[Artificial Intelligence / Machine Learning] Naive Bayes Spam Filter Part 1.

Written by Geol Choi | Nov. 07, 2016

이번 글에서는 Naive Bayes 이론을 기반으로 한 Spam Filter 작성에 대해 알아보도록 하겠습니다.

Theoretical Background

서로 종속적인 사건 A, B가 있을 때 사건 B가 일어났다는 전제 하에 사건 A가 일어날 확률은 다음과 계산됩니다:

\(P(A\mid B) = \displaystyle{\frac{P(A \cap B)}{P(B)}}\) ...(1)

여기서 \(P(A \mid B)\)를 조건부 확률(Conditional Probability)이라고 하며, 이는 사건 A와 B가 동시에 일어날 확률, \(P(A \cap B)\)과 사건 B가 일어날 확률에 의해 결정됩니다. 즉, Bayes' Theorem이 의미하는 바는, 사건 B가 일어날 확률에 대하여 사건 A와 B가 동시에 일어날 확률의 비율이라고 할 수 있습니다.

풀어서 얘기하면, 우리가 사건 B를 알고 있을 때, 사건 B가 발견되는 경우에 있어 사건 A와 B가 동시에 일어나는 빈도가 클수록 사건 A의 확률이 커진다는 것입니다.

이는, 사건 B가 일어날 확률 \(P(B)\)는 사건 B가 일어났다는 전제 하에 사건 A가 일어날 확률, \(P(A \mid B)\)를 조절한다는 것입니다. 즉,

 (1) 사건 B가 일어날 확률이 지극히 낮으면 (\(P(B)\) 값이 매우 작으면), \(P(A \cap B)\)도 덩달아 작아진다.

 (2) 반대로 만약 사건 A와 B가 거의 항상 동시에 일어난다면 사건 B의 확률에 상관없이 \(P(A \mid B)\) 또한 크다.

식(1)에서 A와 B를 바꿔쓰면,

\( P(B \mid A) = \displaystyle{\frac{P(B \cap A)}{P(A)}} \) ...(2)

식(1)로부터

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

이며, 식(2)로부터

\( P(B \cap A) = P(B \mid A)P(A) \) ...(4)

이므로, (3) = (4)로부터,

\( P(A \mid B)P(B) = P(B \mid A)P(A) \)

이 성립합니다.

따라서,

\( P(A \mid B) = \displaystyle{\frac{P(A \cap B)}{P(B)}} = \displaystyle{\frac{P(B \mid A)P(A)}{P(B)}} \) ...(5)

이 성립하며, 이를 Bayes' Theorem이라고 합니다.

Terminologies

Bayes' Theorem을 이해하는데 있어 필요한 몇가지 용어에 대해 설명하고자 합니다. Bayes' Theorem을 Spam Filter에 응용할 것이므로, 이에 적절한 예로 설명하도록 합니다.

Prior Probability(사전확률)

이전의 메시지가 Spam인 확률, 즉 \(P(Spam)\).

Likelihood

"Viagra"라는 단어가 이전 Spam 메시지에 사용된 확률, 즉 \(P(Viagra \mid Spam)\).

Marginal Likelihood

"Viagra"라는 단어가 이전의 모든 메시지에 사용된 확률, 즉 \(P(Viagra)\).

Posterior Probability(사후확률)

새로 주어지는 메시지가 얼마나 Spam에 가까운지를 측정하는 확률, 즉 \(P(Spam | Viagra)\).

위의 주어진 용어들에 대한 관계식은 다음과 같습니다:

Posterior Probability = ( Likelihood × Prior Probability ) / Marginal Likelihood

이를 "Viagra" 단어를 포함한 메시지에 대하여 Spam에 적용하면,

\( P(Spam \mid Viagra) = \displaystyle{\frac{P(Viagra \mid Spam)P(Spam)}{P(Viagra)}} \)

입니다.

Frequency Table & Likelihood Table

Frequency Table은 "Viagra"가 Spam과 Ham(Spam이 아닌 메시지를 Ham으로 한다)에 등장하는 빈도수를 표로 정리한 것입니다. 가령, 다음 표와 같이 각 메시지에 "Viagra"가 등장하면 "Yes"를, 등장하지 않으면 "No"로 카운팅합니다.

	Viagra
Frequency	Yes	No	Total
Spam	4	16	20
Ham	1	79	80
Total	5	95	100

표의 내용을 몇가지 분석해 봅니다.

(1) Spam으로 분류된 메시지에 대하여 이 메시지가 "Viagra"를 포함하는 확률은,

\( P(Viagra = Yes \mid Spam) = 4 / 20 = 0.2 \) (20%)

입니다.

(2) 메시지가 Spam이면서 "Viagra"를 포함하는 확률은,

\( P(Viagra = Yes \cap Spam) = 4 / 100 = 0.04 \) (4%)

입니다. 이 확률은 다음과 같이 계산할 수도 있습니다:

\( P(Viagra = Yes \ cap Spam) = P(Spam \mid Viagra = Yes) \cdot P(Viagra = Yes) = (4/5) \cdot (5/100) = 0.04 \) (4%)

(3) 표로부터 Posterior Probability, \( P(Spam \mid Viagra = Yes) \)는 

\( P(Spam \mid Viagra = Yes) = 4/5 = 0.8 \) (80%)

입니다. 즉, 메시지가 "Viagra"를 포함한 경우, 이 메시지는 Spam일 확률이 80%라는 의미가 됩니다.

Naive Bayes 알고리즘

Naive Bayes 알고리즘은 텍스트 등을 분류하는데 있어 간단한 방법으로 Machine Learning 외에도 널리 쓰이는 방법입니다.

모든 특징(Features)들에 대하여 중요도를 동등하게 처리하거나 그 특징들이 서로 독립적이라고 가정하므로 "Naive"라는 이름이 붙었는데, 현실의 문제들은 그러한 특징들의 중요도가 동등하지도 않고 서로 독립적인 경우가 거의 없습니다.

가령, Spam을 분류하는데 특징들 중 메시지를 보낸 사람과 특정 단어가 있다면, 그 중요도가 동등하지 않습니다. 즉, 메시지 내용의 특정 단어보다 보낸 사람이 누구냐가 Spam 분류 기준의 더 중요한 단서가 될 것입니다. 마찬가지로 제목과 내용이 서로 독립적일 수도 없습니다. 왜냐하면 (너무도 당연히) 제목은 내용을 포괄적으로 표현한 것이기 때문입니다.

이러한 한계들이 있음에도 불구하고 Naive Bayes 분류 알고리즘은 상당히 쓸 만합니다. 특징들 간에 독립적인 것을 가정함에도 의존적인 경우에도 상당히 잘 맞습니다. 그 정확도 및 다양한 종류의 문제들에 대한 대처 범위가 넓기 때문에 이 알고리즘은 분류를 위한 기계학습에 있어 가장 첫번째로 추천이 되곤합니다.

그러면 Naive Bayes 알고리즘의 장점 및 단점을 살펴봅니다 :

[Naive Bayes 알고리즘의 장점]

• 간단하고 빠르면서도 효과가 좋음

• 노이즈가 많거나 유실 데이터가 많은 경우에도 잘 적용됨

• 훈련 데이터가 많이 필요하지 않으며 많은 경우에도 물론 잘 적용됨

• 예측을 위한 추정 확률을 얻기 쉬움

[Naive Bayes 알고리즘의 단점]

• 동등하게 중요하고 독립적인 특징의 빈번한 오류 가정에 대하여 의존성이 높음

• 수치 데이터 종류가 많은 것에는 적합하지 않음

• 예측한 분류보다 추정 확률의 신뢰성이 떨어짐

Naive Bayes 알고리즘을 이용한 분류

간단한 예제를 통해 Naive Bayes 알고리즘을 통해 어떻게 Spam/Ham이 분류되는지 살펴보도록 합니다.

Spam/Ham을 분류하기 위한 기준으로 네 가지 단어들(특징들, Features), "Viagra"(W₁), "Money"(W₂), "Groceries"(W₃), "Unscribe"(W₄)을 선정했다고 가정합니다.

훈련을 위한 100개의 데이터(메시지)가 다음과 같이 Frequency Table로 정리하였습니다 :

	Viagra(W1)		Money(W2)		Groceries(W3)		Unscribe(W4)
	Yes	No	Yes	No	Yes	No	Yes	No	Total
Spam	4	16	10	10	0	20	12	8	20
Ham	1	79	14	66	8	71	23	57	80
Total	5	95	24	76	8	91	35	65	100

새로운 메시지가 도착했는데 조사해보니 "Viagra"(W₁)와 "Unscribe"(W₄)의 두 단어가 포함되었으며, "Money"(!W₃)와 "Groceries"(!W₄)는 포함되어 있지 않다고 하면, Posterior Probability(사후확률), 즉, (\( W_1 \cap !W_1 \cap !W_3 \cap W_4 \))이 동시에 일어난 것에 대해 Spam일 확률은 다음과 같이 계산됩니다 :

\( P(Spam \mid W_1 \cap \ !W_2 \cap \ !W_3 \cap W_4) = \displaystyle{\frac{P(W_1 \cap !W_2 \cap !W_3 \cap W_4)P(Spam)}{P(W_1 \cap !W_2 \cap !W_3 \cap W4)}} \) ...(6)

그러나 이것을 계산하기는 매우 어렵습니다. 확률은 집합과 비슷한 성질이 있으므로 벤 다이어그램으로 표현하는데 4개의 특징들 간에 벤 다이어그램을 표기한다고 상상해 보면 알 수 있습니다.

게다가 특징이 한 개씩 늘어날 때마다 계산 복잡도는 어마어마하게 늘어갈 것입니다. 계산을 보다 간단하게 하기 위해 사건 간에 독립성을 가정하며 이 가정을 분류 조건부 독립(Class Conditional Independence)이라고 합니다.

분류 조건부 독립은 사건들이 동등한 분류 값을 갖는 한 서로 독립임을 의미합니다. 이 가정을 하면 A 사건과 B 사건이 동시에 일어날 확률은

\( P(A \cap B) = P(A)P(B) \)

와 같이 계산됩니다. 식(6)에서 우항의 분모는 분류(Ham 또는 Spam)와는 무관하기 때문에 일종의 상수로 취급할 수 있으므로 분류를 위한 계산에는 포함하지 않을 수 있습니다. 따라서, Spam에 대한 조건부 확률은 다음과 같이 표현이 가능합니다:

\( P(Spam \mid W_1 \cap \ !W_1 \cap \ !W_3 \cap W_4) \propto P(W_1 \mid Spam)P(!W_2 \mid Spam)P(!W_3 \mid Spam)P(W_4 \mid Spam)P(Spam)\) ...(7)

여기서 기호 "\(\propto\)"는 비례함을 의미합니다. 마찬가지로 Ham에 대한 조건부 확률은,

\( P(Ham \mid W_1 \cap \ !W_1 \cap \ !W_3 \cap W_4) \propto P(W_1 \mid Ham)P(!W_2 \mid Ham)P(!W_3 \mid Ham)P(W_4 \mid Ham)P(Ham) \) ...(8)

로 표현됩니다. Frequency Table과 식(7)에 근거하여 Spam의 Likelihood를 계산하면,

(4/20) * (10/20) *(20/20) * (12/20) * (20/100) = 0.012

이며, Frequency Table과 식(8)에 근거하여 Ham의 Likelihood를 계산하면,

(1/80) * (66/80) * (71/80) * (23/80) * (80/100) = 0.002

이므로, Ham 보다는 Spam일 가능성이 높습니다. 이를 확률로 변환하면 Ham일 확률은

0.012 / (0.012 + 0.002) = 0.857 (85.7%)

이며, Spam일 확률은

0.002 / (0.012 + 0.002) = 0.143 (14.3%)

이므로, Ham일 확률이 훨씬 높음을 알 수 있습니다. 앞의 과정에 근거하여 Naive Bayes 분류 알고리즘을 하나의 식으로 표현하면,

\( P(C_L \mid F_1, ... , F_n) = \displaystyle{\frac{1}{Z}P(C_L) \prod_{i=1}^{n}{P(F_i \mid C_L)}} \)

입니다. 여기서,

\(C_L\) : 레벨 L에 대한 Class C를,

\(F_i\) : i-번째 특징(Feature),

\(\frac{1}{Z}\) : 환산 계수(Scaling Factor)

입니다. 가령, 이를 앞의 문제에 대입하면,

n = 4, C_L = Spam, F₁ = W₁ , F₂ = !W₂, F₃ = !W₃, F₄ = W₄

이므로,

\( P(C_L \mid F_1,F_2,F_3,F_4) = P(Spam \mid W_1 \cap \ !W_2 \cap \ !W_3 \cap W_4) \)

이며,

\( \displaystyle{\frac{1}{Z}}P(C_L) \prod_{i=1}^{n}{P(F_i \mid C_L)} = \displaystyle{\frac{1}{Z}}P(Spam)P(W_1 \mid Spam)P(!W_2 \mid Spam)P(!W_3 \mid Spam)P(W_4 \mid Spam) \)

입니다. 환산 계수, Z는 다음과 같이 계산됩니다:

\( Z = P(Spam)P(W_1 \mid Spam)P(!W_2 \mid Spam)P(!W_3 \mid Spam)P(W_4 \mid Spam) + P(Ham)P(W_1 \mid Ham)P(!W_2 \mid Ham)P(!W_3 \mid Ham)P(W_4 \mid Ham)  \)

라플라스 추정(Laplace Estimator)

Naive Bayes 필터를 실제 문제에 적용하기에 앞서 한 가지 짚고 넘어가야 할 것이 있습니다. 예를 들어, 다음 상황을 살펴보도록 합니다.

새로운 메시지를 받았는데 다음 네 가지(Viagra, Groceries, Money, Unsubscribe)가 모두 해당된다고 하면 Spam에 대한 Likelihood는,

\( P(W_1 \mid Spam)P(W_2 \mid Spam)P(W_3 \mid Spam)P(W_4 \mid Spam)P(Spam) = (4/20)(10/20)(0/20)(12/20)(20/100) = 0.0 \)

이며, Ham의 Likelihood는,

\( P(W_1 \mid Ham)P(W_2 \mid Ham)P(W_3 \mid Ham)P(W_4 \mid Ham)P(Ham) = (1/80)(14/80)(8/80)(23/80)(80/100) = 0.00005 \)

이므로, Spam과 Ham의 확률은 각각

0.0 / (0.0 + 0.00005) = 0.0

0.00005 / (0.0 + 0.00005) = 1.0

입니다. 이것의 의미는, 새 메시지에 네 가지가 모두 해당될 경우 Spam이 확률이 0%이며, Ham일 확률이 100%라고 단정짓는 결과를 가져옵니다. (사실, 이것은 말도 안 되는 결과입니다!)

이 결과는 당연히 \(P(W_3 \mid Spam) = 0\)이기 때문에 생긴 것입니다. 즉, 아무리 다른 조건부 확률값이 크더라도 단 하나의 조건부 확률이 0이라면 결과는 그냥 0인 것입니다.

Naive Bayes는 사건 간에 서로 독립임을 가정하여 조건부 확률들을 곱셈하는 형식이므로 단 하나의 조건부 확률이 0이 되면 곱셈의 결과는 어쩔 수 없이 0이 됩니다. 새로운 메시지에 Spam임을 의심케하는 다른 조건부 확률들이 높더라도 Groceries가 없다는 이유로 Spam일 확률이 0이라고 결론 짓는 것은 어리석은 일입니다.

이를 회피하기 위한 방안이 바로 Laplace Estimator 입니다. Laplace Estimator는 각 특징에 작은 수의 Count(이를 종종 Small Perturbation이라고 불러왔다)를 추가하는 것입니다.

이 작은 수의 Count는 보통 1개입니다 (1개를 추가하더라도 Sample 수 자체가 적은 경우에는 이 값도 얼마든지 큰 수가 될 수 있음을 유념하자. 그래서 Sample 수가 많을수록 정확한 예측을 하는데 유리한 것이기도 합니다.)

그리하여 각 특징에 Count를 1개씩 추가하여(총 4개가 추가됨) 얻은 Spam과 Ham의 Likelihood는,

\( P(W_1 \mid Spam)P(W_2 \mid Spam)P(W_3 \mid Spam)P(W_4 \mid Spam)P(Spam) = (5/24)(11/24)(1/24)(13/24)(20/100) = 0.0004 \)

\( P(W_1 \mid Ham)P(W_2 \mid Ham)P(W_3 \mid Ham)P(W_4 \mid Ham)P(Ham) = (2/84)(15/84)(9/84)(24/84)(80/100) = 0.0001 \)

이므로, Spam과 Ham의 확률은 각각,

0.0004 / (0.0004 + 0.0001) = 0.8 (80%)

0.0001 / (0.0004 + 0.0001) = 0.2 (20%)

로 Spam의 확률이 훨씬 높음을 알 수 있습니다.

다음 글(Naive Bayes Spam Filter Part 2.)에서는 R을 이용하여 Naive Bayes Spam Filter 코드를 작성해 보도록 합니다.