Algorithms for learning parsimonious context trees

Show full item record



Eggeling , R , Grosse , I & Koivisto , M 2019 , ' Algorithms for learning parsimonious context trees ' , Machine Learning , vol. 108 , no. 6 , pp. 879-911 .

Title: Algorithms for learning parsimonious context trees
Author: Eggeling, Ralf; Grosse, Ivo; Koivisto, Mikko
Contributor organization: Department of Computer Science
Date: 2019-06
Language: eng
Number of pages: 33
Belongs to series: Machine Learning
ISSN: 0885-6125
Abstract: Parsimonious context trees, PCTs, provide a sparse parameterization of conditional probability distributions. They are particularly powerful for modeling context-specific independencies in sequential discrete data. Learning PCTs from data is computationally hard due to the combinatorial explosion of the space of model structures as the number of predictor variables grows. Under the score-and-search paradigm, the fastest algorithm for finding an optimal PCT, prior to the present work, is based on dynamic programming. While the algorithm can handle small instances fast, it becomes infeasible already when there are half a dozen four-state predictor variables. Here, we show that common scoring functions enable the use of new algorithmic ideas, which can significantly expedite the dynamic programming algorithm on typical data. Specifically, we introduce a memoization technique, which exploits regularities within the predictor variables by equating different contexts associated with the same data subset, and a bound-and-prune technique, which exploits regularities within the response variable by pruning parts of the search space based on score upper bounds. On real-world data from recent applications of PCTs within computational biology the ideas are shown to reduce the traversed search space and the computation time by several orders of magnitude in typical cases.
Subject: Exact algorithms
Structure learning
Context-specific independence
Branch and bound
Sequential data
113 Computer and information sciences
Peer reviewed: Yes
Rights: cc_by
Usage restriction: openAccess
Self-archived version: publishedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
Eggeling2019_Ar ... msForLearningParsimoni.pdf 1020.Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record