fastText源码分析以及使用

fastText源码分析

整体结构

fastText的代码整体结构如下图所示：

fasttext模块

主要功能是训练和预测。

数据结构

std::shared_ptr<Args> args_;
std::shared_ptr<Dictionary> dict_; 词典

std::shared_ptr<Matrix> input_; 输入：词向量
std::shared_ptr<Matrix> output_; 输出

std::shared_ptr<QMatrix> qinput_;
std::shared_ptr<QMatrix> qoutput_;

std::shared_ptr<Model> model_; 模型

std::atomic<int64_t> tokenCount_;
std::atomic<real> loss_;

train

train()

利用args_->input文件来初始化词典dict_(Dictionary对象)。
加载预训练的词向量初始化input_或者随机初始化input_；shape为[dict_->nwords()+args_->bucket, args_->dim]。
初始化output_，shape为[dict_->nlabels(), args_->dim](训练分类器)或者[dict_->nwords(), args_->dim](训练词向量)。
startThreads()开启线程，在线程里面训练。
利用input_、output_、arg_初始化model_。

startThreads()

用trainThread()函数初始化thread，并且开始训练。

trainThread()

根据线程数，将训练文件按照总字节数（utils::size）均分成多个部分.
利用input_、output_、arg_初始化model。每个线程里面的这些参数都共享，所以训练的时候都可以改变其值。
调用model.setTargetCounts()函数。具体调用model的实现。
在训练过程中，获取一行数据，然后根据不同的任务调用supervised(有监督学习（分类）),cbow(word2vec (CBOW)),skipgram(word2vec (SKIPGRAM))函数来进行模型更新。
以上三个函数均调用model模块的update函数。

supervised()：有监督学习-分类

model.update(line, labels[i], lr);

cbow()：word2vec-CBOW

model.update(bow, line[w], lr); bow为line[w]这个词的上下文词和词的n-gram。

skipgram()：word2vec-SKIPGRAM

model.update(ngrams, line[w + c], lr); 词和词的n-gram来预测这个词的上下文的所有的词。

predict

读取输入文件的每一行dict_->getLine(ifs, line, labels, model_->rng);
将一个词的n-gram加入词表，用于处理未登录词。(即便一个词不在词表里，我们也可以用它的word n-gram 来预测一个结果)
调用model模块的predict函数，获取k个最可能的分类model_->predict(line, k, predictions);

model模块

整体结构

fastText的代码整体结构如下图所示：

数据结构

std::shared_ptr<Matrix> wi_; fasttext的input_来初始化(多线程共享)。
std::shared_ptr<Matrix> wo_; fasttext的output_来初始化(多线程共享)。
std::shared_ptr<QMatrix> qwi_;
std::shared_ptr<QMatrix> qwo_; 
std::shared_ptr<Args> args_; fasttext的arg_来初始化(多线程共享)。

Vector hidden_; shape为[args->dim]
Vector grad_; shape为[args->dim]
Vector output_; shape为[wo->size(0)]，预测的结果向量。
real loss_;

int32_t hsz_; 值为args->dim
int32_t osz_; 值为wo->size(0)

int64_t nexamples_;
std::vector<real> t_sigmoid_;
std::vector<real> t_log_;
    
// used for negative sampling:
std::vector<int32_t> negatives_;
size_t negpos;

// used for hierarchical softmax:
std::vector< std::vector<int32_t> > paths;
std::vector< std::vector<bool> > codes;
std::vector<Node> tree;

struct Node {
  int32_t parent; 父节点
  int32_t left; 左孩子
  int32_t right; 右孩子
  int64_t count;
  bool binary; 是父节点的左边还是右边
};

对外接口

update()函数

该函数有三个参数，分别是“输入”，“类标签”，“学习率”。
输入是一个int32_t数组，每个元素代表一个词在dictionary里的ID。对于分类问题，这个数组代表输入的短文本，对于word2vec，这个数组代表一个词的上下文。
类标签是一个int32_t变量。对于word2vec来说，它就是带预测的词的ID，对于分类问题，它就是类的label在dictionary里的ID。因为label和词在词表里一起存放，所以有统一的ID体系。
首先判断target必须在合法范围内。
然后计算前向传播：输入层->隐层，由wi_到hidden_，得到hidden_向量的值。
接着根据输出层的不同结构，调用不同的函数，在各个函数中，不仅通过前向传播算出了loss_，还进行了反向传播，计算出了grad_和更新了wo_。调用本模块内的negativeSampling、hierarchicalSoftmax、softmax函数。将层次softmax和负采样统一抽象成多个二元logistic regression计算。
最后反向传播，将grad_上的梯度传播到wi_上的对应行。
注意：分层softmax时，wo_的行数为osz_-1，也就是非叶子节点个数。wo_矩阵表示的含义也是非叶子节点的参数。

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_); // 前向传播
  if (args_->loss == loss_name::ns) { // 前向传播+反向传播
    loss_ += negativeSampling(target, lr);
  } else if (args_->loss == loss_name::hs) {
    loss_ += hierarchicalSoftmax(target, lr);
  } 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);
  }
}

negativeSampling()函数

参数为int类型的target，表示真实结果；real类型的lr，表示学习率。
grad_.zero()对grad_清零。
对于每个正确样本和negative样本调用binaryLogistic函数更新grad_和wo_，最后由logloss公式得出loss。

hierarchicalSoftmax()函数

参数为int类型的target，表示真实结果；real类型的lr，表示学习率。
grad_.zero()对grad_清零。
对于每个huffman路径上经过的节点调用binaryLogistic函数更新grad_和wo_，最后由logloss公式得出loss。

real Model::binaryLogistic(int32_t target, bool label, real lr) {
  // 将 hidden_和参数矩阵的第target行做内积，并计算sigmoid
  real score = utils::sigmoid(wo_->dotRow(hidden_, target));
  // 计算梯度时的中间变量
  real alpha = lr * (real(label) - score);
  // Loss对于hidden_的梯度累加到grad_上。更新e值。
  grad_.addRow(*wo_, target, alpha);
  // Loss对于LR参数的梯度累加到wo_的对应行上。更新参数。
  wo_->addRow(hidden_, target, alpha);
  // LR的Loss
  if (label) {
    return -utils::log(score);
  } else {
    return -utils::log(1.0 - score);
  }
}

softmax()函数

参数为int类型的target，表示真实结果；real类型的lr，表示学习率。
grad_.zero()对grad_清零。
计算出output_的值，并且计算出它们的softmax。
根据softmax后的output_的值，更新grad_和wo_。
由logloss公式得出loss。

setTargetCounts()函数

counts为单词出现的次数组成的数组。索引为label或者word在dict_中的位置。
如果是分类模型，counts为label构成的数组；否则，counts为word构成的数组。
如果损失函数是负采样，调用initTableNegatives(counts)；如果损失函数是层次softmax，调用buildTree(counts)。

initTableNegatives()函数

如果为initTableNegatives，根据每个单词出现的次数构造negatives_，单词出现次数越高，则negatives_里面该单词越多，但每个单词至少都出现一次，表示单词都有概率取到。

buildTree()函数

算法首先对输入的叶子节点进行一次排序(O(nlogn))，然后确定两个下标leaf和node，leaf总是指向当前最小的叶子节点，node总是指向当前最小的非叶子节点，所以，最小的两个节点可以从leaf,leaf-1, node,node+1四个位置中取得，时间复杂度 O(1)，每个非叶子节点都进行一次，所以总复杂度为O(n)，算法整体复杂度为O(nlogn)。
counts 数组保存每个叶子节点的词频，降序排列。
构造tree的大小为2*osz_-1，分配所有节点的空间。
第一个for循环，初始化节点的属性。
第二个for循环，将叶子节点的count属性设置为所对应的单词出现次数。为下一步生成Huffman树做准备。
leaf指向当前未处理的叶子节点的最后一个，也就是权值最小的叶子节点。node指向当前未处理的非叶子节点的第一个，也是权值最小的非叶子节点。
第三个for循环中，逐个构造所有非叶子节点(i>=osz_,i<2*osz_ 1)，并更新非叶子节点的属性left、right、count以及子节点的属性parent、binary，注意只有右节点binary才更新为true。
第四个for循环中，对于所有的叶子节点构造path和code(i>0,i< osz_)，存入paths和codes中。

predict()函数

predict函数可以用于给输入数据打上1～K个类标签，并输出各个类标签对应的概率值，对于层次 softmax，我们需要遍历霍夫曼树，找到top－K的结果，对于普通softmax(包括负采样和softmax的输出)，我们需要遍历结果数组，找到top－K。
如果是层次softmax，使用dfs函数遍历霍夫曼树的所有叶子节点，找到top－k的概率。
如果是普通softmax(包括负采样和softmax的输出)，在结果数组里找到top-k。

dictionary模块

数据结构

std::vector<int32_t> word2int_; 
word转化为int，首先将word hash为数字h，然后设置word2int_[h]的值
std::vector<entry> words_; 根据int读取entry结构

std::vector<real> pdiscard_; 每个词的丢弃概率值
int32_t size_; 单词的个数，去重 size_ = nwords_ + nlabels_
int32_t nwords_; 纯词个数，去重
int32_t nlabels_; 标签词的个数，去重
int64_t ntokens_; 处理过的词的个数

enum class entry_type : int8_t {word=0, label=1};
struct entry {
  std::string word;
  int64_t count;
  entry_type type;
  std::vector<int32_t> subwords;
};

对外接口

外界使用Dictionary，一是通过readFromFile函数，生成词典；二是getLine，获取句的词。

readFromFile()函数：

生成词典，词典中包括纯词和标签词
按照词出现的频率进行排序并且过滤小于指定阈值的词；纯词和标签词可以有不同的阈值。
初始化initTableDiscard表。对每个词根据词的频率获取相应的丢弃概率值，若是给定的阈值小于这个表的值那么就丢弃该词，这里是因为对于频率过高的词可能就是无用词，所以丢弃。比如”的”，”是”等。
初始化ngram表。每个词都对应一个ngram的表的id列表。比如词”我想你”，通过computeNgrams函数可以计算出相应ngram的词索引，假设ngram的词最短为2，最长为3，则就是”<我”，”我想”，”想你”，”你>”，<我想”，”我想你”，”想你>”的子词组成，这里有”<>”因为这里会自动添加词的开始和结束位。这里注意代码实现中的”(word[j] & 0xC0) == 0x80)”这里是考虑utf-8的汉字情况，来使得能够取出完整的一个汉字作为一个”字”。

getLine()函数

参数std::istream& in(读取的文件), std::vector< int32_t>& words(将一行句子转化为int串的表示), std::vector< int32_t>& labels(将label转化为int串的表示)；返回句子长度ntokens。
在函数中会改变参数的值。

一些疑问

model模块中的dfs函数，score < heap.front().first感觉应该是大于，因为是最小堆，score代表损失值，我们应该想要损失值越小越好吧。

model模块中的update函数，反向传播理解有问题。结合参考《word2vec中的数学原理详解》中的公式推导来理解。

fastText使用

fastText功能介绍

fastText主要有两个功能，一个是训练词向量，另一个是文本分类。

词向量的训练，相对于word2vec来说，增加了subwords特性。subwords其实就是一个词的character-level的n-gram。比如单词”hello”，长度至少为3的char-level的ngram有”hel”,”ell”,”llo”,”hell”,”ello”以及本身”hello”。
对于文本分类来说，模型很简单，就是一层word embedding的隐层+输出层。

为了加快训练过程，fastText同样也采用了和word2vec类似的方法。

一种方法是使用hierarchical softmax，当类别数为K，word embedding大小为d时，计算复杂度可以从O(Kd)降到O(dlog(K))。利用了类别不均衡信息。
另一种方法是采用negative sampling，即每次从除当前label外的其他label中选择几个作为负样本，作为出现负样本的概率加到损失函数中。

fastText的一些Tricks:

增加了subwords特性。即一个词的character-level的n-gram，将其用embedding向量来表示，在计算隐层时，把N-gram的embedding向量也加进去求和取平均。这样对于未登录词也可以通过切出来的ngram词向量合并为一个词。由于中文的词大多比较短，这对英文语料的用处会比中文语料更大。
增加了N-gram的特征。具体做法是把N-gram当成一个词，用embedding向量来表示，在计算隐层时，把N-gram的embedding向量也加进去求和取平均。
对于上述提到的两种n-gram，由于n-gram的量远比word大的多，完全存下所有的n-gram也不现实。Fasttext采用了Hash桶的方式，把所有的n-gram都哈希到buckets个桶中，哈希到同一个桶的所有n-gram共享一个embedding vector。不过这种方法潜在的问题是存在哈希冲突，不同的n-gram可能会共享同一个embedding。如果桶大小取的足够大，这种影响会很小。
对计算复杂度比较高的运算，Fasttext都采用了预计算的方法，先计算好值，使用的时候再查表，这是典型的空间或时间的优化思路。
在Negative Sampling中，Fasttext也采用了和word2vec类似的方法，即按照每个词的词频进行随机负采样，词频越大的词，被采样的概率越大。每个词被采样的概率并不是简单的按照词频在总量的占比，而是对词频先取根号，再算占比。这里取根号的目的是降低高频词的采用概率，同事增加低频词的采样概率。
fastText相比deep learning模型的优点是训练速度极快。

训练模型

如果要训练模型，我们选择supervised选项，执行./fasttext supervised。

训练模式下涉及到的主要参数有学习率(-lr)，隐层的维数(-dim)，最小词频（-minCount），负采样个数（-neg）和n-grams的长度(-wordNgrams)等。

参数选择

loss function选用hs(hierarchical softmax)要比ns(negative sampling)训练速度要快很多倍，并且准确率也更高。
wordNgrams默认为1，设置为2以上可以明显提高准确率。
如果词数不是很多，可以把bucket设置的小一点，否则预留会预留太多bucket使模型太大。