Informo-teorio

From Wikipedia

La informo-teorio interesas pri sistemo di komuniko e di lia efiko. La nociono di sistemo di komuniko esinta larga, ol esas mem di la informo-teorio.

Ta domeno truvas sua cientala origino kon Claude Shannon qua es poko la patro fondanto per sua artiklo A Mathematical Theory of Communications publikigita en 1948.

Inter la importanta branchi, on povas citar :

la kodexajo di informo,
la quantiva mesuro di superflua di texto,
la kompreso di donaji
la kriptografo.

[redaktar] Exempli di informo

Informo or informeso indikas, inter ensemblo di eventi, un o multi posibla eventi.

Tale, la informo diminutas la necerteso. En decido-teorio, on konsideras mem ke ol ne apelendas informo ke to qua es posible di havas efekto sur nia decidi (poke di kozi en jurnalo es a ta konto di informi ..).

[redaktar] Prima exemplo

Sive fonto povinta produktar di integra tensioni di 1 a 10 volti e recepciono qua mezuros ta fluo. Ante la sendo di elektra fluo per la fonto, la recepciono ne havas ideo de la tensiono qua esos livrar per la fonto.

En revancho, foye la fluo emisita e recepcionita, la ne-certeso sur la fluo emisita diminutas. L’informo-teorio konsideras ke le recepciono posedas ne-certeso di10 standi.

[redaktar] Duesma exemplo

Libraro posedas larga nombro di labori, di revui, di libri e di vorto-libri. Ni serchas kompleta kurso sur la informo-teorio. Tota un-esme, ol es logika ke ni ne truvos ta dokumentaro en di verko di arti o di literaturo; ni venas do d’obtenar informa informeso qua diminutos nia tempo di inquestar.

[redaktar] ne-perfekta informeso

Sive realizisto do me amas du filmo pri tri. kritikisto ke me konocas bona kritikegas sua lasta filmo e me savas ke me partigas en mez-valoro l’analizi di ta kritikisto quar foye pri kin. Ta kritikon me des-konsilos di irar vidar la filmo? To es ibe la centrala questiono di bayesiala infero, qua quantesas anke en biteti.

[redaktar] Atencez a ne konfundar

Oportas min di biteti per skribar ‘’hundo’’ ke ‘’mamifero’’. Tamen l’indiko ‘’Medoro es hundo’’ kontenas bona ‘’plu’’ d’informo ke l’indiko ‘’Medoro es mamifero’’: la kontenita di semantikala informo di sendajo dependas di kontexto. En fakto, to es la paro sendajo + kontexto qua konstituas la vera porto di informo, e nul tempe la sendajo sole (videz Paradoxo di kompresilo).

[redaktar] Mesuro dil quanteso di informo

[redaktar] Quanteso di informo : elementa kazo

Konsideras N boxi numerila di 1 a N. Individuo A havas celita segun la chanco un objekto en un di ta boxi. Individuo B devas truvar la numero dil boxo ube es celita l’objekto. Per ica, il havas la yuro di pozar di questioni a l’individuo A a qua il-ca devas respondar sen nientio per YES o NO. Ma omna questiono pozita reprezentas kusto a pagar per l’individuo B (per exemplo un euro). Individuo C savas en kel boxo es celita l’objekto. Il havas la posiblo di vendar ta informo a l’individuo B. B acepteros ta vendo-kontrato ke se la precio di C es infra o egala a mez-valora kosto ke B devrus spensar per truvar la boxo en pozar di questioni a A. L’informo detenita per C havas do certa precio. Ta precio reprezentas la quanto di informo per la konoco di la bona boxo : to es la mez-valora nombro di questioni a pozar per identigar ta boxo. Ni notas lu I.

Exemplo:

Kad N = 1, I = 0. To es sole un boxo. Irga questiono es necesa.

Kad N = 2, I = 1. On demandas se la bona boxo es la boxo n°1. La respondo Yes o No determinas lore sen ambigueso kel es la sercha boxo.

Kad N = 4, I = 2. On demandas se la boxo permisas lors d’eliminar du di boxi ed ol suficas di lasta questiono per truvar kel es la bona boxo per du.

Kad N = 2^k, I = k. On skribas la numeri di boxi en bazo 2. Li numeri havas ad-maxime k binara cifri, e per omnu di rango di ta cifri, on demandas se la sercha boxo posedas la cifro 0 o la cifro 1. En k questioni, on havas determinas tota la binara cifri del bona boxo. To rivenas anke a pozar k questioni, omna questiono havinta per skopo di divisar sequence la nombro di konsiderita boxi per 2 (metodo di dikotomio).

On es do amenita a pozar I = log(N), ube log es la logaritmo en bazo 2, ma ta figuro ne produktas su ke en la kazo di N equiprobabla evenementi.

[redaktar] Quanteso di informo relata a evenemento

Supozas nun ke la boxi sive kolorita, e ke to es n reda boxi. Supozas anke ke C savas ke la boxo ube es celita l’objekto es reda. Qual es la precio di ta informo? Sen ta informo, le precio a pagar ne es pluse ke log(n). La precio dil informo ‘’la sercha boxo es reda’’ es do log(N) – log(n) = log N/n.

On definas tale la quanteso di informo kom kreskanta funciono di $\frac{N}{n}$ kom :

$N$ la nombro di posibla evenementi
$n$ la kardinala di sub-ensemblo delimita per l’informo.

Por mezurar ta quanteso d’informo, on pozas : $I = log_{2} \left (\frac{N}{n} \right)$

$I$ es expresas en biteto (o logon, uneso introdukta per Shannon, di qua, en la fakti, biteto es devenita sinonimo), o bona en nat se on uzas la naturala logaritmo vice di logaritmo di bazo 2.

Ta defino justifikas su nam ol volas la sequa propraji :

L'informo es inkluzite en 0 e ∞.
Un evenemento nam poko di probableso reprezentas multo di informo, (exemplo: « nivas en januaro » kontenas multo min d’informo ke « nivas en agosto » se nur ke on sive en la norda hemisfero)
L'informo devas esar adicionala.

Remarko : kande on dispozar di multa informi, la quanteso di blokala informo ne es la sumo di quanteso d’informo. To es devita a la prezenteso di logaritmo. Videz anke: reciproka informo, komuna informo a du sendaji, qua, en l’idajo, explikas ta « sub-adicionala » dil informo.

[redaktar] Entropio, formulo di Shannon

Supozas nun ke la boxi sive di diversa kolori : n₁ boxi de koloro C₁, n₂ boxi de koloro C₂, ..., n_k boxi de koloro C_k, kon n₁ + n₂ + ... + n_k = N. La persono C savas di qual koloro es la sercha boxo. Qual es la precio di ta informo?

L'informo « la boxo es di koloro C₁ » valoras log N/n₁, e ta eventualajo havas probableso n₁/N. L'informo « la boxo es di koloro C2 » valoras log N/n₂, e ta eventualajo havas probableso n₂/N...

La mez-valoro precio di l’informo es do n₁/N log N/n₁ + n₂/N log N/n₂ + ... + n_k/N log N/n_k. Plu generale, se on konsideras k disjunta evenementi di rispektiva probableso p₁, p₂, ..., p_k kun p₁ + p₂ + ... + p_k = 1, lore la quanteso di informo korespondinta a ta distributo di probableso es p₁ log 1/p₁ + ... + p_k log 1/p_k. Ta quanto apelar su entropio del distributo di probableso.

L'entropio permisas do di mezurar la quanteso di mez-valoro informo di ensemblo di evenementi (en partikulara di sendaji) e di mezurar sua necerteso. On notas li $H$ :

$H \left (I \right) = - \sum_{i\in I} p_i \mathbf{log}_2\; p_i$

kun $p_i = \frac{n_i}{N}$ l’asocia probableso a l’aparo di l’evenemento $i$ .

[redaktar] Kodexaja di l’informo

On konsideras sequence di simboli. Omna simbolo povas prenar du valori s₁ e s₂ kun di probablesi rispektive p₁ = 0,8 e p₂ = 0,2. La quanto d’informo kontenas en simbolo es p₁ log 1/p₁ + p₂ log 1/p₂ ≈ 0,7219. Se omna simbolo es nedependanta di segun, lore sendajo di N simboli kontenas en mez-valora quanto d’informo egala a 0,72N. Se la simbolo s₁ es kodexita 0 e la simbolo s₂ es kodexita 1, lore la sendajo havas longua di N, to qua es perdo per raporto ala quanto di informo ke ol portas.

La Shannon-teorii enuncas ke es neposibla di truvar kodexo do la mez-valora longuo sive infra a 0,72N, ma ke ol es posibla di kodexar la sendajo di fasono a ta ke la kodexa sendajo havas en mez-valoro longua anke proxim ke volas di 0,72N kande N augmentas.

Per exemplo, on rigrupas la simboli tri per tri e on kodexas li kom sive :

simboli a kodexar	probableso di trio	kodexita di trio	longua di kodexo
s₁s₁s₁	0.8³ = 0.512	0	1
s₁s₁s₂	0.8² ¥ 0.2 = 0.128	100	3
s₁s₂s₁	0.8² ¥ 0.2 = 0.128	101	3
s₂s₁s₁	0.8² ¥ 0.2 = 0.128	110	3
s₁s₂s₂	0.2² ¥ 0.8 = 0.032	11100	5
s₂s₁s₂	0.2² ¥ 0.8 = 0.032	11101	5
s₂s₂s₁	0.2² ¥ 0.8 = 0.032	11110	5
s₂s₂s₂	0.2³ = 0.008	11111	5