Method and Apparatus for Reducing False Rejection in a Speech Recognition System

This invention relates to a method and an apparatus for automatically performing desired actions in response to spoken requests. It is applicable to speech recognition systems, more particularly methods and apparatuses for automatically providing desired information in response to spoken requests, as may be used to automate telephone directory assistance functions partially or fully.

Besides providing printed telephone directories, telephone companies provide telephone directory assistance services. Users of these services call predetermined telephone numbers and are connected to directory assistance operators. The operators access directory databases to locate the directory listings requested by the users, and release the telephone numbers of those listings to the users.

Because telephone companies handle a very large number of directory assistance calls per year, the associated labor costs are very significant. Consequently, telephone companies and telephone equipment manufacturers have devoted considerable effort to the development of systems that reduce the labor costs associated with providing directory assistance services.

In a typical directory assistance system the caller is first prompted to provide listing information, in other words to specify in what area resides the business or individual whose telephone number he seeks. If valid speech is detected, the speech recognition layer is invoked in an attempt to recognize the unknown utterance. On a first pass search, a fast match algorithm is used to select the top N orthography groups. In a second pass the individual orthographies from the selected groups are re-scored using a more precise likelihoods. The top orthography in each of the top two groups are then processed by a rejection algorithm that evaluates if they are sufficiently distinctive from one another so the top choice candidate can be considered a valid recognition. Usually, three parameters are used by the rejection algorithm: the likelihood per frame of the top choice candidate, the duration likelihood of the phonemes in this top choice, and the likelihood ratio of the two candidates. The last measure requires that the two orthographies the phonetically far apart. If these orthographies are phonetically close they will be rejected frequently.

Consider the following example. The first pass search using the fast match algorithm selects two candidate groups, namely group A and Group B. The following table shows the individual orthographies in the groups.

The individual entries in each of the selected groups are re-scored in a second-pass search. The order of the entries in groups A and B is now as follows.

The orthographies <<Laval>> and <<Lassalle>> are the top choices in the respective groups. For the purpose of this example let us assume that <<Laval>> has a higher score than <<Lassalle>>. The two orthographies are now processed by the rejection algorithm that will determine, among other things, how far phonetically these top choice candidates are. In this example the orthographies are phonetically very similar to one another. The output of the rejection algorithm processing suggests that a correct resolution between the orthographies is unlikely. In other words, there is a real possibility that an incorrect choice will be made.

As seen in the above example, the rejection process can often refuse acceptance of words that have been correctly identified by the speech recognition layer, solely on the basis of the existence of confusable words in the dictionary. This may lead to a problem where some entries will always be rejected. For example, every time a caller requests "Laval" the rejection process will not authorize the acceptance simply because "Lassalle" exists in the dictionary and the rejection ratio will always be too low. Thus, some entries will always be the subject of a self-collision problem so that they will be automated less frequently.

Thus, there exists a need in the industry to refine the rejection process to avoid phonetically similar entries to be consistently rejected although the speech recognition layer has effected the correct choice.

An object of the present invention is to provide a speech recognition dictionary configured to reduce the likelihood of false rejection.

Another object of the invention is to provide a speech recognition system where the likelihood of false rejection is reduced.

Another object the present invention is to provide a method for grouping entries in a speech recognition dictionary to reduce the likelihood of false rejection.

A further object of the invention is a computer readable medium containing a program element that instructs a computer to process a speech recognition dictionary to re-arrange the entries therein in order to reduce the likelihood of false rejection.

The present inventors have made the unexpected discovery that false rejection in a speech recognition system can be significantly reduced by grouping confusable orthographies in the same group of the speech recognition dictionary. During the speech recognition process those groups are examined by the fast match algorithm to generate the top choices. The entries(either all entries or some of them) in the top choice groups are then re-scored using more precise likelihoods. Then the top entries in the two top groups are extracted and processed by the rejection algorithm. Since the confusable orthographies are now grouped together, the likelihood of two confusable orthographies self colliding against one another is significantly reduced.

As embodied and broadly described herein, the invention provides a computer readable medium containing a speech recognition dictionary for use in a speech recognition system that includes a speech recognition layer and a rejection layer, said speech recognition dictionary including a plurality of orthography groups, each orthography group including a plurality of individual orthographies, at least one of said groups including a pair of confusable orthographies where in the event said pair of confusable orthographies are processed by the rejection layer a high probability exists that the rejection layer will reject a selected one of said pair of confusable orthographies by the speech recognition layer. This probability may be of say 0.8. This value is not critical, however as a higher or lower probability of rejection may exist without departing from the spirit of the invention.

In a preferred embodiment, confusable orthographies in the speech recognition dictionary are found by examining the results after running recognition on a large training set containing say 50,000 orthographies. For each orthography data is collected indicative of the entity with whom this orthography was confused or likely to be confused. The collected data also indicates the number of times each orthography was correctly recognized and the number of errors. Based on this information the entries in the speech recognition dictionary are re-grouped to associate the orthographies considered confusable.

As embodied and broadly described herein the invention further provides a computer readable medium containing a speech recognition dictionary for locality recognition for use in an automated directory assistance system that includes a speech recognition layer and a rejection layer, said speech recognition dictionary including a plurality of orthography groups, each orthography group including a plurality of individual orthographies, at least one of said groups including a pair of confusable orthographies where in the event said pair of confusable orthographies are processed by the rejection layer a high probability exists that the rejection layer will reject a selected one of said pair of confusable orthographies by the speech recognition layer, every orthography in at least one group of said speech recognition dictionary other than said one group being indicative of a substantially identical geographical area.

As embodied and broadly described herein the invention further provides a speech recognition system, comprising:

a speech recognition layer

a rejection layer;

a speech recognition dictionary including a plurality of orthography groups, each orthography group including a plurality of individual orthographies potentially recognizable by said speech recognition layer on a basis of a spoken utterance by a user of said speech recognition system, at least one of said groups including a pair of confusable orthographies where in the event said pair of confusable orthographies are processed by said rejection layer a high probability exists that said rejection layer will reject a selected one of said pair of confusable orthographies by the speech recognition layer.

As embodied and broadly described herein, the invention also provides a process for reducing a likelihood of false rejection in a speech recognition system that includes:

a speech recognition layer

a rejection layer;

a speech recognition dictionary including a plurality of individual orthographies potentially recognizable by said speech recognition layer on a basis of a spoken utterance by a user of the speech recognition system;

said process comprising the step of:

identifying at least one pair of orthographies in the speech recognition dictionary that are confusable beyond a certain threshold; and

associating said pair of orthographies to provide means for substantially reducing a likelihood of the rejection layer processing together the orthographies of said pair.

As embodied and broadly described herein, the invention also provides an apparatus for re-arranging a speech recognition dictionary for use in a speech recognition system that includes a speech recognition layer and a rejection layer, the speech recognition dictionary including a plurality of orthographies potentially recognizable by the speech recognition layer on a basis of a spoken utterance by a user of the speech recognition system, said apparatus comprising:

first memory means for holding orthographies of the speech recognition dictionary;

a processor in operative relationship with said first memory means;

a program element providing means for:

identifying at least one pair of orthographies in the speech recognition dictionary that are confusable beyond a certain threshold; and

associating said pair of orthographies to provide means for substantially reducing a likelihood of the rejection layer processing together the orthographies of said pair.

As embodied and broadly described herein, the invention further provides a machine readable medium containing a program element for instructing a computer for generating a speech recognition dictionary for use in a speech recognition system that includes a speech recognition layer and a rejection layer, the speech recognition dictionary including a plurality of orthographies, said computer including:

first memory means for holding orthographies of the speech recognition dictionary;

a processor in operative relationship with said first memory means;

said program element providing means for:

identifying at least one pair of orthographies in the speech recognition dictionary that are confusable, where in the event said pair of orthographies are processed by said rejection layer a high probability exists that said rejection layer will reject a selected one of said pair of confusable orthographies by the speech recognition layer;

placing said pair of orthographies in a group of said speech recognition dictionary to provide means for substantially reducing a likelihood of the rejection layer processing together the orthographies of said pair.

FIG. 1 is a block diagram illustrating the structure of a prior art speech recognition dictionary;

FIG. 2 is a block diagram of the selected orthography groups of a speech recognition dictionary after a first pass search by the speech recognition layer; and

FIG. 3 is a flow chart of the rejection process;

FIG. 4 is a block diagram illustrating the association of confusable orthographies;

FIG. 5 is a block diagram illustrating a group of the speech recognition dictionary arranged in accordance with the inventive process with a view to reduce false rejection;

FIG. 6 is a block diagram of the speech recognition dictionary re-arranged to group confusable orthographies together;

FIG. 7 is flow chart of the selection of confusable orthographies in the speech recognition dictionary; and

FIG. 8 is a functional block diagram of an apparatus for generating the re-arranged speech recognition dictionary allowing to reduce false rejection.

As an introductory comment it should be pointed out that the invention does not directly relate to the structure and operation of an automated directory assistance system, nor to the process for building the speech recognition dictionary from raw data, such as the white pages supplied by the telephone company. Rather, the invention is concerned with a method and apparatus for reorganizing a speech recognition dictionary that can be used in an automated directory assistance system to reduce false rejection. For more information on the structure and detailed operation of an automated directory assistance system the reader may refer to the following documents whose contents are hereby incorporated by reference.

FIG. 1 illustrates the structure of a speech recognition dictionary constructed in accordance with prior art techniques. The dictionary is composed of a plurality of M groups, each group containing entries (orthographies) 22 that lead to the same action. In a specific example, a speech recognition dictionary relating to a localities listing will contain groups in which the orthographies corresponding to a given locality are associated together. For example the orthography "Laval" and "Ville de Laval" will be placed in a first group while the orthography "Lassalle" and "Ville de Lassalle" will be associated in a second group. The orthographies in each group relate to the same distinct geographic region. In general <<same action>> means that the orthographies in a given group are functional synonyms, in other words the action resulting from the selection of one orthography in a group is generally similar to what would result it another orthography in that same group would be selected. This definition, however, is applicable only to the preferred embodiment described herein, as other forms of groupings in the speech recognition dictionary are possible without departing from the spirit of the invention.

During the speech recognition process a first pass search is effected by using a fast match algorithm that scans all the orthographies in the speech recognition dictionary and selects the top N groups that contain the orthographies considered the most likely candidates. FIG. 2 graphically illustrates the selected N groups, here N being 3. The groups are ordered in terms of score, in other words the likelihood of containing the correct choice. In the example shown the entries of group 1 are considered the most likely candidates, followed by the entries in group two and finally the orthographies in group 3.

During the next phase of the speech recognition process, the orthographies in each group are re-scored by using more precise likelihoods. In this manner, the orthographies are re-arranged in the individual groups, with the top orthography in each group being the most likely candidate for that group. In a specific example all the orthographies in the group may be re-scored. In a possible variant only a sub-group of orthographies may be re-scored.

The rejection process consists of extracting from the two top groups, namely groups 1 and 2 the top choice orthographies 24 and 26. The top choice orthography 24 is the one that possesses the highest score. Thus, it is the entry that is most likely to correspond to the spoken utterance. However, before it is accepted by the system as a valid token, it is compared with the second rank orthography 26 to determine if they are sufficiently distinct from one another. Indeed, if the top choice orthography 24 is very close to the second rank orthography 26 the system will assume that a correct resolution between these two entries cannot be made with a high probability of success.

In general, three parameters can be used to establish whether the two orthographies are of confusable nature. The three parameters are: the likelihood per frame of the top choice candidate, the duration likelihood of the phonemes in this top choice, and the likelihoods ratio of the two top choices. The last measure requires the top two choices to be phonetically far apart. FIG. 3 illustrates the flowchart for assessing the rejection ratio. At step 28 the rejection value .theta. is computed for the pair of orthographies. If at step 30 .theta. is found to exceed a certain threshold, the system assumes that the top choice orthographies are sufficiently apart so a correct resolution can be made with a high probability of success. Below the threshold, however, the operation is terminated and the system defaults to the human operator. The rejection algorithm is not described in detail because it does not form part of the invention. For more information, the reader is invited to refer to U.S. Pat. No. 5,097,509 whose contents are incorporated herein by reference.

To avoid the false rejection problem described earlier, the speech recognition dictionary can be re-organized to group together confusable orthographies. In this manner, the rejection process will process only substantially non-confusable entries, thus avoiding the self-collision problem.

FIG. 4 illustrates an orthography 32 of the speech recognition dictionary. This orthography is associated with another orthography 34 considered confusable with it. The confusable orthographies are grouped together in the speech recognition dictionary as shown in FIG. 5. This drawing illustrates the structure of the group of the re-arranged speech recognition dictionary containing the confusable orthographies. Assuming that the original group contained two orthographies (orthography #1 and orthography #2), the new group will contain four entries due to the association of each original orthography with one confusable orthography. It should be appreciated that the original orthography grouping was done based on action parallelism, i.e., the group contained orthographies leading to the same activity. The re-arranged group has no longer this characteristic as entries have been introduced that no longer lead to the same action. Another observation is the fact that by associating one orthography with a confusable companion may very well introduce in the group other orthographies as well. This is because the confusable companion may itself possess its own confusable companion that will be drawn in the group. This chaining may actually insert in the group a significant number of orthographies. FIG. 6 illustrates this point. The orthography 100 located in the second group is found to be confusable with the orthography 102 of the first group. As a result, the orthography 100 is moved to the second group. This action is shown by the arrow 104. However, the orthography 100 also possesses a companion confusable orthography 108 and that orthography is also moved to the top group. This action is shown by the arrow 110.

Another possibility is simply to create a new group in the speech recognition dictionary that contains the confusable orthographies, rather than placing the confusable entries in an existing group.

During the second pass search of the speech recognition process, the entries in the group are re-scored, each orthography being treated as an independent entity. The top choice is then extracted to be processed by the rejection layer along with the top choice from another group. In this example, however, since a single orthography is taken from each group, the self-collision problem between two confusable entries is substantially reduced.

To establish in a given speech recognition dictionary what are the mutually confusable entries, the following data is collected from screened tokens during the commissioning phase of the system (data elements collected for each screened token):

1) confusable orthography;

2) number of times recognized correctly with .theta.<.theta..sub.i

3) number of errors

The value .theta. is the output of the rejection alorithm for the two choices, while .theta..sub.i is a certain threshold that establishes a boundary above which the screened token will simply be ignored. This feature is used to reduce the number of tokens to be processed in the course of searching for confusable orthographies. Only those tokens that are below a given threshold will be inspected by the system while those above the threshold are passed by. The particular threshold value can vary in accordance with the intended application and it is not a critical element of the invention.

To illustrate this algorithm, the following examples can be considered:

a) spoken utterance: Saint-Eustache

b) top choice generated by system: Sainte-Marthe

c) second choice generated by system: Sainte-Barbe

d) is the rejection value for the two choices

In this example the potentially confusable orthography is Sainte-Marthe. Since this is a misrecognition the error count associated with the orthographies Saint-Eustache and Sainte-Marthe is increased by one. In the situation the spoken utterance is correctly recognized, the second choice generated by the system becomes the potentially confusable orthography and the count for correct recognition with .theta.<.theta..sub.i is incremented. Additional examples are illustrated in the following tables.

The results show that after three recognition attempts for the orthography <<Saint-Eustache>> two potentially confusable orthographies exist, namely <<Sainte-Barbe>> and <<Sainte-Marthe>>. More specifically, at the first row <<Saint-Eustache>> and <<Sainte-Marthe>> are the potentially confusable pair, with the error count associated with that pair being incremented by one. At row two, the potentially confusable pair is <<Saint-Eustache>> and <<Sainte-Barbe>>, the correct count for that pair being incremented by one. At the third row, <<Saint-Eustache>> and <<Sainte-Barbe>> are the potentially confusable entries, with the error count for the pair being incremented by one. At the fourth row, <<Laval>> and <<Lassalle>> are the potentially confusable entries, with the correct count being incremented by one. At the fifth row, <<Laval>> and <<Lassalle>> are the potentially confusable pair, with the error count for the pair increased by one. Finally, at the sixth row, <<Laval>> and <<Laville>> are considered as potentially confusable entries with the error count increased by one. The results from these six tokens can be summarized in the following table:

Another possibility of determining the potentially confusable orthographies in the dictionary is to look only at the top choice and at the second choice. Every time the recognition is correct with .theta.<.theta..sub.i the correct count is incremented by one. Every time the top choice is incorrect with .theta.<.theta..sub.i the error count for the word pair is incremented. For example, in the first row of the above table, <<Sainte-Marthe>> is potentially confusable with <<Sainte-Barbe>> and the error count is incremented by one since it is a misrecognition. For the second row, <<Sainte-Eustache>> and <<Sainte-Barbe>> are the potentially confusable words, the correct count being incremented by one. In the third row, <<Sainte-Barbe>> and <<Sainte-Marthe>> are the potentially confusable pair, with the error count for that pair being incremented by one. At the fourth row, the potentially confusable entries are <<Laval>> and <<Lassalle>>, with the correct count being incremented by one. At the fifth row, <<Lassalle>> and <<Laville>> are potentially confusable with the error count being incremented by one. Finally, at the sixth row, <<Laville>> and <<Lassalle>> are the potentially confusable orthographies with the error count being incremented by one.

The expression <<potentially confusable>> orthography refers to an entry in the speech recognition dictionary that may be confused with a given orthography. Actually, for each orthography in the speech recognition dictionary there may exist a number of potentially confusable entries that can be identified by either one of the above methods. In practice, not all of those potentially confusable entries need to be grouped together in the dictionary to achieve a significant reduction in false rejection. In practice only a few of the potentially confusable entries will be associated together and those entries are referred to as <<confusable>> orthographies, rather than <<potentially confusable>> orthographies. Thus, in the vast majority of cases, the confusable orthographies are a sub-class of the potentially confusable entries.

Several methods exist for extracting the sub-class of confusable orthographies from the class of potentially confusable entries. One method is by observing the correct recognition count and error count and comparing it to a threshold. For example, if a potentially confusable pair, say <<Saint-Eustache>> and <<Sainte-Marthe>> has a correct count greater than 10, an error count greater than 1 and a total count (correct count+error count) greater than 25, then these two entries acquire the <<confusable>> status. Another possible method is to say that two words are confusable when the ratio of correct count/error count is greater a 0.5 and the total count greater than 10. It should be appreciated that all those thresholds can vary without departing from the spirit of the invention.

Once the confusable orthography pairs have been generated they must be implanted in the speech recognition dictionary. Two different methods exist for accomplishing this. In one method for each orthography in a given group only a single orthography is entered in that group. Thus, if the group has A orthographies after the re-arranging process is completed it will possess at maximum 2A orthographies. In a different approach larger groups are formed by entering in a group a chain of confusable orthographies as discussed earlier in connection with FIG. 6. This possibility has the advantage of further reducing false rejection as larger number of confusable entries are held in the same group.

The process for generating the re-arranged speech recognition dictionary is shown at FIGS. 7 and 8. After the step that consists of identifying the potentially confusable orthographies, the confusable ones are determined by comparing each potentially confusable pair to a threshold value. Once the confusable orthographies have been identified, they are displaced and grouped together according to either one of the two possibilities described earlier. The entire operation is effected by using the computer illustrated at FIG. 8. The computer includes a processor 36 in operative relationship with a memory having three segments, namely a first segment 38 containing program instructions, a second segment 40 containing the speech recognition dictionary, and a third segment 42 containing the re-arranged speech recognition dictionary. Under the instructions from the program in the first memory segment 38, the processor 36 identifies the confusable orthography pairs and re-arranges them. The resulting entries are then placed in the third memory segment 42. The rearranged speech recognition dictionary may then be recorded on mass storage 44, if wanted.

The above description of a preferred embodiment should not be interpreted in any limiting manner since variations and refinements can be made without departing from the spirit of the invention. The scope of the invention is defined in the appended claims and their equivalents.