当前课程知识点:机器学习概论 >  第四章 马尔可夫模型和隐马尔可夫模型 >  4.4 评估问题 >  评估问题(2)

返回《机器学习概论》慕课在线视频课程列表

评估问题(2)在线视频

下一节:解码问题

返回《机器学习概论》慕课在线视频列表

评估问题(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 机器学习系统设计

--机器学习系统设计(1)

--机器学习系统设计(2)

-第一章作业

-第一章课件

第二章 决策树学习(I)

-2.1 决策树的基本概念

--决策树的基本概念

-2.2 决策树的实例和发展历史

--决策树的实例和发展历史

-2.3 经典决策树算法ID3

--经典决策树算法ID3(1)

--经典决策树算法ID3(2)

--经典决策树算法ID3(3)

-2.4 过拟合和前剪枝

--过拟合和前剪枝

-第二章作业

-第二章课件

第三章 决策树学习(II)和贝叶斯学习

-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 下午茶时间:图灵奖

--下午茶时间:图灵奖(1)

--下午茶时间:图灵奖(2)

-5.2 假设评估

--假设评估(1)

--假设评估(2)

--假设评估(3)

-5.3 置信度和置信区间

--置信度和置信区间(1)

--置信度和置信区间(2)

--置信度和置信区间(3)

-5.4 有限数据下的比较

--有限数据下的比较

-第五章课件

-第五章作业

第六章 基于实例的学习

-6.1 下午茶时间:黑洞照片

--下午茶时间:黑洞照片

-6.2 基于实例的学习的基本概念

--基于实例的学习的基本概念

-6.3 最近邻算法

--最近邻算法

-6.4 K邻近算法

--K近邻算法

-6.5 KD树

--KD树

-6.6 距离加权的K近邻算法

--距离加权的K近邻算法

-第六章课件

-第六章考试

第七章 支持向量机(I)

-7.1 支持向量机的背景

--支持向量机的背景

-7.2 线性支持向量机

--线性支持向量机(1)

--线性支持向量机(2)

--线性支持向量机(3)

--线性支持向量机(4)

--线性支持向量机(5)

-第七章课件

-第七章作业

第八章 支持向量机(II)和无监督学习

-8.1 核函数支持向量机

--核函数支持向量机:向量空间

--核函数支持向量机:核函数(1)

--核函数支持向量机:核函数(2)

-8.4 支持向量机总结

--支持向量机总结

-8.5 无监督学习简介

--无监督学习简介(1)

--无监督学习简介(2)

-8.6 层次聚类

--层次聚类

-8.7 K-means聚类和K-medoids聚类

--K-means聚类和K-medoids聚类

-第八章课件

-第八章作业

评估问题(2)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。