Method and system for computing or determining confidence scores for parse trees at all levels

• US 8,639,509 B2
• Filed: 07/27/2007
• Issued: 01/28/2014
• Est. Priority Date: 07/27/2007
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Weng, Fuliang, Lin, Feng, Feng, Zhe
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): KOVACEK, DAVID M
• Application Number:
  US11/881,464
• Publication Number:
  US 20090030686A1
• Time in Patent Office: 2,377 Days
• Field of Search: 704231-232, 704235-240, 704243-245, 704251-254, 704E15001-E1505, 704E13011-E13014
• US Class Current: 704/252
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

In a confidence computing method and system, a processor may interpret speech signals as a text string or directly receive a text string as input, generate a syntactical parse tree representing the interpreted string and including a plurality of sub-trees which each represents a corresponding section of the interpreted text string, determine for each sub-tree whether the sub-tree is accurate, obtain replacement speech signals for each sub-tree determined to be inaccurate, and provide output based on corresponding text string sections of at least one sub-tree determined to be accurate.

Claims

1. A confidence computing method, comprising performing the following by a processor of a computer:

(a) generating a syntactical parse tree for an interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string;

(b) for each of at least one of the plurality of sub-trees;

extracting at least one feature of the respective sub-tree; and

determining whether the respective sub-tree is accurate, the accuracy determination including;

computing a respective confidence score characterizing a probability of the respective sub-tree'"'"'s accuracy, the confidence score being computed using a statistical model into which the at least one extracted feature is input; and

determining whether the respective confidence score meets a predetermined threshold value, wherein;

the respective sub-tree is determined to be accurate if it is determined that the respective sub-tree'"'"'s confidence score meets the threshold value; and

the respective sub-tree is otherwise determined to be inaccurate; and

(c) subsequent to a determination, for at least one of the sub-trees, that the at least one sub-tree is accurate, providing an output based on the at least one sub-tree'"'"'s at least one corresponding section of the interpreted text string;

wherein the at least one feature includes a history score which includes, for each of at least one child sub-tree of the respective sub-tree, the respective child sub-tree'"'"'s previously computed confidence score.

2. The method of claim 1, further comprising:

(d) interpreting first speech signals as the interpreted text string, wherein (d) is performed prior to (a); and

in (b), conditional upon a determination that the respective sub-tree is inaccurate, obtaining replacement speech signals for replacing the respective sub-tree and the respective sub-tree'"'"'s corresponding section.

3. The method of claim 2, further comprising:

performing (d) to (b) for the replacement speech signals.

4. The method of claim 1, wherein the statistical model includes a maximum entropy model.

5. The method of claim 4, further comprising:

assigning a Part-Of-Speech (POS) tag to each word in the interpreted text string, wherein the syntactical parse tree represents the assignment of the POS tags.

6. The method of claim 5, wherein, in addition to the history score, the at least one feature includes at least one of a set of features, including:

a parse-tree-word-level confidence score calculated based on respective word-level confidence scores of a plurality of words of the respective sub-tree;

a POS-tag confidence score based on respective POS-tag scores computed for the POS tag assignments of the plurality of words of the respective sub-tree;

a linking score representing a conditional probability of a link of a highest level of the respective sub-tree, the link including a dependency relation and a directionality;

each of a plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

each of the plurality of POS tags corresponding to the plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

each of a plurality of multi-level hierarchical POS tags corresponding to the plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

a dependency relation characteristic;

a single level joint head and dependency relation (SL-JHD) characteristic;

a single level joint mod and dependency relation (SL-JMD) characteristic;

a single level joint head, mod, and dependency relation (SL-JHMD) characteristic;

a joint dependency relation (JDR) characteristic;

a multi-level joint head and dependency relation (ML-JHD) characteristic;

a multi-level joint mod and dependency relation (ML-JMD) characteristic;

a multi-level joint head, mod, and dependency relation (ML-JHMD) characteristic;

a head, dependency, and left and right neighbors (HDLRN) characteristic;

a sub-tree size characteristic; and

a semantic slot feature.

7. The method of claim 6, wherein the at least one feature includes a combination of at least two of the set of features in addition to the at least one of the set.

8. The method of claim 6, wherein the at least one feature includes three dependency relation characteristics, including a first dependency relation of the highest level of the respective sub-tree and a second dependency relation and a third dependency relation of a next to highest level of the respective sub-tree.

9. The method of claim 6, wherein the at least one feature includes nine SL-JHD features, including three for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

10. The method of claim 6, wherein the at least one feature includes nine SL-JMD features, including three for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

11. The method of claim 6, wherein the at least one feature includes nine SL-JHMD features, including three for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

12. The method of claim 6, wherein the at least one feature includes three sets of JDR features including:

a first set that includes all dependency relations of all levels of the respective sub-tree;

a second set that includes all dependency relations of all levels of a left sub-tree, the left sub-tree corresponding to a level immediately below the highest level of the respective sub-tree; and

a third set that includes all dependency relations of all levels of a right sub-tree, the right sub-tree corresponding to the level immediately below the highest level of the respective sub-tree.

13. The method of claim 6, wherein the at least one feature includes three ML-JHD features, including one for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

14. The method of claim 6, wherein the at least one feature includes three ML-JMD features, including one for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

15. The method of claim 6, wherein the at least one feature includes three ML-JHMD features, including one for each of the highest level of the respective sub-tree and left and right child sub-trees corresponding to a level immediately below the highest level of the respective sub-tree.

16. The method of claim 6, wherein the at least one feature includes the sub-tree size characteristic, and the sub-tree size characteristic includes:

a first value equal to a number of pre-terminals of the respective sub-tree;

a second value equal to a number of non-terminals of a left child sub-tree corresponding to a level immediately below the highest level of the respective sub-tree; and

a third value equal to a number of non-terminals of a right child sub-tree corresponding to the level immediately below the highest level of the respective sub-tree.

17. The method of claim 6, wherein:

the POS-tag confidence score is calculated as a geometric mean of the respective POS-tag scores.

18. The method of claim 6, wherein:

the dependency relation characteristic includes a first dependency relation characterizing the top level of a respective sub-tree, a second dependency relation characterizing the top level of the respective sub-tree'"'"'s immediate left child, and a third dependency relation characterizing the top level of the respective sub-tree'"'"'s immediate right child.

19. The method of claim 5, wherein the at least one feature includes at least one of a set of features, including:

a parse-tree-word-level confidence score calculated based on respective word-level confidence scores of a plurality of words of the respective sub-tree and/or its surrounding sub-trees;

a POS-tag confidence score based on respective POS-tag scores computed for the POS tag assignments of the plurality of words of the respective sub-tree and/or its surrounding sub-trees;

a linking score representing a conditional probability of a link of a highest level of the respective sub-tree, the link including a dependency relation and a directionality;

a linking score representing a conditional probability of a link of a highest level of the surrounding sub-trees, the link including a dependency relation and a directionality;

a history score which includes, for each of at least one child sub-tree of the surrounding sub-trees, the surrounding child sub-trees'"'"' previously computed confidence score;

each of a plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

each of a plurality of words of the surrounding sub-trees'"'"' corresponding section of the interpreted text;

each of the plurality of POS tags corresponding to the plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

each of the plurality of POS tags corresponding to the plurality of words of the surrounding sub-trees'"'"' corresponding section of the interpreted text;

each of a plurality of multi-level hierarchical POS tags corresponding to the plurality of words of the respective sub-tree'"'"'s corresponding section of the interpreted text;

each of a plurality of multi-level hierarchical POS tags corresponding to the plurality of words of the surrounding sub-trees'"'"' corresponding section of the interpreted text;

a dependency relation characteristic;

a single level joint head and dependency relation (SL-JHD) characteristic;

a single level joint mod and dependency relation (SL-JMD) characteristic;

a single level joint head, mod, and dependency relation (SL-JHMD) characteristic;

a joint dependency relation (JDR) characteristic;

a multi-level joint head and dependency relation (ML-JHD) characteristic;

a multi-level joint mod and dependency relation (ML-JMD) characteristic;

a multi-level joint head, mod, and dependency relation (ML-JHMD) characteristic;

a head, dependency, and left and right neighbors (HDLRN) characteristic;

a sub-tree size characteristic; and

a semantic slot feature.

20. The method of claim 19, wherein the at least one feature includes a combination of at least two of the set of features in addition to the at least one of the set.

21. The method of claim 19, wherein the at least one feature includes three dependency relation characteristics, including a first dependency relation of the highest level of the surrounding sub-trees and a second dependency relation and a third dependency relation of a next to highest level of the surrounding sub-trees.

22. The method of claim 19, wherein the at least one feature includes nine SL-JHD features, including three for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

23. The method of claim 19, wherein the at least one feature includes nine SL-JMD features, including three for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

24. The method of claim 19, wherein the at least one feature includes nine SL-JHMD features, including three for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

25. The method of claim 19, wherein the at least one feature includes three sets of JDR features including:

a first set that includes all dependency relations of all levels of the surrounding sub-trees;

a second set that includes all dependency relations of all levels of a left sub-tree, the left sub-tree corresponding to a level immediately below the highest level of the surrounding sub-trees; and

a third set that includes all dependency relations of all levels of a right sub-tree, the right sub-tree corresponding to the level immediately below the highest level of the surrounding sub-trees.

26. The method of claim 19, wherein the at least one feature includes three ML-JHD features, including one for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

27. The method of claim 19, wherein the at least one feature includes three ML-JMD features, including one for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

28. The method of claim 19, wherein the at least one feature includes the sub-tree size characteristic, and the sub-tree size characteristic includes:

a first value equal to a number of pre-terminals of the surrounding sub-trees;

a second value equal to a number of non-terminals of a left child sub-tree corresponding to a level immediately below the highest level of the surrounding sub-trees; and

a third value equal to a number of non-terminals of a right child sub-tree corresponding to the level immediately below the highest level of the surrounding sub-trees.

32. The method of claim 19, wherein the at least one feature includes three ML-JHMD features, including one for each of the highest level of the surrounding sub-trees and left and right child sub-trees corresponding to a level immediately below the highest level of the surrounding sub-trees.

29. A non-transitory computer-readable medium having stored thereon instructions to be executed by a processor, the instructions which, when executed, cause the processor to determine a confidence by performing the following:

(a) generating a syntactical parse tree representing an interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string;

(b) for each of at least one of the plurality of sub-trees;

extracting at least one feature of the respective sub-tree; and

determining whether the respective sub-tree is accurate, the accuracy determination including;

computing a respective confidence score characterizing a probability of the respective sub-tree'"'"'s accuracy, the confidence score being computed using a statistical model into which the at least one extracted feature is input; and

determining whether the respective confidence score meets a predetermined threshold value, wherein;

the respective sub-tree is determined to be accurate if it is determined that the respective sub-tree'"'"'s confidence score meets the threshold value; and

the respective sub-tree is otherwise determined to be inaccurate; and

(c) subsequent to a determination, for at least one of the sub-trees, that the at least one sub-tree is accurate, providing an output based on the at least one sub-tree'"'"'s at least one corresponding section;

wherein the at least one feature includes a history score which includes, for each of at least one child sub-tree of the respective sub-tree, the respective child sub-tree'"'"'s previously computed confidence score.

30. A confidence computing system, comprising:

a processor configured to;

(a) interpret first speech signals as a text string;

(b) generate a syntactical parse tree representing the interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string;

(c) for each of at least one of the plurality of sub-trees;

extract at least one feature of the respective sub-tree;

determine whether the respective sub-tree is accurate, the accuracy determination including;

computation of a respective confidence score characterizing a probability of the respective sub-tree'"'"'s accuracy, the confidence score being computed using a statistical model into which the at least one extracted feature is input; and

determination of whether the respective confidence score meets a predetermined threshold value, wherein;

the respective sub-tree is determined to be accurate if it is determined that the respective sub-tree'"'"'s confidence score meets the threshold value; and

the respective sub-tree is otherwise determined to be inaccurate; and

conditional upon a determination that the respective sub-tree is inaccurate, obtain replacement speech signals for replacing the respective sub-tree and the respective sub-tree'"'"'s corresponding section; and

(d) subsequent to a determination, for at least one of the sub-trees, that the at least one sub-tree is accurate, provide an output based on the at least one sub-tree'"'"'s at least one corresponding section;

wherein the at least one feature includes a history score which includes, for each of at least one child sub-tree of the respective sub-tree, the respective child sub-tree'"'"'s previously computed confidence score.

31. A confidence computing method, comprising performing the following by a processor of a computer:

(a) generating a syntactical parse tree for the interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string;

(b) for each of at least one parent sub-tree of the plurality of sub-trees;

extracting at least one feature of the respective parent sub-tree; and

determining whether the respective parent sub-tree is accurate, the accuracy determination including;

computing a respective confidence score characterizing a probability of the respective parent sub-tree'"'"'s accuracy, the confidence score being computed using a statistical model into which the at least one extracted feature is input; and

determining whether the respective confidence score meets a predetermined threshold value, wherein;

the respective parent sub-tree is determined to be accurate if it is determined that the respective sub-tree'"'"'s confidence score meets the threshold value; and

the respective parent sub-tree is otherwise determined to be inaccurate; and

(c) subsequent to a determination, for at least one of the sub-trees, that the at least one sub-tree is accurate, providing an output based on the at least one sub-tree'"'"'s at least one corresponding section of the interpreted text string;

wherein the at least one feature includes a linking score representing a conditional probability of a link of a highest level of the respective parent sub-tree, the link including a dependency relation and a directionality.

33. The method of claim 31, wherein the conditional probability is a probability that a determined type and direction of the link is correct given right and left child sub-trees of the respective parent sub-tree.

34. A confidence computing method, comprising performing the following by a processor of a computer:

generating a syntactical parse tree for an interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string; and

for a parent sub-tree of the plurality of sub-trees, the parent sub-tree formed by a combination of a plurality of child sub-trees, determining whether the parent sub-tree is accurate, the accuracy determination including;

computing a parent confidence score characterizing a probability of the parent sub-tree'"'"'s accuracy, the computation of the parent confidence score including inputting into a statistical model a respective child confidence score previously calculated for each of the plurality of child sub-trees; and

determining whether the parent confidence score meets a predetermined threshold value, wherein the parent sub-tree is determined to be accurate if it is determined that the parent sub-tree'"'"'s confidence score meets the threshold value, and the parent sub-tree is otherwise determined to be inaccurate.

35. The method of claim 34, further comprising:

responsive to determining in the determining step that the parent sub-tree is accurate, providing an output based on the parent sub-tree'"'"'s corresponding section of the interpreted text string.

36. A confidence computing method, comprising performing the following by a processor of a computer:

generating a syntactical parse tree for an interpreted text string, the parse tree including a plurality of sub-trees, each of the sub-trees representing a corresponding section of the interpreted text string; and

for a parent sub-tree of the plurality of sub-trees, the parent sub-tree formed by a combination of a plurality of child sub-trees, determining whether the parent sub-tree is accurate, the accuracy determination including;

assigning to each of the child sub-trees a respective accuracy value;

computing a parent confidence score characterizing a probability of the parent sub-tree'"'"'s accuracy, the computation of the confidence score including inputting into a statistical model the accuracy values assigned to the child sub-trees; and

determining whether the parent confidence score meets a predetermined threshold value, wherein the parent sub-tree is determined to be accurate if it is determined that the parent sub-tree'"'"'s confidence score meets the threshold value, and the parent sub-tree is otherwise determined to be inaccurate.

37. The method of claim 36, wherein:

the accuracy determination further includes computing for each of the child sub-trees a respective child confidence score; and

for each of the child sub-trees, the assignment of the respective accuracy value is based on the child confidence score computed for the child sub-tree.