서론

신호처리 분야에선 PDF의 모수-파라미터, 특히 신호의 기댓값을 구하는 일이 빈번하다. 그런데 대부분 파라미터를 추정할 때 모든 데이터를 직접 받아와 계산하는 일이 대부분의 경우 불가능하므로 파라미터 추정이 매우 까다로워진다. 그 상황의 예로는 결과값이 누적되거나 뭉쳐져서 나타나는 경우고, 실제 데이터포인트가 얼마나 존재하는지 모호하게 만든다. 그래서 여기서 선보이는 EM 알고리즘은, 내부 확률분포와 관측값을 결정하는 확률분포가 다대일 구조를 이룰 때 이러한 문제에서도 파라미터를 MLE로 구할 수 있게한다.

<aside> 💡 이후에 확률변수값이 뭉쳐져서(더해져서) 관측되는 예제가 나온다!

</aside>

EM 알고리즘은 이름에서도 알 수 있듯이 Expectation 과정과 Maximization 과정이 있다. Expectation 과정은 지금까지 구해진 파라미터 추정값과 관측 결과를 이용해 내부 변수를 구하는 과정이고, Maximization 과정은 새로운 파라미터 추정값을 구하는 과정이다. 이 과정이 반복되는 것이 EM 알고리즘이다.

EM 알고리즘은 다방면에 적용할 수 있는데, 유전자 분석, 계량경제학, 의학, 사회학 등에서 결과값에 영향을 미치는 알 수 없는 요소가 있을 때 이용된다.

Ector’s Problem

이 이미지처리 예제는 Ector와 Hater가 제안한 문제고 이 글에서 기술하는 EM알고리즘의 표기법을 따르는 문제이다.

문제설정
- 이미지 패턴 인식 문제
- 두 class, 밝은/어두운 이미지
- 어두운 이미지는 둥근 것과 네모난 것으로 구분됨
- 패턴 인식기를 통해 검은 이미지를 인식해내는 것이 목표
가정(내부 분포)
- trinormally distributed, $X_1, X_2, X_3$ 벡터로 $X$로 표기
- 순서대로 둥글고 어두운 물체 수, 네모나고 어두운 물체 수, 흰 물체 수
- $\mathbf{x} = \lbrack x_1,x_2,x_3 \rbrack ^\top$
- $\displaystyle P(X=\mathbf{x}~|~p)=\left(\frac{n!}{x_1!x_2!x_3!}\right)\left(\frac{1}{4}\right)^{x_1}\left(\frac{1}{4}+\frac{p}{4}\right)^{x_2}\left(\frac{1}{2}-\frac{p}{4}\right)^{x_3}\\=f(\mathbf x~|~p)$
- $n=x_1+x_2+x_3$
- $p$는 미지의 파라미터
가정(관측 분포)
- $\mathbf{y}=[y_1,y_2]^\top$, $y_1=x_1+x_2,~ y_2=x_3$
- 이러면 x에서 y로 다대일 관계가 만들어짐
- $\displaystyle P(Y_1=y_1~|~p)=\left(\begin{matrix} n\\y_1 \end{matrix}\right)\left(\frac{1}{2}+\frac{p}{4}\right)^{y_1}\left(\frac{1}{2}-\frac{p}{4}\right)^{n-y_1}\\=g(y_1~|~p)$

이제 MLE는 다음이 된다.

$$ p_{ML}=\argmax_p g(Y_1=y_1~|~p) $$

식을 넣으면 매우 복잡하므로 로그의 argmax를 하면

$$ \begin{equation}

p_{ML}=\argmax_p\log\left(\begin{matrix} n\\y_1 \end{matrix}\right)\left(\frac{1}{2}+\frac{p}{4}\right)^{y_1}\left(\frac{1}{2}-\frac{p}{4}\right)^{n-y_1} \end{equation} $$

EM의 요점은 $x_1$과 $x_2$에 대한 직접적인 정보 없이도 $f(\mathbf{x}~|~p)$의 정보를 이용해 $p$를 추정할 수 있다는 점이다. 윗 대괄호 첨자를 n번째 반복에 대한 거라고 표기하자. 초기 $p^{[0]}$값은 적절히 주고 시작한다.

서론

Ector’s Problem

E과정