1.2 Embedding

1.2 Word Embedding

1.2.1 Introduction

1.2.2 Methods

OneHot

1. "apple" → One-hot encoding: [1, 0, 0]

2. "banana" → One-hot encoding: [0, 1, 0]

3. "cherry" → One-hot encoding: [0, 0, 1]

• Advantages:
One-hot encoding addresses the issue of classifiers not handling categorical data well. To a certain extent, it also helps with feature expansion. Its values are only 0 and 1, and different categories are stored in orthogonal space.

• Disadvantages: Using One-Hot encoding to represent word vectors is extremely simple, but the drawbacks are also quite obvious
• On one hand, the vocabulary size is often very large, often reaching millions. As the vocabulary grows, One-Hot vectors become very sparse and high-dimensional, which may not be suitable for large-scale text data processing. Such high-dimensional data processing consumes a large amount of computational resources and time.
In this case, dimensionality reduction methods like PCA are often used. The combination of one-hot encoding and PCA is useful in practice.
• On the other hand, in One-Hot encoding, all word vectors are mutually orthogonal, meaning there is no representation of similarity between words.

Word2Vec

• The input is context words (usually in One-Hot encoded form).

• Input to the model
• The first layer input_to_hidden maps One-Hot vectors into embedded vectors with a smaller dimension.
• The vectors of multiple context words are averaged to obtain an "overall representation of the context".
• The output layer hidden_to_output converts the overall representation of the context into a vector of the same size as the vocabulary (the possibility of scoring each word as the target word).

• After training, the input_to_hidden matrix is our word embedding matrix (look-up table)!

• Input: A word in the form of a one-hot vector.

• Model
• W: Embeds the input one-hot vector into a dense vector (word embedding).
• V: Projects the embedding back to the vocabulary space to predict context words.

• Predict one context word at a time for each (center word, context word) pair.
• For example: The quick brown fox , if we set window size = 1 , then for the center word "quick", the context is ["The", "brown"]. We would generate two training samples:
• Input: "quick" → Target: "The"
• Input: "quick" → Target: "brown"
• We want the model to assign higher probabilities to actual context words:
• P("The" | "quick") → high
• P("brown" | "quick") → high
• P("banana" | "quick") → low (because "banana" wasn’t a context word)

• Hierarchical softmax using a Huffman tree
To avoid computing softmax probabilities for all words, Word2Vec replaces the softmax mapping with a Huffman tree-based hierarchical softmax. Based on the words frequency, a Huffman tree is constructed to convert the multi-class classification problem into a series of binary classification problems. All internal nodes of the Huffman tree are similar to the hidden units in a neural network layer with learnable parameters. The number of leaf nodes equals the size of the vocabulary, and each represents a word.
📌
Previously, to calculate the probability of a target word, we applied softmax over the entire vocabulary — which is computationally expensive.
Now, we only use each internal node to do binary classification (i.e., to achieve the target word, should we go left or right?) with a value in (0, 1) using the sigmoid function. This value represents an intermediate probability. When we achieve the final target word, we will get such probs, and we multiply them all to get the real probability of the target word.
The advantages are summarized as follows:
• Computational efficiency: Since it is a binary tree, the time complexity is reduced from to approximately
• Greedy optimization: The high-frequency word paths are shorter (closer to the root), allowing faster retrieval, aligning with the concept of greedy optimization
Disadvantages of the Huffman tree: If the center word in our training corpus is a very rare word, then the path in the Huffman tree becomes very long. Negative sampling can solve this issue.

• Negative Sampling
Hierarchical Softmax in the Huffman tree uses a tree structure to replace neural networks, which can improve the efficiency of model training. However, if the center word in our training samples is a rare word, it may take a long time to reach the bottom of the Huffman tree.
in negative sampling method, for a given word w's context Context(w), the word w is a positive sample, and other words are negative samples.
• Negative sample subset:
• Given a positive sample: , the goal is to maximize:
Where:
Where: is context vector. Intuitively, we want words that are in the same context closer to each other, and vice versa. The negative sampling method modifies the loss function of Word2vec and only samples a few negative samples each time, instead of the whole vocabulary, to reduce the computation burden. Each time a training sample updates only part of the weights, while keeping the others fixed; this reduces computation (to some extent, it can also enhance randomness).
Example of Negative Sampling:
• When we input the training sample (input word: "fox", output word: "quick"), we train our neural network. "fox" and "quick" are encoded using one-hot vectors.
Let’s say our vocabulary size is 10,000; in the output layer, we hope that the "quick" word's position outputs 1 and all others are 0. These other positions correspond to negative words.
• When using negative sampling, we randomly select a small portion of negative words (e.g., 5 negative words) to update the corresponding weights. We also update the weights corresponding to our positive word (in this example, the word "quick").
• Assume the output layer is a (300, 10000) matrix. If we use negative sampling, we only update the weights corresponding to the positive word ("quick") and 5 other negative words — a total of 6 output neurons, so we only update 300×6 = 1800 weights per pass.
Sampling Method: Probability-based. We randomly sample according to word frequency. When we sample negative words, we tend to select more frequent words, e.g., "of". This is because such words are not very informative for predicting target words.
Word2Vec uses the 0.75th power of word frequency as a basis for sampling, making words with lower frequency more likely to be selected.

FastText

1. Loss Function: Cross-entropy loss

2. Hierarchical Softmax: Based on category frequency, a Huffman tree is constructed to replace the standard softmax. Using hierarchical softmax can reduce complexity from to . The diagram below shows an example of hierarchical softmax:



Specifically, in this Huffman tree, all internal nodes each contain a parameter and a sigmoid function. Different nodes have different values. During training, the hidden layer vector is used as input from top to bottom. Based on the result at each node, classification is done: if the classification is negative, the vector is passed to the left child of the tree and the code is 0; if positive, to the right child, and the code is 1.

3. N-gram feature: The text content is transformed into sequences of N-length character (or bytes) fragments using a sliding window operation. In the end, the window generates a sequence of character segments of size N.
Additionally, note that an N-gram can have different meanings depending on the granularity — there are character-level n-grams, byte-level n-grams, and word-level n-grams.

1. Filtering out rare words

2. Using hash storage

3. Changing the granularity from character-level to word-level n-grams