🤖 machine learning

Learning High Coverage Discriminative Parsimonious Rulesets

This paper introduces CDPR, a novel framework utilizing two submodular maximization-based algorithms to generate highly accurate, discriminative, and parsimonious IF-THEN rule sets that significantly outperform existing methods in both predictive performance and coverage rates.

Original authors: Mariamma Antony, Raman Sankaran, Chiranjib Bhattacharyya, Uma Satya Ranjan

Published 2026-06-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mariamma Antony, Raman Sankaran, Chiranjib Bhattacharyya, Uma Satya Ranjan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a doctor trying to diagnose a patient. You have a massive rulebook that says, "If the patient has symptom A and symptom B, then they have Disease X."

The Problem: The "High Accuracy, Low Coverage" Trap
Current AI systems that create these rulebooks are like expert detectives who are incredibly good at solving some cases but terrible at solving others.

The Good: When they do find a match in their rulebook, they are usually right (high accuracy).
The Bad: Their rulebook is so picky that it only covers a tiny fraction of patients. For the vast majority of people, the rulebook says, "I have no idea what's wrong with you." The AI then has to guess using a "default rule" (like "it's probably nothing"), which is a black box. The patient gets no explanation, just a guess.

The authors call this the "High Accuracy-Low Coverage Problem." It's like having a map that is perfectly detailed for one specific street but leaves the rest of the city blank.

The Solution: CDPR (The "Full-City" Map)
The paper introduces a new method called CDPR (Coverage Discriminative Parsimonious Rule sets). Think of this as a new way to build a rulebook that aims for three things simultaneously:

High Accuracy: The rules must be correct.
High Coverage: The rules must apply to almost everyone (covering the whole city, not just one street).
Parsimony (Simplicity): The rules must be short and easy to understand, not a tangled mess of conditions.

How They Did It: Two New Algorithms
To build this perfect rulebook, the authors created two new "construction crews" (algorithms) that use a mathematical concept called Submodular Maximization. If that sounds scary, think of it as a smart way to pick the best items from a list without wasting time or picking duplicates.

GRA (Graph Rules Algorithm):
- The Metaphor: Imagine a giant social network where every rule is a person. Some people overlap too much (they cover the exact same patients). GRA builds a map of these overlaps. It then picks the "most popular" person (the rule that covers the most new patients) and adds them to the team. Then, it removes anyone who overlaps too much with that new member. It repeats this until the team is full.
- The Result: It creates a highly accurate, non-redundant team of rules that covers almost everyone. It's a bit slower to build but very precise.
GDY (Greedy Algorithm):
- The Metaphor: This is the "quick and dirty" version. Instead of mapping out every single overlap, it just grabs the rule that looks best right now, adds it, and moves on. It's a bit more relaxed about the overlaps but much faster.
- The Result: It builds a rulebook almost as good as GRA but in a fraction of the time.

The Results: Why It Matters
The authors tested these new crews against the best existing methods (like IDS, RIPPER, and DefragTrees) using data from 12 different real-world scenarios, including heart disease, spam detection, and Alzheimer's screening.

The Big Win: The new methods (GRA and GDY) covered more than 2.5 times as many patients as the next best method.
The Trade-off: They didn't lose accuracy. In fact, they were often more accurate than the old methods.
The Simplicity: The rules they generated were short and simple (parsimonious), making them easy for humans to read and trust.

A Real-World Example: The Alzheimer's Test
The paper specifically tested this on designing Neurocognitive Tests for Alzheimer's.

The Issue: Current tests are long and tedious. Doctors have to run a battery of tests on every patient, even if they don't need to.
The CDPR Fix: The new algorithm figured out the minimum set of rules needed to diagnose different stages of the disease (from "Normal" to "Mild Impairment" to "Dementia").
The Outcome: It created a streamlined testing process. Instead of a long, confusing battery of tests, the doctor can follow a clear, short set of rules that covers almost every patient and explains exactly why a diagnosis was made.

In Summary
This paper solves the problem of AI being "right but useless" because it can't explain its decisions for most people. By using smart mathematical tricks (GRA and GDY), the authors created a system that builds rulebooks that are accurate, simple, and cover almost everyone, making AI trustworthy enough to use in critical fields like healthcare and finance.

Technical Summary: Learning High Coverage Discriminative Parsimonious Rulesets (CDPR)

1. Problem Definition

The paper addresses a critical limitation in current interpretable machine learning: the "high accuracy-low coverage" problem. While existing state-of-the-art (SOTA) rule-learning algorithms (e.g., IDS, RIPPER, DefragTrees) often achieve high predictive accuracy, they frequently fail to cover a significant portion of the input space. Low coverage means that for a large fraction of data points, the model relies on a default rule with unknown logic, undermining the transparency and explainability required in critical domains like healthcare and finance.

The authors define the High Coverage Discriminative Parsimonious Rule set (CDPR) learning problem. The objective is to learn a rule set $S$ that simultaneously maximizes coverage (the fraction of the dataset covered by the rules) while satisfying strict quality constraints regarding:

Discriminative Power: Minimum rule accuracy ( $\alpha$ ).
Parsimony: Maximum rule width ( $\delta$ ) and maximum rule set size ( $\gamma$ ).
Interpretability: Maximum overlap rate ( $\beta$ ) between any two rules to ensure minimal redundancy.

Formally, the problem (CDPRL) is defined as:
$\text{maximize}_{S \subseteq B_{\alpha,\delta}} \text{coverage}(S)$
$\text{subject to: } \text{rule-size}(S) \le \gamma, \quad \text{overlap-rate}(r_i, r_j) \le \beta$
where $B_{\alpha,\delta}$ is the set of candidate rules with accuracy $\ge \alpha$ and width $\le \delta$ . The authors note that existing solvers cannot directly address this because the overlap-rate constraint is neither a matroid nor a knapsack constraint.

2. Methodology

The paper proposes two algorithms rooted in submodular maximization to solve the CDPR problem.

2.1 Graph Rules Algorithm (GRA)

GRA is designed to solve the CDPRL problem directly by transforming it into a submodular optimization problem over a graph structure.

Overlap-Graph Construction: A directed graph $G=(V, E)$ is constructed where vertices represent candidate rules in $B_{\alpha,\delta}$ . A directed edge $(r_i, r_j)$ exists if the overlap rate between $r_i$ and $r_j$ exceeds the threshold $\beta$ .
Selection Process: The algorithm iteratively selects the vertex (rule) with the highest coverage from the graph, adds it to the rule set $S$ , and removes the selected vertex along with any vertices connected to it by a directed edge (to satisfy the overlap constraint). This continues until the rule set reaches size $\gamma$ or the graph is empty.
Theoretical Guarantee: The authors prove that GRA provides an approximation guarantee of $(1 - (1 - \frac{1-\beta}{\gamma(1+d\beta)})^\gamma)$ , where $d$ is the minimum in-degree of the selected nodes.
Complexity: The running time is quadratic in the size of the candidate set $|B_{\alpha,\delta}|$ .

2.2 Greedy Algorithm (GDY)

To address the computational cost of GRA, the authors introduce a relaxed variant called CDPRL-MO (Mean Overlap).

Relaxed Objective: Instead of strictly enforcing an overlap rate $\le \beta$ for every pair, GDY optimizes a function $g(S)$ that balances coverage and the minimization of mean overlap across the set.
Submodularity: The authors prove that the objective function $g(S)$ is a non-monotone submodular function.
Algorithm: GDY employs a greedy approximation algorithm designed for non-monotone submodular maximization with cardinality constraints.
Theoretical Guarantee: GDY achieves a $1/4$ -approximation guarantee.
Complexity: The running time is nearly linear in $|B_{\alpha,\delta}|$ , making it significantly faster than GRA for large candidate sets.

3. Key Contributions

Problem Formulation: The paper introduces CDPR as a novel problem formulation that explicitly targets the high accuracy-low coverage trade-off, a gap the authors identify as unaddressed in prior literature.
Novel Algorithms:
- GRA: A graph-based algorithm with provable approximation guarantees for the strict CDPR problem.
- GDY: A computationally efficient greedy algorithm for the relaxed CDPRL-MO variant.
Theoretical Analysis: The authors provide formal proofs for the approximation guarantees of both algorithms, establishing their theoretical validity within the framework of submodular optimization.
Empirical Validation: Extensive experiments on 12 datasets (10 UCI datasets and 2 Alzheimer's disease datasets) demonstrate the efficacy of the proposed methods.

4. Experimental Results

The authors evaluated GRA and GDY against SOTA baselines (IDS, DefragTrees, RIPPER) and standard black-box models (Random Forest, Logistic Regression).

Coverage: The most significant improvement was observed in coverage rates. GRA achieved an average coverage rate of 97%, and GDY achieved 91%. In contrast, the next best baseline (IDS) achieved only 35%, and RIPPER achieved 31%. This represents a 2.5-fold improvement in average coverage over the best existing rule-learning algorithm.
Accuracy (Discriminative Power): GRA achieved an average Rule Set Accuracy (RSA) of 0.85, outperforming IDS (0.82), DefragTrees (0.76), and RIPPER (0.80). GRA's performance was competitive with Random Forest (RF), matching or surpassing RF in 7 out of 12 datasets.
Parsimony: Both GRA and GDY maintained low rule widths (average max width of 4) and reasonable rule set sizes (average 7 rules), comparable to IDS and RIPPER, and significantly better than DefragTrees (average max width of 10).
Case Study (Alzheimer's Disease): In a specific application designing neurocognitive tests for Alzheimer's screening, GRA and GDY successfully generated rule sets that reduced the number of required features by at least 18% compared to DefragTrees while maintaining high accuracy and coverage (>70%).

5. Significance and Claims

The paper claims that CDPR represents the first attempt to establish an approach that simultaneously optimizes for high coverage, discriminative power, and parsimony in rule learning.

The authors emphasize that while interpretability is often defined merely by model complexity (fewer rules), true interpretability in critical applications requires that the model can explain decisions for the vast majority of inputs (high coverage). By solving the high accuracy-low coverage problem, the proposed methods (GRA and GDY) enable the deployment of interpretable models in domains where transparency and faithfulness are paramount, such as healthcare and criminal justice, without sacrificing predictive performance. The work suggests that submodular maximization is a viable and effective framework for learning high-quality rule sets, offering a path toward more trustworthy AI systems.