Foundations of Machine Learning
Medical Entomology and ZoologyPublished 17 August 2012
Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar
Citations1,159
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This graduate-level textbook introduces fundamental concepts and methods in machine learning, and provides the theoretical underpinnings of these algorithms, and illustrates key aspects for their application.
Abstract
Fundamental topics in machine learning are presented along with theoretical and conceptual tools for the discussion and proof of algorithms.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
Cambridge University Press eBooksConvex Optimization
31,266 Citations2004Stephen Boyd, Lieven Vandenberghe
The Annals of StatisticsGreedy function approximation: A gradient boosting machine.
28,973 Citations2001Jerome H. Friedman
A general gradient descent boosting paradigm is developed for additive expansions based on any fitting criterion, and specific algorithms are presented for least-squares, least absolute deviation, and Huber-M loss functions for regression, and multiclass logistic likelihood for classification.
RadiologyThe meaning and use of the area under a receiver operating characteristic (ROC) curve.
21,812 Citations1982J A Hanley, Barbara J. McNeil
A representation and interpretation of the area under a receiver operating characteristic (ROC) curve obtained by the "rating" method, or by mathematical predictions based on patient characteristics, is presented and it is shown that in such a setting the area represents the probability that a randomly chosen diseased subject is (correctly) rated or ranked with greater suspicion than a random chosen non-diseased subject.
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding
15,035 Citations2000Sam T. Roweis, Lawrence K. Saul
Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction
13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more
An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
Psychological ReviewThe perceptron: A probabilistic model for information storage and organization in the brain.
11,746 Citations1958Frank F. Rosenblatt
This article will be concerned primarily with the second and third questions, which are still subject to a vast amount of speculation, and where the few relevant facts currently supplied by neurophysiology have not yet been integrated into an acceptable theory.
The London Edinburgh and Dublin Philosophical Magazine and Journal of ScienceLIII. <i>On lines and planes of closest fit to systems of points in space</i>
11,670 Citations1901Karl Pearson
This paper is concerned with the construction of planes of closest fit to systems of points in space and the relationships between these planes and the planes themselves.
A training algorithm for optimal margin classifiers
11,594 Citations1992Bernhard E. Boser, Isabelle Guyon +1 more
A training algorithm that maximizes the margin between the training patterns and the decision boundary is presented, applicable to a wide variety of the classification functions, including Perceptrons, polynomials, and Radial Basis Functions.
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
The Annals of Mathematical StatisticsA Stochastic Approximation Method
9,581 Citations1951Herbert Robbins, Sutton Monro
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
Journal of the American Statistical AssociationMarkov Decision Processes: Discrete Stochastic Dynamic Programming.
8,422 Citations1995Kasra Hazeghi, Martin L. Puterman
Markov Decision Processes covers recent research advances in such areas as countable state space models with average reward criterion, constrained models, and models with risk sensitive optimality criteria, and explores several topics that have received little or no attention in other books.
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
The Annals of StatisticsAdditive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)
6,842 Citations2000Jerome H. Friedman, Trevor Hastie +1 more
This work shows that this seemingly mysterious phenomenon of boosting can be understood in terms of well-known statistical principles, namely additive modeling and maximum likelihood, and develops more direct approximations and shows that they exhibit nearly identical results to boosting.
Cambridge University Press eBooksKernel Methods for Pattern Analysis
6,598 Citations2004John Shawe‐Taylor, Nello Cristianini
This book provides an easy introduction for students and researchers to the growing field of kernel-based pattern analysis, demonstrating with examples how to handcraft an algorithm or a kernel for a new specific application, and covering all the necessary conceptual and mathematical tools to do so.
TechnometricsRidge Regression: Biased Estimation for Nonorthogonal Problems
6,562 Citations2000Arthur E. Hoerl, Robert W. Kennard
Programs for Machine Learning
5,794 Citations1994Steven L. Salzberg, Alberto M. Segre
In his new book, C4.5: Programs for Machine Learning, Quinlan has put together a definitive, much needed description of his complete system, including the latest developments, which will be a welcome addition to the library of many researchers and students.
The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
4,535 Citations2002Mikhail Belkin, Partha Niyogi
The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Models for Ordinal Data
4,395 Citations1980Peter McCullagh
Medical Entomology and ZoologyThe Probabilistic Method
4,356 Citations1991Joel Spencer
A particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets - is explored.
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Optimizing search engines using clickthrough data
3,898 Citations2002Thorsten Joachims
The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking.
Information and ControlLanguage identification in the limit
3,569 Citations1967Eric Gold
It was found that theclass of context-sensitive languages is learnable from an informant, but that not even the class of regular languages is learningable from a text.
Perceptrons: an introduction to computational geometry
3,308 Citations1969Marvin Minsky, Seymour Papert
Machine LearningThe Strength of Weak Learnability
3,293 Citations1990Robert E. Schapire
In this paper, a method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy, and it is shown that these two notions of learnability are equivalent.
Cambridge University Press eBooksPrediction, Learning, and Games
3,258 Citations2006Nicolò Cesa‐Bianchi, Gábor Lugosi
This chapter discusses prediction with expert advice, efficient forecasters for large classes of experts, and randomized prediction for specific losses.
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
3,175 Citations2015Vladimir Vapnik, Alexey Chervonenkis
This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady.
Machine LearningAn Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization
2,950 Citations2000Thomas G. Dietterich
The experiments show that in situations with little or no classification noise, randomization is competitive with (and perhaps slightly superior to) bagging but not as accurate as boosting, and sometimes better than randomization.
Journal of Artificial Intelligence ResearchSolving Multiclass Learning Problems via Error-Correcting Output Codes
2,718 Citations1995Tom Dietterich, Ghulum Bakiri
It is demonstrated that error-correcting output codes provide a general-purpose method for improving the performance of inductive learning programs on multiclass problems.
Mathematics of ComputationUpdating quasi-Newton matrices with limited storage
2,710 Citations1980Jorge Nocedal
An update formula which generates matrices using information from the last m iterations, where m is any number supplied by the user, and the BFGS method is considered to be the most efficient.
Improved boosting algorithms using confidence-rated predictions
2,568 Citations1998Robert E. Schapire, Yoram Singer
Machine LearningBoosTexter: A Boosting-based System for Text Categorization
2,194 Citations2000Robert E. Schapire, Yoram Singer
This work describes in detail an implementation, called BoosTexter, of the new boosting algorithms for text categorization tasks, and presents results comparing the performance of Boos Texter and a number of other text-categorization algorithms on a variety of tasks.
The Annals of Mathematical StatisticsStochastic Estimation of the Maximum of a Regression Function
2,143 Citations1952J. Kiefer, J. Wolfowitz
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
Information and ComputationThe Weighted Majority Algorithm
2,022 Citations1994N. Littlestone, Manfred K. Warmuth
Lecture notes in statisticsThe Boosting Approach to Machine Learning: An Overview
2,013 Citations2003Robert E. Schapire
This chapter overviews some of the recent work on boosting including analyses of AdaBoost's training error and generalization error; boosting’s connection to game theory and linear programming; the relationship between boosting and logistic regression; extensions of Ada boost for multiclass classification problems; methods of incorporating human knowledge into boosting; and experimental and applied work using boosting.
MPG.PuRe (Max Planck Society)Large Margin Methods for Structured and Interdependent Output Variables
1,952 Citations2005Ioannis Tsochantaridis, Thorsten Joachims +2 more
This paper proposes to appropriately generalize the well-known notion of a separation margin and derive a corresponding maximum-margin formulation and presents a cutting plane algorithm that solves the optimization problem in polynomial time for a large class of problems.
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Rank aggregation methods for the Web
1,798 Citations2001Cynthia Dwork, Ravi Kumar +2 more
A set of techniques for the rank aggregation problem is developed and compared to that of well-known methods, to design rank aggregation techniques that can be used to combat spam in Web searches.
On the algorithmic implementation of multiclass kernel-based vector machines
1,790 Citations2002Koby Crammer, Yoram Singer
This paper describes the algorithmic implementation of multiclass kernel-based vector machines using a generalized notion of the margin to multiclass problems, and describes an efficient fixed-point algorithm for solving the reduced optimization problems and proves its convergence.
HAL (Le Centre pour la Communication Scientifique Directe)Combinatorics on words
1,751 Citations1984M. Lothaire
The MIT Press eBooksAn Introduction to Computational Learning Theory
1,733 Citations1994Michael Kearns, Umesh Vazirani
The probably approximately correct learning model Occam's razor the Vapnik-Chervonenkis dimension weak and strong learning learning in the presence of noise inherent unpredictability reducibility in PAC learning learning finite automata is described.
Online convex programming and generalized infinitesimal gradient ascent
1,705 Citations2003Martin Zinkevich
An algorithm for convex programming is introduced, and it is shown that it is really a generalization of infinitesimal gradient ascent, and the results here imply that generalized inf initesimalgradient ascent (GIGA) is universally consistent.
Information and ComputationBoosting a Weak Learning Algorithm by Majority
1,686 Citations1995Yoav Freund
An algorithm for improving the accuracy of algorithms for learning binary concepts by combining a large number of hypotheses, each of which is generated by training the given learning algorithm on a different set of examples, is presented.
Lecture notes in computer scienceA Generalized Representer Theorem
1,587 Citations2001Bernhard Schölkopf, Ralf Herbrich +1 more
The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.
Bulletin of the American Mathematical SocietyOn the mathematical foundations of learning
1,578 Citations2001Felipe Cucker, Steve Smale
A main theme of this report is the relationship of approximation to learning and the primary role of sampling (inductive inference) and relations of the theory of learning to the mainstream of mathematics are emphasized.
Communications of the ACMTemporal difference learning and TD-Gammon
1,485 Citations1995Gerald Tesauro
The domain of complex board games such as Go, chess, checkers, Othello, and backgammon has been widely regarded as an ideal testing ground for exploring a variety of concepts and approaches in artificial intelligence and machine learning.
ACM SIGIR ForumIR evaluation methods for retrieving highly relevant documents
1,466 Citations2017Kalervo Järvelin, Jaana Kekäläinen
The novel evaluation methods and the case demonstrate that non-dichotomous relevance assessments are applicable in IR experiments, may reveal interesting phenomena, and allow harder testing of IR methods.
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
In Defense of One-Vs-All Classification
1,387 Citations2004Ryan Rifkin, Aldebaro Klautau
It is argued that a simple "one-vs-all" scheme is as accurate as any other approach, assuming that the underlying binary classifiers are well-tuned regularized classifiers such as support vector machines.
Machine LearningLearning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
1,376 Citations1988Nick Littlestone
This work presents one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions.
Neural network learning theoretical foundations
1,357 Citations2009Martin Anthony, Peter L. Bartlett
The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction, and discuss the computational complexity of neural network learning.
Machine LearningSoft Margins for AdaBoost
1,306 Citations2001Gunnar Rätsch, Takashi Onoda +1 more
It is found that ADABOOST asymptotically achieves a hard margin distribution, i.e. the algorithm concentrates its resources on a few hard-to-learn patterns that are interestingly very similar to Support Vectors.
Probability in Banach Spaces: Isoperimetry and Processes
1,276 Citations1991Michel Ledoux, Michel Talagrand
Journal of Mathematical Analysis and ApplicationsSome results on Tchebycheffian spline functions
1,255 Citations1971George Kimeldorf, Grace Wahba
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
Large margin classification using the perceptron algorithm
1,099 Citations1998Yoav Freund, Robert E. Schapire
Convolution kernels on discrete structures
1,089 Citations1999David Haussler
A new method of constructing kernels on sets whose elements are discrete structures like strings, trees and graphs is introduced, which can be applied iteratively to build a kernel on a innnite set from kernels involving generators of the set.
Random Structures and AlgorithmsAn elementary proof of a theorem of Johnson and Lindenstrauss
963 Citations2002Sanjoy Dasgupta, Anupam Gupta
A result of Johnson and Lindenstrauss shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/ϵ2)‐dimensional Euclidesan space such that the distance between any two points changes by only a factor of (1 ± ϵ).
A dual coordinate descent method for large-scale linear SVM
906 Citations2008Cho‐Jui Hsieh, Kai‐Wei Chang +3 more
A novel dual coordinate descent method for linear SVM with L1-and L2-loss functions that reaches an ε-accurate solution in O(log(1/ε)) iterations is presented.
Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications
871 Citations1992David Haussler
Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.
Journal of Combinatorial Theory Series AOn the density of families of sets
866 Citations1972N. Sauer
This paper will answer the question in the affirmative by determining the exact upper bound of T if T is a family of subsets of some infinite set S then either there exists to each number n a set A ⊂ S with |A| = n such that |T ∩ A| = 2n or there exists some number N such that •A| c for each A⩾ N and some constant c.
Minima of Functions of Several Variables with Inequalities as Side Conditions
854 Citations2013William Karush
Kernel PCA and De-Noising in Feature Spaces
828 Citations1998Sebastian Mika, Bernhard Schölkopf +4 more
This work presents ideas for finding approximate pre-images, focusing on Gaussian kernels, and shows experimental results using these pre- images in data reconstruction and de-noising on toy examples as well as on real world data.
Neural ComputationOn the Convergence of Stochastic Iterative Dynamic Programming Algorithms
805 Citations1994Tommi Jaakkola, Michael I. Jordan +1 more
A rigorous proof of convergence of DP-based learning algorithms is provided by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem, which establishes a general class of convergent algorithms to which both TD() and Q-learning belong.
ePrints Soton (University of Southampton)Ridge Regression Learning Algorithm in Dual Variables
802 Citations1998Craig Saunders, Alex Gammerman +1 more
A regression estimation algorithm which is a combination of the dual version of Ridge Regression is applied to the ANOVA enhancement of the infinitenode splines and the use of kernel functions, as used in Support Vector methods is introduced.
The European Symposium on Artificial Neural NetworksSupport vector machines for multi-class pattern recognition.
794 Citations1999Jason Weston, Chris Watkins
A formulation of the SVM is proposed that enables a multi-class pattern recognition problem to be solved in a single optimisation and a similar generalization of linear programming machines is proposed.
Scholarworks (University of Massachusetts Amherst)Temporal credit assignment in reinforcement learning
778 Citations1984Richard S. Sutton
Information and ControlComplexity of automaton identification from given data
770 Citations1978Eric Gold
The question of whether there is an automaton with n states which agrees with a finite set D of data is shown to be NP-complete, although identification-in-the-limit of finite automata is possible in polynomial time as a function of the size of D.
Journal of the American Statistical AssociationProbability Inequalities for the Sum of Independent Random Variables
756 Citations1962G. G. Bennett
Journal of the ACMCryptographic limitations on learning Boolean formulae and finite automata
744 Citations1994Michael Kearns, Leslie G. Valiant
It is proved that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory and is applied to obtain strong intractability results for approximating a generalization of graph coloring.
Boosting Algorithms as Gradient Descent
712 Citations1999Llew Mason, Jonathan Baxter +2 more
Following previous theoretical results bounding the generalization performance of convex combinations of classifiers in terms of general cost functions of the margin, a new algorithm (DOOM II) is presented for performing a gradient descent optimization of such cost functions.
Transactions of the American Mathematical SocietyMetric spaces and positive definite functions
711 Citations1938I. J. Schoenberg
Applied Physics Letters10.1162/153244302760200704
696 Citations2000
It is shown how to use notions of stability for learning algorithms to derive generalization error bounds based on the empirical error and the leave-one-out error to apply to SVM for regression and classification.
Machine LearningLogistic Regression, AdaBoost and Bregman Distances
689 Citations2002Michael Collins, Robert E. Schapire +1 more
A unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances, and a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases are described, thus showing how the sequential and parallel approaches can themselves be unified.
Journal of the ACMHow to use expert advice
647 Citations1997Nicolò Cesa‐Bianchi, Yoav Freund +4 more
This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts, and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context.
Journal of Computer and System SciencesEfficient algorithms for online decision problems
613 Citations2004Adam Tauman Kalai, Santosh Vempala
It is shown that a very simple idea, used in Hannan's seminal 1957 paper, gives efficient solutions to all of these problems, including a (1+∈)-competitive algorithm as well as a lazy one that rarely switches between decisions.
Machine LearningAsynchronous Stochastic Approximation and Q-Learning
610 Citations1994John N. Tsitsiklis
The Q-learning algorithm, a reinforcement learning method for solving Markov decision problems, is studied to establish its convergence under conditions more general than previously available.
QUT ePrints (Queensland University of Technology)Boosting the margin: A new explanation for the effectiveness of voting methods
578 Citations1997Robert E. Schapire, Yoav Freund +2 more
Neural ComputationPrediction Games and Arcing Algorithms
546 Citations1999Leo Breiman
The theory behind the success of adaptive reweighting and combining algorithms (arcing) such as Adaboost and others in reducing generalization error has not been well understood, and an explanation of whyAdaboost works in terms of its ability to produce generally high margins is offered.
A kernel view of the dimensionality reduction of manifolds
543 Citations2004Jihun Ham, Daniel D. Lee +2 more
Isomap, graph Laplacian eigenmap, and locally linear embedding all utilize local neighborhood information to construct a global embedding of the manifold and it is shown how all three algorithms can be described as kernel PCA on specially constructed Gram matrices.
Games and Economic BehaviorAdaptive Game Playing Using Multiplicative Weights
538 Citations1999Yoav Freund, Robert E. Schapire
A variant of the game-playing algorithm is proved to be optimal in a very strong sense and a new, simple proof of the min–max theorem, as well as a provable method of approximately solving a game.
Journal of the ACMInference of Reversible Languages
530 Citations1982Dana Angluin
An efficient algonthrn is presented for mfernng reversible languages from posmve and negative examples, and it is shown that it leads to correct identification m the hmlt of the class of reversible languages.
IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies
527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more
A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.
AUC Optimization vs. Error Rate Minimization
512 Citations2003Corinna Cortes, Mehryar Mohri
The results show that the average AUC is monotonically increasing as a function of the classification accuracy, but that the standard deviation for uneven distributions and higher error rates is noticeable, so algorithms designed to minimize the error rate may not lead to the best possible AUC values.
Applied Physics Letters10.1162/15324430152733133
506 Citations2000
A general method for combining the classifiers generated on the binary problems is proposed, and a general empirical multiclass loss bound is proved given the empirical loss of the individual binary learning algorithms.
Pacific Journal of MathematicsA combinatorial problem; stability and order for models and theories in infinitary languages
496 Citations1972Saharon Shelah
Improving Elevator Performance Using Reinforcement Learning
495 Citations1995Robert H. Crites, Andrew G. Barto
Results in simulation surpass the best of the heuristic elevator control algorithms of which the author is aware and demonstrate the power of RL on a very large scale stochastic dynamic optimization problem of practical utility.
The Annals of StatisticsEmpirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers
468 Citations2002Vladimir Koltchinskii, Dmitry Panchenko
New probabilistic upper bounds on generalization error of complex classifiers that are combinations of simple classifier combinations, based on the methods of the theory of Gaussian and empirical processes are proved.
The Sizes of Compact Subsets of Hilbert Space and Continuity of Gaussian Processes
455 Citations2010R. M. Dudley
IEEE Transactions on Information TheoryOn the Generalization Ability of On-Line Learning Algorithms
442 Citations2004Nicolò Cesa‐Bianchi, Alex Conconi +1 more
This paper proves tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble, and obtains risk tail bounds for kernel perceptron algorithms interms of the spectrum of the empirical kernel matrix.
Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions
419 Citations1984Christian Berg, Jens Peter Christensen +1 more
Neural ComputationAlgorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation
418 Citations1999Michael Kearns, Dana Ron
…