Cross-Entropy and Kullback–Leibler Divergence

What a model pays for using the wrong probabilities. Cross-entropy defined and split into entropy plus the Kullback–Leibler divergence; Gibbs' inequality proved two ways, with its case of equality; cross-entropy loss shown to be the average negative log-likelihood, so that maximum likelihood is minimum divergence from the data; the asymmetry of the divergence and what each direction punishes; the log-sum inequality, merging of outcomes, convexity, and the link to the chi-square statistic and to Fisher information, all proved. The running example is the character models of the Tiny Shakespeare text. Worked problems on exact small cases, the loss of a uniform model, smoothing on held-out text, two normal distributions and the failure of the triangle inequality.

A model that gives each of the 65 characters of the Tiny Shakespeare text the same probability scores a loss of 4.17 nats per character, and it would score exactly that on any text over those characters. A model that uses the character frequencies of the text scores 3.31. Why does the first number not depend on the text, and can any model that ignores context score below the second? The loss is a cross-entropy. It equals the entropy of the text's characters plus a penalty that is zero only when the model's probabilities are the text's own frequencies, so 3.31 nats is the floor, and the uniform model's 4.17 is the logarithm of 65 whatever the frequencies are.

The cross-entropy of a model $q$ relative to a distribution $p$ on the same alphabet is $H(p, q) = -\sum_x p(x)\log q(x)$. The penalty is the Kullback–Leibler divergence, $D(p \,\|\, q) = \sum_x p(x)\log\frac{p(x)}{q(x)}$, named for Kullback and Leibler (1951), often shortened to KL divergence, and also called the relative entropy.

First we define the two quantities and the identity that ties them to entropy. Then we prove Gibbs' inequality, that the divergence is never negative. Next we show that the cross-entropy loss used to train models is the average negative log-likelihood, which makes maximum likelihood a search for the model of least divergence from the data. Then we take up the asymmetry of the divergence and its two directions. Finally we prove its further properties and its relation to the chi-square statistic and to Fisher information. The article assumes Entropy, whose notation it keeps.

This article is the home of cross-entropy, the Kullback–Leibler divergence and Gibbs' inequality on this site. Entropy borrows Gibbs' inequality from here for three of its proofs, and Mutual Information is built on the divergence.

Notation

Lowercase $p$ and $q$ are two probability mass functions on one finite alphabet $\mathcal{X}$. In this unit $p$ is the distribution that produces the outcomes (the data, or the truth) and $q$ is the one used to predict them (the model). The cross-entropy $H(p, q)$, with two lowercase arguments, should not be confused with the joint entropy $H(X, Y)$ of two random variables, with capitals: the first involves two distributions on one alphabet, the second one distribution on pairs.

The conventions for zeros extend those of Entropy. A term with $p(x) = 0$ contributes 0 to every sum below, whatever $q(x)$ is. A term with $p(x) > 0$ and $q(x) = 0$ is $+\infty$: both $H(p, q)$ and $D(p \,\|\, q)$ are infinite when the model rules out something that can happen. Sums therefore run over the support of $p$, the outcomes with $p(x) > 0$.

Logarithms written $\log$ are to any fixed base greater than 1. Losses in this article are in nats (natural logarithm, $\ln$), the unit of PyTorch's F.cross_entropy and of the language model pages. Where bits are used the text says so.

Paying for the wrong probabilities

Here is the idea. An outcome $x$ that a model gave probability $q(x)$ carries the surprisal $-\log q(x)$ for someone who believes the model. If outcomes are in fact produced with probabilities $p(x)$, the average surprisal experienced is the cross-entropy:

$$H(p, q) = E_p\big[-\log q(X)\big] = \sum_{x} p(x)\log\frac{1}{q(x)}.$$

The expectation is taken with the true probabilities, and the surprisal is computed with the model's. When the model is right, $q = p$, the cross-entropy is the entropy: $H(p, p) = H(p)$.

For the text, let $p$ be the shares of the 65 characters in the whole file, and consider three models of a single character.

Model $q$ $H(p, q)$ (nats)
Uniform over the 65 characters 4.1744
The shares in the first 90% of the file (the walkthrough's training split) 3.3129
The shares in the whole file, $q = p$ 3.3128

The uniform model gives $-\ln\frac{1}{65} = \ln 65 = 4.1744$ nats for every character, so its average is 4.1744 under any $p$ at all:

$$H(p, u) = \sum_x p(x)\ln 65 = \ln 65.$$

That answers the first half of the opening question. The loss of a model that spreads its probability evenly over $n$ outcomes is $\log n$, for every text. The table of reference losses in the bigram language model lists this value, 4.17, in its first row.

The Kullback–Leibler divergence of $q$ from $p$ is the excess of the cross-entropy over the entropy:

$$D(p \,\|\, q) = H(p, q) - H(p) = \sum_{x} p(x)\log\frac{p(x)}{q(x)}.$$

The second form follows by combining the two sums term by term, $-p\log q + p\log p = p\log\frac{p}{q}$. Rearranged,

$$H(p, q) = H(p) + D(p \,\|\, q).$$

The cross-entropy is the uncertainty that is in the data anyway, plus what the model adds by being wrong. For the uniform model, $D(p \,\|\, u) = 4.1744 - 3.3128 = 0.8616$ nats. For the training-split shares it is 0.0001 nats: the split is nine tenths of the file, and its shares are nearly the file's.

The divergence is the expected value, under $p$, of $\log\frac{p(X)}{q(X)}$, the logarithm of the likelihood ratio of the two distributions for one observation. For $N$ independent observations the log-likelihood ratios add, so the expected log-likelihood ratio in favor of the truth is $N\,D(p \,\|\, q)$: the divergence is the rate at which evidence against a wrong model accumulates. The Neyman–Pearson Lemma shows why the likelihood ratio is the right statistic for that comparison.

Gibbs' inequality

Can a wrong model ever have a lower cross-entropy than the right one, by luck of the probabilities? No. That is the content of the most used inequality of the subject. MacKay (2003, Section 2.6) names it after Gibbs and calls it "probably the most important inequality in this book".

Everything rests on one fact about the logarithm.

Lemma. For every $x > 0$, $\ln x \le x - 1$, with equality only at $x = 1$.

Proof. Let $f(x) = x - 1 - \ln x$ for $x > 0$. Its derivative $f'(x) = 1 - \frac1x$ is negative for $x < 1$ and positive for $x > 1$. So $f$ decreases strictly up to $x = 1$ and increases strictly after it, and its only minimum is $f(1) = 0$. Hence $f(x) \ge 0$, with equality only at $x = 1$. $\square$

Geometrically, the line $y = x - 1$ is the tangent to the curve $y = \ln x$ at $x = 1$, and the curve, being concave, lies below its tangent.

Theorem (Gibbs' inequality). Let $p$ be a probability mass function on a finite alphabet, and let $q$ assign nonnegative numbers to the same alphabet with $\sum_x q(x) \le 1$. Then

$$D(p \,\|\, q) = \sum_{x} p(x)\log\frac{p(x)}{q(x)} \ge 0,$$

with equality exactly when $q(x) = p(x)$ for every $x$. In particular, for two mass functions $H(p, q) \ge H(p)$, with equality exactly when $q = p$.

The statement allows $q$ to sum to less than 1, which costs nothing in the proof. One use shows what the extra generality is for. The lengths $\ell(x)$ of the code words of a uniquely decodable binary code satisfy $\sum_x 2^{-\ell(x)} \le 1$, so $q(x) = 2^{-\ell(x)}$ is such a $q$, and the expected length $L$ of the code satisfies $L - H(p) = \sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}} = D(p \,\|\, q) \ge 0$ in one step. Perplexity and Source Coding, which proves the inequality on the lengths, takes the equivalent route: it divides $q$ by its sum, applies the inequality to two mass functions, and accounts separately for the part of the sum that falls short of 1. No page of the unit depends on the general form.

The plan of the proof: apply the lemma to the ratio $q(x)/p(x)$ and average under $p$. The right side of the lemma then averages to $\sum q - \sum p \le 0$.

Proof. If $q(x) = 0$ for some $x$ with $p(x) > 0$, the divergence is $+\infty$ and the inequality holds strictly. Otherwise let $S$ be the support of $p$, on which $q$ is positive. It is enough to prove the inequality for natural logarithms, since changing the base multiplies the divergence by a positive constant. By the lemma with $x = q(x)/p(x)$,

$$-D(p \,\|\, q) = \sum_{x \in S} p(x)\ln\frac{q(x)}{p(x)} \le \sum_{x \in S} p(x)\left(\frac{q(x)}{p(x)} - 1\right) = \sum_{x \in S} q(x) - \sum_{x \in S} p(x) \le 1 - 1 = 0.$$

So $D(p \,\|\, q) \ge 0$.

Equality. If $q = p$ every logarithm is $\ln 1 = 0$ and $D = 0$. Conversely, suppose $D(p \,\|\, q) = 0$. Then both inequalities in the display are equalities. The first is a sum of the lemma's inequalities, each multiplied by $p(x) > 0$, so each must be an equality, which by the lemma means $q(x)/p(x) = 1$ for every $x \in S$. Then $\sum_{x \in S} q(x) = 1$, and since $q$ is nonnegative and sums to at most 1, $q(x) = 0$ off $S$, where $p(x) = 0$ as well. So $q = p$ everywhere. $\square$

A second proof, by Jensen's inequality. Jensen's inequality, proved in Probability Inequalities, says that for a concave function $\varphi$ and a random variable $W$, $E[\varphi(W)] \le \varphi(E[W])$. Take $\varphi = \ln$, and let $W = q(X)/p(X)$ where $X$ has mass function $p$, with $q$ positive on the support $S$ of $p$. Then

$$-D(p \,\|\, q) = E_p\!\left[\ln\frac{q(X)}{p(X)}\right] \le \ln E_p\!\left[\frac{q(X)}{p(X)}\right] = \ln\sum_{x \in S} p(x)\,\frac{q(x)}{p(x)} = \ln\sum_{x \in S} q(x) \le \ln 1 = 0.$$

This is the proof in MacKay (2003, solution to Exercise 2.26). The two proofs are close relatives: the lemma is the statement that the concave function $\ln$ lies below its tangent line at 1, and the proof of Jensen's inequality on that page uses the same kind of supporting line at the mean. Neither proof uses anything from Entropy, which is why that article can borrow the theorem.

Back to the text. With $u$ the uniform model, Gibbs' inequality gives $D(p \,\|\, u) = \ln 65 - H(p) \ge 0$, which is the upper bound on entropy proved in Entropy. And it answers the second half of the opening question. For every model $q$ of a single character, $H(p, q) \ge H(p) = 3.3128$ nats, with equality only for $q = p$. No model that ignores context can score below 3.3128 on the whole text, and only the text's own frequencies reach it.

Cross-entropy loss is the average negative log-likelihood

The models on this site are not scored against a known distribution $p$. They are scored on data. This section shows that the two are the same computation.

Let $x_1, \dots, x_N$ be observed outcomes, and let $\hat{p}(x) = \frac{1}{N}\#\{i : x_i = x\}$ be their empirical distribution, the share of the sample equal to $x$. A model $q$ that treats the observations as independent gives the sample the likelihood $\prod_i q(x_i)$ (see The Likelihood Function). The loss that training code reports is the average negative log-likelihood per observation.

Theorem (the loss is a cross-entropy). For any sample and any model $q$,

$$-\frac{1}{N}\sum_{i=1}^{N}\ln q(x_i) = H(\hat{p}, q) = H(\hat{p}) + D(\hat{p} \,\|\, q).$$

Proof. Group the observations by their value. The outcome $x$ occurs $N\hat{p}(x)$ times, and each occurrence contributes $-\ln q(x)$. So $-\frac1N\sum_i \ln q(x_i) = -\frac1N\sum_x N\hat{p}(x)\ln q(x) = -\sum_x \hat{p}(x)\ln q(x)$, which is $H(\hat{p}, q)$. The second equality is the identity of the last section. $\square$

The table of the last section was an instance. There $p$ was the empirical distribution of the 1,115,394 characters, and the three numbers were the average negative log-likelihoods of the file under three models.

Three consequences follow, and each is used on other pages.

Maximum likelihood is minimum divergence. Suppose the model is to be chosen from a family $\{q_\theta\}$. The entropy $H(\hat{p})$ does not depend on $\theta$. So the three problems

$$\text{maximize } \prod_i q_\theta(x_i), \qquad \text{minimize } H(\hat{p}, q_\theta), \qquad \text{minimize } D(\hat{p} \,\|\, q_\theta)$$

have the same solutions. Maximum likelihood estimation picks the member of the family closest to the data, with closeness measured by the divergence from the empirical distribution to the model.

An unrestricted model fits the frequencies. If the family contains every distribution on the alphabet, Gibbs' inequality gives the answer without calculus: $D(\hat{p} \,\|\, q) \ge 0$ with equality only at $q = \hat{p}$. The maximum likelihood estimate of a distribution on a finite alphabet is the vector of observed shares, and it is unique. Naive Bayes classification reaches the same estimate with a Lagrange multiplier.

Models with context. A model that predicts a character from the one before it has a row of probabilities $q(\cdot \mid a)$ for each previous character $a$. Its loss over the adjacent pairs of a text is the average of $-\ln q(b \mid a)$ over the pairs $(a, b)$. Grouping the pairs by $a$, and writing $\hat{p}(a)$ for the share of pairs whose first character is $a$ and $\hat{p}(\cdot \mid a)$ for the shares of what follows it,

$$\text{loss} = \sum_{a}\hat{p}(a)\,H\big(\hat{p}(\cdot \mid a),\,q(\cdot \mid a)\big) = H(X_2 \mid X_1) + \sum_a \hat{p}(a)\,D\big(\hat{p}(\cdot \mid a)\,\big\|\,q(\cdot \mid a)\big),$$

by the identity applied to each row. Here $H(X_2 \mid X_1) = \sum_a \hat{p}(a) H(\hat{p}(\cdot \mid a))$ is the conditional entropy of the text's adjacent characters. Each divergence is at least 0, and the rows can be chosen separately, so the loss is smallest when every row equals the observed shares. Its least value is the conditional entropy. On the training split that is 2.4519 nats, the figure the bigram language model gives (as 2.45) for the floor no bigram table can pass on the training text. The argument there, by the maximum likelihood estimate of each row, is this one.

The same holds for the two-outcome case of Classification Loss Functions. The log loss of a predicted probability is $-\ln q(y)$ for the outcome $y$ that occurred, and its average over cases is a cross-entropy. That page's statement that the log loss "is the negative log-likelihood of the outcome under the model" is the theorem above.

What the model is judged against: held-out text

A model is fitted on one sample and judged on another. The theorem applies to the second sample as well as the first. If $\hat{p}_{\text{val}}$ is the empirical distribution of held-out data and $q$ the fitted model,

$$\text{held-out loss} = H(\hat{p}_{\text{val}}) + D(\hat{p}_{\text{val}} \,\|\, q).$$

For the single-character model fitted on the training split and scored on the validation split (the last 111,540 characters), the three terms are $3.3473 = 3.3373 + 0.0100$ nats. The validation text has slightly different shares from the training text, and the model pays 0.0100 nats per character for the difference.

Example (a loss that is infinite). The roles cannot be exchanged. Four characters of the training split, $, &, 3 and X, never occur in the validation split. A model equal to the validation shares gives them probability 0, and its cross-entropy on the training split is infinite, although it differs from the training shares hardly at all: the four characters make up 143 of 1,003,854. A single outcome that the model calls impossible, once observed, makes the average surprisal infinite. The same happens to the bigram model fitted by counts. At 187 of the 111,539 adjacent pairs of the validation text, a pair occurs that the training text never contains, and the count-based table gives each of them probability 0. This is why count-based models are smoothed, and why the bigram page reports its count-based validation loss with add-one smoothing. Problem 3 below works that number.

In the long run

If the observations are independent draws from a distribution $p$, then for a fixed model $q$ with $H(p, q)$ finite, the loss $-\frac1N\sum_i \ln q(X_i)$ is an average of independent, identically distributed terms with mean $E_p[-\ln q(X)] = H(p, q)$. By the law of large numbers it converges to $H(p, q) = H(p) + D(p \,\|\, q)$. In the long run, then, minimizing the loss means minimizing the divergence $D(p \,\|\, q)$ from the true distribution, and a family that does not contain $p$ is led toward its member with the least divergence from $p$. That statement concerns the loss of each fixed model. The convergence of the minimizing parameter itself needs more conditions, and is the subject of Asymptotics of the Maximum Likelihood Estimator.

The divergence is not a distance

The notation $D(p \,\|\, q)$, with its double bar, is a reminder that the two arguments play different roles. The expectation is taken under the first.

Asymmetry. For the text and the uniform model, $D(p \,\|\, u) = 0.8616$ nats, and in the other order $D(u \,\|\, p) = 1.3766$ nats. The first number is the cost of predicting the text with a uniform model. The second is the cost of predicting uniformly drawn characters with the text's frequencies. It is larger because a uniform source produces the dollar sign once in 65 characters, and the text's model, which saw it once in 1,115,394, charges $\ln 1{,}115{,}394 = 13.92$ nats for each one.

No triangle inequality. A distance satisfies $d(a, c) \le d(a, b) + d(b, c)$. The divergence does not. For three coins with probabilities of heads 0.5, 0.25 and 0.1, in bits,

$$D(0.5 \,\|\, 0.1) = 0.7370 > D(0.5 \,\|\, 0.25) + D(0.25 \,\|\, 0.1) = 0.2075 + 0.1332 = 0.3407.$$

Problem 5 works the arithmetic. The divergence shares one property with a distance, the one Gibbs' inequality gives: it is zero exactly when its arguments coincide, and positive otherwise. MacKay (2003, Section 2.6) makes the same point, that the relative entropy is sometimes called a distance but "is not strictly a distance".

The two directions

Because the divergence is asymmetric, "the distribution in the family closest to $p$" has two meanings.

  • Forward: minimize $D(p \,\|\, q)$ over $q$. The expectation is under the target $p$. The divergence is infinite if $q$ gives probability 0 to anything $p$ can produce, so the minimizer must cover the whole support of $p$. This is the direction of maximum likelihood, as shown above, with $p$ the empirical distribution.
  • Reverse: minimize $D(q \,\|\, p)$ over $q$. The expectation is under the approximation $q$. The divergence is infinite if $q$ gives positive probability to anything $p$ cannot produce, so the minimizer must stay inside the support of $p$. It is free to ignore parts of it. This is the direction of the variational methods of MacKay (2003, Chapter 33). There the target is a distribution whose normalizing constant is hard to evaluate, and a simpler distribution $q$ is adjusted to minimize the relative entropy from $q$ to the target. Those methods belong to the Bayesian Inference unit.

The character distribution shows the difference on a deliberately crude family: the distributions that are uniform on some subset $A$ of the alphabet, $q_A(x) = 1/|A|$ for $x \in A$ and 0 elsewhere.

Forward. $D(p \,\|\, q_A)$ is infinite unless $A$ contains every character that occurs. The only member of the family with a finite forward divergence is the uniform distribution on all 65, at 0.8616 nats. It must reserve $\frac{1}{65}$ for the dollar sign, which occurs once.

Reverse. For a subset of $k$ characters,

$$D(q_A \,\|\, p) = \sum_{x \in A}\frac1k\ln\frac{1/k}{p(x)} = -\ln k - \frac1k\sum_{x \in A}\ln p(x).$$

For a given $k$ the sum of $\ln p(x)$ is largest when $A$ holds the $k$ most frequent characters, so only those subsets need to be compared:

$k$ The $k$ most frequent characters hold this share of the text $D(q_A \,\|\, p)$ (nats)
1 0.1523 1.8818
5 0.4060 0.9890
10 0.6247 0.5617
19 0.8284 0.3788
20 0.8424 0.3747
21 0.8543 0.3762
26 0.9011 0.4051
65 1.0000 1.3766

The reverse divergence is least at $k = 20$: the space, the newline, the comma and the seventeen lowercase letters e t o a h s r n i l d u m y w f c. The best approximation in this direction gives no probability to 45 of the 65 characters, which together make up 15.76 percent of the text. The forward direction cannot leave out even one.

The reverse divergence of a uniform distribution on the k most frequent characters of the text, for every k from 1 to 65. Notice that the curve falls steeply, reaches its minimum of 0.3747 nats at k = 20, and then climbs as rarer characters are let in, ending at 1.3766 nats when all 65 are included. The forward divergence is finite at one point only, k = 65, where it is 0.8616 nats (the square); for every smaller k it is infinite.
The reverse divergence of a uniform distribution on the k most frequent characters of the text, for every k from 1 to 65. Notice that the curve falls steeply, reaches its minimum of 0.3747 nats at k = 20, and then climbs as rarer characters are let in, ending at 1.3766 nats when all 65 are included. The forward divergence is finite at one point only, k = 65, where it is 0.8616 nats (the square); for every smaller k it is infinite.

The two answers describe the text in different ways, and neither is wrong. A forward fit is a model that is never infinitely surprised. A reverse fit marks out a high-probability region of the distribution, and it says nothing about what lies outside it. Which is wanted depends on the use. A model that will be scored on held-out data by its log-likelihood must be fitted in the forward direction, or smoothed until it covers everything.

Further properties

Four more properties are used elsewhere in the unit. Each follows from Gibbs' inequality.

Theorem (log-sum inequality). For nonnegative numbers $a_1, \dots, a_n$ and positive numbers $b_1, \dots, b_n$, with $A = \sum_i a_i$ and $B = \sum_i b_i$,

$$\sum_{i=1}^{n} a_i\log\frac{a_i}{b_i} \ge A\log\frac{A}{B},$$

with equality exactly when $a_i/b_i$ is the same for every $i$. (Terms with $a_i = 0$ are 0.)

Proof. If $A = 0$ every $a_i$ is 0 and both sides are 0. Otherwise let $p_i = a_i/A$ and $q_i = b_i/B$, two mass functions. Then

$$\sum_i a_i\log\frac{a_i}{b_i} = A\sum_i p_i\log\frac{A\,p_i}{B\,q_i} = A\,D(p \,\|\, q) + A\log\frac{A}{B}\sum_i p_i \ge A\log\frac{A}{B}$$

by Gibbs' inequality, with equality exactly when $p = q$, that is $a_i/A = b_i/B$ for all $i$. $\square$

Theorem (merging outcomes). Let $g$ be a function on the alphabet, and let $p_g$ and $q_g$ be the distributions of $g(X)$ when $X$ has distribution $p$ and $q$: $p_g(y) = \sum_{x : g(x) = y} p(x)$, and likewise $q_g$. Then $D(p_g \,\|\, q_g) \le D(p \,\|\, q)$.

Proof. If $D(p \,\|\, q)$ is infinite there is nothing to prove. Otherwise $q$ is positive on the support of $p$. Drop from the alphabet the outcomes with $q(x) = 0$, which have $p(x) = 0$ too and contribute to neither side. For each value $y$ of $g$, apply the log-sum inequality to the numbers $a = p(x)$ and $b = q(x)$ for the $x$ with $g(x) = y$:

$$\sum_{x : g(x) = y} p(x)\log\frac{p(x)}{q(x)} \ge p_g(y)\log\frac{p_g(y)}{q_g(y)}.$$

Summing over $y$ gives $D(p \,\|\, q) \ge D(p_g \,\|\, q_g)$. $\square$

Merging outcomes can hide a difference between two distributions and cannot create one. On the text, the divergence of the validation shares from the training shares is 0.0100 nats over the 65 characters. After folding capitals into lowercase letters (39 outcomes) it is 0.0028 nats, and after sorting characters into the four groups of Entropy (lowercase, capitals, space and newline, other symbols) it is 0.0021 nats. The same theorem, applied to joint distributions, is the reason processing cannot increase mutual information.

Theorem (convexity). For mass functions $p_1, p_2, q_1, q_2$ on one alphabet and $0 \le \lambda \le 1$,

$$D\big(\lambda p_1 + (1-\lambda)p_2 \,\big\|\, \lambda q_1 + (1-\lambda)q_2\big) \le \lambda D(p_1 \,\|\, q_1) + (1-\lambda)D(p_2 \,\|\, q_2).$$

Proof. If the right side is infinite there is nothing to prove, and for $\lambda = 0$ or 1 the two sides are equal. Otherwise fix an outcome $x$ and apply the log-sum inequality to the two pairs $a_1 = \lambda p_1(x)$, $b_1 = \lambda q_1(x)$ and $a_2 = (1-\lambda)p_2(x)$, $b_2 = (1-\lambda)q_2(x)$, leaving out a pair whose $b$ is 0 (its $a$ is then 0 as well, since the right side is finite):

$$\big[\lambda p_1(x) + (1-\lambda)p_2(x)\big]\log\frac{\lambda p_1(x) + (1-\lambda)p_2(x)}{\lambda q_1(x) + (1-\lambda)q_2(x)} \le \lambda p_1(x)\log\frac{p_1(x)}{q_1(x)} + (1-\lambda)p_2(x)\log\frac{p_2(x)}{q_2(x)}.$$

Summing over $x$ gives the statement. $\square$

With $p_1 = p_2 = p$ this says that $D(p \,\|\, q)$ is a convex function of the model $q$. A model that is a blend of two models is at least as good as the weighted average of their losses: $H(p, \lambda q_1 + (1-\lambda) q_2) \le \lambda H(p, q_1) + (1-\lambda)H(p, q_2)$, since the cross-entropy differs from the divergence by $H(p)$.

Theorem (independent pairs add). If $p(x, y) = p_1(x)\,p_2(y)$ and $q(x, y) = q_1(x)\,q_2(y)$, then $D(p \,\|\, q) = D(p_1 \,\|\, q_1) + D(p_2 \,\|\, q_2)$.

Proof. If either divergence on the right is infinite, some pair has $p(x, y) > 0$ and $q(x, y) = 0$, and the left side is infinite too. Otherwise $\log\frac{p(x, y)}{q(x, y)} = \log\frac{p_1(x)}{q_1(x)} + \log\frac{p_2(y)}{q_2(y)}$. Multiply by $p_1(x)p_2(y)$ and sum over both variables. In the first term the sum over $y$ of $p_2(y)$ is 1, leaving $D(p_1 \,\|\, q_1)$; in the second the sum over $x$ leaves $D(p_2 \,\|\, q_2)$. $\square$

By induction, $N$ independent observations from $p$, judged under a model that also treats them as independent draws from $q$, have divergence $N\,D(p \,\|\, q)$. This is the additivity used at the end of the section on paying for the wrong probabilities.

Small differences: chi-square and Fisher information

When the model is close to the truth, the divergence is close to half of a familiar statistic. This section proves the statement with explicit bounds. Natural logarithms are used throughout.

For mass functions $p$ and $q$ with $q$ positive on the alphabet, let

$$\chi^2(p, q) = \sum_{x}\frac{\big(p(x) - q(x)\big)^2}{q(x)}.$$

For a sample of size $N$ with shares $p$ and a hypothesized distribution $q$, $N\chi^2(p, q)$ is Pearson's chi-square statistic $\sum (O - E)^2/E$ with observed counts $O = Np$ and expected counts $E = Nq$, the statistic of feature selection and of the planned Categorical Data Analysis unit.

Theorem (the divergence and chi-square). Let $t(x) = \frac{p(x) - q(x)}{q(x)}$ be the relative error of the model on outcome $x$, and suppose $|t(x)| \le \varepsilon < 1$ for every $x$. Then, in nats,

$$\frac{\chi^2(p, q)}{2(1 + \varepsilon)} \le D(p \,\|\, q) \le \frac{\chi^2(p, q)}{2(1 - \varepsilon)}.$$

Also, with no condition on $t$ (and $q$ positive on the alphabet, as the definition of $\chi^2$ requires),

$$D(p \,\|\, q) \le \ln\big(1 + \chi^2(p, q)\big) \le \chi^2(p, q) \quad \text{in nats.}$$

The unit matters here. In bits the last inequality can fail: for $p = (1, 0)$ and $q = \left(\tfrac23, \tfrac13\right)$, $\chi^2 = 0.5$, and the divergence is $\ln\tfrac32 = 0.405$ nats but 0.585 bits.

The idea: write $p = q(1 + t)$. The divergence becomes an average, under $q$, of a function of $t$ that vanishes to second order at $t = 0$, and its second-order term is $t^2/2$.

Proof. Since $p(x) = q(x)(1 + t(x))$,

$$D(p \,\|\, q) = \sum_x q(x)\,(1 + t(x))\ln(1 + t(x)).$$

Because $\sum_x q(x)\,t(x) = \sum_x (p(x) - q(x)) = 0$, subtracting $t(x)$ inside the sum changes nothing:

$$D(p \,\|\, q) = \sum_x q(x)\,\psi(t(x)), \qquad \psi(t) = (1 + t)\ln(1 + t) - t.$$

(For $t = -1$, where $p(x) = 0$, $\psi(-1) = 1$ by the convention $0\ln 0 = 0$.) The function $\psi$ has $\psi(0) = 0$, $\psi'(t) = \ln(1 + t)$, so $\psi'(0) = 0$, and $\psi''(t) = \frac{1}{1 + t}$. By Taylor's theorem with the Lagrange form of the remainder, for each $t > -1$ there is a $\xi$ between 0 and $t$ with

$$\psi(t) = \frac{t^2}{2(1 + \xi)}.$$

If $|t| \le \varepsilon < 1$ then $1 - \varepsilon \le 1 + \xi \le 1 + \varepsilon$, so $\frac{t^2}{2(1+\varepsilon)} \le \psi(t) \le \frac{t^2}{2(1-\varepsilon)}$. Multiply by $q(x)$ and sum, using $\sum_x q(x)\,t(x)^2 = \chi^2(p, q)$, for the two-sided bound.

For the last claim, expand the square: $\chi^2(p, q) = \sum_x \frac{p(x)^2}{q(x)} - 2\sum_x p(x) + \sum_x q(x) = \sum_x \frac{p(x)^2}{q(x)} - 1$. So $E_p\!\left[\frac{p(X)}{q(X)}\right] = \sum_x p(x)\frac{p(x)}{q(x)} = 1 + \chi^2(p, q)$. By Jensen's inequality for the concave function $\ln$, as in the second proof of Gibbs' inequality,

$$D(p \,\|\, q) = E_p\!\left[\ln\frac{p(X)}{q(X)}\right] \le \ln E_p\!\left[\frac{p(X)}{q(X)}\right] = \ln\big(1 + \chi^2(p, q)\big),$$

and $\ln(1 + c) \le c$ by the lemma. $\square$

In the example above the first inequality is an equality: $\ln(1 + 0.5) = \ln\tfrac32$.

So when every relative error is small, $2N\,D(\hat{p} \,\|\, q)$, the likelihood ratio statistic for a hypothesized distribution $q$ (see Likelihood Ratio, Wald and Score Tests), and Pearson's $N\chi^2(\hat{p}, q)$ are nearly equal. On the text, taking the validation shares as $p$ and the training shares as $q$: $\chi^2 = 0.0233$, half of it is 0.0116, and the divergence is 0.0100 nats. The agreement is rough, and the two-sided bound does not apply, because the relative errors are not all small: the largest $|t|$ is 2.31, on a rare character. The unconditional bound holds, as it must: $\ln(1 + 0.0233) = 0.0230$, above 0.0100.

Corollary (Fisher information). Let $q_\theta$ be a family of mass functions on a finite alphabet, with $q_\theta(x) > 0$ and differentiable in a real parameter $\theta$. Then

$$\lim_{\delta \to 0}\frac{D(q_{\theta+\delta} \,\|\, q_\theta)}{\delta^2} = \frac{I(\theta)}{2}, \qquad I(\theta) = \sum_x q_\theta(x)\left(\frac{\partial}{\partial\theta}\ln q_\theta(x)\right)^2,$$

where $I(\theta)$ is the Fisher information of one observation, defined in Fisher Information and the Cramér–Rao Bound. (This $I$, with one argument, is not the mutual information $I(X; Y)$ of the next article.)

Proof. Apply the theorem with $p = q_{\theta+\delta}$ and $q = q_\theta$. The relative error is $t_\delta(x) = \frac{q_{\theta+\delta}(x) - q_\theta(x)}{q_\theta(x)}$, and by differentiability $t_\delta(x)/\delta \to \frac{\partial_\theta q_\theta(x)}{q_\theta(x)} = \frac{\partial}{\partial\theta}\ln q_\theta(x)$ as $\delta \to 0$, for each of the finitely many $x$. So $\varepsilon_\delta = \max_x |t_\delta(x)| \to 0$, and $\chi^2(q_{\theta+\delta}, q_\theta)/\delta^2 = \sum_x q_\theta(x)\,(t_\delta(x)/\delta)^2 \to I(\theta)$. The two-sided bound, divided by $\delta^2$, squeezes $D/\delta^2$ between $\frac{\chi^2/\delta^2}{2(1 + \varepsilon_\delta)}$ and $\frac{\chi^2/\delta^2}{2(1 - \varepsilon_\delta)}$, both of which tend to $I(\theta)/2$. $\square$

The order of the two arguments does not matter in the limit. Apply the theorem instead with $p = q_\theta$ and $q = q_{\theta+\delta}$. The relative error is now $\frac{q_\theta(x) - q_{\theta+\delta}(x)}{q_{\theta+\delta}(x)}$, and divided by $\delta$ it tends to $-\frac{\partial}{\partial\theta}\ln q_\theta(x)$, because $q_{\theta+\delta}(x) \to q_\theta(x)$. So $\chi^2(q_\theta, q_{\theta+\delta})/\delta^2 = \sum_x q_{\theta+\delta}(x)\,(\cdot)^2 \to I(\theta)$ again, and the same squeeze gives $D(q_\theta \,\|\, q_{\theta+\delta})/\delta^2 \to I(\theta)/2$. Fisher Information and the Cramér–Rao Bound states the approximation in that second order, with the first argument held fixed.

In words, $D(q_{\theta+\delta} \,\|\, q_\theta) \approx \tfrac12 I(\theta)\,\delta^2$ for small $\delta$: Fisher information is the curvature of the divergence at zero. For a coin with probability of heads $\theta$, $I(\theta) = \frac{1}{\theta(1-\theta)}$, so the approximation is $\frac{\delta^2}{2\theta(1-\theta)}$. The script compares it with the exact divergence at $\theta = 0.2$:

$\delta$ Exact $D$ (nats) $\delta^2 / (2\theta(1-\theta))$ Ratio
0.1 0.028168 0.031250 0.9014
0.01 0.00030870 0.00031250 0.9878
0.001 0.0000031211 0.0000031250 0.9988

The ratio tends to 1. This local form is what natural evolution strategies use: the natural gradient measures a step by the divergence it causes, and for a small step $\delta\theta$ that divergence is $\tfrac12\,\delta\theta^{\top}F\,\delta\theta$ with $F$ the Fisher information matrix. The corollary proves the one-parameter case on a finite alphabet. The case of several parameters and of densities is stated there and not proved here.

What is proved, what is cited, what is computed

Proved here: the lemma $\ln x \le x - 1$; Gibbs' inequality with its case of equality, by the lemma and again by Jensen's inequality; that the cross-entropy loss of a sample is its average negative log-likelihood, and that maximum likelihood minimizes the divergence from the empirical distribution; the unrestricted maximum likelihood estimate on a finite alphabet; the floor for models with context; the log-sum inequality; that merging outcomes cannot increase the divergence; convexity; additivity over independent pairs; the two-sided bound relating the divergence to chi-square and the bound $D \le \ln(1 + \chi^2)$; and the Fisher information limit for one parameter on a finite alphabet, in both orders of the arguments.

Proved on a linked page: Jensen's inequality (Probability Inequalities) and the law of large numbers (The Laws of Large Numbers).

Cited: the name of Gibbs' inequality and the proof by Jensen's inequality follow MacKay (2003, Section 2.6 and Exercise 2.26). The divergence carries the names of Kullback and Leibler (1951); nothing else in this article is drawn from that paper. Cover and Thomas (2006) is the standard textbook treatment. The use of the reverse direction in variational methods is from MacKay (2003, Chapter 33, Section 33.1). The quadratic form of the divergence for several parameters and for densities is stated on the linked pages and not proved here.

Computed on one text: every number about the Tiny Shakespeare file. The comparison of the two directions uses a family of uniform distributions on subsets, chosen because both minimizations can be done exactly; it illustrates the support conditions, which are proved, and makes no claim about other families.

Worked problems

These problems are posed for this article, on small exact cases and on the unit's text. The script tools/experiments/statistics/cross-entropy-and-kl-divergence.py checks every number.

Problem 1 (all three quantities by hand). Let $p = \left(\tfrac12, \tfrac14, \tfrac14\right)$ and let $u = \left(\tfrac13, \tfrac13, \tfrac13\right)$. Compute, in bits, $H(p)$, $H(p, u)$, $D(p \,\|\, u)$, $H(u, p)$ and $D(u \,\|\, p)$. Then let $r = \left(\tfrac12, \tfrac12, 0\right)$ and $s = \left(\tfrac14, \tfrac14, \tfrac12\right)$ and find $D(r \,\|\, s)$ and $D(s \,\|\, r)$.

Solution. $H(p) = \tfrac12\log_2 2 + \tfrac14\log_2 4 + \tfrac14\log_2 4 = 0.5 + 0.5 + 0.5 = 1.5$ bits. Under the uniform model every outcome has surprisal $\log_2 3 = 1.5850$ bits, so $H(p, u) = 1.5850$ and $D(p \,\|\, u) = 1.5850 - 1.5 = 0.0850$ bits. In the other order, the surprisals under $p$ are 1, 2 and 2 bits, each weighted by $\tfrac13$: $H(u, p) = \tfrac53 = 1.6667$ bits. The entropy of $u$ is 1.5850, so $D(u \,\|\, p) = 1.6667 - 1.5850 = 0.0817$ bits. The two divergences differ, 0.0850 against 0.0817.

For the second pair, $D(r \,\|\, s) = \tfrac12\log_2\frac{1/2}{1/4} + \tfrac12\log_2\frac{1/2}{1/4} + 0 = 1$ bit; the third outcome has $r = 0$ and contributes nothing, although $s$ puts half its probability there. In the other order the third term is $\tfrac12\log_2\frac{1/2}{0}$, which is $+\infty$: $D(s \,\|\, r) = \infty$. The model $r$ rules out an outcome that $s$ produces half the time.

Problem 2 (the loss of a model that has learned nothing). Show that a model that gives equal probability to every item of a vocabulary of size $V$ has loss $\ln V$ on every text. Evaluate it for the 65 characters of the walkthrough and for the 12,715 tokens of its byte-pair tokenizer. How does the walkthrough's untrained bigram model compare?

Solution. Every observation contributes $-\ln\frac1V = \ln V$, so the average is $\ln V$ whatever the observations are; in the notation above, $H(\hat{p}, u) = \ln V$ for every $\hat{p}$. For characters, $\ln 65 = 4.1744$ nats. For the tokenizer's vocabulary, $\ln 12{,}715 = 9.4505$ nats per token. The two are not comparable as they stand, because a token spans several characters; Perplexity and Source Coding treats the conversion.

By Gibbs' inequality, $\ln V = H(\hat{p}) + D(\hat{p} \,\|\, u)$, so the uniform model's loss exceeds the entropy of the data by its divergence from uniform, 0.8616 nats for the characters of the whole text. A training run whose loss starts near $\ln V$ has an output layer that begins near uniform. The walkthrough's bigram model does not: its untrained table of random logits scores about 4.66 nats, half a nat worse than uniform, as the bigram language model reports and explains. A model can be worse than knowing nothing, because confident wrong probabilities cost more than even ones.

Problem 3 (smoothing on held-out text). The bigram table fitted by counts on the training split is scored on the validation split, with add-one smoothing: $q(b \mid a) = \frac{\text{count}(ab) + 1}{\text{count}(a) + 65}$. Its loss is 2.4819 nats. Split that loss into the part no bigram table could avoid on the validation text and the part due to the model.

Solution. By the formula for models with context, the loss on the validation pairs is

$$H_{\text{val}}(X_2 \mid X_1) + \sum_a \hat{p}_{\text{val}}(a)\,D\big(\hat{p}_{\text{val}}(\cdot \mid a)\,\big\|\,q(\cdot \mid a)\big).$$

The first term is the conditional entropy of the validation text's own adjacent characters, the loss of the table fitted to the validation text itself. The script computes it from the 1,030 distinct pairs of the validation split: 2.3735 nats. The second term is the rest, $2.4819 - 2.3735 = 0.1084$ nats, and the script confirms it by computing the weighted divergences row by row. So the smoothed training table loses 0.1084 nats per character against the best possible bigram table for this validation text. Without smoothing the second term would be infinite, because of the 187 positions holding one of the 23 pairs the training split never contains.

One caution keeps the numbers honest. The 2.3735 nats is a floor for this validation text only, reached by a table fitted to it, which no model trained on other data could know.

Why the validation floor is lower than the training floor. The validation text's floor is 0.0784 nats below the training split's 2.4519. Two explanations suggest themselves, and the script tests both.

Fewer pairs. The experiment in Entropy shows conditional entropies computed from counts falling as the counts thin out, and the validation text has a ninth as many pairs. To measure that effect alone, the script draws 111,539 of the 1,003,853 training pairs at random, without replacement, 30 times (seeds 0 to 29). The floors of those samples have median 2.4468 nats, with interquartile range 2.4440 to 2.4483. Thinning the counts lowers the floor by about 0.0051 nats, a small part of the difference.

One continuous passage. The validation text is not a random sample of pairs. It is one stretch of the file. Cut the training split into nine consecutive windows, each as long as the validation text. Their floors range from 2.3723 to 2.4219 nats, with mean 2.3994. The validation text's 2.3735 lies within that range, near its low end: one of the nine windows is lower and eight are higher.

The difference between the two floors therefore splits into two named parts,

$$\underbrace{2.4519 - 2.3735}_{0.0784} = \underbrace{2.4519 - 2.3994}_{0.0525} + \underbrace{2.3994 - 2.3735}_{0.0260}.$$

The first part sets the whole training text against an average passage of it, and the second sets the average passage against this one. (Each figure is rounded separately, so the last digits do not add.) The second part is particular to the last tenth of the file, which is more predictable from its own counts than all but one of the nine training windows. Nothing here explains why. The first part can be analyzed.

The relation between the windows and the whole is exact. Let $J$ be the window a pair falls in. The floor of the pooled pairs is $H(X_2 \mid X_1)$, and the average of the nine window floors, which have equal weights, is $H(X_2 \mid X_1, J)$. Their difference is a conditional mutual information (Mutual Information):

$$H(X_2 \mid X_1) - H(X_2 \mid X_1, J) = I(X_2; J \mid X_1) \ge 0.$$

It is the amount that knowing which part of the text a pair comes from tells about the next character, beyond what the previous character tells. For the nine windows it is $2.4519 - 2.3994 = 0.0525$ nats. (The nine windows hold all the training pairs but the last two, and their pooled floor is 2.4519 to four places.) Part of any such difference is the counting effect again, because a mutual information computed from counts is positive even for a split that means nothing. When the same pairs are dealt into nine equal parts at random (30 partitions, seeds 0 to 29), the average floor of the parts has median 2.4466 nats, with interquartile range 2.4466 to 2.4467, a difference of 0.0053 nats from the pooled floor. The count of degrees of freedom in Mutual Information, applied within each previous character, anticipates nearly the same figure: a previous character with $s$ distinct successors contributes $(s - 1)(9 - 1)$ degrees of freedom, the 65 characters have 1,380 distinct pairs between them, and $8 \times (1{,}380 - 65)/(2 \times 1{,}003{,}851) = 0.0052$ nats.

Subtracting 0.0053 as an estimate of the counting part leaves about 0.0472 nats for position in the text. That figure is an estimate and not an exact split, because the bias of a mutual information computed from counts was measured for a split that means nothing and need not be the same for one that means something. What it measures is that each passage is more predictable from its own counts than from the counts of the whole. A likely reason, not tested here, is that passages differ in their speakers and names.

On this evidence, about 0.005 of the 0.0784 nats comes from the validation text being short. The rest comes from its being one passage (about 0.047) and from its being this particular passage (0.0260).

Problem 4 (two normal distributions with the same spread). For densities the divergence is defined with an integral in place of the sum, $D(f \,\|\, g) = \int f(x)\ln\frac{f(x)}{g(x)}\,dx$ (see Differential Entropy and the Gaussian). Find it for two normal densities with means $\mu_1$ and $\mu_2$ and the same standard deviation $\sigma$, and check the two values quoted in natural evolution strategies: means 1.0 and 1.2, with $\sigma = 1$ and with $\sigma = 0.1$.

Solution. $D = \dfrac{(\mu_1 - \mu_2)^2}{2\sigma^2}$ nats. The normalizing constants of the two densities are equal and cancel in the ratio, leaving

$$\ln\frac{f(x)}{g(x)} = \frac{(x - \mu_2)^2 - (x - \mu_1)^2}{2\sigma^2}.$$

The divergence is the expectation of this under $f$, that is, for $X$ normal with mean $\mu_1$ and variance $\sigma^2$. Then $E[(X - \mu_1)^2] = \sigma^2$, and $E[(X - \mu_2)^2] = \operatorname{Var}(X) + (\mu_1 - \mu_2)^2 = \sigma^2 + (\mu_1 - \mu_2)^2$, since the mean square about any point is the variance plus the squared distance from the mean to that point (Expectation, Variance and Covariance). So

$$D = \frac{\sigma^2 + (\mu_1 - \mu_2)^2 - \sigma^2}{2\sigma^2} = \frac{(\mu_1 - \mu_2)^2}{2\sigma^2}.$$

With means 1.0 and 1.2 the numerator is 0.04. For $\sigma = 1$, $D = 0.04/2 = 0.02$ nats. For $\sigma = 0.1$, $D = 0.04/0.02 = 2.00$ nats, a hundred times larger, as that article's figure states. This divergence happens to be symmetric in the two means. And it is exactly $\tfrac12 I(\mu)\,\delta^2$ with $\delta = \mu_1 - \mu_2$ and $I(\mu) = 1/\sigma^2$, the Fisher information of a normal mean. (The derivative of the log density with respect to $\mu$ is $(x - \mu)/\sigma^2$, whose mean square is $\sigma^2/\sigma^4$.) For this family the quadratic approximation of the last section is exact. The script checks the formula by numerical integration.

Problem 5 (the triangle inequality fails). For coins with probabilities of heads $a = 0.5$, $b = 0.25$ and $c = 0.1$, compute in bits the divergences $D(a \,\|\, b)$, $D(b \,\|\, c)$ and $D(a \,\|\, c)$, where $D(a \,\|\, b)$ stands for the divergence between the two-outcome distributions $(a, 1 - a)$ and $(b, 1 - b)$.

Solution. For two coins, $D(a \,\|\, b) = a\log_2\frac{a}{b} + (1 - a)\log_2\frac{1-a}{1-b}$.

  • $D(0.5 \,\|\, 0.25) = 0.5\log_2 2 + 0.5\log_2\frac{0.5}{0.75} = 0.5 - 0.2925 = 0.2075$.
  • $D(0.25 \,\|\, 0.1) = 0.25\log_2 2.5 + 0.75\log_2\frac{0.75}{0.9} = 0.3305 - 0.1973 = 0.1332$.
  • $D(0.5 \,\|\, 0.1) = 0.5\log_2 5 + 0.5\log_2\frac{0.5}{0.9} = 1.1610 - 0.4240 = 0.7370$.

The direct divergence, 0.7370 bits, is more than twice the sum of the two steps, $0.2075 + 0.1332 = 0.3407$ bits. Going through an intermediate model does not bound the direct divergence. The reason is visible in the quadratic approximation: for small differences the divergence behaves like a squared distance, $\tfrac12 I(\theta)\delta^2$, and squared distances do not satisfy the triangle inequality either. Two steps of size $\delta$ cost about $2 \times \tfrac12 I\delta^2$, and one step of size $2\delta$ costs about $\tfrac12 I(2\delta)^2 = 4 \times \tfrac12 I\delta^2$, twice as much. The three coins of this problem are not close to one another, so this is the reason in miniature and not a computation of the numbers above.

What we have learned

The cross-entropy $H(p, q)$ is the average surprisal of outcomes drawn from $p$ and predicted with $q$. It is the entropy of $p$ plus the Kullback–Leibler divergence $D(p \,\|\, q)$, and Gibbs' inequality says the divergence is never negative and is zero only for $q = p$. The loss reported when a model is trained or evaluated is a cross-entropy with the data's empirical distribution in the first place, so minimizing it is maximum likelihood, and its floor is an entropy: 3.3128 nats for single characters of the Tiny Shakespeare text, 2.4519 nats for a bigram table on the training split. The divergence is not a distance. It is asymmetric, the forward direction forces a model to cover everything the data can produce, and the reverse direction lets an approximation ignore part of its target. For nearby distributions it is half a chi-square, and its curvature is the Fisher information.

In Entropy, the amount by which conditioning lowers entropy turned out to be a divergence between a joint distribution and the product of its marginals. Mutual Information takes that divergence as its subject: how much one variable tells about another.

References

  • Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory, 2nd edition. Wiley. record · 8 pages
  • Kullback, S., and Leibler, R. A. (1951). On information and sufficiency. The Annals of Mathematical Statistics, 22(1), 79–86. record · 2 pages
  • MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Section 2.6, "Gibbs' inequality"; Exercise 2.26 and its solution; Chapter 33, "Variational Methods". record · 5 pages