We propose an abstract self bounding genetic algorithm that can be applied to various problems of machine learning. The bound on the generalization error that is output by our algorithm is based on Rademacher penalization, a data driven penalization technique. We prove probabilistic oracle inequalities for the theoretical risk of the estimators based on this approach. This is done by comparing the performance of an idealized genetic algorithm that uses a fitness function based on the generalization error with that of an empirical genetic algorithm based on Rademacher penalization. The inequalities indicate that although we are not able to implement the idealized algorithm (because of the inability to compute the generalization error), the empirical algorithm does almost as well as the idealized algorithm would.

We study a method of optimal data-driven aggregation of classifiers in a convex combination and establish tight upper bounds on its excess risk with respect to a convex loss function under the assumption that the so- lution of optimal aggregation problem is sparse. We use a boosting type algorithm of optimal aggregation to develop aggregate classifiers of ac- tivation patterns in fMRI based on locally trained SVM classifiers. The aggregation coefficients are then used to design a "boosting map" of the brain needed to identify the regions with most significant impact on clas- sification.

Consider a problem of recovery of a smooth function (signal, image) f/spl isin//spl Fscr//spl isin/L/sub 2/([0, 1]/sup d/) passed through an unknown filter and then contaminated by a noise. A typical model discussed in the paper is described by a stochastic differential equation dY/sub f//sup /spl epsi//(t)=(Hf)(t)dt+/spl epsi/dW(t), t/spl isin/[0, 1]/sup d/, /spl epsi/>0 where H is a linear operator modeling the filter and W is a Brownian motion (sheet) modeling a noise. The aim is to recover f with asymptotically (as /spl epsi//spl rarr/0) minimax mean integrated squared error. Traditionally, the problem is studied under the assumption that the operator H is known, then the ill-posedness of the problem is the main concern. In this paper, a more complicated and more realistic case is considered where the operator is unknown; instead, a training set of n pairs {(e/sub l/, Y(e/sub l/)/sup /spl sigma//), l=1, 2,..., n}, where {e/sub l/} is an orthonormal system in L/sub 2/ and {Y(e/sub l/)/sup /spl sigma//} denote the solutions of stochastic differential equations of the above type with f=e/sub l/ and /spl epsi/=/spl sigma/ is available. An optimal (in a minimax sense over considered operators and signals) data-driven recovery of the signal is suggested. The influence of /spl epsi/, /spl sigma/, and n on the recovery is thoroughly studied; in particular, we discuss an interesting case of a larger noise during the training and present formulas for threshold levels for n beyond which no improvement in recovery of input signals occurs. We also discuss the case where H is an unknown perturbation of a known operator. We describe a class of perturbations for which the accuracy of recovery of the signal is asymptotically the same (up to a constant) as in the case of precisely known operator.

We suggest a penalty function to be used in various problems of structural risk minimization. This penalty is data dependent and is based on the sup-norm of the so-called Rademacher process indexed by the underlying class of functions (sets). The standard complexity penalties, used in learning problems and based on the VC-dimensions of the classes, are conservative upper bounds (in a probabilistic sense, uniformly over the set of all underlying distributions) for the penalty we suggest. Thus, for a particular distribution of training examples, one can expect better performance of learning algorithms with the data-driven Rademacher penalties. We obtain oracle inequalities for the theoretical risk of estimators, obtained by structural minimization of the empirical risk with Rademacher penalties. The inequalities imply some form of optimality of the empirical risk minimizers. We also suggest an iterative approach to structural risk minimization with Rademacher penalties, in which the hierarchy of classes is not given in advance, but is determined in the data-driven iterative process of risk minimization. We prove probabilistic oracle inequalities for the theoretical risk of the estimators based on this approach as well.

In this paper we develop the method of bounding the generalization error of a classifier in terms of its margin distribution which was introduced in the recent papers of Bartlett and Schapire, Freund, Bartlett and Lee. The theory of Gaussian and empirical processes allow us to prove the margin type inequalities for the most general functional classes, the complexity of the class being measured via the so called Gaussian complexity func(cid:173) tions. As a simple application of our results, we obtain the bounds of Schapire, Freund, Bartlett and Lee for the generalization error of boost(cid:173) ing. We also substantially improve the results of Bartlett on bounding the generalization error of neural networks in terms of h -norms of the weights of neurons. Furthermore, under additional assumptions on the complexity of the class of hypotheses we provide some tighter bounds, which in the case of boosting improve the results of Schapire, Freund, Bartlett and Lee. 1 Introduction and margin type inequalities for general functional classes Let (X, Y) be a random couple, where X is an instance in a space Sand Y E {-I, I} is a label. Let 9 be a set of functions from S into JR. For 9 E g, sign(g(X)) will be used as a predictor (a classifier) of the unknown label Y. If the distribution of (X, Y) is unknown, then the choice of the predictor is based on the training data (Xl, Yl ), ... , (Xn, Yn) that consists ofn i.i.d. copies of (X, Y). The goal ofleaming is to find a predictor 9 E 9 (based on the training data) whose generalization (classification) error JP'{Yg(X) :::; O} is small enough. We will first introduce some probabilistic bounds for general functional classes and then give several examples of their applications to bounding the generalization error of boosting and neural networks. We omit all the proofs and refer an interested reader to [5]. Let (8, A, P) be a probability space and let F be a class of measurable functions from (8, A) into lR. Let {Xd be a sequence of i.i.d. random variables taking values in (8, A) with common distribution P. Let Pn be the empirical measure based on the sample (Xl,'" ,Xn), Pn := n- l E~=l c5x " where c5x denotes the probability distribution con(cid:173) centrated at the point x. We will denote P! := Is !dP, Pn! := Is !dPn, etc. In what follows, £OO(F) denotes the Banach space of uniformly bounded real valued functions on F with the norm IIYII.:F := sUPfE.:F 1Y(f)I, Y E £OO(F). Define n n where {gi} is a sequence of i.i.d. standard normal random variables, independent of {Xi}' We will call n t-+ Gn(F) the Gaussian complexity function of the class F. One can find in the literature (see, e.g. [11]) various upper bounds on such quantities as Gn (F) in terms of entropies, VC-dimensions, etc. We give below a bound in terms of margin cost functions (compare to [6, 7]) and Gaussian complexities. Let Theorem 1 For all t > 0, lP'{ =3/ E F: P{! :-::; O} > Let us consider a special family of cost functions. Assume that cP is a fixed non increasing Lipschitz function from IR into IR such that cp(x) 2: (1 + sgn( -x)) /2 for all x E lR. One can easily observe that L( cpU 15)) :-::; L( cP )15- 1 . Applying Theorem 1 to the class of Lipschitz functions Theorem 2 For all t > 0, lP'{3! E F: P{! :-::; O} > inf [Pncp(L) + 2y'2irL(cp) Gn(F) aE[O,l] cogIOg~(2c5-l)r/2] + t:n2 }:-::; 2exp{-2t2}. $('.dropdown-menu a.dropdown-toggle').on('click', function (e) { if (!$(this).next().hasClass('show')) { $(this).parents('.dropdown-menu').first().find('.show').removeClass("show"); } var $subMenu = $(this).next(".dropdown-menu"); $subMenu.toggleClass('show'); $(this).parents('li.nav-item.dropdown.show').on('hidden.bs.dropdown', function (e) { $('.dropdown-submenu .show').removeClass("show"); }); return false; }); Name Change Policy × Requests for name changes in the electronic proceedings will be accepted with no questions asked. However name changes may cause bibliographic tracking issues. Authors are asked to consider this carefully and discuss it with their co-authors prior to requesting a name change in the electronic proceedings. Use the "Report an Issue" link to request a name change. Report an Issue | Name Change Policy Do not remove: This comment is monitored to verify that the site is working properly