Subword Embeddings

The problem, from first principles

Word2vec gives every word its own vector, so a word never seen in training, a typo or an inflected form like "unhappiness" has no embedding at all. fastText fixes this by representing a word as the sum of the vectors of its character n-grams. The word is wrapped in boundary markers (< and >), so "where" becomes <where> and its 3-grams are <wh, whe, her, ere, re>. Because words that share morphemes share n-grams, "unhappy" and "unhappiness" automatically get related vectors, and an unseen word still receives a vector built from whatever of its n-grams were learned.

From theory to code

Implement char_ngrams and subword_embedding.

Constraints

• char_ngrams(word, n_min, n_max) wraps the word as '<' + word + '>' and returns the list of all character n-grams for n from n_min to n_max inclusive, ordered by n then by start position, followed by the whole wrapped word '<word>' itself (always appended last, even if its length falls inside the range, but not duplicated if it already appeared as an n-gram).
• subword_embedding(word, table, n_min, n_max, dim) averages the vectors table[g] over the n-grams (from char_ngrams) that are keys of table (a dict from string to length-dim arrays). If none are present return a zero vector of length dim.

Hints