Optimizing Product Provenance Verification
using Data Valuation Methods

Let $\mathcal{X}$ be a set of locations where data is collected, where $x\in\mathcal{X}$ typically is specified by a longitude and latitude. Let $\mathcal{Y}$ be the set of measurements made over $\mathcal{X}$, here denoting stable isotope ratio values (e.g. $\delta^{13}C$, $\delta^{2}H$, $\delta^{15}N$, $\delta^{18}O$, $\delta^{34}S$), or trace element values (e.g. Si, Cu, S, Ba, Rb). We denote $f$ and $g$ as functions of interest (defined below). For evaluation purposes, we split our data into training and test datasets, where $D=\{z_{i}\}_{i=1}^{N}$ represents the training dataset with $N$ data points and $z_{i}=(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}$. Similarly, $T=\{z_{i}\}_{i=1}^{M}$ denotes the test dataset with $M$ data points. We let $v(h,A,B)$ denote the performance of the model $h$ trained on a dataset $A$ and evaluated on the dataset $B$, where $v$ would return a numerical value, $v(h,A,B)\in\mathbb{R}$. In cases when the function and the test dataset are known, we drop the dependence in the notation to simply say $v(A)$.

Data valuation is crucial for understanding the contribution of individual training samples to the performance of trained models for timber provenance. The Shapley value, introduced by (Shapley, 1953), offers a principled approach to quantify this contribution, identifying both highly informative and potentially detrimental data points. The Shapley value, $\phi_{i}$, for a data point $i$ is computed as the weighted average of its marginal contribution to model performance across all possible subsets of the training data:

Here, $D$ is the full training set, $S$ is a subset excluding $i$, and $v(S)$ is the model performance (e.g., negative mean absolute error) when trained on subset $S$. High positive Shapley values indicate highly valuable data points that significantly improve performance, while low or negative values suggest redundancy or detrimental effects, possibly due to outliers, measurement errors, or model misspecification. The Shapley value is not an arbitrary metric; it is uniquely characterized by satisfying a set of desirable axioms, ensuring fairness and consistency in data valuation:

1. (1)

   Efficiency: The sum of the Shapley values for all data points equals the difference in performance between the model trained on the full dataset and the model trained on an empty dataset: $\sum_{i\in D}\phi_{i}=v(D)-v(\emptyset)$. This means the total value is fully distributed among the data points.

2. (2)

   Symmetry (or Null Player): If a data point $i$ has zero marginal contribution to every possible subset (i.e., $v(S\cup\{i\})=v(S)$ for all $S$), then its Shapley value is zero: $\phi_{i}=0$. Useless data points receive zero value.

3. (3)

   Linearity: If the performance metric $v$ is a linear combination of two other performance metrics, $v=a\cdot v_{1}+b\cdot v_{2}$, then the Shapley values for $v$ are the same linear combination of the Shapley values for $v_{1}$ and $v_{2}$. This ensures consistency across different performance measures.

4. (4)

   Dummy: if two data points $i$ and $j$ always have the same marginal contribution to every subset of $D$ then their Shapley value must be equal. $\phi_{i}=\phi_{j}$.

These axioms provide a strong theoretical justification for using the Shapley value. Furthermore, the Shapley value can be equivalently expressed as a sum over permutations of the dataset (Shapley, 1953):

where $\Pi(D)$ is the set of all permutations of data points in $D$, $\pi$ is a permutation sampled uniformly at random from $\Pi(D)$, and $P^{\pi}_{i}$ is the set of data points preceding instance $z_{i}$ in permutation $\pi$.

Truncated Monte Carlo Shapley Value. The exact computation of Shapley values is computationally prohibitive due to the factorial term, requiring evaluation of $2^{|S|}$ subsets. We address this shortcoming by employing the Truncated Monte Carlo Shapley estimation. This method, proposed in (Ghorbani and Zou, 2019), approximates the Shapley values by randomly sampling a limited number of subsets instead of exhaustively considering all possibilities. The key idea is that each random permutation provides an unbiased estimate of the marginal contribution of each data point. By averaging these estimates over multiple permutations, the approximation converges to the true Shapley values. The number of iterations controls the trade-off between computational cost and accuracy. Algorithm 1 shows each step in detail.

By employing the data Shapley value, particularly with the Truncated Monte Carlo approximation, we can gain valuable insights into the training data, identify influential samples, diagnose potential issues, and ultimately improve the accuracy and robustness of their GP-based timber provenance models. This data-centric approach, grounded in a strong axiomatic foundation, complements model-centric evaluations and facilitates a more efficient use of resources for data collection and model refinement.

Acquiring high-quality isotope values for model training is a significant expense. Furthermore, standard data valuation techniques reveal a critical issue: not all data points contribute equally to predictive performance. In fact, some points may even be detrimental. Therefore, our objective is to strategically select a subset $D^{\prime}\subseteq D$ from the original training data $D$ that maximizes model accuracy for both forward and backward prediction tasks. We propose to leverage Shapley values computed once on the full dataset to identify data point importance. We hypothesize that by using these initial global valuations, we can efficiently identify and sequentially remove less valuable samples. Our data selection methodology consists of three distinct steps. Initially, we compute data values for all points in $D$ using the entire dataset. Subsequently, we sort the data points and remove the least valuable one according to these pre-calculated values. Finally, we evaluate the model’s performance using the test dataset. This sequential removal process continues as long as model performance improves, relying on the initial single valuation. Please refer to Algorithm 2 for a detailed algorithmic description. This simplified data selection method offers a computationally efficient approach to valuation, aiming to maximize model performance while minimizing the need for costly and potentially redundant data acquisition through a single valuation and sequential removal strategy.

We utilized data from two datasets of the genus Quercus, collected from various regions worldwide. Two broad datasets were combined in this study with the first dataset comprising tree samples distributed globally, while the second dataset was focuses specifically on European countries. Stable isotope ratio measurements were performed following the protocols outlined in (Watkinson et al., 2020; Boner et al., 2007).

As described in Section 3, the objective of data valuation is to strategically select subsets of the dataset that maximize model performance. Instead of solely selecting the most valuable data points, we implement an iterative approach. Given a dataset $D$ consisting of data points $(z_{1},z_{2},\dots,z_{i})$ and their corresponding data Shapley values $(\phi_{1},\phi_{2},\dots,\phi_{i})$, we conduct experiments by removing the low value data points $z_{k}$, where the data Shapley value $\phi_{k}$ satisfies $\phi_{k}<\phi_{j}\quad\forall j\neq k$, or equivalently, $\phi_{k}=\min_{j}\phi_{j}$. Furthermore, we extend our experiments by investigating the opposite case: removing the high-value data points $z_{m}$, where the Shapley value $\phi_{m}$ satisfies $\phi_{m}>\phi_{j}\quad\forall j\neq m$, or equivalently, $\phi_{m}=\max_{j}\phi_{j}$. We then evaluate model performance and analyze how the data valuation framework influences the overall model behavior. We report the root mean square error (RMSE) for all performance plots, defined as $\text{RMSE}=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\hat{y}_{i})^{2}}$, where $y_{i}$ and $\hat{y}_{i}$ represent the actual and predicted multivariate outputs involving variables $\mathcal{X}$ or $\mathcal{Y}$, on both forward and backward directions.

For this experiment, we explore the relevance and application of data Shapley values in the context of SIRA. Fig. 1 presents distribution plots for one subset of the dataset, evaluated in both directions of SIRA analysis, i.e., forward and backward, as described in Section 3. This analysis highlights a significant variation in data Shapley values depending on the dataset and the machine learning model utilized. These results indicate that subsets with Shapley values exhibiting greater extremities will correspond to larger performance gains following the data selection process.

We conducted two types of experiments, removing both high value and low value data points, as described in Section 4.2. We present the error plots showing the effect of removing these two types of data points for Gaussian process regression and random forest models. In both models, the RMSE increases (indicating performance degradation) when data points with high Shapley values are removed. Similarly, the RMSE decreases (indicating performance improvement) or remains stable when data points with low Shapley values are removed (Figure 2(a) and Figure 2(b)). Figure 2(c) illustrates one such case, where performance improves by removing specific data points (marked as red x on the map).

We further investigate whether the Shapley values from two different models agree with each other. We present three types of rank comparison plots in Figure 2(d-f). All three representations demonstrate a high degree of agreement between the two models in this experiment, indicating that data value ranks can remain consistent across different model architectures.

We conduct experiments with two types of approaches for handling missing data: (i) median imputation, where missing values are replaced with the median of the dataset, and (ii) listwise deletion, where data points containing missing values are excluded entirely from the training process. Additionally, we perform data selection experiments by removing both high-value and low-value data points and comparing the corresponding performance rankings.

We conducted experiments involving the removal of both high-value and low-value data points, as described in Section 4.2. The error plots (Figures 3(a) and 3(b)) illustrate the effects of removing these data points under both missing data handling strategies. For both strategies, the RMSE increases (indicating performance degradation) when data points with high Shapley values are removed. Conversely, the RMSE decreases (indicating performance improvement) or remains stable when data points with low Shapley values are removed.

We observe significant performance improvements when low-value data points are removed from both strategies, with the improvement being more pronounced for median imputation (26.66%) compared to listwise deletion (5.88%). This result demonstrates the effectiveness of data valuation as a strategy for improving missing data handling. Moreover, the Shapley values for the median imputation strategy exhibit higher magnitudes compared to listwise deletion (Figures 3(c) and 3(d)), which aligns with the greater performance improvements observed for median imputation.

In this experiment, we investigate whether selecting data based on valuation metrics can improve performance in both directions of SIRA. For this analysis, we present the results of applying the random forest model in both forward and backward directions using two distinct datasets: USA-only data and Europe-only data.

USA-only data: We present the error plots showing the effect of removing high-value versus low-value data points on the performance of the random forest model. In both directions, the RMSE increases (indicating performance degradation) when data points with high Shapley values, are removed. Similarly, the RMSE either decreases (indicating performance improvement) or remains stable when data points with low Shapley values, are removed (Figures 5(a) and 5(b)). Figure 5(c) illustrates a specific case where performance improves following the removal of certain data points, marked as red x on the map.

We observe performance improvements when low-value data points are removed from the dataset, with the improvement being more pronounced in the backward direction (27.13%) compared to the forward direction (0.14%). This finding demonstrates that performance improvement can indeed vary depending on the direction of SIRA. Moreover, consistent with the observations made in Section 4.5, the Shapley values associated with the backward direction exhibit higher magnitudes compared to the forward direction (Figure 1), which aligns with the greater performance improvements observed for the backward direction.

We further investigate whether the Shapley values from both directions show agreement. To this end, we present three types of rank comparison plots in Figure 5(d-f). All three representations indicate a high degree of agreement between the two directions, suggesting that data value ranks remain relatively consistent across different directions of SIRA.

Europe-only data: We conduct the same set of experiments and analyses on the Europe-only dataset. Similar patterns of performance improvement and deterioration are observed when low-value and high-value data points are removed, respectively (Figure 6). In the backward direction, performance improved by 5.08%, while in the forward direction, it improved by 7.81%.

We also compared the Shapley value ranks of the data points. For the Europe-only dataset, the similarities were less ideal than other cases, indicating that the ranking of data importance can differ across directions in different datasets. Figure 6(d-f) illustrates the corresponding plots for this case.

Here, we analyze the appropriate level of granularity for data selection to maximize performance when using a specific model and a data valuation framework. Instead of removing one data point at a time, we consider clusters of fixed distances (in kilometers) and remove all data points within that distance if a data point is selected for removal during the data selection process. We performed this location-based data selection for both high value (Figure 4(b)) and low value (Figure 4(a)) data points to understand the impact on model performance.

Consistent with the results of previous experiments, we observe performance improvements when low-value data points are removed. Furthermore, the cluster-based removal approach enhances the model’s performance more effectively than the one-by-one removal approach. This finding suggests that certain regions within the dataset are not essential for the best-performing model, or the improvements may be attributed to errors in the data extraction pipelines affecting specific regions.

For this experiment, we explore the variations in data Shapley values across different genera and species, aiming to identify the most and least significant contributors within the dataset. We present a sample distribution plot of data Shapley values for individual species within one dataset (Figure 4(c)). The plot demonstrates that certain species exhibit significantly higher data Shapley values compared to others, indicating their greater contribution to the model’s performance.