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

• US 8,972,312 B2
• Filed: 08/08/2012
• Issued: 03/03/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): Chaki, Kakali
• Assistant Examiner(s): SITIRICHE, LUIS A
• Application Number:
  US13/569,742
• Publication Number:
  US 20130325759A1
• Time in Patent Office: 937 Days
• Field of Search: None
• US Class Current: 706/12
• 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 for which at least one constraint has been specified on a portion of the data, the at least one constraint relating to a similarity and/or dissimilarity of at least some of the portion of the data. Techniques comprise determining a first transformation that approximates the at least one constraint using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least a portion of the data, 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 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, the method comprising:

obtaining a first transformation used to transform the training data when the plurality of clusters were fit to the training data, the first transformation approximating at least one constraint relating to a similarity and/or dissimilarity of at least a portion of the training data, wherein the first transformation was determined using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least a portion of the training data;

transforming the input data using at least the first transformation to obtain transformed input data;

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,

wherein the at least one constraint was specified by identifying a first set of data pairs in the data, the first set of data pairs indicating that the data identified by each respective data pair in the first set of data pairs was associated with a same classification, and was specified by identifying a second set of data pairs in the data, the second set of data pairs indicating that data identified in each respective data pair in the second set of data pairs was associated with a different classification.

2. The method of claim 1, wherein comparing the transformed input data to the plurality of cluster comprises determining which cluster center the transformed input data is closest to using at least one of a cosine similarity and a Euclidean distance.

3. The method of claim 1, wherein the first transformation was determined by selecting values for the first transformation that increased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the first set of data pairs according to the cosine similarity, and decreased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the second set of data pairs according to the cosine similarity.

4. The method of claim 1, wherein the first transformation was determined by optimizing a function that included the first transformation as a parameter.

5. The method of claim 4, wherein the function included at least one first term that evaluates the cosine similarity between data in each respective data pair in the first set of data pairs transformed using the first transformation.

6. The method of claim 5, wherein the function included at least one second term that evaluates the cosine similarity between data in each respective data pair in the second set of data pairs transformed using the first transformation.

7. The method of claim 6, wherein the first transformation was selected as a transformation that tended to maximize the at least one first term and minimize the at least one second term.

8. The method of claim 1, wherein the first transformation includes a diagonal matrix.

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, wherein the input data represents a speech input from a user.

11. 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 determined based, at least in part, on at least one representative vector that was determined from the training data for each of a plurality of classifications; and

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

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

12. At least one non-transitory computer readable storage medium storing instructions, that when executed by at least one processor, perform a method of classifying input data 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, the method comprising:

obtaining a first transformation used to transform the training data when the plurality of clusters were fit to the training data, the first transformation approximating at least one constraint relating to a similarity and/or dissimilarity of at least a portion of the training data, wherein the first transformation was determined using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least a portion of the training data;

transforming the input data using at least the first transformation to obtain transformed input data;

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,

wherein the at least one constraint was specified by identifying a first set of data pairs in the data, the first set of data pairs indicating that the data identified by each respective data pair in the first set of data pairs was associated with a same classification, and was specified by identifying a second set of data pairs in the data, the second set of data pairs indicating that data identified in each respective data pair in the second set of data pairs was associated with a different classification.

13. The at least one non-transitory computer readable storage medium of claim 12, wherein comparing the transformed input data to the plurality of cluster comprises determining which cluster center the transformed input data is closest to using at least one of a cosine similarity and a Euclidean distance.

14. The at least one non-transitory computer readable storage medium of claim 12, wherein the first transformation was determined by selecting values for the first transformation that increased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the first set of data pairs according to the cosine similarity, and decreased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the second set of data pairs according to the cosine similarity.

15. The at least one non-transitory computer readable storage medium of claim 12, wherein the first transformation was determined by optimizing a function that included the first transformation as a parameter.

16. The at least one non-transitory computer readable storage medium of claim 15, wherein the function included at least one first term that evaluates the cosine similarity between data in each respective data pair in the first set of data pairs transformed using the first transformation.

17. The at least one non-transitory computer readable storage medium of claim 16, wherein the function included at least one second term that evaluates the cosine similarity between data in each respective data pair in the second set of data pairs transformed using the first transformation.

18. The at least one non-transitory computer readable storage medium of claim 17, wherein the first transformation was selected as a transformation that tended to maximize the at least one first term and minimize the at least one second term.

19. The at least one non-transitory computer readable storage medium of claim 12, wherein the first transformation includes a diagonal matrix.

20. The at least one non-transitory computer readable storage medium of claim 12, further comprising performing at least one action based on the classification of the input data.

21. The at least one non-transitory computer readable storage medium of claim 12, wherein the input data represents a speech input from a user.

22. The at least one non-transitory computer readable storage medium of claim 12, the method further comprising:

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

a transformation determined based, at least in part, on at least one representative vector that was determined from the training data for each of a plurality of classifications; and

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

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

23. A system for classifying input data 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, the system comprising:

at least one computer readable storage medium for storing the input data and for storing a first transformation used to transform the training data when the plurality of clusters were fit to the training data, the first transformation approximating at least one constraint relating to a similarity and/or dissimilarity of at least a portion of the training data, wherein the first transformation was determined using a cosine similarity as a measure of the similarity and/or dissimilarity of the at least a portion of 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;

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,

wherein the at least one constraint was specified by identifying a first set of data pairs in the data, the first set of data pairs indicating that the data identified by each respective data pair in the first set of data pairs was associated with a same classification, and was specified by identifying a second set of data pairs in the data, the second set of data pairs indicating that data identified in each respective data pair in the second set of data pairs was associated with a different classification.

24. The system of claim 23, wherein the at least one processor is configured to determine which cluster center the transformed input data is closest to using at least one of a cosine similarity and a Euclidean distance.

25. The system of claim 23, wherein the first transformation was determined by selecting values for the first transformation that increased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the first set of data pairs according to the cosine similarity, and decreased the similarity, upon transformation by the first transformation, of at least some of the data pairs in the second set of data pairs according to the cosine similarity.

26. The system of claim 23, wherein the first transformation was determined by optimizing a function that included the first transformation as a parameter.

27. The system of claim 26, wherein the function included at least one first term that evaluates the cosine similarity between data in each respective data pair in the first set of data pairs transformed using the first transformation.

28. The system of claim 27, wherein the function included at least one second term that evaluates the cosine similarity between data in each respective data pair in the second set of data pairs transformed using the first transformation.

29. The system of claim 28, wherein the first transformation was selected as a transformation that tended to maximize the at least one first term and minimize the at least one second term.

30. The system of claim 23, wherein the first transformation includes a diagonal matrix.

31. The system of claim 23, wherein the at least one processor is configured to perform at least one action based on the classification of the input data.

32. The system of claim 23, wherein the input data represents a speech input from a user.

33. The system of claim 23, the at least one processor configured to:

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

a transformation determined based, at least in part, on at least one representative vector that was determined from the training data for each of a plurality of classifications; and

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

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