divergencia de Bregman

En matemáticas , específicamente en estadística y geometría de la información , una divergencia de Bregman o distancia de Bregman es una medida de la diferencia entre dos puntos, definida en términos de una función estrictamente convexa ; forman una clase importante de divergencias . Cuando los puntos se interpretan como distribuciones de probabilidad —ya sea como valores del parámetro de un modelo paramétrico o como un conjunto de datos de valores observados— la distancia resultante es una distancia estadística . La divergencia de Bregman más básica es la distancia euclidiana al cuadrado .

Las divergencias de Bregman son similares a las métricas , pero no satisfacen ni la desigualdad triangular (nunca) ni la simetría (en general). Sin embargo, satisfacen una generalización del teorema de Pitágoras , y en geometría de la información la variedad estadística correspondiente se interpreta como una variedad (dualmente) plana . Esto permite generalizar muchas técnicas de la teoría de la optimización a las divergencias de Bregman, geométricamente como generalizaciones de los mínimos cuadrados .

Las divergencias de Bregman reciben su nombre del matemático soviético e israelí Lev M. Bregman , quien introdujo el concepto en 1967.

Dejar${\displaystyle F\colon \Omega \to \mathbb {R} }$sea ​​una función estrictamente convexa y continuamente diferenciable definida en un conjunto convexo.${\displaystyle \Omega }$.

La distancia de Bregman asociada con F para puntos${\displaystyle p,q\in \Omega }$es la diferencia entre el valor de F en el punto p y el valor de la expansión de Taylor de primer orden de F alrededor del punto q evaluada en el punto p : $${\displaystyle D_{F}(p,q)=F(p)-F(q)-\langle \nabla F(q),pq\rangle .}$$

• No negatividad :${\displaystyle D_{F}(p,q)\geq 0}$a pesar de${\displaystyle p}$,${\displaystyle q}$Esto es consecuencia de la convexidad de${\displaystyle F}$.
• Positividad : Cuando${\displaystyle F}$es estrictamente convexa,${\displaystyle D_{F}(p,q)=0}$si y solo si${\displaystyle p=q}$.
• Unicidad hasta la diferencia afín :${\displaystyle D_{F}=D_{G}}$si y solo si${\displaystyle FG}$es una función afín.
• Convexidad :${\displaystyle D_{F}(p,q)}$es convexa en su primer argumento, pero no necesariamente en el segundo. Si F es estrictamente convexa, entonces${\displaystyle D_{F}(p,q)}$es estrictamente convexa en su primer argumento.
  • Por ejemplo, tome f ( x ) = | x |, suavícela en 0, luego tome${\displaystyle y=1,x_{1}=0.1,x_{2}=-0.9,x_{3}=0.9x_{1}+0.1x_{2}}$, entonces${\displaystyle D_{f}(y,x_{3})\approx 1>0.9D_{f}(y,x_{1})+0.1D_{f}(y,x_{2})\approx 0.2}$.
• Linealidad : Si pensamos en la distancia de Bregman como un operador sobre la función F , entonces es lineal con respecto a coeficientes no negativos. En otras palabras, para${\displaystyle F_{1},F_{2}}$estrictamente convexa y diferenciable, y${\displaystyle \lambda \geq 0}$,$${\displaystyle D_{F_{1}+\lambda F_{2}}(p,q)=D_{F_{1}}(p,q)+\lambda D_{F_{2}}(p,q)}$$
• Dualidad : Si F es estrictamente convexa, entonces la función F tiene una función conjugada convexa.${\displaystyle F^{*}}$que también es estrictamente convexa y continuamente diferenciable en algún conjunto convexo.${\displaystyle \Omega ^{*}}$. La distancia de Bregman definida con respecto a${\displaystyle F^{*}}$es dual a${\displaystyle D_{F}(p,q)}$como$${\displaystyle D_{F^{*}}(p^{*},q^{*})=D_{F}(q,p)}$$Aquí,${\displaystyle p^{*}=\nabla F(p)}$y${\displaystyle q^{*}=\nabla F(q)}$son los puntos duales correspondientes a p y q .
  Además, utilizando las mismas notaciones:$${\displaystyle D_{F}(p,q)=F(p)+F^{*}(q^{*})-\langle p,q^{*}\rangle }$$
• Forma integral: mediante la forma de resto integral del teorema de Taylor , una divergencia de Bregman se puede escribir como la integral del hessiano de${\displaystyle F}$a lo largo del segmento de línea entre los argumentos de la divergencia de Bregman.
• La media como minimizador : Un resultado clave sobre las divergencias de Bregman es que, dado un vector aleatorio , el vector medio minimiza la divergencia de Bregman esperada respecto a dicho vector. Este resultado generaliza el resultado clásico que establece que la media de un conjunto minimiza el error cuadrático total respecto a los elementos del conjunto. Este resultado fue demostrado para el caso vectorial por (Banerjee et al. 2005) y extendido al caso de funciones/distribuciones por (Frigyik et al. 2008). Este resultado es importante porque justifica aún más el uso de la media como representante de un conjunto aleatorio, especialmente en la estimación bayesiana.
• Las bolas de Bregman están delimitadas y son compactas si${\displaystyle X}$está cerrado : Defina la bola de Bregman centrada en${\displaystyle x}$con radio${\displaystyle r}$por${\displaystyle B_{f}(x,r):=\left\{y\in X:D_{f}(y,x)\leq r\right\}}$. Cuando${\displaystyle X\subset \mathbb {R} ^{n}}$es de dimensión finita,${\displaystyle \forall x\in X}$, si${\displaystyle x}$está en el interior relativo de${\displaystyle X}$, o si${\displaystyle X}$está cerrado localmente en${\displaystyle x}$(es decir, existe una bola cerrada)${\displaystyle B(x,r)}$centrado en${\displaystyle x}$, de tal manera que${\displaystyle B(x,r)\cap X}$está cerrado), entonces${\displaystyle B_{f}(x,r)}$está limitado para todos${\displaystyle r}$. Si${\displaystyle X}$está cerrado, entonces${\displaystyle B_{f}(x,r)}$es compacto para todos${\displaystyle r}$.
• Ley de los cosenos : ^{[ 1 ]}
  Para cualquier${\displaystyle p,q,z}$$${\displaystyle D_{F}(p,q)=D_{F}(p,z)+D_{F}(z,q)-(pz)^{T}(\nabla F(q)-\nabla F(z))}$$
• Ley del paralelogramo : para cualquier${\displaystyle \theta ,\theta _{1},\theta _{2}}$,$${\displaystyle B_{F}\left(\theta _{1}:\theta \right)+B_{F}\left(\theta _{2}:\theta \right)=B_{F}\left(\theta _{1}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+B_{F}\left(\theta _{2}:{\frac {\theta _{1}+\theta _{2}}{2}}\right)+2B_{F}\left({\frac {\theta _{1}+\theta _{2}}{2}}:\theta \right)}$$

  

• Proyección de Bregman : Para cualquier${\displaystyle W\subset \Omega }$, definir la "proyección de Bregman" de${\displaystyle q}$sobre${\displaystyle W}$:$${\displaystyle P_{W}(q)=\mathop {\operatorname {argmin} } _{\omega \in W}D_{F}(\omega ,q).}$$Entonces
  • si${\displaystyle W}$Si es convexa, entonces la proyección es única si existe;
  • si${\displaystyle W}$es no vacío, cerrado y convexo y${\displaystyle \Omega \subset \mathbb {R} ^{n}}$Si es de dimensión finita, entonces la proyección existe y es única. ^{[ 3 ]}
• Teorema generalizado de Pitágoras : ^{[ 1 ]}
  Para cualquier${\displaystyle v\in \Omega ,a\in W}$,$${\displaystyle D_{F}(a,v)\geq D_{F}(a,P_{W}(v))+D_{F}(P_{W}(v),v).}$$Esto es una igualdad si${\displaystyle P_{W}(v)}$está en el interior relativo de${\displaystyle W}$.
  En particular, esto siempre sucede cuando${\displaystyle W}$es un conjunto afín.
• Falta de desigualdad triangular: Dado que la divergencia de Bregman es esencialmente una generalización de la distancia euclidiana al cuadrado, no existe desigualdad triangular. De hecho,${\displaystyle D_{F}(z,x)-D_{F}(z,y)-D_{F}(y,x)=\langle \nabla f(y)-\nabla f(x),z-y\rangle }$, que pueden ser positivas o negativas.

Teoremas de clasificación

• Las únicas divergencias de Bregman simétricas en${\displaystyle X\subset \mathbb {R} ^{n}}$son distancias euclidianas generalizadas al cuadrado ( distancia de Mahalanobis ), es decir,${\displaystyle D_{f}(y,x)=(y-x)^{T}A(y-x)}$para algunos positivos definidos${\displaystyle A}$. ^{[ 5 ]}

Prueba

Para cualquier${\displaystyle x\neq y\in X}$, definir${\displaystyle r=\|y-x\|,v=(y-x)/r,g(t)=f(x+tv)}$para${\displaystyle t\in [0,r]}$. Dejar${\displaystyle z(t)=x+tv}$.

Entonces${\displaystyle g'(t)=\langle \nabla f(z(t)),v\rangle }$para${\displaystyle t\in (0,r)}$y desde entonces${\displaystyle \nabla f}$es continuo, también para${\displaystyle t=0,r}$.

Entonces, a partir del diagrama, vemos que para${\displaystyle D_{f}(x;z(t))=D_{f}(z(t);x)}$a pesar de${\displaystyle t\in [0,r]}$, debemos tener${\displaystyle g'(t)}$lineal en${\displaystyle t\in [0,r]}$.

Así encontramos que${\displaystyle \nabla f}$varía linealmente a lo largo de cualquier dirección. Por el siguiente lema,${\displaystyle f}$es cuadrática. Dado que${\displaystyle f}$También es estrictamente convexa, es de forma${\displaystyle f(x)+x^{T}Ax+B^{T}x+C}$, dónde${\displaystyle A\succ 0}$.

Lema : Si${\displaystyle S}$es un subconjunto abierto de${\displaystyle \mathbb {R} ^{n}}$,${\displaystyle f:S\to \mathbb {R} }$tiene derivada continua, y dado cualquier segmento de línea${\displaystyle [x,x+v]\subset S}$, la función${\displaystyle h(t):=\langle \nabla f(x+tv),v\rangle }$es lineal en${\displaystyle t}$, entonces${\displaystyle f}$es una función cuadrática.

Idea de demostración: Para cualquier función cuadrática${\displaystyle q:S\to \mathbb {R} }$, tenemos${\displaystyle f-q}$aún tiene dicha linealidad derivada, por lo que restaremos algunas funciones cuadráticas y mostraremos que${\displaystyle f}$se convierte en cero.

La idea de la prueba se puede ilustrar completamente para el caso de${\displaystyle S=\mathbb {R} ^{2}}$, así que lo demostramos en este caso.

Por la linealidad derivada,${\displaystyle f}$es una función cuadrática en cualquier segmento de línea en${\displaystyle \mathbb {R} ^{2}}$. Restamos cuatro funciones cuadráticas, de tal manera que${\displaystyle g:=f-q_{0}-q_{1}-q_{2}-q_{3}}$se vuelve idénticamente cero en el eje x, el eje y y el${\displaystyle \{x=y\}}$línea.

Dejar${\displaystyle q_{0}(x,y)=f(0,0)+\nabla f(0,0)\cdot (x,y),q_{1}(x,y)=A_{1}x^{2},q_{2}(x,y)=A_{2}y^{2},q_{3}(x,y)=A_{3}xy}$, para bien elegidos${\displaystyle A_{1},A_{2},A_{3}}$Ahora usa .${\displaystyle q_{0}}$para eliminar el término lineal y usar${\displaystyle q_{1},q_{2},q_{3}}$respectivamente para eliminar los términos cuadráticos a lo largo de las tres líneas.

${\displaystyle \forall (x,y)\in \mathbb {R} ^{2}}$no en el origen, existe una línea${\displaystyle l}$al otro lado de${\displaystyle (x,y)}$que interseca el eje x, el eje y y el${\displaystyle \{x=y\}}$línea en tres puntos diferentes. Dado que${\displaystyle g}$es cuadrático en${\displaystyle l}$y es cero en tres puntos diferentes,${\displaystyle g}$es idénticamente cero en${\displaystyle l}$, de este modo${\displaystyle g(x,y)=0}$. De este modo${\displaystyle f=q_{0}+q_{1}+q_{2}+q_{3}}$es cuadrática.

Las siguientes dos caracterizaciones son para divergencias en${\displaystyle \Gamma _{n}}$, el conjunto de todas las medidas de probabilidad en${\displaystyle \{1,2,...,n\}}$, con${\displaystyle n\geq 2}$.

Defina una divergencia en${\displaystyle \Gamma _{n}}$como cualquier función de tipo${\displaystyle D:\Gamma _{n}\times \Gamma _{n}\to [0,\infty ]}$, de tal manera que${\displaystyle D(x,x)=0}$a pesar de${\displaystyle x\in \Gamma _{n}}$, entonces:

• La única divergencia en${\displaystyle \Gamma _{n}}$La divergencia de Kullback-Leibler es aquella que es a la vez una divergencia de Bregman y una divergencia f . ^{[ 6 ]}
• Si${\displaystyle n\geq 3}$, entonces cualquier divergencia de Bregman en${\displaystyle \Gamma _{n}}$que satisface la desigualdad de procesamiento de datos debe ser la divergencia de Kullback-Leibler. (De hecho, una suposición más débil de "suficiencia" es suficiente). Existen contraejemplos cuando${\displaystyle n=2}$. ^{[ 6 ]}

Dada una divergencia de Bregman${\displaystyle D_{F}}$, su "opuesto", definido por${\displaystyle D_{F}^{*}(v,w)=D_{F}(w,v)}$Generalmente, no se trata de una divergencia de Bregman. Por ejemplo, la divergencia de Kullback-Leiber es tanto una divergencia de Bregman como una divergencia f. Su inversa también es una divergencia f, pero según la caracterización anterior, la divergencia KL inversa no puede ser una divergencia de Bregman.

• El ejemplo canónico de una distancia de Bregman es la distancia euclidiana al cuadrado.${\displaystyle D_{F}(x,y)=\|x-y\|^{2}}$.
• La distancia de Mahalanobis al cuadrado${\displaystyle D_{F}(x,y)={\tfrac {1}{2}}(x-y)^{T}Q(x-y)}$se genera mediante la forma cuadrática convexa${\displaystyle F(x)={\tfrac {1}{2}}x^{T}Qx}$. La distancia euclidiana al cuadrado es el caso especial donde${\displaystyle Q}$es la identidad, es decir, para${\displaystyle F(x)=\|x\|^{2}}$. Como se ha señalado, las diferencias afines, es decir, los órdenes inferiores añadidos en${\displaystyle F}$son irrelevantes para${\displaystyle D_{F}}$.
• La divergencia generalizada de Kullback-Leibler$${\displaystyle D_{F}(p,q)=\sum _{i}p(i)\log {\frac {p(i)}{q(i)}}-\sum _{i}p(i)+\sum _{i}q(i)}$$es generado por la función de entropía negativa$${\displaystyle F(p)=\sum _{i}p(i)\log p(i)}$$Cuando se restringe al simplex , los dos últimos términos se cancelan, dando la divergencia de Kullback-Leibler habitual para las distribuciones.
• La distancia Itakura-Saito ,$${\displaystyle D_{F}(p,q)=\sum _{i}\left({\frac {p(i)}{q(i)}}-\log {\frac {p(i)}{q(i)}}-1\right)}$$es generada por la función convexa$${\displaystyle F(p)=-\sum _{i}\log p(i)}$$

Una herramienta clave en geometría computacional es la idea de dualidad proyectiva , que mapea puntos a hiperplanos y viceversa, preservando la incidencia y las relaciones arriba-abajo. Existen numerosas formas analíticas de la dualidad proyectiva: una forma común mapea el punto${\displaystyle p=(p_{1},\ldots p_{d})}$al hiperplano${\textstyle x_{d+1}=\sum _{i=1}^{d}2p_{i}x_{i}}$. Este mapeo puede interpretarse (identificando el hiperplano con su normal) como el mapeo convexo conjugado que lleva el punto p a su punto dual.${\displaystyle p^{*}=\nabla F(p)}$donde F define el paraboloide d- dimensional${\textstyle x_{d+1}=\sum _{i}x_{i}^{2}}$.

Si ahora sustituimos el paraboloide por una función convexa arbitraria, obtenemos una aplicación dual diferente que conserva las propiedades de incidencia y de arriba-abajo de la dualidad proyectiva estándar. Esto implica que conceptos duales naturales en geometría computacional, como los diagramas de Voronoi y las triangulaciones de Delaunay, conservan su significado en espacios de distancia definidos por una divergencia de Bregman arbitraria. Por lo tanto, los algoritmos de la geometría "normal" se extienden directamente a estos espacios (Boissonnat, Nielsen y Nock, 2010).

Las divergencias de Bregman pueden interpretarse como casos límite de divergencias de Jensen sesgadas (véase Nielsen y Boltz, 2011). Las divergencias de Jensen pueden generalizarse mediante la convexidad comparativa, y los casos límite de estas generalizaciones de las divergencias de Jensen sesgadas dan lugar a la divergencia de Bregman generalizada (véase Nielsen y Nock, 2017). La divergencia de cuerda de Bregman ^{[ 7 ]} se obtiene tomando una cuerda en lugar de una línea tangente.

Las divergencias de Bregman también pueden definirse entre matrices, entre funciones y entre medidas (distribuciones). Las divergencias de Bregman entre matrices incluyen la pérdida de Stein y la entropía de von Neumann . Las divergencias de Bregman entre funciones incluyen el error cuadrático total, la entropía relativa y el sesgo cuadrático; véanse las referencias de Frigyik et al. a continuación para definiciones y propiedades. De manera similar, las divergencias de Bregman también se han definido sobre conjuntos, mediante una función de conjunto submodular conocida como el análogo discreto de una función convexa . Las divergencias de Bregman submodulares engloban varias medidas de distancia discretas, como la distancia de Hamming , la precisión y la exhaustividad , la información mutua y otras medidas de distancia basadas en conjuntos (véase Iyer y Bilmes, 2012 para más detalles y propiedades de la divergencia de Bregman submodular).

Para obtener una lista de las divergencias de Bregman de matrices comunes, consulte la Tabla 15.1 en ^{[ 8 ] .}

En el aprendizaje automático, las divergencias de Bregman se utilizan para calcular la pérdida logística biterizada, que funciona mejor que la función softmax con conjuntos de datos ruidosos. ^{[ 9 ]}

La divergencia de Bregman se utiliza en la formulación del descenso de espejo , que incluye algoritmos de optimización utilizados en el aprendizaje automático, como el descenso de gradiente y el algoritmo de cobertura .