오래전부터 한번정도 해보자고 했던 포스팅을 해보고자 한다.

Spam Filter 알고리즘 인데, 수많은 필터링 알고리즘중에서 가장 오래되었고, 구현하기 쉬운 Paul Graham의 Baysian Filtering 알고리즘을 이야기 해보겠다.
베이지언 알고리즘은 수많은 확률적인 분류에서 약방의 감초처럼 나오는 놈이라서 좀 더 살펴볼 필요가 있지만 일단 생략한다. (자세한 부분은 관련 도서를 참고하기를…아니면 요놈의 포스트를 보면 조금 알 수 있다. )

이 알고리즘은 그레이엄의 “A Plan for Spam“이라는 글에서 처음 소개가 된 필터링 알고리즘으로서 복잡하지 않아서 퍼포먼스도 좋고 구현하기 쉬운 장점이 있다.  (기억으로는 이 글이 해커와 화가라는 책에 소개가 되었던거 같다. 책을 도서관에서 빌려 읽는 바람에 확인하기 힘들다. 아시는분 덧글이라두… ^^; )

이 알고리즘은 3가지 식으로 요약할 수 있다.

b(w) = (the number of spam e-mails containing the word w) / (the total number of spam e-mails)

g(w) = (the number of ham e-mails containing the word w) / (the total number of ham e-mails)

p(w) = b(w) / (b(w) + g(w))

3번째 식 P(w)는 실제 w의 스팸일 확률을 나타낸다. 조건부 확률로 나타내자면 P(Spam|w)로 나타낼 수 있다.

그럼 왜 저런 식이 나왔을까 고민하지 않을 수 없는데… (결국을 설명을 하게 되는군… 쩝)

베이지언 룰을 사용해서 P(Spam|w)를 구해보자!

                     P(w|Spam) P(Spam)
P(Spam|w) = —————————–
                     P(w)

위와 같은 식이 나올 수 있겠다.

P(w|Spam)은 스팸인 모든 메일에서 w가 나온 횟수를 계산하면 가져올 수 있는 결과이고, P(Spam)은 전체 메일에서 Spam 메일의 갯수를 알아보면 나오는 확률이다. 또한 여기서 분모 P(w)는 전체 확률(?)을 이용해 “P(Spam) P(w|Spam) + P(Ham)P(w|Ham)”으로 치환할 수 있고 따라서 아래와 같은 식이 완성된다.

                                  P(w|Spam) P(Spam)
P(Spam|w) = ————————————————
                     P(Spam)P(w|Spam) + P(Ham)P(w|Ham)

여기서 P(Spam)과 P(Ham)의 관계가 P(Spam) ~= P(Ham)라고 가정하면 아래와 같은 식이 나온다. 물론 폴 그래이엄이 이런 가정을 했기 때문에 나중에 P(w|Ham)에 2를 곱해주면서 정확도가 더 나아졌다는 말이 나왔으니, 그래이엄의 현실 세계(메일박스)에서는 스팸에 비해 약 2배의 non-spam 메일이 있는것이 아닐까 생각해본다. 정리해보면 아래와 같은 식이 나온다.(개인적인 생각으로는 아래의 식을 쓰는게 아니라 위의 식을 쓰는게 더 맞는 이야기가 아닐까 한다. )
실제로 그레이엄은 1개의 ham 메일과 1개의 스팸메일을 가지고 실험을 시작했다고 하니 당시에는 틀린식이 아니였을 것이다.

                       P(w|Spam)
P(Spam|w) = —————————————–
                     P(w|Spam)    +    P(w|Ham)

여기서 P(w|Ham) 은 위에서 소개한 g(w)가 되겠고, b(w)는 P(w|Spam)이 되겠다.

그런데 여기서 중요한 하나의 식이 새로 나오는데 이것은 바로 이런 word의 컴비네이션인 문서에 대해서 어떤 식을 도출하느냐이다.

Ending Spam이라는 책을 보면 아래의 식이 나온다.

여기서 A,B,C 각각은 문서에 포함된 word가 스팸일 확률을 의미한다.
물론 이걸 바로 쓰면 괜찮은 결과가 나오나.. 일단 이 식이 어떻게 도출되는지 알아보는 의미는 있는거 같다.

예를 들어 우리가 구하고자 하는  문서가 딱 두개의 term만 보유한다고 치자. 그러면 P(Spam| X and Y)를 구하는게 목적인데 이것을 Bayes룰로 풀어쓰면 아래와 같다.

여기서 X, Y의 독립가정 즉, naive Bayes룰을 사용하고 위에서 설명한 전체 확률 개념을 적용한다면 아래의 식이 완성된다. (독립가정은 X, Y의 텀들이 문서안에 서로의 존재에 대해서 영향을 끼치지않는다는것이다. )

여기서 바로 식을 사용하는게 가능하지만 그레이험의 식을 유도하기 위해서 다시한번 베이지언 룰을 사용해 P(X|Spam)을 P(Spam|X) …. 등의 식으로 변환한다.

위 식을 정리하면 아래의 식이 도출된다.

    P(Spam|X)*P(Spam|Y)/P(Spam)
——————————————————————
P(Spam|X)*P(Spam|Y)/P(Spam) + P(Ham|X)*P(Ham|Y)/P(Ham)

이 식을 위의 가정처럼 P(Spam) ~= P(Ham) 이라고 하고 P(Spam|X)와 P(Ham|X)는 배반사건이므로 드디어 그래이엄의 식이 도출이 된다.

      P(Spam|X) * P(Spam|Y)
——————————————————
P(Spam|X)*P(Spam|Y) + (1-P(Spam|X)) *(1-P(Spam|Y))

이렇게 해서 폴 그레이엄의 스팸 필터 알고리즘에 대해서 유도 작업을 해봤다. 이 유도하는 과정을 어디서도 쉽게 볼 수 없어서 나름대로 생각하고 고민해서 식을 구해봤다. 이렇게 하면서 얻은 가장 큰 수확은 무엇보다도 왜 P(X|Ham) 인 확률에 2를 곱해줘서 성능이 좋아 졌는지 이유를 알수 있었다는 것이다.
그저 식에 대한 이해없이 알고리즘만 가지고 필터를 사용해서는 커스터마이징이 힘들다는것을 증명하는게 아닐까 한다. 위에서 소개한 Ending Spam이라는 책은 이런 설명이 전혀 없어서 베이지언 룰에서 어떻게 저런 간단한 식이 나왔는지 알수가 없었다. (이 책의 큰 장점이자 단점중에 하나다.)

뭐 이런 기반위에 Term의 전체 빈도수를 가지고 신뢰도를 기반으로 하는 Term 확률 재산정하는 과정이 있는데 이 부분에 대해서는 다음에 설명하도록 하겠다.

ps. 참고한 문서는 Ending Spam과 A Statistical Approach to the Spam Problem이라는 문서다.

ps. 필터링 알고리즘이 최근에는 Support Vector Machine이 성능이 좋다고 한다. gray area를 표현하기 좋아서 false positive를 방지하는데 좋다고 하는데 정확하게 어떻게 구현했는지 서베이는 해봐야 할거 같다. (서포트 벡터 사이의 공간을 gray area라고 칭하는 건지?? 잘 모르겠다. ㅎㅎ )

폴 그레이엄의 Bayesian Spam Filter 알고리즘 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.