[머신러닝] 나이브 베이즈 분류 Naive Bayes Classification에 대하여

1. 개요

    나이브 베이즈는 베이즈 정리를 사용하는 확률 분류기의 일종으로 특성들 사이에 독립을 가정한다.^[각주:1] 이론이 어렵지 않고 구현이 간단하며 "나이브"한 가정에도 불구하고 여러 복잡한 상황에서 잘 작동하기 때문에 다양한 분야에서 사용되고 있다. 

    독립변수에 따라 여러가지 모습을 가지지만 이번 포스팅에서는 어떤 메시지가 스팸(spam)인지 또는 정상(ham)인지 분류하는 문제만 고려한다. 2장에서는 나이브 베이즈 분류를 이해하기 위한 배경 지식을 간단하게 훑어보고 3장에서 나이브 베이즈가 어떤 식으로 작동하는지 살펴본다. 4장에서는 나이브 베이즈를 실제 데이터에 적용하여 텍스트 메시지를 분류해본다.

2. 배경 지식

2.1. 베이지안 통계

    베이지안 통계에서는 모수 $\theta$가 고정된 값을 가지지 않고 관측된 데이터 $\mathcal{D}$가 고정되어 있다고 생각한다. $\mathcal{D}$가 주어졌을 때 $\theta$의 불확실성을 $p(\theta |\mathcal{D})$로 표현하며 이것을 사후 분포 posterior distribution라고 한다. 사후 분포는 다음과 같이 분해된다.

$$\begin{array}{}\text{(1)}& p(\theta |\mathcal{D})=\frac{p(\mathcal{D}|\theta )p(\theta )}{p(\mathcal{D})}\propto p(\mathcal{D}|\theta )p(\theta )\end{array}$$

    $p(\mathcal{D}|\theta )$는 우도 함수 likelihood function이며 $p(\theta )$는 데이터를 관측하기 전 $\theta$에 대한 불확실성을 나타낸 것으로 사전 분포 prior distribution라고 한다. 즉, 사후 분포는 데이터를 관찰하여 모수의 불확실성(사전 분포)을 보정한 결과라고 할 수 있다.

    한편, 어떤 우도 함수에 대하여 적절한 사전 분포를 정하면 사후, 사전 분포를 서로 같게 할 수 있는데, 이 사전 분포를 공액 사전 분포 conjugate prior distribution이라고 부른다. 예를 들어, 우도 함수가 정규 분포일때 사전 분포를 정규 분포로 하면 사후 분포도 정규 분포가 된다. 

    지금까지의 내용은 모수 $\theta$에 관한 내용이었다. 그런데 우리가 모델을 만들고 예측을 할 때에는 $\theta$가 개입하지 않는다. 즉, 기존에 관찰한 $\mathcal{D}$로 새로운 데이터 $\tilde{x}$를 예측을 한다는 것은 다음을 구하는 것이다.

$$\begin{array}{}\text{(2)}& p(\tilde{x}|\mathcal{D})=\int p(\tilde{x}|\theta )p(\theta |\mathcal{D})d\theta \end{array}$$

    이때 $p(\tilde{x}|\mathcal{D})$를 사후 예측 분포 posterior predictive distribution이라고 부른다. 전통적인 통계 Frequentist와는 다르게 $\theta$의 추정치를 모델에 직접 대입하지 않고 $\theta$에 대한 적분을 하는 것은 $\theta$가 변수 random variable이기 때문이다. 즉, 사후 예측 분포는 $p(\tilde{x}|\theta )$를 가중평균한 것이라고 할 수 있다. 어떤 분포의 기대값 expectation을 구하기 위하여 정의역 domain에 대한 적분을 하는 것과 비슷한 개념이다.

    만약 $p(\tilde{x}|\mathcal{D})$가 알려진 분포가 아닌 경우 그 분포를 MCMC나 Variational Inference 등으로 근사해야 한다. 하지만 그러한 작업들은 계산 시간이 오래 걸리거나 복잡한 경우가 많다. 그래서 사후 분포를 최대화하는 $\theta$를 구하여 $p(\tilde{x}|\mathcal{D})$에 대입하여 사후 예측 분포를 추정하기도한다. 이때 사후 분포를 최대화하는 값을 $\theta$ 의 MAP Maximum A Posteriori라고 한다. ML Maximum Likelihood와 비슷한데, 우도가 아닌 사후 분포를 최대화한다는 것이 다르다.

$$\begin{array}{rcl}{\hat{\theta }}_{MAP}& =& \text{arg}\underset{\theta }{max}p(\theta |\mathcal{D})\\ \text{(3)}& & =& \text{arg}\underset{\theta }{max}p(\mathcal{D}|\theta )p(\theta )\end{array}$$

    MAP으로 사후 예측 분포를 추정하는 방식을 사후 분포의 분산과 관련지어 생각해 볼 수 있다. 만약 표본의 수 $n$이 커서 사후 분포의 분산이 충분하게 작아진다면 사후 분포는 델타 함수와 유사하게 될 것이다. 그리고 델타 함수의 성질에 의하여 사후 분포를 다음과 같이 간단하게 나타낼 수 있는데, 이를 plug-in principle 또는 plug-in approximation이라고 부른다.

$$\begin{array}{}\text{(4)}& p(\theta |\mathcal{D})\approx \delta (\theta -{\hat{\theta }}_{MAP})\to p(\tilde{x}|\mathcal{D})\approx \int p(\tilde{x}|\theta )\delta (\theta -{\hat{\theta }}_{MAP})d\theta =p(\tilde{x}|{\hat{\theta }}_{MAP})\end{array}$$

2.2. 여러가지 분포

    나이브 베이즈에서 사용되는 몇가지 확률 분포와 그 성질을 소개한다.

2.2.1. 다항분포 Multinomial distribution

    다항 분포 Multinomial distribution은 $n$번의 독립된 시행 각각이 $K$ 개의 결과 $A_1,A_2,\cdots ,A_K$를 가지는 상황에 대한 분포이다. 예를 들어, 주사위를 100번 던질 때 각 면이 나오는 횟수는 다항 분포를 따른다. $n=1$인 다항 분포는 Categorical distribution $Cat(x;\mathcal{P})$이라고 부른다. $\mathcal{P}=(p_1,p_2,\cdots ,p_K)$를 $A_1,A_2,\cdots ,A_K$가 일어날 확률이라고 정의하면 다항 분포의 확률 밀도 함수 $Mult(x;\mathcal{P})$는 다음과 같다. 단, $\sum _k{x}_k=n$, $\sum _k{p}_k=1$이다.

$$\begin{array}{}\text{(5)}& f(x_1,x_2,\cdots ,x_k;n,p_1,p_2,\cdots ,p_K)=\frac{\mathrm{\Gamma }(n+1)}{\prod _k\mathrm{\Gamma }(x_k+1)}\prod _k{p}_k^{x_k}\end{array}$$

2.2.2. 디리클레 분포 Dirichlet distribution

    디리클레 분포 Dirichlet distribution은 벡터 $\mathcal{P}=(p_1,p_2,\cdots ,p_K)\in {\mathbb{R}}^K$의 각 원소가 0보다 큰 양수이며 그 합이 1인 벡터에 대한 분포이다. 예를 들어, 어떤 주사위의 각 면이 나올 확률, 가위 바위 보를 할 때 각 수가 나올 확률이 디리클레 분포를 따른다. 양수 벡터 $\alpha =({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_K)$를 모수로 가지며 확률 밀도 함수 $Dir(\mathcal{P};\alpha )$는 다음과 같다. 단, ${\alpha }_0=\sum _i{\alpha }_i$이다.

 

$$\begin{array}{}\text{(6)}& f(p_1,p_2,\cdots ,p_K;{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_K)=\frac{\mathrm{\Gamma }({\alpha }_0)}{\prod _k\mathrm{\Gamma }({\alpha }_k)}\prod _k{p}_k^{{\alpha }_k-1}\end{array}$$

    디리클레 분포의 주변 확률 분포 marginal probability distribution은 베타 분포가 된다. 즉, $p_i\sim Beta({\alpha }_i,{\alpha }_0-{\alpha }_i)$이다. 그리고 정의역의 특성에서 알 수 있듯이 디리클레 분포는 확률에 관한 분포로 볼 수 있으며, 다음과 같이 다항 분포의 공액 사전 분포가 된다.

$$\begin{array}{rcl}p(\mathcal{P}|\mathcal{D})& \propto & p(\mathcal{D}|\mathcal{P})p(\mathcal{P}|\alpha )\propto \prod _k{p}_k^{x_k}\prod _k{p}_k^{{\alpha }_k-1}\\ \text{(9)}& & \propto & Dir(\mathcal{P};{\alpha }_1+x_1,{\alpha }_2+x_2,\cdots ,{\alpha }_K+x_K)\end{array}$$

    이 사후 분포의 MAP ${\hat{p}}_k$는 다음과 같이 구할 수 있다.^[각주:2] 먼저 사후 분포에 $\log$를 취한 후 제약 조건을 더하여 $f$를 구한다.  

$$\begin{array}{}\text{(10)}& f(\mathcal{P},\lambda )=\sum _k{x}_k\log p_k+\sum _k({\alpha }_k-1)\log p_k+\lambda (1-\sum _k{p}_k)\end{array}$$

    이제 $\lambda$에 대한 미분 계수를 계산한다.

$$\begin{array}{}\text{(11)}& \frac{\partial f}{\partial \lambda }=1-\sum _k{p}_k=0\end{array}$$

    그리고 $p_k$에 대한 미분 계수를 구한 후 확률의 합이 1인 것을 이용하여 $\lambda$를 구한다.

$$\begin{array}{rcl}\frac{\partial f}{\partial p_k}=\frac{x_k^{\prime }}{p_k}-\lambda =0& \iff & x_k^{\prime }=\lambda p_{k}where{x}_k^{\prime }=x_k+{\alpha }_k-1\\ & \iff & \sum _k{x}_k^{\prime }=\lambda \sum _k{p}_k\\ \text{(12)}& & \iff & x_0+{\alpha }_0-K=\lambda where{x}_0=\sum _k{x}_k\end{array}$$

    따라서 ${\hat{p}}_k=(x_k+{\alpha }_k-1)/(x_0+{\alpha }_0-K)$ 이다.

2.2.3. Dirichlet-Multinomial distribution

    Dirichlet-Multinomial distribution은 다항 분포와 디리클레 분포가 결합된 형태이다. 양수 벡터 $\alpha =({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_K)$를 모수로 가지며 확률 밀도 함수 $p(x;\alpha )$는 다음과 같다.

$$\begin{array}{rcl}p(x;\alpha )& =& \int Mult(x;\mathcal{P})Dir(\mathcal{P};\alpha )d\mathcal{P}\\ & =& \int \frac{\mathrm{\Gamma }(n+1)}{\prod _k\mathrm{\Gamma }(x_k+1)}\prod _k{p}_k^{x_k}\frac{\mathrm{\Gamma }({\alpha }_0)}{\prod _k\mathrm{\Gamma }({\alpha }_k)}\prod _k{p}_k^{{\alpha }_k-1}d\mathcal{P}\\ & =& \frac{\mathrm{\Gamma }(n+1)}{\prod _k\mathrm{\Gamma }(x_k+1)}\frac{\mathrm{\Gamma }({\alpha }_0)}{\prod _k\mathrm{\Gamma }({\alpha }_k)}\int \prod _k{p}_k^{x_k+{\alpha }_k-1}d\mathcal{P}\\ \text{(13)}& & =& \frac{n!\mathrm{\Gamma }({\alpha }_0)}{\mathrm{\Gamma }(n+{\alpha }_0)}\prod _k\frac{\mathrm{\Gamma }(x_k+{\alpha }_k)}{x_k!\mathrm{\Gamma }({\alpha }_k)}\end{array}$$

    $n=1$일 때 Categorical distribution이 되며 $\alpha$가 적당히 크다면 다항 분포에 근사한다.^[각주:3]

$$\begin{array}{rcl}\frac{n!\mathrm{\Gamma }({\alpha }_0)}{\mathrm{\Gamma }(n+{\alpha }_0)}\prod _k\frac{\mathrm{\Gamma }(x_k+{\alpha }_k)}{x_k!\mathrm{\Gamma }({\alpha }_k)}& \approx & \frac{n!}{{\alpha }_0^n}\prod _k\frac{{\alpha }_k^{n_k}}{n_k!}\because \frac{\mathrm{\Gamma }(x+\beta )}{\mathrm{\Gamma }(x)}\approx x^{\beta }forlargex\\ \text{(14)}& & =& \frac{n!}{\prod _k{n}_k!}\prod _k{\left(\frac{{\alpha }_k}{{\alpha }_0}\right)}^{n_k}\end{array}$$

3. Naive Bayes Classification

그림 1. 귀여운 아기 수달

    한 문장 안의 여러 단어들은 그 사용 빈도에 있어 서로 밀접한 관련이 있다. 그림 1을 보자. 어떤 문장에 수달이라는 단어가 있다면, 그 문장에 "귀엽다"라는 단어도 등장할 가능성이 크다. 반면 입자 가속기라는 단어가 있는 문장에서 "귀엽다"라는 단어를 찾기는 어려울 것이다.

    그리고 한 문장 내 단어들은 등장 순서에도 서로 상관이 있다. 일반적으로 한국어 문장에서는 주어가 가장 처음에 나오고 동사가 가장 나중에 나오기 때문이다.^[각주:4] 이러한 관계를 $15$와 같이 나타낼 수 있다. $x_i$는 $i$번째 메시지의 단어를 벡터로 나타낸 것, $x_{ik}$는 $x_i$의 $k$번째 원소, $y_i$는 $i$번째 메시지의 분류 그리고 ${\theta }_c$를 분류 $c$의 모수이다.

$$\begin{array}{rcl}p(x_i|y_i=c,{\theta }_c)& =& p(x_{i1},x_{i2},\cdots ,x_{iK}|y_i=c,{\theta }_c)\\ & =& p(x_{i1}|x_{i2},\cdots ,x_{iK},y_i=c,{\theta }_c)p(x_{i2},\cdots ,x_{iK}|y_i=c,{\theta }_c)\\ \text{(15)}& & =& \cdots \end{array}$$

    하지만 나이브 베이즈에서는 이러한 사실들을 무시한다. 즉, 문장에 어떤 단어가 등장할 확률은 다른 단어의 존재 여부 및 순서와 무관하다라고 "나이브"하게 가정한다. 즉 식 $(15)$을 식 $(16)$과 같이 간결하게 표시할 수 있다.

$$\begin{array}{rcl}p(x_i|y_i=c,{\theta }_c)& =& p(x_{i1},x_{i2},\cdots ,x_{iK}|y_i=c,{\theta }_c)\\ \text{(16)}& & =& \prod _k^{K}p(x_{ik}|y_i=c,{\theta }_c)\because p(x_{ij}|x_{i,j+1},\cdots ,x_{iK},y_i=c,{\theta }_c)=p(x_{ij}|y_i=c,{\theta }_c)\end{array}$$

    이제 나이브 베이즈가 어떻게 동작하는지 보자. 표 1과 같이 나이브 베이즈의 가정에 맞추어 5개의 메시지에서 단어를 순서없이 추출하였다. 그리고 어떤 메시지로부터 추출한 단어가 (call, happy, fine, otter)이라고 할 때 이 메시지가 정상(ham)인지 스팸(spam)인지 분류해보자.

표 1. 학습용 메시지

메세지 ID	메시지로부터 추출한 단어	분류
1	fine, hope, fine, care	ham
2	happy, year, hope, good, semester	ham
3	premium, phone, service, call	spam
4	fine, give, call, question	ham
5	call, immediately, urgent, message, waiting	spam

    먼저 단어장 $V$를 만들자. $V$는 유일한 단어로 구성되므로 $V=\{$ fine, hope, care, happy, year, good, semester, premium, phone, service, call, give, question, immediately, urgent, message, waiting$\}$라고 할 수 있으며 $V$의 길이 $K$는 17이다. 이제 $V$에 맞추어 각 메시지를 인코딩하는 작업이 필요한데 가능한 방법이 두가지가 있다. 첫번째 방법은 등장 여부로 인코딩하는 것이다. 즉, ID가 1인 메시지의 경우 $(1,1,1,0,\cdots ,0)$으로 만들 수 있다. 두번째 방법은 단어가 등장한 횟수로 인코딩하는 것이다. 메시지 1의 경우 $(2,1,1,0,\cdots ,0)$이며 단어의 총 개수 $n_1$는 4이다. 인코딩의 방법에 따라 우도 함수와 공액 사전 분포를 다르게 해야 하는데 여기서는 두번째 방법을 사용한다. 마지막으로 분류의 개수 $C$는 2이다. 

    사후 예측 분포 $p(\tilde{y}|\tilde{x},\mathcal{D})=\int p(\tilde{x}|\tilde{y}=c,{\theta }_c,\mathcal{D})p(\tilde{y}=c|\pi ,\mathcal{D})p({\theta }_c,\pi |\mathcal{D})d{\theta }_{c}d\pi$를 구성하기 위하여 먼저 사후 분포 $p({\theta }_c,\pi |\mathcal{D})$가 필요하다. 단, $\pi$는 $y_i$에 대한 모수이다.

$$\begin{array}{}\text{(17)}& p({\theta }_c,\pi |\mathcal{D})& \propto & \prod _{i}p(x_i|y_i=c,{\theta }_c,\pi )p(y_i=c|{\theta }_c,\pi )p({\theta }_c,\pi )\end{array}$$

    식 $(17)$에서 $\prod _{i}p(x_i|y_i=c,{\theta }_c,\pi )$는 메시지의 단어에 대한 우도 함수이다. $x_i$를 단어의 개수로 인코딩을 하였으므로 다항 분포라고 하자. 단, $N_{kc}=\sum _i{x}_{ik}$이다.

$$\begin{array}{}\text{(18)}& \prod _{i}p(x_i|y_i=c,{\theta }_c,\pi )\propto \prod _i\prod _k{\theta }_{kc}^{x_{ik}}\propto \prod _k{\theta }_{kc}^{N_{kc}}\end{array}$$

    식 $(17)$에서 $p(y_i=c|\pi )$는 $i$번째 메시지의 분류에 대한 우도 함수이다. $C$개 중 하나를 고르는 것과 같으므로 Categorical distribution으로 하자. 단, $N_c$는 학습용 데이터에서 분류 $c$에 해당하는 메시지의 개수이다.

$$\begin{array}{}\text{(19)}& \prod _{i}p(y_i=c|\pi )\propto \prod _i\prod _c{\pi }_c^{I(y_i=c)}\propto \prod _c{\pi }_c^{N_c}\end{array}$$

    식 $(17)$에서 $p({\theta }_c,\pi )$는 모수에 대한 사전 분포이다. 각각이 독립이라고 가정하고 공액 사전 분포를 만들기 위하여 모두 디리클레 분포로 정한다. 그리고 hyper parameter로 ${\beta }_c,\alpha$를 주자. $\beta ,\alpha$의 차원은 각각 $K,C$이다. 이렇게 구성한 사전 분포가 다음과 같다.

$$\begin{array}{}\text{(20)}& p(\pi |\alpha )p({\theta }_c|{\beta }_c)=Dir(\pi ;\alpha )Dir({\theta }_c;{\beta }_c)\propto \prod _c{\pi }_c^{{\alpha }_c-1}\prod _k{\theta }_{kc}^{{\beta }_{kc}-1}\end{array}$$

    식 $(20)$을 식 $(17)$에 대입하여 다음을 얻는다.

$$\begin{array}{rcl}p({\theta }_c,\pi |\mathcal{D})& \propto & \prod _k{\theta }_{kc}^{\sum _i{x}_{ik}}\prod _c{\pi }_c^{N_c}\prod _c{\pi }_c^{{\alpha }_c-1}\prod _k{\theta }_{kc}^{{\beta }_{kc}-1}\\ & \propto & \prod _k{\theta }_{kc}^{N_{kc}+{\beta }_{kc}-1}\prod _c{\pi }_c^{N_c+{\alpha }_c-1}\\ \text{(21)}& & \propto & Dir({\theta }_c|N_{1c}+{\beta }_{1c},\cdots ,N_{Kc}+{\beta }_{Kc})Dir(\pi |N_1+{\alpha }_1,\cdots ,N_C+{\alpha }_C)\end{array}$$

    이 사후 분포를 통하여 사후 예측 분포를 쉽게 구할 수 있다.

$$\begin{array}{rcl}p(\tilde{y}|\tilde{x},\mathcal{D})& =& \int p(\tilde{x}|\tilde{y}=c,{\theta }_c,\mathcal{D})p(\tilde{y}=c|\pi ,\mathcal{D})p({\theta }_c,\pi |\mathcal{D})d{\theta }_{c}d\pi \\ & =& \int Cat(\tilde{y}=c;\pi )Dir(\pi ;N_1+{\alpha }_1,\cdots ,N_C+{\alpha }_C)d\pi \\ & \times & \int Mult(\tilde{x};{\theta }_c)Dir({\theta }_c;N_{1c}+{\beta }_{1c},\cdots ,N_{Kc}+{\beta }_{Kc})d{\theta }_c\\ \text{(22)}& & =& \left(\frac{N_c+{\alpha }_c}{N+{\alpha }_0}\right)\frac{\tilde{n}!\mathrm{\Gamma }({\beta }_{0c}+N_c)}{\mathrm{\Gamma }(\tilde{n}+{\beta }_{0c}+N_c)}\prod _k\frac{\mathrm{\Gamma }({\tilde{x}}_k+{\beta }_{kc}+N_{kc})}{{\tilde{x}}_k!\mathrm{\Gamma }({\beta }_{kc}+N_{kc})}\end{array}$$

    즉, 사후 예측 분포는 Categorical Distribution과 Dirichlet-Multinomial Distribution의 곱으로 나타난다는 것을 알 수 있다. Dirichlet-Multinomial Distribution이 다항 분포로 근사한다는 것을 이용하면 사후 예측 분포를 다음과 같이 쓸 수도 있다.

$$\begin{array}{}\text{(23)}& p(\tilde{y}=c|\tilde{x},\mathcal{D})\approx \left(\frac{N_c+{\alpha }_c}{N+{\alpha }_0}\right)\frac{\tilde{n}!}{\prod _k{\tilde{x}}_k!}\prod _k{\left(\frac{{\beta }_{kc}+N_{kc}}{{\beta }_{0c}+N_c}\right)}^{{\tilde{x}}_k}\end{array}$$

    한편, MAP을 사후 분포에 대입하여 사후 예측 분포를 근사할 수도 있다.

$$\begin{array}{rcl}p(\tilde{y}=c|\tilde{x},\mathcal{D})& \approx & p(\tilde{y}=c|\tilde{x},{\hat{\theta }}_c,\hat{\pi })\\ & \propto & p(\tilde{y}=c|\hat{\pi })p(\hat{x}|\tilde{y}=c,{\hat{\theta }}_c)\\ \text{(24)}& & \propto & \left(\frac{N_c+{\alpha }_c-1}{N+{\alpha }_0-C}\right)\frac{\tilde{n}!}{\prod _k{\tilde{x}}_k!}\prod _k{\left(\frac{N_{kc}+{\beta }_{kc}-1}{N_c+{\beta }_{0c}-K}\right)}^{{\tilde{x}}_k}\end{array}$$

    사후 예측 분포를 직접 구한 결과와 MAP을 대입하여 추정한 결과가 유사하다. 식 $(23)$과 식 $(24)$에 적절한 ${\beta }_{kc}$, ${\alpha }_c$를 주면 서로 같은 형태를 만들 수도 있다.^[각주:5] 예를 들어 식 $(23)$에서 ${\beta }_{kc}=1$, 식 $(24)$에서는 ${\beta }_{kc}=2$로 정한다면 서로 같은 분포가 된다.

    사후 예측 분포를 사용한 예측 ${\hat{y}}_{post}$이 식 $(25)$와 같다. Underflow를 방지하기 위해서 로그 변환을 사용한다. 또한 $c$가 포함되어 있지 않은 항은 모든 $c$에 대하여 같은 값을 가지므로 생략할 수 있다. 그리고 $\tilde{n}=\sum _k{\tilde{x}}_k$이다.

$$\begin{array}{rcl}{\hat{y}}_{post}& =& \text{arg}\underset{c}{max}p(\tilde{y}|\tilde{x},\mathcal{D})\\ & =& \text{arg}\underset{c}{max}\left(\frac{N_c+{\alpha }_c}{N+{\alpha }_0}\right)\frac{\tilde{n}!\mathrm{\Gamma }({\beta }_{0c}+N_c)}{\mathrm{\Gamma }(\tilde{n}+{\beta }_{0c}+N_c)}\prod _k\frac{\mathrm{\Gamma }({\tilde{x}}_k+{\beta }_{kc}+N_{kc})}{{\tilde{x}}_k!\mathrm{\Gamma }({\beta }_{kc}+N_{kc})}\\ & =& \text{arg}\underset{c}{max}\log (N_c+{\alpha }_c)+\log \mathrm{\Gamma }({\beta }_{0c}+N_c)-\log \mathrm{\Gamma }(\tilde{n}+{\beta }_{0c}+N_c)\\ \text{(25)}& & +& \sum _k\log \mathrm{\Gamma }({\tilde{x}}_k+{\beta }_{kc}+N_{kc})-\sum _k\log \mathrm{\Gamma }({\beta }_{kc}+N_{kc})\end{array}$$

    MAP을 사용한 예측 ${\hat{y}}_{MAP}$이 식 $(26)$과 같다.

$$\begin{array}{rcl}{\hat{y}}_{MAP}& =& \text{arg}\underset{c}{max}p(\tilde{y}=c|\tilde{x},{\hat{\theta }}_c,\hat{\pi })\\ & =& \text{arg}\underset{c}{max}\left(\frac{N_c+{\alpha }_c-1}{N+{\alpha }_0-C}\right)\frac{\tilde{n}!}{\prod _k{\tilde{x}}_k!}\prod _k{\left(\frac{N_{kc}+{\beta }_{kc}-1}{N_c+{\beta }_{0c}-K}\right)}^{{\tilde{x}}_k}\\ \text{(26)}& & =& \text{arg}\underset{c}{max}\log (N_c+{\alpha }_c-1)+\sum _k{\tilde{x}}_k\log (N_{kc}+{\beta }_{kc}-1)-\tilde{n}\log (N_c+{\beta }_{0c}-K)\end{array}$$

    이제 키워드 call, happy, fine, otter가 있는 메시지를 분류해보자. 식 $(25)$와 $(26)$을 사용하기 위한 변수가 표 2와 같다.

표 2. 예측을 위한 변수의 값

	Label
	ham	spam
$N_c$	5	2
$N_{happy,c}$	1	0
$N_{call,c}$	1	2
$N_{fine,c}$	3	0
$N_{otter,c}$	0	0

    이때 고려해야 할 문제가 한가지 있는데, ${\alpha }_c$와 같은 hyper parameter의 값으로 어떻게 정하냐는 것이다. hyper parameter는 우리가 모수에 관해 가지고 있던 생각을 반영한다. 만약 아무런 정보를 가지고 있지 않다면 모든 hyper parameter가 1의 값을 갖게 할 수 있다. 이는 사전 분포가 균등 분포 Uniform distribution이라는 것을 의미한다.

    하지만 균등 분포를 사전 분포로 하는 것은 MAP을 이용한 예측 시 문제가 된다. otter와 같이 학습 데이터에 없는 단어가 테스트에 등장할 시 $P({\hat{y}}_{MAP}=c)$가 모든 $c$에 대하여 0이 되어 버리기 때문이다.^[각주:6] 이를 방지하기 위하여 MAP을 이용한 예측 시, ${\beta }_{kc}=2$의 값을 주어 어떤 단어라도 등장할 가능성이 있다는 것을 열어둔다. 이을 라플라스 평활 Laplace smoothing이라고도 부른다. 사후 예측 분포를 이용하는 경우에는 예측 확률이 0이 되지 않기 때문에 ${\beta }_{kc}=1$의 값을 주고 ${\alpha }_c$는 모두 0으로 설정한다.

    식 $(25)$와 $(26)$은 대소 비교를 통하여 예측을 하기위한 척도지 일반적인 의미의 확률은 아니다. 확률을 구하기 위해서는 $\exp$를 취해야 하는데, Underflow를 방지하기 위하여 값들 중 최대값을 각 값에서 뺀 후 진행하는 것이 효과적이다. 예를 들어, 어떤 메시지가 분류 $A$일 "가능성" -30, $B$일 "가능성"가 -35라고 하자. 그 메시지가 $A$일 확률은 $e^{-30}/(e^{-30}+e^{-35})$인데, $e^{-35}$를 계산하는 과정에서 Underflow의 가능성이 있다. 따라서 각 "가능성"에서 최대값인 -30을 뺀 후 그 메시지가 $A$일 확률을 구하면 $1/(1+e^{-5})$로 전과 동일하고 Underflow가 일어나는 것도 방지할 수 있다.

   

    위의 내용을 바탕으로 키워드 call, happy, fine, otter가 있는 메시지는, 사후 예측 분포를 사용한 경우 86.695%, MAP을 사용한 경우 86.857%의 확률로 ham으로 분류된다. 두 방법이 차이가 거의 없음을 알 수 있는데, 이는 Dirichlet-Multinomial distribution이 다항 분포에 잘 근사하기 때문이다. 이 값을 확인하기 위해서는 이 링크의 코드를 실행하면 된다.

4. Naive Bayes를 이용한 메시지 분류

4.1. 데이터 소개 및 메시지 분류

    SMS Spam Cellection은 5,574개의 영어 메시지를 담은 데이터셋으로 4,827개의 정상(ham) 메시지와 747개의 스팸(spam) 메시지가 있다. 이 데이터에 대한 자세한 설명은 여기에 있으며 메시지의 일부는 다음과 같다. 

표 3. SMS Spam Cellection의 일부

분류	내용
ham	What you doing? how are you?
ham	Ok lar... Joking wif u oni...
spam	Sunshine Quiz! Win a super Sony DVD recorder if you canname the capital of Australia? Text MQUIZ to 82277.
spam	URGENT! Your Mobile No 07808726822 was awarded a L2,000 Bonus Caller Prize on 02/09/03! This is our 2nd attempt to contact YOU! Call 0871-872-9758 BOX95QU
ham	Cos i was out shopping wif darren jus now n i called him 2 ask wat present he wan lor. Then he started guessing who i was wif n he finally guessed darren lor.

   

    이 데이터 셋은 학습 데이터와 테스트 데이터가 따로 구분되어 있지 않으므로 학습용/테스트용 데이터를 약 4:1 비율로 나눈다. 본 포스팅에서는 난수를 생성하여 각각 4,465개 1,109개로 나누었다. 사전에 seed를 주었기 때문에 결과를 재연할 수 있을 것이다. 구현에는 Python 3.5.2(Anaconda 4.1.1)를 사용하였다.

    학습 데이터에서 메시지를 띄어쓰기 단위로 분리하여 단어를 추출하자. $K$는 13,752이며 테스트 데이터로 분류기의 성능을 평가한 결과, 95.85%의 예측이 본래의 분류와 같았다. "나이브"한 가정과 쉬운 구현을 고려해볼 때 괜찮은 결과이다. 결과를 재연하기 위해서는 이 링크의 파일을 받아 main.py를 실행하면 된다.

4.2. 데이터 전처리를 통한 성능 향상

    데이터 전처리를 통하여 이 분류기의 성능을 높일 수 있다. 먼저 생각할 수 있는 것은 영문자를 모두 소문자 또는 대문자로 통일하는 것이다. 이 작업을 하기 전에는 Cat과 cat이 서로 다른 단어로 취급되기 때문에 그 단어에 대한 과소 추정이 일어나게 된다. 물론 영문장의 특성상 Cat과 cat은 다른 위치에 있을 가능성이 높다. 하지만 나이브 베이즈의 가정을 고려해볼 때, 단어를 모두 대문자 또는 소문자로 변환하는 것이 합리적이다. 

    그 다음으로 생각할 수 있는 것은 숫자를 제거하는 것이다. 일반적으로 숫자는 단어로서의 기능을 갖지 않기 때문이다. 하지만 특정한 상황에서 숫자도 문장을 분류하는데 도움을 줄 수 있다. "대한민국이 16강에 진출하였다.", "루나틱하이가 오버워치 APEX 시즌 3에서 2연패를 달성하였다.", "100% 당첨!"과 같은 문장이 그러한 예이다. 이와 같은 문장에 사용되는 숫자는 제거하지 않는 것이 좋을 수도 있다. 

    구두점 punctuation을 제거하는 것도 좋은 방법이다. "수달... 넘나 귀여운 것"과 "수달, 넘나 귀여운 것"는 다른 뉘앙스를 전달하지만 같은 뜻을 지니고 있다. 하지만 "수달..."과 "수달,"이 다른 단어로 취급되어 "수달"에 대한 과소 추정이 일어나게 된다. 구두점을 제거하게 되면 모두 같은 단어가 되어 정확한 계측을 할 수 있다.

    일반적인 문장에서 자주 사용되는 단어들이 있다. 영어에서는 the, be, you, 한국어에서는 ~다, 나, 그리고 등이 있다. 이러한 단어들을 불용어 Stopwords 라고 부른다. 불용어는 문장을 분류하늗네 큰 도움이 되지 못할 뿐만 아니라 그 단어가 포함되지 않은 경우 추정을 왜곡하기도 한다. 따라서 이들을 단어장에서 제거하는 것이 좋다. 본 포스팅에서는 MySQL의 영어 정지어를 사용하여 전처리를 진행한다. 

    이밖에도 너무 짧은 문자 제거하기, 활용형을 원형으로 바꾸기^[각주:7] 등이 있다. 지금까지 소개한 전처리 방법을 이용하여 본 데이터를 가공한 결과, $K=7398$이 되었으며 1,115개의 테스트 메시지를 97.85%의 정확도로 분류하게 되었다. 

5. 마치며

    얼마전 어떤 시험 문제로 나이브 베이즈를 구현하라는 것이 나왔다. 나이브 베이즈는 보통 머신 러닝 책의 초반에 짧게 소개되는 경우가 많고 크게 어렵지 않은 방법론으로 알려져 있다. 그래서 나는 나는 그것을 쉽게 할 수 있으리라 생각했다. 하지만 책상 앞에 앉으니 내가 그것을 제대로 이해하지 못하고 있다는 의문이 들었다. 사실 그때 작성한 코드를 보면 의문이 아니라 사실임이 분명해 보인다. 시험이 끝나고 나서도 불편한 마음이 끊이질 않아 이 포스팅을 작성하게 되었다. 나이브 베이즈에 대한 몇가지 의문이 해소되어 좋다.

1. 출처: 위키피디아, https://en.wikipedia.org/wiki/Naive_Bayes_classifier [본문으로]
2. 출처: Kevin P. Murphy, Machine Learning, 2012 [본문으로]
3. 감마 함수 비의 근사에 대해서는 다음을 참고하라. F Tricomi, 1951, The asymptotic expansion of a ratio of gamma functions [본문으로]
4. 한국어는 조사가 있어 문장 순서의 엄격함이 다른 종류의 언어보다 덜 하지만 일반적인 어순은 존재한다. [본문으로]
5. 하지만 이러한 작업은 일반적으로 권장되지 않는다. 출처: Jason D.M. Rennie, 2001, Improving Multi-class Text Classification with Naive Bayes [본문으로]
6. 물론 log 변환도 되지 않는다. [본문으로]
7. 예: went-> go, 갔다 -> 가다 [본문으로]