Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

Category:

фильтр имени Байеса

Используется для классификации (в частности, для фильтрации SPAM) и основан на формуле (теореме Байеса). Формула Байеса выводится следующим образом:

Во-первых, имеем непосредственно из определения условной вероятности P(A|B) (вероятности события A, при условии, что событие B уже произошло):

P(A∩B) = P(A|B) P(B)

Словами: A и B происходят одновременно, если происходит А, при условии уже происшедшего B, и происходит B.

Совершенно аналогично

P(A∩B) = P(B|A) P(A)

Словами: A и B происходят одновременно, если происходит B, при условии уже происшедшего A, и происходит A.

Приравниваем, и получаем теорему Байеса
         P(B|A) P(A)
P(A|B) = -----------
            P(B)
Пример: Пусть известно, что Вася умеет хорошо решать задачи (скажем, решает типичную задачу с вероятностью 4/5), а Петя -- плохо (решает с вероятностью 1/4). Домашние задания они делают вместе. Когда приходит время, они тянут спички. Кому достается длинная -- решает заданную на дом задачу (другой ее копирует). Вы учитель, если задача решена правильно -- какова вероятность, что ее решал Петя ?

На такой вопрос и дает ответ формула Байеса. Вероятности гипотез, что задачу решал Петя P(Петя) и задачу решал Вася P(Вася) равны P(Петя)=P(Вася)=1/2 (предполагается, что жребий они тянут честно). Если задачу досталось решать Васе (ну, или папе его, который силен в математике ;-), то вероятность того, что она решена правильно P(правильно|Вася)=4/5, а если досталось Пете, то P(правильно|Петя)=1/4. Вероятность того, что задача эта вообще будет решена их коллективным методом равна P(правильно)=P(правильно|Петя)P(Петя) + P(правильно|Вася)P(Вася) = 1/4*1/2 + 4/5*1/2=42/80 (больше 1/2, тоесть Пете выгодно ;-).

Соответственно, по формуле Байеса вероятность того, что при правильном решении задачи ее решил Вася равна
                    P(правильно|Вася) P(Вася)   4/5 * 1/2   16
P(Вася|правильно) = ------------------------- = --------- = -- ≈ 0.76 ,
                           P(правильно)            42/80    21
а то, что ее решил Петя равна
                    P(правильно|Петя) P(Петя)   1/4 * 1/2   5
P(Петя|правильно) = ------------------------- = --------- = -- ≈ 0.24  .
                           P(правильно)            42/80    21
SPAM фильтруют аналогично, только Петя и Вася не решают задачи, а пишут письма. Петя -- Ваш друг и пишет письма о пьянках, вечеринках, женщинах, компьютерах. Вася -- коммерсант, и, сидя в темном сыром подвале, движимый идеей быстрого обогащения, он строчит и рассылает всем подряд письма о курсах украинского русского, наркоте и Виагре. У каждого из них свой характерный лексикон (набор слов). Точнее, каждому слову можно приписать вероятность : кому оно более характерно -- Пете или Васе. Исходя из набора слов в рассматриваемом письме по приведенным Выше формулам рассчитывается -- кто его с какой вероятностью писал.

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

update (9.8.2006): спаммеры наносят ответный удар путем рассылки фрагментов из архивов проэкта Гутенберг. ;-)
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments