An automated exact solution framework towards best subset selection in logistic regression

Abstract

Logistic regression is a simplistic yet powerful modelling technique widely utilised to solve binary and multi-class classification problems. It provides interpretable and actionable insights about the relationship between independent variables and the target, which is not always possible when considering complex machine learning algorithms. As such, logistic regression is favoured as a modelling technique in the financial and healthcare industries where interpretability is paramount. Its interpretability relates to the fact that it can translate a linear combination of regression parameter estimates to a binary class domain while also providing statistically interpretable parameter estimates that could bring to light valuable underlying trends. Identifying a subset of predictive independent variables from a large set of potential inputs can drive much-needed value creation for any business. The NP-hard best subset selection problem is a well-known problem within literature, with multiple solution algorithms proposed to produce parsimonious predictive models. As part of this thesis, a novel exact automated solution framework is proposed to solve the best subset selection problem within the context of logistic regression. The framework uses a mixed integer programming piecewise linear underestimation of the log-likelihood function, as proposed by Venter (2020), while utilising explicit cardinality constraints to facilitate variable selection. The automated logistic regression solution framework (ALRSF) comprises four distinct steps: a cardinality selection step, a search space pruning step, an optimality step and a bound tightening step. The proposed framework also draws on techniques such as Benders decomposition and Lagrangian relaxation to reduce the computational burden associated with finding high-quality solutions while simultaneously making strides towards proving optimality. Empirical results show that the proposed solution framework significantly outperforms the standard branch-and-bound algorithm that is often used to perform best subset selection (which also serves as the benchmark during our comparison). Notable improvements in memory requirement, optimality gap size, problem size, and solution quality are observed. The results suggest that the proposed deterministic ALRSF provides a holistic and computationally efficient approach towards solving the NP-hard best subset selection problem.