Skip to content

(10.02)W09_L04 Viterbi Decoding Algorithm

Jump to bottom
elecsoul edited this page Oct 12, 2018 · 1 revision

https://youtu.be/O1U2NWaSYn4

승관(2018.10.02):

  • Viterbi Decoding Algorithm이 Decoding Problem의 해결의 위해 가장 많이 사용된다.

  • Step1: Initialize를 해준다.

  • Step2: V를 Growth 하는 방향으로 Iteration 해준다.

  • Step3: 특정 K값을 찾아서 Whole Sequence로 돌아 갈수 있다.

  • Underflow problem이 발생할수 있기 때문에 Log 도메인에서 계산힌다.

대하(2018.10.02):
이번 시간에는 지난 주에 하려던 backward probability를 구하는 방법을 알아보았다.
바로 viterbi decoding algorithm인데, 이는 tracing assembly line scheduling에 의해서 빠르게 계산된다.

결국에는 z(latent variable)을 가지고 최적의 V_k를 찾는 문제이다.

점점 마지막이 다가오니 게을러지는 것 같다...

민규(2018.10.02):
오늘은 Viterbi decoding 알고리즘에 대해서 배웠다. 이전에 forward 와 backward prob.의 곱형태로 특정 t 시간에서의 latent factor가 가장 most probable한 k를 찾는 것이다. 이제 이것을 decoding 해야하는데 이것을 Viterbi 알고리즘을 통해서 푸는 것이다. 이것을 쓰는 이유는 우리가 latent variable 하나가 아닌 전체 시퀀스의 latent variable을 알아내고자 하기 때문이다. 식 유도가 되면 결과적으로 V에 대한 재귀형태가 나와서 recursive하게 풀 수 있으며, 그와 동시에 다이나믹 프로그래밍으로 더 효율적으로 해결할 수 있다. 그리고 이에 대한 예시를 통해서 이해를 도왔다. 물론 완벽하게 이해는 못했다 ㅋ. 아무튼 단점이 있는 확률이다 보니 state가 많아지면 underflow가 발생한다. 그래서 실제 구현에서는 log로 스케일 변환 후 연산을 수행한다.

성빈(2018.10.02):
Fow back 특정타임 t에서 레이턴트 팩터가 특정 클러스터에 속할 확률
-> 싱글레이턴트 한계점
전체에 대해서 하려면 디코딩이 필요하다 이때 사용하는 알고리즘이
비터비 알고리즘이다 공장라인 최단시간 예시를 통해 살짝 보았는데
T시간까지 반복해가면서 Vt와 어떤 이전의 assignment가 likely한지 확인한다?
그럼 VT가 나옴 ㅇㅇ(잘 모르겠다)
실제로는 Undeflow 문제가 발생하는데 log를 취해서 해결한다
(곱셈이 덧셈으로 바뀌게 됨) 아...

진구(2018.10.02):
잘 이해가 안 되었었는데 공장의 예를 보니 좀 와닿았다. 역시 예시가 중요.
약간 다르다면 우리 여기에서는 확률이라는 점?
시퀀셜한 무언가가 계속 들어올 때 어느 것이 가장 확률이 높은가? 이것을 구하는게 결국 HMM인 건가?!
약간 알듯말듯 하다.
확률의 곱을 여러번 하면 값이 매우 작아지므로 실제로는 로그를 취해서 씀.

Clone this wiki locally