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)$ 。

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

PKU ACM 3255解题报告

By Jorbe 2014/02/22 计算机科学 No Comments

dijkstra算法由荷兰计算机科学家dijkstra提出。核心算法思想是广度优先搜索，也是一种贪心算法。dijkstra算法可以用来求非负权有向图的单源最短路径，其实它不仅仅可以用来求单源最短路径，还能用来求单源次短路径，后面我会具体给个求单源次短路径的问题。

dijkstra算法描述：设置[......]