Dokázali jsme to!
"Účelem tohoto kurzu je připravit vás na vaši technickou budoucnost."
Dobrý den, Habr. Vzpomeňte si na úžasný článek (+219, 2588 záložek, 429k přečtení)?
Takže Hamming (ano, ano, sebemonitorování a sebeopravování ) existuje celek , napsaný na základě jeho přednášek. Překládáme to, protože ten muž říká, co si myslí.
Toto není kniha jen o IT, je to kniha o stylu myšlení neuvěřitelně cool lidí. „Není to jen podpora pozitivního myšlení; popisuje podmínky, které zvyšují šance na odvedení skvělé práce.“
Děkuji Andrey Pakhomov za překlad.
Informační teorie byla vyvinuta C. E. Shannonem na konci 1940. let XNUMX. století. Vedení Bell Labs trvalo na tom, aby to nazval „Teorie komunikace“, protože... toto je mnohem přesnější název. Z pochopitelných důvodů má název „Teorie informací“ mnohem větší dopad na veřejnost, proto si jej Shannon vybral a je to název, který známe dodnes. Samotný název naznačuje, že teorie se zabývá informacemi, což ji činí důležitou, když se posouváme hlouběji do informačního věku. V této kapitole se dotknu několika hlavních závěrů z této teorie, poskytnu ne striktní, ale spíše intuitivní důkazy o některých jednotlivých ustanoveních této teorie, abyste pochopili, co to vlastně „teorie informace“ je, kde ji můžete použít. a kde ne.
Za prvé, co je to „informace“? Shannon klade rovnítko mezi informace a nejistotu. Zvolil záporný logaritmus pravděpodobnosti události jako kvantitativní míru informace, kterou obdržíte, když nastane událost s pravděpodobností p. Když vám například řeknu, že počasí v Los Angeles je mlhavé, pak se p blíží 1, což nám opravdu mnoho informací nedává. Ale když řeknu, že v červnu v Monterey prší, bude ve zprávě nejistota a bude obsahovat více informací. Spolehlivá událost neobsahuje žádné informace, protože log 1 = 0.
Podívejme se na to podrobněji. Shannon se domníval, že kvantitativní míra informace by měla být spojitou funkcí pravděpodobnosti události p a pro nezávislé události by měla být aditivní – množství informace získané v důsledku výskytu dvou nezávislých událostí by se mělo rovnat množství informací získaných v důsledku vzniku společné události. Například výsledek hodu kostkou a hodu mincí se obvykle považuje za nezávislé události. Přeložme výše uvedené do jazyka matematiky. Jestliže I (p) je množství informací obsažených v události s pravděpodobností p, pak pro společnou událost sestávající ze dvou nezávislých událostí x s pravděpodobností p1 a y s pravděpodobností p2 dostaneme
(x a y jsou nezávislé události)
Toto je funkční Cauchyho rovnice, platí pro všechny p1 a p2. Předpokládejme, že k vyřešení této funkční rovnice
p1 = p2 = p,
toto dává
Pokud p1 = p2 a p2 = p, pak
atd. Rozšíření tohoto procesu pomocí standardní metody pro exponenciály, pro všechna racionální čísla m/n platí následující
Z předpokládané spojitosti informační míry vyplývá, že logaritmická funkce je jediným spojitým řešením Cauchyho funkční rovnice.
V teorii informace je běžné, že základ logaritmu je 2, takže binární výběr obsahuje přesně 1 bit informace. Proto se informace měří podle vzorce
Pojďme se zastavit a pochopit, co se stalo výše. Zaprvé jsme nedefinovali pojem „informace“, pouze jsme definovali vzorec pro její kvantitativní měření.
Za druhé, toto opatření podléhá nejistotě, a přestože je přiměřeně vhodné pro stroje – například telefonní systémy, rádio, televizi, počítače atd. – neodráží normální lidské postoje k informacím.
Za třetí, toto je relativní měřítko, záleží na aktuálním stavu vašich znalostí. Pokud se podíváte na proud „náhodných čísel“ z generátoru náhodných čísel, předpokládáte, že každé další číslo je nejisté, ale pokud znáte vzorec pro výpočet „náhodných čísel“, další číslo bude známé, a proto nebude obsahovat informace.
Shannonova definice informace je tedy v mnoha případech vhodná pro stroje, ale nezdá se, že by odpovídala lidskému chápání tohoto slova. Z tohoto důvodu by se „teorie informací“ měla nazývat „teorie komunikace“. Na změnu definic (které daly teorii její počáteční popularitu a díky kterým si lidé stále myslí, že tato teorie pojednává o „informacích“) je však příliš pozdě, takže s nimi musíme žít, ale zároveň musíte jasně pochopit, jak daleko je Shannonova definice informace od jejího běžně používaného významu. Shannonovy informace se zabývají něčím úplně jiným, totiž nejistotou.
Zde je něco, na co byste měli myslet, když navrhujete jakoukoli terminologii. Jak se navrhovaná definice, jako je Shannonova definice informace, shoduje s vaší původní myšlenkou a jak moc se liší? Neexistuje téměř žádný termín, který by přesně odrážel vaši předchozí vizi konceptu, ale v konečném důsledku je to použitá terminologie, která odráží význam konceptu, takže formalizace něčeho pomocí jasných definic vždy přináší nějaký šum.
Uvažujme systém, jehož abeceda se skládá ze symbolů q s pravděpodobnostmi pí. V tomto případě průměrné množství informací v systému (jeho očekávaná hodnota) se rovná:
To se nazývá entropie systému s rozdělením pravděpodobnosti {pi}. Termín "entropie" používáme, protože stejný matematický tvar se objevuje v termodynamice a statistické mechanice. To je důvod, proč pojem „entropie“ kolem sebe vytváří určitou auru důležitosti, která nakonec není opodstatněná. Stejná matematická forma zápisu neznamená stejnou interpretaci symbolů!
Entropie rozdělení pravděpodobnosti hraje hlavní roli v teorii kódování. Gibbsova nerovnost pro dvě různá rozdělení pravděpodobnosti pi a qi je jedním z důležitých důsledků této teorie. Takže to musíme dokázat
Důkaz je založen na zřejmém grafu, Obr. 13.I, což ukazuje, že
a rovnosti je dosaženo pouze tehdy, když x = 1. Aplikujme nerovnost na každý člen součtu z levé strany:
Pokud se abeceda komunikačního systému skládá z q symbolů, pak vezmeme-li pravděpodobnost přenosu každého symbolu qi = 1/q a dosadíme q, získáme z Gibbsovy nerovnosti
Obrázek 13.I
To znamená, že pokud je pravděpodobnost přenosu všech q symbolů stejná a rovna - 1 / q, pak je maximální entropie rovna ln q, jinak platí nerovnost.
V případě jednoznačně dekódovatelného kódu máme Kraftovu nerovnost
Nyní, když definujeme pseudo-pravděpodobnosti
kde samozřejmě = 1, což vyplývá z Gibbsovy nerovnosti,
a aplikujte trochu algebry (nezapomeňte, že K ≤ 1, takže můžeme vypustit logaritmický člen a později možná posílit nerovnost), dostaneme
kde L je průměrná délka kódu.
Entropie je tedy minimální hranice pro jakýkoli kód znak po symbolu s průměrnou délkou kódového slova L. Toto je Shannonova věta pro kanál bez rušení.
Nyní zvažte hlavní větu o omezeních komunikačních systémů, ve kterých jsou informace přenášeny jako proud nezávislých bitů a je přítomen šum. Rozumí se, že pravděpodobnost správného přenosu jednoho bitu je P > 1/2 a pravděpodobnost, že hodnota bitu bude během přenosu invertována (dojde k chybě), je rovna Q = 1 - P. předpokládejme, že chyby jsou nezávislé a pravděpodobnost chyby je stejná pro každý vyslaný bit – to znamená, že v komunikačním kanálu je „bílý šum“.
Způsob, jakým máme dlouhý proud n bitů zakódovaný do jedné zprávy, je n-rozměrné rozšíření jednobitového kódu. Hodnotu n určíme později. Zvažte zprávu skládající se z n-bitů jako bod v n-rozměrném prostoru. Protože máme n-rozměrný prostor - a pro jednoduchost budeme předpokládat, že každá zpráva má stejnou pravděpodobnost výskytu - existuje M možných zpráv (M bude také definováno později), proto pravděpodobnost jakékoli odeslané zprávy je
(odesílatel)
Rozpis 13.II
Dále zvažte myšlenku kapacity kanálu. Aniž bychom zacházeli do podrobností, kapacita kanálu je definována jako maximální množství informací, které lze spolehlivě přenášet komunikačním kanálem, přičemž se bere v úvahu použití nejúčinnějšího kódování. Neexistuje žádný argument, že komunikačním kanálem lze přenášet více informací, než je jeho kapacita. To lze dokázat pro binární symetrický kanál (který používáme v našem případě). Kapacita kanálu při odesílání bitů je specifikována jako
kde, jako dříve, P je pravděpodobnost žádné chyby v žádném odeslaném bitu. Při odesílání n nezávislých bitů je kapacita kanálu dána
Pokud jsme blízko kapacitě kanálu, pak musíme poslat téměř toto množství informací pro každý ze symbolů ai, i = 1, ..., M. Vzhledem k tomu, že pravděpodobnost výskytu každého symbolu ai je 1 / M, dostaneme
když pošleme kteroukoli z M stejně pravděpodobných zpráv ai, máme
Když je odesláno n bitů, očekáváme výskyt nQ chyb. V praxi u zprávy skládající se z n bitů budeme mít v přijaté zprávě přibližně nQ chyb. Pro velké n relativní variace (variace = šířka distribuce, )
rozložení počtu chyb se bude s rostoucím n stále více zužovat.
Takže ze strany vysílače vezmu zprávu ai k odeslání a nakreslím kolem ní kouli s poloměrem
který je o něco větší o hodnotu rovnající se e2 než očekávaný počet chyb Q, (obrázek 13.II). Pokud je n dostatečně velké, pak existuje libovolně malá pravděpodobnost, že se na straně přijímače objeví bod zprávy bj, který přesahuje tuto kouli. Načrtneme si situaci, jak ji vidím z pohledu vysílače: máme libovolné poloměry od přenášené zprávy ai k přijaté zprávě bj s pravděpodobností chyby rovnou (nebo téměř rovnou) normálnímu rozdělení, dosahující maxima z nQ. Pro jakékoli dané e2 je n tak velké, že pravděpodobnost, že výsledný bod bj bude mimo moji sféru, je tak malá, jak chcete.
Nyní se podívejme na stejnou situaci z vaší strany (obr. 13.III). Na straně přijímače je koule S(r) o stejném poloměru r kolem přijatého bodu bj v n-rozměrném prostoru, takže pokud je přijatá zpráva bj uvnitř mé koule, pak zpráva ai odeslaná mnou je uvnitř vaší koule.
Jak může dojít k chybě? K chybě může dojít v případech popsaných v tabulce níže:
Obrázek 13.III
Zde vidíme, že pokud v kouli postavené kolem přijatého bodu existuje alespoň jeden další bod odpovídající možné odeslané nezakódované zprávě, pak během přenosu došlo k chybě, protože nemůžete určit, která z těchto zpráv byla odeslána. Odeslaná zpráva je bezchybná pouze v případě, že se jí odpovídající bod nachází v kouli a v daném kódu nejsou možné další body, které jsou ve stejné kouli.
Máme matematickou rovnici pro pravděpodobnost chyby Pe, pokud byla odeslána zpráva ai
První faktor můžeme vyhodit ve druhém členu, vezmeme-li jej jako 1. Tak dostaneme nerovnost
Je zřejmé, že
proto
znovu použít na poslední termín vpravo
Vezmeme-li dostatečně velké n, lze první člen považovat za malý, řekněme menší než nějaké číslo d. Proto máme
Nyní se podívejme na to, jak můžeme zkonstruovat jednoduchý substituční kód pro kódování M zpráv skládajících se z n bitů. Shannon neměl ponětí, jak přesně vytvořit kód (kódy na opravu chyb ještě nebyly vynalezeny), zvolil náhodné kódování. Hoďte mincí pro každý z n bitů ve zprávě a opakujte postup pro M zpráv. Celkem je potřeba udělat nM přehození mincí, takže je to možné
kódové slovníky se stejnou pravděpodobností ½ nM. Náhodný proces vytváření číselníku samozřejmě znamená, že existuje možnost duplikátů a také bodů kódu, které budou blízko u sebe a budou tedy zdrojem pravděpodobných chyb. Je třeba dokázat, že pokud k tomu nedojde s pravděpodobností větší než jakákoli malá zvolená chybová úroveň, pak je dané n dostatečně velké.
Rozhodující je, že Shannon zprůměroval všechny možné kódové knihy, aby našel průměrnou chybu! Pro označení průměrné hodnoty nad množinou všech možných náhodných číselníků použijeme symbol Av[.]. Zprůměrování přes konstantu d samozřejmě dává konstantu, protože pro zprůměrování je každý člen stejný jako každý jiný člen v součtu,
které lze zvýšit (M–1 jde na M)
Pro každou danou zprávu při zprůměrování napříč všemi číselníky prochází kódování všemi možnými hodnotami, takže průměrná pravděpodobnost, že je bod v kouli, je poměr objemu koule k celkovému objemu prostoru. Objem koule je
kde s=Q+e2 <1/2 a ns musí být celé číslo.
Poslední výraz vpravo je největší v tomto součtu. Nejprve odhadněme jeho hodnotu pomocí Stirlingova vzorce pro faktoriály. Poté se podíváme na klesající koeficient členu před ním, všimněte si, že tento koeficient roste, když se pohybujeme doleva, a tak můžeme: (1) omezit hodnotu součtu na součet geometrické posloupnosti s tento počáteční koeficient, (2) rozšířit geometrickou posloupnost z n členů na nekonečný počet členů, (3) vypočítat součet nekonečné geometrické posloupnosti (standardní algebra, nic významného) a nakonec získat limitní hodnotu (pro dostatečně velký n):
Všimněte si, jak se entropie H(s) objevila v binomické identitě. Všimněte si, že rozšíření Taylorovy řady H(s)=H(Q+e2) poskytuje odhad získaný s přihlédnutím pouze k první derivaci a ignorování všech ostatních. Nyní dáme dohromady konečný výraz:
kde
Stačí zvolit e2 takové, že e3 < e1, a pak bude poslední člen libovolně malý, pokud je n dostatečně velké. V důsledku toho lze průměrnou chybu PE získat tak malou, jak je požadováno, s kapacitou kanálu libovolně blízkou C.
Pokud má průměr všech kódů dostatečně malou chybu, musí být vhodný alespoň jeden kód, existuje tedy alespoň jeden vhodný kódovací systém. Toto je důležitý výsledek získaný Shannonem - "Shannonův teorém pro šumový kanál", i když je třeba poznamenat, že to dokázal pro mnohem obecnější případ než pro jednoduchý binární symetrický kanál, který jsem použil. Pro obecný případ jsou matematické výpočty mnohem složitější, ale myšlenky se příliš neliší, takže velmi často můžete na příkladu konkrétního případu odhalit skutečný význam věty.
Pojďme kritizovat výsledek. Opakovaně jsme opakovali: "Pro dostatečně velké n." Ale jak velké je n? Velmi, velmi velké, pokud opravdu chcete být blízko kapacitě kanálu a mít jistotu správného přenosu dat! Ve skutečnosti tak velké, že budete muset čekat velmi dlouho, než nashromáždíte zprávu o dostatečném množství bitů, abyste ji mohli později zakódovat. V tomto případě bude velikost slovníku náhodného kódu prostě obrovská (koneckonců, takový slovník nemůže být reprezentován kratší formou než úplný seznam všech bitů Mn, přestože n a M jsou velmi velké)!
Kódy pro opravu chyb se vyhýbají čekání na velmi dlouhou zprávu a jejímu následnému kódování a dekódování prostřednictvím velmi rozsáhlých kódových knih, protože se vyhýbají samotným kódovým knihám a místo toho používají běžné výpočty. V jednoduché teorii mají takové kódy tendenci ztrácet schopnost přiblížit se kapacitě kanálu a stále udržovat nízkou chybovost, ale když kód opraví velké množství chyb, fungují dobře. Jinými slovy, pokud přidělíte určitou kapacitu kanálu opravám chyb, musíte většinu času používat schopnost opravy chyb, tj. v každé odeslané zprávě musí být opraveno velké množství chyb, jinak tuto kapacitu plýtváte.
Přitom výše dokázaná věta stále není nesmyslná! Ukazuje, že efektivní přenosové systémy musí používat chytrá schémata kódování pro velmi dlouhé bitové řetězce. Příkladem jsou satelity, které přeletěly za vnější planety; Jak se vzdalují od Země a Slunce, jsou nuceni opravovat další a další chyby v datovém bloku: některé satelity používají solární panely, které poskytují asi 5 W, jiné využívají jaderné zdroje, které poskytují přibližně stejný výkon. Nízký výkon napájecího zdroje, malá velikost talířů vysílače a omezená velikost talířů přijímače na Zemi, obrovská vzdálenost, kterou musí signál urazit - to vše vyžaduje použití kódů s vysokou úrovní korekce chyb pro vytvoření efektivní komunikační systém.
Vraťme se k n-rozměrnému prostoru, který jsme použili ve výše uvedeném důkazu. Při diskusi jsme ukázali, že téměř celý objem koule je soustředěn blízko vnějšího povrchu - je tedy téměř jisté, že vysílaný signál se bude nacházet poblíž povrchu koule postavené kolem přijímaného signálu, a to i při relativně malý poloměr takové koule. Není proto divu, že se přijatý signál po opravě libovolně velkého počtu chyb, nQ, libovolně blíží signálu bez chyb. Kapacita propojení, o které jsme hovořili dříve, je klíčem k pochopení tohoto jevu. Všimněte si, že podobné koule konstruované pro opravu chyb Hammingových kódů se navzájem nepřekrývají. Velký počet téměř ortogonálních rozměrů v n-rozměrném prostoru ukazuje, proč můžeme umístit M koulí do prostoru s malým přesahem. Pokud připustíme malý, libovolně malý přesah, který může vést jen k malému počtu chyb při dekódování, můžeme získat husté rozmístění koulí v prostoru. Hamming zaručoval určitou míru opravy chyb, Shannon - nízkou pravděpodobnost chyby, ale zároveň zachování skutečné propustnosti libovolně blízké kapacitě komunikačního kanálu, což Hammingovy kódy neumí.
Informační teorie nám neříká, jak navrhnout efektivní systém, ale ukazuje cestu k efektivním komunikačním systémům. Je to cenný nástroj pro budování komunikačních systémů mezi stroji, ale jak již bylo zmíněno dříve, má malý význam pro to, jak spolu lidé komunikují. Míra, do jaké je biologická dědičnost podobná technickým komunikačním systémům, je jednoduše neznámá, takže v současné době není jasné, jak se teorie informace vztahuje na geny. Nezbývá nám nic jiného, než to zkusit, a pokud nám úspěch ukáže strojovou povahu tohoto jevu, pak neúspěch ukáže na další významné aspekty povahy informace.
Neodbíhejme příliš. Viděli jsme, že všechny původní definice ve větší či menší míře musí vyjadřovat podstatu našeho původního přesvědčení, ale vyznačují se určitým stupněm zkreslení, a proto nejsou použitelné. Tradičně se uznává, že v konečném důsledku definice, kterou používáme, ve skutečnosti definuje podstatu; ale to nám pouze říká, jak věci zpracovat, a v žádném případě nám to nedává žádný význam. Postulační přístup, tak silně preferovaný v matematických kruzích, ponechává v praxi mnoho přání.
Nyní se podíváme na příklad IQ testů, kde je definice kruhová, jak chcete, a ve výsledku zavádějící. Vzniká test, který má změřit inteligenci. Poté je revidován, aby byl co nejkonzistentnější, a poté je publikován a jednoduchou metodou kalibrován tak, aby naměřená „inteligence“ byla normálně rozdělena (samozřejmě na kalibrační křivce). Všechny definice musí být překontrolovány, nejen když jsou poprvé navrženy, ale také mnohem později, když jsou použity ve vyvozených závěrech. Do jaké míry jsou definiční hranice vhodné pro řešený problém? Jak často se definice uvedené v jednom nastavení používají ve zcela odlišných nastaveních? To se stává docela často! V humanitních oborech, se kterými se v životě nevyhnutelně setkáte, se to stává častěji.
Jedním z účelů této prezentace teorie informace, kromě demonstrování její užitečnosti, tedy bylo upozornit vás na toto nebezpečí, nebo vám přesně ukázat, jak ji použít k dosažení požadovaného výsledku. Již dlouho se uvádí, že počáteční definice určují, co nakonec najdete, v mnohem větší míře, než se zdá. Prvotní definice od vás vyžadují velkou pozornost nejen v jakékoli nové situaci, ale i v oblastech, se kterými dlouhodobě pracujete. To vám umožní pochopit, do jaké míry jsou získané výsledky tautologií a ne něčím užitečným.
Slavný příběh Eddingtona vypráví o lidech, kteří lovili v moři sítí. Po prostudování velikosti ryb, které ulovili, určili minimální velikost ryb, které se nacházejí v moři! Jejich závěr byl řízen použitým nástrojem, nikoli realitou.
Chcete-li se pokračovat ...
Kdo chce pomoci s překladem, úpravou a vydáním knihy - napište do osobní zprávy nebo emailu [chráněno e-mailem]
Mimochodem, také jsme spustili překlad další skvělé knihy - )
Zvláště hledáme kteří pomohou s překladem , (transfer na 10 minut, prvních 20 je již obsazeno)
Obsah knihy a přeložené kapitoly
- Úvod do The Art of Doing Science and Engineering: Learning to Learn (28. března 1995)
- "Základy digitální (diskrétní) revoluce" (30. března 1995)
- "Historie počítačů - hardware" (31. března 1995)
- "Historie počítačů - software" (4. dubna 1995)
- "Historie počítačů - aplikace" (6. dubna 1995)
- "Umělá inteligence - část I" (7. dubna 1995)
- "Umělá inteligence - část II" (11. dubna 1995)
- "Umělá inteligence III" (13. dubna 1995)
- "n-dimenzionální prostor" (14. dubna 1995)
- "Teorie kódování - Reprezentace informací, část I" (18. dubna 1995)
- "Teorie kódování - Reprezentace informací, část II" (20. dubna 1995)
- "Kódy pro opravu chyb" (21. dubna 1995)
- "Teorie informací" (25. dubna 1995)
- "Digitální filtry, část I" (27. dubna 1995)
- "Digitální filtry, část II" (28. dubna 1995)
- "Digitální filtry, část III" (2. května 1995)
- "Digitální filtry, část IV" (4. května 1995)
- "Simulace, část I" (5. května 1995)
- "Simulace, část II" (9. května 1995)
- "Simulace, část III" (11. května 1995)
- "Vláknová optika" (12. května 1995)
- "Computer Aided Instruction" (16. května 1995)
- "Matematika" (18. května 1995)
- "Kvantová mechanika" (19. května 1995)
- "Kreativita" (23. května 1995). Překlad:
- "Odborníci" (25. května 1995)
- "Nespolehlivá data" (26. května 1995)
- "Systémové inženýrství" (30. května 1995)
- „Dostanete, co změříte“ (1. června 1995)
- (Červen 2, 1995) přeložit po 10 minutových kouscích
- Hamming, „Vy a váš výzkum“ (6. června 1995).
Kdo chce pomoci s překladem, úpravou a vydáním knihy - napište do osobní zprávy nebo emailu [chráněno e-mailem]
Zdroj: www.habr.com