[머신 러닝] 나이브 베이즈 분류기 (Naive Bayes Classifier, NBC)

Naive Bayes Classifier (NBC)는 스팸 필터, 문서 분류 등에 사용되는 분류기이다. NBC의 기본 원리는 posterior probability에 베이즈 정리 (Bayes' theorem)과 naive한 가정을 적용하여 데이터를 분류하는 것이다.  NBC는 1950년대 이후 광범위하게 연구되고 있으며, 적절한 전처리를 거치면 서포트 벡터 머신 (Support Vector Machine)과도 경쟁할 만큼 우수한 분류 성능을 보여준다.

1. Decision rule

먼저, state of nature $\omega_k \in \{0, 1 \}$를 정의한다. $\omega_k$는 $k$번째 class인 $c_k$가 선택되었을 때, 1의 값을 갖는 binary variable이다. NBC는 주어진 데이터 $x$에 대해 $P(\omega_k|x)$가 가장 클 경우, $x$를 $c_k$에서 생성된 데이터라고 판별한다. NBC에서는 $P(\omega_k|x)$를 계산하기 위해 [식 1]과 같이 베이즈 정리를 적용한다.

그러나 $p(x|\omega_k) = p(x_1, x_2, ..., x_d|\omega_k)$를 계산하기 위해서는 입력 데이터 $x$를 구성하는 모든 요소 $\{x_1, x_2, ..., x_d\}$의 상관관계를 고려해야 하기 때문에 $p(x|\omega_k$)의 값을 결정하는 것은 매우 어렵거나 때로는 불가능하다. 이러한 문제를 해결하기 위해 NBC에서는 [식 2]와 같이 "naive"한 가정을 한다.

또한, [식 1]에서 $p(x)$는 모든 class에 대해 동일한 값을 갖기 때문에 decision에 영향을 주지 않는다. 따라서, NBC의 decision rule은 아래의 [식 3]과 같다.

2. 예제

NBC는 문서에 포함된 키워드를 통해 문서의 종류를 구분하는 분류기로써 이용될 수 있다. 5개의 문서를 포함하는 training dataset은 아래의 [표 1]과 같다.

[표 1] 문서 분류기를 위한 training dataset

문서를 분류하기 위해 NBC $P(\text{function}|\text{C/C++}), P(\text{class}|\text{C/C++}), ..., P(\text{synchronized}|\text{Java})$와 $P(\text{C/C++}), P(\text{Java})$를 계산해야 한다. 우리는 각각의 word가 나타나는 횟수를 통해 $P(x_i|\omega_k)$를 쉽게 계산할 수 있다. 예를 들어, $P(\text{string}|\text{Java}), P(\text{class}|\text{Java})$ 그리고 $P(\text{Java})$는 아래와 같이 계산된다.

만약, 입력된 문서 $D$가 string, int, array라는 세 가지 word를 포함하고 있다면, NBC는 아래와 같은 과정을 통해 $D$를 Java와 관련된 문서라고 판단한다.

그러나 위와 같은 과정을 통해 데이터를 분류하는 NBC는 아래의 두 가지 문제를 갖고 있다.

• 예제의 $P(\text{string}|\text{C/C++})$과 같이 training dataset에 존재하지 않는 데이터가 나타날 경우에는 $P(x|\omega_k)$가 항상 0으로 계산된다.

• 확률은 항상 1보다 작거나 같은 값을 갖기 때문에 높은 차원의 데이터가 입력될 경우에는 모든 class에 대해 $P(x|\omega_k)$가 모두 0으로 수렴하게 된다.

NBC에서는 아래에 서술할 Laplace smoothing과 log-probability를 이용하여 이러한 두 가지 문제를 해결한다.

3. Laplace smoothing

$P(x_i|\omega_k)$에 대해 Laplace smoothing은 아래의 [식 4]와 같이 적용된다.

[식 4]에서 $count(x_i, \omega)$는 $k$번째 class에서 $x_i$가 나타난 횟수이다. $|\omega_k|$와 $|u|$는 각각 $k$번째 class의 모든 요소의 수와 모든 class에서 유일한 요소의 수를 나타낸다. 예를 들어, Laplace smoothing을 적용하여 계산한 $P(\text{int}|\text{Java})$는 아래와 같다.

4. Log-probability

확률은 항상 1보다 작거나 같은 값을 가져야 하기 때문에 많은 수의 확률을 곱하면 그 값은 0으로 수렴한다. 따라서, 높은 차원의 데이터에 대한 $p(x|\omega_k)$를 [식 2]와 같이 계산하면, 그 값은 항상 0으로 수렴할 것이다. NBC에서는 이러한 문제를 해결하기 위해 [식 2]의 양변에 log를 적용하여 [식 5]와 같이 $p(x|\omega_k)$를 계산한다.

Log는 단조증가함수 (monotonically increasing function)이기 때문에 [식 2] 대신 [식 5]를 사용하여 decision을 내려도 그 결과는 바뀌지 않는다.