notebooks/bayesian-network-basics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bayesian Network: Basics\n",
    "\n",
    "---\n",
    "\n",
    "**Bayesian (belief) network** is a very powerful model to represent the uncertainty in the world, including the **dependencies** between different random variables (events) in the real world, and the corresponding **(conditional) probabilities**.\n",
    "\n",
    "Bayesian network has a number of **advantages** for representing knowledge about an uncertain \"world\".\n",
    "\n",
    "- The model encodes dependencies among all variables, it readily **handles situations where some data entries are missing**.\n",
    "- A Bayesian network can be used to learn causal relationships, and hence can be used to **gain understanding about a problem** and to **predict the consequences of intervention**. \n",
    "- The model has both a causal and probabilistic semantics, it is an ideal representation for **combining prior knowledge** (which often comes in causal form) and data. \n",
    "- Bayesian statistical methods in conjunction with Bayesian networks offer an efficient and principled approach for **avoiding overfitting to data**.\n",
    "\n",
    "In this tutorial, we will introduce the basics of Bayesian network."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The \"Alarm World\"\n",
    "\n",
    "---\n",
    "\n",
    "Let us consider the following \"*alarm world*\": you installed an **alarm** system in your house against **burglary**. However, New Zealand frequently has **earthquakes**, and the alarm system can be occasionally set off by an earthquake as well. In addition, the alarm can be set off by mistake with a very small probability. You have two neighbours, **John** and **Mary**. They might call you if they hear the alarm from your house while you are away. On the other hand, they might still call you for other issues even if they do not hear the alarm. However, they do not know each other, thus they will not communicate with each other about calling you.\n",
    "\n",
    "<img src=\"img/alarm.png\" width=300></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random Variables\n",
    "\n",
    "---\n",
    "\n",
    "In this \"alarm world\", there are five binary **random variables**.\n",
    "\n",
    "- $B$: Whether a **b**urglar breaks into the house or not.\n",
    "- $E$: Whether there is an **e**arthquake or not.\n",
    "- $A$: Whether the **a**larm is set off or not.\n",
    "- $J$: Whether your neighbour **J**ohn calls you or not.\n",
    "- $M$: Whether your neighbour **M**ary calls you or not."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Causal Dependencies\n",
    "\n",
    "---\n",
    "\n",
    "From domain knowledge, we have the following **causal dependencies** between the random variables.\n",
    "\n",
    "- The alarm can be set off by a burglar.\n",
    "- The alarm can be set off by an earthquake.\n",
    "- Whether a burglar breaks into the house is independent from whether there is an earthquake.\n",
    "- John might call you if they hear the alarm.\n",
    "- Mary might call you if they hear the alarm.\n",
    "- Since John and Mary do not communicate, **given the alarm condition**, whether John calls is independent from whether Mary calls."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Directed Acyclic Graph\n",
    "\n",
    "---\n",
    "\n",
    "Based on the above domain knowledge, we can represent the random variables in the alarm world and their (in)dependencies by the following **Directed Acyclic Graph (DAG)**. \n",
    "\n",
    "<img src=\"img/alarm-dag.png\" width=150></img>\n",
    "\n",
    "We can see that each **node** represents a random variable, and each **directed edge** represents a causal dependency between the variables. For example, the directed edge $(B, A)$ means that the burglary variable is a cause of the alarm variable, and the alarm variable is an effect of the burglary variable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (Conditional) Probabilities\n",
    "\n",
    "---\n",
    "\n",
    "The causal dependencies are qualitative. For quantitative reasoning, we need the (conditional) probabilities for each random variable in the DAG.\n",
    "\n",
    "Again, from domain knowledge, we have the following probabilities.\n",
    "\n",
    "- A burglar breaks into the house with probability of 0.1%.\n",
    "- The probability of an earthquake is 0.2%.\n",
    "- If there were both a burglar and an earthquake, the alarm is set off with probability of 95%.\n",
    "- If there was a burglar but no earthquake, the alarm is set off with probability of 94%.\n",
    "- If there was no burglar and an earthquake, the alarm is set off with probability of 29%.\n",
    "- If there was no burglar and no earthquake, the alarm is set off by mistake with probability of 0.1%.\n",
    "- If the alarm is set off, John will hear it and call you with probability of 90%.\n",
    "- If the alarm is not set off, John will call you for other issues with probability of 5%.\n",
    "- If the alarm is set off, Mary will hear it and call you with probability of 70%.\n",
    "- If the alarm is not set off, Mary will call you for other issues with probability of 1%."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the above probabilities, we can have the following **Bayesian network** for the alarm world.\n",
    "\n",
    "<img src=\"img/alarm-bn.png\" width=500></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the above example, we can see that to define a Bayesian network, we need to define\n",
    "\n",
    "1. A **Directed Acyclic Graph (DAG)**, where each **node** represents a **random variable** in the world, and each **directed edge** represents a **causal dependency** between two random variables\n",
    "2. A **Conditional Probability Table (CPT)** for each node $X$ in the graph. The conditional probabilities are $P(X\\ |\\ parents(X))$, where $parents(X)$ are the parents (incoming neighbours) of $X$ in the graph. They are direct causes of $X$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (In)dependencies <a name=\"dependency\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "An important task in a Bayesian network is to identify the **(in)dependencies** between any pair of random variables in the network. In general, there are four types of common (in)dependencies between variables.\n",
    "\n",
    "<img src=\"img/cause-effect.png\" width=550></img>\n",
    "\n",
    "- **Direct Cause**: $A$ is a direct cause of $B$, if $A$ is an incoming neighbour of $B$. Obviously we have\n",
    "    - $A$ **and $B$ are <span style=\"color: red;\">dependent</span>**.\n",
    "- **Indirect Cause**: $A$ is an indirected cause of $C$, if there is a directed path from $A$ to $C$. In the above 3-node example, the directed path is $A \\rightarrow B \\rightarrow C$. We have \n",
    "    - $A$ **and $C$ are conditionally <span style=\"color: blue;\">independent</span> given $B$**. This is obvious, since if the direct cause is given, then the indirect cause is not needed.\n",
    "- **Common Cause**: $B$ and $C$ have the common cause $A$, and they are not direct cause of each other. We have\n",
    "    - $B$ **and $C$ are conditionally <span style=\"color: blue;\">independent</span> given $A$**.\n",
    "    - $B$ **and $C$ are <span style=\"color: red;\">dependent</span> with each other if $A$ is not given**. This is because if $A$ is not given, then the probability of $A$ is dependent on $B$ (or $C$), which in turn changes the probability of $C$ (or $B$).\n",
    "- **Common Effect**: $A$ and $B$ have the common effect $C$, and they are not direct cause of each other. We have\n",
    "    - $A$ **and $B$ are <span style=\"color: blue;\">independent</span>** ($C$ is not given).\n",
    "    - $A$ **and $B$ are conditionally <span style=\"color: red;\">dependent</span> given $C$**. This is also called \"explaining away\". Since both $A$ and $B$ are the causes of $C$, if $C$ is given, either $A$ or $B$ can be the cause. Thus, one cause can \"explain away\" the other. For example, in the alarm network, both burglary and earthquake are the causes of the alarm. Given that the alarm is set off, if we know that there is a burglary, then there is no need to require earthquake to set off the alarm, and the conditional probability of earthquake is reduced. On the other hand, if we know that there is no burglary, then earthquake becomes the main cause of the alarm, and its conditional probability must be very high."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Independencies in the Alarm Network\n",
    "\n",
    "<img src=\"img/alarm-dag.png\" width=150></img>\n",
    "\n",
    "In the above alarm network, we can find the following independencies:\n",
    "\n",
    "- $B$ and $E$ are independent\n",
    "- $B$ and $J$ are conditionally independent given $A$ (indirect cause)\n",
    "- $B$ and $M$ are conditionally independent given $A$ (indirect cause)\n",
    "- $E$ and $J$ are conditionally independent given $A$ (indirect cause)\n",
    "- $E$ and $M$ are conditionally independent given $A$ (indirect cause)\n",
    "- $J$ and $M$ are conditionally independent given $A$ (common cause)\n",
    "\n",
    "> **NOTE**: $B$ and $E$ will become <span style=\"color: red;\">dependent</span> if $A$ is given, due to common effect $A$ (explaining away)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Factorisation <a name=\"factorisation\"></a>\n",
    "\n",
    "---\n",
    "\n",
    "The independencies in a Bayesian network can be summarised as follows.\n",
    "\n",
    "> **THEOREM**: In a Bayesian network, a node is conditionally independent from **all the nodes except its direct effects**, if the **direct causes are all given**, and **no direct effect is given**.\n",
    "\n",
    "**Proof**\n",
    "\n",
    "1. Given all the direct causes, a node is conditionally independent from all its indirect causes, as well as any other cause/effect node extended from its indirect causes.\n",
    "2. Given all the direct causes, a node is conditionally independent from all the direct effects of its direct causes (common cause), as well as any other cause/effect node extended from them.\n",
    "3. If no direct effect is given, then a node is conditionally independent from the direct cause of its direct effect (common effect), as well as any other cause/effect node extended from them.\n",
    "4. There is no other node than the above categories.\n",
    "\n",
    "<p style=\"text-align: right\"> $\\blacksquare$ </p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a Bayesian network with the nodes $\\{X_1, \\dots, X_n\\}$. We can have the following theorem.\n",
    "\n",
    "> **THEOREM**: If the order of $\\{X_1, \\dots, X_n\\}$ is consistent with the nodes in the directed acyclic graph, i.e., for each node $X_i$, no direct effect of $X_i$ is before it, then each node $X_i$ is conditionally independent from all the nodes in $\\{X_1, \\dots, X_{i-1}\\}$ except its direct cause, if all its direct causes are given.\n",
    "\n",
    "**Proof**\n",
    "\n",
    "- First, from the order of the nodes in the network, we have that **all the directed causes of $X_i$ are in $\\{X_1, \\dots, X_{i-1}\\}$**. Otherwise, if a direct cause of $X_i$ is outside $\\{X_1, \\dots, X_{i-1}\\}$, there must be a directed path from outside $\\{X_1, \\dots, X_{i-1}\\}$ to $X_i$, which contradicts the order of the nodes.\n",
    "- Second, the node order already tells that no direct effect of $X_i$ is in $\\{X_1, \\dots, X_{i-1}\\}$. In other words, **no direct effect of $X_i$ is given in $\\{X_1, \\dots, X_{i-1}\\}$**.\n",
    "\n",
    "Therefore, from the first theorem, we know that each node $X_i$ is conditionally independent from all the nodes in $\\{X_1, \\dots, X_{i-1}\\}$ except its direct cause, if all its direct causes are given.\n",
    "\n",
    "<p style=\"text-align: right\"> $\\blacksquare$ </p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above theorem can be written as\n",
    "\n",
    "$$\n",
    "P(X_i\\ |\\ X_1, \\dots, X_{i-1}) = P(X_i\\ |\\ parents(X_i)).\n",
    "$$\n",
    "\n",
    "On the other hand, from the chain (product) rule, we have \n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(X_1, \\dots, X_n) \\\\\n",
    "& = P(X_1) * P(X_2\\ |\\ X_1) * \\dots * P(X_n\\ |\\ X_1, \\dots, X_{n-1}).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Therefore, the Bayesian network can be written as the following **factorisation** of joint probability distribution.\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(X_1, \\dots, X_n) \\\\\n",
    "& = P(X_1\\ |\\ parents(X_1)) \\dots * P(X_n\\ |\\ parents(X_n)).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "For example, in the alarm network, the factorisation is\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "& P(B, E, A, J, M) \\\\\n",
    "& = P(B) * P(E) * P(A\\ |\\ B, E) * P(J\\ |\\ A) * P(M\\ |\\ A).\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "> **NOTE**: The factorisation of the joint probability distribution is equivelant to the representation of previous graph + probability tables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "- More tutorials can be found [here](https://github.com/meiyi1986/tutorials).\n",
    "- [Yi Mei's homepage](https://meiyi1986.github.io/)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyMUhVpwLgftmeLtOZUU/BvG",
   "name": "murderer-bn.ipynb",
   "provenance": []
  },
  "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.9.6"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "0e1a5c69cfed4342892752d5b4131c2d": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "DescriptionStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "DescriptionStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "description_width": ""
     }
    },
    "211ec25b1db34e999c1bc53329d42f44": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "2e0959ce50f744d9ac8a801878f29c99": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "DescriptionStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "DescriptionStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "description_width": ""
     }
    },
    "30dfd17e6f1f4bbd9cefdbbb92cb4958": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "DescriptionStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "DescriptionStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "description_width": ""
     }
    },
    "3c120f9e3aeb46119d12f74ac1035992": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "FloatProgressModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "FloatProgressModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "ProgressView",
      "bar_style": "success",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_6557561de25f435190bc75158f6b5064",
      "max": 2,
      "min": 0,
      "orientation": "horizontal",
      "style": "IPY_MODEL_44df7ae731d848d894bc5c1c6d1c1b19",
      "value": 2
     }
    },
    "44df7ae731d848d894bc5c1c6d1c1b19": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "ProgressStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "ProgressStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "bar_color": null,
      "description_width": ""
     }
    },
    "4ed92c6ebfad491dbb7838cf9040f789": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "FloatProgressModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "FloatProgressModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "ProgressView",
      "bar_style": "success",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_211ec25b1db34e999c1bc53329d42f44",
      "max": 2,
      "min": 0,
      "orientation": "horizontal",
      "style": "IPY_MODEL_d27706f35c334b51ad555598e9a261ef",
      "value": 2
     }
    },
    "4eeaa192b99849988659547ed6f8a17b": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HBoxModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HBoxModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HBoxView",
      "box_style": "",
      "children": [
       "IPY_MODEL_ebbedb522c874b79a1095af4963bd976",
       "IPY_MODEL_3c120f9e3aeb46119d12f74ac1035992",
       "IPY_MODEL_5f75346373df4a13a6fb38f557b8d259"
      ],
      "layout": "IPY_MODEL_e0ba45aac28749c7a189293ca73dc51b"
     }
    },
    "50331471295a4a40934016b913fb515b": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "53ce67001ef5424696addd3eaf8de144": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HTMLModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HTMLModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HTMLView",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_a39141612b074880aa5637c8cafeaefa",
      "placeholder": "​",
      "style": "IPY_MODEL_30dfd17e6f1f4bbd9cefdbbb92cb4958",
      "value": "Eliminating: Weapon: 100%"
     }
    },
    "5f75346373df4a13a6fb38f557b8d259": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HTMLModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HTMLModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HTMLView",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_7a797eefb0fd4a1787240a9fb24cd338",
      "placeholder": "​",
      "style": "IPY_MODEL_2e0959ce50f744d9ac8a801878f29c99",
      "value": " 2/2 [27:43&lt;00:00, 831.94s/it]"
     }
    },
    "6557561de25f435190bc75158f6b5064": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "7a1a9a0fad754286bffa70151701f414": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "7a797eefb0fd4a1787240a9fb24cd338": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "865d602624a641b984c01a84e2a6bd49": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HBoxModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HBoxModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HBoxView",
      "box_style": "",
      "children": [
       "IPY_MODEL_53ce67001ef5424696addd3eaf8de144",
       "IPY_MODEL_4ed92c6ebfad491dbb7838cf9040f789",
       "IPY_MODEL_fd119f513d5d4433a211898cec4e374b"
      ],
      "layout": "IPY_MODEL_87939cd8df4f4a45b553df2b37f4524b"
     }
    },
    "87939cd8df4f4a45b553df2b37f4524b": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "8b33c262861e433286b8a3601aaa8391": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "DescriptionStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "DescriptionStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "description_width": ""
     }
    },
    "a39141612b074880aa5637c8cafeaefa": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "d27706f35c334b51ad555598e9a261ef": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "ProgressStyleModel",
     "state": {
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "ProgressStyleModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "StyleView",
      "bar_color": null,
      "description_width": ""
     }
    },
    "e0ba45aac28749c7a189293ca73dc51b": {
     "model_module": "@jupyter-widgets/base",
     "model_module_version": "1.2.0",
     "model_name": "LayoutModel",
     "state": {
      "_model_module": "@jupyter-widgets/base",
      "_model_module_version": "1.2.0",
      "_model_name": "LayoutModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/base",
      "_view_module_version": "1.2.0",
      "_view_name": "LayoutView",
      "align_content": null,
      "align_items": null,
      "align_self": null,
      "border": null,
      "bottom": null,
      "display": null,
      "flex": null,
      "flex_flow": null,
      "grid_area": null,
      "grid_auto_columns": null,
      "grid_auto_flow": null,
      "grid_auto_rows": null,
      "grid_column": null,
      "grid_gap": null,
      "grid_row": null,
      "grid_template_areas": null,
      "grid_template_columns": null,
      "grid_template_rows": null,
      "height": null,
      "justify_content": null,
      "justify_items": null,
      "left": null,
      "margin": null,
      "max_height": null,
      "max_width": null,
      "min_height": null,
      "min_width": null,
      "object_fit": null,
      "object_position": null,
      "order": null,
      "overflow": null,
      "overflow_x": null,
      "overflow_y": null,
      "padding": null,
      "right": null,
      "top": null,
      "visibility": null,
      "width": null
     }
    },
    "ebbedb522c874b79a1095af4963bd976": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HTMLModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HTMLModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HTMLView",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_50331471295a4a40934016b913fb515b",
      "placeholder": "​",
      "style": "IPY_MODEL_8b33c262861e433286b8a3601aaa8391",
      "value": "Finding Elimination Order: : 100%"
     }
    },
    "fd119f513d5d4433a211898cec4e374b": {
     "model_module": "@jupyter-widgets/controls",
     "model_module_version": "1.5.0",
     "model_name": "HTMLModel",
     "state": {
      "_dom_classes": [],
      "_model_module": "@jupyter-widgets/controls",
      "_model_module_version": "1.5.0",
      "_model_name": "HTMLModel",
      "_view_count": null,
      "_view_module": "@jupyter-widgets/controls",
      "_view_module_version": "1.5.0",
      "_view_name": "HTMLView",
      "description": "",
      "description_tooltip": null,
      "layout": "IPY_MODEL_7a1a9a0fad754286bffa70151701f414",
      "placeholder": "​",
      "style": "IPY_MODEL_0e1a5c69cfed4342892752d5b4131c2d",
      "value": " 2/2 [00:00&lt;00:00, 37.07it/s]"
     }
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}