word2vec和它的亲戚矩阵分解

原文发表于公众号：一个算卦工程师的自白，欢迎拉到文末关注，接收作者各种靠谱和不靠谱的推送。

论文题目：Neural Word Embedding as Implicit Matrix Factorization

 这是一篇2014年NIPS上的文章，比较老了，以前也被标题吸引下载过，但一直没看。近期看了一系列词向量表示的文章，尤其是前两天看到的一篇文章提到了用SVD分解PMI矩阵来替代word2vec，让我又想起了这篇文章，所以最近又找出来仔细看了一遍，很有收获。

这篇文章的核心是讲了这么几件事情：

SGNS和PMI矩阵的等价性推导：

1. 通过损失函数变换推导证明了SGNS（Skip-gram Negative Sampling）的优化结果，也就是一堆词向量，和分解一个PMI矩阵得到的结果，也就是的一个矩阵的行向量，是近似一回事，只差了一个常量log(k)，其中k是每条正样本对应的负样本的数量。也就是说被分解的矩阵的每个元素为PMI(w,c)-log(k)，其中w是中心词，c是上下文词。简单证明过程如下（详细证明请参考论文）：

   1. 首先，可证明，如果w和c可取无限长SGNS的loss取到最小值时，对应的w·c（点乘）对应的就是PMI(w,c)-log(k)。这是因为，如果w和c可取无限长，则可认为有无限多个参数可用，那么根据基础的可学习理论，每个wi·ci就可以独立拟合任意一个值。

   2. 然后，将SGNS的loss进行重新整理，其中一个关键步骤是将w·c看做一个整体变量x，并将每个cell独立优化——可以独立优化的前提是前面提到的w和c可取无限长所以w和c可以独立拟合需要的值，通过梯度取最小，就可以得出每个独立的w和c对应的w·c在local loss取到最小时所取的值，而这个值，恰好就是PMI(w,c)-log(k)。

2. NCE loss优化的过程与SGNS类似，其结果等价于分解一个条件概率矩阵，即矩阵中每个元素为logP(w|c)-log(k)，变量含义同上。

3. 但是，在现实中肯定是不可能取任意长的w和c的，所以就会有的cell要偏离上面提到的最优质，所以问题就变成了一个带权的矩阵分解问题，其中权重由wc的pair的出现次数决定，限制条件就是k，也就是w和c向量的长度限制。

PMI矩阵分解的优化方法：

1. 由于PMI矩阵是个稠密矩阵，还会有很多不好处理的缺失值，而且把缺失值写成0也会有问题，所以分解Positive PMI会更合理，也就是把所有非正值都变成0。

   1. 作者认为，忽略PMI矩阵中的负值的直觉原因是有正向关联的词更有用，例如Canada和snow，而有反向关联的词并没有那么有用，例如Canada和desert。所以两个词的相似度更多是由他们共同出现的正向例子所影响的，而不是反向例子[1]。

2. 进一步地，作者类比PPMI提出了Shifted PPMI，也就是把元素为PMI(w,c)-log(k)这个矩阵也做positive处理，分解这个SPPMI矩阵就对应着优化SGNS。

3. 分解SPPMI可以直接用SVD分解，SVD在复原PMI或类似矩阵方面效果非常好，而且不用调优任何参数，但在具体NLP任务上则效果不一。

4. SVD与SGNS的比较：

   1. 但我对这点表示疑惑，因为PMI矩阵中的cell已经就是带权的了，直接优化不就好了吗？为什么还需要考虑是否带权的问题呢？

   2. SVD分解的结果在word similarity上面表现不差异SGNS，但是在analog等其它问题上效果就不如SGNS了。

   3. SVD分解可以在简单计数的结果上进行，而无需构造海量的SGNS样本。这对于数据量很大的情况下有优势，因为在这个场景下SVD的计算量不变，但是SGNS的计算量则会随着样本量增大而增大。

   4. SVD方法不能随着向量维度的提升而提升，但SGNS可以。原因之一是维度提升之后SVD就会尽力去拟合一个大量结果是0的矩阵，得到一个近似0的结果。

   5. SVD无法解决带权的问题，但SGNS是基于SGD的，可以解决这个问题。所以SGNS会给高频样本更多注意，使其优化效果更好，但SVD无法区分这一点，也无法针对性优化高频数据。

   6. SVD不处理未观察到的结果，SGNS可以，因为这是它的负样本。

   7. SGNS不要求矩阵是稀疏的，但SVD要求矩阵最好稀疏，否则计算量很大。

5. 基于梯度的SVD（SMF）的优势劣势介于SVD和SGNS之间，比如计算能力比SVD强，可以处理权重，不能完全复原原始矩阵等。

总结起来，这篇文章最重要的意义在于让我们对于词向量这个有点黑盒子的东西有了一个比较好理解的维度，一个合理的解释，但SVD的方法由于有上面种种问题，并不一定适合在大柜数据的实际场景中运用。

后记：后来又看到一篇文章[2]说本文的推论不成立，原因在于SGNS等价于矩阵分解的前提是w和c可取无限长，也就是有无限个参数可用，但事实上不是这样。但我觉得可以把w和c无限制的情况看作是最优情况，也就是目标值，而有限制的情况是我们的学习模型，目的是拟合这个目标值，也就是把问题看作是一个回归问题，这样得到的结果应该也是合理的。而且从实际效果上来看，用SVD分解SPPMI矩阵确实能起到不错的效果。

话说回来，即使本文提出的推论有瑕疵，但仍然是把SGNS和MF做比较讨论的第一篇公开文章（我所知道的），其贡献还是很大的。

---

1. 这种做法感觉和ReLU的思想很像，都是舍弃负值，只使用正值。 

2. http://building-babylon.net/2016/05/12/skipgram-isnt-matrix-factorisation/