1. 基本符号定义
- w：词库中的单词;
- Context(w): 特定句子中w的上下文;
- v(w): w的词向量，即最终结果;
- m: 词向量的维数;
- C: 语料;
- D: 词库。
2. Hierarchical Softmax
2.1 CBOW
2.1.1 预处理和符号定义
对于语料中的每一个单词w，取在其之前的c个单词和之后的c个单词作为Context(w)，将数据保存为二元组形式(w, Context(w))。
对于语料中的所有单词，按照出现频率构建哈夫曼树，使得频率较高的单词距离根节点较近，频率较低的单词距离根节点较远。
对于哈夫曼树，每个叶节点与一个单词对应。
对于单词w，有：
- : 从根节点出发到达w对应叶节点的路径
- : 中包含节点的个数
- : 的第i个节点，根节点为第1个节点，叶节点为最后一个节点
- : 中第i个节点对应的哈夫曼编码，根节点不对应编码
2.1.2 优化目标
对于二元组(w, Context(w))，CBOW模型根据Context(w)预测w。
优化目标为最大化对数似然函数 \begin{align} \zeta = \sum\limits_{w\in C} \log p(w|Context(w)) \end{align}
2.1.3 模型
在CBOW模型中，Context(w)在CBOW模型中为2c个单词，将这2c个单词的词向量累加，得到向量。
为了方便后续处理，给扩充一维，数值为1，位置在第一维。
对于单词w，从根节点出发到达该单词代表的叶节点，中间经过的每一个非叶节点，都视为一个逻辑回归二分类器，分类结果对应左右子节点。
约定：分到左边为0类（编码0），分到右边是1类（编码1）。
哈夫曼树的叶节点为所有单词，非叶节点视为一个逻辑回归二分类器。 定义为中第i个节点对应的参数向量，不包括叶节点。 得到 \begin{align} p(w|Context(w))=\prod\limits_{i=2}^{l^w}p(d_i^w|X_w, \theta_{i-1}^w) \end{align}
使用符号g代表sigmoid函数，有
\begin{align} p(d_i^w|X_w, \theta_{i-1}^w) = \left\{ \begin{aligned} 1-g(X_w^T\theta_{i-1}^w) \quad & d_i^w = 0 \\ g(X_w^T\theta_{i-1}^w) \quad & d_i^w = 1 \end{aligned} \right. \end{align}
为了方便，上式变形为
\begin{align} p(d_i^w|X_w, \theta_{i-1}^w)=[1-g(X_w^T\theta_{i-1}^w)]^{1-d_i^w}[g(X_w^T\theta_{i-1}^w)]^{d_i^w} \end{align}
2.1.3 梯度
将上式代入到优化目标中，得到
\begin{align} \zeta=\sum\limits_{w\in C}\sum\limits_{i=2}^{l^w}{(1-d_i^w)log[1-g(x_w^T\theta_{i-1}^w)]+d_i^wlog[g(x_w^T\theta_{i-1}^w)]} \end{align}
令 \begin{align} J={(1-d_i^w)log[1-g(x_w^T\theta_{i-1}^w)]+d_i^wlog[g(x_w^T\theta_{i-1}^w)]} \end{align} 求导，得
\begin{align} \frac{\sigma J}{\sigma \theta_{i-1}^w} &= [d_i^w-g(x_w^T\theta_{i-1}^w)]X_w \\ \frac{\sigma J}{\sigma X_w} &= [d_i^w-g(x_w^T\theta_{i-1}^w)]\theta_{i-1}^w \end{align}
2.2 Skip-gram
2.2.1 预处理和符号定义
同CBOW。
2.2.2 梯度
对于二元组(w, Context(w))，Skip-gram模型根据w预测Context(w)。
优化目标为最大化对数似然函数 \begin{align} \zeta = \sum\limits_{w\in C} \log p(Context(w)|w) \end{align}
其中
\begin{align} p(Context(w)|w) = \prod\limits_{u\in Context(w)}p(u|w) \end{align}
且
\begin{align} p(u|w)=\prod\limits_{i=2}^{l^u}p(d_i^u|v(w),\theta_{i-1}^u)=\prod\limits_{i=2}^{l^u}[1-g({v(w)}^T\theta_{i-1}^u)]^{1-d_i^u}[g({v(w)}^T\theta_{i-1}^u)]^{d_i^u} \end{align}
回代得到
\begin{align} \zeta=\sum\limits_{w\in C}\sum\limits_{u\in Context(w)}\sum\limits_{i=2}^{l^u}(1-d_i^u)log[1-g({v(w)}^T\theta_{i-1}^u)]+d_i^ulog[g({v(w)}^T\theta_{i-1}^u)] \end{align}
令
\begin{align} J = (1-d_i^u)log[1-g({v(w)}^T\theta_{i-1}^u)]+d_i^ulog[g({v(w)}^T\theta_{i-1}^u)] \end{align}
求导
\begin{align} \frac{\sigma J}{\sigma \theta_{i-1}^u} &= [d_i^u-g({v(w)}^T\theta_{i-1}^u)]v(w) \\ \frac{\sigma J}{\sigma v(w)} &= [d_i^u-g({v(w)}^T\theta_{i-1}^u)]\theta_{i-1}^u \end{align}
3. Negative Sampling
3.1 CBOW
根据Context(w)预测w，对于给定的二元组(w, Context(w))，这是一个正样本，其余的词就是负样本。
由于负样本数量较大，只选取其中的一个子集，具体的选取在3.3节中讲述。
假设对于w有一个选取好的负样本集NEG(w)。
Negative Sampling没有哈夫曼树，重新定义符号。
为词w对应的一个辅助向量，为待训练参数。
定义为当上下文为Context(w)时，预测中心词为u的概率。
最大化目标函数为
\begin{align} \zeta=\sum\limits_{w\in C}\left\{log[g(X_w^T\theta^w)]+\sum\limits_{u\in NEG(w)}log[1-g(X_w^T\theta^u)]\right\} \end{align}
使上式最大化，也就是最大化正样本概率的同时最小化负样本概率。
令
\begin{align} J=log[g(X_w^T\theta^w)]+\sum\limits_{u\in NEG(w)}log[1-g(X_w^T\theta^u)] \end{align}
求导，得
\begin{align} \frac{\sigma J}{\sigma X_w} &= [1-g(X_w^T\theta^w)]\theta^w-\sum\limits_{u\in NEG(w)}g(X_w^T\theta^u)\theta^u \\ \frac{\sigma J}{\sigma \theta^w} &=[1-g(X_w^T\theta^w)]X_w \\ \frac{\sigma J}{\sigma \theta^u} &= -g(X_w^T\theta^u)X_w \end{align}
3.2 Skip-gram
优化目标 \begin{align} \zeta=\sum\limits_{w\in C}\sum\limits_{u\in Context(w)}\left\{log[g({v(w)}^T\theta^u)]+\sum\limits_{z\in NEG(u)}log[1-g({v(w)}^T\theta^z)]\right\} \end{align}
3.3 负采样算法
带权采样，语料中的频率越大，词的选取概率越大。 Google的word2vec中的概率为
\begin{align} \frac{counter(w)^{\frac{3}{4}}}{\sum\limits_{u\in D}counter(u)^{\frac{3}{4}}} \end{align}