Skip to content

[HMM] Viterbi algorithm

Jump to bottom
Myungchul Shin edited this page Sep 13, 2018 · 18 revisions 
1. 시간 t ( 1 ~ T )에서 각 상태 j ( 1 ~ N )별로  
    - delta t ( j ) 값 : 1개
    - delta 값은 최대값이므로 그러한 조건을 만족하는 이전 상태는 psi t ( j ) :  1개

2.  마지막 time T에서  delta T ( 1 ), delta T ( 2 ), ... , delta T ( N ) 중에서 
    최대값인 상태가 우리가 구하고자 하는 상태열(state sequence)의 마지막 상태

3. 이 상태를 q* ( T ) 라고 하자

4. q* ( T ) 상태에서 대응하는 이전 상태는 psi T ( q* ( T ) ) 에 저장되어 있다

5. back-tracking을 하면서 t=1 까지 돌아가면 해당 path가 최적의 해

* coding skill
  - viterbi algorithm을 실제로 코딩한다고 생각해보자. 
    lattice는 어떤 자료구조로 만들어야할까? 일반적으로 state stack을 사용한다.
    즉, 관측가능한 output sequences를 왼쪽에서 오른쪽으로 스캔하면서 
    stack에 모든 가능한 state를 `push`한다. 
    push하면서 path_prob, path_node를 계산한다. 
  - stack의 entry는 이러한 state 관련 정보를 구조체로 담고 있어야 한다. 예를 들어서,  
  typedef struct {
    int index;
    state_t state; // state 자체의 정보, begin/end offset, term의 begin/end pointer 등등
    int     next;
    int     child;
    double  path_prob;
    int     path_node; // back-tracking에 사용된다 
  } stack_entry_t;
  - 어떤 문제에서는 'start state ~ end state'까지 경로길이가 다르게 표현되는 경우도 있다.(async lattice)
    - 예를 들어서, 'abc' -> 'a b c'(3 states), 'ab c'(2 states), 'abc'(1 state)
    - 이런식으로 전이가 가능한 경우, 경유하는 상태의 수가 많으면 path_prob이 더 작아지는 경향이 있다. 
      즉, 짧은 path를 더 선호하게 된다.

6. 만약,  n-best 개의 path를 찾으려면 어떻게 해야할까? 
  - 아래 내용을 참조하자.
  • n-best path 등에 대한 간략한 정리
http://www.cs.rochester.edu/u/james/CSC248/Lec9.pdf

1. viterbi와 beam search 차이점
    - viterbi는 optimal search
    - beam search는 approximation
    - 모든 timestep에서 back pointer의 수는 동일
    - beam size가 state의 수와 같다면 viterbi와 동일
    - beam과 n-best는 아무 관련이 없다.
    - beam은 긴 sequence에서도 빠른 처리속도를
       얻는데 적합한 방식이다.

2. lattice는 sync, async 구조가 있음
    - time step마다 state가 존재하는 sync
    - path의 길이가 다를 수도 있는 async
       : timestep을 정의하기 애매하다
    - beam search는 sync 구조에서 사용가능
      : 같은 timestep에서 sorting을 해야하기 때문

3. lattice의 모양은 async인 경우가 많다
    - 예) abcde -> ab/cde, ab/c/de
    - 전이확률, 생성확률을 누적하면 path의 길이가
       짧은 쪽이 유리하게 되는데 이런 문제는 
       best-first search와 a* search 차이점을 보면
       힌트를 얻을 수 있지 않을까?
    - best-first search는 agenda라고 하는 ordered queue를
      사용하는데, 기본적으로 1-best viterbi와 같다
      다음 timestep으로 확장시 길이가 짧은 path가
      더 유리한 문제가 있으므로 a* search를 이용해서
      보정 가능하다.

4. n-best viterbi
    - 모든 state에 path_info(back_pointer, prob)을 하나씩
      유지하는 것이 1-best viterbi인데
    - 이러한 path_info를 배열로 n개 생성해야한다.
      [(back_pointer1, path_info_index1, prob1), (back_pointer2, path_info_index2, prob2), ...] 
    - 각각의 state에서 '(들어오는 state의 수) x n' 번 확률을 계산해서 정렬하고
      상위 n개에 해당하는
      path_info('이전 state', '이전 state의 path_info에서 index', '누적 prob')를 생성한다. 
    - 마지막 timestep(</s>)에서 정렬된 path_info n개에 대해
      backtracking을 하면 n-best path를 구성.
      여기서 주의할 점은, 마지막에서 back_pointer를 따라서 돌아갈 때
      path_info_index의 위치에 해당하는 path_info를 참조해야한다는 것이다. 
      예를 들면, 이전 timestep에서는 path_info 배열의 0번째가 아니라 
      1번째에서 그 이전 timestep으로 연결될 수 있다.
    - sync, async lattice에 무관하게 처리 가능하다.
    - n-best viterbi beam search라는 것도 있다
       : 단순히 beam 컨셉을 적용하면 되는데
         async lattice에서는 사용하기 곤란하다
    - n-best viterbi decoding을 위한 lattice stack 자료구조는 대략 아래와 같다. 

      /* path info for n-best decoding */
      typedef struct path_info {
	double	path_prob;	// accumulated prob
	int	path_node[2];	// back lattice no, its corresponding index of path_infos
      } path_info_t;

     /* lattice entry */
     typedef struct lattice {
	int	no;
	int	boff;	// begin offset
	int	eoff;	// end offset
	term_t*	bterm;	// begin term
	term_t*	eterm;	// end term
	int	next;		// next sibling on the stack
	int	child;		// child on the stack
	etype_info_t*	etype_info;	// link to etype info
	int		ipath_infos;	// top of path_infos
	path_info_t*	path_infos;	// for n-best path,  malloc(size=nbest+1)
     } lattice_t;

5. multipath search
    - lattice에서 러프한 방식으로 n-best path를 찾는다
    - 그 다음 좀더 정교한 knowledge를 이용해서
       path들을 정렬한다
    - two-path search라고도 부른다.
    - 전이확률, 생성확률 등의 계산이 곤란한 경우
      뭔가 다른 방식으로 처리할때 필요해보인다
Clone this wiki locally