Divergence de Bregman

En mathématiques, la divergence de Bregman est une mesure de la différence entre deux distributions dérivée d'une fonction potentiel U à valeurs réelles strictement convexe et continûment différentiable.

Illustration de la définition de la divergence de Bregman dans un espace unidimensionnel

Le concept a été introduit par Lev M. Bregman (en) en 1967. Par l'intermédiaire de la transformation de Legendre, au potentiel $U$ correspond un potentiel dual $U^{*}$ et leur différentiation donne naissance à deux systèmes de coordonnées duaux.

Définition

Soit $U(x)$ une fonction à valeurs réelles, strictement convexe et continûment différentiable définie sur un domaine convexe fermé $\Omega$. La divergence de Bregman d'un point $x_{1}$ de $\Omega$ par rapport à un autre point $x_{0}$ de $\Omega$ est :

$D_{U}(x_{1}:x_{0})=U(x_{1})-U(x_{0})-\langle \nabla U(x_{0}),(x_{1}-x_{0})\rangle$

Propriétés

La divergence de Bregman possède certaines des propriétés d'une distance :

• Positivité : $\forall x,y\in \Omega ,D_{U}(x:y)\geq 0$.
• Séparation : $\forall x,y\in \Omega ,D_{U}(x:y)=0\Leftrightarrow x=y$.

Par contre, la symétrie et l'inégalité triangulaire ne sont pas vérifiées, ce qui fait qu'elle n'est pas une distance.

Autres propriétés :

• Convexité : la divergence est convexe par rapport à son premier argument.
• Linéarité : pour deux fonctions convexes U et V à valeur réelle et un réel $\forall \lambda >0,D_{U+\lambda V}(x:y)=D_{U}(x:y)+\lambda D_{V}(x:y)$.
• Dualité : la divergence de Bregman est de nature duale : par transformation de Legendre de $U$, on obtient une fonction $U^{*}$ dont la divergence associée $D_{U^{*}}$ est symétrique par rapport à $D_{U}$ :

$D_{U}(x:y)=D_{U^{*}}(y^{*}:x^{*})$.

Les points x et y étant exprimés selon deux systèmes de coordonnées duaux issus de la transformation de Legendre : $x^{*}=\nabla U(x)$ et $x=\nabla U^{*}(x^{*})$. La divergence peut être réécrite sous la forme :

$D_{U}(x:y)=U(x)+U^{*}(y^{*})-\langle x\cdot y^{*}\rangle$.

Exemples

• La distance de Mahalanobis (et donc le carré de la distance euclidienne) est une divergence de Bregman auto-duale :

$D_{U}(p:q)={\frac {1}{2}}\sum _{ij}a_{ij}(p_{i}-q_{i})(p_{j}-q_{j})$,

avec

$U(p)={\frac {1}{2}}\sum _{ij}a_{ij}p_{i}p_{j}$.

• les α-divergences popularisées par Amari sont un autre exemple.

La divergence entre une distribution p par rapport à une distribution q est définie par :

$D^{(\alpha )}(p:q)={\frac {4}{1-\alpha ^{2}}}\sum _{i}{\frac {1-\alpha }{2}}p_{i}+{\frac {1+\alpha }{2}}q_{i}-p_{i}^{\frac {1-\alpha }{2}}\cdot q_{i}^{\frac {1+\alpha }{2}}$.

La divergence duale de $D^{(\alpha )}$ est $D^{(-\alpha )}$.

Par ailleurs, les α-divergences dérivent des fonctions potentiels :

$U^{(\alpha )}(p)={\frac {2}{1+\alpha }}\sum _{i}p_{i}$

et des coordonnées associées :

$r_{i}^{(\alpha )}(p)={\frac {2}{1-\alpha }}p_{i}^{\frac {1-\alpha }{2}}$.

On a alors la relation de dualité des transformées de Legendre :

$r_{i}^{(-\alpha )}=\nabla _{r^{(\alpha )}}U^{(\alpha )}$.

Par ailleurs, avec les notations introduite, la divergence peut être écrite selon sa forme canonique :

$D^{(\alpha )}(p:q)=U^{(\alpha )}(p)+U^{(-\alpha )}(q)-\sum _{i}r_{i}^{(\alpha )}(p)r_{i}^{(-\alpha )}(q)$.

Un cas particulier de α-divergence est la divergence de Kullback-Leibler

• La distance de Itakura-Sato :

$D_{U}(p:q)=\sum _{i}{\frac {p_{i}}{q_{i}}}-\log {\frac {p_{i}}{q_{i}}}-1$,

avec

$U(p)=\sum _{i}\log p_{i}$.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bregman divergence » (voir la liste des auteurs).