0%

embedding as matrix factorizaiton

Neural Word Embedding as Implicit Matrix Factorization

前言

尽管嵌入模型很明显是基于分布假设来进行优化,使常出现的word-context对向量内积极大化,并极小化随机word-context对内积。但对于这些优化指标的讨论很少,也不清楚为什么这样能够得到期望的结果。这篇文章对此进行了探讨,表明SGNS(skip-gram with negative-sampling)的训练方法实际上是加权矩阵分解,其目标函数在隐式地分解一个移动PMI矩阵,并基于此提出了更高效的优化方式。

SGNS

关于skip-gram with negative-sampling,这里就不再赘述,请查看下面两篇文章:

总的来说,SGNS的目标函数如下:

这里$V_W$为单词集,$V_C$为上下文集,$P_D$为均匀测度满足$P_D(c)=\frac{|(c)|}{|D|}$.

隐式矩阵分解下的SGNS

SGNS将单词以及上下文嵌入为低维空间的向量,得到单词与上下文向量构成的矩阵$W$与$C$,这两者实际上是相同的。$W$的行元素(即单词嵌入向量)被直接提取使用,但原始SG模型会进行上下文预测,SGNS可以看作是对矩阵$M=W\cdot C^T$的分解。

对于$M$,其分量$M_{i,j}$对应了$W_i,C_j$的向量积,这表示着特定单词与上下文的关联强度,而这种关联矩阵常常出现于NLP的研究中,但该矩阵并没有显式出现在SGNS的优化函数中,那么将SNGS看作对$M$的隐式分解说得通吗?如果不是,SGNS分解的是哪个矩阵呢?

刻画该隐式矩阵

重写式子$(1)$:

然后显式地计算出期望项:

结合两式并将$l$改写为局部形式:

定义$x=\vec{w}\cdot \vec{c}$,并对其求导:

令其为零得到:

我们可以直接给出显式解:

这里指出$log(\frac{|(w,c)|\cdot|D|}{|(w)|\cdot |(c)|})$即$(w,c)$的PMI(pointwise mutual information),PMI常见于nlp的研究中,可以进一步将上式写为:

SGNS实际上在分解上述的矩阵,当$k=1$即负采样率为1时,SGNS的目标函数其实在分解由单词与上下文构成的关联矩阵,并且关联强度由PMI给出,这里将其定义为PMI阵,$M^{PMI}$. 当$k$变化时,对应的PMI阵会有所偏移,$M^{PMIk}=M^{PMI}-logk$.

其它的嵌入算法也可以相应理解,如noise-contrastive estimation模型分解的矩阵为:

PMI

PMI是信息理论中用于度量一对离散输出$x,y$的度量函数:

在进行词嵌入时,上面的概率完全是由计数来估计的:

上面所给的PMI估计并不是定义良好的,当不存在某个$(w,c)$对时,对应的估计将为负无穷,一个修改方式是将负无穷的分量重整为0。但考虑PMI的语义,这并不合理,更好的做法是将负值全都置为零,这称为postive PMI(PPMI):

词嵌入的其它选择

首先由前面的推导,很容易得到下面的shifted PPMI:

谱降维:SVD over Shifted PPMI

如果将SGNS理解为矩阵分解,那么通常的矩阵分解也可以直接用于求解词嵌入,这里使用truncated SVD.

SVD将M分解为三个矩阵的乘积$U\cdot \Sigma \cdot V^T$,这里$U$和$V$是正交阵,$\Sigma$为奇异值构成的对角阵。令$\Sigma_d$为前$d$个奇异值构成的对角阵,$U_d$和$V_d$为从$U,V$对应列抽出的子阵。$M_d=U_d\cdot \Sigma_d \cdot V_d^T$为$M$的秩$d$最佳估计,即有$M_d=\mathop{\arg\min}\limits_{Rank(M’)=d}||M’-M||_2$成立.

如果使用SVD,那么$W=U_d \cdot \Sigma_d$行间的向量积等于$M_D$行间的向量积,使用$W$足够作为$M_D$的低维稠密表示。在NLP的研究中,一个常见方法是对PPMI矩阵$M^{PPMI}$进行SVD分解,并使用$W^{SVD}=U_d\cdot \Sigma_d$以及$C^{SVD}=V_D$的行元素分别作为单词与上下文表示。但这种方法得到的结果在语义任务上总是达不到SGNS的性能。

对称SVD

如果直接使用SVD来分解,那么最终得到的单词、上下文嵌入阵会相当不同,仅$C^{SVD}$为正交的,SGNS方法相比显得更加对称,故而这里使用如下的分解:

尽管缺乏理论解释,但在实践中进行对称化后能得到更好的性能。

SVD versus SGNS

SVD不需要训练以及超参数的调整,对任何$\{(w,c,|(w,c)|)\}$形式的数据都可以使用,泛用性更高。

而SGNS可以更好地处理观察,未观察事件;除此之外, SGNS对不同$(w,c)$对分配了不同权重,这对于SVD来说是相当困难的,对于非稀疏的矩阵SGNS拥有更高的分解效率。

一个有趣的想法是使用随机矩阵分解,作者将其放在未来工作中。

实验结果

个人觉得理论仍然不太充分,有些地方还是有点自圆其说,实验结果还过得去。

table1

table2