Bragman eltérés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 20-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Bragman- divergencia vagy a Bragman-távolság két pont közötti távolság mértéke , amelyet szigorúan konvex függvényként határozunk meg. Az eltérések fontos osztályát. Ha a pontokat valószínűségi eloszlásként értelmezzük , akár egy parametrikus modell értékeként , akár megfigyelt értékek halmazaként, akkor a kapott távolság egy statisztikai távolság . A legelemibb Bragman-divergencia a négyzetes euklideszi távolság .

A Bragman-divergencia hasonló a metrikákhoz , de nem teljesíti sem a háromszög-egyenlőtlenséget , sem a szimmetriát (általános esetben), de kielégíti az általánosított Pitagorasz-tételt . Az információgeometriában a megfelelő statisztikai sokaságot lapos sokaságként (vagy kettősként) értelmezzük . Ez lehetővé teszi számos optimalizálási technikának a Bragman-divergencia általánosítását, amely geometriailag megfelel a legkisebb négyzetek módszerének általánosításának .

A Bragman-divergencia Lev Meerovich Bragman nevéhez fűződik , aki 1967-ben javasolta a koncepciót .

Definíció

Legyen egy folyamatosan differenciálható szigorúan konvex függvény egy zárt konvex halmazon . $F:\Omega \to \mathbb {R}$ $\Omega$

Az F függvényhez tartozó Bragman-távolság pontokhoz az F függvény p pontban lévő értéke és az F függvény q pontban lévő elsőrendű Taylor-kiterjesztésének értéke közötti különbség, amelyet a p pontban számítunk ki : $p,q\in \Omega$

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

Tulajdonságok

Nem- negativitás : minden p, q esetén. Ez az F konvexitásának következménye. $D_{F}(p,q)\geqslant 0$
Konvexitás : A függvény konvex az első argumentumban, de nem feltétlenül konvex a másodikban (lásd Bauschke és Borwein cikkét [1] ) $D_{F}(p,q)$
Linearitás : Ha a Bragman-távolságot az F függvény operátorának tekintjük , akkor az lineáris a nemnegatív együtthatókhoz képest. Más szavakkal, szigorúan konvex és differenciálható és , ${\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)

Dualitás : Az F függvény konvex konjugátummal rendelkezik . A számára definiált Bragman-távolság összefügg $F^{*}$ $F^{*}$ $D_{F}(p,q)$

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

Itt és a p-nek és q-nak megfelelő kettőspontok.

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

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

Átlag legalább : A Bragman-divergencia kulcsfontosságú eredménye az, hogy egy véletlen vektort adva a vektorok átlaga minimalizálja a várt Bragman eltérést a véletlen vektortól. Ez az eredmény általánosítja azt a tankönyvi eredményt, hogy a halmaz átlaga minimalizálja a halmaz elemeinek össznégyzetes hibáját. Ezt az eredményt a vektorok esetében Banerjee és munkatársai [2] igazolták, és Fridjik és munkatársai [3] kiterjesztették a függvények/eloszlások esetére .

Példák

A négyzetes euklideszi távolság a konvex függvény által alkotott Bragman-távolság kanonikus példája ${\displaystyle D_{F}(x,y)=\|xy\|^{2))$ ${\displaystyle F(x)=\|x\|^{2))$
A konvex függvényből képzett Mahalanobis távolság négyzete . Ez a fenti négyzetes euklideszi távolság általánosításának tekinthető. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Általánosított Kullback-Leibler eltérés

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

a negatív entrópiafüggvény alkotja

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

Távolság Itakura-Saito ,

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

konvex függvénnyel általánosítva

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

A projektív kettősség általánosítása

A számítási geometria egyik kulcsfontosságú eszköze a projektív kettősség ötlete , amely a pontokat a hipersíkra és fordítva képezi le, miközben továbbra is fenntartja az előfordulási és a feletti/alatti kapcsolatokat. A projektív kettősségnek sok fajtája létezik – a szokásos forma egy pontot egy hipersíkra képez le . Ez a leképezés felfogható (ha a hipersíkot a normállal azonosítjuk) konvex konjugált leképezésként, amely a p pontot a duális pontba viszi , ahol F egy d - dimenziós paraboloidot definiál . $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))$

Ha most a paraboloidot bármely konvex függvénnyel helyettesítjük, akkor egy másik duális leképezést kapunk, amely megőrzi a standard projektív dualitás előfordulási és feletti/alatti tulajdonságait. Ebből következik, hogy a számítási geometria természetes kettős fogalmai, mint például a Voronoi-diagram és a Delaunay-háromszögelés , megőrzik értéküket olyan terekben, amelyek távolságát egy tetszőleges Bragman-divergencia határozza meg. A "normál" geometria algoritmusai természetesen kiterjednek ezekre a terekre [4] .

A Bragman-divergencia általánosításai

A Bragman-divergencia a Jensen-féle ferde eltérések korlátozó eseteiként értelmezhető [5] (lásd Nielsen és Bolz tanulmányát [6] ). A Jensen-divergencia komparatív konvexitás segítségével általánosítható, és ezen ferde Jensen-divergencia határeseteinek általánosítása általánosított Bragman divergenciákhoz vezet (lásd Nielsen és Nock [7] tanulmányát ). A Bragman [8] akkorddivergensét úgy kapjuk meg, hogy érintő helyett akkordot veszünk.

Bragman eltérés más objektumokon

A Bragman-divergencia definiálható mátrixokra, függvényekre és mértékekre (eloszlásokra). A mátrixokra vonatkozó Bragman-divergencia magában foglalja a Stein-veszteségfüggvényt [9] és a Neumann-entrópiát . A függvények Bragman divergenciái közé tartozik a teljes négyzetes hiba, a relatív entrópia és a torzítás négyzet (lásd Frigik et al . [3] alább a definíciókat és tulajdonságokat). Hasonlóképpen, a Bragman-divergencia halmazokra is meghatározható a szubmoduláris halmazfüggvénnyel , amely a konvex függvény diszkrét analógjaként ismert . A szubmoduláris Bragman-divergencia számos diszkrét mértéket foglal magában, mint például a Hamming-távolságot , a pontosságot és a visszahívást , a kölcsönös információt és néhány más távolságmértéket a halmazokon ( a szubmoduláris Bragman-divergencia részleteit és tulajdonságait lásd Ayer és Bilmes [10] ).

A gyakori Bragman-mátrix eltérések listája a 15.1. táblázatban található Nock, Magdalow, Bryce, Nielsen cikkében [11] .

Alkalmazások

A gépi tanulásban a Bragman divergenciát egy módosított logisztikai hibafüggvény kiszámítására használják, amely zajos adatok esetén jobban teljesít, mint a softmax [12] .

Jegyzetek

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ A Jensen-Shannon Divergence név gyökeret vert az orosz nyelvű irodalomban , bár Jensen dán, és dánul kell olvasni, nem angolul. A Wikipédián van egy cikk Jensenről .
↑ Nielsen, Boltz, 2011 .
↑ Nielsen, Nock, 2017 .
↑ Nielsen, Frank & Nock, Richard (2018), The Bregman chord divergence, arΧiv : 1810.09113 [cs.LG].
↑ A Stein vesztesége kifejezést lásd: https://www.jstor.org/stable/2241373?seq=1 Archiválva : 2020. november 17., a Wayback Machine -nél
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , p. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , p. 14987-14996.

Irodalom

H. Bauschke, J. Borwein. A Bregman-távolság együttes és különálló konvexitása // Inherently Parallel Algorithms in Feasibility and Optimization and their Applications / D. Butnariu, Y. Censor, S. Reich (szerkesztők). – Elsevier, 2001.
R. Nock, B. Magdalou, E. Briys, F. Nielsen. Mátrixadatok bányászata a Bregman MatrixDivergences segítségével a portfólió kiválasztásához // Mátrix információs geometria . — 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Robusztus, kétirányú logisztikai veszteség a Bregman-divergencia alapján // Konferencia a Neurális információfeldolgozó rendszerekről . — 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Klaszterezés Bregman eltérésekkel // Journal of Machine Learning Research . - 2005. - T. 6 . - S. 1705-1749 .
Bragman LM Relaxációs módszer konvex halmazok közös pontjának megtalálására és alkalmazása konvex programozási problémák megoldására // Zh. Vychisl. matematika.és matek. fiz. - 1967. - V. 7 , 3. sz .
Béla A. Frigyik, Santosh Srivastava, Maya R. Gupta. Funkcionális Bregman eltérések és az eloszlások bayesi becslése // IEEE Transactions on Information Theory . - 2008. - T. 54 , sz. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Az eredetiből archiválva: 2010. augusztus 12.
Rishabh Iyer, Jeff Bilmes. Szubmoduláris-Bregman divergenciák és Lovász-Bregman divergenciák az Alkalmazásokkal // . — 2012.
Béla A. Frigyik, Santosh Srivastava, Maya R. Gupta. Bevezetés a funkcionális származékokba . — Washingtoni Egyetem, Dept. of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergencia és elégséges a konvex optimalizáláshoz // Entrópia. - 2017. - T. 19 , sz. 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. A kettős Voronoi-diagramok a reprezentatív Bregman-divergencia tekintetében // Proc. 6. Nemzetközi Szimpózium a Voronoi Diagramokról . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. A szimmetrikus Bregman-divergencia központjairól . – 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. A Bregman Voronoi diagramok megjelenítéséről // Proc. 23. ACM szimpózium a számítási geometriáról (videosáv) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoi diagramok // Diszkrét és számítási geometria . - 2010. - T. 44 , sz. 2 . – S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. A legkisebb körülzáró Bregman Balls közelítéséről // Proc. 22. ACM Szimpózium a Számítógépes Geometriáról. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. A Burbea-Rao és Bhattacharyya centroidok // IEEE Transactions on Information Theory . - 2011. - T. 57 , sz. 8 . — S. 5455–5466 . - doi : 10.1109/TIT.2011.2159046 . - arXiv : 1004.5049 .
Frank Nielsen, Richard Nock. Skew Jensen eltérések és Bregman eltérések általánosítása összehasonlító konvexitással // IEEE Signal Processing Letters . - 2017. - T. 24 , sz. 8 . – S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - Iránykód . - arXiv : 1702.04877 .