Entropi (bilgi teorisi) - Entropy (information theory)

İki bit entropi: İki adil yazı tura durumunda, bit cinsinden bilgi entropisi, olası sonuçların sayısının 2 tabanında logaritmasıdır; iki jetonla dört olası sonuç ve iki bit entropi vardır. Genel olarak bilgi entropisi, tüm olası sonuçlar göz önüne alındığında, bir olay tarafından iletilen ortalama bilgi miktarıdır.

bilgi teorisi
Entropi diferansiyel entropi koşullu entropi ortak entropi Karşılıklı bilgi Koşullu karşılıklı bilgi göreli entropi entropi oranı Ayrık noktaların sınırlama yoğunluğu Sonlu blok uzunluk bilgi teorisi
Asimptotik eşbölme özelliği Hız-bozulma teorisi
Shannon'ın kaynak kodlama teoremi Kanal kapasitesi Gürültülü kanal kodlama teoremi Shannon-Hartley teoremi
v T e

Gelen bilgi teorisi , entropi a rastgele değişkenin "bilgi", "sürpriz" veya "belirsizlik" değişkenin olası sonuçlar doğasında ortalama seviyesidir. Bilgi entropisi kavramı, Claude Shannon tarafından 1948 tarihli " A Mathematical Theory of Communication " makalesinde tanıtıldı ve aynı zamanda Shannon entropisi olarak da anılır . Örnek olarak, tura gelme olasılığı p ve tura gelme olasılığı 1 - p olan taraflı bir madeni para düşünün . Bir sonucun diğerine üstün gelmesini beklemek için hiçbir neden olmadığında, maksimum sürpriz p = 1/2 içindir . Bu durumda yazı tura bir bitlik bir entropiye sahiptir . Minimum sürpriz, olay bilindiğinde ve entropi sıfır bit olduğunda p = 0 veya p = 1 içindir . p'nin diğer değerleri, sıfır ve bir bit arasında farklı entropiler verir.

Olası sonuçları olan , ayrı bir rastgele değişken verildiğinde , olasılıkla ortaya çıkan entropi resmi olarak şu şekilde tanımlanır: ${\görüntüleme stili X}$${\displaystyle x_{1},...,x_{n}}$${\displaystyle \mathrm {P} (x_{1}),...,\mathrm {P} (x_{n}),}$${\görüntüleme stili X}$

burada değişkenin olası değerlerinin toplamını belirtir. Baz seçimi , logaritma , farklı uygulamalar için değişiklik gösterir. Taban 2, bit (veya " shannon ") birimini verirken, taban e "doğal birimler" nat verir ve taban 10 "dits", "bans" veya " hartley " birimlerini verir . Entropi Eşdeğer tanımıdır beklenen değer ve öz bilgi bir değişkenin. ${\görüntüleme stili \Sigma }$${\görüntüleme stili \log }$

Entropi ilk olarak Shannon tarafından bir veri iletişim sisteminin üç unsurdan oluştuğu iletişim teorisinin bir parçası olarak yaratılmıştır : bir veri kaynağı, bir iletişim kanalı ve bir alıcı. "Temel iletişim sorunu" - Shannon tarafından ifade edildiği gibi - alıcının, kanaldan aldığı sinyale dayanarak kaynak tarafından hangi verilerin üretildiğini tanımlayabilmesidir. Shannon, bir veri kaynağından gelen mesajları kodlamanın, sıkıştırmanın ve iletmenin çeşitli yollarını düşündü ve ünlü kaynak kodlama teoreminde , entropinin, kaynaktan gelen verilerin tamamen gürültüsüz bir kanala kayıpsız olarak ne kadar iyi sıkıştırılabileceği konusunda mutlak bir matematiksel sınırı temsil ettiğini kanıtladı . Shannon, gürültülü kanal kodlama teoreminde gürültülü kanallar için bu sonucu önemli ölçüde güçlendirdi .

Bilgi teorisindeki entropi , istatistiksel termodinamikteki entropiye doğrudan benzer . Rastgele değişkenin değerleri mikro durumların enerjilerini gösterdiğinde analoji sonuçlanır, bu nedenle entropi için Gibbs formülü Shannon'ın formülüyle resmi olarak aynıdır. Entropi, kombinatorik gibi matematiğin diğer alanlarıyla ilgilidir . Tanım, entropinin bir değişkenin ortalama sonucunun ne kadar "şaşırtıcı" olduğunun bir ölçüsü olması gerektiğini belirleyen bir dizi aksiyomdan türetilebilir . Sürekli bir rastgele değişken için, diferansiyel entropi , entropiye benzer.

Tanıtım

Bilgi teorisinin temel fikri, iletilen bir mesajın "bilgisel değerinin", mesajın içeriğinin şaşırtıcı olma derecesine bağlı olmasıdır. Bir olay çok olasıysa, bu olayın beklendiği gibi gerçekleşmesi şaşırtıcı değildir (ve genellikle ilginç değildir); dolayısıyla böyle bir mesajın iletimi çok az yeni bilgi taşır. Ancak, bir olayın gerçekleşmesi olası değilse, olayın gerçekleştiğini veya olacağını öğrenmek çok daha bilgilendiricidir. Örneğin, belirli bir sayının bir piyangoda kazanan sayı olmayacağı bilgisi çok az bilgi sağlar, çünkü seçilen herhangi bir sayı neredeyse kesinlikle kazanmayacaktır. Ancak, belirli bir sayıda bilginin olacak çok düşük bir olasılık olayın sonucunu iletişim kurar, çünkü bir piyango kazanmak yüksek değere sahiptir.

Bilgi içeriği (aynı zamanda surprisal bir olayın) olasılık olarak artan bir fonksiyonu olan bir olayın azalır. Yani 1'e yakın olduğunda , o olayı görmenin "sürprizinin" düşük olduğunu söyleriz, ancak 0'a yakınsa, o olayı görmenin sürprizinin yüksek olduğunu söyleriz. Bu ilişkiyi yakalamanın olası bir yolu, sürprizi olarak tanımlamak olabilir , ancak olduğu durumlarda , 1'lik bir sürprize yol açacaktır (0 sürpriz olduğunu söylemek daha mantıklı olurdu). Bu nedenle, daha iyi bir işlev , olasılığın 1 üzerindeki logaritmasıdır ; bu, olayın olasılığı 1 olduğunda bize 0 sürpriz verir. Aslında, günlük, belirli bir karakterizasyon kümesini karşılayan tek işlevdir . ${\görüntüleme stili E}$${\görüntüleme stili p(E)}$${\görüntüleme stili P(E)}$${\görüntüleme stili P(E)}$${\displaystyle {\frac {1}{P(E)}}}$${\görüntüleme stili P(E)=1}$${\displaystyle \log \sol({\frac {1}{P(E)}}\sağ)}$

Bu nedenle, E'nin bilgisini (veya sürprizini) logaritmanın nerede olduğu ile veya eşdeğeri olarak tanımlayabiliriz . Entropi, rastgele bir denemenin sonucunu belirleyerek iletilen beklenen (yani ortalama) bilgi miktarını ölçer. Bu, bir zar atmanın bir yazı tura atmaktan daha yüksek entropiye sahip olduğu anlamına gelir, çünkü bir zar atışının her sonucu, bir yazı tura atışının ( ) her sonucundan daha küçük bir olasılığa (yaklaşık ) sahiptir . ${\displaystyle I(E)=-\log _{2}(p(E))}$${\displaystyle I(E)=\log _{2}\left({\frac {1}{p(E)}}\sağ)}$${\görüntüleme stili \log }$${\görüntüleme stili p=1/6}$${\görüntüleme stili p=1/2}$

Yazı tura atma örneğini düşünün. Tura gelme olasılığı yazı olasılığıyla aynıysa, yazı tura atma entropisi iki sonuçlu bir deneme için olabileceği kadar yüksektir. Yazı tura atışının sonucunu önceden tahmin etmenin bir yolu yoktur: Eğer birinin seçim yapması gerekiyorsa, her iki tahmin de olasılıkla doğru olacağından, atışın tura veya tura geleceğini tahmin ederek elde edilecek ortalama bir avantaj yoktur. . Böyle bir yazı tura entropisine (bit olarak) sahiptir, çünkü eşit olasılıkla ortaya çıkan iki olası sonuç vardır ve gerçek sonucun öğrenilmesi bir bit bilgi içerir. Buna karşılık, iki yazı olan ve yazı olmayan bir yazı tura kullanarak yazı tura atıldığında, yazı tura her zaman tura geleceğinden entropi vardır ve sonuç mükemmel bir şekilde tahmin edilebilir. Benzer şekilde, denk olası değerlere sahip bir trit (yaklaşık 1.58496) bit bilgi içerir, çünkü üç değerden birine sahip olabilir. ${\ Displaystyle 1/2}$${\displaystyle \mathrm {H} (E)=1}$${\displaystyle \mathrm {H} (E)=0}$${\displaystyle \log _{2}3}$

Bir karakter dizisi olarak ele alınan İngilizce metin oldukça düşük entropiye sahiptir, yani oldukça tahmin edilebilirdir. Sırada ne olacağını tam olarak bilmiyorsak, örneğin 'e'nin 'z'den çok daha yaygın olacağından, 'qu' kombinasyonunun diğerlerinden çok daha yaygın olacağından oldukça emin olabiliriz. içinde bir 'q' ile kombinasyon ve 'th' kombinasyonu 'z', 'q' veya 'qu'dan daha yaygın olacaktır. İlk birkaç harften sonra genellikle kelimenin geri kalanı tahmin edilebilir. İngilizce metin, mesajın karakteri başına 0,6 ile 1,3 bit arasında entropiye sahiptir.

Eğer bir sıkıştırma şeması kayıpsızsa – ki burada sıkıştırmayı açarak tüm orijinal mesajı her zaman kurtarabilirsiniz – o zaman sıkıştırılmış bir mesaj orijinal ile aynı miktarda bilgiye sahiptir ancak daha az karakterle iletilir. Karakter başına daha fazla bilgiye (daha yüksek entropi) sahiptir. Sıkıştırılmış bir iletinin daha az fazlalığı vardır . Shannon kaynak teoremi kodlama kayıpsız bir sıkıştırma düzeni için, ortalama olarak değil, kompres mesaj olabilir devletler fazla mesajın bit başına bilgilerin birden bit, ancak herhangi bir değeri, bu daha az mesajın bit başına bilgilerin birden biraz uygun kullanılarak elde edilebilir kodlama şeması. Bir mesajın bit başına entropisi ile o mesajın uzunluğu çarpımı, mesajın toplam ne kadar bilgi içerdiğinin bir ölçüsüdür.

Eğer biri 4 karakter 'A', 'B', 'C' ve 'D' içeren dizileri iletecek olsaydı, iletilen bir mesaj 'ABADDCAB' olabilir. Bilgi teorisi, bunu iletecek mümkün olan en küçük bilgi miktarını hesaplamanın bir yolunu sunar. 4 harfin tümü eşit derecede olasıysa (%25), (ikili kanal üzerinden) her harfi 2 bit kodlamaktan (ikili olarak) daha iyi bir şey yapılamaz: 'A', '00', 'B' olarak kodlanabilir. '01', 'C' '10' ve 'D' '11' olarak. 'A' %70 olasılıkla, 'B' %26 ve 'C' ve 'D' her biri %2'lik bir olasılıkla oluşursa, değişken uzunluklu kodlar atanabilir, böylece '1' almak başka bir bite bakmayı söyler 2 bit sıralı 1 zaten alınmamışsa. Bu durumda, 'A' '0' (bir bit), 'B' '10', 'C' '110' ve D '111' olarak kodlanacaktır. Zamanın %70'inin yalnızca bir bitin, zamanın %26'sının iki bitin ve zamanın yalnızca %4'ünün 3 bitin gönderilmesi gerektiğini görmek kolaydır. Ortalama olarak, entropi daha düşük olduğundan ('A' ve ardından 'B'nin yüksek prevalansı nedeniyle - karakterlerin birlikte %96'sı) 2 bitten daha az gereklidir. Olasılık ağırlıklı günlük olasılıklarının toplamının hesaplanması, bu etkiyi ölçer ve yakalar.

Shannon teoremi ayrıca kayıpsız bir sıkıştırma şemasının tüm mesajları kısaltamayacağını ima eder . Bazı mesajlar daha kısa geliyorsa, güvercin deliği prensibi nedeniyle en az birinin daha uzun çıkması gerekir . Pratik kullanımda, bu genellikle bir sorun değildir, çünkü kişi genellikle anlamsız metin yerine İngilizce bir belge veya gürültüden ziyade dijital fotoğraflar gibi belirli mesaj türlerini sıkıştırmakla ilgilenir ve bir sıkıştırma algoritması, bazı olası veya ilginç olmayan dizileri daha büyük hale getirir.

Tanım

Adını Boltzmann'ın Η-teoreminden alan Shannon , olası değerlere ve olasılık kütle fonksiyonuna sahip ayrı bir rastgele değişkenin entropisini Η (Yunanca büyük harf eta ) şöyle tanımladı : ${\metin stili X}$${\textstyle \sol\{x_{1},\ldots ,x_{n}\sağ\}}$ ${\textstyle \mathrm {P} (X)}$

${\displaystyle \mathrm {H} (X)=\operatöradı {E} [\operatöradı {I} (X)]=\operatöradı {E} [-\log(\mathrm {P} (X))].}$

İşte bir beklenen değer operatörü ve ben bir bilgi içeriği arasında X . kendisi rastgele bir değişkendir. ${\ Displaystyle \ operatör adı {E} }$${\displaystyle \operatöradı {I} (X)}$

Entropi açıkça şu şekilde yazılabilir:

burada b bir baz ve logaritması kullanılır. Ortak değerleri b 2, olan Euler sayısı e ve 10, ve entropi gelen birimleri bit için b = 2 , NAT için b = e , ve yasaklar için b = 10 .

Durumunda P ( x _i ) = 0 bazı i , toplam kısmı karşılık gelen değeri 0 günlük _b (0) olarak alınır 0 ile tutarlıdır, sınır :

${\displaystyle \lim _{p\to 0^{+}}p\log(p)=0.}$

Ayrıca , iki değişkenin koşullu entropisini ve değerleri alarak ve sırasıyla şu şekilde tanımlayabiliriz : ${\görüntüleme stili X}$${\görüntüleme stili Y}$${\displaystyle x_{i}}$${\görüntüleme stili y_{j}}$

${\displaystyle \mathrm {H} (X|Y)=-\sum _{i,j}p(x_{i},y_{j})\log {\frac {p(x_{i},y_{) j})}{p(y_{j})}}}$

olasılığı nerede ve . Bu miktar, rastgele değişken verilen rastgele değişkendeki rastgelelik miktarı olarak anlaşılmalıdır . ${\görüntüleme stili p(x_{i},y_{j})}$${\displaystyle X=x_{i}}$${\görüntüleme stili Y=y_{j}}$${\görüntüleme stili X}$${\görüntüleme stili Y}$

Örnek

Bir yazı turasının entropisi Η( X ) (yani beklenen sürpriz ), bit olarak ölçülür, paranın eğilimine karşı grafiklendirilir Pr( X = 1) , burada X = 1 turaların bir sonucunu temsil eder.

Burada, entropi en fazla 1 bittir ve bir yazı tura sonucunun (2 olası değer) iletilmesi için ortalama en fazla 1 bit (adil bir para için tam olarak 1 bit) gerekir. Adil bir kalıbın sonucu (6 olası değer) entropi günlüğü ₂ 6 bit olacaktır.

Yazı veya tura gelme olasılığı bilinen, ancak mutlaka adil olmayan bir para atmayı düşünün; bu bir Bernoulli süreci olarak modellenebilir .

Madeni paranın bir sonraki atışının bilinmeyen sonucunun entropisi, madeni para adil ise (yani, yazı ve turaların her ikisinin de 1/2 olasılığı eşitse) maksimize edilir. Bu, bir sonraki atışın sonucunu tahmin etmek en zor olduğu için maksimum belirsizlik durumudur; yazı tura atmanın sonucu tam bir bit bilgi verir. Bunun nedeni ise

${\displaystyle {\begin{hizalanmış}\mathrm {H} (X)&=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log _{b} \mathrm {P} (x_{i})}\\&=-\sum _{i=1}^{2}{{\frac {1}{2}}\log _{2}{\frac { 1}{2}}}\\&=-\sum _{i=1}^{2}{{\frac {1}{2}}\cdot (-1)}=1\end{hizalı}} }$

Bununla birlikte, madeni paranın adil olmadığını, ancak p ve q olasılıklarıyla tura veya tura geldiğini biliyorsak , burada p ≠ q , o zaman daha az belirsizlik vardır. Her fırlatıldığında, bir tarafın diğerinden daha fazla gelmesi daha olasıdır. Azaltılmış belirsizlik, daha düşük bir entropide ölçülür: ortalama olarak, madeni paranın her atışı, bir tam bilgi bitinden daha azını verir. Örneğin, p = 0,7 ise, o zaman

$${\displaystyle {\begin{hizalanmış}\mathrm {H} (X)&=-p\log _{2}(p)-q\log _{2}(q)\\&=-0.7\log _ {2}(0.7)-0.3\log _{2}(0.3)\\&\yaklaşık -0.7\cdot (-0.515)-0.3\cdot (-1.737)\\&=0.8816<1\end{hizalı} }}$$

Tekdüze olasılık, maksimum belirsizliği ve dolayısıyla maksimum entropiyi verir. O halde entropi, yalnızca tek biçimli olasılık ile ilişkili değerden azalabilir. Uç nokta, asla tura gelmeyen çift başlı bir madeni para veya asla tura gelmeyen çift kuyruklu bir madeni paradır. O zaman belirsizlik yok. Entropi sıfırdır: Her yazı tura sonucu her zaman kesin olduğundan, her yazı tura atışı yeni bilgi vermez.

Entropi, bilgi uzunluğuna bölünerek normalleştirilebilir. Bu orana metrik entropi denir ve bilginin rastgeleliğinin bir ölçüsüdür.

karakterizasyon

Anlamını anlama -Σ p _ı log ( s _ı ) , ilk olarak bir bilgi fonksiyonu tanımlayabilir I bir olay açısından i olasılığı ile p _i . i olayının gözlemlenmesi nedeniyle elde edilen bilgi miktarı, Shannon'un bilginin temel özelliklerine ilişkin çözümünden kaynaklanmaktadır :

1. I ( p ) olduğu kadar monoton olarak azalan içinde p : bir olay olasılığında bir artış tersi şeklinde gözlemlenen bir etkinlik hakkında bilgiler ve yardımcısı azalır.
2. I( p ) ≥ 0 : bilgi negatif olmayan bir niceliktir.
3. I(1) = 0 : her zaman meydana gelen olaylar bilgi iletmez.
4. I( p ₁ , p ₂ ) = I( p ₁ ) + I( p ₂ ) : bağımsız olaylardan öğrenilen bilgiler, her olaydan öğrenilen bilgilerin toplamıdır.

İki bağımsız olay verildiğinde, eğer ilk olay n tane eşit olası sonuçtan birini ve diğeri m tane eşit olası sonuçtan birini veriyorsa, o zaman ortak olayın mn tane eşit olası sonucu vardır . Bunun anlamı , ilk değeri kodlamak için log ₂ ( n ) biti ve ikinci değeri kodlamak için log ₂ ( m ) gerekiyorsa, her ikisini de kodlamak için log ₂ ( mn ) = log ₂ ( m ) + log ₂ ( n ) gerekir. .

Shannon, uygun bir seçimin şu şekilde verildiğini keşfetti : ${\ Displaystyle \ operatör adı {I} }$

${\displaystyle \operatöradı {I} (p)=\log \left({\tfrac {1}{p}}\sağ)=-\log(p)}$

Aslında, sadece olası değerler şunlardır için . Buna ek olarak, bir değer seçme k değeri seçme eşdeğerdir için ve böylece, X tekabül için logaritmasının bir baz . Bu nedenle, entropi yukarıdaki dört özellikle karakterize edilir. ${\ Displaystyle \ operatör adı {I} }$${\displaystyle \operatöradı {I} (u)=k\log u}$${\görüntüleme stili k<0}$${\displaystyle x>1}$${\displaystyle k=-1/\log x}$

Kanıt

Biri sürekli olarak türevlenebilir olduğu varsayılan bilgi fonksiyonu olsun , birinin sahip olduğu: ${\textstyle \operatöradı {I} }$ ${\displaystyle {\begin{hizalanmış}&\operatöradı {I} (p_{1}p_{2})&=\ &\operatöradı {I} (p_{1})+\operatöradı {I} (p_{2 })&&\quad {\text{Özellikten başlayarak}}}\\&p_{2}\operatorname {I} '(p_{1}p_{2})&=\ &\operatorname {I} '(p_{ 1})&&\quad {\text{wrt türevini alarak}}\ p_{1}\\&\operatorname {I} '(p_{1}p_{2})+p_{1}p_{2}\ operatöradı {I} ''(p_{1}p_{2})&=\ &0&&\quad {\text{wrt türevini alarak}}\ p_{2}\\&\operatöradı {I} '(u)+ u\operatöradı {I} ''(u)&=\ &0&&\quad {\text{tanıtılan}}\,u=p_{1}p_{2}\\&(u\mapsto u\operatöradı {I} ' (u))'&=\ &0\end{hizalı}}}$ Bu diferansiyel denklem , herhangi birinin çözümüne yol açar . Özellik 2'ye yönlendirir . Özellikler 1 ve 3 daha sonra da tutun. ${\displaystyle \operatöradı {I} (u)=k\log u}$${\displaystyle k\in \mathbb {R} }$${\görüntüleme stili k<0}$

Farklı bilgilerin birimleri ( bit için ikili logaritma log ₂ , NAT için doğal logaritma ln , yasaklar için ondalık logaritmik günlüğüne ₁₀ ve benzeri) olan sabit katları birbirinden. Örneğin, adil bir yazı tura durumunda, turalar, yaklaşık 0,693 nats veya 0,301 ondalık basamak olan log ₂ (2) = 1 bit bilgi sağlar. Toplama özelliğinden dolayı, n atış , yaklaşık 0,693 n nat veya 0,301 n ondalık basamak olan n bit bilgi sağlar .

Anlamı gözlemlenen olayların (anlamı mesajlarının ) entropi tanımında önemli değil. Entropi yalnızca belirli bir olayı gözlemleme olasılığını hesaba katar, bu nedenle kapsüllediği bilgi, olayların kendi anlamı değil, temeldeki olasılık dağılımı hakkında bilgidir.

alternatif karakterizasyon

Entropinin başka bir karakterizasyonu aşağıdaki özellikleri kullanır. p _i = Pr( X = x _i ) ve Η _n ( p ₁ , ..., p _n ) = Η( X ) olarak ifade ederiz .

1. Süreklilik: H sürekli olmalıdır , böylece olasılık değerlerinin çok küçük bir miktar değiştirilmesi entropiyi sadece küçük bir miktar değiştirecektir.
2. Simetri: x _i sonuçları yeniden sıralanırsa H değişmemelidir . Yani, herhangi bir permütasyon için .${\displaystyle \mathrm {H} _{n}\left(p_{1},p_{2},\ldots p_{n}\right)=\mathrm {H} _{n}\left(p_{i_ {1}},p_{i_{2}},\ldots ,p_{i_{n}}\sağ)}$ ${\displaystyle \{i_{1},...,i_{n}\}}$${\görüntüleme stili \{1,...,n\}}$
3. Maksimum: tüm sonuçlar eşit derecede olasıysa maksimum olmalıdır, yani .${\displaystyle \mathrm {H} _{n}}$${\displaystyle \mathrm {H} _{n}(p_{1},\ldots ,p_{n})\leq \mathrm {H} _{n}\left({\frac {1}{n}} ,\ldots ,{\frac {1}{n}}\sağ)}$
4. Artan sonuç sayısı: eş olasılıklı olaylar için, entropi sonuçların sayısıyla birlikte artmalıdır, yani ${\displaystyle \mathrm {H} _{n}{\bigg (}\underbrace {{\frac {1}{n}},\ldots ,{\frac {1}{n}}} _{n}{ \bigg )}<\mathrm {H} _{n+1}{\bigg (}\underbrace {{\frac {1}{n+1}},\ldots ,{\frac {1}{n+1 }}} _{n+1}{\bigg )}.}$
5. Toplamsallık: her biri b ₁ , ..., b _k elemanlı k kutuya (alt sistemlere) bölünmüş n düzgün dağılmış elemandan oluşan bir topluluk verildiğinde , tüm grubun entropisi, entropinin toplamına eşit olmalıdır. kutuların sistemi ve kutuların bireysel entropileri, her biri belirli bir kutuda olma olasılığı ile ağırlıklandırılmıştır.

Toplamsallık kuralı aşağıdaki sonuçlara sahiptir: b _i pozitif tamsayılar için burada b ₁ + ... + b _k = n ,

${\displaystyle \mathrm {H} _{n}\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\sağ)=\mathrm {H} _{ k}\left({\frac {b_{1}}{n}},\ldots ,{\frac {b_{k}}{n}}\sağ)+\sum _{i=1}^{k }{\frac {b_{i}}{n}}\,\mathrm {H} _{b_{i}}\left({\frac {1}{b_{i}}},\ldots ,{\ frac {1}{b_{i}}}\sağ).}$

k = n , b ₁ = ... = b _n = 1 seçimi bu, belirli bir sonucun entropisinin sıfır olduğu anlamına gelir: Η ₁ (1) = 0 . Bu, n sembollü bir kaynak alfabenin etkinliğinin basitçe onun n -ary entropisine eşit olarak tanımlanabileceği anlamına gelir . Ayrıca bkz. Artıklık (bilgi teorisi) .

Diğer özellikler

Shannon entropisi, bazıları için entropiyi, X rastgele değişkeninin değerini ortaya çıkararak öğrenilen (veya ortadan kaldırılan belirsizliğin) miktarı olarak yorumlamak için yararlı olan aşağıdaki özellikleri karşılar :

• Olasılığı sıfır olan bir olay eklemek veya çıkarmak entropiye katkıda bulunmaz:

${\displaystyle \mathrm {H} _{n+1}(p_{1},\ldots ,p_{n},0)=\mathrm {H} _{n}(p_{1},\ldots ,p_ {n})}$.

• Jensen eşitsizliği kullanılarak doğrulanabilir .

${\displaystyle \mathrm {H} (X)=\operatöradı {E} \sol[\log _{b}\left({\frac {1}{p(X)}}\sağ)\sağ]\leq \log _{b}\left(\operatöradı {E} \sol[{\frac {1}{p(X)}}\sağ]\sağ)=\log _{b}(n)}$.

Log _b ( n )' nin bu maksimum entropisi, tek tip olasılık dağılımına sahip bir kaynak alfabesi ile etkin bir şekilde elde edilir: tüm olası olaylar eşit olasılıklı olduğunda belirsizlik maksimumdur.

• ( X , Y ) (yani X ve Y'nin aynı anda değerlendirilmesi ) değerlendirilerek ortaya çıkan entropi veya bilgi miktarı, ardışık iki deney gerçekleştirerek ortaya çıkan bilgilere eşittir: önce Y'nin değeri değerlendirilir , ardından X'in değeri ortaya çıkar. Y'nin değerini bildiğinize göre . Bu şu şekilde yazılabilir:

${\displaystyle \mathrm {H} (X,Y)=\mathrm {H} (X|Y)+\mathrm {H} (Y)=\mathrm {H} (Y|X)+\mathrm {H} (X).}$

• Eğer nerede o zaman, bir işlevdir . Önceki formülü verimlere uygulamak${\görüntüleme stili Y=f(X)}$${\görüntüleme stili f}$${\displaystyle H(f(X)|X)=0}$${\görüntüleme stili H(X,f(X))}$

${\displaystyle \mathrm {H} (X)+\mathrm {H} (f(X)|X)=\mathrm {H} (f(X))+\mathrm {H} (X|f(X) ),}$

bu nedenle , bir değişkenin entropisi ancak ikincisi bir fonksiyondan geçirildiğinde azalabilir.${\görüntüleme stili H(f(X))\leq H(X)}$

• Eğer X ve Y iki bağımsız rasgele değişkenler, daha sonra değerini bilerek olan Y değerinin bilgimizi etkilemez X (iki bağımsızlığının birbirini etkilemez olmadığı için):

${\displaystyle \mathrm {H} (X|Y)=\mathrm {H} (X).}$

• İki eşzamanlı olayın entropisi, her bir olayın entropilerinin toplamından daha fazla değildir, yani , ancak ve ancak iki olay bağımsız ise eşitlikle.${\displaystyle \mathrm {H} (X,Y)\leq \mathrm {H} (X)+\mathrm {H} (Y)}$
• Entropi olan içbükey olasılık işlevinde , örneğin,${\displaystyle \mathrm {H} (p)}$${\görüntüleme stili p}$

${\displaystyle \mathrm {H} (\lambda p_{1}+(1-\lambda )p_{2})\geq \lambda \mathrm {H} (p_{1})+(1-\lambda )\ matematik {H} (p_{2})}$

tüm olasılık kütle fonksiyonları için ve . ${\displaystyle p_{1},p_{2}}$${\displaystyle 0\leq \lambda \leq 1}$

• Bu duruma göre, negatif entropi (negentropi) işlevi konvekstir ve bunun konveks konjugat olup LogSumExp .

Bakış açıları

termodinamik entropi ile ilişkisi

Entropi kelimesini bilgi teorisinde benimsemenin ilhamı, Shannon'ın formülü ile istatistiksel mekanikten bilinen çok benzer formüller arasındaki yakın benzerlikten geldi .

Olarak istatistik termodinamik termodinamik için en genel formül entropi S bir termodinamik sistem olup Gibbs entropi ,

${\displaystyle S=-k_{\text{B}}\sum p_{i}\ln p_{i}\,}$

burada k, _B ise Boltzmann sabiti , ve p _ı bir olasılığıdır mikro durum . Gibbs entropi tanımlandı J. Willard Gibbs tarafından önceki çalışma sonra 1878'de Boltzmann (1872).

Gibbs entropisi , 1927'de John von Neumann tarafından tanıtılan von Neumann entropisini vermek için neredeyse hiç değişmeden kuantum fiziği dünyasına dönüşür.

${\displaystyle S=-k_{\text{B}}\,{\rm {Tr}}(\rho \ln \rho )\,}$

burada ρ kuantum mekanik sisteminin yoğunluk matrisidir ve Tr izdir .

Günlük pratik düzeyde, bilgi entropisi ve termodinamik entropi arasındaki bağlantılar açık değildir. Fizikçiler ve kimyagerler, bir sistem termodinamiğin ikinci yasasına uygun olarak, değişmeyen bir olasılık dağılımından ziyade başlangıç ​​koşullarından kendiliğinden uzaklaştığından, entropideki değişikliklerle daha fazla ilgilenmeye eğilimlidirler . Boltzmann sabiti k _B'nin küçüklüğünün gösterdiği gibi, kimyasal ve fiziksel süreçlerdeki çok küçük miktarlardaki maddeler için bile S / k _B'deki değişiklikler , veri sıkıştırma veya sinyal işlemedeki herhangi bir şeye kıyasla son derece büyük olan entropi miktarlarını temsil eder . Klasik termodinamikte entropi, makroskopik ölçümlerle tanımlanır ve bilgi entropisi tanımının merkezinde yer alan herhangi bir olasılık dağılımına atıfta bulunmaz.

Termodinamik ile şimdi bilgi teorisi olarak bilinen şey arasındaki bağlantı ilk olarak Ludwig Boltzmann tarafından yapılmış ve onun ünlü denklemiyle ifade edilmiştir :

${\displaystyle S=k_{\metin{B}}\ln(W)}$

belirli bir makro durumun termodinamik entropisi nerede (sıcaklık, hacim, enerji vb. gibi termodinamik parametrelerle tanımlanır), W , verilen makro durumu verebilen mikro durumların sayısıdır (çeşitli enerji durumlarındaki parçacıkların çeşitli kombinasyonları) ve k _B , Boltzmann sabitidir . Her mikrodurumun eşit derecede olası olduğu varsayılır, böylece belirli bir mikrodurumun olasılığı p _i = 1/W olur . Bu olasılıklar, Gibbs entropisi (veya eşdeğer olarak k _B çarpı Shannon entropisi) için yukarıdaki ifadeye ikame edildiğinde , Boltzmann denklemi ortaya çıkar. Teorik bilgi terimlerinde, bir sistemin bilgi entropisi, verilen makrodurumda bir mikrodurumu belirlemek için gereken "eksik" bilgi miktarıdır. ${\görüntüleme stili S}$

Jaynes'in (1957) görüşüne göre , istatistiksel mekanik tarafından açıklandığı şekliyle termodinamik entropi, Shannon'ın bilgi teorisinin bir uygulaması olarak görülmelidir : termodinamik entropi, ayrıntılı mikroskobik durumu tanımlamak için gereken Shannon bilgisinin miktarıyla orantılı olarak yorumlanır. orantı sabiti sadece Boltzmann sabiti olmak üzere, yalnızca klasik termodinamiğin makroskopik değişkenleri cinsinden bir tanımla açıklanmayan sistemin durumu . Bir sisteme ısı eklemek, termodinamik entropisini arttırır, çünkü sistemin makroskopik değişkenlerinin ölçülebilir değerleriyle tutarlı olan olası mikroskobik durumlarının sayısını arttırır ve herhangi bir tam durum açıklamasını daha uzun hale getirir. (Makaleye bakın: maksimum entropi termodinamiği ). Maxwell'in şeytanı (varsayımsal olarak) tek tek moleküllerin durumları hakkındaki bilgileri kullanarak bir sistemin termodinamik entropisini azaltabilir; ancak, Landauer (1961'den) ve iş arkadaşlarının gösterdiği gibi, iblisin kendisinin işlev görmesi için süreçteki termodinamik entropiyi, en azından ilk elde etmeyi ve saklamayı önerdiği Shannon bilgisi miktarı kadar artırması gerekir; ve böylece toplam termodinamik entropi azalmaz (bu da paradoksu çözer). Landauer ilkesi , modern bilgisayarlar çok daha az verimli olsa da, bir bilgisayarın belirli bir miktarda bilgiyi işlemek için üretmesi gereken ısı miktarına daha düşük bir sınır koyar.

Veri sıkıştırma

Entropi, olasılıksal bir model bağlamında tanımlanır. Bağımsız adil jeton atışları, atış başına 1 bitlik bir entropiye sahiptir. Her zaman uzun bir B dizisi üreten bir kaynağın entropisi 0'dır, çünkü bir sonraki karakter her zaman bir 'B' olacaktır.

Entropiler veri kaynağının kodlamak için gereken, sembol başına gerekli bilgi oranının ortalama sayısı anlamına gelir. Shannon'ın insan tahmin edicileriyle yaptığı deneyler, İngilizce'de karakter başına 0,6 ile 1,3 bit arasında bir bilgi oranı gösteriyor; PPM sıkıştırma algoritması İngilizce metinde karakteri başına 1.5 bit sıkıştırma oranı elde edebilirsiniz.

Shannon'ın entropi tanımı, bir bilgi kaynağına uygulandığında, kaynağı kodlanmış ikili rakamlar olarak güvenilir bir şekilde iletmek için gereken minimum kanal kapasitesini belirleyebilir. Shannon'ın entropisi, mesajın belirlenen (veya tahmin edilebilir) kısmının aksine bir mesajda bulunan bilgiyi ölçer. İkincisinin örnekleri, dil yapısındaki fazlalığı veya harf veya kelime çiftlerinin, üçlülerin vb. oluşum sıklıklarıyla ilgili istatistiksel özellikleri içerir.

Minimum kanal kapasitesi teoride tipik küme kullanılarak veya pratikte Huffman , Lempel–Ziv veya aritmetik kodlama kullanılarak gerçekleştirilebilir . (Ayrıca bkz . Kolmogorov karmaşıklığı .) Pratikte, sıkıştırma algoritmaları kasıtlı olarak, hatalara karşı koruma sağlamak için sağlama toplamı biçiminde bazı makul fazlalıklar içerir .

Science dergisinde 2011 yılında yapılan bir araştırma, 2007 yılında mevcut olan en etkili sıkıştırma algoritmalarına göre normalleştirilmiş optimal olarak sıkıştırılmış bilgileri depolamak ve iletmek için dünyanın teknolojik kapasitesini tahmin ediyor, bu nedenle teknolojik olarak mevcut kaynakların entropisini tahmin ediyor.

Yazarlar, 1986'da ve yine 2007'de insanlığın bilgi depolamak için (tamamen entropik olarak sıkıştırılmış) teknolojik kapasitesini tahmin ediyor. Bilgileri üç kategoriye ayırıyorlar - bir ortamda bilgi depolamak, tek yönlü yayın ağları aracılığıyla bilgi almak veya bilgi alışverişi yapmak iki yönlü telekomünikasyon ağları aracılığıyla

Çeşitliliğin bir ölçüsü olarak entropi

Entropi, çeşitliliği ölçmenin birkaç yolundan biridir. Spesifik olarak, Shannon entropi logaritmasıdır ¹ D , gerçek çeşitlilik parametresi göstergesi 1'e eşittir.

entropinin sınırlamaları

Bilgi içeriğini bir şekilde matematiksel olarak nicelleştiren bir dizi entropi ile ilgili kavram vardır:

• öz bilgi Belirli bir olasılık dağılımı alınan bireysel bir mesaj veya sembolün,
• entropi mesajlar veya semboller, belirli bir olasılık dağılımının ve
• Entropiler a stokastik süreç .

("Öz bilgi oranı", belirli bir stokastik süreç tarafından üretilen belirli bir mesaj veya sembol dizisi için de tanımlanabilir: bu, durağan bir süreç durumunda her zaman entropi oranına eşit olacaktır .) Diğer bilgi miktarları farklı bilgi kaynaklarını karşılaştırmak veya ilişkilendirmek için de kullanılır.

Yukarıdaki kavramları karıştırmamak önemlidir. Hangisinin kastedildiği çoğu zaman sadece bağlamdan anlaşılır. Örneğin, biri İngilizcenin "entropisinin" karakter başına yaklaşık 1 bit olduğunu söylediğinde, aslında İngilizceyi stokastik bir süreç olarak modelliyor ve entropi oranından bahsediyor . Shannon, terimi bu şekilde kullandı.

Çok büyük bloklar kullanılırsa, karakter başına entropi hızı tahmini, dizinin olasılık dağılımı tam olarak bilinmediğinden yapay olarak düşük olabilir; bu sadece bir tahmindir. Şimdiye kadar yayınlanmış her kitabın metni, her sembolün tam bir kitabın metni olduğu bir dizi olarak ele alınırsa ve N yayınlanmış kitap varsa ve her kitap yalnızca bir kez yayınlanırsa, her kitabın olasılığının tahmini şöyledir: 1/ N ve entropi (bit olarak) −log ₂ (1/ N ) = log ₂ ( N ) şeklindedir . Pratik bir kod olarak bu, her kitaba benzersiz bir tanımlayıcı atamaya ve kitaba atıfta bulunmak istendiğinde kitabın metni yerine onu kullanmaya karşılık gelir . Bu, kitaplar hakkında konuşmak için son derece yararlıdır, ancak tek bir kitabın veya genel olarak dilin bilgi içeriğini karakterize etmek için o kadar yararlı değildir: Olasılık dağılımını bilmeden kitabı tanımlayıcısından yeniden oluşturmak mümkün değildir, yani , tüm kitapların tam metni. Ana fikir, olasılıksal modelin karmaşıklığının dikkate alınması gerektiğidir. Kolmogorov karmaşıklığı , herhangi bir özel olasılık modelinden bağımsız bir dizinin bilgi içeriğinin değerlendirilmesine izin veren bu fikrin teorik bir genellemesidir; diziyi çıkaran evrensel bir bilgisayar için en kısa programı dikkate alır . Belirli bir model için bir dizinin entropi oranını ve kod çizelgesini (yani olasılıksal model) elde eden bir kod, böyle bir programdır, ancak en kısa olmayabilir.

Fibonacci dizisi 1, 1, 2, 3, 5, 8, 13, .... diziyi bir mesaj olarak ve her sayıyı bir sembol olarak ele alırsak, mesajdaki karakter sayısı kadar sembol vardır. yaklaşık olarak log ₂ ( n )' lik bir entropi . Fibonacci dizisinin ilk 128 sembolünün entropisi yaklaşık 7 bit/semboldür, ancak dizi n = 3 için bir formül [ F( n ) = F( n −1) + F( n −2) kullanılarak ifade edilebilir. , 4, 5, ... , F(1) =1 , F(2) = 1 ] ve bu formül çok daha düşük entropiye sahiptir ve Fibonacci dizisinin herhangi bir uzunluğu için geçerlidir.

Kriptografide entropinin sınırlamaları

İn şifreleme , entropi genellikle yaklaşık gerçek olsa da, bir kriptografik anahtar belirsizliğin bir ölçüsü olarak kullanılır belirsizlik ölçülememiştir. Örneğin, tekdüze ve rastgele oluşturulmuş 128 bitlik bir anahtarın 128 bit entropisi vardır. Ayrıca kaba kuvvetle kırılmak için (ortalama olarak) tahminler gerekir. Entropi, olası anahtarlar tekdüze seçilmezse gereken tahmin sayısını yakalamada başarısız olur. Bunun yerine, bir kaba kuvvet saldırısı için gereken çabayı ölçmek için tahminde bulunma adı verilen bir ölçü kullanılabilir. ${\ Displaystyle 2^{127}}$

Kriptografide kullanılan tek tip olmayan dağılımlardan başka problemler ortaya çıkabilir. Örneğin, özel veya kullanan 1.000.000 basamaklı bir ikili tek seferlik ped . Ped 1.000.000 bit entropiye sahipse, mükemmeldir. Ped 999,999 bit entropiye sahipse, eşit olarak dağıtılmışsa (pedin her bir biti 0,999999 bit entropiye sahiptir) iyi bir güvenlik sağlayabilir. Ancak, ilk bitin sabit olduğu ve kalan 999.999 bitin tamamen rastgele olduğu pedde 999.999 bit entropi varsa, şifreli metnin ilk biti hiç şifrelenmeyecektir.

Markov süreci olarak veri

Metin için entropi tanımlamanın yaygın bir yolu, metnin Markov modeline dayanmaktadır . Bir sipariş-0 kaynağı için (her karakter son karakterlerden bağımsız olarak seçilir), ikili entropi şöyledir:

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum p_{i}\log p_{i},}$

burada p _i olasılığıdır i . Birinci dereceden bir Markov kaynağı için (bir karakter seçme olasılığının yalnızca hemen önceki karaktere bağlı olduğu bir kaynak ), entropi oranı :

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}\ p_{i}(j)\log p_{i}( J),}$

burada i bir durumdur (belirli önceki karakterler) ve önceki karakter olarak i verilen j'nin olasılığıdır . ${\displaystyle p_{i}(j)}$

İkinci dereceden bir Markov kaynağı için entropi oranı

${\displaystyle \mathrm {H} ({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\sum _{k}p_{ i,j}(k)\ \log \ p_{i,j}(k).}$

Verimlilik (normalleştirilmiş entropi)

Tekdüze olmayan dağılıma sahip bir kaynak alfabe, bu sembollerin tekdüze dağılıma sahip olmasından (yani "optimize edilmiş alfabe") daha az entropiye sahip olacaktır. Entropideki bu eksiklik verimlilik denilen bir oran olarak ifade edilebilir:

${\displaystyle \eta (X)={\frac {H}{H_{max}}}=-\sum _{i=1}^{n}{\frac {p(x_{i})\log _ {b}(p(x_{i}))}{\log _{b}(n)}}}$

Logaritmanın temel özelliklerini uygulayarak, bu miktar şu şekilde de ifade edilebilir:

${\displaystyle \eta (X)=-\sum _{i=1}^{n}{\frac {p(x_{i})\log _{b}(p(x_{i}))}{ \log _{b}(n)}}=\sum _{i=1}^{n}{\frac {\log _{b}(p(x_{i})^{-p(x_{i) })})}{\log _{b}(n)}}=\sum _{i=1}^{n}\log _{n}(p(x_{i})^{-p(x_) {i})})=\log _{n}(\prod _{i=1}^{n}p(x_{i})^{-p(x_{i})})}$

Verimlilik, bir iletişim kanalının etkin kullanımını ölçmede fayda sağlar . Entropi maksimum entropiye bölündüğünden bu formülasyona normalleştirilmiş entropi de denir . Ayrıca, yukarıdaki son logaritma içindeki duyarsızlıkla gösterildiği gibi , verimlilik (pozitif) baz b'nin seçimine kayıtsızdır . ${\görüntüleme stili {\log _{b}(n)}}$

Sürekli rastgele değişkenler için entropi

diferansiyel entropi

Shannon entropisi, ayrık değerler alan rastgele değişkenlerle sınırlıdır. Gerçek çizgi üzerinde sonlu veya sonsuz desteğe sahip olasılık yoğunluk fonksiyonu f ( x ) ile sürekli bir rastgele değişken için karşılık gelen formül , entropinin yukarıdaki formu bir beklenti olarak kullanılarak analoji ile tanımlanır: ${\displaystyle \mathbb {X} }$

${\displaystyle h[f]=\operatöradı {E} [-\ln(f(x))]=-\int _{\mathbb {X} }f(x)\ln(f(x))\, dx.}$

Bu, diferansiyel entropidir (veya sürekli entropidir). Sürekli entropi bir ön-madde h [ f ] fonksiyonel ifadesidir Hm olarak , H-teoremi arasında Boltzmann .

Her iki fonksiyon arasındaki benzerlik düşündürücü olsa da, şu soru sorulmalıdır: diferansiyel entropi, Shannon ayrık entropisinin geçerli bir uzantısı mı? Diferansiyel entropi, Shannon ayrık entropisinin sahip olduğu bir takım özelliklerden yoksundur - hatta negatif olabilir - ve özellikle ayrık noktaların yoğunluğunu sınırlayan düzeltmeler önerilmiştir .

Bu soruyu cevaplamak için iki fonksiyon arasında bir bağlantı kurulmalıdır:

Çöp kutusu boyutu sıfıra giderken genel olarak sonlu bir ölçü elde etmek için . Ayrık durumda, kutu boyutu her (örtük) genişliğinin n (sonlu veya sonsuz) olasılıkları ile gösterilir depo s _n . Sürekli alan genelleştirildiğinden, genişlik açık hale getirilmelidir.

Bunu yapmak için , boyut kutularına ayrılmış sürekli bir f fonksiyonu ile başlayın . Ortalama değer teoremi ile her kutuda bir x _i değeri vardır , öyle ki ${\görüntüleme stili\Delta }$

${\displaystyle f(x_{i})\Delta =\int _{i\Delta }^{(i+1)\Delta }f(x)\,dx}$

f fonksiyonunun integrali ( Riemann anlamında) şu şekilde tahmin edilebilir:

${\displaystyle \int _{-\infty }^{\infty }f(x)\,dx=\lim _{\Delta \to 0}\sum _{i=-\infty }^{\infty }f (x_{i})\Delta }$

burada bu limit ve "bin boyutu sıfıra gider" eşdeğerdir.

belirteceğiz

${\displaystyle \mathrm {H} ^{\Delta }:=-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log \left(f(x_{i) })\Delta \sağ)}$

ve logaritmayı genişleterek,

${\displaystyle \mathrm {H} ^{\Delta }=-\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(f(x_{i})) -\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(\Delta )}$

Δ → 0 olarak

${\displaystyle {\begin{hizalanmış}\sum _{i=-\infty }^{\infty }f(x_{i})\Delta &\to \int _{-\infty }^{\infty }f (x)\,dx=1\\\sum _{i=-\infty }^{\infty }f(x_{i})\Delta \log(f(x_{i}))&\to \int _{-\infty }^{\infty }f(x)\log f(x)\,dx.\end{hizalı}}}$

Not; log (Δ) → -∞ olarak Δ → 0 , diferansiyel ya da sürekli bir entropi özel tanımlanmasını gerektirir:

${\displaystyle h[f]=\lim _{\Delta \to 0}\left(\mathrm {H} ^{\Delta }+\log \Delta \sağ)=-\int _{-\infty }^ {\infty }f(x)\log f(x)\,dx,}$

bu, daha önce belirtildiği gibi, diferansiyel entropi olarak adlandırılır. Bu, diferansiyel entropinin n → ∞ için Shannon entropisinin bir sınırı olmadığı anlamına gelir . Bunun yerine, Shannon entropisinin sınırından sonsuz bir kayma ile farklıdır (ayrıca bilgi boyutu hakkındaki makaleye bakın ).

Ayrık noktaların sınırlama yoğunluğu

Shannon entropi aksine diferansiyel entropi olduğunu, sonuç olarak çıkıyor değil belirsizlik veya bilgi genel iyi bir ölçüde. Örneğin, diferansiyel entropi negatif olabilir; ayrıca sürekli koordinat dönüşümleri altında değişmez değildir. Bu sorun, x boyutlu bir değişken olduğunda birimlerin değişmesiyle gösterilebilir . f(x) o zaman 1/x birimlerine sahip olacaktır . Logaritmanın argümanı boyutsuz olmalıdır, aksi halde uygun değildir, böylece yukarıda verilen diferansiyel entropi uygunsuz olacaktır. Eğer Δ , x'in bir "standart" değeriyse (yani "bin boyutu") ve bu nedenle aynı birimlere sahipse, değiştirilmiş diferansiyel entropi uygun biçimde şu şekilde yazılabilir:

${\displaystyle H=\int _{-\infty }^{\infty }f(x)\log(f(x)\,\Delta )\,dx}$

ve sonuç, x için herhangi bir birim seçimi için aynı olacaktır . Aslında, ayrık entropinin limiti, genel olarak sonsuz olan bir terimi de içerecektir . Bu beklenen bir durumdur: sürekli değişkenler, ayrıklaştırıldığında tipik olarak sonsuz entropiye sahip olacaktır. Ayrık noktaların limit yoğunluk gerçekten bir dağıtım onun niceleme sistemin üzerine üniform bir dağılım daha tanımlamaktır ne kadar kolay bir ölçüsüdür. ${\displaystyle N\sağ ok \infty }$${\görüntüleme stili \log(N)}$

göreli entropi

Ayrık ve sürekli durumda eşit derecede iyi çalışan bir başka yararlı entropi ölçüsü , bir dağılımın göreli entropisidir . Dağılımdan bir referans ölçüsüne m Kullback-Leibler sapması olarak tanımlanır . Bir olasılık dağılımı varsayalım s olan mutlak sürekli bir ölçü ile ilgili m , yani bir şekilde taşımaktadır, p ( dx ) = f ( x ) m ( dx ) bir negatif olmayan için m -integrable fonksiyon f ile m -integral 1, o zaman bağıl entropi olarak tanımlanabilir

${\displaystyle D_{\mathrm {KL} }(p\|m)=\int \log(f(x))p(dx)=\int f(x)\log(f(x))m(dx ).}$

Bu biçimde göreli entropi genelleştiren (Kayıt değişimine) ölçüsü ayrık entropi, her iki m, olan sayma ölçü ve ölçü diferansiyel entropi, m olan Lebesgue ölçümü . m ölçüsünün kendisi bir olasılık dağılımıysa, göreceli entropi negatif değildir ve ölçü olarak p = m ise sıfırdır . Bu bir uygun şekilde dikkate ölçü dönüşümünü alırsa bağımsız ve değişmez altında reparameterizations koordinat dolayısıyla, herhangi bir önlem alanı için tanımlandığı m . Göreceli entropi ve (dolaylı olarak) entropi ve diferansiyel entropi, "referans" ölçüsüne bağlıdır m .

Kombinatoriklerde kullanın

Entropi, kombinatorikte yararlı bir nicelik haline geldi .

Loomis-Whitney eşitsizliği

Bunun basit bir örneği, Loomis-Whitney eşitsizliğinin alternatif bir kanıtıdır : her A ⊆ Z ^d alt kümesi için

${\displaystyle |A|^{d-1}\leq \prod _{i=1}^{d}|P_{i}(A)|}$

burada P _ı olan ortogonal projeksiyonu olarak i koordine inci:

${\displaystyle P_{i}(A)=\{(x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{d}):(x_{1} ,\ldots ,x_{d})\in A\}.}$

Kanıt, Shearer eşitsizliğinin basit bir sonucu olarak gelir : eğer X ₁ , ..., X _d rastgele değişkenlerse ve S ₁ , ..., S _n {1, ..., d }' nin altkümeleri ise , her tamsayı 1 arasında d tam yatmaktadır r sonra, bu alt gruplarının

${\displaystyle \mathrm {H} [(X_{1},\ldots ,X_{d})]\leq {\frac {1}{r}}\sum _{i=1}^{n}\mathrm {H} [(X_{j})_{j\in S_{i}}]}$

burada rastgele değişkenler Kartezyen ürünü olan X- _j endeksleri olan j olarak S _i (bu vektörün boyutu büyüklüğüne eşit şekilde S _i ). ${\displaystyle (X_{j})_{j\in S_{i}}}$

Biz Loomis-Whitney bu nasıl türetildiğini taslağını Gerçekten de, izin X- değerleri ile eşit olarak dağıtılan bir rastgele değişken A ve böylece her bir nokta, A eşit olasılıkla meydana gelir. Sonra (yukarıda bahsedilen entropinin diğer özellikleriyle) Η( X ) = log| bir | , nerede | bir | A'nın kardinalitesini gösterir . Let S _i = {1, 2, ..., I -1, i + 1, ..., d }. Aralığı içerdiği P _i ( A ) ve dolayısıyla . Şimdi bunu Shearer eşitsizliğinin sağ tarafını sınırlamak için kullanın ve elde ettiğiniz eşitsizliğin karşı taraflarını üsleyin. ${\displaystyle (X_{j})_{j\in S_{i}}}$${\displaystyle \mathrm {H} [(X_{j})_{j\in S_{i}}]\leq \log |P_{i}(A)|}$

Binom katsayısına yaklaşım

Tamsayıları için 0 < k < n izin q = k / n . Sonra

${\displaystyle {\frac {2^{n\mathrm {H} (q)}}{n+1}}\leq {\tbinom {n}{k}}\leq 2^{n\mathrm {H} (Q)},}$

nerede

${\displaystyle \mathrm {H} (q)=-q\log _{2}(q)-(1-q)\log _{2}(1-q).}$

Kanıt (kroki)

Not ifadesinin bir terimdir ${\displaystyle {\tbinom {n}{k}}q^{qn}(1-q)^{n-nq}}$ ${\displaystyle \sum _{i=0}^{n}{\tbinom {n}{i}}q^{i}(1-q)^{ni}=(q+(1-q))^{ n}=1.}$ Yeniden düzenleme üst sınırı verir. Alt sınır için, ilk önce, biraz cebir kullanarak, bunun toplamadaki en büyük terim olduğunu gösterir. Ama sonra, ${\displaystyle {\binom {n}{k}}q^{qn}(1-q)^{n-nq}\geq {\frac {1}{n+1}}}$ Toplamda n + 1 terim olduğu için. Yeniden düzenleme alt sınırı verir.

Bunun güzel bir yorumu, tam olarak k birçok 1 olan n uzunluğundaki ikili dizelerin sayısının yaklaşık olarak . ${\displaystyle 2^{n\mathrm {H} (k/n)}}$

Ayrıca bakınız

Referanslar

Bu makale , Creative Commons Atıf/Benzer Paylaşım Lisansı altında lisanslanan Shannon'ın PlanetMath üzerindeki entropisinden materyal içermektedir .

daha fazla okuma

bilgi teorisi üzerine ders kitapları

• Cover, TM , Thomas, JA (2006), Elements of Information Theory - 2. Baskı. , Wiley-Interscience, ISBN  978-0-471-24195-9
• MacKay, DJC (2003), Bilgi Teorisi, Çıkarım ve Öğrenme Algoritmaları , Cambridge University Press, ISBN  978-0-521-64298-9
• Arndt, C. (2004), Bilgi Ölçüleri: Bilim ve Mühendislikte Bilgi ve Tanımı , Springer, ISBN  978-3-540-40855-0
• Gray, RM (2011), Entropi ve Bilgi Teorisi , Springer.
• Martin, Nathaniel FG & İngiltere, James W. (2011). Entropinin Matematiksel Teorisi . Cambridge Üniversitesi Yayınları. ISBN'si 978-0-521-17738-2.CS1 bakımı: yazarlar parametresini kullanır ( link )
• Shannon, CE , Weaver, W. (1949) İletişimin Matematiksel Teorisi , Illinois Üniversitesi Yayınları. ISBN  0-252-72548-4
• Stone, JV (2014), Bilgi Teorisi Bölüm 1 : Bir Öğretici Giriş , Sheffield Üniversitesi, İngiltere. ISBN  978-0956372857 .

Dış bağlantılar

• "Entropi" , Matematik Ansiklopedisi , EMS Press , 2001 [1994]
• "Entropi" de Rosetta Kod Shannon uygulamalarının -repository farklı programlama dillerinde entropi.
• Entropi , entropi kavramının tüm yönleriyle ilgili disiplinler arası bir dergidir. Açık Erişim.