Optimal data compression of data streams can be mathematically reduced to being able to predict a sequence of zeros and ones. This is a classical problem in probability theory which was illustrated by Laplace in the 18th century by asking ''What is the probability that the sun will rise tomorrow?''. Laplace derived a solution that is today known as Laplace's Rule of Succession. It assigns the probability (k+1)/(m+2) to any event that has occurred k times in m trials so that the probability of the event is proportional to the number of its occurrences plus one. For this reason, it is also called the ‘‘add–1 rule’’.
Over the years, probabilists and information theorists have proposed multitudes of alternatives for Laplace's rule. However, the required computations are often infeasible. Moreover, some strategies require that the total number of predictions to be made, or the horizon, needs to be known in advance. If this is the case, is not possible to provide the optimal prediction after m steps unless we know how many more steps are left.
In a paper to appear in the leading machine learning journal, Journal of Machine Learning Research, Kazuho Watanabe of the Toyohashi University of Technology and Teemu Roos of HIIT provide new insight into the achievability of asymptotic optimality with or without knowledge of the horizon. The main theoretical result gives a negative answer to an open problem asking whether the loss due to lack of knowledge of the horizon can be made to vanish as the number of predictions grows.
Watanabe and Roos also propose a set of prediction strategies (shown as the three lowest curves in the above figure) that take advantage of a known horizon in novel ways to achieve significantly better predictions than earlier strategies (the two highest curves in the same figure). Surprisingly, a simple variant of Laplace's rule is found to perform extremely well: if Laplace's rule is expressed as an ‘‘add–α rule’’ with α=1, the new rule can be represented as ‘‘add–α’’ with the value of α depending on the horizon according to the following simple formula, where n is the horizon:
Based on the above asymptotically optimal rule, since today (February 25) the sun has risen 56 times since the turn of the year and there are 309 days left until the next one, the probability that the sun will rise tomorrow is 99.2 %. Laplace's rule, on the other hand, would give probability 98.3 %. In either case, a pretty safe bet. (Note that no guarantees are given about the chance of overcast.)
- K. Watanabe and T. Roos, "Achievability of asymptotic minimax regret by horizon-dependent and horizon-independent strategies", to appear in Journal of Machine Learning Research, 2015.
- K. Watanabe, T. Roos, and P. Myllymäki, "Achievability of asymptotic minimax regret in online and batch prediction", in Proc. 5th Asian Conference on Machine Learning (ACML-2013), JMLR W&CP 29, 2013, pp. 181–196.
Last updated on 3 Mar 2015 by Teemu Roos - Page created on 25 Feb 2015 by Teemu Roos