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?
 A: 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.
A: 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.
A: 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.
