Measuring the Shattering coefficient of Decision Tree models. (15th December 2019)

• Record Type: Journal Article
• Authors: de Mello, Rodrigo F.; Manapragada, Chaitanya; Bifet, Albert
• Is Part Of: Expert systems with applications. Volume 137(2019)
• Page Start: 443
• Page End: 452
• Publication Date: 2019-12-15
• Subjects: Shattering coefficient -- Decision Trees -- Statistical Learning Theory -- Learning guarantees; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.07.012
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: The Statistical Learning Theory to study learning guarantees of Decision Trees; The numerical formulation of the Shattering coefficient for Decision Trees; Complexity assessment of Decision-Tree models using the Generalization Bound. Abstract: In spite of the relevance of Decision Trees (DTs), there is still a disconnection between their theoretical and practical results while selecting models to address specific learning tasks. A particular criterion is provided by the Shattering coefficient, a growth function formulated in the context of the Statistical Learning Theory (SLT), which measures the complexity of the algorithm bias as sample sizes increase. In attempt to establish the basis for a relative theoretical complexity analysis, this paper introduces a method to compute the Shattering coefficient of DT models using recurrence equations. Next, we assess the bias of models provided by DT algorithms while solving practical problems as well as their overall learning bounds in light of the SLT. As the main contribution, our results support other researchers to decide on the most adequate DT models to tackle specific supervised learning tasks.