Максимальный ROC-AUC меньше 1: разбор задачи с собеседования

Даниил Фенелонов 19 апреля 2026 г. 5 минут чтения

Содержание

Максимальный ROC-AUC, если он не единица: разбор задачи с собеседования

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

Что такое ROC-AUC без теории

Большинство людей запоминают ROC-AUC как «площадь под кривой, которая строится по TPR и FPR при разных порогах». Определение верное, но бесполезное для рассуждений. На самом деле у себя в голове очень сложно представить, что такое TPR и FPR и как построение графика в этих координатах дает нам понимание о качества классификации. Оно не даёт интуиции: почему AUC равен именно этому числу, от чего зависит, как меняется. Когда на собеседовании задаёшь вопрос чуть в сторону от стандартного — человек говорит про площадь под кривой и зависает.

А между тем, у ROC-AUC есть простая и мощная интерпретация через пары.

AUC как доля правильно ранжированных пар

Возьмём датасет, в котором $k$ объектов относятся к классу 1 (positive) и $m$ объектов к классу 0 (negative). Классификатор присваивает каждому объекту скор - чем выше скор, тем увереннее модель, что объект positive.

Теперь составим все возможные пары (positive, negative). Их ровно $k\times m$ . Для каждой пары зададим вопрос: правильно ли модель ранжировала эту пару? То есть получил ли positive-объект более высокий скор, чем negative?

AUC = \frac{\text{число пар, в которых } s(x^{+}) > s(x^{-})}{k \cdot m}

где $s(⋅)$ - скор классификатора.

Вот и всё. AUC - это доля пар, в которых модель «угадала» порядок. Если все positive ранжированы выше всех negative — AUC = 1. Если модель подбрасывает монетку — AUC ≈ 0.5.

Из этого сразу видно важное свойство: при уникальных скорах (без совпадений) каждая пара вносит либо 1, либо 0 в числитель. Значит, AUC принимает дискретные значения:

AUC \in \left\{\frac{j}{k \cdot m} \;\middle|\; j = 0, 1, 2, \ldots, k \cdot m\right\}

Это конечное множество. Не любое число от 0 до 1 может быть AUC — это ключ к решению задачи.

Постановка задачи

Дан датасет из 6 сэмплов. Мы строим бинарный классификатор со строго уникальными скорами. Какой максимальный ROC-AUC можно получить, если он строго меньше единицы?

Хороший первый шаг — уточнить у интервьюера распределение классов. Это не придирка: ответ напрямую зависит от числа positive и negative сэмплов. Но предположим, что распределение неизвестно, и нужно найти глобальный максимум по всем допустимым разбиениям.

Решение

Шаг 1: максимальное число пар

Для фиксированного разбиения $(k,m)$ , где $k+m=6$ , общее число пар:

P(k) = k \cdot (6 - k)

$k$ (positive)	$m$ (negative)	Число пар $k⋅m$
1	5	5
2	4	8
3	3	9
4	2	8
5	1	5

Шаг 2: максимальный AUC < 1

Если $AUC=1$ , все $k⋅m$ пар ранжированы правильно. Если $AUC\le1$ , хотя бы одна пара сломана в ней negative получил скор выше, чем positive. Минимальная потеря - это ровно одна такая инверсия:

AUC_{\max}^{<1}(k) = \frac{k \cdot m - 1}{k \cdot m}

Шаг 3: перебор разбиений

$k / m$	Число пар	$AUC_{\max}^{<1}$	Значение
1 / 5	5	4554	0.800
2 / 4	8	7887	0.875
3 / 3	9	8998	0.889
4 / 2	8	7887	0.875
5 / 1	5	4554	0.800

Результат

\boxed{AUC_{\max}^{<1} = \frac{8}{9} \approx 0.889}

Максимум достигается при равном разбиении классов $k=m=3$ .

Интуиция: число пар $k⋅m$ максимально при $k=m$ (это следует из неравенства AM-GM: при фиксированной сумме $k+m=n$ произведение максимально, когда слагаемые равны). Чем больше пар, тем мельче шаг дискретизации метрики, и тем ближе к единице можно подобраться, потеряв лишь одну пару.

Для произвольного n и неизвестного разбиения ответ обобщается:

AUC_{\max}^{<1}(n) = \frac{\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil - 1}{\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil}

Проверка перебором на Python

Подтвердим результат полным перебором всех перестановок скоров для каждого разбиения классов:

from itertools import permutations
from sklearn.metrics import roc_auc_score

for k in range(1, 6):
    n_neg = 6 - k
    y_true = [1] * k + [0] * n_neg
    auc_values = set()

    for perm in permutations(range(6)):
        auc = roc_auc_score(y_true, list(perm))
        auc_values.add(round(auc, 10))

    sorted_aucs = sorted(auc_values, reverse=True)
    max_below_1 = [a for a in sorted_aucs if a < 1.0][0]
    n_pairs = k * n_neg

    print(f"k={k}, m={n_neg} | пар: {n_pairs} | "
          f"макс AUC<1: {max_below_1:.4f} "
          f"({round(max_below_1 * n_pairs)}/{n_pairs})")

Результат:

k=1, m=5 | пар: 5  | макс AUC<1: 0.8000 (4/5)
k=2, m=4 | пар: 8  | макс AUC<1: 0.8750 (7/8)
k=3, m=3 | пар: 9  | макс AUC<1: 0.8889 (8/9)
k=4, m=2 | пар: 8  | макс AUC<1: 0.8750 (7/8)
k=5, m=1 | пар: 5  | макс AUC<1: 0.8000 (4/5)

Глобальный максимум: 8/9 ≈ 0.889 при разбиении 3/3. Совпадает с аналитическим решением.

Что проверяет этот вопрос

Задача компактная, решается за пару минут, но фильтрует точно.

Понимание механики ROC-AUC. Кандидат, который знает AUC только как «площадь под кривой», не сможет решить задачу. Нужно уметь думать о ней как о доле правильно ранжированных пар — тогда решение выписывается в несколько строк.

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

Способность задать уточняющий вопрос. Ответ зависит от распределения классов, и кандидат, который начинает решать без уточнения — теряет балл. На реальных задачах молчаливые допущения обходятся дороже.

PS

Интерпретация AUC через пары — это не просто удобная метафора. Формально ROC-AUC эквивалентен нормализованной статистике Манна-Уитни (Mann-Whitney U statistic), она же статистика Уилкоксона (Wilcoxon rank-sum). Та самая $U$ , которая используется в непараметрическом тесте на различие двух распределений, — это ровно число правильно ранжированных пар, которое мы считали выше. $AUC = U / (k \cdot m)$ . Так что, решая эту задачу, вы заодно разбирались в основах непараметрической статистики — просто без лишней терминологии.

Поделиться в Telegram