HMM(Hidden Markov Model)은 강력한 통계학적 분석 방법이다. HMM으로 해결할 수 있는 유형의 문제는 Evaluation Problem, Decoding Problem, Learning Problem 세가지이다. Hidden이라는 이름이 붙은 이유는, 관찰자는 오로지 특정 상태에서 방출되는 기호들을 관찰할 수 있을 뿐이며, 기호가 어떤 상태에서 방출된 것인지 알 수 없기 때문이다. (즉, HMM이 현재 어떤 상태인지 알 방법이 없다)
예를 들어, 카지노(Casino)에서 주사위 던지기 게임을 한다고 했을 때, 이 카지노의 딜러(Dealer)는 언제나 공정한 주사위를 사용하지 않는다고 하자. 딜러는 가중치가 적용된 주사위와 공정한 주사위를 번갈아가며 사용한다. 여기서 결과로 얻어진 시퀀스(Sequence)를 관찰했을 때, 이 시퀀스가 공정한 주사위를 사용했다고 보기에는 힘든, 특정 주사위 순서가 자주 나타났다고 하자. 이런 시퀀스가 얻어질 가능성이 어느 정도 되는지 평가하는 문제가 Evaluation Problem이다. 그리고, 이 시퀀스에서 어느 부분이 공정한 주사위를 사용한 결과인지, 어느 부분이 가중치가 적용된 주사위를 던진 부분인지 판단하는 문제가 Decoding Problem이다. 마지막으로 Learning Problem은 주사위에 가중치가 적용되었다면 어느 정도로 가중치가 적용되었는지, 공정한 주사위를 사용했다면 어느 정도로 공정한 주사위인지, 또는 얼마나 자주 딜러가 주사위를 바꾸는지 따위의, 변수들을 결정하는 문제이다. 즉, 다음과 같이 나타낼 수 있다.
1. Evaluation Problem
GIVEN : HMM m, sequence x
FIND : Prob[x | m]
2. Decoding Problem
GIVEN : HMM m, sequence x
FIND : sequence π of states that max Prob[x, π | m]
3. Learning Problem
GIVEN : HMM m, unspecified transition / emmision prob., sequence x
FIND : parameters θ = (e(i)(.), a(ij) that max P[x | θ]
통상적으로 첫 번째 Evaluation Problem과 Decoding Problem은 이를 해결하는 일반적인 알고리즘이 존재하지만 마지막 Learning Problem은 이를 해결하는 방법이 매우 복잡하고, 그 정도에 따라 난이도가 결정된다.
HMM에는 다음과 같은 기본적인 정의가 있다.
1. 알파벳(Alphabet, Symbol) Σ = { b1, b2, b3, b4, ...., bm }
2. 상태집합(Set of States) Q = { 1, .... K }
3. 변환 가능성(Transition Probalbility) : 상태 1에서 2로 변할 가능성, 예를 들어 a(ij)는 i에서 j로 상태가 변할 가능성을 표기한다.
4. 시작 가능성(Start Probability) a(0i) : 어떤 상태에서 시작할 가능성
5. 방출 가능성(Emission Probability) e(i)(b) : 어떤 상태에서 알파벳 집합 원소를 방출할 가능성.
e(i)(b) = P(x(i) = b | π(i) = K }, e(i)(b1) + .... + b(i)(b(m)) = 1 (모든 상태 1 .... K에 대해서, 여기서 π(i)는 현재 상태를 뜻한다)
이 정의를 이용한 예를 들어보면, 어떤 시점 t에서 영향을 미치는 것은 현재 상태 인자 π(t)이며, 이때 가능한 시퀀스의 표기는 다음과 같다.
P(π(t+1) = K | π(1) π(2) π(3) π(4) .... π(t), x(1) x(2) x(3) x(4) .... x(t) }
좀 더 구체적으로 예를 들어보자. 딜러가 주사위를 던졌을 때, x = 1, 2, 1, 5, 6, 2, 1, 6, 2, 4라는 시퀀스가 관찰되었다고 하자. 공정한 주사위에서는 각 숫자가 나올 확률이 1 / 6으로 모두 동일하지만, 가중치가 적용된 주사위에서 6이 나올 확률이 1 / 2이며, 나머지 수가 나올 확률은 1 / 10이라 하자. 또, 공정한 주사위를 사용했을 때 다음에 다시 공정한 주사위를 사용할 확률은 0.95, 가중치가 적용된 주사위를 사용했을 때 다음에도 가중치가 적용된 주사위를 사용할 확률은 0.95라 하자. 이때, 공정한 주사위를 사용했을 확률은 어떻게 될까? 즉, π = F(Fair), F, F, F, F, F, F, F, F, F일 확률은 얼마인가?
처음 시작 확률에서, 공정한 주사위를 사용할 확률과 가중치가 적용된 주사위를 사용할 확률이 1 / 2라고 했을 때, 다음과 같이 쓸 수 있다. 계산은 처음 시작 확률 * 그 상태에서 해당 알파벳(결과)을 방출할 확률 * 다음 상태로 전이될 확률을 곱하는 과정으로 이루어진다.
1 / 2 * P(1 | F) * P(F | F) * P(2 | F) * P(F | F) .. * P(4 | F) = 1 / 2 * (1 / 6)^10 * (0.95)^9 = 0.521 * 10^(-9)
그렇다면, 딜러가 가중치가 적용된 주사위를 사용할 확률 π = L(Loaded), L, L, L, L, L, L, L, L, L은 어떻게 되는가?
1 / 2 * P(1 | L) * P(L | L) * P(2 | L) * P(L | L) .... * P(4 | L) = 1 / 2 * (1 / 10)^8 * (1 / 2)^2 * (0.95)^9 = 0.79 * 10^(-9)
따라서, 이 시퀀스의 경우 가중치가 적용된 주사위를 사용하고 있을 확률이 공정한 주사위를 사용했을 확률보다 높다고 할 수 있다.
HMM 방법은 각 사건들이 독립사건이라고 전제하고 있다. 어떤 사건에 영향을 미치는 것은 바로 전의 상태 인자뿐이며, 경우에 따라서는 이 방법이 약점으로 지적되기도 한다.
예를 들어, 카지노(Casino)에서 주사위 던지기 게임을 한다고 했을 때, 이 카지노의 딜러(Dealer)는 언제나 공정한 주사위를 사용하지 않는다고 하자. 딜러는 가중치가 적용된 주사위와 공정한 주사위를 번갈아가며 사용한다. 여기서 결과로 얻어진 시퀀스(Sequence)를 관찰했을 때, 이 시퀀스가 공정한 주사위를 사용했다고 보기에는 힘든, 특정 주사위 순서가 자주 나타났다고 하자. 이런 시퀀스가 얻어질 가능성이 어느 정도 되는지 평가하는 문제가 Evaluation Problem이다. 그리고, 이 시퀀스에서 어느 부분이 공정한 주사위를 사용한 결과인지, 어느 부분이 가중치가 적용된 주사위를 던진 부분인지 판단하는 문제가 Decoding Problem이다. 마지막으로 Learning Problem은 주사위에 가중치가 적용되었다면 어느 정도로 가중치가 적용되었는지, 공정한 주사위를 사용했다면 어느 정도로 공정한 주사위인지, 또는 얼마나 자주 딜러가 주사위를 바꾸는지 따위의, 변수들을 결정하는 문제이다. 즉, 다음과 같이 나타낼 수 있다.
1. Evaluation Problem
GIVEN : HMM m, sequence x
FIND : Prob[x | m]
2. Decoding Problem
GIVEN : HMM m, sequence x
FIND : sequence π of states that max Prob[x, π | m]
3. Learning Problem
GIVEN : HMM m, unspecified transition / emmision prob., sequence x
FIND : parameters θ = (e(i)(.), a(ij) that max P[x | θ]
통상적으로 첫 번째 Evaluation Problem과 Decoding Problem은 이를 해결하는 일반적인 알고리즘이 존재하지만 마지막 Learning Problem은 이를 해결하는 방법이 매우 복잡하고, 그 정도에 따라 난이도가 결정된다.
HMM에는 다음과 같은 기본적인 정의가 있다.
1. 알파벳(Alphabet, Symbol) Σ = { b1, b2, b3, b4, ...., bm }
2. 상태집합(Set of States) Q = { 1, .... K }
3. 변환 가능성(Transition Probalbility) : 상태 1에서 2로 변할 가능성, 예를 들어 a(ij)는 i에서 j로 상태가 변할 가능성을 표기한다.
4. 시작 가능성(Start Probability) a(0i) : 어떤 상태에서 시작할 가능성
5. 방출 가능성(Emission Probability) e(i)(b) : 어떤 상태에서 알파벳 집합 원소를 방출할 가능성.
e(i)(b) = P(x(i) = b | π(i) = K }, e(i)(b1) + .... + b(i)(b(m)) = 1 (모든 상태 1 .... K에 대해서, 여기서 π(i)는 현재 상태를 뜻한다)
이 정의를 이용한 예를 들어보면, 어떤 시점 t에서 영향을 미치는 것은 현재 상태 인자 π(t)이며, 이때 가능한 시퀀스의 표기는 다음과 같다.
P(π(t+1) = K | π(1) π(2) π(3) π(4) .... π(t), x(1) x(2) x(3) x(4) .... x(t) }
좀 더 구체적으로 예를 들어보자. 딜러가 주사위를 던졌을 때, x = 1, 2, 1, 5, 6, 2, 1, 6, 2, 4라는 시퀀스가 관찰되었다고 하자. 공정한 주사위에서는 각 숫자가 나올 확률이 1 / 6으로 모두 동일하지만, 가중치가 적용된 주사위에서 6이 나올 확률이 1 / 2이며, 나머지 수가 나올 확률은 1 / 10이라 하자. 또, 공정한 주사위를 사용했을 때 다음에 다시 공정한 주사위를 사용할 확률은 0.95, 가중치가 적용된 주사위를 사용했을 때 다음에도 가중치가 적용된 주사위를 사용할 확률은 0.95라 하자. 이때, 공정한 주사위를 사용했을 확률은 어떻게 될까? 즉, π = F(Fair), F, F, F, F, F, F, F, F, F일 확률은 얼마인가?
처음 시작 확률에서, 공정한 주사위를 사용할 확률과 가중치가 적용된 주사위를 사용할 확률이 1 / 2라고 했을 때, 다음과 같이 쓸 수 있다. 계산은 처음 시작 확률 * 그 상태에서 해당 알파벳(결과)을 방출할 확률 * 다음 상태로 전이될 확률을 곱하는 과정으로 이루어진다.
1 / 2 * P(1 | F) * P(F | F) * P(2 | F) * P(F | F) .. * P(4 | F) = 1 / 2 * (1 / 6)^10 * (0.95)^9 = 0.521 * 10^(-9)
그렇다면, 딜러가 가중치가 적용된 주사위를 사용할 확률 π = L(Loaded), L, L, L, L, L, L, L, L, L은 어떻게 되는가?
1 / 2 * P(1 | L) * P(L | L) * P(2 | L) * P(L | L) .... * P(4 | L) = 1 / 2 * (1 / 10)^8 * (1 / 2)^2 * (0.95)^9 = 0.79 * 10^(-9)
따라서, 이 시퀀스의 경우 가중치가 적용된 주사위를 사용하고 있을 확률이 공정한 주사위를 사용했을 확률보다 높다고 할 수 있다.
HMM 방법은 각 사건들이 독립사건이라고 전제하고 있다. 어떤 사건에 영향을 미치는 것은 바로 전의 상태 인자뿐이며, 경우에 따라서는 이 방법이 약점으로 지적되기도 한다.
