A framework for estimating risk

We consider the problem of model assessment by risk estimation. Variousapproaches to risk estimation are considered in a uni ed framework. This a discussion of various complexity dimensions and approaches to obtainingbounds on covering numbers is also presented.The second type of training sample interval estimator discussed in the thesisis Rademacher bounds. These bounds use advanced concentration inequalities,so a chapter discussing such inequalities is provided. Our discussionof Rademacher bounds leads to the presentation of an alternative, slightlystronger, form of the core result used for deriving local Rademacher bounds,by avoiding a few unnecessary relaxations.Next, we turn to a discussion of PAC-Bayesian bounds. Using an approachdeveloped by Olivier Catoni, we develop new PAC-Bayesian bounds basedon results underlying Hoe ding's inequality. By utilizing Catoni's conceptof \exchangeable priors", these results allowed the extension of a coveringnumber-based result to averaging classi ers, as well as its correspondingalgorithm- and data-dependent result.The last contribution of the thesis is the development of a more exibleshell decomposition bound: by using Hoe ding's tail inequality rather thanHoe ding's relative entropy inequality, we extended the bound to generalloss functions, allowed the use of an arbitrary number of bins, and introducedbetween-bin and within-bin \priors".Finally, to illustrate the calculation of these bounds, we applied some of themto the UCI spam classi cation problem, using decision trees and boostedstumps.framework is an extension of a decision-theoretic framework proposed byDavid Haussler. Point and interval estimation based on test samples andtraining samples is discussed, with interval estimators being classi ed basedon the measure of deviation they attempt to bound.The main contribution of this thesis is in the realm of training sample intervalestimators, particularly covering number-based and PAC-Bayesianinterval estimators. The thesis discusses a number of approaches to obtainingsuch estimators. The rst type of training sample interval estimatorto receive attention is estimators based on classical covering number arguments.A number of these estimators were generalized in various directions.Typical generalizations included: extension of results from misclassi cationloss to other loss functions; extending results to allow arbitrary ghost samplesize; extending results to allow arbitrary scale in the relevant coveringnumbers; and extending results to allow arbitrary choice of in the use ofsymmetrization lemmas.These extensions were applied to covering number-based estimators for variousmeasures of deviation, as well as for the special cases of misclassi -cation loss estimators, realizable case estimators, and margin bounds. Extendedresults were also provided for strati cation by (algorithm- and datadependent)complexity of the decision class.In order to facilitate application of these covering number-based bounds,