Bilgi darboğazı yöntemi - Information bottleneck method

Bilgi darboğaz yöntemi bir tekniktir bilgi teorisi tarafından ortaya Naftali Tishby Fernando C Pereira ve William Bialek . X ile gözlemlenen ilgili bir Y değişkeni arasında ortak bir olasılık dağılımı p(X,Y) verildiğinde, bir rastgele değişken X'i özetlerken (örneğin kümeleme ) doğruluk ve karmaşıklık ( sıkıştırma ) arasındaki en iyi dengeyi bulmak için tasarlanmıştır - ve kendi kendini tanımlayan "Sinyal işleme ve öğrenmede çeşitli sorunları tartışmak için şaşırtıcı derecede zengin bir çerçeve" sağlamak olarak .

Uygulamalar dağılımsal kümelemeyi ve boyut indirgemeyi içerir ve daha yakın zamanda derin öğrenme için teorik bir temel olarak önerilmiştir . Klasik asgari yeterli istatistik kavramını, parametrik istatistiklerden üssel formda olmak zorunda olmayan keyfi dağılımlara kadar genelleştirdi . Bunu , ilgili değişken Y ile karşılıklı bilginin bir kısmını yakalamak için yeterlilik koşulunu gevşeterek yapar .

Bilgi darboğazı, aynı zamanda , X'ten gelen doğrudan tahmine kıyasla, sıkıştırılmış bir T temsilinden Y'nin ne kadar iyi tahmin edildiğini ölçen bir bozulma fonksiyonu ile bir oran bozulma problemi olarak da görülebilir . Bu yorum, bilgi darboğazı değiş tokuşunu çözmek ve p(X,Y) dağılımından bilgi eğrisini hesaplamak için genel bir yinelemeli algoritma sağlar .

Sıkıştırılmış gösterimin rastgele değişken tarafından verilmesine izin verin . Algoritma, koşullu dağılıma göre aşağıdaki işlevleri en aza indirir : ${\görüntüleme stili T}$${\görüntüleme stili p(t|x)}$

${\displaystyle \min _{p(t|x)}\,\,I(X;T)-\beta I(T;Y),}$

nerede ve sırasıyla ve ve ve ve ve öğelerinin karşılıklı bilgileridir ve bir Lagrange çarpanıdır . ${\görüntüleme stili I(X;T)}$${\görüntüleme stili I(T;Y)}$${\görüntüleme stili X}$${\görüntüleme stili T}$${\görüntüleme stili T}$${\görüntüleme stili Y}$${\görüntüleme stili \beta }$

Minimum yeterli istatistik

Kendinden tutarlı denklemler

öğrenme teorisi

Faz geçişleri

Derin öğrenmenin bilgi teorisi

Bilgi Darboğazı Teorisi, son zamanlarda Derin Sinir Ağlarını (DNN) incelemek için kullanılmaktadır. ve sırasıyla bir DNN'nin giriş ve çıkış katmanları olarak düşünün ve ağın herhangi bir gizli katmanı olsun . Shwartz-Ziv ve Tishby, karşılıklı bilgi önlemleri ile . Bu durumda ve sırasıyla gizli katmanın girdi ve çıktı hakkında içerdiği bilgi miktarını ölçün. Bir DNN'nin eğitim sürecinin iki ayrı aşamadan oluştuğunu varsaydılar; 1) arttığı bir ilk yerleştirme aşaması ve 2) azaldığı bir sonraki sıkıştırma aşaması . Saxe et al. DNN'lerdeki bu sıkıştırma olgusunun kapsamlı olmadığını ve belirli aktivasyon fonksiyonuna bağlı olduğunu belirterek Shwartz-Ziv ve Tishby'nin iddiasına karşı çıktı. Özellikle ReLu aktivasyon fonksiyonları ile sıkıştırmanın gerçekleşmediğini iddia ettiler. Shwartz-Ziv ve Tishby, Saxe ve arkadaşlarının karşılıklı bilgilerin zayıf tahminleri nedeniyle sıkıştırma gözlemlemediğini savunarak bu iddialara itiraz ettiler. Son zamanlarda, Noshad ve ark. bu tartışmayı araştırmak için ortak bilginin oran-optimal bir tahmincisi kullandı ve optimal karma tabanlı tahmin edicinin, ReLu ve maxpooling aktivasyonları ile daha geniş bir ağ yelpazesinde sıkıştırma fenomenini ortaya çıkardığını gözlemledi. Öte yandan, yakın zamanda Goldfeld ve ark. gözlemlenen sıkıştırmanın, bilgi-teorik fenomenlerin değil, geometrik bir sonucu olduğunu savundular, bu görüş de paylaşılmıştır. ${\görüntüleme stili X}$${\görüntüleme stili Y}$${\görüntüleme stili T}$${\görüntüleme stili I(X,T)}$${\görüntüleme stili I(T,Y)}$${\görüntüleme stili I(X,T)}$${\görüntüleme stili I(T,Y)}$${\görüntüleme stili I(T,Y)}$${\görüntüleme stili I(X,T)}$

Varyasyon darboğazı

Gauss darboğazı

Gauss darboğazı, yani bilgi darboğazı yaklaşımının Gauss değişkenlerine uygulanması, kanonik korelasyon analizi ile ilgili çözümlere yol açar . Birlikte çok değişkenli, kovaryanslı sıfır ortalama normal vektörler olduğunu ve bunun sıkıştırılmış bir versiyonu olduğunu ve ile verilen bir karşılıklı bilgi değerini koruması gerektiğini varsayalım . Optimumun , matrisin ortogonal satırlara sahip olduğu elemanların doğrusal kombinasyonlarından oluşan normal bir vektör olduğu gösterilebilir. ${\görüntüleme stili X,Y\,}$${\displaystyle \Sigma _{XX},\,\,\Sigma _{YY}}$${\görüntüleme stili T\,}$${\görüntüleme stili X\,}$${\görüntüleme stili Y\,}$${\görüntüleme stili T\,}$${\ Displaystyle X,\,\,T=AX\,}$${\görüntüleme stili A\,}$

İzdüşüm matrisi aslında matrisin (genellikle asimetrik) tekil değer ayrışmasının ağırlıklı sol özvektörlerinden seçilen satırları içerir.${\görüntüleme stili A\,}$${\görüntüleme stili M\,}$

${\displaystyle \Omega =\Sigma _{X|Y}\Sigma _{XX}^{-1}=I-\Sigma _{XY}\Sigma _{YY}^{-1}\Sigma _{XY }^{T}\Sigma _{XX}^{-1}.\,}$

Tekil değer ayrıştırmasını tanımlayın

${\displaystyle \Omega =U\Lambda V^{T}{\text{ ile }}\Lambda =\operatorname {Diag} {\big (}\lambda _{1}\leq \lambda _{2}\cdots) \lambda _{N}{\büyük )}\,}$

ve kritik değerler

${\displaystyle \beta _{i}^{C}{\underset {\lambda _{i}<1}{=}}(1-\lambda _{i})^{-1}.\,}$

daha sonra projeksiyondaki aktif özvektörlerin sayısı veya yaklaşıklık sırası şu şekilde verilir: ${\görüntüleme stili M\,}$

${\displaystyle \beta _{M-1}^{C}<\beta \leq \beta _{M}^{C}}$

Ve sonunda alıyoruz

${\displaystyle A=[w_{1}U_{1},\dots ,w_{M}U_{M}]^{T}}$

Ağırlıkların verildiği

${\displaystyle w_{i}={\sqrt {(\beta (1-\lambda _{i})/\lambda _{i}r_{i}}}}$

nerede ${\displaystyle r_{i}=U_{i}^{T}\Sigma _{XX}U_{i}.\,}$

Gauss bilgi darboğazını zaman serilerine (süreçlere) uygulamak, optimal tahmine dayalı kodlamayla ilgili çözümler sağlar. Bu prosedür, resmi olarak doğrusal Yavaş Özellik Analizine eşdeğerdir .

Doğrusal dinamik sistemlerdeki optimal zamansal yapılar, darboğaz yönteminin Gauss olmayan örneklenmiş verilere bir uygulaması olan sözde geçmiş-gelecek bilgi darboğazında ortaya çıkarılabilir. Creutzig, Tishby ve diğerleri tarafından ele alındığı şekliyle kavram, alıştırmada iki bağımsız aşama oluşturduğundan, sorunsuz değildir: ilk olarak, veri örneklerinin alındığı bilinmeyen ana olasılık yoğunluklarının tahmini ve ikinci olarak, bu yoğunlukların darboğazın bilgi teorik çerçevesi.

yoğunluk tahmini

Darboğaz yöntemi istatistiksel terimlerden ziyade olasılıksal olarak çerçevelendiğinden, örnek noktalarındaki temel olasılık yoğunluğu tahmin edilmelidir. Bu, Silverman tarafından açıklanan çoklu çözümlerle iyi bilinen bir sorundur . Mevcut yöntemde, bir Markov geçiş matrisi yöntemi kullanılarak ortak örnek olasılıkları bulunur ve bu, darboğaz yönteminin kendisiyle bir miktar matematiksel sinerjiye sahiptir. ${\displaystyle X={x_{i}}\,}$

İsteğe bağlı olarak artan mesafe metriği tüm numune çiftleri arasındaki mesafe matris olup . Daha sonra bazıları için örnek çiftleri arasındaki geçiş olasılıkları hesaplanmalıdır. Durumları gibi örnekleri ve normalleştirilmiş bir sürümünü tedavisi Markov durum geçiş olasılığı matrisi olarak, sonra 'durumları' olasılıklarının vektör ilk durumuna durumunu adımlar , bir . Başlangıç ​​vektöründen bağımsız olan matrisin baskın özvektörü tarafından olağan şekilde verilen denge olasılık vektörü . Bu Markov geçiş yöntemi, olasılıkların yoğunluklarıyla orantılı olduğu iddia edilen örnek noktalarda bir olasılık kurar. ${\görüntüleme stili f\,}$${\displaystyle d_{i,j}=f{\Big (}{\Big |}x_{i}-x_{j}{\Big |}{\Big )}}$${\displaystyle P_{i,j}=\exp(-\lambda d_{i,j})\,}$${\displaystyle \lambda >0\,}$${\görüntüleme stili P\,}$${\görüntüleme stili t\,}$${\görüntüleme stili p(0)\,}$${\görüntüleme stili p(t)=P^{t}p(0)\,}$${\ Displaystyle p(\infty )\,}$${\görüntüleme stili P\,}$${\görüntüleme stili p(0)\,}$

Uzaklık matrisinin özdeğerlerinin kullanımına ilişkin diğer yorumlar Silverman'ın İstatistik ve Veri Analizi için Yoğunluk Tahmininde tartışılmıştır . ${\görüntüleme stili d\,}$

Kümeler

Aşağıdaki yumuşak kümeleme örneğinde, referans vektörü örnek kategorileri içerir ve birleşik olasılığın bilindiği varsayılır. Yumuşak bir küme , veri örnekleri üzerindeki olasılık dağılımı ile tanımlanır . Tishby et al. Hız bozulma teorisinde geliştirilen Blahut-Arimoto algoritmasının nihai bir genellemesi olan kümeleri belirlemek için aşağıdaki yinelemeli denklem setini sundu . Bu tür bir algoritmanın sinir ağlarında uygulanması, deterministik tavlamada Gibbs Dağılımlarının uygulanmasında ortaya çıkan entropi argümanlarından kaynaklanıyor gibi görünmektedir . ${\görüntüleme stili Y\,}$${\görüntüleme stili p(X,Y)\,}$${\displaystyle c_{k}\,}$${\displaystyle x_{i}:\,\,\,p(c_{k}|x_{i})}$

${\displaystyle {\begin{cases}p(c|x)=Kp(c)\exp {\Big (}-\beta \,D^{KL}{\Big [}p(y|x)\, ||\,p(y|c){\Big ]}{\Big )}\\p(y|c)=\textstyle \sum _{x}p(y|x)p(c|x)p (x){\big /}p(c)\\p(c)=\textstyle \sum _{x}p(c|x)p(x)\\\end{durumlar}}}$

Yinelemenin her satırının işlevi şu şekilde genişler:

Satır 1: Bu, matris değerli bir koşullu olasılıklar kümesidir.

${\displaystyle A_{i,j}=p(c_{i}|x_{j})=Kp(c_{i})\exp {\Big (}-\beta \,D^{KL}{\Big) [}p(y|x_{j})\,||\,p(y|c_{i}){\Big ]}{\Big )}}$

Kullback-Leibler diverjans arasında örnek veriler tarafından üretilen vektörler ve azaltılmış bilgi vekil tarafından üretilenler referans (veya kategorik) verilerine göre sıkıştırılmış vektörün aslına tayin etmek üzere uygulanırken , temel darboğaz denkleme uygun olarak. dağılımlar arasındaki Kullback-Leibler ayrımıdır.${\ Displaystyle D^{KL}\,}$${\görüntüleme stili Y\,}$${\görüntüleme stili x\,}$${\görüntüleme stili c\,}$${\görüntüleme stili Y\,}$${\displaystyle D^{KL}(a||b)\,}$${\görüntüleme stili a,b\,}$

${\displaystyle D^{KL}(a||b)=\sum _{i}p(a_{i})\log {\Big (}{\frac {p(a_{i}))}{p( b_{i})}}{\Büyük )}}$

ve bir skaler normalizasyondur. Mesafenin negatif üssü ile ağırlıklandırma, Kullback-Leibler ayrışması büyük olduğunda önceki küme olasılıklarının 1. satırda daha düşük ağırlıkta olduğu anlamına gelir, bu nedenle başarılı kümeler olasılıkta büyürken başarısız olanlar azalır. ${\görüntüleme stili K\,}$

Satır 2: İkinci matris değerli koşullu olasılıklar kümesi. Tanım olarak

${\displaystyle {\begin{hizalanmış}p(y_{i}|c_{k})&=\sum _{j}p(y_{i}|x_{j})p(x_{j}|c_{ k})\\&=\sum _{j}p(y_{i}|x_{j})p(x_{j},c_{k}){\big /}p(c_{k})\ \&=\sum _{j}p(y_{i}|x_{j})p(c_{k}|x_{j})p(x_{j}){\big /}p(c_{k })\\\end{hizalanmış}}}$

Bayes kimliklerinin kullanıldığı yerler. ${\görüntüleme stili p(a,b)=p(a|b)p(b)=p(b|a)p(a)\,}$

Satır 3: bu satır, kümelerin marjinal dağılımını bulur${\görüntüleme stili c\,}$

${\displaystyle {\begin{aligned}p(c_{i})&=\sum _{j}p(c_{i},x_{j})&=\sum _{j}p(c_{i} |x_{j})p(x_{j})\end{hizalı}}}$

Bu standart bir sonuçtur.

Algoritmanın diğer girdileri , baskın özvektörü tarafından önceden belirlenmiş olan marjinal örnek dağılımı ve matris değerli Kullback-Leibler sapma fonksiyonudur. ${\görüntüleme stili p(x)\,}$${\görüntüleme stili P\,}$

${\displaystyle D_{i,j}^{KL}=D^{KL}{\Big [}p(y|x_{j})\,||\,p(y|c_{i}){\ Büyük ]}{\Büyük )}}$

örnek aralıklarından ve geçiş olasılıklarından türetilmiştir.

Matris rastgele veya makul bir tahminle başlatılabilirken, matrisin ön değerlerine ihtiyacı yoktur. Algoritma yakınsamasına rağmen, çözülmesi gereken birden fazla minimum olabilir. ${\displaystyle p(y_{i}|c_{j})\,}$${\displaystyle p(c_{i}|x_{j})\,}$

Karar konturlarını tanımlama

Eğitim kümesinin dışında yeni bir örneği kategorize etmek için önceki mesafe metriği , bir normalleştirme ile içindeki ve içindeki tüm örnekler arasındaki geçiş olasılıklarını bulur . İkinci olarak küme ve koşullu kategori olasılıklarını elde etmek için 3 satırlı algoritmanın son iki satırını uygulayın. ${\görüntüleme stili x'\,}$${\görüntüleme stili X\,}$${\görüntüleme stili x'\,}$${\görüntüleme stili X:\,\,}$${\displaystyle {\tilde {p}}(x_{i})=p(x_{i}|x')=\mathrm {K} \exp {\Big (}-\lambda f{\big (}{\displaystyle {\tilde {p}}) \Big |}x_{i}-x'{\Big |}{\big )}{\Big )}}$${\displaystyle \mathrm {K} \,}$

${\displaystyle {\begin{hizalanmış}&{\tilde {p}}(c_{i})=p(c_{i}|x')=\sum _{j}p(c_{i}|x_{ j})p(x_{j}|x')=\sum _{j}p(c_{i}|x_{j}){\tilde {p}}(x_{j})\\&p(y_ {i}|c_{j})=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k})p(x_{k}|x') /p(c_{j}|x')=\sum _{k}p(y_{i}|x_{k})p(c_{j}|x_{k}){\tilde {p}}( x_{k})/{\tilde {p}}(c_{j})\\\end{hizalı}}}$

Nihayet

${\displaystyle p(y_{i}|x')=\sum _{j}p(y_{i}|c_{j})p(c_{j}|x'))=\sum _{j} p(y_{i}|c_{j}){\tilde {p}}(c_{j})\,}$

Parametre , sıfırdan artırıldıkça, kategori olasılık uzayında artan sayıda öznitelik belirli kritik eşiklerde odaklandığından yakın denetim altında tutulmalıdır. ${\görüntüleme stili \beta\,}$

Bir örnek

Aşağıdaki durum, rastgele girdiler ve tarafından oluşturulan iki çıktı kategorisi ile dört kadranlı bir çarpanda kümelemeyi inceler . Bu işlev, her kategori için uzamsal olarak ayrılmış iki kümeye sahiptir ve bu nedenle yöntemin bu tür dağılımları işleyebileceğini gösterir. ${\görüntüleme stili u,v\,}$${\görüntüleme stili \pm 1\,}$${\displaystyle y=\operatör adı {işaret} (uv)\,}$

20 numune alınır, kareye eşit olarak dağıtılır . Kategori sayısının ötesinde kullanılan küme sayısı, bu durumda iki, performans üzerinde çok az etkiye sahiptir ve sonuçlar, parametreler kullanılarak iki küme için gösterilmektedir . ${\görüntüleme stili [-1,1]^{2}\,}$${\displaystyle \lambda =3,\,\beta =2.5}$

Mesafe fonksiyonu, koşullu dağılımın 2 × 20 matris olduğu yerdir.${\displaystyle d_{i,j}={\Big |}x_{i}-x_{j}{\Big |}^{2}}$${\displaystyle x_{i}=(u_{i},v_{i})^{T}\,}$${\görüntüleme stili p(y|x)\,}$

${\displaystyle {\begin{aligned}&Pr(y_{i}=1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=1\,\\&Pr( y_{i}=-1)=1{\text{ if }}\operatorname {sign} (u_{i}v_{i})=-1\,\end{hizalı}}}$

ve başka yerde sıfır.

2. satırdaki toplama, +1 veya -1 eğitim değerlerini temsil eden yalnızca iki değeri içerir, ancak yine de iyi çalışır. Şekil, Y = 1'i temsil eden '0' ve Y = -1'i temsil eden 'x' ile yirmi örneğin konumlarını göstermektedir . Birlik olabilirlik oranı seviyesindeki kontur gösterilir,

${\displaystyle L={\frac {\Pr(1)}{\Pr(-1)}}=1}$

kare üzerinde yeni bir örnek taranırken. Teorik olarak kontur ve koordinatları ile hizalanmalıdır, ancak bu kadar küçük örnek sayıları için bunun yerine örnek noktaların sahte kümelerini izlemişlerdir. ${\görüntüleme stili x'\,}$${\görüntüleme stili u=0\,}$${\görüntüleme stili v=0\,}$

Sinir ağı/bulanık mantık analojileri

Bu algoritma, tek bir gizli katmana sahip bir sinir ağına biraz benzer. Dahili düğümler, kümeler tarafından temsil edilir ve ağ ağırlıklarının birinci ve ikinci katmanları sırasıyla koşullu olasılıklardır ve . Bununla birlikte, standart bir sinir ağından farklı olarak, algoritma tamamen örnek değerlerin kendisinden ziyade girdi olarak olasılıklara dayanırken, dahili ve çıkış değerlerinin tümü koşullu olasılık yoğunluk dağılımlarıdır. Doğrusal olmayan işlevler, uzaklık ölçütü (veya etki işlevleri/radyal temel işlevler ) ve sigmoid işlevler yerine geçiş olasılıklarında kapsüllenir . ${\displaystyle c_{j}\,}$${\displaystyle p(c_{j}|x_{i})\,}$${\displaystyle p(y_{k}|c_{j})\,}$${\görüntüleme stili f(.)\,}$

Blahut-Arimoto üç satır alogritmadır tekrarlamalar onlarca, hızla yakınsar ve farklılaşan tarafından , ve ve küme kardinalitesi, özellikleri odak çeşitli seviyeleri elde edilebilir. ${\görüntüleme stili \beta\,}$${\ Displaystyle \ lambda \,}$${\görüntüleme stili f\,}$

İstatistiksel yumuşak kümeleme tanımı , bulanık mantığın sözel bulanık üyelik kavramıyla biraz örtüşmektedir . ${\displaystyle p(c_{i}|x_{j})\,}$

Uzantılar

İlginç bir uzantı, yan bilgilerle bilgi darboğazı durumudur. Burada bilgi, bir hedef değişken hakkında en üst düzeye çıkarılır ve bir başkası hakkında en aza indirilir, verilerin seçilen yönleri hakkında bilgilendirici bir temsil öğrenilir. resmen

${\displaystyle \min _{p(t|x)}\,\,I(X;T)-\beta ^{+}I(T;Y^{+})+\beta ^{-}I( T;Y^{-})}$

bibliyografya

• Weiss, Y. (1999), "Özvektörleri kullanarak bölümleme: birleştirici bir bakış", Proceedings IEEE Uluslararası Bilgisayarla Görme Konferansı (PDF) , s. 975–982
• P. Harremoes ve N. Tishby "Yeniden Ziyaret Edilen Bilgi Darboğazı veya İyi Bir Bozulma Önlemi Nasıl Seçilir". Uluslararası Bilgi Teorisi Sempozyumu (ISIT) 2007 tutanaklarında

Referanslar