Cheat sheet

Information theory

10 formulas · Back to the formula library

  1. Channel capacity

    C=max⁡p(x)I(X;Y)C = \max_{p(x)} I(X; Y)

    The highest rate at which information can cross a noisy channel with errors driven arbitrarily low. Shannon's result is that below this rate reliable communication is possible and above it is not — with no gentle slope in between.

    Symbols

    CC
    The capacity, in bits per channel use.
    I(X;Y)I(X; Y)
    The mutual information between input and output.
    max⁡p(x)\max_{p(x)}
    Maximised over every way of choosing inputs.
  2. Conditional entropy

    H(Y∣X)=H(X,Y)−H(X)H(Y \mid X) = H(X, Y) - H(X)

    How much uncertainty is left in Y once you already know X. It reaches zero when X determines Y outright, and stays at the full entropy of Y when X tells you nothing about it.

    Symbols

    H(X,Y)H(X, Y)
    The joint entropy of both variables.
    H(X)H(X)
    The entropy of X alone.
  3. Cross-entropy

    H(P,Q)=−∑xP(x)log⁡Q(x)H(P, Q) = -\sum_{x} P(x) \log Q(x)

    The average number of bits needed to encode data from P using a code optimised for Q. It splits into the entropy of P plus the divergence from P to Q, which is why minimising it over a model is the same as minimising that divergence.

    Symbols

    PP
    The true distribution, usually a one-hot label in practice.
    QQ
    The predicted distribution the model outputs.
  4. Jensen–Shannon divergence

    JSD(P∥Q)=12DKL(P∥M)+12DKL(Q∥M)\mathrm{JSD}(P \parallel Q) = \tfrac{1}{2} D_{\mathrm{KL}}(P \parallel M) + \tfrac{1}{2} D_{\mathrm{KL}}(Q \parallel M)

    A symmetric, always-finite cousin of the KL divergence, built by comparing both distributions against their average. Its square root is a true distance, which KL divergence never is.

    Symbols

    MM
    The mixture, equal to half of P plus half of Q.
    PP
    The first distribution.
    QQ
    The second distribution.
  5. Joint entropy

    H(X,Y)=−∑x,yp(x,y)log⁡p(x,y)H(X, Y) = -\sum_{x, y} p(x, y) \log p(x, y)

    The total uncertainty in two variables considered together. It is never more than the sum of the separate entropies, and the shortfall is exactly how much the two share.

    Symbols

    p(x,y)p(x, y)
    The joint probability of both outcomes.
    XX
    The first random variable.
    YY
    The second random variable.
  6. Kullback–Leibler divergence

    DKL(P∥Q)=∑xP(x)log⁡P(x)Q(x)D_{\mathrm{KL}}(P \parallel Q) = \sum_{x} P(x) \log \frac{P(x)}{Q(x)}

    The extra bits you pay, on average, when you encode samples drawn from P using a code built for Q. It is zero only when the two distributions agree everywhere, and it is not symmetric — swapping P and Q gives a different number.

    Symbols

    PP
    The true distribution — the one the data actually comes from.
    QQ
    The approximating distribution — the model, or the code you built.
  7. Mutual information

    I(X;Y)=∑x,yp(x,y)log⁡p(x,y)p(x) p(y)I(X; Y) = \sum_{x, y} p(x, y) \log \frac{p(x, y)}{p(x)\, p(y)}

    How many bits knowing one variable saves you on the other. Unlike correlation it catches any kind of dependence, not just linear ones, and it is symmetric in its two arguments.

    Symbols

    p(x,y)p(x, y)
    The joint distribution.
    p(x)p(y)p(x)p(y)
    What the joint would be if the two were independent.
  8. Perplexity

    PPL=exp⁡ ⁣(−1N∑i=1Nlog⁡p(xi∣x<i))\mathrm{PPL} = \exp\!\left(-\frac{1}{N} \sum_{i=1}^{N} \log p(x_i \mid x_{<i})\right)

    The exponential of average cross-entropy, read as an effective number of choices. A perplexity of 20 means the model is about as uncertain as if it were picking uniformly among 20 tokens at every step.

    Symbols

    NN
    The number of tokens scored.
    p(xi∣x<i)p(x_i \mid x_{<i})
    The probability the model gave the true next token.
    exp⁡\exp
    Converts average log-loss back into a count of choices.
  9. Self-information

    I(x)=−log⁡p(x)I(x) = -\log p(x)

    The surprise of one particular outcome. A certain event carries none; a one-in-a- million event carries about twenty bits. Entropy is just this quantity averaged over every outcome.

    Symbols

    xx
    A single outcome.
    p(x)p(x)
    Its probability.
  10. Shannon entropy

    H(X)=−∑xp(x)log⁡p(x)H(X) = -\sum_{x} p(x) \log p(x)

    The average surprise in a random variable, and the floor on how few bits any lossless code can spend on it. A fair coin costs one bit; a coin that always lands heads costs nothing to describe.

    Symbols

    XX
    The random variable being measured.
    pp
    Its probability mass function.
    log⁡\log
    Base two for bits, base e for nats.
Esc
↑↓ navigate↵ open? shortcuts

Keyboard shortcuts

Press Esc to close

Anywhere

⌘K
Search and commands
/
Search
?
This sheet
Esc
Close

Reading a lesson

J
Next lesson
K
Previous lesson
B
Bookmark