# Fidex and FidexGlo: From Local Explanations to Global Explanations of Deep Models +
## 3 Materials and Methods
### The Fidex Algorithm  
Fidex is a local rule extraction algorithm, which means that it generates an explanation for a single sample. Specifically, it is a greedy algorithm that aims to maximize the fidelity criterion. Fidelity refers to how well the extracted rules mimic the behavior of a model. For example, with \(s\) samples in a training set and \(s^{\prime}\) samples for which the classifications of the rules match the classifications of the model, the fidelity is \(s^{\prime}/s\).  
Let us describe Fidex; we assume that we have \(d\) input variables \(x_{1}\ldots x_{d}\). Furthermore, let us denote \(L_{xi}\) the list of hyperplanes for input variable \(x_{i}\); \(L_{xi}\) is calculated according to Equation (7). The purpose of Fidex is to determine a propositional rule \(R\) with respect to sample \(S\). The fidelity of \(R\) to be reached in \(\rho\) steps is \(\phi\), and is calculated with all the samples of the training set. The pseudocode of the Fidex algorithm is shown in Algorithm 1:  
```
Given sample \(S\) and rule \(R=\emptyset\) for\(<\)\(n=1\ldots\rho\)> do for\(<\)all hyperplanes \(L_{xi}\) of all input variables \(x_{i}\)> do  find the hyperplane \(h^{*}\) allowing the highest improvement of fidelity endfor if\(<\)the increment of fidelity is strictly positive> then\(R=R\cup h^{*}\) if\(<\)fidelity reaches value \(\phi\)> then exit endfor
```  
**Algorithm 1** Pseudocode of the Fidex algorithm  
Fidex's computational complexity depends mainly on its loops and corresponds to \(O(\rho\cdot d\cdot\Theta\cdot s)\), with \(s\) being the number of training samples. Note that the \(s\) factor appears as, for each new rule antecedent, Fidex must determine whether a sample is covered by \(R\) or not. Finally, \(\Theta\) is due to the number of hyperplanes in each list of possible hyperplanes \(L_{xi}\). As an example of the number of hyperplanes, if we have 100 input variables and 100 steps in the staircase function in the first hidden layer of a DIMLP (or a QSVM) then \(L_{xi}\) has 10,000 hyperplanes, but if we have an ensemble of 25 DIMLPs, this number becomes 250,000. With a CNN trained on images of size 64 \(\times\) 64 and 255 steps, we obtain 1,044,480 hyperplanes. As this number is quite large, we have two parameters to reduce the number of hyperplanes. Specifically, the execution of Fidex is managed by five parameters:  
* \(\mu\): minimal number of samples covering the final rule;
* \(\rho\): maximal number of Fidex steps (which is strongly related to the number of rule antecedents);
* \(\phi\): fidelity of the rule;
* \(p\): dropout of input variables;
* \(q\): dropout of hyperplanes.  
The parameter \(\mu\) is the minimum number of samples in the final rule, with a default value of two. The maximum number of iterations in Fidex which is related to the maximum number of rule antecedents is \(p\); its default value is ten. The default value of \(\phi\), which corresponds to the fidelity that has to be reached, is 100%. The execution time of Fidex can be accelerated by considering two dropout parameters: \(p\) and \(q\). Essentially, \(p\) determines at each step the proportion of input variables that will not be considered. The excluded variables are selected randomly. Parameter \(q\) is similar, but with respect to excluded hyperplanes in \(L_{xi}\). Default values for \(p\) and \(q\) are equal to 0. If variables \(x_{i}\) are always selected with the same order, for instance from 1 to \(d\) (see step 3) and without dropout (\(p=0\) and \(q=0\)), Fidex is deterministic. Since a DT is a collection of nodes with conditions related to the input variables, the list of hyperplanes for an ensemble is the union of all the conditions of the trees. As a result, with GB, which typically uses shallow trees, fewer hyperplanes are brought into play compared to RFs and DIMLPs, so the rule extraction algorithm tends to be faster.