🈺 👩🏽‍🤝‍👨🏼 👕 FastText: receta de código 👳 🔌 🖖🏻

¡Buen dia amigos! Le presento una traducción amateur del artículo original: FastText: paso a paso por el código de Maria Mestre.

Una pequeña advertencia: parte de la información proporcionada puede no ser completamente cierta debido al paso del tiempo y los errores aleatorios del autor. En cualquier caso, cualquier comentario será deseable.

Es posible que haya encontrado una herramienta como FastText para vectorizar sus cuerpos de texto, pero ¿sabía que FastText también puede clasificarlos? O tal vez lo sabían, pero ¿sabía él cómo lo hace? Miremos desde adentro ... quiero decir, a través de la pantalla.

La biblioteca FastText fue desarrollada principalmente por el equipo de Facebook para clasificar textos, pero también se puede usar para entrenar incrustaciones de palabras. Desde el momento en que FastText se convirtió en un producto accesible para todos (2016), se ha utilizado ampliamente debido a su buena velocidad de entrenamiento y excelente rendimiento.

Al leer la documentación oficial (muy escasa de explicación), me di cuenta de que contiene una gran parte de los algoritmos que pueden no ser completamente transparentes, por lo que se decidió averiguar de forma independiente cómo funciona todo y con qué se come. Comencé leyendo el artículo principal de los creadores y un vistazo rápido al curso de aprendizaje profundo de Stanford en PNL. En el proceso de todo este placer, solo aumenté las preguntas. Por ejemplo: que en el curso de las conferencias de Stanford y en una parte del artículo hablan sobre el uso de N-gramos, pero no dicen ninguna característica en su aplicación. Además, los parámetros prescritos en la línea de comando incluyen un determinado depósito cuyos únicos comentarios suenan como "el número de contenedores (depósitos)". ¿Cómo se calculan estos N-gramos? ¿Cubeta? No está claro ... Queda una opción, ver el código enGitHub .

Después de ver todo lo bueno, se descubrió lo siguiente

FastText utiliza con confianza N-gramos de caracteres con el mismo éxito que N-gramos de palabras.
FastText admite la clasificación multiclase, que puede no ser tan obvia la primera vez.
El número de parámetros del modelo.

Introducción al modelo

Según un artículo escrito por desarrolladores, el modelo es una red neuronal simple con una capa oculta. El texto representado por la bolsa de palabras (BOW) se pasa a través de la primera capa en la que se transforma en incrustaciones de palabras. Posteriormente, las incrustaciones resultantes se promedian en todo el texto y se reducen a la única que es aplicable en todo el texto. En la capa oculta, trabajamos con n_words * dim según el número de parámetros, donde dim es el tamaño de incrustación y n_words es el tamaño del diccionario utilizado para el texto. Después del promedio, obtenemos un único vector que pasa a través de un clasificador bastante popular: se utiliza la función softmaxpara mapeo lineal (conversión) de los datos de entrada de la primera capa a la última. Una matriz de dimensión dim * n_output actúa como una transformación lineal , donde n_output es nuestro número de clases reales. En el artículo original, la probabilidad final se considera como probabilidad de registro :

imagen

donde:

x_n es la representación de una palabra en n-gramo.
Y esta es una matriz de búsqueda que extrae la incrustación de una palabra.
Esta es una transformación lineal de la salida.
f directamente la función softmax en sí.

Todo en general no es tan malo, pero echemos un vistazo al código:

Código como traducción de una idea

El archivo con los datos de origen que podemos aplicar para nuestro clasificador debe seguir una forma específica: __label__0 (texto).

Como ejemplos:
__label__cat Este texto trata sobre gatos.
__label__dog Este texto trata sobre perros.

El archivo fuente se usa como argumento para la función de tren . La función de tren comienza con la inicialización y el posterior llenado de la variable 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_ es una instancia de la clase Diccionario.


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

Después de leer y analizar las oraciones del archivo fuente, llenamos dos vectores:

palabras_ que contienen palabras únicas extraídas del texto
word2int_ contiene hashes para cada palabra según su posición en el vector words_int . Esto es realmente muy importante, ya que determina cuál se usará para buscar incrustaciones de la matriz A

El vector de palabras contiene instancias de entrada. Cada uno de los cuales puede ser un tipo de palabra para etiqueta y tener un contador de llamadas. También hay un campo de subpalabras , pero lo veremos un poco más.

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

Al agregar palabras o etiquetas a la variable word2int_ , las colisiones se resuelven necesariamente de tal manera que nunca nos referimos a dos palabras diferentes que tengan el mismo índice. Simplemente no habrá ninguno.

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 vectores se filtran para garantizar que se incluyan las palabras y etiquetas que se mencionan al menos una vez. Después de pasar a la parte en que se utiliza el ReadFromFile función donde initNgrams se llama . Casi llegamos a la mística de usar N-gramos.


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

La función initNgrams define todas las combinaciones de caracteres de N-gram y los agrega al vector ngram . Al final, todos los valores hash para N-gramos se calculan y se suman en el vector ngram , formando el tamaño del cubo . En otras palabras, se agregan hashes de caracteres de N-gram después de agregar hashes de palabras de N-gram. Como resultado, sus índices no se superponen con los índices de las palabras, pero pueden superponerse entre sí.

En general, para cada palabra en el texto, puede proporcionar subpalabras ... N-gramos de caracteres.
La matriz de incrustación A muestra lo siguiente:

Las nwords_ líneas iniciales que contienen incrustaciones para cada palabra del diccionario disponible para el texto.
Siga el grupo de líneas que contienen incrustaciones para cada N-gramo 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);
}

Entonces adivinamos los místicos personajes de N-gram. Ahora tratemos con N-gramos de palabras.

Volviendo a la función de tren , se ejecutan las siguientes instrucciones:

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

Aquí es donde se inicializa la matriz de incrustación A. Debe señalarse que si los vectores pretrained funcionan con esta función, entonces esta variable se considera completa. Si esto no sucede, la matriz se inicializa con números aleatorios -1 / dim y 1 / dim , donde dim es el tamaño de nuestra incrustación. Dimensión de la matriz A ( n_words_ + bucket ; dim ), es decir vamos a configurar todas estas incrustaciones para cada palabra. La salida también se inicializa en este paso.

Como resultado, obtenemos la parte donde comenzamos a entrenar nuestro 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();
}

Hay dos puntos principales en esta parte del código. Primero, la función getLine llama a la variable dict_ . En segundo lugar, se llama a la función supervisada .

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

En la función anterior, leemos los textos de la entrada, determinamos los índices para cada palabra uno tras otro usando word2int_ . Agregamos los N-gramos que componen estas palabras a la variable de palabras , como se indica en el código. Y al final, agregamos etiquetas directamente al vector de etiquetas .

Después de leer completamente y agregar texto (oraciones del corpus) directamente a los vectores creados para ellos, obtenemos una parte del código que procesa N-gramos. Esta es la función 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);
    }
  }
}

Nosotros miramos más allá. La variable hashes es un conjunto de hashes para cada palabra en el texto, donde la línea contiene el número de palabras en la oración y el número de N-gramos utilizados. El parámetro n es el parámetro wordNgrams e indica la longitud máxima de los N-gramos de palabras. Cada N-gramo de palabras obtiene su propio hash calculado mediante una fórmula recursiva

h = h * 116049371 + h a s h e s [j]

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

. Esta fórmula es un algoritmo de hash FNV aplicado a una cadena: toma el hash de cada palabra en el N-gramo de palabras y las agrega. Por lo tanto, se obtiene un conjunto de hashes únicos. Como resultado, este valor (puede llegar a ser bastante grande) se transmite en módulo.

Por lo tanto, los N-gramos de palabras se calculan aproximadamente de la misma manera que los N-gramos de caracteres, pero con una ligera diferencia: no seleccionamos una palabra específica. Increíble movimiento.

Después de leer la oración, se llama a la función supervisada . Si la oferta tiene varias etiquetas, seleccionamos al azar una de ellas.


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

Y finalmente, la función de actualización del 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);
  }
}

Las variables de entrada que pasan por la función supervisada tienen una lista de índices de todos sus componentes (palabras, N-gramos de palabras y símbolos) de la oración. El objetivo es definir una clase en la salida. La función computeHidden determina todas las incorporaciones para cada componente de la entrada buscándolas en la matriz wi_ y promediando ( addRow se suma y divide por su tamaño). Después de modificar el vector hidden_, envíelos para su activación a través de softmax y defina una etiqueta.

Esta sección de código muestra el uso de la función de activación softmax . La pérdida de registro también se calcula .

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

Con este método, no obtendremos un aumento en el tamaño de N-gramos de palabras y caracteres. El crecimiento está limitado por el número de cubos ya disponibles .

Por defecto, FastText no usa N-gramos, pero recomendamos las siguientes opciones:

Bucker = 2,000,000; wordNgrams> 1 o maxn> 0
dim = 100
n_output = 2
n_words = 500000

En total, obtenemos una cantidad bastante grande de parámetros para el entrenamiento

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

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

Demasiado, ¿no es así?) Como podemos ver incluso a través de un enfoque tan simple, tenemos una cantidad bastante grande de parámetros, lo cual es muy típico de los métodos de aprendizaje profundo. Se usa una estimación muy aproximada, por ejemplo, el número de N-gramos tomados para 2_000_000, para mostrar el orden. En general, la complejidad del modelo puede reducirse ajustando algunos hiperparámetros, como un depósito o el umbral de muestreo.

Algunos enlaces pueden ser útiles:
research.fb.com/fasttext
arxiv.org/pdf/1607.01759.pdf y arxiv.org/pdf/1607.04606v1.pdf
www.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJzQtileLTqGL_XtG (de 47:39)

FastText: receta de código

Después de ver todo lo bueno, se descubrió lo siguiente

Introducción al modelo

Código como traducción de una idea

More articles: