От статистики к машинному обучению

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

Две ошибки пожарной сигнализации

Система решает, эвакуировать ли здание. Ложная тревога останавливает работу, но пропуск пожара угрожает людям. Accuracy считает обе ошибки одинаковыми:

$$\ell_{0/1}(a,y)=\mathbf1\{a\ne y\}.$$

Эта формула молча утверждает, что остановить конвейер на два часа и не заметить дым — одно и то же событие, стоящее одну единицу. Ни один пожарный инспектор такого договора не подпишет. Матрица потерь различает действия:

$$\begin{array}{c|cc} &y=0&y=1\\ \hline a=0&0&10000\\ a=1&20&0 \end{array}$$

Здесь $a=1$ — эвакуация, $y=1$ — пожар, числа — условные единицы ущерба. Если модель оценивает $p=P(y=1\mid x)$, ожидаемые потери двух действий:

$$R(0\mid x)=10000\,p,\qquad R(1\mid x)=20\,(1-p).$$

Эвакуация выгоднее, как только $10000p>20(1-p)$, то есть при

$$p>p^*=\frac{20}{20+10000}=0{,}001996\approx 0{,}002 .$$

Две тысячных. Порог возник из цены решений, а не из симметричного числа $0{,}5$, и он в двести пятьдесят раз меньше привычной середины. Модель при этом ни разу не переобучалась: изменилась только бухгалтерия.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Общая матрица и правило выбора действия

Пусть действий $a\in\{0,1\}$, а цены ошибок обозначены $c_{FP}$ (ложная тревога) и $c_{FN}$ (пропуск). Верные решения условимся считать бесплатными. Тогда

$$R(0\mid x)=c_{FN}\,p,\qquad R(1\mid x)=c_{FP}\,(1-p),$$

и точка безразличия находится из $c_{FN}p=c_{FP}(1-p)$:

$$p^*=\frac{c_{FP}}{c_{FP}+c_{FN}} .$$

Формула читается словами: порог — это доля цены ложной тревоги в сумме цен двух ошибок. Удвойте стоимость ложной тревоги — порог поднимется, система станет осторожнее объявлять тревогу. Удесятерите цену пропуска — порог упадёт. Заметьте, что в формулу не вошли ни базовая частота события, ни объём выборки, ни архитектура модели: вся частотная информация уже упакована в $p$.

Потеря из вероятностной модели

Матрица цен приходит из предметной области. Но откуда берётся сама потеря, по которой мы обучаем? Пусть модель задаёт условную плотность $p_\theta(y\mid x)$. Максимизация правдоподобия из урока 45 эквивалентна минимизации среднего отрицательного логарифма:

$$\widehat\theta= \arg\min_\theta\; -\frac1n\sum_{i=1}^n\log p_\theta(y_i\mid x_i).$$

Для нормального ответа с постоянной дисперсией $\sigma^2$

$$-\log p_\theta(y\mid x)=\frac{(y-f_\theta(x))^2}{2\sigma^2}+\log\sqrt{2\pi\sigma^2},$$

и минимизация по $\theta$ сводится к сумме квадратов — так была выведена линейная регрессия. Для Бернулли получается бинарная кросс-энтропия:

$$\ell(p,y)=-y\log p-(1-y)\log(1-p).$$

Log-loss жёстко штрафует уверенную ошибку: при $y=1$ прогноз $p=0{,}001$ стоит $-\log 0{,}001\approx6{,}91$, а $p=0{,}4$ — лишь $0{,}92$. Разница в семь с половиной раз — это и есть цена самоуверенности.

Вальд перевернул привычную оптику: не «какая оценка правильная», а «какое решающее правило дешевле в среднем». Всё, что мы делаем в этом уроке, — школьный пересказ этой мысли на языке классификаторов.

Правило оценивания, которому выгодна честность

Предположим, синоптик знает истинную вероятность дождя $p$, но сообщает число $q$. Какая метрика заставит его сказать правду? Для log-loss ожидаемая потеря

$$\mathbb E\,\ell(q,Y)=-p\log q-(1-p)\log(1-q).$$

Производная по $q$ равна $-p/q+(1-p)/(1-q)$; приравняв её нулю, получаем $q=p$. Для Brier score $(q-y)^2$

$$\mathbb E\,(q-Y)^2=p(1-q)^2+(1-p)q^2,$$

производная $-2p(1-q)+2(1-p)q=2(q-p)$ обращается в нуль там же. А вот средний модуль ошибки

$$\mathbb E\,|q-Y|=p(1-q)+(1-p)q=p+q(1-2p)$$

линеен по $q$: при $p>1/2$ он падает до самого края, и честному синоптику выгодно кричать «дождь наверняка».

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Ченцов: почему логарифм здесь не случаен

Кажется, что строго proper правил бесконечно много (так и есть) и выбор между ними — дело вкуса. Советский математик Николай Николаевич Ченцов (1930–1992) показал, что у семейств распределений есть собственная геометрия, и она почти жёстко фиксирована. В книге «Статистические решающие правила и оптимальные выводы» (1972) он ввёл категорию статистических задач, в которой морфизмами служат марковские отображения — переходы к достаточным статистикам и огрублениям данных.

Смысл теоремы для нас прикладной. Если потребовать, чтобы мера расхождения между распределениями не зависела от того, в каких единицах и с какой детализацией записаны данные, то допустимый выбор сжимается почти до одной точки: информации Фишера из урока 46 и порождаемой ею дивергенции Кульбака — Лейблера, чьей выборочной версией и является log-loss. Логарифм в кросс-энтропии — не эстетическое предпочтение, а следствие требования инвариантности.

Почему 0/1-потеря неудобна обучению

Для линейного score $s(x)$ и метки $y\in\{-1,+1\}$ ошибка записывается как

$$\mathbf1\{y\,s(x)\le 0\},$$

ступенчатая функция отступа $m=ys$. Она почти всюду имеет нулевую производную, а в нуле — разрыв. Малое улучшение неверного score не меняет потерю до самого пересечения границы, поэтому градиентный метод из урока 22 не получает никакого направления. Более того, минимизация 0/1-потери по линейным правилам — NP-трудная задача в общем случае.

Используют суррогаты — выпуклые функции отступа:

$$\ell_{\log}(m)=\log\left(1+e^{-m}\right),\qquad \ell_{\text{hinge}}(m)=\max(0,1-m),\qquad \ell_{\exp}(m)=e^{-m}.$$

Все три в нуле равны единице (после нормировки логистической на $\log 2$) и мажорируют ступеньку, поэтому их минимизация ограничивает сверху долю ошибок. При этом они поощряют запас: точка, классифицированная верно с отступом $m=2$, всё ещё стоит $\log(1+e^{-2})\approx0{,}127$ ната — есть куда улучшаться. На рис. 57.3 логистическая кривая нормирована делением на $\log 2$, поэтому там та же точка читается как $0{,}183$; содержательно это одна и та же величина в других единицах.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лаборатория цены

Список оценок модели здесь зафиксирован раз и навсегда. Сначала не трогайте калибровку и двигайте только два ползунка цены: зелёная штриховая линия теоретического порога $c_{FP}/(c_{FP}+c_{FN})$ поедет вдоль оси, а красная точка эмпирического минимума будет ехать вместе с ней. Ни один вес не переобучался — переписался прайс-лист.

Затем поставьте порог вручную на $0{,}5$ и посмотрите, сколько это стоит при несимметричных ценах. Наконец переключите калибровку на «занижает» или «завышает»: AUC не изменится ни в одном знаке — порядок объектов монотонное преобразование не трогает, — а цена при теоретическом пороге вырастет. Ранжирование и решение по деньгам — разные способности модели.

Реальный спам: три прайс-листа — три порога

Возьмём коллекцию SMS Spam Collection: $5572$ сообщения, из них $747$ спама, доля спама $0{,}134$. Разделим её на обучение и тест в отношении $70{:}30$ и обучим логистическую регрессию на бинарных признаках слов. На тесте из $1672$ сообщений (в нём $224$ спама) при пороге $0{,}5$ получается $2$ ложные блокировки и $30$ пропусков — accuracy $0{,}981$ при том, что «объявить всё не спамом» даёт $0{,}866$.

Теперь переведём ошибки в деньги. При симметричных ценах $1{:}1$ оптимален порог $0{,}224$ со счётом $24$ единицы, тогда как привычные $0{,}5$ стоят $32$. Если блокировка настоящего письма в двадцать раз дороже пропуска спама ($20{:}1$), оптимум уезжает к $0{,}768$: счёт $41$ против $70$ при $0{,}5$ — переплата $29$ единиц. Если наоборот, пропуск дороже в двадцать раз ($1{:}20$), оптимальный порог падает до $0{,}069$ со счётом $186$, а порог $0{,}5$ обходится в $602$ — в $3{,}2$ раза дороже.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Калибровка отделима от ранжирования

Возьмём те же вероятности и монотонно исказим их: $q=p^3$. Порядок объектов не изменился ни на одну пару, поэтому AUC остался равен $0{,}9852$ — совпадение до двенадцатого знака. Но взвешенная ошибка калибровки выросла с $0{,}0124$ до $0{,}0312$, а главное — сломалось решение. При прайс-листе $20{:}1$ теория предписывает порог $20/21\approx0{,}952$; на честных вероятностях он стоит $79$ единиц, на искажённых — $118$. Тот же ранжировщик, та же таблица цен, счёт хуже в полтора раза.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Отсюда практическое разделение обязанностей. Сначала оценивается $P(y\mid x)$ и проверяется калибровка — теми же приёмами, что и в уроке 31. Затем минимизируется условный риск по актуальной матрице цен. Одна калиброванная модель обслуживает и дешёвый скрининг с низким порогом, и рискованное вмешательство с высоким. Если же обучать отдельный классификатор под каждый текущий порог, изменение цены потребует нового обучения и затруднит аудит.

Квадрат, модуль и квантиль

В регрессии выбор потери — это выбор того, какую характеристику условного распределения оценивает модель. Минимум

$$\mathbb E\left[(Y-a)^2\mid X=x\right]$$

достигается в условном среднем $\mathbb E[Y\mid X=x]$, минимум $\mathbb E[|Y-a|\mid X=x]$ — в условной медиане, а pinball-потеря

$$\rho_\tau(u)=u\left(\tau-\mathbf1\{u<0\}\right),\qquad u=y-q,$$

даёт условный квантиль уровня $\tau$. Проверим на реальных данных. Возьмём велопрокат и один срез: восемь утра рабочего дня, $496$ таких часов за два года. Спрос в этом срезе колеблется от $31$ до $839$ поездок; среднее $477{,}0$, медиана $463$, квантиль уровня $0{,}9$ равен $719$.

Численная минимизация трёх потерь по константе даёт $476{,}8$, $462{,}4$ и $718{,}6$ — с точностью до шага сетки ровно среднее, медиану и квантиль. Ниже среднего лежит $53{,}6\%$ дней, ниже квантиля $0{,}9$ — $90{,}3\%$: определения работают буквально.

$$\frac{\partial}{\partial q}\,\mathbb E\rho_\tau(Y-q)= -\tau P(Y>q)+(1-\tau)P(Y<q)=0 \;\Longleftrightarrow\; P(Y<q)=\tau .$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Задача газетчика: от цены к квантилю

Пусть нехватка одной единицы товара стоит $c_u$ (упущенная прибыль), а лишняя единица — $c_o$ (хранение). Ожидаемая суточная стоимость запаса $q$

$$\mathbb E\left[c_u\max(Y-q,0)+c_o\max(q-Y,0)\right]$$

пропорциональна $\mathbb E\rho_\tau(Y-q)$ при

$$\tau=\frac{c_u}{c_u+c_o},$$

то есть оптимальный запас — квантиль этого уровня. Классический результат теории запасов, ровно того же вида, что и порог $p^*$ для классификации.

Возьмём наш велопрокат: недостача велосипеда стоит $9$ рублей упущенной выручки, лишний велосипед — $1$ рубль обслуживания. Тогда $\tau=9/10=0{,}9$ и оптимальный парк на этот час равен $719$ машинам. Проверим деньгами: средняя суточная стоимость при запасе «по среднему» ($477$) равна $766{,}8$ рубля, при запасе по медиане — $820{,}1$, а при квантиле $0{,}9$ — $286{,}4$. Экономия относительно «разумного среднего» составляет $480{,}4$ рубля в день: расход падает в $2{,}7$ раза.

Редкий класс: веса, focal и что они портят

Если мошенничество составляет $0{,}1\%$, классификатор «всегда честно» получает $99{,}9\%$ accuracy. Стандартные приёмы: взвешенная потеря

$$\ell_w=w_1\,y\,\ell(p,1)+w_0\,(1-y)\,\ell(p,0),$$

focal loss $-(1-p)^\gamma\log p$, гасящая вклад уже лёгких примеров, и resampling, меняющий частоты в обучении.

Все три изменяют не только границу, но и шкалу. Модель, обученная на искусственно сбалансированных данных, видит другой prior, и её вероятности систематически завышены. Связь известна: если обучающая доля положительных $\pi'$ отличается от истинной $\pi$, то в шансах

$$\frac{p}{1-p}=\frac{p'}{1-p'}\cdot \frac{\pi}{1-\pi}\cdot\frac{1-\pi'}{\pi'} ,$$

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

PR-AUC часто информативнее ROC-AUC для редкого класса, потому что precision непосредственно реагирует на число ложных тревог, а доля ложноположительных в знаменателе ROC разбавлена огромным отрицательным классом. Но итоговая метрика всё равно должна быть переведена в поток решений: сколько проверок в день и сколько пропусков.

Потери для ранжирования

Иногда системе не нужна абсолютная вероятность: важно поставить релевантный документ выше нерелевантного. Pairwise-потеря сравнивает пару $(i,j)$ и штрафует случай, когда score хорошего объекта не выше:

$$\ell_{\text{pair}}=\log\left(1+e^{-(s_i-s_j)}\right).$$

Это та же логистическая функция, но от разности оценок, поэтому она инвариантна к сдвигу всей шкалы — и, как следствие, не даёт калиброванных чисел. Listwise-методы учитывают целый список и позиции: полезность первых трёх мест выше полезности сотого, поэтому NDCG дисконтирует низкие позиции весом $1/\log_2(1+\text{позиция})$.

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

Истинный риск и его выборочная замена

Для решающего правила $f$ истинный риск

$$R(f)=\mathbb E_{(X,Y)\sim P}\;\ell(f(X),Y)$$

усредняет потерю по будущему распределению. Мы не знаем $P$ и заменяем ожидание выборочным средним:

$$\widehat R_n(f)=\frac1n\sum_{i=1}^n\ell(f(x_i),y_i).$$

При фиксированном $f$ это несмещённая оценка, и закон больших чисел из урока 41 обещает сходимость. Но если то же $f$ выбрано по этой же выборке, оценка становится оптимистичной — почему именно и насколько, разберёт урок 58.

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

$$\mathbb E\left[(Y-f(X))^2\right]= \mathbb E\left[(f(X)-m(X))^2\right]+\mathbb E\left[\mathrm{Var}(Y\mid X)\right],$$

где $m(x)=\mathbb E[Y\mid X=x]$. Второе слагаемое — неустранимый шум: никакая модель его не уменьшит. Первое — то, за что отвечает обучение. Аналогичное разложение существует и для log-loss: избыточная потеря относительно идеального предсказателя равна средней дивергенции Кульбака — Лейблера между истинным условным распределением и предсказанным.

Когда цена недифференцируема

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

Рабочая схема состоит из трёх этажей. Обучаем по гладкому суррогату (кросс-энтропия), получая вероятности. Проверяем калибровку. И только затем решаем задачу распределения ресурса: отсортировать объекты по убыванию ожидаемой выгоды $c_{FN}p_i-c_{FP}(1-p_i)$ и брать сверху, пока не кончится квота. Такое правило совпадает с пороговым, если квота не связывает, и автоматически превращается в «порог по ёмкости лаборатории», если связывает.

Спор не с оптимизатором

Потеря — не техническая деталь оптимизатора, а место, где задача сообщает алгоритму свои ценности. Из вероятностной модели она выводится через минус логарифм правдоподобия; из прикладной постановки — через матрицу цен, и тогда порог решения равен $c_{FP}/(c_{FP}+c_{FN})$, а не $0{,}5$. Строго proper правила делают честность выгодной, теорема Ченцова объясняет, почему среди них логарифм занимает особое место, а суррогаты отступа существуют лишь потому, что у ступеньки нет градиента.

В регрессии выбор потери — это выбор точки распределения: квадрат даёт среднее, модуль — медиану, pinball — квантиль, и на реальном велопрокате разница между средним и квантилем $0{,}9$ составила $242$ поездки и $480$ рублей в день. Разделяйте три вещи: чем обучаете, что измеряете и что делаете. Спорить, как мы видели, нужно не с оптимизатором, а с прайс-листом.

Задачи