Enginius/Machine Learning

HMM viterbi algorithm

아래의 정의는 wikipedia 에서 (http://en.wikipedia.org/wiki/Viterbi_algorithm)

Viterbi algorithm

The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events. These algorithms belong to the realm of information theory.

The algorithm makes a number of assumptions.

• First, both the observed events and hidden events must be in a sequence. This sequence often corresponds to time.
• Second, these two sequences need to be aligned, and an instance of an observed event needs to correspond to exactly one instance of a hidden event.
• Third, computing the most likely hidden sequence up to a certain point t must depend only on the observed event at point t, and the most likely sequence at point t − 1.

These assumptions are all satisfied in a first-order hidden Markov model.

The terms "Viterbi path" and "Viterbi algorithm" are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the "Viterbi parse".

The Viterbi algorithm was conceived by Andrew Viterbi in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. For more details on the history of the development of the algorithm see David Forney's article.[1] The algorithm has found universal application in decoding theconvolutional codes used in both CDMA and GSM digital cellular, dial-up modems, satellite, deep-space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognitionkeyword spottingcomputational linguistics, and bioinformatics. For example, in speech-to-text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

여기에 있는 내용을 바탕으로 VC로 만들어봤다.

Viterbi.zip

```
// Viterbi.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include
#include
#include

#define max2( a , b ) ( (a) < (b) ? (b) : (a) )
#define max3( a, b, c )  max2( (a) , max2( (b), (c) ) )
#define max4( a, b, c, d )  max3( (a) , (b), max2( (b), (c) ) )

int _tmain(int argc, _TCHAR* argv[])
{
// DATA 1
//*
#define nr_states			2		// hidden state 종류의 수
#define nr_visibles			3		// visible output 종류의 수
#define nr_observations		3		// 측정한 visibles의 수

// hidden_states
#define RAINY 0
#define SUNNY 1

// visible_observations (행렬 때문에 0부터 시작)
#define WALK  0
#define SHOP  1
#define CLEAN 2

// hidden_states의 종류
int states[nr_states] = { RAINY, SUNNY };

// 관측된 결과				Output data
int observation[nr_observations] = { WALK, SHOP, CLEAN };

// 초음 확률 prior			w
float start_probability[nr_states] = {0.6,0.4};		// hidden state의 초기 확률

// Transition matrix		A
float transiton_probability[nr_states][nr_states] = { {0.7,0.3},{0.4,0.6} };

// Emission matrix			B
float emission_probability[nr_states][nr_visibles]  = { {0.1,0.4,0.5 }, {0.6,0.3,0.1 }};
//*/

/*/ DATA 2
#define nr_states			3		// hidden state 종류의 수
#define nr_visibles			2		// visible output 종류의 수
#define nr_observations		3		// 측정한 visibles의 수

// hidden_states
#define U1  0
#define U2  1
#define U3	2

// visible_observations (행렬 때문에 0부터 시작)
#define RED 0
#define BLUE 1

// hidden_states의 종류
int states[nr_states] = { U1, U2 , U3  };

// 관측된 결과				Output data
int observation[nr_observations] = { RED, BLUE, RED };

// 초음 확률 prior			w
float start_probability[nr_states] = {0.3333333333, 0.3333333333, 0.3333333333};		// hidden state의 초기 확률

// Transition matrix		A
float transiton_probability[nr_states][nr_states] = { {0.3, 0.6, 0.1}, {0.5, 0.2, 0.3} , {0.4, 0.1, 0.5} };

// Emission matrix			B
float emission_probability[nr_states][nr_visibles]  = { {0.5 , 0.5} , {0.3333333333 , 0.6666666666}  , {0.75 , 0.25} };
//*/

//////////////////////////////////////////////////////////////////////////////////////////////
//								viterbi path를 실제로 구해보자								//
//////////////////////////////////////////////////////////////////////////////////////////////
int path_temp[nr_states][nr_observations];
int vpath[nr_observations];

float v[nr_states][nr_observations + 1];	// 1을 더한 것은 초기조건 0을 고려하기 위해서이다.

for (int time = 0; time <= nr_observations; time++)
{
// 현재 시간을 print
printf("\n\ntime: %d\n", time);

if(time == 0)
{
// time = 0, 즉 처음에 초기화 한다.
for (int i = 0; i 1 일 때는 이전 모든 이전 state에서 오는 최대값을 구해야 한다.
for (int i = 0; i < nr_states; i++)
{
//printf("state: %d \n", i);
// 각 state에 대해서 최대값을 구한다.
float v_max = 0, v_temp;
int v_max_j = 0;
for (int j = 0; j < nr_states; j++)
{
//j는 t-1 에서 state를 뜻한다.
v_temp = v[j][time-1] * transiton_probability[j][i];
//printf("v_temp%d: %f \n", i,v_temp);
if( v_temp > v_max )
{
v_max = v_temp;
v_max_j = j;
}
}
// v_max에는 현재 state i에 대한 최대v가 들어가있다.
// v_max_j에는 현재 state를 최대로 만들기 위한 t-1의 state 번호가 들어있다.

// 현재
path_temp[i][time-1] = v_max_j;
//printf("max_j: %d \n", path_temp[i][time-1]);

v[i][time] = v_max * emission_probability[i][ observation[time-1] ];
printf("v%d: %f \n", i,v[i][time]);
}

// 현재 시간 t에서 각 state의 확률이 들어있다.
// 모든 state중에 최대값을 구하자.
float v_max_temp = 0;
int v_max_i_temp = 0;
for (int i = 0; i < nr_states; i++)
{
// path를 지정한다. time-2를 한 이유는 time이 2일 때 1번 path를 알 수 있기 때문이고, C에서 배열은 0에서 시작하기 때문이다.
// 즉 path[0]가 time=1에서 hidden 상태를 나타낸다.

if ( v_max_temp < v[i][time] )
{
v_max_temp = v[i][time] ;
v_max_i_temp = i;

// 조금 이상하긴 하지만 이렇게 하면 될듯
vpath[nr_observations-1] = v_max_i_temp;
}
}
vpath[time - 2] = path_temp[v_max_i_temp][time-1];
}

} // for (int time = 0; time <= nr_observations; time++) //
// 마지막 path는 가장 확률이 높은 값으로 한다.

//* viterbi path를 출력하자
for (int time = 0; time < nr_observations; time++)
{
printf("path%d: %d \n", time, vpath[time] );
}
//*/

return 0;
}

```
실험 결과는 다음과 같다.

아래의 그림과 비교해 보면 viterbi 확룔과 path가 일치하는 것을 알 수 있다.

'Enginius > Machine Learning' 카테고리의 다른 글

 Expectation of X^n; X~N(u,sigma^2)  (0) 2011.10.24 2011.10.14 2011.10.13 2011.10.12 2011.10.07 2011.10.06