8. Transformers › 8.1 Tokenization

Section 8.1
Tokenization

The transformer models was originally designed for natural language processing tasks, and as we saw in the last lecture, the first step in being able to process language data is to encode text into a form amenable for numerical calculations in a deep learning model. The mechanism for converting symbolic data into vectors is called tokenization. One way to think about this is as a mapping from the discrete set \(\{1, 2, \ldots, m\}\) to the space of \(d\)-dimensional vectors, \(\reals^d\). Here each element in the set \(\{1, 2, \ldots, m\}\) indexes a discrete item from the universe of symbols, e.g., a vocabulary of words or \(n\)-grams. An example is shown in Figure 107.

Tokenization breaks long sentences into a sequence of words (or sub-words) and the represents each as a vector. Observe that the same word (e.g., “the” in the s
Figure 107: Tokenization breaks long sentences into a sequence of words (or sub-words) and the represents each as a vector. Observe that the same word (e.g., “the” in the sentence above) gets mapped to the same embedding vector irrelevant of where it appears in the sentence.

To make this more concrete, let \(E: {\cal V} \to \reals^d\) be an encoder from fixed vocabulary \({\cal V}\) to \(n\)-dimensional vectors. This can be implemented, for example, via a lookup table. Then a sequence of \(T\) words \(\langle w_t \in {\cal V} \mid t = 1, \ldots, T\rangle\) gets encoded as a sequence of tokens \(\langle z_t = E(w_t) \in \reals^d \mid t = 1, \ldots, T\rangle\), as illustrated in Figure 108. In practice, we tokenize sub-words (or \(n\)-grams) rather than full words. Pre-processing is sometimes carried out before converting a piece of text into a sequence of vectors to reduce words to their stems, i.e., part of the word that captures lexical meaning, filter stop words, i.e., common words that carry little meaning, or compress whitespace. However, this has become less important for massive models trained on internet-scale data.

Tokenization of a sequence of words results in a sequence of -dimensional tokens (vectors)
Figure 108: Tokenization of a sequence of words results in a sequence of \(n\)-dimensional tokens (vectors).

We can also decode from tokens back to words using a decoder model, \(D: \reals^d \to \cV\). Here we need to worry about the fact that some vectors in \(\reals^d\) may not correspond to vectors hit by the encoder \(E\). Mathematically, we say that the encoder function \(E\) is not surjective, meaning that it only maps onto part of \(\reals^d\). There are two standard approaches to get around this difficulty. The first approach is to take the nearest encoded vector to an arbitrary vector \(z \in \reals^d\),

\begin{align} D(z) &= \argmin_{w \in \cV} \|E(w) - z\|^2 \tag{244}\end{align}

which effectively divides \(\reals^d\) into piecewise constant regions associated with each word \(w \in \cV\). The second approach is to treat the decoder as a stochastic function. Instead of a deterministic decoder function \(D\), we define (or learn) a discrete distribution \(P_D\) over the embedding space and sample a word from this discrete distribution,

\begin{align} w \sim P_D(w \mid z) \tag{245}\end{align}

For example, if \(z\) and \(E(w)\) are both normalized, then we could define \(P_D\) as

\begin{align} P_D(w \mid z) &= \textbf{softmax}(E(w)^T z \mid w \in {\cal V}). \tag{246}\end{align}

There are several research works that propose how to assign vectors to words, i.e., how to structure the embedding space. In the skip-gram model [71], the high-level idea is to train an encoder model on a large text corpus, \(\cT\), with the desired property that words appearing close to each other in the corpus should have vector representations that are close to each other in embedding space. Consider word \(w_i\) with neighbouring words

\begin{align} \cN_i &= \{w_{i-n}, w_{i-n+1}, \ldots, w_{i-1}, w_{i+1}, \ldots, w_{i+n-1}, w_{i+n}\} \tag{247}\end{align}

for some neighbourhood size \(n\), e.g., \(n = 4\). We want \(w_i\) to be a good predictor of \(w_j \in \cN_i\), i.e., we want to maximize the log-likelihood of the conditional probability of adjacent words to a given word for every word in the corpus,

\begin{align} \sum_{w_i \in \cT} \sum_{w_j \in \cN_i} \log P(w_j \mid w_i) \tag{248}\end{align}

Given a training text corpus \(\cT\), this is a self-supervised objective. The distribution \(P\) can be modelled as the softmax over embedding similarity, i.e.,

\begin{align} P(w_j \mid w_i) &\propto \exp(z_i^T z_j) \tag{249}\end{align}

where \(z_i\) and \(z_j\) are the vector representations of \(w_i\) and \(w_j\), respectively, and are the free parameters to be optimized.

Many others approaches and variants of this idea have been proposed, such as GloVe [81] and BERT [22]. For the purposes of these lectures, we will assume that a pre-trained embedding model is supplied, and that the embedding space also contains special tokens such as the start-of-sequence and end-of-sequence tokens discussed in the last lecture.

8.1.1 Positional Encoding

In addition to encoding a word (or \(n\)-gram) as a vector, transformers also encode the location that each word appears in the sequence. This is done with a clever technique known as positional encoding. Here, the \(k\)-th position in a sequence is encoded as a \(d\)-dimensional vector \(\psi_k\) with \((2i)\)-th and \((2i+1)\)-th elements1 determined as

\begin{align} \psi_k(2i) &= \sin \left(\frac{k}{n^{(2i/d)}}\right) \tag{250}\\ \psi_k(2i+1) &= \cos \left(\frac{k}{n^{(2i/d)}}\right) \tag{251}\end{align}

for \(i = 0, \ldots, \frac{d}{2} - 1\). The elements in the positional encoding vector represent a geometric progression of wavelengths from \(2 \pi\) to \(2 \pi n\) as illustrated in Figure 109 (Vaswani et al. [103] set \(n = 10^4\)).

The position encoding vectors are added to the word embedding vectors for each token to give

\begin{align} w_k \gets w_k + \psi_k \tag{252}\end{align}

as the vector representation of the token at the \(k\)-th position.

Positional encoding for transformer models
Figure 109: Positional encoding for transformer models.

The transformer architecture itself has no notion of order.2 As such, without positional encoding (or masking, which we will see later) the transformer is technically a set processing model rather than a sequence processing model. Positional encoding allows the model to reason about the order of tokens in the set, thus defining a sequence.

A new type of positional encoding called rotational positional embeddings (RoPE) [95] has become popular in recent years. This replaces the standard additive positional encoding with a multiplicative rotation that preserves relative distance between tokens when performing scaled-dot product attention, i.e., shifting two tokens along a sequence shouldn’t change their relative distance. Details can be found in Su et al. [95] for the interested student.

  1. 1. Indexing here is zero-based.
  2. 2. This property is called permutation equivariant—if we shuffle the input tokens, the outputs shuffle in the same way.