Viterbiアルゴリズム学習(コードと注釈付き)
詳細コード:https://github.com/SunnyCat2013/viterbi-algorithm研二は音声認識の授業でviterbiアルゴリズムを書いたことがある.最近HMMを復習している時、viterbiの実現をよく覚えていないような気がして、暇を見つけてもう一度復習しました.例は李航の『統計学習方法』P 18610.3を参考にした.用語がわからなければ、P 1730.1を見てみましょう.
#include
#include
#include
using namespace std;
int main(){
// 《 》P186, 10.3。 P173 10.1
// ( , )
double pi[3] = { 0.2, 0.4, 0.4 }; // ( )
int q = 0;
for (auto _: pi) q++;
double A[3][3] = { 0.5, 0.2, 0.3, 0.3, 0.5, 0.2, 0.2, 0.3, 0.5 }; // (A[i][j] i j )
double B[3][2] = { 0.5, 0.5, 0.4, 0.6, 0.7, 0.3 }; // ( , 、 )
// int output[] = { 0, 1, 0 , 1}; // : 、 、 、
int output[] = { 0, 1, 0}; // : 、 、
int T = 0;
//
for (auto o: output) T++;
cout << "T: " << T << endl;
double **delta = new double *[T]; // ,delta[i][j] i , j 。
for (int i; i < T; i++) {
delta[i] = new double[q];
}
int psi[T][q];
// 1 delta
int color = output[0];
cout << "output should be:
" << "0.1\t0.16\t0.28" << endl;
cout << "init delta[0][i]" << endl;
for (int i = 0; i < q; i ++) {
delta[0][i] = pi[i] * B[i][color];
cout << delta[0][i] << "\t";
}
cout << endl;
cout << endl;
for (int i = 1; i < T; i++) { // T - 1
color = output[i];
for (int j = 0; j < q; j++) { // ,
double i_j_pro[q]; // i, j , i - 1 q
for (int k = 0; k < q; k++) {
// i_j_pro[k] = delta[i - 1][k] * A[k][j];
i_j_pro[k] = delta[i - 1][k] * A[k][j] * B[j][color]; // B( )
}
// i_j_pro
int idx = 0;
double imax = i_j_pro[idx];
for (int k = 1; k < q; k++) {
if (i_j_pro[k] > imax) {
imax = i_j_pro[k];
idx = k;
}
}
delta[i][j] = imax;
psi[i][j] = idx;
cout << "Time: " << i << "\t" << "delta: " << delta[i][j] << "\t" << "Choose box: " << psi[i][j] << endl;
}
cout << endl;
}
// decode
j = argmax(delta[i][j])
int path[T];
int i = T - 1;
int idx = 0;
double imax = delta[i][idx];
for (int k = 1; k < q; k++) {
if (delta[i][k] > imax) {
imax = delta[i][k];
idx = k;
}
}
path[i] = idx;
// , psi[i + 1][ ]
for (int i = T - 2; i >= 0; i--) {
path[i] = psi[i + 1][path[i + 1]];
}
// , output {0, 1, 0} , :The best path: begin -> 2 -> 2 -> 2 -> end
cout << "The best path: begin -> ";
for (auto p: path) {
cout << p << " -> ";
}
cout << "end" << endl;
return 0;
}