[ML] EM Algorithm과 GMM(Gaussian Mixture Model)

※해당 게시물에 사용된 일부 자료는 순천향대학교 빅데이터공학과 정영섭 교수님의 머신러닝 전공수업 자료에 기반하였음을 알려드립니다.

 

이번 포스팅에서는 EM(Expectation Maximum)알고리즘과 이 EM 알고리즘을 이용한 모델 중 하나인 GMM(Gaussian Mixture Model)에 대해서 알아보려고 한다. 목차는 다음과 같다.

 

1. EM 알고리즘이란?

2. EM 알고리즘 프로세스

3. GMM이란?

4. GMM에서 적용되는 EM알고리즘 프로세스

1. EM 알고리즘이란?

EM 알고리즘은 기본적으로 Unsupervised learning에 주로 사용되는 알고리즘이다. 그래서 Clustering에 사용되기도 한다. EM 알고리즘은 크게 E-step과 M-step 2가지 단계로 나누어질 수 있는데 결론부터 말하면 이 E-step과 M-step을 반복하면서(iterative) 최적의 파라미터값을 찾아가는 흐름이다. 그럼 각 단계에서 무엇을 하는지 간단히 알아보자.

 

• E-step : 주어진 임의의 파라미터 초기값에서 Likelihood와 최대한 근사한 likelihood값을 계산한다.

• M-step : E-step에서 계산된 likelihood를 최대화(maximize)하는 새로운 파라미터값을 얻는다.

• 위 2단계를 파라미터값이 크게변하지 않을 때까지 계속적으로 반복한다.

따라서 EM알고리즘의 목적은 Likelihood(조건부 확률)을 최대화하는 파라미터를 찾기 위함이라고 할 수 있다. 이 때 예전 포스팅에서 모델의 학습 방법 중 하나로 배웠던 MLE(Maximum Likelihood Estimation)과 동일한 방법이라고 생각할 수 있는데 두 방법 사이의 차이점은 분명하다. MLE는 파라미터 변수에 관해 편미분을 하여 최적의 파라미터를 '직접' 구했다. 즉, 목적함수가 미분이 가능한(Global optimum을 구할 수 있는) Convex 또는 Concave 함수라는 것이다. 

 

이에 반해 EM알고리즘은 E-M step을 반복하면서 최적의 파라미터에 근사한 값을 찾아나가는 과정이라고 볼 수 있다. ANN(인공신경망)모델과 유사하게 Global optimum을 찾는 것을 보장하진 못하며 설령 찾더라도 해당 지점이 진짜 Global optimum임을 인지를 못한다. 따라서 Local mimimum을 찾게 되며 목적함수가 Convex 또는 Concave 함수로 이루어지지 않았을 가능성이 매우 높다.(물론 항상 예외는 있는 법이라..)

 

EM알고리즘은 구하고자 하는 파라미터들의 함수(ex. 확률분포)에 대해 확률변수로 정의하여 이에 대해 최적화를 수행한다. 

 

출처 : https://jayhey.github.io/novelty%20detection/2017/11/03/Novelty_detection_MOG/

2. EM 알고리즘 프로세스

이제 본격적으로 EM알고리즘이 어떻게 전개해나가는지 수식과 연관지어 배워보자. 우선 익혀야 할 사전 개념이 있는데 바로 'Jensen's inequality' (옌센 부등식) 이다. 다음 그림을 살펴보자.

 

옌센 부등식

 

옌센 부등식은 기본적으로 아래로 볼록하거나 위로 볼록한 Convex 또는 Concave 모양의 함수일 때 성립하는 부등식이다. 먼저 Convex(아래로 볼록) 모양 그래프와 첫 번째줄 수식을 같이 살펴보면 그래프위에서 파란색 1번, 빨간색 2번 좌표에 해당하는 y값이 바로 옆의 수식의 1,2번이 mapping된다. 따라서 2번이 항상 1번보다 항상 같거나 크다는 부등식이 성립된다. 

 

반대로 Concave(위로 볼록) 모양 그래프일 때는 부등식의 기호가 반대로 바뀌어 성립된다. 이 부등식이 성립하는 Concave 함수의 대표적인 예시는 log함수가 있다.

 

이제 사전적인 개념을 익혔으니 본격적인 EM 알고리즘의 과정에 대해서 살펴보자.

 

EM알고리즘의 과정

 

우선 θ값을 모델 파라미터값으로 정의하고 Z값은 확률변수로 정의해보자. 이 때 Z값이라는 확률변수가 존재한다고 가정한다. 우리는 이 Z값을 통해서 θ값도 동시에 알아낼 수 있다. 그리고 X는 주어진 데이터를 의미한다. 

 

이제 위의 옌센 부등식이 성립하는 함수 종류 중 하나이며 Concave 모양인 log함수를 적용해 log-likelihood를 정의해보자. lnP(X|θ)이다. 이는 lnP(X,Z | θ) 로 나타낼 수 있으며 이를 q(Z)라고 정의해보자. q(Z)는 옌센 부등식을 성립하기 때문에 옌센부등식 공식에 q(Z)함수를 대입해보자. 이 때 옌센부등식의 우항에 해당하는 식이 L(q,θ) 이며 이 식을 통해 우리는 최적의 파라미터를 구할 것이다.

 

이제 옌센부등식에서 L(q,θ) 을 왼쪽으로 이항시켜 "q(Z) - L(q,θ) >= 0" 을 만들게 되면 이 수식 자체가 '두 확률분포의 차이'를 의미하게 된다. 여기서 두 확률분포의 차이를 구하는 KL Divergence를 이용하면 된다. 따라서 q(Z)와 L(q,θ)의 KL Divergence값을 최대한 작게 만들어서 q(Z) = L(q,θ)가 되도록 만들면 된다. 이 등식을 성립시키기 위해서는 KL = 0 이 되어야 한다.

 

그렇다면 어떻게 KL = 0이 되도록 만들 수 있을까? 다음 그림을 살펴보면서 EM알고리즘이 KL=0을 만들도록 하는 과정을 하나씩 읽어보자.

 

KL = 0을 어떻게 만들까?

3. GMM이란?

GMM은 Gaussian Mixture Model로 EM알고리즘을 적용한 여러가지 모델 중 하나이다. Clustering 모델에 사용되기도 하며 주로 음성인식 모델링시에 사용된다. GMM 알고리즘을 사용해 음성인식 기술을 개발하는 카카오에서 이에 대해서 잘 다룬 포스팅이 있어 공유하려 한다.

https://brunch.co.kr/@kakao-it/105

[카카오AI리포트]음성인식 방법과 카카오i의 음성형엔진

4. GMM에서 적용되는 EM알고리즘 프로세스

그렇다면 이제 EM알고리즘이 GMM모델에서 어떻게 적용되는지 알아보자. 먼저 GMM모델을 이해하기 위해서 하나의 가정을 들으면서 이해해보자. 밑의 그림에서 C값(두 개의 가우시안 분포가 존재함을 알고 있음)을 이미 안다고 가정하지만 실제 GMM모델은 C값을 모르는 상태이며 이 문제점 때문에 EM 알고리즘이 사용되는 것이다.

 

GMM모델을 이해하기 위한 가정예시

 

우선 우리는 C값 즉, 두 개의 확률분포가 모두 베르누이 분포임(각 분포를 Cluster1, Cluster2로 지정해보자.)을 알고 있다고 가정해보자. C값을 알고 있으니 모델 파라미터 값인 θ값(두 개의 베르누이 분포의 평균과 표준편차값들)을 자동으로 알게 된다. 이 상태에서 특정 데이터 x일 때의 Marginal값을 구해보자. 현재 가정하고 있는 예시에서라면 특정 데이터 x가 Cluster1일 때의 경우와 Cluster2일 때의 경우를 구하고 이 두 개의 값을 더해줌으로써 Marginal값을 구할 수 있다. 

 

그렇다면 이제 특정 데이터 하나일 때가 아닌 모든 데이터를 고려할 경우를 살펴보자.

 

모든 데이터를 고려해보자.

 

모든 데이터를 고려하게 되면 위 그림의 맨 윗줄 수식처럼 바뀐다. 단순히 시그마로 모든 데이터를 고려하는 수식을 추가한 것 밖에 없다. 이 때 우리는 C값을 알고 있으므로 MLE를 이용해서 쉽게 최적의 파라미터를 직접 구할 수 있게 된다.

 

하지만 문제는 우리가 사전에 C값을 알 수가 없다는 것이다.

 

C값을 모르면 어떻게 해야할까?

 

이제 우리는 앞서 배웠던 EM알고리즘을 사용하게 된다. 먼저 초기 파라미터값(θ값)을 임의로 부여해준다. 그리고 앞에 설명할 때 정의했던 변수를 그대로 이용하자면 log-likelihood와 가장 근사한 값의 L(q,θ)값을 구한다. 그리고 이 L(q,θ) 을 최대화하는 새로운 θ값을 구한다. 

 

다음은 위 GMM에 적용되는 EM알고리즘을 수학적 수식으로 설명한 그림들이다. 

<E-step>

E-step의 수학적 수식

상황은 오른쪽 그림과 같다고 생각하면 된다. 이 때 우리는 감마(Γ, γ)값을 구해주기 위해서 초기값으로 임의로 부여한 파라미터(θ)값에 기반해 계산한다.(위의 예시는 현재 두 개의 가우시안 분포라고 임의로 초기값을 딱 맞게 부여했다고 가정했기 때문에 위 수식에서 C=1, C=2일 때라고 적혀있는 것이다. 이렇게 초기값을 딱 들어맞게 준다는 것은 사실상 불가능한 일이긴 하다..) 

 

C=1일 때의  감마(Γ, γ)값 수식을 간단하게 이해한다고 하면 "C=1일 경우 / (C=1일경우 + C=2일경우)" 가 되겠다. C=2일 때의 감마(Γ, γ)값 수식도 C=1일때와 똑같이 이해하면 된다.

 

<M-step>

M-step의 수학적 수식

 

이제 M-step으로 넘어와서 E-step에서 구한 감마(Γ, γ)값을 최대화하는 것이다. 이번 예시에서는 파라미터 θ값에 속하는 여러가지 파라미터값들(평균, 표준편차값들) 중 μ1의 arg max를 어떻게 구하는지만 살펴보자. arg max를 구하기 위해서 "μ1 = arg max ~ "의 우항에 해당하는 식을  μ1에 관해서 '=0'으로 두고 미분을 수행해준다. 

 

미분을 해주는 이유는 log함수가 Concave함수 모양으로 미분=0이 되는 y값이 최대값을 갖게되기 때문이다. 이런 식으로 다른 파라미터인 μ2, σ1, σ2에 대해서도 각 변수에 관해 편미분을 해줌으로써 각 파라미터의 최대값을 찾을 수 있게 된다.

 

마지막으로 이러한 E-M step을 계속적으로 반복하면서 최적의 파라미터 값을 찾아주게 된다.