shapiq.approximator.OddSHAP¶

class shapiq.approximator.OddSHAP(n, *, sampling_weights=None, random_state=None, interaction_factor=10, tree_params=None, **kwargs)[source]¶

Bases: Approximator

OddSHAP approximator for first-order Shapley values (Fumagalli et al., 2026).

Note

Where Algorithm 1 of the paper falls back to TreeSHAP for budgets below n * interaction_factor, this implementation expands the selection of active terms also to individuals, allowing a minimum budget of interaction_factor. Below that, it raises ValueError (no silent downgrade to another estimator), unless the budget already covers the full coalition space (budget >= 2**n). It therefore does not reproduce the low-budget, high-dimension regime of the paper’s Figure 2.

The active support’s candidate budget (ceil(budget / interaction_factor)) is shared between individuals and higher-order odd interactions: the most relevant individuals (ranked by absolute Fourier coefficient, all n of them always considered) are screened first, and only the remaining candidate budget is spent on higher-order odd interactions. Unlike the paper, low budgets can therefore leave some individuals out of the active support entirely (their Shapley value is then estimated as exactly 0).

Initialize the OddSHAP approximator.

tree_params entries override the surrogate defaults — including random_state, n_jobs, and verbose; max_depth defaults to 10 (the paper’s configuration) unless overridden.

Parameters:

  • n (int)

  • sampling_weights (np.ndarray | None)

  • random_state (int | None)

  • interaction_factor (int)

  • tree_params (dict[str, Any] | None)

  • kwargs (Any)

approximate(budget, game, **kwargs)[source]¶

Approximate first-order Shapley values.

The method samples coalitions, evaluates the game, detects sparse odd interactions, solves the constrained odd Fourier regression problem, and transforms the fitted coefficients into Shapley values.

Parameters:

  • budget (int) – Number of game evaluations available to the approximator.

  • game (Game | Callable[[ndarray], ndarray]) – Game or callable that evaluates coalition matrices.

  • **kwargs (Any) – Additional keyword arguments kept for API compatibility.

Return type:

InteractionValues

Returns:

Estimated first-order Shapley values.

Raises:

  • ValueError – If budget < min(interaction_factor, 2**n), i.e. the budget is below the eta-based minimum and does not cover the full coalition space either. Algorithm 1 of the paper falls back to TreeSHAP in this regime; this implementation deliberately raises instead, so an under-budgeted call never silently returns a different estimator’s values.

  • RuntimeError – If the sampled coalitions do not contain the empty or grand coalition.

valid_indices: tuple[str, ...] = ('SV',)¶

The valid indices for the base approximator.