Bregmanova divergence - Bregman divergence

v matematika konkrétně statistika a informační geometrie, a Bregmanova divergence nebo Bregmanova vzdálenost je měřítkem vzdálenost mezi dvěma body, definované přísně konvexní funkce; tvoří důležitou třídu divergence. Když jsou body interpretovány jako rozdělení pravděpodobnosti - zejména jako buď hodnoty parametru a parametrický model nebo jako soubor dat pozorovaných hodnot - výsledná vzdálenost je a statistická vzdálenost. Nejzákladnější Bregmanovou divergencí je na druhou euklidovská vzdálenost.

Bregmanovy divergence jsou podobné metriky, ale nevyhovují ani nerovnost trojúhelníku (vůbec) ani symetrie (obecně). Splňují však zevšeobecnění Pythagorova věta a v informační geometrii odpovídající statistická rozmanitost je interpretován jako (duálně) ploché potrubí. To umožňuje mnoho technik teorie optimalizace zobecnit na Bregmanovy divergence, geometricky jako zobecnění nejmenší čtverce.

Bregmanovy divergence jsou pojmenovány po Lev M. Bregman, který představil koncept v roce 1967.

Definice

Nechat ${displaystyle F: Omega o mathbb {R}}$ být přísně rozlišitelný konvexní funkce definováno na uzavřeném konvexní sada ${displaystyle Omega}$.

Bregmanova vzdálenost spojená s F pro body ${displaystyle p, qin Omega}$ je rozdíl mezi hodnotou F v bodě str a hodnota prvního řádu Taylorova expanze z F kolem bodu q hodnoceno v bodě str:

${displaystyle D_ {F} (p, q) = F (p) -F (q) -langle abla F (q), p-qangle.}$

Vlastnosti

• Nezápornost: ${displaystyle D_ {F} (p, q) geq 0}$ pro všechna p, q. To je důsledek konvexity F.
• Konvexnost:${displaystyle D_ {F} (p, q)}$ je konvexní ve svém prvním argumentu, ale ne nutně ve druhém argumentu (viz ^[1])
• Linearita: Pokud uvažujeme o Bregmanově vzdálenosti jako operátorovi funkce F, pak je lineární s ohledem na nezáporné koeficienty. Jinými slovy, pro ${displaystyle F_ {1}, F_ {2}}$ přísně konvexní a diferencovatelné a ${displaystyle lambda geq 0}$,

${displaystyle D_ {F_ {1} + lambda F_ {2}} (p, q) = D_ {F_ {1}} (p, q) + lambda D_ {F_ {2}} (p, q)}$

• Dualita: Funkce F má a konvexní konjugát ${displaystyle F ^ {*}}$. Bregmanova vzdálenost definovaná s ohledem na ${displaystyle F ^ {*}}$ má zajímavý vztah ${displaystyle D_ {F} (p, q)}$

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

Tady, ${displaystyle p ^ {*} = abla F (p)}$ a ${displaystyle q ^ {*} = abla F (q)}$ jsou duální body odpovídající p a q.

• Znamená to jako minimalizátor: Klíčovým výsledkem Bregmanových divergencí je, že vzhledem k náhodnému vektoru střední vektor minimalizuje očekávanou Bregmanovu divergenci od náhodného vektoru. Tento výsledek zobecňuje výsledek učebnice, že průměr množiny minimalizuje celkovou čtvercovou chybu prvků v sadě. Tento výsledek byl pro vektorový případ prokázán (Banerjee et al. 2005) a rozšířen na případ funkcí / distribucí (Frigyik et al. 2008). Tento výsledek je důležitý, protože dále ospravedlňuje použití střední hodnoty jako zástupce náhodné množiny, zejména v bayesovském odhadu.

Příklady

• Čtvercová euklidovská vzdálenost ${displaystyle D_ {F} (x, y) = | x-y | ^ {2}}$ je kanonický příklad Bregmanovy vzdálenosti generovaný konvexní funkcí ${displaystyle F (x) = | x | ^ {2}}$
• Na druhou Mahalanobisova vzdálenost, ${displaystyle D_ {F} (x, y) = {frac {1} {2}} (x-y) ^ {T} Q (x-y)}$ který je generován konvexní funkcí ${displaystyle F (x) = {frac {1} {2}} x ^ {T} Qx}$. Lze to považovat za zevšeobecnění výše uvedené čtvercové euklidovské vzdálenosti.
• Zobecněný Kullback – Leiblerova divergence

${displaystyle D_ {F} (p, q) = součet _ {i} p (i) log {frac {p (i)} {q (i)}} - součet p (i) + součet q (i)}$

je generován záporem entropie funkce

${displaystyle F (p) = součet _ {i} p (i) log p (i)}$

• The Vzdálenost Itakura – Saito,

${displaystyle D_ {F} (p, q) = součet _ {i} vlevo ({frac {p (i)} {q (i)}} - log {frac {p (i)} {q (i)}) } -1 světlo)}$

je generována konvexní funkcí

${displaystyle F (p) = - součet _ {i} log p (i)}$

Zobecnění projektivní duality

Klíčový nástroj výpočetní geometrie je myšlenka projektivní dualita, který mapuje body na hyperplany a naopak, při zachování výskytu a vztahů pod a pod. Existuje mnoho analytických forem projektivního dvojího: jedna společná forma mapuje bod ${displaystyle p = (p_ {1}, ldots p_ {d})}$ do nadroviny ${displaystyle x_ {d + 1} = součet _ {1} ^ {d} 2p_ {i} x_ {i}}$. Toto mapování lze interpretovat (identifikace hyperplánu s jeho normálem) jako konvexní mapování konjugátu, které vezme bod p do jeho dvojitého bodu ${displaystyle p ^ {*} = abla F (p)}$, kde F definuje d-rozměrný paraboloid ${displaystyle x_ {d + 1} = součet x_ {i} ^ {2}}$.

Pokud nyní nahradíme paraboloid libovolnou konvexní funkcí, získáme odlišné duální mapování, které si zachová incidenci a vlastnosti pod-pod standardní projektivní duální. To znamená, že přirozené duální pojmy ve výpočetní geometrii jsou podobné Voronoiovy diagramy a Delaunayovy triangulace zachovat jejich význam v prostorech vzdáleností definovaných libovolnou Bregmanovou divergencí. Algoritmy z „normální“ geometrie tedy zasahují přímo do těchto prostorů (Boissonnat, Nielsen a Nock, 2010)

Zobecnění Bregmanových divergencí

Bregmanovy divergence lze interpretovat jako mezní případy zkosení Jensenovy divergence (viz Nielsen a Boltz, 2011). Jensenovy divergence lze zobecnit pomocí komparativní konvexity a omezené případy těchto zkosených generalizací Jensenových divergencí přinesou zobecněnou Bregmanovu divergenci (viz Nielsen a Nock, 2017).^[2] se získá tak, že namísto tečné čáry vezmeme akord.

Bregmanova divergence u jiných objektů

Bregmanovy divergence lze definovat také mezi maticemi, mezi funkcemi a mezi takty (distribucemi). Bregmanovy divergence mezi maticemi zahrnují Steinova ztráta a von Neumannova entropie. Bregmanovy divergence mezi funkcemi zahrnují celkovou druhou mocninu chyby, relativní entropii a druhou mocninu zkreslení; viz odkazy Frigyik et al. níže pro definice a vlastnosti. Podobně byly také definovány Bregmanovy divergence v množinách, a funkce submodulární sady který je známý jako diskrétní analog a konvexní funkce. Submodulární Bregmanovy divergence zahrnují řadu diskrétních měr vzdálenosti, jako je Hammingova vzdálenost, přesnost a odvolání, vzájemné informace a některá další měření vzdálenosti založená na sadě (viz Iyer & Bilmes, 2012), kde najdete další podrobnosti a vlastnosti submodulárního Bregmana.)

Seznam běžných maticových Bregmanových divergencí najdete v tabulce 15.1 v.^[3]

Aplikace

Ve strojovém učení se Bregmanovy divergence používají k výpočtu dvou temperované logistické ztráty, která funguje lépe než funkce softmax s hlučnými datovými sadami.^[4]

Reference

externí odkazy