shapiq.approximator.sampling#

This module contains stochastic sampling procedures for coalitions of players.

Classes

CoalitionSampler(n_players, sampling_weights)

The coalition sampler to generate a collection of subsets as a basis for approximation methods.

ShapleySamplingMixin()

Mixin class for the computation of Shapley weights.
class shapiq.approximator.sampling.CoalitionSampler(n_players, sampling_weights, pairing_trick=False, random_state=None)[source]#

Bases: object

The coalition sampler to generate a collection of subsets as a basis for approximation methods.

Sampling is based on a more general variant of [Fumagalli et al. 2023](https://proceedings.neurips.cc/paper_files/paper/2023/hash/264f2e10479c9370972847e96107db7f-Abstract-Conference.html) All variables are stored in the sampler, no objects are returned. The following variables are computed:

  • sampled_coalitions_matrix: A binary matrix that consists of one row for each sampled

    coalition. Each row is a binary vector that indicates the players in the coalition. The matrix is of shape (n_coalitions, n_players).

  • sampled_coalitions_counter: An array with the number of occurrences of the coalitions

    in the sampling process. The array is of shape (n_coalitions,).

  • sampled_coalitions_probability: An array with the coalition probabilities according to the

    sampling procedure (i.e., the sampling weights). The array is of shape (n_coalitions,).

  • coalitions_per_size: An array with the number of sampled coalitions per size (including

    the empty and full set). The array is of shape (n_players + 1,).

  • is_coalition_size_sampled: An array that contains True, if the coalition size was

    sampled and False (computed exactly) otherwise. The array is of shape (n_players + 1,).

  • sampled_coalitions_dict: A dictionary containing all sampled coalitions mapping to their

    number of occurrences. The dictionary is of type dict[tuple[int, …], int].

Parameters:

  • n_players (int) – The number of players in the game.

  • sampling_weights (ndarray) – Sampling for weights for coalition sizes, must be non-negative and at least one >0.

  • pairing_trick (bool) – Samples each coalition jointly with its complement, default is False

  • random_state (Optional[int]) – The random state to use for the sampling process. Defaults to None.

Attributes and Properties:

n: The number of players in the game. n_max_coalitions: The maximum number of possible coalitions. adjusted_sampling_weights: The adjusted sampling weights without zero-weighted coalition

sizes. The array is of shape (n_sizes_to_sample,).

sampled: A flag indicating whether the sampling process has been executed. coalitions_matrix: The binary matrix of sampled coalitions of shape (n_coalitions,

n_players).

coalitions_counter: The number of occurrences of the coalitions. The array is of shape

(n_coalitions,).

coalitions_probability: The coalition probabilities according to the sampling procedure. The

array is of shape (n_coalitions,).

n_coalitions: The number of coalitions that have been sampled.

Examples

>>> sampler = CoalitionSampler(n_players=3, sampling_weights=np.array([1, 0.5, 0.5, 1]))
>>> sampler.sample(5)
>>> print(sampler.coalitions_matrix)
[[False, False, False],
 [False, False, True],
 [True, True, True],
 [True, False, False],
 [False, True, True]]
execute_border_trick(sampling_budget)[source]#

Moves coalition sizes from coalitions_to_sample to coalitions_to_compute, if the expected number of coalitions is higher than the total number of coalitions of that size.

The border trick is based on a more general version of [Fumagalli et al. 2023](https://proceedings.neurips.cc/paper_files/paper/2023/hash/264f2e10479c9370972847e96107db7f-Abstract-Conference.html).

Parameters:

sampling_budget (int) – The number of coalitions to sample

Return type:

int

Returns:

The sampling budget reduced by the number of coalitions in coalitions_to_compute

execute_pairing_trick(sampling_budget, coalition_size, permutation)[source]#

Executes the pairing-trick for a sampling budget and coalition sizes.

The pairing-trick is based on the idea of [Covert and Lee 2021](https://proceedings.mlr.press/v130/covert21a.html) and pairs each coalition with its complement.

Works similar as the initial coalition, but throws a warning, if the subset is not allowed

for sampling.

Parameters:

  • sampling_budget (int) – The currently remaining sampling budget.

  • coalition_size (int) – The coalition size of the coalition that should be paired.

  • permutation – The permutation from which the coalition was drawn.

Return type:

int

Returns:

The remaining sampling budget after the pairing-trick.

sample(sampling_budget)[source]#

Samples distinct coalitions according to the specified budget.

Parameters:

sampling_budget (int) – The budget for the approximation (i.e., the number of distinct coalitions to sample/evaluate).

Raises:

UserWarning – If the sampling budget is higher than the maximum number of coalitions.

Return type:

None

property coalitions_counter: ndarray#

Returns the number of occurrences of the coalitions

Returns:

A copy of the sampled coalitions counter of shape (n_coalitions,).

property coalitions_matrix: ndarray#

Returns the binary matrix of sampled coalitions.

Returns:

A copy of the sampled coalitions matrix as a binary matrix of shape (n_coalitions,

n_players).

property coalitions_probability: ndarray#

Returns the coalition probabilities according to the sampling procedure.

Returns:

A copy of the sampled coalitions probabilities of shape (n_coalitions,).

property n_coalitions: int#

Returns the number of coalitions that have been sampled.

Returns:

The number of coalitions that have been sampled.

class shapiq.approximator.sampling.ShapleySamplingMixin[source]#

Bases: ABC

Mixin class for the computation of Shapley weights.

Provides the common functionality for regression-based approximators like RegressionFSI. The class offers computation of Shapley weights and the corresponding sampling weights for the KernelSHAP-like estimation approaches.