Probability estimate for K-nearest neighbor
View Patent ↗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.
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.