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 se jo pridobi tedaj, ko se izvede poskus, in se dobi njeno vrednost. Ta entropija je torej merilo za količino informacije, ki se jo dobi s poznavanjem vrednosti slučajne spremenljivke.

Označi se jo s $\mathbf {H} \!\,$. Meri pa se jo v bitih.

Zgled: 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.

Zgled 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 se dobi po definiciji entropije zanjo vrednost H = 1 bit. To pomeni, da vsak izid meta kovanca da 1 bit informacije.

Zgked je popolnoma drugačen, če kovanec ni pravilen (vsak izid poskusa ni enako verjeten). Naj 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 je večja nesigurnost v izidu poskusa. S tem pa je tudi zmanjšana entropijo oziroma vsak met kovanca 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 se lahko izračuna entropijo iz zgornjega izraza. Problem nastopi pri vrednosti p = 0, kjer se dobi za entropijo vrednost nič. V preostalem delu pa je graf funkcije entropija/verjetnost simetrična.

Če se vrže kovanec dvakrat, so štiri možni izidi 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