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

{{rq|sources|cleanup|style|isbn}}
'''Ба́йесовская фильтра́ция спа́ма''' — метод для [[Спам#Фильтрация|фильтрации спама]], основанный на применении [[Наивный байесовский классификатор|наивного байесовского классификатора]], опирающегося на прямое использование [[Теорема Байеса|теоремы Байеса]]. Теорема Байеса названа в честь её автора [[Байес, Томас|Томаса Байеса]] (1702—1761) — английского математика и священника, который первым предложил использование теоремы для корректировки убеждений, основываясь на обновлённых данных.

== История ==
Первой известной программой, фильтрующей [[электронная почта|почту]] с использованием байесовского классификатора, была программа iFile Джейсона Ренни, выпущенная в 1996 году. Программа использовала сортировку почты по папкам<ref>{{cite web|url=http://people.csail.mit.edu/jrennie/ifile/old/README-0.1A|author=Jason Rennie|title=ifile|year=1996|archiveurl=https://www.webcitation.org/6BfV6cMYA?url=http://people.csail.mit.edu/jrennie/ifile/old/README-0.1A|archivedate=2012-10-25}}</ref>. Первая академическая публикация по наивной байесовской фильтрации спама появилась в 1998 году{{sfn|Sahami, Dumais, Heckerman, Horvitz|1998}}. Вскоре после этой публикации была развернута работа по созданию коммерческих фильтров спама{{Нет АИ|16|9|2012}}. Однако в 2002 г. Пол Грэм смог значительно уменьшить число ложноположительных срабатываний до такой степени, что байесовский фильтр мог использоваться в качестве единственного фильтра спама<ref>Paul Graham (2003), [http://www.paulgraham.com/better.html Better Bayesian filtering] {{Wayback|url=http://www.paulgraham.com/better.html |date=20100621011536 }}</ref><ref>Brian Livingston (2002), [http://www.infoworld.com/t/business/paul-graham-provides-stunning-answer-spam-e-mails-295 Paul Graham provides stunning answer to spam e-mails] {{Wayback|url=http://www.infoworld.com/t/business/paul-graham-provides-stunning-answer-spam-e-mails-295 |date=20100610014352 }}</ref>{{sfn|Guzella, Caminhas|2009}}.

Модификации основного подхода были развиты во многих исследовательских работах и внедрены в программных продуктах<ref>{{cite web|url=http://kb.mozillazine.org/Junk_Mail_Controls|author=|title=Junk Mail Controls|publisher=MozillaZine|date=2009-11|archiveurl=https://www.webcitation.org/6BfV72i2w?url=http://kb.mozillazine.org/Junk_Mail_Controls|archivedate=2012-10-25}}</ref>. Многие современные почтовые клиенты осуществляют байесовское фильтрование спама. Пользователи могут также установить отдельные программы фильтрования почты. Фильтры для почтового сервера — такие, как [[DSPAM]], [[SpamAssassin]], [[SpamBayes]], [[SpamProbe]], [[Bogofilter]], CRM114 — используют методы байесовского фильтрования спама{{sfn|Guzella, Caminhas|2009}}. Программное обеспечение серверов электронной почты либо включает фильтры в свою поставку, либо предоставляет [[API]] для подключения внешних модулей.

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

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

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

== Математические основы ==
Почтовые байесовские фильтры основываются на теореме Байеса. Теорема Байеса используется несколько раз в контексте спама:
* в первый раз, чтобы вычислить вероятность, что сообщение — спам, зная, что данное слово появляется в этом сообщении;
* во второй раз, чтобы вычислить вероятность, что сообщение — спам, учитывая все его слова (или соответствующие их подмножества);
* иногда в третий раз, когда встречаются сообщения с редкими словами.

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

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

:<math>\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)}</math>

где:

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

=== ''Спамовость'' слова ===
Недавние статистические исследования<ref>{{Cite web |url=http://www.certmag.com/read.php?in=5056 |title=More Than 90 Percent of E-Mails in Third Quarter (of 2008) Were Spam, Certification Magazine |access-date=2012-09-16 |archive-date=2012-09-23 |archive-url=https://web.archive.org/web/20120923184501/http://www.certmag.com/read.php?in=5056 |deadlink=no }}</ref> показали, что на сегодняшний день вероятность любого сообщения быть спамом составляет по меньшей мере 80 %: <math> \Pr(S) = 0.8 ;  \Pr(H) = 0.2</math>.

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

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

:<math>\Pr(S\mid W) = \frac{\Pr(W\mid S)}{\Pr(W\mid S) + \Pr(W\mid H)}</math>

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

:<math>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)}</math>

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

:<math>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)}</math>

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

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

=== Объединение индивидуальных вероятностей ===
Программные спам-фильтры, построенные на принципах [[Наивный байесовский классификатор|наивного байесовского классификатора]], делают «наивное» предположение о том, что [[Пространство элементарных событий|события]], соответствующие наличию того или иного слова в электронном письме или сообщении, являются [[Независимость (теория вероятностей)|независимыми]] по отношению друг к другу. Это упрощение в общем случае является неверным для естественных языков — таких, как английский, где вероятность обнаружения прилагательного повышается при наличии, к примеру, существительного. Исходя из такого «наивного» предположения, для решения задачи классификации сообщений лишь на 2 класса: <math>S</math> (спам) и <math>H = \neg S</math> («хэм», то есть не спам) из теоремы Байеса можно вывести следующую формулу оценки вероятности «спамовости» всего сообщения, содержащего слова <math>W_1, W_2, ... W_N</math>:

:<math>p(S\mid W_1, W_2, ... W_N) =</math> [по теореме Байеса] <math>= \frac{p(W_1, W_2, ... W_N\mid S) \cdot p(S)}{p(W_1, W_2, ... W_N)} = </math> [так как <math>W_i</math> предполагаются независимыми] <math>=</math>

:<math>= \frac{\prod_{i} p(W_i\mid S) \cdot p(S)}{p(W_1, W_2, ... W_N)} = </math> [по теореме Байеса] <math>=\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)} =</math> [по [[Формула полной вероятности|формуле полной вероятности]]] <math>=</math>

:<math>=\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)} =</math>

:<math>= \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}} = </math>

:<math>= \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)}</math>

Таким образом, предполагая <math>p(S) = p(\neg S) = 0.5</math>, имеем:

: <math>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)}</math>

где:

*<math>p = Pr(S \mid W_1, W_2, ..., W_N)</math> — вероятность, что сообщение, содержащее слова <math>W_1, W_2, ..., W_N</math> — спам;
* <math>p_1</math> — условная вероятность <math>p(S\mid W_1)</math> того, что сообщение — спам, при условии, что оно содержит первое слово (к примеру, «replica»);
* <math>p_2</math> — условная вероятность <math>p(S\mid W_2)</math> того, что сообщение — спам, при условии, что оно содержит второе слово (к примеру, «watches»);
* и т. д.
* <math>p_N</math> — условная вероятность <math>p(S\mid W_N)</math> того, что сообщение — спам, при условии, что оно содержит ''N''-е слово (к примеру, «home»).

(Demonstration:<ref>{{Cite web|url=http://www.mathpages.com/home/kmath267.htm|title=Combining probabilities|archiveurl=https://www.webcitation.org/66yGdTo48?url=http://www.mathpages.com/home/kmath267.htm|archivedate=2012-04-16}} at MathPages</ref>)

Результат ''p'' обычно сравнивают с некоторым порогом (например, <math>0.5</math>), чтобы решить, является ли сообщение спамом или нет. Если ''p'' ниже, чем порог, сообщение рассматривают как вероятный «ham», иначе его рассматривают как вероятный спам.

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

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

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

Некоторые программные продукты принимают во внимание тот факт, что определённое слово появляется несколько раз в проверяемом сообщении<ref>{{Cite web|url=http://spamprobe.sourceforge.net/paper.html|author=Brian Burton|title=SpamProbe - Bayesian Spam Filtering Tweaks|date=2003|archiveurl=https://www.webcitation.org/66yGdtOlm?url=http://spamprobe.sourceforge.net/paper.html|archivedate=2012-04-16}}</ref>, другие этого не делают.

Некоторые программные продукты используют ''словосочетания'' — ''patterns'' (последовательности слов) вместо изолированных слов естественных языков<ref>{{Cite web|url=http://bnr.nuclearelephant.com/l|author=Jonathan A. Zdziarski|title=Bayesian Noise Reduction: Contextual Symmetry Logic Utilizing Pattern Consistency Analysis|date=2004|deadlink=unknown-host}}{{Недоступная ссылка|date=Сентябрь 2017 |bot=InternetArchiveBot }}</ref>. Например, с «контекстным окном» из четырёх слов они вычисляют спамовость словосочетания «Виагра, хорошо для», вместо того, чтобы вычислить спамовости отдельных слов «Виагры», «хорошо», и «для». Этот метод более чувствителен к контексту и лучше устраняет [[байесовский шум]] — за счёт большей базы данных.

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

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

: <math>p = C^{-1}(-2 \ln(p_1 p_2 \cdots p_N), 2N)</math>

где через ''C''<sup>−1</sup> обозначена обратная функция для функции распределения хи-квадрат (см. {{нп5|Обратное распределение хи-квадрат|||Inverse-chi-squared distribution}}).

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

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

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

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

== См. также ==
* [[Байесовское программирование]]

== Примечания ==
{{примечания}}

== Литература ==
* {{статья|автор=Guzella T. S., Caminhas W. M. |заглавие=A review of machine learning approaches to Spam filtering|издание=Expert Systems with Applications|год=2009|volume=36, no. 7|pages=10206—10222|doi=10.1016/j.eswa.2009.02.037|ref=Guzella, Caminhas}}
* {{книга|автор=Metsis V., Androutsopoulos I., Paliouras G. |часть=Spam Filtering with Naive Bayes — Which Naive Bayes?|ссылка часть=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.5542&rep=rep1&type=pdf|заглавие=CEAS 2006: Third Conference on Email and Anti-Spam, July 27-28, 2006, Mountain View, California, USA|год=2006|ref=Metsis, Androutsopoulos, Paliouras}} <!-- про разные версии наивного байеса -->
* {{статья|автор=Sahami M., Dumais S., Heckerman D., Horvitz E. |заглавие=A Bayesian approach to filtering junk email|ссылка=http://research.microsoft.com/en-us/um/people/horvitz/junkfilter.htm|издание=AAAI Workshop on Learning for Text Categorization. Technical Report|год=1998|ref=Sahami, Dumais, Heckerman, Horvitz}}

== Ссылки ==
* ''Paul Graham.''  [http://www.paulgraham.com/spam.html A plan for spam] {{Wayback|url=http://www.paulgraham.com/spam.html |date=20040404013856 }} // Персональный сайт Пола Грэхема. <!-- статья про практику, но теоретически очень слабая, не стоит основываться на материале из неё — [[Участник:X7q]] -->

[[Категория:Фильтрация спама]]