PGM.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kmouts/PMS/blob/master/PGM.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6CzU89Q914Te"
      },
      "outputs": [],
      "source": [
        "from IPython.display import Image"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_O1NFcG714Tc"
      },
      "source": [
        "# Introduction to Probabilistic Graphical Models & Bayesian Networks"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bEDMYiUt14Tg"
      },
      "source": [
        "Contents\n",
        "--------\n",
        "1. Lets start with some data\n",
        "2. Different ways of learning from data\n",
        "3. Why probabilistic graphical models\n",
        "4. Major types of PGMs\n",
        "5. What are Bayesian Models\n",
        "6. Independencies in Bayesian Networks\n",
        "7. How is Bayesian Model encoding the Join Distribution\n",
        "8. How we do inference from Bayesian models\n",
        "9. Types of methods of inference\n",
        "10. Loading example models\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The naive Bayes algorithm, a fast and simple modeling technique used in classification problems, has been widely used because of its speed and relatively good performance. However, it is based on the assumption that all variables (model features) are independent, which is often not true.\n",
        "\n",
        "In some cases, it may be necessary to build a model specifying dependent, independent, or conditionally independent variables. In addition, it may be useful to track in real time how event probabilities change when new evidence is added to the model.\n",
        "\n",
        "The **Bayesian Belief Network** is useful because it allows you to construct a model with nodes and directed edges by clearly defining the relationships between variables.\n",
        "\n"
      ],
      "metadata": {
        "id": "lmWNz8xHev0k"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QuQSYueC14Tg"
      },
      "source": [
        "### 1. Lets start with some data\n",
        "\n",
        "We can take an example of predicting the type of flower based on the sepal length and width of the flower. Let's say we have some data (discretized iris data set on sepal length and width). The dataset looks something like this:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "qs7nV6oo14Tg"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "from sklearn.datasets import load_iris\n",
        "\n",
        "iris = load_iris()\n",
        "mini_iris = np.round(iris.data[:, :2]).astype(int)\n",
        "data = pd.DataFrame(mini_iris, columns=['length', 'width'])\n",
        "data['type'] = iris.target\n",
        "\n",
        "np.random.seed(10)\n",
        "\n",
        "#Shuffle data\n",
        "data = data.iloc[np.random.permutation(len(data))]\n",
        "data"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3hEooWzI14Th"
      },
      "source": [
        "### 2. Different ways of learning from data\n",
        "\n",
        "Now let's say we want to predict the type of flower for a new given data point. There are multiple ways to solve this problem. We will consider these two ways in some detail:  \n",
        "\n",
        "1. We could find a function which can directly map an input value to it's class label.\n",
        "2. We can find the probability distributions over the variables and then use this distribution to answer queries about the new data point.\n",
        "\n",
        "There are a lot of algorithms for finding a mapping function. For example linear regression tries to find a linear equation which explains the data. Support vector machine tries to find a plane which separates the data points. Decision Tree tries to find a set of simple greater than and less than equations to classify the data. Let's try to apply Decision Tree on this data set.\n",
        "\n",
        "We can plot the data and it looks something like this:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "UgfZBRZo14Th"
      },
      "outputs": [],
      "source": [
        "%matplotlib inline\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "\n",
        "# Adding a little bit of noise so that it's easier to visualize\n",
        "data_with_noise = data.iloc[:, :2] + np.random.normal(loc=0, scale=0.1, size=(150, 2))\n",
        "plt.scatter(data_with_noise.length, data_with_noise.width, c=[ \"bgr\"[k] for k in data.iloc[:,2] ], s=200, alpha=0.3)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Slp0bxl14Ti"
      },
      "source": [
        "In the plot we can easily see that the blue points are concentrated on the top-left corner, green ones in bottom left and red ones in top right.\n",
        "\n",
        "Now let's try to train a Decision Tree on this data."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "cSBiA5Yy14Ti"
      },
      "outputs": [],
      "source": [
        "from sklearn.tree import DecisionTreeClassifier\n",
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "X_train, X_test, y_train, y_test = train_test_split(data[['length', 'width']].values, data.type.values, test_size=0.2)\n",
        "\n",
        "classifier = DecisionTreeClassifier(max_depth=4)\n",
        "classifier.fit(X_train, y_train)\n",
        "classifier.predict(X_test)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "7wIrSCeu14Tj"
      },
      "outputs": [],
      "source": [
        "classifier.score(X_test, y_test)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HD5jsmHI14Tj"
      },
      "source": [
        "So, in this case we got a classification accuracy of 53 %.\n",
        "\n",
        "Now moving on to our second approach using a probabilistic model.\n",
        "The most obvious way to do this classification task would be to compute a Joint Probability Distribution over all these variables and then marginalize and reduce over these according to our new data point to get the probabilities of classes."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "6Zz7EbJT14Tj"
      },
      "outputs": [],
      "source": [
        "X_train, X_test = data[:120], data[120:]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "0e8DMUZp14Tj"
      },
      "outputs": [],
      "source": [
        "X_train"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "BKEPOC5114Tk"
      },
      "outputs": [],
      "source": [
        "# Computing the joint probability distribution over the training data\n",
        "joint_prob = X_train.groupby(['length', 'width', 'type']).size() / 120\n",
        "joint_prob"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "NOawOp_K14Tk"
      },
      "outputs": [],
      "source": [
        "# Predicting values\n",
        "\n",
        "# Selecting just the feature variables.\n",
        "X_test_features = X_test.iloc[:, :2].values\n",
        "X_test_actual_results = X_test.iloc[:, 2].values\n",
        "\n",
        "predicted_values = []\n",
        "for i in X_test_features:\n",
        "    # remove comment to check the probabilities\n",
        "    # print(i, joint_prob[i[0], i[1]])\n",
        "    predicted_values.append(joint_prob[i[0], i[1]].idxmax())\n",
        "\n",
        "predicted_values = np.array(predicted_values)\n",
        "predicted_values"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "t0ATckE414Tk"
      },
      "outputs": [],
      "source": [
        "# Comparing results with the actual data.\n",
        "predicted_values == X_test_actual_results"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "e37kPA8c14Tk"
      },
      "outputs": [],
      "source": [
        "score = (predicted_values == X_test_actual_results).sum() / 30\n",
        "print(score)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "collapsed": true,
        "id": "5P6U75SA14Tk"
      },
      "source": [
        "### 3. Why Probabilistic Graphical Models\n",
        "\n",
        "In the previous example we saw how Bayesian Inference works. We construct a Joint Distribution over the data and then condition on the observed variable to compute the posterior distribution. And then we query on this posterior distribution to predict the values of new data points."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BVYY6C9J14Tl"
      },
      "source": [
        "But the problem with this method is that the Joint Probability Distribution is exponential to the number of states (cardinality) of each variable. So, for problems having a lot of features or having high cardinality of features, inference becomes a difficult task because of computational limitations. For example, for 10 random variables each having 10 states, the size of the Joint Distribution would be 10^10."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YDYdgNYQ14Tl"
      },
      "source": [
        "__Proababilistic Graphical Models (PGM)__: PGM is a technique of compactly representing Joint Probability Distribution over random variables by exploiting the (conditional) independencies between the variables. PGM also provides us methods for efficiently doing inference over these joint distributions.\n",
        "\n",
        "Each graphical model is characterized by a graph structure (can be directed, undirected or both) and a set of parameters associated with each graph.\n",
        "\n",
        "The problem in the above example can be represented using a Bayesian Model (a type of graphical model) as:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "72W1znlP14Tl"
      },
      "outputs": [],
      "source": [
        "Image(url=\"https://github.com/kmouts/PMS/blob/master/support/Iris_BN.png?raw=true\",height=300)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "FUb8wqBD14Tl"
      },
      "source": [
        "In this case the parameters of the network would be $P(L)$, $P(W)$ and $P(T | L, W)$. So, we will need to store 5 values for $L$, 3 values for $W$ and 45 values for $P(T | L, W)$. So, a total of 45 + 5 + 3 = 53 values to completely parameterize the network which is actually more than 45 values which we need for $P (T, L, W)$. But in the cases of bigger networks **graphical models help in saving space**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pRO_urIU14Tl"
      },
      "source": [
        "### 4. Types of Graphical Models\n",
        "\n",
        "There are mainly 2 types of graphical models:\n",
        "\n",
        "1. Bayesian Models: A Bayesian Model consists of a directed graph and Conditional Probability Distributions(CPDs) associated with each of the node. Each CPD is of the form $P(node | parents(node))$ where $parents(node)$ are the parents of the node in the graph structure.\n",
        "\n",
        "2. Markov Models: A Markov Models consists of an undirected graph and are parameterized by Factors. Factors represent how much 2 or more variables agree with each other."
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5. What are Bayesian Models\n",
        "A Bayesian network, Bayes network, belief network, Bayes(ian) model or probabilistic directed acyclic graphical model is a probabilistic graphical model (a type of statistical model) that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). Bayesian networks are mostly used when we want to represent causal relationship between the random variables. Bayesian Networks are parameterized using Conditional Probability Distributions (CPD). Each node in the network is parameterized using $P(node | Pa(node))$ where $Pa(node)$ represents the parents of node in the network.\n",
        "\n",
        "We can take the example of the student model:"
      ],
      "metadata": {
        "id": "7lYglkuEqAva"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "Image(url=\"https://github.com/kmouts/PMS/blob/master/support/student_full_param.png?raw=true\",height=500)"
      ],
      "metadata": {
        "id": "WkQdBJ0JquUC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "We are going to use **pgmpy** library of the construction of BNs:\n",
        "\n",
        "**[pgmpy](https://pgmpy.org/#)** *is a pure python implementation for Bayesian Networks with a focus on modularity and extensibility. Implementations of various alogrithms for Structure Learning, Parameter Estimation, Approximate (Sampling Based) and Exact inference, and Causal Inference are available.*"
      ],
      "metadata": {
        "id": "M8sDFtb5vvJr"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Lets install it first:\n"
      ],
      "metadata": {
        "id": "y6zZ4-sntucc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install -q causalgraphicalmodels\n",
        "!pip install -q pgmpy\n",
        "!pip install superimport\n",
        "\n",
        "!wget -q https://raw.githubusercontent.com/probml/pyprobml/master/scripts/pyprobml_utils.py\n",
        "!wget -q https://raw.githubusercontent.com/probml/pyprobml/master/scripts/pgmpy_utils.py\n",
        "#import pyprobml_utils as pml\n",
        "# import pgmpy_utils as pgm"
      ],
      "metadata": {
        "id": "lFUJy4TUun47"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "In pgmpy we define the network structure and the CPDs separately and then associate them with the structure. Here's an example for defining the above model:"
      ],
      "metadata": {
        "id": "yJkCMh2WwpVM"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from pgmpy.models import BayesianNetwork\n",
        "from pgmpy.factors.discrete import TabularCPD\n",
        "\n",
        "# Defining the model structure. We can define the network by just passing a list of edges.\n",
        "model = BayesianNetwork([('D', 'G'), ('I', 'G'), ('G', 'L'), ('I', 'S')])\n",
        "\n",
        "# Defining individual CPDs.\n",
        "cpd_d = TabularCPD(variable='D', variable_card=2, values=[[0.6], [0.4]])\n",
        "cpd_i = TabularCPD(variable='I', variable_card=2, values=[[0.7], [0.3]])\n",
        "\n",
        "# The representation of CPD in pgmpy is a bit different than the CPD shown in the above picture. In pgmpy the colums\n",
        "# are the evidences and rows are the states of the variable. So the grade CPD is represented like this:\n",
        "#\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "#    | diff    | intel_0 | intel_0 | intel_1 | intel_1 |\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "#    | intel   | diff_0  | diff_1  | diff_0  | diff_1  |\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "#    | grade_0 | 0.3     | 0.05    | 0.9     | 0.5     |\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "#    | grade_1 | 0.4     | 0.25    | 0.08    | 0.3     |\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "#    | grade_2 | 0.3     | 0.7     | 0.02    | 0.2     |\n",
        "#    +---------+---------+---------+---------+---------+\n",
        "\n",
        "cpd_g = TabularCPD(variable='G', variable_card=3,\n",
        "                   values=[[0.3, 0.05, 0.9,  0.5],\n",
        "                           [0.4, 0.25, 0.08, 0.3],\n",
        "                           [0.3, 0.7,  0.02, 0.2]],\n",
        "                  evidence=['I', 'D'],\n",
        "                  evidence_card=[2, 2])\n",
        "\n",
        "cpd_l = TabularCPD(variable='L', variable_card=2,\n",
        "                   values=[[0.1, 0.4, 0.99],\n",
        "                           [0.9, 0.6, 0.01]],\n",
        "                   evidence=['G'],\n",
        "                   evidence_card=[3])\n",
        "\n",
        "cpd_s = TabularCPD(variable='S', variable_card=2,\n",
        "                   values=[[0.95, 0.2],\n",
        "                           [0.05, 0.8]],\n",
        "                   evidence=['I'],\n",
        "                   evidence_card=[2])\n",
        "\n",
        "# Associating the CPDs with the network\n",
        "model.add_cpds(cpd_d, cpd_i, cpd_g, cpd_l, cpd_s)\n",
        "\n",
        "# check_model checks for the network structure and CPDs and verifies that the CPDs are correctly\n",
        "# defined and sum to 1.\n",
        "model.check_model()"
      ],
      "metadata": {
        "id": "RKCWHuOqt4tL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# We can now call some methods on the BayesianModel object.\n",
        "# e.g.: model.get_cpds()\n",
        "# Printing a CPD with it's state names defined.\n",
        "print(model.get_cpds('G'))\n",
        "# model.get_cardinality('G')"
      ],
      "metadata": {
        "id": "mKOCfKCBbBgS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 6. Independencies in Bayesian Networks\n",
        "\n",
        "Independencies implied by the network structure of a Bayesian Network can be categorized in 2 types:\n",
        "\n",
        "1. __Local Independencies:__ Any variable in the network is independent of its non-descendents given its parents. Mathematically it can be written as: $$ (X \\perp NonDesc(X) | Pa(X) $$\n",
        "where $NonDesc(X)$ is the set of variables which are not descendents of $X$ and $Pa(X)$ is the set of variables which are parents of $X$.\n",
        "\n",
        "2. __Global Independencies:__ For discussing global independencies in Bayesian Networks we need to look at the various network structures possible.\n",
        "Starting with the case of 2 nodes, there are only 2 possible ways for it to be connected:\n"
      ],
      "metadata": {
        "id": "BLXhQUUJlfLW"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "Image(url=\"https://github.com/kmouts/PMS/blob/master/support/two_nodes.png?raw=true\",height=80)"
      ],
      "metadata": {
        "id": "XucdogVKmHEW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "In the above two cases it is fairly obvious that change in any of the node will affect the other. For the first case we can take the example of $difficulty \\rightarrow grade$. If we increase the difficulty of the course the probability of getting a higher grade decreases. For the second case we can take the example of $SAT \\leftarrow Intel$. Now if we increase the probability of getting a good score in SAT that would imply that the student is intelligent, hence increasing the probability of $i_1$. Therefore in both the cases shown above any change in the variables leads to change in the other variable.\n",
        "\n",
        "Now, there are four possible ways of connection between 3 nodes:"
      ],
      "metadata": {
        "id": "cWcZ6fUnmn8P"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "Image(url=\"https://github.com/kmouts/PMS/blob/master/support/three_nodes.png?raw=true\",height=300)"
      ],
      "metadata": {
        "id": "uwXOYWnKmYj2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now in the above cases we will see the flow of influence from $A$ to $C$ under various cases.\n",
        "\n",
        "1. __Causal:__ In the general case when we make any changes in the variable $A$, it will have effect of variable $B$ (as we discussed above) and this change in $B$ will change the values in $C$. One other possible case can be when $B$ is observed i.e. we know the value of $B$. So, in this case any change in $A$ won't affect $B$ since we already know the value. And hence there won't be any change in $C$ as it depends only on $B$. Mathematically  we can say that: $(A \\perp C | B)$.\n",
        "2. __Evidential:__ Similarly in this case also observing $B$ renders $C$ independent of $A$. Otherwise when $B$ is not observed the influence flows from $A$ to $C$. Hence $(A \\perp C | B)$.\n",
        "3. __Common Evidence:__ This case is a bit different from the others. When $B$ is not observed any change in $A$ reflects some change in $B$ but not in $C$. Let's take the example of $D \\rightarrow G \\leftarrow I$. In this case if we increase the difficulty of the course the probability of getting a higher grade reduces but this has no effect on the intelligence of the student. But when $B$ is observed let's say that the student got a good grade. Now if we increase the difficulty of the course this will increase the probability of the student to be intelligent since we already know that he got a good grade. Hence in this case $(A \\perp C)$ and $( A \\not\\perp C | B)$. This structure is also commonly known as V structure.\n",
        "4. __Common Cause:__ The influence flows from $A$ to $C$ when $B$ is not observed. But when $B$ is observed and change in $A$ doesn't affect $C$ since it's only dependent on $B$. Hence here also $( A \\perp C | B)$.\n",
        "\n",
        "Let's now see a few examples for finding the independencies in a newtork using pgmpy:\n"
      ],
      "metadata": {
        "id": "k223NNX9m7GG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Getting the local independencies of a variable.\n",
        "model.local_independencies('G')"
      ],
      "metadata": {
        "id": "j5YBUuQNnA_W"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Getting all the local independencies in the network.\n",
        "model.local_independencies(['D', 'I', 'S', 'G', 'L'])"
      ],
      "metadata": {
        "id": "3qxOZ1I7nSDW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Active trail: For any two variables A and B in a network if any change in A influences the values of B then we say\n",
        "#               that there is an active trail between A and B.\n",
        "# In pgmpy active_trail_nodes gives a set of nodes which are affected (i.e. correlated) by any\n",
        "# change in the node passed in the argument.\n",
        "model.active_trail_nodes('D')"
      ],
      "metadata": {
        "id": "vTkEwZgzoL-P"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "model.active_trail_nodes('D', observed='G')"
      ],
      "metadata": {
        "id": "OTpu0d0Tocpv"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 7. How is this Bayesian Network representing the Joint Distribution over the variables ?\n",
        "Till now we just have been considering that the Bayesian Network can represent the Joint Distribution without any proof. Now let's see how to compute the Joint Distribution from the Bayesian Network.\n",
        "\n",
        "From the chain rule of probabiliy we know that:\n",
        "\n",
        "$P(A, B) = P(A | B) * P(B)$\n",
        "\n",
        "Now in this case:\n",
        "\n",
        "$P(D, I, G, L, S) = P(L| S, G, D, I) * P(S | G, D, I) * P(G | D, I) * P(D | I) * P(I)$\n",
        "\n",
        "Applying the local independence conditions in the above equation we will get:\n",
        "\n",
        "$P(D, I, G, L, S) = P(L|G) * P(S|I) * P(G| D, I) * P(D) * P(I)$\n",
        "\n",
        "From the above equation we can clearly see that the Joint Distribution over all the variables is just the product of all the CPDs in the network. Hence encoding the independencies in the Joint Distribution in a graph structure helped us in reducing the number of parameters that we need to store.\n"
      ],
      "metadata": {
        "id": "BFmigTl4pQW3"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 8. Inference in Bayesian Models\n",
        "Till now we discussed just about representing Bayesian Networks. Now let's see how we can do inference in a Bayesian Model and use it to predict values over new data points for machine learning tasks. Here, we will consider that *we already have our model*.\n",
        "\n",
        "In inference we try to answer probability queries over the network given some other variables. So, we might want to know the probable grade of an intelligent student in a difficult class given that he scored good in SAT. So for computing these values from a Joint Distribution we will have to reduce over the given variables that is $I = 1$, $D = 1$, $S = 1$ and then marginalize over the other variables that is $L$ to get $P(G | I=1, D=1, S=1)$.\n",
        "But carrying on marginalize and reduce operation on the complete Joint Distribution is computationaly expensive since we need to iterate over the whole table for each operation and the table is exponential is size to the number of variables. But in Graphical Models we exploit the independencies to break these operations in smaller parts making it much faster.\n",
        "\n",
        "One of the very basic methods of inference in Graphical Models is __Variable Elimination__.\n",
        "\n",
        "\n",
        "#### Variable Elimination\n",
        "We know that:\n",
        "\n",
        "$P(D, I, G, L, S) = P(L|G) * P(S|I) * P(G|D, I) * P(D) * P(I)$\n",
        "\n",
        "Now let's say we just want to compute the probability of G. For that we will need to marginalize over all the other variables.\n",
        "\n",
        "$P(G) = \\sum_{D, I, L, S} P(D, I, G, L, S)$\n",
        "\n",
        "$P(G) = \\sum_{D, I, L, S} P(L|G) * P(S|I) * P(G|D, I) * P(D) * P(I)$\n",
        "\n",
        "$P(G) = \\sum_D \\sum_I \\sum_L \\sum_S P(L|G) * P(S|I) * P(G|D, I) * P(D) * P(I)$\n",
        "\n",
        "Now since not all the conditional distributions depend on all the variables we can push the summations inside:\n",
        "\n",
        "$P(G) = \\sum_D P(D) \\sum_I P(G|D, I) * P(I) \\sum_S P(S|I) \\sum_L P(L|G)$\n",
        "\n",
        "So, by pushing the summations inside we have saved a lot of computation because we have to now iterate over much smaller tables.\n",
        "\n",
        "Let's take an example for inference using Variable Elimination in pgmpy:"
      ],
      "metadata": {
        "id": "2NSWxOcxpmZg"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from pgmpy.inference import VariableElimination\n",
        "infer = VariableElimination(model)\n",
        "g_dist = infer.query(['G'])\n",
        "print(g_dist)"
      ],
      "metadata": {
        "id": "U1N-9NI6qI1h"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "There can be cases in which we want to compute the conditional distribution let's say $P(G | D=0, I=1)$. In such cases we need to modify our equations a bit:\n",
        "\n",
        "$P(G | D=0, I=1) = \\sum_L \\sum_S P(L|G) * P(S| I=1) * P(G| D=0, I=1) * P(D=0) * P(I=1)$\n",
        "\n",
        "$P(G | D=0, I=1) = P(D=0) * P(I=1) * P(G | D=0, I=1) * \\sum_L P(L | G) * \\sum_S P(S | I=1)$\n",
        "\n",
        "In pgmpy we will just need to pass an extra argument in the case of conditional distributions:\n"
      ],
      "metadata": {
        "id": "6kKiCtUdsqEw"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(infer.query(['G'], evidence={'D': 0, 'I': 1}))"
      ],
      "metadata": {
        "id": "1uiZzYuJrLQY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(infer.query(['G'], evidence={'D': 1, 'I': 1, 'S':0}))"
      ],
      "metadata": {
        "id": "Zhmx9cpzuQl5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#  What is the probable grade of an intelligent student in a difficult class given that he scored good in SAT?\n",
        "# WRITE YOUR CODE HERE\n",
        "\n",
        "\n",
        "# Is it dependent from the SAT score?"
      ],
      "metadata": {
        "id": "xJ2y3aBbuOnx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "####  Predicting values from new data points\n",
        "Predicting values from new data points is quite similar to computing the conditional probabilities. We need to query for the variable that we need to predict given all the other features. The only difference is that rather than getting the probabilitiy distribution we are interested in getting the most probable state of the variable.\n",
        "\n",
        "In pgmpy this is known as MAP query. Here's an example:\n"
      ],
      "metadata": {
        "id": "lkOattJFwfN7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "infer.map_query(['G'])"
      ],
      "metadata": {
        "id": "IhgeQyMMwt2y"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "infer.map_query(['G'], evidence={'D': 0, 'I': 1, 'L': 1, 'S': 1})"
      ],
      "metadata": {
        "id": "jceSk29ZwyV6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 9. Other methods for Inference\n",
        "Even though exact inference algorithms like Variable Elimination optimize the inference task, it is still computationally quite expensive in the case of large models. For such cases we can use approximate algorithms like Message Passing Algorithms, Sampling Algorithms etc.\n"
      ],
      "metadata": {
        "id": "iQVyhgg8xHek"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 10. Loading example models\n",
        "To quickly try out different features, pgmpy also has the functionality to directly load some example models from the [bnlearn repository](https://colab.research.google.com/github/kmouts/PMS/blob/master/PGM.ipynb#scrollTo=4dVfYML22rd9&line=2&uniqifier=1)."
      ],
      "metadata": {
        "id": "4dVfYML22rd9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from pgmpy.utils import get_example_model\n",
        "\n",
        "model = get_example_model(\"cancer\")\n",
        "print(\"Nodes in the model:\", model.nodes())\n",
        "print(\"Edges in the model:\", model.edges())\n",
        "model.get_cpds()"
      ],
      "metadata": {
        "id": "BX9lzQ4h25QN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "We can draw the Network as well:"
      ],
      "metadata": {
        "id": "0oQQzXr6DGk0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install -q daft networkx\n",
        "!apt install -q libgraphviz-dev\n",
        "!pip install -q pygraphviz"
      ],
      "metadata": {
        "id": "3wrRPEe134Tg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx as nx\n",
        "import matplotlib.pyplot as plt\n",
        "\n",
        "\n",
        "# Turning Our Bayesian Network into a Picture\n",
        "graph = model.to_graphviz()\n",
        "graph.layout()\n",
        "# graph.draw('file.png')\n",
        "# Image('file.png')\n",
        "\n",
        "# Showing Our Picture\n",
        "nx.draw(graph, with_labels=True, node_size=500, node_color=\"skyblue\", font_size=10, font_color=\"black\")\n",
        "\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "n7GPHMdf3-4p"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Can you get the probabilities for a person who lives in Polluted environment and is a Smoker, has Dyspnoea but his X-ray is clean to have Cancer?"
      ],
      "metadata": {
        "id": "UT424TyiDQ0i"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Make your exmperiments here\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "m6WkRg6pD8AT"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8.10"
    },
    "colab": {
      "provenance": [],
      "toc_visible": true,
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}