Natural language speech recognition using slot semantic confidence scores related to their word recognition confidence scores

[0002] This application is a continuation-in-part application of U.S. patent application Ser. No. 08/576,874 filed on Dec. 21, 1995 and entitled METHOD AND SYSTEM FOR BUILDING AND RUNNING NATURAL LANGUAGE UNDERSTANDING SYSTEMS, now U.S. Pat. No. 6,292,764, issued Sep. 18, 2001. This application also claims priority of provisional application serial No. 60/091,047 filed Jun. 29, 1998 entitled METHOD AND APPARATUS FOR PROCESSING AND INTERPRETING NATURAL LANGUAGE IN A VOICE ACTIVATED APPLICATION, invented by Eric I Chao Chang and Eric G. Jackson.

[0003] This invention relates to the field of interpreting natural language. More particularly, this invention relates to a method and apparatus for processing and interpreting natural language which enhances the operation through the use of semantic confidence values to enhance efficiency.

[0004] The following definitions may be helpful in understanding the background of the invention as it relates to the invention and the discussion outlined below.

[0005] Confidence: a measure of a degree of certainty that a system has accurately identified input language. In the preferred embodiment, it is a measure of the degree of perceived acoustic similarity between input speech and an acoustic model of the speech.

[0006] Phrase: a sequence of words.

[0007] Example: “from Boston”

[0008] Grammar rule: a specification of a set of phrases, plus meaning of those phrases

[0009] Example: (from [(boston ? massachusetts)(dallas ? texas)]

[0010] Generates: “from boston”, “from boston Massachusetts”, “from dallas”, “from dallas texas”

[0011] Grammar: a set of grammar rules.

[0012] Edge: a match located by a parser of a grammar rule against a phrase contained in an input sentence.

[0013] Example: From the sentence “I want to fly from Boston to Dallas,” a parser could create an edge for the phrase “from Boston” using the grammar rule shown above.

[0014] Slot: a predetermined unit of information identified by a natural language interpreter from a portion of the natural language input. For example, from the phrase “from Boston” the natural language interpreter might determine that the “origin” slot is to be filled with the value “BOS” (the international airport code for Boston).

[0015] Parse tree: a set of edges used in constructing a meaning for an entire sentence.

[0016] Example:

[0017] Natural language interpreters are well known and used for a variety of applications. One common use is for an automated telephone system. It will be apparent to those of ordinary skill in the art that these techniques can and have been applied to a variety of other uses. For example, one could use such a system to purchase travel tickets, to arrange hotel reservations, to trade stock, to find a telephone number or extension, among many other useful applications.

[0018] As an example, consider a system for use in providing information about commercial passenger air flights. A caller to the system might say “I want to fly from Boston to San Francisco, tomorrow.” This exemplary system requires three pieces of information to provide information about relevant air flights including the origin city, the destination city and the time of travel. Other systems could require more or less information to complete these tasks depending upon the goals of the system. While the exemplary system also uses a speech recognizer to understand the supplied spoken natural language, it could also receive the natural language via other means such as from typed input, or using handwriting recognition.

[0019] Using a predetermined grammar with a set of grammar rules, such a system parses the sentence into edges. Each edge represents a particular needed piece or set of information. The sentence can be represented by a parse tree as shown in the definitions above.

[0020] In a parsing operation, the system performs the parsing operation by matching grammar rules to the natural language input. For example, one grammar rule that can specify than an origin expression is the word “from” or the phrase “out of” followed by a city name. If the natural language input is “I want to fly from Boston to Dallas:, the system will locate the phrase “from Boston” and create a record in its internal data structures that these words match the origin expression grammar rules. This record is sometimes referred to as an edge. Systems look for predetermined grammars within collections of natural language. The system performs the parsing operation in accordance with the grammar as a way of forming/filling the desired edges with information from a natural language input. For example, the natural language interpreter identifies the initial city by seeking any of several origin city words such as <‘from’, ‘starting’, ‘leaving’, ‘beginning’, . . . >related to a city name from a list of cities. If the natural language interpreter finds an origin city and a city from the list, it will then fill the origin city edge. Similarly, the natural language interpreter identifies the destination city by seeking any of several destination city words such as <‘to’, ‘ending’, ‘arriving’, ‘finishing’, . . . >related to a city name from the list of cities. If the natural language interpreter finds a destination city and a predefined city, it will then fill the destination city edge. The grammar for the natural language interpreter similarly identifies the desired time of the flight by seeking any of several time words such as <‘o'clock’, ‘morning’, ‘afternoon’, ‘a.m.’, ‘p.m.’, ‘January’, ‘February’, . . . , ‘Monday’, ‘Tuesday’, . . . >related to a number. Using this technique, the natural language interpreter can interpret spoken utterances if they contain the requisite information, regardless of the ordering of the sentence. Thus, the sentence listed above as “I want to fly from Boston to San Francisco, tomorrow,” will provide the same result as the sentence, “Please book a flight to San Francisco, for flying tomorrow, from Boston.”

[0021] If the natural language interpreter is unable to identify the appropriate words, or a related city name, then the parsing will be terminated as unsuccessful. For example, if the caller says, “I want to fly to visit my mother,” the parsing will be unsuccessful. There is no source city word nor source city in the sentence. Further, even though the natural language interpreter finds a destination city word, it cannot find a city name that it recognizes.

[0022] For a natural language interpreter used in conjunction with a speech recognition system, the natural language interpreter is provided the speech recognizer's best determination of each word resulting from the recognition operation. A speech recognizer ‘listens’ to a user's spoken words, determines what those words are and presents those words in a machine format to the natural language interpreter. As part of the recognition operation, each word is provided a word confidence score which represents the confidence associated with each such word that the speech recognizer has for the accuracy of its recognition. Thus, it is generally considered useful to take into account the accent or speech patterns of a wide variety of users. A score is generated and associated with each word in the recognition step. Using the scores for each individual word is not entirely satisfactory because that collection of scores does not relate to the meaning the speaker intends to convey. If a single word has a very low word confidence score, the user may be required to re-enter the request.

[0023] In one prior approach, the scores for each of the words are combined into a single composite confidence score for the entire sentence. While this approach solves certain problems associated with using the scores for each word and provides a workable solution, it suffers from several drawbacks.

[0024] The composite confidence score described above is weighted by all the words in the entire sentence. In a long sentence, a speaker might use many words that are in essence unrelated to providing the information that the natural language interpreter needs. For example, if the speaker says, “Please help me to arrange a flight tomorrow to visit my friend for their birthday celebration leaving from Minneapolis and arriving in Cleveland.” In this example, assume that the speaker talks clearly, so that almost every word has a very high confidence score. A loud background noise occurs during the speaking of the words “Minneapolis” and “Cleveland” so that the confidence score for those two words is low. In fact the speech recognizer incorrectly recognizes one of the words. Nevertheless, because the composite confidence score is high for the entire sentence, the recognition for the sentence is accepted. Thus, the natural language interpreter instructs the system to find the wrong flight information.

[0025] On the other hand, even if the critical information is all properly recognized, if the composite confidence score is low, the entire sentence is rejected. For example, the speaker says, “I want to fly tomorrow from Chicago to Phoenix.” In this example also assume that the speaker talks clearly. The speech recognizer properly identifies the words, “tomorrow from Chicago to Phoenix.” A loud background noise occurs during the speaking of the words, “I want to fly.” Those words have a low confidence score. Thus, even though the critical information is accurately recognized this sentence is rejected because the composite confidence score for the sentence is low. Because of the operation of prior systems, the information is rejected and the user is required to again provide all the information. This is inconvenient for the user.

[0026] As can be seen, use of a composite confidence score for the entire sentence results in an operation of the system which is not optimal. Under one set of conditions described above, the system will attempt to utilize incorrect information in carrying out its task. Under the other set of conditions described, the system will require the user to re-provide all of the information, i.e., repeat the entire sentence. One scenario provides an incorrect result, the other is inconvenient to the user.

[0027] What is needed is a natural language interpreter for use in conjunction with a speech recognizer which provides more accurate results. What is further needed is a natural language interpreter for use in conjunction with a speech recognizer which does not require a user to re-enter information that was correctly received.

[0028] According to the present invention, a stream of input speech is coupled as an input to a speech recognizer. The speech can be provided to the speech recognizer directly from a user or first stored and provided from a memory circuit. Each input word is recognized by the speech recognizer and a word confidence score is associated to with each corresponding recognized word. The recognized words and their associated word confidence scores are provided to a natural language interpreter which parses the stream of recognized words into predetermined edges. From the edges, the natural language interpreter forms semantic slots which represent a semantic meaning. A slot confidence score is determined for each slot. The slot confidence score is used as a basis for determining the confidence to be placed into a particular predetermined semantic meaning. Based upon the slot confidence score, an ancillary application program determines whether to accept the words used to fill each slot. If the slot is rejected, the application program can request the user to repeat the information necessary to fill that slot only, rather than requiring the user to repeat the entire stream of input speech.

[0029] While the invention is described in terms of edges and slot confidence scores, it will be apparent to one of ordinary skill in the art that the essence of using slots is to provide a confidence score for a particular meaning. There are a variety of ways that this can be achieved. Nevertheless, the remainder of this patent document will discuss the invention in terms of slot confidence scores. It will be understood that this could be interpreted to mean any semantic meaning.

[0030] FIG. 1 shows a flow chart of the method of the preferred embodiment.

[0031] There are a variety of applications for automated speech systems. Such systems utilize a voice recognizer which receives input speech and determines what words were spoken. The output from the speech recognizer is then provided to a natural language interpreter which then determines what meaning should be attributed to the recognized words. The output of the natural language interpreter is then provided to and utilized by an ancillary applications program. The applications program can be any one of a myriad of well recognized types.

[0032] The choice of application is not material to the operation or construction to the present invention. As an aid to understanding the present invention, the example of a system for providing information about commercial passenger air flights is given. The scope of the invention is not intended to be limited to this application. Rather, the invention is directed toward a method of improving the operation of a system which receives a stream of speech, interprets the speech, and then process the natural language for use by the application. In a nutshell, the invention forms a confidence score for each of the several predetermined slot associated with the speech. If the confidence score exceeds a predetermined threshold for all the slot, the application program can then process the language. Otherwise, the application can query the user to clarify only the slot that fails to exceed threshold. Depending upon the circumstances in which the invention is used, more than one threshold value can be selected, with a different threshold used for different slots. Thus slots having varying perceived importance can have varying thresholds to account for their relative importance. This form of conveying information is more like natural human interaction than the prior technique where the entire sentence must be re-spoken by the user.

[0033] The invention will be better understood, by considering the steps outlined in the flow chart of FIG. 1. The process begins at the step 100. In the step 102 a stream of input speech is received by a speech recognizer. The speech recognizer can be of a type commercially available. The speech recognizer can be of a type that includes a special purpose hardware system, or could be software running on a general purpose computer. One example of a speech recognizer could be one of the products currently available from Nuance Communications, of Menlo Park, Calif. The input speech could be applied directly to the speech recognizer or it could be stored in a memory. The novel aspects of the invention do not depend upon the exact source of the input speech.

[0034] The speech recognizer examines the input speech and makes a conventional determination as to the identity of each word in the input stream in the step 104. Additionally, the speech recognizer assigns a word confidence score to each recognized word. Next, the output of the recognized words and their associated word confidence scores are provided to a natural language interpreter in the step 106. The natural language interpreter can be of a type commercially available. The natural language interpreter can be of a type that includes a special purpose hardware system, or could be software running on a general purpose computer. One example of a natural language interpreter could be one of the products currently available from Nuance Communications, of Menlo Park, Calif. The recognized speech could be applied directly to the natural language interpreter or it could be stored in a memory. The novel aspects of the invention do not depend upon the exact source of the recognized speech.

[0035] It will be apparent to one of ordinary skill in the art that the speech recognizer and the natural language interpreter could be constructed in two separate physically distinct systems. According to the preferred embodiment, these two operations are performed in a single general purpose computer running two program sequences, one for speech recognition and another for interpreting natural language. The two program sequences could be two separate programs that operate cooperatively. According to the preferred embodiment, these two programs comprise routines within a single computer program.

[0036] The natural language interpreter is configured to operate in conjunction with an application program. The application program is ancillary to the present invention. The application program will define what information it needs to carry out the desired functions. For the example of providing information about commercial passenger air flights utilized in this description, the application program requires the origin city, the destination city and the time of travel. It will be apparent that other applications could require other information. A specification will be used for identifying the required information to the natural language interpreter. Any convenient means can be used for conveying the specification to be communicated to the natural language interpreter. In the preferred embodiment, the specification takes the form of a grammar, which is an input to the natural language interpreter. Alternatively, the natural language interpreter can be modified to include the specification. Or the application program can include the specification wherein the application program and the natural language interpreter include an interface to allow the specification to be communicated to the natural language interpreter. Alternatively, the specification can be included as a discrete software element and include interfaces to both the natural language interpreter and the application program. The specification defines the edges to be filled as a function of the parsing operation of the natural language interpreter. The edges are used to fill the slots.

[0037] In the next step 106, the natural language interpreter performs the parsing operation to fill the edges, which in turn are use to form the slots. The natural language interpreter then determines which words are in each slot in the step 108. For each slot, the word confidence scores are combined for all the words in a slot to form a slot confidence score in the step 110. The actual method of combining the word confidence scores can vary according to the application. For example, the word confidence scores can be combined by merely forming a mathematical average of their respective values.

[0038] For other systems, certain words can be ascribed more importance so that weighted averaging can be used. In this way the system can be designed to distinguish between words that are merely used to fill a slot from words that are crucial for filling a slot. For example, in selecting a stock in a system used for purchasing stocks, a user might be interested in IBM. The user might utter “International Business Machines Incorporated.” All four words contribute to the filling the company name slot but only the first three are necessary words.

[0039] To implement this feature, various subsets of words are sent to the natural language interpreter. The natural language interpreter returns the slots that are filled and their value. According to the preferred embodiment, slots are filled with a slot value, eg., the airport code or stock ticker designation. It is possible that the slots could be filled with other information to designate the value such as the actual words. Then smaller subsets of words are systematically sent to the natural language interpreter. The smallest subset of words that can still generate the same slot values are identified as necessary words. As an example, the following subsets are sent to the natural language interpreter:

[0040] “international business machines incorporated”→IBM

[0041] “international business machines”→IBM

[0042] “international machines incorporated”→No parse

[0043] “business machines incorporated”→No parse

[0044] “international incorporated”→No parse

[0045] “international”→No parse

[0046] “business”→No parse

[0047] “machines”→No parse

[0048] “incorporated”→No parse

[0049] For still other systems, it may be practical to reduce each word that makes up the slot into its fundamental phones. A confidence score can be formed for each phone for each word in the slot and those phone confidence scores can be combined using any convenient technique for form the slot confidence value. It will be apparent to one of ordinary skill in the art that any convenient statistical method can be used to achieve the goals of the present invention.

[0050] Next, in the step 112 the slot confidence scores are examined to determined whether they exceed a threshold established by the specification. If each slot confidence score exceeds the threshold, the information in the slot is used by the application program as appropriate; for example a schedule of relevant flights is provided to the user in the step 114.

[0051] If the threshold is not exceeded for one or more slot, that slot fails to achieve an acceptable confidence level. The application program can not use the information in that slot. Unlike prior systems, the user need not provide the entire sentence or set of information. Rather, the user is automatically queried in the step 116 in an attempt to re-acquire the speech related to the failed slot. In the preferred embodiment, the application program includes the software to generate the query. However, it will be apparent that the natural language interpreter could include this function. The speech recognizer receives the new speech related only to the failed slot or slots in the step 118. Thereafter, in the step 120 the speech recognizer identifies the words and assigns word confidence score to the new words. The information is provided to the natural language interpreter which parses the words in the step 122. It may be possible to eliminate this step if only a single slot was filled. The words for each failed slot are identified in the step 124. A slot confidence score is formed for each of the failed slots in the step 126. Thereafter, the flow returns to the step 112.

[0052] Such a system can be used as follows. A user calls the system to learn about passenger air flights from Boston to Phoenix. The user says, “I want to fly on the third of May from Boston to Phoenix.” For some reason, the speech recognizer has difficulty understanding the word Phoenix and assigns a low word confidence score to that word. The score is so low that the slot confidence score for the destination city slot is below the acceptable threshold. The application program fills the two slots for which is has information, namely origin city and time, but does not know the destination city. The application program can be configured to generate speech and ask the user to repeat that information. For example, the application program can say, “It is understood that you wish to fly from Boston on May 3. To which city do you wish to travel?” The user might say “to Phoenix.” However, the application program expects only destination city information. Thus, it does not need a word to properly fill the slot. Indeed, the user might only say “Phoenix” in response to the application program query.

[0053] Similarly, the user might simply fail to supply information. For example, the user might call and say “I want to fly to Phoenix on May 3.” Here the natural language interpreter can fill two of the slots. The origin city slot is empty. The application might be programmed to say “In which city to you wish to begin your flight?”

[0054] The present invention has been described in terms of specific embodiments incorporating details to facilitate the understanding of the principles of construction and operation of the invention. Such reference herein to specific embodiments and details thereof is not intended to limit the scope of the claims appended hereto. It will be apparent to those skilled in the art that modifications can be made in the embodiments chosen for illustration without departing from the spirit and scope of the invention.

[0055] Specifically, it will be apparent to one of ordinary skill in the art that the device of the present invention could be implemented in several different ways and the apparatus disclosed above is only illustrative of the preferred embodiment of the invention and is in no way a limitation. It will be apparent that the various aspects of the above-described invention can be utilized singly or in combination with one or more of the other aspects of the invention described herein. In addition, the various elements of the present invention could be substituted with other elements.