Although recent evidence suggest that multicomponent therapy can be more effective in the treatment of complex diseases than single drug treatments, discovering such drug combinations remains a challenging and expensive task. We propose a machine learning approach for this problem. In our approach we use a relatively small set of drug combinations for which effectiveness has been assessed (perhaps experimentally) to train a kernel based model that can be used to rank other previously unseen drug combinations by their effectiveness. We present experimental results for the problem of selective killing of cells using synthetic data from a human apoptosis model. Our learning algorithm is able to produce very good rankings on unseen data, both in terms of producing mostly the correct ordering of drug combinations, and in terms of quality at the top of the list, that is, orderings that have most of the drug combinations with the largest scores at the top of the list. This is important in the case were the ranking algorithm is used to produce an ordered list of drug combinations that is in turn tested experimentally, as this would allow the experimental effort to concentrate on drug combinations at the top of the list.

Graph-based manifold learning techniques have become of paramount importance when researchers have been faced to nonlinear data. These techniques have allowed them to discover relations that usual approaches such as PCA and MDS were incapable of. However, properties such as non-uniform sampling, varied topological substructures and highly curved manifolds still represent a challenge to these methods. We propose a graph building framework that strives at capturing the topological structures hidden in the data by means of a locality linear characterization combined with a MST-based noise model. We propose two algorithms under such framework that show improved performance over usual approaches.

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 present several algorithms that combine many base learners trained on different distributions of the data, but allow some of the base learners to be trained simultaneously by separate processors. Our algorithms train batches of base classifiers using distributions that can be generated in advance of the training process. We propose several heuristic methods that produce a group of useful distributions based on the performance of the classifiers in the previous batch. We present experimental evidence that suggest that two of our algorithms are able to produce classifiers as accurate as the corresponding Adaboost classifier with the same number of base learners, but with a greatly reduced computation time.

In this paper, we present a weakened variation of support vector machines that can be used together with Adaboost. Our modified support vector machine algorithm has the following interesting properties: first, it is able to handle distributions over the training data; second, it is a weak algorithm in the sense that it ensures an empirical error upper bounded by 1/2 . Third, when used together with Adaboost, the resulting algorithm is faster than the usual SVM training algorithm; and finally, we show that our boosted SVM can be effective as an editing algorithm.

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