Энтропия это параметр оценивающий в информатике

Информационная энтропия

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

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

Содержание

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

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

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

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

Шеннон вывел это определение энтропии из следующих предположений:

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме:

где K — константа (и в действительности нужна только для выбора единиц измерения).

В общем случае b-арная энтропия (где b равно 2,3. ) источника = (S,P) с исходным алфавитом S = <a₁, …, a_n> и дискретным распределением вероятности P = <p₁, …, p_n> где p_i является вероятностью a_i (p_i = p(a_i)) определяется формулой:

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

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

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

где — это состояние, зависящее от предшествующего символа, и — это вероятность , при условии, что был предыдущим символом.

Так, для русского алфавита без буквы « ё » [1]

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

		.		.
			.		.
			.		.
.	.	.	.	.	.	.
			.		.
.	.	.	.	.	.	.
			.		.

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

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

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

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

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

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

		…		…
		…		…
…	…	…	…	…	…
		…		…
…	…	…	…	…	…
		…		…

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

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

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

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

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

Свойства

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

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

1) H(p₁, …, p_n) определена и непрерывна для всех p₁, …, p_n, где p_i [0,1] для всех i = 1, …, n и p₁ + … + p_n = 1. (Заметьте, что эта функция зависит только от распределения вероятностей, а не от алфавита.)

2) Для целых положительных n, должно выполняться следующее неравенство:

3) Для целых положительных b_i, где b₁ + … + b_n = n, должно выполняться равенство:

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

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

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

История

Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

Литература

См. также

Внешние ссылки

Эта статья содержит материал из статьи Информационная энтропия русской Википедии.

Источник

Введение в понятие энтропии и ее многоликость

Как может показаться, анализ сигналов и данных — тема достаточно хорошо изученная и уже сотни раз проговоренная. Но есть в ней и некоторые провалы. В последние годы словом «энтропия» бросаются все кому не лень, толком и не понимая, о чем говорят. Хаос — да, беспорядок — да, в термодинамике используется — вроде тоже да, применительно к сигналам — и тут да. Хочется хотя бы немного прояснить этот момент и дать направление тем, кто захочет узнать чуть больше об энтропии. Поговорим об энтропийном анализе данных.

В русскоязычных источниках очень мало литературы на этот счет. А цельное представление вообще получить практически нереально. Благо, моим научным руководителем оказался как раз знаток энтропийного анализа и автор свеженькой монографии [1], где все расписано «от и до». Счастью предела не было, и я решила попробовать донести мысли на этот счет до более широкой аудитории, так что пару выдержек возьму из монографии и дополню своими исследованиями. Может, кому и пригодится.

Итак, начнем с начала. Шенноном в 1963 г. было предложено понятие меры усредненной информативности испытания (непредсказуемости его исходов), которая учитывает вероятность отдельных исходов (до него был еще Хартли, но это опустим). Если энтропию измерять в битах, и взять основание 2, то получим формулу для энтропии Шеннона
, где Pi это вероятность наступления i-го исхода.

То есть в этом случае энтропия напрямую связана с «неожиданностью» возникновения события. А отсюда вытекает и его информативность — чем событие более предсказуемо, тем оно менее информативно. Значит и его энтропия будет ниже. Хотя открытым остается вопрос о соотношениях между свойствами информации, свойствами энтропии и свойствами различных ее оценок. Как раз с оценками мы и имеем дело в большинстве случаев. Все, что поддается исследованию — это информативность различных индексов энтропии относительно контролируемых изменений свойств процессов, т.е. по существу, их полезность для решения конкретных прикладных задач.

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

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

Пусть есть система, которая каждые 100 тактов переключается между несколькими состояниями и порождает сигнал x (рисунок 1.5), характеристики которого изменяются при переходе. Но какие — нам не известно.

Разбив x на реализации по 100 отсчетов можно построить эмпирическую плотность распределения и по ней вычислить значение энтропии Шеннона. Получим значения, «разнесенные» по уровням (рисунок 1.6).

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

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

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

Так вот, фишка в том, что энтропия связных процессов сближается при усилении их связи. Черт побери, как это красиво-то!

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

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

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

Источник

4.2. Энтропия и информация

Разность Н(β) и Н_α(β), очевидно, показывает, какие новые сведения относительно β получаем, про­изведя опыт α. Эта величина называется информацией относи­тельно опыта β, содержащейся в опыте α.

Данное выражение открывает возможность численного изме­рения количества информации. Запишем ряд следствий:

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

Следствие 2 . Пусть опыт α = β, т.е. просто произведен опыт β. Поскольку он несет полную информацию о себе самом, неопреде­ленность его исхода полностью снимается, т.е. Ηᵦ(β)=0. Тогда I(β,β)=Η(β). Исходя из этого, можно считать, что:

энтропия равна информации относительно опыта, которая со­держится в нем самом.

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

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

2.Информация симметрична относительно последовательности опытов.

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

Какое количество информации требуется, чтобы узнать исход броска монеты?

В данном случае n=2 и события равновероятны, т.е. р₁ = р₂ = 0,5.

Игра «Угадай-ка-4». Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет» Какое количество информации должны получить, чтобы узнать задуманное число, т.е полностью снять начальную неопределенность? Как правильно построить процесс угадывания?

Рис. 1.5. Выборочный каскад

Таким образом, для решения задачи оказалось достаточно 2-х вопро­сов независимо от того, какое число было задумано. Совпадение меж­ду количеством информации и числом вопросов с бинарными ответами неслучайно.

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

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

Легко получить следствие формулы (1.24) для случая, когда все n исходов равновероятны (собственно, именно такие и рассматри­вались в примерах 1.10 и 1.13). В этом случае все

Эта формула была выведена в 1928 г. американским инжене­ром Р. Хартли. Она связывает количество равно­вероятных состояний (n) и количество информации в сообщении (I), что любое из этих состояний реализовалось. Ее смысл в том, что, если некоторое множество содержит n элементов и х принад­лежит данному множеству, то для его выделения (однозначной идентификации) среди прочих требуется количество информации, равное log2n.

Частным случаем применения формулы (1.27) является си­туация, когда n=2ᵏ, подставляя это значение в (1.27), получим:

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

Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта? Как построить угадывание?

Следуя из ранее рассмотренного, справедливы следующие утверждения:

Утверждение 1. Выражение (1.24) является статистическим определением понятия «информация», поскольку в него входят вероятности воз­можных исходов опыта. По сути, дается операционное определе­ние новой величины, т.е. устанавливается процедура (способ) из­мерения величины.

Выражение (1.23) можно интерпретировать следующим образом:

если начальная энтропия опыта H1, а в результате сообщения ин­формации I энтропия становится равной H2 (очевидно, Н1≥ Н2), то I=H1-H2, т.е. информация равна убыли энтропии. В частном случае, если изначально равновероятных исходов было n1, а в результате пе­редачи информации I неопределенность уменьшилась, и число исходов стало n2 (очевидно, n2≤n1), то из (1.27) получается:

Таким образом, справедливо следующее определение:

В случае равновероятных исходов информация равна лога­рифму отношения числа возможных исходов до и после (получения сообщения).

Утверждение 3 . Следствием аддитивности энтропии независимых опытов (1.13) оказывается аддитивность информации. Пусть с выбором од­ного из элементов (X_A) множества А, содержащего n_A элементов, связано формула, информации, а с выбором Х_B из В с n_B элемен­тами информации связано формула и второй выбор никак не свя­зан с первым, то при объединении множеств число возможных со­стояний (элементов) будет n=n_A∙n_B и для выбора комбинации Х_AХ_B потребуется количество информации:

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

Следовательно, для угадывания всей шестизначной комбинации требуется I = 17 бит информации, т.е. нужно задать 17 вопросов. В среднем на один элемент (одну игру) приходится 17/6 = 2,833 вопроса, что близко к значению log₂(7).

Таким образом, справедливо следующее утверждение:

Величина I, определяемая описанным выше образом, показы­вает, сколько в среднем необходимо сделать парных выборов для установления результата (полного снятия неопределенно­сти), если опыт повторить многократно (n→∞).

Утверждение 5. Не всегда с каждым из от­ветов на вопрос, имеющий только с два варианта ответа (такие вопросы называются бинарными), связан ровно 1 бит информации. Ответ на бинарный вопрос может содержать не более 1 бит информации. Информация равна 1 бит только для равновероятных ответов. В остальных случаях она меньше 1 бит.

При угадывании результата броска игральной кости задается вопрос «Выпало 6?». Какое количество информации содержит ответ?

р=1/6, 1-р=5/6, следовательно из (1.24):

Утверждение 6 . Формула (1.24) приводит еще к одному выводу.

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

Утверждение 9. Информация и знание. На бытовом уровне, в науках социаль­ной направленности, например в педагогике «информация» отожде­ствляется с «информированностью», т.е. человеческим знанием, которое, в свою очередь, связано с оценкой смысла информации.

В теории информации же, напротив, информация является мерой нашего незнания чего-либо (но что в принципе может произойти); как только это происходит и узнаем результат, информация, связан­ная с данным событием, исчезает. Состоявшееся событие не несет информации, поскольку пропадает его неопределенность (энтропия становится равной нулю), и согласно (1.23) I=0.

Источник