Probability estimate for K-nearest neighbor

• US 7,016,884 B2
• Filed: 06/27/2002
• Issued: 03/21/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.
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Datskovskiy, Sergey
• Application Number:
  US10/183,213
• Publication Number:
  US 20040002931A1
• Time in Patent Office: 1,363 Days
• Field of Search: 706/46, 706/20, 706/15, 706/27
• 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 pattern recognition system comprising:

a classifier that receives pattern-related indicia and classifies the indicia by determining distances of K nearest neighbors; and

a trained probability transducer that calculates posterior probabilities of classes based on the distances of the K nearest neighbor outputs of the classifier.

2. The system of claim 1, the pattern related indicia comprising scanned images of handwriting.

3. The system of claim 1, the pattern related indicia comprising medical images.

4. The system of claim 1, the pattern related indicia comprising audio data.

5. The system of claim 1, the outputs being ranked.

6. The system of claim 1, the outputs comprising a class and distance.

7. The system of claim 6, the classifier comprising a kernel function that computes the distance.

8. The system of claim 1, the outputs comprising an index into a stored database of examples, a class, and a distance.

9. The system of claim 8, the classifier comprising a kernel function that computes the distance.

10. The system of claim 1, the trained probability transducer comprising a softmax component.

11. The system of claim 10, the trained probability transducer further comprising a trained parametric model.

12. The system of claim 11, the trained parametric model comprising a plurality of rank-class computations.

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

14. The system of claim 12, the rank-class computations comprising a lookup table, wherein the index into the lookup table depends on a class output produced by the classifier and a second class.

15. The system of claim 12, the rank-class computations comprising a lookup table, wherein the index into the lookup table depends on an index output produced by the classifier.

16. The system of claim 11, the trained parametric model comprising learned partial stun initializations.

17. The system of claim 11, the trained parametric model comprising one parameter per rank.

18. The system of claim 11, the trained parametric model comprising one lookup table per rank.

19. The system of claim 11, the trained parametric model comprising a lookup table, the lookup table containing one entry for each example in a training set.

20. A computer-implemented method that generates posterior probabilities comprising:

computing a non-probabilistic classifier output for a data point, the non-probabilistic classifier output comprising a ranked vector of K nearest neighbor outputs; and

computing probabilistic outputs for the data point from the ranked vector of K nearest neighbor outputs utilizing a trained parametric model.

21. The method of claim 20, the probabilistic outputs comprising a probability and class for the given data point.

22. A computer-implemented classification system comprising:

means for computing a non-probabilistic classifier output for at least one data point, the non-probabilistic classifier output comprising a ranked vector of K nearest neighbor outputs; and

means for computing probabilistic outputs for the at least one data point from the ranked vector of K nearest neighbor outputs utilizing a trained parametric model.