隐马尔科夫-维特比算法

概念介绍:

  继上篇贝叶斯(https://cloud.tencent.com/developer/article/1056640)后,一直想完成隐马尔科夫这篇,一是一直没有时间完成python的示例实现代码,二是想找一个区别于天气的隐马尔科夫例子。区别于贝叶斯,隐马尔科夫模型是基于时序的概率模型,本文只关注于一阶隐马尔科夫模型,即某一时刻的状态值只跟上一时刻的状态值有关。该模型可以用三元组表示:λ = (A, B,π ), 其中:

  • A:为状态转移概率矩阵
  • B:为观察概率矩阵,或称为概率矩阵
  • π:为初始概率矩阵 

举一个例子来说明。

  • 假设有一只电动玩具狗,它只会干三件事:汪汪叫(W),跑来跑去(R),睡觉(S)。则观察状态集合V为{W, R, S}, 则观察状态数目M=3 .
  • 经过了解得知,电动玩具狗是受情绪控制的,它会无聊(B),高兴(H),生气(A),故状态集合Q={B, H,A}, 状态数目N=3
  • 分析这只玩具狗后得知其状态转移概率矩阵为:
  • 混淆矩阵为:
  • 初始概率矩阵为:π = (0.2, 0.4, 0.4)

维特比算法

  假设一天中观察到玩具狗的行为序列为{W,R,S,R,S}, 求最可能的情绪状态序列是什么。这是典型的隐马尔科夫解码问题,下面使用维特比算法求解。

  •  维特比变量

 : 使t时刻为状态i的最佳状态序列的概率值,递推公式:

  •  辅助变量  

 表示t时刻为状态i时的前一时刻t-1时的最佳状态,注意, 

为t时刻为i的最佳的概率,而

为最佳状态值,由此也可知

 记录了到达此点的最佳上一个时刻的状态点路径,故分配T*N数组存储,用于最后回溯路径得到最终结果,动态规划的思想。

Python 实现代码:

class yieldmrkf_t:
    def __init__(self, A, B, Pi, OSet, QSet):
        self.A  = A # 转移概率矩阵
        self.B  = B # 混淆概率矩阵
        self.Pi = Pi # 初始概率矩阵
        self.N  = len(Pi) # 隐状态数量
        self.M  = len(B) / self.N # 观察状态数量
        self.OsetVal = OSet
        self.QSetVal = QSet
        self.QSet = []
        self.Oset = []
        for i in range(0, self.N):
            self.QSet.append(i)
        for i in range(0, self.M):
            self.Oset.append(i)
    def dump(self):
        strA = "A:"
        i = 0
        for k in self.A:
            if i % self.N == 0:
                strA = strA + "\n"
            strA = strA + " " + str(k)
            i = i + 1
        print(strA)
        i = 0
        strB = "B:"
        for k in self.B:
            if i % self.M == 0:
                strB = strB + "\n"
            strB = strB + " " + str(k)
            i = i + 1
        print(strB)
        print("Pi:", self.Pi, "N:", self.N, "M:", self.M)
    def get_a(self, i, j):
        return self.A[i*self.N + j]
    def get_b(self, o, i):
        return self.B[i*self.M + o]
    def get_delta(self, delta_set, t, i):
        return delta_set[t*self.N + i]
    def convertOState(self, OStateSet_Val):
        dest = []
        for k in OStateSet_Val:
            for i in range(0, self.M):
                if k == self.OsetVal[i]:
                    dest.append(i)
        return dest
    def decode(self, OStateSet_Val):
        OStateSet = self.convertOState(OStateSet_Val)
        T = len(OStateSet)
        # 初始化t= 1 的情况
        delta_set = []
        fai_set   = []
        for i in self.QSet:
            delta_1_i = self.Pi[i] * self.get_b(OStateSet[0], i)
            delta_set.append(delta_1_i)
            fai_set.append(0)
        # 递推求的delta 和fai
        for t in range(1, T):
            for i in self.QSet:
                fai_t_i   = 0
                tmp_fai_i = 0
                tmp_delta = 0
                for j in self.QSet:
                    #compute fai
                    tmp = self.get_delta(delta_set, t - 1, j) * self.get_a(j, i)
                    if tmp > tmp_fai_i:
                        tmp_fai_i = tmp
                        fai_t_i   = j
                    #compute delta
                    tmp = tmp * self.get_b(OStateSet[t], i)
                    if tmp > tmp_delta:
                        tmp_delta = tmp
                fai_set.append(fai_t_i)
                delta_set.append(tmp_delta)
        #select last i
        tmp_rate_i_T = 0
        i_T = 0
        for i in self.QSet:
            tmp = self.get_delta(delta_set, T-1, i)
            if tmp > tmp_rate_i_T:
                tmp_rate_i_T = tmp
                i_T = i
        i_dest = []
        i_dest.append(i_T)
        for tmp_t in range(1, T):
            t = T - tmp_t
            i_dest.append(fai_set[(t) * self.N + i_dest[len(i_dest) - 1]])

        dest = []
        for n in range(0, T):
            dest.append(self.QSetVal[i_dest[(T-n) - 1]])
        return dest

OSet = ['W', 'R', 'S']
QSet = ['B','H', 'A']
O    = ['W', 'R', 'S', 'R', 'S']
A  = [0.5, 0.2, 0.3, 0.3, 0.5, 0.2, 0.2, 0.3, 0.5]
B  = [0.5, 0.2, 0.3, 0.4, 0.1, 0.5, 0.7, 0.1, 0.2]
Pi = [0.2, 0.4, 0.4]
o = yieldmrkf_t(A, B, Pi, OSet, QSet)
o.dump()
dest = o.decode(O)
print("output:", dest

输出结果:

A: 0.5 0.2 0.3 0.3 0.5 0.2 0.2 0.3 0.5 B: 0.5 0.2 0.3 0.4 0.1 0.5 0.7 0.1 0.2 ('Pi:', [0.2, 0.4, 0.4], 'N:', 3, 'M:', 3) ('output:', ['A', 'H', 'H', 'H', 'H'])

总结

  • 隐马尔科夫适用于时序概率模型,“隐”的含义是既可观察的状态序列和隐藏(不可观察的)状态序列存在一定关系
  • 本文探究了隐马尔科夫的解码问题,分析实现了维特比算法
  • 隐马尔科夫的概率计算问题和模型参数学习问题待以后探究。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SnailTyan

ResNet论文翻译——中英文对照

Deep Residual Learning for Image Recognition Abstract Deeper neural networks are...

2208
来自专栏人工智能头条

一文轻松get朴素贝叶斯算法,以及女朋友

761
来自专栏AI研习社

CNN中的maxpool到底是什么原理?

首先细讲一下 Max pooling。 Max pooling 在卷积后还会有一个 pooling 的操作,尽管有其他的比如 average pooling...

2674
来自专栏趣学算法

动态规划算法秘籍

动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

832
来自专栏数说工作室

logistic回归:从生产到使用【下:生产篇】

logistic回归:从生产到使用【下:生产篇】 上篇介绍了logistic模型的原理,如果你只是想使用它,而不需要知道它的生产过程,即拟合方法及编程实现,那么...

2875
来自专栏吉浦迅科技

【阿星的学习笔记(2)】使用Tensorflow实作卷积神经网络(CNN)

Lady之前已经向各位介绍一个朋友阿星(Ashing)以及他的机器学习读书笔记! 阿星也是我们手撕深度学习算法微信群的热心群友!接下来,Lady我也会陆续分享这...

33110
来自专栏编程

我的R语言小白之梯度上升和逐步回归的结合使用

我的R语言小白之梯度上升和逐步回归的结合使用 今天是圣诞节,祝你圣诞节快乐啦,虽然我没有过圣诞节的习惯,昨天平安夜,也是看朋友圈才知道,原来是平安夜了,但是我昨...

2136
来自专栏云时之间

EM算法学习(番外篇):HMM的参数估计

在上一篇文章中留下了个尾巴是关于EM算法在HMM隐马尔可夫模型的参数估计拓展上的应用.在学习EM算法以后,我们再去学习HMM的Baum-Weich算法就会相对的...

4157
来自专栏FD的专栏

贝叶斯分类器

贝叶斯决策论是一种基于概率的决策理论。当所有相关的概率都已知的理想情况下,贝叶斯决策论考虑如何基于这些概率和误判损失来选择最优的类别标记。

862
来自专栏懒人开发

(3.8)James Stewart Calculus 5th Edition:Derivatives of Logarithmic Functions

具体 y = a^x 求导过程,可以见3.5.5: 先化简: (指数函数,只要求导,化成e为底去做, 因为e^x 求导,为 e^x ,这样可以简化难度)

613

扫码关注云+社区