notebooks/FastTreeSHAP_Crop_Mapping.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0a98a119",
   "metadata": {},
   "source": [
    "# FastTreeSHAP in Crop Mapping Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9abc80a5",
   "metadata": {},
   "source": [
    "This notebook contains usages and detailed comparisons of FastTreeSHAP v1, FastTreeSHAP v2 and the original TreeSHAP in **multiclass classification** problems using scikit-learn, XGBoost and LightGBM. It may take a few minutes to run through all code in this notebook. The source of crop mapping data is https://archive.ics.uci.edu/ml/datasets/Crop+mapping+using+fused+optical-radar+data+set."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc30314c",
   "metadata": {},
   "source": [
    "## Load Python libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8fdb2cf3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.metrics import roc_auc_score, accuracy_score\n",
    "import xgboost as xgb\n",
    "import lightgbm as lgb\n",
    "import fasttreeshap\n",
    "import os\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a19a83ac",
   "metadata": {},
   "source": [
    "## Pre-process training and testing data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7c93f44",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run the following statement if download the dataset directly from\n",
    "# https://archive.ics.uci.edu/ml/datasets/Crop+mapping+using+fused+optical-radar+data+set\n",
    "#data = pd.read_csv(\"WinnipegDataset.txt\", sep = \",\", engine = \"python\")\n",
    "#data, _ = train_test_split(data, test_size = 0.9, random_state = 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a797955e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# source of data: https://archive.ics.uci.edu/ml/datasets/Crop+mapping+using+fused+optical-radar+data+set\n",
    "data = pd.read_csv(\"../data/crop_train.csv\")\n",
    "train, test = train_test_split(data, test_size = 0.33, random_state = 0)\n",
    "label_train = train[\"label\"] - 1\n",
    "label_test = test[\"label\"] - 1\n",
    "train = train.iloc[:, 1:]\n",
    "test = test.iloc[:, 1:]\n",
    "print(\"Training data has {} rows and {} columns.\".format(train.shape[0], train.shape[1])) \n",
    "print(\"Testing data has {} rows and {} columns.\".format(test.shape[0], test.shape[1])) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "255f4b25",
   "metadata": {},
   "source": [
    "## Train a random forest model using scikit-learn and compute SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d119eae",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_estimators = 200  # number of trees in random forest model\n",
    "max_depth = 8  # maximum depth of any trees in random forest model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6298c1e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# train a random forest model\n",
    "rf_model = RandomForestClassifier(n_estimators = n_estimators, max_depth = max_depth, random_state = 0)\n",
    "rf_model.fit(train, label_train)\n",
    "print(\"Accuracy on testing set is {:.2f}.\".format(accuracy_score(label_test, rf_model.predict(test))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e6b1fcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# obtain total number of leaves\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model)\n",
    "num_leaves = sum(shap_explainer.model.num_nodes) - sum(sum(shap_explainer.model.children_left > 0))\n",
    "print(\"Total number of leaves is {}.\".format(num_leaves))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86d1737d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate memory usage of FastTreeSHAP v2 since FastTreeSHAP v2 has a stricter memory constraint than\n",
    "# TreeSHAP and FastTreeSHAP v1\n",
    "# derivation of the memory estimation can be found in Deep Dive Section in FastTreeSHAP_Census_Income notebook\n",
    "def memory_estimate_v2(shap_explainer, num_sample, num_feature, n_jobs):\n",
    "    max_node = max(shap_explainer.model.num_nodes)\n",
    "    max_leaves = (max_node + 1) // 2\n",
    "    max_combinations = 2**int(shap_explainer.model.max_depth)\n",
    "    phi_dim = num_sample * (num_feature + 1) * shap_explainer.model.num_outputs\n",
    "    n_jobs = os.cpu_count() if n_jobs == -1 else n_jobs\n",
    "    memory_1 = (max_leaves * max_combinations + phi_dim) * 8 * n_jobs\n",
    "    memory_2 = max_leaves * max_combinations * shap_explainer.model.values.shape[0] * 8\n",
    "    memory = min(memory_1, memory_2)\n",
    "    if memory < 1024:\n",
    "        print(\"Memory usage of FastTreeSHAP v2 is around {:.2f}B.\".format(memory))\n",
    "    elif memory / 1024 < 1024:\n",
    "        print(\"Memory usage of FastTreeSHAP v2 is around {:.2f}KB.\".format(memory / 1024))\n",
    "    elif memory / 1024**2 < 1024:\n",
    "        print(\"Memory usage of FastTreeSHAP v2 is around {:.2f}MB.\".format(memory / 1024**2))\n",
    "    else:\n",
    "        print(\"Memory usage of FastTreeSHAP v2 is around {:.2f}GB.\".format(memory / 1024**3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "180cc84f",
   "metadata": {},
   "source": [
    "### Compute SHAP values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9df6fd5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "080cebb6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v0 (i.e., original TreeSHAP)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"v0\", n_jobs = n_jobs)\n",
    "shap_values_v0 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4ab3768e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"v1\", n_jobs = n_jobs)\n",
    "shap_values_v1 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c2fd56f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v1 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf8239e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate memory usage of FastTreeSHAP v2 since FastTreeSHAP v2 has a stricter memory constraint than\n",
    "# TreeSHAP and FastTreeSHAP v1\n",
    "memory_estimate_v2(shap_explainer, num_sample, test.shape[1], n_jobs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5db81218",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v2\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"v2\", n_jobs = n_jobs)\n",
    "shap_values_v2 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v2.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28fd6ee6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v2\n",
    "print(\"Maximum difference of SHAP values between v2 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v2 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3a51d5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via automatic TreeSHAP algorithm selection\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"auto\", n_jobs = n_jobs)\n",
    "shap_values_auto = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e31a304",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_auto - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab1a6abf",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f56c511",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values/SHAP interaction values via TreeSHAP algorithm with version \"algorithm_version\"\n",
    "# (parallel on \"n_jobs\" threads)\n",
    "def run_fasttreeshap(model, sample, interactions, algorithm_version, n_jobs, num_round, num_sample, shortcut = False):\n",
    "    shap_explainer = fasttreeshap.TreeExplainer(\n",
    "        model, algorithm = algorithm_version, n_jobs = n_jobs, shortcut = shortcut)\n",
    "    run_time = np.zeros(num_round)\n",
    "    for i in range(num_round):\n",
    "        start = time.time()\n",
    "        shap_values = shap_explainer(sample.iloc[:num_sample], interactions = interactions).values\n",
    "        run_time[i] = time.time() - start\n",
    "        print(\"Round {} takes {:.3f} sec.\".format(i + 1, run_time[i]))\n",
    "    print(\"Average running time of {} is {:.3f} sec (std {:.3f} sec){}.\".format(\n",
    "        algorithm_version, np.mean(run_time), np.std(run_time), \" (with shortcut)\" if shortcut else \"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6ac6c62",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e355f016",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = False, algorithm_version = \"v0\", n_jobs = n_jobs,\n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b3fdcab",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = False, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f332040",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v2 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = False, algorithm_version = \"v2\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1dacd00a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = False, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b89ceda2",
   "metadata": {},
   "source": [
    "### Compute SHAP interaction values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67f6c5d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f7fbbecc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v0 (i.e., original TreeSHAP)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"v0\", n_jobs = n_jobs)\n",
    "shap_interaction_values_v0 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92fd067a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"v1\", n_jobs = n_jobs)\n",
    "shap_interaction_values_v1 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "de04358a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP interaction values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_v1 - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c6947ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via automatic TreeSHAP algorithm selection\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "shap_explainer = fasttreeshap.TreeExplainer(rf_model, algorithm = \"auto\", n_jobs = n_jobs)\n",
    "shap_interaction_values_auto = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7175c995",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP interaction values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_auto - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcacc325",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP interaction values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "397e1d0d",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14095298",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = True, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1040daa8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = True, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9bb34071",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "run_fasttreeshap(\n",
    "    model = rf_model, sample = test, interactions = True, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5ed3061",
   "metadata": {},
   "source": [
    "## Train an XGBoost model and compute SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5583b19",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_estimators = 200  # number of trees in XGBoost model\n",
    "max_depth = 8  # maximum depth of any trees in XGBoost model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a17c354",
   "metadata": {},
   "outputs": [],
   "source": [
    "# train an XGBoost model\n",
    "xgb_model = xgb.XGBClassifier(\n",
    "    max_depth = max_depth, n_estimators = n_estimators, learning_rate = 0.1, n_jobs = -1,\n",
    "    use_label_encoder = False, eval_metric = \"logloss\", random_state = 0)\n",
    "xgb_model.fit(train, label_train)\n",
    "print(\"Accuracy on testing set is {:.2f}.\".format(accuracy_score(label_test, xgb_model.predict(test))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41c05894",
   "metadata": {},
   "outputs": [],
   "source": [
    "# obtain total number of leaves\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model)\n",
    "num_leaves = sum(shap_explainer.model.num_nodes) - sum(sum(shap_explainer.model.children_left > 0))\n",
    "print(\"Total number of leaves is {}.\".format(num_leaves))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c14575fc",
   "metadata": {},
   "source": [
    "### Compute SHAP values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8278d3fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc84aa67",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via \"shortcut\" (i.e., original TreeSHAP in XGBoost package)\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = True)\n",
    "shap_values_shortcut = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_shortcut.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e49f3ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v0 (i.e., original TreeSHAP in SHAP package)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v0 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f403b44d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v0\n",
    "print(\"Mean and maximum differences of SHAP values between v0 and shortcut is {:.2e} and {:.2e}.\".format(\n",
    "    np.mean(abs(shap_values_v0 - shap_values_shortcut)), np.max(abs(shap_values_v0 - shap_values_shortcut))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28f4b23c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v1\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v1 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e4f2fad",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v1 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "665e0324",
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate memory usage of FastTreeSHAP v2 since FastTreeSHAP v2 has a stricter memory constraint than\n",
    "# TreeSHAP and FastTreeSHAP v1\n",
    "memory_estimate_v2(shap_explainer, num_sample, test.shape[1], n_jobs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44cb6113",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v2\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v2\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v2 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v2.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2dbbf1f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v2\n",
    "print(\"Maximum difference of SHAP values between v2 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v2 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8645a3d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via automatic TreeSHAP algorithm selection\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"auto\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_auto = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56e45b01",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_auto - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7a1a94c",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3a1c6994",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b5ea273",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run \"shortcut\" version of TreeSHAP multiple times and record its average running time\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = False, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5d4925d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = False, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20a63c39",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = False, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "50b6354e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v2 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = False, algorithm_version = \"v2\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3fc0971",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = False, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0a99bca",
   "metadata": {},
   "source": [
    "### Compute SHAP interaction values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d756f176",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2a72ad79",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via \"shortcut\" (i.e., original TreeSHAP in XGBoost package)\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = True)\n",
    "shap_interaction_values_shortcut = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_shortcut.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "45828180",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v0 (i.e., original TreeSHAP in SHAP package)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_v0 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4e4737b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v0\n",
    "print(\"Mean and maximum differences of SHAP values between v0 and shortcut is {:.2e} and {:.2e}.\".format(\n",
    "    np.mean(abs(shap_interaction_values_v0 - shap_interaction_values_shortcut)), \n",
    "    np.max(abs(shap_interaction_values_v0 - shap_interaction_values_shortcut))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "993e5edc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"v1\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_v1 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b11e86a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP interaction values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_v1 - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aaec20a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via automatic TreeSHAP algorithm selection\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "shap_explainer = fasttreeshap.TreeExplainer(xgb_model, algorithm = \"auto\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_auto = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fad3527",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP interaction values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_auto - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e6099a3",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP interaction values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4fe7457f",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1265acac",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run \"shortcut\" version of TreeSHAP multiple times and record its average running time\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = True, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0dc837d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = True, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d4ceae74",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = True, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9fbd2c4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "run_fasttreeshap(\n",
    "    model = xgb_model, sample = test, interactions = True, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "912dcb57",
   "metadata": {},
   "source": [
    "## Train a LightGBM model and compute SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b8078b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_estimators = 500  # number of trees in LightGBM model\n",
    "max_depth = 8  # maximum depth of any trees in LightGBM model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40f38b7f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# train a LightGBM model\n",
    "lgb_model = lgb.LGBMClassifier(\n",
    "    max_depth = max_depth, n_estimators = n_estimators, learning_rate = 0.1, n_jobs = -1, random_state = 0)\n",
    "lgb_model.fit(train, label_train)\n",
    "print(\"Accuracy on testing set is {:.2f}.\".format(accuracy_score(label_test, lgb_model.predict(test))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2181658c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# obtain total number of leaves\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model)\n",
    "num_leaves = sum(shap_explainer.model.num_nodes) - sum(sum(shap_explainer.model.children_left > 0))\n",
    "print(\"Total number of leaves is {}.\".format(num_leaves))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8414fe5c",
   "metadata": {},
   "source": [
    "### Compute SHAP values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "479e6a2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c320f798",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via \"shortcut\" (i.e., original TreeSHAP in LightGBM package)\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = True)\n",
    "shap_values_shortcut = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_shortcut.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6f64812",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v0 (i.e., original TreeSHAP in SHAP package)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v0 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5aa50b06",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v0\n",
    "print(\"Mean and maximum differences of SHAP values between v0 and shortcut is {:.2e} and {:.2e}.\".format(\n",
    "    np.mean(abs(shap_values_v0 - shap_values_shortcut)), np.max(abs(shap_values_v0 - shap_values_shortcut))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cd75d55e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v1\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v1 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e6fbfab",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v1 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbcaf524",
   "metadata": {},
   "outputs": [],
   "source": [
    "# estimate memory usage of FastTreeSHAP v2 since FastTreeSHAP v2 has a stricter memory constraint than\n",
    "# TreeSHAP and FastTreeSHAP v1\n",
    "memory_estimate_v2(shap_explainer, num_sample, test.shape[1], n_jobs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5996f51d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via FastTreeSHAP v2\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v2\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_v2 = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_v2.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cde624e7",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v2\n",
    "print(\"Maximum difference of SHAP values between v2 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_v2 - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "718a48ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP values via automatic TreeSHAP algorithm selection\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"auto\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_values_auto = shap_explainer(test.iloc[:num_sample]).values\n",
    "shap_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0d296d3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_values_auto - shap_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2a50cef",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d896056",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 10000  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1678a471",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run \"shortcut\" version of TreeSHAP multiple times and record its average running time\n",
    "# by default, parallel computing on all available cores is enabled in \"shortcut\"\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = False, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c5578112",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = False, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d67857f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = False, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "240ec8b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v2 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = False, algorithm_version = \"v2\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6cf33aa8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# it turns out that \"auto\" selects \"v2\" as the most appropriate TreeSHAP algorithm\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = False, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "822267fd",
   "metadata": {},
   "source": [
    "### Compute SHAP interaction values via different versions of TreeSHAP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2ad061c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97552a93",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v0 (i.e., original TreeSHAP in SHAP package)\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "# \"shortcut\" of SHAP interaction values is not enabled for LightGBM in SHAP package\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v0\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_v0 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v0.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b3f5e5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via FastTreeSHAP v1\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"v1\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_v1 = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_v1.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "460f60ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of FastTreeSHAP v1\n",
    "print(\"Maximum difference of SHAP interaction values between v1 and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_v1 - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "446f553d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute SHAP interaction values via automatic TreeSHAP algorithm selection\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "shap_explainer = fasttreeshap.TreeExplainer(lgb_model, algorithm = \"auto\", n_jobs = n_jobs, shortcut = False)\n",
    "shap_interaction_values_auto = shap_explainer(test.iloc[:num_sample], interactions = True).values\n",
    "shap_interaction_values_auto.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9155abb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# justify the correctness of automatically selected TreeSHAP algorithm\n",
    "print(\"Maximum difference of SHAP interaction values between auto and v0 is {:.2e}.\".format(\n",
    "    np.max(abs(shap_interaction_values_auto - shap_interaction_values_v0))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b657a84",
   "metadata": {},
   "source": [
    "### Compare running times of different versions of TreeSHAP in computing SHAP interaction values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5da08cba",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_sample = 100  # number of samples to be explained\n",
    "num_round = 3  # number of rounds to record mean and standard deviation of running time\n",
    "n_jobs = -1  # number of parallel threads (-1 means utilizing all available cores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0eff8c4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v0 (i.e., original TreeSHAP) multiple times and record its average running time\n",
    "# parallel computing is not enabled in original TreeSHAP in SHAP package, but here we enable it for a fair comparison\n",
    "# on execution time\n",
    "# \"shortcut\" of SHAP interaction values is not enabled for LightGBM in SHAP package\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = True, algorithm_version = \"v0\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61888328",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run FastTreeSHAP v1 multiple times and record its average running time\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = True, algorithm_version = \"v1\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60aaf781",
   "metadata": {},
   "outputs": [],
   "source": [
    "# run automatically selected TreeSHAP algorithm multiple times and record its average running time\n",
    "# v1 is always preferred to v0 in any use cases, and v2 does not support interactions\n",
    "run_fasttreeshap(\n",
    "    model = lgb_model, sample = test, interactions = True, algorithm_version = \"auto\", n_jobs = n_jobs, \n",
    "    num_round = num_round, num_sample = num_sample, shortcut = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4cf393b7",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}