Entropia (informazio-teoria)

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 ${\displaystyle \log _{2}2=1}$ da. Modu berean, probabilitate bereko hiru aukera egongo balira, Shannon-en entropia ${\displaystyle \log _{2}3}$ izango litzateke.

Demagun zorizko aldagai baten hasierako indeterminazio maila ${\displaystyle k}$ dela (${\displaystyle k}$ egoera posible dituela, alegia). Demagun, gainera, egoera guztiak probabilitate berekoak direla. Hori hala izanik, konbinazio jakin bat gertatzeko probabilitatea ${\displaystyle p=1/k}$ izango da. Beraz, honakoa idatz daiteke:[oh 1]

${\displaystyle \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, ${\displaystyle i.}$ egoera ${\displaystyle p_{i}}$ probabilitatez gertatzen bada, informazio-kantitateen batuketa haztatuaren bidez kalkulatuko da entropia:[1][oh 2]

${\displaystyle 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, ${\displaystyle H(X)}$ notazioaren bidez adierazten da eta aldagaiaren egoera desberdinei dagokien informazio-kantitatearen batezbesteko balio haztatua da.

${\displaystyle 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.

Xren entropia 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.

${\displaystyle {\begin{aligned}\mathrm {H} (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{aligned}}}$

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:

${\displaystyle {\begin{aligned}\mathrm {H} (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<1\end{aligned}}}$

Entropiak honako propietateak betetzen ditu:

1. Ez da negatiboa. ${\displaystyle p_{i}}$probabilitate bat denez, ${\displaystyle 0<p_{i}\leq 1}$ betetzen da. Hortaz, ${\displaystyle \log _{2}p_{i}\leq 0}$ eta ondorioz ${\displaystyle -\log _{2}p_{i}\geq 0}$ betetzen dela ziurta daiteke.
2. ${\displaystyle H\leq \log _{a}(n)}$. Hau da, H entropiak goi-bornea du (maximoa denean) eta ez du informazio-galerarik suposatzen.
3. Izan bitez {A1, …, An} emaitza posibleak eta p1, …, pn probabilitateak dituen prozesu bat. ${\displaystyle H(p_{1},\dots ,p_{n})\,}$ funtzioa maximoa da ${\displaystyle p_{1}=\dots =p_{n}=1/n\,}$ betetzen denean; emaitza guztiak probabilitate berberaz gerta daitezkeenean ematen da ziurgabetasunaren maila maximoa.
4. Izan bitez {A1, …, An} emaitza posibleak eta p1, …, pn probabilitateak dituen prozesu bat. ${\displaystyle H(p_{1},\dots ,p_{n})\,}$funtzioak 0 balioa du ${\displaystyle p_{i}=0}$ bada i-ren edozein baliorako klase jakin baterako izan ezik, non ${\displaystyle p_{j}=0}$. Modu intuitiboan pentsa daiteke egoera batek edo gehiagok probabilitate altua dutenean entropia nabarmenki jaisten dela, ziurgabetasuna txikitzen delako.

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[3]. 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.

${\displaystyle H(X)=-\sum _{i}p(x_{i})\log _{2}p(x_{i})=\sum _{i}-p(x_{i})\log _{2}p(x_{i})=}$ ${\displaystyle =\sum _{i}p(x_{i})[log_{2}(1)-\log _{2}(p(x_{i}))]=\sum _{x}p(x)\log _{2}(1/p(x))}$

Beraz, ${\displaystyle X}$ zorizko aldagai diskretu baten ${\displaystyle x_{i}}$ sinbolo espezifiko batek ematen duen informazioa, bitetan neurtua, horrela definitzen da:

${\displaystyle I(x_{i})=\log _{2}{\frac {1}{p(x_{i})}}=-\log _{2}{p(x_{i})}}$

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:

${\displaystyle 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:

${\displaystyle H(X|Y)=-\sum _{y}p(y)\sum _{x}p(x|y)\log _{2}p(x|y)}$

• 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.

• Informazio kantitatea
• Baldintzazko entropia
• Elkarrekiko informazioa

• Komunikazioaren Matematikaren teoria (ingelesez)
• Shannon-en entropia kalkulatzeko kalkulagailua (ingelesez)
• Fitxategientzako Shannon-en entropia kalkulatzeko kalkulagailua (ingelesez)