0. 基础
0.1 语言基础
python yeild return区别
https://l1nwatch.gitbook.io/interview_exercise/stackoverflow-about-python/python-zhong-guan-jian-zi-yield-you-shi-mo-zuo-yong
带yeild函数为生成器,而不是函数,只能调用一次,不是所有结果都在内存里
生成器可以控制资源访问
Python 装饰器
本质上就是一个高阶函数(函数的函数),用于修改增加函数的功能,可用于鉴权 日志等
python 多线程 多进程
只能利用单核 假的多线程
python的原始解释器CPython中存在着GIL
Python代码的执行由Python虚拟机(解释器)来控制。Python在设计之初就考虑要在主循环中,同时只有一个线程在执行,就像单CPU的系统中运行多个进程那样,内存中可以存放多个程序,但任意时刻,只有一个程序在CPU中运行。同样地,虽然Python解释器可以运行多个线程,只有一个线程在解释器中运行。对Python虚拟机的访问由全局解释器锁(GIL)来控制,正是这个锁能保证同时只有一个线程在运行。
在多线程环境中,Python虚拟机按照以下方式执行。1.设置GIL。2.切换到一个线程去执行。3.运行。4.把线程设置为睡眠状态。5.解锁GIL。6.再次重复以上步骤。
多进程
https://www.liaoxuefeng.com/wiki/1016959663602400/1017628290184064
from multiprocessing import Pool
进程间通信 通过queue pipe
我们以Queue为例,在父进程中创建两个子进程,一个往Queue里写数据,一个从Queue里读数据:
线程安全
线程间共享变量 及global变量 在多线程环境下 都是不安全的
需要使用threading 同步机制
代码语言:txt复制from threading import Thread, Lock, enumerate
import time
num = 0
mutex = Lock()
def add_num():
global num
for i in range(100000):
mutex.acquire()
num = 1
mutex.release()
读写锁
可以多个线程同时占用读模式的读写锁,但是只能一个线程占用写模式的读写锁。
代码语言:txt复制import threading
class RWlock(object):
def __init__(self):
self._lock = threading.Lock()
self._extra = threading.Lock()
self.read_num = 0
def read_acquire(self):
with self._extra:
self.read_num = 1
if self.read_num == 1:
self._lock.acquire()
def read_release(self):
with self._extra:
self.read_num -= 1
if self.read_num == 0:
self._lock.release()
def write_acquire(self):
self._lock.acquire()
def write_release(self):
self._lock.release()
python2 python3 map的差别
map()是 Python内置的高阶函数,它接收一个函数 f 和一个 list,并通过把函数 f 依次作用在 list 的每个元素上,得到一个新的 list 并返回。
代码语言:txt复制def f(x):
return x*x
print map(f, [1, 2, 3, 4, 5, 6, 7, 8, 9])
执行结果:1, 4, 9, 10, 25, 36, 49, 64, 81
但是在python3返回的是
现在我们只需要将print(map(f,1,2,3,4))写成print(list(map(f,1,2,3,4)))就好了。
因为在python3中接收一个函数 f 和一个 list,并通过把函数 f 依次作用在 list 的每个元素上,得到一个新的 tuple 并返回。
所以我们直接强制转化就ok了
Python2中,map()函数的func可以为None,如map(seq1,seq2[,...[,seqn),其作用类似于将seq*中的对应索引的值取出作为一个元组,最终返回一个包含多个元组的列表。而Python3中,map()函数如果不指定func,则最终对返回的map对象转换时就会抛"TypeError"
函数初始化列表为空
会有深浅拷贝问题,需要在函数体内初始化空数组
https://blog.csdn.net/Aifore/article/details/84257494
super()函数与MRO
super()函数用于调用父类方法
在多继承场景下如何找到父类?
MRO:
http://c.biancheng.net/view/5450.html
0.2 计算机基础
线程
操作系统中可执行调度最小单元
同步与互斥锁
同步就是程序按预定的先后次序依次运行。
通过线程同步机制,能保证共享数据在任何时刻,最多有一个线程访问,以保证数据的正确性。
互斥锁为资源引入了一个状态:锁定/非锁定
某个线程要更改共享数据时,先将其锁定,此时资源的状态为“锁定”,其他线程不能更改。直到该线程释放资源,将资源的状态变成“非锁定”,其他的线程才能再次锁定该资源。互斥锁保证了每次只有一个线程进行操作,从而保证了多线程情况下数据的正确性。
预防死锁:
- 使用可重入锁Rlock 底层维护计数器与互斥锁,不同线程count 不会阻塞
- 避免多次锁定
- 保证加锁顺序
- 加入超时定时锁 自动释放锁
拷贝
直接赋值:其实就是对象的引用(别名)。
浅拷贝(copy):拷贝父对象,不会拷贝对象的内部的子对象。
深拷贝(deepcopy): copy 模块的 deepcopy 方法,完全拷贝了父对象及其子对象。
0.3 数据结构
快排
代码语言:txt复制def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i = 1
array[i], array[j] = array[j], array[i]
array[i 1], array[r] = array[r], array[i 1]
return i 1
二分查找
代码语言:txt复制# 返回 x 在 arr 中的索引,如果不存在返回 -1
def binarySearch (arr, l, r, x):
# 基本判断
if r >= l:
mid = int(l (r - l)/2)
# 元素整好的中间位置
if arr[mid] == x:
return mid
# 元素小于中间位置的元素,只需要再比较左边的元素
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# 元素大于中间位置的元素,只需要再比较右边的元素
else:
return binarySearch(arr, mid 1, r, x)
else:
# 不存在
return -1
树的遍历
前序 中序 后序 (左右 根节点 根节点的位置)
1. 机器学习基础
1.1 基础模型
激活函数总结
https://zhuanlan.zhihu.com/p/73214810
sigmoid
- sigmoid函数可以把实数域光滑的映射到0,1空间。
- 函数值恰好可以解释为属于正类的概率(概率的取值范围是0~1),中心为0.5。
- sigmoid函数单调递增,连续可导,导数形式非常简单,是一个比较合适的函数
优点:平滑、易于求导
缺点:
- 激活函数计算量大(在正向传播和反向传播中都包含幂运算和除法);
- 反向传播求误差梯度时,求导涉及除法;
- Sigmoid导数取值范围是0, 0.25,由于神经网络反向传播时的“链式反应”,很容易就会出现梯度消失的情况。例如对于一个10层的网络, 根据0.25^10很小,第10层的误差相对第一层卷积的参数W1的梯度将是一个非常小的值,这就是所谓的“梯度消失”。
- Sigmoid的输出不是0均值(即zero-centered);这会导致后一层的神经元将得到上一层输出的非0均值的信号作为输入,随着网络的加深,会改变数据的原始分布。
推导:https://zhuanlan.zhihu.com/p/24967776
tanh
tanh为双曲正切函数,其英文读作Hyperbolic Tangent。tanh和 sigmoid 相似,都属于饱和激活函数,区别在于输出值范围由 (0,1) 变为了 (-1,1),可以把 tanh 函数看做是 sigmoid 向下平移和拉伸后的结果
tanh作为激活函数的特点:
相比Sigmoid函数,
- tanh的输出范围时(-1, 1),解决了Sigmoid函数的不是zero-centered输出问题;
- 幂运算的问题仍然存在;
- tanh导数范围在(0, 1)之间,相比sigmoid的(0, 0.25),梯度消失(gradient vanishing)问题会得到缓解,但仍然还会存在
DNN 前面使用tanh 最后用sigmoid
relu
Relu(Rectified Linear Unit)——修正线性单元函数:该函数形式比较简单,
公式:relu=max(0, x)
ReLU作为激活函数的特点:
- 相比Sigmoid和tanh,ReLU摒弃了复杂的计算,提高了运算速度。
- 解决了梯度消失问题,收敛速度快于Sigmoid和tanh函数,但要防范ReLU的梯度爆炸
- 容易得到更好的模型,但也要防止训练中出现模型‘Dead’情况。
ReLU 强制将x<0部分的输出置为0(置为0就是屏蔽该特征),可能会导致模型无法学习到有效特征,所以如果学习率设置的太大,就可能会导致网络的大部分神经元处于‘dead’状态,所以使用ReLU的网络,学习率不能设置太大。
Leaky ReLU中的公式为常数,一般设置 0.01。这个函数通常比 Relu 激活函数效果要好,但是效果不是很稳定,所以在实际中 Leaky ReLu 使用的并不多。
PRelu(参数化修正线性单元) 中的公式作为一个可学习的参数,会在训练的过程中进行更新。
RReLU(随机纠正线性单元)也是Leaky ReLU的一个变体。在RReLU中,负值的斜率在训练中是随机的,在之后的测试中就变成了固定的了。RReLU的亮点在于,在训练环节中,aji是从一个均匀的分布U(I,u)中随机抽取的数值。
RNN seq2seq LSTM GRU
https://cloud.tencent.com/developer/article/1869960
RNN中为什么要采用tanh而不是ReLu作为激活函数?
https://www.zhihu.com/question/61265076
relu可能会导致梯度消失,直接把激活函数换成ReLU会导致非常大的输出值,将激活函数换成ReLU也不能解决梯度在长程上传递的问题
Attention
Attention 种类
Soft/Hard Attention
soft attention:传统attention,可被嵌入到模型中去进行训练并传播梯度
hard attention:不计算所有输出,依据概率对encoder的输出采样,在反向传播时需采用蒙特卡洛进行梯度估计
Global/Local Attention
global attention:传统attention,对所有encoder输出进行计算
local attention:介于soft和hard之间,会预测一个位置并选取一个窗口进行计算
Self Attention
传统attention是计算Q和K之间的依赖关系,而self attention则分别计算Q和K自身的依赖关系。
beam search
https://blog.csdn.net/weixin_38937984/article/details/102492050
神经网络中的参数计算
https://zhuanlan.zhihu.com/p/33223290
XGBoost原理及推导
https://cloud.tencent.com/developer/article/1835890
XGBoost 特征重要度排序
https://zhuanlan.zhihu.com/p/355884348
https://www.jianshu.com/p/2920c97e9e16
- weight
xgb.plot_importance
这是我们常用的绘制特征重要性的函数方法。其背后用到的贡献度计算方法为weight
。
‘weight’ - the number of times a feature is used to split the data across all trees.
简单来说,就是在子树模型分裂时,用到的特征次数。这里计算的是所有的树。这个指标在R包里也被称为frequency
。
weight 将给予数值特征更高的值,因为它的变数越多,树分裂时可切割的空间越大。所以这个指标,会掩盖掉重要的枚举特征。
- gain
model.feature_importances_
这是我们调用特征重要性数值时,用到的默认函数方法。其背后用到的贡献度计算方法为gain
。
‘gain’ - the average gain across all splits the feature is used in.
gain 是信息增益的泛化概念。这里是指,节点分裂时,该特征带来信息增益(目标函数)优化的平均值。
gain 用到了熵增的概念,它可以方便的找出最直接的特征。即如果某个特征的下的0,在label下全是0,则这个特征一定会排得靠前。
- cover
model = XGBRFClassifier(importance_type = 'cover')
这个计算方法,需要在定义模型时定义。之后再调用model.feature_importances_
得到的便是基于cover
得到的贡献度。
‘cover’ - the average coverage across all splits the feature is used in.
cover 形象来说,就是树模型在分裂时,特征下的叶子结点涵盖的样本数除以特征用来分裂的次数。分裂越靠近根部,cover 值越大。
cover 对于枚举特征,会更友好。同时,它也没有过度拟合目标函数,不受目标函数的量纲影响。
1.2 训练与调优
batch_size 过大或者过小问题
https://www.zhihu.com/question/32673260
https://zhuanlan.zhihu.com/p/86529347
batch size过小,花费时间多,同时梯度震荡严重,不利于收敛;
batch size过大,不同batch的梯度方向没有任何变化,容易陷入局部极小值。
learning_rate 如何设置
过小:速度慢,易过拟合
过大:震荡
0.01 - 0.001 ,逐渐衰减 衰减倍数100倍
L0 L1 L2正则区别
https://blog.csdn.net/zouxy09/article/details/24971995
https://www.zhihu.com/question/26485586
L0范数(非零参数的个数)特征系数,难求解
L1 lasso 删除影响过大feature,可用于特征筛选,难优化求解(梯度不变),许多特征=0
L2 ridge 特征平均,防止过拟合,提高泛化能力,许多特征趋近0
优化器选择
https://cloud.tencent.com/developer/article/1872633
batch normalize
https://www.cnblogs.com/shine-lee/p/11989612.html
公式原理
设某一隐藏层的输入是 Ai−1,类似公式(2),首先需要求出中间值
Zi=Wi∗Ai−1 bi(3)
然后在求出激活值Ai之前进行BN,过程如下
设当前mini-batch有m个样本,对应m个中间值,分别为Z(1)i、Z(2)i、Z(3)i……Z(m)i
①首先求出当前中间值的均值和方差
均值:μ=1m∑mj=1Zji 方差:δ2=1m∑mj=1(Zji−μ)2
②然后进行normalization,与公式(1)相似
Zjinorm=Zji−μδ2 ϵ√(4)
可以对比看一下上面的公式(1),这里略有不同的是δ2 ϵ−−−−−√替代δ是为了避免分母为0
进行到这一步,Zinorm已经是一个均值为0,方差为1的变量,但是我们不希望所有层的分布总是如此,毕竟我们希望隐藏层能够学习到足够的知识,而数据的分布本身就是需要学习到的,所以我们进一步计算
③适当进行缩放和平移
bni=γZinorm β(5)
缩放参数γ和平移参数β,使得该隐藏层的均值变为β,方差变为γ,这两个参数参与模型的训练,就像权重矩阵W一样用梯度下降进行参数更新,随着模型的迭代逐渐改变
④最后使用激活函数
Ai=g(bni)(6)
这个过程中,我们既保证了每一层的激活值的数据分布是一个正态分布,体现出来的数据形状类似上图的图②,表现为一个规则的园坑,又能使得每一层不至于在normalization之后损失了太多本该被学习到的知识
总而言之
BN起到了类似normalization的作用,对数据的分布发生了改变,使得损失函数的取值分布接近于圆坑,就像上面的图②,从而可以使用更大的学习率,加快了网络的收敛。
基于这样的好处,我基本上在做任何深度学习的模型的时候都加上BN处理,这样会使我的调参变得很任性,学习率设置的比较大也不怕。
使用Batch Normalization,可以获得如下好处,
- 可以使用更大的学习率,训练过程更加稳定,极大提高了训练速度。
- 可以将bias置为0,因为Batch Normalization的Standardization过程会移除直流分量,所以不再需要bias。
- 对权重初始化不再敏感,通常权重采样自0均值某方差的高斯分布,以往对高斯分布的方差设置十分重要,有了Batch Normalization后,对与同一个输出节点相连的权重进行放缩,其标准差σ也会放缩同样的倍数,相除抵消。
- 对权重的尺度不再敏感,理由同上,尺度统一由γ参数控制,在训练中决定。
- 深层网络可以使用sigmoid和tanh了,理由同上,BN抑制了梯度消失。
- Batch Normalization具有某种正则作用,不需要太依赖dropout,减少过拟合。
梯度消失 梯度爆炸 CEC机制
https://www.jianshu.com/p/3f35e555d5ba
https://zhuanlan.zhihu.com/p/25631496
https://zhuanlan.zhihu.com/p/51490163
图所示的含有3个隐藏层的神经网络,梯度消失问题发生时,接近于输出层的hidden layer 3等的权值更新相对正常,但前面的hidden layer 1的权值更新会变得很慢,导致前面的层权值几乎不变,仍接近于初始化的权值,这就导致hidden layer 1相当于只是一个映射层,对所有的输入做了一个同一映射,这是此深层网络的学习就等价于只有后几层的浅层网络的学习了
如果使用sigmoid函数 取值与求导后分别如下
解决方法:
- 梯度爆炸:
如果模型参数不是(-1,1)之间的数,比如是50,对w1求导时,就会出现很多大的数的累乘,更新参数会出现问题,无法完成网络学习
解决方法:合理的初始化模型参数
- 梯度消失:
- 使用Relu leak-relu elu等激活函数
Relu:思想也很简单,如果激活函数的导数为1,那么就不存在梯度消失爆炸的问题了,每层的网络都可以得到相同的更新速度。
f(x) = max(0,x)
relu的优点:
* 解决了梯度消失、爆炸的问题
*计算方便,计算速度快
*加速了网络的训练
relu的缺点:
*由于负数部分恒为0,会导致一些神经元无法激活(可通过设置小学习率部分解决)
*输出不是以0为中心的
尽管relu也有缺点,但是仍然是目前使用最多的激活函数。
leaky relu,f(x) = max(α*z,z),α=0.01,解决了0区间带来的影响。
elu激活函数也是为了解决relu的0区间带来的影响,其数学表达为:
f(x) = x, (x>0)
f(x) = a(e^x - 1), (otherwise)
- 预训练
此方法来自Hinton在2006年发表的一篇论文,Hinton为了解决梯度的问题,提出采取无监督逐层训练方法,其基本思想是每次训练一层隐节点,训练时将上一层隐节点的输出作为输入,而本层隐节点的输出作为下一层隐节点的输入,此过程是逐层“预训练”(pre-training);在预训练完成后,再对整个网络进行“微调”(fine-tunning)。Hinton在训练深度信念网络(Deep Belief Networks中,使用了这个方法,在各层预训练完成后,再利用BP算法对整个网络进行训练。此思想相当于是先寻找局部最优,然后整合起来寻找全局最优,此方法有一定的好处,但是目前应用的不是很多了。
- batch normalize
通过规范化操作将输出信号x规范化到均值为0,方差为1保证网络的稳定性,消除了w带来的放大缩小的影响,进而解决梯度消失和爆炸的问题。
- 残差网络
- LSTM
- 梯度剪切
其思想是设置一个梯度剪切阈值,然后更新梯度的时候,如果梯度超过这个阈值,那么就将其强制限制在这个范围之内。这可以防止梯度爆炸。
另外一种解决梯度爆炸的手段是采用权重正则化(weithts regularization)
训练 验证 测试集
留出法 留一法 k折交叉验证
留出法(Holdout cross validation)
上文提到的,按照固定比例将数据集静态的划分为训练集、验证集、测试集。的方式就是留出法。
留一法(Leave one out cross validation)
每次的测试集都只有一个样本,要进行 m 次训练和预测。 这个方法用于训练的数据只比整体数据集少了一个样本,因此最接近原始样本的分布。但是训练复杂度增加了,因为模型的数量与原始数据样本数量相同。 一般在数据缺乏时使用。
k 折交叉验证(k-fold cross validation)
静态的「留出法」对数据的划分方式比较敏感,有可能不同的划分方式得到了不同的模型。「k 折交叉验证」是一种动态验证的方式,这种方式可以降低数据划分带来的影响。具体步骤如下:
- 将数据集分为训练集和测试集,将测试集放在一边
- 将训练集分为 k 份
- 每次使用 k 份中的 1 份作为验证集,其他全部作为训练集。
- 通过 k 次训练后,我们得到了 k 个不同的模型。
- 评估 k 个模型的效果,从中挑选效果最好的超参数
- 使用最优的超参数,然后将 k 份数据全部作为训练集重新训练模型,得到最终模型。
https://easyai.tech/ai-definition/3dataset-and-cross-validation/
2. NLP
各种词向量种类及特点:
种类
- 基于one-hot、tf-idf、textrank等的bag-of-words;
- 主题模型:LSA(SVD)、pLSA、LDA;
- 基于词向量的固定表征:word2vec、fastText、glove
- 基于词向量的动态表征:elmo、GPT、bert
特点
- 矩阵分解(LSA):利用全局语料特征,但SVD求解计算复杂度大;
- 矩阵分解(LSA):利用全局语料特征,但SVD求解计算复杂度大;
- 基于NNLM/RNNLM的词向量:词向量为副产物,存在效率不高等问题;
- word2vec、fastText:优化效率高,但是基于局部语料;
- glove:基于全局预料,结合了LSA和word2vec的优点;
- elmo、GPT、bert:动态特征;
2.1 W2V Glove FastText
word2vec和NNLM对比有什么区别?(word2vec vs NNLM)
1)其本质都可以看作是语言模型;
2)词向量只不过NNLM一个产物,word2vec虽然其本质也是语言模型,但是其专注于词向量本身,因此做了许多优化来提高计算效率:
- 与NNLM相比,词向量直接sum,不再拼接,并舍弃隐层;
- 考虑到sofmax归一化需要遍历整个词汇表,采用hierarchical softmax 和negative sampling进行优化,hierarchical softmax 实质上生成一颗带权路径最小的哈夫曼树,让高频词搜索路劲变小;negative sampling更为直接,实质上对每一个样本中每一个词都进行负例采样;
word2vec 两种训练方式哪种更好?
对生僻词谁更好?
CBOW模型中input是context(周围词)而output是中心词,训练过程中其实是在从output的loss学习周围词的信息也就是embedding,但是在中间层是average的,一共预测V(vocab size)次就够了。
skipgram是用中心词预测周围词,预测的时候是一对word pair,等于对每一个中心词都有K个词作为output,对于一个词的预测有K次,所以能够更有效的从context中学习信息,但是总共预测K*V词。
skipgram胜出
word2vec霍夫曼树 Hierarchical Softmax
https://blog.csdn.net/zynash2/article/details/81636338
https://zhuanlan.zhihu.com/p/52517050
哈夫曼树(Huffman Tree)又称为带权路径长度最短二叉树,或最优二叉树。如A:15,B:10,C:3,D:5,下图所示为哈夫曼树:带权路径长度WPL=3*3 5*3 10*2 15*1=59
在CBOW中,输出层为一棵根据词频构造的哈夫曼树。其实在word2vec之前,即有类似的三层神经网络结构做词向量模型,一点很大的不同是,之前的方法输出层是一个softmax层,从隐藏层到输出层即需要计算所有词的softmax概率,计算量很大,而输出层为哈夫曼树则避免了计算所有词的softmax概率。所以从隐藏层到输出层的映射是按树形结构一步步走的。使用哈夫曼树的好处在于,即降低了计算量,而且由于按照词频构造的哈夫曼树,高频词可以较短时间内找到。
负采样
https://cloud.tencent.com/developer/article/1780054
基于Hierarchical Softmax的CBOW模型有一个明显的缺点:由于哈夫曼树是按照词频构造的,所以当w为出现次数很少的生僻词时,则需要搜寻很深才能到达w所在的节点。Negative Sampling的方法并没有使用哈夫曼树,通过采样的方法,提高了模型训练的效率。
训练一个网络是,计算训练样本然后轻微调整所有的神经元权重来提高准确率。换句话说,每一个训练样本都需要更新所有神经网络的权重。
就像如上所说,当词汇表特别大的时候,如此多的神经网络参数在如此大的数据量下,每次都要进行权重更新,负担很大。
在每个样本训练时,只修改部分的网络参数,负采样是通过这种方式来解决这个问题的。
当我们的神经网络训练到单词组(‘fox’, ‘quick’)时候,得到的输出或label都是一个one-hot向量,也就是说,在表示’quick’的位置数值为1,其它全为0。
负采样是随机选择较小数量的’负(Negative)’单词(比如5个),来做参数更新。这里的’负’表示的是网络输出向量种位置为0表示的单词。当然,’正(Positive)’(即正确单词’quick’)权重也会更新。
论文中表述,小数量级上采用5-20,大数据集使用2-5个单词。
我们的模型权重矩阵为300x10000,更新的单词为5个’负’词和一个’正’词,共计1800个参数,这是输出层全部3M参数的0.06%
负采样的选取是和频次相关的,频次越高,负采样的概率越大:
论文选择0.75作为指数是因为实验效果好。C语言实现的代码很有意思:首先用索引值填充多次填充词汇表中的每个单词,单词索引出现的次数为P(wi)∗table_size。然后负采样只需要生成一个1到100M的整数,并用于索引表中数据。由于概率高的单词在表中出现的次数多,很可能会选择这些词。
子采样
在以上例子中,可以看到频繁单词’the’的两个问题:
- 对于单词对(‘fox’,’the’),其对单词’fox’的语义表达并没有什么有效帮助,’the’在每个单词的上下文中出现都非常频繁。
- 预料中有很多单词对(‘the’,…),我们应更好的学习单词’the’
Word2vec使用子采样技术来解决以上问题,根据单词的频次来削减该单词的采样率。以window size为10为例子,我们删除’the’:
- 当我们训练其余单词时候,’the’不会出现在他们的上下文中。
- 当中心词为’the’时,训练样本数量少于10。
采样率
P(wi)=1.0(100%保留),对应的 z(wi)<=0.0026。(表示词频大于0.0026的单词才会进行子采样)
P(wi)=0.5(50%保留),对应的 z(wi)=0.00746。
P(wi)=0.033(3.3%保留),对应的 z(wi)=1.0。(不可能)
TextCNN 文本分类
https://blog.csdn.net/asialee_bird/article/details/88813385
(1)嵌入层(Embedding Layer)
通过一个隐藏层, 将 one-hot 编码的词投影到一个低维空间中,本质上是特征提取器,在指定维度中编码语义特征。 这样, 语义相近的词, 它们的欧氏距离或余弦距离也比较近。(作者使用的单词向量是预训练的,方法为fasttext得到的单词向量,当然也可以使用word2vec和GloVe方法训练得到的单词向量)。
(2)卷积层(Convolution Laye)
在处理图像数据时,CNN使用的卷积核的宽度和高度的一样的,但是在text-CNN中,卷积核的宽度是与词向量的维度一致!这是因为我们输入的每一行向量代表一个词,在抽取特征的过程中,词做为文本的最小粒度。而高度和CNN一样,可以自行设置(通常取值2,3,4,5),高度就类似于n-gram了。由于我们的输入是一个句子,句子中相邻的词之间关联性很高,因此,当我们用卷积核进行卷积时,不仅考虑了词义而且考虑了词序及其上下文(类似于skip-gram和CBOW模型的思想)。
(3)池化层(Pooling Layer)
因为在卷积层过程中我们使用了不同高度的卷积核,使得我们通过卷积层后得到的向量维度会不一致,所以在池化层中,我们使用1-Max-pooling对每个特征向量池化成一个值,即抽取每个特征向量的最大值表示该特征,而且认为这个最大值表示的是最重要的特征。当我们对所有特征向量进行1-Max-Pooling之后,还需要将每个值给拼接起来。得到池化层最终的特征向量。在池化层到全连接层之前可以加上dropout防止过拟合。
(4)全连接层(Fully connected layer)
全连接层跟其他模型一样,假设有两层全连接层,第一层可以加上’relu’作为激活函数,第二层则使用softmax激活函数得到属于每个类的概率。
使用预训练的word2vec 、 GloVe初始化效果会更好。一般不直接使用One-hot。
卷积核的大小影响较大,一般取1~10,对于句子较长的文本,则应选择大一些。
卷积核的数量也有较大的影响,一般取100~600 ,同时一般使用Dropout(0~0.5)。
激活函数一般选用ReLU 和 tanh。
池化使用1-max pooling。
随着feature map数量增加,性能减少时,试着尝试大于0.5的Dropout。
评估模型性能时,使用交叉验证。
glove和word2vec、 LSA对比有什么区别?(word2vec vs glove vs LSA)
1)glove vs LSA
- LSA(Latent Semantic Analysis)可以基于co-occurance matrix构建词向量,实质上是基于全局语料采用SVD进行矩阵分解,然而SVD计算复杂度高;
- glove可看作是对LSA一种优化的高效矩阵分解算法,采用Adagrad对最小平方损失进行优化;
2)word2vec vs glove
- word2vec是局部语料库训练的,其特征提取是基于滑窗的;而glove的滑窗是为了构建co-occurance matrix,是基于全局语料的,可见glove需要事先统计共现概率;因此,word2vec可以进行在线学习,glove则需要统计固定语料信息。
- )log(X_{ij})
- word2vec损失函数实质上是带权重的交叉熵,权重固定;glove的损失函数是最小平方损失函数,权重可以做映射变换。
- 总体来看,glove可以被看作是更换了目标函数和权重函数的全局word2vec。
2.2 Transformer
https://cloud.tencent.com/developer/article/1868051
2.3 BERT
https://cloud.tencent.com/developer/article/1865094
https://cloud.tencent.com/developer/article/1855316 BERT 文本分类
bert的全称是Bidirectional Encoder Representation from Transformers,bert的核心是双向Transformer Encoder,提出以下问题并进行解答:
自回归与自编码模型
主流语言模型可分为 自回归(Autoregressive) 和 自编码 (AutoEncoder) 模型,其区别在于自回归模型只利用上文或下文预测一个词的概率(如 GPT, ELMo),而自编码模型可以同时结合上下文(如BERT)。
为什么bert采取的是双向Transformer Encoder,而不叫decoder?
BERT Transformer 使用双向self-attention,而GPT Transformer 使用受限制的self-attention,其中每个token只能处理其左侧的上下文。双向 Transformer 通常被称为“Transformer encoder”,而左侧上下文被称为“Transformer decoder”,decoder是不能获要预测的信息的。
elmo、GPT和bert在单双向语言模型处理上的不同之处?
在上述3个模型中,只有bert共同依赖于左右上下文。那elmo不是双向吗?实际上elmo使用的是经过独立训练的从左到右和从右到左LSTM的串联拼接起来的。而GPT使用从左到右的Transformer,实际就是“Transformer decoder”。
bert构建双向语言模型不是很简单吗?不也可以直接像elmo拼接Transformer decoder吗?
BERT 的作者认为,这种拼接式的bi-directional 仍然不能完整地理解整个语句的语义。更好的办法是用上下文全向来预测mask,也就是用 “能/实现/语言/表征/../的/模型”,来预测mask。BERT 作者把上下文全向的预测方法,称之为 deep bi-directional。
bert为什么要采取Marked LM,而不直接应用Transformer Encoder?
我们知道向Transformer这样深度越深,学习效果会越好。可是为什么不直接应用双向模型呢?因为随着网络深度增加会导致标签泄露。如下图:
双向编码与网络深度的冲突
深度双向模型比left-to-right 模型或left-to-right and right-to-left模型的浅层连接更强大。遗憾的是,标准条件语言模型只能从左到右或从右到左进行训练,因为双向条件作用将允许每个单词在多层上下文中间接地“see itself”。
为了训练一个深度双向表示(deep bidirectional representation),研究团队采用了一种简单的方法,即随机屏蔽(masking)部分输入token,然后只预测那些被屏蔽的token。论文将这个过程称为“masked LM”(MLM)。
bert为什么并不总是用实际的MASK token替换被“masked”的词汇?
NLP必读 | 十分钟读懂谷歌BERT模型: 虽然这确实能让团队获得双向预训练模型,但这种方法有两个缺点。首先,预训练和finetuning之间不匹配,因为在finetuning期间从未看到MASKtoken。为了解决这个问题,团队并不总是用实际的MASKtoken替换被“masked”的词汇。相反,训练数据生成器随机选择15%的token。例如在这个句子“my dog is hairy”中,它选择的token是“hairy”。然后,执行以下过程: 数据生成器将执行以下操作,而不是始终用MASK替换所选单词: 80%的时间:用MASK标记替换单词,例如,my dog is hairy → my dog is MASK 10%的时间:用一个随机的单词替换该单词,例如,my dog is hairy → my dog is apple 10%的时间:保持单词不变,例如,my dog is hairy → my dog is hairy. 这样做的目的是将表示偏向于实际观察到的单词。 Transformer encoder不知道它将被要求预测哪些单词或哪些单词已被随机单词替换,因此它被迫保持每个输入token的分布式上下文表示。此外,因为随机替换只发生在所有token的1.5%(即15%的10%),这似乎不会损害模型的语言理解能力。 使用MLM的第二个缺点是每个batch只预测了15%的token,这表明模型可能需要更多的预训练步骤才能收敛。团队证明MLM的收敛速度略慢于 left-to-right的模型(预测每个token),但MLM模型在实验上获得的提升远远超过增加的训练成本。
bert模型的主要创新点都在pre-train方法上,即用了Masked LM和Next Sentence Prediction两种方法分别捕捉词语和句子级别的representation。
下面给出了Transformer Encoder模型的整体结构:
Transformer Encoder
multi-head attention
tokenize
https://cloud.tencent.com/developer/article/1865689
不考虑多头的原因,self-attention中词向量不乘QKV参数矩阵,会有什么问题?
Self-Attention的核心是用文本中的其它词来增强目标词的语义表示,从而更好的利用上下文的信息。
self-attention中,sequence中的每个词都会和sequence中的每个词做点积去计算相似度,也包括这个词本身。
对于 self-attention,一般会说它的 q=k=v,这里的相等实际上是指它们来自同一个基础向量,而在实际计算时,它们是不一样的,因为这三者都是乘了QKV参数矩阵的。那如果不乘,每个词对应的q,k,v就是完全一样的。
在相同量级的情况下,qi与ki点积的值会是最大的(可以从“两数和相同的情况下,两数相等对应的积最大”类比过来)。
那在softmax后的加权平均中,该词本身所占的比重将会是最大的,使得其他词的比重很少,无法有效利用上下文信息来增强当前词的语义表示。
而乘以QKV参数矩阵,会使得每个词的q,k,v都不一样,能很大程度上减轻上述的影响。
当然,QKV参数矩阵也使得多头,类似于CNN中的多核,去捕捉更丰富的特征/信息成为可能。
为什么BERT选择mask掉15%这个比例的词,可以是其他的比例吗?
BERT采用的Masked LM,会选取语料中所有词的15%进行随机mask,论文中表示是受到完形填空任务的启发,但其实与CBOW也有异曲同工之妙。
从CBOW的角度,这里
有一个比较好的解释是:在一个大小为
的窗口中随机选一个词,类似CBOW中滑动窗口的中心词,区别是这里的滑动窗口是非重叠的。
那从CBOW的滑动窗口角度,10%~20%都是还ok的比例。
上述非官方解释,是来自我的一位朋友提供的一个理解切入的角度,供参考。
使用BERT预训练模型为什么最多只能输入512个词,最多只能两个句子合成一句?
这是Google BERT预训练模型初始设置的原因,前者对应Position Embeddings,后者对应Segment Embeddings
在BERT中,Token,Position,Segment Embeddings 都是通过学习来得到的,pytorch代码中它们是这样的
代码语言:javascript复制self.word_embeddings = Embedding(config.vocab_size, config.hidden_size)
self.position_embeddings = Embedding(config.max_position_embeddings, config.hidden_size)
self.token_type_embeddings = Embedding(config.type_vocab_size, config.hidden_size)
上述BERT pytorch代码来自:https://github.com/xieyufei1993/Bert-Pytorch-Chinese-TextClassification,结构层次非常清晰。
而在BERT config中
代码语言:javascript复制"max_position_embeddings": 512
"type_vocab_size": 2
因此,在直接使用Google 的BERT预训练模型时,输入最多512个词(还要除掉[CLS]和[SEP]),最多两个句子合成一句。这之外的词和句子会没有对应的embedding。
当然,如果有足够的硬件资源自己重新训练BERT,可以更改 BERT config,设置更大max_position_embeddings 和 type_vocab_size值去满足自己的需求。
为什么BERT在第一句前会加一个[CLS]标志?
BERT在第一句前会加一个[CLS]标志,最后一层该位对应向量可以作为整句话的语义表示,从而用于下游的分类任务等。
为什么选它呢,因为与文本中已有的其它词相比,这个无明显语义信息的符号会更“公平”地融合文本中各个词的语义信息,从而更好的表示整句话的语义。
具体来说,self-attention是用文本中的其它词来增强目标词的语义表示,但是目标词本身的语义还是会占主要部分的,因此,经过BERT的12层,每次词的embedding融合了所有词的信息,可以去更好的表示自己的语义。
而[CLS]位本身没有语义,经过12层,得到的是attention后所有词的加权平均,相比其他正常词,可以更好的表征句子语义。
当然,也可以通过对最后一层所有词的embedding做pooling去表征句子语义。
这里补充一下bert的输出,有两种,在BERT TF源码中对应:
一种是get_pooled_out(),就是上述[CLS]的表示,输出shape是[batch size,hidden size]。
一种是get_sequence_out(),获取的是整个句子每一个token的向量表示,输出shape是[batch_size, seq_length, hidden_size],这里也包括[CLS],因此在做token级别的任务时要注意它。
Self-Attention 的时间复杂度是怎么计算的?
Self-Attention时间复杂度:
,这里,n是序列的长度,d是embedding的维度。
Self-Attention包括三个步骤:相似度计算,softmax和加权平均,它们分别的时间复杂度是:
相似度计算可以看作大小为(n,d)和(d,n)的两个矩阵相乘:
,得到一个(n,n)的矩阵
softmax就是直接计算了,时间复杂度为
加权平均可以看作大小为(n,n)和(n,d)的两个矩阵相乘:
,得到一个(n,d)的矩阵
因此,Self-Attention的时间复杂度是
。
这里再分析一下Multi-Head Attention,它的作用类似于CNN中的多核。
多头的实现不是循环的计算每个头,而是通过 transposes and reshapes,用矩阵乘法来完成的。
In practice, the multi-headed attention are done with transposes and reshapes rather than actual separate tensors. —— 来自 google BERT 源码
Transformer/BERT中把 d ,也就是hidden_size/embedding_size这个维度做了reshape拆分,可以去看Google的TF源码或者上面的pytorch源码:
hidden_size (d) = num_attention_heads (m) * attention_head_size (a),也即 d=m*a
并将 num_attention_heads 维度transpose到前面,使得Q和K的维度都是(m,n,a),这里不考虑batch维度。
这样点积可以看作大小为(m,n,a)和(m,a,n)的两个张量相乘,得到一个(m,n,n)的矩阵,其实就相当于(n,a)和(a,n)的两个矩阵相乘,做了m次,时间复杂度(感谢评论区指出)是
。
张量乘法时间复杂度分析参见:矩阵、张量乘法的时间复杂度分析
因此Multi-Head Attention时间复杂度也是
,复杂度相较单头并没有变化,主要还是transposes and reshapes 的操作,相当于把一个大矩阵相乘变成了多个小矩阵的相乘。
Transformer在哪里做了权重共享,为什么可以做权重共享?
Transformer在两个地方进行了权重共享:
(1)Encoder和Decoder间的Embedding层权重共享;
(2)Decoder中Embedding层和FC层权重共享。
对于(1),《Attention is all you need》中Transformer被应用在机器翻译任务中,源语言和目标语言是不一样的,但它们可以共用一张大词表,对于两种语言中共同出现的词(比如:数字,标点等等)可以得到更好的表示,而且对于Encoder和Decoder,嵌入时都只有对应语言的embedding会被激活,因此是可以共用一张词表做权重共享的。
论文中,Transformer词表用了bpe来处理,所以最小的单元是subword。英语和德语同属日耳曼语族,有很多相同的subword,可以共享类似的语义。而像中英这样相差较大的语系,语义共享作用可能不会很大。
但是,共用词表会使得词表数量增大,增加softmax的计算时间,因此实际使用中是否共享可能要根据情况权衡。
该点参考:https://www.zhihu.com/question/333419099/answer/743341017
对于(2),Embedding层可以说是通过onehot去取到对应的embedding向量,FC层可以说是相反的,通过向量(定义为 x)去得到它可能是某个词的softmax概率,取概率最大(贪婪情况下)的作为预测值。
那哪一个会是概率最大的呢?在FC层的每一行量级相同的前提下,理论上和 x 相同的那一行对应的点积和softmax概率会是最大的(可类比本文问题1)。
因此,Embedding层和FC层权重共享,Embedding层中和向量 x 最接近的那一行对应的词,会获得更大的预测概率。实际上,Decoder中的Embedding层和FC层有点像互为逆过程。
通过这样的权重共享可以减少参数的数量,加快收敛。
但开始我有一个困惑是:Embedding层参数维度是:(v,d),FC层参数维度是:(d,v),可以直接共享嘛,还是要转置?其中v是词表大小,d是embedding维度。
查看 pytorch 源码发现真的可以直接共享:
代码语言:javascript复制fc = nn.Linear(d, v, bias=False) # Decoder FC层定义
weight = Parameter(torch.Tensor(out_features, in_features)) # Linear层权重定义
Linear 层的权重定义中,是按照 (out_features, in_features) 顺序来的,实际计算会先将 weight 转置在乘以输入矩阵。所以 FC层 对应的 Linear 权重维度也是 (v,d),可以直接共享。
BERT非线性的来源在哪里?
前馈层的gelu激活函数和self-attention,self-attention是非线性的,感谢评论区指出。
BERT的三个Embedding直接相加会对语义有影响吗?
这是一个非常有意思的问题,苏剑林老师也给出了回答,真的很妙啊:
Embedding的数学本质,就是以one hot为输入的单层全连接。 也就是说,世界上本没什么Embedding,有的只是one hot。
在这里想用一个例子再尝试解释一下:
假设 token Embedding 矩阵维度是 [4,768];position Embedding 矩阵维度是 [3,768];segment Embedding 矩阵维度是 [2,768]。
对于一个字,假设它的 token one-hot 是[1,0,0,0];它的 position one-hot 是[1,0,0];它的 segment one-hot 是[1,0]。
那这个字最后的 word Embedding,就是上面三种 Embedding 的加和。
如此得到的 word Embedding,和concat后的特征:[1,0,0,0,1,0,0,1,0],再过维度为 [4 3 2,768] = [9, 768] 的全连接层,得到的向量其实就是一样的。
再换一个角度理解:
直接将三个one-hot 特征 concat 起来得到的 [1,0,0,0,1,0,0,1,0] 不再是one-hot了,但可以把它映射到三个one-hot 组成的特征空间,空间维度是 4*3*2=24 ,那在新的特征空间,这个字的one-hot就是[1,0,0,0,0...] (23个0)。
此时,Embedding 矩阵维度就是 [24,768],最后得到的 word Embedding 依然是和上面的等效,但是三个小Embedding 矩阵的大小会远小于新特征空间对应的Embedding 矩阵大小。
当然,在相同初始化方法前提下,两种方式得到的 word Embedding 可能方差会有差别,但是,BERT还有Layer Norm,会把 Embedding 结果统一到相同的分布。
BERT的三个Embedding相加,本质可以看作一个特征的融合,强大如 BERT 应该可以学到融合后特征的语义信息的。
参考:https://www.zhihu.com/question/374835153
下面两个问题也非常好,值得重点关注,但网上已经有很好的解答了,如下:
Transformer的点积模型做缩放的原因是什么?
参考:https://www.zhihu.com/question/339723385
在BERT应用中,如何解决长文本问题?
参考:https://www.zhihu.com/question/3274
2.4 NLU任务
https://easyai.tech/ai-definition/nlu/
https://zhuanlan.zhihu.com/p/143221527
2.5 NLG任务
https://zhuanlan.zhihu.com/p/375142707
3. leetcode
逆序数对问题
设A1..n是一个包含n个不同数的数组。如果在i < j的情况下,有Ai > Aj,则(i, j)就称为A中的一个逆序对(inversion)。给出一个算法,它能用O(n log n)的最坏运行时间,确定n个元素的任何排列中逆序对的数目。‘
归并排序
链表翻转
https://cloud.tencent.com/developer/article/1835266
迭代 递归
求集合所有子集
深度优先算法 BFS
蓄水池抽样算法
https://www.jianshu.com/p/7a9ea6ece2af
给定一个数据流,数据流长度N很大,且N直到处理完所有数据之前都不可知,请问如何在只遍历一遍数据(O(N))的情况下,能够随机选取出m个不重复的数据。
算法思路大致如下:
- 如果接收的数据量小于m,则依次放入蓄水池。
- 当接收到第i个数据时,i >= m,在0, i范围内取以随机数d,若d的落在0, m-1范围内,则用接收到的第i个数据替换蓄水池中的第d个数据。
- 重复步骤2。
算法的精妙之处在于:当处理完所有的数据时,蓄水池中的每个数据都是以m/N的概率获得的。
分布式蓄水池
如果遇到超大的数据量,即使是O(N)的时间复杂度,蓄水池抽样程序完成抽样任务也将耗时很久。因此分布式的蓄水池抽样算法应运而生。运作原理如下:
- 假设有K台机器,将大数据集分成K个数据流,每台机器使用单机版蓄水池抽样处理一个数据流,抽样m个数据,并最后记录处理的数据量为N1, N2, ..., Nk, ..., NK(假设m<Nk)。N1 N2 ... NK=N。
- 取1, N一个随机数d,若d<N1,则在第一台机器的蓄水池中等概率不放回地(1/m)选取一个数据;若N1<=d<(N1 N2),则在第二台机器的蓄水池中等概率不放回地选取一个数据;一次类推,重复m次,则最终从N大数据集中选出m个数据。
m/N的概率验证如下:
第k台机器中的蓄水池数据被选取的概率为m/Nk。
从第k台机器的蓄水池中选取一个数据放进最终蓄水池的概率为Nk/N。
第k台机器蓄水池的一个数据被选中的概率为1/m。(不放回选取时等概率的)
重复m次选取,则每个数据被选中的概率为m*(m/Nk*Nk/N*1/m)=m/N。
寻找最近回文数
https://github.com/Shellbye/Shellbye.github.io/issues/71
最长回文子串
https://cloud.tencent.com/developer/article/1835232
Word Break
https://cloud.tencent.com/developer/article/1835271
生成括号
给定n对括号,写一个函数来生成成对的括号的所有组合。
For example, given n = 3, a solution set is: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”
如果左括号还有剩余,则可以放置左括号,如果右括号的剩余数大于左括号,则可以放置右括号。
https://cloud.tencent.com/developer/article/1835234
coin change
https://cloud.tencent.com/developer/article/1835233
dsj = 1
di = di-sj 1 (di-sj != 0 )
-> dpx c = min(dpx 1, dpx c)
4. 大数据
4.1 大数据量文本去重
https://www.jianshu.com/p/21d743ddc397
使用spark的分区排序去重算子去重方法的优点
a、在于sortWithinPartitions方法返回的是按Partition排好序的DataFrame对象。
我们只需在Partition排好序的DataFrame对象后采用dropDuplicates删除相同的列,返回一个DataFrame,得到最新时间的数据。
b、这种去重方式大幅度提升了海量数据去重性能,减少了过程中shuffle操作。
5. Ref
5.1 面经
- https://github.com/amusi/Deep-Learning-Interview-Book
- https://nowcoder.net/discuss/693666?channel=-1&source_id=discuss_terminal_discuss_sim_nctrack&ncTraceId=33c4da6bfe26440ba4a999b368dd71bd.163.16281287115543777
- https://www.nowcoder.com/discuss/587631?from=gitnowcoder2021
4.2 参考
https://zhuanlan.zhihu.com/p/115014536 预训练模型综述