词向量
一种简单直观的词表示方法是
统计语言模型
统计语言模型是用来计算一个句子的概率的
句子的概率
给定一个由T个词\(w_1,w_2,…,w_T\)按顺序构成的句子，根据Bayes，计算该句子的概率p(W)
$$p(W) = p(w_1^T) = p(w_1,w_2,…,w_T) = p(w_1)*p(w_2|w_1)*p(w_3|(w_1^2))…p(w_T|(w_1^{T-1}))$$
其中等式中的各个因子（条件概率）就是语言模型的参数，常用的语言模型都是在近似求p(W)。如果给定一个词典大小为N的语料库，考虑长度为T的任意句子，理论上有\(N^T\)种可能组合，而每个句子需要计算T个参数，总共需要计算
n-gram模型
针对参数繁多，该模型做了一个简化的假定，即一个词出现的概率只与它前面的n-1个词相关。实际中最多采用
$$(p(w_k|w^{k-1}_1) = p(w_k|w^{k-1}_{k-n+1}) = \frac{count(w_{k-n+1}^k)}{count(w_{k-n+1}^{k-1})}$$
如果过程中出现\(count(w_{k-n+1}^k)\) = \(count(w_{k-n+1}^{k-1})\) 或者 \(count(w_{k-n+1}^{k-1}) = 0\)，则需要做
n-gram模型的缺陷是无法建模更远的关系，语料的不足使得无法训练更高阶的语言模型；而且无法建模出词之间的相似度。
最大似然
对句子模型的另一种转化是利用机器学习，构造一个目标函数，并最大似然该函数。优化目标求得最优参数，利用最优参数预测未知句子的概率。
其中C表示
$$p(w|Context(w)) = F(w,Context(w),\theta)$$
神经概率语言模型
Bengio(03) - 《A Neural Probabilistic Language Model》
神经网络包含四层：
取
选用双曲正切函数作为隐藏层的激活函数，计算过程为：
$$z_w = tanh(Wx_w + p), y_w = Uz_w + q$$
输出为一个长度为D的向量\(y_w = (y_{w,1}, y_{w,2},…,y_{w,D})^T\)，通过softmax归一化，每个分量表示上下文为Context(w)时下一词为词典第i个词的概率。
关于softmax归一化： 形式为：$$ P(y=i) = \frac{exp(\sum_d w_{id}x_{d})}{\sum_j exp(\sum_d w_{jd} x_{d})} $$ 主要是针对多分类问题，归一化输出概率值。
Word2vec核心
word2vec中用到了两个重要模型:
CBOW和Skip-gram包括三层：
1. CBOW
CBOW = Continuous Bag-of-Words, 目标函数为：
$$\sum_{w \in c} log p(w|Context(w)) = \sum_{t=1}^T log p(w_t|\tau(w_{t-k},w_{t-k-1},…,w_{t+k-1},w_{t+k}))$$
其中T表示整个词典的大小，模型的目标是
Hierarchical Softmax
相比于之前的神经概率语言模型，主要有
问题1：huffman树的应用原理，及hierarchical softmax到底指什么？
hs可以保证叶节点输出的概率值是归一化的。将二叉树中的每个中间结点看作一个隐含的二分类器，一个词的huffman编码就是多个隐含二分类器作用的结果。最后输出层得到的是在当前上下文（输入层）的前提下，各个词的概率，softmax是指这些概率之和为1，即归一化。证明如下：当树的高度为2，即根节点连接两个叶子节点，设左叶子节点的概率为p，则右叶子节点概率为1-p。它们的概率和为1；当树的高度为k时，从根到叶子节点的一个路径可以看成k个独立事件的一种发生可能，所有的叶子节点刚好包括了全部可能情况，概率总和为1。
问题2：简单描述一下模型流程？
根据上图，首先从训练集中选取一个sentence，对于其中的一个词w，计算其上下文词向量的加和，得到\(X_w\)向量(长度为词向量的维度)，即投影层。对于huffman树中的每个非叶子节点，添加一个辅助向量\(\theta\)，\(X_w\)和\(\theta\)层层作用后，可以得到每个叶子节点的概率。计算输出概率与真实值的残差，然后用随机梯度优化参数，使残差尽可能小。在模型训练过程中，可以得到最优参数下的词向量集合。这些词向量就是word2vec。
================================================================
关于模型的
结点的带权路径长度: 从根结点到该结点的路径长度乘以该结点的权值
树的带权路径长度: 所有叶结点的带权路径长度之和
Huffman树是在给定n个叶子结点和其对应权值的前提下，构造一棵二叉树，使该树的带权路径长度最小。已知语料库中各词的词频，可以构建一棵二叉树，每个词作为树的叶子节点，并保证词频越大的词离根节点越近。每个叶子对应的
此外为每个非叶子结点设置一个
对于词w，从根结点到该叶结点的路径中，假设有\(l^w\)层，经历了\(l^w-1\)次二分类，则条件概率\( p(w|Context(w)) = \prod\limits_{j=2}^{l^w} p(d_j^w|X_w,\theta_{j-1}^w) \), \(d_j^w\)表示第j个结点对应的编码，\(\theta_j^w\)表示第j个结点对应的辅助向量。
第一步，目标函数对数化: $$F = \sum_{w \in C} log p(w|Context(w)) = \sum_{w \in C} log \prod\limits_{j=2}^{l^w} \sigma(\theta_{j-1}^w X_w)^{1-{d_j^w}} (1-\sigma(\theta_{j-1}^w X_w))^{d_j^w} $$
第二步，取内部项F(w,u):
$$ F(w,u) = (1-{d_j^w}) log(\sigma(\theta_{j-1}^w X_w)) + {d_j^w} log(1-\sigma(\theta_{j-1}^w X_w))$$
第三步，随机梯度上升:
\(\theta_{j-1}^w\)的更新公式为：
$$ \frac{\partial F(w,u)}{\partial \theta_{j-1}^w} = (1 - d_j^w - \sigma(X_w^T*\theta_{j-1}^w)) X_w$$
$$ \theta_{j-1}^w := \theta_{j-1}^w + \eta (1 - d_j^w - \sigma(X_w^T*\theta_{j-1}^w)) X_w $$
\(X_w\)和\(\theta_{j-1}^w\)具有对称性，更新公式类似，这里注意更新的\(v(\tilde{w})\)而非加和后的\(X_w\)：
$$v(\tilde{w}) := v(\tilde{w}) + \eta \sum\limits_{j=2}^{l^w}(1 - d_j^w - \sigma(X_w^T*\theta_{j-1}^w)) \theta_{j-1}^w, \tilde{w} \in Context(w)$$
================================================================
Negative Sampling
huffman树中从根节点到叶子节点路径上的各个中间结点，分为正负两类，构造好huffman树后，每个词w对应的采样样本（中间结点）也就确定。训练的目标是最大化似然函数值。由此衍生出，用简单的
设NEG(w)是关于词w的一个负样本集，对已一个给定的
$$ g(w) = \prod\limits_{u \in w \cup NEG(w)} p(u|Context(w))$$
=================================================================
关于模型的
为每个词设置一个
第一步，转换目标函数:
$$g(w) = \prod\limits_{u \in w \cup NEG(w)} [\sigma(\theta^u X_w^T)]^{L^w(u)} [1 - \sigma(\theta^u X_w^T)] ^ {(1-L^w(u))}$$
因为正样本只有一个，故可简化为\(g(w) =\sigma(\theta^u X_w^T) \prod\limits_{u \cup NEG(w)} [1 - \sigma(\theta^u X_w^T)] ^ {1-L^w(u)}\)
第二步，考虑整个语料库:
$$F = log G = log \prod\limits_{w \in C} g(w)$$ $$ = \sum\limits_{w \in C} \sum\limits_{u \in w \cup NEG(w)} {L^w(u)}log[\sigma(\theta^u X_w^T)] + (1-L^w(u))log[1 - \sigma(\theta^u X_w^T)]$$ $$ = \sum\limits_{w \in C} \bigg (log(\sigma(\theta^u X_w^T)) + \sum\limits_{u \in NEG(w)} log(\sigma(-\theta^u X_w^T))\bigg)$$
第三步，随机梯度上升:
$$ F(w,u) = L^w(u) log[\sigma(\theta^u X_w^T)] + (1-L^w(u)) log[1 - \sigma(\theta^u X_w^T)] $$
\(\theta^u\)的
$$\frac{\partial F(w,u)}{\partial \theta^u} = L^w(u) (1 -\sigma(\theta^u X_w^T)) X_w - (1-L^w(u)) \sigma(\theta^u X_w^T) X_w $$ $$ = L^w(u) X_w - \sigma(\theta^u X_w^T) X_w $$
$$\theta^u := \theta^u + \eta (L^w(u) - \sigma(\theta^u X_w^T)) X_w$$
根据\(\theta^u\)和\(X_w\)的
$$v(\tilde{w}) := v(\tilde{w}) + \sum\limits_{u \in w \cup NEG(w)} \eta (L^w(u) - \sigma(\theta^u X_w^T))\theta^u, \tilde{w} \in Context(w)$$
2. SKIP-GRAM
Hierarchical Softmax
与CBOW不同是，输入层只有一个词向量w。
关键在于\(p(Context(w)|w)\)的定义：
$$ p(Context(w)|w) = \prod\limits_{u \in Context(w)} p(u|w) $$，其他推导类似CBOW。
Negative Sampling
已知词w，预测词w的上下文，则针对上下文中的每个词，将该词看作正样本，选取一定数量的负样本。目标函数为：
$$F = log G = log \prod\limits_{w \in C} g(w)$$ $$ = \sum\limits_{w \in C} \sum\limits_{u \in Context(w)} \sum\limits_{z \in u \cup NEG(u)} {L^u(z)}log[\sigma(\theta^z X_w^T)] + (1-L^u(z))log[1 - \sigma(\theta^z X_w^T)]$$
公式中对于一个样本(w, Context(w)), 对Context(w)中的每个词，都做了一次负采样。而word2vec源码对此作了改动，只对词w进行了|Context(w)|次负采样。
c源码阅读
命令行参数
| 参数 | 说明 |
|---|---|
| size | Projection Layer的长度，即词向量的长度 |
| train | 语料库地址，即训练集 |
| save-vocab | 词典保存地址 |
| read-vocab | 词典读取地址，如果没指定，从语料库中学习词典 |
| debug | debug_mode，debug信息打印控制 |
| binary | 是否保存为二进制 |
| cbow | 确定是cbow，还是skip-gram模型 |
| alpha | 学习率 |
| output | 模型保存地址 |
| window | 窗口大小，默认值5 |
| sample | 采样百分比 |
| hs | 是否进行Hierarchical Softmax |
| negative | 是否进行负采样 |
| threads | 线程数 |
| min-count | 有效词频的最小值，默认值5 |
| classes | 聚类个数 |
数据结构
每个词用结构体
struct vocab_word{
char *word; //词本身
long long cn; //语料集中的词频
int *point; //huffman树中，从根节点到该词所在叶节点的中间结点列表
char *code, codelen; //该词对应的huffman编码和编码长度
};
整个词表用一个数组vocab表示，为了快速查找给定词的信息，建立了一个
哈希的策略是线性探测的开放定址法，计算词w的哈希值hv(w)作为下标索引，若该位置被占用，则顺序往下找，直到找到一个未被占用的位置。
vocab = (struct vocab_word *)calloc(vocab_max_size, sizeof(struct vocab_word));
vocab_hash = (int *)calloc(vocab_hash_size, sizeof(int));
模型实现
1. 关于Net
对于hs来说，参数主要有
关于初始化，syn0采用零初始化，syn1,syn1neg采用随机初始化([\(-\frac{-0.5}{size}, \frac{0.5}{size}\)])，其中size为词向量的长度。
代码中Hierarchical Softmax和Negative Sampling可以同时训练。neu1代表\(X_w\),即输入词向量加和后的向量；neu1e代表\(e\)，即huffman树每一条路径（从根到叶子节点）梯度更新的求和，用来更新相应的词向量。
2. sigmoid函数值计算
建模过程中用到
sigmoid函数中涉及指数运算，指数运算利用幂级数展开式实现，如果展开项数过多，则计算比较耗时。
3. 词频和窗口
删除小于阈值(min_count)的低频词，对高频词采用
模型训练以行为单位进行，对于一个给定行，包含T个词，每个词为一个训练样本，对于某个词w，定义context(w)为：设置一个窗口阈值参数window(5)，每次构造context(w)时，生成一个随机数\(c \in [1, window]\)，w前后各取c个词构成context。
4. 创建huffman树
简单来说，用一个vocab_size*2+1大小的数组存储树的
在构建树的过程中，不断更新中间结点的词频，并保存各个节点的编码(0/1)，各个节点的父节点(层次信息)。从叶子节点(词)回溯，得出该词在树中的
详见
5. 负采样
假设词典中的每个词w对应一个线段l(w),其长度为：
$$len(w) = \frac{[counter(w)]^{0.75}}{\sum\limits_{u \in D} [counter(u)]^{0.75}} $$
将这些线段首尾相接拼接在一起，形成一个长度为1的线段。随机往这个线段上打点，则高频词被打中的概率大。将这个单位线段等距离分割成M份(M远大于N,\(M=10^8\))，每次生成一个[0,M-1]的随机数r，r对应的词即为采样。有点类似k-means++的做法。
详见
6. 学习率\(\eta\)
学习率采用
$$\eta = \eta_{0}(1-\frac{word\_count\_actual}{train\_words+1})$$
随着训练的进行\(\eta\)会逐渐变小，当小于阈值\(\eta_{min}\)时，\(\eta = \eta_{min}\)
7. 多线程并行
整个工作流程是：首先读取语料库中词表并统计词频，做一些模型初始化工作，然后多线程训练word2vec，判断classes，如果为0，则保存词向量；反之，对得到的词向量进行K-means聚类，聚类个数为classes，并保存聚类结果。
pthread_t *pt = (pthread_t *)malloc(num_threads * sizeof(pthread_t));
for (a = 0; a < num_threads; a++)
pthread_create(&pt[a], NULL, TrainModelThread, (void *)a);
for (a = 0; a < num_threads; a++)
pthread_join(pt[a], NULL);
//平衡划分语料文件
fseek(fi, file_size / (long long)num_threads * (long long)id, SEEK_SET);
并行的
Spark MLlib 1.6 实现
可调参数
| 参数 | 说明 |
|---|---|
| vectorSize | 词向量的长度 |
| learningRate | 学习率 |
| numPartitions | 分区数，默认为1，越小准确率越高 |
| numIterations | 迭代次数，默认为1，不大于numPartitions |
| seed | 随机数种子 |
| minCount | 有效词频的最小值，默认值5 |
| window | 上下文的窗口大小，默认值5 |
主要实现了基于hierarchical softmax框架下的skip-gram模型。
广播
对于sigmod函数值表格，词信息数组，词的hash表三个变量，通过广播机制，变成全局变量。
val sc = dataset.context //dataset: RDD[Iterable[String]]
val expTable = sc.broadcast(createExpTable)
val bcVocab = sc.broadcast(vocab)
val bcVocabHash = sc.broadcast(vocabHash)
分布式
根据语料集文件，读取文件中的全部句子，将句子按分区数分发。
参考链接
论文：Efficient Estimation of Word Representations in Vector Space
论文：Distributed Representations of Words and Phrases and their Compositionality