Partial traceback and dynamic programming

Dynamic programming is used in speech recognition to search efficiently for word sequences whose templates best match acoustic data. The search is constrained by finite-state networks embodying grammatical rules. Typically, dynamic programming is implemented in two steps: the first calculates, for each state in a network and for each time, the best way of arriving at that state at that time; the second traces back from the final state at the final time to the initial state at the initial time to determine the best path through the network. This second step cannot be initiated before the determination (usually from the detection of silence) that the final state has been reached. Such a determination is difficult in the recognition of truly continuous speech; there are often no reliable anchor points. Further, it is often desirable to be able to recognize at least part of an utterance before a speaker has stopped talking. In this paper we introduce a technique for discovering the initial section of the optimal path through a network before the traversal of the network is complete. It can be used to report a system's interpretation of acoustic data from the not-too-distant past without relying on or making any decisions which may degrade recognition accuracy.