The windowEM algorithm

"windowEM 알고리즘"에 관한 기술적 요약

문제 정의
기댓값 최대화(Expectation-Maximization, EM) 알고리즘은 잠재 변수가 포함된 모델에서 최대 우도 추정을 수행하는 표준적인 방법이다. 그러나 대규모 데이터셋(예: 수십억 개의 데이터 포인트를 포함하는 유전체 데이터)의 맥락에서, 표준 EM 알고리즘은 매 반복마다 전체 데이터셋을 처리해야 하므로 계산적으로 비실용적이다. 이를 가속화하기 위해 미니 배치(mini-batch)를 사용하는 확률적 EM 버전들이 제안되어 왔으나, 이들은 특히 파라미터 공간이 복잡하거나 특정 잠재 변수가 데이터 내에 희소하게 나타나는 경우, 거칠거나 노이즈가 섞인 파라미터 추정치를 생성하는 경우가 많다. 이러한 노이즈는 사이트 빈도 스펙트럼(site frequency spectra, SFS)과 같은 추정된 분포에서 인위적인 "돌출부(bumps)"를 만드는 등의 아티팩트를 유발할 수 있으며, 과적합(over-fitting)에 기여할 수 있다.

방법론: windowEM 알고리즘
저자들은 데이터를 $B$개의 블록으로 나누고 이 블록들을 원형으로 배치하는 windowEM이라는 확률적 EM 변형 알고리즘을 제안한다. 이 알고리즘은 다음 메커니즘을 통해 작동한다:

1. 블록 분할: 데이터는 $B$개의 블록($x_1, \dots, x_B$)으로 나뉜다. 블록의 크기와 분포는 다를 수 있으며, 서로 독립이라고 가정하지 않는다.
2. 순차적 업데이트: 알고리즘은 현재 블록 $k$의 추정치가 이전 블록 $k-1$의 추정치를 시드(seed)로 사용하여 도출되는 일련의 업데이트를 수행한다. 구체적으로, 현재의 파라미터 추정치 $\theta_t$를 사용하여 블록 $b(t+1)$에 대해 표준 EM 알고리즘을 한 번 수행함으로써 예비 추정치 $\psi_{t+1}$을 얻는다:
   $$\psi_{t+1} = f_{b(t+1)}(\theta_t) = \arg\max_{\theta'} Q_{b(t+1)}(\theta' | \theta_t)$$
3. 롤링 윈도우 평균화(Rolling Window Averaging): 단일 블록 업데이트에 내재된 노이즈를 상쇄하기 위해, 알고리즘은 추정치의 "인구 집단(population)"을 유지한다. 주어진 단계에서의 최종 추정치 $\theta_t$는 크기가 $w$인 롤링 윈도우 내에서 가장 최근의 $w$개 예비 추정치의 평균이다:
   $$\theta_t = \frac{1}{w} \sum_{i=t-w+1}^{t} \psi_i$$
4. 순환 반복: 블록들은 순환적으로 배치된다. $B$가 유한하면, 알고리즘은 블록들을 반복적으로 통과하며 에포크(epochs)를 수행한다. 만약 $B = \infty$이면, 알고리즘은 고유한 블록들의 무한한 수열을 따라 진행한다.
5. 최종 추정: $B$개 추정치의 인구 집단을 평균함으로써 단일 점 추정치를 생성할 수 있다.

저자들은 이 알고리즘이 Polyak-Ruppert 평균화에서 영감을 받았으나, 표준적인 확률적 경사 하강법 방식처럼 기울기(gradient)나 업데이트를 평균내는 것이 아니라, 원형으로 배열된 데이터에 대한 순차적 EM 단계에서 생성된 추정치들에 평균을 적용한다는 점에서 다르다고 언급한다.

주요 이론적 기여
본 논문은 유한한 $B$와 무한한 $B$라는 두 가지 시나리오 하에서 windowEM의 수렴 특성을 조사한다.

• 유한한 $B$: 저자들은 수축 이론(contraction theory)을 활용한다. 업데이트 함수가 수축(contraction)이라면 블록 추정치의 수열이 수렴함을 입증한다. 핵심적인 발견은 하나의 블록에 대한 고정점(fixed point)이 존재하면 모든 블록에 대해 고정점이 존재한다는 것이다. 이러한 블록 추정치의 분포는 윈도우 크기 $w$에 따라 달라지는데, 경험적으로 더 큰 윈도우 크기는 블록 추정치 간의 분산을 낮춘다.
• 무한한 $B$: $B = \infty$인 경우(또는 블록이 반복되지 않을 만큼 충분히 큰 경우)에 대해, 저자들은 종속 데이터에 대한 랜덤 이터레이션 이론(random iteration theory)을 적용한다. 저자들은 블록 인덱스가 커짐에 따라 추정치가 고정점으로 수렴하기 위한 조건을 제공한다. 또한, $B \to \infty$일 때 블록 추정치의 에르고딕 평균(ergodic average)의 수렴을 보장하는 조건을 확립한다.
• 지수 가족(Exponential Families): 분석은 지수 가족에 대해 특히 엄격하다. 저자들은 평균값 파라미터화(mean value parameterization)에 대해 업데이트 함수가 흔히 충분 통계량(sufficient statistics)의 선형 함수임을 보여준다. 지수 가족 분포의 혼합(mixtures)의 경우에도 업데이트 함수는 추정된 클래스 확률에 의해 가중치가 부여된 관측 통계량에 대해 선형성을 유지한다.
• 특수 사례: 논문은 $w=1$인 경우($\text{평균화 없는 순차적 EM으로 환원됨}$)와 $w=B$인 경우(업데이트가 모든 블록에 대한 평균이 되어, 선형성 가정 하에 표준 EM 솔루션과 동일한 고정점을 낼 수 있음)와 같은 특정 구성들을 분석한다.

경험적 결과
논문은 두 가지 주요 예제를 통해 알고리즘을 검증한다:

1. 예시적 이항 분포 예제: 유전자 빈도 추정 문제. 결과는 windowEM이 최대 우도 추정치(MLE)로 빠르게 수렴함을 보여준다. 추정치의 분산은 윈도우 크기 $w$가 증가함에 따라 감소하지만, $w$가 커짐에 따라 수렴 속도는 약간 느려질 수 있다.
2. 단변량 가우시안 혼합 모델: 가우시안 분포의 혼합에 대해 알고리즘을 테스트한다.
   • $n=10^5$개의 데이터 포인트와 $B=10$개의 블록을 사용한 시뮬레이션에서, windowEM은 표준 EM보다 훨씬 빠르게 완전 데이터 MLE에 근접하는 로그 우도(log-likelihood)를 달성했다.
   • 주목할 점은, 표준 EM이 결국 windowEM보다 높은 로그 우도를 달성하기는 했으나, 이는 완전 데이터 MLE를 초과하기도 했다는 것인데, 이는 과적합을 시사한다. 추정치의 인구 집단을 평균하여 도출된 windowEM 추정치는 표준 EM에서 보이는 "오버슈트(overshoot)" 없이 실제 기저 분포에 더 가깝게 유지되며 일종의 규제화(regularizer) 역할을 하는 것으로 나타났다.
   • 더 작은($n=10^4$) 및 더 큰($n=10^6$) 데이터셋에서도 유사한 경향이 관찰되었으며, windowEM은 표준 EM보다 더 빠르게 완전 데이터 MLE에 가깝게 안정화되었다.

의의 및 주장
저자들은 windowEM이 표준 EM은 불가능하고 표준 확률적 EM은 너무 노이즈가 심한 대규모 추론을 위한 실용적인 해결책을 제공한다고 주장한다. 주요 의의는 추정치의 인구 집단을 롤링 윈도우를 통해 평균화함으로써 유도되는 **규제화 효과(regularization effect)**에 있다.

• 과적합 방지: 저자들은 유전체학(SFS 추정) 및 가우시안 혼합 모델의 경험적 증거를 바탕으로, windowEM이 과적합을 방지하는 데 도움을 준다고 추측한다. 특정 블록의 희귀한 사건들에 의해 인위적으로 팽창될 수 있는 추정치를 매끄럽게 함으로써, 알고리즘은 더 안정적인 파라미터 추정치를 생성한다.
• 이론적 토대: 본 논문은 유한 블록 및 무한 블록 시나리오를 구분하고 수축 및 랜덤 이터레이션 이론을 활용하여 이 특정 체계의 수렴에 대한 최초의 이론적 조사를 제공한다.
• 겸손한 태도: 저자들은 자신들의 주장에 있어 신중함을 유지한다. windowEM이 항상 절대적인 최대 우도 추정치에 도달하지 못할 수도 있고(심지어 표준 EM보다 낮은 로그 우도를 가질 수도 있음), 결과적으로 발생하는 추정치가 분산 감소 덕분에 더 견고하고 통계적으로 의미 있을 수 있음을 언급한다. 그들은 표준 EM에 대한 보편적 우위를 주장하는 것이 아니라, 대규모 데이터 환경에서 안정성과 속도 사이의 트레이드오프를 선호하는 선택임을 밝히고 있다.