이 글에서는 나이브 베이즈 분류기 (Naive Bayes Classifier) 에 대해서 다루고자 한다.
크게 2가지 영역으로 나누어서 얘기해 볼 수 있겠다. 이 포스트에서는 알고리즘을 다루고, 다음번 포스트에서 Spam Mail 및 NewsGroup 을 활용한 응용 부분을 확인해 보자.
- Naive Bayes Classifier Algorithm
- Naive Bayes Classifier Applications
1. Naive Bayes Classifier Algorithm
나이브 베이즈 분류기는 머신러닝(Machine Learning) 알고리즘 중에서 가장 단순하며 적은 연산으로도 훌륭한 성능을 보여주는 분류기라고 할 수 있겠다. 서포트 벡터나 랜던 포레스트 처럼 복잡한 연산을 수행하지 않아도 되며 알고리즘 자체도 조건부 독립에 대한 통계적인 지식이 있다면 비교적 쉽게 이해할 수 있다는 장점이 있다.
Naive Bayes Classifier 자체의 정의를 확인하기 전에 먼저 짚고 넘어가야 할 기본적인 통계적인 지식들을 살펴보도록 하자.
1) 조건부 확률과 독립시행
이전 포스트 에서 언급하였지만, 확률 공간을 전확률 공간이 아닌 A 로 한정지은 상태에서 B와 만나는 영역을
구하면, P(B|A) = \dfrac{P( A \cap B)}{P(A)} 이 된다.
또 시행을 반복할 때 사전 시행의 결과가 이후 시행에 영향을 미치지 않는 다면,
P(A) \times P(B|A)= P(A) \times P(B) 와 같이 기술할 수 있고, P(A \cap B) = P(A) \times P(B) 됨을 확인 할 수 있었다.
흔히 확률적으로 독립이라고 하면 위 조건을 만족하는 경우를 말한다. 이는 marginal independence 라고 부른다.
2) 베이즈 정리 (Bayes Theorem)
베이즈 정리가 고등학교 수학의 정석에 나왔던 내용이었다는 사실을 기억하지 못할 정도로 대충 배우고 넘어간 부분이다. 지금에 와서야 베이즈 정리가 머신 러닝을 지탱하는 핵심 개념이라는 점을 알게 되었다.
P(H|E) = \dfrac {P(E|H) \cdot P(H)}{P(E)} 로 표현되며, 바꿔 말하면 다음과 같다.
사후확률(posterior) = {가능도(likelihood) × 사전확률(prior)} / {모델에 대한 증거(model evidence)}
머신러닝에서 P(H|E) . 즉, 새로운 증거 E 가 나타났을 때,
특정 가설 H 를 만족하는 확률을 구하려면,
가능도(likelihood) P(E|H) 와 사전확률 P(H) 을 알아야 하는데,
가능도는 미리 학습할 데이터 셋을 통해서 가설 H 마다의 증거 E 가 발생한 확률을 계산해서 보유할 수 있게 된다. 일반적으로 가설 H 는 Class 로 표현하고 해당 Class 가 2개인 경우는 Spam Filter 와 같은 TRUE /FALSE 구분 문제로 Class 가 복수개인 경우는 NewsGroup 분류와 같은 복수개 Class 중 하나로 분류하는 문제가 된다.
여기서 사전확률 P(H) 는 경험적으로 얻어지거나 (Class 별로 균일하게) 혹은 데이터 셋으로부터 얻어진 Label 을 Counting 하여 구할 수 있다. 분모에 위치한 모델에 대한 증거(model evidence) 는 흔히 marginal likelihood 로 불려지는데 대립가설들 별로 증거 E에 대한 likelihood 를 모두 더하면(적분하면) 얻을 수 있다. 대립가설들의 likelihood 를 모두 알 경우나눠버리면 사라지는데 그 비율로 사후 확률을 쉽게 유추할 수 있기 때문에 상수(Constant) 항으로 취급된다.
3) 결합확률 (Joint Probability) 과 Chain Rule
p(y_1, y_2) 가 이산 랜덤 변수(Discrete Random Variables) 이면, Y_1, Y_2의 결합확률 분포는 다음과 같다.
p(y_1, y_2)=P(Y_1=y_1, Y_2=y_2), \,\,\, -\infty< y_1 < \infty, -\infty< y_2 < \infty
함수 p(y_1, y_2) 를 결합 확률 함수 (joint probability function) 이라고 칭한다.
p(y_1, y_2) 는 P(Y_1 = y_1, Y_2 = y_2) 로 기술되는데,
간편하게 p(y_1, y_2) 로 표현한다.
Naive Bayes Classifier 를 정의하기 위해 n개 x에 대한 결합확률을 조건부 독립개념을 사용하여 n개의 확률의 곱으로 p(x_i|y) 로 표현하게 되는데 이때 P(X_i = x_i| Y=y_k) 로 이해하면 되겠다.
n개 변수들의 결합확률로에서부터 Chain Rule 을 적용시키면 개별 확률의 곱으로 표현할 수 있게 되는데, 나이브 베이즈 분류기 정의를 이해하기 위해서는 짚고 넘어가야 할 부분이다. 자세한 내용은 여기 를 참조하자.
P(x_1, x_2, \cdots, x_n) = P(x_n|x_{n-1}, \cdots, x_1) P(x_{n-1} | x_{n-2}, \cdots, x_1) \times P(x_{n-2}|x_{n-3}, \cdots,x_1) \cdots P(x_2|x_1) P(x_1)
4) 조건부 독립 (Conditional Independence)
이전 포스트 의 Officer 와 Commander 예제를 확인해 보자. 조건부 독립에 대해 확실히 감이 올 것이다.
Naive Bayes Classifier 의 ‘Naive’ 란 단어 그대로 단순한, 순진한 이라는 의미를 가진다. 여기서 뭐가 순진하다는거지? 라고 반문할 수 있는데 바로, 가설이 정해졌을 때(주어졌을 때) 개별 x_i 들끼리는 서로 조건부 독립이 성립할 거라는 순진한 믿음을 의미한다.
즉, P(x_1 | x_2, y) = P(x_1 | y) 가 성립한다는 것이다. 결합확률 분포로 부터 체인룰을 사용하여 풀어낸 식에서 조건(given) 에 해당하는 부분이 y에 의해서만 결정된다고 보는 것이다. 그러면 위의 식에 y 를 하나 더 추가하고 정리하면 다음과 같이 결합확률 분포에서 출발하여 y 와 x_i 만 관여하는 개별적인 확률의 곱을 얻는다.
P(x_1, x_2, \cdots, x_n, y) = P(x_n|x_{n-1}, \cdots, x_1,y) P(x_{n-1} | x_{n-2}, \cdots, x_1,y) \times P(x_{n-2}|x_{n-3}, \cdots,x_1,y) \cdots P(x_2|x_1,y) P(x_1|y)P(y)\Longrightarrow P(x_1, x_2, \cdots,x_n, y) = P(x_n|y) P(x_{n-1}| y) \cdots P(x_2|y)P(x_1|y)P(y)
자, 이제 Naive Bayes Classifier 를 정의할 차례가 되었다.
5) Naive Bayes Classifier Algorithm
주어진 것.
- Class 별 사전확률 (Y)
- Class 값이 주어졌을 때( Y=y), d개의 조건부 독립인 X의 features X_i 에 대해서, likelihood 를 안다. P(X_i=x|Y=y)
정의.
f_{NB} = argmax_{Y=y}P(Y=y)\prod_{1 \leq i \leq d} P(X_i=x|Y=y)
결합확률함수로 표현되는 다음 식은 (2^d-1)k 개의 파라미터 조합을 필요로 한다.
P(Y=y,X_1=x_1,X_2=x_2, \cdots, X_d=x_d)
현실 세계에서 이 조합을 구하기란 매우 어려운 일이다. 따라서 우리는 순진하게 Y=y 가 주어진다면, 나머지 X_i 들에 상관없이 결합확률함수를 단순화 시킬 수 있다고 믿는 것이다. 지극히 순진한 가정이 아니냐고 할 수 있겠지만, 나이브 베이즈 분류기는 현실 세계에서도 잘 작동한다.
위의 정의에 따르면 P(Y=y)\prod_{1 \leq i \leq d} P(X_i=x|Y=y) 이 확률을 최대화 (argmax) 하는 y(class 중 하나) 를 찾기 위해
P(X_i=x|Y=y) 와 P(Y=y) 각각을 찾아야 한다. 이건 어떻게 정의 내릴 수 있을까?
최대우도추정법 (Maximum Likelihood Estimation) 에서 우리는 모 파라미터(population’s parameter) 를 추정하는 방법을 확인했다. 즉, 하나의 파라미터를 고정하고 우도함수(likelihood function) 을 미분하여 0으로 만드는 파라미터 값을 구하는 방식이다. 이 우도함수는 아래 2가지 파라미터로 구성되었다고 생각할 수 있다.
- q(y), where y \in \{1,\cdots,k\}
- q_j(x|y), where j \in \{1, \cdots, d\}, x \in \{-1,+1\}, y \in \{1, \cdots, k\}
최대우도추정법을 통해서 얻어진 모 파라미터는 다음과 같다. (최대우도추정법으로 유도하는 과정은 여기 를 참고하길 바란다.)
- q(y) = \dfrac {count(y)}{n}
- q_j(x|y)= \dfrac {count_j(x|y)}{count(y)}, where\, {count}_j(x|y)= \displaystyle\sum_{i=1}^{n} {[[y^{(i)}=y\, and\, x_j^{(i)}=x]]}