혼합분포군집(mixture distribution clustering)

 

 

데이터들이 항상 정규분포와 같은 단일분포만 따른다고 하면 얼마나 편할까 ? 하지만, 세상은 그렇게 호락호락하지 않게도 실제 데이터들의 형태를 보면 봉우리가 2개인 분포, 도넛형태의 분포 등.. 다양한 분포를 가지는 데이터들이 존재한다. 매우 복잡한 형태를 가진 데이터들의 분포는 혼합분포로 설명될 수 있다.

 

○ 혼합분포

 

"혼합분포"란 여러 분포를 확률적으로 선형 결합한 분포이다. 이는 각 데이터가 하나의 분포만을 따르는 것이 아니라 또 다른 분포(또는 모수가 다른 같은 분포)를 따르는 것을 의미한다. 다음 그림을 통해 직관적으로 이해할 수 있다. 

 

ex) 3개의 정규분포가 결합된 혼합분포

데이터의 분포가 다봉형의 형태(빨간 곡선)를 띠며, 이를 단일 분포로 적합하는 것은 바람직하지 않아 보인다. 이런 경우, 혼합 분포를 떠올릴 수 있으며 위의 그림에서는 3개의 분포(파란 곡선)가 결합된 것으로 이해할 수 있다. 흔히 정규분포 또는 다변량 정규분포를 가정하며, 실제로 매우 복잡한 형태의 자료에 대해서도 충분한 개수의 정규분포를 고려하면 모집단 분포를 잘 근사해 낼 수 있다(반드시는 아님).  

 

마찬가지로 왼쪽 그림의 경우 단일 정규분포를 적합한 것이며, 데이터의 형태를 잘 설명한다고 할 수 없다. 반면, 오른쪽 그림은 혼합 정규분포를 적합한 것으로 데이터의 형태를 더 잘 설명하는 것으로 보인다. 

 

 

일반적으로 K개 분포의 가중합으로 표현되는 혼합모형(mixed model or k-component mixture density)은 다음과 같이 정의할 수 있다. 

 

$p(x|\theta) = \sum_{i=1}^K \pi_k \, g_k(x|\theta_k)$

 

• $g_k(x|\theta_k)$  :  k번째 분포에서 데이터가 관측될 조건부 확률.(=  혼합모형을 이루는 단일 확률밀도 함수)
• $\theta_k$  :  k번째 분포의 모수벡터
• $k$  :  k번째 분포
• $\pi_k$  :  k번째 분포가 혼합모형에서 차지하는 중요도 또는 가중치.(= mixing coefficients)

 

예를 들어, 혼합모형이 두 정규분포의 결합으로 이루어져 있다면 다음과 같이 표현할 수 있다. 

 

$p(x|\mu, \Sigma) = \pi N(x|\mu_1,\Sigma_1) + (1-\pi) N(x|\mu_2,\Sigma_2)$

 

이를 혼합 정규분포라고 하며,  하나의 분포 $N(x|\mu_k,\Sigma_k)$는 component of the mixture 라고 한다. 가중치 $\pi_k$는 mixing coefficients 라고 하며 다음의 조건을 만족한다. 

 

$\sum_{k=1}^{K} \pi = 1$  ,  $0 \leq \pi_k \leq 1$.

 

---

○ 혼합분포 추정

 

각 데이터가 어떤 분포를 따르는지 알면 혼합분포를 구하기 쉽지만, 사실상 데이터가 주어진다고 해도 분포 가정을 하는 것일 뿐 정확한 분포를 알아내는 것은 불가능하다. 따라서, 데이터에 대해 단일 분포로 가정하고 분석할지 혼합분포로 가정하고 분석할지는 분석가의 역량이 달려있다. 이 글은 혼합분포에 대한 포스팅인 만큼 혼합분포로 국한짓고 추정하는 방법까지도 살펴볼 것이다. 먼저, 혼합분포를 추정하기 위해서는 "잠재변수(latent variable)"을 알아야한다. 

 

잠재변수는 각 자료가 어느 집단에 속하는지에 대한 정보를 가지는 역할을 한다. 따라서, 잠재변수를 포함하는 혼합분포를 이용하여 알고자 하는 혼합분포를 추정할 것이다. 앞으로 잠재변수를 $Z$라고 표현할 것이다. $Z$는 혼합분포 수에 따른 K차원의 이진 랜덤 변수(binary random variable)이며, 이는 각 데이터가 K번째 분포에서 나왔으면 1, 아니면 0으로 표현된다(1-of-K representation). 예를 들어, n번째 데이터가 3개 혼합분포 중 1번째 분포에서 나왔으면 $z_1=\left \{1, 0, 0 \right \}$으로 표현될 것이다. 

 

$z_k \in \left \{0, 1 \right \}$ , $\sum_k z_k =1$

 

잠재변수를 이용하여 혼합분포를 찾는 2가지 방법이 존재한다. 

 

 

1. 사전확률과 조건부확률 이용

 

① $z$ 의 주변 확률 분포(marginal distribution)는 $\pi_k$ (k번째 분포에 속할 사전확률)로 정의할 수 있다. 

 

$p(z_k = 1) = \pi_k$

 

이를 일반화 하면 $p(z) = \prod_{k=1}^{K} \pi_k^{z_k}$이다. 

 

② $z$ 의 특정값이 주어졌을 때 $x$ 의 조건부 확률 분포(codition distribution)는 다음과 같다. 편의를 위해 정규분포를 가정한다.

 

$p(x|z_k=1) = N(x|\mu_k, \Sigma_k)$

 

이를 일반화 하면 $p(x|z) = \prod_{k=1}^{K} N(x|\mu_k, \Sigma_k)^{z_k}$이다. 

 

$x$ 와 $z$ 의 결합 확률 분포(joint distribution)는 $p(z,x) = p(z)p(x|z)$을 통해 구할 수 있으며, 

 

$p(x, z) = p(z)p(x|z) = \prod_{k=1}^K \pi_k^{z_k} N(x|\mu_k, \Sigma_k)^{z_k}$

 

$x$ 의 주변 확률 분포(marginal distribution)는 다음과 같다. 

$p(x) = \sum_z p(z)p(x|z) = \sum_{k=1}^K \pi_k N(x|\mu_k, \Sigma_k)$

 

우리가 처음에 소개했던 혼합분포의 형태와 같음을 알 수 있다. 혼합분포 $p(x)$를 구하기 위해 $p(x|z)$를 이용하는 방법으로 문제를 귀결시켰다. 지금까지 증명한 것은 명시적으로 잠재 변수 $z$ 를 도입하여 $x$ 에 대한 주변 확률 분포(즉, 혼합분포)를 구하는 과정이다. 

 

 

2. 사후확률 이용

 

주변 확률 분포 $p(x)$ 대신 $z$ 의 조건부 확률 분포(사후확률)를 이용하여 작업을 진행할 수도 있다. $x$ 가 주어졌을 때 $z$ 의 조건부 확률은 다음과 같다. 

 

$r(z_k) \equiv p(z_k=1| x) = \frac{p(z_k=1) p(x|z_k=1)}{\sum_{j=1}^{K} p(z_k=1)p(x|z_k=1)}$

$= \frac{\pi_k N(x|\mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j N(x|\mu_k, \Sigma_k)}$

 

$\pi_k$는 $z_k$=1일 때의 사전확률이며, $r(z_k)$는 x가 주어졌을 때 k군집일 확률인 사후확률을 나타낸다(It is also the responsibility that component k takes for explaining the observation x.) 역시나 우리는 데이터가 어떤 군집에 속하는지 알 수 없기 때문에 유사한 역할을 할 잠재변수(z)를 도입한 것이다. 

 

 

지금까지 소개했던 확률들의 역할을 그림을 통해 볼 수 있다. 

 

위의 500개 데이터는 3개의 혼합 정규 분포로부터 생성되었다. 그림(a)는 결합 확률 분포 $p(z)p(x|z)$ 로부터 각각의 $z_k$ 에 대해 생성된 샘플이며, 색상별로 구분되었다. (b)는 주변 확률 분포 $p(x)$의 샘플이며 z값이 무시된 상태이다. (c)는 $r(z_k)$ 에 따라 색상을 다르게 표현한 것이다. (a)와 (c)의 그림이 좀 다른 것을 볼 수 있는데, 실제 결과를 경성 혼합(soft mixture)방식으로 표현했기 때문이다. 즉, $r(z_k)$ 의 값에 따라 각각의 색을 적당히 혼합하였다. 예를 들어, $r(z_1)=1$ 인 경우 완전히 붉은색으로 표현되지만, $r(z_2)=0.5, r(z_3)=0.5$ 와 같은 결과를 얻은 경우, 녹색과 파란색을 반반씩 섞게 된다. 참고로 (a)와 같은 결과를 complete 하다고 표현하고 (b)와 같은 결과를 incomplete 하다고 표현한다. 

 

○ 혼합분포군집

 

혼합분포의 개념을 익혔으니 다음으로는 혼합분포군집에 대해서 알아보도록 하자. "혼합분포군집"은 모형-기반(model-based)의 군집 방법으로 말그대로 모형(분포)를 기반으로 데이터를 군집하는 것이다. 즉, 각 데이터가 혼합분포 중 어느모형으로부터 나왔을 확률이 높은지에 따라 군집의 분류가 이루어진다. 따라서, k개의 각 모형은 곧 군집을 의미한다. 

 

군집을 수행하기 위해서는 혼합모형에서의 모수와 가중치를 추정해야한다. 일반적으로 단일분포의 경우 로그-가능도함수(Log-likelihood function)를 2번 미분하는 과정을 통해 최대가능도추정량(MLE)을 찾는다. 하지만, 혼합모형의 경우 가능도함수의 표현식이 복잡하기 때문에 닫힌 형태의 MLE 해를 구할 수 없게 된다(이따가 증명해 보일 것).

 

$ln(p(X|\pi, \mu, \Sigma)) = \sum_{n=1}^{N} ln \left \{ \sum_{k=1}^{K} \pi_k N(x_n | \mu_k, \Sigma_k) \right \}$

 

따라서, 가능도 함수를 최대화시켜주는 방법으로 반복 수치 최적 알고리즘(iterative numerical optimization techniques)을 사용한다. 이를 우리는 EM알고리즘이라고 부를 것이다. 

 

 

○ EM알고리즘(Expectation Maximization)

 

일반적으로 MLE를 구하기 위해 로그-가능도 함수를 2번 미분하는 과정을 거치게 된다. 하지만, 혼합분포에서는 이 방법이 닫힌 형태의 해를 가져다주지 못하기 때문에 EM알고리즘을 사용할 것이라고 위에서 언급하였다. 이제부터는 왜 닫힌 형태의 해를 얻을 수 없는지와 그에 대응한 EM알고리즘에 대해 알아볼 것이다. 

 

데이터를 가지고 살을 붙여가며 전개해보자. 독립인 혼합분포로부터 데이터가 $x_1, \cdots , x_N$ 주어졌다고 가정하자. 데이터의 크기는 $N \times D$ 이며(N : 샘플의 개수, D : 한 샘플의 차원), 행렬 X 로 표현할 수 있다. 이런 경우, 한 줄에 해당하는 데이터는 $x_n^D$가 된다. 이 샘플에 대응하는 잠재변수($Z$)는 $N \times K$ 크기의 행렬이 될 것이며, 한개의 데이터는 $z_n^K$ 으로 표현될 것이다.

 

데이터에 대한 로그-가능도 함수를 구하면 다음과 같다. 

 

$ln(p(X|\pi, \mu, \Sigma)) = \sum_{n=1}^{N} ln \left \{ \sum_{k=1}^{K} \pi_k N(x_n | \mu_k, \Sigma_k) \right \}$

 

 

1. 미분을 이용한 MLE 

 

로그 가능도 함수를 모수($\mu_k , \Sigma_k, \pi$)에 대해 미분하고 이 값이 0이 되는 평균($\mu_k$)을 구하고자 한다. 

첫번째 식의 양변에 $\Sigma_k$를 곱하고 전개하면 평균값을 구할 수 있다. (이 때는 $\Sigma_k$ 이 nonsingular matrix라고 가정.)

$N_k$는 군집 k 에 대한 effective number 라고 해석할 수 있다. 수식을 자세히 보면, k번째 정규 분포의 평균값인 $\mu_k$는 전체 데이터에 대한 가중($r(x_k)$) 평균임을 알 수 있다. 그럼에도 불구하고 하나의 군집에 국한된 평균값으로 고려할 수 있는 이유는 사후분포 $r(x_k)$ 에 의해 데이터가 k번째 정규분포에만 영향을 미치는 정도를 계산할 수 있기 때문이다. 

 

마찬가지로 $\Sigma_k$ 의 추정값은 다음과 같다. 

이는 단일 정규분포 형태와 비슷하며 추가로 가중치로 사후확률이 사용되었고, 군집의 effective number로 나눠준 형태를 가진다. 

 

마지막으로, 혼합 계수인 $\pi_k$를 추정하면 되는데, 혼합 계수는 추가적인 제약이 존재하기 때문에 로그 가능도 함수에 이러한 제약을 추가하여 라그랑지안 승수 방식으로 처리한다. 

양변에 $\pi_k$를 곱하면 $r(z_{nk})$가 나온다. 이를 전개하면 다음과 같다. 

이렇게 구한 평균과 분산, 혼합 계수는 닫힌-형태의 해를 가지지 못하는데 이는 모두 사후확률 $r(z_{nk})$에 영향을 받기 때문이다. 따라서, 이를 풀기 위해 EM알고리즘을 사용한다. 

 

 

2. EM 알고리즘

 

EM알고리즘은 가능도함수를 최대로 만들어주는 모수를 찾기 위한 반복적인 알고리즘이다. 간단하게 설명하면, 잠재변수를 도입하여 각 자료가 어느 군집에 속할지 사후확률을 추정하고(E-step), 사후확률을 통해 모수를 재추정하여(M-step) 로그-가능도함수가 수렴할 때 까지 반복한다. 갱신된 모수 추정치에 대해 위 과정을 반복한다면 수렴하는 값을 얻게 되고, 이는 최대가능도추정치(MLE)로 사용될 수 있다. 

EM알고리즘의 과정은 다음과 같다. 

 

• Initialization
  • 평균, 분산, 혼합계수에 대해 임의의 초기값을 정해준다.
  • 초기값에 대한 로그가능도 함수를 구한다.
  • 그림 (a)에 해당

• E-step
  • 현재 파라미터의 값을 사용하여 사후확률 $r(z_{nk})$을 구한다.
  • 그림 (b)에 해당

•  M-step
  • E-step 에서 계산한 사후확률을 이용하여 평균, 분산, 혼합 계수의 값을 재추정한다. 
  • 그림 (c)에 해당

 

• iterative
  • 파라미터 또는 로그 가능도함수가 수렴할 때까지 E-step과 M-step을 반복한다. 
  • 그림 (d), (e), (f)에 해당

 

EM알고리즘 simulation

 

 

 

 

 

<참고문헌>

cedar.buffalo.edu/~srihari/CSE574/Chap9/Ch9.2-MixturesofGaussians.pdf

www.mghassany.com/MLcourse/gaussian-mixture-models-em.html

8 Gaussian Mixture Models & EM | Machine Learning

norman3.github.io/prml/docs/chapter09/2.html

2. Mixture of Gaussians

arxiv.org/pdf/1901.06708.pdf