Method and apparatus for generating decision tree questions for speech processing

• US 20040044528A1
• Filed: 09/03/2002
• Published: 03/04/2004
• Est. Priority Date: 09/03/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chelba, Ciprian I., Morton, Rachel I.
• Granted Patent: US 7,788,096 B2
• Time in Patent Office: Days
• US Class Current: 704/249
• CPC Class Codes: G10L 15/083 Recognition networks G10L15/142, G10L15/16 take precedence
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

The present invention automatically builds question sets for a decision tree. Under the invention, mutual information is used to cluster tokens, representing either phones or letters. Each cluster is formed so as to limit the loss in mutual information in a set of training data caused by the formation of the cluster. The resulting sets of clusters represent questions that can be used at the nodes of the decision tree.

Claims

1. A method of forming a decision tree used in speech processing, the method comprising:

grouping at least two tokens to form a first possible cluster;

determining a mutual information score based on the first possible cluster;

grouping at least two tokens to form a second possible cluster;

determining a mutual information score based on the second possible cluster;

selecting one of the first cluster and the second cluster based on the mutual information scores associated with the first cluster and the second cluster; and

using the selected cluster to form a question in the decision tree.

2. The method of claim 1 wherein each token is a linguistic phone.

3. The method of claim 2 wherein the decision tree defines clusters of context-dependent phones.

4. The method of claim 3 wherein the context-dependent phones are triphones.

5. The method of claim 1 wherein each token is a letter in an alphabet.

6. The method of claim 1 wherein selecting one of the first cluster and the second cluster comprises selecting the cluster that provides a higher mutual information score.

7. The method of claim 1 wherein determining a mutual information score based on the first possible cluster comprises:

placing a cluster token representing the first possible cluster in place of each of the at least two tokens in a set of training data to form a modified set of training data; and

determining the mutual information score of the modified set of training data.

8. A computer-readable medium having computer-executable instructions for performing steps comprising:

using mutual information to form clusters of tokens found in training data;

building a decision tree by utilizing at least one of the clusters of tokens to form a question for a node in the decision tree; and

using the decision tree to identify a leaf node of the tree based on an input.

9. The computer-readable medium of claim 8 wherein using mutual information to form clusters of tokens comprises forming clusters of phones.

10. The computer-readable medium of claim 9 wherein using the decision tree to identify a leaf node based on an input comprises identifying a leaf node for a context-dependent phone.

11. The computer-readable medium of claim 10 wherein the context-dependent phone comprises a triphone.

12. The computer-readable medium of claim 8 wherein using mutual information to form clusters of tokens comprises forming clusters of letters.

13. The computer-readable medium of claim 12 wherein using the decision tree to identify a leaf node comprises using the decision tree to identify a pronunciation for an input comprising a combination of letters.

14. The computer-readable medium of claim 8 where using mutual information to form clusters of tokens comprises:

identifying a first possible cluster and a second possible cluster;

determining a mutual information score for the training data using the first possible cluster;

determining a mutual information score for the training data using the second possible cluster; and

selecting between the first possible cluster and the second possible cluster based on the mutual information scores for the first possible cluster and the second possible cluster.

15. A method of forming a decision tree, the method comprising:

identifying at least two possible clusters of tokens in a set of training data;

using co-occurrence frequency counts of clusters to select one of the at least two possible clusters;

using the selected cluster as a question for a node in the decision tree.

16. The method of claim 15 wherein using co-occurrence frequency counts comprises determining a mutual information score.

17. The method of claim 15 wherein each token is a phone.

18. The method of claim 17 wherein the decision tree defines groupings for context-dependent phones.

19. The method of claim 15 wherein each token is a letter.