Expectation Maximization

FrontPage|FindPage|TitleIndex|RecentChanges| UserPreferences P RSS
ExpectationMaximization algorithm 은 'missing data' 가 있을 때의 maximum likelihood estimation 방법이다.

문제상황

A와 B 의 두 사람의 아무개씨가 있다. 이 사람들은 서로 다른 시간대에 살고 있어서, 노스모크에 글을 주로 올리는 시간이 다르다. 하지만 우리는 둘 다 아무개이기 때문에 노스모크에 올라온 글만 보고는 누가 A 아무개이고, 누가 B 아무개인지 모른다.

몇가지 가정을 하자.
  1. 두 사람이 올리는 글의 시간들이 둘 다 정규분포를 이룬다.
  2. 두 정규분포의 분산은 같다.
  3. 정규분포의 평균을 아는 상태에서 어떤 event 의 떨어진 차이를 알면, 그 event 가 일어날 확률을 계산해 주는 공식을 알고 있다. (사실 이것은 가정이 아니고 실제 존재하는 공식이다)

이제 우리가 알고 싶은 것은 두 사람이 올린 글들의 시간이 이루는 두 정규분포 각각의 평균이고, 이것을 알면, 어느 글이 A와 B 중 누가 올린 글인지 확률적으로 계산할 수 있다.

EM algorithm을 사용한 해결

  1. 먼저 평균 m_A, m_B를 임의로 정한다.
  2. 정규분포의 평균과 거기서 떨어진 시간의 위치를 이미 알고 있으므로 각각의 글들에 대해서 A에 속하는 확률과 B 에 속하는 확률을 계산할 수 있다.
  3. 모든 글에 대해서 A와 B에 속하는 확률의 평균을 내면 새로운 m_A' 와 m_B' 가 계산된다.
  4. 처음으로 돌아가서 새로운 평균을 가지고 그 다음의 과정을 수렴할 때까지 반복한다.

잡담

위의 문제는 "Machine Learning" by Mitchell 에 나온 예를 노스모크의 상황으로 각색한 것이다. 일단 이 문제에서 missing 된 data 는 각각의 글이 A와 B 어느 사람이 올린 것인가이다. EM algorithm을 그대로 실생활에 적용할 일이 많지는 않겠지만, 여기 담겨있는 의미를 이렇게도 생각해 볼 수 있을 것 같다.

이것은 일종의 피드백의 반복을 보여주고 있으며, 그때마다 처음의 전혀 근거 없던 가정이 조금씩 진실에 가깝게 수정되어 가는 것을 보여준다. 물론 그것이 실제 진실이 아닌 local optima 일 가능성도 있지만. 어쨌든 삶이라는 것도 이런 방식이 되어야하지 않을까 싶다. 똑같은 일이라도 반복할 때마다 조금씩 나아지고 발전해야지, 단순히 의미 없는 반복이어서는 곤란할 것이다.

EM algorithm 은 "Machine Learning" 의 한 분야이다. 기계도 이렇게 하면 뭔가를 배워 가는데... 사람은...? ^^

보통의 NeuralNetwork에서 쓰는 방법을 일컫는 말인가요? (NeuralNetwork는 개념만 알고 용어는 몰라서요...) --AnswerMe Refactor, DeleteMe, PuzzletChung

NeuralNetwork에서 쓰이는 보통의 학습방법은 Back Propagation이고, 굳이 greedy heuristic algorithm중의 하나에 비유하자면, gradient descent방법의 매우 체계적인 적용이랄 수 있습니다. EM Algorithm은 확률 기반 clustering에서 주로 많이 쓰입니다. --naya


"; if (isset($options[timer])) print $menu.$banner."
".$options[timer]->Write()."
"; else print $menu.$banner."
".$timer; ?> # # ?>