鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

隐马尔科夫模型(HMM)学习之 viterbi算法

来源:互联网 作者:佚名 时间:2015-09-25 05:36
viterbi 算法 主要解决已知HMM和观察序列,找到最可能的隐藏状态,也就是所说的解码问题。解码在 语音 识别 中的应用就是,根据一段声音序列,找到最有可能对应的文字序列。 还是天气和水藻的这个例子,我们运用viterbi 算法 找出dry,damp,soggy对应的天气

   viterbi算法主要解决已知HMM和观察序列,找到最可能的隐藏状态,也就是所说的解码问题。解码在语音识别中的应用就是,根据一段声音序列,找到最有可能对应的文字序列。


   还是天气和水藻的这个例子,我们运用viterbi算法找出dry,damp,soggy对应的天气情况。所有的已知条件和之前那个前向算法都是一直的,不同之处就是求解的过程。


1.  根据初始概率和观察概率,计算t=0时刻的概率值,保存在delta数组的第一列


2.  计算t=i 时刻(i < T)状态j (j < M)下概率的值,选出最大的概率值maxVal,乘以观察概率保存到delta数组 中,然后将相应的索引值保存到path数组中。


3.  在t = T -1时刻,选出最大的那个概率值,最大概率值保存在prob中,同时用k记下对应的行号,并将k存入list的头部


4.  t从 T - 1开始循环到t=1,因为当前t时刻path数组中的值保存的是t-1时刻的行号,因此循环的取出该值,最后就是所要求的隐藏状态的路径了。



java版viterbi算法

package cn.yunzhisheng.hmm;


import java.util.LinkedList;

import java.util.List;


publicclass HMM {


publicint   M = 3;

// 转移矩阵

publicdouble[][] transferMatix = {

{0.500, 0.375, 0.125},

{0.250, 0.125, 0.625},

{0.250, 0.375, 0.375}

};


// 观察矩阵

publicdouble[][] observationMatix = {

{0.60, 0.20, 0.15, 0.05},

{0.25, 0.25, 0.25, 0.25},

{0.05, 0.10, 0.35, 0.50}

};

// 初始概率

publicdouble[] pi = {0.63, 0.17, 0.20};



public List<Integer> viterbi(int[] seq){

int T = seq.length;

// 保存计算的概率

double [][] delta = newdouble[M][T];

// 保存最佳路径

int [][] path = newint[M][T];

// 当前概率的值

double val = 0.0;

// 保存当前最大概率的值

double maxVal = 0.0;

// t-1时刻最大概率的索引

int maxIndex = 0;

// t = 0 用初始概率乘以相应观察矩阵的概率,保存到delta的第一列中

for(int j = 0; j < M; j++){

delta[j][0] = pi[j] * observationMatix[j][seq[0]];

}

for(int t = 1; t < T; t++){

for(int j = 0; j < M; j++){

maxVal = 0.0;

maxIndex= 0;

for(int i = 0; i < M; i++){

val = delta[i][t-1] * transferMatix[i][j];

if(val > maxVal){

// 保存最大概率

maxVal= val;

// 保存t-1时刻的索引

maxIndex = i;

}

}

// 将概率保存在delta数组中

delta[j][t] = maxVal * observationMatix[j][seq[t]];;

path[j][t] = maxIndex;

}

}

// 对最后一列,比较概率,找到最大概率的索引

double prob = 0.0;

int k = 0;

for(int j = 0; j < M; j++){

if(delta[j][T-1] > prob){

prob = delta[j][T-1];

k = j;

}

}

System.out.println("prob=" + prob);

LinkedList<Integer> list = new LinkedList<Integer>();

list.addFirst(k);

int row = k;

for(int t = T-1; t > 0; t--){

int v = path[row][t];

list.addFirst(v);

row = v;

}


return list;

}



publicstaticvoid main(String[] args) {

HMM hmm = new HMM();

// 观察序列

int [] seq = {0, 2, 3};

// 前向算法

//double p = hmm.forward(seq);

//System.out.println(p);

// 维特比算法

List<Integer> weather = hmm.viterbi(seq);

System.out.println(weather);

}

}


运行结果:

prob=0.01107421875

[0, 1, 2]


即最终的隐藏状态是:sunny,cloudy,rainy


注:http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/s3_pg3.html 这个网站计算有问题,它把状态矩阵给弄反了


我的计算结果和 umdhmm是一样的,同时手工计算的也是这个结果。



移动开发

网友评论
<