기댓값 최대화 알고리즘
기댓값 최대화 알고리즘(, 약자 EM 알고리즘)은 관측되지 않는 잠재변수에 의존하는 확률 모델에서 최대가능도()나 최대사후확률(, 약자 MAP)을 갖는 모수의 추정값을 찾는 반복적인 알고리즘이다.
EM 알고리즘은 모수에 관한 추정값으로 로그가능도()의 기댓값을 계산하는 기댓값 (E) 단계와 이 기댓값을 최대화하는 모수 추정값들을 구하는 최대화 (M) 단계를 번갈아가면서 적용한다.
최대화 단계에서 계산한 변수값은 다음 기댓값 단계의 추정값으로 쓰인다.
기댓값 최대화 알고리즘은 1977년 아서 뎀스터, 낸 라드와 도널드 루빈에 의해 제시되었다. 하지만 특수한 경우에서의 기댓값 최대화 알고리즘은 이미 몇몇 저자들에 의해 연구되고 있었고, 특히 롤프 선드버그는 페르 마틴-뢰프, 앤더스 마틴-뢰트와 함께 지수족에 한정된 기댓값 최대화 알고리즘에 관한 연구를 한 바 있다. 1977년 뎀스터-라드-루빈 논문은 이 방법을 일반화하여 지수족뿐만 아니라 다양한 확률분포에 한해서도 알고리즘이 수렴함을 밝혔다. 왕립통계협회저널에 게재된 이 논문은 그 혁신성으로 인해 롤프 선드버그를 비롯한 여럿에게 극찬을 받았으며, 기댓값 최대화 알고리즘을 통계분석의 중요한 도구로 자리매김하게 하였다.
이후 뎀스터-라드-루빈 논문의 알고리즘 수렴성 분석에 오류가 발견되었고, 1983년 C.F. 제프 우에 의해 옳은 증명이 제시되었다. 제프 우의 증명은 기댓값 최대화 알고리즘이 지수족뿐만 아니라 다른 확률분포에도 성립함을 보였다.
기댓값 최대화 알고리즘은 통계 모델의 수식을 정확히 풀 수 없을 때 최대가능도를 구하는 데 사용된다. 이런 통계 모델은 대개 잠재변수와 관측할 수 없는 모수, 관측된 데이터로 구성되어 있고, 몇몇 관측값들이 누락되어 있거나 관측되지 않은 데이터가 존재한다고 가정할 수도 있다. 예를 들면, 혼합 모델에서 매 관측값이 그에 상응하는 잠재변수 혹은 관측되지 않은 값을 가지고 있다고 가정할 수 있다.
최대가능도는 관측되지 않은 모든 변수 각각에 대하여 로그가능도를 미분한 식을 풀어서 구할 수 있다. 하지만 잠재변수를 포함하는 통계 모델의 수식들은 매우 복잡하여 이와 같은 방법으로는 풀 수 없다. 각각의 변수에 관해 미분한 식은 서로 얽혀있어 한 수식의 해를 구하기 위해서는 다른 식의 해를 구해야 하는데, 이 수식의 해 또한 이전 식의 변수를 포함하기 때문이다. 따라서 이 경우 정확한 해를 계산하는 것은 불가능하다.
하지만 기댓값 최대화 알고리즘을 이용하면 이 문제의 해를 수치적으로 계산할 수 있다. 우선 서로 얽혀있는 두 식과 각각의 변수들을 가정해보자. 두 식은 얽혀있기 때문에 한 식의 변수는 다른 식의 변수일 수 있다. 첫번째 식의 변수값을 임의로 잡은 후 이 변수값으로 두번째 식의 변수값을 추정한다. 그렇게 구한 변수값으로 다시 첫번째 식의 변수값을 추정하고 이를 반복한다. 특정한 상황에서 충분히 많은 반복을 거치면 각각의 변수들이 일정한 값으로 수렴한다는 것을 보일 수 있다. 또한, 이 값에서 로그가능도의 미분은 0이 됨을 보일 수 있고, 이는 이 값이 극점이거나 안장점임을 의미한다. 일반적으로 로그가능도는 여러 개의 극점을 가질 수 있으므로 기댓값 최대화 알고리즘이 반드시 최댓값을 구할 수는 없다. 어떤 가능도는 특이점, 즉 무의미한 극점을 갖기도 한다. 예를 들어, 혼합 모델에서 한 성분의 평균 매개변수를 관측된 하나의 데이터로 놓고 분산 변수를 0으로 설정할 때 발생하는 특이점이 기댓값 최대화 알고리즘으로 구해지는 해가 될 수 있다.
관측할 수 있는 확률변수 formula_1와 관측할 수 없는 확률변수 formula_2, 그리고 모수 formula_3가 있을 때, formula_4에 대한 확률분포는 formula_5로 주어져 있다. 이 때 최대가능도를 계산하고 싶은 경우, 최대화하려는 가능도 함수는 formula_6로 정의할 수 있다.
이 수식의 계산비용은 잠재변수 formula_2가 취할 수 있는 값의 수에 비례하고, formula_2의 차원이 증가할수록 취할 수 있는 값의 수는 지수적으로 증가하기 때문에 이 수식을 계산하기는 매우 어렵다.
기댓값 최대화 알고리즘은 다음 두 단계를 반복하여 가능도 함수 formula_9의 최대가능도를 구한다.
기댓값 (E) 단계에서는 formula_10가 주어지고 새로운 formula_3를 사용할 때 가능도의 기댓값 formula_12를 정의한다. 이 때 기댓값을 취하는 확률분포는 formula_1, formula_10가 주어졌을 때 formula_2의 조건부 분포이다.
최대화 (M) 단계에서는 formula_12를 최대화하는 새로운 모수 formula_18를 계산한다.
기댓값 최대화 알고리즘은 다양한 모델에 적용 가능하지만, 적용되는 모델은 일반적으로 다음 성질을 만족한다.모수 formula_3가 주어졌을 때, 잠재변수 formula_2에 관한 가능도 함수를 최대화함으로써 formula_2의 값을 어렵지 않게 추정할 수 있고, 반대로 잠재변수 formula_2의 값이 주어졌을 때, 모수에 관한 가능도 함수를 최대화함으로써 모수 formula_3의 값을 추정할 수 있다. 모수와 잠재변수 중 하나의 값을 알면 다른 값도 쉽게 알 수 있다는 것이 기댓값 최대화 알고리즘의 핵심이다. 다음은 기댓값 최대화 알고리즘을 간략히 요약한 것이다.이 알고리즘은 비용함수의 극대점으로 단조 수렴한다.
기댓값 최대화 알고리즘은 극대점을 찾기 때문에, 구한 값이 실제 최대점은 아닐 수 있다. 이를 피하기 위해 여러 개의 임의 초기값에 대해 계산하는 기법이나 담금질 기법 등이 같이 사용될 수 있다.
비록 EM을 반복하는 것이 관측된 데이터(한계) 기능도 함수를 증가시키지만 그 순열이 최대가능도로 수렴한다는 증거는 없다. 다항 분포에서는, EM 알고리즘이 초기값에 따라 관측된 데이터 가능도 함수의 극대값으로 수렴할 수도 있다. 경사 하강법(서로 다른 초기 추정량 formula_32에서 시작하는 방법)이나 담금질 기법 등 수 많은 체험적이거나 메타 발견적 학습 방법이 있다.
EM은 가능도가 지수족일때 특히 유용하다: E 단계는 충분 통계량()의 기대값들의 합이 되며, M 단계는 선형 함수를 최대화하는 것을 포함한다. 이런 경우에는, 각각의 단계에서 선드버그 공식을 이용하여 닫힌 해를 도출하는 것이 가능하다.
EM 방법은 뎀스터-라드-루빈 논문에서 베이즈 추론에서 최대 사후 확률을 계산하기 위해 변형되었다.
경사 하강법, 켤레기울기법, 또는 가우스-뉴턴 방법의 변형 등과 같은 최대가능도를 찾는 여러 방법들이 존재한다. EM과 달리, 이러한 방법들은 일반적으로 가능도 함수의 첫 번째와 두 번째 미분의 계산을 필요로 한다.
기댓값 최대화 알고리즘은 formula_33을 직접적으로 향상시키기 보다 formula_34를 향상시키는 일이다.
여기에서 증명하는 것은 formula_34를 향상시키는 formula_36를 찾으면 formula_33가 향상된다는 것이다.
확률이 0이 아닌 formula_38를 만족하는 어떤 formula_2에 대해서, 다음과 같이 이야기할 수 있다:
formula_41를 formula_2에 대해서 합한 값(혹은 적분한 값)을 양변에 곱할 수 있다. 좌변은 상수인 기댓값이므로:
여기에서, formula_44는 음수의 합(negated sum)으로 정의된다.
마지막 식은 formula_45인 경우를 포함해서 모든 formula_36에 대해서도 성립한다.
이전의 식으로부터 이 마지막 식을 빼면,
이다.
하지만, 깁스 부등식(Gibbs' inequality)에 의해서 formula_49이다.
그러므로, 우리는 다음 결론에 도달할 수 있다:
그러므로, formula_51에 비해서 formula_34가 커지도록 formula_36을 선택하면, 최소한 그 이상으로 formula_54에 비해서 formula_33가 향상될 것이다.
상황에 따라서는, 기댓값 최대화 알고리즘을 다음의 두 최대화 단계로 보는 것이 편리하다. "q"는 미관측 데이터 "z"를 나타내는 임의의 확률 분포, "p"(· |"x";"θ")는 관측 데이터 "x"가 주어졌을 때의 조건부 확률 분포, "H"를 엔트로피, 그리고 "D"를 쿨백-라이블러 발산이라고 할 때, 다음 식을 고려한다.
그러면 기댓값 최대화에서의 단계는 다음과 같이 나타낼 수 있다:
기댓값 최대화 알고리즘은 기계 학습과 컴퓨터 비전의 데이터 클러스터링에 자주 사용된다. 자연 언어 처리 분야에는 확률적 문맥 자유 문법()의 자율 유도를 위한 두 가지 중요한 알고리즘의 예로 바움-웰치 알고리즘()과 안밖 알고리즘()이 있다.
심리측정학에서 기댓값 최대화 알고리즘은 문항 반응 이론 모델의 아이템 매개변수와 잠재 능력의 추정을 위해 거의 없어서는 안된다.
기댓값 최대화 알고리즘은 누락된 데이터를 처리하고 미확인 변수를 관찰하는 능력이 있어 포트폴리오 리스크()의 가격을 정하고 관리하는 유용한 도구가 되고 있다.
기댓값 최대화 알고리즘은 또한 의학 영상 복원, 특히 양전자 방출 단층촬영과 단일광자방출단층활영()에 널리 쓰인다.
칼만 필터는 일반적으로 온라인 상태 추정에 사용되고 최소 분산 평활화는 오프라인 또는 배치() 상태 추정에 사용된다. 그러나 이러한 최소 분산 해법들을 위해서는 상태공간 모델의 매개변수 추정이 필요하다. 기댓값 최대화 알고리즘은 절리 상태()와 모수 추정 문제를 푸는데 사용될 수 있다.
기댓값 최대화 알고리즘의 필터링과 평활화는 아래의 두 단계를 반복함으로써 일어난다.
칼만 필터 또는 최소 분산 평활화가 하나의 입력을 받고 하나의 출력을 하는 시스템에서 잡음 섞인 측정을 한다고 가정하자. 최대가능도 계산으로부터 갱신된 측정 잡음 분산 추정을 얻을 수 있다.
이 때 formula_60는 N 스칼라 측정인 formula_61으로부터 필터 또는 평활화에 의해 계산된 스칼라 출력 추정이다. 비슷하게 1차 자기회귀 과정을 위해, 갱신된 과정 잡음 분산 추정이 다음과 같이 계산된다.
이 때 formula_60와 formula_64가 필터 또는 평활화에 의해 계산된 스칼라 상태 추정들이다. 갱신된 모델 계수 추정은 다음을 통해서 얻어진다.
위와 같은 모수 추정의 수렴에 대해서 잘 연구되어 있다.
기댓값 최대화 알고리즘의 때때로 느린 수렴을 가속화 하기 위해서 몇 가지 방법이 제시되어 왔다. 켤레기울기법을 사용하는 것과 수정된 뉴턴의 방법 기법들이 그 예다. 추가적으로 기댓값 최대화 알고리즘은 속박 추정 기법들과 함께 쓰인다.
조건부 기댓값 최대화(, 약자 ECM)는 각각의 M 단계를 각각의 매개변수 formula_66가 개별적으로 최대화 되고 조건부로 다른 매개변수들은 고정되는 조건부 최대화 (CM) 단계의 배열로 대체하였다.
이 아이디어는 후에 대체 설명에서 E 단계와 M 단계 모두에 대해서 손실 함수 "F"의 증가를 찾는 일반화된 기댓값 최대화(, 약자 GEM) 알고리즘으로 확장된다.
기댓값 최대화 알고리즘을 MM (Majorize/Minimize 또는 Minorize/Maximize, 문맥에 따라서) 알고리즘 의 하위 분류로 간주하는 것도 또한 가능하고 그러므로 더욱 일반적인 경우에 대해 개발된 어떤 기구를 사용하는 것이 가능하다.
기댓값 최대화 알고리즘에 사용되는 Q-함수는 로그가능도를 기반으로 하고 있다. 그러므로, log-EM 알고리즘으로 간주된다. 로그가능도의 사용은 α-로그가능도 비율로 일반화 될 수 있다. 그러면, 관찰된 데이터의 α-로그가능도 비율은 그것의 Q-함수와 α-발산을 사용한 등식으로 정확하게 표현된다. 이 Q-함수를 얻는 것은 일반화 된 E 단계이다. 그것의 최대화는 일반화된 M 단계이다. 이 두 단계를 α-EM 알고리즘
이라고 부르며 log-EM 알고리즘이 이에 하위 분류로 포함된다. 따라서, 야스오 마츠야마()의 α-EM 알고리즘은 정확히 log-EM 알고리즘의 일반화이다. 기울기 또는 Hessian 행렬의 계산이 필요 없다. α-EM은 알맞은 α를 선택함으로써 log-EM 알고리즘 보다 더 빠르게 수렴한다. α-EM 알고리즘은 은닉 마르코프 모델 추정 알고리즘 α-HMM 의 더 빠른 버전으로 이어졌다.
기댓값 최대화 알고리즘은 부분적으로 베이즈가 아닌 최대가능도방법이다. 최종 결과는 (베이즈 방식의) 잠재변수와 "θ" (최대가능도 또는 사후 최빈값() 중 하나)의 점추정에 대한 확률분포로 나타난다. 잠재변수처럼 "θ"에 대한 확률분포로 나타나는 완전한 베이즈 방식의 버전을 생각해 볼 수 있다. 추론을 위한 베이즈 방식의 접근법은 간단하게 "θ"을 다른 잠재변수와 같이 취급한다. 이 패러다임에선 E 단계와 M 단계의 구분이 없어진다. 만약 위에서 말한 변분 베이즈 근사법과 같이 인수분해된 Q 근사값을 사용하면, 각각의 잠재변수("θ"가 포함된)에 대해서 반복하고 한 번에 하나씩 최적화할 수 있다. 그러면 "k"가 잠재변수의 갯수라고 할 때, 한 번 반복할 때마다 "k" 단계들이 있다. 그래픽 모델()에서 앞의 방법은 각각의 변수의 새로운 "Q"를 마르코프 블랭킷()에만 의존시킴으로써 쉽게 만들 수 있어서, 국소 메시지 전달()이 효율적인 추론으로 사용될 수 있다.
정보 기하학()에서, E 단계와 M 단계는 이중 아핀 접속의 사영()으로 해석되고, e-연결()과 m-연결()로 불린다. 쿨백-라이블러 발산 또한 이 용어들을 사용해서 해석될 수 있다.
두 개의 formula_67차원 다변수 정규분포가 혼합되어 있는 경우, 보통 이 모델에서 formula_67차원 값을 수집하는 것은 가능하지만 그 값이 두 분포 중 어느 분포에서 나온 것인지는 알 수 없는 경우가 많다. 이 문단에서는 이러한 경우에 대한 기댓값 최대화 알고리즘을 유도한다.
전체 formula_69개의 점을 수집하였을 때, formula_70번째 수집되는 값은 formula_71로 나타낼 수 있다. 여기에서 formula_72는 formula_67차원 점을 가리키는 관측 가능한 변수, 그리고 formula_74는 두 개의 정규분포 중 어느 분포에서 수집되었는지를 가리키는 관측 불가능한 변수이다.
formula_70번째 값이 두 분포 중 어느 분포에서 수집되는지에 대한 확률은 formula_70와 독립적이기 때문에, formula_77는 formula_70에 관계없는 매개변수로 표현할 수 있다. 이 값을 formula_79인 벡터 formula_80로 표기하도록 한다(formula_81).
마지막으로, 두 다변수 정규분포를 각각 formula_82, formula_83로 표기하기로 한다.
즉,
그렇다면 이 모델에서 매개변수는 formula_86가 된다.
이제 가능도 함수 formula_87를 다음과 같이 표현할 수 있다:
불완전한 데이터 가능도 함수는
완전한 데이터 가능도 함수는
여기에서 formula_90는 지시 함수이고, formula_91는 다변수 정규분포의 확률 밀도 함수이다. 여기에서 formula_91를 풀어서 쓰면 다음과 같이 정리된다.
모수 formula_32에 대하여 formula_74에 대한 확률분포 formula_96는 다음과 같이 계산한다.
그러면 기댓값 단계의 formula_12 함수는 다음과 같이 계산된다.
이제 최대화 단계를 계산한다. formula_12 함수는 formula_101에 대한 식과 formula_102에 대한 식의 선형 결합이기 때문에, formula_101와 formula_102에 대해 독립적으로 최대화를 계산하는 것이 가능하다.
먼저 모수 formula_105는 다음과 같이 유도된다.
이 식은 이항분포에서의 최대가능도를 계산하는 경우와 동일하며, 따라서 다음과 같이 계산할 수 있다.
다음으로 formula_108에 대한 식은 다음과 같다.
이 식은 다변수 정규분포에서의 최대가능도를 계산하는 식과 유사하며, 다음과 같이 계산할 수 있다.
formula_112도 같은 방식으로 구할 수 있다.
반복과정은 각 과정에서 가능도 사이의 증가폭이 사전에 정의된 기준점 아래로 내려오면 종료한다.
즉, 사전에 정의된 기준점 formula_113에 대해서, formula_114이면 종료한다.
앞서 소개한 알고리즘은 두 개 이상의 다변수 정규 분포를 혼합한 경우에도 적용이 가능하다.
동일한 크기의 이미지 formula_115개가 주어졌을 때, 이를 formula_116라 하자. 각 이미지는 formula_117개의 픽셀로 이루어져 있고 각 픽셀은 formula_118 혹은 formula_119의 값을 가진다. 즉, formula_120이다. 또한 각각의 픽셀이 서로에 대해 조건부 독립적이라 가정하면, 성분 formula_121의 모든 이미지에 관한 픽셀 formula_70의 확률분포는 모수 formula_123를 갖는 베르누이 분포로 모델링 할 수 있다.
혼합 모델이 formula_124개의 군집(cluster)을 가진다고 가정할 때, 어떤 이미지가 군집 formula_70에 속해 있을 확률을 formula_126이라 하자. formula_127는 혼합 계수(mixing coefficient)라 불린다.
이 모델은 어떤 이미지가 특정 군집에 속할 확률변수와 그 군집에서의 픽셀 분포 변수를 모수로 갖는다. 즉, formula_128이고,
formula_129이다.
하나의 트레이닝 이미지(training image) formula_130에 관한 가능도 함수는 다음과 같다.
formula_131
이 때 formula_130가 군집 formula_121에 의해 생성되었을 확률은 다음과 같다.
formula_134
formula_124-차원 잠재변수 formula_136을 정의함으로써 주어진 이미지가 어떤 군집에 속할 확률을 모델링 할 수 있다. formula_137가 formula_119-of-formula_124 표기법으로 나타내어졌다고 하자. 즉,
formula_140에 대하여, formula_141이고, formula_142가 성립한다.
formula_137의 분포가 formula_144로 주어져 있다고 가정하자. 그러면 다음이 성립한다.
formula_145
또한, formula_146라 하면,
formula_147이다.
잠재변수 formula_137들을 포함하는 집합 formula_149를 정의하고 위 수식을 사용하면,
formula_150이 성립하고,
트레이닝 이미지의 집합 formula_151를 정의하면 formula_2에 관한 formula_1의 조건부 확률분포를 다음과 같이 유도할 수 있다.
formula_154
이제 위 수식들과 확률의 곱셈법칙을 이용하면 완전한 데이터 가능도()를 구할 수 있고,
formula_155
이에 로그함수를 취하면 완전한 데이터 로그가능도() formula_156가 유도된다.
formula_157
기댓값 단계에서 잠재변수의 값을 업데이트 하기 위해 formula_2의 확률분포를 formula_159이라 하자. 이 분포는 정확히 풀 수 없으므로 값을 추정해야 하는데, 이를 위해 현재 formula_160의 값을 이 변수의 기댓값으로 대체한다.
formula_161
이와 같이 formula_162의 값을 업데이트 하면 잠재변수 formula_163가 더 이상 formula_119-of-formula_124식으로 나타내어지지 않는다는 사실을 알 수 있다. 이는 이미지 formula_166이 하나의 군집이 아니라 여러 개의 군집에 부분적으로 속한다는 것을 의미한다.
이 모델의 모수들(혼합 계수 및 군집별 픽셀 분포 변수)을 최대화하기 위해 다음 식을 이용한다.
formula_167
formula_168
위 식을 formula_169에 관해 최대화하기 위해 미분하여 formula_118이 되는 값을 찾는다.
formula_171
이 때, formula_172는 군집 formula_173에 실질적으로 속한 이미지의 갯수이다.
군집 formula_173에서의 픽셀 분포의 매개변수 formula_175는 다음과 같이 나타낼 수 있다.
formula_176
formula_177는 군집 formula_173에 (실질적으로) 속한 이미지들의 가중 평균을 의미한다.
formula_179를 혼합 계수 formula_180와 조건 formula_181에 관해 최대화하기 위해 라그랑주 승수법(Lagrange Multiplier)을 이용한다.
formula_182
최댓값은 다음과 같이 구할 수 있다.
formula_183
formula_184
위 두 결과를 종합하면 formula_185이고,
formula_186이다.
베르누이 혼합 모델의 기댓값(E) 및 최대화(M) 단계의 수식들은 다음과 같다.
기댓값 단계(E step):
formula_187
최대화 단계(M step):
formula_188
formula_189
이 때, formula_190이고, formula_191이다.
EM은 극값으로만 수렴하고 일반적으로 수렴율에 대한 범위가 없다. 고차원에서 잘 작동하지 않고 극값의 수가 다수가 존재할 가능성이 있다. 따라서 특히 고차원 상에서 다른 학습 방법을 사용할 필요가 있다. 이 때 모멘트-기반 접근 방식이나 스펙트럼 기법이 더 좋은 효과를 보장한다. 모멘트-기반 접근은 확률 모형의 매개변수를 학습하기 위한 것으로 최근 들어 사용이 많아지기 시작했는데, 이는 EM이 극값만을 보장해주는 것에 반해 모멘트-기반 접근은 최대, 최솟값을 보장하기 때문이다. 혼합 모형, 은닉 마르코프 모델, 공동체 모델 등으로부터 학습을 보장하는 알고리즘들이 유도될 수 있다. 이 스펙트럼 방법들은 잘못된 극값을 찾아내지 않고, 모수의 참값을 특정 제약 조건 하에서 일관적으로 도출시킨다.
EM 알고리즘은 MM 알고리즘 의 특수한 형태로 볼 수 있다.