Основы теории информации и криптографии - -Учебное пособие (В.В. Лидовский)

3. лекция: смысл энтропии шеннона

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

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

Рассмотрим пример (скачки). В заезде участвуют 4 лошади с равными шансами на победу, т.е. вероятность победы каждой лошади равна 1/4. Введем д.с.в. X, равную номеру победившей лошади. Здесь HX=2. После каждого заезда по каналам связи достаточно будет передавать два бита информации о номере победившей лошади. Кодируем номер лошади следующим образом: 1-00, 2-01, 3-10, 4-11. Если ввести функцию L(X), которая возвращает длину сообщения, кодирующего заданное значение X, то м. о. ML(X)- это средняя длина сообщения, кодирующего X. Можно формально определить Lчерез две функции L(X)=len(code(X)), где code(X)каждому значению Xставит в соответствие некоторый битовый код, причем, взаимно однозначно, а lenвозвращает длину в битах для любого конкретного кода. В этом примере ML(X)=HX.

Пусть теперь д.с.в. Xимеет следующее распределение

P(X=1)={3over4},, P(X=2)={1over8},,
P(X=3)=P(X=4)={1over16},

т.е. лошадь с номером 1 - это фаворит. Тогда

HX={3over4}log_2{4over3}+{1over8}log_28+{1over8}log_216=
{19over8}-{3over4}log_23approx1.186 hbox{ бит/сим}.

Закодируем номера лошадей: 1-0, 2-10, 3-110, 4-111, - т.е. так, чтобы каждой код не был префиксом другого кода (подобное кодирование называют префиксным). В среднем в 16 заездах 1-я лошадь должна победить в 12 из них, 2-я - в 2-х, 3-я - в 1-м и 4-я - в 1-м. Таким образом, средняя длина сообщения о победителе равна (1*12+2*2+3*1+3*1)/16=1.375бит/сим или м. о. L(X). Действительно, L(X)сейчас задается следующим распределением вероятностей: P(L(X)=1)=3/4, P(L(X)=2)=1/8, P(L(X)=3)=1/8. Следовательно,

ML(X)={3over4}+{2over8}+{3over8}={11over8}=1.375 hbox{
бит/сим}.

Итак, ML(X) > HX.

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

То, что энтропия Шеннона соответствует интуитивному представлению о мере информации, может быть продемонстрировано в опыте по определению среднего времени психических реакций. Опыт заключается в том, что перед испытуемым человеком зажигается одна из Nлампочек, которую он должен указать. Проводится большая серия испытаний, в которых каждая лампочка зажигается с определенной вероятностью p_i(sum_i^Np_i=1), где i- это номер лампочки. Оказывается, среднее время, необходимое для правильного ответа испытуемого, пропорционально величине энтропии -sum_{i=1}^N p_ilog_2p_i, а не числу лампочек N, как можно было бы подумать. В этом опыте предполагается, что чем больше информации будет получено человеком, тем дольше будет время ее обработки и, соответственно, реакции на нее.

Упражнение 13 Найти энтропию д.с.в. Xи среднюю длину каждого из приведенных кодов для этой д.с.в.

vbox{offinterlineskiphalign{&strutquad#cr
X&        omit vrule&  1&   3&   4&   5& 6cr

oalign{hrule}
p&        omit vrule& 0.4& 0.2& 0.1& 0.2& 0.1cr
code1(X)& omit vrule& 000& 001& 010& 011& 111cr
code2(X)& omit vrule& 0&  100& 101& 110& 111cr
code3(X)& omit vrule& 00&  01&  110& 10&  111cr
code4(X)& omit vrule& 0&  10&  1110&110&
1111.cr}}

Упражнение 14 д.с.в. Xравна количеству "гербов", выпавших на двух идеальных монетках. Найти энтропию X. Придумать минимальный код для X, вычислить его среднюю длину и обосновать его минимальность.

Упражнение 15 д.с.в. Xзадана распределением P(X=2^n)=1/2^n, n=1,2,ldotsНайти энтропию этой д.с.в. Придумать минимальный код для X, вычислить его среднюю длину и обосновать его минимальность.

Упражнение 16 Про д.с.в. Xизвестно, что ее значениями являются буквы кириллицы. Произведен ряд последовательных измерений X, результат которых - "ТЕОРИЯИНФОРМАЦИИ". Составить на основании этого результата приблизительный закон распределения вероятностей этой д.с.в. и оценить минимальную среднюю длину кодов для X.

Семантическая информация

В 50-х годах XX века появились первые попытки определения абсолютного информационного содержания предложений естественного языка. Стоит отметить, что сам Шеннон однажды заметил, что смысл сообщений не имеет никакого отношения к его теории информации, целиком построенной на положениях теории вероятностей. Но его способ точного измерения информации наводил на мысль о возможности существования способов точного измерения информации более общего вида, например, информации из предложений естественного языка. Примером одной из таких мер является функция inf(s)=-log_2p(s), где s- это предложение, смысловое содержание которого измеряется, p(s)- вероятность истинности s. Вот некоторые свойства этой функции-меры:

если s_1 Rightarrow s_2(из s_1следует s_2) - истинно, то inf(s_1) ge inf(s_2);

inf(s) ge 0;

если s- истинно, то inf(s)=0;

inf(s_1s_2)=inf(s_1)+inf(s_2) xLeftrightarrow
p(s_1cdot s_2)=p(s_1)p(s_2), т.е. независимости s_1и s_2.

Значение этой функция-меры больше для предложений, исключающих большее количество возможностей. Пример: из s_1- "a>3" и s_2- "a=7" следует, что s_2 Rightarrow
s_1или inf(s_2)ge inf(s_1); ясно, что s_2исключает больше возможностей, чем s_1.

Для измерения семантической информации также используется функция-мера cont(s) = 1-p(s). Ясно, что cont(s)=1-2^{-inf(s)}или inf(s)=-log_2(1-cont(s)).

Упражнение 17 Вычислить inf(s)и cont(s)предложения s_1, про которое известно, что оно достоверно на 50\%, и предложения s_2, достоверность которого 25\%.