Divergence de Bregman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher


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

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 à valeur réelle strictement convexe et continûment différentiable.

Le concept a été introduit par Lev M. Bregman (en) en 1967[1]. 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 duals.

Définition[modifier | modifier le code]

Soit U(x) une fonction à valeur réelle 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[modifier | modifier le code]

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

  • Positivité : \forall x,y \in \Omega, D_U(x:y)\geq0.
  • 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[2] : 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 duals 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[modifier | modifier le code]

 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[3] 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^{(\alpha)}_i (p)= \frac{2}{1-\alpha} p_i^\frac{1-\alpha}{2} .

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

 r^{(-\alpha)}_i = \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^{(\alpha)}_i (p) r^{(-\alpha)}_i (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[modifier | modifier le code]

  1. L. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, Vol. 7(3): 200--217, 1967.
  2. S. Amari, Information geometry in optimization, machine learning and statistical inference, Front. Electr. Electron. Eng. China, vol. 5(3), pp. 241-260, 2010, DOI 10.1007/s11460-010-0101-3
  3. S. Amari, H. Nagaoka, Methods of information geometry, Translations of mathematical monographs; v. 191, American Mathematical Society, 2000 (ISBN 978-0821805312)

(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)