Part1 基本数学概念
1. 极大似然估计(MLE),最大后验概率(MAP),最小二乘法,EM
先验概率:根据以往经验分析和得到的概率,不用做实验就知道的概率
后验概率:后验概率是在考虑了一个事实之后的条件概率
极大似然和最大后验
MLE
求参数θ,使得P(X|θ)最大
知道分布的具体情况,但是不知道具体的参数,比如说知道了使正态分布,但是不知道μ和σ
求解
argmaxμp(X,μ)argmax_{\mu}p(X,\mu) argmaxμp(X,μ)
其中p(X,μ)就是似然函数,表征在参数μ下出现观测数据的概率,假设每次观测时独立的
p(x1,x2,...,xn;μ)=∏p(xi;μ)p(x_1,x_2,...,x_n;\mu)=\prod p(x_i;\mu) p(x1,x2,...,xn;μ)=∏p(xi;μ)
即求解
argmaxμlog(p(X,μ))=argmaxμ∑logp(xi;μ)argmax_{\mu}\log(p(X,\mu))=argmax_\mu \sum\log p(x_i;\mu) argmaxμlog(p(X,μ))=argmaxμ∑logp(xi;μ)
前提假设:
训练样本的分布能代表样本的真实分布。每个样本集中的样本都是所谓独立同分布的随机变量 (iid条件),且有充分的训练样本
MAP
求参数θ,使得P(X|θ)*P(θ)最大
由于:
P(θ∣X)=P(X∣θ)P(θ)P(X)P(\theta|X)=\frac{P(X|\theta)P(\theta)}{P(X)} P(θ∣X)=P(X)P(X∣θ)P(θ)
由于P(X)P(X)P(X)为常数,则MAP即求θθθ,使得P(θ∣X)P(θ|X)P(θ∣X)最大,MLE和MAP的区别:MLE是把先验概率P(θ)P(θ)P(θ)认为等于1,即认为θ是均匀分布
最小二乘法
最小二乘法是找到一个(组)估计值,使得实际值与估计值的距离最小
基本假设
解释变量是确定变量,不是随机变量随机误差项具有零均值,同方差,服从正态分布随机误差项与解释变量之间不相关
EM
EM老是跟MLE放在一起,我们来判别一下MLE和EM的不同
MLE:已知数据分布模型,采样的数据,但是不知道模型的具体参数,根据采样数据反推使得采样数据概率最大的模型的参数
EM:相当于是MLE又进阶了一层,已知各个类别的分布模型,以及采样的数据,不知道采样的数据究竟来自于哪个类别,以及每个类别模型的参数
在这个例子里面,本身数据来自于哪个类别这个应该是我们已知的,但实际情况我们并不知道,所以把数据来自于哪个类别成为隐变量ZZZ,则我们就要求解argmaxP(θ∣X,Z)argmaxP(\theta|X,Z)argmaxP(θ∣X,Z).
E步:
给定初始超参数Θt\Theta^tΘt,计算Q=P(Z∣X;Θt)Q=P(Z|X;\Theta^t)Q=P(Z∣X;Θt)
M步:
根据Q,计算使似然函数最大的Θt+1\Theta^{t+1}Θt+1
推导:
在未知子模型的分布αk\alpha_kαk时,其自变量分布如下P(x;θ)=∑i=1kαkϕ(x;θk)P(x ; \theta)=\sum_{i=1}^{k} \alpha_{k} \phi\left(x ; \theta_{k}\right)P(x;θ)=∑i=1kαkϕ(x;θk)
似然函数:
l(θ)=∑i=1mlogp(xi;θ)l(\theta)=\sum_{i=1}^{m} \log p\left(x_{i} ; \theta\right)l(θ)=∑i=1mlogp(xi;θ)
我们需要求得这个似然函数的一个最大值
由于我们不知道观察到的序列来自于哪个子模型,则
l(θ)=∑i=1mlogp(xi;θ)=∑i=1mlog∑ZQ(z)p(xi∣z;θ)l(\theta)=\sum_{i=1}^{m} \log p\left(x_{i} ; \theta\right)=\sum_{i=1}^{m}\log \sum_{Z}Q(z)p(x_i|z;\theta) l(θ)=i=1∑mlogp(xi;θ)=i=1∑mlogZ∑Q(z)p(xi∣z;θ)
其中,mmm:样本数量;Q(z)Q(z)Q(z):子模型的概率分布
由于∑ZQ(z)=1\sum_{Z}Q(z)=1∑ZQ(z)=1,则上式有
l(θ)=∑i=1mlog∑ZQ(z)p(xi,z;θ)Q(z)≥∑i=1m∑ZQ(z)logp(xi,z;θ)Q(z)l(\theta)=\sum_{i=1}^{m}\log \sum_{Z}Q(z)\frac{p(x_i,z;\theta)}{Q(z)}\ge\sum_{i=1}^{m} \sum_{Z} Q\left(z\right) \log \frac{p(x_i,z;\theta)}{Q\left(z\right)} l(θ)=i=1∑mlogZ∑Q(z)Q(z)p(xi,z;θ)≥i=1∑mZ∑Q(z)logQ(z)p(xi,z;θ)
上述第二条用了Jensen不等式,因为log是凹函数
考虑不等式取得等号的条件p(xi,z;θ)Q(z)=c\frac{p(x_i,z;\theta)}{Q(z)}=cQ(z)p(xi,z;θ)=c,同时考虑∑ZQ(z)=1\sum_{Z}Q(z)=1∑ZQ(z)=1,则有
Q(z)=p(xi,z;θ)∑zp(xi,z;θ)=p(xi,z;θ)p(xi;θ)=p(z∣xi;θ)Q(z)=\frac{p(x_i,z;\theta)}{\sum_zp(x_i,z;\theta)}=\frac{p(x_i,z;\theta)}{p(x_i;\theta)}=p(z|x_i;\theta) Q(z)=∑zp(xi,z;θ)p(xi,z;θ)=p(xi;θ)p(xi,z;θ)=p(z∣xi;θ)
则有EM算法,初始化θ\thetaθ,E步:根据θ\thetaθ求出Q(z)Q(z)Q(z),即第xix_ixi个数据来自ziz_izi的概率;M步:根据所求出的Q,最大化第二步得到的l(θ)l(\theta)l(θ),利用MLE求出新的θ\thetaθ
2. 优化方法汇总(GD家族,一阶导数)
优化方法总结
简单说明几个特点:
SGD
Θt+1,i=Θt,i−αgt,i\Theta_{t+1,i}=\Theta_{t,i}-\alpha g_{t,i} Θt+1,i=Θt,i−αgt,i
Θt,i:t轮学习中参数θi的取值\Theta_{t,i}:t轮学习中参数\theta_i的取值 Θt,i:t轮学习中参数θi的取值
BGD:下降速度慢,若cost function为凸函数,保证到全局最优
SGD:下降快,但是容易收敛到局部最优且困在鞍点
MBGD:取一个batch来计算
总的缺点:
选取适当的学习率α较为困难,需要再训练过程中给调整学习率的大小(预先设定迭代次数m,执行m次后减小学习率)每个参数的学习率是相同的(不合理!)对于稀疏矩阵不合理,解决方案是对于稀疏矩阵中频率较低的特征设置大学习率,高频特征设置小学习率
Momentum
vt=γvt−1+αgt,iv_t=\gamma v_{t-1}+\alpha g_{t,i} vt=γvt−1+αgt,i
Θ=Θ−vt\Theta=\Theta-v_t Θ=Θ−vt
会观察历史梯度,若当前梯度方向与历史梯度一直,增强该梯度,否则,衰减该梯度
Momentum和nestrov相当于在sgd的基础上加了一阶动量
Nesterov和Momentum的区别
momentum同时计算该点的历史速度和梯度,然后叠加,nestreov是计算该点的速度,计算前进后的梯度,将两者叠加
Nestreov
vt=γvt−1+α∇f(xt+γvt)v_t=\gamma v_{t-1}+\alpha \nabla f(x_t+\gamma v_t) vt=γvt−1+α∇f(xt+γvt)
xt+1=xt−vtx_{t+1}=x_t-v_t xt+1=xt−vt
Adagrad
Momentum中对于每个参数的训练使用了相同的学习率,Adagrad可以实现对学习率的调整
Θt+1,i=Θt,i−αGt,ii+ϵgt,i\Theta_{t+1,i}=\Theta_{t,i}-\frac{\alpha}{\sqrt{G_{t,ii}+\epsilon}}g_{t,i} Θt+1,i=Θt,i−Gt,ii+ϵαgt,i
Gt,ii=∑j=1t−1gj,i,代表θi从第1轮到第t轮的梯度平方和,ϵ为平滑项,避免分母为0G_{t,ii}=\sum_{j=1}^{t-1}g_{j,i},代表\theta_i从第1轮到第t轮的梯度平方和,\epsilon为平滑项,避免分母为0 Gt,ii=j=1∑t−1gj,i,代表θi从第1轮到第t轮的梯度平方和,ϵ为平滑项,避免分母为0
缺点:中后期分母项越来越大,导致梯度趋近于0
容易困在局部极值点
RMSprop
Θt+1,i=Θt,i−αEt+ϵgt,i\Theta_{t+1,i}=\Theta_{t,i}-\frac{\alpha}{\sqrt{E_{t}+\epsilon}}g_{t,i} Θt+1,i=Θt,i−Et+ϵαgt,i
其中:
Et=0.9Et−1+0.1gt2E_{t}=0.9E_{t-1}+0.1g_t^2Et=0.9Et−1+0.1gt2,将Adagrad中的累加变为平均值,缓解梯度下降过快问题
rmsprop和adagrad相当于在sgd的基础上加了二阶动量
Adam
不仅把学习率改了,连梯度也改了
mt=β1mt−1+(1−β1)gtm_{t}=\beta_{1} m_{t-1}+\left(1-\beta_{1}\right) g_{t} mt=β1mt−1+(1−β1)gt
vt=β2vt−1+(1−β2)gt2v_{t}=\beta_{2} v_{t-1}+\left(1-\beta_{2}\right) g_{t}^{2} vt=β2vt−1+(1−β2)gt2
m^t=mt1−β1t\hat{m}_{t}=\frac{m_{t}}{1-\beta_{1}^{t}} m^t=1−β1tmt
v^t=vt1−β2t\hat{v}_{t}=\frac{v_{t}}{1-\beta_{2}^{t}} v^t=1−β2tvt
Θt+1=Θt−αv^t+ϵm^t\Theta_{t+1}=\Theta_{t}-\frac{\alpha}{\sqrt{\hat{v}_{t}}+\epsilon} \hat{m}_{t} Θt+1=Θt−v^t+ϵαm^t
在稀疏矩阵时,常用Adagrad,RMSprop,Adam,因为可以动态调整学习率
β1\beta_1β1控制一阶动量,β2\beta_2β2控制二阶动量
Adam是二阶动量是固定时间窗口内的累积,随着时间窗口的变化,遇到的数据可能发生巨变,这样的话就会造成vtv_tvt并不是时刻减小的,在训练后期引起学习率产生震荡,导致模型无法收敛
Adam+SGD到Adabound
为什么又不用Adam了,Adam的两宗罪:
Adam罪状一:可能不收敛
其中,SGD没有用到二阶动量,因此学习率是恒定的(实际使用过程中会采用学习率衰减策略,因此学习率递减)。AdaGrad的二阶动量不断累积,单调递增,因此学习率是单调递减的。因此,这两类算法会使得学习率不断递减,最终收敛到0,模型也得以收敛。
Adam罪状二:可能错过全局最优解
深度神经网络往往包含大量的参数,在这样一个维度极高的空间内,非凸的目标函数往往起起伏伏,拥有无数个高地和洼地。有的是高峰,通过引入动量可能很容易越过;但有些是高原,可能探索很多次都出不来,于是停止了训练。
不同优化算法最核心的区别,就是第三步所执行的下降方向:
ηt=(α/Vt)⋅mt\eta_{t}=(\alpha / \sqrt{V_{t}}) \cdot m_{t} ηt=(α/Vt)⋅mt
这个式子中,前半部分是实际的学习率(也即下降步长),后半部分是实际的下降方向。SGD算法的下降方向就是该位置的梯度方向的反方向,带一阶动量的SGD的下降方向则是该位置的一阶动量方向。自适应学习率类优化算法为每个参数设定了不同的学习率,在不同维度上设定不同步长,因此其下降方向是缩放过(scaled)的一阶动量方向。
那么我们就会想到,可不可以把这两者结合起来,先用Adam快速下降,再用SGD调优,一举两得?思路简单,但里面有两个技术问题:
什么时候切换优化算法?——如果切换太晚,Adam可能已经跑到自己的盆地里去了,SGD再怎么好也跑不出来了。切换算法以后用什么样的学习率?——Adam用的是自适应学习率,依赖的是二阶动量的累积,SGD接着训练的话,用什么样的学习率?
首先来看第二个问题,切换之后用什么样的学习率。Adam的下降方向是
ηtAdam=(α/Vt)⋅mt\eta_{t}^{A d a m}=(\alpha / \sqrt{V_{t}}) \cdot m_{t} ηtAdam=(α/Vt)⋅mt
而SGD的下降方向是
ηtSGD=αSGD⋅gt\eta_{t}^{S G D}=\alpha^{S G D} \cdot g_{t} ηtSGD=αSGD⋅gt
ηtSGD\eta_{t}^{S G D}ηtSGD必定可以分解为 ηtAdam\eta_{t}^{A d a m}ηtAdam 所在方向及其正交方向上的两个方向之和,那么其在ηtAdam\eta_{t}^{A d a m}ηtAdam 方向上的投影就意味着SGD在Adam算法决定的下降方向上前进的距离,而在 ηtAdam\eta_{t}^{A d a m}ηtAdam 的正交方向上的投影是 SGD 在自己选择的修正方向上前进的距离。
图片来自原文,这里p为Adam下降方向,g为梯度方向,r为SGD的学习率。
如果SGD要走完Adam未走完的路,那就首先要接过Adam的大旗——沿着 ηtAdam\eta_{t}^{A d a m}ηtAdam 方向走一步,而后在沿着其正交方向走相应的一步。
这样我们就知道该如何确定SGD的步长(学习率)了——SGD在Adam下降方向上的正交投影,应该正好等于Adam的下降方向(含步长)。也即:
projηtSGD=ηtAdam\operatorname{proj}_{\eta_{t}^{S G D}}=\eta_{t}^{\operatorname{Adam}} projηtSGD=ηtAdam
解这个方程,我们就可以得到接续进行SGD的学习率:
αtSGD=((ηtAdam)TηtAdam)/((ηtAdam)Tgt)\alpha_{t}^{S G D}=\left(\left(\eta_{t}^{\operatorname{Adam}}\right)^{T} \eta_{t}^{\operatorname{Adam}}\right) /\left(\left(\eta_{t}^{\operatorname{Adam}}\right)^{T} g_{t}\right) αtSGD=((ηtAdam)TηtAdam)/((ηtAdam)Tgt)
为了减少噪声影响,作者使用移动平均值来修正对学习率的估计:
λtSGD=β2⋅λt−1SGD+(1−β2)⋅αtSGDλ~tSGD=λtSGD/(1−β2t)\begin{aligned} \lambda_{t}^{S G D}=& \beta_{2} \cdot \lambda_{t-1}^{S G D}+\left(1-\beta_{2}\right) \cdot \alpha_{t}^{S G D} \\ & \tilde{\lambda}_{t}^{S G D}=\lambda_{t}^{S G D} /\left(1-\beta_{2}^{t}\right) \end{aligned} λtSGD=β2⋅λt−1SGD+(1−β2)⋅αtSGDλ~tSGD=λtSGD/(1−β2t)
这里直接复用了Adam的 β2\beta_2β2 参数。
然后来看第一个问题,何时进行算法的切换。
作者的回答也很简单,那就是当 SGD的相应学习率的移动平均值基本不变的时候,即:
∣λ~tSGD−αtSGD∣<ϵ\left|\tilde{\lambda}_{t}^{S G D}-\alpha_{t}^{S G D}\right|<\epsilon ∣∣∣λ~tSGD−αtSGD∣∣∣<ϵ
.每次迭代玩都计算一下SGD接班人的相应学习率,如果发现基本稳定了,那就SGD以 λ~tSGD\tilde{\lambda}_{t}^{S G D}λ~tSGD 为学习率接班前进。
3.优化方法汇总(Newton家族,二阶导数)
为什么深度学习不采用newton家族的算法作为优化算法:
答:牛顿法需要用到梯度和Hessian矩阵(二阶梯度矩阵),很难写出深度神经网络你和函数的表达式,更不用说求解梯度和Hessian矩阵了,即使能够求解,在输入特征维度较高的时候,Hessian矩阵大小是n*n,耗费内存较高,求逆更是做梦;另外,当为凸函数的时候,牛顿法一定会下降,但是非凸的时候不一定
牛顿法
基本思想:在现有极小点估计值的附近对f(x)做二阶泰勒展开,进而找到极小点的下一个估计值
2.拟牛顿法
为了解决牛顿法中Hessian矩阵的问题,构造Hessian矩阵的近似矩阵来还原Hessian矩阵,常有DFP,BFGS算法
4.距离的度量
对于距离的度量需要满足一些基本的性质:
非负性,同一性,对称性,三角不等式:
常用的度量距离的方案:
连续变量的距离度量
欧氏距离(适用于连续变量间的距离度量)
所有与原点的距离为1的构成了一个半径1的圆形
切比雪夫距离
dist=max(∣x1−x2∣,∣y1−y2∣)dist=max(|x_1-x_2|,|y_1-y_2|)dist=max(∣x1−x2∣,∣y1−y2∣)
所有与原点的距离为1的构成了一个边长2的正方形
曼哈顿距离
dist=∣x1−x2∣+∣y1−y2∣dist=|x_1-x_2|+|y_1-y_2|dist=∣x1−x2∣+∣y1−y2∣
马氏距离
用来度量一个样本点P与数据分布为D的集合的距离。
假设一个样点P为:x=(x1,x2,x3,...,xN)Tx = (x_1,x_2,x_3,...,x_N)^Tx=(x1,x2,x3,...,xN)T
数据集D均值为:μ=(μ1,μ2,μ3,...,μN)T\mu = (\mu_1,\mu_2,\mu_3,...,\mu_N)^Tμ=(μ1,μ2,μ3,...,μN)T,协方差矩阵是S
则这个样本点P与数据集合D的马氏距离为:DM(x)=(x−μ)TS−1(x−μ)D_M(x) = \sqrt{(x-\mu)^TS^{-1}(x-\mu)}DM(x)=(x−μ)TS−1(x−μ)
马氏距离也可以衡量两个来自同一分布的样本x和y的相似性,其中x和y是向量:d(x,y)=(x−y)TS−1(x−y)d(x,y) = \sqrt{(x-y)^TS^{-1}(x-y)}d(x,y)=(x−y)TS−1(x−y)
向量距离的度量
余弦距离
cosθ=aTb∣a∣∣b∣cos\theta = \frac{a^Tb}{|a||b|}cosθ=∣a∣∣b∣aTb
对于无序的类别特征度量,可以用one-hot加余弦距离来度量
变量之间的距离度量
皮尔逊相关系数考察两个变量的关系,值越大,两个变量越近强相关,即距离越近,所以距离
dist=1−ρX,Ydist=1-\rho_{X,Y}dist=1−ρX,Y
ρX,Y=Cov(X,Y)/σXσY=E((X−μX)(Y−μY))/σXσY\rho_{X,Y} = Cov(X, Y)/\sigma_X\sigma_Y = E((X-\mu_X)(Y-\mu_Y))/\sigma_X\sigma_YρX,Y=Cov(X,Y)/σXσY=E((X−μX)(Y−μY))/σXσY
spearman相关系数
spearman相关系数采用的是取值等级而不是取值本身,例如,给定三个值:33,21,44,它们的等级就分别是2,1,3
相对于皮尔森相关系数,斯皮尔曼相关系数对于数据错误和极端值的反应不敏感。
5.大数定律与中心极限定理
6 引用
1 /p/32230623
2 /peghoty/
引用太多,无法一一列举,如有需要请私信我
如果觉得《机器学习算法Part1 基本数学概念》对你有帮助,请点赞、收藏,并留下你的观点哦!