HMM-维特比算法 第一章
假定现在隐含态是s1,s2,s3；观测状态是A,B
隐含态之间的转移情况如下图1:
文章图片
上图1,2,3对应的就是隐含态s1,s2,s3之间的转移情况，然后他们之间的输出状态A,B之间的概率如下表
文章图片
现在要计算最有可能输出观测序列是O={ABAB}的隐含序列。
把上面问题抽象成如下网络模型:
文章图片
即计算如下的条件概率P(O|隐含状态组合序列)的最大值:
argmaxP(O|隐含状态组合序列)
可以计算P(O|隐含状态组合序列)的所有可能:P(O|s1,s1,s1,s1), P(O|s2,s1,s1,s1)......P(O|s3,s3,s3,s3)，然后找到里面最大的概率，从而也就知道了隐含状态组合序列。但是这种方法开销巨大，解决办法是根据概率不随时间变化的特性，来减小复杂度。
第二章 给定一个观察序列和HMM，寻找最有可能的隐含状态序列。像前向算法一样，我们定义局部概率δ，即到达网络中某个状态时的概率。这里的局部概率和前向算法的概率不同，前向算法的概率是所有路径的概率是求和，而这里的局部概率是计算最有可能的路径的概率，即概率最大的那个。
【HMM之维特比算法】对于图2而言，网络中的每一个状态，都有一个到达该状态的最可能路径。举例而言:t=4，如下3个状态，都有一个到达此状态的最佳路径。
文章图片
我们称这些路径是局部最佳路径，也都对应一个相关联的概率，即局部概率δ。δ(i,t)表示的是t时刻，到达状态i的最大的概率，其所对应的隐含态序列就是最大概率的隐含状态序列，当t=T时，就是观测到状态的最有可能的隐含状态序列。
和前向算法类似，分别计算t=1和t>1时刻的局部概率。
t=1时，由于之前并不存在状态，我们用初始概率和输出概率来作为t=1时刻的局部概率，如下式(1)所示:
文章图片
t>1时，我们递归地利用t-1时刻的局部概率来计算t时刻的局部概率
文章图片
.
文章图片
在图4中，可能会有如下三种结果:
(隐含状态序列)s1x
(隐含状态序列)s2x
(隐含状态序列)s3x
我们要计算其中最有可能的路径。根据马尔科夫的假设:给定一个序列，一个状态的发生只依赖于前面n个状态，当n=1时，即一阶马尔科夫时，状态x发生的概率只取决于前面的一个状态，即:
P(到达状态最可能路径)*P(x|t-1最有可能状态)*P(观测状态|x)
用符号表示就是:
文章图片
第三章 接下来是简单的Python代码实现:
#! /usr/bin/env python
#! -*- coding=utf-8 -*-from numpy import *
import numpy as np
import random
import copy#HMM-viterbi算法
def hmm_viterbi():
Nstate = 3
Nobs = 2
T = 4
init_prob = [1.0,0.0,0.0]
trans_prob = np.array([[0.4,0.6,0.0],[0.0,0.8,0.2],[0.0,0.0,1.0]])
emit_prob = np.array([[0.7,0.3],[0.4,0.6],[0.8,0.2]])
obs_seq = [0,1,0,1] #(ABAB)
#单独计算t=1时刻的局部概率
partial_prob = zeros((Nstate,T))
path = zeros((Nstate,T))
for i in range(Nstate):
partial_prob[i,0] = init_prob[i] * emit_prob[i,obs_seq[0]]
path[i,0] = i #计算t>1时刻的局部概率
for t in range(1,T,1):
newpath = zeros((Nstate,T))
for i in range(Nstate):
prob = -1.0
for j in range(Nstate):
nprob = partial_prob[j,t-1] * trans_prob[j,i] * emit_prob[i,obs_seq[t]]
if nprob > prob:
prob = nprob
partial_prob[i,t] = nprob
newpath[i,0:t] = path[j,0:t]
newpath[i,t] = i
path = newpath
prob = -1.0
j = 0
print path
for i in range(Nstate):
if(partial_prob[i,T-1] > prob):
prob = partial_prob[i,T-1]
j = i
print path[j,:]
if __name__ == '__main__':
hmm_viterbi()
推荐阅读
- 机器学习算法系列（七）-对数几率回归算法（一）（Logistic Regression Algorithm）
- 机器学习算法系列（六）- 弹性网络回归算法（Elastic Net Regression Algorithm）
- 机器学习算法系列（五）- Lasso回归算法（Lasso Regression Algorithm）
- 机器学习算法系列（四）- 岭回归算法（Ridge Regression Algorithm）
- 机器学习算法系列（二）- 口袋算法（Pocket Algorithm）
- 机器学习算法系列（一）- 感知器学习算法（PLA）
- 机器学习算法系列（〇）- 基础知识
- 机器学习算法|树类算法之---lightGBM使用与调参
- spark|ALS算法推荐