기대-최대화(EM) 알고리즘은 통계학과 머신러닝에서 관찰되지 않은 잠재 변수에 의존하는 통계 모델의 최대 우도 또는 최대 사후 확률 추정치의 국소 최대값을 찾는 반복적 방법입니다. EM은 기대(E) 단계와 최대화(M) 단계를 번갈아 수행하는데, E 단계는 현재 매개변수 추정치를 사용하여 기대 로그 가능도에 대한 함수를 계산하고, M 단계는 기대 로그 가능도를 최대화하도록 매개변수를 갱신한다. 갱신된 추정치는 다음 E 단계에 사용되며, 수렴할 때까지이 과정을 반복합니다.
머신러닝에서 EM은 데이터가 불완전한 모델(혼합 모델(예: 가우시안 혼합 모델)이나 숨은 마르코프 모델)을 위한 핵심 도구이다. EM은 군집화, 이미지 분할, 확률적 그래픽 모델을 위한 매개변수 추정에 응용되며, 심층 생성 모델에서 사용되는 더 고급 변분 추론의 기초 역할을 합니다.
역사
EM 알고리즘은 1977년 아서 뎀프스터, 낸 레어드, 도날드 루빈의 논문에서 공식적으로 명명되고 설명되었지만, 그 알고리즘은 이전에 특정 사례에서 제안되었었다. 세드릭 스미스는 유전자 개수 세활용하여 대립 유전자 빈도를 추정하였고, H.O. 하틀리가 1958년 관련 접근을 도입했으며, 이후 하틀리와 Hocking가 1977년에 이를 확장하면서 핵심 개념을 제공했습니다. 롤프 순드베리가 지수족에 대해 상세한 해법을 개발했고, 페르 마르틴-뢰프와 안데르스 마틴-로프에 의해 영향을 받았다. 뎀피스-레이드-루빈 논문은 이 방법을 더 포괄적인 클래스로 일반화하고 확장했지만, 그 수렴 증명은 결점이 있었습니다. 씨. F. 제프 우가 1983년에 수정된 수렴 분석을 제공하여 EM의 유효성을 지수족 밖에서도 확립하였다. 그 이후 알고리즘은 통계 분석의 표준이 되었다. 그리고 멩과 반 다이크(1997)와 같은 후속 연구가 그것을 더욱 정제했다.
알고리즘 단계
EM 알고리즘은 우도 함수에 잠재 변수가 포함되어 직접 도함수 기반 최대화가 불가능한 최적화 문제를 해결한다. 그 대신에, 알고리즘은 연동 방정식을 반복적으로 해결합니다: 즉, 매개변수는 설정 변수에 의존하고, 잠재 변수는 매개변수에 의존한다, 이 때문에 대입 시 방정식이 풀리지 않는 경우가 많다.
EM은 두 단계를 번갈아 수행하며 이 순환을 깨뜨립니다:
- E 단계: 이전 반복의 현재 매개변수 추정치가 주어졌을 때, 관측 데이터에 조건화된 잠재 변수의 분포에 대한 로그-가능도의 기대값을 계산한다.
- M 단계: 기대 로그-가능도를 매개변수에 대해 최대화하여, 관측 데이터의 가능도를 증가시키거나 그대로 유지(비감소)가 보장되는 새로운 추정치를 만들어낸다. 이것은 수렴 될 때까지 반복한다.
모델에 독립적인 잠재변수가 있다면, E-단계는 잠재 변수의 최대 사후 확률 추정치를 찾는 것으로 단순화되며, 종종 숨은 마르코프 모델을 위해비터리 알고리즘과 같은 방법을 사용한다. 전체 프로세스는 결국 주별 가능도의 지역 최대값에 도달한다, 그러나 전역 최적값을 보장하지 않으며 지역 최대만 보장합니다. 혼합 모델에서, 이 절차는 구성 요소에 있어 하나가 분산이 0이고 그 평균이 데이터 포인트와 일치하는 특이점이 발생하는 곳의 해로 수렴할 수 있습니다.
적용 분야
EM은 추정된 가우시언 혼합에 대한 응용과 몇 변수 누락이 있는 데이터를 해결하는 다중 선형 회귀 문제 해결에 사용된다. 머신러닝에서는, 클러스터링을 위한 가우시안 혼합 모델을 포함한 잠재 변수 모델의 기대 최대화 중요 구성 요소로, scikit-learn 및 다른 라이브러리에 구현되어 있습니다. 또한 마르크 체인을 위한 텍스트 시퀀스나 컴퓨터 비전의 이미지 분할에 대한 알고리즘의 기반을 만듭니다.
이 방법은 베이지안 네트워크 및 확률적 그래픽 모델과 같은 분야에 채택되었으며, 마이클 조던와 다프네 콜러 같은 인물이 구조화된 모델에 적용했습니다. 현대적 설정에서, EM은 그래프코어 모델에서의 반복 최적화를 위한 이론적 기반 역할하지만, 심층 신경망은 종종 그라디언트 기반 방법을 대신 사용합니다.
변형과 확장
여러 변형이 기본 EM보다 향상합니다. 일반화 EM(GEM)은 기대 로그 세대를 최대화하는 것보다는 증가시키는 매개변수를 찾는 것으로 M-단계를 완화한다. 기대 조건부 최대화(ECM)는 M-단계를 더 간단한 하위 단계로 분리하여 제약 조건이 있는 매개변수 유용해진다. 몬테카로 EM은 기대 로그가능을 해석적으로 계산할 수없는 때 E-단계에 해결에 샘플링(예들랜덤 마르코브 체인 몬테카로)을 사용한다. 이들 변형은 EM의 핵심 경고함을 유지하면서도 특정 계산비용 과제를 해결합니다.
생성형 AI에서, EM의 아이디어는 잠재 표현이 있는 모델의 학습에 나타나지만, 생성 모델(생성 AI)은 현재 신경망에 적합한 빈도주의 또는 확률적 접근 방식에 의존하고 있다.
제한 및 고려 사항
EM은 전역 최대치에 도달할 것을 보장하지 않으며, 지역 최, 사인지점에서 멈출 수 있다. 그것은 초기화에 민감할 수 있으며, 어떤 경우에는 해에 인 헐스 특이성이 있습니다. 또한, E-단계는 복잡한 모델에 대해 계산 불가능이 될 기대 로그가능을 계산할 수 있다고 가정합니다. 이때 변분 추론(근사 추론을 위한 대안) 또는 결합 방법 같은 변형이 적합할 수 있습니다. 현대 ML 환경에서 전문가들은 그 단순성 때문에 EM에 의존하는 경우가 많지만, 딥 GP 모델이나 신경망의 경우 그라디언트 기반 최적화를 선호합니다.
같이보기
- 머신러닝
- 딥러닝
- 인공지능
- 카네기 멜른 대학교 (ML연구)
참고 문헌
- Dempster, A. P.; Laird, N. M.; Rubin, D. B. (1977). "Maximum Likelihood from the Missing Data via the EM Algorithm" 저널 of the Royal Statistical Society.
- Wu, C. F. J. (1983). EM 알고리즘의 수렴 성질에 대하여. Annals of Statistics.
- Hartley, H. O. (1958). 불완전 데이터의 최대 우도 추정. Biometrics.
{, "infobox": {"type": "algorithm", "introduced": "1977", "introduced_by": "Arthur Dempster, Nan Laird, and Donald Rubin", "related": ["machine-learning", "artificial-intelligence", "deep-learning"]}, ", "categories": ["statistical-algorithms", "machine-learning", "latent-variable-models","optimization-methods"]}