Náhodný prostor událostí
V roce 1946 navrhl americký statistik John Tukey název BIT
Představte si prostor náhodných událostíkterý sestává z házení jedné falešné mince, na jehož obou stranách je orel. Kdy padne orel? Je jasné, že vždy. Víme to předem, protože náš prostor je uspořádán. Pád orla je spolehlivá událost, to znamená, že jeho pravděpodobnost je rovna 1. Dáme mnoho informací, pokud řekneme o orli? Ne Množství informací v takové zprávě, které budeme považovat za rovné 0.
Nyní si hodíme poctivou mincí:na jedné straně jsou to hlavy a na druhé ocasy, jak má být. Přistávací hlavy nebo ocasy budou dvě různé události, které tvoří náš prostor náhodných událostí. Pokud oznámíme výsledek jednoho hodu, bude to skutečně nová informace. Pokud padnou hlavy, oznámíme 0, a pokud budou ocasy 1. K nahlášení této informace potřebujeme pouze 1 bit.
co se změnilo?V našem prostoru akcí se objevila nejistota. Máme o tom co říct někomu, kdo sám nehází mincí a nevidí výsledek losování. Ale aby správně pochopil naše sdělení, musí přesně vědět, co děláme a co znamenají nuly a jedničky.Naše prostory pro události musí odpovídat a proces dekódování jedinečně obnovuje výsledek hodu.Pokud se prostor událostí vysílače a přijímače neshoduje nebo neexistuje možnost jednoznačného dekódování zprávy, zůstane informace pouze šumem v komunikačním kanálu.
Pokud hodíte dva nezávisle a současněmincí, pak budou čtyři různé stejně pravděpodobné výsledky: hlavy-hlavy, hlavy-ocasy, ocasy-hlavy a ocasy-ocasy. K přenosu informace budeme potřebovat 2 bity a naše zprávy budou následující: 00, 01, 10 a 11. Informací je dvakrát více. Stalo se tak proto, že se zvýšila nejistota. Pokud se pokusíme uhodnout výsledek takového párového losování, máme dvojnásobnou šanci, že se zmýlíme.
Čím větší je nejistota prostoru událostí, tím více informací zpráva o jeho stavu obsahuje.
Pojďme si trochu zkomplikovat náš eventový prostor.Dosud byly všechny události, které se staly, stejně pravděpodobné. Ale v reálných prostorech nemají všechny události stejnou pravděpodobnost. Řekněme, že pravděpodobnost, že vrána, kterou vidíme, bude černá, se blíží 1. Pravděpodobnost, že první kolemjdoucí, kterého potkáme na ulici, bude muž, je přibližně 0,5. Potkat krokodýla v ulicích Moskvy je ale téměř nemožné. Intuitivně chápeme, že zpráva o setkání s krokodýlem má mnohem větší informační hodnotu než o černé vráně.Čím nižší je pravděpodobnost události, tím více informací ve zprávě o takové události.
Nechť prostor událostí není tak exotický. Jen stojíme u okna a podíváme se na projíždějící auta. Projíždějí se auta čtyř barev, které musíme hlásit. Abychom to dokázali, zakódujeme barvy: černá - 00, bílá - 01, červená - 10, modrá - 11. Abychom přesně informovali o tom, které auto řídilo, stačí přenést 2 kousky informací.
Ale na dlouhou dobu sleduji auta,Všimněte si, že barva auta je nerovnoměrně rozložena: černá - 50% (každou sekundu), bílá - 25% (jedno ze čtyř), červená a modrá - o 12,5% (jeden v osmi). Poté můžete optimalizovat přenášené informace.
Většina aut je černá, takžeoznačme černou - 0 - nejkratší kód a nechť kód všech ostatních začíná na 1. Ze zbývající poloviny bílá - 10 a zbývající barvy začínají na 11. Nakonec označme červenou - 110 a modrou - 111.
Nyní, když předáváme informace o barvě auta, můžeme ho více zakódovat.
Shannon Entropie
Nechť se náš prostor akce skládá z nrůzné události. Při hodu dvouhlavou je právě jedna taková událost, při hodu jedné poctivé mince právě 2, při hodu dvěma mincemi nebo sledování aut právě 4. Každá událost má pravděpodobnost, že nastane. Při hodu dvouhlavou mincí nastane jedna událost (vypadnutí hlav) a její pravděpodobnost je p1 = 1. Při hodu poctivou mincí nastanou dvě události, jsou stejně pravděpodobné a pravděpodobnost každé je 0,5: p1 = 0,5, p2 = 0,5. Při házení dvou poctivých mincí nastanou čtyři události, všechny jsou stejně pravděpodobné a pravděpodobnost každé je 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. Při pozorování automobilů jsou čtyři události a mají různé pravděpodobnosti: černá - 0,5, bílá - 0,25, červená - 0,125, modrá - 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
To není náhoda.Shannon si vybral entropii (míru nejistoty v prostoru události) tak, že byly splněny tři podmínky:
- 1Entropie spolehlivé události, jejíž pravděpodobnost je 1, se rovná 0.
- Entropie dvou nezávislých událostí se rovná součtu entropií těchto událostí.
- Entropie je maximální, pokud jsou všechny události stejně pravděpodobné.
Všechny tyto požadavky jsou plně v souladu s našimipředstavy o nejistotě prostoru události. Pokud existuje pouze jedna událost (první příklad), neexistuje žádná nejistota. Pokud jsou události nezávislé – nejistota součtu je rovna součtu nejistot – jednoduše se sčítají (příklad házení dvou mincí). A konečně, pokud jsou všechny události stejně pravděpodobné, pak je stupeň nejistoty systému maximální. Stejně jako v případě hození dvěma mincemi jsou všechny čtyři události stejně pravděpodobné a entropie je 2, je větší než v případě aut, kdy jsou události také čtyři, ale mají různé pravděpodobnosti - v tomto případě je entropie 1,75.
Veličina H hraje ústřední roli v teorii informace jako míra informace, výběru a nejistoty.
Claude Shannon
Claude Elwood Shannon- Americký inženýr, kryptoanalytik amatematik. Považován za „otce informačního věku“. Zakladatel teorie informace, která našla uplatnění v moderních high-tech komunikačních systémech. Poskytoval základní pojmy, myšlenky a jejich matematické formulace, které v současnosti tvoří základ pro moderní komunikační technologie.
V roce 1948 navrhl použít slovo "bit"označit nejmenší jednotku informací. On také demonstroval, že entropie zadaná jím je ekvivalentní nejistotě informací v přenášené zprávě. Shannon je články “matematická teorie komunikace” a “teorie komunikace v tajných systémech” být zvažován základní pro teorii informací a kryptografii.
Během druhé světové války Shannon pracoval v Bellových laboratořích na vývoji kryptografických systémů, které mu později pomohly objevit metody kódování opravující chyby.
Shannon významně přispěl k teorii pravděpodobnostních schémat, teorii her, teorii automatů a teorii řídících systémů - oblastech vědy, které jsou součástí konceptu kybernetiky.
Kódování
A hozené mince a projíždějící auta nejsoujsou podobné číslům 0 a 1. Chcete-li nahlásit události, ke kterým dochází v prostorech, musíte si představit způsob, jak tyto události popsat. Tento popis se nazývá kódování.
Zprávy lze kódovat nekonečným množstvím různých způsobů. Ale Shannon ukázal, že nejkratší kód nemůže být v bitech menší než entropie.
Proto je entropie zprávy měřítkeminformace ve zprávě. Protože ve všech uvažovaných případech je počet bitů při kódování roven entropii, znamená to, že kódování bylo optimální. Zkrátka už není možné kódovat zprávy o dění v našich prostorách.
Při optimálním kódování nemůžete ztratit respzkreslit jeden přenášený bit ve zprávě. Pokud dojde ke ztrátě byť jen jednoho bitu, informace budou zkreslené. Všechny skutečné komunikační kanály však neposkytují 100% jistotu, že všechny části zprávy dorazí k příjemci nezkreslené.
Chcete-li tento problém vyřešit, musíte to udělatkód není optimální, ale nadbytečný. Odešlete například spolu se zprávou její kontrolní součet - speciálně vypočítanou hodnotu získanou při převodu kódu zprávy, kterou lze ověřit přepočtem po přijetí zprávy. Pokud se přenášený kontrolní součet shoduje s vypočteným, pravděpodobnost, že přenos byl bezchybný, bude poměrně vysoká. A pokud se kontrolní součet neshoduje, musíte požádat o opakovaný přenos. Zhruba takto dnes funguje většina komunikačních kanálů, například při přenosu paketů informací přes internet.
Zprávy přirozeného jazyka
Zvažte prostor událostí, který se skládáz pracovních míst v přirozeném jazyce. To je zvláštní případ, ale jeden z nejdůležitějších. Události zde budou přenášené znaky (písmena pevné abecedy). Tyto znaky se nacházejí v jazyce s různými pravděpodobnostmi.
Nejfrekvenční symbol (tj. Jeden, kterýje nejvíce často nalezený ve všech textech psaných v ruštině) je prostor: tisíce charakterů, průměrný prostor je nalezený 175 časů. Druhá frekvence je symbol “o” - 90, následovaný jinými samohláskami: “e” (nebo “e” - my nebudeme rozlišovat je) - 72, “a” - 62, a i - 62, a jediný další \ t první souhláska "t" - 53. A nejvzácnější "f" - tento symbol se nachází pouze dvakrát na tisíc znaků.
Použijeme ruskou abecedu 31 písmenjazyk (neliší se „e“ a „e“, stejně jako „ъ“ a „ь“). Pokud by se všechna písmena vyskytovala v jazyce se stejnou pravděpodobností, pak by entropie na symbol byla H = 5 bitů, ale pokud vezmeme v úvahu skutečné frekvence symbolů, entropie bude menší: H = 4,35 bitů. (To je téměř dvakrát méně než u tradičního kódování, když je znak přenášen jako bajt - 8 bitů).
Ale entropie charakteru v jazyce je ještě nižší. Pravděpodobnost výskytu dalšího znaku není zcela předurčena průměrnou frekvencí znaku ve všech textech. Který znak bude následovat závisí na již přenesených postavách. Například v moderním ruštině po symbolu "ъ" nemůže následovat zvuk souhlásky. Po dvou následných samohláskách “e”, třetí samohláska “e” následuje extrémně zřídka, ledaže ve slově “dlouho-hrdelný”. To znamená, že další znak je do jisté míry předem určen. Pokud vezmeme v úvahu takovou předurčenost dalšího symbolu, nejistota (tj. Informace) dalšího symbolu bude ještě menší než 4,35. Podle některých odhadů, následující symbol v ruštině je předurčený strukturou jazyka více než 50%, to znamená, s optimálním kódováním, všechny informace mohou být přenášeny smazáním poloviny dopisů od zprávy.
Další věc je, že ne každý dopis lze bezpečně smazat. Vysokofrekvenční "o" (a obecně samohlásky), například, je snadno překračovat, ale vzácné "f" nebo "e" je poměrně problematické.
Přirozený jazyk, kterým spolu komunikujeme, je vysoce redundantní, a proto spolehlivý; pokud jsme něco špatně zaslechli, nevadí, informace se stejně přenesou.
Do doby, než Shannon zavedl měřítko informací, jsme nemohli pochopit, že jazyk je nadbytečný, a do jaké míry můžeme zprávy komprimovat (a proč jsou textové soubory archivátorem tak dobře komprimovány).
Redundance přirozeného jazyka
V článku "O tom, jak vorpsimanie tektkt"(název zní přesně takhle!) fragment románu Ivana Turgeneva Noble Nest byl vzat a podroben nějaké transformaci: 34% písmen, ale ne náhodných, bylo z fragmentu odstraněno. První a poslední písmena ve slovech byla ponechána, pouze samohlásky byly vymazány a ne všechny. Cílem nebylo pouze získat zpět všechny informace o převedeném textu, ale také zajistit, aby osoba, která tento text přečetla, nezažila žádné zvláštní potíže kvůli chybějícím písmenům.
Proč je relativně snadné číst toto poškozenétext? Ve skutečnosti obsahuje potřebné informace k rekonstrukci celých slov. Rodilý mluvčí ruštiny má určitý soubor událostí (slova a celé věty), které používá k rozpoznání. Kromě toho má mluvčí k dispozici také standardní jazykové struktury, které mu pomáhají získat informace. Například,"Ona je blae blee"- s vysokou pravděpodobností lze číst jako"Byla citlivější.". Ale bráno samostatně"Je víc bla", spíše bude obnoven jako„Byla bělejší“. Jelikož v každodenní komunikaci jednámes kanály, ve kterých je šum a rušení, jsme docela dobří v obnovování informací, ale pouze těch, které již předem známe. Například fráze"Její funkce nejsou v nejmenším příjemné, htya nmngo rspkhli a splash"čte se dobře až na poslední slovo"Splash" - "shromáždil". Toto slovo není v moderním lexikonu. Při rychlém čtení slova"Splash"čte se spíše jako „přilepená k sobě“; když je pomalá, jednoduše to mate.
Digitalizace signálu
Zvuk nebo akustické kmity jsou sinusoidy. To lze vidět například na obrazovce zvukového editoru. Pro přesné vyjádření zvuku budete potřebovat nekonečný počet hodnot - celou sinusovou vlnu. To je možné s analogovým připojením. Zpívá - posloucháte, kontakt není přerušen, dokud trvá píseň.
V digitální komunikaci přes kanál můžeme přenášet pouze konečný počet hodnot. Znamená to, že zvuk nelze přesně reprodukovat? Ukázalo se, že ne.
Různé zvuky jsou různě modulovaná sinusovka.Vysíláme pouze diskrétní hodnoty (frekvence a amplitudy) a samotná sinusová vlna nemusí být přenášena - přijímací zařízení jej může generovat.Generuje sinusoidu a je na ni superponovánamodulace vytvořená z hodnot přenášených komunikačním kanálem. Existují přesné principy toho, které diskrétní hodnoty musí být přenášeny, aby se zvuk na vstupu do komunikačního kanálu shodoval se zvukem na výstupu, kde jsou tyto hodnoty superponovány na nějakou standardní sinusoidu (to je Kotelnikovova věta o).
Kotelnikovův teorém (v anglicky psané literatuře - Nyquist - Shannonova věta, věta o čtení)- zásadní prohlášení v oblasti digitáluzpracování signálu, propojení spojitých a diskrétních signálů a prohlášení, že „libovolnou funkci F(t), sestávající z frekvencí od 0 do f1, lze nepřetržitě přenášet s libovolnou přesností pomocí čísel následujících za sebou po dobu 1/(2*f1) sekund
Kódování proti rušení. Hammingovy kódy
Pokud je na nespolehlivém kanálu vysílatKódovaný text Ivana Turgeneva, i když s některými chybami, bude mít za následek poměrně smysluplný text. Pokud ale potřebujeme všechno přenést, úloha bude nevyřešena: nevíme, které bity jsou špatné, protože chyba je náhodná. Ani kontrolní součet neukládá vždy.
To je důvod, proč dnes při přenosu datsítě nemají tendenci k optimálnímu kódování, ve kterém může být do kanálu zasunuto maximální množství informací, ale spíše k takovému kódování (zjevně nadbytečnému), ve kterém mohou být chyby obnoveny - stejně jako když čteme slova ve fragmentu Ivana Turgeneva.
Existují speciální kódy oprav chyb, které umožňují obnovit informace po poruše. Jedním z nich je Hammingův kód.Řekněme, že celý náš jazyk se skládá ze tří slov:111000, 001110, 100011. Zdroj zprávy i příjemce tato slova znají. A víme, že v komunikačním kanálu dochází k chybám, ale při přenosu jednoho slova není zkresleno více než jeden bit informace.
Předpokládejme, že nejprve projdeme slovo 111000. Výsledkem je, že ne více než jedna chyba (identifikovali jsme chybu) se může změnit na jedno ze slov:
1) 111 000,011 000, 101000, 110000, 111100, 111010, 111001.
Při přenosu slova 001110 lze získat libovolné slovo:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Konečně za 100011 se můžeme dostat na recepci:
3) 100011,000011, 110011, 101011, 100111, 100001, 100010.
Všimněte si, že všechny tři seznamy nejsou párové.protínají se. Jinými slovy, pokud se na druhém konci komunikačního kanálu objeví jakékoli slovo ze seznamu 1, příjemce ví, že slovo 111000 mu bylo předáno, a pokud se objeví nějaké slovo ze seznamu 2, zobrazí se slovo 001110 a ze seznamu 3 slovo 100011. Říká se, že náš kód stanovil jednu chybu.
Ke korekci došlo kvůli dvěma faktorům.Za prvé, příjemce zná celý „slovník“, tj. prostor událostí příjemce zprávy se shoduje s prostorem toho, kdo zprávu odeslal. Když byl kód odeslán pouze s jednou chybou, vyšlo slovo, které nebylo ve slovníku.
Zadruhé, slova ve slovníku byla vybrána zvláštním způsobem.I když došlo k chybě, příjemce nemohlzaměňovat jedno slovo za druhé. Pokud se například slovník skládá ze slov „dcera“, „tečka“, „boule“ a během přenosu byl výsledkem „vochka“, pak by příjemce s vědomím, že takové slovo neexistuje, nemohl opravte chybu – kterékoli ze tří slov se může ukázat jako správné. Pokud slovník obsahuje „tečku“, „daw“, „větev“ a víme, že není povolena více než jedna chyba, pak je „vochka“ rozhodně „tečka“ a ne „daw“. V kódech pro opravu chyb jsou slova volena přesně tak, aby byla „rozpoznatelná“ i po chybě. Jediný rozdíl je v tom, že kód „abeceda“ má pouze dvě písmena - nulu a jednu.
Redundance takového kódování je velmi velká a počet slov, která můžeme takto přenášet, je poměrně malý.Musíme vyloučit jakékoli slovo ze slovníku,který se v případě chyby může shodovat s celým seznamem odpovídajícím přenášeným slovům (např. slova „dcera“ a „tečka“ nemohou být ve slovníku). Přesný přenos zpráv je však tak důležitý, že je vynaloženo velké úsilí na výzkum kódů odolných vůči chybám.
Vnímání
Pojmy entropie (nebo nejistota anepředvídatelnost) zprávy a redundance (nebo předurčení a předvídatelnost) velmi přirozeně odpovídají našim intuitivním představám o míře informací. Čím více je tato zpráva nepředvídatelná (tím větší je její entropie, protože je méně pravděpodobná), tím více informací přenáší. Pocit (například setkání s krokodýlem na Tverskaja) je vzácná událost, její předvídatelnost je velmi nízká, a proto je informační hodnota vysoká. Často se informace nazývají novinami - zprávami o událostech, ke kterým právě došlo, o kterých stále nic nevíme. Pokud nám však řeknou o druhém a třetím čase o stejných slovech, nadbytečnost zprávy bude velká, její nepředvídatelnost klesne na nulu a my prostě nebudeme poslouchat, mávat pryč od mluvčího se slovy "Já vím, já vím." Média se proto snaží tak těžké být první. Tato korespondence s intuitivním smyslem pro novost, která dává vzniknout neočekávaným novinkám, hrála významnou roli ve skutečnosti, že Shannonův článek, který nebyl určen pro čtenáře, se stal senzací, kterou tisk získal jako univerzální klíč k poznání přírody. - od lingvistů a literárních kritiků po biology.
AleShannon informační koncept - přísná matematická teoriea jeho aplikace mimo komunikační teorii je velmi nespolehlivá. Ale v teorii samotné komunikace hraje ústřední roli.
Sémantické informace
Shannon, zavádějící koncept entropie jako měřítkainformace, dostal možnost s informacemi pracovat - především je měřit a vyhodnocovat charakteristiky, jako je kapacita kanálu nebo optimální kódování. Ale hlavním předpokladem, který umožnil Shannonovi úspěšně pracovat s informacemi, byl předpoklad, že generování informace je náhodný proces, který lze úspěšně popsat z hlediska teorie pravděpodobnosti.Je-li proces ne náhodný, to znamená, že dodržuje zákony (navíc není vždy jasné, jak se to děje v přirozeném jazyce), pak se na něj Shannonova úvaha nevztahuje.Nic, co Shannon říká, nemá nic společného s tím, že informace jsou smysluplné.
Zatímco mluvíme o postavách (nebo písmenech abecedy),Můžeme se dobře dohadovat o náhodných událostech, ale jakmile se dostaneme ke slovům jazyka, situace se dramaticky změní. Řeč je proces, který je speciálně organizovaný, a zde je struktura zprávy neméně důležitá než postavy, kterými je přenášena.
Zrovna nedávno to vypadalo, že nemůžeme nic dělat.udělali, abychom se alespoň nějak přiblížili měření smysluplnosti textu, ale v posledních letech se situace začíná měnit. A to především díky aplikaci umělých neuronových sítí na úlohy strojového překladu, automatické sumarizace textů, extrahování informací z textů a generování zpráv v přirozeném jazyce. Všechny tyto úkoly zahrnují transformaci, kódování a dekódování smysluplných informací obsažených v přirozeném jazyce. A postupně se vytváří představa o informačních ztrátách při takových proměnách, a tedy o rozsahu smysluplných informací. Jasnost a přesnost, kterou má Shannonova informační teorie, však dnes v těchto obtížných problémech ještě není k dispozici.