패턴 인식 (3) 확률 분포 추정
패턴인식, 오일석 지음/교보문고 |
3. 확률 분포 추정
사후 확률 $ P(w_i | x) $를 이용하여 분류하기 위하여 2장에서 우도와 사전 확률의 곱으로 바꾸어 계산하였고 이들 확률은 미리 알고 있다고 가정하였다. 여기서는 이들 확률을 실제와 가깝게 어떻게 추정하는지 알아보자.
일반적인 분류기 학습 과정은 주어진 훈련 집합 X로부터 분류기가 지니고 있는 매개변수 집합 $ \Theta $를 추정하는 것으로 생각할 수 있다. 이러한 과정을 학습(learning) 또는 훈련(training)이라고 한다. 이 틀을 베이시언 분류에 적용하면 우리는 사전 확률과 우도를 추정해야 한다. 그 방법으로는 최대 우도법, 비모수 추정법, EM 알고리즘 등이 있다.
사전 확률은 비교접 쉽게 추정할 수 있다. 샘플의 수를 N이라 하고 $ w_i $에 속하는 샘플 수를 $ N_i $이라 하면 $ P(w_i) = N_i / N $으로 추정하면 된다. N이 충분히 크다면 실제 값에 근접하게 될 것이다.
우도의 경우는 쉬운 문제가 아니다. 우도와 비슷한 분포를 알고 있거나 그러한 분포를 가정할 수 있다면 문제는 그 분포의 매개 변수를 추정하는 문제로 줄어들 수 있다. 이러한 경우 최대 우도법을 사용하는 것이 적절하다.
하지만 임의의 모양을 가진 확률 분포를 가진 경우에는 이를 표현하느 수학 함수가 존재하지 않기 때문에 이것을 어떻게 표현해야 할지도 고려하여야 한다. 적어도 다른 부류에 속한 샘플은 서로 영향을 미치지 않는다고 가정할 수 있다. 따라서 X중 $ w_i $에 속하는 샘플 집합 $ X_i $를 가지고 $ p(x | w_i) $를 추정하는 문제로 생각할 수 있다.
3.1 히스토그램 추정
특지의 동적 범위가 [0, 1]이라고 하고 이 범위를 몇개의 구간으로 나눈 뒤 그 안의 샘플 수를 세어 만든 것이다. 이것을 히스토그램(histogram)이라 한다. 히스토그램의 각 빈(bin)의 값을 N으로 나누면 그것이 곧 확률 분포가 된다.
현실적으로 이 방법은 공간의 차원이 낮고 X의 크기가 충분히 커야한다.
3.2 최대 우도(maximum likelihood)
이 방법은 정규 분포와 같이 매개 변수로 표현되는 경우에만 적용이 가능하다. 매개 변수 집합을 $ \Theta $로 표시하자. 주어진 X를 발생시켰을 가능성이 가장 높은 $ \Theta $ 를 찾는다면, 즉 가장 큰 우도를 갖는 $ \Theta $를 찾는다면 그것이 찾고자 하는 분포의 매개 변수가 될 것이다. 이를 수식으로 나타내면 다음과 같다.
$$\hat{\Theta} = \arg \max_{\Theta} p(X | \Theta)$$
모든 샘플은 독립적으로 추출되었다고 가정할 수 있다면, 우도는 다음과 같이 쓸 수 있다. 훈련집합 X 는 $ X = \{ x_1, x_2, \cdots, x_N \} $ 이다.
$$p(X | \Theta) = \prod_{i=1}^{N} p(x_i | \Theta)$$
풀기가 쉽도록 여기에 $ \ln $을 사용하여 로그 우도(log likelihood) 형태로 표현한다. 이제 식은 다음과 같이 변환된다.
$$p(X | \Theta) = \sum_{i=1}^{N} \ln( p(x_i | \Theta))$$
이 문제는 이제 최적화 문제(optimization problem)로 어떠한 방법을 사용하여 풀어도 상관없으나, 단순하게는 미분을 이용한 풀이를 사용할 수 있다.
$$\frac{\partial L (\Theta)}{\partial \Theta} = 0 \\ L(\Theta) = \sum_{i=1}^{N} \ln( p(x_i | \Theta))$$
특별히 만약 추정하고자 하는 확률 분포가 정규 분포일 경우, 정규 분포의 평균은 샘플의 평균과 같게 계산된다.
지금까지의 ML은 매개 변수의 확률 분포 $ p(\Theta) $가 균일하다는 가정에서 수행되었다. 만약 그렇지 않은 경우에는 최적화 문제를 고쳐 써야 한다.
$$\hat{\Theta} = \arg \max_{\Theta} p(\Theta) \sum_{i=1}^N \ln p(x_i | \Theta)$$
이러한 수식을 풀어 매개변수를 찾는 방법을 MAP(maximum a posterior) 방법이라고 한다.
3.3 비모수적 방법
앞의 ML과 MAP는 모수적(parametric) 방법이다. 모수적 방법은 매개 변수로 표현할 수 있는 특정한 종류의 확률 분포에서만 적용이 가능하다는 한계가 있다. 현실에서는 특정한 확률 분포를 따르지 않는 경우가 많으므로 이러한 분포의 추정을 위한 비모수적(nonparametric) 방법이 필요하다.
3.3.1 파젠 창
파젠 창(Parzen windows) 방법은 임의 확률 분포에 적용이 가능하다. 히스토그램 추정 방법과 유사한 방법으로 임의의 점 x을 중심으로 크기 h인 창을 씌우고 그 창 안에 있는 샘플의 수를 세어 k라고 하자. 이 때의 확률은 다음과 같이 추정한다.
$$p(x) = \frac{1}{h^d} \frac{k_x}{N}$$
N은 전체 샘플의 수, $ k_x $는 창 내에 들어있는 샘플의 수, $ h^d $는 d차원 창의 부피를 뜻한다.
파젠 창의 단점은 확률 분포가 계단 모양의 불연속적인 확률 밀도 함수가 만들어진다는 것이다. 이를 개선하기 위해 중점에 가까운 샘플에 더 많은 가중치를 주도록 하도록 하자. 수식으로 나타낼 때에는 커널 함수(kernel function)를 사용한다.
$$p(x) = \frac{1}{h^d} \frac{1}{N} \sum_{i=1}^{N} \kappa(\frac{x - x_i}{h})$$
이 때, $ \kappa $는 커널 함수이며, $ \kappa(x) \geq 0 $이고, $ \int_x \kappa(x) dx = 1 $을 만족하여야 한다. 가장 대표적인 함수는 정규 분포 함수이다. h는 실험적으로 찾아야 한다.
파젠 창 방법은 차원의 저주에서 자유롭지 못하다.
3.3.2 k-최근접 이웃 추정
파젠 창이 고정된 창의 크기를 이용하였지만 반대로 생각하여보자. x를 중심으로 창의 크기를 늘려가며 k개의 샘플이 창에 들어올 때까지 창의 크기를 확장하여보자. 이 때의 창의 크기 h를 이용하여 확률 분포를 추정해볼 수 있다.
$$p(x) = \frac{1}{h_x^d} \frac{k}{N}$$
이러한 방법을 k-최근접 이웃 추정(k-nearest neighbors estimation)이라고 한다. 이 방법은 훈련 집합의 크기가 크고 차원이 높아짐에 따라 계산량이 많아진다. 속도를 빠르게 하기 위해 훈련 집합을 특정 공간에 미리 구간으로 나누어두는 보르노이 도형(Vornoi diagram) 방법을 활용할 수 있다.
3.3.3 k-최근접 이웃 분류기
k-최근접 이웃 분류기는 이웃 추정 방법과 매우 흡사하다. 알지 못하는 샘플 x가 들어왔을 때, x를 중심으로 창을 씌우고 훈련 샘플이 k개가 들어올 때 까지 창을 늘린다. 창 안에 들어온 샘플 중에서 $ w_i $에 속하는 것의 개수를 $ k_i $라고 하자. 다음을 계산할 수 있다.
$$p(x | w_i) = \frac{k_i}{h_x^d N_i}$$
$$p(w_i) = \frac{N_i}{N}$$
$$p(x) = \frac{k}{h_x^d N}$$
베이스 공식에 대입하면, 다음을 얻는다.
$$p(w_i | x) \frac{P(w_i) p(x|w_i)}{p(x)} = \frac{k_i}{k}$$
결국 창 내에서 가장 많은 $k_i $를 갖는 부류로 분류하면 된다. 이러한 방법을 사용하려면 적절한 거리 척도가 있어야 한다.
3.4 혼합 모델
혼합 모델(mixture model)은 하나의 확률 분포가 아니라 두 개 이상의 서로 다른 확률 분포의 홉합으로 모델링 한다.
3.4.1 가우시안 혼합
가우시안은 하나의 모드를 가지기 때문에 두개 이상의 모드를 가지는 확률 분포를 표현하기에는 곤란하다. 따라서 여러개의 가우시안 분포를 사용하여 모델링하는 방법을 생각할 수 있다. 이러한 아이디어를 가우시안 혼합이라 한다.
구해야 하는 매개변수들은 다음과 같다.
- 가우시안의 개수 K
- k번째 가우시안의 매개 변수 $ (u_k, \Sigma_k) $
- k번째 가우시안의 가중치 $ \pi_k, k=1, \dots, K $
가우시안 혼합의 수식을 살펴보면 다음과 같다.
$$p(x) = \sum_{k=1}^{K} \pi_k N(x | u_k, \Sigma_k)$$
각각의 가우시안을 요소 분포(component distribution)이라 하고, $ \pi_k $는 가중치로서 혼합 계수(mixing coefficient)이라고 한다. 혼합계수도 일종의 확률 값이므로 $ 0 \leq \pi_k \leq 1, \sum_{k=1}^{K} \pi_k = 1 $의 조건을 만족해야한다.
주어진 샘플들 $ X = \{ x_1, \dots, x_N \} $로부터 매개변수를 구하는 방법을 최대 우도 문제로 발전시켜 보자. 로그 우도 형태로 식을 표현해보자.
$$\ln p(X | \Theta) = \sum_{i=1}^{N} \ln(\sum_{k=1}^K \pi_k N(x_i, | u_k, \Sigma_k))$$
$$\hat{\Theta} = \arg \max_{\Theta} \ln p(X | \Theta)$$
3.4.2 EM 알고리즘
가우시안을 하나만 가졌을 때는 미분을 이용하여 쉽게 추정이 가능하였으나 이제는 여러 가우시안의 매개 변수 뿐 아니라 혼합 계수 또한 추정하여야 하므로 미분을 이용하기가 어렵다.
EM 알고리즘의 기본 골격은 다음의 계산을 반복하는 것이다.
- E(Expectation) 단계 : $ \Theta $를 이용하여, 샘플 별로 K개의 가우시안에 속할 확률을 추정한다.
- M(Maximization) 단계 : E 단계에서 구한 소속 확률을 이용하여 $ \Theta $를 추정한다.
EM 알고리즘을 구현하기 위해서는 샘플 $x_i$가 어느 가우시안에 속하는지를 나타내는 벡터 $ z = (z_1, \dots, z_K)^T $를 사용하여야 한다. $z_i$는 샘플이 i번째 가우시안일 때에는 1, 나머지는 0의 값을 갖는다. 이제 샘플 $x_i$가 j번째 가우시안에서 발생했다고 가정하면, 그때의 $ x_i $의 조건부 확률, 또는 우도를 다음과 같이 쓸 수 있다.
$$p(x_i | z_j = 1) = N(x_i | u_j, \Sigma_j )$$
z는 실제로 알고리즘의 입력과 출력이 되는 것은 아니지만, 내부적으로 숨어서 보조적인 역할을 하는데 이러한 변수를 은닉 변수(latent variable)이라고 부른다.
또 다른 확률 하나는, 샘플 $x_i$가 관찰되었을 때 그것이 j 번째 가우시안에서 발생했을 조건부 확률 $P(z_j = 1 | x_i )$이다.
$$P(z_j=1 | x_i) = \frac{\pi_j N(x_i | u_j, \Sigma_j)}{\sum_{k=1}^K \pi_j N(x_i | u_j, \Sigma_j)}$$
이제 EM 알고리즘에 맞추어 각 파라미터를 계산하면 된다. 각 가우시안 요소의 평균, 분산은 각 확률의 가중치 평균을 이용하여 구할 수 있다. 혼합 계수 또한 라그랑제 승수(Lagrange multiplier)를 이용하여 구할 수 있다.
EM알고리즘의 특징을 알아보면 다음과 같다.
- 군집화(clustering)을 위한 k-평균(k-mean) 알고리즘은 EM알고리즈과 비슷하게 동작한다.
- EM 알고리즘은 속도가 느리므로 k-평균 알고리즘으로 미리 초기화를 하는 방법이 쓰이기도 한다.
- 동작이 멈추는 시점을 위하여 수렴 여부를 어떻게 판단할지도 한가지 문제이다.
- EM 알고리즘이 최적 해로 수렴한다는 것은 증명되어있으나 전역 최적 해(global optimal solution)가 아닌 지역 최적 해(local optimal solution)로 수렴할 수도 있다.
- EM은 불완전한 데이터가 주어진 경우릉 위한 최대 우도 추정법의 일종이다.