2. Мера количества информации по Шэннону

Количество информации, содержащееся в сообщении, может быть определено как минимальная емкость, потребная для его хранения. Для ясности начнем с частного примера. Рассмотрим сообщение, имеющее два состояния, например, ответ на некоторый вопрос, допускающий лишь ответы «да» и «нет». Если я задаю вопрос: «Вы — левша?», ответное сообщение имеет два состояния и может быть запасено одной двоичной запасающей ячейкой. Хочется сказать, что сообщение содержит одну двоичную единицу информации, так как взятое само по себе оно не может быть запасено более экономно. Но такое заключение было бы слишком поспешно.

Допустим, что наш вопрос задан 128 лицам, и 128 ответных: двоичных сообщений запасены системой из двоичных запасающих ячеек. (Предполагается, что нам нужно не только подсчитать число ответов «да» и число ответов «нет», но и сохранить в точности порядок ответов.) Идя по наименее замысловатому пути, т. е. используя одну запасающую ячейку на каждое сообщение, мы получили бы, например, такуьр последовательность:

Ожидаемым ответом на вопрос «Вы - левша?» является «нет» и из 128 сообщений лишь одно или два будут иметь состояние «да». Ясно теперь, что было бы более экономным запасать положения ответов «да» в последовательности и преобразовывать номера 9, 25 и т. д. [из последовательности (2)] к двоичному виду 0001001 и 0011001. Нужно брать 7 знаков, так как всего имеется возможных сообщений. Таким образом, последовательность (2) может быть закодирована в последовательность

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

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

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

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

Все сказанное было лишь введением. Мы должны теперь рассмотреть очень интересную статистическую задачу о вычислении минимальной средней емкости, нужной для сообщения, если даны вероятности его различных состояний. Вычислительная сторона задачи легка, чего нельзя сказать, однако, про ее принципиальную сторону. Первый подход заключается в том, чтобы взять последовательность из сообщений, подсчитать общее число состояний и предусмотреть для каждого из них соответствующее состояние в накопителе. Пока что все тривиально: логарифм числа этих состояний дает емкость достаточно большую, очевидно, чтобы вместить наши сообщений, однако эта емкость больше, чем необходимо, так как здесь не учитываются априорные ожидания. Отсюда — второй подход, заключающийся в том, чтобы, увеличивая до бесконечности, использовать закон больших чисел (гл. I, § 2). Последовательности, в которых различные состояния встречаются в пропорции, заметно отличной от ее среднего значения, становятся все менее и менее вероятными, и в пределе их общая вероятность обращается в нуль, поэтому такие последовательности можно не

принимать в расчет. Таковы трудные ступени рассуждения; формальная же их обработка очень проста.

Для простоты рассмотрим сообщения, имеющие лишь два состояния, и предположим, что вероятности этих состояний, которые мы можем назвать гербом и решеткой, равны Аналогия между нашими сообщениями и орлянкой очень удачна, ибо в обоих случаях мы имеем дело, по существу, со случайной последовательностью двоичных знаков. Если правильная монета бросается раз и очень велико, число выпадений герба всегда находится где-то около Если монета погнута так, что вероятность герба равна тогда ожидаемое число гербов равно Более точно, вероятность выпадения некоторого числа гербов не лежащего внутри пределов

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

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

В пределе, как бы ни было мало последний член исчезает, и мы получаем

где лежит где-то в интервале (4). Остается лишь подставить (5) в (7) и упростить выражение. Игнорируя в (4), имеем и уравнение (5) может быть записано так:

Когда велико, это уравнение может быть упрощено с помощью асимптотической формулы Стирлинга

Таким образом, в силу уравнения (7), (8) и (9) дают

что является ответом на поставленную задачу. Таково среднее количество информации двоичного сообщения, в котором суть вероятности состояний. Если брать логарифмы при основании 2, то эта величина указывает, какова средняя доля двоичной запасающей ячейки, необходимая для запасания одного сообщения. Многократное повторение слова «среднее» здесь необходимо, так как формула получена путем усреднения по сообщениям, среди которых оба состояния встречаются пропорционально своим вероятностям. Действительно, из формы выражения (10) очевидно, что оно представляет собой среднее по двум состояниям, и это приводит к следующему очень простому заключению:

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

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

Когда сообщение имеет больше, чем два состояния, среднее количество информации на одно сообщение дается формулой Шэннона [1, 4]

где априорная вероятность состояния. Это выражение можно рассматривать как следствие из (11). Его можно также вывести из исходных принципов. Если всего имеется состояний, Я максимально, когда все равны, и равно

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

Читавшие первую главу узнают в выражении (12) энтропию распределения вероятностей Энтропия есть мера «недостающей информации» (слова Больцмана). Здесь не должно смущать представление, что измеряет среднюю информацию в сообщении, ибо действительно есть мера «априорного незнания», выраженная в терминах «априорных вероятностей». Когда состояние сообщения становится известным, вероятности превращаются в достоверности, незнание снимается, и информация соответственно увеличивается, как это станет ясно дальше.