Entropia (informazio-teoria)

Informazio-teoriaren alorrean entropiak, informazio-entropia eta Shannonen entropia (Claude E. Shannon-en omenez) izenez ere ezagutua, informazio iturri baten ziurgabetasuna neurtzen du.

Bi entropia-bit

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

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.

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

${\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}}$

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:

1. Ez da negatiboa. $p_{i}$probabilitate bat denez, $0<p_{i}\leq 1$ betetzen da. Hortaz, $\log _{2}p_{i}\leq 0$ eta ondorioz $-\log _{2}p_{i}\geq 0$ betetzen dela ziurta daiteke.
2. $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. $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.
4. 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 _{2}p(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, M₁M₂M₁M₁M₃M₁M₂M₃ 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)$

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)

• Datuak: Q204570
• Multimedia: Entropy and information / Q204570