FastText: receita de código

Bom dia amigos Apresento a você uma tradução amadora do artigo original: FastText: percorrendo o código de Maria Mestre.

Um pequeno aviso: algumas das informações fornecidas podem não ser completamente verdadeiras devido à passagem do tempo e a erros aleatórios do autor. De qualquer forma, qualquer feedback será desejável!

Você pode ter encontrado uma ferramenta como o FastText para vetorizar seus corpos de texto, mas sabia que o FastText também pode classificá-los? Ou talvez eles soubessem, mas ele sabia como faz isso? Vamos olhar de dentro para fora ... quero dizer, através da tela.

A biblioteca FastText foi desenvolvida principalmente pela equipe do Facebook para classificar os textos, mas também pode ser usada para treinar a incorporação de palavras. Desde o momento em que o FastText se tornou um produto acessível a todos (2016), ele tem sido amplamente utilizado devido à sua boa velocidade de treinamento e excelente desempenho.

Lendo a documentação oficial (muito escassa para explicação), percebi que ela contém uma parte bastante grande dos algoritmos que podem não ser completamente transparentes, por isso foi decidido descobrir independentemente como tudo funciona e com o que se come. Comecei lendo o artigo principal dos criadores e uma rápida olhada no curso de aprendizado profundo de Stanford na PNL. No processo de todo esse prazer, apenas ampliei as perguntas. Por exemplo: no curso das palestras de Stanford e em uma parte do artigo eles falam sobre o uso de N-gramas, mas não dizem nenhum recurso em sua aplicação. Portanto, os parâmetros prescritos na linha de comando incluem um determinado bucket, os únicos comentários que soam como "o número de containers (buckets)". Como esses N-gramas são calculados? Balde? Não está claro ... Uma opção permanece, observe o código emgithub .

Depois de assistir tudo de bom, foi descoberto o seguinte

• O FastText usa N gramas de caracteres com o mesmo sucesso que N gramas de palavras.
• O FastText suporta classificação multiclasse, o que pode não ser tão óbvio na primeira vez.
• O número de parâmetros do modelo

Introdução do modelo

Segundo um artigo escrito pelos desenvolvedores, o modelo é uma rede neural simples com uma camada oculta. O texto representado pela palavra bolsa (BOW) é passado pela primeira camada na qual é transformado em incorporação de palavras. Posteriormente, a incorporação resultante é calculada sobre o texto inteiro e reduzida para o único aplicável ao longo do texto. Na camada oculta, trabalhamos com n_words * dim pelo número de parâmetros, em que dim é o tamanho da incorporação e n_words é o tamanho do dicionário usado para o texto. Após a média, obtemos um único vetor que passa por um classificador bastante popular: a função softmax é usadapara mapeamento linear (conversão) dos dados de entrada da primeira camada para a última. A matriz da dimensão dim * n_output atua como uma transformação linear , onde n_output é o número de classes reais. No artigo original, a probabilidade final é considerada probabilidade de log : em



que:

• x_n é a representação de uma palavra em n-grama.
• E essa é uma matriz de pesquisa que extrai a incorporação de uma palavra.
• Esta é uma transformação linear da saída.
• f diretamente a própria função softmax.

Tudo em geral não é tão ruim, mas ainda vamos dar uma olhada no código:

Código como uma tradução da ideia

O arquivo com os dados de origem que podemos aplicar ao nosso classificador deve seguir um formulário específico: __label__0 (texto).

Como exemplos:
__label__cat Esse texto é sobre gatos.
__label__dog Este texto é sobre cães.

O arquivo de origem é usado como argumento para a função train . A função train começa com a inicialização e o subsequente preenchimento da variável 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_ é uma instância da classe 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) {}

Após ler e analisar as frases do arquivo de origem, preenchemos dois vetores:

• words_ contendo palavras únicas extraídas do texto
• word2int_ contendo hashes para cada palavra de acordo com sua posição no vetor words_ . Isso é realmente muito importante, pois determina qual será usado para procurar por incorporamentos da matriz A

O vetor words_ contém instâncias de entrada. Cada um deles pode ser um tipo de palavra para etiqueta e ter um contador de chamadas para elas. Há também um campo de subpalavras , mas vamos analisá- lo um pouco mais.

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

Ao adicionar palavras ou tags à variável word2int_ , as colisões são necessariamente resolvidas de tal maneira que nunca nos referimos a duas palavras diferentes com o mesmo índice. Simplesmente não haverá.

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

Ambos os vetores são filtrados para garantir que as palavras e tags mencionadas pelo menos uma vez sejam incluídas. Depois passamos para a parte onde nós usamos o ReadFromFile função onde initNgrams é chamado . Quase chegamos ao místico de usar N-gramas.

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

A função initNgrams define todas as combinações de caracteres N-gram e as adiciona ao vetor ngram . No final, todos os hashes para N-gramas são calculados e somados no vetor ngram , formando o tamanho do balde . Em outras palavras, os hashes de caracteres N-gram são adicionados após a adição de hashes de palavras N-gram. Como resultado, seus índices não se sobrepõem aos índices de palavras, mas podem se sobrepor.

Em geral, para cada palavra do texto, você pode fornecer subpalavras ... N-gramas de caracteres.
A matriz de incorporação A exibe o seguinte:

• As linhas iniciais nwords_ contendo incorporação para cada palavra do dicionário disponível para o texto.
• Siga o intervalo de linhas que contém incorporações para cada N-grama de caracteres

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

Então, adivinhamos os caracteres místicos do N-grama. Agora vamos lidar com N gramas de palavras.

Voltando à função de trem , as seguintes instruções são executadas:

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

É aqui que a matriz de incorporação A. é inicializada. Deve-se ressaltar que se os Vectores pré-treinados trabalharem com essa função, essa variável será considerada completa. Se isso não acontecer, a matriz será inicializada com números aleatórios -1 / dim e 1 / dim , onde dim é o tamanho da nossa incorporação. Dimensão da matriz A ( n_words_ + bucket ; dim ), ou seja, nós vamos montar todos esses casamentos para cada palavra. A saída também é inicializada nesta etapa.

Como resultado, obtemos a parte em que começamos a treinar nosso modelo.

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

Existem dois pontos principais nesta parte do código. Primeiro, o getLine função chama o dict_ variável . Segundo, a função supervisionada é chamada .

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

Na função acima, lemos os textos da entrada, determinamos os índices de cada palavra, um após o outro, usando word2int_ . Nós adicionamos os N-gramas que compõem essas palavras à variável words , conforme indicado no código. E, no final, adicionamos rótulos diretamente ao vetor de rótulos .

Depois de ler e adicionar completamente o texto (frases do corpus) diretamente aos vetores criados para eles, obtemos uma parte do código que processa N-gramas. Esta é a função 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);
    }
  }
}

Nós olhamos mais longe. A variável hashes é um conjunto de hashes para cada palavra no texto, em que a linha contém o número de palavras na frase e o número de N gramas usados. O parâmetro n é o parâmetro wordNgrams e indica o comprimento máximo dos N-gramas de palavras. Cada grama N de palavras obtém seu próprio hash calculado por uma fórmula recursiva

$$

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

. Essa fórmula é um algoritmo de hash FNV aplicado a uma string: pega o hash de cada palavra no N-grama de palavras e as adiciona. Assim, é obtido um conjunto de hashes exclusivos. Como resultado, esse valor (pode ser bastante grande) é transmitido para o módulo.

Assim, N-gramas de palavras são calculados aproximadamente da mesma maneira que N-gramas de caracteres, mas com uma pequena diferença - não usamos uma palavra específica. Movimento incrível.

Depois de ler a frase, a função supervisionada é chamada . Se a oferta tiver várias tags, selecionamos aleatoriamente uma delas.

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

E, finalmente, a função de atualização do modelo.

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

As variáveis ​​de entrada que passam pela função supervisionada têm uma lista de índices de todos os seus componentes (palavras, N gramas de palavras e símbolos) da sentença. O objetivo é definir uma classe na saída. A função computeHidden determina todas as incorporações para cada componente da entrada pesquisando-as na matriz wi_ e na média ( addRow é somado e dividido por seu tamanho). Após modificar o vetor hidden_, envie-os para ativação via softmax e defina um rótulo.

Esta seção do código mostra o uso da função de ativação do softmax . A perda de log também é calculada .

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

Usando esse método, não obteremos um aumento no tamanho de N gramas de palavras e caracteres. O crescimento é limitado pelo número de baldes já disponíveis .

Por padrão, o FastText não usa N-gramas, mas recomendamos as seguintes opções:

• bucker = 2.000.000; wordNgrams> 1 ou maxn> 0
• dim = 100
• n_output = 2
• n_words = 500000

No total, obtemos um número bastante grande de parâmetros para treinamento

$$

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

Demais, não é?) Como podemos ver, mesmo através de uma abordagem tão simples, temos um número bastante grande de parâmetros, o que é típico dos métodos de aprendizado profundo. Uma estimativa aproximada é usada, por exemplo, o número de N-gramas retirados para 2_000_000, para mostrar a ordem. Em geral, a complexidade do modelo pode ser reduzida ajustando alguns hiperparâmetros, como um balde ou o limite de amostragem.

Alguns links podem ser úteis:
research.fb.com/fasttext
arxiv.org/pdf/1607.01759.pdf e arxiv.org/pdf/1607.04606v1.pdf
www.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJzQtileLTqGL_XtG (a partir de 47:39)