Metric learning for nearest class mean classifiers

• US 9,031,331 B2
• Filed: 07/30/2012
• Issued: 05/12/2015
• Est. Priority Date: 07/30/2012
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mensink, Thomas, Verbeek, Jakob, Csurka, Gabriela, Perronnin, Florent
• Primary Examiner(s): STREGE, JOHN B
• Application Number:
  US13/561,655
• Publication Number:
  US 20140029839A1
• Time in Patent Office: 1,016 Days
• Field of Search: 382/159, 382/224, 382/305
• US Class Current: 382/224
• 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/24137 Distances to cluster centroïds
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/35 Categorising the entire scene, e.g. birthday party or wedding scene

Abstract

A classification system and method enable improvements to classification with nearest class mean classifiers by computing a comparison measure between a multidimensional representation of a new sample and a respective multidimensional class representation embedded into a space of lower dimensionality than that of the multidimensional representations. The embedding is performed with a projection that has been learned on labeled samples to optimize classification with respect to multidimensional class representations for classes which may be the same or different from those used subsequently for classification. Each multidimensional class representation is computed as a function of a set of multidimensional representations of labeled samples, each labeled with the respective class. A class is assigned to the new sample based on the computed comparison measures.

Claims

1. A classification method comprising:

with a processor, for a new sample to be classified, for each of a set of classes, computing a probability for each class based on a comparison measure between a multidimensional representation of the new sample and a respective multidimensional class representation, the comparison measure being computed in a space of lower dimensionality than the multidimensional representation of the new sample by embedding the multidimensional representation of the new sample and the multidimensional class representations with a projection that has been learned on labeled samples to optimize classification of the labeled samples based on the comparison measure, the comparison measure being based on an exponentially decreasing function of a distance between the embedded multidimensional representation of the sample and a respective one of the embedded multidimensional class representations, each multidimensional class representation being computed based on a set of multidimensional representations of labeled samples that are labeled with the respective class; and

assigning a class to the new sample based on the computed probabilities.

2. The method of claim 1, wherein the projection is one which optimizes an objective function which maximizes, over the labeled samples, a likelihood that a labeled sample will be classified with a correct label, the correct label having been assigned to the labeled sample from a finite set of labels for the labeled samples.

3. The method of claim 1, further comprising learning the projection.

4. The method of claim 3, wherein the learning of the projection aims to minimize the negative log-likelihood of the class labels y_iε

{1, . . . , C} of the training samples according to the objective function;

5. The method of claim 4, wherein the learning of the projection includes optimizing the objective function with stochastic gradient descent.

6. The method of claim 3, wherein the learning of the projection includes learning a subspace in which each labeled sample is closer in the subspace to its multidimensional class representation than to multidimensional class representations of other classes.

7. The method of claim 1, wherein the multidimensional representation of the new sample comprises a statistical representation of features extracted from the new sample.

8. The method of claim 7, wherein the multidimensional representation of the new sample comprises at least one of a Fisher Vector and a Bag-of-Visual-words representation.

9. The method of claim 1, wherein the assigning a class comprises computing a probability for each class based on an exponential decreasing function of a distance between the embedded multidimensional representation of the new sample and a respective embedded multidimensional class representation.

10. The method of claim 1, wherein each comparison measure comprises a distance measure.

11. The method of claim 10, wherein the assigning of the class comprises assigning a class for which the distance is a minimum.

12. The method of claim 10, wherein the computing the comparison measure comprises computing the l₂ distance.

13. The method of claim 1, wherein each multidimensional class representation is a mean of multidimensional representations of the labeled samples labeled with the respective class.

14. The method of claim 1, wherein each multidimensional class representation comprises a set of cluster centers obtained from the multidimensional representations of the samples labeled with the respective class.

15. The method of claim 14, wherein the assigning of a class comprises computing a probability for each class based on a mixture of exponentially decreasing functions of a distance between the embedded multidimensional representation of the new sample and a respective one of the embedded multidimensional class representations.

16. The method of claim 1, wherein the projection is a D×

d dimensional matrix, where D represents a number of the dimensions in the multidimensional representation and multidimensional class representations and d represents a number of the dimensions in the embedded multidimensional representation and embedded multidimensional class representations.

17. The method of claim 16, wherein d≦

0.5 D.

18. The method of claim 1, wherein for at least one of the multidimensional class representations, the set of samples used in computing the multidimensional class representation is not identical to the set of the samples labeled with that class which were used in learning the projection.

19. The method of claim 1, wherein for at least one of the classes in the set of classes, no samples labeled with that class are used in learning the projection.

20. The method of claim 1, wherein the new sample and the labeled samples each comprises an image.

21. A computer program product comprising a non-transitory recoding medium storing instructions which when executed by a computer, perform the method of claim 1.

22. A system comprising memory which stores instructions for performing the method of claim 1 and a processor in communication with the memory which implements the instructions.

23. A system comprising:

memory which stores;

a projection matrix for embedding multidimensional representations into an embedding space, the projection matrix having been learned from class-labeled samples to optimize a classification rate on the labeled samples with nearest class mean classifiers; and

a nearest class mean classifier for each of a set of classes, each of the nearest class mean classifiers in the set being computed based on multidimensional representations of samples that are labeled with the respective class;

instructions for;

computing a comparison measure between a multidimensional representation of a new sample and each of the nearest class mean classifiers, the comparison measure being computed in the embedding space in which the multidimensional representation of the new sample and the nearest class mean classifiers are embedded with the projection matrix, the comparison measure being based on an exponentially decreasing function of a distance between the embedded multidimensional representation of the new sample and a respective one of the embedded multidimensional class representations, and

outputting information based on the comparison measure; and

a processor in communication with the memory which implements the instructions.

24. The system of claim 23, further comprising a database which stores a set of the labeled samples.

25. The system of claim 23, wherein the outputting information comprises a class for the new sample corresponding to the nearest class mean classifier that the comparison measure indicates is closest to the new sample.

26. A method of generating a classification system, comprising:

providing a multidimensional representation and a class label for each of a set of training samples, each of the class labels corresponding to a respective one of a set of classes;

computing a nearest class mean classifier for each of the classes, based on the multidimensional representations of training samples labeled with that class;

with a processor, learning a projection based on the multidimensional representations, class labels, and nearest class mean classifiers which embeds the multidimensional representations and nearest class mean classifiers into an embedding space that optimizes a classification of the training samples by the set of nearest class mean classifiers in the embedding space, the learning of the projection aims to minimize the negative log-likelihood of the class labels y_iε

{1, . . . , C} of the training samples according to the objective function;

27. The method of claim 26, wherein the projection comprises a D×

d matrix, where d is a number of dimensions in the embedding space and D is a number of dimensions in each of the nearest class mean classifiers and where D is greater than d.