Bragman Divergens

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 november 2021; kontroller kräver 2 redigeringar .

Bragman divergens eller Bragman divergens är ett mått på avståndet mellan två punkter , definierat i termer av en strikt konvex funktion . De utgör en viktig klass av divergenser . Om punkterna tolkas som en sannolikhetsfördelning , antingen som värden av en parametrisk modell , eller som en uppsättning observerade värden, så är det resulterande avståndet ett statistiskt avstånd . Den mest elementära Bragman-divergensen är det kvadratiska euklidiska avståndet .

Bragman-divergenser liknar metrik , men tillfredsställer inte vare sig triangelolikheten eller symmetri (i det allmänna fallet), men de tillfredsställer den generaliserade Pythagoras teorem . I informationsgeometri ] tolkas motsvarande statistiska grenrör som ett platt grenrör (eller dual). Detta gör att många optimeringstekniker kan generaliseras till Bragman-divergens, vilket geometriskt motsvarar en generalisering av minsta kvadratmetoden .

Bragman-divergensen är uppkallad efter Lev Meerovich Bragman , som föreslog konceptet 1967.

Definition

Låta vara en kontinuerligt differentierbar strikt konvex funktion definierad på en sluten konvex uppsättning . $F:\Omega \to \mathbb {R}$ $\Omega$

Bragman-avståndet som är associerat med funktionen F för punkter är skillnaden mellan värdet på funktionen F i punkt p och värdet på första ordningens Taylor-expansion av funktionen F i punkt q , beräknat i punkt p : $p,q\in \Omega$

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

Egenskaper

Icke- negativitet : för alla p, q. Detta är en konsekvens av konvexiteten hos F. $D_{F}(p,q)\geqslant 0$
Konvexitet : Funktionen är konvex i det första argumentet, men inte nödvändigtvis konvex i det andra (se artikel av Bauschke och Borwein [1] ) $D_{F}(p,q)$
Linjäritet : Om vi betraktar Bragman-avståndet som en operator för funktionen F , så är det linjärt med avseende på icke-negativa koefficienter. Med andra ord, för strikt konvexa och differentierbara och , ${\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 ett konvext konjugat . Bragman-avståndet som definieras för är relaterat till $F^{*}$ $F^{*}$ $D_{F}(p,q)$

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

Här och är de dubbla punkterna som motsvarar p och q.

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

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

Betyder åtminstone : Nyckelresultatet om Bragman-divergens är att givet en slumpmässig vektor, minimerar medelvärdet av vektorerna den förväntade Bragman- divergensen från den slumpmässiga vektorn. Detta resultat generaliserar läroboksresultatet att det uppställda medelvärdet minimerar det totala kvadratiska felet för elementen i mängden. Detta resultat bevisades för fallet med vektorer av Banerjee et al . [2] och utvidgades till fallet med funktioner/distributioner av Fridjik et al . [3] .

Exempel

Det kvadratiska euklidiska avståndet är det kanoniska exemplet på Bragman-avståndet som bildas av den konvexa funktionen ${\displaystyle D_{F}(x,y)=\|xy\|^{2))$ ${\displaystyle F(x)=\|x\|^{2))$
Fyrkanten på Mahalanobis-avståndet , som bildas av en konvex funktion . Detta kan ses som en generalisering av det kvadratiska euklidiska avståndet ovan. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Generaliserad Kullback-Leibler divergens

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

bildas av den negativa entropifunktionen

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

Avstånd Itakura-Saito ,

D_{F}(p,q)=\summa _{i}\left({\frac {p(i)}{q(i)))-\log {\frac {p(i)} {q(i)}}-1\höger)

generaliserad av en konvex funktion

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

Generalisering av projektiv dualitet

Ett nyckelverktyg inom beräkningsgeometri är idén om projektiv dualitet , som kartlägger punkter till hyperplanet och vice versa samtidigt som förekomsten och ovan/under-relationerna bibehålls. Det finns många typer av projektiv dualitet - den vanliga formen mappar en punkt till ett hyperplan . Denna mappning kan förstås (om vi identifierar hyperplanet med normalen) som en konvex konjugatavbildning som tar punkten p till dubbelpunkten , där F definierar en d -dimensionell paraboloid . $p=(p_{1},\ldots p_{d})$ ${\displaystyle x_{d+1}=\summa _{1}^{d}2p_{i}x_{i))$ $p^{*}=\nabla F(p)$ $x_{d+1}=\summa x_{i}^{2}$

Om vi nu ersätter paraboloiden med någon konvex funktion får vi ytterligare en dubbel mappning som bevarar incidensen och ovan/under-egenskaperna för den standardprojektiva dualiteten. Det följer av detta att naturliga dubbla begrepp av beräkningsgeometri, som Voronoi-diagrammet och Delaunay-trianguleringarna , behåller sitt värde i utrymmen med ett avstånd som definieras av en godtycklig Bragman-divergens. Algoritmer för "normal" geometri sträcker sig naturligt till dessa utrymmen [4] .

Generaliseringar av Bragman-divergensen

Bragman-divergenser kan tolkas som begränsande fall av Jensen-skew-divergenser [5] (se uppsatsen av Nielsen och Bolz [6] ). Jensen-divergenser kan generaliseras med hjälp av jämförande konvexitet, och generalisering av gränsfallen för dessa skeva Jensen-divergenser leder till generaliserade Bragman-divergenser (se uppsatsen av Nielsen och Nock [7] ). Den ackordala divergensen för Bragman [8] erhålls genom att ta ett ackord istället för en tangent.

Bragman divergens på andra objekt

Bragman-divergens kan definieras för matriser, funktioner och mått (fördelningar). Bragman-divergensen för matriser inkluderar Stein-förlustfunktionen [9] och Neumann-entropin . Bragman-divergenser för funktioner inkluderar totalt kvadratfel, relativ entropi och kvadratisk bias (se Frigik et al . [3] nedan för definitioner och egenskaper). På liknande sätt definieras Bragman-divergensen också för mängder med hjälp av den submodulära uppsättningsfunktionen , känd som den diskreta analogen till den konvexa funktionen . Submodulär Bragman-divergens inkluderar ett antal diskreta mått som Hamming-avstånd , precision och återkallelse , ömsesidig information och några andra avståndsmått på uppsättningar (se Ayer och Bilmes [10] för detaljer och egenskaper för submodulär Bragman-divergens).

En lista över vanliga Bragman-matrisdivergenser finns i tabell 15.1 i artikeln av Nock, Magdalow, Bryce, Nielsen [11] .

Applikationer

Inom maskininlärning används Bragman-divergens för att beräkna en modifierad logistisk felfunktion som presterar bättre än softmax på bullriga data [12] .

Anteckningar

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ Namnet Jensen-Shannon Divergence har slagit rot i ryskspråkig litteratur , även om Jensen är en dansk och bör läsas på danska, inte på engelska. 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].
↑ För termen Steins förlust, se https://www.jstor.org/stable/2241373?seq=1 Arkiverad 17 november 2020 på Wayback Machine
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , sid. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , sid. 14987-14996.

Litteratur

H. Bauschke, J. Borwein. Gemensam och separat konvexitet för Bregman-avståndet // 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. Bryt matrisdata med Bregman MatrixDivergences för portföljval // Matrix Information Geometry . — 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Robust tvåtempererad logistisk förlust baserad på Bregman-avvikelser // Konferens om neurala informationsbehandlingssystem . — 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 Avslappningsmetod för att hitta en gemensam punkt för konvexa uppsättningar och dess tillämpning för att lösa problem med konvex programmering // Zh. Vychisl. matte.och matte. fiz. - 1967. - V. 7 , nr 3 .
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Funktionella Bregman-divergenser och Bayesiansk uppskattning av distributioner // IEEE-transaktioner på informationsteori . - 2008. - T. 54 , nr. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Arkiverad från originalet den 12 augusti 2010.
Rishabh Iyer, Jeff Bilmes. Submodulära-Bregman-divergenser och Lovász-Bregman-divergenser med Applications // . — 2012.
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. En introduktion till funktionella derivat . - University of Washington, avd. of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergens och tillräcklighet för konvex optimering // Entropi. - 2017. - T. 19 , nr. 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. De dubbla Voronoi-diagrammen med avseende på representativa Bregman-divergenser // Proc. Sjätte internationella symposiet om Voronoi-diagram . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. Om tyngdpunkterna för symmetriserade Bregman-divergenser . – 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. Om visualisering av Bregman Voronoi-diagram // Proc. 23:e ACM Symposium on Computational Geometry (videospår) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoi-diagram // Diskret och beräkningsgeometri . - 2010. - T. 44 , nr. 2 . — S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. På att approximera de minsta omslutande Bregman Balls // Proc. 22:a ACM-symposiet om beräkningsgeometri. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. Burbea-Rao och Bhattacharyya centroids // IEEE Transactions on Information Theory . - 2011. - T. 57 , nr. 8 . — S. 5455–5466 . - doi : 10.1109/TIT.2011.2159046 . - arXiv : 1004.5049 .
Frank Nielsen, Richard Nock. Generalisering av skev Jensen-divergenser och Bregman-divergenser med jämförande konvexitet // IEEE-signalbearbetningsbokstäver . - 2017. - T. 24 , nr. 8 . — S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - . - arXiv : 1702.04877 .