Universal context tree PTH-order least squares prediction

Andrew C. 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