DE102008062923B4 - Method and device for generating a hit list in automatic speech recognition - Google Patents

Abstract

Method for generating a hit list in automatic speech recognition, wherein the hit list comprises at least one hit list word group which is generated by the speech recognition as possible hits based on a spoken word group,
where each group of words includes at least one word,
characterized by
that the hit list is generated from at least one source word group, which is determined by the speech recognition as a hit, using the Levenshtein method, wherein the hit list includes the at least one source word group.

Description

The present invention relates to a method and a device for generating a hit list in automatic speech recognition.

The DE 10 2004 055 230 B3 This describes a method for recognizing spoken input. A predefined vocabulary is divided into several sections containing phonetically similar words. In a first step, the spoken input is assigned to a section, and in a second step, the spoken input is identified from the vocabulary of that assigned section.

The DE 103 08 611 A1 This study deals with the risk of confusion between vocabulary entries. It uses the Levenshtein algorithm to determine the distance between two phoneme sequences.

The US 7,386,441 B2 describes natural language processing with operations that operate on weighted and unweighted multi-tape automata.

The DE 102 44 722 A1 The task is to compare two sequences of spoken language units. The Levenshtein method is used to determine the distance between two articulatory feature vectors.

The US 6,393,395 B1 This concerns the recognition of handwritten script and language.

The EP 17 39 655 A2 This concerns a method and a computer program product for generating a list of hypotheses from the vocabulary of a speech recognition system.

The DE 10 2007 028 235 A1 concerns a method and a data processing device for determining a list of hypotheses from a vocabulary of a speech recognition system.

Statistical speech recognition systems calculate an ordered list of possible recognized word groups from a user's spoken word group (e.g., a voice command). These word groups are defined in the system's vocabulary. This list is ordered according to a confidence level that compares the word groups represented in the vocabulary with the actual user input (the spoken word group). The similarity calculation incorporates not only symbolic factors (e.g., a corresponding sound symbol stored in the vocabulary) but also signal-related parameters (e.g., speaker characteristics). This often results in the best match being followed by alternatives ordered according to the perceived acoustic similarity. However, this order is not readily apparent to the average user.

Therefore, the object of the present invention is to create the hit list in an automatic speech recognition system in such a way that the order of the hit list is more intuitive for the user than is the case according to the prior art.

According to the invention, this problem is solved by a method for generating a hit list according to claim 1, by a device for generating a hit list according to claim 5, and by a vehicle according to claim 7. The dependent claims define preferred and advantageous embodiments of the present invention.

The present invention provides a method for generating a hit list in automatic speech recognition. The hit list comprises at least one hit list word group, i.e., it includes one or more hit list word groups. A word group is understood to be a sequence of one word or a sequence of several words. The hit list is generated by the speech recognition system based on a word group spoken, for example, by a user, as potential matches. The hit list is generated from at least one initial word group (i.e., one or more initial word groups), which is identified as a match by the speech recognition system. Based on or depending on this initial word group, the hit list is created using the Levenshtein method such that it includes the initial word group.

In other words, speech recognition generates several source word groups, from which the hit list is then generated using the Levenshtein algorithm. The source word groups can be sorted using the Levenshtein algorithm, as will be explained below, or further hits can be generated from the source word groups using the Levenshtein algorithm, and the resulting hit list can then be sorted using the Levenshtein algorithm.

The Levenshtein algorithm generates a hit list consisting of word groups or strings, structured based on the symbolic similarity of these groups. This ensures that the hits or word groups in the list share similar spelling or are ordered according to spelling, resulting in a speech recognition result that is more comprehensible to the user than is possible with current technology.

According to one embodiment of the invention, the hit list comprises several hit list word groups. The speech recognition system identifies the best match within the elements or word groups of the hit list and sorts the elements of the hit list according to the Levenshtein distance that each element of the hit list has from the best match, with the best match being the first element of the hit list. This sorting is performed with increasing Levenshtein distance, so that the hits following the best match in the hit list have a smaller Levenshtein distance than those hits that are further down or at the end of the hit list. Thus, according to this embodiment, the hit list is ordered or sorted according to increasing Levenshtein distance, and it begins with the best match or a Levenshtein distance of 0.

The hit list resulting from this embodiment is ordered according to decreasing symbolic similarity or decreasing similarity at the letter level, so that those hits which have a higher symbolic similarity to the best hit are higher in the hit list than those hits which have a lower symbolic similarity to the best hit.

According to a further embodiment of the invention, one or more additional word groups are added to the hit list, which have the smallest possible Levenshtein distance from the best hit. These one or more additional word groups can be contained within a predefined set of word groups, which also includes the best hit.

In other words, this embodiment adds further elements to the hit list without using speech recognition. Starting with the best match, which is determined via speech recognition, further word groups are identified that have the smallest possible Levenshtein distance from the best match. To avoid generating completely nonsensical word groups, the procedure can be restricted by predefining a specific set of word groups (for example, all place names within a particular region) from which the further word groups must be drawn.

Within the scope of the present invention, a device for generating a hit list in automatic speech recognition is also provided. The device comprises acquisition means (e.g., a microphone) for capturing a spoken word group, speech recognition means for performing speech recognition based on the spoken word group, and output means (e.g., a monitor) for outputting or displaying the hit list generated by the speech recognition. The speech recognition means generate the hit list by determining at least one hit list word group as a speech recognition hit, starting from the spoken word group. As an intermediate step, the speech recognition means determine at least one source word group by performing speech recognition based on the spoken word group. Using the Levenshtein method, the hit list, which includes this at least one source word group, is generated based on this at least one source word group.

The advantages of the device according to the invention essentially correspond to the advantages of the method according to the invention, which is why a repetition is omitted here.

Finally, within the scope of the present invention, a vehicle is provided which includes a device according to the invention.

The present invention is particularly suitable for generating voice commands or for specifying place names or addresses, for example in a navigation system. Of course, the present invention is not limited to this preferred area of application, but can also be used, for example, in general dictation systems.

The Levenshtein process and embodiments according to the invention are explained in detail below with reference to the accompanying figures.

In 1 It is shown how a hit list is generated previously and how it is generated with the present invention.

In 2 A vehicle according to the invention is schematically depicted with a device according to the invention for generating a hit list.

The Levenshtein distance, sometimes also called edit distance, edit interval, or edit range, is a measure in information theory of the difference between two strings (word groups) with respect to the minimum number of insert, delete, and replace operations required to transform one string into the other. The Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who introduced it in 1965.

1. 1. Tier
2. 2. Toer (Ersetze i durch o)
3. 3. Tor (Lösche e)

For example, to get from the string "Tier" to the string "Tor", a substitution and a deletion are necessary, so that the Levenshtein distance is therefore 2, as can be seen from the procedure shown below:

1. 1. Animal
2. 2. Toer (Replace i with o)
3. 3rd Gate (Delete e)

The following describes an algorithm to determine the Levenshtein distance between two strings or groups of words.

This algorithm calculates the Levenshtein distance using a matrix of the form (n + 1) × (m + 1), where n and m are the lengths of the strings to be compared. One string is written into the first row of the matrix and the other into the first column, each with a leading space (here called ε), as shown in Table 1 below.

The element D _0,0 , which lies in the 0th column and in the 0th row of the matrix, has by definition the value 0, i.e. D _0,0 = 0.

The following rule applies to all other elements of the matrix: $$D=\text{min}\left\{\begin{array}{l}{D}_{i-\mathrm{1,}i-1}+0\left(gleicherBuchstabe\right)\hfill \\ D_{i-\mathrm{1,}i-1}+1\left(Ersetzung\right)\hfill \\ D_{i,i-1}+1\left(E\text{ inf }\ddot{u}gung\right)\hfill \\ D_{i-\mathrm{1,}i}+1\left(L\ddot{o}schung\right)\hfill \end{array}\right\}$$

This results in the following Table 1: Table 1 ε T O r ε 0 1 2 3 T 1 0 1 2 i 2 1 1 2 e 3 2 2 2 r 4 3 3 2

In the table above, the actual matrix containing the elements D _{_i,j} is marked with a thick line. The matrix can be filled, for example, from the upper left corner (D _{_0,0}) to the lower right corner (D_{_4,3} ), starting with D _{_0,0} = 0, as defined above. The value of an element D_{_i,j} is calculated based on its left neighbor D_{_i,j-1} , its upper neighbor D_{_i-1,j,} and its upper left diagonal neighbor D _{_i-1,j-1} . With one exception, the element's value is determined by finding the minimum of the value of its left neighbor, its upper neighbor, and its upper left diagonal neighbor, and then increasing this minimum by 1. Only if the value of the upper left diagonal neighbor equals this minimum, and simultaneously the character corresponding to the element's position in the two strings is the same, does the element's value equal the value of its upper left diagonal neighbor.

 int Levenshtein-Distanz(char s[1..n], char t[1..m])
     declare int D[0..n, 0..m]
     declare int i, j, cost
     for i : = 0 to n
            D[i,0] := i
     for j :0 1 to n
            D[0,j] := j
     for i := 1 to n
            for j := 1 to m
                   if s[i] = t[j] then cost := 0
                                else cost := 1
                   D[i,j] := minimum( D[i-1,j] + 1, // Einfügen
                                       D[i, j-1]+ 1, // Löschen
                                       D[i-1,j-1] + cost // Ersetzen
                                       return d[n,m]

The following is pseudocode for an algorithm to determine the Levenshtein distance, where this algorithm is given a first string of length n by means of s and a second string of length m by means of t, and the algorithm returns the Levenshtein distance of these two strings:

 int Levenshtein distance(char s[1..n], char t[1..m])
     declare int D[0..n, 0..m]
     declare int i, j, cost
     for i := 0 to n
            D[i,0] := i
     for j :0 1 to n
            D[0,j] := j
     for i := 1 to n
            for j := 1 to m
                   if s[i] = t[j] then cost := 0
                                else cost := 1
                   D[i,j] := minimum( D[i-1,j] + 1, // Insertion
                                       D[i, j-1]+ 1, // Delete
                                       D[i-1,j-1] + cost // Replace
                                       return d[n,m]

In 1 Figure 1 illustrates how a method according to the invention works in comparison to a prior art method. A spoken input is provided to speech recognition software 5. Using feature extraction and a search, the speech recognition software 5 generates a hit list in which the individual elements are represented in spoken language. From this preliminary hit list, a hit list is then generated in which the individual elements of this hit list are represented in written language, i.e., the elements of this hit list are word groups or individual words in written form.

Reference numeral 6 designates the hit list in which the individual elements of the hit list are sorted according to the recognition criteria, as is the case according to the prior art. Reference numeral 7 designates a hit list generated according to the invention, wherein the individual elements of the hit list are sorted in descending order of Levenshtein distance to the best hit, which is at the top of the hit list. For better understanding, the Levenshtein distance is given in parentheses in hit list 7.

It can be seen that the phrase or rather the word “Beatles” has a greater symbolic similarity to the word “Eagles” than to the word “B-52s”, which is why the word “Eagles” is in second place in the hit list 7 according to the invention, whereas in the hit list 6 according to the prior art the word “B-52s” is in second place, which has the least symbolic similarity among the elements of the hit list to the best hit “Beatles”.

In 2 Figure 1 schematically depicts a vehicle 10 according to the invention, which includes a device 1 according to the invention for generating a hit list in automatic speech recognition. The device 1 according to the invention itself comprises a microprocessor 2, a microphone 3, and a display 4 for showing the hit list 7. A spoken phrase (e.g., a voice command or a place name) is recorded or captured by the microphone 3, for example, from the driver of the vehicle 10, and forwarded to the microprocessor 2, in which speech recognition software is installed. The microprocessor 2 analyzes the spoken word group and generates a hit list 7 according to the invention, which the microprocessor 2 then outputs via the display 4.

Reference symbol list

1

device

2

microprocessor

3

microphone

4

Advertisement

5

Speech recognition

6

Hit list sorted by recognition criteria

7

Results sorted by Levenshtein distance

10

vehicle

Claims (7)

Method for generating a hit list in automatic speech recognition, wherein the hit list comprises at least one hit list word group, which is generated by the speech recognition as possible hits starting from a spoken word group, wherein each word group comprises at least one word, characterized in that the hit list is generated by the Levenshtein method starting from at least one initial word group, which is determined by the speech recognition as a hit, wherein the hit list comprises the at least one initial word group. Procedure according to Claim 1 , characterized in that the hit list comprises several hit list word groups, that the best hit is determined in the hit list by the speech recognition, and that the hit list word groups are sorted according to the Levenshtein distance, which the hit list word groups each have from the best hit, with increasing Levenshtein distance. Procedure according to Claim 1 or 2 , characterized in that the best match is determined in the hit list by the speech recognition, and that at least one further word group is added to the hit list by determining, starting from the best match, at least one further word group which has the smallest possible Levenshtein distance. Procedure according to Claim 3 characterized in that at least one further word group is contained in a predetermined set of word groups, which also includes the best match. Device for generating a hit list in automatic speech recognition, wherein the device comprises acquisition means for acquiring a spoken word group, speech recognition means for performing speech recognition, and output means for outputting the hit list, wherein the speech recognition means generate the hit list by determining at least one hit list word group as a hit of the speech recognition, starting from the spoken word group, wherein each word group comprises at least one word, characterized in that the speech recognition means generate the hit list starting from at least one initial word group, which the speech recognition means determine as a hit during the performance of the speech recognition, using the Levenshtein method, wherein the hit list comprises the at least one initial word group. Device according to Claim 5 , characterized in that the device for carrying out the method according to one of the Claims 1 - 4 is designed. Vehicle with a device according to Claim 5 or 6 .