Часть 1 – Энтропия

Часть 2 – Mutual Information

В этой 3-й части мы поговорим про Machine Learning, а именно, про задачу прогноза, в контексте теории информации.

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

Что такое Machine Learning?

Чтобы двигаться дальше, нам нужны базовые понятия из ML, такие как: факторы, target, Loss-функция, обучающий и тестовый пулы, overfitting и underfitting и их варианты, регуляризация, разные виды утечки данных.

Факторы (features) – это то, что вам даётся на вход, а сигнал (target) – это то, что нужно спрогнозировать, используя факторы. Например, вам нужно спрогнозировать температуру завтра в 12:00 в определённом городе – это target, а дано вам множество чисел про сегодня и предыдущие дни: температура, давление, влажность, направление и сила ветра в этом и соседних городах в разное время дня – это факторы.

Обучающие Данные – это множество примеров (aka сэмплов) с известными правильными ответами, то есть строчки в таблице, в которой есть и поля с факторами features=(f₁, f₂, ..., f_n), и поле target. Данные принято делить на две части – обучающий пул (train set) и тестовый пул (test set). Выглядит это примерно так.

Обучающий пул:

id	f₁	f₂	...	*target*	*predict*
1	1.234	3.678	...	1.23	?
2	2.345	6.123	...	2.34	?
...	...	...	...	...	...
18987	1.432	3.444	....	5.67	?

Тестовый пул:

id	f₁	f₂	...	*target*	*predict*
18988	6.321	6.545	...	4.987	?
18989	4.123	2.348	...	3.765	?
...	...	...	...	....	...
30756	2.678	3.187	...	2.593	?

В общих чертах задачу прогноза можно сформулировать в духе соревнования на kaggle.com:

Задача прогноза (задача ML). Вам дан обучающий пул. Реализуйте в виде кода функцию $\mathcal{P}(f_1, \ldots, f_k),$ которая по заданным факторам возвращает значение, максимально близкое к target. Мера близости задана с помощью Loss-функции, и значение этой функции называется ошибкой прогноза: где $predict=\mathcal{P}(f_1,\ldots,f_k).$ Качество прогноза определяется средним значением ошибки во время применения этого прогноза в жизни, но по факту для оценки этой средней ошибки будет использоваться некоторый тестовый пул, который от вас скрыт.

У величины $\xi = predict - target$ есть специальное название – невязка. Два популярных варианта Loss-функции для задач прогноза вещественной величины – это:

средний квадрат невязки, что также называют среднеквадратической ошибкой или mse (mean square error);
средний модуль невязки, что также называют L1-ошибкой.

На практике задача ML более общая и высокоуровневая. А именно, нужно разработать в меру универсальную ML-модель – способ получения функций $\mathcal{P}(f_1, \ldots, f_n)$ по данному обучающему пулу и заданной Loss-функции. А также нужно уметь делать model evaluation: мониторить качество прогноза в работающей системе, уметь обновлять обученные модели (пошагово, делая новые версии, или модифицируя внутренние веса модели в режиме online), улучшать качество модели, контролировать чистоту и качество факторов.

Процесс получения функции $\mathcal{P}(f_1, \ldots, f_n)$ по обучающему пулу называется обучением. Популярны такие варианты ML-моделей (классы моделей):

Линейная модель, в которой $\mathcal{P}(f_1,\ldots,f_n)=\sum_{i} w_i\cdot f_i$ , и процесс обучения сводится к подбору параметров $(w_1,w_2,\ldots, w_n)$ , что делается обычно методом градиентного спуска.
Gradient boosted trees (GBT) – модель, в которой функция выглядит как сумма нескольких слагаемых (сотен, тысяч), где каждое слагаемое – это решающее дерево, в узлах которого находятся условия на факторы, а в листьях – конкретные числа; каждое слагаемое можно представлять как какую-то систему вложенных if-конструкций с условиями на значения факторов, где в конечных узлах находятся просто числа. GBT – это не только про то, что решение есть сумма деревьев, но и вполне конкретный алгоритм получения этих слагаемых. Для обучения GBT есть много готовых программ: CatBoost, xgboost. См. статью на хабре.
Neural Networks – в простейшем базовом варианте это модель вида $\mathcal{P}(\vec{f}) = W_k\odot W_{k-1}\odot \ldots W_1 \odot \vec{f}$ , где – матрицы, размеры которых определяет разработчик модели, факторы представлены в виде вектора $\vec{f} = \|f_1,\ldots,f_n\|^{T}$ , оператор $\odot$ соответствует умножению вектора на матрицу с последующим обнулением всех отрицательных чисел в результирующем векторе. Операторы выполняются в порядке справа налево – это важно в случае наличия такого обнуления. Матрицы называются слоями нейросети, а количество матриц – глубиной нейросети. Вместо обнуления отрицательных можно брать произвольные другие нелинейные преобразования. Если бы не было нелинейных преобразований после умножения вектора на матрицу, все матрицы можно было бы "схлопнуть" в одну и пространство возможных функций не отличалось бы того, что задаётся линейной моделью. Я описал линейную архитектуру нейросети, но возможны и более сложные, например,

$\mathcal{P}(\vec{f})=W_6\odot(W_1\odot W_2 \cdot \vec{f} + W_3\odot W_4 \odot W_5\odot W_2\odot \vec{f})+W_7\odot \vec{f}$ .
Кроме самых разных поэлементных нелинейных преобразования и умножения на матрицу в нейросетях могут использоваться операторы скалярного произведения векторов и оператор поэлементного максимума для двух векторов одной размерности, объединения векторов в один более длинный и др. Можно думать об общей архитектуре для функции , когда на вход поступает вектор, а дальше с помощью операторов $\{+,-,\cdot, \max \}$ , нелинейных функций $\{\tanh, \mathrm{abs}, \max(0, \cdot), \ldots\}$ и весов $\{w_1, w_2, \ldots\}$ конструируется ответ. В этом смысле нейросети могут представлять самой функции довольно общего вида. По факту, архитектуру функции $\mathcal{P}$ называют нейросетью тогда, когда в ней присутствует что-то похожее на цепочку вида $W_k\odot W_{k-1}\odot \ldots W_1 \odot \vec{f}$ . А так, мы по сути имеем задачу регрессии – подобрать параметры (веса) в параметрически заданной функции, чтобы минимизировать ошибку. Есть множество методов обучения нейросетей, они в своем большинстве итерационные, и за шаг изменения весов отвечает модуль, который программисты называют оптимизатором, см. например AdamOptimizer.

Терминология ML

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

Overfitting

Overfitting (переобучение) – это когда выбранная вами модель сложнее, чем реальность, стоящая за target И/ИЛИ данных слишком мало, чтобы позволить себе обучать такую сложную модель. Есть две основные причины overfitting:

too complex model: Устройство модели сильно сложнее, чем реальность или в своей сложности ей не соответствует. Проще это визуализировать на примере однофакторной модели.
Пусть в обучающем пуле 11 точек а модель – суть многочлен 10-й степени. Можно подобрать такие коэффициенты в многочлене, что он "заглянет" в каждую точку обучающего пула, но при этом не будет обладать хорошим качеством прогноза:
Голубая линия – многочлен 10 степени, который смог в точности воспроизвести обучающий пул из 11 точек. Но правильная модель скорее линейная (чёрная линия), а отклонения от неё – это или шум, или что-то, объясняемое факторами, которых у нас нет
Многочлен 10-й степени – это очевидный и часто используемый пример переобучения. Многочлены невысокой степени, но от многих переменных тоже могут давать overfitting. Например, вы можете подбирать модель predict = многочлен степени 3 от 100 факторов (кстати, сколько в нём коэффициентов?), в то время как реальность соответствует predict = многочлен степени 2 от факторов + случайный шум. При этом, если у вас данных довольно много, то классические методы регрессии могут дать приемлемый результат, и коэффициенты при членах степени 3 будут очень маленькими. Эти члены степени 3 будут вносить маленький вклад в ответ при прогнозе для типичных значений факторов (как в случае с интерполяцией). Но в зоне крайних значений факторов, где прогноз уже скорее экстраполяция, а не интерполяция, высокие степени будут вносить заметный вклад и портить качество прогноза. Ну и, конечно, когда данных мало, шум может начать восприниматься за чистую монету, и прогноз будет стараться заглянуть в каждую точку обучающего пула.
insufficient train data: Модель может более менее соответствовать реальности, но при этом вы можете не иметь достаточное количество обучающих данных. Приведём опять пример с многочленом: пусть и реальность и ваша модель есть многочлен 3-й степени от двух факторов. Этот многочлен задаётся 10 коэффициентами, то есть пространство возможных прогнозаторов у вас 10-мерное. Если в обучающем пуле у вас 9 примеров, то, записав равенство "многочлен(features_i) = target_i" для каждого примера, вы получите 9 уравнений на эти коэффициенты, и их недостаточно, чтобы однозначно определить 10 коэффициентов. В пространстве возможных прогнозаторов вы получите прямую и каждая точка на этой прямой есть прогнозатор, который идеально повторяет то, что у вас в обучающем пуле. Вы можете случайно выбирать один из них, и это с высокой вероятностью будет плохой прогнозатор.
- Важное замечание про обучение многопараметрических моделей. Пример выше может показаться искусственным, но правда в том, что современные нейросетевые модели могут содержать миллионы параметров или даже больше. Например, языковая модель GPT3 содержит 175 млрд. параметров.
  Если в вашей модели N = 175 млрд. параметров, а размер обучающего пула M = 1 млрд, то в общем случае вы имеете бесконечное множество моделей идеально подходящих под обучающий лог, и это множество – суть многообразие размерности N - M = 174 млрд.
  В случае с глубокими многопараметрическими нейросетями эффект "insufficient train data" проявляется в полный рост, если действовать неправильно. А именно, если искать строгий минимум ошибки на обучающем пуле, то получается плохой, overfitted, прогнозатор. Поэтому на практике так не делают. Выработаны интересные техники и интуиция про то, как обучать модель с N параметрами на M примерах, где M заметно меньше N. Используются регуляризационные добавки к Loss-функции (L2, L1), Stochastic Gradient Descent, Dropout Layers, Early Stopping, prunning и другие техники.
  ВАЖНО: Знание этих техник и умение их применять во многом и определяет экспертизу в ML.

Underfitting

Underfitting – это когда модель прогноза проще, чем реальность. Также как и в случае с overfitting здесь есть две основных причины:

too simplistic model: выбрана слишком простая модель, сильно упрощающая то, что в реальности стоит за target. Такие случаи по-прежнему встречаются в продакшене, и обычно это линейные модели. Линейные модели привлекают своей простотой и наличием математических теорем, обосновывающих и описывающих их предиктивные способности. Но можно с уверенностью сказать, что если вы решите с помощью линейных моделей прогнозировать курс валют, погоду, вероятность покупки или вероятность возврата кредита, то вы получите слабую модель – under-fitted weak model.
too early stopping: обычно процессы обучения моделей итеративны, и если проделать слишком мало итераций, то получается недообученная модель;

Data leakage

Data leakage – это когда вы во время обучения использовали то, что есть в тестовом пуле или данные, которые недоступны или отличаются от тех, что будут доступны на практике при применении модели в жизни. Модели, которые сумеют воспользоваться этой утечкой, будут иметь неоправданно низкую ошибку на тестовом пуле и выбраны для использования в жизни. Есть несколько видов data leakage:

утечка таргета в факторы: Если, в задаче с прогнозом температуры вы добавите фактор – средняя температура за K дней, и в эти K дней при обучении случайно попадёт в том числе и целевой день, на который нужно сделать прогноз, то вы получите испорченный или нерабочий прогнозатор. Могут быть более сложные утечки через факторы. В случае прогноза какого-то будущего события вы должны многократно убедиться, что при вычислении факторов для обучающего пула не используются данные, которые получены во время этого события или после.
простая утечка тестового пула: Иногда всё просто – в обучающий пул попадают строчки из тестового пула.
утечка через подбор гиперпараметров: Правило, что для обучения разрешено использовать только обучающий пул, обманчиво просто. Здесь можно легко обмануться. Типичный пример неявной утечки – это подбор гиперапараметров при обучении. У всякого алгоритма обучения есть гиперпараметры. Например, у градиентного спуска есть параметр "скорость обучения" и параметр, задающий критерий останова. Ещё вы к Loss-функции можете добавить регуляризационные компоненты $R_2=\lambda_2 \sum w_i^2$ и $R_1=\lambda_1 \sum |w_i|$ , и вот вам ещё два гиперапараметра $\lambda_1$ и $\lambda_2$ . Приставка "гипер" используется, чтобы отличать внутренние параметры модели (веса), от параметров влияющих на процесс обучения.
Итак, предположим, вы решили в цикле проверять разные гиперпараметры обучения и выбрать те гиперпараметры, на которых достигается минимум ошибки на тестовом пуле. Надо понимать, что здесь происходит утечка тестового пула в модель. "Засаду", которая здесь скрывается, легко понять, именно с точки зрения теории информации. Когда вы задаете вопрос, чему равна ошибка на тестовом пуле, вы получаете информацию о тестовом пуле. А когда вы, на основании этой информации, принимаете какие-то решение, влияющие в конечном итоге на веса вашей модели, то значит биты этой информации оказываются в весах модели.
Ещё можно проиллюстрировать концепцию утечки тестового пула доведя до абсурда понятие гиперапараметров. Ведь разница между весами (параметрами) и гиперпараметрами (параметрами процесса обучения) чисто формальная. Давайте веса модели, например коэффициенты многочлена 10 степени все назовоём гиперапараметрами, а процесса обучения у нас не будет (множество внутренних весов у нас будет пустым). И давайте запустим безумный цикл по перебору всех возможных комбинаций значений гиперпараметров (каждый параметр будем перебирать от -1000 до +1000 с шагом $10^{-6}$ ) и вычислению ошибки на тестовом пуле. Понятно, что через условные миллиард лет мы найдём такую комбинацию параметров, которая даёт очень маленькую ошибку на тестовом пуле и картинку выше мы сможем запостить снова, но уже с другой подписью:
Голубая линия – многочлен 10 степени, который смог в точности воспроизвести тестовый пул из 11 точек.
Этот прогнозатор будет хорошо себя показывать на тестовом пуле, а в жизни – плохо.
- На практике используются модели с тысячами или миллионами весов и описанные эффекты проявляются на пулах больших размеров, особенно при наличии утечки данных из будущего (см. ниже).
- Надо понимать, что утечка теста через подбор гиперпараметров так или иначе всегда происходит. Даже если вы сделали специальный валидационный пул для подбора гиперпараметров, а тестовый пул никак не использовали для подбора гиперпараметров, всё равно наступает момент вычисления метрики качества на тестовом пуле. А потом наступает момент, когда у вас есть несколько моделей, измеренных на тестовом пуле, и вы выбираете лучшую модель по метрике на тесте. Этот момент выбора также можно назвать утечкой, но не всегда нужно бояться этой утечки.
- Важное замечание про то, когда нужно боятся этой утечки. Если эффективная сложность модели (см. определение ниже) у вас сотни или больше бит, то можно не боятся утечки такого сорта и не выделять специальный пул для подбора гиперпараметров – логарифм числа выстрелов для подбора гиперпараметров должен быть заметно меньше сложности модели.
утечка данных из будущего: например, когда вы обучаете прогнозаторы вероятности клика на рекламное объявление, то в идеале обучающий пул должен содержать данные, доступные исключительно на даты меньше даты X, где X – минимальная дата событий в тестовом пуле. Иначе возможны хитрые утечки типа следующей. Пусть мы взяли множества событий показы рекламы размеченной target = 1 для кликнутых событий показа, и target = 0 для некликнутой. И пусть мы разбили множество событий на тестовый и обучающий пул не по границе даты X, а случайным образом, например, в пропорции 50:50. Известно, что пользователи любят кликать сразу на несколько объявлений одной тематики подряд в течение нескольких минут, отбирая нужный товар или услугу. И тогда такие серии нескольких кликов будут случайно делиться на две части – одна пойдёт в обучающий, другая – в тестовый пул. Можно искусственным образом сделать модель с утечкой: возьмём самую хорошую правильную модель без утечки и дополнительно запомним факты "пользователь U кликал на тематику T" из обучающего лога. Затем при использовании модели будем совсем ненамного повышать вероятность клика для случаев (U, T) из этого множества. Это улучшит модель с точки зрения ошибки на тестовом пуле, но ухудшит её с точки применения на практике на новых данных. Мы описали искусственную модель, но несложно представить естественный механизм такого запоминания пар (U, T) и завышения вероятности для них в нейросетях и других популярных алгоритмах ML. Наличие таких утечек из будущего усугубляет проблему утечки через гиперпараметры. На таком тестовом пуле с утечкой будут выигрывать модели перекрученные в сторону запоминания данных. Более общим образом эту проблему можно описать так: модель может переобучиться под test set, если MI между примером в train set и примером в test set больше, чем между примером в train set и реальным примером при использовании модели в жизни.

Задачи

Задача 3.1. Пусть реальность такова, что $target = w_0 + w_1\cdot f + w_2\cdot f^2+ \nu,$ где $\nu$ – случайное число из $\mathcal{N}(0,\alpha^2),$ $\alpha=0.2.$ Фактор сэмплируется из $\mathcal{N}(0,1).$ Сколько в среднем нужно обучающих данных, чтобы, имея соответствующую реальности модель, получить оценки весов равные истинным с точностью до среднеквадратичной ошибки $\varepsilon=0.01$ ? Считайте, что априорное распределение весов – это нормальное распределение $\mathcal{N}(0,\sigma^2).$ Запишите ответ как функцию от $\alpha$ , $\varepsilon$ , $\sigma.$ Как ошибка прогноза зависит от размера обучающего лога?

Ответ

Есть такой способ получения ответа "от физиков". Пусть размер обучающего лога равен . Из задачи 1.16 мы имеем интуицию, что $\varepsilon = c / \sqrt{n}$ . Константа в этой задаче является функцией от $\alpha$ и $\sigma$ . Но есть ли зависимость от $\sigma?$ На самом деле нет. Действительно, шум $\alpha\cdot \nu$ как бы стирает цифры в десятичной записи значения , начиная с какого-то места после десятичной точки. При увеличении $\sigma$ остается больше значащих цифр и ровно настолько больше значащих цифр мы узнаем про коэффициенты $\{w_0, w_1, w_2\}.$ И тем самым при увеличении $\sigma$ позиция в десятичной записи $\{w_0, w_1, w_2\}$ , начиная с которой есть неопределённость остается той же. Из того, что $\sigma$ не участвует в формуле и из соображений размерности, формула должна выглядеть так

$\varepsilon =c_0 \cdot {\alpha \over \sqrt{n}}$

Где константа вычисляется эмпирически равна примерно 0.9. Соответственно получаем ответ $n = 0.8\cdot \left({\alpha \over \varepsilon} \right)^2$ .

Ошибка самого значения равна

$mse=\sqrt{\varepsilon^2 + \alpha^2}=\alpha \cdot \sqrt{1+0.8/n}$

Это следствие того, что при сложении двух независимых случайных величин $w'_0 + w'_1\cdot f + w'_2\cdot f^2$ и $\nu$ дисперсии складываются. Они должны быть независимы при правильном прогнозе, потому то если они зависимы, то модель можно улучшить, сделав некую калибровку прогноза.

Таким образом, в этой задаче прогноза и многих практических задачах есть неустранимая ошибка $\alpha$ . Она определяет две вещи:
(1) то, какую ошибку вы получите для случая очень большого обучающего пула (при $n\to \infty$ имеем $mse=\alpha \sqrt{1 + \beta /n}\to \alpha$ )
(2) а также размер пула, необходимый для достижения какой-либо заданной ошибки внутренних параметров, квадратично зависит от этой неустранимой ошибки: $n=\beta \cdot (\alpha/\varepsilon)^2$

Неустранимая ошибка $\alpha$ определяется количеством информации в сигнале, которая в принципе отсутствует в ваших факторах. Размер обучающего лога, необходимый для получения модели определённой точности mse, квадратично зависит от этой ошибки:

$n={\beta \over (mse/\alpha)^2 -1 }\approx \beta \cdot (\alpha / mse)^2 \; \;\mathrm{при\;маленьких} \; \alpha/mse$

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

К тому же факторы часто зависимы и сами по себе содержат в себе шумную компоненту. Контроль пользы от новых факторов и отбор факторов (feature selection) – это отдельная сложная тема для разговора.

Задача 3.2. Пусть реальность такова, что target есть многочлен 2-й степени от 10 факторов, при этом коэффициенты в многочлене – это числа разово сэмплированные из $\mathcal{N}(0,1),$ а факторы – независимые случайные числа из $\mathcal{N}(0,1)$ . Сколько нужно данных в обучающем логе, чтобы получить приемлемое качество прогноза, когда все факторы лежат на отрезке [-1, 1], для случая, когда модель верна, то есть является многочленом 2-й степени?
А если модель есть многочлен 3-й степени?

Задача 3.3. Постройте модель пользователей, которые в каждый момент времени склонны больше кликать на объявления какой-то одной тематики, заинтересовавшей их в данный момент, и убедитесь, что деление пула на обучающий и тестовый пул не по времени, а случайно, приводит к утечке данных из будущего.
Можно взять, например, такую модель. У каждого пользователя есть 10 любимых тематик, мы их знаем и храним в профиле пользователя. Пользовательская активность разделена на сессии, каждая сессия длится 5 минут, и во время сессии каждый пользователь видит ровно 10 объявлений по одной из его 10 тематик, тематика из любимых выбирается случайно. В каждую сессию пользователь интересуется одной из этих 10 тематик особенно сильно, и нет никаких факторов, позволяющих угадать, какой именно. Вероятность клика для такой "горячей" тематики в 2 раза больше, чем обычно. Для каждого пользователя по истории его кликов мы хорошо знаем вероятности клика для его 10 тематик, и пусть, если их упорядочить по интересности для конкретного пользователя, вектор этих вероятностей равен {0.10, 0.11, 0.12, ..., 0.19} .
Идентификатор пользователя и номер категории и есть доступные нам факторы. Насколько можно увеличить правдоподобие прогноза вероятности на тестовом пуле, если предположить, что каждая сессия разделилась ровно пополам между тестовым и обучающим пулами (5 событий пошли в один пул и 5 – во второй), и статистику по 5 событиям из обучающего пула можно использовать для прогноза вероятности клика на 5 других?
Предлагается экспериментально получить overfitting из-за утечки данных из будущего , используя какую-либо программу для ML, например, CatBoost.

Определение 3.1. Имплементационная $\varepsilon$ -сложность функции ( $\varepsilon$ -ИС) – это то, сколько бит информации о функции нужно передать от одного программиста другому, чтобы тот смог её воспроизвести со среднеквадратичной ошибкой не более, чем $\varepsilon$ . Два программиста предварительно договариваются о параметрическом семействе функций и априорном распределении параметров (весов) этого семейства.
Эффективная сложность модели – это минимальная имплементационная сложность функции среди всех возможных функций, которые дают такое же качество прогноза такое, что и данная модель.

Задача 3.4. Какая средняя $\varepsilon$ -ИС функции вида

$p(f_1,\ldots,f_n)=\sum_{i=1}^n w_i\cdot f_i$

от n факторов, в которой веса сэмплированы из распределения $\mathcal{N}(0,\sigma^2)$ , а факторы сэмплируются из $\mathcal{N}(0,1)$ .

Ответ

При фиксированных факторах погрешность функции определяется погрешностями весов по формуле

$\delta p^2 = \sum_i \delta w_i ^2 f_i^2$

В среднем по всем возможным значениям факторов получаем $\delta p^2 = {\sum}_i \delta w_i ^2$ . Если мы хотим $\delta p^2 \le \varepsilon^2$ , то веса нужно передавать с точностью $\delta w_i \le \varepsilon^2 /n$ .

Таким образом, согласно ответу в задаче 1.9, в среднем нужно будет передать $n\cdot \log(\sqrt{n}\cdot \sigma/\varepsilon)$ бит. Здесь видно важное свойство очень сложных моделей – для определения сложности сложной модели не так важно какое и насколько хорошее у вас априорное знание о весах, и не так важно, какая вам требуется точность или какая точность по факту достигается. Основная компонента в ИС модели это $0.5 \cdot n\cdot \log n$ , где n – некое эффективное количество весов, равноправно и с пользой участвующих в модели.

Задача 3.5. Функция t(id) задаётся таблицей как функция от одного фактора – id категории. Есть N = 1 млн. категорий, их доли в данных различны, и можно считать, что их доли получены сэмплированием 1 млн. чисел из экспоненциального распределения с последующей нормализацией, чтобы сумма долей была 1 (такое сэмплирование соответствует разовому сэмплированию из распределения Дирихле с параметрами {1,1,...,1} – 1 млн. единичек). Значения функции t для этих категорий сэмплированы из бета-распределения $B(\alpha, \beta),$ $\alpha=2,\;\beta=10$ независимо от их доли.
Какова средняя $\varepsilon$ -ИС таких функции?

Ответ

Во-первых, давайте опишем поведение этой функции в районе очень маленьких $\varepsilon$ . Когда $\varepsilon \ll 1/10^6$ , мы вынуждены хранить табличную функцию – 1 млн. значений. Можно численно или по формуле из википедии почитать энтропию бета-распределения $B(\alpha, \beta)$ . Далее можно положить, что мы хотим передать другому программисту, что значение t для какой-то конкретной категории i лежит в районе некоторого фиксированного значения с разрешённой погрешностью $\varepsilon$ . Это все равно что сузить "колпак" распределения $B(\alpha, \beta)$ до, скажем, нормального распределения $\mathcal{N}(t_i, \varepsilon^2).$ Разница энтропий $B(\alpha, \beta)$ и $\mathcal{N}(t_i, \varepsilon^2)$ равна примерно $-2.38 -\log \varepsilon$ . Это надо сделать для 1 миллиона категорий, поэтому для очень маленьких $\varepsilon$ ответ $N\cdot (-2.38 + \log 1/\varepsilon)$ .

Для больших $\varepsilon$ (но всё ещё заметно меньше 1) работает другая стратегия. Давайте разобьем промежуток [0,1] на одинаковые отрезки длины $\delta$ , и будем для каждой категории передавать номер отрезка, в который попало значение функции для этой категория. Эта информация имеет объём $N\cdot (H_{B(2,10)}+ \log(1/\delta))$ (см. задачу 1.7). В результате в каждом ответе наша ошибка будет ограничена длиной отрезка, в который мы попали. Если ответом считать середину отрезка и предполагать равномерность распределения (что допустимо, когда отрезки маленькие), то ошибка в рамках отрезка длины $\delta$ равна $\delta/\sqrt{12}$ . Таким образом, чтобы получить заданную среднюю ошибку $\varepsilon$ , нужно брать отрезки длиной $\delta=\sqrt{12}\cdot \varepsilon$ . Итого ответ равен $N\cdot (-2.20487 + \log 1/\varepsilon)$ .

Оба подхода дают ответ вида $N\cdot (c + \log 1/\varepsilon)$ . Идея использования фильтра Блюма для хранения множеств категорий для каждого отрезка даёт тот же результат.

Задача 3.6. Пусть в предыдущей задаче смысл функции – вероятность клика на рекламное объявление. Перенумеруем все категории в порядке убывания их истинной доли и обозначим порядковый номер как order_id, а исходный случайный идентификатор как id. Предлагается рассмотреть разные варианты ML с огрублением номера (идентификатора) категории до натурального числа от 1 до 1000. Это ограничение может быть связано, например, с тем, что вы хотите хранить статистику по историческим данным, и у вас есть возможность хранить только 1000 пар (показы, клики). Варианты огрубления идентификатора категории:
(a) огрубленный идентификатор равный id' = id // 1000 (целочисленное деление на 1000);
(b) огрубленный идентификатор равный id' = order_id для топовых 999 категорий по доле, а всем остальным назначить идентификатор 1000;
(с) какой-то другой способ огрубления id' = G(id), где G – детерминированная функция, которую вы можете сконструировать на базе статистики кликов на 100 млн показов, где каждый показ имеет какую-то категорию с вероятностью ровной доле категорий, а клик происходит согласно вероятности клика для этой категории.
Оцените значение ошибки error в этих трёх вариантах, где а $LL=-{\sum}_{i=1}^n t_i \log(p_i) + (1-t_i)\log(1-p_i)$ , а – это значение для идеального прогноза .

Задача 3.7. Пусть реальность такова, что $target ={\sum}_{i=1}^{45} w_i\cdot f_i +0.02 \cdot \nu$ , где $\nu$ – это шум, случайное число из $\mathcal{N}(0,1)$ . А ваша модель $predict = {\sum}_{i=1}^{50} w_i\cdot f_i +0.02 \cdot \nu,$
где веса $w_1,w_2, \ldots,w_{70}$ вам неизвестны и имеют априорное распределение лапласа со средним 0 и дисперсией 1. Последние 5 факторов модели по факту бесполезны для прогноза. Какого размера должен быть обучающий пул, чтобы получить среднеквадратическую ошибку прогноза

$mse={\sum}_{i=1}^n(predict_i - target_i)^2 / n \le 0.04^2$ .

Сгенерируйте три пула №1, №2, №3 c размерами 50, 50, 100000 и узнайте как лучше действовать – (а), (б) или (в):
(а) соединить два пула в один и на основании объединённого пула найти наилучшие веса, минимизирующие на этом пуле
(б) для различных пар $(\lambda_1, \lambda_2)$ , найти наилучшие веса, минимизирующие $mse + \lambda_1 \sum |w_i| + \lambda_2 \cdot \sum w_i^2$ на пуле №1; из всех пар выбрать такую пару $\lambda_1$ , $\lambda_2$ , на которых достигается минимум на пуле №2; пары $(\lambda_1, \lambda_2)$ предлагается взять из множества $A \times B,$ где и геометрические прогрессии с отдо 1. Нарисуйте график ошибки как функцию от $\lambda_1$ , положив $\lambda_2 = 0$ .
(в) соединить два пула в один и на основании объединённого пула найти наилучшие веса, минимизирующие $mse + \lambda_1 \sum |w_i| + \lambda_2 \cdot \sum w_i^2$ на этом пуле; значения $\lambda_1$ , $\lambda_2$ взять из пункт (б).
Метод тем лучше, чем меньше ошибка на пуле №3, который соответствует применению модели в реальности. Стабилен ли победитель, когда вы генерируете новые пулы? Нарисуйте таблицу 3x3 mse ошибок на трёх пулах в этих трёх методах.
Как падает ошибка на пуле №3 с ростом размеров пулов №1 и №2?

Задача 3.8. Пусть реальность такова, что $target =l_1(\vec{f})+ l_2(\vec{f}) +l_3(\vec{f})+\nu$ , где

$\nu$ – это шум, случайное число из $\mathcal{N}(0,\delta^2)$ , $\delta=0.02$ .
факторы $\vec{f}=\|f_1,\ldots,f_{m}\|^t$ – независимые случайные величины с равномерным распределением на отрезке , .
$l_1(\vec{f})=w_0+\sum w_{i}\cdot f_i$ – это линейная функция с коэффициентами из $\mathcal{N}(0,1)$ .
$l_2(\vec{f})={1 \over 2}\sum w_{ij}\cdot f_i\cdot f_j$ – это квадратичная однородная функция, в которой большая часть коэффициентов $w_{ij}$ равна нулю, кроме случайных , которые были сгенерированы из из $\mathcal{N}(0,1)$ .
$l_3(\vec{f})={1 \over 6}\sum w_{ijk}\cdot f_i\cdot f_j\cdot f_j$ – это кубическая однородная функция, в которой большая часть коэффициентов $w_{ijk}$ равна нулю, кроме случайных которые были сгенерированы из из $\mathcal{N}(0,1)$ .

Какая будет mse ошибка прогноза в среднем на достаточно больших тестовых и обучающих пулах по различным вариантам функции $target(\vec{f})$ (то есть для различных вариантов сэмплирования коэффициентов $w_i, \; w_{ij},\; w_{ijk}$ ) для случая, когда ваша модель есть

(а0) $\mathcal{P}(\vec{f})=l_1(\vec{f})$ с истинными значениями коэффициентов.
(б0) $\mathcal{P}(\vec{f})=l_1(\vec{f})+l_2(\vec{f})$ с истинными значениями коэффициентов.
(в0) $\mathcal{P}(\vec{f})=l_1(\vec{f})+l_2(\vec{f})+l_3(\vec{f})$ с истинными значениями коэффициентов.
(а1) $\mathcal{P}(\vec{f})=l_1(\vec{f})$ с обучением (то есть с коэффициентами, полученными регрессией).
(б1) $\mathcal{P}(\vec{f})=l_1(\vec{f})+l_2(\vec{f})$ с обучением, без знания, какие коэффициенты равны 0.
(в1) $\mathcal{P}(\vec{f})=l_1(\vec{f})+l_2(\vec{f})+l_3(\vec{f})$ с обучением, без знания, какие коэффициенты равны 0.
(в2) $\mathcal{P}(\vec{f})=l_1(\vec{f})+l_2(\vec{f})+l_3(\vec{f})$ с обучением и знанием, какие именно коэффициенты равны 0.
(г1) $\mathcal{P}(\vec{f})$ нейросеть глубины d = 5, размер внутренних слоёв h=5 (внутренние матрицы имеют размер h x h).

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

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

Пронаблюдайте явление переобучения в этих моделях (кроме первых двух), уменьшив размер обучающего пула до некоторого значения. Для каждой модели это будет свой размер. Попробуйте избавится от явления переобучения
1) добавляя к Loss-функции регуляризационные члены $R_1=\lambda_1\cdot \sum |w|,$ $R_2=\lambda_2 \cdot \sum w^2$ ;
2) используя early stopping;
3) используя SGD;
4) меняя архитектуру нейросети;
5) добавляя Dropout;
6) комбинацию перечисленных методов.

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

Задача 3.9. Пусть реальность такова, что

$target =w_0+\sum_{i=1}^{m} w_i\cdot f_i+\nu,$

где

веса разово сэмплированы из $\mathcal{N}(0,\sigma^2)$ ;
$\nu$ – это шум, случайное число из $\mathcal{N}(0,\delta^2)$ , $\delta=0.5$ .
величины $f_1,\ldots,f_{m}$ – независимые случайные величины с нормальным распределением $\mathcal{N}(0,1)$ .

Как зависит ошибка определения весов от размера обучающего лога и $m, \; \delta?$

Ответ

В первом приближении ответ равен

$mse(w_i) = {\delta \over \sqrt{n}}.\;\;\;\;\;(1)$

И это хорошее приближение для случая $n \gg m$ ( заметно больше ).

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

Средний квадрат ошибки весов, нормированный на δ^2 для m=50. Ось X нормирована на m, то есть X=1 соответствует n = m. Красная линия соответствует функции 1/n.

Если у кого-то есть хороший ответ про аналитическое приближение в окрестности n ~ m, пишите в личку.

Задача 3.10. Пусть реальность такова, что

$target =\sum_{i=1}^{11} w_i\cdot g_i+\nu,$

где

веса разово сэмплированы из $\mathcal{N}(0,1)$ ;
$\nu$ – это шум, случайное число из $\mathcal{N}(0,\delta^2)$ , $\delta=0.5$ .
величины $g_1,\ldots,g_{m}$ – независимые случайные величины с нормальным распределением $\mathcal{N}(0,1)$ ;
вам даны факторы с шумом: $f_i = g_i + \zeta_i$ , где случайный шум $\zeta_i$ в каждом примере сэмплируется из распределения $\mathcal{N}(0, z_i^2)$ (это записывается как $\zeta_i\sim\mathcal{N}(0,z_i^2)),$ где размеры шумов известны и равны $z_i=0.01 \cdot 2^i$ .

Как будет выглядеть наилучший прогноз, если вам известны точные значения весов
Как лучше всего реализовать обучение в этой задаче (когда веса неизвестны и их надо "обучить")?

Ответ

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

$target = F_0 + w_1\cdot g_1 + \nu_1,\; \\ \nu_1 \sim \mathcal{N}(0, \delta_1^2), \; g_1\sim \mathcal{N}(0,1), \\ predict_0 = F_0, \\ f_1 = g_1 + \zeta_1, \; \; \zeta_1\sim \mathcal{N}(0,z_1^2)$

Можно ли уменьшить ошибку mse, взяв новый прогноз

$predict_1 = predict_0 + w_1\cdot f_1?$

Текущая ошибка равна дисперсии $D(target - predict_0) = w_1^2 + \delta_1^2.$ Ошибка нового прогноза будет равна $D(target - predict_1) = w_1^2 \cdot z_1^2+\delta_1^2,$ она меньше старой ошибки, если

Давайте построим последовательность улучшений прогноза

$predict_0 = 0,\\ predict_1 = predict_0 + t_1 \cdot w_1 \cdot f_1, \\ predict_2=predict_1 + t_2\cdot w_2\cdot f_2, \\ \ldots \\ predict_{m} = predict_{m-1} + t_{m}\cdot w_{m}\cdot f_{m}$

Числа равны 0 или 1 – это индикаторы того, берём мы фактор в линейный прогноз или нет. $D(target - predict_0) = \sigma_0^2 = w_1^2 + \delta_1^2$ , где

$\delta_1^2 = \sum_{i=2}^{m} w_i^2 + \delta^2$

Потом, если мы возьмём первый фактор, ошибка будет равна

$D(target - predict_1) =\sigma_1^2= w_1\cdot z_1^2 + \delta_1^2$

Логично брать новый фактор в линейный прогноз тогда, когда

В итоге ошибка конечного прогноза равна

$D(target - predict_{m}) = \sigma_m^2=\sum_{i=1}^m \min(1, z_i^2)\cdot w_i^2+\delta^2$

Итак в случае линейного прогноза и известных весов можно брать или не брать слагаемые, и логично быть слагаемые $w_i\cdot f_i$ с теми факторами в которых дисперсия шума меньше, чем дисперсия самого незашумлённого фактора . Но ведь кроме вариантов "брать" и "не брать" есть ещё вариант брать с другим, меньшим по модулю весом. Кроме того, модель прогноза не обязательно должна быть линейной. Правильное решение задачи выглядит сложнее, в действительности мы всегда можем извлечь пользу из фактора, если в нём есть новая информация, даже если он очень зашумлён.

Пусть у нас есть два несмещённых прогноза и и их ошибки равны

$\; mse_0 = D(target - predict_0) = \sigma_0^2,\\ mse_1=D(target - predict_1) = \sigma_1^2.$

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

$predict_c = {m_0 \cdot predict_0 + m_1 \cdot predict_1 \over m_0 + m_1},\\ m_0 = 1/\sigma_0^2,\; m_1 = 1/\sigma_1^2.$

И погрешность этого прогноза была бы равна

$\sigma_c^2 = {1 \over 1/\sigma_0^2 + 1/\sigma_1^2}$

То есть $m_c = 1/\sigma_c^2 = m_0 + m_1.$

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

В нашем случае оценки зависимы, в ошибках

$target - predict_0 = -w_1\cdot g_1 + \nu_1, \\ target - predict_1= - w_1\cdot \zeta_i + \nu_1$

есть общая часть $\nu_1$ – общая неустранимая ошибка для этих двух прогнозов. При комбинировании мы как бы комбинируем только две независимые части $-w_1\cdot g_1$ и $-w_1 \cdot \zeta_1$ и получаем ответ

$predict_c= F_0 + {m_0\cdot 0 + m_1\cdot (w_1 \cdot f_i) \over m_0 + m_1}=\\=F_0 + {1\over m_0/m_1+1}\cdot w_1\cdot f_1$

где

$m_0 = 1/w_1^2,\; m_1= 1/(w_1^2\cdot z_1^2).$

Итого:

$predict_c = F_0 + {1 \over z_1^2+1}\cdot w_1\cdot f_1$

И ошибка у такого прогноза будет

$\sigma_c^2 = w_1^2 {z_1^2\over z_1^2 + 1} + \delta_1^2$

что меньше погрешностей $\sigma_0^2=w_1^2 + \delta_1^2$ и $\sigma_1^2=w_1\cdot z_1^2 + \delta_1^2$ обоих прогнозов и

Итоговая формула наилучшего линейного прогноза выглядит так

$predict = \sum_{i=1}^m {1\over z_i^2 + 1} \cdot w_i \cdot f_i$

А ошибка этого прогноза равна

$D(target - predict) = \sigma^2=\sum_{i=1}^m {z_i^2\over z_i^2+1} \cdot w_i^2+\delta^2$

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

Веса можно оценить по формуле

$w'_i= \mathrm{avg}(target \cdot f_i)/\mathrm{avg}(f_i^2)$

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

$M(target \cdot f_i) =\\= M((\ldots + w_i\cdot g_i)\cdot (g_i + \zeta_i)) =\\= M(w_i\cdot g_i^2) = w_i$

А средний квадрат фактора равен

$M((g_i + \zeta_i)^2) = M(g_i^2 + \zeta_i^2) = 1 + z_i^2$

Таким образом выражение $w'_i = \mathrm{avg}(target \cdot f_i)/\mathrm{avg}(f_i^2)$ в пределе равно , то есть в точности тому, что нужно подставить в формулу . Величина будет вычислена с погрешностью, то есть будет иметь отклонение от – из-за конечности обучающего пула (нормировка будет неидеальной, и средние величины по выборке будут отличаться от истинных мат. ожиданий). Пусть нам дана оценка среднего квадрата относительной погрешности:

$\epsilon_i=\left( { w'_i \over w_i / (1+z_i^2)}-1\right),\;\; d^2_i=M(\epsilon_i^2).$

Если мы не берём в прогноз слагаемое $w'_i\cdot f_i$ , то дополнительное слагаемое к квадрату ошибки (от потери истинного слагаемого $w_i\cdot g_i$ ) равно Если же мы вместо $w_i\cdot g_i$ берём $w'_i\cdot f_i$ , то дополнительное слагаемое к квадрату ошибки равно

$M((w'_i\cdot f_i - w_i\cdot g_i)^2) =\\=M\left(\left({w_i \over 1+z_i^2}\cdot (1 + \epsilon_i)\cdot(g_i + \zeta_i) - w_i\cdot g_i\right)^2\right) = \\ = w_i^2\cdot M\left(\left(\left({1 + \epsilon_i\over 1+z_i^2} - 1\right)\cdot g_i + \left({1 + \epsilon_i\over 1+z_i^2}\right)\cdot \zeta_i \right)^2 \right)$

Здесь мы просто

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

Если это выражение больше то фактор лучше отбросить. Выражение в итоге упрощается до

$w_i^2 \cdot\left({1 + d_i^2 \over (1 + z_i^2)^2} - {2 \over 1 + z_i^2}+1 + {1+d_i^2 \over (1+z_i^2)^2} z_i^2 \right) = \\ = w_i^2 \cdot\left({d_i^2 + z_i^2 \over 1 + z_i^2} \right)$

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

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

Квадратичная Loss-функция и Mutual Information

Обычно задача прогноза формулируется как задача минимизации ошибки:

ML-task №3.1: По данному обучающему пулу обучите модель $predict=\mathcal{P}(f_1, \ldots)$ , которая минимизирует среднюю ошибку . Качество прогноза будет измеряться по средней ошибке на скрытом тестовом пуле.

Но можно попробовать сформулировать задачу прогноза как задачу максимизации MI.

ML-task №3.2: По данному обучающему пулу обучите модель $\mathcal{P}(f_1, \ldots)$ такую, что

значение predict имеет максимально возможное значение взаимной информации с то есть $\mathrm{MI}(predict, target)\to \mathrm{max}$ ;
является несмещённым прогнозом , а именно, мат. ожидание невязки $\xi = predict - target$ равно 0 при условии для любого .

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

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

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

Подробнее

Детерминированная функция $\mathcal{P}(f_1, \ldots, f_k)$ интерпретируется как случайная величина следующим образом: мы сэмплируем строчку из тестового пула, берём из неё набор факторов $(f_1, \ldots, f_k)$ и , подставляем факторы в функцию и получаем значение и пару зависимых случайных величин .

Требование несмещённости следует воспринимать как несмещённость в среднем при рассмотрении обучающего и тестового пулов как случайных величин. То есть конкретный конечный обучающий пул однозначно даст модель со смещённым прогнозом – среднее значение разницы не будет равно нулю в среднем на случайном примере из потенциально бесконечного тестового пула. Но можно рассмотреть разницу , где среднее берётся по всевозможным моделям, которые можно было бы получить, обучаясь на гипотетических обучающих пулах и тестируя на гипотетических тестовых пулах. Другой вариант легализации несмещённости – это требование несмещённости в пределе, при стремлении размера обучающего пула в бесконечность. Такие интерпретации несмещённости дают шанс на существование решения задачи ML-task №3.2.2. Но честно говоря, ни инженеры, ни теоретики ML не уделяют вопросу смещённости большого внимания, как это обычно делается в методах мат. статистики. ML-щики это признают, и открыто предпочитают тестировать и оценивать свои методы на искусственных или реальных задачах по метрикам ошибки, не анализируя их смещённость.

Но мне требование несмещённости потребовалось, чтобы переформулировать задачу прогноза в терминах максимизации MI.

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

Определение 3.2: Loss-функцию равную мат. ожиданию квадратичной ошибки $M_{\xi^2}$ будем называть – ошибкой или квадратичной ошибкой или mse. А Loss-функцию $M_{|\xi|^p}$ будем называть – ошибкой.

Утверждение 3.1: Пусть ваша модель в задаче ML-task №3.2.2 или ML-task №3.2.1 такова, что невязка $\xi = predict - target$ обладает двумя свойствами:

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

Тогда задачи ML-task №3.1 и ML-task №3.2 эквивалентны для Loss=mse, то есть задача "maximize MI" даёт тот же ответ, что и задача "minimize mse-ошибку".

Конечно, описанные в утверждении свойства редко встречаются на практике, но тем не менее, этот факт интересен.
Во-первых, эти свойства достижимы тогда, когда вектор из факторов и -а $(f_1, f_2, \ldots, f_n, target)$ является измерением многомерной нормальной величины, а именно, так и будет, если есть линейная комбинация нескольких независимых гауссовских величин, некоторые из которых нам известны и даны как факторы. Тогда прогноз естественно тоже искать как линейную комбинацию данных факторов.
В этом случае

$\mathrm{MI}(target, predict) = \log({\sigma_t^2 / \sigma_e^2})$ ,

где $\sigma_e^2$ и есть среднее значение квадратичной ошибки прогноза, то есть $M_{\xi^2} = M_{{(target - predict)}^2}$ , а $\sigma_t^2$ — дисперсия -а (см. задачу 2.8 про MI двух зависимых нормальных величин). Понятно, что в этом случае задача максимизации $\mathrm{MI}$ эквивалентна задаче минимизации $M_{\xi^2}=\sigma_e^2$

Надо понимать, что хотя чистый и не зависящий от гаусс для ошибки $\xi$ на практике не встречается, тем не менее, распределение при фиксированном часто выглядит как гауссовский "колокол" с центром в , и утверждение про эквивалентность тоже почти верно, а именно, задача максимизации MI эквивалентна задаче минимизации ошибки в -подобной метрике, где усреднение делается с весом, неким образом зависящим от .

Точнее так — если колокол распределения $\rho_\xi$ одномодальный, симметричный, с квадратичной вершинкой, то и найдётся и эквивалентная задача про максимизацию MI. Это мы обсудим ниже.

А сейчас попробуем доказать утверждение про эквивалентность задач "maximize MI" и "minimize L₂" для случая, описанного в утверждении 3.1.

Введём короткие обозначения t = target, p = predict.

Доказательство основано на том, что мы просто записываем значение $\mathrm{MI}$ в таком виде:

$\mathrm{MI}(p, t) = H(t) - \int H(t | p = x) \rho_{p}(x) dx$

Величина не зависит от прогноза и равна $C + 0.5\cdot \log(D(t)).$ Величина равна $C + 0.5\cdot \log(D(t|p=x)),$ где как мы обозначили дисперсию прогнозируемой величины при заданном значении прогноза. Согласно второму условию утверждения она константа. В случае несмещённого прогноза это $M_{\xi^2}$ (то есть как раз квадратичная ошибка) при условии

Выражение $\int \ldots \rho_{p}(x) dx$ — суть просто усреднение по пулу.

Если $M_{\xi^2}$ не зависит от значения то мы получим нужное утверждение. Действительно,

$\mathrm{MI}(p, t) = С + 0.5\cdot \log(D(t)) - \int (C + 0.5 \log(\mathrm{mse})) \rho_{p}(x) dx = \\ = 0.5 \cdot \log(D(t) / \mathrm{mse})$

Максимизация этого выражения равносильна минимизации mse. Конец доказательства.

Для большего понимания распишем более подробно выражение

$\mathrm{MI}(p, t) =\\= H(t) - \int H(t | p = x) \rho_{p}(x) dx =\\= H(t) - \int \rho_{t}(y | p = x) \log(1/\rho_{t}(y | p = x)) \rho_{p}(x) dx dy =\\ = H(t) - \int \log(1/\rho_{t}(y | p = x)) \cdot \rho_{t,p}(x, y) dx dy$

Интегрирование

$\int \ldots (\rho_{t,p}(x, y) dx dy$

снова соответствует просто усреднению по пулу, а выражение $\log(1/\rho_{t}(y | p = x))$ и есть то, что нужно интерпретировать как значение ошибки. Если перейти к дискретизированному случаю, и вспомнить про кодирование Хаффмана, то $\log(1/P(t= y | p = x))$ есть количество бит, которое требуется для записи кода значения (с точностью до $\varepsilon$ ) при условии, что известно значение . Если прогноз не смещен, и он нам дан, то, чтобы закодировать с некоторой заданной точностью, проще записать код для невязки $\xi=t- p$ , которая есть случайная величина с нулевым средним и меньшим значением дисперсии, нежели дисперсия . Эти рассуждения наводят ещё на одну формулировку задачи прогноза как задачи максимизации MI:

ML-task №3.3: По данному обучающему пулу обучите модель $predict(f_1, \ldots, f_k)$ такую, чтобы задача кодирования невязки с точностью до $\varepsilon$ требовала минимального количества бит.

В этой задаче имеется в виду наивное кодирование чисел, когда записываются все значащие цифры. Например, пусть фиксирована точность $\varepsilon = 0.000001$ , тогда число $-0.000123456789\pm 0.000001$ логично кодировать как "-123". Здесь мы тратим один бит на знак (+ или - в начале), далее нас не интересуют все цифры начиная с седьмого места после десятичной точки, и мы записываем только значащие цифры, не перечисляя лидирующие нули, и мы понимаем, что последняя цифра в коде стоит на шестом места после десятичной точки. В таком кодировании чем меньше ошибка в среднем, тем меньше бит потребуется для кодирования всех ошибок на тестовом пуле. Значение $\varepsilon$ должно быть достаточно мало. Но поверх этого наивного кодирования важно применить ещё кодирование Хаффмана, чтобы различие в вероятностях разных ошибок позволило дополнительно сжать данные.

В этой формулировке мы как бы невольны назначать свою Loss-функцию. Некоторые склонны рассматривать это как критерий правильного выбора Loss-функции: если вы минимизируйте mse, то хорошо, когда $\log(1/P(t= y | p = x))$ с ростом обучающего и тестового пулов стремится к $A \cdot (y - x)^2 + B$ , то есть распределение невязки близко к нормальному, а когда вы минимизируйте L₁- ошибку, то хорошо, если $\log(1/P(t= y | p = x))$ стремится к $A\cdot |y - x| + B$ , то есть распределение невязки близко к распределению Лапласа. В общем случае ожидается приближённое равенство $P(t = y| p=x) \approx e^{-A \cdot Loss(y,x) + B}$ и если это не так, то либо вы "недоделали ML", либо ваша задача не относится к классу хороших.

Видимо, при определённых условиях, верны рассуждения и в другую сторону. Если у вас есть идеальное решение задачи ML-task №3.3, то изучив распределение невязки для её решения, вы узнаёте какую Loss-функцию нужно использовать, чтобы извлечь максимум информации о сигнале.

Log-Likelihood и Mutual Information

Пример задачи из жизни: Реализуйте детерминированную функцию
$\mathcal{P}(пол, возраст, последние\ 10\ поисковых\ запросов, \ldots)$
прогнозирующую вероятность p того, что пользователь кликнет на данное рекламное объявление.

Задачи такого типа, когда нужно спрогнозировать булеву величину (величину, принимающую значения "Да" или "Нет"), называются задачами бинарной классификации (Binary Classification Problems).
Для их решения обычно используется метод максимизации правдоподобия, а именно, предполагается, что прогноз должен возвращать вещественное число от 0 до 1, соответствующее вероятности того, что (пользователь кликнет на рекламу). При обучении прогнозатора на обучающем множестве можно подбирать такие значения внутренних параметров модели (aka весов), на которых достигается максимальная вероятность видеть то, что находится в обучающем множестве.

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

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

Вероятность видеть то, что мы видим в пуле, в применении к модели называется правдоподобием модели (model likelihood). То есть мы говорим 'вероятность события' и 'правдоподобие модели', но не говорим 'вероятность модели' или 'правдоподобие событий'.

Вот пример тестового пула из трёх строчек:

i	f₁	f₁	f₁	target	predict= P(target=1)	P(target=0)
1	...	...	...	0
2	...	...	...	1
3	...	...	...	0
			$\mathrm{Likelihood}=(1-p_1)\cdot p_2\cdot(1-p_3)$

Удобнее оперировать значением LogLikelihood:

$\mathrm{LogLikelihood} = \log((1 - p_1)\cdot p_2\cdot (1 - p_3)) = \log(1 - p_1) + \log (p_2) + \log(1 - p_3)$

Строчки с входят в суммарный LogLikelihood как $\log(predict)$ , а строчки с — как $\log(1 - predict)$ .

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

ML-task №3.4: Дан обучающий лог. Найдите детерминированную функцию $predict(f_1,f_2,\ldots),$ чтобы значение $\mathrm{LogLikelihood}(predict, target)$ на тестовом пуле было максимально.

Сформулируем аналогичную задачу в терминах максимизации MI.

ML-task №3.5: Найдите детерминированную функцию $p=predict(f_1,f_2,\ldots),$ чтобы случайная дискретная величина $\xi$ принимающая значения 0 и 1 с вероятностями $\{p,\; 1 - p\},$ имела максимально возможное значение взаимной информации $\mathrm{MI}(\xi, target)$ с величиной .

Утверждение 3.2: Если ваша модель такова, что $\xi = predict - target$ является случайной величиной с нулевым средним (то есть прогноз не смещён), тогда задачи ML-task №3.2.2 и ML-task №3.2.1 эквивалентны, то есть задача "maximize MI(target, predict)" даёт тот же ответ, что и задача "maximize LogLikilihood".

То, что прогноз не смещён или, другими словами, не требует калибровки не является сложным требованием. В задачах классификации, если вы используете Gradient Boosted Trees или нейросети с правильными гиперпараметрами (скорость обучения, число итераций) прогноз получается несмещённым. А именно, если вы берёте события с $predict \in [x - \varepsilon, x + \varepsilon],$ то получаете множество событий с

$p_{fact} = { \mathrm{number\_of\_lines\_with\_target\_1} \over \mathrm{number\_of\_lines}} = {\mathrm{clicks} \over \mathrm{impressions}}\approx x$

В задачах классификации строчки, у которых target = 1 мне привычно называть кликами (clicks), а строчки с target = 0 – некликами (notclicks). Клики + неклики дают множество всех событий, которые называются показами (impressions). Фактическое отношение кликов к показам называется CTR — Click Through Rate.

Чтобы доказать утверждение 3.2, давайте воспользуемся решением задачи:

Задача 3.10. Как по N измерениям двух случайных величин — дискретной величины $\xi$ , принимающей значения от 1 до M, и булевой случайной величины $\mu,$ оценить значение $\mathrm{MI}(\xi,\; \mu)$ ?

Можно думать про эту задачу так: $\xi$ — это некоторая категориальная величина про рекламное объявление, её значения интерпретировать как идентификатор класса, а $\mu = \mathrm{IsClick}$ — это индикатор того, был ли клик. Данные про измерение пар $(\xi, \mu)$ — это просто лог кликов и некликов.

Для решения этой задачи удобно воспользоваться формулой

$\mathrm{MI}(\xi,\mu) = H(\mu) - H(\mu | \xi)=H(\mu)-{\sum}_i P(\xi=i)\cdot H(\mu|\xi=i)$

Значение $H(\mu)=H(\mathrm{ctr}_{0})$ , где $\mathrm{ctr}_{0} = \mathrm{ctr}_{total} = \mathrm{clicks}_{total} / \mathrm{impressions}_{total}$ — средний CTR по всему логу.

Значение $H(\mu | \xi = i) = H(\mathrm{ctr}_i)$ , где $\mathrm{ctr}_{i} = \mathrm{clicks}_{i} / \mathrm{impressions}_{i}$ — CTR по событиям, в которых $\xi = i$ , что естественно называть CTR в классе i. Подставляем это в формулу и получаем:

.

$\mathrm{MI}(\mu, \xi) = H(\mu) - H(\mu | \xi) = \\ = H(\mathrm{ctr}_{0}) - \displaystyle\sum_{i\in classes} { \mathrm{impressions}_i \over \mathrm{impressions}_{total} } \cdot H(\mathrm{ctr}_i) = \\ = - (\mathrm{ctr}_{0}\cdot \log(\mathrm{ctr}_{0}) + (1 - \mathrm{ctr}_{0})\cdot \log(1 - \mathrm{ctr}_{0})) +\\ + \displaystyle\sum_{i\in classes} {\mathrm{impressions}_i \over \mathrm{impressions}_{total}} \cdot ( \mathrm{ctr}_{i}\cdot \log(\mathrm{ctr}_{i}) + (1 - \mathrm{ctr}_{i})\cdot \log(1 - \mathrm{ctr}_{i}))$

Давайте займёмся первым слагаемым и запишем его в виде суммы по классам:

$H(\mu) = - \left(\displaystyle{\mathrm{clicks}_{total} \over \mathrm{impressions}_{total}} \log(\mathrm{ctr}_{0}) + \displaystyle{\mathrm{notclicks}_{total} \over \mathrm{impressions}_{total}}\cdot \log(1 - \mathrm{ctr}_{0})\right) = \\$ $= - \displaystyle\sum_{i \in classes}\left({\mathrm{clicks}_i \over \mathrm{impressions}_{total}} \log(\mathrm{ctr}_{0}) + {\mathrm{notclicks}_i \over \mathrm{impressions}_{total}}\cdot \log(1 - \mathrm{ctr}_{0})\right) =$ $- \displaystyle\sum_{i \in classes}\left({\mathrm{ctr}_i \cdot \mathrm{impressions}_i \over \mathrm{impressions}_{total}} \log(\mathrm{ctr}_{0}) + {(1 - \mathrm{ctr}_i)\cdot \mathrm{impressions}_i \over \mathrm{impressions}_{total}} \log(1 - \mathrm{ctr}_{0})\right).$

Подставив это в выражение для MI, и поместив обе части в одну сумму по классам, получим итоговое выражение для MI:

$\displaystyle\sum_{i \in classes} { \mathrm{impressions}_i \over \mathrm{impressions}_{total}} \cdot \left(\mathrm{ctr}_{i}\cdot \log\left({\mathrm{ctr}_{i} \over \mathrm{ctr}_{0}}\right) + (1 - \mathrm{ctr}_{i})\cdot \log\left({1 - \mathrm{ctr}_{i} \over 1 - \mathrm{ctr}_{0}}\right)\right) = \\ = \displaystyle{1 \over \mathrm{impressions}_{total}} \displaystyle\sum_{e \in \mathrm{impressions}} \mathrm{ctr}_{i(e)}\cdot \log{\left({\mathrm{ctr}_{i(e)} \over \mathrm{ctr}_{0}}\right)} + (1 - \mathrm{ctr}_{i(e)})\cdot \log{\left({1 - \mathrm{ctr}_{i(e)} \over 1 - \mathrm{ctr}_{0}}\right)}$

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

В случае, когда классы есть просто корзины прогноза, и прогноз не смещён, то есть средний прогноз в корзине совпадает с реальным $\mathrm{ctr}$ в корзине, имеем:

$\mathrm{LogLikelihood(predict)}=\\ = \sum_{e\in \mathrm{impressions}}\mathrm{ctr}_{i(e)}\cdot \log(\mathrm{ctr}_{i(e)}) + (1-\mathrm{ctr}_{i(e)})\cdot\log(1-\mathrm{ctr}_{i(e)})=\\=$

А если прогноз равен константе $\mathrm{ctr}_0$ , то выражение для правдоподобия равно

$\mathrm{LogLikelihood}(\mathrm{predict}=\mathrm{ctr}_0)=\\ = \sum_{e\in \mathrm{impressions}}\mathrm{ctr}_{0}\cdot \log(\mathrm{ctr}_{0}) + (1-\mathrm{ctr}_{0})\cdot\log(1-\mathrm{ctr}_{0})=\\= \sum_{e\in \mathrm{impressions}}\mathrm{ctr}_{i(e)}\cdot \log(\mathrm{ctr}_{0}) + (1-\mathrm{ctr}_{i(0)})\cdot\log(1-\mathrm{ctr}_{0})$

Замена $\mathrm{ctr}_0$ на $\mathrm{ctr}_{i(e)}$ валидна, так как выражения c логарифмами константны и среднее значение $\mathrm{ctr}_{i(e)}$ по всем impressions равно $\mathrm{ctr}_0$ .

B здесь мы видим, что итоговое выражение для MI есть просто нормированная разница двух выражений для LogLikelihood:

$\mathrm{MI}(\xi, \mu) = \ \mathrm{MI}(predict, \mu) =\\ \ {1 \over \mathrm{impressions}_{total}}\cdot (\mathrm{LogLikelihood}(predict) - \mathrm{LogLikelihood}(predict = \mathrm{ctr}_{0})$

То есть $\mathrm{MI}(predict, target)$ в случае несмещённого прогноза есть линейная функция от LogLikelihood.

Кстати, величина $\mathrm{LogLikelihood}(predict_1) - \mathrm{LogLikelihood}(predict_2)$ называется Log Likelihood Ratio двух прогнозаторов, и её естественно нормировать на количество событий (impressions). В качестве часто берут какой-нибудь простейший прогноз, в нашем случае, это константный прогноз. Часто имеет смысл мониторить график величины LogLikelihoodRatio / impressions, а не LogLikelihood / impressions, беря в качестве бейслайнового прогноза какой-либо робастный (простой, надёжный неломающийся) прогноз, основанный на небольшом числе факторов. Также иногда можно брать $\mathrm{LogLikelihoodRatio} / \mathrm{impressions} \cdot \mathrm{ctr}_0^{\gamma}$ , для некоторого $\gamma$ , чтобы устранить корреляцию или антикорреляцию с $\mathrm{ctr}_0$ и лучше видеть точки поломок прогноза.

Итак, для несмещённого прогноза величина MI между прогнозом и сигналом равна удельному (нормированному на число строк) Log Likelihood Ratio вашего прогноза и наилучшего константного прогноза.

Оценка Mutual Information = Machine Learning

Два утверждения — 3.1 и 3.2 — говорят о том, что Mutual Information является метрикой качества, которая в некоторых допущениях соответствует двум метрикам в задачах прогноза — квадратичной ошибке в задаче прогноза вещественной величины с нормальным распределением и LogLikelihood в задаче бинарной классификации.

Сама величина Mutual Information не может использоваться как Loss-функция, потому что она не является метрикой на данных, то есть не представляется как сумма значений Loss-функции по элементам пула. Смысл "соответствия" можно пояснить так: практически все Loss-функции в конечном итоге занимаются максимизацией Mutual Information predict-а и target-а, но с разными дополнительными добавками.

Возможно, свет на это прольют следующие два утверждения (опять без доказательства):

Утверждение 3.3: Если у вас есть прогноз на факторах $f_1,\ldots,f_k$ , и есть новый фактор $f_{k+1},$ такой что $\mathrm{MI}(\{f_{k+1}, predict\}, target) > \mathrm{MI}(predict, target),$ то при достаточно большом обучающем логе этот фактор уменьшит вашу Loss-функцию, если она нормальная. Loss-функция называется нормальной если она падает, когда вы в любом элементе пула значение predict приближаете к target. Квадратичная ошибка mse, -ошибка, LogLikelihood — это всё нормальные Loss-функции. Далее будем считать, что Loss-функция нормальная.

Произвольное монотонное преобразование прогноза будем называть калибровкой прогноза.

Утверждение 3.4 (требует уточнения условий): Если вы нашли такое изменение весов (ака внутренних параметров) вашей модели, которое увеличивает $\mathrm{MI}(predict, target),$ то после надлежащей калибровки прогноза вырастет и ваша Loss-функция.

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

Задача 3.11: Докажите, что для случая, когда $target=\mathcal{P}(f_1,f_2,\ldots,w_1,w_2,\ldots) + \nu$ , где $\nu$ случайный шум, и модель соответствует реальности, при увеличении обучающего лога веса стремятся к правильным значениям весов для обоих Loss-функций и. При этом в случае, если шум имеет симметричное распределение, обе Loss-функций дают несмещённый прогноз.

Задача 3.12: Приведите пример модели и реального target, когда Loss-функции и дают разные прогнозы даже на очень большом обучающем пуле, так что один нельзя перевести во второй никаким монотонным преобразованием (один прогноз нельзя получить калибровкой второго).

Утверждение 3.5: Задача оценки $mi = \mathrm{MI}(\{f_1,\ldots, f_k\}, target)$ эквивалентна задаче построения прогноза $predict=\mathcal{P}(f_1,\ldots, f_k)$ в какой-то Loss-функции.

Это утверждение говорит, что истинное значение mi примерно равно supremum $\mathrm{MI}(predict, target)$ всем парам (ML-метод, Loss-функция), где
ML-метод ::= ("структура модели", "метод получения весов модели"),
"метод получения весов модели" ::= ("алгоритм", "гиперпараметры алгоритма"),
а равенство тем точнее, чем больше обучающий пул.

Собственно та пара (ML-метод, Loss-функция), которая даст самое большое значение $\mathrm{MI}(predict, target)$ близкое к mi, и есть модель, самая близкая к реальности, то есть тому, как на самом деле связаны $f_1,\ldots,f_k$ и target.

Итак: Мы сформулировали две глубокие связи между задачами прогноза и MI:

Во-первых, максимизация MI в некотором смысле соответствует задаче минимизации какой-то Loss-функции
Во-вторых, "оценка MI" = "ML", а именно, задача оценки $\mathrm{MI}(\{f_1,\ldots, f_k\}, target)$ эквивалентна задаче построения прогноза $\mathcal{P}(f_1,\ldots, f_k)$ для какой-то Loss-функции. И собственно, ML-метод и Loss-функция, которые дают максимум $\mathrm{MI}(predict, target)$ и является наиболее правдоподобной моделью.

3. Теория информации и ML. Прогноз