Entropija (informatika)

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Entropija ali Shannonova entropija je v informatiki količina, ki meri negotovost izzida poskusa povezanega s slučajno spremenljivko. Ta vrsta entropije določa za pričakovano vrednost količino informacije, ki jo pridobimo takrat, ko izvedemo poskus, in dobimo njeno vrednost. Ta entropija je torej merilo za količino informacije, ki jo dobimo s poznavanje vrednosti slučajne spremenljivke.

Označimo jo s \mathbf{H}. Merimo pa jo v bitih.
Primer: met kovanca ima entropijo enega bita. Seveda v primeru, da kovanec ni pravilen, je negotovost večja in s tem tudi entropija nižja.

Uvedel jo je ameriški elektrotehnik in matematik Claude Elwood Shannon (1916 – 2001) v letu 1948.

Če je X slučajna spremenljivka, ki lahko zavzame diskretne vrednosti x1, x2, x3,…. xn, potem je Shannonova entropija zanjo enaka

H(X) = \sum_{i=1}^n {p(x_i)\,I(x_i)} = -\sum_{i=1}^n {p(x_i) \log_b p(x_i)},

kjer je b osnova logaritma (kadar je enota za entropijo bit, je b enak 2).

Entropija pri metu kovanca v odvisnosti od pravilnosti kovanca (Pr(X=1). Funkcija kaže maksimum. Največja je entropija pri verjetnosti 0,5. Popolnoma nepravilni kovanec (na obeh straneh glava ali številka) ima entropijo enako 0 (znan je izzid naslednjega meta).
Povezava med entropijo in številom meta kovanca.

Primer meta kovanca[uredi | uredi kodo]

Pri metu kovanca sta enako verjetna dva izzida glava in številka. Če je entropija merilo za negotovost, potem je očitno, da mora graf entropije imeti tudi maksimum.

Za posamezne poskuse velja P(X=x0) = ½ (glava) oziroma p0 in P(X=x1) = ½ (številka) oziroma p1 Iz tega dobimo po definiciji entropije zanjo vrednost H = 1 bit. To pomeni, da nam vsak izzid meta kovanca da 1 bit informacije.

Primer je popolnoma drugačen, če kovanec ni pravilen (vsak izzid poskusa ni enako verjeten). Recimo, da je verjetnost 60% (p 0) da pade glava in 40% (p1) da pade številka. Velja p 0 + p 1 = 1. Entropija se izračuna po zgornjem obrazcu na naslednji način

H = - ( p \cdot \log_2 p + q \cdot \log_2 q)

kjer je q enak 1-p. V tem primeru imamo večjo nesigurnost v izzid poskusa. S tem pa tudi zmanjšano entropijo oziroma vsak met kovanca nam da manj kot 1 bit informacije. Če pa bi imel kovanec na obeh straneh glavo (popolnoma nepravilni kovanec), bi bila entropija nič. Izzid meta kovanca nam ne bi dal nobene informacije, ker je izzid poskusa vedno znan oziroma enak.

Za vsako verjetnost lahko izračunamo entropijo iz zgornjega izraza. Problem nastopi pri vrednosti p = 0, kjer dobimo za entropijo vrednost nič. V ostalem delu pa je graf funkcije entropija/verjetnost simetrična.

Če vržemo kovanec dvakrat, imamo štiri možne izzida poskusa. Verjetnost vsakega izzida pa je 0,25. Pri 20 zaporednih metih je verjetnost 20 bitov.

Zunanje povezave[uredi | uredi kodo]

Glej tudi[uredi | uredi kodo]