Лекция 4. Энтропия и информация

1. Объемный подход к измерению количества информации

2. Энтропийный подход к измерению количества информации

1. Объемный подход к измерению количества информации

Объем данных в сообщении измеряется количеством символов (разрядов) в этом сообщении. В различных системах счисления один разряд имеет различный вес. Также в различных системах счисления различны единицы измерения объема данных.

В двоичной системе счисления единица измерения количества информации – бит (bit – binary digit – двоичная цифра, двоичный разряд). В десятичной системе счисления единица измерения – дит (десятичный разряд).

Создатели компьютеров отдают предпочтение именно двоичной системе счисления потому, что в техническом устройстве наиболее просто реализовать два противоположных физических состояния. Имеется в виду некоторый физический элемент, имеющий два различных состояния: намагниченность в двух противоположных направлениях; прибор, пропускающий или не пропускающий электрический ток; конденсатор, заряженный или незаряженный; и т.п.

В компьютере бит является наименьшей возможной единицей информации. Объем данных, записанных двоичными знаками в памяти компьютера или на внешнем носителе информации, подсчитывается просто по количеству требуемых для такой записи двоичных символов. При этом, естественно, невозможно нецелое число битов.

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

8 бит = 1 байт;

1024 байта = 1 килобайт (Кбайт);

1024 килобайта = 1 мегабайт (Мбайт);

1024 магабайта = 1 гигабайт (Гбайт);

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

2. Энтропийный подход к измерению количества информации

Как выяснено в предыдущей лекции, предшествующий опыт может уменьшить количество исходов последующего опытаи, следовательно, уменьшить его неопределенность.Разностьвеличини, очевидно, показывает, какие новые сведения относительно опытамы получаем, произведя опыт. Эта величина называетсяинформацией относительно опыта , содержащейся в опыте:

. (5.1)

Данное выражение открывает возможность численного измерения количества информации, поскольку оценивать энтропию мы уже умеем. Из формулы (5.1) легко получить ряд следствий:

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

Следствие 2. Пусть опыт, то есть просто произведен опытсам по себе. Поскольку результат его несет полную информацию о себе самом, неопределенность исхода этого опыта полностью снимается, то есть. Тогда из (5.1) следует:.

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

Отметим ряд свойств информации:

1. , причемтогда и только тогда, когда опытыинезависимы. При этом опыты не несут никакой информации друг относительно друга.

2. , то есть информация симметрична относительно последовательности опытов.

3. Из Следствия 2, которое гласит , а также из представления энтропии в виде(формула (4.4) из предыдущей лекции) следует, что

. (5.2)

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

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

По формуле (5.2):

;

– вероятность выпадения герба;

– вероятность выпадения решки;

.

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

Исходами (их всего 4) в данном случае являются: – задуман 0;– задумана 1;– задумана 2;– задумана 3. Конечно, предполагается, что вероятности быть задуманными у всех чисел одинаковы, поэтому, где.

.

По формуле (5.2):

.

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

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

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

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

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

В рассмотренном примере два полученных ответа в выборочном каскаде полностью сняли начальную неопределенность. Подобная процедура позволяет определить количество информации в любой задаче, интерпретация которой может быть сведена к парному выбору. Данное утверждение перестает быть справедливым в том случае, если каждый из двух возможных ответов имеет разную вероятность – такая ситуация будет рассмотрена позднее.

Получим следствие формулы (5.2) для случая, когда все исходов опыта равновероятны. Именно такие опыты и рассматривались в примерах 1 и 2. В этом случае все

,

и, следовательно, формулу (5.2) можно переписать так:

.

Таким образом,

. (5.3)

Эта формула была выведена в 1928 году инженером Р.Хартли (США) и носит его имя. Онасвязывает количество равновероятных состояний и количество информациив сообщении о том, что какое-то из этих состояний реализовалось.

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

Частным случаем применения формулы (5.3) является ситуация, когда число возможных состояний (исходов опыта) можно представить в виде. Именно эта ситуация реализовалась в рассмотренных выше двух примерах. Подставляяв формулу (5.3), получаем:

. (5.4)

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

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

Для данной ситуации возможных исходов . Значит,, следовательно,.

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

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

2. Выражение (5.1) можно интерпретировать следующим образом. Если начальная энтропия опыта равна , а в результате сообщения информацииэнтропия становится равной(очевидно, что), то ясно, что формулу (5.1) можно переписать так:

,

то есть информация равна убыли энтропии.

В частном случае, если изначально равновероятных исходов в опыте было , а в результате передачи информациинеопределенность в исходе (результате) опыта уменьшилась, и число исходов стало(очевидно, что), то из (5.1) получается:

.

Таким образом, можно дать следующее определение понятия информации:

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

В случае равновероятных исходов некоторого опыта информация равна логарифму (по основанию 2) отношения числа возможных исходов этого опыта до и после получения информации.

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

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

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

4. Следствием аддитивности энтропии независимых опытов (см. формулу (4.5) из предыдущей лекции) является аддитивность информации.

Докажем это.

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

,

что и требовалось доказать.

5. Вернемся к утверждению о том, что количество информации (в битах) численно равно количеству вопросов с двумя равновероятными вариантами ответа. Означает ли это, что информация должна быть всегда величиной целой? Из формулы Хартли (5.3) следует, что(– целое число бит) только в случае. А в остальных ситуациях? Например, если нужно угадать число от 0 до 6 (всего 7 равновероятных исходов), необходимо получитьинформации. Поэтому для угадывания числа от 0 до 7 нужно задать 3 (три) вопроса, поскольку число вопросов, естественно, может быть только целым.

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

, где.

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

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

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

Рассмотрим опыт, реализующийся посредством двух случайных событий. Поскольку их (этих случайных событий) всего два, очевидно, что они являются дополнительнымидруг другу. Если эти события равновероятны, то их вероятности, поэтому информация, связанная с опытом, в результате которого появляется одно из этих событий, равна, как следует из (5.2) и из формулы Хартли. Однако, если вероятности этих событий различны (,), то из формулы (5.2) получаем функцию:

.

На рис. 2представлен график функции.

Видно, что при и прифункция. В частности, криваясимметрична относительно прямойи достигает максимума.

Рис. 2. График функции I(p).

Если теперь считать, что событие «1» – это утвердительный ответ на бинарный вопрос, а событие «2» – это отрицательный ответ на этот бинарный вопрос, то приходим к следующему заключению:

Ответ на бинарный вопрос может содержать не более 1 бит информации. При этом информация равна 1 бит только в случае равновероятных бинарных ответов; в остальных случаях информация меньше 1 бит.

Пример. При угадывании результата броска игральной кости задается вопрос: «Выпало 6?» Какое количество информации содержит ответ?

Утвердительный ответ имеет вероятность .

Отрицательный ответ имеет вероятность .

Таким образом, по формуле (5.2):

;

;

.

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

Таким образом, больше неопределенности(необходимой для ее снятия информации) связано с теми событиями (исходами опыта), которые менее вероятны. Действительно, то, что произойдет именно, мы почти наверняка знали и до опыта; поэтому реализация этого исхода добавляет мало к нашей осведомленности о результате опыта. Наоборот, исход– весьма редкий (трудноожидаемый); неопределенности с ним связано больше, поэтому и информации надо получить больше, чтобы узнать, что произойдет именно событие. Однако при многократных повторах опыта такое количество информации мы получать не будем, так как событиемаловероятно и будет происходить редко. Среднее же количество информации на один исход, то есть информация об опыте, согласно формуле (5.2) равна.

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