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

• US 9,064,491 B2
• Filed: 08/08/2012
• Issued: 06/23/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): ALBERTALLI, BRIAN LOUIS
• Application Number:
  US13/569,830
• Publication Number:
  US 20130325472A1
• Time in Patent Office: 1,049 Days
• 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 frequency information associated with features in the data. Techniques include determining a first transformation based, at least in part, on the frequency information, 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 using only a subset of the training data based, at least in part, on frequency information corresponding to a number of times respective words in a vocabulary of interest occurred in the subset of the training data, 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 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 cluster that the input data was determined to be associated with.

2. The method of claim 1, wherein the at least a portion of the training data included a plurality of observations, and wherein each of the plurality of observations was associated with one of the plurality of classifications.

3. The method of claim 2, wherein the frequency information comprises feature counts that corresponded to the number of times respective words in a vocabulary of interest occurred in the plurality of speech utterances for each of the plurality of classifications.

4. The method of claim 3, wherein the plurality of observations were represented by a respective plurality of feature vectors, each of the plurality of feature vectors having included a plurality of values associated with a respective represented in the training data, and wherein the feature counts were based on summing respective values for feature vectors associated with each of the plurality of classifications.

5. The method of claim 4, wherein the frequency information included the feature counts scaled by at least one weighting factor.

6. The method of claim 1, wherein the first transformation comprises at least one transformation matrix that was formed, at least in part, from the frequency information.

7. The method of claim 2, wherein the first transformation transforms the input data from an n-dimensional space to transformed input data in a lower m-dimensional space.

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

9. The method of claim 1, further comprising performing at least one action based on the classification of the input data.

10. 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 a plurality of representative vectors that were determined from the training data for the plurality of classifications, respectively; and

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

11. At least one computer readable storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to 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 using only a subset of the training data based, at least in part, on frequency information corresponding to a number of times respective words in a vocabulary of interest occurred in the subset of the training data, 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 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 cluster that the input data was determined to be associated with.

12. The at least one computer readable storage medium of claim 11, wherein the at least a portion of the training data included a plurality of observations, and wherein each of the plurality of observations was associated with one of the plurality of classifications.

13. The at least one computer readable storage medium of claim 12, wherein the frequency information comprises feature counts corresponded to a number of times respective words in a vocabulary of interest occurred in the plurality of speech utterances for each of the plurality of classifications.

14. The at least one computer readable storage medium of claim 13, wherein the plurality of observations were represented by a respective plurality of feature vectors, each of the plurality of feature vectors having included a plurality of values associated with a respective represented in the training data, and wherein the feature counts were based on summing respective values for feature vectors associated with each of the plurality of classifications.

15. The at least one computer readable storage medium of claim 14, wherein the frequency information included the feature counts scaled by at least one weighting factor.

16. The at least one computer readable storage medium of claim 11, wherein the first transformation comprises at least one transformation matrix that was formed, at least in part, from the frequency information.

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

18. The at least one computer readable storage medium of claim 17, wherein m corresponds to a number of classifications corresponding to the plurality of classifications.

19. The at least one computer readable storage medium of claim 11, further comprising performing at least one action based on the classification of the input data.

20. The at least one computer readable storage medium of claim 11, 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 a plurality of representative vectors that were determined from the training data for the plurality of classifications, respectively; and

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

21. 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 system comprising:

at least one computer readable storage medium for storing the input data and for storing a first transformation generated using only a subset of the training data based, at least in part, on frequency information corresponding to a number of times respective words in a vocabulary of interest occurred in the subset of the training data, 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 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 cluster that the input data was determined to be associated with.

22. The system of claim 21, wherein the at least a portion of the training data included a plurality of observations, and wherein each of the plurality of observations was associated with one of the plurality of classifications.

23. The system of claim 22, wherein the frequency information comprises feature counts corresponded to a number of times respective words in a vocabulary of interest occurred in the plurality of utterances for each of the plurality of classifications.

24. The system of claim 23, wherein the plurality of observations were represented by a respective plurality of feature vectors, each of the plurality of feature vectors having included a plurality of values associated with a respective represented in the training data, and wherein the feature counts were based on summing respective values for feature vectors associated with each of the plurality of classifications.

25. The system of claim 24, wherein the frequency information included the feature counts scaled by at least one weighting factor.

26. The system of claim 21, wherein the first transformation comprises at least one transformation matrix that was formed, at least in part, from the frequency information.

27. The system of claim 21, wherein the first transformation transforms the input data from an n-dimensional space to transformed input data in a lower m-dimensional space.

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

29. The system of claim 21, further comprising performing at least one action based on the classification of the input data.

30. The system of claim 21, 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 a plurality of representative vectors that were determined from the training data for the plurality of classifications, respectively; and

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