Prediction With Expert Advice For The Brier Game

The paper gives a new algorithm for a natural probability forecasting problem and shows a tight performance bound. It also describes results of extensive experiments performed on novel data sets. The paper introduces a new algorithm and analysis for online prediction from expert advice for multi-class classification with square-loss.

A game of prediction consists of three components: the space of events ⚠ $\Omega$, the space of predictions ⚠ $\Gamma$, and the loss function ⚠ $\lambda: \Omega \times \Gamma \to \mathbb{R}$ which measures the quality of predictions. In our experiments we are interested in the "Brier game" (Brier, 1950), since it is widely used in probability forecasting.

Let ⚠ $\Omega$ be a finite and non-empty set, ⚠ $\Gamma=P(\Omega)$ be the set of all probability measures on ⚠ $\Omega$, and \begin{equation*} \lambda(\omega,\gamma) = \sum_{o\in\Omega} \left( \gamma\{o\} - \delta_{\omega}\{o\} \right)^2,\end{equation*} where ⚠ $\delta_{\omega}\in P(\Omega)$ is a probability measure concentrated at ⚠ $\omega$: ⚠ $\delta_{\omega}\{\omega\}=1$ and ⚠ $\delta_{\omega}\{o\}=0$ for ⚠ $o\ne\omega$.

The theoretical bound for its cumulative loss at a prediction step ⚠ $N$ is \begin{equation*} L_N(\mathrm{AA}) \le L_N^k + \ln K \end{equation*} for any expert ⚠ $k$, where ⚠ $K$ is the number of experts. It is proved that the theoretical bound for the AA is optimal. It is also proved that the Brier game is mixable for ⚠ $\eta \le 1$. The substitution function for the algorithm is capable to give proper prediction even if the weights are not normalized at each step.

Experiments on the prediction of the result of football and tennis matches are made and show the theoretical bound is rather tight empirically. Bookmakers are used as experts, and the loss of the prediction algorithm is close to the loss of the best bookmaker.

The journal version of the paper describes the experiments with Khutsishvili's formula and makes a comparison with other prediction algorithms.

The Matlab package of the algorithms used is provided for public use.

References