FastText介绍(word2vec,层次softmax,负采样)

0. 简介

fastText是Facebook2016年提出的文本分类工具，是一种高效的浅层网络。

主流模型忽略单词的形态学，在大的单词库以及稀少单词时，出现局限性。 Fasttext 基于 skipgram或者CBOW 模型，考虑每个单词的字符，具有计算迅速，允许计算在训练数据没有出现过的单词表示。
比如， “dog”, “dogs” 这些都有同一个词根"dog". 根据字符差生 子词嵌入（subword embedding）的方法。一般，使用fastText进行文本分类，也会产生词的embedding。

1. 基本知识

1.1 Word2Vec

CBOW模型是，利用上下文预测目标词汇。

Skip-gram是利用当前时刻的词，预测它上下文的内容。
$$\sum _{t=1}^T\sum _{c\in {\mathcal{C}}_t}\log p\left(w_c|w_t\right)$$

1.2 softmax回归

有m个样本$\left\{(x^{(1)},y^{(1)}),...\right\}$, y ( i ) ∈ { 0 , 1 } y^{(i)}\in \left\{ {0,1} \right\} y(i)∈{ 0,1}.假设，

$$h_{\theta }(x)=?\begin{array}{c}P(y=1|x;\theta )\\ P(y=2|x;\theta )\\ ?\\ P(y=K|x;\theta )\end{array}?=\frac{1}{{\sum }_{j=1}^K{e}^{\theta (j{)}^{T}x}}?\begin{array}{c}{e}^{{\theta }^{(1{)}^T}x}\\ e^{{\theta }^{(2)}x}\\ ?\\ e^{\theta (K{)}^{T}x}\end{array}?$$

Word2Vec 模型对最后一层输出值经过Softmax运算，来获得预测单词的概率。
比如，Skip-gram模型
$$p\left(w_c|w_t\right)=\frac{e^{s\left(w_t,w_c\right)}}{{\sum }_{j=1}^W{e}^{s\left(w_t,j\right)}}$$

其中，s(,) 得分函数(scoring function)把 $(w_t,w_c)$评估为一个实数值。

1.2 分层Softmax

词汇$y$量很大时，softmax归一化很耗时，分层Softmax用树的层级结构来代替扁平化的标准Softmax。

霍夫曼树
霍夫曼树建立的过程是基于词频，它把词频高的单词尽量靠近根节点。具体实现是，先把词频最低的两个词用一个树表示，两个词频相加为这棵树新的词频（把这颗树当作一个单词）；再重新选取词频最低的两个词，继续构建树，直到所有单词表示完成。

在word2vec中，我们采用了二元逻辑回归的方法，即规定沿着左子树走，那么就是负类(霍夫曼树编码1)，沿着右子树走，那么就是正类(霍夫曼树编码0)。判别正类和负类的方法是使用sigmoid函数，即：
$$P(+)=\sigma \left(x_w^T\theta \right)=\frac{1}{1+e^{?x_w^T\theta }}$$

计算$P(y=j)$时，只需计算一条路径上所有节点的概率值。

$$\begin{array}{rl}\mathrm{P}\left(y_2\right)& =\mathrm{P}\left(n\left(y_2,1\right),\text{ left }\right)?\mathrm{P}\left(n\left(y_2,2\right),\text{ left }\right)?\mathrm{P}\left(n\left(y_2,3\right),\text{ right }\right)\\ & =\sigma \left({\theta }_{n\left(y_2,1\right)}^{T}X\right)?\sigma \left({\theta }_{n\left(y_2,2\right)}^{T}X\right)?\sigma \left(?{\theta }_{n\left(y_2,3\right)}^{T}X\right)\end{array}$$

其中，树的不同节点${\theta }_{n(,)}$也不同。

关于分层Softmax，可以看刘建平的博客.

1.3 负采样
Negative Sampling.
在Skip-gram模型中，预测上下文单词(context words)可以看做一系列的二分类任务。目标是独立预测当前(center word, context word)对是否包含上下文单词。负样本是随机从单词库根据出现的频率加权采样得到的单词集。

$$\log \left(1+e^{?s\left(w_t,w_c\right)}\right)+\sum _{n\in {\mathcal{N}}_{t,c}}\log \left(1+e^{s\left(w_t,n\right)}\right)$$

也可写成:
$$\sum _{t=1}^T?\sum _{c\in {\mathcal{C}}_t}?\left(s\left(w_t,w_c\right)\right)+\sum _{n\in {\mathcal{N}}_{t,c}}?\left(?s\left(w_t,n\right)\right)?$$

关于得分函数s，可以定义为：
$$s\left(w_t,w_c\right)={\mathbf{u}}_{w_t}^{?}{\mathbf{v}}_{w_c}$$

其中，$u,v$分别是单词$w_t,w_c$的向量表示。

关于负采样的概率：
随机选择反例样本，其概率通常设定为语料库各词频的3/4次幂。这样，增加了低频样本采样的概率。

2. FastText模型

FastText模型生成词的Embedding。

2.1 子单词模型
subword model,考虑单词的内部结构.

字符的n-grams,比如，对单词 where, n=3, 那么，
表示有：
<wh, whe, her, ere, re>
得分函数为：
$$s(w,c)=\sum _{g\in {\mathcal{G}}_w}{\mathbf{z}}_g^{?}{\mathbf{v}}_c$$

这里，$z_g$代表 单词w 在 g-grams 下的向量表示。

好处：
（1）对于低频词生成的词向量会更好，n-gram可以和其他词共享；
（2）对于训练词库之外的单词，仍然可以构建它们的词向量。叠加它们的字符级n-gram 向量。

2.2 模型结构

FastText架构和Word2Vec的CBOW模型相似，FastText模型只有3层：输入层，隐含层，输出层（Hierarchical Softmax），输入都是多个经向量表示的单词，输出都是一个特定的target，隐含层都是多个词向量的叠加平均。

不同的是 ：
（1）CBOW的输入是目标单词的上下文，fastText的输入是多个单词及其n-gram特征，这些特征用来表示单个文档；
（2）CBOW的输入单词被onehot编码过，fastText的输入特征是被embedding过；
（3）CBOW的输出是目标词汇，fastText的输出是文档对应的类标。

fastText的核心思想就是：将整篇文档的词及n-gram向量叠加平均得到文档向量，然后使用文档向量做softmax多分类。这中间涉及到两个技巧：字符级n-gram特征的引入以及分层Softmax分类。

模型前半部分，叠加构成文档的所有词及n-gram的词向量，取平均，生成用来表征文档的词向量。
模型的后半部分，用Softmax分类器来输出每个词向量的类别。

3 总结

FastText效果好的原因：使用词Embedding和字符级n-gram，使得，轻量级的网络取得较好的结果。

Q1：和word2vec的不同：

fastText优点：

适合大型数据+高效的训练速度：能够训练模型“在使用标准多核CPU的情况下10分钟内处理超过10亿个词汇”

支持多语言表达：利用其语言形态结构，fastText能够被设计用来支持包括英语、德语、西班牙语、法语以及捷克语等多种语言。FastText的性能要比时下流行的word2vec工具明显好上不少，也比其他目前最先进的词态词汇表征要好。

专注于文本分类，在许多标准问题上实现当下最好的表现（例如文本倾向性分析或标签预测）。

---

reference：

1. 机器之心文章；
2. 原论文 Bag of Tricks for Efficient Text Classification；
3. 原论文2 Enriching Word Vectors with Subword Information;
4. Github fasttext code;
5. 刘建平的博客;