기댓값 최대화 알고리즘

역사

기댓값 최대화 알고리즘은 1977년 아서 뎀스터, 낸 라드와 도널드 루빈에 의해 제시되었다. 하지만 특수한 경우에서의 기댓값 최대화 알고리즘은 이미 몇몇 저자들에 의해 연구되고 있었고, 특히 롤프 선드버그는 페르 마틴-뢰프, 앤더스 마틴-뢰트와 함께 지수족에 한정된 기댓값 최대화 알고리즘에 관한 연구를 한 바 있다. 1977년 뎀스터-라드-루빈 논문은 이 방법을 일반화하여 지수족뿐만 아니라 다양한 확률분포에 한해서도 알고리즘이 수렴함을 밝혔다. 왕립통계협회저널에 게재된 이 논문은 그 혁신성으로 인해 롤프 선드버그를 비롯한 여럿에게 극찬을 받았으며, 기댓값 최대화 알고리즘을 통계분석의 중요한 도구로 자리매김하게 하였다.
이후 뎀스터-라드-루빈 논문의 알고리즘 수렴성 분석에 오류가 발견되었고, 1983년 C.F. 제프 우에 의해 옳은 증명이 제시되었다. 제프 우의 증명은 기댓값 최대화 알고리즘이 지수족뿐만 아니라 다른 확률분포에도 성립함을 보였다.

서론

기댓값 최대화 알고리즘은 통계 모델의 수식을 정확히 풀 수 없을 때 최대가능도를 구하는 데 사용된다. 이런 통계 모델은 대개 잠재변수와 관측할 수 없는 모수, 관측된 데이터로 구성되어 있고, 몇몇 관측값들이 누락되어 있거나 관측되지 않은 데이터가 존재한다고 가정할 수도 있다. 예를 들면, 혼합 모델에서 매 관측값이 그에 상응하는 잠재변수 혹은 관측되지 않은 값을 가지고 있다고 가정할 수 있다.
최대가능도는 관측되지 않은 모든 변수 각각에 대하여 로그가능도를 미분한 식을 풀어서 구할 수 있다. 하지만 잠재변수를 포함하는 통계 모델의 수식들은 매우 복잡하여 이와 같은 방법으로는 풀 수 없다. 각각의 변수에 관해 미분한 식은 서로 얽혀있어 한 수식의 해를 구하기 위해서는 다른 식의 해를 구해야 하는데, 이 수식의 해 또한 이전 식의 변수를 포함하기 때문이다. 따라서 이 경우 정확한 해를 계산하는 것은 불가능하다.
하지만 기댓값 최대화 알고리즘을 이용하면 이 문제의 해를 수치적으로 계산할 수 있다. 우선 서로 얽혀있는 두 식과 각각의 변수들을 가정해보자. 두 식은 얽혀있기 때문에 한 식의 변수는 다른 식의 변수일 수 있다. 첫번째 식의 변수값을 임의로 잡은 후 이 변수값으로 두번째 식의 변수값을 추정한다. 그렇게 구한 변수값으로 다시 첫번째 식의 변수값을 추정하고 이를 반복한다. 특정한 상황에서 충분히 많은 반복을 거치면 각각의 변수들이 일정한 값으로 수렴한다는 것을 보일 수 있다. 또한, 이 값에서 로그가능도의 미분은 0이 됨을 보일 수 있고, 이는 이 값이 극점이거나 안장점임을 의미한다. 일반적으로 로그가능도는 여러 개의 극점을 가질 수 있으므로 기댓값 최대화 알고리즘이 반드시 최댓값을 구할 수는 없다. 어떤 가능도는 특이점, 즉 무의미한 극점을 갖기도 한다. 예를 들어, 혼합 모델에서 한 성분의 평균 매개변수를 관측된 하나의 데이터로 놓고 분산 변수를 0으로 설정할 때 발생하는 특이점이 기댓값 최대화 알고리즘으로 구해지는 해가 될 수 있다.

성질

비록 EM을 반복하는 것이 관측된 데이터(한계) 기능도 함수를 증가시키지만 그 순열이 최대가능도로 수렴한다는 증거는 없다. 다항 분포에서는, EM 알고리즘이 초기값에 따라 관측된 데이터 가능도 함수의 극대값으로 수렴할 수도 있다. 경사 하강법(서로 다른 초기 추정량 에서 시작하는 방법)이나 담금질 기법 등 수 많은 체험적이거나 메타 발견적 학습 방법이 있다.
EM은 가능도가 지수족일때 특히 유용하다: E 단계는 충분 통계량(Sufficient statistic)의 기대값들의 합이 되며, M 단계는 선형 함수를 최대화하는 것을 포함한다. 이런 경우에는, 각각의 단계에서 선드버그 공식을 이용하여 닫힌 해를 도출하는 것이 가능하다.
EM 방법은 뎀스터-라드-루빈 논문에서 베이즈 추론에서 최대 사후 확률을 계산하기 위해 변형되었다.
경사 하강법, 켤레기울기법, 또는 가우스-뉴턴 방법의 변형 등과 같은 최대가능도를 찾는 여러 방법들이 존재한다. EM과 달리, 이러한 방법들은 일반적으로 가능도 함수의 첫 번째와 두 번째 미분의 계산을 필요로 한다.

적용

기댓값 최대화 알고리즘은 기계 학습과 컴퓨터 비전의 데이터 클러스터링에 자주 사용된다. 자연 언어 처리 분야에는 확률적 문맥 자유 문법(probabilistic context-free grammar)의 자율 유도를 위한 두 가지 중요한 알고리즘의 예로 바움-웰치 알고리즘(Baum-Welch algorithm)과 안밖 알고리즘(inside-outside algorithm)이 있다.
심리측정학에서 기댓값 최대화 알고리즘은 문항 반응 이론 모델의 아이템 매개변수와 잠재 능력의 추정을 위해 거의 없어서는 안된다.
기댓값 최대화 알고리즘은 누락된 데이터를 처리하고 미확인 변수를 관찰하는 능력이 있어 포트폴리오 리스크(portfolio risk)의 가격을 정하고 관리하는 유용한 도구가 되고 있다.
기댓값 최대화 알고리즘은 또한 의학 영상 복원, 특히 양전자 방출 단층촬영과 단일광자방출단층활영(single photon emission computed tomography)에 널리 쓰인다.

변종

기댓값 최대화 알고리즘의 때때로 느린 수렴을 가속화 하기 위해서 몇 가지 방법이 제시되어 왔다. 켤레기울기법을 사용하는 것과 수정된 뉴턴의 방법 기법들이 그 예다. 추가적으로 기댓값 최대화 알고리즘은 속박 추정 기법들과 함께 쓰인다.
조건부 기댓값 최대화(Expectation conditional maximization, 약자 ECM)는 각각의 M 단계를 각각의 매개변수 가 개별적으로 최대화 되고 조건부로 다른 매개변수들은 고정되는 조건부 최대화 (CM) 단계의 배열로 대체하였다.
이 아이디어는 후에 대체 설명에서 E 단계와 M 단계 모두에 대해서 손실 함수 F의 증가를 찾는 일반화된 기댓값 최대화(generalized expectation maximization, 약자 GEM) 알고리즘으로 확장된다.
기댓값 최대화 알고리즘을 MM (Majorize/Minimize 또는 Minorize/Maximize, 문맥에 따라서) 알고리즘 의 하위 분류로 간주하는 것도 또한 가능하고 그러므로 더욱 일반적인 경우에 대해 개발된 어떤 기구를 사용하는 것이 가능하다.

α-EM 알고리즘

기댓값 최대화 알고리즘에 사용되는 Q-함수는 로그가능도를 기반으로 하고 있다. 그러므로, log-EM 알고리즘으로 간주된다. 로그가능도의 사용은 α-로그가능도 비율로 일반화 될 수 있다. 그러면, 관찰된 데이터의 α-로그가능도 비율은 그것의 Q-함수와 α-발산을 사용한 등식으로 정확하게 표현된다. 이 Q-함수를 얻는 것은 일반화 된 E 단계이다. 그것의 최대화는 일반화된 M 단계이다. 이 두 단계를 α-EM 알고리즘

이라고 부르며 log-EM 알고리즘이 이에 하위 분류로 포함된다. 따라서, 야스오 마츠야마(Yasuo Matsuyama)의 α-EM 알고리즘은 정확히 log-EM 알고리즘의 일반화이다. 기울기 또는 Hessian 행렬의 계산이 필요 없다. α-EM은 알맞은 α를 선택함으로써 log-EM 알고리즘 보다 더 빠르게 수렴한다. α-EM 알고리즘은 은닉 마르코프 모델 추정 알고리즘 α-HMM 의 더 빠른 버전으로 이어졌다.

변분 베이즈 근사법과의 관계

기댓값 최대화 알고리즘은 부분적으로 베이즈가 아닌 최대가능도방법이다. 최종 결과는 (베이즈 방식의) 잠재변수와 θ (최대가능도 또는 사후 최빈값(posterior mode) 중 하나)의 점추정에 대한 확률분포로 나타난다. 잠재변수처럼 θ에 대한 확률분포로 나타나는 완전한 베이즈 방식의 버전을 생각해 볼 수 있다. 추론을 위한 베이즈 방식의 접근법은 간단하게 θ을 다른 잠재변수와 같이 취급한다. 이 패러다임에선 E 단계와 M 단계의 구분이 없어진다. 만약 위에서 말한 변분 베이즈 근사법과 같이 인수분해된 Q 근사값을 사용하면, 각각의 잠재변수(θ가 포함된)에 대해서 반복하고 한 번에 하나씩 최적화할 수 있다. 그러면 k가 잠재변수의 개수라고 할 때, 한 번 반복할 때마다 k 단계들이 있다. 그래픽 모델(graphical models)에서 앞의 방법은 각각의 변수의 새로운 Q를 마르코프 블랭킷(Markov blanket)에만 의존시킴으로써 쉽게 만들 수 있어서, 국소 메시지 전달(message passing)이 효율적인 추론으로 사용될 수 있다.

기하학적 해석

정보 기하학(information geometry)에서, E 단계와 M 단계는 이중 아핀 접속의 사영(projection)으로 해석되고, e-연결(e-connection)과 m-연결(m-connection)로 불린다. 쿨백-라이블러 발산 또한 이 용어들을 사용해서 해석될 수 있다.

알고리즘의 종료

반복과정은 각 과정에서 가능도 사이의 증가폭이 사전에 정의된 기준점 아래로 내려오면 종료한다.
즉, 사전에 정의된 기준점 에 대해서, 이면 종료한다.

일반화

앞서 소개한 알고리즘은 두 개 이상의 다변량 정규 분포를 혼합한 경우에도 적용이 가능하다.

예제 2: 베르누이 혼합 모델

동일한 크기의 이미지 개가 주어졌을 때, 이를 라 하자. 각 이미지는 개의 픽셀로 이루어져 있고 각 픽셀은  혹은 의 값을 가진다. 즉, 이다. 또한 각각의 픽셀이 서로에 대해 조건부 독립적이라 가정하면, 성분 의 모든 이미지에 관한 픽셀 의 확률분포는 모수 를 갖는 베르누이 분포로 모델링 할 수 있다.
혼합 모델이 개의 군집(cluster)을 가진다고 가정할 때, 어떤 이미지가 군집 에 속해 있을 확률을 이라 하자. 는 혼합 계수(mixing coefficient)라 불린다.
이 모델은 어떤 이미지가 특정 군집에 속할 확률변수와 그 군집에서의 픽셀 분포 변수를 모수로 갖는다. 즉, 이고,
이다.
하나의 트레이닝 이미지(training image) 에 관한 가능도 함수는 다음과 같다.
이 때 가 군집 에 의해 생성되었을 확률은 다음과 같다.
-차원 잠재변수 을 정의함으로써 주어진 이미지가 어떤 군집에 속할 확률을 모델링 할 수 있다. 가 -of- 표기법으로 나타내어졌다고 하자. 즉,
에 대하여, 이고, 가 성립한다.
의 분포가 로 주어져 있다고 가정하자. 그러면 다음이 성립한다.
또한, 라 하면,
이다.
잠재변수 들을 포함하는 집합 를 정의하고 위 수식을 사용하면,
이 성립하고,
트레이닝 이미지의 집합 를 정의하면 에 관한 의 조건부 확률분포를 다음과 같이 유도할 수 있다.
이제 위 수식들과 확률의 곱셈법칙을 이용하면 완전한 데이터 가능도(complete data likelihood)를 구할 수 있고,
이에 로그함수를 취하면 완전한 데이터 로그가능도(complete data log-likelihood) 가 유도된다.

기댓값 단계(E step)

기댓값 단계에서 잠재변수의 값을 업데이트 하기 위해 의 확률분포를 이라 하자. 이 분포는 정확히 풀 수 없으므로 값을 추정해야 하는데, 이를 위해 현재 의 값을 이 변수의 기댓값으로 대체한다.
이와 같이 의 값을 업데이트 하면 잠재변수 가 더 이상 -of-식으로 나타내어지지 않는다는 사실을 알 수 있다. 이는 이미지 이 하나의 군집이 아니라 여러 개의 군집에 부분적으로 속한다는 것을 의미한다.

최대화 단계(M step)

이 모델의 모수들(혼합 계수 및 군집별 픽셀 분포 변수)을 최대화하기 위해 다음 식을 이용한다.
위 식을 에 관해 최대화하기 위해 미분하여 이 되는 값을 찾는다.
이 때, 는 군집 에 실질적으로 속한 이미지의 개수이다.
군집 에서의 픽셀 분포의 매개변수 는 다음과 같이 나타낼 수 있다.
는 군집 에 (실질적으로) 속한 이미지들의 가중 평균을 의미한다.
를 혼합 계수 와 조건 에 관해 최대화하기 위해 라그랑주 승수법(Lagrange Multiplier)을 이용한다.
최댓값은 다음과 같이 구할 수 있다.
위 두 결과를 종합하면 이고,
이다.

요약

베르누이 혼합 모델의 기댓값(E) 및 최대화(M) 단계의 수식들은 다음과 같다.
기댓값 단계(E step):
최대화 단계(M step):
이 때, 이고, 이다.

EM의 대체 알고리즘

EM은 극값으로만 수렴하고 일반적으로 수렴율에 대한 범위가 없다. 고차원에서 잘 작동하지 않고 극값의 수가 다수가 존재할 가능성이 있다. 따라서 특히 고차원 상에서 다른 학습 방법을 사용할 필요가 있다. 이 때 모멘트-기반 접근 방식이나 스펙트럼 기법이 더 좋은 효과를 보장한다. 모멘트-기반 접근은 확률 모형의 매개변수를 학습하기 위한 것으로 최근 들어 사용이 많아지기 시작했는데, 이는 EM이 극값만을 보장해주는 것에 반해 모멘트-기반 접근은 최대, 최솟값을 보장하기 때문이다. 혼합 모형, 은닉 마르코프 모델, 공동체 모델 등으로부터 학습을 보장하는 알고리즘들이 유도될 수 있다. 이 스펙트럼 방법들은 잘못된 극값을 찾아내지 않고, 모수의 참값을 특정 제약 조건 하에서 일관적으로 도출시킨다.