conftrace_

2018 NeurIPS 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.

🐣 Hot Topic Early Bird - decision tree

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

More from NeurIPS 2018

All NeurIPS 2018 papers →

Learning a latent manifold of odor representations from neural responses in piriform cortex

Global Gated Mixture of Second-order Pooling for Improving Deep Convolutional Neural Networks

Neural Code Comprehension: A Learnable Representation of Code Semantics

Amortized Inference Regularization

Structure-Aware Convolutional Neural Networks

Alternating optimization of decision trees, with application to learning sparse oblique trees