entropia informacji, Matematyka dyskretna
[ Pobierz całość w formacie PDF ]
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
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
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
{
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
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
}
[ Pobierz całość w formacie PDF ]