  We develop a scoring and classification procedure based on the PAC-Bayesian
approach and the AUC (Area Under Curve) criterion. We focus initially on the
class of linear score functions. We derive PAC-Bayesian non-asymptotic bounds
for two types of prior for the score parameters: a Gaussian prior, and a
spike-and-slab prior; the latter makes it possible to perform feature
selection. One important advantage of our approach is that it is amenable to
powerful Bayesian computational tools. We derive in particular a Sequential
Monte Carlo algorithm, as an efficient method which may be used as a gold
standard, and an Expectation-Propagation algorithm, as a much faster but
approximate method. We also extend our method to a class of non-linear score
functions, essentially leading to a nonparametric procedure, by considering a
Gaussian process prior.
