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

• US 20090030686A1
• Filed: 07/27/2007
• Published: 01/29/2009
• Est. Priority Date: 07/27/2007
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Lin, Feng, Weng, Fuliang, Feng, Zhe
• Granted Patent: US 8,639,509 B2
• Time in Patent Office: Days
• US Class Current: 704/240
• 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:

(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 sub-tree, determining whether the respective sub-tree is accurate; 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.

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:

in (b), for the accuracy determination;

computing a respective confidence score characterizing a probability of the respective sub-tree'"'"'s accuracy; 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.

4. The method of claim 3, further comprising:

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

5. The method of claim 3, further comprising:

for each sub-tree, extracting at least one feature of the respective sub-tree, wherein the confidence score of the respective sub-tree is computed using a statistical model into which the at least one extracted feature is input.

6. The method of claim 5, wherein the statistical model includes a maximum entropy model.

7. The method of claim 6, 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.

8. The method of claim 7, 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;

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;

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;

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.

9. The method of claim 8, 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.

10. The method of claim 8, 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.

11. The method of claim 8, 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.

12. The method of claim 8, 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.

13. The method of claim 8, 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.

14. The method of claim 8, 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.

15. The method of claim 8, 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.

16. The method of claim 8, 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.

17. The method of claim 8, 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.

18. The method of claim 8, 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.

21. The method of claim 7, 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 respective sub-tree, the respective child sub-tree'"'"'s previously computed confidence score;

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.

22. The method of claim 21, 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.

23. The method of claim 21, 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.

24. The method of claim 21, 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.

25. The method of claim 21, 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.

26. The method of claim 21, 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.

27. The method of claim 21, 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.

28. The method of claim 21, 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.

29. The method of claim 21, 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.

30. The method of claim 21, 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.

31. The method of claim 21, 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.

19. A 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 sub-tree, determining whether the respective sub-tree is accurate; 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.

20. 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 sub-tree;

determine whether the respective sub-tree is accurate; 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.