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."

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."

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?"

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."

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."

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?"

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."

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 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."

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."

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."

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."