Prediction uncertainty estimates for different kinds of models For which kinds of supervised machine learning techniques is it possible to estimate how uncertain the model is about its predictions for given level/range of the predictor once the model is trained on a set of data?
I can imagine that it is possible to do that e.g. for random forest by looking at the variance of votes that the forest is giving for a data point in the evaluation dataset. On the other hand it seems for me impossible to estimate model uncertainty for linear regression and similar methods.
Could anyone explain for which machine learning techniques this can be done or point me to the relevant literature?
 A: Many models can actually provide you with the uncertainty measure, first of all:


*

*Naive Bayes directly models the P(y|x) probability, which is exactly what you are asking for

*Support Vector Machine defines a hyperplane, a distance to this hyperplane is a certainty measure (closer the point, less certain is the model). In libraries like python sklearn you can access it by looking for the difference between decision_function(x) value and the intercept parameter

*Multilayer Neural Network if you train a network for the M-classes classification task with the M-output neurons network (and the expected output for the element of first class is 1 0 0 ..., for the second 0 1 0 ... and so on), the output neurons' values can be used as a certainty measure (0 0.7 0 ... can be interpreted as "quite a member of second class), but of course some more interesting measures can be used here (like e.g. Kullback–Leibler divergence)

A: The "delta method" is textbook.  Things like Neural Networks, which resolve into analytic expressions and are most efficiently trained using gradient approximators.  It is applicable to methods with an analytic form whose derivatives exist including linear, polynomial, GLM (generalized linear models), GMM (gaussian mixture models).  
Bootstrap resampling, one of the fundamentals behind random forests, works in a large number of other areas and is considered an ensemble method.  (Personally I feel like it could be abused, and one has to be able to defend the use of a uniform random distribution as a non-informative prior, or one has to be able to use some variation on Metropolis-Hastings.)
A: One way to assess the quality of your model is using k-fold cross validation. The idea is to split your training data into (say k=10) 10 parts, train on 9/10 of the training data and predict 1/10 of the data. This way you can get an indication of the quality of your model. You can also combine this with trying out different "tuning" parameters, to find the optimum settings given a training data-set.
Another way is using a machine-learning algorithm which is interpretable, i.e. each feature is given a weight. This enables you to observe which features are important and which are not and make a decision based on your prior information about the problem. Linear SVM and Adaboost are both interpretable
