Technical Appendix to "ShapBPT: Image Feature Attributions using Data-Aware Binary Partition Trees"

ShapBPT: Image Feature Attributions using Data-Aware Binary Partition Trees Technical Appendix Derivation of Equation (4) We present a clear formulation of the Owen approximation of Shapley values within a hierarchical coalition structure, as this specific approach appears to be absent from existing published literature. To ease our formulation, we start from a simple extension of the Shapley formula: ωi(Q, N)= ! S→N\{i} 1 n·"n↑1 |S|#!i(Q→S)(8) where nis the cardinality of N. Eq. (8) assigns a unique distribution of the total worth ε(N)generated by cooperation among players in a coalition game, and is extended by assuming that all coalitions Sare supported by a persistent set of players Q. The regular Shapley value (Shapley 1953, Eq.12) are obtained from (8) as ωi(⊋,N). The persistent set Qis used for the Owen approximation. The Owen coalition value (Owen 1977) is an extension of the Shapley value, and it is a quantity ”i(T)that represents the worth of player iin a game with coalition structure T. The original formulation for a two-level coalition structure hierarchy3works as follows. Consider a player ibelonging to team Tj↑T↓. Then ”i(T)= ! H↓M j↔↗H! S↓Tj i↔↗S 1 m·"m↑1 |H|#·1 tj·"tj↑1 |S|#!i(QH→S) (9) where M={1...m}is the set of structured coalition indices of T,QH=$k↗HTk, and tj=|Tj|. Eq. (9) can be seen as a two-level Shapley value, where inside a team Tjall coalitions are possible, but once a coalition S↔Tjis formed, only a restricted all-or-nothing form of cooperation with the other teams is possible. It is possible to rewrite (9) by explicitly identifying the Shapley value for the subsets Sof Tj. By doing so with (8) and applying simple algebraic transformations, we get ”i(T)= ! H→M\{j} 1 m·"m↑1 |H|#ωi(QH,T j)(10) i.e. the Owen coalition value is defined on the basis of the Shapley value (extended as in Eq. (8)), similarly to the approach of the so-called “two-steps value” formulation of (Owen 2013, p.300). Example 3. Consider a coalition structure T= %{1,2},{3,4,5},{6}&. The coalition value ”1(T)= 3In a two-level coalition structure hierarchy T, we have T→= {T1...T m}, and ↑1↓i↓m:Ti→=↔. ϑ1(⊋,T)is the weighted sums of eight marginals: 1 6!1(⊋)1 6!1({2}) 1 6!1({3,4,5,6})1 6!1({3,4,5,6,2}) 1 12!1({6})1 12!1({6,2}) 1 12!1({3,4,5})1 12!1({3,4,5,2}) Since player 1is in an a-priori coalition with player 2, the other two teams {3,4,5}and {6}can only appear as a whole. As a consequence, the Owen approximation of the Shapley coefficients only observes some coalitions, that preserve the integrity of the teams that are in a separate branch of the tree hierarchy. Observe that ”i(T)↗=ωi(⊋,N), as only a selected structured subsets of coalitions are formed (see (López and Saboya 2009) for an in-depth analysis of this relation). The two-level formulation is easily extended to an arbitrary hierarchy of coalitions, and this idea has been pioneered for image data by the SHAP Partition Explainer (Lundberg 2020; Shrikumar, Greenside, and Kundaje 2017; Lundberg and Lee 2017). Therefore a hierarchical Owen coalition value can be obtained rewriting Eq. (10) on top of other Owen coalition values for a coalition T, as long as Tis not an indivisible coalition. The concept is also briefly sketched in(Owen 1977, p.87), but we rewrite the equation to have a simple recursive formula that is general for m-ary and binary hierarchical coalition structures, as in Eqs. (2) and (3), respectively. Binary and multi-way tree hierarchies (i.e. m>2). Consider Eq. (10) and replace the summation over the subsets of indices Mwith a uniform subset Uof the subcoalition structure of T↓, making the marginal contribution of Eq. (1) as the base case of the recursion, and adding a persistent set Qas done for Eq. (8). ”i(Q, T)=         ! U→T↘\{Tj} 1 m·"m↑1 |U|#”i(Q→QU,T j) if T↓={T1...T m} 1 |T|!T(Q)if Tis indivisible (11) where QU=$|U| k=1 Uk, and assuming Tjcontains i. As before, indivisible coalitions receive uniform attributions among all players. The Owen coalition value for player i using Eq. (11) is obtained from ”i(⊋,T), with Tthe HCS root. When T={N},T↓=↘, then Eq. (11) reduces to ωi(Q, N), which is trivially equivalent to Eq.(8). Using a two-level HCS, then Eq. (11) is equivalent to Eq. (9) and Eq. (10). For arbitrary nested hierarchies, the equation expands, generating the coalitions Qthat may pair with the set Tcontaining player i, following the hierarchy constraints. Example 4. Consider a three-level HCS T=+%{1,2},{3,4}&,%{5,6},{7},{8}&, The hierarchical coalition value ”1(⊋,T)is the weighted sums of eight marginals: 1 8!1(⊋)1 8!1({2}) 1 8!1({5,6,7,8})1 8!1({5,6,7,8,2}) 1 8!1({3,4})1 8!1({3,4,2}) 1 8!1({5,6,7,8,3,4})1 8!1({5,6,7,8,3,4,2}) Coalitions can pair with player 1following the hierarchy. Therefore {3,4}and {5,6,7,8}can only appear as a whole block from the point-of-view of player 1, even if the partition {5,6,7,8}is not a single coalition. Eq. (11) applies to m-ary coalition structure, but the case for binary hierarchies is simpler. By assuming m=2, the formula ”i(Q, T)of Eq. (11) can be simplified, obtaining Eq. (4) and completing our derivation. Proof of Theorem 1 Applying Eq. (4) to a partition Tthat admits a sub-coalition structure T↓={T1,T 2}creates four branches (two for i↑T1and two for i↑T2) and necessitates two εevaluations. Since we are assuming the BHCS hierarchy to be a balanced tree with depth d, we can define the total number a(d)of εevaluations for the expansion of all nodes up to depth d. Such quantity a(d)follows a linear recurrence sequence represented by Eq. (12) a(d)=-4·a(d≃1) + 2 if d>0 0if d=0 (12) Recursion from Eq. (12) can be eliminated, since the equation is a well-known non-homogeneous linear recurrence with constant coefficients, having solution a(d)=ϖ·a(d≃1) + ϱ=ϱ(ϖd↑1≃1) ϖ≃1 By using ϖ=4and ϱ=2, Eq. (12) simplifies to a(d)=2 3(4d↑1≃1) ⇐O(4d)(13) i.e., the time complexity of Eq.(4) exhibits exponential growth. Pseudo-code of the Owen approximation algorithm A limitation of equation Eq. (4) is that the same coalitions are generated in the recursive expansion of ”i(⊋,T), for different players i↑N. This issue may severely limit the performance, but it can be easily solved either by memoization, or by generating all the coalitions using a tree visit. An efficient iterative implementation of the latter is sketched in Algorithm 1, and it is conceptually equivalent to the Partition Explainer of SHAP (Lundberg 2020). Therefore it does not constitute a novel paper contribution, but we report it for reader’s convenience and self-containment. Algorithm 1: Iterative implementation of Eq. (4). 1function OwenValues(ω,T,b) 2foreach i↗Ndo ![i]↘0 3queue.push!≃1,⊋,T,ω(⊋),ω(N)⇐" 4while queue is not empty do 5w, Q, T, vQ,v Q→T↘queue.pop() 6if Tis indivisible or b↓1then 7foreach i↗Tdo 8![i]↘![i]+ w |T|!vQ→T⇒vQ" 9else 10 T1,T 2↘T→ 11 vQ→T1↘ω(Q⇑T1) 12 vQ→T2↘ω(Q⇑T2) 13 b↘b⇒2 14 queue.push!≃w 2,Q,T 1,v Q,v Q→T1⇐, ≃w 2,Q⇑T2,T 1,v Q→T2,v Q→T⇐, ≃w 2,Q,T 2,v Q,v Q→T2⇐, ≃w 2,Q⇑T1,T 2,v Q→T1,v Q→T⇐" 15 return ! Algorithm 1 operates at the partition level. It starts from the full coalition at the root Tof the BPT hierarchy (measuring the difference ε(N)≃ε(⊋)). Partitions are inserted into a queue, assumed to be ordered by a priority w. It then proceeds by splitting the next partition with the highest w, using Eq. (4). Each split requires two model evaluations (line 13), thus reducing the budget bby 2. The splitting continues until the budget bis consumed, or all partitions left are indivisible. Pseudo-code of the BPT algorithm Detailed pseudo-code for the BPT algorithm can be found in (Salembier and Garrido 2000; Randrianasoa et al. 2018, 2021), but a pseudo-code is provided in Algorithm 2. It uses three functions: •init_bpt: initializes the unitary partitions iof the BPT hierarchy from the individual pixels px of the input image x, and creates the heap of all the pairs of adjacent pixels. •get_dist: computes the distance between two (adjacent) partitions iand jusing Eq. (5). •build_bpt: iteratively merges adjacent partitions in distance-order, each time creating a new merged partition k, and updates the weights in the heap accordingly. The function proceeds as long as there are adjacent partitions, i.e. it stops when all pixels are merged into a single root partition. Once Algorithm 2 has generated a merging sequence, it can be efficiently stored into 6 arrays: •leaf _idx[i]: the image pixel of unitary coalition i, with i↑[1,n]; •left_branch[k]and right_branch[k]: the two partition indexes resulting from the split Tk↓of each non-unitary coalition k, with k↑[n+1,2n≃1]; •start[k]and end[k]: index interval of pixels for the non-unitary partition k; •pixels: the sorted array of pixel indexes, indexed by start and end. Therefore, the memory requirement for the BPT hierarchy is #(6n)integers. The core data structure is a graph of the partitions (nodes), paired with the list of adjacencies (edges). The adjacency list needs to be sorted efficiently in order to extract the edge adj =(i, j)having the smallest dist(i, j), as defined by Eq. (5) and computed by function get_dist. To do so, a heap data structure is a reasonable choice. Merging coalitions therefore requires to both modify the nodes and update the edges. This process, described at line 16 of build_bpt and depicted in Figure 2/B, shows that each merge operation requires to traverse the adjacency list of the merged partitions. Further details can be found in (Randrianasoa et al. 2018). Python implementation ShapBPT is implemented in Python. A snippet of the python code using the ShapBPT package to obtain a Shapley explanation for a given image using the masking function εis provided in Algorithm 3. While not detailed in the paper, the implementation supports multi-class explanations, similarly to (Lundberg 2020). Sensitivity of the distance function We run a small sensitivity analysis of the distance function dist(Ti,T j)over 100 randomly sampled images from ImageNet-S50. Unless otherwise stated, all experiments use the same ResNet-50 classifier, a fixed evaluation budget b of 100 model calls per image and the ShapBPT hyperparameters reported in the main text. We consider three variations of the distance function. •Default (Eq. (5)) - color ⇒area ⇒⇑perimeter. •No-perimeter - color ⇒area (drops the perimeter term). •No-color - area ⇒⇑perimeter (drops the color term). Area cannot be dropped, as it generates imbalanced trees. We report the relative change (!%) in AU -IoU and max-IoU against the default distance. Distance variant !AU -IoU ⇓!max-IoU ↓ Default (Eq. (5)) 0.0% 0.0% No-perimeter term ≃2.65%≃3.78% No-color term ≃12.61%≃24.40% Dropping the perimeter term produces a small loss in AU -IoU of ≃2.65% and a small loss in max-IoU of ≃3.78%, showing that the presence of the perimeter term provides a benefit. Dropping the color term results in significant losses (≃12.61% in AU -IoU and ≃24.40% in max-IoU ), which shows that color term is very relevant. Therefore, the default color-area-perimeter distance of Eq. (5) is a well-behaved compromise: inexpensive to compute and close to the Pareto front. We plan to study more complex alternatives in a future work. Algorithm 2: Pseudo-code of the BPT algorithm. 1function init_bpt(X:image) 2foreach pixel px of image xdo 3i↘make_partition() 4minR[i]↘maxR[i]↘R[px] 5minG[i]↘maxG[i]↘G[px] 6minB[i]↘maxB[i]↘B[px] 7area[i]↘1;perimeter[i]↘4;root [i]↘i 8foreach pair of partitions i, j that have adjacent pixels in xdo 9heap_push(heap,make_adjacency(i,j, weight=get_dist(i,j)) ) 1function get_dist(i,j) 2rangeR ↘max(maxR[i]⇒maxR[j])⇒ min(minR[i]⇒minR[j]) 3rangeG ↘max(maxG[i]⇒maxG[j])⇒ min(minG[i]⇒minG[j]) 4rangeB ↘max(maxB[i]⇒maxB[j])⇒ min(minB[i]⇒minB[j]) 5area ↘area[i]+area[j] 6perimeter ↘perimeter [i]+perimeter [j]⇒ 2⇓adjacent_perimeter[i,j] 7color _score ↘(rangeR2+rangeG 2+rangeB 2) 8return color _score ⇓area ⇓⇔perimeter 1function build_bpt() 2while heap is not empty do 3adj ↘heap_pop(heap) 4i, j ↘partitions in adj 5k↘make_partition() 6minR[k]↘min(minR[i],minR[j]) 7maxR[k]↘max(maxR[i],maxR[j]) 8minG[k]↘min(minG[i],minG[j]) 9maxG[k]↘max(maxG[i],maxG[j]) 10 minB[k]↘min(minB[i],minB[j]) 11 maxB[k]↘max(maxB[i],maxB[j]) 12 area[k]↘area[i]+area[j] 13 perimeter[k]↘perimeter[i]+perimeter[j] 14 root [k]↘k;root [i]↘root [j]↘k 15 left_branch[k]↘i;right_branch[k]↘j 16 merge linked lists of adjacencies of iand jinto a single linked list for partition k, updating the heap weights using get_dist since partitions iand jare now merged together. Algorithm 3: Example Python code. 1from shap_bpt import Explainer 2explainer = Explainer(ω, image_to_explain, num_explained_classes) 3shap_values = explainer.explain_instance(max_evals=b) Evaluation details Experiment E1 This experiment employs the 1K-V2 pretrained model (Vryniotis 2021), utilizing the ResNet50 architecture (He et al. 2016) available in the PyTorch library, which reports an accuracy of 80.858%. Masking is applied by substituting affected pixels with a uniform gray color. The analysis is conducted on the ImageNet-S50 dataset (Gao et al. 2022), which provides precise ground-truth masks for a selected subset of images. To maintain consistency, only images for which the ground-truth mask corresponds to the top predicted class are considered, resulting in a total of 574 images. Figure 6 shows additional saliency maps for the E1 experiment, generated by explaining the classification of the ResNet50 model on the samples from the ImageNet-S50 dataset. Figure 7 reports the results for E1, with one table for each of the four scores, plus one for the evaluation time (logscale). All reported times were computed with an Intel Core i9 CPU, an Nvidia 4070 GPU, and 16GB of RAM. Scores are drawn as boxplots (treating values outside 10 times the interquantile range as outliers, drawn as fuchsia dots), with a method symbol on the right (see the legend for the mapping). In E1, BPT is positioned close or at the top of every score. In this case, AA has a slightly better AUC +score, but a worse AUC ↑score than BPT. The BPT method seems to be particularly effective at the IoU scores max-IoU and AUIoU, which can be explained by its capacity of recognizing the borders of the objects, by following a data-aware hierarchy. Only GradCAM reaches similar IoU scores, but in practice the localization of GradCAM is more blurred and fuzzy (this limitation is apparently not well captured by the two IoU scores). Experiment E2 One important limitation of experiments relying on some unknown black-box model is that the ground truth may not be faithful, as the model may classify an object based on partial details or using weak correlations. To overcome this limitation, experiment E2 replicates E1 adopting an ideal model which perfectly follows the ground truth. The ideal model εlin(S)=|S≃G| |G| is a linear function that outputs the proportion of pixels of S that belong to the ground truth G. Since εlin is not a neural network, CAM methods cannot be used and are excluded. By using a linear model, the experimental environment has minimal noise, is therefore simpler to interpret, and provides a better baseline for assessment, even if it is less realistic than a deep learning model. Figure 8 shows the results of experiment E2, while a subset of the generated saliency maps are depicted in Figure 9. The results shows the effectiveness of the BPT explanation strategy: all BPT-bachieve better scores that their AA-b counterpart, for the same budget b. Experiment E3 Experiment E3 replicates the setup of E1 and E2, but employs a Vision Transformer model, specifically SwinViT (Liu et al. 2021). Vision Transformer models are known for their robustness against partial occlusion of recognized objects, making it more challenging for model-agnostic methods to analyze their behavior by selectively masking parts of the image. A summary of the results is presented in Figure 11, while a selection of saliency maps from the same set of examples is depicted in Figure 10. Due to the limitations of the LRP method’s implementation, which does not support this transformer-based architecture, we excluded it from the results. Analyzing the explanations produced by different methods, it is evident that all approaches, except for BPT, generate significantly more ambiguous saliency maps, attributing considerable importance to background features while failing to focus adequately on the classified objects. In contrast, the maps produced by BPT appear clearer and more focused. Notably, BPT consistently achieves superior performance across all evaluation metrics. This experiment provides valuable insights, as Vision Transformer models exhibit increased robustness to input masking, making them particularly challenging to interpret using model-agnostic methods. Unlike convolutional models, these transformers-based model require clever feature replacement techniques for behavior probing, and ShapBPT seems to be significantly better than the other methods. Input AA-100 AA-500 AA-1000 LIME-100 LIME-500 LIME-1000 GradCAM |IDG| |GradExpl|Ground Truth BPT-100 BPT-500 BPT-1000 LRP GradShap 00003843 lemon 0.45014 00004203 bullet_train 0.31623 00007684 agaric 0.48667 00008292 airliner 0.56394 00011346 cellular_telephone 0.17521 (a) (b) (c) (d) (e) (f) (g) (h) 000017505 tree_frog 0.34687 00020075 container_ship 0.42062 00025140 red_fox 0.30399 Figure 6: Additional saliency maps generated for the E1 experiment. Figure 7: Results for four metrics across 574 images from the ImageNet-S50 dataset, with methods ranked by performance (highest at the top) for experiment E1. Arrows denote whether higher or lower scores are better. 0.4 0.6 0.8 1.0 1.2 1 01 2 1 3 02 03 2 3 AUC+ 0.0 0.2 0.4 0.6 1 01 1 2 02 03 3 2 3 AUC 0.0 0.5 1.0 1 2 3 1 01 2 3 03 02 max-IoU 0.00 0.25 0.50 0.75 1 2 1 01 3 2 02 03 3 AU-IoU 0.1 1 10 01 03 02 3 2 1 3 2 1 log(time) Figure 8: Results for the four metrics across 574 images from the ImageNet-S50 dataset, with methods ranked by performance (highest at the top) for the experiments E2. Input BPT-100 BPT-500 BPT-1000 AA-100 AA-500 AA-1000 LIME-100 LIME-500 LIME-1000 Image: 00000618 Class: sulphur_butterfly (a) 00017635 ladybug 00005428 street_sign 00008733 park_bench (b) (c) (d) Ground Truth Figure 9: Saliency maps obtained from the ideal linear model εlin, experiment E2. Input AA-100 AA-500 AA-1000 LIME-100 LIME-500 LIME-1000 GradCAM |IDG| |GradExpl|Ground Truth BPT-100 BPT-500 BPT-1000 LRP GradShap (a) 00047683 sulphur_butterfly 0.88395 00017635 ladybug 0.91768 (b) 00005428 street_sign 0.90125 (c) 00008733 park_bench 0.89729 (d) Not Available Not Available Not Available Not Available Figure 10: Saliency maps from selected instances in the E3 experiment (with SwinViT). 0.0 0.5 1.0   1 2  3 01 03 02 1 2 3 AUC+ 0.0 0.5 1.0    01  03 3 02 2 1 1 2 3 AUC 0.0 0.5 1.0     03 02 01 3 1 2 3 2 1 max-IoU 0.0 0.2 0.4 0.6     03 02 01 1 3 2 3 2 1 AU-IoU 0.1 1 10 03 01 3 3 02 2 2 1  1    log(time) Figure 11: Results for the four metrics across 621 images from the ImageNet-S50 dataset, with methods ranked by performance (highest at the top) for the experiments E3. Experiment E4 This experiment focuses on the MS-COCO dataset (Lin et al. 2014), which includes 80 object classes with diverse image sizes and aspect ratios, and a wider range of details than ImageNet. The task is object detection, evaluated on 5,000 images (from the validation set) with bounding box and segmentation map annotations. A pre-trained Yolo11s model (Jocher and Qiu 2024) from the Ultralytics library (319 layers, 9.4M parameters, 21.7 GFLOPs) is used as a black-box model for its accuracy and fast inference. The XCV task involves highlighting detected objects and comparing them to segmentation maps, with evaluation based on performance curve metrics and ground-truth comparisons, as explained in Experimental Assessment Section. Also in this case, ShapBPT demonstrates strong capability in highlighting the boundaries of detected objects, outperforming AA in most metrics. Experiments E5 This experiment considers a multiclass regression model rather than a classification model. The objective is to determine the presence (positive prediction) or absence (negative prediction) of specific facial features, such as brown hair or eyeglasses. The explainable AI task involves identifying the regions that contribute to these predictions. A score ε(N)>ε(⊋)indicates the presence of the feature, while a score ε(N)<ε(⊋)signifies its absence. The dataset used for this study is CelebA-HQ (Karras et al. 2018), which includes 40 facial attributes. For this analysis, we focus on two attributes—brown hair and eyeglasses—for which ground-truth segmentation masks are available. A total of 106 images were evaluated. The model employed is a pre-trained sequential convolutional neural network (CNN) provided by (Batra 2020). An example of the XCV task is illustrated in Figure 14, where multiple instances are analyzed. The first three are: 0.1 A subject with brown hair, correctly identified as having brown hair (positive score). 0.2 A subject with black hair, correctly identified as not having brown hair (negative score). 0.3 A subject wearing eyeglasses, correctly identified as having them (positive score). For positive cases (a, c, d, and e), the Shapley values are positive in the regions contributing to the positive prediction. Conversely, for negative cases (b and f), the Shapley values are negative in the areas responsible for the negative prediction. Since CAM methods do not inherently satisfy the efficiency axiom of Shapley values, their outputs are considered in absolute terms. Results of the evaluation are reported in the tables in Figure 15. This experiment shows again the capacity of BPTbased methods to adaptively follow the borders of the activating regions, achieving high performances particularly on IoU scores. Note that also in this case, as previously discussed for E1, the ground truth can only be considered as a weak approximation of the model’s learnt representation, as the model is likely to use multiple features of the subject face to determine the presence or the absence of a specific attribute, not just the shape of the hair or the eyeglasses. Nonetheless, the localization of that area remains more precise when data-awareness is used. Experiment No. of Methods No. of Images AUC+AUC↑max-IoU AU-IoU E1 14 574 0.0 4.10e-197 0.0 2.49e-135 E2 12 574 0.0 0.0 0.0 0.0 E3 14 621 0.0 4.56e-248 0.0 0.0 E4 9 274 1.09e-111 1.54e-15 1.94e-96 1.29e-18 E5 14 436 0.0 0.0 1.36e-31 1.64e-13 E6 9 280 2.12e-145 4.03e-175 8.53e-260 0.009 E7 13 593 0.0 1.27e-209 6.06e-162 0.0 Table 2: One-way ANOVA summary of all four metrics across the seven experiments. the Owen extension of Shapley values, whose recursive additivity hinges on a binary partition tree (BPT). Consequently, raw SAM outputs cannot be plugged directly into hierarchical-Shapley frameworks without additional structure. One direction is the Explain Any Concept (EAC), which couples SAM with Shapley values to attribute predictions to aflat set of SAM-derived concept masks (Sun et al. 2023). Because these masks may overlap and are treated independently, the Shapley computation is executed once on the initial segmentation, with no mechanism for iterative refinement of coalitions. This design means EAC’s faithfulness is entirely dependent on the initial SAM proposals already capturing all semantically relevant regions (like LIME), thereby breaking requirement R2 of the ShapBPT framework (i.e. progressive, data-driven refinement of the coalition hierarchy). In scenarios where the first-pass segmentation misses fine-grained or contextually important regions, EAC cannot recover them, whereas ShapBPT’s recursive splits can adaptively hone in on such details. A viable research direction toward a SAM-based Hierarchical Coalition Structure (HCS) is to post-process the SAM mask set into a non-overlapping, nested hierarchy that is compatible with the Owen recursion. One potential starting point follows the Panoptic-SAM pipeline4, which “paints” SAM masks from largest to smallest to obtain a panoptic segmentation; a region-adjacency graph could then be constructed and merged iteratively (e.g., by similarity or containment) to yield a balanced tree. Still the tree is not strictly binary, which either needs a binarization or requires a reformulation of (4) to deal with n-ary trees. We plan as a future work to define a SAM-HCS and test its effectiveness against a morphology-driven BPTs, to understand how effective it is w.r.t. a fully refinable BPT structure. Remarks on h-Shap We considered including h-Shap (Teneggi, Luster, and Sulam 2022), which has a faster convergence compared to Theorem 1. However, since the object recognition task addressed by h-Shap is incomparable to that of the other XCV methods, as h-Shap treats binary-valued games only, we chose to exclude it. Despite this, we believe that h-Shap would also benefit from the use of BPT partitions. 4Panoptic Segment Anything. https://github.com/segments-ai/ panoptic-segment-anything