Methods and apparatus for performing transformation techniques for data clustering and/or classification

• US 9,117,444 B2
• Filed: 08/08/2012
• Issued: 08/25/2015
• Est. Priority Date: 05/29/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Rachevsky, Leonid, Kanevsky, Dimitri, Ramabhadran, Bhuvana
• Primary Examiner(s): GUERRA-ERAZO, EDGAR X
• Application Number:
  US13/569,792
• Publication Number:
  US 20130325471A1
• Time in Patent Office: 1,112 Days
• Field of Search: 704/245, 704/243, 704/244, 704/246, 704/256, 704/256.7, 704/235, 704/277
• US Class Current: 1/1
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G10L 15/063 Training

Abstract

Some aspects include transforming data, at least a portion of which has been processed to determine at least one representative vector associated with each of a plurality of classifications associated with the data to obtain a plurality of representative vectors. Techniques comprise determining a first transformation based, at least in part, on the plurality of representative vectors, applying at least the first transformation to the data to obtain transformed data, and fitting a plurality of clusters to the transformed data to obtain a plurality of established clusters. Some aspects include classifying input data by transforming the input data using at least the first transformation and comparing the transformed input data to the established clusters.

Claims

1. A method of classifying input data representing speech input by a user of a speech application as belonging to one of a plurality of classifications, the plurality of classifications associated with a respective plurality of clusters that were fit to training data representing a plurality of speech utterances associated with the speech application, the method comprising:

using at least one processor to perform;

obtaining a first transformation generated based, at least in part, on a plurality of representative vectors determined from the training data, the plurality of representative vectors including at least one representative vector determined for each of the plurality of classifications, wherein the plurality of clusters were fit to the training data at least in part by fitting the plurality of clusters to transformed training data obtained by applying the first transformation to the training data;

transforming the input data using at least the first transformation to obtain transformed input data representing the speech input by the user of the speech application;

comparing the transformed input data to the plurality of clusters to determine which cluster of the plurality of clusters the input data should be associated with; and

classifying the input data according to a classification of the plurality of classifications associated with the determined cluster.

2. The method of claim 1, wherein each of the plurality of representative vectors was determined based on its location with respect to training data associated with other classifications.

3. The method of claim 1, wherein each of the plurality of representative vectors represented a boundary between training data associated with the corresponding classification and training data associated with other classifications.

4. The method of claim 3, wherein the plurality of representative vectors were determined as a respective plurality of support vectors.

5. The method of claim 1, wherein the first transformation transforms the input data from an n-dimensional space to a lower m-dimensional space.

6. The method of claim 5, wherein m corresponds to a number of classifications corresponding to the plurality of classifications.

7. The method of claim 1, further comprising:

obtaining at least one second transformation, the at least one second transformation comprising at one least one of;

a transformation that approximated at least one constraint, relating to a similarity and/or dissimilarity of at least some of the training data, using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least some of the training data; and

a transformation determined based, at least in part, on frequency information determined based on features represented in the training data; and

applying the at least one second transformation to the input data to obtained the transformed input data.

22. The method of claim 1, wherein the first transformation was generated using only a subset of the training data.

8. At least one non-transitory computer readable storage medium for storing instructions that, when executed on at least one processor, perform a method of classifying input data representing speech input by a user of a speech application as belonging to one of a plurality of classifications, the plurality of classifications associated with a respective plurality of clusters that were fit to training data representing a plurality of speech utterances associated with the speech application, the method comprising:

obtaining a first transformation generated based, at least in part, on a plurality of representative vectors determined from the training data, the plurality of representative vectors including at least one representative vector determined for each of the plurality of classifications, wherein the plurality of clusters were fit to the training data at least in part by fitting the plurality of clusters to transformed training data obtained by applying the first transformation to the training data;

transforming the input data using at least the first transformation to obtain transformed input data representing the speech input by the user of the speech application;

comparing the transformed input data to the plurality of clusters to determine which cluster of the plurality of clusters the input data should be associated with; and

classifying the input data according to a classification of the plurality of classifications associated with the determined cluster.

9. The at least one non-transitory computer readable storage medium of claim 8, wherein each of the plurality of representative vectors was determined based on its location with respect to training data associated with other classifications.

10. The at least one non-transitory computer readable storage medium of claim 8, wherein each of the plurality of representative vectors represented a boundary between training data associated with the corresponding classification and training data associated with other classifications.

11. The at least one non-transitory computer readable storage medium of claim 10, wherein the plurality of representative vectors were determined as a respective plurality of support vectors.

12. The at least one non-transitory computer readable storage medium of claim 8, wherein the first transformation transforms the input data from an n-dimensional space to a lower m-dimensional space.

13. The at least one non-transitory computer readable storage medium of claim 12, wherein m corresponds to a number of classifications corresponding to the plurality of classifications.

14. The at least one non-transitory computer readable storage medium of claim 8, further comprising:

obtaining at least one second transformation, the at least one second transformation comprising at one least one of;

a transformation that approximated at least one constraint, relating to a similarity and/or dissimilarity of at least some of the training data, using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least some of the training data; and

a transformation determined based, at least in part, on frequency information determined based on features represented in the training data; and

applying the at least one second transformation to the input data to obtained the transformed input data.

23. The non-transitory computer-readable storage medium of claim 8, wherein the first transformation was generated using only a subset of the training data.

15. A system for classifying input data representing speech input by a user of a speech application as belonging to one of a plurality of classifications, the plurality of classifications associated with a respective plurality of clusters that were fit to training data representing a plurality of speech utterances associated with the speech application, the method comprising:

at least one computer readable storage medium for storing the input data and for storing a first transformation generated based, at least in part, on a plurality of representative vectors determined from the training data, the plurality of representative vectors including at least one representative vector determined for each of the plurality of classifications, wherein the plurality of clusters were fit to the training data at least in part by fitting the plurality of clusters to transformed training data obtained by applying the first transformation to the training data; and

at least one processor capable of accessing the at least one computer readable storage medium, the at least one processor configured to;

transform the input data using at least the first transformation to obtain transformed input data representing the speech input by the user of the speech application;

compare the transformed input data to the plurality of clusters to determine which cluster of the plurality of clusters the input data should be associated with; and

classify the input data according to a classification of the plurality of classifications associated with the determined cluster.

16. The system of claim 15, wherein each of the plurality of representative vectors was determined based on its location with respect to training data associated with other classifications.

17. The system of claim 15, wherein each of the plurality of representative vectors represented a boundary between training data associated with the corresponding classification and training data associated with other classifications.

18. The system of claim 17, wherein the plurality of representative vectors were determined as a respective plurality of support vectors.

19. The system of claim 15, wherein the first transformation transforms the input data from an n-dimensional space to a lower m-dimensional space.

20. The system of claim 19, wherein m corresponds to a number of classifications corresponding to the plurality of classifications.

21. The system of claim 15, wherein the at least one processor is configured to:

obtain at least one second transformation, the at least one second transformation comprising at one least one of;

a transformation that approximated at least one constraint, relating to a similarity and/or dissimilarity of at least some of the training data, using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least some of the training data; and

a transformation determined based, at least in part, on frequency information determined based on features represented in the training data; and

apply the at least one second transformation to the input data to obtained the transformed input data.

24. The system of claim 15, wherein the first transformation was generated using only a subset of the training data.