doc/source/methods/Similarity.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[[source]](../api/alibi.explainers/similarity/grad.rst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Similarity explanations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview <a id='overview'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `GradientSimilarity` class implements an explanation method that belongs to the family of the [similarity-based explanations](https://arxiv.org/abs/2006.04528) methods. \n",
    "\n",
    "Given an input instance of a machine learning model, similarity-based methods aim to explain the output of the model by finding and presenting instances seen during training that are similar to the  given instance. Roughly speaking, an explanation of this type should be interpreted by the user following a rationale of the type:  \"I classify this image as a cat because it is similar to another image in the training set that was labeled as a cat\". \n",
    "\n",
    "Various similarity-based methods use different metrics to quantify the similarity between two instances. The `GradientSimilarity` class implements gradients-based metrics, as introduced by [Charpiat et al., 2019](https://papers.nips.cc/paper/2019/hash/c61f571dbd2fb949d3fe5ae1608dd48b-Abstract.html).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Theory <a id='theory'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The purpose of gradient based methods is to define a similarity kernel between two instances that quantify how similar the instances are *according to a model* trained for a specific task (for example a classifier).\n",
    "In particular, given two instances $z = (x, y)$ and $z^\\prime = (x^\\prime, y^\\prime),$ a model $f_{\\theta}(x)$  parametrized by $\\theta$ and a loss function $\\mathcal{L}_\\theta(z) = \\mathcal{L}(f_\\theta(x), y)$, we define similarity as the influence of $z$ over $z^\\prime$ with respect to the loss function. The similarity quantifies how much an additional parameter's update that changes the loss calculated at $z$ by a certain amount would change the loss calculated at $z^\\prime.$\n",
    "\n",
    "In particular, let us consider the Taylor expansion of the loss function $\\mathcal{L}$ at the point $z,$ which reads like:\n",
    "$$\n",
    "\\mathcal{L}_{\\theta + \\delta\\theta}(z) = \\mathcal{L}_\\theta(z) + \\delta\\theta \\nabla_\\theta \\mathcal{L}_\\theta(z) + \\mathcal{O(||\\delta \\theta\\|^2)}\n",
    "$$\n",
    "\n",
    "If we want to change the loss at $z$  by an amount $\\epsilon,$ we can do so by changing the model's parameters $\\theta$ by an amount $\\delta\\theta = \\epsilon \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z)||^2}$. In fact, by substituting this value in the Taylor expansion above we obtain:\n",
    "\n",
    "$$\n",
    "\\mathcal{L}_{\\theta+\\delta\\theta} (z)=\\mathcal{L}_\\theta(z) + \\epsilon + \\mathcal{O}(|\\epsilon|^2)\n",
    "$$\n",
    "\n",
    "Now, we would like to  measure the impact of such change of parameters on the loss function calculated at a different point $z^\\prime.$ Using  Taylor expansion again, the loss at point $z^\\prime$ is given by:\n",
    "\n",
    "$$\n",
    "\\mathcal{L}_{\\theta + \\delta\\theta}(z^\\prime) = \\mathcal{L}_\\theta(z') + \\delta\\theta \\nabla_\\theta \\mathcal{L}_\\theta(z') + \\mathcal{O(||\\delta \\theta\\|^2)}\n",
    "$$\n",
    "\n",
    "Substituting $\\delta\\theta = \\epsilon \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z)||^2}$ we have\n",
    "\n",
    "$$\n",
    "\\mathcal{L}_{\\theta + \\delta\\theta}(z') = \\mathcal{L}_\\theta(z') + \\epsilon \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z)||^2} + \\mathcal{O(||\\epsilon||^2)}.\n",
    "$$\n",
    "\n",
    "In conclusion, the kernel\n",
    "\n",
    "$$\n",
    "k_{\\theta}(z, z') = \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z)||^2}\n",
    "$$\n",
    "\n",
    "quantifies how much the loss function at point $z'$ has changed after a parameters' update that has changed the loss at point $z$ by an amount $\\epsilon.$ It represents the influence that the point $z$ has over the point $z'$ with respect to the loss function. \n",
    "\n",
    "Based on this kernel, which is not symmetric,  the original paper suggests two symmetric alternatives:\n",
    "$$\n",
    "k_{\\theta}(z, z') = \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z')||||\\nabla_\\theta \\mathcal{L}_\\theta(z)||}.\n",
    "$$\n",
    "\n",
    "$$\n",
    "k_{\\theta}(z, z') = \\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z).\n",
    "$$\n",
    "\n",
    "All the three versions of the kernel are implemented in the `GradientSimilarity` class (see [Usage](#usage) section below). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Usage <a id='usage'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialization\n",
    "\n",
    "```python\n",
    "from alibi.explainers.similarity.grad import GradientSimilarity\n",
    "\n",
    "model = <YOUR_MODEL>\n",
    "loss_fn = <YOUR_LOSS_FUNCTION>\n",
    "\n",
    "explainer = GradientSimilarity(predictor=model,  # your tensorflow or pytorch model.\n",
    "                               loss_fn=loss_fn,  # your loss_fn. Usually the loss function of your model.\n",
    "                               sim_fn='grad_dot',  # 'grad_dot', 'grad_cos' or 'grad_asym_dot'.\n",
    "                               task='classification',  # 'classification' or 'regression'.\n",
    "                               precompute_grads=False,  # precompute training set gradients in fit step.\n",
    "                               backend='tensorflow',  # 'tensorflow' or 'pytorch'.\n",
    "                               device=None,  #  pytorch device. For example 'cpu' or 'cuda'.\n",
    "                               verbose=False)\n",
    "```\n",
    "\n",
    "* `predictor`: The `GradientSimilarity` class provides both a `tensorflow` and a `pytorch` backend, so your predictor can be a model in either of these frameworks. The `backend` argument must be set accordingly.\n",
    "\n",
    "* `loss_fn`: The loss function $\\mathcal{L}(f_\\theta(x), y)$ used to compute the gradients. Usually the loss function used by the model for training, but it can be any function taking as inputs the model's prediction and the labels $y$-s.\n",
    "\n",
    "* `sim_fn`: The similarity function used to compute the kernel $k_{\\theta}(z, z').$ `GradientSimilarity` implements 3 kernels:\n",
    "\n",
    "    * 'grad_dot',  defined as \n",
    "    $$\n",
    "    k_{\\theta}(z, z') = \\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z).\n",
    "    $$\n",
    "    \n",
    "    * 'grad_cos', defined as\n",
    "    $$\n",
    "    k_{\\theta}(z, z') = \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z')||||\\nabla_\\theta \\mathcal{L}_\\theta(z)||}.\n",
    "    $$\n",
    "    \n",
    "    * 'grad_asym_dot', defined as\n",
    "    $$\n",
    "    k_{\\theta}(z, z') = \\frac{\\nabla_\\theta \\mathcal{L}_\\theta(z')\\cdot\\nabla_\\theta \\mathcal{L}_\\theta(z)}{||\\nabla_\\theta \\mathcal{L}_\\theta(z)||^2}.\n",
    "    $$\n",
    "\n",
    "* `precompute_grads`: Whether to pre-compute the training set gradients during the fit step or not.\n",
    "\n",
    "* `backend`: Backend framework. `tensorflow` or `pytorch`.\n",
    "\n",
    "* `device`: pytorch device. For example `cpu` or `cuda`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fit\n",
    "\n",
    "Fitting is straightforward, just passing the training set:\n",
    "```python\n",
    "explainer.fit(X_train, y_train)\n",
    "```\n",
    "\n",
    "In this step, the dataset and the data input dimensions are stored as attributes of the class. If `precompute_grads=True`, the gradients for all the training instances are computed and stored as attributes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Explanation\n",
    "\n",
    "We can now explain the instance by running:\n",
    "\n",
    "```python\n",
    "explanation = explainer.explain(X, y)\n",
    "```\n",
    "\n",
    "\n",
    "* `X`: Test instances to be explained.\n",
    "\n",
    "* `y`: Target class (optional). This array can contain either a single entrance that is applied for all test instances or multiple entrances, one for each test instance.\n",
    "\n",
    "The returned explanation is a standard `alibi` explanation class with the following data attributes:\n",
    "\n",
    "* `scores`: A numpy array with the similarity score for each train instance.\n",
    "* `ordered_indices`: A numpy array with the indices corresponding to the train instances, ordered from the most similar to the least similar.  \n",
    "* `most_similar`: A numpy array with the 5 most similar instances in the train set.\n",
    "* `least_similar`: A numpy array with the 5 least similar instances in the train set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Notes on usage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Fitting and train set\n",
    "\n",
    "The `GradientSimilarity` will order the instances passed on the fit step based on the similarity with the instances passed on the explain step, regardless of whether they have been used for training the model or not. In the [examples below](#Examples)  we downsample the training set by picking a number of random instances in order to speed up the fit step. \n",
    "\n",
    "Setting `precompute_grads=True` will speed up the computation during the explain step, but the fit step will require considerably more time as the gradients for all the training instances are computed.  It could also require a considerable amount of memory for large datasets as all the gradients are stored as attributes of the class instance. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Similarity metrics\n",
    "\n",
    "As reported in [Hanawa et al. (2021)](https://arxiv.org/pdf/2006.04528.pdf), the `grad_dot`  metrics fails the identical class test, meaning that not always the most similar instances produced belong to the same class of the instance of interest. On the other hand, it is highly likely that the most similar instances belong to the same class  as the instance of interest when the `grad_cos` metric is used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Batch explanations\n",
    "\n",
    "When a batch of instances are passed to explain, a naive loop over the instances is performed internally and the gradients are calculated one instance at the time. This is due to limitation in the `tensorflow` and `pytorch` backends which automatically aggregate the values of the gradients in a batch. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Examples <a id='Examples'></a>\n",
    "\n",
    "[Similarity explanation on MNIST](../examples/similarity_explanations_mnist.ipynb)\n",
    "\n",
    "[Similarity explanation on ImageNet](../examples/similarity_explanations_imagenet.ipynb)\n",
    "\n",
    "[Similarity explanation on 20 news groups](../examples/similarity_explanations_20ng.ipynb)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}