일반적인 EM 알고리즘 유도 과정

EM(Expectation-Maximization) 알고리즘은 불완전 데이터의 최대 가능도 추정을 위한 반복적 방법입니다. 주어진 관찰된 데이터 $X$와 숨겨진 변수 $Z$에 대해 파라미터 $\theta$를 추정하는 과정입니다.

최대 가능도 추정

주어진 관찰 데이터 $X$에 대해 파라미터 $\theta$를 추정하는 목표는 가능도 함수 $p(X|\theta)$를 최대화하는 것입니다. 로그 가능도는 다음과 같이 표현됩니다:

$[ \log p(X|\theta) = \log \sum_Z p(X, Z|\theta) ]$

여기서 $Z$는 숨겨진 변수입니다.

직접 최적화의 어려움

로그 가능도 $\log p(X|\theta)$를 직접 최적화하는 것은 숨겨진 변수 $Z$의 존재로 인해 어렵습니다. 따라서 EM 알고리즘은 대신 잠재 변수 $Z$의 분포 $q(Z)$를 사용하여 문제를 단순화합니다.

E 단계와 M 단계 유도

EM 알고리즘은 두 단계, E 단계와 M 단계로 구성됩니다.

E 단계 (Expectation Step)

E 단계에서는 현재 파라미터 추정값 $\theta^{(t)}$를 사용하여 잠재 변수의 분포 $q(Z)$를 추정합니다. 이는 $q(Z)$가 주어진 데이터 $X$와 현재 파라미터 $\theta^{(t)}$ 아래에서 숨겨진 변수 $Z$의 조건부 확률분포가 되도록 합니다:

$[ q(Z) = p(Z|X, \theta^{(t)}) ]$

이 조건부 분포를 사용하여 $\theta$에 대한 증분 가능도 $\mathcal{Q}(\theta, \theta^{(t)})$를 정의합니다:

$[ \mathcal{Q}(\theta, \theta^{(t)}) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ] ]$

이는 다음과 같이 계산됩니다:

$[ \mathcal{Q}(\theta, \theta^{(t)}) = \sum_Z p(Z|X, \theta^{(t)}) \log p(X, Z|\theta) ]$

M 단계 (Maximization Step)

M 단계에서는 $\mathcal{Q}(\theta, \theta^{(t)})$를 최대화하여 새로운 파라미터 추정값 $\theta^{(t+1)}$를 찾습니다:

$[ \theta^{(t+1)} = \arg \max_{\theta} \mathcal{Q}(\theta, \theta^{(t)}) ]$

유도 과정

EM 알고리즘의 유도 과정은 증분 로그 가능도 $\mathcal{L}(\theta, q)$를 최대화하는 것으로 시작됩니다:

$[ \mathcal{L}(\theta, q) = \mathbb{E}_{Z \sim q(Z)} [ \log p(X, Z|\theta) ] - \mathbb{E}_{Z \sim q(Z)} [ \log q(Z) ] ]$

여기서 첫 번째 항은 데이터와 숨겨진 변수의 결합 로그 가능도의 기대값이며, 두 번째 항은 $q(Z)$의 엔트로피입니다.

젠슨 불평등 사용

젠슨 불평등을 사용하여 다음과 같은 관계를 얻을 수 있습니다:

$[ \log p(X|\theta) = \log \sum_Z p(X, Z|\theta) \geq \sum_Z q(Z) \log \frac{p(X, Z|\theta)}{q(Z)} ]$

이 식에서 오른쪽 항은 증분 로그 가능도 $\mathcal{L}(\theta, q)$입니다:

$[ \mathcal{L}(\theta, q) = \sum_Z q(Z) \log \frac{p(X, Z|\theta)}{q(Z)} ]$

E 단계에서의 최적 분포 $q(Z)$

E 단계에서는 현재 파라미터 $\theta^{(t)}$를 사용하여 최적의 $q(Z)$를 찾습니다. 최적의 $q(Z)$는 $p(Z|X, \theta^{(t)})$입니다:

$[ q(Z) = p(Z|X, \theta^{(t)}) ]$

따라서 $\mathcal{L}(\theta, q)$는 다음과 같이 됩니다:

$[ \mathcal{L}(\theta, p(Z|X, \theta^{(t)})) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ] - \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(Z|X, \theta^{(t)}) ] ]$

M 단계에서의 파라미터 최적화

M 단계에서는 $\mathcal{L}(\theta, q)$의 첫 번째 항인 $\mathcal{Q}(\theta, \theta^{(t)})$를 최대화하여 파라미터 $\theta$를 업데이트합니다:

$[ \theta^{(t+1)} = \arg \max_{\theta} \mathcal{Q}(\theta, \theta^{(t)}) ]$

요약

1. E 단계:

   • 잠재 변수의 조건부 분포 $p(Z|X, \theta^{(t)})$를 계산합니다.
   • $\mathcal{Q}(\theta, \theta^{(t)})$를 계산합니다: $\mathcal{Q}(\theta, \theta^{(t)}) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ]$

2. M 단계:

   • $\mathcal{Q}(\theta, \theta^{(t)})$를 최대화하여 새로운 파라미터 $\theta^{(t+1)}$를 찾습니다: $\theta^{(t+1)} = \arg \max_{\theta} \mathcal{Q}(\theta, \theta^{(t)})$

위 과정을 반복하여 파라미터 $\theta$가 수렴할 때까지 진행합니다.

젠슨 불평등 (Jensen's Inequality)

젠슨 불평등은 볼록 함수(convex function)에 대한 중요한 불평등입니다. 이는 확률론과 정보 이론에서 매우 유용하게 사용되며, EM 알고리즘의 유도 과정에서도 중요한 역할을 합니다. 여기서는 젠슨 불평등의 개념과 이를 EM 알고리즘에 적용하는 방법을 상세히 설명하겠습니다.

볼록 함수와 오목 함수

먼저, 볼록 함수(convex function)와 오목 함수(concave function)에 대해 알아봅시다.

1. 볼록 함수 (Convex Function): 함수 $f(x)$가 정의역 내의 모든 $x$와 $y$에 대해 다음을 만족하면 볼록 함수라고 합니다.

$[ f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y) ]$

여기서 $0 \leq \lambda \leq 1$입니다. 이는 함수의 그래프가 두 점을 잇는 직선보다 아래에 있음을 의미합니다.

2. 오목 함수 (Concave Function): 함수 $f(x)$가 정의역 내의 모든 $x$와 $y$에 대해 다음을 만족하면 오목 함수라고 합니다.

$[ f(\lambda x + (1 - \lambda) y) \geq \lambda f(x) + (1 - \lambda) f(y) ]$

여기서 $0 \leq \lambda \leq 1$입니다. 이는 함수의 그래프가 두 점을 잇는 직선보다 위에 있음을 의미합니다.

젠슨 불평등 (Jensen's Inequality)

젠슨 불평등은 볼록 함수에 대해 다음과 같이 정의됩니다.

불평등의 정의

함수 $f$가 볼록 함수이고, $X$가 확률 변수일 때, 다음 불평등이 성립합니다:

$[ f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)] ]$

여기서 $\mathbb{E}[X]$는 $X$의 기대값을 의미합니다. 만약 $f$가 오목 함수라면 부등호의 방향이 반대가 됩니다:

$[ f(\mathbb{E}[X]) \geq \mathbb{E}[f(X)] ]$

증명

젠슨 불평등의 증명은 간단한 경우로부터 일반적인 경우로 확장됩니다. 여기서는 간단한 불연속 확률 변수의 경우를 증명하겠습니다.

증명 (불연속 확률 변수의 경우)

1. $X$가 불연속 확률 변수이고, $X$가 값 $x_i$를 확률 $p_i$로 취한다고 가정합니다. 따라서 $\sum_{i} p_i = 1$입니다.

2. 기대값 $\mathbb{E}[X]$는 다음과 같이 정의됩니다:

$[ \mathbb{E}[X] = \sum_{i} p_i x_i ]$

3. 볼록 함수 $f$에 대해, 다음을 보여야 합니다:

$[ f\left(\sum_{i} p_i x_i\right) \leq \sum_{i} p_i f(x_i) ]$

4. 볼록 함수의 정의에 따라, 모든 $x_i$에 대해 다음이 성립합니다:

$[ f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y) ]$

이를 $p_i$와 $x_i$의 합에 대해 확장하면 다음과 같이 됩니다:

$[ f\left(\sum_{i} p_i x_i\right) \leq \sum_{i} p_i f(x_i) ]$

따라서, 젠슨 불평등이 성립합니다.

EM 알고리즘에서 젠슨 불평등의 역할

EM 알고리즘에서는 젠슨 불평등을 사용하여 로그 가능도 $\log p(X|\theta)$를 하한으로 나타내고, 이를 최대화하는 과정을 반복합니다. 젠슨 불평등을 사용하여 다음과 같은 관계를 얻습니다:

$[ \log p(X|\theta) = \log \sum_Z p(X, Z|\theta) ]$

젠슨 불평등을 적용하여 다음과 같이 변형할 수 있습니다:

$[ \log p(X|\theta) = \log \sum_Z q(Z) \frac{p(X, Z|\theta)}{q(Z)} \geq \sum_Z q(Z) \log \frac{p(X, Z|\theta)}{q(Z)} ]$

여기서 $q(Z)$는 임의의 확률 분포입니다. 이 식은 다음과 같이 재구성할 수 있습니다:

$[ \log p(X|\theta) \geq \mathbb{E}_{Z \sim q(Z)} \left[ \log \frac{p(X, Z|\theta)}{q(Z)} \right] ]$

이렇게 젠슨 불평등을 사용하여 로그 가능도의 하한을 구하고, 이 하한을 최대화하는 것이 EM 알고리즘의 핵심 아이디어입니다.

요약

• 볼록 함수와 오목 함수: 볼록 함수는 두 점을 잇는 직선보다 아래에 있는 함수이고, 오목 함수는 그 직선보다 위에 있는 함수입니다.
• 젠슨 불평등: 볼록 함수 $f$에 대해, $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$가 성립합니다.
• EM 알고리즘에서의 역할: 젠슨 불평등을 사용하여 로그 가능도의 하한을 구하고, 이를 최대화하는 과정으로 파라미터를 추정합니다.

젠슨 불평등은 EM 알고리즘의 수학적 기초를 이해하는 데 중요한 도구입니다. 이를 통해 EM 알고리즘이 어떻게 동작하는지, 그리고 왜 그 과정이 유효한지 이해할 수 있습니다.

쿨백-라이블러 다이버전스(Kullback-Leibler Divergence)

쿨백-라이블러 다이버전스(KL 다이버전스)는 두 확률 분포 간의 차이를 측정하는 방법입니다. 이는 정보 이론에서 도입된 개념으로, 한 확률 분포를 사용하여 다른 확률 분포를 근사할 때 발생하는 정보 손실을 측정합니다.

정의

KL 다이버전스는 두 확률 분포 $P$와 $Q$에 대해 다음과 같이 정의됩니다:

$[ D_{KL}(P \parallel Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)} ]$

또는 연속 확률 분포의 경우:

$[ D_{KL}(P \parallel Q) = \int_{-\infty}^{\infty} p(x) \log \frac{p(x)}{q(x)} \, dx ]$

여기서:

• $P(x)$는 실제 분포 또는 참 분포입니다.
• $Q(x)$는 근사 분포 또는 모델 분포입니다.
• $p(x)$와 $q(x)$는 각각 $P$와 $Q$의 확률 밀도 함수입니다.

직관적인 설명

KL 다이버전스는 다음과 같은 질문에 답하는 도구입니다: "분포 $P$를 사용하여 데이터가 발생한다고 가정했을 때, 분포 $Q$를 사용하여 데이터를 설명하는 데 얼마나 많은 추가 정보가 필요한가?"

• 정보 손실: $P$와 $Q$가 동일하다면, KL 다이버전스는 0이 됩니다. 이는 두 분포 간에 정보 손실이 없음을 의미합니다.
• 비대칭성: KL 다이버전스는 대칭적이지 않습니다. 즉, $D_{KL}(P \parallel Q) \neq D_{KL}(Q \parallel P)$입니다. 이는 두 분포 사이의 방향성 있는 정보를 측정합니다.

성질

1. 비대칭성: $D_{KL}(P \parallel Q) \neq D_{KL}(Q \parallel P)$.
2. 비음성(non-negativity): $D_{KL}(P \parallel Q) \geq 0$, 평등은 $P = Q$일 때만 성립합니다.
3. 정확한 측정: KL 다이버전스는 실제로 두 분포 간의 "거리"가 아니라는 점에서 중요합니다. 이는 측정 기준이 방향성 있고 대칭적이지 않기 때문입니다.

예제

두 개의 확률 분포가 있다고 가정해 봅시다: $P$는 실제 분포이고 $Q$는 근사 분포입니다. 예를 들어, $P$는 다음과 같은 확률 분포를 가질 수 있습니다:

$[ P = \{0.1, 0.4, 0.5\} ]$

그리고 $Q$는 다음과 같은 분포를 가질 수 있습니다:

$[ Q = \{0.2, 0.3, 0.5\} ]$

이 두 분포 간의 KL 다이버전스를 계산해 보겠습니다:

$[ D_{KL}(P \parallel Q) = 0.1 \log \frac{0.1}{0.2} + 0.4 \log \frac{0.4}{0.3} + 0.5 \log \frac{0.5}{0.5} ]$

이를 계산하면:

$[ D_{KL}(P \parallel Q) = 0.1 \log 0.5 + 0.4 \log \frac{4}{3} + 0.5 \log 1 ]$
$[ = 0.1 \cdot (-0.301) + 0.4 \cdot 0.124 + 0.5 \cdot 0 ]$
$[ = -0.0301 + 0.0496 ]$
$[ = 0.0195 ]$

따라서, $P$와 $Q$ 사이의 KL 다이버전스는 약 0.0195입니다. 이는 $Q$가 $P$를 얼마나 잘 근사하고 있는지에 대한 정보 손실의 정도를 나타냅니다.

응용 분야

KL 다이버전스는 다양한 분야에서 사용됩니다:

• 정보 이론: 정보 손실과 효율성 분석
• 기계 학습: 모델 평가, 특히 베이즈 추론과 변분 추정(variational inference)에서 중요
• 통계학: 분포 간 차이 측정
• 신호 처리: 데이터 압축과 복원

결론

쿨백-라이블러 다이버전스는 두 확률 분포 간의 차이를 측정하는 강력한 도구입니다. 비대칭적 특성으로 인해 특정 응용 분야에서 두 분포의 방향성 있는 차이를 이해하고 분석하는 데 유용합니다. 이는 특히 모델의 성능을 평가하고 정보 손실을 최소화하는 데 중요한 역할을 합니다.

EM 알고리즘과 KL 다이버전스 유도 과정

EM(Expectation-Maximization) 알고리즘은 불완전 데이터의 최대 가능도 추정을 위한 반복적 방법입니다. KL 다이버전스는 두 확률 분포 간의 차이를 측정하는 도구로, EM 알고리즘의 유도에 중요한 역할을 합니다. 여기서는 EM 알고리즘을 KL 다이버전스를 사용하여 어떻게 유도할 수 있는지 상세히 설명하겠습니다.

1. 최대 가능도 추정

EM 알고리즘의 목표는 주어진 관찰 데이터 $X$에 대해 파라미터 $\theta$를 추정하여 가능도 함수 $p(X|\theta)$를 최대화하는 것입니다. 즉, 로그 가능도를 최대화하는 것입니다:

$[ \log p(X|\theta) = \log \sum_Z p(X, Z|\theta) ]$

여기서 $Z$는 숨겨진 변수(또는 잠재 변수)입니다. 하지만, 직접 최적화하기 어려운 이유는 숨겨진 변수 $Z$ 때문입니다.

2. 변분 방법 도입

KL 다이버전스를 사용하여 로그 가능도를 재구성할 수 있습니다. 임의의 확률 분포 $q(Z)$를 도입하고, Jensen's inequality(젠슨 불평등)을 사용하여 다음과 같이 재구성할 수 있습니다:

$[ \log p(X|\theta) = \log \sum_Z p(X, Z|\theta) ]$

젠슨 불평등을 사용하여 다음과 같이 변형합니다:

$[ \log p(X|\theta) = \log \sum_Z q(Z) \frac{p(X, Z|\theta)}{q(Z)} \geq \sum_Z q(Z) \log \frac{p(X, Z|\theta)}{q(Z)} ]$

오른쪽 항을 보면, 이는 증분 로그 가능도와 KL 다이버전스의 합으로 볼 수 있습니다. 이를 더 구체적으로 분해하면 다음과 같이 쓸 수 있습니다:

$[ \log p(X|\theta) = \mathbb{E}_{Z \sim q(Z)} [ \log p(X, Z|\theta) ] - \mathbb{E}_{Z \sim q(Z)} [ \log q(Z) ] + \mathbb{E}_{Z \sim q(Z)} [ \log q(Z) ] - \log \sum_Z q(Z) ]$

여기서 $\mathbb{E}_{Z \sim q(Z)}$는 $q(Z)$에 대한 기대값을 나타냅니다.

3. 증분 로그 가능도와 KL 다이버전스

위 식을 다시 정리하면 다음과 같이 됩니다:

$[ \log p(X|\theta) = \mathcal{L}(q, \theta) + D_{KL}(q(Z) \parallel p(Z|X, \theta)) ]$

여기서,

• $\mathcal{L}(q, \theta) = \mathbb{E}_{Z \sim q(Z)} [ \log p(X, Z|\theta) ] - \mathbb{E}_{Z \sim q(Z)} [ \log q(Z) ]$는 증분 로그 가능도입니다.
• $D_{KL}(q(Z) \parallel p(Z|X, \theta))$는 $q(Z)$와 $p(Z|X, \theta)$ 사이의 KL 다이버전스입니다.

KL 다이버전스는 항상 0보다 크거나 같기 때문에, 최대화 문제는 증분 로그 가능도 $\mathcal{L}(q, \theta)$를 최대화하는 문제로 변환할 수 있습니다.

4. E 단계 (Expectation Step)

E 단계에서는 $q(Z)$를 최적화하여 KL 다이버전스를 0으로 만듭니다. 이는 $q(Z)$를 $p(Z|X, \theta^{(t)})$로 설정하는 것입니다:

$[ q(Z) = p(Z|X, \theta^{(t)}) ]$

따라서, $\mathcal{L}(q, \theta)$는 다음과 같이 변형됩니다:

$[ \mathcal{L}(q, \theta) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ] - \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(Z|X, \theta^{(t)}) ] ]$

5. M 단계 (Maximization Step)

M 단계에서는 $\mathcal{L}(q, \theta)$를 최대화하여 파라미터 $\theta$를 업데이트합니다. 즉, 다음과 같은 최적화 문제를 풉니다:

$[ \theta^{(t+1)} = \arg \max_{\theta} \mathcal{Q}(\theta, \theta^{(t)}) ]$

여기서,

$[ \mathcal{Q}(\theta, \theta^{(t)}) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ] ]$

6. 상세한 수식 유도

E 단계에서 $\mathcal{Q}(\theta, \theta^{(t)})$를 계산하는 과정은 다음과 같습니다:

1. 현재 파라미터 $\theta^{(t)}$로 $p(Z|X, \theta^{(t)})$를 계산합니다.
2. $p(Z|X, \theta^{(t)})$를 사용하여 $\mathcal{Q}(\theta, \theta^{(t)})$의 기대값을 계산합니다:

$[ \mathcal{Q}(\theta, \theta^{(t)}) = \sum_Z p(Z|X, \theta^{(t)}) \log p(X, Z|\theta) ]$

M 단계에서는 $\mathcal{Q}(\theta, \theta^{(t)})$를 최대화하여 $\theta$를 업데이트합니다.

요약

1. E 단계:

   • $q(Z)$를 $p(Z|X, \theta^{(t)})$로 설정하여 KL 다이버전스를 0으로 만듭니다.
   • $\mathcal{Q}(\theta, \theta^{(t)})$를 계산합니다: $\mathcal{Q}(\theta, \theta^{(t)}) = \mathbb{E}_{Z \sim p(Z|X, \theta^{(t)})} [ \log p(X, Z|\theta) ]$

2. M 단계:

   • $\mathcal{Q}(\theta, \theta^{(t)})$를 최대화하여 새로운 파라미터 $\theta^{(t+1)}$를 찾습니다: $\theta^{(t+1)} = \arg \max_{\theta} \mathcal{Q}(\theta, \theta^{(t)})$

EM 알고리즘을 통해 로그 가능도를 점진적으로 최대화하고, 주어진 데이터에 대한 최적의 파라미터를 찾을 수 있습니다.