STRUCTURAL RISK MINIMIZATION OVER DATA-DEPENDENT HIERARCHIES

The paper introduces some generalizations of Vapnik's method of struct ural risk minimization (SRM). As well as making explicit some of the d etails on SRM, it provides a result that allows one to trade off error s on the training sample against improved generalization performance. It then considers the more general case when the hierarchy of classes is chosen in response to the data. A result is presented on the genera lization performance of classifiers with a ''large margin.'' This theo retically explains the impressive generalization performance of the ma ximal margin hyperplane algorithm of Vapnik and co-workers (which is t he basis for their support vector machines). The paper concludes with a more general result in terms of ''luckiness'' functions, which provi des a quite general way for exploiting serendipitous simplicity in obs erved data to obtain better prediction accuracy from small training se ts. Four examples are given of such functions, including the Vapnik-Ch ervonenkis (VC) dimension measured on the sample.