Взаимосвязь энтропии и информации. Информационная энтропия. Формула Шеннона

Понятие Энтропи́и впервые введено в 1865 Р. Клаузиусом в термодинамике для определения меры необратимого рассеяния энергии. Энтропия применяется в разных отраслях науки, в том числе и в теории информации как мера неопределенности какого-либо опыта, испытания, который может иметь разные исходы. Эти определения энтропии имеют глубокую внутреннюю связь. Так на основе представлений об информации можно вывести все важнейшие положения статистической физики. [БЭС. Физика. М: Большая российская энциклопедия, 1998].

Информационная двоичная энтропия для независимых (неравновероятных) случайных событий x с n возможными состояниями (от 1 до n , p - функция вероятности) рассчитывается по формуле Шеннона :

Эта величина также называется средней энтропией сообщения. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины .
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других.
В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки теории информации, которая использует понятие вероятности. Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

В случае равновероятных событий (частный случай), когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов и формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, как один из научных подходов к оценке сообщений:

, где I – количество передаваемой информации, p – вероятность события, N – возможное количество различных (равновероятных) сообщений.

Задание 1. На равновероятные события.
В колоде 36 карт. Какое количество информации содержится в сообщении, что из колоды взята карта с портретом “туз”; “туз пик”?

Вероятность p1 = 4/36 = 1/9, а p2 = 1/36. Используя формулу Хартли имеем:

Ответ: 3.17; 5.17 бит
Заметим (из второго результата), что для кодирования всех карт, необходимо 6 бит.
Из результатов также ясно, что чем меньше вероятность события, тем больше информации оно содержит. (Данное свойство называется монотонностью )

Задание 2. На неравновероятные события
В колоде 36 карт. Из них 12 карт с “портретами”. Поочередно из колоды достается и показывается одна из карт для определения изображен ли на ней портрет. Карта возвращается в колоду. Определить количество информации, передаваемой каждый раз, при показе одной карты.

При любом процессе управления и передачи происходит преобразование входной информации в выходную. Обычно под информацией понимают некоторые сведения, символы, знаки. Статистическая теория: понятие информации характеризуется как устранение неопределён.

Информация определяется как сведение является объектом хранения, передачи и приёма. Информация передаётся с помощью сигнала. В основе количественной оценки получение информации лежит представление о передачи сообщения, как о случайном стохастическом процессе во времени.

Устраняют неопределённость с помощью испытаний, чем выше неопределённость, тем выше ценность информации.

Степень неопределённости зависит от числа значений, которые может принимать величина и исхода событий.

За меру количества информации определяется случайная величина H(А):

где-вероятностьiисхода.

Знак минус стоит как компенсация H(А)-это энтропия опыта А (формулу придумал Клод Шинон).

Чем большеH(A), тем больше мера незнания.

Накопление сведений о некоторой системе уменьшает энтропию. Информация это определённый вклад в энтропию.

Пусть дана x-система.

если
, то

где

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

Информация не является материальной или энергетической категорией, она не когда не создаётся, а только передаётся и принимается, но может утрачиваться, исчезать.

Согласно второму закону термодинамики энтропия увеличивается параллельно с разрушением организованных структур стремясь к хаотическому вероятностному состоянию.

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

-двоичная единица или бит.

x-система связаны

y-система

I(x,y)=H(x)+H(y)-H(x,y), где

H(x,y)-энтропия объединённой системы.

, где,

Для непрерывного сигнала.

где(x)-плотность вероятности величиныx. Шинонский подход не учитывает семантического содержания.

33.Понятие эргодического источника. Избыточность.

На практике встречаются эргодические источники, в которых корреляционные связи распространяется на конечное число предшествующих источников. В эргодическом источнике
корреляционные связи отсутствуют, т.е.

Математическим представлением сообщений создаваемых эргодическими источниками являются цепь Маркова.

Цепью Маркова n-порядка называют последовательность, зависимость испытаний при которой, вероятность некоторого исхода
вiиспытании зависит от исходов имевших место в каких-либоnпредыдущих испытаниях, но не зависит от более ранних исходов.

В эргодическом источнике nпорядка распределения
приk=1,2,…,mне остаётся постоянной, а зависит от того, какие были последниеnбукв сообщений.

вероятность выбораqбуквы из алфавита.

Число возможных состояний определяется:
, гдеmэто алфавита,n-порядок,M-число возможных состояний источника.

Для определения полной энтропии необходимо:

если M=1, то получаем классическую формулу Шинона.

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

R-избыточность, показывает эффективность работы источника.

Причиной Rявляется однозначность и опеорная вероятность выбора между сообщениями.

Количество информации

Введение

2. Неопределенность, количество информации и энтропия

3. Формула Шеннона

4. Формула Хартли

5. Количество информации, получаемой в процессе сообщения

Список использованной литературы

Введение

По определению А.Д. Урсула - «информация есть отраженное разнообразие». Количество информации есть количественная мера разнообразия. Это может быть разнообразие совокупного содержимого памяти; разнообразие сигнала, воспринятого в процессе конкретного сообщения; разнообразие исходов конкретной ситуации; разнообразие элементов некоторой системы… - это оценка разнообразия в самом широком смысле слова.

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

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

Разнообразие необходимо при передаче информации. Нельзя нарисовать белым по белому, одного состояния недостаточно. Если ячейка памяти способна находиться только в одном (исходном) состоянии и не способна изменять свое состояние под внешним воздействием, это значит, что она не способна воспринимать и запоминать информацию. Информационная емкость такой ячейки равна 0.

Минимальное разнообразие обеспечивается наличием двух состояний. Если ячейка памяти способна, в зависимости от внешнего воздействия, принимать одно из двух состояний, которые условно обозначаются обычно как «0» и «1», она обладает минимальной информационной ёмкостью.

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

1 бит (bit - сокращение от англ. binary digit - двоичное число) - единица измерения информационной емкости и количества информации, а также и еще одной величины - информационной энтропии, с которой мы познакомимся позже. Бит, одна из самых безусловных единиц измерения. Если единицу измерения длины можно было положить произвольной: локоть, фут, метр, то единица измерения информации не могла быть по сути никакой другой.

На физическом уровне бит является ячейкой памяти, которая в каждый момент времени находится в одном из двух состояний: «0» или «1».

Если каждая точка некоторого изображения может быть только либо черной, либо белой, такое изображение называют битовым, потому что каждая точка представляет собой ячейку памяти емкостью 1 бит. Лампочка, которая может либо «гореть», либо «не гореть» также символизирует бит. Классический пример, иллюстрирующий 1 бит информации - количество информации, получаемое в результате подбрасывания монеты - “орел” или “решка”.

Количество информации равное 1 биту можно получить в ответе на вопрос типа «да»/ «нет». Если изначально вариантов ответов было больше двух, количество получаемой в конкретном ответе информации будет больше, чем 1 бит, если вариантов ответов меньше двух, т.е. один, то это не вопрос, а утверждение, следовательно, получения информации не требуется, раз неопределенности нет.

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

Количество информации мы будем обозначать символом I, вероятность обозначается символом P. Напомним, что суммарная вероятность полной группы событий равна 1.

2.Неопределенность, количество информации и энтропия

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

Ситуация максимальной неопределенности предполагает наличие нескольких равновероятных альтернатив (вариантов), т.е. ни один из вариантов не является более предпочтительным. Причем, чем больше равновероятных вариантов наблюдается, тем больше неопределенность, тем сложнее сделать однозначный выбор и тем больше информации требуется для этого получить. Для N вариантов эта ситуация описывается следующим распределением вероятностей: {1/N, 1/N, … 1/N}.

Минимальная неопределенность равна 0, т.е. эта ситуация полной определенности, означающая что выбор сделан, и вся необходимая информация получена. Распределение вероятностей для ситуации полной определенности выглядит так: {1, 0, …0}.

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия.

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

Рис. 1. Поведение энтропии

для случая двух альтернатив.

На рисунке 1. показано поведение энтропии для случая двух альтернатив, при изменении соотношения их вероятностей (p, (1-p)).

Максимального значения энтропия достигает в данном случае тогда, когда обе вероятности равны между собой и равны?, нулевое значение энтропии соответствует случаям (p0=0, p1=1) и (p0=1, p1=0).

Рис. 2. Связь между энтропией и количеством информации.

Количество информации I и энтропия H характеризуют одну и ту же ситуацию, но с качественно противоположенных сторон. I - это количество информации, которое требуется для снятия неопределенности H. По определению Леона Бриллюэна информация есть отрицательная энтропия (негэнтропия).

Когда неопределенность снята полностью, количество полученной информации I равно изначально существовавшей неопределенности H.

При частичном снятии неопределенности, полученное количество информации и оставшаяся неснятой неопределенность составляют в сумме исходную неопределенность. Ht + It = H.

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

3.Формула Шеннона

В общем случае, энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P: {p0, p1, …pN-1}, т.е. H=F(N, P). Расчет энтропии в этом случае производится по формуле Шеннона, предложенной им в 1948 году в статье "Математическая теория связи".

В частном случае, когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов, т.е. H=F(N). В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. на 20 лет раньше.

Формула Шеннона имеет следующий вид:

Рис. 3. Нахождение логарифма b по основанию a - это нахождение степени, в которую нужно возвести a, чтобы получить b.

Напомним, что такое логарифм.

Логарифм по основанию 2 называется двоичным:

log2(8)=3 => 23=8

log2(10)=3,32 => 23,32=10

Логарифм по основанию 10 -называется десятичным:

log10(100)=2 => 102=100

Основные свойства логарифма:

1. log(1)=0, т.к. любое число в нулевой степени дает 1;

2. log(ab)=b*log(a);

3. log(a*b)=log(a)+log(b);

4. log(a/b)=log(a)-log(b);

5. log(1/b)=0-log(b)=-log(b).

Знак минус в формуле (1) не означает, что энтропия - отрицательная величина. Объясняется это тем, что pi1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма, поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

интерпретируется как частное количество информации, получаемое в случае реализации i-ого варианта. Энтропия в формуле Шеннона является средней характеристикой - математическим ожиданием распределения случайной величины {I0, I1, … IN-1}.

Пример расчета энтропии по формуле Шеннона. Пусть в некотором учреждении состав работников распределяется так: ? - женщины, ? - мужчины. Тогда неопределенность, например, относительно того, кого вы встретите первым, зайдя в учреждение, будет рассчитана рядом действий, показанных в таблице 1.

Таблица 1.

Ii=log2(1/pi), бит

pi*log2(1/pi), бит

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

Таблица 2.

Ii=log2(1/pi), бит

pi*log2(1/pi), бит

4.Формула Хартли

Формула Хартли - частный случай формулы Шеннона для равновероятных альтернатив.

Подставив в формулу (1) вместо pi его (в равновероятном случае не зависящее от i) значение, получим:

таким образом, формула Хартли выглядит очень просто:

Из нее явно следует, что чем больше количество альтернатив (N), тем больше неопределенность (H). Эти величины связаны в формуле (2) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации - битам.

Энтропия будет являться целым числом лишь в том случае, если N является степенью числа 2, т.е. если N принадлежит ряду: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048…}

Рис. 3. Зависимось энтропии от количества равновероятных вариантов выбора (равнозначных альтернатив).

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

Например, если известно, что в результате определения того, что интересующий нас Коля Иванов живет на втором этаже, было получено 3 бита информации, то количество этажей в доме можно определить по формуле (3), как N=23=8 этажей.

Если же вопрос стоит так: “в доме 8 этажей, какое количество информации мы получили, узнав, что интересующий нас Коля Иванов живет на втором этаже?”, нужно воспользоваться формулой (2): I=log2(8)=3 бита.

5.Количество информации, получаемой в процессе сообщения

До сих пор были приведены формулы для расчета энтропии (неопределенности) H, указывая, что H в них можно заменять на I, потому что количество информации, получаемое при полном снятии неопределенности некоторой ситуации, количественно равно начальной энтропии этой ситуации.

Но неопределенность может быть снята только частично, поэтому количество информации I, получаемой из некоторого сообщения, вычисляется как уменьшение энтропии, произошедшее в результате получения данного сообщения.

Для равновероятного случая, используя для расчета энтропии формулу Хартли, получим:

Второе равенство выводится на основании свойств логарифма. Таким образом, в равновероятном случае I зависит от того, во сколько раз изменилось количество рассматриваемых вариантов выбора (рассматриваемое разнообразие).

Исходя из (5) можно вывести следующее:

Если, то - полное снятие неопределенности, количество полученной в сообщении информации равно неопределенности, которая существовала до получения сообщения.

Если, то - неопределенности не изменилась, следовательно, информации получено не было.

Если, то => , если, => . Т.е. количество полученной информации будет положительной величиной, если в результате получения сообщения количество рассматриваемых альтернатив уменьшилось, и отрицательной, если увеличилось.

Если количество рассматриваемых альтернатив в результате получения сообщения уменьшилось вдвое, т.е. , то I=log2(2)=1 бит. Другими словами, получение 1 бита информации исключает из рассмотрения половину равнозначных вариантов.

Рассмотрим в качестве примера опыт с колодой из 36 карт.

Рис. 4. Иллюстрация к опыту с колодой из 36-ти карт.

Пусть некто вынимает одну карту из колоды. Нас интересует, какую именно из 36 карт он вынул. Изначальная неопределенность, рассчитываемая по формуле (2), составляет H=log2(36)5,17 бит. Вытянувший карту сообщает нам часть информации. Используя формулу (5), определим, какое количество информации мы получаем из этих сообщений:

Вариант A. “Это карта красной масти”.

I=log2(36/18)=log2(2)=1 бит (красных карт в колоде половина, неопределенность уменьшилась в 2 раза).

Вариант B. “Это карта пиковой масти”.

I=log2(36/9)=log2(4)=2 бита (пиковые карты составляют четверть колоды, неопределенность уменьшилась в 4 раза).

Вариант С. “Это одна из старших карт: валет, дама, король или туз”.

I=log2(36)-log2(16)=5,17-4=1,17 бита (неопределенность уменьшилась больше чем в два раза, поэтому полученное количество информации больше одного бита).

Вариант D. “Это одна карта из колоды".

I=log2(36/36)=log2(1)=0 бит (неопределенность не уменьшилась - сообщение не информативно).

Вариант D. “Это дама пик".

I=log2(36/1)=log2(36)=5,17 бит (неопределенность полностью снята).

Энтропия (теория информации)

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

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

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

Формальные определения

Определение с помощью собственной информации

Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X , имеющей конечное число значений: I (X ) = − logP X (X ). Тогда энтропия будет определяться как: От основания логарифма зависит единица измерения информации и энтропии: бит , нат или хартли .

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n ) рассчитывается по формуле:

Эта величина также называется средней энтропией сообщения . Величина называется частной энтропией , характеризующей только i -e состояние.

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

В общем случае b -арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где p i является вероятностью a i (p i = p (a i ) ) определяется формулой:

Определение энтропии Шеннона связано с понятием термодинамической энтропии . Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Альтернативное определение

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет условиям:

Свойства

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию − 2(0,5log 2 0,5) = 1 бит на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: . Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

1. Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
2. Количество энтропии не всегда выражается целым числом бит.

Математические свойства

Эффективность

Исходный алфавит, встречающийся на практике, имеет вероятностное распределение, которое далеко от оптимального. Если исходный алфавит имел n символов, тогда он может быть сравнён с «оптимизированным алфавитом», вероятностное распределение которого однородно. Соотношение энтропии исходного и оптимизированного алфавита - это эффективность исходного алфавита, которая может быть выражена в процентах.

Из этого следует, что эффективность исходного алфавита с n символами может быть определена просто как равная его n -арной энтропии.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .

Вариации и обобщения

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):

где i - это состояние, зависящее от предшествующего символа, и p i (j ) - это вероятность j , при условии, что i был предыдущим символом.

Так, для русского языка без буквы « » .

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Так, для описания потерь со стороны источника (то есть известен посланный сигнал), рассматривают условную вероятность получения приёмником символа b j при условии, что был отправлен символ a i . При этом канальная матрица имеет следующий вид:

	b 1	b 2	…	b j	…	b m
a 1			…		…
a 2			…		…
…	…	…	…	…	…	…
a i			…		…
…	…	…	…	…	…	…
a m			…		…

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а сумма всех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника - p (b j ) . Потери, приходящиеся на передаваемый сигнал a i , описываются через частную условную энтропию:

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

Означает энтропию со стороны источника, аналогично рассматривается - энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можно получить p (a i ) , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия, или энтропия объединения , предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B ) , где A , как всегда, характеризует передатчик, а B - приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий p (a i b j ) , и для полного описания характеристик канала требуется только одна матрица:

p (a 1 b 1)	p (a 1 b 2)	…	p (a 1 b j )	…	p (a 1 b m )
p (a 2 b 1)	p (a 2 b 2)	…	p (a 2 b j )	…	p (a 2 b m )
…	…	…	…	…	…
p (a i b 1)	p (a i b 2)	…	p (a i b j )	…	p (a i b m )
…	…	…	…	…	…
p (a m b 1)	p (a m b 2)	…	p (a m b j )	…	p (a m b m )

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером j даст p (b j ) , сумма строки с номером i есть p (a i ) , а сумма всех элементов матрицы равна 1. Совместная вероятность p (a i b j ) событий a i и b j вычисляется как произведение исходной и условной вероятности,

Условные вероятности производятся по формуле Байеса . Таким образом имеются все данные для вычисления энтропий источника и приёмника:

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

H (A B ) = −	∑	∑	p (a i b j )logp (a i b j ).
	i	j

Единица измерения - бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов - отправленного и полученного. Путём несложных преобразований также получаем

Взаимная энтропия обладает свойством информационной полноты - из неё можно получить все рассматриваемые величины.

История

Примечания

См. также

Ссылки

• Claude E. Shannon. A Mathematical Theory of Communication (англ.)
• С. М. Коротаев.

4.ЭНТРОПИЯ И ИНФОРМАЦИЯ

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

Неопределенность может иметь разное происхождение. Один из ее видов – неизвестность – рассматривается теорией познания и философией; такого типа неопределенность возникает, когда мы, например, задаем вопрос «Есть ли жизнь на других планетах?» или «Существуют ли другие цивилизации?» и т.п.

Другой вид неопределенности – расплывчатость, размытость, – например, «Сколько надо взять песчинок, чтобы образовать небольшую кучу»? С неопределенностью этого типа мы встречаемся в квантовой механике. На её основе построена нелокальная версия термодинамики, которая способна ответить на сходный вопрос: «сколько надо иметь частиц, чтобы образовать макроуровень и каково квантовое рассеяние этого числа»?. Эта неопределенность объективна, для нее характерно, что она неустранима в процессе измерений. В математике такой неопределенностью занимается теория размытых множеств. Следует попутно отметить, что размытость – характерное свойство языка: «в комнату (какую?) вошел высокий (какого роста?) молодой (какого конкретно возраста?) человек (кто он?) и т.п.

Третий вид неопределенности – случайность . В ее основе лежат статистические закономерности, устанавливаемые теорией вероятности. Этот вид неопределенности используется статистической физикой и совместно с неопределённостью второго типа в квантовой механике. Отличительная особенность статистической неопределенности заключается в том, что для нее можно установить количественную меру, о которой пойдет речь далее.

Оставим пока в стороне вопрос о практической значимос888ти статистической меры неопределенности, сосредоточив внимание на её сущности. Рассмотрим несколько простейших ситуаций, которые будем именовать опытами А,BиC. Предполагается, что читателю знакомы элементы теории вероятности.

О п ы т А будет заключаться в бросании монеты. В этом опыте возможны два исхода (k =2): “орел или решка”. Очевидно, вероятность каждого исхода(i =1,2).

О п ы т B– бросание игральной шестигранной кости. В этом опыте возможны уже шесть исходов (k =6). Вероятность каждого исхода.

О п ы т C предполагает одновременное бросание двух костей. Для этого опыта k =36 и.

Оценка неопределённости результатов опытов есть оценка трудности предугадывания исхода опыта. Интуитивно ясно, что из всех описанных ситуаций опыт С имеет максимальную неопределённость, поскольку число исходов здесь самое большое и заранее предвидеть исход этого опыта труднее всего.

Чтобы перейти к количественной оценке неопределённости сформулируем основные требования к функции, которая должна играть роль меры неопределённости. Будем обозначать эту функцию буквой H .

П е р в о е требование. Функция Н должна монотонно возрастать с увеличением числа исходов опыта.

В т о р о е требование. Функция Н должна быть равна нулю, если имеется единственный исход (k =1). Это означает, что если возможен лишь один исход, то никакой неопределённости не возникает и результат опыта можно предвидеть безошибочно.

Т р е т ь е требование. Обратим внимание на то, что один опыт С можно рассматривать как два опыта В, и потребуем, чтобы суммарное значение энтропии двух опытов В было равно энтропии опыта С

или в общем случае не для двух, а n простых опытов

Если бы третье требование не соблюдалось, то оценка неопределённости опыта С оказалась бы противоречивой и зависела бы от субъективной трактовки самого опыта – считать ли, что имел место опыт С, или всё же кости упали не одновременно и имели место два опыта В. Принятие этого требования равносильно введению свойств аддитивности для будущей оценки неопределённости. По умолчанию принимается, что рассматриваемые элементы (кости) не взаимодействуют между собой. В термодинамической трактовке это равносильно принятию идеальной системы.

Решим функциональное уравнение (4.1) относительно функции . Для этого дифференцируем обе части выражения (4.1-1) поk , используя требование монотонности функции:

Теперь дифференцируем (4.1) по n

Разделим уравнение (4.2) на (4.3)

что равносильно

Интегрируя это выражение, используя для правой части табличный интеграл, находим

где – постоянная интегрирования.

Из последнего выражения

Так как с увеличением k энтропия растёт (первое требование), тоC >0, и это выражение можно переписать в следующем окончательном виде:

,a >1.

Из него следует, что оно удовлетворяет также второму требованию. Выбор основания логарифмов при a >1не имеет значения и определяет лишь выбор единицы измерения неопределённости. Чаще всего применяют двоичные или натуральные логарифмы. Если используют двоичные логарифмы, то за единицу измерения неопределённости принимают неопределённость опыта, который имеет два равновероятных исхода (опыт А). Такая ситуация отвечает энтропии одной элементарной компьютерной ячейки, в которой хранится либо 0 либо 1. Для этой ячейки

Такая единица измерения называется битом (от англ.binarydiget– двоичная единица).

Итак, при k равновероятных исходах неопределённость опыта составляет

где p – вероятность исхода опыта.

Если учесть, что для равновероятных исходов

то, умножая (4.4) на единицу в виде суммы вероятностей , получаем

Каждый член правой части этого выражения можно рассматривать как вклад отдельного исхода в общую неопределённость опыта. В случае равновероятных исходов вклад каждого из них в общую неопределенность опыта одинаков и формула (4.5) сворачивается в (4.4).

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

Выражение (4.5) можно записать в компактной форме

Если число опытов N , то с учётом аддитивности энтропии

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

Рис. 4.1. Зависимость энтропии для двух исходов опыта

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

Так как только приp =0 илиp =1, то энтропия опыта равна нулю только в случае, когда одна из вероятностей равна единице и, следовательно, все остальные равны нулю. Это обстоятельство хорошо согласуется со смыслом величиныH как меры неопределенности: в этом случае опыт вообще не содержит никакой неопределенности, так как результат опыта можно предвидеть заранее.

На рис.4.1 изображен график функции H для двух исходов опыта, из которого видно, как меняется энтропия при изменении одного из исходов опыта от нуля до единицы. Из графика следует, что максимальное значение энтропии соответствует равновероятным событиям,. При этом максимальное значение энтропии

В общем случае, т. е. не для двух, а k исходов опыта, максимальное значение энтропии соответствует.

Тот факт, что максимум энтропии отвечает равновероятным событиям, согласуется со смыслом энтропии. Действительно, в случае равновероятных событий нельзя отдать предпочтение ни одному исходу и таким образо8м предвидеть результат труднее всего.

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

Если неопределенность до опыта составляла Н (априорная неопределенность ), а после опыта –(апостериорная неопределенность ), то очевидно, неопределенность, устраненная в ходе опыта, составит:

Эта разность носит название количества информации .

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

Количество информации, как и энтропия, измеряется в битах. Один бит информации – это количество информации, сообщающее о том, какое из двух равновероятных событий имело место. Например, количество информации, заключающееся в одной элементарной ячейке ЭВМ, содержащей либо 0, либо 1, составляет один бит.

Рассмотрим пример, в котором бы фигурировала апостериорная неопределенность. Пусть методом перебора вариантов ведется поиск корня некоторого уравнения с точностью до полуцелого числа. Предварительно известно, что значение корня находится в интервале от 1 до 100, так что следует перебрать 200 вариантов. Тогда неопределенность значения корня в равновероятном варианте (4.4) составит H = log 2 200 = 13,3 бит.

Пусть проведена проверка 150 вариантов возможных значений корня, но корень не найден. Однако получена ли некоторая информация о значении корня? Несомненно, и чтобы ее определить, необходимо сначала найти остаточную (апостериорную) неопределенность: Н 1 =log 2 (200 – 150) = 5,6. Тогда искомое количество информации составит= 13,3 – 5,6 = 7,7 бит.

Условная энтропия. Рассмотрим понятие количества информации на примере передачи сигналов. Пусть передается группа сигналов азбукой Морзе:

        

До получения очередного символа на приемном конце существует неопределенность «какой сигнал будет отправлен?» Эту неопределенность можно характеризовать энтропией «на один символ» (4.6) при числе исходов k= 3 (точка, тире, пробел) с вероятностями р i (i= 1, 2, 3). Вероятности появления на приемном конце точки, тире или пробела, т.е. вероятности (частоты) употребления символов конкретного языка специалистам известны из статистического анализа большого объема текстов на этом языке. Подсчитав энтропию на один символ, по формуле (4.6) легко определить общую энтропию сообщения (4.7). В данном примере 10 символов, включая пробел и, следовательно, N = 10.

Итак, на приемном конце до получения сообщения существовала априорная неопределенность (4.7) или на один знак (4.6). После получения сообщения неопределенность была устранена и получена информация I=H– 0.

Однако такая простая ситуация возникает, если сообщение передается без помех (канал без шума ). Если имеется шум, то его действие приводит к тому, что переданный символ может либо остаться прежним (i-м), либо быть случайно подмененным любым другим (n-м) символом. Вероятность такой подмены по обозначению р(y n  x i), где х относится к переданному сигналу, а y к принимаемому сигналу в приемнике. В канале без помех y n = x i . Вероятность р(y n  x i) носит название условной вероятности x i) -–вероятность того, что отправленный i-й сигнал соответствует n-му сигналу на приемном конце. Конечно, эту ситуацию можно рассматривать и со стороны передатчика, используя условные вероятности вида р(x i y n). В этом случае р(x i y n) – вероятность того, что принятый на приемном конце n-й сигнал соответствует i-му сигналу на передающей стороне. Понятие условной вероятности вводит условную энтропию как функцию условной вероятности. В общем виде это записывается в следующих обозначениях:

I(X,Y) = H(X) – H(XY)

I(X,Y) = H(Y) – H(YX)

В этих идентичных выражениях условная энтропия играет роль апостериорной энтропии, а количество информации есть мера соответствия двух случайных объектов Х и Y.

Эта мера позволяет понять связь между понятием информации и её количеством . Информация есть отражение одного объекта другим. В данном примере такими объектами являются приемник и передатчик. Среднее же количество информации и есть числовая характеристика полноты этого отражения, степени соответствия, наконец,степени взаимодействия этих объектов. Но при взаимодействии объекты оказывают влияние друг на друга, и мы привыкли при этом различать причину и следствие.Количественное описание информации это другой тип описания взаимодействий, никак не связанный с классическими причинно-следственными описаниями . Такой тип связи характерен для НВТ.

Здесь полезно обратиться к п.3.6, где уже касались ограничений классического, причинно-следственного механизма при описании взаимодействий в открытой системе.

4.3.Энтропия непрерывного множества. Ранее была рассмотренаэнтропия дискретного множества. Это означает, что подразумевались системы, где число возможных исходов (элементов множества) конечно. Однако приходится часто сталкиваться с ситуациями, когда число элементов может быть сколь угодно велико. Из теории вероятностей известно, что в этом случае следует иметь дело не с вероятностью отдельного исхода, которая равна нулю, а с плотностью распределения вероятности. Эта функция обладает таким свойством, что величинаесть вероятность того, что интересующая нас переменнаяx (значение корня в примере п.4.2.) примет значения, заключенные в интервале отx доx+dx .

Теперь для оценки неопределенности необходимо прибегнуть к энтропии непрерывного множества, которая по аналогии с энтропией дискретного множества (4.5) имеет вид

. (4.9)

В качестве примера использования этой функции, попытаемся оценить неопределенность опыта, связанного со случайным поиском в заданном интервале значения корня (см. п.4.2) при отсутствии ограничения на точность поиска.

Повышая требования к точности ответа, можно ожидать сколь угодно большого числа возможных исходов опыта. При этом вероятность каждого исхода стремится к нулю, а искомый корень может принимать все возможные (бесчисленные) значения в заданном числовом интервале от 0 до 200. Попробуем использовать для этой же задачи энтропию непрерывного множества. Введем отрезок длиной l =x 1 –x 0 относительных единиц. Вероятность обнаружить значение корня на участке dx составляет dx/1 . С другой стороны, эта же вероятность по определению. Следовательно, для равновероятного случая=dx /l и= 1/l. Подставляя это значение в (4.), несложно получить H = log 2 l= 5,6 бит.

Сравним полученный результат с примером в п.4.2. В случае дискретного множества в энтропии используется число дискретных интервалов на выделенном отрезке, а в случае непрерывного множества – относительная длина самого отрезка . Заметим, что длина должна быть выражена в относительной форме, в противном случае под логарифмом появилась бы размерная величина. Масштаб приведения к относительной форме не имеет для информационной энтропии принципиального значения, поскольку с самого начала энтропия введена с точностью до множителя (до постоянной интегрирования, см процедуру интегрирования в п.4.1).

Энтропия непрерывного множества или дифференциальная энтропия (4.9) обладает большинством свойств энтропии дискретного множества.

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

4.4.Энтропия как мера разнообразия, неупорядоченности, хаоса. До сих пор понятие энтропии связывалось с неопределенностью. Энтропия допускает и другое толкование. Представим себе систему, состоящую из камеры, в которой находятсяN шаровmтипов, отличающихся, например, цветом. Предполагается, чтоNдостаточно большое число. Обозначим долю шаровi -го типа (цвета) –. Если произвести опыт над системой, заключающийся в извлечении наугад одного шара, то энтропия одного опыта согласно (4.6) составит:

При этом принято, что размеры шаров одинаковы, в противном случае вероятность извлечения шаров i -того типа не будет точно соответствовать их доле в камере. Энтропия всех опытов над системой

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

Первая из двух функций характеризует степень неупорядоченности системы или степень разнообразия в ней с учётом выбранного признака для различения элементов системы (цвета шаров). Если бы в камере находились шары одного типа, тогда одно из значений вероятностиp =z равнялось бы единице, а все остальные – нулю, и энтропия приняла бы нулевое значение. Это означало бы, что система полностью упорядочена, или, что то же самое – в системе отсутствует разнообразие по оцениваемому признаку (цвету).

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

По аналогии с только что рассмотренным примером формулой (4.11) можно оценивать неупорядоченность потока смеси каких-либо веществ. В этом случае – концентрацияi -го компонента в мольных долях;N – расход потока или число молекул, проходящее через некоторое сечение в единицу времени. Поскольку числоN в практических задачах всегда очень велико, можно перейти к иному масштабу для энтропии. Например, поделив левую и правую части на число Авогадро, получим

где F – расход потока, кмоль/ед. времени. Обозначение энтропии в новом масштабе оставлено прежним.

Таким образом, энтропия оценивает разнообразие элементов в системе по некоторому определенному признаку, который может нас интересовать в той или иной задаче; см п. 4.6 и 4.7.

Обратим внимание, что выражение (4.10) с точностью до множителя совпадает с термодинамическим выражением для мольной энтропии смешения идеального газа

S= –R, (4.13)

где R– газовая постоянная.

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

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

4.5.Связь информационной энтропии с физикой. Понятие энтропии впервые было введено в термодинамику Клаузисом как соотношение, связывающее элементарное приращение энтропииdS с элементарным количеством теплотыdQ при температуреТ

dS = dQ/T (4.14)

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

Энтропия Больцмана. Рассмотрим основанное на статистическом подходе известное уравнение Больцмана

где k B – постоянная Больцмана,k B =1,3810Дж/К;W– число микросостояний.

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

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

Проследим на весьма упрощённой модели, как появляются эти новые свойства, связанные с понятием энтропии Больцмана.

Для наглядности возьмем систему всего из десяти частиц (N =10), распределённых на четырёх энергетических уровнях, имеющих относительные величины энергии 1, 2, 3 и 4. Общая энергия системы равна 20 относительным единицам. Задача заключается в том, чтобы высказать некоторые соображения относительно того состояния, которое примет система, предоставленная самой себе, т.е. относительно того, как распределятся частицы по уровням энергии.

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

Так, одно из возможных макросостояний в рассматриваемой системе из десяти частиц таково: на первом энергетическом уровне находится одна частица (N 1 =1), на втором располагаются восемь частиц (N 2 =8) и одна занимает третий уровень (N 3 =1). Четвертый уровень не занят. Общая энергия равна 11+82+13+ 40=20. Предположим, что частицы пронумерованы. Тогда данное макросостояние можно было бы осуществлять различным способом (через различные микросостояния), помещая, например, на уровеньcэнергией 1 поочерёдно частицы с номером 1, 2, 3, 4, 5 и т.д., т.е. осуществляя разные перестановки частиц, не нарушая макросостояния системы.

. (4.16)

Здесь r – число энергетических уровней; в данном примереr = 4.

Если теперь перейти к другому макросостоянию, т.е. взять иное распределение частиц по энергетическим уровням, например, N 1 =2,N 2 =7,N 3 =0 иN4=1 (общая энергия 21+72+14 = 20), то число способов осуществления данного макросостоянияWоказывается равным 360.