Меню Рубрики

Что такое энтропия с точки зрения информации

Энтропи́я (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

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

Введение понятия энтропии основывается на использовании вероятностной меры различных опытов. Для получения формулы информационной энтропии можно использовать следующий прием. Пусть имеется последовательность из N событий (например, текст из N букв), каждое из которых принимает одно из M состояний (M ¾ количество букв в алфавите). Тогда . Вероятность проявления данного состояния находим для достаточно длинной цепочки событий как, i=1, ¼ , M. Общее число различных последовательностей из N букв M-буквенного алфавита. Формально появление каждой из R последовательностей равновероятно, поэтому для определения количества информации в такой цепочке событий используем формулу Хартли для равновероятных исходов(1). Для нашего случая все N и все Ni достаточно велики, так как только тогда все pi как вероятности имеют смысл. Поэтому применим преобразование Стирлинга аналогично тому, как это делается в статистической физике. Используя все указанные посылки и приведя логарифм (1) к натуральному основанию, получим формулу Шеннона ¾ информационную энтропию в расчете на каждое из M возможных состояний.

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

5. Основные понятия базовых информационных процессов: хранения, передачи обработки информации.

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

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

Под хранением информации следует понимать содержание информации во внешней памяти компьютера.

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

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

Основные свойства хранилища информации – объем хранимой информации, надежность хранения, время доступа, наличие защиты информации.

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

В современных компьютерах основными носителями информации для внешней памяти служат магнитные и оптические диски.

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

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

В качестве единицы хранения данных принят объект переменной длины, называемый файлом. Файл – это последовательность произвольного числа байтов, обладающая уникальным собственным именем. Обычно в отдельном файле хранят данные, относящиеся к одному типу. В этом случае тип данных определяет тип файла.

Процесс транспортирования информации рассматривается в рамках эталонной семиуровневой модели, известной как модель OSI (Open System Intercongtion- связь открытых систем). Большое внимание уделено протоколам различных уровней, обеспечивающих необходимый уровень стандартизации:

1. Нижний уровень (канальный и физический уровни OSI, например NDIS, ODI)

2. Средний уровень ( сетевой, транспортный и сеансовый уровни OSI, например сеансовые и дейтаграммные протоколы)

3. Верхний уровень (уровень представления и прикладной уровень OSI)

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

Канальный уровень. На этом уровне осуществляется управление звеном сети (каналом) и реализуется пересылка блоков (совокуп­ности битов) информации по физическому звену. Осуществляет та­кие процедуры управления, как определение начала и конца блока, обнаружение ошибок передачи, адресация сообщений и др

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

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

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

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

Под обработкой информации понимают ее преобразование с целью подготовки к практическому использованию. Иногда обработка информации определяется как оперирование данными по определенным правилам.

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

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

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

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

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

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

Еще один важный вид обработки информации – поиск. Задача поиска состоит в отборе нужной информации, удовлетворяющей определенным условиям поиска, в имеющемся хранилище информации. Алгоритм поиска зависит от способа организации информации. Если информация структурирована, то поиск осуществляется быстрее, можно построить оптимальный алгоритм.

Читайте также:  Как врачи определяют зрение по таблице

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

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

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

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

Экземпляр объекта — это конкретный элемент множества. Например, объектом может являться государственный номер автомобиля, а экземпляром этого объекта — конкретный номер К 173 ПА.

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

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

По видам (типам) сигналов выделяются следующие:

Аналоговый сигнал является естественным. Его можно зафиксировать с помощью различных видов датчиков. Например, датчиками среды (давление, влажность) или механическими датчиками (ускорение, скорость)

Цифровые сигналы являются искусственными, т.е. их можно получить только путем преобразования аналогового электрического сигнала.

Дискретный сигнал – это все тот же преобразованный аналоговый сигнал, только он необязательно квантован по уровню.

Дискретизация — преобразование непрерывной функции в дискретную.

Используется в гибридных вычислительных системах и цифровых устройствах при импульсно-кодовой модуляции сигналов в системах передачи данных [1] . При передаче изображения используют для преобразования непрерывного аналогового сигнала в дискретный или дискретно-непрерывный сигнал.

7.Кодирование информации. Алфавит. Слово. Словарь. Двоичное кодирование.

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

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

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

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

Алфавит языка интерпретации сообщений – конечное множество входящих в него знаков, обычно задается их прямым перечислением. Конечная последовательность знаков алфавита называется словом в алфавите. Количество знаков в слове определяет длину слова. Множество различных допустимых слов образует словарный запас (словарь) алфавита. Любой алфавит имеет упорядоченный вид, знаки расположены последовательно в строгом порядке, таким образом, в словаре обеспечивается упорядочивание всех слов по алфавиту.

В качестве длины кода для кодирования символов было выбрано 8 бит или 1 байт. Поэтому одному символу текста соответствует один байт памяти.

Различных комбинаций из 0 и 1 при длине кода 8 бит может быть 28 = 256, поэтому с помощью одной таблицы перекодировки можно закодировать не более 256 символов. При длине кода в 2 байта (16 бит) можно закодировать 65536 символов. Для того чтобы закодировать один символ используют количество информации равное 1 байту, т. е. I = 1 байт = 8 бит. При помощи формулы, которая связывает между собой количество возможных событий К и количество информации I, можно вычислить сколько различных символов можно закодировать К = 2I = 28 = 256, т. е. для представления текстовой информации можно использовать алфавит мощностью 256 символов.

Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255. Одному и тому же двоичному коду ставится в соответствие различные символы.

9. ​Количество информации. Мера количества информации и ее свойства. Формула Хартли.

Количество информации – число, адекватно характеризующее величину разнообразия (набор состояний, альтернатив и т.д.) в оцениваемой системе.

Мера информации – формула, критерий оценки количества информации.

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

K
Это незавершённая статья из области эвентологии и её применений, редактируемая при участии Мастера

Энтропи́я в теории информации — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

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

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

Содержание

Формальные определения [ править ]

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

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

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

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

  • мера должна быть непрерывной; т. е. изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение энтропии;
  • в случае, когда все варианты (буквы в приведенном примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать полную энтропию;
  • должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых энтропия конечного результата должна будет являтся суммой энтропий промежуточных результатов.

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

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

Шеннон определил, что измерение энтропии (H = − p1 log2p1 − … − pn log2pn), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д. См. Цепи Маркова.

В общем случае b-арная энтропия (где b равно 2,3. ) источника = (S,P) с исходным алфавитом S = a1, …, an> и дискретным распределением вероятности P = p1, …, pn> где pi является вероятностью ai (pi = p(ai)) определяется формулой:

Определение энтропии Шеннона очень связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между понятиями энтропии в термодинамике и теории информации. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

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

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

Читайте также:  Что такое воспитание с научной точки зрения

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

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

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

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

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

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

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

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

Взаимная энтропия [ править ]

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

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

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

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

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

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

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

Свойства [ править ]

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию бита на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: . Так, к примеру, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

  1. Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
  2. Количество энтропии не всегда выражается целым числом бит.

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

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

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

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

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

Эффективность [ править ]

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

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

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля-Зива или арифметического кодирования.

История [ править ]

В 1948 году, исследуя проблему рациональной передачи информации через зашумленный коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных шифров.

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

Информационная энтропия: определение понятия, свойства, система

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

Объем информации, передаваемый каждым событием, определенным таким образом, становится случайной величиной, ожидаемым значением которой является информационная энтропия. Как правило, энтропия относится к беспорядку или неопределенности, а ее определение, используемое в теории информации, непосредственно аналогично определению, используемому в статистической термодинамике. Концепция ИЭ была введена Клодом Шенноном в его статье 1948 года «Математическая теория коммуникации». Отсюда и возник термин «информационная энтропия Шеннона».

Определение и система

Базовая модель системы передачи данных состоит из трех элементов: источника данных, канала связи и приемника, и, как выражается Шеннон, «основная проблема связи» заключается в том, чтобы получатель мог идентифицировать, какие данные были сгенерированы источником, на основе сигнала, который он получает по каналу. Энтропия обеспечивает абсолютное ограничение на кратчайшую возможную среднюю длину кодирования без потерь сжатых данных по источнику. Если энтропия источника меньше пропускной способности канала связи, данные, генерируемые им, могут быть надежно переданы приемнику (по крайней мере теоретически, возможно, пренебрегая некоторыми практическими соображениями, такими как сложность системы, необходимой для передачи данных и количества времени, которое может потребоваться для передачи данных).

Информационная энтропия обычно измеряется в битах (альтернативно называемых «шэннонами») или иногда в «естественных единицах» (nats) или десятичных разрядах (называемых «dits», «bans» или «hartleys»). Единица измерения зависит от базы логарифма, которая используется для определения энтропии.

Свойства и логарифм

Логарифм распределения вероятностей полезен как мера энтропии, потому что он аддитивен для независимых источников. Например, энтропия справедливой ставки монеты составляет 1 бит, а энтропия m-томов — это m бит. В простом представлении биты log2 (n) необходимы для представления переменной, которая может принимать одно из n значений, если n является степенью 2. Если эти значения одинаково вероятны, энтропия (в битах) равна этому числу. Если одно из значений более вероятно, чем другие, наблюдение, что это значение происходит, менее информативно, чем если бы произошел какой-то менее общий результат. И наоборот, более редкие события предоставляют дополнительную информацию при слежении.

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

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

Теория информации

Основная идея теории информации заключается в том, что чем больше человек знает о теме, тем меньше информации о ней можно получить. Если событие очень вероятно, это не удивительно, когда это происходит и, следовательно, дает мало новой информации. И наоборот, если событие было невероятным, гораздо более информативным было то, что произошло событие. Следовательно, информационное наполнение является возрастающей функцией обратного вероятности события (1 / p).

Читайте также:  Кто такой нигилист с точки зрения базарова

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

Особенности

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

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

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

Бросок монеты

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

Это связано с тем, что невозможно предсказать, что исход монеты забрасывается досрочно: если нам нужно будет выбирать, самое лучшее, что мы можем сделать, — это предсказать, что монета упадет решкой, и это предсказание будет правильным с вероятностью 1 / 2. Такой бросок монеты имеет один бит энтропии, так как есть два возможных результата, которые происходят с равной вероятностью, а изучение фактического результата содержит один бит информации.

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

Заключение

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

Грубо говоря, теорема о кодировании исходного кода Шеннона гласит: схема сжатия без потерь не может сокращать сообщения в среднем, чтобы иметь более одного бита информации на бит сообщения, но может быть достигнуто любое значение, меньшее одного бита информации на бит сообщения, используя подходящую схему кодирования. Энтропия сообщения в битах, умноженная на его длину, является мерой того, сколько общей информации содержится в нем.

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


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

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

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

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

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

Энтропия бывает разная черная белая красная:

  • термодинамическая
  • алгоритмическая
  • информационная
  • дифференциальная
  • топологическая

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

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

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

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

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

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

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

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

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

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

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

Источники:
  • http://www.wikiznanie.ru/ru-wz/index.php/%D0%AD%D0%BD%D1%82%D1%80%D0%BE%D0%BF%D0%B8%D1%8F_(%D0%B2_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%B8)
  • http://fb.ru/article/431228/informatsionnaya-entropiya-opredelenie-ponyatiya-svoystva-sistema
  • http://habr.com/post/305794/