기댓값-최대화(EM) 알고리즘의 개념
기댓값-최대화(Expectation-Maximization, EM) 알고리즘은 모수(parameter) 추정치를 찾아내는 데 널리 사용되는 대표적인 반복적 개선(iterative refinement) 알고리즘입니다. EM은 k-평균(k-means) 패러다임의 확장으로 볼 수 있는데, k-평균에서는 군집 평균을 기준으로 각 객체를 가장 유사한 군집에 할당하는 방식을 사용합니다.
반면 EM은 각 객체를 '소속 확률(membership probability)'을 나타내는 가중치에 따라 군집에 배정합니다. 다시 말해, 군집 사이에 엄격한 경계가 존재하지 않으며, 새로운 군집 평균은 이러한 가중치가 반영된 측정값을 기반으로 계산됩니다.
EM 알고리즘의 작동 원리
EM 알고리즘은 혼합 모델(mixture model)의 모수들, 즉 모수 벡터(parameter vector)에 대한 초기 추정치 또는 '추측(guess)'에서 출발합니다. 이후 모수 벡터가 생성한 혼합 밀도와 비교하여 객체들을 반복적으로 재점수화(rescoring)하며, 재점수화된 객체들을 이용해 모수 추정치를 갱신합니다.
각 객체는 특정 군집에 속해 있다는 가정 하에 해당 속성 값 집합을 가질 확률을 부여받게 됩니다. 전체 알고리즘은 다음과 같은 절차로 구성됩니다.
1단계: 모수 벡터의 초기 추정
k개의 객체를 무작위로 선택하여 군집 평균 또는 중심을 정의하고(k-평균 분할 방식과 유사), 나머지 모수에 대한 초기 추측값을 설정합니다.
2단계: 두 단계의 반복적 개선
다음의 두 단계를 반복하면서 모수(또는 군집)를 지속적으로 개선합니다.
(a) 기대 단계(Expectation Step)
각 객체 xi를 다음 확률에 따라 군집 ck에 할당합니다.
$$P(x_{i}\epsilon C_{k})=p(C_{k}|x_{i})=\frac{p(C_{k})p(x_{i}|C_{k})}{p(x_{i})}$$
여기서 p(xi|Ck) = N(mk, Ek(xi))는 평균 mk를 중심으로 하는 정규(가우시안) 분포를 따르며, 기댓값은 Ek입니다. 즉, 이 단계에서는 모든 군집에 대해 객체 xi의 군집 소속 확률을 계산하며, 이 확률들이 곧 객체 xi의 '기대되는(expected)' 군집 소속도가 됩니다.
(b) 최대화 단계(Maximization Step)
앞선 기대 단계에서 얻은 확률 추정치를 활용하여 모델의 모수를 재추정(또는 개선)합니다. 예를 들어 다음과 같습니다.
$$m_{k}=\frac{1}{n}\sum_{i=1}^{n}\frac{x_{i}P(x_{i}\epsilon C_{k})}{\sum_{j}P(x_{i}\epsilon C_{j})}$$
이 단계는 주어진 데이터에 대한 할당 결과의 가능도(likelihood)를 '최대화'하는 과정이라고 할 수 있습니다.
EM 알고리즘의 특징과 성능
EM 알고리즘은 구조가 단순하여 이해하고 구현하기 쉽다는 장점이 있습니다. 빠른 속도로 수렴하지만, 항상 전역 최적해(global optimum)에 도달한다고 보장할 수는 없습니다. 다만 특정 형태의 최적화 함수에 대해서는 수렴이 보장됩니다.
계산 복잡도는 입력 특성의 수(d), 항목의 수(n), 반복 횟수(t)에 대해 선형적으로 증가하므로, 대규모 데이터에도 비교적 효율적으로 적용할 수 있습니다.
베이지안 군집화와 AutoClass
베이지안 군집화 기법은 클래스 조건부 확률 밀도(class-conditional probability density)의 계산을 목표로 하며, 주로 통계학 분야에서 활용되어 왔습니다.
산업 현장에서 가장 잘 알려진 베이지안 군집화 기법 중 하나가 AutoClass입니다. AutoClass는 EM 알고리즘의 변형된 형태를 사용하며, 객체가 속한 올바른 군집이 주어졌을 때 해당 객체의 속성 값을 예측하는 능력을 최대화하는 군집화를 목표로 합니다. 또한 AutoClass는 군집의 개수까지 자동으로 추정할 수 있다는 강점이 있습니다.
AutoClass는 다양한 응용 분야에서 활용되었으며, 실제로 적외선 천문학 데이터를 분석하여 기존에 알려지지 않았던 새로운 별의 종류를 발견하는 성과를 거두기도 했습니다.