💻 computer science

Target-confidence Recourse Using tSeTlin machines: TRUST

The paper proposes TRUST, a framework that leverages Probabilistic Tsetlin Machines and Bayesian optimization to generate robust, interpretable counterfactual explanations by directly searching for minimal input changes that satisfy user-defined prediction confidence targets, thereby overcoming the fragility of conventional boundary-crossing recourse methods.

Original authors: K. Darshana Abeyrathna, Sara El Mekkaoui, Nils Enric Canut Taugbøl, Anuja Vats

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: K. Darshana Abeyrathna, Sara El Mekkaoui, Nils Enric Canut Taugbøl, Anuja Vats

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 applying for a loan, and the bank's computer says "No." You ask, "What do I need to change to get a 'Yes'?"

Most current AI systems answer with a bare minimum suggestion: "If you increase your income by just $1, the computer will flip its decision to 'Yes'."

The paper calls this a "boundary-hugging" counterfactual. It's like standing right on the edge of a cliff. Technically, you are on the safe side, but a tiny breeze (a small error in the data or a slight change in the model) could knock you right back off the edge. It's a fragile "Yes."

TRUST is a new method proposed by researchers at DNV that changes the game. Instead of asking, "What is the smallest change to get a Yes?", it asks: "What is the smallest change to get a confident Yes?"

Here is how the paper explains this, using simple analogies:

1. The Goal: From "Edge of the Cliff" to "Deep in the Valley"

In the old way, the AI just wants you to cross the line. In the TRUST method, you tell the AI: "I don't just want to cross the line; I want to be 80% sure I'm safe."

The Analogy: Imagine you are walking through a foggy forest.
- Old Method: The AI tells you to take one step forward. You are now technically on the "safe path," but you are still in the fog. If you stumble slightly, you might fall back into the danger zone.
- TRUST Method: You tell the AI, "I want to walk until I am in a clearing where I am 90% sure I won't get lost." The AI might tell you to take five steps instead of one. You are now deeper in the safe zone. If you stumble, you are still safe.

2. The Engine: The "Logic Puzzle" Machine (Tsetlin Machine)

To do this, the researchers didn't use a standard "black box" AI (like a deep neural network) that gives a number but doesn't explain why. They used something called a Probabilistic Tsetlin Machine (PTM).

The Analogy: Think of a standard AI as a magician pulling a rabbit out of a hat. You see the rabbit (the result), but you don't know how it happened.
The PTM: Think of the PTM as a team of logic detectives. Each detective has a specific rule, like "If the applicant is under 73 AND has few lymph nodes, then they are likely to survive."
- These detectives don't just say "Yes" or "No." They say, "I am 90% sure this rule applies," or "I am only 50% sure."
- The final decision is a vote among all the detectives.

3. The Superpower: Seeing Why One Option is Better

This is the paper's most unique claim. Because the AI is made of these logic detectives, TRUST can explain why one suggestion is more reliable than another, even if they look similar.

The Scenario: Imagine two people want to get a loan.
- Person A changes their income just enough to barely pass the rule.
- Person B changes their income a bit more to pass the rule comfortably.
The Old AI: Might say, "Person A is better because they changed less."
TRUST: Looks at the "detectives" and says: "Person A's success depends on a rule that is very shaky. If their data changes slightly, that rule might stop working. Person B's success relies on rules that are rock-solid. Even though Person B changed more, their 'Yes' is much more stable."

The paper calls this "Clause-Level Attribution." It's like being able to look under the hood of a car and see exactly which engine part is wobbling, rather than just knowing the car is moving.

4. The Results: Trading a Little Effort for Big Safety

The researchers tested this on real-world data (like predicting survival after surgery) and made-up data.

The Finding: When they asked for a "high confidence" result (e.g., 92% sure), the AI suggested changes that were slightly larger than the bare minimum.
The Payoff: These suggestions were much more robust. When the researchers added "noise" (simulated errors or small changes) to the data, the "bare minimum" suggestions often failed and turned back into "No." The "high confidence" suggestions stayed "Yes."

Summary

TRUST is a tool that lets you say to an AI: "I don't just want a yes; I want a stable, reliable yes."

It uses a special type of AI made of logical rules (like a team of detectives) to find the smallest change you need to make to reach that level of safety. It admits that sometimes you have to change a little more to get a result you can truly trust, and it explains exactly why that extra change makes your outcome safer.

What the paper does NOT claim:

It does not claim this works for every type of AI (it specifically uses the Tsetlin Machine).
It does not claim this is a medical cure or a guaranteed way to get a loan approved in the real world yet; it is a research framework tested on datasets.
It does not say this is faster than current methods (in fact, it notes it can be slower because it does more complex searching).

Technical Summary: Target-Confidence Recourse Using tSeTlin Machines (TRUST)

Problem Statement

Counterfactual explanations (CEs) are the standard mechanism for providing algorithmic recourse in high-stakes decision-making systems (e.g., credit approval, clinical risk stratification). The prevailing formulation of recourse seeks the minimal change to an input $x$ required to flip a model's decision from negative to positive. Formally, this is an optimization problem minimizing the distance $d(x, x')$ subject to the constraint that the predicted probability $M(x') \geq 0.5$ .

The paper identifies two critical limitations in this binary framing:

Fragility: Counterfactuals generated near the decision boundary (where $M(x') \approx 0.5$ ) are often unstable under noise, model updates, or perturbations. They may technically satisfy the label-flip condition but fail in practice due to low confidence margins.
Misalignment with Decision-Making: Real-world decision systems frequently employ explicit confidence thresholds (e.g., requiring 80% confidence for approval). Existing methods cannot directly answer questions like, "What is the minimal change to achieve approval with at least 80% confidence?" They treat confidence as a post-hoc property rather than a user-specified optimization target.

While prior work has addressed robustness indirectly through margin constraints or neighborhood validity, and uncertainty-aware methods (like CLUE or probabilistic certificates) exist, none allow users to specify a desired confidence level as a primary constraint during the generation of recourse.

Methodology: The TRUST Framework

The authors propose TRUST (Target-confidence Recourse Using tSeTlin machines), a framework that reformulates recourse as a target-confidence problem.

1. Problem Formulation

Instead of minimizing distance subject to $M(x') \geq 0.5$ , TRUST seeks a counterfactual $x'$ that minimizes the cost $d(x, x')$ subject to a user-defined target confidence $\tau \in (0.5, 1)$ and a tolerance $\epsilon$ :
$\min_{x'} d(x, x') \quad \text{s.t.} \quad |M(x') - \tau| \leq \epsilon$
This formulation generalizes standard CEs (recovered when $\tau = 0.5$ ) and allows for the explicit generation of recourse options at varying confidence levels, enabling a principled trade-off analysis between cost and robustness.

2. Model Instantiation: Probabilistic Tsetlin Machine (PTM)

To instantiate this framework, the authors utilize a Probabilistic Tsetlin Machine (PTM) paired with Bayesian Optimization (BO).

Why PTM? Unlike black-box probabilistic classifiers (e.g., calibrated neural networks) where confidence scores lack direct interpretability, the PTM decomposes predictions into human-interpretable logical clauses with probabilistic activations. This structure allows the model to link feature changes directly to shifts in prediction confidence.
Why Bayesian Optimization? The search space for counterfactuals is non-convex and potentially expensive to evaluate, especially with stochastic models. BO is employed to efficiently search the input space, balancing exploration and exploitation to find candidates matching the target confidence $\tau$ while minimizing distance. Theoretical guarantees under regularity conditions ensure asymptotic optimality.

3. Clause-Level Counterfactual Attribution

A distinct contribution of the TRUST framework is the ability to perform clause-level attribution. When multiple counterfactuals achieve the same target confidence but differ in cost or stability, the PTM structure allows practitioners to trace these differences to specific logical rules.

The framework analyzes the "firing probabilities" of individual clauses.
It identifies whether a counterfactual satisfies rules robustly (deep within the rule's probabilistic boundaries) or fragily (near the edge of a rule's condition).
This provides a mechanistic explanation for why one recourse option is more reliable than another, a capability absent in feature-level explanations from black-box models.

Key Contributions

Target-Confidence Formulation: The paper introduces Eq. (2) as the first CE objective where prediction confidence is a user-specified constraint rather than an emergent property. This shifts the paradigm from "minimal label flip" to "minimal change for a specific risk threshold."
Clause-Level Attribution: By leveraging the PTM, the authors enable a novel explanatory layer that connects feature-level changes to confidence shifts via interpretable logical clauses. This supports the comparison of competing recourse options based on the stability of the underlying decision rules.
Robustness by Design: The framework establishes a practical link between confidence-aware counterfactuals and robustness. By targeting higher confidence levels directly, robustness is achieved by construction (moving deeper into the positive class region) rather than through post-hoc filtering.

Experimental Results

The authors evaluated TRUST on two synthetic datasets (2D and 5D) and two real-world datasets (Iris binary classification and Haberman Survival). They compared TRUST (PTM + BO) against standard gradient-based (Wachter) and sampling-based (GrowingSpheres) baselines from the CARLA library.

Key Findings:

Robustness vs. Cost Trade-off: TRUST allows explicit control over the trade-off. At a lower target confidence ( $\tau=0.50$ ), TRUST produces counterfactuals with minimal distance (comparable to or better than baselines). At a higher target confidence ( $\tau=0.85$ ), TRUST generates counterfactuals that are significantly more robust to noise (achieving 100% robustness on several benchmarks) while maintaining low recourse costs.
Performance Metrics: On the Haberman dataset, TRUST achieved an L2 distance of 0.10 at 0.92 confidence with perfect robustness, outperforming baselines which struggled to maintain high confidence without sacrificing robustness.
Interpretability: Qualitative analysis on the Haberman dataset demonstrated that two counterfactuals satisfying the same logical rule (e.g., "Positive lymph nodes $\leq 4$ ") could have vastly different reliability. TRUST's clause-level analysis revealed that a counterfactual with lymph nodes = 4 was fragile (near the rule boundary), whereas one with lymph nodes = 2 was robust, explaining the difference in confidence stability mechanistically.

Significance and Claims

The paper claims that TRUST provides a confidence-aware and interpretable foundation for algorithmic recourse in high-stakes settings. Its significance lies in:

Shifting the Optimization Objective: Moving from binary label flipping to satisfying user-defined risk thresholds, which aligns better with regulatory and practical decision-making needs (e.g., EU AI Act, GDPR).
Mechanistic Explanation: Unlike prior methods that offer only feature-level changes, TRUST explains why a recourse option is robust or fragile by exposing the stability of the underlying logical rules (clauses).
Practical Utility: It enables decision-makers to choose between recourse options based on a transparent cost-confidence-robustness spectrum, rather than being forced to accept the "cheapest" option which may be unstable.

The authors remain modest regarding limitations, noting that the framework relies on well-calibrated probabilistic predictions, that the current implementation (PTM) has computational overhead compared to gradient-based methods, and that broader validation across larger benchmarks is future work. However, they assert that the proposed framework successfully addresses the gap between theoretical recourse and stable, actionable decision support.