Entropia (informazio-teoria)

thumb|Bi entropia-bit
Informazio-teoriaren alorrean **entropia**k, **informazio-entropia** eta **Shannonen entropia** (Claude E. Shannon-en omenez) izenez ere ezagutua, informazio iturri baten ziurgabetasuna neurtzen du.

Entropia kontzeptua termodinamikan, mekanika estatistikoan eta informazio-teorian erabiltzen da. Kasu guztietan entropia «desordenaren neurri» edo «konbinazio jakin batzuen berezitasun» moduan ulertzen da. Ziurgabetasunaren neurri bat dela edo edozein prozesutan ziurgabetasun hori mugatzeko, murrizteko edo ezabatzeko behar den informazioa dela uler daiteke. Kontua da, informazioaren eta entropiaren kontzeptuek oso harreman estua dutela, nahiz eta hortaz konturatzeko mekanika estatistikoaren eta informazio-teoriaren arloetan lan handia egin behar izan zen.

## Sarrera 
Informazio-teoriaren oinarrizko ideia honakoa da: gai bati buruz zenbat eta gehiago jakin, orduan eta informazio berri gutxiago lortuko da. Gertakari bat emateko probabilitatea handia bada, gertatzen denean ez da harrigarria eta, beraz, gertatu izanak informazio berri gutxi ematen du. Gertatzeko probabilitatea txikia bada, ordea, gertakizuna jazo izana nabarmenki adierazgarriagoa da. Hortaz, informazio kantitatea gertakarien probabilitatearen alderantzizkoa (1/p) adierazten duen funtzio gorakorra da. Gertakari bat baino gehiago badago, gertaeretako batek emango lukeen batezbesteko informazio kantitatea neurtzen du entropiak. Adibidez, dado bat jaurtitzeak txanpon bat jaurtitzeak baino entropia handiagoa duela esan nahi du horrek, dadoa jaurtitzean eman daitezkeen gertakariek txanpona jaurtitzean eman daitezkeenek baino probabilitate txikiago baitute.

Beraz, entropia egoera baten *ziurgabetasun-neurria* edo *batezbesteko informazio kantitatea* da. Kontzeptu horiek ulertzeko adibide gisa, har dezagun bozketa politikoarena. Bozketak egiten dira haien emaitza aldez aurretik ezagutzen ez delako eta, ondorioz, bozketen emaitzek *informazio* berria emango dute. Beste era batera esanda: *a priori*, bozketaren entropia altua da. Bozketa egin eta handik gutxira bozketa bera errepikatuko balitz, lehenengo bozketaren emaitza dagoeneko ezaguna denez, bigarrenean lortuko den emaitza iragarri ahalko litzateke eta emaitza berriak ez luke informazio gehigarri askorik emango; kasu horretan, bigarren bozketaren entropia, *a priori*, txikia da (aurrekoarekin alderatuz).

Beste adibide bat txanponaren jaurtiketarena da. Aurpegia eta gurutzea lortzeko probabilitateak berdinak direla suposatuz, txanpona jaurtitzearen entropiak izan dezakeen balio maximoa du. Aldez aurretik jaurtiketaren emaitza zein izango den iragartzeko modurik ez dagoelako gertatzen da hori. Iragarpen bat eman beharko balitz, aurpegia aterako dela esan genezake adibidez, asmatzeko probabilitatea 1/2ekoa izanik. Horrelako txanpon jaurtiketa batean entropiaren balioa 1 da, gertatzeko probabilitate bera duten bi egoera daudelako (aurpegia, gurutzea). Txanponaren bi aldeetan aurpegia egongo balitz, ordea, entropiaren balioa 0 izango litzateke, errorerik gabe iragarri ahal izango litzatekeelako txanpona jaurti eta emaitza aurpegia izango dela. Horrela, probabilitate bereko gertakari bitarren Shannon-en entropia \log_22=1 da. Modu berean, probabilitate bereko hiru aukera egongo balira, Shannon-en entropia \log_23 izango litzateke.

## Definizio formala 
Demagun zorizko aldagai baten hasierako indeterminazio maila k dela (k egoera posible dituela, alegia). Demagun, gainera, egoera guztiak probabilitate berekoak direla. Hori hala izanik, konbinazio jakin bat gertatzeko probabilitatea p=1/k izango da. Beraz, honakoa idatz daiteke:

\log_2(k)= \log_2[1/(1/k)]= \log_2(1/p) = \underbrace{\log_2(1)}_{= 0}-\log_2(p) =- \log_2(p)

Egoera guztiak probabilitate berekoak ez badira, hau da, i. egoera p_i probabilitatez gertatzen bada, informazio-kantitateen batuketa haztatuaren bidez kalkulatuko da entropia:

H=-p_1 \log_2(p_1)-p_2 \log_2(p_2)-....-p_k \log_2(p_k)=- \sum_{i=1}^{k}p_i \log_2(p_i)

Beraz, X zoriozko aldagaiaren entropia, H(X) notazioaren bidez adierazten da eta aldagaiaren egoera desberdinei dagokien informazio-kantitatearen batezbesteko balio haztatua da.

H(X)=- \sum_{i=1}^{k}p(x_i) \log_2 p(x_i)

Horrela definitutako entropiak X zoriozko aldagaiaren ziurgabetasun mailaren neurria ematen du eta ondorioz, informazio-kantitatea adierazten du.

### Adibidea 
Har dezagun txanpon baten jaurtiketaren adibidea. Txanpona jaurtitzean aurpegia ala gurutzea lortzen dira; txanpona zintzoa bada, bi egoerek probabilitate bera dute eta beraz, jaurtiketaren emaitzaren entropia maximoa da. Ziurgabetasun maximoko egoera da, hurrengo jaurtiketaren emaitza aurreikustea ia ezinezkoa delako.
[thumb|Xren entropia [Bernoulli saiakuntza|Bernoulli-ren saiakuntzan. (Xak 0 edo 1 balioak har ditzakeen ausazko saiakuntza). Entropia P(X=1) probabilitatearen araberakoa da. P(X=1)=0,5 denean, emaitza guztiek probabilitate bera dute, beraz, ziurgabetasun-maila altua da eta entropia maximoa.]]

\begin{align}
\Eta(X) &= -\sum_{i=1}^n {\mathrm{p}(x_i) \log_2 \mathrm{p}(x_i)} 
\\ &= -\sum_{i=1}^2 {\frac{1}{2}\log_2{\frac{1}{2}}} 
\\ &= -\sum_{i=1}^2 {\frac{1}{2} \cdot (-1)} = 1
\end{align}

Baina txanpona ez bada zintzoa, hau da, aurpegia lortzeko probabilitatea (p) eta gurutzea lortzekoa (q) desberdinak badira, (p≠q), orduan Bernoulli-ren prozesu baten bidez eredutu ahal izango dugu. Kasu horretan, ziurgabetasuna txikiagoa da, txanpona jaurtitzen den aldiero txanponaren alde bat lortzearen probabilitatea bestea lortzearena baino handiagoa delako. Ziurgabetasuna murriztean entropia ere murrizten da. Adibidez, p=0,7 denean:

\begin{align}
\Eta(X) &=  - p \log_2 (p) - q \log_2 (q)
\\ &= - 0.7 \log_2 (0.7) - 0.3 \log_2 (0.3) 
\\ &\approx - 0.7 \cdot (-0.515) - 0.3 \cdot (-1.737) 
\\ &= 0.8816 

### Elkarrekiko informazioa 
Entropia elkarrekiko informazioaren kasu berezi bat bezala uler daiteke. Zorizko bi aldagairen elkarrekiko informazioa I(X, Y) notazioaz adierazten da eta bi aldagaien elkarrekiko mendekotasuna neurtzen du. Zorizko Y aldagai baten balioa ezagutzeak X aldagaiaren ziurgabetasun maila edo **entropia** zenbat murrizten duen neurtzen du. Beraz, zera ondoriozta daiteke: X eta Y berdinak badira, orduan I(X; X) = H(X) betetzen da.

## Propietateak 
Entropiak honako propietateak betetzen ditu:

# Ez da negatiboa. ***p_i***probabilitate bat denez, 0  betetzen da. Hortaz, \log_2p_i \le 0 eta ondorioz -\log_2 p_i \ge 0 betetzen dela ziurta daiteke.
# H \le \log_a (n). Hau da, H entropiak goi-bornea du (maximoa denean) eta ez du informazio-galerarik suposatzen.
# Izan bitez {A1, …, An} emaitza posibleak eta p1, …, pn probabilitateak dituen prozesu bat. H(p_1,\dots, p_n)\, funtzioa maximoa da p_1 = \dots = p_n = 1/n\, betetzen denean; emaitza guztiak probabilitate berberaz gerta daitezkeenean ematen da ziurgabetasunaren maila maximoa.
# Izan bitez {A1, …, An} emaitza posibleak eta p1, …, pn probabilitateak dituen prozesu bat. H(p_1,\dots, p_n)\,funtzioak 0 balioa du p_i = 0 bada i-ren edozein baliorako klase jakin baterako izan ezik, non p_j = 0. Modu intuitiboan pentsa daiteke egoera batek edo gehiagok probabilitate altua dutenean entropia nabarmenki jaisten dela, ziurgabetasuna txikitzen delako.

## Kodetzaile optimoa 
**Kodetzaile optimoa** mezu bat kodetzeko bit kopuru minimoa erabiltzen duena da. Kodetzaile optimo batek kode laburrak erabiliko ditu maiztasun handiz agertzen diren mezuak kodetzeko eta gutxitan agertzen diren mezuetarako kode luzeagoak erabiliko dira. Horrela, memoria gunearen errendimendua optimizatzen da eta sistema eraginkorra da, mezua adierazteko behar den bit kopuruari dagokionez.

Adibidez, Morse kodea kodetzaile optimo bat ez izan arren, printzipio horretan oinarritzen da, ingelesez maiztasun handiagoz agertzen diren hizkiei kode laburragoak esleituz.

Beste adibide bat Huffmanen algoritmoa da. Algoritmo horrek informazioa trinkotzen du **kodetzaile optimoan** oinarrituz. Lehenik, karaktereen agerpen-maiztasuna kalkulatzen du, ondoren kodetzaile optimoa bilatzen du zuhaitz bitarren bidez. Datu-konpresio teknika batzuk sinboloen probabilitateak kalkulatu ordez sinbolo-sekuentzien probabilitateak kalkulatzen dituzte, datuen konpresio maila altuagoa lortzeko.

Kodetzaile optimo bat eraiki daiteke X zorizko aldagai baten entropian oinarrituz. Logaritmoa oinarri bitarrean erabiltzen bada, mezu bat kodetzeko behar den **bit kopuruaren batezbestekoa** lortzen da. Horrela, Shannon-ek analitikoki frogatu zuenez, mezu baten konpresioa sinboloak banaka hartuz eta informazio galerarik gabe zenbat konprima daitekeen kalkula daiteke (muga maximoa). Konpresioaren muga (bitetan neurtua), entropiaren eta mezuaren luzeraren biderkadura izango da.

H(X) = -\sum_{i}p(x_i) \log_2 p(x_i) = \sum_{i}-p(x_i)\log_2p(x_i) = 
=\sum_{i}p(x_i)[log_2(1)-\log_2(p(x_i))] = \sum_{x}p(x) \log_2(1/p(x))

Beraz, X zorizko aldagai diskretu baten x_i sinbolo espezifiko batek ematen duen informazioa, bitetan neurtua, horrela definitzen da:

I(x_i) = \log_2{\frac{1}{p(x_i)}}=-\log_2{p(x_i)}

### Adibidea 
Demagun mezu batek hiru egora izan ditzakeela. M1 egoeraren probabilitatea %50-ekoa da, M2 egoeraren probabilitatea %25-ekoa da eta M3 egoerarena %25-ekoa.

M1-erako \log_2 [1/p(M_1)]=\log_2 2= 1 lortuko dugu.

M2-erako \log_2 [1/p(M_2)]=\log_2 4= 2 lortuko dugu.

M3-erako \log_2 [1/p(M_2)]=\log_2 4= 2 lortuko dugu.

Beraz, kodetzaile optimoak bit bat erabiliko du M1 transmititzeko, eta bi bit beharko dira M2 eta M3 kodetzeko. Adibidez, M1 kodetzeko "0" erabil dezakegu, M2 kodetzeko 10 eta M3rako 11. Hala egingo bagenu, M1M2M1M1M3M1M2M3 mezua “010001101011” moduan kodetuko genuke, 12 bit erabiliz. Entropiaren balioa honakoa izango litzateke:

H(X)= 1/2 \log_2(2)+1/4 \log_2(4) + 1/4 \log_2(4)=1,5

Zera ondoriozta daiteke: kodetzaile optimoak 1,5 bit beharko ditu Xren edozein balio kodetzeko.

## Baldintzazko entropia 
: *Ikus* Baldintzazko entropia

Izan bitez X eta Y, haien artean independenteak ez diren bi aldagai; horietako bat ezagutzeak (Y, adibidez) besteari buruzko informazioa (Xri buruzkoa) ematen digu. Informazioaren entropiari dagokionez, Y aldagaiaren informazioak X aldagaiaren ziurgabetasuna txikituko duela esan dezakegu. Beraz, X aldagaiaren entropia Y aldagaiaren menpe dagoela esan daiteke:

H(X,Y)=-\sum_{x,y} p(x,y) \log_2 p(x,y)

Bayes-en teorematik p(x,y)=p(y)p(x|y) dela dakigu, non Y ezagututa X egoera gertatzearen probabilitatea p(x|y) den. Honakoa adieraz daiteke:

H(X|Y)=-\sum_{y} p(y) \sum_{x} p(x|y) \log_2 p(x|y)

## Oharrak 
## Erreferentziak 
## Bibliografia 
* Jorge Ramió Aguirre, Aplicaciones criptográficas. Libro guía de la asignatura de Seguridad Informática. Escuela Universitaria de Informática. Universidad Politécnica de Madrid. Enero de 1998.

## Ikus, gainera 
* Informazio kantitatea
* Baldintzazko entropia
* Elkarrekiko informazioa

## Kanpo estekak 
* Komunikazioaren Matematikaren teoria (ingelesez)
* Shannon-en entropia kalkulatzeko kalkulagailua (ingelesez)
* Fitxategientzako Shannon-en entropia kalkulatzeko kalkulagailua (ingelesez)