Context tree switching

Joel Veness; Kee Siong Ng; Marcus Hutter; Michael Bowling

doi:10.1109/DCC.2012.39

Context tree switching

Joel Veness^*, Kee Siong Ng, Marcus Hutter, Michael Bowling

^*Corresponding author for this work

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

31 Citations (Scopus)

Abstract

This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.

Original language	English
Title of host publication	Proceedings - DCC 2012
Subtitle of host publication	2012 Data Compression Conference
Pages	327-336
Number of pages	10
DOIs	https://doi.org/10.1109/DCC.2012.39
Publication status	Published - 2012
Event	2012 Data Compression Conference, DCC 2012 - Snowbird, UT, United States Duration: 10 Apr 2012 → 12 Apr 2012

Publication series

Name	Data Compression Conference Proceedings
ISSN (Print)	1068-0314

Conference

Conference	2012 Data Compression Conference, DCC 2012
Country/Territory	United States
City	Snowbird, UT
Period	10/04/12 → 12/04/12

Access to Document

10.1109/DCC.2012.39

Cite this

@inproceedings{2760d5234b0b45c6a632f1b3c88a84a5,

title = "Context tree switching",

abstract = "This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.",

keywords = "Context Tree Weighting",

author = "Joel Veness and Ng, {Kee Siong} and Marcus Hutter and Michael Bowling",

year = "2012",

doi = "10.1109/DCC.2012.39",

language = "English",

isbn = "9780769546568",

series = "Data Compression Conference Proceedings",

pages = "327--336",

booktitle = "Proceedings - DCC 2012",

note = "2012 Data Compression Conference, DCC 2012 ; Conference date: 10-04-2012 Through 12-04-2012",

}

TY - GEN

T1 - Context tree switching

AU - Veness, Joel

AU - Ng, Kee Siong

AU - Hutter, Marcus

AU - Bowling, Michael

PY - 2012

Y1 - 2012

N2 - This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.

AB - This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.

KW - Context Tree Weighting

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

U2 - 10.1109/DCC.2012.39

DO - 10.1109/DCC.2012.39

M3 - Conference contribution

SN - 9780769546568

T3 - Data Compression Conference Proceedings

SP - 327

EP - 336

BT - Proceedings - DCC 2012

T2 - 2012 Data Compression Conference, DCC 2012

Y2 - 10 April 2012 through 12 April 2012

ER -

Context tree switching

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this