Информацио́нная энтропи́я — мера неопределённости некоторой системы (в статистической физике или теории информации). Энтропия дискретного источника равна среднему количеству информации, приходящейся на один символШеннон К. Работы по теории информации и кибернетике, 1963. — С. 264. (сообщениеФано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 59., элементУсенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 26.Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 23.) источника. Характеризует непредсказуемость появления какого-либо символа алфавита.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотностью, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии -го порядка, см. ниже) встречаются очень редко, то рассчитанная энтропия языка уменьшается ещё сильнееЛось А. Б., Нестеренко А. Ю., Рожков М. И. Криптографические методы защиты информации, 2016. — С. 64..
Формальные определения В случае равновероятных символов источника информационная энтропия рассчитывается по формуле Хартли:
,
где — мощность (основание, объём) алфавита (количество различных символов алфавита), — количество информации в каждом символе. В общем случае, основание логарифма в определении энтропии может быть любым, большим 1 (так как алфавитом, состоящим только из одного символа, нельзя передавать информацию). Выбор основания логарифма определяет единицу измерения информации. Для информационных систем, основанных на двоичной системе счисления, единицей информации является двоичный символ — бит и основание логарифма . В этом случае энтропия называется двоичной энтропией. В задачах математической статистики более удобным может оказаться применение натурального логарифма (), в этом случае единицей измерения информации является нат.
Для случайной величины , принимающей независимых случайных значений с вероятностями (), для энтропии используется формула Шеннона:
Здесь означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение (для предложений на русском языке — количество информации, содержащейся в конкретной букве, имеющей номер в русском алфавите, ),
— среднее количество информации, приходящейся на один символ (для предложений на русском языке — количество информации на одну букву). Эта величина также называется средней энтропией источника. Величина называется частной энтропией, характеризующей только -e состояние.
Таким образом, энтропия системы является суммой с противоположным знаком всех вероятностей появления состояния (события) с номером , умноженных на их же двоичные логарифмы. Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей, однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).
В случае марковского источника -го порядка, когда условная вероятность появления текущего символа зависит только от предыдущих символов, то есть при наличия вероятностных связей между символами (что имеет место в текстовом сообщении), энтропия источника определяется по формулеВаргаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 18.C. E. Shannon. Prediction and Entropy of Printed English, 1951. — P. 51.:
где — вероятность -го состояния источника, которое определяется символами, предшествующих текущему символу , — число состояний, — условная вероятность выбора источником символа в -ом состоянии, — -ая последовательность из символов, предшествующая символу , — вероятность появления последовательности и .
Клодом Шенноном было уcтановлено, что энтропия английского текста при равна 0.6—1.3 бит/символAngelo Vulpiani, Roberto Livi. The Kolmogorov Legacy in Physics, 2003. — P. 98.. Также с помощью экспериментальных оценок установлено, что энтропия русского языка с учетом вероятностных связей между элементами равна 1.4 бит/символ для разговорной речи, 1.19 бит/символ для литературного текста, 0.83 бит/символ для делового текста. Энтропия французского языка с учетом вероятностных связей между элементами равна 1.5, 1.38, 1.22 бит/символ соответственно.
Определение по Шеннону Клод Шеннон задал требования к измерению энтропии: функция должна быть непрерывной относительно ; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции; в случае, когда все события равновероятны (), увеличение количества событий должно увеличивать значение функции, то есть функция должна быть монотонно возрастающей при увеличении ; Если выбор распадается на два последовательных выбора, то первоначальное значение функции должна быть взвешенной суммой индивидуальных значений функцииШеннон К. Работы по теории информации и кибернетике, 1963. — С. 260..
Эти требования к энтропии можно записать в виде: определена и непрерывна для всех , где для всех и . (Эта функция зависит только от распределения вероятностей, но не от алфавита.) Для целых положительных , должно выполняться следующее неравенство:
Для целых положительных , где , должно выполняться равенство
Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид:
где — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма).
Шеннон определил, что измерение энтропии (), применяемое к источнику информации, может определить требования к пропускной способности канала, необходимой для надёжной передачи информации в виде закодированных двоичных чисел.
Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.
Определение с помощью собственной информации Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины , имеющей конечное число значений:
и собственной информации:
Тогда энтропия определяется как математическое ожидание этой величины:
Единицы измерения информационной энтропии От основания логарифма зависит единица измерения количества информации и энтропии: бит, нат, трит или хартли.
Свойства Энтропия является количеством, определённым в контексте вероятностной модели для источника информации. Например, бросание монеты имеет энтропию: бит на одно кидание (при условии его независимости), а количество возможных состояний равно: возможных состояния (значения) («орёл» и «решка»). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: , а количество возможных состояний равно: возможное состояние (значение) («А») и от основания логарифма не зависит.
Примером запоминающих устройств, в которых используются разряды с энтропией, равной нулю, но с количеством информации, равным одному возможному состоянию, то есть не равным нулю, являются разряды данных записанных в ПЗУ, в которых каждый разряд имеет только одно возможное состояние.
Свойствами энтропии являютсяШеннон К. Работы по теории информации и кибернетике, 1963. — С. 262.: Неотрицательность: . Энтропия равна нулю, когда все вероятности , кроме одной, равны нулю, и эта вероятность равна единице. Максимальное значение энтропии равно и достигается в случае, когда все символы алфавита равновероятны, где — основание алфавита. Энтропия — выпуклая вверх функция распределения вероятностей элементовФомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 56.. Если имеют одинаковое распределение вероятностей элементов, то .
Вариации и обобщения
b-арная энтропия В общем случае b-арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где является вероятностью символа (), определяется формулой:
В частности, при , мы получаем обычную двоичную энтропию, измеряемую в битах. При , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При мы получаем информацию, измеряемую в натах.
Условная энтропия Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия) меньше. Для учёта таких фактов используется условная энтропия.
Условной энтропией (для марковской модели) называется энтропия для алфавита, где известны вероятности появления одного символа после известной последовательности из предыдущих символов :
где — основание алфавита, — -ая последовательность из символов, предшествующая символу , — совместная вероятность появления последовательности и , — условная вероятность появления символа после последовательности Cover, T., King, R. A. convergent gambling estimate of the entropy of English, 1978. — P. 413..
Например, для русского текста без буквы «ё» (так принимается по определению), Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69..
При эта условная энтропия называется энтропией текста.
Условную энтропию можно использовать при определении информационных потерь при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Для описания потерь со стороны источника (то есть известен посланный символ) рассматривают условную вероятность получения приёмником символа при условии, что был отправлен символ . При этом канальная матрица имеет следующий вид: … … … … … … …… … … … … … … … …… … … … … … … …
Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый символ , описываются через частную условную энтропию (условная энтропия источника из принятых символов при фиксированном переданном символе ):
Для вычисления потерь при передаче всех символов используется средняя условная энтропияФомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 60.:
означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо всюду указывается .
Свойства условной энтропииФомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 61.: , , , в случае, когда символы источников и независимы. , в случае, когда символы источников и полностью зависимыУсенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 33.. , .
Энтропия объединения Энтропия объединенияУсенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 32. (совместная энтропия, энтропия произведения) предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления символов источника) и обозначается , где характеризует передатчик, а — приёмник.
Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий , и для полного описания характеристик канала требуется только одна матрица:
… … … … … … … … … … … … … … … … … … … …