Advancing Theory and Methodology for Tree-Based Algorithms in High Dimensions

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Predictive statistical modeling has long been part of the backbone of science and engineering. In recent years, the proliferation of big data has led to a need to go beyond traditional linear models, and a need for flexible models that can exploit complicated nonlinear relationships. Models based on decision trees have emerged as an easy-to-use and high performing class of models, especially for unstructured tabular datasets such as electronic health records, in which they have been found to typically outperform neural networks. Furthermore, since decision trees can be easily visualized and simulated by non-experts, this makes them easier to audit than black box machine learning models, which is especially important when predictions are used to guide high-stakes decisions in the clinic or the courtroom. Unfortunately, models based on decision trees are not well understood statistically, and it is still unclear when and why various models obtain better relative predictive performance. The project plans to bridge this gap by identifying structural properties in real world datasets that make them either amenable or not amenable to current tree-based models. This understanding will then be used to develop better algorithms based on decision trees, as well as methodology to extract reproducible scientific insights from these models. In the duration of the project, graduate students will be trained in theory, domain-driven data science, and open-source software development. Research results will further be disseminated through courses, an upcoming book, and presentations at workshops and conferences. The project plans two thrusts to develop relevant theory for decision trees and random forests. First, it will analyze the generalization performance of tree-based algorithms on a range of different generative regression models in order to elicit their inductive bias. Inductive bias is a well-known concept from machine learning, and is defined as the assumptions an algorithm makes when generalizing to new data. Since real world datasets often present some structure that can be exploited using the right inductive bias, results of this project will allow better identification of which algorithm to choose in a given application, thus improving on classical nonparametric regression analysis of decision trees and random forests. Second, the project will study a new general framework for obtaining model-agnostic nonlinear feature significance measures using mean decrease in impurity (MDI) feature importance. This framework makes use of a novel interpretation of MDI in terms of r-squared values from linear regression, and is asymptotically valid even if the decision tree used to generate MDI is not necessarily a good model for the underlying regression function. 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.