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

Давайте предположим, что подозреваемое сообщение содержит слово «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⁻¹ обозначена обратная функция для функции распределения хи-квадрат (см. Обратное распределение хи-квадрат).

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