Sub-partitioned vector quantization of probability density functions

• US 5,535,305 A
• Filed: 12/31/1992
• Issued: 07/09/1996
• Est. Priority Date: 12/31/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc., Intel Corporation
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Acero, Alejandro, Lee, Kai-Fu, Chow, Yen-Lu
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): ONKA, THOMAS
• Application Number:
  US07/999,293
• Time in Patent Office: 1,286 Days
• Field of Search: 395/2.65, 395/2.54, 395/2.47, 395/2.49
• US Class Current: 704/256
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G10L 15/144 Training of HMMs
• CPC Class Codes: G10L 2015/022 Demisyllables, biphones or triphones being the recognition units

Abstract

A speech recognition memory compression method and apparatus subpartitions probability density function (pdf) space along the hidden Markov model (HMM) index into packets of typically 4 to 8 log-pdf values. Vector quantization techniques are applied using a logarithmic distance metric and a probability weighted logarithmic probability space for the splitting of clusters. Experimental results indicate a significant reduction in memory can be obtained with little increase in overall speech recognition error.

Claims

1. A method for creating a subpartitioned vector quantized memory for the storage of hidden Markov model (HMM) log-probability density functions (log-pdfs) corresponding to a phoneme model having at least one code-book and one state, comprising the following steps:

a) organizing the HMM log-pdfs of each code-book by column and grouped by state so that corresponding log-pdf values of each of the HMM log-pdfs form a set of log-pdf value columns;

b) subpartitioning the log-pdf value columns into an integer number of equal length packets each packet identified by an associated packet index;

c) vector quantizing the subpartitioned packets, creating a set of subpartitioned vector quantization (SVQ) encoding vectors and associated SVQ encoding vector indices;

d) constructing an address translation table that is addressable by the packet indices, listing the SVQ encoding vector indices associated with each packet index, for generating, at output, an encoding index corresponding to the packet index used to address the address translation table; and

e) constructing a SVQ vector table for storing the set of SVQ encoding vectors in accordance with the associated SVQ encoding vector indices.

2. The method of claim 1 wherein the step of vector quantizing the subpartitioned packets comprises the following steps:

a) selecting an initial set of at least two trial cluster centroids;

b) assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial cluster centroids and assigning the given packet to the closest trial cluster centroid;

c) computing an actual cluster centroid for each cluster corresponding to a trial centroid;

d) computing an overall error value using the actual cluster centroids and if greater than a prescribed value selecting a new set of trial cluster centroids and returning to step (b), otherwise proceed to step (e);

e) splitting the clusters corresponding to the actual cluster centroids of step (c) by selecting two or more trial cluster centroids for each actual cluster centroid and returning to step (b) unless a prescribed number of clusters has been created.

3. The method of claim 2 wherein the step of assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial centroids is computed in probability-weighted-log-probability space.

4. The method of claim 2 wherein the step of splitting clusters is based on a weighted-log-probability space.

5. The method of claim 2 wherein the step of splitting clusters uses a binary splitting algorithm in weighted-log-probability space.

6. The method of claim 2 wherein the step of assigning packets to the trial cluster centroids by computing the distance is computed in log-probability space.

7. The method of claim 2 wherein the step of splitting clusters is based on a log-probability space.

8. The method of claim 1 further comprising steps for retrieving a packet specified by a packet index from a subpartitioned vector quantized (SVQ) memory for HMM log-pdfs, the SVQ memory comprising an address translation table and a SVQ vector table, the further steps comprising:

a) addressing the address translation table by the packet index and retrieving a corresponding SVQ encoding index; and

b) addressing the SVQ vector table by using the corresponding SVQ encoding index and retrieving a SVQ encoding vector corresponding to the SVQ encoding index.

9. The method of claim 8 further comprising a step for retrieving a HMM log-pdf value corresponding to a specified log-pdf element index of a specified packet index, the step comprising

selecting the element of the SVQ encoding vector indicated by the specified log-pdf element index.

10. A subpartitioned vector quantization memory compression storage and retrieval system for HMM log-pdfs, addressable by a read address that includes a packet index corresponding to a packet location in uncompressed memory, comprising:

a) an address translation table memory for storing and outputting SVQ encoding vector indices at an output port, each addressable through a read address port by a corresponding packet index; and

b) a vector table memory for storing a set of SVQ encoding vectors, addressable by a corresponding encoding vector index, with a read address port connected to the output of the address translation table memory, and an output port for providing the encoded vector corresponding to a packet specified by the packet index.

11. The memory .compression system of claim 10 further comprising means for selecting a specific element from the encoded vector corresponding to a packet specified by the packet index.

12. The memory compression system of claim 11 wherein the externally provided element index is a set of lower order bits in the read address supplied to the memory compression storage and retrieval system.

13. A method for creating a subpartitioned vector quantized (SVQ) memory for compressing capacity memory for the storage of a set of discrete log-probability density functions (log-pdfs) each with an equal number of prescribed elements, comprising the following steps:

a) arranging the set of log-pdfs as a matrix wherein each log-pdf of the set is contained in a row and the elements of each row are elements of distinct columns;

b) subpartitioning the log-pdf value columns into an integer number of equal length packets each packet identified by an associated packet index;

c) vector quantizing the subpartitioned packets, creating a set of subpartitioned vector quantization (SVQ) encoding vectors and associated SVQ encoding vector indices;

d) constructing an address translation table that is addressable by the packet indices, listing the SVQ encoding vector indices associated with each packet index, for generating, at output, an encoding index corresponding to the packet index used to address the address translation table; and

e) constructing a SVQ vector table for storing the set of SVQ encoding vectors in accordance with the associated SVQ encoding vector indices.

14. The method of claim 13 further comprising the step of converting the elements of a set of discrete probability density functions (pdfs), each set with an equal number of prescribed elements, by substituting the logarithm of the elements for forming a set of log-probability density functions (log-pdfs).

15. The method of claim 13 wherein the step of vector quantizing the subpartitioned packets comprises the following steps:

a) selecting an initial set of at least two trial cluster centroids;

b) assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial cluster centroids and assigning the given packet to the closest trial cluster centroid;

c) computing an actual cluster centroid for each cluster corresponding to a trial cluster centroid;

d) computing an overall error value using the actual cluster centroids and if greater than a prescribed value selecting a new set of trial cluster centroids and returning to step (b), otherwise proceed to step (e);

e) splitting the clusters corresponding to the actual cluster centroids of step (c) by selecting two or more trial cluster centroids for each actual cluster centroid and returning to step (b) unless a prescribed number of clusters has been created.

16. The method of claim 15 wherein the step of assigning packets to the trial cluster centroids by computing the distance between a given packet and the trial centroids is computed in probability-weighted-log-probability space.

17. The method of claim 15 wherein the step of splitting clusters is based on a weighted-log-probability space.

18. The method of claim 15 wherein the step of splitting clusters uses a binary splitting algorithm in weighted-log-probability space.

19. The method of claim 15 wherein the step of assigning packets to the trial cluster centroids by computing the distance is computed in log-probability space.

20. The method of claim 15 wherein the step of splitting clusters is based on a log-probability space.

21. The method of claim 13 further comprising steps for retrieving a packet specified by a packet index from a subpartitioned vector quantized (SVQ) memory for log-probability density functions (log-pdfs), the SVQ memory comprising an address translation table and a SVQ vector table, the further steps comprising:

a) addressing the address translation table by the packet index and retrieving a corresponding SVQ encoding index; and

b) addressing the SVQ vector table by using the corresponding SVQ encoding index and retrieving a SVQ encoding vector corresponding to the SVQ encoding index.

22. The method of claim 21 further comprising a step for retrieving a log-probability density function (log-pdf) value corresponding to a specified log-pdf element index of a specified packet index, the step comprising

selecting the element of the SVQ encoding vector indicated by the specified log-pdf element index.

23. A speech recognition system comprising:

a) a speech transducer for generating an electrical signal representative of the input acoustical speech signal;

b) an analog-to-digital converter for scalar quantization of the electrical signal at its output, having an input port connected to the output of the speech transducer;

c) a speech signal feature extraction processor connected to the output of the analog-to-digital converter for extracting a speech feature vector;

d) a vector quantizer having an input connected to the output of the feature extraction processor for producing a vector quantized speech feature vector at an output;

e) a phoneme probability processor connected to the output of the vector quantifier for operating on the vector quantized speech feature vector and computing a set of probabilities that a given hidden Markov model produced the speech feature vector based on a prescribed set of hidden Markov models;

f) a hidden Markov model memory for storing a prescribed set of hidden Markov models which is implemented as a sub-partitioned vector quantization storage and retrieval system, addressable by the phoneme probability processor and for producing at an output phone probabilities, the output connected to the phoneme probability processor; and

g) a search engine for searching for a candidate sentence, given the phone probabilities, and for outputting a word sequence identifier for the most probable word sequence of the candidate sentence.

24. The speech recognition system of claim 23 wherein the speech feature extraction processor comprises:

(a) a linear predictive coding processing for producing at output a set of linear predictive coding coefficients representative of the acoustic speech signal with its input connected to the analog-to-digital converter output.

(b) a cepstral processor with it input connected to the linear predictive encoding processor output for producing a cepstral vector with a set of coefficients representative of the linear predictive coding coefficients.

25. The speech recognition system of claim 23 wherein the system further comprises a multiplicity of vector quantizers, one for each distinct feature vector.