Moderní teorie informace
Přihlásit se
Moderní teorie informace (5/8) · 4:02

Matematická teorie komunikace Claude Shannon ve svém slavném článku z roku 1948 demonstroval, jak generovat anglický text pomocí Markovovských řetězců. Tento systém potom dále využil k definování informačních zdrojů a "změření" informace. Originální článek najdete zde: http://www.mast.queensu.ca/~math474/shannon1948.pdf

Navazuje na Počátky teorie informace.
Shannon právě skončil vývoj teorií vztahujících se k šifrování a proto si byl dobře vědom, že lidská komunikace je směsí náhodnosti a statistických závislostí. Písmena v naších zprávách byla zjevně do určité míry závislá na předchozích písmenech. V roce 1949 publikoval přelomový článek "A Mathematical Theory of Communication". Využívá v něm Markovovy modely jako nástroj k pochopení komunikace. Začíná s ukázkovým příkladem. Představte si, že se setkáte s textem napsaným v abecedě písmen "A" "B" a "C". O tomto jazyce nic nevíte. Ale všimnete si, že se "áčka" drží spolu zatímco "béčka" a "céčka" ne. Pak ukázal, že můžete navrhnout stroj pro generování podobně vypadajícího textu použítím Markovova řetězce. Začal aproximací nultého řádu, kde jsme jen nezávisle vybrali každý symbol (A, B nebo C) náhodně a vytvořili řetězec. Tento řetězec ale nevypadá jako ten původní. Shannon ukázal, že lepší je aproximace 1. řádu, kde jsou písmena vybrána nezávisle, ale podle pravděpodobnosti s jakou se daná písmena v řetězci objevují. Tohle už je trochu lepší, protože "áčka" se objevují více, ale stále to nezachycuje strukturu. Další krok je klíčový. Aproximace druhého řádu, bere v potaz každý pár symbolů. V tomto případě máme 3 stavy. První stav představuje všechny páry začínající na "A", druhý páry začínající na "B" a třetí páry začínající na "C". Všimněte si, že kelímek s "A" má mnoho párů "AA", protože podmíněná pravděpodobnost "A" po "A" je v naší původní zprávě větší. Teď můžeme vytvářet sekvence pomocí modelu 2. řádu takto: Začneme kdekoli, vybereme kostičku a napíšeme první písmeno a posuneme se ke kelímku podle druhého písmena. Pak vybereme novou kostičku a tento proces opakujeme donekonečna. Tato posloupnost již začíná vypadat jako naše původní zpráva, protože tento model zahrnuje podmíněné závislosti mezi písmeny. Dalšího zlepšení dosáhneme pomocí aproximace 3. řádu, která zahrnuje skupiny 3 písmen - triagramy. V tomto případě potřebujeme 9 stavů. Shannon poté použil stejný postup na reálný anglický text a použil statistiku, která byla známa pro písmena, páry, triagramy atd. Ukázal to samé zlepšení pro přechody od aproximací 0. řádu, 1. řádu, 2. řádu a 3. řádu. Poté zkusil to samé pomocí slov místo písmen. Napsal: "Podobnost s běžným anglickým textem..." ...se velmi zvyšuje s každým řádem." A opravdu, tyto stroje produkovaly sice bezobsažný text, ale obsahovaly podobnou statistickou strukturu, kterou je možno vidět v angličtině. Shannon poté definoval kvantitativní míru informace, když si uvědomil, že množství informace ve zprávě musí souviset s návrhem stroje, který by mohl být použit ke generování podobných sekvencí. To nás přivádí ke konceptu entropie.
video