Universal context tree PTH-order least squares prediction

Andrew C. Singer; Suleyman S. Kozat; Georg C. Zeitler

doi:10.1109/MLSP.2006.275537

Universal context tree P^TH-order least squares prediction

Andrew C. Singer
, Suleyman S. Kozat
, Georg C. Zeitler

Office of the Dean of the College of Engineering and Applied Sciences

IBM
University of Illinois at Urbana-Champaign

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 p^th-order model.

Original language	English
Title of host publication	Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006
Publisher	IEEE Computer Society
Pages	141-146
Number of pages	6
ISBN (Print)	1424406560, 9781424406562
DOIs	https://doi.org/10.1109/MLSP.2006.275537
State	Published - 2006
Event	2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 - Maynooth, Ireland Duration: Sep 6 2006 → Sep 8 2006

Publication series

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

Conference

Conference	2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006
Country/Territory	Ireland
City	Maynooth
Period	09/6/06 → 09/8/06

Access to Document

10.1109/MLSP.2006.275537

Cite this

Singer, A. C., Kozat, S. S., & Zeitler, G. C. (2006). Universal context tree P^TH-order least squares prediction. In Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 (pp. 141-146). Article 4053636 (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006). IEEE Computer Society. https://doi.org/10.1109/MLSP.2006.275537

Singer, Andrew C. ; Kozat, Suleyman S. ; Zeitler, Georg C. / Universal context tree P^TH-order least squares prediction. Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006. IEEE Computer Society, 2006. pp. 141-146 (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006).

@inproceedings{4b43b09b0e564bc8a8dfee0b5000eceb,

title = "Universal context tree PTH-order least squares prediction",

abstract = "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.",

author = "Singer, \{Andrew C.\} and Kozat, \{Suleyman S.\} and Zeitler, \{Georg C.\}",

year = "2006",

doi = "10.1109/MLSP.2006.275537",

language = "English",

isbn = "1424406560",

series = "Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006",

publisher = "IEEE Computer Society",

pages = "141--146",

booktitle = "Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006",

note = "2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 ; Conference date: 06-09-2006 Through 08-09-2006",

}

Singer, AC, Kozat, SS & Zeitler, GC 2006, Universal context tree P^TH-order least squares prediction. in Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006., 4053636, Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006, IEEE Computer Society, pp. 141-146, 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006, Maynooth, Ireland, 09/6/06. https://doi.org/10.1109/MLSP.2006.275537

Universal context tree P^TH-order least squares prediction. / Singer, Andrew C.; Kozat, Suleyman S.; Zeitler, Georg C.
Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006. IEEE Computer Society, 2006. p. 141-146 4053636 (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

Y1 - 2006

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 - https://www.scopus.com/pages/publications/38949086490

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 -

Singer AC, Kozat SS, Zeitler GC. Universal context tree P^TH-order least squares prediction. In Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006. IEEE Computer Society. 2006. p. 141-146. 4053636. (Proceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006). doi: 10.1109/MLSP.2006.275537