Задачи занятия:
- Научиться среди предложенных событий выбирать неопределенные;
- Установить соответствие между вероятностью события и его неопределенностью;
- Научиться подсчитывать энтропию события по формуле Хартли;
- Отработать метод половинного деления для решения задач на угадывание;
- Разобрать алгоритм решения задач на угадывание с применением понятия энтропии.
Способы измерения информации
Понятие количества информации естественно возникает, к примеру, в следующих типовых случаях:
- Равенство вещественных переменных а = b, заключает в себе информацию о том, что а равно b. Про равенство а2 = b2 можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, но не наоборот. Равенство а3 = b3 несет в себе информацию по объему такую же, как и первое;
-
Пусть происходят некоторые измерения с некоторой погрешностью. Тогда чем больше будет проведено измерений, тем больше информации об измеряемой сущности будет получено;
-
М.о. некоторой сл. в. содержит в себе информацию о самой сл. в. Важно заметить, что для сл.в., распределенной по нормальному закону, с известной дисперсией знание м.о. дает полную информацию о сл.в.;
-
Рассмотрим схему передачи информации. Пусть передатчик описывается ел. в. X, тогда из-за помех в канале связи на приемник будет приходить сл.в. Y = X + Z, где Z — это сл.в., описывающая помехи. В этой схеме можно говорить о количестве информации, содержащейся в сл.в. Y, относительно X. Чем ниже уровень помех (дисперсия Z мала), тем больше информации можно получить из Y. При отсутствии помех Y содержит в себе всю информацию об X.
В 1865 ᴦ. немецкий физик Рудольф Клаузиус ввел в статистическую физику понятие энтропии или меры уравновешенности системы.
В 1921 ᴦ. основатель большей части математической статистики, англичанин Роналд Фишер впервые ввел термин “информация” в математику, но полученные им формулы носят очень специальный характер.
В 1948 ᴦ. Клод Шеннон в своих работах по теории связи выписывает формулы для вычисления количества информация и энтропии. Термин “энтропия” используется Шенноном по совету патриарха компьютерной эры фон Неймана, отметившего, что полученные Шенноном для теории связи формулы для ее расчета совпали с соответствующими формулами статистической физики, а также то, что “точно никто не знает” что же такое энтропия.
В основе теории информации лежит предложенный Шенноном способ измерения количества информации, содержащейся в одной сл. в. относительно другой сл. в. Этот способ приводит к выражению количества информации числом.
Для д.с.в. X и Y, заданных законами распределения P(X = Xi) = pi, P(Y = Yj) = qj и совместным распределением P(X = Xi,Y = Yj) = pij, количество информации, содержащейся в X относительно Y, равно
Стоит сказать, что для непрерывных сл. в. X и Y, заданных плотностями распределения вероятностей pX(t1), p Y (t2) и P X Y (t1,t2), аналогичная формула имеет вид
Очевидно, что
и, следовательно,
Энтропия д. с. в. X в теории информации определяется формулой
Свойства меры информации и энтропии:
1) Логарифмированием из очевидного для всех х неравенства (равенство устанавливается только при х = 1) получается неравенство
ᴛ.ᴇ. I(X, Y) = 0 только при pij = piqj для всех i и j, ᴛ.ᴇ. при независимости X и Y. В случае если X и Y независимы, то pij = piqj и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X, Y) = 0;
2) Следует из симметричности формул относительно аргументов;
3) В случае если НХ = 0, то все члены суммы, определяющей НХ, должны быть нули, что возможно только тогда и только тогда, когда X — константа;
4) Из четырех очевидных соотношений
получается
5) Нужно доказать
или
но
а значит аргументы у всех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше 0.
В случае если HX = I(X,X) = I(X,Y), то для каждого i pij равно либо qj, либо 0. Но из pij = P(X = Xi,Y = Yj) = P(X = Xi/Y = Yj)P(Y = Yj)∈ {qj,0} следует P(X = Xi/Y = Yj) ∈ {0,1}, что возможно только в случае, когда X — функция от Y.
При независимости сл. в. X и Y одна из них ничем не описывает другую, что и отражается в том, что для таких сл. в. I(X, Y) = 0.
Рассмотрим пример измерения количества информации при подбрасывании двух игральных костей.
Пусть заданы д. с. в. X1, X2 и Y. X1 и X2 — количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а Y = X1 +X2. Найти I(Y,X1), I(X1,X1), I(Y, Y).
Законы распределения вероятностей для д. с. в. X1 и X2 совпадают, т.к. кости одинаковые и без изъянов.
Закон распределения вероятностей для д. с. в. Y,
вследствие того, что Х1 Х2 — независимы и в связи с этим
будет
Таблицы, определяющие Y:
Закон совместного распределения вероятностей д. с. в. Х1 и Y будет
к примеру,
В общем случае получится
Тогда
Здесь
что соответствует свойствам информации.
Подчеркнутый член в расчете I(X1,Y) соответствует информации о двух случаях из 36, когда Y = 2 и Y =12, которые однозначно определяют Х1. Шесть случаев, когда Y = 7, не несут никакой информации об X1, что соответствует подчеркнутому члену
.
Расчеты можно проводить, используя 4-е свойство информации, через энтропию.
Расчет количества информации с использованием 4-го свойства, а не определения, обычно требует меньше вычислений.
Рассмотрим более простой пример. Пусть д. с. в. X равна количеству очков, выпавших на игральной кости, а д. с. в. Y равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X, Y) и /(Y, Y).
Составим законы распределения вероятностей д. с. в. X и Y.
Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, при i = 1…6 pi = Р(Х = i) = 1/6 и, соответственно, при j = 0…1 qj = P(Y = j) = 1/2.
Составим также закон совместного распределения вероятностей этих д. с. в.
Точное количество выпавших очков дает точную информацию о четности, ᴛ.ᴇ. 1 бит. Из I(X, Y) = I(Y,Y) = 1бит/сим и 3-го свойства информации следует, что информация об X полностью определяет Y, но не наоборот, т.к. I(X,Y) ¹ I(X,X) =1 + log23 » 2.58 бит/сим. Действительно, Y функционально зависит от X, а X от Y функционально не зависит.
Расчеты через энтропию будут следующими
Комментарии: