Theory and Applications of Agnostic PAC-Learning with Small Decision Trees

摘要: Abstract We exhibit a theoretically founded algorithm T2 for agnostic PAC-learning of decision trees at most 2 levels, whose computation time is almost linear in the size training set. evaluate performance this learning on 15 common “real-world” datasets, and show that these datasets provides simple with little or no loss predictive power (compared C4.5). In fact, continuous attributes its error rate tends to be lower than C4.5. To best our knowledge first shown applicable classification problems. Since one can prove an PAC- algorithm, guaranteed produce close optimal 2-level from sufficiently large sets any (!) distribution data. regard differs strongly all other algorithms are considered applied machine learning, which guarantee given about their new datasets. also demonstrate used as diagnostic tool investigation expressive limits trees. Finally, T2, combination bounds VC-dimension bounded depth we derive, us now tools necessary comparing curves theoretical estimates theory.