一. 前言
自然语言处理(NLP)是机器学习，人工智能中的一个重要领域。文本表达是 NLP中的基础技术，文本分类则是 NLP 的重要应用。在 2016 年， Facebook Research 开源了名为 fasttext[1] 的文本表达和分类的计算库。 fasttext 是基于文章 [2], [3], [4] 所提出算法的实现，针对变形词汇表达，线性分类优化提供了优秀的解决方案。 本文试图梳理 FastText 在文本表达和文本分类方面的工作，并进行实践。
二. 词嵌入
1. 背景介绍
词表达是 NLP 处理中的关键技术。常见的方式如 one-hot，使用了高维稀疏向量表示词汇，这样的特征可以反映词出现的频率，却不能反映词之间的关系。与此对应，词嵌入技术将词汇的上下文关系嵌入一个低维空间，其中比较有代表性的方法如 word2vec [5]， GloVe[6]。本段落将分析 word2vec 的原理。
2. word2vec
word2vec 将词的上下文关系嵌入到低维空间。更具体而言，word2vec 将词的上下文关系转换为分类关系，并以此同时训练词嵌入向量和 logistic regression 分类器。
1. 逻辑回归
logistic regression 是经典的线性分类模型。广义上而言，线性模型由三个部分组成， 1. 输入向量 2. 线性系数 3. 偏移(bias)，而 bias 可以进一步表示成线性系数。所以，二分类的线性分类问题可以表示为输入 $x$ 和系数 $w$ 的内积结果 $w^Tx$，结果的正负决定了数据的类别。分类器参数通过最小化损失函数 $l(y, w^Tx)$来完成，不同的损失函数定义了不同的分类模型。
下面列举了svm， lr 的损失函数，其中 $y\in \{-1, 1\}$
logit : $\Sigma_{i=1}^N ln(1 + e^{-y_i w^Tx_i})$
svm : $\Sigma_{i=1}^N max(0, 1- y _iw^Tx_i) + \lambda||w||^2$
logistic regression 也广泛地应用在多分类问题中，通过 softmax 函数计算数据属于每个类别的概率完成分类。因为分类神经网络的输出层通常也设定为 softmax 函数，所以多分类 lr 也可以表示为浅层神经网络。
下面我们分析 word2vec 如何将词的上下文关系转化为分类任务。
2. skip-gram
我们将词的上下文定义为以词 $w_i$ 为中心，窗口为 $k$ 前后范围内的词 $C_i = {w_{i-k}, w_{i-k+1}, ..., w_{i-1}, w_{i+1}, ... w_{i+k}}$。
skip-gram 将词之间的关系变成了 $|V|$ 多分类问题，其中 $|V|$ 是词库大小。每个词有两个变量 $x_i, w_i$，前者为词嵌入向量，后者是线性分类器的系数，在相关文章中又称为上下文向量。
skip-gram 用中心词汇来预测其上下文，如下图：
3. cbow
Continuous bag of words(cbow) 是与 skip-gram 相对应的另一种将上下文转化为分类任务的方式。
上图显示 cbow 用上下文词向量的加和结果来预测其中心词汇，其它的方式还有拼接。需要注意的是拼接的方式会导致上下文向量 $c_i$ 维度增大 $2 k$ 倍数， $k$ 为上下文窗口。
4. 针对多分类的计算优化
word2vec 将上下文关系转化为多分类任务，进而训练逻辑回归模型，这里的类别数量是 $|V|$ 词库大小。通常的文本数据中，词库少则数万，多则百万，在训练中直接训练多分类逻辑回归并不现实。
word2vec [5] 中提供了两种针对大规模多分类问题的优化手段， negative sampling 和 hierarchical softmax。以 skip-gram 为例，中心词对上下文的词类是正面例子，对所有其它的词则是负面例子。在优化中，negative sampling 只更新少量负面类，从而减轻了计算量。hierarchical softmax 将词库表示成前缀树，从树根到叶子的路径可以表示为一系列二分类器，一次多分类计算的复杂度从 $|V|$ 降低到了树的高度。
3. 总结
词嵌入技术将词的上下文关系嵌入到低维空间。word2vec 将词的局部上下文转化为了多分类任务，从而训练逻辑回归模型，并将逻辑回归模型中的输入部分作为词嵌入输出。
三. FastText 子词嵌入
1. 背景介绍
词嵌入技术在 NLP 领域发挥了越来越大的作用，相较于 one-hot 特征，词嵌入具有维度低，体现词间关系等特点。但传统的词嵌入技术忽略了词的微变形特性，如英语中动词的第三人称，进行时或过去时变形。针对这个问题， [2] 提出使用子词来学习词的表达，每个词由内部的 n-gram 字母串组成。在中文处理中， [7] 提出了类似的算法。
2. FastText 的实现
FastText 的子词嵌入在 word2vec 的基础上，引入了子词这个因素，从而使得词的微变形关系也能映射到嵌入空间中。
1. 子词
在 fasttext 中，每个词被看做是 n-gram 字母串包。为了区分前后缀情况，"<"， ">" 符号被加到了词的前后端。除了词的子串外，词本身也被包含进了 n-gram 字母串包。以 where 为例，$n=3$ 的情况下，其子串分别为
<wh, whe, her, ere, re>，以及其本身 <where>
注意，这里的 her 与单词 <her> 是不同的。
现在我们看看 fasttext 具体是怎么计算子串的。
void Dictionary::initNgrams() {
for (size_t i = 0; i < size_; i++) {
// 加入前后缀符号 <, >
std::string word = BOW + words_[i].word + EOW;
// 词本身作为特殊子串加入包中
words_[i].subwords.push_back(i);
// 计算并将词子串加入包中
computeNgrams(word, words_[i].subwords);
}
}
// 计算词子串
void Dictionary::computeNgrams(const std::string& word,
std::vector<int32_t>& ngrams,
std::vector<std::string>& substrings) const {
for (size_t i = 0; i < word.size(); i++) {
std::string ngram;
if ((word[i] & 0xC0) == 0x80) continue;
for (size_t j = i, n = 1; j < word.size() && n <= args_->maxn; n++) {
ngram.push_back(word[j++]);
// 将 utf-8 编码数据部分推入 ngram
while (j < word.size() && (word[j] & 0xC0) == 0x80) {
ngram.push_back(word[j++]);
}
if (n >= args_->minn && !(n == 1 && (i == 0 || j == word.size()))) {
// fasttext 使用 open hash 进行 string->int 转换
int32_t h = hash(ngram) % args_->bucket;
ngrams.push_back(nwords_ + h);
substrings.push_back(ngram);
}
}
}
}
在 fasttext 中，minn 和 maxn 参数控制了子串的长度，其默认值分别为 3, 6。再以 where 为例，在默认子串参数情况下，其子串包内容为:
<wh, <whe, <wher, <where, whe, wher, where, where>, her, here, here>, ere, ere>, re> 以及自身 <where>
下面我们看 fasttext 是如何用子串来构造词嵌入的，这里注意每个子串也有自身的嵌入表示。
void Model::computeHidden(const std::vector<int32_t>& input, Vector& hidden) const {
assert(hidden.size() == hsz_);
hidden.zero();
for (auto it = input.cbegin(); it != input.cend(); ++it) {
if(quant_) {
// product quantization 优化
// 子串加和
hidden.addRow(*qwi_, *it);
} else {
// 子串加和
hidden.addRow(*wi_, *it);
}
}
// 平均
hidden.mul(1.0 / input.size());
}
代码非常简明直接，每个词是其子串嵌入表示的加和平均。
fasttext 的另一个优势，是学习未知词的表达。以 working 为例，如果这个词在学习文本中没有出现过，但文本包含了 work, 和 ing，那么 working 的词嵌入向量也能够合理地计算出来。
2. skip-gram
一个词的嵌入是其子串嵌入的加和平均。当这个嵌入表示计算出来后，后续步骤与 word2vec 的 skip-gram 相同。下面是 fasttext 的 skip-gram 实现代码：
void FastText::skipgram(Model& model, real lr,
const std::vector<int32_t>& line) {
std::uniform_int_distribution<> uniform(1, args_->ws);
for (int32_t w = 0; w < line.size(); w++) {
// 窗口大小
int32_t boundary = uniform(model.rng);
const std::vector<int32_t>& ngrams = dict_->getNgrams(line[w]);
for (int32_t c = -boundary; c <= boundary; c++) {
if (c != 0 && w + c >= 0 && w + c < line.size()) {
// 通过 ngrams 计算 line[w] 的表示，通过逻辑回归优化 ngrams 的嵌入表示
model.update(ngrams, line[w + c], lr);
}
}
}
}
我们来详细看看 Model::update 函数是怎么用逻辑回归来优化 ngrams 的嵌入表示
void Model::update(const std::vector<int32_t>& input, int32_t target, real lr) {
assert(target >= 0);
assert(target < osz_);
if (input.size() == 0) return;
// 子串加权平均得到词嵌入表示
computeHidden(input, hidden_);
// 针对分类问题的 3 种处理
// 1. negative sampling 优化
if (args_->loss == loss_name::ns) {
loss_ += negativeSampling(target, lr);
}
// 2. hierarchical softmax 优化
else if (args_->loss == loss_name::hs) {
loss_ += hierarchicalSoftmax(target, lr);
}
// 3. 直接计算多分类逻辑回归
// 在文本分类模式下使用
else {
loss_ += softmax(target, lr);
}
nexamples_ += 1;
// 逻辑回归产生了导数，在文本分类情况下导数向量需要除以子串数量
if (args_->model == model_name::sup) {
grad_.mul(1.0 / input.size());
}
// 将导数直接加到子串向量中
for (auto it = input.cbegin(); it != input.cend(); ++it) {
wi_->addRow(grad_, *it, 1.0);
}
}
在第二段，我们简单介绍了针对大量多分类的优化策略, negative sampling 和 hierarchical sampling。这里我们看看 fasttext 是怎样实现这些策略。
// 根据词频构构建采样表
void Model::initTableNegatives(const std::vector<int64_t>& counts) {
real z = 0.0;
for (size_t i = 0; i < counts.size(); i++) {
z += pow(counts[i], 0.5);
}
// 每个词类在采样表中数量与其词频开方成比例
for (size_t i = 0; i < counts.size(); i++) {
real c = pow(counts[i], 0.5);
for (size_t j = 0; j < c * NEGATIVE_TABLE_SIZE / z; j++) {
negatives.push_back(i);
}
}
std::shuffle(negatives.begin(), negatives.end(), rng);
}
// 负采样
real Model::negativeSampling(int32_t target, real lr) {
real loss = 0.0;
grad_.zero();
// 负采样 args_->neg 个类别
for (int32_t n = 0; n <= args_->neg; n++) {
if (n == 0) {
// 将当前词作为正面例子对 target 类进行二分逻辑回归训练
loss += binaryLogistic(target, true, lr);
} else {
// 将当前词作为负面例子对负采样类进行二分逻辑回归训练
loss += binaryLogistic(getNegative(target), false, lr);
}
}
return loss;
}
// 负采样一个类
int32_t Model::getNegative(int32_t target) {
int32_t negative;
// 轮询采样表
do {
negative = negatives[negpos];
negpos = (negpos + 1) % negatives.size();
} while (target == negative);
return negative;
}
下面我们看看 hierarchical softmax 的实现
// 根据词频构造前缀树，因为树的内部节点数量为 |V| - 1 所以可以用 |V| * 2 的数组存储树结构
void Model::buildTree(const std::vector<int64_t>& counts) {
tree.resize(2 * osz_ - 1);
for (int32_t i = 0; i < 2 * osz_ - 1; i++) {
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
tree[i].count = 1e15;
tree[i].binary = false;
}
for (int32_t i = 0; i < osz_; i++) {
tree[i].count = counts[i];
}
int32_t leaf = osz_ - 1;
int32_t node = osz_;
for (int32_t i = osz_; i < 2 * osz_ - 1; i++) {
int32_t mini[2];
for (int32_t j = 0; j < 2; j++) {
if (leaf >= 0 && tree[leaf].count < tree[node].count) {
mini[j] = leaf--;
} else {
mini[j] = node++;
}
}
tree[i].left = mini[0];
tree[i].right = mini[1];
tree[i].count = tree[mini[0]].count + tree[mini[1]].count;
tree[mini[0]].parent = i;
tree[mini[1]].parent = i;
tree[mini[1]].binary = true;
}
for (int32_t i = 0; i < osz_; i++) {
std::vector<int32_t> path;
std::vector<bool> code;
int32_t j = i;
while (tree[j].parent != -1) {
path.push_back(tree[j].parent - osz_);
code.push_back(tree[j].binary);
j = tree[j].parent;
}
paths.push_back(path);
codes.push_back(code);
}
}
// 用 hierarchical softmax 进行多分类计算
real Model::hierarchicalSoftmax(int32_t target, real lr) {
real loss = 0.0;
grad_.zero();
// 词的 0，1 表示
const std::vector<bool>& binaryCode = codes[target];
// 词到树根的路径
const std::vector<int32_t>& pathToRoot = paths[target];
for (int32_t i = 0; i < pathToRoot.size(); i++) {
// 路径上的节点对应二分类， 0,1 编码决定分类
// 用二分逻辑回归进行训练
loss += binaryLogistic(pathToRoot[i], binaryCode[i], lr);
}
return loss;
}
最后我们看一下二分逻辑回归的实现。
// 用一个正/负面例子更新二分逻辑回归模型
real Model::binaryLogistic(int32_t target, bool label, real lr) {
real score = sigmoid(wo_->dotRow(hidden_, target));
real alpha = lr * (real(label) - score);
grad_.addRow(*wo_, target, alpha);
wo_->addRow(hidden_, target, alpha);
if (label) {
return -log(score);
} else {
return -log(1.0 - score);
}
}
3. cbow
第二段讲解了 cbow 的原理是用中心词的上下文来预测中心词, 这里我们看看 fasttext 是如何实现 cbow 的。
void FastText::cbow(Model& model, real lr,
const std::vector<int32_t>& line) {
std::vector<int32_t> bow;
std::uniform_int_distribution<> uniform(1, args_->ws);
for (int32_t w = 0; w < line.size(); w++) {
int32_t boundary = uniform(model.rng);
bow.clear();
for (int32_t c = -boundary; c <= boundary; c++) {
// 将上下文的子字符串加入包中
if (c != 0 && w + c >= 0 && w + c < line.size()) {
const std::vector<int32_t>& ngrams = dict_->getNgrams(line[w + c]);
bow.insert(bow.end(), ngrams.cbegin(), ngrams.cend());
}
}
// 用所有子字符串来预测中心词，从而更新参数
model.update(bow, line[w], lr);
}
}
fasttext 的处理非常简洁，将上下文的子串全部加和平均作为输入去预测中心词。
3. 总结
fasttext 利用子词改良了词嵌入的质量，在嵌入学习中考虑了词的内部结构。在具体实现中， fasttext 用子词向量的加和平均表示词向量, 提供了 skip-gram 和 cbow 模式训练词嵌入表达。
四. FastText 线性文本分类优化
1. 背景介绍
对于文本分类而言，线性分类器往往能够达到非常优秀，媲美深度模型的效果。通常，线性模型的参数数量与词库大小相关，导致模型规模巨大。 fasttext 针对线性分类器模型进行了诸多优化，在不显著损失分类器精度的情况下，减少了内存使用和计算时间。
2. fasttext 分类模型架构
fasttext 的词嵌入是通过分类学习完成的，所以词嵌入和文本分类模型可以用下图统一表示。
其中 $x_1, ..., x_N$ 表示一个文本中的 ngram 向量，一个文本的表示是所有 ngram 的加和平均。这和前文中提到的 cbow 相似，cbow 用上下文的 ngram 去预测中心词，而此处用全部的 ngram 去预测指定类别。
与前文词嵌入模型一样， fasttext 模型在进行文本分类监督训练时，既学习词嵌入表达，也学习分类器线性系数。
3. 优化
1. 子空间量化
product quantization [8] 是一种保存数据间距离的压缩技术。PQ 用一个码本来近似数据，与传统的 keams 训练码本不同的是， PQ 将数据空间划分为 k 个子空间，并分别用 kmeans 学习子空间码本。数据的近似和重建均在子空间完成，最终拼接成结果。
在 fasttext 中，子空间码本大小为 256，可以用 1 byte 表示。子空间的数量在 [2, d/2] 间取值。
除了用 PQ 对数据进行量化压缩，fasttext 还提供了对分类系数的 PQ 量化选项。
PQ 的优化能够在不影响分类其表现的情况下，将分类模型压缩为原大小的 $\frac{1}{10}$。
2. 裁剪字典内容
fasttext 提供了一个诱导式裁剪字典的算法，保证裁剪后的字典内容覆盖了所有的文章。具体而言，fasttext 存有一个保留字典，并在线处理文章，如果新的文章没有被保留字典涵盖，则从该文章中提取一个 norm 最大的词和其子串加入字典中。
字典裁剪能够有效将模型的数量减少，甚至到原有的 $\frac{1}{100}$。
4. 总结
fasttext 利用 Product Quantization 对字典中的 词嵌入向量进行了压缩，并使用诱导式字典方法，构造涵盖全部文本的字典。两者结合，能够在不明显损害分类算法表现的情况下，将分类模型大小减小数百倍 。
五. 实践
本段我们对词嵌入进行实践。词嵌入的比较有两种方式，直接比较是验证词表达保存了人为标注的词间关系，间接比较则是通过使用嵌入表达向量进行进一步学习，比如情绪预测[5]，通过模型的表现判断词嵌入的质量。
我们用中文维基数据 [9] 进行了训练，fasttext 的参数使用默认值， epoch 设置为50。此外 facebook 还提供了训练好的多国语言表达 [10].
以下我们分别用 nn(最近邻) 对中文维基训练结果进行实践：
// 乒乓球的近似词汇
Query word? 乒乓球
壁球 0.837808
曲棍球 0.792717
网球 0.792332
排球 0.789665
手球 0.780589
田径 0.780279
桌球 0.778775
举重 0.776161
沙滩排球 0.775708
乒乓球队 0.772797
// "男乒乓球" 并不存在， fasttext 仍然可以得到合理结果
Query word? 男乒乓球
乒乓球 0.767142
中国男子乒乓球队 0.725763
兵乓球 0.691391
体操 0.688922
张怡宁 0.688578
陈若琳 0.681761
跳水队 0.678217
打乒乓球 0.677547
王楠 0.671578
吴敏霞 0.669105
六. 总结
fasttext 是 facebook 开源的关于文本表达和文本分类的计算库。fasttext 结合词的子串信息计算词表达，提高了对微变形词汇的学习。针对文本分类模型， fasttext 使用了子空间量化和字典裁剪的策略，在不损失模型精度的情况下，将模型大小缩减数百倍。
在 fasttext 之上，可以做进一步优化，一个方向是在文本分类模型中，文本表达用类似 tf-idf 的方式对词进行加权平均。在字典裁剪算法上，一个涵盖所有文本的词并不一定有区分能力，比如 "the" 这个单词，可以尝试从保留区分能力的视角来保留字典。
七. 引用
[1] https://github.com/facebookresearch/fastText
[2] Bojanowski, Piotr and Grave, Edouard and Joulin, Armand and Mikolov, Tomas. "Enriching Word Vectors with Subword Information".
[3] Joulin, Armand and Grave, Edouard and Bojanowski, Piotr and Mikolov, Tomas. "Bag of Tricks for Efficient Text Classification".
[4]Joulin, Armand and Grave, Edouard and Bojanowski, Piotr and Douze, Matthijs and Jegou, Herve and Mikolov, Tomas. "FastText.zip: Compressing text classification models".
[5] Mikolov, Tomas, et al. "Efficient Estimation of Word Representations in Vector Space".
[6] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. "GloVe: Global Vectors for Word Representation".
[7] Xinxiong Chen, Lei Xu, Zhiyuan Liu, Maosong Sun, and Huanbo Luan. 2015. Joint learning of character and word embeddings. In Proc. IJCAI.
[8] Product quantization for nearest neighbor search. H Jegou, M Douze, C Schmid. IEEE Transactions on Pattern Analysis and Machine Intelligence
[9] https://dumps.wikimedia.org/zhwiki/
[10] https://github.com/facebookresearch/fastText/blob/master/pretrained-vectors.md
