Entropia (teoria informacji)

W przypadku innych zastosowań zobacz Entropia (ujednoznacznienie) .

W teorii informacji entropia zmiennej losowej to średni poziom „informacji”, „niespodzianki” lub „niepewności” związany z możliwymi wynikami zmiennej. Biorąc pod $\ Displaystyle p: {\ X} matematyczny {X}}\do [0,1]}$ dyskretną zmienną losową , która przyjmuje wartości w alfabecie $i$${$ dystrybuowana zgodnie z :

$${\ Displaystyle \ operatorname {H} (X): = - \ suma _ {x\w {\mathcal {X}}}p(x)\log p(x)=\mathbb {E} [-\log p(X)],}$$

gdzie oznacza $.$ możliwych wartości zmiennej Wybór podstawy dla logarytmu $różny$ dla różnych aplikacji. Podstawa 2 daje jednostkę bitów (lub „ shannons ”), podczas gdy podstawa e daje „jednostki naturalne” nat , a podstawa 10 daje jednostki „dits”, „bans” lub „ hartleys ”. Równoważną definicją entropii jest oczekiwana wartość informacji o sobie zmiennej.

Dwa bity entropii: w przypadku dwóch uczciwych rzutów monetą entropia informacyjna w bitach to logarytm o podstawie 2 liczby możliwych wyników; przy dwóch monetach są cztery możliwe wyniki i dwa bity entropii. Ogólnie rzecz biorąc, entropia informacji to średnia ilość informacji przekazywanych przez zdarzenie, biorąc pod uwagę wszystkie możliwe wyniki.

Pojęcie entropii informacyjnej zostało wprowadzone przez Claude'a Shannona w jego artykule z 1948 r. „ Mathematical Theory of Communication ” i jest również określane jako entropia Shannona . Teoria Shannona definiuje transmisji danych składający się z trzech elementów: źródła danych, kanału komunikacyjnego i odbiornika. „Podstawowym problemem komunikacji” – jak to określił Shannon – jest to, aby odbiorca był w stanie zidentyfikować, jakie dane wygenerowało źródło, na podstawie sygnału, który odbiera kanałem. Shannon rozważał różne sposoby kodowania, kompresji i przesyłania wiadomości ze źródła danych i udowodnił w swoim słynnym twierdzeniu o kodowaniu źródłowym , że entropia stanowi absolutną matematyczną granicę tego, jak dobrze dane ze źródła mogą być bezstratnie skompresowane na idealnie bezszumowym kanale. Shannon znacznie wzmocnił ten wynik dla hałaśliwych kanałów w swoim twierdzeniu o kodowaniu hałaśliwych kanałów .

Entropia w teorii informacji jest bezpośrednio analogiczna do entropii w termodynamice statystycznej . Analogia pojawia się, gdy wartości zmiennej losowej wyznaczają energie mikrostanów, więc wzór Gibbsa na entropię jest formalnie identyczny ze wzorem Shannona. Entropia ma znaczenie dla innych dziedzin matematyki, takich jak kombinatoryka i uczenie maszynowe . Definicję można wyprowadzić z zestawu aksjomatów stanowiących, że entropia powinna być miarą tego, jak informacyjny jest średni wynik zmiennej. W przypadku ciągłej zmiennej losowej entropia różniczkowa jest analogiczna do entropii.

Wstęp

Podstawową ideą teorii informacji jest to, że „wartość informacyjna” przekazywanego komunikatu zależy od stopnia zaskoczenia treści komunikatu. Jeśli wystąpi wysoce prawdopodobne zdarzenie, wiadomość zawiera bardzo mało informacji. Z drugiej strony, jeśli wystąpi wysoce nieprawdopodobne zdarzenie, wiadomość zawiera znacznie więcej informacji. Na przykład wiedza, że ​​jakaś konkretna liczba nie będzie zwycięską liczbą na loterii, dostarcza bardzo mało informacji, ponieważ żadna konkretna wybrana liczba prawie na pewno nie wygra. Jednak wiedza o tym, że dana liczba wygra na loterii, ma dużą wartość informacyjną, ponieważ komunikuje wynik zdarzenia o bardzo niskim prawdopodobieństwie.

Treść informacyjna , $prawdopodobieństwa$ także zaskoczeniem lub samoinformacją, zdarzenia funkcją, która rośnie $wraz$ . Kiedy $}$ , zaskoczenie wydarzeniem jest niskie, ale jeśli jest bliskie 0, zaskoczenie wydarzeniem jest $Displaystyle p ($ jest wysoko. Zależność ta jest opisana przez funkcję

$${\ Displaystyle \ log \ lewo ({\ Frac {1} {p (E)}} \ prawej),}$$

gdzie ${\ displaystyle \ log}$ jest logarytmem , co daje niespodziankę 0, gdy prawdopodobieństwo zdarzenia wynosi 1. W rzeczywistości log $\ displaystyle \ log}$ jest jedyną funkcją, która spełnia ten konkretny zestaw charakterystyk .

W związku $według$ tym możemy zdefiniować informację lub zaskoczenie zdarzenia

$${\ Displaystyle I (E) = - \ log _ {2} (p (E))}$$

lub równoważnie,

$${\ Displaystyle I (E) = \ log _ {2} \ lewo ({\ Frac {1} {p (E)}} \ prawo).}$$

Entropia mierzy oczekiwaną (tj. średnią) ilość przekazywanych informacji, identyfikując wynik próby losowej. Oznacza to, że rzut kostką $każdy$ ponieważ każdy wynik rzutu kostką ma mniejsze prawdopodobieństwo (około ) wynik rzutu monetą ( ${\ displaystyle p = 1/2}$ ).

Rozważmy tendencyjną monetę z prawdopodobieństwem p wypadnięcia reszki i prawdopodobieństwem 1 − p wypadnięcia reszki. Maksymalną niespodzianką jest sytuacja, gdy p = 1/2 , dla której nie oczekuje się jednego wyniku w stosunku do drugiego. W tym przypadku rzut monetą ma entropię jednego bitu . (Podobnie, jeden trit z równoprawnymi wartościami zawiera ${\ displaystyle \ log _ {2} 3}$ (około 1,58496) bitów informacji, ponieważ może mieć jedną z trzech wartości.) Minimalnym zaskoczeniem jest p = 0 lub p = 1 , gdy wynik zdarzenia jest znany z wyprzedzeniem, a entropia wynosi zero bitów. Kiedy entropia wynosi zero bitów, jest to czasami określane jako jedność, gdzie nie ma żadnej niepewności - nie ma wolności wyboru - nie ma informacji . Inne wartości p dają entropie od zera do jednego bitu.

Teoria informacji jest przydatna do obliczenia najmniejszej ilości informacji wymaganej do przekazania wiadomości, jak w przypadku kompresji danych . Rozważmy na przykład transmisję sekwencji zawierających 4 znaki „A”, „B”, „C” i „D” przez kanał binarny. Jeśli wszystkie 4 litery są równie prawdopodobne (25%), nie można zrobić nic lepszego niż użycie dwóch bitów do zakodowania każdej litery. „A” może kodować jako „00”, „B” jako „01”, „C” jako „10”, a „D” jako „11”. Jeśli jednak prawdopodobieństwo każdej litery jest nierówne, powiedzmy, że „A” występuje z 70% prawdopodobieństwem, „B” z 26%, a „C” i „D” z 2% każda, można przypisać kody o zmiennej długości. W tym przypadku „A” byłoby zakodowane jako „0”, „B” jako „10”, „C” jako „110”, a D jako „111”. Przy tej reprezentacji w 70% przypadków wystarczy wysłać tylko jeden bit, w 26% przypadków dwa bity, a tylko w 4% przypadków 3 bity. Średnio potrzeba mniej niż 2 bity, ponieważ entropia jest niższa (ze względu na dużą częstość występowania „A”, po którym następuje „B” – razem 96% znaków). Obliczenie sumy prawdopodobieństw logarytmicznych ważonych prawdopodobieństwem mierzy i uwzględnia ten efekt. Tekst angielski, traktowany jako ciąg znaków, ma dość niską entropię, czyli jest dość przewidywalny. Możemy być całkiem pewni, że na przykład „e” będzie znacznie bardziej powszechne niż „z”, że kombinacja „qu” będzie znacznie bardziej powszechna niż jakakolwiek inna kombinacja zawierająca „q” i że kombinacja „th” będzie bardziej powszechne niż „z”, „q” lub „qu”. Po kilku pierwszych literach często można odgadnąć resztę słowa. Tekst w języku angielskim ma od 0,6 do 1,3 bitów entropii na znak wiadomości.

Definicja

Nazwany na cześć twierdzenia Η Boltzmanna , Shannon zdefiniował entropię Η (grecka wielka litera eta ) dyskretnej zmiennej losowej , która przyjmuje wartości w alfabecie i jest $textstyle X}$$}$ p ${\ Displaystyle p: {\ mathcal {X}} \ do [0,1]}$ , że ${\ Displaystyle p ( x):=\mathbb {P} [X=x]}$ :

$${\ Displaystyle \ operatorname {H} (X) = \ mathbb {E} [\ nazwa operatora {I} (X)] = \ mathbb {E} [- \ log p (X)].}$$

Tutaj $jest$ operatorem wartości oczekiwanej , a I treścią informacyjną X . ${\ Displaystyle \ operatorname {I} (X)}$ sam w sobie jest zmienną losową.

Entropię można wyraźnie zapisać jako:

$${\ Displaystyle \ operatorname {H} (X) = - \ suma _ {x \ w {\ mathcal {X}}} p(x)\log _{b}p(x),}$$

gdzie b jest podstawą użytego logarytmu . Typowymi wartościami b są 2, liczba Eulera e i 10, a odpowiednimi jednostkami entropii są bity dla b = 2 , nats dla b = e i bany dla b = 10 .

W przypadku $p (x) = 0}$$Displaystyle$ dla pewnego wartość odpowiedniej sumy 0 log_b(0) is taken to be 0, which is consistent with the limit:

$${\ Displaystyle \ lim _ {p \ do 0 ^ {+}} p \ log (p) = 0.}$$

Można również zdefiniować entropię warunkową dwóch zmiennych i ${$$\ displaystyle Y},$ przyjmując wartości ze zbiorów $X}}}$ i ${\ displaystyle {\ mathcal {Y} }}$ odpowiednio, jako:

$${\ Displaystyle \ operatorname {H} (X|Y)=-\suma _{x,y\in {\mathcal {X}}\razy {\mathcal {Y}}}p_{X,Y}(x,y)\log {\frac { p_{X,Y}(x,y)}{p_{Y}(y)}},}$$

gdzie ${\ Displaystyle p_ {X, Y} (x, y): = \ mathbb {P} [X = x, Y = y]}$ i ${\ Displaystyle p_ {Y} (y) = \ mathbb {P} [Y = y]}$ . Tę wielkość należy ${\ displaystyle Y$ jako pozostałą losowość w zmiennej losowej, biorąc pod uwagę zmienną losową $}$ .

Teoria miary

$formalnie$ w języku teorii miary w następujący sposób przestrzenią prawdopodobieństwa Niech będzie zdarzeniem ${\ Displaystyle A \ in \ Sigma}$ . Niespodzianką jest ZA { $displaystyle A}$

$${\ Displaystyle \ sigma _ {\ mu} (A) = - \ ln \ mu (A).}$$

Oczekiwaną niespodzianką jest ZA $\ displaystyle A}$

$${\ Displaystyle h _ {\ mu} (A) = \ mu (A) \ sigma _ {\ mu} (A).}$$

ZA ${\ Displaystyle \ mu}$ -prawie partycja jest zbiorem rodziny ${\ Displaystyle P \ subseteq {\ mathcal {P}} (X)}$ taka, że ${\ displaystyle \ mu (\ mathop {\ kubek} P) = 1}$ i ${\ Displaystyle \ mu (A \ czapka B) = 0}$ dla wszystkich różnych ${\ Displaystyle A, B\w P}$ . (Jest to złagodzenie zwykłych warunków podziału). Entropia wynosi P $\ displaystyle P}$

$${\ Displaystyle \ operatorname {H} _ {\ mu} (P) = \ suma _ {A \ in P} h _ {\ mu} (A).}$$

Niech będzie algebrą sigma na $X}$$displaystyle$ . Entropia wynosi M $\ displaystyle M}$

$${\ Displaystyle \ operatorname {H} _ {\ mu} (M) = \ sup _ {P \ subseteq M} \ operatorname {H} _ {\ mu} (P).}$$

Wreszcie, entropia przestrzeni prawdopodobieństwa to entropia w odniesieniu do μ $\ displaystyle \ mu}$$mu}$ sigma-algebra wszystkich mierzalnych podzbiorów ${\ displaystyle X}$ .

Definicja Ellermana

David Ellerman chciał wyjaśnić, dlaczego entropia warunkowa i inne funkcje mają właściwości podobne do funkcji z teorii prawdopodobieństwa. Twierdzi, że poprzednie definicje oparte na teorii miary działały tylko z potęgami 2.

Ellerman stworzył „logikę partycji”, czyli dualność podzbiorów uniwersalnego zbioru. Informacje są określane ilościowo jako „dits” (wyróżnienia), miary dotyczące partycji. „Dits” można przekształcić w bity Shannona , aby uzyskać wzory na entropię warunkową itp.

Przykład

Entropia Η( X ) (tj. oczekiwana niespodzianka ) rzutu monetą, mierzona w bitach, przedstawiona na wykresie w funkcji odchylenia monety Pr( X = 1) , gdzie X = 1 reprezentuje wynik orła. Tutaj entropia wynosi co najwyżej 1 bit, a przekazanie wyniku rzutu monetą (2 możliwe wartości) będzie wymagało średnio co najwyżej 1 bita (dokładnie 1 bit na uczciwą monetę). Wynik uczciwego rzutu kostką (6 możliwych wartości) miałby log entropii ₂ 6 bitów.

Główne artykuły: binarna funkcja entropii i proces Bernoulliego

Rozważ rzut monetą ze znanym, niekoniecznie uczciwym, prawdopodobieństwem wypadnięcia orła lub reszki; można to modelować jako proces Bernoulliego .

Entropia nieznanego wyniku następnego rzutu monetą jest maksymalizowana, jeśli moneta jest uczciwa (to znaczy, jeśli reszka i orzeł mają równe prawdopodobieństwo 1/2). Jest to sytuacja maksymalnej niepewności, ponieważ najtrudniej jest przewidzieć wynik następnego rzutu; wynik każdego rzutu monetą dostarcza jednego pełnego bitu informacji. To dlatego, że

$${\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {H} (X) & = - \ suma _ {i = 1} ^ {n} {p (x_ {i}) \ log _ {b} p(x_{i})}\\&=-\suma _{i=1}^{2}{{\frac {1}{2}}\log _{2}{\frac {1}{2 }}}\\&=-\sum _{i=1}^{2}{{\frac {1}{2}}\cdot (-1)}=1\end{wyrównane}}}$$

Jeśli jednak wiemy, że moneta nie jest uczciwa, ale wypadnie orzeł lub reszka z prawdopodobieństwem p i q , gdzie p ≠ q , wtedy jest mniejsza niepewność. Za każdym razem, gdy jest rzucany, jedna strona jest bardziej prawdopodobna niż druga. Zmniejszona niepewność jest kwantyfikowana w niższej entropii: średnio każdy rzut monetą dostarcza mniej niż jeden pełny bit informacji. Na przykład, jeśli p = 0,7, to

$${\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {H} (X) i = - p \ log _ {2} (p) -q \ log _ {2} (q) \\ &=-0,7\log _{2}(0,7)-0,3\log _{2}(0,3)\\&\około -0,7\cdot (-0,515)-0,3\cdot (-1,737)\\&=0,8816 <1\end{wyrównane}}}$$

Jednolite prawdopodobieństwo daje maksymalną niepewność, a zatem maksymalną entropię. Entropia może zatem zmniejszać się tylko od wartości związanej z jednolitym prawdopodobieństwem. Skrajnym przypadkiem jest moneta z dwoma reszkami, która nigdy nie wypada reszką, lub moneta z podwójnymi reszkami, która nigdy nie kończy się reszką. Wtedy nie ma niepewności. Entropia wynosi zero: każdy rzut monetą nie dostarcza żadnych nowych informacji, ponieważ wynik każdego rzutu jest zawsze pewny.

Entropię można znormalizować, dzieląc ją przez długość informacji. Stosunek ten nazywany jest entropią metryczną i jest miarą losowości informacji.

Charakteryzacja

Aby zrozumieć znaczenie −Σ p _i log( pi ₎ prawdopodobieństwem , najpierw zdefiniuj funkcję informacyjną I w kategoriach zdarzenia i z p _i . Ilość informacji uzyskanych dzięki obserwacji zdarzenia i wynika z rozwiązania Shannona podstawowych własności informacji :

1. I( p ) maleje monotonicznie w p : wzrost prawdopodobieństwa zdarzenia zmniejsza informację z obserwowanego zdarzenia i odwrotnie.
2. I(1) = 0 : zdarzenia, które zawsze występują, nie przekazują informacji.
3. I( p ₁ · p ₂ ) = I( p ₁ ) + I ( p ₂ ) : informacja uzyskana z niezależnych zdarzeń jest sumą informacji uzyskanych z każdego zdarzenia.

Biorąc pod uwagę dwa niezależne zdarzenia, jeśli pierwsze zdarzenie może przynieść jeden z n równie prawdopodobnych wyników, a drugie ma jeden z m równie prawdopodobnych wyników, to istnieje mn równie prawdopodobnych wyników wspólnego zdarzenia. Oznacza to, że jeśli log ₂ ( n ) bitów jest potrzebnych do zakodowania pierwszej wartości i log ₂ ( m ) do zakodowania drugiej, potrzeba log ₂ ( mn ) = log ₂ ( m ) + log ₂ ( n ) do zakodowania obu .

Shannon odkrył, że odpowiedni wybór daje: ${\ displaystyle \ operatorname {I}}$

$${\ Displaystyle \ nazwa operatora {I} (p) = \ log \ lewo ({\ tfrac {1} {p}} \ prawej) = -\log(p)}$$

W rzeczywistości jedynymi możliwymi wartościami są $\$$operatorname {I} (u) = k \ log u}$${ \ Displaystyle$ dla $\displaystyle k<0}$ . Dodatkowo ${\ Displaystyle k = -1/\ log x}$ wartości dla k równoznaczne z wybraniem wartości dla $x$ że x odpowiada podstawa logarytmu . Zatem entropia charakteryzuje się powyższymi czterema właściwościami.

Dowód

Niech $textstyle \operatorname {I}}$ będzie funkcją informacyjną, co do której zakłada się, że jest dwukrotnie różniczkowalna w sposób ciągły, ma się: ${\ Displaystyle {\ rozpocząć { wyrównane}&\nazwa_operatora {I} (p_{1}p_{2})&=\ &\nazwa_operatora {I} (p_{1})+\nazwa_operatora {I} (p_{2})&&\quad {\ text{Zaczynając od właściwości 3}}\\&p_{2}\nazwa_operatora {I} '(p_{1}p_{2})&=\ &\nazwa_operatora {I} '(p_{1})&&\quad { \text{biorąc pochodną wrt}}\ p_{1}\\&\operatorname {I} '(p_{1}p_{2})+p_{1}p_{2}\operatorname {I} ''( p_{1}p_{2})&=\ &0&&\quad {\text{biorąc pochodną wrt}}\ p_{2}\\&\operatorname {I} '(u)+u\operatorname {I} ' '(u)&=\ &0&&\quad {\text{wprowadzenie}}\,u=p_{1}p_{2}\\&(u\mapsto u\nazwa operatora {I} '(u))'&= \ &0\end{wyrównane}}}$ To $_$ różniczkowe $_ c\in \mathbb {R}}$ rozwiązania pewnego . Właściwość 2 daje ${\ displaystyle c = 0}$ . Właściwość 1 i 2 dają to $p\in [0,1]$ wszystkich ja $\ Displaystyle \ operatorname {I} (p) \$$k<0$.

Różne jednostki informacji ( bity dla logarytmu binarnego log ₂ , nat dla logarytmu naturalnego ln , bany dla logarytmu dziesiętnego log ₁₀ i tak dalej) są stałymi wielokrotnościami siebie. Na przykład, w przypadku uczciwego rzutu monetą, orzeł zapewnia log ₂ (2) = 1 bit informacji, co odpowiada w przybliżeniu 0,693 natów lub 0,301 cyfr dziesiętnych. Ze względu na addytywność n rzutów dostarcza n bitów informacji, co odpowiada w przybliżeniu 0,693 n nat lub 0,301 n cyfr dziesiętnych.

Znaczenie obserwowanych zdarzeń (znaczenie komunikatów ) nie ma znaczenia w definicji entropii. Entropia bierze pod uwagę tylko prawdopodobieństwo zaobserwowania określonego zdarzenia, więc informacje, które zawiera, to informacje o leżącym u podstaw rozkładzie prawdopodobieństwa , a nie o znaczeniu samych zdarzeń.

Alternatywna charakterystyka

Inna charakterystyka entropii wykorzystuje następujące właściwości. Oznaczamy p _ja = Pr( X = x _ja ) i Η _n ( p ₁ , ..., p _n ) = Η ( X ) .

1. Ciągłość: H powinno być ciągłe , więc zmiana wartości prawdopodobieństw o ​​bardzo małą wartość powinna zmienić entropię tylko o niewielką wartość.
2. Symetria: H powinno pozostać niezmienione, jeśli wyniki x _i zostaną ponownie uporządkowane. H. $\ Displaystyle \ operatorname {H} _ {n} \ lewo (p_ {1},p_{2},\ldots p_{n}\right)=\mathrm {H} _{n}\left(p_{i_{1}},p_{i_{2}},\ldots , p_{i_{n}}\right)}$ dla dowolnej permutacji $..., i_ {n} \}}$ z $..., n \}}$ .
3. Maksimum: ${\ Displaystyle \ operatorname {H} _ {n} (p_ {1}, \ ldots, p_ {n}) \ równoważnik \ operatorname {H} _ {n} \ lewo ({\ Frac {1} {n} },\ldots ,{\frac {1}{n}}\right)}$$}$ wyniki są jednakowo .
4. Rosnąca liczba wyników: dla zdarzeń równo prawdopodobnych entropia powinna rosnąć wraz z liczbą wyników, tj. ${\ Displaystyle \ operatorname {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. Addytywność: biorąc pod uwagę zespół n równomiernie rozłożonych elementów, które są podzielone na k pudeł (podsystemów) z b ₁ , ..., b _k elementów w każdym, entropia całego zespołu powinna być równa sumie entropii system pudełek i indywidualne entropie pudełek, z których każda ważona jest prawdopodobieństwem znalezienia się w tym konkretnym pudełku.

Reguła addytywności ma następujące konsekwencje: dla dodatnich liczb całkowitych b _i gdzie b ₁ + ... + b _k = n ,

${\ Displaystyle \ operatorname {H} _ {n} \ lewo ({\ Frac {1} {n}}, \ ldots, {\ Frac {1} {n}} \ prawej) = \ operatorname {H} _ { k}\left({\frac {b_{1}}{n}},\ldots,{\frac {b_{k}}{n}}\right)+\suma _{i=1}^{k }{\frac {b_{i}}{n}}\,\mathrm {H} _{b_{i}}\left({\frac {1}{b_{i}}},\ldots,{\ ułamek {1}{b_{i}}}\prawo).}$

Wybierając k = n , b ₁ = ... = b _n = 1 oznacza to, że entropia pewnego wyniku wynosi zero: Η ₁ (1) = 0 . Oznacza to, że wydajność alfabetu źródłowego z n symbolami można po prostu zdefiniować jako równą jego n -arnej entropii. Zobacz także Nadmiarowość (teoria informacji) .

Charakteryzacja alternatywna poprzez addytywność i subaddytywność

Inna zwięzła aksjomatyczna charakterystyka entropii Shannona została podana przez Aczéla , Forte i Ng, poprzez następujące właściwości:

1. Subaddytywność: ${\ Displaystyle \ operatorname {H} (X, Y) \ równoważnik \ operatorname {H} (X) + \ operatorname {H} (Y) }$ dla wspólnie rozłożonych zmiennych losowych ${\ Displaystyle X, Y}$ .
2. addytywność: ${\ Displaystyle \ operatorname {H} (X, Y) = \ operatorname {H} (X) + \ operatorname {H} (Y)}$$gdy$ zmienne .
3. Rozszerzalność: ${\ Displaystyle \ operatorname {H} _ {n + 1} (p_ {1}, \ ldots ,p_{n},0)=\mathrm {H} _{n}(p_{1},\ldots ,p_{n})} , tj. dodanie$ wyniku z prawdopodobieństwem zerowym nie zmienia entropii.
4. Symetria: ${\ Displaystyle \ operatorname {H} _ {n} (p_ {1}, \ ldots, p_ {n})}$ jest niezmiennikiem przy permutacji ${\ displaystyle p_ {1}, \ ldots, p_ {n}}$ .
5. Małe dla małych prawdopodobieństw: ${\ Displaystyle \ lim _ {q \ do 0 ^ {+}} \ operatorname {H} _ {2} (1-q, q )=0}$ .

Wykazano, że każda funkcja $właściwości$ musi być stałą wielokrotnością entropii Shannona, z nieujemną stałą. W porównaniu do wcześniej wspomnianych charakterystyk entropii, ta charakterystyka skupia się raczej na właściwościach entropii jako funkcji zmiennych losowych (subaddytywność i addytywność), niż na właściwościach entropii jako funkcji wektora prawdopodobieństwa ${ \displaystyle p_{1}, \ldots, p_{n}}$ .

$,$ że jeśli odrzucimy właściwość „małe dla małych prawdopodobieństw”, to to być nieujemna liniowa kombinacja entropii Shannona i entropii Hartleya .

Dalsze właściwości

Entropia Shannona spełnia następujące właściwości, z których niektóre warto interpretować entropię jako oczekiwaną ilość uzyskanych informacji (lub wyeliminowaną niepewność) poprzez ujawnienie wartości zmiennej losowej X :

• Dodanie lub usunięcie zdarzenia z prawdopodobieństwem zerowym nie ma wpływu na entropię:

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

• Można potwierdzić za pomocą nierówności Jensena , a następnie nierówności Sedrakyana , że

${\ styl wyświetlania \mathrm {H} (X)=\mathbb {E} [-\log _{b}p(X)]\leq -\log _{b}\left(\mathbb {E} [p(X) ]\right)\leq \log _{b}n}$ .

Ta maksymalna entropia log _b ( n ) jest skutecznie osiągana przez alfabet źródłowy o jednolitym rozkładzie prawdopodobieństwa: niepewność jest maksymalna, gdy wszystkie możliwe zdarzenia są jednakowo prawdopodobne.

• Entropia lub ilość informacji ujawniona przez oszacowanie ( X , Y ) (czyli jednoczesne oszacowanie X i Y ) jest równa informacji ujawnionej przez przeprowadzenie dwóch następujących po sobie eksperymentów: najpierw oszacowanie wartości Y , a następnie ujawnienie wartości X pod warunkiem, że znasz wartość Y . Można to zapisać jako:

${\ Displaystyle \ operatorname {H} (X, Y) = \ operatorname {H} (X | Y) + \ operatorname {H} (Y) = \ operatorname {H} (Y | X) + \ operatorname {H} (X).}$

• daje Jeśli ${\ Displaystyle Y = f (X)}$ gdzie ${\ Displaystyle f}$ jest funkcją, to ${\ Displaystyle \ operatorname { H} (f(X)|X)=0}$ . $fa$ poprzedniego

$\ Displaystyle \ operatorname {H} (X) + \ operatorname {H} (f (X) | X) = \ operatorname {H} (f (X) }) + \ operatorname {H} (X | f (X)),}$

więc ${\ Displaystyle \ operatorname {H} (f (X)) \ równoważnik \ operatorname { H} (X)}$ , entropia zmiennej może się zmniejszyć tylko wtedy, gdy ta ostatnia przechodzi przez funkcję.

• Jeśli X i Y są dwiema niezależnymi zmiennymi losowymi, to znajomość wartości Y nie wpływa na naszą wiedzę o wartości X (ponieważ obie nie wpływają na siebie nawzajem przez niezależność):

${\ Displaystyle \ operatorname {H} (X|Y) = \ operatorname {H} (X).}$

• Bardziej ogólnie, dla dowolnych zmiennych losowych X i Y mamy

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

• Entropia dwóch jednoczesnych zdarzeń jest nie większa niż suma entropii każdego pojedynczego zdarzenia, tj. ${\ Displaystyle \ operatorname {H} (X, Y) \leq \mathrm {H} (X)+\mathrm {H} (Y)}$ , z równością wtedy i tylko wtedy, gdy dwa zdarzenia są niezależne.
• Entropia jest wklęsła w funkcji masy prawdopodobieństwa $Displaystyle \ operatorname {$ tj. $H. ( p ) {$

${\ Displaystyle \ operatorname {H} (\ lambda p_ {1} + (1 -\lambda )p_{2})\geq \lambda \mathrm {H} (p_{1})+(1-\lambda )\mathrm {H} (p_{2})} dla wszystkich prawdopodobieństwa funkcji$

masy ${\ Displaystyle p_ {1}, p_ {2}}$ i $lambda \ równoważnik 1}$ \

• W związku z tym funkcja entropii ujemnej (negentropii) jest wypukła, a jej koniugat wypukły to LogSumExp .

Aspekty

Związek z entropią termodynamiczną

Główny artykuł: Entropia w termodynamice i teorii informacji

Inspiracją do przyjęcia słowa entropia w teorii informacji było bliskie podobieństwo wzoru Shannona do bardzo podobnych wzorów znanych z mechaniki statystycznej .

W termodynamice statystycznej najbardziej ogólnym wzorem na entropię termodynamiczną S układu termodynamicznego jest entropia Gibbsa ,

${\ Displaystyle S = - k _ {\ tekst {B}} \ suma p_ {i} \ ln p_ {i} \,}$

gdzie k _B jest stałą Boltzmanna , a _pi jest prawdopodobieństwem mikrostanu . Entropia Gibbsa została zdefiniowana przez J. Willarda Gibbsa w 1878 r. Po wcześniejszej pracy Boltzmanna (1872).

Entropia Gibbsa przekłada się prawie niezmieniona na świat fizyki kwantowej, dając entropię von Neumanna , wprowadzoną przez Johna von Neumanna w 1927 r.,

${\ Displaystyle S = - k _ {\ tekst {B}} \ {\ rm {Tr}} (\ rho \ ln \ rho) \,}$

gdzie ρ jest macierzą gęstości układu mechaniki kwantowej, a Tr jest śladem .

Na codziennym poziomie praktycznym powiązania między entropią informacyjną a entropią termodynamiczną nie są oczywiste. Fizycy i chemicy są bardziej zainteresowani zmianami entropii, gdy układ spontanicznie ewoluuje od swoich warunków początkowych, zgodnie z drugą zasadą termodynamiki , niż niezmiennym rozkładem prawdopodobieństwa. Jak wskazuje drobiazgowość stałej Boltzmanna k _B , zmiany S / k _B dla nawet niewielkich ilości substancji w procesach chemicznych i fizycznych reprezentują wielkości entropii, które są niezwykle duże w porównaniu z czymkolwiek w kompresji danych lub przetwarzaniu sygnałów . W klasycznej termodynamice entropia jest definiowana w kategoriach pomiarów makroskopowych i nie odnosi się do żadnego rozkładu prawdopodobieństwa, który ma kluczowe znaczenie dla definicji entropii informacyjnej.

Związek między termodynamiką a tym, co jest obecnie znane jako teoria informacji, został po raz pierwszy dokonany przez Ludwiga Boltzmanna i wyrażony jego słynnym równaniem :

${\ Displaystyle S = k _ {\ tekst {B}} \ ln W}$

gdzie jest entropią termodynamiczną określonego makrostanu (określoną przez parametry termodynamiczne, takie jak temperatura, objętość, energia itp.), $W$ liczbą mikrostanów (różne kombinacje cząstek w różnych stanach energetycznych), które mogą dają dany makrostan, a k _B jest stałą Boltzmanna . Zakłada się, że każdy mikrostan jest jednakowo prawdopodobny, tak że prawdopodobieństwo danego mikrostanu wynosi p _i = 1/ W . Gdy te prawdopodobieństwa podstawimy do powyższego wyrażenia na entropię Gibbsa (lub równoważnie k _B razy entropia Shannona), otrzymamy równanie Boltzmanna. W kategoriach teorii informacji entropia informacyjna systemu to ilość „brakujących” informacji potrzebnych do określenia mikrostanu przy danym makrostanie.

Zdaniem Jaynesa (1957), entropię termodynamiczną, wyjaśnioną przez mechanikę statystyczną , należy postrzegać jako zastosowanie teorii informacji Shannona: entropię termodynamiczną interpretuje się jako proporcjonalną do ilości dalszych informacji Shannona potrzebnych do zdefiniowania szczegółowej mikroskopowej stan układu, którego nie komunikuje opis wyłącznie w kategoriach makroskopowych zmiennych klasycznej termodynamiki, przy czym stała proporcjonalności jest po prostu stałą Boltzmanna . Dodanie ciepła do układu zwiększa jego entropię termodynamiczną, ponieważ zwiększa liczbę możliwych stanów mikroskopowych układu, które są zgodne z mierzalnymi wartościami jego zmiennych makroskopowych, wydłużając każdy pełny opis stanu. (Patrz artykuł: termodynamika maksymalnej entropii ). Demon Maxwella może (hipotetycznie) zmniejszyć entropię termodynamiczną układu, wykorzystując informacje o stanach poszczególnych cząsteczek; ale, jak Landauer (z 1961 r.) i współpracownicy, aby sam demon mógł funkcjonować, musi zwiększyć entropię termodynamiczną w procesie przynajmniej o ilość informacji Shannona, które zamierza najpierw zdobyć i przechować; więc całkowita entropia termodynamiczna nie maleje (co rozwiązuje paradoks). Zasada Landauera nakłada dolną granicę na ilość ciepła, jaką komputer musi wytworzyć, aby przetworzyć określoną ilość informacji, chociaż nowoczesne komputery są znacznie mniej wydajne.

Kompresja danych

Główne artykuły: twierdzenie Shannona o kodowaniu źródłowym i kompresja danych

Definicja entropii Shannona zastosowana do źródła informacji może określić minimalną przepustowość kanału wymaganą do niezawodnego przesyłania źródła jako zakodowanych cyfr binarnych. Entropia Shannona mierzy informacje zawarte w wiadomości w przeciwieństwie do części wiadomości, która jest określona (lub przewidywalna). Przykładami tych ostatnich są redundancja w strukturze języka lub właściwości statystyczne dotyczące częstości występowania par liter lub słów, trójek itp. Minimalną przepustowość kanału można zrealizować w teorii za pomocą typowego zestawu lub w praktyce za pomocą Huffmana , Lempla - Ziva lub kodowanie arytmetyczne . (Zobacz także złożoność Kołmogorowa ). W praktyce algorytmy kompresji celowo zawierają pewną rozsądną redundancję w postaci sum kontrolnych w celu ochrony przed błędami. Współczynnik entropii źródła danych to średnia liczba bitów na symbol potrzebna do jego zakodowania. Eksperymenty Shannona z ludzkimi predyktorami pokazują szybkość informacji między 0,6 a 1,3 bitów na znak w języku angielskim; algorytm kompresji PPM może osiągnąć stopień kompresji 1,5 bita na znak w tekście angielskim.

Jeśli schemat kompresji jest bezstratny — taki, w którym zawsze można odzyskać całą oryginalną wiadomość przez dekompresję — to skompresowana wiadomość zawiera taką samą ilość informacji jak oryginał, ale jest przekazywana mniejszą liczbą znaków. Ma więcej informacji (wyższa entropia) na postać. Skompresowana wiadomość ma mniejszą redundancję . Twierdzenie Shannona o kodowaniu źródłowym stwierdza, że ​​bezstratny schemat kompresji nie może skompresować wiadomości średnio tak, aby zawierały więcej niż jeden bit informacji na bit wiadomości, ale dowolna wartość mniejsza niż jeden bit informacji na bit wiadomości może zostać osiągnięta przez zastosowanie odpowiedniego schemat kodowania. Entropia wiadomości na bit pomnożona przez długość tej wiadomości jest miarą całkowitej ilości informacji zawartych w wiadomości. Twierdzenie Shannona sugeruje również, że żaden schemat bezstratnej kompresji nie może skrócić wszystkich wiadomości. Jeśli niektóre wiadomości wychodzą krócej, przynajmniej jedna musi wyjść dłużej ze względu na zasadę przegródki . W praktyce nie stanowi to na ogół problemu, ponieważ zwykle interesuje nas kompresja tylko niektórych rodzajów wiadomości, takich jak dokument w języku angielskim, w przeciwieństwie do bełkotliwego tekstu lub fotografii cyfrowych, a nie szumu, i nie ma znaczenia, czy algorytm kompresji powoduje, że niektóre nieprawdopodobne lub nieciekawe sekwencje stają się większe.

Badanie z 2011 roku w Science szacuje światową zdolność technologiczną do przechowywania i przekazywania optymalnie skompresowanych informacji, znormalizowanych na podstawie najskuteczniejszych algorytmów kompresji dostępnych w roku 2007, szacując w ten sposób entropię technologicznie dostępnych źródeł.

Wszystkie liczby w entropicznie skompresowanych eksabajtach

Rodzaj informacji	1986	2007
Składowanie	2.6	295
Audycja	432	1900
Telekomunikacja	0,281	65

Autorzy szacują możliwości technologiczne ludzkości do przechowywania informacji (w pełni skompresowanej entropicznie) w 1986 i ponownie w 2007. Dzielą informacje na trzy kategorie — przechowywanie informacji na nośniku, otrzymywanie informacji za pośrednictwem jednokierunkowych sieci rozgłoszeniowych lub wymiana informacji przez dwukierunkowe sieci telekomunikacyjne .

Entropia jako miara różnorodności

Główny artykuł: Indeks różnorodności

Entropia jest jednym z kilku sposobów pomiaru różnorodności biologicznej i jest stosowana w postaci wskaźnika Shannona . Indeks różnorodności jest ilościową miarą statystyczną tego, ile różnych typów istnieje w zbiorze danych, takich jak gatunki w społeczności, co odpowiada za bogactwo ekologiczne , równość i dominację . W szczególności entropia Shannona jest logarytmem ¹ D , prawdziwego wskaźnika różnorodności z parametrem równym 1. Wskaźnik Shannona jest powiązany z proporcjonalną obfitością typów.

Ograniczenia entropii

Istnieje wiele koncepcji związanych z entropią, które w pewien sposób matematycznie określają zawartość informacji:

• samoinformacja pojedynczego komunikatu lub symbolu zaczerpnięta z danego rozkładu prawdopodobieństwa ,
• entropia danego rozkładu prawdopodobieństwa wiadomości lub symboli oraz
• szybkość entropii procesu stochastycznego .

(„Szybkość samoinformacji” można również zdefiniować dla określonej sekwencji komunikatów lub symboli generowanych przez dany proces stochastyczny: zawsze będzie ona równa szybkości entropii w przypadku procesu stacjonarnego). Inne ilości informacji są również używane do porównywania lub powiązania różnych źródeł informacji.

Ważne jest, aby nie mylić powyższych pojęć. Często jasne jest tylko z kontekstu, o który z nich chodzi. Na przykład, gdy ktoś mówi, że „entropia” języka angielskiego wynosi około 1 bitu na znak, w rzeczywistości modeluje język angielski jako proces stochastyczny i mówi o współczynniku entropii . Sam Shannon użył tego terminu w ten sposób.

Jeśli używane są bardzo duże bloki, oszacowanie współczynnika entropii na znak może stać się sztucznie zaniżone, ponieważ rozkład prawdopodobieństwa sekwencji nie jest dokładnie znany; to tylko szacunki. Jeśli weźmie się pod uwagę tekst każdej kiedykolwiek opublikowanej książki jako sekwencję, gdzie każdy symbol jest tekstem całej książki, i jeśli jest N opublikowanych książek, a każda książka została opublikowana tylko raz, oszacowanie prawdopodobieństwa każdej książki wynosi 1/ N , a entropia (w bitach) to −log ₂ (1/ N ) = log ₂ ( N ) . Jako praktyczny kod odpowiada to przypisywaniu każdej książce unikalnego identyfikatora i używaniu go zamiast tekstu książki, ilekroć ktoś chce się do niej odnieść. Jest to niezwykle przydatne do mówienia o książkach, ale nie jest tak przydatne do charakteryzowania zawartości informacyjnej pojedynczej książki lub ogólnie języka: nie można zrekonstruować książki na podstawie jej identyfikatora bez znajomości rozkładu prawdopodobieństwa, tj. , pełny tekst wszystkich książek. Kluczową ideą jest to, że należy wziąć pod uwagę złożoność modelu probabilistycznego. Złożoność Kołmogorowa jest teoretycznym uogólnieniem tej idei, które pozwala na rozważenie zawartości informacyjnej sekwencji niezależnej od jakiegokolwiek konkretnego modelu prawdopodobieństwa; bierze pod uwagę najkrótszy program dla uniwersalnego komputera , który wyświetla sekwencję. Kod, który osiąga współczynnik entropii sekwencji dla danego modelu, plus książka kodów (tj. model probabilistyczny), jest jednym z takich programów, ale może nie być najkrótszy.

Ciąg Fibonacciego to 1, 1, 2, 3, 5, 8, 13, .... traktując ciąg jako wiadomość, a każdą liczbę jako symbol, jest prawie tyle symboli, ile jest znaków w wiadomości, dając entropia około log ₂ ( n ) . Pierwsze 128 symboli ciągu Fibonacciego ma entropię około 7 bitów/symbol, ale sekwencję można wyrazić za pomocą wzoru [ F ( n ) = F ( n −1) + F ( n −2) dla n = 3 , 4, 5, ... , F(1) =1 , F(2) = 1 ] i ten wzór ma znacznie niższą entropię i dotyczy dowolnej długości ciągu Fibonacciego.

Ograniczenia entropii w kryptografii

W kryptoanalizie entropia jest często z grubsza używana jako miara nieprzewidywalności klucza kryptograficznego, chociaż jego rzeczywista niepewność jest niemierzalna. Na przykład klucz 128-bitowy, który jest generowany w sposób jednolity i losowy, ma 128 bitów entropii. $.$ wymaga również (średnio) zgadywania Entropii nie udaje się uchwycić liczby wymaganych domysłów, jeśli możliwe klucze nie są wybierane jednolicie. Zamiast tego do pomiaru wysiłku wymaganego do ataku siłowego można zastosować miarę zwaną zgadywaniem .

Inne problemy mogą wynikać z niejednorodnych rozkładów stosowanych w kryptografii. Na przykład jednorazowy pad binarny o długości 1 000 000 cyfr przy użyciu wyłączności lub. Jeśli podkładka ma 1 000 000 bitów entropii, jest idealna. Jeśli podkładka ma 999 999 bitów entropii, równomiernie rozłożonych (każdy pojedynczy bit płytki ma 0,999999 bitów entropii), może zapewnić dobre bezpieczeństwo. Ale jeśli pad ma 999 999 bitów entropii, gdzie pierwszy bit jest ustalony, a pozostałe 999 999 bitów jest całkowicie losowych, pierwszy bit tekstu zaszyfrowanego w ogóle nie zostanie zaszyfrowany.

Dane jako proces Markowa

Powszechny sposób definiowania entropii dla tekstu opiera się na modelu tekstu Markowa . Dla źródła rzędu 0 (każdy znak jest wybierany niezależnie od ostatnich znaków) entropia binarna wynosi:

${\ Displaystyle \ operatorname {H} ({\ mathcal {S}}) = - \ suma p_ {i} \ log p_ {i},}$

gdzie p _i jest prawdopodobieństwem i . Dla źródła Markowa pierwszego rzędu (takiego, w którym prawdopodobieństwo wyboru znaku zależy tylko od znaku bezpośrednio poprzedzającego) współczynnik entropii wynosi:

${\ Displaystyle \ operatorname {H} ({\ mathcal {S}}) = - \ suma _ {i} p_{i}\sum _{j}\ p_{i}(j)\log p_{i}(j),} [$

gdzie i jest stanem $.$ pewne poprzedzające znaki), prawdopodobieństwem j podanego jako znaku

Dla źródła Markowa drugiego rzędu współczynnik entropii wynosi

${\ Displaystyle \ operatorname {H} ({\ mathcal {S}}) = - \ suma _ {i} p_ {i} \ suma _ {j} p_ {i} (j) \ suma _ {k} p_ { i,j}(k)\ \log \ p_{i,j}(k).}$

Wydajność (znormalizowana entropia)

Alfabet źródłowy z nierównomiernym rozkładem będzie miał mniejszą entropię niż gdyby te symbole miały rozkład równomierny (tj. „alfabet zoptymalizowany”). Ten niedobór entropii można wyrazić jako stosunek zwany wydajnością :

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

Stosując podstawowe właściwości logarytmu, wielkość tę można również wyrazić jako:

${\ Displaystyle \ eta (X) = - \ suma _ {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)}}=\suma_{i=1}^{n}\log _{n}(p(x_{i})^{ -p(x_{i})})=\log _{n}(\prod _{i=1}^{n}p(x_{i})^{-p(x_{i})})}$

Wydajność jest przydatna w ilościowym określaniu efektywnego wykorzystania kanału komunikacyjnego . To sformułowanie jest również określane jako znormalizowana entropia, ponieważ entropia jest dzielona przez maksymalny ${\ Displaystyle {\ log _ {b} (n)}}$ . Ponadto wydajność jest obojętna na wybór (dodatniej) podstawy b , na co wskazuje niewrażliwość w końcowym logarytmie powyżej.

Entropia dla ciągłych zmiennych losowych

Entropia różniczkowa

Główny artykuł: Entropia różniczkowa

Entropia Shannona jest ograniczona do zmiennych losowych przyjmujących wartości dyskretne. Odpowiedni wzór na ciągłą zmienną losową z funkcją gęstości prawdopodobieństwa fa ( x ) ze skończonym lub nieskończonym wsparciem na linii rzeczywistej jest definiowany przez analogię, przy użyciu powyższej postaci entropii jako oczekiwania ${\ displaystyle \ mathbb {X}}$ :

${\ Displaystyle \ operatorname {H} (X) = \ mathbb {E} [- \ log f (X)] = - \ int _ {\ mathbb {X}} f (x) \ log f (x) \, \mathrm {d} x.}$

Jest to entropia różniczkowa (lub entropia ciągła). Prekursorem ciągłej entropii h [ f ] jest wyrażenie na funkcjonał Η w H- twierdzeniu Boltzmanna .

Chociaż analogia między obiema funkcjami jest sugestywna, należy zadać następujące pytanie: czy entropia różniczkowa jest prawidłowym rozszerzeniem dyskretnej entropii Shannona? Entropia różniczkowa nie ma wielu właściwości, które ma dyskretna entropia Shannona - może nawet być ujemna - i zaproponowano poprawki, w szczególności ograniczające gęstość dyskretnych punktów .

Aby odpowiedzieć na to pytanie, należy ustanowić połączenie między dwiema funkcjami:

Aby uzyskać ogólnie skończoną miarę, gdy rozmiar pojemnika spada do zera. W przypadku dyskretnym rozmiar pojemnika jest (niejawną) szerokością każdego z n (skończonych lub nieskończonych) pojemników, których prawdopodobieństwa są oznaczone przez p _n . Ponieważ domena ciągła jest uogólniona, szerokość musi być wyraźna.

Aby to zrobić, zacznij od funkcji ciągłej f podzielonej na przedziały o rozmiarze ${\ displaystyle \ Delta}$ . Z twierdzenia o wartości średniej wynika, że ​​w każdym przedziale istnieje taka wartość x _{i, że}

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

całkę funkcji f można przybliżyć (w sensie riemannowskim) przez

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

gdzie ten limit i „rozmiar pojemnika spada do zera” są równoważne.

będziemy oznaczać

$${\ Displaystyle \ operatorname {H} ^ {\ Delta}: = - \ suma _ {i = - \infty }^{\infty}f(x_{i})\Delta \log \left(f(x_{i})\Delta \right)}$$

i rozszerzając logarytm, mamy

$${\ Displaystyle \ operatorname {H} ^ {\ Delta} = - \ suma _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta \ log (f (x_ {i})) -\sum _{i=-\infty}^{\infty}f(x_{i})\Delta \log(\Delta).}$$

Ponieważ Δ → 0 mamy

${\ Displaystyle {\ rozpocząć {wyrównane} \ suma _ {i = - \ infty} ^ {\ infty} f (x_ {i}) \ Delta & \ do \ int _ {- \ infty} ^ {\ infty} f (x)\,dx=1\\\suma _{i=-\infty }^{\infty }f(x_{i})\Delta \log(f(x_{i}))&\do \int _{-\infty }^{\infty }f(x)\log f(x)\,dx.\end{wyrównane}}}$

Notatka; log(Δ) → −∞ jak Δ → 0 , wymaga specjalnej definicji entropii różniczkowej lub ciągłej:

${\ Displaystyle h [f] = \ lim _ {\ Delta \ do 0}\left(\mathrm {H} ^{\Delta }+\log \Delta \right)=-\int _{-\infty }^{\infty }f(x)\log f(x)\ ,dx,}$

która jest, jak powiedziano wcześniej, określana jako entropia różniczkowa. Oznacza to, że entropia różniczkowa nie jest granicą entropii Shannona dla n → ∞ . Różni się raczej od granicy entropii Shannona nieskończonym przesunięciem (zobacz także artykuł o wymiarze informacyjnym ).

Gęstość graniczna punktów dyskretnych

Główny artykuł: Granica gęstości punktów dyskretnych

W rezultacie okazuje się, że w przeciwieństwie do entropii Shannona, entropia różniczkowa na ogół nie jest dobrą miarą niepewności lub informacji. Na przykład entropia różniczkowa może być ujemna; nie jest również niezmienna w przypadku ciągłych transformacji współrzędnych. Problem ten można zilustrować zmianą jednostek, gdy x jest zmienną wymiarową. f ( x ) będzie wtedy miało jednostki 1/ x . Argument logarytmu musi być bezwymiarowy, w przeciwnym razie jest niewłaściwy, więc podana powyżej entropia różniczkowa będzie niewłaściwa. Jeśli Δ jest jakąś „standardową” wartością x (tj. „rozmiarem pojemnika”) i dlatego ma te same jednostki, to zmodyfikowaną entropię różniczkową można zapisać we właściwej postaci jako:

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

a wynik będzie taki sam dla dowolnego wyboru jednostek dla x . W rzeczywistości granica dyskretnej entropii jako $Displaystyle \$ również termin $N)}$ , który ogólnie byłby nieskończony. Można się tego spodziewać: zmienne ciągłe miałyby zazwyczaj nieskończoną entropię po dyskretyzacji. gęstość punktów dyskretnych jest w rzeczywistości miarą tego, o ile łatwiej jest opisać rozkład niż rozkład, który jest jednorodny w swoim schemacie kwantyzacji.

Względna entropia

Główny artykuł: Uogólniona entropia względna

Inną przydatną miarą entropii, która działa równie dobrze w przypadku dyskretnym, jak i ciągłym, jest względna entropia rozkładu. Definiuje się ją jako rozbieżność Kullbacka – Leiblera od rozkładu do miary odniesienia m w następujący sposób. Załóżmy, że rozkład prawdopodobieństwa p jest absolutnie ciągły względem miary m , tj. ma postać p ( dx ) = f ( x ) m ( dx ) dla pewnej nieujemnej m -całkowej funkcji f z m -całką 1, wtedy względną entropię można zdefiniować jako

${\ Displaystyle D _ {\ operatorname {KL}} (p \ | m) = \ int \ log (f (x)) p (dx) = \ int f (x) \ log (f (x)) m (dx ).}$

W tej postaci entropia względna uogólnia (aż do zmiany znaku) zarówno entropię dyskretną, gdzie miarą m jest miara licząca , jak i entropię różniczkową, gdzie miarą m jest miara Lebesgue'a . Jeśli miara m sama jest rozkładem prawdopodobieństwa, względna entropia jest nieujemna i wynosi zero, jeśli p = m jako miary. Jest ona zdefiniowana dla dowolnej przestrzeni miary, a więc jest niezależna od współrzędnych i niezmienna przy reparametryzacji współrzędnych, jeśli odpowiednio uwzględni się transformację miary m . Względna entropia i (domyślnie) entropia i entropia różniczkowa zależą od miary „referencyjnej” m .

Zastosowanie w kombinatoryce

Entropia stała się użyteczną wielkością w kombinatoryce .

Nierówność Loomisa-Whitneya

Prostym tego przykładem jest alternatywny dowód nierówności Loomisa-Whitneya : dla każdego podzbioru A ⊆ Z ^d mamy

${\ Displaystyle | A | ^ {d-1} \ równoważnik \ prod _ {i = 1} ^ {d} | P_ {i} (A) |}$

gdzie P _i jest rzutem ortogonalnym w i- tej współrzędnej:

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

Dowód jest prostym następstwem nierówności Shearera : jeśli X ₁ , ..., X _d są zmiennymi losowymi i S ₁ , ..., S _n są podzbiorami {1, ..., d } takimi, że każda liczba całkowita zatem między 1 a d leży dokładnie w r tych podzbiorów

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

gdzie ${\ Displaystyle (X_ {j}) _ {j \ w S_ {i}}}$ jest iloczynem kartezjańskim zmiennych losowych X _j z indeksami j w S _ja (więc wymiar tego wektor jest równy rozmiarowi S _i ).

Naszkicujemy, w jaki sposób wynika z tego Loomis-Whitney: Rzeczywiście, niech X będzie zmienną losową o jednolitym rozkładzie z wartościami w A i tak, aby każdy punkt w A występował z równym prawdopodobieństwem. Wtedy (na podstawie dalszych właściwości entropii wspomnianych powyżej) Η( X ) = log| | _ , gdzie | | _ oznacza kardynalność A . Niech S _ja = {1, 2, ..., ja −1, ja +1, ..., re }. Zakres ${\ Displaystyle (X_ {j}) _ {j \ w S_ {i}}}$ jest zawarty w P _ja ( ZA ) i stąd ${\ Displaystyle \ operatorname {H} [(X_ {j}) _ {j \ w S_ {i}}] \ równoważnik \ log | P_ {i} (A) |}$ . Teraz użyj tego, aby powiązać prawą stronę nierówności Shearera i potęgować przeciwne strony otrzymanej nierówności.

Przybliżenie do współczynnika dwumianowego

Dla liczb całkowitych 0 < k < n niech q = k / n . Następnie

${\ Displaystyle {\ Frac {2 ^ {n \ operatorname {H} (q)}} {n + 1}} \ leq {\tbinom {n}{k}}\leq 2^{n\mathrm {H} (q)},}$

Gdzie

${\ Displaystyle \ operatorname {H} (q) = - q \ log _ {2} (q) - (1-q) \ log _ {2} (1-q).}$

Dowód (szkic)

${\ Displaystyle {\ tbinom {n} {k}} q ^ {qn} (1-q) ^ {n-nq}}$ to jeden ${n }{\tbinom {n}{i}}q^{i}(1-q)^{ni}=(q+(1-q))^{n}=1.}$ ja Zmiana układu daje górną granicę. W przypadku dolnej granicy najpierw pokazuje się, używając pewnej algebry, że jest to największy wyraz w sumowaniu. Ale wtedy, ${\ Displaystyle {\ binom {n} {k}} q ^ {qn} (1-q) ^ {n-nq} \geq {\frac {1}{n+1}}}$ w sumowaniu jest n + 1 wyrazów. Zmiana układu daje dolną granicę.

Dobrą interpretacją tego jest to, że liczba łańcuchów binarnych o długości n z dokładnie k wieloma jedynekami wynosi około ${\ Displaystyle 2 ^ {n \ operatorname {H} (k/n)}}$ .

Zastosowanie w uczeniu maszynowym

uczenia maszynowego wywodzą się w dużej mierze ze statystyki, a także teorii informacji. Ogólnie rzecz biorąc, entropia jest miarą niepewności, a celem uczenia maszynowego jest zminimalizowanie niepewności.

uczenia się drzew decyzyjnych wykorzystują względną entropię do określenia reguł decyzyjnych rządzących danymi w każdym węźle. $jest równy różnicy$ informacji w drzewach decyzyjnych $}$ entropią entropią warunkową $\$$Y$ biorąc pod uwagę $, określa ilościowo oczekiwane informacje lub zmniejszenie entropii$ podstawie dodatkowej znajomości wartości atrybutu ${\ displaystyle X}$ . Zysk informacji służy do określenia, które atrybuty zbioru danych dostarczają najwięcej informacji i powinien być wykorzystany do optymalnego podziału węzłów drzewa.

wnioskowania bayesowskiego często stosują zasadę maksymalnej entropii w celu uzyskania rozkładów prawdopodobieństwa a priori . Chodzi o to, że dystrybucja, która najlepiej reprezentuje aktualny stan wiedzy o systemie, to ta z największą entropią, a zatem nadaje się do bycia priorytetem.

Klasyfikacja w uczeniu maszynowym przeprowadzana za pomocą regresji logistycznej lub sztucznych sieci neuronowych często wykorzystuje standardową funkcję strat, zwaną utratą entropii krzyżowej , która minimalizuje średnią entropię krzyżową między prawdą podstawową a przewidywanymi rozkładami. Ogólnie rzecz biorąc, entropia krzyżowa jest miarą różnic między dwoma zbiorami danych, podobnie jak dywergencja KL (inaczej entropia względna).

Zobacz też

• Przybliżona entropia (ApEn)
• Entropia (termodynamika)
• Entropia krzyżowa - jest miarą średniej liczby bitów potrzebnych do zidentyfikowania zdarzenia ze zbioru możliwości między dwoma rozkładami prawdopodobieństwa
• Entropia (strzałka czasu)
• Kodowanie entropijne - schemat kodowania, który przypisuje kody do symboli, aby dopasować długości kodu do prawdopodobieństw symboli.
• Szacowanie entropii
• Nierówność mocy entropii
• Informacje Fishera
• Wykres entropii
• Odległość Hamminga
• Historia entropii
• Historia teorii informacji
• Złożoność fluktuacji informacji
• Geometria informacji
• Entropia Kołmogorowa-Synaju w układach dynamicznych
• Odległość Levenshteina
• Wzajemne informacje
• Zakłopotanie
• Zmienność jakościowa – inne miary rozproszenia statystycznego dla rozkładów nominalnych
• Entropia względna kwantowa – miara rozróżnialności dwóch stanów kwantowych.
• Entropia Rényi – uogólnienie entropii Shannona; jest to jeden z rodziny funkcjonałów służących do ilościowego określania różnorodności, niepewności lub losowości systemu.
• Losowość
• Próbka entropii (SampEn)
• Indeks Shannona
• Indeks Theila
• Typoglikemia

Ten artykuł zawiera materiał z entropii Shannona na PlanetMath , który jest objęty licencją Creative Commons Attribution/Share-Alike License .

Dalsza lektura

Podręczniki z teorii informacji

•   Okładka, TM , Thomas, JA (2006), Elementy teorii informacji - wyd. 2. , Wiley-Interscience, ISBN 978-0-471-24195-9
•   MacKay, DJC (2003), Teoria informacji, wnioskowanie i algorytmy uczenia się , Cambridge University Press, ISBN 978-0-521-64298-9
•   Arndt, C. (2004), Środki informacyjne: informacja i jej opis w nauce i inżynierii , Springer, ISBN 978-3-540-40855-0
• Gray, RM (2011), Entropia i teoria informacji , Springer.
•   Martin, Nathaniel FG i Anglia, James W. (2011). Matematyczna teoria entropii . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-17738-2 . {{ cite book }} : CS1 maint: używa parametru autorów ( link )
•   Shannon, CE , Weaver, W. (1949) Matematyczna teoria komunikacji , Univ of Illinois Press. ISBN 0-252-72548-4
•   Stone, JV (2014), rozdział 1 teorii informacji: wprowadzenie do samouczka , University of Sheffield, Anglia. ISBN 978-0956372857 .

Linki zewnętrzne

• „Entropia” , Encyklopedia matematyki , EMS Press , 2001 [1994]
• „Entropia” w Rosetta Code — repozytorium implementacji entropii Shannona w różnych językach programowania.
• Entropia to interdyscyplinarne czasopismo poświęcone wszystkim aspektom koncepcji entropii. Otwarty dostęp.