自然語言處理系列之Viterbi算法

  前面已經介紹了隐馬爾可夫模型，本篇博文主要是介紹用 viterbi 算法來解決 HMM 中的預測問題，也稱為解碼問題。

  維特比算法實際是用動态規劃解隐馬爾可夫模型預測問題，即用動态規劃(dynamic programming)求機率最大路徑（最優路徑）。這時一條路徑對應着一個狀态序列。

  根據動态規劃原理，最優路徑具有這樣的特性：如果最優路徑在時刻t通過 (it)∗ ,那麼這一路徑從 it∗ 到終點 iT∗ 的部分路徑，對于從 it∗ 到 iT∗ 的所有可能的部分路徑來說，必須是最優的。因為假如不是這樣，那麼從 i1∗ 到終點 iT∗ 就有另一條更好的部分路徑存在，如果把它和 i1∗ 到終點 it∗ 的部分路徑連接配接起來，就會形成一條比原來的路徑更優的路徑，這是沖突的。依據這一原理，我們隻需從時刻t=1開始，遞推地計算在時刻t狀态為i的各條部分路徑的最大機率，直至得到時刻 t=T 狀态為i的各條路徑的最大機率。時刻 t=T 的最大機率即為最優路徑的機率 P∗ ,最優路徑的終結點 iT∗ 也同時得到。之後，為了找出最優路徑的各個結點，從終結點 iT∗ 開始，由後向前逐漸求得結點 iT−1∗,...,i1∗ 得到最優路徑這就是維特比算法。

• viterbi 算法

  輸入：模型 λ=(A,B,π) 和觀測 O=(o1,o2,...,oT) ;

  輸出：最優路徑 (i1∗,...,iT−1∗,iT∗) .

  (1) 初始化

  δ1(i)=πibi(oi),i=1,2,...,N

  ψ1(i)=0,i=1,2,...,N

  (2) 遞推.對 t=2,3,...,T

  δt(i)=max[δt−1(j)aji]bi(ot),i=1,2,..,N;1≤j≤N

  ψt(i)=argmax[δt−1(j)aji],i=1,2,...,N;1≤j≤N

  (3) 終止

  P∗=maxδT(i),1≤j≤N

  iT∗=argmax[δT(i)],1≤j≤N

  (4)最優路徑回溯. 對 t=T−1,T−2,...,1

  it∗=ψt+1(i∗t+1)

• 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 = ; j < status.length; j++) {
            theta[][j] = start_p[j] + observe_p[j][];
            delta[][j] = ;
        }
        Map<String, Integer> map = new HashMap<String, Integer>();
        int index = ;
        for (String ele : observe) {
            if (map.containsKey(ele)) {
                continue;
            }
            map.put(ele, index);
            index++;
        }

        for (int i = ; i < observe.length; i++) {
            for (int j = ; j < status.length; j++) {
                int direction = ;
                double prob = Double.MAX_VALUE;
                for (int k = ; k < status.length; k++) {
                    double tmpProb = theta[i - ][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 = ;
        for (int j = ; j < status.length; j++) {
            if (theta[observe.length - ][j] < prob) {
                prob = theta[observe.length - ][j];
                pos = j;
            }
        }
        List<String> res = new ArrayList<String>();
        res.add(status[pos]);
        //回溯路徑
        for (int i = observe.length - ; i > ; 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 = ; i < start_p.length; ++i) {
            start_p[i] = -Math.log(start_p[i]);
        }
        for (int i = ; i < transfer_p.length; ++i) {
            for (int j = ; j < transfer_p[i].length; ++j) {
                transfer_p[i][j] = -Math.log(transfer_p[i][j]);
            }
        }
        for (int i = ; i < observe_p.length; ++i) {
            for (int j = ; 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[]{, , };
        double[][] transfer_p = new double[][]{
                {, , },
                {, , },
                {, , }
        };
        double[][] observe_p = new double[][]{
                {, },
                {, },
                {, }
        };
        List<String> result = compute(observe, status, start_p, transfer_p, observe_p);
        System.out.println(result);//[3, 3, 3]

    }
}
           

  測試用例來源于李航老師的《統計機器學習》的例子。

• 參考資料：《統計機器學習》，李航