Editing Carnegie Mellon's Harpy System (section)

==== '''5.2 Search space reduction''' ====
The Harpy system uses heuristics to reduce the calculations and search spaces, and therefore increases the speed of recognition. The formula for the reaction time shown as below:

'''''(rec.time in seconds)= (#time samples)(.022+.0004(#templates)+.00027(#states)+.00005(# pointers)'''''

The formula shows the 4 main areas where Harpy applies heuristics: '''the number of time samples used''', the number of '''templates''' used for the acoustic match probabilities per time sample, the number of '''states''' checked per time sample, and the number of '''pointers''' checked per time sample.  

The methods used by Harpy to reduce all these number checked per time are based on the notion that '''not all network state probabilities need be updated every time sample'''. At time sample 0, there is probability 1 of being in the initial state and probability of being in all other states. The only states that have non-zero probability at time sample 1 are those states that can be reached in one transition from the initial state. Similarly, the only states that have non-zero probability at time ample N are those states that can be reached in N transitions (both inter and intra-state) from the initial state. At M time samples from the end of the utterance, the only states that need be checked are those from which the final state can be reached in M transitions. Unfortunately, this significantly reduces the number of states that need to be checked only near the start or end of the utterance. Intuitively, the only paths that need to be checked at every time sample are those that are "obvious".

The number of pointers checked at every time sample is dependent on the number of states checked.

The Harpy system uses ‘best-several’ search strategy to reduce the number of paths checked and guarantee the performance in large search space conditions. That is, Harpy searches for a few ‘best’ paths in parallel. ‘best’ is calculated by heuristics.