В теории информации , то энтропия из случайной величины является средним уровнем «информации», «сюрприза», или «неопределенности» , присущей возможными результатов переменных. Концепция информационной энтропии была введена Клодом Шенноном в его статье 1948 года « Математическая теория коммуникации » [1] [2] и иногда в его честь называют энтропией Шеннона . В качестве примера рассмотрим смещенную монету с вероятностью p выпадения орла и вероятностью 1 - p выпадения решки. Максимальный сюрприз - при p = 1/2, когда нет причин ожидать, что один результат важнее другого, и в этом случае подбрасывание монеты имеет энтропию в один бит . Минимальный сюрприз - это когда p = 0 или p = 1 , когда событие известно и энтропия равна нулю битов. Другие значения p дают разные энтропии между нулем и единицей битов.
Учитывая дискретную случайную величину , с возможными исходами , которые происходят с вероятностью энтропия формально определяется как:
где обозначает сумму возможных значений переменной, а - логарифм , выбор основания различается в зависимости от приложения. База 2 дает единицу битов (или « шеннонов »), в то время как основание e дает «естественные единицы» nat , а основание 10 дает единицу, называемую «точками», «банами» или « хартли ». Эквивалентное определение энтропии является ожидаемым значением из собственной информации переменного. [3]
Энтропия была первоначально создана Шенноном как часть его теории коммуникации, в которой система передачи данных состоит из трех элементов: источника данных, канала связи и приемника. В теории Шеннона «фундаментальная проблема коммуникации», как выразился Шеннон, заключается в том, чтобы приемник мог определить, какие данные были сгенерированы источником, на основе сигнала, который он получает через канал. [1] [2] Шеннон рассмотрел различные способы кодирования, сжатия и передачи сообщений из источника данных и доказал в своей знаменитой теореме кодирования источника, что энтропия представляет собой абсолютный математический предел того, насколько хорошо данные из источника могут быть сжаты без потерь. на совершенно бесшумный канал. Шеннон значительно усилил этот результат для зашумленных каналов в своей теореме кодирования зашумленных каналов .
Энтропия в теории информации прямо аналогична энтропии в статистической термодинамике . Аналогия возникает, когда значения случайной величины обозначают энергии микросостояний, поэтому формула Гиббса для энтропии формально идентична формуле Шеннона. Энтропия имеет отношение к другим областям математики, таким как комбинаторика . Определение может быть получено из набора аксиом, устанавливающих, что энтропия должна быть мерой того, насколько «удивительным» является средний результат переменной. Для непрерывной случайной величины дифференциальная энтропия аналогична энтропии.
Вступление
Основная идея теории информации состоит в том, что «информационная ценность» передаваемого сообщения зависит от того, насколько удивительно его содержание. Если событие очень вероятно, неудивительно (и, как правило, неинтересно), когда это событие происходит так, как ожидалось; следовательно, передача такого сообщения несет очень мало новой информации. Однако, если событие маловероятно, гораздо информативнее узнать, что событие произошло или произойдет. Например, знание того, что какое-то конкретное число не будет выигрышным в лотерее, дает очень мало информации, потому что любое конкретное выбранное число почти наверняка не выиграет. Тем не менее, известно , что конкретное число будет выиграть в лотерею имеет большое значение , поскольку он передает результат очень низкой вероятности события.
Информационное содержание (также называется surprisal ) о событии - функция, убывающая как вероятность события увеличивается, определяемое или эквивалентно , где это логарифм . Энтропия измеряет ожидаемый (т.е. средний) объем информации, передаваемой путем определения результата случайного испытания. [4] : 67 Это означает, что бросок кубика имеет более высокую энтропию, чем бросание монеты, потому что каждый результат броска кубика имеет меньшую вероятность (примерно), чем каждый результат подбрасывания монеты ().
Рассмотрим пример подбрасывания монеты. Если вероятность выпадения орла такая же, как и вероятность выпадения решки, то энтропия подбрасывания монеты настолько высока, насколько это могло бы быть для испытания с двумя исходами. Невозможно предсказать результат подбрасывания монеты заранее: если нужно выбирать, нет никакого среднего преимущества, которое можно получить, предсказав, что при подбрасывании будет решка или орел, поскольку любой прогноз с вероятностью будет верным.. Такой бросок монеты имеет энтропию(в битах), поскольку есть два возможных результата, которые происходят с равной вероятностью, и изучение фактического результата содержит один бит информации. Напротив, подбрасывание монеты с использованием монеты с двумя орлами и без решки имеет энтропию.так как монета всегда выпадет орлом, и исход можно предсказать идеально. Точно так же одна трость с равновероятными значениями содержит (около 1,58496) бит информации, потому что он может иметь одно из трех значений.
Английский текст, рассматриваемый как строка символов, имеет довольно низкую энтропию, т. Е. Достаточно предсказуем. Если мы не знаем точно, что будет дальше, мы можем быть вполне уверены, что, например, «e» будет гораздо более распространенным, чем «z», что комбинация «qu» будет гораздо более распространенной, чем любая другая. комбинация с «q» в нем, и что комбинация «th» будет более распространенной, чем «z», «q» или «qu». Часто после первых букв можно угадать остаток слова. Английский текст имеет от 0,6 до 1,3 бита энтропии на символ сообщения. [5] : 234
Если компрессия схема без потерь - один , в котором вы всегда можете восстановить все исходное сообщение декомпрессии - то сжатое сообщение имеет такое же количество информации , как в оригинале , но сообщается в меньшем количестве символов. Он содержит больше информации (более высокая энтропия) для каждого символа. Сжатое сообщение имеет меньшую избыточность . Теорема кодирования источника Шеннона утверждает, что схема сжатия без потерь не может сжимать сообщения в среднем так, чтобы иметь более одного бита информации на бит сообщения, но что любое значение меньше одного бита информации на бит сообщения может быть достигнуто с помощью подходящего схема кодирования. Энтропия сообщения на бит, умноженная на длину этого сообщения, является мерой того, сколько общей информации содержит сообщение.
Если передать последовательности, состоящие из 4 символов «A», «B», «C» и «D», передаваемое сообщение могло бы быть «ABADDCAB». Теория информации дает способ вычислить минимально возможное количество информации, которая это передаст. Если все 4 буквы равновероятны (25%), нельзя сделать лучше (по двоичному каналу), чем иметь 2 бита, кодирующие (в двоичном) каждую букву: 'A' может кодироваться как '00', 'B' как «01», «C» как «10» и «D» как «11». Если «A» встречается с вероятностью 70%, «B» - с 26%, а «C» и «D» - с 2% каждый, можно назначить коды переменной длины, так что получение «1» говорит о необходимости взглянуть на другой бит. если еще не было получено 2 бита последовательных единиц. В этом случае «A» будет закодирован как «0» (один бит), «B» - как «10», «C» - как «110», а D - как «111». Легко видеть, что в 70% случаев необходимо отправить только один бит, в 26% случаев - два бита и только в 4% случаев - 3 бита. В среднем требуется менее 2 бит, поскольку энтропия ниже (из-за высокой распространенности буквы «А», за которой следует «В» - вместе 96% символов). Расчет суммы логарифмических вероятностей, взвешенных по вероятности, измеряет и фиксирует этот эффект.
Теорема Шеннона также подразумевает, что никакая схема сжатия без потерь не может сократить все сообщения. Если некоторые сообщения выходят короче, по крайней мере одно должно выходить дольше из-за принципа ячейки . На практике это, как правило, не проблема, потому что обычно требуется сжатие только определенных типов сообщений, таких как документ на английском языке, в отличие от бессмысленного текста или цифровых фотографий, а не шума, и неважно, если алгоритм сжатия увеличивает размер некоторых маловероятных или неинтересных последовательностей.
Определение
Названный в честь -теоремы Больцмана , Шеннон определил энтропию Η (греческая заглавная буква эта ) дискретной случайной величины. с возможными значениями и вероятностная функция масс в виде:
Здесь является оператором ожидаемого значения , и я это содержание информации из X . [6] : 11 [7] : 19–20 сам по себе является случайной величиной.
Энтропию можно явно записать как:
где b - основание используемого логарифма . Общие значения b - 2, число Эйлера e и 10, а соответствующие единицы энтропии - биты для b = 2 , nats для b = e и запреты для b = 10 . [8]
В случае P ( x i ) = 0 для некоторого i значение соответствующего слагаемого 0 log b (0) принимается равным 0 , что согласуется с пределом : [9] : 13
Можно также определить условную энтропию двух переменных а также принимая ценности а также соответственно, как: [9] : 16
где вероятность того, что а также . Под этой величиной следует понимать количество случайности в случайной величине. учитывая случайную величину .
Пример
Рассмотрите возможность подбрасывания монеты с известной, не обязательно справедливой, вероятностью выпадения орла или решки; это можно смоделировать как процесс Бернулли .
Энтропия неизвестного результата следующего подбрасывания монеты максимизируется, если монета справедливая (то есть, если орел и решка имеют равную вероятность 1/2). Это ситуация максимальной неопределенности, так как исход следующей жеребьевки предсказать сложнее всего; результат каждого подбрасывания монеты предоставляет один полный бит информации. Это потому что
Однако, если мы знаем, что монета несправедлива, но выпадает орел или решка с вероятностями p и q , где p ≠ q , то неопределенности меньше. Каждый раз, когда его бросают, одна сторона с большей вероятностью поднимется, чем другая. Сниженная неопределенность количественно выражается более низкой энтропией: в среднем каждый бросок монеты дает менее одного полного бита информации. Например, если p = 0,7, то
Равномерная вероятность дает максимальную неопределенность и, следовательно, максимальную энтропию. Таким образом, энтропия может уменьшаться только от значения, связанного с равномерной вероятностью. Крайний случай - это двуглавая монета, у которой никогда не выпадает решка, или двусторонняя монета, у которой никогда не выпадает решка. Тогда нет никакой неопределенности. Энтропия равна нулю: каждое подбрасывание монеты не дает новой информации, поскольку результат каждого подбрасывания монеты всегда определен. [9] : 14–15
Энтропию можно нормализовать, разделив ее на длину информации. Это соотношение называется метрической энтропией и является мерой случайности информации.
Характеристика
Чтобы понять значение -∑ p i log ( p i ) , сначала определите информационную функцию I в терминах события i с вероятностью p i . Количество информации , полученной в результате наблюдения события я следует из решения Шеннона из фундаментальных свойств в информации : [10]
- Я ( р ) является монотонно убывающей в р : увеличение вероятности события уменьшает информацию от наблюдаемого события, и наоборот.
- I ( p ) ≥ 0 : информация - неотрицательная величина.
- I (1) = 0 : всегда происходящие события не передают информацию.
- I ( p 1 , p 2 ) = I ( p 1 ) + I ( p 2 ) : информация, полученная из независимых событий, является суммой информации, полученной из каждого события.
Учитывая два независимых события, если первое событие может дать один из n равновероятных исходов, а другое имеет один из m равновероятных исходов, то существует mn равновероятных исходов совместного события. Это означает, что если log 2 ( n ) битов необходимы для кодирования первого значения и log 2 ( m ) для кодирования второго, нужно log 2 ( mn ) = log 2 ( m ) + log 2 ( n ) для кодирования обоих .
Шеннон обнаружил, что подходящий выбор дан кем-то:
Фактически, единственно возможные значения находятся для . Кроме того, выбор значения k эквивалентен выбору значения для , так что x соответствует основанию логарифма . Таким образом, энтропия характеризуется четырьмя указанными выше свойствами.
Доказательство Позволять - информационная функция, которую предполагается дважды непрерывно дифференцируемой, мы имеем: Это дифференциальное уравнение приводит к решению для любой . Свойство 2 приводит к. Тогда также сохраняются свойства 1 и 3.
Различные единицы информации ( биты для двоичного логарифма log 2 , nats для натурального логарифма ln , запреты для десятичного логарифма log 10 и так далее) являются постоянными кратными друг другу. Например, в случае правильного подбрасывания монеты орел предоставляет log 2 (2) = 1 бит информации, что составляет примерно 0,693 ната или 0,301 десятичной цифры. Из-за аддитивности n бросков предоставляют n битов информации, что составляет примерно 0,693 n нат или 0,301 n десятичных цифр.
Смысл событий , наблюдаемых (смысл сообщений ) не имеет значения в определении энтропии. Энтропия учитывает только вероятность наблюдения конкретного события, поэтому информация, которую она инкапсулирует, представляет собой информацию о лежащем в основе распределении вероятностей, а не о значении самих событий.
Альтернативная характеристика
Другая характеристика энтропии использует следующие свойства. Обозначим p i = Pr ( X = x i ) и Η n ( p 1 ,…, p n ) = Η ( X ) .
- Непрерывность: H должно быть непрерывным , так что изменение значений вероятностей на очень небольшое количество должно изменять энтропию только на небольшую величину.
- Симметрия: H должно быть неизменным, если результаты x i переупорядочиваются. Это,для любой перестановки из .
- Максимум: должен быть максимальным, если все исходы одинаково вероятны, т.е. .
- Увеличение количества исходов: для равновероятных событий энтропия должна увеличиваться с увеличением количества исходов, т.е.
- Аддитивность: учитывая ансамбль из n равномерно распределенных элементов, которые разделены на k блоков (подсистем) с b 1 , ..., b k элементами в каждом, энтропия всего ансамбля должна быть равна сумме энтропии система ящиков и индивидуальные энтропии ящиков, каждая из которых взвешена с вероятностью попадания в эту конкретную ячейку.
Правило аддитивности имеет следующие последствия: для натуральных чисел b i, где b 1 +… + b k = n ,
Выбор k = n , b 1 =… = b n = 1 означает, что энтропия определенного результата равна нулю: Η 1 (1) = 0 . Это означает, что эффективность исходного алфавита с n символами может быть определена просто как равная его n -арной энтропии. См. Также Резервирование (теория информации) .
Другие свойства
Энтропия Шеннона удовлетворяет следующим свойствам, для некоторых из которых полезно интерпретировать энтропию как количество полученной информации (или устраненной неопределенности) путем выявления значения случайной величины X :
- Добавление или удаление события с нулевой вероятностью не влияет на энтропию:
- .
- Используя неравенство Дженсена, можно подтвердить, что
- . [9] : 29
- Эта максимальная энтропия log b ( n ) эффективно достигается исходным алфавитом, имеющим равномерное распределение вероятностей: неопределенность максимальна, когда все возможные события равновероятны.
- Энтропия или количество информации, полученной при оценке ( X , Y ) (то есть при одновременном оценивании X и Y ), равно информации, полученной при проведении двух последовательных экспериментов: сначала оценивается значение Y , а затем раскрывается значение X при условии , что вы знаете , значение Y . Это можно записать так: [9] : 16
- Если где функция, то . Применяя предыдущую формулу к дает
- так , энтропия переменной может уменьшаться только тогда, когда последняя передается через функцию.
- Если X и Y - две независимые случайные величины, то знание значения Y не влияет на наши знания о значении X (поскольку они не влияют друг на друга по своей независимости):
- Энтропия двух одновременных событий - это не более чем сумма энтропий каждого отдельного события, т.е. , с равенством тогда и только тогда, когда два события независимы. [9] : 28
- Энтропия является вогнутой в функции вероятности массового, т.е. [9] : 30
- для всех вероятностных массовых функций а также . [9] : 32
- Соответственно, функция отрицательной энтропии (негэнтропии) является выпуклой, а ее выпуклым сопряженным элементом является LogSumExp .
Аспекты
Связь с термодинамической энтропией
Вдохновение для принятия слова энтропия в теории информации произошло из-за близкого сходства между формулой Шеннона и очень похожими известными формулами из статистической механики .
В статистической термодинамике наиболее общая формула для термодинамической энтропии S в виде термодинамической системы является энтропией Гиббса ,
где k B - постоянная Больцмана , а p i - вероятность микросостояния . Энтропия Гиббса была определена Гиббс в 1878 г. после ранней работы Больцмана (1872 г.). [11]
Энтропия Гиббса практически без изменений переводится в мир квантовой физики, чтобы дать энтропию фон Неймана , введенную Джоном фон Нейманом в 1927 году,
где ρ - матрица плотности квантово-механической системы, а Tr - след .
На повседневном практическом уровне связь между информационной энтропией и термодинамической энтропией не очевидна. Физики и химики склонны больше интересоваться изменениями энтропии по мере того, как система спонтанно эволюционирует от своих начальных условий в соответствии со вторым законом термодинамики , а не неизменным распределением вероятностей. Как показывает малая величина постоянной Больцмана k B , изменения S / k B даже для крошечных количеств веществ в химических и физических процессах представляют собой количества энтропии, которые чрезвычайно велики по сравнению с чем-либо в сжатии данных или обработке сигналов . В классической термодинамике энтропия определяется в терминах макроскопических измерений и не ссылается на какое-либо распределение вероятностей, которое является центральным для определения информационной энтропии.
Связь между термодинамикой и тем, что сейчас известно как теория информации, впервые была установлена Людвигом Больцманом и выражена его знаменитым уравнением :
где - термодинамическая энтропия определенного макросостояния (определяемая термодинамическими параметрами, такими как температура, объем, энергия и т. д.), W - количество микросостояний (различные комбинации частиц в различных энергетических состояниях), которые могут дать данное макросостояние, а k B - постоянная Больцмана . Предполагаются , что каждое микросостояние с равной вероятностью, так что вероятность данного микросостояния является р я = 1 / W . Когда эти вероятности подставляются в приведенное выше выражение для энтропии Гиббса (или эквивалентно k B, умноженное на энтропию Шеннона), получается уравнение Больцмана. В терминах теории информации информационная энтропия системы - это количество «недостающей» информации, необходимой для определения микросостояния при данном макросостоянии.
По мнению Джейнса (1957), термодинамическая энтропия, как объясняется статистической механикой , должна рассматриваться как приложение теории информации Шеннона: термодинамическая энтропия интерпретируется как пропорциональная количеству дополнительной информации Шеннона, необходимой для определения подробных микроскопических данных. состояние системы, которое не передается описанием исключительно в терминах макроскопических переменных классической термодинамики, при этом константа пропорциональности является просто постоянной Больцмана . Добавление тепла к системе увеличивает ее термодинамическую энтропию, потому что это увеличивает количество возможных микроскопических состояний системы, которые согласуются с измеряемыми значениями ее макроскопических переменных, что делает любое полное описание состояния более длинным. (См. Статью: термодинамика максимальной энтропии ). Демон Максвелла может (гипотетически) уменьшить термодинамическую энтропию системы, используя информацию о состояниях отдельных молекул; но, как показали Ландауэр (с 1961 г.) и его коллеги, для функционирования демон сам должен увеличивать термодинамическую энтропию в процессе, по крайней мере, на количество информации Шеннона, которую он предлагает сначала получить и сохранить; и поэтому полная термодинамическая энтропия не уменьшается (что разрешает парадокс). Принцип Ландауэра накладывает нижнюю границу на количество тепла, которое компьютер должен генерировать для обработки заданного количества информации, хотя современные компьютеры намного менее эффективны.
Сжатие данных
Энтропия определяется в контексте вероятностной модели. Независимые честные подбрасывания монеты имеют энтропию 1 бит на подбрасывание. Источник, который всегда генерирует длинную строку B, имеет энтропию 0, так как следующим символом всегда будет «B».
Скорость энтропии источника данных означает среднее количество бит на символ, необходимое для его кодирования. Эксперименты Шеннона с человеческими предсказателями показывают скорость передачи информации от 0,6 до 1,3 бита на символ в английском языке; [12] алгоритм сжатия PPM может достичь коэффициента сжатия 1,5 бит на символ в английском тексте.
Определение энтропии Шеннона в применении к источнику информации может определить минимальную пропускную способность канала, необходимую для надежной передачи источника в виде закодированных двоичных цифр. Энтропия Шеннона измеряет информацию, содержащуюся в сообщении, в отличие от той части сообщения, которая определена (или предсказуема). Примеры последнего включают избыточность в структуре языка или статистические свойства, относящиеся к частотам появления пар букв или слов, троек и т. Д.
Минимальная пропускная способность канала может быть реализована теоретически с использованием типичного набора или на практике с использованием кодирования Хаффмана , Лемпеля – Зива или арифметического кодирования . (См. Также сложность Колмогорова .) На практике алгоритмы сжатия намеренно включают некоторую разумную избыточность в виде контрольных сумм для защиты от ошибок.
В исследовании 2011 года, проведенном в Science, оценивается мировая технологическая способность хранить и передавать оптимально сжатую информацию, нормализованную по наиболее эффективным алгоритмам сжатия, доступным в 2007 году, таким образом оценивая энтропию технологически доступных источников. [13] : 60–65
Тип информации | 1986 г. | 2007 г. |
---|---|---|
Место хранения | 2,6 | 295 |
Транслировать | 432 | 1900 г. |
Телекоммуникации | 0,281 | 65 |
Авторы оценивают технологические возможности человечества хранить информацию (полностью энтропийно сжатую) в 1986 году и снова в 2007 году. Они разбивают информацию на три категории: хранить информацию на носителе, получать информацию через сети одностороннего вещания или обмениваться информацией. через двусторонние телекоммуникационные сети. [13]
Энтропия как мера разнообразия
Энтропия - один из нескольких способов измерения разнообразия. В частности, энтропия Шеннона - это логарифм 1 D , истинный индекс разнообразия с параметром, равным 1.
Ограничения энтропии
Существует ряд связанных с энтропией концепций, которые каким-то образом математически определяют количество информации:
- себя информацию отдельного сообщения или символа берется из заданного распределения вероятностей,
- энтропия заданного распределения вероятностей сообщений или символов, а также
- энтропия скорость из стохастического процесса .
(«Скорость самоинформации» также может быть определена для конкретной последовательности сообщений или символов, генерируемых данным случайным процессом: она всегда будет равна скорости энтропии в случае стационарного процесса .) Другие количества информации также используются для сравнения или связи различных источников информации.
Важно не путать приведенные выше понятия. Часто только из контекста ясно, о чем идет речь. Например, когда кто-то говорит, что «энтропия» английского языка составляет около 1 бита на символ, они фактически моделируют английский язык как стохастический процесс и говорят о его скорости энтропии . Сам Шеннон использовал этот термин таким образом.
Если используются очень большие блоки, оценка скорости энтропии для каждого символа может стать искусственно заниженной, поскольку распределение вероятностей последовательности точно не известно; это только оценка. Если рассматривать текст каждой книги, когда-либо опубликованной, как последовательность, где каждый символ является текстом всей книги, и если опубликовано N книг, и каждая книга публикуется только один раз, оценка вероятности каждой книги будет 1 / N , а энтропия (в битах) равна −log 2 (1 / N ) = log 2 ( N ) . На практике это соответствует присвоению каждой книге уникального идентификатора и использованию его вместо текста книги всякий раз, когда кто-то хочет сослаться на книгу. Это чрезвычайно полезно для разговоров о книгах, но не столь полезно для характеристики информационного содержания отдельной книги или языка в целом: невозможно восстановить книгу по ее идентификатору, не зная распределения вероятностей, т. Е. , полный текст всех книг. Ключевая идея состоит в том, что необходимо учитывать сложность вероятностной модели. Колмогоровская сложность - это теоретическое обобщение этой идеи, которое позволяет рассматривать информационное содержание последовательности независимо от какой-либо конкретной вероятностной модели; он рассматривает самую короткую программу для универсального компьютера , выводящего последовательность. Код, который достигает скорости энтропии последовательности для данной модели, плюс кодовая книга (то есть вероятностная модель), является одной из таких программ, но может быть не самой короткой.
Последовательность Фибоначчи - это 1, 1, 2, 3, 5, 8, 13, .... рассматривая последовательность как сообщение, а каждое число как символ, символов почти столько же, сколько символов в сообщении, что дает энтропия примерно log 2 ( n ) . Первые 128 символов последовательности Фибоначчи имеют энтропию примерно 7 бит / символ, но последовательность может быть выражена с помощью формулы [ F ( n ) = F ( n −1) + F ( n −2) для n = 3. , 4, 5,… , F (1) = 1 , F (2) = 1 ], и эта формула имеет гораздо более низкую энтропию и применима к любой длине последовательности Фибоначчи.
Ограничения энтропии в криптографии
В криптоанализе энтропия часто грубо используется как мера непредсказуемости криптографического ключа, хотя ее реальная неопределенность неизмерима. Например, 128-битный ключ, который генерируется равномерно и случайным образом, имеет 128 бит энтропии. Также требуется (в среднем)догадывается взломать грубой силой. Энтропия не может уловить необходимое количество предположений, если возможные ключи не выбраны единообразно. [14] [15] Вместо этого, мера называется догадками может быть использована для измерения усилия , необходимое для грубой силы атаки. [16]
Другие проблемы могут возникнуть из-за неоднородных распределений, используемых в криптографии. Например, одноразовый двоичный блокнот из 1 000 000 цифр с использованием исключающего или. Если блокнот имеет 1000000 бит энтропии, он идеален. Если блокнот имеет 999999 бит энтропии, равномерно распределенный (каждый отдельный бит блока имеет 0,999999 бит энтропии), это может обеспечить хорошую безопасность. Но если блокнот имеет 999 999 бит энтропии, где первый бит фиксирован, а остальные 999 999 бит совершенно случайны, первый бит зашифрованного текста не будет зашифрован вообще.
Данные как марковский процесс
Обычный способ определения энтропии для текста основан на марковской модели текста. Для источника порядка 0 (каждый символ выбирается независимо от последних символов) двоичная энтропия равна:
где p i - вероятность i . Для марковского источника первого порядка (в котором вероятность выбора символа зависит только от непосредственно предшествующего символа) коэффициент энтропии равен:
- [ необходима цитата ]
где i - состояние (некоторые предыдущие символы) и- вероятность того, что j задан предыдущим символом i .
Для марковского источника второго порядка скорость энтропии равна
Эффективность (нормализованная энтропия)
Исходный алфавит с неравномерным распределением будет иметь меньшую энтропию, чем если бы эти символы имели равномерное распределение (т.е. «оптимизированный алфавит»). Этот дефицит энтропии можно выразить как коэффициент, называемый эффективностью [ Эта цитата требует цитирования ] :
Применяя основные свойства логарифма, эту величину также можно выразить как:
Эффективность полезна для количественной оценки эффективного использования канала связи . Эта формулировка также называется нормализованной энтропией, поскольку энтропия делится на максимальную энтропию.. Кроме того, эффективность безразлична к выбору (положительного) основания b , на что указывает нечувствительность в пределах последнего логарифма, приведенного выше.
Энтропия для непрерывных случайных величин
Дифференциальная энтропия
Энтропия Шеннона ограничена случайными величинами, принимающими дискретные значения. Соответствующая формула для непрерывной случайной величины с функцией плотности вероятности f ( x ) с конечным или бесконечным носителемна действительной прямой определяется по аналогии, используя приведенную выше форму энтропии в качестве математического ожидания: [9] : 224
Это дифференциальная энтропия (или непрерывная энтропия). Предшественник непрерывной энтропии ч [ ф ] является выражение для функционала Н в Н-теореме о Больцмана .
Хотя аналогия между обеими функциями наводит на размышления, необходимо задать следующий вопрос: является ли дифференциальная энтропия допустимым расширением дискретной энтропии Шеннона? Дифференциальная энтропия лишена ряда свойств, которыми обладает дискретная энтропия Шеннона - она может быть даже отрицательной - и были предложены поправки, в частности, ограничение плотности дискретных точек .
Чтобы ответить на этот вопрос, необходимо установить связь между двумя функциями:
Чтобы получить обычно конечную меру, когда размер ячейки стремится к нулю. В дискретном случае размер бина - это (неявная) ширина каждого из n (конечных или бесконечных) бинов, вероятности которых обозначены как p n . Поскольку непрерывная область является обобщенной, ширина должна быть указана явно.
Для этого начнем с непрерывной функции f, дискретизированной на ячейки размером. По теореме о среднем значении в каждой ячейке существует такое значение x i , что
интеграл от функции f может быть аппроксимирован (в римановом смысле) выражением
где этот предел и «размер ячейки стремится к нулю» эквивалентны.
Обозначим
и раскладывая логарифм, имеем
При ∆ → 0 имеем
Примечание; log (Δ) → −∞ при Δ → 0 требует специального определения дифференциальной или непрерывной энтропии:
которая, как было сказано ранее, называется дифференциальной энтропией. Это означает, что дифференциальная энтропия не является пределом энтропии Шеннона при n → ∞ . Скорее, он отличается от предела энтропии Шеннона бесконечным смещением (см. Также статью об измерении информации ).
Предельная плотность дискретных точек
Оказывается, в результате чего, в отличие от энтропии Шеннона, дифференциальная энтропия не в целом хорошей мерой неопределенности или информации. Например, дифференциальная энтропия может быть отрицательной; также он не инвариантен относительно непрерывных преобразований координат. Эта проблема может быть проиллюстрирована изменением единиц измерения, когда x - размерная переменная. Тогда f (x) будет иметь единицы 1 / x . Аргумент логарифма должен быть безразмерным, в противном случае он неправильный, так что приведенная выше дифференциальная энтропия будет неправильной. Если Δ является некоторым «стандартным» значением x (т. Е. «Размером ячейки») и, следовательно, имеет те же единицы измерения, то модифицированная дифференциальная энтропия может быть записана в надлежащей форме как:
и результат будет таким же при любом выборе единиц для x . Фактически, предел дискретной энтропии при также будет включать срок , что в общем случае было бы бесконечным. Это ожидается: непрерывные переменные обычно имеют бесконечную энтропию при дискретизации. Предельная плотность дискретных точек действительно является мерой того , насколько проще распределение является описать , чем распределение, однороден по схеме квантования.
Относительная энтропия
Еще одна полезная мера энтропии, которая одинаково хорошо работает как в дискретном, так и в непрерывном случае, - это относительная энтропия распределения. Он определяется как расхождение Кульбака – Лейблера от распределения к эталонной мере m следующим образом. Предположим , что распределение вероятностей р является абсолютно непрерывна относительно меры т , т.е. имеет вид р ( дх ) = е ( х ) м ( ах ) для некоторого неотрицательного м -интегрируемой функции F с м -интеграла 1, тогда относительную энтропию можно определить как
В этой форме относительная энтропия обобщает (с точностью до смены знака) как дискретную энтропию, где мера m является считающей мерой , так и дифференциальную энтропию, где мера m является мерой Лебега . Если мера m сама является распределением вероятностей, относительная энтропия неотрицательна и равна нулю, если p = m в качестве меры. Он определен для любого пространства меры, следовательно, не зависит от координат и инвариантен относительно повторных параметризаций координат, если правильно учесть преобразование меры m . Относительная энтропия и (неявно) энтропия и дифференциальная энтропия зависят от «эталонной» меры m .
Использование в комбинаторике
Энтропия стала полезной величиной в комбинаторике .
Неравенство Лумиса – Уитни
Простым примером этого является альтернативное доказательство неравенства Лумиса – Уитни : для любого подмножества A ⊆ Z d мы имеем
где P i - ортогональная проекция по i- й координате:
Доказательство следует как простое следствие неравенства Ширера : если X 1 ,…, X d - случайные величины и S 1 ,…, S n - подмножества {1,…, d } такие, что каждое целое число от 1 до d лежит в ровно r этих подмножеств, то
где - декартово произведение случайных величин X j с индексами j в S i (так что размерность этого вектора равна размеру S i ).
Мы набросаем, как Лумис – Уитни следует из этого: в самом деле, пусть X - равномерно распределенная случайная величина со значениями в A, так что каждая точка в A встречается с равной вероятностью. Тогда (в силу других свойств энтропии, упомянутых выше) Η ( X ) = log | А | , где | А | обозначает мощность A . Пусть S i = {1, 2,…, i −1, i +1,…, d }. Диапазонсодержится в P i ( A ) и, следовательно,. Теперь используйте это, чтобы ограничить правую часть неравенства Ширера и возвести в степень противоположные стороны полученного неравенства.
Приближение к биномиальному коэффициенту
Для целых чисел 0 < k < n положим q = k / n . потом
где
- [17] : 43
Доказательство (эскиз) Обратите внимание, что это один член выражения Перестановка дает верхнюю границу. Что касается нижней границы, сначала с помощью некоторой алгебры показывают, что это наибольший член в суммировании. Но потом,
поскольку в суммировании содержится n + 1 слагаемых. Перестановка дает нижнюю границу.
Хорошая интерпретация этого состоит в том, что количество двоичных строк длины n, содержащих ровно k единиц, приблизительно равно. [18]
Смотрите также
- Перекрестная энтропия - это мера среднего количества битов, необходимых для идентификации события из набора возможностей между двумя распределениями вероятностей.
- Энтропия (стрела времени)
- Энтропийное кодирование - схема кодирования, которая назначает коды символам, чтобы длина кода соответствовала вероятностям символов.
- Оценка энтропии
- Неравенство энтропийной мощности
- Информация Fisher
- Энтропия графа
- Расстояние Хэмминга
- История энтропии
- История теории информации
- Сложность флуктуации информации
- Информационная геометрия
- Энтропия Колмогорова – Синая в динамических системах.
- Расстояние Левенштейна
- Взаимная информация
- Недоумение
- Качественная вариация - другие меры статистической дисперсии для номинальных распределений
- Квантовая относительная энтропия - мера различимости двух квантовых состояний.
- Энтропия Реньи - обобщение энтропии Шеннона; это один из семейства функционалов для количественной оценки разнообразия, неопределенности или случайности системы.
- Случайность
- Индекс Шеннона
- Индекс Тейла
- Типогликемия
Рекомендации
- ^ a b Шеннон, Клод Э. (июль 1948 г.). «Математическая теория коммуникации» . Технический журнал Bell System . 27 (3): 379–423. DOI : 10.1002 / j.1538-7305.1948.tb01338.x . hdl : 10338.dmlcz / 101429 .( PDF , заархивирован отсюда )
- ^ а б Шеннон, Клод Э. (октябрь 1948 г.). «Математическая теория коммуникации» . Технический журнал Bell System . 27 (4): 623–656. DOI : 10.1002 / j.1538-7305.1948.tb00917.x . hdl : 11858 / 00-001M-0000-002C-4317-B .( PDF , заархивирован отсюда )
- ^ Патрия, РК; Бил, Пол (2011). Статистическая механика (Третье изд.). Академическая пресса. п. 51. ISBN 978-0123821881.
- ^ Маккей, Дэвид JC (2003). Теория информации, выводы и алгоритмы обучения . Издательство Кембриджского университета. ISBN 0-521-64298-1.
- ^ Шнайер, B: Прикладная криптография , второе издание, John Wiley and Sons.
- ^ Борда, Моника (2011). Основы теории информации и кодирования . Springer. ISBN 978-3-642-20346-6.
- ^ Хан, Те Сун и Кобаяши, Кинго (2002). Математика информации и кодирования . Американское математическое общество. ISBN 978-0-8218-4256-0.CS1 maint: использует параметр авторов ( ссылка )
- ↑ Шнайдер, Т. Д., Учебник по теории информации с приложением о логарифмах , Национальный институт рака, 14 апреля 2007 г.
- ^ Б с д е е г ч я J Томас М. Кавер; Джой А. Томас (1991). Элементы теории информации . Хобокен, Нью-Джерси: Wiley. ISBN 978-0-471-24195-9.
- ^ Картер, Том (март 2014). Введение в теорию информации и энтропию (PDF) . Санта-Фе . Проверено 4 августа 2017 года .
- ↑ Сравните: Больцман, Людвиг (1896, 1898). Vorlesungen über Gastheorie: 2 тома - Лейпциг 1895/98 UB: O 5262-6. Английская версия: Лекции по теории газа. Перевод Стивена Дж. Браш (1964) Беркли: Калифорнийский университет Press; (1995) Нью-Йорк: Дувр ISBN 0-486-68455-5
- ^ Марк Нельсон (24 августа 2006 г.). «Приз Хаттера» . Проверено 27 ноября 2008 года .
- ^ a b «Мировой технологический потенциал для хранения, передачи и вычисления информации» , Мартин Гильберт и Присцила Лопес (2011), Science , 332 (6025); бесплатный доступ к статье здесь: martinhilbert.net/WorldInfoCapacity.html
- ^ Мэсси, Джеймс (1994). «Гадание и энтропия» (PDF) . Proc. Международный симпозиум IEEE по теории информации . Источник +31 Декабря 2 013 .
- ^ Мэлоун, Дэвид; Салливан, Уэйн (2005). «Предположения не заменяют энтропию» (PDF) . Материалы конференции «Информационные технологии и телекоммуникации» . Источник +31 Декабря 2 013 .
- ^ Плиам, Джон (1999). «Дальность догадок и вариаций как меры защиты шифров». Международный семинар по избранным направлениям криптографии . DOI : 10.1007 / 3-540-46513-8_5 .
- ^ Аоки, Новые подходы к макроэкономическому моделированию.
- ^ Вероятность и вычисления, М. Митценмахер и Э. Упфаль, Cambridge University Press
Эта статья включает материал энтропии Шеннона на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .
дальнейшее чтение
Учебники по теории информации
- Cover, TM , Thomas, JA (2006), Элементы теории информации - 2-е изд. , Wiley-Interscience, ISBN 978-0-471-24195-9
- Маккей, DJC (2003), Теория информации, алгоритмы вывода и обучения , Cambridge University Press, ISBN 978-0-521-64298-9
- Арндт, К. (2004), Информационные меры: информация и ее описание в науке и технике , Springer, ISBN 978-3-540-40855-0
- Грей Р.М. (2011), Теория энтропии и информации , Springer.
- Мартин, Натаниэль Ф. Г. и Англия, Джеймс У. (2011). Математическая теория энтропии . Издательство Кембриджского университета. ISBN 978-0-521-17738-2.CS1 maint: использует параметр авторов ( ссылка )
- Шеннон, CE , Уивер, W. (1949) Математическая теория коммуникации , Univ of Illinois Press. ISBN 0-252-72548-4
- Стоун, СП (2014), Глава 1 теории информации: Введение в учебное пособие , Университет Шеффилда, Англия. ISBN 978-0956372857 .
Внешние ссылки
- "Энтропия" , Математическая энциклопедия , EMS Press , 2001 [1994]
- «Энтропия» в Rosetta Code - хранилище реализаций энтропии Шеннона на различных языках программирования.
- Энтропия междисциплинарный журнал по всем аспектам концепции энтропии. Открытый доступ.