0%

动态规划DP

​ 基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。

​ 核心:找到递推公式

二维递归

1.背包问题
2.分割等和子数组(也会背包问题)

给定一个只包含正整数非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

1
2
3
4
5
输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

​ 本题是一个经典的动态规划问题的题型——0/1背包问题,背包的大小为sum(nums)/2。该问题首先要我们初始化一个数组w,w[i]代表能否将背包填充到i,而能将背包填充到i有两种方式,一种是直接使用i大小的块,第二是使用多个小块,因此我们可以总结出递推公式:

​ w[i] = w[i]||w[i-num]

​ 这个递推公式用程序表示就是:

1
2
3
for num in nums:
for i in range(c, num - 1, -1):
w[i] = w[i] or w[i - num]

​ 举例来说:

​ 对于输入[1,5,11,5]来说,
​ 当num=1时,通过递推式只能得到w[1]=true
​ 当num=5时,通过递推式能够得到w[5]=true,w[6]=true,因为可以通过1+5组合
​ 当num=5时,通过递推式能够得到新的w[11]=true(5+6=11)
​ 当num=11时,没有新改动w
​ 所以此时可以发现w[11]=true,所以可以等分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def canPartition(self, nums) -> bool:
# 计算总价值
c = sum(nums)
# 奇数直接排除
if c % 2 != 0:
return False
c = c // 2
w = [False] * (c + 1)
# 第0个位置设置为true,表示当元素出现的时候让w[i-num]为True,也就是w[i]为True
w[0] = True
for num in nums:
for i in range(c, num - 1, -1):
w[i] = w[i] or w[i - num]

return w[c]

​ 当然本题也就可以使用BST,但是时间复杂度太高,leetcode没过

回溯法-深度优先搜索BST

​ 在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。

​ 核心:暴力遍历

1.求解一个集合的全部子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

​ 找子集相关问题的BST基本上采用的核心思想:每个位置都可能出现采用或者不采用两种情况,而如果可能出现重复的元素,那么就要事先将原数组进行排序,存进result之前判断是否已有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

def core(nums,i,tmp):
if i==length:
result.append(tmp)
return
#每次向后遍历时有两种情况,一种是将当前节点值加入到tmp中,一种是不加入
core(nums,i+1,tmp+[nums[i]])
core(nums,i+1,tmp)

nums.sort()
length = len(nums)
result = []
core(nums,0,[])

return result

拓展:含重复的子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""

def core(nums,i,tmp):
if i==length:
if tmp not in result:
result.append(tmp)
return

core(nums,i+1,tmp)
core(nums,i+1,tmp+[nums[i]])

length = len(nums)
result = []
nums.sort() #这里必须要先排序
core(nums,0,[])
return result
2.全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def core(nums,tmp):
if nums==[]:
result.append(tmp)
return

for num in nums:
s = nums[::]
s.remove(num)
core(s,tmp+[num])

result = []
core(nums,[])

return result

拓展:含重复数组的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def permuteUnique(self, nums: List[int]) -> List[List[int]]:


def core(nums,tmp):
if nums==[]:
if tmp not in result:
result.append(tmp)
return

for num in nums:
s = nums[::]
s.remove(num)
core(s,tmp+[num])


result = []
nums.sort()
core(nums,[])
return result
3.划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。

示例 1:

1
2
3
输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:

if k == 1:
return True
#如果不能被k整除,那么直接无解
sum_num = sum(nums)
if sum_num % k != 0:
return False

avg = sum_num // k
nums.sort(reverse=True)

n = len(nums)
if n < k :return False
visited = set() #标志位,标志哪个位置已经被使用过了

def dfs(k,tmp_sum,loc):
#当选用的几个数之和等于目标值,那么k减一,再找下一个子集
if tmp_sum == avg:
return dfs(k-1,0,0)
#如果k==1,由于上面已经验证过可以被k整除,因此一定成立
if k == 1:
return True
for i in range(loc,n):
if i not in visited and nums[i] + tmp_sum <= avg:
visited.add(i)
if dfs(k,tmp_sum+nums[i],i+1):
return True
visited.remove(i)
return False
return dfs(k,0,0)

原始的神经网络语言模型:里面一般有三层,输入层(词向量),隐藏层和输出层(softmax层),里面最大的问题在于从隐藏层到输出的softmax层的计算量很大,因为要计算所有词的softmax概率,再去找概率最大的值

Word2Vec对原始语言模型的改进:

1.对于从输入层到隐藏层的映射,没有采取神经网络的线性变换加激活函数的方法,而是采用简单的对所有输入词向量求和并取平均的方法。

比如输入的是三个4维词向量:(1,2,3,4),(9,6,11,8),(5,10,7,12),那么我们word2vec映射后的词向量就是(5,6,7,8)。由于这里是从多个词向量变成了一个词向量。

2.word2vec采样了霍夫曼树来代替从隐藏层到输出softmax层的映射(Hierarchical Softmax)。这样隐藏层到输出层的softmax不是一步完成的,而是沿着哈弗曼树一步一步完成的。

Hierarchical Softmax

​ 和之前的神经网络语言模型相比,我们的霍夫曼树的所有内部节点就类似之前神经网络隐藏层的神经元,其中,根节点的词向量对应我们的投影后的词向量,而所有叶子节点就类似于之前神经网络softmax输出层的神经元叶子节点的个数就是词汇表的大小

使用Hierarchical Softmax的好处

1.由于是二叉树,之前计算量为V,现在变成了log2V

2.由于使用霍夫曼树是高频的词靠近树根,这样高频词需要更少的时间会被找到。

算法过程

STEP 1:扫描语料库,统计每个词出现的频数,保存在一个hash表中

STEP2:根据个词的词频建立哈弗曼树

  • 最终每个词汇都是哈弗曼树的叶子节点,词频就是相应的权值

  • 根节点对应的词向量就是我们投影后的词向量

  • 而所有叶子节点就类似神经网络softmax输出层的神经元,叶子节点个数就是词汇表大小
  • 非叶子节点代表某一类词
  • 哈弗曼树建立好后每个词都会有一个二进制的哈弗曼编码

STEP3:初始化词向量和哈弗曼树非叶子节点的向量

​ 向量维度是我们给定的参数K。

STEP4:训练,也就是通过梯度下降算法不断优化词向量

​ 在初始化后的词向量,回到语料库,逐句读取一系列的词,然后用梯度下降算法算法算出梯度,更新词向量的值、非叶子检点的值。(哈弗曼树就相当于一个优化后的神经网络)

参数更新过程

基于Negative Sampling的Word2vec

Hierarchical Softmax的的缺点

​ 对于生僻词需要在哈弗曼树中向下走很久。

Negative Sampling算法

​ Negative Sampling不再使用(复杂的Huffman树),而是利用相对简单的随机负采样,能大幅度提升性能,因此,将其作为Hierarchical softmax的替代方案

核心思想通过负采样将问题转化为求解一个正例和neg个负例进行二元回归问题。每次只是通过采样neg个不同的中心词做负例,就可以训练模型

方法:我们有一个训练样本,中心词是w,它周围上下文共有2c个词,记为context(w)。由于这个中心词w,的确和context(w)相关存在,因此它是一个真实的正例。通过Negative Sampling采样,我们得到neg个和w不同的中心词wi,i=1,2,..neg,这样context(w)和wi就组成了neg个并不真实存在的负例利用这一个正例和neg个负例,我们进行二元逻辑回归,得到负采样对应每个词wi对应的模型参数θi,和每个词的词向量

本质上是对训练集进行了采样,从而减小了训练集的大小。

Negative Sampling负采样方法

3、 word2vec负采样有什么作用?

1.加速了模型计算,模型每次只需要更新采样的词的权重,不用更新所有的权重

2.保证了模型训练的效果,中心词其实只跟它周围的词有关系,位置离着很远的词没有关系

常见问题

1.skip gram和cbow各自的优缺点

(1) cbow的速度更快,时间复杂度为O(V),skip-gram速度慢,时间复杂度为O(nV)

​ 在cbow方法中,是用周围词预测中心词,从而利用中心词的预测结果情况,使用GradientDesent方法,不断的去调整周围词的向量。cbow预测行为的次数跟整个文本的词数几乎是相等的(每次预测行为才会进行一次backpropgation, 而往往这也是最耗时的部分),复杂度大概是O(V);

​ 而skip-gram是用中心词来预测周围的词。在skip-gram中,会利用周围的词的预测结果情况,使用GradientDecent来不断的调整中心词的词向量,最终所有的文本遍历完毕之后,也就得到了文本所有词的词向量。可以看出,skip-gram进行预测的次数是要多于cbow的:因为每个词在作为中心词时,都要使用周围每个词进行预测一次这样相当于比cbow的方法多进行了K次(假设K为窗口大小),因此时间的复杂度为O(KV),训练时间要比cbow要长。

(2)当数据较少或生僻词较多时,skip-gram会更加准确;

​ 在skip-gram当中,每个词都要收到周围的词的影响,每个词在作为中心词的时候,都要进行K次的预测、调整。因此, 当数据量较少,或者词为生僻词出现次数较少时, 这种多次的调整会使得词向量相对的更加准确。因为尽管cbow从另外一个角度来说,某个词也是会受到多次周围词的影响(多次将其包含在内的窗口移动),进行词向量的跳帧,但是他的调整是跟周围的词一起调整的,grad的值会平均分到该词上, 相当于该生僻词没有收到专门的训练,它只是沾了周围词的光而已

2.Negative Sampling和Hierarchical softmax各自的优缺点

Hierarchical softmax

优点:

​ 1.由于是二叉树,之前计算量为V,现在变成了log2V,效率更高

​ 2.由于使用霍夫曼树是高频的词靠近树根,这样高频词需要更少的时间会被找到

缺点:

​ 对于生僻词在hierarchical softmax中依旧需要向下走很久

Negative Sampling

优点:

​ 1.对于低频词的计算效率依然很高

3.word2vec的缺点

1.使用的只是局部的上下文信息,对上下文的利用有限

2.和glove相比比较难并行化

4、word2vec和fastText对比有什么区别?(word2vec vs fastText)

1)都可以无监督学习词向量, fastText训练词向量时会考虑subword

2)fastText还可以进行有监督学习进行文本分类,其主要特点:

  • 结构与CBOW类似,但学习目标是人工标注的分类结果;
  • 采用hierarchical softmax对输出的分类标签建立哈夫曼树,样本中标签多的类别被分配短的搜寻路径;
  • 引入N-gram,考虑词序特征;
  • 引入subword来处理长词,处理未登陆词问题;

参考文献:基于Negative Sampling的模型

GMM 是学习出一些概率密度函数

k-means 的结果是每个数据点被 assign 到其中某一个 cluster 了,而 GMM 则给出这些数据点被 assign 到每个 cluster 的概率,又称作 soft assignment。

假设数据服从 Mixture Gaussian Distribution ,换句话说,数据可以看作是从数个 Gaussian Distribution 中生成出来的

准备知识

1.参数估计的方法

概率模型的参数估计分为两大类:

1.不含隐变量的参数估计—极大似然估计/贝叶斯估计法

2.含隐变量的参数估计—EM算法

2.jensen不等式

X是一个随机变量,f(X)是一个凸函数(二阶导数大或等于0),那么有:

当且仅当X是常数的时候等号成立

如果f(X)是凹函数,不等号反向

3.先验概率、后验概率、条件概率

先验概率:P(Y)

先验概率是只根据事情之前发生各个结果出现情况估计的概率(无关特征)

后验概率:P(Y|X)

后验概率是在各个X的分布下各个Y出现的概率(特征符合这个X时Y为这个的概率)

条件概率:P(X|Y)

条件概率是在结果某一种情况时X出现这种分布的概率

4.自信息、互信息

自信息:I(x) = -logp(x)

​ 概率是衡量确定性的度量,那么信息是衡量不确定性的度量.越不确定信息量越高。

互信息:I(x;y) = log(p(x|y)/p(x))

​ 已知y,x的不确定性减少量(其值可正可负)

5.熵

对随机变量平均不确定性的度量,一个系统越有序,信息熵越低。

​ 熵的另一种解读也就是自信息的期望

H(X) = E[I(X)] = ∑P(x)I(x) = -∑p(x)logp(x)

6.条件熵

​ 在给定y条件下,x的条件自信息量为I(x|y),X的集合的条件熵为

​ 进一步在给定Y(各个y)的条件下,X集合的条件熵:

​ 也就是在联合符号集合上的条件自信息量两个概率的加权平均

EM算法

​ EM算法主要用于求解概率模型的极大似然估计极大后验概率。EM算法是通过迭代求解观测数据对数似然函数L(θ) = logP(Y|θ)的极大化,实现参数估计的。

每次迭代主要分为E、M两步:

​ E步:求期望。即求log(P,Z|θ)关于P(Z|Y,θi)的期望

(各个隐变量可能的概率下乘以出现这种结果的总和)

​ M步:极大化Q函数得到新的参数θ

​ 在构建具体的EM算法时,最重要的时定义Q函数,每次迭代中,Em算法通过极大似然化Q函数来增大对数似然函数L(θ)

算法推导

注意:1.EM算法在每次迭代后均能提高观测数据的似然函数值

2.EM算法不能保证全局最优,只能保证局部最优,因此算法受初值的影响

3.EM算法可以用于无监督学习

XGB的优势

1. XGBoost加入了正则化项,正则化项中包含了叶子节点个数,使学到的模型更加简单。原始的GBDT没有,可以有效防止过拟合

2. XGBoost实现了局部并行计算,比原始的GBDT速度快的多

3. XGBoost中内置了缺失值的处理,尝试对缺失值进行分类,然后学习这种分类

4. 可在线学习,这个sklearn中的GBDT也有

5. XGboost允许在交叉验证的过程中实现boosting,通过一次run就能得到boosting迭代的优化量;而GBDT只能人工的使用grid-search

6.支持列抽样。不仅能有效防止过拟合,还能减少计算量

XGBoost的并行计算是如何实现的?

​ 注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完成才能进行下一次迭代的(第t次迭代的代价函数里面包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点)xgboost在训练之前,预先对数据进行排序,然后保存block结构,后面的迭代中重复的使用这个结构,大大减小计算量。这个block结构也使得并行称为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。

XGBoost的参数

​ XGBoost的参数主要分为三大类:

1.调控整个方程的参数

2.调控每步树的参数

3.调控优化表现的变量

1.调控整个方程的参数
  • booster [defalut=gbtree] 基模型
    • gbtree:树模型
    • gblinear:线性模型
  • nthread [default to maximum number of threads available if not set] 使用的线程数
    • 用于并行计算,默认使用全部内核
2.调节基分类器的参数

​ 这里只讨论树模型作为基模型的情况,因为树模型作为基分类器效果总是优于线性模型。

  • eta/learning rate [default=0.3] 学习的初始速率

    • 通过减小每一步的权重能够使建立的模型更加具有鲁棒性
    • 通常最终的数值范围在[0.01-0.2]之间

    Shrinkage(缩减),相当于学习速率。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了消弱每棵树的影响,让后面有更大的学习空间。在实际应用中,一般把学习率设置的小一点,然后迭代次数设置的大一点(补充:传统GBDT的实现也有学习速率)

  • gamma [default=0]

    • 一个节点分裂的条件是其分裂能够起到降低loss function的作用,gamma 定义loss function降低多少才分裂
    • 它的值取决于 loss function需要被调节
  • lambda/reg_lambda [default=1]

    • L2正则化的权重,用于防止过拟合
  • alpha/reg_alpha [default=0]

    • L1正则化的权重,可以用于特征选择
    • 一般用于特征特别多的时候,可以大大提升算法的运算效率
  • subsample [default=1]

    • 每棵树使用的样本比例 [0.5~1]
    • 低值使得模型更保守且能防止过拟合,但太低的值会导致欠拟合
  • colsample_bytree [default=1]
    • 每棵树随机选取的特征的比例 [0.5-1]
3.调控优化表现的参数
  • objective [default=reg:linear]
  • eval_metric
  • seed

调参

调参开始时一般使用较大的学习速率 0.1

1.初始参数设置

max_depth = 5

min_child_weight = 1 #如果是不平衡数据,初始值设置最好小于1

2.首先调节的参数 max_depth和min_child_weight

​ 在整个GBDT中,对整个模型效果影响最大的参数就是max_depth和min_child_weight。

max_depth 一般在3~10先用step为2进行网格搜索找到范围,找到范围再用step为1的网格搜索确定具体值

min_child_weight 一般现在1~6先使用step为2的网格搜索找到最佳参数值范围,然后再用step为1的网格索索确定具体参数值

3. 调整gamma

gamma参数主要用于控制节点是否继续分裂,一般使用网格搜索在0~0.5之间进行步长为0.1的搜索

4.调整subsample和colsample_bytree

这两个参数主要是用来防止拟合的,参数值越小越能防止过拟合 一般0.6~1之间网格搜索

5.尝试降低学习速率增加更多的树

学习速率降为0.1或0.01

结论:1.仅仅通过调参来提升模型效果是很难的

2.要想提升模型效果最主要是通过特征工程、模型融合等方式

为什么要进行归一化?

​ 原因在于神经网络的本身就在于学习数据的分布,一旦训练数据和测试数据分布不同,那么网络的泛化能力也将大大降低;另外一方面,再使用BSGD时一旦每批训练数据的分布不相同,那么网络在每次进行迭代时都要去适应不同的数据分布,这将大大降低网络的学习速度

为什么要使用BN?

​ 这主要是因为对于一般的归一化,只是在输入网络之前对数进行了归一化,而在神经网络的训练过程中并没有对数据做任何处理,而在神经网络的的训练过程中只要网络的前面几层的数据分布发生微小的变化,那么后面的网络就会不断积累放大这个分布的变化,因此一旦有任意一层的数据发生改变,这层以及后面的网络都会需要去从新适应学习这个新的数据分布,而如果训练过程中,每一层的数据都在不断发生变化,那么更将大大影响网络的训练速度,因此需要在网络的每一层输入之前都将数据进行一次归一化,保证数据分布的相同,加快网络训练速度

​ 在另一方面,由于将网络的每一步都进行了标准化,数据分布一致,因此模型的泛化能力将更强。

BN的本质是什么?

一个可学习有参数(γ、β)的使每层数据之前进行归一化的网络层

BN使用位置

线性层后全连接层之前

BN过程

对于一般的归一化没使用下面的公式进行归一化计算:

但是如果仅仅使用上面的公式来对某层的输出做下一层的输入做归一化,那么是会影响到前面一层学习到的特征的。例如:网络中间某一层学习到特征数据本身就分布在S型激活函数的两侧,强制把它归一化处理、标准差也限制在了1,把数据变换成分布于s函数的中间部分,这样就相当于我这一层网络所学习到的特征分布被搞坏了。因此,BN引入了可学习的参数γ、β

​ 上面的公式表明,通过学习到的重构参数γ、β,是可以恢复出原始的某一层所学到的特征的。

BN中为什么要在后面γ、β?不加可以吗?

​ 不可以,因为这是BN中的最关键步骤。不使用γ、β会造成归一化的同时破坏前一层提取到的特征,而BN通过记录每个神经元上的γ、β,使前一层的特征可以通过γ、β得以还原。

BN层是对每一个神经元归一化处理,那在CNN的BN层是怎么应用的?是不参数个数会非常多?

​ 对于CNN上采用了类似权值共享的策略,将一个特征图看做一个神经元,因此参数个数并不会很多。

例如:如果min-batch sizes为m,那么网络某一层输入数据可以表示为四维矩阵(m,f,w,h),m为min-batch sizes,f为特征图个数,w、h分别为特征图的宽高。在CNN中我们可以把每个特征图看成是一个特征处理(一个神经元),因此在使用Batch Normalization,mini-batch size 的大小就是:m.w.h,于是对于每个特征图都只有一对可学习参数:γ、β,总参数个数也就是2m个。

BN的作用

1.防止过拟合。有了BN,dropout和正则化的需求下降了

2.加速训练

BN算法是如何加快训练和收敛速度的呢?

BN算法在实际使用的时候会把特征给强制性的归到均值为0,方差为1的数学模型下。深度网络在训练的过程中,如果每层的数据分布都不一样的话,将会导致网络非常难收敛和训练,而如果能把每层的数据转换到均值为0,方差为1的状态下,一方面,数据的分布是相同的,训练会比较容易收敛,另一方面,均值为0,方差为1的状态下,在梯度计算时会产生比较大的梯度值,可以加快参数的训练,更直观的来说,是把数据从饱和区直接拉到非饱和区。更进一步,这也可以很好的控制梯度爆炸和梯度消失现象,因为这两种现象都和梯度有关。

BN算法为什么能防止过拟合?

在训练中,BN的使用使得一个mini-batch中的所有样本都被关联在了一起,因此网络不会从某一个训练样本中生成确定的结果。

​ 二叉树最常用的遍历算法主要分为下面几种:

1.先序遍历

2.中序遍历

3.后序遍历

4.层次遍历

​ 下面我们将针对这些遍历算法的递归与非递归实现分别给出代码实现以及特点。

这里有一点我们需要注意:

​ 无论是前序、中序、后续,都是指根节点访问的顺序,而左右节点的相对访问顺序永远是相同的,即先访问做节点,后访问右节点。

先序遍历

​ 先序遍历指在二叉树遍历过程中首先输出根节点,然后再分别输出左右节点的遍历方式。

递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def core(result,root):
if root==None:
return
result.append(root.val)
core(result,root.left)
core(result,root.right)

result = []
core(result,root)
return result
非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root==None:
return []

res = []
stack = [root]

while stack:
node = stack.pop()
res.append(node.val)
#注意这里的顺序一定是先右后左,和一般的相反
if node.right!=None:
stack.append(node.right)
if node.left!=None:
stack.append(node.left)

return res

中序遍历

​ 二叉树的中序遍历是指现先遍历左节点,中间遍历根节点,最后在遍历右节点的便利方式。

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Core(root):
if root==None:
return []

Core(root.left)
result.append(root.val)
Core(root.right)

return result

result = []
Core(root)

return result

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root==None:
return []

stack = []
result = []

pos = root

while stack or pos:
if pos:
stack.append(pos)
pos = pos.left
else:
pos = stack.pop()
result.append(pos.val)
pos = pos.right
return result

后序遍历

层次遍历

非递归实现

​ 利用队列先进先出的特点,依次将结点的左、右孩子入队,然后依次出队访问,以此为循环。当有些题目中要求按照层输出时,需要根据每层的节点个数做一个计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []

queue = [root]
result = []

while queue:
tmp = []
number_flag = len(queue) #层节点个数计数器
i = 0
while i<number_flag:
node = queue.pop(0)
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
i += 1
result.append(tmp)

return result

根据两个序列复原二叉树

​ 这种题目其实只有两个,核心是找出先根据一个序列找出根节点,然后在根据另一个序列找出其左右子树的元素,然后不断的递归这个过程即可。

已知前序遍历中序遍历

​ 在已知前序遍历的题目中,就以前序遍历为基础,去不断地区分剩下的数据应该在左子树还是右子树即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
"""
先将前序遍历的第一个节点作为根节点,然后在后序遍历中找到其对应的位置,左右分别做相同的操作
"""
len_pre = len(preorder)
len_in = len(inorder)

if len_pre==0 or len_in==0:
return None


tree_root = TreeNode(preorder[0])
preorder = preorder[1:]


left_len = 0
for i in inorder:
if i==tree_root.val:
break
else:
left_len+=1
inorder.remove(tree_root.val)
if left_len>=1:
tree_root.left = self.buildTree(preorder[:left_len],inorder[:left_len])
if len(preorder)-left_len>=1:
tree_root.right = self.buildTree(preorder[left_len:],inorder[left_len:])

return tree_root
已知前序遍历和后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
"""
前序遍历的第一个节点必定是根节点,随后的节点就是其左子树的根节点,然后再在
后序遍历中找到这个节点的位置就可以确定左子树中有哪些节点,右子树中有哪些节点
"""

tree_root = TreeNode(pre[0])

pre = pre[1:]
post = post[:-1]
left_len = 0

for i in post:
if i==pre[0]:
left_len+=1
break
else:
left_len+=1

if left_len>=1:
tree_root.left = self.constructFromPrePost(pre[:left_len],post[:left_len])
if len(post)-left_len>=1:
tree_root.right = self.constructFromPrePost(pre[left_len:],post[left_len:])

return tree_root
已知中序后序遍历构造二叉树
 没有前序遍历时,使用后序遍历定根节点     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:  
len_in = len(inorder)
len_post = len(postorder)
if len_in==0 or len_in!=len_post:
return None

tree_root = TreeNode(postorder[-1])
postorder = postorder[:-1]
left_len = 0

for i in inorder:
if i==tree_root.val:
break
else:
left_len += 1

inorder.remove(tree_root.val)
if left_len>=1:
tree_root.left = self.buildTree(inorder[:left_len],postorder[:left_len])
if len(postorder)-left_len>=1:
tree_root.right = self.buildTree(inorder[left_len:],postorder[left_len:])

return tree_root

二叉搜索树

二叉搜索树的性质:

​ 1.中序遍历的结果有序

​ 2.左子树上的节点都比根节点小,右子树都比根节点大

修剪二叉搜索树

​ 给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""

if root==None:
return None

if root.val<L:
return self.trimBST(root.right,L,R)
elif root.val>R:
return self.trimBST(root.left,L,R)
else:
root.left = self.trimBST(root.left,L,R)
root.right = self.trimBST(root.right,L,R)

return root
把二叉搜索树转化为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如:

1
2
3
4
5
6
7
8
9
输入: 二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
root_ref = root
stack = []
prev = 0
while stack or root:
while root:
stack.append(root)
root = root.right
root = stack.pop()
root.val += prev
prev = root.val
root = root.left
return root_ref
验证搜索二叉树

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
方法一:用搜索二叉树的性质1,中序遍历一定有序,那么我们只需要在中序遍历中保证后添加的数比前面添加的最后一个数的即可,出现不符合这一规律的直接返回False
注:这里需要特别注意,二叉搜索数中不能出现两个一样的值,因此不能直接输出中序序列和排序号好的序列对比
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
stack = []
pos = root

result = []
while stack or pos:
while pos:
stack.append(pos)
pos = pos.left

pos = stack.pop()
if result!=[]:
if result[-1]<pos.val:
result.append(pos.val)
else:
return False
else:
result.append(pos.val)
pos = pos.right

return True

回文子串

例:给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""

length = len(s)
result = 0
for i in range(length):
for j in range(i+1,length+1): #这里注意循环的范围为range(i+1,length+1)
if s[i:j]==s[i:j][::-1]:
result += 1

return result

最长回文子串

​ 最长回文子串也是回文串中常见的一中题目,下面是例题

例:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

思路一:Manacher算法

​ 首先先将字符串首尾以及字符和字符之间采用”#“进行补齐,补齐后的字符串总长度2n+1(n为原始字符串长度)。然后从第一个非#字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def get_length(string, index):
# 循环求出index为中心的最长回文字串
length = 0
seq = ""
if string[index]!="#":
seq = string[index]
length = 1
string_len = len(string)
for i in range(1,index+1):
if index+i<string_len and string[index-i]==string[index+i]:
# print(string[index-i],seq+string[index+i])
if string[index-i]!="#":
length +=2
seq = string[index-i]+seq+string[index+i]
else:
break
return length,seq

s_list = [i for i in s]
string = "#"+"#".join(s)+"#"

length = len(string)
max_length = 0
max_seq = ""

for index in range(0,length):
# print("====")
tmp_len,tmp_seq = get_length(string,index)
# print(tmp_len,tmp_seq)
if tmp_len>max_length:
max_length = tmp_len
max_seq = tmp_seq

return max_seq

思路二:动态规划

​ 这里的动态规划的核心思路就是从头开始向后进行遍历,每次想看头尾同时加入比最大之前最大回文子串的长多+1字符串是不是回文子串(注意但是首部索引不能超过0),如果是则记录起始节点start,max_len的值+2;否则判断只在尾部进行字符串加1的字符串时不是回文子串(这里之说以不必尝试在头部加1,因为再从头开始遍历的过程中已经尝试了头部加1),如果是记录start节点,max_len的值+2

​ f(x+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""

length = len(s)
max_len = 0
start = 0

for i in range(length):
if i-max_len>=1 and s[i-max_len-1:i+1]==s[i-max_len-1:i+1][::-1]:
start = i-max_len-1
max_len += 2
elif i-max_len>=0 and s[i-max_len:i+1]==s[i-max_len:i+1][::-1]:
start = i-max_len
max_len += 1

return s[start:start+max_len]

最长回文子序列516

z

​ 在含环的问题中,存在一些关键性的结论,在解决问题时非常有帮助,下面是一些相关的总结。

1.判断链表是否有环

​ 结论:一个速度为1的low指针和一个速度为2的fast指针同时从头向前走,如果其中fast指针为None,那么则为无环,如果两个只能指向的元素相等,那么链表有环。

2.判断链表的环入口节点

​ 结论:函数一样的双指针进行遍历,如果fast指针为None,那么则为无环。如果两个指针指向的的元素相同,那么这个节点到链表入口点的长度链表头到链表入口点的长度相等。

推导过程:

​ 设链表头到入口节点的长度为a

​ 链表入口节点到相遇节点的长度为b

​ 相遇节点到链表入口节点的长度为c

​ 那么因为fast的速度为2,low的速度为1,因此可以认为low入环时走在前面,每次fast和low之间的距离缩小1,因此,必定会在第一圈完成之前相遇。所以有

​ low 在环内位置: (a+b)-a mod (b+c) -> b mod (b+c)

​ fast 在环内位置:2(a+b)-a mod (b+c) -> a+2b mod (b+c)

二者应该相等,因此得出 a+b mod (b+c) = 0 即a = c

​ 利用这个结论,我们可以先判断判断链表是否有环,如果有环,那么先找到相间的节点,然后再用一个新指针从头开始以速度为1和low指针从相交节点同时开始遍历,当两个点相交的节点即为环入口节点。

例题:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def detectCycle(head):
"""
:type head: ListNode
:rtype: ListNode
"""
low,fast = head,head

while fast and fast.next and fast.next:
low, fast = low.next, fast.next.next
if fast==low:
p = head
while p!=low:
p = p.next
low = low.next
return p
return None

3.变形型题目

​ 有一类题目不会明显的说让解决环的问题,但是使用环来解决,往往会起到意想不到的效果。

例题:编写一个程序,找到两个单链表相交的起始节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def getIntersectionNode(headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if headA==None or headB==None:
return None

#相判断两个是否相交
pA = headA
pB = headB

while pA.next:
pA = pA.next

while pB.next:
pB = pB.next


if pA!=pB:
return None

#将PA首尾相接
tail = pA
pA.next = headA

fast = headB
low = headB

while True:
fast = fast.next.next
low = low.next
if fast==low:
s = headB
while s!=low:
low = low.next
s = s.next
tail.next = None
return s

这道题利用了和上一道题目完全一样的规律解决

test2

​ transformer模型来自于Google的经典论文Attention is all you need,在这篇论文中作者采用Attention来取代了全部的RNN、CNN,实现效果效率的双丰收。

​ 现在transformer在NLP领域已经可以达到全方位吊打CNN、RNN系列的网络,网络处理时间效率高,结果稳定性可靠性都比传统的CNN、RNN以及二者的联合网络更好,因此现在已经呈现出了transformer逐步取代二者的大趋势。

下面是从一系列的论文中获取到的RNN、CNN、Transformer三者的对比结论:

1.从任务综合效果方面来说,Transformer明显优于CNN,CNN略微优于RNN。

2.速度方面Transformer和CNN明显占优,RNN在这方面劣势非常明显。(主流经验上transformer和CNN速度差别不大,RNN比前两者慢3倍到几十倍)

Transformer模型具体细节

​ transformer模型整体结构上主要EncoderDecoder两部分组成,Encoder主要用来将数据进行特征提取,而Decoder主要用来实现隐向量解码出新的向量表示(原文中就是新的语言表示),由于原文是机器翻译问题,而我们要解决的问题是类文本分类问题,因此我们直接减Transformer模型中的Encoder部分来进行特征的提取。其中主要包括下面几个核心技术模块:

1.残差连接

2.Position-wise前馈网络

3.多头self-attention

4.位置编码

​ 1.采用全连接层进行Embedding (Batch_size,src_vocab_size,model_dim)

​ 2.在进行位置编码,位置编码和Embedding的结果进行累加

​ 3.进入Encoder_layer进行编码处理(相当于特征提取)

​ (1)

1.位置编码(PositionalEncoding)

​ 大部分编码器一般都采用RNN系列模型来提取语义相关信息,但是采用RNN系列的模型来进行语序信息进行提取具有不可并行、提取效率慢等显著缺点,本文采用了一种 Positional Embedding方案来对于语序信息进行编码,主要通过正余弦函数,

image-20190304162008847

在偶数位置,使用正弦编码;在奇数位置使用余弦进行编码。

为什么要使用三角函数来进行为之编码?

​ 首先在上面的公式中可以看出,给定词语的pos可以很简单其表示为$d_{model}$维的向量,也就是说位置编码的每一个位置每一个维度对应了一个波长从2π到100002π的等比数列的正弦曲线,也就是说可以表示各个各个位置的*绝对位置

​ 在另一方面,词语间的相对位置也是非常重要的,这也是选用正余弦函数做位置编码的最主要原因。因为

​ 因此对于词汇间位置偏移k,PE(pos+k)可以表示为PE(pos)和PE(k)组合的形式,也就是具有相对位置表达能力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class PositionalEncoding(nn.Module):

"""
位置编码层
"""

def __init__(self, d_model, max_seq_len):
"""
初始化
Args:
d_model: 一个标量。模型的维度,论文默认是512
max_seq_len: 一个标量。文本序列的最大长度
"""
super(PositionalEncoding, self).__init__()

# 根据论文给的公式,构造出PE矩阵
position_encoding = np.array([
[pos / np.power(10000, 2.0 * (j // 2) / d_model) for j in range(d_model)]
for pos in range(max_seq_len)])
# 偶数列使用sin,奇数列使用cos
position_encoding[:, 0::2] = np.sin(position_encoding[:, 0::2])
position_encoding[:, 1::2] = np.cos(position_encoding[:, 1::2])
position_encoding = torch.Tensor(position_encoding)

# 在PE矩阵的第一行,加上一行全是0的向量,代表这`PAD`的positional encoding
# 在word embedding中也经常会加上`UNK`,代表位置单词的word embedding,两者十分类似
# 那么为什么需要这个额外的PAD的编码呢?很简单,因为文本序列的长度不一,我们需要对齐,
# 短的序列我们使用0在结尾补全,我们也需要这些补全位置的编码,也就是`PAD`对应的位置编码
pad_row = torch.zeros([1, d_model])
position_encoding = torch.cat((pad_row, position_encoding))

# 嵌入操作,+1是因为增加了`PAD`这个补全位置的编码,
# Word embedding中如果词典增加`UNK`,我们也需要+1。看吧,两者十分相似
self.position_encoding = nn.Embedding(max_seq_len + 1, d_model)
self.position_encoding.weight = nn.Parameter(position_encoding,
requires_grad=False)
def forward(self, input_len,max_len):
"""
神经网络的前向传播。
Args:
input_len: 一个张量,形状为[BATCH_SIZE, 1]。每一个张量的值代表这一批文本序列中对应的长度。
param max_len:数值,表示当前的词的长度

Returns:
返回这一批序列的位置编码,进行了对齐。
"""
# 找出这一批序列的最大长度
tensor = torch.cuda.LongTensor if input_len.is_cuda else torch.LongTensor

# 对每一个序列的位置进行对齐,在原序列位置的后面补上0
# 这里range从1开始也是因为要避开PAD(0)的位置
input_pos = tensor(
[list(range(1, len + 1)) + [0] * (max_len - len) for len in input_len.tolist()])

return self.position_encoding(input_pos)

2.scaled Dot-Product Attention

scaled代表着在原来的dot-product Attention的基础上加入了缩放因子$1/sqrt(d_k)$,$d_k$表示Key的维度,默认用64.

为什么要加入缩放因子?

​ 在$d_k$(key的维度)很大时,点积得到的结果维度很大,使的结果处于softmax函数梯度很小的区域,这是后乘以一个缩放因子,可以缓解这种情况的发生。

Dot-Produc代表乘性attention,attention计算主要分为加性attention和乘性attention两种。加性 Attention 对于输入的隐状态 $h_t$ 和输出的隐状态 $s_t$直接做 concat 操作,得到 [$h_t:s_t$] ,乘性 Attention 则是对输入和输出做 dot 操作。

Attention又是什么呢?通俗的解释Attention机制就是通过query和key的相似度确定value的权重。论文中具体的Attention计算公式为:

​ 在这里采用的scaled Dot-Product Attention是self-attention的一种,self-attention是指Q(Query), K(Key), V(Value)三个矩阵均来自同一输入。就是下面来具体说一下K、Q、V具体含义:

  1. 在一般的Attention模型中,Query代表要进行和其他各个位置的词做点乘运算来计算相关度的节点,Key代表Query要进行查询的各个节点,每个Query都要遍历全部的K节点,计算点乘计算相关度,然后经过缩放和softmax进行归一化的到当前Query和各个Key的attention score,然后再使用这些attention score与Value相乘得到attention加权向量
  2. 在self-attention模型中,Key、Query、Value均来自相同的输入
  3. 在transformer的encoder中的Key、Query、Value都来自encoder上一层的输入,对于第一层encoder layer,他们就是word embedding的输出和positial encoder的加和。

query、key、value来源:

​ 他们三个是由原始的词向量X乘以三个权值不同的嵌入向量$W_q、W_k、W_v$得到的,三个矩阵尺寸相同

Attention计算步骤:

  1. 如上文,将输入单词转化成嵌入向量;
  2. 根据嵌入向量得到 q、k、v三个向量;
  3. 为每个向量计算一个score: score = q*k
  4. 为了梯度的稳定,Transformer使用了score归一化,即除以 sqrt(dk);
  5. 对score施以softmax激活函数;
  6. softmax点乘Value值 v ,得到加权的每个输入向量的评分 v;
  7. 相加之后得到最终的输出结果Sum(z) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class ScaledDotProductAttention(nn.Module):
"""
标准的scaled点乘attention层
"""
def __init__(self, attention_dropout=0.0):
super(ScaledDotProductAttention, self).__init__()
self.dropout = nn.Dropout(attention_dropout)
self.softmax = nn.Softmax(dim=2)

def forward(self, q, k, v, scale=None, attn_mask=None):
"""
前向传播.
Args:
q: Queries张量,形状为[B, L_q, D_q]
k: Keys张量,形状为[B, L_k, D_k]
v: Values张量,形状为[B, L_v, D_v],一般来说就是k
scale: 缩放因子,一个浮点标量
attn_mask: Masking张量,形状为[B, L_q, L_k]

Returns:
上下文张量和attention张量
"""
attention = torch.bmm(q, k.transpose(1, 2))

if scale:
attention = attention * scale
if attn_mask is not None:
# 给需要 mask 的地方设置一个负无穷
attention = attention.masked_fill(attn_mask,-1e9)

# 计算softmax
attention = self.softmax(attention)
# 添加dropout
attention = self.dropout(attention)
# 和V做点积
context = torch.bmm(attention, v)

return context, attention

3.多头Attention

​ 论文作者发现将 Q、K、V 通过一个线性映射之后,分成 h 份,对每一份进行 scaled dot-product attention 效果更好。然后,把各个部分的结果合并起来,再次经过线性映射,得到最终的输出。这就是所谓的 multi-head attention。上面的超参数 h 就是 heads 的数量。论文默认是 8。

​ 这里采用了四个全连接层+有个dot_product_attention层(也可以说是8个)+layer_norm实现。

为什么要使用多头Attention?

​ 1.”多头机制“能让模型考虑到不同位置的Attention

​ 2.”多头“Attention可以在不同的足空间表达不一样的关联

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class MultiHeadAttention(nn.Module):
"""
多头Attention层
"""

def __init__(self, model_dim=512, num_heads=8, dropout=0.0):
super(MultiHeadAttention, self).__init__()

self.dim_per_head = model_dim // num_heads
self.num_heads = num_heads

self.linear_k = nn.Linear(model_dim, self.dim_per_head * num_heads)
self.linear_v = nn.Linear(model_dim, self.dim_per_head * num_heads)
self.linear_q = nn.Linear(model_dim, self.dim_per_head * num_heads)

self.dot_product_attention = ScaledDotProductAttention(dropout)
self.linear_final = nn.Linear(model_dim, model_dim)
self.dropout = nn.Dropout(dropout)

self.layer_norm = nn.LayerNorm(model_dim)

def forward(self, key, value, query, attn_mask=None):

# 残差连接
residual = query
dim_per_head = self.dim_per_head
num_heads = self.num_heads
batch_size = key.size(0)
# 线性层 (batch_size,word_nums,model_dim)
key = self.linear_k(key)
value = self.linear_v(value)
query = self.linear_q(query)

# 将一个切分成多个(batch_size*num_headers,word_nums,word//num_headers)
"""
这里用到了一个trick就是将key、value、query值要进行切分不需要进行真正的切分,直接将其维度整合到batch_size上,效果等同于真正的切分。过完scaled dot-product attention 再将其维度恢复即可
"""
key = key.view(batch_size * num_heads, -1, dim_per_head)
value = value.view(batch_size * num_heads, -1, dim_per_head)
query = query.view(batch_size * num_heads, -1, dim_per_head)
#将mask也复制多份和key、value、query相匹配 (batch_size*num_headers,word_nums_k,word_nums_q)
if attn_mask is not None:
attn_mask = attn_mask.repeat(num_heads, 1, 1)

# 使用scaled-dot attention来进行向量表达
#context:(batch_size*num_headers,word_nums,word//num_headers)
#attention:(batch_size*num_headers,word_nums_k,word_nums_q)
scale = (key.size(-1)) ** -0.5
context, attention = self.dot_product_attention(
query, key, value, scale, attn_mask)

# concat heads
context = context.view(batch_size, -1, dim_per_head * num_heads)
# final linear projection
output = self.linear_final(context)

# dropout
output = self.dropout(output)

# 这里使用了残差连接和LN
output = self.layer_norm(residual + output)

return output, attention

4.残差连接

​ 在上面的多头的Attnetion中,还采用了残差连接机制来保证网络深度过深从而导致的精度下降问题。这里的思想主要来源于深度残差网络(ResNet),残差连接指在模型通过一层将结果输入到下一层时也同时直接将不通过该层的结果一同输入到下一层,从而达到解决网络深度过深时出现精确率不升反降的情况。

为什么残差连接可以在网络很深的时候防止出现加深深度而精确率下降的情况?

​ 神经网络随着深度的加深会会出现训练集loss逐渐下贱,趋于饱和,然后你再加深网络深度,训练集loss不降反升的情况。这是因为随着网络深度的增加,在深层的有效信息可能变得更加模糊,不利于最终的决策网络做出正确的决策,因此残差网络提出,建立残差连接的方式来将低层的信息也能传到高层,因此这样实现的深层网络至少不会比浅层网络差。

5.Layer normalization

Normalization

​ Normalization 有很多种,但是它们都有一个共同的目的,那就是把输入转化成均值为 0 方差为 1 的数据。我们在把数据送入激活函数之前进行 normalization(归一化),因为我们不希望输入数据落在激活函数的饱和区。

Batch Normalization(BN)

​ 应用最广泛的Normalization就是Batch Normalization,其主要思想是:在每一层的每一批数据上进行归一化。我们可能会对输入数据进行归一化,但是经过该网络层的作用后,我们的数据已经不再是归一化的了。随着这种情况的发展,数据的偏差越来越大,我的反向传播需要考虑到这些大的偏差,这就迫使我们只能使用较小的学习率来防止梯度消失或者梯度爆炸。

Layer normalization(LN)

​ LN 是在每一个样本上计算均值和方差,而不是 BN 那种在批方向计算均值和方差.

Layer normalization在pytorch 0.4版本以后可以直接使用nn.LayerNorm进行调用

6.Mask

mask 表示掩码,它对某些值进行掩盖,使其在参数更新时不产生效果。Transformer 模型里面涉及两种 mask,分别是 padding masksequence mask

​ 在我们使用的Encoder部分,只是用了padding mask因此本文重点介绍padding mask。

padding mask

​ 什么是 padding mask 呢?因为每个批次输入序列长度是不一样的也就是说,我们要对输入序列进行对齐。具体来说,就是给在较短的序列后面填充 0。因为这些填充的位置,其实是没什么意义的,所以我们的 attention 机制不应该把注意力放在这些位置上,所以我们需要进行一些处理。具体的做法是,把这些位置的值加上一个非常大的负数(负无穷),这样的话,经过 softmax,这些位置的概率就会接近0!而我们的 padding mask 实际上是一个张量,每个值都是一个 Boolean,值为 false 的地方就是我们要进行处理的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def padding_mask(seq_k, seq_q):
"""
param seq_q:(batch_size,word_nums_q)
param seq_k:(batch_size,word_nums_k)
return padding_mask:(batch_size,word_nums_q,word_nums_k)
"""

# seq_k和seq_q 的形状都是 (batch_size,word_nums_k)
len_q = seq_q.size(1)
# 找到被pad填充为0的位置(batch_size,word_nums_k)
pad_mask = seq_k.eq(0)
#(batch_size,word_nums_q,word_nums_k)
pad_mask = pad_mask.unsqueeze(1).expand(-1, len_q, -1) # shape [B, L_q, L_k]

return pad_mask

3.Position-wise 前馈网络

​ 这是一个全连接网络,包含两个线性变换和一个非线性函数(实际上就是 ReLU)

这里实现上用到了两个一维卷积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class PositionalWiseFeedForward(nn.Module):
"""
前向编码,使用两层一维卷积层实现
"""

def __init__(self, model_dim=512, ffn_dim=2048, dropout=0.0):
super(PositionalWiseFeedForward, self).__init__()
self.w1 = nn.Conv1d(model_dim, ffn_dim, 1)
self.w2 = nn.Conv1d(ffn_dim, model_dim, 1)
self.dropout = nn.Dropout(dropout)
self.layer_norm = nn.LayerNorm(model_dim)

def forward(self, x):
output = x.transpose(1, 2)
output = self.w2(F.relu(self.w1(output)))
output = self.dropout(output.transpose(1, 2))

# add residual and norm layer
output = self.layer_norm(x + output)
return output