Created by potrace 1.13, written by Peter Selinger 2001-2015

从函数近似的角度看梯度下降,牛顿法及EM算法

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

梯度下降

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

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

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

image

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

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

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

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
评论加载中...
发表评论