Pull to refresh

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

Reading time 9 min
Views 16K

Давно хотел сделать учебные материалы по теме Теория Информации + 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. Базовые определения

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

H(\{p_1, \ldots, p_M \}) = \sum_{i=1}^M p_i \log(1 / p_i)    \;\;\;\;\;(1)\sum_{i=1}^M p_i =1, \;\; p_i > 0.\;\;\;\;\;\;

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

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

Логарифм

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

\log_2(1)  = 0,  \; \log_2(2) = 1, \; \log_2(4) = 2,\;  \log_2(8)  = 3,\; \log_2(1024) = 10.

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

\log_2(3) = 1.5849\ldots, \; \log_2(10) = 3.3219\ldots

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

\log(x) - \log(y) = \log(x/y)

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

Битовые слова

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

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

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

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

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

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

I(message) = H(before) - H(after)\;\;\;\;\;\;\;(2)

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

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

Некоторые вопросы неэффективны, например, вопрос "верно ли, что число меньше либо равно 25?" уменьшит неопределенность на \log 100 - \log 25 =\log(100/25)= 2бита с вероятностью 0.25, а с вероятностью 0.75 только на  \log(100)-\log(75)=\log(100/75)бит, то есть в среднем на 0.25 \log(1 / 0.25) + 0.75 \log(1 / 0.75) = 0.811278бит. Если вы своим вопросом разбиваете множество вариантов в пропорции x: 1 - x, то среднее количество бит информации в ответе равно  x \log(1/x) + (1 - x ) \log(1/(1-x)).

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

Опр. 1.3: H(\{x, 1-x\}) = H(x) =  x \log (1/x) + (1 - x ) \log(1/(1-x))

График H(x)

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

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

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

H(\{p_1, \ldots, p_M\}) = \sum_{i=1}^M p_i \log(1 / p_i).\;\;\;\;\;\;\;\;(1)

Опр. 1.4: Энтропия дискретного распределения  P=\{p_i\}_{i=1}^Mзадаётся формулой (1) выше.

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

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

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

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

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

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

Для случайной величины \xi будем использовать такие обозначения для энтропии его распределения P=\{p_i\}_{i=1}^M(ещё раз "перегрузим" функцию H):

H(\xi)или H(P)или H(\{p_i\}_{i=1}^M)или H(\{p_i\}_i)

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

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

Ответ

Примерно  \log 2  - (p \log(1 / p) + (1 - p) \log(1 / (1 - p))) = \log 2 - H(\{p, 1-p\}), где p = 0.35

Задача 1.3: У Вани есть неизвестное слово длины kв алфавите длины M. Он сообщил доли всех букв в слове — P = \{p_1, ..., p_M\}.
Чему равно I(message) / kпри больших k?

Ответ
\approx \log M - \sum_{i=1}^M{p_i \log(1 / p_i)} = \log M - H(P)

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

Опр. 1.5: Информация в сообщении по некоторую случайную величину — это разница энтропий: I(message) = H(P_{apriori}) - H(P_{aposteriori})

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

Задача 1.4: Чему равна энтропия дискретного распределения P = \{\lambda ^ i \cdot (1 - \lambda)\}_{i = 0}^{\infty}?Сколько информации содержится в сообщении \xi \ne 0где \xiимеет распределение P?

Ответ:
H(P) = H(\lambda) / (1 - \lambda)I(``\xi \ne 0'') = 0

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

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

Ответ:

P = \{0.8, 0.1,0.1\}, а сообщение message = "это не первый элемент". Тогда P_{after} = \{0, 0.5, 0.5\},\ H(P) = 0.9219,\ H(P_{after}) = 1.0

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

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

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

p_k=e^{-\lambda}{\lambda^k \over k!}, k=0,\;1,\ldots,+\infty.

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

Ответ
H(\{p_k\}_{k=0}^{\infty})={1\over  2} \log (2\pi e \lambda) - {1\over 12 \lambda}-{1\over 24 \lambda^2}+O(1/\lambda^3)

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

Ответ:

Нужно разбить ось x на корзинки длиной \varepsilonпосчитать вероятности p_iкаждой корзинки и посчитать H(\{p_i\}_i)Если значение\varepsilonдостаточно мало, то ответ можно приблизить интегралом:

\sum_i \rho(x_i) \cdot \varepsilon \cdot \log (1 / (\rho(x_i) \cdot \varepsilon) ) \approx \log(1/\varepsilon) - \int_{-\infty}^{+\infty} \rho(x)\log(\rho(x))dx == \log(1/\varepsilon) + H(\rho)

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

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

H(\rho) = -\int_X \rho(x) \log(\rho(x)) dx

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

Задача 1.8: Даны два распределения \rho_1(x)и \rho_2(x)двух вещественных случайных величин. К чему стремится разница Q(\rho_1,  \varepsilon) -  Q(\rho_2, \varepsilon)при \varepsilon\to0?

Ответ:
H(\rho_1) - H(\rho_2)

Задача 1.9: Чему равна энтропия нормального распределения \mathcal{N}(\mu, \sigma)?

Ответ:
1/2  \cdot (1 + \log(2\pi \sigma^2))

Задача 1.10: Напишите формулу для энтропии экспоненциального распределения \rho(x)=e^{-x/a}/a.

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

\rho(x) = w_1\rho_1(x) + w_2\rho_2(x),\;\;\;\;w_1 + w_2 = 1

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

Ответ
H(\rho) = -\int_{X_1+X_2} \rho(x) \log(\rho(x)) dx \\=-\int_{X_1+X_2} (w_1\rho_1(x)+ w_2\rho_2(x))\log(w_1\rho_1(x) + w_2\rho_2(x)) dx =\\ =-\int_{X_1} w_1\rho_1(x) \log(w_1\rho_1(x)) dx-\int_{X_2} w_2\rho_2(x) \log(w_2\rho_2(x)) dx

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

-w_1\int_{X_1} \rho_1(x) \log(w_1\rho_1(x))- w_2\int_{X_2} \rho_2(x) \log(w_2\rho_2(x))dx=\\=w_1\cdot H_1 + w_2\cdot H_2 -w_1\log w_1 - w_2\log w_2

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

Интерпретация формулы такая: результат измерения с вероятностью w_1находится в X_1и с вероятностью w_2 – в X_2и соответственно нам достанется неопределённость H_1значений на множестве X_1или неопределённость H_2 на множестве X_2. Но чтобы выяснить, в каком из них находится измерение мы потратим в среднем-(w_1\log w_1 + w_2 \log w_2)вопросов.

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

Задача 1.12: Случайная величина \xi равновероятно равна 0 или 1. Случайная величина \nuзависит от \xi: если \xi=0, то \nuсэмплируется из \mathcal{N}(0, 1), а если \xi=1, то \nuсэмплируется из \mathcal{N}(\mu, 1). Сколько бит информацию про случайную величину \nu содержится в сообщении ``\xi=0"(как функция от \mu)?

Ответ

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

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

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

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

  • в окрестности \mu=0рост квадратичный, примерно  (\mu/2.37)^2.

  • а приближение к 1 происходит примерно по закону 1-e^{-(\mu/2.74)^2 - 0.21}

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

Ответ

 I(``x=10") = (4861 - 2520 \gamma - 252\log(3628800/11))/(252 \log(2)) \approx 1.17.

I(``x=10, 9, 11, 8, 10") = 3.729.

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

Задача 1.15: Случайные величины p_1,\; p_2,\;\ldots,p_{10}сэмплированы из бета-распределения с параметрами \alpha=9, \beta=1. Сами p_1,\; p_2,\;\ldots,p_{10} нам неизвестны, но нам дали 10 измерений x_1,\;x_2,\;\ldots,x_{10}из 10 биномиальных распределений с параметрами n=100, \;p_iи это наше знание про p_1,\; p_2,\;\ldots,p_{10}. Сколько бит информации мы получим в среднем про случайную биномиальную величину с параметрами n=100, \;p_iи когда нам назовут значение i? А если p_1,\; p_2,\;\ldots,p_{10} известны абсолютно точно (случай n=\infty)? А если 10 заменить на \infty?

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

Задача 1.16. Случайная величина \xiимеет распределение \mathcal{N}(a,\varepsilon^2). Величина aнам неизвестна, но мы знаем, что она была сэмплирована из распределения \mathcal{N}(0,\sigma^2). Сколько информации про a мы в среднем получим от первого измерения величины \xi? Как будет расти количество полученной информации с числом измерений?

Ответ

Начальная дисперсия aравна \sigma^2. После mизмерений дисперсия уменьшается до величины
\sigma_m^2=\left({1\over \sigma^2} + {m \over \varepsilon^2}\right)^{-1}.

Из начальной энтропии C + 0.5\cdot \log(\sigma^2) вычитаем конечную энтропию и C + 0.5\cdot \log(\sigma_m^2) и получаем

{1\over  2} \cdot \log\left(1 + m\cdot {\varepsilon^2 \over \sigma^2}\right)

Таким образом, при больших m информация растёт как c + {1\over 2}\log(m), а погрешность \sigma_m уменьшается примерно пропорционально 1/\sqrt{m}.

То есть число верных знаков в десятичной записи числа a растёт как \log(\sqrt{m}) /\log(10). Если вам хочется получить ещё один верный десятичный знак числа a необходимо увеличить число измерений m в 100 раз

Продолжение:

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

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

Tags:
Hubs:
+14
Comments 1
Comments Comments 1

Articles