Эта статья хочет поделиться с вами документом «Одномерная граница площади при ROC».

Эта статья была впервые опубликована в общедоступном аккаунте «Code Farmer Training Factory». Я заинтересован в том, чтобы делиться машинным обучением, рекомендательными системами, интеллектуальным анализом данных, документами и технологиями глубокого обучения. Добро пожаловать, обратите внимание!

Уровень этого предложения все еще ограничен, пожалуйста, потерпите меня, любая форма обсуждения очень приветствуется, и каждый может учиться и добиваться прогресса вместе. Кодировать слова непросто, если вам понравилось, ставьте лайк, добавляйте в закладки и пересылайте три раза подряд!

Краб Краб всеобщей поддержки, приглашаем всех обратить внимание, вперед, поделиться три подряд!

Если вам нужно загрузить оригинальную статью, вы можете подписаться на официальный аккаунт, ответить «UBAUC» в фоновом режиме и загрузить статью!

Abstract & Intro

Площадь под ROC (AUC) является важным показателем для задач бинарной классификации и двудольного ранжирования. Однако сложно использовать AUC в качестве цели обучения для прямой оптимизации (потери 0-1 дискретны), поэтому большинство существующих алгоритмов оптимизируются на основе суррогатных потерь для AUC.Существенным недостатком суррогатных потерь является то, что они требуют попарного сравнения обучающих данных, что приводит к медленному времени выполнения и увеличению объема локального хранилища для онлайн-обучения.В этой статье предлагается новая суррогатная потеря, основанная на риске AUC, которая не требует попарных сравнений, но все же может ранжировать прогнозы. Далее авторы демонстрируют, что операции сортировки можно избежать, а цель обучения, основанная на этом суррогате, имеет линейную сложность как во времени, так и в хранении. Наконец, эксперименты подтверждают эффективность суррогатного онлайн-алгоритма оптимизации AUC на основе потерь и пакетного алгоритма.

Problem Definition

$\{(x_i,y_i)\}_{i=1}^N$, для образца,$y_i \in \{-1, +1\}$для этикетки,$x_i \in \mathcal{R}^d$.$\mathcal{I}^+=\{i|y_i=+1\}, \mathcal{I}^-=\{i|y_i=-1\}$— индексы положительных и отрицательных выборок соответственно, где$N^+=|\mathcal{I}^+|,N^-=|\mathcal{I}^-|, N^+ + N^- = N$. определить индикаторную функцию$\textbf{I}: \textbf{I}_a=1$, возвращает 1 для истинного и 0 для ложного. Бинарный классификатор:$c_{w,\theta}: \mathcal{R}^d \mapsto \{-1, +1\}$:

$f_w: \mathcal{R}^d \mapsto \mathcal{R},w$параметр,$\theta$является прогнозируемым порогом.

сделать$c_i=f_w(x_i)$- оценка прогноза i-й выборки, аПредположим, что ни один из предсказанных результатов не является точно равным.

для порога$\theta$, отрицательные образцы, прогнозируемое значение которых превышает пороговое значение, являются ложными положительными результатами, которые рассчитываются следующим образом:Точно так же порог положительного образца выше, чем$\theta$является истинно положительным, рассчитывается следующим образом:Риск AUC определяется следующим образом:Видно, что AUC — это потеря рассогласования положительных и отрицательных образцов, то есть ранжирование положительных образцов ниже, чем у отрицательных. так$L_{AUC}=0$Это идеальный порядок!$L_{AUC}$и$\theta$Независимый.

Method

AUC Risk Without Pairwise Comparison

сделать$(c_1^\uparrow, c_2^\uparrow,\dots,c_N^\uparrow)$за$(c_1, c_2,\dots,c_N)$отсортированы по возрастанию, т.е.$c_1^\uparrow<c_2^\uparrow<\dots<c_N^\uparrow$,сделать $r_i$– позиция i-го положительного образца в отсортированном списке;$c_i^{\uparrow+}$Список после сортировки по i-му положительному образцу$(c_1^\uparrow, c_2^\uparrow,\dots,c_N^\uparrow)$Соответствующий балл в , а именно:$c_i^{\uparrow+}=c_{r_i^+}^{\uparrow+}$.

Предполагается на приведенном выше рисунке$N^+=7,N^-=6, (r_1^+, r_2^+,r_3^+,r_4^+,r_5^+,r_6^+,r_7^+)=(4, 6, 7, 8, 9, 11, 13)$, второй положительный образец, обведенный кружком, стоит перед двумя отрицательными образцами, поэтому его вклад в риск AUC составляет:$N^-+i-r_i^+$.И так далее, для всех положительных и отрицательных образцов в шахматном порядке имеем:$3+2+2+2+2+1+0 = 12$,AUC risk =$\frac{12}{6 \times 7} =\frac{2}{7}$, что согласуется с тем, что было введено ранее.

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

Теорема 2:Когда нет ничьей для прогнозов на тренировочном наборе:

доказывать: учитывать$r_i^+$, рейтинг отрицательных выборок ниже, чем$i$Количество положительных образцов равно$r_i^+-i$,То есть есть$N^- + i - r_i^+$отрицательные образцы оцениваются выше, чем он (что приводит к неуместной паре). Суммирование всех расположенных в шахматном порядке пар дает указанный выше результат.

$\sum_{i=1}^{N^+} (N^- + i)$Сортировка по величине в списке для оценки прогнозов$N^+$Нижний индекс значения,$\sum_{i=1}^{N^+}r_i^+$— индекс положительного образца в отсортированном списке. следовательно,Риск AUC, определенный в уравнении (2), пропорционален разнице между двумя суммами.

Univariate Bound on AUC risk

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

По формуле (2) можно получить новую отсортированную оценку предсказания.$(c_1^\uparrow, c_2^\uparrow,\dots,c_N^\uparrow)$Альтернативная потеря риска AUC:

$\tilde{L}$неотрицательно, потому что второй член всегда меньше или равен первому члену

Computing $\tilde{L}$ without Explicit Ranking

Уравнение (3) требует сортировки, которая по-прежнему является трудоемкой операцией.Согласно следующей теореме 3 мы можем найти эквивалентную форму (3) без сортировки.

Теорема 3: Для$N$вещественные числа$z_1<\dots<z_N$, задача суммы вершин k может быть эквивалентна:где оптимальные параметры$\lambda^*$удовлетворить$z_{N-k} \le \lambda^* \le z_{N-k+1}$

доказывать: Сначала нам нужно знать,$\sum_{N-k+1}^Nz_i$является решением следующей задачи линейного программирования:Соответствующее уравнение Лагранжа:в$a\ge 0,b \ge 0$,$\lambda$есть множитель Лагранжа. будет около$L$частная производная от$p$установить как$0$,Ты можешь иметь:, Применяя уравнение (13), можно получить двойственное уравнение (12):Ограничение формулы (14) говорит нам, что:, при установлении знака равенства целевая функция принимает минимальное значение.Переставьте его, чтобы получить (4). Идем дальше, когда мы выбираем$\lambda^*$удовлетворить$z_{N-k} \le \lambda^* \le z_{N-k+1}$,У нас есть:

$$k\lambda^* + \sum_{i=1}^N [z_i - \lambda^*]_+ = k \lambda^* + \sum_{i=N-k+1}^N (z_i - \lambda^*) = \sum_{i=N-k+1}^N z_i$$

Согласно теореме (3), уравнение (3) можно записать в следующем виде:

что далее переводится как:

По свойствам шарнирных потерь$[a]_+ -a = [-a]_+$:

Итак, исходя из$\tilde{L}$Регрессия численной модели , сформированная целевая функция: В формуле (5) вспомогательная переменная$\lambda$Его можно понимать как порог, разделяющий две категории, и, как и исходное определение риска AUC,$\tilde{L}(w)$Выбор порога независим, если взять общее минимальное значение из всех возможных значений порога.

$\tilde{L}(w)$Интуитивное объяснение дается в контексте бинарной классификации, которая наказывает только те положительные примеры, предсказанное значение которых ниже порога, т.е.$[\lambda - f_w(x_i)]_+$, а предсказание отрицательной выборки больше порогового значения$[f_w(x_i) - \lambda]_+$. Кроме того, согласно лемме 3 оптимальная$\lambda^* \in [c_{N^+}^\uparrow, c_{N^++1}^\uparrow)$

Relation with SVM Objective

Внимательные студенты могут обнаружить, что когда функция предсказания является линейной$f_w(x) = w^Tx$, $\tilde{L}(w)$Существует сильное сходство с целевой функцией SVM.

Восстановленная функция потерь SVM: Классификатор в SVM обычно$w^\top x + b$, здесь член смещения установлен отрицательным для удобства сравнения. Если порог$\lambda$Это расценивается как предвзятость в SVM, т.е.$w^\top x - \lambda$, целевая функция SVM:Можно видеть, что приведенная выше формула такая же, как формула (5), обе имеют шарнирную потерю!$\tilde{L}_{SVM}(w,\lambda)$да$\tilde{L}(w)$верхняя граница,так как

так,Это помогает объяснить некоторые долгосрочные экспериментальные наблюдения: по оценке AUC стандартные SVM не могут постоянно превосходить другие методы, которые напрямую максимизируют AUC (поскольку потеря прямой максимизации AUC имеет более жесткую границу!)

Две целевые функции также различаются по двум важным параметрам:

• Константа 1 в потерях SVM - это запас, который должен установить классификатор.
• $\tilde{L}(w)$середина$\lambda$Пропало при сворачивании, а в SVM$\lambda$все еще там.(так как$\tilde{L}(w)$последний$\lambda^* \in [c_{N^+}^\uparrow, c_{N^++1}^\uparrow)$, который может быть напрямую оптимизирован итеративно)

OPTIMIZATION

Resolving Ties in Prediction Scores

Прямая оптимизация (5)Будут проблемы: (5) в$w$Диапазон значений не является фиксированным, поэтому цель обучения может быть уменьшена за счет уменьшения масштаба w, так что может быть получено тривиальное решение w = 0.

Основная причина$\tilde{L}(w)$Формула основана наНет предположения о ничьей в прогнозируемых результатах, а тривиальное решение соответствует полярно противоположному результату, т.е. независимо от данных. Функция прогнозирования всегда выдает один и тот же результат (0).

Чтобы решить эту проблему, в данной статье целевая функция дополнена двумя дополнительными условиями:

где второй член соответствует члену наименьших квадратов, чтобы противодействовать эффекту центрирования w до нуля,$\Omega(w)$является термином регуляризации.

Linear Predictor

когда$f_w(x)=w^\top x$,$\Omega(w)=\frac{1}{2}||w||^2$час,$[x^\top w -\lambda]_+$является выпуклой функцией. когда$\alpha\in[0,1],w,w',\lambda,\lambda'$:следовательно$\sum_{i=1}^N[x^\top w - \lambda]_+ + N^+ \lambda$является выпуклой функцией.$\min\sum_{i=1}^N[c_i-\lambda]_+ + N^+\lambda$также является выпуклой функцией.

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

Batch Learning

С настройкой пакетного обучения мы знаем все обучающие выборки, поэтому мы можем использовать алгоритм спуска по блочным координатам для оптимизации (8):Оптимизация w может быть преобразована в следующую задачу ограниченной оптимизации:

Это задача квадратичной выпуклой оптимизации, которая может быть решена методом внутренних точек, когда размерность w средняя или малая. Для многомерного w алгоритм онлайн-обучения более эффективен, поскольку он позволяет избежать построения матрицы Гессе.

Online Learning

где размер шага$\eta_t \sim \frac{1}{\sqrt{t}}$.

Experiments