Készítette: Fegyverneki Sándor. Miskolci Egyetem, 2002

´ OELM ´ ´ INFORMACI ELET

¨ Osszefoglal´ o – seg´edlet

K´esz´ıtette: Fegyverneki S´andor

Miskolci Egyetem, 2002.

i

Fegyverneki S´andor: Inform´aci´oelm´elet

´ TARTALOMJEGYZEK 1. Bevezet´es

1

2. Az inform´aci´ omennyis´eg

6

3. Az I-divergencia

13

3.1 Inform´ aci´ o ´es bizonytalans´ag

13

3.2 A sztochasztikus f¨ ugg˝ os´eg m´er´ese

16

3.3 Urnamodellek

18

4. Forr´ ask´ odol´ as

22

5. Csatornakapacit´ as

32

6. Csatornak´ odol´ as

42

7. Folytonos eset

47

¨ ´ FUGGEL EK

51

´ IRODALOMJEGYZEK

58

ii

Fegyverneki S´andor: Inform´aci´oelm´elet

´ 1. BEVEZETES A statisztikai h´ırk¨ ozl´eselm´eletet h´arom f˝o ter¨ uletre szok´as osztani: inform´aci´ oelm´elet, jeldetekt´alas ´es sztochasztikus sz˝ ur´es. Jeldetekt´ al´ as: Legyen {ξt , t ∈ T } a megfigyelt sztochasztikus jel. A H0 hipot´ezis eset´en {ξt , t ∈ T } egy mintaf¨ uggv´eny az Nt sztochasztikus zajb´ol, m´ıg a H1 eset´en az St + Nt jel+zaj folyamatb´ol. A megfigyel˝o d¨ ont valamelyik hipot´ezis jav´ ara felhaszn´alva egy megfelel˝o optimalit´asi krit´eriumot, pl. egy teszt statisztik´at. Sztochasztikus filtr´aci´ o: ez nem m´as, mint a jelek, adatok sz˝ ur´ese, azaz a megfigyelt jel, adatsor transzform´al´asa valamilyen szempontok szerint. Az inform´aci´ o fogalma k¨ozponti szerepet j´atszik az egyes ember ´es a t´arsadalom ´elet´eben, ´es tudom´anyos kutat´asban. Mindennapi ´elet¨ unk minden pillanat´aban az inform´aci´ o megszerz´es, tov´abbad´as, t´arol´as probl´em´ aj´ aval vagyunk elfoglalva. Term´eszetesen m´as ´es m´as a jelent´ese ugyanannak az inform´aci´ onak a k¨ ul¨onb¨oz˝o felhaszn´al´ok sz´am´ara. Hasonl´ okat mondhatunk az ´eszlel´es, t´arol´as, ´ert´ek stb. eset´eben is. Az adott helyzett˝ol f¨ ugg˝ oen szubjekt´ıven d¨ont¨ unk, haszn´aljuk fel stb. Ez´ert nem foglalkozunk az inform´aci´ o fogalm´aval. Az inform´aci´ oelm´elet szempontj´ab´ol csak az inform´aci´o mennyis´ege az ´erdekes, mint ahogy adatt´arol´ askor is mell´ekes, hogy honnan j¨ottek ´es mit jelentenek az adatok. Csak a c´elszer˝ u elhelyez´es¨ ukr˝ol kell gondoskodni. Napjainkban m´ar el´egg´e vil´agos, hogy konkr´et tartalm´at´ol, megjelen´esi form´aj´ at´ ol ´es felhaszn´al´ as´ at´ol elvonatkoztatva besz´elhet¨ unk az inform´aci´ o sz´amszer˝ u mennyis´eg´er˝ ol, ami ´eppen olyan pontosan defini´al1

Fegyverneki S´andor: Inform´aci´oelm´elet hat´ o ´es m´erhet˝ o, mint b´armely m´as fizikai mennyis´eg. Hossz´ u volt azonban az u ´t, amely ehhez a felismer´eshez vezetett. Mindenekel˝ott azt kell tiszt´azni, hogy mikor van egy´altal´an a k´erd´esnek ´ertelme. Persze mindenkinek van valamilyen – t¨obb´e-kev´esb´e szubjekt´ıv – elk´epzel´ese az inform´aci´ omennyis´eg´enek fogalm´ar´ol, de a k¨oznapi sz´ohaszn´alatban ez altal´ ´ aban az inform´aci´ o konkr´et megjelen´esi form´aj´anak terjedelmess´eg´ehez, m´asr´eszt a hasznoss´ag´ ahoz ´es egy´eb tulajdons´agaihoz kapcsol´odik. Ahhoz, hogy j´ol haszn´alhat´ o m´er˝ osz´amot kapjunk minden esetleges vagy szubjekt´ıv t´enyez˝ ot˝ ol el kell vonatkoztatni. Ezek k¨oz´e soroljuk az inform´ aci´ o konkr´et tartalm´at, form´aj´at ´es mindent, ami a k¨oznyelvben az inform´aci´ o fogalm´ahoz k¨ot˝ odik. Ezt a k¨ony¨ortelen absztrakci´ot az indokolja, hogy az inform´aci´ o megszerz´es´evel, feldolgoz´as´aval, felhaszn´al´as´ aval (t´arol´ as, ´atalak´ıt´ as, tov´ abb´ıt´as) kapcsolatos gyakorlati probl´em´ak k¨ oz¨ ott nagyon sok olyan is akad, melynek megold´as´ahoz (pl. a k´ıv´ant berendez´es vagy elj´ar´ as megtervez´es´ehez) az inform´aci´o sz´amos jellemz˝ oje k¨oz¨ ul kiz´ar´ olag csak a mennyis´eget kell figyelembe venni. Az inform´aci´ o fogalma olyan univerz´alis, annyira ´athatja a mindennapi ´elet¨ unket ´es a tudom´any minden ´ag´at, hogy e tekintetben csak az energiafogalommal hasonl´ıthat´ o ¨ossze. A k´et fogalom k¨oz¨ott t¨obb szempontb´ ol is ´erdekes p´arhuzamot vonhatunk. Ha v´egigtekint¨ unk a kult´ ura, a tudom´any nagy eredm´enyein, a legnagyobb felfedez´eseken, azoknak jelent˝ os r´esz´et k´et vil´agosan elk¨ ul¨ on´ıthet˝o oszt´alyba sorolhatjuk. Az egyik csoportba az energia ´atalak´ıt´as´aval, t´arol´as´aval, tov´abb´ıt´ as´ aval kapcsolatos felfedez´esek tartoznak. Pl. a t˝ uz felfedez´ese, a v´ız´es sz´elenergia felhaszn´al´ asa, egyszer˝ u g´epek kostru´al´asa, az elektromos energia hasznos´ıt´ asa stb. Az egyik csoportba az inform´aci´o ´atalak´ıt´as´aval, t´arol´as´aval, tov´abb´ıt´ as´ aval kapcsolatos felfedez´esek tartoznak. Pl. az ´ır´as, a k¨onyvnyomtat´ as, a t´av´ır´ o, a f´enyk´epez´es, a telefon, a r´adi´o, a telev´ızi´o ´es a sz´am´ıt´og´ep stb. Sz´ amos, az els˝o csoportba tartoz´o felfedez´esnek megvan a p´arja a 2

Fegyverneki S´andor: Inform´aci´oelm´elet m´ asodik csoportban. M´eg egy szempontb´ ol tanuls´ agos p´arhuzamot vonni az energia- ´es az inform´aci´ ofogalom k¨oz¨ ott. Hossz´ u id˝obe telt, am´ıg kialakult az energiamennyis´eg elvont fogalma, amelynek alapj´an a k¨ ul¨onb¨oz˝o megjelen´esi form´ ait, mint pl. a mechanikai energi´at, a h˝oenergi´at, a k´emiai energi´at, az elektromos energi´at stb. ¨ossze lehetett hasonl´ıtani, k¨oz¨os egys´eggel lehetett m´erni. Erre a felismer´esre ´es egyben az energia-megmarad´as elv´enek a meghat´aroz´ as´ ara a XIX. sz´azad k¨ozep´en jutott el a tudom´any. Az inform´aci´ o fogalm´aval kapcsolatban a megfelel˝o l´ep´es csak a XX. sz´ azad k¨ozep´en t¨ort´ent meg. Miel˝ ott r´at´ern´enk az inform´aci´omennyis´eg m´ert´ek´enek kialakul´as´ara, t¨ort´enet´ere meghat´arozzuk, hogy mit is jelent az inform´aci´o absztrakt form´ aban. Inform´ aci´ on ´ altal´ aban valamely v´eges sz´ am´ u ´es el˝ ore ismert lehet˝ os´eg valamelyik´enek a megnevez´es´et ´ertj¨ uk. Nagyon fontos, hogy inform´aci´omennyis´egr˝ol csak akkor besz´elhet¨ unk, ha a lehets´eges alternat´ıv´ ak halmaza adott. De ebben az esetben is csak akkor besz´elhet¨ unk az inform´aci´omennyis´eg defini´al´as´ar´ol, ha t¨omegjelens´egr˝ ol van sz´o, vagyis ha nagyon sok esetben kapunk vagy szerz¨ unk inform´aci´ ot arr´ol, hogy az adott lehet˝os´egek k¨oz¨ ul melyik k¨ovetkezett be. Mindig ez a helyzet a h´ırad´astechnik´aban ´es az adatfeldolgoz´ asban, de sz´amos m´as ter¨ uleten is. Az inform´aci´ omennyis´eg kialakul´as´ahoz a kezdeteket a statisztikus fizika kutat´oi adt´ak meg. Ebb˝ol ad´od´ık a fizik´aban haszn´alatos elnevez´es(pl. entr´ opia). L.Boltzmann (1896), Szil´ard L. (1929), Neumann J. (1932). Tov´ abb´ a, a kommunik´ aci´oelm´elettel foglalkoz´ok: H. Nyquist (1924), R,V.L. Hartley (1928). A h´ırk¨ ozl´es matematikai elm´elet´et C.E. Shannon (1948) foglalta ossze oly m´odon, hogy hamarosan tov´abbi, ugr´asszer˝ ¨ u fejl˝od´es alakuljon ki ezen a ter¨ uleten. M´ar nemcsak az elm´elet alapprobl´em´ait fejti ki, 3

Fegyverneki S´andor: Inform´aci´oelm´elet hanem u ´gysz´ olv´ an valamennyi alapvet˝o m´odszer´et ´es eredm´eny´et tartalmazza. P´ arhuzamosan fejlesztette ki elm´elet´et N. Wiener (1948), amely er˝ osen t´amaszkodott a matematikai statisztik´ara ´es elevezetett a kibernetikai tudom´anyok kifejl˝od´es´ehez. Shannon a k¨ovetkez˝ ok´eppen adta meg az (egyir´any´ u) h´ırk¨ozl´esi rendszer ´altal´ anos modellj´et: forr´ as → k´ odol´ o → csatorna → dek´odol´o → felhaszn´al´o L´ athat´ o, hogy meg kell oldanunk a k¨ovetkez˝o probl´em´akat: Az u ¨zenet leford´ıt´ asa tov´ abb´ıthat´ o form´ara. Az ´erkez˝o jel alapj´an az u ¨zenet biztons´ agos vissza´all´ıt´ asa. A ford´ıt´ as(k´odol´as) legyen gazdas´agos (a dek´ odol´ as is) a biztons´ag megtart´asa mellett. Haszn´aljuk ki a csatorna lehet˝ os´egeit (sebess´eg, kapacit´ as). Term´eszetesen ezek a probl´em´ak m´ar a tervez´esi szakaszban felmer¨ ulnek. Viszont gyakran ker¨ ul¨ unk szembe azzal, hogy a m´ar megl´ev˝o rendszer jellegzetess´egeit, kapacit´ asait kell optim´alisan kihaszn´alni. Sz´amos sz´am´ıt´ astechnikai p´elda van arra, hogy a biztons´agos ´atvitel mennyire lelass´ıtja az adat´araml´ ast. Tov´abb´a egy ,, j´o” k´odol´as hogyan v´altoztatja az u ¨zenet terjedelm´et, a felhaszn´al´as gyorsas´ag´at. Az inform´aci´ oelm´eletet k´et nagy ter¨ uletre bonthatjuk: az algebrai k´ odol´ aselm´elet ´es a Shannon-f´ele val´osz´ın˝ us´egsz´am´ıt´ason alapul´o elm´elet. Az inform´aci´ oelm´elettel foglalkoz´ok a k¨ovetkez˝o h´arom k´erd´es aval foglalkoznak: Mi az inform´aci´o? Melyek az ,, mennyis´egi” vizsg´alat´ inform´aci´ o´ atvitel pontoss´ ag´ anak a korl´atai? Melyek azok a m´odszertani ´es kisz´am´ıt´ asi algoritmusok, amelyek a gyakorlati rendszerek eset´en a h´ırk¨ ozl´es ´es az inform´aci´ ot´ arol´ as a megval´os´ıt´as sor´an megk¨ozel´ıti az el˝ obb eml´ıtet pontoss´ agi, hat´ekonys´agi korl´atokat? Az eddigiek alapj´an a jegyzet anyag´at a k¨ovetkez˝o t´emak¨or¨okben foglalhatjuk ¨ossze: Az inform´aci´ omennyis´eg´enek m´er´ese ´es ennek kapcso4

Fegyverneki S´andor: Inform´aci´oelm´elet lata m´as matematikai ter¨ uletekkel. A h´ırk¨ozl´esi rendszerek matematikai modellje(zajos, zajmentes vagy diszkr´et, folytonos). K´odol´aselm´elet (zajos, zajmentes; forr´as, csatorna).

5

Fegyverneki S´andor: Inform´aci´oelm´elet

´ OMENNYIS ´ ´ 2. AZ INFORMACI EG A bevezet´es alapj´an inform´aci´ on valamely v´eges sz´am´ u ´es el˝ore ismert lehet˝os´eg valamelyik´enek a megnevez´es´et ´ertj¨ uk. K´erd´es: Mennyi inform´aci´ ora van sz¨ uks´eg egy adott X = {x1 , x2 , . . . , xn } v´eges halmaz valamely tetsz˝oleges elem´enek azonos´ıt´as´ahoz vagy kiv´alaszt´ as´ ahoz? Tekints¨ uk p´eld´ aul a j´olismert hamis p´enz probl´em´at. Itt k´etserpeny˝ os m´erleg seg´ıts´eg´evel kell kiv´alasztani a k¨ uls˝ore teljesen egyforma p´enzdarabok k¨oz¨ ul a k¨onnyebb hamisat. Ez u ´gy t¨ort´enhet, hogy azonos darabsz´ am´ u csoportokat t´eve a m´erlegre, meg´allap´ıtjuk, hogy a keletkezett h´arom csoportb´ol melyikben van a hamis. Ha ugyanis a m´erleg egyens´ ulyban van, akkor a marad´ekban van, ha nem, akkor a k¨onnyebb csoportban. Ez az elj´ar´ as addig folytat´odik, am´ıg megtal´aljuk a hamis p´enzdarabot. Ha n = 3k alak´ u a p´enzdarabok sz´ama, akkor ´atlagosan k m´erlegel´esre van sz¨ uks´eg, de ´atlagosan enn´el kevesebb m´ar nem vezethet mindig eredm´enyre. ´ Megjegyz´ es: Altal´ aban legal´abb log3 n m´erlegel´esre van sz¨ uks´eg, ami ¨osszef¨ ugg azzal, hogy egy m´erlegel´esnek 3 kimenetele van. A probl´ema tov´ abbi vizsg´alat´ara m´eg visszat´er¨ unk, viszont el˝otte tekints¨ uk a k¨ovetkez˝ o egyszer˝ u probl´em´at: H´ any bin´ aris sz´ amjegy sz¨ uks´eges egy n elem˝ u halmaz elemeinek azonos´ıt´ as´ ahoz? P´ elda: Az amerikai hadseregn´el ´all´ıt´olag u ´gy v´egzik a v´erbajosok felkutat´ as´ at, hogy az eg´esz t´arsas´ agt´ol v´ert vesznek, ´es a p´aciensek fel´e6

Fegyverneki S´andor: Inform´aci´oelm´elet nek v´er´eb˝ ol egy r´eszt ¨ossze¨ ontve elv´egzik a Wassermann-pr´ob´at. Amelyik f´eln´el ez pozit´ıv, ott a felezget´est tov´abb folytatj´ak eg´esz addig, am´ıg a betegeket ki nem sz˝ urt´ek. Ez a m´odszer nagyon gazdas´agos, mert ha 1000 p´aciens k¨oz¨ ott pontosan egy v´erbajos van, akkor az 10 vizsg´alattal lokaliz´alhat´ o, m´ıg az egyenk´enti vizsg´alatn´al – ami adminisztr´aci´os szempontb´ ol persze sokkal egyszer˝ ubb – ´atlagosan 500 pr´ob´ara van sz¨ uks´eg. Hartley(1928) szerint az n elem˝ u X halmaz elemeinek azonos´ıt´as´ahoz I = log2 n mennyis´eg˝ u inform´aci´ ora van sz¨ uks´eg. Ennek az a szeml´eletes tartalma, hogy ha n = 2k alak´ u, akkor k k = log2 n hossz´ us´ ag´ u bin´aris sorozat sz¨ uks´eges. Ha n 6= 2 alak´ u, akkor [log2 n] + 1 ([·] az eg´eszr´eszt jel¨oli) a sz¨ uks´eges bin´aris jegyek sz´ama. Tov´ abb´ a, ha azt tekintj¨ uk, hogy az ´altalunk vizsg´alt esetek valamely t¨ omegjelens´eghez tartoznak, akkor az a k´erd´es, hogy az X elemeib˝ol ´all´o tetsz˝ olegesen hossz´ u sorozatok hogyan ´ırhat´ok le bin´aris sorozatokkal. Tekints¨ unk az m hossz´ us´ ag´ u X elemeib˝ol ´all´o sorozatokat, akkor m k−1 m ezek sz´ama n . Ha 2 < n ≤ 2k , akkor az X halmaz egy elem´ere k es˝ o bin´aris jegyek sz´ama . Ekkor m log2 n ≤

1 k < log2 n + , m m

azaz m n¨ ovel´es´evel log2 n tetsz˝olegesen megk¨ozel´ıthet˝o. Ezek szerint, Hartley formul´ aja az inform´aci´o mennyis´eg´et a megad´ ashoz sz¨ uks´eges ´alland´ o hossz´ us´ag´ u bin´aris sorozatok als´o hat´arak´ent defini´ alja. Ennek megfelel˝oen, az inform´aci´omennyis´eg egys´eg´et bitnek nevezz¨ uk, ami val´ osz´ın˝ uleg a ”binary digit” angol nyelv˝ u kifejez´es r¨ovid´ıt´ese. Hartley szerint a k´et elem˝ u halmaz elemeinek azonos´ıt´as´ahoz van sz¨ uks´eg egys´egnyi (1bit) mennyis´eg˝ u inform´aci´ora. N´eh´any szerz˝o az e alap´ u 7

Fegyverneki S´andor: Inform´aci´oelm´elet term´eszetes logaritmust prefer´alja, ekkor az egys´eg a nat. A logaritmusok k¨ oz¨ otti ´atv´ alt´ as alapj´an 1bit = ln 2nat. Hartley egyszer˝ u formul´ aja sz´amos esetben j´ol haszn´alhat´o, de van egy komoly hib´aja: nem veszi figyelembe, hogy – t¨omegjelens´egr˝ol l´ev´en sz´ o – az egyes alternat´ıv´ ak nem felt´etlen¨ ul egyen´ert´ek˝ uek. P´eld´ aul, nem sok inform´aci´ ot nyer¨ unk azzal, hogy ezen a h´eten sem nyert¨ unk a lott´on, mert ezt el˝ore is sejthett¨ uk volna, hiszen rendszerint ez t¨ort´enik. Ezzel szemben az ¨ot¨ os tal´alat h´ıre rendk´ıv¨ ul meglep˝o, mert igaz´ an nem sz´am´ıthatunk r´a, ez´ert az sokkal t¨obb inform´aci´ot szolg´altat. Ezt a neh´ezs´eget Shannon(1948) a val´osz´ın˝ us´eg ´es az inform´aci´o fogalm´ anak ¨osszekapcsol´ as´ aval oldotta meg. Shannon szerint egy P (A) val´ osz´ın˝ us´eg˝ u A esem´eny bek¨ovetkez´ese I = log2

1 P (A)

mennyis´eg˝ u inform´aci´ ot szolg´altat. Ez a m´er˝osz´am a Hartley-f´el´en´el sokkal ´arnyaltabb megk¨ ul¨ onb¨ oztet´est tesz lehet˝ov´e, ´es ha az n lehet˝os´eg 1 mindegyike egyform´an val´ osz´ın˝ us´eg˝ u, akkor Hartley-f´ele formul´ara ren duk´ al´ odik. A tov´ abbiakban el˝osz¨ or megvizsg´aljuk, hogy mennyire term´eszetes a Shannon ´altal bevezetett m´er˝ osz´am. Az eddigiek alapj´an a k¨ovetkez˝o tulajdons´agokat v´arjuk el az inform´aci´omennyis´eg m´er˝osz´am´at´ol: 1. Additivit´ as: Legyen n = N M alak´ u, azaz fel´ırhat´o k´et term´eszetes sz´am szorzatak´ent. Ekkor X felbonthat´o N darab diszjunkt M elem˝ u N [ halmaz uni´ oj´ ara, azaz X = Ei . Ez azt jelenti, hogy az azonos´ıt´asa i=1

az elemeknek u ´gy is t¨ort´enhet, hogy el˝osz¨or az Ei halmazok egyik´et azonos´ıtjuk, s ut´ana az Ei halmazon bel¨ ul t¨ort´enik az azonos´ıt´as. Eml´ekezz¨ unk vissza a hamis p´enz probl´em´ara. Ekkor elv´arhat´o, hogy a k´et sz´ am´ıt´ asi m´od alapj´an az inform´aci´omennyis´egek megegyezzenek, azaz I(N M ) = I(N ) + I(M ). 8

Fegyverneki S´andor: Inform´aci´oelm´elet Megjegyz´ es: Ez a tulajdons´ag f¨ uggetlens´egk´ent is fel´ırhat´o, mert k´et egym´ast´ ol f¨ uggetlen¨ ul elv´egzett azonos´ıt´as ¨osszekapcsol´as´anak felel meg. 2. Monotonit´ as: A lott´os p´elda alapj´an elv´arhat´o, hogy kisebb val´ osz´ın˝ us´eg˝ u esem´eny bek¨ovetkez´ese nagyobb inform´aci´omennyis´eg˝ u legyen. Ebb˝ol viszont r¨ogt¨ on k¨ovetkezik, hogy az inform´aci´omennyis´eg csak a val´ osz´ın˝ us´egt˝ ol f¨ ugg. L´etezik f f¨ uggv´eny, hogy az A esem´eny val´ osz´ın˝ us´eg´ehez rendelt I(A) = f (P (A)). Hiszen P (A) = P (B) eset´en I(A) = I(B), mert ha P (A) ≤ P (B), akkor I(A) ≥ I(B), m´ıg ha P (A) ≥ P (B), akkor I(A) ≤ I(B). 1 3. Norm´ al´ as: Legyen I(A) = 1, ha P (A) = . Ez ¨osszhagban van 2 azzal, hogy egy k´etelem˝ u halmaz elemeinek az azonos´ıt´as´ahoz pontosan 1bit inform´aci´ ora van sz¨ uks´eg. ´ 2.1.TETEL: Ha f : (0, 1] → R ´es (1) f (p) ≥ f (q), ha p ≤ q, (2) 1 1 f (pq) = f (p) + f (q), (3) f ( ) = 1, akkor f (p) = log2 . 2 p 1 Bizony´ıt´ as: Az x = log2 jel¨ol´essel az ´all´ıt´asunk alakja: f (2−x ) = p x, ha x ≥ 0. Ezt fogjuk bizony´ıtani. A (2) felt´etel alapj´an f (pn ) = nf (p) (n ∈ N), ami teljes indukci´oval 1 egyszer˝ uen bel´athat´ o. Ezt alkalmazva a p = esetre kapjuk, hogy 2 f (2−n ) = n. Tov´ abb´ a, à n !m à n! 2−n =

−

, azaz f (2−n ) = mf

2 m

ekkor

à f

−

2 m

,

n! n 2 m = . m −

Teh´ at b´armely 0 < x racion´alis sz´amra f (2−x ) = x. Ha x = 0, akkor 1 1 1 = f ( 20 ) = f ( ) + f (20 ) = 1 + f (1), 2 2 9

azaz f (1) = 0.

Fegyverneki S´andor: Inform´aci´oelm´elet Ha x > 0 irracion´alis, akkor minden m ∈ N eset´en l´etezik n ∈ N, hogy n n+1 ≤x< . m m Ekkor n =f m

  n+1 n! − n+1 2 m ≤ f (2−x ) ≤ f 2 m  = , m

Ã

−

amelyb˝ ol m → ∞ eset´en k¨ovetkezik, hogy f (2−x ) = x, ha x ≥ 0, azaz 1 ¦ f (p) = log2 . p 1 2.1.Defin´ıci´ o: Az I(ξ = x) = log2 mennyis´eget a ξ val´osz´ıP (ξ = x) n˝ us´egi v´altoz´ o x ´ert´eke ´altal tartalmazott egyedi inform´ aci´ omennyis´egnek nevezz¨ uk. 2.2.Defin´ıci´ o: A P = {p1 , p2 , . . . , pn } eloszl´as´ u ξ val´osz´ın˝ us´egi v´altoz´o Shannon-f´ele entr´ opi´ aj´ anak nevezz¨ uk a H(ξ) = −

n X

pi log2 pi

i=1

mennyis´eget. Megjegyz´ es: A val´ osz´ın˝ us´egek k¨oz¨ott a 0 is el˝ofordulhat, ´ıgy probl´em´ at okozhat hiszen a logaritmus f¨ uggv´eny csak pozitiv sz´amokra ´ertelmezett. Ezt azonban megoldja az, hogy az x log2 x f¨ uggv´eny folytonosan kiterjeszthet˝ o a null´ ara, mert lim x log2 x = 0,

x→0+0

azaz

0 log2 0 = −0 log2

1 =0 0

lehet defin´ıci´ o szerint (l. F¨ uggel´ek). Vegy¨ uk ´eszre, hogy a H(ξ) mennyis´eg nem m´as, mint az egyedi inform´ aci´ omennyis´eg v´arhat´ o ´ert´eke. 10

Fegyverneki S´andor: Inform´aci´oelm´elet Ha nem okoz zavart, akkor az entr´opia jel¨ol´es´ere m´eg a k¨ovetkez˝oket is fogjuk haszn´alni: H(ξ) = H(P) = Hn (p1 , p2 , . . . , pn ) = H(p1 , p2 , . . . , pn ). ´ 2.2.TETEL: (Az entr´ opia tulajdons´ agai:) 1. Hn (p1 , p2 , . . . , pn ) ≥ 0. Bizony´ıt´ as: Az ¨osszeg minden tagja nemnegat´ıv. 2. Ha pk = 1 ´es pi = 0 (1 ≤ i ≤ n, i 6= k), akkor Hn (p1 , p2 , . . . , pn ) = 0. 3. Hn+1 (p1 , p2 , . . . , pn , 0) = Hn (p1 , p2 , . . . , pn ). ¶ µ 1 1 1 , ,..., 4. Hn (p1 , p2 , . . . , pn ) ≤ Hn = log2 n. n n n Bizony´ıt´ as: A − log2 x konvex f¨ uggv´enyre alkalmazzuk a Jensenegyenl˝ otlens´eget. 5. H(ξ) folytonos f¨ uggv´eny. 6. Hn (p1 , p2 , . . . , pn ) szimmetrikus a val´osz´ın˝ us´egekben. 7. Ha qn = p1 + p2 + . . . + pm , akkor Hn+m−1 (q1 , q2 , . . . , qn−1 , p1 , p2 , . . . , pm ) = p1 p2 pm = Hn (q1 , q2 , . . . , qn ) + qn Hm ( , , . . . , ). qn qn qn Bizony´ıt´ as: Megjegyz´ es: Az entr´ opia axiomatikus sz´armaztat´asa: Ha a fenti tulajdons´agok k¨oz¨ ul megk¨ovetelj¨ uk, hogy (1) H(P) folytonos a P eloszl´ asban; 1 (2) A pi = (1 ≤ i ≤ n) esethez tartoz´o H monoton n¨ovekv˝o az n n f¨ uggv´eny´eben; 11

Fegyverneki S´andor: Inform´aci´oelm´elet ¯ = 1 − λ, akkor (3) Ha 0 ≤ λ ≤ 1, λ ¯ n ) = Hn (p1 , p2 , . . . , pn ) + pn H2 (λ, λ). ¯ Hn+1 (p1 , p2 , . . . , λpn , λp

12

Fegyverneki S´andor: Inform´aci´oelm´elet

3. Az I-divergencia 3.1 Inform´ aci´ o´ es bizonytalans´ ag Egy v´eletlent˝ ol f¨ ugg˝ o kimenetel˝ u k´ıs´erlet eredm´enye t¨obb-kevesebb m´ert´ekben bizonytalan. A k´ıs´erlet elv´egz´es´evel ez a bizonytalans´ag megsz˝ unik. A k´ıs´erlet eredm´eny´ere vonatkoz´o, erdetileg fenn´all´o bizonytalans´ agot m´erhetj¨ uk azzal az inform´aci´omennyis´eggel, amit a k´ıs´erlet elv´egz´es´evel (´atlagban) nyer¨ unk. A bizonytalans´agot teh´at felfoghatjuk, mint inform´aci´ o hi´anyt, vagy megford´ıtva: az inform´aci´ot u ´gy, mint a bizonytalans´ ag megsz¨ untet´es´et. Az inform´aci´o bet¨olt´ese ekvivalens a bizontalans´ ag megsz¨ untet´es´evel, azaz inform´ aci´ o bet¨ olt´es=a-priori bizonytalans´ ag – a-posteriori bizonytalans´ ag. A k´et fogalom viszony´ at j´ol vil´ag´ıtja meg a k¨ovetkez˝o p´elda: Ha egy A esem´eny val´ osz´ın˝ us´ege eredetileg p, de a B esem´eny megfigyel´ese ut´an q-ra v´altozott (azaz P (A) = p ´es P (A|B) = q), akkor log2

1 q 1 − log2 = log2 p q p

inform´aci´ ot nyert¨ unk (vagy vesztett¨ unk). Teh´at log2 erezt¨ unk A-ra n´ezve. Vegy¨ uk ´eszre, hogy log2

q inform´aci´ot szp

q P (A|B) P (A ∩ B) P (B|A) = log2 = log2 = log2 . p P (A) P (A)P (B) P (B)

Tov´ abb´ a, hogy az inform´aci´ onyeres´eg 0, ha A ´es B f¨ uggetlenek. Egy K k´ıs´erlet lehets´eges kimeneteleinek egy teljes esem´enyrendszere legyen az A1 , A2 , . . . , An , amelyek (a-priori) val´osz´ın˝ us´ege pi = P (Ai ) 13

Fegyverneki S´andor: Inform´aci´oelm´elet sz´ amok (i = 1, 2, . . . , n). Megfigyelt¨ uk egy B esem´eny bek¨ovetkez´es´et, ´ amely kapcsolatban ´all a K k´ıs´erlettel. Ugy azon felt´etel mellett, hogy B bek¨ovetkezett, az Ai esem´enyek felt´eteles (a-posteriori) val´osz´ın˝ us´egei elt´ernek ezek eredeti (a-priori) val´ osz´ın˝ us´egeit˝ol, m´egpedig P (Ai |B) = qi . K´erd´es: mennyi inform´aci´ ot nyert¨ unk a B esem´eny megfigyel´ese altal a K k´ıs´erlet v´arhat´ ´ o kimenetel´ere n´ezve? Tudjuk, hogy P = {pi } ´es Q = {qi } eloszl´asok. Ha nem azonosak, akkor l´etezik olyan Ak esem´eny, amelyre pk > qk ( a bizonytalans´ag cs¨ okkent) ´es olyan is, amelyre pk < qk (a bizonytalans´ag n˝ott). Az inform´ aci´ onyeres´eg v´arhat´ o ´ert´eke: D(Q||P) =

n X

qi log2

i=1

qi . pi

Ezt a mennyis´eget a B esem´eny megfigyel´ese ´altal kapott a K k´ıs´erletre vonatkoz´ o Shannon-f´ele inform´ aci´ omennyis´eg´enek vagy a P eloszl´asnak a Q eloszl´assal val´ o helyettes´ıt´es´enel fell´ep˝o inform´aci´onyeres´egnek nevezz¨ uk. P´ elda: Egy v´alaszt´ ason n p´ art ind´ıt jel¨oltet. El˝ozetes elk´epzel´es¨ unk az, hogy az egyes p´artok jel¨oltjeire a leadott szavazatokb´ol p1 , p2 , . . . , pn r´esz esik. A v´alaszt´ as ut´an megismerj¨ uk a t´enyleges q1 , q2 , . . . , qn szavazati ar´anyokat. Az a h´ır, amely ezt az inform´aci´ot sz´all´ıtotta inform´ aci´ omennyis´eget juttata birtokunkba, amely mennyis´eg jellemzi azt, hogy az eredeti elk´epzel´es¨ unkt˝ ol milyen messze ´all a val´os´ag. Teh´at felfoghat´ o a k´et eloszl´as k¨oz¨ otti elt´er´es m´er˝osz´amak´ent is. Megjegyz´ es: Az eloszl´asok k¨oz¨otti elt´er´esek m´er˝osz´am´ara sokf´ele pr´ ob´ alkoz´ as t¨ort´ent (Hellinger(1926), Kolmogorov(1931), Mises(1931), Pearson(1905) stb.) Az inform´aci´ omennyis´eghez k¨ot˝od˝ot a D(Q||P) diszkrimin´ al´ o inform´aci´ ot Kullback ´es Leibler(1951) vezette be hipot´ezis14

Fegyverneki S´andor: Inform´aci´oelm´elet vizsg´ alat felhaszn´al´ as´ aval. Szok´asos elnevez´es m´eg az inform´aci´o divergencia vagy I-divergencia. ´ 3.1.TETEL: (Az I-divergencia tulajdons´ agai:) 1. D(Q||P) ≥ 0, egyenl˝ os´eg akkor ´es csak akkor, ha pi = qi (1 ≤ i ≤ n). Bizony´ıt´ as: µ ¶ n qi qi 1 X D(Q||P) = qi log2 qi 1 − = ≥ p ln 2 p i i i=1 i=1 Ã n ! n X X 1 = qi − pi = 0. ln 2 i=1 i=1 n X

2. Ha qk = 1 ´es qi = 0 (1 ≤ i ≤ n, i 6= k), akkor D(Q||P) = log2

1 . pk

3. D(Q||P) nem szimmetrikus. Bizony´ıt´ as: Tekints¨ uk p´eld´ aul azt az esetet, amikor pk = 1 ´es pi = 0

(1 ≤ i ≤ n, i 6= k).

4. D(Q||P) folytonos f¨ uggv´eny. 5. D(Q||P) konvex f¨ uggv´enye a P eloszl´asnak a Q r¨ogz´ıt´ese eset´en. 6. D(Q||P) konvex f¨ uggv´enye a Q eloszl´asnak a P r¨ogz´ıt´ese eset´en. 7. Legyenek Q1 ´es Q2 illetve P1 ´es P2 f¨ uggetlenek, ekkor D(Q1 × Q2 ||P1 × P2 ) = D(Q1 ||P1 ) + D(Q2 ||P2 ). 8. Ha qk =

mk X

qkj ´es pk =

j=1

mk X

pkj (k = 1, . . . , n), akkor

j=1

mk n X X k=1

n

X qkj qk qkj log2 ≥ qk log2 , pkj pk j=1 k=1

15

Fegyverneki S´andor: Inform´aci´oelm´elet azaz a feloszt´as (particion´al´ as) finom´ıt´asa nem cs¨okkenti a diszkrimin´al´o inform´aci´ ot. Egyenl˝ os´eg akkor ´es csak akkor, ha b´armely k ´es j eset´en qkj pkj = . qk pk Bizony´ıt´ as: Az u ´n. log-szumma egyenl˝otlens´eg alapj´an bizony´ıtunk. Legyen a1 , . . . , an ´es b1 , . . . , bn mindegyike nemnegat´ıv, tov´abb´a n X

n X

ai = a ´es

i=1

ekkor

bi = b > 0,

i=1

n X

ai log2

i=1

ai a ≥ a log2 . bi b

ai bi = . a b Ha a = 0, akkor az ´all´ıt´ as nyiln´anval´o. Ha a 6= 0, akkor legyen

Egyenl˝ os´eg akkor ´es csak akkor, ha b´armely 1 ≤ i ≤ n eset´en

ai bi qi = , pi = , a b

´es

n X

ai log2

i=1

ai a − a log2 = aD(Q||P) ≥ 0. bi b

Megjegyz´ es: Legyen L(Q||P) =

n X

qi log2 pi , ekkor D(Q||P) =

i=1

−H(Q − L(Q||P).

Ha Q r¨ogz´ıtett, akkor D(Q||P) minim´alis, ha L(Q||P) maxim´alis, ez´ert ezt maximum likelihood feledatnak nevezz¨ uk. Szok´asos elnevez´es L(Q||P) kifejez´esre a likelihood illetve a T (Q||P) = −L(Q||P) kifejez´esre az inakkurancia. Ha P r¨ogz´ıtett, akkor D(Q||P) minimaliz´al´asa a minimum diszkrimin´ al´ o inform´aci´ o feladat. 3.2 A sztochasztikus f¨ ugg˝ os´ eg m´ er´ ese 16

Fegyverneki S´andor: Inform´aci´oelm´elet A sztochasztikus f¨ uggetlens´eg ellent´ete a sztochasztikus f¨ ugg˝os´eg, ami azonban nem ´ırhat´ o le olyan egy´ertelm˝ uen, mint az el˝obbi, hiszen nem csak egy eset lehets´eges, ez´ert a f¨ ugg˝os´eg er˝oss´eg´enek jellemz´es´ere megpr´ ob´ alunk bevezetni egy m´er˝ osz´amot. Legyen A ´es B k´et esem´eny, amelyre P (A) = a ´es P (B) = b, Tov´ abb´ a C1 = A ∩ B, C2 = A ∩ B , C3 = A ∩ B, C4 = A ∩ B . A {Ci } teljes esem´enyrendszerhez k´etf´elek´eppen kapcsolunk val´osz´ın˝ us´egeket: a-priori felt´etelezz¨ uk, hogy f¨ uggetlenek (P (Ci ) = pi ) ´es aposteriori meghat´arozzuk (megfigyel´es, becsl´es) a P (Ci ) = qi val´osz´ın˝ us´egeket. Ekkor meg tudjuk hat´arozni a k´et eloszl´as elt´er´es´et. 3.1.Defin´ıci´ o: Az A ´es B esem´eny f¨ ugg˝os´egi m´er˝osz´am´anak nevezz¨ uk a D(Q||P) diszkrimin´al´ o inform´aci´ ot. Jele: I(A ∧ B). Ha A ´es B f¨ uggetlenek, akkor p1 = ab, p2 = a(1 − b), p3 = (1 − a)b, p4 = (1 − a)(1 − b). Ha P (A ∩ B) = x, akkor q1 = x, q2 = a − x, q3 = b − x, q4 = 1 − a − b + x. Teh´ at x (a − x) + (a − x) log2 + ab a(1 − b) (b − x) (1 − a − b + x) + (b − x) log2 + (1 − a − b + x) log2 . b(1 − a) (1 − a)(1 − b)

I(A ∧ B) = x log2

Vizsg´aljuk meg I(A ∧ B) viselked´es´et: 1. D(Q||P) ≥ 0, ´ıgy I(A ∧ B) ≥ 0. 2. I(A ∧ B) = I(B ∧ A), azaz szimmetrikus. 17

Fegyverneki S´andor: Inform´aci´oelm´elet 3. Ha a ´es b r¨ ogz´ıtett, akkor max{0, a + b − 1} ≤ x ≤ min{a, b}. Legyen u = max{0, a + b − 1} ´es v = min{a, b}, azaz u ≤ x ≤ v. Ez az intervallum sohasem u ¨res, hiszen ab ∈ [u, v]. Innen az is k¨ovetkezik, hogy x mindig megv´alaszthat´ ou ´gy, hogy I(A ∧ B) minimuma el´eressen. 4. Legyen f (x) = I(A ∧ B) ln 2, ekkor x(1 − a − b + x) , (a − x)(b − x) 1 1 1 1 f 00 (x) = + + + . x 1−a−b+x a−x b−x f 0 (x) = ln

Ebb˝ ol ad´odik, hogy f konvex, f 0 monoton n¨ovekv˝o. K¨onnyen bel´athat´o, hogy lim f 0 (x) = −∞, lim f 0 (x) = +∞ ´es f 0 (ab) = 0.

x→u+0

x→v−0

3.2.Defin´ıci´ o: Ha A1 , A2 , . . . , An ´es B1 , B2 , . . . , Bm teljes esem´enyrendszerek, amelyekre P (Ai ) = qi (1 ≤ i ≤ n), P (Bj ) = rj (1 ≤ j ≤ m) ´es P (Ai ∩ Bj ) = pij . Ekkor a {Ai } ´es {Bj } teljes esem´enyrendszerek sztochasztikus ¨osszef¨ ugg´es´enek m´er˝osz´ama I({Ai }, {Bj }) =

n X m X i=1 j=1

pij log2

pij . qi rj

Ezt a m´er˝ osz´ amot k¨olcs¨ on¨ os inform´aci´omennyis´egnek nevezz¨ uk. Megjegyz´ es: A teljes esem´enyrendszerek alapj´an ´at´ırhat´o val´osz´ın˝ us´egi v´altoz´ okra. Jele: I(ξ ∧ η). 3.3 Urnamodellek Egy urn´aban n k¨ ul¨ onb¨ oz˝ o fajt´aj´ u goly´o van. Legyenek ezek a t´ıpusok a1 , a2 , . . . , an . Az ai t´ıpus kih´ uz´ asa jelentse az Ai esem´enyt ´es tudjuk, 18

Fegyverneki S´andor: Inform´aci´oelm´elet hogy P (Ai ) = pi (1 ≤ i ≤ n). H´ uzzunk az urn´ab´ol visszatev´essel K-szor. Ekkor Ω = {ω|ω = (ai1 , . . . , aiK } azaz |Ω| = nK . ki (1 ≤ i ≤ n), ahol ki az Ai esem´eny K bek¨ovetkez´eseinek a sz´ama egy adott ω ∈ Ω elemi esem´eny(minta) eset´en. Az ω ∈ Ω minta (K, ε) tipikus (”j´o”), ha |ˆ pi − pi | < ε minden 1 ≤ i ≤ n eset´en.

3.3.Defin´ıci´ o:

Legyen pˆi =

Megjegyz´ es: A j´o mint´ ak val´osz´ın˝ us´ege k¨ozel azonosnak tekinthet˝ o: P (ω) = pk11 pk22 · . . . · pknn . n n n X X X ki 1 1 log2 P (ω) = ki log2 pi = −K log2 = −K pˆi log2 . K pi pi i=1 i=1 i=1 ¯ ¯ ¯ ¯ ¯ ¯ n n n n ¯X ¯X X 1 ¯¯ 1 ¯¯ 1 1 ¯¯ ¯¯X ¯ ¯ pi − pi ) log2 ¯ < ε ¯ log2 ¯ , pˆi log2 − pi log2 ¯ = ¯ (ˆ ¯ ¯ ¯ pi i=1 pi ¯ ¯ i=1 pi ¯ pi ¯ i=1 i=1 ¯ ¯ n ¯X 1 ¯¯ ¯ ahol ¯ atos mennyis´eg, ´ıgy log2 ¯ egy korl´ ¯ pi ¯ i=1

P (ω) ≈ 2−KH . Felmer¨ ul a k´erd´es, hogy a tipikus mint´ak mennyire t¨oltik meg az elemi esem´enyek ter´et. Tekints¨ uk r¨ogz´ıtett K, n, ε eset´en az ¨osszes tipikus mint´at. Jel¨olj¨ uk ezt C-vel ´es jel¨olje Bi azt amikor az i-edik t´ıpus´ u goly´o becsl´ese (a relat´ıv gyakoris´ ag) ε-n´al k¨ozelebb van a val´osz´ın˝ us´eghez. Ekkor C = B1 ∩ B2 ∩ . . . ∩ Bn = B1 ∪ B2 ∪ . . . ∪ Bn , ´ıgy ³ P (C) = 1 − P

´ B1 ∪ B2 ∪ . . . ∪ Bn

≥1−

n X i=1

19

P ( Bi ),

Fegyverneki S´andor: Inform´aci´oelm´elet de P (Bi ) → 1 a nagy sz´amok t¨orv´enye ´ertelm´eben. Teh´at a ”j´o” mint´ak osszess´eg´enek val´ ¨ osz´ın˝ us´ege tart egyhez. Az el˝oz˝ oek alapj´an heurisztikusan az v´arhat´o, hogy Ω k´et r´eszre bonthat´ o, amelyb˝ol az egyik val´ osz´ın˝ us´ege kicsi, a m´asik pedig k¨ozel azonos val´ osz´ın˝ us´eg˝ u elemekb´ol ´all. ´ 3.2.TETEL: (McMillan felbont´ asi t´ etel) Legyen adott az el˝oz˝ oek szerint egy urnamodell. R¨ogz´ıtett δ > 0 eset´en l´etezik K0 , ha K > K0 , akkor Ω=F ∪ F , ahol 1.

P ( F ) < δ. ω ∈ F,

¯ ¯ ¯1 ¯ 1 ¯ akkor ¯ log2 − H ¯¯ < δ. K P (ω)

2.

Ha

3.

(1 − δ)2K(H−δ) ≤ |F | ≤ 2K(H+δ) .

Bizony´ıt´ as: Legyen ¯ ¯ ¯ ¯ 1 ¯ F = {ω| ¯log2 − KH ¯¯ < Kδ}, P (ω) azaz teljes´ıtse a 2. felt´etelt. Teh´ at ha ω ∈ F, akkor 2−K(H+δ) ≤ P (ω) ≤ 2−K(H−δ) . Legyen ξ(ω) = − log2 P (ω), ekkor E(ξ) = KH ´es a f¨ uggetlens´eg miatt à n ! ¶2 X µ 1 D2 (ξ) = K pi log2 − H2 . p i i=1 Legyen D2 (ξ) = Kσ 2 , akkor a Csebisev-egyenl˝otlens´eg alapj´an P ( F ) = P (|ξ − KH| > Kδ) ≤ 20

Kσ 2 1 σ2 = < δ, K 2 δ2 K δ2

Fegyverneki S´andor: Inform´aci´oelm´elet ha K0 el´eg nagy. A 3. r´esz bizony´ıt´ as´ ahoz vegy¨ uk ´eszre, hogy 1≥

X ω∈F

P (ω) ≥

X

e−K(H+δ) = |F |e−K(H+δ) ,

ω∈F

amelyb˝ ol ad´odik az ´all´ıt´ as egyik fele. M´asr´eszt P (F ) ≥ 1 − δ, ´ıgy r¨ogt¨on k¨ ovetkezik a m´asik egyenl˝ otlens´eg is.

21

Fegyverneki S´andor: Inform´aci´oelm´elet

´ ´ ´ 4. FORRASK ODOL AS A Shannon-f´ele egyir´any´ u hirk¨ozl´esi modell ´altal´anos alakja: forr´as → k´ odol´ o →csatorna → dek´odol´o → felhaszn´al´o zaj A h´ırk¨ ozl´es feladata eljuttatni az inform´aci´ot a felhaszn´al´ohoz. A t´ avols´ agok miatt az inform´aci´ o tov´ abb´ıt´as´ara valamilyen eszk¨oz¨oket (csatorn´ akat) haszn´alunk, amelyek n´eh´any j´ol meghat´arozott t´ıpus´ u jelet tudnak tov´abb´ıtani. Teh´ at a tov´ abb´ıt´ashoz az inform´aci´ot a csatorna t´ıpus´ anak megfelel˝oen kell ´atalak´ıtani. Ez a k´odol´as, m´ıg a tov´abb´ıt´as ut´ an vett jelekb˝ol az inform´aci´ onak a visszaalak´ıt´as´at dek´odol´asnak. Tov´ abbi probl´ema forr´asa, hogy az ´atvitel sor´an a tov´abb´ıtott jelek megv´ altozhatnak, azaz u ´n. zajos csatorn´aval dolgozunk. Teh´at olyan m´ odszerekre is sz¨ uks´eg van, melyekkel az ilyen zajos csatorn´akon is el´eg megbizhat´ oan vihet˝o ´at az inform´aci´o, ´es amellett az ´atvitel k¨olts´egei, sebess´ege sem g´atolja a haszn´alhat´ os´agot. A h´ırk¨ ozl´es matematikai modellj´eben szerepl˝o r´esztvev˝ok tulajdons´ againak a le´ır´ as´ ara ´es a feladat megold´as´ara haszn´aljuk a k¨ovetkez˝o fogalmakat. Forr´ as: X = {x1 , . . . , xn } – v´eges halmaz, forr´as´ab´ec´e. u ¨zenet eml´ekezetn´elk¨ uli forr´as stacion´ arius forr´as csatorna´ ab´ec´e vagy k´od´ ab´ec´e – Y = {y1 , . . . , ys } csatorna 22

Fegyverneki S´andor: Inform´aci´oelm´elet zajmentes csatorna K´ odol´ asi elj´ar´ as: X – az X-b˝ol k´esz´ıtett v´eges sorozatok halmaza Y – az Y -b´ ol k´esz´ıtett v´eges sorozatok halmaza g:X →Y – bet˝ unk´enti – blokkonk´enti – ´alland´ o hossz – v´altoz´ o hossz A dek´odolhat´ os´ ag: egy´ertelm˝ u dek´odolhat´os´ag, gazdas´agoss´agi szempontok. Egy´ertelm˝ uen dek´odolhat´o – k¨ ul¨onb¨oz˝o k¨ozlem´enyek k´odk¨ ozlem´enyei is k¨ ul¨ onb¨ oz˝ ok. Zajmentes csatorna + bet˝ unk´enti k´odol´as: g:X→Y Megjegyz´ es: g(xi ) = Ki az xi bet˝ uh¨oz rendelt k´odsz´o. Jel¨olje K a k´odszavak halmaz´at. A K k´od prefix, ha a k´odszavak mind k¨ ul¨onb¨oz˝oek ´es egyik k´odsz´o sem folytat´asa a m´asiknak. Megjegyz´ es: Az ´alland´ o k´odhossz´ u k´od mindig prefix, ha a k´odszavai k¨ ul¨ onb¨ oz˝ oek. ´ ´ ´ 4.1.ALL ITAS: Minden prefix k´od egy´ertelm˝ uen dek´odolhat´o. Sardinas-Patterson m´odszer: Legyen K tetsz˝ oleges k´od, amelyben a k´odszavak k¨ ul¨onb¨oz˝oek ´es 00 0 00 nem u ¨resek. A K sz´ o a K sz´o ut´an k¨ovetkezik, ha K 6= ∅ ´es l´etezik 0 00 Ki ∈ K, hogy K K = Ki vagy K 0 = Ki K 00 . A K k´odhoz rekurz´ıve megkonstru´aljuk az Sm , m = 0, 1, 2, . . . hal23

Fegyverneki S´andor: Inform´aci´oelm´elet mazokat. Legyen S0 = K. Az Sm+1 halmazt az Sm halmaz szavai ut´an k¨ ovetkez˝ o szavak halmazak´ent defini´aljuk. ´ ´ ´ 4.2.ALL ITAS: A X k´ od akkor ´es csak akkor egy´ertelm˝ uen dek´odolhat´o, ha az Si , (i ≥ 1) halmazok nem tartalmaznak k´odsz´ot, azaz S0 egy elem´et. Keres´esi strat´egi´ ak ´es prefix k´odok ´ 4.1.TETEL: Az s alternat´ıv´ as keres´esi strat´egi´ara L=

n X

L(xi )P (ξ = xi ) ≥

i=1

H(ξ) . log2 s

Jel¨ ol´esek: A g k´ odol´ as eset´en ||g(xi )|| = Li a g(xi ) k´odsz´o hossza. ´ ´ ´ 4.3.ALL ITAS: A k´odf´ ak ´es a prefix k´odok k¨oz¨ott k¨olcs¨on¨os egy-egy´ertelm˝ u megfeleltet´es van. Megjegyz´ es: A prefix k´od ´atlagos k´odhossza nem lehet kisebb, mint H(ξ) . log2 s ´ 4.2.TETEL: (Kraft-Fano egyenl˝ otlens´ eg.) Ha K = {K1 , . . . , Kn } s sz´ am´ u k´odjelb˝ ol k´esz´ıtett prefix k´od, akkor n X

s−Li ≤ 1,

i=1

ahol Li a Ki k´ odsz´ o hossza. ´ 4.3.TETEL: (Kraft-Fano egyenl˝ otlens´ eg megford´ıt´ asa.) Ha az L1 , . . . , Ln term´eszetes sz´amok eleget tesznek a n X

s−Li ≤ 1

i=1

24

Fegyverneki S´andor: Inform´aci´oelm´elet egyenl˝ otlens´egnek, ahol s ≥ 2 term´eszetes sz´am, akkor l´etezik s k´odjelb˝ol alkotott K = {K1 , . . . , Kn } prefix k´od, melyn´el a Ki k´odsz´o hossza ´eppen Li . ´ 4.4.TETEL: L´etezik prefix k´od, hogy L≤

H(P) + 1. log2 s

Bizony´ıt´ as: konstrukci´ os bizony´ıt´as – Shannon-Fano k´od. Gilbert-Moore k´od: Nincs sz¨ uks´eg sorbarendez´esre. Ekkor L≤

H(P) + 1 + 1. log2 s

4.x1.Defin´ıci´ o: Az egy´ertelm˝ uen dek´odolhat´o k´od hat´asfoka: γ=

H(P) . L log2 s

4.x2.Defin´ıci´ o: A k´odot optim´alisnak nevezz¨ uk, ha egy´ertelm˝ uen dek´ odolhat´ o ´es maxim´alis hat´asfok´ u. ´ ´ ´ Adott P eloszl´as´ 4.4.ALL ITAS: u forr´as´ab´ec´e s sz´am´ u k´odjelb˝ol alkotott egy´ertelm˝ uen dek´odolhat´ o k´odjai k¨oz¨ott mindig van optim´alis. Huffmann-k´ od – maxim´alis hat´asfok´ u prefix k´od. Tulajdons´agok: 1. Monotonit´as. Ha p1 ≥ p2 ≥ . . . ≥ pn , akkor L1 ≤ L2 ≤ . . . ≤ Ln . 2. A k´odfa teljess´ege. Legyen m = Ln , ekkor minden m − 1 hossz´ us´ ag´ u k´odjelsorozat ki van haszn´alva a k´odol´asn´al, azaz maga is k´ odsz´ o vagy egy r¨ovidebb k´odsz´ o kieg´esz´ıt´es´eb˝ol ad´odik, vagy pedig az egyik k´odjel hozz´a´ır´ as´ aval valamelyik m hossz´ us´ag´ u k´odsz´ot kapjuk bel˝ole. Ha volna kihaszn´alatlan ´ag, akkor azt v´alasztva ism´et prefix k´ odot kapn´ ank, melynek viszont kisebb az ´atlagos k´odhossza. 25

Fegyverneki S´andor: Inform´aci´oelm´elet Megjegyz´ es: Optim´ alis, bin´aris k´odfa teljes. 3. Ln = Ln−1 ´es az ut´ols´ o k´odjel¨ ukt˝ol eltekintve azonosak. ¨ Megjegyz´ es: Osszevon´ asi algoritmus. Az optim´alis k´odfa minden v´egpontt´ ol k¨ ul¨ onb¨ oz˝ o sz¨ogpontj´ab´ol s ´el indul ki, kiv´eve esetleg egy v´epont el˝otti sz¨ogpontot, amelyb˝ol r ´el megy tov´abb, ahol 2 ≤ r ≤ s. Ekkor n = k(s − 1) + r. A teljes k´odf´ an´ al r = s. Teh´ at az els˝o ¨osszevon´asi l´ep´esben az r legkev´esb´e val´ osz´ın˝ u elemet kell ¨osszevonni, m´ıg az ¨osszes t¨obbiben az s legkev´esb´e val´ osz´ın˝ ut. ´ 4.5.TETEL: (McMillan-dek´ odol´ asi t´ etel.) Ha g : X → Y egy´ertelm˝ uen dek´odolhat´ o, akkor n X

s−||g(xi )|| ≤ 1.

i=1

Bizony´ıt´ as: Jel¨ olje W (N, L) azon N hossz´ us´ag´ u k¨ozlem´enyeknek a sz´ am´ at, melyek k´odk¨ ozlem´eny´enek a hossza ´eppen L. m := max Li . 1≤i≤n

A bizony´ıt´ as l´ep´esei: 1. A k´od egy´ertelm˝ uen dek´odolhat´o. W (N, L) ≤ sL , azaz W (N, L)s−L ≤ 1. Teh´ at

mN X

W (N, L)s−L ≤ mN.

L=1

2. Teljes indukci´ oval bizony´ıtjuk, hogy à n !N mN X X s−Li . W (N, L)s−L = i=1

L=1

26

Fegyverneki S´andor: Inform´aci´oelm´elet 3. Ha c ´es m adott pozit´ıv sz´amok, akkor az (1 + c)N ≤ mN egyenl˝ otlens´eg nem teljes¨ ulhet minden N term´eszetes sz´amra, ´ıgy n X

s−Li ≤ 1.

i=1

´ ´ ´ 4.5.ALL ITAS: Egy´ertelm˝ uen dek´odolhat´o k´od eset´en L≥

H(P) . log2 s

Bizony´ıt´ as: Legyen qi :=

s−Li . n X s−Lj j=1

Ekkor 0 ≥ −D(Q||P). Blokkos k´odol´ as: g : X k → Y,

L=

L(k) . k

Eml´ekezetn´elk¨ uli, stacion´arius forr´as. Az optim´alis k´odra: H(P (k) ) H(P (k) ) ≤ L(k) ≤ + 1. log2 s log2 s A f¨ uggetlens´egb˝ ol H(P (k) ) = kH(P), 27

Fegyverneki S´andor: Inform´aci´oelm´elet s ´ıgy H(P) H(P) 1 ≤L≤ + . log2 s log2 s k Kompresszi´ o: X = Y,

1≥

H(P) . log2 s

K¨ olcs¨ on¨ os inform´aci´ omennyis´eg: ´ ´ ´ 4.6.ALL ITAS: I(ξ, η) = H(ξ) + H(η) − H(ξ, η) Felt´eteles entr´ opia: H(ξ|η) =

m X

P (η = yj )H(ξ|η = yj )

j=1

H(ξ|η = yj ) =

n X

P (ξ = xi |η = yj ) log2

i=1

1 . P (ξ = xi |η = yj )

H(ξ, η) = H(η) + H(ξ|η) H(ξ) ≥ H(ξ|η) egyenl˝ os´eg f¨ uggetlens´eg eset´en. H(ξ) ≥ H(ξ) − H(ξ|η) = I(ξ, η) ≥ 0. Stacion´er forr´as entr´ opi´ aja: ´ ´ ´ 4.7.ALL ITAS: H(ξ|η) ≤ H(ξ|f (η)). Bizony´ıt´ as: z jel¨olje f (η) egy lehets´eges ´ert´ek´et, ´es legyen py =

P (ξ = x, η = y) , P (ξ = x, f (η) = z) 28

qy =

P (η = y) . P (f (η) = z)

Fegyverneki S´andor: Inform´aci´oelm´elet Ekkor py ´es qy is egy eloszl´ast ad, ha y felveszi azokat az ´ert´ekeket, amelyre f (y) = z, azaz y ∈ f −1 (z). Az I-divergencia tulajdons´agai alapj´an: X

py log2

f (y)=z

py ≥ 0, qy

azaz X f (y)=z

P (ξ = x, η = y)P (f (η) = z) P (ξ = x, η = y) log2 ≥ 0. P (ξ = x, f (η) = z) P (ξ = x, f (η) = z)P (η = y)

Szorozzuk be a P (ξ = x, f (η) = z) k¨oz¨os nevez˝ovel ´es bontsuk fel a logaritmust a k¨ovetkez˝ ok´eppen: X

P (ξ = x, η = y) log2

f (y)=z

X

+

P (ξ = x, η = y) + P (η = y)

P (ξ = x, η = y) log2

f (y)=z

X

P (ξ = x, η = y) log2

f (y)=z

≥

X

P (f (η) = z) ≥ 0. P (ξ = x, f (η) = z)

1 ≥ P (ξ = x|f (η) = z)

P (ξ = x, η = y) log2

f (y)=z

1 . P (ξ = x|η = y)

1 ≥ P (ξ = x|f (η) = z) X 1 ≥ P (ξ = x, η = y) log2 . P (ξ = x|η = y)

P (ξ = x, f (η) = z) log2

f (y)=z

Ez minden ξ = x ´es f (y) = z eset´en teljes¨ ul. V´egezz¨ ul el a osszegz´est ezekre az egyenl˝ ¨ otlens´egekre. Mivel H(ξ|η) =

X y

P (η = y)

X

P (ξ = x|η = y) log2

x

29

XX x

1 , P (ξ = x|η = y)

z

Fegyverneki S´andor: Inform´aci´oelm´elet ´ıgy igazoltuk az ´all´ıt´ ast. ´ ´ ´ 4.8.ALL ITAS: Stacion´er forr´as eset´en a H(P (k) ) k→∞ k lim

hat´ ar´ert´ek l´etezik. Jele: H ? Bizony´ıt´ as: Tudjuk, hogy a forr´as stacion´er ´es H(ξ, η) = H(η) + H(ξ|η), ez´ert H(P (k) ) = H(ξ1 , . . . , ξk ) = H(ξ2 , . . . , ξk ) + H(ξ1 |ξ2 , . . . , ξk ) = = H(ξk ) + H(ξk−1 |ξk ) + . . . + H(ξ1 |ξ2 , . . . , ξk ) = = H(ξ1 ) + H(ξ1 |ξ2 ) + . . . + H(ξ1 |ξ2 , . . . , ξk ) = = H(ξ1 ) +

k X

H(ξ1 |ξ2 , . . . , ξi ).

i=2

A (ξ2 , . . . , ξi ) v´eletlen vektor f¨ uggv´enye a (ξ2 , . . . , ξi+1 ) v´eletlen vektornak, ez´ert H(ξ1 ) ≥ H(ξ1 |ξ2 ) ≥ . . . ≥ H(ξ1 |ξ2 , . . . , ξk ). H(P

(k)

) = H(ξ1 ) +

k X

H(ξ1 |ξ2 , . . . , ξi ) ≥ kH(ξ1 |ξ2 , . . . , ξk+1 ).

i=2

Teh´ at H(P (k+1) ) = H(P (k) ) + H(ξ1 |ξ2 , . . . , ξk+1 ) ≤ Ekkor

k+1 H(P (k) ). k

H(P (k+1) ) H(P (k) ) ≤ . k+1 k

Teh´ at a sorozat monoton cs¨okken˝ o ´es alulr´ol korl´atos, s ´ıgy l´etezik a hat´ ar´ert´ek. 30

Fegyverneki S´andor: Inform´aci´oelm´elet A H ? mennyis´eget a forr´as ´atlagos entr´opi´aj´anak nevezz¨ uk. Megjegyz´ es: Eml´ekezetn´elk¨ uli esetben H ? = H(P), egy´ebk´ent H ? ≤ H(P). Csatornakapacit´ as (eml´ekezetn´elk¨ uli eset): C = max I(ξ, η) Q

Megjegyz´ es: 1. Legyen C a kapacit´as, L az ´atlagos k´odhossz. Ha H(P) ≤ LC, akkor tov´ abb´ıthatjuk a forr´as ´altal szolg´altatott k¨ozlem´enyeket. 2. Zajmentes ´es eml´ekezetn´elk¨ uli csatorn´ara: C = log2 s. 3. Bin´aris szimmetrikus csatorna: C = 1 − H(p, q). Milyenek a bemeneti illetve kimeneti eloszl´asok? ´ 4.6.TETEL: (A zajmentes h´ırk¨ ozl´ es alapt´ etele.) Ha a H ? entr´opi´ aj´ u stacion´arius forr´as k¨ozlem´enyeit C kapacit´as´ u zajmentes csatorn´an tov´abb´ıtjuk, akkor nincsen olyan egy´ertelm˝ uen dek´odolhat´o blokkonk´enti k´odol´ asi elj´ar´ as, melyn´el H? L< , C ha viszont R > H ? , akkor l´etezik olyan blokkhossz, hogy R L< . C Megjegyz´ es: A McMillan-particion´al´asi t´etel szerepe: 1. haszn´ alhat´ o ´alland´ o k´odhossz´ u k´od tervez´es´ehez.

Fel-

2. Gyakorlati szempont: megfelel˝o az olyan k´odol´as is, amelyn´el annak val´ osz´ın˝ us´ege, hogy egy k´odsz´o dek´odol´as´an´al hib´at k¨ovet¨ unk el kisebb, mint egy el˝ore megadott δ > 0 sz´am. Az ilyen k´odol´asi elj´ar´ast 1 − δ megb´ızhat´ os´ aggal dek´odolhat´ onak nevezz¨ uk. 31

Fegyverneki S´andor: Inform´aci´oelm´elet

´ 5. CSATORNAKAPACITAS Az eddigiek alapj´an tudjuk, hogy zajmentes csatorna eset´en az egy csatornajelre (k´od´ ab´ec´ebeli elemre) jut´o ´atlagos inform´aci´o ´atvitel megegyezik a k´od´ ab´ec´e eloszl´as´ ahoz kapcsol´od´o entr´op´aval, azaz H(Q), amely akkor maxim´alis, ha a jelek eloszl´asa egyenletes. A forr´as optim´alis k´ odol´ asa ezt a maxim´alis esetet pr´ob´alja k¨ozel´ıteni. A k¨ovetkez˝o szakaszban arra pr´ob´ alunk v´alaszt adni mi t¨ort´enik akkor, ha a csatornajelek ´atviteli ideje nem azonos. 3.1 Zajmentes csatorna kapacit´ asa nem azonos ´ atviteli id˝ o eset´ en Adott Y = {y1 , . . . , ys } csatorna´ab´ec´e eset´en felt´etelezz¨ uk, hogy a jelek ´atviteli ideje ismert illetve k´ıs´erleti u ´ton megfelel˝o pontoss´aggal meghat´ arozhat´ o. Jel¨olje az id˝oket T = {t1 , . . . , ts }. Felt´etelezz¨ uk, hogy ti > 0 (i = 1, . . . , s). Ha egy inform´aci´ oforr´ as jeleket bocs´at ki, akkor azt k´odolva keletkezik egy k´od¨ uzenet (csatorna¨ uzenet). Ekkor felmer¨ ulnek a k¨ovetkez˝o k´erd´esek: Egy adott k´odol´ as eset´en milyen gyorsan, milyen ´atlagos sebess´eggel tov´ abb´ıtja a csatorna az u ¨zenetet? Van-e az inform´aci´otov´abb´ıt´asnak fels˝ o hat´ara ´es ha van mennyi az? Nyilv´ an a sebess´eg f¨ ugg a k´odol´ast´ol (a k´od¨ uzenet elemeinek az eloszl´ as´ at´ ol), ez´ert az a c´elunk, hogy a k´odot u ´gy v´alasszuk meg, hogy az inform´aci´ otov´ abb´ıt´ as sebess´ege maxim´alis legyen. Legyen a csatorna´ab´ec´e bet˝ uinek eloszl´asa Q = {q1 , . . . , qs }. Ha a csatorna¨ uzenet hossza N, akkor egy kiv´alasztott jel pl. yi v´arhat´oan N qi -szer fordul el˝o ´es a v´arhat´ oan −N qi log2 qi mennyis´eg˝ u inform´aci´ot 32

Fegyverneki S´andor: Inform´aci´oelm´elet tov´abb´ıt. Ugyanez a teljes u ¨zenetre s X

1 = N H(Q). qi

N qi log2

i=1

Hasonl´ oan a v´arhat´ o ´atviteli id˝o: s X

N qi ti = N

i=1

s X

qi ti ,

i=1

ebb˝ ol az egy bet˝ ure jut´o v´arhat´ o ´atviteli id˝o (jel¨olje τ ) τ=

s X

qi ti .

i=1

5.1.Defin´ıci´ o: Az inform´aci´ otov´ abb´ıt´as sebess´eg´enek nevezz¨ uk a v(Q) =

H(Q) τ

mennyis´eget. Megjegyz´ es: Az el˝oz˝ o defin´ıci´oban szerepl˝o mennyis´eg ´atlagsebess´eg. 5.2.Defin´ıci´ o: Az inform´aci´ o´ atviteli sebess´eg maximum´at csatornakapacit´ asnak nevezz¨ uk (jele: C), azaz C = max Q

v(Q),

ahol Q a csatorna´ab´ec´e lehets´eges eloszl´asa. Megjegyz´ es: Az eloszl´asok ¨osszess´ege az el¨oz¨o defin´ıci´oban kompakt halmazt alkot ´es v(Q) folytonosan f¨ ugg a Q eloszl´ast´ol, ez´ert l´etezik a szupremuma ´es azt fel is veszi. ´ 5.3.TETEL: Zajmentes, eml´ekezetn´elk¨ uli (v´eges, diszkr´et) csatorna eset´en a csatornakapacit´ as a s X

2−vti = 1

i=1

33

(5.1)

Fegyverneki S´andor: Inform´aci´oelm´elet egyenlet egyetlen v = C ≥ 0 megold´asa. Ezt a qi = 2−Cti

(i = 1, . . . , s)

(5.2)

eloszl´ as realiz´alja. Bizony´ıt´ as: Ha C megold´asa az (5.1) egyenletnek, akkor az (5.2) szerint megadott sorozat eloszl´as ´es az ´atlagsebess´egre teljes¨ ul a k¨ovetkez˝ o: s X

H(Q) v(Q) = = τ

1 qi log2 qi i=1 s X

s X

qi log2

i=1

≤

s X

qi ti

i=1

s X

1 2−Cti

=

qi ti

i=1

qi Cti

i=1 s X

= C, qi ti

i=1

ahol az egyenl˝ os´eg csak az (5.2) esetben teljes¨ ul. Teh´ at csak azt kell bel´atnunk, hogy C egy´ertelm˝ uen l´etezik. Az s X

f (v) =

2−vti

i=1

f¨ uggv´eny szigor´ uan monoton cs¨okken˝o. Tov´abb´a, f (0) = s > 1 ´es

lim f (v) = 0.

v→+∞

A folytonoss´ag miatt l´etezik v = C, ahol f (C) = 1 ´es ez egy´ertelm˝ ua szigor´ u monotonit´as miatt. 3.2 Zajos csatorna kapacit´ asa Bemeneti ´ab´ec´e: Y = {y1 , . . . , ys }. Kimeneti ´ab´ec´e: Z = {z1 , . . . , zm }. 34

Fegyverneki S´andor: Inform´aci´oelm´elet

qj = P (ξ = yj ),

j = 1, 2, . . . , s,

ri = P (η = zi ),

i = 1, 2, . . . , m,

tij = P (zi |yj ), pij = tij qj , s X ri = tij qj ,

i = 1, 2, . . . , m,

j=1

R = T Q. A T = (tij ) m´atrixot ad´okarakterisztika vagy csatornam´atrixnak nevezz¨ uk. M´ıg az egy¨ uttes eloszl´as P = (pij ) m´atrixa az u ´n. ´atviteli m´atrix. Csatornakapacit´ as:

C = max I(ξ, η). Q

Megjegyz´ es: I(ξ, η) = H(R) − H(R|Q) = H(Q) − H(Q|R). A zajos csatorn´ak oszt´alyoz´ asa a csatorna m´atrix alapj´an: 1. H(Q|R) = 0 – vesztes´egmentes. A kimenet egy´ertelm˝ uen meghat´ arozza a bemenetet. Minden i eset´en l´etezik j, hogy pij = ri . 2. H(R|Q) = 0 – determinisztikus. A bemenet egy´ertelm˝ uen meghat´ arozza a kimenetet. Minden j eset´en l´etezik i, hogy pij = qj . 3. H(R|Q) = H(Q|R) = 0 – zajmentes. A bemenet ´es a kimenet egy´ertelm˝ uen meghat´arozz´ ak egym´ast. Ekkor tij = δij . 4. C = 0, azaz H(R|Q) = H(R) – haszn´alhatatlan. Pl. az oszlopok megegyeznek. 5. Szimmetrikus csatorna – a sorok ´es az oszlopok is ugyanabb´ol a vektorokb´ol ´ep¨ ulnek fel. 35

Fegyverneki S´andor: Inform´aci´oelm´elet 1 6 1   T =  61   3 1 3

1 3 1  3 . 1   6 1 6

Szimmetrikus csatorna est´en H(η|ξ = yj ) minden j eset´en ugyanaz, ´ıgy H(η|ξ) = H(η|ξ = yj ). Teh´ at C = max I(ξ, η) = max H(R) − H(R|Q) = log2 m − H(R|Q). Q

Q

Megjegyz´ es: Ha a kimeneti eloszl´as egyenletes, akkor a bemeneti is. Legyen s = m, azaz a bemeneti ´es kimeneti ´ab´ec´e bet˝ uinek sz´ama megegyezik. Jel¨olje Hk a csatornam´atrix k-adik oszlop´anak entr´opi´aj´at, azaz Hk = H(η|ξ = yk ). Ekkor a C = max I(ξ, η) Q

sz´els˝ o´ert´ek feladatot kell megoldanunk a

s X

qj = 1 felt´etel mellett, ´ıgy

j=1

a Lagrange-f´ele multiplik´ atoros m´odszert alkalmazzuk. f¨ uggv´eny

L(Q, λ) =

s X i=1

ri log2

s X s X



s X

A Lagrange

1 + pij log2 tij + λ  qj − 1 . ri i=1 j=1 j=1

Hat´ arozzuk meg a deriv´altakat: 36

Fegyverneki S´andor: Inform´aci´oelm´elet 1. ri =

s X

qj tij , ´ıgy

j=1 s

∂H(η) X ∂H(η) ∂ri = = ∂qk ∂ri ∂qk i=1 ¶ s µ X 1 =− log2 ri + tik = ln 2 i=1 s

X 1 − tik log2 ri . =− ln 2 i=1 2. H(η|ξ) =

s X

qj Hj , ´ıgy

j=1

∂H(η|ξ) = Hk . ∂qk Teh´ at a Lagrange-f¨ uggv´eny deriv´altjaib´ol ad´od´o egyenletrendszer s

X ∂L 1 =− − tik log2 ri − Hk + λ = 0, ∂qk ln 2 i=1

k = 1, . . . , s,

s

∂L X = qj − 1 = 0. ∂λ j=1 1. Az els˝o s egyenlet mindegyik´et szorozzuk meg a megfelel˝o qk val´osz´ın˝ us´eggel ´es adjuk ¨ossze. Ekkor s

X 1 1 X − qk Hk + λ = 0. + ri log2 − ln 2 i=1 ri k=1

Ebb˝ ol C = H(η) − H(η|ξ) = 2. Meghat´arozzuk C =

1 − λ. ln 2

1 − λ ´ert´ek´et. ln 2 37

Fegyverneki S´andor: Inform´aci´oelm´elet A Lagrange-f¨ uggv´eny parci´alis deriv´altjaib´ol ad´od´o egyenleteket alak´ıtsuk ´at a k¨ovetkez˝ ok´eppen. ¶ s µ X 1 −Hk = − λ + log2 ri tik , ln 2 i=1

k = 1, . . . , s.

Ez egy line´aris egyenletrendszernek tekinthet˝o, amelynek az ismeretlenjei ui =

1 − λ + log2 ri , ln 2

i = 1, . . . , s.

A megold´as fel´ırhat´ o s

ui =

X 1 − λ + log2 ri = − Hk τki , ln 2

i = 1, . . . , s,

k=1

alakban, ahol a (τki ) m´atrix a T m´ atrix inverze. Ekkor s X −

2

Hk τki

k=1

1 −λ , = ri 2 ln 2

i = 1, . . . , s,

(5.2.1)

¨ Osszeadva az egyenleteket ´es alkalmazva a log2 f¨ uggv´enyt azt kapjuk, hogy s X − Hk τki s X 1 log2 2 k=1 = − λ. ln 2 i=1 Az (5.2.1) egyenletrendszerb˝ ol s X − −C

2 ahol C =

2

k=1

Hk τki = ri ,

i = 1, . . . , s,

1 − λ. Ezzel meghat´aroztuk az R kimeneti eloszl´ast. Az ln 2 R = TQ 38

Fegyverneki S´andor: Inform´aci´oelm´elet line´ aris egyenletrendszer megold´as´ aval pedig meghat´arozhat´o a Q bemeneti eloszl´as. Megjegyz´ es: 1. Ha l´etezik qk = 0, akkor probl´em´as a megold´as els˝ o r´esze. 2. I(ξ, η) maxim´alis (´es ez´ert egyenl˝o a csatornakapacit´assal) akkor ´es csak akkor, ha a Q bemeneti eloszl´as olyan, hogy ∂I a.) = λ minden k eset´en, amikor qk 6= 0. ∂qk ∂I b.) ≤ λ minden k eset´en, amikor qk = 0. ∂qk ´ 5.4.TETEL: A l´etez˝ o megold´as egy´ertelm˝ u ´es maximaliz´alja a k¨olcs¨on¨os inform´aci´ omennyis´eget. Bizony´ıt´ as: A csatornam´atrix r¨ogz´ıtett, ez´ert I(ξ, η) csak a bemeneti Q eloszl´ast´ ol f¨ ugg. Jel¨olje: I(Q). I(Q) konk´ av f¨ uggv´enye a Q eloszl´asnak. Ha Q1 = {q11 , q12 , . . . , q1s }, Q2 = {q21 , q22 , . . . , q2s }, ´es Q = ϑQ1 + (1 − ϑ)Q2 , ahol 0 ≤ ϑ ≤ 1. s s X X H(R|Q) = q j Hj = (ϑq1j + (1 − ϑ)q2j )Hj = j=1 s X

=ϑ

j=1

q1j Hj + (1 − ϑ)

j=1

s X

q2j Hj =

j=1

= ϑH(R1 |Q1 ) + (1 − ϑ)H(R2 |Q2 ). Ebb˝ ol ad´od´ oan I(Q) = H(Q) − ϑH(R1 |Q1 ) − (1 − ϑ)H(R2 |Q2 ). Viszont az entr´ opia konk´ av, ´ıgy I(Q) is konk´av. 5.5.LEMMA: Tegy¨ uk fel, hogy g : Rn → R konk´av az n X S = {(p1 , . . . , pn )|pi ≥ 0, i = 1, 2, . . . , n ´es pi = 1} i=1

39

Fegyverneki S´andor: Inform´aci´oelm´elet halmazon. Ha g folytonosan differenci´alhat´o S belsej´eben ´es l´etezik p∗i > 0 (i = 1, 2, . . . , n) u ´gy, hogy

∂g ¯¯ ¯ ∂pi

= 0,

i = 1, 2, . . . , n ´es p∗ ∈ S,

p=p∗

ahol p = (p1 , . . . , pn ), p∗ = (p∗1 , . . . , p∗n ), akkor a g f¨ uggv´eny abszol´ ut ∗ maximuma az S halmazon g(p ). Bizony´ıt´ as: Tegy¨ uk fel, hogy g(p) > g(p∗ ). Legyen 0 < ϑ ≤ 1, akkor (1 − ϑ)g(p∗ ) + ϑg(p) − g(p∗ ) g((1 − ϑ)p∗ + ϑp) − g(p∗ ) ≥ = ϑ ϑ = g(p) − g(p∗ ) > 0. A felt´etelek alapj´an viszont ∂g ¯¯ = 0, ¯ ∂pi p=p∗

i = 1, 2, . . . , n,

´es ´ıgy az ir´anymenti deriv´altnak 0-hoz kellene tartani, ami ellentmond´as. Teh´ at minden p ∈ S eset´en g(p) ≤ g(p∗ ). P´ elda:

µ T =

0.9 0.2 0.1 0.8

¶

q1 + q2 = 1, r1 = 0.9q1 + 0.2q2 , r2 = 0.1q1 + 0.8q2 , H1 ≈ 0.4689956 H2 ≈ 0.7219281 A parci´alis deriv´altakb´ ol ad´od´ o egyenletrendszer. 1 − 0.9 log2 r1 − 0.1 log2 r2 − H1 + λ = 0 ln 2 1 − − 0.2 log2 r1 − 0.8 log2 r2 − H2 + λ = 0 ln 2

−

40

Fegyverneki S´andor: Inform´aci´oelm´elet ´ Atalak´ ıtva µ

¶ µ ¶ 1 1 −H1 = − λ + log2 r1 0.9 + − λ + log2 r2 0.1 ln 2 ln 2 ¶ µ ¶ µ 1 1 −H2 = − λ + log2 r1 0.2 + − λ + log2 r2 0.8 ln 2 ln 2 Legyen

1 − λ + log2 r1 ln 2 1 u1 = − λ + log2 r2 ln 2

u2 =

Ekkor

u2 ≈ −0.7941945, u1 ≈ −0.4328624, C = log2 (2u1 + 2u2 ) ≈ 0.397754.

Tov´ abb´ a

2−C+u1 = r1 = 0.9q1 + 0.2q2 , 2−C+u2 = r2 = 0.1q1 + 0.8q2 , r2 ≈ 0.4377112, r1 ≈ 0.5622888, q1 ≈ 0.517555, q2 ≈ 0.48445.

41

Fegyverneki S´andor: Inform´aci´oelm´elet

´ ´ 6. CSATORNAKODOL AS Szimmetrikus bin´aris csatorna esete: µ T =

p q q p

¶

Probl´ ema: Milyen felt´etelek mellett, ´es hogyan oldhat´ o meg a csatorn´ aban az ´ atviteln´el keltkezett hib´ ak jelz´ese ´es jav´ıt´ asa? P´ elda: egys´eg):

A bit h´aromszoroz´os m´odszer(Commodore-64 kazett´as 0 → 000 1 → 111

Ha a dek´odol´ as a t¨obb azonos bit szerint t¨ort´enik, akkor 2 hiba jelezhet˝o ´es egy hiba jav´ıthat´ o. Ha p = 0.9, akkor a helyes ´atvitel (jav´ıt´assal) val´osz´ın˝ us´ege p3 + 3p2 q = 0.972. 6.1.Defin´ıci´ o: u ¨zenetsz´ o(k bit)→ k´odsz´o(n bit) ´atalak´ıt´ast(k´odol´ast) (k, n) k´odnak nevezz¨ uk. Legyen A = {0, 1} ´es adott a k¨ovetkez˝o k´et m˝ uveleti t´abla. A ”kiz´ar´ o vagy” m˝ uvelet (jele:∨) vagy m´ask´eppen a modulo 2 ¨osszead´ as (jele:⊕), ´es a hagyom´ anyos szorz´as a k´et m˝ uvelet. ´ Ekkor (A, ∨) ´es (A, ·) Abel-csoport. Tov´abb´a, (A, ∨, ·) test. Ertelmezz¨ uk az An eset´en az el˝obbi m˝ uveleteket bitenk´ent, ekkor (An , ∨) vektort´er a (A, ∨, ·) test felett. 6.2.Defin´ıci´ o: Legyen a ∈ An . ||a|| jelentse az egyes bitek sz´am´at. 42

Fegyverneki S´andor: Inform´aci´oelm´elet Ekkor ||·|| : An → Z norma. 6.3.Defin´ıci´ o: A d(a, b) = ||a ∨ b|| mennyis´eget Hamming-f´ele t´avols´ agnak nevezz¨ uk. ´ ´ ´ 6.4.ALL ITAS: A Hamming-f´ele t´avols´ag kiel´eg´ıti a t´avols´ag tulajdons´ agait. ´ ´ ´ 6.5.ALL ITAS: A Hamming-f´ele t´avols´ag invari´ans az eltol´asra, azaz d(a, b) = d(a ∨ c, b ∨ c). Bizony´ıt´ as: d(a ∨ c, b ∨ c) = ||(a ∨ c) ∨ (b ∨ c)|| = ||a ∨ (c ∨ c) ∨ b)|| = ||a ∨ b|| = = d(a, b). 6.6.Defin´ıci´ o: A v1 , v2 , . . . , vm k´odszavakb´ol ´all´o k´od eset´en a k´odszavak t´avols´ agai k¨oz¨ ul a minim´alisat k´odt´avols´agnak nevezz¨ uk. Megjegyz´ es: Legyen d = min d(vi , vj ), a csatorna´ab´ec´e i6=j k

Y = {0, 1}. Jel¨ol´esek: u ∈ Y (az eredeti u ¨zenet), v ∈ Y n (az unak megfelel˝o csatorna k´odsz´ o), v˜ ∈ Y n ( a v-nek megfelel˝o csatorn´an athaladt jelsorozat, azaz az ´atviteln´el keletkezik. Ekkor ´ P (˜ v |v) = q d(˜v,v) pn−d(˜v,v) . Ha a v˜ eredetij´enek azt a v k´ odsz´ ot tekintj¨ uk, amelyre a P (˜ v |v) felt´eteles val´ osz´ın˝ us´eg a lehet˝o legnagyobb, azt maximum likelihood k´odol´asnak nevezz¨ uk. Tegy¨ uk fel, hogy 0 < q < 0.5, akkor µ ¶d(˜v,v) q P (˜ v |v) = pn p maxim´ alis, ha d(˜ v , v) minim´alis. 43

Fegyverneki S´andor: Inform´aci´oelm´elet Ez azt jelenti, hogy bin´aris szimmetrikus csatorna eset´en a minim´alis t´ avols´ agon alapul´o dek´odol´ as (jav´ıt´ as) megegyezik a maximum likelihood k´ odol´ as alapj´an t¨ort´en˝ ovel. ´ ´ ´ 6.7.ALL ITAS: Legyen egy vett sz´oban a hib´ak sz´ama legfeljebb r. Tetsz˝ oleges k´odsz´ o eset´en a legfeljebb r sz´am´ u hiba a minim´alis t´avols´agon alapul´o hibajav´ıt´ as m´odszer´evel jav´ıthat´o akkor ´es csak akkor, ha a k´ odt´ avols´ ag d ≥ 2r + 1. Bizony´ıt´ as: El´egs´egess´eg: Ha d ≥ 2r + 1 ´es ||e|| ≤ r (e a hibavektor), akkor d(˜ v , vi ) < d(˜ v , vj ) b´ armely i 6= j eset´en, ha v˜ = vi ∨ e. d = min d(vi , vj ) ≤ d(vi , vj ) ≤ d(vi , v˜) + d(˜ v , vj ) ≤ r + d(˜ v , vj ) i6=j

azaz d(˜ v , vj ) ≥ d − r ≥ (2r + 1) − r = r + 1. Sz¨ uks´egess´eg: Ha ||e|| ≤ r ´es v˜ = vi ∨e minim´alis t´avols´agon alapul´o dek´ odol´ asa mindig helyes eredm´enyre vezet, akkor d ≥ 2r + 1. d(vi , vj ) ≤ d(vi , v˜) + d(˜ v , vj ) ⇒ d(˜ v , vj ) ≥ d − r, azaz a vi -b˝ ol torzult v˜ sz´ o a vj -t˝ ol legal´abb d − r t´avols´agra van. Mivel azt akarjuk, hogy a dek´odol´ as vi -be t¨ort´enjen, ez´ert d(˜ v , vi ) < d − r ⇒ d > 2r, azaz d > 2r + 1. 6.8.Defin´ıci´ o: Ha a k´odszavak csoportot alkotnak a k´odot csoportk´odnak nevezz¨ uk. P´ elda: Adottak a k¨ovetkez˝ o (2,5) k´odok: ´ ´ ´ 6.9.ALL ITAS: Csoportk´odban a k´odsz´o alak´ u hibavektor eset´en a hiba nem jelezhet˝o ´es nem jav´ıthat´ o. A nem k´odsz´o alak´ u hiba legal´abb jelezhet˝ o. 44

Fegyverneki S´andor: Inform´aci´oelm´elet ´ ´ ´ 6.10.ALL ITAS: Csoportk´od eset´en a hiba´atereszt´es val´osz´ın˝ us´ege megegyezik a csupa z´erus k´odsz´ o alak´ u hib´ak val´osz´ın˝ us´eg´enek az ¨osszeg´evel. P´ elda: Az (A) csoportk´od eset´en, ha p = 0.9, akkor a hiba´atereszt´es val´ osz´ın˝ us´ege: 2q 3 p2 + q 4 p = 0.0171, a k´odt´avols´ag: 3, a dek´odol´oi hiba ( 2 vagy t¨obb hiba): 0.08146. ´ ´ ´ 6.11.ALL ITAS: Egy (k,n) csoportk´od eset´en d = min ||vi ||. vi 6=0

´ 6.12.TETEL: G csoportk´od, vi ∈ G r¨ogz´ıtett, e hibavektor. Ha a hiba jav´ıthat´ o, akkor ez a tulajdons´aga f¨ uggetlen vi -t˝ol. Bizony´ıt´ as: Ha e jav´ıthat´ o, akkor d(vi ∨ e, vi ) < d(vi ∨ e, vj ) i 6= j. Azt kell bel´atni, hogy d(vk ∨ e, vk ) < d(vk ∨ e, vj )

k 6= j.

A Hamming-t´avols´ ag eltol´as invari´ans, ez´ert d(vk ∨ e, vj ) = d((vk ∨ e) ∨ (vk ∨ vi ), vj ∨ (vk ∨ vi )) = = d(vi ∨ e, vj ∨ (vk ∨ vi )) ≥ d(vi ∨ e, vi ) = = d((vi ∨ e) ∨ (vk ∨ vi ), vi ∨ (vk ∨ vi )) = d(vk ∨ e, vk ). Megjegyz´ es: Hogyan lehetne automatiz´alni a k¨ovetkez˝o probl´em´ akat? 1. A csoport tulajdons´ag ellen˝orz´ese. 2. T´arol´as, k´odsz´o keres´es. 3. K´odt´ avols´ ag kisz´am´ıt´ as. 6.13.Defin´ıci´ o: Legyen u ∈ Ak , G k × n t´ıpus´ u m´atrix, ahol gij ∈ A. A k´od line´aris, ha v T = uT G. A G m´atrixot gener´al´ o m´atrixnak nevezz¨ uk. P´ elda:

µ G=

1 0 0 1 45

1 0

0 1

1 1

¶

Fegyverneki S´andor: Inform´aci´oelm´elet ´ Eppen az (A) csoportk´odot adja meg. ´ ´ ´ 6.14.ALL ITAS: A line´aris k´od csoportk´od. 6.15.Defin´ıci´ o: Legyen E k × k t´ıpus´ u egys´egm´atrix. A G = (E|P ) gener´ ator m´atrix´ u k´odot szisztematikus k´odnak nevezz¨ uk. µ ¶ P N´eh´ any elnevez´es: P parit´ asm´atrix, F = parit´asellen˝orz˝o E m´ atrix (E(n−k)×(n−k) ), uT P parit´asvektor. 6.16.Defin´ıci´ o: Legyen v˜ egy vett k´odsz´o a csatornakimeneten. Az s vektort a v˜ vektorhoz tartoz´o szindr´om´anak nevezz¨ uk, ha sT = v˜T F. ´ ´ ´ 6.17.ALL ITAS: A szindr´oma akkor ´es csak akkor z´erusvektor, ha a vett sz´ o k´odsz´ o. Megjegyz´ es: A szindr´om´ ak egy oszt´alyoz´ast adnak. ´ ´ ´ 6.18.ALL ITAS: A csatorna kimenet´en vett azonos mell´ekoszt´alyokba tartoz´ o szavak szindr´om´ aja azonos, k¨ ul¨onb¨oz˝o mell´ekoszt´alyokhoz tartoz´ ok´e k¨ ul¨ onb¨ oz˝ o. (k, n) szisztematikus k´od eset´en: (Ak , ∨) csoport, a gener´al´as ut´an (S, ∨) r´eszcsoport (S ⊂ An ), S meghat´aroz egy mell´ekoszt´alyra bont´ast. K´esz´ıts¨ uk el a mell´ekoszt´ alyt´ abl´ azatot, majd ebb˝ol a dek´odol´asi t´abl´azatot (oszt´alyels˝ ok-mimim´ alis norm´aj´ u oszt´alyelemek kiv´alaszt´asa). ´ ´ ´ A dek´odol´ 6.18.ALL ITAS: asi t´abl´azatban b´armely sz´o t´avols´aga a saj´at oszlopa tetej´en ´all´ o k´odsz´ ot´ ol nem nagyobb, mint b´armely m´as k´odsz´ot´ol. Megjegyz´ es: 1. A dek´odol´ asi t´abl´azat alkalmas maximum likelihood k´odol´ asra. 2. Az oszt´alyels˝ o alak´ u hib´ak jav´ıthat´ok. 3. A helyes dek´odol´ as val´ osz´ın˝ us´ege megegyezik az oszt´alyels˝o alak´ u hib´ ak val´ osz´ın˝ us´egeinek az ¨osszeg´evel. 46

Fegyverneki S´andor: Inform´aci´oelm´elet

7. FOLYTONOS ESET A ξ folytonos val´ osz´ın˝ us´egi v´altoz´o lehets´eges ´ert´ekeinek halmaza nemmegsz´ aml´ alhat´ o, ez´ert H(ξ) defini´al´as´ahoz el˝osz¨or elk´esz´ıtj¨ uk a ξδ diszkr´et val´ osz´ın˝ us´egi v´altoz´ ot, amely a ξ kerek´ıt´es´enek is tekinthet˝o: ξδ = nδ,

ha

(n − 1)δ < ξ ≤ nδ,

n ∈ Z.

Ekkor Znδ f (x)dx = δ f˜(nδ),

P (ξδ = nδ) = P ((n − 1)δ < ξ ≤ nδ) = (n−1)δ

ahol mn ≤ f˜(nδ) ≤ Mn , azaz a minimum ´es a maximum k¨oz¨otti ´ert´ek az adott intervallumon. H(ξδ ) = −

+∞ X

δ f˜(nδ) ln(δ f˜(nδ)) =

n=−∞

= − ln δ −

+∞ X

δ f˜(nδ) ln(f˜(nδ)),

n=−∞

mert +∞ X n=−∞

+∞ Z δ f˜(nδ) = f (x)dx = 1. −∞

Ha δ → 0, akkor − ln δ → +∞, ez´ert +∞ Z lim(H(ξδ ) + ln δ) = − f (x) ln f (x)dx = H(ξ). δ↓0

−∞

47

Fegyverneki S´andor: Inform´aci´oelm´elet P´ elda: Legyen ξ a 0, ϑ) intervallumon egyenletes eloszl´as´ u. Ekkor H(ξ) = ln ϑ, azaz j´ol l´athat´ o, hogy a H(ξ) lehet negat´ıv is. Megjegyz´ es: Az entr´ opia diszkr´et esetben a bizonytalans´agot m´eri, m´ıg folytonos esetben csak a bizonytalans´ag v´altoz´as´at. N´ eh´ any fogalom folytonos esetben: Entr´ opia, mint v´arhat´ o ´ert´ek: H(ξ) = E(− ln f (ξ)). P´ elda: 1. Exponenci´alis eloszl´asra: H(ξ) = 1 − ln λ. 2. Norm´alis √ eloszl´ asra: H(ξ) = 0.5 + ln(σ 2π). Egy¨ uttes entr´ opia: H(ξ, η) = E(− ln f (ξ, η)). √ P´ elda: Norm´alis eloszl´asra: H(ξ, η) = 1 + ln(2πσ1 σ2 1 − r2 ). K¨ olcs¨ on¨ os inform´aci´ omennyis´eg: µ I(ξ, η) = E ln

f (ξ, η) fξ (ξ)fη (η)

¶ .

P´ elda: Norm´alis eloszl´asra: I(ξ, η) = −0.5 ln(1 − r2 ). I-divergencia:

µ ¶ fη (η) D(η||ξ) = E ln . fξ (η)

Megjegyz´ es: D(η||ξ) ≥ 0. Transzform´ aci´ o: η = g(ξ). Diszkr´et esetben H(η) ≤ H(ξ). Egyenl˝os´eg akkor ´es csak akkor, ha g invert´ alhat´ o. Folytonos esetben H(η) ≤ H(ξ) + E(ln |g 0 (ξ)|). Egyenl˝os´eg akkor ´es csak akkor, ha g invert´ alhat´ o. 48

Fegyverneki S´andor: Inform´aci´oelm´elet Bizony´ıt´ as: Ha g invert´ alhat´o, akkor a val´osz´ın˝ us´egi v´altoz´ok transzform´ aci´ oja alapj´an +∞ Z H(η) = − fη (y) ln fη (y)dy = −∞ +∞ Z fξ (x) dx = =− fξ (x) ln 0 |g (x)| −∞

+∞ +∞ Z Z =− fξ (x) ln fξ (x)dx + fξ (x) ln |g 0 (x)|dx. −∞

−∞

Maximum entr´ opia m´odszer (MEM): Entr´ opia maximaliz´al´ as felt´etelek mellett. P´ elda: 1. P´enzfeldob´ as: ξ = P (f ej). Felt´etel: A s˝ ur˝ us´egf¨ uggv´eny 0 a [0, 1] intervallumon k´ıv¨ ul. K´erd´es: H(ξ) mikor lesz maxim´alis? Az I-divergencia nemnegativit´asa alapj´an tetsz˝oleges g s˝ ur˝ us´egf¨ uggv´eny eset´en Z1 −

Z1 g(x) ln g(x)dx ≤ −

0

g(x) ln f (x)dx = 0 = H(ξ), 0

ha ξ egyenletes eloszl´as´ u a [0, 1] intervallumon. V´ arhat´ o ´ert´ek felt´etelek: A ξ val´ osz´ın˝ us´egi v´altoz´ o f s˝ ur˝ us´egf¨ uggv´eny´et nem ismerj¨ uk. Viszont adott, hogy E(gi (ξ)) = ai ,

(i = 1, 2, . . . , n),

ahol a gi f¨ uggv´enyek ismertek. Ekkor a MEM alapj´an à n ! X f (x) = A exp − λi gi (x) , i=1

49

Fegyverneki S´andor: Inform´aci´oelm´elet ahol a λi ´ert´ekeket meghat´arozz´ ak az adott v´arhat´o ´ert´ekek, m´ıg az A ´ert´eke abb´ol ad´ odik, hogy f s˝ ur˝ us´egf¨ uggv´eny. Bizony´ıt´ as: Ha f (x) ebben a form´aban adott, akkor E(ln f (ξ)) = ln A −

n X

λi ai .

i=1

M´ as s˝ ur˝ us´egf¨ uggv´eny eset´en az I-divergencia alapj´an: −E(ln g(ξ)) ≤

n X i=1

50

λi ai − ln A.

Fegyverneki S´andor: Inform´aci´oelm´elet

¨ ´ FUGGEL EK ´ ´ ˝ EGSZ ´ ´ ´ ´ F1. VALOSZ INUS AM ITAS 1.Defin´ıci´ o: Egy v´eletlen k´ıs´erlet lehets´eges eredm´enyeinek ¨osszes´eg´et minta t´ernek nevezz¨ uk. Jele: Ω. Az Ω elemeit elemi esem´enyeknek nevezz¨ uk. 2.Defin´ıci´ o: nevezz¨ uk, ha

Az Ω r´eszhalmazainak egy F rendszer´et σ-algebr´ anak

(1) Ω ∈ F, (2) A ∈ F, akkor A ∈ F, (3) A1 , A2 , . . . ∈ F , akkor A1 ∪ A2 ∪ . . . ∈ F. Az F elemeit pedig esem´enyeknek nevezz¨ uk. Megjegyz´ es: Ha A, B ∈ F, akkor A ∩ B ∈ F . 3.Defin´ıci´ o: Az Ω-t szok´as biztos esem´enynek, az ∅-t pedig lehetetlen esem´enynek nevezni. Tov´ abb´ a, az A esem´eny bek¨ ovetkezik, ha a k´ıs´erlet eredm´enye eleme az A halmaznak. Megjegyz´ es: Az A∪B esem´eny bek¨ovetkezik, ha legal´abb az egyik k¨ oz¨ ul¨ uk bek¨ovetkezik, m´ıg az A ∩ B esem´eny akkor k¨ovetkezik be, ha mind a kett˝ o bek¨ ovetkezik. 4.Defin´ıci´ o: nevezz¨ uk, ha

A P : F → R nemnegat´ıv lek´epez´est val´osz´ın˝ us´egnek

(1) P (Ω) = 1, 51

Fegyverneki S´andor: Inform´aci´oelm´elet (2) A ∩ B = ∅, akkor P (A ∪ B) = P (A) + P (B), (3) A1 , A2 , . . . egym´ ast k¨olcs¨on¨osen kiz´ar´o esem´enyek (azaz Ai ∩ Aj = ∅, ha i < j ´es i, j = 1, 2, . . .), akkor P(

∞ [

Ai ) =

∞ X

i=1

P (Ai ).

i=1

1.LEMMA: (1) P ( A ) = 1 − P (A). (2) P (∅) = 0. (3) P (B\A) = P (B) − P (A ∩ B). (4) Ha A ⊂ B, akkor P (A) ≤ P (B). (5) P (A ∪ B) = P (A) + P (B) − P (A ∩ B). ´ 1.TETEL: (Poincar´ e) Az A1 , A2 , . . . , An , esem´enyekre P(

n [

i=1

Ai ) =

n X

X

k−1

(−1)

k=1

i1
P(

k \

Aij ),

j=1

ahol az ¨osszegz´est az ¨osszes lehets´eges {i1 , i2 , . . . , ik } ⊂ {1, 2, . . . , n} esetre tekintj¨ uk. 5.Defin´ıci´ o: Az A esem´eny B felt´etel melletti felt´eteles val´ osz´ın˝ us´eg´enek nevezz¨ uk a P (A ∩ B) P (A|B) = P (B) mennyis´eget, ha P (B) > 0. Megjegyz´ es: A P (·|B) : F → R lek´epez´es t´enyleg val´osz´ın˝ us´eg. 2.LEMMA:

n−1 \

Ha az A1 , A2 , . . . , An esem´enyrendszerre P (

i=1

akkor P(

Ai ) > 0,

n \

Ai ) = P (A1 )P (A2 |A1 ) . . . P (An |A1 ∩ A2 ∩ . . . ∩ An−1 ).

i=1

52

Fegyverneki S´andor: Inform´aci´oelm´elet 6.Defin´ıci´ o:

Az A1 , A2 , . . . esem´enyrendszert teljes esem´enyrendszer∞ [ nek nevezz¨ uk, ha Ai ∩ Aj = ∅, ha i < j ´es i, j = 1, 2, . . . , ´es Ai = Ω. i=1

´ 2.TETEL: Ha A1 , A2 , . . . teljes esm´enyrendszer ´es P (Ai ) > 0, ha i = 1, 2, . . . , akkor tetsz˝oleges B esem´eny eset´en P (B) =

∞ X

P (B|Ai )P (Ai ).

i=1

´ 3.TETEL: (Bayes) Ha A1 , A2 , . . . teljes esm´enyrendszer ´es P (Ai ) > 0, ha i = 1, 2, . . . , akkor tetsz˝oleges pozit´ıv val´osz´ın˝ us´eg˝ u B esem´eny eset´en P (B|Ak )P (Ak ) P (Ak |B) = P∞ . i=1 P (B|Ai )P (Ai ) Megjegyz´ es: A Bayes-t´etelhez kapcsol´od´oan bevezethetj¨ uk a k¨ovetkez˝ o elnevez´eseket: P (Ai ) az u ´n. a-priori val´osz´ın˝ us´eg ´es P (Ai |A) az u ´n. a-posteriori val´ osz´ın˝ us´eg. 7.Defin´ıci´ o: Az A ´es B esem´enyt sztochasztikusan f¨ uggetlennek nevezz¨ uk, ha P (A ∩ B) = P (A)P (B). Az A1 , A2 , . . . , An esem´enyeket p´ aronk´ent sztochasztikusan f¨ uggetlennek nevezz¨ uk, ha P (Ai ∩ Aj ) = P (Ai )P (Aj )

(1 ≤ i < j ≤ n).

Az A1 , A2 , . . . , An esem´enyeket teljesen sztochasztikusan f¨ uggetlennek nevezz¨ uk, ha P (Ai1 ∩ . . . ∩ Aik ) = P (Ai1 ) . . . P (Aik ) (1 ≤ i1 < . . . < ik ≤ n,

2 ≤ k ≤ n).

Az {A1 , A2 , . . . , An } ´es {B1 , B2 , . . . , Bm } esem´enyrendszereket sztochasztikusan f¨ uggetlennek nevezz¨ uk, ha P (Ai ∩ Bj ) = P (Ai )P (Bj ) 53

Fegyverneki S´andor: Inform´aci´oelm´elet (1 ≤ i ≤ n,

1 ≤ j ≤ m).

P´ elda: Ha az A ´es B esem´enyek f¨ uggetlenek, akkor A ´es B, A ´es B ´es A ´es B is f¨ uggetlenek, azaz az {A, A } ´es {B, B } esem´enyrendszerek is f¨ uggetlenek. 3.LEMMA: Ha A1 , A1 , . . . , An f¨ uggetlen esem´enyek ´es P (Ai ) < 1 (i = n [ 1, 2, . . . , n), akkor P ( Ai ) < 1. i=1

Bizony´ıt´ as: P(

n [

Ai ) =

i=1

= P(

n [

Ai ) = 1 − P (

i=1

n [

Ai ) = 1 − P (

i=1

n \

i=1

Ai ) = 1 −

n Y

P ( Ai ).

i=1

8.Defin´ıci´ o: A ξ :→ R lek´epez´est diszkr´et val´ osz´ın˝ us´egi v´ altoz´ onak nevezz¨ uk, ha ξ(Ω) = {x1 , x2 , . . .} lehets´eges ´ert´ekek halmaza legfeljebb megsz´ aml´alhat´ oan v´egtelen sz´amoss´ag´ u ´es ξ −1 (xi ) = {ω|ω ∈ Ω,

ξ(ω) = xi } ∈ F(i = 1, 2, . . .).

9.Defin´ıci´ o: A {pi = P (ξ −1 (xi )), i = 1, 2, . . .} sz´amok ¨osszess´eg´et a ξ val´ osz´ın˝ us´egi v´altoz´ o eloszl´ as´anak nevezz¨ uk. ∞ X 10.Defin´ıci´ o: A xi pi mennyis´eget v´arhat´o ´ert´eknek nevezz¨ uk, ha ∞ X

i=1

|xi | pi < +∞. Jele: E(ξ).

i=1

11.Defin´ıci´ o: Bernoulli k´ıs´erletsorozatnak nevezz¨ uk, ha adott A ∈ F ´es egym´ast´ ol f¨ uggetlen¨ ul, azonos k¨or¨ ulm´enyek k¨oz¨ott elv´egezz¨ uk ugyanazt a k´ıs´erletet, s ”csak” azt figyelj¨ uk, hogy az A esem´eny bek¨ovetkezett-e vagy sem. 54

Fegyverneki S´andor: Inform´aci´oelm´elet ¨ ´ F2. KONVEX FUGGV ENYEK k1.Defin´ıci´ o: Legyen U egy intervallum (z´art, ny´ılt, f´elig z´art). Az f : U → R konvex f¨ uggv´eny, ha f (λa + µb) ≤ λf (a) + µf (b), ahol a, b ∈ U, λ + µ = 1, λ ≥ 0 ´es µ ≥ 0. ´ k2.TETEL: 1. Ha f ´es g konvex f¨ uggv´eny ´es α ≥ 0, β ≥ 0, akkor αf + βg szint´en konvex. 2. V´eges sok konvex f¨ uggv´eny ¨osszege is konvex. 3. Konvex f¨ uggv´enyek egy konvergens sorozat´anak a (pontonk´enti) hat´ ara is konvex. 4. Ha f : U → R konvex f¨ uggv´eny ´es a < x < b, akkor f (x) − f (a) f (b) − f (a) f (b) − f (x) ≤ ≤ . x−a b−a b−x Ha f szigor´ uan konvex, akkor az egyenl˝otlens´egek is azok. 5. Ha f : U → R konvex f¨ uggv´eny ´es a < c < b, akkor l´etezik a bal´es jobboldali deriv´alt minden c eset´en. Tov´abb´a, f 0 − ´es f 0 + monoton nemcs¨ okken˝ o ´es f 0 − (c) ≤ f 0 + (c). Ezenk´ıv¨ ul minden x ∈ U eset´en f (x) ≥ f (c) + f 0 − (c)(x − c),

f (x) ≥ f (c) + f 0 + (c)(x − c),

azaz a konvex f¨ uggv´eny minden pontj´ahoz l´etezik egyenes ( amely az adott ponton kereszt¨ ul megy), amely a g¨orbe alatt marad vagy legfeljebb ´erinti azt. 6. Az f : U → R konvex f¨ uggv´eny folytonos az intervallum minden bels˝o pontj´ aban. 55

Fegyverneki S´andor: Inform´aci´oelm´elet 7. Legyen U ny´ılt ´es f k´etszer differenci´alhat´o, akkor f konvex akkor ´es csak akkor, ha f 00 > 0 minden x ∈ U. ´ k3.TETEL: (Jensen-egyenl˝ otlens´ eg) Ha f konvex f¨ uggv´eny ´es ξ olyan val´ osz´ın˝ us´egi v´altoz´ o, amelyre l´etezik E(f (ξ)) ´es f (E(ξ)), akkor E(f (ξ)) ≥ f (E(ξ)). Bizony´ıt´ as: Legyen L a t´amaszt´oegyenes az f f¨ uggv´enyhez az (E(ξ), f (E(ξ))) pontban, akkor E(f (ξ)) ≥ E(L(ξ)) = L(E(ξ)) = f (E(ξ)). Megjegyz´ es: E(ξ 2 ) ≥ E 2 (ξ). Az x ln x f¨ uggv´ eny vizsg´ alata: Az f (x) = x ln x csak x > 0 eset´en ´ertelmezett, viszont folytonosan kiterjeszthet˝ o az x = 0 esetre, azaz ha x → 0, akkor l´etezik f hat´ar´ert´eke. f 0 (x) = 1 + ln x, amib˝ ol l´athat´o, hogy x < e−1 eset´en f 0 (x) < 0, azaz f monoton cs¨okken˝ o a (0, e−1 ) szakaszon. Tov´abb´a, 1≤

√ n

√ 2 n + (n − 2) · 1 n−2 2 2 n≤ = + √ <1+ √ , n n n n

´ıgy lim

√ n

n→+∞

Teh´ at

n = 1.

√ 1 1 ln = lim − ln n n = 0. n→+∞ n n n→+∞

lim x ln x = lim

x→0+0

´ IT ´ AS: ´ k4.ALL 1−

1 ≤ ln x ≤ x − 1. x 56

Fegyverneki S´andor: Inform´aci´oelm´elet Bizony´ıt´ as: Az ln x f¨ uggv´eny konk´av, ´ıgy az x = 1 helyen fel´ırt t´ amaszt´ o egyenesre igaz, hogy ln x ≤ x − 1, 1 ul, egyenl˝ os´eg csak x = 1 eset´en. Tov´ abb´a, ha x > 0, akkor > 0 is teljes¨ x azaz 1 1 ln ≤ − 1, x x ami ekvivalens azzal, hogy ln x ≥ 1 −

1 . x

´ IT ´ AS: ´ k5.ALL Ha {an > 0} sorozat ´es an → a, akkor n 1X lim ak = a ´es n→+∞ n k=1

´ IT ´ AS: ´ k6.ALL lim

n→+∞

v u n uY n lim t ak = a.

n→+∞

k=1

n √ = e. n n!

´ IT ´ AS: ´ k7.ALL (Aszimptotikus Stirling-formula) ln n! = 1. n→+∞ n ln n − n lim

57

Fegyverneki S´andor: Inform´aci´oelm´elet

´ IRODALOMJEGYZEK

[1] G. Birkhoff–T.C.Bartee: A modern algebra a sz´ am´ıt´ og´eptudom´ anyban, M˝ uszaki K¨onyvkiad´ o, Budapest, 1964. [2] Csisz´ar I.– Fritz J´ozsef: Inform´ aci´ oelm´elet, Tank¨onyvkiad´o, Budapest, 1980. [3] Fritz J´ozsef: Bevezet´es az inform´ aci´ oelm´eletbe, Tank¨onyvkiad´o, Budapest, 1971. [4] Fritz J´ozsef: Inform´ aci´ oelm´elet, Mat.Kut.Int., Budapest, 1973. [5] Sz.V. Jablonszkij–O.B. Lupanov: Diszkr´et matematika a sz´ am´ıt´ astudom´ anyban, M˝ uszaki K¨onyvkiad´o, Budapest, 1980. [6] C.E. Shannon–W.Weaver: A kommunik´ aci´ o matematikai elm´elete, OMIKK, Budapest, 1986. [7] F.M. Reza: Bevezet´es az inform´ aci´ oelm´eletbe, M˝ uszaki K¨onyvkiad´o, Budapest, 1963.

58