Подробное обсуждение определения, интерпретации, ограничений, сложности вычислений кривой ROC и расширения до мультиклассов.

Фон

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

Понять состав кривой ROC

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

Частота совпадений определяется соотношением истинных положительных результатов из всех основных истинных положительных результатов. Другими словами, сколько из всех действительно релевантных примеров успешно определяет классификатор? Уровень ложных срабатываний определяется соотношением ошибок на основании истинно отрицательных. Другими словами, из всех действительно нерелевантных примеров сколько из них ошибочно попадает в классификатор. Математически их можно выразить как условные вероятности:

Мы можем оценить вероятности, посчитав примеры, которые попадают в четыре ячейки матрицы неточностей.

Определение в форме условных вероятностей дает много полезных перспектив для понимания частоты совпадений и ложноположительных результатов.

Например, поскольку частота совпадений и частота ложных срабатываний обусловлены соответствующими наземными метками истинности, они инвариантны к изменению распределения классов в наборе данных. Таким образом, они являются хорошими показателями, отражающими внутреннее качество классификатора. Вы можете проверить это путем случайной выборки наборов тестовых данных из различных комбинаций распределения наземных меток достоверности. Результирующая частота совпадений и частота ложных срабатываний будут одинаковыми для всех этих выборочных наборов тестовых данных с незначительной дисперсией, вносимой случайной выборкой.

Кроме того, из формул условной вероятности также ясно, что количество совпадений и количество ложных срабатываний не составляют в сумме 1. Их умножение или деление одного на другое не дает какой-либо непосредственно полезной информации из-за основного истинного знаменателя в формулы.

Постройте кривую ROC

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

Имея набор данных с диапазоном пороговых значений, мы получим соответствующий набор пар «частота совпадений» и «частота ложных срабатываний», используя приведенные выше формулы оценки. Затем мы можем построить график ROC с частотой ложных срабатываний по оси x и частотой совпадений по оси y. См. Иллюстрацию ниже.

Чтобы было ясно, каждая точка на кривой ROC является одним и тем же классификатором с различным порогом.

Анализ кривой ROC

Давайте посмотрим поближе, чтобы понять, что изображено на графике. Строка y=x - это когда классификатор просто делает случайные предположения. Чтобы понять, почему это так, рассмотрим определение условной вероятности частоты совпадений и частоты ложных срабатываний. Случайное угадывание означает, что результат классификации не зависит от основных истинных меток. В этом случае частота совпадений равна частоте ложных срабатываний.

Точка (0,0) - это когда классификатор никогда не имеет ложных срабатываний, потому что он вообще не вызывает никаких положительных примеров. Это как безмолвный классификатор. И наоборот, точка (1,1) - это то место, где классификатор запускается для всех примеров, достигая 100% вероятности совпадений, но также получая 100% ложноположительных результатов, потому что он ошибочно классифицирует все отрицательные примеры как положительные.

Теперь интуитивно мы хотим, чтобы кривая ROC нашего классификатора была выше линии y=x. Это означает, что при той же частоте ложных срабатываний классификатор имеет хорошую частоту попаданий. Или симметрично, с той же частотой попаданий, у классификатора меньше ложных срабатываний. Очевидно, что теоретический идеал находится в (0,1).

С другой стороны, классификатор с кривой ROC ниже y=x может показаться хуже случайных предположений. Но на самом деле мы можем перевернуть это - рассматривать классифицированный положительный результат как отрицательный и наоборот - чтобы сделать его лучше, чем случайные предположения. Конечно, в этом случае более важно выяснить, почему классификатор приходит к противоположному выводу о базовой истине. Обычно это происходит из-за ошибок в коде.

Для сравнения производительности классификаторов мы часто используем площадь под кривой (AUC) как единый показатель. Чем больше AUC, тем лучше производительность. Однако, применяя это к сценариям реального мира, мы должны учитывать цену ошибок. В некоторых случаях низкая вероятность попадания обходится гораздо дороже, например, при обнаружении болезней. В других случаях высокий уровень ложных срабатываний может быть более опасным. Мы должны выбрать порог, который максимизирует ожидаемое вознаграждение, исходя из конкретных вариантов использования.

Ограничение кривой ROC

Кривая ROC во многих случаях является отличным показателем производительности. Но это не обязательно показывает точность классификатора. Точность определяется как из всех классифицированных положительных результатов, сколько из них действительно положительные. В терминах условной вероятности его формула выглядит следующим образом

Точность полезна в тех случаях, когда можно пропустить некоторые релевантные примеры, но нам нужна высокая степень уверенности в классифицированных положительных результатах.

Чтобы понять, почему ROC не является предпочтительным в этом случае, рассмотрим набор данных с очень небольшим количеством достоверных положительных результатов. Классификатор может достичь высокой частоты совпадений и низкой частоты ложных срабатываний (близких к идеальной (0,1) точке), классифицируя надмножество основных истинных положительных результатов как положительных - скажем, мощность надмножества вдвое больше, чем наземных истинных положительных результатов. Показатель попадания составляет 100%, потому что он успешно определяет все достоверные положительные результаты. Уровень ложных срабатываний по-прежнему низок из-за подавляющего количества отрицательных истинных результатов в наборе данных (знаменатель частоты ложных срабатываний), несмотря на его чрезмерное количество ложных срабатываний. Однако точность в этом случае составляет всего 50%.

Сложность вычислений

Кривая ROC - это один и тот же классификатор с разными порогами. Вы можете подумать, что для получения пар «частота совпадений» и «частота ложных срабатываний» для построения кривой нам придется многократно запускать классификатор на тестовых данных каждый раз с другим порогом. В этом случае сложность вычислений составит m*n*O(classifier). m - количество порогов. n - количество примеров. O(classifier) - это сложность классификации одного примера, что очень дорого во многих современных моделях на основе глубоких нейронных сетей.

На самом деле есть более эффективный способ. Обратите внимание, что значения, полученные классификатором до применения порога, не меняются. Так что нет необходимости повторять классификацию на примерах. Просто прогоните классификатор по всем примерам один раз и отсортируйте выходные значения в порядке убывания. Сложность вычислений составляет n*O(classifier)+nlog(n). Затем нам нужно всего лишь одно линейное сканирование, чтобы построить кривую ROC. Во время сканирования мы отслеживаем частоту совпадений и частоту ложных срабатываний. Давайте воспользуемся логистической регрессией в качестве иллюстративного примера. Все выходные значения будут в диапазоне [0,1]. Классификатор классифицирует пример как положительный, если порог больше или равен выходному значению. См. Следующий фрагмент кода Python для алгоритма линейного сканирования:

hit = 0.
false_positive = 0.
n = len(output_values)
roc = []
# output_values is sorted in descending order.
for i, v in enumerate(output_values):
    # Assuming threshold == v, then the ith example will be 
    # classified as positive, because the example is classifier
    # positive when threshold >= v.
    if label(i) == POSITIVE:
        hit += 1
    else:
        false_positive += 1
    roc.append((false_positive/n, hit/n))

Ключевым моментом здесь является то, что, поскольку выходные значения отсортированы в порядке убывания, перемещение порога слева направо не меняет классификацию ранее встречавшихся примеров - когда пример классифицируется как положительный, он остается положительной классификацией, когда мы понижаем порог. Следовательно, мы можем просто продолжать накапливать количество совпадений и ложных срабатываний в линейном сканировании. Общий комплекс n*O(classifier)+nlog(n)+n. Когда O(classifier) - тяжелая часть, этот алгоритм намного эффективнее.

Расширение на несколько классов

До сих пор мы предполагали, что в ярлыках только два класса. Фактически, кривая ROC была в основном предназначена для двоичной классификации. Когда у нас более двух классов, мы обычно строим один против остальных пар для каждого класса и строим соответствующую кривую ROC. Чтобы использовать конкретный пример, мультиклассовые классификаторы часто используют softmax для генерации массива вероятностей. Значение ith в массиве соответствует вероятности класса ith. Для любого класса i мы можем построить его кривую ROC, варьируя порог для значения ith. Если значение ith больше или равно порогу, пример классифицируется как класс i (положительный). В противном случае он классифицируется как прочие (отрицательный). С этим построением мы возвращаемся к нашей бинарной классификации, где можно построить кривую ROC. См. Иллюстрацию на следующем графике.

Нам также необходимо развить метрику AUC, поскольку мы больше не имеем дело только с одной кривой ROC. Проводятся исследования для оценки объема под поверхностью (VUS) и некоторые более удобные в вычислительном отношении приближения к этому. У нас нет времени вдаваться в подробности. Лично я считаю, что если метрику становится трудно вычислить и понять, возможно, она больше не является подходящей метрикой для решения проблемы. Мы должны искать альтернативы. Например, ImageNet оценивает классификаторы по точности топ-1 и топ-5, даже несмотря на то, что его распределение по классам не сбалансировано - есть много классов, у которых очень мало примеров.

Подведение итогов

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