The weighted majority algorithm

DOI10.1006/INCO.1994.1009zbMath0804.68121DBLPjournals/iandc/LittlestoneW94OpenAlexW2093825590WikidataQ29400139 ScholiaQ29400139MaRDI QIDQ1322487

Manfred K. Warmuth, Nicholas Littlestone

Publication date: 1994

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/35582a30685083c62dca992553eec44123be9d07

zbMATH Keywords

weighted voting weighted majority algorithm on-line prediction algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Voting theory (91B12)

Related Items (only showing first 100 items - show all)

On the robustness of learning in games with stochastically perturbed payoff observations ⋮ Imitation dynamics with payoff shocks ⋮ Generalization bounds for averaged classifiers ⋮ Replicator dynamics: old and new ⋮ On approximating weighted sums with exponentially many terms ⋮ Online learning in online auctions ⋮ Representation in the (artificial) immune system ⋮ Feature selection via Boolean independent component analysis ⋮ Improved second-order bounds for prediction with expert advice ⋮ AWESOME: a general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents ⋮ Generalized mirror descents in congestion games ⋮ Evolutionary game theory: a renaissance ⋮ Dynamic benchmark targeting ⋮ On-line maximum likelihood prediction with respect to general loss functions ⋮ A decision-theoretic generalization of on-line learning and an application to boosting ⋮ Online learning for min-max discrete problems ⋮ On minimaxity of follow the leader strategy in the stochastic setting ⋮ Two queues with non-stochastic arrivals ⋮ On the complexity of learning from drifting distributions ⋮ Adaptive regularization of weight vectors ⋮ Selection of relevant features and examples in machine learning ⋮ Wrappers for feature subset selection ⋮ Efficient learning with virtual threshold gates ⋮ Combining initial segments of lists ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ A statistical approach to adaptive problem solving ⋮ Committee polyhedral separability: complexity and polynomial approximation ⋮ PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting ⋮ Context-based unsupervised ensemble learning and feature ranking ⋮ Predicting a binary sequence almost as well as the optimal biased coin ⋮ Algorithm portfolio selection as a bandit problem with unbounded losses ⋮ Foraging theory for dimensionality reduction of clustered data ⋮ Online variance minimization ⋮ Combining block-based and online methods in learning ensembles from concept drifting data streams ⋮ Online multiple kernel classification ⋮ Scale-free online learning ⋮ Sparse regression learning by aggregation and Langevin Monte-Carlo ⋮ Learning with stochastic inputs and adversarial outputs ⋮ The online performance estimation framework: heterogeneous ensemble learning for data streams ⋮ Approachability, regret and calibration: implications and equivalences ⋮ Multi-domain learning by confidence-weighted parameter combination ⋮ Increasing coverage to improve detection of network and host anomalies ⋮ Extracting certainty from uncertainty: regret bounded by variation in costs ⋮ Regret bounds for sleeping experts and bandits ⋮ Learning in games with continuous action sets and unknown payoff functions ⋮ Loss functions, complexities, and the Legendre transformation. ⋮ Learning recursive functions: A survey ⋮ Nonstochastic bandits: Countable decision set, unbounded costs and reactive environments ⋮ Kernelization of matrix updates, when and how? ⋮ Analysis of two gradient-based algorithms for on-line regression ⋮ Combining trigram and automatic weight distribution in Chinese spelling error correction ⋮ Randomized prediction of individual sequences ⋮ Online aggregation of unbounded losses using shifting experts with confidence ⋮ Online linear optimization and adaptive routing ⋮ Universal forecasting algorithms ⋮ On-line learning of smooth functions of a single variable ⋮ Credibility dynamics: a belief-revision-based trust model with pairwise comparisons ⋮ On the asymptotic optimality of the comb strategy for prediction with expert advice ⋮ Consistency of discrete Bayesian learning ⋮ A continuous-time approach to online optimization ⋮ Exponential weight algorithm in continuous time ⋮ Bounding the inefficiency of outcomes in generalized second price auctions ⋮ Disparate data fusion for protein phosphorylation prediction ⋮ Sequential model aggregation for production forecasting ⋮ Learning with continuous experts using drifting games ⋮ An analysis on the relationship between uncertainty and misclassification rate of classifiers ⋮ A quasi-Bayesian perspective to online clustering ⋮ New bounds on the price of bandit feedback for mistake-bounded online multiclass learning ⋮ Near-optimal no-regret algorithms for zero-sum games ⋮ Tracking the best hyperplane with a simple budget perceptron ⋮ Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity ⋮ Regret to the best vs. regret to the average ⋮ Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning ⋮ Sensor networks: from dependence analysis via matroid bases to online synthesis ⋮ Automated adaptation strategies for stream learning ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ A bad arm existence checking problem: how to utilize asymmetric problem structure? ⋮ Prediction with expert advice: a PDE perspective ⋮ A game of prediction with expert advice ⋮ Regret in the on-line decision problem ⋮ Adaptive game playing using multiplicative weights ⋮ Conditional universal consistency. ⋮ Sampling from non-smooth distributions through Langevin diffusion ⋮ Perspectives on multiagent learning ⋮ Worst-case analysis of the Perceptron and Exponentiated Update algorithms ⋮ Aggregating algorithm for prediction of packs ⋮ On the efficiency of data collection for multiple naïve Bayes classifiers ⋮ On prediction of individual sequences ⋮ On-line learning of linear functions ⋮ Multi-agent reinforcement learning: a selective overview of theories and algorithms ⋮ Predicting nearly as well as the best pruning of a planar decision graph. ⋮ On learning unions of pattern languages and tree patterns in the mistake bound model. ⋮ Apple tasting. ⋮ Suboptimal measures of predictive complexity for absolute loss function ⋮ Exponential weight approachability, applications to calibration and regret minimization ⋮ Direct and indirect algorithms for on-line learning of disjunctions ⋮ Adaptive and self-confident on-line learning algorithms ⋮ The weighted majority algorithm ⋮ Incremental learning with partial instance memory ⋮ Link prediction in multiplex networks

Cites Work

This page was built for publication: The weighted majority algorithm