Learning Certifiably Optimal Rule Lists for Categorical Data

Motivation

• Rule lists provide human-readable reasons for predictions, addressing the interpretability problem of socially consequential machine-learning decisions.The introduction contrasts this transparency with proprietary models whose prediction reasons and potential bias cannot be independently determined, as in COMPAS.Source: §1 · pp. 1–2

Problem formulation

• The algorithm searches rule lists assembled from pre-mined frequent itemsets, overcoming the exponential worst-case search through algorithmic, data-structure, and implementation techniques.The goal is solving fairly large practical instances to optimality rather than relying on brute force.Source: §1 · p. 2

Method

• CORELS uses specialized branch-and-bound search to find the optimal rule list under a regularized risk function and certify that no alternative is better.The certificate also measures how close greedy models are to optimal.Source: §1 · pp. 2–3

Branch-and-bound

• CORELS prunes incomplete lists using lower bounds on regularized risk, rule-level requirements, incumbent comparisons, and symmetry-aware comparisons across permutations.The symmetry-aware map is especially important because it tracks the best accuracy for incomplete lists capturing the same data.Source: §1 · p. 3

Implementation

• A modified prefix-tree trie organizes rule-list generation and evaluation while supporting breadth-first, best-first, and stochastic search with tunable space-time tradeoffs.Priority-queue ordering enables different best-first strategies, and limiting trie nodes controls memory use.Source: §1 · p. 3

Empirical results

• CORELS produces certifiably optimal, interpretable rule lists with accuracy matching approaches such as random forests on COMPAS and stop-and-frisk data.These results question the need for proprietary black-box recidivism prediction.Source: §1 · p. 3

Optimal trees and lists

• CORELS addresses the computationally hard optimal decision-tree problem through tighter bounds and data structures than prior optimization-based methods, including Nijssen and Fromont (2010).Rule lists and decision trees are equivalent in representational power, but prior bottom-up tree search can create memory problems, whereas CORELS uses tight bounds and data structures.Source: §2 · p. 4

Search strategies

• Rule-list search spaces are smaller and simpler than tree spaces, helping Bayesian rule-list methods escape local minima more effectively, although CORELS has tighter bounds than existing Bayesian lists.Greedy methods such as CART, C4.5, and RIPPER explore less of the search space, while Bayesian tree methods often reach only locally optimal solutions.Source: §2 · p. 4

DNF and rule mining

• CORELS can be restricted to learn optimal DNF models, and rule-learning or associative-classification methods could help order its queue to eliminate search space faster.This follows because DNF models are a proper subset of decision lists; CORELS may use methods such as Rijnbeek and Kors (2010) and earlier rule-learning work to prioritize search.Source: §2 · p. 5

Optimization and preprocessing

• CORELS shares its objective and some bounds with Rudin and Ertekin (2016), but mixed-integer programming solvers generally cannot match CORELS’s speed.CORELS depends on pre-mined rules obtained by enumeration, and alternative association-rule-mining methods could reasonably substitute for this preprocessing step.Source: §2 · p. 5

Interpretability

• Interpretability motivates CORELS because transparent models have societal and regulatory importance, while achieving both sparsity and accuracy requires substantial optimization beyond heuristics.The section connects this motivation to the European Union’s “right to an explanation” discussed by Goodman and Flaxman (2016).Source: §2 · p. 5

Scope and limitations

• CORELS produces predictive rather than causal models and does not account for outcome or information-gathering costs, although its framework could be adapted to causal and treatment-regime settings.Interpretability constraints and class-imbalance handling can also be extended, but Falling Rule Lists are more complicated because CORELS’s basic support bounds do not apply directly.Source: §2 · pp. 5–6

3.1 Notation

• The framework learns binary-classification rule lists whose consequent and default predictions are set empirically to minimize training misclassification error for each antecedent prefix.Rules classify each datum using the first true antecedent, with uncaptured data assigned the default prediction.Source: §3.1 · pp. 6–8

3.2 Objective Function

• The objective is a regularized empirical risk combining misclassification loss, measured as the fraction of training data incorrectly predicted, with a regularization term penalizing longer rule lists.The regularization parameter λ ≥ 0 is a small constant; λ = 0.01 is equivalent to misclassifying 1% of data when increasing a rule list by one association rule.Source: §3.2 · p. 8

3.3 Optimization Framework

• Branch-and-bound exploits prefix lower bounds, accuracy-based pruning, maximum-length bounds, support and prediction thresholds, and permutation reduction to eliminate large parts of the rule-list search space.These bounds preserve the guarantee of finding a globally optimal rule list from the pre-mined rules.Source: §3.3 · p. 8

3.4 Hierarchical Objective Lower Bound

• The hierarchical lower bound decomposes prefix and default-rule errors, and any extension of a prefix has objective at least that prefix’s bound, enabling subtree pruning when the bound reaches the current best objective.A one-step lookahead further prunes all longer extensions when b(dp, x, y) + λ ≥Rc.Source: §3.4 · pp. 9–10

3.5 Upper Bounds on Prefix Length

• Upper bounds on prefix length come from the number of available antecedents, the current best objective, and tighter bounds based on specific prefix families.A perfect K-rule list allows pruning prefixes of length K or greater when identifying a single optimal rule list.Source: §3.5 · pp. 11–12
• Prefix-specific bounds limit the lengths of rule-list continuations whose lower bound is below the current best objective, generalizing the one-step lookahead bound.For the empty rule list, the bound reproduces the earlier bound because b(dp, x, y) = 0.Source: §3.5 · pp. 12–13

3.6 Upper Bounds on the Number of Prefix Evaluations

• Theorem 7 bounds remaining prefix evaluations using the current best objective and queue state, while Proposition 9 offers a weaker, easier-to-compute progress metric.Theorem 7 incorporates prefix-specific objective lower bounds; Proposition 9 uses only coarse queue information and is used in the implementation and user-facing progress display.Source: §3.6 · pp. 13, 15

Proposition 9 (Coarse-grained upper bound on remaining prefix evaluations)

• Proposition 9 counts remaining evaluations from queue prefix lengths and the bound K = min(⌊Rc/λ⌋, M), but is strictly weaker than Theorem 7.Its bound depends on the current best objective and coarse queue information, whereas Theorem 7 also uses prefix-specific objective lower bounds.Source: §3.6 · pp. 14–15, Proposition 9 (Coarse-grained upper… · p. 15

3.7 Lower Bounds on Antecedent Support

• Theorem 10 requires every antecedent in an optimal rule list to capture at least a fraction λ of data, enabling pruning and restricting mined rules to normalized support at least λ.Theorem 11 tightens this by requiring each rule to correctly classify at least a fraction λ of data; both bounds can be used, with the easier support check first.Source: §3.7 · pp. 16–17

3.8 Upper Bound on Antecedent Support

• Theorem 21 implies that antecedent normalized support is at most 1 −λ, but the implementation does not use this upper bound because preliminary experiments showed no meaningful benefit.The result is presented in Appendix A and is used to restrict rule mining rather than as an implementation pruning bound.Source: §3.8 · p. 17

3.9 Antecedent Rejection and its Propagation

• Antecedent rejection unifies insufficient, insufficient accurate, and excessive support, and Theorem 12 propagates rejection to larger prefixes, allowing them to be pruned as non-optimal.The implementation prunes directly using the underlying support bounds; dedicated data structures for direct propagation were left as future work.Source: §3.9 · pp. 17–18

3.10 Equivalent Support Bound

• Equivalent-support pruning discards prefixes that capture the same data as a more accurate prefix, because replacing a prefix with equal support cannot improve the objective.Theorem 15 formalizes this equivalence across rule lists whose prefixes capture exactly the same data.Source: §3.10 · p. 20
• Equivalent-support pruning applies when prefixes capture the same data and one prefix has a no-greater objective lower bound than the other.Under these conditions, the optimal objective over the first prefix’s extensions lower-bounds the optimal objective over the second’s extensions.Source: §3.10 · p. 21

3.11 Permutation Bound

• Permutation symmetry lets branch-and-bound retain one best prefix per equivalence class, because permuted prefixes capture the same data and the less accurate ordering can be pruned.This symmetry-aware pruning accounts for the factorial equivalence among prefixes containing the same antecedents.Source: §3.11 · pp. 21–22, §3.12 · p. 22

Theorem 17 (Upper bound on prefix evaluations with symmetry-aware pruning)

• Theorem 17 bounds the evaluated prefixes by retaining only one representative for each permutation-equivalence class after each prefix length, with optimal-list length bounded by K = min(⌊1/2λ⌋, M).The construction evaluates prefixes breadth-first and propagates the resulting combination-based count through prefix lengths.Source: Theorem 17 (Upper bound on prefix… · p. 22
• Symmetry-aware pruning reduces prefix evaluations by about 23× for M = 100, K = 5 and about 360,000× for M = 1000, K = 10.The reduced counts are about 3.9 × 10^8 versus 9.1 × 10^9, and 2.7 × 10^24 versus 9.6 × 10^29, respectively.Source: Theorem 17 (Upper bound on prefix… · p. 22

3.13 Similar Support Bound

• The similar-support bound lower-bounds objective differences using lower-bound differences minus the normalized support disagreement, but the implementation does not currently use it.It can prune prefixes with similar support when the resulting bound reaches the current best objective.Source: §3.13 · pp. 23–24

3.14 Equivalent Points Bound

• Equivalent-point sets yield a tighter lower bound because any rule assigns one label to all points in a set, forcing at least the minority-label count as mistakes.The bound tightens the default-rule misclassification component and can be combined with other bounds; experiments report potentially dramatic practical consequences.Source: §3.14 · pp. 24–26

Incremental computations

• A cache stores each prefix’s objective lower bound, enabling incremental evaluation of child bounds and objectives during branch-and-bound.The objective is computed from the child lower bound, avoiding additional storage of the parent objective.Source: §4 · pp. 26–27

Incremental branch-and-bound

• Algorithm 2 combines incremental bound and objective functions with cached prefixes to return a provably optimal rule list and objective.It groups computations by parent prefix and applies the bound before evaluating candidate objectives.Source: §4 · pp. 27–28

Implementation

• Grouping all children of a prefix consolidates cache queries and represents them with one queue element, reducing repeated operations and queue storage.Both savings arise because children share their parent’s stored lower bound and are processed as a group.Source: §4 · p. 28
• Nearly 1000-fold smaller maximum queues result when optimizing over a set of 1000 antecedents.This comparison is between Algorithm 2 and Algorithm 1.Source: §4 · p. 29

5.1 Prefix Tree

• The prefix tree caches evaluated prefixes and stores bounds, viable extensions, deletion status, and metadata needed for incremental computation.Each node encodes a rule, while each root-to-node path represents a prefix; stored bounds include b(dp, x, y) and b0(dp, x, y).Source: §5.1 · p. 30

5.2 Queue

• Queues represent unexplored prefix-tree leaves and support breadth-first, depth-first, best-first, and custom search policies through unified priority-queue ordering.The implementation uses STL queue and priority queue structures, with lower-bound ordering usually faster than breadth-first search.Source: §5.2 · p. 31

5.3 Symmetry-aware Map

• The symmetry-aware map canonicalizes antecedent sets and retains only the permutation with the better lower bound, pruning inferior permutations and their subtrees.If a candidate improves on an existing permutation, the map, trie, and queue are updated; otherwise, the candidate is discarded.Source: §5.3 · p. 31

5.4 Incremental Execution

• Incremental execution extends queued prefixes, updates objectives and bounds, applies pruning checks, and outputs the optimal rule list when the queue is exhausted.The hierarchical lower bound prevents insertion of extensions that cannot improve the current best objective, while alternate early termination is possible when memory thresholds are exceeded.Source: §5.4 · p. 32

5.5 Garbage Collection

• Garbage collection limits trie memory by deleting subtrees ruled out by the current objective and lazily removing marked leaves after their queue entries are popped.Lazy deletion is necessary because the STL priority queue does not expose or update elements in its underlying container.Source: §5.5 · p. 32

5.6 Custom Scheduling Policies

• Curiosity functions prioritize prefixes by estimating related rule lists’ objective values, favoring prefixes with greater captured support when lower bounds are equal.The strategy models extensions with smaller support as having greater potential for mistakes and computes curiosity from quantities already derived during execution.Source: §5.6 · pp. 34–35
• Curiosity-ordered priority queues sometimes dramatically reduce execution time versus lower-bound ordering on specific small problems, though broader effectiveness remains future work.Curiosity equals the objective lower bound scaled by inverse normalized support and requires no additional expensive computations.Source: §5.6 · p. 35

6.1 Computational Environment

• The experiments ran each timing measurement separately on one hardware thread of an Intel Xeon server with 264 GB RAM, although most experiments fit comfortably on 16 GB laptops.The study investigated predictive performance, model size, convergence, optimization contributions, and search-space pruning.Source: §6.1 · p. 36, §6 · p. 36

6.2 Data Sets and Prediction Problems

• The recidivism task used 6,907 complete Broward County records, while the weapon task used 325,800 frisked or searched NYPD records with 10,885 weapons found.CORELS used 13 binary features yielding 122 average antecedents for recidivism and 5 categorical features yielding 28 antecedents for weapon prediction.Source: §6.2.1 · pp. 36–37, §6.2.2 · p. 37

6.2.2 Weapon Prediction

• In the NYPD weapon data, only about 3.3% of eligible frisked or searched records involved identified criminal possession of a weapon.Class-imbalance resampling produced training sets of 566,839 datapoints for 10-fold cross-validation, while test sets were not resampled.Source: §6.2.2 · p. 37

6.3 Example Optimal Rule Lists

• CORELS’s optimal rule lists were short, easy to understand, and generally robust across cross-validation folds, with similar rules up to prefix permutations.Smaller λ values allowed longer lists and reduced robustness; race-dependent antecedents appeared in none of the optimal ProPublica lists using Feature Set B.Source: §6.3 · pp. 38–39, Figure 3 · p. 38, Figure 4 · p. 39

6.4 Comparison of CORELS to the Black Box COMPAS Algorithm

• CORELS achieved mean test accuracy 0.665 (standard deviation 0.018) versus COMPAS’s 0.660 (standard deviation 0.019) across 10 recidivism cross-validation folds.CORELS and COMPAS showed similar TPR, FPR, TNR, and FNR patterns across black and white individuals.Source: §6.4 · p. 40, Figure 7 · p. 41, Figure 9 · p. 45

6.5 Comparison of CORELS to a Heuristic Model for Weapon Prediction

• CORELS models recovered at least 40% of weapons on average while requiring well under 25% of stops, outperforming heuristic models with T ≥2.CORELS models also included approximately 3 or 5 rules and required no arithmetic, making them approximately as small and interpretable as the heuristic models.Source: §6.5 · p. 43, Figure 8 · p. 44

6.6 Predictive Performance and Model Size for CORELS and Other Algorithms

• CORELS produces predictive performance comparable to or better than other algorithms while learning short rule lists without sacrificing performance.On ProPublica, test-accuracy differences across algorithms were not statistically significant; on NYCLU, CORELS achieved intermediate TPR with relatively low FPR.Source: §6.6 · p. 45, Figure 9 · p. 45
• CORELS found short rule lists using age, prior convictions, and sex with test accuracy comparable to COMPAS, and the same two-feature list appeared across all 10 folds.With only age and prior convictions and λ = 0.005, CORELS again achieved COMPAS-comparable test accuracy; the resulting rules require no arithmetic computation.Source: §6.6 · pp. 46–47, Figure 13 · p. 47

6.7 CORELS Execution Traces, for Different Regularization Parameters

• As λ decreased, CORELS required longer prefixes and larger data structures, while optimality certification occurred when the lower bound matched the current best objective.The optimum was reached in a small fraction of total execution time, but lower λ values made pruning the remaining search space more difficult.Source: §6.7 · pp. 48–49

6.8 Efficacy of CORELS Algorithm Optimizations

• Removing any single optimization increased runtime; equivalent points were most important for ProPublica, whereas the symmetry-aware map was crucial for NYCLU.Without the equivalent-points bound, ProPublica executions reached prefixes of at least length 10 and terminated incomplete; without the symmetry-aware map, NYCLU required more than an hour.Source: §6.8 · pp. 50, 52

6.9 Algorithmic Speedup

• 28 million prefixes yielded 893× and 1.8 × 10^13 reductions versus naïvely examining prefixes through lengths 5 and 10, respectively, while runtime was about 36 seconds.Naïve evaluation would take about 9 hours for length 5 and 21 million years for length 10.Source: Table 6 · p. 53, §6.9 · pp. 54–55

Empirical impact of bounds

• Equivalent support and equivalent points bounds produced the most significant empirical performance improvements and were sometimes critical for finding and certifying optimal solutions.These bounds sometimes mattered even on small problems.Source: §7 · p. 56

Future bounds

• Future work should efficiently exploit the similar support bound, which may enable principled approximate variants of the approach.The paper identifies efficient practical exploitation of this bound as an important direction.Source: §7 · p. 56

Data structures

• Symmetry-aware maps support accurate-support and equivalent-support bounds, but efficient data structures remain needed for equivalent-points, similar-support, and antecedent-rejection bounds.The looser accurate-support bound can be checked before the tighter accurate-antecedent-support bound, while antecedent-rejection propagation also remains future work.Source: §7 · p. 56

Progress estimation

• Upper bounds on the remaining search space estimate execution time and help compare the effects of retaining or removing algorithmic bounds.Theorem 7 and the lower-overhead Proposition 9 provide such progress information.Source: §7 · p. 56

Execution and guarantees

• The algorithm outputs an optimal training solution with a certificate, while incomplete executions can provide quality guarantees by bounding the remaining search space.The optimal rule list is often identified in seconds, compared with minutes needed to prove optimality.Source: §7 · pp. 56–57

Search policies

• Search policies that improve prefix-evaluation order could substantially increase pruning and reduce total runtime.The evaluation order affects how quickly the search space is pruned.Source: §7 · p. 57

Limitations

• CORELS may struggle to certify optimality when many relevant features are highly correlated and large search-space regions are difficult to exclude.It scales well to large numbers of observations, but its optimality-certification difficulty increases in these feature settings.Source: §8 · p. 57
• CORELS is unsuitable for raw images and does not directly handle continuous variables, though engineered interpretable features or rules could make it useful in both settings.Image-derived classifiers could be combined with CORELS, while Fast Boxes is suggested for discovering interpretable continuous-data rules.Source: §8 · pp. 57–58

Future directions

• Future work could develop simpler optimal DNF algorithms, cost-sensitive or weighted-regularized CORELS, and hybrid models that use black boxes near the decision boundary.The weighted extensions would require more general versions of the existing theorems.Source: §8 · pp. 57–58

Limitations

• CORELS neither ranks subgroups by positive-outcome likelihood nor estimates treatment effects, but empirical antecedent proportions or causal rule-list methods can address these needs.Alternative approaches include Falling Rule Lists, Causal Falling Rule Lists, CITR, and interpretable treatment-regime methods.Source: §8 · p. 57

Future directions

• CORELS optimizes one-sided decision trees with conjunctive leaves, and extending its ideas to generic single-variable-split trees would require addressing their greater symmetry.Equivalent generic trees create challenges for symmetry-aware data structures.Source: §8 · p. 58

Theorem 21

• Antecedents capturing nearly all data left uncovered by their prefix are non-optimal when the uncovered remainder is less than λ.Equality at λ can preserve optimality; otherwise the added rule’s penalty exceeds any possible error reduction.Source: Appendix A · p. 59
• Additional rules after an antecedent with insufficient remaining support also cannot restore optimality, because each subsequent rule inherits support at most λ.The proof applies Theorem 10 to conclude that any such extended rule list is non-optimal.Source: Appendix A · p. 59

Algorithmic implication

• Theorem 21 enables branch-and-bound pruning of prefixes whose next antecedent’s support is too similar to the remaining uncovered-data support.Such a rule behaves like the preceding list’s default rule, so its error reduction cannot offset the longer prefix’s regularization penalty.Source: Appendix A · p. 59

Proposition 22

• Proposition 22 shows that excessive antecedent support propagates when a prefix is embedded in a longer rule list, making that longer list non-optimal.The inherited prefix support is at least the original prefix support, so the designated antecedent remains excessive and Theorem 21 applies.Source: Appendix A · p. 60

Objective equivalence

• Analogous extensions preserve objective differences because corresponding prefixes capture the same data, share default errors, and use identical added antecedents and labels.This yields R(d′, x, y) − R(d, x, y) = R(D′, x, y) − R(D, x, y).Source: Appendix B · p. 61

Lower-bound comparison

• Under b(dp, x, y) ≤ b(Dp, x, y), the corresponding base rule lists satisfy R(d, x, y) ≤ R(D, x, y).The proof then transfers the objective difference from an optimal extension d∗ to its analogous extension D∗.Source: Appendix B · p. 62

Unequal prefixes

• When prefixes differ, extensions containing antecedents absent from the other prefix cannot be optimal because those antecedents have insufficient support.The argument applies symmetrically to antecedents unique to either prefix, using Theorem 10.Source: Appendix B · p. 62

Conclusion

• Combining the base inequality with optimal-extension equivalence proves min d′∈σ(dp) R(d′, x, y) ≤ min D′∈σ(Dp) R(D′, x, y).The proof restricts attention to extensions excluding unsupported antecedents, which have direct analogues under the other prefix.Source: Appendix B · p. 63

Construction

• The proof defines rule lists d, D, d′, and D′ so that d′ and D′ share the same added antecedents while retaining their respective prefixes.The prefixes have lengths K and κ, while the extensions add K′−K analogous antecedents.Source: Appendix C · p. 63

Objective comparison

• R(D′, x, y) ≥ R(d′, x, y) + b(Dp, x, y) − b(dp, x, y) − ω − Ω.The bound accounts for the difference between the objective lower bounds and the largest possible discrepancy on data associated with ω and Ω.Source: Appendix C · p. 63

Conclusion

• Applying the comparison to an optimal rule list D∗ with prefix Dp and its analogous list d∗ yields the desired inequality (24).The analogous list d∗ uses K∗ = K + κ∗ − κ and shares D∗’s additional κ∗ − κ antecedents.Source: Appendix C · pp. 63–64

Appendix D. Proof of Theorem 20 (Equivalent Points Bound)

• The proof lower-bounds default-rule misclassification error by summing label differences within sets of equivalent points relative to each set’s minority class.This parallels the lower-bound strategy used for the misclassification error in Proposition 19.Source: Appendix D · p. 64

Appendix E. Data Processing Details and Antecedent Mining

• The appendices connect the theoretical equivalent-points bound with the experimental data-processing documentation.Appendix D develops the bound, while Appendix E documents the datasets underlying the experiments.Source: Appendix D · p. 64, Appendix E · p. 65

Appendix D. Proof of Theorem 20 (Equivalent Points Bound)

• Applying the equivalent-points counting identity yields a lower bound on the objective R(d, x, y).The identity follows from the definition of b0(dp, x, y).Source: Appendix D · p. 64
• The objective R(d, x, y) is decomposed into predictive loss, default-rule error, and regularization, then expressed as b(dp, x, y) plus default-rule error.The decomposition supplies the basis for deriving a lower bound on R(d, x, y).Source: Appendix D · p. 64
• The proof compares lower bounds for d and d′, showing that the bound for d is no greater than the corresponding bound for d′.The comparison combines bounds on b and b0 and establishes the desired inequality in (27).Source: Appendix D · pp. 64–65

Appendix E. Data Processing Details and Antecedent Mining

• Appendix E provides details about the datasets used in the experiments reported in Section 6.The appendix is devoted to data-processing details and antecedent mining.Source: Appendix E · p. 65

E.1 ProPublica Recidivism Data Set

• Researchers construct 17 single-clause antecedents from these categorical values, such as (age = 23 −25).Source: §E.1 · p. 66
• They also form two-clause antecedents by combining pairs of single-clause antecedents, such as age and prior-count categories.Source: §E.1 · p. 66
• Antecedents with support below 0.005 or above 0.995 are eliminated using the lower-bound result in Theorem 10, §3.7.Source: §E.1 · p. 66
• After filtering, each fold contains 121–123 antecedents, compared with about 130 without filtering, because λ = 0.005 is the smallest studied regularization value.Source: §E.1 · p. 66
• The ProPublica data set uses 6 attributes and 17 categorical values, including juvenile crimes formed by aggregating three juvenile-crime categories.Source: Table 7 · p. 66

E.2 NYPD Stop-and-frisk Data Set

• The ProPublica data set is larger than, but similar to, the NYCLU NYPD stop-and-frisk data set described next.Source: §E.2 · p. 66

E.3 NYCLU Stop-and-frisk Data Set

• The processed NYCLU dataset contains 29,595 records involving frisking and/or searching after removing missing-data and extreme-age cases.The original data included 45,787 incidents; 30,961 involved frisking and/or searching, and 1,929 records were removed for missing data, with additional exclusions for age below 12 or above 89.Source: §E.3 · p. 66
• To address class imbalance, the experiments resample the smaller class with replacement within pre-generated cross-validation folds.Each training set in the 10-fold experiments contains 50,743 observations.Source: §E.3 · p. 66
• The NYCLU prediction problems use 5 categorical attributes with 28 values, plus negations of 18 antecedents for stop reason and additional circumstances.Together, these produce 46 antecedents for rule-list construction.Source: §E.3 · p. 67, Table 8 · p. 67
• The feature specification is summarized in Table 8 as 5 categorical attributes and 28 values.These attributes define the categorical feature space used in the NYCLU experiments.Source: Table 8 · p. 67

Appendix F. Example Optimal Rule Lists, for Different Values of λ

• Appendix F lists CORELS optimal rule lists across 10 cross-validation folds for each prediction problem and several regularization values λ.These listings correspond to CORELS results summarized in Figures 11 and 12 (§6.6).Source: Appendix F · p. 67
• As λ decreases, the optimal rule lists generally become longer.The appendix uses rule-list examples at different regularization settings to illustrate this length–regularization relationship.Source: Appendix F · p. 67

Optimal rule-list structure

• Across 10 folds, λ = 0.02 yielded the same length-1 list, while λ = 0.01 and 0.005 yielded 2- or 3-rule and 3- or 4-rule lists, respectively, with nearly identical prefix rules up to permutation.All prefix rules predicted the positive class and every default rule predicted the negative class; the objective was not designed to enforce either property.Source: §F.1 · p. 67, Figure 19 · p. 68, Figure 20 · p. 69

λ = 0.02

• The rule if (priors > 3) then predict yes, else predict no was found by all 10 folds at λ = 0.02.This is the shared length-1 rule identified for the largest regularization parameter.Source: §F.1 · pp. 67–68, Figure 19 · p. 68

λ = 0.005

• At λ = 0.005, optimal lists used combinations of age, sex, juvenile crimes, and prior convictions, with 3- or 4-rule structures across folds.Examples included age = 18 −20 with sex = male, age = 21 −22 with priors = 2 −3, age = 23 −25 with priors = 2 −3, and priors > 3.Source: §F.1 · pp. 68–69

• CORELS produced example optimal NYPD rule lists predicting weapon discovery, with the displayed rules varying by regularization and feature set.The examples include λ = 0.01 and λ = 0.005 settings across 10 cross-validation folds.Source: §F.2 · p. 70, Figure 21 · p. 70, Figure 22 · p. 71
• The strongest displayed rules first predict yes for stop reason = suspicious object, then use transit-authority, housing-authority, Manhattan, or inside/outside conditions.Some rules predict no for housing-authority stops or outdoor stops, while others predict yes for transit-authority or indoor stops.Source: §F.2 · pp. 70–71
• Feature Set D rules retain stop reason = suspicious object as the first prefix rule and otherwise distinguish acting as lookout, fits description, and furtive movements.These rules predict no for those listed stop reasons before a default yes prediction.Source: §F.2 · p. 71, Figure 22 · p. 71
• For λ = 0.005, seven folds are shown, while the remaining three were equivalent up to prefix-rule permutation and began with the same first prefix rule.The examples were found by CORELS across 10 cross-validation folds.Source: §F.2 · p. 71

• Across 10 cross-validation folds, λ = 0.04 and 0.01 produce optimal rule lists containing the same or equivalent rules, up to permutation.Figure 23 presents these example lists for the two larger regularization parameters.Source: §F.3 · p. 72, Figure 23 · p. 72
• At λ = 0.0025, optimal rule lists show greater diversity and length while sharing similar structure.Figure 24 shows example lists learned with this smaller regularization parameter.Source: §F.3 · p. 72, Figure 24 · p. 73
• The lists predict weapon discovery using stop reasons and locations, including suspicious objects, suspicious bulges, casing, transit authority, and Manhattan.Representative lists vary in rule ordering and additional conditions across folds.Source: §F.3 · pp. 72–73

Appendix G. Additional Results on Predictive Performance and Model Size for CORELS and Other Algorithms

• The comparison covers CORELS and three other algorithms using the NYPD data set with Feature Set D.Algorithm parameters are shown in parentheses in the legend, as in Figure 12.Source: Appendix G · p. 74
• The appendix plots test-set TPR and FPR as functions of model size across different methods.The plots use the NYPD stop-and-frisk data set with Feature Set D.Source: Figure 25 · p. 74, Appendix G · p. 74
• C4.5 finds large models for all tested parameters on the NYPD weapon-prediction task.Legend markers and error bars represent means and standard deviations across cross-validation folds.Source: Appendix G · p. 74, Figure 25 · p. 74