Bragman Divergence

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 noiembrie 2021; verificările necesită 2 modificări .

Divergența Bragman sau distanța Bragman este o măsură a distanței dintre două puncte , definită în termenii unei funcții strict convexe . Ele formează o clasă importantă de divergențe . Dacă punctele sunt interpretate ca o distribuție de probabilitate , fie ca valori ale unui model parametric , fie ca un set de valori observate, atunci distanța rezultată este o distanță statistică . Cea mai elementară divergență Bragman este distanța euclidiană pătrată .

Divergențele Bragman sunt similare cu metrica , dar nu satisfac nici inegalitatea triunghiului, nici simetria (în cazul general), dar satisfac teorema generalizată a lui Pitagora . În geometria informației varietatea statistică corespunzătoare este interpretată ca o varietate plată (sau duală). Acest lucru permite ca multe tehnici de optimizare să fie generalizate la divergența Bragman, care corespunde geometric unei generalizări a metodei celor mai mici pătrate .

Divergența Bragman este numită după Lev Meerovich Bragman , care a propus conceptul în 1967.

Definiție

Fie o funcție strict convexă diferențiabilă continuu definită pe o mulțime convexă închisă . $F:\Omega \to \mathbb {R}$ $\Omega$

Distanța Bragman asociată cu funcția F pentru puncte este diferența dintre valoarea funcției F în punctul p și valoarea expansiunii Taylor de ordinul întâi a funcției F în punctul q , calculată în punctul p : $p,q\in \Omega$

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

Proprietăți

Non- negativitate : pentru toate p, q. Aceasta este o consecință a convexității lui F. $D_{F}(p,q)\geqslant 0$
Convexitate : Funcția este convexă în primul argument, dar nu neapărat convexă în al doilea (vezi lucrarea lui Bauschke și Borwein [1] ) $D_{F}(p,q)$
Liniaritate : Dacă luăm în considerare distanța Bragman ca operator al funcției F , atunci aceasta este liniară în raport cu coeficienții nenegativi. Cu alte cuvinte, pentru strict convexe și diferențiabile și , $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)

Dualitate : Funcția F are un conjugat convex . Distanța Bragman definită pentru este legată de $F^{*}$ $F^{*}$ $D_{F}(p,q)$

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

Aici , și sunt punctele duale corespunzătoare lui p și q.

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

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

Cel puțin medie : Rezultatul cheie despre divergența Bragman este că, având în vedere un vector aleator, media vectorilor minimizează divergența Bragman așteptată față de vectorul aleator. Acest rezultat generalizează rezultatul manual că media setului minimizează eroarea pătrată totală a elementelor mulțimii. Acest rezultat a fost demonstrat pentru cazul vectorilor de Banerjee et al .[2] și extins la cazul funcțiilor/distribuțiilor de către Fridjik și colab .[3] .

Exemple

Distanța euclidiană pătrată este exemplul canonic al distanței Bragman formată de funcția convexă $D_{F}(x,y)=\|xy\|^{2)$ $F(x)=\|x\|^{2)$
Pătratul distanței Mahalanobis , care este format dintr-o funcție convexă . Aceasta poate fi văzută ca o generalizare a distanței euclidiene pătrate de mai sus. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Divergența generalizată Kullback-Leibler

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

este format din funcția de entropie negativă

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

Distanța Itakura-Saito ,

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

generalizat printr-o funcţie convexă

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

Generalizarea dualității proiective

Un instrument cheie în geometria computațională este ideea dualității proiective , care mapează punctele către hiperplan și invers, menținând totuși incidența și relațiile deasupra/dedesubt. Există multe tipuri de dualitate proiectivă - forma obișnuită mapează un punct la un hiperplan . Această mapare poate fi înțeleasă (dacă identificăm hiperplanul cu normalul) ca o mapare conjugată convexă care duce punctul p la punctul dual , unde F definește un paraboloid d -dimensional . $p=(p_{1},\ldots p_{d})$ $x_{d+1}=\sum _{1}^{d}2p_{i}x_{i)$ $p^{*}=\nabla F(p)$ $x_{d+1}=\sum x_{i}^{2}$

Dacă înlocuim acum paraboloidul cu orice funcție convexă, obținem o altă mapare duală care păstrează incidența și proprietățile de deasupra/dedesubt ale dualității proiective standard. De aici rezultă că conceptele naturale duale ale geometriei computaționale, cum ar fi diagrama Voronoi și triangulațiile Delaunay , își păstrează valoarea în spații cu o distanță definită de o divergență Bragman arbitrară. Algoritmii de geometrie „normală” se extind în mod natural la aceste spații [4] .

Generalizări ale divergenței Bragman

Divergențele Bragman pot fi interpretate ca cazuri limitative de divergențe skew Jensen [5] (vezi lucrarea lui Nielsen și Bolz [6] ). Divergențele Jensen pot fi generalizate folosind convexitatea comparativă, iar generalizarea cazurilor limită ale acestor divergențe Jensen oblice duce la divergențe Bragman generalizate (vezi lucrarea lui Nielsen și Nock [7] ). Divergența de acorduri a lui Bragman [8] se obține prin luarea unei coarde în locul unei tangente.

Divergenta bragman asupra altor obiecte

Divergența Bragman poate fi definită pentru matrici, funcții și măsuri (distribuții). Divergența Bragman pentru matrice include funcția de pierdere Stein [9] și entropia Neumann . Divergențele Bragman pentru funcții includ eroarea pătrată totală, entropia relativă și părtinirea pătratului (vezi Frigik și colab . [3] mai jos pentru definiții și proprietăți). În mod similar, divergența Bragman este definită și pentru mulțimi prin intermediul funcției set submodulare , cunoscută sub numele de analogul discret al funcției convexe . Divergența Bragman submodulară include o serie de măsuri discrete, cum ar fi distanța Hamming , precizia și rechemarea , informații reciproce și alte măsuri de distanță pe seturi (vezi Ayer și Bilmes [10] pentru detalii și proprietăți ale divergenței Bragman submodulare).

O listă cu divergențele comune ale matricei Bragman poate fi găsită în Tabelul 15.1 din articolul lui Nock, Magdalow, Bryce, Nielsen [11] .

Aplicații

În învățarea automată, divergența Bragman este utilizată pentru a calcula o funcție de eroare logistică modificată care funcționează mai bine decât softmax pe date zgomotoase [12] .

Note

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ Numele Jensen-Shannon Divergence a prins rădăcini în literatura în limba rusă , deși Jensen este danez și ar trebui citit în daneză, nu în engleză. Wikipedia are un articol despre Jensen .
↑ Nielsen, Boltz, 2011 .
↑ Nielsen, Nock, 2017 .
↑ Nielsen, Frank & Nock, Richard (2018), The Bregman chord divergence, arΧiv : 1810.09113 [cs.LG].
↑ Pentru termenul de pierdere a lui Stein, consultați https://www.jstor.org/stable/2241373?seq=1 Arhivat 17 noiembrie 2020 la Wayback Machine
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , p. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , p. 14987-14996.

Literatură

H. Bauschke, J. Borwein. Convexitatea comună și separată a distanței Bregman // Algoritmi inerent paralel în fezabilitate și optimizare și aplicațiile lor / D. Butnariu, Y. Censor, S. Reich (editori). — Elsevier, 2001.
R. Nock, B. Magdalou, E. Briys, F. Nielsen. Mining Matrix Data cu Bregman MatrixDivergences pentru selecția portofoliului // Matrix Information Geometry . — 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Pierderi logistice bi-temperate robuste bazate pe divergențele Bregman // Conferința privind sistemele de procesare a informațiilor neuronale . — 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Clustering cu divergențele Bregman // Journal of Machine Learning Research . - 2005. - T. 6 . - S. 1705-1749 .
Bragman LM Metoda de relaxare pentru găsirea unui punct comun al mulţimilor convexe şi aplicarea acestuia la rezolvarea problemelor de programare convexă // Zh. Vychisl. matematică.și matematică. fiz. - 1967. - V. 7 , nr 3 .
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Divergențele Bregman funcționale și estimarea bayesiană a distribuțiilor // Tranzacții IEEE pe teoria informației . - 2008. - T. 54 , nr. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Arhivat din original pe 12 august 2010.
Rishabh Iyer, Jeff Bilmes. Divergențele submodulare-Bregman și divergențele Lovász-Bregman cu Aplicații // . — 2012.
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. O introducere în derivatele funcționale . - Universitatea din Washington, Dept. of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergență și suficiență pentru optimizarea convexă // Entropie. - 2017. - T. 19 , nr. 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. Diagramele Voronoi duale cu privire la divergențele Bregman reprezentaționale // Proc. Al 6-lea Simpozion Internațional de Diagrame Voronoi . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. Despre centroizii divergențelor Bregman simetrizate . — 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. Despre vizualizarea diagramelor Bregman Voronoi // Proc. Al 23-lea Simpozion ACM de geometrie computațională (pistă video) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoi Diagrame // Geometrie discretă și computațională . - 2010. - T. 44 , nr. 2 . — S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. La aproximarea celor mai mici bile Bregman care înglobează // Proc. Al 22-lea Simpozion ACM de Geometrie Computațională. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. Centroizii Burbea-Rao și Bhattacharyya // 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. Generalizarea divergențelor Skew Jensen și a divergențelor Bregman cu convexitate comparativă // Litere de procesare a semnalului IEEE . - 2017. - T. 24 , nr. 8 . — S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - Cod biblic . - arXiv : 1702.04877 .