13장 - EM 알고리즘

13장. EM 알고리즘

이번 장에서는 비지도 학습의 세계로 들어간다. K-평균 클러스터링으로 시작하여, 가우시안 혼합 모델과 이를 학습하기 위한 기대값-최대화(EM) 알고리즘을 다룬다. EM 알고리즘이 단순한 직관적 아이디어에서 출발하지만, 옌센 부등식을 통해 엄밀하게 유도될 수 있음을 보인다.

13.1 비지도 학습으로의 전환

지금까지는 지도 학습 알고리즘에 많은 시간을 할애했다. 양성 예제와 음성 예제가 주어지면, 로지스틱 회귀나 SVM 같은 알고리즘으로 결정 경계를 찾는 것이었다.

비지도 학습에서는 레이블이 없는 데이터만 주어진다. 입력 \(x\)와 출력 \(y\)가 함께 주어지는 대신, \(x\)만 주어진다. 훈련 세트는 다음과 같은 형태다.

\[\{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}\]

이 데이터에서 무언가 흥미로운 구조를 발견하는 것이 목표다.

13.2 K-평균 클러스터링

비지도 학습의 첫 번째 알고리즘은 클러스터링이다. 데이터가 주어졌을 때, 알고리즘이 스스로 데이터 안에 별개의 군집이 존재한다는 사실을 파악하도록 한다.

활용 사례: 시장 세분화

클러스터링의 가장 흔한 활용 중 하나는 시장 세분화다. 온라인 쇼핑 사이트의 사용자 데이터베이스에 클러스터링을 적용하면, 연령대, 성별, 교육 수준, 거주 지역 등에 따른 다양한 시장 세그먼트를 발견할 수 있다. 이를 통해 각 그룹에 맞춘 마케팅 캠페인을 설계할 수 있다.

알고리즘의 동작

K-평균 알고리즘의 동작 과정을 살펴보자. 레이블 없는 데이터가 2차원 평면에 흩어져 있다고 하자. 이 데이터에서 두 개의 군집을 찾고 싶다.

초기화: 두 개의 점을 선택한다. 이 점들을 **군집 중심(cluster centroid)**이라 부르며, 찾으려는 두 군집의 중심에 대한 최선의 추측이다.
반복: 수렴할 때까지 다음 두 단계를 반복한다.
- 할당 단계: 각 훈련 예제를 살펴보고, 더 가까운 군집 중심에 따라 빨간색 또는 파란색으로 칠한다.
- 업데이트 단계: 같은 색으로 칠해진 모든 점의 평균을 구하고, 해당 군집 중심을 그 평균 위치로 이동한다.

이 두 단계를 반복하면, 어느 시점에서 더 이상 변화가 없게 된다. 점을 다시 칠해도 색이 바뀌지 않고, 군집 중심을 다시 계산해도 위치가 변하지 않는다. 이때 알고리즘이 수렴했다고 한다.

수학적 정의

데이터셋에 레이블이 없으므로, 훈련 세트는 \(\{x^{(1)}, x^{(2)}, \ldots, x^{(m)}\}\)이다.

1단계: 군집 중심 \(\mu_1, \mu_2, \ldots, \mu_k\)를 무작위로 초기화한다.

실무에서 가장 흔한 초기화 방법은 완전히 랜덤한 벡터를 고르는 것이 아니라, 훈련 세트에서 \(k\)개의 예제를 무작위로 선택하여 군집 중심의 초기값으로 설정하는 것이다. 고차원 데이터에서는 이 방법이 특히 효과적이다.

2단계: 수렴할 때까지 반복한다.

각 \(i\)에 대해, \(c^{(i)}\)를 \(x^{(i)}\)에 가장 가까운 군집 중심의 인덱스로 설정한다:

\[c^{(i)} := \arg\min_j \|x^{(i)} - \mu_j\|^2\]

각 \(j\)에 대해, \(\mu_j\)를 군집 \(j\)에 할당된 모든 점의 평균으로 갱신한다:

\[\mu_j := \frac{\sum_{i: c^{(i)}=j} x^{(i)}}{\sum_{i} \mathbf{1}\{c^{(i)}=j\}}\]

여기서 거리 측정에는 L2 노름을 사용한다. L2 노름의 제곱을 사용해도 결과는 동일한데, 최소화의 대상이 되는 값의 크기 순서가 바뀌지 않기 때문이다.

비용 함수와 수렴 증명

K-평균의 비용 함수(왜곡 함수라고도 부른다)는 다음과 같다.

\[J(c, \mu) = \sum_{i=1}^{m} \|x^{(i)} - \mu_{c^{(i)}}\|^2\]

이 비용 함수는 각 점과 그 점이 할당된 군집 중심 사이의 제곱 거리의 합이다. K-평균의 매 반복은 이 비용 함수를 감소시킨다. \(J\)는 항상 0 이상이므로(제곱 거리의 합이므로), 매 반복마다 감소하는 음이 아닌 함수는 결국 수렴해야 한다.

실무에서 매우 큰 데이터셋에 K-평균을 실행할 때는, \(J\)가 감소하는 속도가 너무 느려지면 완전한 수렴을 기다리지 않고 적당한 시점에서 중단하기도 한다.

K의 선택

K-평균에서 가장 자주 받는 질문은 "K를 어떻게 선택하는가?"이다. 비지도 학습에서는 올바른 군집 수가 본질적으로 모호한 경우가 많다. 같은 데이터를 보고 어떤 사람은 두 개의 군집을, 다른 사람은 네 개의 군집을 볼 수 있다.

AIC나 BIC 같은 자동 선택 기준이 존재하지만, 실무에서는 하류 응용의 목적에 따라 K를 결정하는 것이 더 효과적이다.

시장 세분화: 마케팅 팀이 4개의 캠페인을 감당할 수 있다면 K=4를, 100개의 캠페인은 관리할 수 없다면 K=100은 피한다.
이미지 압축: 이미지를 얼마나 압축하고 싶은지에 따라 색상 군집 수를 결정한다.
뉴스 기사 그룹화: 뉴스 기사에 대해 의미 있는 군집 수가 어느 정도인지 판단한다.

지역 최솟값 문제

K-평균은 지역 최솟값에 빠질 수 있다. 이를 완화하기 위해, 서로 다른 랜덤 초기화로 K-평균을 10회, 100회, 또는 1,000회 실행한 뒤, 비용 함수 \(J\)가 가장 낮은 결과를 선택하는 방법을 사용한다.

13.3 밀도 추정과 이상 탐지

클러스터링과 밀접하게 관련되어 있지만 상당히 다른 문제가 **밀도 추정(density estimation)**이다.

이상 탐지의 동기

항공기 엔진이 조립 라인에서 나올 때마다 진동과 열 방출에 관한 특성을 측정한다고 하자. 데이터를 2차원 평면에 표시하면, 대부분의 엔진은 특정 영역에 밀집해 있다. 새로운 엔진이 조립 라인에서 나왔을 때, 그 진동-열 특성 조합이 기존 데이터와 크게 다르다면, 이 엔진은 **이상(anomaly)**일 가능성이 높다. 엔진을 출하하기 전에 추가 점검을 실시해야 한다.

이상 탐지의 핵심은 \(p(x)\)를 모델링하는 것이다. 모든 훈련 데이터가 주어졌을 때, 데이터가 추출된 확률 밀도 함수를 추정한다. 새로운 예제 \(x\)에 대해 \(p(x)\)가 매우 작으면 이상으로 판별한다.

\[p(x) < \epsilon \implies \text{이상 탐지}\]

이상 탐지의 응용

제조업: 항공기 엔진, 반도체 등 제품의 품질 검사
통신 네트워크: 기지국의 네트워크 패턴이 비정상적이면 기술자 파견
컴퓨터 보안: 특정 컴퓨터가 평소와 다른 비정상적 네트워크 트래픽을 발생시키면 해킹 의심

복잡한 분포의 문제

흥미로운 점은, 진동과 열 각각의 값은 정상 범위 안에 있더라도, 그 조합이 비정상적일 수 있다는 것이다. 예를 들어 데이터가 L자 형태로 분포하는 경우, 단일 가우시안이나 단순한 지수족 분포로는 이를 모델링할 수 없다.

이 문제를 해결하기 위해 **가우시안 혼합 모델(Mixture of Gaussians)**을 도입한다.

13.4 가우시안 혼합 모델

L자 형태의 데이터 분포를 보고, "이 데이터는 실제로 두 개의 가우시안에서 나온 것 같다"고 생각해 보자. 한 가지 유형의 항공기 엔진은 아래쪽 가우시안에서, 다른 유형은 위쪽 가우시안에서 추출된 것이다. 두 가우시안이 합쳐져 L자 형태의 영역에 높은 확률 밀도를, 그 바깥에는 낮은 확률 밀도를 부여한다.

1차원 예시를 통한 직관

이해를 돕기 위해 \(x \in \mathbb{R}\)인 1차원 예시를 살펴보자. 수직선 위에 데이터 점들을 표시하면, 왼쪽에 밀집된 그룹과 오른쪽에 밀집된 그룹이 보인다. 이 데이터는 두 개의 가우시안에서 나온 것 같다.

만약 어떤 예제가 가우시안 1에서, 어떤 예제가 가우시안 2에서 왔는지 알고 있다면, 각 가우시안을 해당 데이터에 피팅하면 끝이다. 전체 밀도는 왼쪽에 높고, 가운데가 낮고, 오른쪽에 다시 높은 쌍봉 형태가 된다.

문제는 어떤 예제가 어떤 가우시안에서 왔는지 모른다는 것이다. EM 알고리즘이 바로 이 문제를 해결한다.

모델 정의

잠재 변수(latent variable) \(z\)를 도입한다. "잠재"란 숨겨져 있거나 관측되지 않는다는 뜻이다. 존재하지만 직접 그 값을 볼 수 없다.

\(x^{(i)}\)와 \(z^{(i)}\)의 결합 분포를 다음과 같이 정의한다.

\[z^{(i)} \sim \text{Multinomial}(\phi)\]

\[x^{(i)} \mid z^{(i)} = j \sim \mathcal{N}(\mu_j, \Sigma_j)\]

두 가우시안의 혼합이라면 \(z\)는 단순히 베르누이 분포를 따르고, \(k\)개의 가우시안 혼합이라면 \(z\)는 1부터 \(k\)까지의 값을 취하는 다항 분포를 따른다. \(z^{(i)} = j\)라는 것을 알면, \(x^{(i)}\)는 평균 \(\mu_j\), 공분산 \(\Sigma_j\)인 가우시안에서 추출된다.

가우시안 판별 분석과의 비교

이 모델은 가우시안 판별 분석(GDA)과 매우 유사하다. 차이점은 두 가지다.

값의 범위: GDA에서 레이블 \(y\)는 두 값만 취했지만, 여기서 \(z\)는 1부터 \(k\)까지의 값을 취한다.
공분산 행렬: 관례적으로 가우시안 혼합 모델에서는 각 가우시안이 자체 공분산 행렬 \(\Sigma_j\)를 갖는다.

가장 중요한 차이점은, GDA에서는 레이블 \(y^{(i)}\)가 관측 가능했지만, 여기서 \(z^{(i)}\)는 잠재 변수로서 훈련 세트에서 볼 수 없다는 것이다.

\(z\)를 알고 있다면

만약 \(z^{(i)}\)의 값을 알고 있다면, 최대 우도 추정(MLE)을 사용하여 모든 매개변수를 추정할 수 있다.

\[\ell(\theta) = \sum_{i=1}^{m} \log p(x^{(i)}, z^{(i)}; \theta)\]

미분을 취하고 0으로 놓으면, 다음과 같은 추정값을 얻는다.

\[\phi_j = \frac{1}{m} \sum_{i=1}^{m} \mathbf{1}\{z^{(i)} = j\}\]

\[\mu_j = \frac{\sum_{i=1}^{m} \mathbf{1}\{z^{(i)} = j\} \cdot x^{(i)}}{\sum_{i=1}^{m} \mathbf{1}\{z^{(i)} = j\}}\]

이것은 GDA에서 \(y\)를 \(z\)로 대체한 것과 정확히 같은 공식이다. \(\Sigma_j\)에 대한 공식도 유사하게 유도된다.

하지만 \(z\)의 값을 모르기 때문에 이 공식을 직접 사용할 수 없다.

13.5 EM 알고리즘: 가우시안 혼합 모델

EM 알고리즘은 두 단계로 구성된다. 먼저 \(z\)의 값을 추측하고, 그 추측을 바탕으로 최대 우도 추정의 공식을 적용한다.

E 단계 (기대값 단계)

각 훈련 예제 \(i\)와 각 가우시안 \(j\)에 대해 다음을 계산한다.

\[w_{ij} := p(z^{(i)} = j \mid x^{(i)}; \phi, \mu, \Sigma)\]

이것은 현재 매개변수 값이 주어졌을 때, \(x^{(i)}\)가 \(j\)번째 가우시안에서 왔을 사후 확률이다. 베이즈 정리를 사용하여 계산한다.

\[w_{ij} = \frac{p(x^{(i)} \mid z^{(i)} = j; \mu_j, \Sigma_j) \cdot p(z^{(i)} = j; \phi)}{\sum_{l=1}^{k} p(x^{(i)} \mid z^{(i)} = l; \mu_l, \Sigma_l) \cdot p(z^{(i)} = l; \phi)}\]

여기서:

\(p(x^{(i)} \mid z^{(i)} = j)\)는 평균 \(\mu_j\), 공분산 \(\Sigma_j\)인 가우시안 밀도 함수다:

\[p(x^{(i)} \mid z^{(i)} = j) = \frac{1}{(2\pi)^{n/2}|\Sigma_j|^{1/2}} \exp\left(-\frac{1}{2}(x^{(i)} - \mu_j)^T \Sigma_j^{-1} (x^{(i)} - \mu_j)\right)\]

\(p(z^{(i)} = j) = \phi_j\)는 다항 분포의 매개변수로, \(z\)가 값 \(j\)를 취할 확률이다.

직관적으로, \(w_{ij}\)는 각 예제를 각 가우시안에 대해 "이 예제가 이 가우시안에서 왔을 확률은 얼마인가?"라는 질문에 답하는 것이다. 가까운 가우시안에는 0.8을, 먼 가우시안에는 0.2를 할당하는 식이다.

M 단계 (최대화 단계)

E 단계에서 계산한 \(w_{ij}\)를 사용하여 매개변수를 갱신한다.

\[\phi_j := \frac{1}{m} \sum_{i=1}^{m} w_{ij}\]

\[\mu_j := \frac{\sum_{i=1}^{m} w_{ij} \cdot x^{(i)}}{\sum_{i=1}^{m} w_{ij}}\]

\[\Sigma_j := \frac{\sum_{i=1}^{m} w_{ij} (x^{(i)} - \mu_j)(x^{(i)} - \mu_j)^T}{\sum_{i=1}^{m} w_{ij}}\]

이 공식들은 \(z\)를 알고 있을 때의 MLE 공식에서 지시 함수 \(\mathbf{1}\{z^{(i)} = j\}\)를 \(w_{ij}\)로 대체한 것이다. 이는 우연이 아니다. \(w_{ij}\)는 지시 함수의 기댓값이기 때문이다.

\[w_{ij} = E[\mathbf{1}\{z^{(i)} = j\} \mid x^{(i)}]\]

기댓값 단계에서 지시 함수의 기댓값을 계산하고, 최대화 단계에서 그 기댓값을 사용하는 것이 바로 "기대값-최대화"라는 이름의 유래다.

K-평균과의 관계

가우시안 혼합 모델의 EM 알고리즘은 K-평균과 비슷하지만, **연성 할당(soft assignment)**을 사용한다는 점이 다르다.

특성	K-평균	EM (가우시안 혼합)
할당 방식	경성(hard): 가장 가까운 군집에 100% 할당	연성(soft): 확률적으로 여러 군집에 분배
표현	\(c^{(i)} \in \{1, \ldots, k\}\)	\(w_{ij} \in [0, 1]\), \(\sum_j w_{ij} = 1\)
군집 모양	구형 (등방성)	타원형 (공분산으로 표현)

K-평균에서는 한 점이 빨간 군집 중심보다 파란 군집 중심에 아주 조금이라도 더 가까우면 100% 파란색으로 할당한다. EM은 확률을 사용하여 "이 점은 80%의 확률로 파란 가우시안에서, 20%의 확률로 빨간 가우시안에서 왔다"고 부드럽게 할당한다.

밀도 추정의 활용

EM 알고리즘으로 가우시안 혼합 모델을 피팅하면, \(p(x, z)\)의 결합 밀도를 얻는다. \(x\)의 밀도는 \(z\)를 주변화하여 구한다.

\[p(x) = \sum_{z} p(x, z)\]

가우시안 혼합 모델은 매우 풍부한 분포 가족을 형성한다. 두 가우시안만으로도 L자 형태, 좁고 높은 봉우리와 넓고 낮은 봉우리의 조합, 그 외 다양한 형태의 분포를 모델링할 수 있다. 가우시안의 수를 늘리면 더 복잡한 분포도 표현할 수 있다.

새 항공기 엔진이 나오면 \(p(x)\)를 평가하여 값이 크면 정상으로 판단하고, \(p(x) < \epsilon\)이면 이상으로 판별하여 추가 점검을 실시한다.

13.6 EM 알고리즘의 일반적 유도

앞선 절에서 "잠재 변수의 값을 추측하고 MLE 공식에 대입한다"는 직관적 설명을 했다. 이 설명은 가우시안 혼합 모델에서는 유효하지만, 더 일반적인 모델에 EM을 적용하려면 엄밀한 유도가 필요하다. 이 유도를 통해 EM이 최대 우도 추정 알고리즘이며, 수렴이 보장된다는 것을 보일 수 있다.

옌센 부등식 (Jensen's Inequality)

EM 알고리즘의 유도에는 옌센 부등식이 핵심적으로 사용된다.

볼록 함수에 대한 옌센 부등식: \(f\)가 볼록 함수이고 \(X\)가 확률 변수이면,

\[f(E[X]) \leq E[f(X)]\]

직관적 이해를 위해, \(X\)가 확률 \(\frac{1}{2}\)로 1, 확률 \(\frac{1}{2}\)로 5를 취하는 경우를 생각하자. \(E[X] = 3\)이다.

\(f(E[X]) = f(3)\): 볼록 곡선 위의 \(x=3\)에 해당하는 점
\(E[f(X)] = \frac{1}{2}f(1) + \frac{1}{2}f(5)\): 곡선 위의 두 점 \((1, f(1))\)과 \((5, f(5))\)를 잇는 **현(chord)**의 중점

볼록 함수에서 현은 항상 곡선 위에 있으므로, \(E[f(X)] \geq f(E[X])\)가 성립한다.

이 부등식의 방향을 기억하는 실용적 팁: 볼록 함수를 그리고 현을 그어 보면, 현 위의 중점이 항상 곡선 위의 대응점보다 높다는 것을 즉시 확인할 수 있다.

추가 조건: \(f\)가 순볼록(strictly convex) 함수이면(즉 직선이 아니라 항상 위로 휘어져 있으면), 등호가 성립하는 경우는 \(X\)가 상수(항상 같은 값을 취하는 확률 변수)인 경우뿐이다.

\[f(E[X]) = E[f(X)] \iff X = E[X] \text{ (확률 1로)}\]

오목 함수에 대한 옌센 부등식: 오목 함수는 볼록 함수의 부호를 뒤집은 것이므로 부등호 방향이 반대가 된다.

\[f(E[X]) \geq E[f(X)]\]

EM 알고리즘에서는 로그 함수(\(\log x\)는 오목 함수)에 대한 오목 형태의 옌센 부등식을 사용한다.

13.7 EM 알고리즘의 유도

문제 설정

매개변수 \(\theta\)로 매개변수화된 모델 \(p(x, z; \theta)\)가 있고, \(x\)만 관측된다. 훈련 세트는 \(\{x^{(1)}, \ldots, x^{(m)}\}\)이다. 로그 우도는 다음과 같다.

\[\ell(\theta) = \sum_{i=1}^{m} \log p(x^{(i)}; \theta) = \sum_{i=1}^{m} \log \sum_{z^{(i)}} p(x^{(i)}, z^{(i)}; \theta)\]

\(p(x)\)는 결합 분포에서 \(z\)를 주변화하여 얻는다. 목표는 이 로그 우도를 최대화하는 \(\theta\)를 찾는 것이다.

하한 구성

임의의 확률 분포 \(Q_i(z^{(i)})\)를 도입한다. \(Q_i\)는 \(z^{(i)}\)에 대한 분포로, \(\sum_{z^{(i)}} Q_i(z^{(i)}) = 1\)을 만족한다.

\[\ell(\theta) = \sum_{i=1}^{m} \log \sum_{z^{(i)}} p(x^{(i)}, z^{(i)}; \theta)\]

같은 양으로 곱하고 나누어 변환한다.

\[= \sum_{i=1}^{m} \log \sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})}\]

\(Q_i\)가 확률 분포이므로, 합 안의 식은 \(z^{(i)} \sim Q_i\)에 대한 기댓값으로 해석할 수 있다.

\[= \sum_{i=1}^{m} \log E_{z^{(i)} \sim Q_i}\left[\frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})}\right]\]

로그 함수는 오목 함수이므로, 오목 형태의 옌센 부등식 \(f(E[X]) \geq E[f(X)]\)을 적용하면:

\[\geq \sum_{i=1}^{m} E_{z^{(i)} \sim Q_i}\left[\log \frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})}\right]\]

\[= \sum_{i=1}^{m} \sum_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})}\]

이 마지막 식은 로그 우도 \(\ell(\theta)\)의 **하한(lower bound)**이다. \(\theta\)의 함수로 보면, 이것이 바로 앞서 그림에서 설명한 "초록색 곡선"이다.

하한을 밀착시키기

하한이 현재 \(\theta\) 값에서 로그 우도와 같아지도록(밀착하도록) \(Q_i\)를 선택해야 한다. 옌센 부등식에서 등호가 성립하는 조건은, 기댓값 안의 확률 변수가 상수인 경우다. 즉:

\[\frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})} = c \quad \text{(상수, } z^{(i)}\text{의 값에 무관)}\]

이것은 \(Q_i(z^{(i)})\)가 \(p(x^{(i)}, z^{(i)}; \theta)\)에 비례해야 한다는 뜻이다. \(Q_i\)는 확률 분포이므로 합이 1이 되어야 한다. 따라서:

\[Q_i(z^{(i)}) = \frac{p(x^{(i)}, z^{(i)}; \theta)}{\sum_{z^{(i)}} p(x^{(i)}, z^{(i)}; \theta)} = \frac{p(x^{(i)}, z^{(i)}; \theta)}{p(x^{(i)}; \theta)} = p(z^{(i)} \mid x^{(i)}; \theta)\]

즉 \(Q_i\)를 \(z^{(i)}\)의 사후 분포로 설정하면 하한이 밀착한다. 이것이 바로 앞서 가우시안 혼합 모델에서 \(w_{ij}\)로 저장한 값이다.

EM 알고리즘의 요약

모든 것을 종합하면 EM 알고리즘은 다음과 같다.

E 단계: 각 \(i\)에 대해 다음을 설정한다.

\[Q_i(z^{(i)}) := p(z^{(i)} \mid x^{(i)}; \theta)\]

이것은 로그 우도의 하한을 현재 \(\theta\)에서 밀착시키는 것에 해당한다(초록색 곡선 그리기).

M 단계: 하한을 \(\theta\)에 대해 최대화한다.

\[\theta := \arg\max_\theta \sum_{i=1}^{m} \sum_{z^{(i)}} Q_i(z^{(i)}) \log \frac{p(x^{(i)}, z^{(i)}; \theta)}{Q_i(z^{(i)})}\]

이것은 초록색 곡선의 최댓값을 찾는 것에 해당한다.

수렴의 직관

EM의 각 반복을 그림으로 이해하면 다음과 같다.

E 단계: 현재 \(\theta\) 값에서 로그 우도에 밀착하는 하한 곡선을 구성한다.
M 단계: 하한 곡선을 최대화하여 새로운 \(\theta\)를 얻는다.

하한을 최대화하면 로그 우도도 함께 증가한다. 하한이 현재 점에서 로그 우도와 같고, 하한의 최댓값은 현재 점 이상이므로, 새로운 \(\theta\)에서의 로그 우도는 이전 이상이다.

이 과정을 반복하면 로그 우도가 단조 증가하며, 결국 **지역 최적해(local optimum)**에 수렴한다.

직접 최대화가 어려운 이유

로그 우도를 \(\theta\)에 대해 직접 미분하고 0으로 놓으면 안 되는 것일까? 가우시안 혼합 모델의 경우, 로그 안에 합이 있으므로 해석적으로 풀 수 있는 닫힌 형태의 해가 존재하지 않는다. 반면 EM의 M 단계에서는 하한의 형태가 훨씬 단순하여(로그와 합의 순서가 바뀌어 있으므로) 해석적 해를 구할 수 있다. 이것이 EM 알고리즘의 강점이다.

핵심 정리

개념	핵심
K-평균 클러스터링	경성 할당 기반 반복 알고리즘. 비용 함수 \(J = \sum \\|x^{(i)} - \mu_{c^{(i)}}\\|^2\)를 최소화
K의 선택	자동 기준(AIC, BIC)보다 하류 응용의 목적에 따라 결정하는 것이 실용적
밀도 추정	\(p(x)\)를 모델링하여 \(p(x) < \epsilon\)이면 이상으로 판별
가우시안 혼합 모델	잠재 변수 \(z \sim \text{Multinomial}(\phi)\), \(x \mid z = j \sim \mathcal{N}(\mu_j, \Sigma_j)\)
E 단계	\(w_{ij} = p(z^{(i)} = j \mid x^{(i)}; \theta)\) 계산 (사후 확률)
M 단계	\(w_{ij}\)를 사용하여 \(\phi, \mu, \Sigma\) 갱신 (가중 MLE)
K-평균 vs EM	K-평균은 경성 할당, EM은 연성 할당 (확률적 가중치)
옌센 부등식	볼록: \(f(E[X]) \leq E[f(X)]\), 오목: \(f(E[X]) \geq E[f(X)]\)
EM의 수렴	로그 우도의 하한을 반복적으로 밀착-최대화하여 지역 최적해에 수렴

이전 장: 12장 - ML 모델 디버깅과 오류 분석 다음 장: 14장 - EM 알고리즘과 인자 분석