notes/machine_learning/evaluation.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"выбор_модели"
]
},
"source": [
"## Перечисление подходов к подбору гиперпараметров\n",
"\n",
"Способы подбора гиперпараметов алгоритма машинного обучения бывают следующими:\n",
"* перебор с экспоненциальной по числу гиперпараметров вычислительной сложностью:\n",
" - поиск по сетке (grid search) с кросс-валидацией относительно разбиения выборки на $k$ подвыборок,\n",
" - поиск по сетке с усреднением результатов $t$ кросс-валидаций относительно разбиения выборки на $k$ подвыборок;\n",
"* перебор, подходящий и для большого числа гиперпараметров:\n",
" - поиск по случайному подмножеству узлов полной сетки (randomized grid search),\n",
" - поиск по подмножеству, составленному в соответствии с некотрым детерминированным планом эксперимента (design of experiment), которым может быть:\n",
" - латинский гиперкуб,\n",
" - оптимизированный латинский гиперкуб,\n",
" - последовательность Холтона,\n",
" - последовательность Соболя;\n",
"* поиск оптимума в пространстве гиперпараметров на базе суррогатной модели:\n",
" - Байесовская оптимизация с предсказаниями, сделанными [регрессией на основе гауссовских процессов](__home_url__/notes/Регрессия на основе гауссовских процессов) (реализована такая оптимизация, например, в `skopt.gp_minimize`);\n",
"* некоторые теоретические оценки:\n",
" - для линейной регрессии оценка среднеквадратической ошибки при leave-one-out кросс-валидации считается в замкнутой форме без необходимости много раз настраивать веса,\n",
" - [информационные критерии](__home_url__/notes/Информационные критерии):\n",
" - Акаике, AIC,\n",
" - Шварца (также известен как байесовский), BIC;\n",
" - выбор гиперпараметров по байесовскому [принципу наибольшей обоснованности](__home_url__/notes/Принцип наибольшей обоснованности) (maximum evidence principle)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"выбор_модели"
]
},
"source": [
"## Информационные критерии\n",
"\n",
"Иногда в моделях из одного и того же семейства есть параметр, регулирующий сложность. Например, в семействе полиномиальных функций сложностью можно считать максимальную допустимую степень многочлена. Довольно часто сложность можно положить равной количеству оцениваемых по данным параметров — эта формулировка, в частности, включает в себя предыдущую, ведь при оценивании многочленом степени не выше $d$ оценивается $d+1$ параметр.\n",
"\n",
"Модели из одного и того же семейства, отличающиеся друг от друга только сложностью, можно оценивать при помощи информационных критериев.\n",
"\n",
"Информационный критерий Акаике имеет вид:\n",
"$$\\mathrm{AIC} = 2k - 2l,$$\n",
"где $k$ — количество оценённых по данным параметров, а $l$ — значение функционала качества, достигнутое на тренировочной выборке (например, логарифм правдоподобия данных при условии того, что выборка порождается из распределения, задаваемого той моделью, которая была построена на тренировочной выборке).\n",
"\n",
"Байесовский информационный критерий имеет вид:\n",
"$$\\mathrm{BIC} = \\log{(n)} \\, k - 2l,$$\n",
"где $n$ — размер тренировочной выборки.\n",
"\n",
"По сути, информационные критерии представляют собой оценку качества подгонки под данные с дополнительным штрафом за сложность модели. Интуитивно говоря, чем сложнее модель, тем больше ситуаций, под которые её можно подогнать и, значит, тем менее ценны уровни качества подгонки под данные.\n",
"\n",
"Чем ниже значение какого-либо информационного критерия, тем более хорошей считается модель."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"функции_потерь",
"теория_информации"
]
},
"source": [
"## Логарифмическая функция потерь и энтропия Шеннона\n",
"\n",
"Логарифмическая функция потерь (log loss) имеет вид:\n",
"$$\\mathrm{log\\_loss}\\left(y, \\hat{P}\\right) = -\\frac{1}{n}\\sum_{i = 1}^n\\sum_{j = 1}^c [y_i = j] \\, \\log \\hat{P}_{ij},$$\n",
"где $n$ — количество объектов, $c$ — количество классов, $y$ — вектор длины $n$, такой что его $i$-я компонента $y_i$ равна верному ответу на $i$-м объекте выборки, $\\hat{P}$ — матрица размера $n \\times c$, такая что на пересечении $i$-й строки и $j$-го столбца стоит предсказанная вероятность принадлежности $i$-го объекта к $j$-му классу, а, наконец, квадратные скобки даны в нотации Айверсона, то есть выражение с ними равно 1, если то, что в скобках, верно, и равно 0, если то, что в скобках, неверно.\n",
"\n",
"Логарифмическая функция потерь с точностью до константы является логарифмом от правдоподобия обучающей выборки. Если обозначить за $Y$ матрицу, $i$-й строкой которой является вектор, в котором везде стоят нули кроме содержащей единицу $j$-й позиции, где $j$ — истинная метка $i$-го объекта, то правдоподобие обучающей выборки относительно получившейся модели $\\hat{P}$ записывается в виде:\n",
"$$\\prod_{i=1}^n\\prod_{j=1}^c \\hat{P}_{ij}^{Y_{ij}}.$$\n",
"Обратить внимание стоит на то, что пронаблюдавшиеся метки объектов считаются детерминированными, то есть предполагается, что к меткам не подмешивается случайная ошибка, способная их исказить. Именно из-за детерминированности меток матрица $Y$ берётся в виде, где в каждой строке кроме нулей есть ровно одна единица, что после логарифмирования даёт множители вида $[y_i = j]$.\n",
"\n",
"Хотя точки оптимума для минимизации логарифмической функции потерь и максимизации правдоподобия совпадают, первый вариант предпочтительнее, если используются градиентные методы оптимизации, а в подсчёте $\\hat{P}$ фигурируют экспоненты (как, например, в софтмаксе). Когда взятие логарифма от правдоподобия убирает эти экспоненты, ииногда устраняются проблемы с затухающим градиентом.\n",
"\n",
"Помимо интерпретации, отталкивающейся от максимизации правдоподобия, логарифмическая функция потерь имеет интерпретацию, восходящую к теории информации.\n",
"\n",
"Чтобы понять, в чём именно связь, обратимся к понятию энтропии Шеннона. Энтропия Шеннона — функционал на вероятностных распределениях. Поскольку речь идёт о $c$-классовой классификации, определим энтропию Шеннона только на вероятностных распределениях на множестве $c$ классов, хотя на самом деле она определена и для непрерывных распределений:\n",
"$$H(p) = - \\sum_{i = 1}^c p_i \\log_2{p_i},$$\n",
"где $p = (p_i)_{i=1}^c$ — вектор длины $c$, такой что его $i$-я компонента $p_i$ равна вероятности того, что просэмплированный из генеральной совокупности объект принадлежит к $i$-му классу.\n",
"\n",
"Какой смысл в так определённой величине? Короткий ответ: она сообщает, чему равно математическое ожидание (относительно генеральной совокупности) количества бит информации, получаемой при измерении класса одного случайного объекта. Например, если все классы кроме одного имеют нулевую вероятность, то $H(p) = 0$, ведь никакой информации в измерении класса нет: и без измерений известно, что может быть только один класс.\n",
"\n",
"Из короткого ответа непонятно, почему энтропия Шеннона, и впрямь, является ожидаемым количеством бит информации, даваемым замером класса на одном случайном объекте. Чтобы углубиться в это, придётся немного формализовать задачу. Допустим, метку каждого класса представили в виде последовательности нулей и единиц (т.е. последовательности бит) так, что у разных классов разные метки. При вышеописанной кодировке введём $l$ как вектор длины $c$, $l = (l_i)_{i=1}^c$, $i$-я компонента которого $l_i$ равна длине последовательности нулей и единиц, кодирующей метку $i$-го класса. Задача ставится как задача минимизации по возможным способам закодировать метки классов (так, чтобы разные классы имели разные метки) следующего функционала, являющегося математическим ожиданием длины последовательности, представляющей класс случайного объекта:\n",
"$$L = \\sum_{i = 1}^c p_i l_i.$$\n",
"Шеннон показал, что оптимальное значение $L_{opt}$ не может быть меньше, чем $H(p)$. Более того, существуют схемы, позволяющие приблизиться к этому теоретическому минимуму, а именно коды Хаффмана и коды Шеннона-Фано. Таким образом, становится понятно, почему $H(p)$ можно интерпретировать как ожидаемое количество бит информации, ведь в вышеописанной тракторвке это ожидаемая длина битового представления метки класса при оптимальном кодировании меток.\n",
"\n",
"Чтобы понять, как логарифмическая функция потерь связана с энтропией Шеннона, введём понятие кросс-энтропии между двумя задаваемыми векторами $p$ и $q$ вероятностными распределениями на метках классов:\n",
"$$H(p, q) = - \\sum_{i=1}^c p_i \\log_2{q_i}.$$\n",
"Эта величина может восприниматься следующим образом. Допустим, вектор $p$ содержит истинные вероятности классов, но при выборе способа закодировать метки классов думали, что истинные вероятности классов задаются вектором $q$, так что и кодирование получилось оптимальным для $q$. В таком случае $H(p, q)$ задаёт ожидаемое количество бит информации, которую потребуется передать, чтобы с указанным оптимальным для $q$ кодированием сообщить метку класса объекта, пришедшего из распределения, характеризуемого $p$. Только что кросс-энтропия $H(p, q)$ была описана с точки зрения разрастания количества бит, которое потребуется передать, но есть и взгляд с точки зрения потери информации: если разрешено передать лишь столько бит, сколько ровно хватило бы при оптимальном для $p$ кодировании, то при оптимальном для $q$ кодировании часть информации придётся потерять.\n",
"\n",
"Так вот, логарифмическая функция потерь — средняя по выборке кросс-энтропия между распределением, сконцентрированным в истинном классе объекта, и распределением, задаваемым предсказанными для этого объекта вероятностями классов."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"теория_информации"
]
},
"source": [
"## Дивергенция Кульбака-Лейблера\n",
"\n",
"Дивергенция Кульбака-Лейблера — асимметричное \"расстояние\" между двумя вероятностными распределениями. Из-за асимметричности и используется слово \"дивергенция\", а не слово \"расстояние\".\n",
"\n",
"В случае распределений над дискретным множеством $c$ возможных классов любое вероятностное распределение можно представить в виде вектора длины $c$, сумма компонент которого равна 1. Тогда для распределений, характеризуемых векторами $p=(p_i)_{i=1}^c$ и $q=(q_i)_{i=1}^c$, дивергенция Кульбака-Лейблера равна:\n",
"$$D_{KL}\\left(p \\, \\Vert \\, q \\right) = - \\sum_{i=1}^c p_i \\log \\frac{q_i}{p_i}.$$\n",
"\n",
"Смысл так введённой величины становится понятен из следующего соотношения:\n",
"$$D_{KL}\\left(p \\, \\Vert \\, q \\right) = H(p, q) - H(p),$$\n",
"где $H(p, q)$ — кросс-энтропия между распределениями, описываемыми векторами $p$ и $q$, а $H(p)$ — [энтропия Шеннона](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона) распределения, описываемого вектором $p$. Из выписанного равенства следует, что дивергенция Кульбака-Лейблера показывает, чему равно ожидаемое количество \"лишних\" бит, которые потребуется передать для описания исхода, приходящего из распределения, описываемого $p$, если для кодирования исходов была выбрана схема, оптимизированная для распределения, описываемого $q$. Также из выписанного равенства следует, что при использовании в качестве функции потерь дивергенции Кульбака-Лейблера между распределением, сконцентрированным в истинном классе объекта, и предсказанными вероятностями классов, получится то же самое, что получается при использовании логарифмической функции потерь, так как $H(p)$ не зависит от предсказанного $q$.\n",
"\n",
"Свойства дивергенции Кульбака-Лейблера:\n",
"* Неотрицательна: $D_{KL}\\left(p \\, \\Vert \\, q \\right) \\ge 0$, причём равна 0 тогда и только тогда, когда $p = q$ (следует из неравенства Йенсена);\n",
"* С точностью до умножения на константу является предельным элементом параметрического семейства дивергенций Кресси-Рида в пределе при $\\lambda \\to 0$:\n",
"$$D_{KL}\\left(p \\, \\Vert \\, q \\right) = -\\frac{1}{2} \\lim_{\\lambda \\to 0} \\frac{2}{\\lambda(\\lambda + 1)} \\sum_{i=1}^c p_i\\left(\\left(\\frac{p_i}{q_i}\\right)^\\lambda - 1\\right),$$\n",
"следует это из правила Лопиталя. К этому же параметрическому семейству с точностью до умножения на константу принадлежат расстояние Хеллингера и $\\chi^2$-расстояние."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"метрики_качества"
]
},
"source": [
"## Коэффициент детерминации\n",
"\n",
"Коэффициент детерминации $R^2$ тесно связан со среднеквадратичной ошибкой (MSE): $R^2 = 1 - \\frac{\\mathrm{MSE}}{\\mathrm{Var}[y]}$, где запись $\\mathrm{Var}[y]$ обозначает дисперсию целевой переменной. Из выписанной формулы вытекает, что с точки зрения оптимизации $R^2$ и MSE эквивалентны друг другу.\n",
"\n",
"Основное преимущество, благодаря которому смотреть на $R^2$ удобнее, чем на MSE, заключается в том, что он проще в трактовке результатов. Не зная данных, сложно сказать, насколько хорошим или плохим является среднеквадратичная ошибка, равная, скажем, 12. А коэффициент детерминации не может быть больше 1, поэтому можно заранее сказать, что значения, близкие к 1, хороши. Второй опорной точкой является 0: если $R^2 < 0$, то это означает, что предсказания модели отклоняются от фактических значений сильнее, чем фактические значения отклоняются от своего среднего по выборке.\n",
"\n",
"По сути, $R^2$ говорит об отмасштабированной среднеквадратичной ошибке. Можно бы было смотреть на метрику $\\frac{\\mathrm{MSE}}{\\mathrm{Var}[y]}$. Вычитание из единицы этого отношения имеет исторические причины, восходящие к тому, что $R^2$ стал популярен благодаря эконометрике. Эконометристы, как правило, не проводят тестирование на отложенной выборке, потому что им неинтересно предсказание на новых объектах, а интересно объяснение зависимостей в существующей выборке. Если обучать методом наименьших квадратов линейную регрессию со включённой константой, то $R^2$ на обучающей выборке заведомо будет в диапазоне от 0 до 1, и в эконометрическом контексте можно считать, что $R^2$ показывает, какую долю дисперсии целевой переменной удалось отразить в модели.\n",
"\n",
"Наконец, стоит отметить, что с трактовкой значений $R^2$ стоит быть аккуратнее. Например, пусть выборка разнородна и в ней есть объекты двух типов, таких что у каждого типа значения целевой переменной лежат в своём обособленном диапазоне. Тогда $R^2$, подсчитанный на всей выборке, будет выше, чем среднее двух коэффициентов детерминации, подсчитанных каждый только на объектах одного типа. Дело в том, что поменяется знаменатель, ведь дисперсия целевой переменной внутри каждого из двух диапазонов ниже, чем дисперсия целевой переменной, подсчитанная на всех объектах. Подобный эффект может привести к тому, что даже у слабых моделей $R^2$, вычисленный на всей выборке, будет близок к 1. В этом случае высокие значения $R^2$ говорят не о том, что MSE мала, а о том, что MSE мала относительно высокой дисперсии, значительный вклад в которую вносит разнородность выборки."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"метрики_качества"
]
},
"source": [
"## ROC AUC\n",
"\n",
"#### Определение\n",
"\n",
"Метрика ROC AUC применима для моделей бинарной классификации, способных ранжировать объекты по степени своей уверенности в их принадлежности к положительному классу (грубо говоря, предсказывающая вероятности, хотя эти «вероятности» и не обязаны быть [настоящими вероятностями](__home_url__/notes/Калибровка предсказанных вероятностей)).\n",
"\n",
"Название метрики ROC AUC в полном виде звучит как площадь под ROC-кривой (AUC — аббревиатура для \"area under curve\"). Как следует из названия, эта метрика может быть определена через ROC-кривую (где ROC — аббревиатура для \"receiver operating characteristic\").\n",
"\n",
"ROC-кривая рисуется внутри квадрата с вершинами в точках (0, 0), (1, 0), (1, 1) и (0, 1), где по оси абсцисс откладывается доля объектов нулевого класса, ошибочно отнесённых к положительному, а по оси ординат — доля объектов положительного класса, верно отнесённых к нему. Исходно кривая начинает строиться из точки (0, 0), что означает, что для этой точки, какой бы ни была степень уверенности в принадлежности к положительному классу, объект всегда причисляется к нулевому классу. Чтобы построить вторую точку, возьмём наибольшую степень уверенности в принадлежности к положительному классу и все объекты, на которых она была возвращена (как правило, это всего один объект, ведь совпадающие предсказания встречаются редко). Пусть среди этих объектов $m_0$ принадлежало к нулевому классу и $m_1$ принадлежало к положительному классу. Для выборки, на которой измеряется ROC AUC, обозначим общее количество объектов нулевого класса за $n_0$, а общее количество объектов положительного класса — за $n_1$. Тогда вторая точка ROC-кривой имеет координаты ($m_0 / n_0, m_1 / n_1)$. Таким образом, вторая точка соответствует порогу, при котором только объекты с наибольшей степенью уверенности в принадлежности к положительному классу относятся к положительному классу, а остальные приписываются к отрицательному. Далее рассматривается наибольшая из оставшихся степеней уверенности, для неё считаются новые значения $m_0$ и $m_1$, а следующая точка ROC-кривой получается из предыдущей сдвигом на $m_0 / n_0$ по оси абсцисс и сдвигом на $m_1 / n_1$ по оси ординат. Процесс продолжается, пока кривая не придёт в точку (1, 1), соответствующую отнесению всех без исключения объектов к положительному классу. В случае, если совпадающих предсказаний не было, это займёт $n_0 + n_1$ шагов, а, если они были, меньше.\n",
"\n",
"Если любой объект положительного класса имел предсказание выше, чем у любого объекта нулевого класса, ROC-кривая пройдёт через точку (0, 1), а площадь под ней составит 1. Если все объекты имеют одно и то же предсказание, ROC-кривая пройдёт по побочной диагонали квадрата, а площадь под ней составит $1 / 2$, что является наихудшим значением (ведь для значений ниже $1 / 2$ можно перевернуть предсказания). \n",
"\n",
"#### Связь со статистическими тестами\n",
"\n",
"В математической статистике существует непараметрический тест Манна-Уитни(-Уилкоксона) для проверки гипотезы о том, что средние значения признака на объектах из двух разных выборок равны. Статистика для этого теста $U$ является суммой по декартову произведению первой выборки на вторую выборку величины, равной 1, если у объекта из второй выборки признак больше, $1 / 2$, если признаки равны, и 0, если у объекта из первой выборки признак больше.\n",
"\n",
"В качестве первой выборки возьмём объекты нулевого класса из той выборки, на которой считается ROC AUC, в качестве второй выборки возьмём объекты положительного класса оттуда же, а в качестве признака возьмём предсказанные классификатором степени уверенности в принадлежности к положительному классу. Тогда:\n",
"$$\\mathrm{ROC\\_AUC} = \\frac{U}{n_0 n_1}.$$\n",
"Чтобы доказать это, разрежем квадрат со стороной 1, в котором строилась ROC-кривая, на $n_0 n_1$ равных прямоугольников с длиной $1 / n_0$ и высотой $1 / n_1$. Объекты каждого из классов пронумеруем по убыванию предсказаний. Для пары из $i$-го объекта нулевого класса и $j$-го объекта положительного класса рассмотрим соответствующее им слагаемое из опредления $U$. Если оно равно 1, то $(i, j)$-й прямоугольник (если нумеровать их слева направо по оси абсцисс и снизу вверх по оси ординат) целиком лежит под ROC-кривой. Если оно равно 0, то $(i, j)$-й прямоугольник целиком лежит над ROC-кривой. Если оно равно $1 / 2$, то $(i, j)$-й прямоугольник входит в группу прямоугольников, на которых совпадают предсказания, и эту группу прямоугольников ROC-кривая по диагонали делит пополам. Тем самым равенство доказано. \n",
"\n",
"Из этого равенства вытекает полезная интерпретация. ROC AUC оценивает вероятность того, что при равновероятном выборе одного объекта из всех объектов нулевого класса, представленных в выборке, и равновероятном выборе одного объекта из всех объектов положительного класса, представленных в выборке, объект положительного класса получит более высокое предсказание, чем объект отрицательного класса.\n",
"\n",
"#### Свойства\n",
"\n",
"Из предыдущей интерпретации ROC AUC как вероятности следует, что ROC AUC не зависит от баланса классов. Детализация этого утверждения такова: при зафиксированной модели ни сэмплирование новых объектов одного из классов из того же распределения, из какого они были порождены, ни удаление объектов одного из классов с вероятностями, сохраняющими распределение объектов в этом классе, не поменяют математическое ожидание ROC AUC. Если быть ещё более точным, то для этого также необходимо, чтобы $n_0$ и $n_1$ были достаточно велики, дабы диапазон допустимых значений ROC AUC не был слишком дискретным.\n",
"\n",
"Также в отличие от полноты ROC AUC нельзя сделать равной 1, просто приписывая все объекты к положительному классу, а в отличие от точности ROC AUC нельзя сделать равной 1, почти всё кроме очевидно положительных объектов приписывая к нулевому классу.\n",
"\n",
"Однако ROC AUC не всегда является уместной метрикой для оценки качества бинарной классификации. Дело в том, что ROC AUC зависит от ранжирования всей без исключения выборки. Если же стоит задача, имея $n$ объектов, выбрать из них $k$, где $k < n$, так, чтобы среди выбранных было как можно больше объектов положительного класса, то метрика precision@k (возможно, подсчитанная в разбивке на какие-то группы из $n$ объектов и затем усреднённая) более уместна. Все улучшения или ухудшения в ранжировании ниже $k$-й позиции не изменят полезность модели для поставленной задачи, но на ROC AUC в отличие от precision@k они скажутся.\n",
"\n",
"Другим следствием того, что ROC AUC зависит от ранжирования всей выборки (а не лишь интересующей её части), является то, что порой конкретные значения ROC AUC бывают обманчивы. Например, пусть дана выборка, где объекты нулевого класса разнородны: часть из них модель всегда ранжирует ниже всех объектов положительного класса, а часть не отличает от объектов положительного класса (т.е. ранжирует вперемежку с ними). Чем выше доля той части, которую модель ранжирует максимально низко, тем выше ROC AUC. Иными словами, ROC AUC можно сколь угодно приближать к 1, включая в выборку объекты, для которых даже без машинного обучения очевиден их класс. И это не противоречит тому, что ROC AUC не зависит от баланса классов: описанное изменение ROC AUC вызывается не изменением баланса классов, а изменением структуры класса, куда добавляют очевидные объекты."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"интерпретируемость"
]
},
"source": [
"## Регрессионные значения Шэпли и SHAP-значения\n",
"\n",
"#### Постановка задачи\n",
"\n",
"Рассмотрим задачу объяснения предсказания обученной модели на каком-то конкретном объекте. Допустим, хочется получить результат в следующем виде:\n",
"$$\\hat{y} = \\phi_0 + \\sum_{i=1}^n \\phi_i,$$\n",
"где:\n",
"* $\\hat{y}$ — предсказание модели на выбранном объекте (для краткости индекс объекта здесь и далее опущен),\n",
"* $\\phi_0$ — некоторое базовое предсказание, не зависящее от признаков (например, для регрессии, обучаемой с MSE в качестве функции потерь, это может быть среднее значение целевой переменной на обучающей выборке, а для классификации, обучаемой с логарифмической функцией потерь, это может быть вектор долей классов в обучающей выборке),\n",
"* $\\phi_i$ — вклад $i$-го признака в предсказание модели на рассматриваемом объекте, этот вклад требуется каким-то образом найти,\n",
"* $n$ — количество признаков, используемых моделью.\n",
"\n",
"#### Регрессионные значения Шэпли\n",
"\n",
"Для сформулированной выше задачи можно в качестве стартовой точки предложить следующую попытку решения. Обучим модель, во всём аналогичную исходной модели кроме того, что $i$-й признак не использовался, и положим $\\phi_i = \\hat{y} - \\hat{y}_{\\backslash i}$, где $\\hat{y}_{\\backslash i}$ — предсказание модели, обученной на всех признаках кроме $i$-го. Однако у этого способа есть существенные недостатки. Во-первых, нет никаких гарантий, что будет соблюдаться желаемое условие $\\hat{y} = \\phi_0 + \\sum_{i=1}^n \\phi_i$. Во-вторых, интерпретация полученных величин вызывает вопросы: например, сильный признак, такой что информация, содержащаяся в нём, косвенно отражена и в других признаках, может получить маленький по модулю $\\phi_i$, но, казалось бы, модуль $\\phi_i$ должен быть большим, раз признак сильный.\n",
"\n",
"Разовьём предыдущую попытку путём обобщения. Расставим все признаки в каком-то произвольном порядке и обозначим за $P$ множество всех признаков, которые при таком упорядочивании оказались перед $i$-м признаком. Тогда решение определим так: $\\phi_i = \\hat{y}_{P \\cup \\{i\\}} - \\hat{y}_P$, где $\\hat{y}_P$ — предсказание модели, обученной на всех признаках, принадлежащих $P$ (если $P = \\emptyset$, то $\\hat{y}_P = \\phi_0$), а $\\hat{y}_{P \\cup \\{i\\}}$ — предсказание модели, обученной на $i$-м признаке и на всех признаках, принадлежащих $P$. Отметим три момента:\n",
"* если упорядочивание признаков зафиксировать для всех $i$, то условие $\\hat{y} = \\phi_0 + \\sum_{i=1}^n \\phi_i$ будет соблюдаться;\n",
"* для признака, оказавшегося последним, получится то же самое, что получилось бы при первом способе;\n",
"* недостатком является то, что результат зависит от упорядочивания признаков, а оно, как отмечалось выше, берётся произвольно.\n",
"\n",
"Устраним имеющийся недостаток за счёт усреднения по всем возможным упорядочиваниям множества из $n$ признаков. Обозначим за $N_{\\backslash i}$ множество всех подмножеств множества исходных признаков, таких что $i$-й признак в них не входит. Тогда определим искомые вклады признаков так:\n",
"$$\\phi_i = \\sum_{S \\in N_{\\backslash i}} \\frac{(\\vert S \\vert)! (n - \\vert S \\vert - 1)!}{n!} (\\hat{y}_{S \\cup \\{i\\}} - \\hat{y}_S),$$\n",
"где множитель перед разностью показывает для каждого конкретного подмножества $S$, какую долю из всех $n!$ упорядочиваний $n$ признаков составляют такие, где на первых $\\vert S \\vert$ позициях стоят признаки из $S$, а на $(\\vert S \\vert + 1)$-й позиции стоит $i$-й признак.\n",
"\n",
"В [литературе](http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf) доказывается, что предложенный способ определить вклады признаков в предсказание на конкретном объекте является единственным способом, удовлятворяющим ряду естественных условий. При этом впервые это было доказано не в контексте машинного обучения, а в контексте теории игр (грубо говоря, решалась [задача](https://en.wikipedia.org/wiki/Shapley_value) о том, как разделить награду за результат между нескольким участникам одной команды), и по имени экономиста, доказавшего это, такие коэффициенты $\\phi_i$ называют регрессионными значениями Шэпли.\n",
"\n",
"#### SHAP-значения\n",
"\n",
"Теоретически регрессионные значения Шэпли решают поставленную задачу, но на практике их вычисление может оказаться вычислительно неподъёмным. Модель потребуется обучать $O(n!)$ раз, что при хоть сколько-нибудь больших $n$ затратно.\n",
"\n",
"Для получения результата за разумное время используют приближения к регрессионным значениям Шэпли. Тут можно применить несколько приёмов:\n",
"* Оценить сумму из формулы для $\\phi_i$ лишь по части слагаемых.\n",
"* Заменить многократное обучение модели на усреднение по различным вариантам исключённых признаков. Делается это так. Берётся только исходная модель (обученная на всех признаках). Её предсказание в случае исключения каких-либо признаков определяется как среднее по обучающей выборке её предсказаний на синтетических объектах, оставленные признаки которых равны оставленным признакам того исходного объекта, для которого ищется вклад признаков, а исключённые признаки равны исключённым признакам какого-либо объекта из обучающей выборки. Преимуществом этого приёма является то, что устраняется влияние случайности на обучение разных моделей.\n",
"* В предыдущем приёме можно усреднять не по всей обучающей выборке, а лишь по её случайному подмножеству.\n",
"* Если речь идёт о некоторой конкретной модели (например, об ансамбле деревьев или нейронной сети), можно использовать и какие-то специфичные для этой модели техники (наподобие DeepLIFT).\n",
"\n",
"Инструмент, объединяющий различные способы приближённо вычислить регрессионные значения Шэпли, назван [SHAP](https://github.com/slundberg/shap). Возвращаемые им вклады признаков в предсказание модели на некотором объекте называют SHAP-значениями."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"метрики_качества",
"ранжирование"
]
},
"source": [
"## Метрики качества ранжирования\n",
"\n",
"#### Введение\n",
"\n",
"Назовём группой множество объектов, таких что их надо отранжировать (представить в виде упорядоченного списка), а в рамках одной группы $i$-й объект имеет некоторую неотрицательную полезность $u_i$ (при этом в другой группе этот же объект может иметь иную полезность). Например, группу могут образовывать ссылки на сайты, найденные по какому-либо поисковому запросу пользователя. Тогда полезности $u_i$ будут зависеть, с одной стороны, от степени соответствия сайта запросу, а, с другой стороны, от степени соответствия сайта пользователю и истории его действий.\n",
"\n",
"Пусть есть некоторая модель ранжирования, а требуется оценить её качество на множестве групп. Стандартная процедура выглядит так: каждая группа ранжируется отдельно, для получившихся ранжирований вычисляется какая-либо метрика качества, а затем результаты агрегируются по всем группам (например, берётся среднее или взвешенное среднее).\n",
"\n",
"#### Метрики для бинарной полезности\n",
"\n",
"Если в каждой группе объекты бывают двух классов, нулевого и положительного, то для оценки качества ранжирования могут использоваться:\n",
"* [ROC AUC](__home_url__/notes/ROC AUC), усреднённая по группам,\n",
"* средний обратный ранг (MRR, Mean Reciprocal Rank) — для каждой группы вычисляется отношение единицы к рангу (т.е. позиции) первого положительного примера в ней, а от полученных отношений берётся среднее,\n",
"* «средняя усреднённая точность» (MAP, Mean Average Precision) — для каждой группы вычисляется усреднённая точность, а именно среднее по всем объектам положительного класса точностей, получающихся при проведении границы между классами сразу же после позиции, на которой стоит соответствующий объект положительного класса:\n",
"$$\\mathrm{AP} = \\frac{\\sum_{i=1}^{\\vert g \\vert} \\left( \\frac{1}{i} \\sum_{j=1}^i u_j \\right) u_i}{\\sum_{i=1}^{\\vert g \\vert} u_i},$$\n",
"где индексы $i$ и $j$ проходят через объекты в том же порядке, в каком объекты отранжированы, $\\vert g \\vert$ — размер группы, а $u_i \\in \\{0, 1\\}$ — бинарная полезность $i$-го объекта.\n",
"\n",
"#### DCG и NDCG\n",
"\n",
"Определим DCG (Discounted Cumulative Gain, дисконтированный совокупный выигрыш) так:\n",
"$$\\mathrm{DCG} = \\sum_{i=1}^t \\frac{f(u_i)}{\\log_2(i+1)},$$\n",
"где нумерация объектов идёт в том же порядке, в каком они отранжированы, $t$ — порог, который можно или положить равным количеству объектов в группе, или подобрать на основании представлений о предметной области (скажем, приравнять его к количеству ссылок на первой странице поисковой выдачи), а $f$ — некоторая неубывающая функция. В качестве $f$, как правило, берут или тождественную функцию, или функцию $f(u_i) = 2^{u_i} - 1$.\n",
"\n",
"DCG предполагает, что наиболее полезные объекты должны быть показаны как можно выше, и это обеспечивается за счёт двух механик:\n",
"* отсечение: если объект не вошёл в первые $t$ объектов, его полезность не будет учтена,\n",
"* дисконтирование: чем больше $i$ (позиция объекта), тем выше знаменатель $\\log_2(i+1)$.\n",
"\n",
"У DCG есть тот недостаток, что по конкретному его значению, не зная деталей задачи, нельзя сказать, насколько хорошо ранжирование. К тому же, если порог $t$ меняется от группы к группе (например, потому что меняются размеры групп), агрегация отдельных DCG в общую для всех групп метрику качества может оказаться лишённой смысла. Эти недостатки исправлены в метрике под названием NDCG (Normalized DCG, отнормированный дисконтированный совокупный выигрыш). Определим IDCG (Ideal DCG, идеальный DCG) как DCG, получающийся при ранжировании по убыванию полезностей объектов. Тогда:\n",
"$$\\mathrm{NDCG} = \\frac{\\mathrm{DCG}}{\\mathrm{IDCG}}.$$\n",
"NDCG всегда лежит на отрезке от 0 до 1 и его корректно усреднять по группам, чтобы получить значение метрики на множестве интересующих групп.\n",
"\n",
"#### ERR\n",
"\n",
"У MRR есть обобщение, применимое в том числе тогда, когда полезности $u_i$ не являются бинарными. Называется оно ожидаемый обратный ранг (ERR, Expected Reciprocal Rank). Эта метрика предполагает, что осуществляется проход по отранжированному списку объектов группы и с вероятностью $p(u_i)$ выбирается $i$-й объект (после чего процесс останавливается). ERR равен математическому ожиданию величины $1 / i$, то есть:\n",
"$$\\mathrm{ERR} = \\sum_{i=1}^{\\vert g \\vert} \\frac{1}{i} \\left(p(u_i) \\prod_{j=1}^{i-1} (1 - p(u_j))\\right),$$\n",
"где $\\vert g \\vert$ — размер группы, а выражение в скобках интерпретируется как вероятность того, что процесс остановится на $i$-м объекте, то есть не будет выбран ни один из первых $(i-1)$ объектов, но будет выбран $i$-й объект.\n",
"\n",
"В оригинальной статье [Chapelle et al., 2009](https://www.researchgate.net/publication/220269787_Expected_reciprocal_rank_for_graded_relevance) полезности отображались в вероятности выбора объекта так:\n",
"$$p(u_i) = \\frac{2^{u_i} - 1}{2^{\\max_j u_j}}.$$\n",
"\n",
"#### pFound\n",
"\n",
"Метрика pFound похожа на ERR тем, что тоже опирается на модель процесса, в котором происходит проход по отранжированному списку объектов группы. Однако теперь у этого процесса есть три варианта того, что может произойти после $i$-го объекта:\n",
"* процесс продолжается и переходит к $(i+1)$-му объекту,\n",
"* $i$-й объект может быть выбран как подходящий (и на этом процесс завершается),\n",
"* процесс оканчивается неуспехом; вероятность этого не зависит от $i$ и равна фиксированной константе $p_\\mathrm{break}$.\n",
"\n",
"Как это заложено в названии, pFound равняется вероятности того, что процесс завершится выбором какого-либо объекта. Верхнеуровнево данная вероятность выражается так:\n",
"$$\\mathrm{pFound} = \\sum_{i=1}^{\\vert g \\vert} p_\\mathrm{look}(i) p_\\mathrm{rel}(i),$$\n",
"где $p_\\mathrm{look}(i)$ — вероятность дойти до $i$-го объекта, а $p_\\mathrm{rel}(i)$ — вероятность того, что процесс завершится на $i$-м объекте (при условии, что до него дошли). Что касается первой из этих вероятностей, по построению процесса она равна:\n",
"$$p_\\mathrm{look}(i) = p_\\mathrm{look}(i - 1) (1 - p_\\mathrm{rel}(i - 1))(1 - p_\\mathrm{break}).$$\n",
"В качестве $p_\\mathrm{rel}(i)$ можно использовать любую неубывающую функцию, отображающую все $u_i$ на отрезок от 0 до 1. В частности, это может быть:\n",
"* $p_\\mathrm{rel}(i) = u_i / \\max_j u_j$,\n",
"* $p_\\mathrm{rel}(i) = 2^{u_i / \\max_j u_j} - 1$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"ранжирование",
"постановка_задачи",
"функции_потерь"
]
},
"source": [
"## RankNet, LambdaRank и YetiRank\n",
"\n",
"#### RankNet\n",
"\n",
"В задаче ранжирования есть группы объектов, в каждой из которых объекты нужно расположить по порядку. Например, группы могут быть образованы поисковыми запросами, а объектами тогда будут веб-страницы, ссылки на которые в ответ на запрос нужно показать в виде списка. Предположим, что есть обучающее множество групп $G$, где для некоторых пар объектов из одной и той же группы известно, какой из них должен быть отранжирован выше. Такие попарные сравнения не обязаны быть транзитивными: может получиться, что для некой группы объект $a$ предпочтительнее объекта $b$, $b$ предпочтительнее $c$, но $c$ предпочтительнее $a$. На работоспособность RankNet отсутствие транзитивности не влияет.\n",
"\n",
"Пусть есть некоторая параметризованная вектором весов $w$ функция, дифференцируемо зависящая от них (в оригинальной работе бралась нейронная сеть). Эта функция по признакам группы, по признакам $i$-го объекта и ещё каким-либо признакам возвращает вещественную величину $s_i$, а внутри группы ранжирование объектов происходит по убыванию их $s_i$. RankNet настраивает веса $w$ градиентным спуском, а оптимизируемая функция потерь устроена так:\n",
"$$C = \\sum_{g \\in G} \\sum_{(i, j) \\in I_g} -\\log \\sigma\\left(\\kappa(s_i - s_j)\\right),$$\n",
"где $G$ — множество обучающих групп, $I_g$ — множество пар $(i, j)$, таких что в группе $g$ $i$-й объект предпочтительнее $j$-го, $\\sigma$ — сигмоидная функция активации, а $\\kappa$ — вещественный гиперпараметр, задающий масштаб для нелинейности в сигмоиде. Выписанная функция потерь является дифференцируемой [аппроксимацией](__home_url__/notes/Аппроксимация функции потерь) для разрывной функции потерь:\n",
"$$\\tilde{C} = \\sum_{g \\in G} \\sum_{(i, j) \\in I_g} [s_i < s_j],$$\n",
"где квадратные скобки обозначают нотацию Айверсона. Эта разрывная функция потерь $\\tilde{C}$ интерпретируется как количество пар, отранжированных неверно. А исходную функцию потерь $C$ также можно интерпретировать как прологарифмированое правдоподобие попарных предпочтений, если $\\sigma\\left(\\kappa(s_i - s_j)\\right)$ считать предсказанной вероятностью того, что $i$-й объект должен быть отранжирован выше $j$-го в группе $g$.\n",
"\n",
"Помимо дифференцируемости у $C$ есть следующие полезные свойства:\n",
"* при $s_i = s_j$ она не обращается в 0 и тем самым требует обеспечения зазора между $s_i$ и $s_j$,\n",
"* при $s_i \\gg s_j$ её градиент обнуляется, то есть её нельзя минимизировать, бесконечно накручивая уверенность на одних и тех же парах,\n",
"* при $s_i \\ll s_j$ градиент постоянен, то есть невозможно такое, что по каким-либо причинам обучение на одной из пар застрянет в области без градиента.\n",
"\n",
"По сути, на RankNet можно смотреть не только как на метод ранжирования, но и как на постановку задачи ранжирования с попарной функцией потерь.\n",
"\n",
"#### Ускорение обучения RankNet\n",
"\n",
"При выполнении градиентного спуска для обучения весов $w$ можно выполнять меньше действий, если результаты повторяющихся вычислений помещать в специальные переменные и переиспользовать их значения.\n",
"\n",
"Убедимся в этом на примере $k$-й компоненты вектора градиента $C$ по $w$ (здесь внешнее суммирование делается по всему $G$ как при классическом градиентном спуске):\n",
"$$\\frac{\\partial C}{\\partial w_k} = \\sum_{g \\in G} \\sum_{(i, j) \\in I_g} \\frac{\\partial C}{\\partial (s_i - s_j)} \\frac{\\partial (s_i - s_j)}{\\partial w_k} = \\sum_{g \\in G} \\sum_{(i, j) \\in I_g} \\frac{\\partial C}{\\partial (s_i - s_j)} \\left(\\frac{\\partial s_i}{\\partial w_k} - \\frac{\\partial s_j}{\\partial w_k}\\right) = \\sum_{g \\in G} \\sum_{(i, j) \\in I_g} \\lambda_{ij} \\left(\\frac{\\partial s_i}{\\partial w_k} - \\frac{\\partial s_j}{\\partial w_k}\\right),$$\n",
"где в последнем равенстве было введено обозначение:\n",
"$$\\lambda_{ij} = \\frac{\\partial C}{\\partial (s_i - s_j)}.$$\n",
"Тогда суммарно на всей группе $g$ вклад в $k$-ю компоненту градиента $C$ по $w$ составит:\n",
"$$\\sum_{i} \\lambda_i \\frac{\\partial s_i}{\\partial w_k},$$\n",
"где теперь суммирование проводится по всем объектам группы, а ещё добавилось обозначение:\n",
"$$\\lambda_i = \\sum_{\\iota: (i, \\iota) \\in I_g} \\lambda_{i\\iota} - \\sum_{\\iota: (\\iota, i) \\in I_g} \\lambda_{i\\iota}.$$\n",
"Выигрыш в производительности заключается в том, что достаточно один раз на всей группе $g$ вычислить $\\lambda_{i}$, а потом использовать их при подсчёте градиента.\n",
"\n",
"Дополнительно распишем, как вычислять $\\lambda_{ij}$. Вспомним следующие известные равенства:\n",
"$$\\log(x)^\\prime = \\frac{1}{x},$$\n",
"$$\\sigma^\\prime(x) = \\sigma(x)(1 - \\sigma(x)),$$\n",
"$$1 - \\sigma(x) = \\sigma(-x).$$\n",
"Благодаря им и формуле для производной композиции функций получаем:\n",
"$$\\lambda_{ij} = -\\kappa \\sigma\\left(\\kappa(s_j - s_i)\\right).$$\n",
"\n",
"#### LambdaRank\n",
"\n",
"Как ранее обсуждалось, RankNet неявно предполагает, что целью является минимизация количества пар, отранжированных неправильно. Подобное предположение не подходит для многих прикладных задач. Например, в информационном поиске важнее всего качество первых $n$ элементов поисковой выдачи, а порядок не попавших в топ-$n$ документов не имеет значения. Именно поэтому у RankNet появилась усовершенствованная версия под названием LambdaRank. Она является эвристическим способом оптимизировать различные [метрики качества ранжирования](__home_url__/notes/Метрики качества ранжирования).\n",
"\n",
"Определённости ради остановимся на NDCG, потому что эмпирически подтверждено, что для него эвристика LambdaRank работает. Правда, в отличие от функций потерь NDCG надо максимизировать, поэтому его правильнее называть функцией полезности. Так вот, рассмотрим градиентный спуск, в котором почему-то по-другому определены $\\lambda_{ij}$:\n",
"$$\\lambda_{ij} = \\frac{\\partial C}{\\partial (s_i - s_j)} \\vert \\Delta_{ij}(\\mathrm{NDCG}) \\vert,$$\n",
"где $\\Delta_{ij}(\\mathrm{NDCG})$ — изменение в NDCG, которое произойдёт, если в отранжированной по убыванию $s_i$ группе переставить местами $i$-й и $j$-й объекты (в исходной нумерации, не зависящей от того, как они ранжируются), а модуль от него берётся, чтобы сохранилось свойство $\\lambda_{ij} = -\\lambda_{ji}$. Получающийся с такими лямбдами градиент мог бы соответствовать дифференцируемой аппроксимации NDCG, но для работы LambdaRank не нужна явная функция потерь или полезности, а достаточно лишь иметь её градиент.\n",
"\n",
"#### YetiRank\n",
"\n",
"В статье [Lyzhin et al., 2022](https://arxiv.org/pdf/2204.01500.pdf) отмечается, что у LambdaRank есть два потенциально слабых места:\n",
"* $\\Delta_{ij}(\\mathrm{NDCG})$ может сильно измениться при небольших изменениях вектора $s$;\n",
"* ненулевые $\\lambda_{ij}$ есть и у таких пар, которые за одно обновление весов градиентным спуском не переставить местами, из-за чего градиент искажается смещением в сторону того, что быстро не изменить.\n",
"\n",
"Чтобы побороть первую проблему, было предложено вектор $s$ складывать со случайным шумом, а потом усреднять результаты по нескольким реализациям этого шума. Так при близких $s_i$ и $s_j$ в части случаев будет выше отранжирован $i$-й объект, а в части — $j$-й, и это сгладит резкий скачок при изменении знака разности между $s_i$ и $s_j$.\n",
"\n",
"Чтобы побороть вторую проблему, $\\lambda_{ij}$ полагаются равными 0 всегда за исключением тех случаев, когда при ранжировании по зашумлённому $s$ $i$-й и $j$-й объекты находятся на соседних позициях.\n",
"\n",
"Получившаяся функция потерь называется YetiLoss, а алгоритм, оптимизирующий её — YetiRank."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"функции_потерь",
"ранжирование"
]
},
"source": [
"## Посписочные функции потерь\n",
"\n",
"#### Введение\n",
"\n",
"Выборка для обучения ранжирующей модели может быть составлена не только из независимых друг от друга объектов (как это в идеале должно быть в задачах регрессии и классификации). Порой естественным образом объекты разбиваются на группы, внутри которых объекты зависимы, а ранжирование нужно только в пределах каждой из групп. Например, если пользователь листает ленту в социальной сети и какие-то элементы пропускает, а на какие-то кликает, то группой можно считать один заход пользователя в ленту, а отранжировать элементы хочется так, чтобы кликнутые элементы были сверху.\n",
"\n",
"Если функция потерь для задачи ранжирования зависит от порядка всех объектов группы, она называется посписочной или погрупповой. В противовес им существуют поточечные функции потерь (то есть функции потерь для регрессии или классификации) и попарные функции потерь (то есть функции потерь, вычисляемые на некоторых парах объектов из одной и той же группы).\n",
"\n",
"Далее все формулы будут приводиться для одной группы размера $\\vert g \\vert$, целевая переменная на $i$-м объекте которой будет обозначаться как $y_i$, а предсказание модели — как $s_i$. На всякий случай напомним, что по убыванию этих предсказаний и делается ранжирование.\n",
"\n",
"#### Модификации поточечных функций потерь\n",
"\n",
"Из поточечной MSE можно сделать посписочную функцию, в [документации CatBoost'а](https://catboost.ai/en/docs/concepts/loss-functions-ranking#QueryRMSE) называемую QueryMSE:\n",
"$$\\mathrm{QueryMSE}(y, s) = \\frac{1}{\\vert g \\vert} \\sum_{i=1}^{\\vert g \\vert} \\left(y_i - s_i - \\frac{1}{\\vert g \\vert}\\sum_{j=1}^{\\vert g \\vert} (y_j - s_j)\\right)^2.$$\n",
"По сравнению с MSE в выражении, возводимом в квадрат, добавилось ещё одно вычитаемое, интерпретируемое как среднее по группе отличие $y_j$ от $s_j$. Можно считать, что каждое $s_i$ увеличили на него. Если бы для каждой группы разрешили все предсказания сдвинуть на какую-то константу, индивидуально подобранную под эту группу, то для минимизации MSE ровно так и надо было бы сдвигать $s_i$. Тем самым QueryMSE убирает присущую MSE чувствительность к сдвигам всех предсказаний из одной группы на одну и ту же величину. Поскольку подобные сдвиги не меняют порядок объектов, чувствительность к ним с точки зрения ранжирования не нужна, а её устранение перенаправляет оптимизацию в сторону расстановки $s_i$ друг относительно друга.\n",
"\n",
"Впрочем, за это приходится платить потерей физического смысла $s_i$. Эти предсказания больше не являются оценкой целевой переменной. Если на этапе обучения можно вычислить сдвиг, после которого они ей станут, то на этапе применения этот сдвиг взять неоткуда.\n",
"\n",
"Для бинарной классификации вариантов, как устранить чувствительность [логарифмической функции потерь](__home_url__/notes/Логарифмическая функция потерь и энтропия Шеннона) к сдвигам, сразу два. Их оба объединяет то, что модель в качестве $s_i$ должна возвращать «логиты», то есть сырые значения без попыток уложить их в диапазон от 0 до 1. Отличаются же они способом, которым из $s_i$ получается вероятность принадлежности $i$-го объекта к положительному классу.\n",
"\n",
"Первый способ предполагает, что делается это по такой формуле:\n",
"$$\\hat{y}_i = \\sigma(s_i + k) = \\frac{1}{1 + e^{-(s_i + k)}},$$\n",
"где $k$ — сдвиг, подбираемый для каждой группы индивидуально исходя из минимизации логарифмической функции потерь. В отличие от случая с MSE здесь не получается выписать аналитическое выражение для $k$ и его нужно искать численными методами.\n",
"\n",
"Второй способ использует такую формулу:\n",
"$$\\hat{y}_i = \\mathrm{softmax}(s)_i = \\frac{e^{s_i}}{\\sum_{j=1}^{\\vert g \\vert} e^{s_j}}.$$\n",
"\n",
"Вне зависимости от выбранного способа далее $\\hat{y}_i$ подставляются в формулу логарифмической функции потерь:\n",
"$$\\mathrm{LogLoss}(y, \\hat{y}) = - \\frac{1}{\\vert g \\vert} \\sum_{i=1}^{\\vert g \\vert} \\left( y_i \\log \\hat{y}_i + (1 - y_i) \\log (1 - \\hat{y}_i) \\right).$$\n",
"\n",
"По-хорошему, обе этих модификации логарифмической функции потерь могли бы называться QueryLogLoss, но в документации CatBoost'а первую называют QueryCrossEntropy, а вторую — QuerySoftmax.\n",
"\n",
"В QueryCrossEntropy, как и в QueryMSE, чувствительность к сдвигу устраняется прибавлением ко всем $s_i$ одного и того же $k$. Как следствие, на этапе применения из $s_i$ нельзя получить $\\hat{y}_i$, ведь для новых групп их $k$ неизвестны. Это означает, что опять модель выдаёт лишь сырые предсказания, не поддающиеся калибровке и интерпретации. Более того, по сравнению с QueryMSE появляется ещё такой недостаток (пусть и некритичный), что численный поиск сдвигов $k$ отнимает вычислительные ресурсы. С другой стороны, зато [считается](https://catboost.ai/en/docs/references/querycrossentropy), что QueryCrossEntropy можно складывать с обычной LogLoss, а потом оптимизировать их взвешенную сумму. Это даёт одновременно и преимущества посписочной функции потерь с точки зрения метрик качества ранжирования, и возвращение чувствительности к сдвигу, а с ней и возможности калибровать вероятности вида $\\hat{y}_i = \\sigma(s_i)$.\n",
"\n",
"В QuerySoftmax чувствительность к сдвигу убирается в софтмаксе, и тут никакие переменные $k$ вводить не надо. Если на этапе применения группы примерно такого же размера, что и в обучающей выборке, то можно спокойно вычислять и калибровать $\\hat{y}_i$. Однако на практике на этапе применения группы могут быть сильно больше (скажем, ранжируется 1000 кандидатов, а в обучающую выборку попадут только те из них, до которых пользователь долистает). В отличие от QueryCrossEntropy к QuerySoftmax не очень-то корректно прибавлять LogLoss, потому что тогда будут совсем уж противоречивые определения вероятности принадлежности объекта к положительному классу. Решение проблемы есть в статье [Bai et al., 2023](https://arxiv.org/pdf/2211.01494.pdf), где предлагается в софтмаксе заменить экспоненту на сигмоиду.\n",
"\n",
"#### Гладкие аппроксимации разрывных метрик качества\n",
"\n",
"В статье [Qin et al., 2008](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-164.pdf) предлагается способ приблизить основные [метрики качества ранжирования](__home_url__/notes/Метрики качества ранжирования) дифференцируемыми функциями потерь. Ключевая идея заключается в том, что функция $[x > 0]$ (индикатор того, что $x$ больше 0) может быть аппроксимирована, в частности, логистической функцией $1 / (1 + \\exp(-x / t))$, где $t > 0$ — заранее заданный параметр, называемый температурой.\n",
"\n",
"Позиция $i$-го объекта в группе является разрывной функцией от вектора $s$, и при помощи данной идеи она может быть аппроксимирована так:\n",
"$$\\mathrm{ApproxRank}(s)_i = 1 + \\sum_{j \\ne i} \\frac{1}{1 + \\exp\\left(\\frac{-(s_j - s_i)}{t}\\right)}.$$\n",
"Далее для краткости введём обозначение $\\pi(s)_i = \\mathrm{ApproxRank}(s)_i$, то есть $\\pi$ — отображение из вектора предсказаний в вектор приближённых позиций.\n",
"\n",
"Для тех матрик качества, где вся разрывность возникает только из-за позиции, этого достаточно для определения функций потерь. Так, имеем:\n",
"$$\\mathrm{ApproxNDCG}(y, s) = - \\frac{1}{\\mathrm{IDCG}(y)} \\sum_{i=1}^{\\vert g \\vert} \\frac{f(y_i)}{\\log_2(1 + \\pi(s)_i)},$$\n",
"$$\\mathrm{ApproxMARR}(y, s) = - \\frac{1}{\\sum_{i=1}^{\\vert g \\vert} y_i} \\sum_{i=1}^{\\vert g \\vert} \\frac{1}{\\pi(s)_i} y_i,$$\n",
"где последняя функция потерь предполагает бинарные целевые переменные, а MARR расшифровывается как Mean Average Reciprocal Rank: отличие от MRR в том, что берутся ранги всех объектов положительного класса, а не только одного, отранжированного выше остальных. Множитель $\\frac{1}{\\sum_{i=1}^{\\vert g \\vert} y_i}$ как раз и отвечает за усреднение по ним. А ещё в обеих формулах у правой части изменён знак, потому что NDCG и MARR надо максимизировать, а функции потерь — минимизировать.\n",
"\n",
"Однако в метриках наподобие MAP разрывность также возникает из-за отсечения по какому-либо порогу. Эту разрывность тоже можно апроксимировать логистической функцией со своей температурой $\\tau$. Итого имеем:\n",
"$$\\mathrm{ApproxMAP}(y, s) = - \\frac{1}{\\sum_{i=1}^{\\vert g \\vert} y_i} \\sum_{i=1}^{\\vert g \\vert} \\left(\\frac{y_i}{\\pi(s)_i} + \\sum_{j \\ne i} \\frac{y_i y_j}{\\pi(s)_i} \\frac{1}{1 + \\exp\\left(-(\\pi(s)_i - \\pi(s)_j) / \\tau\\right)}\\right).$$\n",
"Интерпретация тут такая. Сначала, как и ранее, идёт множитель, отвечающий за усреднение по объектам положительного класса. При суммировании по объектам ненулевой вклад внесут только объекты положительного класса, потому что $i$-е слагаемое кратно $y_i$. Если $y_i = 1$, то в выражении под суммой первый член показывает вклад $i$-го объекта в ту точность, которая возникает при проведении границы между классами после позиции $i$-го объекта, а второй член равен вкладу в эту точность тех объектов положительного класса, которые отранжированы выше $i$-го.\n",
"\n",
"Какая бы метрика ни приближалась, недостаток этого подхода в том, что чем ниже температура (то есть чем точнее логистическая функция приближает индикаторную функцию), тем больше становится область, в которой градиент логистической функции неинформативен. Таким образом, есть компромисс между несоответствием функции потерь метрике и возможностью успешной оптимизации.\n",
"\n",
"#### Отрицательные прологарифмированные правдоподобия\n",
"\n",
"Как известно, логарифмическая функция потерь с точностью до константы является логарифмом правдоподобия обучающей выборки относительно распределения, задаваемого предсказанными вероятностями. В задаче ранжирования тоже бывают функции потерь, являющиеся прологарифмированным правдоподобием: на этот раз — идеального ранжирования относительно некого распределения, параметризованного вектором предсказаний $s$. Более того, в отличие от логарифмической функции потерь эти функции потерь работают не только с бинарными целевыми переменными.\n",
"\n",
"Если ранее в этой заметке индексация объектов была произвольной, теперь под $i$-м объектом будем иметь в виду объект, занимающий $i$-ю позицию в идеальном ранжировании. Если у нескольких объектов одинаковые целевые переменные, позиции между ними распределяются случайно. Более того, некоторые программные реализации даже [не фиксируют](https://www.tensorflow.org/ranking/api_docs/python/tfr/keras/losses/ListMLELoss) зерно случайности, так что значение функции потерь может меняться при неизменных входах.\n",
"\n",
"В качестве правдоподобия можно взять вероятность идеального ранжирования при сэмплировании из распределения Плакетта-Льюса:\n",
"$$\\mathbb{P}(y \\vert s) = \\prod_{i=1}^{\\vert g \\vert} \\mathrm{softmax}(s)_i = \\prod_{i=1}^{\\vert g \\vert} \\frac{\\exp(s_i)}{\\sum_{j=i}^{\\vert g \\vert} \\exp(s_j)}.$$\n",
"Из этой формулы можно увидеть интерпретацию распределения Плакетта-Льюса. На каждую текущую позицию ставится объект, просэмплированный из категориального распределения над ещё не выбранными объектами группы, где вероятности задаются применением софтмакса к тем компонентам вектора $s$, которые соответствуют этим объектам.\n",
"\n",
"Функция потерь под названием ListMLELoss в таком случае принимает вид:\n",
"$$\\mathrm{ListMLELoss}(y, s) = -\\log \\mathbb{P}(y \\vert s).$$"
]
}
],
"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
}