Language Modeling#

If one wanted to give an example of an NLP application, one of the best examples would be the next-word prediction feature of a smartphone keyboard. It’s a feature that billions of people use hundreds of times every day.

Next-word prediction is a task that can be addressed by a language model. A language model can take a list of words (let’s say two words), and attempt to predict the word that follows them. In practice, however, the model doesn’t output only one word. It actually outputs a probability score for all the words it knows (the model’s “vocabulary”, which can range from a few thousand to over a million words). The keyboard application then has to find the words with the highest scores, and present those to the user. After being trained, early neural language models would calculate a prediction in three steps:

The first step is the most relevant for us as we discuss embeddings. One of the results of the training process was this matrix that contains an embedding for each word in our vocabulary. During prediction time, we just look up the embeddings of the input word, and use them to calculate the prediction:

Let’s now turn to the training process to learn more about how this embedding matrix was developed.

Language Model Training#

Words get their embeddings by us looking at which other words they tend to appear next to. The mechanics of that is that

1. We get a lot of text data (say, all Wikipedia articles, for example). then
2. We have a window (say, of three words) that we slide against all of that text.
3. The sliding window generates training samples for our model

Here is an example:

The example above is trying to predict the target word by looking at two words before it, we can also look at two words after it. Another architecture that also tended to show great results does things a little differently and is the one we will be using as part of our following discussion: instead of guessing a word based on its context (the words before or maybe even after it), this architecture tries to guess neighboring words within certain radius using the current word. It is called Skipgram, which has a window sliding across the texts like this:

The word in the green slot would be the input(or current) word, each pink box would be a possible output within its radius. In this case, the radius is 2 (words)

A single snapshot of the sliding window creates four separate samples in our training dataset:

A couple of positions later, we have a lot more examples:

Now that we have our skipgram training dataset that we extracted from existing running text, let’s glance at how we use it to train a basic neural language model that predicts the neighboring word. We start with the first sample in our dataset. We grab the feature and feed to the untrained model asking it to predict an appropriate neighboring word.

The model conducts the three steps and outputs a prediction vector (with a probability assigned to each word in its vocabulary). Since the model is untrained, it’s prediction is sure to be wrong at this stage. But that’s okay. We know what word it should have guessed – the label/output cell in the row we’re currently using to train the model:

How far off was the model? We could choose to subtract the two vectors resulting in an error vector:

This error vector can now be used to update the model so the next time, it’s a little more likely to guess thou when it gets not as input.

And that concludes the first step of the training. We proceed to do the same process with the next sample in our dataset, and then the next, until we’ve covered all the samples in the dataset. That concludes one epoch of training. We do it over again for a number of epochs, and then we’d have our trained model and we can extract the embedding matrix from it and use it for any other application.

While this extends our understanding of the process, it’s still not how word2vec is actually trained. We’re missing a couple of key ideas.

The 3rd step (Project to output vocabulary) is very expensive from a computational point of view - especially knowing that we will do it once for every training sample in our dataset (easily tens of millions of times). We need to do something to improve performance, which is missing from the basic training strategy introduced above.

One solution for boosting the performance is to split our target into 2 steps:

1. Generate high-quality word embeddings (Don’t worry about next-word prediction).
2. Use these high-quality embeddings to train a language model (to do next-word prediction).

We will be focusing on step 1 as we’re focusing on embeddings. To generate high-quality embeddings using a high-performance model, we can switch the model’s task from predicting a neighboring word to taking the input and output word, and outputing a score indicating if they’re neighbors or not (0 for “not neighbors”, 1 for “neighbors”).

This simple switch changes the model we need from a neural network, to a logistic regression model - thus it becomes much simpler and much faster to calculate.

This switch requires we switch the structure of our dataset – the label is now a new column with values 0 or 1. They will be all 1 since all the words we added are neighbors.

This can now be computed at blazing speed – processing millions of examples in minutes. But there’s one loophole we need to close. If all of our examples are positive (target: 1), we open ourselves to the possibility of a smartass model that always returns 1 - achieving 100% accuracy, but learning nothing and generating garbage embeddings. To address this, we need to introduce negative samples to our dataset - samples of words that are not neighbors. Our model needs to return 0 for those samples. Now that’s a challenge that the model has to work hard to solve - but still at blazing fast speed.

But what do we fill in as output words? We randomly sample words from our vocabulary

This idea is inspired by Noise-contrastive estimation. We are contrasting the actual signal (positive examples of neighboring words) with noise (randomly selected words that are not neighbors). This leads to a great tradeoff of computational and statistical efficiency.

We have now covered two of the central ideas in word2vec: as a pair, they’re called skipgram with negative sampling:

Word2vec Training Process#

Now that we’ve established the two central ideas of skipgram and negative sampling, we can proceed to look closer at the actual word2vec training process.

Before the training process starts, we pre-process the text we’re training the model against. In this step, we determine the size of our vocabulary (we’ll call this vocab_size, think of it as, say, 10,000) and which words belong to it.

At the start of the training phase, we create two matrices – an Embedding matrix and a Context matrix. These two matrices have an embedding for each word in our vocabulary (So vocab_size is one of their dimensions). The second dimension is how long we want each embedding to be (embedding_size – 300 is a common value, but we’ve looked at an example of 50 earlier in our discussion here).

At the start of the training process, we initialize these matrices with random values. Then we start the training process. In each training step, we take one positive example and its associated negative examples. Let’s take our first-step data (highlighted in light blue rows):

Now we have 4 words: the input word not and output/context words: thou (the actual neighbor), aaron, and taco (the negative examples). We proceed to look up their embeddings - for the input word, we look in the Embedding matrix. For the context words, we look in the Context matrix (even though both matrices have an embedding for every word in our vocabulary).

Then, we take the dot product of the input embedding with each of the context embeddings. In each case, that would result in a number, that number indicates the similarity of the input and context embeddings

Now we need a way to turn these scores into something that looks like probabilities - we need them to all be positive and have values between zero and one. This is a great task for sigmoid, the logistic operation.

And we can now treat the output of the sigmoid operations as the model’s output for these examples. We can see that taco has the highest score and aaron still has the lowest score both before and after the sigmoid operations.

Now that the untrained model has made a prediction, and seeing as though we have an actual target label to compare against, let’s calculate how much error is in the model’s prediction. To do that, we just subtract the sigmoid scores from the target labels (error = target - sigmoid_scores).

Here comes the “learning” part of “machine learning”. We can now use this error score to adjust the embeddings of not, thou, aaron, and taco so that the next time we make this calculation, the result would be closer to the target scores.

This concludes the training step. We emerge from it with slightly better embeddings for the words involved in this step (not, thou, aaron, and taco). We now proceed to our next step (the next positive sample and its associated negative samples) and do the same process again.

The embeddings continue to be improved while we cycle through our entire dataset for a number of times. We can then stop the training process, discard the Context matrix, and use the Embeddings matrix as our pre-trained embeddings for the next task.

Window Size and Number of Negative Samples

Two key hyperparameters in the word2vec training process are the window size and the number of negative samples.

Different tasks are served better by different window sizes. One heuristic is that smaller window sizes (2-15) lead to embeddings where high similarity scores between two embeddings indicates that the words are interchangeable (notice that antonyms are often interchangable if we’re only looking at their surrounding words – e.g. good and bad often appear in similar contexts). Larger window sizes (15-50, or even more) lead to embeddings where similarity is more indicative of relatedness of the words.

The number of negative samples is another factor of the training process. The original paper prescribes 5-20 as being a good number of negative samples. It also states that 2-5 seems to be enough when you have a large enough dataset.

Example - Character-Level Language Model#

We all heard of this buz word “LLM” (Large Language Model). But let’s put that aside for just a second and look at a much simpler one called “character-level language model” where, for example, we input a prefix of a word such as “hell” and the model outputs a complete word “hello”. We call inputs like “hell” a sequence.

How do we train such model? One approach is to have one function invoked 4 times, with each time taking a single character as input and calculates an output:

Input for the function is actually a one-hot encoded vector representing a single character

In our “hello” example above, the input sequence would be “h”, “e”, “l”, “l”, “o”. For each of these characters, the input to the function is not the character itself, but a vector. This vector has a size equal to the total number of unique characters in our vocabulary, i.e. a vocabulary of four possible letters “helo”. For a specific character, the vector will have a value of 1 at the index corresponding to that character, and 0 everywhere else.

For example, the input for the character “h” would be a vector of length 4. This vector would have a value of 1 at the 1st position (since ‘h’ is the 1st letter of the alphabet) and 0s in all other 3 positions. The next input would be the one-hot encoded vector for “e”, and so on. This process allows the function to handle sequential data by processing one character at a time.

But one might have noticed that if the 3rd invocation produces $f('l') = 'l'$, then why would the 4th one, given the same input, outputs a different character of ‘o’? This suggests that we should take the history into account. Instead of having $f$ depend on 1 parameter, we now have it take 2 parameters.

1. a character, and
2. a variable that summarizes the previous calculations:

Now it makes much more sense with:

But what if we want to predict a longer or shorter word? For example, how about predicting “cat” by “ca”? That’s simple, we will have 2 black boxes to do the work.

What if the function $f$ is not smart enough to produce the correct output everytime? We will simply collect a lot of examples such as “cat” and “hello”, and feed them into the boxes to train them until they can output correct vocabulary like “cat” and “hello”.

This is the idea behind RNN. It’s recurrent because the boxed function gets invoked repeatedly for each element of the sequence. In the case of our character-level language model, element is a character such as “e” and sequence is a string like “hell”:

CAUTION

The diagram below is not multiple functions chained together, but a single function being repeatedly invoked

Each function $f$ is a network unit containing 2 perceptrons. One perceptron computes the “history” like $h_1$, $h_2$, $h_3$.

One great thing about the RNNs is that they offer a lot of flexibility on how we wire up the neural network architecture. Normally when we are working with neural networks, we are given a fixed sized input vector (red boxes below), then we process it with some hidden layers (green), and we produce a fixed sized output vector (blue). The left-most model in figure below is the Vanilla Neural Networks, which receives a single input and produce one output (The green box in between actually represents layers of neurons). The rest of the models on the right are all Recurrent Neural Networks that allow us to operate over sequences of input, output, or both at the same time:

• An example of one-to-many model is image captioning where we are given a fixed sized image and produce a sequence of words that describe the content of that image through RNN
• An example of many-to-one task is sentiment classification in NLP where we are given a sequence of words of a
• sentence and then classify what sentiment (e.g. positive or negative) that sentence is.
• An example of many-to-many task is machine translation in NLP, where we can have an RNN that takes a sequence of words of a sentence in English, and then this RNN is asked to produce a sequence of words of a sentence in German.
• There is also a variation of many-to-many task as shown in the last model in figure below, where the model generates an output at every timestep. An example of this many-to-many task is video classification on a frame level where the model classifies every single frame of video with some number of classes. We should note that we don’t want this prediction to only be a function of the current timestep (current frame of the video), but also all the timesteps (frames) that have come before this video.

TIP

A CNN learns to recognize patterns across space. So a CNN will learn to recognize components of an image (e.g., lines, curves, etc.) and then learn to combine these components to recognize larger structures (e.g., faces, objects, etc.)

A RNN will similarly learn to recognize patterns across time. So a RNN that is trained to translate text might learn that “dog” should be translated differently if preceded by the word “hot”.

The mechanism by which the two kinds of NNs represent these patterns is different, however. In the case of a CNN, we are looking for the same patterns on all the different subfields of the image. In the case of a RNN we are (in the simplest case) feeding the hidden layers from the previous step as an additional input into the next step. While the RNN builds up memory in this process, it is not looking for the same patterns over different slices of time in the same way that a CNN is looking for the same patterns over different regions of space.

It should be noted that “time” and “space” here shouldn’t be taken too literally. We could run a RNN on a single image for image captioning, for instance, and the meaning of “time” would simply be the order in which different parts of the image are processed. So objects initially processed will inform the captioning of later objects processed.

The sequence regime of operation is much more powerful compared to fixed networks that are doomed from the get-go by a fixed number of computational steps. Moreover, as we’ll see in a bit, RNNs combine the input vector with their state vector with a fixed (but learned) function to produce a new state vector. This can in programming terms be interpreted as running a fixed program with certain inputs and some internal variables. Viewed this way, RNNs essentially describe programs. In fact, it is known that RNNs are Turing-Complete in the sense that they can simulate arbitrary programs (with proper weights).

Space → Time v.s. Function → Program

If training vanilla neural nets is optimization over functions, training recurrent nets is optimization over programs.

If our data is not in form of sequences, we can still formulate and train powerful models that learn to process it sequentially. we are learning stateful programs that process our fixed-sized data.

At the core, RNNs accept an input vector x and give us an output vector y. This output vector’s contents are influenced not only by the input we just fed in, but also on the entire history of inputs we’ve fed in from the past. The RNN’s API consists of a single step function:

1
rnn = RNN()
2
y = rnn.step(x) # x is an input vector, y is the RNN's output vector

This is where RNN starts to model the notion of “memory”: The RNN class has some internal state that is updated every time step() is called. In the simplest case this state consists of a single hidden vector h:

1
class RNN:
2
    # ...
3
    def step(self, x):
4
        # update the hidden state
5
        self.h = np.tanh(np.dot(self.W_hh, self.h) + np.dot(self.W_xh, x))
6
        # compute the output vector
7
        y = np.dot(self.W_hy, self.h)
8
        return y

The step function above specifies the forward pass of RNN. There are 3 parameters $W_hh$, $W_xh$, and $W_hy$. The hidden vector, or more generally the hidden state, is defined by

where $t$ is the index of the “black boxes” shown earlier. In our example of “hell”, $t \in \{ 1, 2, 3, 4 \}$. The hidden state $h$ is usually initialized with zero vector (simulating “no memory at all”). There are 2 terms inside the $g_1$:

1. one term based on the previous hidden state $W_{hh}h^{(t - 1)}$, and
2. the other term based on the current input $W_{xh}x^{(t)}$

In the program above we use numpy np.dot which is a matrix multiplication. The 2 terms interact with addition.

We initialize matrices $W_hh$, $W_xh$, and $W_hy$ with random numbers and the bulk of work during training goes into finding the matrices that gives rise to the desirable behavior, as measured with some loss function that expresses our preferences to what kind of output y we would like to see in response to our input sequence x

The value $y$ is given by

What are $g_1$ and $g_2$?

They are activation functions which are used to change the linear function in a perceptron to a non-linear function. Please refer to Machine Learning by Mitchell, Tom M. (1997), Paperback (page 96) for why we bump it to non-linear

A typical activation function for $g_1$ is $tanh$:

$$tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$$

which squashes the activations to the range $[0, 1]$

In practice, $g_2$ is constance, i.e. $g_2 = 1$

We get RNNs as neural networks if we stack up as follows:

1
y1 = rnn1.step(x)
2
y = rnn2.step(y1)

In other words we have two separate RNNs: One RNN is receiving the input vectors and the second RNN is receiving the output of the first RNN as its input. Except neither of these RNNs know or care - it’s all just vectors coming in and going out, and some gradients flowing through each module during backpropagation.