DLIME

Architecture

Algorithm

• Input: Dataset $\mathcal{D}_{train}$, Instance $x$, lenght of explanation $\mathcal{K}$
• Initialise $\mathcal{Y} \leftarrow {}$
• Initialise cluster for $i$ /in/ $1,\dots,N$ do
  • $C_i \leftarrow {i}$
• end
• Initialise clusters to merge $\mathcal{S} \leftarrow$ for $i$ /in/ $1\dots N$
• while /no more clusters are available for merging/ do
  • Pick two most similar cluster with minimum distance $d$:
    • $(j,k) \leftarrow \arg\min_{d(j,k)} \in \mathcal{S}$
  • Create new cluster $C_l \leftarrow C_j \bigcup C_k$
  • Mark $j$ and $k$ unavailable to merge
  • if $C_l \neq i$ in $1\dots N$ then
    • Mark $l$ as available, $\mathcal{S} \leftarrow \mathcal{S} \bigcup {l}$
  • end
  • foreach $i \in \mathcal{S}$ do
    • Update similarity matrix by computing distance $d(i, l)$
  • end
• end
• while $i$ /in/ $1,\dots,n$ do
  • $d(\mathbf{x}i, \mathbf{x})=\sqrt{(x{i1}-x_1)^2+\dots+(x_{im}-x_m)^2}$
• end
• $ind \leftarrow$ Find indices for the $k$ smallest distance $d(\mathbf{x}_i, \mathbf{x})$
• $\hat{y} \leftarrow$ Get majority label for $x \in ind$
• $n^s \leftarrow$ Filter $\mathcal{D}_{train}$ based on $\hat{y}$
• foreach $i$ /in/ $1, \dots, n$ do
  • $\mathcal{Y} \leftarrow $ Pairwise distance of each instance in cluster $n^s$ with the original instance $x$
• end
• $\omega \leftarrow$ LinearRegression$(n^s, \mathcal{Y}, \mathcal{K})$
• return $\omega$