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 distancia 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 del triángulo (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 (doble) 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 mínimos cuadrados .
Las divergencias de Bregman llevan el nombre de Lev M. Bregman , quien introdujo el concepto en 1967.
Definición
Dejar ser una función estrictamente convexa , continuamente diferenciable, definida en un conjunto convexo cerrado .
La distancia de Bregman asociada con F para puntoses la diferencia entre el valor de F en el punto py 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 todo p, q. Esta es una consecuencia de la convexidad de F.
- Convexidad :es convexo en su primer argumento, pero no necesariamente en el segundo argumento (ver [1] )
- Linealidad : si pensamos en la distancia de Bregman como un operador en la función F , entonces es lineal con respecto a los coeficientes no negativos. En otras palabras, para estrictamente convexo y diferenciable, y ,
- Dualidad : la función F tiene un conjugado convexo . La distancia de Bregman definida con respecto a tiene una relación interesante con
- Aquí, y son los puntos duales correspondientes ap y q.
- 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 probado para el caso del vector 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 representante de un conjunto aleatorio, particularmente en la estimación bayesiana.
Ejemplos de
- Distancia euclidiana al cuadrado es el ejemplo canónico de una distancia de Bregman, generada por la función convexa
- La distancia de Mahalanobis al cuadrado , que es generado por la función convexa . Esto se puede considerar como una generalización de la distancia euclidiana al cuadrado anterior.
- La divergencia generalizada de Kullback-Leibler
- es generado por la función de entropía negativa
- es generado por la función convexa
Generalizando la dualidad proyectiva
Una herramienta clave en geometría computacional es la idea de dualidad proyectiva , que mapea 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 mapea 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 los 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 de Jensen sesgadas (véase Nielsen y Boltz, 2011). Las divergencias de Jensen se pueden generalizar usando convexidad comparativa, y los casos límite de estas generalizaciones de divergencias de Jensen sesgadas producen divergencias de Bregman generalizadas (ver Nielsen y Nock, 2017). La divergencia del acorde de Bregman [2] 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; véanse 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 submodular subsumen una serie de medidas de distancia discretas, como la distancia de Hamming , precisión y recuperación , información mutua y algunas otras medidas de distancia basadas en conjuntos (ver Iyer y Bilmes, 2012) para obtener más detalles y propiedades del Bregman submodular).
Para obtener una lista de las divergencias de Bregman de la matriz común, consulte la Tabla 15.1 en. [3]
Aplicaciones
En el aprendizaje automático, las divergencias de Bregman se utilizan para calcular la pérdida logística bitemperada , con un rendimiento mejor que la función softmax con conjuntos de datos ruidosos. [4]
Referencias
- ^ "Convexidad conjunta y separada de la distancia de Bregman", por H. Bauschke y J. Borwein, en D. Butnariu, Y. Censor y S. Reich, editores, Algoritmos inherentemente paralelos en viabilidad y optimización y sus aplicaciones , Elsevier 2001
- ^ Nielsen, Frank; Nock, Richard (2018). "La divergencia de acordes de Bregman". arXiv : 1810.09113 [ cs.LG ].
- ^ "Geometría de la información de la matriz", R. Nock, B. Magdalou, E. Briys y F. Nielsen, pdf , de este libro
- ^ Ehsan en medio, Manfred K. Warmuth, Rohan Anil, Tomer Koren (2019). "Robusta pérdida logística bitemperada basada en divergencias de Bregman". Conferencia sobre sistemas de procesamiento de información neuronal. págs. 14987-14996. pdf
- Banerjee, Arindam; Merugu, Srujana; Dhillon, Inderjit S .; Ghosh, Joydeep (2005). "Agrupación con divergencias de Bregman" . Revista de investigación sobre aprendizaje automático . 6 : 1705-1749.
- 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". URSS Matemáticas Computacionales y Física Matemática . 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 . Archivado desde el original (PDF) el 12 de agosto de 2010.
- Iyer, Rishabh .; Bilmes, Jeff (2012). "Divergencias submodular-Bregman y divergencias Lovász-Bregman con aplicaciones". Conferencia sobre sistemas de procesamiento de información neuronal .
- Frigyik, Bela A .; Srivastava, Santosh; Gupta, Maya R. (2008). Introducción a las derivadas funcionales (PDF) . Informe técnico de 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 . Bibcode : 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. 6º Simposio Internacional de Diagramas de Voronoi . IEEE. doi : 10.1109 / ISVD.2009.15 .
- Nielsen, Frank; Nock, Richard (2007). "Sobre los centroides de las divergencias de Bregman simétrizadas". 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 video) . doi : 10.1145 / 1247069.1247089 .[ enlace muerto permanente ]
- Boissonnat, Jean-Daniel; Nielsen, Frank; Nock, Richard (2010). "Diagramas de Bregman Voronoi" . Geometría discreta y computacional . 44 (2): 281-307. arXiv : 0709.2196 . doi : 10.1007 / s00454-010-9256-1 .
- Nielsen, Frank; Nock, Richard (2006). "Aproximando las más pequeñas que encierran Bregman Balls". Proc. 22º Simposio ACM sobre Geometría Computacional . págs. 485–486. doi : 10.1145 / 1137856.1137931 .
- Nielsen, Frank; Boltz, Sylvain (2011). "Los centroides de Burbea-Rao y Bhattacharyya". Transacciones IEEE sobre teoría de la información . 57 (8): 5455–5466. arXiv : 1004.5049 . doi : 10.1109 / TIT.2011.2159046 .
- Nielsen, Frank; Nock, Richard (2017). "Generalizar las divergencias de Skew Jensen y las divergencias de Bregman con convexidad comparativa". Cartas de procesamiento de señales IEEE . 24 (8): 1123–1127. arXiv : 1702.04877 . Código Bibliográfico : 2017ISPL ... 24.1123N . doi : 10.1109 / LSP.2017.2712195 .