Книги по системному анализу

Системный анализ

«Адаптивное управление сложными системами на основе теории распознавания образов»

В. С. Симанков, Е. В. Луценко

Оглавление    
Глава 4, «Формальная постановка задачи» Глава 4, «Информация как мера снятия неопределенности»

Глава 4: Теория информации и ее ключевые понятия

Термин «информация» произошел от латинского слова informatio, которое означает разъяснение, осведомление [351]. Данное понятие является одним из ключевых понятий кибернетики и понимается как совокупность каких-либо сведений или данных.

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

Современная наука о свойствах информации и закономерностях информационных процессов называется теорией информации. Содержание понятия «информация» можно раскрыть на примере двух исторически первых подходов к измерению количества информации: подходов Хартли и Шеннона. Первый из них основан на теории множеств и комбинаторике, а второй — на теории вероятностей.

В основе всей теории информации лежит открытие, сделанное Р. Хартли в 1928 году, и состоящее в том, что информация допускает количественную оценку [374]. Завершенный и полный вид этой теории придал в 1948 году К. Шеннон [390]. Большой вклад в дальнейшее развитие и обобщение теории информации внесли отечественные ученые А.Н. Колмогоров, А.А. Харкевич, Р.Л. Стратанович [373]. Недавно германские исследователи советских архивов сообщили о том, что теория, известная сегодня как теория Шеннона, была создана А.Н.Колмогоровым еще в 1938 году, но была засекречена, так как использовалась в военных разработках.

Подход Р. Хартли

Подход Р. Хартли основан на весьма фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

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

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

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

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

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации мы получаем, узнав о том, какой выбран элемент.

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

Рассмотрим множество, состоящее из чисел в двоичной системе счисления длиной I двоичных разрядов. При этом каждый из разрядов может принимать значения только 0 и 1 (табл. 4.1).

Таблица 4.1 — К выводу формулы количества информации по Р.Хартли

Количество двоичных разрядов (i) Количество состояний, которое можно пронумеровать i-разрядными двоичными числами (N) Основание системы счисления
10 16 2
1 2 0
1
0
1
0
1
2 4 0
1
2
3
0
1
2
3
00
01
10
11
3 8 0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
4 16 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
... ...      
i 2i      

Очевидно, количество этих чисел (элементов) в множестве равно:

N = 2i.

Рассмотрим процесс выбора чисел из рассмотренного множества. До выбора вероятность выбрать любое число одинакова. Существует объективная неопределенность в вопросе о том, какое число будет выбрано. Эта неопределенность тем больше, чем больше N — количество чисел в множестве, а чисел тем больше — чем больше разрядность i этих чисел.

Примем, что выбор одного числа дает нам следующее количество информации:

i = Log2(N).

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

Это выражение и представляет собой формулу Хартли для количества информации. Отметим, что оно полностью совпадает с выражением для энтропии (по Эшби), которая рассматривалась им как количественная мера степени неопределенности состояния системы.

При увеличении длины числа в два раза количество информации в нем также должно возрасти в два раза, несмотря на то, что количество чисел в множестве возрастает при этом по показательному закону (в квадрате, если числа двоичные), т.е. если

N2 = (N1)2,

то

I2 = 2⋅I1,

F(N1⋅N1) = F(N1) + F(N1).

Это невозможно, если количество информации выражается линейной функцией от количества элементов в множестве. Но известна функция, обладающая именно таким свойством: это Log:

Log2(N2) = Log2(N1)2 = 2⋅Log2(N1).

Это второе требование называется требованием аддитивности.

Таким образом, логарифмическая мера информации, предложенная Хартли, одновременно удовлетворяет условиям монотонности и аддитивности. Сам Хартли пришел к своей мере на основе эвристических соображений, подобных только что изложенным, но в настоящее время строго доказано, что логарифмическая мера для количества информации однозначно следует из этих двух постулированных им условий [391].

Минимальное количество информации получается при выборе одного из двух равновероятных вариантов. Это количество информации принято за единицу измерения и называется «бит».

Подход К. Шеннона

Клод Шеннон основывается на теоретико —вероятностном подходе. Это связано с тем, что исторически шенноновская теория информации выросла из потребностей теории связи, имеющей дело со статистическими характеристиками передаваемых сообщений и каналов связи.

Пусть существует некоторое конечное множество событий (состояний системы): X = {x1, x2, ..., xN}, которые могут наступать с вероятностями: p(xi), соответственно, причем множество вероятностей удовлетворяет естественному условию нормировки:

∑p(xi) = 1

Исходное множество событий характеризуется некоторой неопределенностью, т.е. энтропией Хартли, зависящей, как мы видели выше, только от мощности множества. Но Шеннон обобщает это понятие, учитывая, что различные события в общем случае не равновероятны. Например, неопределенность системы событий: {монета упала «орлом», монета упала «решкой»}, значительно выше, чем неопределенность событий: {монета упала «орлом», монета упала «ребром»}, так как в первом случае варианты равновероятны, а во втором случае вероятности вариантов сильно отличаются:

  H(X) = -∑p(xi)⋅Log2(p(xi)) (4.1)

Если измерять количество информации изменением степени неопределенности, то шенноновское количество информации численно совпадает с энтропией исходного множества:

  I(X) = -∑p(xi)⋅Log2(p(xi)) (4.2)

Связь формул К. Шеннона И Р. Хартли

Следуя [391], приведем вывод выражения Шеннона (4.2) непосредственно из выражения Хартли для количества информации: I = Log2(N).

Пусть события исходного множества мощности N равновероятны:

p(xi) = 1/N,

тогда учитывая, что

Log(1/N) = Log(1)⋅Log(N) = Log(N),
∑1/N = 1

непосредственно из формулы Хартли получаем

I(X) = -∑1/N⋅Log2(1/N) = -∑p(xi)⋅Log2(p(xi)).

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

Сравнение подходов Р. Хартли и К. Шеннона

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

В теории Шеннона существенным образом используется статистика, причем предполагается, что случайные события (состояния системы) распределены по нормальному закону.

Таким образом, различие между подходами Хартли и Шеннона к построению теории информации соответствует различию между непараметрическими и параметрическими методами в статистике.

Если говорить более конкретно, то очевидно, что мера Шеннона асимптотически переходит в меру Хартли при условии, что вероятности всех событий (состояний) равны.

В статистике доказано [273, 391] фундаментальное свойство энтропии случайного процесса, состоящее в том, что при условии нормальности распределения и достаточно больших выборках все множество событий можно разделить на две основные группы:

  • высоковероятные события (считающиеся заслуживающими изучения);
  • маловероятные события (считаются не заслуживающими особого внимания).

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

Оглавление    
Глава 4, «Формальная постановка задачи» Глава 4, «Информация как мера снятия неопределенности»