对于复杂函数,很难求得其极值,所以诞生的很多算法通过迭代求得函数的极值,本文用函数近似的思想来理解梯度下降,牛顿法及EM算法.

梯度下降

f(x)进行一阶泰勒展开:

f(x)= f(x_n)+f'(x_n)(x-x_n)

f(x_n)x_n看成常量,这相当于关于x的一次函数:
image.png

当每步足够小时,找原函数的最低点,相当于找这条直线的最低点,所以有迭代公式:

x_{n+1}=x_n-\eta f'(x_n)

换种说法,梯度下降其实就是用x_n处函数的切线,来近似代替原函数求极值.

牛顿法

f(x)进行二阶泰勒展开:

f(x)= f(x_n)+f'(x_n)(x-x_n)+\frac{1}{2}f''(x_n)(x-x_n)^2

f(x_n)x_n看成常量,这相当于关于x的抛物线:
image.png

找原函数的最低点,相当于找这条抛物线的最低点,所以有迭代公式:

x = x_0  - \frac{f'(x_0)}{f''(x_0)}

换种说法,牛顿法其实就是用x_n处函数的抛物线,来近似代替原函数求极值.

因为二次函数比一次函数更像原函数,所以牛顿法要比梯度下降迭代的快.但是当数据量和数据纬度比较大的时候,从矩阵的角度,矩阵二阶导数为海森矩阵(Hessian matrix),计算海森矩阵和它的逆矩阵是非常耗时,所以在机器学习任务中通常还是会采用梯度下降.

EM算法

EM算法是求交叉熵的极值的算法,交叉熵的公式为:

S=-\sum_{x,y} \tilde{p}(x,y)\log \sum_z p(x|z)p(z|y)

其中p(x|z),p(z|y)为待求参数.

EM算法也是采用函数近似的方法来求极值的,这个函数在很多教材中被称为G函数.

S使用梯度下降求极值是行不通的,因为概率需要满足条件:

p(x|z) >0 ,\quad p(z|y) > 0

\sum_z p(x|z) = 1,\quad \sum_y p(z|y)=1

我们不妨考虑这样的近似函数:

S_n'=-\sum_{x,y} \tilde{p}(x,y)\sum_z C_{x,y,z,n} \log p(x|z)p(z|y)

对比原S的一阶梯度,与S'的一阶梯度:

\begin{aligned}&\frac{\partial S}{\partial p_n(x|z)} = -\sum_{y} \frac{\tilde{p}(x,y)}{\sum_z p_n(x|z)p_n(z|y)}p_n(z|y)\\ 
&\frac{\partial S}{\partial p_n(z|y)} = -\sum_{x} \frac{\tilde{p}(x,y)}{\sum_z p_n(x|z)p_n(z|y)}p_n(x|z)\end{aligned}

\begin{aligned}&\frac{\partial S'}{\partial p_n(x|z)} = -\sum_{y} \frac{\tilde{p}(x,y)C_{x,y,z,n}}{p_n(x|z)}\\ 
&\frac{\partial S'}{\partial p_n(z|y)} = -\sum_{x} \frac{\tilde{p}(x,y)C_{x,y,z,n}}{p_n(z|y)}\end{aligned}

我们希望S′的梯度跟原来S的梯度是一样的(具有一阶精度),所以令:

\frac{\partial S}{\partial p_n(x|z)} = \frac{\partial S'}{\partial p_n(x|z)}

\frac{\partial S}{\partial p_n(z|y)} = \frac{\partial S'}{\partial p_n(z|y)}

可得:

C_{x,y,z,n}=\frac{p_n(x|z)p_n(z|y)}{\sum_z p_n(x|z)p_n(z|y)}

于是我们可以用S'代替原函数S求极值.


参考:
https://kexue.fm/archives/4277

posted @ 2018-12-12 09:08:51
评论加载中...

发表评论