前人栽树，后人乘凉
word2vec 中的数学原理详解（五）基于 Negative Sampling 的模型
最后一个讲的很细致，强烈推荐
动机：Word2Vec以及word Embedding概念很早就知道了，xc对此很感兴趣
不过最近发现一些公司面试时候喜欢考这里的知识点，然而层次softmax的细节以及如何应用到训练中我还不是很懂，于是找了一下相关资料
Word2Vec
word2vec也叫word embeddings,中文名“词向量”、”词嵌入”。是Google 的 Tomas Mikolov 在《Efficient Estimation of Word Representation in Vector Space》提出的。word2vec分两个模型，分别为skip-gram(Continuous Skip-gram Model 跳字模型)和CBOW(Continuous Bag-of-Words Model 连续词袋模型)。
本质上是一种单词聚类的方法
one-hot
独热编码即 One-Hot 编码，又称一位有效编码，其方法是使用N位状态寄存器来对N个状态进行编码，每个状态都有它独立的寄存器位，并且在任意时候，其中只有一位有效。
优点：
解决了分类器不好处理离散数据的问题
在一定程度上也起到了扩充特征的作用。
缺点：在文本特征表示上有些缺点就非常突出
- 它是一个词袋模型，不考虑词与词之间的顺序（文本中词的顺序信息也是很重要的）
- 它假设词与词相互独立（在大多数情况下，词与词是相互影响的）
- 它得到的特征是离散稀疏的(维度灾难)。
解决：
word embedding（词嵌入），即将高维词向量嵌入到一个低维空间。
词向量：
word2vec
word2vec模型其实就是简单化的神经网络。
输入是One-Hot Vector，Hidden Layer没有激活函数，也就是线性的单元。Output Layer维度跟Input Layer的维度一样，用的是Softmax回归。当这个模型训练好以后，我们并不会用这个训练好的模型处理新的任务，我们真正需要的是这个模型通过训练数据所学得的参数，例如隐层的权重矩阵。
每个词都可有两个向量表达，既可以是背景词，也可以是中心词。
词袋模型训练时间更短，但是skip-gram更精准
CBOW对小型数据库比较合适，而Skip-Gram在大型语料中表现更好
skip-gram
跳字模型就是用一个词去预测它文本序列周围的词，例如：”the“，”man“，”hit“，”his“，”son“。比如时间窗口大小为2，则可以用”hit“中心词来预测”the“，”man“，”his“，”son“这些窗口小于2的背景词的最大概率。
CBOW
连续词袋模型就是用文本序列周围的词来预测中心词，例如，给定文本序列”the“，”man“，”hit“，”his“，”son“，连续词袋模型关心的是给定”the“，”man“，”his“，”son“一起生成中心词”hit“的概率。
训练过程
以“我爱北京天安门”这句话为例。
假设我们现在关注的词是“爱”，
C＝2时它的上下文分别是“我”，“北京天安门”
CBOW模型就是把“我” “北京天安门” 的one hot表示方式作为输入，也就是C个$1*V$的向量
分别跟同一个$VxN$的大小的系数矩阵$W1$相乘得到C个$1xN$的隐藏层$hidden layer$，
C个取平均所以只算一个隐藏层。
这个过程也被称为线性激活函数(这也算激活函数？分明就是没有激活函数了)。
再跟另一个$NxV$大小的系数矩阵W2相乘得到$1xV$的输出层
这个输出层每个元素代表的就是词库里每个词的事后概率。
输出层需要跟ground truth也就是“爱”的one hot形式做比较计算loss。
优化：这里需要注意的就是V通常是一个很大的数比如几百万，计算起来相当费时间，除了“爱”那个位置的元素肯定要算在loss里面，word2vec就用基于huffman编码的Hierarchical softmax筛选掉了一部分不可能的词，然后又用nagetive samping再去掉了一些负样本的词所以时间复杂度就从O(V)变成了O(logV)。Skip gram训练过程类似，只不过输入输出刚好相反。
知乎的回答：
- 输入层：上下文单词的onehot. {假设单词向量空间dim为V，上下文单词个数为C}
- 所有onehot分别乘以共享的输入权重矩阵W. {V*N矩阵，N为自己设定的数，初始化权重矩阵W}
- 所得的向量 {因为是onehot所以为向量} 相加求平均作为隐层向量, size为1*N.
- 乘以输出权重矩阵W’ {N*V}
- 得到向量 {1*V} 激活函数处理得到V-dim概率分布 {PS: 因为是onehot嘛，其中的每一维斗代表着一个单词}，概率最大的index所指示的单词为预测出的中间词（target word）
- 与true label的onehot做比较，误差越小越好
所以，需要定义loss function（一般为交叉熵代价函数），采用梯度下降算法更新W和W’。训练完毕后，输入层的每个单词与矩阵W相乘得到的向量的就是我们想要的词向量（word embedding），这个矩阵（所有单词的word embedding）也叫做look up table（其实聪明的你已经看出来了，其实这个look up table就是矩阵W自身），也就是说，任何一个单词的onehot乘以这个矩阵都将得到自己的词向量。有了look up table就可以免去训练过程直接查表得到单词的词向量了。**
训练加速小trick
- 把常见的词组作为一个单词。
- 少采样常见的词 （译者按：A the 啥的都滚粗）
- 修改优化目标函数，这个策略成为“Negative Sampling“，使得每个训练样本只去更新模型中一小部分的weights
普遍认为Hierarchical Softmax对低频词效果较好；Negative Sampling对高频词效果较好，向量维度较低时效果更好
降采样（下采样）
又名downsampled、SubSampling
实际是对高频词进行随机采样，关于随机采样的选择问题，考虑高频词往往提供相对较少的信息，因此可以将高于特定词频的词语丢弃掉，以提高训练速度。
解决“the“这种常见的词，（理解：数据不平衡）
我们使用 $w_i$ 来表示单词，$z(w_i)$ 表示它出现在词库中的概率。比如花生在1bilion的词库中出现了1,000词，那么$z(花生)=1E−6$。
有个叫‘sample‘的参数控制了降采样的程度，一般设置为0.001。这个值越小代表更容易扔掉一些词。
$z(w_i)<=0.0026$ 的情况下，$P(w_i)=1$，我们不会把这些词扔掉
当$z(w_i)<=0.00746$ 的情况下，$P(wi)=0.5$,
负采样Negative Sampling（skip-gram举例）
训练神经网络 意味着输入一个训练样本调整weight，让它预测这个训练样本更准。换句话说，每个训练样本将会影响网络中所有的weight。
像我们之前讨论的一样，我们词典的大小意味着我们有好多weight，所有都要轻微的调整。
negative sampling 每次让一个训练样本仅仅更新一小部分的权重参数，从而降低梯度下降过程中的计算量。
如果 vocabulary 大小为1万时， 当输入样本 ( “fox”, “quick”) 到神经网络时，
“ fox” 经过 one-hot 编码，在输出层我们期望对应 “quick” 单词的那个神经元结点输出 1，
其余 9999 个都应该输出 0。
在这里，这9999个我们期望输出为0的神经元结点所对应的单词我们为 negative word.
Negative sampling 解决了这个问题，每次我们就修改了其中一小部分weight，而不是全部。
当训练（fox，quick）这个词对的时候，quick这个词的概率是1，其他的都是0。通过negative sample，我们只是随机的选了一部分negative词（假设是5个）来update weight。（这些negative 词就是我们希望是0的。）
论文中说5-20个词适合小数据集， 2-5个词适合大数据集。
negative sample也是根据他们出现频率来选的。更常出现的词，更容易被选为negative sample。
$f(w) $代表 每个单词被赋予的一个权重，即 它单词出现的词频.
与层次softmax相比，NEG不再使用复杂的Huffman树，而是利用相对简单的随机负采样，能大幅提高性能，因为可以作为分层softmax的一种替代。
层次softmax Hierarchical Softmax
大家都知道哈夫曼树是带权路径最短的树，一般神经网络语言模型在预测的时候，输出的是预测目标词的概率（每一次预测都要基于全部的数据集进行计算，很大的时间开销）。
Hierarchical Softmax是一种对输出层进行优化的策略:
输出层从原始模型的利用softmax计算概率值改为了利用Huffman树计算概率值。
一开始我们可以用以词表中的全部词作为叶子节点，词频作为节点的权，构建Huffman树，作为输出。从根节点出发，到达指定叶子节点的路径是唯一的。Hierarchical Softmax正是利用这条路径来计算指定词的概率，而非用softmax来计算。
即Hierarchical Softmax：把 N 分类问题变成 log(N)次二分类
作为一种计算高效的近似方法，Hierarchical Softmax被广泛使用。Morin和Bengio[1]首先将这种方法引入神经网络语言模型。
该方法不用为了获得概率分布而评估神经网络中的W个输出结点，而只需要评估大约log2(W)个结点。层次Softmax使用一种二叉树结构来表示词典里的所有词，V个词都是二叉树的叶子结点，而这棵树一共有V−1个非叶子结点。
对于每个叶子结点（词），总有一条从根结点出发到该结点的唯一路径。这个路径很重要，因为要靠它来估算这个词出现的概率。以下图为例（图来自Xin Rong,2014[6]），白色结点为词典中的词，深色是非叶子结点。图中画出了从根结点到词w2的唯一路径，路径长度L(w2)=4，而n(w,j)表示从根结点到词w2的路径上的的第j个结点。
在层次Softmax模型中，叶子节点的词没有直接输出的向量，而非叶子节点其实都有响应的输出向量。**
求目标词的概率 ：
在模型的训练过程中，通过Huffman编码，构造了一颗庞大的Huffman树，同时会给非叶子结点赋予向量。我们要计算的是目标词w的概率，这个概率的具体含义，是指从root结点开始随机走，走到目标词w的概率。因此在途中路过非叶子结点（包括root）时，需要分别知道往左走和往右走的概率。
word2vec和word embedding的区别
简言之，word embedding 是一个将词向量化的概念，中文译名为”词嵌入”。 word2vec是谷歌提出的一种word embedding的具体手段，采用了两种模型(CBOW与skip-gram模型)与两种方法(负采样与层次softmax方法)的组合，比较常见的组合为 skip-gram+负采样方法。
