Bragmanova divergence

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. listopadu 2021; kontroly vyžadují 2 úpravy .

Bragmanova divergence nebo Bragmanova vzdálenost je míra vzdálenosti mezi dvěma body , definovaná v podmínkách přísně konvexní funkce . Tvoří důležitou třídu divergencí . Pokud jsou body interpretovány jako rozdělení pravděpodobnosti , buď jako hodnoty parametrického modelu , nebo jako soubor pozorovaných hodnot, pak výsledná vzdálenost je statistická vzdálenost . Nejzákladnější Bragmanova divergence je kvadratická euklidovská vzdálenost .

Bragmanovy divergence jsou podobné metrikám , ale nesplňují ani trojúhelníkovou nerovnost , ani symetrii (v obecném případě), ale splňují zobecněnou Pythagorovu větu . V informační geometrii je odpovídající statistická varieta interpretována jako plochá varieta (nebo duální). To umožňuje mnoho optimalizačních technik zobecnit na Bragmanovu divergenci, která geometricky odpovídá zobecnění metody nejmenších čtverců .

Bragmanova divergence je pojmenována po Levu Meeroviči Bragmanovi , který tento koncept navrhl v roce 1967.

Definice

Dovolit je spojitě diferencovatelná přísně konvexní funkce definovaná na uzavřené konvexní množině . $F:\Omega \to \mathbb {R}$ $\Omega$

Bragmanova vzdálenost spojená s funkcí F pro body je rozdíl mezi hodnotou funkce F v bodě p a hodnotou Taylorova rozvoje prvního řádu funkce F v bodě q , vypočtené v bodě p : $p,q\in \Omega$

D_{F}(p,q)=F(p)-F(q)-\langle \nabla F(q),pq\rangle .

Vlastnosti

Nezápornost : pro všechna p, q. To je důsledek konvexnosti F. $D_{F}(p,q)\geqslant 0$
Konvexnost : Funkce je konvexní v prvním argumentu, ale nemusí nutně konvexní ve druhém (viz článek Bauschkeho a Borweina [1] ) $D_{F}(p,q)$
Linearita : Uvažujeme-li Bragmanovu vzdálenost jako operátor funkce F , pak je lineární s ohledem na nezáporné koeficienty. Jinými slovy, pro přísně konvexní a diferencovatelné a , ${\displaystyle F_{1},F_{2))$ $\lambda \geqslant 0$

D_{F_{1}+\lambda F_{2}}(p,q)=D_{F_{1}}(p,q)+\lambda D_{F_{2}}(p,q)

Dualita : Funkce F má konvexní konjugát . Bragmanova vzdálenost definovaná pro souvisí s $F^{*}$ $F^{*}$ $D_{F}(p,q)$

D_{F^{*}}(p^{*},q^{*})=D_{F}(q,p)

Zde jsou duální body odpovídající p a q.

p^{*}=\nabla F(p)

q^{*}=\nabla F(q)

Přinejmenším průměr : Klíčovým výsledkem o Bragmanově divergenci je, že daný náhodný vektor, průměr vektorů minimalizuje očekávanou Bragmanovu divergenci od náhodného vektoru. Tento výsledek zobecňuje učebnicový výsledek, že množinový průměr minimalizuje celkovou druhou mocninu prvků množiny. Tento výsledek byl prokázán pro případ vektorů Banerjee et al [2] a rozšířen na případ funkcí/distribucí Fridjikem et al [3] .

Příklady

Druhá mocnina euklidovské vzdálenosti je kanonický příklad Bragmanovy vzdálenosti tvořené konvexní funkcí ${\displaystyle D_{F}(x,y)=\|xy\|^{2))$ ${\displaystyle F(x)=\|x\|^{2))$
Druhá mocnina Mahalanobisovy vzdálenosti , která je tvořena konvexní funkcí . Toto může být viděno jako zobecnění druhé mocniny euklidovské vzdálenosti nahoře. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Generalizovaná Kullback-Leiblerova divergence

D_{F}(p,q)=\součet _{i}p(i)\log {\frac {p(i)}{q(i)))-\součet p(i)+\ součet q(i)

je tvořena funkcí negativní entropie

F(p)=\sum _{i}p(i)\log p(i)

Vzdálenost Itakura-Saito ,

D_{F}(p,q)=\sum _{i}\left({\frac {p(i)}{q(i)))-\log {\frac {p(i)} {q(i)}}-1\vpravo)

zobecněno konvexní funkcí

F(p)=-\sum _{i}\log p(i)

Zobecnění projektivní duality

Klíčovým nástrojem ve výpočetní geometrii je myšlenka projektivní duality , která mapuje body do nadroviny a naopak, přičemž stále zachovává vztahy incidence a nad/pod. Existuje mnoho typů projektivní duality – obvyklá forma mapuje bod do nadroviny . Toto zobrazení lze chápat (pokud nadrovinu ztotožníme s normálou) jako konvexní sdružené zobrazení, které vezme bod p do duálního bodu , kde F definuje d - rozměrný paraboloid . $p=(p_{1},\ldots p_{d})$ ${\displaystyle x_{d+1}=\sum _{1}^{d}2p_{i}x_{i))$ $p^{*}=\nabla F(p)$ ${\displaystyle x_{d+1}=\sum x_{i}^{2))$

Pokud nyní nahradíme paraboloid jakoukoli konvexní funkcí, získáme další duální zobrazení, které zachová incidenci a vlastnosti nad/pod standardní projektivní dualitou. Z toho vyplývá, že přirozené duální koncepty výpočetní geometrie, jako Voronoiův diagram a Delaunayovy triangulace , si zachovávají svou hodnotu v prostorech se vzdáleností definovanou libovolnou Bragmanovou divergenci. Algoritmy "normální" geometrie se přirozeně rozšiřují i do těchto prostorů [4] .

Zobecnění Bragmanovy divergence

Bragmanovy divergence lze interpretovat jako limitující případy Jensenových skew divergencí [5] (viz článek Nielsena a Bolze [6] ). Jensenovy divergence lze zobecnit pomocí komparativní konvexity a zobecnění limitních případů těchto zkreslených Jensenových divergencí vede ke zobecněným Bragmanovým divergencím (viz článek Nielsena a Nocka [7] ). Tetivová divergence Bragmana [8] se získá tak, že místo tečny vezmeme akord.

Bragmanova divergence na jiných objektech

Bragmanovu divergenci lze definovat pro matice, funkce a míry (rozdělení). Bragmanova divergence pro matice zahrnuje Steinovou ztrátovou funkci [9] a Neumannovu entropii . Bragmanovy divergence pro funkce zahrnují úplnou druhou mocninu chyby, relativní entropii a druhou mocninu (viz Frigik et al . [3] níže pro definice a vlastnosti). Podobně je Bragmanova divergence definována také pro množiny pomocí submodulární množinové funkce , známé jako diskrétní analogie konvexní funkce . Submodulární Bragmanova divergence zahrnuje řadu diskrétních měření, jako je Hammingova vzdálenost , přesnost a vyvolání , vzájemná informace a některé další míry vzdálenosti na množinách ( podrobnosti a vlastnosti submodulární Bragmanovy divergence viz Ayer a Bilmes [10] ).

Seznam běžných divergenci Bragmanovy matice lze nalézt v tabulce 15.1 v článku Nocka, Magdalow, Bryce, Nielsena [11] .

Aplikace

Ve strojovém učení se Bragmanova divergence používá k výpočtu modifikované logistické chybové funkce, která funguje lépe než softmax na zašuměných datech [12] .

Poznámky

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ Název Jensen-Shannon Divergence zakořenil v ruskojazyčné literatuře , ačkoli Jensen je Dán a měl by se číst v dánštině, nikoli v angličtině. Wikipedia má článek o Jensenovi .
↑ Nielsen, Boltz, 2011 .
↑ Nielsen, Nock, 2017 .
↑ Nielsen, Frank & Nock, Richard (2018), The Bregman akord divergence, arΧiv : 1810.09113 [cs.LG].
↑ Termín Steinova ztráta viz https://www.jstor.org/stable/2241373?seq=1 Archivováno 17. listopadu 2020 na Wayback Machine
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , str. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , str. 14987-14996.

Literatura

H. Bauschke, J. Borwein. Společná a oddělená konvexita Bregmanovy vzdálenosti // Inherentně paralelní algoritmy ve proveditelnosti a optimalizaci a jejich aplikace / D. Butnariu, Y. Censor, S. Reich (editoři). — Elsevier, 2001.
R. Nock, B. Magdalou, E. Briys, F. Nielsen. Těžba maticových dat pomocí Bregmanových maticových divergenci pro výběr portfolia // maticová informační geometrie . — 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Robustní bi-temperované logistické ztráty založené na Bregmanových rozdílech // Konference o systémech zpracování neuronových informací . — 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Shlukování s Bregmanovými divergencemi // Journal of Machine Learning Research . - 2005. - T. 6 . - S. 1705-1749 .
Bragman LM Relaxační metoda pro nalezení společného bodu konvexních množin a její aplikace při řešení problémů konvexního programování // Zh. Vychisl. matematika.a matematika. fiz. - 1967. - V. 7 , č. 3 .
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Funkční Bregmanovy divergence a Bayesovský odhad distribucí // Transakce IEEE na teorii informace . - 2008. - T. 54 , č. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Archivováno z originálu 12. srpna 2010.
Rishabh Iyer, Jeff Bilmes. Submodulární-Bregmanovy divergence a Lovász-Bregmanovy divergence s aplikacemi // . — 2012.
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Úvod do funkčních derivátů . — University of Washington, Dept. of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergence a dostatečnost pro konvexní optimalizaci // Entropie. - 2017. - T. 19 , no. 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. Duální Voronoiovy diagramy s ohledem na reprezentativní Bregmanovy divergence // Proc. 6. mezinárodní symposium o Voronoiových diagramech . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. O centroidech symetrických Bregmanových divergenci . — 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. O vizualizaci Bregman Voronoi diagramů // Proc. 23. sympozium ACM o počítačové geometrii (video stopa) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoiovy diagramy // Diskrétní a výpočetní geometrie . - 2010. - T. 44 , č. 2 . — S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. O aproximaci nejmenších obklopujících koulí Bregman // Proc. 22. sympozium ACM o počítačové geometrii. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. Centroidy Burbea-Rao a Bhattacharyya // IEEE Transactions on Information Theory . - 2011. - T. 57 , č.p. 8 . — S. 5455–5466 . - doi : 10.1109/TIT.2011.2159046 . - arXiv : 1004.5049 .
Frank Nielsen, Richard Nock. Generalizing Skew Jensen Divergences and Bregman Divergences with Comparative Convexity // IEEE Signal Processing Letters . - 2017. - T. 24 , no. 8 . — S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - . - arXiv : 1702.04877 .