Machine Learning to Predict Class Probabilities I am looking for classifiers that output probabilties that examples belong to one of two classes.
I know of logistic regression and naive Bayes, but can you tell me of others that work in a similar way? That is, classifiers that predict not the classes to which examples belong, but the probability that examples fit to a particular class?
Bonus points for any thoughts you can share on the advantages and disadvantages of these different classifiers (including logistic regression and naive Bayes). For example, are some better for multi-class classification?
 A: SVM is closely related to logistic regression, and can be used to predict the probabilities as well based on the distance to the hyperplane (the score of each point). You do this by making score -> probability mapping some way, which is relatively easy as the problem is one-dimensional. One way is to fit an S-curve (e.g. the logistic curve, or its slope) to the data. Another way is to use isotonic regression to fit a more general cumulative distribution function to the data.
Other than SVM, you can use a suitable loss function for any method which you can fit using gradient-based methods, such as deep networks.
Predicting probabilities is not something taken into consideration these days when designing classifiers. It's an extra which distracts from the classification performance, so it's discarded. You can, however, use any binary classifier to learn a fixed set of classification probabilities (e.g. "p in [0, 1/4], or [1/4, 1/2], or ...") with the "probing" reduction of Langford and Zadrozny.
A: There are many - and what works best depends on the data. There are also many ways to cheat - for example, you can perform probability calibration on the outputs of any classifier that gives some semblance of a score (i.e.: a dot product between the weight vector and the input). The most common example of this is called Platt's scaling. 
There is also the matter of the shape of the underlying model. If you have polynomial interactions with your data, then vanilla logistic regression will not be able to model it well. But you could use a kerneled version of logistic regression so that the model fits the data better. This usually increases the "goodness" of the probability outputs since you are also improving the accuracy of the classifier. 
Generally, most models that do give probabilities are usually using a logistic function, so it can be hard to compare. It just tends to work well in practice, Bayesian networks are an alternative. Naive Bayes just makes too simplistic an assumption for its probabilities to be any good - and that is easily observed on any reasonably sized data set. 
In the end, its usually easier to increase the quality of your probability estimates by picking the model that can represent the data better. In this sense, it doesn't matter too much how you get the probabilities. If you can get 70% accuracy with logistic regression, and 98% with a SVM - then just giving a "full confidence" probability alone will make you results "better" by most scoring methods, even though they aren't really probabilities (and then you can do the calibration I mentioned before, making them actually better). 
The same question in the context of being unable to get an accurate classifier is more interesting, but I'm not sure anyones studied / compared in such a scenario.  
A: Another possibility are neural networks, if you use the cross-entropy as the cost functional with sigmoidal output units. That will provide you with the estimates you are looking for.
Neural networks, as well as logistic regression, are discriminative classifiers, meaning that they attempt to maximize the conditional distribution on the training data. Asymptotically, in the limit of infinite samples, both estimates approach the same limit.
You shall find a detailed analysis on this very question in this paper. The takeaway idea is that even though the generative model has a higher asymptotic error, it may approach this asymptotic error much faster than the discriminative model. Hence, which one to take, depends on your problem, data at hand and your particular requirements.
Last, considering the estimates of the conditional probabilities as an absolute score on which to base decisions (if that is what you are after) does not make much sense in general. What is important is to consider, given a concrete sample, the best candidates classes output by the classifier and compare the associated probabilities. If the different between the best two scores is high, it means that the classifier is very confident about his answer (not necessarily right).
