The weighted majority algorithm

By Nick Littlestone, Manfred K. Warmuth. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Memory Efficient Experience Replay for Streaming Learning (2018, neutral): “[37], [38], [39], [56], [63] or ensemble methods [7], [9], [27], [44], [46], [51], [54], [61], [70], [72].”
Introduction to Online Convex Optimization (2016, methodology): “The problem of prediction from expert advice and the Weighted Majority algorithm were devised in (71; 73).”
A unified view of entropy-regularized Markov decision processes (2017, positive): “In particular, entropy regularization has proven to be one of the most successful tools of machine learning and related ﬁelds (Littlestone and Warmuth, 1994; Vovk, 1990; Freund and Schapire, 1997; Kivinen and Warmuth, 2001; Arora et al., 2012).”
Adaptive and Self-Confident On-Line Learning Algorithms (2000, methodology): “As a relevant example, both the standard analysis [29, 34] and our self-confident analysis for Weighted Majority still hold when the dimension of the input space (the number of experts) is countably infinite.”
Classifier Ensembles for Changing Environments (2004, methodology): “The most famous representative of this group is the Weighted Majority algorithm by Littlestone and Warmuth [17] , shown below.”
From External to Internal Regret (2005, unknown): “A typical optimized experts algorithm, such as in Littlestone and Warmuth (1994), Freund and Schapire (1995), Auer et al. (2002b), and Cesa-Bianchi et al. (1993), will have R(L min , T, N ) = O( √ L min log N + log N ).”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “[61], Freund and Schapire introduced the Hedge [26] algorithm to solve a variant of the online learning problem(10) of Section 2.”
DDD: A New Ensemble Approach for Dealing with Concept Drift (2012, background): “Online learning often operates in the scenario explained in [10] and further adopted in many works, such as [2], [7], [11], and [12]: Learning proceeds in a sequence of trials.”
Game theory, on-line prediction and boosting (1996, methodology): “Proof: The proof follows directly from Theorem 2 of Freund and Schapire [9], which in turn is a simple and direct generalization of Littlestone and Warmuth [15].”
Learning in games with continuous action sets and unknown payoff functions (2016, methodology): “This penalty function is 1 -strongly convex with respect to the (cid:96) 1 norm on R d and a straightforward calculation shows that the induced choice map is This model is known as logit choice and the associated learning scheme has been studied extensively in evolutionary game theory and online lea”
Bandit Algorithms (2020, background): “The reader can explore this topic by reading the articles by Mannor and Shamir [2011], Alon et al.”
Learning in Nonstationary Environments: A Survey (2015, background): “Dynamic weighted majority (DWM) [90], is an extension of the weighted majority algorithm (WM) [26] that extends WM to data streams with concept drift, and uses an updated period to add/remove classifiers.”
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1995, methodology): “Our algorithm is based in part on an algorithm recently presented by Freund and Schapire [3], which in turn is a variant of Littlestone and Warmuth’s [7] weighted majority algorithm, and Vovk’s [lo] aggregating strategies.”
Maximum Likelihood Decision Fusion for Weapon Classification in Wireless Acoustic Sensor Networks (2017, background): “Two of the most common fusion rules are average fusion and majority vote [40], although it goes without saying that there are more alternatives [41].”
Dynamical Models and tracking regret in online convex programming (2013, methodology): “The MD approach is a generalization of online learning algorithms such as online gradient descent (Zinkevich, 2003) and weighted majority (Littlestone & Warmuth, 1994).”