Bonjour mes amis! Je vous présente une traduction amateur de l'article original: FastText: en parcourant le code de Maria Mestre.
Un petit avertissement: certaines des informations fournies peuvent ne pas être complètement vraies en raison du passage du temps et des erreurs aléatoires de l'auteur. Dans tous les cas, tout retour sera souhaitable!
Vous avez peut-être rencontré un outil tel que FastText pour vectoriser votre corps de textes, mais saviez-vous que FastText peut également gérer leur classification? Ou peut-être qu'ils le savaient, mais savait-il comment il le faisait? Regardons cela de l'intérieur ... Je veux dire, à travers l'écran.
La bibliothèque FastText a été principalement développée par l'équipe Facebook pour classer les textes, mais elle peut également être utilisée pour former des incorporations de mots. Depuis le moment où FastText est devenu un produit accessible à tous (2016), il a été largement utilisé en raison de sa bonne vitesse d'entraînement et de ses excellentes performances.En lisant la documentation officielle (très rare pour l'explication), je me suis rendu compte qu'elle contient une assez grande partie des algorithmes qui peuvent ne pas être complètement transparents, il a donc été décidé de déterminer indépendamment comment tout cela fonctionne et avec quoi il mange. J'ai commencé par lire l'article principal des créateurs et un bref aperçu du cours d'apprentissage approfondi de Stanford en PNL. Au cours de tout ce plaisir, je n'ai fait qu'accroître les questions. Par exemple: qu'au cours des conférences de Stanford et dans une partie de l'article, ils parlent de l'utilisation des N-grammes, mais ils ne disent aucune fonctionnalité dans leur application. Ainsi, les paramètres prescrits dans la ligne de commande incluent un certain compartiment dont les seuls commentaires sonnent comme "le nombre de conteneurs (compartiments)". Comment ces N-grammes sont-ils calculés? Seau? Ce n'est pas clair ... Une option reste, regardez le code surgithub .Après avoir regardé tout le bien, ce qui suit a été découvert
- FastText utilise en toute confiance N-grammes de caractères avec le même succès que N-grammes de mots.
- FastText prend en charge la classification multiclasse, ce qui n'est peut-être pas si évident la première fois.
- Le nombre de paramètres du modèle
Introduction au modèle
Selon un article écrit par des développeurs, le modèle est un simple réseau neuronal avec une couche cachée. Le texte représenté par le sac de mots (BOW) passe à travers la première couche dans laquelle il est transformé en encastrements de mots. Par la suite, les incorporations résultantes sont moyennées sur l'ensemble du texte et réduites à la seule applicable à l'ensemble du texte. Dans la couche cachée, nous travaillons avec n_words * dim par le nombre de paramètres, où dim est la taille de l'incorporation et n_words est la taille du dictionnaire utilisé pour le texte. Après la moyenne, nous obtenons un seul vecteur qui passe par un classificateur plutôt populaire: la fonction softmax est utiliséepour la cartographie linéaire (conversion) des données d'entrée de la première couche à la dernière. Une matrice de dimension dim * n_output agit comme une transformation linéaire , où n_output est notre nombre de classes réelles. Dans l'article d'origine, la probabilité finale est considérée comme une probabilité logarithmique :
où:- x_n est la représentation d'un mot en n-gramme.
- Et ceci est une matrice de recherche qui extrait l'incorporation d'un mot.
- Il s'agit d'une transformation linéaire de la sortie.
- f directement la fonction softmax elle-même.
Tout n'est pas si mal en général, mais regardons quand même le code:Traduction de code comme idée
Le fichier avec les données source que nous pouvons appliquer pour notre classificateur doit suivre une forme spécifique: __label__0 (texte).A titre d'exemples:__label__cat Ce thext concerne les chats.__label__dog Ce texte concerne les chiens.Le fichier source est utilisé comme argument de la fonction train . La fonction train commence par l'initialisation et le remplissage ultérieur 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 == "-") {
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_ est une instance de la 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) {}
Après avoir lu et analysé les phrases du fichier source, nous remplissons deux vecteurs:- mots_ contenant des mots uniques extraits du texte
- word2int_ contenant des hachages pour chaque mot selon sa position dans le vecteur words_ . Ceci est en fait très important, car il détermine qui sera utilisé pour rechercher les plongements de la matrice A
Le vecteur words_ contient des instances d'entrée. Chacun d'eux peut être un type de mot pour label et avoir un compteur d'appels. Il y a aussi un champ de sous- mots , mais nous allons l'examiner un peu plus loin.struct entry {
std::string word;
int64_t count;
entry_type type;
std::vector<int32_t> subwords;
};
En ajoutant des mots ou des balises à la variable word2int_ , les collisions sont nécessairement résolues de telle manière que nous ne faisons jamais référence à deux mots différents ayant le même index. Il n'y en aura tout simplement pas.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++;
}
}
Les deux vecteurs sont filtrés pour garantir que les mots et les balises mentionnés au moins une fois sont inclus. Après nous passons à la partie où nous utilisons la ReadFromFile fonction où initNgrams est appelée . Nous sommes presque arrivés au mystique de l'utilisation de N-grammes.
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 fonction initNgrams définit toutes les combinaisons de caractères N-gramme et les ajoute au vecteur ngram . Au final, tous les hachages de N-grammes sont calculés et additionnés dans le vecteur ngram , formant la taille du seau . En d'autres termes, des hachages de caractères N-gramme sont ajoutés après l'ajout de hachages de mots N-gramme. En conséquence, leurs indices ne se chevauchent pas avec les indices des mots, mais peuvent se chevaucher.En général, pour chaque mot du texte, vous pouvez fournir des sous- mots ... N-grammes de caractères.L'incorporation de la matrice A affiche les éléments suivants:- Les lignes nwords_ initiales contenant les plongements pour chaque mot du dictionnaire disponible pour le texte.
- Suivez le seau de lignes contenant des plongements pour chaque N-gramme de caractères
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);
}
Nous avons donc deviné les caractères mystiques N-gramme. Voyons maintenant les N-grammes de mots.De retour à la fonction train , les instructions suivantes sont exécutées: 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();
C'est là que la matrice d'intégration A est initialisée. Il faut noter que si des vecteurs pré - formés fonctionnent avec cette fonction, alors cette variable est considérée comme pleine. Si cela ne se produit pas, la matrice est initialisée avec des nombres aléatoires -1 / dim et 1 / dim , où dim est la taille de notre intégration. Dimension de la matrice A ( n_words_ + bucket ; dim ), c'est-à-dire nous allons configurer toutes ces intégrations pour chaque mot. La sortie est également initialisée à cette étape.En conséquence, nous obtenons la partie où nous commençons à former notre modèle.
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();
}
Il y a deux points principaux dans cette partie du code. Tout d'abord, la fonction getLine appelle la variable dict_ . Deuxièmement, la fonction supervisée est appelée .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;
}
Dans la fonction ci-dessus, nous lisons les textes des données d'entrée, déterminons les indices pour chaque mot l'un après l'autre en utilisant word2int_ . Nous ajoutons les N-grammes qui composent ces mots à la variable des mots , comme indiqué dans le code. Et à la fin, nous ajoutons des étiquettes directement au vecteur d' étiquettes .Après avoir entièrement lu et ajouté du texte (phrases du corpus) directement aux vecteurs créés pour eux, nous obtenons une partie du code qui traite les N-grammes. Il s'agit de la fonction 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);
}
}
}
Nous regardons plus loin. La variable de hachage est un ensemble de hachages pour chaque mot du texte, où la ligne contient le nombre de mots dans la phrase et le nombre de N-grammes utilisés. Le paramètre n est le paramètre wordNgrams et indique la longueur maximale des N-grammes de mots. Chaque N-gramme de mots obtient son propre hachage calculé par une formule récursive
. Cette formule est un algorithme de hachage FNV appliqué à une chaîne: il prend le hachage de chaque mot dans le N-gramme de mots et les ajoute. Ainsi, un ensemble de hachages uniques est obtenu. En conséquence, cette valeur (qui peut s'avérer assez grande) est transmise modulo.Ainsi, les N-grammes de mots sont calculés approximativement de la même manière que les N-grammes de caractères, mais avec une légère différence - nous ne hachons pas un mot spécifique. Mouvement incroyable.Après avoir lu la phrase, la fonction supervisée est appelée . Si l'offre comporte plusieurs balises, nous en sélectionnons une au hasard.
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);
}
Et enfin, la fonction de mise à jour du modèle.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);
}
}
Les variables d'entrée passant par la fonction supervisée ont une liste d'indices de toutes leurs composantes (mots, N-grammes de mots et symboles) de la phrase. Le but est de définir une classe sur la sortie. La fonction computeHidden détermine tous les plongements pour chaque composant de l'entrée en les recherchant dans la matrice wi_ et en faisant la moyenne ( addRow est additionné et divisé par leur taille). Après avoir modifié le vecteur hidden_, envoyez-les pour activation via softmax et définissez une étiquette.Cette section de code montre l'utilisation de la fonction d' activation softmax . La perte de journal est également calculée .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]);
}
En utilisant cette méthode, nous n'obtiendrons pas une augmentation de la taille des N-grammes de mots et de caractères. La croissance est limitée par le nombre de seaux déjà disponibles .Par défaut, FastText n'utilise pas de N-grammes, mais nous recommandons les options suivantes:- bucker = 2 000 000; wordNgrams> 1 ou maxn> 0
- dim = 100
- n_output = 2
- n_words = 500000
Au total, nous obtenons un nombre assez important de paramètres pour la formation
Trop, n'est-ce pas?) Comme nous pouvons le voir, même avec une approche aussi simple, nous avons un assez grand nombre de paramètres, ce qui est très typique des méthodes d'apprentissage en profondeur. Une estimation très grossière est utilisée, par exemple, le nombre de N-grammes pris pour 2_000_000, afin de montrer l'ordre. En général, la complexité du modèle peut être réduite en réglant certains hyperparamètres, comme un seau ou le seuil d'échantillonnage.Certains liens peuvent être utiles:research.fb.com/fasttextarxiv.org/pdf/1607.01759.pdf et arxiv.org/pdf/1607.04606v1.pdfwww.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJzQtileLTqGL_Xt (à partir de 47:39)