최근에 Markov Chain이라는 것을 듣게 됐다. 이게 사실은 확률론의 '확률 과정'이라는 곳에서 나오는 개념인데, 필자는 수학 찐따라 기본적으로 위키피디아에서 설명하는 정의는 이해하지 못한다.
첫 문장부터 확률 공간, 가측 집합, 가측 공간같은 소리를 하는데다, markov chain에 대해 잘 정리된 것 같은 글들은 수학적 배경이 너무 많이 필요해서 여기에 좀 정리해보려고 한다.
Markov Chain
Markov Chain은, Markov Property를 지닌 이산 시간 확률 과정(Discrete-time Stochastic Process)을 의미한다(라고 설명하고 있다). 무작정 정리하기 전에, 그냥 Markov Chain의 예를 직접 보도록 하자.
Markov Chain의 예와 이의 해석
위 그림의 s, c, r을 state(상태)라고 부르고, 각 state 사이에 이어진 유향 선분(화살표)에 대해 할당된 가중치들은 해당 상태 전이가 이루어질 수 있는 확률을 의미한다(확률론에서 항상 그러는지는 모르겠으나, Markov Chain에서는 확률을 표현할 때 0~100%에 대한 구간을 [0, 1]로 두어 대응시키고 있다). 위 그림의 경우, s에서 c가 될 확률이 0.3(30%)이고, c에서 r이 될 확률이 0.5(50%)같은 식으로 해석하면 된다. 조건부 확률을 떠올려서 P(s|c)=0.3, P(c|r)=0.5같이 봐도 되고. 그렇다면 위 markov chain을 기준으로 했을 때, 오늘 날씨가 맑음(s)이고, 내일 날씨가 비(r)이며 모레 날씨가 맑음(s)이 될 확률은 P(s|r) * P(r|s) = 0.1 * 0.4 = 0.04가 될 것이다.
다시 정리하면
Markov Chain은 그냥 어떤 state를 정의하고, 그 state들 각각에 대한 전이 확률을 정의해둔 채 이거 갖고 짝짝꿍 하는 거다. 다시 정리하면, 위처럼 sunny, cloudy, rainy같은 state(상태)가 존재하고, 각 state를 넘나드는 확률값이 존재해서 이게 chain처럼 구성되어 있고, 상태 전이 확률이 항상 현재 state에만 의존한다면(예를 들어 s → c라는 전이의 확률이 r에 의존하지 않는다면), 이를 Markov Chain이라고 부른다. 여기서 '상태 전이 확률이 항상 현재 state에만 의존하는 것'이 Markov Property를 나타낸다.
근데 뭐 sunny, cloudy, rainy 이런 것만 봐서 이게 도대체 얼마나 유의미한 것을 도출해낼 수 있을까 싶을텐데, real world에선 이런 곳에 쓰이고 있다.
- Markov Chain에서, chain이 커지면(상태 전이 횟수가 늘어나면) 특정 state에 전이될 확률이 고정된 값으로 수렴한다고 한다. 웹 전체를 markov chain으로 두었을 때, '서핑이 오랜 시간 이루어진다'고 가정하면 특정 웹 페이지 X에 도달하는 것은 고정 확률이라고 볼 수 있다. Google의 Page Rank 알고리즘이 markov chain 이론을 기반으로 만들어졌다고 한다.
- 안드로이드의 Google 키보드에는 'Google 키보드를 개선하기 위해 Google 어플리케이션에 입력하는 내용 공유'라는 옵션이 있다. 이게 켜져 있으면, 우리가 타이핑하는 단어들이 Google로 보내져서 Markov Chain에 반영되고, 이를 통해 Google은 단어 예측(Typing Word Prediction)을 수행한다.
- 음성 인식, 추천 엔진 등 상태 전이 확률을 통해 뭔가 예측할 필요가 있는 곳들에서 Markov Chain을 자주 사용하고 있다고 한다.