Learning Decision Trees with Stochastic Linear Classifiers

Tom Jurgenson, Yishay Mansour
Proceedings of Algorithmic Learning Theory, PMLR 83:489-528, 2018.

Abstract

In this work we propose a top-down decision tree learning algorithm with a class of linear classifiers called stochastic linear classifiers as the internal nodes’ hypothesis class. To this end, we derive efficient algorithms for minimizing the Gini index for this class for each internal node, although the problem is non-convex. Moreover, the proposed algorithm has a theoretical guarantee under the weak stochastic hypothesis assumption.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-jurgenson18a, title = {Learning Decision Trees with Stochastic Linear Classifiers}, author = {Jurgenson, Tom and Mansour, Yishay}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {489--528}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/jurgenson18a/jurgenson18a.pdf}, url = {https://proceedings.mlr.press/v83/jurgenson18a.html}, abstract = {In this work we propose a top-down decision tree learning algorithm with a class of linear classifiers called stochastic linear classifiers as the internal nodes’ hypothesis class. To this end, we derive efficient algorithms for minimizing the Gini index for this class for each internal node, although the problem is non-convex. Moreover, the proposed algorithm has a theoretical guarantee under the weak stochastic hypothesis assumption.} }
Endnote
%0 Conference Paper %T Learning Decision Trees with Stochastic Linear Classifiers %A Tom Jurgenson %A Yishay Mansour %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-jurgenson18a %I PMLR %P 489--528 %U https://proceedings.mlr.press/v83/jurgenson18a.html %V 83 %X In this work we propose a top-down decision tree learning algorithm with a class of linear classifiers called stochastic linear classifiers as the internal nodes’ hypothesis class. To this end, we derive efficient algorithms for minimizing the Gini index for this class for each internal node, although the problem is non-convex. Moreover, the proposed algorithm has a theoretical guarantee under the weak stochastic hypothesis assumption.
APA
Jurgenson, T. & Mansour, Y.. (2018). Learning Decision Trees with Stochastic Linear Classifiers. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:489-528 Available from https://proceedings.mlr.press/v83/jurgenson18a.html.

Related Material