Kullback-Leibler divergence ($D_{\mathrm{KL}}(P\Vert Q)$)

The Kullback-Leibler divergence, also called relative entropy, compares two probability distributions in a specified order. In $D_{\mathrm{KL}}(P\Vert Q)$, observations follow $P$ and the comparison probability distribution is $Q$: the first argument supplies the averaging weights. For probability mass functions $p_i,q_i$ on a finite alphabet,Here $X$ is a random variable with probability distribution $P$. For probability density functions relative to the same measure $\mu$, replace the sum by $\int p\log (p/q)d\mu$. These formulas use natural logarithms unless stated otherwise. The expected value is under $P$, even though $Q$ appears in the denominator. ^[ref]

Take $P=(0.75,0.25)$ and $Q=(0.5,0.5)$ on two outcomes. Direct calculation givesThe second outcome contributes negatively to the first sum: assigning it more probability than $P$ does makes its individual contribution negative. Nevertheless, relative entropy nonnegativity guarantees a nonnegative total. Reversing the arguments changes both the likelihood ratio and the averaging probabilities; taking an absolute value inside the logarithm would define a different quantity.

The units depend on the logarithm: natural logarithms give nats, whereas base-two logarithms give bits. Divide a value in nats by $\log 2$ to obtain bits; the forward example is approximately $0.188722$ bits. Changing the base rescales every Kullback-Leibler divergence by the same positive factor. Since the two calculated directions differ, Kullback-Leibler divergence is asymmetric and cannot be a metric. It also need not satisfy the triangle inequality. ^[ref]

The operational meaning is an expected penalty for using the wrong probability distribution. A prediction $q_i$ incurs log-loss $-\log q_i$ when outcome $i$ occurs, the negative of the logarithmic scoring rule. Under $P$, its expected value is the cross-entropy $H(P,Q)=-{\sum }_i{p}_i\log q_i$. Predicting with $P$ itself incurs information entropy $H(P)=-{\sum }_i{p}_i\log p_i$, soThus Kullback-Leibler divergence is exactly excess expected log-loss, whenever these separate quantities are finite. ^[ref]

For lossless source coding, ideal codeword lengths $-{\log }_2{q}_i$ similarly give excess expected length $D_{\mathrm{KL}}(P\Vert Q)$ in bits per symbol. Actual prefix codes require integer codeword lengths; Shannon's source coding theorem explains how long blocks approach ideal per-symbol lengths. The interpretation concerns an average, not a fractional physical bit attached to every outcome. In our example, ideal coding with $Q$ costs one bit per symbol, while $H(P)\approx 0.811278$ bits; the difference is exactly the computed $0.188722$ bits. ^[ref]

Zeros require explicit conventions. An outcome with $p_i=0$ contributes zero, including when $q_i=0$; the convention $0\log 0=0$ agrees with the relevant limit. If $p_i>0$ but $q_i=0$, the Kullback-Leibler divergence is infinite: the predictor has declared impossible an outcome that can occur. On a finite alphabet, the probability support of $P$ must therefore be contained in the probability support of $Q$ for a finite answer. For example, $P=(1,0)$ and $Q=(0.5,0.5)$ give $D(P\Vert Q)=\log 2$, but $D(Q\Vert P)=+\infty$. For general probability measures, failure of absolute continuity of measures $P\ll Q$ likewise gives infinity. Even $P\ll Q$ does not guarantee a finite integral. ^[ref]

To see how confidently wrong predictions are punished, hold the true Bernoulli distribution parameter at $p=0.75$ and vary the predicted parameter $q$. Its binary relative entropy isIt vanishes at $q=0.75$, equals approximately $2.894055$ nats at $q=0.01$, and equals $0.596495$ nats at $q=0.99$. Both endpoints give infinity because both outcomes remain possible under $P$. Predicting almost no successes is especially costly because successes actually occur three quarters of the time. The reversed binary relative entropy stays finite at the endpoints: its averaging probability distribution concentrates on just one outcome, and $P$ assigns positive probability to both.

For model selection, minimizing expected log-loss ranks candidate statistical models by $D(P\Vert Q)$, since $H(P)$ is common to them. The true probability distribution is usually unknown, so one estimates predictive performance using fresh observations or cross-validation. Fitting and assessing on the same data can reward overfitting; a small fitted Kullback-Leibler divergence alone does not establish useful prediction.

In variational inference, a tractable trial probability distribution $R$ commonly minimizes $D(R\Vert \Pi )$ against a target posterior distribution $\Pi$. Maximizing the evidence lower bound accomplishes this without evaluating the target's normalization constant. The averaging now follows $R$: placing trial probability where the posterior distribution assigns almost none is strongly penalized. The chosen direction and trial family therefore matter. ^[ref]

These comparisons do not by themselves establish causal inference. Two statistical models can reproduce the same observed probability distribution while predicting different responses to an intervention. Choosing the smaller Kullback-Leibler divergence therefore needs additional assumptions or experimental evidence before supporting a causal claim. ^[ref]

The original reference is S. Kullback and R. A. Leibler's 1951 paper ^[ref], published in The Annals of Mathematical Statistics 22(1), pages 79–86. Its title connects this comparison with sufficient statistics: the historical setting was statistical information, before today's widespread applications in prediction and variational inference.

Let $Q$ be a random probability mass function on a finite alphabet, let $p=\mathbb{E}Q$, and suppose a fixed reference $r$ is positive on the probability support of $p$. Then $Q$ vanishes almost surely wherever $p=0$, andTaking expected values yields the displayed decomposition. In particular it applies to an unbiased empirical distribution. It separates sampling fluctuation from reference mismatch: even perfect recovery of $p$ leaves the deterministic relative entropy $D(p\Vert r)$. A bound comparing different references must account for this term.

For a fixed probability mass function $p$ on a finite alphabet, relative entropy is a convex function of its first probability mass function. For $p_i>0$, the coordinate function $f_i(t)=t{\log }_2(t/p_i)$ has $f_i^{\prime \prime }(t)=1/(t\ln 2)>0$ on $(0,\infty )$ and extends continuously with $f_i(0)=0$. Applying scalar convexity coordinate by coordinate proves the inequality. If $p_i=0$, finite relative entropy requires $q_i=r_i=0$ for every positive-weight constituent; otherwise the right side is infinite. Thus the assertion also holds as an extended-valued convexity statement. On the probability simplex supported where $p>0$, the function is strictly convex: two distinct probability mass functions give a strict inequality for $0<\lambda <1$.

For a measurable event $A$, applying Jensen inequality to $u\log u$ separately on $A$ and its complement shows that the Kullback-Leibler divergence between two probability measures is at least the divergence between the two event indicators. This reduces a general probability measure comparison to a binary one and is the key step in a proof of Pinsker's inequality.

For $d(a,b)=a\log (a/b)+(1-a)\log ((1-a)/(1-b))$, the second derivative with respect to $a$ is $1/[a(1-a)]\ge 4$. Its value and first derivative at $a=b$ vanish, so $d(a,b)\ge 2(a-b{)}^2$. Boundary values follow by continuity or the infinite-divergence convention. Together with the binary partition bound for relative entropy, this gives Pinsker's inequality with the natural-logarithm constant.

For sufficiently regular positive probability densities, this compares their spatial logarithmic derivatives. It is the dissipation functional for relative entropy under suitable diffusion equations. For standard Gaussian $g=\gamma$, it becomes $\int |\nabla \log f+v{|}^{2}f$, and in one dimension equals $\int |f^{\prime }{|}^2/f+\int v^{2}f-2$ at unit mass.

The differential estimate $I^{\prime }(t)\le -2I(t)$ gives the displayed exponential bound by an integrating factor. Start at any time with finite information. Combining this with a zero limiting entropy yields $H(f_t\mid \gamma )={\int }_t^{\infty }I(s)ds\le I(t)/2$.

For probability distributions $P,Q$, relative entropy satisfies $D_{\mathrm{KL}}(P\Vert Q)\ge 0$, with equality exactly when $P=Q$. Thus truthful prediction uniquely minimizes expected log-loss whenever the comparison is well defined, explaining the strictly proper scoring rule property of the logarithmic scoring rule.

For a short proof with probability density functions $f,g$ and $g>0$, set $r=f/g$. Their integrals both equal one, givingThe strictly convex function $r\log r-r+1$ is minimized only at $r=1$, so equality means $f=g$ almost everywhere. Its value at zero is one by $0\log 0=0$. Where $g=0<f$, relative entropy is infinite; where both vanish, the contribution is zero. These conventions extend the argument beyond positive reference probability density functions.

For nonnegative densities of possibly different total masses, this divergence includes the mass correction $-x+y$ as well as the logarithmic term. It is the Bregman distance of the maximum-entropy regularization functional at a positive reference $y$. Convexity of $s\log s-s$ proves nonnegativity. For equal masses the correction integrates to zero, recovering the Kullback-Leibler divergence; for probability density functions both masses are one. Use the usual extended-value conventions at zero reference density.

For probability mass functions $P,Q,R$ with compatible supports,When the final term vanishes, this is the Pythagorean identity for relative entropy.

The Pythagorean identity iswhenever the residual term in the three-point identity for relative entropy is zero. Convex information projections replace equality by the corresponding Pythagorean inequality.

The binary relative entropy is the Kullback-Leibler divergence between Bernoulli distributions:It is the exact exponent obtained by optimizing the Chernoff bound for a Bernoulli mean.

For probability distributions $p$ and $q$ on the same finite set,with equality exactly when $p=q$ on the support of $p$.

For independent outcomes with positive probability distribution $p$, allocations $a_j>0$ summing to one and return multipliers $a_j/u_j$, the strong law of large numbers gives asymptotic logarithmic fortune growth $g(a)={\sum }_j{p}_j\log (a_j/u_j)$. Gibbs inequality gives $g(a)=g(p)-D(p\Vert a)$, so the unique optimum is $a=p$. Writing $U={\sum }_j{u}_j$ gives $g(p)=D(p\Vert u/U)-\log U$. Thus $U<1$ guarantees positive optimal growth, whereas $U>1$ allows the house to force negative growth by choosing $u_j=U{p}_j$, but does not guarantee decline for every choice of $u$.

For probability distributions $P$ and $Q$ on a product space, the Kullback-Leibler divergence decomposes into the divergence of a marginal and the expected divergence of the corresponding conditional distributions. Iteration gives

For nonnegative $a_i,b_i$, with $a={\sum }_i{a}_i$ and $b={\sum }_i{b}_i$, the log-sum inequality isIt proves both Gibbs inequality and the data processing inequality for relative entropy.

For a probability mass function $Q$ of full support on a finite alphabet and a real function $g$,where $D_e$ uses natural logarithms. The unique maximizing probability mass function is the exponential tilt $P^{\ast }(x)=Q(x)e^{g(x)}/{\mathbb{E}}_Q{e}^g$.

For univariate normal distributions,

If $P={⨂}_{i=1}^n{P}_i$ is a product measure, $Q$ is any probability measure, and $X^{(i)}$ omits coordinate $i$, then

For a random vector $X_{1:n}$,This is equivalent to Han's inequality for relative entropy after expansion against a product reference measure.

For a discrete random vector with $n$ coordinates, this is the average information entropy per coordinate over all subsets of size $k$. Independent coordinates give the same average for every $k$, even when their individual entropies differ. If all coordinates are copies of one random variable $Z$, the average is $h(Z)/k$.

For discrete random variables, normalized subset entropy decreases with subset size. For finite entropies, the chain rule for information entropy and conditioning reduces entropy give ${\sum }_{i\in S}h(X_{S\setminus \{i\}})\ge (|S|-1)h(X_S)$. Sum this over all $k$-subsets $S$. Every $(k-1)$-subset occurs $n-k+1$ times, and $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=(n-k+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ cancels the normalization factors. This proves $h_k^{(n)}\le h_{k-1}^{(n)}$. If a marginal entropy is infinite, every one of these subset averages is infinite; otherwise all entropies used in the proof are finite.

The strong formfollows by iterating entropy submodularity.

For a product reference $P={⨂}_i{P}_i$ and arbitrary $Q$,It follows from the chain rule for relative entropy and convexity of relative entropy in its first argument.