Entropija (informatika)

Za druge pomene glej Entropija.

Entropija ali Shannonova entropija je v informatiki količina, ki meri negotovost izida 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 poznavanjem 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 manjša 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 x₁, x₂, x₃,…. x_n, 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 izid naslednjega meta).

Povezava med entropijo in številom meta kovanca.

Primer meta kovanca

Pri metu kovanca sta enako verjetna dva izida 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=x₀) = ½ (glava) oziroma p₀ in P(X=x₁) = ½ (številka) oziroma p₁ Iz tega dobimo po definiciji entropije zanjo vrednost H = 1 bit. To pomeni, da nam vsak izid meta kovanca da 1 bit informacije.

Primer je popolnoma drugačen, če kovanec ni pravilen (vsak izid poskusa ni enako verjeten). Recimo, da je verjetnost 60% (p ₀) da pade glava in 40% (p₁) da pade številka. Velja p ₀ + p ₁ = 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 izid 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č. izid meta kovanca nam ne bi dal nobene informacije, ker je izid 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 izida poskusa. Verjetnost vsakega izida pa je 0,25. Pri 20 zaporednih metih je verjetnost 20 bitov.

Zunanje povezave

• Entropija in informacija (rusko)
• Opis entropije v informatiki Arhivirano 2011-05-15 na Wayback Machine. (angleško)
• Informatika in entropija Arhivirano 2009-05-21 na Wayback Machine. (angleško)

Glej tudi

• klasična entropija
• statistična entropija