Lecture 6: Naive Bayes, Laplace smoothing

다 들었는데 블로그에 글을 안써서... 특히 수식 변환 쓰는 난이도가 더럽게 어렵다.

---

Source of Knowledge

 

• assumptions$($가설$)$
• data$($현실에서의 경험, 데이터$)$

 

Example: Spam Classification

 

이메일에서의 text를 feature vector $x \in \mathbb{R}^d$로 변환한다고 하자. one-hot encoding을 사용하고, $d$가 사전에 있는 단어들의 개수라 정의할 때, $x_i$는 사전에 $i$번째 단어가 등장하는 경우 $1$으로 정의된다. 

 

예를 들어, I ate apple이라는 문장은 사전이 $[I, am, main, function, ate, apple]$일때 $[1, 0, 0, 0, 1, 1]$로 변형된다는 것이다. 이걸 이용해 Naive Bayes를 설명해 보자.

 

Naive Bayes

 

Naive Bayes는 MLE와 베이즈 정리를 이용한 분류 알고리즘이다. Naive Bayes에서 선행돼야 하는 조건은 다음과 같다.

 

• feature vector $x$의 원소 $x_1, x_2, \cdots, x_d$는 $y$에 대해서 서로 독립이다. 즉 $P(x_1, x_2, \cdots, x_d | y) = \prod_{i=1}^{d} P(x_i | y)$

$\phi_{j|y = k} = P(x_j = 1 | y = 1), \phi_{j|y = 0} = P(x_j = 1 | y = 0)$라고 하면 우리가 maximum하게 만들어야 하는 Likelihood function은 다음과 같다.

 

• $\prod P(x^{(i)}, y^{(i)} ; \phi_y, \phi_{j|y})$
• $= \prod P(x^{(i)} | y^{(i)} ; \phi_y, \phi_{j|y}) \times P(y^{(i)} ; \phi_y, \phi_{j|y})$
• $= \prod (P(y^{(i)} ; \phi_y) \prod P(x_{j}^{(i)} | y^{(i)} ; \phi_{j|y}))$

위의 식에 log를 씌우고 미분을 하거나 적절하게 카운팅하면 데이터에 맞는 확률을 구할 수 있다.

 

• $\phi_y = \frac{\sum_{i=1}^{n} [y^{(i)} = 1]}{n}$
• $\phi_{j | y = 1} = \frac{\sum_{i=1}^{n} [x^{(i)} = 1, y^{(i)} = 1]}{y^{(i)} = 1}$
• $\phi_{j | y = 0} = \frac{\sum_{i=1}^{n} [x^{(i)} = 1, y^{(i)} = 0]}{y^{(i)} = 0}$

이제 예측을 해보자! 우리가 아는 Bayes' rule에 따라서 x인 데이터가 1일 확률을 계산할 때 다음과 같은 계산이 가능하다.

 

$P(y = 1 | x) = \frac{P(x | y = 1)P(y = 1)}{P(x)}$

 

여기서 $P(y = 1) = \phi_y$, $P(x | y = 1) = \prod P(x^{(i)} | y)$이고 $P(x)$는 예측끼리 비교할 때 지워지므로 $argmax P(y = j | x)$인 $j$를 쉽게 결정할 수 있다.

 

Laplace smoothing

 

만약 사전에 존재하는 단어 중 어떠한 데이터에도 포함되지 않은 단어가 $j$번째에 위치한다고 생각해보자. 그렇다면 학습 후 $j$번째 단어에 대한 확률은 $\phi_{j | y = 1} = \phi_{j | y = 0} = 0$으로 계산되어 예측할 때 확률 계산에도 0으로 결과가 나올 것이다. 이것을 방지하기 위해 Laplace smoothing을 사용한다.

 

Laplace smoothing은 단순히 $P(x | y) = \frac{count(x, y) + a}{count(y) + a \dot N}$으로 만드는 것이다. 즉, 모든 데이터는 최소 $a$만큼의 확률을 가지게 만든다.