stringtranslate.com

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 , en particular 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 que muchas técnicas de la teoría de la optimización se generalicen a las divergencias de Bregman, geométricamente como generalizaciones de mínimos cuadrados .

Las divergencias de Bregman reciben su nombre del matemático ruso Lev M. Bregman , quien introdujo el concepto en 1967.

Definición

Sea una función estrictamente convexa, continuamente diferenciable, definida en un conjunto convexo .

La distancia de Bregman asociada con F para los puntos 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 :

Propiedades

Aquí, y son los puntos duales correspondientes a p y q.
Además, utilizando las mismas notaciones:

Para cualquier

Teorema de Pitágoras generalizado para la divergencia de Bregman. [2]

. Entonces

Para cualquiera ,

Esta es una igualdad si está en el interior relativo de .

En particular, esto siempre sucede cuando es un conjunto afín.

Pruebas

Arreglar . Realizar la transformación afín en , de modo que .

Tome algunos , tales que . Luego considere la derivada "direccional radial" de en la esfera euclidiana .

Para todos .

Como es compacto, alcanza un valor mínimo en algún momento .

Dado que es estrictamente convexo, . Entonces .

Como es en , es continua en , por lo tanto es cerrada si es.

Arreglar . Tomar algunos , luego dejar . Luego dibujar la bola de Bregman . Es cerrada y acotada, por lo tanto compacta. Como es continua y estrictamente convexa en ella, y acotada por debajo por , alcanza un mínimo único en ella.

Por la ley del coseno, , que debe ser , ya que se minimiza en , y es convexo.

Si , entonces como está en el interior relativo, podemos movernos desde en la dirección opuesta de , para disminuir , contradicción.

De este modo .

Teoremas de clasificación

Prueba
Divergencia de Bregman interpretada como áreas.

Para cualquier , defina para . Sea .

Entonces , para , y como es continua, también para .

Luego, del diagrama, vemos que para todo , debemos tener lineal en .

Así, encontramos que varía linealmente a lo largo de cualquier dirección. Por el siguiente lema, es cuadrático. Como también es estrictamente convexo, tiene la forma , donde .

Lema : Si es un subconjunto abierto de , tiene derivada continua y dado cualquier segmento de línea , la función es lineal en , entonces es una función cuadrática.

Idea de prueba: Para cualquier función cuadrática , todavía tenemos dicha linealidad derivada, por lo que restaremos algunas funciones cuadráticas y demostraremos que se convierte en cero.

La idea de prueba se puede ilustrar completamente para el caso de , por lo que la demostramos en este caso.

Por la linealidad derivada, es una función cuadrática en cualquier segmento de línea en . Restamos cuatro funciones cuadráticas, de modo que se vuelve idénticamente cero en el eje x, el eje y y la línea.

Sea , para una elección correcta . Ahora use para eliminar el término lineal y use respectivamente para eliminar los términos cuadráticos a lo largo de las tres líneas.

no en el origen, existe una línea que cruza el eje x, el eje y y la línea en tres puntos diferentes. Como es cuadrática en , y es cero en tres puntos diferentes, es idénticamente cero en , por lo tanto . Por lo tanto es cuadrática.

Las siguientes dos caracterizaciones son para divergencias en , el conjunto de todas las medidas de probabilidad en , con .

Defina una divergencia en como cualquier función de tipo , tal que para todo , entonces:

Dada una divergencia de Bregman , su "opuesto", definido por , generalmente no es 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.

Ejemplos

se genera por la función de entropía negativa
Cuando se restringe al símplex , los dos últimos términos se cancelan, dando lugar a la divergencia de Kullback-Leibler habitual para distribuciones.
es generado por la función convexa

Generalizando la dualidad proyectiva

Una herramienta clave en la geometría computacional es la idea de dualidad proyectiva , que asigna puntos a hiperplanos y viceversa, al tiempo que preserva la incidencia y las relaciones arriba-abajo. Existen numerosas formas analíticas del dual proyectivo: una forma común asigna el punto al hiperplano . Esta asignación se puede interpretar (identificando el hiperplano con su normal) como la asignación conjugada convexa que lleva el punto p a su punto dual , donde F define el paraboloide de dimensión d .

Si ahora reemplazamos el paraboloide por una función convexa arbitraria, obtenemos una función dual diferente que conserva las propiedades de incidencia y arriba-abajo del dual proyectivo estándar. Esto implica que los 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).

Generalización de las divergencias de Bregman

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 utilizando la convexidad comparativa, y los casos límite de estas generalizaciones de divergencias de Jensen sesgadas producen divergencias de Bregman generalizadas (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.

Divergencia de Bregman en otros objetos

Las divergencias de Bregman también se pueden definir 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; consulte las referencias de Frigyik et al. a continuación para obtener definiciones y propiedades. De manera similar, las divergencias de Bregman también se han definido sobre conjuntos, a través de una función de conjunto submodular que se conoce como el análogo discreto de una función convexa . Las divergencias de Bregman submodulares subsumen una serie de medidas de distancia discretas, como la distancia de Hamming , la precisión y la recuperación , la información mutua y algunas otras medidas de distancia basadas en conjuntos (consulte Iyer y Bilmes, 2012 para obtener más detalles y propiedades del Bregman submodular).

Para obtener una lista de divergencias de Bregman de matriz comunes, consulte la Tabla 15.1 en [8] .

Aplicaciones

En el aprendizaje automático, las divergencias de Bregman se utilizan para calcular la pérdida logística biterminada y tienen un mejor rendimiento 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 .

Referencias

  1. ^ ab "Aprendizaje con divergencias de Bregman" (PDF) . utexas.edu . Consultado el 19 de agosto de 2023 .
  2. ^ Adamčík, Martin (2014). "La geometría de la información de las divergencias de Bregman y algunas aplicaciones en el razonamiento multiexperto". Entropy . 16 (12): 6338–6381. Bibcode :2014Entrp..16.6338A. doi : 10.3390/e16126338 .
  3. ^ Dhillon, Inderjit ; Tropp, Joel (2008). "Matrix Nearness Problems with Bregman Divergence" (PDF) . SIAM Journal on Matrix Analysis and Applications . 29 (4). Supongamos que D_\varphi es una divergencia de Bregman, supongamos que {C_k} es una colección finita de conjuntos cerrados y convexos cuya intersección no está vacía. Dada una matriz de entrada Y, nuestro objetivo es producir una matriz \mathbf{X} en la intersección que diverja menos de \textbf{Y}, es decir, resolver \min_{\mathbf{X} } D_\varphi(\mathbf{X};\mathbf{Y}) sujeta a \mathbf{X} \in \big\cap_k C_k. En condiciones suaves, la solución es única y tiene una caracterización variacional análoga a la caracterización de una proyección ortogonal sobre un conjunto convexo" (ver s2.4, página 1125 para más información)
  4. ^ Nielsen, Frank (28 de octubre de 2021). "Aproximaciones rápidas de la divergencia de Jeffreys entre mezclas gaussianas univariadas mediante conversiones de mezclas a distribuciones polinomiales exponenciales". Entropía . 23 (11): 1417. arXiv : 2107.05901 . Bibcode :2021Entrp..23.1417N. doi : 10.3390/e23111417 . ISSN  1099-4300. PMC 8619509 . PMID  34828115. 
  5. ^ Nielsen, Frank; Boissonnat, Jean-Daniel ; Nock, Richard (septiembre de 2010). "Diagramas de Bregman Voronoi: propiedades, algoritmos y aplicaciones". Geometría discreta y computacional . 44 (2): 281–307. arXiv : 0709.2196 . doi :10.1007/s00454-010-9256-1. ISSN  0179-5376. S2CID  1327029.
  6. ^ ab Jiao, Jiantao; Courtade, Thomas; No, Albert; Venkat, Kartik; Weissman, Tsachy (diciembre de 2014). "Medidas de información: el curioso caso del alfabeto binario". IEEE Transactions on Information Theory . 60 (12): 7616–7626. arXiv : 1404.6810 . doi :10.1109/TIT.2014.2360184. ISSN  0018-9448. S2CID  13108908.
  7. ^ Nielsen, Frank; Nock, Richard (2019). "La divergencia de las cuerdas de Bregman". Ciencia geométrica de la información . Apuntes de clase en informática. Vol. 11712. págs. 299–308. arXiv : 1810.09113 . doi :10.1007/978-3-030-26980-7_31. ISBN 978-3-030-26979-1. Número de identificación del sujeto  53046425.
  8. ^ "Geometría de la información matricial", R. Nock, B. Magdalou, E. Briys y F. Nielsen, pdf, de este libro
  9. ^ Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren (2019). "Pérdida logística robusta bitemperada basada en divergencias de Bregman". Conferencia sobre sistemas de procesamiento de información neuronal. pp. 14987-14996. pdf