Top-down particle filtering for Bayesian decision trees

Balaji Lakshminarayanan, Daniel Roy, Yee Whye Teh
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):280-288, 2013.

Abstract

Decision tree learning is a popular approach for classification and regression in machine learning and statistics, and Bayesian formulations - which introduce a prior distribution over decision trees, and formulate learning as posterior inference given data - have been shown to produce competitive performance. Unlike classic decision tree learning algorithms like ID3, C4.5 and CART, which work in a top-down manner, existing Bayesian algorithms produce an approximation to the posterior distribution by evolving a complete tree (or collection thereof) iteratively via local Monte Carlo modifications to the structure of the tree, e.g., using Markov chain Monte Carlo (MCMC). We present a sequential Monte Carlo (SMC) algorithm that instead works in a top-down manner, mimicking the behavior and speed of classic algorithms. We demonstrate empirically that our approach delivers accuracy comparable to the most popular MCMC method, but operates more than an order of magnitude faster, and thus represents a better computation-accuracy tradeoff.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-lakshminarayanan13, title = {Top-down particle filtering for Bayesian decision trees}, author = {Lakshminarayanan, Balaji and Roy, Daniel and Whye Teh, Yee}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {280--288}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/lakshminarayanan13.pdf}, url = {https://proceedings.mlr.press/v28/lakshminarayanan13.html}, abstract = {Decision tree learning is a popular approach for classification and regression in machine learning and statistics, and Bayesian formulations - which introduce a prior distribution over decision trees, and formulate learning as posterior inference given data - have been shown to produce competitive performance. Unlike classic decision tree learning algorithms like ID3, C4.5 and CART, which work in a top-down manner, existing Bayesian algorithms produce an approximation to the posterior distribution by evolving a complete tree (or collection thereof) iteratively via local Monte Carlo modifications to the structure of the tree, e.g., using Markov chain Monte Carlo (MCMC). We present a sequential Monte Carlo (SMC) algorithm that instead works in a top-down manner, mimicking the behavior and speed of classic algorithms. We demonstrate empirically that our approach delivers accuracy comparable to the most popular MCMC method, but operates more than an order of magnitude faster, and thus represents a better computation-accuracy tradeoff.} }
Endnote
%0 Conference Paper %T Top-down particle filtering for Bayesian decision trees %A Balaji Lakshminarayanan %A Daniel Roy %A Yee Whye Teh %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-lakshminarayanan13 %I PMLR %P 280--288 %U https://proceedings.mlr.press/v28/lakshminarayanan13.html %V 28 %N 3 %X Decision tree learning is a popular approach for classification and regression in machine learning and statistics, and Bayesian formulations - which introduce a prior distribution over decision trees, and formulate learning as posterior inference given data - have been shown to produce competitive performance. Unlike classic decision tree learning algorithms like ID3, C4.5 and CART, which work in a top-down manner, existing Bayesian algorithms produce an approximation to the posterior distribution by evolving a complete tree (or collection thereof) iteratively via local Monte Carlo modifications to the structure of the tree, e.g., using Markov chain Monte Carlo (MCMC). We present a sequential Monte Carlo (SMC) algorithm that instead works in a top-down manner, mimicking the behavior and speed of classic algorithms. We demonstrate empirically that our approach delivers accuracy comparable to the most popular MCMC method, but operates more than an order of magnitude faster, and thus represents a better computation-accuracy tradeoff.
RIS
TY - CPAPER TI - Top-down particle filtering for Bayesian decision trees AU - Balaji Lakshminarayanan AU - Daniel Roy AU - Yee Whye Teh BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-lakshminarayanan13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 280 EP - 288 L1 - http://proceedings.mlr.press/v28/lakshminarayanan13.pdf UR - https://proceedings.mlr.press/v28/lakshminarayanan13.html AB - Decision tree learning is a popular approach for classification and regression in machine learning and statistics, and Bayesian formulations - which introduce a prior distribution over decision trees, and formulate learning as posterior inference given data - have been shown to produce competitive performance. Unlike classic decision tree learning algorithms like ID3, C4.5 and CART, which work in a top-down manner, existing Bayesian algorithms produce an approximation to the posterior distribution by evolving a complete tree (or collection thereof) iteratively via local Monte Carlo modifications to the structure of the tree, e.g., using Markov chain Monte Carlo (MCMC). We present a sequential Monte Carlo (SMC) algorithm that instead works in a top-down manner, mimicking the behavior and speed of classic algorithms. We demonstrate empirically that our approach delivers accuracy comparable to the most popular MCMC method, but operates more than an order of magnitude faster, and thus represents a better computation-accuracy tradeoff. ER -
APA
Lakshminarayanan, B., Roy, D. & Whye Teh, Y.. (2013). Top-down particle filtering for Bayesian decision trees. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):280-288 Available from https://proceedings.mlr.press/v28/lakshminarayanan13.html.

Related Material