Самоорганизация и неравновесные
процессы в физике, химии и биологии
 Мысли | Доклады | Самоорганизация 
  на первую страницу НОВОСТИ | ССЫЛКИ   

Р.Л. Стратонович. Теория информации. Деревья (Великий Лес) выбора
от 09.10.06
  
Доклады


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

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


В. Васнецов. Витязь на распутье
Теория информации вместе с другими математическими дисциплинами, такими, как теория оптимальных статистических решений, теория оптимального управления, теория алгоритмов и автоматов, теория игр и другие, входит в состав теоретической кибернетики - науке об управлении. По своему основному содержанию указанные дисциплины являются самостоятельными и не связанными между собой. Но это не значит, что они совершенно оторваны одна от другой, что мосты между ними не возможны. Без сомнения, возможно и вероятно появление комбинаторных теорий, в которых используются понятия и результаты различных дисциплин и которые соединяют между собой отдельные дисциплины. Картина подобна деревьям в лесу: стволы их стоят отдельно, а кроны переплетаются. Первое время они растут независимо, а затем, переплетаясь ветвями, проникают друг в друга. Конечно, в целом высказанное утверждение об обьединении дисциплин является предположительным, однако срастание друг с другом некоторых первоначально оторванных дисциплин является уже реальностью, свершившимся фактом. Как видно из ряда работ и из предлагаемой книги, срастаются три дисциплины:
1. статистическая термодинамика как математическая теория;
2. шенноновская теория информации;
3. теория оптимальных статистических решений (вместе с ее многошаговыми (последовательностными) разновидностями - оптимальной фильтрацией и динамическим программированием...
В настоящей главе мы введем эту логарифмеческую меру количества информации и изложим ряд вытекающих из нее свойств информации, таких, например, как свойство аддитивности. Понятие количества информации тесно связано с понятием энтропии, являющейся мерой неопределенности. Приобретение информации сопровождается уменьшением неопределенности, поэтому количество информации можно измерять количеством исчезнувшей неопределенности, т.е. энтропии. В случае дискретного сообщения, т.е. дискретной случайной величины, энтропия определяется формулой Больцмана
Hx = - S P(x) ln P(x)       
где x - случайная величина, а Р(x) - ее распределение вероятностей. В данной главе большое значение придается тому, что формула является следствием ( в асимптотическом смысле) более простой формулы Хартли H = ln M. Важным результатом теории информации является тот факт, что множества реализаций энтропийно устойчивой  (это понятие определено в п. 1.5.) случайной величины можно разбить на два подмножества. Первое из них имеет исчезающе малую вероятность, и поэтому его можно отбросить. Второе подмножество содержит приблизительно еHx реализации (т.е. вариантов записи), оно часто значительно меньше полного числа реализаций. Реализации этого второго множества приближенно можно считать равновероятными. Следуя терминалогии, введенной Больцманом, эти равновероятные реализации можно называть микросостояниями...
1.1.1. Определение  энтропии в случае равновероятных возможностей
Пусть имеется М равноправных и, следовательно, равновероятных возможностей.
Например, при бросании правильной игральной кости М = 6.
Конечно, не во всех примерах формализация условий проводится так просто и определенно, как в случае игральной кости.
Мы предполагаем, тем не менее, что она проведена, что действительно осуществляется одна из М возможностей и никакая иная, что эти возможности равноправны.
Тогда имеется априорная неопределенность, прямо связанная с М (т.е. чем больше М, тем больше неопределенность).
Измеряющая ее численная величина носит название энтропии и обозначается Н:
H = f(M),

(1.1.1)


Где f(*) - некоторая возрастающая неотрицательная функция, определенная по меньшей мере для чисел натурального ряда.
При бросании кости и выяснении выпавшего числа приходит информация, количество которой обозначим I. После этого (т.е. апостериори) никакой неопределенности не остается:
Апостериорная M =1 и этому значению должна соответствовать H pr = f(1) = 0.
Количество пришедшей информации естественно измерять величиной исчезнувшей неопределенности:
I = H pr - H ps,

(1.1.2)


Здесь индекс pr  означает "априори", а ps - "апостериори".
Мы видим, что пришедшее количество информации I совпадает с первоначальной энтропией.
Также и в других случаях ( в частности для приводимой в дальнейшем формулы (1.2.3) сообщение, имеющее энтропию Н, может передавать количество информации I, равное Н.
Для определения вида функции f(*) в (1.1.1) используем вполне естественный принцип аддитивности.
В применении к игральной кости он гласит: Энтропия двух бросаний кости в два раза больше, чем энтропия одного бросания, трех бросаний - в три раза больше и т.д. В применении к другим примерам данный принцип указывает, что энтропия нескольких несвязанных систем, рукояток управления и т. п. равна сумме энтропий отдельных систем, рукояток управления и т. п.
Но число равноправных возможностей сложной системы М равно произведению числа возможностей m каждой из подсистем (простых по отношению к сложной).
При двух бросаниях игральной кости число различных пар (x1,x2) где x1 принимает одно из шести значений и x2 - также одно из шести значений) - возможностей равно 36=62.
Применяя формулу (1.1.1) для этого числа, получаем энтропию f(6n).
Согласно принципу аддитивности находим
f(6n) = n f(6),
При других m > 1 эта формула имела бы вид
f(mn) = n f(m),

(1.1.3)


Обозначая x = mn, имеем n = ln x/ ln m  и из (1.1.3) получаем
f(x) = K ln x,

(1.1.4)


где K = f(m)/ln m - положительная константа, не зависящая от х.
Она связана с выбором единиц информации.
Итак, вид функции f(*) определен с точностью до выбора единиц измерения.
Легко проверить, что отмеченное ранее условие f(1) = 0 действительно выполняется.
Впервые логарифмическую меру информации ввел Хартли [1], поэтому величину H = K lnM называют хартлиевским количеством информации...
1.1.2. Энтропия в случае неравновероятных возможностей и ее свойства
Пусть теперь вероятности различных возможностей (реализаций) не равны друг другу.
Если, как и раньше, число возможностей равно M, можно рассматривать случайную величину x, принимающую одно из М значений.
Взяв в качестве x номер возможности, получим, что эти возможности равны  1, ..., M.
Вероятности P(x) этих значений, неотрицательны и подчинены условию нормировки:
S P(x) =1.
Если применить формально равенство (1.1.8) к этому случаю, то получим, что каждому значению x соответствует, вообще говоря своя энтропия
H(x)   = -ln P(x).

(1.2.1)


Тем самым мы приписываем определенное значение энтропии каждой реализации величины x.
Поскольку x - случайная величина, то эту энтропию можно рассматривать как случайную величину.
Как и в п. 1.1, апостериорная энтропия, имеющаяся после выяснения реализации x, равна нулю.
Поэтому информация, получаемая при выяснении реализаций, численно равна первоначальной энтропии
I(x)   =  H(x)   = -ln P(x).

(1.2.2)


Она, как и H(x), оказывается зависящей от вида реализации сообщения (от значения x ), т.е. является случайной.
Из этой формулы видно, что информация и энтропия велики, когда априорная вероятность данной реализации мала, и наоборот.
Это вполне соответствует интуитивным представлениям.
Пример. Допустим, что нам интересно знать, сдал или не сдал экзамен данный студент. Примем следующие вероятности этих двух событий:
P(сдал) = 7/8,  P(не сдал) =1/8.
Отсюда видно, что этот студент является довольно сильным. Если нам сообщили, что он сдал экзамен, мы вправе сказать: "Ваше сообщение мне мало что дало, я и без этого предполагал, что он сдал".
Количественно по формуле (1.2.2) информации этого сообщения равна
I(сдал) = log2(8/7) = 0.193 бита.
Если нам сообщили, что не сдал, мы скажем:  - "Неужели?" и почувствуем, что в большей степени обогатились знаниями.
Количественно информации такого сообщения равна
I(не сдал) = log2(8) = 3 бита.
В теории, однако, большую роль играет не случайная энтропия (соответственно информация) (1.2.1), (1.2.2), а усредненная энтропия, определенная формулой
Hx   = MH(x) =   - S P(x)  ln P(x).

(1.2.3)


Будем называть ее больцмановской энтропией или больцмановской информацией.
В приведенном выше примере усреднение по обоим сообщениям дает
Ix   = Hx   = 7/8 * 0.193  + 3/8 = 0.544 бита...
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.Рис.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.Рис.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.).
Доказательство закончено.
Р.Л. Стратонович. Теория информации. М.: Сов. радио, 1975, 424с.
http://www.twirpx.com/file/34571/
Р.Л. Стратонович. Теория информации
http://kirsoft.com.ru/freedom/KSNews_186.htm
Руслан Стратонович. Определение ценности информации
http://sinsam.kirsoft.com.ru/KSNews_89.htm

  


СТАТИСТИКА