当前课程知识点:机器学习概论 > 第四章 马尔可夫模型和隐马尔可夫模型 > 4.4 评估问题 > 评估问题(2)
给定了o1到ot和ot+1是没有关系的
它和xt+1也没关
所以o1到ot的部分 它只和xt有关在这个里面
所以从o1到ot我们把它和xt反过来
然后其中在t+1时刻的观察量和t+1时刻它的隐藏的状态
他们会隐式的和这个有关
好 我们把这个公式就把它拆成了这样的三项
在接下来其实我们就是利用了我们刚才说的独立性的假设
输出独立性假设和我们的转移概率的就是一阶马尔可夫假设
我们把它做一个组合
前面的第一项是给定xt状态的o1到ot
最后一项是给定xt状态
这两个组合到一起就是从o1到ot的输出概率
以及从xt隐藏状态的联合概率
中间这一项我们同样的会应用输出独立性假设
因为我们的ot+1他只和xt+1有关 它和xt是没有关系的
我们在这两个点之间是没有斜线的连线的
所以中间这一个就可以拆成两部分
Xt的状态影响了xt+1的状态 然后xt+1的状态
影响了ot+1的状态 经过这样的拆分和组合
我们就会看到这个东西变得非常的规范
而且马上好像看到曙光了 因为前面这个好像很眼熟对不对
前面这个其实就是αt(i)
这个东西是什么
它就是转移概率 第三项就是输出概率
所以经过这样的推导你会发现很好玩
第t+1时刻它的状态就是αt+1(j)它是等于
前一个时刻的αt(i)乘以
从这个状态到t+1时刻的状态的转移概率
再乘以这个状态到隐状态到输出的观察输出值之间的输出概率
它等于这三个的层级并且然后穷举一下中间前一个状态的
所有可能情况就好了
求和i是从1到N所有可能的状态
所以事实上你有了αt你就可以计算出来αt+1
有了αt+1就可以计算αt+i
然后一直就可以一步一步的计算到最后一步的xti
所以这个就是我们的前向算法
前向算法我们推导出这样的一个公式
我们定义好αt(i)是什么之后
我们就会发现αt+i(j)是等于αt(i)
就是前一个时刻的状态乘以从前一个时刻的i状态
转移到当前时刻的j状态再乘以从当前时刻的j状态
它的输出为当前观察到的状态
然后其中把前一个时刻的状态要穷举一下
这个是跟最早说的问题二的穷举有点像
那么它的复杂度有多少呢
按照这个的复杂度
我们想一想看 你看我们一共有T的时刻
在每一个时刻你其实一共要有2N次乘法
就是要有多少个乘法
因为你是一个输出乘以转移概率乘以一个输出概率
而且在t+1时刻会有N个j
所以其实一共会有N的平方这么多个
每一个时刻你是N的平方这么多次 N的平方这么多
因为每一次是有N个计算 然后你要穷举N次
前一个时刻它有N个状态
求和是N乘N 也就是N方 然后在每一个长度的时候
它是N方 一共有T长度 所以是N方乘以T
我们放在这里 把它写下来
我们会看到这种动态规划的算法它的复杂度
时间复杂度要远远低于我们刚才穷举的办法
T都是有的 剩下的一个是N方数量级
一个是N的T次方数量级 长度越长差异越大
所以我们特别好的利用了一个特点就是
它的转移概率和它的输出独立性的特性
所以我们可以用一个动态规划的算法
好 这个是前向算法
我们仔仔细细地带给大家一步一步的分析了一下
那么事实上还有一个解决的思路是叫做后向算法
后向算法算起来事实上跟刚才的思路非常的接近
所以我可能带大家推导的就没有那么的细
但是会给大家把关键步骤列在这里
刚才前向算法大家理解的时候你可以看这个图
前向算法是说我把前面t个时刻知道了 想看第t+1时刻
后向算法顾名思义从后往前看 倒着看
后向算法我们会定义一个参数叫做β这样一个变量
βt(i)描述的是从t时刻到最后一个输出状态观察到的输出状态
ot到oT然后以及我当前知道的是xti
这个就是差别 就好像说我一共从今天开始到这一周
就是从周一到周五 前向算法是说从周一周二周三这样观察下来
后向算法是说我从周五周四周三周二反着去观察
从后面的时刻往前去推
那么βt(i)我们定义成已知我们从ti时刻一直到最后结束它的观察值
以及ti这个时刻它的状态为i
那么我们会看到整个你如果想观察到整个时间序列的话
就是一直把它推到了第一天 推到了第一步的β1(i)
然后最初还有一个初始化不要忘 就是初始化πi
然后对第一天的所有可能的状态i做一个枚举
就是i从1到N有这么多的状态就可以了
也就说被β1第1天隐藏状态是晴天
第一天的隐藏状态加上第一天隐藏状态是下雨
加上第一天隐藏状态是有雾
这三种情况下面的β1都分别计算出来
再乘以对应的初始的π的值加在一起就可以了
这是后向算法 那么这个是我们想知道的 怎么算呢
我们需要去找出来一个βt-1和βt之间的关系
所以我们事实上会发现那βt-1和βt的关系
我们就首先把它推到βt和βt+1之间的关系
我们已经知道t+1这一天它的β值了
所以用类似的推导方法 我们不在一步一步的写出来
当我把这个给出来大家回去用仿照着我们前面
前向算法 你一步一步的
非常容易把它推导出来
我想知道当前的β值 它就等于就后一个时刻βt+1的j
乘以我们从当前的aij就是从t时刻到t+1时刻的转移概率
再乘以t时刻到t时刻的输出概率
所以就是aij乘以biot再乘以后面你已经知道的β的值
然后把后面知道β值的取值的状态做一个枚举就可以
就是一共会有N种可能状态
在算法里面最初始的是最后一个时刻
就是我们这个是给定的定义
βT+1是可以用我们整个序列只有T长度
所以序列的T+1的βI那它都等于1
这个是我们给出来 你就可以一步一步从后往前的一步一步的算出来
知道βT+1就可以知道βT
就可以这样βT-1 然后就可以知道βt+1时刻
知道βt一直求到β1 然后把β1可能的状态三种状态枚举就可以了
同样的它的计算的复杂度也是类似的
所以其实我们到现在就已经讨论完了
我们在隐马尔可夫模型马模型的一个评估问题
这个评估问题我们其实一共讨论了三种做法
这三种做法分别是第一穷举
穷举的做法事实上理解起来是最容易的
但是计算起来最麻烦
穷举就是你想知道观察这个状态
你就把它可能对应的所有隐状态穷举一遍
然后在每一个可能的隐状态里面
所以你会看到这个是序列x到xt的枚举
然后每一个状态里面就是π乘以转移概率乘以输出
再乘以转移概率乘以输出再乘以转移概率乘以输出一直乘下去
算完就行了 但它的复杂度我们已经算过
它是2T乘以N的T次方这么多次乘法运算
然后我们利用了这个模型的结构
我们定义了动态规划的算法
在这个动态规划算法里面 我们定义一个中间时刻
比如说中间的xt时刻 我们会发现在αt(i)
那么把这个定义好之后我们会发现下一步
αt+1(i)它是等于αt(i)乘以转移概率aij然后再乘一个输出概率
从t+1时刻到输出概率的乘积然后加到一起
所以我们整个的输出 整个观察到序列的输出
你想求得就是在最后这个时刻的αT(i)的所有可能的情况
加在一起可以
它的计算复杂度 它是N方乘以T的数量级的乘法运算
所以他们基本上你可以看到这两个差异
如果T都是一样的话 那么它们差异的倍数一个是N方一个是N的T次方
同样的后向算法是从后往前算
从离现在最近的一天往前倒着算 算出来的时候
它事实上就等于第一天的β1(i)的所有可能的情况
前面再乘一个π初始的状态
好这是我们的穷举的算法前向算法和后向算法
这是我们今天课上在隐马尔可夫模型课上解决的第一个问题
叫做评估问题
-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聚类
-第八章作业





