← Back to papers
2018 NIPS NeurIPS 2018

PAC-Bayes Tree: weighted subtrees with guarantees

Abstract

We present a weighted-majority classification approach over subtrees of a fixed tree, which provably achieves excess-risk of the same order as the best tree-pruning. Furthermore, the computational efficiency of pruning is maintained at both training and testing time despite having to aggregate over an exponential number of subtrees. We believe this is the first subtree aggregation approach with such guarantees.

🧭 Keyword Pioneer — tree pruning
🐣 Hot Topic Early Bird — decision tree
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Tin D Nguyen , Samory Kpotufe

Topics

Machine Learning > Core Methods > Classification Machine Learning > Optimization & Theory > Bayesian Inference Machine Learning > Optimization & Theory > Theory

Keywords

excess risk decision tree pac-bayesian theory tree pruning subtree aggregation weighted majority
Download PDF

Related papers

Maximum Causal Tsallis Entropy Imitation Learning 2018
Recurrent World Models Facilitate Policy Evolution 2018
Bandit Learning in Concave N-Person Games 2018
Algorithmic Assurance: An Active Approach to Algorithmic Testing using Bayesian Optimisation 2018
PAC-Bayes bounds for stable algorithms with instance-dependent priors 2018