|
1.3. Условная энтропия. Свойства иерархической
аддитивности Обобщим формулы (1.2.1), (1.2.3)
на случай условных вероятностей.
Пусть имеются случайные величины x1,
…, xn, описываемые
совместным распределением P(x1,
…, xn).
Условной вероятности
P(xk, …, xnЅ
x1, …, xk-1)=
P(x1, …, xn)/
P(x1, …, xk-1)
(k Ј
n).
сопоставляем случайную условную энтропию
Н(xk, …, xnЅ
x1, …, xk-1)=
-ln P(xk, …, xnЅ
x1, …, xk-1) (1.3.1)
Введем особое обозначение для результата усреднения
ее по xk, …, xn:
Нxk, …, xn(
Ѕ x1,
…, xk-1)= - еxk,
…, xn P(xk,
…, xnЅ
x1, …, xk-1)
x ln P(xk, …, xnЅ
x1, …, xk-1),
(1.3.2)
Рис.1.1. Этапы разбиения и дерево выборов в общем
случае
также для результата полного усреднения:
Нxk, …, xn
Ѕ x1,
…, xk-1 = MН(xk,
…, xn Ѕ
x1, …, xk-1)
= - еx1,
…, xn P(x1,
…, xnЅ
x1, …, xk-1)
x ln P(xk, …, xnЅ
x1, …, xk-1),
(1.3.3)
Если еще менять k и n, то мы будем иметь большое число
различных энтропий, условных и безусловных, случайных
и неслучайных.
Между ними существуют определенные тождественные соотношения,
которые рассматриваются ниже.
Прежде чем перейти к формулировке основного иерархического
тождества (1.3.4.), покажем, как можно ввести
иерархическое множество случайных величин x1,
…, xn, даже если первоначально
была лишь одна случайная величина x.
Пусть x принимает одно из М значений
с вероятностью P(x).
Выбор одной реализации будем производить в несколько
этапов.
На первом этапе пусть указывается принадлежность тому
или иному подмножеству из полного набора неперекрывающихся
подмножеств E1, …, Em1.
Пусть x1 указывает
номер этого подмножества.
На втором этапе каждое подмножество делится на более
мелкие подмножества Ex1 x2.
Вторая случайная величина x2
указывает, какому более мелкому подмножеству принадлежит
реализация случайной величины.
Эти более мелкие подмножества делятся, в свою очередь,
до тех пор, пока мы не получим подмножества, состоящие
из одного элемента.
Число n нетривиальных этапов разбиения, очевидно,
не может превосходить M - 1.
Фиксированной схеме разбиений можно сопоставить дерево,
изображенное на рис. 1.1.
Дальнейшее рассуждения будут относиться к какому-то
одному выбранному дереву.
Чтобы указать реализацию x,
необходимо и достаточно фиксировать совокупность реализаций
( x1,
x2, …, xn).
Чтобы указать узел (k+1)-го этапа, нужно указать значения
x1, ..., xk.
Тогда значение xk+1
указывает ту ветвь, по которой мы будем выходить из
этого узла.
В качестве примера дерева можно указать простое дерево,
изображенное на рис. 1.2., которое рассматривал
Шеннон.
Рис.1.2. Дерево выборов для одного конкретного
примера
С выбором на каждом этапе связана некоторая неопределенность.
Рассмотрим соответствующую ей энтропию.
Первый этап имеет один узел, и энтропия выбора равна
Hx1.
Фиксация x1 определяет
узел второго этапа.
Вероятность пойти по ветви x2
из узла x1 равна условной
вероятности
P(x2Ѕ
x1) = P(x1,
x2)/ P(x1).
Энтропия, связанная с выбором одной ветви из этого
узла, есть не что иное, как условная энтропия типа
(1.3.2.) при n=2, k=2:
Hx2(Ѕ
x1) = - еx2P(x2Ѕ
x1) ln P(x2Ѕ
x1).
Усреднение по всем узлам второго этапа, как и в (1.3.3.),
дает полную энтропию выбора на втором этапе:
Hx2Ѕ
x1 = MHx2(Ѕ
x1) = еx1P(x1)
Hx2(Ѕ
x1).
Вообще энтропия выбора на k-м этапе в узле, который
определяется значениями x1,
..., xk-1, равна
Hxk (Ѕx1,
..., xk-1),
а полная энтропия k-го этапа
Hxk Ѕx1,
..., xk-1
= M Hxk
(Ѕx1,
..., xk-1).
Для примера на рис. 1.2. энтропия первого этапа
равна Hx1
= 1 бит.
Узел А имеет энтропию Hx2
(Ѕx1
= 1) = 0, а узел В - энтропию Hx2
(x1 = 2) = 2/3 log
3/2 + 1/3 log 3 = log23 - 2/3 бита.
Средняя энтропия второго этапа, очевидно, равна Hx2Ѕx1
= 1/2 Hx2
(Ѕ2) = 1/2 log23 -
1/3 бита.
Важная закономерность состоит в том, что сумма энтропий
всех этапов равна полной энтропии Hx,
которую можно вычислить без разбиения выбора на этапы.
Для указанного примера
Hx1x2 = 1/2 log
2 + 1/3 log 3 + 1/6 log 6 = 2/3 + 1/2 log23
бита,
что, действительно, совпадает с суммой Hx1
+ Hx2Ѕx1.
Это имеет место не только для данного примера.
Теорема 1.4. Энтропия обладает свойством иерархической
аддитивности:
Hx1,...,xn = Hx1
+ Hx2Ѕx1
+ Hx3Ѕx1x2
+ ... + HxnЅx1,...,xn-1(1.3.4)
Доказательство. По определению условных вероятностей
они обладают следующим свойством иерархической мультипликативности:
P(x1,...,xn) = P(x1)P(x2Ѕx1)P(x3Ѕx1x2)
...P(xnЅx1,...,xn-1)(1.3.5)
Логарифмируя (1.3.5) и учитывая определение
(1.3.1.) случайной условной энтропии, имеем
H(x1,...,xn) = H(x1)
+ H(x2Ѕx1) + H(x3Ѕx1x2)
+ ... + H(xnЅx1,...,xn-1).(1.3.6.)
Усредняя это равенство в соответствии с (1.3.3.),
получаем равенство (1.3.4.).
Доказательство закончено.
Свойство, о котором идет речь в теореме 1.4.,
является проявлением того простого принципа аддитивности,
который был принят в параграфе 1.1.
Оно является следствием выбора логарифмической функции
в (1.1.1.).
Легко понять, что из этого свойства вытекает свойство
аддитивности (1.2.8.), (1.2.9.).
В самом деле, для независимых случайных величин условная
вероятность совпадает с безусловной.
Логарифмируя эти вероятности, имеем H(x2Ѕx1)
= H(x2) и после усреднения Hx2Ѕx1
= Hx2.
Следовательно, равенство Hx1x2
= Hx1 + Hx2Ѕx1
обращается в Hx1x2
= Hx1 + Hx2.
Частное проявление свойства (1.3.4.) для двухэтапного
разбиения было принято Шенноном [1], а также Файнстейном
[1] в качестве одной из аксиом для вывода формулы
(1.2.3.), т.е. в сущности для для специализации
логарифмической меры информации.
И при других аксиоматических способах определения
количества информации свойство аддитивности в той
или иной (может быть слабой и частной) форме приходится
постулировать, чтобы выделить специальную логарифмическую
меру.
В заключение этого параграфа докажем одну теорему,
касающуюся условной энтропии.
Сформулируем сначала следующее важное вспомогательное
предложение.
Теорема 1.5. Каковы бы ни были распределения вероятностей
P(x) и Q(x),
выполняется неравенство
еx
P(x) x ln P(x)/Q(x)
і 0. (1.3.7.)
Доказательство близко к доказательству теоремы 1.2.
Оно основано на использовании неравенства (1.2.4.)
для функции f(x) = ln x.
Положим теперь x = Q(x)/P(x)
и будем проводить усреднение с весом P(x).
Тогда
Mx = еx
P(x) x Q(x)/P(x)
= еxQ(x)
= 1
и
Mf(x) = еx
P(x) x ln Q(x)/P(x).
Подстановка этих значений в (1.2.4.) дает
еx
P(x) x ln Q(x)/P(x)
Ј ln 1 = 0,
что завершает доказательство.
Теорема 1.6. Условная энтропия не может превосходить
безусловную:
HxЅh Ј
Hx.(1.3.8.)
Доказательство. Пользуясь теоремой 1.5., заменим
в ней P(x) на Р(xЅh),
Q(x) на P(x);
Тогда будем иметь
- еx
P(xЅh) x ln P(xЅh)
і еx
P(xЅh) x ln P(x).
Усреднение этого неравенства по h
с весом P(h) приводит к неравенству
- еx
P(x,h) x ln P(xЅh)
Ј -еx
P(x) x ln P(x).
что совпадает с (1.3.8.).
Доказательство закончено.
Аналогично доказывается следующая теорема.
Теорема 1.6а. При добавлении условий условная энтропия
не увеличивается:
HxЅh V Ј
HxЅV.(1.3.9.)
|