HMM+维特比算法

article/2025/10/3 23:18:58

一、简介

请添加图片描述

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

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

观察序列长度 T，状态个数N
for 状态s from 1 to N：do//计算每个状态的概率，相当于计算第一观察值的隐状态t=1v[s,1] = a(0,s)*b(O1|s) //第一列的每一个=初始状态概率 * 发射概率back[s,1]=0 //回溯保存最大概率状态//计算每个观察（词语）取各个词性的概率，保存最大者，从第二个开始，因为第一个是由初始状态概率决定。
for from 观察序列第二个 to T do：for 状态s from 1 to N：dov[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]//回溯输出隐状态序列

四、完整代码

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+" ");}
}