Probability and Information Theory for Machine Learning from Scratch

01A prediction is a distribution

A random variable takes values with probabilities. For a discrete variable, a probability mass function lists the probability of each value, and those probabilities sum to one. For a continuous variable, a density plays the same role with integrals in place of sums.^[1] A classifier's softmax output is a mass function over classes; a regression model with Gaussian noise outputs a density.

Two rules generate the rest. The sum rule recovers a marginal from a joint; the product rule factors a joint into a conditional times a marginal. Applying the product rule both ways and dividing gives Bayes' theorem.^[1]

The denominator comes from the sum rule and makes the posterior over all hypotheses sum to one. Prior, likelihood, posterior are roles, not kinds of number: all three are probabilities.

The classic case is a test for a rare condition. A 90% sensitive test with a 5% false-positive rate, applied to a population where 1% have the condition, gives a positive result that is more often a false alarm than a true detection. The posterior is small because the prior is small; the test's accuracy does not change that arithmetic.

02Expectation and the cost of estimating it

The expectation of f under a distribution is its average value weighted by probability. Loss functions are expectations: a model's training loss is the average loss over the data distribution, approximated by the average over the samples at hand.^[1]

The approximation is a Monte Carlo estimate. Its error does not vanish with a better formula; it shrinks with the number of samples, and slowly.^[1]

The variance of a sample mean of n independent draws is σ²/n, so the typical error, the standard error, is σ/√n.^[5] Four times the samples halve the error. The same rate explains why a validation set of 100 examples cannot resolve a 1% accuracy difference (the standard error of an accuracy near 80% is about 4 points there) and why a minibatch gradient is noisy.

03Maximum likelihood

A model with parameters θ assigns a probability to the data. Read as a function of θ with the data fixed, that probability is the likelihood, and the maximum likelihood estimate is the θ that makes the observed data most probable.^[4] For 9 heads in 13 independent flips the likelihood is θ⁹(1 − θ)⁴, and its maximum is at θ = 9/13, the fraction anyone would have guessed.

Products of thousands of probabilities underflow double precision: (1/2)¹¹⁰⁰ is already below the smallest positive double, about 4.9 × 10⁻³²⁴. Taking the logarithm turns the product into a sum that fits comfortably, and because the logarithm is increasing, the maximum of L and the minimum of NLL sit at the same θ.^[4]

Most losses in this series are negative log-likelihoods. Mean squared error is the negative log-likelihood of a Gaussian noise model; cross-entropy is the negative log-likelihood of a categorical model.^[3] Choosing a loss is choosing a noise model, whether or not the choice is stated.

04Information and entropy

An outcome with probability p carries self-information −log₂ p bits: a fair coin flip delivers one bit, a 1-in-1024 event delivers ten. The logarithm makes information add across independent events, and the base chooses the unit. Shannon's 1948 paper introduced the word bit, which John Tukey had coined for binary digit.^[6][2]

Entropy is the expected self-information: the average surprise of drawing from p. It is zero when one outcome is certain and reaches its maximum log₂ k when all k outcomes are equally likely.^[1][2]

The entropy of a language, in bits per token, is the floor under any model's loss on it. A model cannot predict the irreducible randomness of what a person will type next; it can only stop adding avoidable surprise on top of it. The scaling-law fits on the training page have a constant term for exactly this reason.

05Cross-entropy and KL divergence

A model q is scored against the true distribution p by the cross-entropy, the average surprise the model experiences on outcomes drawn from the truth. It splits into two parts: the entropy of the truth, which no model can reduce, and the KL divergence from p to q, which measures the model's avoidable surprise.^[2]

KL(p‖q) ≥ 0 with equality only when q equals p, a consequence of Jensen's inequality applied to the convex function −log.^[1] So minimizing cross-entropy over a fixed dataset minimizes the divergence from the data distribution, and the minimum of the loss is the entropy of the data, not zero.

The divergence is not symmetric: KL(p‖q) and KL(q‖p) differ, and they penalize different mistakes. KL(p‖q) blows up when q puts zero mass where p has some, since the model is infinitely surprised by a real outcome; KL(q‖p) ignores regions p covers that q skips. Fitting by maximum likelihood minimizes KL(p‖q), the direction that forbids the model from ruling out anything the data do.^[1][7] The fine-tuning page uses a KL term in the other role, as a leash that keeps a tuned model near its reference.

06Softmax, temperature and log-sum-exp

A network's last layer produces real-valued scores, the logits, not probabilities. The softmax exponentiates them, which makes them positive, and divides by the sum, which makes them sum to one. It keeps the ordering, so the largest logit is the predicted class with or without the normalization.^[3] The form goes back to Boltzmann's distribution over the energy states of gas molecules, proportional to exp(−E/kT), where the temperature T controls how strongly low energies are favored; Gibbs adapted the idea in 1902.^[3]

Subtracting the largest logit before exponentiating changes nothing mathematically, because softmax is invariant to adding a constant to every input, and it keeps every exponential at most one so nothing overflows. Frameworks compute the log-probability this way directly; PyTorch's cross-entropy loss takes logits and is documented as log-softmax followed by negative log-likelihood.^[8]

The cross-entropy of a one-hot target against the softmax is −log p_true, and its gradient with respect to the logits is p − y: the predicted probabilities minus the one-hot target.^[3] The loss is bounded below by zero and reaches it only in the limit of infinite confidence, so a trained classifier keeps pushing its logits apart; a wrong prediction made with probability near one costs −log of something near zero, which is unbounded.^[3]

07A stable cross-entropy, checked

These complete programs implement log-sum-exp with the maximum subtracted, the log-softmax, the cross-entropy of a one-hot target, entropy and KL divergence. The checks assert the properties from this page: shift invariance of the softmax under a shift of 1000 that would overflow a naive exponential, CE = H + KL on a fixed pair of distributions, KL ≥ 0 and KL(p‖p) = 0, and that the gradient p − y agrees with a finite-difference derivative of the loss.

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <vector>
using Vector = std::vector<double>;
double logSumExp(const Vector& logits) {
    const double maximum = *std::max_element(logits.begin(), logits.end());
    double total = 0;
    for (double logit : logits) total += std::exp(logit - maximum); // Every term is at most 1: no overflow.
    return maximum + std::log(total);
}
Vector logSoftmax(const Vector& logits) {
    const double normalizer = logSumExp(logits);
    Vector logProbabilities(logits.size());
    for (std::size_t index = 0; index < logits.size(); ++index) logProbabilities[index] = logits[index] - normalizer;
    return logProbabilities;
}
// Cross-entropy of a one-hot target against the softmax of the logits: −log p[target].
double crossEntropyFromLogits(const Vector& logits, std::size_t target) { return -logSoftmax(logits)[target]; }
double entropyBits(const Vector& probabilities) {
    double sum = 0;
    for (double p : probabilities) if (p > 0) sum -= p * std::log2(p); // 0 log 0 counts as 0.
    return sum;
}
double crossEntropyBits(const Vector& truth, const Vector& model) {
    double sum = 0;
    for (std::size_t index = 0; index < truth.size(); ++index)
        if (truth[index] > 0) sum -= truth[index] * std::log2(model[index]); // Infinite if model[index] == 0.
    return sum;
}
double klBits(const Vector& truth, const Vector& model) { return crossEntropyBits(truth, model) - entropyBits(truth); }
int main() {
    const Vector logits{2.0, 1.0, -1.0};
    Vector shifted = logits;
    for (double& logit : shifted) logit += 1000.0; // exp(1002) overflows a double; the stable form does not care.
    const Vector probabilities = logSoftmax(logits), shiftedProbabilities = logSoftmax(shifted);
    double mass = 0;
    for (std::size_t index = 0; index < 3; ++index) {
        assert(std::abs(probabilities[index] - shiftedProbabilities[index]) < 1e-9); // Shift invariance.
        mass += std::exp(probabilities[index]);
    }
    assert(std::abs(mass - 1.0) < 1e-12); // The probabilities sum to one.
    const Vector truth{0.7, 0.2, 0.1}, model{0.5, 0.3, 0.2};
    assert(std::abs(crossEntropyBits(truth, model) - (entropyBits(truth) + klBits(truth, model))) < 1e-12);
    assert(klBits(truth, model) > 0 && std::abs(klBits(truth, truth)) < 1e-12); // Gibbs' inequality.
    assert(std::abs(klBits(truth, model) - klBits(model, truth)) > 1e-3);    // Not symmetric.
    const std::size_t target = 1;
    for (std::size_t index = 0; index < 3; ++index) {
        Vector plus = logits, minus = logits;
        plus[index] += 1e-5; minus[index] -= 1e-5;
        const double numerical = (crossEntropyFromLogits(plus, target) - crossEntropyFromLogits(minus, target)) / 2e-5;
        const double analytic = std::exp(probabilities[index]) - (index == target ? 1.0 : 0.0); // p − y.
        assert(std::abs(numerical - analytic) < 1e-7);
    }
}

fn log_sum_exp(logits: &[f64]) -> f64 {
    let maximum = logits.iter().copied().fold(f64::NEG_INFINITY, f64::max);
    let total: f64 = logits.iter().map(|logit| (logit - maximum).exp()).sum(); // Every term is at most 1: no overflow.
    maximum + total.ln()
}
fn log_softmax(logits: &[f64]) -> Vec<f64> {
    let normalizer = log_sum_exp(logits);
    logits.iter().map(|logit| logit - normalizer).collect()
}
// Cross-entropy of a one-hot target against the softmax of the logits: −log p[target].
fn cross_entropy_from_logits(logits: &[f64], target: usize) -> f64 { -log_softmax(logits)[target] }
fn entropy_bits(probabilities: &[f64]) -> f64 {
    probabilities.iter().filter(|&&p| p > 0.0).map(|p| -p * p.log2()).sum() // 0 log 0 counts as 0.
}
fn cross_entropy_bits(truth: &[f64], model: &[f64]) -> f64 {
    truth.iter().zip(model).filter(|(p, _)| **p > 0.0).map(|(p, q)| -p * q.log2()).sum() // Infinite if q == 0.
}
fn kl_bits(truth: &[f64], model: &[f64]) -> f64 { cross_entropy_bits(truth, model) - entropy_bits(truth) }
fn main() {
    let logits = [2.0, 1.0, -1.0];
    let shifted: Vec<f64> = logits.iter().map(|logit| logit + 1000.0).collect(); // exp(1002) overflows; the stable form does not care.
    let probabilities = log_softmax(&logits);
    let shifted_probabilities = log_softmax(&shifted);
    let mut mass = 0.0;
    for index in 0..3 {
        assert!((probabilities[index] - shifted_probabilities[index]).abs() < 1e-9); // Shift invariance.
        mass += probabilities[index].exp();
    }
    assert!((mass - 1.0).abs() < 1e-12); // The probabilities sum to one.
    let truth = [0.7, 0.2, 0.1];
    let model = [0.5, 0.3, 0.2];
    assert!((cross_entropy_bits(&truth, &model) - (entropy_bits(&truth) + kl_bits(&truth, &model))).abs() < 1e-12);
    assert!(kl_bits(&truth, &model) > 0.0 && kl_bits(&truth, &truth).abs() < 1e-12); // Gibbs' inequality.
    assert!((kl_bits(&truth, &model) - kl_bits(&model, &truth)).abs() > 1e-3);    // Not symmetric.
    let target = 1;
    for index in 0..3 {
        let mut plus = logits;
        let mut minus = logits;
        plus[index] += 1e-5;
        minus[index] -= 1e-5;
        let numerical = (cross_entropy_from_logits(&plus, target) - cross_entropy_from_logits(&minus, target)) / 2e-5;
        let analytic = probabilities[index].exp() - if index == target { 1.0 } else { 0.0 }; // p − y.
        assert!((numerical - analytic).abs() < 1e-7);
    }
}

08Where probability goes wrong in code

The two directions of KL divergence answer different questions, and papers specify which one they minimize because the fitted result differs. When a divergence appears in a loss, find out which argument is the data and which is the model before reading any conclusion from it.

A softmax output is a distribution by construction, not a calibrated one: a model can report 0.95 for predictions that are right 70% of the time. Cross-entropy training pushes toward calibration on the training distribution, and the evaluation page measures how far a model drifts from it on held-out data.

Likelihood and probability are read in opposite directions. P(data | θ) summed over all possible data is one; summed over all θ it is anything. Treating a likelihood as a distribution over parameters is the mistake the posterior in §1 exists to correct, and it needs a prior to do it.

09What's next

Linear Models and Gradient Descent puts the two foundation pages to work: a linear map from the first produces a prediction, a negative log-likelihood from this one scores it, and gradient descent moves the weights downhill. Later pages keep that loop and replace the model in the middle.

10Sources

The cited texts define the quantities and state the theorems. Widget readouts report values computed in the page from the displayed settings and seeds.

1. Christopher M. Bishop, 2006. Pattern Recognition and Machine Learning, Springer. The sum and product rules and Bayes' theorem (1.10–1.12), expectation and its sample estimate (1.33–1.35), entropy and its maximum at the uniform distribution (1.97–1.98), KL divergence, Jensen's inequality and KL ≥ 0 (1.113–1.118), and maximum likelihood as KL minimization (1.119).
2. Aston Zhang, Zachary C. Lipton, Mu Li, Alexander J. Smola, 2023. Dive into Deep Learning, Appendix: Information Theory, Cambridge University Press. Self-information in bits, entropy bounds, KL properties including infinity and asymmetry, and cross-entropy as entropy plus KL.
3. Aston Zhang et al., 2023. Dive into Deep Learning, Section 4.1: Softmax Regression. The softmax definition and its order preservation, the Boltzmann and Gibbs origin and temperature, the cross-entropy loss bounded below by zero, and its gradient softmax(o) − y.
4. Aston Zhang et al., 2023. Dive into Deep Learning, Appendix: Maximum Likelihood. The 9-of-13 coin example, likelihood underflow and the negative log-likelihood.
5. Aston Zhang et al., 2023. Dive into Deep Learning, Section 2.6: Probability and Statistics. Expectation, variance and the behaviour of sample averages.
6. Claude E. Shannon, 1948. A Mathematical Theory of Communication, Bell System Technical Journal 27. Entropy as a measure of information; the paper that introduced the word bit, as sources 1 and 2 note.
7. Solomon Kullback, Richard A. Leibler, 1951. On Information and Sufficiency, Annals of Mathematical Statistics 22(1). The origin of the divergence named in source 1.
8. PyTorch contributors. torch.nn.CrossEntropyLoss. The loss takes unnormalized logits and is equivalent to LogSoftmax followed by NLLLoss.