NLP

Word2Vec之 预备知识

由于工作中有需要计算句子的相似度，有用到Word2Vec算法，就去研究了下；后来用LibSVM做情感分析时又需要用到Word2Vec，这时发现之前看的时候没有做笔记，回过头来再去看的时候，又有点模糊了，所以这里对Word2Vec算法做一下总结

预备知识

要理解word2vec，大致需要了解sigmoid函数、贝叶斯公式、逻辑回归、Hafuman树等基础知识，下面会讲解一下sigmoid函数和Hafuman树

Sigmoid函数

Sigmoid函数是神经网络中常用的激活函数之一，定义为

$$\sigma(x) = \frac{1}{1 + e^{-x}}$$
其中，$x \in (-\infty,+\infty)$，值域为 $(0,1)$.

---

下面给出 R 画图代码:

x <- seq(-10,10,0.05)
y <- 1/(1 + exp(-x))
plot(x,y,'p',main = "sigmoid函数",)

---

Sigmoid函数的导函数具有如下形式：

$$\sigma'(x) = \sigma(x) \left[ 1 - \sigma(x) \right]$$ 这是一个非常好的性质，因为导函数的值就能直接通过原函数来求得.

由此易得，函数 $log{\sigma(x)}$ 和 $log{(1 - \sigma(x))}$ 的导函数分别为:

$$\left[ log{\sigma(x)} \right]' = 1 - \sigma(x) , \left[ log{(1 - \sigma(x))} \right]' = -\sigma(x)$$

$\sigma'(x) = \left( \frac{1}{1 + e^{-x}} \right)' = \left( -1 \times \frac{1}{(1 + e^{-x})^2} \right) \left( 1 + e^{-x} \right)' \\\ \ \ \ = \left( -1 \times \frac{1}{(1 + e^{-x})^2} \right) \times e^{-x}(-1) \\\ \ \ \ = \frac{1}{1 + e^{-x}} \times \frac{e^{-x}}{1 + e^{-x}} \\\ \ \ \ = \sigma(x) \times (1 - \sigma(x)$

---

Huffman树

Huffman树是由Huffman编码生成；核心思想就是让出现频率较高的元素具有较短的编码，出现频率较低的元素具有较长编码，这样整体集合的编码长度就比较短了，因为集合中大部分都是出现频率较高的元素.

---

树的基本概念

• 路径和路径长度
  在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径.通路中分支的数目称为路径长度.
  若规定根结点的层号为 1，则从根结点到第 $L$ 层结点的路径长度为 $L - 1$

• 结点的权和带权路径长度
  若为树中结点赋予一个具有某种含义的(非负)数值，则这个数值称为该结点的权.
  结点的带权路径长度是指，从根结点到该结点之间的路径长度与该结点的权的乘积.

• 树的带权路径长度
  树的带权路径长度规定为所有叶子结点的带权路径长度之和.

---

Huffman树的构造

给定 $n$ 个权值 $\{\omega_1,\omega_2,\cdots,\omega_n\}$ 作为二叉树的 $n$ 个叶子结点，可通过以下算法来构造一颗 Huffman 树.

算法描述:

1. 将 $\{\omega_1,\omega_2,\cdots,\omega_n\}$ 看成是有 $n$ 棵树的森林（每棵树仅有一个结点）

2. 在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和

3. 从森林中删除选取的两棵树，并将新树加入森林

4. 重复 2, 3 步，直到森林中只剩一棵树为止，该树即为所求的 Huffman 树

---

自然语言背景知识

word2vec 是用来生成词向量的工具，而词向量与语言模型有着密切的关系，所以我们先介绍一下语言模型和词向量的概念.

统计语言模型

进入大数据时代，互联网上每天都会生成大量的语音、文本、图片、视频等数据，而要让计算机自动理解这些数据，自然语言处理(Nature Language Processing)必不可少，其中统计语言模型(Statistical Language Model)是所有 NLP 的基础，被广泛应用于语音识别、机器翻译、分词、词性标注和信息检索等任务.

举个例子: 在语音识别系统中，对于给定的语音段 Voice，需要找到一个使概率 $p(Text | Voice)$ 最大的文本段 Text，利用 Bayes 公式，有

$$p(Text | Voice) = \frac{p(Voice | Text) \cdot p(Text)}{p(Voice)}$$
其中 $p(Voice | Text)$ 为声学模型，而 $p(Text)$ 为语言模型.

---

简单地说，统计语言模型是用来计算一个句子的概率的概率模型，它通常基于几个语料库来构建.一个句子的概率是什么呢？

假设 $W = (\omega_l^T) = (\omega_1,\omega_2,\cdots,\omega_T)$ 表示由 $T$ 个词 $\omega_1,\omega_2,\cdots,\omega_T$ 按顺序构成的一个句子，则 $\omega_1,\omega_2,\cdots,\omega_T$的联合概率

$$p(W) = p(\omega_l^T) = p(\omega_1,\omega_2,\cdots,\omega_T)$$
这就是这个句子的概率.利用 Bayes公式，上式可以被链式地分解为 $$p(W) = p(\omega_1) \cdot p(\omega_2 | \omega_l^1) \cdot p(\omega_3 | \omega_l^2) \cdots p(\omega_T | \omega_l^{T-1})$$
其中的条件概率 $p(\omega_1) , p(\omega_2 | \omega_l^1) , p(\omega_3 | \omega_l^2) , p(\omega_T | \omega_l^{T-1})$就是语言模型的参数.若这些参数已经全部算得，那么给定一个句子 $W$，就可以很快地算出相应的 $p(W)$了.

这些参数的计算，常用的方法有 n-gram 模型、决策树、最大熵模型、最大熵马尔科夫模型、条件随机场、神经网络等方法.

---

n-gram 模型

考虑 $p(\omega_k | \omega_l^{k-1}), k > 1$ 的近似计算.利用 Bayes公式，有

$$p(\omega_k | \omega_l^{k-1}) = \frac{p(\omega_l^k)}{p(\omega_l^{k-1})}$$
根据大数定理，当语料库足够大时，$p(\omega_k | \omega_l^{k-1})$ 可近似地表示为 $$p(\omega_k | \omega_l^{k-1}) \approx \frac{count(\omega_l^k)}{count(\omega_l^{k-1})}$$
其中 $count(\omega_l^k)$ 和 $count(\omega_l^{k-1})$ 分别表示词串 $\omega_l^k$ 和 $\omega_l^{k-1}$ 的统计将会多么耗时.

---

从上式可以看出：一个词出现的概率与它前面的所有词都相关.如果假定一个词出现的概率只与它前面固定数目的词相关呢？这就是 n-gram模型 的基本思想，它作了一个 $n - 1$ 阶的 Markov 假设，认为一个词出现的概率就只与它前面的 $n - 1$ 个词相关，即:

$$p(\omega_k | \omega_l^{k-1}) \approx p(\omega_k | \omega_{k-n+1}^{k-1})$$
于是有 $$p(\omega_k | \omega_l^{k-1}) \approx \frac{count(\omega_{k-n+1}^k)}{count(\omega_{k-n+1}^{k-1})}$$
以 $n = 2$ 为例，就有 $$p(\omega_k | \omega_l^{k-1}) \approx \frac{count(\omega_{k-1},\omega_k)}{count(\omega_{k-1})}$$
这样简化后，不仅使得单个参数的统计变得更容易，也使得参数的总数变少了.

从计算复杂度和模型效果方面去考虑，实际应用中最多采用 $n = 3$的三元模型.

尽管理论上 n 越大越好.但是需要注意到的是，当 n 大到一定程度时，模型效果的提升幅度会变小.而模型参数的量级是词典大小 N的指数函数 ($O(N^n)$).

---

对于统计语言模型而言，利用最大似然，可把目标函数设为:

$$\prod_{\omega \in C}{p(\omega | Context(\omega))}$$ 其中 $C$ 表示语料(Corpus)，$Context(\omega)$ 表示词 $\omega$ 的上下文(Context)，即 $\omega$ 周边的词的集合.当 $Context(\omega)$ 为空时，就取 $p(\omega | Context(\omega)) = p(\omega)$.特别地，对于前面介绍的 n-gram模型，就有 $Context(\omega_i) = \omega_{i-n+1}^{i-1}$.

连乘形式的函数值不好求，所以在实际应用中，一般使用最大对数似然，把目标函数变为:

$$L = \sum_{\omega \in C}{log{p(\omega | Context(\omega))}}$$ 然后对这个函数进行最大化.

其中，概率 $p(\omega | Context(\omega))$ 已被视为关于 $\omega$ 和 $Context(\omega)$ 的函数，即

$$p(\omega | Context(\omega)) = F(\omega,Context(\omega),\theta)$$ 其中 $\theta$ 为待定参数集.这样一旦进行优化得到最优参数集 $\theta^*$ 后，$F$也就唯一被确定了，以后任何概率 $p(\omega | Context(\omega))$ 就可以通过函数 $F(\omega,Context(\omega),\theta^*)$ 来计算了.

与 n-gram 相比，这种方法不需要事先计算并保存所有的概率值，而是可以通过直接计算函数 $F$ 来获得，且选取合适的模型可使得 $\theta$ 中参数的个数远小于 n-gram 中模型参数的个数.

这时模型设计的重点就变成了如何构造函数 $F$，并训练出最优参数集 $\theta^*$

---

神经概率语言模型

神经概率语言模型本质上是神经网络，关于神经网络的具体讲解可参考之前写的机器学习之神经网络一篇，这里不再赘述.

对于语料 $C$ 中的任意一个词 $\omega$，将 $Context(\omega)$ 取为其前面的 $n-1$ 个词，这样二元对 $(Context(\omega),\omega)$就是一个训练样本了.接下来讨论样本$(Context(\omega),\omega)$经过神经网络时是如何参与运算的.

注意，一旦语料 $C$ 和词向量长度 m 给定后，投影层和输出层的规模就确定了，前者为 $(n-1)m$，后者为 $N = |D|$ 即语料 $C$ 的词汇量大小.而隐藏层的规模 $n_h$ 是可调参数由用户指定.

为什么投影层的规模是 $(n-1)m$ 呢？因为输入层包含 $Context(\omega)$ 中 $n-1$ 个词的词向量，而投影层的向量 $X_{\omega}$ 是这样构造的：将输入层的 $n-1$ 个词向量按顺序首尾相接地拼起来形成一个长向量，其长度当然就是 $(n-1)m$了.有了向量 $X_{\omega}$，接下来的计算过程就如一般神经网络的训练过程一样了，具体为:

$$\begin{cases} X_{\omega} = tanh(W X_{\omega} + p) \\ Y_{\omega} = U Z_{\omega} + q \end{cases}$$ 其中 tanh 为双曲正切函数，用来做隐藏层的激活函数.

这里 tanh()函数是作用在向量的每一个分量上

若当前词的前面不足 $n-1$ 个词，可以人为添加一个(或几个)填充向量，它们也参与训练过程

经过上述两步计算得到的 $Y_{\omega} = (y_{\omega,1},y_{\omega,2},\cdots,y_{\omega,N})^T$ 只是一个长度为 $N$ 的向量，其分量不能表示概率.如果想要 $Y_{\omega}$ 的分量 $y_{\omega,i}$ 表示当上下文为 $Context(\omega)$ 时下一个词恰为词典 $D$ 中第 $i$ 个词的概率，则还需要做一个 softmax 归一化，归一化后 $p(\omega|Context(\omega))$ 就可以表示为

$$p(\omega | Context(\omega)) = \frac{e^{y_{\omega,i_{\omega}}}}{\sum_{i=1}^N{e^{y_{\omega,i}}}}$$ 其中 $i_{\omega}$ 表示词 $\omega$ 在词典 $D$ 中的索引.

---

词向量

这里对词向量做一个简单的介绍。在 NLP 任务中，我们将自然语言处理用机器学习算法来处理，但机器无法直接理解人类的语言，就需要把人类的语言（语音，文本）数学化，词向量就是一种解决办法.

一种最简单的词向量是 one-hot representation，就是用一个很长的向量来表示一个词，向量的长度为词典 $D$ 的大小 $N$，向量的分量只有一个 1，其它全为 0，1 的位置对应该词在词典中的索引.这种词向量表示有个缺点，就是容易产生维数灾难，尤其是讲其用于 Deep Learning 场景时；另外，它不能很好地刻画词与词之间的相似性.

另一种词向量是 Distributed Representation，它的做法是通过训练将某种语言中的每个词映射成一个固定长度的短向量（这个"短"是相对于one-hot representation 来说的，数量级一般在 $10^1 到 10^2$），所有这些向量构成一个词向量空间，而每一向量则可视为该空间中的一点，在这个空间上引入"距离"，就可以根据词之间的距离来判断它们之间的（词法、语义上的）相似性了.

word2vec 中就是采用的 Distributed Representation 词向量方式，具体如何操作，在后面会介绍.

---

word2vec模型介绍

word2vec 中有两个重要的模型——CBOW(Continuous Bag-of-Words Model) 模型 和 Skip-gram(Continuous Skip-gram Model) 模型.

从图中可知，两个模型都包含三层：输入层、投影层和输出层. CBOW模型是在已知当前词 $\omega_t$ 的上下文 $\omega_{t-2},\omega_{t-1},\omega_{t+1},\omega_{t+2}$的前提下预测当前词 $\omega_t$；而 Skip-gram模型却是在已知当前词 $\omega_t$ 的前提下，预测上下文 $\omega_{t-2},\omega_{t-1},\omega_{t+1},\omega_{t+2}$.

对于 CBOW 和 Skip-gram 两个模型，word2vec 给出了两套框架，它们分别基于 Hierarchical Softmax (分层softmax)和 Negative Sampling (负采样) 来进行设计.

---

在前面的神经网络语言模型中提到，目标函数取对数似然函数

$$L = \sum_{\omega \in C}{log{p(\omega | Context(\omega))}}$$ 其中的关键是条件概率函数 $p(\omega | Context(\omega))$ 的构造.

对于 word2vec 中基于 Hierarchical Softmax 的 CBOW 模型，优化的目标与上式类似；而对于基于 Hierarchical Softmax 的 Skip-gram 模型，优化的目标函数形如:

$$L = \sum_{\omega \in C}{log{p(Context(\omega) | \omega)}}$$
因此，讨论过程中我们应将重点放在 $p(\omega | Context(\omega))$ 或 $p(Context(\omega) | \omega)$ 的构造上.