You can estimate the empirical out-of-sample error of your classifier (model fitted using the data) and if consistently better than chance then it's a certificate that your classifier has good generalisation properties. You can asses the generalisation using the VC theory, cross-validation or the through the evidence p(D) .

http://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory

http://en.wikipedia.org/wiki/Cross-validation_(statistics)

You can compute the AUC-ROC and AUC-PR

In fact, random guessing is just another classifier. So the general question is how to show that two classifiers differ in performance. You did not specify what you mean by random guessing (non uniform priors...), and no cost function for misclassifications. If using resampling or cross validation techniques, it remains to specify, whether the respective model's parameters are readusted on each stratum or else one fixed set of model parameters is evaluated on random subsets. If small sample properties could matter, the latter can be misleading.

What do you mean under "classes are different"? Do you mean that different classes should have different probabilistic origin, i.e. data of two classes should be generated by two random variables? Or maybe data shoud occupy some special area, like it is when you use geometrical classifier like Support Vector Machine?

I think one issue is what sort of performance measurement you choose for representing the ability of your classifiers to distinguish different classes from each other. There are some studies indicating that bookmaker informedness (introduced by Prof. David M.W. Powers) is a better measurement unit than accuracy, recall, precision, and so on. Bookmaker Informedness is chance corrected probability of informed decision with value between -1 and +1 where 0 represents chance level and 1 perfect performance. The sign indicates whether the information is being used correctly or incorrectly (perversely).

Now, going back to your question, if you are looking at averaged accuracy (assuming that you are using a cross validation scheme) as your performance measurement unit, and also assuming that you only have 2 different classes in your data, anything above 50% would be better than chance by 50% representing the chance level which is what you expect to get when you do a random guessing. if you choose to use Bookmaker Informedness 0 would represent the chance level and anything above it shows that your classifier is working better than chance.

Another issue in here is about the cross-validation (CV). There are some studies indicating that there is a high variation within the performance that you achieve for different folds in CV and the average performance that you get from your CV is tend to have a bias toward upper boundaries of possible performance. Efron proposed 0.632+ bootstrap for a solution but some other studies showed that this solution tend to have a bias toward lower boundaries. It seems that a combination of CV and 0.632+ bootstrap is the scheme that tend to have low variability across folds and no bias toward upper or lower boundaries this is with understanding of the extra computational load required for the method.

Thank you for your answers. The responses to my questions, so far, have particularly dealt with ways to calculate performance measures of a classifier. I am thankful for you answers but they do not fully address my question. The measures, like CV accuracy or AUC are random variables. Each time, I "draw" a training set, I draw a value from this random variable. A chance classifier will, for a given training set, not always yield an estimated accuracy of 50% but might sometimes do a little better. This is why the belief "anything above 50% would be better than chance by 50% representing the chance level " is especially dangerous. Your random guesser might just have had a lucky day. This is why it is necessary to base our decisions on a statistical test. I wonder what tests in conjunction with what performance measures you employ to evaluate your classifiers.

As I said, random classifier is just another classifier. If performing CV, this and your-classifier-of-choice will both yield distributions of accuracy, precision etc.

These distributions may be tested with e.g. Kolmogorov-Smirnov for equality

I agree with Matthias, assuming that you do a 10 times 10 CV on your data using your classifier. this will give you 100 measurements on performance of your classifier. now you can draw 100 random guesses. As you said, some of them might happen to be better than 50% but some of them might also be worse. you have to assess the performance of your classifier based on the average results and on average your random classifier would perform close to 50%. As Matthias said, you can apply statistical test such as One-Way Anova or Kolmogorov-Smirnov to prove the existence of significant difference among your random guessing and your chosen classifier. If your classifier is performing better or worse than chance (random guessing) you can expect to get a p value less than 0.05.

At the most basic level, if you have a 'Gold Standard' you might do well with Cohen's kappa (for 2 x 2 tables) and Fleiss' otherwise (not the same thing, although both very informative).

Hope that this might help.

Jon, you suggest using a measure of inter-rater reliability. That sounds interesting. Again, is there a statistical test to determine whether this congruency between two raters formalized as kappa is significantly different from zero? Why should I prefer kappa over any other test statistic?

A simple idea: you could compare the actual gessing (obtained with your algorithm) with the one obtained from randomly picking the observations in the two classes. The random test can be performed a large number of times, because it is very fas!. You can thus build up the histogram of a quality parameter (say proportion of observations correctly identified) in many random test. You will be able to place the result of your algorithm on this histogram of random allocations. From this, you can have a certain idea on the performance of your algorithm. Of course, in the random tests, you must respect the true proportions of the observed classes.

The advantage of this idea is that you can easly cope with some constraints of the quality parameter you have chosen.

Still, I'd like to move the discussion to statistical evaluation of classifiers. After all, any score, whether its AUC (as suggested by Nicola), its a histogram overlap (if I understand Dominique correctly), or a inter-rater reliability (as suggested by Jon), or CV estimates of accuracy (as suggested by Matthias and Adham), is a random variable that we draw values from each time we estimate the score.

What is your experience and/or opinion on using t-test, ANOVA, Friedman test, Wilcoxon, or others to compare classifier performance?

as an example: when classifying binary responses after running a logistic regression, the area under the ROC curve bigger than 0.5 means that predictions are better than random guessing

Yes ROC better represent the performance of the classification. For more realistic reflection of the performance of classification model you can compute Negative Predictive Values and Positive Predictive Values for a binary classification.

Reagrding ROC: The problem with ROC is, that the usual statistical machinery does not hit -- which was Andreas' initial concern.

Nevertheless, ROC is meaningful if the problem is not symmetric (minor and major class), or cost of error is not known, as initially discussed in:

Provost et al., 1998 'The case against Accuracy esyimation for Comparing Induction Algorithms'

I think that what you are looking for, for any performance metric, is to compare vs the Zero classifier. This is not uniformly random, but a classifier which predicts all test records as belonging to the majority class value in the training set. Thus, if in a training set you have more negative records than positive, and your test set has 98 negative records and 2 positive, the Zero classifier will acheive a 98% accuracy, but of course the precision and AUC for the positive class will be prohibitive. A unirform random classifier might perform better than a Zero classifier. Thus, the baseline classifier versus which to compare other models is the Zero classifier.

Hi Andreas,

I am confused on a similar issue. What test did you use to compare classifier performance with baseline accuracy over cross-validation rounds?

Even though this seems to be an old post my response might be relevant to others. I would refer you to the paper of Janez Demsar “Statistical Comparisons of Classifiers over Multiple Data Sets" JMLR, Journal of Machine Learning Research, 2006:

http://www.jmlr.org/papers/volume7/demsar06a/demsar06a.pdf

In summary, the author evaluates a number of statistical tests to compare classification algorithms’ performance. Base of the results, the author recommends two parametric statistical tests: the Wilcoxon sighed ranks test (for comparing two classifiers) and the Friedman test (for comparing more than two classifiers) over multiple data sets.