비터비 알고리즘(HMM) 계산기

상태는 보이지 않고 그 상태가 내놓은 관측만 보이는 모형입니다. 예를 들어 건강한지 열이 났는지는 직접 볼 수 없고 「정상·추움·어지러움」이라는 증상만 볼 수 있는 상황입니다. 상태끼리 옮겨 다니는 확률(전이)과 상태마다 어떤 관측을 내놓을 확률(방출)로 이뤄집니다.

관측열이 주어졌을 때 가장 그럴듯한 상태열 하나를 찾습니다. 걸음마다 「이 상태로 오는 가장 좋은 길」만 남기고 나머지는 버리는 동적계획법이라, 경우의 수가 상태 수의 관측 길이 제곱만큼 폭발하는데도 한 번만 훑으면 끝납니다. 1967년 앤드루 비터비가 통신 부호의 복호를 위해 만들었습니다.

비터비는 가장 좋은 경로 하나의 확률이고 전향은 모든 경로의 확률을 다 더한 값입니다. 표를 채우는 모양은 똑같고 최댓값을 쓰느냐 합을 쓰느냐만 다릅니다. 그래서 비터비 확률은 언제나 전향 확률보다 작거나 같습니다. 이 둘을 섞는 것이 가장 흔한 실수입니다.

확률을 그냥 곱하면 금세 0이 되어 버리기 때문입니다. 걸음마다 1보다 작은 수가 거듭 곱해져 이 도구의 기본 모형이라면 200걸음에 10⁻⁸⁹, 1,000걸음이면 배정밀도로도 그냥 0이 됩니다. 그러면 어느 경로가 나은지 가릴 수 없습니다. 로그를 취하면 곱셈이 덧셈이 되어 이 문제가 사라집니다.

음성 인식, 품사 태깅, 유전자 서열에서 유전자 영역 찾기, 통신 부호의 복호에 쓰입니다. 「보이지 않는 상태가 있고 그것이 내놓은 신호만 보인다」는 꼴이면 대체로 이 틀에 들어맞습니다.

각 줄의 합으로 나눠 1이 되게 고친 뒤 계산하고, 고쳤다는 것을 알려줍니다. 비율만 적어도 되도록 한 것인데, 원래 확률을 넣었다면 합이 1인지 확인하는 것이 좋습니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 모형과 관측열은 이 기기에만 남습니다.