0%

Glove Embedding - Mathematical Derivation


  • 记录一下Glove词向量的数学推导,因为原论文不是画模型得出的,而是纯数学操作计算得到的目标函数,这种设计方式非常有意思,而且还将word2vec的数学本质写出来进行了对比。
  • 原论文:GloVe: Global Vectors for Word Representation

词向量

  • 无论是基于全局矩阵分解的还是基于局部窗口的词向量,其提取semantic的方式都是从词与词的共现统计信息中挖掘意义。
  • 显然,全局的方式没有利用到局部的优点:全局例如LSA等技术对于局部上下文信息不敏感,难以根据上下文挖掘近义词;局部的方式没有利用到全局的优点,它只依赖于独立的局部上下文,窗口太小的话不能有效利用整个文档乃至语料的信息。
  • Glove的思路是利用全局的词与词共现矩阵,同时利用局部上下文关系计算相关性。
  • 词向量的结果是能产生有意义的语义关系到距离关系的映射,针对这个目标,Glove设计了一个log-bilinear回归模型,并具体采用一个加权最小均方回归模型来训练词向量。

发现

  • 定义:
    • \(x\):为单个词。
    • \(X_{ij}\)\(x_j\) 出现在\(x_i\)的上下文中的次数。
    • \(X_i = \sum _k x_{ik}\):所有词出现在\(x_i\)的上下文中的次数。
    • \(P_{ij} = P(j|i) = \frac {x_{ij}} {X_i}\)\(x_j\)出现在\(x_i\)的上下文中的概率,即上下文出现频次计数概率化,论文中称之为"co-occurrence probabilities"。
    • \(r = \frac {P_{ik}}{P_{jk}}\):引入中间词\(x_k\),论文中叫"probe word",通过引入这个\(x_k\)可以间接的衡量\(x_i\)\(x_j\)的关系,通过\(r\)即ratio表示。
  • \(r\)引入的作用体现在两个方面:
    • 对于要比较的\(x_i\)\(x_j\),筛除对于没有区分度的\(x_k\),也就是噪音。当\(r \approx 1\)时,\(x_k\)即为噪音。
    • 给定\(x_k\),使得\(r >> 1\)的那些\(x_i\)具有相近的词义,使得\(r << 1\)的那些\(x_j\)具有相近的词义。
  • 因此,我们可以过滤噪音,仅仅在\(r\)很大或很小的词共现数据中挖掘词义关系。

设计

  • 接下来,作者直接根据目标设计函数。

  • 目标是:设计出来的词向量之间的距离计算结果应该能够反映之前我们从词共现矩阵中发现的ratio,具体而言是对于三元组,词i,j和probe word k,这三个词的词向量能够体现r

  • 那么直接设计,定义\(w_i\)\(x_i\)对应的词向量,则假设\(F\)为计算距离的函数:

    \[ F(w_i,w_j,w^{*}_k) = r \\ = \frac {P_{ik}}{P_{jk}} \\ \]

  • 上面\(w_k\)的词向量加了星号区别于\(w_i\)\(w_j\)的词向量,因为\(w_k\)是独立的上下文词向量,与我们需要的词向量是平行的两套,类似于word2vec里面的前后词嵌入矩阵。

  • 接下来,一个自然的想法是,减少参数,即只需要词向量和上下文词向量,因为是距离计算函数且向量空间是线性空间,我们使用\(w_i\)\(w_j\)的向量差作为参数:

    \[ F(w_i - w_j,w^{*}_k) = \frac {P_{ik}}{P_{jk}} \\ \]

  • 现在函数的参数是向量,输出是张量,最简单的一个结构就是做点乘:

    \[ F((w_i-w_j)^T w^{*}_k) = \frac {P_{ik}}{P_{jk}} \\ \]

  • 接下来的一个关键点:对称。注意到虽然区分了上下文和非上下文词向量,但是由于共现矩阵\(X\)是对称的,因此两套词向量\(w\)\(w^{\*}\)应该具有相同的效果,只是由于随机初始化不同,两套词向量的值不一样,在衡量相似度时应该是一样的目标,即\(w_i^T w^{\*}_j\)\(w_j^T w^{\*}_i\)一样。

  • 由于对称性,\(x_i,x_j,x_k\)可以是语料中任意词,因此\(F\)函数的两个参数应该是可以交换位置(\(w\)\(w^{\*}\)\(X\)\(X^T\)),那这里进一步运用了一点数学技巧将函数对称化:

    • 设计:

      \[ F((w_i-w_j)^T w^{*}_k) = \frac {F(w_i w^{*}_k)} {F(w_j w^{*}_k)} \\ \]

    • 那么分子分母都是一样的形式,即

      \[ F(w_i w^{*}_k) = P_{ik} = \frac {X_{ik}} {X_i} \\ \]

    • 要满足上面\(F\)可以拆分为两个子\(F\)的比,则\(F\)可以为\(exp\)函数,即

      \[ w_i^T w_k^{*} = log(X_{ik}) - log {X_i} \\ \]

    • 这样k,i,j下标可互换位置且表达意思一致。由于分子分母形式一致,因此我们只要关注这个形式能够满足就行了,之后求分数自然会满足从三元组到ratio的映射。

    • 注意到上面式子当中,左边的两个向量内积,i,k符号互换值不变,而右边的两个log式子相减并不满足这种对称,因此我们补上一个\(log{x_k}\)使之对称,并将其简化为偏置\(b^{*}\),同样的道理,i,k符号互换后,补上一个\(Log{x_i}\)使之对称,即偏置\(b_i\),偏置和词向量一样,也是两套:

      \[ w_i^Tw_k^{*} + b_i + b_k^{*} = log(X_{ik}) \\ \]

    • 最后加上平滑,防止log的参数取0:

      \[ w_i^Tw_k^{*} + b_i + b_k^{*} = log(1 + X_{ik}) \\ \]

  • 到这里我们已经初步完成了\(F\)函数的设计,但这个还存在的一个问题是,它是平均加权每一个共现的,而一般语料中大部分共现都频次很低

  • Glove的解决办法是使用加权函数。加权之后将词向量的训练看成是F函数的最小均方误差回归,设计损失函数:

    \[ J = \sum _{i,j}^V f(X_{ij}) (w_i^T w_j^{*} + b_i + b_j^{*} - log (1 + X_{ij}))^2 \\ \]

  • 其中f为加权函数,其参数是共现频次,作者指出该函数必须满足三条性质:

    • \(f(0)=0\):显然,没有出现共现则权重为0。
    • Non-decreasing:共现频次越大则权重越大。
    • relatively small for large X:防止对于某些频次很高的常见共现加权过大,影响结果。
  • 基于以上三种性质,作者设计了截尾的加权函数,在阈值\(X_{max}\)以内:

    \[ f(x) = (\frac {x}{X_{max}}) ^ {\alpha} \\ \]

    超过阈值则函数值为1.

与Word2vec比较

  • 对于Word2vec中的skip-gram模型,其目标是最大化给定上下文之后预测正确中心词的概率,一般通过softmax函数将其概率化,即:

    \[ Q_{ij} = \frac {exp (w_i^T w_j^{*})} { \sum _{k=1}^V exp(w_i^T w_k^{*})} \\ \]

  • 通过梯度下降求解,则整体损失函数可以写成:

    \[ J = - \sum _{i \in corpus , j \in context(i)} log Q_{ij} \\ \]

  • 将相同的\(Q_{ij}\)先分组再累加,得到:

    \[ J = - \sum _{i=1}^V \sum _{j=1}^V X_{ij} log Q_{ij} \\ \]

  • 接下来用之前定义的符号进一步变换:

    \[ J = - \sum _{i=1^V} X_i \sum _{j=1}^V P_{ij} log Q_{ij} \\ = \sum _{i=1}^V X_i H(P_i,Q_i) \\ \]

  • 也就是说,Word2vec的损失函数实际上是加权的交叉熵,然而交叉熵只是一种可能的度量,且具有很多缺点:

    • 需要归一化的概率作为参数
    • softmax计算量大,称为模型的计算瓶颈
    • 对于长尾分布,交叉熵常常分配给不太可能的项太多权重
  • 解决以上问题的方法:干脆不归一化,直接用共现计数,不用交叉熵和softmax,直接用均方误差,令\(Q_{ij} = exp(w_i^T w_j^{*})\)\(P_{ij} = X_{ij}\),则:

    \[ J = \sum _{i,j} X_i (P_{ij} - Q_{ij})^2 \\ \]

  • 但是不归一化会造成数值上溢,那就再取个对数:

    \[ J = \sum _{i,j} X_i (log P_{ij} - log Q_{ij})^2 \\ = \sum _{i,j} X_i (w_i^T w_j^{*} - log X_{ij})^2 \\ \]

  • 这样就得到了Glove最朴素的目标函数。

  • Word2vec的作者发现筛除一些常见词能够提高词向量效果,而Word2vec中的加权函数即\(f(X_i)=X_i\),因此筛除常见词等价于设计一个非降的加权函数。Glove则设计了更为精巧的加权函数。

  • 因此从数学公式推导上看,Glove简化了Word2vec的目标函数,用均方误差替换交叉熵,并重新设计了加权函数。

思路

  • 该文提供了一个很好的设计模型的思路,即根据评测指标设计目标函数,反过来训练模型,得到函数的参数(副产品)作为所需的结果。