English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Decision trees are popular machine learning models that are simple to buildand easy to interpret. Even though algorithms to learn decision trees date backto almost 50 years, key properties affecting their generalization error arestill weakly bounded. Hence, we revisit binary decision trees on real-valuedfeatures from the perspective of partitions of the data. We introduce thenotion of partitioning function, and we relate it to the growth function and tothe VC dimension. Using this new concept, we are able to find the exact VCdimension of decision stumps, which is given by the largest integer $d$ suchthat $2\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$, where $\ell$is the number of real-valued features. We provide a recursive expression tobound the partitioning functions, resulting in a upper bound on the growthfunction of any decision tree structure. This allows us to show that the VCdimension of a binary tree structure with $N$ internal nodes is of order $N\log(N\ell)$. Finally, we elaborate a pruning algorithm based on these resultsthat performs better than the CART algorithm on a number of datasets, with theadvantage that no cross-validation is required.

Decision trees as partitioning machines to characterize their generalization properties