Энтропия также характеризует степень «непредсказуемости» несовместных событий, вероятности которых равны $p_\alpha$. Eсли $n$ невелико и все вероятности малы, кроме одной, то почти всегда происходит соответствующее ей событие. Эта ситуация вполне предсказуема (энтропия мала). При равномерном же распределении вероятностей может произойти «что угодно» (энтропия максимальна).

☝ Доказательство основного свойства энтропии проводится при помощи поиска экстремума со связями (метод множителей Лагранжа). Условие нормировки (сумма $p_\alpha$ равна 1) умножаем на параметр $\lambda$ и добавляем к энтропии. Затем ищем экстремум по $p_1. p_n,\lambda$: $$ H = -\sum p_\alpha\,\ln p_\alpha + \lambda\,\bigr(\sum p_\alpha- 1\bigr),

p_\alpha=\mathrm. $$ Производная по $\lambda$ даёт условие нормировки и которого следует, что $p_\alpha=1/n$.

Код Хаффмана

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

Например, пусть вероятности символов $\$ равны $\<1/2,

1/16\>$. Построим бинарное дерево, листьями которого являются символы. Спускаясь вниз от корня (равновероятно выбирая левую или правую ветки), мы будем попадать в эти символы с заданными вероятностями (см. рисунок). Тогда оптимальный код символа будет кодом пути к нему по дереву ($0$ — на левую ветку, $1$ — на правую):

Если $p_b = 1/2^b$, то $b = -\log_2 p_b$ равно числу бит (шагов от корня к листу). Соответственно, средняя длина на символ $b\,p_b$ равна энтропии текста.

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

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

Средняя длина кода Хаффмана на символ больше или равна энтропии $H$ распределения вероятностей символов и меньше, чем $H_<\max>=\log_2 n$. Длина кода каждого символа обычно (но не всегда) равна целой части $-\log_2 p_\alpha$.

Кросс-энтропия

Рассмотрим два набора вероятностей $P=\$ и $Q=\$. Степень различности этих распределений характеризует кросс-энтропия: $$ H(P,Q) = -\sum^n_ <\alpha=1>p_\alpha\,\ln q_\alpha. $$

Она достигает минимума, когда распределения совпадают $p_\alpha=q_\alpha$ (это доказывается также, как и для энтропии). На Python кросс-энтропию легко вычислить при помощи библиотеки numpy: Приведём примеры кросс-энтропии: Заметим, что для любых $P,Q$ справедливо неравенство $H(P) \le H(P,Q)$.

Кросс-энтропия непосредственно связана с расстоянием Кульбака — Лейблера: $$ D_(P,Q) = \sum^n_ <\alpha=1>p_\alpha \ln \frac = H(P,Q)-H(P). $$ Это расстояние всегда неотрицательно и равно нулю, когда распределения вероятностей $P$ и $Q$ совпадают.
В отличии от обычных метрик, это расстояние несимметрично: $D_(P,Q)\neq D_(Q,P)$.

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

Пусть есть словарь $\mathcal=\. w^<(\text)>\>$, состоящий из $\text=|\mathcal|$ слов (или символов). Последовательность $\mathcal= w_1\,w_2. \,w_N$, где $w_i\in \mathcal$ образует текст длиной $N=\mathrm(\mathcal)$. .

Пусть для каждого слова известны $\text$ вероятностей $P(w_i)$ и $\text^2$ условных вероятностей $P(w_i\to w_j)$. Тогда можно определить условную энтропию: $$ H_1 = — \sum_i P\bigr(w^<(i)>\bigr)

\sum_j P\bigr(w^<(i)>\to w^<(j)>\bigr)\,\log P\bigr(w^<(i)>\to w^<(j)>\bigr). $$ Аналогично, при помощи $P(w^<(i)>,w^<(j)>)$ и $P(w^<(i)>,w^ <(j)>\to w^<(k)>)$, можно определить условную энтропию второго порядка $H_2$ и т.д.

Перплексия

Вероятностная языковая модель для данного слова $w$, по его контексту $\ <\mathcal— w\>$ (текст $\mathcal$ без слова $w$) или по предшествующим к $w$ словам предсказывает вероятность этого слова: $P(w|\mathcal — w)$. Одной из метрик качества различных моделей является перплексия. Чем меньше перплексия, тем лучше модель.

Перплексией (perplexity) текста $\mathcal$ длиной $N=\mathrm(\mathcal)$ называют: $$ \mathcal

= \exp\Bigr( -\frac<1>\,\sum^_ \ln P(w_i|\mathcal-w_i) \Bigr). $$

Если вероятности $P(w_i|\mathcal-w_i)$ оцениваются по предшествующей слову $w_i$ истории $P(w_i|w_1. w_)$ то, по цепному правилу имеем (сумма логарифмов равна логарифму произведения): $\mathcal

=\exp(-\ln P(w_1. w_n)/N)$, или: $$ \mathcal

= P(w_1. w_N)^ <-1/N>\equiv \sqrt[N]<\frac<1>>. $$ Чем выше совместная вероятность последовательности слов, тем меньше перплексия. Важно помнить, что языковая модель должна возвращать «честную», нормированную на единицу вероятность слова $P(w_i|\mathcal-w_i)$.
Т.е. сумма таких вероятностей по всем словам словаря должна равняться единице. Если это не так, то перплексия может оказаться неоправданно заниженной (например, когда для любого слова словаря модель возвращает 1).

Простейшая языковая модель, независимо от контекста, предсказывает безусловную вероятность слова: $P(w|\mathcal — w) = P(w)$. В этом случае в сумме будет $N^ <(i)>= P(w^<(i)>)\cdot N$ раз встречаться слово $w^<(i)>$ и перплексия равна экспоненте от энропии вероятностей слов словаря: $$ \mathcal

_ <1>= \exp\Bigr( -\sum^_ <\alpha=1>P\bigr(w^<(\alpha)>\bigr)\,\ln P\bigr(w^<(\alpha)>\bigr) \Bigr)

e^, $$ где $\mathcal=\. w^<(n)>\>$ — словарь из $n$ слов. Когда в модели все вероятности равны $P(w)=1/n$, перплексия равна мощности словаря (количеству различных слов): $\mathcal

_0 = n$. Минимальное значение перплексии равно 1. Перплексия, в отличии от энтропии, не зависит от основания логарифма (можно заменить $\ln\mapsto \log_2$ и $e\mapsto 2$).

Перплексию иногда интерпретируют как степень ветвления текста (branching factor) (сколько возможно веток для очередного слова, взвешенных на вероятности этих веток).

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

Обычно языковую модель строят на одном множестве документов, а перплексию измеряют на другом. Чтобы не было тематического или стилевого перекоса, каждый документ разбивается на тренировочную и тестовую части (hold-out perplexity). Если в качестве ошибки модели используют кросс-энтропию CE в расчёте на слово, то перплексия равна $\mathcal

=\exp\text$.

Существует 1B Word Benchmark data set длиной около 829’250’940 английских слов со словарём 793’471 слов (в архиве 11 GB). На этом датасете часто сравнивают различные языковые модели (см. тут и тут). Так 5-граммные модели с интерполяцией дают значение $\mathcal

=67$ (1.76B параметров), LSTM + CNN INPUTS (см. этот документ) $\mathcal

=30$ (1.04B параметров), а ансамбль моделей достигает значения $\mathcal

=23.7$ (2016).

Дифференциальная энтропия

Для непрерывных случайных величин энтропия их плотности вероятности $p(x)$ определяется аналогичным образом: $$ H[X] = -\int\limits_X p(x)\,\ln p(x)\,dx = — \langle \ln p(x) \rangle $$ и называется дифференциальной энтропией. Рассмотрим в качестве примера нормальное (гауссово) распределение со средним $\mu$ и дисперсией $D$: $$ p(x) = \frac<1><\sqrt<2\pi D>>\, e^<-\frac<(x-\mu)^2><2D>>. $$ Дифференциальная энтропия этого распределения равна: $$ H[X]

\frac<1><2>\ln (2\pi\,D\,e). $$ Обратим внимание, что в отличии от энтропии для дискретных случайных чисел, дифференциальная энтропия может быть отрицательной (выше при $D \lt 1/2\pi e$). Связано это с тем, что значения плотности вероятности (в отличии от вероятностей) могут быть больше единицы.

Можно показать, что нормальное распределение имеет наибольшую дифференциальную энтропию среди всех распределений с такой же дисперсией (доказывается это при помощи лагранжевого метода с двумя связями — на нормировку распределения и равенство его дисперсии $D$). Поэтому, для любой случайной величины $$ \langle(x-x_<ср>)^2\rangle \ge \frac><2\pi e>. $$

1. Теория информации + ML. Энтропия

Давно хотел сделать учебные материалы по теме Теория Информации + Machine Learning. Нашёл старые черновики и решил довести их до ума здесь, на хабре.

Теория Информации и Machine Learning мне видятся как интересная пара областей, глубокая связь которых часто неизвестна ML инженерам, и синергия которых раскрыта ещё не в полной мере.

Когда я говорю коллегам, что LogLoss на тесте и Mutual Information между прогнозом и прогнозируемой величиной связаны напрямую, и по несложной формуле можно из одного получить второе, они часто искренне удивляются. В википедии со страницы LogLoss есть ссылка на Mutual Information, но не более того.

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

Начнём с базовых понятий Энтропии, Информации в сообщении, Взаимной Информации (Mutual Information), пропускной способности канала. Далее будут материалы про схожесть задач максимизации Mutual Information и минимизации Loss-а в регрессионных задачах. Затем будет часть про Information Geometry: метрику Фишера, геодезические, градиентные методы, и их связь с гауссовскими процессами (движение по градиенту методом SGD — это движение по геодезической с шумом).

Также нужно затронуть AIC, Information Bottleneck, поговорить про то, как устроен поток информации в нейронных сетях – Mutual Information между слоями (Information Theory of Deep Learning, Naftali Tishby) и многое другое. Не факт, что получится всё перечисленное охватить, но попробую начать.

1. Базовые определения

Есть три более менее разных способа прийти к формуле энтропии распределения

Давайте их опишем. Начнём с базовых определений.

Опр. 1.1: Неопределенность — это логарифм по основанию 2 от числа равновероятных вариантов: . Измеряется в битах. Например, неопределенность неизвестного битового слова длины k равна k.

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

Для не степеней двойки эта функция гладко продолжается. Например,

Важное свойство логарифма:

Поробуйте вывести его из нестрогого определения выше для случая, когда и степени двойки.

Битовые слова длины – это последовательности нулей и единиц длины . Каждый знак в битовом слове называется битом. Например, вот битовые слова длины 5:

00000, 00001, 00010, 00011, 00100, 00101, . , 11100, 11101, 111110, 11111

Их 32 штуки. , то есть неопределённость слова длины 5 равна 5.
Именно столько неизвестных бит в неизвестном битовом слове длины 5.

Таким образом, каждый знак в битовом слове называется битом, но ещё бит – это единица измерения неопределённости. И из этого примера понятно почему.

Для краткости везде далее обозначается просто как .

Опр. 1.2: Информация в сообщении — это разница неопределенностей до получения сообщения и после

Тоже измеряется в битах.

Например, Ваня загадал число от 1 до 100. Нам сообщили, что оно меньше либо равно 50. Неопределённость до сообщения равна , а после — . То есть в этом сообщении 1 бит информации. Умело задавая бинарные вопросы (вопросы, на которые ответ ДА или НЕТ), можно извлекать ровно 1 бит информации.

Некоторые вопросы неэффективны, например, вопрос «верно ли, что число меньше либо равно 25?» уменьшит неопределенность на бита с вероятностью 0.25, а с вероятностью 0.75 только на бит, то есть в среднем на бит. Если вы своим вопросом разбиваете множество вариантов в пропорции , то среднее количество бит информации в ответе равно .

Это выражение будем обозначать через или . Здесь мы как программисты перегрузим функцию H так, чтобы она работала для двух случаев — когда на вход поступает пара чисел, сумма которых равна 1, и когда одно число из отрезка [0, 1].

Опр. 1.3:

Видно, что задавая бинарные вопросы, в можно извлекать максимум 1 бит информации в среднем (максимальное значение функции . Ещё раз: да, можно сразу задавать вопросы типа «Число равно 57?» и если повезёт, получать log(100) бит информации. Но если не повезёт, вы получите лишь log(100/99) бит информации. Среднее число бит информации для такого сорта вопросов равно что заметно меньше 1.

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

Если мы будем задавать не бинарные вопросы, а вопросы, которые подразумевают в качестве ответа натуральное число от 1 до M, то мы сможем в одном ответе получать более, чем один бит информации. Если мы задаём такой вопрос, для которого все M ответов равновероятны, то в среднем мы будем получать бит. Если же вероятность ответа i равна p(i), то среднее число бит в ответе будет равно:

Опр. 1.4: Энтропия дискретного распределения задаётся формулой (1) выше.

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

ИТАК: Первый простой способ прийти к формуле энтропии — это посчитать среднее число бит информации в ответе на вопрос с разновероятными ответами.

Давайте пойдём дальше. Пусть Ваня не загадывает число, а сэмплирует его из распределения . Сколько бинарных вопросов нужно задать Ване, чтобы узнать выпавшее число? Интуитивно понятно, что нужно разбить множество вариантов на два подмножества уже равных не по количеству элементов, а по суммарному значению вероятности, и спросить Ваню, в каком из двух находится выпавшее число. Получить ответ и продолжить в том же духе с новым уменьшенным множеством вариантов — снова разбить его на два с примерно равным весом, спросить в каком из двух находится выпавшее число и так далее. Идея хорошая, но не совсем рабочая. Оказывается, правильнее поступать с конца и начать строить дерево разбиений снизу, а именно, найти два самых мало вероятных варианта и объединить их в один новый вариант, тем самым уменьшив число вариантов на 1. Потом снова найти два самых маловероятных и снова объединить их в один новый, и так далее, построив конечном итоге бинарное дерево. В листьях этого дерева находятся числа. Внутренние вершины помечены множеством чисел из поддерева, корнем которого они являются. Корень дерева помечен множеством всех чисел. Это дерево и даёт алгоритм того, как нужно задавать вопросы Ване. Нужно двигаться с корня дерева и спрашивать Ваню, куда по этому дереву идти — влево или вправо (в каком из двух множеств вершин детей находится выпавшее число). Это дерево даёт не только рецепт самого быстрого в среднем метода угадывания числа, но ещё и алгоритм Хаффмана сжатия данных.

Задача 1.1: Изучите код Хаффмана. Докажите, что текст с исходной длиной символов N имеет в сжатом виде длину, ограниченную снизу величиной бит и при удачных обстоятельствах её достигает.

ИТАК: Формула возникает при решении задачи о минимальном среднем числе бинарных вопросов, которые нужно задать, чтобы выведать выпавшее значение случайной величины с распределением

Это второй способ прийти к формуле (1).

Для случайной величины будем использовать такие обозначения для энтропии его распределения (ещё раз «перегрузим» функцию H):

Есть ещё один, третий, простой способ прийти к формуле энтропии, но нужно знать формулу Стирлинга.

Задача 1.2: Есть неизвестное битовое слово длины k (последовательность единиц и ноликов, всего k символов). Нам сообщили, что в нём 35% единичек. Чему равно при больших k?

Задача 1.3: У Вани есть неизвестное слово длины в алфавите длины M. Он сообщил доли всех букв в слове — .
Чему равно при больших ?

ИТАК: Задача 1.3 и есть третий способ прийти к формуле (1).

Опр. 1.5: Информация в сообщении по некоторую случайную величину — это разница энтропий:

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

Задача 1.4: Чему равна энтропия дискретного распределения ?Сколько информации содержится в сообщении где имеет распределение ?

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

Задача 1.5: Приведите пример конечного распределения и сообщения, которое не уменьшает, а увеличивает неопределённость.

, а сообщение message = «это не первый элемент». Тогда

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

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

Задача 1.6: Напишите формулу для энтропии распределения Пуассона

Найдите простое приближение для больших .

Задача 1.7: Дано распределение вещественной случайной величины. Пусть — это сколько бинарных вопросов в среднем нужно задать, чтобы узнать какое-то выпавшее значение случайной величины с точностью до . Найдите приближённое выражение для малых значений .

Нужно разбить ось x на корзинки длиной посчитать вероятности каждой корзинки и посчитать Если значениедостаточно мало, то ответ можно приблизить интегралом:

(см. определение энтропии непрерывного распределения ниже).

Опр. 1.6: Энтропия непрерывного распределения равна

Здесь мы ещё раз перегрузили значение символа H для случая, когда аргумент есть функция плотности вероятности (PDF).

Задача 1.8: Даны два распределения и двух вещественных случайных величин. К чему стремится разница при ?

Задача 1.9: Чему равна энтропия нормального распределения ?

Задача 1.10: Напишите формулу для энтропии экспоненциального распределения .

Задача 1.11: Случайная величина является смесью двух случайных величин, то есть её распределение есть взвешенная сумма распределений:

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

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

В этой задаче хотелось показать, что даже в простом случае непересекающихся носителей энтропии не просто складываются с соответствующими весами, а появляется добавка . Если веса равны 1/2, то эта добавка равна 1.

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

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

Задача 1.12: Случайная величина равновероятно равна 0 или 1. Случайная величина зависит от : если , то сэмплируется из , а если , то сэмплируется из . Сколько бит информацию про случайную величину содержится в сообщении (как функция от )?

Есть такой численный ответ:

Понятно, что график начинается с 0 и стремится к 1:

при два гаусса одинаковые и сообщение про то, какой из них был выбран ничего не даёт;

при имеем смесь (mixture) двух гауссовских распределений с сильно разнесёнными центрами; сообщение про значение говорит, в каком из двух «гауссовских колпаков» находится ответ, и число вариантов уменьшается примерно в два раза, а неопределённость уменьшается на 1; «примерность» связана с тем, что «колпаки» перекрываются, но размер перекрытия быстро уменьшается с ростом .

в окрестности рост квадратичный, примерно .

а приближение к 1 происходит примерно по закону

Задача 1.13: Случайная величина устроена так: сначала сэмплируется число из экспоненциального распределения со средним , а потом сэмплируется случайное число из распределения Пуассона, с параметром . Мы получили сообщение, что одно измерение дало . Сколько бит информации мы получили про случайную величину ? Дайте численный ответ. Сколько бит информации даст последовательность измерений 10, 9, 11, 8, 10?

Задача 1.14: Случайная величина устроена так: сначала один раз сэмплируется число из бета-распределения с параметрами , а потом сэмплируется случайное число из биномиального распределения с параметрами . Мы получили сообщение, что одно измерение дало 10 (то есть 10 из 100 бросаний монетки выпали орлом). Сколько бит информации мы получили про скрытую случайную величину ? Дайте численный ответ. Сколько бит информации даст последовательность измерений 10, 9, 11, 8, 10?

Задача 1.15: Случайные величины сэмплированы из бета-распределения с параметрами . Сами нам неизвестны, но нам дали 10 измерений из 10 биномиальных распределений с параметрами и это наше знание про . Сколько бит информации мы получим в среднем про случайную биномиальную величину с параметрами и когда нам назовут значение ? А если известны абсолютно точно (случай )? А если 10 заменить на ?

Эту задачу можно сформулировать на языке ML так: у нас есть категориальная фичадля прогноза булевой величины (‘кликнет пользователь на баннер или нет’). Насколько хорош будет наш прогноз, если в обучающих данных нам известны лишь исторические данные про количество кликов и некликов по этим 10 категориям?

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

Начальная дисперсия равна . После измерений дисперсия уменьшается до величины
.

Из начальной энтропии вычитаем конечную энтропию и и получаем

Таким образом, при больших информация растёт как , а погрешность уменьшается примерно пропорционально .

То есть число верных знаков в десятичной записи числа растёт как . Если вам хочется получить ещё один верный десятичный знак числа необходимо увеличить число измерений в 100 раз

Часть 2 – Mutual Information. В ней рассказывается про Взаимную Информацию – концепцию, которая открывает двери в помехоустойчивое кодирование, алгоритмы сжатия, а также даёт новый взгляд на задачи Машинного Обучения.

Часть 3 – ML & Mutual Information. Основы ML в контексте теории информации.

Как определяется энтропия дискретных случайных величин

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

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

Например, если опыт состоит в определении возраста случайно выбранного студента 1-го курса дневного отделения вуза, то с большой долей уверенности можно утверждать, что он окажется менее 30 лет; хотя по положению на дневном отделении могут обучаться лица в возрасте до 35 лет, чаще всего очно учатся выпускники школ ближайших нескольких выпусков. Гораздо меньшую определенность имеет аналогичный опыт, если проверяется, будет ли возраст произвольно выбранного студента меньше 18 лет. Для практики важно иметь возможность произвести численную оценку неопределенности разных опытов. Попробуем ввести такую количественную меру неопределенности.

Начнем с простой ситуации, когда опыт имеет %%n%% равновероятных исходов. Очевидно, что неопределенность каждого из них зависит от n, т.е.

Мера неопределенности является функцией числа исходов %%f(n)%%.

Можно указать некоторые свойства этой функции:

1. %%f(1) = 0%%, поскольку при %%n = 1%% исход опыта не является случайным и, следовательно, неопределенность отсутствует;
2. %%f(n)%% возрастает с ростом %%n%%, поскольку чем больше число возможных исходов, тем более затруднительным становится предсказание результата опыта.

* Для обозначения опытов со случайными исходами будем использовать греческие буквы (%%α%%, %%β%% и т.д.), а для обозначения отдельных исходов опытов (событий) — латинские заглавные (%%А%%, %%В%% и т.д.).

Для определения явного вида функции %%f(n)%% рассмотрим два независимых опыта %%α%% и %%β*%% с количествами равновероятных исходов, соответственно %%n_α%% и %%n_β%%. Пусть имеет место сложный опыт, который состоит в одновременном выполнении опытов α и β; число возможных его исходов равно %%nα \cdot nβ%%, причем, все они равновероятны. Очевидно, неопределенность исхода такого сложного опыта %%α ^ β%% будет больше неопределенности опыта %%α%%, поскольку к ней добавляется неопределенность %%β%%; мера неопределенности сложного опыта равна %%f(n_α \cdot n_β)%%. С другой стороны, меры неопределенности отдельных %%α%% и %%β%% составляют, соответственно, %%f(n_α)%% и %%f(n_β)%%. В первом случае (сложный опыт) проявляется общая (суммарная) неопределенность совместных событий, во втором — неопределенность каждого из событий в отдельности. Однако из независимости %%α%% и %%β%% следует, что в сложном опыте они никак не могут повлиять друг на друга и, в частности, %%α%% не может оказать воздействия на неопределенность %%β%%, и наоборот. Следовательно, мера суммарной неопределенности должна быть равна сумме мер неопределенности каждого из опытов, т.е. мера неопределенности аддитивна:

$$f(n_α \cdot n_β)=f(n_α)+f(n_β)

Теперь задумаемся о том, каким может быть явный вид функции %%f(n)%%, чтобы он удовлетворял свойствам (1) и (2) и соотношению (2.1)? Легко увидеть, что такому набору свойств удовлетворяет функция %%log(n)%%, причем можно доказать, что она единственная из всех существующих классов функций. Таким образом:

За меру неопределенности опыта с n равновероятными исходами можно принять число %%log(n)%%.

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

$$log_b n=log_b а\cdot log_a n $$

переход к другому основанию состоит во введении одинакового для обеих частей выражения (2.1) постоянного множителя %%log_b а%%, что равносильно изменению масштаба (т.е. размера единицы) измерения неопределенности. Поскольку это так, имеется возможность выбрать удобное (из каких-то дополнительных соображений) основание логарифма. Таким удобным основанием оказывается 2, поскольку в этом случае за единицу измерения принимается неопределенность, содержащаяся в опыте, имеющем лишь два равновероятных исхода, которые можно обозначить, например, ИСТИНА (True) и ЛОЖЬ (False) и использовать для анализа таких событий аппарат математической логики.

Единица измерения неопределенности при двух возможных равновероятных исходах опыта называется бит.

Название бит происходит от английского binary digit, что в дословном переводе означает «двоичный разряд» или «двоичная единица».

Таким образом, нами установлен явный вид функции, описывающей меру неопределенности опыта, имеющего %%n%% равновероятных исходов:

Эта величина получила название энтропия. В дальнейшем будем обозначать ее Н .

Вновь рассмотрим опыт с %%n%% равновероятными исходами. Поскольку каждый исход случаен, он вносит свой вклад в неопределенность всего опыта, но так как все %%n%% исходов равнозначны, разумно допустить, что и их неопределенности одинаковы. Из свойства аддитивности неопределенности, а также того, что согласно (2.2) общая неопределенность равна %%log_2 n%%, следует, что неопределенность, вносимая одним исходом составляет

$$\frac log_2 n = — \frac log_2 \frac = -p \cdot log_2 p $$

где %%р =\frac %% — вероятность любого из отдельных исходов.

Таким образом, неопределенность, вносимая каждым из равновероятных исходов, равна:

$$H=-p \cdot log_2 p

Теперь попробуем обобщить формулу (2.3) на ситуацию, когда исходы опытов неравновероятны, например, %%p(A_1)%% и %%p(A_2)%%. Тогда:

$$H_1=-p(А_1) \cdot log_2 р(А_1)$$ $$H_2=-p(А_2) \cdot log_2 р(А_2)$$

$$H=H_1+H_2=-p(А_1) \cdot log_2 р(А_1)-p(А_2) \cdot log_2 р(А_2)$$

Обобщая это выражение на ситуацию, когда опыт %%α%% имеет %%n%% неравновероятных исходов %%А_1, А_2. А_n%%, получим:

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

$$H(α)\leqslant -log_2 p(A^α)$$

%%А^α%% — обозначает исходы, возможные в опыте α.

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

Для практики формула (2.4) важна тем, что позволяет сравнить неопределенности различных опытов со случайными исходами.

Пример 2.1. Имеются два ящика, в каждом из которых по 12 шаров. В первом -3 белых, 3 черных и 6 красных; во втором — каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей исходов этих опытов?

Согласно (2.4) находим энтропии обоих опытов:

%%Н_β > Н_α%%, т.е. неопределенность результата в опыте β выше и, следовательно, предсказать его можно с меньшей долей уверенности, чем результат α.

Как определяется энтропия дискретных случайных величин

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

Понятие неопределенности

Первым специфическим понятием теории информации является понятие неопределенности случайного объекта, для которого удалось ввести количественную меру, названную энтропией. Начнем с простейшего примера — со случайного события. Пусть, например, некоторое событие может произойти с вероятностью 0,99 и не произойти с вероятностью 0,01, а другое событие имеет вероятности соответственно 0,5 и 0,5. Очевидно, что в первом случае результатом опыта «почти наверняка» является наступление события, во втором же случае неопределенность исхода так велика, что от прогноза разумнее воздержаться.

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

Энтропия и ее свойства

Примем (пока без обоснования) в качестве меры неопределенности случайного объекта А с конечным множеством возможных состояний А1. Аn с соответствующими вероятностями P₁,P₂. P_n величину

которую и называют энтропией случайного объекта А (или распределения . Убедимся, что этот функционал обладает свойствами, которые вполне естественны для меры неопределенности.

Н(p₁. p_n)=0 в том и только в том случае, когда какое-нибудь одно из

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

Дифференциальная энтропия

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

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

Теперь величину К можно принять равной единице измерения х, что приводит к функционалу

который получил название «дифференциальной энтропии». Это аналог энтропии дискретной величины, но аналог условный, относительный: ведь единица измерения произвольна. Запись (3) означает, что мы как бы сравниваем неопределенность случайной величины, имеющей плотность p(x), с неопределенностью случайной величины, равномерно распределенной в единичном интервале. Поэтому величина h(X) в отличие от Н(Х) может быть не только положительной. Кроме того, h(X) изменяется при нелинейных преобразованиях шкалы х, что в дискретном случае не играет роли. Остальные свойства h(X) аналогичны свойствам Н(Х), что делает дифференциальную энтропию очень полезной мерой.

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

Фундаментальное свойство энтропии случайного процесса

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

Назовем каждое такое состояние «символом», множество возможных состояний — «алфавитом», их число m — «объемом алфавита». Число возможных последовательностей длины n, очевидно, равно mn. Появление конкретной последовательности можно рассматривать как реализацию одного из mn возможных событий. Зная вероятности символов и условные вероятности появление следующего символа, если известен предыдущий (в случае их зависимости), можно вычислить вероятность P(C) для каждой последовательности С. Тогда энтропия множества , по определению, равна

На множестве можно задать любую числовую функцию f_n(C), которая, очевидно, является случайной величиной. Определим f_n(C) c помощью соотношения f_n(C) = -[1/n]⋅logP(C).

Математическое ожидание этой функции

Это соотношение является одним из проявлений более общего свойства дискретных эргодических процессов. Оказывается, что не только математическое ожидание величины f_n(C) при n стремящемся к бесконечности имеет своим пределом H, но и сама эта величина f_n(C) стремится к H при n стремящемся к бесконечности. Другими словами, как бы малы ни были e > 0 и s > 0, при достаточно большом n справедливо неравенство

т.е. близость f_n(C) к H при больших n является почти достоверным событием.

Для большей наглядности сформулированное фундаментальное свойство случайных процессов обычно излагают следующим образом. Для любых заданных e > 0 и s > 0 можно найти такое no, что реализация любой длины n > no распадаются на два класса:

1. группа реализаций, вероятность P(C) которых удовлетворяет неравенству |[1/n]⋅log(P(C))+H| < ε
2. группа реализаций, вероятности которых этому неравенству не удовлетворяют.

Cуммарные вероятности этих групп равны соответственно 1-s и s, то первая группа называется «высоковероятной», а вторая — «маловероятной».

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

1. независимо от того, каковы вероятности символов и каковы статистические связи между ними, все реализации высоковероятной группы приблизительно равновероятны. Это следствие, в частности, означает, что при известной вероятности P(C) одной из реализаций высоковероятной группы можно оценить число N₁ реализаций в этой группе: N₁ = 1 / P(C).
2. Энтропия H_n с высокой точностью равна логарифму числа реализаций в высоковероятной группе: H_n = n * H = log N₁
3. При больших n высоковероятная группа обычно охватывает лишь ничтожную долю всех возможных реализаций (за исключением случая равновероятных и независимых символов, когда все реализации равновероятны и и H = log m).

Действительно, из соотношения (9) имеем

Число N всех возможных реализаций есть

Доля реализаций высоковероятной группы в общем числе реализаций выражается формулой

и при H < logm эта доля неограниченно убывает с ростом n. Например, если a = 2, n = 100, H = 2,75, m = 8, то

т.е. к высоковероятной группе относится лишь одна тридцати миллионная доля всех реализаций!

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

что и доказывает справедливость фундаментального свойства в этом случае.

Подведем итог

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

Количество информации

В основе всей теории информации лежит открытие, что «информация допускает количественную оценку». В простейшей форме эта идея была выдвинута еще в 1928г. Хартли, но завершенный и общий вид придал ее Шэннон в 1948г. Не останавливаясь на том, как развивалось и обобщалось понятие количества информации, дадим сразу ее современное толкование.

Количество информации как мера снятой неопределенности

Процесс получения информации можно интерпретировать как «изменение неопределенности в результате приема сигнала». Проиллюстрируем эту идею на примере достаточно простого случая, когда передача сигнала происходит при следующих условиях:

1. полезный (передаваемый) сигнал является последовательностью статистически независимых символов с вероятностями p(x_i),i = 1,m ;
2. принимаемый сигнал является последовательностью символов Y_k того же алфавита;
3. если шумы (искажения) отсутствуют, то принимаемый сигнал совпадает с отправленным Y_k=X_k ;
4. если шум имеется, то его действие приводит к тому, что данный символ либо остается прежним (i-м), либо подменен любым другим (k-м) с вероятностью p(y_k/x_i) ;
5. искажение данного символа является событием статистически независимым от того, что произошло с предыдущим символом.

Итак, до получения очередного символа ситуация характеризуется неопределенностью того, какой символ будет отправлен, т.е. априорной энтропией Н(Х). После получения символа y_k неопределенность относительно того, какой символ был отправлен, меняется: в случае отсутствия шума она вообще исчезает (апостериорная энтропия равна нулю, поскольку точно известно, что был передан символ y_k=x_i), а при наличии шума мы не можем быть уверены, что принятый символ и есть переданный, т.е. возникает неопределенность, характеризуемая апостериорной энтропией H(X/y_k)=H(

В среднем после получения очередного символа энтропия H(X/Y)=M_y

Определим теперь количество информации как меру снятой неопределенности: числовое значение количества информации о некотором объекте равно разности априорной и апостериорной энтропии этого объекта, т.е. I(X,Y) = H(X)-H(X/Y). (1)

Используя свойство 2 энтропии, легко получить, что I(X,Y) = H(Y) — H(Y/X) (2)

В явной форме равенство (1) запишется так:

а для равенства (2) имеем:

Количество информации как мера соответствия случайных процессов

Представленным формулам легко придать полную симметричность: умножив и разделив логарифмируемое выражение в (3) на p(y_k), а в (4) на p(x_i) сразу получим, что

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

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

Формула (5) обобщается на непрерывные случайные величины, если в отношении (1) и (2) вместо Н подставить дифференциальную энтропию h; при этом исчезает зависимость от стандарта К и, значит, количество информации в непрерывном случае является столь же безотносительным к единицам измерения, как и в дискретном:

где р(x), p(y) и p(x,y) — соответствующие плотности вероятностей.

Свойства количества информации

Отметим некоторые важные свойства количества информации.

1. Количество информации в случайном объекте Х относительно объекта Y равно количеству информации в Y относительно Х: I(X,Y) = I(Y,X)
2. Количество информации неотрицательно: I(X,Y) > 0. Это можно доказать по-разному. Например, варьированием p(x,y) при фиксированных p(x) и p(y) можно показать, что минимум I, равный нулю, достигается при p(x,y) = p(x) p(y).
3. Для дискретных Х справедливо равенство I(X,X) = H(X).
4. Преобразование y (.) одной случайной величины не может увеличить содержание в ней информации о другой, связанной с ней, величине: I[y (X),Y] < I(X,Y) (9)
5. Для независимых пар величин количество информации аддитивно: I( ) = ∑ I(X_i,Y_i)

Единицы измерения энтропии и количества информации

Рассмотрим теперь вопрос о единицах измерения количества информации и энтропии. Из определений I и H следует их безразмерность, а из линейности их связи — одинаковость их единиц. Поэтому будем для определенности говорить об энтропии. Начнем с дискретного случая. За единицу энтропии примем неопределенность случайного объекта, такого, что

Легко установить, что для однозначного определения единицы измерения энтропии необходимо конкретизировать число m состояний объекта и основание логарифма. Возьмем для определенности наименьшее число возможных состояний, при котором объект еще остается случайным, т.е. m=2, и в качестве основания логарифма также возьмем число 2. Тогда из равенства

вытекает, что p₁=p₂=1/2. Следовательно, единицей неопределенности служит энтропия объекта с двумя равновероятными состояниями. Эта единица получила название «бит». Бросание монеты дает количество информации в один бит. Другая единица «нит» получается, если использовать натуральные логарифмы. Обычно она употребляется для непрерывных величин.

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

Остановимся еще на одном важном моменте. До сих пор речь шла о среднем количестве информации, приходящемся на пару состояний (x_i,y_k) объектов X и Y. Эта характеристика естественна для рассмотрения особенностей стационарно функционирующих систем, когда в процессе функционирования принимают участие все возможные пары (x_i,y_k). Однако в ряде практических случаев оказывается необходимым рассмотреть информационное описание конкретной пары состояний, оценить содержание информации в конкретной реализации сигнала. Тот факт, что некоторые сигналы несут информации намного больше, чем другие, виден на примере того, как отбираются новости средствами массовой информации (о рождении шестерых близнецов сообщают практически все газеты мира, а о рождении двойни не пишут).

Допуская существование количественной меры информации (x_i,y_k), в конкретной паре (x_i,y_k) естественно потребовать, чтобы индивидуальное и среднее количество информации удовлетворяли соотношению

Хотя равенство имеет место не только при равенстве всех слагаемых, сравнение формул (5) и, например, (4) наталкивает на мысль, что мерой индивидуальной информации в дискретном случае может служить величина

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

Пример

Пусть по выборке (т.е. совокупности наблюдений x=x1. xn требуется отдать предпочтение одной из конкурирующих гипотез (H или H₁), если известны распределения наблюдений при каждой из них, т.е. p(x/H₀) и p(x/H₁). Как обработать выборку? Из теории известно, что никакая обработка не может увеличить количество информации, содержащегося в выборке x (см. формулу (9). Следовательно, выборке x следует поставить в соответствие число, содержащее всю полезную информацию, т.е. обработать выборку без потерь. Возникает мысль о том, чтобы вычислить индивидуальное количество информации в выборке x о каждой из гипотез и сравнить их:

Какой из гипотез теперь отдать предпочтение зависит теперь от величины 7d 0i и от того, какой порог сравнения мы назначим. Оказывается, что мы получили статистическую процедуру, оптимальность которой специально доказывается в математической статистике, — именно к этому сводится содержание фундаментальной леммы Неймана-Пирсона. Данный пример иллюстрирует эвристическую силу теоретико-информационных представлений.

Подведем итог

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

Необходимые сведения о случайных величинах

Кратко перечислим основные понятия, более подробное изложение можно найти в [1], [2], [3].

5.2.1 Энтропия

Количественной мерой неопределенности служит энтропия. Пусть задана дискретная случайная величина , принимающая значения _ ,

Определение 5.10 Энтропия случайной величины определяется равенством:

.

1. 
2. 
3. и , иными словами, есть три случайные величины и :

_ )=0″ />, _ )= 0,08″ /> бит.

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

Пусть двумерная случайная величина задана распределением

_ , _ \right)=-\sum _ ^ ^ >\log

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

Определение 5.12 Условная энтропия задаётся формулой:

величина :

Похожие публикации:

1. Microsoft solitaire collection что это за программа и нужна ли она
2. Как подключить cpp файл c
3. Как показать скрытые столбцы в excel
4. Почему не скачивается музыка с вк