首页 > 代码库 > Ruby写的向前算法
Ruby写的向前算法
隐马尔科夫模型中有三个问题:
1) 估计问题:给定一个观察序列O=O1O2...OT和模型u = (A, B, π), 如何快速地计算出给定模型u情况下,观察序列O的概率,即P(O|u)
2) 序列问题: 给定观察序列O=O1O2...OT和模型u = (A, B, π), 如何快速有效地选择在一定意义下“最优”的状态序列Q=q1q2...qT,使得该状态序列“最好地解释”观察序列?
3) 训练问题或参数估计:给定一个观察序列O=O1O2...OT,如何根据最大似然估计来求模型的参数值?即如何调节模型u=(A, B, π)的参数,使得P(O|u)最大?
问题1是一个解码问题,前向算法可以解决该问题(forward procedure),也是动态规划法的一种应用。
关于前向算法的基础知识可以看下面的文章
http://www.cnblogs.com/tornadomeet/archive/2012/03/24/2415583.html
最后是ruby代码
class FowardAlgorithm def initialize(pi, trans_pro, emit_pro) @pi = pi @trans_pro = trans_pro @emit_pro = emit_pro end def alpha1(state, ob) @pi[state] * @emit_pro[state][ob] end def alpha(t, state) # t starts from 0, states starts from 9 if t.equal? 0 alpha1(state, @ob[0]) else sum = (0...@trans_pro.size).inject(0.0) { |sum, i| sum += alpha(t-1, i) * @trans_pro[i][state] } sum * @emit_pro[state][@ob[t]] end end def p_rerial_n ob n = ob.size n -= 1 @ob = ob # time & states res = 0.0 0..@trans_pro.size.times { |i| #print "time #{n}, state #{i}" tmp = alpha n, i res += tmp } res endenddef test pi = [0.2, 0.4, 0.4] trans_pro = [ [0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5] ] emit_pro = [ [0.5, 0.5], [0.4, 0.6], [0.7, 0.3] ] f = FowardAlgorithm.new pi, trans_pro, emit_pro puts f.p_rerial_n([0, 1, 0, 1])endif $PROGRAM_NAME == __FILE__ testend
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。