Notes on Yoav Freund and Robert E. Schapire, Game Theory, On-line Prediction, and Boosting

This is a set of notes for a paper covered by the learning theory reading group, which I’m posting here with some keywords so I can easily search for them. I doubt they’ll be useful for anyone else, but who knows?

These notes cover the whole paper. Despite the usual disclaimer, this set of notes may actually be thorough enough to be useful to someone besides myself because I was presenting this week. The exposition in the paper is excellent, and it’s pretty basic, so you’re probably still better off just reading the paper directly, though :-).

We study the close connections between game theory, on-line prediction and boosting. After a brief review of game theory, we describe an algorithm for learning to play repeated games based on the on-line prediction methods of Littlestone and Warmuth. The analysis of this algorithm yields a simple proof of von Neumann’s famous minmax theorem, as well as a provable method of approximately solving a game. We then show that the on-line prediction model is obtained by applying this gameplaying algorithm to an appropriate choice of game and that boosting is obtained by applying the same algorithm to the “dual” of this game.

Advertisements
Notes on Yoav Freund and Robert E. Schapire, Game Theory, On-line Prediction, and Boosting

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s