1. 引言

2. 背景：Skip-Gram with Negative Sampling (SGNS)

翻译成“负采样跳图”？？

3. 作为隐式矩阵分解的 SGNS

SGNS 把单词和上下文都嵌入到低维空间 \(\mathbb{R}^d\)，生成单词和上下文矩阵 \(W\) 和 \(C\)。NLP 任务中一般用 \(W\) 来计算单词相似度，而 \(C\) 被丢弃。不管怎样我们来考虑一下这个矩阵 \(W \cdot C^{\mathsf{T}} = M\)。于是 SGNS 相当于把维度为 \(|V_W| \times |V_C|\) 的矩阵 \(M\) 分解为两个较小的矩阵。

分解的是个什么矩阵？\(M_{ij} = \vec{w}_i\cdot\vec{c}_j\) 。于是 \(M\) 这个矩阵每行对应于一个单词，每列对应一个上下文，而每个元素的值 \(f(w,c)\) 刻画一个单词和一个上下文之间的关联度。这种单词-上下文关联矩阵在 NLP 以及单词相似度领域很常见。不过，SGNS 的目标函数并没有明确说这种关联度具体如何定义。关于关联度 \(f(w,c)\) 我们能说些什么？SGNS 分解的是个什么矩阵？

3.1 隐式矩阵的性质

考虑上面的全局目标函数。当维度 \(d\) 足够大时 (此时相当于没有任何信息丢失，可以完美重构矩阵 \(M\))，每个内积 \(\vec{w}\cdot\vec{c}\) 可以独立于其它任意取值。

_{给定 \(n^2\) 个数 \(M_{ij}\)，求出 \(2n\) 个 \(d\) 维矢量 \(u_i\) 和 \(v_j\)，使得 \(u_i \cdot v_j = M_{ij}\)。当 \(2nd \ge n^2\) 总是有解的。}

把 \(l\) 重写为 \[ l = \sum_{w\in V_W} \sum_{c\in V_C} \#(w,c) \log\sigma(\vec{w}\cdot\vec{c}) +\\ \quad\quad\quad \sum_{w\in V_W} \#(w) \left\{k\cdot \mathbb{E}_{c_N\sim P_D} \left[\log\sigma(-\vec{w}\cdot\vec{c}_N)\right]\right\}。 \] 这里用到了 \(\sum_{w\in V_W}\sum_{c\in V_C} \#(w,c) f(w) = \sum_{w\in V_W} \#(w) f(w) \) 这个性质，因为 \(\sum_{c\in V_C} \#(w,c) = \#(w)\)。

可以把期望值那项显式写为 \[ \mathbb{E}_{c_N\sim P_D} \left[\log\sigma(-\vec{w}\cdot\vec{c}_N)\right] = \sum_{c_N\in V_C} \frac{\#(c_N)}{|D|} \log\sigma(-\vec{w}\cdot\vec{c}_N) \\ = \frac{\#(c)}{|D|} \log\sigma(-\vec{w}\cdot\vec{c}) + \sum_{c_N\in V_{C\backslash\{c\}}}\frac{\#(c_N)}{|D|} \log\sigma(-\vec{w}\cdot\vec{c}_N). \] 这里 \(c\) 是一个任意的上下文。 于是，对于特定的一对 \((w,c)\)，\(l\) 中对应的项是 \[ l(w,c) = \#(w,c)\log\sigma(\vec{w}\cdot\vec{c}) + k\cdot\#(w)\cdot\frac{\#(c)}{|D|}\cdot\sigma(-\vec{w}\cdot\vec{c}). \] 记 \(\vec{w}\cdot\vec{c}\) 为 \(x\)，通过 \(d l(w,c)/dx = 0\) 的条件，可得到 \[ \vec{w}\cdot\vec{c} = \log\left(\frac{\#(w,c)\cdot |D|}{\#(w)\cdot\#(c)}\right) - \log k. \] 有趣的是，这项 \[ \log\left(\frac{\#(w,c)\cdot |D|}{\#(w)\cdot\#(c)}\right) \] 正好是 \((w,c)\) 的逐点互信息 (PMI)。

_{随机变量 \(X\) 和 \(Y\) 的互信息定义为 \[ I(X; Y) = \sum_{x\in X, y\in Y} p(x,y)\log\left(\frac{p(x,y)}{p(x)p(y)}\right). \] \(\log\left(\frac{p(x,y)}{p(x)p(y)}\right)\) 是逐点互信息 PMI。}

于是我们知道，SGNS 分解的矩阵是 \[ M^{\text{SGNS}}_{ij} = \vec{w}_i\cdot\vec{c}_j = \text{PMI}(w_i, c_j) - \log k. \] 当 \(k=1\)，SGNS 的目标是分解单词与上下文的互信息矩阵 (PMI 矩阵)。当 \(k\ge2\)，PMI 矩阵平移了 \(\log k\)。

其它嵌入方法可以类似分析。比如 noise-contrastive estimation (NCE) 方法相当于分解平移过的对数条件概率矩阵 \[ M^{\text{NCE}}_{ij} = \vec{w}_i\cdot\vec{c}_j = \log\left(\frac{\#(w,c)}{\#(c)}\right) - \log k = \log P(w|c) - \log k. \]

3.2 加权矩阵分解

3.3 逐点互信息

这里逐点互信息的经验估计是 \[ \text{PMI}(w,c) = \log\left(\frac{\#(w,c)\cdot|D|}{\#(w)\cdot\#(c)}\right). \] PMI 作为 NLP 中关联度的度量，最初由 Church 和 Hanks 引入，被大量单词相似度任务采用。

\(M^\text{PMI}\) 这个矩阵的定义带来一些问题。由于许多 \((w,c)\) 对并没有观测到，所以相应的互信息是无穷。其次，这个矩阵是稠密的，并且维度很大（\(|V_W|\times|V_C|\)）。当然，我们通过可以把每个 \(\#(w,c)\) 都加 1 来去掉无穷，但矩阵仍然是稠密的。

NLP 中常用的另一种方法是，当 \(\#(w,c)=0\) 时，把相应的矩阵元设成 0; 这样得到的矩阵记为 \(M_0^\text{PMI}\)。但这导致了不自洽，因为相关性极弱的单词-上下文对给出负的矩阵元，而未观测到的（因此更加不相关）单词-上下文对对应的矩阵元是 0；这样显得不太公平，因为后者按理应该比前者更“负面”。

一种稀疏而自洽的方法是使用正定 PMI (PPMI) 度量 \[ \text{PPMI}(w,c) = \max(\text{PMI}(w,c), 0). \] 这样做的直觉解释是，人们似乎倾向于想到正面关联 (比如“加拿大”和“雪”)，而难以发明负面关联 (比如“加拿大”和“沙漠”)。所以两个单词的相似度受它们共同的正面上下文的影响要大于它们的共同负面上下文的影响。于是抛弃那些负关联的上下文而简单把这些矩阵元标记为 0。

_{一个值得注意的例外是语义相似度的情形。比如，所有动词之前都不大可能有限定词，以及所有过去时态的动词之前都不大可能有“be”。}

\(M_0^\text{PMI}\) 和 \(M^\text{PPMI}\) 在自然语言处理领域是众所周知的。对各种单词-上下文关联度量的定量比较表明，PMI，特别是 PPMI，在大量单词相似度任务上表现最佳。所以，PMI 矩阵以 SGNS 优化目标的最优解的面目出现还是很有意思的。

4. 其它单词表示

SGNS 在 \(k=1\) 的情形是要隐式分解 \(M^\text{PMI}\) 这个矩阵，因此，一个自然的想法是，用 \(M^\text{PPMI}\) 的行来直接计算单词相似度。虽然 \(M^\text{PPMI}\) 是 \(M^\text{PMI}\) 的近似，它仍然可以让目标函数很接近最优值。本节提出另两种基于 \(M^\text{PPMI}\) 的单词表示方法。

4.1 平移的 PPMI

PMI 来自 SGNS 的 \(k=1\) 的情形，而不同的 \(k\) 会显著提高嵌入结果。关联度量是 \(\text{PMI}(w,c) - \log k\)，这意味着可以采用 Shifted PPMI (SPPMI) \[ \text{SPPMI}_k(w,c) = \max(\text{PMI}(w,c) - \log k, 0). \] 这种方法在 NLP 和单词相似度社区似乎还没被研究过。

4.2 谱降维：SVD 比 SPPMI 好

虽说稀疏矢量表示表现良好，使用稠密低维矢量还是有优势的，比如可以提高计算效率，以及更好的一般性。 一种与 SGNS 的随机梯度下降算法不同的矩阵分解方法是截断“奇异值分解” (truncated Singular Value Decomposition; SVD)。这是线性代数里针对 \(L_2\) 损失的秩为 \(d\) 的最优分解算法。SVD 把矩阵 \(M\) 分解为三个矩阵的乘积，\(U\cdot\Sigma\cdot V^\mathsf{T}\)，这里 \(U\) 和 \(V\) 是正交矩阵，而 \(\Sigma\) 是奇异值组成的对角矩阵。以 \(\Sigma_d\) 表示顶部 \(d\) 个奇异值组成的对角矩阵，\(U_d\) 和 \(V_d\) 表示从 \(U\) 和 \(V\) 选择相应的列组成的矩阵。则矩阵 \(M_d = U_d\cdot\Sigma_d\cdot V_d^\mathsf{T}\) 是秩为 \(d\) 的矩阵里对原矩阵 \(M\) 近似最好的，在 \[ M_d = \text{argmin}_{\text{Rank}(M')=d} ||M'-M||_2 \] 这种意义上。

奇异值分解

当线性方程或矩阵

矩阵 \(W=U_d\cdot\Sigma_d\) 两行的内积与 \(M_d\) 两行的内积相等，这是由于 \(V\) 是正交矩阵。在考虑单词-上下文矩阵时，矩阵 \(W\) 的稠密的 \(d\) 维行向量是 \(M_d\) 的极高维行向量的完美替代。其实在 NLP 领域另一种常见办法是，用 SVD 分解 \(M^\text{PPMI}\) 矩阵，然后用 \(W^\text{SVD} = U_d\cdot\Sigma_d\) 以及 \(C^\text{SVD} = V_d\) 的行向量作为单词和上下文的表示。只不过，使用 \(W^\text{SVD}\) 作为单词表示在语义任务上一致地不如从 SGNS 得到的 \(W^\text{SGNS}\) 嵌入好。

对称 SVD 注意到通过 SVD 得到的单词和上下文矩阵性质很不同。比如，上下文矩阵是正交的而单词矩阵不是。另一方面，SGNS 训练给出的分解要对称许多，在两者的矩阵都不是正交矩阵这个意义上；并且训练中没有对两个矩阵有任何偏向。因此提议一种类似的对称分解： \[ W^{\text{SVD}_{1/2}} = U_d\cdot\sqrt{\Sigma_d},\quad C^{\text{SVD}_{1/2}} = V_d\cdot\sqrt{\Sigma_d}. \] 虽说理论上并不清楚，但实际上这样对称化的矩阵的确在语义任务上表现好很多。这里的 \(1/2\) 指数还可取成别的，因此变得可调节。不同的值有可能表现得更好。

SVD 与 SGNS 的比较 谱算法相对随机梯度训练有两个计算上的优势。一是，它是精确的，不需要去调节学习速率和其它超参数。第二，它可以通过计数数据 (即 \(\{(w,c,\#(w,c))\}\) 这样的三元组集合) 来训练，这让它相对 SGNS 而言可以应用于更大的语料库。SGNS 要求每个观测 \((w,c)\) 单独出现。

另一方面，随机梯度法也有优势：相对 SVD 而言，它对已观测和未观测事件做了区分；已经知道 SVD 受未观测值的影响较大，而这在单词-上下文矩阵中是常见的。更重要的是，SGNS 的目标函数给了不同的 \((w,c)\) 对不同的权重，观测次数多的权重较高，而低的则允许更多误差。可惜，精确的加权 SVD 计算困难。最后，由于 SGNS 只在乎观测到 (以及采样到) 的 \((w,c)\) 对，它不需要背后的矩阵是稀疏的，这让分解稠密矩阵 (比如精确的 \(\text{PMI}-\log k\) 矩阵) 称为可能。这在 SVD 是不可能的。

SGNS 和 SVD 之间有个有趣的中间地带，那就是随机矩阵分解 (stochastic matrix factorization; SMF) 方法的运用。这方法在协作过滤领域是常见的。与 SVD 不同，SMF 不是精确的，并且需要超参数调节，但 SMF 在处理未观测值方面比 SVD 好，并且可以实现重要性权重，这就跟 SGNS 很像。但是，就像 SVD 而不像 SGNS，SMF 可以直接工作在 \(\{(w,c,f(w,c))\}\) 三元组上，这就让优化目标更加直接，且能用于更大的语料库。SMF 相对 SVD 和 SGNS 还有别的优势，比如正规化化 (regularization)，这导致一些可能的改进。作者说以后再研究这个。

5. 实验结果

从两个方面比较基于矩阵的算法和 SGNS 算法。首先看每个方法对目标函数的优化程度，然后看它们在不同语言学任务上的表现。作者发现对有些任务而言对目标函数优化得好跟在任务上表现得好是两码事。

实验设置 所有模型都用英文维基百科训练。事先去掉了非文字元素，做了分句和分词。 语料库包含 77.5M 个句子，1.5B 个词。 所有上下文通过焦点单词左右两侧宽度为 2 的窗口得到。出现次数少于 100 的单词忽略。 最后，词汇表包含 189533 个单词和上下文。 训练 SGNS 模型用的是修改过的 word2vec, 这个软件的输入是事先提取出的单词-上下文对。 试验了三种 \(k\) 值，1，5，15。 对 SVD，采用了对称方法。

5.1 对目标函数的优化

用目标函数的解析表达式（即关于全局目标函数的表达式）来量化每个算法对目标函数的优化程度。 最优情形是让 \(\vec{w}\cdot\vec{c} = \text{PMI}(w,c) - \log k\) 的情形， 此时目标函数的值 \(l_\text{opt}\) 作为评判基准。

作者发现 SPPMI 对最优解的近似接近完美，尽管当只考虑正矩阵元时丢掉了许多信息。对于矩阵分解方法，增加维度导致更好的结果，这是预料中的。当 \(d\le500\) 且 \(k=1\) 时 SVD 比 SGNS 优化得稍微好点。但是，SGNS 可以通过采用更高维度来降低误差，而 SVD 就不行。并且，当 \(k\) 增加时 SVD 会变得很糟糕。作者猜测这是由于 \(k\) 增加时矩阵的零元素越来越多，而 SVD 的 \(L_2\) 目标函数是无权重的，且不区分观测到的和未观测的元素，导致 SVD 倾向于用很接近零的矩阵来分解。

5.2 单词表示在语言学任务上的表现

语言学任务和数据集 使用了四个数据集，测试了单词相似度和关系类比任务。用 Finkelstein 等人的 WordSim353 和 Bruni 等人的 MEN 来测试两两单词相似性。这两个数据集的单词对有人工赋予的相似度分数。用单词矢量对的 cosine 相似度与人工相似度之间的相关系数 ()Spearman's \(\rho\) 来评价。

两个类推数据集提供“a 之于 a* 就像 b 之于 b*”这样的问题，这里 b* 是未知的，需要从整个词汇表中去找。Syntactic 数据集包含 8000 个形态-语义类推问题，比如“good is to best as smart is to smartest”。Mixed 数据集包含 19544 个问题，其中约半数跟 Syntactic 里的类似，剩下的更强调语义，比如“巴黎之于法国就像东京之于日本”这样的问题。过滤掉不在词汇表里的问题后，Syntactic 里的问题还剩下 7118 个，而 Mixed 里的还剩下 19258 个。类推问题通过 Levy 和 Goldberg 的相似度乘积算法来回答：\(\text{argmax}_{b*\in V_{W\backslash\{a*,b,a\}}} \cos(b*,a)\cdot\cos(b*,b)/(\cos(b*,a) + \epsilon)\)。评价方法就是看谁给出的正确答案多。

结果 在单词相似度任务上，SPPMI 的结果比 SGNS 好，而 SVD 进一步提高。但基于 PMI 的最佳方法与最佳 SGNS 配置给出的结果差异不大，基本打成平手。不同的 \(k\) 值对所有方法的结果都有显著影响：SGNS 用较大的 \(k\) 比较好，而 SPPMI 和 SVD 用较小的 \(k\) 比较好。这可能是因为 \(k\) 越大，丢掉的信息越多（因为只保留了正矩阵元）。通过调节 \(k\) 可以让 SPPMI 比传统的 PPMI 好很多。

类推任务上表现就不一样了。首先，SVD 不如 SGNS 和 SPPMI。有趣的是，在语义类比数据集上 SGNS 比别的都好。当使用加性类推恢复方法时这点更明显。从语言学上讲，语义类推数据集跟其它数据集很不一样，因为它对常见单词提供的上下文信息依赖更多。作者猜测 SGNS 表现得好是因为其训练机制让频繁出现的对影响更大，而 SVD 方法中所有矩阵元权重相等。

6. 结论

作者分析了 SGNS 单词嵌入算法，发现这算法背后是在对单词-上下文的 PMI 矩阵 \(M^\text{PMI} - \log k\) 用随机梯度下降的方法做分解。作者基于他们自己过去的发现提出了 SPPMI 方法，发现这方法比传统 PPMI 矩阵好。但是，尽管 SPPMI 对 SGNS 的目标函数优化得更好，但它在语言学任务上的表现并不一定更好，特别是在语义类推任务上。作者猜测这是由于 SGNS 降低了罕见单词的权重，而基于 PMI 的方法会夸大。

作者还试验了 SVD 方法。尽管 SVD 在优化 SGNS 的目标函数上表现很差，但在单词相似度任务上比别的要稍微好点。可是 SVD 在单词类推任务上不行。SVD 与 SGNS 的一个主要差异是， SGNS 进行的是加权矩阵分解。这可能是它在单词类推任务上领先的原因。今后的工作是研究怎么对基于 PMI 的关联矩阵进行加权矩阵分解。