Method, apparatus and system for building a compact language model for large vocabulary continuous speech recognition (LVCSR) system

• US 7,418,386 B2
• Filed: 04/03/2001
• Issued: 08/26/2008
• Est. Priority Date: 04/03/2001
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zhao, Qingwei, Lai, Chunrong, Pan, Jielin
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US10/297,354
• Publication Number:
  US 20060053015A1
• Time in Patent Office: 2,702 Days
• Field of Search: 704/257
• US Class Current: 704/257
• CPC Class Codes: G10L 15/06 Creation of reference templates; Training of speech recognition systems, e.g. adaptation to the characteristics of the speaker's voice G10L15/14 takes precedence
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

According to one aspect of the invention, a method is provided in which a set of probabilistic attributes in an N-gram language model is classified into a plurality of classes. Each resultant class is clustered into a plurality of segments to build a code-book for the respective class using a modified K-means clustering process which dynamically adjusts the size and centroid of each segment during each iteration in the modified K-means clustering process. A probabilistic attribute in each class is then represented by the centroid of the corresponding segment to which the respective probabilistic attribute belongs.

Claims

1. A method comprising:

digitizing input speech;

converting the digitized input speech into a sequence of feature vectors;

classifying a set of probabilistic attributes in an N-gram language model into a plurality of classes, the probabilistic attributes representing various conditional probabilities of a set of words in the language of the input speech;

clustering each resultant class into a plurality of segments to build a codebook for the respective class using a modified K-means clustering process which dynamically adjusts the size and centroid of each segment during each iteration in the modified K-means clustering process;

representing a probabilistic attribute in each class by the centroid of the corresponding segment to which the respective probabilistic attribute belongs; and

applying the feature vectors to the probabilistic attributes to select a set of words corresponding to the input speech.

2. The method of claim 1 wherein a probabilistic attribute is represented by a first number of data bits before clustering.

3. The method of claim 2 wherein the respective probabilistic attribute is represented by an index value having a second number of data bits after clustering, the second number being smaller than the first number, the respective index value being used to reference a corresponding codeword in the respective codebook.

4. The method of claim 1 wherein a probabilistic attribute is a probability value associated with an n-gram node in the N-gram language model.

5. The method of claim 1 wherein a probabilistic attribute is a back-off weight associated with an n-gram node in the N-gram language model.

6. The method of claim 1 wherein the N-gram language model is a tri-gram language model and wherein the plurality of classes includes a first class corresponding to a set of uni-gram probability values, a second class corresponding to a set of uni-gram back-off weight, a third class corresponding to a set of bi-gram probability values, a fourth class corresponding to a set of bi-gram back-off weights, and a fifth class corresponding to a set of tri-gram probability values.

7. The method of claim 1 wherein clustering each resultant class includes:

initializing the plurality of segments such that all segments have equivalent areas;

setting the centroid of each segment such that the area of the respective segment is approximately equally split based on the corresponding centroid; and

performing a set of operations iteratively until one or more optimization criteria are met, including;

computing a total deviation of the plurality of segments;

replacing the edge of each segment by an arithmetic average of the nearest two centroids; and

setting a new centroid for each resultant segment.

8. The method of claim 7 wherein computing the total deviation includes:

computing a deviation of each segment based upon the corresponding centroid of the respective segment; and

summing the deviations of the segments to generate the total deviation.

9. The method of claim 7 wherein performing the set of operations includes:

determining, for each segment in the plurality of segments, whether the new edge value equals the previous edge value; and

indicating that the one or more optimization criteria are met if the new edge value equals the previous edge value.

10. The method of claim 7 wherein performing the set of operations includes:

determining whether a predetermined number of iterations is reached; and

indicating that the one or more optimization criteria are met if the predetermined number of iterations is reached.

11. The method of claim 7 wherein performing the set of operations includes:

determining whether a changing rate in the total deviation is less than a predetermined threshold; and

indicating that the one or more optimization criteria are met if the changing rate in the total deviation is less than the predetermined threshold.

12. A method comprising:

digitizing input speech;

converting the digitized input speech into a sequence of feature vectors; and

applying the feature vectors to a decoder to select a set of words corresponding to the input speech, the decoder being generated by

clustering a set of probabilistic values associated with each data class of a plurality of data classes of an N-gram language model into a plurality of clusters using a modified K-means clustering process which dynamically adjusts the size and centroid of each respective cluster during each iteration in the modified K-means clustering process unit one or more predetermined conditions are satisfied, the probabilistic attributes representing various conditional probabilities of a set of words in the language of the input speech, the clustering including;

initializing the plurality of clusters such that all clusters have equivalent areas;

setting the centroid of each resultant cluster such that the area of each respective cluster is approximately equally split based on the corresponding centroid; and

performing a set of operations iteratively until one or more predetermined conditions are satisfied, including;

computing a total deviation of the clusters;

replacing the edge of each cluster by an arithmetic average of the nearest two centroids; and

setting a new centroid for each resultant segment.

13. The method of claim 12 wherein performing the set of operations includes:

determining, for each cluster in the plurality of clusters, whether the new edge value equals the previous edge value; and

indicating that the one or more predetermined conditions are satisfied if the new edge value equals the previous edge value.

14. The method of claim 12 wherein performing the set of operations includes:

determining whether a predetermined number of iterations is reached; and

indicating that the one or more predetermined conditions are satisfied if the predetermined number of iterations is reached.

15. The method of claim 12 wherein performing the set of operations includes:

determining whether a changing rate in the total deviation is less than a predetermined threshold; and

indicating that the one or more predetermined conditions are satisfied if the changing rate in the total deviation is less than the predetermined threshold.

16. An apparatus comprising:

a decoder for a speech recognition system, the decoder including an input to receive a characterization of the spectral properties of a speech signal, and a language model to apply to the characterization in order to recognize the speech signal as a set of words, the language model having

a plurality of codebooks each being built based upon a corresponding class of probabilistic values that represent conditional probabilities of a set of words in the in a language model, each codebook including a plurality of codewords each representing one or more corresponding probabilistic values, wherein each codebook of the plurality of codebooks is built using a modified K-means clustering process which dynamically adjusts the size and centroid of each cluster during each iteration in the modified K-means clustering process until a total deviation of the clusters is optimized based upon one or more optimization criteria.

17. The apparatus of claim 16 wherein the language model is a tri-gram language model and wherein the plurality of classes includes a first class corresponding to a set of uni-gram probability values, a second class corresponding to a set of uni-gram back-off weights, a third class corresponding to a set of bi-gram probability values, a fourth class corresponding to a set of bi-gram back-off weights, and a fifth class corresponding to a set of tri-gram probability values.

18. The apparatus of claim 16 wherein each codebook for the corresponding class of probabilistic values is built by the modified K-means clustering process which includes:

logic to initialize a plurality of clusters such that all clusters have equivalent areas;

logic to set the centroid of each cluster such that the area of the respective cluster is approximately equally split based on the corresponding centroid; and

logic to perform a set of operations iteratively until one or more optimization criteria are met, including;

logic to compute a total deviation of the plurality of clusters;

logic to replace the edge of each cluster by an arithmetic average of the nearest two centroids; and

logic to set a new centroid for each resultant cluster.

19. The apparatus of claim 18 wherein logic to compute the total deviation includes:

logic to compute a deviation of each cluster based upon the corresponding centroid of the respective cluster; and

logic to sum the deviation of all clusters to generate the total deviation.

20. The apparatus of claim 18 wherein logic to perform the set of operations includes:

logic to determine, for each cluster, whether the new edge value equals the previous edge value.

21. The apparatus of claim 18 wherein logic to perform the set of operations includes:

logic to determine whether a predetermined number of iterations is reached.

22. The apparatus of claim 18 wherein logic to perform the set of operations includes:

logic to determine whether a changing rate in the total deviation is less than a predetermined threshold.

23. A system comprising:

a feature extraction unit to convert an input signal representing an input speech into a set of feature vectors each representing a corresponding frame of the input signal;

an acoustic model comprising a set of phonetic statistical models each representing a distinct phonetic unit;

a language model including;

a plurality of codebooks each being built based upon a corresponding class of probabilistic values that represent conditional probabilities of a set of words in the language model, each codebook including a plurality of codewords each representing one or more corresponding probabilistic values, wherein each codebook of the plurality of codebooks is built using a modified K-means clustering process which dynamically adjusts the size and the centroid of each cluster during each iteration in the modified K-means clustering process until a total deviation of the clusters is optimized based upon one or more optimization criteria; and

a decoder coupled to the feature extraction unit, the acoustic model, and the language model, the decoder to recognize the input speech as a set of words based, at least in part, upon the feature vectors, the acoustic model, and the language model.

24. The system of claim 23 wherein the language model is a tri-gram language model and wherein the plurality of classes includes a first class corresponding to a set of uni-gram probability values, a second class corresponding to a set of uni-gram back-off weights, a third class corresponding to a set of bi-gram probability values, a fourth class corresponding to a set of bi-gram back-off weights, and a fifth class corresponding to a set of tri-gram probability values.

25. The system of claim 23 wherein each codebook for the corresponding class of probabilistic values is built by the modifier K-means clustering process which includes:

logic to initialize a plurality of clusters such that all clusters have equivalent areas;

logic to set the centroid to each cluster such that the area of the respective cluster is approximately equally split based on the corresponding centroid; and

logic to perform a set of operations iteratively until one or more optimization criteria are met, including;

logic to compute a total deviation of the plurality of clusters;

logic to replace the edge of each cluster by an arithmetic average of the nearest two centroids; and

logic to set a new centroid for each resultant cluster.

26. The system of claim 25 wherein logic to perform the set of operations includes:

logic to determine, for each cluster, whether the new edge value equals the previous edge value;

logic to determine whether a predetermined number of iterations is reached; and

logic to determine whether a changing rate in the total deviation is less than a predetermined threshold.

27. A machine-readable medium comprising instructions which, when executed by a machine, cause the machine to perform operations including:

digitizing input speech;

converting the digitized input speech into a sequence of feature vectors;

classifying a set of probabilistic attributes in an N-gram language model into a plurality of classes, the probabilistic attributes representing various conditional probabilities of a set of words in the language of the input speech;

clustering each resultant class into a plurality of segments to build a codebook for the respective class using a modified K-means clustering process which dynamically adjusts the size and the centroid of each segment during each iteration in the modified K-means clustering process;

representing a probabilistic attribute in each class by the centroid of the corresponding segment to which the respective probabilistic attribute belongs; and

applying the feature vectors to the probabilistic attributes to select a set of words corresponding to the input speech.

28. The machine readable medium of claim 27 wherein the N-gram language model is a tri-gram language model and wherein the plurality of classes includes a first class corresponding to a set of uni-gram probability values, a second class corresponding to a set of uni-gram back-off weights, a third class corresponding to a set of bi-gram probability values, a fourth class corresponding to a set of bi-gram back-off weights, and a fifth class corresponding to a set of tri-gram probability values.

29. The machine-readable medium of claim 27 wherein clustering each resultant class includes:

initializing the plurality of segments such that all segments have equivalent areas;

setting the centroid of each segment such that the area of the respective segment is approximately equally split based on the corresponding centroid; and

performing a set of operations iteratively until one or more optimization criteria are met, including;

computing a total deviation of the plurality of segments;

replacing the edge of each segment by an arithmetic average of the nearest two centroids; and

setting a new centroid for each resultant segment.

30. The machine-readable medium of claim 29 wherein performing the set of operations includes:

determining, for each cluster, whether the new edge value equals the previous edge value;

determining whether a predetermined number of iterations is reached; and

determining whether a changing rate in the total deviation is less than a predetermined threshold.