ML Anthology

Sample Compression Bounds for Decision Trees

Mohak Shah
ICML 2007 pp. 799-806
doi:10.1145/1273496.1273597 /icml/2007/shah2007icml-sample/

Abstract

We propose a formulation of the Decision Tree learning algorithm in the Compression settings and derive tight generalization error bounds. In particular, we propose Sample Compression and Occam's Razor bounds. We show how such bounds, unlike the VC dimension or Rademacher complexities based bounds, are more general and can also perform a margin-sparsity trade-off to obtain better classifiers. Potentially, these risk bounds can also guide the model selection process and replace traditional pruning strategies.

PDF ICML Semantic Scholar

Cite

Text

Shah. "Sample Compression Bounds for Decision Trees." International Conference on Machine Learning, 2007. doi:10.1145/1273496.1273597

Markdown

[Shah. "Sample Compression Bounds for Decision Trees." International Conference on Machine Learning, 2007.](https://mlanthology.org/icml/2007/shah2007icml-sample/) doi:10.1145/1273496.1273597

BibTeX

@inproceedings{shah2007icml-sample,
  title     = {{Sample Compression Bounds for Decision Trees}},
  author    = {Shah, Mohak},
  booktitle = {International Conference on Machine Learning},
  year      = {2007},
  pages     = {799-806},
  doi       = {10.1145/1273496.1273597},
  url       = {https://mlanthology.org/icml/2007/shah2007icml-sample/}
}