How difficult is it to understand a Machine Learning method based on integer optimization?

Question

I'm trying to understand a paper called "Supersparse Linear Integer Models for Predictive Scoring Systems" by Ustun, Tracà and Rudin, who introduce a really interesting method for generating an understandable classification system that actually challenges machine learning models for binary decisions in at least some areas. According to the authors, they use a mixed-integer problem (MIP), whose objective penalizes the training error (of which I do not what it is), the $L_0$-norm and the $L_1$-norm (of which I know the definition in regular Linear Algebra cases, but not in this instance) of its coefficients.

In their formulation, they use an optimization in the form of:

$$\min_\lambda\frac{1}{N}\sum_{i = 1}^{N}\mathbb{1}[y_1x_1^\top\lambda \leq 0] + C_0\|\lambda\|_0+C_1\|\lambda\|_1$$

which produces a classifier $\hat y = \operatorname{sgn}(x^\top\lambda)$ where $x \in \mathbb{R}^P$ is a vector of features (with $P$ being number of features), $\lambda \in \mathbb{Z}^P$ being number of coefficients and $\hat y \in \{-1,1\}$ being the predicted labels. Also within the formula, $C_0$ and $C_1$ are referred to as penalties, and the paper continues by listing an MIP with $N + 3P$ variables and $2N + 6P$ constraints, which I could also have listed, but didn't, since I only wanted to give an idea of what I will have to work with.

Now, the reason I even posted all this here, is not because I'm expecting an explanation of the research, but rather because I'd be really happy if anybody could provide me with information on what topics I will have to deal with and whether anyone with knowledge on this can tell if I should even bother trying to understand it.

I'm a second-year physics and third-year psychology student with basic knowledge in Statistics, Linear Algebra, and Analysis (we got introduced to multivariate analysis some while ago and were talking about Lagrange Multipliers and more general integrals (Lebesgue, Darboux) in the last lessons).

Regarding the paper, I now started out by looking at optimization problems, for which I found some very easy and comprehensible examples, and then looked at examples of Linear-Programming Problems, which I understand to be optimization problems in which the function domain has been constrained, for example by some inequalities.

I really want to apologize for the vast and general character of my question and understand that there probably is no simple solution to this and do not want to upset anyone with it, but I'm rather just looking for general information on whether these types of problem are graspable for someone with basic understanding in math and what type of material I should read/watch/work out. Any help is greatly appreciated.

---

If this is the wrong forum to ask this question, please let me know.

Answer 1

This forum is fine for this question. The training error is just the first term (summation) in the objective function. Technically, I would say the sum without the factor $\frac{1}{N}$ is the training error; they scaled it to make it commensurable in some sense with the penalties for model size (the two norm terms). The model size penalties are intended to discourage overfitting.

To understand how to solve the model (beyond "stick it in a solver program and turn the crank"), you would need to first understand linear programming (which optimizes a linear function of continuous variables subject to constraints posed as linear equalities and inequalities), and then move on to integer linear programming (in which some or all of those continuous variables are restricted to integer values, which makes solving much harder in general). On the other hand, to understand how to use this approach, you could get by with just an understanding of what integer linear programming is (basically what I just said, maybe expanded a bit), plus a knowledge of what are/are not suitable programs for solving such models (and how to specify the model as input to such a program), plus how to "linearize" the term in the summation (which I'm pretty sure Ustun et al. would do using so-called "big M" constraints). The distinction here is somewhat like learning to drive a car (second case) v. learning how the internal combustion engine works (first case).

The "drive the car" version (including what "big M" constraints are) is certainly within reach of someone with your math background, with what I would consider to be modest effort. The "internal combustion engine" version does not require more mathematical chops than what you have demonstrated, but does require quite a bit more time and effort getting up to speed ... and, I suspect, would not pay dividends in the psychology domain. (I refuse to speculate about physics, since I'm pretty sure all physics beyond basic mechanics is voodoo.)

Answer 2

I'd be really happy if anybody could provide me with information on what topics I will have to deal with and whether anyone with knowledge on this can tell if I should even bother trying to understand it.

The topics under discussion are medicine, statistics and artificial intelligence.

The paper "Supersparse Linear Integer Models for Predictive Scoring Systems" (Jun 25 2013), by Berk Ustun, Stefano Traca, and Cynthia Rudin is an introduction to a:

"formal approach for creating scoring systems, called Supersparse Linear Integer Models (SLIM). SLIM produces scoring systems that are accurate and interpretable using a mixed-integer program (MIP) whose objective penalizes the training error, $L^0$- norm (empty set) and $L^1$-norm of its coefficients.".

A scoring system consists of as small a list as possible of properties, each property is assigned a score. The score is added up and serves as a prediction of an outcome.

Receiver operating characteristic curve analysis provides tools to select possibly optimal models and to discard suboptimal ones independently from (and prior to specifying) the cost context or the class distribution. ROC analysis is related in a direct and natural way to cost/benefit analysis of diagnostic decision making.

A simple explanation is that they are optimizing the input space, collecting the least amount of data, asking the fewest questions, and using AI with MIP feedback to determine how optimal the answer is compared to using a full data set (a much larger list of information).

That permits a doctor to perform the fewest number of tests, or ask the patient the least number of questions, and obtain extremely close to the same diagnosis as would be obtained from a much more thorough (and costly) investigation.

... I'm rather just looking for general information on whether these types of problem are graspable for someone with basic understanding in math and what type of material I should read/watch/work out. Any help is greatly appreciated.

An example of how a new scoring system is developed and improved from an existing scoring system is presented in: "Validation and modification of the ‘Chiang Mai University Intussusception scoring system’ used to predict failure of non-surgical treatment in infantile intussusception" (July 23 2019), by Kaimook Boonsanit, Supika Kritsaneepaiboon, Piyawan Chiengkriwate, and Surasak Sangkhathat.

They were able to improve the sensitivity of the origonal Chiang Mai University Intussusception (CMUI) scoring system by altering the input parameters (asking different questions) at a cost of a small reduction in specificity.

Reading those articles, to understand scoring improvement, involves some understanding of medical terminology and procedures but doesn't require an understanding of artificial intelligence.

The original analysis, as described in "Prognostic indicators for failed nonsurgical reduction of intussusception", is simply:

"Statistical analysis was done with commercial statistical software (STATA 11.0; StataCorp LP, College Station, TX, USA). The descriptive data were reported in count and percent for categorical data, and mean and standard deviation or median and interquartile range for continuous data. The univariable analysis was done by Fisher’s exact test for categorical data and Student’s t-test or Mann–Whitney U-test for continuous data. The multivariable regression analysis of the prognostic factors for intussusception reduction failure was done by generalized linear model for exponential risk regression, and reported by risk ratio (RR) clustered by an age of 3 years (due to the risk for pathologic leading point). The receiver operating characteristic curve was plotted for assessing the performance of the multivariable model. The statistical significance level was set as two-tailed with a P-value <0.05.".

Ustun's paper is simply the application of artificial intelligence to determine the best input to provide the most optimal output, that differs from a simple application of Operations Research where most or all of the available data would be utilized to provide the most optimal solution.

A newer paper (Sept 17 2019) by Ustun and Rudin, "Learning Optimized Risk Scores" follows up on their earlier work:

Abstract
Risk scores are simple classification models that let users make quick risk predictions by adding and subtracting a few small numbers. These models are widely used in medicine and criminal justice, but are difficult to learn from data because they need to be calibrated, sparse, use small integer coefficients, and obey application-specific constraints.

In this paper, we introduce a machine learning method to learn risk scores. We formulate the risk score problem as a mixed integer nonlinear program, and present a cutting plane algorithm to recover its optimal solution. We improve our algorithm with specialized techniques that generate feasible solutions, narrow the optimality gap, and reduce data-related computation. Our algorithm can train risk scores in a way that scales linearly in the number of samples in a dataset, and that allows practitioners to address application-specific constraints without parameter tuning or post-processing.".