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 \cup 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} \cup \{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} โ† $ 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\)