CS244n Lecture Notes1:Word Embedding Part 1

从图中可以看出，最基本的层次分为语音分析和文本OCR、切分，之后是语态分析(分析某些元素所祈祷的作用)，之后是句法分析(对句子中的词语语法功能进行分析)，再下一层是语义解释(分析每个成分在语义含义层面的事情)，最后是语篇分析(所谓的终极理解)。各个问题都是研究的NLP 的核心问题，难度和挑战也是逐层加大。虽然NLP 离完全AI 还有很大距离，但当前的技术水平，以使它在各行业有了广泛的应用。

• 拼写检查、关键词搜索、同义词查找
• 信息提取，如提取价格、日期、地点
• 文本分类、情感分析
• 机器翻译
• 对话系统，问答
  在工业届很多实际场景中也得到广泛的应用。
• 搜索场景(语音和文字)
• 在线广告
• 自动、辅助翻译
• 市场情感分析
• 语音辨识
• 聊天对话系统(客服助手、设备控制、购物)

  What’s so special about human(nature) language?

  人类语言后者称作自然语言被设计的初衷是用来携带、传达彼此之间的信息，并不是由任何物理形成产生的，基于这一个特点，它不同于视觉、图像处理或其他机器学习任务。举个具体的例子”rocket”, 这个词可以指代火箭这个概念，同时也可以表示具体事物火箭。不同的说话语气也可以表示不同的含义，比”Whooompaa”. 自然语言可以用多种形式进行表示，比如声音、手势、书写，这些信息不断的通过信号传送到人的大脑中，这样人才能去理解。NLP 的目标是通过设计算法让计算机能够理解自然语言并帮助执行一些任务。根据任务难度不同，NLP 研究任务举例如下。
  Easy
• 拼写检查
• 关键词搜索
• 同义词查找
  Medium
• 文档解析
  Hard
• 机器翻译
• 语义分析(分析某个query 的具体具体含义)
• 指代分析(分析一篇文档中指称代词具体指的什么)
• 问答系统
• 聊天机器人
  那么为什么要引入深度学习呢？因为深度学习可以看成是一个强大的表示学习系统，利用学到的representation 去解决NLP 相关的任务。现在问题来了，如和去得到一个词的表示，这个表示以何种形式进行存在呢？经过前人的探索和研究，将”word” 表示成vector 形式能够极大的促进任务的解决，因为word 都以向量的形式进行表示，则可以进行距离方式(Jaccard,Cosine, Euclidean) 进行计算。

  Word Vector

  将word 表示成vector 对解决NLP Task 有着重要的帮助，如何将word 转换为vector 呢？最直观的想法是建立一个vocabulary，然后将每个word 都表示成一个vocab 大小的vector,vector 中只有在word 出现的index 位置为1，其他位置全部为0，这种方式就是常说的基于BOW(bag of words) 的one-hot编码。这种方式的缺陷显而易见，一是vocabulary 词
  典很大，英文词典可达到13million，而中文词典更大；二是这种方式并不能体现同义词之间的相近关系。根据one-hot encoding 的结果，计算任意两个词间的点积，结果都是零，这就是体现了这种encoding 方式并不能体现出词间的某种相似性。除one-hot encoding 之外，还有字符编码等。

  SVD Based Methods

  除了前面提到的one-hot encoding 之外还可以利用基于矩阵分解对的方式来获得word vecotr(通常也称作word embedding)。这种方式有个前提假设，“经常同时出现的词语义具有相似性，即词间的共现性。”首先我们遍历一个大的document 库，目的是要构建一个word-document 矩阵。首先构建个vocabulary，然后遍历每个word i在每个document j中出现的次数，存放在Xij , 这样就形成了一个矩阵XRM,M 是总的文档数量。当构造出word-doc 矩阵之后，利用SVD(Singular Value Decomposition) 对矩阵
  进行分析，矩阵分解公式如下，
  

进行矩阵分解之后，观察奇异值(对角矩阵S 中对角线上的值)，然后选取k 个值，从而选择子矩阵U1:V;1:k 作为word embedding 矩阵，那么每个词将表示成一个k-dimension 的vector。这中方式其实类似于LSA。但同时这种方式也存在一些问题，如下：

• word-doc 矩阵经常变换，因为频繁会有新的词加入进来
• 整个矩阵会非常系数，因为有很多词并不共现
• 矩阵维度很大
• SVD 复杂度是O(n2)
• 对于词频率不均衡需(有些词频率会很大) 要特殊处理

  Iteration Based Methods - Word2Vec

  换一种思维，设计一种模型，让模型的参数词向量，通过对模型的迭代训练、误差优化、参数更新学到word vectors。在NLP 任务中，学者们已尝试过很多中方式来实现这个目的。比如在特定的NLP 任务中，刚开始时将每个word 转换为一个词向量，训练不仅仅更新模型参数同时也训练word vector。(注：这在tensorflow 中是基于look table 实现)。这里介绍一种更高效、简单的、概率的方法word2vec, 它是一个软件包，包含两种算法CBOW(continuous bag-of-words) 和Skip-gram。前者是给定context word 来预测center word，后者刚好相反；两种训练方法Negative Sampling 和Hierarchical Softmax, 负采样通过负采样来定义目标函数，分层softmax 通过一种高效的树结构计算词典中每个词概率来定义目标函数。下文会对他们进行详细阐述。

  Continuous Bag of Words Model(CBOW)

  给定context word(上下文周边词) 来预测center word 的方式被称作CBOW 模型。CBOW 网络结构如图所示。
  
  下面给出模型中一些必要的参数定义和说明：
  
  

在CBOW 中每个词会学习到两个vector，输入词向量vi 和输出词向量uj，最终选择哪个作为后文会讨论。CBOW 模型执行具体过程如下.

以上就是CBOW 模型具体执行过程，其中省略了梯度推导和计算.

Skip-gram

Skip-gram 是通过中心词来预测周围词的模型。skip-gram 网络模型如图所示。skip-gram 模型过程基本与CBOW 类似，下面对该过程进行具体介绍。

在CBOW 和Skip gram 模型中，采用生成的概率分布去预测词的真实分布，如何去评价模型的好坏呢？根据信息论我们知道，cross entropy 是用来测度两个分布之间差异，因此在CBOW 和SG 模型中也采用交叉熵作为目标函数。在SG 模型中，基于朴素贝叶斯假设，将预测的上下文词的联合概率分布当做独立分布去计算。这里以SG 模型为
主，且词窗口设定为1，则目标函数为

其中，yi 是真是词向量，属于one-hot 编码只有在下标为c 处为1，而预测概率by 是通过softmax 而来。以上就是最终的目标函数，可以基于此目标函数对其中的输入参vc 和输出参数uc 就梯度，采用梯度下降法进行求解最优值。各参数梯度求导可参考文献[1]

Negative Sampling

回顾一下目标函数，整个词表的大小|V| 可能会很大，每次更新都需要O(|V|) 的时间，我们设法对它进行优化，一个直观的想法是通过采样来替代遍历整个词典。在每个训练步，通过采样一些负例来代替遍历整个词典。采样原则基于某个分布Pn(w)，它的概率值与词典中词的频率顺序相对应，换句话说就是频率高的词被采样概率越大。为了适应负采样做法我们需要调整目标函数、梯度、更新规则。Negative Sampling 是Mikolov
在这篇Paper中进行论述. 负采样是基于Skip-gram 模型，但优化的目标函数不同。给定一个词和上下文中的词构成的词对(w; c)，用P(D = 1jw; c)表示词对来源于与语料库(这里语料库的意思是指w 是词c 的上下文词，即在同一个窗口内)，记P(D = 0jw; c) 表示词对不是来自于语料库，用sigmod 函数对前一种情况进行建模

函数图像如下，它可以看成是Softmax 的1 维情况根据前面的描述，我们设计一个新的目标函数，如果词和上下文来源于同一个语料库，则最大化他们来源于同一个语料库的概率，如果不是，则最大化他们不是来源于同一个语料库的概率，即最小化来源于同一语料库的概率。我们采用极大似然函数法来表示这两个概率，

Hierarchical Softmax

Mikolov 在这篇中同时也介绍了另外一个优化普通softmax 的方法即使hierarchical softmax，分层softmax。在实践中，hierarchical softmax对罕见词有较好的效果，而negative sampling 对高频词有较好的效果。Hierarchical softmax 采用一个二叉树来表示词典中所有词如图所示。每一个叶子

节点都代表一个词，从根节点到leaf 节点只有唯一一条路径，这个路径被定义为每个词的概率，图中除去根节点和叶子节点以外的节点，都是一个需要模型学习的向量。当用Hierarchical softamx 时，整个模型中每个词只有输入表示，而不像原始模型中那样也具有输出表示。下图是Hierarchical softmax 二叉树的一个示例。在这个模型中，当给定一个向量wi 和P(wjwi) 时，词w 的概率就等于从根节点出发随机游走到与w 相关的叶子节点的概率。由于采用二叉树结构，所有模型计算复杂度从最初的O(|V |) 变成O(log(|V |)). 为了进一步介绍该模型，引入一下记号，

为了训练这个模型，我们的目标依然是最小化负对数似然函数-logP(w|w_i)，但是我们只需要更新在二叉树中从根节点到叶子节点路径上的节点的向量即可，而不需要更新每个词的输出向量。这个方法的速度取决于如何构建二叉树及如何用叶子节点表示每个词，在MIKOLOV 的论文中使用的是Huffman 树，它的特点是频率越高的词在树中路径越短。
5 参考文献
[Bengio et al., 2003] Bengio, Y., Ducharme, R., Vincent, P., and Janvin,C. (2003). A neural probabilistic language model. J. Mach. Learn. Res.,3:1137–1155. [Collobert et al., 2011] Collobert, R., Weston, J., Bottou,L., Karlen, M., Kavukcuoglu, K., and Kuksa, P. P. (2011). Natural languageprocessing (almost) from scratch. CoRR, abs/1103.0398. [Mikolovet al., 2013] Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013).
Efficient estimation of word representations in vector space. CoRR, abs/1301.3781. [Rong, 2014] Rong, X. (2014). word2vec parameter learningexplained. CoRR, abs/1411.2738. [Rumelhart et al., 1988] Rumelhart, D.E., Hinton, G. E., and Williams, R. J. (1988). Neurocomputing: Foundationsof research. chapter Learning Representations by Back-propagating Errors, pages 696–699. MIT Press, Cambridge, MA, USA.