Discrete and Continuous Optimization for Interpretable Machine Learning in High Stakes Decision Making

Abstract

In high-stakes decision-making and scientific knowledge discovery, the demand for interpretable machine learning models is paramount.These models must not only exhibit high predictive capabilities but also provide domain experts with a clear understanding of the underlying decision-making processes. This transparency empowers professionals to leverage their domain expertise to evaluate the validity and relevance of the model's predictions.At the heart of developing such interpretable models is to solve a complex combinatorial problem.Conventional methods, like $\ell_1$ regularization, often compromise solution quality. In contrast, $\ell_0$-based methods, while precise, face challenges due to their NP-hard nature, rendering them unscalable for large-scale datasets.This Ph.D. dissertation is dedicated to bridging this statistical and computational gap.In the following sections, we present four interrelated works, covering statistical models such as generalized additive models, scoring systems, linear regression, and Cox proportional hazards models. These works are unified by the use of discrete and continuous optimization techniques to develop simple yet highly accurate models. Given the combinatorial nature of the optimization problems, we develop novel algorithms from three perspectives: (1) searching for optimal solutions, (2) certifying the optimality of solutions, and (3) decomposing and exploiting hidden structures.The algorithms developed in this dissertation efficiently produce high-quality solutions across various fields such as healthcare, criminal justice, finance, and scientific discovery.On real-world datasets with thousands of features and observations, our algorithms can generate models with only 10-20 parameters in seconds to minutes, with predictive performance on par with black-box models. By leveraging the synergy between machine learning and optimization, this research contributes towards making AI systems more trustworhty and human-centered.