The weighted majority algorithm

DOI10.1006/inco.1994.1009zbMath0804.68121OpenAlexW2093825590WikidataQ29400139 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

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, Binary switch portfolio, The Post-Disaster Debris Clearance Problem Under Incomplete Information, Inertial Game Dynamics and Applications to Constrained Optimization, Competitive On-line Statistics, Asymptotically optimal strategies for online prediction with history-dependent experts, Further Investigations of 3-Member Simple Majority Voting for Chess, Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case, Improved algorithms for bandit with graph feedback via regret decomposition, Optimal anytime regret with two experts, Online Metric Algorithms with Untrusted Predictions, Adaptiveness and consistency of a class of online ensemble learning algorithms, Space-dependent turbulence model aggregation using machine learning, Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback, No-regret algorithms in on-line learning, games and convex optimization, A unified stochastic approximation framework for learning in games, Universal regression with adversarial responses, Metalearning of time series: an approximate dynamic programming approach, Relaxing the i.i.d. assumption: adaptively minimax optimal regret via root-entropic regularization, Independent learning in stochastic games, Following the Perturbed Leader to Gamble at Multi-armed Bandits, A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs, PORTFOLIO SELECTION AND ONLINE LEARNING, Unnamed Item, Automated trading with boosting and expert weighting, Prediction of time series by statistical learning: general losses and fast rates, A survey on concept drift adaptation, Multiagent cooperative search for portfolio selection, A general class of adaptive strategies, Probability theory for the Brier game, Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme, Agnostic learning of geometric patterns, General linear relations between different types of predictive complexity, A PAC Approach to Application-Specific Algorithm Selection, On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning, A Hybrid Approach of Boosting Against Noisy Data, Tracking climate models, An extension of play against the random past strategy. Choosing the right experts on IBM forecasts, A Learning Algorithm to Select Consistent Reactions to Human Movements, Unnamed Item, Dynamic Bayesian Combination of Multiple Imperfect Classifiers, Unnamed Item, Structural Online Learning, Learning Volatility of Discrete Time Series Using Prediction with Expert Advice, The Follow Perturbed Leader Algorithm Protected from Unbounded One-Step Losses, Learning in Games via Reinforcement and Regularization, Scale-Free Algorithms for Online Linear Optimization, Online Learning over a Finite Action Set with Limited Switching, MODEL THEORY AND MACHINE LEARNING, How many strings are easy to predict?, Learning Optimal Forecast Aggregation in Partial Evidence Environments, Partial Monitoring—Classification, Regret Bounds, and Algorithms, Online Learning of Nash Equilibria in Congestion Games, Unnamed Item, An ensemble method for concept drift in nonstationary environment, Unnamed Item, Small-Loss Bounds for Online Learning with Partial Information

Cites Work