Online Forest Density Estimation

Frederic Koriche CRIL
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:346-355, 2016.

Abstract

Online density estimation is the problem of predicting a sequence of outcomes, revealed one at a time, almost as well as the best expert chosen from a reference class of probabilistic models. The performance of each expert is measured with the log-likelihood loss. The class of experts examined in this paper is the family of discrete, acyclic graphical models, also known as Markov forests. By coupling Bayesian mixtures with symmetric Dirichlet priors for parameter learning, and a variant of “Follow the Perturbed Leader” strategy for structure learning, we derive an online forest density estimation algorithm that achieves a low regret, with a per-round time complexity that is quasi-quadratic in the input dimension. Using simple and flexible update rules, this algorithm can be easily adapted to predict with Markov trees or mixtures of Markov forests. Empirical results indicate that our online algorithm is a practical alternative to the state-of-the-art batch algorithms for learning tree-structured graphical models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-cril16a, title = {Online Forest Density Estimation}, author = {CRIL, Frederic Koriche}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {346--355}, 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/cril16a/cril16a.pdf}, url = {https://proceedings.mlr.press/r14/cril16a.html}, abstract = {Online density estimation is the problem of predicting a sequence of outcomes, revealed one at a time, almost as well as the best expert chosen from a reference class of probabilistic models. The performance of each expert is measured with the log-likelihood loss. The class of experts examined in this paper is the family of discrete, acyclic graphical models, also known as Markov forests. By coupling Bayesian mixtures with symmetric Dirichlet priors for parameter learning, and a variant of “Follow the Perturbed Leader” strategy for structure learning, we derive an online forest density estimation algorithm that achieves a low regret, with a per-round time complexity that is quasi-quadratic in the input dimension. Using simple and flexible update rules, this algorithm can be easily adapted to predict with Markov trees or mixtures of Markov forests. Empirical results indicate that our online algorithm is a practical alternative to the state-of-the-art batch algorithms for learning tree-structured graphical models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Online Forest Density Estimation %A Frederic Koriche CRIL %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-cril16a %I PMLR %P 346--355 %U https://proceedings.mlr.press/r14/cril16a.html %V R14 %X Online density estimation is the problem of predicting a sequence of outcomes, revealed one at a time, almost as well as the best expert chosen from a reference class of probabilistic models. The performance of each expert is measured with the log-likelihood loss. The class of experts examined in this paper is the family of discrete, acyclic graphical models, also known as Markov forests. By coupling Bayesian mixtures with symmetric Dirichlet priors for parameter learning, and a variant of “Follow the Perturbed Leader” strategy for structure learning, we derive an online forest density estimation algorithm that achieves a low regret, with a per-round time complexity that is quasi-quadratic in the input dimension. Using simple and flexible update rules, this algorithm can be easily adapted to predict with Markov trees or mixtures of Markov forests. Empirical results indicate that our online algorithm is a practical alternative to the state-of-the-art batch algorithms for learning tree-structured graphical models. %Z Reissued by PMLR on 04 October 2026.
APA
CRIL, F.K.. (2016). Online Forest Density Estimation. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:346-355 Available from https://proceedings.mlr.press/r14/cril16a.html. Reissued by PMLR on 04 October 2026.

Related Material