Немного о Precision и Recall

FRD и нефункциональные требования

Зачастую в практике системного аналитика, составляющего FRD, встречаются вещи неформализуемые. Примером могут быть требования типа:

• Приложение должно работать быстро
• Приложение должно потреблять мало трафика
• Видеоматериал должен быть качественным.

Такие требования, будучи записанными в FRD «как есть», являются чудовищным источником проблем впоследствии. Формализация таких требований — постоянная головная боль аналитика. Обычно аналитик решает задачу в два приема: сначала выдвигается «эквивалентное» формальное требование, затем в процессе общения (с заказчиком, экспертом предметной области и т.п.) доказывается, что такое формальное требование может заменить собой исходное требование. Вообще говоря, полученное нами требование не является функциональным; оно описывает не «что» должна уметь делать система, а «как делать». При этом «как делать» должно быть сформулировано с конкретной качественной характеристикой.

Это была преамбула к тезису о том, что системный аналитик должен хорошо владеть математическим аппаратом и заодно уметь объяснять «математику» заказчику. А теперь рассмотрим пример.

О задаче классификации

Предположим, что мы пишем FRD для системы контекстной рекламы, похожей на Amazon Omakase. Одним из модулей нашей будущей системы будет контекстный анализатор:

Анализатор принимает на входе текст веб-страницы и производит его контекстный анализ. То, каким образом он это делает, нас особо не интересует; важно, что на выходе мы получаем набор товарных категорий (множество которых заранее определено). Далее на основе этих категорий мы можем показывать баннеры, товарные ссылки (как Amazon) и т.п. Анализатор для нас пока является черным ящиком, которому мы можем задать вопрос (в виде текста документа) и получить ответ.

Заказчик хочет, чтобы анализатор «хорошо определял контекст». Нам надо сформулировать, что это требование означает. Для начала поговорим о контексте как таковом, т.е. о том самом наборе категорий, который возвращается анализатором. Можно определить это как задачу классификации, когда документу (веб-странице) сопоставляется множество классов из заранее определенного числа; в нашем случае классы — это товарные категории. Задача классификации довольно часто встречается в обработке текстов (например, спам-фильтры).

Метрики оценки

Рассмотрим метрики оценки, применимые к задаче классификации. Допустим, что мы знаем правильные категории для некоторого числа документов. Сгруппируем ответы нашего гипотетического анализатора следующим образом:

• Истинно-положительные (true positives) — те категории, которые мы ожидали увидеть и получили на выходе
• Ложно-положительные (false positives) — категории, которых быть на выходе не должно и анализатор их ошибочно вернул на выходе
• Ложно-отрицательные (false negatives) — категории, которые мы ожидали увидеть, но анализатор их не определил
• Истинно-отрицательные (true negatives) — категории, которых быть на выходе не должно и на выходе анализатора они тоже совершенно правильно отсутствуют.

Назовем тестовой выборкой множество документов (веб-страниц), для которых мы знаем правильные ответы. Если подсчитать по каждой категории число попаданий (считаем попадания по парам документ — категория), получим каноническую табличку распределения ответов:

Левая колонка таблицы — это «правильные» сочетания документов и категорий (присутствия которых мы ожидаем на выходе), правая — неправильные. Верхняя строка таблицы — положительные (positive) ответы классификатора, нижняя — отрицательные (в нашем случае — отсутствие категории в ответе). Если число всех пар документ — категория равно N, то нетрудно увидеть, что

Таблица распределения (contingency matrix) дает несколько иной взгляд на оценку качества нашего классификатора, нежели просто подсчет правильных и неправильных ответов. Здесь обозначено целых 4 непересекающихся класса ответов, множества которых можно изобразить на картинке. Здесь зеленые области обозначают правильные ответы, красные — неправильные. Весь прямоугольник целиком соответствует нашей выборке из N пар.

В общем-то, теперь можно записать требование заказчика в виде (число неправильных ответов равно нулю) и на этом остановиться. Однако на практике таких систем не бывает и анализатор будет, разумеется, работать с ошибками относительно тестовой выборки. Понять процент ошибок нам поможет метрика правильности (accuracy):

В числителе мы видим диагональ матрицы — суммарное число правильных ответов, который делится на общее число вопросов. Например, анализатор, давший 9 правильных ответов из 10 возможных, имеет accuracy 90%.

Метрика F₁

Простым примером неприменимости accuracy-метрики является задача определения обувного бренда. Допустим, мы хотим подсчитать число упоминаний обувных брендов в тексте. Рассмотрим задачу классификации, целью которой будет определить, является ли указанная сущность обувным брендом (Timberland, Columbia, Ted Baker, Ralph Lauren и т.п.). Иначе говоря, мы разбиваем сущности в тексте на два класса: A — Обувной бренд, B — Все остальное.

Теперь рассмотрим вырожденный классификатор, который просто возвращает класс B (Все остальное) для любых сущностей. Для этого классификатора число истинно-положительных ответов будет равно 0. Вообще говоря, давайте подумаем на тему, а часто ли при чтении текста в интернете нам встречаются обувные бренды? Оказывается, как ни странно, что в общем случае 99.9999% слов текста не являются обувными брендами. Построим матрицу распределения ответов для выборки в 100.000:

Вычислим его accuracy, который будет равен 99990 / 100000 = 99.99%! Итак, мы легко построили классификатор, который по сути не делает ничего, однако имеет огромный процент правильных ответов. В то же время совершенно понятно, что задачу определения обувного бренда мы не решили. Дело в том, что правильные сущности в нашем тексте сильно «разбавлены» другими словами, которые для классификации никакого значения не имеют. Учитывая этот пример, вполне понятно желание использовать другие метрики. Например, значение tn явно является «мусорным» — оно вроде как означает правильный ответ, но разрастание tn в итоге сильно «подавляет» вклад tp (который нам важен) в формулу accuracy.

Определим меру точности (P, precision) как:

Как нетрудно заметить, мера точности характеризует, сколько полученных от классификатора положительных ответов являются правильными. Чем больше точность, тем меньше число ложных попаданий.

Мера точности, однако, не дает представление о том, все ли правильные ответы вернул классификатор. Для этого существует так называемая мера полноты (R, recall):

Мера полноты характеризует способность классификатора «угадывать» как можно большее число положительных ответов из ожидаемых. Заметим, что ложно-положительные ответы никак не влияют на эту метрику.

Precision и Recall дают довольно исчерпывающую характеристику классификатора, причем «с разных углов». Обычно при построении подобного рода систем приходится все время балансировать между двумя этими метриками. Если вы пытаетесь повысить Recall, делая классификатор более «оптимистичным», это приводит к падению Precision из-за увеличения числа ложно-положительных ответов. Если же вы подкручиваете свой классификатор, делая его более «пессимистичным», например, строже фильтруя результаты, то при росте Precision это вызовет одновременное падение Recall из-за отбраковки какого-то числа правильных ответов. Поэтому удобно для характеристики классификатора использовать одну величину, так называемую метрику F₁:

Фактически это просто среднее гармоническое величин P и R. Метрика F₁ достигает своего максимума 1 (100%), если P = R = 100%.
(нетрудно прикинуть, что для нашего вырожденного классификатора F₁ = 0). Величина F₁ является одной из самых распространенных метрик для подобного рода систем. Именно F₁ мы и будем использовать, чтобы сформулировать пороговое качество нашего анализатора в FRD.

В вычислении F₁ для задачи классификации есть два основных подхода.

• Суммарный F₁: результаты по всем классам сводим в одну единую таблицу, по которой затем вычисляется метрика F₁.
• Средний F₁: для каждого класса формируем свою contingency matrix и свое значение F₁, затем берем простое арифметическое среднее для всех классов.

Зачем нужен второй способ? Дело в том, что размеры выборки для разных классов могут сильно различаться. Для каких-то классов у нас может быть очень мало примеров, а для каких-то — много. В итоге метрики одного «большого» класса, будучи сведенными в одну общую таблицу, будут «забивать» все остальные. В ситуации, когда мы хотим оценить качество работы системы более-менее равномерно для всех классов, второй вариант подходит лучше.

Обучающая и тестовая выборка

Выше мы рассматривали классификацию на единой выборке, для которой нам известны все ответы. Если применить это к контекстному анализатору, который мы пытаемся описать, все выглядит немного сложнее.

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

Мы вычисляем значение F₁ по заданной выборке, которая известна заранее. Эта выборка обычно называется обучающей. Однако мы не знаем, как поведет себя классификатор на тех данных, которые нам неизвестны. Для этих целей обычно используется так называемая тестовая выборка, иногда называемая golden set. Разница между обучающей и тестовой выборкой чисто умозрительная: ведь имея некоторое множество примеров, мы можем разрезать его на обучающую и тестовую выборку как нам угодно. Но для самообучающихся систем формирование правильной обучающей выборки очень критично. Неправильно подобранные примеры могут сильно повлиять на качество работы системы.

Типична ситуация, когда классификатор показывает хороший результат на обучающей выборке и совершенно провальный — на тестовой выборке. Если наш алгоритм классификации основан на машинном обучении (т.е. зависит от обучающей выборки), мы можем оценить его качество по более сложной «плавающей» схеме. Для этого все имеющиеся у нас примеры делим, скажем, на 10 частей. Изымаем первую часть и используем ее для обучения алгоритма; оставшиеся 90% примеров используем как тестовую выборку и вычисляем значение F₁. Затем изымаем вторую часть и используем в качестве обучающей; получаем другое значение F₁, и т.д. В итоге мы получили 10 значений F₁, теперь берем их среднее арифметическое значение, которое и станет окончательным результатом. Повторюсь, что это способ (называемый также cross-fold validation) имеет смысл только для алгоритмов, основанных на машинном обучении.

Возвращаясь к написанию FRD, замечаем, что у нас ситуация куда хуже. Мы имеем потенциально неограниченный набор входных данных (все веб-страницы интернета) и нет никакого способа оценить контекст страницы, кроме как участие человека. Таким образом, наша выборка может быть сформирована только вручную, причем сильно зависеть от капризов составителя (а решение о том, отнести ли страницу к какой-то категории, принимает человек). Мы можем оценить меру F₁ на известных нам примерах, но никак не можем узнать F₁ для всех страниц интернета. Поэтому для потенциально неограниченных наборах данных (таких, как веб-страницы, коих неисчислимо много), иногда используют «метод тыка» (unsupervised). Для этого случайным образом выбирают определенное число примеров (страниц) и по ним оператор (человек) составляет правильный набор категорий (классов). Затем мы можем испытать классификатор на этих выбранных примерах. Далее, считая, что выбранные нами примеры являются типичными, мы можем приближенно оценить точность алгоритма (Precision). При этом Recall мы оценить не можем (неизвестно, сколько правильных ответов находятся за пределами выбранных нами примеров), следовательно, не можем вычислить и F₁.

Таким образом, если мы хотим узнать, как ведет себя алгоритм на всех возможных входных данных, самое лучшее, что сможем оценить в этой ситуации — это приближенное значение Precision. Если же все согласны использовать заранее определенную фиксированную выборку, то можно вычислить средние значение F₁ по этой выборке.

В итоге?

А в итоге нам придется сделать следующее:

1. Зафиксировать обучающую выборку. Обучающая выборка будет построена исходя из представлений заказчика о «правильном» контексте.
2. Зафиксировать набор категорий для нашего анализатора. Не можем же мы вычислять F₁ по неопределенному набору классов?
3. Описать требование в виде: Анализатор должен определять контекст с средней величиной F₁ не менее 80%. (например)
4. Объяснить это заказчику.

Как видим, написать FRD на такую систему нелегко (особенно последний пункт), но возможно. Что касается порогового значения F₁, в таких случаях можно отталкиваться от значений F₁ для похожих задач классификации.