Universal context tree PTH-order least squares prediction

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006
PublisherIEEE Computer Society
Pages141-146
Number of pages6
ISBN (Print)1424406560, 9781424406562
DOIs
StatePublished - Jan 1 2006
Event2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006 - Maynooth, Ireland
Duration: Sep 6 2006Sep 8 2006

Publication series

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

Other

Other2006 16th IEEE Signal Processing Society Workshop on Machine Learning for Signal Processing, MLSP 2006
CountryIreland
CityMaynooth
Period9/6/069/8/06

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Signal Processing

Cite this

Singer, A. C., Kozat, S. S., & Zeitler, G. C. (2006). Universal context tree PTH-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). [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

Universal context tree PTH-order least squares prediction. / Singer, Andrew Carl; 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 proceedingConference contribution

Singer, AC, Kozat, SS & Zeitler, GC 2006, Universal context tree PTH-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, 9/6/06. https://doi.org/10.1109/MLSP.2006.275537
Singer AC, Kozat SS, Zeitler GC. Universal context tree PTH-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). https://doi.org/10.1109/MLSP.2006.275537
Singer, Andrew Carl ; Kozat, Suleyman S. ; Zeitler, Georg C. / Universal context tree PTH-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{5832ffd6a44f4cd4a3ce8a3e676f2238,
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 Carl} and Kozat, {Suleyman S.} and Zeitler, {Georg C.}",
year = "2006",
month = "1",
day = "1",
doi = "10.1109/MLSP.2006.275537",
language = "English (US)",
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",

}

TY - GEN

T1 - Universal context tree PTH-order least squares prediction

AU - Singer, Andrew Carl

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

ER -