A new Hedging algorithm and its application to inferring latent random variables (2008)
We present a new online learning algorithm for cumulative discounted gain. This learning algorithm does not use exponential weights on the experts. Instead, it uses a weighting scheme that depends on...
Random projection trees for vector quantization (2008)
Dasgupta, Sanjoy, Freund, Yoav
A simple and computationally efficient scheme for tree-structured vector quantization is presented. Unlike previous methods, its quantization error depends only on the intrinsic dimension of the data...
Motif Discovery through Predictive Modeling of Gene Regulation (2007)
Middendorf, Manuel, Kundaje, Anshul, Shah, Mihir, Freund, Yoav, Wiggins, Chris H., Leslie, Christina
We present MEDUSA, an integrative method for learning motif models of transcription factor binding sites by incorporating promoter sequence and gene expression data. We use a modern large-margin...
Identifying metabolic enzymes with multiple types of association evidence (2006)
Kharchenko, Peter, Chen, Lifeng, Freund, Yoav, Vitkup, Dennis, Church, George M
Abstract Background Existing large-scale metabolic models of sequenced organisms commonly include enzymatic functions which can not be attributed to any gene in that organism. Existing computational...
A classification-based framework for predicting and analyzing gene regulatory response (2006)
Kundaje, Anshul, Middendorf, Manuel, Shah, Mihir, Wiggins, Chris H, Freund, Yoav, Leslie, Christina
Abstract Background We have recently introduced a predictive framework for studying gene transcriptional regulation in simpler organisms using a novel supervised learning algorithm called GeneClass....
Predicting Genetic Regulatory Response Using Classification (2004)
Middendorf, Manuel, Kundaje, Anshul, Wiggins, Chris, Freund, Yoav, Leslie, Christina
We present a novel classification-based method for learning to predict gene regulatory response. Our approach is motivated by the hypothesis that in simple organisms such as Saccharomyces cerevisiae,...
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...
Predicting Genetic Regulatory Response using Classification: Yeast Stress Response (2004)
Middendorf, Manuel, Kundaje, Anshul, Wiggins, Chris, Freund, Yoav, Leslie, Christina
We present a novel classification-based algorithm called GeneClass for learning to predict gene regulatory response. Our approach is motivated by the hypothesis that in simple organisms such as...
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...
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...
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...
Unsupervised Improvement of Visual Detectors using Co-Training (2003)
Anat Levin, Paul Viola, Yoav Freund
One significant challenge in the construction of visual detection systems is the acquisition of sufficient labeled data. This paper describes a new technique for training visual detectors which...
Continuous Drifting Games (2002)
We combine the results of [13] and [8] and derive a continuous variant of a large class of drifting games. Our analysis furthers the understanding of the relationship between boosting, drifting games...
An Adaptive Version of the Boost By Majority Algorithm (2002)
We propose a new boosting algorithm. This boosting algorithm is an adaptive version of the boost by majority algorithm and combines bounded goals of the boost by majority algorithm with the...
The Alternating Decision Tree Learning Algorithm (2002)
The application of boosting procedures to decision tree algorithms has been shown to produce very accurate classifiers. These classifiers are in the form of a majority vote over a number of decision...
The Non-Stochastic Multi-Armed Bandit Problem (2001)
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...
Experiments with a New Boosting Algorithm (2001)
Yoav Freund, Robert E. Schapire
. 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 that consistently...
Selective Sampling Using the Query by Committee Algorithm (2001)
Yoav Freund, Eli Shamir, David Haussler
. We analyze the "query by committee" algorithm, a method for filtering informative queries from a random stream of inputs. We show that if the two-member committee algorithm achieves information...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, 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...
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...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (2001)
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...
Discussion of the paper "Arcing Classifiers" by Leo Breiman (2001)
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 (2001)
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...
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...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (2000)
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...
An Efficient Boosting Algorithm for Combining Preferences (2000)
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...
Game Theory, On-line Prediction and Boosting (2000)
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...
Continuous Drifting Games (2000)
We combine the results of [5] and [3] and derive a continuous variant of a large class of drifting games. Our analysis furthers the understanding of the relationship between boosting, drifting games...
Analysis of a Pseudo-Bayesian Prediction Method (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...
Gambling in a Rigged Casino: (2000)
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...
Estimating a Mixture of Two Product Distributions (1999)
We describe an efficient algorithm for estimating a mixture of two product distributions over binary vectors. 1 Introduction There are two major lines in research in Machine learning, supervised...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1999)
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 Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1999)
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...
Selective sampling using the Query by Committee algorithm (1999)
Yoav Freund, H. Sebastian Seung, Eli Shamir, Naftali Tishby
We analyze the "query by committee" algorithm, a method for filtering informative queries from a random stream of inputs. We show that if the two-member committee algorithm achieves information gain...
How to Use Expert Advice (1999)
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...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, 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...
Efficient Learning of Typical Finite Automata from Random Walks (1999)
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...
Unsupervised Learning of Distributions on Binary Vectors Using Two Layer Networks (1999)
this paper is related to both of these lines of work and has some advantages over each of them. If we find a good model of the distribution, we can tackle other interesting learning problems, such as...
An Efficient Boosting Algorithm for Combining Preferences (1999)
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...
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, 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...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (1999)
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...
Discussion of the paper "Arcing Classifiers" by Leo Breiman (1999)
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.
Efficient Learning of Typical Finite Automata from Random Walks (1999)
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...
Learning to Model Sequences Generated By Switching Distributions (1999)
We study efficient algorithms for solving the following problem, which we call the switching distributions learning problem. A sequence S = oe 1 oe 2 : : : oe n , over a finite alphabet Sigma is...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1999)
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 Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1999)
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...
Adaptive Game Playing Using Multiplicative Weights (1999)
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...
Game Theory, On-line Prediction and Boosting (1999)
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...
Using and Combining Predictors That Specialize (1999)
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 the...
Large Margin Classification Using the Perceptron Algorithm (1999)
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 maximal-margin...
Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods (1999)
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...
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 maximal-margin...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1998)
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...
Selective sampling using the Query by Committee algorithm (1998)
. We analyze the "query by committee" algorithm, a method for filtering informative queries from a random stream of inputs. We show that if the two-member committee algorithm achieves information...
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...
Using and Combining Predictors That Specialize (1998)
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 the...
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...
Using and Combining Predictors That Specialize (1998)
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 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 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 hypothesis usually does not increase as its size becomes very large, and...
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...
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...
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 hypothesis usually does not increase as its size becomes very large, and...
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...
Discussion of the paper "Arcing Classifiers" by Leo Breiman (1998)
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.
Self Bounding Learning Algorithms (1998)
Most of the work which attempts to give bounds on the generalization error of the hypothesis generated by a learning algorithm is based on methods from the theory of uniform convergence. These bounds...
Experiments with a New Boosting Algorithm (1998)
Yoav Freund, Robert E. Schapire
. 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 that consistently...
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...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1998)
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...
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1998)
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...
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...
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...
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...
A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1998)
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 Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting (1998)
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...
How to Use Expert Advice (1998)
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...