Лекция 3. Математические модели для оценки информативности источников сообщений
Курс “Теория информации и кодирования”

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

Подход ТИК к оценке информативности
Информативность дискретного источника. Безусловная энтропия
Учет предыстории. Условная энтропия
Информативность непрерывного источника


3.1 Подход ТИК к оценке информативности

Направления измерения информации
Используются три основных подхода к измерению (определению количества) информации (рис.3.1):
  • структурный (информационная емкость сообщений);
  • статистический (информативность сообщений);
  • семантический (смысл - содержательность, целесообразность и т.п.).

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

Информативность и неопределенность (энтропия)
Подход, на который опирается ТИК при оценке информативности состоит в следующем (рис.3.2):
  • любое сообщение рассматривается как последовательность элементов. С точки зрения условного наблюдателя перед поступлением от Источника каждого такого элемента существует неопределенность — каким будет его значение. Величина этой неопределенности зависит от объема алфавита N и распределения вероятностей появления элементов;
  • для расчета величины неопределенности используется функция энтропии H (бит/знак). Значение энтропии зависит от того, рассматривается ли каждый знак безотносительно к прочим (безусловная энтропия) или с учетом предыстории его появления (условная энтропия);
  • при поступлении конкретного элемента исходная неопределенность относительно его значения устраняется (снимается). При этом количество поступившей от Источника информации численно равно энтропии: I=H (бит/знак);
  • количество информации в сообщении определяется как сумма информативностей всех его элементов.

Особенности дискретных и непрерывных источников
Приведенное выше описание является наиболее общим. Уточним особенности его применения для дискретных и непрерывных источников сообщений (рис.3.3):
  • элементами дискретного сообщения являются знаки. Их полный набор составляет алфавит объемом N, в котором знаки могут задаваться своими номерами I;
  • неопределенность появления конкретных разновидностей знаков задается дискретным распределением вероятностей. В простейшем случае знаки независимы, а их вероятности pi, соответственно, безусловны и образуют строку. Если учитывается предыстория знаков, то источник описывается матрицей условных вероятностей pi/j (при глубине истории на один знак) или наборами таких матриц (при большей глубине истории);
  • элементами непрерывного сообщения могут считаться отсчеты его амплитуды ui, зафиксированные с достаточно высокой частотой дискретизации (согласно правилу Найквиста-Котельникова). Как мы помним, согласно теореме Котельникова такая последовательность отсчетов эквивалентна исходной непрерывной зависимости u(t). При этом значения самих амплитуд ui также являются непрерывными и характеризуются непрерывными распределениями плотности вероятностей (последние опять-таки могут быть безусловными или условными);
  • как видно, математический аппарат для дискретных и непрерывных сообщений должен иметь существенные особенности. Поэтому мы будем рассматривать оба эти случая отдельно. Важно подчеркнуть, что для практики случай дискретных сообщений более важен — хотя бы потому, что непрерывные сообщения в современной технической среде представлены в оцифрованном виде. Этот случай будет для нас основным. Однако вариант непрерывных сообщений имеет качественные особенности, учет которых нам будет необходим, в частности, при рассмотрении передачи сигналов.

Контрольные вопросы
1) Назовите основные подходы к определению количества информации. Поясните аналогию с заполнением упаковки.
2) Почему структурный и статистический подходы к измерению информации широко используются, а семантический подход применяется в исключительных случаях.
3) Поясните связь понятий неопределенности и информации с позиций ТИК.
4) Что такое безусловная и условная энтропия.
5) Как с позиций ТИК связаны информативность отдельных знаков и количество информации в сообщении.
6) Что представляют собой элементы дискретных и непрерывных сообщений. Приведите примеры.
7) Как различаются способы вероятностного описания дискретного и непрерывного источников сообщений.


3.2 Информативность дискретного источника. Безусловная энтропия

Формула безусловной энтропии
Математическим выражением неопределенности служит функция информационной энтропии. Рассмотрим наиболее простой случай безусловной энтропии, расчет которой базируется на безусловных вероятностях появления знаков (рис.3.4):
  • формула для расчета безусловной информационной энтропии (в дальнейшем просто энтропии) была предложена основоположником ТИК Клодом Шенноном и имеет вид:
    Н= - Σ pi log2 pi (i = 1...N) (3.1)
    Здесь pi — вероятность появления i-й разновидности знака из алфавита объемом N.
    Шеннон строго обосновал уникальность такой функции для оценки информативности источника дискретных сообщений;
  • использование двоичного логарифма позволяет получить размерность информационной энтропии в битах на знак, что соответствует принятым единицам измерения;
  • удобно интерпретировать значение Н как среднюю величину неопределенностей появления всех знаков, каждая из которых вычисляется как
    Нi = - log2pi (3.2)
    Действительно, согласно (3.1), величина Н вычисляется как средневзвешенное значение Нi с весовыми коэффициентами в виде вероятностей pi .

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

Информативности отдельных знаков
Исходя из того, что информативность знака соответствует снимаемой им неопределенности, можно рассматривать величину Нi как меру такой информативности. При этом формула (3.2) отвечает понятным для нас требованиям (рис.3.5):
  • знак «-» в формуле (3.2) гарантирует неотрицательность расчетной величины информативности, поскольку логарифмы вероятностей неположительны (сами вероятности не превышают единицы);
  • c уменьшением вероятности знака расчетная величина его информативности растет. Например, вероятностям 1/2, 1/4 и 1/8 будут соответствовать значения информативности 1, 2 и 3 бит/знак;
  • примение логарифма позволяет согласовать статистический и структурный подходы. Так в случае, когда вероятности всех N знаков алфавита одинаковы (при этом pi=1/N), приведенная формула дает значение информативности Нi = - log2(1/N) = log2N. Здесь значение информативности знаков совпадает с их информационной емкостью.

Свойства функции энтропии
Представление об особенностях функции безусловной энтропии дает рис. 3.6, где отображено влияние распределения вероятностей знаков для разных объемов алфавита.
Как видно по рисунку, значение энтропии растет с увеличением объема алфавита и убывает с ростом неравномерности распределения (что интуитивно понятно).
Действительно, величину безусловной энтропии можно интерпретировать также как меру разнообразия знаков в сообщениях. Такое разнообразие имеет как бы два измерения:
  • объем алфавита источника N. Чем больше разновидностей знаков, тем их разнообразие выше;
  • характер распределения вероятностей pi. Чем выше неравномерность распределения, тем разнообразие меньше (одни знаки появляются чаще других).

Свойства функции энтропии более полно отображены на рис. 3.7.
Эти свойства также интуитивно очевидны:
  • значение Н неотрицательно (неопределенность либо присутствует и тогда Н>0, либо ее нет и в этом случае Н=0);
  • минимальное значение Н=0 соответствует случаю, когда для одного j-го вида знаков pj =1, а для всех остальных pi≠j =0 (если постоянно появляется знак только одного вида, остается предполагать, что он будет появляться и дальше);
  • максимальное значение Н достигается для одинаковых вероятностей pi (действительно, в этом случае ни один из вариантов не имеет преимущества и существует «полная неопределенность»). При этом все pi =1/n, из чего следует max(H)=log2n.

Контрольные вопросы
1) Запишите формулу безусловной энтропии. Поясните ее связь с формулой неопределенности появления отдельных знаков
2) Поясните, как в модели ТИК величина безусловной энтропии используется для подсчета количества информации
3) Как в общем зависит величина энтропии от объема алфавита и распределения вероятностей знаков в сообщениях
4) Назовите свойства функции безусловной энтропии. Каково ее максимальное значение, например, при объеме алфавита источника n=32
5) При каких условиях энтропия в зависимости от распределения вероятностей знаков меняется слабо и при каких сильно (используйте данные рис.3.6 и 3.7)


3.3 Учет предыстории. Условная энтропия

Особенности условной энтропии
В отличие от безусловной энтропии условная характеризует неопределенность появления знаков сообщения с учетом их предыстории (рис.3.8):
  • соседние знаки в сообщениях могут быть связаны (например, в пределах слов в тексте). При этом такая связь является не жесткой, а вероятностной. Так, если в русскоязычном тексте слово начинается с буквосочетания «чт», то следующей буквой вероятно будет «o» (слово «что»), однако, возможна и «е» («чтец»), и «у» («чту»). Как видно, учет предыстории позволяет уменьшить неопределенность, но она все-таки сохраняется;
  • величина условной неопределенности (энтропии) зависит от глубины учета предыстории. В нашем примере если учтены две предыдущих буквы «чт», неопределенность будет существенно ниже, чем когда известна только одна предыдущая «т», а та в свою очередь меньше, чем если предыстория вообще не учитывается (например, после согласной буквы «т» значительно возрастает вероятность следования гласных букв, а повтор буквы «т» в русскоязычном тексте очень маловероятен);
  • в зависимости от глубины предыстории k будем обозначать условную энтропию Н(k), в этом контексте безусловная энтропия обозначается как Н(0). Общая закономерность состоит в том, что с ростом k величина условной энтропии как минимум не убывает:
    Н(0) >= Н(1) >= Н(2) ... (3.3)

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

Расчет условной энтропии на основе условных вероятностей
Вычисление условной энтропии выполняется с учетом условных вероятностей появления знаков (рис.3.9):
  • в частности, если известно, что очередному знаку предшествовал знак j-го типа (глубина истории k=1), то соответствующая «частная» энтропия (относительно данного условия) может быть вычислена по формуле:
    Н(1)j= - Σ pi/j log2 pi/j (j = 1...N) (3.4)
    где pi/j – условные вероятности появления всех i-х знаков после заданного j-го;
  • теперь, усредняя значения Н(1)j с учетом “удельных весов” (вероятностей) знаков, получим значение условной энтропии с глубиной истории в один шаг k=1:
    Н(1) = - Σ pj Σ pi/j log2 pi/j (i = 1...N, j = 1...N) (3.5)
  • следующая формула позволяет вычислить значение условной энтропии с глубиной истории k=2:
    Н(2) = - Σ pl Σ pj Σ pi/j,l log2pi/j,l (i = 1...N, j = 1...N, l = 1...N ) (3.6).
    Аналогично вычисляются значения энтропии и при больших значениях k;
  • Отметим, что каждый шаг увеличения глубины истории означает рост мерности таблицы условных вероятностей. В частности, при k=1 мы будем работать с двумерной таблицей размером nxn=n2, при k=2 - с трехмерной размером n3 и т.д. (рис.3.9). При этом каждое значение условной вероятности нужно подсчитывать. Очевидно, что рост громоздкости на практике ограничивает глубину учета предыстории знаков.

Контрольные вопросы
1) Покажите на примере, что при учете предыстории появления знаков в тексте величина неопределенности для каждого следующего знака может уменьшаться.
2) Что такое условная энтропия. Приведите пример условной энтропии с различной глубиной истории при анализе текста
3) Приведите и поясните формулу «частной» энтропии относительно знака j-го типа, условной энтропии для случая глубины истории k=1 и для случая глубины истории k=2
4) Как определить количество условных вероятностей, необходимых для подсчета условной энтропии при глубине истории 1, 2, 3 и т.д.
5) Какие моменты ограничивают эффективность практического применения расчета условной энтропии для оценки информационной неопределенности знаков в сообщениях.


3.4 Информативность непрерывного источника

Полная энтропия непрерывного источника
Рассмотрим энтропию непрерывного источника по аналогии с дискретным — рис.3.10:
  • пусть функция плотности вероятности f(u) квантована с шагом Δu. Тогда площадь столбца Δu f(ui) соответствует вероятности pi и формула энтропии по аналогии примет вид:
    HΔu (U) = - Σ [Δu f(ui)] log2 [Δu f(ui)] (3.7);
  • чтобы корректно перейти от дискретных величин к непрерывным, выполняется предельный переход при Δu →0. Описание вывода вынесено в необязательное дополнение *. Здесь же приведем конечный результат:
    H(U) = - ∫ f(u) log2 f(u) du - log2 Δu (3.8)
    Это и есть формула энтропии непрерывной величины, которую принято называть полной;
  • первое слагаемое похоже на формулу энтропии дискретного источника, в которой дискретные вероятности pi заменены непрерывной функцией плотности вероятности f(u), а знак суммы — интегралом. При этом интеграл определенный (в пределах от Umin до Umax) и имеет конечное значение. Второе слагаемое устремляется к бесконечности при Δu →0. Это вполне логично, поскольку неопределенность значений непрерывной величины действительно бесконечна. Но для практических нужд желательно перейти к конечным величинам.

* Учитывая известное правило, что логарифм произведения равен сумме логарифмов сомножителей, формулу (3.7) можно представить как сумму двух слагаемых:
HΔu(U) = - Σ[Δu f(ui)]{log2Δu+log2f(ui)} = - Σ[f(ui)log2f(ui)]Δu - log2Δu Σf(ui)Δu
Теперь, полагая, что Δu→0, получим:
- первое слагаемое
Σ [f(ui) log2 f(ui)] Δu ≈ ∫ f(u) log2 f(u) du;
- второе слагаемое
- log2Δu Σf(ui)Δu = - log2 Δu, поскольку Σ f(ui) Δu = ∫ f(u)du = 1.

Дифференциальная энтропия
Для исключения бесконечности вычтем из (3.8) последнее слагаемое:
H*(U) = H(U) - (- log2 Δu) = - ∫ f(u) log2 f(u) du (3.9).
Полученную величину H*(U) называют дифференциальной энтропией (используется также термин относительная энтропия). Ее удобно использовать для сопоставления непрерывных случайных величин, которые различаются своими распределениями f(u).
Величину дифференциальной энтропии H*(U) удобно интерпретировать как отличие полной энтропии рассматриваемой величины U от от энтропии -log2Δu некоторой базовой случайной величины. Показано, что такая базовая величина должна иметь равномерное распределение в пределах изменения u от 0 до 1.
Свойства дифференциальной энтропии (ДЭ) иллюстрирует рис.3.11:
  • ДЭ может быть как положительно, так и отрицательной. Действительно, Н*(U) определяется по отношению к энтропии величины, равномерно распределенной от 0 до 1. Но аналогичная величина, распределенная в более узком диапазоне очевидно характеризуется меньшей неопределенностью;
  • ДЭ увеличивается с ростом дисперсии величины U. Очевидно, что чем больше разброс значений случайной величины, тем выше неопределенность. Добавим, что значение Н*(U) помимо дисперсии зависит также от вида распределения плотности вероятностей f(u). Ниже мы рассмотрим этот момент подробнее;
  • величина ДЭ она не зависит от мат. ожидания случайной величины. На самом деле, если мы будем помещать распределение такой величины в разные ее диапазоны, это никак не повлияет на степень неопределенности.

Примеры распределений с максимальной энтропией
Особый интерес представляют случаи распределений, для которых величина энтропии при заданной дисперсии является максимальной (рис.3.12):
  • случай 1. Если для непрерывной случайной величины фиксированы границы ее диапазона, то максимальным будет значение ДЭ для равномерного распределения плотности вероятности f(u). Такой вариант полностью аналогичен случаю дискретного источника;
  • формула расчета величины H*(U) для равномерного распределения f(u) в диапазоне от a до b будет иметь вид:
    H*(U)= -∫ [1/(b-a)] log2 [1/(b-a)] du = log2 (b-a) (3.10)
    При этом дисперсия определяется как D = σ2 = (b-a)2/12;
  • случай 2. Если для непрерывной случайной величины ограничена ее дисперсия, то максимальная энтропия будет у нормального (Гауссова) распределения плотности вероятности. Такой вариант характерен, в частности, для передачи сигналов, для которых ограничивается мощность (которая пропорциональна дисперсии);
  • формула для определения ДЭ также выводится исходя их (3.9). В результате получается
    H*(U) = log2 √(2πσ2e) (3.11)
    (здесь e - константа Эйлера примерно равная 2,72)

Количественное сравнение рассмотренных случаев выполним на примере, когда значение ДЭ H*(U)=0. Тогда под знаком логарифма в обоих формулах должна быть 1. При этом для равномерного распределения D=σ2=1/12=0,083 и σ=0,289. Для нормального распределения исходя из (3.11) D=σ2=1/(2πe)=0,058 и σ=0,242. В случае нормального распределения для достижения того-же значения H*(U) необходима величина дисперсии в 0,083/0,058=1,42 раза меньше, чем при равномерном распределении. Такая пропорция сохранится независимо от заданной величины ДЭ, поскольку она определяется соотношением формул (3.10) и (3.11).

Контрольные вопросы
1) Как устанавливается соответствие между дискретным и непрерывным подходами к определению энтропии. Поясните это с помощью рисунка
2) Запишите итоговую формулу для определения энтропии непрерывной величины. Почему она дает бесконечное значение энтропии. Насколько это соответствует интуитивным представлениям.
3) Поясните понятие дифференциальной энтропии и запишите формулу для ее определения.
4) Сформулируйте и поясните с помощью рисунка основные свойства дифференциальной энтропии непрерывного источника
5) Запишите формулы дифференциальной энтропии для равномерного и нормального распределений плотности вероятности. Проиллюстрируйте с помощью этих формул основные свойства ДЭ.
6) Используя формулы (3.10) и (3.11), рассчитайте пропорцию величины дисперсии для равномерного и нормального распределений для случая, когда H*(U).

О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP