EM 알고리즘의 수렴성

 

 

 

문제의 정의

$X$ : 관측된 데이터

$Z$ : 잠재 변수

$\theta$ : 모델의 파라미터

 

목표 : 로그우도

 

$L(\theta) = \ln P(x|\theta) = \ln \displaystyle \sum_{Z} P(X,Z|\theta) $

 

위 식을 최대가 되게 만드는 $\theta$를 찾는 것이다.

하지만 잠재 변수 $Z$에 대한 합(또는 적분)이 로그 함수 내부에 있어서 이를 직접 미분하여 최적화하는 것은 해석적으로 매우 어렵다.

 

옌센 부등식(Jensen's Ineuqality)와 증거 하한(ELBO)

이 문제를 해결하기 위해 잠재 변수 $Z$에 대한 임의의 확률 분포 $q(Z)$를 도입한다. 

 

$\sum_{Z}q(Z)=1$이고 $q(Z)\ge0$이므로 식을 다음과 같이 조작할 수 있다.

 

$L(\theta) = \ln \displaystyle \sum_{Z}P(X,Z|\theta) = \ln \sum_{Z} q(Z)\dfrac{P(X,Z|'theta)}{q(Z)} $

 

로그 함수는 오목 함수이므로 옌센 부등식 $\log(\mathbb{E}[Y] \ge \mathbb{E}[\ln (Y)]$를 적용할 수 있다. 즉, 

 

$L(\theta) \ge \displaystyle \sum_{Z} q(Z)\ln\dfrac{ P(X,Z|\theta) }{ q(Z) } $

 

우변의 식을 ELBO(Evidence Lower BOund)라고 정의하며, 이를 $\mathcal{L}(\theta, q)$로 표기하자. 그러면 우도 함수는 항상 ELBO보다 크거나 같다.

 

$L(\theta) \ge \mathcal{L}(\theta, q)$

 

E-step

E-step의 핵심은 현재 파라미터 $\theta^{(t)}$가 주어졌을 때, 하한인 ELBO를 원래의 목적 함수인 $L(\theta^{(t)})$와 완전히 접하게(tight) 만드는 확률 분포 $q(Z)$를 찾는 것이다

.

그 우도와 ELBO의 차이는 사실 쿨백-라이블러 발산(Kullback-Leibler Divergence)으로 나타낼 수 있다.

 

$L(\theta) - \mathcal{L}(\theta, q) = D_{KL}(q(Z) || P(Z|X, \theta)) \ge 0$

 

등호가 성립하려면(즉, 차이가 0이 되려면) $q(Z)$가 조건부 확률 분포 $P(Z|X, \theta)$와 완전히 같아져야 합니다. 따라서 $t$번째 단계에서 우리는 $q$를 다음과 같이 설정합니다.

 

$q^{(t)}(Z) = P(Z|X, \theta^{(t)})$

 

이렇게 설정하면, 다음 등식이 성립합니다.

 

$L(\theta^{(t)}) = \mathcal{L}(\theta^{(t)}, q^{(t)})$

 

M-step

M-step에서는 E-step에서 구한 분포 $q^{(t)}(Z)$를 고정한 상태에서, 하한인 $\mathcal{L}(\theta, q^{(t)})$를 최대화하는 새로운 파라미터 $\theta^{(t+1)}$을 찾습니다.

 

$\theta^{(t+1)} = \arg\max_{\theta} \mathcal{L}(\theta, q^{(t)})$

 

이 정의에 의해, $\theta^{(t+1)}$에서 평가한 ELBO는 $\theta^{(t)}$에서 평가한 ELBO보다 항상 크거나 같습니다.

 

$\mathcal{L}(\theta^{(t+1)}, q^{(t)}) \ge \mathcal{L}(\theta^{(t)}, q^{(t)})$

 

 

유계 단조 수열은 수렴한다

학부 해석학 초반에 배우는 'Bounded and monotone sequences are convergent'을 이용하면 된다.

 

E-M 단계를 거치며 ELBO는 단조 증가(Monotonically increasing)하지만 상한(Upper bound) $L(\theta)$가 있으므로 반드시 수렴한다.