Method for probabilistic error-tolerant natural language understanding

• US 20020042711A1
• Filed: 02/22/2001
• Published: 04/11/2002
• Est. Priority Date: 08/11/2000
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Lin, Yi-Chung
• Granted Patent: US 6,920,420 B2
• Time in Patent Office: Days
• US Class Current: 704/257
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding

Abstract

A method of probabilistic error-tolerant natural language understanding. The process of language understanding is divided into a concept parse and a concept sequence comparison steps. The concept parse uses a parse driven by a concept grammar to construct a concept parse forest set by parsing results of speech recognition. The concept sequence comparison uses an error-tolerant interpreter to compare the hypothetical concept sequences included by the concept parse forest set and the exemplary concept sequences included in the database of the system. A most possible concept sequence is found and converted into a semantic framed that expresses the intention of the user. The whole process is led by a probability oriented scoring function. When error occurs in the speech recognition and a correct concept sequence cannot be formed, the position of the error is determined and the error is recovered according to the scoring function to reduce the negative effect.

Claims

1. A method of probabilistic error-tolerant natural language understanding, comprising:

using a speech recognition to convert an utterance of a user into a possible word sequence set;

dividing a concept grammar into a static grammar and a dynamic grammar, wherein the static grammar is predetermined and is not variable according to the input word sequence set, while the dynamic grammar is formed by comparing the input word sequence set and the static grammar;

using the concept grammar to parse the word sequence set into a concept parse forest, wherein the concept parse forest further comprises at least one hypothetical concept sequence;

using at least one exemplary concept sequence to represent the concept sequence which is well-formed being recognized by the concept grammar; and

comparing the hypothetical concept sequences and the exemplary concept sequences to find the most possible concept sequence, and to convert the concept sequence into a semantic frame expressing intention of the user.

2. The method according to claim 1, wherein:

the process for understanding the utterance of the user using the method of probabilistic error-tolerant natural language understanding is presented by a probability formula as;

$\left(\hat{W},\hat{F},\hat{C},\hat{K},\hat{E}\right)=\underset{\left(W,F,C,K,E\right)}{\mathrm{argmax}}<br><br>P\left(W,F,C,K,E<br><br>U\right)$

U representing an articulation characteristic of the utterance of the user;

W being one possible word sequence in the word sequence set output by the speech recognition module;

F being one possible concept parse forest defined by a system grammar;

C being a hypothetical concept sequence corresponding to the concept parse forest;

K being the exemplary concept sequence;

E being one edit operation sequence to change the exemplary concept sequence to the hypothetical concept sequence; and

(W,F,C,K,E) being a most possible assemble of the word sequence, the concept parse forest, the hypothetical concept sequence, the exemplary concept sequence and the edit operation sequence; and

the process for understanding the utterance of the user using the method of probabilistic error-tolerant natural language understanding is probability oriented to use a scoring function to replace the probability formula as;

$\left(\hat{W},\hat{F},\hat{C},\hat{K},\hat{E}\right)=\underset{\left(W,F,C,K,E\right)}{\mathrm{argmax}}<br><br>\left\{S_W+S_F+S_K+S_E\right\}$

S_W being a speech score;

S_F being a grammar score;

S_K being an example score; and

S_E being an edit operation score;

weights larger than zero are given to different probability parameters to find the most possible word sequence, the concept parse forest, the hypothetical concept sequence, the exemplary concept sequence and the edit operation according to;

S(W,F,C,K,E)=w₁×

S_W+w₂×

S_F+w₃×

S_K+w₄×

S_E w₁ being a weight of speech score;

w₂ being a weight of grammar score;

w₃ being a weight of example score; and

w₄ being a weight of edit operation score.

3. The method according to claim 1, wherein the word sequence set is represented by either a sentence list or a word graph.

4. The method according to claim 1, wherein a correctness of a concept sequence example database is constructed by the exemplary concept sequence can be parsed and confirmed by human intellectual, and the well-formed concept sequence defined by human can also be added to make up insufficiency of a text corpus.

5. The method according to claim 1, wherein the first term of the probability term P(W,F,C,K,E|U) can further deduced as:

6. The method according to claim 5, wherein the speech recognition uses a statistical model to estimate the second probability P(U|W) in the first probability term P(W,F,C,K,E|U).

7. The method according to claim 5, wherein the third probability term P(W,F,C,K,E) in the first probability term P(W,F,C,K,E|U) is simplified as:

8. The method according to claim 7, wherein the fifth probability term P(W,F|C) and the sixth probability term P(F|C) are equal to each other since one terminal node sequence of the concept parse forest is the word sequence.

9. The method according to claim 8, wherein when the word sequence set is parsed by using a SCFG probability model, the sixth probability term P(F|C) is estimated by:

10. The method according to claim 7, wherein the seventh probability term P(C, E|K) and the eighth probability term P(E|K) of the third probability term P(W,F,C,K,E) are equal to each other due to information of the concept sequence included by the edit operation sequence.

11. The method according to claim 7, wherein the ninth probability term P(K) of the first probability term P(W,F,C,K,E|U) is estimated by N-gram probability model as:

12. The method according to claim 10, wherein the eighth probability term P(E|K) can be simplified as:

13. The method according to claim 1, wherein the scoring function including the following scores to be estimated as:

S_W=log P(U|W) for the speech score;

$S_F=\underset{T\in <br><br>F,A\to <br><br>\mathrm{\alpha <br><br>}\in <br><br>T}{\sum <br><br>}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(\mathrm{\alpha <br><br>}<br><br>A\right)$

for the grammar score;

$S_K=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>\log <br><br>\text{\hspace{1em}<br><br>}<br><br>p<br><br>\left(k_i|k_{i-N+1}^{i-1}\right)$

for the example score; and

$S_E=\underset{i=1}{\overset{n}{\sum <br><br>}}<br><br>P<br><br>\left(e_i|k_{L<br><br>\left(e_i\right)-X+1}^{L<br><br>\left(e_1\right)},k_{R<br><br>\left(e_i\right)}^{R<br><br>\left(e_i\right)+Y-1}\right)$

for the edit score.

14. The method according to claim 13, wherein when training data is insufficient, the example score is defined as