nbs/sgd_shapley.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# default_exp sgd_shapley"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "# Author: Simon Grah <simon.grah@thalesgroup.com>\n",
    "#         Vincent Thouvenot <vincent.thouvenot@thalesgroup.com>\n",
    "\n",
    "# MIT License\n",
    "\n",
    "# Copyright (c) 2020 Thales Six GTS France\n",
    "\n",
    "# Permission is hereby granted, free of charge, to any person obtaining a copy\n",
    "# of this software and associated documentation files (the \"Software\"), to deal\n",
    "# in the Software without restriction, including without limitation the rights\n",
    "# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\n",
    "# copies of the Software, and to permit persons to whom the Software is\n",
    "# furnished to do so, subject to the following conditions:\n",
    "\n",
    "# The above copyright notice and this permission notice shall be included in all\n",
    "# copies or substantial portions of the Software.\n",
    "\n",
    "# THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n",
    "# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\n",
    "# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\n",
    "# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\n",
    "# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\n",
    "# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\n",
    "# SOFTWARE."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import operator as op\n",
    "from functools import reduce\n",
    "import random\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hide\n",
    "np.random.seed(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Projected Stochastic Gradient Shapley\n",
    "\n",
    "> Estimate the Shapley Values using a Projected Stochastic Gradient algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shapley Value definition\n",
    "\n",
    "In Collaborative Game Theory, Shapley Values ([Shapley,1953]) can distribute a reward among players in a fairly way according to their contribution to the win in a cooperative game. We note $\\mathcal{M}$ a set of $d$ players. Moreover, $v : P(\\mathcal{M}) \\rightarrow R_v$ a reward function such that $v(\\emptyset) = 0$. The range $R_v$ can be $\\Re$ or a subset of $\\Re$. $P(\\mathcal{M})$ is a family of sets over $\\mathcal{M}$. If $S \\subset \\mathcal{M}\\text{, } v(S)$ is the amount of wealth produced by coalition $S$ when they cooperate.\n",
    "\n",
    "The Shapley Value of a player $j$ is a fair share of the global wealth $v(\\mathcal{M})$ produced by all players together:\n",
    "\n",
    "$$\\phi_j(\\mathcal{M},v) = \\sum_{S \\subset \\mathcal{M}\\backslash \\{j\\}}\\frac{(d -|S| - 1)!|S|!}{d!}\\left(v(S\\cup \\{j\\}) - v(S)\\right),$$\n",
    "\n",
    "with $|S| = \\text{cardinal}(S)$, i.e. the number of players in coalition $S$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Shapley Values as contrastive local attribute importance in Machine Learning\n",
    "\n",
    "Let be $X^*\\subset\\Re^d$ a dataset of individuals where a Machine Learning model $f$ is trained and/or tested and $d$  the dimension of $X^*$. $d>1$ else we do not need to compute Shapley Value. We consider the attribute importance of an individual $\\mathbf{x^*} = \\{x_1^*, \\dots, x_d^*\\} \\in X^*$ according to a given reference $\\mathbf{r} = \\{r_1, \\dots, r_d\\}\\in X^*$.  We're looking for $\\boldsymbol{\\phi}=(\\phi_j)_{j\\in\\{1, \\dots, d\\}}\\in \\Re^d$ such that:\n",
    "$$ \\sum_{j=1}^{d} \\phi_j = f(\\mathbf{x^*}) - f(\\mathbf{r}), $$ \n",
    "where $\\phi_j$ is the attribute contribution of feature indexed $j$.  We loosely identify each feature by its column number. Here the set of players $\\mathcal{M}=\\{1, \\dots, d\\}$ is the feature set.\n",
    "\n",
    "In Machine Learning, a common choice for the reward is $ v(S) = \\mathbb{E}[f(X) | X_S = \\mathbf{x_S^*}]$, where $\\mathbf{x_S^*}=(x_j^*)_{j\\in S}$ and $X_S$ the element of $X$ for the coalition $S$. \n",
    "For any $S\\subset\\mathcal{M}$, let's define $ z(\\mathbf{x^*},\\mathbf{r},S)$ such that $z(\\mathbf{x^*},\\mathbf{r},\\emptyset) = \\mathbf{r}$, \\ $z(\\mathbf{x^*},\\mathbf{r},\\mathcal{M}) = \\mathbf{x^*}$ and\n",
    "\n",
    "$$ z(\\mathbf{x^*},\\mathbf{r},S) = (z_1,\\dots, z_d) \\text{ with } z_i =  x_i^* \\text{ if } i \\in S \\text{ and } r_i  \\text{ otherwise }$$ \n",
    "\n",
    "As explain in [Merrick,2019], each reference $\\textbf{r}$ sets a single-game with $ v(S) = f(z(\\mathbf{x^*},\\mathbf{r},S)) - f(\\mathbf{r}) $, $v(\\emptyset) = 0 $ and $v(\\mathcal{M}) = f(\\mathbf{x^*}) - f(\\mathbf{r}) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Estimation of Shapley Values by a Projected Stochastic Gradient algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Shapley Values are the only solution of a weighted linear regression problem with an equality constraint (see \\cite{RVZ}, \\cite{Lundberg} and \\cite{Aas}):\n",
    "\n",
    "$$ \\underset{\\boldsymbol{\\phi}\\in \\Re^d}{\\text{argmin}} \\sum_{S \\in \\mathcal{M}, S \\neq \\{\\emptyset, \\mathcal{M}\\}} w_S \\ [v(S) - \\sum_{j \\in S} \\phi_j]^2  $$ \n",
    "\n",
    "$$ \\text{subject to} \\sum_{i=j}^{d} \\phi_j = v(\\mathcal{M}) $$\n",
    "\n",
    "where the weights $w_S = \\dfrac{(d - 1)}{ {d\\choose|S|} |S| (d - |S|)}$.\n",
    "\n",
    "The function we want to minimize is:\n",
    "$$ F(\\boldsymbol{\\phi}) = (X\\boldsymbol{\\phi} - Y)^T W (X\\boldsymbol{\\phi} - Y) = \\dfrac{1}{n} \\sum_{i=1}^{n} n w_i (y_i - \\mathbf{x_i}^T \\boldsymbol{\\phi})^2 = \\dfrac{1}{n} \\sum_{i=1}^{n} g_i(\\boldsymbol{\\phi}), $$\n",
    "\n",
    "$F$ is a $\\mu$-strongly convex function defined on a convex set:\n",
    "$$ K = \\{\\boldsymbol{\\phi}; \\sum_{j=1}^{d} \\phi_j = v(\\mathcal{M}) \\ ; \\ ||\\boldsymbol{\\phi}|| \\le D \\} = K_1 \\cap K_2. $$\n",
    "\n",
    "We denote $\\boldsymbol{\\phi_t}=(\\phi_i^t)_{i\\in\\{1, \\dots, d\\}}$ the Shapley Values estimator at the iteration $t$. We also define $i_t\\sim p$, with $p$ a discrete uniform distribution with support $\\{1, \\dots, n\\}$, the coalition randomly draw for the iteration $t$. To find the unique minimum of $F$ on $K$, the Projected Stochastic gradient algorithm at each iteration $t$ follows the rules:\n",
    "\n",
    "Sample a coalition:\n",
    "$$ i_t \\sim p$$\n",
    "One step of gradient descent:\n",
    "$$ \\boldsymbol{\\phi_t} = \\text{Proj}_K (\\boldsymbol{\\phi_{t-1}} - \\gamma_t \\ (n p_{i_t})^{-1} \\nabla g_{i_t}) $$\n",
    "where\n",
    "* $\\gamma_t$ is a constant or decreasing step-size (also called the learning rate). $\\forall t, \\gamma_t > 0$;\n",
    "* $\\text{Proj}_K$ is the orthogonal projection on $K$;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "[Shapley,1953] _A value for n-person games_. Lloyd S Shapley. In Contributions to the Theory of Games, 2.28 (1953), pp. 307 - 317.\n",
    "\n",
    "[Merrick,2019] _The Explanation Game: Explaining Machine Learning Models with Cooperative Game Theory_. Luke Merrick, Ankur Taly, 2019."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Parameters__\n",
    "\n",
    "* `x`: pandas Series. The instance $\\mathbf{x^*}$ for which we want to calculate Shapley value of each attribute,\n",
    "\n",
    "* `fc`: python function. The reward function $v$,\n",
    "\n",
    "* `r`: pandas Series. The reference $\\mathbf{r}$. The Shapley values (attribute importance) is a contrastive explanation according to this individual,\n",
    "\n",
    "* `n_iter`: integer. The number of iteration, \n",
    "\n",
    "* `step`: float. Step size for the SGD algorithm,\n",
    "\n",
    "* `step_type`: string. Type of step-size learning rule. Options are: \"constant\", \"sqrt\", \"inverse\",\n",
    "\n",
    "* `callback`: optional. An python object which can be called at each iteration to record distance to minimum for example. At each iteration, callback(Φ),\n",
    "\n",
    "* `Φ_0`: numpy array or pandas Series, optional. Initial vector for the SGD algorithm.\n",
    "\n",
    "__Returns__\n",
    "\n",
    "* `Φ`: pandas Series. Shapley values of each attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "def ncr(n, r):\n",
    "    \"\"\"\n",
    "    Combinatorial computation: number of subsets of size r among n elements\n",
    "    Efficient algorithm\n",
    "    \"\"\"\n",
    "    r = min(r, n-r)\n",
    "    numer = reduce(op.mul, range(n, n-r, -1), 1)\n",
    "    denom = reduce(op.mul, range(1, r+1), 1)\n",
    "    return numer / denom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "class SGDshapley():\n",
    "    \"\"\"\n",
    "    Estimate the Shapley Values using a Projected Stochastic Gradient algorithm.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, d, C):\n",
    "        \"\"\"\n",
    "        Calculate internal values for later purposes\n",
    "        Those elements depend only on the number of features d\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        d : integer\n",
    "            Dimension of the problem. The number of features\n",
    "        \"\"\"\n",
    "\n",
    "        # Store in a dictionary for each size k of coalitions\n",
    "        dict_ω_k = dict() # weights per size k\n",
    "        dict_L_k = dict() # L-smooth constant per size k\n",
    "        D = C * np.sqrt(d)\n",
    "        for k in range(1, d):\n",
    "            ω_k = (d - 1) / (ncr(d, k) * k * (d - k))\n",
    "            L_k = ω_k * np.sqrt(k) * (np.sqrt(k) * D + C)\n",
    "            dict_ω_k.update({k: ω_k})\n",
    "            dict_L_k.update({k: L_k})\n",
    "        # Summation of all L per coalition (closed formula)\n",
    "        sum_L = np.sum([(d-1)/(np.sqrt(k)*(d-k)) * (np.sqrt(k)*D + C) for k in range(1, d)])\n",
    "        # Probability distributions for sampling new instance\n",
    "        # Classic SGD\n",
    "        p = [ncr(d,k) for k in range(1,d)]\n",
    "        p /= np.sum(p)\n",
    "        # Importance Sampling proposal q\n",
    "        q = np.array(list(dict_L_k.values())) * np.array(p)\n",
    "        q /= np.sum(q)\n",
    "\n",
    "        # Save internal attributes\n",
    "        self.d = d\n",
    "        self.n = 2**d - 2\n",
    "        self.dict_ω_k = dict_ω_k\n",
    "        self.dict_L_k = dict_L_k\n",
    "        self.sum_L = sum_L\n",
    "        self.p = p\n",
    "        self.q = q\n",
    "\n",
    "    def _F_i(self, Φ, x_i, y_i, ω_i):\n",
    "        \"\"\"Function value per instance i\"\"\"\n",
    "        res = .5 * self.n * ω_i * (np.dot(x_i, Φ) - y_i)**2\n",
    "        return res\n",
    "\n",
    "    def _grad_F_i(self, Φ, x_i, y_i, ω_i):\n",
    "        \"\"\"Gradient vector per instance i\"\"\"\n",
    "        res = ω_i * x_i[:,None].dot(x_i[None,:]).dot(Φ) - ω_i * y_i * x_i\n",
    "        return res\n",
    "\n",
    "    def _Π_1(self, x, b):\n",
    "        \"\"\"Projection Π on convex set K_1\"\"\"\n",
    "        if np.abs((np.sum(x) - b)) <= 1e-6:\n",
    "            return x\n",
    "        else:\n",
    "            return x - (np.sum(x) - b)/len(x)\n",
    "\n",
    "    def _Π_2(self, x, D):\n",
    "        \"\"\"Projection Π on convex set K_2\"\"\"\n",
    "        if np.linalg.norm(x) > D:\n",
    "            return x * D / np.linalg.norm(x)\n",
    "        else:\n",
    "            return x\n",
    "\n",
    "    def _Dykstra_proj(self, x, D, b, iter_proj=100, epsilon=1e-6):\n",
    "        \"\"\"\n",
    "        Dykstra's algorithm to find orthogonal projection\n",
    "        onto intersection of convex sets\n",
    "        \"\"\"\n",
    "        xk = x.copy()\n",
    "        d = len(x)\n",
    "        pk, qk = np.zeros(d), np.zeros(d)\n",
    "        for k in range(iter_proj):\n",
    "            yk = self._Π_2(xk + pk, D)\n",
    "            pk = xk + pk - yk\n",
    "            if np.linalg.norm(self._Π_1(yk + qk, b) - xk, 2) <= epsilon:\n",
    "                break\n",
    "            else:\n",
    "                xk = self._Π_1(yk + qk, b)\n",
    "                qk = yk + qk - xk\n",
    "        return xk\n",
    "\n",
    "    def sgd(self, x, fc, ref, n_iter=100, step=.1, step_type=\"sqrt\",\n",
    "            callback=None, Φ_0=False):\n",
    "        \"\"\"\n",
    "        Stochastic gradient descent algorithm\n",
    "        The game is defined for an element x, a reference r and function fc\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        # Get general information\n",
    "        feature_names = list(x.index)\n",
    "        f_x, f_r = fc(x.values), fc(ref.values)\n",
    "        v_M = f_x - f_r\n",
    "\n",
    "        d = self.d\n",
    "        n = 2**d - 2\n",
    "        p = self.p\n",
    "        dict_ω_k = self.dict_ω_k\n",
    "        q = self.q\n",
    "        dict_L_k = self.dict_L_k\n",
    "        sum_L = self.sum_L\n",
    "\n",
    "        # Store Shapley Values in a pandas Series\n",
    "        if Φ_0:\n",
    "            Φ = Φ_0.copy()\n",
    "        else:\n",
    "            Φ = np.zeros(d)\n",
    "        Φ_storage = np.zeros((n_iter,d))\n",
    "\n",
    "        # projection onto convex set K by using a simple algorithm\n",
    "        # Φ = self._Dykstra_proj(Φ, D, v_M, iter_proj, epsilon=1e-6)\n",
    "        Φ = Φ - (np.sum(Φ) - v_M) / d\n",
    "\n",
    "        # Sample in advance coalition sizes\n",
    "        list_k = np.random.choice(list(range(1, d)), size=n_iter, p=q)\n",
    "\n",
    "        for t in tqdm(range(1, n_iter+1)):\n",
    "            # build x_i\n",
    "            k = list_k[t-1]\n",
    "            indexes = np.random.permutation(d)[:k]\n",
    "            x_i = np.zeros(d)\n",
    "            x_i[indexes] = 1\n",
    "            # Compute y_i\n",
    "            z_S = np.array([x.values[j] if x_i[j] == 1 else ref.values[j] for j in range(d)])\n",
    "            f_S = fc(z_S)\n",
    "            y_i = f_S - f_r\n",
    "            # get weight ω_i\n",
    "            ω_i = dict_ω_k[k]\n",
    "            # calculate gradient\n",
    "            p_i = dict_L_k[k] / sum_L\n",
    "            grad_i = 1/(p_i) * self._grad_F_i(Φ, x_i, y_i, ω_i)\n",
    "            # update Φ\n",
    "            if step_type == \"constant\":\n",
    "                Φ = Φ - step * grad_i\n",
    "            elif step_type == \"sqrt\":\n",
    "                Φ = Φ - (step/np.sqrt(t)) * grad_i\n",
    "            elif step_type == \"inverse\":\n",
    "                Φ = Φ - (step/(t)) * grad_i\n",
    "\n",
    "            # projection onto convex set K\n",
    "            # Φ = self._Dykstra_proj(Φ, D, v_M, iter_proj, epsilon=1e-6)\n",
    "            Φ = Φ - (Φ.sum() - v_M) / d\n",
    "\n",
    "            # update storage of Φ\n",
    "            Φ_storage[t-1,:] = Φ\n",
    "\n",
    "            if callback and (t % d == 0):\n",
    "                callback(pd.Series(np.mean(Φ_storage[:t,:],axis=0), index=feature_names))\n",
    "\n",
    "        # Average all Φ\n",
    "        Φ = pd.Series(np.mean(Φ_storage,axis=0), index=feature_names)\n",
    "\n",
    "        return Φ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "<h4 id=\"SGDshapley.sgd\" class=\"doc_header\"><code>SGDshapley.sgd</code><a href=\"__main__.py#L88\" class=\"source_link\" style=\"float:right\">[source]</a></h4>\n",
       "\n",
       "> <code>SGDshapley.sgd</code>(**`x`**, **`fc`**, **`ref`**, **`n_iter`**=*`100`*, **`step`**=*`0.1`*, **`step_type`**=*`'sqrt'`*, **`callback`**=*`None`*, **`Φ_0`**=*`False`*)\n",
       "\n",
       "Stochastic gradient descent algorithm\n",
       "The game is defined for an element x, a reference r and function fc"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from nbdev.showdoc import *\n",
    "show_doc(SGDshapley.sgd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use a simulated dataset from the book _Elements of Statistical Learning_ ([hastie,2009], the Radial example). $X_1, \\dots , X_{d}$ are standard independent Gaussian. The model is determined by:\n",
    "\n",
    "$$ Y = \\prod_{j=1}^{d} \\rho(X_j), $$\n",
    "\n",
    "where $\\rho\\text{: } t \\rightarrow \\sqrt{(0.5 \\pi)} \\exp(- t^2 /2)$. The regression function $f_{regr}$ is deterministic and simply defined by $f_r\\text{: } \\textbf{x} \\rightarrow \\prod_{j=1}^{d} \\phi(x_j)$. For a reference $\\mathbf{r^*}$ and a target $\\mathbf{x^*}$, we define the reward function $v_r^{\\mathbf{r^*}, \\mathbf{x^*}}$ such as for each coalition $S$, $v_r^{\\mathbf{r^*}, \\mathbf{x^*}}(S) = f_{regr}(\\mathbf{z}(\\mathbf{x^*}, \\mathbf{r^*}, S)) - f_{regr}(\\mathbf{r^*}).$\n",
    "\n",
    " [hastie,2009] _The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition_. Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome. Springer Series in Statistics, 2009.\n",
    "\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dimension = 5 ; nb of coalitions = 30\n"
     ]
    }
   ],
   "source": [
    "d, n_samples = 5, 100\n",
    "mu = np.zeros(d)\n",
    "Sigma = np.zeros((d,d))\n",
    "np.fill_diagonal(Sigma, [1] * d)\n",
    "X = np.random.multivariate_normal(mean=mu, cov=Sigma, size=n_samples)\n",
    "X = pd.DataFrame(X, columns=['x'+str(i) for i in range(1, d+1)])\n",
    "def fc(x):\n",
    "    phi_x = np.sqrt(.5 * np.pi) * np.exp(-0.5 * x ** 2)\n",
    "    return np.prod(phi_x)\n",
    "y = np.zeros(len(X))\n",
    "for i in range(len(X)):\n",
    "    y[i] = fc(X.values[i])\n",
    "n = 2**d - 2\n",
    "print(\"dimension = {0} ; nb of coalitions = {1}\".format(str(d), str(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pick an individual x to explain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x1    0.144044\n",
       "x2    1.454274\n",
       "x3    0.761038\n",
       "x4    0.121675\n",
       "x5    0.443863\n",
       "Name: 2, dtype: float64"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = X.iloc[np.random.choice(len(X), size=1)[0],:]\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Single reference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x1    0.684501\n",
       "x2    0.370825\n",
       "x3    0.142062\n",
       "x4    1.519995\n",
       "x5    1.719589\n",
       "Name: 83, dtype: float64"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reference = X.iloc[np.random.choice(len(X), size=1)[0],:]\n",
    "reference"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 5000/5000 [00:00<00:00, 8277.34it/s]\n"
     ]
    }
   ],
   "source": [
    "sgd_est = SGDshapley(d, C=y.max())\n",
    "sgd_shap = sgd_est.sgd(x=x, fc=fc, ref=reference, n_iter=5000, step=.1, step_type=\"sqrt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x1    0.112323\n",
       "x2   -0.553257\n",
       "x3   -0.152112\n",
       "x4    0.528580\n",
       "x5    0.617877\n",
       "dtype: float64"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sgd_shap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hide\n",
    "from shapkit.shapley_values import ShapleyValues"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tests"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x_pred = fc(x.values)\n",
    "reference_pred = fc(reference.values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert np.abs(sgd_shap.sum() - (x_pred - reference_pred)) <= 1e-10 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 5/5 [00:00<00:00, 392.77it/s]\n"
     ]
    }
   ],
   "source": [
    "true_shap = ShapleyValues(x=x, fc=fc, ref=reference)\n",
    "assert np.linalg.norm(sgd_shap - true_shap, 2) <= 0.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Export-"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Converted index.ipynb.\n",
      "Converted inspector.ipynb.\n",
      "Converted monte_carlo_shapley.ipynb.\n",
      "Converted plots.ipynb.\n",
      "Converted sgd_shapley.ipynb.\n",
      "Converted shapley_values.ipynb.\n"
     ]
    }
   ],
   "source": [
    "#hide\n",
    "from nbdev.export import notebook2script\n",
    "notebook2script()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}