HMM+维特比算法

一、简介

Viterbi 算法

考虑到穷举方法的缺点，可以采用：Viterbi 算法: 动态搜索最优状态序列，这样每个节点保存的是到当前节点的局部最优概率；依据最后一个时刻中概率最高的状态，逆向找其路径中的上一个最大部分最优路径，从而找到整个最优路径。

二、理论描述

隐含马尔可夫模型被认为是解决大多数自然语言处理问题快速、有效的方法，成功解决了复杂的语音识别、机器翻译等问题。
HMM是一个五元组(O,Q,O0,A,B)：
O:{o1….ot}是状态集合, 也称为观测序列；
Q:{q1…qv}是一组输出结果，也称隐序列；
aij=P(qj|qi): 转移概率分布；
bij=P(oj|qi): 发射概率分布；
O0是初始状态,有些还有终止状态。

维特比算法是以部分最优去获得全局最优，每个节点保存的是当前节点的局部最有概率，一局最后一个时刻中概率最高的状态，逆向找其路径中的上一个最大部分最优路径，从而找到整个最优路径。

三、算法描述

（1）HMM中计算概率矩阵

需要平滑数据，对数据每个元素值加一，然后逐个计算当前元素在该行中的概率。

public void computeProp(float[][] A) {//计算概率矩阵
        int i, j;
        float[] t = new float[A.length];
        //平滑数据，对数组每个元素值加一
        for (i = 0; i < A.length; i++) {
            for (j = 0; j < A[i].length; j++) {
                A[i][j] += 1;
                t[i] += A[i][j];
            }
        }
        //计算当前元素在该行中的概率
        for (i = 0; i < A.length; i++)
            for (j = 0; j < A[i].length; j++)
                A[i][j] /= t[i];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）维特比算法(长度为T的观测序列, 长度为N的状态图)

观察序列长度 T，状态个数N
for 状态s from 1 to N：do

//计算每个状态的概率，相当于计算第一观察值的隐状态t=1
     v[s,1] = a(0,s)*b(O1|s) //第一列的每一个=初始状态概率 * 发射概率
     back[s,1]=0 //回溯保存最大概率状态

//计算每个观察（词语）取各个词性的概率，保存最大者，从第二个开始，因为第一个是由初始状态概率决定。
for from 观察序列第二个 to T do：
    for 状态s from 1 to N：do
   
      v[s,t]=max（v[i,t-1]*a[i,s]*b(Ot | s) //当前状态=前一个状态*转移*发射（该状态/词性下词t的概率），保存最大者

      //保存回溯点，该点为前一个状态转移到当前状态的最大概率点
      back[s,t]=arg{1,N} max v[i,t-1]*a(i,s)
 //最后
  v[T]=max v[T]
  back[T] = arg{1,N} max v[T]
 //回溯输出隐状态序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

四、完整代码

hmm_viterbi.java

public class hmm_viterbi {

    public int[] Viterbi(float[][] A, float[][] B, String[] O) {
        int back[][] = new int[A.length][O.length];
        float V[][] = new float[A.length][O.length];
        double[] init = {0.2, 0.1, 0.1, 0.2, 0.3, 0.1};
        int i, s, k, t;

        for (i = 0; i < A.length; i++) {
            V[i][0] = (float) (init[i] * B[i][0]);
            back[i][0] = i;
        }
        //计算每个观察值的取隐状态中的最大概率
        for (t = 1; t < O.length; t++) {
            int[][] path = new int[A.length][O.length];
            //遍历每个隐状态，计算状态转移到当前状态的最大概率
            for (s = 0; s < A.length; s++) {
                float maxSProb = -1;
                int preS = 0;
                for (i = 0; i < A.length; i++) {
                    float prob = V[i][t - 1] * A[i][s] * B[s][t];//B[s][t]为隐状态s到观察值t的发射概率
                    if (prob > maxSProb) {
                        maxSProb = prob;
                        preS = i;
                    }
                }
                //保存该状态的最大概率
                V[s][t] = maxSProb;
                //记录路径
                System.arraycopy(back[preS],0,path[s],0,t);
                path[s][t]=s;
            }
            back=path;
        }


        //回溯路径
        float maxP = -1;
        int lastS = 0;
        for (s = 0; s < A.length; s++) {
            if (V[s][O.length - 1] > maxP) {
                maxP = V[s][O.length - 1];
                lastS = s;
            }
        }
        return back[lastS];
    }

//    计算概率矩阵
    public void computeProp(float[][] A) {
        int i, j;
        float[] t = new float[A.length];
        //平滑数据，对数组每个元素值加一
        for (i = 0; i < A.length; i++) {
            for (j = 0; j < A[i].length; j++) {
                A[i][j] += 1;
                t[i] += A[i][j];
            }
        }
        //计算当前元素在该行中的概率
        for (i = 0; i < A.length; i++)
            for (j = 0; j < A[i].length; j++)
                A[i][j] /= t[i];


        for (i = 0; i < A.length; i++) {
            for (j = 0; j < A[i].length; j++)
                System.out.print(A[i][j] + "    ");
            System.out.println();
        }

        System.out.println();
    }

    public static void main(String[] args) {
        //状态转移矩阵
        float A[][] = {

                {0, 0, 0, 48636, 0, 19}, {1973, 0, 426, 187, 0, 38}, {43322, 0, 1325, 17314, 0, 185}, {1067, 3720, 42470, 11773, 614, 21392}, {6072, 42, 4758, 1476, 129, 1522}, {8016, 75, 4656, 1329, 954, 0}};
        //发射矩阵
        float B[][] = {

                {0, 0, 0, 0, 0, 0, 69016, 0}, {0, 10065, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 5484, 0, 0, 0, 0}, {10, 0, 36, 0, 382, 108, 0, 0}, {43, 0, 133, 0, 0, 4, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 48809}};

        int i, j;
        //语料库词语
        String[] word = {"bear", "is", "move", "on", "president", "progress", "the", "."};
        //待标注句子
        String O[] = {"The", "bear", "is", "on", "the", "move", "."};
        //语料库词性
        String Q[] = {"/AT ", "/BEZ ", "/IN ", "/NN ", "/VB ", "/PERIOD "};
        String seq="Bear move on the president .";
        String Os[]=seq.split(" ");
        for (String w:O)
            System.out.println(w);

        float emission[][] = new float[B.length][O.length];

        hmm_viterbi hmmViterbi = new hmm_viterbi();
        hmmViterbi.computeProp(A);

        //计算观察序列的转移矩阵
        //根据待标注句子的词计算出每个单词的出现次数矩阵
        for (i = 0; i < O.length; i++) {
            int r = 0;
            for (int t = 0; t < word.length; t++) {
                if (O[i].equalsIgnoreCase(word[t]))
                    r = t;
            }
            for (j = 0; j < B.length; j++)
                emission[j][i] = B[j][r];
        }
        hmmViterbi.computeProp(emission);
        int path[];
        path=hmmViterbi.Viterbi(A, emission, O);

        for (i=0;i<O.length;i++){
            System.out.print(O[i]+Q[path[i]]);
        }

        for (int p:path)
            System.out.print(p+" ");

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

五、运行结果