[转] fastText
mark~
from : https://www.jiqizhixin.com/articles/2018-06-05-3
fastText的起源
fastText是FAIR(Facebook AIResearch) 在2016年推出的一款文本分类与向量化工具。它的官网(fasttext.cc)上是这样介绍的:
FastText is an open-source, free, lightweightlibrary that allows users to learn text representations and text classifiers.It works on standard, generic hardware. Models can later be reduced in size toeven fit on mobile devices.
fastText开源、免费、轻量级,适用于文本分类和文本向量化表示场景,运行于标准硬件环境。裁剪压缩过的模型甚至可以轻松跑在移动设备上。
fastText最惊艳的地方在于,和最前沿深度神经网络模型相比,它在分类精度等指标毫不逊色的情况下,把训练和推断速度降低了几个数量级!按Facebook的报告,在普通多核CPU上,10亿词的文本训练时间小于10分钟,50万句子分到31.2万类别用时小于1分钟。
下面这张图可以清楚地看到这一点,深度模型天级的训练时间被压榨到了秒级!
简单介绍一下fastText的主要作者,这位高颜值的Facebook科学家Tomas Mikolov小哥。他2012年到2014年就职于Google,随后跳到了Facebook至今。
他名扬天下的,主要是以下三篇重要论文:
1.Efficient Estimation of WordRepresentation in Vector Space, 2013 —— 这篇是word2vec的开蒙之作;
2.Distributed Representations ofSentences and Documents, 2014 —— 这篇将词向量的思想扩展到了段落和文档上;
3.Enriching Word Vectors withSubword Information, 2016 —— 这篇和fastText相关,引入了词内的n-gram信息,丰富了词向量的语义。
fastText能够做到效果好,速度快,主要依靠两个秘密武器:一是利用了词内的n-gram信息(subword n-gram information),二是用到了层次化Softmax回归(Hierarchical Softmax)的训练trick。我们分别介绍一下。
Subword n-gramlnformation
在fastText的工作之前,大部分的文本向量化的工作,都是以词汇表中的独立单词作为基本单元来进行训练学习的。这种想法非常自然,但也会带来如下的问题:
· 低频词、罕见词,由于在语料中本身出现的次数就少,得不到足够的训练,效果不佳;
· 未登录词,如果出现了一些在词典中都没有出现过的词,或者带有某些拼写错误的词,传统模型更加无能为力。
fastText引入了subword n-gram的概念来解决词形变化(morphology)的问题。直观上,它将一个单词打散到字符级别,并且利用字符级别的n-gram信息来捕捉字符间的顺序关系,希望能够以此丰富单词内部更细微的语义。我们知道,西方语言文字常常通过前缀、后缀、字根来构词,汉语也有单字表义的传统,所以这样的做法听起来还是有一定的道理。
举个例子。对于一个单词“google”,为了表达单词前后边界,我们加入<>两个字符,即变形为“<google>”。假设我们希望抽取所有的tri-gram信息,可以得到如下集合:G = { <go, goo, oog,ogl, gle, le>}。在实践中,我们往往会同时提取单词的多种n-gram信息,如2/3/4/5-gram。这样,原始的一个单词google,就被一个字符级别的n-gram集合所表达。
在训练过程中,每个n-gram都会对应训练一个向量,而原来完整单词的词向量就由它对应的所有n-gram的向量求和得到。所有的单词向量以及字符级别的n-gram向量会同时相加求平均作为训练模型的输入。
从实验效果来看,subword n-gram信息的加入,不但解决了低频词未登录词的表达的问题,而且对于最终任务精度一般会有几个百分点的提升。唯一的问题就是由于需要估计的参数多,模型可能会比较膨胀。不过,Facebook也提供了几点压缩模型的建议:
· 采用hash-trick。由于n-gram原始的空间太大,可以用某种hash函数将其映射到固定大小的buckets中去,从而实现内存可控;
· 采用quantize命令,对生成的模型进行参数量化和压缩;
· 减小最终向量的维度。
需要注意的是以上几种方法都会以一定的精度损失为代价,尤其是维度的压缩,具体可以实践中再权衡。
Hierarchical Softmax
另一个效率优化的点是所谓的层次化Softmax。
Softmax大家都比较熟悉,它是逻辑回归(logisticregression)在多分类任务上的推广,是我们训练的神经网络中的最后一层。一般地,Softmax以隐藏层的输出h为输入,经过线性和指数变换后,再进行全局的归一化处理,找到概率最大的输出项。当词汇数量V较大时(一般会到几十万量级),Softmax计算代价很大,是O(V)量级。
层次化的Softmax的思想实质上是将一个全局多分类的问题,转化成为了若干个二元分类问题,从而将计算复杂度从O(V)降到O(logV)。
每个二元分类问题,由一个基本的逻辑回归单元来实现。如下图所示,从根结点开始,每个中间结点(标记成灰色)都是一个逻辑回归单元,根据它的输出来选择下一步是向左走还是向右走。下图示例中实际上走了一条“左-左-右”的路线,从而找到单词w₂。而最终输出单词w₂的概率,等于中间若干逻辑回归单元输出概率的连乘积。
至此,我们还剩下两个问题,一是如何构造每个逻辑回归单元的输入,另一个是如何建立这棵用于判断的树形结构。
逻辑回归单元的参数
每个逻辑回归单元中,sigmoid函数所需的输入实际上由三项构成,如下公式所示:
记号说明如下:
1. ⟦x⟧是一个特殊的函数,如果下一步需要向左走其函数值定义为1,向右则取-1。在训练时,我们知道最终输出叶子结点,并且从根结点到叶子结点的每一步的路径也是确定的。
2. v' 是每个内部结点(逻辑回归单元)对应的一个向量,这个向量可以在训练过程中学习和更新。
3. h 是网络中隐藏层的输出。
因此,我们以隐藏层的输出、中间结点对应向量以及路径取向函数为输入,相乘后再经过sigmoid函数,得到每一步逻辑回归的输出值。
霍夫曼树的构造
Hierarchical Softmax采用的树型结构实际上是一棵二叉霍夫曼树。
霍夫曼树是在解决通信编码过程中引入的。在通信过程中,需要将字符信息编码成为0/1二进制串。显然,给出现频繁的字符较短的编码,出现较少的字符以较长的编码,是最经济的方案。通过一棵霍夫曼树的构造,我们让越频繁的字符离根结点越近,使得最终的通信编码最短。
霍夫曼树的构造步骤如下:
在做Hierarchical Softmax之前,我们需要先利用所有词汇(类别)及其频次构建一棵霍夫曼树。这样,不同词汇(类别)作为输出时,所需要的判断次数实际上是不同的。越频繁出现的词汇,离根结点越近,所需要的判断次数也越少。从而使最终整体的判断效率更高。
fastText和传统CBOW模型对比
这里假设你对word2vec的CBOW模型比较熟悉,我们来小结一下CBOW和fastText的训练过程有什么不同。下面两张图分别对应CBOW和fastText的网络结构图。
两者的不同主要体现在如下几个方面:
· 输入层:CBOW的输入是目标单词的上下文并进行one-hot编码,fastText的输入是多个单词embedding向量,并将单词的字符级别的n-gram向量作为额外的特征;
· 从输入层到隐藏层,CBOW会将上下文单词向量叠加起来并经过一次矩阵乘法(线性变化)并应用**函数,而fastText省略了这一过程,直接将embedding过的向量特征求和取平均;
· 输出层,一般的CBOW模型会采用Softmax作为输出,而fastText则采用了Hierarchical Softmax,大大降低了模型训练时间;
· CBOW的输出是目标词汇,fastText的输出是文档对应的类标。
小结
fastText已经在云脑科技内部多个项目中得到了实践运用,包括短文本分类任务、实体识别消歧任务、同义近义简称别名挖掘任务、推荐系统中的文本向量化特征提取等等。
实践经验表明,fastText更适用于样本数量大、类别标签多的任务,一般能够得到很好的效果,大多数情况下强于传统的BOW + LR/SVM分类器。更重要的是,训练效率非常之高。
参考资料
1. 1607.01759Bag of Tricks for Efficient Text Classification
2. 1607.04606Enriching Word Vectors with Subword Information
3. [1411.2738]word2vec Parameter Learning Explained
4. 技术干货丨fastText原理及实践 - 云+社区 - 腾讯云