은닉 마르코프 모델(Hidden Markov model)

여름날의 일기장이 있다고 합시다. 날씨는 적혀 있지 않고, 그날 먹은 아이스크림 개수(1–3개)만 적혀 있습니다. 날씨는 오늘 날씨에 따라 내일 날씨가 정해지는 마르코프 연쇄를 따르고, 더운 날에는 아이스크림을 많이, 추운 날에는 적게 먹는 경향이 있습니다. 이처럼 상태(날씨)는 숨어 있고 상태에 따라 확률적으로 나오는 관측(아이스크림)만 보이는 모델이 은닉 마르코프 모델입니다. 필요한 것은 처음 상태의 확률⁠(probability)⁠, 상태 사이의 전이 확률⁠(transition probability)⁠ $a_{rs}$, 상태마다 관측이 나올 조건부 확률⁠(conditional probability)⁠ $b_s(o)$입니다. 여기서는 첫날이 더울 확률 0.8, 더운 날 1·2·3개를 먹을 확률 0.2·0.4·0.4, 추운 날 0.5·0.4·0.1로 둡니다(교재에 자주 나오는 장난감 예입니다).

더운 날 다음 날도 더울 확률 , 추운 날 다음 날도 추울 확률 입니다. 그림 위쪽의 아이스크림 개수를 누르면 1→2→3으로 바뀝니다.

가장 그럴듯한 날씨열은 이고, 그 날씨열과 관측이 함께 일어날 확률은 입니다. 날씨열은 $2^8 = 256$가지라 모두 따져 볼 수도 있지만, 날이 T일이고 상태가 N개이면 $N^T$가지로 금방 감당할 수 없게 됩니다. 비터비 알고리즘은 날마다 '오늘 이 상태에서 끝나는 최선의 날씨열'만 기억합니다. 1967년 이탈리아 태생 미국 공학자 앤드루 비터비가 잡음 섞인 신호에서 오류 정정 부호⁠(error-correcting code)⁠를 풀려고 만든 방법입니다. 이것으로 충분한 까닭은 이렇습니다. 내일 '더움'에서 끝나는 최선의 날씨열에서 마지막 날을 떼어 내면, 남은 앞부분은 오늘 '더움'이나 '추움'에서 끝나는 최선의 날씨열이어야 합니다. 더 나은 앞부분이 있다면 그것으로 바꿔 끼워 더 좋은 날씨열을 만들 수 있기 때문입니다. 그래서 일은 $T N^2$에 비례하는 횟수의 곱셈으로 끝납니다. 편집 거리⁠(edit distance)⁠와 같은 동적 계획법⁠(dynamic programming)⁠입니다. 확률에 −로그를 씌우면 곱이 합으로, 최대가 최소로 바뀌어, 이 계산은 날짜별 상태를 점으로 둔 격자 그래프 위의 최단 경로⁠(shortest path)⁠ 찾기가 됩니다. 한 걸음씩 나아가는 계산은 거리표끼리 곱셈 대신 덧셈을, 덧셈 대신 최솟값을 쓰는 (min, +) 곱입니다(풍부화된 범주⁠, enriched category⁠). 실제 프로그램도 아주 작은 수가 이어 곱해져 0이 되지 않도록 로그로 계산합니다.

최대(max) 대신 합을 쓰면 전향 알고리즘⁠(forward algorithm)⁠이 되어, 모든 날씨열에 걸친 관측열 자체의 확률을 같은 격자로 구합니다($P(o_{1:T})$ = ). 이 값으로 베이즈 정리⁠(Bayes' theorem)⁠를 쓰면 '관측을 보았을 때 셋째 날이 더웠을 확률'처럼 관측을 본 뒤에 고친 확률(사후 확률⁠, posterior probability⁠)도 얻습니다. 거꾸로 관측만 잔뜩 있고 전이 확률과 방출 확률(상태가 관측을 내놓을 확률 $b_s(o)$)을 모를 때는 바움–웰치 알고리즘⁠(Baum–Welch algorithm)⁠으로 확률들을 배웁니다. 1960년대 말 미국 수학자 레너드 바움과 로이드 웰치가 내놓은 방법으로, 지금의 확률로 날마다 숨은 상태가 무엇이었을지 짐작하고, 그 짐작으로 전이와 방출의 횟수를 다시 세어 확률을 고치기를 되풀이합니다. 되풀이할 때마다 관측열의 확률이 줄지 않습니다. 중심으로 무리를 나누고, 나눈 무리로 중심을 다시 구하기를 되풀이하는 k-평균 군집⁠(k-means clustering)⁠도 같은 '번갈아 고치기' 계열(기댓값 최대화⁠(expectation–maximization)⁠, EM)의 방법입니다.

언어에서는 숨은 상태가 품사⁠(part of speech)⁠, 관측이 낱말입니다. Time flies like an arrow에서 flies는 동사일 수도 명사일 수도 있고, like는 전치사일 수도 동사일 수도 있습니다. 품사 사이의 전이 확률(명사 다음에 동사가 올 확률 등)과 품사별 낱말 확률을 말뭉치⁠(corpus)⁠에서 세어 두면, 비터비 알고리즘이 문장 전체에 가장 그럴듯한 품사열을 붙입니다. 음성 인식에서는 숨은 상태가 음소(뜻을 가르는 말소리의 최소 단위, 예를 들어 '발'과 '말'을 가르는 ㅂ과 ㅁ), 관측이 소리의 스펙트럼(짧은 순간의 소리를 진동수별 세기로 나눈 것)이었고, 신경망⁠(neural network)⁠ 이전의 음성 인식은 대부분 이 모델 위에 서 있었습니다.

이어지는 곳. 품사 전이 확률은 앞 품사로 다음 품사를 맞히는 것이니 품사열에 대한 n-그램⁠(n-gram)⁠ 모델입니다. 은닉 마르코프 모델은 화살표마다 확률을 붙이고 상태를 감춘 유한 오토마톤⁠(finite automaton)⁠으로 볼 수도 있습니다. 상태가 위치나 속도⁠(velocity)⁠처럼 연속적인 값이고, 상태의 변화와 관측이 선형이며 잡음이 정규분포⁠(normal distribution)⁠이면, 같은 '숨은 상태 → 관측' 구조가 칼만 필터⁠(Kalman filter)⁠가 됩니다. 1960년 헝가리 태생 미국 공학자 루돌프 칼만이 내놓은 방법으로, 잡음 섞인 측정값으로 움직이는 물체의 위치를 차례로 추정하며 GPS와 우주선 항법에 쓰입니다. 은닉 마르코프 모델은 확률 모델 가운데 '숨은 원인 → 보이는 결과' 구조의 가장 단순한 예입니다.