# _Applied Sciences_
## 2 The Gbt-HIPS Method
### Merging and Pruning  
The final step generates the CR-based explanation using a breadth first, greedy, heuristic search of the path snippets. Before the search commences, the first step is to set the rule consequent as the GBT model's classification of the explanandum instance \(\mathbf{x}\). This step guarantees local accuracy. The search then begins from \(\varnothing\implies g(\mathbf{x})\), the \"null\" rule that has an empty antecedent and maximum coverage. The first path snippet, at the top of the sorted dictionary, is appended to the rule's antecedent. The reliability on the training data is evaluated and this value stored. Then, one at a time in turn, path snippets from the sorted dictionary are added as candidate antecedent terms. If the union improves the reliability, the snippet is retained in the rule. If not, the snippet is simply discarded. In both cases snippets are removed from the dictionary.  
To further reduce the number of iterations, any path snippets are deleted from the ranked list if they contain boundary values of continuous features that fall outside the current coverage region. That is, coverage is forced to decrease monotonically. These steps, merging a path snippet and pruning the dictionary, iterate until a target reliability threshold is met or the list is exhausted, as illustrated in Algorithm 1.  
```
1:procedureRuleMerge(\(g\), \(\mathbf{X}\), \(\mathbf{x}\), dictionary, \(\rho\))
2:\(\triangleright\) Inputs: model, training data, explanandum, sorted map, target reliability.
3:\(\mathcal{C}\leftarrow\varnothing\)\(\triangleright\) Candidate set of antecedent terms
4:\(r\leftarrow\zeta(g,\mathbf{X},\mathbf{x})\)\(\triangleright\) Prior reliability.
5:while\(r<\rho\) and length dictionary \(>0\)do
6:\(\mathbf{Z}\leftarrow\mathbf{X}\cap(\mathcal{C}\cup\textit{ dictionary}^{(1)})\)
7:\(\triangleright\) Append top ranking path snippet. Partition only covered instances.
8:if\(\zeta(g,\mathbf{Z},\mathbf{x})>r\)then
9:\(\mathcal{C}\leftarrow\mathcal{C}\cup\textit{ dictionary}^{(1)}\)\(\triangleright\) Path snippet added to rule.
10:\(r\leftarrow\zeta(g,\mathbf{Z},\mathbf{x})\)
11:\(\textit{ dictionary}\leftarrow\textit{ dictionary}\setminus\textit{ dictionary}^{(1)}\)
12:return\(\mathcal{C}\)\(\triangleright\) Remove top snippet. Reset indices.
```  
**Algorithm 1** Rule Merging  
After rule merging completes, the candidate set of antecedent terms \(\mathcal{C}\) is returned, forming the final candidate rule. This candidate is pruned of extraneous terms in a process that also generates the counterfactual detail, while enforcing minimal completeness, as required by [PERSON]'s principles of explanation [35]. The inclusion of extraneous terms can occur because the greedy heuristic only enforces a monotonic increase in reliability. Thus, terms that increase performance only very slightly may be included. Furthermore, some antecedent terms are rendered redundant through interaction with terms that are added subsequently. These non-optimal side-effects are to be expected with greedy, heuristic algorithms. Therefore, the pruning step iterates through the \"point changes\", removing any antecedent terms that are found to be extraneous. A point change is defined as the reversal of the inequality constraint of a single antecedent term. Therefore, point changes represent a set of \"adjacent spaces\" to that hyper-cube (or half-space) of the input space that is covered by the rule. Adjacent spaces are outside the hyper-cube by one axis-aligned step across a single rule boundary. To determine whether an antecedent term is extraneous, the reliability is evaluated on the training instances covered by each adjacent space. If reliability decreases by <\(\delta\) (a user-defined parameter) inside an adjacent space, that antecedent term can be removed from the rule. The result is a shorter rule that has a greater coverage and whose reliability lies within the user-defined tolerance of the unpruned candidate's reliability.