The List Viterbi Training Algorithm and Its Application to Keyword Search over Databases

Hidden Markov Models (HMMs) are today employed in a varietyof applications, ranging from speech recognition to bioinformatics.In this paper, we present the List Viterbi training algorithm, aversion of the Expectation-Maximization (EM) algorithm based onthe List Viterbi algorithm instead of the commonly used forwardbackwardalgorithm. We developed the batch and online versionsof the algorithm, and we also describe an interesting application inthe context of keyword search over databases, where we exploit aHMM for matching keywords into database terms. In our experimentswe tested the online version of the training algorithm in asemi-supervised setting that allows us to take into account the feedbacksprovided by the users.