隐马尔科夫-维特比算法

概念介绍:

  继上篇贝叶斯(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 条评论
登录 后参与评论

相关文章

来自专栏深度学习自然语言处理

基于汉语短文本对话的立场检测系统理论与实践

汉语短文本对话立场检测的主要任务就是通过以对话的一个人的立场为主要立场,而判断另一个人针对该人的回话的立场。立场包括支持,反对,中立三种立场。基于对话的立场检测...

1271
来自专栏机器之心

深度学习碰上古文献,西南大学提出基于CNN的古彝文识别方法

摘要:作为世界六大古文字之一的古彝文记录下几千年来人类发展历史。针对古彝文的识别能够将这些珍贵文献材料转换为电子文档,便于保存和传播。由于历史发展,区域限制等多...

2732
来自专栏PPV课数据科学社区

重要的机器学习算法

关键词:机器学习,算法 正文: 本文旨在为那些获取关于重要机器学习概念知识的人们提供一些机器学习算法,同时免费提供相关的材料和资源。并且附上相关算法的程序实现...

2756
来自专栏机器之心

教程 | 用Scikit-Learn构建K-近邻算法,分类MNIST数据集

选自TowardsDataScience 作者:Sam Grassi 机器之心编译 参与:乾树、刘晓坤 K 近邻算法,简称 K-NN。在如今深度学习盛行的时代,...

4195
来自专栏机器之心

学界 | 南京大学提出使用树型集成算法构建自编码器模型:对比DNN有更高的准确性和高效性

27210
来自专栏机器学习算法工程师

不懂word2vec,还敢说自己是做NLP?

如今,深度学习炙手可热,deep learning在图像处理领域已经取得了长足的进展。随着Google发布word2vec,深度学习在自然语言处理领域也掀起了一...

1225
来自专栏数据派THU

手把手教你在Python中实现文本分类(附代码、数据集)

文本分类是商业问题中常见的自然语言处理任务,目标是自动将文本文件分到一个或多个已定义好的类别中。文本分类的一些例子如下:

1.4K5
来自专栏大数据挖掘DT机器学习

文本情感分析:特征提取(TFIDF指标)&随机森林模型实现

作者:Matt 自然语言处理实习生 http://blog.csdn.net/sinat__26917383/article/details/513024...

8374
来自专栏量化投资与机器学习

【Python机器学习】系列五决策树非线性回归与分类(深度详细附源码)

查看之前文章请点击右上角,关注并且查看历史消息 所有文章全部分类和整理,让您更方便查找阅读。请在页面菜单里查找。 相关内容:(点击标题可查看原文) 第1章 机...

3736
来自专栏磐创AI技术团队的专栏

TensorFlowNews五大经典卷积神经网络介绍:LeNet / AlexNet / GoogLeNet / VGGNet/

前言:这个系列文章将会从经典的卷积神经网络历史开始,然后逐个讲解卷积神经网络结构,代码实现和优化方向。 (以下内容来翻译自斯坦福大学课程:http://cs23...

4178

扫码关注云+社区