 |
Понятие информационной энтропии.
|
|
|
|
Извечтно,что из-за этого внешнего сходства величину Log2K в теории информации также называют энтропией и обозначают символом H.
Информационная энтропия – это мера неопределённости состояния некоторой случайной величины (физической системы) с конечным или счётным числом состояний. Случайная величина( с.в. ) – это величина, которая в результате эксперимента или наблюдения принимает числовое значение, заранее неизвестно какое.
Итак, пусть X – случайная величина, которая может принимать N различных значений x1, x2, … xN; если все значения с.в. X равновероятны, то энтропия (мера неопределённости) величины X равна:
H(X) = Log2 N. (2.5)
Замечание. Если случайная величина (система) может находиться только в одном состоянии (N=1), то её энтропия равна 0. Фактически это уже не случайная величина. Неопределённость системы тем выше, чем больше число её возможных равновероятных состояний.
Энтропия и количество информации измеряются в одних и тех же единицах – в битах.
Определение. 1 бит – это энтропия системы с двумя равновероятными состояниями.
Пусть система X может находиться в двух состояниях x1 и x2 с равной вероятностью, т.е. N = 2; тогда её энтропия H(X) = Log2 2 = 1 бит. Пример такой системы даёт нам монета, при подбрасывании которой выпадает либо орёл (x1), либо решка (x2). Если монета «правильная», то вероятность выпадения орла или решки одинаковая и равна 1/2.
Дадим ещё одно определение единицы измерения информации.
Определение. Ответ на вопрос любой природы (любого характера) содержит 1 бит информации, если он с равной вероятностью может быть
«да» или «нет».
Пример. Игра в «пусто-густо». Вы прячете мелкий предмет в одной руке и предлагаете партнёру угадать, в какой руке вы его спрятали. Он спрашивает вас «в левой руке?» (или просто выбирает руку: левую или правую). Вы отвечаете «да», если он угадал, или «нет», в противном случае. При любом варианте ответа партнёр получает 1 бит информации, а неопределённость ситуации полностью снимается.
|
|
|
Рассмотрим несколько задач на применение формулы Хартли.
Задача 1. на применение формулы Хартли.
Некто задумал натуральное число в диапазоне от 1 до 32. Какое минимальное число вопросов надо задать, чтобы гарантированно угадать задуманное (выделенное) число. Ответы могут быть только «да» или «нет».
Комментарий. Можно попытаться угадать задуманное число простым перебором. Если повезёт, то придётся задать только один вопрос, а при самом неудачном варианте перебора придётся задать 31 вопрос. В предложенной задаче нужно определить минимальное число вопросов, с помощью которых вы гарантированно определяете задуманное число.
Решение. По формуле Хартли можно вычислить количество информации, которое необходимо получить для определения выделенного элемента x из множества целых чисел {1,2,3 ……, 32}. Для этого необходимо получить Н = Log2 32 = 5 бит информации. Вопросы надо задавать так, чтобы ответы на них были равновероятны. Тогда ответ на каждый такой вопрос будет приносить 1 бит информации. Например, можно разбить числа на две равные группы от 1 до 16 и от 17 до 32 и спросить, в какой группе находится задуманное число. Далее, аналогично следует поступить с выделенной группой, которая содержит уже лишь 16 чисел, и т.д. Пусть, например, задумано число 7.
Вопрос №1: Задуманное число принадлежит множеству {17.. 32}? Ответ «нет» приносит вам 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1.. 16}.
Вопрос №2: Задуманное число принадлежит множеству {1.. 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {1.. 8}.
|
|
|
Вопрос №3: Задуманное число принадлежит множеству {1.. 4}? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {5.. 8}.
Вопрос №4: Задуманное число принадлежит множеству {7; 8}? Ответ «да» приносит вам ещё 1 бит информации. Мы теперь знаем, что число принадлежит множеству {7; 8}.
Вопрос №5: Задуманное число равно 8? Ответ «нет» приносит вам ещё 1 бит информации. Мы теперь знаем, что задуманное число равно 7. Задача решена. Было задано пять вопросов, в ответ получено 5 бит информации и определено задуманное число. É
Количество информации. Формула Шеннона.
Известно, что дальнейшее развитие теория информации получила в работах Клода Шеннона, американского инженера и математика (1916 – 2001), который являлся одним из создателей математической теории информации.
В своих работах К. Шеннон определил количество информации через энтропию - величину, известную в термодинамике и статистической физике как мера разупорядоченности системы, а за единицу количества информации принял то, что впоследствии назвали битом (bit).
Здесь для дальнейшего изложения необходимо использовать некоторые понятия теории вероятности: случайное событие, опыт, вероятность события, случайная величина. В окружающем нас мире происходят различные события, причем случайным называют событие, которое может наступить или не наступить в результате некоторого испытания, опыта или эксперимента. Будем обозначать события заглавными буквами A, B, C и т.д. Количественная мера возможности наступления некоторого события A называется его вероятностью и обозначается как p(A), p – от английского probability. Чем более возможно наступление случайного события, тем больше его вероятность: если A более возможно чем B, то p(A) > p(B). Вводится понятие достоверного события – событие, которое обязательно наступит. Это событие обозначают W и полагают, что его вероятность p(W) = 1. Невозможным называют событие, которое никогда не произойдёт. Его обозначают «и полагают, что его вероятность p(«) = 0. Для вероятностей всех остальных событий A выполняется неравенство p(«) < p(A) < p(W), или 0 < p(A) < 1.
Для событий вводится понятие суммы и произведения. Сумма событий A+B – это событие, которое состоит в наступлении события A или В. Произведение событий A*B состоит в одновременном наступлении события A и B. События A и B несовместны, если они не могут наступить вместе в результате одного испытания. Вероятность суммы несовместных событий равна сумме их вероятностей. Если А и В несовместные события, то p(A+B) = p(A) + p(B).
|
|
|
События A1, A2, A3, …An образуют полную группу, если в результате опыта обязательно наступит хотя бы одно из них. Если события A1, A2, A3, …An попарно несовместны и образуют полную группу, то сумма их вероятностей p1+p2+p3+ …. pn =1. Если они при этом ещё и равновероятны, то вероятность каждого равна p = 1/n, где n – число событий. Вероятность события определяется как отношение числа благоприятных событию исходов опыта к общему числу исходов. Частота события – эмпирическое приближение его вероятности. Она вычисляется в результате проведения серии опытов как отношение числа опытов, в которых событие наступило к общему числу опытов. При большом числе
опытов (испытаний) частота события стремится к его вероятности.
Вывод формулы Шеннона
К. Шеннон, используя подход Р. Хартли, обратил внимание на то, что при передаче словесных сообщений частота (вероятность) использования различных букв алфавита не одинакова: некоторые буквы используются очень часто, другие - редко.
Рассмотрим алфавит Am состоящий из m символов. Обозначим через pi вероятность (частоту) появления i-ого символа в любой позиции передаваемого сообщения, состоящего из n символов. Один i – ый символ
алфавита несёт количество информации равное -Log2(pi). Перед логарифмом стоит «минус» потому, что количество информации величина неотрицательная, а Log2(x) <0 при 0<x<1.
На месте каждого символа в сообщении может стоять любой символ алфавита Am; количество информации, приходящееся на один символ сообщения, равно среднему значению информации по всем символам алфавита Am:
(3.1) i =1
Общее количество информации, содержащееся в сообщении из n символов
равно:
(3.2)
Если все символы алфавита Am появляются с равной вероятностью,
|
|
|
то все pi = p. Так как Σрi = 1, то p = 1/m.).
=
Вывод: формула Шеннона (3.2) в случае, когда все символы алфавита равновероятны, переходит в формулу Хартли (2.2).
В общем случае количество энтропии H произвольной системы X (случайной величины), которая может находиться в m различных состояниях x1, x2, … xm c вероятностями p1, p2, … pm, вычисленное по формуле Шеннона, равно
(3.3)
Напомним, что p1+ p2+ … +pm = 1. Если все pi одинаковы, то все состояния системы X равновероятны; в этом случае pi = 1/m, и формула
(3.3) переходит в формулу Хартли (2.5): H(X) = Log2(m).
Замечание. Количество энтропии системы (случайной величины) Х не зависит от того, в каких конкретно состояниях x1, x2, … xm может находиться система, но зависит от числа m этих состояний и от
вероятностей p1, p2, … pm, с которыми система может находиться в этих состояниях. Это означает, что две системы, у которых число состояний одинаково, а вероятности этих состояний p1, p2, … pm равны (с точностью до порядка перечисления), имеют равные энтропии.
|
|
|
