Entropia (teoria informacji) - Entropy (information theory)

Dwa bity entropii: w przypadku dwóch uczciwych rzutów monetą entropia informacji w bitach jest logarytmem o podstawie 2 liczby możliwych wyników; przy dwóch monetach są cztery możliwe wyniki i dwa bity entropii. Ogólnie entropia informacji to średnia ilość informacji przekazywanych przez zdarzenie, przy uwzględnieniu wszystkich możliwych wyników.

W teorii informacji , entropia o zmiennej losowej jest średni poziom „informacji”, „zaskoczenia” lub „niepewności” występującego w możliwych wyników zmiennej. Pojęcie entropii informacyjnej zostało wprowadzone przez Claude'a Shannona w jego pracy z 1948 r. „ A Mathematical Theory of Communication ” i jest również określane jako entropia Shannona . Jako przykład rozważ monetę tendencyjną z prawdopodobieństwem p wylądowania na orłach i prawdopodobieństwem 1 − p wylądowania na rewersie. Maksymalna niespodzianka występuje dla p = 1/2 , gdy nie ma powodu, aby oczekiwać jednego wyniku zamiast drugiego. W tym przypadku rzut monetą ma entropię jednego bitu . Minimalna niespodzianka występuje dla p = 0 lub p = 1 , gdy zdarzenie jest znane, a entropia wynosi zero bitów. Inne wartości p dają różne entropie od zera do jednego bitu.

Biorąc pod uwagę dyskretną zmienną losową , z możliwymi wynikami , które występują z prawdopodobieństwem, entropia jest formalnie zdefiniowana jako:

gdzie oznacza sumę nad możliwymi wartościami zmiennej. Wybór podstawy , logarytmu , jest różny dla różnych zastosowań. Baza 2 daje jednostkę bitów (lub „ shannons ”), podczas gdy podstawa e daje „jednostki naturalne” nat , a podstawa 10 daje jednostki „dits”, „banów” lub „ hartley ”. Równoważna definicja entropii jest wartość oczekiwana od siebie informacji zmiennej.

Entropia została pierwotnie stworzona przez Shannona jako część jego teorii komunikacji, w której system transmisji danych składa się z trzech elementów: źródła danych, kanału komunikacyjnego i odbiornika. „Podstawowy problem komunikacji” – jak wyraził Shannon – polega na tym, aby odbiorca był w stanie zidentyfikować, jakie dane zostały wygenerowane przez źródło, na podstawie sygnału, który otrzymuje przez kanał. Shannon rozważał różne sposoby kodowania, kompresowania i przesyłania wiadomości ze źródła danych i udowodnił w swoim słynnym twierdzeniu o kodowaniu źródłowym, że entropia reprezentuje absolutną matematyczną granicę tego, jak dobrze dane ze źródła mogą być bezstratnie skompresowane na całkowicie bezszumowym kanale. Shannon znacznie wzmocnił ten wynik dla zaszumionych kanałów w swoim twierdzeniu o kodowaniu zaszumionych kanałów .

Entropia w teorii informacji jest bezpośrednio analogiczna do entropii w termodynamice statystycznej . Analogia powstaje, gdy wartości zmiennej losowej oznaczają 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 . Definicję można wyprowadzić z zestawu aksjomatów ustalających, że entropia powinna być miarą tego, jak „zaskakujący” jest średni wynik zmiennej. W przypadku ciągłej zmiennej losowej entropia różniczkowa jest analogiczna do entropii.

Wstęp

Podstawowa idea teorii informacji polega na tym, że „wartość informacyjna” komunikowanego komunikatu zależy od stopnia, w jakim treść komunikatu jest zaskakująca. Jeśli zdarzenie jest bardzo prawdopodobne, nie jest niespodzianką (i generalnie nieciekawą), kiedy to zdarzenie dzieje się zgodnie z oczekiwaniami; stąd transmisja takiej wiadomości niesie ze sobą bardzo mało nowych informacji. Jeśli jednak zdarzenie jest mało prawdopodobne, o wiele bardziej pouczające jest dowiedzenie się, że zdarzenie miało miejsce lub się wydarzy. Na przykład wiedza, że ​​jakaś konkretna liczba nie będzie zwycięską liczbą w loterii, dostarcza bardzo mało informacji, ponieważ każdy wybrany numer prawie na pewno nie wygra. Jednak wiadomo, że dany numer będzie wygrać na loterii ma dużą wartość, ponieważ komunikuje wyniku bardzo niskiego prawdopodobieństwa zdarzenia.

Zawartość informacyjna (nazywana również zaskoczeniem ) zdarzenia to funkcja, która rośnie wraz ze spadkiem prawdopodobieństwa zdarzenia. Więc kiedy jest bliski 1, mówimy, że „zaskoczenie” zobaczenia tego zdarzenia jest małe, ale jeśli jest bliskie 0, powiedzielibyśmy, że zaskoczenie zobaczenia tego zdarzenia jest wysokie. Możliwym sposobem uchwycenia tej relacji byłoby zdefiniowanie niespodzianki jako , ale w przypadkach, gdy , doprowadziłoby to do niespodzianki równej 1 (gdy bardziej sensowne byłoby stwierdzenie, że ma 0 niespodzianek). Dlatego ładniejszą funkcją do użycia jest logarytm 1 nad prawdopodobieństwem , co dałoby nam 0 zaskoczenia, gdy prawdopodobieństwo zdarzenia wynosi 1. W rzeczywistości log jest jedyną funkcją, która spełnia określony zestaw charakteryzacji .

Stąd możemy zdefiniować informację (lub zaskoczenie) E przez lub równoważnie , gdzie jest logarytm . Entropia mierzy oczekiwaną (tj. średnią) ilość przekazywanych informacji poprzez identyfikację wyniku losowej próby. Oznacza to, że rzucenie kostką ma wyższą entropię niż rzucenie monetą, ponieważ każdy wynik rzutu kostką ma mniejsze prawdopodobieństwo (około ) niż każdy wynik rzutu monetą ( ).

Rozważmy przykład rzutu monetą. Jeśli prawdopodobieństwo rzutu orłem jest takie samo, jak prawdopodobieństwo rzutu resztkami, to entropia rzutu monetą jest tak wysoka, jak w przypadku procesu z dwoma wynikami. Nie ma sposobu, aby przewidzieć wynik rzutu monetą z wyprzedzeniem: jeśli trzeba wybierać, nie ma średniej przewagi, którą można uzyskać, przewidując, że rzut wypadnie rewersem lub rewersem, ponieważ obie prognozy będą prawidłowe z prawdopodobieństwem . Taki rzut monetą ma entropię (w bitach), ponieważ istnieją dwa możliwe wyniki, które występują z równym prawdopodobieństwem, a poznanie rzeczywistego wyniku zawiera jeden bit informacji. W przeciwieństwie do tego, rzut monetą przy użyciu monety, która ma dwa orły i nie ma reszek, ma entropię, ponieważ moneta zawsze wypadnie orłem, a wynik można dokładnie przewidzieć. Podobnie, jeden tryt z równoprawdopodobnymi wartościami zawiera (około 1,58496) bitów informacji, ponieważ może mieć jedną z trzech wartości.

Tekst angielski, traktowany jako ciąg znaków, ma dość niską entropię, czyli jest dość przewidywalny. Jeśli nie wiemy dokładnie, co będzie dalej, 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 kombinację z „q” i że kombinacja „th” będzie bardziej powszechna niż „z”, „q” lub „qu”. Po kilku pierwszych literach często można odgadnąć resztę wyrazu. Tekst angielski ma od 0,6 do 1,3 bitów entropii na znak wiadomości.

Jeśli schemat kompresji jest bezstratny – taki, w którym zawsze możesz odzyskać całą oryginalną wiadomość przez dekompresję – wtedy skompresowana wiadomość zawiera taką samą ilość informacji jak oryginał, ale jest przekazywana w mniejszej liczbie znaków. Posiada więcej informacji (wyższa entropia) na postać. Skompresowana wiadomość ma mniejszą nadmiarowość . Twierdzenie Shannona o kodowaniu źródłowym stwierdza, że ​​schemat kompresji bezstratnej nie może skompresować wiadomości, średnio, aby mieć więcej niż jeden bit informacji na bit wiadomości, ale każda wartość mniejsza niż jeden bit informacji na bit wiadomości może być osiągnięta przez zastosowanie odpowiedniego schemat kodowania. Entropia wiadomości na bit pomnożona przez długość tej wiadomości jest miarą tego, ile informacji zawiera wiadomość.

Gdyby ktoś miał przesłać sekwencje składające się z 4 znaków 'A', 'B', 'C' i 'D', transmitowaną wiadomością może być 'ABADDCAB'. Teoria informacji daje sposób na obliczenie najmniejszej możliwej ilości informacji, która to przekaże. Jeśli wszystkie 4 litery są jednakowo prawdopodobne (25%), nie można zrobić lepszego (na kanale binarnym) niż zakodowanie 2 bitów (binarnie) każdej litery: 'A' może zakodować '00', 'B' jako „01”, „C” jako „10”, a „D” jako „11”. Jeśli 'A' występuje z prawdopodobieństwem 70%, 'B' z 26%, a 'C' i 'D' z 2% każdy, można przypisać kody o zmiennej długości, tak że otrzymanie '1' oznacza, że ​​trzeba spojrzeć na inny bit chyba że odebrano już 2 bity z kolejnych jedynek. W tym przypadku „A” będzie kodowane jako „0” (jeden bit), „B” jako „10”, „C” jako „110”, a D jako „111”. Łatwo zauważyć, że w 70% przypadków wystarczy wysłać tylko jeden bit, w 26% dwa bity, a tylko w 4% przypadków 3 bity. Średnio wymagane są mniej niż 2 bity, ponieważ entropia jest niższa (ze względu na dużą częstość występowania „A”, a następnie „B” – łącznie 96% znaków). Obliczenie sumy logarytmicznych prawdopodobieństw ważonych prawdopodobieństwem mierzy i ujmuje ten efekt.

Twierdzenie Shannona sugeruje również, że żaden bezstratny schemat kompresji nie może skrócić wszystkich wiadomości. Jeśli jakieś wiadomości wychodzą krócej, przynajmniej jedna musi wyjść dłużej, ze względu na zasadę szufladki . W praktyce zwykle nie stanowi to problemu, ponieważ zwykle interesuje nas tylko kompresja pewnych rodzajów wiadomości, takich jak dokument w języku angielskim, w przeciwieństwie do bełkotu lub zdjęć cyfrowych, a nie szumu, i nie ma znaczenia, czy algorytm kompresji powiększa niektóre mało prawdopodobne lub nieciekawe sekwencje.


Definicja

Nazwany na cześć twierdzenia Boltzmanna , Shannon zdefiniował entropię Η (grecka litera eta ) dyskretnej zmiennej losowej z możliwymi wartościami i funkcją masy prawdopodobieństwa jako:

Tutaj jest spodziewany operator wartość , a I jest treść informacji o X . sama jest zmienną losową.

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

gdzie b jest podstawa z logarytmu używany. Wspólne wartości b to 2, liczba Eulera e i 10, a odpowiadającymi jednostkami entropii są bity dla b = 2 , nats dla b = e i bany dla b = 10 .

W przypadku P( x i ) = 0 dla niektórych i , wartość odpowiedniej sumy 0 log b (0) jest przyjmowana jako 0 , co jest zgodne z limitem :

Można również zdefiniować warunkową entropię dwóch zmiennych oraz przyjmując wartości i odpowiednio jako:

gdzie jest prawdopodobieństwo, że i . Wielkość tę należy rozumieć jako wielkość losowości w zmiennej losowej przy danej zmiennej losowej .

Przykład

Entropia Η( X ) (tj. oczekiwana niespodzianka ) rzutu monetą, mierzona w bitach, wykreślona w funkcji odchylenia monety Pr( X = 1) , gdzie X = 1 reprezentuje wynik orłów.

Tutaj entropia wynosi co najwyżej 1 bit, a przekazanie wyniku rzutu monetą (2 możliwe wartości) będzie wymagać średnio co najwyżej 1 bitu (dokładnie 1 bit dla uczciwej monety). Wynik uczciwej kości (6 możliwych wartości) miałby log entropii 2 6 bitów.

Rozważ rzucenie monetą ze znanym, niekoniecznie sprawiedliwym, prawdopodobieństwem wyrzucenia orła lub reszki; można to zamodelować jako proces Bernoulliego .

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

Jeśli jednak wiemy, że moneta nie jest sprawiedliwa, ale wypada reszek lub reszek z prawdopodobieństwem p i q , gdzie pq , wtedy niepewność jest mniejsza. Za każdym razem, gdy jest rzucany, jest bardziej prawdopodobne, że jedna strona wyskoczy niż druga. Mniejsza niepewność jest określana ilościowo 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

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

Entropię można znormalizować, dzieląc ją przez długość informacji. Ten stosunek nazywa się entropią metryczną i jest miarą losowości informacji.

Charakteryzacja

Aby zrozumieć znaczenie p i log( p i ) , najpierw zdefiniuj funkcję informacyjną I w kategoriach zdarzenia i z prawdopodobieństwem p i . Ilość informacji uzyskanych dzięki obserwacji zdarzenia i wynika z roztworu Shannona podstawowych właściwości z informacjami :

  1. I( p ) jest monotonicznie malejące w p : wzrost prawdopodobieństwa zdarzenia zmniejsza informację z obserwowanego zdarzenia i vice versa.
  2. I( p ) ≥ 0 : informacja jest wielkością nieujemną .
  3. I(1) = 0 : zdarzenia, które zawsze występują, nie przekazują informacji.
  4. I( p 1 , p 2 ) = I( p 1 ) + I( p 2 ) : informacja wyciągnięta z niezależnych zdarzeń jest sumą informacji wyciągniętych z każdego zdarzenia.

Biorąc pod uwagę dwa niezależne zdarzenia, jeśli pierwsze zdarzenie może dać jeden z n równoprawdopodobnych 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 2 ( n ) bitów jest potrzebnych do zakodowania pierwszej wartości i log 2 ( m ) do zakodowania drugiej, potrzebny jest log 2 ( mn ) = log 2 ( m ) + log 2 ( n ) do zakodowania obu .

Shannon odkrył, że odpowiedni wybór daje:

W rzeczywistości jedyne możliwe wartości to for . Dodatkowo wybranie wartości k jest równoznaczne z wybraniem wartości dla , tak że x odpowiada podstawie logarytmu . Zatem entropia charakteryzuje się powyższymi czterema właściwościami.

Różne jednostki informacji ( bity dla logarytmu binarnego log 2 , nats dla logarytmu naturalnego ln , bany dla logarytmu dziesiętnego log 10 itd.) są wzajemnie stałymi wielokrotnościami . Na przykład, w przypadku uczciwego rzutu monetą, orła dostarczają log 2 (2) = 1 bit informacji, czyli około 0,693 nata lub 0,301 cyfry dziesiętnej. Ze względu na addytywność n rzutów dostarcza n bitów informacji, co stanowi około 0,693 n natów lub 0,301 n cyfr dziesiętnych.

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

Charakterystyka alternatywna

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

  1. Ciągłość: H powinna być ciągła , tak aby zmiana wartości prawdopodobieństw o ​​bardzo małą wielkość zmieniała entropię tylko w niewielkim stopniu.
  2. Symetria: H powinno pozostać niezmienione, jeśli wyniki x i są ponownie uporządkowane. Oznacza to, że dla każdej permutacji z .
  3. Maksimum: powinno być maksimum, jeśli wszystkie wyniki są jednakowo prawdopodobne, tj . .
  4. Rosnąca liczba wyników: w przypadku zdarzeń równoprawdopodobnych entropia powinna wzrastać wraz z liczbą wyników, tj.
  5. Addytywność: przy danym zespole n równomiernie rozmieszczonych elementów, które są podzielone na k pudełek (podsystemów) z b 1 , ..., b k elementów, entropia całego zespołu powinna być równa sumie entropii system pudełek i indywidualne entropie pudełek, każdy ważony prawdopodobieństwem znalezienia się w tym konkretnym pudle.

Zasada addytywności ma następujące konsekwencje: dla liczb całkowitych dodatnich b i gdzie b 1 + ... + b k = n ,

Wybranie k = n , b 1 = ... = b n = 1 oznacza, że ​​entropia pewnego wyniku wynosi zero: Η 1 (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 Redundancja (teoria informacji) .

Dalsze właściwości

Entropia Shannona spełnia następujące właściwości, dla niektórych z nich przydatne jest zinterpretowanie entropii jako ilości poznanej informacji (lub wyeliminowanej niepewności) poprzez ujawnienie wartości zmiennej losowej X :

  • Dodanie lub usunięcie zdarzenia z prawdopodobieństwem zerowym nie wpływa na entropię:
.
.
Ta maksymalna entropia log b ( n ) jest skutecznie osiągana przez alfabet źródłowy o jednorodnym rozkładzie prawdopodobieństwa: niepewność jest maksymalna, gdy wszystkie możliwe zdarzenia są jednakowo prawdopodobne.
  • Entropia lub ilość informacji ujawnionych przez oszacowanie ( X , Y ) (czyli jednoczesne oszacowanie X i Y ) jest równa informacji ujawnionej przez przeprowadzenie dwóch kolejnych eksperymentów: najpierw oszacowanie wartości Y , a następnie ujawnienie wartości X biorąc pod uwagę, że znasz wartość Y . Może to być zapisane jako:
  • Jeśli gdzie jest funkcją, to . Stosując poprzedni wzór do plonów
więc entropia zmiennej może się zmniejszyć tylko wtedy, gdy ta ostatnia jest przekazywana 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ść):
  • Entropia dwóch jednoczesnych zdarzeń jest nie więcej niż sumą entropii każdego pojedynczego zdarzenia, tj. z równością wtedy i tylko wtedy, gdy te dwa zdarzenia są niezależne.
  • Entropia jest wklęsła w funkcji masy prawdopodobieństwa , tj.
dla wszystkich funkcji masy prawdopodobieństwa i .

Aspekty

Związek z entropią termodynamiczną

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 ,

gdzie k B jest stałą Boltzmanna , a p i jest prawdopodobieństwem mikrostanu . Gibbs entropia określono przez J. Willard Gibbs 1878 po wcześniejszych prac 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 roku,

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

Na codziennym praktycznym poziomie powiązania między entropią informacyjną a entropią termodynamiczną nie są oczywiste. Fizycy i chemicy są bardziej zainteresowani zmianami w entropii, gdy układ spontanicznie ewoluuje od swoich warunków początkowych, zgodnie z drugą zasadą termodynamiki , a nie niezmiennym rozkładem prawdopodobieństwa. Jak wskazuje drobiazgowość stałej k B Boltzmanna , zmiany w S / k B dla nawet niewielkich ilości substancji w procesach chemicznych i fizycznych reprezentują ilości entropii, które są niezwykle duże w porównaniu z czymkolwiek w kompresji danych lub przetwarzaniu sygnału . 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 stworzony przez Ludwiga Boltzmanna i wyrażony jego słynnym równaniem :

gdzie jest entropią termodynamiczną danego makrostanu (określoną przez parametry termodynamiczne, takie jak temperatura, objętość, energia itp.), W to liczba mikrostanów (różne kombinacje cząstek w różnych stanach energetycznych), które mogą dać dany makrostan, oraz k B jest stałą Boltzmanna . Zakłada się, że każdy mikrostan jest jednakowo prawdopodobny, więc prawdopodobieństwo danego mikrostanu wynosi p i = 1/W . Gdy te prawdopodobieństwa są podstawione w powyższym wyrażeniu dla entropii Gibbs (lub równoważnie k B razy entropii Shannon), wyników równań Boltzmanna. W kategoriach teorii informacji entropia informacyjna systemu to ilość „brakujących” informacji potrzebnych do określenia mikrostanu w danym makrostanie.

W opinii Jaynesa (1957), entropia termodynamiczna, wyjaśniona przez mechanikę statystyczną , powinna być postrzegana jako zastosowanie teorii informacji Shannona: entropia termodynamiczna jest interpretowana jako proporcjonalna do ilości dalszych informacji Shannona potrzebnych do zdefiniowania szczegółowego mikroskopu. stan układu, który pozostaje niekomunikowany opisem wyłącznie w kategoriach zmiennych makroskopowych termodynamiki klasycznej, przy czym stała proporcjonalności jest tylko stałą Boltzmanna . Dodanie ciepła do układu zwiększa jego entropię termodynamiczną, ponieważ zwiększa liczbę możliwych stanów mikroskopowych układu zgodnych 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) zredukować entropię termodynamiczną układu, wykorzystując informacje o stanach poszczególnych cząsteczek; ale, jak wykazali Landauer (od 1961) i współpracownicy, aby sam demon mógł funkcjonować, musi w tym procesie zwiększyć entropię termodynamiczną, przynajmniej o ilość informacji Shannona, którą proponuje najpierw pozyskać i przechowywać; a więc całkowita entropia termodynamiczna nie maleje (co rozwiązuje paradoks). Zasada Landauera nakłada dolną granicę na ilość ciepła, które komputer musi wytworzyć, aby przetworzyć określoną ilość informacji, chociaż współczesne komputery są znacznie mniej wydajne.

Kompresja danych

Entropia jest definiowana w kontekście modelu probabilistycznego. Niezależne uczciwe rzuty monetą mają entropię 1 bitu na rzut. Źródło, które zawsze generuje długi ciąg znaków B, ma entropię równą 0, ponieważ następnym znakiem będzie zawsze „B”.

Szybkość entropii źródła danych oznacza średnią liczbę bitów na symbol potrzebną do jego zakodowania. Eksperymenty Shannona z ludzkimi predyktorami pokazują szybkość informacji między 0,6 a 1,3 bita na znak w języku angielskim; algorytm kompresji PPM może osiągnąć stopień sprężania 1,5 bitów na znak w tekście angielskim.

Definicja entropii Shannona, zastosowana do źródła informacji, może określić minimalną przepustowość kanału wymaganą do niezawodnej transmisji źródła w postaci 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łady tych ostatnich obejmują redundancję w strukturze języka lub właściwości statystyczne związane z częstotliwością występowania par liter lub słów, trypletów itp.

Minimalną przepustowość kanału można zrealizować teoretycznie przy użyciu typowego zestawu lub w praktyce przy użyciu kodowania Huffmana , Lempel-Ziv lub kodowania arytmetycznego . (Patrz także złożoność Kołmogorowa .) W praktyce algorytmy kompresji celowo zawierają pewną rozsądną nadmiarowość w postaci sum kontrolnych w celu ochrony przed błędami.

Badanie przeprowadzone w 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 2007 roku, tym samym szacując entropię technologicznie dostępnych źródeł.

Wszystkie liczby w entropowo skompresowanych eksabajtach
Rodzaj informacji 1986 2007
Składowanie 2,6 295
Audycja 432 1900
Telekomunikacja 0,281 65

Autorzy szacują technologiczną zdolność ludzkości do przechowywania informacji (w pełni entropowo skompresowanych) w 1986 r. i ponownie w 2007 r. Dzielą informacje na trzy kategorie — przechowywanie informacji na nośniku, odbieranie informacji za pośrednictwem jednokierunkowych sieci nadawczych lub wymianę informacji poprzez dwukierunkowe sieci telekomunikacyjne .

Entropia jako miara różnorodności

Entropia to jeden z kilku sposobów pomiaru różnorodności. W szczególności entropia Shannona jest logarytmem 1 D , rzeczywistego wskaźnika różnorodności z parametrem równym 1.

Ograniczenia entropii

Istnieje szereg pojęć związanych z entropią, które matematycznie określają ilościowo zawartość informacji:

("Szybkość informacji o sobie" może być również zdefiniowana dla określonej sekwencji wiadomości lub symboli generowanych przez dany proces stochastyczny: będzie ona zawsze równa szybkości entropii w przypadku procesu stacjonarnego .) Inne ilości informacji są również wykorzystywane do porównywania lub powiązania różnych źródeł informacji.

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

Jeśli używane są bardzo duże bloki, oszacowanie szybkości entropii na znak może stać się sztucznie niskie, ponieważ rozkład prawdopodobieństwa sekwencji nie jest dokładnie znany; to tylko szacunek. Jeśli weźmie się pod uwagę tekst każdej kiedykolwiek opublikowanej książki jako sekwencję, w której każdy symbol jest tekstem całej książki, i jeśli jest N opublikowanych książek, a każda książka jest opublikowana tylko raz, oszacowanie prawdopodobieństwa każdej książki jest 1/ N , a entropia (w bitach) wynosi −log 2 (1/ N ) = log 2 ( N ) . Jako praktyczny kod odpowiada to przypisaniu każdej książce unikalnego identyfikatora i używaniu go zamiast tekstu książki za każdym razem, gdy 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 języka w ogóle: nie jest możliwe zrekonstruowanie książki na podstawie jej identyfikatora bez znajomości rozkładu prawdopodobieństwa, to znaczy , pełny tekst wszystkich książek. Kluczową ideą jest rozważenie złożoności modelu probabilistycznego. Złożoność Kołmogorowa jest teoretycznym uogólnieniem tej idei, które pozwala na rozważenie zawartości informacyjnej ciągu niezależnego od jakiegokolwiek konkretnego modelu prawdopodobieństwa; uwzględnia najkrótszy program dla uniwersalnego komputera, który wyprowadza sekwencję. Kod, który osiąga współczynnik entropii ciągu dla danego modelu, plus książka kodów (tj. model probabilistyczny), jest jednym z takich programów, ale może nie być najkrótszym.

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, co daje entropia około log 2 ( n ) . Pierwsze 128 symboli ciągu Fibonacciego ma entropię około 7 bitów/symbol, ale sekwencja może być wyrażona 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ż jej rzeczywista niepewność jest niewymierna. Na przykład klucz 128-bitowy, który jest generowany jednolicie i losowo, ma 128 bitów entropii. Złamanie przy użyciu brutalnej siły wymaga również (średnio) domysłów. Entropia nie jest w stanie uchwycić wymaganej liczby prób, jeśli możliwe klucze nie są wybierane jednolicie. Zamiast tego do pomiaru wysiłku wymaganego do ataku brute force można użyć miary zwanej zgadywaniem .

Inne problemy mogą wynikać z niejednorodnych dystrybucji stosowanych w kryptografii. Na przykład jednorazowy pad binarny o wartości 1 000 000 cyfr przy użyciu wyłącznego lub. Jeśli pad ma 1 000 000 bitów entropii, jest idealny. Jeżeli nakładka ma 999,999 bitów entropii, równomiernie rozłożonych (każdy pojedynczy bit nakładki ma 0,999999 bitów entropii), może to zapewnić dobre zabezpieczenie. Ale jeśli pad ma 999 999 bitów entropii, gdzie pierwszy bit jest stały, a pozostałe 999 999 bitów jest całkowicie losowe, pierwszy bit zaszyfrowanego tekstu w ogóle nie zostanie zaszyfrowany.

Dane jako proces Markowa

Powszechny sposób definiowania entropii 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:

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

gdzie i jest stanem (pewne poprzedzające znaki) i jest prawdopodobieństwem j podanym i jako poprzedni znak.

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

Wydajność (znormalizowana entropia)

Alfabet źródłowy z niejednorodnym 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ą:

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

Wydajność ma zastosowanie w ilościowym określeniu efektywnego wykorzystania kanału komunikacyjnego . To sformułowanie jest również określane jako entropia znormalizowana, ponieważ entropia jest podzielona przez maksymalną entropię . 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óżnicowa

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 f ( x ) o skończonym lub nieskończonym podparciu na linii rzeczywistej definiuje się przez analogię, stosując powyższą postać entropii jako oczekiwanie:

Jest to entropia różniczkowa (lub entropia ciągła). Prekursor stałego entropii h [ f ] jest ekspresja funkcjonalnego Ti w H twierdzenia o Boltzmanna .

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

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

Aby uzyskać ogólnie skończoną miarę, gdy rozmiar pojemnika zbliża się do zera. W przypadku dyskretnym rozmiar bin to (ukryta) szerokość każdego z n (skończonych lub nieskończonych) bin, których prawdopodobieństwa są oznaczone przez p n . Ponieważ domena ciągła jest uogólniana, szerokość musi być wyraźnie określona.

Aby to zrobić, zacznij od funkcji ciągłej f zdyskretyzowanej do pojemników o rozmiarze . Według twierdzenia o wartości średniej istnieje wartość x i w każdym przedziale taka, że

całka funkcji f może być aproksymowana (w sensie riemannowskim) przez

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

będziemy oznaczać

i rozszerzając logarytm, mamy

Jako Δ → 0, mamy

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

co jest, jak powiedziano wcześniej, nazywane entropią różniczkową. Oznacza to, że entropia różniczkowa nie jest granicą entropii Shannona dla n → ∞ . Raczej różni się od granicy entropii Shannona o nieskończone przesunięcie (patrz też artykuł o wymiarze informacyjnym ).

Ograniczenie gęstości punktów dyskretnych

Okazuje się w rezultacie, że w przeciwieństwie do entropii Shannona, entropia różniczkowa nie jest generalnie dobrą miarą niepewności lub informacji. Na przykład entropia różniczkowa może być ujemna; również nie jest niezmienna w ciągłych przekształceniach współrzędnych. Problem ten można zilustrować zmianą jednostek, gdy x jest zmienną wymiarowaną. f(x) będzie wtedy miał jednostki 1/x . Argument logarytmu musi być bezwymiarowy, w przeciwnym razie jest niewłaściwy, tak że entropia różniczkowa, jak podano powyżej, będzie niewłaściwa. Jeśli Δ jest pewną „standardową” wartością x (tj. „rozmiarem binu”) i dlatego ma te same jednostki, to zmodyfikowana entropia różniczkowa może być zapisana we właściwej postaci jako:

a wynik będzie taki sam dla dowolnego wyboru jednostek dla x . W rzeczywistości, granica entropii dyskretnej zawierałaby również wyraz , który na ogół byłby nieskończony. Oczekuje się tego: zmienne ciągłe mają zazwyczaj nieskończoną entropię po dyskretyzacji. Ograniczającym gęstość dyskretnych punktów jest naprawdę miarą tego, jak wiele łatwiej dystrybucja jest opisanie niż rozkładzie, który jest jednolity nad swoim systemem kwantyzacji.

Entropia względna

Inną użyteczną miarą entropii, która działa równie dobrze w przypadku dyskretnym i ciągłym, jest względna entropia rozkładu. Jest on zdefiniowany jako rozbieżność Kullbacka-Leiblera z 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 funkcji m- całkowalnej f z m- całką 1, wtedy względną entropię można zdefiniować jako

W tej postaci entropia względna uogólnia (do zmiany znaku) zarówno entropię dyskretną, gdzie miara m jest miarą zliczania , jak i entropię różniczkową, gdzie miara m jest miarą Lebesgue'a . Jeśli miara m jest sama w sobie rozkładem prawdopodobieństwa, względna entropia jest nieujemna i zero, jeśli p = m jako miary. Jest ona definiowana dla dowolnej przestrzeni miar, stąd współrzędna niezależna i niezmienna przy reparametryzacji współrzędnych, jeśli właściwie uwzględni się transformację miary m . Entropia względna i (w domyśle) entropia i entropia różniczkowa zależą od „referencyjnej” miary 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 AZ d mamy

gdzie P i jest rzutem ortogonalnym na i- tą współrzędną:

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

gdzie jest iloczynem kartezjańskim zmiennych losowych X j o indeksach j w S i (a więc wymiar tego wektora jest równy rozmiarowi S i ).

Szkicujemy, jak Loomis-Whitney z tego wynika: Rzeczywiście, niech X będzie zmienną losową o rozkładzie jednostajnym o wartościach w A i tak, aby każdy punkt w A występował z równym prawdopodobieństwem. Wtedy (według dalszych własności entropii wymienionych powyżej) Η( X ) = log| | , gdzie | | oznacza liczność A . Niech S i = {1, 2, ..., i -1, i +1, ..., d }. Zakres jest zawarty w P ı ( A ) , a co za tym idzie . Teraz użyj tego, aby powiązać prawą stronę nierówności Shearera i zwiększyć potęgę przeciwnych stron powstałej nierówności.

Aproksymacja do współczynnika dwumianowego

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

gdzie

Miła interpretacja tego jest taka, że ​​liczba ciągów binarnych o długości n z dokładnie k wielu jedynek wynosi w przybliżeniu .

Zobacz też

Bibliografia

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 do teorii informacji

Zewnętrzne linki