비터비 알고리즘

Viterbi 알고리즘은 특히 마르코프 정보원과 숨겨진 마르코프 모델(HMM)의 맥락에서 관측된 일련의 사건을 초래하는 가장 가능성이 높은 숨겨진 상태의 시퀀스의 최대 사후 확률 추정치를 얻기 위한 동적 프로그래밍 알고리즘이다.

이 알고리즘은 CDMA 및 GSM 디지털셀룰러, 다이얼업모뎀, 위성통신, 심공간통신 및 802.11 무선LAN에서 사용되는 컨볼루션코드 디코딩에 보편적으로 적용되고 있습니다.그것은 또한 현재 음성 인식, 음성 합성, ^[1]분리, 키워드 스팟팅, 컴퓨터 언어학, 생물 정보학에도 일반적으로 사용된다.예를 들어 음성-텍스트(음성 인식)에서 음향신호는 관측된 일련의 이벤트로 취급되며 텍스트 문자열은 음향신호의 "숨겨진 원인"으로 간주된다.Viterbi 알고리즘은 음향 신호가 주어졌을 때 가장 가능성이 높은 텍스트 문자열을 찾습니다.

역사

비터비 알고리즘은 1967년에 노이즈가 많은 디지털 통신 ^[2]링크 상의 컨볼루션 코드의 디코딩 알고리즘으로 제안한 Andrew Viterbi의 이름을 따서 명명되었습니다.그러나 그것은 비터비, 니들맨, 운쉬, 바그너와 ^[3]피셔의 발견을 포함하여 적어도 7개의 독립적인 발견을 가진 다중 발명의 역사를 가지고 있다.이것은 1987년에 음성 태그 부착의 한 방법으로 자연 언어 처리에 도입되었습니다.

Viterbi 경로 및 Viterbi 알고리즘은 ^[3]확률과 관련된 최대화 문제에 동적 프로그래밍 알고리즘을 적용하는 표준 용어가 되었습니다.예를 들어, 통계 해석에서 동적 프로그래밍 알고리즘을 사용하여 일반적으로 "비터비 해석"^[4]^[5]^[6]이라고 불리는 문자열의 가장 가능성이 높은 단일 컨텍스트 프리 파생(파스)을 검출할 수 있습니다.또 다른 애플리케이션은 일련의 ^[7]관측치에 최대우도를 할당하는 트랙이 계산되는 목표 추적에 있습니다.

내선번호

max-sum 알고리즘(또는 max-product 알고리즘)이라고 불리는 비터비 알고리즘의 일반화는 베이지안 네트워크, 마르코프 랜덤 필드 및 조건부 랜덤 필드 등 다수의 그래픽 모델에서 잠재 변수의 전체 또는 일부 서브셋의 가장 가능성이 높은 할당을 찾기 위해 사용될 수 있다.잠복변수는 일반적으로 변수와 변수들 사이의 제한된 수의 선형구조와 함께 숨겨진 마르코프 모델(HMM)과 유사한 방식으로 연결될 필요가 있다.일반적인 알고리즘은 메시지 전달을 포함하며 신념 전파 알고리즘(전향-후향 알고리즘의 일반화)과 실질적으로 유사합니다.

반복 비터비 디코딩이라고 불리는 알고리즘을 사용하면 주어진 숨겨진 마르코프 모델에 가장 잘 일치하는 관찰의 연속성을 찾을 수 있다.이 알고리즘은 터보 ^[8]코드를 다루기 위해 Qi Wang 등에 의해 제안되었다.반복적인 Viterbi 디코딩은 변경된 Viterbi 알고리즘을 반복적으로 호출하여 컨버전스가 될 때까지 필러 점수를 재추정함으로써 기능합니다.

대체 알고리즘인 Lazy Viterbi 알고리즘이 ^[9]제안되었습니다.실용적으로 관심이 있는 어플리케이션의 경우 합리적인 노이즈 조건 하에서 레이지 디코더(Lazy Viterbi 알고리즘 사용)는 원래의 Viterbi 디코더(Viterbi 알고리즘 사용)보다 훨씬 빠릅니다.원래의 Viterbi 알고리즘은 가능한 결과의 트렐리스 내의 모든 노드를 계산하는 데 반해, Lazy Viterbi 알고리즘은 순서대로 평가하는 노드의 우선순위 목록을 유지합니다.또, 통상, 같은 결과에 대해서 필요한 계산의 수는 통상의 Viterbi 알고리즘보다 적습니다(단, 결코 많지는 않습니다).그러나 하드웨어에서는 병렬화가 쉽지^{[clarification needed]} 않습니다.

유사 코드

이 알고리즘은 경로 $X=(x_{1},x_{2},\ldots ,x_{T})$ $=$ ( $X=(x_{1},x_{2},\ldots ,x_{T})$ , $X=(x_{1},x_{2},\ldots ,x_{T})$ 2, $X=(x_{1},x_{2},\ldots ,x_{T})$ … , $X=(x_{1},x_{2},\ldots ,x_{T})$ ) { $displaystyle$ X=( $x_{1$ }, $x_{2},\ldots,x_{T}}$ 을 $X=(x_{1},x_{2},\ldots ,x_{T})$ 를) 생성합니다. 이 경로는 x $x_{n}\in S=\{s_{1},s_{2},\dots ,s_{K}\}$ † $=$ { $x_{n}\in S=\{s_{1},s_{2},\dots ,s_{K}\}$ , s $x_{n}\in S=\{s_{1},s_{2},\dots ,s_{K}\}$ , $x_{n}\in S=\{s_{1},s_{2},\dots ,s_{K}\}$ $}$ { $displaystyle x_n},$ {1}, {in}, { $1},$ {1},S}, {1}의}입니다. $displaystyle$ Y $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ ( $y_{$ 1}, $y_{2},\ldots,y_{T}),$ $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ = $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ { $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ 1, $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ 2, $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ N $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ }({ $displaystyle$ $y_{n$ }\ $in$ O= { $o_1},o_2},\dots, o_{$ N $Y=(y_{1},y_{2},\ldots ,y_{T})$ $N$ $y_{n}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ $N$ 서 $displaystyle$ n은 number입니다.

$K\times T$ K × $K\times T$ (\ $displaystyle$ K $\times$ T $)$ 의 $K\times T$ 2차원 테이블이 구성됩니다.

$T1의$ 각 $T_{1}[i,j]$ $T_{1}[i,j]$ [ $i$ , $j]({$ $T_{1}[i,j]$ T_ ${$ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ $])$ 에는 $T_{1}[i,j]$ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ 까지 X ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ ^ $=$ ( x ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ ^ 1, ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ ^ 2, ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})$ $^$ j ) { $displaystyle$ {X} $=$ hat { $x} }$ {\hat} {1}의 확률이 저장됩니다 $.$ ${\hat {x}}_{j}=s_{i}$ i ${\hat {x}}_{j}=s_{i}$ {\ $displaystyle {x}_{j}=s_{i$ }}: Y $=$ ( $Y=(y_{1},y_{2},\ldots ,y_{j})$ $Y=(y_{1},y_{2},\ldots ,y_{j})$ , $Y=(y_{1},y_{2},\ldots ,y_{j})$ , $Y=(y_{1},y_{2},\ldots ,y_{j})$ $Y=(y_{1},y_{2},\ldots ,y_{j})$ $){displaystyle$ Y=( $y_{1}, y_{2},$ \ $ldots, y_{j$ 를 $Y=(y_{1},y_{2},\ldots ,y_{j})$ 합니다.
$T2의$ $T_{2}[i,j]$ $T_{2}[i,j]$ [ $i,$ $]({$ displaystyle $T_{2}$ $T_{2$ $}[i,$ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ $])$ 에는 $T_{2}[i,j]$ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ 까지 X ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ ^ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ ( ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ 1, ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ ^ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ , ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ …, ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ ^ - 1, ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ ^ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ )의 x ${\hat {x}}_{j-1}$ - ${\hat {x}}_{j-1}$ ({ $displaystyle$ { $x}_j-1$ $x}_{1},{\hat {x}_{2},\ldots,{\hat {x}_{j-1},{\hat {x}=s_{i}}}$ $\forall j,2\leq j\leq T$ ${\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}=s_{i})$ $\forall j,2\leq j\leq T$ J $\forall j,2\leq j\leq T$ $\forall j,2\leq j\leq T$ $\forall j,2\leq j\leq T$ $\forall j,2\leq j\leq T$ { $displaystyle j, 2$ \ $leq$ j\ $leq$ T $}$

테이블 $T_{1}[i,j],T_{2}[i,j]$ 는 $T_{1}[i,j],T_{2}[i,j]$ [ $T_{1}[i,j],T_{2}[i,j]$ , $T_{1}[i,j],T_{2}[i,j]$ , $T_{1}[i,j],T_{2}[i,j]$ $T_{1}[i,j],T_{2}[i,j]$ , $]{$ $displaystyle T_{1$ } [ $i$ , $j$ ], $T_{2}[i,j]$ 는 $T_{1}[i,j],T_{2}[i,j]$ K $t$ j + $K\cdot j+i$ { $displaystyle$ K \ $cdot$ j + $i$ $K\cdot j+i$ 의 오름차순으로 채워집니다.

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

1 [

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

,

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

]

=

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

k (

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

[

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

,

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

-

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

])

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

A

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

B

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

j

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

) {

displaystyle T_{1

} [

i

, j ]= \

max

_ {

k

} { (

T

_ { 1

]

\

cdot

A _ {

ki

} \

CDOT B

_ {

y

}

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

} } 。

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

[

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

=

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

k

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

(

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

[

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

,

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

-

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

])

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

B

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

) {

displaystyle T_{2}[i

,

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

j ]=\

operatorname

{

snapmax

}

T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

_ { { k

}

{ (

T_{1}[ k

,

j-1]\cdot A_i}

A ki $($ $스타일 A_{ki})$ $B_{iy_{j}}$ $B_{iy_{j}}$ y $($ B_ ${iy_{j})$ 로 $B_{iy_{j}}$ 지정합니다. $B_{iy_{j}}$ $B_{iy_{j}}$ j(\ $display style$ B_{ $iy_{j}})$ 는 $B_{iy_{j}}$ 음이 아니고 k $(\displaystyle$ k})와는 $k$ 독립적이므로 후자의 식에 표시할 필요가 $B_{iy_{j}}$ .

입력

관측 $O=\{o_{1},o_{2},\dots ,o_{N}\}$ O $=$ { $O=\{o_{1},o_{2},\dots ,o_{N}\}$ 1, $O=\{o_{1},o_{2},\dots ,o_{N}\}$ 2, $O=\{o_{1},o_{2},\dots ,o_{N}\}$ $O=\{o_{1},o_{2},\dots ,o_{N}\}$ N $}$ {{ $displaystyle$ O=\{ $o_{1$ }, $o_{$ 2},\ $dots, o_{N$
상태 $S=\{s_{1},s_{2},\dots ,s_{K}\}$ S $S=\{s_{1},s_{2},\dots ,s_{K}\}$ { $S=\{s_{1},s_{2},\dots ,s_{K}\}$ , $S=\{s_{1},s_{2},\dots ,s_{K}\}$ 2 , $S=\{s_{1},s_{2},\dots ,s_{K}\}$ , $S=\{s_{1},s_{2},\dots ,s_{K}\}$ $S=\{s_{1},s_{2},\dots ,s_{K}\}$ $}$ { $displaystyle$ S = \ { $s$ _ { s _ {1} , $s$ _ {2 $}$ , \ $dots$ , s $_$ { $K$ } $S=\{s_{1},s_{2},\dots ,s_{K}\}$ ,
초기 확률 $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ = ( $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ , $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ , $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ 2, ... , ${\$ $\Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})$ ) { $displaystyle$ \Pi = ( \ $pi$ _ {1} , \ $pi$ _ {2} , $\pi$ _ { $K$ $\pi _{i}$ $}$ ) $\pi _{i}$ $x_{1}=s_{i}$ { \ $displaystyle$ $\pi$ _ { $i$ $}$ { $K}$ ) 。
일련의 관측치 Y $Y=(y_{1},y_{2},\ldots ,y_{T})$ ( $Y=(y_{1},y_{2},\ldots ,y_{T})$ , $Y=(y_{1},y_{2},\ldots ,y_{T})$ 2 $Y=(y_{1},y_{2},\ldots ,y_{T})$ , $Y=(y_{1},y_{2},\ldots ,y_{T})$ , $Y=(y_{1},y_{2},\ldots ,y_{T})$ ) { $displaystyle$ Y $=$ ( $y$ _ {1 $}$ $, y$ _ {2 $}$ , \ $ldots$ , y _ { $T$ } ) ( $시간$ t { $style$ $t$ }의 $t$ $o_{i}$ 가 $o_{i}$ { $y_{t}=o_{i}$ }= $y_{t}=o_{i}$ ${i$ 인 $Y=(y_{1},y_{2},\ldots ,y_{T})$ $y_{t}=o_{i}$ 경우)
$크기$ $K\times K$ × $(\displaystyle$ K $\times$ K)의 $A$ $K\times K$ 트랜지션 매트릭스 A $(\$ $displaystyle A_{ij})$ 는 $A_{ij}$ $s_{i}$ $(\$ })에서 $s_{i}$ $s_{j}$ $(\$ 로의 트랜지션 확률을 $A_{ij}$ 합니다.
크기 $K\times N$ × $N$ 의 방출 $매트릭스$ B(\ $displaystyle$ B $)$ 는 $B$ $(\$ 가 $K\times N$ $B_{ij}$ $s_{i}$ $(\$ 에서 $(\$ 를 $o_{j}$ 관찰할 확률을 저장하도록 $B_{ij}$ .

산출량

가장 가능성이 높은 숨겨진 상태 $X=(x_{1},x_{2},\ldots ,x_{T})$ X $X=(x_{1},x_{2},\ldots ,x_{T})$ ( $X=(x_{1},x_{2},\ldots ,x_{T})$ , $X=(x_{1},x_{2},\ldots ,x_{T})$ $X=(x_{1},x_{2},\ldots ,x_{T})$ , $X=(x_{1},x_{2},\ldots ,x_{T})$ , $X=(x_{1},x_{2},\ldots ,x_{T})$ ) { $displaystyle$ X = ( $x_{1},x_{2},\ldots,x_{T}}$

함수 VITERBI $(O,S,\Pi ,Y,A,B):X$   $(O,S,\Pi ,Y,A,B):X$   $(O,S,\Pi ,Y,A,B):X$   $(O,S,\Pi ,Y,A,B):X$   $,$   $, B$ 각 $(O,S,\Pi ,Y,A,B):X$   $i=1,2,\ldots ,K$  i $(O,S,\Pi ,Y,A,B):X$  $i=1,2,\ldots ,K$ , $i=1,2,\ldots ,K$ 2, $i=1,2,\ldots ,K$ (\ $displaystyle i$ = $i=1,2,\ldots ,K$ 1,  $2,\ldots,$  K $i=1,2,\ldots ,K$ ) $T_{1}[i,1]\leftarrow \pi _{i}\cdot B_{iy_{1}}$   $T_{1}[i,1]\leftarrow \pi _{i}\cdot B_{iy_{1}}$  [ ],각  $j=2,3,\ldots ,T$  j  $j=2,3,\ldots ,T$ , $j=2,3,\ldots ,T$ , $j=2,3,\ldots ,T$   $j=2,3,\ldots ,T$   ${\displaystyle$  j $=2,3,\ldots,T}$ 는 $j=2,3,\ldots ,T$  각  $i=1,2,\ldots ,K$ 에 대해 i  $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  $i=1,2,\ldots ,K$ , $i=1,2,\ldots ,K$ , $i=1,2,\ldots ,K$  {\ $display$  i $=1,2,\ldots,$ K $i=1,2,\ldots ,K$  $}$ 는 $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ T1 [ $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ j] ←  $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ k $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ [ $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  - 1 $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ ])를 수행합니다 $T_{1}[i,j]\gets \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ [ $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  arg $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ k (  $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ 1 [ $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  , $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  -  $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ ]) $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$   $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  B  $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$  y $T_{2}[i,j]\gets \arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}$ ) \  $displaystyle T_{2$ } [ $i$  ,  $j$ ]\ $gets \ display$ style \  $max$ _ { k } { (  $T$ _ { 1 $}$  [ k ,  $j$ - 1 ]\  $cdot$  A _ ki _ {  $CD _$ { i } $T}\gets \max$  _ ${k}{(T_{1}[k,T])}$   $x_{T}\leftarrow s_{z_{T}}$   $z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}$  $x_{T}\leftarrow s_{z_{T}}$   $x_{T}\leftarrow s_{z_{T}}$   $x_{T}\leftarrow s_{z_{T}}$   $x_{T}\leftarrow s_{z_{T}}$ {\ $displaystyle x_{$  $T}\왼쪽 화살표 s_{z_{$  $j=T,T-1,\ldots ,2$  $x_{T}\leftarrow s_{z_{T}}$  $j=T,T-1,\ldots ,2$   $j=T,T-1,\ldots ,2$   $j=T,T-1,\ldots ,2$  - 1 $j=T,T-1,\ldots ,2$ 、 ... , 2 $j=T,T-1,\ldots ,2$  $j=T,T-1,\ldots ,2$ {  $z_{j-1}\leftarrow T_{2}[z_{j},j]$  j $z_{j-1}\leftarrow T_{2}[z_{j},j]$  $x_{j-1}\leftarrow s_{z_{j-1}}$   $T$ - 1 $j=T,T-1,\ldots ,2$  $z_{j-1}\leftarrow T_{2}[z_{j},j]$   $x_{j-1}\leftarrow s_{z_{j-1}}$  $z_{j-1}\leftarrow T_{2}[z_{j},j]$  [  $z_{j-1}\leftarrow T_{2}[z_{j},j]$ ,  $j$  $]$  \  $displaystyle z$ _ { j $z_{j-1}\leftarrow T_{2}[z_{j},j]$ } \  $displaydisplay T$ _ {  $z$  $x_{j-1}\leftarrow s_{z_{j-1}}$  { j $z_{j-1}\leftarrow T_{2}[z_{j},j]$ } [ $z$ _ { j } }  $x_{j-1}\leftarrow s_{z_{j-1}}$ 1 $x_{j-1}\leftarrow s_{z_{j-1}}$ - $x_{j-1}\leftarrow s_{z_{j-1}}$ _  $displaystylefload$

Python에 가까운 간결한 설명:

# 확률 == p.Tm: 트랜지션 매트릭스.Em: 배출 매트릭스.함수 viterbi(O, S, δ, Tm, Em): best_path trelis ← 행렬(길이(S), 길이(O) # 각 관측치가 주어진 각 상태의 p.를 보유합니다.포인터 ← 매트릭스(길이(S), 길이(O)) # 백포인터를 최상의 이전 상태로 유지하려면 # 시간 0에서 각 숨겨진 상태의 페이지 결정...s가 범위(길이(S): trelis[s, 0] ← δ[s] * Em[s, O[0] #... 그 후 각 상태의 가장 가능성이 높은 이전 상태 추적, 범위(1, 길이(O): s가 범위(길이(S) k)인 경우: k ← arg(k, olis[1])] pointers[s, o] ← k best_path ← list() k ← argmax(k in treellis[k, length(O)-1]) # 범위 o에 대한 최적의 최종 상태의 k를 찾습니다(length(O)-1, -1, -1). # 마지막 관찰에서 역추적.best_path.insert(0, S[k]) # 가장 가능성이 높은 경로 k ← 포인터[k, o] # 이전 상태를 삽입하여 이전 상태를 가장 잘 반환하는 best_path를 찾습니다.

설명.

상태 $공간$ S(\ $displaystyle$ S $S$ $초기$ 확률 $\pi _{i}$ i $(\$ $displaystyle$ i $)$ 및 $\pi _{i}$ $상태$ i $(\displaystyle$ i)에서 $i$ $상태$ i(\ $displaystyle$ i $)$ 로의 $i$ 이행 $a_{i,j}$ i $(\$ 를 $a_{i,j}$ 가진 숨겨진 마르코프 모델(HM)이 주어졌다고 가정합니다.{\ $displaystyle$ j $j$ 예를 들어 $y_{1},\dots ,y_{T}$ $y_{1},\dots ,y_{T}$ $y_{1},\dots ,y_{T}$ $(\$ 가장 가능성이 높은 상태 $x_{1},\dots ,x_{T}$ 1, $x_{1},\dots ,x_{T}$ …, $x_{1},\dots ,x_{T}$ T $(\$ {})가 표시됩니다 $.$ 관측치를 생성하는 T $}}$ 은 $x_{1},\dots ,x_{T}$ (는) 반복^[10] 관계에 의해 주어진다.

{begin {1,k}&=\mathrm {P}{big (}y_{1}\k'big}\cdot \pi _{k},\V_{t,k}&\max _{x\in S}\left(\mathrm {P}\big {p}\t}\t}\cdot {pi _{big}\end { aligned}

$V_{t,k}$ 서 V t $V_{t,k}$ {\ $displaystyle V_{t,k}$ 는 $V_{t,k}$ $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ 큰 상태 $시퀀스$ P $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ 1, $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ , $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ , $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ $)$ {\ $displaystyle \mathrm {P}(\$ big (} $x_{1$ },\ $dots, y_{1})$ 의 첫 번째 t를 담당할 $\mathrm {P} {\big (}x_{1},\dots ,x_{t},y_{1},\dots ,y_{t}{\big )}$ 확률입니다. $스타일$ k $}$ 을 $k$ (를) 최종 상태로 지정합니다.Viterbi 경로는 두 번째 방정식에서 사용된 $상태$ x $(\displaystyle$ x $)$ 를 $x$ 기억하는 포인터를 저장하여 가져올 수 있습니다. $V_{t,k}$ $\mathrm {Ptr} (k,t)$ r ( $\mathrm {Ptr} (k,t)$ $,$ ) $\mathrm {Ptr} (k,t)$ （ \ $displaystyle$ \ $mathrm$ { Ptr $（ k$ , $t$ ）） $t>1$ $V_{t,k}$ $V_{t,k}$ t $t>1$ > $1$ 、 $t>1$ $V_{t,k}$ \ $displaystyle$ V $x$ _ ${ t$ , $k$ } 、 $t$ $= 1$ 이면k \ $displaystyle$ k $t=1$ 의 $\mathrm {Ptr} (k,t)$ $V_{t,k}$ $k$ $x$ 을 반환하는 함수라고 합니다.

디스플레이 스타일T}&=\arg \max _{x\in S}(V_{T,x}),\x_{t-1}&=\mathrm {Ptr}(x_{t},t)\end { aligned}}

여기서는 arg max의 표준 정의를 사용합니다.

이 구현의 복잡성은 O $O(T\times \left|{S}\right|^{2})$ × $O(T\times \left|{S}\right|^{2})$ 2 $)({$ $displaystyle$ O $(T\times\left {S}\right$ ^{ $2$ 입니다. 내부 루프의 최대값이 현재 상태로 직접 링크되는 상태(즉, k $\display k$ 에서 $k$ jdisplay에 $대한$ 엣지가 있음)에서만 반복됨으로써 더 나은 추정치가 존재합니다. $style$ j $}$ 입니다.상각분석을 사용하면 복잡도가 O $O(T\times (\left|{S}\right|+\left|{E}\right|))$ × ( $O(T\times (\left|{S}\right|+\left|{E}\right|))$ $O(T\times (\left|{S}\right|+\left|{E}\right|))$ ) $O(T\times (\left|{S}\right|+\left|{E}\right|))$ { $display style$ O $(T\times (\left {S}\right +\left {E}\right$ 인 것을 알 수 있습니다. $E$ 서E { $display style$ E $}$ 는 $E$ 그래프의 가장자리 수입니다.

예

마을 사람들 모두가 건강하거나 열이 있고, 마을 의사만이 각각의 열 여부를 판단할 수 있는 마을을 생각해보자.의사는 환자에게 어떻게 느끼는지 물어보고 열을 진단한다.마을 사람들은 보통, 어지럽거나 춥다고만 대답할 수 있다.

의사는 환자의 건강 상태가 별개의 마르코프 사슬처럼 작동한다고 믿는다."건강"과 "열"의 두 가지 상태가 있지만, 의사는 직접 관찰할 수 없습니다. 그것들은 의사에게 숨겨져 있기 때문입니다.환자의 건강 상태에 따라 매일 의사에게 "정상적으로 느껴진다", "추운 느낌이 든다", "현기증이 난다"고 말할 가능성이 있다.

관찰(정상, 감기, 어지러움)은 숨겨진 상태(건강, 발열)와 함께 숨겨진 마르코프 모델(HMM)을 형성하며 Python 프로그래밍 언어로 다음과 같이 나타낼 수 있습니다.

관찰하다 = ("정상", "차가워", "실패") 미국. = ("건강", '열') start_p = {"건강": 0.6, '열': 0.4} 트랜스_p = {     "건강": {"건강": 0.7, '열': 0.3},     '열': {"건강": 0.4, '열': 0.6}, } 방출_p = {     "건강": {"정상": 0.5, "차가워": 0.4, "실패": 0.1},     '열': {"정상": 0.1, "차가워": 0.3, "실패": 0.6}, }

이 코드에는start_p는 환자가 처음 방문했을 때 HMM이 어떤 상태인지에 대한 의사의 믿음을 나타냅니다(의사가 알고 있는 것은 환자가 건강한 경향이 있다는 것 뿐).여기서 사용되는 특정 확률 분포는 평형 분포가 아니며, 평형 분포는 (전이가능성이 주어짐) 대략적으로{'Healthy': 0.57, 'Fever': 0.43}.그transition_p는 기본 마르코프 사슬의 건강 상태 변화를 나타냅니다.이 예에서 오늘날 건강한 환자는 내일 열이 날 확률이 30%에 불과합니다.그emit_p기본 조건(건강 또는 발열)이 주어졌을 때 가능한 각 관찰(정상, 감기 또는 어지러움)의 가능성을 나타냅니다.건강한 환자는 정상이라고 느낄 확률이 50%이고 열이 있는 환자는 현기증을 느낄 확률이 60%이다.

주어진 HMM의 그래픽 표현

3일 연속 내원하면 첫날은 정상, 둘째 날은 감기, 셋째 날은 어지러움을 느끼게 된다.의사는 질문을 합니다: 이러한 관찰을 설명할 수 있는 환자의 건강 상태의 가장 가능성이 높은 순서는 무엇입니까?이는 Viterbi 알고리즘에 의해 응답됩니다.

방어하다 비터비(관찰하다, 미국., start_p, 트랜스_p, 방출_p):     V = [{}]     위해서 세인트 에 미국.:         V[0] [세인트] = {"prob": start_p[세인트] * 방출_p[세인트] [관찰하다[0]], "실패": 없음.}     # t > 0일 때 Viterbi 실행     위해서 t 에 범위(1, 렌(관찰하다)):         V.추가하다({})         위해서 세인트 에 미국.:             max_tr_prob = V[t - 1] [미국.[0]] ["prob"] * 트랜스_p[미국.[0]] [세인트]             prev_st_selected = 미국.[0]             위해서 프리버전 에 미국.[1:]:                 tr_prob = V[t - 1] [프리버전] ["prob"] * 트랜스_p[프리버전] [세인트]                 한다면 tr_prob > max_tr_prob:                     max_tr_prob = tr_prob                     prev_st_selected = 프리버전              최대_prob = max_tr_prob * 방출_p[세인트] [관찰하다[t]]             V[t] [세인트] = {"prob": 최대_prob, "실패": prev_st_selected}      위해서 선 에 할 수 있다(V):         인쇄물(선)      옵트 = []     최대_prob = 0.0     베스트_st = 없음.     # 가장 가능성이 높은 상태와 그 역추적 취득     위해서 세인트, 데이터. 에 V[-1].항목들():         한다면 데이터.["prob"] > 최대_prob:             최대_prob = 데이터.["prob"]             베스트_st = 세인트     옵트.추가하다(베스트_st)     이전의 = 베스트_st      # 첫 번째 관찰까지 백트랙을 따라가다     위해서 t 에 범위(렌(V) - 2, -1, -1):         옵트.삽입하다(0, V[t + 1] [이전의] ["실패"])         이전의 = V[t + 1] [이전의] ["실패"]      인쇄물 ("국가의 단계는" + " ".합류하다(옵트) + "일 확률이 가장 높은%s" % 최대_prob)  방어하다 할 수 있다(V):     # 사전에서 단계별 표를 인쇄하다     산출하다 " " * 5 + "     ".합류하다(("%3d" % i) 위해서 i 에 범위(렌(V)))     위해서 주 에 V[0]:         산출하다 "%.7초: " % 주 + " ".합류하다("%.7초" % ("%lf" % v[주] ["prob"]) 위해서 v 에 V)

함수viterbi는 다음 인수를 사용합니다.obs는 관찰의 순서입니다(예:['normal', 'cold', 'dizzy'];states은닉 상태의 집합입니다.start_p시작 확률입니다.trans_p이행 확률입니다.emit_p방출 확률입니다.코드의 단순화를 위해 관찰 시퀀스는obs빈칸이 아니라trans_p[i] [j]그리고.emit_p[i] [j]모든 상태 i, j에 대해 정의됩니다.

실행 예에서는 forward/Viterbi 알고리즘이 다음과 같이 사용됩니다.

비터비(관찰하다,         미국.,         start_p,         트랜스_p,         방출_p)

스크립트의 출력은 다음과 같습니다.

$ python viterbi_syslog.py 0 1 2 정상: 0.300 0.08400 0.00588 발열: 0.04000 0.02700 0.01512 상태 단계는 가장 높은 확률 0.01512의 건강 발열입니다.

이것은 관찰 결과가['normal', 'cold', 'dizzy']주정부에서 생성되었을 가능성이 높다.['Healthy', 'Healthy', 'Fever']즉, 관찰된 활동을 볼 때 환자는 첫째 날과 둘째 날(그날 추위에도 불구하고)에 건강했을 가능성이 가장 높았고 셋째 날에만 열이 났다.

Viterbi 알고리즘의 연산은 트렐리스 다이어그램으로 시각화할 수 있습니다.Viterbi 패스는 기본적으로 이 트렐리를 통과하는 최단 경로입니다.

소프트 출력 비터비 알고리즘

Soft Output Viterbi Algorithm(SOVA)은 기존의 Viterbi 알고리즘의 변형입니다.

SOVA는 입력 심볼의 priori 확률을 고려하여 결정의 신뢰성을 나타내는 소프트 출력을 생성하는 수정된 경로 메트릭을 사용한다는 점에서 기존의 Viterbi 알고리즘과는 다릅니다.

SOVA의 첫 번째 단계는 생존자 경로의 선택이며, 각 순간마다 하나의 고유 노드 t를 통과합니다.각 노드에는 2개의 브런치가 수렴되어 있기 때문에(한쪽 브런치는 서바이버 패스를 형성하도록 선택되고 다른 한쪽 브런치는 폐기됨), 선택한 브런치와 폐기된 브런치 사이의 브런치 메트릭(또는 비용)의 차이는 선택 시 오류의 양을 나타냅니다.

이 비용은 슬라이딩 윈도 전체(통상 최소 5개의 제약조건 길이)에 걸쳐 누적되며, 이는 Viterbi 알고리즘의 하드비트 판정의 신뢰성에 대한 소프트 출력 측정값을 나타냅니다.

「」를 참조해 주세요.

레퍼런스

^ 자비에르 앵구라 외 연구진, "스피커 디어라이제이션: 최근의 연구 리뷰"는 19개를 회수했다.2010년 8월 IEEE TASLP
^ 2005년 4월 29일, G. David Forney Jr: Viterbi 알고리즘: 개인 이력
^ ^a ^b Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. p. 246.
^ Schmid, Helmut (2004). Efficient parsing of highly ambiguous context-free grammars with bit vectors (PDF). Proc. 20th Int'l Conf. on Computational Linguistics (COLING). doi:10.3115/1220355.1220379.
^ Klein, Dan; Manning, Christopher D. (2003). A* parsing: fast exact Viterbi parse selection (PDF). Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL). pp. 40–47. doi:10.3115/1073445.1073461.
^ Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). "AUGUSTUS: Ab initio prediction of alternative transcripts". Nucleic Acids Research. 34 (Web Server issue): W435–W439. doi:10.1093/nar/gkl200. PMC 1538822. PMID 16845043.
^ Quach, T.; Farooq, M. (1994). "Maximum Likelihood Track Formation with the Viterbi Algorithm". Proceedings of 33rd IEEE Conference on Decision and Control. Vol. 1. pp. 271–276. doi:10.1109/CDC.1994.410918.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)
^ Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Iterative Viterbi Decoding, Trellis Shaping, and Multilevel Structure for High-Rate Parity-Concatenated TCM". IEEE Transactions on Communications. 50: 48–55. doi:10.1109/26.975743.
^ A fast maximum-likelihood decoder for convolutional codes (PDF). Vehicular Technology Conference. December 2002. pp. 371–375. doi:10.1109/VETECF.2002.1040367.
^ Xing E, 슬라이드 11.

일반 참고 자료

Viterbi AJ (April 1967). "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm". IEEE Transactions on Information Theory. 13 (2): 260–269. doi:10.1109/TIT.1967.1054010. (주의: Viterbi 디코딩 알고리즘은 섹션 IV에 설명되어 있습니다).구독이 필요합니다.
Feldman J, Abou-Faycal I, Frigo M (2002). "A Fast Maximum-Likelihood Decoder for Convolutional Codes". Proceedings IEEE 56th Vehicular Technology Conference. Vehicular Technology Conference. Vol. 1. pp. 371–375. CiteSeerX 10.1.1.114.1314. doi:10.1109/VETECF.2002.1040367. ISBN 978-0-7803-7467-6. S2CID 9783963.
Forney GD (March 1973). "The Viterbi algorithm". Proceedings of the IEEE. 61 (3): 268–278. doi:10.1109/PROC.1973.9030. 구독이 필요합니다.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.2. Viterbi Decoding". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Rabiner LR (February 1989). "A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626. (HMM 의 전송 알고리즘과 Viterbi 알고리즘에 대해 설명합니다).
신할, R, 고드프리드 T. Tousaint, "수정된 비터비 알고리즘을 사용한 텍스트 인식 실험", 패턴 분석 및 기계 지능에 관한 IEEE 트랜잭션, Vol. PAMI-l, 1979년 4월, 페이지 184–193.
신할, R, 고드프리드 T. Toussaint, "소스 통계에 대한 수정된 Viterbi 알고리즘의 민감도", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.PAMI-2, 1980년 3월, 페이지 181–185.

외부 링크

Wikibooks에서 Java, F#, Clojure, C# 구현
칩 플레밍의 비터비 디코딩을 사용한 컨볼루션 코딩 튜토리얼
비터비 알고리즘에 대한 설명을 포함하는 숨겨진 마르코프 모델 툴킷(C에 구현됨)의 튜토리얼
Andrew J. Viterbi 박사의 Viterbi 알고리즘(scholarpedia.org).

실장

Mathematica는 확률적 프로세스에 대한 지원의 일부로 구현된다.
Susa 신호 처리 프레임워크는 여기서 순방향 오류 수정 코드 및 채널 이퀄라이제이션에 대한 C++ 구현을 제공합니다.
C++
C#
자바
자바 8
줄리아(HMBase).jl)
펄
프롤로그
하스켈
가세요
SFIHM에는 Viterbi 디코딩용 코드가 포함되어 있습니다.

[1] 자비에르 앵구라 외 연구진, "스피커 디어라이제이션: 최근의 연구 리뷰"는 19개를 회수했다.2010년 8월 IEEE TASLP

[2] 2005년 4월 29일, G. David Forney Jr: Viterbi 알고리즘: 개인 이력

[slp-3] Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. p. 246.

[4] Schmid, Helmut (2004). Efficient parsing of highly ambiguous context-free grammars with bit vectors (PDF). Proc. 20th Int'l Conf. on Computational Linguistics (COLING). doi:10.3115/1220355.1220379.

[5] Klein, Dan; Manning, Christopher D. (2003). A* parsing: fast exact Viterbi parse selection (PDF). Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL). pp. 40–47. doi:10.3115/1073445.1073461.

[6] Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). "AUGUSTUS: Ab initio prediction of alternative transcripts". Nucleic Acids Research. 34 (Web Server issue): W435–W439. doi:10.1093/nar/gkl200. PMC 1538822. PMID 16845043.

[7] Quach, T.; Farooq, M. (1994). "Maximum Likelihood Track Formation with the Viterbi Algorithm". Proceedings of 33rd IEEE Conference on Decision and Control. Vol. 1. pp. 271–276. doi:10.1109/CDC.1994.410918.{{cite conference}}: CS1 maint: 여러 이름: 작성자 목록(링크)

[8] Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Iterative Viterbi Decoding, Trellis Shaping, and Multilevel Structure for High-Rate Parity-Concatenated TCM". IEEE Transactions on Communications. 50: 48–55. doi:10.1109/26.975743.

[9] A fast maximum-likelihood decoder for convolutional codes (PDF). Vehicular Technology Conference. December 2002. pp. 371–375. doi:10.1109/VETECF.2002.1040367.

[10] Xing E, 슬라이드 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search

비터비 알고리즘

네임스페이스

더

목차

역사

내선번호

유사 코드

예

소프트 출력 비터비 알고리즘

「」를 참조해 주세요.

레퍼런스

일반 참고 자료

외부 링크

실장

Search

비터비 알고리즘

역사

내선번호

유사 코드

예

소프트 출력 비터비 알고리즘

「 」를 참조해 주세요.

레퍼런스

일반 참고 자료

외부 링크

실장

「」를 참조해 주세요.