18697371034

Committed 21 Oct 2025 08:54PM UTC coverage: 92.858% (+0.06%) from 92.799%

Build # 18697371034

Build Type

Pull #431

github

Committed by

web-flow

Commit Message

Merge 435a34452 into ac5614648

Pull Request Pull Request #431: Product kernel explainer

Run Details

186 of 210 new or added lines in 13 files covered. (88.57%)

22 existing lines in 5 files now uncovered.

5214 of 5615 relevant lines covered (92.86%)

0.93 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.18

/src/shapiq/explainer/product_kernel/product_kernel.py

"""Implementation of ProductKernelSHAPIQ for computing Shapley values."""

from __future__ import annotations

import math
from typing import TYPE_CHECKING, Literal

import numpy as np
from sklearn.metrics.pairwise import rbf_kernel

if TYPE_CHECKING:
    from shapiq.explainer.product_kernel.base import ProductKernelModel

ProductKernelSHAPIQIndices = Literal["SV"]


class ProductKernelComputer:
    """The Product Kernel Computer for product kernel-based models.

    This class computes the Shapley values for product kernel-based models.
    The functions are obtained from the PKeX-Shapley LocalExplainer. https://github.com/Majeed7/RKHS-ExactSHAP/blob/main/explainer/LocalExplainer.py#L3

    References:
        -- [pkex-shapley] Majid Mohammadi and Siu Lun Chau, Krikamol Muandet. (2025). Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods. https://arxiv.org/abs/2505.16516

    Attributes:
        model: The product kernel model to explain.
        kernel_type: The type of kernel to be used. Defaults to ``"rbf"``.
        max_order: The maximum interaction order to be computed. Defaults to ``1``.
        index: The type of interaction to be computed. Defaults to ``"SV"``.
        d: The number of features in the model.

    """

    def __init__(
        self,
        model: ProductKernelModel,
        *,
        max_order: int = 1,
        index: ProductKernelSHAPIQIndices = "SV",
    ) -> None:
        """Initializes the ProductKernelSHAPIQ explainer.

        Args:
            model: A product kernel-based model to explain.
            max_order: The maximum interaction order to be computed. Defaults to ``1``.
            index: The type of interaction to be computed. Defaults to ``"SV"``.

        Returns:
            None.
        """
        self.model = model
        self.kernel_type = self.model.kernel_type
        self.max_order = max_order
        self.index = index
        self.d = model.d

    def precompute_weights(self, num_features: int) -> np.ndarray:
        """Precompute model weights (mu coefficients) for computing Shapley values.

        Args:
            num_features: Number of features.

        Returns:
            List of precomputed mu coefficients.
        """
        unnormalized_factors = [
            (math.factorial(q) * math.factorial(num_features - q - 1)) for q in range(num_features)
        ]

        return np.array(unnormalized_factors) / math.factorial(num_features)

    def compute_elementary_symmetric_polynomials(self, kernel_vectors: list) -> list:
        """Compute elementary symmetric polynomials using a dynamic programming approach.

        Args:
            kernel_vectors: List of kernel vectors (1D arrays).

        Returns:
            List of elementary symmetric polynomials.
        """
        # Initialize with e_0 = 1
        max_abs_k = max(np.max(np.abs(k)) for k in kernel_vectors) or 1.0
        scaled_kernel = [k / max_abs_k for k in kernel_vectors]

        # Initialize polynomial coefficients: P_0(x) = 1
        e = [np.ones_like(scaled_kernel[0], dtype=np.float64)]

        for k in scaled_kernel:
            # Prepend and append zeros to handle polynomial multiplication (x - k)
            new_e = [np.zeros_like(e[0])] * (len(e) + 1)
            # new_e[0] corresponds to the constant term after multiplying by (x - k)
            new_e[0] = -k * e[0]
            # Compute the rest of the terms
            for i in range(1, len(e)):
                new_e[i] = e[i - 1] - k * e[i]
            # The highest degree term is x^{len(e)}, coefficient is e[-1] (which is 1 initially)
            new_e[len(e)] = e[-1].copy()
            e = new_e

        # Extract elementary symmetric polynomials from the coefficients
        n = len(scaled_kernel)
        elementary = [np.ones_like(e[0])]  # e_0 = 1
        for r in range(1, n + 1):
            sign = (-1) ** r
            elementary_r = sign * e[n - r] * (max_abs_k**r)
            elementary.append(elementary_r)

        return elementary

    def compute_shapley_value(self, kernel_vectors: list, feature_index: int) -> float:
        """Compute the Shapley value for a specific feature of an instance.

        Args:
            kernel_vectors: List of kernel vectors (1D arrays).
            feature_index: Index of the feature.

        Returns:
           Shapley value for the specified feature.
        """
        alpha = self.model.alpha
        cZ_minus_j = [kernel_vectors[i] for i in range(self.model.d) if i != feature_index]
        e_polynomials = self.compute_elementary_symmetric_polynomials(cZ_minus_j)
        mu_coefficients = self.precompute_weights(self.model.d)

        # Compute kernel vector for the chosen feature
        k_j = kernel_vectors[feature_index]
        onevec = np.ones_like(k_j)

        # Compute the Shapley value
        result = np.zeros_like(k_j)
        for q in range(self.model.d):
            if q < len(e_polynomials):
                result += mu_coefficients[q] * e_polynomials[q]

        shapley_value = alpha.dot((k_j - onevec) * result)

        return shapley_value.item()

    def compute_kernel_vectors(self, X: np.ndarray, x: np.ndarray) -> list:
        """Compute kernel vectors for a given dataset X and instance x.

        Args:
            X: The dataset (2D array) used to train the model.
            x: The instance (1D array) for which to compute Shapley values.

        Returns:
            List of kernel vectors corresponding to each feature. Length = number of features.
        """
        # Initialize the kernel matrix
        kernel_vectors = []

        # For each sample and each feature, compute k(x_i^j, x^j)
        for i in range(self.d):
            kernel_vec = rbf_kernel(
                X[:, i].reshape(-1, 1),
                x[..., np.newaxis][i].reshape(1, -1),
                gamma=self.model.gamma,
            )
            kernel_vectors.append(kernel_vec.squeeze())

        return kernel_vectors

1	"""Implementation of ProductKernelSHAPIQ for computing Shapley values."""
2
3	from __future__ import annotations	1✔
4
5	import math	1✔
6	from typing import TYPE_CHECKING, Literal	1✔
7
8	import numpy as np	1✔
9	from sklearn.metrics.pairwise import rbf_kernel	1✔
10
11	if TYPE_CHECKING:	1✔
NEW 12	from shapiq.explainer.product_kernel.base import ProductKernelModel	×
13
14	ProductKernelSHAPIQIndices = Literal["SV"]	1✔
15
16
17	class ProductKernelComputer:	1✔
18	"""The Product Kernel Computer for product kernel-based models.
19
20	This class computes the Shapley values for product kernel-based models.
21	The functions are obtained from the PKeX-Shapley LocalExplainer. https://github.com/Majeed7/RKHS-ExactSHAP/blob/main/explainer/LocalExplainer.py#L3
22
23	References:
24	-- [pkex-shapley] Majid Mohammadi and Siu Lun Chau, Krikamol Muandet. (2025). Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods. https://arxiv.org/abs/2505.16516
25
26	Attributes:
27	model: The product kernel model to explain.
28	kernel_type: The type of kernel to be used. Defaults to ``"rbf"``.
29	max_order: The maximum interaction order to be computed. Defaults to ``1``.
30	index: The type of interaction to be computed. Defaults to ``"SV"``.
31	d: The number of features in the model.
32
33	"""
34
35	def __init__(	1✔
36	self,
37	model: ProductKernelModel,
38	*,
39	max_order: int = 1,
40	index: ProductKernelSHAPIQIndices = "SV",
41	) -> None:
42	"""Initializes the ProductKernelSHAPIQ explainer.
43
44	Args:
45	model: A product kernel-based model to explain.
46	max_order: The maximum interaction order to be computed. Defaults to ``1``.
47	index: The type of interaction to be computed. Defaults to ``"SV"``.
48
49	Returns:
50	None.
51	"""
52	self.model = model	1✔
53	self.kernel_type = self.model.kernel_type	1✔
54	self.max_order = max_order	1✔
55	self.index = index	1✔
56	self.d = model.d	1✔
57
58	def precompute_weights(self, num_features: int) -> np.ndarray:	1✔
59	"""Precompute model weights (mu coefficients) for computing Shapley values.
60
61	Args:
62	num_features: Number of features.
63
64	Returns:
65	List of precomputed mu coefficients.
66	"""
67	unnormalized_factors = [	1✔
68	(math.factorial(q) * math.factorial(num_features - q - 1)) for q in range(num_features)
69	]
70
71	return np.array(unnormalized_factors) / math.factorial(num_features)	1✔
72
73	def compute_elementary_symmetric_polynomials(self, kernel_vectors: list) -> list:	1✔
74	"""Compute elementary symmetric polynomials using a dynamic programming approach.
75
76	Args:
77	kernel_vectors: List of kernel vectors (1D arrays).
78
79	Returns:
80	List of elementary symmetric polynomials.
81	"""
82	# Initialize with e_0 = 1
83	max_abs_k = max(np.max(np.abs(k)) for k in kernel_vectors) or 1.0	1✔
84	scaled_kernel = [k / max_abs_k for k in kernel_vectors]	1✔
85
86	# Initialize polynomial coefficients: P_0(x) = 1
87	e = [np.ones_like(scaled_kernel[0], dtype=np.float64)]	1✔
88
89	for k in scaled_kernel:	1✔
90	# Prepend and append zeros to handle polynomial multiplication (x - k)
91	new_e = [np.zeros_like(e[0])] * (len(e) + 1)	1✔
92	# new_e[0] corresponds to the constant term after multiplying by (x - k)
93	new_e[0] = -k * e[0]	1✔
94	# Compute the rest of the terms
95	for i in range(1, len(e)):	1✔
96	new_e[i] = e[i - 1] - k * e[i]	1✔
97	# The highest degree term is x^{len(e)}, coefficient is e[-1] (which is 1 initially)
98	new_e[len(e)] = e[-1].copy()	1✔
99	e = new_e	1✔
100
101	# Extract elementary symmetric polynomials from the coefficients
102	n = len(scaled_kernel)	1✔
103	elementary = [np.ones_like(e[0])] # e_0 = 1	1✔
104	for r in range(1, n + 1):	1✔
105	sign = (-1) ** r	1✔
106	elementary_r = sign * e[n - r] * (max_abs_k**r)	1✔
107	elementary.append(elementary_r)	1✔
108
109	return elementary	1✔
110
111	def compute_shapley_value(self, kernel_vectors: list, feature_index: int) -> float:	1✔
112	"""Compute the Shapley value for a specific feature of an instance.
113
114	Args:
115	kernel_vectors: List of kernel vectors (1D arrays).
116	feature_index: Index of the feature.
117
118	Returns:
119	Shapley value for the specified feature.
120	"""
121	alpha = self.model.alpha	1✔
122	cZ_minus_j = [kernel_vectors[i] for i in range(self.model.d) if i != feature_index]	1✔
123	e_polynomials = self.compute_elementary_symmetric_polynomials(cZ_minus_j)	1✔
124	mu_coefficients = self.precompute_weights(self.model.d)	1✔
125
126	# Compute kernel vector for the chosen feature
127	k_j = kernel_vectors[feature_index]	1✔
128	onevec = np.ones_like(k_j)	1✔
129
130	# Compute the Shapley value
131	result = np.zeros_like(k_j)	1✔
132	for q in range(self.model.d):	1✔
133	if q < len(e_polynomials):	1✔
134	result += mu_coefficients[q] * e_polynomials[q]	1✔
135
136	shapley_value = alpha.dot((k_j - onevec) * result)	1✔
137
138	return shapley_value.item()	1✔
139
140	def compute_kernel_vectors(self, X: np.ndarray, x: np.ndarray) -> list:	1✔
141	"""Compute kernel vectors for a given dataset X and instance x.
142
143	Args:
144	X: The dataset (2D array) used to train the model.
145	x: The instance (1D array) for which to compute Shapley values.
146
147	Returns:
148	List of kernel vectors corresponding to each feature. Length = number of features.
149	"""
150	# Initialize the kernel matrix
151	kernel_vectors = []	1✔
152
153	# For each sample and each feature, compute k(x_i^j, x^j)
154	for i in range(self.d):	1✔
155	kernel_vec = rbf_kernel(	1✔
156	X[:, i].reshape(-1, 1),
157	x[..., np.newaxis][i].reshape(1, -1),
158	gamma=self.model.gamma,
159	)
160	kernel_vectors.append(kernel_vec.squeeze())	1✔
161
162	return kernel_vectors	1✔

mmschlk / shapiq / 18697371034

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous