Finite-Memory Universal Prediction of Individual Continuous Sequences

Details Finite-Memory Universal Prediction of Individual Continuous Sequences Finite-Memory Universal Prediction of Individual Continuous Sequences

2011-02-14

arxiv.org/abs/1102.2836v3

Computer Science

Information Theory

Scientific paper

In this paper we consider the problem of universal prediction of individual {\em continuous} sequences with square-error loss, using a deterministic finite-state machine (FSM). The goal is to attain universally the performance of the best constant predictor tuned to the sequence, which predicts the empirical mean and incurs the empirical variance as the loss. The paper analyzes the tradeoff between the number of states of the universal FSM and the excess loss (regret). We first present the Exponential Decaying Memory (EDM) machine, used in the past for predicting binary sequences, and show bounds on its performance. Then we look explicitly for the optimal machine with a small number of states. We consider a class of machines denoted the Degenerated Tracking Memory (DTM) machines, find the optimal DTM machine and show that it outperforms any other machine for a small number of states. Incidentally, we prove a lower bound indicating that even with large number of states the regret of the DTM machines does not vanish. Finally, we study the problem of universal machines with large number of states. We prove a lower bound on the achievable regret of any FSM, a lower bound that defines the best rate in which the regret can vanish with the number of states. Then we propose a new machine, the Enhanced Exponential Decaying Memory, which attains the bound and outperforms the EDM machine for any number of states.

Affiliated with

Also associated with

No associations

Rating

Finite-Memory Universal Prediction of Individual Continuous Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finite-Memory Universal Prediction of Individual Continuous Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite-Memory Universal Prediction of Individual Continuous Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216684