Informteorio

Informteorio aŭ informa 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,

- datumkunpremo aŭ datumdensigo,

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

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 ${\displaystyle X}$ kun ${\displaystyle n}$ simboloj, simbolo ${\displaystyle i}$ havanta probablon ${\displaystyle p_{i}}$ aperi, la entropio ${\displaystyle H}$ de la fonto ${\displaystyle X}$, 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.

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.

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.

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.

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.

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.

Konsideru ${\displaystyle N}$ skatolojn numeritaj de 1 ĝis ${\displaystyle N}$. 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 ${\displaystyle I}$.

Ekzemploj:

Aŭ ${\displaystyle N=1}$, ${\displaystyle I=0}$; estas nur unu skatolo, ne utilas iu ajn demando.

Aŭ ${\displaystyle N=2}$, ${\displaystyle I=1}$; 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.

Aŭ ${\displaystyle N=4}$, ${\displaystyle I=2}$; 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.

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

Do oni povas skribi la rezulton: ${\displaystyle I=\log _{2}(N)}$, sed ĝi validas nur se la ${\displaystyle N}$ eventoj estas samprobablaj.

Supozu ni nun, ke la skatoloj estu kolorigitaj kaj ke estu ${\displaystyle n}$ 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 ${\displaystyle \log _{2}(N)}$. Dank' al tiu informo, la pagenda prezo estas nur ${\displaystyle \log _{2}(n)}$. La prezo de la informo «la serĉata skatolo estas ruĝa» estas do ${\displaystyle \log _{2}(N)-\log _{2}(n)=\log _{2}(N/n)}$.

Tial difiniĝas la kvanto da informo, kiel kreska funkcio de ${\displaystyle {\frac {N}{n}}}$ kun:

• ${\displaystyle N}$ nombro de eblaj eventoj,
• ${\displaystyle n}$ nombro de eventoj de la subaro difinita per la informo.

Por mezuri tiun infrormkvanton, oni difinas: ${\displaystyle I=\log _{2}\left({\frac {N}{n}}\right)=-\log _{2}\left({\frac {n}{N}}\right)\ \,,}$

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

Supozu ni, ke estas diverskoloraj skatoloj: n₁ skatoloj kun koloro C₁, n₂ skatoloj kun koloro C₂…, n_k skatoloj kun koloro C_k, kun n₁ + n₂ + … + n_k = 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 C₁» valoras log N/n₁, kaj tiu okazaĵo havas probablon n₁/N. La informo «la koloro de la skatolo estas C₂» valoras log N/n₂, kaj tiu okazaĵo havas probablon n₂/N...

La averaĝa prezo de la informo estas do n₁/N log N/n₁ + n₂/N log N/n₂ + … + n_k/N log N/n_k. Pli ĝenerale, se oni konsideras k disajn eventojn kun respektivas probabloj p₁, p₂…, p_k kaj p₁ + p₂ + … + p_k = 1, tial la informkvanto respondanta al tiu probablodistribuo estas p₁ log 1/p₁ + … + p_k log 1/p_k. 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 ${\displaystyle H}$

${\displaystyle H(I)=\log _{2}(N)-\sum _{i}p_{i}\log _{2}(n_{i})=-\sum _{i\in I}p_{i}\log _{2}(n_{i}/N)=-\sum _{i\in I}p_{i}\log _{2}(p_{i})}$

kun ${\displaystyle p_{i}={\frac {n_{i}}{N}}}$ la probablo asociita al la apero de la evento ${\displaystyle i}$ kaj sekvas:

${\displaystyle H\left(I\right)=-\sum _{i\in I}p_{i}\log _{2}\;p_{i}\ \,.}$

• angle (PDF) C. E. Shannon A Mathematical Theory of Communication (angle). L’Institut d’électronique et d’informatique Gaspard-Monge. (Represita kun korektoj el Bell System Technical Journal, Vol. 27, paĝo, 623–656, Julio, oktobro, 1948.)
• https://fr.wikipedia.org/wiki/R%C3%A9f%C3%A9rence:Elements_of_Information_Theory Eldonejo Wiley-Interscience, ISBN 978-0-471-24195-9 (angle)
• http://www.inference.org.uk/mackay/itila/ 16 videoj de prelegoj de David MacKay (angle)

• Video pri la entropio en la informteorio (france)

Portalo pri Komputiko

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