Введение в понятие Энтропия

Из Теории Информационных Технологий и Систем известно, что информационная энтропия - это мера хаотичности информации [1]. Другими словами, это неопределённость появления какого-либо символа первичного алфавита.

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

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

В информатике большое месте занимает теория информации Шеннона и его подход к понятию энтропия. Если заглянуть в Википедию [2], можно узнать, что родился он в 1916 году в городе Петочки, Мичиган, США. Он закончил Мичиганский Университет и после этого долгое время работал в Массачусетском Технологическом Институте, где защитил степень доктора по математике и магистра по электротехнике. На сегодняшний день Шеннон известен как автор фундаментальных трудов по теории информации, электротехнике и криптографии. Мировую известность Шеннону принесла статья «Математическая теория связи», опубликованная в 1948 году. В ней Шеннон изложил свои идеи, ставшие впоследствии основой современных теорий и техник обработки передачи и хранения информации. Он ввел понятие информации, содержащейся в передаваемых сообщениях и первым начал рассматривать передаваемые сообщения и шумы в каналах связи с точки зрения статистики, рассматривая как конечные множества сообщений, так и непрерывные множества сообщений. Развитая Шенноном теория информации помогла решить главные проблемы, связанные с передачей сообщений, а именно: устранить избыточность передаваемых сообщений, произвести кодирование и передачу сообщений по каналам связи с шумами. 

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

Можно проследить связь между количеством информации и энтропией. [3] Приведем ряд примеров. При бросании монеты выпадает орел или решка, это определенная информация о результатах бросания. При бросании кубика мы получаем информацию о выпадении определенного количества очков. В каким из этих двух случаев мы получаем больше информации?

Известно, что вероятность W выпадения орла равна 1/2, вероятность выпадения трех очков на кости - W=1/6. Реализация менее вероятного события дает больше информации: чем больше неопределенность до получения сообщения о событии (бросание монеты, кости), тем большее количество информации поступает при получении сообщения. Информация I связана с числом равновероятных возможностей P - для монеты P=2, для кости P=6. При бросании двух костей мы получаем вдвое больше информации, чем при бросании одной кости: информация независимых сообщений аддитивна, а числа равновероятных возможностей перемножаются. Значит, если имеются два набора равновероятных событий P₁ и P₂ , то полное число событий

P=P₁*P₂, (1)

а количество информации I складывается, т. е.

I(P)=I(P₁*P₂)=I(P₁)+ I(P₂).    (2)

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

I=A*log(P)

где постоянная А и основание логарифма могут быть выбраны по соглашению. В теории информации условились полагать А=1, а основание логарифма двум, т. е.

I=log₂(P). (3)

При бросании монеты получается информация (Р=2), которую примем за единицу информации I=1:

log₂(2)=1 бит

В общем виде формула (3) принимает вид (вывод опускается)[3]:

Такая величина (4) названа Шенноном информационной энтропией.

В начале работы была постулирована идея о том, что различные буквы встречаются в языке с разными вероятностями. Для того, чтобы подтвердить или опровергнуть данное утверждение, можно провести небольшое исследование: возьмем достаточно большой набор слов русского языка и подсчитаем вероятности появления различных символов. В качестве источника слов возьмем "Толковый словарь русского языка в 4-х т." - всего 86702 слова. Чтобы обработать этот объем информации воспользуемся утилитой, написанной автором этой работы на первом курсе обучения в ГУ-ВШЭ.

 

Утилита была создана в том числе для подсчета вероятностей встречи различных символов в тексте и расчета энтропии. Проведем это с выбранным словарем. Результаты показаны на рисунках 1 и 2.

 

Рисунок 1. Результаты анализа толкового словаря

 

Рисунок 2. Результаты анализа толкового словаря (продолжение)

 

Как видно из результатов, наименьшая вероятность встретить знак "Ъ", наибольшая - буквы "А", "В", "Е", "Н" "О", "Р", "С", "Т". Интересное наблюдение: расположение букв на клавиатуре таково, что наиболее часто встречающиеся буквы находятся в центре (можно посмотреть на полученный ряд и центр клавиатуры), а самые популярные "А" и "О" отмечены точками для расположения указательных пальцев. Английская же раскладка организована по другому принципу - самые популярные буквы расположены на удалении друг от друга, что диктовалось технологией реализации первых клавиатур печатных машинок и со временем так укоренилось в обществе, что нынче проект перевода общества на более эргономичную клавиатуру сопряжен с невероятно большими издержками, что делает его невыполнимым (в литературе такая ситуация получила название "QWERTY"-эффект).

Для наглядности распределения вероятностей средствами утилиты можно построить диаграмму (см. рис. 3).

 

Рисунок 3. Диаграмма соотношения вероятностей появления различных символов

 

Наиболее крупные ячейки и есть самые часто встречаемые символы.

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

В качестве художественного произведения взят отрывок в первые 2700 слов "Анны Карениной". Для чистоты эксперимента из текста были удалены все знаки препинания.

 

Рисунок 4. Вероятности появления символов и энтропия для художественного текста.

В качестве примера технического текста взята инструкция по эксплуатация герметизированных свинцово-кислотных аккумуляторов с регулирующими клапанами (2700 слов). Для чистоты эксперимента из текста так же были удалены все знаки препинания.

 

Рисунок 5. Вероятности появления символов и энтропия для технического текста.

 

Как видно, распределение вероятностей в целом не изменилось, хотя конкретные значения несильно исказились. В целом мера неопределенности несильно выросла, что можно объяснить, например, большим использованием специфических терминов, в которых используются редкие для художественной речи сочетания букв.

Выше были подсчитаны вероятности встретить каждую букву при случайном выборе одной буквы из массива связного текста. Однако интересно, изменяются ли эти вероятности внутри одного слова? Если мы случайным образом выберем первую букву, то будет ли распределение вероятностей при выявлении следующей буквы такой же, как и при выборе первой буквы?

Можно провести мысленный эксперимент. Вероятность, что первой попавшейся буквой будет "О", достаточно велика, в то время, как вероятность выбрать "Ь" очень мала, но она есть. Пусть первой буквой в слове попалась "О". Поскольку в русском языке не встречаются буквосочетания "ОЬ", то вероятность встретить следующей буквой "Ь" станет не та, малая, что была раньше, а ноль. Поэтому можно сделать вывод, что вероятности при последующей встрече букв в рамках одного слова будут отличаться от вероятностей встретить эти буквы в качестве первых. Следовательно, неопределенность падает и каждая последующая буква несет меньшее количество информации, чем предыдущая.

 

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

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

В ходе работы были получены следующие результаты:

было получено определение понятия энтропии - это мера хаотичности информации, или неопределённость появления какого-либо символа первичного алфавита.

было введено понятие информационной энтропии Шеннона.

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

была высказана идея о вероятной идентичности поведения слов внутри связных текстов поведению букв внутри слов языка.

Список использованных источников информации

1. Кирсанов А.П. Теория информационных технологий и систем. Курс лекций, ГУ-ВШЭ, 2007

2. http://ru.wikipedia.org/wiki/Шеннон,_Клод_Эдвуд , дата обращения 21.09.2010

3. Дульнев Г.Н., Ипатов А.П., Агеев И.Л. Электронный учебник по дисциплине: "Синергетика". http://de.ifmo.ru/bk_netra/page.php?tutindex=13 - дата обращения 21.09.2010

4. Толковый словарь русского языка: В 4 т. - М.: Сов. энцикл.: ОГИЗ - http://feb-web.ru/feb/ushakov/ush-abc/11/us1146515.htm - дата обращения 21.09.2010