Классификация: провести границу

Пять с половиной тысяч настоящих SMS, из них 747 — спам. Мы превратим каждое сообщение в несколько чисел, проведём в пространстве этих чисел границу, а затем выясним главное: граница — это ещё не решение. Решение появляется вместе с порогом, а порог — вместе с ценой каждой из двух ошибок.

Сто сорок символов против фильтра

Вот три сообщения из настоящей коллекции SMS, собранной для исследований спам-фильтров:

«Ok lar... Joking wif u oni...»

«Free entry in 2 a wkly comp to win FA Cup final tkts 21st May 2005. Text FA to 87121 to receive entry question(std txt rate)»

«I'll call you when I get off work»

Первое и третье — обычная переписка; исследователи спама называют её ham, «ветчина», в противовес консервированному spam. Второе — реклама лотереи, и человек опознаёт её мгновенно, не дочитывая. Наша задача на урок: научить этому машину и честно измерить, насколько ей можно доверять.

Спам-фильтр — удобный полигон, но выводы урока не про SMS. Той же машинерией больница сортирует снимки на «норма» и «показать врачу», банк метит переводы «обычный» и «похож на мошенничество», конвейер отделяет годные детали от брака, а модерация — допустимые сообщения от запрещённых. Везде одна конструкция: признаки, граница, порог, две ошибки с разными ценами. Спам мы выбрали за то, что его данные открыты, а обе цены ошибок знакомы каждому владельцу почтового ящика.

Коллекция, с которой мы работаем, называется SMS Spam Collection; её собрали в 2011 году Тьяго Алмейда и Хосе Мария Гомес Идальго из британских и сингапурских источников, и она лежит в открытом архиве UCI. В ней 5574 сообщения: 4827 обычных и 747 спама, доля спама 13,4%. Каждая строка уже размечена человеком, так что по классификации прошлого урока это обучение с учителем, ответ — класс из двух значений. Копия файла лежит в репозитории курса: scripts/data/sms-spam-collection.tsv.

Из текста в числа: признаки

Модель не читает текст; она видит числа. Первый шаг любой классификации — выбрать, какие числа вычислять из объекта. Посмотрим на коллекцию глазами статистика, как мы делали с автобусами в уроке о статистике, и сравним два класса по простым измеримым свойствам.

Средняя длина обычного сообщения — 72,5 символа, спама — 139,7: спамеру нужно место под условия акции. Цифр в обычном сообщении в среднем 0,3, в спаме — 15,8: телефоны, коды, суммы. Слово «free» встречается в 26,6% спама и в 1,4% переписки; «call» — в 46,5% спама против 6%. Каждое такое свойство отделяет классы лишь частично, но их сумма уже почти решает задачу.

Соберём из сообщения $t$ вектор из восьми признаков:

$$x(t)=\Bigl( 1,\; \tfrac{\text{длина}}{100},\; \tfrac{\text{цифры}}{10},\; [\text{free}],\; [\text{call}],\; [\text{txt}],\; [\text{www}],\; [\text{win/prize}] \Bigr),$$

где квадратные скобки — индикаторы: единица, если слово есть, ноль иначе. Первый признак всегда равен единице; он даст модели свободный член, «фон подозрительности». Восемь чисел вместо ста сорока символов — огромная потеря информации, и она сознательная: с прозрачными признаками мы сможем прочитать выученное правило глазами. Настоящие фильтры используют тысячи признаков-слов; геометрия у них та же.

Счёт и граница в пространстве признаков

Линейный классификатор сворачивает вектор признаков в одно число, счёт:

$$s(t)=\langle w,\,x(t)\rangle =\sum_{j} w_j\,x_j(t),$$

и объявляет сообщение спамом, когда счёт велик. Геометрически уравнение $s(t)=0$ задаёт гиперплоскость в пространстве признаков: по одну сторону живёт переписка, по другую — спам. В полном восьмимерном пространстве её не нарисовать, но два признака — длину и число цифр — можно отложить по осям и посмотреть на настоящие сообщения.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Обратите внимание, чего на рисунке нет: идеальной границы. Облака перекрываются, потому что признаки не различают «позвони мне после шести» от «позвони и выиграй». Часть неопределённости — цена дешёвых признаков, часть неустранима: бывают сообщения, которые и человек классифицирует не сразу. С этим фактом классификация живёт всегда, и весь дальнейший аппарат — способ жить с ним честно.

Выбор признаков — это ещё и выбор мира, в котором фильтр умеет жить. Наши индикаторы привязаны к английским словам, потому что коллекция англоязычная: на русском спаме признаки «free» и «txt» молчат, и от восьмимерной модели остаются длина да цифры. Модель наследует границы своих данных, как выборка наследовала рамку в уроке о статистике; вопрос «на каком потоке это будет работать» задаётся на этапе признаков, а не после жалоб пользователей.

От счёта к вероятности

Счёт $s$ пробегает всю числовую ось, и его сырое значение трудно интерпретировать: что значит «счёт 2,7»? Сигмоида переводит счёт в число из интервала $(0,1)$:

$$\hat p =\sigma(s) =\frac{1}{1+e^{-s}},$$

которое мы будем читать как оценку вероятности спама. При $s=0$, на самой границе, $\hat p=0{,}5$; большой положительный счёт прижимает $\hat p$ к единице, большой отрицательный — к нулю. Модель со свободным членом, линейным счётом и сигмоидой называется логистической регрессией; слово «регрессия» в имени историческое, задачу она решает классификационную.

Обучение выбирает веса $w$, минимизируя логарифмическую потерю из прошлого урока на размеченных сообщениях:

$$L(w) =\frac{1}{n}\sum_{i=1}^{n} \Bigl[ -y_i\ln\sigma\bigl(\langle w,x_i\rangle\bigr) -(1-y_i)\ln\bigl(1-\sigma(\langle w,x_i\rangle)\bigr) \Bigr],$$

где $y_i=1$ для спама. Мы обучили такую модель на 4000 случайно отобранных сообщениях коллекции, оставив 1574 для честной проверки; все числа ниже посчитаны на отложенной части и воспроизводятся скриптом из репозитория. Вот выученные веса:

Признак	фон	длина/100	цифры/10	free	call	txt	www	win
Вес	−4,87	0,03	5,94	2,93	−0,34	2,90	5,10	2,33

Откуда берутся эти числа? Производная логарифмической потери по весам устроена поучительно просто:

$$\frac{\partial L}{\partial w} =\frac{1}{n}\sum_{i=1}^{n} \bigl(\sigma(\langle w,x_i\rangle)-y_i\bigr)\,x_i ,$$

то есть каждый пример тянет веса с силой, равной ошибке на нём: верно и уверенно классифицированные сообщения почти не тянут, ошибки тянут сильно, и тянут именно те признаки, которые в них горят. Обучение — несколько тысяч маленьких шагов против этой силы; сами алгоритмы шагания и их подводные камни — предмет уроков об оптимизации, здесь нам хватит смысла формулы: модель формируется своими ошибками.

Таблица читается как рентген правила. Фон −4,87: без улик сообщение считается перепиской с большим запасом. Самые тяжёлые улики — цифры и ссылки; «free» и «win» весят умеренно. А вес «call» оказался отрицательным, хотя в спаме это слово встречается в восемь раз чаще! Разгадка в совместности признаков: спамерское «call» всегда приходит с цифрами номера, и признак цифр уже забрал его вклад себе; оставшийся чистый эффект слова «позвони» — лёгкий сигнал живой переписки. Веса линейной модели говорят не «встречается ли признак в спаме», а «что он добавляет к уже учтённому», и путать эти вопросы опасно.

Вторая дорога к тому же счёту: наивный Байес

Исторически спам-фильтры пришли к линейному счёту другой дорогой, и она стоит того, чтобы пройти её пешком. Спросим прямо: какова вероятность, что сообщение — спам, если в нём есть слово «free»? По формуле условной вероятности, которую мы построим строго в уроке о Байесе, ответ собирается из трёх известных нам частот:

$$\Pr(\text{спам}\mid\text{free}) =\frac{\Pr(\text{free}\mid\text{спам})\,\Pr(\text{спам})} {\Pr(\text{free})} =\frac{0{,}266\cdot 0{,}134}{0{,}266\cdot 0{,}134+0{,}014\cdot 0{,}866} \approx 0{,}746.$$

Одно слово подняло вероятность спама с фоновых 13,4% до 75%. Наивный байесовский фильтр повторяет этот ход для каждого слова и перемножает вклады, наивно считая слова независимыми уликами. В логарифмах произведение превращается в сумму:

$$\ln\frac{\Pr(\text{спам}\mid t)}{\Pr(\text{переписка}\mid t)} =\ln\frac{\Pr(\text{спам})}{\Pr(\text{переписка})} +\sum_{\text{слово}\in t} \ln\frac{\Pr(\text{слово}\mid\text{спам})} {\Pr(\text{слово}\mid\text{переписка})},$$

и справа стоит знакомая конструкция: свободный член плюс сумма весов встреченных признаков. Наивный Байес — тоже линейный счёт, только веса в нём не подбираются оптимизацией, а вычисляются из частот напрямую. Отсюда и его историческая роль: фильтр Грэма 2002 года можно было пересчитать на калькуляторе, и он уже отбивал девяносто с лишним процентов спама. Логистическая регрессия обычно точнее, потому что честно учитывает совместность улик — мы видели на весе «call», как сильно это меняет дело, — но обе модели говорят на одном языке логарифмических шансов.

Порог: вероятность становится решением

Фильтру недостаточно числа $\hat p$: письмо надо либо показать, либо убрать в папку «спам». Решение принимает порог $\tau$:

$$\text{решение}(t)= \begin{cases} \text{спам}, & \hat p(t)\ge \tau,\\[2pt] \text{переписка}, & \hat p(t)<\tau. \end{cases}$$

В уроке о статистике и решениях мы вывели, откуда берётся порог: из цен двух ошибок. Пропущенный спам стоит секунды раздражения. Письмо о работе, молча похороненное в папке «спам», может стоить самой работы. Цены несимметричны в сотни раз, и поэтому канонический порог $0{,}5$ — не закон природы, а всего лишь точка, где цены ошибок объявлены равными. Весь этот урок можно рассматривать как разворачивание одной мысли: граница принадлежит модели, а порог — задаче.

$$\tau^\star =\frac{c_{\mathrm{FP}}}{c_{\mathrm{FP}}+c_{\mathrm{FN}}},$$

где $c_{\mathrm{FP}}$ — цена ложной тревоги (переписка в спаме), а $c_{\mathrm{FN}}$ — цена пропуска. Проверьте предельные случаи: при равных ценах $\tau^\star=0{,}5$; при бесконечно дорогой ложной тревоге $\tau^\star\to 1$, фильтр трогает только очевидное.

Полезно увидеть, среди чего порог выбирает. Нарисуем счёт всех отложенных сообщений двумя гистограммами: переписка своим распределением, спам — своим.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Матрица ошибок: четыре клетки вместо одной

Применим фильтр с порогом $\tau=0{,}5$ к отложенным 1574 сообщениям, из которых 226 — спам. Результат укладывается в матрицу два на два:

	предсказано: спам	предсказано: переписка
на деле спам	205	21
на деле переписка	10	1338

У каждой клетки есть имя и судьба. 205 верно пойманных — истинные срабатывания, TP. 21 пропущенный спам — ложные пропуски, FN: они доберутся до глаз. 10 честных сообщений в спаме — ложные тревоги, FP: самые дорогие жильцы матрицы. 1338 — истинные пропуски, TN, тихая норма. Одно число «доля верных ответов» схлопывает четыре судьбы в кашу; матрица — минимальный честный отчёт классификатора, и просить её нужно раньше любых процентов.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Ловушка доли верных ответов

Доля верных ответов нашего фильтра при пороге 0,5:

$$\mathrm{accuracy} =\frac{205+1338}{1574} \approx 0{,}980.$$

Число выглядит триумфом, пока рядом не встанет базовая линия из урока о режимах. Фильтр, который вообще ничего не делает и объявляет перепиской всё подряд, верен в $1348/1574\approx 85{,}6\%$ случаев: класс «переписка» попросту большой. Настоящий вклад модели — дистанция между 85,6% и 98%, а не сами 98%. На перекошенных классах доля верных ответов всегда льстит, и чем перекошеннее классы, тем наглее: при доле спама 0,1% фильтр-бездельник верен на 99,9%.

Редкий класс — норма жизни, а не курьёз: болезнь на скрининге, мошенническая транзакция, деталь с браком. Везде, где класс, ради которого построена система, встречается редко, точность нужно заменять метриками, которые смотрят на редкий класс в упор.

Популярное обходное решение — пересобрать обучающие данные так, чтобы классов стало поровну, — лечит симптом и создаёт болезнь. Модель, обученная на мире с половиной спама, выучит завышенный фон подозрительности; её вероятности перестанут быть честными для потока с 13% спама, и порог, выведенный из цен, промахнётся. Балансировать выборку можно, но тогда калибровку и порог обязательно пересчитывают на настоящем распределении — об этом шаге чаще всего забывают.

Точность и полнота

Два главных таких показателя отвечают на два разных вопроса. Точность (precision): если фильтр крикнул «спам», насколько ему верить? Полнота (recall): какую долю всего спама фильтр поймал?

$$\mathrm{precision} =\frac{TP}{TP+FP} =\frac{205}{205+10} \approx 0{,}953, \qquad \mathrm{recall} =\frac{TP}{TP+FN} =\frac{205}{205+21} \approx 0{,}907.$$

Заметьте, что в знаменателях стоят разные ошибки: точность портят ложные тревоги, полноту — пропуски. Поэтому пара «точность-полнота» не схлопывается в одно число без потери смысла: она двумерна, как двумерна пара цен $c_{\mathrm{FP}}$ и $c_{\mathrm{FN}}$. Когда одно число всё же нужно — для таблицы лидеров или автоматического отбора моделей — берут их гармоническое среднее, F-меру, но выбор рабочей точки она не отменяет.

Кривая компромисса

Порог — ручка, и её можно крутить. Каждое положение даёт свою матрицу, свою пару «точность-полнота», и все положения сразу рисуются одной кривой.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Кривая отвечает и на вопрос «какая модель лучше»: фильтр, чья кривая лежит целиком выше и правее, лучше при любых ценах ошибок. Кривые же пересекающиеся объявляют ничью, которую разрешают только цены: одна модель лучше для осторожной политики, другая — для агрессивной. Сравнение классификаторов одним числом при неизвестных ценах — самая распространённая методическая ошибка в задачах с редким классом.

В литературе чаще встречается другая пара осей, ROC-кривая: доля пойманного спама против доли потревоженной переписки,

$$\mathrm{TPR}=\frac{TP}{TP+FN}, \qquad \mathrm{FPR}=\frac{FP}{FP+TN}.$$

У неё есть достоинство: обе оси — доли внутри своего класса, и кривая не зависит от того, сколько спама в потоке. Но у нашей задачи это достоинство оборачивается слепотой. При пороге 0,5 фильтр тревожит $10/1348\approx 0{,}7\%$ переписки — на ROC-оси это почти ноль, превосходно. А точность при тех же десяти ложных тревогах — 95%, и если бы спама было не 13%, а 1%, те же 0,7% ложных тревог обрушили бы точность до половины: каждый второй крик «спам» был бы ложным. Точность чувствует редкость класса, FPR — нет; поэтому на редких классах рабочую точку выбирают по паре «точность-полнота», а ROC оставляют для сравнения моделей между задачами.

Метрика — тоже оценка по выборке

Число $\mathrm{precision}=0{,}995$ при пороге 0,9 выглядит как факт, но вспомним урок о статистике: это выборочная доля, посчитанная по 189 срабатываниям, и у неё есть стандартная ошибка. Одна-единственная ложная тревога из 189 — это оценка $\hat p=1/189$ вероятности ложного крика, и интервал Уилсона для неё простирается от 0,1% до 2,9%: истинная точность фильтра лежит где-то между 97,1% и 99,9%. Разница между «одна ошибка на тысячу» и «одна на тридцать четыре» — это разница между рекламным обещанием и честным отчётом, и по 189 наблюдениям различить их невозможно.

$$\operatorname{se}\bigl(\widehat{\mathrm{prec}}\bigr) =\sqrt{\frac{\widehat{\mathrm{prec}}\,(1-\widehat{\mathrm{prec}})} {TP+FP}},$$

и знаменатель здесь — не размер теста, а число срабатываний: чем выше порог, тем меньше срабатываний и тем шире неопределённость самой точности. Осторожные фильтры измеряются хуже всех именно там, где обещают больше всего. Правило то же, что для опросов: рядом с каждой метрикой должен стоять объём выборки, по которому она посчитана, а громкие сравнения «99,5 против 99,1» без интервалов — шум.

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

Лаборатория порога

Всё, что было выше, собрано в лабораторию с настоящими счетами нашего фильтра на отложенных сообщениях.

Порядок опытов. Сначала посмотрите на две гистограммы счёта: переписка слева, спам справа, перекрытие — зона неизбежных ошибок. Двигайте порог и следите за матрицей: ошибки перетекают из клетки в клетку, исчезать им некуда. Затем задайте цены ошибок и найдите порог наименьших месячных потерь; сравните его с расчётным $\tau^\star$ и с привычкой ставить 0,5. В конце включите «дрейф спама»: новые рассылки без слова «free» сползают влево, и вчерашний оптимальный порог тихо теряет полноту — к этому сюжету мы вернёмся через раздел.

Калибровка: можно ли верить числу 0,7

Порог превращает $\hat p$ в решение, молча предполагая, что $\hat p$ — честная вероятность. Это надо проверять. Соберём все сообщения, которым модель дала $\hat p$ около 0,7, и посмотрим, какая доля из них действительно спам. У откалиброванной модели — около 70%. Систематическое расхождение называется раскалиброванностью: модель, уверенная на 99% там, где права в 80% случаев, опасна не ошибками, а тоном, которым она их совершает.

$$\text{калибровка: }\; \Pr\bigl(\text{спам}\,\bigm|\,\hat p\approx q\bigr)\approx q \quad\text{для всех } q.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

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

Право промолчать

Между «спам» и «переписка» просится третий ответ: «не уверен, покажи человеку». Введём зону отказа: при $\hat p\in[\tau_1,\tau_2]$ фильтр не решает сам, а откладывает сообщение в папку проверки. Отказ — не слабость, а честность, купленная за чужое время: сколько сообщений в зоне, столько минут ручного разбора. На нашем тесте зона $[0{,}3;\,0{,}9]$ вмещает 34 сообщения из 1574, около двух процентов потока, и забирает в себя треть всех ошибок уверенного фильтра: внутри зоны ошибкой оказывается каждая третья точка, снаружи — одна из семидесяти семи. Сомнительное действительно скапливается у границы.

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

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Больше двух классов

Почта делит письма не на два, а на много ящиков: переписка, рассылки, уведомления, спам. Линейная механика обобщается без драмы: каждый класс $k$ получает свой вектор весов и свой счёт $s_k$, а вероятности классов выдаёт обобщение сигмоиды, softmax:

$$\hat p_k =\frac{e^{s_k}}{\sum_{m} e^{s_m}},$$

устроенный так, что все $\hat p_k$ положительны и в сумме дают единицу. Решение — класс с наибольшей вероятностью, либо отказ, если максимум недостаточно велик. Матрица ошибок становится $K\times K$, и её недиагональные клетки рассказывают, какие классы путаются между собой; у почты это обычно «рассылки» с «уведомлениями», а не спам с перепиской. Мы встретимся с softmax в каждом уроке о нейросетях, начиная с распознавания цифр.

Ловушка дисбаланса в многоклассовом мире прячется в усреднении. Полноту можно посчитать по каждому классу и усреднить двумя способами:

$$\text{макро} =\frac{1}{K}\sum_{k}\mathrm{recall}_k, \qquad \text{микро} =\frac{\sum_k TP_k}{\sum_k (TP_k+FN_k)},$$

и они расходятся ровно тогда, когда классы неравны. Микро-среднее взвешивает классы их размером, и редкий «спам» в нём тонет так же, как тонул в доле верных ответов; макро-среднее даёт каждому классу равный голос и роняет оценку системы, забросившей хоть один класс. Какое среднее честное — зависит от того, ради какого класса построена система; выбирать его молчанием нельзя.

Паспорт классификатора

Соберём выводы урока в чек-лист отчёта, который стоит требовать от любого классификатора — своего или чужого. Матрица ошибок на отложенных данных, с указанием их объёма и происхождения. Базовая линия: что даёт тривиальное правило и сколько модель добавляет к нему. Рабочая точка: порог, его вывод из цен ошибок, точность и полнота с интервалами по формулам урока 05. Калибровка: диаграмма надёжности или хотя бы фраза о том, что её проверяли. И срок годности: на каком потоке метрики посчитаны и когда их пересчитают. Пять пунктов помещаются на одну страницу; всё, что отчёт прячет, обычно прячется не случайно.

Противник учится тоже

Всё это время мы молча считали, что завтрашний спам похож на вчерашний. Для спама это предположение ложно по построению: по ту сторону фильтра сидит человек, читающий те же метрики. Слово «free» стало уликой — спамеры пишут «fr33»; цифры выдают — номер прячется в картинку; фильтры выучили картинки — реклама переехала в мессенджеры. Это не дрейф мира из урока о статистике, где ковид просто случился с автобусами; это направленная адаптация против нашей модели.

Отсюда два практических следствия. Первое: метрики фильтра нужно мерить непрерывно, а не однажды при сдаче, и падение полноты на свежем потоке — штатное событие, а не ЧП. Второе: признаки, которые дёшево подделать («нет слова free»), проигрывают признакам, подделка которых ломает сам спам: сообщение без ссылки и номера безвредно, потому что жертве некуда идти. Гонка фильтра и спамера — самый наглядный школьный пример состязательной среды, и всерьёз мы вернёмся к ней в уроке о безопасности ИИ.

Граница, порог и цена: сборка урока

Классификация начинается с признаков: они переводят объект в числа и заранее решают, что модель сможет увидеть. Линейная модель проводит в пространстве признаков границу, сигмоида превращает расстояние до неё в вероятность, и веса читаются как вклады улик при фиксированных остальных — с ловушкой коррелированных признаков. Решение принимает не граница, а порог, и он выводится из цен двух ошибок, как в уроке 05. Отчитываться о качестве нужно матрицей ошибок, точностью и полнотой относительно честной базовой линии; на редком классе доля верных ответов лжёт. Пара «точность-полнота» двумерна, кривая компромисса показывает все рабочие точки сразу, калибровка проверяет, можно ли верить самим вероятностям, а зона отказа покупает честность за время человека. И над всем этим стоит специфика состязательной среды: спам эволюционирует против фильтра, поэтому метрики живут, пока их меряют. В следующем уроке тот же конвейер — признаки, модель, метрика, цена ошибки — повернётся к задачам, где ответ не класс, а число.

Задачи