Pruning Rules for Learning Parsimonious Context Trees

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu


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.
OtsikkoUncertainty in Artificial Intelligence : Proceedings of the Thirty-Second Conference (2016) June 25-29, 2016, Jersey City, New Jersey, USA
ToimittajatAlexander Ihler, Dominik Janzing
JulkaisupaikkaCorvallis, Oregon
KustantajaAUAI Press
ISBN (painettu)978-0-9966431-1-5
TilaJulkaistu - 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaConference on Uncertainty in Artificial Intelligence - Jersey City, New Jersey, Yhdysvallat (USA)
Kesto: 25 kesäkuuta 201629 kesäkuuta 2016
Konferenssinumero: 32


Proceeding volume:


  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä