SOINTER: A NOVEL DEEP ENERGY-BASED INTERPRETATION METHOD FOR EXPLAINING STRUCTURED OUTPUT MODELS
Year: 2021

Abstract:
We propose a novel interpretation technique to explain the behavior of structured output models, which learn mappings between an input vector to a set of output variables simultaneously. Because of the complex relationship between the computational path of output variables in structured models, a feature can affect the value of output through other ones. We focus on one of the outputs as the target and try to find the most important features utilized by the structured model to decide on the target in each locality of the input space. In this paper, we assume an arbitrary structured output model is available as a black box and argue how considering the correlations between output variables can improve the explanation performance. The goal is to train a function as an interpreter for the target output variable over the input space. We introduce an energy-based training process for the interpreter function, which effectively considers the structural information incorporated into the model to be explained. The effectiveness of the proposed method is confirmed using a variety of simulated and real data sets.

text: We propose a novel interpretation technique to explain the behavior of structured output models, which learn mappings between an input vector to a set of output variables simultaneously. Because of the complex relationship between the computational path of output variables in structured models, a feature can affect the value of output through other ones. We focus on one of the outputs as the target and try to find the most important features utilized by the structured model to decide on the target in each locality of the input space. In this paper, we assume an arbitrary structured output model is available as a black box and argue how considering the correlations between output variables can improve the explanation performance. The goal is to train a function as an interpreter for the target output variable over the input space. We introduce an energy-based training process for the interpreter function, which effectively considers the structural information incorporated into the model to be explained. The effectiveness of the proposed method is confirmed using a variety of simulated and real data sets.

heading: 1 INTRODUCTION
text: The impressive prediction performance of novel machine learning methods has motivated researchers of different fields to apply these models in challenging problems. However, their complex and non-linear inherence limit the ability to explain what they have learned. Interpretation gets more attention when we want to discover the reasons behind the model’s decision and be sure about the trustworthiness and fairness of a trained machine learning model in areas such as medicine, finance, and judgment. Additionally, interpreting a model with a satisfying prediction accuracy in a scientific problem, which results in understanding relationships behind the data, leads to new knowledge about the problem domain.Murdoch et al. (2019)
In many real-world applications, the goal is to map an input variable to a high-dimensional structured output, e.g., image segmentation and sequence labeling. In such problems, the output space includes a set of statistically related random variables. As considering these dependencies can increase the prediction accuracy, many structured output models have been introduced. Many of these methods use graphical models, including random fields, to capture the structural relations between variables. Most define an energy function over these random fields, with a global minimum at the ground truth. Therefore, an inference is needed to find the best configuration of output variables for input by minimizing the energy function in the prediction step. Early efforts to utilize deep neural networks in structured output problems adopt deep networks to extract high-level features from the input vector to incorporate them in calculating the energy function Peng et al. (2009); Chen et al. (2015); Schwing & Urtasun (2015). The computational complexity of the inference step in models that use random fields limits their ability to incorporate complex structures and interactions between output variables. Recent works in Belanger & McCallum (2016); Gygli et al. (2017); Belanger et al. (2017); Graber et al. (2018) propose to adopt deep networks instead of random fields to model the structure of the output space. Nevertheless, complex interactions between problem variables in such models make their interpretation too challenging, specifically when we focus on the model behavior in predicting a single output variable.
This paper attempts to interpret a structured output model by focusing on each output variable separately. Our approach to model interpretation is based on instance-wise feature selection. Its goal is to find the relative importance of each input feature in predicting a single output variable. The subset of important features can vary across the input space. The complicated interactions between computational paths of output variables in structured output models cause critical challenges for finding a subset of important features associated with each output variable. A feature may not be used directly in the computational path of output but affects its value through relations with other outputs. To compute the importance of a feature for a target output variable, we should aggregate its effect on all output variables that are correlated to this target.
Existing approaches of model interpretation can be divided into two groups, model-based and post hoc analysis Murdoch et al. (2019). The model-based interpretation approach encourages machine learning methods that readily provide insight into what the model learned. However, it leads to simple models that are not sufficiently effective for complex structured output problems. Here we follow the post hoc analysis and try to explain the behavior of a trained, structured output model provided as a black box. Many interpretation techniques to find the importance of features as a post hoc analysis have been introduced. Works in Zhou & Troyanskaya (2015); Zeiler & Fergus (2013); Zintgraf et al. (2017) make perturbations to some features and observe their impact on the final prediction. These techniques are computationally inefficient in situations where we search for the most valuable features. Since we should perform a forward propagation for all possible perturbations, in another trend, works in Simonyan et al. (2013); Bach et al. (2015) back-propagate an importance signal from the target output through the network to calculate the critical signal of features by calculating the gradient of the target w.r.t the input features. These models are computationally more efficient than perturbation-based techniques because they need only one pass of propagating. However, they need the structure of the network to be known. As this approach may cause a saturation problem, DeepLIFT Shrikumar et al. (2017) proposes that instead of propagating a gradient signal, the difference of the output from a reference value in terms of the difference of features from a reference value to be considered. In addition to these approaches, other ideas have also been introduced in model interpretation. Authors in Ribeiro et al. (2016) introduce LIME which trains a local interpretable surrogate model to simulate the behavior of a black box model in the vicinity of a sample. It randomly selects a set of instances of the input space around that sample and obtains the black box prediction for them, and trains the surrogate model by this new dataset. Therefore this interpretable model is a good approximation of the black box around the locality of the selected sample. Shapley value, a concept from the game theory, explains how to distribute an obtained payout between coalition players fairly. The work in Lundberg & Lee (2017) proposes the kernel SHAP for approximating the shapely value for each feature as its importance for a prediction. As an information-theoretic perspective on interpretation, the work in Chen et al. (2018) proposes to find a subset of features with the highest mutual information with the output. This subset is expected to involve the most important features for the output.
Existing interpretation techniques can be applied to explain the behavior of a structured model, w.r.t. a single output, by ignoring other output variables. However, none of these approaches consider possible correlations between output variables and only analyze the marginal behavior of the black box on the target. In this paper, we attempt to incorporate the structural information between output variables during training the interpreter. As our goal is to present a local interpreter, which is trained globally as Chen et al. (2018), we train a function over the input space which returns the index of most important features for decision making about the target output. Since the value of other output variables affects the value of the target, incorporating them into the training procedure of an interpreter function may lead to higher performance and decrease our uncertainty about the black box behavior. To the best of our knowledge, this is the first time an interpreter is designed mainly for structured output models, and dependencies between output variables are considered during training the interpreter.

heading: 2 PRELIMINARIES AND MOTIVATION
text: Structured output prediction models map an arbitrary n-dimensional feature vector x ∈ X to the output y ∈ Y where y = [y1, y2, . . . , yd] includes a set of correlated variables with known and unknown complex relationships and Y shows a set of valid configurations.
Now we explain our intuition about an interpreter, which explains the behavior of a structured output model in predicting a single output variable. We assume a structured model is available as a black box about which we do not know. Our goal is to find indices of k important features of x which affect the black box prediction about the target output yt. As for different localities of the input space these indices may vary, the proposed interpreter is a function IN t(x;α) : X → {0, 1}n over the input space with a set of parameters α which returns an n-dimensional k-hot vector. In this vector, the value of 1 shows the indices of selected k important features for target output yt.
We define Θsb as the set of all parameters and hidden variables inside the structured black box. The probabilistic graphical model of Fig. 1 describes dependencies between problem variables. In this figure, x shows the input variable, ysbt and y sb −t = {ysbi |i 6= t} show black box predictions and αIN t is the set of parameters of IN t. The bidirectional edge between ysbt and ysb−t emphasizes the correlation between the outputs of a structured model. In fact αIN t is determined based on Θsb and the black box architecture, and the final prediction of the ysbt does not directly affect its value. However, here, Θsb is a latent variable which makes active paths between αIN t and output values ysbt and y sb −t. Therefore αIN t and y sb −t are dependent random variables and we have:
H(αIN t |x,ysbt ) > H(αIN t |x,ysbt ,ysb−t) (1)
where H(.|.) shows the conditional entropy. We use the strict inequality because αIN t and ysb−t are dependent random variables. The left term measures our uncertainty when we train the interpreter only by observing the target output ysbt . This inequality confirms that the uncertainty is decreased when we consider observed ysb−t during estimating αIN t . Motivated by this fact we propose a training procedure for an interpreter IN t which incorporates the structural information of the output space by observing the black box prediction on all output variables.
We call our method SOInter as we propose it to train an Interpreter specifically for Structured Output models.

heading: 3 PROPOSED METHOD
text: We consider psb(y|x) as the distribution by which the structured black box predicts the output as follows,
ysb = arg max y psb(y|x). (2)
Our goal is to train the interpreter IN t(x;α) which explores a subset of most important features that affects the value of black box prediction on the target output yt in each locality of the input space. As the desired interpreter detects the subset of most important features, we expect perturbating other ones does not change the black box prediction of the target yt. Motivated by this statement, we are encouraged to compare the black box prediction for the target output when a sample and its perturbated version are passed through the black box. The interpreter IN t(x;α) returns a k-hot vector in which the value of 1 shows the index of a selected feature. We define x̃, a perturbated
version of x, as follows,
x̃ = x IN t(x;α) (3) in which only features selected by the interpreter are included, and other ones are filled with zeros. Therefore by passing x and x̃ through the black box, we expect the value of the tth element of predictions to be the same, and we can define a penalty over the value of the target in these two situations. However, since the structure of the black box is unknown and the arg max operation in equation 2 is non-differentiable, a loss function that directly compares these two output values can not be used to find the optimal interpreter. Therefore, in the following subsection, we try to achieve a penalty according to the difference between these values for the target, which can transfer the gradient through an interpreter block.

heading: 3.1 OBTAINING A TRACTABLE LOSS FUNCTION
text: We consider ỹ as the black box prediction when masked inputs x̃ are given to the black box i.e.,
ỹ = arg max y
psb(y|x̃). (4)
We define distribution qα to estimate the probability density function of ỹ. We assume qα is from the exponential family and can be parameterized as follows,
qα(y|x) = exp(−Eq(x̃, y))∫
y′ exp(−Eq(x̃, y′)) (5)
As we define qα the distribution over the output variables when the masked input is given to the black box, Eq can be considered as an energy function describing the structural information incorporated into the black box. We train a deep neural network to estimate this energy block, using a set of samples from the input space and their associated outputs predicted by the black box. For an input feature x, the obtained energy function Eq(x, y) has the minimum value when y is equal to the black box prediction for x. The detailed architecture of this block depends on the data inherence. Different techniques to train an energy network have been introduced recently Belanger & McCallum (2016); Belanger et al. (2017); Gygli et al. (2017) which can be used to train Eq in a pre-training phase. Here we use the work in Gygli et al. (2017). Since after the pre-training phase, the only unknown parameters of qα are parameters of IN t, we show it by the index of α. Now to find the optimum value for α, we define the following penalty over the log-likelihood of qα,
SL(x, ysbt , ỹ; α) = max{0, (log qα([ỹt, ỹ−t] |x)− log qα( [ ysbt , ỹ−t ] |x) + L(ỹt,ysbt ))}.
(6)
When the target values for an input x and its perturbated version x̃ are the same, i.e. ỹt = ysbt , the penalty value is zero. Otherwise, as ỹ maximizes qα, SL(x, ysbt , ỹ; α) has a positive value which is proportional to the difference between the desired target value ysbt and the most offending answer ỹt. Using the log-likelihood of the joint distribution qα(.|x) in calculating the penalty, which ỹ−t is the most probable value for other outputs according to the qα, leads to incorporate the structural information between output variables.
Now we attempt to achieve a more simpler form of equation 6. According to equation 5 the loglikelihood of qα equals to,
log qα(y|x) = −Eq(x̃, y)− log ∫
y′ exp(−Eq(x̃, y′)). (7)
Because the second term of equation 7 for both of log qα( [ ysbt , ỹ−t ] |x) and log qα([ỹt, ỹ−t] |x) is the same, we can write the equation 6 as follows,
SL(x, ysbt , ỹ; α) = max{0, (Eq(x̃, [ ysbt , ỹ−t ] )− Eq(x̃, [ỹt, ỹ−t]) + L(ỹt,ysbt ))}. (8)
We propose to iteratively calculate the most offending answer ỹ for the current qα and then minimize the penalty function of equation 8 according to α. It is worth mentioning that we consider a constraint only over the ysbt as we intend to find the best interpreter for the target. As Eq is a deep neural network and x̃ is an element-wise multiplication of x and IN t(x;α), the gradient over the penalty of equation 8 can be back-propagated through the interpreter block.
The final proposed iterative optimization procedure for an interpreter block can be expressed as follows,
α(k) = arg min α Ep(x)[SL(x, ysbt , ỹ(k−1); α)]
ỹ(k) = arg max y psb(y|x IN t(x;α(k))) (9)
where ysb = arg maxy psb(y|x). In the first step, the expected penalty of equation 8 is minimized to find the optimum value for the parameter α. The penalty function SL is minimized when we find a value for α which makes [ ysbt ,y−t ] the strict maximum of qα(.|x) with the margin proportional to L. In the second step, the black box prediction for the input which is masked by the output of the current interpreter is calculated.
The initial value α(0) is selected randomly and its associated ỹ(0) is obtained using the second step of equation 9. The algorithm is continued until the value of the penalty SL does not considerably change which is usually obtained in less than 100 iterations. Here we consider L = I(ysbt , ỹt) which is an indicator function

heading: 3.2 THE INTERPRETER BLOCK
text: The interpreter IN t includes a deep neural network, with a set of parameters α, followed by a Gumbel-Softmax Jang et al. (2017) unit. The detailed architecture of the deep network depends on the inherence of x. The dimension of the interpreter output is the same as the feature vector x. Fig. 2 describes the architecture used for training the interpreter IN t(x, α). The output of the deep networkWα shows the importance of the elements of the feature vector x. To encourage the interpreter to find top k important features associated with the target output yt, we use the GumbelSoftmax trick as proposed in Chen et al. (2018). To obtain top k important features, we consider the output ofWα(x) as parameters of the categorical distribution. Then we can independently draw a sample for k times. Each sample is a one-hot vector in which the element with the value of 1 shows the selected feature. To have a k-hot vector, we can simply get the element-wise maximum of these one-hot vectors. However this sampling process is not differentiable and we use its continuous approximation introduced by the Gumbel-Softmax trick. Considering following random variables,
gi = − log(− log(ui)) (10)
where ui ∼ Uniform(0, 1), we can use the re-parameterization trick instead of direct sampling fromWα(x) as follows:
ci = exp{log(Wα(x)i + gi)/τ}
Σj exp{log(Wα(x)j + gj)/τ} (11)
The vector c is the continuous approximation of the sampled one-hot vector. To have k selected features, we draw k vectors cj , j = 1 . . . k and obtain their element-wise maximum as follows Chen et al. (2018),
IN t(x, α)i = maxj {c j i , j = 1 . . . k} (12)
Finally, Algorithm 1 of Appendix A summarizes what we propose to train the interpreter IN t.

heading: 4 EXPERIMENTS
text: We evaluate the performance of our proposed interpreter on both synthetic and real datasets. In section 4.1, we define two arbitrary energy functions to synthesize structured data. We compare the performance of SOInter with two well-known interpretation techniques, Lime and Kernel-Shap, which are frequently used to evaluate the performance of interpretation methods, and L2X Chen et al. (2018) which proposes an information-Theoretic method for interpretation. None of these techniques are specifically designed for structured models. Indeed, they only consider the target output and ignoring other ones. In section 4.2 and 4.3, the efficiency of SOInter is shown with two real text and image datasets.

heading: 4.1 SYNTHETIC DATA
text: Here we define two arbitrary energy functions on input vector x and output variables y, E1 and E2 in equation 13, which are linear and non-linear functions respectively according to the input features.
E1 = (x1y1 + x4)(1− y2) + (x2(1− y1) + x3)y2 E2 = (sin(x1)y1y3 + |x4|) (1− y2)y4 + ( exp(
x2 10 − 1)(1− y1)(1− y3) + x3
) y2(1− y4)
(13)
Input features are randomly generated using the standard normal distribution. Output variables are considered as binary discrete variables. For each input vector x, we found the corresponding output by the following optimization,
y∗ = arg min y E(x, y) (14)
where E shows the energy function from which we attempt to generate data. E1 describes the energy value over a structured output of size 2 and E2 describes an output of size 4. For each scenarios, we simulate input vectors with the dimension of 5, 10, 15 and 20.
For each generated dataset, we train a structured prediction energy network introduced in Gygli et al. (2017). As it has the sufficient ability to learn energy functions in equation 13, we can assume it has successfully captured the important features with a negligible error rate. We adopt each interpretation techniques to explain trained energy networks. According to equation 13 first four features affect the value of outputs. Fig. 3 compares the accuracy of results obtained by each method during the interpretation. Diagrams of Fig. 3 show results for target outputs y1 and y2 in E1 and two arbitrary outputs y3 and y4 in E2. As there may be randomness in interpretation methods, we run each interpreter five times for each dataset. Each line in the diagrams shows the average value, and the highlighted area shows the standard deviation. SOInter has an overall better performance compared to others.
As the accuracy measures the exact match of the subset of important features with ground truths, we consider an order for features and report the median rank of important ones in Fig. 4 as proposed in Chen et al. (2018). As the first four features are the solution, the desired median rank is 2.5 in all situations. As shown, SOInter has the nearest median rank to 2.5 nearly in all cases.
As the number of input features is increased, the performance of methods is generally degraded. This is because the ratio of important features compared to the size of the input vector is decreased, which can lead to confusion of the interpreter.
However, the obtained results confirm the robustness of SOInter for the more significant number of input features. Thus the proposed method is more reliable when the size of the input vector is large.

heading: 4.2 MULTI-LABEL CLASSIFICATION ON BIBTEX DATASET
text: Bibtex is a standard dataset for the multi-label classification of texts. Each sample in Bibtex involves an input feature vector corresponding to 1836 words mapped to a 159-dimensional output vector. Elements of the output vector are associated with a set of tags that describes the sample subject. We train a structured prediction energy network (SPEN) as a multi-label classifier on Bibtex with a desirable accuracy as shown in Gygli et al. (2017). A SPEN as a structured black box is a challenging benchmark for an interpreter because of its ability to capture more complicated relations between output variables. During interpreting this classifier with SOInter, we select an output variable, i.e., a tag, as a target of explanation and find the top 30 features related to this tag for each sample. According to SPEN decisions, we aggregate those top features over all samples for each tag and find the top 30 features which are expected to be correlated to this tag. Table 1 shows the general top 30 features for different 3 tags. More results are provided in Table 3 of Appendix A. As shown, word sets are meaningfully correlated to their corresponding tags. In addition, we highlight bold words that are correlated to each tag confirmed by human experts.

heading: 4.3 IMAGE SEGMENTATION ON WEIZMANN-HORSE DATASET
text: Image segmentation is another structured output learning task in which the image is partitioned into semantic regions. Here we again train a SPEN for segmentation of 24×24 Weizmann-horse dataset. Each image of this dataset is partitioned into two regions which determines the borders of the horse. During the interpretation, we consider a pixel as the target and find pixels of the image that affect the target’s output.
In Fig. 5 the pixel in [10, 10] is considered as target and the interpretation results for arbitrary images are shown. We do experiments for different numbers of important features of 5, 10, 50, and 100. The red pixel shows the target, and green ones are obtained important input features as expected green pixels are placed in the locality of the target.
Table 2 compares the accuracy and post-accuracy of the SPEN in finding the label of the target during the segmentation process. Post-accuracy measures the model performance when only the selected features are passed through the SPEN and un-selected ones are masked with zero. These measures are shown for different choices for the number of important features. The negligible difference between the accuracy and post-accuracy confirms that the interpreter selects pixels which are the most effective ones in labeling the target. In addition, the increased value of the post-accuracy in some situations shows that omitted features confuse the segmentation model, i.e. SPEN, as a noise signal. These observations show that SOInter successfully selects important features which affect the SPEN decision for the target output.

heading: 5 CONCLUSION
text: We have presented SOInter, an interpreter for explaining structured output models. We focused on a single output variable of a structured model, available as a black box, as the target. Then we train a function over the input space, which returns a subset of important features for the black box to decide on the target. This is the first time an interpreter has been designed explicitly for structured output models to the best of our knowledge. These models learn complex relations between output variables which ignoring them while interpreting a single output can decline the explanation performance. We used an energy model to learn the structural information of the black box and utilize it during the interpreter’s training. The effectiveness of SO-Inter is confirmed using synthetic and real structured datasets.

heading: A APPENDIX
text: Algorithm 1 The training procedure of the interpreter IN t(x;α) 1: function INTERPRETER-BLOCK(x, α) 2: return Gumbel-Softmax (Wα(x)) 3: end function 4: 5: function SL-CALCULATOR(x, ỹ, α) 6: x̃← x Interpreter-Block(x, α) 7: ysb ← arg maxy psb(y|x) 8: L ← |ỹt − ysbt | 9: SL ← max{0, Eq(x̃, [ ysbt , ỹ−t ] )− Eq(x̃, [ỹt, ỹ−t]) + L} 10: return SL 11: end function 12: 13: function TRAINING-INTERPRETER(t) 14: α(0) ← Sample Standard Normal distribution 15: ỹi
(0) ← arg maxy psb(y|x Interpreter-Block(xi, α(0)), for i = 1...N 16: k = 1 17: while the penalty does not change considerably do 18: α(k) = Adam-minimizerα ΣNi SL-calculator(xi, ỹi
(k−1), α) 19: ỹi
(k) = Adam-minimizery − psb(y|xi Interpreter-Block(xi, α(k))), for i = 1...N 20: k = k + 1 21: end while 22: end function

Review summaries:
The paper works on a novel problem of interpreting and explaining structured output models. The paper utilizes an energy based model to account for correlations between structured outputs and learns an interpretability block which given as input an image learns to mask it such that the energy based model would assign a similar score to the ground truth output and input as well as the ground truth output and perturbed input. In essence, the energy based model is a proxy for the actual deep neural network performing the structured prediction task. Results on a couple of datasets demonstrate that the work does better than baselines like LIME which do not utilize the correlations in the outputs modeled by the energy based model.  

The paper proposes a technique for identifying what input variables are most relevant for determining the value of a single, given output variable in structured-output (MAP) inference.  The idea is to learn an energy model that predicts which input variables are relevant to a particular structured prediction (x, y).  The authors propose to implement the energy model using a neural network followed by a Gumbel-softmax activation, and to train it by maximizing a structured hinge loss.  The proposed approach is evaluated on three datasets and compared to standard attribution techniques (LIME, SHAP, L2X).

The authors propose an energy-based training method for achieving model interpretability, which performs instance-wise feature selection. The proposed model adopts a similar approach of one of the pre-existing interpretable methods by calculating feature-level importance score with regard to each instance. The authors validate their method on synthetic and public datasets.

This paper propose a method for interpreting structured output model. The key idea is to find an "interpretation" which explains an "target" output random variable based on subset of rest of the output variables. The training objective is on finding a small subset which keeps the target output random variable invariant. The proposed methodology is applied to explain a synthetic energy function and structured prediction energy networks.