EM(Expectation Maximization)

EM 알고리즘(Expectation-Maximization Algorithm)은 관측되지 않은 데이터(숨겨진 변수) 또는 누락된 데이터가 포함된 확률 모델의 최대 우도 추정(MLE)을 찾기 위한 반복적인 최적화 알고리즘입니다. 이 알고리즘은 특히 혼합 모델(예: 가우시안 혼합 모델)을 피팅할 때 자주 사용됩니다. EM 알고리즘의 주요 아이디어는 관찰된 데이터와 숨겨진 데이터를 결합하여 우도 함수를 최대화하는 것입니다.

\(\)

EM 알고리즘의 단계

EM 알고리즘은 두 가지 주요 단계로 구성됩니다: E 단계(Expectation 단계)와 M 단계(Maximization 단계).

1. E 단계 (Expectation 단계):

숨겨진 변수의 기대값을 계산하는 단계입니다.
현재 매개변수 추정치를 사용하여 숨겨진 변수의 분포를 추정합니다.
이 단계에서는 관측된 데이터를 고정하고, 숨겨진 변수를 조건부 기대값으로 대체합니다.

2. M 단계 (Maximization 단계):

숨겨진 변수의 기대값을 사용하여 매개변수를 업데이트하는 단계입니다.
E 단계에서 계산된 기대값을 사용하여 우도 함수를 최대화하는 매개변수 추정치를 찾습니다.
매개변수가 업데이트되면 다음 반복에서 다시 E 단계로 이동합니다.

이 과정은 우도 함수가 수렴할 때까지 반복됩니다.

예제1 : 가우시안 혼합 모델 (Gaussian Mixture Model, GMM)

가우시안 혼합 모델은 여러 개의 가우시안 분포의 선형 결합으로 구성된 모델입니다. EM 알고리즘은 GMM의 매개변수를 추정하는 데 널리 사용됩니다.

1. 초기화:

가우시안 분포의 개수 \( K \)를 설정합니다.
각 가우시안 분포의 초기 매개변수(평균, 분산, 혼합 계수)를 설정합니다.

2. E 단계:

각 데이터 포인트가 각 가우시안 분포에 속할 확률(책임도, responsibility)을 계산합니다.
이 확률은 현재 매개변수 추정치를 사용하여 계산됩니다.

3. M 단계:

책임도를 사용하여 각 가우시안 분포의 매개변수를 업데이트합니다.
새로운 평균, 분산, 혼합 계수를 계산합니다.

4. 수렴 검사:

매개변수 추정치가 수렴할 때까지 E 단계와 M 단계를 반복합니다.

수학적 설명

E 단계

데이터 포인트 \( x_i \)가 가우시안 분포 \( k \)에 속할 확률을 계산합니다:
\[ \gamma_{ik} = \frac{\pi_k \mathcal{N}(x_i | \mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j \mathcal{N}(x_i | \mu_j, \Sigma_j)} \]

여기서:

\( \gamma_{ik} \)는 데이터 포인트 \( x_i \)가 가우시안 분포 \( k \)에 속할 책임도입니다.
\( \pi_k \)는 가우시안 분포 \( k \)의 혼합 계수입니다.
\( \mathcal{N}(x_i | \mu_k, \Sigma_k) \)는 가우시안 분포 \( k \)의 확률 밀도 함수입니다.

M 단계

책임도를 사용하여 매개변수를 업데이트합니다:
\[ \mu_k = \frac{\sum_{i=1}^N \gamma_{ik} x_i}{\sum_{i=1}^N \gamma_{ik}} \]
\[ \Sigma_k = \frac{\sum_{i=1}^N \gamma_{ik} (x_i – \mu_k)(x_i – \mu_k)^T}{\sum_{i=1}^N \gamma_{ik}} \]
\[ \pi_k = \frac{1}{N} \sum_{i=1}^N \gamma_{ik} \]

장점과 단점

장점:

관찰되지 않은 데이터가 포함된 모델에서 매개변수 추정에 효과적입니다.
혼합 모델과 같은 복잡한 모델을 피팅할 수 있습니다.

단점:

초기 매개변수 값에 민감하며, 지역 최적값에 수렴할 수 있습니다.
계산 비용이 높으며, 수렴 속도가 느릴 수 있습니다.

예제 2

EM 알고리즘은 통계 모델링, 기계 학습, 데이터 마이닝 등 다양한 분야에서 널리 사용됩니다. 관찰되지 않은 데이터가 있는 상황에서 강력한 도구로 사용될 수 있습니다.

위 그림은 EM 알고리즘을 사용하여 가우시안 혼합 모델(GMM)을 피팅한 결과를 시각화한 것입니다.

데이터 포인트: 두 개의 가우시안 분포에서 생성된 데이터를 나타냅니다. 각 데이터 포인트는 EM 알고리즘에 의해 할당된 클러스터에 따라 색상이 달라집니다.
가우시안 분포의 타원: 각 클러스터의 가우시안 분포를 나타내는 타원이 그려져 있습니다. 타원은 가우시안 분포의 평균과 공분산을 기반으로 그려지며, 타원의 크기와 방향은 분포의 모양과 범위를 나타냅니다.

이 시각화는 EM 알고리즘이 두 개의 가우시안 분포를 어떻게 식별하고 분리하는지 보여줍니다. 타원의 크기와 방향은 각 클러스터의 데이터 분포를 잘 설명하고 있습니다.