前面已经介绍了隐马尔可夫模型，本篇博文主要是介绍用 viterbi 算法来解决 HMM 中的预测问题，也称为解码问题。
  维特比算法实际是用动态规划解隐马尔可夫模型预测问题，即用动态规划(dynamic programming)求概率最大路径（最优路径）。这时一条路径对应着一个状态序列。
  根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻t通过(it)∗<script type="math/tex" id="MathJax-Element-1">(i_t)^*</script>,那么这一路径从it∗<script type="math/tex" id="MathJax-Element-2">{i_t}^*</script>到终点iT∗<script type="math/tex" id="MathJax-Element-3">{i_T}^*</script>的部分路径，对于从it∗<script type="math/tex" id="MathJax-Element-4">{i_t}^{*}</script>到iT∗<script type="math/tex" id="MathJax-Element-5">{i_T}^*</script>的所有可能的部分路径来说，必须是最优的。因为假如不是这样，那么从i1∗<script type="math/tex" id="MathJax-Element-6">{i_1}^*</script>到终点iT∗<script type="math/tex" id="MathJax-Element-7">{i_T}^*</script>就有另一条更好的部分路径存在，如果把它和i1∗<script type="math/tex" id="MathJax-Element-8">{i_1}^*</script>到终点it∗<script type="math/tex" id="MathJax-Element-9">{i_t}^*</script>的部分路径连接起来，就会形成一条比原来的路径更优的路径，这是矛盾的。依据这一原理，我们只需从时刻t=1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直至得到时刻t=T<script type="math/tex" id="MathJax-Element-10">t=T</script>状态为i的各条路径的最大概率。时刻t=T<script type="math/tex" id="MathJax-Element-11">t=T</script>的最大概率即为最优路径的概率P∗<script type="math/tex" id="MathJax-Element-12">P^*</script>,最优路径的终结点iT∗<script type="math/tex" id="MathJax-Element-13">{i_T}^*</script>也同时得到。之后，为了找出最优路径的各个结点，从终结点iT∗<script type="math/tex" id="MathJax-Element-14">{i_T}^*</script>开始，由后向前逐步求得结点iT−1∗,...,i1∗<script type="math/tex" id="MathJax-Element-15">{i_{T-1}}^*,...,{i_1}^*</script>得到最优路径这就是维特比算法。

• viterbi 算法
  输入：模型λ=(A,B,π)<script type="math/tex" id="MathJax-Element-16">\lambda=(A,B,\pi)</script>和观测O=(o1,o2,...,oT)<script type="math/tex" id="MathJax-Element-17">O=(o_1,o_2,...,o_T)</script>;
  输出：最优路径(i1∗,...,iT−1∗,iT∗)<script type="math/tex" id="MathJax-Element-18">({i_1}^*,...,{i_{T-1}}^*,{i_T}^*)</script>.
  (1) 初始化
  

  δ1(i)=πibi(oi),i=1,2,...,N
  <script type="math/tex; mode=display" id="MathJax-Element-19">\delta_1(i)=\pi_ib_i(o_i), \qquad i=1,2,...,N</script>
  
  ψ1(i)=0,i=1,2,...,N
  <script type="math/tex; mode=display" id="MathJax-Element-20">\psi_1(i)=0, \qquad i=1,2,...,N</script>
  (2) 递推.对t=2,3,...,T<script type="math/tex" id="MathJax-Element-21">t=2,3,...,T</script>
  
  δt(i)=max[δt−1(j)aji]bi(ot),i=1,2,..,N;1≤j≤N
  <script type="math/tex; mode=display" id="MathJax-Element-22">\delta_t(i)=max[\delta_{t-1}(j)a_{ji}]b_i(o_t), \qquad i=1,2,..,N;1\leq j\leq N</script>
  
  ψt(i)=argmax[δt−1(j)aji],i=1,2,...,N;1≤j≤N
  <script type="math/tex; mode=display" id="MathJax-Element-23">\psi_t(i)=argmax[\delta_{t-1}(j)a_{ji}], \qquad i=1,2,...,N;1\leq j\leq N</script>
  (3) 终止
  
  P∗=maxδT(i),1≤j≤N
  <script type="math/tex; mode=display" id="MathJax-Element-24">P^*=max\delta_T(i), \qquad 1\leq j\leq N</script>
  
  iT∗=argmax[δT(i)],1≤j≤N
  <script type="math/tex; mode=display" id="MathJax-Element-25">{i_T}^*=argmax[\delta_T(i)], \qquad 1\leq j\leq N</script>
  (4)最优路径回溯. 对t=T−1,T−2,...,1<script type="math/tex" id="MathJax-Element-26">t=T-1,T-2,...,1</script>
  
  it∗=ψt+1(i∗t+1)
  <script type="math/tex; mode=display" id="MathJax-Element-27">{i_t}^*=\psi_{t+1}({i_{t+1}^*})</script>

• viterbi算法实现

package com.feng.nlp.algorithm;

import java.util.*;

/**
 * Created by lionel on 17/4/11.
 */
public class Viterbi {
    public static List<String> compute(String[] observe, String[] status, double[] start_p, double[][] transfer_p, double[][] observe_p) {
        double[][] theta = new double[observe.length][status.length];
        int[][] delta = new int[observe.length][status.length];
        transfermation(start_p, transfer_p, observe_p);
        for (int j = 0; j < status.length; j++) {
            theta[0][j] = start_p[j] + observe_p[j][0];
            delta[0][j] = 0;
        }
        Map<String, Integer> map = new HashMap<String, Integer>();
        int index = 0;
        for (String ele : observe) {
            if (map.containsKey(ele)) {
                continue;
            }
            map.put(ele, index);
            index++;
        }

        for (int i = 1; i < observe.length; i++) {
            for (int j = 0; j < status.length; j++) {
                int direction = 0;
                double prob = Double.MAX_VALUE;
                for (int k = 0; k < status.length; k++) {
                    double tmpProb = theta[i - 1][k] + transfer_p[k][j] + observe_p[j][map.get(observe[i])];
                    if (tmpProb < prob) {
                        prob = tmpProb;
                        direction = k;
                        theta[i][j] = prob;
                    }
                }
                delta[i][j] = direction;
            }
        }
//        for (int i = 0; i < theta.length; i++) {
//            for (int j = 0; j < theta[i].length; j++) {
//                System.out.print(theta[i][j] + " ");
//            }
//            System.out.println();
//        }
        double prob = Double.MAX_VALUE;
        int pos = 0;
        for (int j = 0; j < status.length; j++) {
            if (theta[observe.length - 1][j] < prob) {
                prob = theta[observe.length - 1][j];
                pos = j;
            }
        }
        List<String> res = new ArrayList<String>();
        res.add(status[pos]);
        //回溯路径
        for (int i = observe.length - 1; i > 0; i--) {
            res.add(status[delta[i][pos]]);
            pos = delta[i][pos];
        }

        Collections.reverse(res);
        return res;
    }

    public static void transfermation(double[] start_p, double[][] transfer_p, double[][] observe_p) {
        for (int i = 0; i < start_p.length; ++i) {
            start_p[i] = -Math.log(start_p[i]);
        }
        for (int i = 0; i < transfer_p.length; ++i) {
            for (int j = 0; j < transfer_p[i].length; ++j) {
                transfer_p[i][j] = -Math.log(transfer_p[i][j]);
            }
        }
        for (int i = 0; i < observe_p.length; ++i) {
            for (int j = 0; j < observe_p[i].length; ++j) {
                observe_p[i][j] = -Math.log(observe_p[i][j]);
            }
        }
    }


    public static void main(String[] args) {
        String[] observe = {"红", "白", "红"};
        String[] status = {"1", "2", "3"};
        double[] start_p = new double[]{0.2, 0.4, 0.4};
        double[][] transfer_p = new double[][]{
                {0.5, 0.2, 0.3},
                {0.3, 0.5, 0.2},
                {0.2, 0.3, 0.5}
        };
        double[][] observe_p = new double[][]{
                {0.5, 0.5},
                {0.4, 0.6},
                {0.7, 0.3}
        };
        List<String> result = compute(observe, status, start_p, transfer_p, observe_p);
        System.out.println(result);//[3, 3, 3]

    }
}

  测试用例来源于李航老师的《统计机器学习》的例子。

• 参考资料：《统计机器学习》，李航