Statistics Without Probability (Individual Sequences)

July 4, 2012

(This article was originally published at Normal Deviate, and syndicated at StatsBlogs.)

Happy Independence Day and Happy Higgs Day.

Frequentist statistics treats observations as random and parameters as fixed. Bayesian statistics treats everything as probabilistic. But there is an approach to statistics that removes probability completely. This is the theory of individual sequences which is a subset of online (sequential) learning. You can think of this theory of taking the idea of distribution free inference to an extreme. The description I’ll give is basically from the book:

Nicolò Cesa-Bianchi and Gábor Lugosi, (2006). Prediction, Learning, and Games

and the article:

Cesa-Bianchi and Lugosi, (1999). On Prediction of Individual Sequences. The Annals of Statistics, 27, 1865-1895.

1. Individual Sequences

Let ${y_1,y_2,y_3,\ldots}$ be a sequence of numbers. For simplicity, we’ll assume that ${y_t \in\{0,1\}}$ . We observe the data sequentially and our goal is to predict the next observation. For any time ${t}$ , let

$\displaystyle y^t = (y_1,\ldots, y_t)$

denote the first ${t}$ observations.

The data sequence is not assumed to be random. It is just a sequence of numbers. In fact, we even allow for the possibility that the sequence is generated by an adversary who is trying to screw up our predictions.

We also have a set of algorithms (or predictors) ${{\cal F}=\{F_1, \ldots, F_N\}}$ . (In the literature, these algorithms are often called experts but I prefer to use the term algorithms.) Each algorithm takes any observed sequence and spits out a prediction. So ${F_j(y^t)}$ is the prediction of ${y_{t+1}}$ from algorithm ${j}$ based on ${y^t = (y_1,\ldots, y_t)}$ . We will assume that the predictions take values in the interval ${[0,1]}$ . Your goal is to observe the sequence and the outputs of the algorithms and then construct your own prediction. The situation unfolds as follows:

You see ${y^{t-1}}$ and ${(F_{1,t},\ldots,F_{N,t})}$ where ${F_{j,t} = F_j(y^{t-1})}$ is the prediction for ${y_t}$ from algorithm ${j}$ .
You make a prediction ${P_t}$ .
${y_t}$ is revealed.
You suffer loss ${\ell(P_t,y_t)}$ .

We will focus on the loss ${\ell(p_t,y_t)=|p_t-y_t|}$ but the theory works more generally. The average cumulative loss after ${n}$ rounds experienced by algorithm ${j}$ is

$\displaystyle L_j(y^n) = \frac{1}{n}\sum_{t=1}^n |F_{j,t}-y_t| \equiv \frac{1}{n}S_j(y^n)$

where ${S_j(y^n) = \sum_{t=1}^n |F_{j,t}-y_t|}$ . (I am using the average rather than the sum which is more common.)

You suffer average cumulative loss

$\displaystyle L_P(y^n) =\frac{1}{n}\sum_{t=1}^n |P_t-y_t|.$

Your regret is your cumulative loss compared to the loss of the best prediction algorithm:

$\displaystyle {\sf regret} =L_P(y^n) - \min_j L_j(y^n).$

Since we are not using probability, how do we deal with the fact that the regret depends on the particular sequence? The answer is: we take the worst case over all sequences. We define the maximum regret

$\displaystyle R_n = \max_{y^n \in \{0,1\}^n} \left( L_P(y^n) - \min_j L_j(y^n)\right)$

where the maximum is over all possible binary sequence of length ${n}$ . Finally, the minimax regret is

$\displaystyle V_n = \inf_P \max_{y^n \in \{0,1\}^n} \left( L_P(y^n) - \min_j L_j(y^n)\right).$

This is the smallest possible maximum regret over all predictors ${P}$ .

It has been shown that

$\displaystyle V_n \leq \sqrt{\frac{\log N}{2n}}.$

In fact, this bound is essentially tight.

Is there an algorithm ${P}$ that achieves this bound? Yes: it is the weighted majority algorithm going back to Vovk (1990) and Littlestone and Warmuth (1994).

The algorithm is simple: we simply take a weighted average of the predictions from ${F_1,\ldots, F_N}$ . Let ${P_t(y^{t-1}) = \sum_{j=1}^N w_{j,t-1} \ F_{j,t}}$ where the weights are

$\displaystyle w_{j,t-1} =\frac{\exp\left\{ - \gamma S_{j,t-1} \right\}}{Z_t}$

and ${Z_t = \sum_{j=1}^N \exp\left\{ - \gamma S_{j,t-1} \right\}.}$ The ${w_j}$ ‘s are called exponential weights.

Theorem 1 Let ${\gamma = \sqrt{8 \log N/n}}$ . Then
$\displaystyle L_P(y^n) - \min_{1\leq j\leq N} L_j(y^n) \leq \sqrt{\frac{\log N}{2n}}.$

The proof (again I refer you to Cesa-Bianchi and Lugosi 1999) is quite simple and, interestingly, it is very probabilistic. That is, even though the problem has no probability in it, the proof techniques are probabilistic.

The result is for a specific time ${n}$ . We can make the result uniform over time as follows. If we set ${\gamma_t = \sqrt{ 8 \log N/t}}$ then we have:

$\displaystyle L_P(y^n) \leq \min_j L_j(y^n) + \sqrt{ \frac{1 + 12n \log N}{8n}}$

for all ${n}$ and for all ${y_1,y_2,\ldots, y_n}$ .

Now suppose that ${{\cal F}}$ is an infinite class. A set ${{\cal G}=\{G_1,\ldots, G_N\}}$ is an ${r}$ -covering if, for every ${F}$ and every ${y^n}$ there is a ${G_j}$ such that

$\displaystyle \sum_{t=1}^n |F_t(y^{t-1}) - G_{j,t}(y^{t-1})| \leq r.$

Let ${N(r)}$ denote the size of the smallest ${r}$ -covering.

Theorem 2 (Cesa-Bianchi and Lugosi) The minimax regret satisfies
$\displaystyle V_n({\cal F}) \leq \inf_{r>0} \left( \frac{r}{n} + \sqrt{ \frac{\log N(r)}{2n}}\right)$

Cesa-Bianchi and Lugosi then construct a predictor that nearly achieves the bound of the form

$\displaystyle P_t = \sum_{k=1}^\infty a_k P_t^{(k)}$

where ${P_t^{(k)}}$ is a predictor based on a finite subset of ${{\cal F}}$ . (Again, there are hidden connections to probability; the construction uses chaining, which is a familiar technique in empirical process theory.)

2. Back To Probability

What if we have batch data (as opposed to sequential data) and that we make the usual i.i.d stochastic assumption. Can we still use these online ideas? (The reference for this section is: Cesa-Bianchi, Conconi and Gentile 2004).

Using batchification it is possible to use online learning for non-online learning. For example, suppose we are given data: ${(Z_1,\ldots, X_n)}$ where ${Z_t = (X_t,Y_t)}$ and an arbitrary algorithm ${A}$ that takes data and outputs classifier ${H}$ . We apply ${A}$ sequentially to get classifiers ${H_0,H_1,\ldots,H_n}$ . Let

$\displaystyle M_n = \frac{1}{n}\sum_{t=1}^n \ell( H_{t-1}(X_t),Y_t)$

To choose a final classifier we either use ${\overline{H} = \frac{1}{n}\sum_{i=1}^n H_{t-1}}$ or define ${\hat H}$ by choosing ${H_t}$ to minimize

$\displaystyle \frac{1}{t}\sum_{i=1}^n \ell(H_t(X_t),Y_t) + \sqrt{ \frac{1}{2(n-t)} \log\left( \frac{n (n+1)}{\delta}\right)}$

Let ${R(H)}$ be the risk, that is, probability of misclassifying a future observation.

Theorem 3 If ${\ell}$ is convex:
$\displaystyle \mathbb{P}\left( R(\overline{H}) \geq M_n + \sqrt{\frac{2}{n}\log\left( \frac{1}{\delta}\right)}\right)\leq \delta.$

For any ${\ell}$ ,
$\displaystyle \mathbb{P}\left( R(\hat{H}) \geq M_n + \sqrt{\frac{36}{n}\log\left( \frac{2(n+1)}{\delta}\right)}\right)\leq \delta.$

This means that we get nice performance bounds in the traditional probabilistic sense from online methods.

3. Summary

Individual sequence prediction and, more generally, online prediction methods, are interesting because they require no stochastic assumptions. This is very satisfying because the usual assumption that the data are drawn from a distribution (or, if you are a Bayesian, the assumption of exchangeability) is a fiction. Data are just numbers. Except in special situations, assuming that the data are random is something we do by reflex but it is often not justifiable.

Most research in this area is done by people in machine learning. Statistics is being left behind. There are exceptions of course; some names that come to mind are Gabor Lugosi, Andrew Nobel, Peter Grunwald, Andrew Barron, Sasha Rakhlin, and others I am forgetting. Nonetheless, I think that most statisticians are unaware of this area. We need to be more involved in it.

4. References

Nicolò Cesa-Bianchi and Gábor Lugosi (2006). Prediction, Learning, and Games.

Cesa-Bianchi, N. and Conconi, A. and Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50, 2050–2057.

Cesa-Bianchi and Lugosi, (1999). On Prediction of Individual Sequences. The Annals of Statistics, 27, 1865-1895.

Littlestone, N. and Warmuth, M. (1994). The weighted majority algorithm. Inform. and Computing. 108, 212-261.

Vovk, V. (1990). Aggregating strategies. Proc. Third Workshop on Computational Learning Theory, 371–383.

I recommend these lecture notes by Sasha Rakhlin and Karthik Sridharan.

—Larry Wasserman