associated to the different classifiers. The search for the main hyper-parameter to (best cross validation score) was done through a grid search procedure using the GridSearchCV<fnref n="21" /> from Scikit-Learn. The values for the number of decision trees and maximum depth of the RF tested were ranging in [3,40] and [4,100] respectively.

**3.4.1 Results**

We report the following results by setting the following parameters *nb Trees*=10 and *max depth*=24 for the surrogate classifier. Each surrogate model was trained on the vicinity of an input sample *x* using different values of radius (*r*). For the MNIST dataset, the experiments were conducted on an average of 1500 to 2500 instances picked randomly. As for the rest of the datasets, all instances were used to test the approach.

**Impact of hyper-parameters on the fidelity of surrogate model**

We present in this section the results of experiments conducted on the MNIST dataset to show the impact
of the different hyper-parameters used on the fidelity of the surrogate model.

The *max_depth* represents the maximum allowed depth of each tree in the forest. Note that the deeper the tree, the more splits it has (i.e it captures more information about the data). Figure 3.8 shows the results of experiments conducted to find a suitable *max_depth* to improve the accuracy. The blue curve represents the accuracy when the classification model is built on the training dataset and the red one corresponds to the accuracy of the model on the test data. As shown on the different plots of Figure 3.8, the accuracy of RF is best for values of *max_depth* between 10 and 20.

The *ntree* parameter (also referenced to as *nb Trees*) represents the number of decision trees in RF. The classification accuracy of a RF can be improved when using a large number of trees but it also results in a more important training time. Figure 3.11 shows the results of experiments conducted to find a suitable *ntree* to balance accuracy and computation time. The green curve represents the accuracy of the classification model on the training dataset and the orange one corresponds to the accuracy of the model on the test data. As shown on Figure 3.11, the accuracy of classification is not significantly improved when *ntree* is greater than 10 but still reached at least 92%. Thus, the *ntree* was set as 10 during the evaluation.

Figure 3.9 shows the number of $CF_x$ explanations with respect to the neighborhood size $|V_x|$. The blue and red bars correspond respectively to the case when a maximum size of $|V_x|$ is used and when not. As shown in Figure 3.9, the instances having a large number of neighbors have a bigger total number of explanations, in comparison to when an upper bound for the vicinity size is used. Since in this experiment we propose local explanations, a maximum number of neighbors was set during the experimentation to preserve the "local" aspect of the explanations as well as to optimize their enumeration (all explanations).

Figure 3.10 shows the performance of RF classification model trained on a set of neighbors obtained using different radius values. We can observe that the model has good performance for the different sizes of $V_x$ and seems to not be significantly improved for neighborhoods composed of more than 200 instances in general. As shown in Figure 3.9, a large neighborhood generates a large set of explanations. Thus, to balance the accuracy of RF and the size of the output set of explanations, we set the maximum size of the locality of an instance to 200.

<footnote n="21">²¹GridSearchCV exhaustively generates candidates from a grid of parameter values specified with the param_grid parameter.</footnote>
<figure><img src="image_24.png" /><figcaption>Figure 3.8: The classification accuracy of RF models with respect to the *max_depth* parameter.</figcaption></figure>

## Evaluating the CNF encoding feasibility

We report our results regarding the encoding phase to generate the CNF formulae in terms of its size represented in number of variables and clauses (Vars/CLs) and also the encoding time (in seconds). We use the Tseitin Transformation [Tse83] to encode the propositional formulae associated to our surrogate model into an equisatisfiable CNF formulae, the input format required to use the SAT solvers. For the MNIST dataset, the predictions are made using <fnref n="22" /> the "one-vs-all" BNN classifiers trained to recognize the digits. The results reported here concern the "0","2","6" and "8" digits but they are similar for the other digits. For the other datasets, a MLP classifier is used. Note that a maximum number of neighbor instances set to 200 is used to limit our region of interest around an instance *x*.

**Table 3.2** shows that the generated random forest classifiers provide interesting results in terms of fidelity (high accuracy of the surrogate models) and tractability (size of the CNF encoding). This ensures that the explanations generated locally are relevant for the original model having the same behavior. In Table 3.2, the size of CNF is expressed as *number of variables/number of clauses*. We can see that the number of variables and clauses of CNF formulae remains reasonable and easily handled by the current SAT-solvers which confirms the feasibility of the approach.

<footnote n="22">²²the results for the other digits are similar but can not be reported here because of space limitation</footnote>
<figure><img src="image_25.png" /><figcaption>Figure 3.9: Example to compare the average total number of CF<sub>x</sub> explanations with respect to the neighborhood size when it is limited to a maximum number (|V<sub>x</sub>| ≤ T) or not limited.</figcaption></figure>

<table><caption>Table 3.2: Evaluating the scalability of the CNF encoding in terms of size (number of variables and clauses) and encoding time in seconds for different datasets using different radius values.</caption><thead><tr><th>Radius (r)</th><th>|V<sub>x</sub>|</th><th>Dataset name</th><th>Acc (%)</th><th>MIN |Σ| (Vars/CLs)</th><th>AVG |Σ| (Vars/CLs)</th><th>MAX |Σ| (Vars/CLs)</th><th>MIN runtime (s)</th><th>AVG runtime (s)</th><th>MAX runtime (s)</th></tr></thead><tbody><tr><td rowspan="4">100</td><td>60</td><td>MNIST_0</td><td>97.4</td><td>141/837</td><td>449/930</td><td>841/1079</td><td>0.8916</td><td>0.9739</td><td>1.1667</td></tr><tr><td>69</td><td>MNIST_2</td><td>95.25</td><td>98/825</td><td>689/1025</td><td>1359/1624</td><td>0.904</td><td>1.1</td><td>1.53</td></tr><tr><td>70</td><td>MNIST_6</td><td>96.7</td><td>124/833</td><td>783/1060</td><td>1443/1874</td><td>0.913</td><td>1.14</td><td>1.62</td></tr><tr><td>169</td><td>MNIST_8</td><td>95.21</td><td>1219/1230</td><td>1615/2318</td><td>2043/3499</td><td>1.26</td><td>1.78</td><td>3.68</td></tr><tr><td rowspan="4">150</td><td>160</td><td>MNIST_0</td><td>97.7</td><td>147/843</td><td>1475/1934</td><td>2083/3657</td><td>0.8991</td><td>1.1643</td><td>1.6446</td></tr><tr><td>167</td><td>MNIST_2</td><td>91.19</td><td>1205/1211</td><td>1579/2263</td><td>2069/3672</td><td>1.32</td><td>1.87</td><td>3.71</td></tr><tr><td>165</td><td>MNIST_6</td><td>93.88</td><td>1211/1216</td><td>1739/2702</td><td>2173/3950</td><td>1.17</td><td>1.6</td><td>3.01</td></tr><tr><td>200</td><td>MNIST_8</td><td>95.1</td><td>1529/2070</td><td>1795/2798</td><td>2133/3725</td><td>1.38</td><td>1.87</td><td>2.92</td></tr><tr><td rowspan="4">250</td><td>201</td><td>MNIST_0</td><td>98.87</td><td>1744/4944</td><td>1979/5540</td><td>2176/6066</td><td>0.83</td><td>1.05</td><td>1.51</td></tr><tr><td>>200</td><td>MNIST_2</td><td>93</td><td>1941/5452</td><td>2172/6050</td><td>2429/6760</td><td>0.88</td><td>1.06</td><td>1.92</td></tr><tr><td>>200</td><td>MNIST_6</td><td>96</td><td>1978/5534</td><td>2270/6293</td><td>2558/7028</td><td>0.82</td><td>0.92</td><td>1.31</td></tr><tr><td>>200</td><td>MNIST_8</td><td>95.12</td><td>1837/5178</td><td>2059/5727</td><td>2330/6408</td><td>0.74</td><td>0.86</td><td>1.32</td></tr><tr><td>1</td><td>33</td><td rowspan="6">SPECT</td><td>100</td><td>1296/3866</td><td>1565/4576</td><td>2163/6154</td><td>2.71</td><td>3.06</td><td>3.86</td></tr><tr><td>2</td><td>52</td><td>99.04</td><td>1317/3918</td><td>1776/5160</td><td>3139/8846</td><td>1.01</td><td>2.08</td><td>4.09</td></tr><tr><td>3</td><td>63</td><td>97.3</td><td>1297/3862</td><td>1933/5581</td><td>3519/9850</td><td>0.89</td><td>1.29</td><td>2</td></tr><tr><td>4</td><td>75</td><td>93.47</td><td>1322/3928</td><td>1891/5493</td><td>33003/9264</td><td>0.752</td><td>1.11</td><td>1.872</td></tr><tr><td>7</td><td>112</td><td>90.98</td><td>1676/4886</td><td>2315/6683</td><td>2638/7588</td><td>85.7</td><td>1.11</td><td>1.29</td></tr><tr><td>22</td><td>160</td><td>99</td><td>2495/7174</td><td>2758/7921</td><td>3088/8844</td><td>1.07</td><td>1.214</td><td>1.5</td></tr><tr><td>5</td><td>36</td><td rowspan="2">MONKS</td><td>91.21</td><td>1314/3908</td><td>1576/4595</td><td>2353/6668</td><td>1.09</td><td>2.124</td><td>4.62</td></tr><tr><td>16</td><td>181</td><td>98</td><td>2351/6714</td><td>2883/8146</td><td>3451/9694</td><td>1.66</td><td>1.56</td><td>2.03</td></tr><tr><td>5</td><td>26</td><td rowspan="3">BREAST CANCER</td><td>78.68</td><td>1291/3836</td><td>1757/5080</td><td>2995/8454</td><td>1.21</td><td>1.76</td><td>2.38</td></tr><tr><td>10</td><td>147</td><td>79.82</td><td>1327/3942</td><td>4605/12891</td><td>5868/16416</td><td>1.18</td><td>2.18</td><td>3.84</td></tr><tr><td>48</td><td>>200</td><td>82</td><td>5094/14184</td><td>6069/16907</td><td>7053/19586</td><td>2.02</td><td>2.5</td><td>3.42</td></tr><tr><td>2</td><td>22</td><td rowspan="3">CONGRES VOTING</td><td>100</td><td>128/280</td><td>1368/4042</td><td>1494/4372</td><td>0.9</td><td>1.73</td><td>3.7</td></tr><tr><td>5</td><td>70</td><td>94.67</td><td>1291/3836</td><td>1853/5347</td><td>2997/8462</td><td>1.15</td><td>1.74</td><td>2.64</td></tr><tr><td>16</td><td>>200</td><td>90.82</td><td>1313/3893</td><td>2024/5783</td><td>2873/8122</td><td>0.91</td><td>1.85</td><td>2.45</td></tr></tbody></table>
<figure><img src="image_26.png" /><figcaption>Figure 3.10: The classification accuracy of RF models with the respect to the neighborhood size.</figcaption></figure>

## Evaluating the enumeration of symbolic explanations

The objective here is to assess the practical feasibility of the enumeration (scalability) of $SR_x$ and $CF_x$ explanations. For the enumeration of $CF_x$, we use the * EnumELSRMRCache tool$^{23}$ implementing the boosting algorithm for MCSes enumeration proposed in [GIL18] with a timeout set to 600s. As for the $SR_x$ explanations, their computation is easily done by exploiting the minimal hitting set duality relationship between MUSes and MCSes. The different values used for the radius $r$ during the experiments has a direct impact on determining the locality of $x$, and therefore selecting the data used to train the surrogate model.

We observe within **Table 3.3** that the average runtime remains reasonable (note that the times shown in Table 3.3 relate to the time taken to list all the explanations. The solver starts to find the first explanations very promptly) and that the approach is efficient in practice for medium sized classifiers (as shown in the experiments for BNNs with around 800 variables). We also observe that the number of $CF_x$ may be challenging, hence, this emphasizes the need for scoring metrics to filter them out and identify the ones with the strongest influence on the prediction.

Table 3.4 presents the evaluation of the sufficient reasons generation ($SR_x$). Those explanations are enumerated using the duality between sufficient reasons and counterfactuals. Knowing that the runtime

<footnote>23available at http://www.cril.univ-artois.fr/enumcs/</footnote>
<figure><img src="image_27.png" /><figcaption>Figure 3.11: The classification accuracy of RF models with respect to the *ntree* parameter.</figcaption></figure>

reported in Table 3.4 is the time needed for the enumeration of all possible $SR_x$ explanations, the results remain of the same order of magnitude as that of the counterfactuals presented in Table 3.3.

The pie charts in Figure 3.12 are used to illustrate the portion of relevant features on average (Figure 3.12a) and at most (Figure 3.12b) composing the explanations enumerated for the different classifiers trained on the MNIST dataset. As shown on the charts, the number of relevant features remains low
<table><caption>Table 3.3: Evaluating the enumeration of all the counterfactual explanations.</caption><thead><tr><th>Radius (r)</th><th>Dataset name</th><th>MIN #CF</th><th>AVG #CF</th><th>MAX #CF</th><th>MIN runtime (s)</th><th>AVG runtime (s)</th><th>MAX runtime (s)</th><th>One CF runtime (s)</th></tr></thead><tbody><tr><td rowspan="4">100</td><td>MNIST_0</td><td>1</td><td>80</td><td>1047</td><td>8*10<sup>-4</sup></td><td>4.09*10<sup>-2</sup></td><td>54*10<sup>-1</sup></td><td rowspan="12">&le; 10<sup>-4</sup></td></tr><tr><td>MNIST_2</td><td>1</td><td>2198</td><td>222180</td><td>3*10<sup>-4</sup></td><td>32.42*10<sup>-2</sup></td><td>43.24</td></tr><tr><td>MNIST_6</td><td>1</td><td>13753</td><td>225456</td><td>2.4*10<sup>-3</sup></td><td>12.39</td><td>275.52</td></tr><tr><td>MNIST_8</td><td>1</td><td>5343</td><td>85407</td><td>1.1*10<sup>-3</sup></td><td>2.74</td><td>35.08</td></tr><tr><td rowspan="4">150</td><td>MNIST_0</td><td>1</td><td>4733</td><td>261504</td><td>10<sup>-4</sup></td><td>0.88</td><td>67.05</td></tr><tr><td>MNIST_2</td><td>4</td><td>23503</td><td>346288</td><td>3*10<sup>-3</sup></td><td>13.36</td><td>315.34</td></tr><tr><td>MNIST_6</td><td>1</td><td>29527</td><td>401117</td><td>6.6*10<sup>-3</sup></td><td>19.1</td><td>328.73</td></tr><tr><td>MNIST_8</td><td>2</td><td>5703</td><td>739433</td><td>7*10<sup>-4</sup></td><td>1.86</td><td>57.38</td></tr><tr><td rowspan="4">250</td><td>MNIST_0</td><td>10</td><td>35790</td><td>285219</td><td>0.005</td><td>21.49</td><td>234.18</td></tr><tr><td>MNIST_2</td><td>13</td><td>63916</td><td>546005</td><td>0.11</td><td>42.11</td><td>600</td></tr><tr><td>MNIST_6</td><td>15</td><td>79520</td><td>640868</td><td>0.11</td><td>50.86</td><td>531.16</td></tr><tr><td>MNIST_8</td><td>6</td><td>69678</td><td>1210349</td><td>33*10<sup>-4</sup></td><td>32.3</td><td>315.34</td></tr><tr><td>3</td><td rowspan="4">SPECT</td><td>1</td><td>2</td><td>11</td><td>0</td><td>64*10<sup>-4</sup></td><td>137*10<sup>-4</sup></td><td rowspan="4">0</td></tr><tr><td>4</td><td>2</td><td>19</td><td>107</td><td>2*10<sup>-4</sup></td><td>1.58*10<sup>-2</sup></td><td>5.75*10<sup>-2</sup></td></tr><tr><td>7</td><td>2</td><td>71</td><td>446</td><td>2.7*10<sup>-3</sup></td><td>5.24*10<sup>-2</sup></td><td>2.88*10<sup>-1</sup></td></tr><tr><td>22</td><td>15</td><td>204</td><td>700</td><td>0.01</td><td>0.12</td><td>0.42</td></tr><tr><td>5</td><td rowspan="2">MONKS</td><td>1</td><td>3</td><td>20</td><td>2*10<sup>-4</sup></td><td>5.3*10<sup>-3</sup></td><td>1.4*10<sup>-2</sup></td><td rowspan="2">0</td></tr><tr><td>16</td><td>3</td><td>15</td><td>41</td><td>0.01</td><td>0.03</td><td>0.06</td></tr><tr><td>5</td><td rowspan="3">BREAST CANCER</td><td>1</td><td>18</td><td>202</td><td>0</td><td>1.57*10<sup>-2</sup></td><td>1.54*10<sup>-1</sup></td><td rowspan="3">0</td></tr><tr><td>10</td><td>1</td><td>368</td><td>3118</td><td>2*10<sup>-4</sup></td><td>6.97*10<sup>-1</sup></td><td>6.05</td></tr><tr><td>48</td><td>11</td><td>947</td><td>5541</td><td>0.02</td><td>1.5</td><td>17.7</td></tr><tr><td>2</td><td rowspan="3">CONGRES VOTING</td><td>1</td><td>1</td><td>3</td><td>3*10<sup>-4</sup></td><td>6.6*10<sup>-3</sup></td><td>9.2*10<sup>-3</sup></td><td rowspan="3">0</td></tr><tr><td>5</td><td>1</td><td>3</td><td>11</td><td>5*10<sup>-4</sup></td><td>7.9*10<sup>-3</sup></td><td>3.28*10<sup>-2</sup></td></tr><tr><td>16</td><td>1</td><td>5</td><td>44</td><td>1.9*10<sup>-3</sup></td><td>1.21*10<sup>-2</sup></td><td>4*10<sup>-2</sup></td></tr></tbody></table>

compared to the size of the input feature space (composed of 784 variables). This is directly related to the property of minimality of our explanations, which translates into concise symbolic explanations.

<figure><img src="image_28.png" /><figcaption>Figure 3.12: The percentage of relevant features w.r.t the initial feature space composed of 784 variables for the MNIST dataset.</figcaption></figure>
<table><caption>Table 3.4: Evaluating the enumeration of all the sufficient reasons explanations.</caption><thead><tr><th>Radius (r)</th><th>Dataset name</th><th>MIN #SR</th><th>AVG #SR</th><th>MAX #SR</th><th>MIN runtime (s)</th><th>AVG runtime (s)</th><th>MAX runtime (s)</th></tr></thead><tbody><tr><td rowspan="4">100</td><td>MNIST_0</td><td>1</td><td>230</td><td>1808</td><td>1.1* 10<sup>-3</sup></td><td>2.94* 10<sup>-2</sup></td><td>3.38* 10<sup>-1</sup></td></tr><tr><td>MNIST_2</td><td>1</td><td>9911</td><td>116700</td><td>1.2* 10<sup>-3</sup></td><td>47.6</td><td>595</td></tr><tr><td>MNIST_6</td><td>3</td><td>1900</td><td>19129</td><td>1.1* 10<sup>-3</sup></td><td>7.018* 10<sup>-1</sup></td><td>7.06</td></tr><tr><td>MNIST_8</td><td>1</td><td>13032</td><td>126764</td><td>9* 10<sup>-4</sup></td><td>31</td><td>488</td></tr><tr><td rowspan="4">150</td><td>MNIST_0</td><td>12</td><td>31665</td><td>172530</td><td>2.2* 10<sup>-3</sup></td><td>77.87</td><td>519</td></tr><tr><td>MNIST_2</td><td>1</td><td>11851</td><td>119937</td><td>7* 10<sup>-4</sup></td><td>36.58</td><td>594</td></tr><tr><td>MNIST_6</td><td>5</td><td>17218</td><td>144640</td><td>1* 10<sup>-3</sup></td><td>63.09</td><td>558</td></tr><tr><td>MNIST_8</td><td>2</td><td>20189</td><td>227446</td><td>8* 10<sup>-4</sup></td><td>29.1</td><td>578</td></tr><tr><td rowspan="4">250</td><td>MNIST_0</td><td>3</td><td>32135</td><td>246428</td><td>1.4* 10<sup>-3</sup></td><td>100</td><td>595</td></tr><tr><td>MNIST_2</td><td>16</td><td>27519</td><td>155956</td><td>3.1* 10<sup>-3</sup></td><td>104.67</td><td>592</td></tr><tr><td>MNIST_6</td><td>65</td><td>38323</td><td>179112</td><td>7.2* 10<sup>-3</sup></td><td>121</td><td>577</td></tr><tr><td>MNIST_8</td><td>4</td><td>33659</td><td>315753</td><td>1.4* 10<sup>-3</sup></td><td>35.98</td><td>536</td></tr><tr><td>3</td><td rowspan="4">SPECT</td><td>1</td><td>3</td><td>13</td><td>9*10<sup>-4</sup></td><td>1.8*10<sup>-3</sup></td><td>4.9*10<sup>-3</sup></td></tr><tr><td>4</td><td>1</td><td>21</td><td>113</td><td>1.1*10<sup>-3</sup></td><td>5*10<sup>-3</sup></td><td>2.32*10<sup>-2</sup></td></tr><tr><td>7</td><td>1</td><td>87</td><td>390</td><td>1.2*10<sup>-3</sup></td><td>2.47*10<sup>-2</sup></td><td>12.36*10<sup>-2</sup></td></tr><tr><td>22</td><td>1</td><td>223</td><td>1290</td><td>9*10<sup>-4</sup></td><td>4.94*10<sup>-2</sup></td><td>41.97*10<sup>-2</sup></td></tr><tr><td>5</td><td rowspan="2">MONKS</td><td>1</td><td>3</td><td>13</td><td>8*10<sup>-4</sup></td><td>1.3*10<sup>-3</sup></td><td>3.4*10<sup>-3</sup></td></tr><tr><td>16</td><td>1</td><td>28</td><td>102</td><td>8*10<sup>-4</sup></td><td>3.9*10<sup>-3</sup></td><td>1.67*10<sup>-2</sup></td></tr><tr><td>5</td><td rowspan="3">BREAST CANCER</td><td>1</td><td>23</td><td>308</td><td>1*10<sup>-3</sup></td><td>4.4*10<sup>-3</sup></td><td>6.69*10<sup>-2</sup></td></tr><tr><td>10</td><td>1</td><td>1502</td><td>10817</td><td>9*10<sup>-4</sup></td><td>6.66*10<sup>-2</sup></td><td>7.63</td></tr><tr><td>48</td><td>4</td><td>4737</td><td>69838</td><td>1.3*10<sup>-3</sup></td><td>2.16</td><td>55.25</td></tr><tr><td>2</td><td rowspan="3">CONGRES VOTING</td><td>1</td><td>2</td><td>3</td><td>1.1*10<sup>-3</sup></td><td>1.5*10<sup>-3</sup></td><td>2.4*10<sup>-3</sup></td></tr><tr><td>5</td><td>1</td><td>2</td><td>5</td><td>8*10<sup>-4</sup></td><td>1.4*10<sup>-3</sup></td><td>2.4*10<sup>-3</sup></td></tr><tr><td>16</td><td>1</td><td>8</td><td>46</td><td>9*10<sup>-4</sup></td><td>2.5*10<sup>-3</sup></td><td>1.1*10<sup>-2</sup></td></tr></tbody></table>

Figure 3.13 represents box plots indicating the range in which the size of explanations (number of variables) is located. We observe that in general, the symbolic explanations are of concise sizes which help a human to understand the reasons of a model’s decision easily.

## Illustrating $SR_x$ and $CF_x$ explanations for MNIST dataset

We show examples of both types of symbolic explanations Figure 3.14. Recall that we trained two "one-vs-all"^24 BNNs for each digit ranging from 0 to 9 and we will be using them as black-boxes on some test samples. Although the performance of the classifiers is not the key objective to this study, we use well-trained models that can predict the output well. The classification models $f_8$ and $f_0$ have respectively achieved an accuracy of 97% and 99% on test data. Figure 3.14 shows some relevant data samples and the symbolic explanations generated to explain their predictions. The first column shows the input test images representing different digits, their prediction and the targeted outcome that can be reached using a counterfactual explanation. Results are depicted on three columns. The column "Relevant features" represents all the pixels included in the set of explanations enumerated for the test input. The "sufficient

<footnote>^24 A "one-vs-all" BNN $f_i$ returns a positive prediction for an input image representing the "i" digit, and negative one otherwise.</footnote>
<figure><img src="image_29.png" /><figcaption>Figure 3.13: The range of explanations size enumerated for the different datasets.</figcaption></figure>

reason" column corresponds to a picture depicting the set of pixels composing an example of a single sufficient reason explanation that justifies the model's decision. Finally, the last column represents an example of a single counterfactual explanation highlighting the set of pixels to activate/deactivate in order to provide users with actionable explanations in the form of data sample that would have received a different outcome. The first row associated to a test input shows images with the pixels composing the different explanations. The second row represents the overlay of test input and the different explanations. Let us consider the first test input (x), Figure 3.14 shows an example of a single SRₓ explanation highlighting the sufficient pixels for the models f₈ to trigger a negative prediction for the image x. It also provides an example of a CFₓ explanation showing the pixels to invert in the test input to make the model f₈ predict x positively. Another example is presented for a test input illustrating a 1-digit and it is recognized as non 0-digit by f₀. The last row is an example of a test input positively predicted by f₀ as a 0-digit.

## 3.5 Conclusion

In this chapter, we have proposed a post-hoc interpretability method in order to explain the decisions of black-box classification models. We proposed a novel model agnostic generic approach to explain individual outcomes by providing two complementary types of symbolic explanations (*sufficient reasons* and *counterfactuals*). The generation of local symbolic explanations is done within the framework of satisfiability solving. It takes advantage of the strengths of already existing and proven solutions, and of the powerful practical tools for the generation of MCSes/MUSes. We also introduced a substitution
Prediction : $f_8 = 0$

Target : $f_8 = 1$

Test input

<figure><img src="image_30.png" /></figure>

Relevant features

<figure><img src="image_31.png" /></figure>

Sufficient reason (SR)

<figure><img src="image_32.png" /></figure>

Counterfactual (CF)

<figure><img src="image_33.png" /></figure>

Prediction : $f_0 = 0$

Target : $f_0 = 1$

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

Prediction : $f_0 = 1$

Target : $f_0 = 0$

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /><figcaption>Figure 3.14: Example inputs from MNIST dataset and their respective symbolic explanations.</figcaption></figure>

approach as a solution to overcome the complexity of encoding a ML classifier into an equivalent logical
representation. It consists in approximating the original model locally using a surrogate model which
will subsequently be used to explain individual predictions of black-box ML models. This approach
initially proposed for single-label classification constitutes the cornstone on which the rest of our work
is based and has been extended for multi-label classification in the next chapter.
# Chapter 4

## Symbolic explanations for multi-label classification

Multi-label classification is a well-known predictive task encountered in a wide range of applications such as text categorization, object recognition in images, classification of genes and bio-informatics. For example, in a text categorization problem, each document can be simultaneously assigned to multiple labels or classes (for example, a conference paper may at the same time be tagged as *Machine learning*, *XAI* and *bio-informatics*). In single-label classification, classes are mutually exclusive. At the opposite, in multi-label classification, classes do not exclude each other allowing the same input instance to be simultaneously classified into multiple classes.

This chapter is dedicated to the presentation of an agnostic and declarative approach to provide different types of symbolic explanations for multi-label classifiers. It extends the declarative and model-agnostic approach we presented to explain the predictions of single-label classifiers. More precisely, in addition to sufficient reason and counterfactual explanations presented in Chapter 3, the proposed approach in this chapter makes it possible to generate explanations at different granularity levels which go from structural relationships between labels to the selection of features allowing to force the prediction to any desired target prediction.

We first present in Section 4.1 a brief refresher of the main methods that have been proposed by the community. In Section 4.2, we deal with the definitions of explanations (sufficient reasons and counterfactual explanations) in a multi-label setting on two different levels of granularity (the whole prediction or parts of the prediction). We will present in Section 4.3 a new type of explanations specific to multi-label problems where we rely on the relationships among the considered classes to infer and present explanations. We present a SAT-based setting to enumerate those explanations in Section 4.4. Finally, we tackle in Section 4.5 the issue of evaluating our approach on different types of data.

### 4.1 Brief review of related works

Unlike single-label classification problems, very few studies have focused on explaining multi-label classifiers. There is mainly a couple of simple feature attribution methods based on aggregating feature importance scores of the different predicted labels computed individually. Explanation approaches in multi-label classification can mainly be categorized into feature importance explanations and decision rules explanations. In [PGMP19], the authors propose "MARLENA", a model-agnostic method to explain the decisions of a multi-label black-box. It generates a synthetic neighborhood around the sample to be explained and learns a multi-label decision tree on it. The explanations are simply the decision rules derived from those decision trees. In [CGG$^{+20}$], the authors propose an approach to explain neural
network-based systems by learning first-order logic rules from the outputs of the multi-label model. This approach completely ignores the features when providing explanations. The explaining functions give a description in terms of first-order logic where each rule expresses the validity of a certain explanation w.r.t. the output of the model on a given input. In [SB21], the authors focus on multi-label model explainability and propose a method to merge multiple feature importance explanations corresponding to each class into a single list of feature contributions. The aggregation of the feature weights is simply the average feature weights over the *k* labels. The same idea is used in [Che21] except that they compute Shapley values over the dataset using kernel-SHAP and then compute a global feature importance per label.

Such methods are limited when it comes to the explanation types they provide. For instance, one can not identify which part of the features is responsible for a given part of the multi-label prediction. Moreover, from a user point of view, it can be hard to interpret what a given feature importance means in the case of a multi-label decision given that a feature may have strong influence for predicting a given label while it is irrelevant for predicting other labels. In the majority of related works, there are even no clear and formal definitions of what a multi-label explanations are. To our knowledge, there is no symbolic explanation for the classification multi-label problems. We propose different types of explanations that take into account several possible situations where the interest of the user is directed towards an explanation of the entire prediction or of a specific part of it. Our contribution proposes not only explanations which justify the output obtained, but also actionable explanations in the form of counterfactuals.

## 4.2 Feature-based explanations

A feature-based explanation involves only features, i.e. aims to explain the predictions of a classifier based only on the features of the input data. It can be associated with different semantics and different granularity levels. We focus on two complementary types of feature-based explanations that are the sufficient reasons and counterfactuals.

<table><caption>Table 4.1: The symbolic-based multi-label explanations</caption><thead><tr><th></th><th>Entire-outcome</th><th>Fine-grained</th></tr></thead><tbody><tr><td><strong>Sufficient reasons</strong> (Which features cause the current prediction)</td><td>Why f(x)=y ?</td><td>What causes a subset of labels y' ⊆ y to be predicted by f ?</td></tr><tr><td><strong>Counterfactuals</strong> (Which features to modify to have an alternative prediction)</td><td>Which x' st. f(x')=y' ?</td><td>Which x' forces f to make a desired partial prediction ?</td></tr></tbody></table>

As for single-label classification, sufficient reason explanations correspond to the minimal part of the input data that is sufficient to trigger the current prediction while *counterfactual* explanations refer to the minimal changes in the input data to get an alternative target outcome. Depending on the problem under study, it may be relevant to have different types of explanations. Assume that we have a multi-label classifier (MLC) with a large output set (e.g. hundreds). We may care little about all the labels as it may be irrelevant to provide an explanation for the entire outcome of the model, especially for datasets with very low density, as it represents an inherent challenge for multi-label classification [WXH$^+$14, BH17, BCPdI19, Nig16]. This is especially true since in most cases, the user is interested in the few classes predicted positively. For example, in document categorization tasks, a user may want to understand why a document is (or not) classified in such classes. Explaining "Why the document was not classified in all the remaining classes?" may be irrelevant. Based on this observation, the approach we propose called
SYMCA for SYmbolic explanations for Multi-label ClAssification provides explanations for both the
entire prediction (all classes) and explanations for parts of the prediction that are of interest to the user.
We sum up in Table 4.1 the different cases we consider for feature-based explanations.

Let us introduce a running example that will be used within this chapter to illustrate the different concepts covered.

**Example 28 (Running example).** Classifying Yelp reviews into 5 categories. The "Yelp reviews classification"<sup>25</sup> is a categorization problem of reviews about businesses and services into relevant categories to help the users understand the rating of a given restaurant. The objective here is to know whether a review positively comments on certain aspects such as the Food, Service, Ambience, Deals and Worthiness. The dataset contains more than 10000 reviews from food and restaurant areas. There are three nominal features: Good (4-5 stars), Moderate (3 stars) and Bad (1-2 stars). The output classes (labels) are : (Food (F)), (Service (S)), (Ambience (A)), (Deals (D)), (Worthiness (W)). We consider the MLC f depicted in Figure 4.1 and consisting in a Binary Relevance classifier<sup>26</sup> using decision trees as base classifiers. Given the following review<sup>27</sup> : "We went out with friends to have mexican food, the quesadillas was delicious and came with a lot of cheese. We find the place a little boring but the dining room seemed nice" and a 4 stars rating as inputs, the review was classified positively commenting about label F, and negatively about the rest (S,A,D and W). It corresponds to y=(1,0,0,0,0) where y = f(x). The extracted features used in this example correspond to the highlighted paths in Figure 4.1.

<figure><img src="image_48.png" /><figcaption>Figure 4.1: Binary Relevance classifier trained on the Yelp dataset using decision trees as base classifiers</figcaption></figure>

<footnote n="25"><sup>25</sup>The dataset is available at https://www.ics.uci.edu/~vpsaini/.

<sup>26</sup>The binary relevance method (BR for short) is about training one binary classifier independently for each label in order to perform multi-label classification. It is the most commonly used strategy for multi-label classification.

<sup>27</sup>Of course, this is the raw text of the review. Raw data is first pre-processed and two types of features are extracted : i) textual features consisting of unigrams, bigrams and trigrams and ii) binary features representing rating 1-2 stars, 3 stars, and 4-5 stars respectively. Classification is achieved on extracted features.</footnote>
4.2.1 Entire-outcome explanations

An entire-outcome explanation explains all the predicted labels simultaneously. We recall that in the multi-label setting, the output is a vector y of k binary values assigned to each class of the output space Y. Our feature-based explanations are based on the definition of sufficient reasons and counterfactuals proposed initially for the binary case (see Chapter 3).

**Entire-outcome sufficient reasons explanations** An entire-outcome sufficient reason explanation (SR for short) identifies the minimal part of a data sample x (namely, the subset of features) sufficient to trigger the current multi-label outcome. Formally, a SR is defined as follows:

**Definition 30 (SR explanations).** Let $x$ be a data instance and $y=f(x)$ be its prediction by the multi-label classifier $f$. An entire-outcome sufficient reason explanation $\tilde{x}$ is such that:

1. $\tilde{x} \subseteq x$ ($\tilde{x}$ is a part of $x$),

2. $\forall \acute{x} \in X, \tilde{x} \subset \acute{x} : f(\acute{x})=f(x)$ ($\tilde{x}$ suffices to trigger $y=f(x)$),

3. There is no partial instance $\hat{x} \subset \tilde{x}$ satisfying 1 and 2 (minimality).

While the two first conditions in Definition 30 search for parts of $x$ allowing to fire the same prediction, the minimality condition allows to find parsimonious explanations (in terms of the number of features involved in the explanation). As we will see in our experiments, the explanations are not unique in the general case. Note that this is the same definition as the one of the SR for the single-label classification case except that $y$ represents a vector of labels instead of one label. In fact, multi-label classification is a generalization of the single-label classification.

**Example 29 (Example 28 continued).** (SR explanations) The explanations can concern the words present but also the words absent in a given comment entry $x$. The presence of a word is represented by a binary variable set to 1 if the word appears in $x$ and 0 otherwise. Let us introduce an example of a SR explanation. We want to explain the prediction $y=(1, 0, 0, 0, 0)$ for the review in hand. Given Table 4.2 showing examples of one instance of SR explanation per label, an example of sufficient reason for the entire-outcome is ('IsRatingBad:0', 'waitress:0', 'looking:0', 'daily_specials:0', 'this_place_is:0', 'delicious:1', 'the staff is:0', 'service_great:0', 'great place:0', 'really cool:0', 'staff:0', 'excellent:0', 'happy hour menu:0', 'prices good:0', 'for happy hour:0', 'the bar area:0', 'the atmosphere is:0', 'pleasantly surprised:0', 'reasonably priced:0'). It is easy to check that this SR involves parts forcing the five decisions trees to predict $y=(1, 0, 0, 0, 0)$ as detailed in Table 4.2.

<table><caption>Table 4.2: A SR explanation for the multi-label prediction $y=(1, 0, 0, 0, 0)$.</caption><thead><tr><th>Labels</th><th>y</th><th>Sufficient reason explanation</th></tr></thead><tbody><tr><td>Food (Y<sub>1</sub>)</td><td>1</td><td>['IsRatingBad: 0', 'waitress: 0', 'looking: 0', 'this place is: 0', 'delicious: 1']</td></tr><tr><td>Service (Y<sub>2</sub>)</td><td>0</td><td>['the staff is: 0', 'staff: 0', 'excellent: 0', 'service_great: 0']</td></tr><tr><td>Ambience (Y<sub>3</sub>)</td><td>0</td><td>['great place: 0', 'really_cool: 0', 'the_atmosphere_is: 0']</td></tr><tr><td>Deals (Y<sub>4</sub>)</td><td>0</td><td>['daily_specials: 0', 'happy_hourMenu: 0', 'for_happy_hour: 0']</td></tr><tr><td>Worthiness (Y<sub>5</sub>)</td><td>0</td><td>['daily_specials: 0', 'happy_hourMenu: 0', 'the_bar_area: 0', 'pleasantly_surprised: 0', 'reasonably_priced: 0']</td></tr></tbody></table>
**Entire-outcome counterfactual explanations** Given a target outcome ý, a counterfactual entire-outcome explanation (CF for short) is the minimal changes to be done in x in order to obtain ý instead of y. In other words, if for some reason, one wants to force the classifier to predict ý, then a counterfactual explanation is those minimal changes [x] needed to make on x such that f(x[ý])=ý. The notation x[ý] denotes the instance x where the variables involved in ý are inverted.

**Definition 31 (CF Explanations).** Let $x$ be a complete data instance and $y=f(x)$ be its prediction by the MLC $f$. Given a target outcome $ý \neq y$, an entire-outcome counterfactual explanation $\tilde{x}$ of $x$ is such that:

1. $\tilde{x} \subseteq x$ ($\tilde{x}$ is part of $x$),

2. $f(x[\tilde{x}])=ý$ ($\tilde{x}$ fires the target prediction),

3. There is no partial instance $\hat{x} \subset \tilde{x}$ satisfying 1 and 2 (minimality).

**Example 30 (Example 28 continued).** (CF explanations) Let's assume that the initial prediction $y$ of the review in hand was (1, 0, 0, 0, 0). We want to know the modifications needed on $x$ such that the review is classified as positively commenting on Service (S), Ambience (A), Deals (D) and Worthiness (W) and negatively commenting the Food (F). Namely, the target prediction ý is (0, 1, 1, 1, 1). Table 4.3 shows examples of one instance of CF explanation per label, an example of entire-outcome counterfactual is : ['delicious:1', 'IsRatingModerate:0', 'staff:0', 'great_place:0', 'little:1', 'daily_specials:0', 'the_bar_area:0)]. Table 4.3 shows how the above entire-outcome CF involves parts forcing each decision tree to trigger the target outcome ý. For example, to force the model to predict $l_2$ positively for $x$, it is enough to add the word 'staff' to $x$, in other words, change 'staff:0' into 'staff:1' in the decision tree associated with label $S(l_2)$.

<table><caption>Table 4.3: An entire-outcome CF explanation for the target prediction $\tilde{y}=(0, 1, 1, 1, 1)$.</caption><thead><tr><th>Labels</th><th>y</th><th>ý</th><th>Counterfactual explanations</th></tr></thead><tbody><tr><td>Food (Y<sub>1</sub>)</td><td>1</td><td>0</td><td>['delicious : 1', 'IsRatingModerate : 0']</td></tr><tr><td>Service (Y<sub>2</sub>)</td><td>0</td><td>1</td><td>['staff : 0']</td></tr><tr><td>Ambience (Y<sub>3</sub>)</td><td>0</td><td>1</td><td>['great_place : 0']</td></tr><tr><td>Deals (Y<sub>4</sub>)</td><td>0</td><td>1</td><td>['daily_specials : 0']</td></tr><tr><td>Worthiness (Y<sub>5</sub>)</td><td>0</td><td>1</td><td>['little : 1', 'the_bar_area : 0']</td></tr></tbody></table>

### 4.2.2 Fine-grained explanations

In practice, it may be more useful to get explanations about a label or a subset of labels of interest rather than an explanation for the entire prediction (a vector of $k$ labels). We say that the label $l_j$ is positively predicted if $l_j = 1$, and negatively predicted if $l_j = 0$.

**Remark 7.** In fact, an entire-outcome explanation is a particular case of fine-grained explanation when the target set of interest corresponds to the whole multi-label output vector.
<figure><img src="image_49.png" /><figcaption>Figure 4.2: Illustration of a fine-grained counterfactual</figcaption></figure>

**Special cases of fine-grained counterfactual explanations** Given an input data instance x, a MLC f and its prediction y=f(x), one may be interested in practice in the following explanations :

- *Counterfactual explanation for expansion*: By expansion, it is meant adding to the current prediction y more labels predicted positively. For example, if an application (represented by a set of features) is rejected because it was deemed to meet few criteria (corresponding to the labels), a natural question in this case is what needs to be changed in the application to meet more criteria (more labels predicted positively). Expansion requires that at least one label $l_i=0$ in the current prediction y will be inverted while preserving those labels already predicted positively.

- *Counterfactual explanation for contraction*: This is the opposite scenario to the expansion. It is rather a matter of having fewer positive labels. Clearly, at least one label $l_i=1$ in the current prediction y needs to be inverted. Thus, the number of negative labels in the new multi-label prediction $\hat{y}$ is greater than the ones in y. The idea is, in addition to the already negatively predicted labels, look for the minimal counterfactual explanations such that the maximum labels positively predicted are deactivated (turns to 0).

Of course, expansion and contraction are special cases of fine-grained counterfactual explanations.

**4.3 Label-based explanations**

Up to now, we explain the predictions of a classifier only using the features of the input data. Relying
solely on features to form symbolic explanations can be problematic in terms of the clarity and relevance
of explanations to the user. For instance, authors in [CGG+20] have experimentally shown that local
explanations based on the relationships between classes may reveal rules that are able to capture relation
between classes such as being Attractive and Young, or being Old and with Gray Hair. As shown in
figures of the Example 33, explaining a complex concept (or label) based solely on features can be
difficult for the user to understand. In some cases, this aspect can be greatly improved by exploiting
relationships or structures between the labels. For instance, if a label $l_i$ is subsumed (in the sense of
concept subsumption) by a label $l_j$ according to the MLC f, then clearly sufficient reasons of $l_i$ are also
sufficient reasons for $l_j$. Other examples of relations that can be easily extracted and exploited are label
equivalence and disjointedness. The main advantage is that we will have parsimonious explanations
which will be easier for a user to understand, and by reducing the number of the explanations generated, it will simplify their enumeration and presentation.

**Example 33.** Let us consider the handwritten digit recognition task performed on the well-known MNIST dataset [LBBH98]. MNIST is composed of 10 classes corresponding to digits from 0 to 9, that we extended by adding the labels "Odd", "Even" and "Prime". Each input image is associated to a vector of thirteen labels<fnref n="28" />. Assume we have the following : a MLC model, an input image x and its multi-label prediction y=(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0). Namely, x is predicted positively for the labels 9-digit ($l_9$) and "Odd" ($l_{10}$).

$$x = \begin{bmatrix} 1 * 1 & 0 \\ 1 * 2 & 0 \\ \vdots & \vdots \\ 1 * 28 & 0 \\ 2 * 1 & 0 \\ 2 * 2 & 0 \\ \vdots & \vdots \\ 28 * 26 & 0 \\ 28 * 27 & 0 \\ 28 * 28 & 0 \end{bmatrix} \qquad y = \begin{bmatrix} l_0 & 0 \\ l_1 & 0 \\ l_2 & 0 \\ \vdots & \vdots \\ l_5 & 0 \\ l_6 & 0 \\ l_7 & 0 \\ l_8 & 0 \\ l_9 & 1 \\ l_{10} & 1 \\ l_{11} & 0 \\ l_{12} & 0 \end{bmatrix}$$

<figure><img src="image_50.png" /><figcaption>(a) Explanations for the label $l_9$ highlighting the pixels sufficient for the model to recognize the image x as 9</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>(b) Explanations for the label $l_{10}$ highlighting the pixels sufficient for the model to recognize the image x as Odd</figcaption></figure>

Figure 4.3: Feature-based explanation for a sample from augmented MNIST dataset.

Figure 4.3 shows a sample image x from the MNIST dataset and its corresponding feature-based explanations. The first column corresponds to the input sample x represented as a matrix of 28x28 pixels

<footnote n="28">²⁸The labels having an index $i \in [0, 9]$ indicate whether the input image x is recognized as an i-digit while the labels having an index $i \in [10, 12]$ indicate respectively whether the represented digit is being classified as an "odd", "even" or a "prime".</footnote>
binarized (784 variables). The second column represents a heatmap corresponding to the frequency of involvement of the variables appearing in $SR_x^{29}$ in the explanation sets of instances from $V_x$. The last column is the feature-attribution explanation provided by the well-known SHAP[LL17] approach$^{30}$. In Figure 4.3, the sufficient reasons were provided by the post-hoc symbolic explainer we presented previously in Chapter 3. While sufficient reasons for label $l_9$ clearly display the pixels that the model relies on for classifying $x$ to be "9", it is hard to understand what makes the classifier predict $x$ as "Odd". Clearly, the feature-based explanations for label "Odd" are not intuitive since the representation of an object is very different from its visual representation. Indeed, classifying the MNIST digits into Odd, Even, Prime classes appears to be somewhat confusing because the way a symbol (e.g. 0,2,7) is written has got nothing to do with the properties of the number. Same observation holds for SHAP explanations. Let us now build another explanation for $x$ being predicted as "Odd" based on the fact that $x$ is predicted as "9" and that the subsumption relation between "9" and "Odd" holds over the predictions of the classifier $f$. The result is presented in Figure 4.4. Clearly, the explanation showing why the image $x$ is predicted as the digit "9" and that label "9" is necessarily associated with label "Odd" is more intuitive and easier to understand.

<figure><img src="image_52.png" /><figcaption>Figure 4.4: Combining feature and label-based explanation for a sample from augmented MNIST.</figcaption></figure>

## Types of label-based explanations

In theory, many relationships between labels can be exploited. In practice, two major questions arise: 1) How to extract the relations between the labels from the predictions of the classifiers $\beta$ and 2) How to exploit the relations extracted during the generation and presentation of explanations?

**Relations between the labels** For the first question, we can limit ourselves to certain types of relationships that are easy to extract and easy to understand for the user. Intuitive and useful examples of label relations are:

**Class subsumption (class implication)**: Let us consider a subsumption relationship between two class labels $Y_1$ and $Y_2$ denoted $Y_1 \subseteq Y_2$ (the notation $Y_1 \subseteq Y_2$ means that samples belonging to $Y_1$ necessarily belong to $Y_2$). If the relation $Y_1 \subseteq Y_2$ holds, then each time the prediction of an instance $x$ is such that

<footnote>$^{29}$Recall that sufficient reasons explanations justify why the trained model has positively predicted labels $l_9$ and $l_{10}$ for $x$.</footnote>

<footnote>$^{30}$The heatmaps represent the value of the pixels contributing positively to the current prediction (having a positive SHAP value). The value 0 is assigned to all the pixels which are unfavorable to the current predictions. (having a negative SHAP value).</footnote>
$Y_1=1$ then necessarily $Y_2=1$. Hence, knowing $Y_1=1$ is sufficient to assert that $Y_2=1$. We chose to focus on the positive predictions since the number of positively predicted labels is very often small compared to the size of the output space of multi-label datasets.

**Proposition 6.** Given a multi-label classifier $f$ and two class variables $Y_1$ and $Y_2$ where $Y_1 \subseteq Y_2$, then, the explanations of $Y_1 = 1$ are explanations for $Y_2 = 1$ and satisfy the conditions (1)-(2) of Definition 24 but do not guarantee to satisfy the condition (3) of the same definition.

*Proof.* Let $\tilde{x} \in SR(x, f_1)$, $f_1(x) = 1$ and $Y_1 \subseteq Y_2$. It is easy to see that $\tilde{x} \subset x$ since $x \in SR(x, f_1)$ (1). Since $f_1(x) = 1$ and $Y_1 \subseteq Y_2$ then $f_2(x) = 1$ (A). $\tilde{x} \in SR(x, f_1)$ implies that condition (2) from Definition 24 is satisfied. More precisely, $\forall \acute{x} \in X, \tilde{x} \subset \acute{x} : f_1(\acute{x})=f_1(x)$. Let $\acute{x}$ s.t $\tilde{x} \subset \acute{x}$. Since $f_1(\acute{x}) = 1$ and $Y_1 \subseteq Y_2$ then $f_2(\acute{x}) = 1$ (B). (A) and (B) imply that $f_2(\acute{x}) = f_2(x)$. Consequently, $\forall \acute{x} \in X, \tilde{x} \subset \acute{x} : f_2(\acute{x})=f_2(x)$ (2). (1) and (2) imply that $\tilde{x}$ satisfies conditions (1)-(2) of Definition 24 for $f_2$.

As for condition 3 of Definition 24 (minimality), there is no guarantee to obtain a minimal explanation for $f_2(x) = 1$ given a sufficient reason for $f_1(x) = 1$ (see counter-example 34).

□

An illustration of this proposition is given in Example 34. In order to explain positively predicted instances, we can simply work on the negation of the symbolic representation (CNF) of $f$ (namely $\neg \Sigma_f$). The enumeration of the explanations is done in the same way as for negative predictions.

**Example 34.** Let us consider the following set of data. From the data, we can see that there is a subsumption relationship between the labels $Y_1$ and $Y_2$ ($Y_1 \subset Y_2$) and between $Y_3$ and $Y_4$ ($Y_4 \subset Y_3$).

<table><thead><tr><th>X = {X<sub>1</sub>, X<sub>2</sub>, X<sub>3</sub>, X<sub>4</sub>}</th><th>Y = {Y<sub>1</sub>, Y<sub>2</sub>, Y<sub>3</sub>, Y<sub>4</sub>}</th></tr></thead><tbody><tr><td>1101</td><td>1111</td></tr><tr><td>0101</td><td>1111</td></tr><tr><td>0001</td><td>1111</td></tr><tr><td>1001</td><td>1110</td></tr><tr><td>1011</td><td>0100</td></tr><tr><td>0111</td><td>0010</td></tr><tr><td>0011</td><td>0011</td></tr></tbody></table>

Assume a decision tree classifier is trained on these data for each label (see Figure 4.5):

We want to explain positive predictions and thus, each classifier $\neg f$ encoded into a CNF formula as shown above.
<figure><img src="image_53.png" /><figcaption>Figure 4.5: Decision tree classifiers trained on different labels.</figcaption></figure>

<table><tr><td>DT<sub>1</sub></td><td>Σ<sub>¬f<sub>1</sub></sub> ⇔ (X<sub>3</sub> ∨ ¬X<sub>4</sub>)</td></tr><tr><td>DT<sub>2</sub></td><td>Σ<sub>¬f<sub>2</sub></sub> ⇔ (X<sub>3</sub>) ∧ (¬X<sub>3</sub> ∨ ¬X<sub>4</sub> ∨ ¬X<sub>1</sub>)</td></tr><tr><td>Input sample</td><td>Σ<sub>x</sub> ⇔ (x<sub>1</sub> ∧ ¬x<sub>2</sub> ∧ ¬x<sub>3</sub> ∧ x<sub>4</sub>)</td></tr></table>

Given the sufficient reason explanations associated to $Y_1$ and $Y_2$, we can see that the $SR(x, \neg f_1) \not\subseteq SR(x, \neg f_2)$. We have $\{\neg x_3, \neg x_4\} \subset x$ and $\forall \acute{x}, \{\neg x_3, \neg x_4\} \subset \acute{x}$ implies $f_2(\acute{x}) = 0$. Nevertheless, $\{\neg x_3, \neg x_4\}$ is not minimal for $\neg f_2$ because of $\neg x_3$.

$$SR(\Sigma_{\neg f_1} \cup \Sigma_x) = \{\{\neg x_3, x_4\}\}$$

$$SR(\Sigma_{\neg f_2} \cup \Sigma_x) = \{\{\neg x_3\}, \{x_1, x_4\}\}$$

**Class equivalence :** Two labels $Y_1$ and $Y_2$ are said equivalent and denoted $Y_1 \equiv Y_2$ if each time an instance $x$ where $Y_1=1$ is such that $Y_2=1$ and if $Y_2=1$ then $Y_1=1$. This means that one can explain $Y_1$ reusing the explanations of $Y_2$ and vice versa. Note that class equivalence relationships may be rare over whole multi-label data-sets but they are likely to be found when explaining in the neighborhood of a given sample $x$.

**Proposition 7.** Given a multi-label classifier $f$ and two class labels $Y_1 = 1$ and $Y_2 = 1$ where $Y_1 \equiv Y_2$, then, the $SR$ explanations of $Y_1 = 1$ are also $SR$ explanations for $Y_2 = 1$ and vice-versa.

*Proof.* Given $Y_1 \equiv Y_2$, proving that $SR(x, f_1) = SR(x, f_2)$ amounts to prove the implication in two directions. For the first implication $SR(x, f_1) \subseteq SR(x, f_2)$, we have the following. Let $\tilde{x} \in SR(x, f_1)$, $f_1(x) = 1$ and $Y_1 \equiv Y_2$. From Proposition 6, since $f_1(x) = 1$ and $Y_1 \subseteq Y_2$, then conditions (1) and (2) of Definition 24 are satisfied. Here it is a proof by contradiction for the condition (3) of Definition 24. Let $x^* \subset \tilde{x}$ s.t $x^* \subset x$ (1) and $\forall \acute{x}, x^* \subset \acute{x}: f_2(\acute{x}) = f_2(x)$ (2). Thanks to $f_1(x) = 1$, (2) and $Y_1 \equiv Y_2$, $\forall \acute{x}, x^* \subset \acute{x}: f_1(\acute{x}) = f_1(x)$ (2'). (1) and (2') imply a contradiction with $\tilde{x} \in SR(x, f_1)$. Thus, $\tilde{x} \supset x$ s.t $\forall \acute{x}, x^* \subset \acute{x}, f_2(\acute{x}) = 1$. Consequently, $\tilde{x} \in SR(x, f_2)$.
For the implication in the opposite direction ($SR(x, f_2) \subseteq SR(x, f_1)$), it is an easy exercise to check
that the same reasoning applies. Consequently, given the relation $Y_1 \equiv Y_2$ then $SR(x, f_1) = SR(x, f_2)$.
□

**Class disjointness :** The disjointness relationship between two labels $Y_1$ and $Y_2$ denoted $Y_1 \cap Y_2 = \emptyset$
denotes the fact that the two classes are mutually exclusive. Namely, for any instance $x$, if $Y_1=1$ then
necessarily $Y_2=0$ and conversely if $Y_1=0$ then necessarily $Y_2=1$. Then, explaining the label $Y_1$ allows to
explain $Y_2$ given the disjointness relation. For instance, using again our digit classification example,
it is enough to explain why a digit is labeled **Odd=1** to understand why it is labeled **Even=0** given that
$\mathbf{Odd} \cap \mathbf{Even}=\emptyset$ holds for $f$.

**Proposition 8.** Given a multi-label classifier $f$ and two class labels $Y_1$ and $Y_2$ where $Y_1 \cap Y_2 = \emptyset$, then, the explanations of $Y_1$ are also explanations for $\neg Y_2$ and vice-versa.

*Proof.* It is clear that the relation $Y_1 \cap Y_2 = \emptyset$ can be written as follows : $Y_1 \subseteq \neg Y_2$ and $Y_2 \subseteq \neg Y_1$.
Therefore, $Y_1 \equiv \neg Y_2$ and vice-versa. Following Proposition 7, it is enough to show that $SR(x, f_1) \subseteq SR(x, \neg f_2)$ and $SR(x, f_2) \subseteq SR(x, \neg f_1)$. The demonstration is provided in Proof 4.3.
□

The relations between labels can be used independently of the instances to explain the general func-
tioning of the classifier. Note that the extraction of some relations may require the use of dedicated tools
or the implementation of specific programs. For instance, testing the equivalence between CNFs comes
down to testing if a CNF is a logical consequence of a premise CNF.

**4.3.1 Impact of presence of relationships on explanations**

To explain the prediction associated with a specific instance, one can combine feature-based explanations
with relations between classes as in the example of Figure 4.4. How to combine such explanations is a
very broad issue.

Logical relationships can be extracted in several ways, whether using the logical representation (e.g CNF) or the set of predictions of these models. We seek to find the relationship (if any) between every pair of labels. There are different ways to extract certain relationships between two classes. One can consider the propositional logic language with the aim of using the efficient SAT solvers as the problem solving engine. For instance, checking the equivalence between two Boolean formulae can be done as presented in [Dar20] for CNFs and in [WZWY19] for Boolean functions. An important advantage in using such formal modeling is their correctness properties (deductions, model checking, etc), in addition to the speed and availability of SAT solvers. However, some of these properties can be too expensive to compute, which limit their use in practice. Another way to do it is empirically, where the identification of relations between two classes will be reduced to a comparison of their predictions on a set of data. Such an ad-hoc approach has the advantage of being fast and efficient in terms of time and space. However, this does not guarantee that all relations are found nor that those found are valid for the whole data space. Another option is to model the problem of finding relationships that bind classes as an association rule learning problem. The aim is to discover strong rules between an antecedent class $Y_1$ and a consequent class $Y_2$ using for instance the confidence measure<fnref n="31" />. For instance, in Example 34 where a class sub- sumption exists between $Y_4$ and $Y_3$ on a given neighborhood, the confidence measure of the association rule $Y_4 \Rightarrow Y_3$ would be equal to 100%.

<footnote n="31">³¹The confidence value of an association rule denoted as $Y_1 \Rightarrow Y_2$ in data mining is the ratio of transactions containing both $Y_1$ and $Y_2$ to the total number of $Y_1$.</footnote>
Once these relations are extracted, they can be exploited to determine the sets of final explanations as well as their presentation. In the case where a label $Y_i$ implies a label $Y_j$, it is possible to directly use the explanations of $Y_i$ to explain $Y_j$ (see Proposition 6). An example is shown in Figure 4.4. Implicitly, this means that the variables that contributed to the prediction of the $i^{th}$ class are also favorable to the $j^{th}$ class given the subsumption relationship between them. When it comes to the equivalence and disjunction between a pair labels ($Y_i, Y_j$), several scenarios are possible and a choice arises : *should we generate explanations for* $Y_i$ *and use them to explain* $Y_j$ *as well, or should we do it in the opposite direction?* and *what are the criteria to consider when making such a choice?* For instance, we can consider the rate of involvement of a label in the detected relations, quality of explanations, etc.

## 4.4 A model-agnostic SAT-based approach for enumerating symbolic explanations

The concepts described so far as well as the different definitions presented describing explanations aim at making the individual predictions of multi-label classifiers more understandable and interpretable for a user. This section presents an extension of the SAT-based model agnostic approach we proposed for the single-label case with the main difference being the output of Step 1 (set of CNFs associated with *k* labels instead of a single CNF associated with the single output class). Indeed, in addition to locally explaining individual classifier predictions, the goal of the approach proposed in Chapter 3 was to build a base explainer to explain a model individually and then use it to explain multi-label classifiers.

<figure><img src="image_54.png" /><figcaption>Figure 4.6: Overview of the proposed approach for the multi-label setting</figcaption></figure>

Before diving into more details, Figure 4.6 depicts a general overview of the approach adapted to the multi-label setting. As mentioned in the introduction, our approach for providing symbolic explanations is agnostic and declarative. It is based on modeling the multi-label classifier and our explanation enumeration problems as variants of the propositional satisfiability problem (SAT). It mainly goes through two steps: A first step for encoding the MLC in an "equivalent" (or "faithful" in case of using a surrogate model) canonical symbolic representation. The second step is about enumerating the explanations.
### 4.4.1 Step 1: Multi-label classifier symbolic modeling

The aim of this step is to associate the multi-label classifier with a symbolic equivalent or faithful symbolic representation that can be processed by a SAT-based oracle to enumerate our symbolic explanations. As shown in Figure 4.6, there are two cases to be considered:

**Direct encoding:** As mentioned in Chapter 3, some machine learning models (e.g. random forests, Binarized Neural Networks and some Bayesian network classifiers) have direct equivalent encoding into symbolic representation such as OBDDs, SDDs (e.g. [NKR+18, SCD19, SSDC20]) and CNFs which is the standard input format for SAT solvers. More details about such approaches were given in Chapter 3. Hence, in some cases, a multi-label classifier can be directly and equivalently encoded in CNF. For instance, the Binary Relevance classifier using decision trees as base classifiers can be equivalently encoded in CNF as illustrated in our running example. The idea is to associate a CNF $\Sigma_{f_i}$ to each base classifier $f_i$ such that the binary prediction of $f_i$ for a data instance $x$ is captured by the truth value or the logical consistency of $\Sigma_{f_i}$ with $\Sigma_x$ (recall that $\Sigma_x$ stands for the CNF encoding of the data instance $x$ $^{32}$). Formally, as stated in Definition 23, $f_i$ is said to be equivalent to $\Sigma_{f_i}$ iff for any data instance $x$:

$$ \Sigma_{f_i} \cup \Sigma_x \models \left\{ \begin{array}{ll} \top & \text{if } f_i(x) = 1 \\ \bot & \text{otherwise} \end{array} \right. \qquad (4.1) $$

where $\top$ means that the conjunction of $\Sigma_{f_i}$ and $\Sigma_x$ is satisfiable, corresponding to a positive prediction of the label $l_i$. $\bot$ means that the conjunction of $\Sigma_{f_i}$ and $\Sigma_x$ is unsatisfiable, corresponding to a negative prediction of the label $l_i$.

**Surrogate modeling:** In case the multi-label classifier (MLC) cannot be directly encoded into a CNF or in case such encoding would be intractable, our approach proceeds by associating with the multi-label classifier a faithful surrogate model that can be encoded into a CNF. In addition to allowing the handling of any multi-label classifier, the surrogate modeling offers another useful advantage that is providing local explanations. Indeed, it is challenging to explain a model's prediction over the whole dataset where the decision boundary may not be easily captured. The surrogate model built locally will make it possible to provide explanations in the neighborhood of $x$. Our approach associates a surrogate model $f_{S_i}$ to each label $l_i$. The surrogate model $f_{S_i}$ is trained on the vicinity of the data sample $x$ using the original training instances or by generating new data samples by randomly perturbing features of the input instance $x$. The MLC model $f$ is then used as a predictor on these samples where the predictions $f(x)$ become the targets. Surrogate models should be tuned to be as faithful as possible to the behavior of the original model $f$ in the neighborhood of $x$. A good surrogate model is the one able to ensure a good trade-off between high faithfulness to the initial model and tractability of its CNF encoding.

**Example 35** (Example 28 continued). Let us continue our running example. The encoding of the five decision trees of Figure 4.1 into five CNFs is straightforward as shown in the following (recall that intuitively, encoding a decision tree in CNF comes down to encode the paths leading to leaves labeled 0).

<footnote>$^{32}$An input sample $x$ is directly encoded in CNF in the form of a set of unit clauses.</footnote>
<table><tr><td>Food</td><td>y<sub>1</sub> ⇔ (IsRatingModerate ∨ coffee ∨ waitress ∨ ¬IsRatingBad) ∧<br/>(IsRatingModerate ∨ coffee ∨ ¬waitress ∨ IsRatingGood) ∧<br/>(IsRatingModerate ∨ ¬coffee ∨ ¬amazing ∨ looking) ∧<br/>(¬IsRatingModerate ∨ flavors ∨ delicious) ∧<br/>(¬IsRatingModerate ∨ flavors ∨ ¬delicious ∨ ¬this_place_is)</td></tr><tr><td>Service</td><td>y<sub>2</sub> ⇔ (service_great ∨ the staff is ∨ excellent ∨ staff) ∧<br/>(service_great ∨ the staff is ∨ ¬excellent ∨ ¬deal) ∧<br/>(service_great ∨ ¬the staff is ∨ ¬size) ∧<br/>(¬service_great ∨ ¬and the service ∨ ¬dont)</td></tr><tr><td>Ambience</td><td>y<sub>3</sub> ⇔ (really_cool ∨ the atmosphere is ∨ great place) ∧<br/>(really_cool ∨ the atmosphere is ∨ ¬great place ∨ ¬high) ∧<br/>(really_cool ∨ ¬the atmosphere is ∨ ¬the service is ∨ point)</td></tr><tr><td>Deals</td><td>y<sub>4</sub> ⇔ (for_happy_hour ∨ happy_hour menu ∨ daily_specials) ∧<br/>(for_happy_hour ∨ ¬happy_hour menu ∨ ¬can_see) ∧<br/>(¬for_happy_hour ∨ prices good ∨ ¬out) ∧<br/>(¬for_happy_hour ∨ prices good ∨ out ∨ ¬without)</td></tr><tr><td>Worth</td><td>y<sub>5</sub> ⇔ (nice ∨ daily_specials ∨ happy_hour menu) ∧<br/>(nice ∨ daily_specials ∨ ¬happy_hour menu ∨ ¬there was a) ∧<br/>(¬nice ∨ the bar area ∨ reasonably priced ∨ pleasantly surprised) ∧<br/>(¬nice ∨ the bar area ∨ ¬reasonably priced ∨ money) ∧<br/>(¬nice ∨ ¬the bar area ∨ ¬little)</td></tr></table>

Once the encoding step is achieved, we can rely on SAT-based oracles to provide explanations as presented in the following step.

### 4.4.2 Step 2: Symbolic explanation enumeration

Recall that in Step 2, we are given as input a set of CNFs (`{Σ₁, ..., Σₖ}`) associated to k labels) encoding the MLC f and a CNF encoding the data instance x denoted Σₓ. The aim of this step is to enumerate explanations for the prediction y=f(x). Similarly to the single-label case, we rely on SAT-based oracles in order to provide sufficient reasons and counterfactuals for a given label lᵢ (see Section 3.3 for how one can use it for binary classifiers). In the following, let SR(x, fSᵢ) (resp. CF(x, fSᵢ)) denote the set of sufficient reasons (resp. counterfactuals) to explain individual prediction of a base classifier fSᵢ(x).

#### Enumerating feature-based explanations

We present in the following how the proposed approach proceeds depending on the type of symbolic explanations to provide. Note that the entire-outcome explanations are actually a general case of fine-grained explanations where the target prediction ŷ concerns all output classes (`|ŷ| = k`).

**Entire-outcome sufficient reasons SR**: Since we can provide sufficient reasons for each label lᵢ, then it suffices to combine (join) an SRᵢ from each classifier fᵢ to form an explanation for the whole outcome.
**Proposition 9.** (Joint entire-outcome SR) Given a sufficient reason $\tilde{x}_i$ for each classifier $i=1,..,k$, the explanation $\tilde{x} = \bigwedge_{i=1}^k \tilde{x}_i$ satisfies conditions (1)-(2) of Definition 30 but does not guarantee to satisfy the condition (3) of the same definition.

*Proof.* (sketch) An explanation $\tilde{x} = \bigwedge_{i=1}^k \tilde{x}_i$ involves exactly one explanation from each individual base classifier. It is easy to check that $\tilde{x}$ verify the property 1 and 2 of Definition 30. Namely, (1) $\tilde{x}$ is part of the data instance (since each part $\tilde{x}_i \subseteq x$), (2) let $\acute{x} \in X, \tilde{x} \subset \acute{x}$, it is easy to see that $f(\acute{x}) = f(x)$. Indeed, since $\tilde{x} \subset \acute{x}$ then $\tilde{x}_i \subset \acute{x}$ for $i=1,..,k$. Following Definition 24, $f_i(\acute{x}) = f_i(x)$ for $i=1,..,k$.

As for the condition (3) of Definition 30 (minimality), combining base classifier SR explanations does not guarantee to obtain a minimal explanation. (see counter-example 36). □

**Example 36.** Assume a multi-label classification problem where data items are labeled in one or more categories (labels). The feature space is $X = \{X_1, X_2, X_3, X_4, X_5\}$ composed of five binary variables and three label variables $Y = \{Y_1, Y_2, Y_3\}$. The classifiers $f_1$ and $f_3$ predicted positively for the instance $x = (0, 1, 1, 0, 0)$. Classifier $f_1$ has three SR explanations for predicting positively $x$, namely $\text{SR}(x, f_1)=\{\neg x_1, x_2, x_3\}, \neg x_1, x_2, \neg x_4\}, \{x_2, x_3, \neg x_4\}\}$ and $f_2$ has also three SR explanations for $f(x)$ that are $\text{SR}(x, f_2)=\{\neg x_1, x_3\}, \{x_3, \neg x_5\}, \neg x_4\}$. Classifier $f_3$ has two SR explanations $\text{SR}(x, f_3)=\{\neg x_1, x_2\}, \{x_3, \neg x_4\}$. The set of joint entire-outcome SR explanations built by joining SR explanations of the three classifiers $f_1, f_2$ and $f_3$ gives 18 joint explanations including the following $\{\neg x_1, x_2, x_3\}, \neg x_1, x_2, x_3, \neg x_5\}, \neg x_1, x_2, x_3, \neg x_4\}, \neg x_1, x_2, x_3, \neg x_4, \neg x_5\}, ..$. In this example, explanations $\neg x_1, x_2, x_3$ and $\neg x_1, x_2, x_3, \neg x_5$ are explanations obtained by combining SR explanations of $f_1(x), f_2(x)$ and $f_3(x)$. Clearly, explanation $\neg x_1, x_2, x_3, \neg x_5$ is not minimal since $\neg x_1, x_2, x_3$ is a joint entire-outcome SR with a smaller size.

An example of an entire-outcome sufficient reason is shown in Table 4.2. The entire-outcome explanations are required to be conform to certain properties adapted from those defined for the BR explanations in [Tab19]. Hence, an entire-outcome explanation should verify:

- Unanimity : The explanation must explain all the parts of the multi-label prediction $f(x) = y$.

- Decomposability : The decomposition of the explanation of $f(x) = y$ should explain every label composing $y$.

**Entire-outcome counterfactuals CF** : Similar to sufficient reasons, one can form an explanation as far as we have counterfactuals $CF_i$ for each label $l_i$. More precisely, let the MLC $f$ predict $y$ for $x$ (namely, $f(x)=y$). Let us assume that the user wants to force the prediction to $\tilde{y}$ of size $k$. Then, an explanation is formed by joining a counterfactual $CF_i$ from each classifier $f_i$.

**Proposition 10.** (Joint entire-outcome CF) Given a counterfactual $\tilde{x}_i$ for each classifier $i=1,..,k$, the explanation $\tilde{x} = \bigwedge_{i=1}^k \tilde{x}_i$ satisfies conditions (1)-(2) of Definition 31 but does not guarantee to satisfy the condition (3) of the same definition.

*Proof.* (sketch) It is easy to check that $\tilde{x}$ verify the property 1 and 2 of Definition 31. Namely, (1) $\tilde{x}$ is part of the data instance (since each part $\tilde{x}_i \subseteq x$), (2) let $\acute{x} \in X, \tilde{x} \subset \acute{x}$, it is easy to see that $f(x[\tilde{x}])=\acute{y}$. Indeed, since $\tilde{x} \subset \acute{x}$ then $\tilde{x}_i \subset \acute{x}$ for $i=1,..,k$. Following Definition 25, $f_i(x[\tilde{x}])=\acute{y}_i$ for $i=1,..,k$.

As for the condition (3) of Definition 31 (minimality), combining base classifier CF explanations does not guarantee to obtain a minimal explanation. (see counter-example 37). □
**Example 37.** (Example 36 continued) Given the SR explanations of classifiers $f_1, f_2$ and $f_3$, the set of CF explanations associated to those classifiers respectively are the following : $CF(x, f_1) = \{\{x_2\}, \{\neg x_1, x_3\}, \{\neg x_1, \neg x_4\}, \{x_3, \neg x_4\}\}, CF(x, f_2) = \{\{x_3, \neg x_4\}, \{\neg x_1, \neg x_5, \neg x_4\}\}$ and finally the set $CF(x, f_3) = \{\{x_2, \neg x_4\}, \{\neg x_1, \neg x_4\}, \{x_2, x_3\}, \{\neg x_1, x_3\}\}$. Joining the CF entire-outcome explanations of classifiers $f_1, f_2$ and $f_3$ gives the following explanations $\{\{x_2, x_3, \neg x_4\}, \{x_2, \neg x_1, \neg x_4, \neg x_5\}, \{\neg x_1, \neg x_4, \neg x_5\}, \{\neg x_1, x_2, x_3, \neg x_4, \neg x_5\}, \dots\}$. It is clear that the explanations $\{\neg x_1, x_2, x_3, \neg x_4, \neg x_5\}$ is not minimal since the joint entire-outcome CF explanation $\{\neg x_1, \neg x_4, \neg x_5\}$ has a smaller size.

An example of an entire-outcome sufficient reason is shown in Table 4.3.

**Fine-grained sufficient reasons** $SR_{\tilde{y}}$: For fine-grained explanations, we proceed in a similar way while restricting to the part $\tilde{y} \subseteq y$ of interest to the user. Let $\tilde{y} = \{\tilde{y}_1, \dots, \tilde{y}_z\}$ be a subset of $y$ representing the labels of interest where $\tilde{y}_j$ is the $j$th element of $\tilde{y}$ with $j = 1, \dots, z$. Namely, given sufficient reasons for each label $y_j \in \tilde{y}$, then joining an $SR_j$ from each classifier $f_j$ with $y_j \in \tilde{y}$ is enough to form an explanation for the partial outcome $\tilde{y}$ as shown in the example 31.

**Lemma 4.** (Joint fine-grained SR) Given a sufficient reason $\tilde{x}_{\tilde{y}_j}$ for each classifier $j = 1, \dots, z$, the explanation $\tilde{x} = \wedge_{j=1}^z \tilde{x}_{\tilde{y}_j}$ satisfies conditions (1)-(2) of Definition 32 but does not guarantee to satisfy the condition (3) of the same definition.

*Proof.* (sketch) An explanation $\tilde{x} = \wedge_{j=1}^z \tilde{x}_{\tilde{y}_j}$ involves exactly one explanation from each individual base classifier in $\tilde{y}$. It is easy to check that $\tilde{x}$ verify the property 1 and 2 of Definition 32. Namely, (1) $\tilde{x}$ is part of the data instance (since each part $\tilde{x}_{\tilde{y}_j} \subseteq x$), (2) let $\acute{x} \in X$, $\tilde{x} \subset \acute{x}$, it is easy to see that $f(\acute{x}) = f(x)$. Indeed, since $\tilde{x} \subset \acute{x}$ then $\tilde{x}_{\tilde{y}_j} \subset \acute{x}$ for $j = 1, \dots, z$. Following Definition 24, $f_j(\acute{x}) = f_j(x)$ for $j = 1, \dots, z$.

As for the condition (3) of Definition 32 (minimality), combining base classifier SR explanations does not guarantee to obtain a minimal explanation. (see counter-example 38). □

**Example 38.** Let us reuse the SR explanations of Example 36. Given a target outcome $\tilde{y} = (l_2, l_3)$, the set of joint fine-grained SR explanations formed by joining SR explanations of classifiers $f_2$ and $f_3$ is $\{\{\neg x_1, x_3, x_2\}, \{\neg x_1, x_3, \neg x_4\}, \{x_3, \neg x_5, \neg x_1, x_2\}, \{x_3, \neg x_5, \neg x_4\}, \{\neg x_4, \neg x_1, x_2\}, \{\neg x_4, x_3\}\}$. Similarly to Example 36, it is clear that the explanations $\{\neg x_1, x_3, \neg x_4\}$ and $\{x_3, \neg x_5, \neg x_4\}$ are not minimal since the size of the explanation $\{\neg x_4, x_3\}$ is smaller.

**Fine-grained counterfactuals** $CF_{\tilde{y}}$: Given counterfactuals for each label $y_j \in \tilde{y}$, then joining an $CF_j$ from each classifier $f_j$ such that $y_j \in \tilde{y}$, $j=1, \dots, z$, allows to build an explanation in order to obtain the partial outcome $\tilde{y}$ as shown in the Example 32.

**Lemma 5.** (Joint fine-grained CF) Given a counterfactual $\tilde{x}_{\tilde{y}_j}$ for each classifier $j = 1, \dots, z$, the explanation $\tilde{x} = \wedge_{j=1}^z \tilde{x}_{\tilde{y}_j}$ satisfies conditions (1)-(2) of Definition 33 but does not guarantee to satisfy the condition (3) of the same definition.

*Proof.* (sketch) An explanation $\tilde{x} = \wedge_{j=1}^z \tilde{x}_{\tilde{y}_j}$ involves exactly one explanation from each individual base classifier in $\tilde{y}$. It is easy to check that $\tilde{x}$ verify the property 1 and 2 of Definition 33. Namely, (1) $\tilde{x}$ is part of the data instance (since each part $\tilde{x}_{\tilde{y}_j} \subseteq x$), (2) let $\acute{x} \in X$, $\tilde{x} \subset \acute{x}$, it is easy to see that $f(\acute{x}) = f(x)$. Indeed, since $\tilde{x}_{\tilde{y}_j} \subset \acute{x}$ then $\tilde{x}_{\tilde{y}_j} \subset \acute{x}$ for $j = 1, \dots, z$. Following Definition 25, $f_j(x[\tilde{x}]) = \acute{y}_j$ for $j = 1, \dots, z$.

As for the condition (3) of Definition 33 (minimality), combining base classifier CF explanations does not guarantee to obtain a minimal explanation. (see counter-example 39). □
**Example 39.** Let us reuse the CF explanations of Example 37. Given a target outcome $\tilde{y} = (l_1, l_2)$, the set of joint fine-grained CF explanations formed by joining CF explanations of classifiers $f_1$ and $f_2$ would be $\{\{x_2, x_3, \neg x_4\}, \{x_2, \neg x_1, \neg x_5, \neg x_4\}, \{\neg x_1, x_3, \neg x_4\}, \{\neg x_1, x_3, \neg x_5, \neg x_4\}, \{x_3, \neg x_4\}, \{\neg x_1, x_3, \neg x_4, \neg x_5\}, \{\neg x_1, x_3, \neg x_4\}, \{\neg x_1, \neg x_5, \neg x_4\}\}$. It is clear that explanation $\{x_2, x_3, \neg x_4\}$ is not minimal since the explanation $\{x_3, \neg x_4\}$ has a smaller size.

**Remark 8.** It is important to notice that our modeling through associating a set of binary classifiers (surrogate models) encoded in CNF is not the only way to use a SAT-based oracle to provide explanations. For instance, one can explain a MLC by learning a one-vs-rest binary function $f'$ that only recognizes the outcome $f(x)$ as a positive prediction. It is formally defined as follows:

$$f'(x) = \begin{cases} 1 & \text{if } f(x) = y \\ 0 & \text{otherwise.} \end{cases} \qquad (4.2)$$

However, such modeling provides neither label-based explanations nor fine-grained ones.

## Enumerating label-based explanations

Recall that label-based explanations denote structural relationships between labels. In order to extract some relationships, one can also rely on a SAT-based modeling where each individual labels $l_i$ is associated with a CNF $\Sigma_{f_i}$. Hence, checking whether some relationships hold between subsets of labels comes down to checking, for example, the corresponding logical relationships between their respective CNF formulas. Alternatively, we can rely on the predictions of labels to search for some relationships.

For instance, assume we are given a multi-label model $f$ and an input $x$, and we want to check whether $l_1$ is equivalently logic to $l_2$ ($l_1 \equiv l_2$) in the vicinity of $x$ (denoted $V_x$). We can either check if the $\Sigma_{f_1}$ is logically equivalent to $\Sigma_{f_2}$ (in which case they must share the same models), or, we can simply check that $l_1=1$ iff $l_2=1$ for any prediction $y'=f(x')$ such that $x' \in V_x$ is a complete instance.

As mentioned in the previous section, what structural relationships between labels or subsets of labels to look for (beyond the three examples cited) and how to exploit them is not a trivial question.

# 4.5 Experimental analysis

This section presents the experimental study carried out to evaluate our approach. The datasets used in our experiments are publicly available and can be found at Kaggle<fnref n="33" /> or at UCI<fnref n="34" />. The Yelp dataset can be found following this link<fnref n="35" />. Numerical and categorical attributes are binarized. The textual datasets used are pre-preprocessed and binarized.

<table><caption>Table 4.4: Properties of the different data-sets used.</caption><thead><tr><th>Dataset</th><th>#instances</th><th>#classes</th><th>#features</th><th>data type</th></tr></thead><tbody><tr><td>Augmented MNIST</td><td>70000</td><td>13</td><td>784</td><td>Images</td></tr><tr><td>Yelp Review Analysis</td><td>10806</td><td>5</td><td>671</td><td>Textual</td></tr><tr><td>IMDB Movie Genre Prediction</td><td>65500</td><td>24</td><td>30</td><td>Textual</td></tr><tr><td>Patient Characteristics Survey (NYS 2015)</td><td>105099</td><td>5</td><td>63</td><td>Textual/ Numeric</td></tr></tbody></table>

<footnote n="33">³³www.kaggle.com</footnote>

<footnote n="34">³⁴archive.ics.uci.edu/ml/</footnote>

<footnote n="35">³⁵https://www.ics.uci.edu/~vpsaini/</footnote>
In order to enumerate our symbolic explanations for binary classifiers, we rely on a SAT-based or-
acle where the enumeration of counterfactuals is done using the enumcs tool[GIL18] and the sufficient
reasons are enumerated thanks to the duality hitting set. The time limit for the enumeration of symbolic
explanations was set to 300 seconds. All experiments presented in this section have been run on a clus-
ter of computers equipped with quadcore bi-processors Intel Xeon E5-2643 3 (3.3 GHz) and 64 GB of
memory running under the CentOS Stream 8.3.

Hyper-parameters tuning

A wide range of hyper-parameters were explored in attempts to reach relatively the best performance of the surrogate models associated to the different multi-label classifiers. We conducted experiments using different radius values for each dataset in order to determine the vicinity of the explained sample that ensures a good faithfulness. The hyper-parameters tuning in this section is done using the randomized search method (RandomizedSearchCV) from Scikit-learn library in its version v0.22.1. Table 4.5 lists the hyper-parameters used to train the surrogate models for each class. Note that some dataset properties may negatively influence the performance of the surrogate model and must be taken into account. For instance, the prediction task becomes harder with an imbalanced data distribution or data with low density. An upper bound for the vicinity size of an explained instance was set to 400 samples.

<table><caption>Table 4.5: Tuned hyper-parameters used for the surrogate models of each of the labels of the different datasets.</caption>
  <thead>
    <tr>
      <th></th>
      <th>label</th>
      <th>ntree</th>
      <th>max_depth</th>
      <th>max features</th>
      <th>min samples split</th>
      <th>min samples leaf</th>
      <th>acc train (%)</th>
      <th>acc test (%)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td rowspan="5">Yelp</td>
      <td>l<sub>1</sub></td>
      <td>19</td>
      <td>100</td>
      <td>auto</td>
      <td>8</td>
      <td>4</td>
      <td>97.3</td>
      <td>92.7</td>
    </tr>
    <tr>
      <td>l<sub>2</sub></td>
      <td>19</td>
      <td>28</td>
      <td>sqrt</td>
      <td>16</td>
      <td>1</td>
      <td>97.8</td>
      <td>87.4</td>
    </tr>
    <tr>
      <td>l<sub>3</sub></td>
      <td>21</td>
      <td>100</td>
      <td>sqrt</td>
      <td>40</td>
      <td>4</td>
      <td>95.7</td>
      <td>89.1</td>
    </tr>
    <tr>
      <td>l<sub>4</sub></td>
      <td>11</td>
      <td>28</td>
      <td>auto</td>
      <td>2</td>
      <td>1</td>
      <td>100</td>
      <td>97.6</td>
    </tr>
    <tr>
      <td>l<sub>5</sub></td>
      <td>9</td>
      <td>100</td>
      <td>sqrt</td>
      <td>40</td>
      <td>2</td>
      <td>96.6</td>
      <td>94.5</td>
    </tr>
    <tr>
      <td rowspan="12">MNIST<sub>ml</sub></td>
      <td>l<sub>1</sub></td>
      <td>13</td>
      <td>28</td>
      <td>sqrt</td>
      <td>8</td>
      <td>1</td>
      <td>99.9</td>
      <td>98.9</td>
    </tr>
    <tr>
      <td>l<sub>2</sub></td>
      <td>19</td>
      <td>50</td>
      <td>sqrt</td>
      <td>8</td>
      <td>1</td>
      <td>99.9</td>
      <td>99.1</td>
    </tr>
    <tr>
      <td>l<sub>3</sub></td>
      <td>13</td>
      <td>100</td>
      <td>auto</td>
      <td>16</td>
      <td>1</td>
      <td>99</td>
      <td>98.1</td>
    </tr>
    <tr>
      <td>l<sub>4</sub></td>
      <td>9</td>
      <td>28</td>
      <td>auto</td>
      <td>8</td>
      <td>1</td>
      <td>99.8</td>
      <td>96.6</td>
    </tr>
    <tr>
      <td>l<sub>5</sub></td>
      <td>13</td>
      <td>36</td>
      <td>sqrt</td>
      <td>2</td>
      <td>2</td>
      <td>99.2</td>
      <td>97.6</td>
    </tr>
    <tr>
      <td>l<sub>6</sub></td>
      <td>11</td>
      <td>36</td>
      <td>auto</td>
      <td>2</td>
      <td>2</td>
      <td>100</td>
      <td>96.8</td>
    </tr>
    <tr>
      <td>l<sub>7</sub></td>
      <td>11</td>
      <td>28</td>
      <td>auto</td>
      <td>8</td>
      <td>4</td>
      <td>99.6</td>
      <td>98.6</td>
    </tr>
    <tr>
      <td>l<sub>8</sub></td>
      <td>21</td>
      <td>14</td>
      <td>sqrt</td>
      <td>16</td>
      <td>1</td>
      <td>99</td>
      <td>97.6</td>
    </tr>
    <tr>
      <td>l<sub>9</sub></td>
      <td>9</td>
      <td>100</td>
      <td>auto</td>
      <td>2</td>
      <td>1</td>
      <td>100</td>
      <td>97</td>
    </tr>
    <tr>
      <td>l<sub>10</sub></td>
      <td>13</td>
      <td>28</td>
      <td>sqrt</td>
      <td>8</td>
      <td>4</td>
      <td>99</td>
      <td>96</td>
    </tr>
    <tr>
      <td>l<sub>11</sub></td>
      <td>11</td>
      <td>14</td>
      <td>auto</td>
      <td>8</td>
      <td>1</td>
      <td>99.2</td>
      <td>95.5</td>
    </tr>
    <tr>
      <td>l<sub>12</sub></td>
      <td>19</td>
      <td>100</td>
      <td>auto</td>
      <td>8</td>
      <td>2</td>
      <td>99.8</td>
      <td>95.5</td>
    </tr>
    <tr>
      <td>l<sub>13</sub></td>
      <td>19</td>
      <td>36</td>
      <td>sqrt</td>
      <td>16</td>
      <td>1</td>
      <td>99.1</td>
      <td>94.1</td>
    </tr>
    <tr>
      <td rowspan="4">NYS15</td>
      <td>l<sub>1</sub></td>
      <td>12</td>
      <td>14</td>
      <td>auto</td>
      <td>8</td>
      <td>8</td>
      <td>100</td>
      <td>100</td>
    </tr>
    <tr>
      <td>l<sub>2</sub></td>
      <td>3</td>
      <td>28</td>
      <td>auto</td>
      <td>40</td>
      <td>4</td>
      <td>97.8</td>
      <td>98.4</td>
    </tr>
    <tr>
      <td>l<sub>3</sub></td>
      <td>12</td>
      <td>7</td>
      <td>sqrt</td>
      <td>8</td>
      <td>8</td>
      <td>99.7</td>
      <td>99.9</td>
    </tr>
    <tr>
      <td>l<sub>4</sub></td>
      <td>12</td>
      <td>14</td>
      <td>auto</td>
      <td>2</td>
      <td>1</td>
      <td>100</td>
      <td>99.4</td>
    </tr>
  </tbody>
</table>
<table><thead><tr><th></th><th>l<sub>5</sub></th><th>12</th><th>28</th><th>auto</th><th>2</th><th>2</th><th>99.2</th><th>97.6</th></tr></thead><tbody><tr><td rowspan="24">IMDB</td><td>l<sub>1</sub></td><td>15</td><td>7</td><td>sqrt</td><td>16</td><td>4</td><td>99.9</td><td>100</td></tr><tr><td>l<sub>2</sub></td><td>12</td><td>28</td><td>auto</td><td>16</td><td>1</td><td>99.9</td><td>99.7</td></tr><tr><td>l<sub>3</sub></td><td>12</td><td>14</td><td>auto</td><td>8</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>4</sub></td><td>15</td><td>28</td><td>sqrt</td><td>40</td><td>1</td><td>99.9</td><td>99.8</td></tr><tr><td>l<sub>5</sub></td><td>9</td><td>28</td><td>sqrt</td><td>16</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>6</sub></td><td>15</td><td>28</td><td>sqrt</td><td>2</td><td>1</td><td>100</td><td>99.7</td></tr><tr><td>l<sub>7</sub></td><td>9</td><td>7</td><td>auto</td><td>8</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>8</sub></td><td>15</td><td>14</td><td>sqrt</td><td>2</td><td>1</td><td>100</td><td>100</td></tr><tr><td>l<sub>9</sub></td><td>15</td><td>7</td><td>sqrt</td><td>16</td><td>1</td><td>100</td><td>100</td></tr><tr><td>l<sub>10</sub></td><td>6</td><td>7</td><td>auto</td><td>40</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>11</sub></td><td>15</td><td>14</td><td>sqrt</td><td>2</td><td>2</td><td>100</td><td>100</td></tr><tr><td>l<sub>12</sub></td><td>9</td><td>14</td><td>sqrt</td><td>2</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>13</sub></td><td>9</td><td>7</td><td>sqrt</td><td>40</td><td>8</td><td>100</td><td>100</td></tr><tr><td>l<sub>14</sub></td><td>15</td><td>28</td><td>sqrt</td><td>2</td><td>4</td><td>99.8</td><td>99.8</td></tr><tr><td>l<sub>15</sub></td><td>15</td><td>28</td><td>auto</td><td>16</td><td>8</td><td>100</td><td>100</td></tr><tr><td>l<sub>16</sub></td><td>12</td><td>28</td><td>sqrt</td><td>2</td><td>1</td><td>100</td><td>98</td></tr><tr><td>l<sub>17</sub></td><td>12</td><td>7</td><td>auto</td><td>40</td><td>2</td><td>99.9</td><td>99.8</td></tr><tr><td>l<sub>18</sub></td><td>15</td><td>28</td><td>sqrt</td><td>16</td><td>2</td><td>99.9</td><td>99.8</td></tr><tr><td>l<sub>19</sub></td><td>12</td><td>14</td><td>auto</td><td>40</td><td>8</td><td>100</td><td>100</td></tr><tr><td>l<sub>20</sub></td><td>12</td><td>28</td><td>sqrt</td><td>2</td><td>8</td><td>99.9</td><td>100</td></tr><tr><td>l<sub>21</sub></td><td>15</td><td>28</td><td>sqrt</td><td>8</td><td>8</td><td>99.8</td><td>100</td></tr><tr><td>l<sub>22</sub></td><td>12</td><td>28</td><td>auto</td><td>2</td><td>4</td><td>100</td><td>100</td></tr><tr><td>l<sub>23</sub></td><td>3</td><td>28</td><td>sqrt</td><td>40</td><td>1</td><td>100</td><td>100</td></tr><tr><td>l<sub>24</sub></td><td>9</td><td>7</td><td>auto</td><td>16</td><td>1</td><td>100</td><td>100</td></tr></tbody></table>

### 4.5.1 Results

In order to generate entire-outcome explanations, each base classifier of the binary relevance (BR) model is approximated using a random forest and then encoded into a CNF formula. Table 4.6 lists the average size and time of the encoding step computed over surrogate models. We can see that the average accuracy of the surrogate random forest classifiers is high meaning that the surrogate models can achieve high faithfulness levels wrt. the original model. Regarding the size of the generated CNFs expressed as the number of variables (Vars) and number of clauses (CLs), one can see that it is tractable and it is easily handled by the SAT-solver (in Step 2).

<table><caption>Table 4.6: Evaluating the CNF encoding over different datasets.</caption><thead><tr><th>Dataset</th><th>radius</th><th>AVG RF acc (%)</th><th>MIN |Σ|</th><th>AVG |Σ|</th><th>MAX |Σ|</th><th>MIN runtime (s)</th><th>AVG runtime (s)</th><th>MAX runtime (s)</th></tr></thead><tbody><tr><td>YELP</td><td>60</td><td>92.67</td><td>96/232</td><td>4827/13004</td><td>13732/36864</td><td>0.48</td><td>3.29</td><td>13.73</td></tr><tr><td>Review</td><td>180</td><td>92.73</td><td>4625/12416</td><td>6812/18395</td><td>15963/428941</td><td>2.97</td><td>4.64</td><td>15.32</td></tr><tr><td>Augmented</td><td>150</td><td>93.97</td><td>509/1268</td><td>12095/32353</td><td>14308/38344</td><td>0.68</td><td>12.58</td><td>16.13</td></tr><tr><td>MNIST</td><td>250</td><td>96.27</td><td>423/1119</td><td>9556/25455</td><td>15105/40530</td><td>1.35</td><td>7.93</td><td>14.41</td></tr><tr><td>IMDB</td><td>30</td><td>99.53</td><td>863/2344</td><td>1282/3533</td><td>3149/8558</td><td>0.82</td><td>1.09</td><td>2.73</td></tr><tr><td>NYS15</td><td>63</td><td>96.73</td><td>2446/6615</td><td>7887/21370</td><td>11305/30594</td><td>1.91</td><td>6.73</td><td>10.12</td></tr></tbody></table>
Table 4.7 shows the results of enumerating both sufficient reasons and counterfactuals explanations. Using local surrogate models over multiple values of the radius, the symbolic explanations of each base classifier are enumerated. An average is then computed and is given in Table 4.7 and Table 4.8. We notice over the different datasets that the average time necessary to enumerate all the explanations for a given instance grows linearly and varies from 2 to 20 seconds to find all the possible explanations of all the base classifiers. For instance, if we compare the enumeration time of mono-label classifiers trained on the MNIST dataset versus the multi-label classifier, we can see that the trend is the same. The same finding holds for the number of explanations where one can see that on average this number increases proportionally to the size of the input features set. We also notice that the number of *SR* explanations is of the same order as the number of *CF* ones. Interestingly enough, one can notice that the time required to find one sufficient reason (resp. counterfactual) explanation is very negligible, meaning that the proposed approach is feasible in practice and allows to explain medium sized multi-label classifiers efficiently.

<table><caption>Table 4.7: Enumeration of entire-outcome counterfactual explanations.</caption><thead><tr><th>Dataset</th><th>radius</th><th>MIN #CFs</th><th>AVG #CFs</th><th>MAX #CFs</th><th>runtime<br>One CF (s)</th><th>MIN<br>runtime(s)</th><th>AVG<br>runtime(s)</th><th>MAX<br>runtime(s)</th></tr></thead><tbody><tr><td>YELP</td><td>60</td><td>1891</td><td>2025</td><td>6858</td><td>≤ 10<sup>-3</sup></td><td>≤ 10<sup>-3</sup></td><td>2.29</td><td>13.46</td></tr><tr><td>Review</td><td>180</td><td>2601</td><td>3203</td><td>9693</td><td>≤ 10<sup>-3</sup></td><td>0.009</td><td>4.5</td><td>29.97</td></tr><tr><td>Augmented<br>MNIST</td><td>150</td><td>96</td><td>4971</td><td>9347</td><td>≤ 10<sup>-3</sup></td><td>0.02</td><td>15.61</td><td>33.27</td></tr><tr><td>IMDB</td><td>250</td><td>1158</td><td>5027</td><td>11323</td><td>≤ 10<sup>-3</sup></td><td>1.77</td><td>15.9</td><td>45.36</td></tr><tr><td>NYS15</td><td>30</td><td>5</td><td>14</td><td>22</td><td>≈ 0</td><td>0.13</td><td>2.78</td><td>7.47</td></tr><tr><td>NYS15</td><td>63</td><td>134</td><td>1052</td><td>2399</td><td>≤ 10<sup>-4</sup></td><td>0.15</td><td>2.83</td><td>9.37</td></tr></tbody></table>

<table><caption>Table 4.8: Enumeration of entire-outcome sufficient reasons explanations.</caption><thead><tr><th>Dataset</th><th>radius</th><th>MIN #SRs</th><th>AVG #SRs</th><th>MAX #SRs</th><th>enumtime<br>One SR (s)</th><th>MIN<br>enumtime(s)</th><th>AVG<br>enumtime(s)</th><th>MAX<br>enumtime(s)</th></tr></thead><tbody><tr><td>YELP<br>Review</td><td>60</td><td>13116</td><td>23167</td><td>38620</td><td>0.028</td><td>10.94</td><td>19.37</td><td>31.95</td></tr><tr><td>Augmented<br>MNIST</td><td>150</td><td>11292</td><td>11956</td><td>12621</td><td>0.053</td><td>12.26</td><td>13.06</td><td>13.85</td></tr><tr><td>IMDB<br>Movie<br>Genre</td><td>30</td><td>3</td><td>41.83</td><td>161</td><td>0.004</td><td>0.003</td><td>0.02</td><td>0.07</td></tr></tbody></table>

## Fine-grained explanations

The following results concern only fine-grained *CF* explanations. However, the findings still hold for the enumeration of the fine-grained *SR* explanations. We vary the size *k*<fnref n="36" /> of the target partial prediction *y*<sub>target</sub> and we choose randomly the labels that compose it, i.e. the labels we are going to explain given an instance *x*. The results are obtained on a BR model trained on each dataset. Both cases of negative and positive predictions are considered and are presented in two parts: we use the acronym *POS* to refer to the explanations of the positively predicted labels and the acronym *NEG* for those of the negatively predicted. Similarly to the entire-outcome explanations, we are first interested in measuring the size of the CNF encoding associated to the labels of interest (*l*<sub>*i*</sub> ∈ *y*<sub>target</sub>), and also we are interested in the enumeration times needed and the size of the sets of explanations generated.

Table 4.9 lists the average size of the CNF formula and runtime of the encoding step. We can see that the

<footnote n="36">³⁶Recall that *k* takes values ∈ [1, |Y|] with |Y| being the number of classes recognized by the MLC.</footnote>
<table><caption>Table 4.9: Evaluation of the CNF encoding size of the different datasets.</caption><thead><tr><th>Dataset</th><th>Pred Type</th><th>AVG RF's accuracy</th><th>MIN |Σ| (Vars/CLs)</th><th>AVG |Σ| (Vars/CLs)</th><th>MAX |Σ| (Vars/CLs)</th><th>MIN runtime (s)</th><th>AVG runtime (s)</th><th>MAX runtime (s)</th></tr></thead><tbody><tr><td rowspan="2">YELP Review</td><td>NEG</td><td>93.5%</td><td>39/94</td><td>4663/12572</td><td>18616/49938</td><td>0.6</td><td>3.75</td><td>23.16</td></tr><tr><td>POS</td><td>89.95%</td><td>28/62</td><td>4071/10932</td><td>12043/32308</td><td>0.5</td><td>2.94</td><td>9.67</td></tr><tr><td rowspan="2">Augmented MNIST</td><td>NEG</td><td>97.48%</td><td>103/250</td><td>6552/17352</td><td>15557/41797</td><td>0.69</td><td>5.32</td><td>15.36</td></tr><tr><td>POS</td><td>92.36%</td><td>117/292</td><td>10808/28840</td><td>18441/49788</td><td>0.97</td><td>10.43</td><td>21.18</td></tr><tr><td rowspan="2">IMDB Movie Genre</td><td>NEG</td><td>99.67%</td><td>279/732</td><td>1426/3860</td><td>7556/20261</td><td>0.79</td><td>1.56</td><td>7.55</td></tr><tr><td>POS</td><td>98.37</td><td>128/296</td><td>3002/8264</td><td>10504/28378</td><td>0.68</td><td>2.61</td><td>8.69</td></tr></tbody></table>

size of the CNFs on average is tractable and that it is almost the same result obtained when enumerating the entire-outcome explanations.

Table 4.10 presents the results of enumerating fine-grained counterfactuals. First, we can say that the size of the CNFs has practically not changed compared to the entire-outcome explanations (see Table 4.6). We clearly notice that on average the number of explanations generated has strongly decreased compared to the results of Table 4.7. This finding makes sense since we have reduced the number of labels to explain. Secondly, we notice that the average time necessary for enumerating one counterfactual is negligible and meets the results of Table 4.7.

<table><caption>Table 4.10: Enumerating fine-grained counterfactuals.</caption><thead><tr><th></th><th>Operation type</th><th>|y<sub>target</sub>|</th><th>AVG #CFs</th><th>MAX #CFs</th><th>enumerative One CF (s)</th><th>AVG |CF|</th><th>AVG enumerated time(s)</th><th>AVG enumerated time(s)</th></tr></thead><tbody><tr><td rowspan="10">YELP</td><td rowspan="4">Expansion (NEG to POS)</td><td>1</td><td>977</td><td>5009</td><td>≤ 10<sup>-4</sup></td><td>2</td><td>0.83</td><td>7.16</td></tr><tr><td>2</td><td>1678</td><td>6716</td><td>≤ 10<sup>-4</sup></td><td>2</td><td>1.65</td><td>11.83</td></tr><tr><td>3</td><td>2102</td><td>7876</td><td>≤ 10<sup>-4</sup></td><td>3</td><td>2.17</td><td>20.19</td></tr><tr><td>4</td><td>3395</td><td>8933</td><td>≤ 10<sup>-4</sup></td><td>3</td><td>4.32</td><td>17.4</td></tr><tr><td rowspan="3">Contraction (POS to NEG)</td><td>1</td><td>848</td><td>6550</td><td>≤ 10<sup>-4</sup></td><td>2</td><td>0.98</td><td>12.99</td></tr><tr><td>2</td><td>490</td><td>5066</td><td>≤ 10<sup>-4</sup></td><td>2</td><td>0.52</td><td>8.01</td></tr><tr><td>3</td><td>441</td><td>3723</td><td>≤ 10<sup>-4</sup></td><td>2</td><td>0.4</td><td>5.14</td></tr><tr><td rowspan="10">MNIST ML</td><td rowspan="3">Expansion (NEG to POS)</td><td>1</td><td>1932</td><td>10011</td><td>≤ 10<sup>-3</sup></td><td>3</td><td>3.18</td><td>27.08</td></tr><tr><td>2</td><td>2158</td><td>9769</td><td>≤ 10<sup>-3</sup></td><td>5</td><td>3.95</td><td>39.56</td></tr><tr><td>3</td><td>3895</td><td>8395</td><td>≤ 10<sup>-3</sup></td><td>5</td><td>8.9</td><td>28.52</td></tr><tr><td rowspan="3">Contraction (POS to NEG)</td><td>1</td><td>2799</td><td>14759</td><td>≤ 10<sup>-3</sup></td><td>2</td><td>5.26</td><td>54.19</td></tr><tr><td>2</td><td>3821</td><td>12895</td><td>≤ 10<sup>-3</sup></td><td>3</td><td>9.54</td><td>48.86</td></tr><tr><td>3</td><td>4642</td><td>12007</td><td>≤ 10<sup>-3</sup></td><td>4</td><td>12.10</td><td>43.79</td></tr><tr><td rowspan="10">IMDB</td><td rowspan="3">Expansion (NEG to POS)</td><td>1</td><td>6</td><td>30</td><td>≈ 0</td><td>2</td><td>0.0023</td><td>0.04</td></tr><tr><td>2</td><td>10</td><td>22</td><td>≈ 0</td><td>2</td><td>0.0041</td><td>0.021</td></tr><tr><td>3</td><td>10</td><td>43</td><td>≈ 0</td><td>2</td><td>0.0038</td><td>0.024</td></tr><tr><td rowspan="3">Contraction (POS to NEG)</td><td>1</td><td>16</td><td>60</td><td>≈ 0</td><td>1</td><td>0.009</td><td>0.02</td></tr><tr><td>2</td><td>16</td><td>62</td><td>≈ 0</td><td>1</td><td>0.008</td><td>0.02</td></tr><tr><td>3</td><td>23</td><td>93</td><td>≈ 0</td><td>1</td><td>0.01</td><td>0.03</td></tr></tbody></table>
## 4.6 Conclusion

In the literature, very few studies have focused on explaining multi-label classifiers, thus it is not obvious to compare our approach to existing ones. Generating symbolic explanations for multi-label classification is quite straightforward to accomplish within the symbolic framework presented in the Chapter 3. However, it is worth noticing that the contributions of this work are not simple extensions from the multi-class framework to the multi-label one since there are, for example, concepts specific to the multi-label case such as label-based and fine-grained explanations. We introduced the concept of the label-based explanations in order to take advantage of the structural relationships between labels in order to reduce the number of generated explanations and improve their presentation to the user.

The declarative paradigm used in our work has been successfully used in explainable AI [Ber21] but also for other problems such as declarative data mining where one can enumerate for example frequent itemsets using a SAT oracle [JSS15]. Doing so, we take advantage of the strengths of modern SAT solvers used as oracles. In the case of ML models that do not admit direct CNF representation, a crucial component of the proposed approach is to approximate the model with another one that does admit such a representation. We intend in future work to focus on the extraction of label-based explanations and their combination with feature-based ones in order to reduce the number of explanations and improve their presentation. We also go beyond symbolic explanations and address score-based explanations in a multi-label setting in the next part of this manuscript.
# Part III

## Feature-attribution explanations
5

Feature attribution explanations for
single-label classification

Large amounts of efforts have been devoted to developing approaches to explain individual classifi-
cation decisions such as decision rules [RSG18], counterfactual examples [WMR17] and logic-based
approaches [SCD18b, DH22, INMS19a, Ign20, INMS19b, ABB<sup>+</sup>22a]. We will focus in this part on a
type of explanation well known in XAI called feature attribution (e.g. SHAP [LL17], LIME [RSG16]).
We start with providing a definition of feature attribution explanation in a general setting as well as the
main approaches that generate them in Section 5.1. In section 5.2.1 we will present the set of fine-grained
properties we propose to analyze, rank and select explanations and in section 5.2.2 the ones allowing to
assess the relevance of features. We also propose some scoring functions to check out the suggested prop-
erties. Full examples of explanations produced by the whole approach and an evaluation are provided in
section 5.3.

**5.1 Feature attribution explanations**

Feature attribution is a popular and widely used approach for explaining the predictions of machine
learning models and is by far the most well-studied explainability technique [BSH<sup>+</sup>10, GBY<sup>+</sup>18]. De-
pending on the application domains and the nature of the data, they are sometimes referred to as pixel
saliency, saliency maps, rationales, attentions, feature-level interpretations, feature importance or simply
feature attributions. Intuitively, a feature attribution method associates a numerical score with each input
feature reflecting the weight or influence of this feature in the prediction of a machine learning model.
It is worth to notice that there is no consensus on the definition or the semantics of these feature attribu-
tions nor on the way to systematically evaluate their relevance. In practice, this can be seen through the
various existing methods to derive feature importance scores reflecting the influence of each attribute for
prediction tasks such as regression or multi-class classification.

**5.1.1 Review of related works**

As mentionned in the state-of-the-art chapter, explainable AI has focused on two main families of post-
hoc approaches when it comes to explaining machine learning models. The first one focuses on for-
mal XAI to provide *symbolic* explanations ([SCD18b], [INMS19b], [Rei87], [Rym94], [INMS19b]) and
are also used for verification and diagnosis purposes ([Rei87], [Rym94], [INMS19b]), while the second
one provides insights into how much each feature contributed to the outcome decision and focuses on
attributing *numerical* importance scores to the input features. These techniques are used across many dif-
ferent domains and are popular amongst machine learning scientists who want to sanity check a model before deploying it [BXS<sup>+</sup>20]. The main objective of our contribution is to firstly to provide complementary types of symbolic explanations and secondly provide score-based ones for a better understanding and usability of explanations. The first part of our work was presented previously in Chapter 3 of part one of this manuscript. We will get into more details about the second part of our contribution within this chapter and present how we provide feature attribution explanations based on some properties.

Feature attribution consists in associating scores to each input feature $X_i$ of an instance $x$ to reflect to what extent $X_i$ contributed to the prediction $f(x)$. Formally, a feature attribution for multi-class tasks is defined as follows :

**Definition 34 (Feature attribution)**. Assume we are given a multi-class classifier $f$ and a feature attribution method $h$. Assume also a data instance $x = (x_1,...,x_n) \in X$. An attribution of the prediction $y = f(x)$ at input instance $x$ is the vector $h(f, x) = (a_1, ..., a_n)$ where each score $a_i \in \mathbb{R}$.

According to the considered method, a feature attribution $a_i$ for the feature $X_i$ may denote sensitivity [SVZ13b], relevance [BBM<sup>+</sup>15], local influence [RSG16], Shapley values [LL17], filter activations [NHWF21], etc. Examples for common feature attribution methods are provided in Section 1.2.2 and we can cite SHAP [LL17], LIME [RSG16], saliency maps [SVZ13a, ZF14, STY17, SDBR15, PLPN19], Grad-CAM [SCD<sup>+</sup>17], integrated gradients [STY17], LRP [BBM<sup>+</sup>15] and DeepLift [SGK17] (see [LPK20, LPK21] for recent literature surveys).

In the rest of this chapter, we will present how we widened the scope of our investigation to compute feature attribution based on symbolic explanations presented previously (cf Chapter 3). In the case of a single-label classification, we limit ourselves in our study to proposing score-based explanations and feature attribution by relying on such explanations and associating scores w.r.t to some properties. As for the multi-label setting, we will expand this study in Chapter 6 to consider other explainability approaches as oracles and see how to combine or aggregate their output to propose feature attribution for multi-label decisions.

## 5.2 Feature attribution explanations for single-label classification

The symbolic explanations we proposed so far to explain individual classification decisions based on the observations that MUSes and MCSes are cornerstones of analyzing thus measuring inconsistencies [LS08] and can be obtained in large numbers. This causes a selection problem as the whole set of explanations can be very large. Indeed, considering the SAT-based modeling we adopt in our approach, an inconsistent Boolean formula can potentially have a large set of explanations (MUSes and MCSes). More precisely, for a knowledge base containing $p$ clauses, the number of MUSes and MCSes can be in the worst case exponential in $p$ [LS08]. Thus, defining how to measure the quality of an explanation and to convey how much the model relies on certain features to make a decision at some specific input becomes necessary in order to focus on those providing more insights.

Figure 5.1 depicts the overview of our XAI approach at **Step 3**. Indeed, in addition to the large number of symbolic explanations, the different needs of users and nature of systems from an application to another raise the question of *which explanations to choose ?* or *which explanations and (or) what features are most relevant ?* We address all of the issues raised above by giving at the same time a local score-based explanation with respect to some properties<sup>37</sup>, and also, feature attribution providing feature-level importance scores for how much a given input feature contributes to a model’s output. These properties can be interpreted as relevance characteristics of an explanation<sup>38</sup> and are presented in Section 5.2. We

<footnote n="37"><sup>37</sup>Those properties can provide information on certain aspects of the generated explanations.</footnote>

<footnote n="38"><sup>38</sup>Of course, the relevance depends on the user's interpretation and the context.</footnote>
<figure><img src="image_55.png" /><figcaption>Figure 5.1: Focus on the Step 3 of the proposed approach</figcaption></figure>

also propose some examples of scoring functions to assess them numerically. This corresponds to **Step 3 (Explanation and feature relevance scoring)** in Figure 5.1.

Before we start the presentation of the properties proposed to assess the relevance of both explanations and features, we introduce some notations and definitions essential for understanding the rest of the work:

* Let $E(x, f)$ be a non empty set denoting the set of explanations (either **SR** or **CF**) for an input instance $x$ predicted negatively by the classifier $f$.

* An explanation is denoted by $e_i$ where $i \in [0, |E(x, f)|]$.

* The neighborhood of $x$ within the radius $r$ denoted $V(x, r)$ (also written $V_x$ for short) is formally defined as $V(x, r):\{v \in X \mid \text{dist}(x, v) \le r\}^{39}$.

* Given an explanation $e_i$, let $\text{size}(e_i)$ denote the number of variables composing it.

**Definition 35 (Extent of an explanation).** Let $\text{Extent}(e_i, x, r)$ be the set of data instances defined as follows: $\{v \in V(x, r) \mid f(v)=f(x) = 0 \text{ and for } e_i \in E(v, f)\}$.

Intuitively, $\text{Extent}(e_i, x, r)$ denotes the set of data instances from the neighborhood of $x$ that are negatively predicted by $f$ and sharing the explanation $e_i$. We provide illustrative examples to describe the different concepts we introduce in this section.

**Example 40.** Let's continue with the United Stated Congressional Voting Records (firstly introduced in example 19) where a trained model $f$ classify instances as 'Republican' or 'Democrat' based on the 16 key votes identified. Given a radius set to 3 ($r = 3$), then the neighborhood of $x$ is $V(x, 3) = \{x', x''\}$. Let the set of sufficient reason explanations associated to each instance from $V(x, 3)$ as follows :

The extent of the different explanations $\in \text{Exp}(f, x)$ are illustrated in Figure 5.3. As shown, an explanation belonging to several set of explanations $E(x_i, f)$ is present in every set highlighted with

<footnote n="39">³⁹`dist(x,v)` denotes a distance measure that returns the distance between `x` and `v`.</footnote>
<figure><img src="image_56.png" /><figcaption>(a) MUSes of $\Sigma_{f,x}$.</figcaption></figure>

<figure><img src="image_57.png" /><figcaption>(b) MUSes of $\Sigma_{f,x'}$.</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(c) MUSes of $\Sigma_{f,x''}$.</figcaption></figure>

$$E(x, f) = \{ e_1 = \{X_4, X_5\}, e_2 = \{X_5, X_{12}\}, e_3 = \{X_4, X_9, X_{12}\} \}$$

$$E(x', f) = \{ e'_1 = \{X_5, X_{12}\}, e'_2 = \{X_3, X_4\} \}$$

$$E(x'', f) = \{ e''_1 = \{X_5, X_{12}\}, e''_2 = \{X_4, X_5\}, e''_3 = \{X_9, X_{10}\}, e''_4 = \{X_5, X_9\} \}$$

the same color. For instance, we can see that the explanation $e_1$ is present in every $E(x_i, f)$ while explanation $e_3$ is specific to the sample $x$.

<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /><figcaption>Figure 5.3: Extent of $E(x, f)$ in the neighborhood $V(x, 3) = \{x', x''\}$.</figcaption></figure>

Hence, the extent sets of explanations in $E(x, f)$ are represented in the following:

$$Extent(e_1, x, 3) = \{ x, x'' \}$$

$$Extent(e_2, x, 3) = \{ x, x', x'' \}$$

$$Extent(e_3, x, 3) = \{ x \}$$

We define now a similar notion to the extent of an explanation but at a feature-level.

**Definition 36 (Cover of a feature).** Let $Cover(X_k, x)$ be the set of explanations from $E(x, f)$ where the feature $X_k$ is involved (namely $Cover(X_k, x) = \{e_i | X_k \in e_i \text{ for } e_i \in E(x, f)\}$).

A cover of a feature designates the set of explanations including the variable $X_i$. It can be computed within set of explanations associated to $x$ (i.e. $E(x, f)$) or the set of explanations of instances from the locality of $x$ (i.e. $E(v, f)$).

$v \in V(x,r)$
**Example 41** (Example 40 continued'.) The cover of the different variables composing the explanations of $x$ within $E(x, f)$ is illustrated in Figure 5.4 and given in the following :

<figure><img src="image_62.png" /><figcaption>Figure 5.4: Cover of the variables in the explanation set $E(x, f)$.</figcaption></figure>

$$ \mathrm{Cover}(X_4, x) = \{ e_1, e_3 \} $$

$$ \mathrm{Cover}(X_5, x) = \{ e_1, e_2 \} $$

$$ \mathrm{Cover}(X_9, x) = \{ e_1 \} $$

$$ \mathrm{Cover}(X_{12}, x) = \{ e_2, e_3 \} $$

The cover of the different variables composing the explanations of $x$ within $E(v, f)$ are illustrated in Figure 5.5 and given in the following :

<figure><img src="image_63.png" /><figcaption>Figure 5.5: Cover of variables in $E(x, f)$ in the neighborhood $V(x, 3)$.</figcaption></figure>
$$ \text{Cover}(X_4, v)_{v \in V_x} = \{e_1, e_3, e'_2, e''_2\} $$

$$ \text{Cover}(X_5, v)_{v \in V_x} = \{e_1, e_2, e'_1, e''_1, e''_2, e''_4\} $$

$$ \text{Cover}(X_9, v)_{v \in V_x} = \{e_3, e''_3, e''_4\} $$

$$ \text{Cover}(X_{12}, v)_{v \in V_x} = \{e_2, e_3, e'_1, e''_1\} $$

### 5.2.1 Properties of symbolic explanations and scoring functions

In this section, we propose three natural properties to evaluate explanations and capture some of the aspects allowing their analysis, ranking and selection:

**Parsimony (PAR)**: The parsimony is a natural property allowing to select the simplest or shortest explanations (namely, explanations involving less features). The intuition behind a simpler explanation is that it is easier to focus on understanding or changing few variables instead of trying to change many features. Hence, the parsimony score of an explanation $e_i$ should be inversely proportional to its size. Formally, given a data instance $x$, its set of explanations $E(x, f)$: For two explanations $e_1$ and $e_2$ from $E(x, f)$: $PAR(e_1)>PAR(e_2)$ iff $size(e_1)<size(e_2)$. An example of a scoring function satisfying the parsimony property is:

$$ S_{PAR}(e_i) = \frac{1}{size(e_i)} \qquad (5.1) $$

**Generality (GEN)**: This property aims to reflect how much an explanation can be general to a multitude of data instances, or in the opposite, reflect how much an explanation is specific to the instance $x$. Intuitively, the generality of an explanation should be proportional to the number of data instances it explains. Given a data instance $x$, its set of explanations $E(x, f)$, its neighborhood $V(x, r)$ and two explanations $e_1$ and $e_2$ from $E(x, f)$: $GEN(e_1)>GEN(e_2)$ iff $|Extent(e_1, x, r)| > |Extent(e_2, x, r)|$. An example of a scoring function capturing this property is:

$$ S_{GEN}(x, r, e_i) = \frac{|Extent(e_i, x, r)|}{|V(x, r)|} \qquad (5.2) $$

Intuitively, this scoring function assesses the proportion of data instances in the neighborhood of the instance $x$ that are negatively predicted and that share the explanation $e_i$.

**Explanation responsibility (RESP)**: This property allows to answer the question how much an explanation is responsible for the current prediction. Intuitively, if there is a unique explanation, then this latter is fully responsible of the decision (only cause of the decision). Hence, the responsibility of an explanation should be inversely proportional to the number of explanations in $E(x, f)$. Given two different data instances $x_1$ and $x_2$, their respective explanation sets $E(x_1, f)$ and $E(x_2, f)$ and an explanation $e_i \in E(x_1, f)$ and $e_j \in E(x_2, f)$, we have:

$RESP(x_1, e_i) < RESP(x_2, e_j)$ iff $|E(x_1, f)| > |E(x_2, f)|$. For a given data instance $x$, the responsibility of $e_i \in E(x, f)$ could be evaluated using the following scoring function:

$$ S_{RESP}(x, e_i) = \frac{1}{|E(x, f)|} \qquad (5.3) $$
**Remark 9.** The scoring function of Eq. 5.3 assigns the same score to every explanation in $E(x, f)$. It means that it can be used to compare two different sets of explanations but it can not be used to evaluate explanations within the same set.

To remedy the problem raised in the previous remark, we propose to define a more granular evaluation of the responsibility of explanations in $E(x, f)$ by calculating a responsibility score for each $e_i$ in the neighborhood of $x$. An example of a scoring function capturing this property, would be:

$$S_{RESP}(x, r, e_i) = \max_{v \in V(x,r)} (S_{RESP}(v, e_i)) \qquad (5.4)$$

**Example 42** (Example 40 continued). Given the set of sufficient reason explanations of $x$ and the instances from its neighborhood, we evaluate the relevance of explanations $e \in E(x, f)$ w.r.t to the properties and by the means of the scoring functions presented above. These score-based explanations are then ranked in order to choose the more convenient one w.r.t to the need of the user for whom these explanations are intended.

<table><caption>Table 5.1: Evaluating explanations w.r.t to the *PAR*, *GEN* and *RESP* properties.</caption><thead><tr><th></th><th colspan="4">criteria</th></tr><tr><th>explanation</th><th>$S_{PAR}(e_i)$</th><th>$S_{GEN}(x, r, e_i)$</th><th>$S_{RESP}(x, e_i)$</th><th>$S_{RESP}(x, r, e_i)$</th></tr></thead><tbody><tr><th>$e_1$</th><td><b>1/2</b></td><td>2/3</td><td>1/3</td><td>1/3</td></tr><tr><th>$e_2$</th><td><b>1/2</b></td><td><b>3/3</b></td><td>1/3</td><td><b>1/2</b></td></tr><tr><th>$e_3$</th><td>1/3</td><td>1/3</td><td>1/3</td><td>1/3</td></tr></tbody></table>

These properties make it possible to analyze and if necessary select or order the symbolic explanations according to a particular property. Of course, we can define other properties or variants of these properties (e.g. relative parsimony to reflect the parsimony of one explanation compared to the parsimony of the rest of the explanations). The properties can have a particular meaning or a usefulness depending on the applications and users. It would be interesting to study the links and the interdependence between these properties. Let us now see properties allowing to assess the relevance of the features reflecting their contribution to the prediction.

### 5.2.2 Properties of features-based explanations and scoring functions

It is possible to have inside the set of explanations the same cardinality and extent for different explanations, and therefore, they cannot be distinguished by properties such as *parsimony*, *generality and responsibility*. Hence, we consider properties at a feature-level by taking a look into the variables composing the explanation and trying to assess their relevance. We propose the following properties for the features:

**Feature involvement (FI)**: This property is intended to reflect the extent of involvement of a feature within the set of explanations. The intuition is that a feature that participates in several explanations of the same instance $x$ should have a higher importance compared to a less involved feature. Given a data instance $x$, its set of explanations $E(x, f)$, and two features $X_1$ and $X_2$:

$\mathcal{FI}(X_1, x) > \mathcal{FI}(X_2, x)$ iff $|\mathcal{Cover}(X_1, x)| > |\mathcal{Cover}(X_2, x)|$. An example of a scoring function capturing this property is:

$$S_{FI}(X_k, x) = \frac{|\mathcal{Cover}(X_k, x)|}{|E(x, f)|} \qquad (5.5)$$
**Feature generality (FG)**: This property captures to what extent a feature is frequently involved in explaining instances in the vicinity of the sample to explain *x*. Given a sample *x*, its vicinity $V(x, r)$ and their explanation set $E(V(x, r), f)$ defined as $\bigcup_{v \in V(x,r)} E(v, f)$ and two features $X_1$ and $X_2$:

$\mathcal{FG}(X_1) > \mathcal{FG}(X_2)$ iff $|\bigcup_{v \in V(x,r)} \mathcal{Cover}(X_1, v)| > |\bigcup_{v \in V(x,r)} \mathcal{Cover}(X_2, v)|$. An example of a scoring function

capturing this property could be:

$$S_{\mathcal{FG}}(X_k) = \frac{|\bigcup_{v \in V(x,r)} \mathcal{Cover}(X_k, v)|}{|\acute{x} \in E(V(x, r), f)|} \quad (5.6)$$

**Feature responsibility (FR)**: This property is intended to reflect the responsibility or contribution of a feature $X_i$ within the set of symbolic explanations of *x*. Intuitively, the responsibility of a feature should be inversely proportional to the size of the explanations where it is involved (the shortest the explanation, the highest the responsibility value of its variables). Given two features $X_1, X_2$ with non empty covers: $\mathcal{FR}(X_1) > \mathcal{FR}(X_2)$ iff $\text{aggr}(\text{size}(e_j)) < \text{aggr}(\text{size}(e_j))$ where $\text{aggr}$ stands for an aggregation function (e.g. min, max, $AVG$, etc.). An example of a scoring function satisfying this property is:

$$S_{\mathcal{FR}}(X_k) = \frac{1}{\underset{e_j \in \text{Cover}(X_k, x)}{AVG(\text{size}(e_j))}} \quad (5.7)$$

**Example 43.** Similarly to Example 42 on score-based explanations, we will take an example for the computation of the different feature attributions w.r.t to the Feature involvement (FI), Feature generality (FG) and Feature responsibility (FR).

<table><caption>Table 5.2: Evaluating explanations w.r.t to the *PAR*, *GEN* and *RESP* properties.</caption><thead><tr><th>feature</th><th>$S_{\mathcal{FI}}(X_k, x)$</th><th>$S_{\mathcal{FG}}(X_k)$</th><th>$S_{\mathcal{FR}}(X_k)$</th></tr></thead><tbody><tr><td>$X_4$</td><td>2/3</td><td>4/9</td><td>1/5</td></tr><tr><td>$X_5$</td><td>2/3</td><td><b>2/3</b></td><td>1/4</td></tr><tr><td>$X_9$</td><td>1/3</td><td>1/3</td><td><b>1/2</b></td></tr><tr><td>$X_{12}$</td><td>2/3</td><td>4/9</td><td>1/5</td></tr></tbody></table>

In addition to the different scores associated to properties presented above, we can aggregate them (e.g., by averaging) to get an overall score depending on the user needs. To the best of our knowledge, our **agnostic** and **declarative** approach was the first that generates different types of symbolic explanations and **fine-grained** score-based ones. Note that this is not an exhaustive list of properties that one could be interested in in order to select and rank explanations or rank features according to their influence on the prediction. For instance, many desiderata can be required for an explanation in order to explain predictions in understandable terms to a user and to its expectations such as plausibility (in the sense that explanations need to be sufficiently convincing to users) [LBJ16, LCH$^+$19, SZM19] and readability [WR15, YRS17, ALSA$^+$17]. However, it is unclear how to choose since standard tests and benchmarks to evaluate such requirements are lacking and such evaluations still remain an open problem [DVK17, JG20].
## 5.3 Experimental results

This section presents some experiments of the score-based and feature attribution explanations generated according to the approach depicted within this chapter. We considered a selection of datasets from the literature and publicly available and can be found on Kaggle<sup>40</sup> or UCI<sup>41</sup>. The studied datasets are associated with binary classification tasks and are listed in Table 5.3. No pre-processing was performed on the data except the binarization of variables.

<table><caption>Table 5.3: Properties of the datasets used.</caption><thead><tr><th>Dataset</th><th>#instances</th><th>#features</th><th>data type</th></tr></thead><tbody><tr><td>MNIST</td><td>70000</td><td>784</td><td>Images</td></tr><tr><td>MONK's Problems</td><td>181</td><td>16</td><td>Numerical</td></tr><tr><td>Spect Heart</td><td>160</td><td>22</td><td>Numerical</td></tr><tr><td>Congressional US Voting</td><td>435</td><td>16</td><td>Numerical</td></tr><tr><td>Heart disease</td><td>303</td><td>9</td><td>Numerical</td></tr><tr><td>Breast Cancer</td><td>287</td><td>48</td><td>Numerical</td></tr></tbody></table>

The experimental protocol used to train surrogate models is already presented in Chapter 3 and remains applicable for this section. All experiments were performed on machines equipped with an Intel Core i7-7700 (3.60GHz ×8) processors, with 32 Gb of RAM and under the Linux Cen-tOS operating system. The time-out has been set to 300 seconds for each execution of an enumeration algorithm.

We present in the following some examples of our score-based explanations provided to explain individual predictions of black-boxes trained on different datasets. In addition, we compare the relevance of our numerical explanations to the ones of similar "feature-attribution" approaches where we consider an important method in Explainable AI: the SHAP<sup>42</sup> tool implementing the SHAP (SHapley Additive exPlanations) approach [LL17].

Figures 5.6a and 5.6b are an example of the feature scores associated to sufficient reasons ($SR_x$) and counterfactuals explanations ($CF_x$) enumerated to explain an instance negatively predicted from the SPECT dataset. The score-based explanations attributed to the features composing the explanations are plotted into bar charts. The blue bar represents the Feature responsibility ($FR$), the red bar represents the Feature involvement ($FI$) and finally, the orange bar represents the Feature generality ($FG$). As observed, the order of importance of features varies depending on the desiderata chosen. An example of the SHAP explanation generated for the instance is also provided in Figure 5.7. Note that the representation of explanations can be done in different ways. For instance, it can be more convenient to represent our explanations in the form of heatmaps when the inputs are images. Such a representation allows to visualize and highlight the part of the input having the highest scores w.r.t to the different criteria. For instance, Figure 5.8 shows heatmaps corresponding to the Feature involvement ($FI$) scores (column "b-c") and Feature responsibility ($FR$) (column "d-e") scores of the different input variables involved in $SR_x$ and $CF_x$. Compared to SHAP explanations (Figure 5.7), ours are most often visually simpler, clearer and easier to understand and use.

To compare our results with existing methods and test if they correspond with those of SHAP, we follow the following protocol: Given a dataset, here we used the Monk's Problems, Spect Heart, Congressional US Voting, Heart disease and Breast Cancer datasets, we enumerate explanations for all instances to using a radius equal to the half of the input space size ($r = |X|/2$). We enumerate symbolic

<footnote n="40"><sup>40</sup>Kaggle dataset: (https://www.kaggle.com/).</footnote>

<footnote n="41"><sup>41</sup>UCI dataset: (http://archive.ics.uci.edu/ml/).</footnote>

<footnote n="42"><sup>42</sup>Available at (https://github.com/slundberg/shap).</footnote>
<figure><img src="image_64.png" /><figcaption>Figure 5.6: Examples of explanations on a test input negatively predicted from the SPECT dataset.</figcaption></figure>

explanations using our approach named ASTERYX and compute the different score-based explanations for the different features. We also generate the SHAP values for each instance. We look for the size
<figure><img src="image_65.png" /><figcaption>Figure 5.7: SHAP values for test input explained in Figure 5.6.</figcaption></figure>

<figure><img src="image_66.png" /><figcaption>Figure 5.8: Heatmaps in columns (b-c) representing the (FI) score, and (d-e) the (FR) computed over the $SR_x$ and $CF_x$ of the samples data from MNIST (column a) in comparison to heatmaps of the SHAP values (column f).</figcaption></figure>

of shortest $SR_x$ explanations ($m$) and select the $m$ important features having the highest SHAP values. A first observation was that finding common variables shared between the explanations of the two approaches per run was systematic. We calculated the fraction: *Number of time there are common variables / Number of total runs* and we obtained 100% for all the datasets used. The second observation is about the number of features shared given the $m$ important SHAP values. The average and maximum
<figure><img src="image_67.png" /><figcaption>Figure 5.9: Average (and maximum) proportion of common important variables between SHAP explanations and those of our ASTERYX approach.</figcaption></figure>

number of input features shared between ASTERYX's explanations and most important SHAP's features is represented in Figure 5.9. The yellow bar corresponds to the average number of most important SHAP values influencing the prediction (having a high score) and presented as an explanation. The green bar corresponds to the average number of common variables between our symbolic explanations ASTERYX and the SHAP explanations. Finally, the orange bar corresponds to the maximum number of variables shared between ASTERYX and SHAP. As observed from the results, we can approximately identify a ratio of 0.5 between the size of the set of common variables and the size of the *m* most important SHAP values.

As for the MNIST dataset, we compared our most important features according to the *FI* score of our approach and those of SHAP and the results on a sample of images coincide in 46% of cases, which is visually confirmed in Figure 5.8. We proceed as follows to compute such kind of correlation coefficient between the different scores proposed and the explanations calculated by SHAP: In a descending order, we consider third of the pixels of the explanations (let *P* be the cardinality of this set) and we compare them with *P* pixels having the highest SHAP values. The correlation coefficient corresponds to the result of the fraction between the size of the intersection set and *P*.

## 5.4 Conclusion

In this chapter, we have presented another type of explanations. Such explanations are numerical feature-based that aim to quantify the contribution of each feature in a prediction. In addition to the generation of two types of symbolic explanations which are *sufficient reasons* and *counterfactuals*, we associate scores reflecting the relevance of the explanations and the features w.r.t to some properties. To the best of our knowledge, our approach is the first that generates different types of symbolic explanations and **fine-**
**grained** score-based ones. Our experimental results show the effectiveness of the proposed approach in providing both symbolic and score-based explanations. Finally, we were able to identify that a large part of the features composing our explanations corresponded to the most influential SHAP values. In next chapter, we will see how feature attribution explanations can be used to explain multi-label predictions and what are the specificities related to such setting.
# Feature-attribution explanations for multi-label classification

In this chapter, we will present the last part that we have explored during this thesis. We shift the attention to multi-label classification where an instance is associated with a non-empty subset of labels and we are interested in defining what a feature attribution explanation represents for such setting. We introduce the problem studied in Section 6.1. We will see in Section 6.2 how we can generalize some feature attribution techniques initially proposed in the literature for mono-label classifiers to the multi-label ones. We describe two desirable criteria to evaluate aggregation of those explanations methods. We also propose a criteria specific to multi-label classification and suggest to use it to infer feature attributions based on relationships between labels. We introduce an alternative to aggregation in Section 6.3 and propose a new attribution method based on symbolic explanations in Section 6.4.

## 6.1 Introduction

A lot of the post-hoc XAI methods have focused on feature-level importance scores for how much a given input feature contributes to a model's output. As stated before, depending on the considered method, a feature attribution may denote sensitivity [SVZ13b], relevance [BBM$^+$15], local influence [RSG16], Shapley values [LL17], filter activations [NHWF21], etc. For multi-label classification where a prediction is a subset of labels, there is only a very simple feature attribution methods based on aggregating feature importance scores of the different predicted labels computed individually.

In this chapter, we are interested in feature attribution for multi-label classification tasks. The goal is to associate to each input feature $X_i$ a score $a_i$ reflecting the influence of $X_i$ on the prediction $y=f(x)$ (or any subset $y'$ of $y$) as illustrated in Figure 6.1.

**Example 44.** In the picture below, the black-box is the multi-label classifier. Input instances are vectors of $n$ feature values. The vectors on the right-hand side show all the feature attributions computed using explanation functions denoted $h(x, y_i)$ for each label. The problem studied is how to find the global feature attributions for a multi-label prediction based on the ones generated for individual labels.
<figure><img src="image_68.png" /><figcaption>Figure 6.1: Illustrative figure of the problem studied</figcaption></figure>

We propose schemes for achieving feature attribution for multi-label classification which are all model-agnostic and which are based on existing feature attribution methods used as oracles.

1. We first point out some deficiencies in attribution methods based on aggregation. To do this, we define three desirable properties such as sensitivity (features actually leading to different predictions should have positive scores), data stability (similar data items predicted equally should lead to similar explanations) and label-explanation correlation (correlated labels should be associated with correlated explanations). We show empirically that some oracles and aggregation operators capture these properties to different extents.

2. The second main contribution of this chapter is a framework based on problem transformation allowing to provide global feature attributions capturing the above properties while using existing attribution methods as an oracle.

3. The third contribution consists in a new attribution method based on symbolic explanations such as sufficient and counterfactual reasons, from which attribution scores are generated.

Examples of the existing feature attribution approaches proposed to explain the multi-label classification such as [SB21, Che21, PGMP19] were previously introduced in Section 4.1 of Chapter 4. In the following, we propose and evaluate schemes for feature attribution specifically designed to explain multi-label predictions in an agnostic way while taking advantage of existing feature attribution methods used as oracles.

## 6.2 Aggregation-based feature attribution

The aim of this section is to compare some aggregation-based attribution methods using existing attribution approaches such as SHAP and LIME considered as oracles employed to generate the set of explanations. In an aggregation-based scheme, the global attribution aggregates feature attributions relative to labels individually into a global attribution for the considered multi-label prediction. This may be useful to get an overall idea of the influence of each feature on the whole (or a subset) predicted labels. Let $h$ denote the attribution oracle used to achieve feature attribution of labels (individually), and let

$$Att(x_i) = Agg_{y_j \in y'}(h(x_i, y_j)), \qquad (6.1)$$
where *Agg* is an aggregation function<sup>43</sup> and *y*′ is the part of the multi-label prediction to explain.

Given that the generated local feature attributions will provide insights into predicting each label $y_j$ individually, then intuitively, one should choose aggregation operators allowing to capture complementary information (contrary to aggregation measures capturing confirmation or consensus as it is the case in ensemble classifiers). In our study, we compare aggregation operators for redundant information on the one side with operators suited for complementary information on the other side.

There are basically two questions when it comes to aggregation: i) *what is the meaning or semantics to give to aggregated scores (for example, is the aggregation of Shapley values for an attribute $X_i$ a Shapley value ?)* and ii) *how to assess relevance of aggregated scores?* Let us first provide three natural properties that we want to capture in a multi-label setting, then, assess in the experimental study to what extent such properties are captured by some common aggregation operators.

## 6.2.1 Three basic properties for feature attribution in multi-label classification

### Sensitivity

This property, also called separability, indicates that if there are two different predictions for two instances of data that differ only in the value of a single feature $X_i$, then the feature $X_i$ must have a positive attribution. Also, if a feature is never used by a model to make a prediction, then the attribution score for that feature should always be zero. To illustrate and motivate the interest of such property, we provide the following example for the case where a change in a feature value alters the prediction and how we expect the importance of the feature to evolve.

**Example 45.** In the figure below, the black-box is a multi-label classifier. Input instances have three features and have similar values except for the variable $X_3$. The model outputs for the instances $x$ and $x'$ two different predictions where the difference lies in the prediction of the label $l_2$. The vectors on the right-hand side correspond to the feature attributions of each instance. The importance of $X_3$ is expected to increase since it represents the only difference between two instances predicted differently.

<figure><img src="image_69.png" /><figcaption>Figure 6.2: Example illustrating the sensitivity property evaluated on the explanations of a multi-label prediction.</figcaption></figure>

In order to evaluate the sensitivity property, the two separability scenarios set out above should be considered empirically. We provide details about how we do it in Section 6.5.1.

<footnote n="43">⁴³In practice, one can use depending on needs *average*, *median*, *max*, *min*, etc.</footnote>
## Data-explanation stability

Data stability, called simply stability in some papers [LPK21], intuitively states that similar data instances predicted equally should have similar explanations. Therefore, small changes in the input data (that do not change the predictions) should result in small changes in the explanations associated with the predictions made on those data. In other words, explanation functions should be insensitive to perturbations in the model inputs, especially if the model output does not change. This aims to capture a kind of continuity, i.e. for data points close to each other in the feature space, we expect their explanations to be close to each other if such data points share the same prediction.

**Example 46.** Similarly to Example 45, the input instances have three features and have similar values except for the variable $X_1$. The model outputs the same prediction for the two instances x and $x'$. The vectors on the right-hand side correspond to the feature attributions of each instance. The importance of $X_1$ is expected to remain the same or undergo minimal changes (low impact) as shown below.

<figure><img src="image_70.png" /><figcaption>Figure 6.3: Example illustrating the data-explanation stability evaluated on the explanations of a multi-label prediction.</figcaption></figure>

Stability evaluation can be achieved similar to the way we assess sensitivity. In the current work, we assess the stability property of a feature attribution function $h$ as its ability to generate feature attributions close to each other for an instance $x$ and a perturbed instance $\acute{x}$ which have the same prediction (namely $f(\acute{x})=f(x)$). We give more insights on how we assess it empirically in Section 6.5.1.

## Label-explanation correlation

This property refers to the consistency of the explanations provided for pairs of labels, especially in case the labels are strongly correlated. Intuitively, if two labels (predicted by the model to be explained), are strongly correlated then their explanations should also be strongly correlated. In an extreme case, if two labels are equivalent (predicted with the same value regardless of the input data), then the explanations must also be strongly correlated. Similarly, if two labels are predicted independently of each other then their explanations should also be independent.

To illustrate this property, suppose a multi-label classification problem consisting in making hypotheses on possible diseases (representing the labels) from a certain number of observed symptoms (representing the features). If two diseases are often always predicted simultaneously, then their explanations (which can be assimilated to the associated symptoms) must be correlated, otherwise the two diseases will not be predicted simultaneously.
While sensitivity and stability properties also apply for multi-class classification, the third property is specific to multi-label classification and it is the first time it is proposed to our knowledge. The correlation between pairs of labels or between pairs of attribution vectors can directly be assessed by commonly used statistical correlation measures such as mutual information, Pearson coefficient, etc.

## 6.2.2 Aggregation operators

In our case, aggregation consists of the operation of merging information from oracles in order to summarize or obtain global information. More precisely, the input to our aggregation operation is a set of $k$ attribution vectors $v_j=(a^j_1, a^j_2, ..., a^j_n)$ such that $v_j=h(x, y_j)$ is the attribution vector obtained by the oracle given the instance $x$ for the label $y_j$. The output is a vector of scores $v_{agg}=(a_1, a_2, ..., a_n)$ where $agg$ is a user defined aggregation operator. Note that the vectors $v_j$ share the same scale and are provided by the same oracle $h$.

**Example 47.** Assume we have a data instance of interest $x=(0, 1, 0, 1, 0)$ to be explained by a feature attribution function $h$ and that its prediction by a model $f$ is $(1, 0, 0)$ (i.e. $f(0, 1, 0, 1, 0)=(1, 0, 0)$). $v_j=h(x, y_j)$ is the attribution vector obtained by the oracle on the instance $x$ for the label $y_j$. The generated feature attribution explanations for each class $l_{j|j=1,2,3}$ of the prediction $y = (1, 0, 0)$ are represented in Table 6.1.

<table><caption>Table 6.1: Feature attribution explanations of $x$ per label.</caption><thead><tr><th></th><th>class</th><th>Att<sub>1</sub></th><th>Att<sub>2</sub></th><th>Att<sub>3</sub></th><th>Att<sub>4</sub></th><th>Att<sub>5</sub></th></tr></thead><tbody><tr><td>v<sub>1</sub></td><td>l<sub>1</sub> = 1</td><td>0.093</td><td>0.55</td><td>0.27</td><td>0.043</td><td>0.044</td></tr><tr><td>v<sub>2</sub></td><td>l<sub>2</sub> = 0</td><td>-0.37</td><td>0.12</td><td>-0.48</td><td>0.15</td><td>0.58</td></tr><tr><td>v<sub>3</sub></td><td>l<sub>3</sub> = 0</td><td>-0.078</td><td>0.46</td><td>-0.75</td><td>0.196</td><td>0.172</td></tr></tbody></table>

The vectors of feature attribution explanation for the prediction of $x$ obtained using the aggregation operators average, maximum and minimum are presented as follows:

<table><caption>Table 6.2: Feature attribution explanation of $f(x) = (1, 0, 0)$.</caption><thead><tr><th></th><th>Att<sub>1</sub></th><th>Att<sub>2</sub></th><th>Att<sub>3</sub></th><th>Att<sub>4</sub></th><th>Att<sub>5</sub></th></tr></thead><tbody><tr><td>v<sub>mean</sub></td><td>-0.118</td><td>0.376</td><td>-0.32</td><td>0.129</td><td>0.265</td></tr><tr><td>v<sub>max</sub></td><td>0.093</td><td>0.55</td><td>0.27</td><td>0.196</td><td>0.58</td></tr><tr><td>v<sub>min</sub></td><td>-0.37</td><td>0.12</td><td>-0.75</td><td>0.043</td><td>0.044</td></tr></tbody></table>

From an aggregation point of view, it is natural that aggregation has some natural properties like commutativity, fairness and insensitivity to vacuous information. From a feature attribution point of view, an aggregation should satisfy some intuitive properties such as unanimity (resp. majority) (e.g. if a feature $X_i$ is considered influential (resp. not influential) for each (most of) label, then it should be considered influential (resp. non influential) by the feature attribution obtained after aggregation). Note that our objective is not to study and analyse aggregation operators for feature attribution purposes. Rather, we will focus on properties that are important from a feature attribution point of view and to what extent aggregation preserves, improves or degrades these properties. It is worth noticing that aggregation-based feature attribution needs $k$ calls to a feature attribution oracle. The following provides a solution based on reusing and inferring feature attributions relative to some labels based on the feature attributions of other correlated labels.
Feature attribution based on aggregation is intuitive and simple to implement but suffers from some drawbacks, in particular, the number of calls to the oracle. Indeed, if the multi-label classification problem includes $k$ labels, it will be necessary to make $k$ calls to the oracle $h$, which can be very computationally expensive, especially if we use an oracle that is not computationally efficient like SHAP in its standard version$^{44}$. One way to improve this is to exploit the following fact: if the oracle used captures the property of *label-explanation correlation* for two labels $y_i$ and $y_j$ then this correlation can potentially make it possible to infer a feature attribution $h(x, y_i)$ from feature attribution $h(x, y_j)$. This is all the more true as this correlation is very strong. The idea is to predict $h(x, y_j)$ from $h(x, y_i)$ by exploiting correlations (especially linear ones) that may exist between predictions of $y_i$ and $y_j$.

The following section provides an alternative scheme to aggregation-based feature attributions that allows to only make one call to a feature attribution oracle.

## 6.3 Multi-label feature attribution through problem transformation

In this section, we provide a setting allowing to rely on existing feature attribution methods considered as oracles to ensure feature attribution without aggregating attributions relative to labels individually. Recall that in multi-label classification tasks, training examples are couples of vectors $(x, y)$ where $x \in X$ is the data input, and $y \in \{0, 1\}^k$ is the corresponding output label vector. In order to explain the prediction $f(x)=y$ of a multi-label classifier $f$, we associate a binary classifier $f'$ with $f$ as follows:

$$f'(x) = \begin{cases} 1 & \text{if } f(x)=y \\ 0 & \text{otherwise} \end{cases} \qquad (6.2)$$

Then, in order to achieve feature attribution for a data instance $x$, we can simply rely on $h(x, f')$. Namely, we achieve feature attribution using the oracle $h$ on a binary classifier $f'$. For instance, if $h$ performs feature attribution for $f(x)$ using a neighborhood around $x$ then in the transformation-based scheme, we will use $h$ to attribute features for $f'$ around $x$.

**Example 48.** (Example 47 continued) In this example, we transform a multi-label problem into a single-label one according to Equation 6.2. Assume that the neighborhood of an instance $x=(0, 1, 0, 1, 0)$ to be explained by a feature attribution function $h$ is given in Table 6.3 and assume that the prediction is $f(0, 1, 0, 1, 0)=(1, 0, 0)$.

<table><caption>Table 6.3: From multi-label predictions into mono-label ones.</caption><thead><tr><th>X<sub>1</sub></th><th>X<sub>2</sub></th><th>X<sub>3</sub></th><th>X<sub>4</sub></th><th>X<sub>5</sub></th><th>f(x)</th><th>f'(x)</th></tr></thead><tbody><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td></tr></tbody></table>

Explaining $f(x) = (1, 0, 0)$ amounts to explaining $f'(x) = 1$ by the means of $h(x, f')$ as shown in Table 6.4.

<footnote>$^{44}$Computationally efficient versions are KernelSHAP or TreeSHAP.</footnote>
<table><caption>Table 6.4: Feature attribution explanation generated for the transformed problem $f'(x)$.</caption><thead><tr><th></th><th>Att<sub>1</sub></th><th>Att<sub>2</sub></th><th>Att<sub>3</sub></th><th>Att<sub>4</sub></th><th>Att<sub>5</sub></th></tr></thead><tbody><tr><th>v<sub>f'</sub></th><td>-0.13</td><td>0.76</td><td>0.45</td><td>-0.29</td><td>0.21</td></tr></tbody></table>

Hence, instead of explaining $f(x)$ with $h$, our transformation-based scheme explains $f'(x)$ with $h$. This transformation approach has several advantages:

* It can be used with any feature attribution oracle $h$ such as SHAP and LIME.

* The semantics of scores is inherited from the one of the used oracle. For instance, using this scheme, it is clear that the numerical score associated to a feature while making a prediction is a Shapley value in case the used oracle is SHAP. This is not necessarily the case when aggregating feature attributions.

* It requires only one single call to an oracle $h$ for the feature attribution while aggregation-based scheme requires $k$ calls to an oracle.

So far, we have proposed a first scheme based on aggregation and a second one based on problem transformation. In the next section, we propose to achieve feature attribution for multi-label classification by first transforming the problem as in the second scheme and then use an oracle providing symbolic explanations.

# 6.4 Multi-label feature attribution through symbolic explanations

In addition to popular attribution methods like SHAP and LIME, we propose to use an alternative oracle that provides different types of symbolic explanations. More precisely, in this scheme, we first transform the problem, then generate symbolic explanations (in the form of sufficient reasons and counterfactuals) and finally derive feature attributions from the computed symbolic explanations. Given that problem transformation is presented in the previous section, let us directly present the remaining steps.

## 6.4.1 Generating symbolic explanations

In order to provide symbolic explanations, we rely on our generic and agnostic approach ASTERYX that allows to generate two main forms of symbolic explanations that are sufficient reasons and counterfactuals along with score-based explanations (cf Chapter 3 and Chapter 5). To recall, the approach is based on encoding a classifier into an equivalent symbolic representation and using a surrogate approach, ASTERYX relies on SAT-based solvers such as [GIL18] and [IMM18] to enumerate the two types of symbolic explanations.

## 6.4.2 From symbolic explanations to feature attributions

Once the symbolic explanations are enumerated, they are used to calculate scores that will be associated with the variables forming these explanations. These scores represent the feature attributions that are derived from the initial set of symbolic explanations. We recall that the scores are calculated with respect to certain properties (previously defined in Chapter 5) that we briefly recall in the following:

* **Feature involvement (FI)**: This property is intended to reflect the extent of involvement of a feature within the set of explanations.
*   **Feature generality ($\mathcal{FG}$)**: This property captures at what extent a feature is frequently involved in explaining instances in the vicinity of the sample to explain.

*   **Feature responsibility ($\mathcal{FR}$)**: This property is intended to reflect the responsibility or contribution of a feature $X_i$ within the set of symbolic explanations of $x$.

## 6.5 Experimental study

This section presents the empirical study carried out to evaluate the three schemes provided for achieving feature attribution for multi-label tasks.

<table><caption>Table 6.5: Properties of the datasets used.</caption><thead><tr><th>Dataset</th><th>#instances</th><th>#classes</th><th>#features</th><th>data type</th><th>density</th></tr></thead><tbody><tr><td>Augmented MNIST</td><td>70000</td><td>13</td><td>784</td><td>Images</td><td>0.184</td></tr><tr><td>Yelp Review Analysis</td><td>10806</td><td>5</td><td>671</td><td>Textual</td><td>0.328</td></tr><tr><td>IMDB Movie Genre Prediction</td><td>65500</td><td>24</td><td>30</td><td>Textual</td><td>0.07</td></tr><tr><td>Foodtruck</td><td>408</td><td>12</td><td>102</td><td>Categorical / Numerical</td><td>0.191</td></tr><tr><td>Patient Characteristics Survey (NYS15)</td><td>105099</td><td>5</td><td>63</td><td>Textual / Numerical</td><td>0.41</td></tr></tbody></table>

We considered a selection of multi-label datasets known from the literature and publicly available and can be found on Kaggle$^{45}$ or UCI$^{46}$. The details of the datasets, such as the number of examples, the type of attributes, the number of classes and their label density are given in Table 6.5. The initial version of the MNIST dataset is composed of 10 classes corresponding to digits from 0 to 9. We extended that version by adding the labels "Odd", "Even" and "Prime" and called it "Augmented MNIST". Each input image is associated to a vector of thirteen labels$^{47}$. Experiments presented in this section have been carried out on a cluster of computers equipped with quadcore bi-processors Intel Xeon E5-2643 3 (3.30 GHz) and 64 GB of memory running under the CentOS Stream 8.3 and on Intel Core i7-7700 (3.60GHz ×8) processors with 32Gb memory on Linux OS.

Two popular multi-class feature attribution methods have been used within the experiments as oracles: the widely-used SHAP [LL17] and LIME [RSG16]. As for symbolic explainer, we used our approach ASTERYX (cf Chapter 3 and 5). We used the Binary relevance (BR) multi-label classifiers with Logistic Regression or Decision Tree as base classifiers from the Scikit-multilearn library. Such BR models are trained on the different datasets and their predictions are being explained. We observed during the experiments that as the label-density decreases, the prediction task becomes harder. Given the neighborhood of a sample test $x$, very few samples are predicted as the non-majority class, which causes learning problems where the trained model recognizes systematically the majority class. To address this problem, we operate an under sampling on the neighborhood $V_x$ where we randomly pick samples from majority class equal to the number of samples in the minority class so that both the classes will have approximately the same number of samples. All the multi-class feature attribution oracles used in our

<footnote>$^{45}$Kaggle dataset: (https://www.kaggle.com/).</footnote>

<footnote>$^{46}$UCI dataset: (http://archive.ics.uci.edu/ml/).</footnote>

<footnote>$^{47}$The labels having an index $i \in [0, 9]$ indicate whether the input image $x$ is recognized as an $i$-digit while the labels having an index $i \in [10, 12]$ indicate respectively whether the represented digit is being classified as an "odd", "even" or a "prime" numbers.</footnote>
experiments are local methods relying on the neighborhood of the instance to explain to generate explanations.

In order to provide an empirical evaluation comparing the three schemes proposed in this paper, let us first present the methodology and means used for each scheme, then give the empirical results of the three schemes.

### 6.5.1 Evaluating aggregation-based feature attribution scheme

In the following, we assess the gain or loss in terms of sensitivity and stability due to the aggregation operation.

**Sensitivity** In our work, the sensitivity property of a feature attribution function *h* is assessed quantitatively as follows:

Let *f* be a classifier, *h* be a feature attribution function, *x* be a data point and assume a set of perturbed instances $\rho(x) = \{\acute{x} : \text{dist}(x, \acute{x}) \le r \text{ and } f(\acute{x}) \ne f(x)\}$, we assess the sensitivity property at *x* as follows:

$$ \eta_{SNS}(h, x) = \underset{\acute{x} \in \rho(x)}{\text{AVG}}(\text{dist}(h(x, f), h(\acute{x}, f))) \quad (6.3) $$

where *dist* denotes a distance (or dissimilarity) function between *x* and a perturbed instance $\acute{x}$. One can sample the data and have a representative assessment of the sensitivity property. According to Equation 6.3, the larger the output, the better is *h* in terms of sensitivity.

Since our objective is to assess the gain or loss in terms of sensitivity due to the aggregation operation, we compare on average the sensitivity of individual label feature attributions (before aggregation) w.r.t the sensitivity of resulting global feature attribution (after aggregation). The results are presented in Table 6.6. Several findings are possible from Table 6.6. In particular, we notice on the different datasets that most of the time, we obtain the best (here highest) values (highlighted in red) of sensitivity at the level of individual label feature attributions (before aggregation), except for the MNIST dataset.

**Data-explanation stability** For any feature attribution function *h*, we can measure its stability following Definition 6.4. Given a classifier *f*, a feature attribution method *h*, a data point *x* and a set of perturbed instances $\rho(x)$ defined as $\rho(x) = \{ \acute{x} : \text{dist}(x, \acute{x}) \le r \text{ and } f(\acute{x}) = f(x) \}$, we assess the stability

<table><caption>Table 6.6: Evaluation of aggregation-based feature attribution wrt the sensitivity property.</caption><thead><tr><th></th><th>Oracle</th><th>Before AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="2">YELP</td><td>SHAP</td><td>3.143</td><td>3.0</td><td>3.44</td><td>3.54</td><td>2.69</td><td>3.16</td></tr><tr><td>LIME</td><td>2.2</td><td>0.96</td><td>2.31</td><td>0.97</td><td>2.06</td><td>0.92</td></tr><tr><td rowspan="2">MNIST</td><td>SHAP</td><td>0.37</td><td>1.19</td><td>0.38</td><td>1.39</td><td>0.361</td><td>1.25</td></tr><tr><td>LIME</td><td>0.294</td><td>0.44</td><td>0.3</td><td>0.46</td><td>0.291</td><td>0.40</td></tr><tr><td rowspan="2">FOOD<br>TRUCK</td><td>SHAP</td><td>2.09</td><td>1.1</td><td>2.14</td><td>1.48</td><td>2.03</td><td>1.24</td></tr><tr><td>LIME</td><td>0.92</td><td>0.37</td><td>0.94</td><td>0.38</td><td>0.9</td><td>0.34</td></tr><tr><td rowspan="2">NYS15</td><td>SHAP</td><td>1.29</td><td>1.1</td><td>1.54</td><td>1.483</td><td>1.34</td><td>1.15</td></tr><tr><td>LIME</td><td>0.76</td><td>0.36</td><td>0.85</td><td>0.37</td><td>0.66</td><td>0.33</td></tr><tr><td rowspan="2">IMDB</td><td>SHAP</td><td>0.43</td><td>1.0</td><td>0.44</td><td>1.17</td><td>0.42</td><td>1.03</td></tr><tr><td>LIME</td><td>0.228</td><td>0.373</td><td>0.232</td><td>0.38</td><td>0.224</td><td>0.35</td></tr></tbody></table>
<table><caption>Table 6.7: Evaluation of aggregation-based feature attribution wrt the data-explanation stability property.</caption><thead><tr><th></th><th>Oracle</th><th>Before AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="2">YELP</td><td>SHAP</td><td><u>0.92</u></td><td>1.75</td><td>1.4</td><td>3.05</td><td>0.7</td><td>2.65</td></tr><tr><td>LIME</td><td>2.11</td><td><u>0.68</u></td><td>2.29</td><td>0.7</td><td>1.79</td><td>0.54</td></tr><tr><td rowspan="2">MNIST</td><td>SHAP</td><td><u>0.39</u></td><td>1.73</td><td>0.41</td><td>1.979</td><td>0.36</td><td>1.19</td></tr><tr><td>LIME</td><td><u>0.24</u></td><td>0.485</td><td>0.25</td><td>0.498</td><td>0.22</td><td>0.401</td></tr><tr><td rowspan="2">FOOD<br>TRUCK</td><td>SHAP</td><td><u>0.75</u></td><td>1.36</td><td>0.82</td><td>1.48</td><td>0.66</td><td>1.08</td></tr><tr><td>LIME</td><td>0.91</td><td><u>0.389</u></td><td>0.94</td><td>0.396</td><td>0.88</td><td>0.347</td></tr><tr><td rowspan="2">NYS15</td><td>SHAP</td><td><u>0.82</u></td><td>1.26</td><td>0.83</td><td>1.37</td><td>0.80</td><td>1.03</td></tr><tr><td>LIME</td><td><u>0.22</u></td><td>0.33</td><td>0.24</td><td>0.345</td><td>0.2</td><td>0.3</td></tr><tr><td rowspan="2">IMDB</td><td>SHAP</td><td><u>0.48</u></td><td>1.52</td><td>0.49</td><td>1.73</td><td>0.4</td><td>1.07</td></tr><tr><td>LIME</td><td><u>0.16</u></td><td>0.41</td><td>0.169</td><td>0.422</td><td>0.15</td><td>0.342</td></tr></tbody></table>

property between $h(x, f)$ and attributions of close instances $\in \rho(x)$ as follows :

$$ \eta_{STB}(h, x) = \underset{\acute{x} \in \rho(x)}{\mathrm{AVG}}(\mathrm{dist}(h(x, f), h(\acute{x}, f))), \qquad (6.4) $$

where *dist* denotes a distance (or dissimilarity) function between *x* and a perturbed instance *x̂*. Equation 6.4 quantitatively assesses the stability property at a data instance *x*. One can sample the data and have a representative assessment. According to our way of evaluating stability, the lower the result, the better the feature attribution in terms of stability.

For the data-explanation stability property, we compare on average the data-explanation stability of individual label feature attributions (before aggregation) w.r.t the data-explanation stability of resulting global feature attribution (after aggregation). The results are presented in Table 6.7.

We obtain the best (here smallest) values (highlighted in green) at the level of the individual label feature attributions, meaning that the property of stability is better preserved before aggregation and merging the individual label feature attributions degrades it. Regarding the best aggregation operator, it can be seen that max aggregation selects the highest values and thus benefits the sensitivity to the detriment of stability. Conversely, for stability, min aggregation is more suitable because it ensures high stability but this is to the detriment of sensitivity. We also observe that the SHAP method seems better than LIME with a higher average value for sensitivity and a lower average value for stability (underlined values per dataset).

In addition to sensitivity and stability, we assess label-explanation correlation in order to choose a feature attribution oracle. In this experiment, we assessed this property by the mean of the Pearson correlation coefficient and Mutual Information (MI). Note that the main difference is that the Pearson's correlation coefficient aims to capture linear relationships between variables while mutual information measures general dependence. Given the base classifiers of a multi-label classifier, we measure the correlation of predictions for each pair of labels and their respective SHAP and LIME explanations.

The results on the different datasets are presented in the Figures 6.4 and 6.5, where the *X* axis groups the pairs of labels sharing the same *MI* or Pearson's *R* interval. For example, the last bin will represent all the pairs of labels $y_i$ and $y_j$ having *MI*($y_i$, $y_j$) or Pearson's *R* belonging to the interval [0.9, 1]. On the *Y* axis, the mean of *MI* or Pearson's *R* of the scores corresponding to the instances predicted with the pair ($y_i$, $y_j$) is represented. We can see that both SHAP and LIME manage to capture strong label-explanation correlation when the labels are strongly correlated. However, the results diverge when it comes to weakly correlated labels where we observe that the mean values of the *MI* and Pearson's *R* metrics are still high for weakly correlated labels, indicating strong correlation between the explanations. Indeed, for the IMDB and the augmented MNIST, we notice that LIME, closely followed by SHAP, tends to capture
<figure><img src="image_71.png" /><figcaption>Figure 6.4: Evaluating label-explanation correlation using the mutual information (MI) coefficient.</figcaption></figure>

<figure><img src="image_72.png" /><figcaption>Figure 6.5: Evaluating label-explanation correlation using the Pearson's R coefficient.</figcaption></figure>

strong correlation regardless of the relationship that exists between the labels. This may be due to the assessment in our experiments of this property on restricted neighborhoods (therefore with very similar instances, possibly similar attributions due to the stability property).

## 6.5.2 Evaluating problem transformation-based feature attribution scheme

We keep up with the same multi-label classifiers and the same oracles (SHAP and LIME) to evaluate multi-label feature attribution through problem transformation. Table 6.8 gives the results of the evaluation wrt the sensitivity and stability properties. The main finding is that the problem transformation approach ensures the smallest values for the stability property over the different datasets. Such results are expected since the approach by definition reduces the task of explaining a multi-label classifiers to explaining a single classifier, which makes it possible to minimize the discrepancies that there could be between the explanations of similar instances.

## 6.5.3 Evaluating symbolic explanation-based feature attribution scheme

The objective here is to evaluate our three basic properties using a symbolic explanation-based oracle. The same multi-label models used for the evaluation of aggregation-based attribution scheme are used in this part.
<table><caption>Table 6.8: Evaluation of multi-label feature attribution through problem transformation.</caption><thead><tr><th>Property</th><th>Dataset</th><th>SHAP</th><th>LIME</th></tr></thead><tbody><tr><td rowspan="4">Sensitivity</td><td>YELP</td><td>0.28</td><td>0.75</td></tr><tr><td>AUG. MNIST</td><td>0.18</td><td>0.15</td></tr><tr><td>FOODTRUCK</td><td>0.29</td><td>0.5</td></tr><tr><td>NYS15</td><td>0.25</td><td>0.75</td></tr><tr><td rowspan="4">Data-explanation stability</td><td>YELP</td><td>0.05</td><td>0.4</td></tr><tr><td>AUG. MNIST</td><td>0.38</td><td>0.09</td></tr><tr><td>FOODTRUCK</td><td>0.6</td><td>0.33</td></tr><tr><td>NYS15</td><td>0.05</td><td>0.4</td></tr></tbody></table>

The feature attribution oracles used are: Feature Involvement (FI), Feature Responsibility (FR) and Feature Generality (FG) from ASTERYX.

<table><caption>Table 6.9: Evaluation of multi-label feature attribution through aggregation by assessing sensitivity for counterfactuals (CF).</caption><thead><tr><th></th><th></th><th>Before AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="3">YELP</td><td>FR<sub>CF</sub></td><td>2.51</td><td>2.43</td><td>2.86</td><td>3.15</td><td>2.18</td><td>2.02</td></tr><tr><td>FG<sub>CF</sub></td><td>1.61</td><td>1.41</td><td>1.82</td><td>1.87</td><td>1.41</td><td>1.11</td></tr><tr><td>FI<sub>CF</sub></td><td>1.26</td><td>1.05</td><td>1.41</td><td>1.46</td><td>1.26</td><td>0.78</td></tr><tr><td rowspan="3">MNIST</td><td>FR<sub>CF</sub></td><td>1.77</td><td>2.49</td><td>1.8</td><td>2.83</td><td>1.75</td><td>2.29</td></tr><tr><td>FG<sub>CF</sub></td><td>1.7</td><td>1.65</td><td>1.74</td><td>1.9</td><td>1.66</td><td>1.49</td></tr><tr><td>FI<sub>CF</sub></td><td>1.53</td><td>1.23</td><td>1.56</td><td>1.46</td><td>1.5</td><td>1.09</td></tr><tr><td rowspan="3">FOOD<br>TRUCK</td><td>FR<sub>CF</sub></td><td>2.05</td><td>1.71</td><td>2.13</td><td>2.37</td><td>1.98</td><td>1.46</td></tr><tr><td>FG<sub>CF</sub></td><td>1.77</td><td>1.41</td><td>1.82</td><td>2.02</td><td>1.71</td><td>1.14</td></tr><tr><td>FI<sub>CF</sub></td><td>1.48</td><td>1.15</td><td>1.51</td><td>1.75</td><td>1.44</td><td>0.9</td></tr><tr><td rowspan="3">NYS15</td><td>FR<sub>CF</sub></td><td>2.22</td><td>1.71</td><td>2.45</td><td>2.33</td><td>1.97</td><td>1.48</td></tr><tr><td>FG<sub>CF</sub></td><td>1.8</td><td>1.44</td><td>1.88</td><td>2.0</td><td>1.71</td><td>1.18</td></tr><tr><td>FI<sub>CF</sub></td><td>1.39</td><td>1.17</td><td>1.45</td><td>1.71</td><td>1.32</td><td>0.93</td></tr><tr><td rowspan="3">IMDB</td><td>FR<sub>CF</sub></td><td>1.29</td><td>2.2</td><td>1.33</td><td>2.49</td><td>1.24</td><td>2.05</td></tr><tr><td>FG<sub>CF</sub></td><td>1.51</td><td>1.62</td><td>1.55</td><td>1.85</td><td>1.47</td><td>1.5</td></tr><tr><td>FI<sub>CF</sub></td><td>1.33</td><td>1.28</td><td>1.34</td><td>1.5</td><td>1.32</td><td>1.15</td></tr></tbody></table>

In Tables 6.9 and 6.10, we notice that we mainly obtain a higher sensitivity at the level of the global feature attribution obtained after the aggregation for the sufficient reasons, while the opposite is observed for the explanations counterfactuals, where we find a greater sensitivity before aggregation. In Table 6.10, we notice a strong stability at the level of the explanations before the aggregation for the SRs. For CFs, the results are more mixed with a slight advantage for aggregation (cf Table 6.9).

In terms of the oracle, none of the three oracles stand out in a striking way, with a slight advantage for the *FR* for sensitivity in CF explanations and for the *FI* for SR explanations which seem to achieve better scores for the Sensitivity property (underlined in Tables 6.9 and 6.10) i.e. tend to be more sensitive to
<table><caption>Table 6.10: Evaluation of multi-label feature attribution through aggregation by assessing sensitivity for sufficient reasons explanations (SR).</caption><thead><tr><th></th><th></th><th>Before AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>SNS</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="3">YELP</td><td>FR<sub>SR</sub></td><td>3.27</td><td>3.34</td><td>3.51</td><td>4.08</td><td>3.04</td><td>2.82</td></tr><tr><td>FG<sub>SR</sub></td><td>3.6</td><td></td><td>3.8</td><td>4.47</td><td>3.41</td><td>2.96</td></tr><tr><td>FI<sub>SR</sub></td><td>3.81</td><td></td><td>3.99</td><td>4.62</td><td>3.63</td><td>3.1</td></tr><tr><td rowspan="3">MNIST</td><td>FR<sub>SR</sub></td><td>1.4</td><td>2.23</td><td>1.43</td><td>2.65</td><td>1.38</td><td>1.94</td></tr><tr><td>FG<sub>SR</sub></td><td>2.69</td><td>2.97</td><td>2.78</td><td>3.55</td><td>2.5</td><td>2.6</td></tr><tr><td>FI<sub>SR</sub></td><td>2.56</td><td>3.09</td><td>2.63</td><td>3.67</td><td>2.5</td><td>2.71</td></tr><tr><td rowspan="3">FOOD<br>TRUCK</td><td>FR<sub>SR</sub></td><td>2.627</td><td>1.8</td><td>2.7</td><td>2.66</td><td>2.56</td><td>1.4</td></tr><tr><td>FG<sub>SR</sub></td><td>3.08</td><td>2.32</td><td>3.12</td><td>3.31</td><td>3.03</td><td>1.85</td></tr><tr><td>FI<sub>SR</sub></td><td>3.09</td><td>2.31</td><td>3.15</td><td>3.24</td><td>3.05</td><td>1.87</td></tr><tr><td rowspan="3">NYS15</td><td>FR<sub>SR</sub></td><td>2.51</td><td>1.88</td><td>2.75</td><td>2.7</td><td>2.27</td><td>1.49</td></tr><tr><td>FG<sub>SR</sub></td><td>2.73</td><td>2.32</td><td>2.36</td><td>3.29</td><td>2.59</td><td>1.91</td></tr><tr><td>FI<sub>SR</sub></td><td>2.64</td><td>2.34</td><td>2.82</td><td>3.22</td><td>2.46</td><td>1.92</td></tr><tr><td rowspan="3">IMDB</td><td>FR<sub>SR</sub></td><td>1.97</td><td>2.21</td><td>2.01</td><td>2.58</td><td>1.94</td><td>1.97</td></tr><tr><td>FG<sub>SR</sub></td><td>2.07</td><td>2.72</td><td>2.09</td><td>3.2</td><td>2.04</td><td>2.47</td></tr><tr><td>FI<sub>SR</sub></td><td>1.92</td><td>2.77</td><td>1.95</td><td>3.23</td><td>1.89</td><td>2.52</td></tr></tbody></table>

perturbations of data causing a change in prediction. With regard to Data-explanation stability, the *FR* stands out with the lowest scores (underlined in Tables 6.12 and 6.11) reflecting a similarity in the feature attributions attributed to instances that have undergone little change that does not impact their prediction. For the choice of aggregation functions, the same analysis made at the level of aggregation-based feature attribution applies to symbolic-based feature attribution oracles (max aggregation for sensitivity and min aggregation for Data-explanation stability)
Chapter 6. Feature-attribution explanations for multi-label classification

<table><caption>Table 6.11: Evaluation of multi-label feature attribution through aggregation by assessing data-explanation stability for sufficient reasons explanations (SR).</caption><thead><tr><th></th><th></th><th>Before AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="3">YELP</td><td>FR<sub>SR</sub></td><td>2.58</td><td><u>1.95</u></td><td>2.99</td><td>3.93</td><td>2.25</td><td>1.03</td></tr><tr><td>FG<sub>SR</sub></td><td>3.66</td><td><u>2.67</u></td><td>4.008</td><td>5.45</td><td>3.34</td><td>1.39</td></tr><tr><td>FI<sub>SR</sub></td><td>3.75</td><td><u>2.76</u></td><td>4.08</td><td>5.61</td><td>3.44</td><td>1.45</td></tr><tr><td rowspan="3">MNIST</td><td>FR<sub>SR</sub></td><td><u>1.02</u></td><td>1.95</td><td>1.11</td><td>3.93</td><td>0.94</td><td>1.s03</td></tr><tr><td>FG<sub>SR</sub></td><td>2.26</td><td><u>2.67</u></td><td>2.43</td><td>5.45</td><td>2.105</td><td>1.39</td></tr><tr><td>FI<sub>SR</sub></td><td><u>2.01</u></td><td>2.76</td><td>2.17</td><td>5.61</td><td>1.85</td><td>1.45</td></tr><tr><td rowspan="3">FOOD<br>TRUCK</td><td>FR<sub>SR</sub></td><td>2.11</td><td><u>1.85</u></td><td>2.17</td><td>2.47</td><td>2.04</td><td>1.55</td></tr><tr><td>FG<sub>SR</sub></td><td>3.31</td><td><u>2.59</u></td><td>2.954</td><td>3.48</td><td>2.84</td><td>2.19</td></tr><tr><td>FI<sub>SR</sub></td><td>3.34</td><td><u>2.62</u></td><td>2.96</td><td>3.53</td><td>2.79</td><td>2.2</td></tr><tr><td rowspan="3">NYS15</td><td>FR<sub>SR</sub></td><td><u>0.46</u></td><td>1.68</td><td>0.48</td><td>2.2</td><td>0.4</td><td>1.43</td></tr><tr><td>FG<sub>SR</sub></td><td><u>1.27</u></td><td>2.44</td><td>1.64</td><td>3.17</td><td>1.1</td><td>2.1</td></tr><tr><td>FI<sub>SR</sub></td><td><u>1.08</u></td><td>2.42</td><td>1.42</td><td>3.17</td><td>0.97</td><td>2.07</td></tr><tr><td rowspan="3">IMDB</td><td>FR<sub>SR</sub></td><td>2.72</td><td><u>1.82</u></td><td>2.76</td><td>2.84</td><td>2.1</td><td>1.34</td></tr><tr><td>FG<sub>SR</sub></td><td>2.70</td><td><u>2.53</u></td><td>2.91</td><td>3.97</td><td>2.4</td><td>1.84</td></tr><tr><td>FI<sub>SR</sub></td><td>2.81</td><td><u>2.52</u></td><td>2.92</td><td>4.01</td><td>2.1</td><td>1.83</td></tr></tbody></table>

<table><caption>Table 6.12: Evaluation of multi-label feature attribution through aggregation by assessing data-explanation stability for counterfactuals (CF).</caption><thead><tr><th></th><th></th><th>Before AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After AVG<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MAX<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>Before MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th><th>After MIN<br>(η<sub>STB</sub>(f<sub>i</sub>, x))</th></tr></thead><tbody><tr><td rowspan="3">YELP</td><td>FR<sub>CF</sub></td><td>0.8</td><td>1.39</td><td>1.19</td><td>2.88</td><td>0.62</td><td>0.82</td></tr><tr><td>FG<sub>CF</sub></td><td><u>0.48</u></td><td>0.96</td><td>0.72</td><td>2.4</td><td>0.37</td><td>0.43</td></tr><tr><td>FI<sub>CF</sub></td><td>1.23</td><td><u>1.03</u></td><td>1.47</td><td>2.75</td><td>1.005</td><td>0.39</td></tr><tr><td rowspan="3">MNIST</td><td>FR<sub>CF</sub></td><td><u>0.41</u></td><td>1.39</td><td>0.51</td><td>2.88</td><td>0.32</td><td>0.82</td></tr><tr><td>FG<sub>CF</sub></td><td><u>0.49</u></td><td>0.96</td><td>0.61</td><td>2.4</td><td>0.35</td><td>0.43</td></tr><tr><td>FI<sub>CF</sub></td><td>1.03</td><td>1.03</td><td>2.75</td><td>2.12</td><td>0.396</td><td>0.619</td></tr><tr><td rowspan="3">FOOD<br>TRUCK</td><td>FR<sub>CF</sub></td><td><u>0.84</u></td><td>1.04</td><td>0.9</td><td>1.5</td><td>0.78</td><td>0.86</td></tr><tr><td>FG<sub>CF</sub></td><td><u>0.69</u></td><td>0.89</td><td>0.79</td><td>1.34</td><td>0.62</td><td>0.72</td></tr><tr><td>FI<sub>CF</sub></td><td>1.31</td><td>1.14</td><td>1.37</td><td>1.69</td><td>1.24</td><td>0.92</td></tr><tr><td rowspan="3">NYS15</td><td>FR<sub>CF</sub></td><td><u>0.38</u></td><td>0.94</td><td>0.89</td><td>1.325</td><td>0.4</td><td>0.79</td></tr><tr><td>FG<sub>CF</sub></td><td><u>0.69</u></td><td>0.88</td><td>0.78</td><td>1.26</td><td>0.62</td><td>0.74</td></tr><tr><td>FI<sub>CF</sub></td><td>0.4</td><td>1.14</td><td>1.03</td><td>1.26</td><td>0.2</td><td>0.74</td></tr><tr><td rowspan="3">IMDB</td><td>FR<sub>CF</sub></td><td><u>0.27</u></td><td>1.12</td><td>1.34</td><td>1.88</td><td>0.2</td><td>0.83</td></tr><tr><td>FG<sub>CF</sub></td><td><u>0.6</u></td><td>0.89</td><td>0.886</td><td>1.63</td><td>0.3</td><td>0.6</td></tr><tr><td>FI<sub>CF</sub></td><td>1.27</td><td><u>1.1</u></td><td>1.37</td><td>2.005</td><td>1.24</td><td>0.75</td></tr></tbody></table>
<table><caption>Table 6.13: Evaluating symbolic explanation-based feature attribution scheme through problem transformation with respect to the Sensitivity and Data-explanation stability properties.</caption><thead><tr><th></th><th></th><th>YELP</th><th>AUG. MNIST</th><th>FOODTRUCK</th><th>NYC15</th></tr></thead><tbody><tr><td rowspan="6">Sensitivity</td><td>FR<sub>CF</sub></td><td>2.46</td><td><u>2.75</u></td><td><u>3.6</u></td><td>2.46</td></tr><tr><td>FR<sub>SR</sub></td><td><u>2.6</u></td><td>1.64</td><td>2.11</td><td><u>2.6</u></td></tr><tr><td>FG<sub>CF</sub></td><td>2.26</td><td>2.18</td><td><u>2.69</u></td><td>2.25</td></tr><tr><td>FG<sub>SR</sub></td><td><u>3.8</u></td><td>2.47</td><td>3.53</td><td><u>3.81</u></td></tr><tr><td>FI<sub>CF</sub></td><td>2.13</td><td>1.83</td><td><u>2.25</u></td><td>2.13</td></tr><tr><td>FI<sub>SR</sub></td><td><u>3.82</u></td><td>2.43</td><td>3.54</td><td><u>3.82</u></td></tr><tr><td rowspan="6">Data-explanation stability</td><td>FR<sub>CF</sub></td><td><u>0.83</u></td><td>1.11</td><td><u>1.67</u></td><td><u>0.83</u></td></tr><tr><td>FR<sub>SR</sub></td><td>1.63</td><td>1.64</td><td>1.9</td><td>1.4</td></tr><tr><td>FG<sub>CF</sub></td><td>1.4</td><td>1.42</td><td>3.42</td><td><u>1.39</u></td></tr><tr><td>FG<sub>SR</sub></td><td>2.39</td><td>2.47</td><td>3.01</td><td>3.26</td></tr><tr><td>FI<sub>CF</sub></td><td>1.81</td><td><u>0.97</u></td><td>2.32</td><td>1.81</td></tr><tr><td>FI<sub>SR</sub></td><td><u>2.4</u></td><td>2.44</td><td>2.58</td><td>3.3</td></tr></tbody></table>

Table 6.13 presents the evaluation results of the symbolic-based feature attribution through problem transformation scheme. SRs explanations seem to be more sensitive to change with higher values compared to those of CFs (underlined in table 6.13). On the other hand, *CF* explanations seem more stable with smaller values than those of SRs (underlined in Table 6.13). In terms of which oracle to choose, the *FR* seems to provide the most stable explanations and along with *FI*, providing the most sensitive explanations too.

The last property we check on the symbolic-based feature attribution explanations is the Label-explanation stability. The results are presented in Figures 6.6 and 6.7. The green bar-charts represent the results of *SRs* explanations while the blue ones represent the results of the *CFs*. As shown in the figures, all of the oracles manages to keep a strong stability between the explanations of related labels. We notice on the graph of certain datasets (in particular MNIST, Yelp and Nyc-mental-illness) that weakly correlated labels are associated with weakly correlated explanations, which reflects a low stability between explanations of labels that are not related. We also note that label-explanation stability is better preserved at the level of the explanation *SRs* compared to the *CFs*.
<figure><img src="image_73.png" /><figcaption>Figure 6.6: Evaluating label-explanation stability using the mutual information (MI) coefficient.</figcaption></figure>

6.5.4 Comparative study

Now that we have seen the results for the different schemes proposed to define feature attribution expla-
nations for a multi-label predictor, we compare them to see if we can identify the best scheme or even
the best oracle feature attribution to use. We summarize the main points as follows:

- **Speed (runtime)**: it is obvious that the problem transformation scheme is faster than the aggregation ones. In the first scheme we call the feature attribution oracle only once while we will have to do *k* calls in the second scheme.

- **Representation of the explanation**: the final representation is the same for all schemes. The multi label explanation will be presented as a vector of size *n* representing the influence of each feature on the whole (or a subset) predicted labels

- **Nature of explanations**: the problem transformation scheme retains the nature of the explanations generated, by transforming the multi-label problem into a binary classification problem, we can directly use the multiple interpretability methods defined for single-label problems and thus, preserve the nature of the explanations and their properties. This is not the case with aggregation.

- **Feature attribution oracle**: there is no clear explanation function that stands out more than the others to best measure the properties according to the different approaches. We notice that SHAP often makes it possible to obtain the smallest values for the criterion of Data-explanation stability while the symbolic-based feature attribution methods seem to get out of it better if we consider the property of sensitivity. Regarding the Label-explanation stability property, symbolic-based oracles seem to stand out compared to SHAP and LIME.
<figure><img src="image_74.png" /><figcaption>Figure 6.7: Evaluating label-explanation stability using the Pearson's R coefficient.</figcaption></figure>

6.5.5 Evaluating feature attribution inference

The goal here is to infer explanations given related classes of a multi-label predictor. To do so, we com-
pare the difference between scores that we will call "deduced" and the real explanations calculated for
the label in question. This evaluation is done on different multi-label predictors having MLP Classifier,
Logistic Regression and Random Forest Classifier as base classifiers. The feature attribution oracles used
are SHAP, LIME and ASTERYX.

Different metrics such as euclidean distance and mean squared error (MSE) were used to compute
the difference between the real feature attribution explanations and the deduced ones and are represented
on the *Y* axis. They give a relatively high weight to large difference between real and deduced scores,
which means the smaller the weight, the closer the fit is to the real feature attribution scores.
The *X* axis represents the *MI* (resp *Pearsons's R*) coefficient between pairs of labels of the same data
instances. For example, pairs of labels *y*<sub>*i*</sub> and *y*<sub>*j*</sub> having *MI*(*y*<sub>*i*</sub>, *y*<sub>*j*</sub>)=1 (resp *Pearsons's R*(*y*<sub>*i*</sub>, *y*<sub>*j*</sub>)=1) are
strongly correlated around *V*(*x*, *r*). On the *Y* axis, the mean of distances between real feature attribution
scores and the *MI*-deduced (resp *Pearson's R*-deduced) scores corresponding to the instances predicted
with the pair (*y*<sub>*i*</sub>, *y*<sub>*j*</sub>) is represented. To sum up, we have on the *X* axis of Figures 6.8 and 6.9, the *MI*(*y*<sub>*i*</sub>,
*y*<sub>*j*</sub>) of different pairs of labels. On the *Y* axis, the average distance between the real and alpha-score
deduced from *MI*(scores) where alpha is the coefficient between the related pair of labels.

The curves in Figures 6.8 and 6.9 show that all the explanation methods used tend to generate expla-
nations very similar to those inferred from a relationship between two classes. These latter are obtained
by multiplying the real scores with the coefficient between the related pair of labels. Note that the greater
the correlation coefficient between the labels, the smaller the difference between the explanation vectors
and those for the two measurements used (MSE and Euclidean distance).
<figure><img src="image_75.png" /><figcaption>Figure 6.8: Average difference between real vs deduced feature attribution scores (SHAP/LIME) given the MI between labels.</figcaption></figure>
<figure><img src="image_76.png" /><figcaption>Figure 6.9: Average difference between real vs deduced feature attribution scores(FR/FIxFG) given the MI between labels.</figcaption></figure>
This track is interesting because in addition to the power of optimization that there may be in terms of
the number of calls to a multi-class oracle and the number of explanations to be processed, the inference
of explanations can be used to "learn to explain" by training a model on the generated explanations.

6.6 Conclusion

The literature reports many approaches for explaining binary and multi-class classifiers but only a few
are dedicated to the multi-label setting. In this chapter, we addressed feature attribution for multi-label
classification problems. The main objective is to take advantage of existing feature attribution methods
for multi-class classification and provide schemes to use them as oracles to provide features attributions in
a multi-label classification setting. We proposed three schemes for achieving this task : i) an aggregation-
based scheme, ii) a problem transformation-based scheme and iii) symbolic explanation-based one. In
order to assess the relevance of feature attributions obtained using our three schemes, we first highlighted
three desirable properties : sensitivity, data-explanation stability and label-explanation correlation, then
used such properties to assess empirically the quality of our feature attribution schemes.We proposed
to go further concerning the property of label-explanation correlation by exploiting it to infer feature
attributions relative to a label by using the explanations already calculated for another label with which
it is correlated. Clearly, the preliminary results we have obtained confirm our intuition regarding the
new property of label-explanation correlation. In addition to the feature attribution inference, it would be
interesting to exploit the correlations to better present explanations. This is a track that we will investigate
in our future work.
Conclusion and future work avenues

This thesis brings different contributions on explaining individual predictions of multi-class and multi-
label classifiers.

Let's first summarize our results and some perspectives that we think are most relevant and promising.
Note that the work of this thesis has been the subject of international publications (see ([BCAMT20]),
([BCAMT21a]), and ([BCAMT21a))).

In chronological order, we first worked on proposing a symbolic approach to generate two types of complementary explanations to explain predictions of a multi-class classification problem. We proposed a generic and declarative approach based on the encoding of the model to be explained in an equivalent symbolic representation. This latter serves to generate in particular two types of symbolic explanations which are *sufficient reasons* and *counterfactuals*. We rely on SAT-solving where we encode the problems of generating our symbolic explanations as two common problems related to satisfiability testing which are enumerating *minimal reasons* of why a formula is inconsistent (MUSes) and *minimal changes to restore the consistency of a formula* (MCSes).

For instance, our contribution makes it possible to equip the symbolic approach proposed in [SCD19] with a module for counterfactual explanations. Our work presented in [BCAMT20] takes advantage of well-defined concepts and proven tools for the MCSes enumeration. Moreover, it is specifically designed to provide exact, valid and complete explanations with a rigorous foundation since it is based on the encoding of a classifier into an **equivalent and tractable** symbolic representation. However, such approach suffered from some limitations. The main issue faced with this contribution is that it required a compilation process to get the symbolic representation of a classifier where the compilation algorithms (e.g [SCD19, SSDC20] ) remain specific to the type of model studied and thus, limit the type of models that could be explained. The other issue was the complexity of exact methods where the size of the symbolic encoding such as Ordered Decision Diagram (ODD) associated with the classifier becomes intractable (exponential) for problems with a few dozen input variables, which makes the explanations too expensive to compute. This is not new as it is known that scalability is a weak point of all exact methods developed for full-precision or binarized networks. Moreover, another issue that arose was the question of how to choose an explanation and on what basis given the large number of explanations generated. Recall that an inconsistent Boolean formula formed by *p* clauses, can potentially have a large set of explanations (the number of MUSes and MCSes can be in the worst case exponential in *p* [LS08]).

In a second time and in order to overcome the scalability limitation mentioned above, we introduced
the surrogate modeling to the encoding step of our approach. Henceforth, the encoding of a classifier
is done either : (1) using model encoding algorithms if available (compilers already exist for Bayesian
networks [SCD19], decision trees and some neural nets) and if the encoding is tractable (non agnostic
case); (2) Or using a surrogate approach consisting in the approximation of the classifier's decisions by
the mean of a surrogate model trained on the locality of an instance (agnostic case). The aim of such
proposal is to balance between the guarantees of using a formal method and its feasibility in practice.
Thus, we keep a rigorous symbolic formalism and we introduce the surrogate modeling to enhance the
scalability of the approach and makes it more general as it assumes no knowledge whatsoever about the
model (model-agnostic). The surrogate model should guarantee to be i) as faithful as possible to the initial model (ensures same predictions) and ii) allows to obtain a tractable CNF encoding. We used the Random Forest classifiers as it showed a good trade-off between the desiderata just mentioned. The experiments showed interesting results in reducing the time and the size of the encoding representation confirming that introducing a symbolic approximation through a surrogate model makes the approach more scalable.

Afterwards, we shifted our attention to the score-based explanations where we equipped our generic model-agnostic approach to explain individual outcomes with a third module (Explanation and feature relevance scoring) that aims to evaluate the explanations by assessing their relevance w.r.t a set of natural properties. Moreover, such module allows to assess the relevance of features and to evaluate their individual contributions to the outcome using scoring functions w.r.t to a set of intuitive properties. The objective of the approach is to explain the predictions of a black-box model by providing both symbolic and score-based explanations with the help of Boolean satisfiability concepts. To the best of our knowledge, our approach is the first that generates different types of symbolic explanations and **fine-grained** score-based ones. It allows on the one hand to exploit the strength of modern SAT-solvers and on the other hand to consider other forms of symbolic explanations.

Our work then turned to the multi-label tasks, where typically many labels are predicted for each instance. First, we extended our proposed approach from a multi-class setting to explain predictions in a multi-label setting by adapting the definitions of the symbolic explanations. We defined several symbolic explanation types and showed how we can enumerate them using the existing SAT-based oracles. By taking advantage of the structural relationships between labels, a new concept for label-based explanations is introduced resulting in a reduction of the number of generated explanations and leading to a better presentation. The contributions of this work, namely, developing concepts specific to the multi-label case such as label-based and fine-grained explanations are not simple extensions from the multi-class framework to the multi-label one.

Finally, we propose a novel model-agnostic feature-based approach based on widely-used feature attribution methods and symbolic explainers. We propose two techniques to generate multi-label explanations: (1) by combining label's explanation using aggregation functions and (2) by learning a binary classifier that only recognizes the outcome to explain (transformation problem). Furthermore, we propose to infer explanations from the relationships between the output classes of a multi-label classifier. We extend the properties of sensitivity, stability to the multi-label setting in addition to a new property specific to multi-label classification that we called label-explanation correlation. We show the method's effectiveness with an empirical analysis on real-world data, yet, none of the XAI methods significantly outperforms the others.

## Prospects and future work

Different avenues for future work are still open after this thesis. Firstly, our analysis of the practical feasibility of the approach has been carried out on few different application cases, but all of them designed to use binary classifiers. It would be interesting to test the applicability of our approach extended to the multi-class case. We also want to check empirically the impact of fidelity of a surrogate model on the generated explanations and their quality. For example, we would check their consistency by testing if the explanations of the surrogate model and the original are approximately the same. We can also evaluate the number of explanations generated and see if it increases/decreases with respect to the fidelity of the surrogate model.
As for numerical explanations, we plan in the future to study the relationships between score-based ex-
planations w.r.t the different properties of sufficient reasons and counterfactuals and check if the minimal
hitting set duality between MUSes and MCSes is reflected at the scores level. Another track would also
be to check the consistency between the scores calculated for the variables and those calculated for the
explanations. Intuitively, a variable that has an important weight w.r.t to some property is expected to
participate in explanations that also have a high score and vice versa. Thus, if such a relationship were to
be confirmed, one could, for example, infer the score of an explanation from the variables that compose
it, and conversely, assign weights to variables from the scores of the explanations in which they partic-
ipate. We also intend to explore the use of inconsistency measurements to assign scores to the different
explanations obtained.

Another interesting avenue would be to check experimentally whether the proposed approach is efficient
in verifying the robustness of a model and finding adversarial examples. We stress that even if for the ex-
isting approaches proposed to generate adversarial examples, the optimization problem is similar to the
one posed in the generation of counterfactuals, the desiderata are different. For example, in adversarial
learning (often applied to images), the goal is an imperceptible change in the input image enough to fool
models into producing incorrect predictions, while for counterfactual enumeration, the goal is provide
users with actionable explanations in the form of data instances that would have received a different
outcome.

There are several relevant directions for future work for the multi-label setting as well. In particular,
we intend to focus on how to extract the relations between the labels from the predictions of the clas-
sifiers and how to exploit the relations extracted during the generation of explanations. In theory, any
relationship between labels can be exploited. In practice, we limited ourselves to certain types of rela-
tionships that are easy to extract and easy to understand for the user, but it can be interesting to explore
other types of relationships linking the output classes.

Another idea for a multi-label setting would be to consider the explanations set generated using a XAI
oracle (e.g LIME or SHAP) for a label as an argumentation system, and multi-label explainability as a
problem fusion of argumentation systems. For example, a variable from the test input may have a posi-
tive influence (score) for a given label and a negative influence (score) for another one, thus, the question
about how to attribute a final score to such variable w.r.t to the whole multi-label prediction arises. Such
idea is motivated by the objective of using the concepts of argumentation for the resolution of conflicts
between the beliefs of a rational agent (here explanations of a data instance input).

Another possible avenue would be the integration of preferences and knowledge of the domain up-
stream of the enumeration, given that SAT modeling allows us to do so.