Explaining Black-box Model Predictions via Two-level Nested Feature Attributions with Consistency Property

## Abstract

Abstract Techniques that explain the predictions of black-box machine learning models are crucial to make the models transparent, thereby increasing trust in AI systems.
The input features to the models often have a nested structure that consists of high- and low-level features, and each high-level feature is decomposed into multiple low-level features.
For such inputs, both high-level feature attributions (HiFAs) and low-level feature attributions (LoFAs) are important for better understanding the model’s decision.
In this paper, we propose a model-agnostic local explanation method that effectively exploits the nested structure of the input to estimate the two-level feature attributions simultaneously.
A key idea of the proposed method is to introduce the consistency property that should exist between the HiFAs and LoFAs, thereby bridging the separate optimization problems for estimating them.
Thanks to this consistency property, the proposed method can produce HiFAs and LoFAs that are both faithful to the black-box models and consistent with each other, using a smaller number of queries to the models.
In experiments on image classification in multiple instance learning and text classification using language models, we demonstrate that the HiFAs and LoFAs estimated by the proposed method are accurate, faithful to the behaviors of the black-box models, and provide consistent explanations.

## 1 Introduction

The rapid increase in size and complexity of machine learning (ML) models has led to a growing concern about their black-box nature.
Models provided as cloud services are literal black boxes, as users have no access to the models themselves and the training data used.
This opacity raises numerous concerns, including issues of trust, accountability, and transparency.
Consequently, techniques to explain the predictions made by those black-box models have been attracting significant attention [, , ].

Various model-agnostic local explanation methods have been proposed to explain the predictions of black-box models.
The representative methods are, for example, local interpretable model-agnostic explanation (LIME) [] and kernel Shapley additive explanations (Kernel SHAP) [], which estimate the feature attributions of the individual prediction by approximating the model’s behavior with local linear surrogate models around the input.

In LIME and Kernel SHAP, the input to the model is generally assumed to be a flat structure, where the input features are treated as independent variables.
In many realistic tasks for various domains, such as image, text, geographic, e-commerce, and social network data, however, the input features have a nested structure that consists of high- and low-level features, and each high-level feature is decomposed into multiple low-level features.
A typical task with such nested features is multiple instance learning (MIL) [] where the model is formulated as set functions [].
In MIL, the input is a set of instances, the high-level feature is an instance in the set, and the low-level features represent the features of the instance.
In addition, even if the input is not represented with a nested structure when it is fed into the model, it may be more natural to interpret it with the nested structure.
For example, although a text input is usually represented as a sequence of words, it is natural to interpret it as having high-level features such as phrases, sentences, and paragraphs.

The two-level features enable us to understand the model predictions with two types of feature attributions that have different levels of granularity in explanation, which we name high-level feature attributions (HiFAs) and low-level feature attributions (LoFAs), respectively.
Figure 1 shows an example of the prediction for a nested structured input and its corresponding HiFAs and LoFAs.
The HiFAs represent how much each of the high-level features contributes to the prediction.
These are also referred to as instance attributions in the MIL literature [, ], which are used to reveal which instances strongly affected the model’s decision.
On the other hand, the LoFAs represent how much each of the low-level features contributes to the prediction, providing a more fine-grained explanation of how the components of the instances affected the prediction.
Both the HiFAs and LoFAs are important for understanding the model’s decision.
However, existing studies have focused on estimating either-level attributions, and no study has addressed estimating the HiFAs and LoFAs simultaneously.

For the estimation of the HiFAs and LoFAs, two naive approaches can be applied.
One is to estimate the HiFAs and LoFAs separately by applying existing model-agnostic local explanation methods to the high- and low-level features, respectively.
The other is to estimate the LoFAs first, as with the former approach, and then estimate the HiFAs by aggregating the LoFAs.
However, these approaches have two rooms for improvement in terms of using the nested structure of the input.
First, even though the queries to the black-box model are often limited in practice due to the computational time and request costs, the input structure is not utilized to reduce the number of queries in the estimation.
Second, the former approach can produce inconsistent explanations between the HiFAs and LoFAs, for example, the most influential high-level feature and the high-level feature to which the most influential low-level feature belongs may not match.

Figure: Figure 1: Example of the black-box model prediction for a nested structured input and its corresponding high- and low-level feature attributions estimated by the proposed method with consistency constraints. Objects in each high-level feature represent the low-level features.

To address these issues, we propose a model-agnostic local explanation method that effectively exploits the nested structure of the input to estimate the HiFAs and LoFAs simultaneously.
A key idea of the proposed method is to introduce the consistency property that should exist between the HiFAs and LoFAs, thereby bridging the separate optimization problems for them.
We solve a joint optimization problem to estimate the HiFAs and LoFAs simultaneously with the consistency constraints depicted in Figure 1 based on the alternating direction method of multipliers (ADMM) [].
The algorithm is a general framework that can also introduce various types of regularizations and constraints for the HiFAs and LoFAs, such as the $\ell_{1}$ and $\ell_{2}$ regularizations and non-negative constraints, which lead to the ease of interpretability for humans.

In experiments, we quantitatively and qualitatively assess the HiFAs and LoFAs estimated by the proposed method on image classification in the MIL setting and text classification using language models, compared with estimating them separately and using a recent attribution method for MIL [].
The experimental results show that the HiFAs and LoFAs estimated by the proposed method 1) satisfy the consistency property, 2) are faithful explanations to the black-box models even when the number of queries to the model is small, 3) can accurately guess the ground-truth positive instances and their features in the MIL task, and 4) are reasonable explanations visually.

The contributions of this work are summarized as follows:

- •
This study is the first to propose a model-agnostic local explanation method to estimate the two-level nested feature attributions simultaneously, which satisfies the consistency property between them.
- •
In the experiments on practical tasks, we demonstrated that the proposed method could produce accurate, faithful, and consistent two-level feature attributions with a smaller number of queries to the black-box models.

## 2 Related Work

Numerous methods for explaining the individual predictions of black-box models have been proposed in the literature [, , , , ].
A versatile approach is to explain feature attributions estimated by approximating the model predictions with surrogate models around the input, such as LIME [] and Kernel SHAP [].
The proposed method is in line with this type of approach.

Set data is one of the nested input features, which treats a set of multiple instances as a single input.
Set data appears in various ML applications, such as point cloud classification [], medical image analysis [], and group recommendation [], and the explainability on those applications has also been studied in the literature [, ].
Unlike our work, most such studies focus only on estimating instance attributions corresponding to those of high-level features.
For example, Early et al. proposed to estimate instance attributions by learning surrogate models with MIL-suitable kernel functions [].

Several studies have addressed estimating feature attributions effectively by leveraging group information of input features.
In the natural language processing literature, some studies estimated sentence- and phrase-level feature attributions by grouping words in the same sentence and phrase together and regarding them as a single feature [, ].
In addition, Rychener et al. showed that word-level feature attributions can be improved by generating perturbations at a sentence level, mitigating the issues of out-of-distribution for the model and high-dimensional search space [].
In the official SHAP library [], by grouping input features by hierarchical clustering in advance and generating perturbations at the group level, one can reduce the number of queries to the model.

If we consider high-level features as nodes and low-level features as the features of the nodes and then somehow put edges between the nodes, we can think of an input as a graph.
By doing so, model-agnostic explanation methods for graphs, such as GNNExplainer [] and GraphLIME [], can be applied to our task.
However, since this approach highly relies on the graph structure, additional information is required to create appropriate edges.

## 3 Proposed Method

### 3.1 Two-level Nested Feature Attributions with Surrogate Models

The model $f$ to be explained is a trained black-box model that takes an arbitrary input, such as tabular, image and text, $\boldsymbol{x}\in\mathcal{X}$, and outputs a prediction $\boldsymbol{y}=f(\boldsymbol{x})\in[0,1]^{C}$ where $\mathcal{X}$ is the input space and $C$ is the number of classes.
The input $\boldsymbol{x}$ is made of two-level nested features, referred to as high-level and low-level features, and the high-level feature is decomposed into multiple low-level features.
In particular, the input $\boldsymbol{x}$ is represented as a set or sequence of $J$ high-level features, i.e., $\boldsymbol{x}=\{\boldsymbol{x}_{j}\}_{j=1}^{J}$ where $\boldsymbol{x}_{j}\in\mathbb{R}^{D_{j}}$ is the $D_{j}$-dimensional low-level feature vector representing the $j$-th high-level feature.
One example of such input appears in image classification under the MIL setting.
In this setting, the input is a bag of images, the high-level feature is an image in the bag, and the low-level features correspond to super-pixels in the image.
Another example appears in a document classification where the input is a sequence of sentences, the high-level feature is a sentence in the sequence, and the low-level features correspond to the words in the sentence.

We consider estimating the high-level feature attributions (HiFAs) and low-level feature attributions (LoFAs) that explain the prediction of the black-box model $f$ for the input $\boldsymbol{x}$ using surrogate models as with LIME and Kernel SHAP.
The HiFAs and LoFAs represent how much high- and low-level features in the input contribute to the prediction, respectively.
In the aforementioned MIL setting, the HiFAs represent how much images in the input bag contribute to the prediction, which is also referred to as instance attributions in the literature, and the LoFAs represent how much super-pixels in the images contribute to the prediction. To estimate the HiFAs and LoFAs, we introduce two-level local linear surrogate models for high-level and low-level features, $e^{\mathrm{H}}$ and $e^{\mathrm{L}}$, that mimic the behaviors of the black-box model $f$ around the input $\boldsymbol{x}$, as follows:

$$ $e^{\mathrm{H}}(\boldsymbol{z}^{\mathrm{H}};\boldsymbol{\alpha})=\sum_{j=1}^{J} \alpha_{j}z^{\mathrm{H}}_{j},\quad\quad e^{\mathrm{L}}(\boldsymbol{z}^{\mathrm {L}};\boldsymbol{\beta})=\sum_{j=1}^{J}\sum_{d=1}^{D_{j}}\beta_{jd}z^{\mathrm{ L}}_{jd},$ (1) $$

where $\boldsymbol{z}^{\mathrm{H}}\in\{0,1\}^{J}$ and $\boldsymbol{z}^{\mathrm{L}}=\{\boldsymbol{z}^{\mathrm{L}}_{j}\}_{j=1}^{J}$ with $\boldsymbol{z}^{\mathrm{L}}_{j}\in\{0,1\}^{D_{j}}$ are simplified inputs associated with the input $\boldsymbol{x}$, which are used to indicate the presence or absence of the high- and low-level features in $\boldsymbol{x}$, respectively; $\boldsymbol{\alpha}\in\mathbb{R}^{J}$ and $\boldsymbol{\beta}=\{\boldsymbol{\beta}_{j}\}_{j=1}^{J}$ with $\boldsymbol{\beta}_{j}\in\mathbb{R}^{D_{j}}$ are the learnable coefficients of these surrogate models, and after learning, they will be the HiFAs and LoFAs themselves, respectively.
For ease of computation below, we define the concatenation of $\boldsymbol{\beta}$ and $\boldsymbol{z}^{\mathrm{L}}$ over the high-level features as $\boldsymbol{\beta}^{\dagger}=\mathtt{concat}(\boldsymbol{\beta}_{1},
\boldsymbol{\beta}_{2},\cdots,\boldsymbol{\beta}_{J})\in\mathbb{R}^{D^{\dagger}}$ and $\boldsymbol{z}^{\mathrm{L}\dagger}=\mathtt{concat}(\boldsymbol{z}^{\mathrm{L}}
_{1},\boldsymbol{z}^{\mathrm{L}}_{2},\cdots,\boldsymbol{z}^{\mathrm{L}}_{J})
\in\{0,1\}^{D^{\dagger}}$, where $D^{\dagger}=\sum_{j=1}^{J}D_{j}$.

The surrogate models are learned with the predictions of the black-box model $f$ for perturbations around the input $\boldsymbol{x}$.
The perturbations are generated by sampling the simplified inputs $\boldsymbol{z}^{\mathrm{H}}$ and $\boldsymbol{z}^{\mathrm{L}\dagger}$ from binary uniform distributions and then constructing masked inputs $\phi_{\boldsymbol{x}}^{\mathrm{H}}(\boldsymbol{z}^{\mathrm{H}}),\phi_{
\boldsymbol{x}}^{\mathrm{L}}(\boldsymbol{z}^{\mathrm{L}\dagger})\in\mathcal{X}$ depending on the simplified inputs, respectively.
Here, $\phi_{\boldsymbol{x}}^{\mathrm{H}}$ and $\phi_{\boldsymbol{x}}^{\mathrm{L}}$ are mask functions that replace the input $\boldsymbol{x}$’s dimensions associated with the dimensions being zero in the simplified inputs $\boldsymbol{z}^{\mathrm{H}}$ and $\boldsymbol{z}^{\mathrm{L}\dagger}$ with uninformative values, such as zero, respectively.
Let $\boldsymbol{Z}^{\mathrm{H}}\in\{0,1\}^{N_{\rm{H}}\times J}$ and $\boldsymbol{Z}^{\mathrm{L}}\in\{0,1\}^{N_{\rm{L}}\times D^{\dagger}}$ be the matrices whose rows are the generated simplified inputs for the high- and low-level features, respectively, where $N_{\rm{H}}$ and $N_{\rm{L}}$ are the numbers of perturbations used to estimate the HiFAs and LoFAs, respectively.
Also, let $\tilde{\boldsymbol{y}}^{\mathrm{H}}=[\tilde{y}^{\mathrm{H}}_{1},\tilde{y}^{
\mathrm{H}}_{2},\cdots,\tilde{y}^{\mathrm{H}}_{N_{\rm{H}}}]^{\top}\in\mathbb{R
}^{N_{\rm{H}}\times C}$ and $\tilde{\boldsymbol{y}}^{\mathrm{L}}=[\tilde{y}^{\mathrm{L}}_{1},\tilde{y}^{
\mathrm{L}}_{2},\cdots,\tilde{y}^{\mathrm{L}}_{N_{\rm{L}}}]^{\top}\in\mathbb{R
}^{N_{\rm{L}}\times C}$ be the predictions of the black-box model for the perturbations where $\tilde{y}^{\mathrm{H}}_{n}=f(\phi_{\boldsymbol{x}}^{\mathrm{H}}(\boldsymbol{Z}
^{\mathrm{H}}_{n}))$ and $\tilde{y}^{\mathrm{L}}_{n}=f(\phi_{\boldsymbol{x}}^{\mathrm{L}}(\boldsymbol{Z}
^{\mathrm{L}}_{n}))$.

Simply, the parameters of the surrogate models, i.e., the HiFAs $\hat{\boldsymbol{\alpha}}$ and LoFAs $\hat{\boldsymbol{\beta}^{\dagger}}$, can be estimated by solving the following weighted least squares separately:

$$ $\displaystyle\hat{\boldsymbol{\alpha}}=\mathop{\rm argmin}\limits_{\boldsymbol {\alpha}}\mathcal{L}_{\mathrm{H}}(\boldsymbol{\alpha})+\lambda_{\rm{H}}\Omega_ {\rm{H}}(\boldsymbol{\alpha})\quad\text{where}\quad\mathcal{L}_{\mathrm{H}}( \boldsymbol{\alpha})=\frac{1}{2}(\tilde{\boldsymbol{y}}^{\mathrm{H}}- \boldsymbol{Z}^{\mathrm{H}}\boldsymbol{\alpha})^{\top}\boldsymbol{W}^{\mathrm{ H}}(\tilde{\boldsymbol{y}}^{\mathrm{H}}-\boldsymbol{Z}^{\mathrm{H}}\boldsymbol {\alpha}),$ (2) $\displaystyle\hat{\boldsymbol{\beta}^{\dagger}}=\mathop{\rm argmin}\limits_{ \boldsymbol{\beta}^{\dagger}}\mathcal{L}_{\mathrm{L}}(\boldsymbol{\beta}^{ \dagger})+\lambda_{\rm{L}}\Omega_{\rm{L}}(\boldsymbol{\beta}^{\dagger})\quad \text{where}\quad\mathcal{L}_{\mathrm{L}}(\boldsymbol{\beta}^{\dagger})=\frac{ 1}{2}(\tilde{\boldsymbol{y}}^{\mathrm{L}}-\boldsymbol{Z}^{\mathrm{L}} \boldsymbol{\beta}^{\dagger})^{\top}\boldsymbol{W}^{\mathrm{L}}(\tilde{ \boldsymbol{y}}^{\mathrm{L}}-\boldsymbol{Z}^{\mathrm{L}}\boldsymbol{\beta}^{ \dagger}),$ (3) $$

where $\boldsymbol{W}^{\mathrm{H}}\in\mathbb{R}^{N_{\rm{H}}\times N_{\rm{H}}}$ and $\boldsymbol{W}^{\mathrm{L}}\in\mathbb{R}^{N_{\rm{L}}\times N_{\rm{L}}}$ are the diagonal matrices whose $n$th diagonal elements represent the sample weights for the $n$th perturbation; $\Omega_{\rm{H}}$ and $\Omega_{\rm{L}}$ are the regularizers for the HiFAs and LoFAs, respectively; $\lambda_{\rm{H}}\geq 0$ and $\lambda_{\rm{L}}\geq 0$ are the regularization strengths.

### 3.2 Joint Optimization with Consistency Constraints

Although the HiFAs and LoFAs provide different levels of explanations, these explanations for the same black-box model should be consistent between them.
From the linearity of the surrogate models and the fact that each high-level feature can be decomposed into low-level features, the following property is expected to be satisfied:

###### Property 1 (Consistency between two-level feature attributions) .

$$ $\alpha_{j}=\sum_{d=1}^{D_{j}}\beta_{jd}\quad(\forall j\in[J]).$ (4) $$

The two surrogate models (1) satisfying the consistency property behave equivalently for the simplified inputs $\boldsymbol{z}^{\mathrm{H}}$ and $\boldsymbol{z}^{\mathrm{L}}$ such that if $z^{\mathrm{H}}_{j}=0$ then $\boldsymbol{z}^{\mathrm{L}}_{j}=\boldsymbol{0}_{D_{j}}$, and if $z^{\mathrm{H}}_{j}=1$ then $\boldsymbol{z}^{\mathrm{L}}_{j}=\boldsymbol{1}_{D_{j}}$ where $\boldsymbol{0}_{D_{j}}$ and $\boldsymbol{1}_{D_{j}}$ are the $D_{j}$-dimensional zero and one vectors, respectively.

The consistency property is essential to provide consistent and convincing explanations to humans.
However, it is often not satisfied for two reasons in practice.
First, the number of perturbations is insufficient to accurately estimate the feature attributions because the number of queries to the model $f$ is often limited due to the computational time and request costs.
Second, in the predictions for the perturbations, the behaviors of the model $f$ can differ between when the high-level features are masked out and when the low-level ones are masked out due to missingness bias [].
To overcome these problems, the proposed method estimates the HiFAs and LoFAs simultaneously by solving the following optimization with consistency constraints:

$$ $\displaystyle\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}}^{\dagger}$ $\displaystyle=\mathop{\rm argmin}\limits_{\boldsymbol{\alpha},\boldsymbol{ \beta}^{\dagger}}\mathcal{L}_{\mathrm{H}}(\boldsymbol{\alpha})+\mathcal{L}_{ \mathrm{L}}(\boldsymbol{\beta}^{\dagger})+\lambda_{\rm{H}}\Omega_{\rm{H}}( \boldsymbol{\alpha})+\lambda_{\rm{L}}\Omega_{\rm{L}}(\boldsymbol{\beta}^{ \dagger})\quad\mathrm{s.t.}\quad\alpha_{j}=\sum_{d=1}^{D_{j}}\beta_{jd}\quad( \forall j\in[J]).$ (5) $$

The consistency constraints bridge the two surrogate models, forcing them to behave equivalently.
This helps complement the insufficiency of the queries to the model and mitigate the negative effects of the missingness bias on the estimation of the HiFAs and LoFAs.

We solve the optimization based on the alternating direction method of multipliers (ADMM) [].
The detailed derivation of the optimization algorithm is provided in Appendix A.
An advantage of employing the ADMM is that despite the interdependence of $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}^{\dagger}$ caused by the consistency constraints, they can be estimated independently as in (2) and (3).
In addition, the solution has another merit in that we can implement various types of regularizations and constraints for $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$, such as sparse regularization and non-negative constraints in $\Omega_{\rm{H}}$ and $\Omega_{\rm{L}}$.
In this paper, we instantiate the proposed method with the LIME-like formulation, that is, we use the cosine kernel for calculating the sample weights $\boldsymbol{W}^{\mathrm{H}}$ and $\boldsymbol{W}^{\mathrm{L}}$ and the $\ell_{2}$ regularization for $\Omega_{\rm{H}}$ and $\Omega_{\rm{L}}$.
The optimization algorithm for this instantiation is provided in Algorithm 1 in Appendix A.

###### Property 1 (Consistency between two-level feature attributions) .

##### Computational Complexity.

In the proposed method, the dominant computation cost is brought by the predictions of the black-box model $f$ for the perturbations, whose computational time complexity is $O((N_{\rm H}+N_{\rm L})Q)$ where $N_{\rm H}$ and $N_{\rm L}$ are the numbers of perturbations for the HiFAs and LoFAs, respectively, and $Q$ is the computational time complexity of $f$ in prediction once.
$Q$ is often large when executing large models and models provided as cloud services.
Therefore, estimating the HiFAs and LoFAs accurately with small $N_{\rm H}$ and $N_{\rm L}$ is crucial.
In the experiments in Section 4, we demonstrate that the proposed method can estimate high-quality HiFAs and LoFAs even when $N_{\rm{H}}$ and $N_{\rm{A}}$ are small.
A detailed discussion on the computational time complexity is provided in Appendix B.

## 4 Experiments

We conducted experiments on two tasks, image classification in an MIL setting and text classification using language models, to evaluate the effectiveness of the proposed method, referred to as Consistent Two-level Feature Attribution (C2FA).
In the experiments, we implemented the proposed method in Algorithm 1 in Appendix A.
Its hyperparameters, $\lambda_{\rm{H}}$, $\lambda_{\rm{L}}$, and $\mu_{1}$, were tuned using the validation subset of each dataset within the following ranges: $\lambda_{\rm{H}},\lambda_{\rm{L}}\in\{0.1,1\}$, and $\mu_{2}\in\{0.001,0.01,0.1\}$.
The remaining hyperparameters were set to $\mu_{1}=0.1$, $\epsilon_{1}=\epsilon_{2}=10^{-4}$, respectively.
All the experiments were conducted on a server with an Intel Xeon Gold 6148 CPU and an NVIDIA Tesla V100 GPU.

##### Comparing Methods.

As comparing methods, we used the following five methods, named LIME [], MILLI [], Bottom-Up LIME (BU-LIME), Top-Down LIME (TD-LIME), and Top-Down MILLI (TD-MILLI).
With LIME, we estimated the HiFAs and LoFAs separately by solving (2) and (3), respectively, where we used the cosine kernel for the sample weights and $\ell_{2}$ regularization for $\Omega_{\rm{H}}$ and $\Omega_{\rm{L}}$.
Hence, LIME can be regarded as the proposed method without the consistency constraints.
MILLI is the state-of-the-art instance attribution method in the MIL setting, which was proposed for estimating the HiFAs only.
Therefore, we estimated the LoFAs in MILLI as with LIME.
With BU-LIME, we first estimated the LoFAs using LIME and then calculated the HiFAs of each high-level feature by summing the LoFAs associated with the high-level feature.
This method always satisfies the consistency property because the HiFAs are calculated from the LoFAs.
With TD-LIME and TD-MILLI, we first estimated the HiFAs using LIME and MILLI, respectively.
Then, for the $j$th high-level feature, we determined the FAs associated with it, $\boldsymbol{\beta}_{j}$, with the samples from the normal distribution with the mean of the $j$th HiFA $\alpha_{j}$ and the standard deviation of $1/D_{j}$.
Finally, by selecting the $d$th low-level feature at random and replacing it with $\beta_{jd}=\alpha_{j}-\sum_{d^{\prime}\in[D_{j}]\backslash\{d\}}\beta_{jd^{
\prime}}$, we obtained the LoFAs associated with the $j$th high-level feature such that they satisfy the consistency property.

### 4.1 Image Classification in Multiple Instance Learning

Figure: (a)

##### Dataset.

We constructed an MIL dataset from the Pascal VOC semantic segmentation dataset [] that allows us to evaluate the estimated HiFAs and LoFAs with the ground-truth instance- and pixel-level labels.
With the training subset of the dataset, each sample (bag) has from three to five images (high-level features) drawn at random from the training subset of the Pascal VOC.
Here, low-level features correspond to regions (super-pixels) of each image, which are obtained by the quick shift algorithm [].
Each bag is labeled positive if at least an image in the bag is associated with “cat” label and negative otherwise.
Also, each image pixel is labeled positive if the pixel is associated with “cat” label and negative otherwise.
We used the instance- and pixel-level supervision only for evaluation.
Similarly, we constructed validation and test subsets whose samples contain images from the training and test subsets of the Pascal VOC, respectively.
The number of samples in training, validation, and test subsets is 5,000, 1,000, and 2,000, respectively, and the positive and negative samples ratio is equal.

##### Black-box Model.

We used DeepSets permutation-invariant model [] with ResNet-50 [] as black-box model $f$ to be explained.
We describe the implementation details of the model in Appendix C.1.
Here, the test accuracy of the model was 0.945.

##### Quantitative Evaluation.

We assessed the estimated HiFAs and LoFAs in terms of correctness, faithfulness, and consistency.
The correctness is evaluated using the ground-truth instance- and pixel-level labels.
Following the evaluation in the MIL study [], we evaluated the estimated HiFAs with normalized discounted cumulative gain (NDCG).
For the estimated LoFAs, as with the evaluation of the LoFAs for single image classification [], we evaluated them as the predictions of the pixel-level labels by the area under ROC curve (AUROC) in the binary semantic segmentation manner.
In the faithfulness evaluation, we assessed whether the estimated HiFAs and LoFAs are faithful to the behaviors of the model $f$ based on insertion and deletion metrics.
The insertion and deletion metrics evaluate the change in the predictions of the model $f$ when features deemed important in the LoFAs are gradually added and removed from the sample, respectively [].
In our experiments, we gradually add and remove the low-level features across all the high-level features in descending order of their LoFAs.
Also, for the HiFAs, we add and remove the high-level features instead of the low-level ones, respectively.
In terms of the consistency evaluation, we used the following two metrics.
The first one is the consistency between the estimated HiFAs and LoFAs, which is calculated with $\|\boldsymbol{\alpha}-\boldsymbol{M}\boldsymbol{\beta}^{\dagger}\|^{2}$ used to calculate the penalty for the consistency constraints in (A).
The second one is the agreement of the most important high- and low-level feature (MIHL), which is calculated by the ratio that the high-level feature of the highest HiFA is identical to the one associated with the low-level feature of the highest LoFA.

We evaluated the above metrics using only the samples with the positive bag label because we could not evaluate the correctness of those with the negative bag label.
We ran the evaluations three times with different random seeds and reported the average scores and their standard deviation.

#### 4.1.1 Results

Figure 2(a) shows the NDCG and deletion scores of the estimated HiFAs over various numbers of perturbations for the LoFAs, $N_{\rm{L}}$, where we fixed the number of perturbations for the HiFAs, $N_{\rm{H}}=5$.
We found that the proposed method (C2FA) consistently achieved the best NDCG and deletion scores, and the superiority of the proposed method is especially noticeable when $N_{\rm{L}}$ is small.
Although BU-LIME improved the scores as $N_{\rm{L}}$ increased, the scores were still lower than those of the proposed method.
Since the other comparing methods estimate the HiFAs without the effects of the LoFAs, their scores were constant regardless of the value of $N_{\rm{L}}$.
In Appendix C.2, we show that similar results were obtained in terms of the insertion metric.
In addition, when we fixed $N_{\rm{H}}=20$, the methods other than BU-LIME equally achieved the highest NDCG and insertion scores regardless of $N_{\rm{L}}$ because $N_{\rm{H}}$ was sufficiently large to estimate the HiFAs accurately.

Figure 2(b) shows the AUROC and deletion scores of the estimated LoFAs over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=20$.
When $N_{\rm{L}}$ is small, we found that the proposed method significantly achieved the highest AUROC and deletion scores.
In particular, the AUROC score of the proposed method at $N_{\rm{L}}=50$ was much the same as those of the second-best methods, LIME, MILLI, and BU-LIME, at $N_{\rm{L}}=150$, and the deletion score of the proposed method at $N_{\rm{L}}=50$ was much the same as that of the second-best methods at $N_{\rm{L}}=100$.
These results show that the proposed method is very efficient for the number of queries to the model $f$ owing to the simultaneous estimation of the HiFAs and LoFAs.

Figure: Figure 3: Example of the estimated HiFAs and LoFAs on the image classification task when $N_{\rm{H}}=20$ and $N_{\rm{L}}=50$. The input is shown on the first row, where the image with the red border is the positive instance. The LoFAs of super-pixels estimated by the proposed method and LIME are shown on the second and third rows, respectively, where the green color’s intensity indicates the magnitude of the LoFA.

Figure 2(c) shows the consistency scores and the agreement scores of MIHL over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=20$.
Here, the consistency scores of BU-LIME, TD-LIME, and TD-MILLI are always zero by definition.
We found that the consistency scores of LIME and MILLI were worse because they estimated the HiFAs and LoFAs separately.
On the other hand, those of the proposed method were nearly zero, which means that the estimated HiFAs and LoFAs satisfied the consistency property.
With the agreement scores of MIHL, we found that the proposed method outperformed the other methods regardless of the values of $N_{\rm{L}}$, and the differences in the scores were especially noticeable at the small $N_{\rm{L}}$ values, i.e., $N_{\rm{L}}\leq 150$.

We visualize an example of the estimated HiFAs and LoFAs by the proposed method and the best-comparing method, LIME, in Figure 3.
Here, we only display the LoFAs larger than 0.1 for ease of understanding.
The figure shows that the proposed method assigned a high LoFA to the super-pixel in
the high-level feature with the positive and highest HiFA (HiFA = 0.89), although LIME assigned high LoFAs to the super-pixels in the negative instances.
The critical difference between the two methods is whether the HiFAs and LoFAs are estimated simultaneously or separately.
Since both the proposed method and LIME assigned the highest HiFA to the positive instance correctly, the result indicates that estimating the HiFAs and LoFAs simultaneously is effective.
Similar results were obtained in other examples shown in Appendix C.3.

### 4.2 Text Classification Using Language Models

Another practical application of the proposed method is to explain the attributions of sentences and the words they contain in text classification with language models.

##### Dataset.

For evaluation, we constructed a dataset whose validation and test subsets are made of 500 and 1,000 product review texts extracted randomly from the training and test subsets of the Amazon reviews dataset [], respectively.
Each sample in the dataset is made of multiple sentences regarded as high-level features, where each sentence is represented as a sequence of words regarded as low-level features, and the sample label represents the review’s polarity, positive or negative.

##### Black-box Model.

To simulate access to black-box language models provided as cloud services, we experimented using BERT [] with the weights fine-tuned on the original Amazon reviews dataset, which is provided on Hugging Face [].
The test accuracy of the model is 0.947.
When masking a word in the input to generate perturbed inputs, we replaced the word with the predefined mask token [MASK].
Similarly, when masking a sentence, we replaced all the words in the sentence with the mask token.

##### Quantitative Evaluation.

Because no ground-truth labels for HiFAs and LoFAs are available in the dataset, we evaluated the estimated HiFAs and LoFAs only in terms of faithfulness and consistency, as with Section 4.1.

#### 4.2.1 Results

Figure: (a)

Figure 4(a) shows the deletion scores of the estimated HiFAs and LoFAs over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=5$ and $50$, respectively.
With the deletion scores of the HiFAs, although the scores of the proposed method were equal to or worse than those of MILLI and TD-MILLI at $N_{\rm{L}}\leq 150$, the proposed method achieved the best at $N_{\rm{L}}\geq 200$.
We found that in this task, the LIME-based methods, including the proposed method, were worse than the MILLI-based methods at the small $N_{\rm{L}}$ values.
As $N_{\rm{L}}$ increased, the proposed method benefited from the consistency constraints and became the only LIME-based method that outperformed the MILLI-based methods.
In Appendix D.1, we show that similar results were obtained in terms of the insertion metric, and when we fixed $N_{\rm{H}}=50$, the scores did not change regardless of the values of $N_{\rm{L}}$ because $N_{\rm{H}}$ was sufficiently large to estimate the HiFAs accurately.
With the deletion scores of the LoFAs, the proposed method outperformed the other methods regardless of the values of $N_{\rm{L}}$.

Figure 4(b) shows the consistency scores and the agreement scores of MIHL over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=50$.
Again, in this task, the consistency scores of the proposed method were nearly zero regardless of the values of $N_{\rm{L}}$.
With the agreement scores of MIHL, the proposed method kept high scores regardless of the values of $N_{\rm{L}}$, although the scores of BU-LIME were slightly better than the proposed method at $N_{\rm{L}}\leq 100$.

Figure: Figure 5: Example of the estimated HiFAs and LoFAs for a negative review text when $N_{\rm{H}}=50$ and $N_{\rm{L}}=50$. The review text is shown at the top, and the HiFAs (left) and the top-5 highest LoFAs (right) estimated by each method are shown at the bottom. Here, the words on the pink background in the review text are those appearing in the chart of the LoFAs.

Figure 5 shows an example of the HiFAs and LoFAs estimated by the proposed method and the second-best method, BU-LIME.
In the example, we fixed at $N_{\rm{H}}=50$ and $N_{\rm{L}}=50$; that is, $N_{\rm{L}}$ is insufficient to estimate the LoFAs accurately.
We found that although the comparing method assigned higher LoFAs to the words in the second sentence (S2), the proposed method assigned higher LoFAs to the words in the first sentence (S1).
This result is because the proposed method can regularize the LoFAs by exploiting the fact that S1 has a high HiFA via the consistency constraints.
Other examples are shown in Appendix D.3.

## 5 Limitations and Broader Impacts

A possible limitation of the proposed method is that the quality of the HiFAs and LoFAs may be worse in cases where the consistency property is inherently not satisfied.
For example, they may happen when the HiFAs and LoFAs are estimated with the combination of different approaches, such as MILLI and LIME, and when the behaviors of the black-box model vary significantly between perturbed inputs that high- and low-level features are partially masked.
To detect such an undesirable situation early, monitoring the losses of the surrogate models, $\mathcal{L}_{\mathrm{H}}$ in (2) and $\mathcal{L}_{\mathrm{L}}$ in (3), is effective because they are likely to be worse even if the objective (5) is minimized.

Our work contributes to improving the transparency of black-box models.
However, it should be noted that high-quality feature attributions may give hints about stealing the information that the model’s providers want to hide, such as the training data and the model’s decision-making process.
To prevent such risks, it is essential to establish guidelines that ensure that the feature attributions are not used for malicious purposes.

## 6 Conclusion

We proposed a model-agnostic local explanation method for nested structured inputs, which explains two-level feature attributions, referred to as HiFAs and LoFAs, simultaneously.
We hypothesized that the consistency property naturally derived from the characteristics of the surrogate models is essential to produce explanations that are accurate, faithful and consistent between HiFAs and LoFAs with a smaller number of queries to the model.
Then, we presented an optimization algorithm that estimates the HiFAs and LoFAs while forcing them to ensure the consistency property.
We demonstrated that the proposed method can produce high-quality explanations query-efficiently in the experiments on image classification in multiple instance learning and text classification using large language models.
In future work, we will expand the applicability of the proposed method by extending it to tasks with three or more levels of nested features, such as multi-multi instance learning [].

### Acknowledgments

This work was supported by JSPS KAKENHI Grant Number 22K17953.

## Appendix A Optimization Algorithm

Our objective to estimate the HiFAs and LoFAs simultaneously is as follows:

$$ $\displaystyle\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}}^{\dagger}$ $\displaystyle=\mathop{\rm argmin}\limits_{\boldsymbol{\alpha},\boldsymbol{ \beta}^{\dagger}}\mathcal{L}_{\mathrm{H}}(\boldsymbol{\alpha})+\mathcal{L}_{ \mathrm{L}}(\boldsymbol{\beta}^{\dagger})+\lambda_{\rm{H}}\Omega_{\rm{H}}( \boldsymbol{\alpha})+\lambda_{\rm{L}}\Omega_{\rm{L}}(\boldsymbol{\beta}^{ \dagger})\quad\mathrm{s.t.}\quad\alpha_{j}=\sum_{d=1}^{D_{j}}\beta_{jd}\quad( \forall j\in[J]).$ (6) $$

We solve the optimization based on the alternating direction method of multipliers (ADMM) [].
By introducing auxiliary variables $\bar{\boldsymbol{\alpha}}\in\mathbb{R}^{J}$ and $\bar{\boldsymbol{\beta}}^{\dagger}\in\mathbb{R}^{D^{\dagger}}$ and Lagrange multipliers $\boldsymbol{v}_{1}\in\mathbb{R}^{J}$, $\boldsymbol{v}_{2}\in\mathbb{R}^{D^{\dagger}}$, and $\boldsymbol{v}_{3}\in\mathbb{R}^{J}$ based on the ADMM manner, our objective is rewritten as follows:

$$ $\displaystyle\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}}^{\dagger}= \mathop{\rm argmin}\limits_{\boldsymbol{\alpha},\boldsymbol{\beta}^{\dagger}} \mathcal{L}_{\mathrm{H}}(\boldsymbol{\alpha})+\mathcal{L}_{\mathrm{L}}( \boldsymbol{\beta}^{\dagger})+\lambda_{\rm{H}}\Omega_{\rm{H}}(\bar{\boldsymbol {\alpha}})+\lambda_{\rm{L}}\Omega_{\rm{L}}(\bar{\boldsymbol{\beta}}^{\dagger})$ $\displaystyle\quad+\boldsymbol{v}_{1}^{\top}\boldsymbol{h}_{1}(\boldsymbol{ \alpha},\bar{\boldsymbol{\alpha}})+\boldsymbol{v}_{2}^{\top}\boldsymbol{h}_{2} (\boldsymbol{\beta}^{\dagger},\bar{\boldsymbol{\beta}}^{\dagger})+\boldsymbol{ v}_{3}^{\top}\boldsymbol{h}_{3}(\boldsymbol{\alpha},\boldsymbol{\beta}^{ \dagger})$ $\displaystyle\quad+\frac{\mu_{1}}{2}\left\{\|\boldsymbol{h}_{1}(\boldsymbol{ \alpha},\bar{\boldsymbol{\alpha}})\|^{2}+\|\boldsymbol{h}_{2}(\boldsymbol{ \beta}^{\dagger},\bar{\boldsymbol{\beta}}^{\dagger})\|^{2}\right\}$ $\displaystyle\quad+\frac{\mu_{2}}{2}\|\boldsymbol{h}_{3}(\boldsymbol{\alpha}, \boldsymbol{\beta}^{\dagger})\|^{2},$ (7) $$

where $\boldsymbol{h}_{1}(\boldsymbol{\alpha},\bar{\boldsymbol{\alpha}})=\boldsymbol{
\alpha}-\bar{\boldsymbol{\alpha}}$, $\boldsymbol{h}_{2}(\boldsymbol{\beta}^{\dagger},\bar{\boldsymbol{\beta}}^{
\dagger})=\boldsymbol{\beta}^{\dagger}-\bar{\boldsymbol{\beta}}^{\dagger}$, $\boldsymbol{h}_{3}(\boldsymbol{\alpha},\boldsymbol{\beta}^{\dagger})=
\boldsymbol{\alpha}-\boldsymbol{M}\boldsymbol{\beta}^{\dagger}$.
Here, $\boldsymbol{M}\in\{0,1\}^{J\times D^{\dagger}}$ is a binary matrix to add up the LoFAs associated with the same high-level feature where we set to $M_{jd}=1$ if the $d$th feature of the concatenated input $\boldsymbol{x}^{\dagger}$ belongs to the $j$th high-level feature $\boldsymbol{x}_{j}$, and $M_{jd}=0$ otherwise.
The hyperparameters $\mu_{1}\geq 0$ and $\mu_{2}\geq 0$ are the penalty parameters for the regularization and the consistency constraint, respectively.

The optimization of (A) is performed by alternating the updates of the variables iteratively.
We summarize the optimization algorithm using $\ell_{2}$ regularization for $\Omega_{\rm{H}}$ and $\Omega_{\rm{L}}$ in Algorithm 1.
Here, $\boldsymbol{I}_{J}$ and $\boldsymbol{I}_{D^{\dagger}}$ are identity matrices of size $J$ and $D^{\dagger}$, respectively, and in Line 9, the variables at the zeroth step are initialized with zero.
The algorithm is terminated when $\|\bar{\boldsymbol{\alpha}}^{t-1}-\bar{\boldsymbol{\alpha}}^{t}\|^{2}+\|\bar{
\boldsymbol{\beta}}^{\dagger}{}^{t-1}-\bar{\boldsymbol{\beta}}^{\dagger}{}^{t}
\|^{2}<\epsilon_{1}$ and $\|\boldsymbol{h}_{1}(\boldsymbol{\alpha}^{t},\bar{\boldsymbol{\alpha}}^{t})\|^
{2}+\|\boldsymbol{h}_{2}(\boldsymbol{\beta}^{\dagger}{}^{t},\bar{\boldsymbol{
\beta}}^{\dagger}{}^{t})\|^{2}+\|\boldsymbol{h}_{3}(\boldsymbol{\alpha}^{t},
\boldsymbol{\beta}^{\dagger}{}^{t})\|^{2}<\epsilon_{2}$ where $\epsilon_{1},\epsilon_{2}\geq 0$ are hyperparameters.
The other hyperparameters of the algorithm are $\lambda_{\rm{H}}$, $\lambda_{\rm{L}}$, $\mu_{1}$, and $\mu_{2}$.

Figure: Algorithm 1 Estimating consistent two-level feature attributions (C2FA) with $\ell_{2}$ regularization

## Appendix B Computational Time Complexity

The computational time complexity of Algorithm 1 is split into three parts.
The first part is the predictions for the perturbed inputs (Line 3), which is $O((N_{\rm{H}}+N_{\rm{L}})Q)$ where $Q$ is the computational cost of the model $f$ in prediction.
The second part is the pre-computation before the iterations (Lines 4–8), which is $O(J^{3}+D^{\dagger}{}^{3}+J^{2}N_{\rm{H}}+JN_{\rm{H}}^{2}+D^{\dagger}{}^{2}N_{
\rm{L}}+D^{\dagger}N_{\rm{L}}^{2})$.
The third part is the iterations (Lines 11–20), which is $O(TJ^{2}D^{\dagger}+TJD^{\dagger}{}^{2})$ where $T$ is the number of iterations.
Compared with estimating the HiFAs and LoFAs by solving (2) and (3) separately,
the third part is an additional computational cost in the proposed method.
However, because one wants to execute the model on low-resource devices and cloud services, $Q$ is often large; consequently, the first part could be dominant.
Therefore, estimating the HiFAs and LoFAs accurately with small $N_{\rm{H}}$ and $N_{\rm{L}}$, i.e., small amounts of perturbed inputs, is crucial in practical situations.
In the experiments in Section 4, we demonstrate that the proposed method can estimate high-quality HiFAs and LoFAs even when $N_{\rm{H}}$ and $N_{\rm{L}}$ are small.
In Appendix D.2, we show that the actual computational time scales linearly with $N_{\rm{H}}$ and $N_{\rm{L}}$ as with estimating the HiFAs and LoFAs separately.

## Appendix C Experiments on Image Classification in Multiple Instance Learning

### C.1 Implementation Details of Black-box Model

We defined the DeepSets permutation-invariant model [] as a black-box model $f$ to be explained.
According to [], the model $f$ comprises two components: a representation function that transforms each instance, $\phi$, and a non-linear network that produces predictions from the extracted representation, $\rho$.
We used ResNet-50 [] pre-trained on ImageNet as the representation function $\phi$ and two-layer multi-layer perceptron (MLP) as the non-linear network $\rho$.
Here, in $\rho$, we used the ReLU activation function for the first layer and the softmax function for the second layer.
Also, the number of hidden units in the MLP was set to 1,024.
The model first extracts the representation of each instance using $\phi$, then adds them up into a single representation, and finally, outputs a prediction by applying $\rho$ to the aggregated single representation.
We trained the model using our MIL image classification dataset with Adam optimizer [] with a learning rate of 0.001, a batch size of 32, and a maximum epoch of 300.
The test accuracy of the model was 0.945.

### C.2 Additional Quantitative Evaluation

Figure: Figure 6: Insertion scores (higher is better) of the estimated HiFAs on the image classification task. The error bars represent the standard deviations of the scores over three runs with different random seeds.

Figure 6 shows the insertion scores of the estimated HiFAs over various numbers of perturbations for the LoFAs, $N_{\rm{L}}$, where we fixed the number of perturbations for the HiFAs, $N_{\rm{H}}=5$.
As with the deletion scores in Figure 2(a), the proposed method consistently achieved the best insertion scores.

Figure: Figure 7: NDCG, insertion, and deletion scores of the estimated HiFAs on the image classification task when the number of perturbed instances $N_{\rm{H}}$ is 20.

Figure 7 shows the NDCG, insertion, and deletion scores of the estimated HiFAs over various $N_{\rm{L}}$, where we fixed $N_{\rm{H}}=20$.
This result shows that the methods other than BU-LIME equally achieved the highest NDCG and insertion scores regardless of $N_{\rm{L}}$ because $N_{\rm{H}}$ was sufficiently large to estimate the HiFAs accurately.

### C.3 Additional Examples of Estimated Feature Attributions

Figure: Figure 8: Two additional examples of the estimated HiFAs and LoFAs in the image classification task when $N_{\rm{H}}=20$ and $N_{\rm{L}}=50$. The input is shown on the first row, where the image with the red border is the positive instance. The HiFAs of super-pixels estimated by the proposed method (C2FA) and LIME are shown on the second and third rows, respectively, where the intensity of the green color indicates the magnitude of the LoFA. Also, the score at the top of each subplot indicates the value of the estimated HiFA for the instance.

Figure 8 shows additional examples of the estimated HiFAs and LoFAs by the proposed method and the best-comparing method, LIME, on the image classification tasks.
In the setting where $N_{\rm{H}}=20$ and $N_{\rm{L}}=50$, the HiFAs tend to be estimated accurately, and the LoFAs tend to be estimated inaccurately because $N_{\rm{L}}=50$ is small.
Therefore, LIME tended to assign high LoFAs to incorrect regions.
On the other hand, the proposed method was able to assign high LoFAs to correct regions by complementing the insufficiency of $N_{\rm{L}}$ with the accurate HiFAs.

## Appendix D Experiments on Text Classification Using Language Models

### D.1 Additional Quantitative Evaluation

Figure: Figure 9: Insertion scores of (left) the estimated HiFAs and (right) the estimated LoFAs on the text classification task (higher is better).

Figure: Figure 10: Insertion (higher is better) and deletion (lower is better) scores of the estimated HiFAs on the text classification task when $N_{\rm{H}}=50$.

Figure 9 shows the insertion scores of the estimated HiFAs and LoFAs over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=5$ and $50$, respectively.
With the insertion scores of the HiFAs, the proposed method became better than the MILLI-based methods as $N_{\rm{L}}$ increased, as with the deletion scores in Figure 4(a).
With the insertion scores of the LoFAs, the proposed method outperformed the other methods regardless of the values of $N_{\rm{L}}$.

Figure 10 shows the insertion and deletion scores of the estimated HiFAs over various values of $N_{\rm{L}}$ where we fixed $N_{\rm{H}}=50$.
In the setting where $N_{\rm{H}}$ is sufficiently large, the MILLI-based methods are superior to the LIME-based methods, including the proposed method, on the text classification task.
This result suggests that the better approach for this task would be to formulate the estimators of the HiFAs (2) and LoFAs (3) with the MILLI-based sample weight kernel and optimize them simultaneously with the proposed consistency constraints.
However, since no study has applied the idea of MILLI for estimating the LoFAs, we left the attempt for future work.

### D.2 Computational Time

Figure: Figure 11: Average computational time of estimating LoFAs using the proposed method on the text classification task when $N_{\rm{H}}=50$.

Figure 11 shows the average computational time of estimating the LoFAs using the proposed method on the text classification task when $N_{\rm{H}}=50$.
From the figure, we can see that the computational time of the proposed method scales linearly with $N_{\rm{L}}$ as with estimating the HiFAs and LoFAs separately.
Here, the computational time of TD-LIME and TD-MILLI is constant against $N_{\rm{L}}$ because they estimate the HiFAs only.

### D.3 Additional Examples of Estimated Feature Attributions

Figure: Figure 12: Examples of the estimated HiFAs and LoFAs for positive review texts when $N_{\rm{H}}=50$ and $N_{\rm{L}}=50$. The review text is shown at the top, and the HiFAs (left) and the top-5 highest LoFAs (right) estimated by each method are shown at the bottom. Here, the words on the pink background in the review text are those appearing in the chart of the LoFAs.

Figure 12 shows additional examples of the HiFAs and LoFAs estimated by the proposed method and the three comparing methods on the text classification task.
The result shows that the sentence with the highest HiFA and the sentence associated with the word with the highest LoFA were consistent in the proposed method.
However, the remaining methods did not show such consistency.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: - line 237. Why does ADMM have the advantage of estimating $\mathcal{\alpha}$ and $\mathcal{\beta}$ independently even though there is the interdependence?
- line 301-303. Does it mean the LoFAs for their higher level feature attribution are just randomly selected based on the corresponding HiFA? What if you take the independently computed LoFA (without the constraint), and distribute each HiFA  proportional to the independently computed LoFA?
- How do bottom-up version of other methods like BU-SHAP, BU-RISE, BU-IntGrad do?
soundness: 2
strengths: - The paper proposes to estimate HiFAs and LoFAs simultaneously, while previous works have only estimated them separately.
- The consistency property proposed by the authors is a reasonable property for HiFAs and LoFAs.
- The paper does experiments that ablate different important properties on both image and text datasets.
- The proposed method performed better than all baselines in all the metrics, and can get better attributions with a smaller number of perturbations.
- The method can be used in both text classification with multiple sentences (inputing as one input) and MIL where there are multiple input images.
summary: The authors propose a method to get high level and low level feature attributions for image classification in multiple instance learning and text classification with multiple sentences using language models. They use a local surrogate model in a LIME-like style, while optimizing for aggregating both high-level and low-level features for prediction. They also include a consistency constraint to enforce that all the attribution scores of low-level features that belong to a high-level feature sum up to that feature. They evaluate on Pascal VOC for image and Amazon reviews for text datasets, using faithfulness, correctness, and consistency metrics, and show that their method outperform baselines.
weaknesses: - The high-level features are constrained to predefined image/sentence and cannot be dynamically chosen by the method.
- With the bottom-up baselines, we can actually convert any feature attribution method to the BU version of it. The paper only compare with different versions of LIME and MILLI. It would be more convincing that faithfulness and consistency cannot be achieved together with more baselines such as (BU-)SHAP, (BU-)RISE[1], IntGrad[2].
- Insertion and deletion are only proxy metrics for faithfulness. Although there is no absolute best metric for faithfulness, it would be good to clarify that they are proxies.
- The object segments in VOC dataset are ground truths for the objects, but not necessarily the model explanation. The model can be using the unintended features to make the prediction. For example, if the wolf always appear with snow in the dataset, the model can be wrongly using the snow for predicting the class fox, but it doesn't mean that attributing to the snow is a wrong attribution. It can be the correct attribution for a model that uses spurious correlation.

[1] Vitali Petsiuk and Abir Das and Kate Saenko. RISE: Randomized Input Sampling for Explanation of Black-box Models. BMVC 2018

[2] Mukund Sundararajan, Ankur Taly, Qiqi Yan. Axiomatic Attribution for Deep Networks. ICML 2017

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: - Lines 89-91: The paper states that estimating HiFAs and LoFAs separately can lead to inconsistent explanations between them. How might this mismatch reduce users' trust in the model?
- Section 4.1: What would the explanation be if a bag contains more than two images featuring "cats"?
soundness: 1
strengths: - Overall, the paper is well-written and well-organized, allowing readers to follow the narrative easily.
- The HiFAs and LoFAs estimated by the proposed method in this paper are consistent.
summary: - Existing studies have primarily focused on estimating either HiFAs or LoFAs, without addressing both levels simultaneously. Current naive approaches either generate a large number of queries or produce inconsistent HiFA and LoFA estimations.
- This paper introduces a model-agnostic local explanation method that effectively leverages the nested structure of input data to estimate both levels of feature attributions simultaneously.
- Experimental results in image and text classification demonstrate that the HiFAs and LoFAs estimated by the proposed method are accurate, faithful to the behavior of black-box models, and provide consistent explanations.
weaknesses: - Lines 297-305: The settings of TD-LIME and TD-MILLI are unclear. Additional explanation is needed to help readers understand their significance.
- This paper lacks a formal introduction to the evaluation metrics NDCG (line 327) and HIML (line 339).
- Figure 3 lacks an introduction to "IA," and the font size should be enlarged.
- The experiments in this paper are conducted solely on synthetic datasets and lack results on real datasets, such as medical imaging data.
- In Figure 5, BU-LIME demonstrates a higher level of consistency between LoFAs and HiFAs compared to C2FA.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: - Just a brainfart thought, why 2 levels? How does the performance of C2FA change as the depth of the nested structure increases (e.g., to 3 or more levels)? Are there theoretical or practical limitations to extending beyond two levels? C3FA can make sense in an NLP context,  Word-level to sentence level to paragraph level.

- The paper mentions that C2FA may perform worse when the consistency property is inherently not satisfied. I feel this can be a more realistic setup, which makes C2FA less pragmatic, any justification here? 

- The current formulation assumes a fixed nested structure. How might C2FA be adapted to handle variable-length or dynamic nested structures, such as those often encountered in NLP tasks?

- The experiments focus on classification tasks. How well do you expect C2FA to generalize to regression problems or other types of model outputs?
soundness: 2
strengths: **Originality:**
- The idea of jointly estimating high-level and low-level feature attributions with consistency constraints is novel and well-motivated.

**Quality:**
- Experiments are comprehensive, evaluating on both CV and NLP tasks.
- Quantitative metrics assess different aspects like correctness, faithfulness, and consistency of the attributions.

**Clarity:**
- The paper is generally well-written with clear visualization.

**Significance:**  
- The method enables more coherent explanations for nested input structures, which are common in many real-world ML applications.
- The approach is model-agnostic and can be applied to various types of nested inputs and black-box models.
summary: This paper proposes a technique for extracting both high-level and low-level feature attributions from black-box machine learning models. The key idea is to simultaneously estimate high-level and low-level feature attributions while enforcing consistency between them through constraints, although they have not validated the assumption that high-level and low-level feature attributions show consistency for sure. The authors evaluate the method on image classification and text classification tasks, showing improvements over baselines in terms of attribution quality and query efficiency.
weaknesses: - One foundamental assumption of this paper is that “ the input features have a nested structure that consists of high- and low-level features, and each high-level feature is decomposed into multiple low-level features. ” 

 - Another important assumption is that there is consistency between low and high level features. However, what if conflicting attributions between high and low levels? For instance, when a high-level feature is deemed important, but none of its constituent low-level features appear significant. As the paper mentions that C2FA may perform worse when the consistency property is inherently not satisfied, I feel this is a more realistic consideration, that there is no consistency.

 - The paper lacks a formal theoretical analysis of the properties and guarantees of the proposed method. For instance, there is no discussion on convergence properties of the optimization algorithm or bounds on the estimation error, or discussion on the robustness, the robustness of C2FA to different types of perturbations or variations in the input structure.

 - It's unclear how the choice of hyperparameters (e.g., λ_H, λ_L, μ) affects the trade-off between consistency and individual attribution accuracy.

 - The experiments are limited to relatively small-scale problems (e.g., classifying a few images or sentences). It's not clear how well C2FA would scale to larger, more complex nested structures like full documents or large image collections.

 - The comparison with MILLI seems unfair, as MILLI is designed only for high-level attributions. A more appropriate baseline would be to combine MILLI with a low-level attribution method.

 - There's no comparison with more recent explanation methods like SHAP-based approaches or gradient-based methods adapted for nested structures.

 - The image classification experiments use a synthetic MIL dataset. It would be more convincing to see results on standard MIL benchmarks or real-world applications.

 - For text classification, only sentiment analysis is considered. Evaluating on more diverse NLP tasks would strengthen the claims of generalizability.

Meta-review: This paper introduces a model-agnostic explanation method for simultaneously estimating high-level and low-level feature attributions (HiFAs and LoFAs) in image and text classification tasks. The method uses a LIME-like local surrogate model with a consistency constraint to ensure that low-level attributions sum to their corresponding high-level features. Evaluated on Pascal VOC (images) and Amazon reviews (text), the approach outperforms baselines in faithfulness, correctness, consistency, and query efficiency, demonstrating its effectiveness in providing accurate and coherent explanations.

The reviewers raised several concerns regarding the novelty and experiments presented in the paper, which I briefly summarize below:

1. One of the comments that the reviewer made is "How do bottom-up versions of other methods like BU-SHAP, BU-RISE, BU-IntGrad do?" The response was not convincing as mentioned by the author.

2.  The settings of TD-LIME and TD-MILLI also seem unclear.

3. Experiments are conducted on synthetic datasets and lack real-world datasets.  It would be more convincing to see results on standard MIL benchmarks or real-world applications.

4. The paper lacks a formal theoretical analysis of the properties and guarantees of the proposed method.

5. The comparison with MILLI seems unfair.

6. Evaluating on more diverse NLP tasks would strengthen the claims of generalizability.

Decision: Reject