23 Mar

梯度下降和EM算法:系出同源,一脉相承

PS:本文就是梳理了梯度下降与EM算法的关系,通过同一种思路,推导了普通的梯度下降法、pLSA中的EM算法、K-Means中的EM算法,以此表明它们基本都是同一个东西的不同方面,所谓“横看成岭侧成峰,远近高低各不同”罢了。

在机器学习中,通常都会将我们所要求解的问题表示为一个带有未知参数的损失函数(Loss),如平均平方误差(MSE),然后想办法求解这个函数的最小值,来得到最佳的参数值,从而完成建模。因将函数乘以-1后,最大值也就变成了最小值,因此一律归为最小值来说。如何求函数的最小值,在机器学习领域里,一般会流传两个大的方向:1、梯度下降;2、EM算法,也就是最大期望算法,一般用于复杂的最大似然问题的求解。

在通常的教程中,会将这两个方法描述得迥然不同,就像两大体系在分庭抗礼那样,而EM算法更是被描述得玄乎其玄的感觉。但事实上,这两个方法,都是同一个思路的不同例子而已,所谓“本是同根生”,它们就是一脉相承的东西。

让我们,先从远古的牛顿法谈起。

牛顿迭代法

给定一个复杂的非线性函数$f(x)$,希望求它的最小值,我们一般可以这样做,假定它足够光滑,那么它的最小值也就是它的极小值点,满足$f'(x_0)=0$,然后可以转化为求方程$f'(x)=0$的根了。非线性方程的根我们有个牛顿法,所以
$$x_{n+1} = x_{n} - \frac{f'(x_n)}{f''(x_n)}$$

阅读剩余部分...

27 Jun

Project Euler 454 :五天攻下“擂台”

进入期末了,很多同学都开始复习了,这学期我选的几门课到现在还不是很熟悉,本想也在趁着这段时间好好看看。偏生五天前我在浏览数学研发论坛的编程擂台时看到了这样的一道题目

设对于给定的$L$,方程
$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$
满足$0 < x < y \leq L$的正整数解共有$f(L)$种情况。比如$f(6)=1,f(12)=3,f(1000)=1069$,求$f(10^{12})$。

这道题目的来源是Project Euler的第454题:Diophantine reciprocals III(丢潘图倒数方程),题目简短易懂,但又不失深度,正符合我对理想题目的定义。而且最近在学习Python学习得不亦乐乎,看到这道题目就跃跃欲试。于是乎,我的五天时间就没有了,而且过程中几乎耗尽了我现在懂的所有编程技巧。由于不断地测试运行,我的电脑发热量比平时大了几倍,真是辛苦了我的电脑。最后的代码,自我感觉已经是我目前写的最精彩的代码了。在此与大家共享和共勉~

上述表达式是分式,不利于编程,由于$n=\frac{xy}{x+y}$,于是上述题目也等价于求$(x+y)|xy$(意思是$x+y$整除$xy$)的整数解。

阅读剩余部分...