(eligible for best student paper) (2009)
Jacob Abernethy, Manfred K. Warmuth, Joel Yellin
We analyze a sequential game between a Gambler and a Casino. The Gambler allocates bets from a limited budget over a fixed menu of gambling events that are offered at equal time intervals. The Casino...
Tracking a small set of experts by mixing past posteriors (2009)
Olivier Bousquet, Manfred K. Warmuth, M. Long
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts....
Optimal Strategies from Random Walks (2009)
Jacob Abernethy, Manfred K. Warmuth, Joel Yellin
We analyze a sequential game between a Gambler and a Casino. The Gambler allocates bets from a limited budget over a fixed menu of gambling events that are offered at equal time intervals, and the...
Online Rotation Problem: (2009)
Adam M. Smith, Manfred K. Warmuth
Many different matrix classes have been tackled recently using online learning techniques, but at least one major class has been left out: rotations. We pose the online learning of rotations as an...
Randomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension ∗ (2009)
Manfred K. Warmuth, Dima Kuzmin
We design an online algorithm for Principal Component Analysis. In each trial the current instance is centered and projected into a probabilistically chosen low dimensional subspace. The regret of...
Bayesian Generalized Probability Calculus for Density Matrices (2009)
Warmuth, Manfred K, Kuzmin, Dima
One of the main concepts in quantum physics is a density matrix, which is a symmetric positive definite matrix of trace one. Finite probability distributions can be seen as a special case when the...
Maximizing the Margin with Boosting Gunnar Rätsch ¡ (2008)
Abstract. AdaBoost produces a linear combination of weak hypotheses. It has been observed that the generalization error of the algorithm continues to improve even after all examples are classified...
Matrix Exponential Updates for On-line Learning and Bregman Projection (2008)
Koji Tsuda, Gunnar Rätsch, Manfred K. Warmuth
We address the problem of learning a positive definite matrix from examples. The central issue is to design parameter updates that preserve positive definiteness. We introduce an update based on...
Continuous Experts and the Binning Algorithm (2008)
Jacob Abernethy, John Langford, Manfred K. Warmuth
Abstract. We consider the design of online master algorithms for combining the predictions from a set of experts where the absolute loss of the master is to be close to the absolute loss of the best...
Exponentially many local minima for single (2008)
Peter Auer, Mark Herbster, Manfred K. Warmuth
neurons
Article No. IC972686 Efficient Learning with Virtual Threshold Gates* (2008)
Wolfgang Maass, Manfred K. Warmuth
E-mail: manfred cis.ucsc.edu We reduce learning simple geometric concept classes to learning disjunctions over exponentially many variables. We then apply an online algorithm called Winnow whose...
Jacob Abernethy, John Langford, Manfred K. Warmuth
Abstract. We consider the design of online master algorithms for combining the predictions from a set of experts where the absolute loss of the master is to be close to the absolute loss of the best...
Continuous Experts and the Binning Algorithm (2008)
Jacob Abernethy, John Langford, Manfred K. Warmuth
Abstract. We consider the design of online master algorithms for combining the predictions from a set of experts where the absolute loss of the master is to be close to the absolute loss of the best...
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...
The Australian National University (2008)
Manfred K. Warmuth, Pack Kaelbling
AdaBoost produces a linear combination of base hypotheses and predicts with the sign of this linear combination. It has been observed that the generalization error of the algorithm continues to...
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...
Manfred K. Warmuth, Karen Glocer, Friedrich Miescher, Max Planck Society
We present a novel boosting algorithm, called SoftBoost, designed for sets of binary labeled examples that are not necessarily separable by convex combinations of base hypotheses. Our algorithm...
Manfred K. Warmuth, Dima Kuzmin
We design an on-line algorithm for Principal Component Analysis. In each trial the current instance is projected onto a probabilistically chosen low dimensional subspace. The total expected quadratic...
Kohei Hatano, Manfred K. Warmuth
We investigate improvements of AdaBoost that can exploit the fact that the weak hypotheses are one-sided, i.e. either all its positive (or negative) predictions are correct. In particular, for any...
Jyrki Kivinen, Manfred K. Warmuth
We consider two algorithms for on-line prediction based on a linear model. The algorithms are the well-known gradient descent (GD) algorithm and a new algorithm, which we call EG \. They both...
Abstract. There are two main families of on-line algorithms depending on whether a relative entropy or a squared Euclidean distance is used as a regularizer. The difference between the two families...
Kohei Hatano, Manfred K. Warmuth
We investigate improvements of AdaBoost that can exploit the fact that the weak hypotheses are one-sided, i.e. either all its positive (or negative) predictions are correct. In particular, for any...
On the Convergence of Leveraging Gunnar Rätsch, (2008)
Sebastian Mika, Manfred K. Warmuth
We give an unified convergence analysis of ensemble learning methods including e.g. AdaBoost, Logistic Regression and the Least-Square-Boost algorithm for regression. These methods have in common...
Learning Permutations Learning Permutations with Exponential Weights ∗ (2008)
David P. Helmbold, Manfred K. Warmuth
We give an algorithm for the on-line learning of permutations. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic weight matrix, and uses an efficient method...
NeuroCOLT Coordinating Partner (2007)
Peter Auer, Mark Herbster, Manfred K. Warmuth
We show that for a single neuron with the logistic function as the transfer function the number of local minima of the error function based
Jyrki Kivinen, Manfred K. Warmuth
This paper addresses the familiar problem of predicting with a linear classifier . The
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...
Manfred K. Warmuth, Michael Mathieson, Christian Lemmen
We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing...
Efficient Margin Maximizing with Boosting* Gunnar RStsch (2007)
Manfred K. Warmuth, Pack Kaelbling
AdaBoost produces a linear combination of base hypotheses and predicts with the sign of this linear combination. It has been observed that the generalization error of the algorithm continues to...
Maximizing the Margin with Boosting Gunnar Rätsch ¡ (2007)
Abstract. AdaBoost produces a linear combination of weak hypotheses. It has been observed that the generalization error of the algorithm continues to improve even after all examples are classified...
The Australian National University (2007)
Manfred K. Warmuth, Pack Kaelbling
AdaBoost produces a linear combination of base hypotheses and predicts with the sign of this linear combination. It has been observed that the generalization error of the algorithm continues to...
Manfred K. Warmuth, Michael Mathieson, Jun Liao, Christian Lemmen
We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing...
Adaptive Caching by Refetching (View in Color) (2007)
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Br, Ismail Ari
We are constructing caching policies that have 13-20 % lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63 %...
Maximizing the Margin with Boosting* (2007)
Gunnar Rfitsch I, Manfred K. Warmuth
Abstract. AdaBoost produces a linear combination of weak hypotheses. It has been observed that the generalization error of the algorithm continues to improve even after all examples are classified...
DRAFT On the Convergence of Leveraging Gunnar Ratsch, (2007)
Sebastian Mika, Manfred K. Warmuth
We give an unified convergence analysis of ensemble learning methods including e.g. AdaBoost, Logistic Regression and the Least-Square-Boost algorithm for regression. These methods have in common...
The Distributed Bit Complexity of the Ring: (2007)
Vakgroep Nformatica, Hans L. Bodlaender, Hans L. Bodlaender, Hans L. Bodlaender, Shlomo Moran, Shlomo Moran, ...
From the Anonymous to the Non-anonymous Case
Manfred K. Warmuth, Michael Mathieson, Christian Lemmen
We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing...
and BIOwulf Technologies (2007)
Olivier Bousquet, Manfred K. Warmuth
Editor: In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n...
On the Convergence of Leveraging Gunnar R atsch, y (2007)
Sebastian Mika, Manfred K. Warmuth
We give an unified convergence analysis of ensemble learning methods including e.g. AdaBoost, Logistic Regression and the Least-SquareBoost algorithm for regression. These methods have in common that...
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...
Linear Hinge Loss and Average Margin Claudio Gentile (2007)
We describe a unifying method for proving relative loss bounds for online linear threshold classification algorithms, such as the Perceptron and the Winnow algorithms. For classification problems the...
Olivier Bousquet, Manfred K. Warmuth
Abstract. In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n...
Olivier Bousquet, Manfred K. Warmuth
Abstract. In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n...
in Neural and Computational Learning II, (2007)
Sebastian Mika, Manfred K. Warmuth, P. Spellucci, R. Israel, S. Lemm
For more information see the NeuroCOLT website
For more information see the NeuroCOLT website (2007)
Introduction 1 We give an unified convergence analysis of ensemble learning methods including e.g. AdaBoost, Logistic Regression and the Least-Square-Boost algorithm for regression. These methods...
Engineering proteinase K using machine learning and synthetic genes (2007)
Liao, Jun, Warmuth, Manfred K, Govindarajan, Sridhar, Ness, Jon E, Wang, Rebecca P, Gustafsson, Claes, ...
Abstract Background Altering a protein's function by changing its sequence allows natural proteins to be converted into useful molecular tools. Current protein engineering methods are limited by a...
Engineering proteinase K using machine learning and synthetic genes (2007)
Liao, Jun, Warmuth, Manfred K, Govindarajan, Sridhar, Ness, Jon E, Wang, Rebecca P, Gustafsson, Claes, ...
Abstract Background Altering a protein's function by changing its sequence allows natural proteins to be converted into useful molecular tools. Current protein engineering methods are limited by a...
Jun Liao, Manfred K Warmuth, Sridhar Govindarajan, Jon E Ness, Rebecca P Wang, Claes Gustafsson, ...
genes
Learning permutations with exponential weights (2007)
David P. Helmbold, Manfred K. Warmuth
Abstract. We give an algorithm for learning a permutation on-line. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic matrix. This matrix is updated by...
Randomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension (2007)
Manfred K. Warmuth, Dima Kuzmin
We design an online algorithm for Principal Component Analysis. In each trial the current instance is centered and projected into a probabilistically chosen low dimensional subspace. The regret of...
Online Kernel PCA with entropic matrix updates (2007)
Dima Kuzmin, Manfred K. Warmuth
A number of updates for density matrices have been developed recently that are motivated by relative entropy minimization problems. The updates involve a softmin calculation based on matrix logs and...
We generalize the Winnow algorithm for learning disjunctions to learning subspaces of low rank. Subspaces are represented by symmetric projection matrices. The online algorithm maintains its...
When is there a free matrix lunch (2007)
The “no-free lunch theorems ” essentially say that for any two algorithms A and B, there are “as many ” targets (or priors over targets) for which A has lower expected loss than B as...
Learning permutations with exponential weights (2007)
David P. Helmbold, Manfred K. Warmuth
We give an algorithm for learning a permutation on-line. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic matrix. This matrix is updated by multiplying the...
The p-norm generalization of the LMS algorithm for adaptive filtering (2006)
Kivinen, Jyrki, Warmuth, Manfred K., Hassibi, Babak
Recently much work has been done analyzing online machine learning algorithms in a worst case setting, where no probabilistic assumptions are made about the data. This is analogous to the H/sup /spl...
The p-norm generalization of the LMS algorithm for adaptive filtering (2006)
Kivinen, Jyrki, Warmuth, Manfred K., Hassibi, Babak
©2006 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale...
The p-Norm Generalization of the LMS Algorithm for Adaptive Filtering (2006)
Jyrki Kivinen, Manfred K. Warmuth, Babak Hassibi
Recently much work has been done analyzing online machine learning algorithms in a worst case setting, where no probabilistic assumptions are made about the data. This is analogous to the r setting...
Totally corrective boosting algorithms that maximize the margin (2006)
We consider boosting algorithms that maintain a distribution over a set of examples. At each iteration a weak hypothesis is received and the distribution is updated. We motivate these updates as...
Unlabeled compression schemes for maximum classes (2006)
Dima Kuzmin, Manfred K. Warmuth
Abstract. We give a compression scheme for any maximum class of VC dimension d that compresses any sample consistent with a concept in the class to at most d unlabeled points from the domain of the...
Online Variance Minimization (2006)
Manfred K. Warmuth, Dima Kuzmin
Abstract. We design algorithms for two online variance minimization problems. Specifically, in every trial t our algorithms get a covariance matrix Ct and try to select a parameter vector wt such...
Unlabeled compression schemes for maximum classes (2006)
Dima Kuzmin, Manfred K. Warmuth, John Shawe-taylor
Maximum concept classes of VC dimension d over n domain points have size � n � ≤d, and this is an upper bound on the size of any concept class of VC dimension d over n points. We give a...
Randomized PCA algorithms with regret bounds that are logarithmic in the dimension (2006)
Manfred K. Warmuth, Dima Kuzmin
We design an on-line algorithm for Principal Component Analysis. The instances are projected into a probabilistically chosen low dimensional subspace. The total expected quadratic approximation error...
Totally corrective boosting algorithms that maximize the margin (2006)
We consider boosting algorithms that maintain a distribution over a set of examples. At each iteration a weak hypothesis is received and the distribution is updated. We motivate these updates as...
The p-norm generalization of the LMS algorithm for adaptive filtering (2005)
Jyrki Kivinen, Manfred K. Warmuth, Babak Hassibi
Abstract: Recently much work has been done analyzing online machine learning algorithms in a worst case setting, where no probabilistic assumptions are made about the data. This is analogous to the H...
Abstract. We discuss a simple sparse linear problem that is hard to learn with any algorithm that uses a linear combination of the training instances as its weight vector. The hardness holds even if...
Bayes rule for density matrices (2005)
The classical Bayes rule computes the posterior model probability from the prior probability and the data likelihood. We generalize this rule to the case when the prior is a density matrix (symmetric...
Matrix exponentiated gradient updates for on-line learning and Bregman projections (2005)
Koji Tsuda, Gunnar Rätsch, Manfred K. Warmuth
We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von...
In cases where linear models are too simple, the following “kernel trick ” is commonly used for designing Machine Learning algorithms: Embed the instances into a high-dimensional feature space...
Matrix exponentiated gradient updates for on-line learning and Bregman projections (2005)
Koji Tsuda, Manfred K. Warmuth, Yoram Singer
We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von...
In cases where linear models are too simple, the following “kernel trick ” is commonly used for designing Machine Learning algorithms: Embed the instances into a high-dimensional feature space...
Matrix exponentiated gradient updates for on-line learning and Bregman projections (2005)
Koji Tsuda, Manfred K. Warmuth, Yoram Singer
We address the problem of learning a symmetric positive definite matrix. The central issue is to design parameter updates that preserve positive definiteness. Our updates are motivated with the von...
Abstract. We discuss a simple sparse linear problem that is hard to learn with any algorithm that uses a linear combination of the training instances as its weight vector. The hardness holds even if...
Classification with free energy at raised temperatures (2003)
Rita Singh, Manfred K. Warmuth, Bhiksha Raj, Paul Lamere
In this paper we describe a generalized classification method for HMM-based speech recognition systems, that uses free energy as a discriminant function rather than conventional probabilities. The...
Support vector machines for active learning in the drug discovery process (2003)
Manfred K. Warmuth, Jun Liao, Gunnar Rätsch, Michael Mathieson, Santosh Putta, Christian Lemmen
We investigate the following data mining problem from computer-aided drug design: From a large collection of compounds, find those that bind to a target molecule in as few iterations of biochemical...
Mitsubishi Electric Research Laboratories (2003)
Http Www Merl, Rita Singh, Rita Singh, Manfred K. Warmuth, Manfred K. Warmuth, Bhiksha Raj, ...
In this paper we describe a generalized classification method for HMM-based speech recognition systems, that uses free energy as a discriminant function rather than conventional probabilities.
Active learning with support vector machines in the drug discovery process (2003)
Manfred K. Warmuth, Jun Liao, Gunnar Rätsch, Michael Mathieson, Santosh Putta, Christian Lemmen
We investigate the following data mining problem from computer-aided drug design: From a large collection of compounds, find those that bind to a target molecule in as few iterations of biochemical...
Boosting versus Covering (2003)
Kohei Hatano Tokyo, Kohei Hatano, Manfred K. Warmuth
We investigate improvements of AdaBoost that can exploit the fact that the weak hypotheses are one-sided, i.e. either all its positive (or negative) predictions are correct. In particular, for any...
Efficient margin maximizing with boosting (2003)
AdaBoost produces a linear combination of base hypotheses and predicts with the sign of this linear combination. The linear combination may be viewed as a hyperplane in feature space where the base...
Tracking a small set of experts by mixing past posteriors (2002)
Olivier Bousquet, Manfred K. Warmuth, M. Long
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts....
Path kernels and multiplicative updates (2002)
Manfred K. Warmuth, Ralf Herbrich, Thore Graepel
Kernels are typically applied to linear algorithms whose weight vector is a linear combination of the feature vectors of the examples. On-line versions of these algorithms are sometimes called...
Path kernels and multiplicative updates (2002)
Manfred K. Warmuth, Ralf Herbrich, Thore Graepel
Kernels are typically applied to linear algorithms whose weight vector is a linear combination of the feature vectors of the examples. On-line versions of these algorithms are sometimes called...
Adaptive caching by refetching (2002)
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Br, Ismail Ari Ý
We are constructing caching policies that have 13-20 % lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63 %...
Adaptive caching by refetching (2002)
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Br, Ismail Ari
We are constructing caching policies that have 13-20 % lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63 %...
Path kernels and multiplicative updates (2002)
Eiji Takimoto, Manfred K. Warmuth, Ralf Herbrich, Thore Graepel
Kernels are typically applied to linear algorithms whose weight vector is a linear combination of the feature vectors of the examples. On-line versions of these algorithms are sometimes called...
Mixing Past Posteriors, Olivier Bousquet, Manfred K. Warmuth, M. Long
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts....
Active learning in the drug discovery process (2002)
Manfred K. Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, Christian Lemmen
We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing...
Adaptive caching by refetching (2002)
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Br, Ismail Ari
We are constructing caching policies that have 13-20 % lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63 %...
Tracking a small set of experts by mixing past posteriors (2002)
Olivier Bousquet, Manfred K. Warmuth, M. Long
In this paper, we examine on-line learning problems in which the target concept is allowed to change over time. In each trial a master algorithm receives predictions from a large set of n experts....
Adaptive caching by refetching (2002)
Robert B. Gramacy, Manfred K. Warmuth, Scott A. Br, Ismail Ari Ý
We are constructing caching policies that have 13-20 % lower miss rates than the best of twelve baseline policies over a large variety of request streams. This represents an improvement of 49–63 %...
Active learning in the drug discovery process (2002)
Manfred K. Warmuth, Gunnar Rätsch, Michael Mathieson, Jun Liao, Christian Lemmen
We investigate the following data mining problem from Computational Chemistry: From a large data set of compounds, find those that bind to a target molecule in as few iterations of biological testing...
Maximizing the margin with boosting (2002)
Gunnar Rätsch, Manfred K. Warmuth
Abstract. AdaBoost produces a linear combination of weak hypotheses. It has been observed that the generalization error of the algorithm continues to improve even after all examples are classified...
Tracking the best linear predictor (2001)
Mark Herbster, Manfred K. Warmuth, Peter Bartlett
In most on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best o-line predictor u from a comparison class of predictors. We call such bounds...
Tracking the best linear predictor (2001)
Mark Herbster, Manfred K. Warmuth, Peter Bartlett
In most on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best o¬-line predictor u from a comparison class of predictors. We call such bounds...
Relative Loss Bounds for Temporal-Difference Learning (2000)
Jürgen Forster, Manfred K. Warmuth
. Foster and Vovk proved relative loss bounds for linear regression where the total loss of the on-line algorithm minus the total loss of the best linear predictor (chosen in hindsight) grows...
Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph (2000)
Eiji Takimoto, Manfred K. Warmuth
We design ecient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees, we...
Boosting as entropy projection (1999)
Jyrki Kivinen, Manfred K. Warmuth
We consider the AdaBoost procedure for boosting weak learners. In AdaBoost, a key step is choosing a new distribution on the training examples based on the old distribution and the mistakes made by...
Averaging expert predictions (1999)
Jyrki Kivinen, Manfred K. Warmuth
Abstract. We consider algorithms for combining advice from a set of experts. In each trial, the algorithm receives the predictions of the experts and produces its own prediction. A loss function is...
Averaging Expert Predictions (1999)
Jyrki Kivinen, Manfred K. Warmuth
. We consider algorithms for combining advice from a set of experts. In each trial, the algorithm receives the predictions of the experts and produces its own prediction. A loss function is applied...
Predicting Nearly as Well as the Best Pruning of a Planar Decision Graph (1999)
Eiji Takimoto, Manfred K. Warmuth
We design efficient on-line algorithms that predict nearly as well as the best pruning of a planar decision graph. We assume that the graph has no cycles. As in the previous work on decision trees,...
Efficient Learning Algorithms. (1998)
Haussler, David, Warmuth, Manfred K.
We have worked on refining and generalizing the PAC learning model introduced by Valiant. Measures of performance for learning algorithms that we have examined include computational complexity,...
Efficient learning with virtual threshold gates (1998)
Wolfgang Maass, Manfred K. Warmuth
We reduce learning simple geometric concept classes to learning disjunctions over exponentially many variables. We then apply an on-line algorithm called Winnow whose number of prediction mistakes...
On the Computational Complexity of Approximating Distributions by Probabilistic Automata (1998)
We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the...
Tracking the Best Expert (1998)
Mark Herbster, Manfred K. Warmuth, Gerhard Widmer, Miroslav Kubat
. We generalize the recent relative loss bounds for on-line algorithms where the additional loss of the algorithm on the whole sequence of examples over the loss of the best expert is bounded. The...
Tracking the Best Regressor (1998)
Mark Herbster, Manfred K. Warmuth
In most of the on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors. We call such...
Tracking the Best Regressor (1998)
Mark Herbster, Manfred K. Warmuth
In most of the on-line learning research the total on-line loss of the algorithm is compared to the total loss of the best off-line predictor u from a comparison class of predictors. We call such...
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...
A New Parameter Estimation Method for Gaussian Mixtures (1998)
Yoram Singer, Manfred K. Warmuth
We describe a new iterative method for parameter estimation of Gaussian mixtures. The new method is based on a framework developed by Kivinen and Warmuth for supervised online learning. In contrast...
Batch and on-line parameter estimation of Gaussian mixtures based on the joint entropy (1998)
Yoram Singer, Manfred K. Warmuth
We describe a new iterative method for parameter estimation of Gaussian mixtures. The new method is based on a framework developed by Kivinen and Warmuth for supervised on-line learning. In contrast...
Tracking the best disjunction (1998)
Peter Auer, Manfred K. Warmuth, Gerhard Widmer, Miroslav Kubat
Abstract. Littlestone developed a simple deterministic on-line learning algorithm for learning k-literal disjunctions. This algorithm (called Winnow) keeps one weight for each of the n variables and...
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...
Analyzing the Performance of Learning Algorithms. (1997)
Haussler, David, Warmuth, Manfred K.
We discuss the approach to the analysis of learning algorithms that we have taken in our laboratory and summarize the results we have obtained in the last few years. We have worked on refining and...
Exponentiated gradient versus gradient descent for linear predictors (1997)
Jyrki Kivinen, Manfred K. Warmuth
We consider two algorithm for on-line prediction based on a linear model. The algorithms are the well-known gradient descent (GD) algorithm and a new algorithm, which we call EG \Sigma. They both...
Exponentiated gradient versus gradient descent for linear predictors (1997)
Jyrki Kivinen, Manfred K. Warmuth
We consider two algorithm for on-line prediction based on a linear model. The algorithms are the well-known Gradient Descent (GD) algorithm and a new algorithm, which we call EG \Sigma. They both...
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...
Efficient Learning with Virtual Threshold Gates (1997)
Wolfgang Maass, Manfred K. Warmuth
We reduce learning simple geometric concept classes to learning disjunctions over exponentially many variables. We then apply an on-line algorithm called Winnow whose number of prediction mistakes...
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...
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...
Relative Loss Bounds for Multidimensional Regression Problems (1997)
Jyrki Kivinen, Manfred K. Warmuth
We study on-line generalized linear regression with multidimensional outputs, i.e., neural networks with multiple output nodes but no hidden nodes. We allow at the final layer transfer functions such...
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...
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...
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 Hidden Markov Models Using Entropy Based Distance Functions (1996)
Yoram Singer, Manfred K. Warmuth
We present new algorithms for parameter estimation of HMMs. By adapting a framework used for supervised learning, we construct iterative algorithms that maximize the likelihood of the observations...
Exponentiated Gradient Versus Gradient Descent for Linear Predictors (1996)
Jyrki Kivinen, Manfred K. Warmuth
We consider two algorithm for on-line prediction based on a linear model. The algorithms are the well-known gradient descent (GD) algorithm and a new algorithm, which we call EG \Sigma . They both...
Training Algorithms for Hidden Markov Models Using Entropy Based Distance Functions (1996)
Yoram Singer, Manfred K. Warmuth
We present new algorithms for parameter estimation of HMMs. By adapting a framework used for supervised learning, we construct iterative algorithms that maximize the likelihood of the observations...
Relative Loss Bounds for Single Neurons (1996)
David P. Helmbold, Jyrki Kivinen, Manfred K. Warmuth
We analyze and compare the well-known Gradient Descent algorithm and the more recent Exponentiated Gradient algorithm for training a single neuron with an arbitrary transfer function. Both algorithms...
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...
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...
Peter Auer, Stephen Kwek, Wolfgang Maass, Manfred K. Warmuth
We present algorithms for learning depth two neural networks where the hidden nodes are threshold gates with constant fan-in. The transfer function of the output node might be more general: we have...
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...
David P. Helmbold, Manfred K. Warmuth
This paper presents relationships between weak learning, weak prediction (where the probability of being correct is slightly larger than 50%), and consistency oracles (which decide whether or not a...
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...
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...
Exponentially Many Local Minima for Single Neurons (1995)
Peter Auer, Mark Herbster, Manfred K. Warmuth
We show that for a single neuron with the logistic function as the transfer function the number of local minima of the error function based on the square loss can grow exponentially in the dimension....
Tracking the Best Disjunction (1995)
Peter Auer, Manfred K. Warmuth
. Littlestone developed a simple deterministic on-line learning algorithm for learning k-literal disjunctions. This algorithm (called Winnow) keeps one weight for each of the n variables and does...
Jyrki Kivinen, Manfred K. Warmuth
We give an adversary strategy that forces the Perceptron algorithm to make (N \Gamma k + 1)=2 mistakes when learning k-literal disjunctions over N variables. Experimentally we see that even for...
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...
Jyrki Kivinen, Manfred K. Warmuth
This paper addresses the familiar problem of predicting with a linear classifier . The
Learning binary relations using weighted majority voting (1995)
Sally A. Goldman, Manfred K. Warmuth, David Haussler
Abstract. In this paper we demonstrate how weighted majority voting with multiplicative weight updating can be applied to obtain robust algorithms for learning binary relations. We first present an...
Estimation of Distributed Parameters by Multiresolution Optimization (1994)
Multiresolution Optimization, Alex T. Pang, Suresh K. Lodha, Manfred K. Warmuth, Koji Amakawa, Koji Amakawa
ix Acknowledgments xi 1. Introduction 1 1.1 Parameter Estimation by Numerical Optimization : : : : : : : : : : : 2 1.2 Local Search Methods : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.3...
On the Worst-case Analysis of Temporal-difference Learning Algorithms (1994)
Robert Schapire Manfred, Manfred K. Warmuth
this paper appeared in Machine Learning: Proceedings of the Eleventh International Conference, 1994.
Bounds on Approximate Steepest Descent for Likelihood Maximization in Exponential Families (1994)
Anders Krogh, Manfred K. Warmuth
An approximate steepest descent strategy converging, in families of regular exponential densities, to maximum likelihood estimates of density functions is described. These density estimates are also...
Tight Worst-Case Loss Bounds for Predicting With Expert Advice (1994)
David Haussler, Jyrki Kivinen, Manfred K. Warmuth
this paper is somewhat different from the one just described. Assume that there are N experts E i , i = 1; : : : ; N , each trying to predict the outcomes y t as best they can. Let x t;i be the...
On the Worst-case Analysis of Temporal-difference Learning Algorithms (1994)
Robert Schapire 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...
The Weighted Majority Algorithm (1994)
Nick Littlestone, Manfred K. Warmuth
We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few...
Nicolo Cesa-Bianchi, Philip M. Long, Manfred K. Warmuth
this paper we study the performance of gradient descent when applied to the problem of on-line linear prediction in arbitrary inner product spaces. We show worst-case bounds on the sum of the squared...
Bounds on Approximate Steepest Descent for Likelihood Maximization in Exponential Families (1993)
Nicol Cesa-Bianchi, Anders Krogh, Manfred K. Warmuth
An approximate steepest descent strategy converging, in families of regular exponential densities, to maximum likelihood estimates of density functions is described. These density estimates are also...
Data Filtering and Distribution Modeling Algorithms for Machine Learning (1993)
Yoav Freund, Manfred K. Warmuth, David Haussler, David P. Helmbold
vi Acknowledgments vii 1. Introduction 1 1.1 Boosting by majority : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 1.2 Query By Committee : : : : : : : : : : : : : :...
Bounds on Approximate Steepest Descent for Likelihood Maximization in Exponential Families (1993)
Nicolò Cesa-Bianchi, Anders Krogh, Manfred K. Warmuth
An approximate steepest descent strategy converging, in families of regular exponential densities, to maximum likelihood estimates of density functions is described. These density estimates are also...
The minimum consistent DFA problem cannot be approximated within any polynomial (1993)
Leonard Pitt, Manfred K. Warmuth
Abstract. The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether...
The Weighted Majority Algorithm (1992)
Nick Littlestone, Manfred K. Warmuth
We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few...
On-Line Learning of Linear Functions (1991)
Nicholas Littlestone, Philip M. Long, Manfred K. Warmuth
this paper, we present near-optimal strategies for combining opinions in situations like this. In more abstract terms, we study the on-line learning of linear functions. We assume that learning...
On-line Prediction and Conversion Strategies (1991)
David P. Helmbold, Manfred K. Warmuth
Editor: Abstract. We study the problem of deterministically predicting boolean values by combining the boolean predictions of several experts. Previous on-line algorithms for this problem predict...
On the Computational Complexity of Approximating Distributions by Probabilistic Automata (1990)
We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the...
Composite Geometric Concepts and Polynomial Predictability (1990)
Philip M. Long, Manfred K. Warmuth
this paper, we assume not only that the target concept is chosen from a particular class, but that the concepts of this class are encoded using a particular representation language, and we allow the...
We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the...
Computing on an Anonymous Ring (1988)
Hagit Attiya, Marc Snir, Manfred K. Warmuth
Abstract. The computational capabilities of a system of n indistinguishable (anonymous) processors arranged on a ring in the synchronous and asynchronous models of distributed computation are...
Relating data compression and learnability (1986)
Nick Littlestone, Manfred K. Warmuth
We explore the learnability of two-valued functions from samples using the paradigm of Data Compression. A first algorithm (compression) choses a small subset of the sample which is called the...
Relating Data Compression and Learnability (1986)
Nick Littlestone, Manfred K. Warmuth
We explore the learnability of two-valued functions from samples using the paradigm of Data Compression. A rst algorithm (compression) choses a small subset of the sample which is called the kernel....
Gap Theorems for Distributed Computation (1986)
Shlomo Moran, Manfred K. Warmuth
lower bounds, gap theorem. Consider a bidirectional ring of n identical processors that communicate asynchronously. The processors have no identifiers and hence the ring is called anonymous. Each...
Engineering proteinase K using machine learning and synthetic genes
Liao, Jun, Warmuth, Manfred K, Govindarajan, Sridhar, Ness, Jon E, Wang, Rebecca P, Gustafsson, Claes, ...
Efficient Learning with Virtual Threshold Gates
Wolfgang Maass, Manfred K. Warmuth
this paper is to reduce learning particular concept classes to the case of learning disjunctions or more generally linear threshold functions over exponentially many variables. Then the algorithm...