Decision Boundary

In an n-dimensional feature space, the decision boundary is an (n-1)-dimensional manifold. For a linear classifier, this is a simple hyperplane defined by w·x + b = 0. For neural networks, the boundary is a highly non-linear, piecewise surface whose complexity grows with depth and width. The topological complexity directly impacts counterfactual search difficulty—smooth, convex boundaries yield easy recourse, while jagged, disconnected regions trap search algorithms in local minima.

The signed distance from an instance to the decision boundary quantifies the model's confidence and the effort required for recourse. For a linear SVM, this is |w·x + b| / ||w||. Counterfactual algorithms like Growing Spheres exploit this by expanding a hypersphere until it intersects the boundary. Key metrics:

• L1 distance: Encourages sparse feature changes
• L2 distance: Penalizes large individual perturbations
• Mahalanobis distance: Accounts for feature covariance, generating more plausible counterfactuals by following the data manifold

Linear boundaries (logistic regression, linear SVM) partition space with a single flat hyperplane. Counterfactuals are trivially found via orthogonal projection. Non-linear boundaries (kernel SVM, neural networks) create complex, often disconnected regions. A neural network with ReLU activations produces a piecewise linear boundary—the feature space is carved into convex polytopes, each assigned to a class. This fragmentation means multiple valid counterfactuals may exist, but some may lie in low-density, implausible regions far from the training data manifold.

For 1-nearest neighbor classifiers, the decision boundary is exactly the Voronoi diagram of the training points. Each training instance defines a convex cell; the boundary is the union of cell edges. This provides intuition for more complex models: the boundary is fundamentally a partition of space into regions of influence. Counterfactual search in this framework is equivalent to finding the nearest training point of the target class—a discrete optimization problem that guarantees validity but not necessarily proximity or plausibility.

A counterfactual is valid if and only if it lies on the opposite side of the decision boundary from the original instance. However, validity alone is insufficient. The counterfactual must also satisfy:

• Feasibility constraints: Immutable features (age, birthplace) must remain unchanged
• Plausibility: The point must lie in a high-density region of P(X)
• Robustness: A small retraining of the model should not invalidate the counterfactual Algorithms that ignore the boundary's local geometry often generate adversarial examples rather than actionable recourse.

For differentiable models, the gradient of the loss with respect to the input points directly toward the decision boundary. Gradient-based counterfactual methods iteratively update x' = x - η · ∇_x L(f(x'), y_target) until the prediction flips. This follows the path of steepest descent in the model's output space. However, this naive approach often produces out-of-distribution points. Regularization terms—penalizing distance from the original point or encouraging proximity to the training manifold—are essential to keep the trajectory crossing the boundary at a plausible location.

The metric quantifying the minimal distance between the original input and the generated counterfactual. It operationalizes the search for the nearest point on the opposite side of the decision boundary.

• Typically measured using L1 (Manhattan) or L2 (Euclidean) norms
• Minimizing proximity ensures the explanation is as close to reality as possible
• A counterfactual with high proximity may be sparse but not necessarily plausible

A model-specific technique that uses the gradient of the loss function to iteratively push the input across the decision boundary. It directly navigates the model's internal surface.

• Minimizes a composite loss: prediction loss + distance penalty
• Requires a differentiable model to compute the gradient with respect to the input
• Can get stuck in local minima, failing to find the true nearest boundary crossing

A counterfactual that lies within the high-density region of the training data distribution, not just across the decision boundary. This prevents generating adversarial artifacts.

• Uses Mahalanobis distance instead of Euclidean to respect feature correlations
• Ensures the explanation is realistic and believable to a human
• A plausible point on the boundary is one that looks like a real data instance

The binary evaluation metric that verifies whether a generated instance has successfully crossed the decision boundary. It is the primary pass/fail check.

• Defined as: f(x_cf) == target_class
• A valid counterfactual must flip the prediction to the predefined desired outcome
• Validity is necessary but not sufficient; the explanation must also be actionable

The property that a counterfactual remains valid even after the decision boundary shifts due to model retraining. A robust explanation crosses a stable region of the boundary.

• Addresses the problem of "flipping back" after a minor model update
• Requires the counterfactual to land deep inside the target class, not just on the edge
• Critical for building trust in high-stakes automated decision systems