Pruning Rules for Learning Parsimonious Context Trees

Ralf Eggeling, Mikko Koivisto
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:158-167, 2016.

Abstract

We give a novel algorithm for finding a parsimonious context tree (PCT) that best fits a given data set.PCTs extend traditional context trees by allowing context-specific grouping of the states of a context variable, also enabling skipping the variable.However, they gain statistical efficiency at the cost of computational efficiency, as the search space of PCTs is of tremendous size.We propose pruning rules based on efficiently computable score upper bounds with the aim of reducing this search space significantly.While our concrete bounds exploit properties of the BIC score, the ideas apply also to other scoring functions.Empirical results show that our algorithm is typically an order-of-magnitude faster than a recently proposed memory-intensive algorithm, or alternatively, about equally fast but using dramatically less memory.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-eggeling16a, title = {Pruning Rules for Learning Parsimonious Context Trees}, author = {Eggeling, Ralf and Koivisto, Mikko}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {158--167}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/eggeling16a/eggeling16a.pdf}, url = {https://proceedings.mlr.press/r14/eggeling16a.html}, abstract = {We give a novel algorithm for finding a parsimonious context tree (PCT) that best fits a given data set.PCTs extend traditional context trees by allowing context-specific grouping of the states of a context variable, also enabling skipping the variable.However, they gain statistical efficiency at the cost of computational efficiency, as the search space of PCTs is of tremendous size.We propose pruning rules based on efficiently computable score upper bounds with the aim of reducing this search space significantly.While our concrete bounds exploit properties of the BIC score, the ideas apply also to other scoring functions.Empirical results show that our algorithm is typically an order-of-magnitude faster than a recently proposed memory-intensive algorithm, or alternatively, about equally fast but using dramatically less memory.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Pruning Rules for Learning Parsimonious Context Trees %A Ralf Eggeling %A Mikko Koivisto %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-eggeling16a %I PMLR %P 158--167 %U https://proceedings.mlr.press/r14/eggeling16a.html %V R14 %X We give a novel algorithm for finding a parsimonious context tree (PCT) that best fits a given data set.PCTs extend traditional context trees by allowing context-specific grouping of the states of a context variable, also enabling skipping the variable.However, they gain statistical efficiency at the cost of computational efficiency, as the search space of PCTs is of tremendous size.We propose pruning rules based on efficiently computable score upper bounds with the aim of reducing this search space significantly.While our concrete bounds exploit properties of the BIC score, the ideas apply also to other scoring functions.Empirical results show that our algorithm is typically an order-of-magnitude faster than a recently proposed memory-intensive algorithm, or alternatively, about equally fast but using dramatically less memory. %Z Reissued by PMLR on 04 October 2026.
APA
Eggeling, R. & Koivisto, M.. (2016). Pruning Rules for Learning Parsimonious Context Trees. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:158-167 Available from https://proceedings.mlr.press/r14/eggeling16a.html. Reissued by PMLR on 04 October 2026.

Related Material