Accelerating the computation of Shapley effects for datasets with many observations

Shapley effects have gained widespread recognition as a variable importance measure, finding applications across various sectors. They are based on the Shapley value from game theory literature [23], used as an attribution method. Considering a team of players generating a value, the Shapley value assigns to each player their fair contribution. If one associates players with input variables (or risk factors) of a model and specifies a total value to be distributed among the variables, the Shapley value allocates this quantity. This framework is employed by [8] to identify the most important variables in variable annuity models. In the context of computer experiments, Owen [16] suggests to adopt the variance of the quantity of interest as the value to distribute among variables using the Shapley value, called in this case Shapley effects [25]. Shapley effects are a variable importance measure and enjoy desirable properties. For example, they remain well-defined even in the case of dependent variables, differently from other variance-based importance indices [17, 25]. Plischke et al. [18] introduce a method to compute Shapley effects based on the concept of Moebius inverse, while Rabitti and Borgonovo [19] apply Shapley effects to identify the most important risk factors in annuity models with dependent mortality and interest rate risks. In the dynamic landscape of the insurance industry, Shapley effects can enhance risk management: distributing variance among risk factors, they enable ranking and prioritization of risk factors and aid the interpretation of machine learning models for insurance claims.

An open research area on Shapley effects is their statistical estimation. Recently, Mase et al. [11] proposed a strategy to estimate Shapley effects directly from a given sample using the concept of cohorts of similar observations. Vallarino et al. [26] combined this idea of cohorts with the Moebius inverse approach and demonstrated that constructing a rating system using Shapley effects leads to more homogeneous risk classes. However, computing the similarity cohorts requires processing all possible observations, making it computationally demanding for datasets with a large number of observations, which is typical in the context of “big data”. This encompasses structured, unstructured, and semi-structured data commonly encountered in various insurance fields, such as analyzing information from telematics and usage-based insurance for computing insurance premiums, detecting insurance fraud, automatically diagnosing diseases from images, managing crop insurance, monitoring weather conditions, understanding variable annuity products, etc.

In this work, we propose an approach to address this computational issue by selecting “representative” observations from the dataset, rather than considering all of them. To achieve this, we adopt a strategy inspired by [3‐5, 7], who employed experimental designs and clustering techniques to identify representative policyholders in extensive portfolios of variable annuities. Specifically, we explore the application of the Latin hypercube design [10, 13], the conditional Latin hypercube design [14] and the hierarchical k-means algorithm [15]. Using the observations selected through these three methods, we compute the Shapley effects employing the algorithm proposed by [26]. This approach is then applied to the well-known French claim frequency dataset, demonstrating a substantial reduction in computational time, with only a limited loss in the accuracy of the Shapley effects estimate.

The subsequent sections of this paper are organized as follows. Section 2 provides an exposition on Shapley effects and their computation. Section 3 presents the Latin hypercube, the conditional Latin hypercube, and the hierarchical k-means algorithm. Section 4 outlines the application of the proposed strategy, highlighting its implementation on the French Motor Third Party Liability (MTPL) dataset. Finally, Sect. 5 concludes the work, summarizing the key findings and implications.

The Shapley value [23] is an attribution method originating from game theory. Its purpose is to allocate the total value generated by a coalition of players into the contribution of each individual player in the coalition.

Let \(\phi _j\) denote the Shapley value of the j-th player. Consider a set of players \(K = \{1,2, \dots ,k\}\) participating to a game. We denote with \(u\subseteq K\) any possible sub-coalition of players and \(\text {val}:2^{K} \rightarrow \mathbb {R}\) as the value function of the game, with \(\text {val}(\emptyset ) = 0\). The value generated by players in the subset u is \(\text {val}(u)\), and the total value of the game to be allocated is \(\text {val}(K)\).

The Shapley value enjoys the following desirable properties as an attribution method: The interpretation of the properties is as follows: Efficiency ensures that the total payoff is distributed among all players. Symmetry states that if two players contribute the same value when joining the same coalition for all coalitions, their Shapley values are equal. The Dummy property requires that a player who contributes nothing to any coalition receives a Shapley value of zero. Additivity implies that if two games are combined, the Shapley value for any player is the sum of the Shapley values that the player would receive in the individual games.

Shapley [23] proves that the unique representation of \(\phi _{j}\) value satisfying these four properties iswhere |u| denotes the cardinality of the subset u. The Shapley value is widely used to assess the sensitivity of a quantity of interest Y in terms of variations of variables \(\textbf{X}=(X_1,X_2,\ldots ,X_k)\). Owen [16] suggests using the Sobol’ index as the value functionwhere \(\textbf{X}_u\) denotes the sub-vector of \(\textbf{X}\) whose components are indexed by u, \(\mathbb {E}(\cdot )\) denotes the expectation and \(\mathbb {V}(\cdot )\) the variance. The Shapley values obtained with this value function are called Shapley effects [25]. With this chosen value function, Shapley effects have become very popular because they are always non-negative (i.e. \(\phi _j \ge 0\) for any j) and they sum up to unity because the value function in (2) has been normalized by the variance of Y (i.e. \(\sum _{j=1}^n \phi _j=1\)) since \(\mathbb {V}[E(Y|\textbf{X})]=\mathbb {V}[Y]\).¹ The Shapley effects allocate the variance of Y among variables, which receive a non-negative fraction of it. The Shapley effect \(\phi _j\) is then interpretable as the fraction of the variance that the j-th variable explains. The higher the variance this variable explains, the more important it is. Moreover, Shapley effects are well-defined under any dependence structure among the variables \(\textbf{X}\) [25].

While Shapley effects enjoy the appealing properties mentioned above, their computation is an open problem. Song et al. [25] propose a double loop Monte Carlo, while Plischke et al. [18] suggest an algorithm based on the Moebius inverse of the value function, reducing the number of evaluations from \(k!\cdot k\) to \(2^k-1\). Denote with \(\text {mob}(u)\) the Moebius inverse of the value function \(\text {val}( u)\), that is \(\text {mob}(u)=\sum _{v\subset u}(-1)^{|u-v|} \text {val}(v)\). Equivalently to Eq. (1), Shapley values can be written as:To compute the Shapley effect \(\phi _j\) from given data, Mase et al. [11, 12] introduce the notion of cohorts of similar observations. Assume we have at hand a dataset of observations \(\{(y_i,\textbf{x}_i)\}_{i=1}^n\), where \(y_i\) and \(\textbf{x}_i\) represent the i-th realization of Y and \(\textbf{X}\) respectively. The cohorts are defined as subsets of observations sharing values of variables similar to those of a target observation denoted by t.

Let \(x_{ij}\) be the value of the j-th variable for the i-th observation (with \(j=1, \dots ,k\) and \(i=1, \dots , n\)), and \(x_{tj}\) be the target value for the selected variable j. A similarity function \(z_{tj}\) is constructed for each variable j; for continuous variables, similarity is defined using a measure of relative distance. A possible similarity function is given by:where \(\delta _{j}\) is the specified distance. The cohort of t with respect to variables in u is defined as:This set contains subjects similar to the target subject t for all variables \(j \in u\). By construction, \(C_{t,u}\) is never empty since it includes at least the target observation \(x_t\).

Using cohorts, Mase et al. [11] estimate the conditional expectation in (2) by considering cohort means:where \(|C_{t,u}|\) is the cardinality. The cohort average \(\bar{y}_{t,u}\) is an estimate of the conditional mean for the target \(\mathbb {E}[Y| \textbf{X}_{t,u}]\). With each observation having probability \(n^{-1}\), an estimate of the value function is obtained:where \(\bar{y}\) and \(\hat{\sigma }^2\) are an estimate of the mean and of the variance of Y respectively. Shapley effects are then obtained using Eq. (3). This algorithm is contained in the Matlab function highercohortshapmob.m available at https://​github.​com/​giovanni-rabitti/​ratingsystemshap​ley.

To find the complexity of this algorithm, we note that for each target subject t, the algorithm runs a loop over \(n\) observations, with each iteration having a complexity of \(O(n)\). This results in a total complexity per main loop iteration of \(O(n^2)\). Given that the outer loop runs \(2^k\) times (i.e. all possible coalition values are evaluated), the overall algorithmic complexity becomes \(O(2^k \cdot n^2)\). The computational complexity of the algorithm exhibits a quadratic growth with respect to \( n \) (the number of observations) and an exponential growth with respect to \( k \) (the number of variables). When a reduced sample of size \( n_0 \) is used instead of the full sample \( n \), the theoretical factor by which the computational complexity is reduced can be expressed as the ratio:This ratio indicates the reduction in computational complexity when the number of observations is decreased from \( n \) to \( n_0 \). Hence, to reduce the complexity, we want to reduce the number of observations n without significantly sacrificing the accuracy of the estimated Sobol’ indices in Eq. (2). This can be possible selecting representative observations from the sample.

To select the \(n_0\) representative observations, we follow the presentation of [4, 6]. The codes are implemented in \(\texttt {R}\), are described in [6] and are publicly available at https://​www2.​math.​uconn.​edu/​~gan/​software.​html. All computations were conducted using a standard laptop equipped with 8GB of RAM.

We apply the algorithms to the French MTPL dataset, which comprises 678,013 insurance policies. This dataset includes for every policyholder the number of claims, policy exposure and 9 explanatory variables: VehPower (the power of the car), VehAge (the vehicle age), DrivAge (the driver’s age), BonusMalus (the bonus/malus rating of the policyholder), VehBrand (the brand of the car), VehGas (the car’s fuel type), Area (the density-rating of the community that the car driver lives in), Density (the density of inhabitants of the city where the car driver lives in), Region (the policy region in France). A detailed exploratory data analysis of this dataset is available in the tutorials by [22, 2] for the Swiss Association of Actuaries (SAA), and the book of [27]. The rebalancing of the dataset by randomly subsampling observations without claims (due to the imbalance in the dataset, which contains more policies without claims) was undertaken for illustrative purposes² and to create a balanced dataset of 68,120 observations, considered as our benchmark data. This operation is a common practice in data analysis [28].

In our numerical illustration, the negative binomial regression model (see, for instance [9]), which can accommodate overdispersion in the data, is fitted on the number of claims using all nine explanatory variables. Finally, the Shapley methodology was used to assess the contribution of each covariate in the negative binomial regression by calculating their impact on the predicted number of claims, which is measured by the explained variance. To compute the Shapley effects, we followed the suggestion of Mase et al. [11] and set \(\delta _j\) to one-tenth of the interquartile range between the 95th and 5th percentiles for continuous variables, while \(\delta _{j}=0\) if they are discrete. The computational times are presented in Table 1.

Table 1 reveals that the strategy based on the conditional Latin hypercube is significantly faster compared to the one based on the Latin hypercube, being approximately ten times quicker. The computational time for the Shapley effects is the duration required by the algorithm of [26] for a given sample size. A non-linear increase in computational time is observed. In particular, estimating the Shapley effects with the full dataset requires more than 18 h and 16 min, while the computation with \(n=2500\) selected observations takes approximately one minute in total (2.89 s to find the representative observations using the CLH plus 61.23 s to estimate the Shapley effects from those observations). The selection of representative observations using Latin hypercube and hierarchical k-means is significantly slower compared to the conditional Latin hypercube method. Interestingly, as the sample size increases, the time required to find the representative policies with these approaches exceeds the time needed to compute the Shapley effects for that sample.

The estimated Shapley effects are illustrated in Fig. 2.

In particular, Fig. 2 presents the Shapley effects estimated with varying numbers of observations selected using the Latin hypercube, the conditional Latin hypercube and the hierarchical k-means. Several observations can be made. Firstly, Bonus-Malus is identified as the most important variable, as also found in Richman et al. [20, 21]. Secondly, the Shapley effects computed with a small sample size (\(n=500\)) using representative observations effectively distinguish between relevant and irrelevant risk factors, with Density and VehGas showing small Shapley effects across all sample dimensions (with the exception of the Shapley effect estimated using hierarchical k-means, which is slightly biased). In general, accuracy tends to increase with larger sample sizes. To confirm this, we considered the sum of the mean squared errors across all sample sizes and sampling strategies, \( \frac{1}{20}\sum _{j=1}^k\sum _{m=1}^{20}(\widehat{\phi }_{j,m}-\phi _j)^2,\) where \(\widehat{\phi }_{j,m}\) is the Shapley effect of the \(j\)-th variable computed for the \(m\)-th replication, with \(m=1,\ldots ,20\), using a specified sampling method, and \(\phi _j\) is the Shapley effect of the \(j\)-th variable computed using the entire dataset. This approach involves summing the squared errors for each Shapley effect across all replications for a given sample size and sampling method, then repeating this process 20 times, and finally averaging the results. Figure 3 shows the results.

Figure 3 shows that at \(n=500\), the error for HK is higher compared to the LH and CLH methods. This difference decreases as n increases, and all three methods exhibit comparable error at \(n=2500\). Interestingly, we also observe that the LH method shows very small oscillations for the sum of mean squared errors. We believe this is a specific feature of this dataset since it is expected that in general the accuracy is increasing as the sample size increases.

Overall, taking into account the trade off between the small loss of accuracy and the significant reduction in computational time, the CLH sampling strategy seems to be optimal choice in this application.

In this work, we proposed a strategy to speed up the computation of Shapley effects, especially when dealing with a large number of observations, a common scenario in various insurance settings involving structured, semi-structured, and unstructured data. We selected representative observations using the Latin hypercube, conditional Latin hypercube, and hierarchical k-means methods, following a methodology similar to that of Gan and Valdez [4] applied to a large portfolio of variable annuities. Subsequently, we computed the Shapley effects using the selected sample.

Applying this strategy to the well-known French MTPL dataset, we observed a notable reduction in computational time without a significant loss of accuracy. Moreover, we emphasize that in our work we assumed a negative binomial predictive model linking the variables \(\textbf{x}\) to the output y (the claim number standardized by policy exposure). Nonetheless, it can be applied to identify the most crucial variables for any model by substituting the observed values \(\{y_i\}_{i=1}^n\) with the predicted values \(\{\hat{y}_i\}_{i=1}^n\) obtained using a specified machine learning model.

In our opinion, our proposed strategy holds promise for a big-data framework, and new research in this direction could be pursued. In particular, when the dataset has a large number of variables (i.e., more than 20), it becomes impractical to estimate all possible coalition values, making it necessary to use stochastic methods to approximate the Shapley value (see [1, 24]). These methods reduce the number of \(2^k\) coalition values to be computed by sampling only a subset of coalitions for which the value is then estimated. We believe that combining our proposed approach with stochastic approximation methods could represent a promising direction for future research, especially when dealing with datasets containing many observations and covariates.

Finally, we note that while our strategy accelerates computation, it introduces an error as it is an approximation. Therefore, deriving theoretical error bounds for the Shapley effects under different sampling designs is an open issue for future research.