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 Datasensitive 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. Permission to make digitnl/hnrd copies ofnll or part ofthis mntcl-inl fol personal or clw.mnm use is gr:u’ted withaut I kc pwvidcd 11~1 lhc oop~s are 1101 made or distrihutrd For profit or comnwx~l advnm~gr. the copy right notice, the title of the puhlwxtion and its dnie appear. and n&t: is given that copyright is hy psmksion of~hr .Ac’M. lnc To copy othmvisc to republish. IO post on servers or to rrdistrilwtr 10 lists. rquires ~pcxilic pemission m&or fee COLT 97 Nashville. Tennesee. USA Copyright 1997 ACM O-89791~891~6197i7..%3.50 Robert C. Williamson Dept of Engineering Australian National University Canberra 0200 Australia Bob.WilliamsonQanu.edu.au