Training a classifier by dimension-wise embedding of training data
View Patent ↗A classifier training method and apparatus for training, a linear classifier trained by the method, and its use, are disclosed. In training the linear classifier, signatures for a set of training samples, such as images, in the form of multi-dimension vectors in a first multi-dimensional space, are converted to a second multi-dimension space, of the same or higher dimensionality than the first multi-dimension space, by applying a set of embedding functions, one for each dimension of the vector space. A linear classifier is trained in the second multi-dimension space. The linear classifier can approximate the accuracy of a non-linear classifier in the original space when predicting labels for new samples, but with lower computation cost in the learning phase.
1. A classifier training method comprising:
providing a set of training samples each training sample comprising a training vector in a first multi-dimension space representative of an object and a class label for the object;
for at least a subset of the training samples, deriving a set of embedding functions for embedding training vectors that are in the first multi-dimension space into a second multi-dimension space of higher dimensionality than the first multi-dimension space, the embedding functions comprising one embedding function for each dimension of the first multi-dimension space;
with the embedding functions, generating a set of embedded vectors in the second multi-dimension space corresponding to the training vectors;
with a computer processor, training a linear classifier on the set of embedded training vectors and their class labels to generate a trained linear classifier operative in the second multi-dimension space for predicting labels for unlabeled sample vectors.
2. The method of claim 1 , wherein each embedding function is selected such that for each dimension of the first multi-dimension space, similarity between two training sample vectors in said dimension is approximated as a dot product of respective embedding functions of the training sample vectors which embed said dimension in the second multi-dimension space.
3. The method of claim 1 , wherein the second multi-dimension space is of higher dimensionality than the first multi-dimension space.
4. The method of claim 1 , wherein in deriving a set of embedding functions, in each dimension d, an embedding function φ d that maps a scalar value x[d] of a training vector x into a new space with E dimensions is learnt, φ d being selected such that in this new space, the dot product between φ d (x i [d]) and φ d (x j [d]), approximates the kernel w(x i [d],x j [d])where x i [d] represents a value of a first vector in dimension d and x j [d] represents a value of a second vector in dimension d in the first multi-dimension space.
5. The method of claim 1 , wherein each training vector is derived from an object selected from the group consisting of an image, a video, a text object, an audio object and combinations and multiples thereof.
6. The method of claim 1 , wherein the generating of the set of embedded vectors comprises for each training vector, concatenating a computed value for each dimension in the second multi-dimension space.
7. The method of claim 1 , wherein each embedding function converts a scalar value for a respective dimension of a sample vector in the first multi-dimension space into a vector having at least one dimension.
8. The method of claim 7 , wherein at least some of the embedding functions convert a scalar value for a respective dimension of a sample vector in the first multi-dimension space into a vector having a plurality of dimensions.
9. The method of claim 1 , wherein the deriving of the embedding functions includes eigenvalue decomposition.
10. The method of claim 1 , wherein the trained linear classifier operative in the second multi-dimension space corresponds to a non-linear classifier in the first dimensional space.
11. The method of claim 1 , further comprising predicting a label for an unlabeled sample vector with the trained classifier, including embedding the unlabeled sample vector in the second multi-dimension space.
12. The method of claim 1 , wherein a Nyström approximation is used to embed samples to be labeled by the classifier in the second multi-dimension space.
13. The method of claim 1 , wherein the deriving a set of embedding functions includes partitioning the dimensions of the first multi-dimension space into a set of bins and computing an embedding function for each bin.
14. The method of claim 1 , wherein the first multi-dimension space comprises at least fifty dimensions.
15. The method of claim 1 , further comprising generating each of the training vectors in the first multi-dimension space by extracting features from an object and deriving the training vector from the extracted features.
16. The method of claim 1 , wherein the number of dimensions in the first multi-dimension space is represented by D and the number of dimensions in the second multi-dimension space is represented by ED.
17. The method of claim 16 , further comprising selecting a value of E which optimizes accuracy of the classifier according to an assessment metric.
18. The method of claim 16 , wherein E is at least 2.
19. The method of claim 16 , wherein E is up to 20.
20. The method as set forth in claim 1 , further comprising:
generating the set of training vectors and the sample vector from images.
21. A computer program product encoding instructions, which when executed on a computer causes the computer to perform the method of claim 1 .
22. A classification system comprising memory which stores a linear classifier formed by the method of claim 1 and a processor, in communication with the memory, which executes instructions for inputting samples to be classified into the classifier.
23. An apparatus for approximating a non-linear classifier in a first multi-dimension space by training a linear classifier in a second multi-dimension space, the apparatus comprising:
memory which stores instructions which:
for at least a subset of an input set of training samples, each training sample in the set comprising a training vector in the first multi-dimension space and a class label, derive a set of embedding functions for embedding each of the training vectors that are in the first multi-dimension space into the second multi-dimension space, the embedding functions comprising one embedding function per dimension of the first multi-dimension space,
with the embedding functions, generate a set of embedded vectors in the second multi-dimension space corresponding to the training vectors, and
train a linear classifier on the set of embedded training vectors and their class labels to generate a trained linear classifier operative in the second multi-dimension space for predicting labels for unlabeled test sample vectors; and
a processor in communication with the memory for executing the instructions.
24. The apparatus of claim 23 , further comprising:
instructions for converting a test sample vector in the first multi-dimension space to a vector in the second multi-dimension space without using the embedding functions.
25. A classification apparatus comprising:
memory which stores a linear classifier configured for classifying a test sample vector input in a first multi-dimension space, the classifier operating in a second multi-dimension space of the same or higher dimensionality than the first multi-dimension space;
instructions for embedding an input test sample vector into the second multi-dimension space and for classifying the embedded vector with the linear classifier, the embedding instructions including:
for each of D dimensions of the first multi-dimension space, generating an E dimensional vector, and
concatenating the E dimensional vectors to form a DE dimensional vector, where D is at least 50 and E is at least 1; and
a processor in communication with the memory for executing the instructions.
26. The apparatus of claim 25 , wherein the embedding instructions include instructions for applying a Nyström approximation to embed the test sample vectors to be labeled by the classifier in the second multi-dimension space.