Основы теории информации

Пусть имеет место некоторое случайное событие. То, что событие случайно, означает отсутствие полной уверенности в его наступлении, что, в свою очередь, создает неопределенность в исходах опытов, связанных с данным событием. Безусловно, степень неопределенности различна для разных ситуаций. Например, если опыт состоит в определении возраста случайно выбранного студента 1-го курса дневного отделения вуза, то с большой долей уверенности можно утверждать, что он окажется менее 30 лет; хотя по положению на дневном отделении могут обучаться лица в возрасте до 35 лет, чаще всего очно учатся выпускники школ ближайших нескольких выпусков. Гораздо меньшую определенность имеет аналогичный опыт, если проверяется, будет ли возраст произвольно выбранного студента меньше 20 лет. Для практики важно иметь возможность произвести численную оценку неопределенности разных опытов.

Введение количественной меры неопределенности целесообразно начать с простой ситуации, когда опыт имеет n равновероятных исходов. Очевидно, что неопределенность каждого из них зависит от n, то есть (символически) неопределенность = f(n). Можно указать некоторые свойства функции f:

· f(1)=0, поскольку при n=1 исход опыта не является случайным и, следовательно, неопределенность отсутствует;

· f(n) возрастает с ростом n, т.к. ввиду большого числа возможных исходов предсказание результата опыта становится весьма затруднительным.

Для определения явного вида функции f(n) рассмотрим два независимых опыта A и B, с количествами равновероятных исходов, соответственно n_A и n_B. Рассмотрим также сложный опыт C, который состоит в одновременном выполнении опытов A и B. Число возможных исходов опыта С равно n_A× n_B, причем, все они равновероятны. Очевидно, неопределенность исхода такого опыта будет больше неопределенности опыта A, поскольку к ней добавляется неопределенность B. Естественно допустить, что мера неопределенности C равна сумме неопределенностей опытов A и B, то есть неопределенность аддитивна:

(1)

Теперь можно задуматься о том, каким может быть явный вид функции f(n), чтобы он удовлетворял приведенным выше свойствам и соотношению (1)? Легко увидеть, что такому набору свойств удовлетворяет функция log(n), причем можно показать, что она единственная из всех возможных классов функций. Таким образом, за меру неопределенности опыта с n равновероятными исходами можно принять число log(n).

Следует заметить, что выбор основания логарифма в данном случае значения не имеет, поскольку в силу известной формулы перехода от одного основания логарифма к другому log_bn = log_ba× log_an, переход к другому основанию состоит во введении одинакового для обеих частей выражения (1) постоянного множителя log_ba, что равносильно изменению масштаба (то есть размера единицы) измерения неопределенности. Поскольку это так, мы имеет возможность выбрать удобное для нас (из каких-то дополнительных соображений) основание логарифма. Таким удобным основанием оказывается 2, поскольку в этом случае за единицу измерения принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода, которые можно обозначить, например, ИСТИНА (True) и ЛОЖЬ (False) и использовать для анализа таких событий аппарат математической логики.

Единица измерения неопределенности при двух возможных исходах опыта называется бит. Название бит происходит от английского binary digit, что в дословном переводе означает «двоичный разряд» или «двоичная единица».

Таким образом, установлен явный вид функции, описывающей неопределенность опыта, имеющего n равновероятных исхода:

(2)

На основании формулы для равновероятных исходов и (2) несложно найти неопределенность, вносимую каждым отдельным исходом в общую. Поскольку исходов n и все они равновероятны (и, следовательно, равнозначны), а общая неопределенность равна log₂n, из свойства аддитивности неопределенности следует, что неопределенность, вносимая одним исходом, составляет

. (3)

Таким образом, неопределенность E, вносимая каждым из равновероятных исходов, равна:

. (4)

Обобщая формулу (4) на ситуацию, когда исходы опытов не равновероятны, например, p(A₁) и p(A₂), имеем:

, (5)

, (6)

. (7)

Обобщая это выражение на n неравновероятных исходов, получаем:

. (8)

Введенная таким образом величина называется энтропией опыта A. С учетом формулы для среднего значения дискретных случайных величин , можно записать (8) в виде

. (9)

Это означает, что энтропия является мерой неопределенности опыта, в котором проявляются случайные события, и равна средней неопределенности всех возможных его исходов.

Из такого определения вытекают следующие свойства энтропии.

1. Как следует из (8), E=0 тогда и только тогда, когда какая-либо из вероятностей p(A_j)=1. Однако при этом из условия нормировки следует, что все остальные p(A_i)=0 (i¹ j), то есть реализуется ситуация, когда один из исходов является достоверным (а событие перестает быть случайным). Во всех остальных случаях, очевидно, E > 0.

2. Из аддитивности неопределенностей следует, что и энтропия, как мера неопределенности, должна обладать аддитивностью, то есть для двух независимых опытов A и B

E(AÙ B)=E(A)+E(B), (10),

то есть энтропия сложного опыта, состоящего из нескольких независимых, равна сумме энтропий отдельных опытов.

3. Пусть имеется два опыта с одинаковым числом исходов n, но в одном случае они равновероятны, а в другом – нет. Каково соотношение энтропий опытов? Можно доказать, что

, (11)

то есть при прочих равных условиях наибольшую энтропию имеет опыт с равновероятными исходами. Другими словами, энтропия максимальна в опытах, где все исходы равновероятны.

При этом имеет место аналогия с понятием энтропии, используемой в физике, когда энтропия выступает как мера беспорядка в системе, при этом вероятность состояния системы максимальна у полностью разупорядоченной (равновесной) системы, причем энтропия и термодинамическая вероятность связаны логарифмической зависимостью.

Рассмотрим пример. Пусть имеются два ящика, в каждом из которых по 12 шаров. В первом – 3 белых, 3 черных и 6 красных; во втором – каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей этих опытов? Согласно (10) находим энтропии обоих опытов:

, (12)

. (13)

Отсюда видно, что E₂> E₁, т.е. во втором опыте неопределенность исхода выше, что, кстати, иллюстрирует справедливость формулы (11).

Энтропия E(A) в соответствии с приведенным выше определением показывает неопределенность исхода опыта A. Возможна ситуация, когда в результате некоторого опыта B, который независим от A и предшествует ему, неопределенность A уменьшится.

Например, имеется три груза разной массы, и опыт состоит в определении наиболее тяжелого. Очевидно, неопределенность опыта уменьшится, если предварительно провести вспомогательный опыт – сравнить массы двух грузов и найти более тяжелый из них. Пусть E_B(A) – энтропия нового опыта, который нужно будет произвести после опыта B. Очевидно, E(A) ³ E_B(A), причем равенство реализуется в том случае, если знание исхода опыта B никак не сказывается на неопределенности опыта A. В остальных случаях знание исхода опыта B понижает неопределенность опыта A. Разность E(A) и E_B(A), очевидно, показывает, какие новые данные относительно A мы получаем, произведя опыт B. Эта разность называется информацией относительно опыта A, содержащейся в опыте B.

(14)

Это выражение открывает возможность численного измерения количества информации. Из него легко получить ряд следствий:

· поскольку единицей измерения неопределенности является бит, то в этих же единицах может быть измерено количество информации;

· пусть B=A, то есть произведен опыт A; очевидно, что при этом полностью снимается неопределенность исхода опыта A, то есть E_A(A)=0, тогда H=E(A) и энтропия опыта равна информации относительно события A, которая содержится в самом опыте;

· энтропия опыта равна той информации, которую мы получаем в результате его осуществления.

Последнее утверждение позволяет записать:

. (15)

На основании (15) можно определить среднее количество информации, содержащейся в каком-либо исходе опыта A. Рассмотрим ряд примеров применения этой формулы.

Пример 1. Какое количество информации требуется, чтобы узнать исход броска монеты?

Решение. В данном случае n=2 и события равновероятны, т.е. p₁=p₂=0, 5. Согласно (15),

H= –0, 5× log₂0, 5 – 0, 5× log₂0, 5 = 1 бит.

Пример 2. Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет». Какое количество информации мы должны получить (сколько задать вопросов), чтобы узнать задуманное число (полностью снять начальную неопределенность).

Решение. Исходами в данном случае являются:

A₁ = «задуман 0», A₂ = «задумано 1», A₃ = «задумано 2», A₄ = «задумано 3».

Предполагая, что вероятности «быть задуманными» у всех чисел одинаковы, для n=4 имеем p(A_i)=1/4, log₂ p(A_i)= –2 и H = 2 бит. Таким образом, для полного снятия неопределенности опыта (угадывания задуманного числа) нам необходимо 2 бит информации, то есть ответы на 2 вопроса с двумя возможными вариантами ответов (да – нет).

Количество информации равно числу вопросов с бинарными вариантами ответов, которые необходимо задать, чтобы полностью снять неопределенность задачи.

Какие вопросы необходимо задать, чтобы процесс угадывания был оптимальным, т.е. содержал минимальное их число? Здесь удобно воспользоваться так называемым выборочным каскадом (рис. 2):

Ответ 1

Вопрос 2

Ответ 2

Рис. 2. Выборочный каскад

Таким образом, два полученных ответа полностью снимают неопределенность. Подобная процедура позволяет определить количество информации в любом сообщении, интерпретация которого может быть сведена к парному выбору. Например, цепочке символов некоторого алфавита, использованного для представления сообщения.

На основе (15) нетрудно получить частное следствие для ситуации, когда все n исходов равновероятны. В этом случае

, (16)

, (17)

. (18)

Формула (18) была выведена еще в 1928 г. американским инженером Р.Хартли. Она связывает количество равновероятных событий n и количество информации в сообщении, что любое из этих событий произошло. Частным случаем применения формулы (18) при n=2^k является

. (19)

Пример: Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта?

Решение: Для данной ситуации n=2⁵, следовательно, k=5 и H=5 бит. Последовательность бинарных вопросов придумайте самостоятельно.

Попытаемся понять смысл полученных результатов. Необходимо выделить ряд моментов.

1. Формула (15) является статистическим определением понятия информация, поскольку в него входят вероятности возможных исходов опыта. По сути, мы даем операционное определение новой величины, то есть устанавливаем процедуру (способ) измерения величины. В науке (научном знании) именно такой метод введения новых терминов считается предпочтительным, поскольку то, что не может быть измерено, не может быть проверено и, следовательно, заслуживает меньшего доверия.

Если изначально исходов было n₁, а в результате передачи информации DH неопределенность уменьшилась и число исходов стало n₂ (очевидно, n₂£ n₁), то из (15) легко получить:

. (20)

Таким образом, можно утверждать, что информация – это то, что понижает неопределенность некоторого опыта с неоднозначным исходом, причем соответствующее количество информации равно логарифму отношения числа возможных исходов до и после получения информации.

2. Энтропию, таким образом, можно определить как меру недостатка информации в системе; она выражает общее количество отсутствующей информации о структуре (строении) системы. Наибольшая энтропия у равновесной полностью беспорядочной системы – о состоянии такой системы наша осведомленность минимальна. Упорядочение системы (наведение какого-то порядка) связано с получением некоторой дополнительной информации и уменьшением энтропии.

3. Объективность информации. Одна и та же информация может иметь различную оценку с точки зрения значимости (важности, ценности) разными потребителями. Определяющей в такой оценке оказывается содержание (смысл) сообщения[6]. Однако при решении задач технического характера содержание сообщения роли не играет. Например, задача телеграфной (и любой другой) линии связи – точно и безошибочно передать сообщение без анализа того, насколько ценной для получателя оказывается переданная информация. Техническое устройство не может оценить важности информации – его задача безошибочно передать или сохранить информацию. Выше мы определили информацию как результат выбора. Такое определение является объективным, а связанная с ним количественная мера информации – одинаковой для любого потребителя. То есть появляется возможность объективного измерения информации, при этом результат измерения – абсолютен. Это служит предпосылкой для решения технических задач. Как мы увидим далее, количество информации можно связать с числом символов (букв) в сообщении. Мы уже говорили, что информатика формулирует законы для формальных информационных процессов, то есть таких, где смысл и ценность информации выводится за рамки рассмотрения и никак не отслеживается. Это связано с тем, что нельзя предложить абсолютной и единой для всех меры ценности информации. С точки зрения информатики страница из учебника информатики или из «Войны и мира» и страница, записанная бессмысленными значками, содержат одинаковое количество информации. Другими словами, в теории информации информация отделяется от знания человека, которое связано с оценками смысла информации и которое не имеет количественной меры. По этой причине утверждение, что информация – это знание о чем-либо, является ошибочным в данном контексте. При этом, жертвуя смысловой (семантической) стороной информации, мы получаем объективные методы измерения количества информации, а также имеем возможность описывать информационные процессы математическими уравнениями. Это очень важно для решения проблем передачи, обработки и хранения информации с помощью технических устройств.

4. Пусть некоторый опыт имеет два исхода A и B, причем, p_A=0, 99, а p_B=0, 01. В случае исхода A мы получим количество информации H_A= –log₂0, 99=0, 0145 бит. В случае исхода B количество информации оказывается равным H_B= –log₂0, 01=6, 644 бит. Другими словами, больше информации связано с теми исходами, которые маловероятны. Действительно, то, что наступит именно A мы почти наверняка знали и до опыта; поэтому реализация такого исхода очень мало добавляет к нашей осведомленности. Наоборот, исход B – весьма редкий; информации с ним связано больше (осуществилось трудно ожидаемое событие). Однако такое большое количество информации мы будет при повторах опыта получать редко, поскольку мала вероятность B. Среднее же количество информации H=0, 99× H_A+0, 01× H_B»0, 081.

При передаче дискретных (текстовых) сообщений по каналу связи появление конкретного знака (буквы) в конкретном месте сообщения на приемном конце – событие случайное. Следовательно, узнавание (отождествление) знака требует получения некоторой порции информации. Попробуем оценить ее.

Сначала будем считать, что появление всех знаков (букв) алфавита в сообщении равновероятны. Тогда для английского алфавита n_e=26. Для русского алфавита n_r=33. Из (18) имеем:

H_e=log₂26=4, 700 бит,

H_r=log₂33=5, 044 бит.

То есть при равновероятном распределении букв получается, что любой знак русского алфавита несет больше информации, чем знак английского. Например, русская «а» несет больше информации, чем «a» английская! Это, безусловно, не означает, что английский язык – язык Шекспира и Диккенса – беднее, чем язык Пушкина и Достоевского. Лингвистическое «богатство» языка определяется количеством слов в нем и их сочетаний, а это никак не связано с числом букв в алфавите. С точки зрения техники это означает, что сообщения из равного количества символов будет иметь разную длину (и соответственно, время передачи) и большими они окажутся у сообщений на русском языке.

Приведенные оценки информационной емкости букв соответствуют предположению об их одинаковой вероятности появления в сообщении. На самом деле это не так, и относительная частота появления в тексте разных букв различна (таблица 5).

Таблица 5. Средние частоты букв для русского алфавита.

Можно поставить вопрос: каково среднее количество информации, приходящее на один знак алфавита, с учетом не равной вероятности их появления в сообщении (текстах)? На основе (15) имеем:

, (21)

где p_i – вероятность (относительная частота) i-го знака данного алфавита, H – средняя информация, приходящаяся на один знак.

Это и есть знаменитая формула К.Шеннона, с работы которого «Математическая теория связи», написанной в 1948 г., принято начинать отсчет возраста теории информации как самостоятельной науки[7].

Необходимо заметить, что формула Шеннона справедлива только в том случае, если вероятность p_i для данного знака одинакова в различных сообщениях. То, что это может быть не так, легко убедиться, если мы возьмем какое-либо короткое (с малым числом знаков) сообщение («Мама мыла раму»), то относительная частота букв не будет совпадать с приведенной в таблице 5. Поэтому вероятности знаков (относительные частоты) определяются для сообщений (текстов), содержащих много символов с тем, чтобы проявились статистические закономерности, неизменные с течением времени.

Сообщения, в которых вероятность появления знака не меняется с течением времени, называются шенноновскими. Теория информации строится именно для таких сообщений, поэтому в дальнейшем мы будем считать это исходным положением (условием применимости) теории.

Применение формулы (21) к алфавиту русского языка дает значение средней информации на знак H=4, 460 бит, для английского языка H=4, 143 бит, для французского H =3.986 бит, для немецкого H=4, 096 бит. В этих оценках, как и в таблице 5, пробел не включен в алфавит, его включение приводит к коррекции данных таблицы и, соответственно, значений H.

В любом случае, и для русского, и для английского языков учет вероятностей появления букв в сообщениях приводит к уменьшению среднего «информационного содержания» буквы, что, кстати, подтверждает справедливость формулы (11). Несовпадение значений средней информации для английского, французского и немецкого языков, основанных на одном алфавите, связано с тем, что частоты появления одинаковых букв в них различаются.

Значение средней информации на букву может быть еще уменьшено учетом корреляций, то есть связей между буквами в словах. Дело в том, что буквы в словах появляются не в любых сочетаниях; это понижает неопределенность угадывания следующей буквы после нескольких, например, в русском языке нет слов, в которых встречается сочетание щц или фъ. И напротив, после некоторых сочетаний можно с большей определенностью, чем чистый случай, судить о появлении следующей буквы, например, после распространенного сочетания пр - всегда следует гласная буква, а их в русском языке 10 и, следовательно, вероятность угадывания следующей буквы есть 1/10, а не 1/33. Учет в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения H=3, 32 бит, учет трехбуквенных – до H=3, 1 бит; экстраполяция, позволяющая учесть все сочетания, дает значение H=2, 14 бит.

Введем величину, которую будем называть избыточностью языка:

, (22)

где H – средняя информация на знак при представлении информации с помощью алфавита данного языка, а H_lim – предельная наименьшая информация на знак в данном языке. Исследования, проведенные Шенноном, показали, что для английского языка H_lim»1, 4¸ 1, 5 бит, что по отношению к H₀=4, 143 дает избыточность около 0, 64. Это означает, что в принципе возможно почти трехкратное сокращение языка без ущерба для его содержательной стороны и выразительности. Например, мы знаем, что в телеграммах используются сокращения «ЗПТ» и «ТЧК» вместо полных слов без ущерба для смысла. Однако такое «экономичное» представление слов снижает разборчивость сообщений и возможность понимания речи при наличии шума (а это одна из проблем передачи информации по реальным каналам связи).

Информационная избыточность естественных языков (и, соответственно, передаваемых сообщений) легла в основу подхода Шеннона к анализу криптозащищенных систем.