FastText: Code-Rezept

Guten Tag, Freunde! Ich präsentiere Ihnen eine Amateurübersetzung des Originalartikels: FastText: Schritt durch den Code von Maria Mestre.

Eine kleine Warnung: Einige der bereitgestellten Informationen sind aufgrund des Zeitablaufs und zufälliger Fehler des Autors möglicherweise nicht vollständig wahr. In jedem Fall ist jedes Feedback wünschenswert!

Möglicherweise sind Sie auf ein Tool wie FastText gestoßen, mit dem Sie Ihren Textkörper vektorisieren können. Wussten Sie jedoch, dass FastText auch mit deren Klassifizierung umgehen kann? Oder vielleicht wussten sie es, aber wusste er, wie er es macht? Schauen wir es uns von innen an ... ich meine, durch den Bildschirm.

Die FastText-Bibliothek wurde hauptsächlich vom Facebook-Team zur Klassifizierung von Texten entwickelt, kann aber auch zum Trainieren von Worteinbettungen verwendet werden. Seit FastText ein Produkt ist, das für jedermann zugänglich ist (2016), ist es aufgrund seiner guten Trainingsgeschwindigkeit und hervorragenden Leistung weit verbreitet.

Als ich die offizielle Dokumentation las (sehr wenig zu erklären), stellte ich fest, dass sie einen ziemlich großen Teil der Algorithmen enthält, die möglicherweise nicht vollständig transparent sind. Daher wurde beschlossen, unabhängig herauszufinden, wie alles funktioniert und womit es isst. Ich begann mit dem Lesen des Hauptartikels der Autoren und einem kurzen Blick auf den Stanford Deep Learning-Kurs in NLP. Während all dieser Freude habe ich nur die Fragen erhöht. Zum Beispiel: dass sie im Verlauf von Stanfords Vorlesungen und in einem Teil des Artikels über die Verwendung von N-Gramm sprechen, aber keine Merkmale in ihrer Anwendung angeben. Zu den in der Befehlszeile angegebenen Parametern gehört auch ein bestimmter Bucket, dessen einzige Kommentare wie "die Anzahl der Container (Buckets)" klingen. Wie werden diese N-Gramm berechnet? Eimer? Es ist nicht klar ... Eine Option bleibt, sehen Sie sich den Code anGithub .

Nachdem ich all das Gute gesehen hatte, wurde Folgendes herausgefunden

• FastText verwendet sicher N-Gramm Zeichen mit dem gleichen Erfolg wie N-Gramm Wörter.
• FastText unterstützt die Klassifizierung mehrerer Klassen, was beim ersten Mal möglicherweise nicht so offensichtlich ist.
• Die Anzahl der Modellparameter

Modell Einführung

Laut einem Artikel von Entwicklern ist das Modell ein einfaches neuronales Netzwerk mit einer verborgenen Schicht. Der durch die Worttasche (BOW) dargestellte Text wird durch die erste Ebene geleitet, in der er in Worteinbettungen umgewandelt wird. Anschließend werden die resultierenden Einbettungen über den gesamten Text gemittelt und auf die einzige reduziert, die im gesamten Text anwendbar ist. In der verborgenen Ebene arbeiten wir mit n_words * dim anhand der Anzahl der Parameter, wobei dim die Größe der Einbettung und n_words die Größe des für Text verwendeten Wörterbuchs ist. Nach der Mittelwertbildung erhalten wir einen einzelnen Vektor, der einen recht beliebten Klassifikator durchläuft: Die Softmax- Funktion wird verwendetzur linearen Abbildung (Konvertierung) der Eingabedaten der ersten bis zur letzten Schicht. Eine Matrix der Dimension dim * n_output fungiert als lineare Transformation , wobei n_output unsere Anzahl realer Klassen ist. Im Originalartikel wird die endgültige Wahrscheinlichkeit als logarithmische Wahrscheinlichkeit betrachtet :



wobei:

• x_n ist die Darstellung eines Wortes in n-Gramm.
• Und dies ist eine Look_up-Matrix, die die Einbettung eines Wortes extrahiert.
• Dies ist eine lineare Transformation der Ausgabe.
• f direkt die Softmax-Funktion selbst.

Alles im Allgemeinen ist nicht so schlecht, aber schauen wir uns trotzdem den Code an:

Code als Ideenübersetzung

Die Datei mit den Quelldaten, die wir für unseren Klassifikator anwenden können, muss eine bestimmte Form haben: __label__0 (Text).

Als Beispiele:
__label__cat In diesem Text geht es um Katzen.
__label__dog In diesem Text geht es um Hunde.

Die Quelldatei wird als Argument für die Zugfunktion verwendet . Die Zug - Funktion beginnt mit der Initialisierung und anschließenden Füllen der dict_ variable .

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_ ist eine Instanz der Dictionary-Klasse.

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

Nachdem wir die Sätze der Quelldatei gelesen und analysiert haben, füllen wir zwei Vektoren:

• words_ enthält eindeutige Wörter, die aus Text extrahiert wurden
• word2int_ enthält Hashes für jedes Wort entsprechend seiner Position im Wortvektor . Dies ist tatsächlich sehr wichtig, da es bestimmt, welche zur Suche nach Einbettungen der Matrix A verwendet werden

Der Wortvektor enthält Eintrittsinstanzen. Jedes davon kann ein Worttyp für Label sein und einen Zähler für Anrufe haben. Es gibt auch ein Unterwortfeld , aber wir werden es uns etwas genauer ansehen.

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

Durch Hinzufügen von Wörtern oder Tags zur Variablen word2int_ werden Kollisionen notwendigerweise so aufgelöst, dass wir niemals auf zwei verschiedene Wörter mit demselben Index verweisen. Es wird einfach keine geben.

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

Beide Vektoren werden gefiltert, um sicherzustellen, dass Wörter und Tags, die mindestens einmal erwähnt werden, enthalten sind. Nachdem wir zu dem Teil übergegangen sind, in dem wir die Funktion readFromFile verwenden, in der initNgrams aufgerufen wird . Wir sind fast zum Mystiker gekommen, N-Gramm zu verwenden.

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

Die Funktion initNgrams definiert alle Kombinationen von N-Gramm-Zeichen und fügt sie dem ngram- Vektor hinzu . Am Ende werden alle Hashes für N-Gramm berechnet und im n-Gramm-Vektor addiert , wodurch die Größe des Eimers gebildet wird . Mit anderen Worten, Hashes von N-Gramm-Zeichen werden hinzugefügt, nachdem Hashes von N-Gramm-Wörtern hinzugefügt wurden. Infolgedessen überlappen sich ihre Indizes nicht mit den Indizes von Wörtern, sondern können sich überlappen.

Im Allgemeinen können Sie für jedes Wort im Text Unterwörter angeben ... N-Gramm Zeichen.
Das Einbetten der Matrix A zeigt Folgendes an:

• Die anfänglichen nwords_-Zeilen enthalten Einbettungen für jedes Wort aus dem Wörterbuch, das für den Text verfügbar ist.
• Folgen Sie dem Zeilenumfang mit Einbettungen für jedes N-Gramm Zeichen

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

Also haben wir die mystischen N-Gramm-Zeichen erraten. Lassen Sie uns nun mit N-Gramm Wörtern umgehen.

Zurück zur Zugfunktion werden folgende Anweisungen ausgeführt:

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

Hier wird die Einbettungsmatrix A initialisiert. Es muss darauf hingewiesen werden, dass diese Variable als voll betrachtet wird, wenn pretrainedVectors mit dieser Funktion arbeiten. Geschieht dies nicht, wird die Matrix mit den Zufallszahlen -1 / dim und 1 / dim initialisiert , wobei dim die Größe unserer Einbettung ist. Dimension der Matrix A ( n_words_ + Bucket ; dim ), d.h. Wir werden alle diese Einbettungen für jedes Wort einrichten. In diesem Schritt wird auch die Ausgabe initialisiert.

Als Ergebnis erhalten wir den Teil, in dem wir mit dem Training unseres Modells beginnen.

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

In diesem Teil des Codes gibt es zwei Hauptpunkte. Zunächst wird die getLine Funktion ruft die dict_ Variable . Zweitens wird die überwachte Funktion aufgerufen .

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

In der obigen Funktion lesen wir die Texte aus den Eingabedaten und bestimmen die Indizes für jedes Wort nacheinander mit word2int_ . Wir fügen Sie das N-Gramm , die diese Worte zu dem bilden Worten Variable , wie in dem Code angegeben. Und am Ende fügen wir Beschriftungen direkt zum Beschriftungsvektor hinzu .

Nachdem wir den Text (Sätze aus dem Korpus) vollständig gelesen und direkt zu den für sie erstellten Vektoren hinzugefügt haben, erhalten wir einen Teil des Codes, der N-Gramm verarbeitet. Dies ist die Funktion 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);
    }
  }
}

Wir schauen weiter. Die Hashes- Variable ist eine Reihe von Hashes für jedes Wort im Text, wobei die Zeile die Anzahl der Wörter im Satz und die Anzahl der verwendeten N-Gramm enthält. Der Parameter n ist der Parameter wordNgrams und gibt die maximale Länge der N-Gramm von Wörtern an. Jedes N-Gramm Wörter erhält einen eigenen Hash, der durch eine rekursive Formel berechnet wird

$$

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

. Diese Formel ist ein FNV- Hash- Algorithmus , der auf eine Zeichenfolge angewendet wird: Er nimmt den Hash jedes Wortes im N-Gramm der Wörter und fügt sie hinzu. Auf diese Weise wird ein Satz eindeutiger Hashes erhalten. Infolgedessen wird dieser Wert (der sich als ziemlich groß herausstellen kann) modulo übertragen.

Daher werden N-Gramm Wörter ungefähr auf die gleiche Weise berechnet wie N-Gramm Zeichen, jedoch mit einem geringfügigen Unterschied - wir haben kein bestimmtes Wort. Erstaunlicher Zug.

Nach dem Lesen des Satzes wird die überwachte Funktion aufgerufen . Wenn das Angebot mehrere Tags enthält, wählen wir zufällig eines davon aus.

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

Und schließlich die Modellaktualisierungsfunktion.

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

Eingangsvariablen, die die überwachte Funktion durchlaufen , enthalten eine Liste von Indizes aller ihrer Komponenten (Wörter, N-Gramm Wörter und Symbole) des Satzes. Ziel ist es, eine Klasse für die Ausgabe zu definieren. Die Funktion computeHidden ermittelt alle Einbettungen für jede Komponente der Eingabe, indem sie in der wi_- Matrix nach ihnen sucht und gemittelt wird ( addRow wird summiert und durch ihre Größe geteilt). Nachdem Sie den Vektor hidden_ ​​geändert haben, senden Sie ihn zur Aktivierung über softmax und definieren Sie eine Bezeichnung.

Dieser Codeabschnitt zeigt die Verwendung der Softmax- Aktivierungsfunktion . Der Protokollverlust wird ebenfalls berechnet .

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

Mit dieser Methode wird die Größe von N-Gramm Wörtern und Zeichen nicht erhöht. Das Wachstum wird durch die Anzahl der bereits verfügbaren Eimer begrenzt .

Standardmäßig verwendet FastText keine N-Gramm, wir empfehlen jedoch die folgenden Optionen:

• Bucker = 2.000.000; wordNgrams> 1 oder maxn> 0
• dim = 100
• n_output = 2
• n_words = 500000

Insgesamt erhalten wir eine ziemlich große Anzahl von Parametern für das Training

$$

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

Zu viel, nicht wahr?) Wie wir selbst durch einen so einfachen Ansatz sehen können, haben wir eine ziemlich große Anzahl von Parametern, was sehr typisch für Deep-Learning-Methoden ist. Eine sehr grobe Schätzung wird verwendet, zum Beispiel die Anzahl der N-Gramm, die für 2_000_000 genommen wurden, um die Reihenfolge anzuzeigen. Im Allgemeinen kann die Komplexität des Modells durch Einstellen einiger Hyperparameter wie eines Buckets oder der Abtastschwelle verringert werden .

Einige Links können nützlich sein:
research.fb.com/fasttext
arxiv.org/pdf/1607.01759.pdf und arxiv.org/pdf/1607.04606v1.pdf
www.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJt (ab 47:39)