Abstract:
Improved word accuracy of speech recognition can be achieved by providing a scheme for automatically limiting the acceptable word sequences. Speech recognition systems consistent with the present invention include a lexicon database with words and associated lexical properties. The systems receive exemplary clauses containing permissible word combinations for speech recognition, and identify additional lexical properties for selected words in the lexicon database corresponding to words in the received exemplary clauses using lexical property tests of a grammar database. Certain lexical property tests are switchable to a disabled state. To identify the additional lexical properties, the exemplary clauses are parsed with the switchable lexical property tests disabled to produce an index of the lexical properties corresponding to the exemplary clauses. The lexicon database is updated with the identified additional lexical properties by assigning the lexical properties to the corresponding words of the lexicon database. The grammar database is compiled with the lexical property tests enabled and the lexicon database with the assigned lexical properties to produce a grammar that embodies constraints of the lexical property tests and the lexical properties.

Description:
BACKGROUND OF THE INVENTION 
     A. Related Applications 
     This application is related to U.S. Ser. No. 08/235,046, entitled &#34;Speech Interpreter With A Unified Grammar Compiler,&#34; filed Apr. 29, 1994 now U.S. Pat. No. 5,642,519, and incorporated herein by reference. 
     B. Field of the Invention 
     This invention relates generally to speech comprehension and, more particularly, to voice-activated command and control systems. The present invention facilitates the process of recognizing speech by automatically eliminating many nonsensical word sequences from consideration. 
     C. Description of the Related Art 
     Speech recognition systems generally include two main elements: a speech recognizer and an interpreter. The speech recognizer converts sound input into sequences of words. The interpreter then tries to understand the input by determining the relevant meaning of the words. 
     To achieve useful recognition rates, conventional speech recognition systems impose constraints other than word lists, such as by specifying a grammar that delineates allowable or acceptable word sequences or by providing statistical likelihoods for word sequences. 
     Programmers build the grammars by hand or with rule compilers as context-free formalisms determining the acceptable word sequences. Hand-built grammars generally provide fine control over the word sequences recognized, but their construction is difficult and painstaking, even for the relative few who are initiated in the art. 
     The statistical models, on the other hand, use tables of the probabilities of each word (unigram), each word pair (bigram), and each word triple (trigram). Some researchers have experimented with extending the statistical systems to include n-grams where &#34;n&#34; is higher than 3, but generally they only express the probabilities of adjacent words. Statistical grammars are built automatically by simply running an analysis program over an appropriate collection of the kinds of sentences that one wishes to recognize. A prime example of this technology is the ARPA-funded Wall Street Journal dictation project. In that project researchers train on the text of previously-printed articles from the Wall Street Journal and test them on text read from a later edition of the Journal. Unfortunately, the database of Wall Street Journal text used in these experiments contains approximately 44 million words, and some of the researchers using this database have indicated that their speech recognition systems would work better with a more complete training set. 
     In the domain of voice-activated command and control systems, one use for a speech recognition system, the utterances to be recognized do not correspond directly to any existing body of text that could be used analogously to the Wall Street Journal text&#39;s role in training the dictation recognizers. Traditional statistical modeling requires a huge database of expected utterances. Statistical models do not have any abstraction of the words, so the actual co-occurrence of words is necessary to count the relative frequency of each. This means that any word pair that does not occur in the training data would be assigned the most unlikely bigram probability. 
     One application for a voice-activated command and control system allows speakers to query the contents of a computerized catalog of products. Such an application requires a grammar that recognizes action words and phrases, such as &#34;can you show me &lt;item&gt;?&#34; or &#34;what &lt;item&gt; do you carry?&#34; in a spoken query, with the speaker supplying a phrase that specifies the item of interest. One over-simplified grammar of such item specification phrases would allow any basic item such as &#34;pants&#34; to be modified by any combination of style family, pattern style, color, size, gender, age, fabric type, fabric style, maker&#39;s name, etc. A particular sweater could thus be called &#34;the petite women&#39;s medium pink jewel-neck cashmere fine-knit `drifter` sweater.&#34; Such an accepting grammar could perform at acceptable levels for extracting the meaning of an input word combination from a written form of the item description. 
     The perplexity of the grammar produced by the cross-product of all these choices is, however, so large that the word accuracy of the speech recognition becomes uselessly low when such a loosely constrained grammar is used. The speech recognition system would accept phrases that no user would ever utter, for example, &#34;the casual cashmere diaper bag.&#34; 
     If a lexicon contained lexical or word entries for every modifier marked with a feature containing the set of things it could realistically modify, or a set of classes of things, then the grammar could be written to allow only the reasonable or acceptable combinations and to rule out the ridiculous ones that should be omitted. This would in turn reduce the perplexity created by loosely constrained grammars. With a grammar compiler that accepts such restrictions based on features in the lexicon, such a markup seems like a possible solution. The grammar could, for instance, record classes of basic items, noting that, for example, &#34;chinos&#34; and &#34;jeans&#34; are &#34;tough clothing&#34; and then only allow them to be associated with fabrics appropriate for &#34;tough&#34; clothes. This would block &#34;lace chinos&#34; but allow &#34;silk blouse&#34; and &#34;denim jeans.&#34; The disadvantage of this approach is that it requires a grammar writer to figure out and record the features that determine allowable modifiers as well as a large amount of detailed work to make the annotations in the lexicon. 
     Although a loosely constrained grammar permits recognition of unacceptable word sequences, tighter constraints based on exactly the items in the catalog would refuse certain acceptable word sequences. Such a system would not recognize combinations of modifiers and basic items that, while reasonable to the speaker, are not specified exactly in the catalog. For example, if the catalog had &#34;canvas jackets&#34; and &#34;denim jeans&#34; but no &#34;denim jackets,&#34; then the speech recognition system with such a restricted grammar built from only catalog item descriptions could not understand the phrase &#34;denim jacket.&#34; Presented with those sounds, the system might produce something like the &#34;d&#39;women jacket&#34; pronunciation of &#34;the women[&#39;s] jacket,&#34; but it could not understand what the user said, i.e., interpret what the user said into a hypothetical catalog item. This would be baffling to a naive user of the system, especially since rephrasing his request to include &#34;a jacket made of denim&#34; would also fail. 
     There is therefore a need for a speaker-independent speech recognition system for a multitude of command and control applications that uses a flexible grammar to limit acceptable word sequences in a manner that improves word accuracy in the speech recognition process. 
     SUMMARY OF THE INVENTION 
     Accordingly, embodiments of the present invention are directed to a method, apparatus, and product that substantially obviates one or more of the problems due to limitations, shortcomings, and disadvantages of the related art. 
     In accordance with the present invention, as embodied and broadly described herein, improved word accuracy for speech recognition can be achieved by providing a scheme for automatically limiting the acceptable word sequences or the word sequences discernable during the speech recognition process. According to one aspect of the present invention, a method, apparatus, and computer program product for automatically modifying a lexicon database containing words and associated lexical properties is comprised of a number of operations, including receiving exemplary clauses containing permissible word combinations for speech recognition, and identifying additional lexical properties for selected words in the lexicon database corresponding to words in the received exemplary clauses using lexical property tests of a grammar database. The exemplary clauses indicate the types of word sequences to be understood during a speech recognition process. Certain lexical property tests are switchable to a disabled state. To identify the additional lexical properties, the exemplary clauses are parsed with the switchable lexical property tests disabled to produce an index of the lexical properties for words in the exemplary clauses. The lexicon database is updated with the identified additional lexical properties by assigning the lexical properties to the corresponding words of the lexicon database. The grammar database is compiled with the lexical property tests enabled and the lexicon database with the assigned lexical properties to produce a grammar that embodies constraints of the lexical property tests and the lexical properties. 
     According to another aspect of the present invention, a method, apparatus, and computer program product for speech recognition involves a lexicon database containing words and associated lexical properties and a grammar database with lexical property tests. Certain lexical property tests are switchable between a disabled state and an enabled state. Consistent with this aspect of the invention, an input speech pattern contains a word sequence that is parsed using the switchable lexical property tests in the enabled state. This permits the identification of a command corresponding to the parsed word sequence and, in turn, initiation of the command to instruct a processor to perform an operation. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, serve to explain the advantages and principles of the invention. In the drawings, 
     FIG. 1 is a block diagram showing the main components of a speech interpreter used to limit the number of recognizable word combinations; 
     FIG. 2 is a flow diagram of the steps performed by the feature parser according to an implementation of the present invention; 
     FIG. 3 is a flow diagram of the steps performed by the lexicon modifier according to an implementation of the present invention; 
     FIG. 4 is a block diagram showing the main components of a speech interpreter used to recognize acceptable word combinations; and 
     FIG. 5 is a diagram of a data processing system that can be used in an implementation of the present invention. 
    
    
     DETAILED DESCRIPTION 
     Reference will now be made in detail to an implementation of the present invention as illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings and the following description to refer to the same or like parts. 
     A. Overview 
     Systems consistent with the present invention automatically limit the number of acceptable word sequences by employing an interpreter that uses rules for parsing a set of word sequences to identify additional lexical properties of words in the set that can be used during a recognition process to discern acceptable word sequences. The system performs two distinct functions. The first involves building the set of acceptable word sequences. The second uses those word sequences to recognize spoken input. 
     B. Building A Set Of Acceptable Word Sequences 
     In accordance with the present invention, speech interpreter 100 shown in FIG. 1 includes grammar database 110, lexicon database 120, feature modifier 130, and lexicon modifier 140. Interpreter 100 may be incorporated into systems such as command and control systems that instruct computers to perform specific functions in response to spoken input. 
     Grammar database 110 constitutes a set of restrictions defining both permissible and acceptable word sequences. Permissible word sequences come from parsing a set of exemplary sentences or clauses that represent word sequences the system should be able to recognize. Acceptable word sequences are the ones that, applying certain sequence rules and related constraints, correspond to word sequences that the system can interpret and take appropriate action. 
     The sequence rules and constraints help parse input word sequences according to specific rules that define conditions under which different words can be combined, for example, in a single sentence. A portion of one such rule is represented as follows: 
     [material][item]. 
     This rule alone means that any word defined in lexicon database 120 with a &#34;material&#34; type may appear before any word of the &#34;item&#34; type. Both are optional, as shown by the brackets (&#34;[ ]&#34;) around each word, meaning that there is no absolute requirement that they be in this sequence. A word of the &#34;item&#34; type may be alone; so too may a word of the &#34;material&#34; type. 
     The constraints, however, dictate which specific words can be combined in accordance with a sequence rule. The constraints, called lexical property (or feature) tests, prescribe both the permissible and acceptable word sequences based on certain word annotations in lexicon database 120 that are characterized as &#34;features&#34; of the words. For example, only specific words of a &#34;material&#34; type may precede specific words of the &#34;item&#34; type based on requiring that they share certain compatible features. 
     Lexicon database 120 includes lexical entries of words and related annotations, some of which describe features of the words. Initially, the words of lexicon database 120 may be automatically generated from, for example, an input word set like a catalog or dictionary. Additionally, some of the annotations for the words are preset so the words can be differentiated by type. For example, a lexical entry for the word &#34;sweater&#34; from the input word set is initially annotated to indicate that the word represents an &#34;item&#34; type, and a lexical entry for the word &#34;woolen&#34; from the input word set is annotated to indicate the word represents a &#34;material&#34; type. Applying the grammar rule that permits material types to precede item types, without additional constraints, would result in &#34;woolen sweater&#34; as a permissible word sequence. But if &#34;woolen&#34; and &#34;sweater&#34; do not share a common feature required by a defined constraint on the combination of [material] and [item], then &#34;woolen sweater&#34; would not be an acceptable sequence. 
     Although this embodiment uses two databases (110 and 120), other configurations are possible as well, for example, one database with both a grammar and a lexicon can be used, as can distributed databases. 
     One purpose of interpreter 100 is to limit the permissible word sequences to only those considered to be acceptable. Systems employing interpreter 100 should be able to &#34;hear&#34; all permissible word sequences, but only understand those that are acceptable, i.e., those that include words having some meaningful relationship. For example, sequences that have no meaning, like &#34;cashmere diaper bag,&#34; may be heard but not understood. Hearing such sequences would allow unacceptable perplexity in a speech recognizer but is not a problem in an interpreter that has words typed or previously recognized as its inputs. Perplexity is an issue only when dealing with the uncertainty of speech recognition. Thus, lexicon database 120 may dictate that &#34;diaper bag&#34; and &#34;jeans&#34; are of the &#34;item&#34; type with an annotation for a fabric feature defined as &#34;sturdy.&#34; The word &#34;cashmere&#34; in lexicon database 120 is a &#34;material&#34; type with a &#34;soft&#34; fabric feature, while the word &#34;denim&#34; is also a &#34;material&#34; type and has a different fabric feature such as &#34;sturdy.&#34; The combination of grammar database and lexicon database 120, with a &#34;[material][item]&#34; rule and constraint that only materials and items with common fabric features are acceptable sequences, would thus permit the combinations &#34;denim diaper bag&#34; and &#34;denim jeans&#34; but not &#34;cashmere diaper bag&#34; and &#34;cashmere jeans.&#34; 
     Some of the lexical features in lexicon database 120 are derived automatically from pre-existing data, making the task of building lexicon database 120 easier, and the cost for adding new words much smaller. The pre-existing data, shown in FIG. 1 as the exemplary clauses directed into feature parser 130, corresponds to the permissible word sequences or speech input that the speaker would reasonable expect the system to recognize. 
     To derive features for lexicon database 120 automatically, feature parser 130 uses grammar database 110 to parse the exemplary clauses to determine the word sequences or, more particularly, features of selected words common to the clauses and lexicon database 120. In a grammar designed with rules using lexical features from pre-existing data, word combinations in the pre-existing data would be rejected if parsed with the rules enabled because the bare or incomplete lexicon would have only the types of the basic items such as a &#34;diaper bag,&#34; without essential parts of the feature annotations. A system like this would reject reasonable combinations as unreasonable. For example, the bare lexicon database may include the word &#34;diaper bag&#34; as an item type, but only after processing the pre-existing data can the system determine that &#34;diaper bag&#34; item may be modified by certain material types like &#34;denim.&#34; If the pre-existing data were parsed with all of the constraints enabled, the acceptable material types could not be identified because the relationships between item types and material types are not yet known when the pre-existing data is parsed. 
     This problem is avoided by allowing certain constraints of grammar database to be disabled when parsing exemplary clauses. Disabling certain lexical feature tests during parsing permits the system to capture information on permissible word sequences. 
     Therefore, feature parser 130 preferably determines whether a given constraint from grammar database 110 can be disabled during the parsing of exemplary clauses. Parser 130 can make this determination by testing an indicator or signal that indicates whether the constraint can be disabled. In the above example, the constraint requiring a material that precedes an item share a common fabric feature would be switchable. 
     It can be expressed in grammar database 110 as follows: 
     
         ______________________________________{ [material][item]where material.fabricType ˜ε item.fabricTypes______________________________________}. 
    
     The &#34;˜ε&#34; indicator would mean the constraint could be disabled. Thus, when feature parser 130 parses input exemplary clauses, sequences like &#34;denim diaper bag,&#34; &#34;denim jeans,&#34; &#34;cashmere diaper bag,&#34; and &#34;cashmere jeans&#34; would all be permissible sequences. When the fabric feature lexical test is later turned on it will block out the unacceptable sequences and allow only &#34;denim diaper bag&#34; and &#34;denim jeans.&#34; 
     Indexing and then processing the results of the parsed clauses provides the information content needed to automatically mark-up or update the lexicon database with the results derived from the pre-existing data, for example, indicating the available blouse fabrics. Feature parser 130 builds the index of parsed clauses. 
     Lexicon modifier 140 performs the update function, modifying lexical entries in lexicon database 120 for each selected word to reflect the extracted features. In the &#34;cashmere diaper bag&#34; example, lexicon database 120 would be modified to reflect the information that the &#34;diaper bag&#34; item has a &#34;sturdy&#34; fabric feature, the same as &#34;denim&#34; material. 
     Once lexicon database 120 is enhanced with this information, the switchable constraints of grammar database 110 can be turned on for speech recognition or compilation of rules for use in speech recognition, as explained in detail in U.S. Ser. No. 08/235,046. When used in a speech recognition application, interpreter 110 will thus block &#34;cashmere&#34; from modifying &#34;diaper bag&#34; or &#34;jeans,&#34; but allow the combinations &#34;denim diaper bag&#34; and &#34;denimjeans.&#34; 
     FIG. 2 is a flow diagram of the preferred steps performed by feature parser 130. Feature parser 130 receives input exemplary clauses (step 210). Some clauses correspond to actual commands and some are merely logically possible, but are not acceptable. In the latter case, the system will notify the user after the recognition process, for example, by synthesized voice output, that an input does not correspond to an available command. 
     Feature parser 130 next parses the exemplary clauses with the switchable rules in grammar database 110 disabled to capture all possible features of selected words common to the exemplary clauses and lexicon database 120 (step 220). In an alternative configuration, feature parser 130 may capture features on words found in the exemplary clauses but not in lexicon database 120. With the exemplary clause, &#34;petite women&#39;s medium pink jewel-neck cashmere fine-knit `drifter` sweater,&#34; feature parser 130 determines whether all of the words preceding &#34;sweater&#34; can modify &#34;sweater,&#34; in accordance with rules and related non-optional constraints from grammar database 110. 
     As feature parser 130 parses the exemplary clauses, it builds an index logically equivalent to a multidimensional matrix or array including selected words from lexicon database 120 and the features for those words identified from the context of the selected words used in the exemplary clauses (step 230). For example, feature parser 130 would include an index entry for &#34;sweater&#34; with a corresponding list of features and values such as: sizemod: &#34;petite&#34;, 
     gendermod: &#34;women&#39;s&#34;, 
     size: &#34;medium&#34;, 
     color: &#34;pink&#34;, 
     patternstyle: &#34;jewel-neck&#34;, 
     fabric: &#34;cashmere&#34;, 
     fabricmod: &#34;fine-knit&#34;, 
     stylename: &#34;drifter&#34;. 
     In one implementation of the present invention, lexicon modifier 140 performs the steps illustrated in the flow diagram of FIG. 3. As a first step, lexicon modifier 140 extracts features from the word-feature index built by feature parser 130 (step 310). Next, lexicon modifier 140 identifies the word entry in lexicon database 120 that exhibits the extracted feature (step 320). For each word in the index, lexicon modifier 320 modifies the lexicon entry accordingly to reflect the corresponding features for that word in the index (step 330). Thus, lexicon database 120 would be modified to indicate that &#34;sweater&#34; has possible feature values that would permit its combination with &#34;petite&#34;, &#34;women&#39;s&#34;, &#34;medium&#34;, &#34;pink&#34;, &#34;jewel-neck&#34;, &#34;cashmere&#34;, &#34;fine-knit&#34;, &#34;drifter&#34; in rules like the &#34;[material][item]&#34; rule. 
     In this fashion, interpreter 100 extracts information from exemplary clauses to update lexicon database 120. By combining this information with the optional rules of grammar database 110 enabled during the speech recognition process, interpreter 100 can select from lexicon database 120 only the acceptable combinations, like the &#34;petite sweater,&#34; but not the other possible one &#34;jewel-neck jeans.&#34; 
     C. Recognizing Acceptable Word Combinations 
     FIG. 4 is a block diagram showing the main components of speech interpreter 100&#39; used during the speech recognition process. As shown, grammar database 110 and lexicon database 120 are used to recognize acceptable word combinations. In this operation, however, the switchable rules of grammar database 110 are enabled to limit the permissible word combinations from lexicon database 120 to only the acceptable ones. Speech understanding generally requires the use of speech recognizer 410, natural language processor 420, and application command translator 430. 
     There are at least two ways of performing the recognition process. The first would be to compile grammar database 110 and lexicon database 120 to generate a speech recognition grammar and a natural language grammar, as explained in U.S. Ser. No. 08/235,046 with speech recognizer 410 using a speech recognition grammar compiled from the natural language grammar. Such a speech recognition grammar would reflect all the constraints imposed by enforcing the switchable restrictions. The natural language understanding is done by natural language processor 420 using the natural language grammar including only the acceptable word sequences. 
     An alternative mechanism to recognize spoken input in accordance with the separate grammar database 110 and lexicon database 120 involves applying the rules and feature tests during recognition. The first option offers the advantage of faster speech recognition but requires an extensive compilation process. The second approach, however, may be too computationally intensive for practical use with speech recognizers on current computers. 
     Speech recognizer 410 is preferably a Hark speech recognizer available from B.B.N., 70 Fawcett Street, Cambridge, Mass. 02138. Other commercially available speech recognizers may also be appropriate and interpreter 100 can be adapted by one skilled in the art to operate with different speech recognizers without departing from the spirit of the present invention. Examples of commercially available speech recognizers which operate with interpreter 100&#39; include Texas Instruments&#39; Dagger and Carnegie Melon University&#39;s SphinxI. 
     Briefly, a speech recognition grammar generated by a unified grammar compiler (not shown), such as the one described in U.S. Ser. No. 08/235,046 is loaded into speech recognizer 410 during initialization. Next, speech recognizer 410 matches the input digitized speech to sequences of phonemes as they sound in various contexts using a Hidden Markoff Model that represents the low-level characteristics of the sounds. Speech recognizer 410 then produces a best-guess word sequence, shown in FIG. 4 as the validated word sequences, by using an internal speech-recognition finite-state machine constructed from the phoneme sequences derived from speech recognition grammar. 
     In this embodiment, the natural language processor 420 named SWIFTUS (SoftWare Instead of Fastus for Text UnderStanding) was written at Sun Microsystems Laboratories, Inc., based on a published description of a natural language processor called Fastus developed by Jerry Hobbs at SRI International, Stanford, Calif. Further details on natural language processor 420 can be found in U.S. Ser. No. 08/235,046. In general, natural language processor 420 generates command summary structures corresponding to the validated word sequences, i.e., selecting and interpreting the acceptable word combinations from among the permissible word combinations using the enabled rules of grammar database 110. 
     Application command translator 430 uses the command summary structures produced by the natural language processor 420 to generate commands to control the system. 
     D. Hardware of Data Processing System 
     FIG. 5 is a diagram of a data processing system consistent with the present invention. In accordance with an embodiment of the present invention as shown in FIG. 5, the speech interpreter is implemented on a general purpose host computer 510 that includes central processing unit (CPU), host memory 530, host bus controller 540, host system bus 550, monitor 560, keyboard 570 and mouse 580. An acoustic input device 590 having an analog-to-digital (A/D) converter 592 and microphone 594 is coupled to system bus 550. 
     Host computer 510 is also coupled to an acoustic output device 600 having a digital-to-analog converter (DAC) 602 and an audio speaker 604. In some embodiments, the conversion of analog speech to and from digital form is accomplished remotely from host computer 510, for example, by coupling digital ISDN telephony lines to system bus 550 of host computer 510 via an appropriate adapter (not shown). 
     E. Conclusion 
     To overcome the shortcomings of conventional speech recognition systems, the present invention automatically updates a lexicon to include the logical extensions of the database of acceptable items using a grammar with certain lexical feature tests that can be disabled during the collection of information for the update process. The modified lexicon is then be used with all of the grammar&#39;s lexical feature tests switched on to parse spoken input. In this manner, the system recognizes only the acceptable word sequences, given the data used to initially mark the lexicon. 
     The foregoing description of an implementation of the invention has been presented for purposes of illustration and description. It is not exhaustive and does not limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practicing of the invention. For example, the described implementation includes software but the present invention may be implemented as a combination of hardware and software or in hardware alone. The scope of the invention is defined by the claims and their equivalents.