19 Nov

更别致的词向量模型(四):模型的求解

损失函数

现在,我们来定义loss,以便把各个词向量求解出来。用$\tilde{P}$表示$P$的频率估计值,那么我们可以直接以下式为loss
\[\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{v}_j\rangle-\log\frac{\tilde{P}(w_i,w_j)}{\tilde{P}(w_i)\tilde{P}(w_j)}\right)^2\tag{16}\]
相比之下,无论在参数量还是模型形式上,这个做法都比glove要简单,因此称之为simpler glove。glove模型是
\[\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{\hat{v}}_j\rangle+b_i+\hat{b}_j-\log X_{ij}\right)^2\tag{17}\]
在glove模型中,对中心词向量和上下文向量做了区分,然后最后模型建议输出的是两套词向量的求和,据说这效果会更好,这是一个比较勉强的trick,但也不是什么毛病。最大的问题是参数$b_i,\hat{b}_j$也是可训练的,这使得模型是严重不适定的!我们有
\[\begin{aligned}&\sum_{w_i,w_j}\left(\langle \boldsymbol{v}_i, \boldsymbol{\hat{v}}_j\rangle+b_i+\hat{b}_j-\log \tilde{P}(w_i,w_j)\right)^2\\
=&\sum_{w_i,w_j}\left[\langle \boldsymbol{v}_i+\boldsymbol{c}, \boldsymbol{\hat{v}}_j+\boldsymbol{c}\rangle+\Big(b_i-\langle \boldsymbol{v}_i, \boldsymbol{c}\rangle - \frac{|\boldsymbol{c}|^2}{2}\Big)\right.\\
&\qquad\qquad\qquad\qquad\left.+\Big(\hat{b}_j-\langle \boldsymbol{\hat{v}}_j, \boldsymbol{c}\rangle - \frac{|\boldsymbol{c}|^2}{2}\Big)-\log X_{ij}\right]^2\end{aligned}\tag{18}\]
这就是说,如果你有了一组解,那么你将所有词向量加上任意一个常数向量后,它还是一组解!这个问题就严重了,我们无法预估得到的是哪组解,一旦加上的是一个非常大的常向量,那么各种度量都没意义了(比如任意两个词的cos值都接近1)。事实上,对glove生成的词向量进行验算就可以发现,glove生成的词向量,停用词的模长远大于一般词的模长,也就是说一堆词放在一起时,停用词的作用还明显些,这显然是不利用后续模型的优化的。(虽然从目前的关于glove的实验结果来看,是我强迫症了一些。)

互信息估算

阅读剩余部分...

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$)的整数解。

阅读剩余部分...