Transformers Made Simple: A User-Friendly guide to Formal Algorithms for Transformers

Transformers have revolutionized the field of natural language processing and artificial neural networks, becoming an essential component of many groundbreaking applications. However, understanding the intricate details of these architectures and algorithms can be challenging for those who are new to the subject or have limited technical knowledge. This article aims to simplify and break down the complex concepts presented in the paper "Formal Algorithms for Transformers," making it more accessible to a wider audience.

In this article, we will provide a clear, easy-to-understand overview of transformer architectures, their training process, applications, key components, and a glimpse of the most prominent models in the field. Our goal is to make this advanced topic more approachable, enabling readers with a basic understanding of machine learning and simpler neural network architectures, such as multilayer perceptrons (MLPs), to gain insights into the world of transformers.

By the end of this article, you will have a solid grasp of the fundamentals of transformers and be better equipped to explore further literature, engage in discussions, or even implement your own transformer-based applications. Join us on this exciting journey to unravel the mysteries behind one of the most powerful and versatile technologies in artificial intelligence today.

?

1. Introduction

Transformers are a type of artificial neural network with a self-attention mechanism. They have been highly successful in natural language processing tasks and other areas. Since their introduction five years ago, many variations have been proposed. However, descriptions of transformers are usually graphical, verbal, partial, or incremental, and no pseudocode has been published for any version, unlike other fields of computer science or related disciplines like reinforcement learning.

This paper aims to provide a comprehensive, concise, and accurate overview of transformer architectures and formal algorithms. It covers various aspects of transformers, such as their structure, training, uses, key components, tokenization, practical considerations, and notable models. The authors believe that these formal algorithms will be helpful for theoreticians, researchers, and those looking to implement a transformer from scratch or augment their paper or textbook with formal transformer algorithms.

By understanding this document, a reader will have a solid grasp of transformers and be ready to engage with the literature on the topic or implement their own transformer using the provided pseudocode as a template (not included for this simplified explanation).

2. Transformers and Typical Tasks

Transformers are a type of neural network model that are highly skilled at processing natural language and, more broadly, handling sequential data. They are frequently employed for tasks such as sequence modeling and predicting one sequence from another.

Notation

1. Vocabulary: A vocabulary is a finite set, which means it has a limited number of items. These items could be words, letters, or tokens.
2. Tokens: Tokens are smaller parts of words. They are often used instead of complete words or letters when working with text.
3. Sequences: A sequence is an ordered arrangement of tokens, like sentences, paragraphs, or documents.
4. Arrays and Indexing: In this explanation, arrays start from 1 instead of 0, which is different from programming languages like Python. When discussing an array, the first item is included in the range.
5. Matrices: A matrix is a grid of numbers with rows and columns. The text talks about a specific way of working with matrices, where the rows and columns are transposed or flipped. This is different from the standard method used in some literature.

Chunking

In machine learning, the common practice is to learn from independent and identically distributed (i.i.d.) data. This is also done for sequence modeling. When working with long articles or texts, they may be divided into smaller parts (called chunks) to fit within the limitations of certain models, like transformers.

Sequence Modeling (DTransformer)

Sequence modeling is a technique used in machine learning to understand patterns in sequences of data. The goal in sequence modeling is to learn an estimate of the probability distribution of sequences in a dataset. In other words, we aim to figure out the likelihood of a particular sequence of data appearing in a dataset. By learning this probability distribution, the model can predict what the next element in a sequence might be, or classify a sequence based on its content. This can be useful for a wide range of applications, such as natural language processing, reinforcement learning policy distillation and music composition.

Sequence-to-Sequence Prediction (EDTransformer)

Sequence-to-sequence prediction is a technique in machine learning where we try to understand the relationship between two sequences of data. In other words, the aim in sequence-to-sequence prediction is to learn an estimate of the conditional distribution of one sequence given another sequence. To do this, we use a process called estimation, where we break down the problem into smaller steps. We try to estimate the likelihood of a certain sequence appearing given another sequence and use that information to make predictions about new sequences of data. Examples of sequence-to-sequence prediction include translation, question answering, and text-to-speech.

Classification (ETransformer)

Classification involves assigning a class or label to a given sequence of data. Put differently, the goal of classification is to learn an estimate of the conditional distribution of a class given a sequence. This means the model learns to assign a class or label to a sequence based on its training data. The models assigns a probability of a class to the sequence. ?Examples of classification tasks include sentiment classification, spam filtering, and toxicity classification.

3. Tokenization: How Text is Represented

Tokenization is the process of breaking down text into individual pieces called tokens, which can then be processed by the algorithm. These tokens can represent characters, words, or parts of words. This is important for natural language tasks because it helps models understand and process text data more effectively.

1. Character-level Tokenization: In character-level tokenization, the text is broken down into individual characters, including letters and punctuation marks. For example, the sentence "My grandma makes the best apple pie." would become a sequence of 36 characters: ['M', 'y', ' ', ...]. This method can result in very long sequences.
2. Word-level Tokenization: Word-level tokenization involves breaking down the text into individual words and punctuation marks. In the example sentence, this would result in a sequence of 7 tokens: ['My', 'grandma', 'makes', ...]. While this method requires a large vocabulary and may have difficulty handling new words, it is a more concise representation than character-level tokenization.
3. Subword Tokenization: This is the most common method used in practice today because it strikes a balance between character-level and word-level tokenization, providing a more efficient and flexible representation of text. ?Subword tokenization breaks text into commonly occurring subword units include prefixes, suffixes, and stems, as well as individual characters. Common words such as 'cious', 'ing', and 'pre' – the smallest units of meaning in a language. Common words and single characters are also included in the vocabulary to ensure all words can be expressed. There are many ways to perform subword tokenization, with one of the simplest and most successful methods being Byte Pair Encoding (BPE).
4. Final Vocabulary and Text Representation: Once a tokenization method is chosen, each token is assigned a unique index number. Special tokens are added to the vocabulary for specific purposes, such as indicating the beginning or end of a sequence or masking tokens in language modeling. The complete vocabulary consists of all tokens, including these special ones.

When representing a piece of text, the text is converted into a sequence of indices (called token IDs) that correspond to the chosen tokens. The sequence starts with the beginning-of-sequence token and ends with the end-of-sequence token.

4. Architectural Components

Components of a transformer, the building blocks, are outlined below.

1.?Token and Positional Embeddings: These are ways of representing words and their positions in a text as mathematical objects (vectors). Tokens represent the words, and positional embeddings capture the ordering of words in the text. These representations help the Transformer understand the meaning of words and their relationships to each other.

1. Attention: This is the main feature of a Transformer. It allows the model to focus on different parts of the text when trying to predict a word. For example, if the model is predicting the next word in a sentence, attention helps it focus on the most relevant words that have come before it. This helps the model make better predictions by using the surrounding context.
2. Bidirectional / Unmasked Self-Attention: This is a type of attention mechanism that allows the model to consider all tokens in a sequence as context when predicting a word, including tokens that come after the current word.
3. Unidirectional / Masked Self-Attention: This is another type of attention mechanism that only considers tokens that come before the current word when making predictions. This is useful for tasks where the model needs to predict one word at a time.
4. Cross-Attention: This is used when the model is working with two different sequences of tokens, such as in translation tasks. It allows the model to focus on relevant parts of the second sequence when making predictions for the first sequence.
5. Multi-Head Attention: This is a technique where multiple attention mechanisms, called attention heads, are used in parallel. Each head learns to focus on different parts of the text, and their combined output is used to make predictions. This allows the model to capture a richer understanding of the context.
6. Layer Normalization: This is a technique used to help improve the training of the model by making sure the outputs of each layer have a consistent scale and distribution. This can help speed up training and improve the final performance of the model.
7. Unembedding: This is the process of converting the mathematical representation of a word (a vector) back into a probability distribution over the possible words in the vocabulary. This is used when the model is making predictions, as it helps determine which word is most likely given the context.

5. Transformer Architectures

In this section, we discuss examples of transformer architectures, such as those used for understanding and generating human-like text. These architectures include EDT, BERT, and GPT. EDT is the original sequence-to-sequence/encoder-decoder transformer, while BERT and GPT are derived from it with some modifications. BERT is an encoder-only transformer, while GPT is a decoder-only transformer. The difference between BERT and GPT is mainly in attention masking, but they also differ in other ways like activation functions and the positioning of layer-norms. This section also provides a simplified notation for the parameters required by a multi-head attention layer.

1. Encoder-Decoder Transformer: This was the first Transformer model, initially used for translating text from one language to another. It has two parts: an encoder that understands the input text and a decoder that generates the translated text. The encoder looks at the entire input text to create a meaningful representation, while the decoder uses this representation to generate the translated text.
2. Encoder-only transformer (BERT) : This model is an example of an encoder-only Transformer, which means it only has the encoder part. BERT is trained to fill in the blanks in a piece of text. It was initially used to learn general patterns in text, which could then be adapted for different language-related tasks. BERT uses a different activation function called GELU, which helps it process text more effectively.
3. Decoder-only transformers (GPT and Gopher): These models are examples of decoder-only Transformers. They focus on predicting the next word in a sentence or paragraph. The primary difference between GPT/Gopher and BERT is that they use unidirectional attention, meaning they only look at the words that come before the current word, not those that come after. GPT-3, a later version of GPT, uses sparse attention, which means it only focuses on a subset of the context to predict the next word.
4. Multi-domain decoder-only transformer (Gato): This model is a multi-modal, multi-task Transformer developed by DeepMind. It can perform various tasks like playing games, navigating 3D environments, controlling robotic arms, captioning images, and having conversations. Gato can handle different types of data, such as images and text, and processes them using a decoder-only Transformer architecture.

6. Transformer Training and Inference

This section lists the pseudocode for various algorithms used for training and using transformers. These algorithms teach the models to perform specific tasks, like translating text, filling in the blanks, or predicting the next word in a sentence.

1. EDTraining(): This algorithm is used for training sequence-to-sequence Transformers, like the original Transformer model. It helps the model learn how to translate text from one language to another.
2. ETraining(): This algorithm is used for training Transformers on the task of masked language modeling, like BERT. It teaches the model to fill in the blanks in a given piece of text.
3. DTraining(): This algorithm is used for training Transformers on the task of predicting the next word in a sentence or paragraph, like GPT and Gopher. It helps the model learn how to complete sentences or paragraphs.
4. DInference(): This algorithm is used for prompting a Transformer trained on next word prediction, like GPT. It includes a "temperature" parameter that controls the creativity of the model's output. A lower temperature results in a more conservative prediction, while a higher temperature leads to more diverse and creative outputs.
5. EDInference(): This algorithm shows how to use a sequence-to-sequence Transformer for prediction. It can be applied to tasks like machine translation.

All these algorithms use a technique called Stochastic Gradient Descent (SGD) to minimize the difference between the model's predictions and the actual outcomes. In practice, more advanced versions of SGD, like RMSProp, AdaGrad, or Adam, are often used for better performance.

Gradient descent

Gradient descent is an optimization technique used in machine learning and deep learning models to find the best set of parameters that minimizes the error or loss function. In the context of training transformer models, here is an overview of gradient descent:

1. Objective: The primary goal of Gradient descent is to minimize the loss function, which measures the difference between the model's predictions and the actual outcomes. In this case, the loss function used is the log loss, also known as cross-entropy. The lower the loss, the better the model is at making predictions.
2. Gradients: The gradient of the loss function with respect to the model's parameters indicates the direction and rate of change of the loss function. By computing the gradient, we can determine the direction in which we need to update the parameters to minimize the loss.
3. Update rule: Stochastic Gradient Descent (SGD) is used in the given context as the update rule for the model's parameters. In SGD, a random sample of data is used to compute the gradient, which is then multiplied by a learning rate (??). The resulting value is subtracted from the current parameters (??) to update them.
4. Automatic differentiation: Computing the gradients for complex models like Transformers can be challenging. Automatic differentiation tools are used to efficiently compute the gradients for the loss function, which are then used in the update rule.
5. Variations of Gradient Descent: In practice, vanilla SGD is often replaced by more refined variations, such as RMSProp, AdaGrad, or Adam. These variations improve the optimization process by adapting the learning rate for each parameter individually, which can lead to faster convergence and better overall performance. Adam is the most commonly used variant nowadays.

7. Practical Considerations

The performance of transformers and other deep neural networks can be enhanced by employing various tricks and techniques related to data preprocessing, architecture, training, regularization, inference, and other aspects of model development and usage. These improvements help make the models more efficient, accurate, and robust.

1. Data preprocessing: This involves cleaning and preparing the data before it's fed into the model. Techniques such as data augmentation (creating new data by modifying existing samples), adding noise, and shuffling the data help create a more diverse and robust dataset for training.
2. Architecture: Improvements can be made to the model's structure. Sparse layers and weight sharing are examples of modifications that can make the model more efficient and effective.
3. Training: Several techniques can enhance the training process, such as using better optimization algorithms, dividing the data into smaller chunks (minibatches), normalizing input data, adjusting the learning rate during training, initializing weights properly, pretraining the model on related tasks, combining multiple models (ensembling), and using multi-task or adversarial training.
4. Regularization: To prevent overfitting and improve generalization, regularization techniques can be applied. These include weight decay (penalizing large weights), early stopping (ending training when performance stops improving), cross-validation (testing the model on different subsets of the data), dropout (randomly turning off some neurons during training), and adding noise to the model's input or weights.
5. Inference: To improve the model's ability to generate predictions, techniques like scratchpad prompting (providing additional context), few-shot prompting (giving a few examples to guide the model), chain of thought (linking multiple prompts), and majority voting (combining the predictions of multiple models) can be used.
6. Others: There are many other techniques and strategies that can be employed to improve the performance of deep neural networks, including transformers.

Source

Phuong, M., & Hutter, M. (2022). Formal Algorithms for Transformers. (July), 1–16. Retrieved from https://arxiv.org/abs/2207.09238