Bregman ayrışması - Bregman divergence

Gelen matematik , özellikle istatistik ve bilgi geometrisi , bir Bregman sapma veya Bregman mesafe bir katı cinsinden tanımlanmaktadır iki nokta arasındaki farkın bir ölçüsüdür konveks fonksiyonu ; önemli bir farklılık sınıfını oluştururlar . Noktalar olasılık dağılımları olarak yorumlandığında – özellikle ya bir parametrik modelin parametresinin değerleri olarak ya da gözlemlenen değerlerin bir veri seti olarak – ortaya çıkan mesafe istatistiksel bir mesafedir . En temel Bregman sapması kare Öklid mesafesidir .

Bregman sapmaları metriklere benzer , ancak ne üçgen eşitsizliğini (hiç) ne de simetriyi (genel olarak) karşılamaz. Bununla birlikte, Pisagor teoreminin bir genellemesini sağlarlar ve bilgi geometrisinde karşılık gelen istatistiksel manifold (ikili) düz bir manifold olarak yorumlanır . Bu, birçok optimizasyon teorisi tekniğinin , geometrik olarak en küçük karelerin genellemeleri olarak Bregman sapmalarına genelleştirilmesine izin verir .

Bregman farklılıkları, 1967'de kavramı tanıtan Lev M. Bregman'ın adını almıştır .

Tanım

Izin sürekli türevlenebilir, katı şekilde dışbükey fonksiyonu kapalı tanımlanan dışbükey grubu . ${\displaystyle F:\Omega \to \mathbb {R} }$ ${\görüntüleme stili\Omega }$

İle ilişkili Bregman mesafe F noktaları için değeri arasındaki fark , F noktasında p ve birinci sıra değerinin Taylor açılımı arasında F noktası çevresinde q noktasında değerlendirilir p : ${\ Displaystyle p,q\in \Omega }$

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

Özellikler

• Olumsuzluk : tüm p, q için. Bu, F'nin dışbükeyliğinin bir sonucudur.${\displaystyle D_{F}(p,q)\geq 0}$
• Convexity : ilk argümanında dışbükeydir, ancak ikinci argümanda mutlaka olması gerekmez (bkz. )${\displaystyle D_{F}(p,q)}$
• Lineerlik : Bregman mesafesini F fonksiyonu üzerinde bir operatör olarak düşünürsek, negatif olmayan katsayılara göre lineerdir. Başka bir deyişle, kesinlikle dışbükey ve türevlenebilir ve ,${\displaystyle F_{1},F_{2}}$${\displaystyle \lambda \geq 0}$

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

• Dualite : F fonksiyonunun dışbükey bir eşleniği vardır . ile ilgili olarak tanımlanan Bregman mesafesinin ilginç bir ilişkisi vardır.${\görüntüleme stili F^{*}}$${\görüntüleme stili F^{*}}$${\displaystyle D_{F}(p,q)}$

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

Burada ve p ve q'ya karşılık gelen ikili noktalardır.${\displaystyle p^{*}=\nabla F(p)}$${\displaystyle q^{*}=\nabla F(q)}$

• Küçültücü olarak ortalama : Bregman sapmaları ile ilgili önemli bir sonuç, rastgele bir vektör verildiğinde, ortalama vektörün, rastgele vektörden beklenen Bregman sapmasını en aza indirmesidir. Bu sonuç, bir kümenin ortalamasının kümedeki öğelere toplam karesel hatayı en aza indirdiği ders kitabı sonucunu genelleştirir. Bu sonuç vektör durumu için (Banerjee et al. 2005) tarafından kanıtlanmıştır ve (Frigyik et al. 2008) tarafından fonksiyonlar/dağılımlar durumuna kadar genişletilmiştir. Bu sonuç önemlidir, çünkü özellikle Bayes tahmininde, rastgele bir kümenin temsilcisi olarak bir ortalamanın kullanılmasını daha da doğrular.

Örnekler

• Kare Öklid mesafesi , dışbükey fonksiyon tarafından üretilen bir Bregman mesafesinin kanonik örneğidir.${\displaystyle D_{F}(x,y)=\|xy\|^{2}}$${\displaystyle F(x)=\|x\|^{2}}$
• Kare Mahalanobis mesafe , dışbükey işlev ile oluşturulur . Bu, yukarıda karesi alınmış Öklid mesafesinin bir genellemesi olarak düşünülebilir.${\displaystyle D_{F}(x,y)={\tfrac {1}{2}}(xy)^{T}Q(xy)}$${\displaystyle F(x)={\tfrac {1}{2}}x^{T}Qx}$
• Genelleştirilmiş Kullback-Leibler ayrışması

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

negatif entropi fonksiyonu tarafından üretilir

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

• Itakura-Saito mesafe ,

${\displaystyle D_{F}(p,q)=\sum _{i}\left({\frac {p(i)}{q(i)}}-\log {\frac {p(i)} {q(i)}}-1\sağ)}$

dışbükey fonksiyon tarafından üretilir

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

Projektif dualitenin genelleştirilmesi

Hesaplamalı geometride önemli bir araç, noktaları ve üst-alt ilişkilerini korurken, noktaları hiper düzlemlere eşleyen ve bunun tersini yapan yansıtmalı ikilik fikridir . Projektif ikilinin sayısız analitik biçimi vardır: ortak bir biçim, noktayı hiper düzleme eşler . Bu eşleme (hiper düzlemi normaliyle özdeşleştirerek), p noktasını ikili noktasına götüren dışbükey eşlenik eşleme olarak yorumlanabilir , burada F d -boyutlu paraboloidi tanımlar . ${\displaystyle p=(p_{1},\ldots p_{d})}$${\displaystyle x_{d+1}=\sum _{1}^{d}2p_{i}x_{i}}$${\displaystyle p^{*}=\nabla F(p)}$${\displaystyle x_{d+1}=\sum x_{i}^{2}}$

Şimdi paraboloidi keyfi bir dışbükey fonksiyonla değiştirirsek, standart projektif dualin insidansını ve yukarıda-aşağıda özelliklerini koruyan farklı bir ikili eşleme elde ederiz. Bu, Voronoi diyagramları ve Delaunay üçgenlemeleri gibi hesaplamalı geometrideki doğal ikili kavramların, keyfi bir Bregman diverjansı tarafından tanımlanan uzaklık uzaylarında anlamlarını koruduğu anlamına gelir. Böylece, "normal" geometriden gelen algoritmalar doğrudan bu uzaylara uzanır (Boissonnat, Nielsen ve Nock, 2010).

Bregman sapmalarının genelleştirilmesi

Bregman sapmaları, çarpık Jensen sapmalarının sınır durumları olarak yorumlanabilir (bkz. Nielsen ve Boltz, 2011). Jensen sapmaları, karşılaştırmalı dışbükeylik kullanılarak genelleştirilebilir ve bu çarpık Jensen sapmaları genellemelerinin sınır durumları, genelleştirilmiş Bregman sapmalarını verir (bkz. Nielsen ve Nock, 2017). Bregman akor ayrımı, teğet bir çizgi yerine bir akor alınarak elde edilir.

Diğer nesnelerde Bregman sapması

Bregman sapmaları matrisler arasında, fonksiyonlar arasında ve ölçüler (dağılımlar) arasında da tanımlanabilir. Matrisler arasındaki Bregman sapmaları, Stein kaybını ve von Neumann entropisini içerir . Fonksiyonlar arasındaki Bregman sapmaları, toplam kare hatası, göreli entropi ve kare yanlılığı içerir; bkz. Frigyik ve ark. tanımlar ve özellikler için aşağıda. Benzer şekilde, Bregman sapmaları da , bir dışbükey işlevin ayrık analoğu olarak bilinen bir alt modüler küme işlevi aracılığıyla kümeler üzerinde tanımlanmıştır . Alt modüler Bregman sapmaları, Hamming mesafesi , kesinlik ve geri çağırma , karşılıklı bilgi ve alt modüler Bregman'ın daha fazla ayrıntı ve özellikleri için bazı diğer küme tabanlı mesafe ölçümleri (bkz.

Ortak matris Bregman sapmalarının bir listesi için Tablo 15.1'e bakın.

Uygulamalar

Makine öğreniminde, gürültülü veri kümeleriyle softmax işlevinden daha iyi performans gösteren iki kademeli lojistik kaybı hesaplamak için Bregman sapmaları kullanılır .

Referanslar

Dış bağlantılar