Better Bayesian Filtering
В январе 2003 года Пол Грэм представил доклад на Spam Conference об улучшении байесовского спам-фильтра, описанного в эссе «A Plan for Spam». Он отмечает, что первые работы по байесовской фильтрации появились ещё в 1998 году (Pantel и Lin, а также группа из Microsoft Research), но фильтр Pantel и Lin ловил лишь 92% спама при 1,16% ложных срабатываний, тогда как фильтр Грэма достигал 99,5% при менее чем 0,03% ложных срабатываний. Расхождение он объясняет пятью причинами: малый объём обучающих данных, игнорирование заголовков писем, стемминг токенов, использование всех токенов вместо 15 самых значимых и отсутствие смещения против ложных срабатываний. Грэм подчёркивает, что спам-фильтрацию нельзя сводить к чистой классификации текста, поскольку письмо имеет структуру, ложные срабатывания гораздо хуже пропусков, а противником выступает живой спамер. Также он рассказывает о более сложной токенизации (сохранение регистра, обработка цен и IP-адресов, пометка токенов из полей To, From, Subject) и упоминает проект CRM114 Билла Еразуниса как мощный пример чистого текстового классификатора.
Январь 2003
(Эта статья была прочитана как доклад на Spam Conference 2003. В ней описана работа, которую я проделал, чтобы улучшить производительность алгоритма, описанного в A Plan for Spam, и что я планирую сделать в будущем.)
Первое открытие, которое я хотел бы здесь представить, — это алгоритм ленивого вычисления научных статей. Просто пишите всё, что захотите, не цитируя никаких предыдущих работ, и возмущённые читатели сами пришлют вам ссылки на все статьи, которые вам следовало бы процитировать. Я обнаружил этот алгоритм после того, как «A Plan for Spam» [1] попала на Slashdot.
Спам-фильтрация — это подраздел классификации текстов, хорошо устоявшейся области, но первыми работами именно о байесовской спам-фильтрации, по-видимому, были две статьи, представленные на одной и той же конференции в 1998 году: одна за авторством Pantel и Lin [2], а другая — группы из Microsoft Research [3].
Когда я услышал об этих работах, я был немного удивлён. Если люди занимались байесовской фильтрацией ещё четыре года назад, почему ею не пользовались все подряд? Прочитав статьи, я понял почему. Фильтр Pantel и Lin был более эффективным из двух, но он ловил лишь 92% спама при 1,16% ложных срабатываний.
Когда я попробовал написать байесовский спам-фильтр, он ловил 99,5% спама при менее чем 0,03% ложных срабатываний [4]. Всегда тревожно, когда два человека, ставя один и тот же эксперимент, получают сильно расходящиеся результаты. Особенно тревожно здесь, потому что эти два набора чисел могут привести к противоположным выводам. У разных пользователей разные требования, но я думаю, что для многих людей уровень фильтрации 92% при 1,16% ложных срабатываний означает, что фильтрация — неприемлемое решение, тогда как 99,5% при менее чем 0,03% ложных срабатываний означает, что она приемлема.
Так почему же мы получили настолько разные числа? Я не пытался воспроизвести результаты Pantel и Lin, но, читая их статью, я вижу пять вещей, которые, вероятно, объясняют это различие.
Первая — попросту в том, что они обучали свой фильтр на очень небольшом объёме данных: 160 спам-писем и 466 не-спам-писем. На таких маленьких наборах данных производительность фильтра должна всё ещё расти. Так что их числа могут даже не быть точной мерой производительности их алгоритма, не говоря уже о байесовской спам-фильтрации в целом.
Но самым важным различием, я думаю, вероятно, является то, что они игнорировали заголовки писем. Любому, кто работал над спам-фильтрами, это покажется нелепым решением. И всё же в самых первых фильтрах, которые я пытался написать, я тоже игнорировал заголовки. Почему? Потому что я хотел сохранить задачу аккуратной. Тогда я мало что знал о заголовках писем, и они казались мне набором случайного мусора. Здесь есть урок для тех, кто пишет фильтры: не игнорируйте данные. Казалось бы, этот урок слишком очевиден, чтобы о нём упоминать, но мне приходилось усваивать его несколько раз.
В-третьих, Pantel и Lin применяли стемминг токенов, то есть, например, сводили и «mailing», и «mailed» к корню «mail». Возможно, они чувствовали, что вынуждены делать это из-за малого размера их корпуса, но если так, то это разновидность преждевременной оптимизации.
В-четвёртых, они вычисляли вероятности иначе. Они использовали все токены, тогда как я использую лишь 15 самых значимых. Если использовать все токены, вы будете склонны пропускать более длинные спам-письма — те, где кто-то рассказывает вам историю своей жизни вплоть до момента, когда разбогател на какой-нибудь схеме многоуровневого маркетинга. И такой алгоритм было бы легко обмануть спамерам: достаточно добавить большой кусок случайного текста, чтобы уравновесить спам-термины.
Наконец, они не вводили смещение против ложных срабатываний. Я считаю, что у любого алгоритма спам-фильтрации должна быть удобная ручка, которую можно покрутить, чтобы снизить долю ложных срабатываний за счёт уровня фильтрации. Я делаю это, считая вхождения токенов в не-спам-корпусе в двойном размере.
Я не думаю, что хорошая идея — рассматривать спам-фильтрацию как чистую задачу классификации текста. Можно использовать методы классификации текста, но решения могут и должны учитывать тот факт, что текст — это электронная почта, и спам в частности. Письмо — это не просто текст; у него есть структура. Спам-фильтрация — это не просто классификация, потому что ложные срабатывания настолько хуже ложных пропусков, что их следует рассматривать как ошибку иного рода. И источник ошибки — не просто случайные колебания, а живой человек-спамер, активно работающий над тем, чтобы обойти ваш фильтр.
Токены
Ещё один проект, о котором я узнал после статьи на Slashdot, — это CRM114 [5] Билла Еразуниса. Это контрпример к принципу проектирования, который я только что упомянул. Это чистый текстовый классификатор, но настолько ошеломляюще эффективный, что ему удаётся фильтровать спам почти идеально, даже не зная, что он именно этим занимается.
Как только я понял, как работает CRM114, мне показалось неизбежным, что в конце концов мне придётся перейти от фильтрации на основе отдельных слов к подходу вроде этого. Но сначала, подумал я, посмотрю, как далеко я смогу продвинуться с отдельными словами. И ответ — на удивление далеко.
В основном я работал над более умной токенизацией. На современном спаме мне удалось достичь уровней фильтрации, приближающихся к уровню CRM114. Эти методы по большей части ортогональны методам Билла; оптимальное решение могло бы включать оба.
В «A Plan for Spam» используется очень простое определение токена. Буквы, цифры, дефисы, апострофы и знаки доллара — это составляющие символы, а всё остальное — разделители токенов. Регистр я тоже игнорировал.
Теперь у меня более сложное определение токена:
Регистр сохраняется.
Восклицательные знаки — составляющие символы.
Точки и запятые — составляющие символы, если они стоят между двумя цифрами. Это позволяет мне получать ip-адреса и цены в неповреждённом виде.
Ценовой диапазон вроде $20-25 даёт два токена: $20 и $25.
Токены, встречающиеся в строках To, From, Subject и Return-Path или внутри url, помечаются соответствующим образом. Например, «foo» в строке Subject становится «Subject*foo». (В роли звёздочки мог бы быть любой символ, который вы не разрешаете в качестве составляющего.)
Подобные меры увеличивают словарь фильтра, что делает его более избирательным. Например, в текущем фильтре «free» в строке Subject имеет вероятность спама 98%, тогда как тот же токен в теле письма имеет вероятность спама лишь 65%.
Вот некоторые из текущих вероятностей [6]:
Subject*FREE 0.9999 free!! 0.9999 To*free 0.9998 Subject*free 0.9782 free! 0.9199 Free 0.9198 Url*free 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546