Глава 3. количественная оценка информации 1 страница

§ 3.1. ЭНТРОПИЯ КАК МЕРА НЕОПРЕДЕЛЕННОСТИ ВЫБОРА

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

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

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

глава 3. количественная оценка информации 1 страница - student2.ru

причем

глава 3. количественная оценка информации 1 страница - student2.ru

Обе формы записи используются в дальнейшем на равных основаниях.

Опираясь на эти сведения, введем сначала меру неопределенности выбора состояния источника. Ее можно рассматривать и как меру количества информации, получаемой при полном устранении неопределенности относительно состояния источника. Мера должна удовлетворять ряду естественных условий. Одним из них является необходимость монотонного возрастания с увеличением возможностей выбора, т. е. числа возможных состояний источника N, причем недопустимые состояния (состояния с вероятностями, равными нулю) не должны учитываться, так как они не меняют неопределенности.

Ограничиваясь только этим условием, за меру неопределенности можно было бы взять число состояний, предположив, что они равновероятны. Однако такая мера противоречит некоторым интуитивным представлениям. Например, при N=1, когда неопределенность отсутствует, она давала бы значение, равное единице. Кроме того, такая мера не отвечает требованию аддитивности, состоящему в следующем.

Если два независимых источника с числом равновероятных состояний N и Μ рассматривать как один источник, одновременно реализующий пары состояний nimj, то естественно предположить, что неопределенность объединенного источника должна равняться сумме неопределенностей исходных источников. Поскольку общее число состояний объединенного источника равно ΝΜ, то искомая функция должна удовлетворять условию

глава 3. количественная оценка информации 1 страница - student2.ru

Соотношение (3.2) выполняется, если в качестве меры неопределенности источника с равновероятными состояниями и характеризующего его ансамбля U принять логарифм числа состояний:

глава 3. количественная оценка информации 1 страница - student2.ru

Тогда при Ν= 1 H(U) = 0 и требование аддитивности выполняется.

Указанная мера была предложена американским ученым Р. Хартли [31] в 1928г. Основание логарифма не имеет принципиального значения и определяет только масштаб или единицу неопределенности. Так как современная информационная техника базируется на элементах, имеющих два устойчивых состояния, то обычно выбирают основание логарифма равным двум. При этом единица неопределенности называется двоичной единицей или битом и представляет собой неопределенность выбора из двух равновероятных событий (bit — сокращение от англ. binary digit — двоичная единица). Если основание логарифма выбрать равным десяти, то неопределенность получим в десятичных единицах на одно состояние (битах).

Пример 3.1. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.

Общая неопределенность ансамбля U в соответствии с (3.3) составляет

глава 3. количественная оценка информации 1 страница - student2.ru

Одно взвешивание способно прояснить неопределенность ансамбля U', насчитывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии) Эта неопределенность

глава 3. количественная оценка информации 1 страница - student2.ru

Так как

глава 3. количественная оценка информации 1 страница - student2.ru

для определения фальшивой монеты достаточно произвести три взвешивания.

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

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

Таким образом, степень неопределенности реализации состояния источника информации зависит не только от числа состояний, но и от вероятностей этих состояний. При неравновероятных состояниях свобода выбора источника ограничивается, что должно приводить к уменьшению неопределенности. Если источник информации имеет, например, два возможных состояния с вероятностями 0,99 и 0,01, то неопределенность выбора у него значительно меньше, чем у источника, имеющего два равновероятных состояния. Действительно, в первом случае результат практически предрешен (реализация состояния, вероятность которого равна 0,99), а во втором случае неопределенность максимальна, поскольку никакого обоснованного предположения о результате выбора сделать нельзя. Ясно также, что весьма малое изменение вероятностей состояний вызывает соответственно незначительное изменение неопределенности выбора.

Это позволяет сформулировать следующее требование к искомой мере неопределенности Н(р1 ... рi ... рN): она должна быть непрерывной функцией вероятностей состояний источника р1 ... pi ... рN с соблюдением условия глава 3. количественная оценка информации 1 страница - student2.ru I = 1. Наибольшее ее значение должно достигаться ι= 1 при равенстве вероятностей всех состояний.

Кроме того, так как мера неопределенности связывается нами только с фактом выбора, а не с множеством конкретных значений наблюдаемых явлений, то Н(р1 … ρN) должна быть функцией от функции распределения случайной величины и не должна зависеть от ее конкретных значений. Иначе говоря, Η(ρ1...ρN) должна являться функционалом распределения вероятностей.

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

глава 3. количественная оценка информации 1 страница - student2.ru

где q1, q2 и q3, q4 — вероятности состояний, образующих соответственно группы Ν—1 и Ν, причем ρN-1 = q1 + q2 и pN-1 = q3 + q4.

Мера неопределенности выбора дискретным источником состояния из ансамбля U, удовлетворяющая указанным условиям, была предложена американским ученым К. Шенноном [36]. Ее называют энтропией дискретного источника информации или энтропией конечного ансамбля:

глава 3. количественная оценка информации 1 страница - student2.ru

где С — произвольное положительное число.

К. Шенноном высказано утверждение, а советским ученым Л. Я- Хинчиным математически строго доказано, что это единственный функционал, удовлетворяющий сформулированным условиям.

Если снова ориентироваться на измерение неопределенности в двоичных единицах, то основание логарифма следует принять равным двум. Примем также С= 1. Из (3.5)

глава 3. количественная оценка информации 1 страница - student2.ru

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

глава 3. количественная оценка информации 1 страница - student2.ru

где Mn — число молекул в данном пространстве; mi — число молекул, обладающих скоростью uI + Du.

Так как miп есть вероятность того, что молекула имеет скорость ui + Δu, то (3.7) можем записать в виде

глава 3. количественная оценка информации 1 страница - student2.ru

Совпадение имеет глубокий физический смысл, так как в обоих случаях величина H характеризует степень разнообразия состояний системы.

Рассмотрим взаимосвязь меры К. Шеннона с мерой Хартли. Если в источнике может быть реализовано N равновероятных состояний, то вероятность каждого из них равна рi = (1/N)(1 глава 3. количественная оценка информации 1 страница - student2.ru i глава 3. количественная оценка информации 1 страница - student2.ru N) и неопределенность, по Хартли, приходящаяся на каждое состояние, выражается числом

глава 3. количественная оценка информации 1 страница - student2.ru

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

глава 3. количественная оценка информации 1 страница - student2.ru

Эта частная неопределенность представляет собой случайную величину, зависящую от того, какое состояние источника в действительности реализуется. Усреднив по всему ансамблю U состояний источника, найдем неопределенность, приходящуюся в среднем на одно состояние:

глава 3. количественная оценка информации 1 страница - student2.ru

Следовательно, мера К. Шеннона является естественным обобщением меры Хартли на случай ансамбля с неравновероятными состояниями. Она позволяет учесть статистические свойства источника информации.

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

Таблица 3.1

глава 3. количественная оценка информации 1 страница - student2.ru

При одинаковых вероятностях появления всех 32 букв алфавита неопределенность, приходящаяся на одну букву, составляет

глава 3. количественная оценка информации 1 страница - student2.ru

Энтропию источника, характеризуемого заданным ансамблем (табл. 3.1), находим, используя формулу (3.6):

глава 3. количественная оценка информации 1 страница - student2.ru

Таким образом, неравномерность распределения вероятностей использования букв снижает энтропию источника с 5 до 4.42 дв. ед.

§ 3.2 СВОЙСТВА ЭНТРОПИИ

Рассмотрим основные свойства энтропии, обратив внимание на то, что сформулированные условия для меры неопределенности выполняются.

1. Энтропия является вещественной и неотрицательной величиной, так как для любого i(1 глава 3. количественная оценка информации 1 страница - student2.ru ) рi изменяется в интервале от 0 до 1, log pi отрицателен и, следовательно, — pi log pi положительна.

2. Энтропия — величина ограниченная. Для слагаемых - pi log pi в диапазоне 0<рi глава 3. количественная оценка информации 1 страница - student2.ru 1 ограниченность очевидна. Остается определить предел, к которому стремится слагаемое — pi log pi, при рi—>0, поскольку — log pi при этом неограниченно возрастает:

глава 3. количественная оценка информации 1 страница - student2.ru

Обозначив a= 1/рi и воспользовавшись правилом Лопиталя, получим

глава 3. количественная оценка информации 1 страница - student2.ru

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

4. Энтропия максимальна, когда все состояния источника равновероятны, что легко доказывается методом неопределенных множителей Лагранжа [23]:

глава 3. количественная оценка информации 1 страница - student2.ru

5. Энтропия источника и с двумя состояниями u1 и u2 изменяется от нуля до единицы, достигая максимума при равенстве их вероятностей:

глава 3. количественная оценка информации 1 страница - student2.ru глава 3. количественная оценка информации 1 страница - student2.ru

График зависимости H(U) в функции ρ

глава 3. количественная оценка информации 1 страница - student2.ru

приведен на рис. 3.1. При ρ « (1- р)частная неопределенность, приходящаяся на состояние u1, велика, однако такие состояния источника весьма редки. Состояния u2 реализуются часто, но неопределенность, приходящаяся на такое состояние, очень мала. Поэтому энтропия, характеризующая среднюю неопределенность на одно состояние ансамбля, также мала. Аналогичная ситуация наблюдается при р » (1—р)·

Отметим, что энтропия непрерывно зависит от вероятностей отдельных состояний, что непосредственно вытекает из непрерывности функции - p log p.

6. Энтропия объединения нескольких статистически независимых источников информации равна сумме энтропии исходных источников.

Не теряя общности, ограничимся рассмотрением объединения, включающего два источника информации u и u. Под объединением двух источников u и u понимают обобщенный источник информации (u,u), характеризующийся вероятностями p(uiui) всех возможных комбинаций состояний ui, источника u и ui, источника u. Аналогично трактуется и объединение ансамблей.

В соответствии с определением энтропия объединения

глава 3. количественная оценка информации 1 страница - student2.ru

здесь p(uiui) — вероятности совместной реализации состояний

глава 3. количественная оценка информации 1 страница - student2.ru

В случае статистической независимости источников информации u и υ запишем

глава 3. количественная оценка информации 1 страница - student2.ru

тогда

глава 3. количественная оценка информации 1 страница - student2.ru

Учитывая, что

глава 3. количественная оценка информации 1 страница - student2.ru

получим

глава 3. количественная оценка информации 1 страница - student2.ru

Соответственно для энтропии объединения нескольких независимых источников u, u, z имеем

глава 3. количественная оценка информации 1 страница - student2.ru

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

7. Энтропия характеризует среднюю неопределенность выбора одного состояния из ансамбля. При ее определении используют только вероятности состояний, полностью игнорируя их содержательную сторону. Поэтому энтропия не может служить средством решения любых задач, связанных с неопределенностью. Например, при использовании этой меры для оценки неопределенности действия лекарства, приводящего к полному выздоровлению больных в 90 % случаев и улучшению самочувствия в остальных 10 % случаев, она получится такой же, как и у лекарства, вызывающего в 90 % случаев смерть, а в 10 % — ухудшение состояния больных.

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

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

Пример 3.3. Заданы ансамбли U и V двух дискретных случайных величин U' и V¢:

глава 3. количественная оценка информации 1 страница - student2.ru

Сравнить их энтропии.

Так как энтропия не зависит от конкретных значений случайной величины, а вероятности их появления у обеих величин одинаковы, то

глава 3. количественная оценка информации 1 страница - student2.ru

§ 3.3. УСЛОВНАЯ ЭНТРОПИЯ И ЕЕ СВОЙСТВА

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

Определим энтропию объединения двух статистически связанных ансамблей U и V. Объединение ансамблей характеризуется матрицей p(UV) вероятностей р(uiui) всех возможных комбинаций состояний ui(1£ i £ N) ансамбля U и состояний uj(1 £ j £ k) ансамбля V:

глава 3. количественная оценка информации 1 страница - student2.ru

Суммируя столбцы и строки матрицы (3.14), получим информацию об ансамблях U и V исходных источников u и u:

глава 3. количественная оценка информации 1 страница - student2.ru

Вероятности р(uiui) совместной реализации взаимозависимых состояний и, и ν·, можно выразить через условные вероятности р(ui/ui) или p(uj/ui) в соответствии с тем, какие состояния принять за причину, а какие — за следствие:

глава 3. количественная оценка информации 1 страница - student2.ru

где p(ui/uj) — вероятность реализации состояний ui ансамбля U при условии, что реализовалось состояние uj ансамбля V; P(uj/ui) — вероятность реализации состояния uj ансамбля V при условии, что реализовалось состояние ui ансамбля U. Тогда выражение (3.11) для энтропии объединения принимает вид

глава 3. количественная оценка информации 1 страница - student2.ru

Сумма

глава 3. количественная оценка информации 1 страница - student2.ru

представляет собой случайную величину, характеризующую неопределенность, приходящуюся на одно состояние ансамбля V при условии, что реализовалось конкретное состояние ui ансамбля U.

Назовем ее частной условной энтропией ансамбля V и обозначим Hui(V):

глава 3. количественная оценка информации 1 страница - student2.ru

При усреднении по всем состояниям ансамбля U получаем среднюю неопределенность, приходящуюся на одно состояние ансамбля V при известных состояниях ансамбля U:

глава 3. количественная оценка информации 1 страница - student2.ru

или

глава 3. количественная оценка информации 1 страница - student2.ru

Величину НU(V) называют полной условной или просто условной энтропией ансамбля V по отношению к ансамблю U.

Подставляя (3.19) в (3.16), получаем

глава 3. количественная оценка информации 1 страница - student2.ru

Выражая в (3.11) p(uiuj) через другую условную вероятность в соответствии с (3.15), найдем

глава 3. количественная оценка информации 1 страница - student2.ru

где

глава 3. количественная оценка информации 1 страница - student2.ru

и

глава 3. количественная оценка информации 1 страница - student2.ru

Таким образом, энтропия объединения двух статистически связанных ансамблей U и V равна безусловной энтропии одного ансамбля плюс условная энтропия другого относительно первого.

Распространяя правило (3.19) на объединение любого числа зависимых ансамблей, получим

глава 3. количественная оценка информации 1 страница - student2.ru

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

Для объединения двух ансамблей U и V данное утверждение принимает вид соотношений

глава 3. количественная оценка информации 1 страница - student2.ru

Из (3.20) и (3.25) следует, что объединение двух произвольных ансамблей удовлетворяет соотношению

глава 3. количественная оценка информации 1 страница - student2.ru

Для объединения нескольких произвольных ансамблей соответственно имеем

глава 3. количественная оценка информации 1 страница - student2.ru

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

В случае отсутствия статистической связи в реализациях состояний ui, из ансамбля U и υj из ансамбля V сведения о результатах выбора состояний из одного ансамбля не снижают неопределенности выбора состояний из другого ансамбля, что находит отражение в равенствах

глава 3. количественная оценка информации 1 страница - student2.ru

Если имеет место однозначная связь в реализациях состояний ui(1 £ i £ N) из ансамбля U и uj(1 £ j £ N) из ансамбля V, то условная энтропия любого из ансамблей равна нулю:

глава 3. количественная оценка информации 1 страница - student2.ru

глава 3. количественная оценка информации 1 страница - student2.ru Действительно, условные вероятности р(ui/uj) и P(uj/ui) в этом случае принимают значения, равные нулю или единице. Поэтому все слагаемые, входящие в выражения (3.17) и (3.23) для частных условных энтропии, равны нулю. Тогда в соответствии с (3.18) и (3.22) условные энтропии также равны нулю.

Равенства (3.30) отражают факт отсутствия дополнительной неопределенности при выборе событий из второго ансамбля.

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

Пример 3.4. Определить энтропии Н(U), H(V), Ηu(U), H(UV), если задана матрица вероятностей состояний системы, объединяющей источники u и u:

глава 3. количественная оценка информации 1 страница - student2.ru

Вычисляем безусловные вероятности состояний каждой системы как суммы совместных вероятностей по строкам и столбцам заданной матрицы:

глава 3. количественная оценка информации 1 страница - student2.ru

Определяем условные вероятности

глава 3. количественная оценка информации 1 страница - student2.ru

глава 3. количественная оценка информации 1 страница - student2.ru

Пример 3.5. Известны энтропии двух зависимых источников: H(U) = 5 дв. ед., H(V) = 10 дв. ед. Определить, в каких пределах будет изменяться условная энтропия Ηυ(V) при изменении HV(U) в максимально возможных пределах.

При решении удобно использовать графическое отображение связи между этропиями. Из рис. 3.3. видим, что максимального значения Hu(V) достигает при от глава 3. количественная оценка информации 1 страница - student2.ru сутствии взаимосвязи и будет равно H(V), т.е. 10 дв. ед. По мере увеличения взаимосвязи Нu(V) будет уменьшаться до значения H(V) — H(U) = 5 дв. ед. При этом HV(U) = 0.

§ 3.4. ЭНТРОПИЯ НЕПРЕРЫВНОГО ИСТОЧНИКА ИНФОРМАЦИИ (ДИФФЕРЕНЦИАЛЬНАЯ ЭНТРОПИЯ)

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

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

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

глава 3. количественная оценка информации 1 страница - student2.ru Естественно, однако, связывать неопределенность выбора значения непрерывной случайной величины с плотностью распределения вероятностей этих значений. Учитывая, что для совокупности значений, относящихся к любому сколь угодно малому интервалу непрерывной случайной величины, вероятность конечна, попытаемся найти формулу для энтропии непрерывного источника информации, используя операции квантования и последующего предельного перехода при уменьшении кванта до нуля.

С этой целью разобьем диапазон изменения непрерывной случайной величины U, характеризующейся плотностью распределения вероятностей р(u), на конечное число n малых интервалов шириной Δu (рис. 3.4). При реализации любого значения u, принадлежащего интервалу ( глава 3. количественная оценка информации 1 страница - student2.ru глава 3. количественная оценка информации 1 страница - student2.ru ), будем считать, что реализовалось значение глава 3. количественная оценка информации 1 страница - student2.ru дискретной случайной величины U. Поскольку Δu мало, вероятность глава 3. количественная оценка информации 1 страница - student2.ru реализации значения u из интервала глава 3. количественная оценка информации 1 страница - student2.ru :

глава 3. количественная оценка информации 1 страница - student2.ru

Тогда энтропия дискретной случайной величины Ữ может быть записана в виде:

глава 3. количественная оценка информации 1 страница - student2.ru

или

глава 3. количественная оценка информации 1 страница - student2.ru

Так как

глава 3. количественная оценка информации 1 страница - student2.ru

то

глава 3. количественная оценка информации 1 страница - student2.ru

По мере уменьшения Δu глава 3. количественная оценка информации 1 страница - student2.ru все больше приближается к вероятности глава 3. количественная оценка информации 1 страница - student2.ru , равной нулю, а свойства дискретной величины Ữ — к свойствам непрерывной случайной величины U.

Переходя к пределу при Δu→0, получаем следующее выражение для энтропии H(U) непрерывного источника:

глава 3. количественная оценка информации 1 страница - student2.ru

Наши рекомендации