Las divergencias de Bregman llevan el 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 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 evaluado en el punto p :
Propiedades
No negatividad : para todos , . Esto es una consecuencia de la convexidad de .
Positividad : Cuando es estrictamente convexa, si y así .
Unicidad hasta diferencia afín : iff es una función afín.
Convexidad : es convexa en su primer argumento, pero no necesariamente en el segundo argumento. Si F es estrictamente convexo, entonces es estrictamente convexo en su primer argumento.
Por ejemplo, tome f(x) = |x|, suavice en 0, luego tome , luego .
Linealidad : si pensamos en la distancia de Bregman como un operador de la función F , entonces es lineal con respecto a coeficientes no negativos. En otras palabras, para estrictamente convexo y diferenciable, y ,
Dualidad : si F es estrictamente convexa, entonces la función F tiene un conjugado convexo que también es estrictamente convexo y continuamente diferenciable en algún conjunto convexo . La distancia de Bregman definida con respecto a es dual a as
Aquí, y están los puntos duales correspondientes a p y q.
Además, usando las mismas notaciones:
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 del vector aleatorio. Este resultado generaliza el resultado del libro de texto de que la media de un conjunto minimiza el error cuadrático total de los elementos del conjunto. Este resultado fue demostrado para el caso de vectores 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 una media como representativa de un conjunto aleatorio, particularmente en la estimación bayesiana.
Las bolas de Bregman están acotadas y compactas si X está cerrado : defina la bola de Bregman centrada en x con radio r por . Cuando es de dimensión finita, si está en el interior relativo de , o si está localmente cerrado en (es decir, existe una bola cerrada centrada en , tal que está cerrada), entonces está acotado para todos . Si es cerrado, entonces es compacto para todos .
En particular, esto siempre sucede cuando 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, lo cual puede ser positivo o negativo.
Unicidad hasta diferencia afín: arreglar algunos , luego para cualquier otro , tenemos por definición .
Convexidad en el primer argumento: por definición, y use la convexidad de F. Lo mismo para la convexidad estricta.
Linealidad en F, ley de los cosenos, ley del paralelogramo: por definición.
Dualidad: Ver figura 1 de. [3]
Las bolas de Bregman están acotadas y compactas si X está cerrado:
Arreglar . Realice una transformación afín para que .
Toma algunos , tales que . Luego considere la derivada "radial-direccional" de en la esfera euclidiana .
para todos .
Como es compacto, alcanza un valor mínimo en algunos .
Dado que es estrictamente convexo, . Entonces .
Como está en , es continua en , por lo tanto está cerrado si es.
La proyección está bien definida cuando es cerrada y convexa.
Arreglar . Toma un poco y luego déjalo . Luego dibuja la bola de Bregman . Es cerrado y acotado, por tanto compacto. Dado que es continuo y estrictamente convexo y está limitado por debajo por , logra un mínimo único en él.
Desigualdad pitagórica.
Por la ley del coseno, , que debe ser , ya que minimiza en , y es convexo.
Igualdad pitagórica cuando está en el interior relativo de .
Si , entonces como está en el interior relativo, podemos movernos en la dirección opuesta a , para disminuir su contradicción.
De este modo .
Teoremas de clasificación
Las únicas divergencias simétricas de Bregman son las distancias euclidianas generalizadas al cuadrado ( distancia de Mahalanobis ), es decir, para algún definido positivo . [4]
Prueba
Para cualquiera , defina para . Dejar .
Entonces for , y puesto que es continuo, también for .
Luego, en el diagrama, vemos que para todos debemos tener un on lineal .
Así encontramos que varía linealmente a lo largo de cualquier dirección. Según 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 recta , 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 tal derivada-linealidad, por lo que restaremos algunas funciones cuadráticas y demostraremos que se vuelve 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 vuelven idénticamente cero en el eje x, el eje y y la recta.
Vamos , por bien elegidos . 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. Dado que es cuadrático en , y es cero en tres puntos diferentes, es idénticamente cero en , por lo tanto . Por tanto es cuadrático.
Las dos caracterizaciones siguientes 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 todos , entonces:
Si , entonces cualquier divergencia de Bregman que satisfaga la desigualdad en el procesamiento de datos debe ser la divergencia de Kullback-Leibler. (De hecho, un supuesto más débil de "suficiencia" es suficiente.) Existen contraejemplos cuando . [5]
Dada una divergencia de Bregman , su "opuesto", definido por , generalmente no es una divergencia de Bregman. Por ejemplo, la divergencia Kullback-Leiber es a la vez una divergencia de Bregman y 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 distancia de Bregman es la distancia euclidiana al cuadrado . Resulta como el caso especial de lo anterior, cuando es la identidad, es decir, para . Como se señaló, las diferencias afines, es decir, los órdenes inferiores agregados en , son irrelevantes para .
Una herramienta clave en geometría computacional es la idea de dualidad proyectiva , que asigna puntos a hiperplanos y viceversa, preservando al mismo tiempo la incidencia y las relaciones arriba-abajo. Existen numerosas formas analíticas del dual proyectivo: una forma común asigna el punto al hiperplano . Este mapeo se puede interpretar (identificando el hiperplano con su normal) como el mapeo conjugado convexo que lleva el punto p a su punto dual , donde F define el paraboloide d -dimensional .
Si ahora reemplazamos el paraboloide por una función convexa arbitraria, obtenemos un mapeo dual diferente que conserva la incidencia y las propiedades 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 arbitraria de Bregman. Así, 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 sesgadas de Jensen (véase Nielsen y Boltz, 2011). Las divergencias de Jensen se pueden generalizar utilizando la convexidad comparativa, y los casos límite de estas generalizaciones sesgadas de las divergencias de Jensen producen una divergencia de Bregman generalizada (ver Nielsen y Nock, 2017). La divergencia de cuerdas de Bregman [6] se obtiene tomando una cuerda en lugar de una recta 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 error cuadrático total, entropía relativa y sesgo al cuadrado; 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, 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 submodulares de Bregman incluyen 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 & Bilmes, 2012 para obtener más detalles y propiedades del Bregman submodular).
Para obtener una lista de divergencias de Bregman matriciales comunes, consulte la Tabla 15.1 en [7]
Aplicaciones
En el aprendizaje automático, las divergencias de Bregman se utilizan para calcular la pérdida logística bitemperada, y funcionan mejor que la función softmax con conjuntos de datos ruidosos. [8]
^ ab "Aprender con las divergencias de Bregman" (PDF) . utexas.edu . Consultado el 19 de agosto de 2023 .
^ Adamčík, Martín (2014). "La geometría de la información de las divergencias de Bregman y algunas aplicaciones en el razonamiento de múltiples expertos". Entropía . 16 (12): 6338–6381. Código Bib : 2014Entrp..16.6338A. doi : 10.3390/e16126338 .
^ 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 polinómicas exponenciales". Entropía . 23 (11): 1417. arXiv : 2107.05901 . Código Bib : 2021Entrp..23.1417N. doi : 10.3390/e23111417 . ISSN 1099-4300. PMC 8619509 . PMID 34828115.
^ 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.
^ ab Jiao, Jiantao; Corteda, Thomas; No, Alberto; Venkat, Kartik; Weissman, Tsachy (diciembre de 2014). "Medidas de información: el curioso caso del alfabeto binario". Transacciones IEEE sobre teoría de la información . 60 (12): 7616–7626. arXiv : 1404.6810 . doi :10.1109/TIT.2014.2360184. ISSN 0018-9448. S2CID 13108908.
^ Nielsen, Frank; Nock, Richard (2019). "La divergencia de acordes de Bregman". Ciencia Geométrica de la Información . Apuntes de conferencias sobre informática. vol. 11712, págs. 299–308. arXiv : 1810.09113 . doi :10.1007/978-3-030-26980-7_31. ISBN978-3-030-26979-1. S2CID 53046425.
^ "Geometría de información matricial", R. Nock, B. Magdalou, E. Briys y F. Nielsen, pdf, de este libro
^ Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren (2019). "Pérdida logística robusta de doble temperamento basada en divergencias de Bregman". Jornada sobre Sistemas de Procesamiento de Información Neural. págs. 14987-14996. pdf
Bregman, LM (1967). "El método de relajación para encontrar los puntos comunes de conjuntos convexos y su aplicación a la solución de problemas en programación convexa". Matemática Computacional y Física Matemática de la URSS . 7 (3): 200–217. doi :10.1016/0041-5553(67)90040-7.
Frigyik, Bela A.; Srivastava, Santosh; Gupta, Maya R. (2008). "Divergencias funcionales de Bregman y estimación bayesiana de distribuciones" (PDF) . Transacciones IEEE sobre teoría de la información . 54 (11): 5130–5139. arXiv : cs/0611123 . doi :10.1109/TIT.2008.929943. S2CID 1254. Archivado desde el original (PDF) el 12 de agosto de 2010.
Frigyik, Bela A.; Srivastava, Santosh; Gupta, Maya R. (2008). Introducción a los derivados funcionales (PDF) . Informe técnico UWEE 2008-0001. Universidad de Washington, Departamento de Ingeniería Eléctrica. Archivado desde el original (PDF) el 17 de febrero de 2017 . Consultado el 20 de marzo de 2014 .
Harremoës, Peter (2017). "Divergencia y suficiencia para la optimización convexa". Entropía . 19 (5): 206. arXiv : 1701.01010 . Código Bib : 2017Entrp..19..206H. doi : 10.3390/e19050206 .
Nielsen, Frank; Nock, Richard (2009). "Los diagramas duales de Voronoi con respecto a las divergencias representacionales de Bregman" (PDF) . Proc. VI Simposio Internacional sobre Diagramas de Voronoi . IEEE. doi :10.1109/ISVD.2009.15.
Nielsen, Frank; Nock, Richard (2007). "Sobre los centroides de divergencias de Bregman simetrizadas". arXiv : 0711.3242 [cs.CG].
Nielsen, Frank; Boissonnat, Jean-Daniel; Nock, Richard (2007). "Sobre la visualización de diagramas de Bregman Voronoi". Proc. 23º Simposio ACM sobre Geometría Computacional (pista de vídeo) . doi :10.1145/1247069.1247089.[ enlace muerto permanente ]
Nielsen, Frank; Nock, Richard (2006). "Sobre la aproximación de las bolas de Bregman envolventes más pequeñas". Proc. 22º Simposio ACM sobre Geometría Computacional . págs. 485–486. doi :10.1145/1137856.1137931.
Nielsen, Frank; Nock, Richard (2017). "Generalización de divergencias sesgadas de Jensen y divergencias de Bregman con convexidad comparativa". Cartas de procesamiento de señales IEEE . 24 (8): 1123–1127. arXiv : 1702.04877 . Código Bib : 2017ISPL...24.1123N. doi :10.1109/LSP.2017.2712195. S2CID 31899023.