Constrained complexity generalized context-tree algorithms

Robert J. Drost, Andrew C. Singer

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

Abstract

In this paper, we present a generalization of the context tree weighting algorithm that can address limitations imposed by the tree structure of traditional context-tree algorithms. By allowing a more general graphical structure, we demonstrate how a greatly increased class of models can be compactly represented using a context graph. Furthermore, through a judicious choice of this context graph, we show that a modified version of the weighting algorithm exists with computational complexity that remains linear in the context-graph depth. Although we present this method specifically in the context of universal prediction and focus on a particular context graph, the method is generally applicable and can be used to trade off algorithmic complexity with modeling power.

Original languageEnglish (US)
Title of host publication2007 IEEE/SP 14th Workshop on Statistical Signal Processing, SSP 2007, Proceedings
Pages131-135
Number of pages5
DOIs
StatePublished - Dec 1 2007
Event2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007 - Madison, WI, United States
Duration: Aug 26 2007Aug 29 2007

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings

Other

Other2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007
Country/TerritoryUnited States
CityMadison, WI
Period8/26/078/29/07

Keywords

  • Context tree weighting
  • Graph theory
  • Trees (graphs)
  • Universal algorithms

ASJC Scopus subject areas

  • Signal Processing

Fingerprint

Dive into the research topics of 'Constrained complexity generalized context-tree algorithms'. Together they form a unique fingerprint.

Cite this