F-divergence explained

In probability theory, an

f -divergence is a certain type of function D _{f(P\|} Q) that measures the difference between two probability distributions P and Q . Many common divergences, such as KL-divergence, Hellinger distance, and total variation distance, are special cases of f -divergence.

History

These divergences were introduced by Alfréd Rényi^[1] in the same paper where he introduced the well-known Rényi entropy. He proved that these divergences decrease in Markov processes. f-divergences were studied further independently by, and and are sometimes known as Csiszár

f -divergences, Csiszár–Morimoto divergences, or Ali–Silvey distances.

Definition

Non-singular case

Let

P and Q be two probability distributions over a space \Omega , such that P\ll Q , that is, P is absolutely continuous with respect to Q . Then, for a convex function f: [ 0 , +inf ty)\to( -inf ty, +inf ty] such that f(x) is finite for all x > 0 , f( 1 ) =0 , and f( 0 ) = \lim _{t\to 0 ^{+}} f(t) (which could be infinite), the f -divergence of P from Q is defined asD _{f(P\parallel} Q) \equiv \int _{\Omega} f\left( (dP)/(dQ) \right)dQ.

We call

f the generator of D _{f} .

In concrete applications, there is usually a reference distribution

\mu on \Omega (for example, when \Omega = \R ^{n} , the reference distribution is the Lebesgue measure), such that P, Q \ll \mu , then we can use Radon–Nikodym theorem to take their probability densities p and q , giving D _{f(P\parallel} Q) = \int _{\Omega} f\left( (p(x))/(q(x)) \right)q(x)d\mu(x).

When there is no such reference distribution ready at hand, we can simply define

\mu = P + Q , and proceed as above. This is a useful technique in more abstract proofs.

The above definition can be extended to cases where

P\ll Q is no longer satisfied (Definition 7.1 of ^[2]).

Since

f is convex, and f( 1 ) = 0 , the function (f(x))/(x -1) must nondecrease, so there exists f'( inf ty) : = \lim _{x\toinfty} f(x)/x , taking value in ( -inf ty, +inf ty] .

Since for any

p(x)> 0 , we have \lim _{q(x)\to} q(x)f \left( (p(x))/(q(x)) \right) = p(x)f'( inf ty) , we can extend f-divergence to the P\not\ll Q .

Properties

Basic relations between f-divergences

• Linearity:

D _{\sum _{i} a _{i} f _{i}} = \sum _{i} a _{i} D _{f _{i}} given a finite sequence of nonnegative real numbers a _{i} and generators f _{i} .D _{f} = D _{g} iff f(x) = g(x) + c(x -1 ) for some c\in \R .

Basic properties of f-divergences

In particular, the monotonicity implies that if a Markov process has a positive equilibrium probability distribution

P ^{*} then D _{f(P(t)\parallel} P ^{*)} is a monotonic (non-increasing) function of time, where the probability distribution P(t) is a solution of the Kolmogorov forward equations (or Master equation), used to describe the time evolution of the probability distribution in the Markov process. This means that all f-divergences D _{f(P(t)\parallel} P ^{*)} are the Lyapunov functions of the Kolmogorov forward equations. The converse statement is also true: If H(P) is a Lyapunov function for all Markov chains with positive equilibrium P ^{*} and is of the trace-form(H(P) = \sum _{i} f(P _{i} ,P ^{*} _{i} ) ) then H(P) = D _{f(P(t)\parallel} P ^{*)} , for some convex function f.^{[3] [4]} For example, Bregman divergences in general do not have such property and can increase in Markov processes.^[5]

Analytic properties

The f-divergences can be expressed using Taylor series and rewritten using a weighted sum of chi-type distances .

Naive variational representation

Let

f ^{*} be the convex conjugate of f . Let effdom (f ^{*)} be the effective domain of f ^{*} , that is, effdom (f ^{*)} = \{y : f ^{*(y)} < inf ty\} . Then we have two variational representations of D _{f} , which we describe below.

Basic variational representation

Under the above setup,

This is Theorem 7.24 in.

Example applications

Using this theorem on total variation distance, with generator

f(x) = (1)/(2) |x -1 |, its convex conjugate is f ^{*(x} ^{*)} = \begin{cases} x ^{*} on [ -1 / 2 , 1 / 2 ],\\ +inf ty else. \end{cases} , and we obtain$$TV(P\backslash |\; Q)\; =\; \backslash sup\_$$

\leq 1/2

E_P[g(X)] - E_Q[g(X)].For chi-squared divergence, defined by f(x) = (x -1 ) ^{2,} f ^{*(y)} = y ^{2/4} + y , we obtain$$\backslash chi^2(P;\; Q)\; =\; \backslash sup\_g\; E\_P[g(X)]\; -\; E\_Q[g(X)^2/4\; +\; g(X)].$$Since the variation term is not affine-invariant in g , even though the domain over which g varies is affine-invariant, we can use up the affine-invariance to obtain a leaner expression.

Replacing

g by a g + b and taking the maximum over a, b \in \R , we obtain$$\backslash chi^2(P;\; Q)\; =\; \backslash sup\_g\; \backslash frac,$$which is just a few steps away from the Hammersley–Chapman–Robbins bound and the Cramér–Rao bound (Theorem 29.1 and its corollary in).

For

\alpha -divergence with \alpha \in ( -inf ty, 0 )\cup( 0 , 1 ) , we have f _{\alpha(x)} = (x ^{\alpha} - \alpha x - ( 1- \alpha))/(\alpha(\alpha -1 )) , with range x\in [ 0 , inf ty) . Its convex conjugate is f ^{*(y) = (1)/(\alpha)} _{\alpha} (x(y) ^{\alpha} - 1 ) with range y\in( -inf ty, ( 1- \alpha) ^{-1} ) , where x(y) = ((\alpha -1 )y + 1 ) ^{(1)/(\alpha -1)} .

Applying this theorem yields, after substitution with

h = ((\alpha -1 )g +1 ) ^{(1)/(\alpha -1)} ,$$D\_\backslash alpha(P\backslash |\; Q)\; =\; \backslash frac\; -\; \backslash inf\_\backslash left(E\_Q\backslash left[\backslash frac\{h^\backslash alpha\}\{\backslash alpha\}\backslash right]\; +\; E\_P\backslash left[\backslash frac\{h^\{\backslash alpha-1\}\}\{1-\backslash alpha\}\backslash right]\; \backslash right),$$or, releasing the constraint on h ,$$D\_\backslash alpha(P\backslash |\; Q)\; =\; \backslash frac\; -\; \backslash inf\_\backslash left(E\_Q\backslash left[\backslash frac\{|h|^\backslash alpha\}\{\backslash alpha\}\backslash right]\; +\; E\_P\backslash left[\backslash frac\{|h|^\{\backslash alpha-1\}\}\{1-\backslash alpha\}\backslash right]\; \backslash right).$$Setting \alpha =-1 yields the variational representation of \chi ^{2} -divergence obtained above.

The domain over which

h varies is not affine-invariant in general, unlike the \chi ^{2} -divergence case. The \chi ^{2} -divergence is special, since in that case, we can remove the | ⋅ | from |h| .

For general

\alpha \in ( -inf ty, 0 )\cup( 0 , 1 ) , the domain over which h varies is merely scale invariant. Similar to above, we can replace h by a h , and take minimum over a> 0 to obtain$$D\_\backslash alpha(P\backslash |\; Q)\; =\; \backslash sup\_\; \backslash left[\backslash frac\{1\}\{\backslash alpha(1-\backslash alpha)\}\; \backslash left(1-\backslash frac\{E\_P[h^\{\backslash alpha-1\}]^\backslash alpha\}\backslash right)\; \backslash right].$$Setting \alpha = (1)/(2) , and performing another substitution by g = \sqrt h , yields two variational representations of the squared Hellinger distance:$$H^2(P\backslash |Q)\; =\; \backslash frac\; 1\; 2\; D\_(P\backslash |\; Q)\; =\; 2\; -\; \backslash inf\_\backslash left(E\_Q\backslash left[h(X)\backslash right]\; +\; E\_P\backslash left[h(X)^\{-1\}\backslash right]\; \backslash right),$$$$H^2(P\backslash |Q)\; =\; 2\; \backslash sup\_\; \backslash left(1-\backslash sqrt\backslash right).$$Applying this theorem to the KL-divergence, defined by f(x) = x ln x, f ^{*(y)} = e ^{y-1} , yields$$D\_(P;\; Q)\; =\backslash sup\_g\; E\_P[g(X)]\; -\; e^E\_Q[e^\{g(X)\}].$$This is strictly less efficient than the Donsker–Varadhan representation$$D\_(P;\; Q)\; =\; \backslash sup\_g\; E\_P[g(X)]-\; \backslash ln\; E\_Q[e^\{g(X)\}].$$This defect is fixed by the next theorem.

Improved variational representation

Assume the setup in the beginning of this section ("Variational representations").

This is Theorem 7.25 in.

Example applications

Applying this theorem to KL-divergence yields the Donsker–Varadhan representation.

Attempting to apply this theorem to the general

\alpha -divergence with \alpha \in ( -inf ty, 0 )\cup( 0 , 1 ) does not yield a closed-form solution.

Common examples of f-divergences

The following table lists many of the common divergences between probability distributions and the possible generating functions to which they correspond. Notably, except for total variation distance, all others are special cases of

\alpha -divergence, or linear sums of \alpha -divergences.

For each f-divergence

D _{f} , its generating function is not uniquely defined, but only up to c ⋅ (t -1 ) , where c is any real constant. That is, for any f that generates an f-divergence, we have D _{f(t)} = D _{f(t)} . This freedom is not only convenient, but actually necessary.

Divergence	Corresponding f(t)	Discrete Form
\chi ^{\alpha} -divergence, \alpha \ge 1	(12)/()	t - 1	^ \,	(12)/(\sum) _{i} \left	\frac\right	^\alpha q_i \,
Total variation distance (\alpha = 1 )	(12)/()	t - 1	\,	(12)/(\sum) _{i}	p_i - q_i	\,
α-divergence	\begin{cases} (t ^{\alpha} - \alpha t - \left( 1- \alpha \right))/(\alpha \left(\alpha -1 \right)) & if \alpha ≠ 0 , \alpha ≠ 1 , \\ t ln t - t +1 , & if \alpha =1 , \\ - ln t + t -1 , & if \alpha =0 \end{cases}
KL-divergence (\alpha =1 )	t ln t	\sum _{i} p _{i} ln (p _{i})/(q _{i})
reverse KL-divergence (\alpha =0 )	- ln t	\sum _{i} q _{i} ln (q _{i})/(p _{i})
Jensen–Shannon divergence	(1)/(2) \left(t ln t - (t + 1 ) ln \left( (t +1)/(2) \right)\right)	(1)/(2) \sum _{i} \left( p _{i} ln (p _{i})/((p _{i} + q _{i)/2}) + q _{i} ln (q _{i})/((p _{i} + q _{i)/2}) \right)
Jeffrey's divergence (KL + reverse KL)	(t - 1 ) ln (t)	\sum _{i} (p _{i} - q _{i)} ln (p _{i})/(q _{i})
squared Hellinger distance (\alpha = (1)/(2) )	(1)/(2) (\sqrt{t} - 1 ) ^{2,1-\sqrt{t}}	(1)/(2) \sum _{i} (\sqrt{p _{i}} - \sqrt{q ^{2 ;} _{i})} 1 - \sum _{i} \sqrt{p _{i} q _{i}}
Pearson \chi ^{2} -divergence (rescaling of \alpha =2 )	(t - 1 ) ^{2,t} ^{2} -1 ,t ^{2} - t	\sum _{i} ((p _{i} - q ^{2} _{i)})/(q _{i})
Neyman \chi ^{2} -divergence (reverse Pearson)(rescaling of \alpha =-1 )	(1 t -1 , (1 t - t)/())/()	2 + \sum _{i} ((p _{i} - q ^{2} _{i)})/(p _{i})

Let f _{\alpha} be the generator of \alpha -divergence, then f _{\alpha} and f _{1-\alpha} are convex inversions of each other, so D _{\alpha} (P\| Q) = D _{1-\alpha} (Q\| P) . In particular, this shows that the squared Hellinger distance and Jensen-Shannon divergence are symmetric.

In the literature, the

\alpha -divergences are sometimes parametrized as\begin{cases} (4)/(1- \alpha ^{2}) ( 1 - t ^{(1+\alpha)/2} ) , & if \alpha ≠ \pm 1 , \\ t ln t, & if \alpha =1 , \\ - ln t, & if \alpha =-1 \end{cases}

which is equivalent to the parametrization in this page by substituting

\alpha \leftarrow (\alpha +1)/(2) .

Relations to other statistical divergences

Here, we compare f-divergences with other statistical divergences.

Rényi divergence

The Rényi divergences is a family of divergences defined by

R _{\alpha} (P \| Q) = (1)/(\alpha -1) log ( E _{Q\left[\left( (dP)/(dQ)} \right) ^{\alpha\right] )}

when

\alpha \in ( 0 , 1 )\cup ( 1 , +inf ty) . It is extended to the cases of \alpha =0 , 1 , +inf ty by taking the limit.

Simple algebra shows that

R _{\alpha(P\|} Q) = (1)/(\alpha -1) ln ( 1+ \alpha(\alpha -1 )D _{\alpha(P\|Q))} , where D _{\alpha} is the \alpha -divergence defined above.

Bregman divergence

The only f-divergence that is also a Bregman divergence is the KL divergence.^[6]

Integral probability metrics

The only f-divergence that is also an integral probability metric is the total variation.^[7]

Financial interpretation

A pair of probability distributions can be viewed as a game of chance in which one of the distributions defines the official odds and the other contains the actual probabilities. Knowledge of the actual probabilities allows a player to profit from the game. For a large class of rational players the expected profit rate has the same general form as the ƒ-divergence.^[8]

See also

• Kullback–Leibler divergence
• Bregman divergence

References

• I. . Csiszár . 1963 . Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizitat von Markoffschen Ketten . Magyar. Tud. Akad. Mat. Kutato Int. Kozl . 8 . 85–108 .
• 10.1143/JPSJ.18.328 . T. . Morimoto . 1963 . Markov processes and the H-theorem . J. Phys. Soc. Jpn. . 18 . 3 . 328–331 . 1963JPSJ...18..328M .
• S. M. . Ali . S. D. . Silvey . 1966 . A general class of coefficients of divergence of one distribution from another . Journal of the Royal Statistical Society, Series B . 28 . 1 . 131–142 . 2984279 . 0196777 .
• I. . Csiszár . 1967 . Information-type measures of difference of probability distributions and indirect observation . Studia Scientiarum Mathematicarum Hungarica . 2 . 229–318 . CITEREFCsisz.C3.A1r1967 .
• I. . Csiszár . Imre Csiszár . P. . Shields . 2004 . Information Theory and Statistics: A Tutorial . Foundations and Trends in Communications and Information Theory . 1 . 4 . 417–528 . 10.1561/0100000004 . 2009-04-08 .
• F. . Liese . I. . Vajda . 2006 . On divergences and informations in statistics and information theory . . 52 . 10 . 4394–4412 . 10.1109/TIT.2006.881731 . 2720215 .
• F. . Nielsen . R. . Nock . 2013 . On the Chi square and higher-order Chi distances for approximating f-divergences . 1309.3029 . 10.1109/LSP.2013.2288355 . 21 . IEEE Signal Processing Letters . 1 . 10–13 . 2014ISPL...21...10N. 4152365 .
• J-F. . Coeurjolly . R. . Drouilhet . 2006 . Normalized information-based divergences . math/0604246 . arXiv:math/0604246 .

Notes and References

1. On measures of entropy and information. Alfréd. Rényi . 1961. The 4th Berkeley Symposium on Mathematics, Statistics and Probability, 1960. University of California Press. Berkeley, CA. 547–561. Eq. (4.20)
2. Book: Polyanskiy . Yury . Information Theory: From Coding to Learning (draft of October 20, 2022) . Yihong . Wu . Cambridge University Press . 2022 . https://web.archive.org/web/20230201222557/https://people.lids.mit.edu/yp/homepage/data/itbook-export.pdf . 2023-02-01.
3. Gorban. Pavel A.. 15 October 2003. Monotonically equivalent entropies and solution of additivity equation. Physica A. 328. 3–4 . 380–390. 10.1016/S0378-4371(03)00578-8 . cond-mat/0304131. 2003PhyA..328..380G. 14975501.
4. Divergence, Optimization, Geometry. Shun'ichi . Amari . Shun'ichi Amari . 2009. The 16th International Conference on Neural Information Processing (ICONIP 20009), Bangkok, Thailand, 1--5 December 2009 . Leung, C.S. . Lee, M. . Chan, J.H.. Lecture Notes in Computer Science, vol 5863 . Springer . Berlin, Heidelberg . 185–193 . 10.1007/978-3-642-10677-4_21 .
5. Gorban. Alexander N.. 29 April 2014. General H-theorem and Entropies that Violate the Second Law. Entropy. 16. 5. 2408–2432. 10.3390/e16052408. 1212.6767. 2014Entrp..16.2408G. free.
6. Jiao . Jiantao . Courtade . Thomas . No . Albert . Venkat . Kartik . Weissman . Tsachy . December 2014 . Information Measures: the Curious Case of the Binary Alphabet . IEEE Transactions on Information Theory . 60 . 12 . 7616–7626 . 10.1109/TIT.2014.2360184 . 0018-9448. 1404.6810 . 13108908 .
7. 0901.2698 . Sriperumbudur . Bharath K. . Fukumizu . Kenji . Gretton . Arthur . Schölkopf . Bernhard . Bernhard Schölkopf . Lanckriet . Gert R. G. . On integral probability metrics, φ-divergences and binary classification . 2009 . cs.IT .
8. Soklakov. Andrei N.. 2020. Economics of Disagreement—Financial Intuition for the Rényi Divergence. Entropy. 22. 8. 860. 10.3390/e22080860. 33286632. 7517462. 1811.08308. 2020Entrp..22..860S. free.