HiddenMarkovModel 의 적용예 ¶
이 인간은 자신은 홈페이지를 하루에 한번씩 편집하거나 또는 편집하지 않는다. 그리고 그날의 감정상태에 따라서 홈페이지를 편집하는 확률이 다르며, 그 날의 감정상태는 그 전날에 의해서 확률적으로 결정되는 Markov Chain을 따른다고 가정한다. 이 상황을 HiddenMarkovModel 로 만들어 보자.
일단 state 는 감정상태에 따라 2가지로 둔다. Happy (이하 H) state 와 Gloomy (이하 G) state 이다. 이 모델의 parameter 들은 다음과 같이 설정한다.
{{|
Begin state에서 H 또는 G state 로 가는 transition 의 확률 : 각각 1/2로 놓는다.
H 또는 G state에서 End state 로 가는 transition 의 확률 : 각각 1로 놓는다. 왜냐하면 이 모델에서 넷째날은 없기 때문이다.
Begin state에서 H 또는 G state 로 가는 transition 의 확률 : 각각 1/2로 놓는다.
H 또는 G state에서 End state 로 가는 transition 의 확률 : 각각 1로 놓는다. 왜냐하면 이 모델에서 넷째날은 없기 때문이다.
G state에서 자신으로 돌아오는 (어제 우울했는데 오늘도 우울할) transition 의 확률 : 4/5
G state에서 H state 로 가는 (어제 우울했는데 오늘은 행복할) transition 의 확률 : 1-(4/5) = 1/5
H state에서 자신으로 돌아오는 (어제 행복했는데 오늘도 행복할) transition 의 확률 = 1/3
H state에서 G state 로 가는 (어제 행복했는데 오늘은 우울할) transition 의 확률 = 1-(1/3) = 2/3
G state에서 H state 로 가는 (어제 우울했는데 오늘은 행복할) transition 의 확률 : 1-(4/5) = 1/5
H state에서 자신으로 돌아오는 (어제 행복했는데 오늘도 행복할) transition 의 확률 = 1/3
H state에서 G state 로 가는 (어제 행복했는데 오늘은 우울할) transition 의 확률 = 1-(1/3) = 2/3
H state에서 자신의 홈페이지를 편집할 emission 확률 (행복한 날 자신의 홈페이지 편집할 확률) : 1/10
G state에서 자신의 홈페이지를 편집할 emission 확률 (우울한 날 자신의 홈페이지 편집할 확률) : 1/100
|}}
G state에서 자신의 홈페이지를 편집할 emission 확률 (우울한 날 자신의 홈페이지 편집할 확률) : 1/100
|}}
이제 우리가 대답하여야 할 질문은...
1. 이 인간이 사흘 연속으로 홈페이지를 편집하였다. 이 사람의 기분 상태는 어땠을까?
이것을 알기 위해서는 우리는 각 경우를 모두 생각해 보아야 한다. 일단 사흘 연속 홈페이지 편집한 사건을 "EEE"라는 하나의 sequence 로 두고, 위에서 설정한 HiddenMarkovModel에서 어떤 경우에 "EEE" 가 가장 높은 확률로 생성되는지를 생각해 본다.
우리는 state를 모른다. HiddenMarkovModel 이 괜히 Hidden 이 아니다. State를 모르기 때문에 Hidden 인 것이다. 이것은 다시 말해서, 이 사람이 우울한 상태(G state)에서 홈페이지를 편집했는지, 아니면 행복한 상태(H state)에서 홈페이지를 편집했는지 모르는 것이다. 그러므로 각각의 경우를 모두 계산해 보아야 한다.
각 state 가 사용될 경우와 그 경우에 "EEE" 가 나올 각각의 확률은 다음과 같다.
{{|
HHH : (1/2 * 1/10) * (1/3 * 1/10) * (1/3 * 1/10) = 0.00005555
HHG : (1/2 * 1/10) * (1/3 * 1/10) * (2/3 * 1/100) = 0.00001111
HGH : (1/2 * 1/10) * (2/3 * 1/100) * (1/5 * 1/10) = 0.00000666
HGG : (1/2 * 1/10) * (2/3 * 1/100) * (4/5 * 1/10) = 0.00002666
HHH : (1/2 * 1/10) * (1/3 * 1/10) * (1/3 * 1/10) = 0.00005555
HHG : (1/2 * 1/10) * (1/3 * 1/10) * (2/3 * 1/100) = 0.00001111
HGH : (1/2 * 1/10) * (2/3 * 1/100) * (1/5 * 1/10) = 0.00000666
HGG : (1/2 * 1/10) * (2/3 * 1/100) * (4/5 * 1/10) = 0.00002666
GGG : (1/2 * 1/100) * (4/5 * 1/100) * (4/5 * 1/100) = 0.00000032
GGH : (1/2 * 1/100) * (4/5 * 1/100) * (1/5 * 1/10) = 0.00000080
GHG : (1/2 * 1/100) * (1/5 * 1/10) * (2/3 * 1/100) = 0.00000066
GHH : (1/2 * 1/100) * (1/5 * 1/10) * (1/3 * 1/10) = 0.00000333
|}}
GGH : (1/2 * 1/100) * (4/5 * 1/100) * (1/5 * 1/10) = 0.00000080
GHG : (1/2 * 1/100) * (1/5 * 1/10) * (2/3 * 1/100) = 0.00000066
GHH : (1/2 * 1/100) * (1/5 * 1/10) * (1/3 * 1/10) = 0.00000333
|}}
이 중에서 가장 높은 확률을 가진 것이 바로 HiddenMarkovModel 의 most probable state path를 찾는 Viterbi algorithm 이다. 바로 "HHH"이다. 이것은 H state 를 3일 연속 돌았을 때 가장 "EEE" 가 나올 확률이 높음을 나타낸다.
따라서 답은 이 사람은 사흘 연속 행복했을 확률이 가장 높다는 것이다.
2. 다음 질문은 이 사람이 사흘 연속 홈페이지를 편집할 전체 확률이다. 이것은 간단하다. 위의 8가지 경우를 모두 더하면 된다. 이것이 HiddenMarkovModel 의 forward algorithm 이다.
0.00005555 + 0.00001111 + 0.00000666 + 0.00002666 + 0.00000032 + 0.00000080 + 0.00000066 + 0.00000333 = 0.00010509
위의 parameter 로 볼 때 이 사람이 사흘 연속 홈페이지를 편집할 확률은 0.0001 정도 된다. 여기에는 사흘 연속 행복한 상태에서 편집한 것 뿐 만 아니라, 사흘 연속 우울한 상태에서 편집한 것도 상대적으로 작은 확률이지만 포함되어 있는 것이다.
3. 마지막 질문을 던져 보자. "EEE" 라는 sequence를 우리가 가지고 있을 때, 이 사람이 3일중 둘째날 H state 였을 확률, 즉 행복했을 확률은 얼마인가?
이것은 forward-backward algorithm을 이용하여 해결할 수 있다.
P(둘째날 "H" | "EEE") = P(둘째날 H, "EEE") / P("EEE") = f * b / P("EEE) 가 되는데, 여기서 f 는 둘째날 "H" state를 사용하였을 때, 첫날, 둘째날 "EE" 가 나오게 만드는 forward algorithm 의 변수고, b 는 둘째날 "H" state 를 사용했을때, 셋째날 "E" 가 나오게 만드는 backward algorithm 의 변수이다.
다시 말해서 f 는 첫날, 둘째날 GH, HH state 가 사용된 상태에서 "EE" (첫날, 둘째날) 가 나오는 것을 계산해 주고, b 는 둘째날, 셋째날, HH, HG 가 사용된 상태에서 "E" (셋째날) 가 나오는 것을 계산해 준다. b를 backward 라고 하는 이유는 셋째날, G, H state 가 사용된 상태에서 그 전날 H 가 사용된 것을 거꾸로 선택하기 때문이다.
f를 계산해 보면
{{|
HH = (1/2 * 1/10) * (1/3 * 1/10) = 0.00166666
GH = (1/2 * 1/100) * (1/5 * 1/10) = 0.0001
|}}
{{|
HH = (1/2 * 1/10) * (1/3 * 1/10) = 0.00166666
GH = (1/2 * 1/100) * (1/5 * 1/10) = 0.0001
|}}
따라서 f 는 0.00166666 + 0.0001 = 0.00176666 이 되고
b를 계산해 보면
{{|
둘째날, 셋째날 HG state 가 사용된 상태(즉, H에서 G 로 가는 transition)에서 셋째날 G state에서 "E" 가 emission 되고, 거기서 끝나는 경우는
2/3 * 1/100 = 0.00666666
둘째날, 셋째날 HG state 가 사용된 상태(즉, H에서 G 로 가는 transition)에서 셋째날 G state에서 "E" 가 emission 되고, 거기서 끝나는 경우는
2/3 * 1/100 = 0.00666666
둘째날, 셋째날 HH state 가 사용된 상태(즉, H에서 H 로 가는 transition)에서 셋째날 H state에서 "E" 가 emission 되고, 거기서 끝나는 경우는
1/3 * 1/10 = 0.03333333
|}}
1/3 * 1/10 = 0.03333333
|}}
이 둘을 합한 값이 0.03999999 이 b 값이 된다.
f * b 를 해 보면 0.00007066 이 나오는데, 이것은 당연한 거지만, 두번째날 H state 가 사용된 모든 경우를 더한 값인,
{{|
HHH : (1/2 * 1/10) * (1/3 * 1/10) * (1/3 * 1/10) = 0.00005555
HHG : (1/2 * 1/10) * (1/3 * 1/10) * (2/3 * 1/100) = 0.00001111
GHG : (1/2 * 1/100) * (1/5 * 1/10) * (2/3 * 1/100) = 0.00000066
GHH : (1/2 * 1/100) * (1/5 * 1/10) * (1/3 * 1/10) = 0.00000333
|}}
HHH : (1/2 * 1/10) * (1/3 * 1/10) * (1/3 * 1/10) = 0.00005555
HHG : (1/2 * 1/10) * (1/3 * 1/10) * (2/3 * 1/100) = 0.00001111
GHG : (1/2 * 1/100) * (1/5 * 1/10) * (2/3 * 1/100) = 0.00000066
GHH : (1/2 * 1/100) * (1/5 * 1/10) * (1/3 * 1/10) = 0.00000333
|}}
0.00005555 + 0.00001111 + 0.00000066 + 0.00000333 = 0.00007065 와 일치한다. 일치 안 하는 부분은 컴퓨터에서 수치해석상의 오차이다.
따라서 3일 연속 홈페이지가 편집되었을 때, 둘째날 H state 가 사용되었을 확률은
P(둘째날 "H" | "EEE") = P(둘째날 H, "EEE") / P("EEE") = f * b / P("EEE) = (0.00176666 * 0.03999999) / 0.00010509 = 0.67243679 이다.
TestFirstProgramming 으로의 적용 ¶
Q : 이것을 어떻게 TestFirstProgramming 으로 구현할 수 있는가?
A : Let's first think of The Simplest Thing That Could Possible Work, and describe it to the computer. We'll listen to the code and the computer's demand as the rest emerges. And if we are truly sure of every logical step of the algorithm, we could ask the code with the unit test, to be made as separated into several concerns...