  Decision trees are a popular tool in machine learning and yield
easy-to-understand models. Several techniques have been proposed in the
literature for learning a decision tree classifier, with different techniques
working well for data from different domains. In this work, we develop
approaches to design decision tree learning algorithms given repeated access to
data from the same domain. We propose novel parameterized classes of node
splitting criteria in top-down algorithms, which interpolate between popularly
used entropy and Gini impurity based criteria, and provide theoretical bounds
on the number of samples needed to learn the splitting function appropriate for
the data at hand. We also study the sample complexity of tuning prior
parameters in Bayesian decision tree learning, and extend our results to
decision tree regression. We further consider the problem of tuning
hyperparameters in pruning the decision tree for classical pruning algorithms
including min-cost complexity pruning. We also study the interpretability of
the learned decision trees and introduce a data-driven approach for optimizing
the explainability versus accuracy trade-off using decision trees. Finally, we
demonstrate the significance of our approach on real world datasets by learning
data-specific decision trees which are simultaneously more accurate and
interpretable.
