A PAC analysis of a Bayesian estimator

Bayesian analysis of generalisation can place a prior distribution on the hypotheses and estimate the volume of this space that is consistent with the training data. The larger this volume the greater the confidence in the classifier obtained. The key feature of such estimators is that they provide a posteriori estimates of generalisation based on properties of the hypothesis and the training data. This contrasts with a `classical PAC analysis which provides only a priori (worst case) bounds. Following results in 26 showing that Data-sensitive analysis of generalisation in the PAC sense is possible, the paper uses the techniques to give the first PAC style analysis of a Bayesian inspired estimator of generalisation. The estimator concerned is the size of a ball which can be placed in the consistent region of parameter space. The ball gives a lower bound on the volume of parameter space consistent with the training set. The larger the ball the better the bound on the generalisation obtained. In all cases the bounds are of good generalisation with high confidence, hence bounding the tail of the distribution of generalisation errors that might occur. The resulting bounds are independent of the complexity of the function class though they depend linearly on the dimensionality of the parameter space. 1