ML Anthology

PAC-Bayes Tree: Weighted Subtrees with Guarantees

Tin D Nguyen, Samory Kpotufe
NeurIPS 2018 pp. 9484-9492
/neurips/2018/nguyen2018neurips-pacbayes/

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Nguyen and Kpotufe. "PAC-Bayes Tree: Weighted Subtrees with Guarantees." Neural Information Processing Systems, 2018.

Markdown

[Nguyen and Kpotufe. "PAC-Bayes Tree: Weighted Subtrees with Guarantees." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/nguyen2018neurips-pacbayes/)

BibTeX

@inproceedings{nguyen2018neurips-pacbayes,
  title     = {{PAC-Bayes Tree: Weighted Subtrees with Guarantees}},
  author    = {Nguyen, Tin D and Kpotufe, Samory},
  booktitle = {Neural Information Processing Systems},
  year      = {2018},
  pages     = {9484-9492},
  url       = {https://mlanthology.org/neurips/2018/nguyen2018neurips-pacbayes/}
}