Word2Vec

Written by    20:43 October 28, 2018 

Word2Vec算法是NLP领域一个里程碑式的工作,它可以通过训练把文本内容映射到一个K维的向量,这样就很方便继续在其他一些算法领域里面使用,比如推荐系统或者广告点击率预估等等。它是在2013年由当时还在Google工作的Tomas Mikolov发表,主要两篇论文是《Distributed Representations of Words and Phrases and their Compositionality》和《Efficient Estimation of Word Representations in Vector Space》.

N-gram

Word2vec主要是通过词的上下文来学习词的表征含义,所以在预处理训练数据的时候,采用了n-gram语言模型,即将一个词前后2n个词作为训练数据,如下图所示就是n=2时的情形:

其实n-gram本身就可以用来构建一个词与词之间的矩阵,用来表示每一个词与上下文之间的关系,比如下图就是一个n=1时候的n-gram词矩阵:

但是当词很多的时候,虽然也可以用到矩阵分解等方法,但是计算的时空复杂度还是比较大,应用不是很方便。

CBOW

Continuous Bag of Words Model 简称CBOW,是Word2Vec的网络模型的一种,其网络结构主要如下图:

左边是选定词的上下文,即n-gram中前后n个词,中间是隐藏层,最右边就是中间词,V是词表大小,N是选定的向量维度,简单来看就是用上下文来预测词本身。具体算法如下,其中窗口大小为m,向量维度为n, n,词的总个数为\(\vert V \vert\):

  1. 用one-hot编码生成2n个向量:
    \((x^{(c-m)}, … , x^{(c-1)}, x^{(c+1)}, … , x^{(c+m)})\)
  2.  基于步骤1初始化生成的2n个向量,乘上输入矩阵\(\mathcal{V} \in \mathcal{R^{n \times \vert V \vert}}\):
    \( ( \mathcal{v}_{(c-m)}=\mathcal{V}x^{(c-m)}, \mathcal{v}_{(c-m+1)}=\mathcal{V}x^{(c-m+1)}, …, \mathcal{v}_{(c+m)}=\mathcal{V}x^{(c+m)} )\)
  3.  对所有的向量取平均,得到:
    \(\hat{\mathcal{v}}=\frac{\mathcal{v}_{c-m}+\mathcal{v}_{c-m+1}+ … + \mathcal{v}_{c-m} }{2m}\)
  4.  然后乘上一个输出层矩阵\(\mathcal{U} \in \mathcal{R^{n \times \vert V \vert}}\)得到:
    \( z = \mathcal{U}\hat{\mathcal{v}}\)
  5.  对结果取一个softmax:
    \(\hat{y} = softmax(z)  \)
  6.  重复迭代使得\(\hat{y}\)接近真实值\(y\),就是中间词的one-hot编码。

确定了迭代过程过后就要确定loss,在Word2Vec里面使用的是交叉熵作为loss,即\(\mathcal{H}(\hat{y}, y)=-y_{i}log y_{i}\),接下来就可以确定优化目标为:

\(\begin{aligned} minimize \mathcal{J} &= -logP(w_{c}|w_{c-m}, …, w_{c-1}, w_{c+1}, …, w_{c+m} \\ &= -logP(u_{c}|\hat{v}) \\ &= -log\frac{ exp(u_{c}^{T} \hat{v}) }{ \sum^{\vert V \vert }_{j=1} exp(u_{j}^{T}\hat{v}) } \\ &= -u^{T}_c\hat{v}+log\sum^{\vert V \vert}_{j=1} exp(u_{j}^{T}\hat{v}) \end{aligned}\)

然后就可以开始用梯度下降来优化计算了。

Skip-gram

Skip-gram则是与CBOW完全相反的一种模型,CBOW用周围词来预测中间词,Skip-gram则是用中间词来预测周围词,其网络模型如下图所示:

其训练过程也与CBOW相似:

  1. 生成一个one-hot编码的向量\(x\)
  2. 乘上输入矩阵\(\mathcal{V} \in \mathcal{R^{n \times \vert V \vert}}\)得到:
    \(v_{c} = \mathcal{V}x\)
  3. 因为这里只有一个向量,所以直接令\(\hat{v} = v_{c} \)
  4.  利用输出层矩阵\(\mathcal{U} \in \mathcal{R^{n \times \vert V \vert}}\), \(u=\mathcal{U}\mathcal{v}_{c}\),得到2m个向量:
    \(u_{c-m}, …, u_{c-1}, u_{c+1}, …, u_{c+m}\)
  5. 对每一个向量取softmax,\(y=softmax(u)\)
  6.  不断迭代使得所求值逼近真实的\(y^{(c-m)}, …, y^{(c-1)}, y^{(c+1)}, …, y^{(c+m)} \)

如同CBOW的目标函数,也使用交叉熵作为loss,稍有不同的是使用了朴素贝叶斯来拆概率计算:

\(\begin{aligned} minimize J &= -logP(w_{c-m}, …, w_{c-1}, w_{c+1}, …, w_{c+m}) \\ &= -log\prod^{2m}_{j=0, j \neq m} P(w_{c-m+j}|w_{c}) \\ &= -log\prod^{2m}_{j=0, j \neq m} P(u_{c-m+j}|v_{c})  \\ &= -log\prod^{2m}_{j=0, j \neq m} \frac{exp(u^{T}_{c-m+j}v_{c})}{\sum^{\vert V \vert}_{k=1}exp(u_{k}^{T}v_{c})} \\ &= -\sum^{2m}_{j=0, j \neq m} u^{T}_{c-m+j}v_{c} + 2m log\sum^{\vert V \vert }_{k=1} exp(u^{T}_{k}v_{c}) \end{aligned}\)

根据作者的建议,Skip-gram一般速度更慢一点,但是对低频词效果更好,而CBOW则训练速度更快一点。

Hierarchical Softmax 和 Negative Sampling

在计算的时候,作者还使用了两个Trick来优化训练速度,第一个是hierarchical softmax,即首先根据词频对词表构建Huffman编码,这样在计算目标函数的时候,\(\sum_{j=1}^{\vert V \vert}\)就变成了\(\sum_{j=1}^{log \vert V \vert}\)了,计算效率大大提高,Word2Vec中,采用了二元逻辑回归的方法,即规定沿着左子树走,那么就是负类(Huffman树编码1),沿着右子树走,那么就是正类(Huffman树编码0),一开始我纠结了半天的Huffman中的非叶子节点意义是什么,但是关键在于Huffman树有用的只是叶子节点,那些非叶子节点可以看成一个隐变量,不需要管实际意义是什么,词频越高的词层数越高,也更容易被学到,这个也符合我们的需求。

第二个则是Negative Sampling,就是随机添加负样本,词频越高的词也更容易被采样到添加负样本,这样其实就是相当于给了低频词更多出场机会,然后打压一下高频词,使得表征意义更为丰富。

Sub-sampling

除了hierarchical softmax和negative sampling,Word2Vec也用到了NLP中常用的sub-sampling来加速训练,选定概率\(P=1-\sqrt{\frac{sample}{freq(w)}}\)来随机删掉一些词,类似于”the”, “a”等等,这些词一般出现频率比较高但是意义不大。

Reference

  1. Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013). Distributed Representations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems.
  2. Mikolov, T., Corrado, G., Chen, K., & Dean, J. (2013). Efficient Estimation of Word Representations in Vector Space. Proceedings of the International Conference on Learning Representations (ICLR 2013).
  3. 邓澍军、陆光明、夏龙,《Deep Learning 实战之 word2vec》
  4. http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model
  5. https://cs224d.stanford.edu/lecture_notes/notes1.pdf
  6. https://www.cnblogs.com/pinard/p/7243513.html
  7. https://www.cnblogs.com/pinard/p/7249903.html

 

 

Category : study

Tags :