shapiq.approximator.LeverageSHAP¶

class shapiq.approximator.LeverageSHAP(n, *, pairing_trick=True, sampling_weights=None, random_state=None, deterministic_counts=True, **kwargs)[source]¶

Bases: Regression[Literal[‘SV’]]

Leverage SHAP approximator for Shapley values.

Leverage SHAP (Musco and Witter, 2025 Musco and Witter [2025]) recovers Shapley values as the solution of a weighted least-squares problem over sampled coalitions, like KernelSHAP, but samples coalitions proportional to their statistical leverage scores, which have the closed form l_z = 1/C(n, ||z||) (Lemma 3.2). Implementation of Algorithm 1:

For the deterministic default, normalize the budget to an even number without exceeding it. Solve for the oversampling parameter c so that m - 2 = sum_{s=1}^{n-1} min(C(n, s), 2c) (Eq. 12); two evaluations are reserved for the empty and grand coalitions.
Draw coalition pairs (z, z̄) without replacement (Algorithm 2). By default (deterministic_counts=True) each size’s pair count is fixed to the expectation of the Binomial draw, largest-remainder rounded so the total is exact – stratification in the spirit of SVARM Kolpaczki et al. [2024]; with deterministic_counts=False it is drawn at random as Algorithm 2 states. Sizes whose layer fits within 2c are enumerated exhaustively.
Reweight each row by the inverse of its inclusion probability. For the deterministic default this probability is the realized per-size count divided by C(n, s); for the Binomial variant it is min(1, 2c * l_z).
Project out the efficiency constraint (Lemma 3.1), solve by weighted least squares, and add the efficiency offset back.

Note

The deterministic default follows the fixed-per-size design used by the paper’s released implementation and reported experiments. To preserve shapiq’s hard budget ceiling, an odd budget is rounded down rather than up as in that implementation; largest-remainder ties can also select a different size. The evaluation count is exactly 2 + 2 * ((min(budget, 2**n) - 2) // 2). The paper’s accuracy theorem is proved for the Binomial deterministic_counts=False variant only (Musco and Witter, 2025, end of Sec. 4).

Example

>>> from shapiq.approximator import LeverageSHAP
>>> from shapiq_games.synthetic import DummyGame
>>> n = 5
>>> game = DummyGame(n=n, interaction=(1, 2))
>>> approximator = LeverageSHAP(n=n, random_state=42)
>>> sv_estimates = approximator.approximate(budget=100, game=game)
>>> print(sv_estimates.values)
[0.  0.2 0.7 0.7 0.2 0.2]