Байесовская фильтрация спама

Ба́йесовская фильтра́ция спа́ма — метод для фильтрации спама, основанный на применении наивного байесовского классификатора, опирающегося на прямое использование теоремы Байеса. Теорема Байеса названа в честь её автора Томаса Байеса (1702—1761) — английского математика и священника, который первым предложил использование теоремы для корректировки убеждений, основываясь на обновлённых данных.

Первой известной программой, фильтрующей почту с использованием байесовского классификатора, была программа iFile Джейсона Ренни, выпущенная в 1996 году. Программа использовала сортировку почты по папкам^[1]. Первая академическая публикация по наивной байесовской фильтрации спама появилась в 1998 году^[2]. Вскоре после этой публикации была развернута работа по созданию коммерческих фильтров спама^[]. Однако в 2002 г. Пол Грэм смог значительно уменьшить число ложноположительных срабатываний до такой степени, что байесовский фильтр мог использоваться в качестве единственного фильтра спама^[3][4][5].

Модификации основного подхода были развиты во многих исследовательских работах и внедрены в программных продуктах^[6]. Многие современные почтовые клиенты осуществляют байесовское фильтрование спама. Пользователи могут также установить отдельные программы фильтрования почты. Фильтры для почтового сервера — такие, как DSPAM, SpamAssassin, SpamBayes, SpamProbe, Bogofilter, CRM114 — используют методы байесовского фильтрования спама^[5]. Программное обеспечение серверов электронной почты либо включает фильтры в свою поставку, либо предоставляет API для подключения внешних модулей.

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

При проверке вновь пришедшего письма вероятность «спамовости» вычисляется по указанной выше формуле для множества гипотез. В данном случае «гипотезы» — это слова, и для каждого слова «достоверность гипотезы» ${\displaystyle P(A_{i})=N_{word_{i}}/N_{words~total}}$ — доля этого слова в письме, а «зависимость события от гипотезы» ${\displaystyle P(B\mid A_{i})}$ — вычисленный ранее «вес» слова. То есть «вес» письма в данном случае — усреднённый «вес» всех его слов.

Отнесение письма к «спаму» или «не-спаму» производится по тому, превышает ли его «вес» некую планку, заданную пользователем (обычно берут 60-80 %). После принятия решения по письму в базе данных обновляются «веса» для вошедших в него слов.

Почтовые байесовские фильтры основываются на теореме Байеса. Теорема Байеса используется несколько раз в контексте спама:

• в первый раз, чтобы вычислить вероятность, что сообщение — спам, зная, что данное слово появляется в этом сообщении;
• во второй раз, чтобы вычислить вероятность, что сообщение — спам, учитывая все его слова (или соответствующие их подмножества);
• иногда в третий раз, когда встречаются сообщения с редкими словами.

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

Формула, используемая программным обеспечением, чтобы определить это, получена из теоремы Байеса и формулы полной вероятности:

${\displaystyle \Pr(S\mid W)={\frac {\Pr(W\mid S)\cdot \Pr(S)}{\Pr(W)}}={\frac {\Pr(W\mid S)\cdot \Pr(S)}{\Pr(W\mid S)\cdot \Pr(S)+\Pr(W\mid H)\cdot \Pr(H)}}}$

где:

• ${\displaystyle \Pr(S\mid W)}$ — условная вероятность того, что сообщение—спам, при условии, что слово «Replica» находится в нём;
• ${\displaystyle \Pr(S)}$ — полная вероятность того, что произвольное сообщение—спам;
• ${\displaystyle \Pr(W\mid S)}$ — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются спамом;
• ${\displaystyle \Pr(H)}$ — полная вероятность того, что произвольное сообщение не спам (то есть «ham»);
• ${\displaystyle \Pr(W\mid H)}$ — условная вероятность того, что слово «replica» появляется в сообщениях, если они являются «ham».

Недавние статистические исследования^[7] показали, что на сегодняшний день вероятность любого сообщения быть спамом составляет по меньшей мере 80 %: ${\displaystyle \Pr(S)=0.8;\Pr(H)=0.2}$.

Однако большинство байесовских программ обнаружения спама делают предположение об отсутствии априорных предпочтений у сообщения быть «spam», а не «ham», и полагает, что у обоих случаев есть равные вероятности 50 %: ${\displaystyle \Pr(S)=0.5,\Pr(H)=0.5}$.

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

${\displaystyle \Pr(S\mid W)={\frac {\Pr(W\mid S)}{\Pr(W\mid S)+\Pr(W\mid H)}}}$

Значение ${\displaystyle Pr(S|W)}$ называют «спамовостью» слова ${\displaystyle W}$; при этом число ${\displaystyle \Pr(W|S)}$, используемое в приведённой выше формуле, приближённо равно относительной частоте сообщений, которые содержат слово ${\displaystyle W}$ в сообщениях, идентифицированных как спам во время фазы обучения, то есть:

${\displaystyle Pr(W_{i}\mid S)={\frac {\mathrm {count} (M:W_{i}\in M,M\in S)}{\sum _{j}\mathrm {count} (M:W_{j}\in M,M\in S)}}}$

Точно так же ${\displaystyle \Pr(W|H)}$ приближённо равно относительной частоте сообщений, содержащих слово ${\displaystyle W}$ в сообщениях, идентифицированных как «ham» во время фазы обучения.

${\displaystyle Pr(W_{i}\mid H)={\frac {\mathrm {count} (M:W_{i}\in M,M\in H)}{\sum _{j}\mathrm {count} (M:W_{j}\in M,M\in H)}}}$

Для того, чтобы эти приближения имели смысл, набор обучающих сообщений должен быть большим и достаточно представительным. Также желательно, чтобы набор обучающих сообщений соответствовал 50 % гипотезе о перераспределении между спамом и «ham», то есть что наборы сообщений «spam» и «ham» имели один и тот же размер.

Конечно, определение, является ли сообщение «spam» или «ham», базируемой только на присутствии лишь одного определённого слова, подвержено ошибкам. Именно поэтому байесовские фильтры спама пытаются рассмотреть несколько слов и комбинировать их спамовость, чтобы определить полную вероятность того, что сообщение является спамом.

Программные спам-фильтры, построенные на принципах наивного байесовского классификатора, делают «наивное» предположение о том, что события, соответствующие наличию того или иного слова в электронном письме или сообщении, являются независимыми по отношению друг к другу. Это упрощение в общем случае является неверным для естественных языков — таких, как английский, где вероятность обнаружения прилагательного повышается при наличии, к примеру, существительного. Исходя из такого «наивного» предположения, для решения задачи классификации сообщений лишь на 2 класса: ${\displaystyle S}$ (спам) и ${\displaystyle H=\neg S}$ («хэм», то есть не спам) из теоремы Байеса можно вывести следующую формулу оценки вероятности «спамовости» всего сообщения, содержащего слова ${\displaystyle W_{1},W_{2},...W_{N}}$:

${\displaystyle p(S\mid W_{1},W_{2},...W_{N})=}$ [по теореме Байеса] ${\displaystyle ={\frac {p(W_{1},W_{2},...W_{N}\mid S)\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=}$ [так как ${\displaystyle W_{i}}$ предполагаются независимыми] ${\displaystyle =}$

${\displaystyle ={\frac {\prod _{i}p(W_{i}\mid S)\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=}$ [по теореме Байеса] ${\displaystyle ={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)}}\cdot p(S)}{p(W_{1},W_{2},...W_{N})}}=}$ [по формуле полной вероятности] ${\displaystyle =}$

${\displaystyle ={\frac {\prod _{i}{\frac {p(S\mid W_{i})\cdot p(W_{i})}{p(S)}}\cdot p(S)}{\prod _{i}(p(W_{i}\mid S))\cdot p(S)+\prod _{i}(p(W_{i}\mid \neg S))\cdot p(\neg S)}}=}$

${\displaystyle ={\frac {\prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N}}{\prod _{i}(p(S\mid W_{i})\cdot p(W_{i}))\cdot p(S)^{1-N}+\prod _{i}(p(\neg S\mid W_{i})\cdot p(W_{i}))\cdot p(\neg S)^{1-N}}}=}$

${\displaystyle ={\frac {\prod _{i}p(S\mid W_{i})}{\prod _{i}(p(S\mid W_{i}))+\left({\frac {p(\neg S)}{p(S)}}\right)^{1-N}\cdot \prod _{i}p(\neg S\mid W_{i})}}}$

Таким образом, предполагая ${\displaystyle p(S)=p(\neg S)=0.5}$, имеем:

${\displaystyle p={\frac {p_{1}p_{2}\cdots p_{N}}{p_{1}p_{2}\cdots p_{N}+(1-p_{1})(1-p_{2})\cdots (1-p_{N})}}}$

где:

• ${\displaystyle p=Pr(S\mid W_{1},W_{2},...,W_{N})}$ — вероятность, что сообщение, содержащее слова ${\displaystyle W_{1},W_{2},...,W_{N}}$ — спам;
• ${\displaystyle p_{1}}$ — условная вероятность ${\displaystyle p(S\mid W_{1})}$ того, что сообщение — спам, при условии, что оно содержит первое слово (к примеру, «replica»);
• ${\displaystyle p_{2}}$ — условная вероятность ${\displaystyle p(S\mid W_{2})}$ того, что сообщение — спам, при условии, что оно содержит второе слово (к примеру, «watches»);
• и т. д.
• ${\displaystyle p_{N}}$ — условная вероятность ${\displaystyle p(S\mid W_{N})}$ того, что сообщение — спам, при условии, что оно содержит N-е слово (к примеру, «home»).

(Demonstration:^[8])

Результат p обычно сравнивают с некоторым порогом (например, ${\displaystyle 0.5}$), чтобы решить, является ли сообщение спамом или нет. Если p ниже, чем порог, сообщение рассматривают как вероятный «ham», иначе его рассматривают как вероятный спам.

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

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

«Нейтральные» слова — такие, как, «the», «a», «some», или «is» (в английском языке), или их эквиваленты на других языках — могут быть проигнорированы. Вообще говоря, некоторые байесовские фильтры просто игнорируют все слова, у которых спамовость около 0.5, так как в этом случае получается качественно лучшее решение. Учитываются только те слова, спамовость которых около 0.0 (отличительный признак законных сообщений — «ham»), или рядом с 1.0 (отличительный признаки спама). Метод отсева может быть настроен, например, так, чтобы держать только те десять слов в исследованном сообщении, у которых есть самое большое absolute value |0.5 − Pr|.

Некоторые программные продукты принимают во внимание тот факт, что определённое слово появляется несколько раз в проверяемом сообщении^[9], другие этого не делают.

Некоторые программные продукты используют словосочетания — patterns (последовательности слов) вместо изолированных слов естественных языков^[10]. Например, с «контекстным окном» из четырёх слов они вычисляют спамовость словосочетания «Виагра, хорошо для», вместо того, чтобы вычислить спамовости отдельных слов «Виагры», «хорошо», и «для». Этот метод более чувствителен к контексту и лучше устраняет байесовский шум — за счёт большей базы данных.

Кроме «наивного» байесовского подхода, есть и другие способы скомбинировать—объединить отдельные вероятности для различных слов. Эти методы отличаются от «наивного» метода предположениями, которые они делают о статистических свойствах входных данных. Две различные гипотезы приводят к радикально различным формулам для совокупности (объединения) отдельных вероятностей.

Например, для проверки предположения о совокупности отдельных вероятностей, логарифм произведения которых, с точностью до константы, подчиняется распределению хи-квадрат с 2N степенями свободы, можно использовать формулу:

${\displaystyle p=C^{-1}(-2\ln(p_{1}p_{2}\cdots p_{N}),2N)}$

где через C⁻¹ обозначена обратная функция для функции распределения хи-квадрат (см. Обратное распределение хи-квадрат^[англ.]).

Отдельные вероятности могут быть объединены также методами марковской дискриминации.

Данный метод прост (алгоритмы элементарны), удобен (позволяет обходиться без «чёрных списков» и подобных искусственных приёмов), эффективен (после обучения на достаточно большой выборке отсекает до 95—97 % спама), причём в случае любых ошибок его можно дообучать. В общем, есть все показания для его повсеместного использования, что и имеет место на практике — на его основе построены практически все современные спам-фильтры.

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

Ещё один не принципиальный недостаток, связанный с реализацией — метод работает только с текстом. Зная об этом ограничении, спамеры стали вкладывать рекламную информацию в картинку. Текст же в письме либо отсутствует, либо не несёт смысла. Против этого приходится пользоваться либо средствами распознавания текста («дорогая» процедура, применяется только при крайней необходимости), либо старыми методами фильтрации — «чёрные списки» и регулярные выражения (так как такие письма часто имеют стереотипную форму).

• Байесовское программирование

• Guzella T. S., Caminhas W. M.  A review of machine learning approaches to Spam filtering // Expert Systems with Applications. — 2009. — Vol. 36, no. 7. — P. 10206—10222. — doi:10.1016/j.eswa.2009.02.037.
• Metsis V., Androutsopoulos I., Paliouras G. . Spam Filtering with Naive Bayes — Which Naive Bayes? // CEAS 2006: Third Conference on Email and Anti-Spam, July 27-28, 2006, Mountain View, California, USA. — 2006.
• Sahami M., Dumais S., Heckerman D., Horvitz E.  A Bayesian approach to filtering junk email // AAAI Workshop on Learning for Text Categorization. Technical Report. — 1998.

• Paul Graham.  A plan for spam Архивная копия от 4 апреля 2004 на Wayback Machine // Персональный сайт Пола Грэхема.