# Local Interpretable Model-agnostic Explanations (LIME)
###### tags: `Data Science`, `Explainable Machine Learning`
## Motivation
* If the users do not trust a model or a prediction, they will not use it.
* Determining trust in individual predictions is an important problem when the model is used for decision making.
* __Data leakage__, defined as the unintentional leakage of signal into the training (and validation) data that would not appear when deployed, potentially increases accuracy.
* __Dataset shift__, where training data is different than test data.
<span style="padding-right: 45px;"></span>

## Contribution
* The authors proposed LIME, an algorithm that can explain the predictions of any classifier or regressor in a faithful way, by approximating it __locally__ (take one sample at a time) with an interpretable model.

## Desired Characteristics for Explainers
* __Interpretable__: linear model and additive model (with low dimensions), decesion tree (with low depth)
<span style="padding-right: 30px;"></span>
* __Local fidelity__: the explainable model must correspond to how the model behaves in the vicinity of the instance being predicted.
* __Model-agnostic__: the explainable model should be able to explain __any model__.

## Methods
### Definitions
* $x \in \mathbf{R}^d$: original features of a specific instance (with $d$ dimensions).
* $x' \in \{0, 1\}^{d'}$: whether the feature of a specific instance is selected. _(The authors do not explain how to optimize this)_.
* $G$: a class of potentially interpretable models
* $g \in G$: a explanable model, with domain $\{0, 1\}^{d'}$
* $\Omega(g)$: complexity of model $g$. For instance, the depth of decision tree or the number of non-zero weights for linear additive models.
* $\pi_x(z)$: proximity measure between an instance $z$ and selected instance $x$.
* $L(f, g, \pi_x)$: measure of unfaithfulness of model $g$ in approximating $f$ in a locality defined by $\pi_x$.

### Optimization Function
In order to ensure both interpretability and local fidelity, the authors must minimize $L(f; g; \pi_x)$ while having $\Omega(g)$ be low enough to be interpretable by humans:

\begin{align}\text{Equation}\;(1):\;\xi(x)=\underset{g\in G}{\mathrm{argmin}}\;L(f, g, \pi_x)+\Omega(g)\end{align}

### Sampling for Local Exploration
1. Let $\pi_x(z)=\exp(-D(x, z)^2/\sigma^2)$ be the weighted probability of other instances being sampled, where $D$ can be any distance metrics between $x$ and $z$ (the feature of other instances), and $\sigma$ is a hyperparameter for _width_.
2. Uniformly draws nonzero element of the instances, denoted as $Z$.
3. Use the perturbed feature of selected instances $z'\in\{0, 1\}^{d'}$ to recover the original representation for selected instances $z\in\mathbf{R}^d$ (see b, c and d in the following figure)
4. Obtain $f(z)$ as the label (ground truth) for the explanable model. e.g. in the figure above, the label for (b) is Electric guitar, which is obtained by the complex model $f$.

### Sparse Linear Explanations
Let $g(z')=w_g\cdot z'$. We can further defined the loss function to be:

\begin{align}\text{Equation}\;(2):\;L(f, g, \pi_x)=\underset{z. z' \in Z}{\Sigma}\pi_x(z)(f(z)-g(z'))^2\end{align}

The it is possible to apply various strategies to optimzed the optimization functions.

### Submodular Pick
Because it is not sufficient to evaluate and assess trust in the model based on a single prediction. The authors proposed to give a global understanding of the model by explaining a set of individual instances:

1. Suppose the users have a budget to examine $B$ explanations and given the explanations for a set of $n$ instances $X$.
2. The authors constructed an $n \times d'$ explanation matrix $W$ representing the local importance of the interpretable components.
3. For each component $j$ (for instance, b, c, and in the above figure is each a component), then we defiened $W_{ij}=\xi(x_i), \text{with}\;x_{ij}'$
4. Define global importance $I_j=\sqrt{\Sigma_{i=1}^nW_{ij}}$
<span style="padding-right: 60px;"></span>
5. Define set function $c(V, W, I)=\underset{j=1}{\overset{d'}{\Sigma}}\pmb{1}_{\{ \exists i\in V:W_{ij}>0\}}I_j$ (if the component is already in the set $V$, then the importance will not be added again)
6. The pick problem can now be formulated as an optimzation problem of the following function. The function is NP-hard; therefore, the authors use greedy algorithm that add the highest marginal covearge gain each time as the solution.

\begin{align}\text{Equation}\;(3):\;Pick(W, I)=\underset{V, |V|<B}{argmax}\;c(V, W, I)\end{align}

## Limitations
* Interpretable model might not be powerful enough to explain certain complex model. e.g. sepia-toned and retro-style images.
* If the underlying model is highly non-linear even in the locality of the prediction, it is not possible to use a linear model to create a faithful explanation. However, this method can estimate the faithfulness of the explnaation using $\text{Equation (2)}$
* There is no hint on which instance to pick for the evaluation of the model.
* The correlated features in the explainer is still difficult to interpret.

## Reference
* Marco Tulio Ribeiro, Sameer Singh, Carlos Guestrin. 2016. "Why Should I Trust You?"- Explaining the Predictions of Any Classifier. arXiv.