Ричард Хемминг: Глава 13. Теория на информацията

Направихме го!

«Целта на този курс е да ви подготви за вашето техническо бъдеще.»

Здравей, Хабр. Помните ли готината статия «Вие и вашата работа» (+219, 2588 в закладки, 429k прочитания)?

И така, при Хеминг (да, да, самоконтролиращи и самокоригиращи се кодове на Хеминг) има цяла книга, написана вдъхновена от неговите лекции. Ние я превеждаме, защото човекът знае за какво говори.

Тази книга не е просто за ИТ, тя е книга за начина на мислене на невероятно готини хора. «Това не е просто заряд на положителното мислене; в нея се описват условията, които увеличават шансовете за постигане на велико дело.»

Благодарности на Андрей Пахомов за превода.

Теорията на информацията е разработена от К. Е. Шенон в края на 40-те години. Ръководството на лабораториите Бел беше настоятелно, че трябва да я нарече „Теория на връзката“, тъй като това е много по-точно заглавие. По очевидни причини, заглавието „Теория на информацията“ има значително по-голямо въздействие върху публиката, така че Шенон избра именно него, и това е именованието, с което е познато до днес. Самото название предполага, че теорията се занимава с информация, и това я прави важна, тъй като все по-дълбоко навлизаме в информационната епоха. В тази глава ще разгледам няколко основни извода от тази теория, ще дам не стриктни, а по-скоро интуитивно разбираеми доказателства на някои от основните положения на теорията, за да разберете какво всъщност е „Теория на информацията“, къде можете да я прилагате и къде не.

Първо, какво е „информация“? Шенон отъждествява информацията с неопределеност. Той избра отрицателния логаритъм на вероятността на събитие като количествена мярка за информацията, която получавате при настъпването на събитие с вероятност p. Например, ако ви кажа, че в Лос Анджелис времето е мъгливо, то р е близо до 1, което в крайна сметка не ни дава много информация. Но ако кажа, че през юни в Монтерей вали дъжд, то в това съобщение има неопределеност и то ще съдържа повече информация. Достоверното събитие не съдържа никаква информация, тъй като log 1 = 0.

Нека да се спрем на това по-подробно. Шеннон смяташе, че количествената мярка на информацията трябва да бъде непрекъсната функция от вероятността на събитие p, а за независими събития тя трябва да бъде адитивна - количеството информация, получена в следствие на извършването на две независими събития, трябва да бъде равно на количеството информация, получено в следствие на извършването на съвместно събитие. Например, резултатът от хвърлянето на зарче и монета обикновено се разглеждат като независими събития. Нека да преведем горепосоченото на математически език. Ако I (p) е количеството информация, което присъства в събитие с вероятност p, то за съвместно събитие, състоящо се от две независими събития x с вероятност p1 и y с вероятност p2 получаваме

(x и y независими събития)

Това е функционално уравнение на Коши, вярно за всички p1 и p2. За решаване на това функционално уравнение предполагаме, че

p1 = p2 = p,

това дава

Ако p1 = p2 и p2 = p, тогава

и т.н. Разширявайки този процес, използвайки стандартния метод за експоненти, за всички рационални числа m / n, следва, че

От предполагаемата непрекъснатост на информационната мярка следва, че логаритмичната функция е единственото непрекъснато решение на функционалното уравнение на Коши.

В теорията на информацията е прието основанието на логаритъма да бъде равно на 2, така че бинарният избор съдържа точно 1 бит информация. Следователно информацията се измерва по формулата

Нека да се спрем и да разберем какво се случи по-горе. Първо, така и не определихме понятието “информация”, просто определихме формулата за количествената й мярка.

На второ място, тази мярка зависи от неопределеността и, макар че е достатъчно подходяща за машини — например телефонни системи, радио, телевизия, компютри и т.н. — тя не отразява нормалното човешко отношение към информацията.

На трето място, това е относителна мярка, която зависи от текущото състояние на вашите знания. Ако гледате на поток от “случайни числа” от генератор на случайни числа, вие предполагате, че всяко следващо число е неопределено, но ако знаете формулата за изчисляване на “случайните числа”, следващото число ще бъде известно и съответно няма да съдържа информация.

По този начин, определението, дадено от Шенън за информация, в много случаи е приложимо за машините, но изглежда не съответства на човешкото разбиране на тази дума. Именно поради тази причина „Теория на информацията“ би следвало да се нарича „Теория на комуникацията“. Въпреки това, вече е твърде късно да променим определенията (благодарение на които теорията придоби първоначалната си популярност и които все още карат хората да вярват, че тази теория се занимава с „информация“), затова сме принудени да се примирим с тях, но в същото време трябва ясно да разбирате колко далеч е определението за информация, дадено от Шенън, от общественото му значение. Информацията на Шенън се занимава с нещо съвсем различно, а именно с неопределеност.

Ето за какво трябва да помислите, когато предлагате терминология. До каква степен предложеното определение, като например определението за информация, дадено от Шенън, съответства на вашата първоначална идея и колко се различава? Почти няма термин, който точно да отразява вашето предишно виждане на концепцията, но в крайна сметка именно използваната терминология отразява смисъла на концепцията, затова формализирането на нещо посредством ясни определения винаги внася известен шум.

Нека разгледаме система, чийто азбука се състои от символи q с вероятности pi. В този случай средното количество информация в системата (нейната очаквана стойност) е равно на:

Това се нарича ентропия на системата с разпределение на вероятността {pi}. Използваме термина „ентропия“, защото същата математическа форма се появява в термодинамиката и статистическата механика. Именно поради това терминът „ентропия“ създава около себе си определена аура на важност, която в крайна сметка не е оправдана. Същата математическа форма на записа не предполага еднаква интерпретация на символите!

Ентропията на разпределението на вероятността играе основна роля в теорията на кодирането. Несправедливостта на Гибс за две различни разпределения на вероятността pi и qi е едно от важните следствия на тази теория. Следователно, трябва да докажем, че

Доказателството се основава на очевидната графика, рис. 13.I, която показва, че

равенството се постига само при x = 1. Да приложим неравенството към всеки член на сумата в лявата част:

Ако азбуката на комуникационната система се състои от q символа, приемайки вероятността за предаване на всеки символ qi = 1/q и заместим q, получаваме от неравенството на Гибс.

Фигура 13.I

Това означава, че ако вероятността за предаване на всички q символа е еднаква и равна на 1/q, то максималната ентропия е ln q, в противен случай неравенството е валидно.

В случая на еднозначно декодируем код, имаме неравенството на Крафт.

Сега, ако определим псевдовероятности

където е крайно = 1, което следва от неравенството на Гибс,

и приложим малко алгебра (помнете, че K ≤ 1, следователно можем да пропуснем логаритмичния член и евентуално да усилваме неравенството по-късно), то получаваме

където L е средната дължина на кода.

Следователно, ентропията е минималната граница за всеки символьен код със средна дължина на кода L. Това е теоремата на Шенън за канала без шум.

Сега да разгледаме основната теорема за ограниченията на комуникационните системи, в които информацията се предава под формата на поток от независими битове и присъства шум. Предполага се, че вероятността за коректно предаване на един бит P > 1/2, а вероятността стойността на бита да бъде инвертирана при предаване (да се случи грешка) е равна на Q = 1 - P. За удобство, предполагаме, че грешките са независими и вероятността за грешка е еднаква за всеки изпратен бит, т.е. в комуникационния канал присъства „бял шум“.

Имаме дълъг поток от n бита, кодирани в едно съобщение - n-измерно разширение на еднобитовия код. Стойността на n ще определим по-късно. Нека разгледаме съобщение, състоящо се от n бита, като точка в n-измерно пространство. Тъй като имаме n-измерно пространство - и за опростяване да предположим, че всяко съобщение има еднаква вероятност за настъпване - съществуват M възможни съобщения (M също ще бъде определено по-късно), следователно, вероятността за всяко изпратено съобщение е равна на

(изпращач)
Графика 13.II

Нека разгледаме идеята за пропускната способност на канала. Без да навлизаме в детайли, пропускната способност на канала се определя като максималния обем информация, който може да бъде надеждно предаден през комуникационния канал, като се вземе предвид използването на максимално ефективно кодиране. Няма доказателства, че през комуникационния канал може да бъде предадено повече информация, отколкото е неговата капацитет. Това може да бъде доказано за бинарния симетричен канал (който използваме в нашия случай). Капацитетът на канала при битово предаване се задава като

където, както и преди, P — вероятността за отсъствие на грешка в който и да е изпратен бит. При изпращане на n независими бита капацитетът на канала се определя като

Ако сме близо до пропускната способност на канала, трябва да изпратим почти толкова информация за всеки от символите ai, i = 1, …, М. С оглед на това, че вероятността за възникване на всеки символ ai е равна на 1 / M, получаваме

когато изпращаме някое от М равновероятни съобщения ai, имаме

При изпращане на n бита очакваме възникването на nQ грешки. На практика, за съобщение, състоящо се от n бита, ще имаме приблизително nQ грешки в полученото съобщение. При големи n относителната вариация (вариацията = ширината на разпределението,)
разпределението на броя на грешките ще бъде все по-тясно с увеличаване на n.

И така, от страна на предавателя, вземам съобщение ai за изпращане и рисувам сфера около него с радиус

който е малко по-голям от величината равна на e2, от очаквания брой грешки Q, (фигура 13.II). Ако n е достатъчно голямо, то съществува произволно малка вероятност точката на съобщението bj от страна на приемника да излезе извън пределите на тази сфера. Нека нарисувам ситуацията, как я виждам аз от страна на предавателя: имаме произволни радиуси от предаденото съобщение ai до полученото съобщение bj с вероятност на грешка равна (или почти равна) на нормално разпределение, достигащо максимум в nQ. За произволно зададено e2 съществува n толкова голямо, че вероятността получената точка bj да излезе извън пределите на моята сфера да бъде толкова малка, колкото желаете.

Сега нека разгледаме същата ситуация от ваша страна (рис. 13.III). От страна на приемника има сфера S( r) с радиус r около приетата точка bj в n-мерно пространство, така че ако приетото съобщение bj се намира вътре в моята сфера, тогава изпратеното от мен съобщение ai е вътре във вашата сфера.

Как може да възникне грешка? Грешка може да се появи в случаите, описани в таблицата по-долу:

Рисунок 13.III

Тук виждаме, че ако в сферата, построена около приетата точка, съществува поне още една точка, съответстваща на възможно изпратено не закодирано съобщение, то при предаване е възникнала грешка, тъй като не можете да определите кое точно от тези съобщения е било изпратено. Изпратеното съобщение не съдържа грешка, само ако точката, която му отговаря, е в сферата, и не съществуват други точки, възможни в дадения код, които също се намират в същата сфера.

Имаме математично уравнение за вероятността на грешка Ре, ако е изпратено съобщение ai.

Можем да изключим първия множител от втория член, приемайки го за 1. По този начин получаваме неравенството

Очевидно е, че

следователно

отново прилагаме към последния член вдясно

Приемайки n като достатъчно голямо, първият член може да бъде приет за произволно малък, да речем по-малък от някакво число d. Следователно имаме

Сега нека разгледаме как може да се изгради код за проста замяна за кодиране на M съобщения, състоящи се от n бита. Нямайки представа за това как точно да се изгражда код (кодове за корекция на грешки все още не са били изобретени), Шенън избра случайно кодиране. Изхвърлете монета за всеки от n битовете в съобщението и повторете процеса за М съобщения. Общо трябва да се направят nM хвърляния на монета, така че са възможни

кодови словарници, имат еднаква вероятност ½nM. Разбира се, случаен процес на създаване на кодов речник означава, че съществува вероятност за поява на дубликати, както и кодови точки, които ще бъдат близки една до друга и следователно ще бъдат източник на вероятни грешки. Необходимо е да се докаже, че ако това не се случва с вероятност по-висока от всяко малко избрано ниво на грешка, то зададеното n е достатъчно голямо.
Ключовият момент е, че Шенън е усреднил всички възможни кодови книги, за да намери средната грешка! Ще използваме символа Av [.], за да обозначим средното значение по множество от всички възможни случайни кодови речници. Усредняването по константа d, разбира се, дава константа, тъй като при усредняването всеки член съвпада с всеки друг член в сумата,

който може да бъде увеличен (M–1 преминава в M )

За всяко конкретно съобщение, при усредняване на всички кодови книги, кодиране преминава през всички възможни стойности, така че средната вероятност точката да бъде в сферата е отношението на обема на сферата към общия обем на пространството. Обемът на сферата при това

където s=Q+e2 <1/2 и ns трябва да бъде цяло число.

Последният член вдясно е най-голям в тази сума. Първо ще оценим стойността му по формулата на Стърлинг за факториели. След това ще разгледаме коефициента на намаление на предишния член, обърнете внимание, че този коефициент нараства при преминаване наляво, и затова можем: (1) да ограничим стойността на сумата с геометрична прогресия с този начален коефициент, (2) да разширим геометричната прогресия с ns членове до безкрайно число членове, (3) да изчислим сумата на безкрайната геометрична прогресия (стандартна алгебра, нищо съществено) и накрая да получим пределната стойност (за достатъчно голямо n):

Обърнете внимание, как ентропията H(s) се е появила в биномиалната идентичност. Забележете, че разлагането в ред на Тейлър H(s)=H(Q+e2) дава оценка, получена, като се вземе само първата производна и се игнорират всички останали. Сега да съберем крайното изражение:

където

Всичко, което трябва да направим, е да изберем e2, така че e3 < e1, и тогава последният член ще бъде колкото искате малък, при достатъчно голямо n. Следователно, средната грешка PE може да бъде направена колкото искате малка при пропускателна способност на канала, колкото искате близка до C.
Ако средното значение за всички кодове има достатъчно малка грешка, то поне един код трябва да бъде подходящ, следователно съществува поне една подходяща система за кодиране. Това е важен резултат, получен от Шенън — "теорема на Шенън за канала с шум", но следва да се отбележи, че той е доказал това за много по-общ случай, отколкото за прост двоичен симетричен канал, използван от мен. За общия случай математическите изчисления са много по-сложни, но идеите не са толкова различни, затова много често, като се гледа частният случай, можем да разкрием истинския смисъл на теоремата.

Нека критикуваме резултата. Ние многократно повтаряхме: "При достатъчно големи n". Но колко голямо е n? Много, много голямо, ако наистина искате да бъдете едновременно близки до капацитета на канала и да сте сигурни в коректната предаване на данни! Толкова голямо, че всъщност ще трябва да чакате много дълго, за да натрупате съобщение от такова количество битове, за да го кодиране по-късно. При това размерът на речника на случайния код ще бъде просто огромен (все пак такъв речник не може да бъде представен в по-кратка форма от пълния списък на всички Mn битове, при условие че n и M са много големи)!

Кодовете за корекция на грешки избягват чакането на много дълго съобщение, с последващото му кодиране и декодиране през много големи кодови книги, защото избягват самите кодови книги и използват вместо тях обикновени изчисления. В проста теория такива кодове обикновено губят способността си да се доближат до капацитета на канала и наред с това да поддържат достатъчно ниска честота на грешки, но когато кодът коригира голямо количество грешки, те показват добри резултати. С други думи, ако предвидите някаква капацитет на канала за корекция на грешки, то трябва да използвате възможността за корекция на грешки по-голямата част от времето, т.е. в всяко изпратено съобщение трябва да са коригирани много грешки, иначе губите тази капацитет напразно.

В същото време, доказаната по-горе теорема все пак не е безсмислена! Тя показва, че ефективните системи за предаване трябва да използват добре обмислени схеми за кодиране на много дълги битови низове. Пример за това са спътниците, които са напуснали пределите на външната планета; с отдалечаването си от Земята и Слънцето, те са принудени да поправят все по-голямо количество грешки в блока данни: някои спътници използват слънчеви батерии, които дават около 5 W, други използват атомни източници на енергия, които осигуряват приблизително същата мощност. Слабата мощност на източника на енергия, малките размери на предавателните антени и ограничените размери на приемниците на Земята, огромното разстояние, което сигналът трябва да преодолее – всичко това изисква използването на кодове с високо ниво на корекция на грешки за изграждането на ефективна комуникационна система.

Нека се върнем към n-измерното пространство, което използвахме в доказателството по-горе. Обсъждайки го, показахме, че почти целият обем на сферата е съсредоточен около външната повърхност, – така че, почти със сигурност, изпратеният сигнал ще бъде разположен на повърхността на сферата, изградена около приетия сигнал, дори при относително малък радиус на такава сфера. Затова не е изненада, че приетият сигнал след корекция на произволно голямо количество грешки, nQ, е колкото се може по-близо до сигнала без грешки. Капацитетът на комуникационния канал, който разгледахме по-рано, е ключът към разбирането на това явление. Обърнете внимание, че подобни сфери, построени за кодовете на Хеминг с корекция на грешки, не се припокриват. Голямото количество практически ортогонални измерения в n-измерното пространство показва, защо можем да вместим M сфери в пространството с малко припокриване. Ако допуснем малко, произволно малко припокриване, което може да доведе само до малко количество грешки при декодиране, може да се постигне плътно разположение на сферите в пространството. Хеминг е гарантирал определено ниво на корекция на грешки, Шенън – ниска вероятност за грешка, но при това запазвайки действителната пропускна способност колкото се може по-близо до капацитета на комуникационния канал, което кодовете на Хеминг не могат да направят.

Теорията на информацията не говори за това как да проектираме ефективна система, но посочва посоката на движение към ефективни комуникационни системи. Това е ценен инструмент за изграждане на комуникационни системи между машини, но, както беше отбелязано по-рано, тя не има особено отношение към начина, по който хората обменят информация помежду си. Степента, в която биологичното наследство е подобно на техническите комуникационни системи, просто не е известна, така че в момента не е ясно доколко теорията на информацията е приложима към гените. Нямаме нищо друго, освен да опитаме, и ако успехът ни покаже машиноподобния характер на това явление, то неуспехът ще посочи на други съществени аспекти на природата на информацията.

Нека не се отклоняваме много. Видяхме, че всички първоначални определения, в по-голяма или по-малка степен, трябва да изразяват същността на нашите основни убеждения, но те са място на определена степен изкривяване, и затова се оказват неприложими. Традиционно се приема, че в крайна сметка определението, което използваме, всъщност определя същността; но това само ни указва как да обработваме нещата и по никакъв начин не носи смисъл за нас. Постулационният подход, толкова силно одобрен в математическите среди, оставя много да се желае на практика.

Сега ще разгледаме пример за IQ тестове, при които определението е толкова циклично, колкото желаете, и в резултат на това ви подвежда. Създава се тест, който предполага да измери интелекта. След това той е преразгледан, за да бъде направен максимално последователен, и след това е публикуван и е калибриран по прост метод така, че измерваният "интелект" да се окаже нормално разпределен (разбира се, по крива на калибриране). Всички определения трябва да бъдат преразгледани не само когато са предложени за първи път, но и много по-късно, когато се използват в направените заключения. В каква степен границите на определенията са подходящи за решаваната задача? Колко често определения, дадени в едни условия, започват да се прилагат в достатъчно различаващи се условия? Такова нещо се случва достатъчно често! В хуманитарните науки, с които неизбежно ще се сблъскате в живота си, това се случва по-често.

Така че, една от целите на тази презентация на теорията за информацията, освен да демонстрира нейната полезност, беше да ви предупреди за тази опасност или да демонстрира как точно да я използвате, за да постигнете желаните резултати. Отдавна е забелязано, че първоначалните определения определят какво намирате в крайна сметка в много по-голяма степен, отколкото изглежда. Първоначалните определения изискват от вас голямо внимание не само във всяка нова ситуация, но и в области, с които отдавна работите. Това ще ви позволи да разберете в каква степен получените резултати са тавтология, а не нещо полезно.

Известната история за Еддингтън разказва за хора, които ловят риба в морето с мрежа. Изучавайки размера на рибите, които са уловили, те определили минималния размер на рибите, които се срещат в морето! Техният извод бил обусловен от използвания инструмент, а не от действителността.

Продължението следва…

Който иска да помогне с превода, оформлението и издаването на книгата — пишете на лични съобщения или на имейл magisterludi2016@yandex.ru

Между другото, ние основахме превода на още една страхотна книга — «The Dream Machine: История на компютърната революция»)

Особено търсим тези, които могат да помогнат с превода на бонусна глава, която има само на видео. (превеждаме по 10 минути, първите 20 вече са взети)

Съдържание на книгата и преведените главиПредговор

1. Въведение в изкуството на науката и инженерството: Учене да се учиш (28 март 1995) Превод: Глава 1
2. «Основи на цифровата (дискретна) революция» (30 март 1995) Глава 2. Основи на цифровата (дискретна) революция
3. «История на компютрите — Хардуер» (31 март 1995) Глава 3. История на компютрите — железо
4. «История на компютрите — Софтуер» (4 април 1995) Глава 4. История на компютрите — Софт
5. «История на компютрите — Приложения» (6 април 1995) Глава 5. История на компютрите — практическо приложение
6. «Изкуствен интелект — Част I» (7 април 1995) Глава 6. Изкуствен интелект — 1
7. «Изкуствен интелект — Част II» (11 април 1995) Глава 7. Изкуствен интелект — II
8. «Изкуствен интелект III» (13 април 1995) Глава 8. Изкуствен интелект — III
9. «n-измерно пространство» (14 април 1995) Глава 9. N-мерно пространство
10. «Теория на кодиране — Представяне на информация, Част I» (18 април 1995) Глава 10. Теория на кодиране — I
11. «Теория на кодиране — Представяне на информация, Част II» (20 април 1995) Глава 11. Теория на кодиране — II
12. «Кодове за корекция на грешки» (21 април 1995) Глава 12. Кодове с корекция на грешки
13. «Теория на информацията» (25 април 1995) Глава 13. Теория на информацията
14. «Цифрови филтри, Част I» (27 април 1995) Глава 14. Цифрови филтри — 1
15. «Цифрови филтри, Част II» (28 април 1995) Глава 15. Цифрови филтри — 2
16. «Цифрови филтри, Част III» (2 май 1995) Глава 16. Цифрови филтри — 3
17. «Цифрови филтри, Част IV» (4 май 1995) Глава 17. Цифрови филтри — IV
18. «Моделиране, Част I» (5 май 1995) Глава 18. Моделиране — I
19. «Моделиране, Част II» (9 май 1995) Глава 19. Моделиране — II
20. «Моделиране, Част III» (11 май 1995) Глава 20. Моделиране — III
21. «Оптика на влакна» (12 май 1995) Глава 21. Волоконна оптика
22. «Компютърно подпомагано обучение» (16 май 1995) Глава 22. Обучение с помощта на компютър (CAI)
23. «Математика» (18 май 1995) Глава 23. Математика
24. «Квантова механика» (19 май 1995) Глава 24. Квантова механика
25. «Креативност» (23 май 1995). Превод: Глава 25. Креативност
26. «Експерти» (25 май 1995) Глава 26. Експерти
27. «Недостоверни данни» (26 май 1995) Глава 27. Недостоверни данни
28. «Системно инженерство» (30 май 1995) Глава 28. Системно инженерство
29. «Каквото измериш, това получаваш» (1 юни 1995) Глава 29. Получавате това, което измервате
30. «Как знаем какво знаем» (2 юни 1995) превеждаме на парчета по 10 минути
31. Хаминг, «Вие и вашето изследване» (6 юни 1995). Превод: Вие и вашата работа

Който иска да помогне с превода, оформлението и издаването на книгата — пишете на лични съобщения или на имейл magisterludi2016@yandex.ru

Източник: habr.com