En iyi çözümlü karar ağaçları için kayarak ileriyi gören yaklaşımlar

Classification trees have gained tremendous attention in machine learning applications due to their inherently interpretable nature. Current state-of-the-art formulations for learning optimal binary classification trees suffer from scalability for larger depths or larger instances. Moreover, they mostly fail to prove optimality after long run times and fit perfectly to the training data while minimizing misclassification error which is likely fail to generalize to the test data. We present a simple but powerful new formulation which we call rolling look-ahead learning approach. By dropping tractability variables which are dependent on instance size, we present a novel two-depth optimal binary classification tree formulation with the objective to minimize gini impurity or misclassification error. The approach can be thought of as a middle ground between myopic and global optimization methods. For larger depths, we developed a hybrid approach which learns by looking ahead 2-steps rolling horizon. It is much faster than the fastest known global optimization methods which can solve an instance with around 50K rows & 135 features in less than 4 minutes, for depth 8. Also, in majority of cases, the proposed approach outperforms global optimization methods & CART in terms of win count tested for 7 depths, 10 Fold and 19 benchmark datasets, and increase in out-of-sample accuracy up to 16.8% and 11.9% with respect to global optimization methods and CART, respectively.