HMM中的维特比解码(Viterbi Agorithm)

By Suz, on 八月 27th, 2010, 1,447 views, 2 comments Share
HMM_vi_logo

本文讨论了HMM中另一种基本算法，维特比算法。以下为部分摘要，点击阅读更多：

…在之前的文章中，已经分别介绍了隐马科夫模型（HMM）的概况以及HMM中广泛应用的一种解决估值问题的算法：前向法(Forward Algorithm)。在本文将介绍解决HMM另外一个问题，解码问题，的算法：维特比算法(Viterbi Agorithm)，也属于HMM中的一个基本算法，而且算法本身很像Forward的这个概念，理解起来相对容易。…

…可以说viterbi算法至此完成了两个任务：1、利用递归方法避开了重复运算提高了效率。2、在结果中找出了“局部最优解”，并将这些最优解拼成一个完整的解。…

…我们需要特别注意到，当前我们面临的问题被称为解码问题，也称为寻找最优解问题。对于最优解，还分为全局最优解与局部最优解(Partial best paths)。上面提到的穷举法就属于全局最优解，因为它已经在全局范围内枚举了所有可能，一个不漏。而刚刚提到的维特比算法则属于寻找局部最优解的方法。… . . . → Read More: HMM中的维特比解码(Viterbi Agorithm)

2 comments   计算机视觉   , , , , ,   Share

HMM中的前向法(Forward Agorithm)

By Suz, on 七月 9th, 2010, 1,358 views, 1 comment Share
HMM_Fa_logo

本文主要介绍隐马科夫模型(HMM)中的一个重要算法：前向法(Foward Algorithm)。将普通算法与前向法优化算法对比，详细分析其实现过程。以下是摘要，点击阅读更多：

…各位应该不难想象，最普通最直接的计算P(O|\lambda)的方法就是枚举所有可能的隐状态序列(S)，然后用Transition Matrix与Emission Matrix的数据，对每一个隐状态序列S求我们的目标观察序列O的一个概率。…

…我们在面对一种所谓的可以简化计算、加速计算的方法面前，应该首先考虑到底这种算法是如何简化？在哪一步发生了奇妙的变化？为什么这样可行？…

…记得在上一页提到的普通穷举算法中，对于所有的可能隐状态路径计算，其实都有很大部分的重复。比如，我要分别算(S1 > S2 > S1 > S3 > S2)这个路径与(S1 > S2 > S1 > S3 > S4)这个路径的概率时候，这两个路径的t<=4的那些状态(S1 > S2 > S1 > S3 >..)其实是相同的。我们的加速算法，切入点就是这里，去掉重复的地方使速度变快，复杂度降低。… . . . → Read More: HMM中的前向法(Forward Agorithm)

One comment   计算机视觉   , , , ,   Share

隐马科夫(HMM)模型

By Suz, on 五月 16th, 2010, 2,067 views, 5 comments Share
HMM_logo

本文介绍非常基础、通用的一个分类模型：隐马科夫模型（HMM），尽量以平实的语言，分别通过实例、图片来说明HMM的过程，并简述了HMM的三个问题和解决方法。以下为文章摘要，点击阅读更多：

…隐马科夫(HMM)模型全称：Hidden Markov model，是一种统计学的模型，是马科夫链与无法观察的状态的结合。在这里，我假设看这篇文章的人已经对马科夫过程(Markov Process)有了初步的认识，对概率论有过初步的学习。…

…那么这个HMM模型，隐马模型到底“隐”在哪里呢？其实解释起来也不难，这里…t-1, t, t+1…各个时刻的x状态是一个随机过程，试想一下，你总不能确定一个随机过程中的每个状态吧？所以，上图的x状态对于我们来说，在没有到达t时间之前，他仍然是未知的，隐藏的（Hidden）。这些x被称为“unobserved state”。…

…HMM过程是，我从任意一个筐开始选水果，我去到那一个框那里，随机拿起里面的一个水果，然后把这个水果记录下来，然后再随机地去另外一个筐里面选水果，不断地重复这个过程，知道我选够了L个水果，我就停止。… . . . → Read More: 隐马科夫(HMM)模型

5 comments   计算机视觉   , , , , ,   Share