Bilgi teorisindeki eşitsizlikler - Inequalities in information theory

Eşitsizlikler çalışmasında çok önemlidir bilgi teorisi. Bu eşitsizliklerin ortaya çıktığı birkaç farklı bağlam vardır.

Entropik eşitsizlikler

Bir demet düşünün nın-nin sonlu (veya en fazla sayılır şekilde) desteklenir rastgele değişkenler aynısında olasılık uzayı. Onlar 2kişin alt kümeler, bunun için (bağlantı ) entropiler hesaplanabilir. Örneğin, ne zaman n = 2, entropileri düşünebiliriz ve . Aşağıdaki eşitsizlikleri karşılarlar (bunlar birlikte iki rastgele değişkenin marjinal ve birleşik entropilerinin aralığını karakterize eder):

Aslında, bunların hepsi tek bir eşitsizliğin özel durumları olarak ifade edilebilir. koşullu karşılıklı bilgi, yani

nerede , , ve her biri rasgele değişkenler koleksiyonumuzun bazı keyfi (muhtemelen boş) alt kümesinin ortak dağılımını gösterir. Bunun doğrusal kombinasyonları olarak türetilebilen eşitsizlikler şu şekilde bilinir: Shannon tipi eşitsizlikler.

Daha büyük için olası entropi değerleri üzerinde başka kısıtlamalar da vardır.Bunu kesinleştirmek için bir vektör içinde alt kümeleri tarafından indekslenmiş olduğu söyleniyor entropik bir eklem varsa, ayrık dağılımı n rastgele değişkenler öyle ki onların ortak entropi, her alt küme için Entropik vektörler kümesi gösterilir Yeung'un notasyonunu takiben.[1]Kapalı veya dışbükey değildir , ama o topolojik kapanma dışbükey olduğu bilinmektedir ve bu nedenle, tüm entropik vektörler tarafından karşılanan (sonsuz sayıda) doğrusal eşitsizliklerle karakterize edilebilir. entropik eşitsizlikler.

Shannon tipi eşitsizlikleri (ancak diğer entropik eşitsizlikleri değil) karşılayan tüm vektörlerin kümesi şunları içerir: Bu sınırlama katıdır ve diğer eşitsizlikler olarak bilinir Shannon olmayan tip Zhang ve Yeung, Shannon tipi olmayan ilk eşitsizliği bildirdi.[2] Matus[3] hiçbir sonlu eşitsizlik kümesinin tüm entropik eşitsizlikleri (doğrusal kombinasyonlarla) karakterize edemeyeceğini kanıtladı. Başka bir deyişle bölge değil politop.

Kullback-Leibler ayrışması için alt sınırlar

Bilgi teorisindeki pek çok önemli eşitsizlik, aslında Kullback-Leibler sapması. Shannon tipi eşitsizlikler bile bu kategorinin bir parçası olarak kabul edilebilir, çünkü iki değişkenli karşılıklı bilgi marjinallerin çarpımına göre ortak dağılımın Kullback-Leibler ayrışması olarak ifade edilebilir ve bu nedenle bu eşitsizlikler özel bir durum olarak görülebilir. Gibbs eşitsizliği.

Öte yandan, Kullback-Leibler ayrışması için yararlı üst sınırlar elde etmek çok daha zor görünmektedir. Bunun nedeni, Kullback-Leibler ayrışması DKL(P||Q) referans dağılımında çok nadir görülen olaylara çok hassas bir şekilde bağlıdır Q. DKL(P||Q) dağılımda sonlu sıfır olmayan olasılık olayı olarak sınırsız artar P referans dağıtımda son derece nadir hale geliyor Qve aslında DKL(P||Q) sıfır olmayan olasılıklı bir olay olsa bile tanımlanmaz. P sıfır olasılığı var Q. (Bu nedenle gereklilik P kesinlikle sürekli olmak Q.)

Gibbs eşitsizliği

Bu temel eşitsizlik, Kullback-Leibler sapması negatif değildir.

Kullback eşitsizliği

Kullback-Leibler ayrışmasına ilişkin bir başka eşitsizlik şu şekilde bilinir: Kullback eşitsizliği.[4] Eğer P ve Q vardır olasılık dağılımları ile gerçek çizgide P kesinlikle sürekli göre Q, ve kimin ilk anları var o zaman

nerede ... büyük sapmalar oran fonksiyonuyani dışbükey eşlenik of biriken üreten fonksiyon Q, ve İlk mi an nın-nin P.

Cramér – Rao bağlı bu sonucun doğal bir sonucudur.

Pinsker eşitsizliği

Pinsker eşitsizliği ile ilgilidir Kullback-Leibler sapması ve toplam varyasyon mesafesi. Eğer P, Q iki olasılık dağılımları, sonra

nerede

Kullback-Leibler ayrışması nats ve

toplam varyasyon mesafesidir.

Diğer eşitsizlikler

Hirschman belirsizliği

1957'de[5] Hirschman, (oldukça iyi davranılmış) bir işlev için öyle ki ve Onun Fourier dönüşümü toplamı diferansiyel entropiler nın-nin ve negatif değildir, yani

Hirschman varsaydı ve daha sonra kanıtlandı,[6] daha keskin bir sınır hangi durumda elde edilir Gauss dağılımı, bu eşitsizliğin sağ tarafının yerini alabilir. Bu, Weyl'in Heisenberg'in formülasyonunu ima ettiği ve ondan daha güçlü olduğu için özellikle önemlidir. belirsizlik ilkesi.

Tao eşitsizliği

Kesikli rastgele değişkenler verildiğinde , , ve , öyle ki değerleri yalnızca [−1, 1] aralığında alır ve Tarafından belirlenir (öyle ki ), sahibiz[7][8]

koşullu beklentiyi koşullu karşılıklı bilgi. Bu basit bir sonucudur Pinsker eşitsizliği. (Not: Radikalin içindeki düzeltme faktörü log 2, koşullu karşılıklı bilgiyi ölçtüğümüz için ortaya çıkar. bitler ziyade nats.)

Ayrıca bakınız

Referanslar

  1. ^ Yeung, R.W. (1997). "Doğrusal bilgi eşitsizlikleri için bir çerçeve". Bilgi Teorisi Üzerine IEEE İşlemleri. 43 (6): 1924–1934. doi:10.1109/18.641556.)
  2. ^ Zhang, Z .; Yeung, R.W. (1998). "Bilgi eşitsizlikleri yoluyla entropi fonksiyonunun karakterizasyonu üzerine". Bilgi Teorisi Üzerine IEEE İşlemleri. 44 (4): 1440–1452. doi:10.1109/18.681320.
  3. ^ Matus, F. (2007). Sonsuz sayıda bilgi eşitsizliği. 2007 IEEE Uluslararası Bilgi Teorisi Sempozyumu.
  4. ^ Fuchs, Aimé; Letta, Giorgio (1970). L'inégalité de Kullback. Uygulama à la théorie de l'estimation. Séminaire de Probabilités. Matematikte Ders Notları. 4. Strasbourg. s. 108–131. doi:10.1007 / bfb0059338. ISBN  978-3-540-04913-5. BAY  0267669.
  5. ^ Hirschman, I. I. (1957). "Entropi Üzerine Bir Not". Amerikan Matematik Dergisi. 79 (1): 152–156. doi:10.2307/2372390. JSTOR  2372390.
  6. ^ Beckner, W. (1975). "Fourier Analizinde Eşitsizlikler". Matematik Yıllıkları. 102 (6): 159–182. doi:10.2307/1970980. JSTOR  1970980.
  7. ^ Tao, T. (2006). "Szemerédi'nin düzenlilik lemması yeniden ziyaret edildi". Katkıda bulunun. Ayrık Matematik. 1: 8–28. arXiv:matematik / 0504472. Bibcode:2005math ...... 4472T.
  8. ^ Ahlswede, Rudolf (2007). "Tao'nun koşullu beklenti ve koşullu karşılıklı bilgiye ilişkin eşitsizliğinin son şekli". İletişim Matematiğindeki Gelişmeler. 1 (2): 239–242. doi:10.3934 / amc.2007.1.239.

Dış bağlantılar

  • Thomas M. Cover, Joy A. Thomas. Bilgi Teorisinin Unsurları, Bölüm 16, "Bilgi Teorisinde Eşitsizlikler" John Wiley & Sons, Inc. 1991 Baskı ISBN  0-471-06259-6 İnternet üzerinden ISBN  0-471-20061-1 pdf[kalıcı ölü bağlantı ]
  • Amir Dembo, Thomas M. Cover, Joy A. Thomas. Bilgi Teorik Eşitsizlikleri. Bilgi Teorisi IEEE İşlemleri, Cilt. 37, No.6, Kasım 1991. pdf