Learning Optimal Predictive Checklists
Year: 2022

Abstract:
Checklists are simple decision aids that are often used to promote safety and reliability in clinical applications. In this paper, we present a method to learn checklists for clinical decision support. We represent predictive checklists as discrete linear classifiers with binary features and unit weights. We then learn globally optimal predictive checklists from data by solving an integer programming problem. Our method allows users to customize checklists to obey complex constraints, including constraints to enforce group fairness and to binarize realvalued features at training time. In addition, it pairs models with an optimality gap that can inform model development and determine the feasibility of learning sufficiently accurate checklists on a given dataset. We pair our method with specialized techniques that speed up its ability to train a predictive checklist that performs well and has a small optimality gap. We benchmark the performance of our method on seven clinical classification problems, and demonstrate its practical benefits by training a short-form checklist for PTSD screening. Our results show that our method can fit simple predictive checklists that perform well and that can easily be customized to obey a rich class of custom constraints.

heading: 1 Introduction
text: Checklists are simple tools that are widely used to assist humans when carrying out important tasks or making important decisions [8, 13, 18, 35, 44, 50, 60, 61, 64, 65, 66]. These tools are often used as predictive models in modern healthcare applications. In such settings, a checklist is a set of Boolean conditions that predicts a condition of interest – e.g., a list of symptoms flag a patient for a critical illness when M out N symptoms are checked. These kinds of “predictive checklists” are often used for clinical decision support because they are easy to use and easy to understand [33, 54]. In contrast to other kinds of predictive models, clinicians can easily scrutinize a checklist, and make an informed decision as to whether they will adopt it. Once they have decided to use a checklist, they can integrate the model into their clinical workflow without extensive training or technology (e.g., as a printed sheet [52]).
Considering these benefits, one of the key challenges in using predictive checklists in healthcare applications is finding a reliable way to create them [33]. Most predictive checklists in medicine are either hand-crafted by panels of experts [30, 41], or built by combining statistical techniques and heuristics [e.g., logistic regression, stepwise feature selection, and rounding 39]. These approaches
* Equal supervision.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
make it difficult to develop checklists that are sufficiently accurate – as panel or pipeline will effectively need to specify a model that performs well under stringent assumptions on model form. Given the simplicity of the model class, it is entirely possible that some datasets may never admit a checklist that is sufficiently accurate to deploy in a clinical setting – as even checklists that are accurate at a population-level may perform poorly on a minority population [57, 70].
In this paper, we introduce a machine learning method to learn checklists from data. Our method is designed to streamline the creation of predictive checklists in a way that overcomes specific challenges of model development in modern healthcare applications. Our method solves an integer programming problem to return the most accurate checklist that obeys user-specified constraints on model form and/or model performance. This approach is computationally challenging, but provides specific functionality that simplifies and streamlines model development. First, it learns the most accurate checklist by optimizing exact measures of model performance (i.e., accuracy rather than a convex surrogate measure). Second, it seeks to improve the performance of checklists by adaptively binarizing features at training time. Third, it allows practitioners to train checklists that obey custom requirements on model form or on prediction, by allowing them to encode these requirements as constraints in the optimization problem. Finally, it provides practitioners with an optimality gap, which informs them when a sufficiently accurate checklist does not exist.
The main contributions of this paper are:
1. We present a machine learning method to learn checklists from data. Our method allows practitioners to customize models to obey a wide range of real-world constraints. In addition, it pairs checklists with an optimality gap that can inform practitioners in model development.
2. We develop specialized techniques that improve the ability of our approach to train a checklist that performs well, and to pair this model with a small optimally gap. One of these techniques can be used to train checklists heuristically.
3. We conduct a broad empirical study of predictive checklists on clinical classification datasets [24, 32, 37, 51, 58]. Our results show that predictive checklists can perform as well as state-of-the-art classifiers on some datasets, and that our method can provide practitioners with an optimality gap to flag when this is not the case. We highlight the ability of our method to handle real-world requirements through applications where we enforce group fairness constraints on a mortality prediction task, and where we build a short-form checklist to screen for PTSD.
4. We provide a Python package to train and customize predictive checklists with open-source and commercial solvers, including CBC [29] and CPLEX [20] (see https://github.com/ MLforHealth/predictive_checklists).

heading: 2 Related Work
text: The use of checklist-style classifiers – e.g., classifiers that assign coefficients of ±1 to Boolean conditions – dates to the work of Burgess [9]. The practice is often referred to as “unit weighting," and is motivated by observations that it often performs surprisingly well [see e.g., 7, 19, 23, 27].
Our work is strongly related to methods that learn sparse linear classifiers with small integer coefficients [see e.g., 4, 11, 31, 38, 68, 69, 75]. We learn checklists from data by solving an integer program. Our problem can be viewed as a special case of an IP proposed by Ustun and Rudin [68], Zeng et al. [77] to learn sparse linear classifiers with small integer coefficients. The problem that we consider is considerably easier to solve from a computational standpoint because it restricts coefficients to binary values and does not include `0-regularization. Here, we make use of this “slack" in computation to add functionality that improves the performance of checklists, namely: (1) constraints to binarize continuous and categorical features into items that can be included in a checklist [see also 10, 12, 71]; and (2) develop specialized techniques to reduce computation during the learning process.
Checklists are M -of-N rules — i.e., classifiers that predict y = +1 when M out of N conditions are true. Early work in machine learning used M -of-N rules in an auxiliary capacity – e.g., to explain the predictions of neural networks [67], or to use as features in decision trees [78]. More recent work has focused on learning M -of-N rules for standalone prediction – e.g. Chevaleyre et al. [16] describe a method to learn M -of-N rules by rounding the coefficients of linear SVMs to {−1, 0, 1} using a randomized rounding procedure [see also 79]. Methods to learn disjunctions and conjunctions are also relevant since they correspond to 1-of-N rules and N -of-N rules, respectively. These methods
learn models by solving a special case of the ERM problem in (1) where M = 1 or M = N . Given that this problem is NP-hard, existing methods often reduce computation by using algorithms that return approximate solutions – e.g., simulated annealing [72], set cover [48, 49], or ERM with a convex surrogate loss [21, 22, 46, 47]. These approaches could be used to learn checklists by solving the ERM problem in (1). However, they would not be able to handle the discrete constraints needed for binarization and customization. More generally, they would not be guaranteed to recover the most accurate checklists for a given dataset, nor pair models with a certificate of optimality that can be used to inform model development.

heading: 3 Methodology
text: We start with a dataset of n examples (xi, yi)ni=1 where xi = [xi1, . . . , xid] ∈ {0, 1}d is a vector of d binary variables and yi ∈ {0, 1} is a label. Here, xi are Boolean variables that could be used as items in a checklist. We denote the indices of positive and negative examples as I+ = {i | yi = +1} and I− = {i | yi = −1} respectively, and let n+ = |I+| and n− = |I−|. We denote the set of positive integers up to k as [k] = {1, . . . , k}. We use the dataset to learn a predictive checklist – i.e., a Boolean threshold rule that predicts ŷ = +1 when at least M of N items are checked. We represent a checklist as a linear classifier with the form:
ŷi = sign(λ>xi ≥M). Here λ = [λ1, . . . , λd] ∈ {0, 1}d is a coefficient vector and λj = 1 iff the checklist contains item j. We denote the number of items in a checklist with coefficients λ as N = ∑d j=1 λj , and denote the threshold number of items that must be checked to assign a positive prediction as M . We learn checklists from data by solving an empirical risk minimization problem with the form:
min λ,M l (λ,M) + NN + MM
s.t. N = ‖λ‖ M ∈ [N ]
λ ∈ {0, 1}d
(1)
Here, l (λ,M) = ∑n i=1 1 [yi 6= ŷi] counts the number of mistakes of a checklist with parameters λ and M . The parameters N > 0 and M > 0 are small penalties used to specify lexicographic preferences. We set N < 1nd and M < N d . These choices ensure that optimization will return the most accurate checklist, breaking ties between checklists that are equally accurate to favor smaller N , and breaking ties between checklists that are equally accurate and sparse to favor smaller M . Smaller values of N and M are preferable, as checklists with smaller N users check fewer items, and checklists with smaller M let users stop checking as soon as M items are checked (see Figure 3).
We recover a globally optimal solution to (1) by solving the integer program (IP): min λ,z,M l+ +W−l− + NN + MM
s.t. Bizi≥M − d∑
j=1
λjxi,j i ∈ I+ (2a)
Bizi≥ d∑
j=1
λjxi,j −M + 1 i ∈ I− (2b)
l+ = ∑ i∈I+ zi
l−= ∑ i∈I− zi
N = d∑
j=1
λj
M ∈ [N ] zi ∈ {0, 1} i ∈ [n] λj ∈ {0, 1} j ∈ [d]
Here, l+ and l− are variables that count the number of mistakes on positive and negative examples. The values of l+ and l− are computed using the mistake indicators zi = 1 [ŷi 6= yi], which are set to
1 through “Big-M" Constraints in (2a) and (2a).These constraints depend on the “Big-M" parameters Bi, which can be set to its tightest possible value maxλM − λ>xi. W− is a user-defined parameter that reflects the relative cost of misclassifying a negative example. By default, we set W− = 1, so that the objective minimizes training error.
Customization The IP in (2) can be customized to fit checklists that obey a wide range of realworld requirements on performance and model form. We list examples of constraints in Table 1. Our method provides two ways of handling classification problems with different costs of False Negatives (FNs) and False Positives (FPs). First, the user can specify the relative misclassification costs for FPs and FNs in the objective function by setting W−. Here, optimizing (2) corresponds directly to minimizing the weighted error. Second, the user can instead specify limits on FPR and FNR - e.g. minimize the training FPR (by setting W− = n−) subject to training FNR ≤ 20%.
Adaptive Binarization Practitioners often work with datasets that contain real-valued and categorical features. In such settings, rule-learning methods often require practitioners to binarize such features before training. Our approach allows practitioners to binarize features into items during training. This allows all items to be binarized in a way that maximizes accuracy. This approach requires practitioners to first define Tj candidate items for each non-binary feature ui,j . For example, given a real-valued feature ui,j ∈ R, the set of candidate items could take the form {xi,j,1, xi,j,2, . . . , xi,j,Tj} where xi,j,t = 1 [ui,j ≥ vj,t] and vj,t is a threshold. We would add the following constraint to IP (2) to ensure that the checklist only uses one of the Tj items: ∑ t∈[Tj ] λtj ≤ 1. In this way, the IP would then choose a binary item that is aligned with the goal of maximizing accuracy. In practice, the set of candidate items can be produced automatically [e.g., using binning or information gain 53] or specified on the basis of clinical standards (as real-valued features like blood pressure and BMI have established thresholds). This approach is general enough to allow practitioners to optimize over all possible thresholds, though this may lead to overfitting. Our experiments in Section 5.2 show that adaptive binarization produces a meaningful improvement in performance for our model class.
Optimality Gap We solve IP (2) with a MIP solver, which finds a globally optimal solution through exhaustive search algorithms like branch-and-bound [73]. Given an instance of IP (2) and a time limit for when to stop the search, a solver returns: (i) the best feasible checklist found within the time limit – i.e., values of λ and M that achieve the best objective value V max = l (λ,M); and (ii) a lower bound on the objective value – i.e., V min, the minimal objective value for any feasible solution. These quantities are used to compute the optimality gap ε := 1− V min
V max . When the upper bound V max
matches the lower bound V min, the solver returns a checklist with an optimality gap of ε = 0 – i.e., one that is certifiably optimal.
In our setting, the optimality gap reflects the worst-case difference in training error between the checklist that a solver returns and the most accurate checklist that we could hope to obtain by solving IP (2). Given a solution to IP (2) with an objective value of L and an optimality gap of ε, any feasible checklist has a training error of at least d(1− ε)Le. When ε is small, the most accurate checklist has a training error ≈ L. Thus, if we are not satisfied with the performance of our model, we know that no checklist can perform better than L, and can make an informed decision to relax constraints, fit a classifier from a more complex hypothesis class, or not fit a classifier at all. When ε is large, our problem may admit a checklist with training error far smaller than L. If we are not satisfied with the
performance of the checklist, we cannot determine whether this is because the dataset does not admit a sufficiently accurate model or because the solver has not been able to find it.

heading: 4 Algorithmic Improvements
text: In this section, we present specialized techniques to speed up the time required to find a feasible solution, and/or to produce a solution with a smaller optimality gap.

heading: 4.1 Submodular Heuristic
text: Our first technique is a submodular optimization technique that we use to generate initial feasible solutions for IP (2). We consider a knapsack cover problem. This problem can be solved to produce a checklist ofNmax or fewer items that: (1) maximizes coverage of positive examples; (2) has a “budget” of negative examples B; and (3) uses at most one item from each of the feature groups R1, ..., RT where each Rt denote a set of items derived from a particular real-valued feature and ∪Tt=1Rt = [d].
max A
f+M (A) (3a)
s.t. |A| ≤Nmax (3b) |A ∩Rt| ≤ 1 t ∈ [T ] (3c)∑ j∈A c(j)≤B (3d)
Here, f+M := ∑ i∈I+ min( ∑ j∈A xi,j ,M) counts the positive examples that are covered by at least M items in A. Constraint (3b) limits the number of items in the checklist. Constraint (3c) requires the checklist to use at most one item from each feature group R1, . . . , RT . Constraint (3d) controls the number of negative examples that are covered by at least M items in A. This is a knapsack constraint that assigns a cost to each item as c(j) = ∑ i∈I− xi,j and limits the overall cost of A using the budget parameter B > 0.
The optimization problem in (3) can be solved using a submodular minimization algorithm given that f+M is monotone submodular (see Appendix A.1 for a proof), and that constraints (3b) to (3d) are special kinds of matroid constraints. We solve (3) with a submodular minimization algorithm adapted from Badanidiyuru and Vondrák [2] (Appendix A.2). The procedure takes as input M , Nmax and B and outputs a set of checklists that use up to Nmax items. This procedure can run within 1 second. Given a problem where we would want to train a checklist that has at most Nmax items, we would solve this problem |B|Nmax times, varying M ∈ [Nmax] and B ∈ B.
In Figure 1a, we show the effect of initializing the IP with checklists produced using the submodular heuristic. As shown, these solutions allow us to initialize the search with a good upper bound, allowing us to ultimately recover a certifiably optimal solution faster. Our empirical results in Section
5.2 show that checklists from our submodular heuristic outperform checklists fit using existing baselines. This highlights the value of this approach as a heuristic to fit checklists (in that it can produce checklists that perform well), and as a technique for initialization (in that it can produce checklists that can be used to initialize IP (2) with a small upper bound).

heading: 4.2 Path Algorithms
text: Our second technique is a path algorithm for sequential training. Given an instance of the checklist IP (2), this algorithm sequentially solves smaller instances of IP (2). The algorithm exploits the fact that small instances can be solved to optimality quickly and thus “ruled out" of the feasible region of subsequent instances. The resulting approach can reduce the size of the branch-and-bound tree and improve the ability to recover a checklist with a small optimality gap. These algorithms can wrap around any procedure to solve IP (2).
In Algorithm 1, we present a path algorithm to train checklists over the full range of model sizes from 1 to Nmax. The algorithm recovers a solution to a problem with a hard model size limit by solving smaller instances with progressively larger limits of Nmax and Mmax. We store the best feasible solution from each iteration in a pool, which is then used to initialize future iterations. If the best feasible solution is certifiably optimal, we add a constraint to constrict the search space for subsequent instances. This allows us to reduce the size of the branch-and-bound tree, resulting in a faster solution in each iteration.

heading: 5 Experimental Results
text: In this section, we benchmark the performance of our methods on seven clinical prediction tasks.

heading: 5.1 Setup
text: Data. We consider seven clinical classification tasks shown in Table 2. For each task, we create a classification dataset by using each of the following techniques to binarize features:
Fixed: We convert continuous and ordinal features into threshold indicator variables using the median, and convert categorical feature into an indicator for the most common category. Adaptive: We convert continuous and ordinal features into 4 threshold indicator variables using quintiles as thresholds, and convert each categorical feature with a one-hot encoding. Optbinning: We use the method proposed by Navas-Palencia [53] to binarize all features.
We process each dataset to oversample the minority class to equalize the number of positive and negative examples due to class imbalance.
Methods. We compare the performance of the following methods for creating checklists:
MIP: We fit a predictive checklist by solving an instance of IP (2) with the appropriate constraints. We solve this problem using CPLEX 12.10 [20] paired with the computational improvements in Section 4 on a 2.4 GHz CPU with 16 GB RAM for ≤ 60 minutes. Cover: We fit a predictive checklist using the submodular heuristic in Section 4.1. We set Nmax = 8, and vary M ∈ [Nmax] and B ∈ {kn+|k ∈ { 13 , 1 2 , 1, 2, 3}}.
Unit: We fit a predictive checklist using unit weighting [7]. We fit L1-regularized logistic regression models for L1 penalties ∈ [10−5, 10]. We convert each model into an array of checklists by including items with positive coefficients and the complements of items with negative coefficients. We convert each logistic regression model into multiple checklists by setting M ∈ [N ].
Evaluation. We use 5-fold cross validation and report the mean, minimum, and maximum test error across the five folds. We use the training set of each fold to fit a predictive checklist that contains at most N ≤ 8 items, and that is required to select at most 1 item from a feature group. We report the training error of a final model trained on all available data.
We report results for MIP checklists where M = 1, which we refer to as MIP_OR since it corresponds to an OR rule. Finally, we report performance for L1-regularized logistic regression (LR) and XGBoost (XGB) as baselines to evaluate performance. We train these methods using all features in an adaptive-binarized dataset to produce informal “lower bounds” on the error rate.
For each method and each dataset, we report the performance of models that achieve the lowest training error with N ≤ 8 items. We compare the performance of Fixed and Adaptive binarization here, and report performance of Optbinning in Appendix D.2.

heading: 5.2 Results
text: In Table 3, we report performance for each method on each dataset when using Fixed binarization and Adaptive binarization. We report the corresponding results for Optbinning in Appendix D.2 due to space limitations. In Figure 2, we show the performance effects of varying N . Lastly, we show predictive checklists trained using our method in Figure 3 and Appendix D.3. In what follows, we discuss these results.
On Performance Our results in Table 3 show that our method MIP outperforms existing techniques to fit checklists (Unit) on 7/7 datasets in terms of training error, and on 5/7 datasets in terms of 5-fold CV test error. As shown in Figure 2, this improvement typically holds across all values of N .
In general, we find that relaxing the value of M yield performance gains across all datasets (see e.g., results for ptsd where the difference in test error between MIP_OR and MIP is 7.8%), though smaller values of M can produce checklists that are easier to use (see checklists in Appendix D.3).
The results in Table 3 also highlight the potential of adaptive binarization to improve performance by binarizing during training time, as MIP with adaptive binarization achieves a better training error than fixed binarization for 6/7 datasets and a better test error on 5/7 datasets.
The performance loss of checklists relative to more complex model classes (LR and XGB) varies greatly between datasets. Checklists trained on heart and readmit perform nearly as well as more complex classifiers. On mortality and kidney, however, the loss may exceed 5%.
On Generalization Our results show that checklist performance on the training set tends to generalize well to the test set. This holds for checklists trained using all methods (i.e., Unit, Cover, MIP_OR, and MIP), which is expected given that checklists belong to a simple model class. Generalization can help us customize checklists in an informed way as we can assume that any changes to the training loss (e.g. with the addition of a constraint) lead to similar changes in the test set. In this regime, practitioners can evaluate the impact of model requirements on predictive performance – since they can measure differences in training error between checklists that obey different requirements, and expect these differences in training error as a reliable proxy for differences in test error.
On the Value of an Optimality Gap One of the benefits of our approach is that it pairs each checklist with an optimality gap, which can inform model development by identifying settings where we cannot train a checklist that is sufficiently accurate (see Section 3). On heart, we train a checklist with a training error of 13.6% and an optimality gap of 54.5%, which suggests that there may exist a checklist with a training error of 6.2%. This optimality gap is not available for checklists trained with a heuristic (like unit weighting or domain expertise), so we would not be able to attribute poor model performance to a difficult problem, or to the heuristic being ineffective.
On Fairness We analyze the fairness of MIP checklists trained on the kidney dataset. The task is to predict in-hospital mortality for ICU patients with kidney failure after receiving Continuous Renal Replacement Therapy (CRRT). In this setting, a false negative is often worse than a false positive, so we train checklists that minimize training FPR under a constraint to limit training FNR to 20%, using an 80%/20% train/test split.
We find that our checklist exhibit performance disparities across sex and race, which is consistent with the tendency of simpler models to exhibit performance disparities [40]. To address this issue, we train a new checklist by solving a version of IP (2) with constraints that limit disparities in training FPR and FNR over 6 intersectional groups g ∈ G = {Male, Female} × {White, Black, Other}. Specifically, 30 constraints that limit the FPR disparity across groups to 15%, and 6 constraints to cap the max FNR for each intersectional group to 20%. This is unique compared to prior methods in fair classification work [76] because it enforces group fairness using exact measures[i.e., without convex relaxations 45] and over intersectional groups .
We find that we can limit performance disparities across all values of N (see Figures 4 and 5, and Appendix D.4), observing that MIP with group fairness constraints has larger FPR overall but exhibits lower FPR disparities over groups (e.g., reducing the test set FPR gap between Black Females and White Males from 54.5% to 30.6%).

heading: 6 Learning a Short-Form Checklist for PTSD Screening
text: In this section, we demonstrate the practical benefits of our approach by learning a short-form checklist for Post-Traumatic Stress Disorder (PTSD) diagnosis.
Background The PTSD Checklist for DSM-5 (PCL-5) is a self-report screening tool for PTSD [5, 74]. The PCL-5 consists of 20 questions that assess the severity of symptoms of PTSD DSM-5. Patients respond to each question with answers of Not at all, A little bit, Moderately, Quite a bit, or Extremely. Given these responses, the PCL assigns a provisional diagnosis of PTSD by counting the number of responses of Moderately or more frequent across four clusters of questions. Patients with a provisional diagnosis are then assessed for PTSD by a specialist. The PCL-5 can take over 10 minutes to complete, which limits its use in studies that include the PCL-5 in a battery of tests (i.e., using the provisional diagnosis to evaluate the prevalence of PTSD and its effect as a potential confounder), and has led to the development of short-form models [see e.g., 6, 43, 80].
Problem Formulation Our goal is to create a short-form version of the PCL-5 – i.e., a checklist that assigns the same provisional diagnoses as PCL-5 using only a subset of the 20 questions. We train our model using data from the AURORA study [51], which contains PCL-5 responses of U.S. patients who have visited the emergency department following a traumatic event. Here, yi = +1 if the patient is assigned a provisional PTSD diagnosis. We encode the response for each question into four binary variables xi,k,l = 1 [qk ≥ l] where qk is the response to each question and l ∈ [4] is denotes its response. Our final dataset contains d = 80 binary variables for n = 873 patients, which we split into an 80% training set and 20% test set.
Since this checklist would be used to screen patients, a false negative diagnosis is less desirable than a false positive diagnosis. We train a checklist that minimizes FPR and that obeys the following operational constraints: (1) limit FNR to 5%; (2) pick one threshold for each PCL-5 question; (3) use at most 8 questions. We make use of the same methods and techniques as in Section 5.2.
Results Our results show that short-form checklists fit using our method outperform other checklists (see Figure 6). In Figure 7, we display a sample N = 8,M = 4 checklist trained with our method which reproduces the PCL-5 diagnosis with high accuracy, offering an alternative to the PCL-5 with simpler binary items and less than half the number of questions.

heading: 7 Concluding Remarks
text: In this work, we presented a machine learning method to learn predictive checklists from data by solving an integer program. Our method illustrates a promising approach to build models that obey constraints on qualities like safety [1] and fairness [3, 14]. Using our approach, practitioners can potentially co-design checklists alongside clinicians – by encoding their exact requirements into the optimization problem and evaluating their effects on predictive performance [17, 36].
We caution against the use of items in a checklist as causal factors of outcomes (i.e., questions in the short-form PCL are not “drivers” of PTSD), and against the use of our method solely due to its interpretability. Recent work has argued against the use of models simply because they are “interpretable" [25] and highlights the importance of validating claims on interpretability through user studies [42, 59].
We emphasize that effective deployment of the checklist models we create does not end at adoption. The proper integration of our models in a clinical setting will require careful negotiation at the personal and institutional level, and should be considered in the context of care delivery [28, 62, 63] and clinical workflows [26, 55].
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the National Science Foundation under Grant No. 2040880. We acknowledge a Wellcome Trust Data for Science and Health (222914/Z/21/Z) and NSERC (PDF-516984) grant. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. Dr. Marzyeh Ghassemi is funded in part by Microsoft Research, and a Canadian CIFAR AI Chair held at the Vector Institute. We would like to thank Taylor Killian, Bret Nestor, Aparna Balagopalan, and four anonymous reviewers for their valuable feedback.

Review summaries:
Method to train classifiers based on integer programing optimization of binarized variables. Evaluate and multiple public healthcare related datasets, comparing accuracy vs. other baseline methods. Offers some optimality gap guarantees of models chosen within time constraints (vs. exhaustive search). 

This work presents an extensive evaluation of checklist models (linear models with binary features and coefficients) for clinical predictions.  Such models are quite transparent relative to more complex families, and can be potentially be extremely simple to implement in clinic.  The learning problem is framed as mixed integer programming, which has other virtues - solvers can provide bounds on how far our current solution is to the optimal solution wrt training set performance, and the inclusion of desirable properties as constraints.  This work also provides an evaluation of binarization methods for continuous variables (recall that features must be binary), and proposes a pair of methods for improving performance of the learned models.  Extensive evaluations are performed on 8 datasets; the checklist models very often achieve quite good performance on par with more complex model families.  

This paper proposed a formulation and learning algorithms for learning diagnostic checkslists.  A checklist is a set of binary items where the prediction is positive if the number of checked items exceeds a threshold.    The paper proposes two techniques to solve the resultant integer program optimization problem.  The first is a submodular heuristic The second is a sequential algorithm that reduces the size of the branch and bound tree by eliminating checklists that would be subsets of checklists that do not perform well.   The submission includes evaluation on multiple datasets and under different binarization schemes. For one dataset, there is an evaluation of group-wise bias in the predictions based on the learned lists. There is also a more detailed case study for PTSD that demonstrates how to translate a realistic goal into the setup needed for the learning problem.