Browsing by Author "Zhong, Chudi"

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find \textit{optimal} decision trees. These new techniques have the potential to trigger a paradigm shift where it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over a variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several orders of magnitude relative to the state-of-the art.

Machine learning has been increasingly deployed for myriad high-stakes decisions that deeply impact people's lives. This is concerning, because not every model can be trusted. Interpretability is crucial for making machine learning models trustworthy. It provides human-understandable reasons for each prediction. This, in turn, enables easier troubleshooting, responsible decision-making, and knowledge acquisition. However, there are two major challenges in using interpretable machine learning for high-stakes problems: (1) interpretable model optimization is often NP-hard, and (2) an inefficient feedback loop is present in the standard machine learning paradigm. My dissertation addresses these challenges and proposes a new paradigm for machine learning to advance trustworthy AI.

I first tackle the challenge of finding interpretable-yet-accurate models. This involves developing efficient optimization algorithms. Models obtained from these algorithms are inherently interpretable while maintaining accuracy comparable to that of black-box counterparts. I then discuss the interaction bottleneck in the standard machine learning paradigm and propose a new paradigm, called learning Rashomon sets, which finds and stores all machine learning models with loss that is within epsilon of the optimal loss. This allows users unprecedented ability to explore and interact with all well-performing models, enabling them to choose and modify models that are best suited for the application.