最近新接触文本分类问题，对于我来数第一个问题就是Word Embedding这个词到底是什么意思，因此也就开始学习了相关知识
http://licstar.net/archives/328
一、Word Embedding定义
Embedding是数学领域的有名词，是指某个对象 X 被嵌入到另外一个对象 Y 中，映射 f : X → Y ，例如有理数嵌入实数。
Word Embedding 是NLP中一组语言模型和特征学习技术的总称，把词汇表中的单词或者短语映射成由实数构成的向量上(映射)
二、One-Hot
最简单的Word Embedding，是指将所有词排成一列，对于词A，只有在它的位置置1，其他位置置0，维度就是所有词的数目。
缺点：
(1）没有考虑单词之间相对位置的关系
(2）词向量可能非常长
为了考虑相互位置关系，会想到n-gram方法，但它可能会导致计算量的急剧增长。
N-Gram
N-Gram是基于一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关（这也是隐马尔可夫当中的假设）。指给定的一段文本或语音中N个项目（item）的序列
两个重要应用场景：
（1）基于一定的语料库，利用N-Gram预计或者评估一个句子是否合理。
（2）评估两个字符串之间的差异程度。这是模糊匹配中常用的一种手段。
N=1时称为unigram，N=2称为bigram，N=3称为trigram，以此类推。
例：将“informationretrieval”视为一段文本，它的5-grams的items依次为：
infor, nform, forma, ormat, rmati, matio, ation, tionr, ionre, onret, nretr, retri, etrie, triev, rieva, ieval
1、字符串间模糊匹配
（1）N-gram距离
两个字符串s，t分别利用N-Gram语言模型来表示时，则对应N-gram子串中公共部分的长度就称之为N-Gram距离。例如：假设有字符串s，那么按照N-Gram方法得到N个分词组成的子字符串，其中相同的子字符串个数作为N-Gram距离计算的方式。具体如下所示：
字符串：s="ABC"，对字符串进行分词，考虑字符串首尾的字符begin和end，得到begin，A，B，C，end。这里采用二元语言模型，则有：（begin,A）、（A,B）、（B,C）、（C,end）。
字符串：t="AB"，对字符串进行分词，考虑字符串首尾的字符begin和end，得到begin，A，B，end。这里采用二元语言模型，则有：（begin,A）、（A,B）、（B,end）。
距离公式：
4+3-2*3=1
2、判断句子有效性
假设有一个字符串s="ABC",对应的BI-Gram的结果如下：（begin,A）、（A,B）、（B,C）、（C,end）。出现字符串s的概率为：
P(ABC)=P(A|begin)P(B|A)P(C|B)*P(end|C)。
3、N-Gram在特征工程中的应用
在处理文本特征时，通常一个关键词作为一个特征。在一些场景可能不够，需要进一步提取更多的特征，可以考虑N-Gram，思路如下：
以Bi-Gram为例，在原始文本中，以每个关键词作为一个特征，通过将关键词两两组合，得到一个Bi-Gram组合，再根据N-Gram语言模型，计算各个Bi-Gram组合的概率，作为新的特征。
二、Cocurrence matrix定义
共现矩阵Cocurrence matrix：一定程度上解决没有考虑单词之间相对位置的关系的问题
实现方法：某个词的意思跟它临近的单词是紧密相关的。可以设定一个窗口（大小一般是5~10)，利用这种共现关系生成词向量（得到一个对称矩阵——共现矩阵，该矩阵统计当前词与其他词在同一窗口中的次数，如果词数是n，那么矩阵是nXn）。
例子：
I like deep learning.
I like NLP.
I enjoy flying.
共现矩阵：
缺点：仍然面对维度灾难。这SVD或者PCA等一些常用的降维方法也会带来其他的一些问题，例如，我们的词汇表中有新词加入，很难为他分配一个新的向量。
三、Dristributed representation
Dristributed representation：低维实数向量，它的思路是通过训练，将每个词都映射到一个较短的词向量上来，可以解决One hot representation的问题，。在word2vec出现之前，已经有用神经网络DNN来用训练词向量进而处理词与词之间的关系了。采用的方法一般是一个三层的神经网络结构（当然也可以多层），分为输入层，隐藏层和输出层(softmax层)
相关或者相似的词，在距离上更接近
自动实现：1）单词语义相似性的度量；2）词汇的语义的类比
四、Word2Vec训练词向量
Word2Vec：CBOW、Skip-Gram
流程：建立模型、通过模型获取嵌入词向量
相关讲解：
word2vec原理(一) CBOW与Skip-Gram模型基础
建模角度理解word embedding及tensorflow实现
一文详解 Word2vec 之 Skip-Gram 模型（结构篇）
一文详解 Word2vec 之 Skip-Gram 模型（训练篇）
一文详解 Word2vec 之 Skip-Gram 模型（实现篇）
1、Skip-Gram
定义：给定input word来预测上下文
训练数据获取：假如有一个句子“The quick brown fox jumps over lazy dog”。
- 选句子中间的一个词作为我们的输入词，例如我们选取“quick”作为input word；
- 定义skip_window的参数，代表从当前input word的一侧（左边或右边）选取词的数量。如果我们设置skip_window=2，那么我们最终获得窗口中的词（包括input word在内）就是['The', 'quick'，'brown', 'fox']。skip_window=2代表着选取左input word左侧2个词和右侧2个词进入我们的窗口，所以整个窗口大小span=2x2=4。
- 参数num_skips，代表从整个窗口中选取多少个不同的词作为output word，当skip_window=2，num_skips=2时，会得到两组 (input word, output word) 形式的训练数据，即 ('quick', 'brown')，('quick', 'the')。
- 训练时，剔除高频的停用词来减少模型的噪音，并加速训练，如'the'、'a'等，它们对其他词的贡献不大。
- input word和output word都是one-hot编码的向量。最终模型的输出是一个概率分布。
对于输入为'the'时，训练时的一个batch会有两个输入(the, quick)和(the, brown)
模型输入：
输入的每一个词都是一个One-Hot表示形式，("the", "quick", "brown", "fox", "jumps","over","lazy","dog")，我们对这个词汇表的单词进行编号0-7。那么”dog“就可以被表示为一个8维向量[0, 0, 0, 0, 0, 0, 0, 1]。
通常词汇表比较大，如果词汇表有10000个词，模型的输入就是一个10000维的向量，那么输出也是一个10000维度（词汇表的大小）的向量，它包含了10000个概率，每一个概率代表着当前词是输入样本中output word的概率大小。
隐含层：
网络的隐层没有使用任何激活函数，但是输出层使用了sotfmax
隐含层节点的个数就是词向量的维数，由One-Hot映射为Dristributed representation
上图网络中隐层的权重矩阵应该为10000行，300列（隐层有300个结点）。最终每个单词可以被编码为300维的词向量
Google在最新发布的基于Google news数据集训练的模型中使用的是300个特征的词向量，在Python的gensim包中封装的Word2Vec接口默认的词向量大小为100， window_size为5
下图中，左右两张图分别从不同角度代表了输入层-隐层的权重矩阵。左图中每一列代表一个10000维的词向量和隐层单个神经元连接的权重向量。右图中，每一行实际上代表了每个单词的词向量。
最终的目标就是学习这个隐层的权重矩阵
我们现在回来接着通过模型的定义来训练我们的这个模型。
input word和output word都会被我们进行one-hot编码。输入被one-hot编码后大多数维度上都是0（实际上仅有一个位置为1），所以向量稀疏，如果我们将一个1 x 10000的向量和10000 x 300的矩阵相乘，它会消耗相当大的计算资源，为了高效计算，隐层权重矩阵看成了一个”查找表“（lookup table），进行矩阵计算时，直接去查输入向量中取值为1的维度下对应的那些权重值。隐层的输出就是每个输入单词的“嵌入词向量”。
输出层
经过神经网络隐层的计算，词从一个1 x 10000的向量变成1 x 300的向量，再被输入到输出层。输出层是一个softmax回归分类器，它的每个结点将会输出一个0-1之间的值（概率），这些所有输出层神经元结点的概率之和为1。
下面是一个例子，训练样本为 (input word: “ants”， output word: “car”) 的计算示意图。
2、CBOW
定义：给定上下文，来预测input word（与Skip-Gram相反）
输入数据：输入有多个单词，每个单词与隐含层矩阵相乘后得到多个词向量，此时对多个词向量平均，再输出到输出层。
3、模型加速
DNN模型最大的问题在于从隐藏层到输出的softmax层的计算量很大，因为要计算所有词的softmax概率，再去找概率最大的值==>Hierarchical Softmax
Hierarchical Softmax（霍夫曼树）提高模型训练的效率（时间复杂度O(n)==>O(logn)）。但是如果训练样本里的中心词w是一个很生僻的词，那么霍夫曼树向下走很久==>Negative Sampling
Negative Sampling：neg个负例，每次网络更新不对所有负样本更新
(1)Hierarchical Softmax
定义：Hierarchical Softmax是一种对输出层进行优化的策略，输出层从原始模型的利用softmax计算概率值改为了利用Huffman树计算概率值。
哈夫曼树怎么来的？ 将语料库中词以及词出现的频率构造一颗哈夫曼树，默认左边(编码为0)是负类，右边(编码为1)是正类，哈夫曼树的叶子节点就是语料库中的所有的词 ，词频越高的词，距离根节点就越近。
从根节点出发，到达指定叶子节点的路径是唯一的。softmax概率计算只需要沿着树形结构进行就可以。如下图所示，可以沿着霍夫曼树从根节点一直走到叶子节点的词w2
和之前的神经网络语言模型相比，霍夫曼树的所有内部节点就类似之前神经网络隐藏层的神经元，其中，根节点的词向量对应我们的投影后的词向量(即隐含层词向量)，而所有叶子节点就类似于之前神经网络softmax输出层的神经元，叶子节点的个数就是词汇表的大小。在霍夫曼树中，隐藏层到输出层的softmax映射是沿着霍夫曼树一步步完成的，因此这种softmax取名为"Hierarchical Softmax"。
实现：在word2vec中，采用二元逻辑回归的方法，即规定沿着左子树走是负类(霍夫曼树编码1)，沿着右子树走是正类(霍夫曼树编码0)。判别正类和负类的方法是使用sigmoid函数
优势：第一，二叉树，将计算量为V降为log2V。第二，由于使用霍夫曼树是高频的词靠近树根，高频词需要更少的时间会被找到，这符合贪心优化思想。
被划分为左子树而成为负类的概率为P(−)=1−P(+)。在某一个内部节点，要判断是沿左子树还是右子树走的标准就是看P(−)、P(+)谁的概率值大。而控制P(−)、P(+)谁的概率值大的因素一个是当前节点的词向量，另一个是当前节点的模型参数θ（需要训练）。
对于上图中的w2，如果它是一个训练样本的输出，那么我们期望对于里面的隐藏节点n(w2,1)的P(−)概率大，n(w2,2)的P(−)概率大，n(w2,3)的P(+)概率大。
回到基于Hierarchical Softmax的word2vec本身，我们的目标就是找到合适的所有节点的词向量和所有内部节点θ, 使训练样本达到最大似然。
(2)Negative Sampling
Word2Vec 的作者在它的第二篇论文中强调了三个创新：
将常见的单词组合（word pairs）或者词组作为单个“words”来处理。
对高频次单词进行抽样来减少训练样本的个数。
对优化目标采用“negative sampling”方法，这样每个训练样本的训练只会更新一小部分的模型权重，从而降低计算负担。
创新一：Word pairs and "phases"
作者指出，一些单词组合（或者词组）的含义和拆开以后具有完全不同的意义。比如“Boston Globe”是一种报刊的名字，而单独的“Boston”和“Globe”这样单个的单词却表达不出这样的含义。因此，在文章中只要出现“Boston Globe”，我们就应该把它作为一个单独的词来生成其词向量，而不是将其拆开。同样的例子还有“New York”，“United Stated”等。
在Google发布的模型中，它本身的训练样本中有来自Google News数据集中的1000亿的单词，但是除了单个单词以外，单词组合（或词组）又有3百万之多。
创新二：高频词抽样
对于“the”这种常用高频单词，存在两个问题：
当我们得到成对的单词训练样本时，("fox", "the") 这样的训练样本并不会给我们提供关于“fox”更多的语义信息，因为“the”在每个单词的上下文中几乎都会出现。
由于在文本中“the”这样的常用词出现概率很大，因此我们将会有大量的（”the“，...）这样的训练样本，而这些样本数量远远超过了我们学习“the”这个词向量所需的训练样本数。
Word2Vec通过“抽样”模式来解决这种高频词问题。
基本思想：对于训练原始文本中遇到的每一个单词，它们都有一定概率被我们从文本中删掉，而这个被删除的概率与单词的频率有关。
抽样率
ωi 是一个单词，Z(ωi) 是 ωi 这个单词在所有语料中出现的频次。如果单词“peanut”在10亿规模大小的语料中出现了1000次，那么 Z(peanut) = 1000/1000000000 = 1e - 6。
有一个参数叫“sample”，这个参数代表一个阈值，默认值为0.001（在gensim包中的Word2Vec类说明中，这个参数默认为0.001，文档中对这个参数的解释为“ threshold for configuring which higher-frequency words are randomly downsampled”）。这个值越小意味着这个单词被保留下来的概率越小（即有越大的概率被我们删除）。
P(ωi) 代表着保留某个单词的概率：
图中x轴代表着 Z(ωi) ，即单词 ωi 在语料中出现频率，y轴代表某个单词被保留的概率。对于一个庞大的语料来说，单个单词的出现频率不会很大，即使是常用词，也不可能特别大。
从这个图中，我们可以看到，随着单词出现频率的增高，它被采样保留的概率越来越小，我们还可以看到一些有趣的结论：
● 当 Z(ωi) <= 0.0026 时，P(ωi) = 1.0 。当单词在语料中出现的频率小于 0.0026 时，它是 100% 被保留的，这意味着只有那些在语料中出现频率超过 0.26% 的单词才会被采样。
● 当时 Z(ωi) = 0.00746 时，P(ωi) = 0.5，意味着这一部分的单词有 50% 的概率被保留。
● 当 Z(ωi) = 1.0 时，P(ωi) = 0.033，意味着这部分单词以 3.3% 的概率被保留。
创新三：负采样（negative sampling）
训练一个神经网络意味着要输入训练样本并且不断调整神经元的权重，从而不断提高对目标的准确预测。每当神经网络经过一个训练样本的训练，它的权重就会进行一次调整。
vocabulary的大小决定了我们的Skip-Gram神经网络将会拥有大规模的权重矩阵，所有的这些权重需要通过我们数以亿计的训练样本来进行调整，这是非常消耗计算资源的，并且实际中训练起来会非常慢。
negative sampling解决了这个问题，它是用来提高训练速度并且改善所得到词向量的质量的一种方法。不同于原本每个训练样本更新所有的权重，负采样每次让一个训练样本仅仅更新一小部分的权重，这样就会降低梯度下降过程中的计算量。
当我们用训练样本 ( input word: "fox"，output word: "quick") 来训练我们的神经网络时，“ fox”和“quick”都是经过one-hot编码的。如果我们的vocabulary大小为10000时，在输出层，我们期望对应“quick”单词的那个神经元结点输出1，其余9999个都应该输出0。在这里，这9999个我们期望输出为0的神经元结点所对应的单词我们称为“negative” word。
当使用负采样时，我们将随机选择一小部分的negative words（比如选5个negative words）来更新对应的权重。我们也会对我们的“positive” word进行权重更新（在我们上面的例子中，这个单词指的是”quick“）。
在论文中，作者指出指出对于小规模数据集，选择5-20个negative words会比较好，对于大规模数据集可以仅选择2-5个negative words。
隐层-输出层拥有300 x 10000的权重矩阵。如果使用了负采样的方法我们仅仅去更新我们的positive word-“quick”的和我们选择的其他5个negative words的结点对应的权重，共计6个输出神经元，相当于每次只更新 300 x 6 = 1800 个权重。对于3百万的权重来说，相当于只计算了0.06%的权重，这样计算效率就大幅度提高。
选择negative words
使用“一元模型分布（unigram distribution）”来选择“negative words”。
一个单词被选作negative sample的概率跟它出现的频次有关，出现频次越高的单词越容易被选作negative words。
代码中的公式实现如下：
每个单词被赋予一个权重，即 f(ωi)， 它代表着单词出现的频次。
公式中开3/4的根号完全是基于经验的，论文中提到这个公式的效果要比其它公式更加出色。你可以在google的搜索栏中输入“plot y = x^(3/4) and y = x”，然后看到这两幅图（如下图），仔细观察x在[0,1]区间内时y的取值，x^(3/4) 有一小段弧形，取值在 y = x 函数之上。
