Смысл энтропии Шеннона

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

Рассмотрим пример (скачки). В заезде участвуют 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)={3\over4},\, P(X=2)={1\over8},\, P(X=3)=P(X=4)={1\over16},$$ т.е. лошадь с номером 1 - это фаворит. Тогда$$HX={3\over4}\log_2{4\over3}+{1\over8}\log_28+{1\over8}\log_216= {19\over8}-{3\over4}\log_23\approx1.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)={3\over4}+{2\over8}+{3\over8}={11\over8}=1.375 \hbox{ бит/сим}.$$ Итак, $$ML(X) > HX$$.

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

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

Упражнение 13 Найти энтропию д.с.в. $$X$$ и среднюю длину каждого из приведенных кодов для этой д.с.в.$$\vbox{\offinterlineskip\halign{\strut\quad#\cr X \omit\ \vrule 1 3 4 5 6\cr \noalign{\hrule} p \omit\ \vrule 0.4 0.2 0.1 0.2 0.1\cr code1(X) \omit\ \vrule 000 001 010 011 111\cr code2(X) \omit\ \vrule 0 100 101 110 111\cr code3(X) \omit\ \vrule 00 01 110 10 111\cr code4(X) \omit\ \vrule 0 10 1110110 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$$ - " $$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%.