 |
Nicolò Cesa-Bianchi and Gábor Lugosi
Cambridge University Press, 2006 ISBN 0521841089 Published March 2006, 406 pages ...beware of mathematicians, and all those who make empty prophecies. The danger already exists that the mathematicians have made a covenant with the devil to darken the spirit and to confine man in the bonds of Hell. St. Augustine, De Genesi ad Litteram libri duodecim. Liber Secundus, 17, 37. Errata (as of September 8, 2006) A review (in French) appeared on the Gazette of Mathématiciens, 110, October 2006. |
This book offers the first comprehensive treatment of the problem
of predicting "individual sequences". Unlike standard statistical
approaches to forecasting, prediction of individual sequences does
not impose any probabilistic assumption on the data-generating
mechanism. Yet, prediction algorithms can be constructed that work
well for all possible sequences, in the sense that their performance
is always nearly as good as the best forecasting strategy in a given
reference class.
The central theme is the model of "prediction using expert advice",
a general framework within which many related problems can be cast
and discussed. Repeated game playing, adaptive data compression,
sequential investment in the stock market, sequential pattern analysis,
and several other problems are viewed as instances of the experts'
framework and analyzed from a common nonstochastic standpoint that
often reveals new and intriguing connections. Old and new forecasting
methods are described in a mathematically precise way with the purpose
of characterizing their theoretical limitations and possibilities.
Preface
1 Introduction
2 Prediction with expert advice
2.1 Weighted average prediction
2.2 An optimal bound
2.3 Bounds that hold uniformly over time
2.4 An improvement for small losses
2.5 Forecasters using the gradient of the loss
2.6 Scaled losses and signed games
2.7 The multilinear forecaster
2.8 The exponential forecaster for signed games
2.9 Simulatable experts
2.10 Minimax regret
2.11 Discounted regret
2.12 Bibliographic remarks
2.13 Exercises
3 Tight bounds for specific losses
3.1 Introduction
3.2 Follow the best expert
3.3 Exp-concave loss functions
3.4 The greedy forecaster
3.5 The aggregating forecaster
3.6 Mixability for certain losses
3.7 General lower bounds
3.8 Bibliographic remarks
3.9 Exercises
4 Randomized prediction
4.1 Introduction
4.2 Weighted average forecasters
4.3 Follow the perturbed leader
4.4 Internal regret
4.5 Calibration
4.6 Generalized regret
4.7 Calibration with checking rules
4.8 Bibliographic remarks
4.9 Exercises
5 Efficient forecasters for large classes of experts
5.1 Introduction
5.2 Tracking the best expert
5.3 Tree experts
5.4 The shortest path problem
5.5 Tracking the best of many actions
5.6 Bibliographic remarks
5.7 Exercises
6 Prediction with limited feedback
6.1 Introduction
6.2 Label efficient prediction
6.3 Lower bounds
6.4 Partial monitoring
6.5 A general forecaster for partial monitoring
6.6 Hannan consistency and partial monitoring
6.7 Multi-armed bandit problems
6.8 An improved bandit strategy
6.9 Lower bounds for the bandit problem
6.10 How to select the best action
6.11 Bibliographic remarks
6.12 Exercises
7 Prediction and playing games
7.1 Games and equilibria
7.2 Minimax theorems
7.3 Repeated two-player zero-sum games
7.4 Correlated equilibrium and internal regret
7.5 Unknown games: game-theoretic bandits
7.6 Calibration and correlated equilibrium
7.7 Blackwell's approachability theorem
7.8 Potential-based approachability
7.9 Convergence to Nash equilibria
7.10 Convergence in unknown games
7.11 Playing against opponents that react
7.12 Bibliographic remarks
7.13 Exercises
8 Absolute loss
8.1 Simulatable experts
8.2 Optimal algorithm for simulatable experts
8.3 Static experts
8.4 A simple example
8.5 Bounds for classes of static experts
8.6 Bounds for general classes
8.7 Bibliographic remarks
8.8 Exercises
9 Logarithmic loss
9.1 Sequential probability assignment
9.2 Mixture forecasters
9.3 Gambling and data compression
9.4 The minimax optimal forecaster
9.5 Examples
9.6 The Laplace mixture
9.7 A refined mixture forecaster
9.8 Lower bounds for most sequences
9.9 Prediction with side information
9.10 A general upper bound
9.11 Further examples
9.12 Bibliographic remarks
9.13 Exercises
10 Sequential investment
10.1 Portfolio selection
10.2 The minimax wealth ratio
10.3 Prediction and investment
10.4 Universal portfolios
10.5 The EG investment strategy
10.6 Investment with side information
10.7 Bibliographic remarks
10.8 Exercises
11 Linear pattern recognition
11.1 Prediction with side information
11.2 Bregman divergences
11.3 Potential-based gradient descent
11.4 The transfer function
11.5 Forecasters using Bregman projections
11.6 Time-varying potentials
11.7 The elliptic potential
11.8 A nonlinear forecaster
11.9 Lower bounds
11.10 Mixture forecasters
11.11 Bibliographic remarks
11.12 Exercises
12 Linear classification
12.1 The zero-one loss
12.2 The hinge loss
12.3 Maximum margin classifiers
12.4 Label efficient classifiers
12.5 Kernel-based classifiers
12.6 Bibliographic remarks
12.7 Exercises
13 Appendix
13.1 Inequalities from probability theory
13.1.1 Hoeffding's inequality
13.1.2 Bernstein's inequality
13.1.3 Hoeffding-Azuma inequality and related results
13.1.4 Khinchine's inequality
13.1.5 Slud's inequality
13.1.6 A simple limit theorem
13.1.7 Proof of Theorem 8.3
13.1.8 Rademacher averages
13.1.9 The Beta distribution
13.2 Basic information theory
13.3 Basics of classification
Bibliography
Author index