Better Bayesian Filtering

January 2003

Январь 2003

(This article was given as a talk at the 2003 Spam Conference.
It describes the work I've done to improve the performance of
the algorithm described in A Plan for Spam,
and what I plan to do in the future.)

(Эта статья была прочитана как доклад на Spam Conference 2003. В ней описана работа, которую я проделал, чтобы улучшить производительность алгоритма, описанного в A Plan for Spam, и что я планирую сделать в будущем.)

The first discovery I'd like to present here is an algorithm for
lazy evaluation of research papers. Just
write whatever you want and don't cite any previous work, and
indignant readers will send you references to all the papers you
should have cited. I discovered this algorithm
after ``A Plan for Spam'' [1] was on Slashdot.

Первое открытие, которое я хотел бы здесь представить, — это алгоритм ленивого вычисления научных статей. Просто пишите всё, что захотите, не цитируя никаких предыдущих работ, и возмущённые читатели сами пришлют вам ссылки на все статьи, которые вам следовало бы процитировать. Я обнаружил этот алгоритм после того, как «A Plan for Spam» [1] попала на Slashdot.

Spam filtering is a subset of text classification,
which is a well established field, but the first papers about
Bayesian
spam filtering per se seem to have been two
given at the same conference in 1998,
one by Pantel and Lin [2],
and another by a group from
Microsoft Research [3].

Спам-фильтрация — это подраздел классификации текстов, хорошо устоявшейся области, но первыми работами именно о байесовской спам-фильтрации, по-видимому, были две статьи, представленные на одной и той же конференции в 1998 году: одна за авторством Pantel и Lin [2], а другая — группы из Microsoft Research [3].

When I heard about this work I was a bit surprised. If
people had been onto Bayesian filtering four years ago,
why wasn't everyone using it?
When I read the papers I found out why. Pantel and Lin's filter was the
more effective of the two, but it
only caught 92% of spam, with 1.16% false positives.

Когда я услышал об этих работах, я был немного удивлён. Если люди занимались байесовской фильтрацией ещё четыре года назад, почему ею не пользовались все подряд? Прочитав статьи, я понял почему. Фильтр Pantel и Lin был более эффективным из двух, но он ловил лишь 92% спама при 1,16% ложных срабатываний.

When I tried writing a Bayesian spam filter,
it caught 99.5% of spam with less than .03% false
positives [4].
It's always alarming when two people
trying the same experiment get widely divergent results.
It's especially alarming here because those two sets of numbers
might yield opposite conclusions.
Different users have different requirements, but I think for
many people a filtering rate of 92% with 1.16% false positives means
that filtering is not an acceptable solution, whereas
99.5% with less than .03% false positives means that it is.

Когда я попробовал написать байесовский спам-фильтр, он ловил 99,5% спама при менее чем 0,03% ложных срабатываний [4]. Всегда тревожно, когда два человека, ставя один и тот же эксперимент, получают сильно расходящиеся результаты. Особенно тревожно здесь, потому что эти два набора чисел могут привести к противоположным выводам. У разных пользователей разные требования, но я думаю, что для многих людей уровень фильтрации 92% при 1,16% ложных срабатываний означает, что фильтрация — неприемлемое решение, тогда как 99,5% при менее чем 0,03% ложных срабатываний означает, что она приемлема.

So why did we get such different numbers?
I haven't tried to reproduce Pantel and Lin's results, but
from reading the paper I see five things that probably account
for the difference.

Так почему же мы получили настолько разные числа? Я не пытался воспроизвести результаты Pantel и Lin, но, читая их статью, я вижу пять вещей, которые, вероятно, объясняют это различие.

One is simply that they trained their filter on very little
data: 160 spam and 466 nonspam mails.
Filter performance should still be climbing with data
sets that small. So their numbers may not even be an accurate
measure of the performance of their algorithm, let alone of
Bayesian spam filtering in general.

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

But I think the most important difference is probably
that they ignored message headers. To anyone who has worked
on spam filters, this will seem a perverse decision.
And yet in the very first filters I tried writing, I ignored the
headers too. Why? Because I wanted to keep the problem neat.
I didn't know much about mail headers then, and they seemed to me
full of random stuff. There is a lesson here for filter
writers: don't ignore data. You'd think this lesson would
be too obvious to mention, but I've had to learn it several times.

Но самым важным различием, я думаю, вероятно, является то, что они игнорировали заголовки писем. Любому, кто работал над спам-фильтрами, это покажется нелепым решением. И всё же в самых первых фильтрах, которые я пытался написать, я тоже игнорировал заголовки. Почему? Потому что я хотел сохранить задачу аккуратной. Тогда я мало что знал о заголовках писем, и они казались мне набором случайного мусора. Здесь есть урок для тех, кто пишет фильтры: не игнорируйте данные. Казалось бы, этот урок слишком очевиден, чтобы о нём упоминать, но мне приходилось усваивать его несколько раз.

Third, Pantel and Lin stemmed the tokens, meaning they reduced e.g. both
``mailing'' and ``mailed'' to the root ``mail''. They may
have felt they were forced to do this by the small size
of their corpus, but if so this is a kind of premature
optimization.

В-третьих, Pantel и Lin применяли стемминг токенов, то есть, например, сводили и «mailing», и «mailed» к корню «mail». Возможно, они чувствовали, что вынуждены делать это из-за малого размера их корпуса, но если так, то это разновидность преждевременной оптимизации.

Fourth, they calculated probabilities differently.
They used all the tokens, whereas I only
use the 15 most significant. If you use all the tokens
you'll tend to miss longer spams, the type where someone tells you their life
story up to the point where they got rich from some multilevel
marketing scheme. And such an algorithm
would be easy for spammers to spoof: just add a big
chunk of random text to counterbalance the spam terms.

В-четвёртых, они вычисляли вероятности иначе. Они использовали все токены, тогда как я использую лишь 15 самых значимых. Если использовать все токены, вы будете склонны пропускать более длинные спам-письма — те, где кто-то рассказывает вам историю своей жизни вплоть до момента, когда разбогател на какой-нибудь схеме многоуровневого маркетинга. И такой алгоритм было бы легко обмануть спамерам: достаточно добавить большой кусок случайного текста, чтобы уравновесить спам-термины.

Finally, they didn't bias against false positives.
I think
any spam filtering algorithm ought to have a convenient
knob you can twist to decrease the
false positive rate at the expense of the filtering rate.
I do this by counting the occurrences
of tokens in the nonspam corpus double.

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

I don't think it's a good idea to treat spam filtering as
a straight text classification problem. You can use
text classification techniques, but solutions can and should
reflect the fact that the text is email, and spam
in particular. Email is not just text; it has structure.
Spam filtering is not just classification, because
false positives are so much worse than false negatives
that you should treat them as a different kind of error.
And the source of error is not just random variation, but
a live human spammer working actively to defeat your filter.

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

Tokens

Токены

Another project I heard about
after the Slashdot article was Bill Yerazunis'
CRM114 [5].
This is the counterexample to the design principle I
just mentioned. It's a straight text classifier,
but such a stunningly effective one that it manages to filter
spam almost perfectly without even knowing that's
what it's doing.

Ещё один проект, о котором я узнал после статьи на Slashdot, — это CRM114 [5] Билла Еразуниса. Это контрпример к принципу проектирования, который я только что упомянул. Это чистый текстовый классификатор, но настолько ошеломляюще эффективный, что ему удаётся фильтровать спам почти идеально, даже не зная, что он именно этим занимается.

Once I understood how CRM114 worked, it seemed
inevitable that I would eventually have to move from filtering based
on single words to an approach like this. But first, I thought,
I'll see how far I can get with single words. And the answer is,
surprisingly far.

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

Mostly I've been working on smarter tokenization. On
current spam, I've been able to achieve filtering rates that
approach CRM114's. These techniques are mostly orthogonal to Bill's;
an optimal solution might incorporate both.

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

``A Plan for Spam'' uses a very simple
definition of a token. Letters, digits, dashes, apostrophes,
and dollar signs are constituent characters, and everything
else is a token separator. I also ignored case.

В «A Plan for Spam» используется очень простое определение токена. Буквы, цифры, дефисы, апострофы и знаки доллара — это составляющие символы, а всё остальное — разделители токенов. Регистр я тоже игнорировал.

Now I have a more complicated definition of a token:

Теперь у меня более сложное определение токена:

Case is preserved.

Регистр сохраняется.

Exclamation points are constituent characters.

Восклицательные знаки — составляющие символы.

Periods and commas are constituents if they occur
between two digits. This lets me get ip addresses
and prices intact.

Точки и запятые — составляющие символы, если они стоят между двумя цифрами. Это позволяет мне получать ip-адреса и цены в неповреждённом виде.

A price range like $20-25 yields two tokens,
$20 and $25.

Ценовой диапазон вроде $20-25 даёт два токена: $20 и $25.

Tokens that occur within the
To, From, Subject, and Return-Path lines, or within urls,
get marked accordingly. E.g. ``foo'' in the Subject line
becomes ``Subject*foo''. (The asterisk could
be any character you don't allow as a constituent.)

Токены, встречающиеся в строках To, From, Subject и Return-Path или внутри url, помечаются соответствующим образом. Например, «foo» в строке Subject становится «Subject*foo». (В роли звёздочки мог бы быть любой символ, который вы не разрешаете в качестве составляющего.)

Such measures increase the filter's vocabulary, which
makes it more discriminating. For example, in the current
filter, ``free'' in the Subject line
has a spam probability of 98%, whereas the same token
in the body has a spam probability of only 65%.

Подобные меры увеличивают словарь фильтра, что делает его более избирательным. Например, в текущем фильтре «free» в строке Subject имеет вероятность спама 98%, тогда как тот же токен в теле письма имеет вероятность спама лишь 65%.

Here are some of the current probabilities [6]:

Вот некоторые из текущих вероятностей [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

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