Show & Tell 39.1 — FeatureAttributor: Deep Dive into SHAP, LIME & Integrated Gradients

[web3guru888]

FeatureAttributor — Algorithm Deep Dive

SHAP (SHapley Additive exPlanations)

SHAP unifies six existing feature attribution methods under the Shapley value framework from cooperative game theory (Lundberg & Lee, 2017).

Core Algorithm — KernelSHAP:

Algorithm: KernelSHAP
Input: model f, instance x, background data D, num_samples K
Output: Shapley values φ

1. Generate K coalition vectors z ∈ {0,1}^M
2. For each z_k:
   a. Map z_k → x'_k (replace masked features with background values)
   b. Compute f(x'_k)
   c. Compute SHAP kernel weight: π(z) = (M-1) / (C(M,|z|) · |z| · (M-|z|))
3. Solve weighted least squares:
   φ = argmin_g Σ_k π(z_k) · [f(x'_k) - g(z_k)]²
   where g(z) = φ₀ + Σᵢ φᵢzᵢ
4. Return φ (satisfies efficiency: Σφᵢ = f(x) - E[f(x)])

TreeSHAP (O(TLD) exact computation):

For tree ensembles, exact Shapley values can be computed in polynomial time by tracking decision paths through each tree, extending the algorithm of Saabas (2014) with proper conditioning.

LIME (Local Interpretable Model-agnostic Explanations)

Algorithm: LIME
Input: model f, instance x, num_samples N, kernel_width σ
Output: sparse linear model coefficients w

1. Generate N perturbed samples x'_i ~ N(x, σ²)
2. Compute f(x'_i) for each perturbation
3. Compute proximity weights: πₓ(x'_i) = exp(-d(x, x'_i)² / σ²)
4. Fit sparse weighted linear model:
   w = argmin_w Σᵢ πₓ(x'_i) · L(f(x'_i), w·x'_i) + Ω(w)
   where Ω is L1 regularization (Lasso)
5. Return top-K features with largest |wᵢ|

Integrated Gradients

Algorithm: Integrated Gradients (Sundararajan et al. 2017)
Input: model f, instance x, baseline x'
Output: attributions a

1. Construct interpolation path: γ(α) = x' + α(x - x'), α ∈ [0,1]
2. Compute path integral via Riemann sum (m steps):
   aᵢ = (xᵢ - x'ᵢ) × (1/m) Σₖ₌₁ᵐ ∂f(γ(k/m))/∂xᵢ
3. Verify completeness axiom: Σᵢ aᵢ ≈ f(x) - f(x')

Integration with Existing Phases

• Phase 20 (Reasoning): Attribute importance to features driving LogicalInferenceEngine conclusions
• Phase 23 (Decision Intelligence): Explain UncertaintyQuantifier risk assessments
• Phase 38 (Federated Learning): Federated SHAP — compute local attributions without sharing raw data

Pseudocode: Attribution Aggregator

def aggregate_attributions(results: dict[str, AttributionResult]) -> FeatureRanking:
    """Ensemble multiple attribution methods via rank correlation."""
    rankings = {}
    for method, result in results.items():
        ranked_indices = sorted(
            range(len(result.attribution_scores)),
            key=lambda i: abs(result.attribution_scores[i]),
            reverse=True
        )
        rankings[method] = ranked_indices
    
    # Reciprocal Rank Fusion (RRF)
    rrf_scores = defaultdict(float)
    k = 60  # RRF constant
    for method, ranking in rankings.items():
        for rank, feature_idx in enumerate(ranking):
            rrf_scores[feature_idx] += 1.0 / (k + rank)
    
    sorted_features = sorted(rrf_scores, key=rrf_scores.get, reverse=True)
    return FeatureRanking(
        feature_indices=tuple(sorted_features),
        importance_scores=tuple(rrf_scores[f] for f in sorted_features),
        method="rrf_ensemble"
    )

See issue #788 for full spec.