🥇Richard Hamming: Pead 13. Informatsiooniteooria

Me tegime selle ära!

„Selle kursuse eesmärk on valmistada teid ette teie tehniliseks tulevikuks.”

Tere, Habr. Kas mäletate seda ägedat artiklit „Teie ja teie töö” (+219, 2588 järjehoidjat, 429k vaatamist)?

Nii et Hammingul (jah, jah, enesekontrollivad ja ennast parandavad Hamming'i koodid) on terve raamat, mis on kirjutatud tema loengute podajärgi. Me tõlgime selle, sest see mees räägib tõde.

See raamat pole lihtsalt IT-st, see raamat räägib uskumatult lahedate inimeste mõtteviisist. „See ei ole lihtsalt positiivse mõtlemise jõud; selles kirjeldatakse tingimusi, mis suurendavad võimalusi teha head tööd.”

Tõlke eest tuleb tänada Andreid Pahhomovit.

Informatsiooniteooria töötati välja Claude E. Shannon'i poolt 1940. aastate lõpus. Bell Labs'i juhtkond rõhutas, et ta nimetaks selle „Side Teooriaks”, kuna see on palju täpsem nimetus. Ilmselgelt, nimetus „Informatsiooniteooria” omab oluliselt suuremat mõju avalikkusele, seetõttu valis Shannon just selle, ja just see on meile tänaseni tuntud. Ise nimetus viitab sellele, et teooria tegeleb informatsiooniga, mis teeb selle oluliseks, kuna me sügavamalt tungime informatsiooniajastusse. Käesolevas peatükis käsitlen mitmeid selle teooria põhipunkte, esitades mitte rangeid, vaid pigem intuitsiooniga arusaadavaid tõendeid mõnede teooria eraisiku printsiipide kohta, et te mõistaksite, millega just on tegu „Informatsiooniteooria” mõistes, kus te seda kasutada saate ja kus mitte.

Esiteks, mis on „informatsioon”? Shannon samastab informatsiooni ebakindlusega. Ta valis tõenäosuse negatiivse logaritmi sündmuse tekkimise kvantitatiivseks mõõdiks, mida te saate, kui sündmuse tõenäosus p realiseerub. Näiteks, kui ma ütlen teile, et Los Angeleses on udune ilm, siis p on lähedal 1, mis põhimõtteliselt ei anna meile palju teavet. Aga kui ma ütlen, et juunis sadab Montereys vihma, siis selles sõnumis on ebakindlust, ja see sisaldab rohkem informatsiooni. Usaldusväärne sündmus ei sisalda mingit teavet, kuna log 1 = 0.

Räägime sellest lähemalt. Shannon arvas, et teabe kvantitatiivne mõõt peaks olema pidev funktsioon sündmuse tõenäosusest p ja et iseseisvate sündmuste puhul peaks see olema additiivne – kahe iseseisva sündmuse käigus saadud teabe hulk peaks olema võrdne ühise sündmuse käigus saadud teabe hulga kogumiga. Näiteks viskega mänguklotside ja mündiga tulemusena saadud tulemused on tavaliselt iseseisvad sündmused. Tõlgime ülaltoodu matemaatika keelde. Kui I (p) on teabe hulk, mis sisaldub sündmuses tõenäosusega p, siis kahe iseseisva sündmuse x, mille tõenäosus on p1, ja y, mille tõenäosus on p2, ühise sündmuse korral saame

(x ja y on iseseisvad sündmused)

See on Cauchy funktsionaalne võrrand, mis kehtib kõigi p1 ja p2 puhul. Selle funktsionaalse võrrandi lahendamiseks oletame, et

p1 = p2 = p,

see annab

Kui p1 = p2 ja p2 = p, siis

jne. Jätkates seda protsessi, kasutades standardmeetodit eksponentsiaalide jaoks, on kõikide ratsionaalsete arvude m / n puhul järgnev tõene

Eeldatava teabe mõõtme pidevuse kohaselt on logaritmiline funktsioon ainus pidev lahendus Cauchy funktsionaalsele võrrandile.

Teabe teoorias on tavaks võtta logaritmi aluseks 2, seega sisaldab binaarne valik täpselt 1 bitti teavet. Seetõttu mõõdetakse teavet järgmise valemiga

Pausime ja vaatame, mis just juhtus. Esiteks, me ei ole määratlenud terminit “teave”, oleme lihtsalt määratlenud selle kvantitatiivse mõõtmise valemi.

Teiseks, see mõõt sõltub ebakindlusest ja kuigi see sobib piisavalt masinatele — näiteks telefonisüsteemidele, raadiosse, televisioonile, arvutitele jne — ei peegelda see normaalselt inimlikku suhtumist teabesse.

Kolmandaks, see on suhteline mõõt, see sõltub teie teadmiste praegusest seisundist. Kui vaatate “juhuslike arvude” voogu juhuslikkuse generaatorist, arvate, et iga järgnev number on ebakindel, kuid kui teate valemit „juhuslike arvude“ arvutamiseks, siis järgmine number on teada ja seega ei sisalda see teavet.

Seega, Shannon'i määratlus teabele sobib paljuski masinate jaoks, kuid näib, et see ei vasta inimese mõistmisele sellest sõnast. Just seetõttu tuleb „Teooria infost” nimetada „Teooria sidestamiseks”. Sellegipoolest on juba liiga hilja määratlusi muuta (mis viis teooria esialgse populaarsuseni ning mis jätkuvalt paneb inimesi arvama, et see teooria tegeleb „teabega”), seega peame selle üle leppima, kuid samas peate selgelt mõistma, kui kaugel on Shannon'i määratlus infost oma igapäevasest tähendusest. Shannon'i info tegeleb millegagi täiesti erinevaga, nimelt ebakindlusega.

See on see, millest peaks mõtlema, kui pakute ette mingit terminoloogiat. Kui hästi pakutud määratlus, näiteks Shannon'i määratlus infost, kooskõlab teie esialgse ideega ja kui palju see erineb? Peaaegu ei ole terminit, mis täpselt peegeldaks teie varasemat nägemust kontseptsioonist, kuid lõppkokkuvõttes peegeldab just kasutatav terminoloogia kontseptsiooni tähendust, seega millegi formaliseerimine selgete määratlustega toob alati sisse teatud müra.

Vaatame süsteemi, mille alfabet koosneb sümbolitest q, millel on tõenäosused pi. Sel juhul keskmine info hulk süsteemis (tema oodatav väärtus) on:

Seda nimetatakse süsteemi entropiaks, mille tõenäosuse jaotuseks on {pi}. Kasutame terminit „entropia”, kuna sama matemaatiline vorm ilmneb termodünaamikas ja statistilises mehaanikas. Just seetõttu loob termin „entropia” enda ümber teatud tähtsuse aura, mis lõppkokkuvõttes ei pruugi olla õigustatud. Sama matemaatilise vormiga ülesanne ei tähenda sama sümbolite tõlgendust!

Tõenäosuse jaotuse entropia mängib peamist rolli kooditeoorias. Gibbs'i ebaühtlus kahe erineva tõenäosuse jaotuse pi ja qi vahel on üks selle teooria olulisi järeldusi. Seega peame tõestama, et

Tõestus põhineb ilmselgel joonisel, joonis 13.I, mis näitab, et

ja võrdsus saavutatakse ainult siis, kui x = 1. Rakendame ebaühtlust iga summa vasakpoolses osas olevate liikmete jaoks:

Kui side süsteemi tähestik koosneb q sümbolist, siis aktsepteerides iga sümboli edastamise tõenäosust qi = 1/q ja asendades q, saame Gibbs'i ebavõrdsuse.

Joonis 13.I

See tähendab, et kui kõikide q sümbolite edastamise tõenäosus on sama ja võrdne — 1/q, siis maksimaalne entropia on ln q; muul juhul kehtib ebavõrdsus.

Ühekasutamiseks dekodeeritava koodi puhul kehtib Krafti ebavõrdsus.

Nüüd, kui me defineerime pseudotõenäosused,

kus on lõplik = 1, mis tuleneb Gibbs'i ebavõrdsusest,

ja rakendame natuke algebraat (meenutades, et K ≤ 1, seega saame logaritmilise liikme kõrvale jätta, ja võib-olla tugevdada ebavõrdsust hiljem), siis saame

kus L on koodi keskmine pikkus.

Seega on entropia minimaalne piir igasugusele sümbolikoodile, mille keskmine koodisõna pikkus on L. See on Shannon'i teoreem häiritud kanalite kohta.

Nüüd vaatame peamist teoreemi side süsteemide kohta, kus info edastatakse sõltumatute bitivoogude kujul ja kus on müra. Eeldatakse, et ühe bitti õige edastamise tõenäosus P > 1/2, ja tõenäosus, et bitin väärtus muutub edastamise ajal (juhtub viga) on Q = 1 — P. Mugavuse huvides oletame, et vead on sõltumatud ja veaoht on iga saadetud bit kohta sama — st suhtluskanalis on olemas 'valge hääl'.

Meil on pikk voog n bitti, kodeeritud ühe sõnumina — n - mõõtmeline laiendus ühte bitti koodist. N'i väärtuse määrame hiljem. Vaatame sõnumit, mis koosneb n-bitist kui punkti n-mõõtmeliselt ruumis. Kuna meil on n-mõõtmeline ruum — ja lihtsuse huvides eeldame, et igal sõnumil on sama tõenäosus esineda — on olemas M võimalikku sõnumit (M määratakse samuti hiljem), seega on tõenäosus, et mõni saadetud sõnum on

(saataja)
Joonis 13.II

Jätkame kanali läbilaskevõime mõtte arutamist. Süvenemata detailidesse, määratletakse kanali läbilaskevõime kui maksimaalne teabe maht, mida saab usaldusväärselt edastada sidekanali kaudu, arvestades maksimaalselt tõhusat kodeerimist. Pole argumente, et sidekanali kaudu saaks edastada rohkem teavet, kui selle maht. Seda saab tõestada binaarse sümmeetrilise kanali puhul (mida me kasutame). Kanali maht, bitipõhise edastamise korral, on määratud kui

kus, nagu varem, P on tõenäosus, et ükski edastatud bitt ei ole vigane. N-bitise sõltumatu biti edastamise korral määratakse kanali maht järgmiselt

Kui me oleme lähedal kanali läbilaskevõimele, peame edastama peaaegu sama palju teavet iga sümboli ai kohta, i = 1, …, M. Arvestades, et iga sümboli ai tekkimise tõenäosus on 1 / M, saame

kui me edastame mõnda M võrdselt tõenäolist sõnumit ai, siis meil on

N-bitise edastamise korral ootame, et tekib nQ viga. Praktikas, n-bitisest sõnumist koosneva sõnumi puhul on meil umbes nQ viga saadud sõnumis. Suurte n-de puhul on suhteline variatsioon (variatsioon = jaotuse laius, )
vigade arvu jaotuse kitseneb üha rohkem, kui n kasvab.

Seega, edastaja poolelt, võtan sõnumi ai edastamiseks ja joonistan selle ümber sfääri raadiusega

mis on veidi suurem kui e2, oodatud vigade arv Q (joonis 13.II). Kui n on piisavalt suur, siis on olemas meelevaldne väike tõenäosus, et sõnumipunkt bj vastuvõtja poolel jääb sellest sfäärist välja. Loon olukorra, nagu mina seda edastaja vaatest näen: meil on eri raadiused edastatud sõnumist ai saadud sõnumini bj, mille vigade tõenäosus on (või peaaegu on) normaaljaotuse kohaselt, ulatudes maksimumini nQ. Iga antud e2 korral on olemas n, mis on piisavalt suur, et tõenäosus, et saadud punkt bj jääb minu sfäärist välja, oleks enam-vähem niivõrd väike, kui te soovite.

Nüüd vaatame seda sama olukorda teie vaatepunktist (joonis 13.III). Vastuvõtja poolel on sphere S(r) sama raadiusega r ümber vastu võetud punkti bj n-mõõtmelises ruumis, nii et kui vastu võetud sõnum bj asub minu sfääris, siis minu saadetud sõnum ai asub teie sfääris.

Kuidas võib viga tekkida? Viga võib esineda allpool kirjeldatud juhtudel:

Joonis 13.III

Siin näeme, et kui vastu võetud punkti ümber ehitatud sfääris on veel vähemalt üks punkt, mis vastab võimalikele saadetud kodeerimata sõnumitele, siis edastamise ajal toimus viga, kuna te ei saa määrata, milline neist sõnumitest on edastatud. Saadetud sõnum ei sisalda viga ainult siis, kui sellele vastav punkt asub sfääris ja ei ole teisi punkte, mis võivad antud koodis asuda samas sfääris.

Meil on matemaatiline võrrand vea tõenäosuse Re jaoks, kui on saadetud sõnum ai

Saame visata teise liikme esimesed tegurid välja, võtta need kaheks. Nii saame ebavõrdsuse.

Ilmselgelt, et

seega

rakendame uuesti viimasele liige paremal

Oletame, et n on piisavalt suur, esimene liige võib olla piisavalt väike, ütleme, väiksem kui mõni number d. Seega saame me

Nüüd vaatame, kuidas võiks ehitada lihtsa asenduskoodi M sõnumi kodeerimiseks, mis koosneb n bitist. Ilma teadmata, kuidas täpselt koodi luua (vigade parandamise koodid ei olnud veel leiutatud), valis Shannon juhusliku kodeerimise. Visake münte iga n bit sõnumis ja korrake protsessi M sõnumi jaoks. Kokku tuleb teha nM mündiviset, seega on võimalikud

koodivääringud, millel on sama tõenäosus ½nM. Loomulikult tähendab koodivääringu juhuslik protsess, et on tõenäosus, et tekivad duplikaadid ja ka koodipunktid, mis on üksteisele lähedased ja seega võivad olla tõenäoliste vigade allikad. Tuleb tõestada, et kui see ei juhtu tõenäosusega, mis on suurem kui mis tahes väike valitud vea tase, siis on antud n piisavalt suur.
Oluline hetk seisneb selles, et Shannon leidis keskmise vea, keskmistades kõik võimalikud koodiraamatud! Kasutame sümbolit Av [.], et tähistada keskmist väärtust paljude juhuslike koodisõnavara seas. Keskmistamine konstandi d järgi annab muidugi konstandi, kuna keskmistamisel sobib iga liige kokku iga teise liikmega summas.

mis võib suureneda (M–1 muutub M-ks)

Konkreetse sõnumi jaoks, keskmistades kõiki koodiraamatuid, läbib kodeerimine kõik võimalikud väärtused, seega on keskmine tõenäosus, et punkt asub sfääris, sfääri mahu ja kogu ruumi mahu suhe. Sel juhul on sfääri maht

kus s=Q+e2 <1/2 ja ns peab olema täisarv.

Viimane paremal pool olev liige on selles summas kõige suurem. Esmalt hindame selle väärtust Stirlingi valemi abil faktorite jaoks. Siis vaatame summas oleva liikme vähenemise koefitsienti, pange tähele, et see koefitsient suureneb liikudes vasakule, seega saame: (1) piirata summa väärtust geomeetrilise progresseerumisega selle algse koefitsiendiga, (2) laiendada geomeetrilist progresseerumist ns liikmest lõpmatusse liikmesse, (3) arvutada lõpmatute geomeetriliste progresseerumiste summa (standardsed algebra, mitte midagi olulist) ja lõpuks saada piirväärtuse (piisavalt suure n jaoks):

Pange tähele, kuidas entropia H(s) ilmus binaaridentiteedis. Pange tähele, et Taylor'i seeria arendamine H(s)=H(Q+e2) annab hinnangu, mis on saadud arvestades ainult esimest derivate ja ignoreerides kõiki teisi. Nüüd kogume lõpliku väljendi:

kus

Kõik, mida peame tegema, on valida e2, nii et e3 < e1, ja siis viimane liige on piisavalt väike, kui n on piisavalt suur. Seega on keskmine viga PE saadud piisavalt väikeseks juhul, kui kanali läbilaskevõime on piisavalt lähedane C-le.
Kui keskmine väärtus kõigi koodide osas on piisavalt väike viga, peab vähemalt üks kood olema sobiv, seega on olemas vähemalt üks sobiv kodeerimissüsteem. See on oluline tulemus, mille Shannon on saanud — „Shannoni teoreem müra kanalite puhul“, kuigi tuleb märkida, et ta tõestas seda palju üldisema juhtumi jaoks kui lihtsalt binaarses sümmeetrilises kanalis, mida mina kasutasin. Üldjuhul on matemaatilised järeldused palju keerulisemad, kuid ideed ei ole nii erinevad, seega saab sageli erijuhtumi näite põhjal avaldada teoreemi tõelist tähendust.

Kritiseerime seda tulemust. Oleme korduvalt rõhutanud: „Piisavalt suurte n puhul”. Kuid kui suur on n? Väga, väga suur, kui soovite samaaegselt olla lähedal kanali läbilaskevõimele ja olla kindel, et andmed edastatakse õigesti! Nii suur, et tegelikult peate ootama väga kaua, et koguda sõnumist nii palju bitte, et pärast seda kodeerida see. Samuti on juhusliku koodeksisõnaraamiku suurus lihtsalt tohutu (kuna sellist sõnaraamatut ei saa esitada lühema vormina kui kõik Mn bitti, samas kui n ja M on väga suured)!

Veakorrektuuri koodid vältida ootamist väga pika sõnumi järele ja selle hilisema kodeerimise ja dekodeerimise kaudu väga suurte koodiraamatute, sest nad väldivad koodiraamatute kasutamist ja kasutavad selle asemel tavapäraseid arvutusi. Lihtsas teoorias sellised koodid tavaliselt kaotavad võime läheneda kanali läbilaskevõimele, samas kui nad säilitavad piisavalt madala vigade sageduse, kuid kui kood parandab palju vigu, saavutavad nad head tulemused. Teisiti öeldes, kui te panete kanali suurema mahutavuse vigade parandamiseks, peate kasutama vigade parandamise võimalust suure osa ajast, st igas saadetud sõnumis peaks olema parandatud suur hulk vigu, vastasel juhul kaotate selle mahutavuse asjata.

Sellegipoolest ei ole ülaltoodud teoreem mõttetu! See näitab, et tõhusad edastussüsteemid peavad kasutama hästi läbi mõeldud kodeerimisscheeme väga pikkade bittide järjestuste jaoks. Näitena võib tuua satelliidid, mis on lahkunud väliste planeetide piiridest; maast ja päikesest eemal liikudes peavad nad parandama üha rohkem ja rohkem vigu andmeplokis: mõni satelliit kasutab päikesepaneele, mis pakuvad umbes 5 W, teised aga tuumajõuallikaid, mille võimsus on ligikaudu sama. Nõrk toide, saatjate väikesed taldrikud ja vastuvõtjate piiratud suurused maal, tohutu kaugus, mille signaal peab ületama — kõik need tegurid nõuavad vigade parandamise kõrge taseme koodide kasutamist tõhusa sidesüsteemi rajamiseks.

Naaseme n-mõõtmelisse ruumi, mida me kasutasime ülaltoodud tõestuses. Rääkides sellest, näitasime, et peaaegu kogu kuulide maht on koondunud välispinnale — seega on peaaegu kindel, et saadetud signaal asub sphere'i pinnal, mis on ehitatud vastuvõetud signaali ümber, isegi kui sellise sphere'i raadius on suhteliselt väike. Seetõttu ei ole üllatav, et pärast suvaliselt suure hulga vigade, nQ, parandamist osutub vastuvõetud signaal nii lähedaseks vigadeta signaalile. Kommunikatsioonikanali maht, mida me varem käsitlesime, on selle fenomeni mõistmise võti. Pange tähele, et sarnased kuulid, mis on ehitatud vigade parandamise Hamming'i koodide jaoks, ei kattuks üksteisega. Suur hulk praktiliselt ortogonaalseid mõõtmeid n-mõõtmelises ruumis näitab, miks saame mahutada M kuuli ruumi minimaalse kattuvusega. Kui lubada väikest, suvaliselt vähest kattuvust, mis suudab põhjustada ainult väikese hulga vigu dekodeerimise protsessis, on võimalik saavutada tihe paiknemine kuuli ruumis. Hamming tagas teatud taseme vigade parandamisest, Shannon aga madala tõenäosuse, kuid säilitades samas tegeliku läbilaskevõime, mis on suvaliselt lähedane kommunikatsioonikanali mahule — seda ei suuda Hamming'i koodid teha.

Informatsiooni teooria ei ütle, kuidas projekteerida tõhusat süsteemi, vaid suunab meid tõhusate side süsteemide poole. See on väärtuslik tööriist masinatevaheliste side süsteemide loomisel, kuid nagu varem mainitud, ei ole tal erilist seost sellega, kuidas inimesed omavahel teavet vahetavad. Bioloogilise pärandi ja tehniliste side süsteemide sarnasuse määr on lihtsalt teadmata, seega ei ole hetkel selge, kui rakendatav informatsiooni teooria geenidele on. Meil ei jää muud üle, kui lihtsalt proovida, ja kui edu näitab meile selle nähtuse masina sarnast olemust, siis ebaõnnestumine osutab teistele olulistele aspektidele teabe loomuses.

Lähme hetkeks kõrvale. Oleme näinud, et kõik esialgsed määratlused peavad suuremal või vähemal määral väljendama meie algsete uskumuste olemust, kuid neile on omane teatud määral moonutust, mistõttu need osutuvad mittetöötavaks. Traditsiooniliselt arvatakse, et viimaks määrab meie kasutatav definitsioon tegelikult olemuse; kuid see näitab meile vaid, kuidas asju käsitleda, andmata meile mingit tähendust. Postulaadi lähenemine, mida matemaatilistes ringkondades nii kõrgelt hinnatakse, jätab praktikas soovida.

Nüüd vaatame IQ-testide näidet, kus määratlemine on nii tsükliline kui soovite, ja seega viib teid eksitusse. Luua test, mis peaks mõõtma intelligentsust. Pärast seda vaadatakse see üle, et see oleks võimalikult järjekindel, ja siis avaldatakse see ning kalibreeritakse lihtsal viisil nii, et mõõdetud 'intelligentsus' oleks normaaljaotuses (loomulikult kalibreerimiskõveraga). Kõiki määratlusi tuleb üle vaadata, mitte ainult siis, kui need esmakordselt esitatakse, vaid ka palju hiljem, kui neid kasutatakse järeldustes. Kuidas määratletud piirid sobivad lahendatava ülesande jaoks? Kui tihti rakendatakse määratlemisi, mis on antud ühes olukorras, piisavalt erinevates olukordades? See juhtub üsna sageli! Humanitaarteadustes, millega te paratamatult kokku puutute oma elus, juhtub see sagedamini.

Seega oli üks selle teabe teooria esituse eesmärke, peale selle kasulikkuse demonstreerimise, hoiatada teid sellest ohtust või näidata, kuidas seda täpselt kasutada soovitud tulemuse saavutamiseks. On ammu märgatud, et algsed määratlused mõjutavad seda, mida te lõpuks leidsite, palju rohkem, kui näib. Algse määratluse puhul on vajalik suur tähelepanu, mitte ainult igas uues olukorras, vaid ka valdkondades, millega olete juba pikka aega tegelenud. See aitab mõista, mil määral saadud tulemused on tautoloogilised, mitte midagi kasulikku.

Tuntud Eddingtoni lugu räägib inimestest, kes püüdsid meres kala võrku. Uurides püütud kalade suurust, määrasid nad minimaalse kalasuuruse, mis meres elab! Nende järeldus põhines kasutatud tööriistal, mitte tegelikkusel.

Jätkub…

Kes soovib aidata raamatu tõlkimisel, kujundamisel ja väljaandmisel — kirjutage isiklikult või e-posti teel magisterludi2016@yandex.ru

Muide, oleme käivitanud tõlke veel ühest lahedast raamatust – „The Dream Machine: Arvutirevolutsiooni lugu“)

Eriti otsime neid, kes aitaksid tõlkida boonuse peatüki, mis on saadaval ainult videos.. (tõlgime 10 minutit, esimesed 20 on juba kirja pandud.)

Raamatu sisu ja tõlgitud peatükidEessõna