Probability estimate for K-nearest neighbor
AssigneeMicrosoft Corporation
InventorsJohn C. Platt, Christopher J.C. Burges
Life of this patent
Estimating the term…
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.
Claims25
A pattern recognition system comprising:
- a classifier that receives pattern-related indicia and classifies the indicia employing a K nearest neighbor approach;
- and
- a trained probability transducer that calculates posterior probabilities of classes based on outputs of the classifier.
A 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 outputs;
- and
- computing probabilistic outputs for the data point from the ranked vector of outputs utilizing a trained parametric model.
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.
A 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 outputs;
- and
- means for computing probabilistic outputs for the at least one data point from the ranked vector of outputs utilizing a trained parametric model.
Dependencies are inferred from the claim text.