Divergence (statistics)

In information geometry, a divergence is a kind of statistical distance: a binary function which establishes the separation from one probability distribution to another on a statistical manifold.

The simplest divergence is squared Euclidean distance (SED), and divergences can be viewed as generalizations of SED. The other most important divergence is relative entropy (also called Kullback–Leibler divergence), which is central to information theory. There are numerous other specific divergences and classes of divergences, notably f-divergences and Bregman divergences (see Template:Slink).

Definition

Given a differentiable manifoldTemplate:Efn $M$ of dimension $n$, a divergence on $M$ is a $C^2$-function $D:M\times M\to [0,\mathrm{\infty })$ satisfying:Template:SfnTemplate:Sfn

1. $D(p,q)\ge 0$ for all $p,q\in M$ (non-negativity),
2. $D(p,q)=0$ if and only if $p=q$ (positivity),
3. At every point $p\in M$, $D(p,p+dp)$ is a positive-definite quadratic form for infinitesimal displacements $dp$ from $p$.

In applications to statistics, the manifold $M$ is typically the space of parameters of a parametric family of probability distributions.

Condition 3 means that $D$ defines an inner product on the tangent space $T_{p}M$ for every $p\in M$. Since $D$ is $C^2$ on $M$, this defines a Riemannian metric $g$ on $M$.

Locally at $p\in M$, we may construct a local coordinate chart with coordinates $x$, then the divergence is $$D(x(p),x(p)+dx)=\frac{1}{2}d{x}^T{g}_p(x)dx+O(|dx{|}^3)$$where $g_p(x)$ is a matrix of size $n\times n$. It is the Riemannian metric at point $p$ expressed in coordinates $x$.

Dimensional analysis of condition 3 shows that divergence has the dimension of squared distance.Template:Sfn

The dual divergence $D^{*}$ is defined as

$D^{*}(p,q)=D(q,p).$

When we wish to contrast $D$ against $D^{*}$, we refer to $D$ as primal divergence.

Given any divergence $D$, its symmetrized version is obtained by averaging it with its dual divergence:Template:Sfn

$D_S(p,q)=\frac{1}{2}(D(p,q)+D(q,p)).$

Difference from other similar concepts

Unlike metrics, divergences are not required to be symmetric, and the asymmetry is important in applications.Template:Sfn Accordingly, one often refers asymmetrically to the divergence "of q from p" or "from p to q", rather than "between p and q". Secondly, divergences generalize squared distance, not linear distance, and thus do not satisfy the triangle inequality, but some divergences (such as the Bregman divergence) do satisfy generalizations of the Pythagorean theorem.

In general statistics and probability, "divergence" generally refers to any kind of function $D(p,q)$, where $p,q$ are probability distributions or other objects under consideration, such that conditions 1, 2 are satisfied. Condition 3 is required for "divergence" as used in information geometry.

As an example, the total variation distance, a commonly used statistical divergence, does not satisfy condition 3.

Notation

Notation for divergences varies significantly between fields, though there are some conventions.

Divergences are generally notated with an uppercase 'D', as in $D(x,y)$, to distinguish them from metric distances, which are notated with a lowercase 'd'. When multiple divergences are in use, they are commonly distinguished with subscripts, as in $D_{\text{KL}}$ for Kullback–Leibler divergence (KL divergence).

Often a different separator between parameters is used, particularly to emphasize the asymmetry. In information theory, a double bar is commonly used: $D(p\parallel q)$; this is similar to, but distinct from, the notation for conditional probability, $P(A|B)$, and emphasizes interpreting the divergence as a relative measurement, as in relative entropy; this notation is common for the KL divergence. A colon may be used instead,Template:Efn as $D(p:q)$; this emphasizes the relative information supporting the two distributions.

The notation for parameters varies as well. Uppercase $P,Q$ interprets the parameters as probability distributions, while lowercase $p,q$ or $x,y$ interprets them geometrically as points in a space, and ${\mu }_1,{\mu }_2$ or $m_1,m_2$ interprets them as measures.

Geometrical properties

Template:Further Many properties of divergences can be derived if we restrict S to be a statistical manifold, meaning that it can be parametrized with a finite-dimensional coordinate system θ, so that for a distribution Template:Nowrap we can write Template:Nowrap.

For a pair of points Template:Nowrap with coordinates θ_p and θ_q, denote the partial derivatives of D(p, q) as

$\begin{array}{cc}D(({\partial }_i{)}_p,q)& \stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{\partial }{\partial {\theta }_p^i}D(p,q),\\ D(({\partial }_i{\partial }_j{)}_p,({\partial }_k{)}_q)& \stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{\partial }{\partial {\theta }_p^i}\frac{\partial }{\partial {\theta }_p^j}\frac{\partial }{\partial {\theta }_q^k}D(p,q),\mathrm{e}\mathrm{t}\mathrm{c}\mathrm{.}\end{array}$

Now we restrict these functions to a diagonal Template:Nowrap, and denote

$\begin{array}{cc}D[{\partial }_i,\cdot ]& :p\mapsto D(({\partial }_i{)}_p,p),\\ D[{\partial }_i,{\partial }_j]& :p\mapsto D(({\partial }_i{)}_p,({\partial }_j{)}_p),\mathrm{e}\mathrm{t}\mathrm{c}\mathrm{.}\end{array}$

By definition, the function D(p, q) is minimized at Template:Nowrap, and therefore

$\begin{array}{cc}& D[{\partial }_i,\cdot ]=D[\cdot ,{\partial }_i]=0,\\ & D[{\partial }_i{\partial }_j,\cdot ]=D[\cdot ,{\partial }_i{\partial }_j]=-D[{\partial }_i,{\partial }_j]\equiv g_{ij}^{(D)},\end{array}$

where matrix g^(D) is positive semi-definite and defines a unique Riemannian metric on the manifold S.

Divergence D(·, ·) also defines a unique torsion-free affine connection ∇^(D) with coefficients

${\mathrm{\Gamma }}_{ij,k}^{(D)}=-D[{\partial }_i{\partial }_j,{\partial }_k],$

and the dual to this connection ∇* is generated by the dual divergence D*.

Thus, a divergence D(·, ·) generates on a statistical manifold a unique dualistic structure (g^(D), ∇^(D), ∇^(D*)). The converse is also true: every torsion-free dualistic structure on a statistical manifold is induced from some globally defined divergence function (which however need not be unique).

For example, when D is an f-divergence for some function ƒ(·), then it generates the metric Template:Nowrap and the connection Template:Nowrap, where g is the canonical Fisher information metric, ∇^(α) is the α-connection, Template:Nowrap, and Template:Nowrap.

Examples

The two most important divergences are the relative entropy (Kullback–Leibler divergence, KL divergence), which is central to information theory and statistics, and the squared Euclidean distance (SED). Minimizing these two divergences is the main way that linear inverse problems are solved, via the principle of maximum entropy and least squares, notably in logistic regression and linear regression.Template:Sfn

The two most important classes of divergences are the f-divergences and Bregman divergences; however, other types of divergence functions are also encountered in the literature. The only divergence for probabilities over a finite alphabet that is both an f-divergence and a Bregman divergence is the Kullback–Leibler divergence. The squared Euclidean divergence is a Bregman divergence (corresponding to the function Template:Tmath) but not an f-divergence.

f-divergences

Template:Main Given a convex function $f:[0,+\mathrm{\infty })\to (-\mathrm{\infty },+\mathrm{\infty }]$ such that $f(0)=\underset{t\to 0^{+}}{\lim }f(t),f(1)=0$, the f-divergence generated by $f$ is defined as

$D_f(p,q)=\int p(x)f\left(\frac{q(x)}{p(x)}\right)dx$.

Kullback–Leibler divergence:	$D_{\mathrm{K}\mathrm{L}}(p,q)=\int p(x)\ln \left(\frac{p(x)}{q(x)}\right)dx$
squared Hellinger distance:	$H^2(p,q)=2\int (\sqrt{p(x)}-\sqrt{q(x)}{)}^{2}dx$
Jensen–Shannon divergence:	$D_{JS}(p,q)=\frac{1}{2}\int p(x)\ln (p(x))+q(x)\ln (q(x))-(p(x)+q(x))\ln \left(\frac{p(x)+q(x)}{2}\right)dx$
α-divergence	$D^{(\alpha )}(p,q)=\frac{4}{1-{\alpha }^2}(1-\int p(x{)}^{\frac{1-\alpha }{2}}q(x{)}^{\frac{1+\alpha }{2}}dx)$
chi-squared divergence:	$D_{{\chi }^2}(p,q)=\int \frac{(p(x)-q(x){)}^2}{p(x)}dx$
(α,β)-product divergenceTemplate:Citation needed:	$D_{\alpha ,\beta }(p,q)=\frac{2}{(1-\alpha )(1-\beta )}\int (1-(\frac{q(x)}{p(x)}{)}^{\frac{1-\alpha }{2}}\left)\right(1-\left(\frac{q(x)}{p(x)}{)}^{\frac{1-\beta }{2}}\right)p(x)dx$

Bregman divergences

Template:Main Bregman divergences correspond to convex functions on convex sets. Given a strictly convex, continuously differentiable function Template:Math on a convex set, known as the Bregman generator, the Bregman divergence measures the convexity of: the error of the linear approximation of Template:Math from Template:Math as an approximation of the value at Template:Math:

$D_F(p,q)=F(p)-F(q)-⟨\mathrm{\nabla }F(q),p-q⟩.$

The dual divergence to a Bregman divergence is the divergence generated by the convex conjugate Template:Math of the Bregman generator of the original divergence. For example, for the squared Euclidean distance, the generator is Template:Tmath, while for the relative entropy the generator is the negative entropy Template:Tmath.

History

The use of the term "divergence" – both what functions it refers to, and what various statistical distances are called – has varied significantly over time, but by c. 2000 had settled on the current usage within information geometry, notably in the textbook Template:Harvtxt.Template:Sfn

The term "divergence" for a statistical distance was used informally in various contexts from c. 1910 to c. 1940. Its formal use dates at least to Template:Harvtxt, entitled "On a measure of divergence between two statistical populations defined by their probability distributions", which defined the Bhattacharyya distance, and Template:Harvtxt, entitled "On a Measure of Divergence between Two Multinomial Populations", which defined the Bhattacharyya angle. The term was popularized by its use for the Kullback–Leibler divergence in Template:Harvtxt and its use in the textbook Template:Harvtxt. The term "divergence" was used generally by Template:Harvtxt for statistically distances. Numerous references to earlier uses of statistical distances are given in Template:Harvtxt and Template:Harvtxt.

Template:Harvtxt actually used "divergence" to refer to the symmetrized divergence (this function had already been defined and used by Harold Jeffreys in 1948Template:Sfn), referring to the asymmetric function as "the mean information for discrimination ... per observation",Template:Sfn while Template:Harvtxt referred to the asymmetric function as the "directed divergence".Template:Sfn Template:Harvtxt referred generally to such a function as a "coefficient of divergence", and showed that many existing functions could be expressed as f-divergences, referring to Jeffreys' function as "Jeffreys' measure of divergence" (today "Jeffreys divergence"), and Kullback–Leibler's asymmetric function (in each direction) as "Kullback's and Leibler's measures of discriminatory information" (today "Kullback–Leibler divergence").Template:Sfn

The information geometry definition of divergence (the subject of this article) was initially referred to by alternative terms, including "quasi-distance" Template:Harvtxt and "contrast function" Template:Harvtxt, though "divergence" was used in Template:Harvtxt for the Template:Math-divergence, and has become standard for the general class.Template:SfnTemplate:Sfn

The term "divergence" is in contrast to a distance (metric), since the symmetrized divergence does not satisfy the triangle inequality.Template:Sfn For example, the term "Bregman distance" is still found, but "Bregman divergence" is now preferred.

Notationally, Template:Harvtxt denoted their asymmetric function as $I(1:2)$, while Template:Harvtxt denote their functions with a lowercase 'd' as $d(P_1,P_2)$.

See also

• Statistical distance

References

Bibliography

• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Citation. Republished by Dover Publications in 1968; reprinted in 1978: Template:Isbn
• Template:Cite journal