Pruning Rules for Learning Parsimonious Context Trees

Show full item record



Permalink

http://hdl.handle.net/10138/164537

Citation

Eggeling , R & Koivisto , M K H 2016 , Pruning Rules for Learning Parsimonious Context Trees . in A Ihler & D Janzing (eds) , Uncertainty in Artificial Intelligence : Proceedings of the Thirty-Second Conference (2016) June 25-29, 2016, Jersey City, New Jersey, USA . AUAI Press , Corvallis, Oregon , pp. 152-161 , Conference on Uncertainty in Artificial Intelligence , Jersey City, New Jersey , United States , 25/06/2016 .

Title: Pruning Rules for Learning Parsimonious Context Trees
Author: Eggeling, Ralf; Koivisto, Mikko Kalle Henrik
Editor: Ihler, Alexander; Janzing, Dominik
Contributor: University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Department of Computer Science
Publisher: AUAI Press
Date: 2016
Language: eng
Number of pages: 10
Belongs to series: Uncertainty in Artificial Intelligence Proceedings of the Thirty-Second Conference (2016) June 25-29, 2016, Jersey City, New Jersey, USA
ISBN: 978-0-9966431-1-5
URI: http://hdl.handle.net/10138/164537
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.
Subject: 113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
UAI2016_Paper66.pdf 586.0Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record