Bragmanin ero

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Bragman- divergentti tai Bragman-etäisyys onkahden pisteen välisen etäisyyden mitta , joka määritellään tiukasti kuperalla funktiolla . Ne muodostavat tärkeän eroavaisuuksien luokan . Jos pisteet tulkitaan todennäköisyysjakaumaksi , joko parametrisen mallin arvoiksi tai havaittujen arvojen joukoksi, niin tuloksena oleva etäisyys on tilastollinen etäisyys . Kaikkein alkeellisin Bragman-divergentti on neliöity Euklidinen etäisyys .

Bragman-divergentit ovat samanlaisia kuin metriikka , mutta ne eivät täytä kolmion epäyhtälöä tai symmetriaa (yleisessä tapauksessa), mutta ne täyttävät yleistetyn Pythagoraan lauseen . Tietogeometriassa vastaava tilastollinen monisto tulkitaan litteäksi monistoksi [ (tai duaaliksi). Tämä mahdollistaa useiden optimointitekniikoiden yleistämisen Bragman-divergentiksi, joka vastaa geometrisesti pienimmän neliösumman menetelmän yleistystä .

Bragman-ero on nimetty Lev Meerovich Bragmanin mukaan, joka ehdotti konseptia vuonna 1967.

Määritelmä

Olkoon jatkuvasti differentioituva tiukasti kupera funktio , joka on määritelty suljetussa kuperassa joukossa . $F:\Omega \to \mathbb {R}$ $\Omega$

Pistefunktioon F liittyvä Bragman-etäisyys on ero funktion F arvon pisteessä p ja funktion F ensimmäisen kertaluvun Taylor-laajennuksen arvon välillä pisteessä q , laskettuna pisteessä p : $p,q\in \Omega$

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

Ominaisuudet

Ei- negatiivisuus : kaikille p, q. Tämä on seurausta F : n kuperuudesta. $D_{F}(p,q)\geqslant 0$
Kupera : Funktio on kupera ensimmäisessä argumentissa, mutta ei välttämättä kupera toisessa (katso Bauschken ja Borweinin artikkeli [1] ) ${\näyttötyyli D_{F}(p,q)}$
Lineaarisuus : Jos tarkastellaan Bragmanin etäisyyttä funktion F operaattorina , niin se on lineaarinen suhteessa ei-negatiivisiin kertoimiin. Toisin sanoen tiukasti kuperalle ja erotettavissa olevalle ja , ${\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)

Dualiteetti : Funktiolla F on kupera konjugaatti . Kohdalle määritetty Bragman-etäisyys liittyy $F^{*}$ $F^{*}$ ${\näyttötyyli D_{F}(p,q)}$

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

Tässä ja ovat p:tä ja q:ta vastaavat kaksoispisteet.

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

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

Vähintään keskiarvo : Bragman-divergenssin avaintulos on, että annettuna satunnaisvektorin vektorien keskiarvo minimoi odotetun Bragman- divergentin satunnaisvektorista. Tämä tulos yleistää oppikirjan tuloksen, jonka mukaan asetettu keskiarvo minimoi joukon alkioiden kokonaisneliövirheen. Banerjee ym . [2] osoittivat tämän tuloksen vektorien tapauksessa ja Fridjik ym . [3] laajensivat funktioiden/jakaumien tapaukseen .

Esimerkkejä

Euklidisen etäisyyden neliö on kanoninen esimerkki konveksin funktion muodostamasta Bragmanin etäisyydestä ${\displaystyle D_{F}(x,y)=\|xy\|^{2))$ ${\displaystyle F(x)=\|x\|^{2))$
Mahalanobiksen etäisyyden neliö , joka muodostuu kuperasta funktiosta . Tämä voidaan nähdä yllä olevan neliöidyn euklidisen etäisyyden yleistyksenä. $D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)$ $F(x)={\tfrac {1}{2}}x^{T}Qx$
Yleistetty Kullback-Leibler-ero

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

muodostuu negatiivisesta entropiafunktiosta

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

Etäisyys Itakura-Saito ,

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

yleistetty konveksilla funktiolla

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

Projektiivisen kaksinaisuuden yleistäminen

Laskennallisen geometrian keskeinen työkalu on idea projektiivisestä kaksinaisuudesta , joka kartoittaa pisteet hypertasoon ja päinvastoin säilyttäen silti esiintymis- ja ylä-/alasuhteet. Projektiivista kaksinaisuutta on monenlaista - tavallinen muoto kartoittaa pisteen hypertasoon . Tämä kartoitus voidaan ymmärtää (jos tunnistamme hypertason normaalin kanssa) kuperaksi konjugaattikuvaukseksi, joka vie pisteen p kaksoispisteeseen , jossa F määrittelee d - ulotteisen paraboloidin . $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))$

Jos nyt korvaamme paraboloidin millä tahansa konveksilla funktiolla, saadaan toinen kaksoiskartoitus, joka säilyttää standardin projektiivisen kaksinaisuuden esiintymisen ja ylä-/ala-ominaisuudet. Tästä seuraa, että laskennallisen geometrian luonnolliset kaksoiskäsitteet, kuten Voronoi-kaavio ja Delaunayn kolmiot, säilyttävät arvonsa avaruudessa, jonka etäisyys määrittää mielivaltaisen Bragman-divergenssin. "Normaalin" geometrian algoritmit ulottuvat luonnollisesti näihin tiloihin [4] .

Yleistykset Bragmanin erosta

Bragman-poikkeamat voidaan tulkita rajoittaviksi tapauksiksi Jensenin vino-eroja [5] (katso Nielsenin ja Bolzin artikkeli [6] ). Jensenin erot voidaan yleistää käyttämällä vertailevaa konveksiteettia, ja näiden vinojen Jensen-poikkeamien rajatapausten yleistäminen johtaa yleistettyihin Bragman-divergensseihin (ks. Nielsenin ja Nockin artikkeli [7] ). Bragmanin [8] sointuhajotus saadaan ottamalla tangentin sijaan sointu.

Bragmanin ero muihin objekteihin

Bragman-divergentti voidaan määritellä matriiseille, funktioille ja mitoille (jakaumille). Matriisien Bragman-divergentti sisältää Steinin häviöfunktion [9] ja Neumannin entropian . Bragman-divergensseja funktioille ovat kokonaisneliövirhe, suhteellinen entropia ja neliöbias (katso Frigik et al . [3] alla määritelmät ja ominaisuudet). Samoin Bragman-divergentti määritellään joukoille myös alimodulaarisen joukkofunktion [ avulla, joka tunnetaan konveksin funktion diskreettianalogina . Submodulaarinen Bragman-divergentti sisältää joukon erillisiä mittareita, kuten Hamming-etäisyys , tarkkuus ja palautus , keskinäinen informaatio ja joitain muita etäisyysmittoja joukoissa (katso Ayer ja Bilmes [10] submodulaarisen Bragman-divergenssin yksityiskohtia ja ominaisuuksia varten).

Luettelo yleisistä Bragman-matriisin eroista löytyy Nockin, Magdalowin, Brycen, Nielsenin artikkelin taulukosta 15.1 [11] .

Sovellukset

Koneoppimisessa Bragman-divergenttiä käytetään muunnetun logistisen virhefunktion laskemiseen, joka toimii paremmin kuin softmax meluisassa datassa [12] .

Muistiinpanot

↑ Bauschke, Borwein, 2001 .
↑ Banerjee, Merugu, Dhillon, Ghosh, 2005 .
↑ 1 2 Frigyik, Srivastava, Gupta, 2008 .
↑ Boissonnat, Nielsen, Nock, 2010 .
↑ Nimi Jensen-Shannon Divergence on juurtunut venäjänkieliseen kirjallisuuteen , vaikka Jensen on tanskalainen ja se pitäisi lukea tanskaksi, ei englanniksi. Wikipediassa on artikkeli Jensenistä .
↑ Nielsen, Boltz, 2011 .
↑ Nielsen, Nock, 2017 .
↑ Nielsen, Frank & Nock, Richard (2018), The Bregman chord divergence, arΧiv : 1810.09113 [cs.LG].
↑ Termi Steinin menetys, katso https://www.jstor.org/stable/2241373?seq=1 Arkistoitu 17. marraskuuta 2020 Wayback Machinessa
↑ Iyer, Bilmes, 2012 .
↑ Nock, Magdalou, Briys, Nielsen, 2012 , s. 373-402.
↑ Amid, Warmuth, Anil, Koren, 2019 , s. 14987-14996.

Kirjallisuus

H. Bauschke, J. Borwein. Bregman-etäisyyden yhteinen ja erillinen konveksiiteetti // Inherently Parallel Algorithms in Feasibility and Optimization ja niiden sovellukset / D. Butnariu, Y. Censor, S. Reich (toimittajat). – Elsevier, 2001.
R. Nock, B. Magdalou, E. Briys, F. Nielsen. Matriisidatan louhinta Bregman-matriisidivergensseillä portfolion valintaa varten // Matriisiinformaatiogeometria . – 2012.
Ehsan Amid, Manfred K. Warmuth, Rohan Anil, Tomer Koren. Bregmanin eroihin perustuva voimakas bi-temperoitu logistinen menetys // Neuraalitietojen käsittelyjärjestelmien konferenssi . — 2019.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, Joydeep Ghosh. Klusterointi Bregmanin erojen kanssa // Journal of Machine Learning Research . - 2005. - T. 6 . - S. 1705-1749 .
Bragman LM Relaksaatiomenetelmä konveksien joukkojen yhteisen pisteen löytämiseksi ja sen soveltaminen konveksin ohjelmoinnin ongelmien ratkaisemiseen // Zh. Vychisl. matematiikka ja matematiikka. fiz. - 1967. - V. 7 , nro 3 .
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Funktionaaliset Bregman-erot ja jakautumien Bayesin estimointi // IEEE Transactions on Information Theory . - 2008. - T. 54 , no. 11 . — S. 5130–5139 . - doi : 10.1109/TIT.2008.929943 . — arXiv : cs/0611123 . Arkistoitu alkuperäisestä 12. elokuuta 2010.
Rishabh Iyer, Jeff Bilmes. Submodulaariset-Bregman-divergentit ja Lovász-Bregman-hajoaukset sovellusten kanssa // . – 2012.
Bela A. Frigyik, Santosh Srivastava, Maya R. Gupta. Johdatus funktionaalisiin johdannaisiin . - Washingtonin yliopisto, osasto of Electrical Engineering, 2008. - (UWEE Tech Report 2008-0001).
Peter Harremoes. Divergenssi ja riittävyys kuperaan optimointiin // Entropia. - 2017. - T. 19 , nro 5 . - S. 206 . - doi : 10.3390/e19050206 . - . - arXiv : 1701.01010 .
Frank Nielsen, Richard Nock. Voronoi-kaksoiskaaviot edustavien Bregman-divergenssien suhteen // Proc. 6. kansainvälinen symposium Voronoin kaavioista . - IEEE, 2009. - doi : 10.1109/ISVD.2009.15 .
Frank Nielsen, Richard Nock. Symmetristettyjen Bregman-erojen keskipisteistä . – 2007.
Frank Nielsen, Jean-Daniel Boissonnat, Richard Nock. Bregman Voronoi -kaavioiden visualisoinnista // Proc. 23. ACM Symposium on Computational Geometry (videoraita) . - 2007. - doi : 10.1145/1247069.1247089 .
Jean-Daniel Boissonnat, Frank Nielsen, Richard Nock. Bregman Voronoin kaaviot // Diskreetti ja laskennallinen geometria . - 2010. - T. 44 , no. 2 . — S. 281–307 . - doi : 10.1007/s00454-010-9256-1 .
Frank Nielsen, Richard Nock. Pienimpien sulkevien Bregman-pallojen likiarvosta // Proc. 22. ACM-symposium laskennallisesta geometriasta. - 2006. - S. 485-486. - doi : 10.1145/1137856.1137931 .
Frank Nielsen, Sylvain Boltz. Burbea-Raon ja Bhattacharyyan sentroidit // IEEE Transactions on Information Theory . - 2011. - T. 57 , no. 8 . — S. 5455–5466 . - doi : 10.1109/TIT.2011.2159046 . - arXiv : 1004.5049 .
Frank Nielsen, Richard Nock. Vino Jensenin ja Bregmanin erojen yleistäminen vertailevalla kuperuudella // IEEE Signal Processing Letters . - 2017. - T. 24 , nro 8 . — S. 1123–1127 . - doi : 10.1109/LSP.2017.2712195 . - . - arXiv : 1702.04877 .