Matematyka Dyskretna
Zbigniew Domański
Instytut Matematyki i Informatyki, Politechnika Częstochowska
Elementy teorii informacji.
Wprowadzenie.
Teoria informacji wykorzystuje język i metody rachunku prawdopodobieństwa oraz
statystyki matematycznej do opisu transferu (transportu) informacji.
0 0 0
Przypiszmy każdemu zdarzeniu x1, x2, , xn prawdopodobieństwo p1 , p2 , , pn jego
wystÄ…pienia:
P0 (xi ) = pi0 , i = 1,2, , n.
Np. przy rzucaniu kostką, prawdopodobieństwo wyrzucenia i-tu oczek (i=1,2,& ,6)
może być przyjęte jako p=1/6.
Przypuśćmy, że kostka nie jest rzetelna i ktoś nas informuje, że liczby 3 i 6 pojawiają
się dwa razy częściej niż pozostałe liczby. Wtedy:
p3 = p6 = 1/ 4, oraz p1 = p2 = p4 = p5 = 1/ 8.
W powyższym przypadku uzyskaliśmy bezspornie informację, którą chcemy zmierzyć
ilościowo. Szukamy wielkości:
0 0 0
I (P, P0 ) = I ( p1, p2, , pn ; p1 , p2 , , pn )
pozwalającej nam ilościowo określić zysk informacji.
1
Postulat Laplace a: dwa zdarzenia należy traktować jako jednakowo prawdopodobne
jeśli nie mamy podstaw sądzić, że jest inaczej.
Taki wybór rozkładu prawdopodobieństwa jest równie arbitralny jak inne możliwe.
Przypuśćmy, że znamy wartości liczbowe jakie mogą wystąpić w serii realizacji
pewnego doświadczenia. Niech te liczby będą równe: x1, x2, , xn . Nie znamy jednak
prawdopodobieństw ich występowania. Jednak w trakcie obserwacji możemy określić
pewne charakterystyki liczbowe jak np. wartość przeciętną
i=6
X = pi xi
"
i=1
Przykład.
W rzucie nierzetelną kostką może to być np.
i=6
i = Å" pi = 4,5
"i
i=1
(dla kostki rzetelnej pi = 1/ 6, i = 3,5 ). Jaki jest rozkład {pi} dla tej kostki?
Na przykład taki:
p1 p2 P3 P4 P5 p6
0 0 0 0.5 0.5 0
Zasada Jaynes a: najbardziej rozsądny rozkład prawdopodobieństwa to taki, który
maksymalizuje funkcję zwaną funkcją nieokreśloności informacji ze względu na
wszystkie możliwe rozkłady prawdopodobieństwa P zgodne z obserwowanymi danymi.
Poniżej wyprowadzimy postać tej funkcji.
Nieokreśloność (nieoznaczoność) informacji.
Niech X = {x1, x2 , , xn} będzie zmienną losową, zaś P = {p1, p2 , , pn} jest
rozkładem prawdopodobieństwa tej zmiennej losowej.
Pmax reprezentuje maksimum informacji jakie można posiadać o wartościach
{x1, x2 , , xn}.
2
Przykład:
1 1 1
Å„Å‚ üÅ‚
P0 = , , , Pmax = {0,0, ,1k , ,0}- pewność.
òÅ‚ żł,
ółn n nþÅ‚
Symbol 1k oznacza, że na pozycji k jest 1.
Wprowadzimy funkcję będącą miarą wzrostu informacji. Niech
I(P, P0 ) = miara wzrostu informacji zawartej w P względem P0.
Jeśli aktualny stan wiadomości jest opisany przez P to brakująca informacja, tj.
nieokreśloność informacji definiujemy jako:
U (P, Pmax , P0 ) = I(Pmax , P0 ) - I (Pmax , P)
Minimalne wymagania nakładane na funkcję U:
1) U jest funkcją ciągłą prawdopodobieństw {p1, p2 , , pn},
2) Jeśli w wyniku pierwszego eksperymentu prawdopodobieństwa są równe zero
poczÄ…wszy od pewnego n1 < n oraz sÄ… jednakowe dla i < n1 tj.:
Å„Å‚ üÅ‚
1 1 1
P1 = , , , ,0, ,0żł,
òÅ‚
ółn1 n1 n1 þÅ‚
a według drugiego eksperymentu
Å„Å‚ üÅ‚
1 1 1 1
P2 = , , , , , ,0, ,0żł,
òÅ‚
ółn 2 n2 n2 n2 þÅ‚
gdzie n2 > n1 to U jest funkcjÄ… rosnÄ…cÄ… n: U (P2 , Pmax , P0 ) > U (P1, Pmax , P0 ) .
3
3) Nieokreśloność zdarzenia łącznego jest sumą niepewności zdarzeń składowych.
Wymagamy aby niepewność dwu zdarzeń niezależnych składających się na
zdarzenie łączne była sumą niepewności: I(P1P2 , P10P20 ) = I(P1, P10 ) + I(P2 , P20 ) .
Warunek ten zapisany dla funkcji U daje zależność:
U (P1P2 , P1max P2max , P10P20 ) = U (P1, P1max , P10 ) +U (P2, P2max , P20 )
W ramach teorii funkcji pokazuje się, że funkcja spełniająca warunki 1)-3) ma postać
(zarówno funkcja U jaki i funkcja I ):
n
ëÅ‚ öÅ‚
pi
ìÅ‚ ÷Å‚
I (P, P0 ) = k pi lnìÅ‚ ÷Å‚, k - staÅ‚a.
"
pi0
i=1
íÅ‚ Å‚Å‚
Jeśli przyjmiemy, że naszej sytuacji początkowej odpowiada rozkład:
1 1 1 1
Å„Å‚ üÅ‚
P0 = , , , pi0 = .
òÅ‚ żł,
n
ółn n nþÅ‚
zaś pełnej informacji odpowiada rozkład:
Pmax = {0,0, ,1l ,0, ,0}, pimax = ´il , l - ustalone
to
1
I (P, P0 ) = k pi (ln pi - ln pi0 ) =k pi ln pi - k( pi )ln
" " "
n
i i i
= k pi ln pi - k Å"1Å" ln n-1 = k pi ln pi + k ln n.
" "
i i
oraz
I (Pmax , P0 ) = k pimax ln pi + k ln n =0 + k ln n .
"
i`"l
4
Ostatecznie, funkcja nieokreśloności dla zadanych powyżej funkcji rozkładu P oraz P0
ma postać:
n
ëÅ‚ öÅ‚
pi
ìÅ‚ ÷Å‚
U (P; Pmax , P0 ) = -k pi lnìÅ‚ ÷Å‚,
"
pi0
i=1
íÅ‚ Å‚Å‚
Funkcję nieokreśloności informacji U często nazywamy entropią informacji.
1
Przyjmując jako stałą k = oraz wykorzystując własność funkcji logarytmicznej
ln 2
ln x / ln 2 = log2 x mamy następującą postać funkcji entropii informacji:
S = - pi log2 pi.
"
i
Wprowadziliśmy tu symbol S stosowany często dla oznaczenia entropii. Powyższa
postać funkcji entropii została podana końcem lat 40-tych przez Shanon a.
Przykład.
Zmienna losowa X = {0,1} ma rozkład prawdopodobieństwa P = {p,1- p}, gdzie
wartość 0 < p d" 1. Dla tej zmiennej funkcja entropii wynosi:
S(X ) = - p log2 p - (1- p)log2 (1- p) = S( p).
S(1/ 2) = 1bit.
S(p)
1
p
0
Na podstawie diagramu widzimy, że
0 0.5 1
entropia jest minimalna (równa 0!)
dla p=0 lub p=1 czyli w sytuacjach gdy mamy pewność (!) co do wartości przyjętej
przez zmiennÄ… losowÄ….
5
Przykład.
a , p = 1/ 2,
Å„Å‚
ôÅ‚b , p = 1/ 4,
ôÅ‚
X = S(X ) = 7 / 4bits .
òÅ‚
ôÅ‚c , p = 1/ 8,
ôÅ‚d , p = 1/ 8.
ół
Jeśli w tym przykładzie chcielibyśmy określić jaką wartość przyjęła zmienna losowa X
to musimy zadać serię pytań:
Pytanie Odpowiedz
Działanie
TAK KONIEC
1 X = a?
NIE Dalej
TAK KONIEC
2 X = b?
NIE Dalej
3 X = c? KONIEC
Przeciętnie musimy pytać około S(X) razy.
Twierdzenie. Minimalna liczba pytań koniecznych do określenia stanu zmiennej
losowej jest zawarta pomiędzy S(X) a S(X)+1.
Istnieje związek pomiędzy entropią informacji a efektywnością kodu. Związek ten
będziemy analizować w dalszej części naszego kursu.
6