Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Nicolo Cesa-bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no...
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
On Reoptimizing Multi-Class Classifiers ∗ (2009)
Chris Bourke, Kun Deng, Stephen D. Scott, Robert E. Schapire, N. V. Vinodch
Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously-learned classifier to work under new conditions. We study the...
Barutcuoglu, Zafer, Airoldi, Edoardo M., Dumeaux, Vanessa, Schapire, Robert E., Troyanskaya, Olga G.
Motivation: The heterogeneity of cancer cannot always be recognized by tumor morphology, but may be reflected by the underlying genetic aberrations. Array comparative genome hybridization (array-CGH)...
Miroslav Dudík, Steven J. Phillips, Robert E. Schapire, John Lafferty
We present a unified and complete account of maximum entropy density estimation subject to constraints represented by convex potential functions or, alternatively, by convex regularization. We...
Exploiting Spatial Information to Improve fMRI Pattern Classification (2008)
Melissa K. Carroll, Kenneth A. Norman, James V. Haxby, Robert E. Schapire
• Classification methods have been successfully applied to pattern extraction from fMRI (e.g. [1,2]). • Most classification approaches have treated individual voxels as features, ignoring the...
BIOINFORMATICS ORIGINAL PAPER Systems biology (2008)
Zafer Barutcuoglu, Robert E. Schapire, Olga G. Troyanskaya
Hierarchical multi-label prediction of gene function
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
Abstract Training Algorithms for Linear Text Classifiers (2008)
David D. Lewis, Robert E. Schapire, James P. Calian, Ron Papka
Systems for text retrieval, routing, categorization and other IR tasks rely heavily on linear classifiers. We propose that two machine learning algorithms, the Widrow-Hoff and EG algorithms, be used...
Methods Gábor Lugosi, Nicolas Vayatis, Robert E. Schapire, Yoav Freund
The notion of a boosting algorithm was originally introduced by Valiant in the context of the “probably approximately correct ” (PAC) model of learnability [19]. In this context boosting is a...
Miroslav Dudík, Robert E. Schapire, Steven J. Phillips
We study the problem of maximum entropy density estimation in the presence of known sample selection bias. We propose three bias correction approaches. The first one takes advantage of unbiased...
We study the problem of an apprentice learning to behave in an environment with an unknown reward function by observing the behavior of an expert. We follow on the work of Abbeel and Ng [1] who...
David Haussler, P. Helmbold, Robert E. Schapire, Manfred K. Warmuth
Abstract. We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no...
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm that achieves almost the same wealth as the best constantrebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm employs...
Feature Induction Using Boosting and Logistic Regression on fMRI Images (2008)
Melissa K. Carroll, Miroslav Dudík, Robert E. Schapire, Kenneth A. Norman
Early efforts in fMRI classification were limited in that individual voxels were used as features (e.g. [1]), yet voxels divide images into regions that do not directly correspond to underlying...
Joseph K. Bradley, Robert E. Schapire
We study boosting in the filtering setting, where the booster draws examples from an oracle instead of using a fixed training set and so may train efficiently on very large datasets. Our algorithm,...
Analysis of boosting algorithms using the smooth margin function (2008)
Rudin, Cynthia, Schapire, Robert E., Daubechies, Ingrid
We introduce a useful tool for analyzing boosting algorithms called the ``smooth margin function,'' a differentiable approximation of the usual margin for boosting algorithms. We present two boosting...
We study the problem of an apprentice learning to behave in an environment with an unknown reward function by observing the behavior of an expert. We follow on the work of Abbeel and Ng [1] who...
Hierarchical Maximum Entropy Density Estimation (2008)
Miroslav Dudík, David M. Blei, Robert E. Schapire
We study the problem of simultaneously estimating several densities where the datasets are organized into overlapping groups, such as a hierarchy. For this problem, we propose a maximum entropy...
Yoav Freund, Michael Kearns, Ronitt Rubinfeld, Robert E. Schapire
In this paper, we describe new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distin-guished by two features: The adoption of an average-case setting...
Joseph K. Bradley, Robert E. Schapire
We study boosting in the filtering setting, where the booster draws examples from an oracle instead of using a fixed training set and so may train efficiently on very large datasets. Our algorithm,...
Joseph K. Bradley, Robert E. Schapire
We study boosting in the filtering setting, where the booster draws examples from an oracle instead of using a fixed training set and so may train efficiently on very large datasets. Our algorithm,...
Aurélie C. Lozano, Robert E. Schapire, Sanjeev R. Kulkarni
We study the statistical convergence and consistency of regularized Boosting methods, where the samples are not independent and identically distributed (i.i.d.) but come from empirical processes of...
Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire
In order to understand AdaBoost’s dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases....
Boosting with Prior Knowledge for Call Classification (2008)
Robert E. Schapire, Marie Rochery, Mazin Rahim, Narendra Gupta
The use of boosting for call classification in spoken language understanding is described in this paper. An extension to the AdaBoost algorithm is presented that permits the incorporation of prior...
Correcting Sample Selection Bias in Maximum (2008)
Entropy Density Estimation, Miroslav Dudík, Robert E. Schapire, Steven J. Phillips
We study the problem of maximum entropy density estimation in the presence of known sample selection bias. We propose three bias correction approaches. The first one takes advantage of unbiased...
Faster solutions of the inverse pairwise Ising problem (2007)
Broderick, Tamara, Dudik, Miroslav, Tkacik, Gasper, Schapire, Robert E., Bialek, William
Recent work has shown that probabilistic models based on pairwise interactions-in the simplest case, the Ising model-provide surprisingly accurate descriptions of experiments on real biological...
Theory, 2000. Logistic Regression, AdaBoost and Bregman Distances (2007)
Michael Collins, Robert E. Schapire, Yoram Singer
An extended abstract of this journal submission
and Statistics, 2001. Why Averaging Classifiers Can Protect Against Overfitting (2007)
Yoav Freund, Yishay Mansour, Robert E. Schapire
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, this algorithm predicts with a weighted average of all...
pages 1-10, 1999. Theoretical Views of Boosting (2007)
Abstract. Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, we briefly survey theoretical work on boosting...
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
Machine Learning, to appear. Drifting Games (2007)
Abstract. We introduce and study a general, abstract game played between two players called the shepherd and the adversary. The game is played in a series of rounds using a finite set of...
Raj D. Iyer, David D. Lewis, Robert E. Schapire, Yoram Singer, Amit Singhal
RankBoost is a recently proposed algorithm for learning ranking functions. It is simple to implement and has strong justifications from computational learning theory. We describe the algorithm and...
Theory and Applications of Predictors That Specialize (2007)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Conference submission (2/1/02). Incorporating Prior Knowledge into Boosting (2007)
Robert E. Schapire, Marie Rochery, Mazin Rahim, Narendra Gupta
We describe a modification to the AdaBoost algorithm that permits the incorporation of prior human knowledge as a means of compensating for a shortage of training data. We give a convergence result...
Conference submission (1/22/02). ATTac-2001: A Learning, Autonomous Bidding Agent (2007)
Peter Stone, Robert E. Schapire, Michael L. Littman, David Mcallester
This paper presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. The core of our approach is learning a model of the...
Peter Stone, Robert E. Schapire, Janos A. Csirik, Michael L. Littman, David Mcallester
Abstract. Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This paper presents a general approach to building autonomous bidding agents to...
Analysis of a Pseudo-Bayesian Prediction Method (2007)
Yoav Freund, Yishay Mansour, Robert E. Schapire
Abstract--- We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, this algorithm predicts with a weighted average of...
Invited to IJCAI Distinguished Paper Track. Learning Theory and Language Modeling (2007)
David Mcallester, Robert E. Schapire
Here we consider some of our recent work on Good-Tuing estimators in the larger context of learning theory and language modeling. The Good-turing estimators have played a significant role in natural...
Peter Auer, Yoav Freund, Robert E. Schapire
for journal publication. The non-stochastic multi-armed bandit problem
Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, Manfred K. Warmuth
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no...
Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, this chapter overviews some of the recent work on boosting...
Ronald L. Rivest, Robert E. Schapire
We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new...
Abstract. We introduce and study a general, abstract game played between two players called the shepherd and the adversary. The game is played in a series of rounds using a finite set of...
Bayesian Aggregation for Hierarchical Classification (2007)
Zafer Barutcuoglu, Robert E. Schapire, Olga G. Troyanskaya, Christopher R. Decoro
Large numbers of overlapping classes are found to be organized in hierarchies in many domains. In multi-label classification over such a hierarchy, members of a class must also belong to all of its...
Sensitivity of predictive species distribution models to change in grain size (2007)
Guisan, Antoine, Graham, Catherine H., Elith, Jane, Huettmann, Falk, Dudik, Miro, Ferrier, Simon, ...
Predictive species distribution modelling (SDM) has become an essential tool in biodiversity conservation and management. The choice of grain size (resolution) of environmental layers used in...
Novel methods improve prediction of species' distributions from occurrence data (2006)
Elith, Jane, Graham, Catherine H., Anderson, Robert P., Dudik, Miroslav, Ferrier, Simon, Guisan, Antoine, ...
Prediction of species' distributions is central to diverse applications in ecology, evolution and conservation science. There is increasing electronic access to vast sets of occurrence records in...
Maximum Entropy Correlated Equilibria (2006)
Ortiz, Luis E., Schapire, Robert E., Kakade, Sham M.
We study maximum entropy correlated equilibria in (multi-player)games and provide two gradient-based algorithms that are guaranteedto converge to such equilibria. Although we do not...
Maximum Entropy Correlated Equilibria (2006)
Ortiz, Luis E., Schapire, Robert E., Kakade, Sham M.
We study maximum entropy correlated equilibria in (multi-player)games and provide two gradient-based algorithms that are guaranteedto converge to such equilibria. Although we do not...
On Reoptimizing Multi-Class Classifiers (2006)
Deng, Kun, Bourke, Chris, Scott, Stephen, Schapire, Robert E., Vinodchandran, N. V.
Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously learned classifier to work under new conditions. We study the...
Novel methods improve prediction of species' distributions from occurrence data (2006)
Elith, Jane, Graham, Catherine H., Anderson, Robert P., Dudik, Miroslav, Ferrier, Simon, Guisan, Antoine, ...
Prediction of species' distributions is central to diverse applications in ecology, evolution and conservation science. There is increasing electronic access to vast sets of occurrence records in...
Novel methods improve prediction of species' distributions from occurrence data (2006)
Elith, Jane, Graham, Catherine H., Anderson, Robert P., Dudik, Miroslav, Ferrier, Simon, Guisan, Antoine, ...
Prediction of species' distributions is central to diverse applications in ecology, evolution and conservation science. There is increasing electronic access to vast sets of occurrence records in...
On Reoptimizing Multi-Class Classifiers ∗ (2006)
Kun Deng, Chris Bourke, Stephen D. Scott, Robert E. Schapire, N. V. Vinodch
Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously learned classifier to work under new conditions. We study the...
On Reoptimizing Multi-Class Classifiers ∗ (2006)
Kun Deng, Chris Bourke, Stephen D. Scott, Robert E. Schapire, N. V. Vinodch
Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously learned classifier to work under new conditions. We study the...
Jane Elith, Catherine H. Graham, Robert P. Anderson, Miroslav Dudík, Simon Ferrier, Antoine Guisan, ...
methods improve prediction of species ’ distributions from
How boosting the margin can also boost classifier complexity (2006)
Lev Reyzin, Robert E. Schapire
Boosting methods are known not to usually overfit training data even as the size of the generated classifiers becomes large. Schapire et al. attempted to explain this phenomenon in terms of the...
Hierarchical multi-label prediction of gene function (2006)
Barutcuoglu, Zafer, Schapire, Robert E., Troyanskaya, Olga G.
Motivation: Assigning functions for unknown genes based on diverse large-scale data is a key task in functional genomics. Previous work on gene function prediction has addressed this problem using...
CSE 254 Seminar in learning algorithms (2005)
Given a training set T, the classification task is to learn a functional relationship between the feature vector x and the class label y. A two class example, in a two-dimensional feature-space is...
Margin-based ranking meets boosting in the middle (2005)
Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E. Schapire
Abstract. We present a margin-based bound for ranking in a general setting, using the L ∞ covering number of the hypothesis space as our complexity measure. Our bound suggests that ranking...
Generalization bounds for averaged classifiers (2004)
Freund, Yoav, Mansour, Yishay, Schapire, Robert E.
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, that is, the hypothesis that minimizes the training error, our...
Generalization bounds for averaged classifiers (2004)
Freund, Yoav, Mansour, Yishay, Schapire, Robert E.
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, that is, the hypothesis that minimizes the training error, our...
Discussions of boosting papers, and rejoinders (2004)
Bartlett, Peter L., Bickel, Peter J., Bühlmann, Peter, Freund, Yoav, Friedman, Jerome, Hastie, Trevor, ...
Discussions of: "Process consistency for AdaBoost" [Ann. Statist. 32 (2004), no. 1, 13-29] by W. Jiang; "On the Bayes-risk consistency of regularized boosting methods" [ibid., 30-55] by G. Lugosi and...
A maximum entropy approach to species distribution modeling (2004)
Steven J. Phillips, Miroslav Dudk, Robert E. Schapire
We study the problem of modeling species geographic distributions, a critical problem in conservation biology. We propose the use of maximum-entropy techniques for this problem, specifically,...
The dynamics of adaboost: Cyclic behavior and convergence of margins (2004)
Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire
In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach...
Performance guarantees for regularized maximum entropy density estimation (2004)
Miroslav Dudík, Steven J. Phillips, Robert E. Schapire
Abstract. We consider the problem of estimating an unknown probability distribution from samples using the principle of maximum entropy (maxent). To alleviate overfitting with a very large number of...
A maximum entropy approach to species distribution modeling (2004)
Steven J. Phillips, Miroslav Dudík, Robert E. Schapire
We study the problem of modeling species geographic distributions, a critical problem in conservation biology. We propose the use of maximum-entropy techniques for this problem, specifically,...
The dynamics of adaboost: Cyclic behavior and convergence of margins (2004)
Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire, Dana Ron
In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach...
An Efficient Boosting Algorithm for Combining Preferences (2003)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer, G. Dietterich
We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several...
Active Learning For Spoken Language Understanding (2003)
Gokhan Tur, Robert E. Schapire, Dilek Hakkani-Tür
In this paper, we describe active learning methods for reducing the labeling effort in a statistical call classification system. Active learning aims to minimize the number of labeled utterances by...
Active Learning For Spoken Language Understanding (2003)
Gokhan Tur Robert, Robert E. Schapire, Dilek Hakkani-tür
In this paper, we describe active learning methods for reducing the labeling effort in a statistical call classification system. Active learning aims to minimize the number of labeled utterances by...
On the Dynamics of Boosting (2003)
Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire
In order to understand AdaBoost's dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional...
ATTac-2001: A learning, autonomous bidding agent (2002)
Peter Stone, Robert E. Schapire, János A. Csirik, Michael L. Littman, David Mcallester
Abstract. Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This paper presents a general approach to building autonomous bidding agents to...
The nonstochastic multiarmed bandit problem (2002)
Peter Auer, Nicolò Cesa-bianchi, Yoav Freund, Robert E. Schapire
In the multi-armed bandit problem, a gambler must decide which arm of £ non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
A Generalization of Principal Component Analysis to the Exponential Family (2002)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
The nonstochastic multiarmed bandit problem (2002)
Peter Auer, Yoav Freund, Robert E. Schapire
Abstract. In the multiarmed bandit problem, a gambler must decide which arm of K nonidentical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
www.research.att.com / schapire
www.research.att.com / schapire
A generalization of principal component analysis to the exponential family (2001)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
A generalization of principal component analysis to the exponential family (2001)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
A generalization of principal component analysis to the exponential family (2001)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
A generalization of principal component analysis to the exponential family (2001)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
Learning Theory and Language Modeling (2001)
David Mcallester, Robert E. Schapire
Here we consider some of our recent work on Good-Tuing estimators in the larger context of learning theory and language modeling. The Good-turing estimators have played a significant role in natural...
Why averaging classifiers can protect against overfitting (2001)
Yoav Freund, Yishay Mansour, Robert E. Schapire
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, this algorithm predicts with a weighted average of all...
A generalization of principal component analysis to the exponential family (2001)
Michael Collins, Sanjoy Dasgupta, Robert E. Schapire
Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not...
www.research.att.com / ¡ schapire
www.research.att.com / schapire
www.research.att.com / schapire
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Logistic regression, adaboost and bregman distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
Abstract. We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two...
BoosTexter: a boosting-based system for text categorization (2000)
Robert E. Schapire, Yoram Singer
Abstract. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting...
Boosting for Document Routing (2000)
Raj Iyer, David Lewis, Robert E. Schapire, Yoram Singer, Amit Singhal
RankBoost is a recently proposed algorithm for learning ranking functions. It is simple to implement and has strong justifications from computational learning theory. We describe the algorithm and...
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
. We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in...
Why Averaging Classifiers Can Protect Against Overfitting (2000)
Yoav Freund, Yishay Mansour, Robert E. Schapire
We study a simple learning algorithm for binary classification. Instead of predicting with the best hypothesis in the hypothesis class, this algorithm predicts with a weighted average of all...
On the Convergence Rate of Good-Turing Estimators (2000)
David Mcallester, Robert E. Schapire
Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...
Jerome Friedman, Trevor Hastie, Yoav Freund, Robert E. Schapire
this paper is in establishing a connection between boosting, a newcomer to the statistics scene, and additive models.
On the Convergence Rate of Good-Turing Estimators (2000)
David Mcallester Robert, Robert E. Schapire
Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...
On the Convergence Rate of Good-Turing Estimators (2000)
David Mcallester Robert, Robert E. Schapire
Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
Reducing multiclass to binary: A unifying approach for margin classifiers (2000)
Erin L. Allwein, Robert E. Schapire, Yoram Singer, Pack Kaelbling
We present a unifying framework for studying the solution of multiclass categorization problems by reducing them to multiple binary problems that are then solved using a margin-based binary learning...
Logistic Regression, AdaBoost and Bregman Distances (2000)
Michael Collins, Robert E. Schapire, Yoram Singer
We give a unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances. The striking similarity of the two problems in this...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Yoav Freund, Robert E. Schapire
yoav, schapire¡ We present a simple algorithm for playing a repeated game. We show that a player using this algorithm suffers average loss that is guaranteed to come close to the minimum loss...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the form of preference...
Boosting Applied to Tagging and PP Attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
Improved Boosting Algorithms Using Confidence-rated Predictions (1999)
Robert E. Schapire, Yoram Singer
. We describe several improvements to Freund and Schapire's AdaBoost boosting algorithm, particularly in a setting in which hypotheses may assign confidences to each of their predictions. We...
Learning to Order Things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
Improved Boosting Algorithms Using Confidence-rated Predictions (1999)
Robert E. Schapire, Yoram Singer
. We describe several improvements to Freund and Schapire's AdaBoost boosting algorithm, particularly in a setting in which hypotheses may assign confidences to each of their predictions. We...
A Short Introduction to Boosting (1999)
Yoav Freund, Robert E. Schapire
Boosting is a general method for improving the accuracy of any given learning algorithm. This short overview paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of...
Boosting Applied to Tagging and PP Attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
We introduce and study a general, abstract game played between two players called the drifter and the adversary. The game is played in a series of rounds using a finite set of "chips" which...
Theoretical Views of Boosting (1999)
. Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, we briefly survey theoretical work on boosting including...
A Brief Introduction to Boosting (1999)
Boosting is a general method for improving the accuracy of any given learning algorithm. This short paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting,...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
wcohen,schapire,singer¡ There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the...
Boosting applied to tagging and PP attachment (1999)
Steven Abney, Robert E. Schapire, Yoram Singer
Boosting is a machine learning algorithm that is not well known in computational linguistics. We apply it to part-of-speech tagging and prepositional phrase attachment. Performance is very...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
Theoretical Views of Boosting and Applications (1999)
. Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, we briefly survey theoretical work on boosting including...
Learning to order things (1999)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order, given feedback in the form of preference...
Algorithms for Portfolio Management based on the Newton Method (1999)
Amit Agarwal, Elad Hazan, Satyen Kale, Robert E. Schapire
We experimentally study on-line investment algorithms first proposed by Agarwal and Hazan and extended by Hazan et al. which achieve almost the same wealth as the best constant-rebalanced portfolio...
The Strength of Weak Learnability. (1998)
The problem considered is that of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class is learnable (or strongly...
Learning Binary Relations and Total Orders. (1998)
Goldman, Sally A., Rivest, Ronald L., Schapire, Robert E.
Learning a binary relation between two sets of objects or between a set and itself represents a binary relation between a set of size n and a set of size m as an n x m matrix of bits, whose (i,j)...
The Emerging Theory of Average-Case Complexity. (1998)
A primary contribution of theoretical computer science has been the identification of the so-called NP-complete problems, a well-known class of problems provably equivalent to one another in...
The Design and Analysis of Efficient Learning Algorithms. (1998)
This thesis explores various theoretical aspects of machine learning with particular emphasis on techniques for designing and analyzing computationally efficient learning algorithms. Many of the...
Boosting the margin: a new explanation for the effectiveness of voting methods (1998)
Bartlett, Peter, Freund, Yoav, Lee, Wee Sun, Schapire, Robert E.
One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and often...
Boosting and Rocchio Applied to Text Filtering (1998)
Robert E. Schapire, Yoram Singer, Amit Singhal
We discuss two learning algorithms for text filtering: modified Rocchio and a boosting algorithm called AdaBoost. We show how both algorithms can be adapted to maximize any general utility matrix...
Discussion of the Paper ‘Arcing Classifiers’ by Leo Breiman (1998)
Yoav Freund, Robert E. Schapire
We would like to thank Leo Breiman for his interest in our work on boosting, for his extensive experiments with the AdaBoost algorithm (which he calls arc-fs) and for his very generous exposition of...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
Boosting the margin: a new explanation for the effectiveness of voting methods (1998)
Robert E. Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee
Abstract. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large,...
Discussion of the paper "Arcing Classifiers" by leo breiman (1998)
Yoav Freund, Robert E. Schapire
We would like to thank Leo Breiman for his interest in our work on boosting, for his extensive experiments with the AdaBoost algorithm (which he calls arc-fs) and for his very generous exposition of...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
. The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
Boosting the margin: a new explanation for the effectiveness of voting methods (1998)
Robert E. Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee
Abstract. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large,...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (1998)
Robert E. Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee
. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large, and...
Learning to Order Things (1998)
William W. Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
. The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
BoosTexter: A System for Multiclass Multi-label Text Categorization (1998)
Robert E. Schapire, Yoram Singer
This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. We first show how to extend the standard notion of classification by allowing...
Large Margin Classification Using the Perceptron Algorithm (1998)
Yoav Freund, Robert E. Schapire
We introduce and analyze a new algorithm for linear classification which combines Rosenblatt 's perceptron algorithm with Helmbold and Warmuth's leave-one-out method. Like Vapnik 's...
An Efficient Boosting Algorithm for Combining Preferences (1998)
Yoav Freund, Raj Iyer, Robert E. Schapire, Yoram Singer
The problem of combining preferences arises in several applications, such as combining the results of different search engines. This work describes an efficient algorithm for combining multiple...
On-Line Portfolio Selection Using Multiplicative Updates (1998)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Gambling in a Rigged Casino: The adversarial multi-armed bandit problem (1998)
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire
In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
Yoav Freund Center, Yoav Freund, G. Dietterich, C○ Yoav Freund, Raj Iyer, Raj Iyer, ...
We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several...
Peter Auer, Yoav Freund, Robert E. Schapire, Nicolò Cesa-bianchi
In the multi-armed bandit problem, a gambler must decide which of £ arm non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
Boosting the margin: a new explanation for the effectiveness of voting methods (1998)
Robert E. Schapire, Yoav Freund
Abstract. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated hypothesis usually does not increase as its size becomes very large,...
Boosting the margin: a new explanation for the effectiveness of voting methods (1998)
Robert E. Schapire, Peter Bartlett, Yoav Freund, Wee Sun Lee
Abstract. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated classifier usually does not increase as its size becomes very large,...
On-line portfolio selection using multiplicative updates (1998)
David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Predicting nearly as well as the best pruning of a decision tree (1997)
David P. Helmbold, Robert E. Schapire
Abstract. Many algorithms for inferring a decision tree from data involve a two-phase process: First, a very large decision tree is grown which typically ends up "over-fitting " the...
Predicting nearly as well as the best pruning of a decision tree (1997)
David P. Helmbold, Robert E. Schapire
Many algorithms for inferring a decision tree from data involve a two-phase process: First, a very large decision tree is grown which typically ends up "over-fitting " the data. To...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (1997)
Robert E. Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee
. One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated hypothesis usually does not increase as its size becomes very large, and...
Using Output Codes to Boost Multiclass Learning Problems (1997)
. This paper describes a new technique for solving multiclass learning problems by combining Freund and Schapire's boosting algorithm with the main ideas of Dietterich and Bakiri's method...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1997)
Yoav Freund, Robert E. Schapire
In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a...
Using and Combining Predictors That Specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
How to Use Expert Advice (1997)
Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, Manfred K. Warmuth
this paper we show that some simple prediction algorithms are optimal for this task in a sense that is closely related to the definitions of universal forecasting, prediction, and data compression...
How to Use Expert Advice (1997)
Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, Manfred K. Warmuth
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts. Our analysis is for worst-case situations, i.e., we make no...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (1997)
Robert E. Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee
One of the surprising recurring phenomena observed in experiments with boosting is that the test error of the generated hypothesis usually does not increase as its size becomes very large, and often...
Using and Combining Predictors That Specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called "experts." These simple algorithms belong to...
Learning to Order Things (1997)
William Cohen, Robert E. Schapire, Yoram Singer
There are many applications in which it is desirable to order rather than classify instances. Here we consider the problem of learning how to order instances given feedback in the form of preference...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1997)
Yoav Freund, Robert E. Schapire
. We consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the...
Discussion of the paper "Arcing Classifiers" by Leo Breiman (1997)
Yoav Freund, Robert E. Schapire
this paper, Breiman uses boosting-by-resampling, instead of boosting-by-reweighting and in this way combines the two methods.
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1997)
Yoav Freund, Robert E. Schapire
In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1997)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Using and combining predictors that specialize (1997)
Yoav Freund, Robert E. Schapire, Yoram Singer
Abstract. We study online learning algorithms that predict by combining the predictions of several subordinate prediction algorithms, sometimes called “experts. ” These simple algorithms belong...
A comparison of new and old algorithms for a mixture estimation Problem (1997)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth, M. Long
Abstract. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for...
Experiments with a New Boosting Algorithm (1996)
Yoav Freund, Robert E. Schapire
Abstract. In an earlier paper, we introduced a new "boosting" algorithm called AdaBoost which, theoretically, can be used to significantly reduce the error of any learning algorithm...
Game Theory, On-line Prediction and Boosting (1996)
Yoav Freund, Robert E. Schapire
We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Training Algorithms for Linear Text Classifiers (1996)
David Lewis, Robert E. Schapire, James P. Callan, Ron Papka
Systems for text retrieval, routing, categorization and other IR tasks rely heavily on linear classifiers. We propose that two machine learning algorithms, the Widrow-Hoff and EG algorithms, be used...
Yoav Freund Att, Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
Yoav Freund Att, Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, ...
We study the problem of efficiently learning to play a game optimally against an unknown adversary chosen from a computationally bounded class. We both contribute to the line of research on playing...
On the Worst-case Analysis of Temporal-difference Learning Algorithms (1996)
Robert E. Schapire, Manfred K. Warmuth, Pack Kaelbling
. We study the behavior of a family of learning algorithms based on Sutton's method of temporal differences. In our on-line learning framework, learning takes place in a sequence of trials, and...
Experiments with a New Boosting Algorithm (1996)
Yoav Freund, Robert E. Schapire
In an earlier paper [9], we introduced a new "boosting" algorithm called AdaBoost which, theoretically, can be used to significantly reduce the error of any learning algorithm that...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
Training Algorithms for Linear Text Classifiers (1996)
David Lewis, Robert E. Schapire, James P. Callan, Ron Papka
Systems for text retrieval, routing, categorization and other IR tasks rely heavily on linear classifiers. We propose that two machine learning algorithms, the Widrow-Hoff and EG algorithms, be used...
Training Algorithms for Linear Text Classifiers (1996)
David D. Lewis, Robert E. Schapire, James P. Callan, Ron Papka
Systems for text retrieval, routing, categorization and other IR tasks rely heavily on linear classifiers. We propose that two machine learning algorithms, the Widrow-Hoff and EG algorithms, be used...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
On-Line Portfolio Selection Using Multiplicative Updates (1996)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
We study the problem of efficiently learning to play a game optimally against an unknown adversary chosen from a computationally bounded class. We both contribute to the line of research on playing...
Yoav Freund, Ronitt Rubinfeld, Michael Kearns, Robert E. Schapire, Dana Ron, Linda Sellie
This paper describes new and e cient algorithms for learning deterministic nite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to model...
Experiments with a New Boosting Algorithm DRAFT — PLEASE DO NOT DISTRIBUTE (1996)
Yoav Freund, Robert E. Schapire
In an earlier paper [9], we introduced a new “boosting ” algorithm called AdaBoost which, theoretically, can be used to significantly reduce the error of any learning algorithm that consistently...
On-line portfolio selection using multiplicative updates (1996)
David P. Helmbold, Yoram Singer, Robert E. Schapire, Manfred K. Warmuth
We present an on-line investment algorithm which achieves almost the same wealth as the best constant-rebalanced portfolio determined in hindsight from the actual market outcomes. The algorithm...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1995)
Peter Auer, Yoav Freund, Robert E. Schapire
In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
How to Use Expert Advice (1995)
Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, Manfred K. Warmuth
this paper we show that some simple prediction algorithms are optimal for this task in a sense that is closely related to the definitions of universal forecasting, prediction, and data compression...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1995)
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire
In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
this paper. Our experimental evidence suggests that setting j ? 1 results in a more effective update. These results agree with the infinitesimal analysis in the limit of n !1 based on a stochastic...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1995)
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, Robert E. Schapire
In the multi-armed bandit problem, a gambler must decide which arm of K non-identical slot machines to play in a sequence of trials so as to maximize his reward. This classical problem has received...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Robert E. Schapire
this paper, games are played by two players. One will be called the adversary and the other the strategy learning algorithm. We think of the adversary as a fixed resource-bounded computational...
A Comparison of New and Old Algorithms for A Mixture Estimation Problem (1995)
David P. Helmbold, Robert E. Schapire, Yoram Singer, Manfred K. Warmuth
. We investigate the problem of estimating the proportion vector which maximizes the likelihood of a given sample for a mixture of given densities. We adapt a framework developed for supervised...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1995)
Yoav Freund, Robert E. Schapire
. We consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a broad, abstract extension of the...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1995)
Yoav Freund, Robert E. Schapire
In the first part of the paper we consider the problem of dynamically apportioning resources among a set of options in a worst-case on-line framework. The model we study can be interpreted as a...
On the Learnability of Discrete Distributions (Extended Abstract) (1994)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
On the Learnability of Discrete Distributions (Extended Abstract) (1994)
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
this paper, we concentrate on discrete distributions over f0; 1g
Toward Efficient Agnostic Learning (1994)
Michael Kearns, Robert E. Schapire, Linda M. Sellie, Lisa Hellerstein
. In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Robert E. Schapire, Ronald L. Rivest
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n m matrix...
Learning sparse multivariate polynomials over a field with queries and counterexamples (1993)
Robert E. Schapire, Linda M. Sellie
Abstract. We consider the problem of learning a polynomial over an arbitrary field F defined on a set of boolean variables. We present the first provably effective algorithm for exactly identifying...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n \Theta m...
Exact Identification of Read-once Formulas Using Fixed Points of Amplification Functions (1993)
Sally A. Goldman, Michael J. Kearns, Robert E. Schapire
In this paper we describe a new technique for exactly identifying certain classes of read-once Boolean formulas. The method is based on sampling the input-output behavior of the target formula on a...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Yoav Freund Att, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
This paper describes new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to...
Efficient Learning of Typical Finite Automata from Random Walks (Extended Abstract) (1993)
Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
) Yoav Freund University of California Santa Cruz, CA 95064 Michael Kearns AT&T Bell Laboratories Murray Hill, NJ 07974 Dana Ron Hebrew University Jerusalem 91904, Israel Ronitt Rubinfeld Cornell...
Exact Identification of Read-once Formulas Using Fixed Points of Amplification Functions (1993)
Sally Goldman, Michael J. Kearns, Robert E. Schapire
In this paper we describe a new technique for exactly identifying certain classes of read-once Boolean formulas. The method is based on sampling the input-output behavior of the target formula on a...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund AT&T Research Murray Hill, NJ 07974 Michael Kearns AT&T Research Murray Hill, NJ 07974 Dana Ron MIT Cambridge, MA 02138 Ronitt Rubinfeld Cornell University Ithaca, NY 14853...
Efficient Distribution-free Learning of Probabilistic Concepts (1993)
Michael J. Kearns, Robert E. Schapire
In this paper we investigate a new formal model of machine learning in which the concept (boolean function) to be learned may exhibit uncertain or probabilistic behavior---thus, the same input may...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
This paper describes new and efficient algorithms for learning deterministic finite automata. Our approach is primarily distinguished by two features: (1) the adoption of an average-case setting to...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund University of California Santa Cruz, CA 95064 Michael Kearns AT&T Bell Laboratories Murray Hill, NJ 07974 Dana Ron Hebrew University Jerusalem 91904, Israel Ronitt Rubinfeld Cornell...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Robert E. Schapire, Ronald L. Rivest
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n m matrix...
Ronald L. Rivest, Robert E. Schapire
We present new procedures for inferring the structure of a nite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new...
On the Sample Complexity of Weakly Learning (1992)
Sally A. Goldman, Michael J. Kearns, Robert E. Schapire
In this paper, we study the sample complexity of weak learning. That is, we ask how much data must be collected from an unknown distribution in order to extract a small but significant advantage in...
Toward efficient agnostic learning (1992)
Michael J. Kearns, Robert E. Schapire, Linda M. Sellie
In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The...
Sally A. Goldman, Robert E. Schapire, Michael J. Kearns
In this paper we describe a new technique for exactly identifying certain classes of read-once Boolean formulas. The method is based on sampling the input-output behavior of the target formula on a...
The design and analysis of efficiency learning algorithms /--Robert Elias Schapire. (1991)
Cover title.
The design and analysis of efficient learning algorithms / (1991)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1991.
Exact Identification of Circuits Using Fixed Points of Amplification Functions (1990)
Sally A. Goldman, Michael J. Kearns, Robert E. Schapire
Abstract. In this paper we describe a new technique for ezactly identifying certain classes of read-once Boolean for-mulas. The method is based on sampling the input-output behavior of the target...
The strength of weak learnability (1990)
Abstract. This paper addresses the problem of improving the accuracy of an hypothesis output by a learning algorithm in the distribution-free (PAC) learning model. A concept class is learnable (or...
Efficient distribution-free learning of probabilistic concepts (1990)
Michael J. Kearns, Robert E. Schapire
In this paper we investigate a new formal model of machine learning in which the concept (boolean function) to be learned may exhibit uncertain or probabilistic behavior -- thus, the same input may...
Diversity-based inference of finite automata /--by Robert Elias Schapire. (1988)
Supervised by Ronald L. Rivest.
Adaptive Game Playing Using Multiplicative Weights
Yoav Freund, Robert E. Schapire
this paper, we present a simple algorithm for solving this problem, and give a simple analysis of the algorithm. The bounds we obtain are not asymptotic and hold for any finite number of rounds. The...
BoosTexter: A Boosting-based System for Text Categorization
Robert E. Schapire, Yoram Singer
. This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting algorithms. We...
Aneuploidy prediction and tumor classification with heterogeneous hidden conditional random fields
Barutcuoglu, Zafer, Airoldi, Edoardo M., Dumeaux, Vanessa, Schapire, Robert E., Troyanskaya, Olga G.
Motivation: The heterogeneity of cancer cannot always be recognized by tumor morphology, but may be reflected by the underlying genetic aberrations. Array comparative genome hybridization (array-CGH)...