shapiq.utils.split_subsets_budget¶

shapiq.utils.split_subsets_budget(order, n, budget, sampling_weights)[source]¶

Determines which subset sizes can be computed explicitly and which sizes need to be sampled.

Given a computational budget, determines the complete subsets that can be computed explicitly and the corresponding incomplete subsets that need to be estimated via sampling.

Parameters:

order (int) – interaction order.
n (int) – number of players.
budget (int) – total allowed budget for the computation.
sampling_weights (ndarray) – weight vector of the sampling distribution in shape (n + 1,). The first and last element constituting the empty and full subsets are not used.

Return type:

tuple[list, list, int]

Returns:

complete subsets, incomplete subsets, remaining budget

Examples

>>> split_subsets_budget(order=1, n=6, budget=100, sampling_weights=np.ones(shape=(6,)))
([1, 5, 2, 4, 3], [], 38)

>>> split_subsets_budget(order=1, n=6, budget=60, sampling_weights=np.ones(shape=(6,)))
([1, 5, 2, 4], [3], 18)

>>> split_subsets_budget(order=1, n=6, budget=100, sampling_weights=np.zeros(shape=(6,)))
([], [1, 2, 3, 4, 5], 100)