Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
Упражнение Какое из соотношений несет в себе больше информации x = 5 или x > 3? 7. Вероятностный подход к измерению дискретной и непрерывной информации В основе теории информации лежит предложенный Шенноном способ измерения количества информации, содержащейся водной сл.в. относительно другой сл. в. Этот способ приводит к выражению количества информации числом. Для д.с.в. X и Y , заданных законами распределения P (X = X i ) = p i , P (Y = Y j ) = q и совместным распределением P (X = X i , Y = Y j ) = p ij , количество информации, содержащейся в X относительно Y , равно, Y ) = i,j p ij log 2 p ij p i Для непрерывных сл. в. X и Y , заданных плотностями распределения вероятностей p X (t 1 ), p Y (t 2 ) и p XY (t 1 , t 2 ), аналогичная формула имеет вид, Y ) = R 2 p XY (t 1 , t 2 ) log 2 p XY (t 1 , Очевидно, что (X = X i , X = X j ) при i = j P (X = при i = j 12 и, следовательно, X) = i p i log 2 p i p i p i = − i p i log 2 p Энтропия д.с.в. X в теории информации определяется формулой) = HX = I(X, Свойства меры информации и энтропии) I(X, Y ) 0, I(X, Y ) = 0 ⇔ X и Y независимы) I(X, Y ) = I(Y, X); 3) HX = 0 ⇔ X — константа) I(X, Y ) = HX + HY − H(X, Y ), где H(X, Y ) = − i,j p ij log 2 p ij ; 5) I(X, Y ) I(X, X). Если I(X, Y ) = I(X, X), то X — функция от Y . 1) Логарифмированием из очевидного для всех неравенства равенство устанавливается только при x = 1 ) получается неравенство x − 1 ln x или x−1 ln 2 log 2 x −I(X, Y ) = i,j p ij log 2 p i q j p ij i,j p ij p i q j p ij − 1 ln 2 = = i,j p i q j − p ij ln 2 = i p i j q j − i,j p ij ln 2 = 1 − 1 ln 2 = те только при p ij = p i q для всех и j , те. при независимости X и Y . Если X и Y независимы, то p ij = p i q и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X, Y ) = 0 ; 2) Следует из симметричности формул относительно аргументов) Если = 0 , то все члены суммы, определяющей, должны быть нули, что возможно только тогда и только тогда, когда константа) Из четырех очевидных соотношений j p ij = p i , i p ij = q j , HX = − i p i log 2 p i = − i,j p ij log 2 p i , HY = − j q j log 2 q j = − i,j p ij log 2 q j 13 получается + HY − H(X, Y ) = i,j p ij (log 2 p ij − log 2 q j − log 2 p i ) = I(X, Y ); 5) Нужно доказать, Y ) = HX + HY − H(X, Y или − H(X, Y ) 0 HY − H(X, Y ) = − i,j p ij log 2 q j + i,j p ij log 2 p ij = i,j p ij log 2 (p ij /q но p ij = P (X = X i , Y = Y j ) q j = P (Y = Y j ) , а значит аргументы у всех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше Если = I(X, X) = I(X, Y ) , то для каждого i p ij равно либо либо 0. Но из p ij = P (X = X i , Y = Y j ) = P (X = X i /Y = Y j )P (Y = Y j ) ∈ {q j , следует (X = X i /Y = Y j ) ∈ {0, 1} , что возможно только в случае, когда X — функция от Y При независимости сл. в. X и Y одна из них ничем не описывает другую, что и отражается в том, что для таких сл.в. I(X, Y ) = Рассмотрим пример измерения количества информации при подбрасывании двух игральных костей. Пусть заданы д. св, и Y . и X 2 — количества очков, выпавших соответственно на й и й игральной кости, а Y = X 1 + Найти I(Y, X 1 ), I(X 1 , X 1 ), I(Y, Y Законы распределения вероятностей для д.с.в. и X 2 совпадают, т.к. кости одинаковые и без изъянов 1 2 3 4 5 6 p 1/6 , те. при j = 1...6 q j = P (X 1 = j) = Закон распределения вероятностей для д.с.в. Y , P (Y = i) = P (X 1 + X 2 = i), i = вследствие того, что X 1 , X 2 — независимы и поэтому (X 1 = n, X 2 = m) = P (X 1 = n)P (X 2 = будет p i = P (X 1 + X 2 = i) = n+m=i 1 n,m 6 P (X 1 = n)P (X 2 = m) = n+m=i 1 n,m 6 Таблицы, определяющие Y : 14 X 2 \ X 1 1 2 3 4 5 6 1 2 3 4 5 6 7 2 3 4 5 6 7 8 3 4 5 6 7 8 9 4 5 6 7 8 9 10 5 6 7 8 9 10 11 6 7 8 9 10 11 12, Y = X 1 + X 2 2 3 4 5 6 7 8 9 10 11 12 p 1 / 36 2 / 36 3 / 36 4 / 36 5 / 36 6 / 36 5 / 36 4 / 36 3 / 36 2 / 36 те. при i = 2...12, p i = P (Y = i) = (6 − |7 − Закон совместного распределения вероятностей д.с.в. и Y будет p ij = P (Y = i, X 1 = j) = P (Y = i/X 1 = j)P (X 1 = например (Y = 2, X 1 = 1) = P (Y = 2/X 1 = 1)P (X 1 = 1) = = P (X 2 = 1)P (X 1 = 1) = В общем случае получится p ij = P (Y = i, X 1 = j) при 1 i − иначе 3 4 5 6 7 8 9 10 11 12 1 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 0 0 0 0 0 2 0 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 0 0 0 0 3 0 0 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 0 0 0 4 0 0 0 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 0 0 5 0 0 0 0 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 0 6 0 0 0 0 0 1 / 36 1 / 36 1 / 36 1 / 36 1 / 36 Тогда, X 1 ) = 6 j=1 1 i−j 6 p ij log 2 p ij p i q j = = 1 36 6 j=1 1 i−j 6 log 2 1 6p i = = 1 36 ( 7 i=2 log 2 1 6p i + 8 i=3 log 2 1 6p i + · · · + 11 i=6 log 2 1 6p i + 12 i=7 log 2 1 6p i ) = 15 = 1 36 ((log 2 6 1 +log 2 6 2 +· · ·+log 2 6 6 )+· · ·+(log 2 6 6 +log 2 6 5 +· · ·+log 2 6 1 )) = = 1 36 (2 log 2 6 + 4 log 2 3 + 6 log 2 2 + 8 log 2 3 2 + 10 log 2 6 5 + 6 log 2 1) = = (2 + 2 log 2 3 + 4 log 2 3 + 6 + 8 log 2 3 − 8 + 10 log 2 3 + 10 − 10 log 2 5)/36 = = (10 + 24 log 2 3 − 10 log 2 5)/36 ≈ 0.69 бит/символ. I(X 1 , X 1 ) = I(X 2 , X 2 ) = − 6 j=1 q j log 2 q j = log 2 6 = 1 + log 2 3 ≈ 2.58 бит/сим. I(Y, Y ) = − 12 i=2 p i log 2 p i = = 1 36 (2 log 2 36 + 4 log 2 18 + 6 log 2 12 + 8 log 2 9 + 10 log 2 36 5 + 6 log 2 6) = = (4+4 log 2 3+4+8 log 2 3+12+6 log 2 3+16 log 2 3+20+20 log 2 3−10 log 2 5+ + 6 + 6 log 2 3)/36 = (46 + 60 log 2 3 − 10 log 2 5)/36 ≈ 3.27 бит/сим. Здесь 0 < I(Y, X 1 ) = I(Y, X 2 ) < I(X 1 , X 1 ) = I(X 2 , X 2 ) < I(Y, Y что соответствует свойствам информации. Подчекнутый член 36 2 log 2 6 = I(X 1 , X 1 )/18 в расчете I(X 1 , Y ) соответствует информации о двух случаях из 36, когда Y = 2 и Y = которые однозначно определяют X 1 . Шесть случаев, когда Y = 7, не несут никакой информации об X 1 , что соответствует подчеркнутому члену 6 log 2 1 = Расчеты можно проводить, используя е свойство информации, через энтропию, X 1 ) = − i,j p ij log 2 p ij = log 2 36 = 2(1 + log 2 3) = 2HX 1 ≈ 5.17 бит/сим. I(Y, X 1 ) = HX 1 + HY − H(X 1 , Y ) = HY − HX 1 ≈ 3.27 − 2.58 = 0.69 бит/сим. Расчет количества информации с использованием го свойства, а не определения, обычно требует меньше вычислений. Рассмотрим более простой пример. Пусть д. св равна количеству очков, выпавших на игральной кости, ад. св равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X, Y ) и I(Y, Y Составим законы распределения вероятностей д.с.в. X и Y . X 1 2 3 4 5 6 p 1/6 Y 0 Таким образом, при i = 1...6 p i = P (X = i) = 1/6 и, соответственно, при j = 0...1 q j = P (Y = j) = 1/2. 16 Составим также закон совместного распределения вероятностей этих д.с.в. X 1 3 5 2 4 6 1 3 5 2 4 6 Y 0 0 0 1 1 1 1 1 1 0 0 0 p 1/6 Таким образом, p ij = P (X = i, Y = j) если i + j — четно, иначе, Y ) = i,j p ij log 2 p ij p i q j = 6 1 6 log 2 2 = 1 бит/сим. I(Y, Y ) = − 1 j=0 q j log 2 q j = 2 1 2 log 2 2 = 1 бит/сим. Точное количество выпавших очков дает точную информацию о четности, те бит. Из I(X, Y ) = I(Y, Y ) = 1 бит/сим иго свойства информации следует, что информация об X полностью определяет Y ноне наоборот, т.к. I(X, Y ) = I(X, X) = 1 + log 2 3 ≈ 2.58 бит/сим. Действительно функционально зависит от X, а X от Y функционально не зависит. Расчеты через энтропию будут следующими, Y ) = − i,j p ij log 2 p ij = log 2 6 = 1 + log 2 3 = HX, I(X, Y ) = HX + HY − HX = HY = 1 бит/сим. Упражнение Найти энтропию д.с.в. X, заданной распределением 2 3 4 5 6 7 8 p 0.1 0.2 0.1 0.05 0.1 0.05 0.3 Упражнение Значения д. св. и определяются подбрасыванием двух идеальных монета д.с.в. Y равна сумме количества гербов, выпавших при подбрасывании этих монет. Сколько информации об содержится в Упражнение Сколько информации об содержится в д.с.в. Z = (X 1 + 1) 2 − X 2 , где независимые д. св. и могут с равной вероятностью принимать значение либо 0, либо 1? Найти и HZ. Каков характер зависимости между и Упражнение Д. св зависимы и распределены также как и соответствующие д. св. из предыдущей задачи. Найти I(X 1 , X 2 ), если совместное распределение вероятностей и описывается законом 0 0 1 1 X 2 0 1 0 1 p 1/3 1/6 1/6 1/3. 17 Упражнение Д. св. и определяются подбрасыванием двух идеальных тетраэдров, грани которых помечены числами от 1 до 4. Д. св равна сумме чисел, выпавших при подбрасывании этих тетраэдров, те. Вычислить I(X 1 , Y ), и HY Упражнение Подсчитать сколько информации об содержится в д.с.в. Z = а также HZ. Д.с.в. и берутся из предыдущего упражнения. Упражнение 11 Д.с.в. может принимать три значения −1, 0 и 1 с равными вероятностями. Д.с.в. с равными вероятностями может принимать значения, 1 и 2. и X 2 — независимы. Y = X 2 1 +X 2 . Найти I(X 1 , Y ), I(X 2 , Y ), HX 1 , HX 2 , HY Упражнение Найти энтропии д. св и количество информации, содержащейся в Z = X + Y относительно Y . X и Y — независимы и задаются распределениями 1 3 4 Y −2 2 p 1/8 1/8 1/4 1/2 p 3/8 5/8. 8. Смысл энтропии Шеннона Энтропия д.с.в. — это минимум среднего количества бит, которое нужно передавать по каналу связи о текущем значении данной д.с.в. Рассмотрим пример (скачки. В заезде участвуют 4 лошади с равными шансами на победу, те. вероятность победы каждой лошади равна. Введем д. св, равную номеру победившей лошади. Здесь = 2. После каждого заезда по каналам связи достаточно будет передавать два бита информации о номере победившей лошади. Кодируем номер лошади следующим образом 1—00, 2—01, 3—10, Если ввести функцию L(X), которая возвращает длину сообщения, кодирующего заданное значение X, том. о. M L(X) — это средняя длина сообщения, кодирующего X. Можно формально определить L через две функции L(X) = len(code(X)), где code(X) каждому значению ставит в соответствие некоторый битовый код, причем, взаимно однозначно, а len возвращает длину в битах для любого конкретного кода. В этом примере M L(X) = Пусть теперь д.с.в. X имеет следующее распределение (X = 1) = 3 4 , P (X = 2) = 1 8 , P (X = 3) = P (X = 4) = 1 16 , 18 те. лошадь с номером 1 — это фаворит. Тогда = 3 4 log 2 4 3 + 1 8 log 2 8 + 1 8 log 2 16 = 19 8 − 3 4 log 2 3 ≈ 1.186 бит/сим. Закодируем номера лошадей 1—0, 2—10, 3—110, 4—111, — те. так, чтобы каждой код не был префиксом другого кода (подобное кодирование называют префиксным. В среднем в 16 заездах я лошадь должна победить виз них, я — в х, я — в ми я в м. Таким образом, средняя длина сообщения о победителе равна ∗ 12 + 2 ∗ 2 + 3 ∗ 1 + 3 ∗ 1)/16 = 1.375 бит/сим или м. о. L(X). Действительно) сейчас задается следующим распределением вероятностей Следовательно L(X) = 3 4 + 2 8 + 3 8 = 11 8 = 1.375 бит/сим. Итак, M L(X) > Можно доказать, что более эффективного кодирования для двух рассмотренных случаев не существует. То, что энтропия Шеннона соответствует интуитивному представлению о мере информации, может быть продемонстрировано в опыте по определению среднего времени психических реакций. Опыт заключается в том, что перед испытуемым человеком зажигается одна из лампочек, которую он должен указать. Проводится большая серия испытаний, в которых каждая лампочка зажигается с определенной вероятностью, где i — это номер лампочки. Оказывается, среднее время, необходимое для правильного ответа испытуемого, пропорционально величине энтропии − N i=1 p i log 2 p i , а не числу лампочек , как можно было бы подумать. В этом опыте предполагается, что чем больше информации будет получено человеком, тем дольше будет время ее обработки и, соответственно, реакции на нее. Упражнение Найти энтропию д. св и среднюю длину каждого из приведенных кодов для этой д.с.в. X 1 3 4 5 6 p 0.4 0.2 0.1 0.2 0.1 code1(X) 000 001 010 011 111 code2(X) 0 100 101 110 111 code3(X) 00 01 110 10 111 code4(X) 0 10 1110 110 1111. 19 Упражнение 14 Д.с.в. X равна количеству гербов, выпавших на двух идеальных монетках. Найти энтропию X. Придумать минимальный код для X, вычислить его среднюю длину и обосновать его минимальность. Упражнение Д. св задана распределением P (X = 2 n ) = 1/2 n , n = 1, 2, . . . Найти энтропию этой д. св. Придумать минимальный код для X, вычислить его среднюю длину и обосновать его минимальность. Упражнение Про д.с.в. X известно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений X, результат которых — “ТЕОРИЯИНФОРМАЦИИ”. Составить на основании этого результата приблизительный закон распределения вероятностей этой д. св. и оценить минимальную среднюю длину кодов для X. 9. Семантическая информация В х годах XX века появились первые попытки определения абсолютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, целиком построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности существования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Примером одной из таких мер является функция inf (s) = − log 2 p(s), где s — это предложение, смысловое содержание которого измеряется, p(s) — вероятность истинности s. Вот некоторые свойства этой функции- меры) если s 1 ⇒ из следует s 2 ) — истинно, то inf (s 1 ) inf (s 2 ); 2) inf (s) 0; 3) если s — истинно, тот. е. независимости и Значение этой функция-меры больше для предложений, исключающих большее количество возможностей. Пример из s 1 — “a > 3” и s 2 — “a = 7” следует, что s 2 ⇒ или inf (s 2 ) inf (s 1 ); ясно, что исключает больше возможностей, чем Для измерения семантической информации также используется функция-мера cont(s) = 1 − p(s). Ясно, что cont(s) = 1 − 2 −inf (или inf (s) = − log 2 (1 − cont(s)). 20 Упражнение Вычислить inf (s) и cont(s) предложения s 1 , про которое известно, что оно достоверно на 50%, и предложения s 2 , достоверность которого 25%. 10. Сжатие информации Цель сжатия — уменьшение количества бит, необходимых для хранения или передачи заданной информации, что дает возможность передавать сообщения более быстро и хранить более экономно и оперативно (последнее означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, если скорость распаковки данных выше скорости считывания данных с носителя информации. Сжатие позволяет, например, записать больше информации на дискету, увеличить размер жесткого диска, ускорить работу с модемом и т.д. При работе с компьютерами широко используются программы-архиваторы данных формата ZIP, GZ, ARJ и других. Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины х годов, мало использовалась в компьютерах на практике. Сжатие данных не может быть большим некоторого теоретические предела. Для формального определения этого предела рассматриваем любое информационное сообщение длины n как последовательность независимых, одинаково распределенных д.с.в. X i или как выборки длины значений одной д.с.в. Доказано [20], что среднее количество бит, приходящихся на одно кодируемое значение д. св, не может быть меньшим, чем энтропия этой д.с.в., те. M L(X) HX для любой д.с.в. X и любого ее кода. Кроме того, доказано [20] утверждение о том, что существует такое кодирование (Шеннона-Фэно, Fano), что HX M L(X) − Рассмотрим д.с.в. и X 2 , независимые и одинаково распределенные и I(X 1 , X 2 ) = 0, следовательно, X 2 ) = HX 1 + HX 2 − I(X 1 , X 2 ) = Вместо и можно говорить о двумерной д. св, Аналогичным образом для мерной д.с.в. X = (X 1 , X 2 , . . . , X n ) можно получить, что HX = Пусть L 1 (X) = L(X)/n, где X = (X 1 , X 2 , . . . , X n ), те. L 1 (X) — это количество бит кода на единицу сообщения X. Тогда M L 1 (X) — это среднее количество бит кода на единицу сообщения при передаче бесконечного множества сообщений X. Из M L(X) − 1 |