Publié le

viterbi 알고리즘 예제

“Viterbi 경로”와 “Viterbi 알고리즘”은 동적 프로그래밍 알고리즘을 적용하여 확률과 관련된 문제를 최대화하는 표준 용어가 되었습니다. [3] 예를 들어, 동적 프로그래밍 알고리즘을 구문 분석하는 통계에서 일반적으로 “Viterbi 구문 분석”이라고 하는 문자열의 단일 컨텍스트 없는 파생(구문 분석)을 검색하는 데 사용할 수 있습니다. [4] [5] [6] 다른 응용 프로그램은 관측값 시퀀스에 최대 가능성을 할당하는 트랙이 계산되는 대상 추적에 있습니다. [7] Viterbi 알고리즘은 비터비 경로라고 불리는 가장 가능성이 높은 숨겨진 상태의 시퀀스를 찾기 위한 동적 프로그래밍 알고리즘으로, 특히 마르코프 정보 소스와 숨겨진 마르코프의 맥락에서 관찰된 일련의 이벤트를 생성합니다. 모델. 이 알고리즘은 경로 X = X = ( x 1 , x 2 , 2 , … … 및 t) {displaystyle X =(x_{1}, x_{2}, ldots, x_{T}}} ,dots,s_{K}}}} 관찰을 생성하는 Y = (y 1, y 2 , y T) {표시 스타일 Y=(y_{1}, y_{2},ldots, y_{T})}}}를 y n{T=로 생성합니다. { o 1 , o 2 , … () 더 많은 가능한 상태 (건강, 발열, 질병1, 질병2 …) 또는 더 많은 가능한 관찰 (정상, 감기, 현기증, 떨림, 메스꺼움, 두통)이 있다면 알고리즘은 어떻게 작동할까요? 전환 및 방출 테이블은 훨씬 더 커질 것입니다. 테이블의 각 열을 계산할 때 더 많은 값을 거쳐야 합니다. 그러나 원리는 동일할 것입니다. 반복 Viterbi 디코딩이라는 알고리즘을 사용하면 주어진 숨겨진 Markov 모델과 가장 일치하는 관측값의 하위 시퀀스를 찾을 수 있습니다.

이 알고리즘은 터보 코드를 처리하기 위해 Qi Wang 등에서 제안합니다. [8] 반복 적인 Viterbi 디코딩 은 반복적으로 수정 된 Viterbi 알고리즘을 호출하여 수렴 될 때까지 필러의 점수를 다시 추정하여 작동합니다. “toqer”라는 단어를 관찰할 때 Viterbi 알고리즘을 사용하여 가장 가능성이 높은 “진정한 단어”를 이전과 동일한 방식으로 계산하고 진정한 단어 “tower”를 얻을 수 있습니다. Viterbi 알고리즘은 첫눈에 완전히 관련이없는 것처럼 보이는 많은 종류의 문제를 해결하는 데 사용할 수 있습니다. 실행 예제에서 전달/비터비 알고리즘은 다음과 같이 사용됩니다: Viterbi 알고리즘은 관찰을 기반으로 하며, 매일(및 각 상태)에 대한 최적의 경로는 전날(및 각 상태)에 대한 최적의 경로에서 쉽게 추론할 수 있습니다. 이 코드에서 start_probability는 환자가 처음 방문할 때 HMM이 어느 상태에 있는지에 대한 의사의 믿음을 나타냅니다 (그가 아는 것은 환자가 건강한 경향이 있다는 것입니다). 여기서 사용되는 특정 확률 분포는 평형 분포가 아니며, 이는 대략 {`Healthy`: 0.57, `발열`: 0.43}입니다.