Viterbi算法定义( Viterbi algorithm definition)

1. Formal definition of algorithm

For each i,, i = 1, ... , n, let : 数据挖掘研究院

- this intialises the probability calculations by taking the product of the intitial hidden state probabilities with the associated observation probabilities. 数据挖掘研究院

For t = 2, ..., T, and i = 1, ... , n let :

数据挖掘研究院

  数据挖掘研究院

- thus determining the most probable route to the next state, and remembering how to get there. This is done by considering all products of transition probabilities with the maximal probabilities already derived for the preceding step. The largest such is remembered, together with what provoked it.

Let : 数据挖掘研究院

  数据挖掘研究院

- thus determining which state at system completion (t=T) is the most probable. 数据挖掘研究院

For t = T - 1, ..., 1 数据挖掘实验室

Let : 数据挖掘研究院

  数据挖掘研究院

- thus backtracking through the trellis, following the most probable route. On completion, the sequence i₁ ... i_T will hold the most probable sequence of hidden states for the observation sequence in hand.

2. Calculating individual ′s and ′s

The calculation of ′s is similar to the calculation of partial probability (′s) in the forward algorithm. Compare this diagram showing ′s and ′s being calculated with the diagram at the end of section 2 under the forward algorithm.

The only difference is that the summation ( ) in the forward algorithm is replaced with max to calculate the ′s - this important difference picks out the most likely route to the current position, rather than the total probability. We also, for the Viterbi algorithm remember the best route to the current position by maintaining a `back-pointer′, via the argmax calculation of the ′s.

资料全文下载

数据挖掘研究院