entropia informacji.PDF

(87 KB) Pobierz
Microsoft Word - Elem-teor-nformacji.doc
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.
Przypiszmy ka demu zdarzeniu
x
,
x
,
3
,
x
prawdopodobie stwo
p
0
1
,
p
0
2
,
3
,
p
0
jego
1
2
n
n
wyst pienia:
P
0
(
x
)
=
p
0
,
i
=
1
2
3
,
n
.
i
i
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:
p
3
=
p
6
=
1
/
4
oraz
p
1
=
p
2
=
p
4
=
p
5
=
1
/
8
.
W powy szym przypadku uzyskali my bezspornie informacj , któr chcemy zmierzy
ilo ciowo. Szukamy wielko ci:
I
(
P
,
P
0
)
=
I
(
p
,
p
,
3
,
p
;
p
0
1
,
p
0
2
,
3
,
p
0
)
1
2
n
n
pozwalaj cej nam ilo ciowo okre li zysk informacji.
1
3247198.006.png
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:
x
,
x
2
,
3
,
x
n
. 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
=
p
i x
i
i
=
1
Przykład .
W rzucie nierzeteln kostk mo e to by np.
= Ã
i
=
6
i
i
×
p
i
=
4
=
1
(dla kostki rzetelnej
p i
=
1
/
6
i
=
3
). Jaki jest rozkład }
{
p dla tej kostki?
i
Na przykład taki:
p 1
p 2
P 3
P 4
P 5
p 6
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
=
{
x
1
,
x
2
,
3
,
x
n
}
b dzie zmienn losow , za
P
=
{
p
1
,
p
2
,
3
,
p
n
}
jest
rozkładem prawdopodobie stwa tej zmiennej losowej.
P reprezentuje maksimum informacji jakie mo na posiada o warto ciach
max
{
x
,
x
2
,
3
,
x
n
}
.
2
1
i
1
3247198.007.png 3247198.008.png
Przykład :
P
0
=
Ê
1
,
1
,
3
,
1
Ú
,
P
max
=
0
3
,
,
3
,
- pewno .
n
n
n
k
Symbol 1 k oznacza, e na pozycji k jest 1.
Wprowadzimy funkcj b d c miar wzrostu informacji . Niech
I
(
P
,
P
0
)
=
miara wzrostu informacji zawartej w P wzgl dem P 0 .
Je li aktualny stan wiadomo ci jest opisany przez P to brakuj ca informacja, tj.
nieokre lono informacji definiujemy jako:
U
(
P
,
P
max
,
P
0
)
=
I
(
P
max
,
P
0
)
-
I
(
P
max
,
P
)
Minimalne wymagania nakładane na funkcj U :
1) U jest funkcj ci gł prawdopodobie stw
{
p
1
,
p
2
,
3
,
p
n
}
,
2) Je li w wyniku pierwszego eksperymentu prawdopodobie stwa s równe zero
pocz wszy od pewnego
n <
1
n
oraz s jednakowe dla
i < tj.:
n
P
1
=
Ê
1
,
1
,
3 n
,
1
,
3
,
0
Ú
,
n
n
1
1
1
a według drugiego eksperymentu
P
2
=
Ê
1
,
1
,
3
,
1
,
3
,
1
,
0
3
,
Ú
,
n
n
n
n
2
2
2
2
gdzie
n > to U jest funkcj rosn c n :
n
U
(
P
2
,
P
max
,
P
0
)
>
U
(
P
1
,
P
max
,
P
0
)
.
2
1
3
{
3247198.009.png 3247198.001.png 3247198.002.png
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
(
P
P
,
P
0
P
0
2
)
=
I
(
P
,
P
0
)
+
I
(
P
,
P
0
)
.
1
2
1
1
1
2
2
Warunek ten zapisany dla funkcji U daje zale no :
U
(
P
P
,
P
max
P
max
,
P
0
P
0
)
=
U
(
P
,
P
max
,
P
0
)
+
U
(
P
,
P
max
2
,
P
0
)
1
2
1
2
1
2
1
1
1
2
2
W ramach teorii funkcji pokazuje si , e funkcja spełniaj ca warunki 1)-3) ma posta
(zarówno funkcja U jaki i funkcja I ):
I
(
P
,
P
0
)
=
k
à =
n
p
ln
Å
Æ
p
i
Õ
Ö
,
k
-
stała.
i
p
0
i
1
i
Je li przyjmiemy, e naszej sytuacji pocz tkowej odpowiada rozkład:
P
0
=
Ê
1
,
1
,
3
,
1
Ú
,
p
0
=
1
.
n
n
n
i
n
za pełnej informacji odpowiada rozkład:
P
max
=
{
0
0
3
,
,
3
,
0
}
,
p
max
=
d
,
l
-
ustalone
l
i
il
to
I
(
P
,
P
0
)
=
k
Ã
p
(ln
p
-
ln
p
0
)
=
à Ã
p
ln
p
-
k
(
p
)
ln
1
i
i
i
i
i
i
n
i
i
i
Ã
Ã
=
k
p
ln
p
-
k
×
1
×
ln
n
-
=
k
p
ln
p
+
k
ln
n
.
i
i
i
i
i
i
oraz
I
(
P
max
,
P
0
)
= Ã ¹
k
p
max
ln
p
+
k
ln
n
=
0
+
k
ln
n
.
i
i
i
l
4
Ä
Ô
k
1
3247198.003.png 3247198.004.png
 
Ostatecznie, funkcja nieokre lono ci dla zadanych powy ej funkcji rozkładu P oraz P 0
ma posta :
à =
n
Ä
p
Ô
U
(
P
;
P
max
,
P
0
)
=
-
k
p
ln
Å
Æ
i
Õ
Ö
,
i
p
0
i
1
i
Funkcj nieokre lono ci informacji U cz sto nazywamy entropi informacji .
Przyjmuj c jako stał
k
=
1
oraz wykorzystuj c własno funkcji logarytmicznej
ln
2
ln
x
/
ln
2
=
log
2
x
mamy nast puj c posta funkcji entropii informacji :
S
=
-
Ã
p
i
log 2
p
i
.
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
=
{
ma rozkład prawdopodobie stwa
P
=
{
p
,
-
p
, gdzie
warto
0
< p
£
1
. Dla tej zmiennej funkcja entropii wynosi:
S
(
X
)
=
-
p
log
2
p
-
(
-
p
)
log
2
(
-
p
)
=
S
(
p
).
S
(
/
2
)
=
1
bit
.
S(p)
1
0
p
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
}
3247198.005.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin