스팸 필터링의 기본 알고리즘은 베이즈 정리(Bayes' Theorem)에 기초하고 있다. 베이즈 정리는 조건부 확률을 이용해 사전 확률과 사후 확률의 관계를 추정하는 정리이다. 새로운 정보가 추가될 때 사후 확률의 변동을 예측하는 방법으로 사용될 수 있다.
다음의 내용은 Wikipedia를 참고하여 정리한 것이다.
http://en.wikipedia.org/wiki/Conditional_probability
http://en.wikipedia.org/wiki/Bayes'_theorem
http://en.wikipedia.org/wiki/Bayesian_spam_filtering
사건 B가 발생한 상황에서 사건 A가 발생할 조건부 확률 P(A|B)는 다음과 같은 식으로 표현할 수 있다.
P(A∣B)=P(B)P(A∩B)
이것은 다음과 같이 이해할 수 있다. (A,B), (A,¬B), (¬A,B), (¬A,¬B)와 같이 사건 A와 B가 각각 발생할 수도 있고 발생하지 않을 수도 있는 4가지 상황을 가정해보자.
이 중에서 B가 발생한 것은 (A,B)와 (¬A,B)에 해당한다.
이 상황에서 (A,B)의 경우가 앞서 말한 “사건 B가 발생한 상황에서 사건 A가 발생”한 경우에 해당된다.
(A,B) 또는 (¬A,B)가 발생할 확률 P(B)를 분모로 하고 (A,B)의 경우에 해당하는 P(A∩B)를 분자로 하는 비율이 P(A∣B)의 값이 되는 것이다.
위의 조건부 확률 식에 따라 다음의 식을 유도할 수 있다.
P(A∣B)∗P(B)=P(A∩B)
A와 B를 바꿔 조건부 확률을 생각해본다면 다음의 식도 성립한다.
P(B∣A)∗P(A)=P(B∩A)
그런데, P(B∩A)=P(A∩B)이므로
P(A∩B)=P(A∣B)∗P(B)=P(B∣A)∗P(A)도 성립한다.
여기서 P(A∣B)=P(B)P(B∣A)∗P(A)......(1)의 식을 얻을 수 있는데, 이것이 바로 Bayes' theorem이다.
사건 B를 A의 발생 여부를 이용해서 분할해나간다. A인 경우와 A가 아닌 경우로 분할하면 다음과 같은 식을 얻을 수 있다.
P(B)=P(A∩B)+P(¬A∩B)=P(B∣A)∗P(A)+P(B∣¬A)∗P(¬A)......(2)
A의 발생 여부를 A인 경우와 A가 아닌 경우로 분할하는 방법 대신에 A를 좀 더 작은 단위로 분할하면 다음과 같은 식을 얻을 수 있다.
P(B)=sumP(B∣Ai)∗P(Ai)......(3)
스팸 판매업자가 대량의 광고 우편물을 보낸 것에서 연유하여 광고성 메일을 스팸이라고 부른다. 햄은 스팸의 반대말로 여기서는 광고성 메일이 아닌 일반 메일을 의미한다.
P(S): 어떤 주어진 메시지가 스팸일 일반적인 확률
P(H): 어떤 주어진 메시지가 햄일 일반적인 확률
스팸(S)와 햄(H)는 서로 소이므로, P(W)=P(W∩S)+P(W∩H)라고 할 수 있다. 그러므로
P(W)=P(W∣S)∗P(S)+P(W∣H)∗P(H)
메시지에 특정 단어 W가 나타났을 때, 이 메시지가 스팸일 확률은 조건부 확률 P(S|W)라고 할 수 있다.
베이즈 정리(1 또는 2)에 따라 다음과 같은 식을 얻을 수 있다.
(S∣W)=P(W)P(W∣S)∗P(S)=P(W∣S)∗P(S)+P(W∣H)∗P(H)P(W∣S)∗P(S)
P(W∣S): 어떤 특정 단어 W가 스팸에 나타날 확률
P(W∣H): 어떤 특정 단어 W가 햄에 나타날 확률
P(S∣W)는 특정 단어 W가 어떤 메시지에 나타났고 그 메시지가 스팸일 확률이지만 그 값을 바로 구하기가 어렵다. 그러나 P(W∣S)는 스팸인 메시지가 있고 특정 단어 W가 그 메시지에 나타날 확률은 대량의 데이터에 대한 통계 처리를 통해 그 값을 미리 구해놓을 수 있다. 그러므로 P(W∣S)를 이용하여 P(S∣W)를 구할 수 있다.
Bayesian spam filter는 스팸과 햄의 비율이 실제 80:20 정도가 아니라 50:50 정도라고 가정하는 것에서 시작한다.(“not biased” 가정을 통해 선입견 없이 공평하게 상황을 보겠다는 의미이다.)
P(S)=P(H)=0.5
이 값을 대입하면 다음의 식을 얻을 수 있다.
P(S∣W)=P(W∣S)/(P(W∣S)+P(W∣H))......(4)
그러나 하나의 단어를 가지고 스팸이냐 햄이냐를 판단하는 것을 오류가 발생하기 쉬운 판단이므로 여러 단어를 동원할 필요성이 발생한다.
이상의 bayesian theorem을 이용하여 스팸 필터링하는 기능을 구현하게 되면 순진한(naive) 가정을 하게 되는데, 어떤 문서 내의 단어들의 출현이 서로 독립적이라는 가정이 바로 그것이다. n개 단어로 구성된 메시지에서 n개 단어가 출현한 상태에서 그 메시지가 스팸일 확률은 4번 식으로부터 다음과 같이 구할 수 있다.
- Wi는 각각 독립적이다.
- 특정 단어 Wi가 스팸에 나타날 확률과 햄에 나타날 확률의 합은 1이다.
이 가정을 식으로 써보면 다음과 같다.
P(W1,...,Wn)=P(W1)∗...∗P(Wn)P(Wi∣S)+P(Wi∣H)=1P(S∣W1,...,Wn)=P(W1,...,Wn∣S)/(P(W1,...,Wn∣S)+P(W1,...,Wn∣H))=P(W1∣S)∗...∗P(Wn∣S)/(P(W1∣S)∗...∗P(Wn∣S)+P(W1∣H)∗...∗P(Wn∣H))=P(W1∣S)∗...∗P(Wn∣S)/(P(W1∣S)∗...∗P(Wn∣S)+(1−P(W1∣S)∗...∗(1−P(Wn∣S))
이 값을 계산하여 정해진 threshold보다 작으면 햄이고, 크면 스팸이라고 판단한다.
그런데 이런 순진한 가정을 그대로 써도 될까? 현실에서의 메시지는 단어끼리 상관관계가 상당히 크기 때문에 독립이라는 가정은 사실 틀렸다고 할 수 있다. 그러나 실제로 대량의 메일 메시지에 대해서 이 가정을 가지고 테스트해보면 상당히 높은 품질을 가지고 스팸과 햄을 잘 구분해내는 것을 알 수 있다. 그래서 이런 방식의 판단 알고리즘을 Naive Bayesian Classifier라고 부른다. 가정이 단순하기 때문에 현실적인 성능을 가지는 스팸 필터를 구현할 수 있는 것이다.