3
$\begingroup$

In the original Skipgram/CBOW both context word and target word are represented as one-hot encoding.

Does fasttext also use one-hot encoding for each subword when training the skip-gram/CBOW model (so the length of the one-hot encoding vector is |Vocab| + |all subwords|)? If they use it, do they use it in both context and target words?

$\endgroup$
  • 1
    $\begingroup$ Have you looked at this document : towardsdatascience.com/fasttext-under-the-hood-11efc57b2b3 ? $\endgroup$ – Nischal Hp Feb 14 at 10:39
  • 1
    $\begingroup$ I have read it, but I'm not quite sure with my understanding . The article mentions that the input vector size is MAX_VOCAB + Bucket Size, is it the on-hot encoding vector? $\endgroup$ – malioboro Feb 14 at 14:19
  • $\begingroup$ The embedding part is implemented in Cpp. fasttext.cc and Vector.cc in github.com/facebookresearch/fastText/blob/master/src . Tried to trace back. but no luck. $\endgroup$ – Vivek Ananthan Feb 28 at 10:19
  • $\begingroup$ getTargetCounts() from the source code could hint, that it is counts and not binary one hot encoding. No mentioning of "context" in the source code. $\endgroup$ – keiv.fly Feb 28 at 23:33
3
+50
$\begingroup$

A quick answer would be No.

Let's walk through how FastText works internally:

For representation purposes, FastText internally initializes a dictionary. Dictionary contains all the collection of words. Besides words, it also maintains the count of all the words in the dictionary (and other information). Every time a new word is added to the dictionary its size is increased and word2int_ is updated to size_(which is increased after assignment).

The code below adds a word into the dictionary.

// adding of new word
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_++; //  word2int_[h] is assigned a uniuqe value 
  } else {
    words_[word2int_[h]].count++; // word's count is being updated here
  }
}

// funciton used to access word ID (which is the representation used)
int32_t Dictionary::getId(const std::string& w) const {
  int32_t h = find(w);
  return word2int_[h];
}

As mentioned in this medium article, word2int_ is indexed on the hash of the word string, and stores a sequential int index to the words_ array. The maximum size of word2int_ vector can be 30000000.

For embeddings matrix of M x N is created where M = MAX_VOCAB_SIZE + bucket_size. Where, M is total vocabulary size including bucket_size corresponds to the total size of array allocated for all the n-gram tokens and N is the dimension of the embedding vector, which means the representation for one word requires the size of 1.

The code below shows how to compute the hash and calculates the ID of the subword. A similar logic is used to access the subword vector. Note here h is an integer value which is calculated using dict_->hash(). This function returns the same h value which is used when adding a word in the dictionary. This makes the process of accessing word IDs only dependent on the value of h.


int32_t FastText::getSubwordId(const std::string& subword) const {
  int32_t h = dict_->hash(subword) % args_->bucket;
  return dict_->nwords() + h;
}

void FastText::getSubwordVector(Vector& vec, const std::string& subword) const {
  vec.zero();
  int32_t h = dict_->hash(subword) % args_->bucket;
  h = h + dict_->nwords();
  addInputVector(vec, h);
}

Long story short, FastText makes use of integer IDs assigned at the beginning and use those IDs to access the embeddings.

I hope this helps. All the code samples are taken from FastText repo. Feel free to dive in to understand more.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is really cool, thank you for this @vikas! $\endgroup$ – Nischal Hp Mar 3 at 15:02
  • $\begingroup$ great explanation, thank you! $\endgroup$ – malioboro Mar 4 at 20:50
  • $\begingroup$ I am glad it was helpful! @malioboro $\endgroup$ – Vikas Bhandary Mar 5 at 6:04
  • $\begingroup$ You are welcome! @NischalHp $\endgroup$ – Vikas Bhandary Mar 5 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.