Взаимная информация и ее свойства. Условная и безусловная взаимная информация

Определим теперь информацию, содержащуюся в одном ансамбле относительно другого, например, в принятом сигнале относительно переданного сообщения. Для этого рассмотрим сообщение двух дискретных ансамблей A и B , вообще говоря, зависимых. Его можно интерпретировать как пару ансамблей сообщений, либо как ансамбли сообщения и сигнала, с помощью которого сообщение передаётся, либо как ансамбли сигналов на входе и выходе канала связи и т. д. Пусть P(a k ,b l )совместная вероятность реализаций a k и b l . Cовместной энтропией ансамблей A и B будем называть:

Введём также понятие условной энтропии:

(2.7)

где P(a k / b l )- условная вероятность a k , если имеет место b l , здесь математические..

Из теоремы умножения вероятностей следует, что .

Для условной энтропии справедливо двойное неравенство:

Рассмотрим два крайних случая:

1. Равенство имеет место в том случае, когда, зная реализацию , можно точно установить реализацию . Другими словами, содержит полную информацию об .

2. Другой крайний случай, когда имеет место, если события и независимые. В этом случае знание реализации не уменьшает неопределённости , т.е. не содержит ни какой информации об А.

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

Подставляя в эту формулу значения H(A) и H(A/B) выразим взаимную информацию через распределение вероятностей:

Если воспользоваться теоремой умножения , то можно записать в симметричной форме т.к. :

(2.12)

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

Сформулируем основные свойства взаимной информации:

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

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

3.

4. , причём равенство имеет место, когда по реализации можно точно установить реализацию .

5. Полагая и учитывая, что получим:

(2.14)

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

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

Если - среднее время передачи одного сообщения, то разделив на формулы H(A/B) и I(A,B) и обозначая:

, , (2.15)

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

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

Производительность источника передаваемого сигнала .

“производительность канала”, то есть полная собственная информация о принятом сигнале за единицу времени.

Величина представляет собой скорость “утечки” информации при прохождении через канал, а - скорость передачи посторонней информации, не имеющий отношения к и создаваемой присутствующими в канале помехами. Соотношение между и зависит от свойств канала. Так, например, при передаче телефонного сигнала по каналу с узкой полосой пропускания, недостаточной для удовлетворительного воспроизведения сигнала, и с низким уровнем помех теряется часть полезной информации, но почти не получается бесполезной. В этом случае . Если же расширяется полоса, сигнал воспроизводится точно, но в паузах ясно прослушиваются “наводки” от соседнего телефонного канала, то, почти не теряя полезной информации, можно получить много дополнительной, как правило, бесполезной информации и .

Эффективное кодирование дискретных сообщений

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

, (2.17)

где - число кодовых символов, a - число сообщений, передаваемых в секунду.

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

Но это отношение представляет среднее число кодовых символов, приходящихся на одно элементарное сообщение. Таким образом, для возможности кодирования и однозначного декодирования сообщения необходимо, чтобы среднее число двоичных символов на сообщение было не меньше энтропии . Является ли это условие достаточным?

Одна из основных теорем теории информации утверждает, что оно “почти достаточно”. Точнее, содержание теоремы кодирования для источника заключается в том, что передавая двоичные символы со скоростью симв/с можно закодировать сообщения так, чтобы передавать их со скоростью:

(сообщений в секунду),

где - сколь угодно малая величина.

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

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

Рассмотрим несколько примеров.

Так, если элементарными сообщениями являются русские буквы и они передаются равновероятно и независимо, то . Каждую букву можно закодировать последовательностью из пяти двоичных символов, поскольку существует 32 такие последовательности.

Разумеется, таким же равномерным кодом можно закодировать и буквы в связном русском тексте, и именно так часто поступают на практике. Но можно обойтись значительно меньшим числом символов на букву. Для русского литературного текста и, следовательно, возможен способ эффективного кодирования (или кодирования со сжатием сообщения), при котором в среднем на букву русского текста будет затрачено немногим более 1,5 двоичных символа, то есть на 70% меньше, чем при примитивном коде.

Существует довольно много способов сжатия сообщений или сокращения избыточности текста. Так, например:”Эта фр. напис. сокращ. и тем не м. мож. надеят., что Вы пойм. её прав.” В предыдущей фразе удалось уменьшить число букв, а следовательно и символов, если её кодировать равномерным кодом почти на 40%.

Другая возможность заключается в том, чтобы кодировать не отдельные буквы, а целые слова.

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

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

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

Тема 2.4. Информация в непрерывных сигналах

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

Разобьём область значений на небольшие интервалы протяжённостью . Вероятность того, что лежит в интервале , +, то есть , приблизительно равна , причём приближение тем точнее, чем меньше интервал . Степень неожиданности такого события равна . Если значения в пределах конечного интервала заменить значениями в начале интервала, то непрерывный ансамбль заменится дискретным, а его энтропия определится как:

Будем теперь увеличивать точность определения значения , уменьшая интервал . В пределе, при должна получиться энтропия непрерывной случайной величины:

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

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

(2.20)

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

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

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

В качестве примера найдём дифференциальную энтропию случайной величины с нормальным распределением вероятности:

, (2.23)

где математическое ожидание, а - дисперсия .

Подставив (2.23) в (2.20), найдём:

Первый интеграл по общему свойству плотности вероятности равен 1, а второй – по определению дисперсии равен . Окончательно

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

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

Тема 2.5. Пропускная способность канала связи

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

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

бит/ симв.

(где максимизация производится по всем многомерным распределениям вероятностей Р(А))

Можно также определить пропускную способность С канала в расчёте на единицу времени.

Вычислим пропускную способность симметричного канала без памяти

(2.26)

Величина в данном случае легко вычисляется, поскольку условная (переходная) вероятность принимает только два значения: , если и (1-Р), если .

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

(2.27)

Следовательно Н(В/А) не зависит от распределения вероятности в ансамбле А, а определяется только переходными вероятностями канала. Это свойство сохраняется для всех моделей с аддитивным шумом.

Подставив (2.27) в (2.26) получим:

Поскольку в правой части только член Н(В) зависит от распределения вероятности Р(А), то максимизировать необходимо именно его.

Максимальное значение Н(В) равно log m и реализуется оно тогда, когда все принятые символы равновероятны и независимы друг от друга. Легко убедиться, что это условие удовлетворяется, если входные символы равновероятны и независимы, поскольку в этом случае

При этом и

Отсюда пропускная способность в расчёте на единицу времени

Для двоичного симметричного канала (m=2) пропускная способность в двоичных единицах в единицу времени

Зависимость от Р согласно формуле (2.31)

При Р=1/2 пропускная способность двоичного канала С=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить совсем не передавая сигналы по каналу, а выбирая их наугад (например, по результатам бросания монеты), то есть при Р=1/2 последовательности на выходе и входе канала независимы. Случай С=0 называется обрывом канала. То, что пропускная способность при P=1 в двоичном канале такая же, как при Р=0 (канал без шумов), объясняется тем, что при Р=1 достаточно все выходные символы инвертировать (то есть заменить 0 на 1 и 1 на 0), чтобы правильно восстановить входной сигнал.

Пропускная способность непрерывного канала вычисляется аналогично. Пусть, например, канал имеет ограниченную полосу пропускания шириной F. Тогда сигналы U(t) и Z(t) соответственно на входе и выходе канала по теореме. Котельникова определяются своими отсчётами, взятыми через интервал 1/(2F), и поэтому информация, проходящая по каналу за некоторое время Т, равна, сумме количества информации, переданной за каждый такой отсчёт. Пропускная способность канала на один такой отсчёт:

Здесь U и Z – случайные величины – сечения процессов U(t) и Z(t) на входе и выходе канала соответственно и максимум берётся по всем допустимым входным сигналам, то есть по всем распределениям U.

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

Вычислим пропускную способность непрерывного канала без памяти с аддитивным белым гауссовским шумом, имеющим полосу пропускания шириной F, если средняя мощность сигнала . Мощность (дисперсию) шума в полосе F обозначим . Отсчёты выходного и входного сигналов, а также шума N связаны равенством:

Так как N имеет нормальное распределение с нулевым математическим ожиданием, то и условная плотность вероятности при фиксированном U будет так же нормальной – с математическим ожиданием U и дисперсией .

Пропускная способность на один отсчёт определятся по формуле (2.32):

Согласно (2.24) условная дифференциальная энтропия h(Z/U) нормального распределения не зависит от математического ожидания и равна . Поэтому для нахождения следует найти такую плотность распределения , при которой максимизируется h(Z). Из (2.33) учитывая, что U и N независимые случайные величины имеем для дисперсий

Таким образом, дисперсиия фиксирована, так как и заданы. Как известно, при фиксированной дисперсии максимальная дифференциальная энтропия обеспечивается нормальным распределением. Из (2.33) видно, что при нормальном одномерном распределении U распределение Z будет так же нормальным и, следовательно, обеспечивается максимум дифференциальной энтропии (2.24).

(2.34)

Переходя к пропускной способности С в расчёте на секунду, заметим, что информация, переданная за несколько отсчётов, максимальна в том случае, когда отсчёты сигналов независимы. Этого можно достичь, если сигнал U(t) выбрать так, чтобы его спектральная плотность была равномерной в полосе F. Отсчёты разделённые интервалами, кратными 1/(2F), взаимно некоррелированы, а для гауссовских величин некоррелированность означает независимость. Поэтому пропускную способность С (за секунду) можно найти, сложив пропускные способности (2.35) для 2F независимых отсчётов:

(2.36)

Она реализуется, если U(t) – гауссовский процесс с равномерной спектральной плотностью в полосе частот F (квазибелый шум).

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

Соотношение (2.36) называется формулой Шеннона. Эта формула имеет важное значение в теории информации, так как определяет зависимость пропускной способности рассматриваемого непрерывного канала от таких его технических характеристик, как ширина полосы пропускания и отношение сигнал шум. Формула Шеннона указывает на возможность обмена полосы пропускания на мощность сигнала и наоборот. Однако поскольку С зависит от F линейно, а от – по логарифмическому закону, компенсировать возможное сокращение полосы пропускания увеличением мощности сигнала, как правило, не выгодно. Более эффективным является обратный обмен мощности сигнала на полосу пропускания.

Максимальный объём информации, которую можно в среднем передать по непрерывному каналу за время ,

Для гауссовского канала

(2.37)

Заметим, что при Выражение (2.37) совпадает с характеристикой названной ёмкостью (объёмом) канала.

Тема 2.6. Теорема К. Шеннона

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

(A)

то существует способ кодирования (преобразования сообщения в сигнал на входе) и декодирования (преобразования сигнала в сообщение на выходе канала), при при котором вероятность ошибочного декодирования и ненадёжность могут быть сколь угодно малы. Если же (A)>C, то таких способов не существует.

Рассмотрим содержание теоремы Шеннона.

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

Но является ли это условие достаточным?

Конечно, при C>H’(A) можно передавать такие сигналы, что достигнет значения H’(A). Но – это скорость передачи информации о сигнале В, а не о сообщении А. Поэтому вопрос сводится к тому, можно ли установить такое соответствие (код) между сообщением А и сигналом В чтобы вся информация, полученная на выходе канала о сигнале В, была в то же время информацией о сообщении А? (Чтобы преобразования между А и В были обратимыми)

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

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

Если бы двоичный канал был без помех и допускал передачу двоичных символов со скоростью символ/с, то пропускная способность в расчёте на секунду была бы

В этом случае данная теорема свелась бы к теореме о кодировании источника.

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

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

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

Тема 2.7. Информация в непрерывных сообщениях. Эпсилон-энтропия

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

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

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

В дальнейшем удобнее будет оперировать не с передаваемым непрерывным сообщением А, а с первичным сигналом В и его реализациями b(t). Дело в том, что непрерывное сообщение А может и не быть функцией времени либо быть функцией нескольких аргументов (например, при телевизионном вещании). Первичный сигнал B(t) в современных системах связи всегда является функцией времени. В тех случаях, когда и сообщение является функцией времени (например, при телефонной связи), первичный сигнал B(t) точно повторяет функцию A(t) и отличается от сообщения только физической природой [например A(t) – звуковое давление, B(t) – ток]. Будем считать, что преобразование сообщения в первичный сигнал обратимо и точность воспроизведения B(t) предопределяет точность воспроизведения A(t). Поэтому в дальнейшем под сообщением будем понимать первичный сигнал В(t).

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

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

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

Если при приёме сигналов учитывается статистический характер сигналов, помех и решений приёмника, то мы говорим, что приём сигналов трактуется как статистическая задача. Впервые такую постановку задачи рассмотрел В.А. Котельников.

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

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

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

ЛЕКЦИЯ 2

ВЗАИМНАЯ ИНФОРМАЦИЯ.

ЦЕЛЬ ЛЕКЦИИ: На базе понятия условной энтропии дать определение взаимной информации, рассмотреть свойства и представить вывод формулы для вычисления среднего количества взаимной информации.

Измеряй все, доступное измерению, и делай недоступное измерению доступным. Галилео Галилей

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

или H(x,y) = H(x) + H x (y)

Условная энтропия удовлетворяет следующим условиям.:

0 ≤ H x (y ) ≤ H (y ),

H x (y ) = 0 , когда по реализации ансамбля X можно точно установить реализацию ансамбля Y ;

H x (y ) = H (y ), когда ансамбли Х и У независимы и знание реализации X не прибавляет информации об Y ;

H (y ) > H x (y ) – общий случай, когда знание реализации X снижает первоначальную неопределенность Y .

Взаимная информация .

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

Введем обозначение взаимной информации I (x , y ). В соответствии со свойством 5 энтропии, можем записать соотношение

I (x,y )= H (x ) – H (x,y ),

которое будет определять меру взаимной информации для любых пар (x , y ) ансамблей Х и У.

В выражении Н(х) – априорная энтропия, Н(x , y ) – остаточная энтропия после получения сведений об ансамбле Х . Тогда I (x , y ) будет характеризовать полную информацию, содержащуюся в ансамбле У об ансамбле Х .

Проиллюстрируем графически энтропию системы и информацию

Рис. 1 Графическое отображение взаимной информации.

Верхние раздельные овалы - при отсутствии связи между ансамблями переменных Х и У ;

Нижние совмещенные овалы - при наличии статистической связи между ансамблями Х и У .

Изучим ансамбли Х и У , характеризующие систему. Энтропию ансамбля Х изобразим овалом с площадью Н(Х) : чем больше энтропия, тем больше площадь. Энтропия ансамбля У - второй овал с площадью Н(У ). Если ансамбли статистически независимы, т.е. связь между ними отсутствует, овалы не пересекаются. Полная энтропия системы равна сумме энтропий, т. е. сумме площадей.

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

Н(Х,У) = Н(Х) + Н(У) - I(Х, Y )

Чем больше взаимная информация, тем теснее связь, тем меньше энтропия Н(Х,У).

Из свойства 5 энтропии следует

H(X,Y) = H(X) + H X (Y)

H(X,Y) = H(Y) + H Y (X )

а также

H(X) + H X (Y) = H(Y) + H Y (X)

H(X) –H X (Y) = H(Y) – H Y (X)

Сравнив и , отметим, что выражение характеризует взаимное равенство информации об ансамбле Х , если известен ансамбль У , и обратно, знание об ансамбле У , если известен ансамбль Х .

I (X , Y ) – называется средней взаимной информацией, содержащейся в ансамблях Х и У .

Свойства взаимной информации .

1. I (X,Y ) = I (Y,X ). Взаимная информация симметрична.
2. I (X , Y ) ≥ 0 . Взаимная информация всегда положительна.

3 . I (X , Y ) = 0 тогда и только тогда, когда ансамбли Х и У независимы.

1. I (X , Y ) = H (X ) – H X (Y ) = H (Y ) – H Y (X ) = H (X ) + H (Y ) – H (X , Y ), т. е. в случае наступления совместного события H (X ) + H (Y ) = H (X , Y ) взаимная информация отсутствует.
2. I(X,Y) ≤ min{H(X),H(Y)}. Взаимная информация не может быть больше информации о каждом ансамбле в отдельности.
3. I(X,Y) ≤ min {log‌‌ ‌‌|X|, log|Y|}. Логарифмическая мера каждого из ансамблей в отдельности больше или равна взаимной информации.

7. Взаимная информация I (X , Y ) имеет максимум (является выпуклой функцией распределения вероятностей).

В общем случае свойство 4 определяет взаимную информацию через энтропию объединенной системы H (X , Y ) и энтропию отдельных её частей H (X ) и H (Y ) рис.1.

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

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

H(X)=M[ - log P(X)], H(Y)=M[ - log P(Y)], H(X,Y)=M[ - log P(X,Y)]

Тогда выражение примет вид

I(X,Y) =M[ - logP(X) – logP(Y) + log(X,Y)].

Преобразовав, получим

Выражение преобразуем с использованием свойства математического

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

У= [у=φ(х)]

представляет собой набор множества значений случайных величин Важно понимать - для вычисления математического ожидания величины у необязательно знать распределение вероятностей p y (y ) для у . Если распределение p x (x ) по ансамблю Х известно , то

Тогда, если p (x i ) m элеменᴛᴏʙ ансамбля Х , а p (y j ) вероятность реализации любого из n элеменᴛᴏʙ ансамбля У , то выражение количества взаимной информации будет иметь вид

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

Марковская модель источника.

Изучим случайные последовательности из произвольного числа событий. Если элементы случайной последовательности – вещественные числа, то такие последовательности называются случайными процессами . Номер элемента в последовательности трактуется как момент времени, в который появилось данное значение

В общем случае множество значений времени может быть непрерывным или дискретным, множество значений случайной последовательности может быть также непрерывным или дискретным

Случайный процесс х 1, x 2, … со значениями x i , алфавита Х, (i = 1, 2, …) задан, если для любых n указан способ вычисления совместных распределений вероятностей p (x 1 ,… x n ). Проще всего задать случайный процесс, предположив, что его значения в различные моменты времени независимы и одинаково распределены.

где p (x i ) – вероятность появления x i в момент i . Важно понимать - для описания такого процесса достаточно указать вероятности p (x ) для всех x (всего I Х I – 1 вероятностей). Важно понимать - для описания более ᴄᴫᴏжных моделей процессов следует опираться на свойство стационарности, позволяющее упростить математические выкладки. Процесс называется стационарным, если для любых n и t имеет место равенство

p(x 1 , …, x n ) = p(x 1+ t x n+ t ),

причем x i = x 1+ t , i = 1, … n . Случайный процесс стационарен, если вероятность любой последовательности не изменится при её сдвиге во времени. Числовые характеристики, в частности математическое ожидание, стационарных процессов не зависят от времени. Рассматривая стационарные процессы, мы можем вычислять независящие от времени информационные характеристики случайных процессов. Пример стационарного процесса – процесс, значения которого независимы и одинаково распределены.

К. Шеннон так определяет дискретный источник сообщений: “ Можно считать, что дискретный источник создает сообщение символ за символом. Он будет выбирать последовательные символы с некоторыми вероятностями, зависящими, вообще говоря, как от предыдущих выборов, так и от конкретного рассматриваемого символа. Физическая система или математическая модель системы, которая создает такую последовательность символов, определяемую некоторой заданной совокупностью вероятностей, называется вероятностным процессом. По этой причине можно считать, что дискретный источник представляется некоторым вероятностным процессом. Обратно, любой вероятностный процесс, который создает дискретную последовательность символов, выбираемых из некоторого конечного множества, может рассматриваться как дискретный источник”.

Статистическая структура такого процесса и статистические свойства источника вполне определяются одномерными p (i ), двумерными p (i , j ) вероятностями появления элеменᴛᴏʙ сообщений на выходе источника. Как указывалось, если между последовательными элементами сообщения отсутствует статистическая связь, то статистическая структура сообщения полностью определяется совокупностью одномерных вероятностей. Появление того или иного элемента сообщения на выходе источника можно рассматривать как определенное событие, характеризующееся своей вероятностью появления. Важно понимать - для совокупности событий вместе с их априорными вероятностями появления существует понятие ансамбля .

Примерами дискретного источника могут служить:

1. Печатные тексты на различных языках.
2. Непрерывные источники сообщений, которые превращены в дискретные с помощью некоторого процесса кванᴛᴏʙания (кванᴛᴏʙанная речь, телевизионный сигнал.

3. Математические случаи, когда просто определяется абстрактно некоторый вероятностный процесс, который порождает последовательность символов.

Подобные источники создают представляют собой вероятностные процессы, известные как дискретные Марковские процессы

В общем случае результат может быть описан следующим образом. Существует конечное число возможных “состояний” системы : S 1 , S 2 ,. . . , S n . Кроме того, имеется совокупность переходных вероятностей pi (j ), т. е. вероятностей того, что система, находящаяся в c остоянии S i , перейдет затем в состояние S j . Для того чтобы использовать ϶ᴛόᴛМарковский процесс в качестве источника сообщений, нужно только предположить, что при каждом переходе из одного состояния в другое создается одна буква. Состояния будут соответствовать “остатку влияния” предшествовавших букв

В графическом примере “состоянием” является узловая точка схемы, а переходные вероятности и создаваемые при этом буквы указаны около соответствующих линий.

Такой источник из четырех букв A , B , C , В , имеющих, соответственно, переходные вероятности 0,1; 0,4; 0,3; 0,2, возвращаясь в узловую точку после

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

На дискретный источник можно распространить такие характеристики случайного сигнала, как эргодичность и стационарность. Полагая источник эргодическим, можно “… отождествлять средние значения вдоль некоторой последовательности со средним значением по ансамблю возможных последовательностей (причем вероятность расхождения равна нулю)”. Например, относительная частота буквы А в частной бесконечной последовательности будет с вероятностью единица равняться её относительной частоте по ансамблю последовательностей.

Простейшей моделью источника, порождающего зависимые сообщения, является Марковский источник. Случайный процесс называют цепью Маркова связности s , если для любых n и для любых x = (x 1 , …, x n ) алфавита X справедливы соотношения

p(x) = p(x 1 , …, x s )p(x s+ 1 / x 1 , … , x s )p(x s+2 /x 2 , …,x s+1 )…p(x n /x n-s ,…,x n-1 ).

Марковским процессом связности s называется такой процесс, для которого при n > s p (x n ,…, x n -1 ) = p (x n / x n - s ,…, x n -1 ), т. е. условная вероятность текущего значения при известных s предшествующих не зависит от всех других предшествующих значений.

Описание Марковского процесса задается начальным распределением вероятностей на последовательностях из первых s значений и условными вероятностями p (x n / x n - s ,…, x n -1 ) для всевозможных последовательностей. Если указанные условные вероятности не изменяются при сдвиге последовательностей во времени, Марковская цепь называется однородной . Однородная Марковская цепь связности s = 1 называется простой цепью Маркова. Важно понимать - для её описания достаточно указать распределение вероятностей p (x 1 ) величины х, принадлежащей множеству Х и условные вероятности

π ij = P(x t = j / x t-1 = i), i,j = 0,1,…,M-1 ,

называемые переходными вероятностями цепи Маркова.

Переходные вероятности удобно записывать в виде квадратной матрицы размерности М х М

называемой матрицей переходных вероятностей. Эта матрица – стохастическая (неотрицательная, сумма элеменᴛᴏʙ каждой строки равна 1).

Если p t - стохастический вектор, компоненты которого – вероятности состояний цепи Маркова в момент времени t , т.е. p t =[ p t (0),…, p t (M -1)], где p t (i ) есть вероятность состояния i в момент времени t (I = 0,1,…,

ЛЕКЦИЯ 29. Архитектурная акустикаЦель архитектурной акустики — обеспечение строительными средствами хорошей слышимости естественной речи и музыки, а также звуков, воспроизводимых электроакустической аппаратурой. При проектировании залов к таким средствам относятся их размеры и форма, членение поверхностей стен и потолков различными объемными элементами, обработка их материалами, отражающими или поглощающими звук. В залах могут размещаться специальные звукопоглощающие конструкции, устанавливаться мебель с определенными звукопоглощающими характеристиками....

Свойства взаимной информации

• Взаимная информация является симметричной функцией случайных величин:

• Взаимная информация неотрицательна и не превосходит информационную энтропию аргументов:

В частности, для независимых случайных величин взаимная информация равна нулю:

В случае, когда одна случайная величина (например, Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): X ) является детерминированной функцией другой случайной величины (Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): Y ), взаимная информация равна энтропии:

Условная и безусловная взаимная информация

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

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

Свойства

• Являются симметричными функциями:

• Удовлетворяют неравенствам:

Напишите отзыв о статье "Взаимная информация"

Литература

• Ошибка Lua в Модуль:Sources на строке 530: attempt to index field "wikibase" (a nil value).

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

Раскрывая последнее выражение, получим соотношение для взаимной информации в симметричном виде:

Рассмотрим основные свойства взаимной информации:

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

2. . Равенство достигается при отсутствии помех, т. е. .

3. , где энтропия выхода канала H(B) и условная энтропия определяются аналогично найденным выше значениям энтропии. Данное свойство вытекает из симметрии выражения для взаимной информации.

4. . Данное свойство вытекает из предыдущего. Равенство здесь имеет место, если .

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

Определение взаимной информации наглядно иллюстрируется на рис. 2.

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

Выводы

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

Заключение

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

2. Условная энтропия представляет собой количество информации, которое теряется из-за помех и не поступает получателю.

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

Литература

1. Р.Р. Биккенин, М.Н. Чесноков Теория электрической связи. Случайные процессы. Помехоустойчивая передача дискретной информации: Учебное пособие / СПб., 2001, стр. 121-127.

2. Д.Д. Кловский «Теория электрической связи» М. «Радио и связь», стр. 246-249, 227-231.

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

Значения индекса Dow Jones Industrial Average (DJI)

Ряд процентных приращений котировок, расчитанный по формуле X[t] / X - 1

Для приведения исследуемой непрерывной, по ее сути, переменной к дискретному типу перейдем к ряду процентных приращений, округленных до 0,01 (1%). Подсчет взаимной информации для непрерывных переменных, хотя и возможен технически, но не информативен, в силу очень большого значения n - конечного набора значений признака, принимаемого случайной переменной.

Базовые концепции информационно-теоретических идей, использованных в статье

(Все формулы а также теория заимствованы в: ru.wikipedia.org а также из ряда монографий, которые можно поискать по ключевым словам.)

Теория информация развивалась неразрывно с теорией связи, я не буду отходить от этой традиции.

Что такое информация?

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

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

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

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

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

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

Например, опыт с многократным подкидыванием честной монетки - это система со средней информацией равной 1 Бит (при подстановке в формулу логарифма по основанию 2). При этом, перед каждым подбрасыванием мы ожидаем выпадение решки или орла с равной вероятностью (эти события! независимы! друг от друга) и неопределенность всегда равна 1. А какова будет информационная энтропия этой системы при неравной вероятности выпадения сторон монетки? Скажем, орел выпадает с вероятностью 0,6, а решка - с вероятностью 0,4. Посчитаем и получим: 0,971 Бита. Энтропия системы уменьшилась, так как неопределенность реализации эксперимента уже меньше: мы ожидаем орел чаще, чем решку.

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

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

Итак, посчитаем энтропию источника данных (http://ru.wikipedia.org/):

Средняя информация (или просто энтропия) данного источника данных (посчитанная по логарифму с основанием 2) составляет 2.098 Бит.

Взаимная информация между случайными переменными посчитана через понятие информационной энтропии (http://ru.wikipedia.org/):

Гистограмма значений взаимной информации между зависимой переменной - процентным приращением индекса, посчитанным по ценам закрытия, - и ее значениями со сдвигом от 1 до 250 шагов назад во времени.

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

Вид функции распределения плотности вероятности для полученного набора значений количества взаимной информации:

Сгенерируем искусственный временной ряд для референсных целей. Источником ряда целых чисел, задающих последовательность значений признака был выбран сайт www.random.org . По информации на сайте, они предоставляют действительно случайные числа (в отличие от ГПСЧ, генератора псевдослучайных чисел).

Полученный ряд приращений, со случайно перемешанных хронологическим порядком

На глаз можно отметить насколько более стационарными стали данные.

Этот же ряд с округленными значениями

Гистограмма значений взаимной информации между зависимой переменной и ее значениями со сдвигом от 1 до 250 шагов назад во времени по искусственному временному ряду приращений (с сохранением того же вида функции плотности вероятности на пространстве значений признака)

Вид функции распределения плотности вероятности для данной выборки:

Сравнение 2 рассмотренных случаев расчета взаимной информации

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

Проверим гипотезу о значимости различия (различия вида функции плотности распределения вероятности) двух выборок посчитанных значений взаимной информации - для исходного и искусственного временных рядов. Прибегнув к непараметрическим тестам, посчитаем статистику по методу Колмогорова-Смирнова (тест Колмогорова-Смирнова применяется для сравнения двух независимых выборок значений с целью определить статистическую значимость различий между значениями выборок. Для этой же цели используется U-тест Манна и Уитни).

Результат: p = 0.00 при принятом пороговом уровне значимости 0,05.

Результат U-теста по методу Манна и Уитни: p = 0.00.

Видим, что в обоих случаях гипотеза о различии между выборками значений признака принимается (p меньше 0,05).

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

P.S.: Буду рад комментариям, критике.