classifiers providing probability of being correct

The way I understand classifiers like kNN, ANN, SVM, Decision Trees... is that after being trained they will associate a new test object to one class out of a set of predefined classes.

My question is whether there are classifiers, or extensions to the once mentioned above where objects are not only classified, but also a certain confidence level (probability of being correct) is provided. So something like $x$ belong to class $C_i$ with probability $0.8$.
I was especially hoping for something in connection with SVM, maybe based on the distance to the margin?

• For SVM, LIBSVM provides an option for generating probability estimates. Visit csie.ntu.edu.tw/~cjlin/libsvmtools. Then, find on page the keyword "probability". – soufanom Jan 23 '13 at 3:44
• Please note that "Probability of being correct" is not what any method will give you unless your willing to accept a tail of conditions/assumptions. This is very important to consider. – Momo Jan 23 '13 at 23:21

For the SVM algorthm you can look at that paper "Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods" and others works derived by this one. The algorithm is implemented also in the libsvm library.

I disagree with the fact that the distance from the margin proportional probability is a good estimator, because an example could be distant from the margin and at the same time distant from the class distribution.

• Also, check out kernel logistic regression and gaussian process classification for some probabilistic kernel-based classifiers. – Stumpy Joe Pete Jan 23 '13 at 22:33

Yes, there are many techniques which produce probabilities of membership.

One class of techniques is generative techniques. Instead of estimating membership given data, these estimate probability densities for each class, as well as a probability distribution on classes. For example, a Gaussian mixture model may assume that each class is a Gaussian distribution with some mean and covariance. From such a generative model, you can determine the membership probabilities in each class by a proportion $p(i) = w_i d_i / \sum_j w_j d_j$ where $w_i$ represents the weight of class $i$ and $d_i$ represents the density of the modeled distribution for class $i$ at the input.

Logistic regression and neural networks with a logistic or softmax output also estimate probabilities of membership.

• However you should make a strong assumption that each class is distributed according to a well defined distribution, e.g. a Gaussian. – shn Jan 24 '13 at 0:50

I agree with robbisg, distance to the margin is a poor predictor of probability.

Scikit-Learn implements probability estimates for SVM by averaging 5-fold CV. This is a nice general strategy.

With all probability estimators of classification you should study the receiver operating characteristic. Scalar classification metrics are notorious for masking how the algorithm is actually performing. This may lead you to consider weighting unbalanced data or calibrating probability estimates with logit.