Embedding算法之矩阵分解

矩阵分解"/>

Embedding算法之矩阵分解

说明

此文章翻译来自2014年nips，Neural Word Embedding as Implicit Matrix Factorization，引用量632。主要贡献是把经典skip-gram算法通过PMI，和矩阵分解联系了起来，并深入探讨了Skip-gram算法的优劣势。作者Omer Levy及Yoav Goldberg，来自Bar-Ilan University。

基于负采样的Skip-gram模型（skip-gram with negative sampling）

把Skip-gram with negative sampling模型简写为SGNS,词对 (w,c) ( w , c ) $(w,c)$在data出现的概率为 p(D=1/w,c) p ( D = 1 / w , c ) $p(D=1/w,c)$,不出现的概率为 p(D=0/w,c) p ( D = 0 / w , c ) $p(D=0/w,c)$,有：

P(D=1/w,c)=σ(w⃗ ⋅c⃗ )=11+e−w⃗ ⋅c⃗  P ( D = 1 / w , c ) = σ ( w → ⋅ c → ) = 1 1 + e − w → ⋅ c → $$P(D=1/w,c)=\sigma(\vec{w}\cdot \vec{c})=\frac{1}{1+e^{-\vec{w}\cdot \vec{c}}}$$
而基于负采样的模型对于单个的 (w,c) ( w , c ) $(w,c)$的目标函数是：
logσ(w⃗ ⋅c⃗ )+k⋅EcN∼PD[logσ(−w⃗ ⋅c⃗ )] l o g σ ( w → ⋅ c → ) + k ⋅ E c N ∼ P D [ l o g σ ( − w → ⋅ c → ) ] $$log\sigma(\vec{w}\cdot \vec{c})+k\cdot \mathbb{E}_{c_N\sim P_D}[log\sigma(-\vec{w}\cdot \vec{c})]$$
其中， k k $k$是负采样数目，cN" role="presentation" style="position: relative;">cNcN$c_N$是sample context,而 PD(c) P D ( c ) $P_D(c)$是 c c $c$出现的概率，可以根据已有数据计算PD(c)=#(c)D" role="presentation" style="position: relative;">PD(c)=#(c)DPD(c)=#(c)D$P_D(c)=\frac{\#(c)}{D}$。总的目标函数为：
ℓ=∑w∈VW∑c∈VC#(w,c)(logσ(w⃗ ⋅c⃗ )+k⋅EcN∼PD[logσ(−w⃗ ⋅c⃗ )]) ℓ = ∑ w ∈ V W ∑ c ∈ V C # ( w , c ) ( l o g σ ( w → ⋅ c → ) + k ⋅ E c N ∼ P D [ l o g σ ( − w → ⋅ c → ) ] ) $$\ell=\sum_{w\in V_W} \sum_{c\in V_C}\#(w,c)(log\sigma(\vec{w}\cdot \vec{c})+k\cdot \mathbb{E}_{c_N\sim P_D}[log\sigma(-\vec{w}\cdot \vec{c})])$$
文章没有看到为什么这里有一个 #(w,c) # ( w , c ) $\#(w,c)$，个人觉得应该是带权重的意思，出现频率越高，词对越重要的，如有理解错误，敬请指正。

SGNS其实是一种隐式的矩阵分解

公式推导

把总体目标函数展开，得到：

ℓ=∑w∈VW∑c∈VC#(w,c)logσ(w⃗ ⋅c⃗ )+∑w∈VW#(w)(k⋅EcN∼PD[logσ(−w⃗ ⋅c⃗ )]) ℓ = ∑ w ∈ V W ∑ c ∈ V C # ( w , c ) l o g σ ( w → ⋅ c → ) + ∑ w ∈ V W # ( w ) ( k ⋅ E c N ∼ P D [ l o g σ ( − w → ⋅ c → ) ] ) $$\ell=\sum_{w\in V_W} \sum_{c\in V_C}\#(w,c)log\sigma(\vec{w}\cdot \vec{c})+\sum_{w\in V_W}\#(w)(k\cdot \mathbb{E}_{c_N\sim P_D}[log\sigma(-\vec{w}\cdot \vec{c})])$$
注意这里有一个技巧，把 ∑#(w,c) ∑ # ( w , c ) $\sum \#(w,c)$给简化了。再简化：
EcN∼PD[logσ(−w⃗ ⋅c⃗ )]=∑cN∈VCPD(cN)logσ(−w⃗ ⋅c⃗ ) E c N ∼ P D [ l o g σ ( − w → ⋅ c → ) ] = ∑ c N ∈ V C P D ( c N ) l o g σ ( − w → ⋅ c → ) $$\mathbb{E}_{c_N\sim P_D}[log\sigma(-\vec{w}\cdot \vec{c})]=\sum_{c_N\in V_C}P_D(c_N)log\sigma(-\vec{w}\cdot \vec{c})$$
这里是期望公式，把 PD(cN)=#c(N)/D P D ( c N ) = # c ( N ) / D $P_D(c_N)=\#c(N)/D$带入化简为：
EcN∼PD[logσ(−w⃗ ⋅c⃗ )]=#(c)|D|logσ(−w⃗ ⋅c⃗ )+∑cN∈VC∖c#(cN)|D|logσ(−w⃗ ⋅cN→) E c N ∼ P D [ l o g σ ( − w → ⋅ c → ) ] = # ( c ) | D | l o g σ ( − w → ⋅ c → ) + ∑ c N ∈ V C ∖ c # ( c N ) | D | l o g σ ( − w → ⋅ c N → ) $$\mathbb{E}_{c_N\sim P_D}[log\sigma(-\vec{w}\cdot \vec{c})]=\frac{\#(c)}{\left | D \right |}log\sigma(-\vec{w}\cdot \vec{c})+\sum_{c_N \in V_C \setminus {c}}\frac{\#(c_N)}{\left | D \right |}log\sigma(-\vec{w}\cdot \vec{c_N})$$
对于一个特定的词对，后面一项便没有了，化简为：
ℓ=#(w,c)logσ(w⃗ ⋅c⃗ )+k⋅#(w)⋅#(c)|D|logσ(−w⃗ ⋅c⃗ ) ℓ = # ( w , c ) l o g σ ( w → ⋅ c → ) + k ⋅ # ( w ) ⋅ # ( c ) | D | l o g σ ( − w → ⋅ c → ) $$\ell=\#(w,c)log\sigma(\vec{w}\cdot \vec{c})+k\cdot \#(w)\cdot \frac{\#(c)}{\left | D \right |}log\sigma(-\vec{w}\cdot \vec{c})$$
此时，我们把 w⃗ ⋅c⃗  w → ⋅ c → $\vec{w}\cdot \vec{c}$作为一个整体求解，求导使得为0，化简后得到：
w⃗ ⋅c⃗ =log(#(w,c)⋅|D|#(w)⋅#(c))−logk w → ⋅ c → = l o g ( # ( w , c ) ⋅ | D | # ( w ) ⋅ # ( c ) ) − l o g k $$\vec{w}\cdot \vec{c}=log\left ( \frac{\#(w,c)\cdot \left |D \right |}{\#(w)\cdot \#(c)} \right )-logk$$
等式右边是可以直接计算的，而k是负采样的个数，人为设定的。接下来就是优化等式求得 w⃗  w → $\vec{w}$和 c⃗  c → $\vec{c}$的问题了，word2vec中用的是梯度下降法，这篇文章里用的是svd，经过了处理的svd，后面将展开。这里还要说的是：
PMI(w,c)=log(#(w,c)⋅|D|#(w)⋅#(c)) P M I ( w , c ) = l o g ( # ( w , c ) ⋅ | D | # ( w ) ⋅ # ( c ) ) $$PMI(w,c)=log\left ( \frac{\#(w,c)\cdot \left |D \right |}{\#(w)\cdot \#(c)} \right )$$
PMI是pointwise mutual information的简写，是NLP中用得很多的一信息度量指标，带入后化简可以得到：
MSGNSij=Wi⋅Cj=w⃗ ⋅c⃗ =PMI(wi,cj)−logk M i j S G N S = W i ⋅ C j = w → ⋅ c → = P M I ( w i , c j ) − l o g k $$M_{ij}^{SGNS}=W_i \cdot C_j=\vec{w}\cdot \vec{c}=PMI(w_i,c_j)-logk$$
显然，当 k=1 k = 1 $k=1$的时候，就只剩下了一项PMI，此时得到的embedding可以看作就是对PMI的分解，如果 k>1 k > 1 $k>1$，那就是对PMI平移之后的分解。而另外一种embedding方法：noise-contrasitive estimation(NCE),也可化简为类似的形式：
MNCEij=w⃗ ⋅c⃗ =log(#(w,c)#(c))−logk=logP(w∖c)−logk M i j N C E = w → ⋅ c → = l o g ( # ( w , c ) # ( c ) ) − l o g k = l o g P ( w ∖ c ) − l o g k $$M_{ij}^{NCE}=\vec{w}\cdot \vec{c}=log\left ( \frac{\#(w,c)}{\#(c)} \right )-logk=logP(w\setminus c)-logk$$

Pointwise Mutual Information

PMI定义为：

PMI(w,c)=log(#(w,c)⋅|D|#(w)⋅#(c)) P M I ( w , c ) = l o g ( # ( w , c ) ⋅ | D | # ( w ) ⋅ # ( c ) ) $$PMI(w,c)=log\left ( \frac{\#(w,c)\cdot \left |D \right |}{\#(w)\cdot \#(c)} \right )$$
由每个词对组成的PMI矩阵，如果直接按照定义进行计算会出现问题，比如，当某一词对未出现过时， PMI(w,c)=log0=−∞ P M I ( w , c ) = l o g 0 = − ∞ $PMI(w,c)=log0=-\infty$.在NLP中常用的方法是将未知的PMI置零。另外还有一个问题就是，由PMI定义，如果分子特别大，分母很小，得到的PMI将为很大的负数，这也不合理，因此处理为：
PPMI(w,c)=max(PMI(w,c),0) P P M I ( w , c ) = m a x ( P M I ( w , c ) , 0 ) $$PPMI(w,c)=max(PMI(w,c),0)$$
Positive PMI,它是稀疏的，而且这样处理以后会有一种效果，两个词对出现决定了它的值，忽略了未出现的词对效果。

如何解得embeddings

Shifted PPMI (SPPMI)，由上一节得到：

SPPMIk(w,c)=max(PMI(w,c)−logk,0) S P P M I k ( w , c ) = m a x ( P M I ( w , c ) − l o g k , 0 ) $$SPPMI_k(w,c)=max(PMI(w,c)-logk,0)$$
我们假定 MSPPMIk M S P P M I k $M^{SPPMI_k}$是由所有词对组成的矩阵，这个矩阵我们是可以直接求得的，由上面的推导我们有：
MSPPMIk=W⋅C M S P P M I k = W ⋅ C $$M^{SPPMI_k}=W\cdot C$$
等式左边是知道的，就是一个矩阵如何分解成两个矩阵，并且是两个维度更低的矩阵相乘。现今非常成熟的SVD即是一种矩阵分解方法，取特征值最大的特征向量组成矩阵后，使得其前后损失最小，即： MSPPMIk≈Md M S P P M I k ≈ M d $M^{SPPMI_k}\approx M_d$，使得：
Md=arg minRank(M′=d)∥∥M′−M∥∥2 M d = a r g m i n R a n k ( M ′ = d ) ‖ M ′ − M ‖ 2 $$M_d=arg \ min_{Rank(M^{'}=d)}\left \| M^{'}-M \right \|_2$$
其形式为 Md=Ud⋅Σd⋅VTd M d = U d ⋅ Σ d ⋅ V d T $M_d=U_d \cdot \Sigma _d \cdot V_d^T$,由此可以直接取得;
WSVDα=Ud⋅(Σd)α , CSVDα=Vd⋅(Σd)1−α W S V D α = U d ⋅ ( Σ d ) α , C S V D α = V d ⋅ ( Σ d ) 1 − α $$W^{SVD_{\alpha }}=U_d \cdot (\Sigma _d)^{\alpha }\ ,\ C^{SVD_{\alpha }} = V_d \cdot (\Sigma _d)^{1-\alpha }$$
α α $\alpha$常常取0,1,1/2.

SVD对比SGNS优劣势分析

优势

1.SVD不需要调参，比如学习率
2.SVD在已知 (w,c,#(w,c)) ( w , c , # ( w , c ) ) ${(w,c,\#(w,c))}$的情况下更易于训练，而SGNS需要单独知道每一对 (w,c) ( w , c ) $(w,c)$的观察值

劣势

1.SGNS对未观察到的数据分别处理，利用了未观察到的数据，而SVD都置零了
2.SGNS对每一对词对分别处理，频率较高的词对将得到更好的结果，而对未观察到的词对具有更好的容错性。
3.SGNS每次处理某一词对时并不需要让其他未观察到的词对值为0，不需要对词对矩阵作稀疏处理即可优化得到各自的embedding

stochastic matrix factorization

作者提到了SVD和SGNS的一种middle-groud算法，兼具两者优点。