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; }