PAC-Bayes Tree: weighted subtrees with guarantees
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyGeneral ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Global Neural CCG Parsing with Optimality Guarantees
We introduce the first global recursive neural parsing model with optimality guarantees during decoding. To support global features, we give up dynamic programs and instead search directly in the space of all possible su…
SentenceA Simple and Efficient Method to Compute a Single Linkage Dendrogram
We address the problem of computing a single linkage dendrogram. A possible approach is to: (i) Form an edge weighted graph $G$ over the data, with edge weights reflecting dissimilarities. (ii) Calculate the MST $T$ of $…
Detection of Common Subtrees with Identical Label Distribution
Frequent pattern mining is a relevant method to analyse structured data, like sequences, trees or graphs. It consists in identifying characteristic substructures of a dataset. This paper deals with a new type of patterns…
MRBTP: Efficient Multi-Robot Behavior Tree Planning and Collaboration
Multi-robot task planning and collaboration are critical challenges in robotics. While Behavior Trees (BTs) have been established as a popular control architecture and are plannable for a single robot, the development of…
Robot Task PlanningTask PlanningLearning Context-Aware Representations of Subtrees
This thesis tackles the problem of learning efficient representations of complex, structured data with a natural application to web page and element classification. We hypothesise that the context around the element insi…
Classification