AF: Small: Building a rich and rigorous theory of decision tree learning

Stanford University, Stanford CA

Investigators

Abstract

Decision trees are logical flowcharts that specify how responses to a sequence of questions can be amalgamated into a single global decision. Decision trees are one of the most natural ways of representing decision-making processes and they pervade everyday life. For example, a loan approval decision can reasonably be modeled as a decision tree that amalgamates various information about the applicant --- for example, "What is their annual income?"; "Have they defaulted on a loan in the past 5 years?"; etc. --- into a single global decision, whether the loan is approved or denied. Decision trees are also very basic objects of study throughout computer science and they play an increasingly important role in machine learning (ML). A central problem here, well studied since the 1970s, is that of decision tree learning: the algorithmic task of efficiently building a decision tree that represents a dataset. For example, given a dataset of applicants who had approved or denied loans, the task would be to build a decision tree that explains these decisions. In this project, the investigator will develop new algorithms for decision tree learning, as well as establish rigorous mathematical guarantees for existing decision tree learning algorithms that are widely used in practice. An important educational goal of this project is to train undergraduates and graduate students through the process of research collaboration and mentorship, with a particular goal of building expertise in decision tree learning and the theory of machine learning more generally. The investigator will also develop new curricular materials and maintain a tight feedback loop with experimental work and with ML practitioners. The popularity and effectiveness of decision trees in machine learning, and throughout computer science more generally, stem from their simplicity. They are extremely fast to evaluate, with evaluation time scaling with their depth, a quantity that is often exponentially smaller than their overall representation size. Alongside other classics such as linear regression, k-means, k-nearest neighbors, and support vector machines, heuristics for learning decision trees are an essential topic in any introductory ML course, and they are part of the standard toolkit of every ML practitioner. The logical and hierarchical structure of decision trees makes them easy to understand, and they are the most canonical example of an explainable model. A recent survey lists decision tree learning as the very first of "10 grand challenges" for the emerging field of explainable ML. Despite its empirical importance and success, many of the most basic theoretical questions regarding decision tree learning remain wide open. The investigator and his students have been working on addressing this for the past couple of years, and this project is structured around two overarching goals that have emerged from their research: (i) Develop new decision tree learning algorithms that advance our fundamental understanding of the problem. (ii) Establish performance guarantees for standard decision tree learning heuristics used in practice and place their empirical success on a firm theoretical footing. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.