PAC-Bayesian Stochastic Model Selection.
PAC-Bayesian learning methods combine the informative priors of Bayesian methods with distribution-free PAC guarantees. Stochastic model selection predicts a class label by stochastically sampling a classifier according to a posterior distribution on classifiers. This paper gives a PAC-Bayesian performance guarantee for stochastic model selection that is superior to analogous guarantees for deterministic model selection. The guarantee is stated in terms of the training error of the stochastic classifier and the KL-divergence of the posterior from the prior. It is shown that the posterior optimizing the performance guarantee is a Gibbs distribution. Simpler posterior distributions are also derived that have nearly optimal performance guarantees.
INTRODUCTION
A PAC-Bayesian approach to machine learning attempts to combine the
advantages of both PAC and Bayesian approaches [20, 15]. The Bayesian
approach has the advantage of using arbitrary domain knowledge in the
form of a Bayesian prior. The PAC approach has the advantage that one
can prove guarantees for generalization error without assuming the truth of
the prior. A PAC-Bayesian approach bases the bias of the learning algorithm
on an arbitrary prior distribution, thus allowing the incorporation of domain
knowledge, and yet provides a guarantee on generalization error that is
independent of any truth of the prior.
PAC-Bayesian approaches are related to structural risk minimization
(SRM) [11]. Here we interpret this broadly as describing any learning algorithm
optimizing a tradeoff between the "complexity", "structure", or "prior
probability" of the concept or model and the "goodness of fit", "description
length", or "likelihood" of the training data. Under this interpretation of
SRM, Bayesian algorithms that select a concept of maximum posterior probability
(MAP algorithms) are viewed as a kind of SRM algorithm. Various
approaches to SRM are compared both theoretically and experimentally by
Kearns et al. in [11]. They give experimental evidence that Bayesian and
MDL algorithms tend to over fit in experimental settings where the Bayesian
assumptions fail. A PAC-Bayesian approach uses a prior distribution analogous
to that used in MAP or MDL but provides a theoretical guarantee
against over fitting independent of the truth of the prior.
Perhaps the simplest example of a PAC-Bayesian theorem is noted in
[15]. Consider a countable class of concepts f 1 , f 2 , f 3 each concept
f i is a mapping from a set X to the two-valued set f0; 1g. Let P be an
arbitrary "prior" probability distribution on these functions. Let D be any
probability distribution on pairs hx; yi with x 2 X and y 2 f0; 1g. We do
not assume any relation between P and D. Define ffl(f i ) to be the error rate
of f i , i.e., the probability over selecting hx; yi according to D that f i (x) 6= y.
Let S be a sample of m pairs drawn independently according to D and define
to be the fraction of pairs hx; yi in S for which f i (x) 6= y. Here "ffl(f i ) is
a measure of how well f i fits the training data and log 1
can be viewed as
the "description length" of the concept f i . It is noted in [15] that a simple
combination of Chernoff and union bounds yields that with probability at
least the choice of the sample S we have the following for all f i .
s
2m (1)
This inequality justifies a concept selection algorithm which selects f   to be
the f i minimizing the description-length vs. goodness-of-fit tradeoff in the
right hand side. If there happens to be a low-description-length concept that
fits well, the algorithm will perform well. If, however, all simple concepts fit
poorly, the performance guarantee is poor. So in practice the probabilities
should be arranged so that concepts which are a-priori viewed as likely
to fit well are given high probability. Domain specific knowledge can be used
in selecting the distribution P . This is precisely the sense in which P is
analogous to a Bayesian prior - a concept f i that is likely to fit well should
be given high "prior probability" P (f i ). Note, however, that the inequality
(1) holds independent of any assumption about the relation between the
distributions P and D.
Formula (1) is for model selection - algorithms that select a single
model or concept. However, model selection is inferior to model averaging
in certain applications. For example, in statistical language modeling for
speech recognition one "smoothes" a trigram model with a bigram model
and smoothes the bigram model with a unigram model. This smoothing is
essential for minimizing the cross entropy between, say, the model and a test
corpus of newspaper sentences. It turns out that smoothing in statistical
language modeling is more naturally formulated as model averaging than as
model selection. A smoothed language model is very large - it contains
a full trigram model, a full bigram model and a full unigram model as
parts. If one uses MDL to select the structure of a language model, selecting
model parameters with maximum likelihood, the resulting structure is much
smaller than that of a smoothed trigram model. Furthermore, the MDL
model performs quite badly. A smoothed trigram model can be theoretically
derived as a compact representation of a Bayesian mixture of an exponential
number of (smaller) suffix tree models [18].
Model averaging can also be applied to decision trees that produce probabilities
at their leaves rather than hard classifications. A common method
of constructing decision trees is to first build an overly large tree which
over fits the training data and then prune the tree in some way so as to
get a smaller tree that does not over fit the data [19, 10]. For trees with
probabilities at leaves, an alternative is to construct a weighted mixture of
the subtrees of the original over fit tree. It is possible to construct a concise
representation of a weighting over exponentially many different subtrees
[3, 17, 9].
This paper is about stochastic model selection - algorithms that stochastically
select a model according to a "posterior distribution" on the models.
Stochastic model selection seems intermediate between model selection and
model averaging - like model averaging it is based on a posterior distribution
over models but it uses that distribution differently. Model averaging
deterministically picks the value favored by a majority of models as
weighted by the posterior. Stochastic model selection stochastically picks a
single model according to the posterior distribution. The first main result of
this paper is a bound on the performance of stochastic model selection that
improves on (1) - stochastic model selection can be given better guarantees
than deterministic model selection. Intuitively, model averaging should
perform even better than stochastic model selection. But proving a PAC
guarantee for model averaging superior to the PAC guarantees given here
for stochastic model selection remains an open problem.
This paper also investigates the nature of the posterior distribution providing
the best performance guarantee for stochastic model selection. It is
shown that the optimal posterior is a Gibbs distribution. However, it is
also shown that simpler posterior distributions are nearly optimal. Section
gives statements of the main results of this paper. Section 3 relates these
results to previous work. The remaining sections present proofs.
2 Summary of the Main Results
Formula (1) applies to a countable class of concepts. It turns out that the
guarantees on stochastic model selection hold for continuous classes as well,
e.g., concepts with real-valued parameters. Here we assume a prior probability
measure P on a possibly uncountable (continuous) concept class C and
a sampling distribution D on a possibly uncountable set of instances X . We
also assume a measurable loss function l such that for any concept c and instance
x we have l(c; x) 2 [0; 1]. For example, we might have that concepts
are predicates on instances and there is a target concept c t such that l(c; x)
is We define l(c) to be the expectation
over sampling an instance x of l(c; x), i.e., E xD l(c; x). We let S range over
samples of m instances each drawn independently according to distribution
D. We define " l(c; S) to be 1
x2S l(c; x). If Q is a probability measure
on concepts then l(Q) denotes E cQ l(c) and " l(Q; S) denotes
The notation 8 signifies that the probability over the generation of
the sample S of \Phi(S) is at least 1 \Gamma ffi . For countable concept classes formula
(1) generalizes as follows to any loss function l with
Lemma 1 (McAllester98) For any probability distribution P on a countable
rule class C we have the following.
8
s
As discussed in the introduction, this leads to a learning algorithm that
selects the concept c   minimizing the SRM tradeoff in the right hand side
of the inequality. The first main result of this paper is a generalization of
(1) to a uniform statement over distributions on an arbitrary concept class.
The new bound involves the Kullback-Leibler divergence, denoted D(QjjP ),
from distribution Q to distribution P . The quantity D(QjjP ) is defined to
be
dP (c)
. The following is the first main result of this paper and is
proved in section 4.
Theorem 1 For any probability distribution (measure) on a possibly uncountable
set C and any measurable loss function l we have the following
where Q ranges over all distributions (measures) on C.
8
s
Note that the definition of l(Q), namely E cQ l(c), is the average loss
of a stochastic model selection algorithm that makes a prediction by first
selecting c according to distribution Q. So we can interpret theorem 1 as a
bound on the loss of a stochastic model selection algorithm using posterior Q.
In the case of a countable concept class where Q is concentrated on the single
concept c the quantity D(QjjP ) equals
(c) and, for large m, theorem 1
is essentially the same as lemma 1. But theorem 1 is considerably stronger
than lemma 1 in that it handles the case of uncountable (continuous) concept
classes. Even for countable classes theorem 1 can lead to a better guarantee
than lemma 1 if the posterior Q is spread over exponentially many different
models having similar empirical error rates. This might occur, for example,
in mixtures of decision trees as constructed in [3, 17, 9].
The second main result of this paper is that the posterior distribution
minimizing the error rate bound given in theorem 1 is a Gibbs distribution.
For any value of fi  0 we define Q fi to be the posterior distribution defined
as follows where Z is a normalizing constant.
Z
For any posterior distribution Q define B(Q) as follows.
s
The second main result of the paper is the following.
Theorem 2 If C is finite then there exists fi  0 such that Q fi is optimal,
i.e., B(Q fi )  B(Q) for all Q, and where fi satisfies the following.
Unfortunately, there can be multiple local minima in B(Q fi ) as a function
of fi and even multiple local minima satisfying (2). Fortunately, simpler
posterior distributions achieve nearly optimal performance. To simplify the
discussion we consider parameterized concept classes where each concept is
specified by a parameter vector \Theta 2 R n . Let l(\Theta; x) be the loss of the
concept named by parameter vector \Theta on the data point x (as discussed
above). To further simplify the analysis we assume that for any given x we
have that l(\Theta; x) is a continuous function of \Theta. For example, we might take
\Theta to be the coefficients of an nth order polynomial p \Theta and take l(\Theta; x) to
be max(1; ffjp \Theta (x) \Gamma f(x)j) where f(x) is a fixed target function and ff is a
fixed parameter of the loss function. Note that a two valued loss function
can not be a continuous function of \Theta unless the prediction is independent of
\Theta. Now consider a sample S consisting of m data points. These data points
define an empirical loss " l(\Theta) for each parameter vector \Theta. This empirical
loss is an average of a finite number of expressions of the form l(\Theta; x) and
hence " l(\Theta) must be a continuous function of \Theta. Assuming that the prior on
\Theta is given by a continuous density we then get that there exists a continuous
density p( " l) on empirical errors satisfying the following where P (U) denotes
the measure of a subset U of the concepts according to the prior measure
on concepts.
x
The second main result of the paper can be summarized as the following
approximate equation where B(Q   ) denotes inf Q B(Q).
This approximate inequality is justified by the two theorems stated below.
Before stating the formal theorems, however, it is interesting to compare
(3) with lemma 1. For a countable concept class we can define c   to be the
concept minimizing the bound in lemma 1. For large m, lemma 1 can be
interpreted as follows.
s
Clearly there is a structural similarity between (4) and (3). However, the
two formulas are fundamentally different in that (3) applies to continuous
concept densities while (4) only applies to countable concept classes.
Another contribution of this paper is theorems giving upper and lower
bounds on B(Q   ) justifying (3). First we give a simple posterior distribution
which nearly achieves the performance of (3). Define " l   as follows.
Define the posterior distribution Q( " l   ) as follows where Z is a normalizing
constant.
We now have the following theorem.
Theorem 3 For any prior (probability measure) on a concept class where
each concept is named by a vector \Theta 2 R n and any sample of m instances, if
the loss function l(\Theta; x) is always in the interval [0; 1] and is continuous in
\Theta, the prior on \Theta is a continuous probability density on R n
and the density p( " l) is non-decreasing over the interval
we have the following.
All of the assumptions used in theorem 3 are quite mild. The final assumption
that the density p( " l) is nondecreasing over the interval defining Q( " l   )
is justified by fact that the definition of " l   implies that for any differentiable
density function p( " l) we must have that the density p( " l) is increasing at the
Finally we show that Q( " l   ) is a nearly optimal posterior.
Theorem 4 For any prior (probability measure) on a concept class where
each concept is named by a vector \Theta 2 R n and any sample of m instances,
if the loss function l(\Theta; x) is always in the interval [0; 1] and is continuous
in \Theta, and the prior on \Theta is a continuous probability density on R n , then we
have the following for any posterior Q.
3 Related Work
A model selection guarantee very similar to (1) has been given by Barron
[1]. Assume concepts f 1 , f 2 , f 3 true and empirical error rates ffl(f i )
and "ffl(f i ) as in (1). Let f   be defined as follows.
s
For the case of error rates (also known as 0-1 loss) Barron's theorem reduces
to the following.
s
There are several differences between (1) and (5). When discussing (1) I
will take f   to be the concept f i minimizing the right hand side of (1) which
is nearly the same as the definition of f   in (5). Formula (1) implies the
following.
8
s
Note that (5) bounds the expectation of ffl(f   ) while (1) is a large deviation
result - it gives a bound on ffl(f   ) as a function of the desired confidence
level ffi. Also note that (1) provides a bound on ffl(f   ) in terms of information
available in the sample while (5) provides a bound on (the expectation of)
ffl(f   ) in terms of the unknown quantities ffl(f i ). This means that a learning
algorithm based on (1) can output a performance guarantee along with the
selected concept. This is true even if the concept is selected by incomplete
search over the concept space and hence is different from f   . No such
guarantee can be computed from (5). If a bound in terms of the unknown
quantities ffl(f i ) is desired, the proof method used to prove (1) yields the
following.
8
Also note that (5), like (1) but unlike theorem 1, is vacuous for continuous
concept classes.
Various other model selection results similar to (1) have appeared in the
literature. A guarantee involving the index of a concept in an arbitrary
given sequence of concepts is given in [12]. A bound based on the index
of a concept class in a sequence of classes of increasing VC dimension is
given in [14]. Neither of these bounds handle an arbitrary prior distribution
on concepts. They do, however, give PAC SRM performance guarantees
involving some form of prior knowledge (learning bias).
Guarantees for model selection algorithms for density estimation have
been given by Yamanishi [21] and Barron and Cover [2]. The guarantees
bound measures of distance between a selected model distribution and the
true data source distribution. In both cases the model is assumed to have
been selected so as to optimize an SRM tradeoff between model complexity
and the goodness of fit to the training data. The bounds hold without any
assumption relating the prior distribution to the data distribution, However,
the performance guarantee is better if there exist simple models that fit
well. The precise statement of these bounds are somewhat involved and
perhaps less interesting than the more elegant guarantee given in formula (6)
discussed below.
Guarantees for model averaging have also been proved. First I will consider
model averaging for density estimation. Let f 1 , f 2 , f 3 be an infinite
sequence of models each of which defines a probability distribution on a set
X . Let P be a "prior probability" on the densities f i . Assume an unknown
distribution g on X which need not be equal to any f i . Let S be a sample of
m elements of X sampled IID according to the distribution g. Let h be the
natural "posterior" density on X defined as follows where Z is a normalizing
constant.
Note that the posterior density h is a function of the sample and hence
is a random variable. Catoni [5] and Yang [23] prove somewhat different
general theorems both of which have as a special case the statement that,
independent of how g is selected, the expectation (over drawing a sample
according to g) of the Kullback-Leibler Divergent D(gjjh) is bounded as
follows.
Again we have that (6) holds without any assumed relation between g and
the prior P . If there happens to be a low complexity (simple) model f i such
that D(gjjf i ) is small, then the posterior density h will have small divergence
from g. If no simple model has small divergence from g then D(gjjh) can
be large. Also not that (6), unlike theorem 1, is vacuous for continuous
model classes. These observations also apply to the more general forms of
appearing in [23] and [5]. Catoni [4] also gives performance guarantees
for model averaging for density estimation over continuous model spaces
using a Gibbs posterior. However, the statements of these guarantees are
quite involved and the relationship to the bounds in this paper is unclear.
Yang [22] considers model averaging for prediction. Consider a fixed
distribution D on pairs hx; yi with x 2 X and y 2 f0; 1g. Consider a
countable class of conditional probability rules f 1 , f 2 , f 3 each
f i is a function from X to [0; 1] where f i (x) is interpreted as P (yjx; f i ).
Consider an arbitrary prior on the models f i and construct the posterior
given a sample S as Q(f i
This posterior on the models
induces a posterior h on y given x defined as follows.
Let g(x) be the true conditional probability P (yjx) as defined by the distribution
D. For any function g 0 from X to [0; 1] define the loss L(g 0 ) as
follows where x  D denotes selecting x from the marginal of D on X .
Finally, define ffi i as follows.
For m  2, the following is a corollary of Yang's theorem.
iA
This formula bounds the loss of the Bayesian model average without making
any assumption about the relationship between the data distributions D and
the prior distribution P . However, it seems weaker than (5) or (6) in that it
does not imply even for a finite model class that for large samples the loss
of the posterior converges to the loss of the best model. As with (6), the
guarantee is vacuous for continuous model classes. These same observations
apply to the more general statement in [22].
Weighted model mixtures are also widely used in constructing algorithms
with on-line guarantees. In particular, the weighted majority algorithm
and its variants can be proved to compete well with the best expert on an
arbitrary sequence of labeled data [13, 6, 8, 7]. The posterior weighting
used in most on-line algorithms is a Gibbs posterior Q fi as defined in the
statement of theorem 2. One difference between these on-line guarantees and
theorem 1 is that for these algorithms one must know the appropriate value
of fi before seeing the training data. Since a-prior knowledge of fi is required,
the on-line algorithm is not guaranteed to perform well against the optimal
performing well against the optimal SRM tradeoff requires
tuning fi in response to the training data. Another difference between on-line
guarantees and either formula (1) or theorem 1 is that (1) (or theorem 1)
provides a guarantee even in cases where only incomplete searches over the
concept space are feasible. On-line guarantees require that the algorithm
find all concepts that perform well on the training data - finding a single
simple concept that fits well is insufficient.
The most closely related earlier result is a theorem in [15] bounding the
error rate of stochastic model selection in the case where the model is selected
stochastically from a set U of models under a probability measure that is
simply a renormalization of the prior on U . Theorem 1 is a generalization
of this result to the case of arbitrary posterior distributions.
4 Proof of Theorem 1
The departure point for the proof of theorem 1 is the following where S is
a sample of size m and \Delta(c) abbreviates
Lemma 2 For any prior distribution (probability measure) P on a (possibly
uncountable) concept space C we have the following.
8
4m
Proof: It suffices to prove the following.
4m (7)
Lemma 2 follows from (7) by an application of Markov's inequality. To prove
it suffices to prove the following for any individual given concept.
4m (8)
For a given concept c, the probability distribution on the sample induces a
probability distribution on \Delta(c). By the Chernoff bound this distribution
on \Delta satisfies the following.
It now suffices to show that any distribution satisfying must satisfy
(8). The distribution on \Delta satisfying (9) and maximizing Ee
is the
continuous density f (\Delta) satisfying
which implies
. So we have the following
Z 1e
theorem 1 we consider selecting a sample S. Lemma 2 implies
that with probability at least 1 \Gamma ffi over the selection of a sample S we have
the following.
4m
To prove theorem 1 it now suffices to show that the constraint (10) on
the function \Delta(c) implies the body of theorem 1. We are interested in
computing an upper bound on the quantity S). Note that
\Delta(c). We now prove the
following lemma.
Lemma 3 For fi ? 0, K ? 0, and Q;
we have that if
then
s
Before proving lemma 3 we note that lemmas 3 and 2 together imply
theorem 1. To see this consider a sample satisfying (10) and an arbitrary
posterior probability measure Q on concepts. It is possible to define three
infinite sequences of vectors
the conditions of lemma 3 with
satisfying the following.
By taking the limit of the conclusion of lemma 3 we then get E cQ \Delta(c)
To prove lemma 3 it suffices to consider only those values of i for which
dropping the indices where does not change the value of
enlarging the feasible set by weakening the constraint (10).
Furthermore, if at some point where
the theorem is immediate. So we can assume without loss of generality that
By Jensen's inequality we have (
. So it now
suffices to prove that
This is a consequence
of the following lemma. 1
1 The original version of this paper [16] proved a bound of approximately the form
maximizing
subject to constraint 10. A
Lemma 4 For fi ? 0, K ? 0, and Q;
and
then n
To prove lemma 4 we take P and Q as given and use the Kuhn-Tucker
conditions to find a vector y maximizing
subject to the constraint
(11).
are functions from R n to
R, y is a maximum of C(y) over the set satisfying f 1 (y)
and C and each f i are continuous and differentiable at y, then either
(at y), or there exists some f i with f i (at y), or there
exists a nonempty subset of the constraints f i 1
that positive coefficients  1 such that
Note that lemma 4 allows y i to be negative. The first step in proving
lemma 4 is to show that without loss of generality we can work with a
closed and compact feasible set. For K ? 0 it is not difficult to show that
there exists a feasible point, i.e., a vector y such that
Let C 0 denote an arbitrary feasible value, i.e.,
point y. Without loss of generality we need only consider points y satisfying
1. So we now have a constrained optimization problem
with objective function
set defined by the following
constraints.
version of theorem 1, which is of the form " l(Q; S)+
proved from this bound by an application of Jensen's inequality. The idea of maximizing
i and achieving theorem 1 directly is due to Robert Schapire.
Constraint (12) implies an upper bound on each y i and constraint (13) then
implies a lower bound on each y i . Hence the feasible set is closed and
compact.
We now note that any continuous objective function on a closed and
compact feasible set must be bounded and must achieve its maximum value
on some point in the set. A constraint of the form f(y)  0 will be called
active at y if For an objective function whose gradient is nonzero
everywhere, at least one constraint must be active at the maximum. Since C 0
is a feasible value of the objective function, constraint (13) can not be active
at the maximum. So by the Kuhn-Tucker lemma, the point y achieving the
maximum value must satisfy the following.
Which implies the following.
Since constraint (12) must be active at the maximum, we have the following.
So we get and the following.
Since this is the maximum value of
the lemma is proved.
5 Proof of Theorem 2
We wish to find a distribution Q minimizing B(Q) defined as follows where
the distribution P and the empirical error " l(c) are given and fixed.
s
Letting K be ln(1=ffi)+ln m+2 and letting fl be objective function
can be rewritten as follows where K and fl are fixed positive quantities
independent of Q.
s
To simplify the analysis we consider only finite concept classes. Let P i be
the prior probability of the ith concept and let " l i be the empirical error rate
of the ith concept. The problem now becomes finding values of Q i satisfying
minimizing the following.
s
If P i is zero then if Q i is nonzero we have that D(QjjP ) is infinite. So
for minimizing B(Q) we can assume that Q i is zero if P i is zero and we
can assume without loss of generality that all P i are nonzero. If all P i are
nonzero then the objective function is a continuous function of a compact
feasible set and hence realizes its minimum at some point in the feasible set.
Now consider the following partial derivative.
@
Note that if Q i is zero when P i is nonzero then @D(QjjP )=@Q
This means that any transfer of an infinitesimal quantity of probability mass
to Q i reduces the bound. So the minimum must not occur at a boundary
point satisfying we can assume without loss of generality that
is nonzero for each i where P i is nonzero - the two distributions have
the same support. The Kuhn-Tucker conditions then imply that
rB is in the direction of the gradient of one of the constraints
In all of these cases there must exist a single value  such that
for all i we have @B=@Q This yields the following.
Hence the minimal distribution has the following form.
r
This is the distribution Q fi of theorem 2.
6 Proof of Theorems 3 and 4
be the posterior distribution of theorem 3. First we note the
following.
dP (c)
We have assumed that p( " l) is nondecreasing over the interval
1=m]. This implies the following.
We also have that " theorem 3 now follows from the
definition of B(Q).
We now prove theorem 4. First we define a concept distribution U such
that U induces a uniform distribution on those error rates " l with
Let W be the subset of the values " l 2 [0; 1] such that p( " l) ? 0. Let ff denote
the size of W as measured by the uniform measure on [0; 1]. Note that
ff  1. Define the concept distribution U as follows.
The total measure of U can be written as follows.
Z
dU
dP
dP
Z
Hence U is a probability measure on concepts.
Now let Q be an arbitrary posterior distribution on concepts. We have the
following.
dP
dP
dU
This implies the following where the third line follows from Jensen's inequality

s
s
s
min
s
7 Conclusion
PAC-Bayesian learning algorithms combine the flexibility prior distribution
on models with the performance guarantees of PAC algorithms. PAC-
Bayesian Stochastic model selection can be given performance guarantees
superior to analogous guarantees for deterministic PAC-Bayesian model se-
lection. The performance guarantees for stochastic model selection naturally
handle continuous concept classes and lead to a natural notion of an
optimal posterior distribution to use in stochastically selecting a model. Although
the optimal posterior is a Gibbs distribution, it is shown that under
mild assumptions simpler posterior distributions perform nearly as well. An
open question is whether better guarantees can be given for model averaging
rather than stochastic model selection.

Acknowledgments

I would like to give special thanks to Manfred Warmuth
for inspiring this paper and emphasizing the analogy between the
PAC and on-line settings. I would also like to give special thanks to Robert
Schapire for simplifying and strengthening theorem 1. Avrim Blum, Yoav
Freund, Michael Kearns, John Langford, Yishay Mansour, and Yoram Singer
also provided useful comments and suggestions.



--R

Complexity regularization with application to artificial neural networks.
Minimum complexity density estimation.
Learning classification trees.
Gibbs estimators.
Universal aggregation rules with sharp oracle inequali- ties
Warmuth How to use expert advice.
Adaptive game playing using multiplicative weights.

Predicting nearly as well as the best pruning of a decision tree.

An experimental and theoretical comparison of model selection methods.
Results on learnability and the Vapnik-Chervonenkis dimension
The weighted majority algo- rithm
Concept learning using complexity regulariza- tion
Some pac-bayesian theorems

On pruning and averaging decision trees.
An efficient extension to mixture techniques for prediction and decision trees.

A pac analysis of a bayesian estimator.
Learning non-parametric densities in tyerms of finite-dimensional parametric hypotheses
Adaptive estimation in pattern recognition by combining different procedures.
Mixing strategies for density estimation.
--TR

--CTR
Franois Laviolette , Mario Marchand, PAC-Bayes risk bounds for sample-compressed Gibbs classifiers, Proceedings of the 22nd international conference on Machine learning, p.481-488, August 07-11, 2005, Bonn, Germany
Matti Kriinen , John Langford, A comparison of tight generalization error bounds, Proceedings of the 22nd international conference on Machine learning, p.409-416, August 07-11, 2005, Bonn, Germany
Avrim Blum , John Lafferty , Mugizi Robert Rwebangira , Rajashekar Reddy, Semi-supervised learning using randomized mincuts, Proceedings of the twenty-first international conference on Machine learning, p.13, July 04-08, 2004, Banff, Alberta, Canada
Arindam Banerjee, On Bayesian bounds, Proceedings of the 23rd international conference on Machine learning, p.81-88, June 25-29, 2006, Pittsburgh, Pennsylvania
Ron Meir , Tong Zhang, Generalization error bounds for Bayesian mixture algorithms, The Journal of Machine Learning Research, 4, 12/1/2003
Matthias Seeger, Pac-bayesian generalisation error bounds for gaussian process classification, The Journal of Machine Learning Research, 3, p.233-269, 3/1/2003
gibbs distribution;model averaging;posterior distribution;PAC-Baysian learning;PAC learning