Editing Carnegie Mellon's Harpy System


== Introduction ==
'''Harpy System''' is a result of combing and improving the best features from two speech systems previously developed at Carnegie Mellon University: '''Hearsay-I''' ( Erman 1974 ) and '''Dragon''' ( Baker 1975 ). Two feature of the Harpy system that led to a successful demonstration are its '''representation of knowledge''' and the use of '''new search techniques'''. In developing speech recognition systems, it is necessary to devise a means of acquiring and representing the many diverse types of knowledge that characterize speech. We must also develop '''matching''' and '''searching''' techniques that convert this passive knowledge into an active process for understanding the utterance in the presence of error, noise, and uncertainty.  


When an utterance is input to the computer. Several pre-processing steps are taken to prepare the data for recognition. The utterance is '''segmented into acoustic units''' and analyzed to determine the segmented features and parameters. The goal of recognition tasks is to find '''an optimal sequence''' of phones satisfying two criteria: '''the sequence must represent a legal path through the knowledge network''' and should '''consist of phones with high acoustic matches'''.


Harpy Systems uses a '''beam search''' to locate this optimal sequence of phones. Harpy begins the beam search by taking all legal phones from the start of the sentence from the knowledge network and entering them in a '''recognition tree'''. Next, a path probability is calculated for each candidate. The path with the best probability is determined and remaining candidates are compared with it. '''Those that fall below a threshold of acceptability are eliminated from further searching'''. The successors of the surviving candidates are expanded based on the information in the knowledge network.
{| class="wikitable"
|+
!
!Hearsay-I System
!Dragon System
!Harpy System
|-
|Sources of Knowledge
|
*Acoustic-Phonetics  (the characteristics of the sounds)
* Prosodics   (the stress and intonation patterns of speech)
* Lexicon   (a dictionary of legal words)
* Syntax   (the grammatical structure of the language)
* Semantics   (the meaning of words and sentences)
* Pragmatics   (the context of the conversation)
|
*Almost '''no''' speech dependent heuristics. 
*The integrated knowledge of both syntax and lexical spellings, a set of user dependent acoustic-phonetic templates, and an acoustic-phonetic probability matching routine. 
*Mathematical acceptability available ---one of probabilistic function of '''[https://wiki.voice-technology.nl/index.php/Hidden_Markov_Models Markov Process]<ref>''Hidden Markov Models''. (2023).[[Hidden Markov Models]]</ref>'''.  

|
*The combination of speech dependent heuristics (Hearsay-I System ) and mathematical tractable model  (Dragon System ). This leverages the use of heuristics to reduce the search space therefore speed increase.
*The system extensively use a network that represents both all legal syntactic paths and pronunciations of these legal paths. 
*No a-priori transition probabilities. 
|-
|Knowledge Representation
|Procedural embedding.
|Markove networks. 
|Transition networks. 
|-
|Search Strategy
|Best-First with backtracking. 
|All paths in parallel ( search all the possible syntactic
and acoustic paths through the network in parallel to determine optimal path ) with no backtracking.
|<nowiki>''best few''</nowiki> in parallel with no backtracking. 
'''Optimized Beam Search'''<ref>Reddy, R. (2013). ''CMU Harpy System 1976 - Beam Search''. Retrieved September 17, 2023, from <nowiki>https://www.youtube.com/watch?v=32KKg3aP3Vw</nowiki>.</ref>
* Locates optimal solution
* Examines near-miss alternatives
* No backtracking
|-
|Segmentation
|Yes
( uses it to reduce effective utterance length )
|No
|Yes
|-
|Strength 
|
*''<u>Segmentation</u>'' of the acoustic signal can effectively  reduce the amount of speech data searched. 
* ''<u>Heuristic speech knowledge</u>'' serves as a practical  guide to mapping and rating words. 
|
*The network data representation of combined knowledge of                                                             <u>''syntax''</u> and the ''<u>phonetic</u>'' dictionary spellings is tractable. 
* The dynamic programming scheme for searching all the network 
* paths in parallel guarantees both a recognition will always be achieved and that the recognition will be the globally optimum one. ( with the given model ) 
|
* Searches only a few "best" syntactic (and acoustic) paths in parallel to determine the optimal path, and uses segmentation to effectively reduce the utterance length.

* Semi-automated generation and tuning of lexicons and templates greatly improved the accuracy of the speech recognition system.

* Has 91% sentence accuracy across five speakers at 30 MIPSS
|-
|Weakness 
|
*''<u>Best-first</u>'' strategy involves <u>''backtracking''</u>,  which can be costly in large search space.
|
*Searching all paths ( even in parallel ) is time consuming. 
|
* The computation of autocorrelation and linear predictor coefficients takes up the majority of processing time in the Harpy speech recognition system (over 64%).
|}
== Historical Context ==
'''Before 1970s''', the speech recognition systems available in the world could only understand '''16 words''' spoken in English. With the goal of ending up with a machine capable of understanding a minimum of 1,000 words, speech recognition technology made major strides '''in the 1970s''', thanks to interest and funding from the U.S. Department of Defense. The DoD’s [https://wiki.voice-technology.nl/index.php/DARPA_Speech_Understanding_Research DARPA Speech Understanding Research]<ref>''DARPA Speech Understanding Research''. (2023). [[DARPA Speech Understanding Research|https://wiki.voice-technology.nl/index.php/DARPA_Speech_Understanding_Research]]</ref> (SUR) program, '''from 1971 to 1976''', funds five years of speech recognition research leading to the creation of the Harpy by Carnegie Mellon, a machine capable of understanding '''1,011 words''', approximately the vocabulary of an average three-year-old<ref>Pinola, M. (2011). ''Speech Recognition Through the Decades: How We Ended Up With Siri.'' <nowiki>https://www.pcworld.com/article/477914/speech_recognition_through_the_decades_how_we_ended_up_with_siri.html</nowiki></ref>.

The Harpy connected speech recognition system is the result of an attempt to understand the relative importance of various design choices of two earlier speech recognition systems developed at Carnegie-Mellon University: the Hearsay-I system and the Dragon system. Systematic performance analysis of various design choices of these two systems resulted in the Harpy system. 

=== Hearsay-I System ===
*'''The Hearsay-I System''' must use all these sources of knowledge effectively in the Hearsay System, this is achieved by representing knowledge as as a set of '''cooperating parallel process'''. The Hearsay System also use the source of knowledge ('''acoustics-phonetics, prosody, lexicon, syntax, semantics and pragmatics''') to '''generate hypothesis''' about what words might appear. The Hearsay System is incrementally trying to match words to the un-analyzed portion of the utterance 
*If the resulting word matches are not optimal, the system '''backs up and tries a different path'''. The technique was known as probabilistic tree. The Hearsay System '''cannot''' recognize sentences in unrestricted English and can only recognize simple phrase structure languages.
*To be acceptable as an input medium, the system must not only perform with high accuracy, but it must also minimize the combinatorial explosion so as to respond as fast as a human would in a similar situation.

=== Dragon System<ref name=":0">Lowerre, B. T. (1976). ''The HARPY Speech Recognition System''. Department of Computer Science, Carnegie-Mellon University.</ref> ===

*'''The Dragon system''' is interesting for its simplicity of design, mathematical tractability and high accuracy performance, which can achieve 100% accuracy on a set of speech data using only '''syntactic and acoustic-phonetic knowledge''';
*It achieves recognition by updating state probabilities of a '''Markov network'''. All possible paths are searched in parallel by a '''dynamic programming scheme''' and lead through states representing all syntactic and phonetic pronunciations;
*The most significant feature of the system is that it '''contains no coded heuristics''' except for the '''acoustic probability matching routine'''. It shows that there is a search algorithm which guarantees a recognition and in a deterministic amount of time.

{| class="wikitable"
|+
!
!Hearsay-I System
!Dragon System
|-
|Model 
|cooperating parallel process
|probabilistic function of Markov Process 
|-
|knowledge representation
|Procedures 
|Markov Networks
|-
|Unit of Speech 
Signal Representation  
|segmentation 
|10 milli-second sample 
|-
|search strategy 
|best-first 
|all paths in parallel
|-
|search time 
|8-50 times real-time
|45-200 times real-time
|-
|What Have Been Tested
|144 connected utterances 
676 words  

5 speakers 
 
4 tasks: Chess, News Retrieval, Medical Diagnosis, Desk Calculator  

28-76 word vocabularies 
|102 utterances
564 words<ref name=":1">Lowerre, B. T. (1974). Comparison of Two Speech Understanding Systems. ''The Journal of the Acoustical Society of America'', ''56, S27''. <nowiki>https://pubs.aip.org/asa/jasa/article/56/S1/S27/740227/Comparison-of-two-speech-understanding-systems</nowiki></ref>
|-
|Performance
|<u>Percentage of words spotted and identified correctly</u> <ref>Reddy, R. (2013). ''CMU Hearsay 1973 (Short Version)''. Retrieved September 17, 2023, from <nowiki>https://www.youtube.com/watch?v=c70QlwttnVg</nowiki>.</ref> 
89% with all the sources of knowledge 

67% without semantics 

44% without syntax and semantics 

(as of October, 1973)
|85% of the words identified correctly<ref name=":1" />
|-
|Approaches 
|acoustics-phonetics, prosody, lexicon, syntax, semantics and pragmatics
|Treats speech recognition as a mathematical computation problem
rather than as an artificial intelligence problem. 
|}

== Harpy System<ref name=":0" /> ==
The Harpy system attempts to combine the best features of the Hearsay-I system and the Dragon system. For instance, it uses a mathematically tractable model, as in the Dragon system, and speech-dependent heuristics, as in the Hearsay-I system. Its optimizations on language representation and search strategy have been shown effective in improving the model speed and accuracy. Moreover, it incorporates new techniques for further improvements 

=== '''1. Model''' ===
The model of the Harpy system is a '''dynamic programming system''' with heuristics to reduce the search space, and thus increasing the speed. The system uses a network contains all possible synthetic paths and all the pronunciations of the paths. The synthetic and pronunciation knowledges are combined together in the ‘synthetic-phonetic’ paths of the network, which contains inter-state connections. 

=== '''2. Representation of knowledge''' ===
The majority of the knowledge represented in the Harpy system is represented within the '''network''', which is a set of states with '''inter-state connections'''. The network is generated by a network compiler from the '''[[wikipedia:Backus–Naur_form|BNF（Backus–Naur form）grammar]]'''<ref>Backus–Naur form. (2023, September 18). In Wikipedia.https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form</ref>, '''the phonetic dictionary''' of the lexical words, and the '''inter-word juncture rules'''. In the phonetic dictionary, the Harpy system uses a speaker-dependent acoustic-phonetic templates to represent the acoustic realization of the phones. Thus, each state in the network contains the following information: the word (the terminal symbol from the BNF grammar), a unique ID number (every BNF terminal symbol with a unique symbol), the phone (from either the phonetic dictionary or the word juncture rules), a list of prior and following states (all the states that may transition into the current state and all the states to which the current state may transition) 

==== '''2.1 Generation''' ====
The generation of the network in the following steps: the BNF grammar is used to generate a grammar network; each state in the grammar network, which represents a terminal symbol in the BNF grammar, is expanded with a phonetic subnetwork that represents the dictionary spelling for the terminal symbol; word juncture rules are added, and finally, special reduction heuristics are applied.

=== '''3. Data dependent transition probabilities''' ===
The Harpy system uses '''data-dependent transition probabilities'''. This is realized by heuristically calculate the transition probabilities for each state during the recognition process from speech-dependent knowledge, and only intrinsic '''phonemic durations''' in the Harpy system. 

The system uses '''minimum and maximum expected durations for each phone''' and the '''current duration''' of the states to calculate the transition probabilities. The current duration for a state is the number of time samples for which the state was its own best prior state. 

* The inter-state transition probability from a state is 1 if the current duration for that state is not less than the minimum expected duration for the phone of that state. If the current duration is less than the minimum expected, then the inter-state transition probability from that state is reduced by a heuristic amount that is proportional to the difference between the minimum expected and the actual current duration. If I is the minimum expected duration, C is the current duration (with C<I) then the inter-state transition probability is H<sup>I-C</sup> where H is a heuristic value. Similarly, if the current duration is not greater than the maximum expected duration, then the intra-state transition probability is 1, otherwise it is   where A is the maximum expected duration and C and H are as before. The current value used for H is.1. A value of 0 for H would be tantamount to a total rejection of a path should the state duration fall outside the interval between the minimum and maximum expected durations. A large value for H(close to 1) and a small interval between the minimum and maximum expected durations would produce a Gaussian like distribution for the transition probabilities.

{| class="wikitable"
|+
|'''Conditions'''
|'''Transition probability'''
|-
|The current duration ≥ The minimum expected duration
|1
|-
|The current duration < The minimum expected duration
|H<sup>I-C</sup>
|-
|The current duration ≤ The maximum expected duration
|1
|-
|The current duration > The maximum expected duration
|H<sup>C-A</sup>
|}

=== '''4. Segmentation''' ===
The Harpy system segments the input data into units larger than 10 mili-seconds time samples. The '''segmentation algorithm''' used in the Harpy system works as follows: The 10 milli-second time samples are processed one at a time to extend the "current" segment. As each 10 milli-second time sample is processed, it is compared against the first 10 milli-second sample of the current segment and against the middle sample. The current segment is considered complete when the distance between the current 10 milli-second sample and either the first sample or the middle sample exceeds a heuristic threshold; the current 10 milli-second sample then becomes the 1<sup>st</sup> sample of the next segment. The linear predictor coefficients that are to represent the now complete current segment are obtained from the sum of the autocorrelation coefficients of all the samples in the segment.

=== '''5. Increasing speed and accuracy''' ===

==== '''5.1 Prior state information saving''' ====
The Harpy system optimized the prior state information saving strategy in Dragon system to reach higher recognition speed. Harpy saves a small number of prior states (100 times samples worth) in memory at a time and when more room is needed, they are saved on external storage (a high speed drum). For the algorithms, Harpy calculates the probabilities by logs and thus do addition, which eliminates the need to scale.

==== '''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.

==== 5.3 State Size reduction ====
The recognition time is dependent upon the confusability among the paths in the Harpy system. The developers removed '''null states, redundant states''', and subsumed '''common states''' to reduce the network size and complexity. The former two removals have no effect on speech recognition accuracy, while the last removal has the potential influencing the recognition process.

* A null state is a state contains no synthetic or phonetic information other than the connections to its prior and following states. Harpy removes null states by linking each of it prior states to each of its following states and deleting the null states. However, the removal of null states increases the number of pointers.
* Two redundant states are 1) same terminal lexical symbol and same prior states or 2) same terminal lexical symbol and same following states. One of the states is selected and removed by Harpy.
* Two states are common if they both have the same phone and 1) same prior states or 2) same following states. Similarly, one state is selected and removed. To avoid danger of completely losing grammatical information due to subsumption of homonyms, the special character ‘!’ may use in the acoustic dictionary to indicate the network compiler.

== Impact ==
The Harpy system was a dark horse during speech recognition development. It showed a greater performance than previous systems. 

* It was the first machine that was capable of understanding '''1,011''' words<ref name=":2">McNamara. C. (2016) A brief history of speech recognition. https://www.linkedin.com/pulse/brief-history-speech-recognition-cronan-mcnamara/</ref>, which was a substantial improvement as previous model can recognize only less than 20 words. 
* Harpy was also capable of recognizing complete sentences<ref name=":0" />. 
* Moreover, the optimization of the previous systems and newly incorporated heuristics both benefited the '''speed''' (requires 4.5 million machine instructions per second) and '''accuracy''' (70.9%-88.6% utterance accuracy) of the recognition<ref name=":0" />. 
* The system also performed quite well for data with background noise<ref>Yegnanarayana. B, Raj. R. D. (1977). Performance of Harpy speech recognition system for speech input with quantization noise. ''J. Acoust. Soc. Am.'' 1; 62 (S1): S27. <nowiki>https://doi.org/10.1121/1.2016106</nowiki></ref>.
* By incorporating Harpy system and the method of HMM (hidden Markow models), Carnegie Mellon University later developed the '''Sphinx system'''<ref>Juang, B. H., & Rabiner, L. R. (2005). Automatic speech recognition–a brief history of the technology development. ''Georgia Institute of Technology. Atlanta Rutgers University and the University of California. Santa Barbara'', ''1'', 67.</ref>. 

== Key Innovations ==

* Collapsing common sub-networks reduces overall network complexity. This breakthrough allows faster processing by simplifying the network.

* Learning lexical representations and phonemic templates from training data accounts for coarticulation effects. Allophonic variations arespecified in the Harpy system by the use of many unique phones (60) withone template per phone rather than a smal! number of phones with alarge number of templates per phone. Optimizing the dictionary and templates using speech evidence from training data is a breakthrough improving accuracy.

* Calculating state probabilities dynamically makes the system more speech-dependent. This breakthrough improves robustness compared to statistical a priori calculations.

* The HARPY system represents knowledge as a finite state network without a-priori transition probabilities. This breakthrough allows more flexible speech-dependent probability calculations. 

* HARPY only searches a few "best" syntactic and acoustic paths to find the optimal path. This dramatically reduces search complexity compared to examining all possible paths.

* Segmenting the utterance reduces its length effectively, decreasing the number of required state probability updates. This significantly speeds up processing.

== Future research ==
For Harpy system, the majority of time used by the system (more that 64%)<ref name=":0" /> is for the generation ofthe autocorrelation and linear predictor coefficients. This problem is not unique to Harpy; all speech systems that use this parametric scheme must face this problem. 

The computational complexity of generating autocorrelation and linear prediction coefficients for speech recognition is still a challenge even with modern techniques and hardware. But the raw computational requirements are still very high for real-time low-latency speech recognition with modern neural network models. Hardware and algorithms have improved, providing much higher peak computing capacities, but real-time performance still requires significant optimization and acceleration. It is an active area of research to find faster and less resource-intensive approaches suitable for embedded/edge applications. 

== ChatGPT ==
We asked Chatgpt to review this Wiki page on Carnegie Mellon's Harpy System to receive feedback and suggestions for improvement, especially on the content and structure of the page, and identify areas where the page can be enhanced in terms of clarity and organization to better serve its intended audience. Provided below is its evaluation of our page:  

"The Wiki page on Carnegie Mellon's Harpy System provides a comprehensive overview of the technology, encompassing its historical context, technical intricacies, and notable innovations. The inclusion of historical background before delving into the Harpy System's development is particularly valuable for contextualizing its significance. The technical terminology may pose challenges for non-expert readers, but it offers insights into the system's complexity. The integration of visual aids, such as tables or diagrams, would be beneficial for conveying complex concepts visually. To ensure clarity and readability, proofreading for grammar and language issues would be beneficial. Finally, a concise summary or concluding section could reinforce the key takeaways from the content, providing readers with a clear understanding of the topic."

== Contributors ==
Sherry Yu-Ting Yeh

Wansu Zhu

Jingsi Huang

Wenjun Meng

== References ==
<references responsive="0" />