Probability estimate for K-nearest neighbor

• US 7,451,123 B2
• Filed: 12/08/2005
• Issued: 11/11/2008
• Est. Priority Date: 06/27/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John C., Burges, Christopher J. C.
• Primary Examiner(s): Vincent; David
• Assistant Examiner(s): Kennedy; Adrian L
• Application Number:
  US11/296,919
• Publication Number:
  US 20060112042A1
• Time in Patent Office: 1,069 Days
• Field of Search: 706/20, 706/25, 706/48, 382/186, 382/187
• 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 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 via receiving feature vectors of objects to be classified;

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 via outputting a classifier output vector and transforming distances between respective points of the first set and second set of training data, wherein transforming comprises a kernel function for taking an exponential of a negative of a scaled Euclidean distance between respective points of the first set and the second set to produce an associated Gaussian similarity measure;

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, the K nearest neighbor classifier outputs indicate;

a distance of an input to K nearest points, classes of the K nearest points, and identities of the K nearest points, wherein the parameters are trained via a second training set disjoint from a first training set used to train the K nearest neighbor classifier;

converting the computed classifier outputs to probabilistic outputs using a probability model, wherein the probability model is built with the classifier outputs and trained via processing various inputs and outputs so as to provide probabilistic outputs from within acceptable error thresholds;

employing the probabilistic outputs for recognition of at least one of;

handwriting samples;

medical images;

faces;

fingerprints;

signals;

automatic control phenomena;

natural phenomena; and

nucleotide sequences; and

employing a class of the K nearest neighbor classifier outputs to determine a class of the first subset of training data, 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.

2. 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′

=Ε

[y|x], where Ε

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

3. The method of claim 2, 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 Ε

[y|x] and then minimizing the expectation of the loss function over a marginal distribution p(x).

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

5. 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.

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

7. The method of claim 5, 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.

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

9. 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.

10. 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, the K nearest neighbor classifier outputs indicate;

a distance of an input to K nearest points, classes of the K nearest points, and identities of the K nearest points, wherein the parameters are trained via a second training set disjoint from a first training set used to train the K nearest neighbor classifier;

converting the computed classifier outputs to probabilistic outputs using a probability model, wherein the probability model is built with the classifier outputs and trained via processing various inputs and outputs so as to provide probabilistic outputs from within acceptable error thresholds; and

employing the probabilistic outputs for recognition of at least one of;

handwriting samples;

medical images;

faces;

fingerprints;

signals;

automatic control phenomena;

natural phenomena; and

nucleotide sequences.

11. A system for performing handwriting recognition employing the method of claim 10.

12. A computer readable medium storing computer executable instructions for performing the method of claim 10.