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