«Системный анализ и проектирование»

Е. Н. Живицкая

↑	Оглавление
←	Лекция 9, «Сигналы в системах»	Лекция 11, «О результатах теории информации»	→

Лекция 10: Энтропия и количество информации

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

Понятие неопределенности

Первым специфическим понятием теории информации является понятие неопределенности случайного объекта, для которого удалось ввести количественную меру, названную энтропией. Начнем с простейшего примера — со случайного события. Пусть, например, некоторое событие может произойти с вероятностью 0,99 и не произойти с вероятностью 0,01, а другое событие имеет вероятности соответственно 0,5 и 0,5. Очевидно, что в первом случае результатом опыта «почти наверняка» является наступление события, во втором же случае неопределенность исхода так велика, что от прогноза разумнее воздержаться.

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

Энтропия и ее свойства

Примем (пока без обоснования) в качестве меры неопределенности случайного объекта А с конечным множеством возможных состояний А1,...,Аn с соответствующими вероятностями P₁,P₂...P_n величину

H(A) = H({p_i}) = -∑ p_i⋅log(p_i)

которую и называют энтропией случайного объекта А (или распределения { }. Убедимся, что этот функционал обладает свойствами, которые вполне естественны для меры неопределенности.

1. Н(p₁...p_n)=0 в том и только в том случае, когда какое-нибудь одно из {p_i } равно единице (а остальные — нули). Это соответствует случаю, когда исход опыта может быть предсказан с полной достоверностью, т.е. когда отсутствует всякая неопределенность. Во всех других случаях энтропия положительна. Это свойство проверяется непосредственно.
2. Н(p₁...p_n) достигает наибольшего значения при p₁=...p_n=1/n т.е. в случае максимальной неопределенности. Действительно, вариация Н по p_i при условии ∑p_i = 1 дает p_i = const = 1/n.
3. Если А и В — независимые случайные объекты, то H(A∩B) = H({p_iq_k}) = H({p_i}) + H({q_k}) = H(A) + H(B). Это свойство проверяется непосредственно.
4. Если А и В — зависимые случайные объекты, то H(A∩B) = H(A) + H(B/A) = H(B) + H(A/B), где условная энтропия H(А/В) определяется как математическое ожидание энтропии условного распределения. Это свойство проверяется непосредственно.
5. Имеет место неравенство Н(А) > Н(А/В), что согласуется с интуитивным предположением о том, что знание состояния объекта В может только уменьшить неопределенность объекта А, а если они независимы, то оставит ее неизменной.

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

Дифференциальная энтропия

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

-∑p_k⋅log(p_k) → ∫p(x)⋅log(p(x))dx

не приводит к нужному результату: плотность p(x) является размерной величиной (размерность плотности p(x) обратно пропорциональна x а логарифм размерной величины не имеет смысла. Однако положение можно исправить, умножив p(x) под знаком логарифма на величину К, имеющую туже размерность, что и величина х:

-∑p_k⋅log(p_k) → ∫p(x)⋅log(K⋅p(x))dx

Теперь величину К можно принять равной единице измерения х, что приводит к функционалу

h(X) = -∫p(x)⋅log(p(x))dx,

который получил название «дифференциальной энтропии». Это аналог энтропии дискретной величины, но аналог условный, относительный: ведь единица измерения произвольна. Запись (3) означает, что мы как бы сравниваем неопределенность случайной величины, имеющей плотность p(x), с неопределенностью случайной величины, равномерно распределенной в единичном интервале. Поэтому величина h(X) в отличие от Н(Х) может быть не только положительной. Кроме того, h(X) изменяется при нелинейных преобразованиях шкалы х, что в дискретном случае не играет роли. Остальные свойства h(X) аналогичны свойствам Н(Х), что делает дифференциальную энтропию очень полезной мерой.

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

Фундаментальное свойство энтропии случайного процесса

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

Назовем каждое такое состояние «символом», множество возможных состояний — «алфавитом», их число m — «объемом алфавита». Число возможных последовательностей длины n, очевидно, равно mn. Появление конкретной последовательности можно рассматривать как реализацию одного из mn возможных событий. Зная вероятности символов и условные вероятности появление следующего символа, если известен предыдущий (в случае их зависимости), можно вычислить вероятность P(C) для каждой последовательности С. Тогда энтропия множества {C}, по определению, равна

H_n = -∑P(C)⋅log(P(C)).

На множестве {C} можно задать любую числовую функцию f_n(C), которая, очевидно, является случайной величиной. Определим f_n(C) c помощью соотношения f_n(C) = -[1/n]⋅logP(C).

Математическое ожидание этой функции

M{f_n(C)} = ∑P(C)⋅f_n(C) = -[1/n]∑P(C)⋅log(P(C)),
M{-[1/n]⋅log(P(C))} = H_n/n
lim(M){-[1/n]⋅log(P(C))} = H

Это соотношение является одним из проявлений более общего свойства дискретных эргодических процессов. Оказывается, что не только математическое ожидание величины f_n(C) при n стремящемся к бесконечности имеет своим пределом H, но и сама эта величина f_n(C) стремится к H при n стремящемся к бесконечности. Другими словами, как бы малы ни были e > 0 и s > 0, при достаточно большом n справедливо неравенство

P{|[1/n]⋅log(P(C))+H| > ε} < δ

т.е. близость f_n(C) к H при больших n является почти достоверным событием.

Для большей наглядности сформулированное фундаментальное свойство случайных процессов обычно излагают следующим образом. Для любых заданных e > 0 и s > 0 можно найти такое no, что реализация любой длины n > no распадаются на два класса:

1. группа реализаций, вероятность P(C) которых удовлетворяет неравенству |[1/n]⋅log(P(C))+H| < ε
2. группа реализаций, вероятности которых этому неравенству не удовлетворяют.

Cуммарные вероятности этих групп равны соответственно 1-s и s, то первая группа называется «высоковероятной», а вторая — «маловероятной».

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

1. независимо от того, каковы вероятности символов и каковы статистические связи между ними, все реализации высоковероятной группы приблизительно равновероятны. Это следствие, в частности, означает, что при известной вероятности P(C) одной из реализаций высоковероятной группы можно оценить число N₁ реализаций в этой группе: N₁ = 1 / P(C).
2. Энтропия H_n с высокой точностью равна логарифму числа реализаций в высоковероятной группе: H_n = n * H = log N₁
3. При больших n высоковероятная группа обычно охватывает лишь ничтожную долю всех возможных реализаций (за исключением случая равновероятных и независимых символов, когда все реализации равновероятны и и H = log m).

Действительно, из соотношения (9) имеем

N₁ = α^nH

Число N всех возможных реализаций есть

N = mⁿ = σ^n⋅log(m)

Доля реализаций высоковероятной группы в общем числе реализаций выражается формулой

N₁/N = σ^{-n⋅log(m-H)}

и при H < logm эта доля неограниченно убывает с ростом n. Например, если a = 2, n = 100, H = 2,75, m = 8, то

N₁/N = 2^-25 = (3⋅10⁷)^-1

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

Строгое доказательство фундаментального свойства эргодических процессов здесь не приводится. Однако следует отметить, что в простейшем случае независимости символов это свойство является следствием закона больших чисел. Действительно, закон больших чисел утверждает, что с вероятностью, близкой к 1, в длиной реализации i-й символ, имеющий вероятность p_i встретится примерно np_i раз. Следовательно вероятность реализации высоковероятной группы есть

P(C) = ∏{p_i^n⋅P_i}
-log(P(C)) = -n⋅∑p_i⋅log(p_i) = n⋅N

что и доказывает справедливость фундаментального свойства в этом случае.

Подведем итог

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

Количество информации

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

Количество информации как мера снятой неопределенности

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

1. полезный (передаваемый) сигнал является последовательностью статистически независимых символов с вероятностями p(x_i),i = 1,m ;
2. принимаемый сигнал является последовательностью символов Y_k того же алфавита;
3. если шумы (искажения) отсутствуют, то принимаемый сигнал совпадает с отправленным Y_k=X_k ;
4. если шум имеется, то его действие приводит к тому, что данный символ либо остается прежним (i-м), либо подменен любым другим (k-м) с вероятностью p(y_k/x_i) ;
5. искажение данного символа является событием статистически независимым от того, что произошло с предыдущим символом.

Итак, до получения очередного символа ситуация характеризуется неопределенностью того, какой символ будет отправлен, т.е. априорной энтропией Н(Х). После получения символа y_k неопределенность относительно того, какой символ был отправлен, меняется: в случае отсутствия шума она вообще исчезает (апостериорная энтропия равна нулю, поскольку точно известно, что был передан символ y_k=x_i), а при наличии шума мы не можем быть уверены, что принятый символ и есть переданный, т.е. возникает неопределенность, характеризуемая апостериорной энтропией H(X/y_k)=H({p(x_i/y_k)})>0.

В среднем после получения очередного символа энтропия H(X/Y)=M_y{H(X/Y_k)}

Определим теперь количество информации как меру снятой неопределенности: числовое значение количества информации о некотором объекте равно разности априорной и апостериорной энтропии этого объекта, т.е. I(X,Y) = H(X)-H(X/Y). (1)

Используя свойство 2 энтропии, легко получить, что I(X,Y) = H(Y) — H(Y/X) (2)

В явной форме равенство (1) запишется так:

I(X,Y) = H(X)-H(X/Y) = -∑p(x_i)⋅(p(x_i))+∑p(y_k)⋅∑p(x_i/y_k)⋅log(p(x_i/y_k)) =
=-∑∑p(x_i,y_k)⋅log(p(x_i))+∑∑p(x_i,y_k)⋅log(p(x_i/y_k)) =
= ∑∑p(x_i,y_k)⋅log{p(x_i,y_k)/p(x_i)} (3)

а для равенства (2) имеем:

I(X,Y) = ∑∑p(x_i,y_k)⋅log{p(y_k/x_i)/p(y_k)} (4)

Количество информации как мера соответствия случайных процессов

Представленным формулам легко придать полную симметричность: умножив и разделив логарифмируемое выражение в (3) на p(y_k), а в (4) на p(x_i) сразу получим, что

I(X,Y) = ∑∑p(x_i,y_k)⋅log{p(y_k/x_i)/[p(x_i)⋅p(y_k)]}

Эту симметрию можно интерпретировать так: «количество информации в объекте Х об объекте Y равно количеству информации в объекте Y об объекте Х. Таким образом, количество информации является не характеристикой одного из объектов, а характеристикой их связи, соответствия между их состояниями. Подчеркивая это, можно сформулировать еще одно определение: «среднее количество информации, вычисляемое по формуле (5), есть мера соответствия двух случайных объектов».

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

Формула (5) обобщается на непрерывные случайные величины, если в отношении (1) и (2) вместо Н подставить дифференциальную энтропию h; при этом исчезает зависимость от стандарта К и, значит, количество информации в непрерывном случае является столь же безотносительным к единицам измерения, как и в дискретном:

I(X,Y) = ∫∫p(x,y)⋅log{p(y/x)/[p(x)⋅p(y)]}dxdy

где р(x), p(y) и p(x,y) — соответствующие плотности вероятностей.

Свойства количества информации

Отметим некоторые важные свойства количества информации.

1. Количество информации в случайном объекте Х относительно объекта Y равно количеству информации в Y относительно Х: I(X,Y) = I(Y,X)
2. Количество информации неотрицательно: I(X,Y) > 0. Это можно доказать по-разному. Например, варьированием p(x,y) при фиксированных p(x) и p(y) можно показать, что минимум I, равный нулю, достигается при p(x,y) = p(x) p(y).
3. Для дискретных Х справедливо равенство I(X,X) = H(X).
4. Преобразование y (.) одной случайной величины не может увеличить содержание в ней информации о другой, связанной с ней, величине: I[y (X),Y] < I(X,Y) (9)
5. Для независимых пар величин количество информации аддитивно: I({X_i,Y_i}) = ∑ I(X_i,Y_i)

Единицы измерения энтропии и количества информации

Рассмотрим теперь вопрос о единицах измерения количества информации и энтропии. Из определений I и H следует их безразмерность, а из линейности их связи — одинаковость их единиц. Поэтому будем для определенности говорить об энтропии. Начнем с дискретного случая. За единицу энтропии примем неопределенность случайного объекта, такого, что

H(X) = -∑p_i⋅log(p_i) = 1

Легко установить, что для однозначного определения единицы измерения энтропии необходимо конкретизировать число m состояний объекта и основание логарифма. Возьмем для определенности наименьшее число возможных состояний, при котором объект еще остается случайным, т.е. m=2, и в качестве основания логарифма также возьмем число 2. Тогда из равенства

-p₁⋅log₂(p₂)-p₂⋅log₂(p₂) = 1

вытекает, что p₁=p₂=1/2. Следовательно, единицей неопределенности служит энтропия объекта с двумя равновероятными состояниями. Эта единица получила название «бит». Бросание монеты дает количество информации в один бит. Другая единица «нит» получается, если использовать натуральные логарифмы. Обычно она употребляется для непрерывных величин.

Количество информации в индивидуальных событиях

Остановимся еще на одном важном моменте. До сих пор речь шла о среднем количестве информации, приходящемся на пару состояний (x_i,y_k) объектов X и Y. Эта характеристика естественна для рассмотрения особенностей стационарно функционирующих систем, когда в процессе функционирования принимают участие все возможные пары (x_i,y_k). Однако в ряде практических случаев оказывается необходимым рассмотреть информационное описание конкретной пары состояний, оценить содержание информации в конкретной реализации сигнала. Тот факт, что некоторые сигналы несут информации намного больше, чем другие, виден на примере того, как отбираются новости средствами массовой информации (о рождении шестерых близнецов сообщают практически все газеты мира, а о рождении двойни не пишут).

Допуская существование количественной меры информации (x_i,y_k), в конкретной паре (x_i,y_k) естественно потребовать, чтобы индивидуальное и среднее количество информации удовлетворяли соотношению

I(X,Y) - M{i(x_i,y_k)} = ∑p(x_i,y_k)⋅i(x_i,y_k) (5)

Хотя равенство имеет место не только при равенстве всех слагаемых, сравнение формул (5) и, например, (4) наталкивает на мысль, что мерой индивидуальной информации в дискретном случае может служить величина

i(x_i,y_k) = log{p(x_i/y_k)/p(x_i)} = log{p(y_k/x_i)/p(y_k)} = log{p(x_i,y_k)/[p(x_i)⋅p(y_k)]}. (6)

а в непрерывном — величина i(x,y) = ln{p(x/y) / p(x)} = ln{{p(y/x) / p(y)} = ln{p(x,y) / p(x)p(y)}, (7)

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

Пример

Пусть по выборке (т.е. совокупности наблюдений x=x1...xn требуется отдать предпочтение одной из конкурирующих гипотез (H или H₁), если известны распределения наблюдений при каждой из них, т.е. p(x/H₀) и p(x/H₁). Как обработать выборку? Из теории известно, что никакая обработка не может увеличить количество информации, содержащегося в выборке x (см. формулу (9). Следовательно, выборке x следует поставить в соответствие число, содержащее всю полезную информацию, т.е. обработать выборку без потерь. Возникает мысль о том, чтобы вычислить индивидуальное количество информации в выборке x о каждой из гипотез и сравнить их:

σi = i(x,H₁)-i(x,H₀) = ln{p(x/H₁)/p(x)}-ln{p(x/H₀)/p(x)} = ln{p(x/H₁)/p(x,H₀)} (15)

Какой из гипотез теперь отдать предпочтение зависит теперь от величины 7d 0i и от того, какой порог сравнения мы назначим. Оказывается, что мы получили статистическую процедуру, оптимальность которой специально доказывается в математической статистике, — именно к этому сводится содержание фундаментальной леммы Неймана-Пирсона. Данный пример иллюстрирует эвристическую силу теоретико-информационных представлений.

Подведем итог

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

↑	Оглавление
←	Лекция 9, «Сигналы в системах»	Лекция 11, «О результатах теории информации»	→