Bayesian variable order Markov models

Christos Dimitrakakis
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:161-168, 2010.

Abstract

We present a simple, effective generalisation of variable order Markov models to full online Bayesian estimation. The mechanism used is close to that employed in context tree weighting. The main contribution is the addition of a prior, conditioned on context, on the Markov order. The resulting construction uses a simple recursion and can be updated efficiently. This allows the model to make predictions using more complex contexts, as more data is acquired, if necessary. In addition, our model can be alternatively seen as a mixture of tree experts. Experimental results show that the predictive model exhibits consistently good performance in a variety of domains.

Cite this Paper


BibTeX
@InProceedings{pmlr-v9-dimitrakakis10a, title = {Bayesian variable order Markov models}, author = {Dimitrakakis, Christos}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {161--168}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/dimitrakakis10a/dimitrakakis10a.pdf}, url = { http://proceedings.mlr.press/v9/dimitrakakis10a.html }, abstract = {We present a simple, effective generalisation of variable order Markov models to full online Bayesian estimation. The mechanism used is close to that employed in context tree weighting. The main contribution is the addition of a prior, conditioned on context, on the Markov order. The resulting construction uses a simple recursion and can be updated efficiently. This allows the model to make predictions using more complex contexts, as more data is acquired, if necessary. In addition, our model can be alternatively seen as a mixture of tree experts. Experimental results show that the predictive model exhibits consistently good performance in a variety of domains.} }
Endnote
%0 Conference Paper %T Bayesian variable order Markov models %A Christos Dimitrakakis %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-dimitrakakis10a %I PMLR %P 161--168 %U http://proceedings.mlr.press/v9/dimitrakakis10a.html %V 9 %X We present a simple, effective generalisation of variable order Markov models to full online Bayesian estimation. The mechanism used is close to that employed in context tree weighting. The main contribution is the addition of a prior, conditioned on context, on the Markov order. The resulting construction uses a simple recursion and can be updated efficiently. This allows the model to make predictions using more complex contexts, as more data is acquired, if necessary. In addition, our model can be alternatively seen as a mixture of tree experts. Experimental results show that the predictive model exhibits consistently good performance in a variety of domains.
RIS
TY - CPAPER TI - Bayesian variable order Markov models AU - Christos Dimitrakakis BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-dimitrakakis10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 161 EP - 168 L1 - http://proceedings.mlr.press/v9/dimitrakakis10a/dimitrakakis10a.pdf UR - http://proceedings.mlr.press/v9/dimitrakakis10a.html AB - We present a simple, effective generalisation of variable order Markov models to full online Bayesian estimation. The mechanism used is close to that employed in context tree weighting. The main contribution is the addition of a prior, conditioned on context, on the Markov order. The resulting construction uses a simple recursion and can be updated efficiently. This allows the model to make predictions using more complex contexts, as more data is acquired, if necessary. In addition, our model can be alternatively seen as a mixture of tree experts. Experimental results show that the predictive model exhibits consistently good performance in a variety of domains. ER -
APA
Dimitrakakis, C.. (2010). Bayesian variable order Markov models. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:161-168 Available from http://proceedings.mlr.press/v9/dimitrakakis10a.html .

Related Material