Learning Optimal Predictive Checklists
Authors: Haoran Zhang
Quaid Morris
Berk Ustun
Marzyeh Ghassemi
Venue: NeurIPS 2021 Poster (2021)
Keywords: healthcare
interpretability
fairness
integer programming
discrete optimization
classification

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 real-valued 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.

Learning Optimal Predictive Checklists
Haoran Zhang Massachusetts Institute Technology iooranz@mit.edi
Quaid Morris
Memorial Sloan Kettering Cancer Center morrisgemskcc.
Berk Ustun" UC San Diego
Maryzeh Ghassemi" Massachusetts Institute of Technology nggassem@mite eeweeemmmmiieeee......em
berk@ucsd.
Abstract
Checklists are simple decision aids that often used to promote safety and reliability in clinical applications. In this paper, we present a method to lear checklists for clinical decision support. We represent predictive checklists 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 faimess and binarize real- valued features at training time. In addition, it pairs models with an optimality gap that 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 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 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 rich class of custom constraints.
1 Introduction
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 set of Boolean conditions that predicts condition of interest - e.g., list of symptoms flag a patient for 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 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., printed sheet [52]).
Considering these benefits, one of the key challenges in using predictive checklists in healthcare applications is finding reliable way 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 heuristies [e.g., logistic regression, stepwise feature selection, and rounding 39]. These approaches
Equal supervision.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

make it difficult to develop checklists that are sufficiently accurate panel or pipeline will effectively need to specify 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 sufficiently accurate to deploy in clinical setting - as even checklists that are accurate at a population-level may perform poorly on minority population [57, 70].
In this paper, we introduce machine learning method learn checklists from data. Our method is designed to streamline the creation of predictive checklists in 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 constraints in the optimization problem. Finally, it provides practitioners with an optimality gap, which informs them when sufficiently accurate checklist does not exist.
prediction, by allowing them to encode these requirements as
The main contributions of this paper are:
1. We present machine learning method to learn checklists from data. Our method allows practi- tioners to customize models to obey a wide range of real-world constraints. In addition, pairs checklists with an optimality gap that can inform practitioners in model development.
We develop specialized techniques that improve the ability of our approach to train a checklist that performs well, and to pair this model with 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 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 enforce group fairness constraints prediction task, and where we build a short-form checklist to screen for PTSD.
mortality
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: http:////ggtttttoo//// com/ Mitorffea.ttt/preeiieec. ottrr//cepeeeeecc.eeeeeeeee..a..
2 Related Work
The use of checklist-stlle classifiers c.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 coeffi- cients [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 restricts coefficients to binary values and does not include f--reuularivation 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 -f 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 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 0, 1} using 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 Nfof-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 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 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 given dataset, nor pair models with certificate of optimality that can be used to inform model development.
3 Methodology
We start with a dataset of n examples (æ;, 1i)2_1 where = [ra......................... E {0, 1]4 is vector of binary variables and y E 1) is label. Here, a; 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 y/ = } respectively, and let n = ||+ and n = |/ We denote the set of positive integers up to k as [k] kk..
We the dataset to learn predictive checklist i.e., a Boolean threshold rule that predicts +1 when at least M of N itemss are checked. We represent checklist as a linear classifier with the form:
y: x x; 2 M).
Here À - Xa] E {0, 13dd coefficient vector and >, iff the checklist contains item j. We denote the number of items in a checklist with coefficients À as N = Σラ= Xy, and denote the threshold number of items that must be checked to assign positive prediction as M. We learn checklists from data by solving an empirical risk minimization problem with the form:
min X.M
(A, M) + N + M
s.t.
N |X||
(I)
M E [N]
AE {0, 11at
Here, ((, Σm 1l [y: * 0z] counts the number of mistakes of a checklist with parameters À and M. The parameters eN > and EM >> are small penalties used to specify lexicographic preferences. We set en < 2 and em < . 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 globally optimal solution to (1) by solving the integer program (IP):
min A.E.
1t + I + N + C
d
S.L. Bi 2
ie
(2a)
Bi >
Ayzi.j - M +1
iE
(2b)
iE!
[=
iEI
X
M E [N]
2, E (0.1) A, E 10
e [n] E [d]
Here, 1+ and I- are variables that count the number of mistakes on positive and negative examples.
The values of [ and I are computed using the mistake indicators 2, 1l [0 * vi). which are set to
3

---

1 through "Big-M" Constraints in (2a) and Tha). constraints depend on the "Big-M" parameters B, which can be set its tightest possible value max, M > x; 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 real- world requirements on performance and model form. We list examples of constraints in Table 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 S 20%.
MODEL REQUIREMENT
EXAMPLE
CONSTRAINT
Model Size
Use S Niss items
N Na..
Procedural
IF cheoklist includes item about coughing, then include item about fever
Afocer 2 Anuugh
Prodiction
Protict = for all paticnts with both fever and coughing
Ayever Annugh Fronup 2 VVE
Class Based Accuracy
Max FPR y
1" F& [y:0"]
Group
FPR disparity 1y% between males
12
54
Minimax Faimess
No group with FNR worse than
1 [6 C
Table I: Model requirements that can be addressed by our method. Each requirement can be directly encoded into IP (2). The IP can then be solved using the same MIP solver to obtain the most accurate checklist that obeys these constraints.
Adaptive Binarization Practitioners often work with datasets that contain real-valued and cate- gorical features. In such settings, rule-learing methods often require practitioners to binarize such features before training. Our approach allows practitioners to binarize features into items during train- ing. This allows all items to be binarized in a way that maximizes accuracy. This approach requires practitioners to first define T₃ candidate items for each non-binary feature Ui.-. For example, given real-valued feature u E IR. the set of candidate items could take the form {at,5, Pi,,,,, ................................ F., where ii j 2 Ug.e] and Vj is a threshold. We would add the following constraint to IP (2) to ensure that the checklist only uses one of the Tj items: EvE(T,] Ar, S 1. In this way, the IP would then choose 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 / = (A, M); and (ii) a lower bound on the objective value i... yminn the minimal objective value for any feasible solution.
These quantities are used compute the optimality gap e == ymm When the upper bound /max matches the lower bound ymin, the solver returns a checklist with an optimality gap of = = 0 i.... 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 e, any feasible checklist has a training error of at least [[1 []] When E is small, the most accurate checklist has a training error As 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 find
4 Algorithmic Improvements
In this section, we present specialized techniques to speed up the time required to find feasible solution, and/or to produce a solution with a smaller optimality gap.
4.1 Submodular Heuristic
Our first technique is submodular optimization technique that we use to generate initial feasible solutions for IP (2). We consider knapsack cover problem. This problem can be solved to produce a
checklist of Nmx 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 R..... RT where each R2 denote a set of items derived from particular real-valued feature and U R. [d]
max A
(A)
(3a)
s.t.
|A| S Nmar
(3b)
A n
Re S
te [
(3c)
Σ c(i) S
(3d)
Here, ftte = Eier+ min(E Fi.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...., Rr. Constraint (3d) controls the number of negative examples that are covered by least M items in A. This is knapsack constraint that assigns a cost to each item as c(j) Eier- Li,j and limits the overall cost of A using the budget parameter B >
The optimization problem in (3) can be solved using a submodular minimization algorithm given that fit is monotone submodular (see Appendix A.1 for proof), and that constraints (3b) to (3d) 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, N Neer and B and outputs a set of checklists that use up to N Nmar items. This procedure can run within second. Given a problem where we would want to train checklist that has most N items, we would solve this problem [B] Nuax times, varying M E [amaz] and B E B.
Algorithm 1: Sequential Training over N and M
100%
Input: maximum # of items Nouz
No Intiialization
Input: objective value function (-))
80%
Knepsack Cover
pool
Optimalty Gap
for E [Nmarl j E [t] do
80%
S + {CIC E (V() (( S
Cinst <- argminges S(C)
Cnew +- solve IP (2) with initial solution Cinie
20%
subject N < and M <
Add (Crew to pool
20K
40K
60K
8CK
100K
end return pool
Nodes Processed
(b)
Figure 1: (a) Performance profile when solving IP (2) with and without initialization. We show the optimality gap vs. the of branch-and- and-boundd nodes when solving (2) for the heart dataset where N and M < 2. (b) algorithm for sequential training over N and M.
In Figure Ia, 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 good upper bound, allowing to ultimately recover certifiably optimal solution faster. Our empirical results in Section
5

---

5.2 show that checklists from our submodular heuristic outperform checklists fit using existing baselines. This highlights the value of this approach as heuristic to fit checklists (in that it can produce checklists that perform well), and as technique for initialization (in that it can produce checklists that can be used to initialize IP (2) with small upper bound).
4.2 Path Algorithms
Our second technique 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" 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 solve IP (2).
In Algorithm 1, we present a path algorithm to train checklists over the full range of model sizes from 1 to N The algorithm recovers solution to problem with a hard model size limit by solving smaller instances with progressively larger limits of Nmax and M 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 certifiably optimal, we add constraint to constrict the search space for subsequent instances. This allows to reduce the size of the branch-and- tree, resulting in faster solution in each iteration.
5
Experimental Results
In this section, we benchmark the performance of our methods on seven clinical prediction tasks.
5.1
Setup
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 indicator for the most common category.
Adaptive: We convert continuous and ordinal features into threshold indicator variables using quintiles 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 class imbalance.
Methods. We compare the performance of the following methods for creating checklists:
MIP: We fit 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 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 and vary M E [Nmaa] and B E {kn lk ( 1,,,
Dataset
dr
dyet
11
Prediction Task
Reference
edlid
20
594
Patient dingnosed with ADHD
[5]]
cardio
40
52
8,815
Patient with cardiogenic shock died in hospital
[58]
kidney
17
80
1.722
Patient with kidney failure died after renal replacement therapy
[37]
mortality
50
484
21,139
Patient died hospital
[37]
ptsd
20
80
873
Patient has PCL-S PTSD diagnosis
[51]
readmiL
42
94
9,766
Patient re-admitted hospital within days
[32]
heart
13
82
303
Patient has heart disense
[24]
Table 2: Clinical prediction tasks used Section 5. Here, n is the number of samples prior to oversampling, dr is the number of feature groups, and dpez. is the number of features after binarization using the adaptive method.

---

Frami RINARIZATION
ARAPTIVE RINARIZATION
Lowne BOUNDS
Daraset
Metric
UNIr
Coven
MIP OR
MIP
UNIT
CoveR
MIP OR
MIP
LR
XGB
ertor
mmn, max)
(11.9. 19.00
(13.5 20.50
19.0
(3,5,200)
(.4)
(2.4. (1.7)
(4.0
(0.0.0)
10.8
2.4)
"ye
miin emer
DP
11.4
114
0.0
1.1
54
23,8
25.3
29.6
24.1
25.0
25.5
29.2
22.6
21.6
26.3
"pet 51
- 15251
tiin (18)
(80)
(21.1. 26.5)
25.0
(21.4 27.2)
16.3
(284431.0
19.6
19.5
(22.5, 25.0
828
24.1
(21 24.2
25.0
(2A 7,2688
25.5
(2777 3009
29.2
$1.9
(21
81.2
22.5
(20.2 23.5)
20,6
(2500 27.0
6,4
dpe 50
kidmay
s - 1760
5P (83
1es emor (86)
(min, mor)
miin cmner (8)
(33.2
53.2
32.4
53.2)
(31 3 18 9)
15.6
33.6
(34.7 40.5)
32.3
45.7
16.7
(11
15.3
11.0
78.9
16 5)
(16 1, 19.89
37.
$4.1
(16 4, 18.6
37.
36.5
(33 2. 36.9)
43.3
54.7
$4.0
(51 2 57.5)
20.4
82.4
$3.8
(28 7, 33.5)
22.3
30,9
(2..3 28.77
25.3
0.2
nortality
20684
ted enor
min en
(min, mor)
(33.1
32.0
16.1)
(37.4 10 7)
066.6 18.4)
17.4
17.3
(2788 90.2)
29.1
(92. 9, 95.5)
35.4
(35 17.0)
36.5
36.5
(37.0 99.4)
37.8
(26., 20.5)
29.6
29,3
22.6
26.4)
(22.2 20.1)
18.0
4.6
pp (83)
0.0
$1.0
80.4
10.9
198
10.
162
4.6
dpet
1106
8.3
14.9)
13.4
0,0
(6.5.
12.5
(5.9
16..5
56
0.0
64)
dpt 50
i 16732
readrit
trin emor (36)
enor (uis, mus)
(4)
(53.8, 57.2)
35,3
35.2
(35.3 40.00
53.3
32.5
(3644 39.3)
16.5
49.3
37.9
(33.8
810
152
36.2
(32 35.5)
34.4
34.2
(32 (6.6)
34.6
34,5
(34.8 35.5)
49.9
33.2
35.2
(52.6 35.7)
33,9
331
73.4
(32.2
32,0
33.0
33.8)
(347.80 38.1)
36
139
I e 131
beart
dyet
-2
5e (8k)
min emorr (9)
(uni,, max)
Ice enor (%)
(13.6,
15.2
16.3
24.20
(12.5, 25.5)
18.5
16.4
(21.2
13.6
29.1
0.0
39.4)
(28.) 28.3)
28.8
31.8)
16.1
(15
23.9
182
33.3)
(21.2
29.1
23.6
08
39.4)
(13.6 19.7)
13.6
54.5
16.7
(10.6
17.6
27,5)
(2..1 25.8)
17.6
87
Table 3: Performance results of all methods on all datasets. For cisck models, we report the training error, test error, and optimality gap for the checklist that minimizes training error and satisfies all constraints. The intervals under test error reflect the 5-CV minimum and maximum test error. We additionally report results for LR and XGB performance baselines that represent informal lower bound on the error of possible checklists.
Unit: We fit a predictive checklist using unit weighting [7]. We fit Li-reuularized logistic regression models for L1 penalties E [10-5, 10j. 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 E [N].
Evaluation. We use 5-lold 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 predictive checklist that contains at most N S 8 items, and that is required to select at most 1 item from a feature group. We report the training error of final model trained on all available data.
We report results for MIP checklists where M = 1, which we refer to as MIP_ON since it corresponds to an OR rule. Finally, we report performance for Li-regularized logistic regression (LR) and XGBoost (XGB) as baselines to evaluate performance. We train these methods using all features in an adaaptiv-binarizze 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 Opthinning in Appendix D.2.
5.2 Results
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 pt sd where the difference 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).
7

---

Trrning
38.0%
Predict 30-day readmission
checked
38.0%
# admissions past year bed days length of stay 2 8 days chronic or uncontrolled pain mood problems past years substance abuse pasi month
Eneer
34.0%
32.0%
30.0%
Maximum # Itoms
Figure 3: Predictive checklist fit for reacimi t using MIP. The checklist has a train error of 33. 1 1%, and a test error of 33.9%. We show sample checklists for all other datasets Appendix D.3.
Figure 2: Performance of checklists with < N items on mortality fit using our approach and unit weighting.
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 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 t 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 the training set tends to gener- alize well to the test set. This holds for checklists trained using all methods (i.c., Unit, Cover, 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 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 measure differences in training error between checklists that obey different requirements, and expect these differences in training error as 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 training error of 13.6% and an optimality gap of 54.5%, which suggests that there may exist a checklist with 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 difficult problem, or to the heuristic being ineffective.
On Fairness We analyze the fairness of MIP checklists trained the ki 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, false negative is often worse than 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 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 disparitics in training FPR and FNR over 6 intersectional groups g E G = {Male, Female) x {Waite, 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 measuresfi.e., without convex relaxations 45] and over intersectional groups
We find that we can limit performance disparities across values of N (see Figures 4 and 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%).
8

---

70.0%
50.0%
00.0%
MTn Toenin Cel
MP. Text Eel
MPPuFae Trakning Bat
40.0%
50.0%
MIP MiP-Faeeess Text Set
60.0%
40.0%
55.0%
00.0%
30.0%
60.0%
20.0%
45.0%
10.0%
Maximum Bema
Maximun Itam
Maximum Boma
Figure FPR (left), maximum FPR disparity (center) and worst-case FNR (right) versus numher of items for checklists for mortality prediction given CRRT using dney. Group fairness constraints effectively limit FPR disparity and worst-case FNR during training, at the cost of overall performance.
Predict Mortality Given CAAT if 3+ Items are Checked
Age 66.0 years
Predict Mortality Given CRRT i 2- Items are Checked
AST 2 162.6 IUAL
ALT 2 16.0 IUN.
Blood 7.29
Bicarbonate
mmoll
MCV 99.0
Blood pH s 7.22
Norepinephrine 2 0.1 magrkgmmn Platelets 5 65.0 x10"/pl.
Norepinephrine 2: 0.1 mogkg/min RDW 19.2%
RDW 19.2%
Time ICU 14.1 hours
FNR
Worst
Gap
FNR
FPR
FPR Gap
Truining Test
20.0%
43.9%
31.3%
24.3%
Training
17.5%
$2.2%
18.1%
13.9%
(a) MIP
(b) MIP + Fairness Constraints
Figure Checklists trained to predict mortality given CRRT (a) without group fairness constraints and (b) with group fairness constraints. Checklist (a) has better overall FPR, but has worse FNR for the worst-cas group, and exhibits disparities in FPR across groups. Checklist (b) obeys group fairness constraints that attenuate the training FPR gap to 15% and the worst-case FNR to 20%.
Learning a Short-Form Checklist for PTSD Screening
In this section, we demonstrate the practical benefits of our approach by learning short-form checklist for Post- coss-Traumati Stress Disorder (PTSD) diagnosis.
Background The PTSD Checklist for DSM-5 (PCL-5) is 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 provisional diagnosis of PTSD by counting the number of responses of Moderately or more frequent across four clusters of questions. Patients with provisional diagnosis are then assessed for PTSD by a specialist. The PCL-5 take 10 minutes to complete, which limits its use in studies that include the PCL-5 (i.e., using the provisional diagnosis to evaluate the prevalence of PTSD and its effect potential confounder), and has led to the development of short-form models [see e.g., 6, 43, 80].
battery of tests
Problem Formulation Our goal is to create short-form version of the PCL-5 i.e., a checklist that assigns the same provisional diagnoses PCI.5 using only 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 traumatic event. Here, y: +1 the patient is assigned provisional PTSD diagnosis. We encode the response for each question into four binary variables Zi,A.I 1 2 !] where 9 the response to each question and / E [4] is denotes its response. Our final dataset contains d = 80 binary variables for n = 873 patients, which split into 80% training set and 20% test set.
Since this checklist would be used to screen patients, false negative diagnosis is less desirable than false positive diagnosis. We train a checklist that minimizes FPR and that obeys the following operational constraints: (1) limit FNR 5%; (2) pick one threshold for each PCL-5 question; (3) use most 8 questions. We make use of the same methods and techniques in Section 5.2.

---

Results Our results show that short-form checklists fit using our method outperform other checklists (see Figure 6). In Figure we display sample N 8, M 1 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.
Predict PTSD it 4+ Items are Checked
40.0%
Unit Triining Set
Avording thinking about experience moderately
Avoiding activities or situations moderately
MIP Training Set MIP Test Set
Blame for stressful experience 2: little bit
30.0%
Feeling distant or cut 2: quite
Irritable angry outbursts moderataly interest activities moderately
20.0%
Repeated disturbing dreams 2 moderately
Trouble experiencing positive feelings 2 moderately(1
10.0%
Figure Short-form of the PCL-5 trained with MIP. of 6.6%/10.885 and a train/test FNR of 4.7% It reproduces the PCL.- 5 diagnosis on the training/test sets with 94.1/90.99, accuracy, and has 70.8% optimality gap. We show condensed PCL-5 questions due space constraint.
Maximum
Items
The checklist has train/test
Figure FPR versus number of items for short-
forms of the PCL-5. MIP outperforms Unit across all values of N.
7 Concluding Remarks
In this work, we presented a machine learning method to lear predictive checklists from data by solving integer program. Our method illustrates 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.6]].
We caution against the use of items in checklist causal factors of outcomes (i.e., questions in the short-form PCL are not "drivers" PTSD), and against the use of our method solely due to its interpretability. Recent work has argued against the of models simply because they "interpretable" [25] and highlights the importance of validating claims on interpretability through user studies [42, 59].
We emphasize that effective deployment the checklist models we create does not end at adoption. The proper integration of our models in clinical setting will require careful negotiation at the personal and institutional level, and should considered in the context of care delivery [28, 62, 63] and clinical workflows [26, 55].
10

---

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/2/21/2) 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 Canadian CIFAR AI Chair held at the Vector Institute. We would like to thank Taylor Killian, Bret Nestor, Apara Balagopalan, and four anonymous reviewers for their valuable feedback.
References
[1] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané, Concrete problems in ai safety. arXiv preprint arXiv: 06565, 2016.
[2] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth anmual ACM-SIAM symposium on Discrete algorithms, pages 1497-1514. SIAM, 2014.
[3] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairml- book.org, 2018. http://wwet fai rmloook org.
[4] Lieven Billiet, Sabine Van Huffel, and Vanya Van Belle. Interval coded scoring: toolbox for interpretable scoring systems. PeerJ Computer Science, 4:e150, 2018.
[5] Christy A Blevins, Frank W Weathers, Margaret T Davis, Tracy K Witte, and Jessica L Domino. The posttraumatic stress disorder checklist for dsm-5 (pcl-5): Development and initial psychometric evaluation. Journal of traumatic stress, 28(6):489 498.4899999, 2015.
[6] Paul D Bliese, Kathleen M Wright, Amy B Adler, Oscar Cabrera, Carl A Castro, and Charles W Hoge. Validating the primary care posttraumatic stress disorder screen and the posttraumatic stress disorder checklist with soldiers returning from combat. Journal of consulting and clinical psychology, 76(2):272 2008.
[7] Philip Bobko, Philip Roth, and Maury A Buster. The usefulness unit weights in creat- ing composite scores: A literature review, application to content validity, and meta-ame analysis. Organizational Research Methods, 10(4):689-709, 2007.
[8] David Brodie and Richard Wells. An evaluation of the utility of three ergonomics checklists for predicting health outcomes in a car manufacturing environment. In Proc. of the 29th Annual Conference of the Human Factors Association of Canada. Citeseer, 1997.
[9] Ernest W Burgess. Factors determining success failure parole. The workings of the indeterminate sentence law and the parole system Illinois, pages 221-234, 1928.
[10] Emilio Carrizosa, Belen Martin BartiinnBBrra,,, and Dolores Romero Morales. Binarized support vector machines. INFORMS Journal on Computing, 22(1):154-11) 2010.
[11) Emilio Carrizosa, Amaya Nogales-Gómer and Dolores Romero Morales. Strongly agree or strongly disagree?: Rating features in support vector machines. Information Sciences, 329: 256-273, 2016.
[12] Emilio Carrizosa, Amaya Nogales-Gómez, and Dolores Romero Morales. Clustering categories support vector machines. Omega, 66:28-37, 2017.
[13] Ken Catchpole and Stephanie Russ. The problem with checklists. BMJ quality & safety, 24(9): 545-549, 2015.
[14] Simon Caton and Christian Haas. Fairness in machine learning: A survey, arXiv preprint vrXiv:2010.0400: 2020.
[15] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
11

---

[16] Yann Chevaleyre, Frederic Koriche, and Saan-Daniel Zucker. Rounding methods for discrete linear classification. In Proceedings of the 30th International Conference on Machine Learning (ICMI-13), pages 651-659, 2013.
[17] Evangelia Christodoulou, Jie Ma, Gary S Collins, Ewout W Steyerberg, Jan Y Verbakel, and Ben Van Calster. A systematic review shows no performance benefit of machine learning over logistic regression for clinical prediction models. Journal of clinical epidemiology, 110:12-22, 2019.
[18] Robyn Clay-Williams and Lacey Colligan. Back to basics: checklists in aviation and healthcare. BMJ quality & safery, 24(7):428 431, 2015.
[19] Jacob Cohen. Things have learned (so far). In Annual Convention of the American Psychologi- cal Association, 98th, Aug, 1990, Boston, MA, US; Presented at the aforementioned conference. American Psychological Association, 1992.
[20] IBM ILOG Cplex. V12. 1: User's manual for cplex. International Business Machines Corpora- tion, 46(53):157, 2009.
[21] Sanjeeb Dash, Dmitry M Malioutov, and Kush R Varshney. Screening for learning classification rules via boolean compressed sensing. Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on, pages 3360-3364. IEEF, 2014.
[22] Sanjeeb Dash, Dmitry M Malioutov, and Kush R Varshney. Learning interpretable classification rules using sequential rowsampling. 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3337-3341. IEEE, 2015.
[23] Robyn M Dawes. The robust beauty of improper linear models in decision making. American psychologist, 34(7):571-582, 1979.
[24] Robert Detrano, Andras Janosi, Walter Steinbrunn, Matthias Pfisterer, Johann-Jakob Schmid, Sarbjit Sandhu, Kern H Guppy, Stella Lee, and Victor Froelicher. International application of new probability algorithm for the diagnosis of coronary artery disease. The American journal of cardiology, 64(5)3304-310, 1989.
[25] Finale Doshi- and Been Kim. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv: I 702.08608, 2017.
[26] B Alex Dummett, Carmen Adams, Elizabeth Scruth, Vincent Liu, Margaret Guo, and Gabriel J Escobar. Incorporating an early detection system into routine clinical practice in two community hospitals. Journal of hospital medicine, 11:S25-S31 2016
[27] Hillel J Einhorn and Robin M Hogarth. Unit weighting schemes for decision making. Organi- zational behavior and human performance, 13(2):171-192, 1975.
[28] Madeleine Clare Elish. The stakes uncertainty: developing and integrating machine learning in clinical care. In Ethnographic Praxis in Industry Conference Proceedings, volume 2018,
pages 364-380. Wiley Online Library, 2018
[29] John Forrest, Ted Ralphs, Stefan Vigerske, Lou Hafer, Bjarni Kristjansson, JP Fasano, Straver, M Lubin, HG Santos, R Lougee, et al. coin-or/cbe: Version 2.9. 9. URL htpp:/dx. doi. org/10.5281/zemodo 1317566, 2018
[30] Brigid M Gillespic and Andrea Marshall. Implementation of safety checklists in surgery: a realist synthesis of evidence. Implementation Science, 10(1):137, 2015.
[31] Sharad Goel, Justin M Rao, Ravi Shroff, et al. Precinct or prejudice? understanding racial disparities in new york city's 's stop-and-friss. policy. Annals of Applied Statistics, 10(1):365-394 2016.
[32] Jeffrey L Greenwald, Patrick R Cronin, Victoria Carballo, Goodarz Danaei, and Garry Choy. A novel model for predicting rehospitalization risk incorporating physical function, cognitive status, and psychosocial support using natural language processing. Medical care, 55(3): 261-266, 2017.
12

---

[33] Brigette Hales, Marius Terblanche, Robert Fowler, and William Sibbald. Development of medical checklists for improved quality of patient care. International Journal for Quality in Health Care, 20(1):22-30, 2008.
[34] Hrayr Harutyunyan. Hrant Khachatrian. David C. Kale, Greg Ver Steeg, and Aram Galstyan. Multitask learning and benchmarking with clinical time series data. Scientific Data, 6(1):96, 2019. ISSN 2052-4463. doi: 10110///411977019-0000 1 1038/ / 1144119977 1597-5977111 01 9- 03---9.
URL https:://///tt org/10.
[35] Alex Haynes, Thomas Weiser, William Berry, Stuart R Lipsitz, Abdel-Hadi S Breizat, E Patchen Dellinger, Teodoro Herbosa, Sudhir Joseph, Pascience I. Kibatala, Marie Carmela M Lapitan, et al. A surgical safety checklist to reduce morbidity and mortality in a global population. New England Journal of Medicine, 360(5):491-499 2009.
[36] Sungsoo Ray Hong. Jessica Hullman, and Enrico Bertini. Human factors in model interpretabil- ity: Industry practices, challenges, and needs. Proceedings of the ACM on Human-Compiln Interaction, 4(CSCW1I)1-266 2020.
[37] Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-Wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. Mimic-iii, a freely accessible critical care database. Scientific data, 3(1):1-9, 2016.
[38] Jongbin Jung. Connor Concannon, Ravi Shroff, Sharad Goel, and Daniel G Goldstein. Simple rules guide expert classifications. Journal of the Royal Statistical Society; Series A (Statistics in Society), 183(3):771-800 2020.
[39] Ronald C Kessler, Lenard Adler, Minnie Ames, Olga Demler, Steve Faraone, EVA Hiripi, Mary J Howes, Robert Jin, Kristina Secnik, Thomas Spencer, et al. The world health organization adult adhd self-report scale (asrs); short screening scale for use in the general population. Psychological medicine, 35(2):245, 2005.
[40] Jon Kleinberg and Sendhil Mullainathan. Simplicity creates inequity: implications for faimess, stereotypes, and interpretability. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 807-808, 2019.
[41] Heidi Kramer and Frank A Drews. Checking the lists: A systematic review of electronic checklist use in health care. Journal of biomedical informatics, 71:S6-S12, 2017.
[42] Isaac Lage, Emily Chen, Jeffrey He, Menaka Narayanan, Been Kim, Samuel Gershman, and Finale Deshi-Velez. Human evaluation of models built for interpretabilityy In Proceedings of the AAAI Conference on Human Computation and Crowdsourcing, volume 7, pages 59-67, 2019.
[43] Ariel J Lang and Murray B Stein. An abbreviated ptsd checklist for use as screening instrument in primary care. Behaviour research and therapy, 43(5):585-59) 2005.
[44] Lorelei Lingard, Glenn Regehr, Beverley Orser, Richard Reznick, G Ross Baker, Diane Doran, Sherry Espin, John Bohnen, and Sarah Whyte. Evaluation of preoperative checklist and team briefing among surgeons, nurses, and anesthesiologists to reduce failures in communication. Archives of surgery, 143(1):12-17, 2008
[45] Michael Lohaus, Michael Perrot, and Ulrike Von Luxburg. Too relaxed to be fair. In Interna- tional Conference on Machine Learning, pages 6360-6369, PMLR, 2020.
[46] Dmitry Malioutov and Kush Varshney. Exact rule learning via boolean compressed sensing. In Proceedings of The 30th International Conference on Machine Learning, pages 765-773, 2013.
[47] Dmitry M Malioutov, Kush R Varshney, Amin Emad, and Sanjeeb Dash. Learning interpretable classification rules with boolean compressed sensing. In Transparent Data Mining for Big and Small Data, pages 95-121 121. Springer, 2017.
[48] Mario Marchand and John Shawe-Taylor. Learning with the set covering machine, In ICMI., pages 345-352, 2001.
13

---

[49] Mario Marchand and John Shawe Taylor. The set covering machine. The Journal of Machine Learning Research, 3:723-746, 2003.
[50] Robert Mauro, Asaf Degani, Loukia Loukopoulos, and Immanuel Barshi. The operational con- text of procedures and checklists in commercial aviation. In Proceedings of the Human Factors and Ergonomics Society Annual Meeting, volume 56, pages 758-762. SAGE Publications Sage CA: Los Angeles, CA, 2012.
[51] Samuel A McLean, Kerry Ressler, Karestan Chase Koenen, Thomas Neylan, Laura Germine, Tanja Jovanovic, Gari D Clifford, Donglin Zeng, Xinming An, Sarah Linnstaedt, et al. The aurora study: a longitudinal. multimodal library of brain biology and function after traumatic stress exposure. Molecular psychiatry, 25(2):283-22) 296. 2020.
[52] Keith E Morse, Steven C Bagley, and Nigam H Shah. Estimate the hidden deployment cost of predictive models to improve patient care. Nature medicine, 26(1):18-1 19, 2020.
[53] Guillermo Navas-Palencia. Optimal binning: mathematical programming formulation. arXiv preprint arXiv:2001. 08025, 2020.
[54] Janki Patel, Kamran Ahmed, Khurshid A Guru, Fahd Khan, Howard Marsh, Mo- hammed Shamim Khan, and Prokar Dasgupta. An overview of the use and implementation of checklists in surgical specialities-a systematic review. International Journal of Surgery, 12(12): 1317-1323, 2014.
[55] Shirley S Paulson, B Alex Dummett, Julia Green, Elizabeth Scruth, Vivian Reyes, and Gabriel J Escobar. What do we do after the pilot is done? implementation hospital early warning system scale. The Joint Commission Journal on Quality and Patient Safery, 46(4))207-216, 2020.
[56] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
[57] Emma Pierson, David M Cutler, Jure Leskovec, Sendhil Mullainathan, and Ziad Obermeyer. An algorithmic approach to reducing unexplained pain disparities in underserved populations. Nature Medicine, 27(1):136-11) 2021.
[58] Tom J Pollard, Alistair EW Johnson. Jesse D Raffa, Leo A Celi, Roger G Mark, and Omar Badawi. The eicu collaborative research database, a freely available multi-center database for critical care research. Scientific data, 5(1):1-13, 2018.
[59] Forough Poursabzi-Sangdee Sangdeh. Daniel G Goldstein, Jake M Hofmmnn Jennifer Wortman Wort- man Vaughan, and Hanna Wallach. Manipulating and measuring model interpretability. In Proceedings of the 2021 CHI Conference Human Factors in Computing Systems, pages 1-52, 2021.
[60] Peter Pronovost, Dale Needham, Sean Berenholtz, David Sinopoli, Haitao Chu, Sara Cosgrove, Bryan Sexton, Robert Hyzy, Robert Welsh, Gary Roth, et al. An intervention decrease catheter-related bloodstream infections in the icu. New England Journal of Medicine, 355(26): 2725 27322, 2006.
[61] Hajo Reijers, Henrik Leopold, and Jan Recker. Towards a science of checklists. In Proceedings of the 50th Hawaii International Conference System Sciences, pages 5773-5782. University of Hawaii, 2017.
[62] Mark P Sendak, Joshua D' Arcy, Sehj Kashyap, Michael Gao, Marshall Nichols, Kristin Corey, William Ratliff, and Suresh Balu. A path for translation of machine learning products into healthcare delivery. EMJ Innov, 10:19-172, 2020.
[63] Pratik Shah, Francis Kendall, Sean Khozin, Ryan Goosen, Jianying Hu, Jason Laramie, Michael Ringel, and Nicholas Schork. Artificial intelligence and machine learning in clinical develop- ment: translational perspective. NPJ digital medicine, 2(1):1-5, 2019.
14

---

[64] Daniel L Stufflebeam. Guidelines for developing evaluation checklists: the checklists develop- ment checklist (edc). Kalamazoo, MI: The Evaluation Center Retrieved on January, 16:2008, 2000.
[65] Øyvind Thomassen, Guttorm Brattebo, Eirik Søfteland, HM Lossius, and J-K Heltne. The effect of a simple checklist on frequent pre-induction deficiencies. Acta anaesthesiologica scandinavica, (1110))1179-111 2010.
[66] Øyvind Thomassen, Ansgar Storesund, Eirik Softeland, and Guttorm Brattebø. The effects of safery checklists in medicine: a systematic review. Acta Anaesthesiologica Scandinavica, 58(1):
5-18, 2014.
[67] Geoffrey G Towell and Jude W Shavlik. Extracting refined rules from knowledge-based neural networks. Machine learning, 13(1):71-101, 1993.
[68] Berk Ustun and Cynthia Rudin. Supersparse Linear Integer Models for Optimized Medical Scoring Systems. Machine Learning, 102(3):349-39) 2016.
[69] Berk Ustun and Cynthia Rudin. Learning optimized risk scores. Journal of Machine Learning Research, 20(150):1-55, 2019.
[70] Darshali A Vyas, Leo Eisenstein, and David Jones. Hidden in plain sight-rreconsidering the use of race correction in clinical algorithms, 2020.
[71] Tong Wang. Multi-value rule sets. arXiv preprint arXiv:1710.05257, 2017.
[72] Tong Wang, Cynthia Rudin, Finale Doshi- Velez, Yimin Liu, Erica Klampfi, and Perry MacNeille. Or's of and's for interpretable classification,, with application to context-aware recommender systems. arXiv preprint
2015.
[73] Laurence A Wolsey. Integer Programming, volume 42. Wiley New York, 1998.
[74] Jennifer H Wortmann, Alexander H Jordan, Frank W Weathers, Patricia A Resick, Katherine A Dondanville, Brittany Hall-Clark, Edna B Foa, Stacey Young-McCaughan Jeffrey S Yarvis, Elizabeth A Hembree, et al. Psychometric analysis of the ptsd checklist-5 (pcl-5) among treatment-seeking military service members. Psychological assessment, 28(1 1):1113:92 2016.
[75] Mike Wu, Michael Hughes, Sonali Parbhoo, Maurizio Zazzi, Volker Roth, and Finale Doshi- Velez. Beyond sparsity: Tree regularization of deep models for interpretability, Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[76] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodrigues! and Krishna P Gummadi. Fairness constraints: A flexible approach for fair classification. Mach. Learn, Res., 20(75):
1-42, 2019.
[77] Jiaming Zeng, Berk Ustun, and Cynthia Rudin. Interpretable classification models for recidivism prediction. Journal of the Royal Statistical Society: Series A (Statistics in Society), 180(3): 689-722, 2017.
[78] Zijian Zheng. Constructing x-of-n attributes for decision tree learning. Machine learning, 40 (1):35-75, 2000.
[79] Jean-Daniel Zucker, Yann Chevaleyre, and Dao Van Sang. Experimental analysis of new algorithms for learning ternary classifiers. In 2015 IEEE RIVF International Conference on Computing & Communication Technologies, pages 19-24. IEFE, 2015.
[80] Kelly L Zuromski, Berk Ustun, Irving Hwang. Terence M Keane, Brian P Marx, Murray B Stein, Robert J Ursano, and Ronald Kessler. Developing an optimal short-form of the ptsd checklist for dsm-5 (pel-5). Depression and anxiety, 36(9):790-88) 800, 2019.
15


Reviews:
[{"review_id": "zVmb2THXdnL", "reviewer": "Reviewer_rvfW", "summary": "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.  \n\nThe paper proposes two techniques to solve the resultant integer program optimization problem.  The first is a submodular heuristic\nThe 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. \n\nThe 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. ", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality\nThis work provides a formulation for a task that has not been adopted in machine learning, but is highly relevant to healthcare. \n\n# Quality\nThis work is thorough and well described in the submission. The experiments support the technique's performance boradly and suggest where future improvements may lie.  The case study on PTSD works very well to illustrate how to take a variety of real-world goals and formulate a checklist search problem. \n\n\n\n# Clarity\nThis paper is overall understandable.  There are minor clarity issues that make some sections require multiple attempts or later context to understand, but they do not interfere with understanding the main conclusions or methods. \n\nThe abstract doesn't stand well on its own.  After reading the paper it reads like a good summary, but before reading, too many parts read as undefined terms. \n\nSection 4.2 is a little hard to parse. Parts of it read as if it's the introduction to a forthcoming more detailed description of the algorithm, but there is no longer description section. \n\nThe fairness evaluation is less strong than the rest of the paper and could be improved some. It's not clear how \"a false negative is worse than a false positive\" (line249) supports minimizing FPR and holding FNR as a constraint and evaluating the FPR gap. This may be a clarity issue, so please explain that connection more clearly, otherwise, your setup seems to suggest that the FNR should be monitored more closely. If false negatives are worse than false positives, it would seem to follow that a gap in the FNR would also be worse- or does setting it as a constraint also make the FNR equal across groups?\n\n\n\n# Significance\nThis work represents a highly interpretable model that presents the predictive task in a similar form to what clinicians already use.  Checklists are widely adopted and trusted in medicine for many reasons and learning the from data presents an opportunity to improve real practice. The performance as is with the current adaptive binarization is comparable to more complex learning algorithms. \n\n\n# Minor Issues \n\n\n- line 22, is it that there are no standardized *automated* approaches or truly no standards in how checklists are developed? expert panels often have strict protocols that they use that do serve as a type of of standardization, though it's less strict than computerized standardization\n- line 47 uses PCL without it being defined yet.\n- line 71: \"reduce computation\" here is not clear, a more specific phrase would help. Because that part is talking about interpretable models, computation could refer to either at the time of learning or prediction. \n- Table 1 is difficult to read small\n- section heading 4.2, should that be plural or singular?\n- line 171: \"The algorithms exploits\" -> \"The algorithm exploits\"\n- line 188: \"... by using one..\" to \"...by using each...\" as  it reads, I was looking for how you chose which one to use until I saw the results\n- the table 3 caption should state that the \"lower bound\" columns are a baseline and the way they're referred to in the table should match the text (line 212)\n- on line 225 it says the checklists performs similarly to more complex classifiers, this could use a citation, \n- line 279, define ED", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the social impact of their work very well, throughout the paper.  The motivation in the introduction makes it clear.  The authors evaluate for bias in one dataset and show how their framework allows for a context-specific mitigation to reduce the most important gaps in performance. The conclusion includes specific cautions for the interpretation and application of their work both with respect to fairness and its role as an interpretable model. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "tmJrxYNqpIl", "reviewer": "Reviewer_hq2w", "summary": "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.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work presents a study of a very restricted class of linear models - binary features and coefficients - for clinical prediction tasks.  Such models are basically checklists - you evaluate some predicates and add up the true values and see if the sum >= some threshold.  Such models have many virtues - the chief ones being that they are potentially very simple to deploy - you can print them out, and clinicians can run them with minimal arithmetic (though evaluating the predicates can still be non-trivial). They are also transparent in the sense of how they arrive at scores (it should be noted that this is not the only important sense of transparent - it does not, as the authors point out, imply causal mechanisms - but lack of this sort of transparency can sometimes be a barrier to adoption).  The formulation finding optimal checklists as a mixed integer program admits the use of off the shelf solvers, and the encoding of some desirable properties (e.g., keeping the number of predicates small, bounding the difference in performance between subgroups small) as constraints on the optimization.  It can also provide bounds on the gap between the current solution and the best possible solution with respect to training set error.  The authors also propose two methods that are claimed to enable better solutions (with respect to time required and quality).  Evaluations are performed on 8 prediction tasks, each using a different dataset, and the checklist models are for the most part on par with some more complex model classes suggesting plenty of room for trading off marginal gains in performance vs ease of use and deployment, etc.  \n\nOverall, I liked this work a lot and _really_ appreciated the clarity of the writing.  I am not aware of previous uses of MIP for finding optimal checklist models for clinical prediction, though of course there is plenty of prior work (NB - this work was cited appropriately by the current work) on linear models with integer coefficients, etc.  Although this work does not present much very new in the way of core methods - it does provide a useful evaluation of a far simpler model class, and the benefits admitted by framing it as an MIP; I think it would be useful for the NeuRIPS community, particularly the subset focused on clinical prediction tasks, to see this work.  There are, however, some ways in which the work could be improved.  \n\nFirst, I strongly recommend doing an ablation of the sub-modularity heuristic and the path algorithm presented in sections 4.1 and 4.2.  The authors demonstrate the benefit of the adaptive binarization scheme (this scheme is not novel but does seem to have a quite substantial effect on bringing the performance of the checklist models on par with the other baselines!) but not these two components of their method. \n\nSecond, in order for the lasso and xgb baselines to be trusted as reasonable lower bounds on error, it is important to provide some detail on hyperparameter tuning.  It doesn't have to be a lot, and can reasonably be relegated to supplementary materials as long as readers are directed there in the main manuscript.  \n\nThird, I recommend being a bit more circumspect in the language describing the utility of the optimality gaps.  These are bounds regarding the training set behavior, not generalization error.  The authors argue that the extremely simple model class prevents large divergences between training and generalization performance most of the time, and this is borne out for the most part in the evaluations.  Perhaps the authors could emphasize how precisely the gap would be used in practice (i.e., as they implied, to help guide the developer in, say, relaxing constraints on number of predicates, etc, to achieve better performance)?\n\nIn summary, I think this is a very clearly written, well organized paper presenting a useful perspective on how to build clinically useful diagnostic or risk prediction models. There are some gaps in the evaluation I would like to see filled.  \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors are commendably straight forward about some of the technical limitations of their work but it could also be pointed out that the path to clinical utility is a bit more complicated than printing out a checklist and posting it on exam room walls - effective adoption does not end at deployment. \n\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "MJGQ4YNkrAs", "reviewer": "Reviewer_Xd4U", "summary": "The paper proposed a new method to learn predictive clinical checklists for classification tasks by solving an integer programming problem.The method was validated and evaluated with 8 benchmark clinical datasets with consideration of ML fairness. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposed an interesting method to learn a short-form checklists from clinical datasets with the potential application of clinical diagnosis, treatment decision making, etc. The paper showed clear problem constructions, originality of the work with comparison to related literatures and decent considerations on model fairness as well as social impact.\nTechnical analysis might require more experiments to improve the soundness and confirm the utilities of the proposed method. Detailed questions/suggestions are as follows:\n1. As indicated in Authors' checklist, no confidence intervals are reported for experiment results. Considering the oversampling on minority class, boostrapping on training data might be necessary to obtain confidence intervals to evaluate performance robustly. Cross validation could also be applied to test generalization ability of different models. \n2. The paper chose accuracy as the main performance comparison metric across different datasets, which could be optimized considering the real-world scenarios. However, depending on the nature of the task, the cost of false positive (FP) and the cost of false negative (FN) prediction might vary a lot. e.g. For PTSD diagnosis, missing a single positive case might lead to severe outcome in delayed treatment, FNR at a fixed TPR might be a better evaluation metric. But for the mortality task, TPR given a fixed FPR is a more important metric since we need to be very cautious in decision-making on withdrawal of life supporting treatment when a ML classifier makes prediction of \"positive\" in mortality. \n3. A fundamental question: For each of the classification task, feature selection and feature importance could be easily obtained, which could be used as a potential checklist as well. What will be the advantages of the proposed method with comparison to get checklists from feature selection?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "3maopZObYV", "reviewer": "Reviewer_rAcQ", "summary": "Method to train classifiers based on integer programing optimization of binarized variables.\nEvaluate and multiple public healthcare related datasets, comparing accuracy vs. other baseline methods.\nOffers some optimality gap guarantees of models chosen within time constraints (vs. exhaustive search).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Seems to be confusing the term \"checklist\" here. What is described are more analogous to clinical risk scores (see MDCalc.com for implemented example).\nThis is quite different than the checklists \"widely used to promote safety and reliability\" eluded to in the Intro such as surgical pre-op checklists. Most of those are about consistently executing a process and have nothing to do with prediction, risk assessment, diagnosis, or calculation.\n\nThe construction and evaluation of the test models developed overall seem fair, but as eluded to in the Intro, these seem to function very similarly to many existing methods for sparse linear classifiers with small integer coefficients. Neither based on performance or interpretability did there seem to be a dramatic advantage to the proposed approach.\nThe \"certifiably optimal result\" was an interesting contribution to define an optimality gap between the current best performing model vs. best conceivably possible given the available data variables.\n\nNot clear there's much value in reporting train set performance throughout manuscript. Is mostly distracting and even confusing as I first thought the XGBoost models were far outperforming the other models, but that's just because they were overfit to the training data. Potential generalizable accuracy on the test sets is much more relevant.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As above, no major concerns beyond existing tools and technology, but also not clear a substantial difference/impact beyond existing ones.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {"ethical_concerns": "No major concerns, as largely just describing a risk score learning method.\nOffers a somewhat perfunctory \"fairness\" sub-study on example model performance for different racial subgroups.\nAn interesting demonstration of the trade off between more \"fair\" performance characteristics across racial subgroups, but resulting with worse performance on average for all. This is a very brief aside study on one example dataset however, so not enough to really explore the issue in a meaningful way within the scope of this paper.\n"}}]

Author rebuttal:

Meta-review: This work proposes an IP-based solution to learning predictive clinical checklists. Overall, the paper was well received, but reviewers make a number of recommendations to help improve the paper that should be incorporated prior to presentation:
-including error bars/confidence intervals
-including an ablation of the sub-modularity heuristic and the path algorithm
-compare to the strongest baselines possible (thorough baseline hyperparameter turning)
-framing of fairness results
I encourage authors to carefully consider reviewer feedback when working on their revision.

Decision: Accept (Poster)