Успяхме!
„Целта на този курс е да ви подготви за вашето техническо бъдеще.“
Здравей, Хабр. Спомнете си страхотната статия (+219, 2588 отметки, 429k прочитания)?
Така че Хеминг (да, да, самонаблюдение и самокоригиране ) има едно цяло , написана въз основа на неговите лекции. Превеждаме го, защото човекът си казва мнението.
Това е книга не само за ИТ, това е книга за стила на мислене на невероятно готини хора. „Това не е просто тласък на позитивното мислене; той описва условията, които увеличават шансовете за извършване на страхотна работа.“
Благодаря на Андрей Пахомов за превода.
Информационната теория е разработена от C. E. Shannon в края на 1940-те години. Ръководството на Bell Labs настоя да го нарече „Теория на комуникацията“, защото... това е много по-точно име. По очевидни причини името "Теория на информацията" има много по-голямо въздействие върху обществеността, поради което Шанън го избира и това е името, което познаваме и до днес. Самото име подсказва, че теорията се занимава с информация, което я прави важна, докато навлизаме все по-дълбоко в информационната ера. В тази глава ще засегна няколко основни извода от тази теория, ще предоставя не строги, а по-скоро интуитивни доказателства за някои отделни положения на тази теория, така че да разберете какво всъщност е „Теория на информацията“, къде можете да я приложите а къде не.
Първо, какво е „информация“? Шанън приравнява информацията с несигурността. Той избра отрицателния логаритъм от вероятността за събитие като количествена мярка за информацията, която получавате, когато се случи събитие с вероятност p. Например, ако ви кажа, че времето в Лос Анджелис е мъгливо, тогава 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, ..., M. Като се има предвид, че вероятността за поява на всеки символ ai е 1 / M, получаваме
когато изпратим някое от 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
Тук виждаме, че ако в сферата, изградена около получената точка, има поне още една точка, съответстваща на възможно изпратено некодирано съобщение, тогава е възникнала грешка по време на предаването, тъй като не можете да определите кое от тези съобщения е било предадено. Изпратеното съобщение е без грешки само ако съответстващата му точка е в сферата и не са възможни други точки в дадения код, които да са в същата сфера.
Имаме математическо уравнение за вероятността за грешка Pe, ако съобщение ai е изпратено
Можем да изхвърлим първия фактор във втория член, като го приемем за 1. Така получаваме неравенството
Очевидно е, че
следователно
приложете отново към последния член вдясно
Вземайки n достатъчно голямо, първият член може да бъде взет колкото желаете малък, да речем по-малък от някакво число d. Следователно имаме
Сега нека да разгледаме как можем да конструираме прост заместващ код за кодиране на M съобщения, състоящи се от n бита. Без никаква представа как точно да се конструира код (кодовете за коригиране на грешки все още не са били изобретени), Шанън избира произволно кодиране. Хвърлете монета за всеки от n бита в съобщението и повторете процеса за M съобщения. Общо трябва да се направят nM хвърляния на монети, така че е възможно
кодови речници със същата вероятност ½nM. Разбира се, произволният процес на създаване на кодова книга означава, че има възможност за дубликати, както и кодови точки, които ще бъдат близо една до друга и следователно ще бъдат източник на вероятни грешки. Трябва да се докаже, че ако това не се случи с вероятност, по-голяма от всяко малко избрано ниво на грешка, тогава даденото n е достатъчно голямо.
Решаващият момент е, че Шанън осредни всички възможни кодови книги, за да намери средната грешка! Ще използваме символа Av[.], за да обозначим средната стойност за множеството от всички възможни произволни кодови книги. Осредняването върху константа d, разбира се, дава константа, тъй като за осредняването всеки член е същият като всеки друг член в сумата,
което може да се увеличи (M–1 отива към M)
За всяко дадено съобщение, когато се осреднява за всички кодови книги, кодирането преминава през всички възможни стойности, така че средната вероятност дадена точка да е в сфера е съотношението на обема на сферата към общия обем на пространството. Обемът на сферата е
където s=Q+e2 <1/2 и ns трябва да е цяло число.
Последният член вдясно е най-големият в тази сума. Първо, нека оценим стойността му, използвайки формулата на Стърлинг за факториели. След това ще разгледаме намаляващия коефициент на члена пред него, отбележете, че този коефициент се увеличава, докато се движим наляво, и така можем: (1) да ограничим стойността на сумата до сумата от геометричната прогресия с този начален коефициент, (2) разширете геометричната прогресия от ns членове до безкраен брой членове, (3) изчислете сумата от безкрайна геометрична прогресия (стандартна алгебра, нищо значимо) и накрая получете граничната стойност (за достатъчно голям н):
Забележете как ентропията H(s) се появи в биномната идентичност. Обърнете внимание, че разширението на реда на Тейлър H(s)=H(Q+e2) дава оценка, получена като се вземе предвид само първата производна и се игнорират всички останали. Сега нека съставим крайния израз:
където
Всичко, което трябва да направим, е да изберем e2 така, че e3 < e1, и тогава последният член ще бъде произволно малък, стига n да е достатъчно голямо. Следователно, средната PE грешка може да бъде получена толкова малка, колкото желаете, с капацитет на канала произволно близък до C.
Ако средната стойност на всички кодове има достатъчно малка грешка, тогава поне един код трябва да е подходящ, следователно има поне една подходяща система за кодиране. Това е важен резултат, получен от Шанън - "теорема на Шанън за канал с шум", въпреки че трябва да се отбележи, че той доказа това за много по-общ случай, отколкото за простия двоичен симетричен канал, който използвах. За общия случай математическите изчисления са много по-сложни, но идеите не са толкова различни, така че много често, като използвате примера на конкретен случай, можете да разкриете истинското значение на теоремата.
Нека да критикуваме резултата. Многократно сме повтаряли: „За достатъчно голямо n.“ Но колко голямо е n? Много, много голям, ако наистина искате да сте близо до капацитета на канала и да сте сигурни в правилния трансфер на данни! Толкова голям всъщност, че ще трябва да чакате много дълго време, за да натрупате съобщение от достатъчно битове, за да го кодирате по-късно. В този случай размерът на произволния кодов речник ще бъде просто огромен (в края на краищата такъв речник не може да бъде представен в по-кратка форма от пълен списък на всички Mn битове, въпреки факта, че n и M са много големи)!
Кодовете за коригиране на грешки избягват да чакат много дълго съобщение и след това да го кодират и декодират чрез много големи кодови книги, защото избягват самите кодови книги и вместо това използват обикновено изчисление. На проста теория, такива кодове са склонни да губят способността да се доближават до капацитета на канала и все още да поддържат нисък процент грешки, но когато кодът коригира голям брой грешки, те се представят добре. С други думи, ако разпределите някакъв капацитет на канала за коригиране на грешки, тогава трябва да използвате способността за коригиране на грешки през повечето време, т.е. голям брой грешки трябва да бъдат коригирани във всяко изпратено съобщение, в противен случай губите този капацитет.
В същото време доказаната по-горе теорема все още не е безсмислена! Това показва, че ефективните системи за предаване трябва да използват интелигентни схеми за кодиране за много дълги низове от битове. Пример са спътници, които са прелетели отвъд външните планети; Докато се отдалечават от Земята и Слънцето, те са принудени да коригират все повече и повече грешки в блока с данни: някои спътници използват слънчеви панели, които осигуряват около 5 W, други използват ядрени източници на енергия, които осигуряват приблизително същата мощност. Ниската мощност на захранването, малкият размер на предавателните антени и ограниченият размер на приемните антени на Земята, огромното разстояние, което сигналът трябва да измине - всичко това изисква използването на кодове с високо ниво на корекция на грешки за изграждане на ефективна комуникационна система.
Нека се върнем към n-мерното пространство, което използвахме в горното доказателство. При обсъждането му показахме, че почти целият обем на сферата е концентриран близо до външната повърхност - по този начин е почти сигурно, че изпратеният сигнал ще бъде разположен близо до повърхността на сферата, изградена около получения сигнал, дори и с относително малък радиус на такава сфера. Следователно не е изненадващо, че полученият сигнал, след коригиране на произволно голям брой грешки, nQ, се оказва произволно близък до сигнал без грешки. Капацитетът на връзката, който обсъдихме по-рано, е ключът към разбирането на този феномен. Обърнете внимание, че подобни сфери, конструирани за кодове на Хеминг за коригиране на грешки, не се припокриват една с друга. Големият брой почти ортогонални измерения в n-измерното пространство показва защо можем да поставим M сфери в пространството с малко припокриване. Ако позволим малко, произволно малко припокриване, което може да доведе само до малък брой грешки по време на декодиране, можем да получим плътно разположение на сферите в пространството. Hamming гарантира определено ниво на коригиране на грешки, Shannon - ниска вероятност за грешка, но в същото време поддържа действителната пропускателна способност произволно близо до капацитета на комуникационния канал, което кодовете на Hamming не могат да направят.
Теорията на информацията не ни казва как да проектираме ефективна система, но посочва пътя към ефективните комуникационни системи. Това е ценен инструмент за изграждане на комуникационни системи машина-машина, но, както беше отбелязано по-рано, има малко значение за това как хората комуникират помежду си. Степента, до която биологичното наследство е като технически комуникационни системи, е просто неизвестна, така че в момента не е ясно как теорията на информацията се прилага към гените. Нямаме друг избор, освен да опитаме и ако успехът ни покаже машиноподобния характер на този феномен, тогава неуспехът ще посочи други важни аспекти от природата на информацията.
Нека не се отклоняваме твърде много. Видяхме, че всички оригинални дефиниции, в по-голяма или по-малка степен, трябва да изразяват същността на нашите първоначални вярвания, но те се характеризират с известна степен на изкривяване и следователно не са приложими. Традиционно се приема, че в крайна сметка определението, което използваме, всъщност определя същността; но това само ни казва как да обработваме нещата и по никакъв начин не ни предава никакво значение. Постулационният подход, толкова силно предпочитан в математическите среди, оставя много да се желае на практика.
Сега ще разгледаме пример за тестове за интелигентност, където дефиницията е толкова кръгова, колкото желаете, и в резултат на това е подвеждаща. Създава се тест, който трябва да измерва интелигентността. След това се преработва, за да стане възможно най-последователен, след което се публикува и, по прост метод, се калибрира, така че измерената „интелигентност“ да се окаже нормално разпределена (на калибрационна крива, разбира се). Всички определения трябва да бъдат проверени отново, не само когато са предложени за първи път, но и много по-късно, когато се използват в направените заключения. До каква степен дефиниционните граници са подходящи за решавания проблем? Колко често определенията, дадени в една среда, се прилагат в съвсем различни настройки? Това се случва доста често! В хуманитарните науки, които неизбежно ще срещнете в живота си, това се случва по-често.
По този начин, една от целите на това представяне на теорията на информацията, в допълнение към демонстрирането на нейната полезност, беше да ви предупреди за тази опасност или да ви покаже как точно да я използвате, за да получите желания резултат. Отдавна е отбелязано, че първоначалните дефиниции определят това, което ще намерите в крайна сметка, в много по-голяма степен, отколкото изглежда. Първоначалните определения изискват много внимание от вас, не само във всяка нова ситуация, но и в области, с които работите от дълго време. Това ще ви позволи да разберете до каква степен получените резултати са тавтология, а не нещо полезно.
Известната история на Едингтън разказва за хора, които ловили риба в морето с мрежа. След като проучиха размера на уловената риба, те определиха минималния размер на рибата, която се намира в морето! Тяхното заключение е водено от използвания инструмент, а не от реалността.
За да се продължи ...
Който желае да помогне с превода, оформлението и издаването на книгата - пишете на лично съобщение или имейл [имейл защитен]
Между другото, стартирахме и превода на друга готина книга - )
Особено търсим тези, които ще помогнат за превода , (трансфер за 10 минути, първите 20 вече са взети)
Съдържание на книгата и преведени глави
- Въведение в изкуството да правиш наука и инженерство: Да се научиш да учиш (28 март 1995 г.)
- „Основи на цифровата (дискретна) революция“ (30 март 1995 г.)
- „История на компютрите – хардуер“ (31 март 1995 г.)
- „История на компютрите – софтуер“ (4 април 1995 г.)
- „История на компютрите – приложения“ (6 април 1995 г.)
- „Изкуствен интелект – част I“ (7 април 1995 г.)
- „Изкуствен интелект – част II“ (11 април 1995 г.)
- „Изкуствен интелект III“ (13 април 1995 г.)
- "n-Dimensional Space" (14 април 1995 г.)
- „Теория на кодирането – Представяне на информация, част I“ (18 април 1995 г.)
- „Теория на кодирането – Представяне на информация, част II“ (20 април 1995 г.)
- „Кодове за коригиране на грешки“ (21 април 1995 г.)
- "Теория на информацията" (25 април 1995 г.)
- „Цифрови филтри, част I“ (27 април 1995 г.)
- "Цифрови филтри, част II" (28 април 1995 г.)
- „Цифрови филтри, част III“ (2 май 1995 г.)
- „Цифрови филтри, част IV“ (4 май 1995 г.)
- „Симулация, част I“ (5 май 1995 г.)
- „Симулация, част II“ (9 май 1995 г.)
- „Симулация, част III“ (11 май 1995 г.)
- "Fiber Optics" (12 май 1995 г.)
- „Компютърно обучение“ (16 май 1995 г.)
- "Математика" (18 май 1995 г.)
- "Квантова механика" (19 май 1995 г.)
- "Творчество" (23 май 1995 г.). Превод:
- "Експерти" (25 май 1995 г.)
- „Ненадеждни данни“ (26 май 1995 г.)
- "Системно инженерство" (30 май 1995 г.)
- „Вие получавате това, което измервате“ (1 юни 1995 г.)
- (Юни 2, 1995) превеждайте на 10-минутни парчета
- Хеминг, „Вие и вашите изследвания“ (6 юни 1995 г.).
Който желае да помогне с превода, оформлението и издаването на книгата - пишете на лично съобщение или имейл [имейл защитен]
Източник: www.habr.com