The Machine Learning Forum

Drifting Games, Boosting and Online Learning

Drifting games are mathematical games between a shepherd and a flock of sheep. The goal of the shepard is to get the sheep into a prescribed region - the stable. This game has been used by Freund to model problems in machine learning, specifically, to model boosting and online learning.

• A talk about drifting games (powerpoint) (Web page)

History

1. Boosting a weak learning algorithm by majority. Yoav Freund / Information and Computation / 1995
2. On-line prediction and conversion strategies. Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, and Manfred K. Warmuth. / Machine Learning / 1996. (This paper presented the online algorithm called "Binomail weights" (BW) .)

One important feature of the boost-by-majority algorithm is that it "gives up" on examples on which to many of the weak classifiers are wrong. This is a direct outcome of the fact that the number of boosting iterations is set in advance, resulting in a game with a finite horizon. This property does not hold for the better known boosting algorithms, Adaboost, Logitboost and their variants.

Schapire was the first to formalize the common ideas shared by Boost-by-Majority and the Binomial weights algorithms. He did so in this paper:

• Drifting games. Robert E. Schapire. Machine Learning, 43(3):265-291, 2001.

• An adaptive version of the boost by majority algorithm. Yoav Freund. Machine Learning, 43(3):293--318, June 2001.

• Drifting games and Brownian motion. Yoav Freund and Manfred Opper. Journal of Computer and System Sciences, 64:113--132, 2002.

The brownboost algorithm did not prove itself in practice. The problem is that when shooting for an error that can be achieved on the training set, the weights assigned to the weak rules tends to increase to infinity. To avoid this from happening, the norm of the rule-weights vector needs to be controlled. This was achieved in Robustboost, by using a type of brownian motion that includes a drift term that pushes the weights towards zero. The Robustboost algorithm does seem to work in practice and is available as part of the JBoost software package. Robustboost is described in this paper:

• A more robust boosting algorithm Yoav Freund, May 2009

Drifting games, Online learning and Tracking

Following up on the BW algorithm and applying the drifting games methodology to a more sophisticated loss function resulted in a new online learning algorithm, called Normalhedge. This algorithm is unique in that unlike the exponential weights online learning algorithms it does not have a learning rate parameter that needs to be tuned. It is therefor a truly universal online learning algoirthm for bounded losses. It achieves very similar bounds to the one achieved by exponential weights algorithms with optimal tuning.

• A parameter-free hedging algorithm, Kamalika Chaudhuri, Yoav Freund, Daniel Hsu, May 2009

Analyzing NormalHedge in continuous time yield much more transparent proofs and tighter bounds. However, it does require familiarity with stochastic process and the Ito integral.

• A method for Hedging in continuous time, Yoav Freund, May 2009

• Tracking using explanation-based modeling, Kamalika Chaudhuri, Yoav Freund, Daniel Hsu, May 2009