기대 극대화는 60 년대와 70 년대에 다양한 애플리케이션으로 개발 된 고전적인 알고리즘입니다. 이것은 수학적으로 정확한 유형 계층구조인,강력한 타입을 정의합니다. 최적화 절차로서,많은 상황에서 업데이트를 분석적으로 계산할 수 있다는 주요 이점을 가진 그라디언트 디센트 등의 대안입니다. 그 이상,그것은 최적화에 대해 생각을위한 유연한 프레임 워크입니다.
이 기사에서는 간단한 클러스터링 예제로 시작한 다음 일반적인 알고리즘에 대해 설명합니다.
측정값과 함께 다양한 데이터 포인트가 있는 상황을 고려하십시오. 우리는 다른 그룹에 할당 할.
예제에서 여기에 우리는 옐로 스톤의 상징적 올드 페이스 간헐천의 폭발에 대한 데이터를 가지고있다. 각 분화에 대해 우리는 그 길이와 이전 분화 이후의 시간을 측정했습니다. 우리는 분출의 두 가지”유형”(다이어그램에서 빨간색과 노란색)이 있다고 가정 할 수 있으며,각 유형의 분출에 대해 결과 데이터는(다변량)정규 분포에 의해 생성됩니다. 이 가우스 혼합물 모델이라고,부수적으로.
케이-의미 클러스터링과 유사하게,우리는 그 두 분포/클러스터가 무엇인지에 대한 무작위 추측으로 시작한 다음 두 단계를 번갈아 반복하여 개선을 진행합니다:
- (기대)각 데이터 포인트를 확률 적으로 클러스터에 할당하십시오. 이 경우 빨간색 클러스터와 노란색 클러스터에서 각각 나올 확률을 계산합니다.
- (최대화)클러스터의 점을 기반으로 각 클러스터의 매개 변수(가중 평균 위치 및 분산-공분산 행렬)를 업데이트합니다(첫 번째 단계에서 할당 된 확률에 의해 가중됨).
와는 달리 케이-의미 클러스터링,우리의 모델은 생성 적입니다. 그리고 모델을 다시 샘플링하여 더 많은(가짜)데이터를 생성 할 수 있습니다.
알았어? 이제 우리는 방정식으로 1 차원 예제를 할 것입니다.
단일 측정으로 데이터 포인트를 고려하십시오 엑스. 첫 번째 클러스터에서 데이터가 생성될 확률은 0 입니다.
그래서 우리는 5 개의 매개 변수를 가지고 있습니다: 혼합 확률 π,및 평균 μ 및 표준 편차 σ 각 클러스터입니다. 나는 그것들을 집합 적으로 다음과 같이 나타낼 것이다.
전체 데이터 세트를 관찰 할 확률(우도)엔 포인트는:
그리고 우리는 일반적으로 우리의 제품을 더 관리하기 쉬운 합계 인 로그 우도로 바꾸기 위해 이것의 로그를 취하기로 선택합니다.
우리의 목표는 이것을 극대화하는 것입니다:우리는 우리가 관찰 한 데이터(최대 우도 추정기)를 관찰 할 가능성이 가장 높은 매개 변수가되기를 바랍니다.
이제 문제는 어떻게 최적화 할 것인가? 직접 및 분석적으로 수행하는 것은 로그의 합계 때문에 까다로울 것입니다.
트릭은 우리가 호출 할 잠재 변수가 상상하는 것입니다. 점이 클러스터 1 또는 클러스터 2 에 있는지 여부를 결정하는 이진(0/1 값)변수입니다. 우리가 각 점에 대해 0 을 알고 있다면 매개 변수의 최대 우도 추정치를 계산하는 것은 매우 쉽습니다. 편의를 위해 두 번째 클러스터에 대한 우리의 선택 인 1 과 일치하기 위해,우리는 두 번째 클러스터에있는 지점의 확률로 전환 할 것입니다.
합계가 이제 로그 외부에 있음을 알 수 있습니다. 또한,우리는 각각의 관찰 가능성을 설명하기 위해 추가 합계를 선택합니다.
우리가 제 2 차 세계 대전을 관찰했다고 역으로 가정하면,최대 우도 추정치는 쉽게 형성 될 수 있습니다. 각 군집 내의 표본 평균을 취한다. 두 번째 클러스터에 있는 점의 표본 비율입니다. 이들은 각 모수에 대한 일반적인 최대 우도 추정기입니다.
물론,우리는 관찰하지 않았다. 이 솔루션은 기대 극대화 알고리즘의 핵심입니다. 우리의 계획은:
- 임의의 초기 매개 변수 선택으로 시작하십시오.
- (기대치)의 추정치를 형성한다.
- (최대화)최대 우도 추정기를 계산하여 모수 추정치를 업데이트합니다.
- 2 단계와 3 단계를 반복하여 수렴합니다.
다시 말하지만,케이-우리가 같은 일을하는 클러스터링을 의미합니다. 에 케이-의미 클러스터링,각 점을 가장 가까운 중심(기대 단계)에 할당합니다. 본질적으로,이것은 하드 추정치입니다. 이 때문에 하드 1 클러스터 중 하나와 0 모든 다른 사람에 대한. 그런 다음 우리는 클러스터(최대화 단계)의 점의 평균으로 중심점을 업데이트합니다. 이것은 최대 우도 추정기입니다. 에 케이-의미 클러스터링,데이터에 대한”모델”에는 표준 편차가 없습니다. (“모델”은 생성 적이 아니기 때문에 겁 따옴표에 있습니다).
이 예제에서는 대신 소프트 할당을 수행합니다. 우리는 때때로 이것을 책임(각 관찰에 대한 각 클러스터의 책임)이라고 부릅니다. 우리는 책임을 다음과 같이 나타낼 것입니다.
이제이 예제에 대한 전체 알고리즘을 작성할 수 있습니다. 그러나 그렇게하기 전에 우리가 정의한 기호 테이블을 신속하게 검토 할 것입니다(많이있었습니다).
여기 알고리즘이 있습니다:
에 대한 기대 최대화 알고리즘은 클러스터 1 에 대한 추정치와 클러스터 1 에 대한 추정치는 유사하지만 대신 가중치로 1-10 을 사용한다는 점에 유의하십시오.
이제 우리는 알고리즘의 예를 제공 한 것을,당신은 희망에 대한 느낌이. 우리는 일반적으로 알고리즘을 논의로 이동합니다. 이것은 기본적으로 우리가 약간 더 복잡한 변수로 한 모든 것을 차려 입는 것입니다. 그리고 그것이 왜 작동하는지 설명 할 수있는 위치에 우리를 넣을 것입니다.
일반적으로 기대 최대화
일반 설정으로 이동해 보겠습니다. 다음은 설정입니다:
- 우리는 어떤 형태의 데이터를 가지고 있습니다.
- 우리는 어떤 형태로든 관찰되지 않은(잠재 된)데이터도 있다고 가정합니다.
- 우리는 매개 변수가있는 모델을 가지고 있습니다.
- 우리는 로그 우도를 계산할 수있는 능력을 가지고 있습니다. 특히,우리의 데이터와 매개 변수를 주어진 잠재 변수의 지정된 할당을 관찰 할 확률의 로그.
- 우리는 또한 조건부 분포를 계산하기 위해 모델을 사용할 수있는 능력을 가지고 있습니다. 이 문제를 해결하려면 다음 단계를 수행해야합니다.
- 결과적으로 우리는 로그 우도를 계산할 수 있습니다. 이것은 매개 변수가 주어진 데이터를 관찰 할 확률의 로그입니다(잠재 변수에 대한 할당을 가정하지 않고).
사용 피 확률을 나타 내기 위해,우리는 지금 쓸 체인 규칙을 사용할 수 있습니다:
표기법은 여기에서 미묘 할 수 있습니다. 세 용어 모두 주어진 매개 변수를 사용합니다.
- 왼쪽의 첫 번째 항은 데이터와 지정된 잠재 변수 할당을 관찰 할 확률입니다.
- 우측의 첫 번째 항은 관찰된 데이터가 주어진 잠재 변수의 지정된 할당 확률이다.
- 마지막 항은 데이터를 관찰 할 확률입니다.
우리는 로그를 취하고 항을 재 배열 할 수 있습니다. 그런 다음 두 번째 줄에서 우리는 표기법 변경(그리고 혼란스러운 것)을 만들 것입니다. 나를 비난하지 마라,나는 그것을 발명하지 않았다):
처음 두 용어에 대해서는 이전 예제의 컨텍스트에서 해당 용어가 무엇인지 검토해 볼 가치가 있습니다. 첫 번째,2018 년 10 월 1 일(2018 년 10 월 1 일),우리가 최적화 할 것입니다. 두 번째,ℓ(θ,X,Δ),었다는 분석적으로 다루기 쉬워졌다.
이제 조건부 분포를 계산할 수 있다고 말한 것을 기억하십시오. 상황이 야생 얻을 곳이다.
우리는 동일한 매개 변수의 두 번째 세트를 소개 할 것입니다. 나는 또한 때때로이”제 2 의”가 가지고있는 것과 같이 그 위에 모자(곡절)로 나타낼 것입니다.2 이 매개 변수 집합을 현재 추정치로 생각하십시오. 현재 우리의 공식에있는 제 2 차 세계 대전은 우리의 견적을 향상시키기 위해 최적화 될 것입니다.
이제 우리는 조건부 분포에 대한 로그 우도의 기대를 취할 것입니다.
왼쪽에있는 용어는 어쨌든(상수)에 대해 알고/신경 쓰지 않기 때문에 변경되지 않습니다. 다시 말하지만,기대는 가능한 값 위에 있습니다. 만약 당신이 우리의 예에 관하여 다음과 같이 하는 경우,용어 2018(2018)는 우리가 기대를 취한 후에 2018(2018)으로 대체되도록 2018(2018)으로 변경됩니다.
자,아주 빨리,우리가 여기서 진행하고있는 표기법의 악몽을 개선하기 위해,우리가 오른쪽에 가지고있는 두 가지 기대치에 대한 속기 표기법을 소개합시다
알고리즘은 다음과 같습니다:
작동 이유
이것이 작동한다는 것을 증명하기 위해 드는 무거운 것은 함수를 고려하는 것입니다. 클레임 R 극대화할 때 θ=θʹ. 전체 증거 대신에 무엇을 연구 계산에 대해 생각해 봅시다. 데이터에 대한 의존도를 제거 엑스(이는 우리가 기대하고있는 분포와 우도 함수 사이에서 공유 됨),아르 자형 개략적으로
즉,우리는 두 가지 확률 분포가 있습니다. 우리는 하나를 사용하여(에 의해 매개 변수화 됨)데이터를 생성 할 수 있습니다. 만약 0 이 단지 하나의 숫자를 나타내고 분포가 확률 밀도 함수를 가지고 있다면,우리는(다시,개략적으로)쓸 수 있습니다)
함수에 대한 암시적인 개략적 형태 아르 자형 특별한 경우
나는 이것을 두 확률 분포 사이의 거리를 거의 측정 한 쿨백-라이블러(케이엘)발산과 유사한 형태로 암시 적으로 작성했습니다. 우리가 빼면 아르 자형(큐||피)상수에서 아르 자형(피//피)우리는 얻을 것이다 케이엘-발산 0 에서 아래에 묶여 있고 0 때 큐=피.(유일한 것은 거리 3 0 분포에서 피 이다 피 자체). 즉,아르 자형 이다 최대화 때 큐=피.이것은 표준 결과입니다클-발산 젠슨의 불평등으로 입증 될 수 있습니다.4
이제 남은 것은 업데이트 단계 전후의 우도 간의 차이를 고려하는 것입니다:
이후 가능성 개선 위의 인수에 의해 아르 자형 이전 매개 변수를 첫 번째 인수로 취함으로써 최대화되므로 두 번째 항은 음수 여야합니다. 양수 마이너스 음수는 양수입니다. 따라서 각 업데이트 단계에서 가능성이 증가했습니다. 각 단계는 일을 더 좋게 만들기 위해 보장됩니다.
또한 큐를 최적화 할 필요가 없습니다. 우리가해야 할 일은 더 나은 만들 수있는 몇 가지 방법을 찾아 우리의 업데이트는 여전히 일을 더 좋게 만들기 위해 보장됩니다.
결론
희망,당신은 지금 알고리즘에 대한 좋은 느낌을 가지고있다. 수학의 관점에서,핵심 방정식은 아래의 우도 일뿐입니다. 그 후,우리는 이전 매개 변수(기대 단계)에 대한 기대치를 취하고 오른쪽의 첫 번째 항을 최적화하는 것이 괜찮다는 것을 보여줍니다. 우리가 가우스 혼합 모델 예제와 동기 부여,이 두 번째 용어는 종종 쉽게 최적화 할 수 있습니다. 세 번째 용어는 우리가 걱정할 필요가 없습니다,그것은 아무것도 엉망 하지 않습니다.
조금 뒤로 물러서서,나는 엠 알고리즘의 힘과 유용성을 강조하고 싶다. 우선,잠재 변수를 도입 한 다음 잠재 변수(매개 변수를 고정 및 알려진 것으로 간주)와 매개 변수(잠재 변수를 고정 및 알려진 것으로 간주)를 교대로 처리하여 계산할 수 있다는 아이디어를 나타냅니다. 이것은 다양한 상황에서 볼 수있는 강력한 아이디어입니다.
둘째,알고리즘은 컴퓨팅 그라디언트에 의존하지 않기 때문에 본질적으로 빠릅니다. 선형 회귀를 사용하는 것과 같이 분석적으로 모델을 해결할 수있을 때마다 더 빠를 것입니다. 그리고 이것은 우리가 분석적으로 다루기 어려운 문제를 가지고 분석적으로 그 부분을 해결할 수있게 해주 며,그 힘을 반복적 인 맥락으로 확장시킵니다.
마지막으로,나는 엠 알고리즘에 대해 할 말이 많이있다 주목하고 싶다. 그것은 최대화 단계 및 변분 베이지안 기술을 수행하는 다른 형태로 일반화되며 다른 방식으로 이해 될 수 있습니다(예:최대화-최대화 또는 통계적 매니 폴드에서 상호 이중 아핀 연결 아래에서 서브 매니폴드에 대한 교대 투영(전자-및 미디엄-연결)). 미래에 더 많은 것!