Задачник по теории информации + ML. Часть 110.09.2022 23:02

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

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

Опр. 1.1: Неопределенность — это логарифм по основанию 2 от числа равновероятных вариантов: $H = \log_2{N}$ . Измеряется в битах. Например, неопределенность неизвестного битового слова длины k равна k. Для краткости везде далее $\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 x - (1 - x ) \log(1-x)$ .

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

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

График H (x)

Видно, что задавая бинарные вопросы, в среднем можно в извлекать максимум 1 бит информации. Ещё раз: да, можно сразу задавать вопросы типа «Число равно 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 для случая, когда на вход поступает дискретное распределение.

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

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

Задача 1.1: Изучите код Хаффмана. Докажите, что текст с исходной длиной символов N имеет в сжатом виде длину, ограниченную снизу величиной $N\cdot H(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: У Вани есть неизвестное слово длины в алфавите длины M. Он сообщил доли всех букв в слове — $P = \{p_1, ..., p_M\}$ .
Чему равно I(message) / 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$ имеет распределение ?

Ответ:

$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$ .

Ответ:

Опр. 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.

Интерпретация формулы такая: результат измерения с вероятностью 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 больше, чем энтропия одного нормального распределения. Носители нормальных случайных величин равны всей прямой, а значит пересекаются, но в случае сильно разных средних можно этим пренебречь.

Задача 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:

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

Ответ

I(``x=10 .

I(``x=10, 9, 11, 8, 10 .

Задача 1.14: Случайная величина $\xi$ устроена так: сначала один раз сэплируется число из бета-распределения с параметрами $\alpha=9, \beta=1$ , а потом сэплируется случайное число из биномиального распределения с параметрами $n=100, \;p$ . Мы получили сообщение, что одно измерение $\xi$ дало 10 (то есть 10 из 100 бросаний монетки выпали орлом). Сколько бит информации мы получили про скрытую случайную величину ? Дайте численный ответ. Сколько бит информации даст последовательность измерений 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$ и когда нам назовут значение ? А если $p_1,\; p_2,\;\ldots,p_{10}$ известны абсолютно точно (случай $n=\infty$ )? А если 10 заменить на $\infty$ ?

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