Solving large-margin hidden Markov model estimation via semidefinite programming

Abstract—In this paper, we propose to use a new optimiza-tion method, i.e., semidefinite programming (SDP), to solve the large-margin estimation (LME) problem of continuous-density hidden Markov model (CDHMM) in speech recognition. First, we introduce a new constraint for LME to guarantee the bounded-ness of the margin of CDHMM. Second, we show that the LME problem subject to this new constraint can be formulated as an SDP problem under some relaxation conditions. Therefore, it can be solved using many efficient optimization algorithms specially designed for SDP. The new LME/SDP method has been evaluated on a speaker independent E-set speech recognition task using the ISOLET database and a connected digit string recognition task using the TIDIGITS database. Experimental results clearly demonstrate that large-margin estimation via semidefinite pro-graming (LME/SDP) can significantly reduce word error rate (WER) over other existing CDHMM training methods, such as MLE and MCE. It has also been shown that the new SDP-based method largely outperforms the previously proposed LME opti-mization methods using gradient descent search. Index Terms—Continuous-density hidden Markov models (CDHMMs), convex optimization, large-margin classifers, large-margin hidden Markov models, semidefinite program-ming (SDP). I