Seminár umelej inteligencie
Mon 20 Feb. 2012, 14:00
Title: O dekódovaní skrytých Markovových modelov
Speaker: Michal Nánasi
Hidden Markov models are traditionally decoded by the Viterbi algorithm which finds the highest probability state path in the model. In recent years, several limitations of the Viterbi decoding have been demonstrated, and new algorithms have been developed to address them. In this talk we propose a new efficient HMM decoding algorithm called the highest expected reward decoding (HERD). It is appropriate when we want to partition sequence into features and allow some tolerance in the placement of each feature boundary. We define our objective function in the terminology of gain functions, where the gain characterizes the similarity between a predicted and the correct annotation. Then we seek the annotation with the highest expected gain where the expectation is taken over all annotations in the HMM. We demonstrate usefulness of our approach on jumping HMMs for recombination detection in viral genomes, where our algorithm predicts recombinations with higher accuracy than the Viterbi algorithm.