Узнайте, как формально измеряется количество информации по Шеннону. Познакомьтесь с комбинаторным и алфавитным подходами, а также с формулой Хартли для расчета количества информации. Используйте оптимальную стратегию в игре "Угадай число".
Cодержание
Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой "новой информации". Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого "Война и мир" в кодировке UTF-8. Его размер - 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?
Комбинаторный подход: информация по Хартли
Мы начнем с самого простого и естественного подхода, предложенного Хартли в 1928 году. Пусть задано некоторое конечное множество. Количеством информации в будем называть . Можно интерпретировать это определение следующим образом: нам нужно битов для описания элемента из .
Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальнейшем все логарифмы будут по основанию 2.
Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про стало известно, что . Теперь нам достаточно битов для описания , таким образом нам сообщили битов информации.
Пример
Воспользуемся приведенными рассуждениями. Можно сказать, что сообщение, уменьшающее пространство поиска в раз приносит битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.
Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.
Применение: цена информации
Любой вопрос можно сформулировать таким образом: "Сколько информации содержится в решении этого вопроса?". Разрешение вопроса равно количеству информации, потраченной на его решение.
Понятие информации
Информация - это одно из фундаментальных понятий современной науки, наряду с понятиями материи и энергии. С точки зрения же человека, информация - это некие сведения, которые могут быть понятными, достоверными, актуальными и т.п., или наоборот.
Существуют различные формальные подходы к определению информации. С точки зрения информатики, нас интересуют два определения.
Подход Хартли
Это удобное интуитивное определение. Неопределенность в данном случае - характеристика нашего незнания о предмете. Например, в момент броска игрального кубика, мы не знаем, какая из 6 граней выпадет. Когда же кубик останавливается на какой-то грани - мы получаем информацию.
Это определение, однако, не слишком удобно без некоторой количественной меры неопределенности.
Алфавитный подход
Так, например, игральный кубик имеет неопределенность 6.
Такой подход к определению информации называется содержательным. Он интуитивно понятен, однако, не отвечает на вопрос "сколько информации получено".
Поскольку любой алфавит может быть закодирован в двоичном, очевидно это определение достаточно универсально: оно применимо для любого сообщения, которое может быть записано на каком-либо языке. Этот подход называется алфавитным.
В качестве основной единицы количества информации принято брать бит - от binary digit.
При алфавитном подходе один бит - это количество информации, которое можно закодировать одним двоичным знаком (0 или 1). С точки зрения содержательного подхода, один бит - это количество информации, уменьшающее неопределенность в два раза.
Существуют более крупные единицы информации, которые чаще используются на практике.
Формула Хартли
Сколько же информации получается в результате броска кубика?
Рассмотрим сначала более простую задачу: сколько информации получается в результате броска монеты? Считаем, что возможны два варианта: "орел" и "решка".
Исходя из содержательного подхода, неопределенность броска монеты составляет 2. После броска, мы имеем один вариант, поэтому количество информации будет равно 1 биту.
Существует множество ситуаций, когда возможные события имеют различные вероятности реализации. Например, если монета несимметрична (одна сторона тяжелее другой), то при ее бросании вероятности выпадения "орла" и "решки" будут различаться.
Формулу для вычисления количества информации в случае различных вероятностей событий предложил К. Шеннон в 1948 году. В этом случае количество информации определяется по формуле:
I = -sum(pi * log2(pi))
где I - количество информации;
N - количество возможных событий;
pi - вероятность i-го события.
Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:
p1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/8.
Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле:
I = -(1/2 * log2(1/2) + 1/4 * log2(1/4) + 1/8 * log2(1/8) + 1/8 * log2(1/8)) = (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита.
Этот подход к определению количества информации называется вероятностным.
Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (pi = 1/N), величину количества информации I можно рассчитать по формуле:
I = log2(N)
По формуле можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:
I = log2(4) = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.
Количество информации, которое мы получаем, достигает максимального значения, если события равновероятны.
Выбор оптимальной стратегии в игре "Угадай число"
На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).
При оптимальной стратегии интервал чисел всегда должен делиться пополам, тогда количество возможных событий (чисел) в каждом из полученных интервалов будет одинаково и отгадывание интервалов равновероятно. В этом случае на каждом шаге ответ первого игрока ("Да" или "Нет") будет нести максимальное количество информации.
