Viterbi算法与实现

Viterbi算法Viterbi算法是一种动态规划算法，用来寻找由观测信息产生(Observed Event)的最可能隐状态序列(Viterbi路径)，这种方法通常用在隐马尔可夫模型中。向前算法是一个类似的算法，用来计算一串观测事件发生的概率。这些算法都属于信息论的范畴。这个算法做一连串的假设。首先，观测事件和隐事件必须处于序列中。这个序列通常是关于时间的。第二，这两个序列需要对应，一个观测事件的实例必须与一个隐事件相关联。第三，计算在特定时间点t的最可能隐序列必须只依赖于位于t的观测事件，和t-1处的最可能序列。这些假设在一阶隐马尔可夫模型中都要被满足。Viterbi路径和Viterbi算法同时遵循寻找单一最可能观测解释的相关动态规划算法。例如，在统计分析中的动态规划算法能应用于寻找一个字符串的单个最相似上下文无关推导，即“Viterbi推导”。Viterbi算法是由Andrew Viterbi 在1967年提出的，是一种用于有噪声的数据链路中错误纠正的模型，并广泛应用在卷积码的解码中，例如CDMA/GSM数字蜂窝，拨号调制解调器，卫星通信，深空通信和802.11无线局域网等。现在也广泛的应用在语言理解，关键词匹配，计算机语言学，生物信息学等。例如，在语音理解中，听觉信号被认为是观测事件的序列，文字串被认为是“潜在的原因”。Viterbi算法能够找到对应听觉信号的最可能文字序列。概要前面提到的假设可以被如下概括。Viterbi算法在一个状态机的假设上做操作。也就是说，在任何时间系统被抽象为一些状态。这些状态是有限的，尽管很大。每个状态被表示为一个节点。多个状态的序列(路径)往往都能产生同一个给定的状态，但其中只有一条是最可能产生这个状态的，被称作“生存路径”。这是一个最基础的假设，因为这个算法会检测所有的可能路径并只保留一个最可能的路径。这种策略并不需要计算所有的路径，只需要一个状态一个路径而已。第二个关键的假设是前一个状态到一个新状态的转移被一个递增的度量描述，通常是一个数字。这种转移是从实践中计算而来的。第三个假设是事件在一个路径上是累加的。所以整个算法的关键是计算每个状态的数值。当发生了一个事件，算法结合上一个可能状态与转换产生的增量度量，并从中选择一个最优的，据此来检测向前的新状态。增量度量由事件触发，并由旧状态与新状态间的转换决定。例如，在数据交换中，可能发生一半的符号由奇状态转换，而另一半由偶状态开始转换。同时，在很多例子中，状态转换图是不连续的。一个简单的例子，一个汽车有三个状态，向前，停止和向后，状态从向前倒向后是不允许的。他必须先进入停止状态。在计算出增量度量和和状态度量后，只有最好的幸存，而其他的被舍弃。这种基础算法有一个改进，允许向前搜索和向后搜索。路径历史必须被储存。在一些实例中，搜索历史是完整的，因为状态机在编码端是从一个已知的状态开始的，而且有充足的空间来维持这些路径。再另一些例子中，需要一个在资源有限条件下的解决方案：一个例子是卷积编码，解码器必须在性能能允许的前提下尽量缩短对历史的记录。尽管Viterbi算法是非常高效的，而且有很多降低计算压力的改进，但它对空间的要求仍然趋向常量。实现Alice知道Bob三天来的活动，第一天出去散步，第二天去购物，第三天清洁了公寓。Alice有两个问题：观测序列的整体概率是什么样的？这几天的天气是什么，最能给出观测序列这样的结果。第一个问题由向前算法计算；第二个问题由Viterbi算法计算。这两个算法在结构上是相似的，事实上，他们是同一种抽象算法的两个不同实例，所以他们可以在一个函数中实现。def forward_viterbi(obs, states, start_p, trans_p, emit_p): T = for state in states: # prob. V. path V. prob. Tstate = (start_pstate, state, start_pstate) for output in obs: U = for next_state in states: total = 0 argmax = None valmax = 0 for source_state in states: (prob, v_path, v_prob) = Tsource_state p = emit_psource_stateoutput * trans_psource_statenext_state prob *= p v_prob *= p total += prob if v_prob valmax: argmax = v_path + next_state valmax = v_prob Unext_state = (total, argmax, valmax) T = U # apply sum/max to the final states: total = 0 argmax = None valmax = 0 for state in states: (prob, v_path, v_prob) = Tstate total += prob if v_prob valmax: argmax = v_path valmax = v_prob return (total, argmax, valmax)函数“forward_viterbi”需要如下几个输入参数，“obs”是观测序列，比如walk,shop,clean;“states”是隐状态的集合；“start_p”是初始的概率，“trans_p”是转移概率；“emit_p”是产生概率。这个算法在位图T和U上做操作，每个都是一个从一个状态到一个三元组(prob,v_path,v_prob)的映射，其中prob表示从开始到现在这个状态的概率之和；v_path是到当前状态的Viterbi路径，v_prob是到当前状态的Viterbi路径的概率。位图T保存保存一个给定时间点t的信息，主循环结构U，保存t+1的相似信息。因为马尔可夫性，任何早于时间t的信息是不需要的。算法初始化T为开始的概率：一个状态的总概率是这个状态开始的概率；到一个开始状态的Viterbi路径是一个单独的路径，并只包含这个状态；Viterbi路径的概率与起始概率是相同的。主循环考量“obs”中的观测值序列。T包含正确的信息但排除当前观测的点。算法继续计算下一个可能状态的三元组(prob,v_path,v_prob)。一个给定状态的总概率，total，为所有到达这个状态的概率的和。更确切的说，算法迭代所有可能的源状态。对每一个愿状态，T保存到某各状态所有路径的概率和。这个概率然后乘以当前观测的产生概率和从当前状态转换到下一状态的转换概率。产生的结果“prob”加入“total”中。“Viterbi”路径的概率用一种类似的方法求得，但用一个离散的最大值代替了累加所有的路径。起始时，最大值valmax为零。对每个原状态，“Viterbi”路径的概率是已知的。这也由产生概率，转移概率的乘积获得，如果大于现有值，就取代“valmax”。通过拓展从下一状态指向当前状态的“Viterbi”路径，“Viterbi”路径被当作对应最大值的“argmax”来计算的。在这种模式下得到的三元组(prob,v_path,v_prob)被储存在U中，一旦得到所有可能的下一状态的U，就取代T，然后保证在迭代的最后循环的不变量得到该值。在最后，使用另一个总结/最大化的过程(当然，这一步也可以在主循环的内部进行，添加一个条件语句并在最后一次迭代中执行这一过程)。在执行的例子中，算法的使用方法如下：def example(): return forward_viterbi(observations, states, start_probability, transition_probability, emission_probability)print example()这个表明walk,shop,clean的概率和为0.033612，Viterbi路径为Sunny,Rainy,Rainy,Rainy,概率为0.009408. Viterbi路径包含四个状态，因为第四个观测值是由第第三个状态产生，并转移到第四个状态。换句话说，一个已知的观测动作，当Bob出去散步时天气最可能是晴天；第一天下雨而接着那天也下雨。在实现这个算法时，需要注意到很多语言用浮点数，因为p是很小的，这可能会造成读取空缓存。一个常用的技巧是取概率的对数并用它贯穿整个计算。这个技巧通常也用在对数系统中。一旦算法结束，正确的结果可以通过指数运算得到。如果你希望实现这算法，使它能接受任意状态，观测值，和概率值，用下面的代码代替上文的声明部分：states = number_of_states=input(how many states? Please write an integer different from 0 or 1)index=0while indexnumber_of_states: states.append(str(raw_input(give a name to the state number+str(index) index=index+1observations = number_of_observations=input(how many observations? Please write an integer different from 0 or 1)index=0while indexnumber_of_observations: observations.append(str(raw_input(give a name to the observation number +str(index) index=index+1start_probability = for state in states: start_probabilitystate = input(give a value for the start probability of the state +state)transition_probability = for initial_state in states: transition_probabilityinitial_state = for final_state in states: transition_probabilityinitial_statefinal_state=input(give a value for the transition probability from the state +initial_state+ to the state +final_state)emissi