Chapter 8. K-Means Clustering and Gausssian Mixture Model

Clustering task and K-Means algorithm
- unsuperveised learning
- K-Means iterative process
- limitation of K-Means algorithm
Gaussian mixture model
- multinomial distribution and multivariate Gaussian distribution
- why mixture model
- parameter updates are derived from the Gaussian mixture model
EM algorithm
- fundamentals of the EM algorithm
- how to derive the EM updates of a model

8-1. K-Means algorithm

1~6주차에서는 supervised learning에 대해 배웠다.

이제는 k-means라는 unsupervised learning을 배워보고자 한다. unsupervised learning이란 label이 존재하지 않은 데이터셋을 활용하여 task를 수행하는 것이다. true value를 모르는 상황에서 패턴을 찾아야 한다.

만약, 우리가 이 데이터셋에 대해 색상 데이터를 가지고 있다면, supervised task가 될 것이다. 그러나 오른쪽과 같이 어떤 군집이 만들어지는지에 대해 모르고, 군집을 찾아야 한다면 이는 unsupervised learning이 된다.

k-means algorithm이란, 잠재적으로 생각하기에 내부적으로 k개의 동력이 있어서 n개의 데이터 포인트들을 clustering하는 기법이다. 위의 데이터들에 대해 k=3개의 동력원이 존재하여 n개의 데이터들이 3개의 동력원들에 의해 군집화된다.

여기서 중요한 것은 K-Means와 K-Nearest Neightbor algorithm은 동작방식이 비슷하나, 다른 기법이다. K-Means는 군집을 찾기 위한 unsupervised task에 사용되는 기법이고, KNN은 supervised task에서 사용되는 기법이다. KNN는 한 데이터의 주변에 가장 가까운 점 k개를 찾아 그에 대해 분류하고, 한 데이터를 주변 점들이 많이 분포되어 있는 값으로 지정해주는 것이다. 그러나 K-Means는 실제 컴퓨터가 보는 정보는 분류되지 않은 검은색 점들이고, 무엇보다 중심점들조차 주어지지 않는다. 이러한 상황에서 중심점들을 찾고, 그에 관련된 데이터들을 분류해야 한다.

따라서 K-Means는 크게 두 단계로 구성되어 있다. 첫번째로는 중심점을 찾는 것이고, 그 후에 중심점들과의 거리를 통해 데이터들을 분류한다.

clustering에 대한 식은 다음과 같다.

$ r_{nk} $ : a assignment variable of data point to cluster
$ \mu_k $ : location of centroids

$ r_{nk} $ 는 cluster에 대한 파라미터로서, 각 데이터 포인트는 1개의 centroid(중심점)에 대해서만 할당된다. 그러므로, 할당된 centroid에 대해서는 1로, 나머지 centroid에 대한 것은 0으로 할당하여 연산한다. 그리고, $ \mu_k $ 는 중심점의 위치이다.

최종적으로 J 를 최소화하는 것이 최적화의 목적이다. 그러나 이 때는 파라미터가 2개이므로, 이러한 경우는 반복적인 최적화를 통해 먼저 $ r_{nk} $를 최적화하고, 최적화된 $ r_{nk} $ 를 통해 $ \mu_k $를 최적화하고, 다시 최적화된 $ \mu_k $를 통해 $ r_{nk} $를 최적화하는 방식을 통해 J를 최소화한다.

Expectation
- 파라미터($ r_{nk} $)에 의해 구해지는 확률을 통해 centroid를 중심으로 한 데이터 포인트들을 할당해준다.
Maximization
- likelihood에 대한 파라미터($ \mu_k $)를 최대화시킴으로써 centroid 위치를 업데이트한다.

$ \mu_k $ 에 대해 optimization하는 과정은 다음과 같다. 최적화하는 방법은 동일하게 미분하여 =0인 값을 찾는 것이다.

결론적으로 구해보면, $ \mu_k $는 할당된 데이터 포인트들의 평균값이 된다.

k-means algorithm의 과정은 다음과 같다.

특정 반복 횟수만큼 아래 과정을 반복한다.

데이터들 중 random 하게 n개를 골라 centroid에 대한 파라미터인 $ \mu_k $ 를 지정한다.
$ r_nk $를 가까운 centroid( $ \mu_k $)에 대해 assign한다. ( 0 또는 1 )
assign된 데이터들의 평균값을 구해 $ \mu_k $ 를 업데이트한다.
다시 $ r_nk $를 업데이트한다.

이러한 반복 과정을 통해, 점차 최적의 centroid를 찾을 수 있다.

이러한 간단한 k-means algorithm에는 한계가 존재한다.

centroid의 개수가 명확하지 않다.
centroid의 초기 위치가 잘못 지정되면 잘못된 optimization이 수행될 수도 있다.
limitation of distance metrics
- euclidean distance만으로는 데이터의 특정을 정확하게 파악하기 힘들다.
hard clustering
- r_nk가 0 또는 1이므로 discrete하다는 단점이 있다.

8-2. Gaussian Mixture Model

Multinomial Distribution

gaussian mixture model을 배우기에 앞서, Multinomial distribution에 대해 다시 한 번 짚고 넘어가자.

먼저 binomial distribution이란, 0 또는 1에 대해서만 나타내어지는 distribution이다. binomial distribution에 있어서 X=(0,0,1,0,0,0) 에 대해 3개를 선택하는 것과 같이, 확률에 대한 식은 다음과 같다.

\[P(X|\mu) = \prod_{k=1}^K \mu_k^{x_k}, \sum_k x_k = 1\]

이 때의 제약조건(Subject)는

$ \mu_k \geq 0 $
$ \sum_k \mu_k = 1 $

이 0 또는 1의 binary한 값을, 0,1,2,3,… 에 대한 값으로 늘린 것이 multinomial distribution 이다.

N개의 선택지($x_1$,…,$x_n$)를 가진 데이터셋 D가 있다고 할 때의 확률은 다음과 같다.

\[P(X|\mu) = \prod_{n=1}^N \prod_{k=1}^K \mu_k^{x_{nk}} = \prod_{k=1}^K \mu_k^{\sum_{n=1}^N x_{nk}} = \prod_{k=1}^K \mu_k^{m_k}\]

이 때, $ m_k = \sum_{n=1}^N x_{nk} $ 이다.

MLE, 즉 확률이 최대가 되는 μ를 구하기 위한 식은 다음과 같다.

Maximize $ P(X|\mu) = \prod_{k=1}^K \mu_k^{m_k} $
제약조건 $ \mu_k >= 0, \sum_k \mu_k = 1 $

MLE task에서 제약조건이 존재할 때에는 lagrange function을 활용하여 MLE를 수행할 수 있다. lagrange function, L은 다음과 같다.

$ L(μ,m,𝜆) = \sum_{k=1}^K m_k :ln\mu_k + \lambda(\sum_{k=1}^K \mu_k - 1) $

lagrange function을 μ_k 에 대해 미분하면

이 때, 제약조건인 $ \sum_k \mu_k = 1 $를 활용하면

이 때, $ \sum_k \sum_{n=1}^N x_{nk} = N $ 인 이유는 모든 선택지에 대한 summation인 k와 개별 선택지마다 모든 데이터 포인트가 선택되는지에 대한 summation인 N에 대해 x_nk를 summation하는 것이므로, N이 된다. 이 때 x는 각 instance k에 대해 n개의 선택지가 선택될 확률이다.

결론적으로 MLE에 대한 μ_k는 m_k/N이 된다. 이는 특정 선택지가 선택된 개수 / 관측한 선택지 전체를 의미한다.

Multivariate Gaussian Distribution

Gaussian Mixture model을 위해 또 다른 재료가 필요하다. 그것이 Multivariate Gaussian Distribution이다.

single dimension에서의 Gaussian Distribution 식은 다음과 같다.

이를 multi dimension으로 바꿀 때는 variance가 covariance matrix로 변환되어 만들어진다. μ값 또한, 벡터의 형태가 된다.

이 multivariate gaussian distribution 식에 대한 MLE를 찾아보자.

먼저 log를 씌워서 식을 단순화시킨다.

그리고 이 때, 사용되는 기법이 trace trick 이다. trace trick은 선형 대수에서 등장하는 기법으로

Trace trick은 위와 같이, Tr 이라는 기호를 통해 나타낸다.

이렇게 간단해진 식을 미분한다. 변수는 μ와 $\sum$ 이므로 이 둘에 대해 미분한다. trace_trick에 대해 미분하면 간단하게 값을 구할 수 있다.

covariance matrix에 대한 예시가 있다.

covariance_matrix를 다양하게 변화시켜가면서 샘플링한 결과이다. 행렬에서 1행 1열과 2행 2열의 위치의 값은 variation이고, 행렬에서 2행 1열과 1행 2열 위치의 값은 correlation 즉 연관성에 대한 상수이다. 만약 분산이 둘다 1인 상황에서 correlation도 둘다 1이라면, 기울기가 양수인 직선의 형태로 나오게 될 것이다. x방향으로도 분산이 1, y방향으로도 분산이 1이고, 서로 상관관계가 크게 작용하고 있다는 의미이기 때문이다.

모든 값을 0으로 두면, 분산이 0이므로 점으로 모이게 될 것이고, 분산은 둘다 존재하나 연관성이 없다면 원의 형태로 둥글게 생긴다.

correlation이 음수인 경우는 반대 방향으로 작용될 것이다.

Mixture Model

이렇게 구한, Multinomial distribution에 대한 MLE estimation 식과 Multivariate gaussian distribution에 대한 MLE estimation을 융합한 것이 Mixture model이다.

mixture model을 히스토그램 측면에서 바라본다면, 여러 개의 데이터가 하나로 모여 있는 것으로 보인다. 그래서 이를 1개의 normal distribution으로 만들면 다소 부정확한 모델이 된다.

따라서, 이러한 모델의 경우 여러 개의 normal distribution으로 만들어서 나타내고자 한다. 이를 Mixture distribution이라 한다.

mixture distribution에 대한 식은 다음과 같다.

\[P(x) = \sum_{k=1}^K \pi_k N(x|\mu_k, \sigma_k)\]

$ \pi_k $ : Mixing coefficients
- multinomial distribution에 대한 값으로, K개의 옵션이 존재하고 그 중 하나가 선택될 확률을 나타낸다. 이 때의 K는 normal distribution의 개수이다.
- weight의 역할을 수행
- $ \sum_{k=1}^K \pi_k = 1 $
- 0 <= π_k <= 1
- k-means에서의 weight 변수는 0 또는 1의 값을 가지지만, 이 때는 확률적인(stochastic) 값을 가진다.
$ N(x|μ_k, σ_k) $ : Mixture component
- multivariate gaussian distribution에 대한 값으로, 개별 normal distribution를 나타낸다.

z라는 새로운 variable이 있다 생각한다면, x에 대한 확률 P(x)는 다음과 같다.

\[P(x) = \sum_{k=1}^K P(z_k)P(x|z)\]

k개 중 z가 선택될 확률과, z가 주어졌을 때, 즉 어떤 normal distribution을 선택했는지에 대한 값이 주어진 상태에서의 x의 확률, 즉 normal distribution을 나타낸다.

Gaussian Mixture Model

이제 데이터 포인트들이 multiple multivariate Gaussian Distribution의 mixture distribution에 대해 구성된다고 생각해보자.

그러면, P(x)는

$ P(x) = \sum_{k=1}^K \pi_k N(x|\mu_k, \sum_k) $

로 나타낼 수 있다. 이때의 $ \pi_k $는 $ P(z_k = 1) = \pi_k $ 이므로 P(Z)는 k개 안에서 선택지($ z_k $)를 선택하는 것이므로 확률 P(x)를 다음과 같이 P(Z)에 대해 나타낼 수 있다.

$ P(Z) = \prod_{k=1}^K \pi_k^{z_k} $

또한, mixture component인 $ N(x|\mu_k, \sum_k) $ 에 대해 $ P(X|z_k = 1) = N(x|\mu_k, \sum_k) $ 인데, 이 z_k가 k개 있으므로, 이를 일반화시키면 다음과 같이 나타낼 수 있다.

$ P(X|Z) = \prod_{k=1}^K N(x|\mu_k, \sum_k)^{z_k} $

위와 같은 baysian network를 가진 모델이 있다고 생각해보자. 파란색은 파라미터에 대한 노드를 나타낸 것이고, N이라는 박스는 안의 내용들이 N번 반복적으로 생성된다는 의미이다.

이 때, conditional probability는 다음과 같이 정의된다.

\[p(z_k=1|x_n) = \cfrac{P(z_k=1)P(x|z_k=1)}{\sum_{j=1}^K P(z_j=1)P(x|z_j=1)}\]

로 나타낼 수 있으므로, 위에서 구한 값들을 그대로 대입한다.

\[p(z_k=1|x_n) = \cfrac{\pi_k N(x|\mu_k, \sum_k)}{\sum_{j=1}^K \pi_j N(x|\mu_j, \sum_j)}\]

기존의 MLE를 구하는 방식은 distance를 사용하여 확률을 사용하지 않았다. 이번에는 확률을 가정했으므로, log likelihood를 활용하여 MLE를 하고자 한다.

Expectation and Maximization of GMM

GMM은 K-Means algorithm과 비슷하다. k-means에서는 assignment variable과 location of cetroid, 2개의 parameter가 존재한다.

GMMM에서는 location of centroid 와 동일한 역할을 하는 μ와 σ로 표현되는 Mixture component, π_k로 나타내지는 multinomial distribution으로 모델링된 값인 Mixing coefficients, k-means의 파라미터들과 동일한 역할을 하는 2개의 parameter가 있다.

이전에 Expectation and Maximization step에 대해 잠깐 살펴보았다. Expectation에서는 data point들을 centroid에 대해 할당하고, Maximization에서는 파라미터들을 업데이트한다.

Expectation step

기존에 K-means는 가장 가까운 centroid에 대해 각 데이터 포인트들을 0 또는 1로 할당했지만, 이제는 확률에 대해 계산할 것이므로 확률을 할당한다. 이전에 구했던 marginalized probability을 할당하면 된다.

$ \gamma(z_{nk}) = p(z_k = 1 | x_n) = \cfrac{P(z_k = 1)P(x|z_k = 1)}{\sum_{j=1}^K P(z_j=1)P(x|z_j=1)} = \cfrac{\pi_k N(x|\mu_k, \sum_k)}{\sum_{j=1}^k \pi_j N(x|\mu_j, \sum_j)} $

x와 파라미터(π,μ,∑) 가 주어졌을 때, $\gamma(z_{nk})$ 를 계산함.
$\gamma(z_{nk})$ 는 수많은 iteration을 통한 지속저긍로 갱신되는 파라미터에 의해 업데이트된다.

Maximization step

그 다음, Maximization step에서는 Expectation에서 계산한 $\gamma(z_{nk})$ 를 통해 파라미터들을 업데이트한다. 업데이트할 파라미터는 π,μ,∑ 이고, 이에 대한 업데이트 식은 다음과 같다.

$ lnP(X|\pi,\mu,\sum) = \sum_{n=1}^N ln{\sum_{k=1}^K \pi_k N(x|\mu_k, \sum_k)} $

이 파라미터들을 최적화를 하기 위해서는 이 식을 미분한다. 만약 제약조건이 존재한다면 lagrange method를 활용하여 미분한다. 각 파라미터들에 대해 미분하므로 총 3번 수행한다.

이 때, π_k에 대한 미분에서 한 데이터 포인트에 대해 k개의 대안이 존재할 때, r(z_nk)를 k개 다 더하면 1이 되고, 이 1을 N개의 데이터 포인트 개수만큼 더하므로 N이 된다. 그리고, pi_k는 확률인데, 이를 k에 대해 다 더하면 1이 된다. 따라서 λ = -N 이 된다.

이렇게 총 3개의 r(z_nk)에 대한 식이 나오므로 이를 통해 파라미터들을 업데이트하고, 이러한 과정을 Maximization이라 할 수 있다.

GMM이 k-means에 대해 soft한 이유는 데이터 포인트들이 확률로 할당되기에 확실한 색상이 아닌 융합된 색상으로 나타내어진다.

centroid(μ_k) 또한 gaussian distribution이므로 정확한 위치가 아닌 분포를 따르고 있다.

GMM의 속성에 대해 알아보자.

GMM의 장점으로는 Soft clustering이 가능해지고, 각각의 분포들에 대해 이전에는 서로의 관계를 알 수 없었으나, GMM에서는 서로의 분포간의 관계를 파악할 수 있으므로 더 많은 정보를 가질 수 있다.

단점으로는 연산이 더 많아지고, local maximum에 빠질 수 있다. 또한 k-means에서도 존재했던 centroid의 개수를 지정해주어야 한다는 점이다.

Relation between K-Means and GMM

multivariate gaussian distribution에 대한 식이 있었다. 이 때, 특정 k에 대한 상황일 때, ∑_k = 𝜖Ι 라고 가정해보자. I는 identity matrix를 의미하고, 𝜖는 EM process에 대한 값이다.

identity matrix는 역행렬과 형태가 동일하다.

이러한 상황에서 지수함수 안의 값을 살펴보자. 지수함수의 특성상 x가 -inf 로 가면 y는 0에 가까워진다. 𝜖가 0에 가까워질수록 -1/2𝜖는 -inf로 갈 것이다. 이러한 상황에서 데이터 포인트가 centroid와 가깝다면 x - μ_k 는 다소 작으므로 다소 천천히 0에 다가가게 되고, 데이터 포인트가 centroid와 멀다면 x - μ_k 는 크므로 빠르게 0에 다가간다.

그렇다면, 특정 상황에서 0 또는 1 로 binary하게 분류할 수 있게 되고, 이러한 경우에는 GMM이 k-means와 동일한 역할을 수행하게 된다.

EM Algorithm

EM 알고리즘에 대해 자세하게 살펴보자.

P(X|θ) 가 있을 때, Z라는 hidden variable이 존재한다면, 이에 대해 marginalization을 수행하여

$ P(X|\theta) = \sum_Z P(X,Z|\theta) $

라는 식이 성립된다.

이 때, q(Z)라는 임의의 변수를 생성하고, 이를 분모에 만들어준다.

그리고 Jensen’s inequality 라는 기법을 활용한다.

jensen’s inequality란 y = φ(x) 라는 식이 있을 때, x에 대한 평균값을 함수에 넣어서 얻은 y값과 각 x를 함수로 넣어 얻은 y들의 평균을 비교한다.

전자가 더 크다면 concave, 후자가 더 크다면 convex 라 한다.

그림에서 특정 함수 f가 있을 때, x1과 x2에 대해 각각 f(x1), f(x2)를 구하여 평균한 것보다 f(x1+x2)/2) 가 더 크면 concave, 더 작으면 convex이다. log(ln) 함수는 concave 에 해당된다.

만약에, $ \sum_Z q(Z) ln \frac{P(X,Z|\theta)}{q(Z)}$ 이 커지면, 좌항도 최소값이 커지는 것이므로 전체적으로 값들이 증가될 것이다.

$ \sum_Z q(Z) ln \frac{P(X,Z|\theta)}{q(Z)}$ 를 풀어보면 $ \sum_Z q(Z) ln P(X,Z|\theta) - q(Z)lnq(Z) $ 가 되고, q(Z)lnq(Z) 는 entropy 식과 동일하므로 entropy, H로 변환할 수 있다.

H로 변환하기 위해 q(Z)도 변하므로 이를 E_q(z) 로 표현할 수 있다. 이렇게 변환한 식을 Q(θ,q) 라는 새로운 함수로 정의한다. 이 때, q는 확률밀도함수여야 한다는 제약조건이 있다.

또는, P(X,Z|θ) 에 대해 bayes rule을 적용하여 변환할 수 있다. 이 때, q는 확률밀도함수로 가정했기 때문에 모든 z에 대해 q를 더하면 1이 된다.

이렇게 변환하게 되면,

$ lnP(X|\theta) - \sum_Z{q(Z)ln \frac{q(Z)}{P(Z|X,\theta)}} $

가 되고, 동일한 lnP(X|θ) 라는 값과 함께 inequality의 원인을 확인할 수 있게 된다. 이 원인을 제거한다면 부등호가 등호가 될 수 있을 것이다.

$ \sum_Z{q(Z)ln \frac{q(Z)}{P(Z|X,\theta)}} $ 를 자세히 살펴보게 되면, KL divergence의 형태와 매우 유사하다.

KL divergence란 kullback leiber divergence를 줄인 말로, 두 확률 분포를 비교하는 기법이다.

비교하는 식은 다음과 같다.

$ KL(P||Q) = \sum_i P(i) ln(\frac{P(i)}{Q(i)}) $

P와 Q라는 확률 분포에 대해 비교하는데, KL(P||Q)와 KL(Q||K) 가 다르다는 비대칭(Non-symmetric)한 특징이 있다. 또다른 특징으로는 KL(P||Q)는 항상 0보다 크다.

jensen’s inequality를 활용하여 표현한 L라는 식에서 θ^t라는 현재 시간에서 가지는 theta를 가져와서 그대로 q^t(Z)로 정의하게 되면 second(KL divergence) term이 0이 된다. 이를 통해 Q를 업데이트하고, 업데이트된 Q를 통해 theta를 최대화하여 theta^(t+1) 을 계산한다.

이를 그래프화하면 다음과 같다. KL이라는 제거할 term이 존재하여 이를 줄이기 위해 q를 최적화한다. 최적화된 q를 통해 다시 theta를 최적화할 수 있고, 최적화된 theta에 대해 다시 KL term이 생겨난다. 생겨난 KL term을 제거하기 위해 다시 q를 최적화한다.

이러한 반복을 통해 최적의 값으로 도달한다. 그러나 목표로 하는 곳은 global maxima이지만, 이 과정을 통해 local maxima에 빠질 수 있다.

EM 알고리즘을 정리하면 다음과 같다.

목표 : latent variable(Z)이 존재할 때 likelihood를 최대화한다.
과정
1. 무작위의 점으로 theta_0를 초기화한다.
2. likelihood가 수렴될 때까지 아래 과정을 반복한다.
3. Expectation step
  - $ q^{t+1}(z) = argmax_qQ(\theta^t, q) = argmax_qL(\theta^t,q) = argmin_qKL(q||P(Z|X,\theta^t)) $
    1. Z를 할당한다.
    2. $ \gamma(z_{nk}) = p(z_k=1|x_n) = \frac{P(z_k=1)P(x|z_k=1)}{\sum_{j=1}^kP(z_j=1)P(x|z_j=1)} = \frac{\pi_k N(x|\mu_k, \sum_k)}{\sum_{j=1}^k \pi_j N(x|\mu_j, \sum_j)} $
4. Maximization step
  - $ \theta^{t+1} = argmax_{\theta} Q(\theta, q^{t+1}) = argmax_{\theta} L(\theta, q^{t+1}) $
  - MLE와 동일한 과정의 최적화
    1. 미분하여 파라미터를 최적화한다.

[KOOC] 인공지능 및 기계학습 개론 8주차 - K-Means Algorithm, Gaussian Mixture Model and EM Algorithm