# US 2006/0053015 A1 · Method, apparatus and system for building a compact language model for large vocabulary continous speech recognition (lvcsr) system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0053015 A1
- Document ID: US20060053015A1
- Status: Published application
- Kind: A1
- Application number: 10/297,354
- Filed: 2001-04-03
- Published: 2006-03-09
- Earliest claimed: 2001-04-03
- Assignees: Intel Corporation
- Inventors: Chunrong Lai; Qingwei Zhao; Jielin Pan
- Web page: https://patentgrep.com/patent/US20060053015A1

## CPC

- G10L 15/197: Probabilistic grammars, e.g. word n-grams
- 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)
- G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING

## 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

### Claim 1

A method comprising:
classifying a set of probabilistic attributes in an N-gram language model into a plurality of classes;
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; and
representing a probabilistic attribute in each class by the centroid of the corresponding segment to which the respective probabilistic attribute belongs.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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 unigram probability values, a second class corresponding to a set of unigram back-off weights, a third class corresponding to a set of bigram probability values, a fourth class corresponding to a set of bigram back-off weights, and a fifth class corresponding to a set of trigram probability values.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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 all segments to generate the total deviation.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 7)

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.

### Claim 12

A method comprising:
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 until one or more predetermined conditions are satisfied, 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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 12)

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.

### Claim 16

An apparatus comprising:
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 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 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.

### Claim 17 (depends on 16)

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 unigram probability values, a second class corresponding to a set of unigram back-off weights, a third class corresponding to a set of bigram probability values, a fourth class corresponding tp a set of bigram back-off weights, and a fifth class corresponding to a set of trigram probability values.

### Claim 18 (depends on 16)

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.

### Claim 19 (depends on 18)

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 deviations of all clusters to generate the total deviation.

### Claim 20 (depends on 18)

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.

### Claim 21 (depends on 18)

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.

### Claim 22 (depends on 18)

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.

### Claim 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 based, at least in part, upon the feature vectors, the acoustic model, and the language model.

### Claim 24 (depends on 23)

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

### Claim 25 (depends on 23)

The system of claim 23 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.

### Claim 26 (depends on 25)

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.

### Claim 27

A machine-readable medium comprising instructions which, when executed by a machine, cause the machine to perform operations including:
classifying a set of probabilistic attributes in an N-gram language model into a plurality of classes;
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; and
representing a probabilistic attribute in each class by the centroid of the corresponding segment to which the respective probabilistic attribute belongs.

### Claim 28 (depends on 27)

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

### Claim 29 (depends on 27)

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.

### Claim 30 (depends on 29)

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.