An empirical evaluation of HHMM parsing time

Abstract:

Current state of the art speech recognition systems use very little structural linguistic information while doing word recognition. Some systems attempt to apply syntactic and semantic analysis to speech, but this is typically done in a pipelined approach, where there is thresholding done in between each stage. It would be advantageous to make use of information about higher level linguistic structure before doing any thresholding, so that uncertainty at different levels (acoustic, word level, syntax, semantics) can all be weighed simultaneously to recover the most likely global outcome. However, the standard CYK parsing algorithm has cubic run-time complexity, which makes it difficult to use in streaming speech applications with unsegmented utterances. Some have proposed frameworks for parsing using time-series models such as hierarchical hidden Markov models (HHMMs), with an architecture similar to that of Murphy and Paskin (2001). These models have been proposed because there are algorithms for recovering a most likely sequence in linear time. However, transforming a grammar into a format usable by time series models like HHMMs increases the constants in the run-time complexity, and the practical effect of these transformations on run-time complexity has not been evaluated thoroughly.