Entropia (teoria informacji)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ten artykuł dotyczy pojęcia z dziedziny teorii informacji. Zobacz też: inne znaczenia tego terminu.

Entropia – średnia ilość informacji, przypadająca na pojedynczą wiadomość ze źródła informacji. Innymi słowy jest to średnia ważona ilości informacji niesionej przez pojedynczą wiadomość, gdzie wagami są prawdopodobieństwa nadania poszczególnych wiadomości.

Wzór na entropię zmiennej losowej X o zbiorze wartości \{x_1, x_2, ..., x_n\}[1]:

H(X)=\sum_{i=1}^np(x_i)\log_r \frac{1}{p(x_i)}= - \sum_{i=1}^np(x_i)\log_r {p(x_i)}\,\!

gdzie p(x_i) to prawdopodobieństwo zajścia zdarzenia {\textstyle x_i}, a r to podstawa logarytmu. W teorii informacji najczęściej stosuje się logarytm o podstawie 2, wówczas jednostką entropii jest bit. Dla r=e jednostka ta nazywa się nat (nit), natomiast dla r=10 – dit lub hartley. W przypadku gdy p(x_i)=0 dla pewnego i, wartość składnika 0 \log_r{0} jest przyjmowana jako 0, co jest zgodne z granicą:

\lim_{p\to0+}p\log (p) = 0.

W latach 60. węgierski matematyk Alfred Rényi uogólnił pojęcie entropii do zbioru funkcji za pomocą których można opisać ilościowo różnorodność, niepewność czy losowość systemu. Miara ta od jego nazwiska nazywana jest entropią Rényi.

Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego w następnej chwili. Jeżeli jakieś zdarzenie w zbiorze zdarzeń występuje z prawdopodobieństwem równym 1, to entropia układu wynosi wówczas 0, gdyż z góry wiadomo, co się stanie – nie ma niepewności.

Własności entropii:

  • jest nieujemna;
  • jest maksymalna, gdy prawdopodobieństwa zajść zdarzeń są takie same;
  • jest równa 0, gdy stany systemu przyjmują wartości tylko 0 albo tylko 1;
  • własność superpozycji – gdy dwa systemy są niezależne, to entropia sumy systemów równa się sumie entropii;
  • jeśli ze źródła danych pobierane są k-literowe ciągi, wówczas entropia wynosi H(X^{(k)}) = kH(X).

Definicja informacyjna była pierwotnie próbą ujęcia tradycyjnego pojęcia entropii znanego z termodynamiki w kategoriach teorii informacji. Okazało się jednak, że definicja ta jest przydatna w ramach samej teorii informacji.

Pojęcie entropii jest bardzo przydatne np. w dziedzinie kompresji danych. Entropię zerowego rzędu można obliczyć znając histogram ciągu symboli. Jest to iloczyn entropii i liczby znaków w ciągu. Osiągi kodowania Huffmana są często zbliżone do tej granicy, jednak lepszą efektywnością charakteryzuje się kodowanie arytmetyczne.

Przyjęcie modelu, w którym uwzględnia się kontekst znaku, pozwala zwykle na bardzo duże obniżenie entropii.

Przykład[edytuj]

W przypadku, gdy prawdopodobieństwa poszczególnych zdarzeń w zbiorze są równe, powyższy wzór można stosować w postaci uproszczonej:

H(X)=\log_2(n),

gdzie: n oznacza wielkość zbioru. Przykładowo dla zbioru 26 liter alfabetu (n= 26) entropia każdej z nich wynosi około 4,7, więc ośmioznakowy ciąg liter wykorzystywany np. jako hasło będzie miał entropię 37,6.

Moneta, która wyrzuca z takim samym prawdopodobieństwem orły i reszki, ma 1 bit entropii na rzut:

- p_{O} \log_2 p_{O} - p_{R} \log_2 p_{R} = - \frac 1 2 \log_2 \frac 1 2 - \frac 1 2 \log_2 \frac 1 2 = \frac 1 2 + \frac 1 2 = 1

Jednakże, jeśli moneta z jakieś przyczyny daje zafałszowany wynik (statystycznie częściej daje albo orła albo reszkę z określonym prawdopodobieństwem) mamy do czynienia z sytuacją, w której jest mniejsza niepewność (możemy łatwiej przewidzieć wynik). Objawia się to niższą entropią. Przykładowo, jeśli założymy, że z czterech rzutów wypadły 3 reszki to podstawiając do wzoru otrzymamy entropię równą 0,81. Idąc do ekstremum, przy czterech rzutach i 4 reszkach lub 4 orłach entropia osiąga minimum czyli 0, ponieważ nie ma niepewności (wiemy co wydarzy się w następnym rzucie). Przedstawiony przykład jest skrajnie uproszczony i próba czterech rzutów jest za mała, aby wyciągać jakieś statystyczne wnioski, ale dobrze obrazuje problem.

Ogólniej każde źródło dające N równie prawdopodobnych wyników ma log2 N bitów na symbol entropii:

- \sum_{i=1}^N \frac 1 N \log_2 \frac 1 N = - N \frac 1 N \log_2 \frac  1 N = -\log_2 \frac 1 N = \log_2 N

Ponadto inną miarą związaną z entropią Shannona jest entropia metryczna, która uwzględnia długość informacji (entropia dzielona jest przez długość wiadomości) i pozwala zmierzyć losowość informacji.

Zobacz też[edytuj]

Przypisy

  1. Damian Niwiński, Michał Strojnowski, Marcin Wojnarski: Teoria informacji – materiały Wydziału MIM UW. [dostęp 2010-01-21].

Linki zewnętrzne[edytuj]

  • kalkulator entropii - jak obliczyć i interpretować entropię dowolnej wiadomości
  • M. Berta, O. Fawzi, M. Tomamichel, On Variational Expressions for Quantum Relative Entropies, arxiv.org/1512.02615