Как определяют спам по формуле Байеса?

[Dims]

Формула Байеса.

P(A|B) = \frac{P(B | A) P(A)}{P(B)}

Допустим, у нас есть таблица слов. Нам известно, сколько каких слов встречалось в письмах и сколько всего было писем. Таким образом, мы можем вычислить вероятность встречания каждого слова.

Кроме того, у нас есть оценка пользователя, какие письма были спамом. Таким образом мы можем рассчитать в общем вероятность того, что данное письмо является спамом.

Рассмотрим слово "покупайте".

P(A) - вероятность (вообще) того, что письмо окажется спамом.
P(B) - вероятность (вообще) того, что встретится слово "покупайте".
P(B|A) - вероятность того, что слово "покупайте" встретится в спамовом письме.

Формула Байеса даёт нам возможность рассчитать

P(A|B) - вероятность того, что письмо является спамом если в нём встретилось слово "покупайте".

Правильно?

Но как обобщить на много слов? Допустим, у нас есть данные не только по слову "покупайте", но и по слову "английский".

Что теперь делать? Считать вероятности сочетаний?

Если считать, что P(B) - это произведение вероятностей встречания слов "покупайте" и "английский", то не получится ли, что формула может дать величину больше 1?

Добавлено спустя 1 час 21 минуту 57 секунд:

Допустим, мы получили два письма. В одном было одно слово, в другом другое. Вероятность каждого слова 50%.

Допустим, второе письме, допустим, со словом "покупайте", было объявлено спамом. То есть, вроятность спама по нашим данным тоже пока 50%.

Получается, для второго письма

P(B|A) - вероятность наличия "покупайте" без "английский" в спаме 100%.
P(A) - вероятность спама 50%
P(B) - вероятность наличия одного слова и присутствия другого всего, полученная путём перемножения вероятностей равна 25%.

В итоге формула дает 2, то есть, больше 1.

Получается, что причина в том, что мы пренебрегли зависимостью между словами. Но не можем же мы учитывать все комбинации всех слов! Как же быть?

[Brukvalub]

Dims в сообщении #156211 писал(а):

В итоге формула дает 2, то есть, больше 1.

Ничего не понял, но особенно не понял, как произведение двух чисел из отрезка [0 , 1] получилось равным 2?

[Dims]

Там же не произведение, там P(B) в знаменателе.

[PAV]

Детали не читал, но условная вероятность так же, как и обычная, не может получиться больше 1. Где-то ошибка.

Добавлено спустя 1 минуту 44 секунды:

По поводу же основного вопроса - он сложный. Честное математическое решение должно учитывать все комбинации, но это нереально. На практике решается различными эвристическими методами.

(Если есть хорошее математическое решение, то я бы и сам очень хотел на него посмотреть).

[Dims]

Об этом и речь. Имея статистику по каждому слову в отдельности, мы можем лишь предположить, каковы вероятности P(B) и P(B|A). Если просто перемножить вероятности отдельных слов, то получится, что мы предположили, что они независимы друг от друга. Поскольку это заведомо не так, вероятности P(B) и P(B|A) окажутся, во-первых, заниженными, а во-вторых, могут нарушить математические соотношения друг с другом, что и даст результат в формуле Байеса больше 1.

[PAV]

Я не понимаю Ваших обозначений и выводов.

Произведение $P(B|A)\cdot P(A)$ равно вероятности пересечения $P(AB)$, которая не может быть меньше $P(B)$. Таким образом, заданные Вами числа не являются корректно заданными вероятностями. С там же успехом можно объявить какую-нибудь вероятность равной 5 а потом удивляться, что странные результаты получаются.

[Dims]

PAV писал(а):

Я не понимаю Ваших обозначений

Почему-то frac не срабатывает.

Мы не знаем вероятности пересечения, мы знаем только P(A) (вероятность спама), а так же вероятности отдельных слов вообще и их вероятности в спаме.

Ещё раз, мы получили два письма со следующими характеристиками (плюс означает наличие, минус отсутствие):

1: английский+ покупайте- спам-
2: английский- покупайте+ спам+

Оцениваем верояность как "в частности" делить на "всего", получаем, что вероятности:

1) слова английский = 50%
2) слова покупайте = 50%
3) спама = 50%

Вероятности слов в спаме:

1) английский = 0%
2) покупайте = 100%.

Для формулы нам нужно P(B|A), P(B) и P(A), из которых мы знаем только P(A) = 50%

P(B|A) и P(B) мне не пришло в голову оценивать никак, кроме как через произведение вероятностей отдельных слов.

Получается P(B|A) = 100%, P(B)=25%.

Получается 1*0,5/0,25 = 2.

[PAV]

Очевидная ошибка. Смотрите:
P(A) = 50% -> половина писем являются спамом
P(B|A) = 100% -> все спамовые письма обладают признаком B.

Отсюда очевидно вытекает, что не менее половины писем должны обладать признаком B.

А у Вас P(B) = 25%. Этого быть не может.

Ошибку у себя поищите сами.

[Pavia]

$A$- событие то что письмо является спамом
$H_i$- гипотиза о том что это(i-ое) слово спамовое. $i$ - по индексу из списка всех слов.

Если у нас имеется полная группа гипотез $H_1,H_2, …, H_n$. И событие $A$ то:
$P(A)=\Sigma(P(H_i)*P(A/H_i))$ -Формула полной вероятности
$P(A)=M_A /M $
$M_A$- число спамовых писем
$M$ -всего писем

$P(H_i)=N_{Hi}/N_i$ вероятность того что слово является спамовым. Другими словами вероятность того что гипотиза выполнилась, те это вероятность поподания слово в спамовое письмо.

$N_{Hi}$- число таких(i-ых) слов встретившихся во всех спамовых письмах
$N_i$ - всего таких(i-ых) слов встретившихся во всех письмах

$P(A/Hi)=N_{HiA}/N_{Hi}$ - называется условной вероятностью, читается как: вероятность наступления события $A$ при условии предварительного наступления события $H_i$.

$N_{HiA}$ - число таких(i-ых) слов прикоторым это письмо окажется спамовым. Его мы незнаем
А следовательно нам нужно найти $P(A/H_i)$

Теорема об умножении вероятностей взаимозависимых событий $A$ и $H$.

$P(AH)=P(A)*P(H/A)=P(H)*P(A/H)$
Откуда

$P(A/H_i)=P(A)*P(H_i/A)/P(H_i)$

$P(H_i/A)= N_{Hi}/N_A$ Отвечает на вопрос: если произошло событие A, то с какой вероятностью его породило одно (любое) из событий $H_1,H_2, …, H_n$?

$N_{Hi}$ - смотри выше
$N_A$ - число слов во всех спамовых письмах


Теперь пусть у нас есть письмо со спамом.
Нужно определить является ли оно спамовым.
Для этого посчитать
$P(A')=\Sigma(P(H'_i)*P(A/H_i))$
И выбрать порог. Порог надо брать относитьльно $P(A)$
$P(H'_i)=N_{H'i}/N_i$
$N_{H'i}$ - число этих (i-ых) слов в данном одном письме.
$N_i$ - всего таких(i-ых) слов встретившихся во всех письмах

Добавлено спустя 2 часа 10 минут 1 секунду:

Или
$A$- событие то что письмо является спамом
$Hi$- гипотиза о том что это(i-ое) слово есть в письме
Тогда вместо $N_i$ будет $N$ - всего слов во всех письмах.
$N_{Hi}$- поменяет смысл на, колличество встретившихся этих(i-ых) слов во всех письмах.

[PAV]

Подробно в написанное не вникал, поскольку мне лично тяжело и не доставляет большого удовольствия читать тексты с таким количеством синтаксических ошибок. Глаза ломает.

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

[Pavia]

PAV
Я старался убрать ошибки .

Цитата:

Бросилось в глаза только то, что если - это событие, что в письме встретилось -е слово, то эти события не образуют полную группу, так как в полной группе события должны быть несовместны.

Я думаю этим можно пренебречь.

Добавлено спустя 6 минут 58 секунд:

Может что порекомендует почитать про Байесовские деревья(сети)?

[PAV]

Pavia в сообщении #156798 писал(а):

Я думаю этим можно пренебречь.

Я так не думаю. В любом случае, это надо серьезно обосновывать.

[xaxa3217]

2Dims нам задавали подобную задачу (конкретно байесовский классификатор текстовых документов), и я столкнулся с проблемой аналогичной вашей. можно рассмотреть задачу в общем случае с несколькими категориями (для спама их очевидно две), тогда если составить реальную таблицу типа "слово - вероятность/кол-во для каждой категории":

покупайте 900 100 (сначала спам, потом не спам)
...

то на самом деле в таблице окажется большое количество нулей, и прямое произведение вероятностей обнулит результат. я нашел решение в нахождении обратной вероятности принадлежности к категории. более подробно писал на своей страничке тут. одновременно с уходом от обнуления, при большом кол-ве нулей в таблице, происходит выход за пределы [0,1] которого в теории быть не должно, но тут практика - не для всех слов можно сказать точную вероятность принадлежности к категории, единственным выход - это нормировка всех вероятностей (по каждой категории) делением на общую сумму, чтобы сумма несовместимых событий была равна единице. по ссылке приведенной выше так же есть исходник программы, которая классифицирует документ-реферат поданный на вход. таблица составлялась по referats.yandex.ru

[Dims]

PAV писал(а):

Отсюда очевидно вытекает, что не менее половины писем должны обладать признаком B.

Компьютеру это не "очевидно".

Цитата:

Ошибку у себя поищите сами.

Я думаю, Вы смотрите на вопрос с математической точки зрения, а это Computer Science.

[PAV]

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