Efficient backward decoding of high-order hidden Markov models

被引：14

作者：

Engelbrecht, H. A. ^{[1
]}

du Preez, J. A. ^{[1
]}

机构：

[1] Univ Stellenbosch, Dept Elect & Elect Engn, ZA-7600 Stellenbosch, South Africa

来源：

PATTERN RECOGNITION | 2010年 / 43卷 / 01期

关键词：

Hidden Markov model; Decoding; High-order; Search; PROBABILISTIC FUNCTIONS; RECOGNITION;

D O I：

10.1016/j.patcog.2009.06.004

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The forward-backward search (FBS) algorithm [S. Austin, R. Schwartz, P. Placeway, The forward-backward search algorithm, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1991, pp. 697-700] has resulted in increases in speed of up to 40 in expensive time-synchronous beam searches in hidden Markov model (HMM) based speech recognition [R. Schwartz, S. Austin, Efficient, high-performance algorithms for N-best search, in: Proceedings of the Workshop on Speech and Natural Language, 1990, pp, 6-11; L. Nguyen, R. Schwartz, F. Kubala, P. Placeway, Search algorithms for software-only real-time recognition with very large vocabularies, in: Proceedings of the Workshop on Human Language Technology, 1993, pp. 91-95: A. Sixtus, S. Ortmanns, High-quality word graphs using forward-backward pruning, in: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 1999, pp. 593-596]. This is typically achieved by using a simplified forward search to decrease computation in the following detailed backward search. FBS implicitly assumes that forward and backward searches of HMMs are computationally equivalent. In this paper we present experimental results, obtained on the CallFriend database, that show that this assumption is incorrect for conventional high-order HMMs. Therefore, any improvement in computational efficiency that is gained by using conventional low-order HMMs in the simplified backward search of FBS is lost. This problem is solved by presenting a new definition of HMMs termed a right-context HMM, which is equivalent to conventional HMMs. We show that the computational expense of backward Viterbi-beam decoding right-context HMMs is similar to that of forward decoding conventional HMMs. Though not the subject of this paper, this allows us to more efficiently decode high-order HMMs, by capitalising on the improvements in computational efficiency that is obtained by using the FBS algorithm. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：99 / 112

页数：14

共 32 条

[21]

Mari JF, 1996, INT CONF ACOUST SPEE, P435, DOI 10.1109/ICASSP.1996.541126

[22] Estimating the pen trajectories of static signatures using hidden Markov models [J].

Nel, EM ;

du Preez, JA ;

Herbst, BM .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27 (11) :1733-1746

[23] DATA DRIVEN SEARCH ORGANIZATION FOR CONTINUOUS SPEECH RECOGNITION [J].

NEY, H ;

MERGEL, D ;

NOLL, A ;

PAESELER, A .

IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1992, 40 (02) :272-281

[24]

Nguyen L., 1993, P DARPA HUM LANG TEC, P91

[25]

PORITZ AB, 1988, P IEEE INT C AC SPEE, V2, P215

[26] A TUTORIAL ON HIDDEN MARKOV-MODELS AND SELECTED APPLICATIONS IN SPEECH RECOGNITION [J].

RABINER, LR .

PROCEEDINGS OF THE IEEE, 1989, 77 (02) :257-286

[27]

RABINER LR, 1986, IEEE ASSP MAG, V1, P4

[28]

RAVISHANKAR MK, 1996, CMUCS96143

[29]

SCHWARTZ R, 1990, P DARPA WORKSH SPEEC, P6

[30] High quality word graphs using forward-backward pruning [J].

Sixtus, A ;

Ortmanns, S .

ICASSP '99: 1999 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, PROCEEDINGS VOLS I-VI, 1999, :593-596

← 1 2 3 4 →