当前课程知识点:机器学习概论 > 第四章 马尔可夫模型和隐马尔可夫模型 > 4.4 评估问题 > 评估问题(1)
今天主要讨论两个问题 第一是评估问题 第二是解码问题
其实评估问题 评估问题是解码问题的基础
如果我们把评估问题研究的特别清楚了
解码问题就用的特别多 而且会用得特别好
我们一会就会看到这个问题怎么用
首先来看第一个评估问题
评估问题其实他的问题描述是这样的
我有一个观察的序列从o1到oT
然后我还有一个初始的你这个模型假设已经有了初始状态
还有转移概率矩阵和你的输出概率矩阵都有了
我现在想知道在当前初始状态下
我能够观察到这样一个观察序列的概率有多大
事实上我们还在刚才天气预报的例子里面
如果看到当时我们已经有了这个模型之后
我想知道模型已经给出来了我想看到连续三天里面
这个人看到 打伞 打伞 没打伞
这样的状态的概率是多大
所以这个我们把它叫做评估问题
就是评估一下输出得到的可能得到这样一个可能性是多少
那么这个问题怎么算 其实比较简单的做法
接近于刚才我们问的问题二的方法
你看我有初始状态 我想知道观察到的状态是什么
我就可以让它等于 因为观察到的状态只和隐状态有关
所以我想知道比如说这连续两天简单来说
我想知道连续这两天是打伞打伞
那么概率有多大 你其实可以穷举一下隐藏的状态
就隐藏的状态是 晴天 晴天 隐藏的状态是 晴天 下雨
隐藏状态是 晴天 有雾 或者是 有雾 晴天 等等
就把所有的可能的隐藏状态穷举一下
枚举一下然后在每一个状态下面
你其实就可以得到在初始状态下你得到隐藏状态的概率
然后根据每一个隐藏状态的概率
给定了每一个隐藏状态你的输出的状态就是确定的
你的这个概率就是能得到的
那么所以事实上再接下来它又等于什么
把求和起来你的从x1
你的输出概率其实就是x1到o1乘以x2到o2乘以xT直到oT
这就是输出的概率 这是你中间就是其中输出概率的这部分
P(X)等于什么呢
P(X)因为它就隐藏的序列
它只和你的隐藏序列的一阶隐马尔可夫假设有关
所以它就是我们前面马尔可夫模型里面的
它就等于初始的状态x1乘以x1到x2的转移x2到x3的转移
一直转移下来
然后一直到最后一个状态
好 那么分别把这两个带回到我们这个公式里面
你就会发现这个时候我们评估的问题
它就等于给出你当前的初始的模型
我观察到一个输出的概率
它就等于这样的一个加和
这个加和是说穷举我所有x1到xT的可能的隐藏状态
在穷举的每一种情况
它就是从π乘以转移概率到输出概率再乘以
转移概率乘以输出概率乘以转移概率乘以输出概率
一直沿着这个链传下来传到最后一天
这个就是我们解决的评估问题第一种做法
非常简单对吧
然后我们其中利用到了这个模型的公式
所以描述起来非常简单
就是你把所有的概率沿着这个链传下去
但是注意这里要穷举所有的x1到xT的状态
这个办法好不好 它是对的
但是它有点麻烦 为什么麻烦
我们来分析一下它的复杂度 就关于这种计算方法
因为你要列举所有可能的状态
假设你的序列的长度是T我们已经知道序列的长度是T
其中每一个如果有N个可能的状态
就每一个状态有N个可能的取值的话
然后长度为T的序列 你就要有N的T次方
这么多种不同可能的情况
就是你枚举的所有隐藏的序列的状态
是有N的T次方这么多的
然后在每一个里面
在已经确定的每一个状态里面 你要做多少次乘积
就是你需要从x1的转移概率 从x1 x2一直传到xT
转移概率传下来长度为T所以你要做T个乘积
同时你还要输出一遍 还有这个输出概率就是B的部分
从x1到o1 xt-1到ot-1直到这
所以你会有T这么个长度的输出概率的乘积
所以我们的计算复杂度你一共要有多少次乘法运算
要有2T乘以N的T次方这么多个
你会发现序列越长 它的长度是在指数上面的
然后序列越长就会越复杂 然后你的状态越多 会越复杂
所以他是个穷举的办法 我们接下来想
有没有比较好的办法 有
接下来办法是隐马尔可夫模型里面最有价值的部分
这个是怎么样 我们首先给大家一个思路
就一种介绍叫做前向算法
前向算法它其实是一种动态规划算法
什么样的动态规划算法 我们来一步一步的看一下
我们首先定义一下某一个状态的它的α的值
我们第一个αt(i) αt(i)的意思是说
我现在已经从第一时刻观察到了第t个时刻
就是有从o1到ot的输出值
我还知道当前第t的时刻的xt它的隐状态是i
当然你知道这个模型的初始值 也就是说给定了这个模型
xT时刻的隐状态为i
然后我还观察到了o1到oT这个T的时刻的输出
我们把当前的这样的一个概率把它叫做αt(i)
很自然的我们想看到动态规划的意思就是我知道了当前这一步
我想看一看下一步怎么样
那么最后一步事实上很显然
它应该就是等于我的αT(i) 就是下一步的每一个状态i
你就会有一个αT(i)
但是穷举最后一步的所有可能状态i从1到N加到一起
就是我整个输出概率
我们想知道的评估问题
所以其实他写起来就是用我们的这种αt(i)的方式来去描述的
我们只要看最后一个时刻的状态是什么就行了
但是这个怎么计算呢
就这个东西到底怎么计算 我们看一看
如果我们知道了αt(i)的话 那么αt+1(j)这怎么算
αt+1(j)我们先根据它的定义把它展开
它就相当于是我们是观察到了从o1到t+1这个时刻的输出
同时我们还知道t+1这个时刻 它的隐藏的状态为j
我们就在这个基础上来做一些计算
这个东西你看我们又再一次会考虑
我们这个是xt+1时刻对吧 我们以xt时刻作为一个桥梁
它事实上是等于我从o1到ot的所有的输出状态
以及在t时刻xt它的一个取的状态
和到现在这个时刻xt+1的时候它有一个状态
和我们当前的输出所以是o1到ot观察值
和ot+1和前一个状态xt的状态为i 和当前的状态为j
其中我们要把前一个状态穷举一下
假设我当前是晴天 我是从哪些状态有可能到晴天
前一天是晴天也可以变成晴天
前一天下雨也可以 有雾也是可以的
所以我要穷举前一个状态的所有可能的情况
所以这就是一个求和 i就是所有的可能状态
这一步是等价的
插上这一步
大家会就会发现你跟αt(i)比一比
有一些地方很像 都有哪些地方很像
你看我们从这一步到这一步会有一些处理
首先我们把xt就是把t时刻的i把它拎出来
就是用我们的贝叶斯公式 你的这样的一个联合概率
等于给定其中一个条件
比如说我们拿t时刻的状态为条件的话
它的先验概率乘以已知在这个条件下剩下的这些量
取得的条件概率乘积 这就是一个贝叶斯公式是等价的
我们提出来的其中的xt这一项作为条件 接下来怎么办
我们把它重新写在这 到这里我们就可以利用刚才的很多个假设了
你看从这一步到这一步
你会发现我们的o1到ot就是我们输出概率
它事实上我们从这看 先从xt 然后再知道xt=i的时候
它会影响到从xt到xt+1这个时刻
然后同时xt+1它会以及后面的输出这是ot +1的这部分
我们把这个东西的前后两个部分拆开
因为如果给定了这两个状态的话 o1到ot和ot+1是没有关系的
-1.1 课程介绍
--课程介绍(1)
--课程介绍(2)
-1.2 机器学习的背景
--机器学习的背景
-1.3 什么是机器学习
--什么是机器学习
-1.4 机器学习系统设计
-第一章作业
-2.1 决策树的基本概念
--决策树的基本概念
-2.2 决策树的实例和发展历史
-2.3 经典决策树算法ID3
-2.4 过拟合和前剪枝
--过拟合和前剪枝
-第二章作业
-3.1 下午茶时间:勒索软件
-3.2 后剪枝
--后剪枝
-3.3 决策树的改进和归纳学习假设
-3.4 贝叶斯学习的背景
--贝叶斯学习的背景
-3.5 极大似然假设、朴素贝叶斯和最小描述长度
-第三章作业
-4.1 下午茶时间:微博的垃圾检测
-4.2 马尔可夫模型
--马尔可夫模型
-4.3 隐马尔可夫模型
--隐马尔可夫模型
-4.4 评估问题
--评估问题(1)
--评估问题(2)
-4.5 解码问题
--解码问题
-4.6 隐马尔可夫模型的应用
-第四章作业
-5.1 下午茶时间:图灵奖
-5.2 假设评估
--假设评估(1)
--假设评估(2)
--假设评估(3)
-5.3 置信度和置信区间
-5.4 有限数据下的比较
--有限数据下的比较
-第五章作业
-6.1 下午茶时间:黑洞照片
-6.2 基于实例的学习的基本概念
-6.3 最近邻算法
--最近邻算法
-6.4 K邻近算法
--K近邻算法
-6.5 KD树
--KD树
-6.6 距离加权的K近邻算法
-第六章考试
-7.1 支持向量机的背景
--支持向量机的背景
-7.2 线性支持向量机
-第七章作业
-8.1 核函数支持向量机
-8.4 支持向量机总结
--支持向量机总结
-8.5 无监督学习简介
-8.6 层次聚类
--层次聚类
-8.7 K-means聚类和K-medoids聚类
-第八章作业


