TY - GEN

T1 - Universal context tree PTH-order least squares prediction

AU - Singer, Andrew C.

AU - Kozat, Suleyman S.

AU - Zeitler, Georg C.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear pth-order model.

AB - We examine the sequential prediction of individual sequences under the square error loss using a competitive algorithm framework. Previous work has described a first-order algorithm that competes against a doubly exponential number of piecewise linear models. Using context trees, this firstorder algorithm achieves the performance of the best piecewise linear first-order model that can choose its prediction parameters observing the entire sequence in advance, uniformly, for any individual sequence, with a complexity only linear in the depth of the context tree. In this paper, we extend these results to a sequential predictor of order p > 1, that asymptotically performs as well as the best piecewise linear pth-order model.

UR - http://www.scopus.com/inward/record.url?scp=38949086490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38949086490&partnerID=8YFLogxK

U2 - 10.1109/MLSP.2006.275537

DO - 10.1109/MLSP.2006.275537

M3 - Conference contribution

AN - SCOPUS:38949086490

SN - 1424406560

SN - 9781424406562

T3 - Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006

SP - 141

EP - 146

BT - Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006

PB - IEEE Computer Society

T2 - 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006

Y2 - 6 September 2006 through 8 September 2006

ER -