Informteorio

matematika studfako

Informteorioinforma teorio, ne aparte specifita, estas la komuna nomo pri la teorio de informoj de Claude Shannon, kiu estas probabloteorio por kvantigi la averaĝajn informojn en aro da mesaĝoj, kies komputila kodigo sekvas precizan statistikan distribuon. Ĉi tiu kampo havas sian sciencan originon kun Claude Shannon, kiu estas la fondinta patro kun sia artikolo A Mathematical Theory of Communication (Matematika Teorio de Komunikado) eldonita en 1948.

Gravaj branĉoj de la informteorio de Shannon inkludas:

- la kodadon de informoj,
- la kvantecan mezuron de redundo de teksto,
- datumkunpremodatumdensigo,
- kriptografio.

En pli ĝenerala senco, informteorio estas teorio celanta kvantigi kaj kvalifiki la nocion de enhavo pri informoj ĉeestantaj en aro da datumoj. Kiel tia, ekzistas alia teorio de informoj: la "algoritma teorio de informoj", kreita de Kolmogorov, Solomonov kaj Gregory Chaitin komence de la 1960-aj jaroj.

Disvolviĝo de la matematika informteorio

redakti

Claude Shannon kaj Warren Weaver plifortigis la paradigmon. Ili estis telekomunikado-inĝenieroj kaj temis pri mezurado de informojn por dedukto de la fundamentaĵoj pri komunikado (kaj ne teorio de informoj). En A Mathematical Theory of Communication (Matematika teorio pri komunikado) [1][2] estas artikolo verkita de la inĝeniero kaj matematikisto Claude Shannon eldonita en la ĵurnalo Bell System Technical Journal en 1948[3][4]. Ili modelis informojn por studi la respondajn leĝojn: bruon, entropion kaj ĥaoson, laŭ ĝenerala analogio al la leĝoj de energio kaj termodinamiko. Iliaj verkoj kompletigis tiujn de Alan Turing, Norbert Wiener kaj John von Neumann (por nomi nur la ĉefajn fakulojn) kaj konstituas la komencan bazon de la "teorio de signalo"" kaj de la "Sciencoj pri informo".

Estu fonto   kun   simboloj, simbolo   havanta probablon   aperi, la entropio   de la fonto  , ankaŭ nomata Shannon-entropio, estas difinita laŭ la informteorio tiele:

 

Komence la natura logaritmo estis uzata. Sed por komforto, ĝi estos anstataŭigata de la logaritmo kun bazo 2, tielmaniere ke la elementa informo estu la bito.

Informadiko do estos teĥnika variado aŭtomatanta la prilaboradon (inkluzive de transdono kaj transporto) de informoj.

Informekzemploj

redakti

Informo difinas, inter aro da eventoj, unu aŭ plurajn eblajn eventojn.

Teorie, la informo reduktas necertecon. En la teorio de decido, oni eĉ konsideras, ke oni devas nomi "informo" nur tion, kio estas "verŝajne havi efikon sur niaj decidoj".

En praktiko, la troo da informo, kiel ĝi aperas en retpoŝtaj sistemoj, povas konduki al saturado kaj malhelpi decidon.

Unua ekzemplo

redakti

Estu fonto, kiu povas produkti elektrajn tensiojn kun entjeraj valoroj de 1 ĝis 10 voltoj kaj ricevilo, kiu mezuros ĉi tiun tension. Antaŭ sendi la kurenton per la fonto, la ricevilo havas neniun ideon pri la elektra fluo, kiu estos transdonita de la fonto. Aliflanke, post la elsendo kaj la ricevo de kurento, la necerteco pri la elsendita fluo malpliiĝas. La informteorio konsideras, ke la ricevilo havas necertecon de 10 statoj.

Dua ekzemplo

redakti

Biblioteko havas multajn verkojn, revuojn, librojn kaj vortarojn. Ni serĉas kompletan kurson pri informteorio. Unue, estas logike, ke ni ne trovos ĉi tiun dosieron en verkoj pri arto aŭ literaturo; ni ĵus akiris informojn, kiuj reduktos nian tempon de serĉo. Ni diris, ke ni ankaŭ volis kompletan kurson, do ni ne trovos ĝin en revuo aŭ en vortaro. Ni akiris plian informon, ke ni serĉas libron, kio ankoraŭ malpliigos la daŭron de nia esplorado.

Malperfekta informo

redakti

Estu reĝisoro, pri kiu mi kutime ŝatas du filmojn el tri. Kritikulo, kiun mi bone konas, mallaŭdis sian lastan filmon kaj mi scias, ke mi kunkonsentas la averaĝan analizon de ĉi tiu kritikulo kvar fojojn el kvin. Ĉu ties kritiko malhelpu min iri por vidi la filmon? Ĉi tiu estas la centra demando pri "Bayesia inferenco", kiu ankaŭ estas kvantigita en bitoj.

Enhavo de informo kaj kunteksto

redakti

Bezonas malpli da bitoj por skribi "hundo" ol "mamulo". Tamen la indiko "Medor estas hundo" enhavas multe pli da informoj ol la indiko "Medor estas mamulo": la enhavo de semantika informo de mesaĝo dependas de la kunteksto. Fakte, estas la paro mesaĝo + kunteksto, kiu konstituas la veran portanton de informoj, kaj neniam la mesaĝo sole.

Mezurante la kvanton da informoj

redakti

Kvanto da informo: elementa kazo

redakti

Konsideru   skatolojn numeritaj de 1 ĝis  . Individuo A kaŝis objekton hazarde en unu el ĉi tiuj skatoloj. Individuo B devas trovi la numeron de la skatolo, en kiu la objekto estas kaŝita. Por ĉi tio, li rajtas demandi la individuon A, al kiu li devas respondi sen mensogi, per JES aŭ NO. Sed por ĉiu demando devas esti pagita de la individua B etan monsumon (ekzemple unu eŭro). Individuo C scias, en kiu skatolo kaŝitas la objekto. Li havas la eblon vendi ĉi tiun informon al la individuo B. B nur akceptos ĉi tiun merkaton se la prezo de C estas malpli ol aŭ egalas al la averaĝa kosto, kiun B devus elspezi por koni la bonan skatolon, per la vico da demandoj al A. La informoj tenataj de C sekve havas certan prezon. Ĉi tiu prezo reprezentas la kvanton da informoj ligitan al la scio de la serĉata skatolo: ĝi estas la averaĝa nombro da petendaj demandoj por identigi ĉi tiun skatolon. Kompreneble ju pli la nombro de skatoloj estas granda, des pli individuo B akceptos pagi grandmonsumon al individuo C. Notu ni ĝin  .

Ekzemploj:

 ,  ; estas nur unu skatolo, ne utilas iu ajn demando.

 ,  ; post la demando ĉu la bona skatolo estas la skatolo 1, la respondo JES aŭ NE permesas tiam senambigue koni tiun, kiu estas la serĉita skatolo.

 ,  ; post la du demandoj ĉu la bona skatolo estas unu el la du skatoloj 1 aŭ 2, se estas respondo JES la problemo estas solvita, se NE sufiĉas alia kroma demando, por trovi tiun, kiu estas la bona skatolo el la du restantaj.

 ,  ; oni numeras la skatolojn laŭ la bazo 2. La numeroj posedas maksimume   duumajn ciferojn, kaj por ĉiu pozicio de tiuj ciferoj, oni demandas ĉu la serĉata skatolo rilatas al la cifero 0 aŭ 1. Per   demandoj, tiel determinitas ĉiuj duumaj ciferoj kaj finfine la pozicio de la bona skatolo. Ĉi tio resumiĝas per   demandoj, ĉiu demando sinsekve dividanta per 2 la nombron de skatoloj konsideritaj (diĥotomia metodo).

Do oni povas skribi la rezulton:  , sed ĝi validas nur se la   eventoj estas samprobablaj.

Kvanto da informoj rilate al unu evento

redakti

Supozu ni nun, ke la skatoloj estu kolorigitaj kaj ke estu   ruĝaj skatoloj. Supozu ankoraŭ, ke la individuo C scias, ke estas ruĝa la skatolo en kiu la objekto estas kaŝita. Kiu estas la prezo de tiu informo? Sen ĝi, la pagenda prezo estus  . Dank' al tiu informo, la pagenda prezo estas nur  . La prezo de la informo «la serĉata skatolo estas ruĝa» estas do  .

Tial difiniĝas la kvanto da informo, kiel kreska funkcio de   kun:

  •   nombro de eblaj eventoj,
  •   nombro de eventoj de la subaro difinita per la informo.

Por mezuri tiun infrormkvanton, oni difinas:  

kie   esprimatas per bito .

Tia difino praviĝas, pro la fakto ke la sekvantaj proprecoj nepras:

  1. informo valoras inter 0 kaj ∞ ;
  2. evento kun malgranda probablo enhavas grankvanton da informoj (ekzemple: « Neĝas dum januaro» enhavas multe malpli da informo ol « Neĝas dun aŭgusto » se ni loĝas en la norda duonglobo);
  3. informo adicias.

Entropio, apliko de Shannon-formulo

redakti

Supozu ni, ke estas diverskoloraj skatoloj: n1 skatoloj kun koloro C1, n2 skatoloj kun koloro C2…, nk skatoloj kun koloro Ck, kun n1 + n2 + … + nk = N. La individuo C konas la koloron de la serĉata skatolo. Kiu estas la prezo de tiu informo?

La informo «la koloro de la skatolo estas C1» valoras log N/n1, kaj tiu okazaĵo havas probablon n1/N. La informo «la koloro de la skatolo estas C2» valoras log N/n2, kaj tiu okazaĵo havas probablon n2/N...

La averaĝa prezo de la informo estas do n1/N log N/n1 + n2/N log N/n2 + … + nk/N log N/nk. Pli ĝenerale, se oni konsideras k disajn eventojn kun respektivas probabloj p1, p2…, pk kaj p1 + p2 + … + pk = 1, tial la informkvanto respondanta al tiu probablodistribuo estas p1 log 1/p1 + … + pk log 1/pk. Tiu kvanto nomiĝas entropio de la probablodistribuo

Tiu Shannon-entropio permesas do mezuri la averaĝan informkvanton da eventaro (aparte de mesaĝoj) kaj mezuri ĝian necertecon. Oni notas ĝin  

 

kun   la probablo asociita al la apero de la evento   kaj sekvas:

 

Referencoj

redakti
  1. Robert B. Ash. Information Theory. New York: Interscience, 1965. (ISBN 0-470-03445-9). New York: Dover 1990. (ISBN 0-486-66521-6), p. v
  2. R.W. Yeung. (2008) Information Theory and Network Coding (Informteorio kaj kodado The Science of Information (La scienco pri informado) (angle), p. 1–01. doi:10.1007/978-0-387-79234-7_1. ISBN 978-0-387-79233-0.
  3. Claude E. Shannon. "A Mathematical Theory of Communication (Matematika teorio pri komunikado)", Julio 1948, paĝoj p. 379–423. (angle)
  4. Claude E. Shannon. "A Mathematical Theory of Communication", oktobro 1948, paĝoj p. 623–666. (angle)

Vidu ankaŭ

redakti

Bibliografio

redakti

Eksteraj ligiloj

redakti

En tiu ĉi artikolo estas uzita traduko de teksto el la artikolo Théorie de l'information en la franca Vikipedio.