Информационная энтропия: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
РоманСузи (обсуждение | вклад) викификация |
QBA-bot (обсуждение | вклад) м откат правок Метка: откат |
||
(не показано 27 промежуточных версий 13 участников) | |||
Строка 1: | Строка 1: | ||
{{Теория информации}} |
{{Теория информации}} |
||
<!-- порядок следования частей будет меняться --> |
<!-- порядок следования частей будет меняться --> |
||
'''Информацио́нная энтропи́я''' — мера неопределённости некоторой системы (в [[статистическая физика|статистической физике]] или [[теория информации|теории информации]]), в частности непредсказуемость появления какого-либо символа [[первичный алфавит|первичного алфавита]]. В последнем случае при отсутствии информационных потерь энтропия численно равна количеству [[информация|информации]] на символ передаваемого сообщения. |
'''Информацио́нная энтропи́я''' — мера неопределённости некоторой системы (в [[статистическая физика|статистической физике]] или [[теория информации|теории информации]]), в частности, непредсказуемость появления какого-либо символа [[первичный алфавит|первичного алфавита]]. В последнем случае при отсутствии информационных потерь энтропия численно равна количеству [[информация|информации]] на символ передаваемого сообщения. |
||
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной |
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной [[частотность]]ю, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии <math>n</math>-го порядка, см. [[#Условная энтропия|ниже]]) встречаются очень редко, то неопределённость уменьшается еще сильнее. |
||
== Формальные определения == |
== Формальные определения == |
||
Информационная '''двоичная энтропия''', при отсутствии информационных потерь, рассчитывается по [[Формула Хартли|формуле Хартли]]: |
Информационная '''двоичная энтропия''', при отсутствии информационных потерь, рассчитывается по [[Формула Хартли|формуле Хартли]]: |
||
<math> |
: <math>I = \log_2 N</math>, |
||
где <math>N</math> — мощность алфавита, <math> |
где <math>N</math> — [[Мощность множества|мощность]] алфавита, <math>I</math> — количество информации в каждом символе сообщения. Для случайной величины <math>x</math>, принимающей <math>n</math> независимых случайных значений <math>x_i</math> с вероятностями <math>p_i</math> (<math>i=1,...n</math>), формула Хартли переходит в формулу Шеннона: |
||
<math>H(x)=-\sum_{i=1}^np_i\log_2 p_i.</math> |
: <math>H(x)=-\sum_{i=1}^np_i\log_2 p_i.</math> |
||
Здесь |
|||
⚫ | |||
: <math>(-\log_2 p_i)</math> означает измеряемое в [[бит]]ах [[количество информации]], содержащейся в том событии, что случайная величина приняла значение <math>x_i</math> (для предложений на русском языке — количество информации, содержащейся в конкретной букве, имеющей номер ''<math>i</math>'' в русском алфавите, <math>i=1,...33</math>), |
|||
: <math>H(x)</math> — количество информации, которое '''в среднем''' приходится на одно событие (для предложений на русском языке — количество информации в среднем на одну букву). |
|||
⚫ | Таким образом, энтропия системы <math>x</math> является суммой с противоположным знаком всех относительных |
||
⚫ | Эта величина также называется '''''средней энтропией сообщения''''' и означает измеряемое в битах среднее количество [[Информация|информации]] на символ передаваемого сообщения. Величина <math>H_{i} = -\log_2{p_i}</math> называется '''''частной энтропией''''', характеризующей только <math>i</math>-e состояние. |
||
⚫ | Таким образом, энтропия системы <math>x</math> является суммой с противоположным знаком всех относительных частотностей появления состояния (события) с номером <math>i</math>, умноженных на их же [[Двоичный логарифм|двоичные логарифмы]]<ref> Данное представление удобно для работы с информацией, представленной в двоичной форме; в общем случае основание логарифма может быть другим.</ref>. Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных [[Плотность вероятности|плотностью распределения вероятностей]], однако полученный функционал будет обладать несколько иными свойствами (см. [[дифференциальная энтропия]]). |
||
В общем случае, основание логарифма в определении энтропии может быть любым, большим 1 (так как алфавитом, состоящим только из одного символа, нельзя передавать информацию); выбор основания логарифма определяет единицу измерения энтропии. Для информационных систем, основанных на двоичной системе счисления, единицей измерения информационной энтропии (собственно, информации) является [[бит]]. В задачах математической статистики более удобным может оказаться применение [[Натуральный логарифм|натурального логарифма]], в этом случае единицей измерения информационной энтропии является [[Нат (теория информации)|нат]]. |
В общем случае, основание логарифма в определении энтропии может быть любым, большим 1 (так как алфавитом, состоящим только из одного символа, нельзя передавать информацию); выбор основания логарифма определяет единицу измерения энтропии. Для информационных систем, основанных на двоичной системе счисления, единицей измерения информационной энтропии (собственно, информации) является [[бит]]. В задачах математической статистики более удобным может оказаться применение [[Натуральный логарифм|натурального логарифма]], в этом случае единицей измерения информационной энтропии является [[Нат (теория информации)|нат]]. |
||
Строка 27: | Строка 32: | ||
Поэтому функция энтропии <math>H</math> должна удовлетворять условиям |
Поэтому функция энтропии <math>H</math> должна удовлетворять условиям |
||
# <math>H(p_1,\;\ldots,\;p_n)</math> определена и непрерывна для всех <math>p_1,\dotsc,p_n</math>, где <math>p_i\in[0,\;1]</math> для всех <math>i=1,\dotsc,n</math> и <math>p_1+\dotsb+p_n=1</math>. ( |
# <math>H(p_1,\;\ldots,\;p_n)</math> определена и непрерывна для всех <math>p_1,\dotsc,p_n</math>, где <math>p_i\in[0,\;1]</math> для всех <math>i=1,\dotsc,n</math> и <math>p_1+\dotsb+p_n=1</math>. (Эта функция зависит только от распределения вероятностей, но не от алфавита.) |
||
# Для целых положительных <math>n</math>, должно выполняться следующее неравенство: |
# Для целых положительных <math>n</math>, должно выполняться следующее неравенство: |
||
#: <math>H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n<H\underbrace{\left(\frac{1}{n+1},\;\ldots,\;\frac{1}{n+1}\right)}_{n+1}.</math> |
#: <math>H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n<H\underbrace{\left(\frac{1}{n+1},\;\ldots,\;\frac{1}{n+1}\right)}_{n+1}.</math> |
||
Строка 33: | Строка 38: | ||
#: <math>H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n= H\left(\frac{b_1}{n},\;\ldots,\;\frac{b_k}{n}\right)+\sum_{i=1}^k\frac{b_i}{n}H\underbrace{\left(\frac{1}{b_i},\;\ldots,\;\frac{1}{b_i}\right)}_{b_i}.</math> |
#: <math>H\underbrace{\left(\frac{1}{n},\;\ldots,\;\frac{1}{n}\right)}_n= H\left(\frac{b_1}{n},\;\ldots,\;\frac{b_k}{n}\right)+\sum_{i=1}^k\frac{b_i}{n}H\underbrace{\left(\frac{1}{b_i},\;\ldots,\;\frac{1}{b_i}\right)}_{b_i}.</math> |
||
Шеннон показал,<ref>{{статья |заглавие=A Mathematical Theory of Communication |издание={{Нп3|Bell System Technical Journal}} |том=27 |номер=3 |страницы=419 |ссылка=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6773024 |doi=10.1002/j.1538-7305.1948.tb01338.x |язык=und |автор=[[Шеннон, Клод|Shannon, Claude E.]] |месяц=7 |год=1948}}</ref> что единственная функция, удовлетворяющая этим требованиям, имеет вид |
Шеннон показал,<ref>{{статья |заглавие=A Mathematical Theory of Communication |издание={{Нп3|Bell System Technical Journal}} |том=27 |номер=3 |страницы=419 |ссылка=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6773024 |doi=10.1002/j.1538-7305.1948.tb01338.x |язык=und |автор=[[Шеннон, Клод|Shannon, Claude E.]] |месяц=7 |год=1948 |archivedate=2016-08-01 |archiveurl=https://web.archive.org/web/20160801132352/http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6773024 }}</ref> что единственная функция, удовлетворяющая этим требованиям, имеет вид |
||
: <math>-K\sum_{i=1}^np(i)\log_2 p(i),</math> |
: <math>-K\sum_{i=1}^np(i)\log_2 p(i),</math> |
||
где <math>K</math> — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма). |
где <math>K</math> — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма). |
||
Строка 42: | Строка 47: | ||
=== Определение с помощью собственной информации === |
=== Определение с помощью собственной информации === |
||
Также можно определить энтропию случайной величины, |
Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины <math>X</math>, имеющей конечное число значений:{{source-ref|Q27473383|pages=16}} |
||
: <math>P_X(x_i)=p_i,\quad p_i\geqslant 0,\;i=1,\;2,\;\ldots,\;n</math> |
: <math>P_X(x_i)=p_i,\quad p_i\geqslant 0,\;i=1,\;2,\;\ldots,\;n</math> |
||
: <math>\sum_{i=1}^n p_i=1</math> |
: <math>\sum_{i=1}^n p_i=1</math> |
||
Строка 58: | Строка 63: | ||
У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: <math>-\sum_{i=1}^\infty\log_2 1=0</math>, а количество '''возможных состояний''' равно: <math>2^0=1</math> '''возможное состояние''' (значение) («А») и от основания логарифма не зависит.<br> Это тоже информация, которую тоже надо учитывать. Примером [[Запоминающие устройства|запоминающих устройств]], в которых используются разряды с энтропией, равной нулю, но с '''количеством информации''', равным одному '''возможному состоянию''', то есть не равным нулю, являются разряды данных записанных в [[Постоянное запоминающее устройство|ПЗУ]], в которых каждый разряд имеет только одно '''возможное состояние'''.<br> |
У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: <math>-\sum_{i=1}^\infty\log_2 1=0</math>, а количество '''возможных состояний''' равно: <math>2^0=1</math> '''возможное состояние''' (значение) («А») и от основания логарифма не зависит.<br> Это тоже информация, которую тоже надо учитывать. Примером [[Запоминающие устройства|запоминающих устройств]], в которых используются разряды с энтропией, равной нулю, но с '''количеством информации''', равным одному '''возможному состоянию''', то есть не равным нулю, являются разряды данных записанных в [[Постоянное запоминающее устройство|ПЗУ]], в которых каждый разряд имеет только одно '''возможное состояние'''.<br> |
||
Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что |
Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для их (данных) зашифровки без потери информации, при оптимальном кодировании. |
||
# Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию или имеют идентичные секции независимо от информации в структуре данных. |
# Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию или имеют идентичные секции независимо от информации в структуре данных. |
||
# Количество энтропии не всегда выражается целым числом битов. |
# Количество энтропии не всегда выражается целым числом битов. |
||
Строка 79: | Строка 84: | ||
В общем случае '''''b''-арная энтропия''' (где ''b'' равно 2, 3, …) источника <math>\mathcal{S}=(S,\;P)</math> с [[первичный алфавит|исходным алфавитом]] <math>S=\{a_1,\;\ldots,\;a_n\}</math> и [[дискретное распределение вероятности|дискретным распределением вероятности]] <math>P=\{p_1,\;\ldots,\;p_n\},</math> где <math>p_i</math> является вероятностью <math>a_i</math> (<math>p_i=p(a_i)</math>), определяется формулой: |
В общем случае '''''b''-арная энтропия''' (где ''b'' равно 2, 3, …) источника <math>\mathcal{S}=(S,\;P)</math> с [[первичный алфавит|исходным алфавитом]] <math>S=\{a_1,\;\ldots,\;a_n\}</math> и [[дискретное распределение вероятности|дискретным распределением вероятности]] <math>P=\{p_1,\;\ldots,\;p_n\},</math> где <math>p_i</math> является вероятностью <math>a_i</math> (<math>p_i=p(a_i)</math>), определяется формулой: |
||
: <math>H_b(\mathcal{S})=-\sum_{i=1}^n p_i\log_b p_i.</math> |
: <math>H_b(\mathcal{S})=-\sum_{i=1}^n p_i\log_b p_i.</math> |
||
В частности, при <math>b=2</math>, мы получаем обычную двоичную энтропию, измеряемую в [[бит]]ах. При <math>b=3</math>, мы получаем тринарную энтропию, измеряемую в [[трит]]ах (один трит имеет источник информации с тремя равновероятными состояниями). При <math>b=e</math> |
В частности, при <math>b=2</math>, мы получаем обычную двоичную энтропию, измеряемую в [[бит]]ах. При <math>b=3</math>, мы получаем тринарную энтропию, измеряемую в [[трит]]ах (один трит имеет источник информации с тремя равновероятными состояниями). При <math>b=e</math> мы получаем информацию, измеряемую в [[Нат (теория информации)|натах]]. |
||
=== Условная энтропия === |
=== Условная энтропия === |
||
Если следование символов алфавита не независимо (например, во [[французский язык|французском языке]] после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия) |
Если следование символов алфавита не независимо (например, во [[французский язык|французском языке]] после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия) меньше. Для учёта таких фактов используется условная энтропия. |
||
'''Условной энтропией''' первого порядка (аналогично для [[Цепь Маркова|Марковской модели]] первого порядка) называется энтропия для алфавита, где известны [[Вероятность|вероятности]] появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний): |
'''Условной энтропией''' первого порядка (аналогично для [[Цепь Маркова|Марковской модели]] первого порядка) называется энтропия для алфавита, где известны [[Вероятность|вероятности]] появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний): |
||
Строка 113: | Строка 118: | ||
|} |
|} |
||
Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал <math>a_i</math>, описываются через частную условную энтропию: |
|||
: <math>H(B\mid a_i)=-\sum_{j=1}^m p(b_j\mid a_i)\log_2 p(b_j\mid a_i).</math> |
: <math>H(B\mid a_i)=-\sum_{j=1}^m p(b_j\mid a_i)\log_2 p(b_j\mid a_i).</math> |
||
Для вычисления потерь при передаче всех сигналов используется общая условная энтропия: |
Для вычисления потерь при передаче всех сигналов используется общая условная энтропия: |
||
Строка 138: | Строка 143: | ||
|} |
|} |
||
Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. |
Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Сумма всех элементов столбца с номером <math>j</math> даёт <math>p(b_j)</math>, сумма строки с номером <math>i</math> есть <math>p(a_i)</math>, а сумма всех элементов матрицы равна 1. Совместная вероятность <math>p(a_ib_j)</math> событий <math>a_i</math> и <math>b_j</math> вычисляется как произведение исходной и условной вероятности: |
||
: <math>p(a_ib_j)=p(a_i)p(b_j\mid a_i)=p(b_j)p(a_i\mid b_j).</math> |
: <math>p(a_ib_j)=p(a_i)p(b_j\mid a_i)=p(b_j)p(a_i\mid b_j).</math> |
||
Условные вероятности производятся по [[Теорема Байеса|формуле Байеса]]. Таким образом, имеются все данные для вычисления энтропий источника и приёмника: |
Условные вероятности производятся по [[Теорема Байеса|формуле Байеса]]. Таким образом, имеются все данные для вычисления энтропий источника и приёмника: |
||
Строка 150: | Строка 155: | ||
== История == |
== История == |
||
В [[1948 |
В [[1948 год]]у, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, [[Шеннон, Клод Элвуд|Клод Шеннон]] предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию [[Термодинамическая энтропия|энтропии]]. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: [[теория информации|теории информации]], которая использует понятие [[вероятность|вероятности]] и [[эргодическая теория|эргодическую теорию]] для изучения статистических характеристик данных и коммуникационных систем, и [[теория кодирования|теории кодирования]], в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных кодов. |
||
Понятие энтропии как меры случайности введено Шенноном в его статье «[[Математическая теория связи (статья)|Математическая теория связи]]» ({{lang-en|A Mathematical Theory of Communication}}), опубликованной в двух частях в [[Bell System Technical Journal]] в 1948 |
Понятие энтропии как меры случайности введено Шенноном в его статье «[[Математическая теория связи (статья)|Математическая теория связи]]» ({{lang-en|A Mathematical Theory of Communication}}), опубликованной в двух частях в [[Bell System Technical Journal]] в 1948 году. |
||
== Примечания == |
|||
⚫ | |||
== См. также == |
== См. также == |
||
Строка 164: | Строка 166: | ||
* [[Расстояние Кульбака — Лейблера]] |
* [[Расстояние Кульбака — Лейблера]] |
||
== |
== Примечания == |
||
⚫ | |||
⚫ | |||
⚫ | |||
== Литература == |
== Литература == |
||
* {{книга|автор=Шеннон К.|заглавие=Работы по теории информации и кибернетике|место={{М.}}|издательство= |
* {{книга|автор=Шеннон К.|заглавие=Работы по теории информации и кибернетике|место={{М.}}|издательство=[[Издательство иностранной литературы]]|год=2002|}} |
||
* {{книга|автор=Волькенштейн М. В.|заглавие=Энтропия и информация|место={{М.}}|издательство=Наука|год=2006|}} |
* {{книга|автор=Волькенштейн М. В.|заглавие=Энтропия и информация|место={{М.}}|издательство=Наука|год=2006|}} |
||
* {{книга|автор=Цымбал В. П.|заглавие=Теория информации и кодирование|место={{К.}}|издательство=Вища Школа|год=2003|}} |
* {{книга|автор=Цымбал В. П.|заглавие=Теория информации и кодирование|место={{К.}}|издательство=Вища Школа|год=2003|}} |
||
* {{книга | автор= Martin, Nathaniel F.G. & England, James W. | заглавие= Mathematical Theory of Entropy | издательство = Cambridge University Press | год = 2011 | isbn = 978-0-521-17738-2 | ref = Martin, England}} |
* {{книга | автор= Martin, Nathaniel F.G. & England, James W. | заглавие= Mathematical Theory of Entropy | издательство = [[Cambridge University Press]] | год = 2011 | isbn = 978-0-521-17738-2 | ref = Martin, England}} |
||
* {{книга|автор=Шамбадаль П.|заглавие=Развитие и приложение понятия энтропии|место=М.|издательство=Наука|год=1967|страниц=280}} |
* {{книга|автор=Шамбадаль П.|заглавие=Развитие и приложение понятия энтропии|место=М.|издательство=Наука|год=1967|страниц=280}} |
||
* {{книга|автор=Мартин Н., Ингленд Дж.|заглавие=Математическая теория энтропии|место=М.|издательство=Мир|год=1988|страниц=350}} |
* {{книга|автор=Мартин Н., Ингленд Дж.|заглавие=Математическая теория энтропии|место=М.|издательство=Мир|год=1988|страниц=350}} |
||
* {{статья|автор=Хинчин А. Я. |ссылка=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=8203&option_lang=rus |заглавие=Понятие энтропии в теории вероятностей |издание=[[Успехи математических наук]] |год=1953 |том=8 |выпуск=3(55) |страницы=3—20 |язык=ru |издательство=[[Математический институт имени В. А. Стеклова РАН|Российская академия наук]] }} |
* {{статья|автор=[[Хинчин, Александр Яковлевич|Хинчин А. Я.]] |ссылка=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=8203&option_lang=rus |заглавие=Понятие энтропии в теории вероятностей |издание=[[Успехи математических наук]] |год=1953 |том=8 |выпуск=3(55) |страницы=3—20 |язык=ru |издательство=[[Математический институт имени В. А. Стеклова РАН|Российская академия наук]] }} |
||
* {{книга|автор=Брюллюэн Л.|заглавие=Наука и теория информации|место=М.|год=1960}} |
* {{книга|автор=Брюллюэн Л.|заглавие=Наука и теория информации|место=М.|год=1960}} |
||
* {{книга|автор=[[Винер, Норберт|Винер Н.]]|заглавие=Кибернетика и общество|место=М.|год=1958}} |
* {{книга|автор=[[Винер, Норберт|Винер Н.]]|заглавие=Кибернетика и общество|место=М.|год=1958}} |
||
Строка 183: | Строка 184: | ||
* {{книга|автор=[[Яглом, Акива Моисеевич|Яглом А. М.]], [[Яглом, Исаак Моисеевич|Яглом И. М.]]|заглавие=Вероятность и информация|место=М.|год=1973}} |
* {{книга|автор=[[Яглом, Акива Моисеевич|Яглом А. М.]], [[Яглом, Исаак Моисеевич|Яглом И. М.]]|заглавие=Вероятность и информация|место=М.|год=1973}} |
||
* {{книга|автор=Волькенштейн М. В.|заглавие=Энтропия и информация|место=М.|издательство=Наука|год=1986|страниц=192}} |
* {{книга|автор=Волькенштейн М. В.|заглавие=Энтропия и информация|место=М.|издательство=Наука|год=1986|страниц=192}} |
||
* {{книга|автор=Верещагин Н.К., Щепин Е.В.|заглавие=Информация, кодирование и предсказание|издательство=ФМОП, МЦНМО|место=М.|год=2012|страниц=238|isbn=978-5-94057-920-5}} |
* {{книга|автор=Верещагин Н. К., Щепин Е. В.|заглавие=Информация, кодирование и предсказание|издательство=ФМОП, МЦНМО|место=М.|год=2012|страниц=238|isbn=978-5-94057-920-5}} |
||
== Ссылки == |
|||
⚫ | |||
⚫ | |||
{{внешние ссылки}} |
{{внешние ссылки}} |
||
[[Категория:Теория информации]] |
[[Категория:Теория информации]] |
||
[[Категория:Кибернетика]] |
[[Категория:Кибернетика]] |
Текущая версия от 12:01, 15 февраля 2024
Информацио́нная энтропи́я — мера неопределённости некоторой системы (в статистической физике или теории информации), в частности, непредсказуемость появления какого-либо символа первичного алфавита. В последнем случае при отсутствии информационных потерь энтропия численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотностью, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии -го порядка, см. ниже) встречаются очень редко, то неопределённость уменьшается еще сильнее.
Формальные определения
[править | править код]Информационная двоичная энтропия, при отсутствии информационных потерь, рассчитывается по формуле Хартли:
- ,
где — мощность алфавита, — количество информации в каждом символе сообщения. Для случайной величины , принимающей независимых случайных значений с вероятностями (), формула Хартли переходит в формулу Шеннона:
Здесь
- означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение (для предложений на русском языке — количество информации, содержащейся в конкретной букве, имеющей номер в русском алфавите, ),
- — количество информации, которое в среднем приходится на одно событие (для предложений на русском языке — количество информации в среднем на одну букву).
Эта величина также называется средней энтропией сообщения и означает измеряемое в битах среднее количество информации на символ передаваемого сообщения. Величина называется частной энтропией, характеризующей только -e состояние.
Таким образом, энтропия системы является суммой с противоположным знаком всех относительных частотностей появления состояния (события) с номером , умноженных на их же двоичные логарифмы[1]. Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей, однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).
В общем случае, основание логарифма в определении энтропии может быть любым, большим 1 (так как алфавитом, состоящим только из одного символа, нельзя передавать информацию); выбор основания логарифма определяет единицу измерения энтропии. Для информационных систем, основанных на двоичной системе счисления, единицей измерения информационной энтропии (собственно, информации) является бит. В задачах математической статистики более удобным может оказаться применение натурального логарифма, в этом случае единицей измерения информационной энтропии является нат.
Определение по Шеннону
[править | править код]Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:
- мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
- в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
- должна быть возможность сделать выбор (в нашем примере — букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.[прояснить]
Поэтому функция энтропии должна удовлетворять условиям
- определена и непрерывна для всех , где для всех и . (Эта функция зависит только от распределения вероятностей, но не от алфавита.)
- Для целых положительных , должно выполняться следующее неравенство:
- Для целых положительных , где , должно выполняться равенство
Шеннон показал,[2] что единственная функция, удовлетворяющая этим требованиям, имеет вид
где — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма).
Шеннон определил, что измерение энтропии (), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. (см. цепи Маркова).
Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.
Определение с помощью собственной информации
[править | править код]Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины , имеющей конечное число значений:[3]
Тогда энтропия определяется как:
Единицы измерения информационной энтропии
[править | править код]От основания логарифма зависит единица измерения количества информации и энтропии: бит, нат, трит или хартли.
Свойства
[править | править код]Энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию:
- бит на одно кидание (при условии его независимости), а количество возможных состояний равно: возможных состояния (значения) («орёл» и «решка»).
У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: , а количество возможных состояний равно: возможное состояние (значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств, в которых используются разряды с энтропией, равной нулю, но с количеством информации, равным одному возможному состоянию, то есть не равным нулю, являются разряды данных записанных в ПЗУ, в которых каждый разряд имеет только одно возможное состояние.
Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для их (данных) зашифровки без потери информации, при оптимальном кодировании.
- Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию или имеют идентичные секции независимо от информации в структуре данных.
- Количество энтропии не всегда выражается целым числом битов.
Математические свойства
[править | править код]- Неотрицательность: .
- Ограниченность: , что вытекает из неравенства Йенсена для вогнутой функции и . Если все элементов из равновероятны, .
- Если независимы, то .
- Энтропия — выпуклая вверх функция распределения вероятностей элементов.
- Если имеют одинаковое распределение вероятностей элементов, то .
Эффективность
[править | править код]Алфавит может иметь вероятностное распределение, далекое от равномерного. Если исходный алфавит содержит символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого — равномерное. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с символами может быть также определена как его -арная энтропия.
Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.
Вариации и обобщения
[править | править код]b-арная энтропия
[править | править код]В общем случае b-арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом и дискретным распределением вероятности где является вероятностью (), определяется формулой:
В частности, при , мы получаем обычную двоичную энтропию, измеряемую в битах. При , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При мы получаем информацию, измеряемую в натах.
Условная энтропия
[править | править код]Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия) меньше. Для учёта таких фактов используется условная энтропия.
Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):
где — это состояние, зависящее от предшествующего символа, и — это вероятность при условии, что был предыдущим символом.
Например, для русского языка без буквы «ё» [4].
Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность получения приёмником символа при условии, что был отправлен символ . При этом канальная матрица имеет следующий вид:
… | … | |||||
---|---|---|---|---|---|---|
… | … | |||||
… | … | |||||
… | … | … | … | … | … | … |
… | … | |||||
… | … | … | … | … | … | … |
… | … |
Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал , описываются через частную условную энтропию:
Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:
означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо всюду указывается (суммируя элементы строки можно получить , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).
Взаимная энтропия
[править | править код]Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается , где характеризует передатчик, а — приёмник.
Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий , и для полного описания характеристик канала требуется только одна матрица:
… | … | ||||
… | … | ||||
… | … | … | … | … | … |
… | … | ||||
… | … | … | … | … | … |
… | … |
Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Сумма всех элементов столбца с номером даёт , сумма строки с номером есть , а сумма всех элементов матрицы равна 1. Совместная вероятность событий и вычисляется как произведение исходной и условной вероятности:
Условные вероятности производятся по формуле Байеса. Таким образом, имеются все данные для вычисления энтропий источника и приёмника:
Взаимная энтропия вычисляется последовательным суммированием по строкам (или по столбцам) всех вероятностей матрицы, умноженных на их логарифм:
Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов: отправленного и полученного. Путём несложных преобразований также получаем
Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины.
История
[править | править код]В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных кодов.
Понятие энтропии как меры случайности введено Шенноном в его статье «Математическая теория связи» (англ. A Mathematical Theory of Communication), опубликованной в двух частях в Bell System Technical Journal в 1948 году.
См. также
[править | править код]- Дифференциальная энтропия (энтропия для непрерывного распределения)
- Взаимная информация
- Энтропийное кодирование
- Цепь Маркова
- Расстояние Кульбака — Лейблера
Примечания
[править | править код]- ↑ Данное представление удобно для работы с информацией, представленной в двоичной форме; в общем случае основание логарифма может быть другим.
- ↑ Shannon, Claude E. A Mathematical Theory of Communication (неопр.) // Bell System Technical Journal[англ.]. — 1948. — July (т. 27, № 3). — С. 419. — doi:10.1002/j.1538-7305.1948.tb01338.x. Архивировано 1 августа 2016 года.
- ↑ Габидулин Э. М., Пилипчук Н. И. Лекции по теории информации — МФТИ, 2007. — С. 16. — 214 с. — ISBN 978-5-7417-0197-3
- ↑ Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69.
Литература
[править | править код]- Шеннон К. Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 2002.
- Волькенштейн М. В. Энтропия и информация. — М.: Наука, 2006.
- Цымбал В. П. Теория информации и кодирование. — К.: Вища Школа, 2003.
- Martin, Nathaniel F.G. & England, James W. Mathematical Theory of Entropy. — Cambridge University Press, 2011. — ISBN 978-0-521-17738-2.
- Шамбадаль П. Развитие и приложение понятия энтропии. — М.: Наука, 1967. — 280 с.
- Мартин Н., Ингленд Дж. Математическая теория энтропии. — М.: Мир, 1988. — 350 с.
- Хинчин А. Я. Понятие энтропии в теории вероятностей // Успехи математических наук. — Российская академия наук, 1953. — Т. 8, вып. 3(55). — С. 3—20.
- Брюллюэн Л. Наука и теория информации. — М., 1960.
- Винер Н. Кибернетика и общество. — М., 1958.
- Винер Н. Кибернетика или управление и связь в животном и машине. — М., 1968.
- Петрушенко Л. А. Самодвижение материи в свете кибернетики. — М., 1974.
- Эшби У. Р. Введение в кибернетику. — М., 1965.
- Яглом А. М., Яглом И. М. Вероятность и информация. — М., 1973.
- Волькенштейн М. В. Энтропия и информация. — М.: Наука, 1986. — 192 с.
- Верещагин Н. К., Щепин Е. В. Информация, кодирование и предсказание. — М.: ФМОП, МЦНМО, 2012. — 238 с. — ISBN 978-5-94057-920-5.
Ссылки
[править | править код]- Shannon Claude E. A Mathematical Theory of Communication Архивная копия от 31 января 1998 на Wayback Machine (англ.)
- Коротаев С. М. Энтропия и информация — универсальные естественнонаучные понятия.