notes/machine_learning/theory_of_machine_learning.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_машинного_обучения"
]
},
"source": [
"## Три фундаментальных источника ошибок в машинном обучении\n",
"\n",
"Оптимальный в байесовском смысле регрессор (или классификатор) — это то, что задаётся следующим формальным выражением:\n",
"$$f_{opt} = \\arg \\min_{f \\in F} \\int_{(x, y) \\sim P_{true}(x, y)}l(f(x), y),$$\n",
"где $F$ — множество всех возможных регрессоров (или классификаторов соответственно), $P_{true}$ — истинное совместное распределение признаков и целевой переменной, а $l$ — функция потерь, по значению регрессора (классификатора) на векторе признаков и целевой переменной на этом векторе признаков возвращающая соответствующий штраф.\n",
"\n",
"В реальности есть ограничения, не позволяющие найти $f_{opt}$.\n",
"\n",
"Во-первых, неизбежна ошибка приближения (approximation error): поиск проводится не по всему множеству возможных регрессоров (классификаторов), а лишь по какому-то подмножеству $\\overline{F} \\subset F$, например, по некому параметрическому семейству. Скажем, в случае с линейной регрессией $\\overline{F}$ — это множество всех линейных регрессоров. Как следствие, ищется уже нечто другое:\n",
"$$\\hat{f_1} = \\arg \\min_{f \\in \\overline{F}} \\int_{(x, y) \\sim P_{true}(x, y)}l(f(x), y).$$\n",
"Ошибка, вызываемая отличием $\\hat{f_1}$ от $f_{opt}$, и называется ошибкой приближения.\n",
"\n",
"Во-вторых, существует ошибка оценивания по данным (estimation error): невозможно получить истинную генеральную совокупность $P_{true}$, а вместо неё есть лишь выборка конечного размера $n$. С учётом такого ограничения задача принимает вид:\n",
"$$\\hat{f_2} = \\arg \\min_{f \\in \\overline{F}} \\frac{1}{n} \\sum_{i=1}^{n} l(f(x_i), y_i) + \\alpha R(f),$$\n",
"где $(x_i, y_i)$ — признаки и ответ на $i$-м объекте обучающей выборки, $R(f)$ — регуляризатор, а $\\alpha$ — коэффициент, задающий силу регуляризации. Ошибка оценивания — ошибка, вызываемая отличием $\\hat{f_2}$ от $\\hat{f_1}$.\n",
"\n",
"В-третьих, не всегда удаётся довести поиск минимума из предыдущего пункта до конца, и отсюда возникает ошибка оптимизации (optimization error). Если предположить, что вычислительные ресурсы ограничены и есть всего лишь $T$ итераций, то получится, что решается задача\n",
"$$\\hat{f_3}^{(T)} = \\arg \\min_{(T); f \\in \\overline{F}} \\frac{1}{n} \\sum_{i=1}^{n} l(f(x_i), y_i) + \\alpha R(f),$$\n",
"где запись $(T)$ под минимумом обозначает, что минимум ищется за ограниченное число шагов. По аналогии с определением предыдущих ошибок ошибка оптимизации — это ошибка, вызываемая отличием $\\hat{f_3}^{(T)}$ от $\\hat{f_2}$.\n",
"\n",
"Можно считать, что машинное обучение на больших данных отличается от машинного обучения на малых данных тем, что ошибка оптимизации начинает доминировать над ошибкой оценивания по данным.\n",
"\n",
"Подробности есть в статье [Bottou, Bousquet, 2007](https://papers.nips.cc/paper/3323-the-tradeoffs-of-large-scale-learning.pdf)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_машинного_обучения"
]
},
"source": [
"## Дилемма смещения и разброса\n",
"\n",
"#### Разложение на смещение, разброс и неустранимую ошибку\n",
"\n",
"Пусть есть совместное распределение вектора признаков какого-либо объекта и целевой переменной на этом объекте $p(x, y) = p(x) p(y \\vert x)$. Также пусть дана порождённая из этого распределения обучающая выборка $(X_{train}, y_{train})$, на которой обучена модель $\\hat{f}$. Для оценки $\\hat{f}$ можно выбрать метрику качества $\\mu$, по паре $(y, \\hat{y})$ возвращающую число, отражающее, насколько приемлемо отклонение предсказания $\\hat{y} = \\hat{f}(x)$ от истинного значения $y$. Но помимо модели $\\hat{f}$ можно оценить и метод машинного обучения, которым она была получена. Точнее, оценить не только сам метод, но и его спецификацию: выбранные значения гиперпараметров и/или ограничения на модель $\\hat{f}$. Такая оценка качества имеет вид:\n",
"$$\\mathbb{E}_{(x, y) \\sim p(x, y)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[ \\mu(y, \\hat{f}_{(X_{train}, y_{train})}(x)) \\right],$$\n",
"где запись $\\hat{f}_{(X_{train}, y_{train})}$ подчёркивает, что модель была обучена именно на выборке $(X_{train}, y_{train})$.\n",
"\n",
"Для наглядности перейдём к частному случаю задачи регрессии со среднеквадратической ошибкой в качестве метрики качества, т.е. $\\mu(y, \\hat{y}) = (y - \\hat{y})^2$. Тогда оценка качества для метода машинного обучения примет вид:\n",
"$$\\mathbb{E}_{(x, y) \\sim p(x, y)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[\\left(y - \\hat{f}_{(X_{train}, y_{train})}(x)\\right)^2\\right] = {\\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{y \\sim p(y \\vert x)} \\left[ y^2 \\right] - 2 \\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{y \\sim p(y \\vert x)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[y \\hat{f}_{(X_{train}, y_{train})}(x) \\right] + \\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[ \\hat{f}_{(X_{train}, y_{train})}(x)^2 \\right]}.$$\n",
"\n",
"Воспользовавшись формулой $\\mathbb{E}[z^2] = \\mathbb{E}[z]^2 + \\mathrm{Var}[z]$, первый член перепишем так:\n",
"$$\\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{y \\sim p(y \\vert x)} \\left[ y^2 \\right] = {\\mathbb{E}_{x \\sim p(x)} \\left[ \\left(\\mathbb{E}_{y \\sim p(y \\vert x)} [y \\vert x]\\right)^2 + \\mathbb{E}_{y \\sim p(y \\vert x)} \\left[\\left(y - \\mathbb{E}_{y \\sim p(y \\vert x)}[y \\vert x]\\right)^2\\right]\\right]}.$$\n",
"В правой части второе слагаемое интерпретируется как шум, неустранимая ошибка. Оно показывает дисперсию $y$ относительно своего условного среднего при заданном $x$ (в среднем по всем $x$).\n",
"\n",
"Так как во втором члене оба множителя условно независимы друг от друга при условии $x$, перепишем этот член так:\n",
"$$\\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{y \\sim p(y \\vert x)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[y \\hat{f}_{(X_{train}, y_{train})}(x) \\right] = {\\mathbb{E}_{x \\sim p(x)} \\left[\\left(\\mathbb{E}_{y \\sim p(y \\vert x)} [y \\vert x]\\right) \\left(\\mathbb{E}_{(X_{train}, y_{train})} \\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right]\\right)\\right]}.$$\n",
"Выражение $\\mathbb{E}_{(X_{train}, y_{train})}\\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right]$ имеет интерпретацию среднего предсказания на объекте с признаками $x$ с усреднением по всем возможным обучающим выборкам (и исходам случайности при обучении, если она есть — хотя краткости ради нигде выше зависимость обучения от случайности не была обозначена).\n",
"\n",
"Вновь воспользовавшись формулой $\\mathbb{E}[z^2] = \\mathbb{E}[z]^2 + \\mathrm{Var}[z]$, третий член перепишем так:\n",
"$$\\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[ \\hat{f}_{(X_{train}, y_{train})}(x)^2 \\right] = {\\mathbb{E}_{x \\sim p(x)} \\left[\\left(\\mathbb{E}_{(X_{train}, y_{train})} \\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right]\\right)^2 + \\mathbb{E}_{(X_{train}, y_{train})} \\left[\\left(\\hat{f}_{(X_{train}, y_{train})}(x) - \\mathbb{E}_{(X_{train}, y_{train})}\\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right]\\right)^2\\right]\\right]}.$$\n",
"Здесь второе слагаемое правой части интерпретируется как разброс, то есть мера отклонения предсказаний модели от среднего предсказания модели при усреднении по всем возможным обучающим выборкам (и случайностям обучения).\n",
"\n",
"Сложим обратно три разобранных отдельно члена и заметим, что все слагаемые, которые не является шумом и разбросом, группируются в квадрат разности. Получим:\n",
"$$\\mathbb{E}_{(x, y) \\sim p(x, y)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[\\left(y - \\hat{f}_{(X_{train}, y_{train})}(x)\\right)^2\\right] = \\mathbb{E}_{x \\sim p(x)} \\left[ \\left(\\mathbb{E}_{(X_{train}, y_{train})} \\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right] - \\mathbb{E}_{y \\sim p(y \\vert x)} [y \\vert x]\\right)^2\\right] + \\mathbb{E}_{x \\sim p(x)} \\mathbb{E}_{(X_{train}, y_{train})} \\left[\\left(\\hat{f}_{(X_{train}, y_{train})}(x) - \\mathbb{E}_{(X_{train}, y_{train})}\\left[\\hat{f}_{(X_{train}, y_{train})}(x)\\right]\\right)^2\\right] + \\mathbb{E}_{(x, y) \\sim p(x, y)} \\left[\\left(y - \\mathbb{E}_{y \\sim p(y \\vert x)}[y \\vert x]\\right)^2\\right]$$\n",
"Это и есть формула разложения оценки качества метода обучения со всей его спецификацией на смещение, разброс и неустранимую ошибку (шум). Смещением здесь является первое слагаемое, интерпретируемое как среднеквадратичное отклонение от истинных значений для усреднённых предсказаний обученной модели с усреднением по всем обучающим выборкам (и случайностям обучения).\n",
"\n",
"#### Интерпретация\n",
"\n",
"Хотя выше формула была выведена только для случая MSE, интересен не столько её общий вид, сколько сами концепции смещения, разброса и шума.\n",
"\n",
"В зависимости от гиперпараметров у метода машинного обучения может меняться нечто, что можно назвать его выразительной силой, ёмкостью или мощностью. Одной из формализаций данного понятия является размерность Вапника-Червоненкиса, но в рамках этой заметки оно будет пониматься неформально.\n",
"\n",
"Утверждается, что чем выше выразительная сила метода машинного обучения, тем ниже его смещение, потому что есть больше возможностей по $x$ получить $\\mathbb{E}_{y \\sim p(y \\vert x)} [y \\vert x]$. С другой стороны, чем выше выразительная сила метода машинного обучения, тем выше его разброс, потому что разные обучающие выборки допускают всё больше и больше разных моделей, приближающих на них зависимость целевой переменной от признаков. Наконец, на шум метод машинного обучения не влияет, потому что это свойство распределения $p(x, y)$. Оставив шум за скобкой, получим, что должна существовать некоторая оптимальная выразительная сила. Если взята меньшая выразительная сила, произойдёт недоподгонка (underfitting): узким местом окажется грубость модели. Если взята большая выразительная сила, произойдёт переподгонка (overfitting): узким местом окажется неустойчивость модели при замене обучающей выборки. Так понятия недоподгонки и переподгонки обретают дополнительный смысл благодаря понятиям смещения и разброса."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_машинного_обучения",
"функции_потерь"
]
},
"source": [
"## Аппроксимация функции потерь\n",
"\n",
"В задачах классификации часто возникают функции потерь, не являющиеся непрерывными, а потому и не являющиеся дифференцируемыми. Это делает невозможным применение к ним оптимизационных методов, для которых нужны градиенты. Очевидный пример такой функции потерь — точность по обоим классам (accuracy) в задаче бинарной классификации:\n",
"$$l(y_i, \\hat{p_i}) = y_i [p_i >= t] + (1 - y_i) [p_i < t],$$\n",
"где $y_i \\in \\{0, 1\\}$ — класс $i$-го объекта, $\\hat{p_i}$ — предсказанная классификатором степень уверенности в принадлежности $i$-го объекта к положительному классу, $t$ — порог для отображения степени уверенности классификатора в предсказанный класс (если классификатор возвращает откалиброванные вероятности, то $t=\\frac{1}{2}$), а квадратные скобки обозначают индикатор (так называемая нотация Айверсона). Из-за того что индикатор разрывен, да ещё и на границе принятия решения (т.е., грубо говоря, в самом интересном месте), оптимизировать такую функцию потерь затруднительно.\n",
"\n",
"Отступом (margin) $i$-го объекта от границы принятия решений будет называть некоторую функцию от $y_i$, $p_i$ и $t$, удовлетворяющую следующим условиям:\n",
"* если отступ положительный, то объект классифицирован верно, а если отрицательный, то неверно;\n",
"* чем отступ больше по модулю, тем выше уверенность классификатора в предсказанном классе $i$-го объекта.\n",
"\n",
"В частности, отступ можно определить как $m_i = (2y_i - 1)(\\hat{p_i} - t)$.\n",
"\n",
"Через отступ точность по обоим классам выражается так:\n",
"$$l(m_i) = [m_i < 0],$$\n",
"причём это верно для любого отступа, потому что следует из первого условия, которому отступ должен удовлетворять.\n",
"\n",
"Если функция потерь $l(y_i, \\hat{p_i})$ выражается как функция отступа $l(m_i)$, то вместо неё можно оптимизировать функцию $l^\\prime(m_i)$, являющуюся выпуклой и такой, что $\\exists k > 0$, такое что $\\forall x \\in \\mathbb{R}$ $l(x) \\le k l^\\prime(x)$. Существует теорема, гласящая, что оптимизация любой $l^\\prime$, обладающей двумя перечисленными свойствами, приведёт и к оптимизации $l$ тогда и только тогда, когда $l^\\prime$ дифференцируема в 0 и её производная в нуле отрицательна.\n",
"\n",
"Для точности по обоим классам в качестве $l^\\prime$ могут быть использованы:\n",
"* функция потерь из метода опорных векторов, также известная как hinge loss, $l^\\prime(m_i) = [m_i - 1 < 0]$;\n",
"* логистическая функция потерь, $l^\\prime(m_i) = \\log_2(1 + e^{-m_i})$.\n",
"\n",
"Логистическая функция потерь обладает интересным свойством: на самом деле, она является [логарифмической функцией потерь](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона), переписанной для частного случая, когда в качестве классификатора используется логистическая регрессия. Для логистической регрессии предсказанная вероятность принадлежности $i$-го объекта к положительному классу такова:\n",
"$$p_i = \\sigma(w^Tx_i) = \\frac{1}{1 + e^{-w^Tx_i}},$$\n",
"где $w$ — вектор весов, а $x_i$ — вектор признаков. В качестве отступа возьмём $m_i = (2y_i - 1)\\sigma^{-1}(p_i) = (2y_i - 1)w^Tx_i$ (зависимости от $t$ тут нет, но, если что, в данном случае $t = \\frac{1}{2}$). Если теперь всё это подставить в определение логарифмической функции потерь, то и получится логистическая функция потерь:\n",
"$$\\mathrm{log\\_loss}(y_i, p_i) = -y_i\\log_2 p_i - (1 - y_i)\\log_2(1 - p_i) = y_i\\log_2(1 + e^{-w^Tx_i}) + (1 - y_i)\\log_2(1 + e^{w^Tx_i}) = \\log_2(1 + e^{-m_i}),$$\n",
"где последний переход доказывается разбором двух случаев, когда $y_i$ равно 0 или 1."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"активное_обучение"
]
},
"source": [
"## Активное обучение\n",
"\n",
"#### Общая информация\n",
"\n",
"Активное обучение поочерёдно совмещает два процесса:\n",
"* обучение модели с учителем,\n",
"* сбор размеченных данных, на которых будет обучаться следующая версия модели.\n",
"\n",
"По сравнению с обучением с учителем единственный новый вопрос таков: для каких дополнительных объектов нужно узнать целевую переменную, чтобы максимально улучшить имеющуюся модель.\n",
"\n",
"Формализуем вышесказанное. Пусть есть исходные обучающие данные $(X_\\mathrm{train}, y_\\mathrm{train})$. Также предположим, что есть неразмеченные данные $X_\\mathrm{extra}$, которые содержат только признаки, однако есть возможность, затратив ресурсы, узнать целевую переменную для любого объекта оттуда. Активное обучение в виде псевдокода устроено так:\n",
"* пока не пройдёт заданное число итераций:\n",
" - обучить модель $f$ на $(X_\\mathrm{train}, y_\\mathrm{train})$;\n",
" - оценить все объекты из $X_\\mathrm{extra}$ некоторой функцией $\\phi_f$, зависящей от модели $f$;\n",
" - $k$ моделей с наибольшими значениями этой функции поместить во множество $X_\\mathrm{new}$;\n",
" - разметить $X_\\mathrm{new}$, получив тем самым обучающие данные $(X_\\mathrm{new}, y_\\mathrm{new})$;\n",
" - $(X_\\mathrm{train}, y_\\mathrm{train}) := (X_\\mathrm{train} \\cup X_\\mathrm{new}, y_\\mathrm{train} \\cup y_\\mathrm{new})$;\n",
" - $X_\\mathrm{extra} := X_\\mathrm{extra} \\setminus X_\\mathrm{new}$;\n",
"\n",
"На самом деле, приведённый псевдокод относится только к активному обучению с отбором из коллекции (pool-based sampling). В общем случае объекты, доступные для разметки, могут меняться от итерации к итерации, как при отборе из потока (stream-based selective sampling), или же для любого признакового описания можно узнать целевую переменную, как при генерации объектов (query synthesis). Поскольку алгоритм отбора из коллекции обобщается на эти случаи, далее будет рассматриваться только он. Ещё можно отметить, что в целом в науке есть такая область, как планирование эксперимента (design of experiment), занимающаяся определением наблюдений, для которых нужно собрать данные — активное обучение является её частью, где полезность наблюдений зависит от их влияния на модель.\n",
"\n",
"С практической точки зрения активное обучение позволяет сократить расходы на разметку данных. Однако платой за это является то, что объекты, отобранные при активном обучении, нерепрезентативны, то есть смещены относительно генеральной совокупности. В частности, на таких данных нельзя оценивать качество модели (по крайней мере, прямо в лоб), а значит их нельзя использовать и для подбора гиперпараметров.\n",
"\n",
"#### Возможные варианты оценивающих функций\n",
"\n",
"Псевдокод из предыдущего раздела показывает, что все отличия между методами отбора примеров сводятся к выбору $\\phi_f$. Как правило, $\\phi_f$ выбирают, отталкиваясь от какой-либо эвристики.\n",
"\n",
"Одна из эвристик — выбирать объекты по степени неуверенности в предсказаниях на них. Для многоклассовой классификации в таком случае возможны следующие варианты:\n",
"* минимальная уверенность в предсказанном классе: $\\phi_f(x_i) = - \\max_j \\hat{p}_{ij}$, где $j$ пробегает все классы, а $\\hat{p}_{ij}$ — возвращённая моделью $f$ степень уверенности в принадлежности объекта $x_i$ к $j$-му классу;\n",
"* минимальный зазор между предсказанным классом и следующим за ним: $\\phi_f(x_i) = - \\max_j \\hat{p}_{ij} + \\max_{j \\ne \\arg \\max_j \\hat{p}_{ij}} \\hat{p}_{ij}$;\n",
"* энтропия предсказанных вероятностей: $\\phi_f(x_i) = \\sum_j \\hat{p}_{ij} \\log \\hat{p}_{ij}$.\n",
"\n",
"В случае бинарной классификации эти три варианта эквивалентны друг другу. Ещё из общего у всех трёх вариантов то, что они высоко ранжируют [выбросы](__home_url__/notes/Автоматическое обнаружение выбросов), поэтому имеет смысл также учитывать в $\\phi_f$ степень типичности объекта. \n",
"\n",
"Для регрессии можно выбирать объекты по [оценке дисперсии целевой переменной](__home_url__/notes/Оценивание дисперсии целевой переменной).\n",
"\n",
"Ещё одна формализация для степени неуверенности подходит и для классификации, и для регрессии. Вместо одной модели $f$ можно обучить несколько (так называемый комитет), а потом отбирать объекты, на которых предсказания комитета сильнее всего расходятся:\n",
"* для классификации в качестве меры расхождения можно взять [дивергенцию Кульбака-Лейблера](__home_url__/notes/Дивергенция Кульбака-Лейблера): $\\phi_f(x_i) = \\sum_k D_{KL}(\\hat{p}_{ijk} \\Vert \\overline{p}_{ij})$, где индексом $k$ пронумерованы модели из комитета, $\\hat{p}_{ijk}$ — вероятность принадлежности $x_i$ к $j$-му классу, предсказанная $k$-й моделью, а $\\overline{p}_{ij}$ — средняя по всем моделям комитета вероятность принадлежности $x_i$ к $j$-му классу;\n",
"* для регрессии можно взять среднеквадратичный разброс предсказаний: $\\phi_f(x_i) = \\sum_k (\\hat{y}_{ik} - \\overline{y}_i)^2$, где $\\hat{y}_{ik}$ — предсказание на объекте $x_i$, сделанное $k$-й моделью, а $\\overline{y}_i$ — среднее по всем моделям комитета предсказание.\n",
"\n",
"Есть и эвристики, не связанные с неопределённостью:\n",
"* выбирать объекты с наибольшим ожидаемым влиянием на параметры модели (expected model change);\n",
"* выбирать объекты, максимизирующие ожидаемое сокращение функции потерь на уже размеченных примерах (expected error reduction)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"постановка_задачи"
]
},
"source": [
"## Задача управления на базе машинно-обученной модели\n",
"\n",
"Машинное обучение может использоваться для решения задачи предсказания, а может использоваться для решения задачи управления. Чтобы увидеть разницу между этими двумя задачами, набросаем общий сценарий и введём некоторое количество базовых сущностей (выделены курсивом). Итак, пусть машинно-обученная _модель_ возвращает предсказания, _пользователь_ модели, получив эти предсказания, принимает _решение_, связанное с каким-либо _процессом_, а конечный _результат_ для пользователя зависит как от его решения, так и от того, как пройдёт процесс. В рамках такого описания задача является задачей предсказания, если решение пользователя не способно повлиять на внутренние стороны процесса, и является задачей управления, если решение пользователя изменяет протекание процесса. Сценарий можно и расширить, допустив, что в задаче управления пользователь также может влиять на признаки объектов и выбирать, для объектов с какими признаками получать предсказания.\n",
"\n",
"Примером задачи предсказания является задача кредитного скоринга. Здесь модель по признакам заёмщика предсказывает вероятность того, что кредит будет возвращён, пользователем является банк, решением является выдавать или нет кредит какому-то конкретному заёмщику, а процессом является процесс выплаты кредита этим заёмщиком. Поскольку платежеспособность заёмщика не зависит от того, в каком банке он получит кредит на условиях, идентичных условиям, предложенным банком, это именно задача предсказания.\n",
"\n",
"Примером задачи управления является задача планирования промо-акций в розничных сетях. В одной из наиболее простых постановок рассматривается всего один товар, и модель по размеру скидки, прошлой истории продаж, дню недели, прогнозу погоды и некоторым другим факторам должна предсказать, сколько единиц товара купят завтра. Здесь пользователем модели является розничная сеть, решением является выставленная скидка, а процессом является поведение покупателей в магазине, а именно то, как они берут продвигаемый товар. Результатом становится валовая прибыль, то есть суммарное количество приобретённых единиц товара, умноженное на отпускную цену. Описанная задача не является задачей предсказания, потому что размер скидки напрямую влияет на покупательское поведение.\n",
"\n",
"В задачах управления качество предсказательной модели иногда бывает сложно оценить на реальных данных. Например, менеджеры, выбрав изначальную скидку и увидев, что весь запас товара разберут, могут решить уменьшить скидку, но если условия сервиса с моделью, которым они пользуются, предполагают ограничение на то, что запросов на предсказание может быть не более одного в день, то предсказание спроса для новой скидки уже не будет получено, и фактический спрос будет не с чем сравнивать.\n",
"\n",
"Однако обычно сценарий использования моделей для задачи управления другой. Предсказательная модель встраивается в функцию от управляемых и неуправляемых параметров, возвращаемое значение которой нужно оптимизировать по управляемым параметрам, соблюдая наложенные на них ограничения. Скажем, если в задаче планирования промо-акций предоставленная моделью функция $\\mathrm{predict}$ предсказывает спрос по размеру скидки, температуре воздуха и вчерашнему спросу, то оптимизируемая функция валовой прибыли имеет вид:\n",
"$$f(\\mathrm{discount}, \\mathrm{temperature}, \\mathrm{lag}) = (\\mathrm{initial\\_price} - \\mathrm{discount}) * \\mathrm{predict}(\\mathrm{discount}, \\mathrm{temperature}, \\mathrm{lag}).$$\n",
"Эту функцию требуется оптимизировать по $\\mathrm{discount} \\in [0; \\mathrm{initial\\_price}]$, и это дополнительная задача оптимизации по суррогатной модели. Модель названа суррогатной, потому что была оценена по данным, а не выведена на основании законов и/или правил, относящихся к предметной области.\n",
"\n",
"Задача управления на базе машинно-обученной модели имеет следующие нюансы:\n",
"* Может присутствовать ограничение на используемые методы машинного обучения (например, ансамбли над решающими деревьями возвращают функцию $\\mathrm{predict}$, являющуюся кусочно-постоянной и потому имеющую неинформативную производную);\n",
"* Помимо ошибок, содержащихся в данных, и ошибок, вызываемых аппроксимацией целевой переменной, появляются ошибки оптимизации (скажем, вызванные локальными экстремумами), то есть нужно быть требовательнее к данным и стараться обеспечить запас качества модели;\n",
"* Наличие предсказательной силы не гарантирует наличие причинно-следственных связей; в частности, к истинному влиянию управляемого параметра моделью может быть ошибочно приписано влияние пропущенных параметров, скоррелированных с этим управляемым параметром. В эконометрике такие явления называют эндогенностью. Как следствие же, модель нужно обучать не только ради точного предсказания целевой переменной, но и ради достоверной оценки влияния факторов на эту целевую переменную."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_машинного_обучения"
]
},
"source": [
"## Калибровка предсказанных вероятностей\n",
"\n",
"#### Введение\n",
"\n",
"Некоторые алгоритмы классификации возвращают только класс, к которому, по их предсказаниям, принадлежит объект, но не в состоянии вернуть вероятности принадлежности к классам. Другие алгоритмы классификации способны возвращать также степени своей уверенности в принадлежности объекта к классам, однако зачастую с этими степенями уверенности надлежит обращаться лишь как с порядковыми величинами, а не как с количественными. Хотя такие величины иногда и называют предсказанными вероятностями принадлежности к классу, в общем случае нет никаких гарантий того, что они объективно отражают степени неопределённости. В частности, в статье [Niculescu-Mizil, Caruana, 2004](http://www.datascienceassn.org/sites/default/files/Predicting%20good%20probabilities%20with%20supervised%20learning.pdf) утверждается, что:\n",
"* Наивный байесовский классификатор смещает вероятности ближе к краям, то есть ближе к 0% или к 100%;\n",
"* Метод опорных векторов и градиентный бустинг над классификационными деревьями смещают вероятности от краёв к центру.\n",
"\n",
"С точки зрения метрик, зависящих только от возвращаемого моделью упорядочивания объектов (скажем, таких метрик, как [ROC AUC](__home_url__/notes/ROC AUC), описанная проблема не имеет значения. Однако для общей точности (accuracy) и точности по положительному классу (precision) порог в 50% для конвертации вероятностей в бинарные метки классов имеет ожидаемый смысл, только если речь идёт об истинных вероятностях. Со многими функциями потерь та же проблема, что и с метриками: например, в логарифмической функции потерь присутствуют предсказанные вероятности, так что если бы они точнее давали количественную оценку неопределённости, процесс обучения мог бы улучшиться. Наконец, истинные вероятности бывают важны с точки зрения предметной области: скажем, в задаче кредитного скоринга потенциальный убыток пропорционален вероятности невозврата кредита. В связи со всем вышесказанным нужны техники, способные откалибровать предсказанные вероятности, сделав их более похожими именно на количественные вероятности.\n",
"\n",
"#### Процедура калибровки\n",
"\n",
"В случае бинарной классификации процесс калибровки устроен так:\n",
"* Обучающая выборка (то есть то, что изначально предлагалось использовать только для настройки параметров, а не для подбора гиперпараметров и слепой финальной оценки) разбивается на то, на чём и будет проходить обучение (скажем, 90% по размеру), и на выборку для калибрации (стало быть, 10% по размеру). Также вместо деления выборки на две части можно сделать серию разделений аналогично тому, как это делается для кросс-валидации.\n",
"* На подвыборке, выделенной под обучение, настраивается модель.\n",
"* Если модель возвращает предсказанные вероятности, то в качестве нового признака объектов из калибрационной выборки берётся вероятность положительного класса. Однако даже если модель не возвращает вероятности, достаточно лишь того, чтобы модель возвращала что-то, по чему объекты можно отранжировать: например, для линейных классификаторов это будет значение функции $g(Xw)$, по знаку которого определяется предсказанный класс;\n",
"* Обучается калибрующая модель, по единственному новому признаку объектов калибрационной выборки (и константе) предсказывающая их класс. Предсказанная ей вероятность уже и будет считаться откалиброванной вероятностью.\n",
"\n",
"#### Калибрующие модели\n",
"\n",
"Одним из наиболее простых вариантов является калибровка Платта. В ней в качестве калибрующей модели берётся логистическая регрессия без какой-либо регуляризации. Эффект калибровки заключается в том, что методом максимального правдоподобия будут найдены коэффициент масштаба $a$ и коэффициент сдвига $b$, такие что значения $\\sigma(ax+b)$, где $\\sigma$ — сигмоидная функция, станут более содержательными. Работает это в основном тогда, когда искажение предсказанных вероятностей относительно истинных вероятностей действительно может быть исправлено сигмоидальным преобразованием.\n",
"\n",
"Более универсальным вариантом является использование в качестве калибрующей модели изотонической регрессии. Изотоническая регрессия — метод машинного обучения, в котором минимизируется MSE в точках обучающей выборки с ограничением на монотонность (то есть в случае с калибровкой чем выше была исходная предсказанная вероятность, тем выше должна быть откалиброванная вероятность). На этапе обучения решается задача квадратичного программирования. Для точек, отсутствовавших в обучающей выборке, можно использовать любую монотонную интерполяцию: например, линейную, и тогда получится, что изотоническая регрессия восстанавливает кусочно-линейную зависимость. "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_машинного_обучения",
"регуляризация"
]
},
"source": [
"## Регуляризация штрафом, накладываемым на норму обучаемых параметров\n",
"\n",
"Пусть есть метод машинного обучения, который настраивает по данным вектор параметров модели $\\theta$. Напомним, что эмпирическим риском называется среднее по обучающей выборке $(X_\\mathrm{train}, y_\\mathrm{train})$ значение функции потерь на объектах из неё, и именно эту величину метод машинного обучения должен минимизировать. Обозначим эмпирический риск за $E(\\theta) = E(\\theta, X_\\mathrm{train}, y_\\mathrm{train})$, то есть далее краткости ради зависимость от $(X_\\mathrm{train}, y_\\mathrm{train})$ будет опускаться. \n",
"\n",
"В общем случае регуляризацией называются любые изменения в процессе обучения, от которых ошибка на обучающей выборке не уменьшается, а вот на тестовой выборке уменьшается. Частным случаем регуляризации является добавление к эмпирическому риску штрафного слагаемого:\n",
"$$\\alpha \\Vert \\theta \\Vert_p = \\alpha \\left(\\sum_{i=1}^k \\vert \\theta_i \\vert^p\\right)^\\frac{1}{p},$$\n",
"где $\\alpha \\ge 0$ — гиперпараметр, задающий силу регуляризации, а $k$ — длина вектора $\\theta$.\n",
"\n",
"Наиболее часто используются значения $p = 1$ ($L_1$-регуляризация, LASSO Тибширани) и $p = 2$ ($L_2$-регуляризация, гребневая регрессия). Первый из этих вариантов приводит к занулению параметров, слабо влияющих на эмпирический риск, а второй — лишь к затуханию таких параметров.\n",
"\n",
"Чтобы понять, чем вызвано это отличие, посмотрим на добавление штрафа $\\alpha \\Vert \\theta \\Vert_p$ под другим углом. Рассмотрим задачу, которая, на первый взгляд, может показаться иной: минимизировать $E(\\theta)$ при ограничении $\\Vert \\theta \\Vert_p \\le c$, где $c > 0$ — заданная константа. Функция Лагранжа для такой задачи имеет вид:\n",
"$$L(\\theta, \\lambda) = E(\\theta) + \\lambda (\\Vert \\theta \\Vert_p - c),$$\n",
"где $\\lambda \\ge 0$ (неотрицательность $\\lambda$ возникает, потому что эта $\\lambda$ относится к ограничению в виде неравенства, а если бы было ограничение в виде равенства, то $\\lambda$ могла бы быть любым числом).\n",
"\n",
"Если ограничения соблюдаются, то:\n",
"$$\\max_{\\lambda \\ge 0} L(\\theta, \\lambda) = E(\\theta).$$\n",
"Если же ограничения не соблюдаются, то:\n",
"$$\\max_{\\lambda \\ge 0} L(\\theta, \\lambda) = +\\infty.$$\n",
"Из этих двух соображений вытекает, что следующие две задачи эквивалентны:\n",
"$$\\min_\\theta \\max_{\\lambda \\ge 0} L(\\theta, \\lambda),$$\n",
"$$\\min_{\\theta, \\Vert \\theta \\Vert_p \\le c} E(\\theta).$$\n",
"Если вернуться к регуляризации штрафом на норму, эквивалентность этих двух задач означает, что для каждого $\\alpha > 0$ существует $c > 0$, такое что задача минимизации регуляризированного эмпирического риска эквивалентна задаче минимизации эмпирического риска без регуляризации, но с ограничением $\\Vert \\theta \\Vert_p \\le c$. Чем меньше $\\alpha$, тем больше $c$, а при $\\alpha = 0$ получаем, что, грубо говоря, $c = +\\infty$, то есть ограничения нет. Биекция, отображающая $\\alpha$ в $c$, зависит от $E(\\theta)$ и, в частности, от $(X_\\mathrm{train}, y_\\mathrm{train})$, так что в общем случае у неё нет явного аналитического вида. Поэтому иногда бывает удобнее регуляризацию на норму $\\theta$ формулировать через $c$, а не через $\\alpha$: например, если подобная формулировка имеет интерпретацию, связанную с решаемой задачей.\n",
"\n",
"Наконец, вернёмся к сравнению $L_1$- и $L_2$-регуляризаций. Получается, первая из них ищет $\\theta$ в $k$-мерном кубе с центром в начале координат и вершинами, у которых ровно одна координата равна $c$, а остальные равны 0. Вторая же ищет $\\theta$ в $k$-мерном шаре с центром в начале координат и радиусом $c$. Этот куб содержится в этом шаре. Более того, при увеличении $c$ шар может касаться линий уровня $E(\\theta)$ любой своей точкой, но для куба из-за его геометрии выше шансы, что он впервые пересечёт линию уровня $E(\\theta)$ ребром, а не гранью. Это и объясняет, откуда берётся отбор признаков. А для понимания, почему что отбор параметров у $L_1$-регуляризации, что затухание параметров у $L_2$-регуляризации затрагивают слабо влияющие параметры, а не важные параметры, можно взглянуть на иллюстрацию со страницы 229 книги [Goodfellow, Bengio, Courville (2016)](https://www.deeplearningbook.org/contents/regularization.html)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"регуляризация"
]
},
"source": [
"## Ранняя остановка\n",
"\n",
"У некоторых методов машинного обучения среди их гиперпараметров выделяется один, напрямую связанный со временем обучения и такой, что по мере его увеличения сокращается риск недоподгонки и возрастает риск переподгонки. Для градиентного бустинга таким параметром является количество деревьев, а для нейронных сетей — количество эпох.\n",
"\n",
"Для предотвращения избыточного увеличения этого гиперпараметра используется такой приём, как ранняя остановка. У него есть несколько версий, но все они начинаются с того, что обучающая выборка $(X_\\mathrm{train}, y_\\mathrm{train})$ разбивается на две непересекающиеся подвыборки $(X_\\mathrm{subtrain}, y_\\mathrm{subtrain})$ и $(X_\\mathrm{early\\_stopping}, y_\\mathrm{early\\_stopping})$. На первой из них происходит обучение, и через каждые $k$ значений обсуждаемого гиперпараметра проводится оценка качества на второй из них. Чем больше $k$, тем меньше вычислительных ресурсов тратится (и, возможно, времени, если оценка качества не делается параллельно с продолжением обучения), но зато тем грубее оценка оптимального значения. Как только на последних $t$ оценках качества метрика не улучшалась по сравнению с лучшим значением по всем оценкам качества, обучение приостанавливается. Модель с наилучшей текущей оценкой качества можно хранить, чтобы в итоге вернуть её, а не то, что получилось через $tk$ итераций после неё.\n",
"\n",
"А вот дальше возможны варианты:\n",
"* считать финальной моделью то, что обучилось на $(X_\\mathrm{subtrain}, y_\\mathrm{subtrain})$: так быстрее всего, но так $(X_\\mathrm{early\\_stopping}, y_\\mathrm{early\\_stopping})$ не используются на полную;\n",
"* с нуля обучить на $(X_\\mathrm{train}, y_\\mathrm{train})$ новую модель с получившимся оптимальным значением гиперпараметра (для нейронных сетей есть открытый вопрос: брать ли то же количество эпох или то же количество пакетов, на которых обновляются веса);\n",
"* получившуюся на $(X_\\mathrm{subtrain}, y_\\mathrm{subtrain})$ модель продолжить дообучать на $(X_\\mathrm{train}, y_\\mathrm{train})$, пока функция потерь на $(X_\\mathrm{train}, y_\\mathrm{train})$ не достигнет того же значения, какого она достигла на $(X_\\mathrm{subtrain}, y_\\mathrm{subtrain})$ в оптимальный момент."
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}