Lankide:Jon Ander González/Proba orria

Entropia (informazio-teoria)

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

Entropia kontzeptua termodinamika, mekanika estatistiko eta informazio-teorian erabiltzen da. Kasu guztietan entropia «desordena-neurri» edo «konbinazio jakin batzuen berezitasun» bezala ulertzen da. Ziurgabetasun-neurri edo edozein prozesutan ziurgabetasun hori mugatu, murriztu edo ezabatu beharrezko informazio-neurri bezala ulertu daiteke. Kontua da informazio eta entropia kontzeptuek oso harreman estua dutela,  hau antzemateko mekanika estatistiko eta informazio-teoriaren arloetan garapen urte asko behar izan zituzten arren.

Sarrera

Informazio-teoriaren oinarrizko ideia zera da: gai baten inguruan gero eta gehiago jakin, orduan eta informazio berri gutxiago lortuko da. Gertaera bat emateko probabilitatea handia bada, gertatzen denean ez da harrigarria eta, beraz, informazio berri gutxi ematen du. Gertatzeko probabilitatea eskasa bada, ordea, gertakizuna jazo izana nabarmenki adierazgarriagoa da. Hortaz, informazio kantitatea gertaeraren probabilitatearen aurkakoa (1/p) adierazten duen funtzio gorakor bat da. Gertaera bat baino gehiago egoteko aukera badago, entropiak gertaeretako bat benetan ematekotan lortzea espero den batezbesteko informazio kantitatea neurtzen du. Dado bat jaurtitzeak txanpon bat jaurtitzeak baino entropia handiagoa duela esan nahi du honek, dado jaurtiketa bakoitzean lortzen den emaitzak txanpona jaurtitzearen emaitzek baino probabilitate txikiago baitu.

Beraz, entropia egoera baten ziurgabetasun-neurria edo batezbesteko informazio kantitatea da. Kontzeptu hauek ulertzeko adibide bezala bozketa politiko bat proposatzen da. Normalean bozketa hauek lortuko den emaitza aldez aurretik ezagutzen ez delako egiten dira eta, hortaz, emaitzek informazio berria emango dute. Beste era batera esanda: bozketaren entropia, a priori, handia da. Denbora gutxi pasata bozketa berdina errepikatuko balitz, lehenengo bozketaren emaitza dagoeneko ezaguna denez, bigarrenean lortuko dena iragarri ahalko litzateke eta emaitza berriek ez lukete informazio gehigarri askorik emango; kasu honetan, bigarren bozketaren entropia, a priori, txikia da (aurrekoarekin alderatuz). Beste adibide bat txanponaren jaurtiketan oinarritutakoa 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 hau. Iragarpen bat eman beharko balitz, aurpegia aterako dela esan zitekeen, eta asmatzeko probabilitatea 1/2 izango litzateke. Horrelako txanpon jaurtiketa batean entropiaren balioa 1 da, gertatzeko probabilitate berdina daukaten bi egoera daudelako.  Txanponaren bi aldeak aurpegiak izango balira, ordea, entropiaren balioa 0 izango litzateke, errorerik gabe iragarri ahalko litzatekeelako emaitza beti aurpegia izango dela. Analogikoki, gertaera bitar ekiprobable batek hurrengo Shannon-en entropia du: $\log _{2}2=1$. Hiru aukera ekiprobable egongo balira, Shannon-en entropia $\log _{2}3$ izango litzateke.

Definizio formala

Suposatu zorizko aldagai baten hasierako indeterminazio maila$k$ dela ($k$ egoera posible daude). Gainera, probabilitate bereko egoera guztiak suposatuko ditugu. Orduan, suposatutako konbinazio bat gertatzeko probabilitatea $p=1/k$izango da. Beraz, $c_{i}$adierazpena horrela idatz dezakegu:

$c_{i}=\log _{2}(k)=\log _{2}[1/(1/k)]=\log _{2}(1/p)=\underbrace {\log _{2}(1)} _{=0}-\log _{2}(p)=-\log _{2}(p)$

$k$ egoera bakoitzak $p_{i}$ probabilitatea badu, entropia informazio-kantitateen batuketa haztatua erabiliz kalkulatuko da:

$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 mezu baten entropia, H(X) bezala adierazia, mezuaren egoera desberdinei dagokien informazio kantitatearen batezbesteko balioa haztatua da.

$H(X)=-\sum _{i}p(x_{i})\log _{2}p(x_{i})$

zorizko aldagai baten ziurgabetasun mailaren neurri bat eta informazio kantitatea adierazten ditu.

Adibidea

Adibide bezala txanpon baten jaurtiketa hartuko dugu. Txanpona jaurtitzean aurpegia ala gurutzea lortuko dugunaren probabilitateak ezagunak dira, baina txanponak ez du zertan txanpon zintzoa izan. Hau Bernouilli prozesu bat bezala irudika dezakegu.

Jaurtiketaren emaitzaren entropia maximizatuko da txanpon zintzoa bada, hau da, probabilitate bera badago aurpegia edo gurutzea lortzeko (P = 0,5). Egoera hau ziurgabetasun maximoko egoera da, hurrengo jaurtiketaren emaitza aurreikustea ia ezinezkoa da eta.

${\begin{aligned}\mathrm {H} (X)&=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log _{b}\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}}$ Bestetik, hartu dezagun zintzoa ez den txanpona, izan ere, aurpegia lortzeko probabilitatea p da eta gurutzea lortzekoa, ordez, q, non p≠q. Egoera honetan ziurgabetasuna txikiagoa da. Jaurtitzen den bakoitzean, txanponaren alde bat lortzearen probabilitatea bestea lortzearena baino handiagoa izango da. 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 balioen elkarrekiko informazioa, I(X, Y) bezala adierazia, bi aldagaien elkarrekiko dependentzia neurtzen duen kantitatea da. Zorizko aldagai bat ezagutzean, demagun Y dela, X aldagaiaren ziurgabetasun maila (entropia) zenbat murrizten den neurtzen du informazio kantitateak. Beraz, honako hau ondoriozta dezakegu: X eta Y berdinak badira, orduan I(X; X) = H(X).

Propietateak

Entropiak hurrengo propietateak dauzka:

1. Ezin da negatiboa izan. $p_{i}$ probabilitate bat izanda, $0<p_{i}\leq 1$ beteko 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 dauka (maximoa denean) eta ez du informazio-galera suposatzen.
3. Izan bedi {A1, …, An} emaitza posibleak eta p1, …, pn probabilitate erlatiboak dituen prozesu bat. $H(p_{1},\dots ,p_{n})\,$funtzioa maximoa da hurrengo egoera ematen bada: $p_{1}=\dots =p_{n}=1/n\,$. Emaitza intuitiboa da mezuaren ziurgabetasun maximoa daukagulako aldagaiaren balio posibleak ekiprobableak direnean.
4. Izan bedi {A1, …, An} emaitza posibleak eta p1, …, pn probabilitate erlatiboak 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, jasoko den mezuari buruzko ziurgabetasun txikiagoa existitzen delako.

Kodetzaile optimoa

Kodetzaile optimo bat mezu bat kodetzeko bit kopuru minimoa erabiltzen duena da.  Kodetzaile optimo batek kode laburrak erabiliko ditu maiztasunez agertzen diren mezuak kodetzeko eta gutxitan agertzen diren mezuen kasuan kode luzeagoez baliatuko da. Modu honetan 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 honetaz aprobetxatzen da, ingelesez maiztasun handiagoarekin agertzen diren hizkiei kode laburragoak esleituz.

Beste eredu bat Huffmanen algoritmoa izango litzateke. Algoritmo honek informazioa trinkotzen du kodetzaile optimoan oinarrituz. Lehenik eta behin, informazioa zeharkatzen du karaktereen maiztasuna aurkituz. Maiztasuna aurkiturik, kodetzaile optimoa bilatzen du zuhaitz bitarren bidez. Trinkotze teknika batzuek ez dute sinbolo bakaneko probabilitateak erabiltzen mezua kodetzeko, baizik eta sinbolo sekuentzien probabilitate bateratua; ulermen maila altuagoa lortuz.

Kodetzaile optimo bat eratu dezakegu X zorizko aldagai baten entropian oinarrituz. Entropiaren bidez kodetzaile optimo batekin mezu bat kodetzeko beharrezko biten batezbestekoa lortu dezakegu, base bitarreko logaritmoa erabiltzen badugu. Beraz, mezu bat sinboloak banaka hartuz informazio galerarik gabe konprimitu daitekeen muga maximoa lortu dezakegu horrela (Shannon-ek analitikoki frogatua). Ulermen muga (bitetan), entropia bider mezuaren luzera 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}$ edo sinbolo espezifiko batek ematen duen  informazioa (bitetan definiturik), hurrengo formula bezala definitzen da:

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

Adibidea

Demagun mezu batek hiru egora izan ahal dituela. 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 aldiz bi bit behar izango ditugu M2 eta M3 egoeretarako. M1 = 0, M2 = 10 eta M3 = 11 erabili dezakegu mezua kodetzeko, adibidez. Hitzarmen honekin, M₁M₂M₁M₁M₃M₁M₂M₃  “010001101011” bezala 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$

Beraz, ondoriozta dezakegu, kodetzaile optimoak 1.5 bit behar izango dituela X-ren edozein baliorako.

Baldintzapeko entropia

Hartu ditzagun bi aldagai, X eta Y, haien artean independenteak ez direnak, hau da, bat ezagutzeak (Y adibidez) besteari buruzko informazioa (X adibidez) ematen digu. Informazioaren entropiari begira, Y aldagaiaren informazioak X aldagaiaren ziurgabetasuna txikituko duela esan dezakegu. Beraz, X aldagaiaren entropia Y aldagaiaren menpe egongo dela esan dezakegu:

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

Bayes-en teoremaren arabera: p(x,y)=p(y)p(x|y) badakigunez, non p(x|y) Y zein den jakinda X egoera bat gertatzearen probabilitatea den, honako hau adieraz dezakegu:

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