This post aims at presenting the basic concepts of online learning, which is in fact a framework. Recently, this approach has been receiving much attention in top-tier conferences such as ICML, NIPS, ALT and COLT. I'm not sure whether Online Learning is a name commonly used by the ML community to define this topic, but I'm going to stay with it. A famous book in this subject is:
Prediction, Learning and Games, written by
Nicolò Cesa-Bianchi and
Gábor Lugosi.
In the traditional statistical learning setting, some stochastic properties about the data are assumed. However, in practice, one cannot guarantee that these properties hold. Consequently, it is extremely hard to provide any theoretical guarantees for the performance of these algorithms. In this scenario, online learning is a framework that has
no assumptions about the environment (I'll discuss the concept of environment below). Besides, differently from traditional approaches that generally have an universal performance measure, online learning is much more pessimistic, just intending to do
as good as a the best reference predictor. These characteristics allow researchers to provide theoretical guarantees for algorithms performance. In fact, some standard approaches such as SVM have already been re-implemented in the online learning framework.
In this framework, the prediction problem is modeled as a game in which one player is the predictor (or forecaster) and the other one is the environment (your adversary). One of the main questions is
how do we generate predictors that are good enough? Of course, we have to define what is good enough... To answer this question, we have to define some basic concepts of the field. These concepts are presented below, together with a description of a game round.
At each time step $t = 1, 2, ...$, the forecaster makes a prediction $p_t \in D$, where $D$ is the set of forecasters. At the sime time, the environment chooses a loss function $\ell_t : D \times \mathcal{L}$, where $\mathcal{L}$ is the set of all loss functions. Notice that both forecaster and environment do not know its adversary choice. The forecaster only knows the loss functions incurred over him in the past i.e., $\ell_{t-1}, \ell_{t-2}, ..., \ell_{1}$. Defining $\ell_t(p_t)$ as the loss incurred to prediction $p_t$, we can define the total loss of the forecaster until that moment, $\hat{L_n}$:
$$\hat{L}_n = \sum_{t=1}^{n}\ell_t(p_t)$$
Once we defined the total loss of the predictor, we should also define the total loss of a predictor $u$, if it was selected in all time steps:
$$L_n = \sum_{t=1}^{n}\ell_t(u)$$
Thus, once these concepts are defined, we can present what we really want to minimize, the regret $R_n$. It is the difference between the performance of the forecaster and the best predictor present in $D$. Formally,
$$R_n = \hat{L}_n - \inf_{u \in D}L_n(u)$$
*Notice that $\inf$ is different from $\min$. For further details, please check the definition of Infimum in the Wikipedia [link].
Basically, we want to keep the regret small while the environment wants to keep it large. To increase the regret, the environment wants to generate a way that the best predictor is hard to be discovered by the forecaster, and it is small, ensuring that the second term of the difference is high. Additionally, the environment wants to define loss functions that are high for predictors different from this chosen one, to ensure that the first element is high. The forecaster, on the other hand, does not have control over the second term, it can just select the best prediction at each time step. This is why this framework works (in a very simplistic statement). Because each prediction $p_t$ made tries to be as good as possible to minimize the regret. This is done looking for patterns and so on.
In general, what people want is to ensure that the forecaster (first term) is as good as the best available predictor along the time. Thus, we can say that, at the limit, when $t$ is arbitrarily large, we want the ratio $\frac{R_n}{n} \rightarrow 0$. In other words, we want the regret to grow sublinearly.
A final question to be answered is:
why don't we just use the loss function of the forecaster to measure performance? Why do we use regret?
I have to confess that this was not clear for me at a first moment, but the answer is to ensure that we can compare our approach with something more concrete. In other words, remember that the environment plays against you, thus it wants to increase the forecaster's loss. It can do it in a pretty simple way, and we can easily show that it can make forecaster's loss arbitrarily large. For example, if the loss can assume values $0$ and $1$, the environment can easily make the forecaster suffer a loss $n$ (worst-case). So, how do we know if our algorithm is good? We have to compare it to something else, in this case, the best predictor. If our regret is $0$, we know that you cannot do any better, even if your forecaster is not good. You are simply working in a problem too hard. It is all a matter of having a basis for comparison.
An analogy that may ease the understanding of this difference are grades in a class. If we state that each student score a grade $p \in \mathbb{R} : 0 \leq p \leq 100$, we just define the range of possibilities (you can see them as losses), however, we do not say if it is possible to score all these grades. Suppose that your professor is working as your adversary (this is just an analogy!) and wants to make the course extremely challenging. Then, at the end you score $40$. It seems pretty bad, however, when you look at your classmates grades, the highest one was $42$. Your loss is huge! But your regret is small... You shouldn't be so sad about your performance, and hopefully you will still receive an A+ ;)
------------------
This post was longer than I expected, so I decided to leave some examples of this framework to the next post. I hope you were able to grasp the main concepts of this framework for predicting individual sequences.
This discussion is completely based on the lecture notes written by Prof.
Csaba Szepesvari, Prof.
Andràs György and
David Pál. The notation used is also the same. Of course, any mistakes are completely my fault.
