1. 개요
나이브 베이즈 분류(Naive Bayes Classification, 이하 NBC)는 가장 기본적이면서 자주 쓰이는 매우 유용한 분류 방법이다. 예제와 함께 나이브 베이즈 분류의 개념과 특징을 알아보고, 한계와 극복 방안, 그리고 활용 사례에 대해 살펴보도록 하겠다.

2. NBC의 기본 가정 및 방법
NBC의 기본적인 가정은, 어떤 객체의 속성들이 서로 독립적이라는 것이다. 예를 들어, 분류해야 할 객체 x의 정보가 벡터로 주어진다면, 각 벡터의 요소들은 x의 속성들이라고 할 수 있으며 이들은 모두 독립적이다. 쉽게 말해서, 인간이라는 객체의 속성을 키와 몸무게라고 가정했을 경우 키와 몸무게가 상호 독립적이라고 가정하는 것이다.
이러한 가정에 의해, x가 주어졌을 때 특정 클래스 C_k로 분류하는 NBC는 다음과 같이 진행할 수 있다.
즉, P(x₁x₂x₃...x_n | C_k)를 P(x_i | C_k)들의 곱이라고 생각한다. 각 요소들의 Class Likelihood를 전부 곱해버리는 것이다. 우선, NBC를 진행하기 전 학습 과정을 의사 코드(Pseudocode)로 나타내면 다음과 같다.
이때 r은 One-hot Encoded Vector이다. 예를 들어, 주어진 데이터 x가 두 번째 클래스(C2)에 속한다는 것을 나타내는 r은 [0 1 0]이다. 따라서, 이 정보를 활용하여 데이터 D가 주어졌을 때, 우선 각 클래스마다 데이터가 몇 개 속해있는지 카운트하여 (1)의 Priority Probability를 구한다. 그 다음, 각 클래스별로 (2)의 Class Likelihood를 구해놓으면 학습이 끝난다.
예시와 함께 살펴보도록 하자. 객체 x는 [키, 몸무게]로 이루어진 벡터로 주어지고, 클래스는 남자 혹은 여자로 주어진다고 가정하자.
그렇다면, D를 구성하는 데이터들은 다음과 같이 주어질 것이다.
이 정보들을 종합하여 위 코드에서 (1)의 Priority Probability를 먼저 구해보자. 데이터들을 카운트하여 표에 정리했더니 다음과 같이 결과가 나타났다고 생각해보자.
그렇다면 전체 데이터 개수 N은 10이기 때문에, P(C₁) = 4 / 10 = 0.4이고, P(C₂) = 6 / 10 = 0.6이라는 사실을 쉽게 알 수 있다. 다음은 (2)의 Class Likelihood를 구해보자. 각 클래스별로, 그리고 각 속성별로 진행을 하면서, 특정 클래스에 속한 데이터 중에서 특정 속성 값을 가진 데이터가 몇 개 있는지 카운트하여 표에 정리한다.
(1)과 (2)를 모두 구하였기 때문에, 분류를 위한 학습이 완료되었다. 그렇다면, 이렇게 학습된 정보를 바탕으로 키가 170, 몸무게가 50인 x가 남자인지 여자인지 분류해보자.
P(C₁ | x)와 P(C₂ | x)를 구했을 때, P(C₂ | x)가 1 / 20으로 더욱 큰 값을 가지므로, x는 C₂, 즉, 남자로 분류된다.

3. NBC의 한계와 극복 방안
NBC는 매우 간단하고 실제 많은 분류 문제에서 강력한 성능을 발휘한다. 단, 문제점이 몇 가지 존재한다. 대표적으로 세 가지 정도를 생각해 볼 수 있는데, 각각에 대해 차근차근 알아보도록 하자.

(1) 실수 데이터의 처리
첫 번째 문제는 데이터의 범위와 관련된 문제이다. 예를 들어, 2의 예제에서 키가 정수가 아닌 실수형으로 주어진다고 생각해보자. 위의 예시에서는 정수형으로 주어졌기 때문에 키가 160인 사람이 몇 명인지 셀 수 있었지만, 키가 170.1, 170.232... 이런식으로 실수로 주어진다면 Class Likelihood를 제대로 구할 수 없다. P(x = v | C_k)가 전부 1 / C_k가 될 것이기 때문이다. 따라서 학습이 제대로 되지 않는다. 또한 분류도 문제이다. 학습 중에는 키가 170.3인 데이터가 없었는데 이 데이터를 분류해야 할 경우, 170.3에 대한 Class Likelihood를 구할 수 없으므로 분류가 제대로 되지 않는다.
이 문제는 완벽하게 해결할 수 없지만, 임시 방편으로 데이터를 정수 구간별로 묶는 방법을 사용할 수 있다. 예를 들어, 10 단위로 몸무게, 키를 묶어서 생각하는 것이다. 이 경우, 170.1, 170.2, 170.3의 키를 가진 각각의 데이터가 존재할 때, 키 170 ~ 180 범위의 데이터가 3개 존재한다고 생각할 수 있게 된다. 또한, 170.4의 키를 가진 데이터가 분류되어야 할 때, 이 데이터가 170 ~ 180 범위에 속한다는 가정 때문에 정상적으로 분류가 가능하게 된다.

(2) 빈번한 0
두 번째 문제는 학습과 분류 과정에서, 확률을 계산한 결과가 0이 나오는 경우가 너무 빈번하다는 것이다. 모든 속성에 대한 Class Likelihood를 곱한다는 특징때문에, 한 속성이라도 Class Likelihood가 0이 되는 경우 결과 확률이 무조건 0이 된다는 문제점이 있다. 2의 예제에서도 볼 수 있듯이, Class Likelihood가 0인 경우가 쉽게 나타난다. 학습 과정에서 특정 속성 값을 가진 데이터가 하나도 없는 경우, 해당 속성 값에 대한 Class Likelihood가 0이 되어 다른 속성 값들을 무의미하게 만들어버린다.
이를 해결하기 위한 방법 중의 하나로, 일종의 가중치, 혹은 편향(Bias)을 확률에 더해주는 방법이 있다.
b의 값은 데이터의 분포를 보고 적절한 값을 선택하면 된다. b의 값이 클수록 Prior Probability를 더욱 신뢰하는 효과가 있다.

(3) 종속성
세 번째 문제는 NBC의 근본적인 문제라고 할 수 있다. 바로 종속성과 관련된 문제이다. NBC에서는 모든 특정 객체의 속성들이 모두 독립적이라고 보기 때문에, 종속성이 있는 속성이 주어질 경우 문제가 발생할 수 있다. 2의 예제에서만 봐도, 키와 몸무게는 종속성이 있다고 생각할 수 있다. 키와 몸무게는 비례하기 마련이다. 하지만, NBC에서는 키와 몸무게가 철저히 독립적이라고 가정한다. 따라서 종속성이 매우 높은 속성들을 가진 데이터가 주어지는 문제의 경우 바람직한 결과를 기대할 수 없다. 이러한 경우, NBC에서는 딱히 해결 방법이 없다. NBC 외에 다른 분류 방법을 고려해봐야 한다.

4. NBC의 활용 사례
NBC를 실제 어떤 Application에 적용할 수 있을까? 대표적인 예로 가장 유명한 스팸(Spam) 메일 분류기가 있다. C₁ = Spam, C₂ = Ham이라고 가정한 뒤, 이메일 x가 주어졌을 때 이를 Spam 혹은 Ham으로 분류하는 것이다. x는 Bag Of Words 벡터로 주어진다. 이메일에 등장할 수 있는 단어의 종류를 모두 구해서 Dictionary로 만들고, x가 Dictionary의 단어 중 n 번째에 위치한 단어를 가지고 있으면 1, 그렇지 않으면 0로 인코딩하여 x를 0과 1로 이루어진 벡터로 만드는 것이다. 예를 들어, 이메일에 등장할 수 있는 단어의 수가 4개(Dictionary의 크기 = 4)이고 이메일 x에서 두 번째, 세 번째 단어가 나타났다면, x = [0 1 1 0]으로 나타낸다. 이를 바탕으로 Prior Probability와 단어 별로 Class Likelihood들을 구하여 학습을 하면, 강력한 스팸 분류기가 탄생한다. 실제로, 여러 이메일 시스템에서 이렇게 NBC를 활용한 스팸 처리기를 활용해왔다고 한다.

5. 정리
NBC는 데이터의 속성들이 모두 독립적이라는 가정 하에, 각 속성의 Class Likelihood를 전부 곱해버리는 방법이다. 따라서 Multivariate 문제를 Univariate 문제로 축소하여 해결한다는 특징이 있다. 학습은 Maximum Likelihood Estimation(MLE)을 활용하여 진행하고, 분류는 Maximum a Posteriori Estimation(MAP)을 활용하여 진행한다.
이 글에서는 데이터가 이산 확률 분포를 따른다는 가정이었지만, 이후의 글에서는 데이터가 연속확률분포를 따를 경우에 이 특성을 활용해 NBC로 파라미터 학습(Parametric Learning)을 진행하는 방법에 대해 살펴보도록 하겠다.

6. References
Alpaydın, Ethem. Introduction to machine learning. Cambridge, MA: MIT Press, 2014. Print.

1. 개요
최대 사후 확률 추정(Maximum A Posteriori Estimation)은 MAP라고 알려져 있는 파라미터 학습법의 일종이다. 최대 가능도 추정(Maximum Likelihood Estimation, 이하 MLE)에서는 동전의 앞면과 뒷면이 나올 확률을 구할 때, 특정한 하나의 동전에 대한 확률에만 관심이 있었다. (참고: http://arkainoh.blogspot.kr/2017/10/parametric.learning.maximum.likelihood.estimation.html)
예를 들어, 관찰 데이터는 D = {h, h, t, h}라고 주어지고, θ1 = 3/4, θ2 = 1/4인 두 개의 동전이 있다고 가정하자. 이때, MLE는 두 개의 동전 중 D를 발생시킬 확률이 높은 것을 선택한다.
그런데, MAP에서는 이 동전을 선택하는 행위 자체도 고려한다. MLE에 따르면 θ1이 가장 적합한 동전이지만, 만약 실제로 동전을 던지는 사람이 동전 θ2를 너무 선호한 나머지 100회의 시행 중 θ2를 99번 던지는 습성이 있다면, "관찰된 데이터가 어떤 동전을 통해 나온 결과인가?"라는 질문에는 θ2를 답으로 내는 것이 바람직하다. 즉, Parameter를 구하는 과정에서 P(θ1) = 0.01, P(θ2) = 0.99라는 Prior Probability를 고려해주는 것이 바로 MAP이다.
베이즈 정리(Bayes Rule)에 의하면 Posterior Probability = Likelihood * Prior Probability / Evidence인데, Evidence의 경우 Posterior Probability가 최대가 되는 Parameter를 구할 때 아무런 영향이 없으므로, Likelihood * Prior Probability만 고려하도록 한다.
요약하자면, MLE는 Likelihood만 고려하여 최적의 Parameter θ를 구하지만, MAP는 Likelihood와 함께 Prior Probability를 고려하여 최적의 θ를 구하는 방법이다.

2. Maximum A Posteriori Estimation (MAP)
MAP의 개념에 대해 조금 더 자세히 알아보자. 연속확률분포를 따르는 데이터 x가 주어졌을 때, 그 평균을 MAP를 통해 구하고자 한다.
앞서 개요에서 언급했던 것처럼, MAP에서는 구하고자 하는 Parameter의 확률, 즉, Prior Probability도 고려해주어야 한다. 따라서, 구하고자 하는 평균도 확률변수로 설정하고, 역시 정규분포를 따른다고 가정한다. (참고: MLE에서는 평균을 구하기 위해 전체 키를 더한 다음 학생 수로 나눴던 것을 상기하자.)
이를 통해 P(μ|D)를 최대화하는 μ을 구하자.
이 식에서의 변수는 μ이기 때문에, μ와 관련된 항들을 제외하고 중요하지 않은 나머지 부분들은 임의의 상수 α로 묶어버린다.
괄호 안의 식을 전개한 뒤 μ에 대해 정리하고 μ와 관련없는 항들을 임의의 상수 α'로 묶어버리면 다음과 같은 결과가 나온다. 이를 [식1]이라고 하자.
이번엔 Posterior Probability인 P(μ|D)도 역시 정규분포 형태라고 가정하자.
즉, 데이터의 그룹에 따라 수많은 μ들이 나올 수 있는데, 그 μ들의 평균이 대략 μn으로 나타날 것이라는 예상이다.
이 식 역시 μ과 관련없는 항들을 임의의 상수 α''로 묶어버리면, 다음과 같은 식을 얻을 수 있다. 이를 [식2]라고 하자.
[식1]과 [식2]는 같아야 하기 때문에, 변수 μ이 포함된 항들의 계수가 같다고 놓고 풀면 다음과 같은 결과가 나온다.
이때 μML은 MLE를 통해 구한 평균을 의미한다.
결국 μn이 우리가 찾고자 하는 답이기 때문에 이를 μMAP라고 하고, 임의의 상수 λ를 다음과 같이 정의하자.
위에서 구한 μn를 λ를 사용하여 표현하면 다음과 같은 관계가 성립됨을 알 수 있다.
즉, MLE로 구한 평균과 Prior Probability의 평균의 적당한 Linear Interpolation이라고 할 수 있다. 이를 간단히 해석해보면 σ0이 작을수록 λ는 커지며, N이 엄청 크다면 MLE로 구한 평균 쪽이 전체를 Dominate해버린다. 즉, Prior Probability에 대한 선험적 지식이 확고할수록 Prior Probability를 믿겠다는 의미가 된다.

3. References
https://en.wikipedia.org/wiki/Maximum_a_posteriori_estimation
Alpaydın, Ethem. Introduction to machine learning. Cambridge, MA: MIT Press, 2014. Print.

1. 기계학습의 목표와 한계

P(C|x): Posterior Probability
P(x|C): Class Likelihood
P(C): Prior Probability
P(x): Evidence

1. 기본 개념
대부분의 데이터 분석 모델은 각각의 샘플 데이터의 발생 확률을 독립적이라고 보는 경우가 많다. 그러나 이는 인간의 언어나 주가 변동 등 연속된 데이터가 특정 패턴을 가진다는 사실을 반영하지 못한다. 예를 들어, 한 단어 안에서 알파벳 h는 x 다음에는 나타나지 않으며, t 혹은 s 다음에 나타날 확률이 높다. 즉, 단어 안에 나타나는 알파벳의 순서는 완전히 독립적이지 않다. 따라서 이와 같이 연속된 데이터가 서로 종속적이라는 관점이 필요하다. 이를 반영한 개념이 바로 마르코프 연쇄(Markov Chain)이다.
마르코프 연쇄는 이산적인 시간 흐름에 따른 시스템의 상태 변화를 확률적으로 나타낸 이산확률과정(또는 Discrete Markov Process)이다.
마르코프 연쇄는 FSM(Finite State Machine)처럼 특정 시점 t에 대한 State가 존재하며, 시간의 진행에 따라 특정 State에서 다른 State로 Transition을 한다. 각각의 State Transition의 확률은 시간의 영향을 받지 않는다. 예를 들어, State₁에서 State₂로 이동할 확률은 모든 시점 t에 대해 동일하다.
효과적인 설명을 위해 다음과 같은 Notation들을 정의한다.

S_i = i번째 State (1 <= i <= N)
q_t = 시점 t에서의 State (e.g. q₃ = S₆)
a_ij = S_i에서 S_j로 전이할 확률
pi_i = 첫 시점(t = 1)에서 S_i에 있을 확률, P(q₁ = S_i)

1차 마르코프 모델(First-order Markov model)에서는 특정 시점 t에서의 State는 바로 이전 시점 t-1에서의 State의 영향을 받는다고 가정한다. 이를 조건부 확률로 표현하면 다음과 같다.

P(q_t+1 = S_j | q_t = S_i, q_t-1 = S_k, ...) = P(q_t+1 = S_j | q_t = S_i)

이를 바탕으로 다음과 같은 관계가 성립한다.

a_ij = P(q_t+1 = S_j | q_t = S_i)

a_ij는 항상 0이거나 양수이며, N개의 모든 State로부터 S_i로 갈 확률을 더하면 1이 된다. 그리고, 첫 시점에서 모든 State에 있을 확률을 각각 더하면 합이 1이 된다.

2. Observable Markov Model
이 모델의 기본 전제는 매 시점마다 어떤 State에 있는지 관찰이 가능하다는 것이다. 즉, t가 주어지면 q_t를 알 수 있다. 따라서 시간 T 동안 어떤 순차적인 데이터가 관찰되었을 때, 이를 O(Observation Sequence)라고 하면 다음과 같이 표현할 수 있다.

O = {q₁, q₂, q₃, q₄, ..., q_T}

만약, 모든 a_ij 값들의 집합 {a_ij}와 pi_i 값들의 집합 {pi_i}가 주어진다면, 특정한 O가 발생할 확률을 쉽게 구할 수 있으며, 여러가지 O들을 트레이닝 데이터로 학습하여 a_ij와 pi_i 값들을 예측할 수 있다.
먼저, 특정 O가 발생할 확률은 다음과 같다.

P(O | {a_ij}, {pi_i}) = pi_q1 * a_q1q2 * a_q2q3 * ... * a_qT-1qT

예를 들어,

pi₁ = 0.4
a₁₁ = 0.1
a₁₃ = 0.2
a₃₂ = 0.5

이러한 정보가 주어졌다면, 특정 O(= {S₁, S₁, S₃, S₂})가 발생할 확률은 0.4 * 0.1 * 0.2 * 0.5가 된다.
반대로, K개의 O가 주어졌을 때, {a_ij}와 {pi_i}를 학습하는 것은 확률적인 추론을 통해 가능하다. 우선 pi_i는 K개의 O 중에서 q₁ = S_i인 O의 개수를 구하면 된다. 즉, q_i = (q₁ = S_i인 O의 개수) / K이다. 그리고 a_ij는 K개의 O 중에서 특정 시점 t에 대해 q_t = S_i인 모든 O들의 개수를 구하고, q_t = S_i와 동시에 q_t+1 = S_j를 만족하는 모든 O들의 개수를 구한 뒤에 나눗셈을 하면 된다. 즉, a_ij = (K개의 O 중 q_t = S_i와 q_t+1 = S_j를 만족하는 O의 수) / (K개의 O 중 q_t = S_i인 O의 수) 단, 모든 t에 대해 고려해줘야 한다.

3. 예시
Observable Markov Model은 항아리에서 공을 뽑는 것에 비유할 수 있다. 빨간색, 파란색, 초록색을 가진 세 개의 항아리가 있고, 한 항아리에는 같은 색의 공이 들어 있다고 가정해보자. 빨간색 공은 빨간색 항아리로부터만 뽑을 수 있으며, 파란색 공은 파란색 항아리로부터만 뽑을 수 있다. 뽑힌 공들의 색깔이 관찰 결과(O)이며, 각각의 항아리는 State를 의미한다. 즉, 어떤 색의 공을 뽑든지 해당 공이 어떤 항아리로부터 나왔는지 알 수 있기 때문에 Observable이라는 표현을 쓰는 것이다.
빨간 항아리를 S₁, 파란 항아리를 S₂, 초록 항아리를 S₃이라고 하고 각각 공을 5개, 2개, 3개 가지고 있다고 가정한다면, 첫 번째 차례에서 특정 색의 공을 뽑을 확률, 즉, pi_i 값들은 다음과 같다.

pi₁ = 0.5
pi₂ = 0.2
pi₃ = 0.3

또한, a₁₂는 빨간 항아리에서 공을 뽑고나서 다음 차례에는 파란 항아리에서 공을 뽑는 확률이라고 생각할 수 있다. 예를 들어, a₁₂ = 0.3, a₂₁ = 0.6이라고 하면 O = {빨간 공, 파란공, 빨간 공}, 즉, 첫 번째 차례에 빨간 공을 뽑고 나서 파란 공을 뽑고 다시 빨간 공을 뽑을 확률은 0.5 * 0.3 * 0.6이다.

4. Reference
Alpaydın, Ethem. Introduction to machine learning. Cambridge, MA: MIT Press, 2014. Print.