System and method for word-sense disambiguation by recursive partitioning

• US 8,099,281 B2
• Filed: 06/06/2005
• Issued: 01/17/2012
• Est. Priority Date: 06/06/2005
• Status: Active Grant

• Current Assignee: Cerence Inc., Cerence Operating Company (Cerence Inc.)
• Original Assignee: Nunance Communications Incorporated
• Inventors: Gleason, Philip
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): ADESANYA, OLUJIMI A
• Application Number:
  US11/145,656
• Publication Number:
  US 20060277045A1
• Time in Patent Office: 2,416 Days
• Field of Search: 704/260, 704/266, 704/267
• US Class Current: 704/260
• CPC Class Codes: G10L 13/08 Text analysis or generation of parameters for speech synthesis out of text, e.g. grapheme to phoneme translation, prosody generation or stress or intonation determination

Abstract

A device and related methods for word-sense disambiguation during a text-to-speech conversion are provided. The device, for use with a computer-based system capable of converting text data to synthesized speech, includes an identification module for identifying a homograph contained in the text data. The device also includes an assignment module for assigning a pronunciation to the homograph using a statistical test constructed from a recursive partitioning of training samples, each training sample being a word string containing the homograph. The recursive partitioning is based on determining for each training sample an order and a distance of each word indicator relative to the homograph in the training sample. An absence of one of the word indicators in a training sample is treated as equivalent to the absent word indicator being more than a predefined distance from the homograph.

Claims

1. A method of constructing a test for use in electronically disambiguating a homograph during a computer-based text-to-speech event, the method comprising:

using at least one processor to construct a decision tree for determining a pronunciation label for the homograph in an input word string, the decision tree comprising at least first and second nodes, the first node being a parent of the second node, wherein the at least one processor is configured to construct the decision tree at least in part by;

accessing a first set of training samples, each of the training samples comprising a word string that contains the homograph and a pronunciation label indicating a correct pronunciation of the homograph in the word string;

applying a plurality of decision rules to the first set of training samples, each of the plurality of decision rules partitioning the first set of training samples into at least two subsets of the first set of training samples;

for each one of the plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the plurality of decision rules contains training samples associated with different pronunciation labels, wherein the one of the plurality of decision rules, when applied to word strings in the first set of training samples, determines whether at least one selected word indicator is present in the word strings, and wherein at least one training sample in the first set of training samples is retained for computing the measure of impurity corresponding to the one of the plurality of decision rules even if the at least one selected word indicator is absent in the word string of the at least one training sample; and

selecting, for the first node of the decision tree, a decision rule from the plurality of decision rules based at least in part on the measures of impurity computed for the plurality of decision rules.

2. The method of claim 1, wherein the at least one processor is further configured to apply the test to the input word string at least in part by:

at the first node of the decision tree, determining whether to proceed to the second node of the decision tree, at least in part by applying the selected decision rule to the input word string.

3. The method of claim 1, wherein the selected decision rule has a lowest measure of impurity among the plurality of decision rules.

4. The method of claim 1, wherein the measures of impurity comprise an entropy measure.

5. The method of claim 4, wherein the entropy measure comprises a Shannon entropy.

6. The method of claim 4, wherein the entropy measure comprises a Gini entropy.

7. The method of claim 1, wherein, when applied to word strings in the first set of training samples, the one of the plurality of decision rules determines an order and a distance of at least one selected word indicator relative to the homograph in each word string, wherein an absence of the at least one selected word indicator in at least one word string is treated as the at least one selected word indicator being more than a predefined distance from the homograph.

8. The method of claim 1, wherein the plurality of decision rules is a first plurality of decision rules and the selected decision rule is a first decision rule that partitions the first set of training samples into at least second and third sets of training samples, and wherein the at least one processor is further configured to construct the decision tree at least in part by:

applying a second plurality of decision rules to the second set of training samples, each of the second plurality of decision rules partitioning the second set of training samples into at least two subsets of the second set of training samples;

for each one of the second plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the second plurality of decision rules contains training samples associated with different pronunciation labels; and

selecting, for the second node of the decision tree, a second decision rule from the second plurality of decision rules based at least in part on the measures of impurity computed for the second plurality of decision rules.

9. A system for constructing a test for use in electronically disambiguating a homograph during a computer-based text-to-speech event, the system comprising:

an input for receiving a plurality of training samples, each training sample comprising a word string containing the homograph and a pronunciation label indicating a correct pronunciation of the homograph in the word string; and

at least one computer coupled to the input to receive the plurality of training samples, the at least one computer programmed to construct a decision tree for determining a pronunciation label for the homograph in an input word string, the decision tree comprising at least first and second nodes, the first node being a parent of the second node, wherein the at least one computer is programmed to construct the decision tree at least in part by;

accessing a first set of training samples, each of the training samples comprising a word string that contains the homograph and a pronunciation label indicating a correct pronunciation of the homograph in the word string;

applying a plurality of decision rules to the first set of training samples, each of the plurality of decision rules partitioning the first set of training samples into at least two subsets of the first set of training samples;

for each one of the plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the plurality of decision rules contains training samples associated with different pronunciation labels, wherein the one of the plurality of decision rules, when applied to word strings in the first set of training samples, determines whether at least one selected word indicator is present in the word strings, and wherein at least one training sample in the first set of training samples is retained for computing the measure of impurity corresponding to the one of the plurality of decision rules even if the at least one selected word indicator is absent in the word string of the at least one training sample; and

selecting, for the first node of the decision tree, a decision rule from the plurality of decision rules based at least in part on the measures of impurity computed for the plurality of decision rules.

10. The system of claim 9, wherein the at least one computer is further programmed to apply the test to the input word string at least in part by:

at the first node of the decision tree, determining whether to proceed to the second node of the decision tree, at least in part by applying the selected decision rule to the input word string.

11. The system of claim 9, wherein the selected decision rule has a lowest measure of impurity among the plurality of decisions.

12. The system of claim 9, wherein the measures of impurity comprise an entropy measure.

13. The system of claim 12, wherein the entropy measure comprises a Shannon entropy.

14. The system of claim 12, wherein the entropy measure comprises a Gini entropy.

15. The system of claim 9, wherein, when applied to word strings in the first set of training samples, the one of the plurality of decision rules determines an order and a distance of at least one selected word indicator relative to the homograph in each word string, wherein an absence of the at least one selected word indicator in at least one word string is treated as the at least one selected word indicator being more than a predefined distance from the homograph.

16. The system of claim 9, wherein the plurality of decision rules is a first plurality of decision rules and the selected decision rule is a first decision rule that partitions the first set of training samples into at least second and third sets of training samples, and wherein the at least one computer is further programmed to construct the decision tree at least in part by:

applying a second plurality of decision rules to the second set of training samples, each of the second plurality of decision rules partitioning the second set of training samples into at least two subsets of the second set of training samples;

for each one of the second plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the second plurality of decision rules contains training samples associated with different pronunciation labels; and

selecting, for the second node of the decision tree, a second decision rule from the second plurality of decision rules based at least in part on the measures of impurity computed for the second plurality of decision rules.

17. At least one machine readable memory, having stored thereon a computer program having a plurality of code sections executable by at least one machine for causing the at least one machine to perform a computer-implemented method for constructing a test for use in disambiguating a homograph during a computer-based text-to-speech event, the method comprising steps of:

using at least one processor to construct a decision tree for determining a pronunciation label for the homograph in an input word string, the decision tree comprising at least first and second nodes, the first node being a parent of the second node, wherein the at least one processor is configured to construct the decision tree at least in part by;

accessing a first set of training samples, each of the training samples comprising a word string that contains the homograph and a pronunciation label indicating a correct pronunciation of the homograph in the word string;

applying a plurality of decision rules to the first set of training samples, each of the plurality of decision rules partitioning the first set of training samples into at least two subsets of the first set of training samples;

for each one of the plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the plurality of decision rules contains training samples associated with different pronunciation labels, wherein the one of the plurality of decision rules, when applied to word strings in the first set of training samples, determines whether at least one selected word indicator is present in the word strings, and wherein at least one training sample in the first set of training samples is retained for computing the measure of impurity corresponding to the one of the plurality of decision rules even if the at least one selected word indicator is absent in the word string of the at least one training sample; and

selecting, for the first node of the decision tree, a decision rule from the plurality of decision rules based at least in part on the measures of impurity computed for the plurality of decision rules.

18. The at least one machine readable memory of claim 17, wherein the at least one processor is further configured to apply the test to the input word string at least in part by:

at the first node of the decision tree, determining whether to proceed to the second node of the decision tree, at least in part by applying the selected decision rule to the input word string.

19. The at least one machine readable memory of claim 17, wherein the selected decision rule has a lowest measure of impurity among the plurality of decision rules.

20. The at least one machine readable memory of claim 17, wherein the measures of impurity comprise an entropy measure.

21. The at least one machine readable memory of claim 20, wherein the entropy measure comprises a Shannon entropy.

22. The at least one machine readable memory of claim 20, wherein the entropy measure comprises a Gini entropy.

23. The at least one machine readable memory of claim 17, wherein, when applied to word strings in the first set of training samples, the one of the plurality of decision rules determines an order and a distance of at least one selected word indicator relative to the homograph in each word string, wherein an absence of the at least one selected word indicator in at least one word string is treated as the at least one selected word indicator being more than a predefined distance from the homograph.

24. The at least one machine readable memory of claim 17, wherein the plurality of decision rules is a first plurality of decision rules and the selected decision rule is a first decision rule that partitions the first set of training samples into at least second and third sets of training samples, and wherein the at least one processor is further configured to construct the decision tree at least in part by:

applying a second plurality of decision rules to the second set of training samples, each of the second plurality of decision rules partitioning the second set of training samples into at least two subsets of the second set of training samples;

for each one of the second plurality of decision rules, computing a corresponding measure of impurity indicative of an extent to which each of the at least two subsets formed by applying the one of the second plurality of decision rules contains training samples associated with different pronunciation labels; and

selecting, for the second node of the decision tree, a second decision rule from the second plurality of decision rules based at least in part on the measures of impurity computed for the second plurality of decision rules.