Różnorodność i entropia

Różnorodność układu to liczba możliwych (do obserwacji) stanów układu.

r - będzie oznaczało różnorodność

n - będzie oznaczało liczbę elementów

k - będzie oznaczało liczbę stanów elementu

Musimy wziąć oczywiście pod uwagę rozróżnialność elementów.

Naty, dity, hartleye i inne

Nat (nit)

Miarą różnorodności jest logarytm naturalny (przy podstawie e) z liczby stanów.

r=lnW

gdzie 'r' oznacza różnorodność, a 'W' oznacza liczbę rozróżnialnych stanów.

Jeżeli liczba stanów wynosi 5 to: natów.

Dit (ban, hartley)

Jeżeli podzielimy to otrzymamy logarytm dziesiętny z x.

Jeżeli liczba stanów wynosi 5 to ditów.

Bit (shannon)

Jeżeli podzielimy to otrzymamy logarytm z x przy podstawie 2.

Jeżeli liczba stanów wynosi 5 to bitów.

Bit jest najczęściej używaną jednostką różnorodności.

Przeliczanie

z \ na	nat	dit	bit
nat	-
dit		-
bit			-

Trochę obliczeń

Obliczenia przeprowadzamy w bitach.

Różnorodność płci

n = 1 (płeć). Elementy są rozróżnialne.

k = 2 (męska, żeńska). Stany są rozróżnialne.

Wynik oznacza, że jeżeli wybierzemy na ślepo jakąś osobę z tłumu, to żeby opisać jej płeć (rozwiać swoją wątpliwość) potrzebujemy uzyskać odpowiedż na tylko jedno pytanie: "Czy to kobieta? (zakładam, że nie trafiliśmy na obojnaka - wtedy k byłoby inne). Odpowiedź będzie 'tak' albo 'nie', czyli '0' albo '1'.

Różnorodność kart

Posługujemy się 52-kartową talią. Wybieramy 1 kartę.

n = 1 (karta). Elementy są rozróżnialne.

k = 52 (kolory × figury). Stany są odróżnialne.

Odpowiedź zaokrąglamy w górę, czyli otrzymujemy 6. Aby opisać jaką kartę wybraliśmy potrzebujemy 6 pytań. Możemy to sobie wyobrazić tak: karty są ponumerowane od 1 do 52. Załóżmy, że wybrana karta to nr 15. Pytania będą brzmiały:

• Czt karta jest w zakresie 1-26? Tak.
• Czy karta jest w zakresie 1-13? Nie.
• Czy karta jest w zakresie 14-20? Tak
• Czy karta jest w zakresie 14-17? Tak
• Czy karta jest w zakresie 14-15? Tak
• Czy karta to 14? Nie.

Możemy to określić prościej. Do zapisania liczby 52 w postaci binarnej potrzeba 6 bitów:

Rzut dwiema monetami równocześnie

n = 2 (monety). Elementy nierozróżnialne.

k = 2 (orzeł, reszka). Elementy rozróżnialne.

W tym przypadku układ OR jest nierozróżnialny od układu RO, gdyż nic nie wiemy o kolejności wypadnięcia. Gdybyśmy rzucali monetami po kolei i kolejność była dla nas ważna musielibyśmy przyjąć, że monety (ze względu na kolejność rzutu) są odróżnialne. Wtedy oczywiście byłyby 2² = 4 możliwości.

Potrzebujemy odpowiedzi na dwa pytania: 1) pierwsza moneta?, 2) orzeł?

Rzut 2 kostkami do gry jednocześnie

n = 2 (kostka). Elementy nierozróżnialne.

k = 6 (jedna ze stron kostki). Elementy rozróżnialne.

Przyjmujemy tu, że nic nie wiemy o kolejności kostek, czy układ (6, 1) jest nieodróżnialny od układu (1, 6). Jeżeli rzucamy kośćmi kolejno i kolejność jest ważna, to musimy kostki uznać za rozróżnialne (ze względu na kolejność rzutu). Wtedy oczywiście będziemy mieli 6² = 36 możliwych wyników.

Do zapisania liczby 21 potrzebujemy 5 bitów, czyli do uzyskania odpowiedzi jaki jest wynik potrzebujemy 5 pytań.

Modelki

Jeżeli będziemy mieli modelki o:

• 7 kolorach oczu
• 4 kolorach skóry
• 8 fryzurach

to różnorodność możemy obliczyć:

n = 1 (modelka). Elementy odróżnialne.

Mamy 3 niezależne od siebie stany modelki (stany odróżnialne)

k₁ = 7¹ (kolor oczu)

k₂ = 4¹ (kolor skóry)

k₃ = 8¹ (rodzaj fryzury)

Prawdopodobieństwo

Sygnalizator drogowy

n = 3 (lampa czerwona, lampa żółta, lampa zielona). Elementy odróżnialne.

k = 2 (zapalony, zgaszony). Stany odróżnialne.

Możliwe stany 'zapalenia':

• żadne
• zielone
• czerwone
• żółte
• zielone, czerwone
• zielone, żółte
• czerwone, żółte
• czerwone, zielone, żółte

W praktyce używa się tylko czterech:

• zielone
• czerwone
• żółte
• zielone, żółte

Różnorodność pełna

Różnorodność wykorzystywana

Powyższe obliczenia są słuszne pod warunkiem, że prawdopodobieństwa wystąpienia (czas trwania światła w danym kolorze) są sobie równe. W tym wypadku prawdopodobieństwem jest prawdopodobieństwo stanu, jaki zastanie kierowca, gdy zobaczy sygnalizator. Jeżeli każdy z 4 czasów jest równy, prawdopodobieństwa stanów są równe, a nasze obliczenia są właściwe.

Nie jest to prawdą przy np. sygnalizatorze.

Załóżmy, że czas 'zapalenia' wynosi:

• zielone - 25s
• zielone, żółte - 5s
• czerwone- 25s
• żółte - 5s

Przy takim układzie (prawdopodobieństwa nie są równe) nasze obliczenia nie są prawdziwe. Musimy użyć innego wzoru.

Entropia informatyczna

Gdy prawdopodobieństwa stanów nie są jednakowe wówczas używamy wzoru

gdzie:

S - oznacza entropię

a - jest pewną stałą, którą dla naszych celów przyjmujemy za równą 1

n - jest liczbą rozpoznawalnych stanów, czyli w tym przypadku 4

Σ - jest znakiem sumy elementów od i = 1 do i = n. W naszym przypadku zsumowane zostaną cztery elementy.

p_i - jest prawdopodobieństwem wystąpienia i-tego stanu.

r - oznacza podstawę logarytmów i zwykle jest to '2'.

r = 2 (obliczenia w bitach) albo r = 10 (obliczenia w ditach)

Obliczamy prawdopodobieństwa:

Obliczenia przeprowadzamy w tabelce:

Obliczenie przebiega następująco:

stan	prawdopodobieństwo stanu p
zielone	0.42	-0.5256
zielone z żółtym	0.08	-0.2915
czerwone	0.42	-0.5256
żółte	0.08	-0.2915
Suma	1.00	-1.6342

Aby uniknąć liczb ujemnych można użyć wzoru w wersji:

Obliczenia wyglądają następująco:

Możemy oczywiście obliczyć S dla równych prawdopodobieństw:

stan	prawdopodobieństwo stanu p
zielone	0.25	-0.5
zielone z żółtym	0.25	-0.5
czerwone	0.25	-0.5
żółte	0.25	-0.5
Suma	1.00	-2.0

Potwierdza to nasz wcześniejszy wynik. Uproszczony wzór na różnorodność możemy stosować gdy prawdopodobieństwa stanów systemu są równe

Oczywiście, niewidomy kierowca potrzebuje 2 pytań, aby dowiedzieć się jakie światło pali się na sygnalizatorze.

Czarne i białe kule

Mamy 8 kul, w tym 4 białe i 4 czarne. Jaka jest różnorodność układu?

Gdy liczyliśmy różnorodność dla monet, kart, kostek, modelek, czy sygnalizatora drogowego, to wiedzieliśmy wszystko o elementach i ich możliwych stanach. Gdy napotykamy np. kule, nic nie wiemy ani o elementach, ani o ich stanach.

Czy mamy osiem elementów (kul) o 2 możliwych stanach (biały czarny), czy mamy dwa układy po cztery elementy, w których każdy element ma 1 możliwy stan?

A może jest to osiem niezależnych kul, z których każda ma inną liczbę możliwych stanów (kolorów),a tylko przypadkowo znajdują się akurat w podobnych stanach?

Oczywiście nie wiemy. Możemy zatem policzyć entropię (różnorodność) dla aktualnego stanu układu.

Wynik wskazuje wyraźnie na to, że ponieważ mamy tylko 1 pytanie mamy do czynienia z dwoma niezależnymi układami po 4 kule i wybieram jeden z tych układów: czarne, czy białe?

Czarne i białe kule 2

Mamy 9 kul, w tym 5 białych i 4 czarne. Jaka jest różnorodność układu?

Wniosek jest podobny do podanego nieco wyżej. Wybieramy między jednym, a drugim układem.

Entropia wiadomości

Załóżmy, że mamy wiadomość:

To jest wiadomość testowa

Nasza wiadomość ma długość n = 25 znaków razem ze spacjami

Prawdopodobieństwo na znak = 1.0/25=0.04. Niektóre litery powtarzają się. Wartości dla nich dodajemy i otrzymujemy tabelkę:

Znak	p
spacja	0.12	-0.3671
a	0.08	-0.2915
d	0.04	-0.1858
e	0.08	-0.2915
i	0.04	-0.1858
j	0.04	-0.1858
m	0.04	-0.1858
o	0.16	-0.423
s	0.08	-0.2915
t	0.16	-0.423
w	0.08	-0.2915
ć	0.04	-0.1858
ś	0.04	-0.1858
Suma	1.0	-3.4937

S = -1*3.4937 = 3.4937 bitów/znak

Ponieważ liczba bitów jest zawsze liczbą całkowitą wynik zawsze zaokrąglamy w gorę, czyli S = 4.

Ta wartość oznacza, że jeśli chcielibyśmy zakodować wiadomość symbolami w systemie dwójkowym to na każdy znak potrzeba 4 bitów, a do zakodowania wiadomości 4 x 25 = 100 bitów.

Entropia oznacza też, że gdybyśmy zadawali pytania 'tak - nie' to potrzebowalibyśmy 4 pytań, aby dowiedzieć się o dany znak w wiadomości (zakładając, że jest ktoś kto zna odpowiedź :-)):

Entropia metryczna

gdzie:

L jest liczbą znaków w wiadomości

Dzięki temu można porównywać ze sobą wiadomości o różnej długości.

Według informacji na stronie Wikipedii (hasło: 'Entropia metryczna') zachodzi co następuje:

• Entropia metryczna spada do zera przy jednolitym ciągu znaków w wiadomości i rośnie monotonicznie wraz ze wzrostem różnorodności wiadomości osiągając wartość 1 dla wiadomości maksymalnie zróżnicowanej.

Jest to nieprawdą. Entropia metryczna faktycznie zachowuje się tak:

Polecenia programu

		System.out.println(InfoUtil.messageEntropy2("a") / 1.0);
		System.out.println(InfoUtil.messageEntropy2("aaaaa") / 5.0);
		System.out.println(InfoUtil.messageEntropy2("aaaaaaaaaa") / 10.0);
		System.out.println("------------------");
		System.out.println(InfoUtil.messageEntropy2("ab") / 2.0);
		System.out.println(InfoUtil.messageEntropy2("abc") / 3.0);
		System.out.println(InfoUtil.messageEntropy2("abcd") / 4.0);
		System.out.println(InfoUtil.messageEntropy2("abcde") / 5.0);
		System.out.println(InfoUtil.messageEntropy2("abcdefghij") / 10.0);
		System.out.println(InfoUtil.messageEntropy2("abcdefghijklmnopqrstuvwxyz") / 26.0);
		System.out.println(InfoUtil.messageEntropy2("aąbcćdeęfghijklłmnńoópqrsśtuvwxyzżź") / 35.0);
		System.out.println("------------------");
		System.out.println(InfoUtil.messageEntropy2("ababbbabab") / 10.0);//2 znaki
		System.out.println(InfoUtil.messageEntropy2("abcbcaabcb") / 10.0);//3 znaki
		System.out.println(InfoUtil.messageEntropy2("abcdeabcde") / 10.0);//5 znaków
		System.out.println(InfoUtil.messageEntropy2("abcdefgcde") / 10.0);//7 znaków
		System.out.println(InfoUtil.messageEntropy2("abcdefghij") / 10.0);//10 znaków
		System.out.println("------------------");
		System.out.println(InfoUtil.messageEntropy2("ababbbababababa") / 15.0);//2 znaki
		System.out.println(InfoUtil.messageEntropy2("abcbcaabcbcbcba") / 15.0);//3 znaki
		System.out.println(InfoUtil.messageEntropy2("abcdeabcdeabcce") / 15.0);//5 znaków
		System.out.println(InfoUtil.messageEntropy2("abcdefgcdeedfga") / 15.0);//7 znaków
		System.out.println(InfoUtil.messageEntropy2("abcdefghijhiagc") / 15.0);//10 znaków
		System.out.println(InfoUtil.messageEntropy2("abcdefghijklmno") / 15.0);//15 znaków

Wynik na konsoli

-0.0
-0.0
-0.0
------------------
0.5
0.5283208335737187
0.5
0.46438561897747244
0.3321928094887362
0.1807861430054266
0.14655094334128468
------------------
0.09709505944546684
0.15709505944546684
0.23219280948873622
0.2721928094887362
0.3321928094887362
------------------
0.06645277546544244
0.10437308202384014
0.15261642856727722
0.18263815079911486
0.2160149285961235
0.2604593730405679

Częstość polskich liter

Jeśli chcesz możesz w ramach ćwiczeń policzyć entropię dla polskiego alfabetu.

Entropia indywidualna

W powyższej tabeli częstość (prawdopodobieństwo) dla pospolitej litery 'a' wynosi 0.0891, a częstość (prawdopodobieństwo) dla rzadszej litery 'ą' wynosi 0.0099.

Możemy obliczyć entropię indywidualną zdarzenia, nazywaną również autoinformacją stowarzyszoną ze zdarzeniem:

Dla litery 'a':

Dla litery 'ą':

Im bardziej nieprawdopodobne zdarzenie tym większą informację niesie.

A oto zachowanie funkcji dla różnych prawdopodobieństw zdarzenia:

0.1 	3.32
0.2 	2.32
0.3 	1.74
0.4 	1.32
0.5 	1.0
0.6 	0.74
0.7 	0.51
0.8 	0.32
0.9 	0.15
1.0 	0.00

Nieoczekiwane zdarzenia przekazują więcej informacji niż oczekiwane.

Układy biologiczne i łańcuchy Markowa

Dany stan układu biologicznego może przechodzić w inny stan układu z pewnym prawdopodobieństwem. Prawdopodobieństwo określa częstość przejścia.

Jeśli mamy trzy możliwe stany, które przechodzą w inne stany z pewnym prawdopodobieństwem to prawdopodobieństwa przejść możemy umieścić w macierzy przejść o wymiarze 3 x 3. Jeżeli ta macierz jest stała, czyli prawdopodobieństwa nie zmieniają się w czasie to transformacja jest zamknięta i jednoznaczna, czyli zdeterminowana.

Jeżeli macierz prawdopodobieństw zmienia się w czasie to mamy do czynienia z transformacją stochastyczną.

W naszej populacji owadów* owad może znajdować się na brzegu (stan B), w wodzie (stan W), lub w norce (stan N). Przyrodnik obserwujący układ zaobserwował, że owady motywowane nieokreślonymi czynnikami zmieniają swoje położenie (stan) i że prawdopodobieństwa przejść są stałe. Te prawdopodobieństwa można umieścić w macierzy prawdopodobieństw ( z macierzami możesz się zapoznać w rozdziale poświęconym macierzom). Tutaj macierz zastąpiliśmy tabelką:

Tabele należy czytać kolumnami: dla kolumny B prawdopodobieństwo p pozostania na brzegu wynosi 0.25, przejścia do wody wynosi 0.75, a wejścia do norki wynosi 0, itd. Suma prawdopodobieństw w kolumnie wynosi 1.0.

Jeżeli uwzględnimy odpowiednio długi okres czasu i okaże się, że prawdopodobieństwo przejścia jest stałe, to taka kolejność stanów i przejść jest nazywana łańcuchem Markowa.

Na podstawie tej macierzy możemy określić prawdopodobne zachowania układu.

Znając macierz prawdopodobieństw, nie znając wcześniejszego stanu danego układu, możemy określić prawdopodobne zachowania tego systemu. Jest to system bez pamięci lub bez historii.

Przy odpowiedniej liczebności pomimo, że zachowanie pojedynczego owada jest określone jedynie z pewnym prawdopodobieństwem, to system jako całość jest niezależny od przypadku i jest systemem zdeterminowanym.

Policzmy entropię dla każdej kolumny:

Teraz obliczamy średnią częstość (WCR) występowania stanów B, W i N. W tym celu sumujemy rzędy i dzielimy przez liczbę kolumn.

Te średnie wartości oznaczają przeciętną częstość owadów w danym miejscu, a więc i średni czas pobytu w tym miejscu.

Następnie obliczamy średnią entropię systemu:

Entropia systemu, a zatem i informacja zawarta w naszym systemie owadów wynosi 0.843 bita na stan.

Uwagi końcowe