失眠网 > 机器学习算法Part1 基本数学概念

机器学习算法Part1 基本数学概念

时间：2019-03-13 23:37:46

相关推荐

机器学习算法Part1 基本数学概念

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μ∑log⁡p(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老是跟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=1mlog⁡p(xi;θ)l(\theta)=\sum_{i=1}^{m} \log p\left(x_{i} ; \theta\right)l(θ)=∑i=1mlogp(xi;θ)

我们需要求得这个似然函数的一个最大值

由于我们不知道观察到的序列来自于哪个子模型，则

l(θ)=∑i=1mlog⁡p(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)log⁡p(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

相对于皮尔森相关系数，斯皮尔曼相关系数对于数据错误和极端值的反应不敏感。