| |
Click here for full text:
On Delayed Prediction of Individual Sequences
Weinberger, Marcelo J.; Ordentlich, Erik
HPL-2001-162
Keyword(s): delayed prediction; sequential decision; on-line algorithms; general loss functions; Lempel-Ziv algorithm
Abstract: Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his/her predictions a number of steps in advance, with incomplete information. For finite action and observation spaces, it is shown that the prediction strategy that minimizes the worst-case regret with respect to the Bayes envelope is obtained through sub- sampling of the sequence of observations. The result extends to the case of logarithmic loss. For finite- state reference prediction strategies, the delayed finite-state predictability is defined and related to its non-delayed counterpart. As in the non-delayed case, an efficient on-line decision algorithm, based on the incremental parsing rule, is shown to perform in the long run essentially as well as the best finite-state strategy determined in hindsight, with full knowledge of the given sequence of observations. An application to adaptive prefetching in computer memory architectures is discussed.
39 Pages
Back to Index
|
printable version
