Probability estimate for K-nearest neighbor

• US 20060112042A1
• Filed: 12/08/2005
• Published: 05/25/2006
• Est. Priority Date: 06/27/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John C., Burges, Christopher J.C.
• Granted Patent: US 7,451,123 B2
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

Systems and methods are disclosed that facilitate producing probabilistic outputs also referred to as posterior probabilities. The probabilistic outputs include an estimate of classification strength. The present invention intercepts non-probabilistic classifier output and applies a set of kernel models based on a softmax function to derive the desired probabilistic outputs. Such probabilistic outputs can be employed with handwriting recognition where the probability of a handwriting sample classification is combined with language models to make better classification decisions.

Claims

1. A method of training a K nearest neighbor classifier, comprising:

obtaining a set of data comprising a first subset of training data and a second subset of training data;

training the K nearest neighbor classifier on the first subset of training data;

sequentially processing the second subset of training data to compute K nearest neighbor classifier outputs for respective points of the second set of training data; and

determining parameters for a parametric model according to the K nearest neighbor classifier outputs, and true outputs of respective points of the second set of training data.

2. The method of claim 1, further comprising employing a class of the K nearest neighbor classifier outputs to determine a class of the first subset of training data.

3. The method of claim 2, the K nearest neighbor classifier outputs indicate at least one of:

a distance of an input to K nearest points, classes of the K nearest points, and identities of the K nearest points.

4. The method of claim 1, training the K nearest neighbor classifier comprises receiving feature vectors of objects to be classified.

5. The method of claim 1, sequentially processing comprises outputting a classifier output vector.

6. The method of claim 1, sequentially processing comprising transforming distances between respective points of the first set and second set of training data.

7. The method of claim 6, transforming comprises a kernel function for taking an exponential of a negative of a scaled Euclidean distance between respective points of the first se and the second set to produce an associated Gaussian similarity measure.

8. The method of claim 1, the training of the K nearest neighbor classifier comprises training with an error metric that is P-admissible in accordance with a P-admissible loss function L(y,y′

) which, for any given x, is minimized at y′

=E[y|x], where E[y|x] denotes the expectation of y for a fixed, given value of x.

9. The method of claim 8, for a case of a single classifier output, minimizing an expectation of a P-admissible loss function over a joint distribution of x and y by replacing y by E[y|x] and then minimizing the expectation of the loss function over a marginal distribution p(x).

10. The method of claim 1, further comprising converting the computed classifier outputs to probabilistic outputs using a probability model.

11. The method of claim 10, further comprising employing the probabilistic outputs employed for recognition of at least one of:

handwriting samples;

medical images;

faces;

fingerprints;

signals;

automatic control phenomena;

natural phenomena; and

nucleotide sequences.

12. The method of claim 1, training the K nearest neighbor classifier comprising a softmax function.

13. The method of claim 1, training the K nearest neighbor classifier is performed in accordance with a trained parametric model for performing a plurality of rank-class computations.

14. The method of claim 13, the rank-class computations comprising a comparison between a class output produced by a classifier and a second class.

15. The method of claim 13, performing the rank-class computations comprises utilizing a lookup table having an index dependent on a class output produced by the classifier and the second class.

16. The method of claim 13, performing the rank-class computations comprises utilizing a lookup table having an index dependent on an index output produced by the classifier.

17. The method of claim 1, training the K nearest neighbor classifier using a trained parametric model comprising one lookup table per rank, the lookup table containing one entry for each example in a training set.

18. A computer-implemented method of training a K nearest neighbor classifier, comprising:

obtaining a set of data comprising a first subset of training data and a second subset of training data;

training the K nearest neighbor classifier on the first subset of training data;

sequentially processing the second subset of training data to compute K nearest neighbor classifier outputs for respective points of the second set of training data; and

determining parameters for a parametric model according to the K nearest neighbor classifier outputs, and true outputs of respective points of the second set of training data.

19. A system for performing handwriting recognition employing the method of claim 18.

20. A computer readable medium storing computer executable instructions for performing the method of claim 18.