前言

同学们好，这一节我们将学习文档分类的第一个算法——FastText。那么FastText是一个什么东西呢？它是facebook开源的一个词向量与文本分类工具，在2016年开源，典型应用场景是“带监督的文本分类问题”，提供简单而高效的文本分类和表征学习的方法，性能比肩深度学习而且速度更快。简单来说，它就是一个文档分类器。

说到FastText,它和我们上一章讲过word2vec词向量算法还有这密切的联系，话说Fasttext的其中一个作者是Thomas Mikolov，熟悉word2vec的同学应该很清楚这个名字，没错，他也是word2vec的其中一个作者，正是他当年在Google带领一个团队鼓捣出来了word2vec，很好的解决了传统词袋表示的缺点，极大地推动了NLP领域的发展。后来这哥们跳槽到了FaceBook，才有了现在的FastText。从“血缘”角度来看，FastText和word2vec可以说是一脉相承。

1、FastText架构

在讲解FastText的模型架构之前，我们得先回顾一下word2vec中的CBOW的架构，它们长得非常相似，因为它们的作者都是Facebook的科学家Tomas Mikolov，而且确实fastText也算是word2vec所衍生出来的。

下面我们先看一下CBOW的架构：

在CBOW中，模型将上下文关系转化为多分类任务，进而训练逻辑回归模型，这里的类别数量|V|词库大小。它的输入是中心词上下的d个词，输出是这个中心词。这里，FastText的模型结构是跟CBOW非常相似的，如下图：

Fasttext也是一个具有三层结构的简版神经网络。不同的是，cbow用上下文去预测中心词，而此处用全部向量去预测指定类别。看到这里，其实我们可以发现，fasttext的模型结构和cbow几乎没有差别，最大的不同就是两个模型的输入和输出不一样。我们先来看输出，cbow输出的中心词，而fasttext输出的指定类别。输入也有着不一样的地方，之前我们学过cbow的输入是经过one-hot编码的词向量，而在fasttext的输入是文本中的one-hot向量+n-gram向量，每个特征是词向量的平均值。至于什么是n-gram向量，我们下面将会一一道来。

2、N-gram向量

在讲解word2vec的时候，我们知道使用的是cbow(连续词袋模型)。虽然这种模型在一定程度上也能学得一些词的特征。但是我们知道一个句子是由一系列有序的词组成的，词与词之间是有顺序的，但是cbow并没有把这个因素考虑进去。譬如，“我 爱 她” 这句话中的词袋模型特征是 "我"，"爱", "她"。这些特征和句子 “她 爱 我” 的特征是一样的,因为“她爱我”的bag（词袋）中也是只包含"我","爱","她"这三个词。为了处理词顺序丢失的问题，FastText增加了N-gram的特征。

n-gram是一种统计语言模型。它基于这样一个假设：第n个词出现与前n-1个词相关，而与其他任何词不相关。（这也是隐马尔可夫当中的假设。）整个句子出现的概率就等于各个词出现的概率乘积。那么在fasttext里面的n-gram向量是如何表示的呢？我们来举个例子，现在有一个文档：

• "苹果 是 一家 伟大的 公司"  现在我们对其进行n-gram处理，这里n-gram中的n为2，那么就会得到以下的组合：
• “苹果 是”
• “是 一家”
• “一家 伟大的”
• “伟大的 公司”

通过n-gram处理之后，我们获取了4个组合。同样的，我们对其进行one-hot处理，便会得到4个向量。那么fasttext是怎么利用上这些向量的呢？看下面这个图：

一开始我们构造和one-hot向量一样的输入，经过隐藏层之后就会得到一个word Embdeddings矩阵和N-gram Embeddings矩阵。然后，将两个矩阵拼接起来去求和取平均。最后，利用softmax函数去预测标签。图中，橙色的部分就是ngram向量。不过在具体实现上，由于n-gram的量远比word大的多，完全存下所有的n-gram也不现实。FastText采用了Hash桶的方式，把所有的n-gram都哈希到buckets个桶中，哈希到同一个桶的所有n-gram共享一个embedding vector。如下图所示：

图中Win是Embedding矩阵，每行代表一个word或N-gram的embeddings向量，其中前V行是word embeddings，后Buckets行是n-grams embeddings。每个n-gram经哈希函数哈希到0-bucket-1的位置，得到对应的embedding向量。用哈希的方式既能保证查找时O(1)的效率，又可能把内存消耗控制在O(buckets * dim)范围内。不过这种方法潜在的问题是存在哈希冲突，不同的n-gram可能会共享同一个embedding。如果桶大小取的足够大，这种影响会很小。

由于fasttext中使用了n-gram特征，使得文档的局部词序可以被考虑在内，这对很多文本分类问题来说十分重要。举个例子，fastText能够学会“男孩”、“女孩”、“男人”、“女人”指代的是特定的性别，并且能够将这些数值存在相关文档中。然后，当某个程序在提出一个用户请求（假设是“我女友现在在儿？”），它能够马上在fastText生成的文档中进行查找并且理解用户想要问的是有关女性的问题。

3、层次SoftMax

在之前，我们提到过fasttext的一大特点是计算非常快。那它到底快在哪里呢？对于有大量类别的数据集，fastText使用了一个分层分类器（而非扁平式架构）。不同的类别被整合进树形结构中（想象下二叉树而非 list）。我们先看下面的图：

上图前面编码的过程部分和word2vec的结构是一模一样，但是解码的部分是用Embedding的向量通过一个哈夫曼树解出来最后的One-Hot向量。

这颗哈夫曼树在形式上跟我们在《数据结构》中学到的哈夫曼树没什么区别，它是在训练开始之前准备好的。如何构造这棵树呢？首先，先在训练样本中统计各个标签出现的频率，频率高的就编得靠根部一些，频率低的就编得离根部远一些。fastText 利用了类别（class）不均衡这个事实（一些类别出现次数比其他的更多），通过使用哈夫曼树建立用于表征类别的树形结构。因此，频繁出现类别的树形结构的深度要比不频繁出现类别的树形结构的深度要小，这也使得进一步的计算效率更高。

上图仅仅以示例中出现的这几个词为例画了个示意图，只有在叶子节点上的点才作为一个词汇，右下角画了一坨云——表示这个部分还要继续这样展开下去，不会是只有这么两层可能有几十层那么多，每个词的编码也更长一些。根据遍历的原则，当从根部走到“军事”这个节点的时候，由于经历了根节点“R”和1个“1”，1个“0”编码的，所以“军事”这个节点的二进制表示就是“10”。

用哈夫曼编码来编所有标签，构造在一棵哈夫曼树里面。哈夫曼编码的标签和One-Hot编码的标签是一一对应关系的——那当然是哈夫曼编码要短很多了。那么从Embedding的向量如何解码出一个标签的哈夫曼编码呢？请继续听我解释两分钟。

一个经过Word Embedding和N-gram Embedding后的编码，就是一个V维的向量。让这个向量在上面那颗哈夫曼树上的每一层的每一个节点都通过一个逻辑回归来选择方向，大于0.5走右边，小于0.5走左边。

这也就意味着，每一层上都有一个

的逻辑回归要做。这里的w和b肯定是未知的，图上我们用w1、w2这样的下标做了区分。可以想象，一开始每一层的w和b是随机初始化的，那么一个v通过逻辑回归的时候就很有可能走错路，比如“军事”的V进入这颗树后，很可能就直接走到“时尚”去了——因为它确实可能上来就映射到“00”这个节点去，这就是误差。误差大小就是损失函数的表达，对于逻辑回归我们就用逻辑回归的损失函数来表达损失就可以了。

因此，为了让每个标签都能顺利分对了类，对于构成误差的各层的w和b以及前面的W矩阵都要做梯度下降，这就是训练过程。用这种方式的好处是，更新的时候速度要比用矩阵解码快一些——相当于建立了一个优化更新过程的索引，对于类别偏斜比较厉害的样本集加速训练的效果要好一些。而且解释起来逻辑也更为明确些，就是不断做二分类的过程。

小结

  Fasttext相对于其它文本分类模型，如SVM，Logistic Regression和neural network等模型，fastText在保持分类效果的同时，大大缩短了训练时间。因此，它非常适合用来训练大型数据，能够训练模型“在使用标准多核CPU的情况下10分钟内处理超过10亿个词汇”。此外，Fasttext专注于文本分类，在许多标准问题上实现当下最好的表现（例如文本倾向性分析或标签预测）。至此，我们已经讲解了FastText的算法原理。如果对算法原理有疑问的同学欢迎在讨论区和我互动。