Bragman-divergens

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. november 2021; checks kræver 2 redigeringer .

Bragman- divergens eller Bragman-afstand er et mål for afstanden mellem to punkter , defineret som en strengt konveks funktion . De udgør en vigtig klasse af divergenser . Hvis punkterne fortolkes som en sandsynlighedsfordeling , enten som værdier af en parametrisk model , eller som et sæt af observerede værdier, så er den resulterende afstand en statistisk afstand . Den mest elementære Bragman-divergens er den kvadrerede euklidiske afstand .

Bragman-divergenser ligner metrik , men opfylder hverken trekantens ulighed eller symmetri (i det generelle tilfælde), men de opfylder den generaliserede Pythagoras sætning . I informationsgeometri ] fortolkes den tilsvarende statistiske manifold som en flad manifold (eller dobbelt). Dette gør det muligt at generalisere mange optimeringsteknikker til Bragman-divergens, hvilket svarer geometrisk til en generalisering af mindste kvadraters metode .

Bragman-divergensen er opkaldt efter Lev Meerovich Bragman , som foreslog konceptet i 1967.

Definition

Lade være en kontinuerligt differentierbar strengt konveks funktion defineret på et lukket konveks sæt . $F:\Omega \to \mathbb {R}$ $\Omega$

Bragman-afstanden forbundet med funktionen F for punkter er forskellen mellem værdien af funktionen F ved punkt p og værdien af førsteordens Taylor-udvidelse af funktionen F ved punkt q , beregnet ved punkt p : $p,q\in \Omega$

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

Egenskaber

Ikke -negativitet : for alle p, q. Dette er en konsekvens af konveksiteten af F. $D_{F}(p,q)\geqslant 0$
Konveksitet : Funktionen er konveks i det første argument, men ikke nødvendigvis konveks i det andet (se papir af Bauschke og Borwein [1] ) $D_{F}(p,q)$
Linearitet : Hvis vi betragter Bragman-afstanden som en operator af funktionen F , så er den lineær med hensyn til ikke-negative koefficienter. Med andre ord, for strengt konvekse og differentierbare og , ${\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)

Dualitet : Funktionen F har et konveks konjugat . Bragman-afstanden defineret for er relateret til $F^{*}$ $F^{*}$ $D_{F}(p,q)$

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

Her og er de dobbeltpunkter svarende til p og q.

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

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

Betyder i det mindste : Nøgleresultatet om Bragman-divergens er, at givet en tilfældig vektor, minimerer middelværdien af vektorerne den forventede Bragman- divergens fra den tilfældige vektor. Dette resultat generaliserer lærebogsresultatet, at det indstillede gennemsnit minimerer den totale kvadrerede fejl af sættets elementer. Dette resultat blev bevist for tilfældet med vektorer af Banerjee et al . [2] og udvidet til tilfældet med funktioner/distributioner af Fridjik et al . [3] .

Eksempler

Den kvadratiske euklidiske afstand er det kanoniske eksempel på Bragman-afstanden dannet af den konvekse funktion ${\displaystyle D_{F}(x,y)=\|xy\|^{2))$ ${\displaystyle F(x)=\|x\|^{2))$
Firkantet af Mahalanobis-afstanden , som er dannet ud fra en konveks funktion . Dette kan ses som en generalisering af den kvadratiske euklidiske afstand ovenfor. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Generaliseret Kullback-Leibler divergens

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

dannes af den negative entropifunktion

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

Afstand Itakura-Saito ,

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

generaliseret af en konveks funktion

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

Generalisering af projektiv dualitet

Et nøgleværktøj inden for beregningsgeometri er ideen om projektiv dualitet , som kortlægger punkter til hyperplanet og omvendt, samtidig med at forekomsten og over/under-relationerne bevares. Der er mange typer af projektiv dualitet - den sædvanlige form kortlægger et punkt til et hyperplan . Denne afbildning kan forstås (hvis vi identificerer hyperplanet med normalen) som en konveks konjugeret afbildning, der tager punktet p til dobbeltpunktet , hvor F definerer en d - dimensionel 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))$

Hvis vi nu erstatter paraboloiden med en hvilken som helst konveks funktion, får vi endnu en dobbelt mapping, der bevarer incidensen og over/under egenskaberne for den standard projektive dualitet. Det følger heraf, at naturlige dobbeltbegreber for beregningsgeometri, som Voronoi-diagrammet og Delaunay-trianguleringerne , bevarer deres værdi i rum med en afstand defineret af en vilkårlig Bragman-divergens. Algoritmer med "normal" geometri strækker sig naturligt til disse rum [4] .

Generaliseringer af Bragman-divergensen

Bragman-divergenser kan tolkes som begrænsende tilfælde af Jensen-skæv-divergenser [5] (se avisen af Nielsen og Bolz [6] ). Jensen-divergenser kan generaliseres ved hjælp af komparativ konveksitet, og generalisering af grænsetilfældene for disse skæve Jensen-divergenser fører til generaliserede Bragman-divergenser (se papiret af Nielsen og Nock [7] ). Den akkordale divergens af Bragman [8] opnås ved at tage en akkord i stedet for en tangent.

Bragman divergens på andre objekter

Bragman-divergens kan defineres for matricer, funktioner og mål (fordelinger). Bragman-divergensen for matricer inkluderer Stein-tabsfunktionen [9] og Neumann-entropien . Bragman-divergenser for funktioner omfatter total kvadratisk fejl, relativ entropi og kvadratisk bias (se Frigik et al . [3] nedenfor for definitioner og egenskaber). Tilsvarende er Bragman-divergensen også defineret for mængder ved hjælp af den submodulære sætfunktion , kendt som den diskrete analog af den konvekse funktion . Submodulær Bragman-divergens inkluderer en række diskrete mål såsom Hamming-afstand , præcision og genkald , gensidig information og nogle andre afstandsmål på sæt (se Ayer og Bilmes [10] for detaljer og egenskaber ved submodulær Bragman-divergens).

En liste over almindelige Bragman matrix divergenser kan findes i Tabel 15.1 i artiklen af Nock, Magdalow, Bryce, Nielsen [11] .

Ansøgninger

I maskinlæring bruges Bragman divergens til at beregne en modificeret logistisk fejlfunktion, der yder bedre end softmax på støjende data [12] .

Noter

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ Navnet Jensen-Shannon Divergence har slået rod i russisksproget litteratur , selvom Jensen er dansker og bør læses på dansk, ikke på engelsk. Wikipedia har en artikel om Jensen .
↑ Nielsen, Boltz, 2011 .
↑ Nielsen, Nock, 2017 .
↑ Nielsen, Frank & Nock, Richard (2018), The Bregman chord divergence, arΧiv : 1810.09113 [cs.LG].
↑ For udtrykket Steins tab, se https://www.jstor.org/stable/2241373?seq=1 Arkiveret 17. november 2020 på Wayback Machine
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , s. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , s. 14987-14996.

Litteratur

H. Bauschke, J. Borwein. Fælles og separat konveksitet af Bregman-distancen // Inherently Parallel Algorithms in Feasibility and Optimization and their Applications / D. Butnariu, Y. Censor, S. Reich (redaktører). — Elsevier, 2001.
R. Nock, B. Magdalou, E. Briys, F. Nielsen. Mining af matrixdata med Bregman MatrixDivergences til porteføljevalg // Matrixinformationsgeometri . – 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Robust Bi-tempereret logistisk tab baseret på Bregman divergenser // Konference om neurale informationsbehandlingssystemer . – 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Clustering med Bregman divergenser // Journal of Machine Learning Research . - 2005. - T. 6 . - S. 1705-1749 .
Bragman LM Afslapningsmetode til at finde et fælles punkt for konvekse sæt og dets anvendelse til at løse problemer med konveks programmering // Zh. Vychisl. matematik.og matematik. fiz. - 1967. - V. 7 , nr. 3 .
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Funktionelle Bregman-divergenser og Bayesiansk estimering af distributioner // IEEE-transaktioner på informationsteori . - 2008. - T. 54 , no. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Arkiveret fra originalen den 12. august 2010.
Rishabh Iyer, Jeff Bilmes. Submodulære-Bregman divergenser og Lovász-Bregman divergenser med Applications // . – 2012.
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. En introduktion til funktionelle derivater . - University of Washington, afd. of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergens og tilstrækkelighed til konveks optimering // Entropi. - 2017. - T. 19 , no. 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. De dobbelte Voronoi-diagrammer med hensyn til repræsentative Bregman-divergenser // Proc. 6. internationale symposium om Voronoi-diagrammer . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. Om tyngdepunkterne af symmetriserede Bregman-divergenser . – 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. Om visualisering af Bregman Voronoi-diagrammer // Proc. 23. ACM-symposium om beregningsgeometri (videospor) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoi-diagrammer // Diskret og beregningsgeometri . - 2010. - T. 44 , no. 2 . — S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. Ved tilnærmelse af de mindste omsluttende Bregman Balls // Proc. 22. ACM-symposium om beregningsgeometri. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. Burbea-Rao og Bhattacharyya centroiderne // IEEE Transaktioner på informationsteori . - 2011. - T. 57 , no. 8 . — S. 5455–5466 . - doi : 10.1109/TIT.2011.2159046 . - arXiv : 1004.5049 .
Frank Nielsen, Richard Nock. Generalisering af skæv Jensen divergenser og Bregman divergenser med sammenlignende konveksitet // IEEE Signal Processing Letters . - 2017. - T. 24 , no. 8 . — S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - . - arXiv : 1702.04877 .