Простір випадкових подій
1946 року американський учений-статистик Джон Тьюкі запропонував назву БІТ
Уявімо собі простір випадкових подій,яке складається з кидання однієї фальшивої монети, на обох сторонах якої орел. Коли випадає орел? Ясно, що завжди. Це ми знаємо заздалегідь, оскільки так влаштовано наше простір. Випадання орла - достовірна подія, тобто його ймовірність дорівнює 1. Чи багато інформації ми повідомимо, якщо скажемо про випав орле? Ні. Кількість інформації в такому повідомленні ми будемо вважати рівним 0.
Тепер давайте кидати правильну монету:з одного боку у неї орел, а з іншого решка, як і годиться. Випадання орла чи решки будуть двома різними подіями, у тому числі складається наш простір випадкових подій. Якщо ми повідомимо про результати одного кидання, то це дійсно буде нова інформація. При випадінні орла ми повідомимо 0, а при рішенні 1. Для того, щоб повідомити цю інформацію, нам достатньо 1 біта.
Що змінилося?У нашому просторі подій виникла невизначеність. Нам є, що про нього розповісти тому, хто сам монету не кидає і результату кидання не бачить. Але, щоб правильно зрозуміти наше повідомлення, він повинен точно знати, чим ми займаємося, що означають 0 та 1.Наші простору подій повинні збігатися, і процес декодування - однозначно відновлювати результат кидання.Якщо простір подій у передавального та приймаючого не співпадає чи немає можливості однозначного декодування повідомлення, інформація залишиться лише шумом у каналі зв'язку.
Якщо незалежно та одночасно кидати двімонети, то різних рівноймовірних результатів буде вже чотири: орел-орел, орел-решка, решка-орел та решка-решка. Щоб передати інформацію, нам знадобиться вже 2 біти, і наші повідомлення будуть такими: 00, 01, 10 та 11. Інформації стало вдвічі більше. Це сталося, бо зросла невизначеність. Якщо ми спробуємо вгадати результат такого парного кидання, маємо вдвічі більше шансів помилитися.
Чим більша невизначеність простору подій, тим більше інформації містить повідомлення про його стан.
Трохи ускладнимо наш простір подій.Поки що всі події, що траплялися, були рівноймовірними. Але в реальних просторах далеко не всі події мають однакову ймовірність. Скажімо, ймовірність того, що побачена нами ворона буде чорною, близька до 1. Імовірність того, що перший зустрінутий на вулиці перехожий виявиться чоловіком — приблизно 0,5. Але зустріти на вулиці Москви крокодила майже неймовірно. Інтуїтивно ми розуміємо, що повідомлення про зустріч із крокодилом має набагато більшу інформаційну цінність, ніж про чорну ворону.Чим нижча ймовірність події, тим більше інформації в повідомленні про таку подію.
Нехай простір подій не така екзотична. Ми просто стоїмо біля вікна і дивимося на проїжджаючі машини. Повз проїжджають автомобілі чотирьох кольорів, про які нам необхідно повідомити. Для цього ми закодируем кольору: чорний - 00, білий - 01, червоний - 10, синій - 11. Щоб повідомити про те, який саме автомобіль проїхав, нам достатньо передати 2 біта інформації.
Але досить довго спостерігаючи за автомобілями,помічаємо, що колір автомобілів розподілено нерівномірно: чорних - 50% (кожен другий), білих - 25% (кожен четвертий), червоних і синіх - по 12,5% (кожен восьмий). Тоді можна оптимізувати передану інформацію.
Найбільше чорних автомобілів, томупозначимо чорний — 0 — найкоротший код, а код решти всіх нехай починається на 1. З половини, що залишилися, білі — 10, а кольори, що залишилися, починаються на 11. На закінчення позначимо червоний — 110, а синій — 111.
Тепер, передаючи інформацію про колір автомобілів, ми можемо закодувати її щільніше.
Ентропія по Шеннону
Нехай наш простір подій складається з nрізних подій. При киданні монети з двома орлами така подія одно, при киданні однієї правильної монети — 2, при киданні двох монет або спостереженні за автомобілями — 4. Кожній події відповідає ймовірність її наступу. При киданні монети з двома орлами подія (випадання орла) одна і її ймовірність p1 = 1. При киданні правильної монети подій дві, вони рівноймовірні і ймовірність кожного - 0,5: p1 = 0,5, p2 = 0,5. При киданні двох правильних монет подій чотири всі вони рівноймовірні і ймовірність кожного - 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. При спостереженні за автомобілями подій чотири, і вони мають різні ймовірності: чорний – 0,5, білий – 0,25, червоний – 0,125, синій – 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Це не випадковий збіг.Шеннон так підібрав ентропію (міру невизначеності в просторі подій), щоб виконувалися три умови:
- 1Ентропія достовірної події, ймовірність якої 1 дорівнює 0.
- Ентропія двох незалежних подій дорівнює сумі ентропій цих подій.
- Ентропія максимальна, якщо всі події рівноймовірно.
Всі ці вимоги цілком відповідають нашимуявленням про невизначеність простору подій. Якщо подія одна (перший приклад) — жодної невизначеності немає. Якщо події незалежні — невизначеність суми дорівнює сумі невизначеностей — вони складаються (приклад із киданням двох монет). І, нарешті, якщо всі події рівноймовірні, то ступінь невизначеності системи є максимальним. Як у випадку з киданням двох монет, всі чотири події рівноймовірні і ентропія дорівнює 2, вона більша, ніж у випадку з автомобілями, коли подій теж чотири, але вони мають різну ймовірність - у цьому випадку ентропія 1,75.
Величина H відіграє центральну роль теорії інформації як міри кількості інформації, можливості вибору і невизначеності.
Клод Шеннон
Клод Шеннон- американський інженер, криптоаналітик іматематик. Вважається «батьком інформаційного віку». Засновник теорії інформації, що знайшла застосування у сучасних високотехнологічних системах зв'язку. Надав фундаментальні поняття, ідеї та їх математичні формулювання, які нині формують основу для сучасних комунікаційних технологій.
У 1948 році запропонував використовувати слово «біт»для позначення найменшої одиниці інформації. Він також продемонстрував, що введена ним ентропія еквівалентна мірі невизначеності інформації в переданому повідомленні. Статті Шеннона «Математична теорія зв'язку» і «Теорія зв'язку в секретних системах» вважаються основними для теорії інформації та криптографії.
Під час Другої світової війни Шеннон у Bell Laboratories займався розробкою криптографічних систем, пізніше це допомогло йому відкрити методи кодування з корекцією помилок.
Шеннон вніс ключовий внесок в теорію імовірнісних схем, теорію ігор, теорію автоматів і теорію систем управління - області наук, що входять в поняття «кібернетика».
кодування
І кидають монети, і проїжджаючі автомобілі несхожі на цифри 0 і 1. Щоб повідомити про події, що відбуваються в просторах, потрібно придумати спосіб описати ці події. Це опис називається кодуванням.
Кодувати повідомлення можна нескінченним числом різних способів. Але Шеннон показав, що найкоротший код не може бути меншим у бітах, ніж ентропія.
Саме тому ентропія повідомлення і є міраінформації у повідомленні. Оскільки у всіх розглянутих випадках кількість біт при кодуванні дорівнює ентропії, значить кодування пройшло оптимально. Коротше закодувати повідомлення про події в нашому просторі вже не можна.
При оптимальному кодуванні не можна втратити абоспотворити в повідомленні жодного біта, що передається. Якщо хоч один біт загубиться, то спотвориться інформація. Адже всі реальні канали зв'язку не дають 100-відсоткової впевненості, що всі біти повідомлення дійдуть до одержувача неспотвореними.
Для усунення цієї проблеми необхідно зробитикод не оптимальним, а надмірним. Наприклад, передавати разом із повідомленням його контрольну суму — спеціальним чином обчислене значення, одержуване під час перетворення коду повідомлення, яке можна перевірити, перерахувавши при отриманні повідомлення. Якщо передана контрольна сума збігатиметься з обчисленою, ймовірність того, що передача пройшла без помилок, буде досить високою. А якщо контрольна сума не збігається, необхідно запросити повторну передачу. Приблизно так сьогодні працює більшість каналів зв'язку, наприклад, при передачі пакетів інформації по інтернету.
Повідомлення на природній мові
Розглянемо простір подій, яке складаєтьсяз повідомлень на природній мові. Це окремий випадок, але один з найважливіших. Подіями тут будуть передані символи (літери фіксованого алфавіту). Ці символи зустрічаються в мові з різною ймовірністю.
Самим частотним символом (тобто таким, якийнайчастіше зустрічається у всіх текстах, написаних російською мовою) є пробіл: з тисячі символів в середньому пробіл зустрічається 175 разів. Другим за частотою є символ «о» - 90, далі йдуть інші голосні: «е» (або «е» - ми їх розрізняти не будемо) - 72, «а» - 62, «і» - 62, і тільки далі зустрічається перший приголосний «т» - 53. А найрідкісніший «ф» - цей символ зустрічається лише двічі на тисячу знаків.
Будемо використовувати 31-буквений алфавіт російськогомови (в ньому не відрізняються «е» і «е», а також «ь» і «ь»). Якби всі букви зустрічалися в мові з однаковою ймовірністю, то ентропія на символ була б Н = 5 біт, але якщо ми врахуємо реальні частоти символів, то ентропія виявиться менше: Н = 4,35 біт. (Це майже в два рази менше, ніж при традиційному кодуванні, коли символ передається як байт - 8 біт).
Але ентропія символу в мові ще нижче. Імовірність появи наступного символу в повному обсязі зумовлена середньою частотою символу в усіх текстах. Те, який символ буде, залежить від символів вже переданих. Наприклад, в сучасній російській мові після символу "ь" не може слідувати символ приголосного звуку. Після двох поспіль голосних "е" третій голосний «е» слід вкрай рідко, хіба тільки в слові «довгошиї». Тобто наступний символ в деякій мірі зумовлений. Якщо ми врахуємо таку зумовленість наступного символу, невизначеність (тобто інформація) наступного символу буде ще менше, ніж 4,35. За деякими оцінками, наступний символ в російській мові зумовлений структурою мови більш ніж на 50%, тобто при оптимальному кодуванні всю інформацію можна передати, викресливши половину букв у повідомленні.
Інша справа, що не всяку букву можна безболісно викреслити. Високочастотну «о» (і взагалі голосні), наприклад, викреслити легко, а ось рідкісні «ф» або «е» - досить проблематично.
Природна мова, якою ми спілкуємося один з одним, високо надмірна, а тому надійна, якщо ми щось недочули — нестрашно, інформацію все одно буде передано.
Але поки Шеннон не ввів міру інформації, ми не могли зрозуміти і того, що мова надлишковий, і до якої міри ми можемо стискати повідомлення (і чому текстові файли так добре стискаються архіватором).
Надмірність природної мови
У статті «Про те, як ми ворпсіманіем теcкт»(Назва звучить саме так!) Був узятий фрагмент роману Івана Тургенєва «Дворянське гніздо» і підданий деякого перетворення: з фрагмента було викреслено 34% букв, але не випадкових. Були залишені перші і останні букви в словах, викреслювалися тільки голосні, причому в повному обсязі. Метою було не просто отримати можливість відновити всю інформацію по перетвореному тексту, а й домогтися того, щоб людина, що читає цей текст, не відчував особливих труднощів через пропуски букв.
Чому порівняно легко читати цей зіпсованийтекст? У ньому справді міститься необхідна інформація відновлення цілих слів. Носій російської мови має у своєму розпорядженні певний набір подій (слів і цілих речень), які він використовує при розпізнаванні. Крім того, у розпорядженні носія є ще й стандартні мовні конструкції, які допомагають йому відновлювати інформацію. Наприклад,«Вона бла блее чвствтльна»— з високою ймовірністю можна прочитати як«Вона була більш чутлива». Але взята окремо фраза«Вона бла блее»скоріше, буде відновлено як«Вона була біліше». Оскільки ми у повсякденному спілкуванні маємо справуз каналами, в яких є шум і перешкоди, досить добре вміємо відновлювати інформацію, але тільки ту, яку ми вже знаємо заздалегідь. Наприклад, фраза«Чрти її НЕ бли лшни пріятнсті, хтя нмнго рспхлі і спллсь»добре читається за винятком останнього слова«Спллсь» - «спливла». Цього слова немає у сучасному лексиконі. При швидкому читанні слово«Спллсь»читається скоріше як «злиплися», за повільного — просто ставить у глухий кут.
Оцифровка сигналу
Звук, або акустичні коливання - це синусоїда. Це видно, наприклад, на екрані звукового редактора. Щоб точно передати звук, знадобиться нескінченну кількість значень - вся синусоїда. Це можливо при аналоговому з'єднанні. Він співає - ви слухаєте, контакт не переривається, поки триває пісня.
При цифровому зв'язку каналом ми можемо передати лише кінцеву кількість значень. Чи це означає, що звук не можна передати точно? Виявляється, ні.
Різні звуки – це по-різному модульована синусоїда.Ми передаємо тільки дискретні значення (частоти і амплітуди), а саму синусоїду передавати не треба - її може породити приймає прилад.Він породжує синусоїду, і на неї накладаєтьсямодуляція, створена за значеннями, переданими каналом зв'язку. Існують точні принципи, які саме дискретні значення треба передавати, щоб звук на вході в канал зв'язку збігався зі звуком на виході, де ці значення накладаються на деяку стандартну синусоїду (про це теорема Котельникова).
Теорема Котельникова (в англомовній літературі - теорема Найквіста - Шеннона, теорема відліків)- фундаментальне твердження в галузі цифровоїобробки сигналів, що зв'язує безперервні і дискретні сигнали і що, що «будь-яку функцію F(t), що складається з частот від 0 до f1, можна безперервно передавати з будь-якою точністю за допомогою чисел, що йдуть один за одним через 1/(2*f1) секунд.
Завадостійке кодування. коди Хеммінга
Якщо по ненадійному каналу передатизакодований текст Івана Тургенєва, нехай і з деякою кількістю помилок, то вийде цілком осмислений текст. Але от якщо нам потрібно передати всі з точністю до біта, завдання виявиться невирішеною: ми не знаємо, які біти помилкові, тому що помилка випадкова. Навіть контрольна сума не завжди рятує.
Саме тому сьогодні при передачі даних помереж прагнуть не стільки до оптимального кодування, при якому в канал можна заштовхати максимальну кількість інформації, скільки до такого кодування (завідомо надлишкового) при якому можна відновити помилки - так, приблизно, як ми при читанні відновлювали слова у фрагменті Івана Тургенєва.
Існують спеціальні перешкодостійкі коди, які дозволяють відновлювати інформацію після збою. Один з них - код Хеммінга.Допустимо, вся наша мова складається з трьох слів:111000, 001110, 100011. Ці слова знають і джерело повідомлення, і приймач. І ми знаємо, що в каналі зв'язку трапляються помилки, але при передачі одного слова спотворюється не більше одного біта інформації.
Припустимо, ми спочатку передаємо слово 111000. У результаті не більше ніж однієї помилки (помилки ми виділили) воно може перетворитися в одне зі слів:
1) 111000,011000, 101000, 110000, 111100, 111010, 111001.
При передачі слова 001110 може вийти кожне зі слів:
2) 001110,101110, 011110, 000110, 001010, 001100, 001111.
Нарешті, для 100011 у нас може вийти на прийомі:
3) 100011,000011, 110011, 101011, 100111 100001, 100010.
Зауважимо, що всі три списки попарно НЕперетинаються. Іншими словами, якщо на іншому кінці каналу зв'язку з'являється будь-яке слово зі списку 1, одержувач точно знає, що йому передавали саме слово 111000, а якщо з'являється будь-яке слово зі списку 2 - слово 001110, а зі списку 3 - слово 100011. У цьому випадку кажуть, що наш код виправив одну помилку.
Виправлення відбулося за рахунок двох факторів.По-перше, одержувач знає весь «словник», Тобто простір подій одержувача повідомлення збігається з простором того, хто повідомлення передав. Коли код передавався всього з однією помилкою, виходило слово, якого в словнику не було.
По-друге, слова в словнику були підібрані особливим чином.Навіть у разі виникнення помилки одержувач не мігпереплутати одне слово з іншим. Наприклад, якщо словник складається зі слів «дочка», «крапка», «кічка», і під час передачі виходило «вочка», то одержувач, знаючи, що такого слова не буває, виправити помилку не зміг би — будь-яке з трьох слів може виявитися правильним. Якщо ж у словник входять «крапка», «галка», «гілка» і нам відомо, що допускається не більше однієї помилки, то «вочка» це свідомо «крапка», а не «галка». У кодах, що виправляють помилки, слова вибираються саме так, щоб вони були «впізнавані» навіть після помилки. Різниця лише в тому, що в кодовому «алфавіті» лише дві літери — нуль та одиниця.
Надмірність такого кодування дуже велика, а кількість слів, які ми можемо таким чином передати, порівняно невелика.Адже нам треба виключати зі словника будь-яке слово,яке може при помилці збігтися з цілим списком, що відповідає переданим словам (наприклад, у словнику не може бути слів «дочка» та «крапка»). Але точна передача повідомлення настільки важлива, що на дослідження завадових кодів витрачаються великі сили.
сенсація
Поняття ентропії (або невизначеності інепередбачуваності) повідомлення і надмірності (або зумовленості і передбачуваності) дуже природно відповідають нашим інтуїтивним уявленням про міру інформації. Чим більше непередбачувано повідомлення (тим більше його ентропія, тому що менша ймовірність), - тим більше інформації воно несе. Сенсація (наприклад, зустріч з крокодилом на Тверській) - рідкісна подія, його передбачуваність дуже мала, і тому велика інформаційна вартість. Часто інформацією називають новини - повідомлення про тільки що події, що відбулися, про які ми ще нічого не знаємо. Але якщо про те, що трапилося нам розкажуть другий і третій раз приблизно тими ж словами, надмірність повідомлення буде велика, його непередбачуваність впаде до нуля, і ми просто не будемо слухати, відмахуючись від оратора зі словами «Знаю, знаю». Тому ЗМІ так намагаються бути першими. Ось це відповідність інтуїтивного відчуття новизни, яке народжує дійсно несподівана звістка, і зіграло головну роль в тому, що стаття Шеннона, абсолютно не розрахована на масового читача, стала сенсацією, яку підхопила преса, яку прийняли як універсальний ключ до пізнання природи вчені найрізноманітніших спеціальностей - від лінгвістів і літературознавців до біологів.
Алепоняття інформації по Шеннону - сувора математична теорія, І її застосування за межами теорії зв'язку дуже ненадійно. Зате в самій теорії зв'язку вона грає центральну роль.
семантична інформація
Шеннон, ввівши поняття ентропії як заходиінформації, отримав можливість працювати з інформацією — насамперед її вимірювати та оцінювати такі характеристики, як пропускна здатність каналів або оптимальність кодування. Але головним припущенням, яке дозволило Шеннону успішно оперувати з інформацією, було припущення, що породження інформації – це випадковий процес, який можна успішно описати у термінах теорії ймовірності.Якщо процес невипадковий, тобто він підпорядковується закономірностям (до того ж не завжди ясним, як це відбувається в природній мові), то до нього міркування Шеннона незастосовні.Все, що говорить Шеннон, не пов'язане з свідомістю інформації.
Поки ми говоримо про символи (або буквах алфавіту),ми цілком можемо міркувати в термінах випадкових подій, але як тільки ми перейдемо до слів мови, ситуація різко зміниться. Мова - це процес, особливим чином організований, і тут структура повідомлення не менш важлива, ніж символи, якими вона передається.
Ще недавно здавалося, що ми нічого не можемозробити, щоб хоч якось наблизитися до виміру свідомості тексту, але останніми роками ситуація почала змінюватися. І пов'язано це насамперед із застосуванням штучних нейронних мереж до завдань машинного перекладу, автоматичного реферування текстів, вилучення інформації з текстів, генерування звітів природною мовою. У всіх цих завданнях відбувається перетворення, кодування та декодування осмисленої інформації, укладеної у природній мові. І поступово складається уявлення про інформаційні втрати за таких перетворень, а отже — про міру осмисленої інформації. Але на сьогоднішній день тієї чіткості та точності, яку має шеннонівська теорія інформації, у цих важких завданнях ще немає.