Jorbe's Blog

Never say never

浅析隐马尔可夫模型(三)

By Jorbe 2014/08/04 计算机科学 No Comments

前面两篇文章写了关于HMM的概率计算问题以及学习问题。这篇文章讲下HMM的预测问题。

预测问题

假设有观测数据O和HMM模型参数 $\lambda =(\pi ,A,B)$ ，求在该条件下最有可能出现的状态序列I。即求 $\underset{I}{argmax}P(I|O,\lambda)=\underset{i_1,i_2,...,i_T}{argmax}\frac{P(I,O|\lambda )}{P(O|\lambda )}$ ，由于分母是个常数，所以也可以表示为： $\underset{I}{argmax}P(I|O,\lambda)=\underset{i_1,i_2,...,i_T}{argmax}P(I,O|\lambda )=\underset{i_1,i_2,...,i_T}{argmax}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_{T}}(o_T)$ 。

其实我们可以把这个问题看成是一个概率图模型，通过求图的最佳路径(路径概率值加[......]

三个经典问题

By Jorbe 2014/04/18 计算机科学 No Comments

求第K小的数

一般的方法是：先对数列进行一次排序，然后找到第k小的数。假如用快排来做排序的话，时间复杂度为O(nlogn)。O(nlogn)看起来貌似效果也不错，但是否还有比它更高效的算法呢？答案是肯定的。我们先来看下第k小的数有什么特点：一个数列中第k小的数，在这个数列中一定有k-1个数比它小，[......]