Ми це зробили!
"Мета цього курсу - підготувати вас до вашого технічного майбутнього."
Привіт Хабр. Пам'ятайте офігенну статтю (+219, 2588 в закладки, 429k прочитань)?
Так от у Хеммінга (так, так, що самоконтролюються і самокоректуються ) є ціла написана за мотивами його лекцій. Ми її перекладаємо, адже мужик каже.
Це книга не просто про ІТ, це книга про стиль мислення неймовірно крутих людей. Це не просто заряд позитивного мислення; в ній описані умови, які збільшують шанси зробити велику роботу.
За переклад дякую Андрію Пахомову.
Теорія інформації була розроблена К. Е. Шенноном наприкінці 1940-х років. Керівництво Лабораторій Белла наполягало, що він назвав її «Теорія Зв'язку», т.к. це набагато точніша назва. З очевидних причин, назва «Теорія Інформації» має значно більший вплив на публіку, тому Шеннон вибрав саме її, і саме вона відома нам донині. Сама назва передбачає, що теорія має справу з інформацією, це і робить її важливою, оскільки ми все глибше проникаємо в інформаційну епоху. У цьому розділі я торкнуся кількох основних висновків з цієї теорії, наведу не суворі, а скоріше інтуїтивно зрозумілі докази деяких окремих положень цієї теорії, щоб ви зрозуміли, чим насправді є «Теорія Інформації», де ви можете її застосовувати, а де ні .
Насамперед, що таке “інформація”? Шеннон ототожнює інформацію з невизначеністю. Він вибрав негативний логарифм ймовірності події як кількісний захід інформації, яку ви отримуєте при настанні події з ймовірністю 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.ІІ
Далі розглянемо ідею пропускну спроможність каналу. Не вдаючись у подробиці, пропускна здатність каналу визначається як максимальний обсяг інформації, який може бути надійно переданий каналом зв'язку, з урахуванням використання максимально ефективного кодування. Немає доказів на користь те, що через канал зв'язку може бути передано більше інформації, ніж його ємність. Це можна довести для бінарного симетричного каналу (який ми використовуємо у нашому випадку). Ємність каналу, при побітовій відправці, задається як
де, як і раніше, 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 Вт, інші використовують атомні джерела живлення, що дають приблизно ту ж потужність. Слабка потужність джерела живлення, невеликі розміри тарілок передавачів та обмежені розміри тарілок приймачів на Землі, величезна відстань, яка має подолати сигнал – все це вимагає використання кодів з високим рівнем корекції помилок для побудови ефективної системи зв'язку.
Повернемося до n-вимірного простору, який ми використовували в доказі вище. Обговорюючи його, ми показали, що майже весь обсяг сфери зосереджений біля зовнішньої поверхні, - таким чином, майже напевно відправлений сигнал розташовуватиметься біля поверхні сфери, побудованої навколо прийнятого сигналу, навіть за відносно невеликого радіусу такої сфери. Тому не дивно, що прийнятий сигнал після виправлення довільно великої кількості помилок, nQ, виявляється як завгодно близький до сигналу без помилок. Місткість каналу зв'язку, яку ми розглянули раніше, є ключем до розуміння цього явища. Зауважте, що подібні сфери, побудовані для кодів Хеммінга з виправленням помилок, не перекривають одна одну. Велика кількість практично ортогональних вимірювань у n-мірному просторі показує, чому ми можемо вмістити M сфер у просторі з невеликим перекриттям. Якщо припустити невелике, скільки завгодно мале перекриття, яке може призводити тільки до невеликої кількості помилок при декодуванні, можна отримати щільне розміщення сфер у просторі. Хеммінг гарантував певний рівень виправлення помилок, Шеннон - низьку ймовірність помилки, але при цьому збереження фактичної пропускної спроможності як завгодно близької до ємності каналу зв'язку, чого коди Хеммінга зробити не можуть.
Теорія інформації не говорить про те, як спроектувати ефективну систему, але вона вказує напрямок руху у бік ефективних систем зв'язку. Це цінний інструмент для побудови систем зв'язку між машинами, але, як зазначалося раніше, вона не має особливого відношення до того, як обмінюються інформацією між собою. Ступінь, у якій біологічне успадкування подібно до технічних систем зв'язку, просто невідома, тому зараз не зрозуміло, наскільки теорія інформації застосовна до генів. Нам не залишається нічого іншого, як просто спробувати, і якщо успіх покаже нам машиноподібний характер цього явища, то невдача вкаже інші істотні аспекти природи інформації.
Давайте небагато відвернемося. Ми бачили, що всі початкові визначення, більшою чи меншою мірою, повинні виражати сутність наших споконвічних переконань, але їм властивий певний ступінь спотворення, і тому вони не застосовні. Традиційно прийнято, що, зрештою, визначення, яке ми використовуємо, фактично визначає суть; але, це лише вказує нам, як обробляти речі і аж ніяк не несе нам жодного сенсу. Постулаційний підхід, що настільки сильно схвалюється в математичних колах, залишає бажати кращого на практиці.
Тепер ми розглянемо приклад тестів на IQ, де визначення є настільки циклічним, наскільки це вам завгодно, і як наслідок вводить вас в оману. Створюється тест, який, як передбачається, має виміряти інтелект. Після цього він переглядається, що зробити його максимально послідовним, наскільки це можливо, а потім його публікують і простим методом калібрують таким чином, щоб вимірюваний «інтелект» виявився нормально розподіленим (звичайно ж по кривій калібруванні). Усі визначення повинні перевірятися ще раз, не тільки коли вони вперше запропоновані, але і набагато пізніше, коли вони використовуються у зроблених висновках. Наскільки межі визначень підходять для розв'язуваного завдання? Як часто визначення, дані в одних умовах, починають застосовуватися в умовах, що досить відрізняються? Таке трапляється досить часто! У гуманітарних науках, з якими ви неминуче зіштовхнетеся у вашому житті, це відбувається частіше.
Таким чином, однією з цілей цієї презентації теорії інформації, окрім демонстрації її корисності, було попередження вас про цю небезпеку, або демонстрація того, як її використовувати для отримання бажаного результату. Давно помічено, що початкові визначення обумовлюють те, що ви знаходите в результаті, набагато більшою мірою, ніж здається. Початкові визначення вимагають від вас великої уваги не тільки в будь-якій новій ситуації, а й у областях, з якими ви давно працюєте. Це дозволить вам зрозуміти, якою мірою отримані результати є тавтологією, а не чимось корисним.
Відома історія Еддінгтона оповідає про людей, які ловили рибу в морі з мережею. Вивчивши розмір риб, які вони впіймали, вони визначили мінімальний розмір риби, що водиться у морі! Їх висновок обумовлений використовуваним інструментом, а чи не дійсністю.
Далі буде ...
Хто хоче допомогти з перекладом, версткою та виданням книги — пишіть на личку чи на пошту [захищено електронною поштою]
До речі, ми ще запустили переклад ще однієї крутої книги. )
Особливо шукаємо тих, хто допоможе перекласти . (перекладаємо по 10 хвилин, перші 20 вже взяли)
Зміст книги та перекладені розділи
- Intro to The Art of Doing Science and Engineering: Learning to Learn (March 28, 1995)
- "Foundations of the Digital (Discrete) Revolution" (March 30, 1995)
- "History of Computers - Hardware" (March 31, 1995)
- "History of Computers - Software" (April 4, 1995)
- "History of Computers - Applications" (April 6, 1995)
- "Artificial Intelligence - Part I" (April 7, 1995)
- "Artificial Intelligence - Part II" (April 11, 1995)
- "Artificial Intelligence III" (April 13, 1995)
- "n-Dimensional Space" (April 14, 1995)
- "Coding Theory - The Representation of Information, Part I" (April 18, 1995)
- "Coding Theory - The Representation of Information, Part II" (April 20, 1995)
- "Error-Correcting Codes" (April 21, 1995)
- "Information Theory" (April 25, 1995)
- "Digital Filters, Part I" (April 27, 1995)
- "Digital Filters, Part II" (April 28, 1995)
- "Digital Filters, Part III" (May 2, 1995)
- "Digital Filters, Part IV" (May 4, 1995)
- "Simulation, Part I" (May 5, 1995)
- "Simulation, Part II" (May 9, 1995)
- "Simulation, Part III" (May 11, 1995)
- Fiber Optics (May 12, 1995)
- "Computer Aided Instruction" (May 16, 1995)
- "Mathematics" (May 18, 1995)
- "Quantum Mechanics" (May 19, 1995)
- "Creativity" (May 23, 1995). Переклад:
- "Experts" (May 25, 1995)
- "Unreliable Data" (May 26, 1995)
- "Systems Engineering" (May 30, 1995)
- You Get What You Measure (June 1, 1995)
- (Червень 2, 1995) перекладаємо по 10 хвилинним шматочкам
- Hamming, You and Your Research (June 6, 1995).
Хто хоче допомогти з перекладом, версткою та виданням книги — пишіть на личку чи на пошту [захищено електронною поштою]
Джерело: habr.com