学步园

算法简介：

Viterbi 算法又叫维特比算法，其是HMM模型中在给出观测序列O，以及状态转移举证M 和 状态-观测矩阵Q之后，求解能够最佳解释序列O的状态序列S的一种动态规划算法。

如果你觉得句子太长，或太拗口，直接看下图：

其中：

•   标记为O的 [0|1] 序列是观测序列， 
•   标记为S的序列中横向的箭头即状态在根据转移矩阵M进行转移，
•   其中S序列与O序列之间向下的箭头表示根据状态生成观测的概率，也即Q矩阵。

假设我们已知观测序列O，即图片Bottom位置的0、1序列

则图片Top位置的用红框框起来的0、1序列就是对应的S序列，即我们所说的在给定矩阵M和Q之后，能最佳地解释O的序列。

算法C实现：

算法的实现也很简单，主要包含两步：

1. 从前到后遍历序列，计算每个观测的最大生成概率。

    在计算过程中，当前观测只依赖于上一个观测的结果，即马氏性。

    每个观测计算的概率为截止目前整条序列生成的最大概率，同时记录当前观测是有上一个观测的哪种状态生成的。

2. 从后向前回溯，得到序列S

    根据1中在每个观测点记录的上一个最佳状态进行回溯即可。

    具体实现如下：

/* ========================================================
 *   Copyright (C) 2014 All rights reserved.
 *   
 *   filename : viterbi.c
 *   author   : ***
 *   date     : 2014-12-19
 *   info     : 
 * ======================================================== */

#include <math.h>
#include <string.h>
#include "viterbi.h"

/* ****************************************
 * @param l   : input 0|1 vector 
 * @param o   : output[smoothed] 0|1 vector
 * @param n   : vector length
 * @param r_t : rate for stat <--> stat
 * @param r_o : rate for stat <--> observ
 * ****************************************/
int viterbi(int * l, int * o, int n, int r_t, int r_o){
    // check params 
    if (!l || !o || r_t < 1 || r_o < 1){
        // return fail
        return -1;
    }

    int i = 0;
    double r_t_ = log(r_t);
    double r_o_ = log(r_o);
    double ls0 = 0.0, ls1 = 0.0, cs0 = 0.0, cs1 = 0.0;
    double ps0 = 0.0, ps1 = 0.0;

    // prev_state for trace back
    int (*pre_s)[2] = (int(*)[2])malloc(sizeof(int[2]) * n);

    // init pre_state and output vector
    memset(pre_s, 0, sizeof(int[2]) * n);
    memset(o, 0, sizeof(int) * n);

    // init the begin stat distribute
    ls0 = (l[0] == 0 ? r_o_ : 0.0);
    ls1 = (l[0] == 1 ? r_o_ : 0.0);

    // pass through to calculate max prob
    for (i = 1; i < n ; i++){
        ps0 = ls0 + r_t_ + (l[i] == 0 ? r_o_ : 0.0);
        ps1 = ls1 +        (l[i] == 0 ? r_o_ : 0.0);
        if (ps0 >= ps1){
            cs0 = ps0; pre_s[i][0] = 0;
        }
        else{
            cs0 = ps1; pre_s[i][0] = 1;
        }
        ps0 = ls0 +        (l[i] == 1 ? r_o_ : 0.0);
        ps1 = ls1 + r_t_ + (l[i] == 1 ? r_o_ : 0.0);
        if (ps0 >= ps1){
            cs1 = ps0; pre_s[i][1] = 0;
        }
        else{
            cs1 = ps1; pre_s[i][1] = 1;
        }
        ls0 = cs0; ls1 = cs1;
    }

    // end state with the max prob
    o[n - 1] = cs0 >= cs1 ? 0 : 1;

    // trace back for prev state
    for (i = n - 2; i >= 0; i--){
        o[i] = pre_s[i + 1][o[i + 1]];
    }

    // free the trace pre states
    free(pre_s);
    pre_s = NULL;
    
    // return success
    return 0;
}

测试代码如下：

int main(){
    int a[15] = {0,0,1,0,0,1,1,1,0,1,1,0,0,0,0};
    int b[15] = {0,0,1,0,0,1,1,1,0,1,1,0,0,0,0};
    int c = viterbi(a,b,15,10,5);
    int i = 0;
    printf("before smooth:\n");
    for (; i < 15; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
    printf("after smooth:\n");
    for (i = 0; i < 15; i++){
        printf("%d ", b[i]);
    }
    printf("\n");
}

测试结果：

before smooth:
0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 
after smooth:
0 0 0 0 0 1 1 1 1 1 1 0 0 0 0