Enumerating Distinct Decision Trees

Salvatore Ruggieri
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2960-2968, 2017.

Abstract

The search space for the feature selection problem in decision tree learning is the lattice of subsets of the available features. We provide an exact enumeration procedure of the subsets that lead to all and only the distinct decision trees. The procedure can be adopted to prune the search space of complete and heuristics search methods in wrapper models for feature selection. Based on this, we design a computational optimization of the sequential backward elimination heuristics with a performance improvement of up to 100X.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-ruggieri17a, title = {Enumerating Distinct Decision Trees}, author = {Salvatore Ruggieri}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2960--2968}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/ruggieri17a/ruggieri17a.pdf}, url = {https://proceedings.mlr.press/v70/ruggieri17a.html}, abstract = {The search space for the feature selection problem in decision tree learning is the lattice of subsets of the available features. We provide an exact enumeration procedure of the subsets that lead to all and only the distinct decision trees. The procedure can be adopted to prune the search space of complete and heuristics search methods in wrapper models for feature selection. Based on this, we design a computational optimization of the sequential backward elimination heuristics with a performance improvement of up to 100X.} }
Endnote
%0 Conference Paper %T Enumerating Distinct Decision Trees %A Salvatore Ruggieri %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-ruggieri17a %I PMLR %P 2960--2968 %U https://proceedings.mlr.press/v70/ruggieri17a.html %V 70 %X The search space for the feature selection problem in decision tree learning is the lattice of subsets of the available features. We provide an exact enumeration procedure of the subsets that lead to all and only the distinct decision trees. The procedure can be adopted to prune the search space of complete and heuristics search methods in wrapper models for feature selection. Based on this, we design a computational optimization of the sequential backward elimination heuristics with a performance improvement of up to 100X.
APA
Ruggieri, S.. (2017). Enumerating Distinct Decision Trees. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2960-2968 Available from https://proceedings.mlr.press/v70/ruggieri17a.html.

Related Material