Uspelo nam je!
"Namen tega tečaja je, da vas pripravi na vašo tehnično prihodnost."
Pozdravljeni, Habr. Spomnite se čudovitega članka (+219, 2588 zaznamkov, 429k branj)?
Torej Hamming (da, da, samonadzor in samopopravljanje ) obstaja celota , napisano na podlagi njegovih predavanj. Prevajamo, ker človek pove svoje mnenje.
To ni knjiga samo o IT, je knjiga o slogu razmišljanja neverjetno kul ljudi. »To ni le spodbuda pozitivnega razmišljanja; opisuje pogoje, ki povečujejo možnosti za odlično delo.«
Hvala Andreju Pakhomovu za prevod.
Teorijo informacij je razvil C. E. Shannon v poznih 1940-ih. Vodstvo Bell Labs je vztrajalo, da jo imenuje "teorija komunikacije", ker ... to je veliko bolj natančno ime. Iz očitnih razlogov ima ime "teorija informacij" veliko večji vpliv v javnosti, zato ga je izbrala Shannon in to ime poznamo še danes. Že samo ime nakazuje, da se teorija ukvarja z informacijami, zaradi česar je pomembna, ko se pomikamo globlje v informacijsko dobo. V tem poglavju se bom dotaknil več glavnih sklepov iz te teorije, ne bom zagotovil strogih, ampak bolj intuitivnih dokazov o nekaterih posameznih določbah te teorije, tako da boste razumeli, kaj je pravzaprav "teorija informacij", kje jo lahko uporabite in kje ne.
Najprej, kaj je "informacija"? Shannon informacije enači z negotovostjo. Izbral je negativni logaritem verjetnosti dogodka kot kvantitativno merilo informacij, ki jih prejmete, ko se zgodi dogodek z verjetnostjo p. Na primer, če vam povem, da je vreme v Los Angelesu megleno, potem je p blizu 1, kar nam res ne daje veliko informacij. Če pa povem, da junija v Montereyu dežuje, bo sporočilo negotovo in vsebovalo bo več informacij. Zanesljiv dogodek ne vsebuje nobenih informacij, saj je dnevnik 1 = 0.
Oglejmo si to podrobneje. Shannon je menil, da bi morala biti kvantitativna mera informacije zvezna funkcija verjetnosti dogodka p, za neodvisne dogodke pa bi morala biti aditivna - količina informacij, pridobljenih kot posledica pojava dveh neodvisnih dogodkov, bi morala biti enaka količina informacij, pridobljenih kot posledica nastanka skupnega dogodka. Na primer, izid meta kocke in kovanca se običajno obravnavata kot neodvisna dogodka. Naj zgoraj prevedemo v jezik matematike. Če je I (p) količina informacij, ki jih vsebuje dogodek z verjetnostjo p, potem za skupni dogodek, sestavljen iz dveh neodvisnih dogodkov x z verjetnostjo p1 in y z verjetnostjo p2, dobimo
(x in y sta neodvisna dogodka)
To je funkcionalna Cauchyjeva enačba, ki velja za vse p1 in p2. Za rešitev te funkcionalne enačbe predpostavimo, da
p1 = p2 = p,
to daje
Če je p1 = p2 in p2 = p, potem
itd. Če ta postopek razširimo s standardno metodo za eksponente, za vsa racionalna števila m/n velja naslednje
Iz predpostavljene zveznosti mere informacije sledi, da je logaritemska funkcija edina zvezna rešitev Cauchyjeve funkcionalne enačbe.
V informacijski teoriji je običajno, da je osnova logaritma 2, tako da binarna izbira vsebuje natanko 1 bit informacije. Zato se informacije merijo s formulo
Ustavimo se in razumemo, kaj se je zgodilo zgoraj. Prvič, nismo definirali pojma "informacija", temveč le formulo za njeno kvantitativno mero.
Drugič, ta ukrep je podvržen negotovosti in čeprav je razumno primeren za stroje – na primer telefonske sisteme, radio, televizijo, računalnike itd. – ne odraža običajnega človeškega odnosa do informacij.
Tretjič, to je relativno merilo, odvisno od trenutnega stanja vašega znanja. Če pogledate tok »naključnih števil« iz generatorja naključnih števil, domnevate, da je vsako naslednje število negotova, a če poznate formulo za izračun »naključnih števil«, bo naslednje število znano in zato ne bo vsebujejo informacije.
Torej je Shannonova definicija informacij v mnogih primerih primerna za stroje, vendar se zdi, da ne ustreza človeškemu razumevanju te besede. Iz tega razloga bi se morala "teorija informacij" imenovati "teorija komunikacije". Vendar je prepozno za spreminjanje definicij (ki so teoriji dale prvotno priljubljenost in zaradi katerih ljudje še vedno mislijo, da se ta teorija ukvarja z "informacijami"), zato moramo živeti z njimi, hkrati pa morate jasno razumeti, kako daleč je Shannonova definicija informacije od njenega običajno uporabljenega pomena. Shannonine informacije obravnavajo nekaj povsem drugega, namreč negotovost.
Tukaj je nekaj, o čemer morate razmišljati, ko predlagate katero koli terminologijo. Kako se predlagana definicija, kot je Shannonova definicija informacije, ujema z vašo prvotno idejo in kako drugačna je? Skoraj ni izraza, ki bi natančno odražal vašo prejšnjo vizijo koncepta, a navsezadnje je uporabljena terminologija tista, ki odraža pomen koncepta, zato formalizacija nečesa z jasnimi definicijami vedno povzroči nekaj hrupa.
Razmislite o sistemu, katerega abeceda je sestavljena iz simbolov q z verjetnostjo pi. V tem primeru povprečna količina informacij v sistemu (njena pričakovana vrednost) je enaka:
To se imenuje entropija sistema z verjetnostno porazdelitvijo {pi}. Izraz "entropija" uporabljamo, ker se ista matematična oblika pojavlja v termodinamiki in statistični mehaniki. Zato izraz "entropija" ustvarja okoli sebe določeno avro pomembnosti, ki pa v končni fazi ni upravičena. Ista matematična oblika zapisa ne pomeni enake interpretacije simbolov!
Entropija verjetnostne porazdelitve ima pomembno vlogo v teoriji kodiranja. Gibbsova neenakost za dve različni verjetnostni porazdelitvi pi in qi je ena od pomembnih posledic te teorije. Torej moramo to dokazati
Dokaz temelji na očitnem grafu, sl. 13.I, kar kaže na to
enakost pa je dosežena šele, ko je x = 1. Uporabimo neenakost za vsak člen vsote z leve strani:
Če je abeceda komunikacijskega sistema sestavljena iz q simbolov, potem vzamemo verjetnost prenosa vsakega simbola qi = 1/q in nadomestimo q, dobimo iz Gibbsove neenakosti
Slika 13.I
To pomeni, da če je verjetnost prenosa vseh q simbolov enaka in enaka - 1 / q, potem je največja entropija enaka ln q, sicer neenakost velja.
V primeru enolično dekodljive kode imamo Kraftovo neenakost
Zdaj, če definiramo psevdo-verjetnosti
kje seveda = 1, kar izhaja iz Gibbsove neenakosti,
in uporabimo malo algebre (ne pozabite, da je K ≤ 1, tako da lahko opustimo logaritemski člen in morda pozneje okrepimo neenakost), dobimo
kjer je L povprečna dolžina kode.
Tako je entropija najmanjša meja za katero koli kodo znak za simbolom s povprečno dolžino kodne besede L. To je Shannonov izrek za kanal brez motenj.
Zdaj razmislite o glavnem izreku o omejitvah komunikacijskih sistemov, v katerih se informacije prenašajo kot tok neodvisnih bitov in je prisoten šum. Razume se, da je verjetnost pravilnega prenosa enega bita P > 1/2, verjetnost, da bo vrednost bita med prenosom obrnjena (prišlo bo do napake), pa je enaka Q = 1 - P. Zaradi priročnosti smo predpostavimo, da so napake neodvisne in je verjetnost napake enaka za vsak poslani bit - to pomeni, da je v komunikacijskem kanalu "beli šum".
Način, kako imamo dolg tok n bitov, kodiranih v eno sporočilo, je n-dimenzionalna razširitev enobitne kode. Vrednost n bomo določili kasneje. Razmislite o sporočilu, sestavljenem iz n-bitov, kot točki v n-dimenzionalnem prostoru. Ker imamo n-dimenzionalni prostor - in zaradi enostavnosti bomo predpostavili, da ima vsako sporočilo enako verjetnost pojava - obstaja M možnih sporočil (M bo tudi definirano kasneje), zato je verjetnost katerega koli poslanega sporočila
(pošiljatelj)
Urnik 13.II
Nato upoštevajte idejo o zmogljivosti kanala. Ne da bi se spuščali v podrobnosti, je zmogljivost kanala opredeljena kot največja količina informacij, ki jih je mogoče zanesljivo prenesti po komunikacijskem kanalu, ob upoštevanju uporabe najučinkovitejšega kodiranja. Nobenega argumenta ni, da je mogoče prek komunikacijskega kanala prenesti več informacij, kot je njegova zmogljivost. To lahko dokažemo za binarni simetrični kanal (ki ga uporabljamo v našem primeru). Zmogljivost kanala pri pošiljanju bitov je navedena kot
kjer je, kot prej, P verjetnost odsotnosti napake v katerem koli poslanem bitu. Pri pošiljanju n neodvisnih bitov je zmogljivost kanala podana z
Če smo blizu zmogljivosti kanala, potem moramo poslati skoraj toliko informacij za vsakega od simbolov ai, i = 1, ..., M. Glede na to, da je verjetnost pojava vsakega simbola ai 1 / M, dobimo
ko pošljemo katero koli od M enako verjetnih sporočil ai, imamo
Ko je poslanih n bitov, pričakujemo, da se bo pojavilo nQ napak. V praksi bomo imeli za sporočilo, sestavljeno iz n-bitov, približno nQ napak v prejetem sporočilu. Za velike n, relativna variacija (variacija = širina porazdelitve, )
porazdelitev števila napak bo z naraščanjem n vedno bolj ozka.
Torej, s strani oddajnika vzamem sporočilo ai za pošiljanje in okoli njega narišem kroglo s polmerom
ki je za znesek, enak e2, nekoliko večji od pričakovanega števila napak Q, (slika 13.II). Če je n dovolj velik, potem obstaja poljubno majhna verjetnost, da se sporočilna točka bj pojavi na sprejemni strani, ki sega izven te krogle. Skicirajmo situacijo, kot jo vidim jaz z vidika oddajnika: imamo kakršne koli polmere od oddanega sporočila ai do prejetega sporočila bj z verjetnostjo napake, ki je enaka (ali skoraj enaka) normalni porazdelitvi, ki doseže maksimum od nQ. Za vsak dani e2 je n tako velik, da je verjetnost, da bo nastala točka bj zunaj moje krogle, tako majhna, kot želite.
Zdaj pa poglejmo isto situacijo z vaše strani (slika 13.III). Na strani prejemnika je krogla S(r) enakega polmera r okoli prejete točke bj v n-dimenzionalnem prostoru, tako da če je prejeto sporočilo bj znotraj moje krogle, je sporočilo ai, ki sem ga poslal jaz, znotraj vaše krogla.
Kako lahko pride do napake? Napaka se lahko pojavi v primerih, opisanih v spodnji tabeli:
Slika 13.III
Tukaj vidimo, da če je v krogli, zgrajeni okoli prejete točke, vsaj še ena točka, ki ustreza morebitnemu poslanemu nekodiranemu sporočilu, potem je med prenosom prišlo do napake, saj ne morete ugotoviti, katero od teh sporočil je bilo poslano. Poslano sporočilo je brez napak le, če je točka, ki mu ustreza, v krogli in v dani kodi ni možnih drugih točk, ki bi bile v isti krogli.
Imamo matematično enačbo za verjetnost napake Pe, če je bilo sporočilo ai poslano
Prvi faktor lahko v drugem členu izločimo in ga vzamemo za 1. Tako dobimo neenakost
Očitno je,
torej
znova se prijavi na zadnji termin na desni
Če je n dovolj velik, lahko prvi člen vzamemo tako majhnega, kot želimo, recimo manj kot neko število d. Zato imamo
Zdaj pa poglejmo, kako lahko sestavimo preprosto nadomestno kodo za kodiranje M sporočil, sestavljenih iz n bitov. Ker ni imela pojma, kako natančno sestaviti kodo (kode za popravljanje napak še niso bile izumljene), je Shannon izbrala naključno kodiranje. Vrzite kovanec za vsakega od n bitov v sporočilu in ponovite postopek za M sporočil. Skupno je treba izvesti nM metov kovancev, tako da je to mogoče
kodnih slovarjev z enako verjetnostjo ½nM. Seveda naključni proces izdelave šifranta pomeni, da obstaja možnost dvojnikov, pa tudi kodnih točk, ki bodo blizu ena drugi in bodo zato vir verjetnih napak. Dokazati je treba, da če se to ne zgodi z verjetnostjo, ki je večja od katere koli majhne izbrane stopnje napake, potem je dani n dovolj velik.
Ključna točka je, da je Shannon izračunal povprečje vseh možnih šifrantov, da bi našel povprečno napako! Za označevanje povprečne vrednosti nad množico vseh možnih naključnih šifrantov bomo uporabili simbol Av[.]. Povprečenje na konstanto d seveda daje konstanto, saj je za povprečenje vsak člen enak vsakemu drugemu členu v vsoti,
ki se lahko poveča (M–1 gre v M)
Za katero koli dano sporočilo pri povprečevanju vseh šifrantov kodiranje poteka skozi vse možne vrednosti, tako da je povprečna verjetnost, da je točka v krogli, razmerje med prostornino krogle in celotno prostornino prostora. Prostornina krogle je
kjer je s=Q+e2 <1/2 in mora biti ns celo število.
Zadnji člen na desni je največji v tej vsoti. Najprej ocenimo njegovo vrednost s pomočjo Stirlingove formule za faktorijele. Nato bomo pogledali padajoči koeficient člena pred njim in opazili, da ta koeficient narašča, ko se premikamo v levo, in tako lahko: (1) vrednost vsote omejimo na vsoto geometrijske progresije z ta začetni koeficient, (2) razširimo geometrijsko napredovanje od ns členov na neskončno število členov, (3) izračunamo vsoto neskončnega geometrijskega napredovanja (standardna algebra, nič pomembnega) in končno dobimo mejno vrednost (za dovolj veliko n):
Opazite, kako se je entropija H(s) pojavila v binomski identiteti. Upoštevajte, da Taylorjev niz H(s)=H(Q+e2) daje oceno, pridobljeno ob upoštevanju samo prvega odvoda in zanemarjanja vseh drugih. Zdaj pa sestavimo končni izraz:
če
Vse, kar moramo storiti, je izbrati e2 tako, da je e3 < e1, in potem bo zadnji člen poljubno majhen, dokler je n dovolj velik. Posledično lahko dobimo povprečno napako PE tako majhno, kot želimo, s kapaciteto kanala, ki je poljubno blizu C.
Če ima povprečje vseh kod dovolj majhno napako, mora biti vsaj ena koda ustrezna, torej obstaja vsaj en ustrezen sistem kodiranja. To je pomemben rezultat, ki ga je dobil Shannon - "Shannonov izrek za hrupni kanal", čeprav je treba opozoriti, da je to dokazal za veliko bolj splošen primer kot za preprost binarni simetrični kanal, ki sem ga uporabil. V splošnem primeru so matematični izračuni veliko bolj zapleteni, vendar ideje niso tako različne, zato lahko zelo pogosto na primeru določenega primera razkrijete pravi pomen izreka.
Kritizirajmo rezultat. Večkrat smo ponovili: "Za dovolj velik n." Toda kako velik je n? Zelo, zelo veliko, če res želite biti blizu zmogljivosti kanala in biti prepričani v pravilen prenos podatkov! Pravzaprav tako veliko, da boste morali čakati zelo dolgo, da boste zbrali sporočilo z dovolj bitov, da ga boste lahko kasneje kodirali. V tem primeru bo velikost slovarja naključne kode preprosto ogromna (navsezadnje takšnega slovarja ni mogoče predstaviti v krajši obliki kot popoln seznam vseh Mn bitov, kljub dejstvu, da sta n in M zelo velika)!
Kode za popravljanje napak se izogibajo čakanju na zelo dolgo sporočilo ter njegovemu nato kodiranju in dekodiranju prek zelo velikih šifrantov, ker se same izogibajo šifrantom in namesto tega uporabljajo običajno računanje. V preprosti teoriji takšne kode ponavadi izgubijo zmožnost približevanja zmogljivosti kanala in še vedno ohranjajo nizko stopnjo napake, ko pa koda popravi veliko število napak, delujejo dobro. Z drugimi besedami, če nekaj zmogljivosti kanala dodelite odpravljanju napak, potem morate večino časa uporabljati zmožnost odpravljanja napak, tj. v vsakem poslanem sporočilu je treba popraviti veliko število napak, sicer zapravite to zmogljivost.
Hkrati pa zgoraj dokazani izrek še vedno ni brez pomena! Kaže, da morajo učinkoviti prenosni sistemi uporabljati pametne sheme kodiranja za zelo dolge bitne nize. Primer so sateliti, ki so leteli onkraj zunanjih planetov; Ko se oddaljujejo od Zemlje in Sonca, so prisiljeni popravljati vedno več napak v podatkovnem bloku: nekateri sateliti uporabljajo sončne celice, ki zagotavljajo približno 5 W, drugi uporabljajo jedrske vire energije, ki zagotavljajo približno enako moč. Majhna moč napajalnika, majhna velikost oddajnih krožnikov in omejena velikost sprejemnih krožnikov na Zemlji, ogromna razdalja, ki jo mora prepotovati signal - vse to zahteva uporabo kod z visoko stopnjo popravljanja napak za izgradnjo učinkovit komunikacijski sistem.
Vrnimo se k n-dimenzionalnemu prostoru, ki smo ga uporabili v zgornjem dokazu. Pri razpravi smo pokazali, da je skoraj celotna prostornina krogle koncentrirana blizu zunanje površine - torej je skoraj gotovo, da se bo poslani signal nahajal blizu površine krogle, zgrajene okoli sprejetega signala, tudi z relativno majhen polmer takšne krogle. Zato ni presenetljivo, da se prejeti signal po popravku poljubno velikega števila napak nQ izkaže za poljubno blizu signala brez napak. Zmogljivost povezave, o kateri smo razpravljali prej, je ključ do razumevanja tega pojava. Upoštevajte, da se podobne krogle, izdelane za Hammingove kode, ki popravljajo napake, ne prekrivajo. Veliko število skoraj pravokotnih razsežnosti v n-dimenzionalnem prostoru kaže, zakaj lahko M krogel postavimo v prostor z malo prekrivanja. Če dovolimo majhno, poljubno majhno prekrivanje, ki lahko povzroči le majhno število napak pri dekodiranju, lahko dobimo gosto postavitev krogel v prostoru. Hamming je zagotovil določeno stopnjo popravljanja napak, Shannon - nizko verjetnost napake, a hkrati ohranjanje dejanske prepustnosti poljubno blizu zmogljivosti komunikacijskega kanala, česar Hammingove kode ne zmorejo.
Informacijska teorija nam ne pove, kako oblikovati učinkovit sistem, vendar kaže pot do učinkovitih komunikacijskih sistemov. Je dragoceno orodje za gradnjo komunikacijskih sistemov stroj-stroj, vendar, kot smo že omenili, nima velikega pomena za to, kako ljudje komunicirajo med seboj. Obseg, do katerega je biološka dediščina podobna tehničnim komunikacijskim sistemom, preprosto ni znan, zato trenutno ni jasno, kako se teorija informacij uporablja za gene. Ni nam preostalo drugega, kot da poskusimo, in če nam uspeh pokaže strojno naravo tega pojava, bo neuspeh pokazal na druge pomembne vidike narave informacij.
Ne zapustimo se preveč. Videli smo, da morajo vse izvirne definicije v večji ali manjši meri izražati bistvo naših prvotnih prepričanj, vendar so zanje značilna določena stopnja popačenja in zato niso uporabne. Tradicionalno velja, da navsezadnje definicija, ki jo uporabljamo, dejansko definira bistvo; toda to nam samo pove, kako stvari obdelati, in nam nikakor ne pomeni nobenega pomena. Postulacijski pristop, ki je v matematičnih krogih tako močno naklonjen, v praksi pušča veliko želenega.
Zdaj si bomo ogledali primer IQ testov, kjer je definicija tako krožna, kot želite, in posledično zavajajoča. Nastane test, ki naj bi meril inteligenco. Nato se revidira, da postane čim bolj dosleden, nato pa se objavi in na preprost način umeri, tako da se izkaže, da je izmerjena »inteligenca« normalno porazdeljena (na umeritveni krivulji, seveda). Vse definicije je treba ponovno preveriti, ne le takrat, ko so prvič predlagane, ampak tudi mnogo kasneje, ko se uporabijo v sklepih. V kolikšni meri so definicijske meje primerne za problem, ki ga rešujemo? Kako pogosto se definicije, podane v enem okolju, uporabijo v precej različnih okoljih? To se zgodi precej pogosto! V humanistiki, s katero se boste v življenju neizogibno srečevali, se to dogaja pogosteje.
Tako je bil eden od namenov te predstavitve informacijske teorije, poleg prikaza njene uporabnosti, tudi opozoriti na to nevarnost oziroma pokazati, kako natančno jo uporabiti za doseganje želenega rezultata. Že dolgo je bilo ugotovljeno, da začetne definicije določajo, kaj boste našli na koncu, v veliko večji meri, kot se zdi. Začetne definicije od vas zahtevajo veliko pozornosti, ne samo v vsaki novi situaciji, ampak tudi na področjih, s katerimi se že dolgo ukvarjate. Tako boste razumeli, v kolikšni meri so dobljeni rezultati tavtologija in ne nekaj uporabnega.
Znana zgodba o Eddingtonu govori o ljudeh, ki so v morju lovili ribe z mrežo. Po študiju velikosti rib, ki so jih ujeli, so določili najmanjšo velikost rib, ki se nahajajo v morju! Njihov zaključek je temeljil na uporabljenem instrumentu, ne na realnosti.
Se nadaljuje ...
Kdor želi pomagati pri prevodu, postavitvi in izidu knjige - pišite v osebno sporočilo ali mail [e-pošta zaščitena]
Mimogrede, lansirali smo tudi prevod še ene kul knjige - )
Posebej iščemo tisti, ki bodo pomagali prevajati . (prenos za 10 minut, prvih 20 je že zavzetih)
Vsebina knjige in prevedena poglavja
- Uvod v umetnost dela znanosti in inženiringa: Učiti se učiti (28. marec 1995)
- "Temelji digitalne (diskretne) revolucije" (30. marec 1995)
- "Zgodovina računalnikov - strojna oprema" (31. marec 1995)
- "Zgodovina računalnikov - programska oprema" (4. april 1995)
- "Zgodovina računalnikov - aplikacije" (6. april 1995)
- "Umetna inteligenca - I. del" (7. april 1995)
- "Umetna inteligenca - II. del" (11. april 1995)
- "Umetna inteligenca III" (13. april 1995)
- "n-dimenzionalni prostor" (14. april 1995)
- "Teorija kodiranja - predstavitev informacij, I. del" (18. april 1995)
- "Teorija kodiranja - predstavitev informacij, II. del" (20. april 1995)
- "Kode za popravljanje napak" (21. april 1995)
- "Teorija informacij" (25. april 1995)
- "Digitalni filtri, I. del" (27. april 1995)
- "Digitalni filtri, II. del" (28. april 1995)
- "Digitalni filtri, III. del" (2. maj 1995)
- "Digitalni filtri, del IV" (4. maj 1995)
- "Simulacija, I. del" (5. maj 1995)
- "Simulacija, II. del" (9. maj 1995)
- "Simulacija, III. del" (11. maj 1995)
- "Fiber Optics" (12. maj 1995)
- "Računalniško podprto poučevanje" (16. maj 1995)
- "Matematika" (18. maj 1995)
- "Kvantna mehanika" (19. maj 1995)
- "Ustvarjalnost" (23. maj 1995). Prevod:
- "Strokovnjaki" (25. maj 1995)
- "Nezanesljivi podatki" (26. maj 1995)
- "Sistemski inženiring" (30. maj 1995)
- "Dobiš, kar meriš" (1. junij 1995)
- (Junij 2, 1995) prevajati v 10-minutnih delih
- Hamming, "Vi in vaše raziskave" (6. junij 1995).
Kdor želi pomagati pri prevodu, postavitvi in izidu knjige - pišite v osebno sporočilo ali mail [e-pošta zaščitena]
Vir: www.habr.com