FastText：代码配方

朋友们，美好的一天！我向您介绍了原始文章的业余翻译：FastText：逐步阅读 Maria Mestre 的代码。

一个小警告：由于时间的流逝和作者的随机错误，所提供的某些信息可能并不完全正确。无论如何，任何反馈都是可取的！

您可能遇到过FastText之类的工具来对文本进行矢量化处理，但是您知道FastText也可以处理其分类吗？也许他们知道，但是他知道他是怎么做的吗？让我们从内部看……我是说，通过屏幕。

FastText库最初是由Facebook团队开发的，用于对文本进行分类，但也可以用于训练单词嵌入。自从FastText成为所有人都可以使用的产品（2016年）以来，由于其良好的培训速度和出色的性能，它已被广泛使用。

阅读官方文档（非常少解释），我意识到它包含了很大一部分算法，这些算法可能不是完全透明的，因此决定独立地弄清所有算法的工作原理以及所用的食物。我首先阅读了创作者的主要文章，并快速浏览了NLP的斯坦福深度学习课程。在所有这些愉悦的过程中，我只增加了疑问。例如：在斯坦福大学的演讲过程中和文章的一部分中，他们谈论了N-gram的使用，但他们并未说明其应用程序中的任何功能。同样，在命令行中指定的参数包括某个存储桶，其上唯一的注释听起来像是“容器数（存储桶）”。这些N语法如何计算？桶？尚不清楚...一种选择仍然存在，请观看代码github。

看完所有的好东西后，发现以下内容

• FastText自信地使用N-gram字符与N-grams单词取得了相同的成功。
• FastText支持多类分类，这在初次使用时可能不太明显。
• 型号参数数

型号介绍

根据开发人员写的一篇文章，该模型是具有一个隐藏层的简单神经网络。单词袋（BOW）表示的文本通过第一层，在该第一层中它被转换为单词嵌入。随后，将生成的嵌入内容在整个文本中平均，然后减少到整个文本中唯一适用的嵌入。在隐藏层中，我们使用n_words * dim的参数数量，其中dim是嵌入的大小，n_words是用于文本的字典的大小。平均后，我们得到一个向量，该向量经过一个相当流行的分类器：使用softmax函数用于第一层的输入数据到最后一层的线性映射（转换）。尺寸为dim * n_output的矩阵充当线性变换，其中n_output是我们的实数类。在原来的文章，最后的概率被认为是对数的情形产生：



其中：

• x_n是n-gram中单词的表示形式。
• 这是一个look_up矩阵，用于提取单词的嵌入。
• 这是输出的线性变换。
• f直接使用softmax函数本身。

总的来说，一切还不错，但是让我们看一下代码：

将代码作为想法翻译

可以用于分类器的包含源数据的文件必须遵循特定的格式：__label__0（文本）。

例如：
__label__cat该主题与猫有关。
__label__dog这段文字是关于狗的。

源文件用作train函数的参数。训练函数从初始化并随后填充dict_变量开始。

void FastText::train(const Args args) {
  args_ = std::make_shared<Args>(args);
  dict_ = std::make_shared<Dictionary>(args_);
  if (args_->input == "-") {
    // manage expectations
    throw std::invalid_argument("Cannot use stdin for training!");
  }
  std::ifstream ifs(args_->input);
  if (!ifs.is_open()) {
    throw std::invalid_argument(
        args_->input + " cannot be opened for training!");
  }
  dict_->readFromFile(ifs);

dict_是Dictionary类的实例。

Dictionary::Dictionary(std::shared_ptr<Args> args) : args_(args),
  word2int_(MAX_VOCAB_SIZE, -1), size_(0), nwords_(0), nlabels_(0),
  ntokens_(0), pruneidx_size_(-1) {}

阅读并解析源文件的句子之后，我们填充两个向量：

• words_包含从文本中提取的唯一单词
• word2int_根据每个单词在words_vector中的位置包含散列。这实际上非常重要，因为它确定将使用哪个搜索矩阵A的嵌入

words_ vector 包含入口实例。每个标签都可以是单词的单词类型，并具有调用它们的计数器。还有一个subwords字段，但我们将进一步研究它。

struct entry {
  std::string word;
  int64_t count;
  entry_type type;
  std::vector<int32_t> subwords;
};

通过将单词或标记添加到word2int_变量中，必须以某种方式解决冲突，即我们永远不会引用具有相同索引的两个不同单词。根本不会有任何东西。

int32_t Dictionary::find(const std::string& w, uint32_t h) const {
  int32_t word2intsize = word2int_.size();
  int32_t id = h % word2intsize;
  while (word2int_[id] != -1 && words_[word2int_[id]].word != w) {
    id = (id + 1) % word2intsize;
  }
  return id;
}

int32_t Dictionary::find(const std::string& w) const {
  return find(w, hash(w));
}

void Dictionary::add(const std::string& w) {
  int32_t h = find(w);
  ntokens_++;
  if (word2int_[h] == -1) {
    entry e;
    e.word = w;
    e.count = 1;
    e.type = getType(w);
    words_.push_back(e);
    word2int_[h] = size_++;
  } else {
    words_[word2int_[h]].count++;
  }
}

对两个向量都进行过滤，以确保包括至少被提及一次的单词和标记。之后我们进入到我们使用的部分readFromFile功能，其中initNgrams被称为。我们几乎到了使用N-gram的神秘面纱。

void Dictionary::readFromFile(std::istream& in) {
  std::string word;
  int64_t minThreshold = 1;
  while (readWord(in, word)) {
    add(word);
    if (ntokens_ % 1000000 == 0 && args_->verbose > 1) {
      std::cerr << "\rRead " << ntokens_  / 1000000 << "M words" << std::flush;
    }
    if (size_ > 0.75 * MAX_VOCAB_SIZE) {
      minThreshold++;
      threshold(minThreshold, minThreshold);
    }
  }
  threshold(args_->minCount, args_->minCountLabel);
  initTableDiscard();
  initNgrams();

initNgrams 函数定义N-gram字符的所有组合，并将它们添加到ngram vector中。最后，将计算所有N-gram的哈希并将其加到ngram向量中，从而形成存储桶的大小。换句话说，在添加N-gram单词的哈希之后，添加N-gram字符的哈希。结果，它们的索引不与单词的索引重叠，但是可以彼此重叠。

通常，对于文本中的每个单词，您都可以提供子单词 ... N个字符的字符。
嵌入矩阵A显示以下内容：

• 最初的nwords_行包含可用于文本的字典中每个单词的嵌入。
• 跟随每行N个gram包含嵌入的行

void Dictionary::initNgrams() {
  for (size_t i = 0; i < size_; i++) {
    std::string word = BOW + words_[i].word + EOW;
    words_[i].subwords.clear();
    words_[i].subwords.push_back(i);
    if (words_[i].word != EOS) {
      computeSubwords(word, words_[i].subwords);
    }
  }
}

void Dictionary::computeSubwords(const std::string& word,
                               std::vector<int32_t>& ngrams) 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++]);
      while (j < word.size() && (word[j] & 0xC0) == 0x80) {
        ngram.push_back(word[j++]);
      }
      if (n >= args_->minn && !(n == 1 && (i == 0 || j == word.size()))) {
        int32_t h = hash(ngram) % args_->bucket;
        pushHash(ngrams, h);
      }
    }
  }
}

void Dictionary::pushHash(std::vector<int32_t>& hashes, int32_t id) const {
  if (pruneidx_size_ == 0 || id < 0) return;
  if (pruneidx_size_ > 0) {
    if (pruneidx_.count(id)) {
      id = pruneidx_.at(id);
    } else {
      return;
    }
  }
  hashes.push_back(nwords_ + id);
}

因此我们猜到了神秘的N-gram字符。现在让我们处理N字词。

返回火车功能，执行以下指令：

  if (args_->pretrainedVectors.size() != 0) {
    loadVectors(args_->pretrainedVectors);
  } else {
    input_ = std::make_shared<Matrix>(dict_->nwords()+args_->bucket, args_->dim);
    input_->uniform(1.0 / args_->dim);
  }

  if (args_->model == model_name::sup) {
    output_ = std::make_shared<Matrix>(dict_->nlabels(), args_->dim);
  } else {
    output_ = std::make_shared<Matrix>(dict_->nwords(), args_->dim);
  }
  output_->zero();
  startThreads();

这是初始化嵌入矩阵A的地方，必须指出，如果pretrainedVectors使用此函数，则该变量被视为已满。如果这没有发生，则使用随机数-1 / dim和1 / dim初始化矩阵，其中dim是我们嵌入的大小。矩阵A的维数（n_words_ + bucket ; dim），即我们将为每个单词设置所有这些嵌入。在此步骤中也将初始化输出。

结果，我们得到了开始训练模型的部分。

void FastText::trainThread(int32_t threadId) {
  std::ifstream ifs(args_->input);
  utils::seek(ifs, threadId * utils::size(ifs) / args_->thread);

  Model model(input_, output_, args_, threadId);
  if (args_->model == model_name::sup) {
    model.setTargetCounts(dict_->getCounts(entry_type::label));
  } else {
    model.setTargetCounts(dict_->getCounts(entry_type::word));
  }

  const int64_t ntokens = dict_->ntokens();
  int64_t localTokenCount = 0;
  std::vector<int32_t> line, labels;
  while (tokenCount_ < args_->epoch * ntokens) {
    real progress = real(tokenCount_) / (args_->epoch * ntokens);
    real lr = args_->lr * (1.0 - progress);
    if (args_->model == model_name::sup) {
      localTokenCount += dict_->getLine(ifs, line, labels);
      supervised(model, lr, line, labels);
    } else if (args_->model == model_name::cbow) {
      localTokenCount += dict_->getLine(ifs, line, model.rng);
      cbow(model, lr, line);
    } else if (args_->model == model_name::sg) {
      localTokenCount += dict_->getLine(ifs, line, model.rng);
      skipgram(model, lr, line);
    }
    if (localTokenCount > args_->lrUpdateRate) {
      tokenCount_ += localTokenCount;
      localTokenCount = 0;
      if (threadId == 0 && args_->verbose > 1)
        loss_ = model.getLoss();
    }
  }
  if (threadId == 0)
    loss_ = model.getLoss();
  ifs.close();
}

代码的这一部分有两个要点。首先，getLine函数调用dict_变量。其次，受监管的函数称为。

int32_t Dictionary::getLine(std::istream& in,
                            std::vector<int32_t>& words,
                            std::vector<int32_t>& labels) const {
  std::vector<int32_t> word_hashes;
  std::string token;
  int32_t ntokens = 0;

  reset(in);
  words.clear();
  labels.clear();
  while (readWord(in, token)) {
    uint32_t h = hash(token);
    int32_t wid = getId(token, h);
    entry_type type = wid < 0 ? getType(token) : getType(wid);

    ntokens++;
    if (type == entry_type::word) {
      addSubwords(words, token, wid);
      word_hashes.push_back(h);
    } else if (type == entry_type::label && wid >= 0) {
      labels.push_back(wid - nwords_);
    }<source lang="cpp">
    if (token == EOS) break;
  }
  addWordNgrams(words, word_hashes, args_->wordNgrams);
  return ntokens;
}

在上面的函数中，我们从输入数据中读取文本，并使用word2int_依次确定每个单词的索引。如代码所示，我们将构成这些单词的N元语法添加到单词 variable 中。最后，我们将标签直接添加到标签 vector 。

在完全阅读并将文本（来自语料库的句子）直接添加到为其创建的向量后，我们获得了处理N-gram的代码的一部分。这是addWordNgrams函数。

void Dictionary::addWordNgrams(std::vector<int32_t>& line,
                               const std::vector<int32_t>& hashes,
                               int32_t n) const {
  for (int32_t i = 0; i < hashes.size(); i++) {
    uint64_t h = hashes[i];
    for (int32_t j = i + 1; j < hashes.size() && j < i + n; j++) {
      h = h * 116049371 + hashes[j];
      pushHash(line, h % args_->bucket);
    }
  }
}

我们进一步看。hashes变量是文本中每个单词的一组哈希值，其中line包含句子中单词的数量和使用的N-gram的数量。参数n是参数wordNgrams，表示单词N-gram的最大长度。每个N-gram单词都有自己的哈希，该哈希由递归公式计算

$$

$$h = h*116049371+hashes[j]$$

。此公式是应用于字符串的FNV哈希算法：它将N-gram单词中每个单词的哈希值加起来。因此，获得了一组唯一的哈希。结果，该值（可能会很大）以模数形式传输。

因此，单词N-gram的计算方法与字符N-gram的计算方法大致相同，只是略有不同-我们不对特定单词进行哈希处理。惊人的举动。

阅读完句子后，将调用受监管的函数。如果要约有多个标签，我们将随机选择其中之一。

void FastText::supervised(
    Model& model,
    real lr,
    const std::vector<int32_t>& line,
    const std::vector<int32_t>& labels) {
  if (labels.size() == 0 || line.size() == 0) return;
  std::uniform_int_distribution<> uniform(0, labels.size() - 1);
  int32_t i = uniform(model.rng);
  model.update(line, labels[i], lr);
}

最后是模型更新功能。

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_) {
      hidden.addRow(*qwi_, *it);
    } else {
      hidden.addRow(*wi_, *it);
    }
  }
  hidden.mul(1.0 / input.size());
}

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);
  }
}

通过监督函数的输入变量具有其句子的所有组成部分（单词，单词和符号的N-grams）的索引列表。目的是在输出上定义一个类。该computeHidden功能通过在搜索他们确定针对输入的各组件的所有的嵌入wi_矩阵和平均（addRow被相加，并通过它们的大小划分）。修改hidden_向量后，通过softmax发送它们以进行激活并定义标签。

本节代码说明softmax激活功能的使用。还计算对数损失。

void Model::computeOutputSoftmax(Vector& hidden, Vector& output) const {
  if (quant_ && args_->qout) {
    output.mul(*qwo_, hidden);
  } else {
    output.mul(*wo_, hidden);
  }
  real max = output[0], z = 0.0;
  for (int32_t i = 0; i < osz_; i++) {
    max = std::max(output[i], max);
  }
  for (int32_t i = 0; i < osz_; i++) {
    output[i] = exp(output[i] - max);
    z += output[i];
  }
  for (int32_t i = 0; i < osz_; i++) {
    output[i] /= z;
  }
}

void Model::computeOutputSoftmax() {
  computeOutputSoftmax(hidden_, output_);
}

real Model::softmax(int32_t target, real lr) {
  grad_.zero();
  computeOutputSoftmax();
  for (int32_t i = 0; i < osz_; i++) {
    real label = (i == target) ? 1.0 : 0.0;
    real alpha = lr * (label - output_[i]);
    grad_.addRow(*wo_, i, alpha);
    wo_->addRow(hidden_, i, alpha);
  }
  return -log(output_[target]);
}

使用这种方法，我们不会增加N-gram单词和字符的大小。增长受到已经可用的存储桶数量的限制。

默认情况下，FastText不使用N-gram，但是我们建议使用以下选项：

• 巴克= 2,000,000; wordNgrams> 1或maxn> 0
• 昏暗= 100
• n_output = 2
• n_words = 500000

总体而言，我们获得了大量用于训练的参数

$$

$$(5000000+2000000)*100+(2*100) = 250,000,000$$

太多了，不是吗？）即使通过这种简单的方法我们也可以看到，我们有相当数量的参数，这是深度学习方法中非常典型的。为了显示顺序，使用了非常粗略的估计，例如，对2_000_000采取的N-gram数。通常，可以通过调整一些超参数（例如存储桶或采样阈值）来降低模型的复杂性。

某些链接可能会有用：
research.fb.com/fasttext
arxiv.org/pdf/1607.01759.pdf和arxiv.org/pdf/1607.04606v1.pdf
www.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJzQtileLTqGL_XtG（来自47:39）