Cross-Entropy: From Compression to LLMs

A 2002 paper titled 'Language Trees and Zipping' illustrated how generic compression techniques could reveal structural relationships between languages. Researchers utilized file compression to cluster languages without requiring prior linguistic knowledge. This study successfully rediscovered a tree of shared lineage among various languages, demonstrating that the approach functions by identifying common patterns across different texts.

Grant Sanderson notes, "The same trick can be used for other natural language tasks, like identifying who authored a given document."

The technique for comparing documents involves appending a small snippet of document B to the end of document A and then compressing the combined result. This method serves as a metric for assessing similarity between texts. Smaller resulting file sizes indicate stronger linguistic patterns shared between the two documents.

Grant Sanderson explains, "Given two documents, A and B, append a small snippet of B to the end of A, and compress the result."

Cross-entropy is a foundational concept that effectively bridges the theoretical gap between data compression and the practical training of modern language models (LLMs). The concept appears in both theoretical discussions of compression and the real-world application of training LLMs. The author suggests re-framing LLM training not merely as next-token prediction, but as a sophisticated form of compression.

Grant Sanderson states, "The specific concept underlying this example is something known as cross-entropy."

A simplified example of a biased random walk, involving directions like 'up,' 'down,' 'left,' and 'right,' demonstrates how probabilities dictate optimal bit allocation in encoding. Optimal encoding principles assign bits based on the negative log base 2 of a symbol's probability. High-frequency symbols, such as 'up' occurring 50% of the time, are assigned fewer bits, while rarer symbols receive more bits, all to minimize the overall length of the encoded message.

Grant Sanderson emphasizes, "The whole point of this toy example is that it's a concrete illustration of a much more general fact, which is that for an optimal code, the number of bits that you allocate to a given symbol looks like the negative log base 2 of the probability for that symbol showing up."

Claude Shannon established the negative logarithm of probability as the definition for the information content of an event. In practical applications, this information content is often expressed as a fractional number. When optimally encoding a long message, the total length is approximately the sum of the information content of all its individual symbols.

Grant Sanderson clarifies, "Claude Shannon defined this expression to be the information content of an event."

The efficiency of a compression scheme can significantly decline when the underlying data distribution changes from the one it was optimized for. For instance, if a system is hard-coded with probabilities for robot instructions (e.g., up 1/8, down 1/8, left 1/4, right 1/2) and the actual distribution shifts, the encoding becomes inefficient. Inefficiency is quantified by measuring the average number of bits required per message under the new context.

Grant Sanderson poses the question, "If you've optimized a compression scheme around one context, how does it perform in another context?"

To generalize the concept of average bits, the new distribution is denoted by P, while Q represents the original, optimized distribution for which the encoding scheme was designed. The average number of bits is calculated as the weighted sum of probabilities from the new distribution (P) multiplied by the information content derived from the original distribution (-log2 of Q).

Grant Sanderson states, "An encoding optimized for this first distribution, Q, allocates negative log base 2 of Q sub i bits to each symbol."

Cross-entropy, by definition, is this general expression that measures the average number of bits per symbol under a mismatched probability distribution. It can be visualized as a series of bars where the width represents the probability from distribution P, and the height signifies the information content, which is -log2(Q). This differs from the entropy of Q, where Q is used as both the weight and the base for the logarithm.

Grant Sanderson explains, "This general expression is, by definition, the cross entropy of the distribution Q relative to the distribution P."

Examining two-event distributions provides intuition for cross-entropy. An even distribution, like 50-50, has an entropy of 1 bit. In contrast, a skewed distribution, such as 90-10, requires less than 1 bit for its own optimal code. However, when an encoding optimized for a skewed distribution is applied to an even distribution, the cross-entropy significantly increases, highlighting the importance of matching distributions for efficient encoding.

Grant Sanderson points out, "Notice how much order matters here. When we swapped the roles of P and Q, the value of this cross entropy changed."

When cross-entropy is plotted as a function of Q, with P held constant, the graph reveals a very distinct minimum point. This minimum value is achieved precisely when the distribution P is identical to the distribution Q. This demonstrates that encoding efficiency is maximized when the distribution used for optimization perfectly matches the actual distribution of the data.

Grant Sanderson observes, "What you'll notice is this graph reaches a very clear minimum, and more specifically, the value where it achieves that minimum is the one where P and Q are identical."

Visualizing the relationship between cross-entropy and entropy demonstrates how moving the true distribution P changes the shape of the cross-entropy graph, tracing out a minimum value. The green curve on such a visualization represents the entropy of P as a function of its individual probabilities. Cross-entropy reaches its minimum when the predicted distribution Q precisely matches the true distribution P. At this point, the minimal value attained by cross-entropy is exactly the entropy of P.

Grant Sanderson illustrates, "this green curve is what the entropy of P would look like as a function of little p sub 1."

Applying cross-entropy to text compression helps quantify the difference between documents. The process involves comparing documents A and B by compressing document B after it's appended to document A. This compression difference serves as an approximation of cross-entropy, measuring how effectively a compression scheme optimized for one context performs when applied to another. While Gzip acts as an empirical, non-perfect estimator of cross-entropy, the concept effectively quantifies discrepancies in patterns between two different settings.

Grant Sanderson asks, "How well does a compression scheme optimized for one context perform when faced with another context?"

Cross-entropy plays a crucial role in the training of large language models by quantifying the difference between a model's understanding of language and its true patterns. Language models receive sequences of text as input and, in turn, produce probability distributions over potential next tokens. To assess the quality of these predictions during training, a loss function is essential. Modern LLMs, with their billions of parameters, operate within a high-dimensional loss surface, and training aims to minimize this loss through techniques like gradient descent and backpropagation.

Grant Sanderson explains, "what you want to quantify is how different a model's understanding of language is from the true patterns of language."

Once a robust loss function is defined for a machine learning model, the remaining training process is handled by established deep learning tools and methodologies. The loss function is designed to represent the model's performance across the vast amount of training data gathered from the internet. Consequently, minimizing this loss function directly correlates with improving the overall performance of the model.

An observer states, "trying to train a model, once you define a good loss function, you're essentially done. The standard machinery of deep learning takes it from there."

The loss function used in large language models can be conceptualized as measuring the average information per token from the model's perspective. The model generates probabilities for each potential next token in a sequence. The loss is then calculated by taking the negative logarithm of these predicted probabilities. Lower information values in this context signify higher confidence and greater accuracy in the model's predictions.

An observer notes, "A very nice way to think about the loss function we use in this case is that you measure the average information per token from the model's perspective."

The negative logarithm function is deliberately chosen for its role in the loss function because it imposes a severe penalty on the model when it assigns a very low probability to the true next token. Conversely, when the model assigns a high probability to the correct token, its contribution to the overall loss is minimal. This mechanism effectively punishes incorrect predictions steeply, guiding the model towards better accuracy.

An observer clarifies, "It's effectively telling you the model is punished, and punished very steeply, if it assigns a very low probability to the true next token."

Natural logarithms are favored over base-2 logarithms in machine learning, primarily due to their mathematical convenience in derivative calculations. While different logarithm bases are equivalent up to a constant factor, natural logarithms simplify the process of computing derivatives, which are a core component of the gradient descent algorithm used in model training. This simplification contributes to cleaner and more efficient algorithmic operations.

An observer explains, "The motive is just that natural logs are a lot cleaner whenever you're taking derivatives, and derivatives are the core part of the gradient descent algorithm."

The term 'cross-entropy loss' for language model training arises from mathematically framing the model's output against a perfectly skewed target distribution, even though the cross-entropy formula itself might not appear explicitly in the initial explanation. This involves calculating cross-entropy between the model's output and a target distribution that is heavily concentrated on the true next token. Through mathematical simplification, this calculation becomes identical to the negative log loss. There is a deeper, more satisfying justification for this label that goes beyond simple algebraic equivalence.

An observer questions, "people call it cross-entropy loss, which at first might sound really strange, given that nowhere in the explanation have we actually used the cross-entropy formula."