FastText: resep kode

Selamat siang teman! Saya sajikan kepada Anda terjemahan amatir dari artikel asli: FastText: melangkah melalui kode oleh Maria Mestre.

Peringatan kecil: beberapa informasi yang diberikan mungkin tidak sepenuhnya benar karena berlalunya waktu dan kesalahan acak penulis. Bagaimanapun, umpan balik akan diinginkan!

Anda mungkin menemukan alat seperti FastText untuk membuat vektor badan teks Anda menjadi vektor, tetapi apakah Anda tahu bahwa FastText juga dapat mengklasifikasikannya? Atau mungkin mereka tahu, tetapi apakah dia tahu bagaimana dia melakukannya? Mari kita melihatnya dari dalam ... Maksud saya, melalui layar.

Perpustakaan FastText terutama dikembangkan oleh tim Facebook untuk mengklasifikasikan teks, tetapi juga dapat digunakan untuk melatih embeddings kata. Sejak saat FastText menjadi produk yang dapat diakses oleh semua orang (2016), telah banyak digunakan karena kecepatan pelatihan yang baik dan kinerja yang sangat baik.

Membaca dokumentasi resmi (sangat langka untuk penjelasan), saya menyadari bahwa itu berisi bagian yang cukup besar dari algoritma yang mungkin tidak sepenuhnya transparan, jadi diputuskan untuk secara mandiri mencari tahu bagaimana semuanya bekerja dan apa yang dimakannya. Saya mulai dengan membaca artikel utama dari pencipta dan melihat sekilas kursus pembelajaran mendalam Stanford di NLP. Dalam proses semua kesenangan ini, saya hanya menambah pertanyaan. Sebagai contoh: bahwa dalam perkuliahan Stanford dan di satu bagian artikel mereka berbicara tentang penggunaan N-gram, tetapi mereka tidak mengatakan fitur apa pun dalam aplikasi mereka. Jadi, parameter yang ditentukan dalam baris perintah termasuk satu ember tertentu, satu-satunya komentar yang terdengar seperti "jumlah kontainer (ember)". Bagaimana N-gram ini dihitung? Ember? Tidak jelas ... Satu pilihan tetap, perhatikan kode aktifgithub .

Setelah menonton semua yang baik, berikut ini diketahui

• FastText dengan percaya diri menggunakan N-gram karakter dengan kesuksesan yang sama dengan N-gram kata.
• FastText mendukung klasifikasi multi-kelas, yang mungkin tidak begitu jelas saat pertama kali.
• Jumlah parameter model

Pengantar Model

Menurut sebuah artikel yang ditulis oleh pengembang, model ini adalah jaringan saraf sederhana dengan satu lapisan tersembunyi. Teks yang diwakili oleh kata bag (BOW) dilewatkan melalui lapisan pertama di mana ia diubah menjadi embed kata. Selanjutnya, embeddings yang dihasilkan rata-rata di seluruh teks dan dikurangi menjadi satu-satunya yang berlaku di seluruh teks. Di lapisan tersembunyi, kami bekerja dengan n_words * redup oleh jumlah parameter, di mana redup adalah ukuran embedding, dan n_words adalah ukuran kamus yang digunakan untuk teks. Setelah rata-rata, kita mendapatkan satu vektor tunggal yang melewati classifier yang agak populer: fungsi softmax digunakanuntuk pemetaan linear (konversi) dari data input dari lapisan pertama ke yang terakhir. Matriks dimensi dim * n_output bertindak sebagai transformasi linear , di mana n_output adalah jumlah kelas nyata kita. Dalam artikel asli, probabilitas akhir dianggap sebagai kemungkinan log : di



mana:

• x_n adalah representasi kata dalam n-gram.
• Dan ini adalah matriks look_up yang mengekstrak embedding kata.
• Ini adalah transformasi linear dari output.
• f secara langsung fungsi softmax itu sendiri.

Semuanya secara umum tidak terlalu buruk, tapi mari kita lihat kode:

Kode sebagai terjemahan ide

File dengan sumber data yang dapat kita terapkan untuk classifier kita harus mengikuti formulir tertentu: __label__0 (teks).

Sebagai contoh:
__label__cat Thext ini berisi tentang kucing.
__label__dog Teks ini tentang anjing.

File sumber digunakan sebagai argumen untuk fungsi kereta . Fungsi kereta dimulai dengan inisialisasi dan selanjutnya mengisi variabel 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_ adalah turunan dari kelas Kamus.

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

Setelah membaca dan menguraikan kalimat dari file sumber, kami mengisi dua vektor:

• words_ mengandung kata-kata unik yang diekstrak dari teks
• word2int_ berisi hash untuk setiap kata sesuai dengan posisinya dalam vektor words_ . Ini sebenarnya sangat penting, karena menentukan yang akan digunakan untuk mencari embeddings dari matriks A

Vektor words_ berisi instance entri. Masing-masing dapat berupa jenis kata untuk label dan memiliki counter panggilan kepada mereka. Ada juga bidang subwords , tetapi kita akan melihatnya sedikit lebih jauh.

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

Dengan menambahkan kata atau tag ke variabel word2int_ , tabrakan harus diselesaikan sedemikian rupa sehingga kita tidak pernah merujuk pada dua kata berbeda yang memiliki indeks yang sama. Tidak akan ada.

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

Kedua vektor disaring untuk memastikan bahwa kata dan tag yang disebutkan setidaknya satu kali disertakan. Setelah kita beralih ke bagian di mana kita menggunakan fungsi readFromFile di mana initNgram dipanggil . Kami hampir sampai pada mistik menggunakan 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();

Fungsi initNgrams mendefinisikan semua kombinasi karakter N-gram dan menambahkannya ke vektor ngram . Pada akhirnya, semua hash untuk N-gram dihitung dan ditambahkan dalam vektor ngram , membentuk ukuran ember . Dengan kata lain, hash karakter N-gram ditambahkan setelah menambahkan hash kata N-gram. Akibatnya, indeks mereka tidak tumpang tindih dengan indeks kata-kata, tetapi bisa tumpang tindih satu sama lain.

Secara umum, untuk setiap kata dalam teks, Anda dapat memberikan subwords ... N-gram karakter.
Matriks penyematan A menampilkan berikut ini:

• Baris nwords_ awal berisi embeddings untuk setiap kata dari kamus yang tersedia untuk teks.
• Ikuti seember baris yang berisi hiasan untuk setiap N-gram karakter

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

Jadi kami menebak karakter mistis N-gram. Sekarang mari kita berurusan dengan N-gram kata.

Kembali ke fungsi kereta , instruksi berikut dijalankan:

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

Di sinilah embedding matriks A diinisialisasi. Harus ditunjukkan bahwa jika vektor prerained bekerja dengan fungsi ini, maka variabel ini dianggap penuh. Jika ini tidak terjadi, maka matriks diinisialisasi dengan angka acak -1 / redup dan 1 / redup , di mana redup adalah ukuran embedding kami. Dimensi matriks A ( n_words_ + ember ; redup ), mis. kita akan mengatur semua hiasan ini untuk setiap kata. Output juga diinisialisasi pada langkah ini.

Sebagai hasilnya, kita mendapatkan bagian di mana kita mulai melatih model kita.

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

Ada dua poin utama dalam bagian kode ini. Pertama, fungsi getLine memanggil variabel dict_ . Kedua, fungsi yang diawasi disebut .

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

Dalam fungsi di atas, kita membaca teks dari data input, menentukan indeks untuk setiap kata satu demi satu dengan menggunakan word2int_ . Kami menambahkan N-gram yang membentuk kata-kata ini ke variabel kata , seperti yang ditunjukkan dalam kode. Dan pada akhirnya, kami menambahkan label langsung ke vektor label .

Setelah sepenuhnya membaca dan menambahkan teks (kalimat dari corpus) langsung ke vektor yang dibuat untuk mereka, kami mendapatkan bagian dari kode yang memproses N-gram. Ini adalah fungsi 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);
    }
  }
}

Kami melihat lebih jauh. Variabel hash adalah satu set hash untuk setiap kata dalam teks, di mana baris berisi jumlah kata dalam kalimat dan jumlah N-gram yang digunakan. Parameter n adalah parameter wordNgrams dan menunjukkan panjang maksimum N-gram kata. Setiap N-gram kata memiliki hash sendiri yang dihitung dengan rumus rekursif

$$

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

. Rumus ini adalah algoritma hash FNV yang diterapkan pada string: ia mengambil hash dari setiap kata dalam N-gram kata dan menambahkannya. Dengan demikian, satu set hash unik diperoleh. Akibatnya, nilai ini (bisa menjadi cukup besar) ditransmisikan modulo.

Jadi, N-gram kata-kata dihitung kira-kira dengan cara yang sama seperti N-gram karakter, tetapi dengan sedikit perbedaan - kita tidak memiliki kata tertentu. Langkah luar biasa.

Setelah membaca kalimat, fungsi yang diawasi dipanggil . Jika tawaran memiliki beberapa tag, kami secara acak memilih salah satunya.

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

Dan akhirnya, fungsi pembaruan model.

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

Variabel input yang melewati fungsi yang diawasi memiliki daftar indeks semua komponennya (kata, N-gram kata dan simbol) dari kalimat. Tujuannya adalah untuk menentukan kelas pada output. Fungsi computeHidden menentukan semua embeddings untuk setiap komponen input dengan mencari mereka dalam matriks wi_ dan rata-rata ( addRow dijumlahkan dan dibagi dengan ukurannya). Setelah memodifikasi vektor hidden_, kirim mereka untuk aktivasi melalui softmax dan tentukan label.

Bagian kode ini menunjukkan penggunaan fungsi aktivasi softmax . Kehilangan log juga dihitung .

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

Dengan menggunakan metode ini, kita tidak akan mendapatkan peningkatan dalam ukuran N-gram kata dan karakter. Pertumbuhan dibatasi oleh jumlah ember yang tersedia .

Secara default, FastText tidak menggunakan N-gram, tetapi kami merekomendasikan opsi berikut:

• bucker = 2.000.000; wordNgrams> 1 atau maks.> 0
• redup = 100
• n_output = 2
• n_words = 500000

Secara total, kami mendapatkan sejumlah besar parameter untuk pelatihan

$$

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

Terlalu banyak, bukan?) Seperti yang dapat kita lihat melalui pendekatan sederhana ini, kita memiliki sejumlah besar parameter, yang sangat khas dari metode pembelajaran yang mendalam. Perkiraan yang sangat kasar digunakan, misalnya, jumlah N-gram yang diambil untuk 2_000_000, untuk menunjukkan pesanan. Secara umum, kompleksitas model dapat dikurangi dengan menyetel beberapa hiperparameter, seperti ember atau ambang batas pengambilan sampel.

Beberapa tautan mungkin bermanfaat:
research.fb.com/fasttext
arxiv.org/pdf/1607.01759.pdf dan arxiv.org/pdf/1607.04606v1.pdf
www.youtube.com/watch?v=isPiE-DBagM&index=5&list=PLU40WL8Ol94IJzQtileLTqGL (mulai 47:39)