Skip to yearly menu bar Skip to main content


Poster

PAC-Bayes Tree: weighted subtrees with guarantees

Tin Nguyen · Samory Kpotufe

Room 517 AB #109

Keywords: [ Learning Theory ] [ Classification ]


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.

Live content is unavailable. Log in and register to view live content