Use of Information Theory in Learning Theory
1. Sources and Codes
Imagine that Alice observes one outcome and must send Bob a binary message from which he can recover it. Before discussing “information” or “uncertainty,” there is a concrete question:
How many bits should Alice assign to each possible outcome?
We will answer only that question at first. Probability, surprisal, cross-entropy, entropy, and KL divergence will then appear one at a time because the previous concept leaves a specific coding question unanswered. All logarithms are base two, so lengths are measured in bits.
1.1 From Code Length to Probability-Aware Coding
Before counting bits, we need to say where the outcomes come from. A source is a process that produces data. Its set of possible outputs is called an alphabet \(\mathcal Z\). Examples include:
- a coin producing
headsortails; - a sensor producing one of several readings;
- a text process producing the next character or token.
The source is not one particular output. It is the repeatable mechanism that may emit many outputs \(Z_1,Z_2,\ldots\). In the simplest memoryless model, each output is drawn independently from the same distribution \(p(z)\). This distribution tells us the long-run frequency with which each symbol appears.
Why encode a source? Computers store and communication channels transmit bits, while the source produces symbols such as words, labels, or sensor values. An encoder maps each emitted symbol—or a block of symbols—to bits; a decoder must recover the original data. We want this mapping to be lossless while using as few bits as possible.
Strictly speaking, we do not encode the abstract source or the distribution \(p\) itself. We encode the outputs produced by the source, using a code designed around their frequencies. “Encoding the source” is standard shorthand for this operation. For one isolated output, saving a fraction of a bit is not very meaningful; over a long sequence, small savings in average length accumulate into substantial storage or transmission savings.
Now suppose the source alphabet has eight possible outcomes and, for the moment, we use the same number of bits for all of them. Three bits are enough:
\[000,001,010,011,100,101,110,111.\]The reason is counting: \(\ell\) bits create \(2^\ell\) distinct strings. Therefore, distinguishing \(N\) equally treated outcomes requires at least
\[\ell=\lceil\log_2N\rceil\]bits. This statement involves no probabilities and no entropy. It is simply the capacity of a binary description.
There is another useful way to see the same count. Imagine all infinite binary sequences as a unit interval. Fixing the first bit selects half of them. Fixing two bits selects one quarter. In general, a particular prefix of length \(\ell\) occupies
\[\underbrace{\frac12\times\cdots\times\frac12}_{\ell\text{ times}}=2^{-\ell}\]of the binary coding space. A shorter prefix reserves a larger region; a longer prefix reserves a smaller one. This geometric fact—length \(\ell\) corresponds to a share \(2^{-\ell}\)—is the bridge from code lengths to probabilities, but we have not crossed that bridge yet.
1.1 从码长到概率感知编码
Why should frequency affect code length at all? Consider four outcomes with frequencies
\[A:\frac12,\qquad B:\frac14,\qquad C:\frac18,\qquad D:\frac18.\]A fixed-length code for four outcomes needs two bits each, for example 00, 01, 10, 11. In eight transmissions, we expect to send \(A\) four times, \(B\) twice, and \(C,D\) once each. The fixed-length code therefore uses
Now try 0, 10, 110, 111. Bob can still decode the stream because no codeword is the beginning of another. The same eight outcomes use
The common outcome \(A\) saves one bit on each of four appearances. The rare outcomes \(C,D\) each cost one extra bit, but they appear only once. The frequent savings outweigh the rare extra costs. That is why equal-length codes waste bits when frequencies are unequal: they spend scarce short descriptions on outcomes that hardly occur.
This example suggests the rule we want to formalize: common outcomes should receive short codewords and rare outcomes may receive longer ones.
A safe variable-length code must still be decodable. The usual requirement is prefix-free: no complete codeword may be the prefix of another. Such a code is a binary tree, and its lengths obey the Kraft inequality
\[\sum_z2^{-\ell(z)}\le1.\]The meaning is concrete: \(2^{-\ell(z)}\) is the region reserved by the prefix for outcome \(z\), and disjoint regions cannot occupy more than the whole coding space.
Now introduce a distribution \(q(z)\). Think of \(q\) as the encoder’s belief about how frequently outcomes will occur. To allocate a fraction of coding space close to \(q(z)\), match
\[2^{-\ell_q(z)}\approx q(z).\]Solving for length gives the ideal, possibly fractional code length
\[\boxed{\ell_q(z)=-\log_2q(z)}.\]The same quantity is called the self-information or surprisal of outcome \(z\) under \(q\):
\[I_q(z)=-\log_2q(z).\]The name “surprisal” is intuitive, but code length is the derivation: an outcome to which the encoder assigns small probability receives little coding space and therefore needs a long address. The logarithm also makes the lengths of two independent outcomes add:
\[-\log_2[q(z_1)q(z_2)]= -\log_2q(z_1)-\log_2q(z_2).\]For dyadic probabilities the correspondence is exact:
| Outcome | \(q(z)\) | Codeword | \(\ell_q(z)\) |
|---|---|---|---|
| A | \(1/2\) | 0 | 1 |
| B | \(1/4\) | 10 | 2 |
| C | \(1/8\) | 110 | 3 |
| D | \(1/8\) | 111 | 3 |
For example, the prefix 10 occupies one quarter of the coding space, matching \(q(B)=1/4\), and has length \(-\log_2(1/4)=2\) bits.
Real codewords have integer lengths, whereas \(-\log_2q(z)\) can be fractional. Huffman coding chooses integer tree depths. Arithmetic coding instead encodes a long sequence as one interval, so its length per symbol can approach the fractional ideal arbitrarily closely. From now on, “code length” means this ideal or asymptotic length unless stated otherwise.
1.2 Describing Real Data with a Model Distribution: Cross-Entropy
We now give a model distribution \(q\) the job of describing data generated from the real distribution \(p\). The model first assigns every possible outcome a probability \(q(z)\). As Section 1.1 showed, this probability implies the ideal code length \(\ell_q(z)=-\log_2q(z)\) when outcome \(z\) occurs.
Cross-entropy is not the distribution \(q\) by itself. It is the score obtained when the probabilities supplied by \(q\) are repeatedly tested on outcomes supplied by \(p\). To turn the one-outcome cost into an overall model cost, we therefore need to know how often each outcome actually occurs.
Separate the two roles explicitly:
- \(p(z)\) is the true data-generating distribution;
- \(q(z)\) is the encoder’s model, which determines the lengths.
Suppose outcome \(z\) appears in a fraction \(p(z)\) of a long sequence. Its code length \(-\log_2q(z)\) is then paid with that same frequency. Therefore
\[\begin{aligned} \text{average length} &=\sum_z \underbrace{p(z)}_{\text{frequency}}\underbrace{[-\log_2q(z)]}_{\text{length when }z\text{ occurs}}\\ &=\mathbb E_{Z\sim p}[-\log_2q(Z)]. \end{aligned}\]This average is called the cross-entropy:
\[\boxed{H(p,q)=-\sum_zp(z)\log_2q(z)}.\]Nothing new was assumed: it is simply “frequency times cost, summed over outcomes.” Notice why the distributions occupy different positions. The outer weight is \(p\) because reality decides what appears; the logarithm contains \(q\) because the encoder decides the length.
What does “the same outcome space” mean? Let \(\mathcal Z\) be the list of results that may occur. Both distributions must refer to that same list:
\[p:\mathcal Z\to[0,1],\qquad q:\mathcal Z\to[0,1].\]For example, if \(\mathcal Z=\{\text{cat},\text{dog},\text{bird}\}\), then \(p\) describes how often those three labels truly occur, while \(q\) gives the encoder’s or classifier’s probabilities for those same three labels. When “dog” occurs, its true frequency \(p(\text{dog})\) weights the length \(-\log_2q(\text{dog})\). The two entries must name the same event for this product to make sense.
A distribution over weather outcomes \(\{\text{sun},\text{rain}\}\) cannot be used as \(q\) when \(p\) is over animal labels: there is no shared outcome \(z\) whose true frequency and assigned code length can be paired. We also require \(q(z)>0\) whenever \(p(z)>0\); otherwise a possible result is assigned an infinite code length.
Therefore, cross-entropy compares two probability assignments over the same possible results. It is not a measure of association between two random variables. We also did not need entropy to derive it—only a model-based code length and a true occurrence frequency.
With samples \(z_1,\ldots,z_n\), replace the population frequencies by an empirical average:
\[\widehat H(p,q)=-\frac1n\sum_{i=1}^n\log_2q(z_i).\]1.2 用模型分布描述真实数据：交叉熵
1.3 The Cost That Remains with a Perfect Model: Entropy
Keep the roles fixed: outputs are generated by a source whose true distribution is \(p\), while we choose a model \(q\) and use it to assign probabilities and hence code lengths. Thus in \(H(p,q)\), the first argument describes the source distribution and the second describes the coding model. With \(p\) held fixed, the next question is: how small could this cost become if the model were perfect?
The theoretical answer assumes that \(p\) is known. In practice it is unknown, which is precisely why a model must learn an approximation \(q\) from samples.
If the encoder knows the true distribution, it should allocate coding space according to that same distribution: set \(q=p\). The code length for one outcome becomes
\[\ell_p(z)=-\log_2p(z),\]and its average becomes
\[\boxed{H(p)=\mathbb E_{Z\sim p}[-\log_2p(Z)]=-\sum_zp(z)\log_2p(z)}.\]The average cost that still remains at this perfect-model reference point is the Shannon entropy. Entropy is not the act of making a model fit reality, nor does its definition claim that a learned model is actually perfect. It is a property of \(p\): the irreducible expected information in source outcomes when the probability model has no mismatch. Thus it is the special value of cross-entropy obtained under the theoretical choice \(q=p\):
\[H(p)=H(p,p).\]Does Shannon entropy assume that we know \(p\)? The definition treats \(p\) as the source’s true distribution, but it does not claim that an observer knows it. These are different statements:
- the source has some distribution \(p\);
- we know \(p\) well enough to calculate or use it.
Exact knowledge is possible when the mechanism is specified by construction—for example, a programmed random generator or an idealized fair die. If \(p\) is an unknown real-world distribution, however, a finite sample cannot determine it exactly in general. Events not seen in the sample may still have positive probability, and many different distributions can produce the same finite observations.
For a finite alphabet, a common estimate replaces \(p\) by empirical frequencies
\[\widehat p_n(z)=\frac1n\sum_{i=1}^n\mathbf 1\{Z_i=z\},\]and computes
\[\widehat H_n=-\sum_z\widehat p_n(z)\log_2\widehat p_n(z).\]Under an i.i.d. finite-alphabet assumption, this plug-in estimate converges to \(H(p)\) as \(n\to\infty\). At finite \(n\) it has sampling uncertainty, typically underestimates entropy, and can miss rare outcomes. For large or structured spaces—natural language is the main example—estimating the full entropy is much harder because most possible contexts and sequences are never repeated.
There is an important measurement asymmetry. We can estimate the cross-entropy of a fixed model \(q\) directly on held-out samples without knowing the numerical values of \(p(z)\):
\[\widehat H(p,q)=-\frac1n\sum_{i=1}^n\log_2q(z_i).\]The samples supply occurrences from \(p\), and the model supplies their lengths. But this measures \(H(p,q)=H(p)+D_{\mathrm{KL}}(p\Vert q)\). Without more assumptions, it does not tell us how much came from the source’s entropy and how much came from model mismatch. In an LLM, held-out next-token loss estimates model cross-entropy; the true conditional entropy of language is generally not directly observable.
Compression offers another operational estimate: a strong universal compressor can approach the entropy rate for certain stationary ergodic sources. A finite compressed file is still not an exact entropy measurement—it includes model mismatch, headers, finite-length overhead, and implementation constraints.
Entropy is a property of a distribution, not of one realized outcome. A single outcome has a code length or surprisal; the distribution has an average length or entropy.
For a Bernoulli source with \(p(Z=1)=\theta\),
\[H_2(\theta)=-\theta\log_2\theta-(1-\theta)\log_2(1-\theta).\]If \(\theta=0\) or \(1\), the outcome is known in advance and the ideal average length is zero. If \(\theta=1/2\), both outcomes are equally likely and one bit is necessary. More generally,
\[0\le H(Z)\le\log_2\lvert\mathcal Z\rvert,\]with the maximum attained by the uniform distribution.
Does Shannon entropy measure the shortest code length? It depends on which notion of length is intended:
- Ideal real-valued length: yes. Assigning \(\ell(z)=-\log_2p(z)\) gives the average \(H(Z)\) exactly.
-
One-symbol binary prefix code: not always exactly. Actual codewords contain an integer number of bits, and the optimal expected length \(L_1^*\) satisfies
\[H(Z)\le L_1^*<H(Z)+1.\]Equality is possible when all nonzero probabilities are dyadic, so every \(-\log_2p(z)\) is an integer. Otherwise an integer code generally sits above entropy. For example, if two outcomes have probabilities \(0.9\) and \(0.1\), any one-symbol binary prefix code needs two distinct codewords such as
0and1, hence \(L_1^*=1\) bit, while \(H_2(0.1)\approx0.469\) bit. -
Long-block or arithmetic code: yes in the asymptotic per-symbol sense. Encoding blocks of \(n\) source symbols lets the fixed rounding overhead be shared across the block, so
\[H(Z)\le\frac{L_n^*}{n}<H(Z)+\frac1n.\]The gap per symbol tends to zero as \(n\to\infty\).
Thus Shannon entropy is best described as the fundamental lower bound and asymptotically achievable rate for lossless compression of a known memoryless source—not necessarily the exact length of the shortest finite codeword or even the exact optimum for a one-symbol code. For sources with memory, the corresponding limit is the entropy rate; for lossy compression, the relevant limit is the rate–distortion function rather than entropy alone.
1.3 完美模型仍需付出的代价：熵
1.4 The Cost of Using the Wrong Code: KL Divergence
We now have two average lengths for the same source \(p\):
- \(H(p)\): use the matched code built from \(p\);
- \(H(p,q)\): use the code built from another distribution \(q\).
The natural measure of mismatch is simply the extra length:
\[\begin{aligned} H(p,q)-H(p) &=\sum_zp(z)[-\log_2q(z)]-\sum_zp(z)[-\log_2p(z)]\\ &=\sum_zp(z)\log_2\frac{p(z)}{q(z)}. \end{aligned}\]This difference is the Kullback–Leibler divergence:
\[\boxed{D_{\mathrm{KL}}(p\Vert q)=\mathbb E_{Z\sim p}\!\left[\log_2\frac{p(Z)}{q(Z)}\right]}.\]Therefore the central identity is not a separate fact to memorize; it is the bookkeeping equation “mismatched length = matched length + extra length”:
\[\boxed{H(p,q)=H(p)+D_{\mathrm{KL}}(p\Vert q)}.\]Why is the extra cost nonnegative? The ideal or asymptotic code matched to the true frequencies is optimal in expected length; changing its allocation cannot improve the average. Formally, Gibbs’ inequality gives
\[D_{\mathrm{KL}}(p\Vert q)\ge0,\]with equality when the normalized distributions \(p\) and \(q\) are the same (ignoring zero-probability events). KL is therefore nonnegative, not strictly positive.
Why, then, do “KL” values sometimes look negative in everyday training? The nonnegativity statement applies to the complete expectation, not to every outcome inside it. The pointwise log-ratio
\[\log_2\frac{p(z)}{q(z)}\]is negative whenever \(p(z)<q(z)\). For example, let \(p=(0.9,0.1)\) and \(q=(0.5,0.5)\). The two contributions to forward KL are
\[0.9\log_2\frac{0.9}{0.5}\approx0.763, \qquad 0.1\log_2\frac{0.1}{0.5}\approx-0.232.\]The second contribution is negative, but the full sum is
\[D_{\mathrm{KL}}(p\Vert q)\approx0.763-0.232=0.531\ge0.\]The same distinction applies to estimation. If we sample \(Z_i\sim p\) and report
\[\widehat D=\frac1n\sum_{i=1}^n\log_2\frac{p(Z_i)}{q(Z_i)},\]then \(\widehat D\) is a finite-sample estimate of KL and can be negative by chance, even though its population expectation cannot be. In LLM and RL code, a logged “KL” is often a per-token log-ratio, a minibatch mean, or a clipped or otherwise approximate surrogate. Those quantities may be negative. A negative value is not a counterexample to Gibbs’ inequality; it means the logged quantity is not the exact full-distribution KL.
The order matters. In \(D_{\mathrm{KL}}(p\Vert q)\), data are averaged according to \(p\) while lengths come from \(q\). Reversing them describes a different coding experiment, so KL is generally asymmetric and is not a distance metric. If \(p(z)>0\) but \(q(z)=0\), the model gives infinite length to an event that can occur, and the forward KL is infinite.
1.4 使用错误编码的代价：KL Divergence
2. Information Theory in Supervised Learning
Nothing distributional disappears when we enter supervised learning. Section 1 used one generic source variable \(Z\sim p_Z\) on an outcome space \(\mathcal Z\). A supervised-data source instead emits a pair:
\[\boxed{(X,Y)\sim p_{XY}\quad\text{on}\quad\mathcal X\times\mathcal Y}.\]The uppercase letters name the two coordinates of a random pair; lowercase \(x,y\) denote values that were actually observed. Their joint distribution \(p_{XY}(x,y)\) determines everything that follows. For discrete variables it gives the marginals and conditionals
\[p_X(x)=\sum_y p_{XY}(x,y),\qquad p_Y(y)=\sum_x p_{XY}(x,y),\qquad p_{Y\mid X}(y\mid x)=\frac{p_{XY}(x,y)}{p_X(x)}\quad\text{for }p_X(x)>0.\]Thus \(X\) and \(Y\) do not replace distributions. They let us refer compactly to the joint distribution, its marginals, and the family of conditional label distributions indexed by \(x\). Once an input \(x\) is known, the true distribution over labels is \(p_{Y\mid X}(\cdot\mid x)\), while the model proposes another distribution \(q_\theta(\cdot\mid x)\) on the same label space. The coding interpretation treats \(X\) as information already available to both sides and \(Y\) as the outcome to describe.
2. 监督学习中的信息论
2.1 From Coding to Supervised Learning
Viewed this way, supervised learning does not introduce a different kind of cross-entropy. It takes the earlier one-outcome coding problem and adds side information: instead of using one unconditional code \(q(z)\), it selects an input-dependent code \(q_\theta(y\mid x)\) after observing \(x\).
First separate the machine-learning task from its coding interpretation. In supervised learning, the predictive model reads an input \(x\) and outputs a probability distribution \(q_\theta(\cdot\mid x)\) over possible labels. For example, after reading an image, a classifier might assign probability \(0.8\) to “cat” and \(0.2\) to “dog.” No literal message needs to be transmitted during training.
To interpret its loss as code length, imagine a separate communication experiment. An encoder sees the realized label \(y\) and turns it into bits using the code determined by \(q_\theta(\cdot\mid x)\). A decoder receives those bits and recovers the label. Both must already know \(x\); otherwise they could not agree on which input-dependent codebook to use. Here, \(x\) is side information, while \(y\) is the outcome being encoded. The ideal length of its code is therefore \(-\log_2q_\theta(y\mid x)\).
The predictor is thus the model that supplies the probabilities; the encoder and decoder are conceptual devices that reveal what those probabilities mean in bits. Both cases follow one rule:
\[\boxed{\text{cross-entropy}=\mathbb E[-\log_2 q(\text{outcome}\mid\text{available side information})]}.\]With no side information, the condition is empty and this reduces to \(\mathbb E[-\log_2q(Z)]\). With \(X\) known, it becomes \(\mathbb E[-\log_2q_\theta(Y\mid X)]\). Equivalently, the chain rule \(q(x,y)=q(x)q(y\mid x)\) gives
\[-\log_2q(x,y)=-\log_2q(x)-\log_2q(y\mid x).\]The first term encodes the input itself; the second encodes the label after the input is already known. A supervised loss normally charges only the second term because the task is to predict \(Y\) from the given \(X\).
Now let
- \(X\) be the input;
- \(Y\) be the label to predict;
- \(p(x,y)\) be the real joint distribution of input-label pairs;
- \(p(x)\) and \(p(y)\) be its two marginal distributions;
- \(p(y\mid x)\) be the true label distribution after input \(x\) is known;
- \(q_\theta(y\mid x)\) be the model’s predictive distribution.
Before inserting these objects into the loss, it helps to follow exactly what a classifier computes. For \(K\) classes, its final layer usually emits a vector
\[\mathbf z_\theta(x)=(z_1,\ldots,z_K)\in\mathbb R^K.\]Each \(z_k\) is a logit: an unrestricted, unnormalized score for class \(k\). A logit may be negative and the logits do not have to sum to one. Softmax turns them into the normalized predictive distribution
\[\underbrace{q_\theta(k\mid x)}_{\text{probability of class }k} =\operatorname{softmax}(\mathbf z)_k =\frac{e^{\overbrace{z_k}^{\text{logit}}}} {\sum_{j=1}^K e^{z_j}}.\]Taking the logarithm after this normalization gives
\[\underbrace{\log q_\theta(k\mid x)}_{\text{log-probability, not a logit}} =\underbrace{z_k}_{\text{class-}k\text{ logit}} -\underbrace{\log\sum_{j=1}^K e^{z_j}}_{\text{shared log-normalizer}}.\]The subscripts have different roles here. \(k\) is a free index: fix a class \(k\) and compute its log-probability. By contrast, \(j\) is a dummy summation index: inside \(\sum_j\) it successively takes the values \(1,\ldots,K\). The formula does not claim that \(z_k=z_j\). Written without the shorthand,
\[[\log\operatorname{softmax}(\mathbf z)]_k =z_k-\underbrace{\log\!\left(e^{z_1}+e^{z_2}+\cdots+e^{z_K}\right)}_{\operatorname{logsumexp}(\mathbf z)}.\]For example, when computing class \(k=2\), the first term is specifically \(z_2\), while the second term contains all logits, including \(z_2\). The first term is correct because the numerator of softmax is \(e^{z_k}\) and \(\log e^{z_k}=z_k\). The shared subtraction is exactly what normalizes the result:
\[\sum_{k=1}^K\exp\!\left(z_k-\operatorname{logsumexp}(\mathbf z)\right) =\frac{\sum_ke^{z_k}}{\sum_je^{z_j}}=1.\]Therefore, for the realized class \(y\), the usual framework-level per-example cross-entropy in nats is
\[\underbrace{\ell_{\mathrm{CE}}(x,y)}_{\text{one-example loss}} =\underbrace{-\log q_\theta(y\mid x)}_{\text{negative log-probability}} =\underbrace{-z_y}_{\text{reward a large true-class logit}} +\underbrace{\log\sum_{j=1}^K e^{z_j}}_{\text{compare it with all class logits}}.\]This is why software libraries normally ask CrossEntropyLoss to receive logits, even though the mathematical loss contains \(\log q_\theta\): the operation internally computes a numerically stable log-softmax and then selects the true class. The coding version uses base-two logarithms, so the same loss in bits is
The objects can now be kept separate:
| Symbol | What it is | Its role |
|---|---|---|
| \(z_k\) | logit | raw score produced by the model |
| \(q_\theta(k\mid x)\) | probability | softmax-normalized probability of class \(k\) |
| \(\log q_\theta(k\mid x)\) | log-probability | logarithm of that normalized probability |
| \(-\log q_\theta(y\mid x)\) | negative log-probability | loss/code length for one observed label \(y\) |
| \(L_{\mathrm{CE}}\) | cross-entropy loss | the preceding one-example quantity averaged under real data |
Fix one input \(x\). The situation is exactly the earlier coding problem, but now the outcome space is the set of labels. If label \(y\) occurs, the model pays
\[-\log_2q_\theta(y\mid x)\]bits. Averaging first over labels and then over inputs gives the population cross-entropy loss
\[\boxed{L_{\mathrm{CE}}=\mathbb E_{(X,Y)\sim p}[-\log_2q_\theta(Y\mid X)]}.\]With every part labeled, the same expression is
\[\underbrace{L_{\mathrm{CE}}}_{\text{population cross-entropy}} =\underbrace{\mathbb E_{(X,Y)\sim p}}_{\text{average according to real-data frequency}} \!\left[ \underbrace{-\log_2}_{\text{probability }\to\text{ bits}} \underbrace{q_\theta(Y\mid X)}_{\text{model probability of the label that occurred}} \right].\]What changes if we remove the logarithm? (Click to expand)
Strictly speaking, the logarithm is not an optional decoration on cross-entropy: it is part of its definition. But we can compare it with the seemingly natural probability loss
\[\ell_{\mathrm{prob}}(x,y)=1-q_\theta(y\mid x),\]where minimizing \(1-q_y\) is equivalent to maximizing the probability assigned to the observed class. At first this appears to have the same goal as minimizing \(-\log q_y\). Their gradients with respect to the probability already reveal a difference:
\[\frac{\partial(-\log q_y)}{\partial q_y}=-\frac1{q_y}, \qquad \frac{\partial(1-q_y)}{\partial q_y}=-1.\]The difference is clearest at the logits, which are the quantities actually changed by backpropagation. Let \(t_k=\mathbf 1\{y=k\}\) be the one-hot target. For natural-log cross-entropy,
\[\boxed{\frac{\partial\ell_{\mathrm{CE}}}{\partial z_k}=q_k-t_k}.\]For the no-log probability loss,
\[\boxed{\frac{\partial\ell_{\mathrm{prob}}}{\partial z_k} =q_y(q_k-t_k) =q_y\frac{\partial\ell_{\mathrm{CE}}}{\partial z_k}}.\]For one example the two gradients point in the same direction, but the no-log gradient is multiplied by the model’s probability \(q_y\) for the correct answer. This reverses the desirable emphasis. If the model is confidently wrong, say \(q_y=0.001\), the cross-entropy gradient on the true-class logit is approximately \(-0.999\), whereas the no-log gradient is approximately \(-0.000999\)—one thousand times smaller. The mistake that most needs correction supplies almost no learning signal. Cross-entropy instead becomes steep as \(q_y\to0\) and continues to push strongly against confident errors. Both gradients vanish as \(q_y\to1\), when the example is already solved.
This per-example rescaling also changes a minibatch update. Each example has a different \(q_y\), so the no-log loss suppresses hard examples before their gradients are summed and gives relatively more influence to examples the model already handles well. It can consequently learn slowly or stall after a poor initialization.
There is a deeper statistical difference when labels are genuinely uncertain. For a fixed \(x\), write \(p_k=p(Y=k\mid x)\) and let \(q\) range over all class distributions. The expected cross-entropy is
\[\mathbb E_p[-\log q_Y] =-\sum_kp_k\log q_k =H(p)+D_{\mathrm{KL}}(p\Vert q),\]so its unique optimum is \(q=p\). It learns the entire conditional distribution. The expected no-log loss is instead
\[\mathbb E_p[1-q_Y]=1-\sum_kp_kq_k.\]This expression is linear in \(q\), so it is minimized by placing all probability on a most likely class. For example, if \(p=(0.6,0.4)\), cross-entropy prefers \(q=(0.6,0.4)\), while the no-log loss prefers \(q=(1,0)\). The latter can recover the most likely class but not calibrated uncertainty. When the label is deterministic, both losses have the same limiting prediction \(q_y=1\), although their paths toward it still differ.
The logarithm is not the only possible way to learn calibrated probabilities. The Brier score, \(\sum_k(q_k-t_k)^2\), is another proper scoring rule and is also minimized in expectation at \(q=p\). What fails above is specifically the linear objective \(1-q_y\), not every loss without a logarithm.
There is a second possible meaning of “not taking the log.” Suppose we retain the likelihood of the entire dataset,
\[\mathcal L(\theta)=\prod_{i=1}^nq_\theta(y_i\mid x_i),\]and maximize this product directly instead of maximizing its logarithm. These two objectives do have the same optimizer, and where \(\mathcal L>0\) their gradients satisfy
\[\nabla_\theta\mathcal L =\mathcal L\,\nabla_\theta\log\mathcal L.\]Thus the full-batch gradient direction is the same but its scale is multiplied by the entire dataset likelihood. Because a product of many probabilities is exponentially small, this gradient rapidly vanishes and may underflow to exactly zero; it also changes dramatically with batch size. Taking the log converts the product into the stable additive objective \(\sum_i\log q_\theta(y_i\mid x_i)\). This is a numerical and optimization reason for the log, in addition to its coding and probability-estimation meanings.
Writing out both averages makes the roles explicit:
\[L_{\mathrm{CE}}=-\sum_xp(x)\sum_yp(y\mid x)\log_2q_\theta(y\mid x).\]For each fixed \(x\), cross-entropy compares the two distributions \(p(\cdot\mid x)\) and \(q_\theta(\cdot\mid x)\) on the same label space. It is therefore imprecise to say that cross-entropy is “between the random variables \(X\) and \(Y\).” It is between true and predicted conditional distributions, averaged over \(X\).
For one observed pair \((x,y)\), the stochastic loss is just the code length of the observed label:
\[L_{\mathrm{CE}}(x,y)=-\log_2q_\theta(y\mid x).\]If the model assigns probability \(0.8\) to the true class, the loss is \(-\log_2 0.8\approx0.322\) bits. Raising the probability of the observed answer shortens its code and lowers the loss.
This is also why cross-entropy and negative log-likelihood are the same training objective. With natural logarithms, the value is measured in nats rather than bits, but the minimizer is unchanged. For a language model, \(X\) is the token prefix, \(Y\) is the next token, and \(q_\theta(\cdot\mid X)\) is the next-token distribution.
2.1 从编码走向监督学习
2.2 How Good Can Prediction Be?
The notation now contains two random variables, but the object being measured is still a distribution. For every possible input value \(x\), the joint distribution supplies one label distribution \(p_{Y\mid X=x}\). The collection
\[\left\{p_{Y\mid X=x}:x\in\mathcal X\right\}\]is simply a family of distributions indexed by the observed input, and \(p_X(x)\) says how frequently each member of that family is used.
For a fixed input \(x\), suppose the model were perfect: \(q_\theta(\cdot\mid x)=p(\cdot\mid x)\). The average label-code length would then be the entropy of the true conditional distribution. Averaging this matched length over inputs defines conditional entropy:
\[\boxed{H(Y\mid X)=\mathbb E_{(X,Y)\sim p}[-\log_2p(Y\mid X)]}.\]Written explicitly as an average of distributional entropies,
\[\boxed{H(Y\mid X)=\sum_xp_X(x)\,H\!\left(p_{Y\mid X=x}\right)}.\]So conditional entropy does not measure a mysterious relation “between two letters.” It averages the entropy of the true label distribution at each input.
This looks almost identical to the earlier cross-entropy loss, but one symbol changes its meaning. Both use the same outer average because, by iterated expectation,
\[\mathbb E_{(X,Y)\sim p}[g(X,Y)] =\mathbb E_{X\sim p(x)}\mathbb E_{Y\sim p(y\mid X)}[g(X,Y)].\]What is averaged differs:
\[H(Y\mid X)=\mathbb E_p[-\log_2\underbrace{p(Y\mid X)}_{\text{true conditional distribution}}],\]whereas
\[L_{\mathrm{CE}}(q_\theta)=\mathbb E_p[-\log_2\underbrace{q_\theta(Y\mid X)}_{\text{model conditional distribution}}].\]They are equal only under the perfect-model assumption \(q_\theta(\cdot\mid x)=p(\cdot\mid x)\) for \(p(x)\)-almost every input. The paragraph began with that assumption; without it, cross-entropy is larger by the expected KL term derived below.
It measures the label uncertainty that remains after the input is known. The word “remains” matters. Before seeing \(X\), the best context-free code for \(Y\) costs \(H(Y)\) bits on average. After seeing \(X\), the best input-dependent code costs only \(H(Y\mid X)\).
We can now decompose the supervised loss using the same matched-versus-mismatched argument as before. For every \(x\),
\[H\!\left(p(\cdot\mid x),q_\theta(\cdot\mid x)\right) =H\!\left(p(\cdot\mid x)\right) +D_{\mathrm{KL}}\!\left(p(\cdot\mid x)\Vert q_\theta(\cdot\mid x)\right).\]Averaging over \(X\) gives
\[\boxed{L_{\mathrm{CE}}=H(Y\mid X)+\mathbb E_X\!\left[D_{\mathrm{KL}}\!\left(p(\cdot\mid X)\Vert q_\theta(\cdot\mid X)\right)\right]}.\]The two terms answer different questions:
- \(H(Y\mid X)\) is ambiguity inherent in the prediction problem given the available input;
- the expected KL is extra loss caused by the model not matching the true conditional distribution.
If labels are deterministic given inputs, then \(H(Y\mid X)=0\). If labels are noisy or genuinely ambiguous, even a perfect model cannot drive the population loss below \(H(Y\mid X)\).
2.2.1 The Same Pattern in Mean Squared Error (Click to expand)
Regression has an exact parallel. Let
\[m(x)=\mathbb E[Y\mid X=x]\]be the true conditional mean, and let \(\mu_\theta(x)\) be the model’s prediction. Add and subtract \(m(X)\) inside the error:
\[Y-\mu_\theta(X)=\underbrace{Y-m(X)}_{\text{unpredictable residual}}+\underbrace{m(X)-\mu_\theta(X)}_{\text{model mismatch}}.\]After squaring and averaging, the cross term vanishes because \(\mathbb E[Y-m(X)\mid X]=0\). Thus
\[\boxed{ \mathbb E[(Y-\mu_\theta(X))^2] =\underbrace{\mathbb E[\operatorname{Var}(Y\mid X)]}_{\text{irreducible conditional variation}} +\underbrace{\mathbb E[(m(X)-\mu_\theta(X))^2]}_{\text{model error}}. }\]This has the same logic as
\[L_{\mathrm{CE}} =\underbrace{H(Y\mid X)}_{\text{irreducible conditional uncertainty}} +\underbrace{\mathbb E_X[D_{\mathrm{KL}}(p(\cdot\mid X)\Vert q_\theta(\cdot\mid X))]}_{\text{model error}}.\]MSE asks the model to match the conditional mean; cross-entropy asks it to match the entire conditional distribution. The best MSE predictor is \(m(x)\), and its minimum population MSE is \(\mathbb E[\operatorname{Var}(Y\mid X)]\). “Irreducible” always means relative to the available input \(X\): adding informative features can reduce both \(\operatorname{Var}(Y\mid X)\) and \(H(Y\mid X)\).
If the fitted predictor \(\widehat\mu_D\) also varies with the random training set \(D\), its model-error term can be split once more. Writing \(\bar\mu(x)=\mathbb E_D[\widehat\mu_D(x)]\) gives the familiar bias–variance decomposition:
\[\mathbb E_D\mathbb E_{X,Y}[(Y-\widehat\mu_D(X))^2] =\underbrace{\mathbb E_X[\operatorname{Var}(Y\mid X)]}_{\text{data noise}} +\underbrace{\mathbb E_X[(m(X)-\bar\mu(X))^2]}_{\text{squared bias}} +\underbrace{\mathbb E_X[\operatorname{Var}_D(\widehat\mu_D(X))]}_{\text{estimator variance}}.\]The first term remains even with the optimal learning procedure; the latter two arise from how the model class and finite training data produce a fitted predictor. This is a further decomposition of the MSE model term, not a different source of label noise.
There is also a direct likelihood connection. If the model assumes
\[q_\theta(y\mid x)=\mathcal N(\mu_\theta(x),\sigma^2)\]with a fixed variance, then—remembering that this article uses base-two logarithms—
\[-\log_2 q_\theta(y\mid x) =\frac12\log_2(2\pi\sigma^2) +\frac{(y-\mu_\theta(x))^2}{2\sigma^2\ln 2}.\]Minimizing Gaussian cross-entropy, or negative log-likelihood, is therefore exactly equivalent to minimizing MSE. If the variance is also learned, the loss additionally charges a \(\log\sigma^2\) term, so predicting uncertainty matters as well as predicting the mean.
Finally, suppose we ask not how good a model is, but how useful the input itself is. Without \(X\), the optimal label code costs \(H(Y)\). With \(X\), it costs \(H(Y\mid X)\). The expected saving is the mutual information:
\[\boxed{I(X;Y)=H(Y)-H(Y\mid X)}.\]To see where the distributions in this expression come from, return to the joint distribution \(p_{XY}\). For discrete \(X\) and \(Y\), it is a two-dimensional table: one axis lists values of \(X\), the other lists values of \(Y\), and each cell contains \(p_{XY}(x,y)\). The figure below turns each cell into a column whose height is its probability mass.
Every distribution used by mutual information is extracted from this same joint table:
- Ignore the input: for a fixed label \(y\), add the columns over every possible input, \(p_Y(y)=\sum_x p_{XY}(x,y).\) This marginal distribution describes labels before we are told which \(x\) occurred.
- Reveal one input: fix \(X=x\) and retain only that slice of the table. Its total mass is \(p_X(x)\), not one, so divide every column in the slice by \(p_X(x)\): \(p_{Y\mid X}(y\mid x)=\frac{p_{XY}(x,y)}{p_X(x)}.\) This normalized slice describes labels after we know that particular input.
Mutual information therefore remains entirely distributional. For each input value, it compares the normalized slice \(p_{Y\mid X=x}\) with the common marginal \(p_Y\). It then averages that comparison using the frequency \(p_X(x)\) with which each slice occurs:
\[\boxed{I(X;Y) =\mathbb E_{X\sim p_X}\!\left[ D_{\mathrm{KL}}\!\left(p_{Y\mid X}(\cdot\mid X)\Vert p_Y\right) \right]}.\]Thus mutual information uses forward KL to measure how much, on average, observing \(X\) changes the label distribution from its prior marginal \(p_Y\)—equivalently, how many bits about \(Y\) the input supplies. Expanding this average and substituting \(p(y\mid x)=p(x,y)/p(x)\) gives
\[\begin{aligned} I(X;Y) &=\mathbb E_{p(x,y)}\!\left[\log_2\frac{p(y\mid x)}{p(y)}\right]\\ &=\mathbb E_{p(x,y)}\!\left[\log_2\frac{p(x,y)}{p(x)p(y)}\right]\\ &=D_{\mathrm{KL}}\!\left(p(X,Y)\Vert p(X)p(Y)\right). \end{aligned}\]If \(X\) and \(Y\) are independent, then \(p(x,y)=p(x)p(y)\) and this KL is zero.
This separates three questions that are easy to conflate: cross-entropy evaluates a predictive distribution, conditional entropy measures irreducible uncertainty after seeing the input, and mutual information measures how much uncertainty the input removes.
| Quantity | Definition | Coding interpretation |
|---|---|---|
| Self-information | \(-\log_2p(z)\) | ideal bits for one outcome \(z\) |
| Entropy | \(\mathbb E_p[-\log_2p(Z)]\) | asymptotically optimal bits per symbol under the true source |
| Cross-entropy | \(\mathbb E_p[-\log_2q(Z)]\) | expected bits using the model’s code |
| KL divergence | \(\mathbb E_p[\log_2 p(Z)/q(Z)]\) | excess expected bits due to mismatch |
| Conditional entropy | \(\mathbb E_p[-\log_2p(Y\mid X)]\) | uncertainty in \(Y\) remaining after observing \(X\) |
| Mutual information | \(H(Y)-H(Y\mid X)\) | uncertainty about \(Y\) removed by observing \(X\) |
To close the discussion, consider a numerical check that puts entropy, cross-entropy, and KL on the same scale. Let the true binary source be \(p=(0.75,0.25)\), while the model assumes \(q=(0.5,0.5)\). The model considers both outcomes equally likely, so it assigns each one the ideal length
\[-\log_2 0.5=1\ \text{bit}.\]No matter which outcome occurs, one bit is paid. Its average is therefore
\[H(p,q)=0.75(1)+0.25(1)=1.\]The matched code instead uses the true probabilities. Its ideal lengths are
\[-\log_2 0.75\approx0.415,qquad -\log_2 0.25=2,\]so the shorter length is paid 75% of the time and the longer one only 25% of the time:
\[H(p)=0.75(0.415)+0.25(2)\approx0.811\ \text{bits}.\]The difference is precisely
\[D_{\mathrm{KL}}(p\Vert q)=H(p,q)-H(p)=1-0.811\approx0.189\ \text{bits}.\]The uniform model is not “wrong” because its code is undecodable; its one-bit code is perfectly valid. It is inefficient because it ignores the three-to-one frequency imbalance and pays about \(0.189\) unnecessary bits per outcome in the long-run limit.
2.3 Three Machine-Learning Consequences
With the coding meanings in place, three machine-learning consequences are now direct.
1. Maximum likelihood and minimum cross-entropy are the same optimization. Suppose the supervised dataset is
\[D=\{(x_i,y_i)\}_{i=1}^n,\]and, conditional on the inputs, the labels are modeled independently. The conditional likelihood is the probability that the model assigns to all observed labels:
\[\mathcal L(\theta;D)=\prod_{i=1}^n q_\theta(y_i\mid x_i).\]Products are awkward to optimize and can underflow numerically, so take a logarithm. Because the logarithm is strictly increasing, it does not change which \(\theta\) is best:
\[\arg\max_\theta\mathcal L(\theta;D) =\arg\max_\theta\sum_{i=1}^n\log q_\theta(y_i\mid x_i).\]Negating converts maximization to minimization, and dividing by the constant \(n\) does not change the optimizer:
\[\arg\max_\theta\mathcal L(\theta;D) =\arg\min_\theta\left[-\frac1n\sum_{i=1}^n\log q_\theta(y_i\mid x_i)\right].\]The expression in brackets is empirical cross-entropy, also called negative log-likelihood. In one-hot classification, this follows explicitly because
\[-\sum_{k=1}^K\mathbf 1\{y_i=k\}\log q_\theta(k\mid x_i) =-\log q_\theta(y_i\mid x_i);\]only the observed class survives the sum. The coding interpretation says the same thing another way:
\[-\log_2\prod_iq_\theta(y_i\mid x_i) =\sum_i-\log_2q_\theta(y_i\mid x_i).\]Thus the maximum-likelihood model assigns the greatest probability to the observed label sequence; equivalently, it gives that sequence the shortest total ideal code. “The same optimization” does not mean the raw likelihood and cross-entropy have the same numerical value—they differ by a logarithm, a minus sign, and often the factor \(1/n\)—only that they select the same \(\theta\).
2. Minimizing population cross-entropy minimizes forward KL. The conditional decomposition derived above is
\[L_{\mathrm{CE}}(\theta) =H(Y\mid X) +\mathbb E_X\!\left[D_{\mathrm{KL}}\!\left(p(\cdot\mid X)\Vert q_\theta(\cdot\mid X)\right)\right].\]Once the data-generating distribution \(p\) and the available input \(X\) are fixed, \(H(Y\mid X)\) is a constant: changing \(\theta\) cannot remove ambiguity inherent in the task. Therefore
\[\arg\min_\theta L_{\mathrm{CE}}(\theta) =\arg\min_\theta\mathbb E_X\!\left[D_{\mathrm{KL}}\!\left(p(\cdot\mid X)\Vert q_\theta(\cdot\mid X)\right)\right].\]If the model family contains the true conditional distribution and optimization succeeds, the KL term can reach zero and \(q_\theta(\cdot\mid x)=p(\cdot\mid x)\) almost everywhere. If the family is restricted, training instead finds its best approximation to \(p\) and a positive mismatch remains. It is forward KL because outcomes are averaged according to the data distribution \(p\). Consequently, an outcome with \(p(y\mid x)>0\) but very small \(q_\theta(y\mid x)\) incurs a large penalty: the model has assigned a very long code to something that really occurs.
In practice, training minimizes empirical cross-entropy on a finite sample, not the inaccessible population expectation. A sufficiently flexible model can lower training loss by memorization, so held-out cross-entropy is needed to estimate whether the expected KL on new data has actually fallen. From the coding viewpoint, training can remove mismatch bits; it cannot reduce the intrinsic \(H(Y\mid X)\) without changing what information is supplied in \(X\).
3. Perplexity is exponentiated cross-entropy. For observed conditional probabilities \(q_i=q_\theta(y_i\mid x_i)\), the average base-two cross-entropy is
\[\widehat H=-\frac1n\sum_{i=1}^n\log_2q_i.\]Exponentiating gives
\[\boxed{\operatorname{PPL}=2^{\widehat H} =\left(\prod_{i=1}^nq_i\right)^{-1/n}}.\]Thus perplexity is the inverse geometric mean probability assigned to the observed outcomes. Its “effective branching factor” interpretation comes from a uniform example: if every step had \(K\) equally likely choices, then each observed outcome would have probability \(1/K\), the cross-entropy would be \(\log_2K\) bits, and perplexity would be exactly \(K\). A model with average loss \(3\) bits per token therefore has the same average code length as an idealized uniform choice among \(2^3=8\) alternatives. This does not mean that exactly eight tokens are plausible at every position; it is an equivalent average scale.
Lower perplexity means shorter average token codes on the same evaluation distribution. Comparisons require the same dataset, tokenization, and conditioning setup: changing the tokenizer changes what counts as one symbol, so perplexities from different vocabularies are not automatically comparable. With natural-log loss, the equivalent formula is \(\operatorname{PPL}=\exp(\text{average NLL})\).
Is training by cross-entropy the same as finding the largest compression ratio? Almost, if the comparison uses a fixed uncompressed representation. Minimizing cross-entropy adjusts \(q_\theta\) so that outcomes common under \(p\) receive shorter codes; because the original number of bits is fixed, a shorter expected encoded length means a larger compression ratio. The population optimum is \(q_\theta=p\), where the expected length reaches \(H(p)\) and the KL mismatch cost vanishes. In supervised learning, the corresponding statement is narrower: minimizing conditional cross-entropy seeks the shortest label code given \(X\), whose irreducible limit is \(H(Y\mid X)\)—it does not compress the input \(X\) itself.
Continuous variables need care. Differential entropy can be negative and changes under a change of coordinates. KL divergence remains invariant under smooth reparameterization, but it is no longer literally a raw finite-bit code length without specifying quantization or a reference measure.
2.2 预测最多能做到多好？
2.3 三个机器学习结论
3. Information Theory in Unsupervised Learning
This section has one destination:
\[\boxed{K(X,Y)=K(X)+K(Y\mid X)+O(\log n)}.\]We want to understand every symbol in this formula and then use it to answer a learning question: if \(X\) is an unlabeled dataset and \(Y\) is a downstream task, in what precise sense can structure in \(X\) help describe \(Y\)?
The route is different from Sections 1 and 2. There, uppercase letters denoted random variables and quantities such as entropy were averages over a distribution. Here, \(X\) and \(Y\) will denote two particular finite objects that have already been observed—for example, two finite datasets stored as bit strings. We therefore need a notion of information for an individual object rather than an average over possible outcomes.
3.1 How Much Information Is in One Fixed Object?
Consider two files of the same length:
- \(s_1\) contains one billion zeros;
- \(s_2\) is a billion-bit string with no exploitable pattern.
If we place the uniform distribution over all billion-bit strings, both have probability \(2^{-10^9}\) and surprisal \(10^9\) bits. Shannon information is answering a question asked before the draw: under the chosen distribution, how surprising is the outcome? It does not by itself express that, after seeing the files, the first admits the short instruction “print zero one billion times,” while the second may require listing nearly every bit.
For a fixed object, we instead ask:
What is the shortest exact, reproducible description that generates this object?
To make “description” and “length” unambiguous, we agree on a binary computer \(U\). A description is a finite binary program \(r\). The machine reads \(r\), produces an output, and must then halt: after finitely many steps, it enters a stop state. Requiring the program to output exactly \(s\) and halt tells us when the finite output is complete; a computation that prints \(s\) and then continues printing has not reproduced exactly \(s\).
There is a second boundary to settle: how does the machine know where one program ends? We use a prefix-free program language, in which no complete valid program is the prefix of another. For example,
\[\{0,10,110,111\}\]is prefix-free, whereas \(\{0,01,10\}\) is not. Prefix-free programs are also called self-delimiting: their ends can be recognized from the incoming bits without sending a separate fixed-width length field. This becomes essential when we later place a description of \(X\) next to a description of \(Y\). As in Section 1, their lengths satisfy Kraft’s inequality,
\[\sum_{r:\,U(r)\ \mathrm{halts}}2^{-\lvert r\rvert}\le 1.\]Finally, we choose \(U\) to be universal: it can simulate any other programmable machine after receiving a fixed interpreter for that machine. We must fix \(U\) before measuring length, just as ordinary coding requires a shared decoder.
The prefix Kolmogorov complexity of a finite string \(s\) is then
\[\boxed{K_U(s)=\min_{r:\,U(r)\downarrow=s}\lvert r\rvert}.\]The notation \(U(r)\downarrow=s\) says that \(U\) runs program \(r\), outputs exactly \(s\), and halts; \(\lvert r\rvert\) is the program length in bits. Once the reference machine is understood, we write \(K(s)\).
Several properties are useful for interpreting this definition.
A literal description is always available. A program can contain a self-delimiting description of the length of \(s\) followed by the bits of \(s\) themselves, so
\[K(s)\le \lvert s\rvert+O(\log\lvert s\rvert).\]Thus complexity is never much larger than an explicitly delimited copy. A patterned string can be far shorter: the loop and the integer needed to generate a billion zeros occupy vastly fewer than a billion bits.
Most long strings are not substantially compressible. There are \(2^m\) strings of length \(m\) but fewer than \(2^{m-c}\) programs shorter than \(m-c\) bits. Because one deterministic halting program produces only one final output, fewer than a fraction \(2^{-c}\) of the length-\(m\) strings can be compressed by more than \(c\) bits. Short descriptions reveal special structure; they are not available for every string.
The choice of universal machine contributes only a fixed constant. If \(U_1\) and \(U_2\) are universal, either can simulate the other using a fixed interpreter. Therefore
\[\lvert K_{U_1}(s)-K_{U_2}(s)\rvert\le c,\]where \(c\) depends on the two machines but not on \(s\). Exact values for small objects depend on the language, but the discrepancy does not grow with the dataset.
Exact Kolmogorov complexity is not computable in general. We can run candidate programs and eventually observe the ones that halt, but a program still running today may halt tomorrow or may run forever. No algorithm can decide this for all programs—the halting problem. Consequently a real compressor can demonstrate an upper bound by producing a description, but it cannot generally certify that the description is the shortest possible. This limitation will matter when we interpret the word “guarantee.”
3.2 What Changes When Another Object Is Already Known?
Suppose Alice and Bob already possess the same fixed object \(X\). Alice now needs to describe another fixed object \(Y\). A program may use \(X\) as an auxiliary input, and the bits of \(X\) are not charged again. This gives conditional Kolmogorov complexity:
\[\boxed{K_U(Y\mid X)=\min_{r:\,U(r,X)\downarrow=Y}\lvert r\rvert}.\]The vertical bar means “with this particular \(X\) already available,” not conditioning on a random event. The quantity asks how many additional program bits are needed to reconstruct this particular \(Y\).
Three cases establish the intuition.
- The program can ignore \(X\), so \(K(Y\mid X)\le K(Y)+O(1)\). Side information cannot make the best description substantially worse.
- If one fixed short procedure \(f\) computes \(Y=f(X)\), then a program only needs to say “run \(f\),” and \(K(Y\mid X)\le K(f)+O(1)\). When \(f\) is fixed independently of the data size, this is written \(K(Y\mid X)=O(1)\).
- Merely possessing a large \(X\) does not guarantee a saving. If none of its structure helps generate \(Y\), then \(K(Y\mid X)\approx K(Y)\).
We also need a way to treat both objects as one output. Let \(K(X,Y)\) be the shortest program length for producing an unambiguously encoded ordered pair \((X,Y)\). It is not the complexity of a raw concatenation with an unknown boundary: the pair representation lets the decoder recover where \(X\) ends and \(Y\) begins. Let
\[n=\lvert X\rvert+\lvert Y\rvert\]denote the total raw size. We now have the three terms in the target formula:
| Term | Question |
|---|---|
| \(K(X)\) | How many bits describe \(X\) alone? |
| \(K(Y\mid X)\) | After \(X\) is known, how many additional bits describe \(Y\)? |
| \(K(X,Y)\) | How many bits describe the pair jointly? |
3.3 Why Does the Joint Description Split?
There is a useful precedent in Shannon information. For random variables with joint distribution \(p(x,y)\), define joint entropy by
\[H(X,Y)=\mathbb E_{(X,Y)\sim p}[-\log_2p(X,Y)].\]The probability factorization \(p(x,y)=p(x)p(y\mid x)\) implies
\[-\log_2p(x,y)=-\log_2p(x)-\log_2p(y\mid x).\]Averaging gives the exact Shannon chain rule
\[H(X,Y)=H(X)+H(Y\mid X).\]Its coding meaning is “describe the random outcome of \(X\), then describe the random outcome of \(Y\) using \(X\).” The Kolmogorov formula asks the analogous question for two fixed objects, but its justification must use programs rather than probabilities.
Start with the easy direction. Take a shortest self-delimiting program for \(X\). After it halts and reconstructs \(X\), run a shortest conditional program for \(Y\) with that reconstructed \(X\) as input. A fixed wrapper combines the two programs and outputs the ordered pair. This constructs a joint description whose length is essentially
\[K(X)+K(Y\mid X).\]Therefore the best joint program cannot be longer than this two-stage construction, apart from bounded bookkeeping.
The reverse direction is subtler. A shortest joint program may mix the shared structure of \(X\) and \(Y\) rather than visibly containing an “\(X\) part” followed by a “\(Y\) part.” The symmetry-of-information theorem says that this mixing cannot create an arbitrarily large hidden saving: the joint description can be reorganized into a description of \(X\) plus what is still needed for \(Y\) once \(X\) is known, with only logarithmic overhead.
The sharp prefix-complexity statement is
\[K(X,Y)=K(X)+K(Y\mid X,K(X))+O(1).\]Why is \(K(X)\) supplied to the second program here? Knowing the exact length of the optimal first description removes ambiguity about how the two optimal descriptions are coordinated. In the simpler formula we do not provide that integer. Since \(K(X)\) is at most on the order of \(n\), a self-delimiting description of its value costs at most \(O(\log n)\) bits. Removing it from the condition therefore yields
\[\boxed{K(X,Y)=K(X)+K(Y\mid X)+O(\log n)}.\]The \(O(\log n)\) term is controlled boundary and complexity bookkeeping. It is not uncertainty in the data and does not grow proportionally with dataset size.
The formula now has a direct two-slip interpretation:
- the first slip reconstructs \(X\) and costs \(K(X)\) bits;
- with \(X\) available, the second slip supplies only what is missing to reconstruct \(Y\) and costs \(K(Y\mid X)\) bits;
- a logarithmic number of bits coordinates the two descriptions.
Two limiting cases are worth retaining.
- If \(Y\) is computable from \(X\) by a fixed short rule, then \(K(Y\mid X)=O(1)\) and describing the pair costs little more than describing \(X\).
- If \(X\) provides no useful structure for describing \(Y\), then \(K(Y\mid X)\approx K(Y)\) and the pair costs approximately the sum of the separate descriptions.
This suggests a useful individual-object analogue of mutual information:
\[\boxed{I_K(X:Y)=K(Y)-K(Y\mid X)}.\]It counts the description bits saved on \(Y\) by already knowing \(X\). Using the chain rule,
\[I_K(X:Y)=K(X)+K(Y)-K(X,Y)+O(\log n),\]so the saving is symmetric between \(X\) and \(Y\) up to logarithmic bookkeeping.
3.4 What Does This Guarantee for Unsupervised Learning?
Now assign the fixed objects concrete learning roles:
- \(X\) is the entire unlabeled training corpus or dataset, not one random input example;
- \(Y\) is the finite data needed to specify performance on a downstream task—for example, its labels or task-specific continuation data.
First imagine describing \(Y\) without using \(X\). The ideal cost is \(K(Y)\). If \(X\) has already been described, the additional ideal cost of appending \(Y\) to the joint description is
\[K(X,Y)-K(X).\]The chain rule identifies this incremental cost:
\[\boxed{K(X,Y)-K(X)=K(Y\mid X)+O(\log n)}.\]This is the central step. It says that an optimal joint description pays for \(X\) once and then pays only for the information in \(Y\) that cannot already be reconstructed from \(X\). The saving relative to describing \(Y\) alone is
\[\begin{aligned} K(Y)-[K(X,Y)-K(X)] &=K(Y)-K(Y\mid X)+O(\log n)\\ &=I_K(X:Y)+O(\log n). \end{aligned}\]So “useful unlabeled data” has a precise ideal meaning: \(X\) is useful for the task exactly to the extent that it shortens the best description of \(Y\).
The stronger guarantee comes from comparing this ideal description with any concrete computable learner. Suppose a learning-and-coding procedure \(A\) receives \(X\) and emits a self-delimiting residual code for \(Y\) of length \(L_A(Y\mid X)\). A universal machine can reproduce \(Y\) from \(X\) by receiving:
- a description of the procedure \(A\), costing \(K(A)\) bits;
- the residual bits produced by \(A\), costing \(L_A(Y\mid X)\) bits;
- a fixed interpreter, absorbed into \(O(1)\).
Therefore
\[K(Y\mid X)\le K(A)+L_A(Y\mid X)+O(1).\]Combining this with the chain rule gives the regret-style guarantee
\[\boxed{K(X,Y)-K(X) \le K(A)+L_A(Y\mid X)+O(\log n)}.\]Read it carefully: if any computable procedure can exploit patterns in the unlabeled data to describe the downstream data compactly, the universal joint description can simulate that procedure and do at least as well, apart from the one-time description of the procedure and logarithmic bookkeeping. If \(A\) is fixed while datasets grow, \(K(A)\) is a fixed cost rather than a cost per example.
This argument is the compression view discussed in Ilya Sutskever: An Observation on Generalization. It gives two honest limiting cases:
- If \(K(Y\mid X)\ll K(Y)\), then this particular unlabeled dataset contains substantial reusable algorithmic structure for this task.
- If \(K(Y\mid X)\approx K(Y)\), then the dataset supplies almost no such structure; the theorem cannot manufacture a learning benefit.
Probabilistic modeling is the computable analogy. Any joint model factors as
\[q_\theta(X,Y)=q_\theta(X)q_\theta(Y\mid X),\]and therefore its ideal code length splits as
\[-\log_2q_\theta(X,Y) =-\log_2q_\theta(X)-\log_2q_\theta(Y\mid X).\]A shared model can reuse patterns learned while describing \(X\) to shorten its description of \(Y\). This motivates unsupervised learning through compression. But the probability identity alone does not prove that minimizing \(-\log q_\theta(X)\) in a restricted neural model will reduce \(-\log q_\theta(Y\mid X)\): the architecture, objective, optimization, finite sample, and way the representation is accessed all matter.
The word guarantee therefore refers to an ideal benchmark, not to every practical training run. Kolmogorov complexity is uncomputable; the theorem says that the ideal universal description can match every computable competitor up to description overhead. A neural network and its optimizer search only a small, computable part of program space. They may approximate the compression principle, but the chain rule does not promise that they reach its optimum or that useful information exists in \(X\).
3. 无监督学习中的信息论
References
- Cover, T. M. & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley. Chapters 2, 5, and 14.
- MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Chapters 2, 4, and 5.
- Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27, 379–423 and 623–656.
- Li, M. & Vitányi, P. (2019). An Introduction to Kolmogorov Complexity and Its Applications (4th ed.). Springer. Chapters 1–2 for foundations, Chapter 4 for the connection with Shannon information, and Chapter 8 for applications.
- Online introductions: Scholarpedia — Algorithmic Complexity and Gregory Chaitin’s publications.