HW 6 - Bayesian Network/Starter/notebook.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-027da61e09ea6982",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "# BMI\/CS 576 - HW6\n",
                "The objectives of this homework are to better understand\n",
                "\n",
                "* the statistical dependencies represented by a Bayesian network\n",
                "* alternative representations of conditional probability distributions (CPDs)\n",
                "* how model evidence works as a score for Bayesian networks\n",
                "* the Sparse Candidate algorithm\n",
                "\n",
                "## HW policies\n",
                "Before starting this homework, please read over the [homework policies](https:\/\/canvas.wisc.edu\/courses\/167969\/pages\/hw-policies) for this course.  In particular, note that homeworks are to be completed *individually*.\n",
                "\n",
                "You are welcome to use any code from the weekly notebooks in your solutions to the HW."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-51388c4a0f9b2aa3",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 1 (30 POINTS)\n",
                "\n",
                "Consider the Bayesian network below \n",
                "\n",
                "![simple_network](simple_network.png)\n",
                "\n",
                "**(a)** Give a table specifying the joint probability distribution, $P(A, B, C)$ represented by the Bayesian network.\n",
                "\n",
                "**(b)** Given your table from (a), compute $P(A = true\\ |\\ C = true)$\n",
                "\n",
                "**(c)** Given your table from (a), compute $P(A = true\\ |\\ B = true)$\n",
                "\n",
                "**(d)** Given your table from (a), compute $P(A = true\\ |\\ B = true, C = true)$\n",
                "\n",
                "**(e)** Given your table from (a), is $A$ independent of $B$? Justify your answer.\n",
                "  \n",
                "**(f)** Given your table from (a), is $A$ independent of $B$ given $C$? Justify your answer.\n",
                "\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "p1",
                    "locked": false,
                    "points": 30,
                    "schema_version": 1,
                    "solution": true
                }
            },
            "source": [
                "###\n",
                "### solution to problem 1\n",
                "###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-3efc15f74bf1d298",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 2 (25 POINTS)\n",
                "As shown in the slide \"Representing CPDs for Discrete Variables\" (slide 8) of the lecture \"Networks - Introduction to Bayesian Networks\" some conditional probability distributions (CPD) can also be represented with a tree.\n",
                "\n",
                "**(a)** Give the CPD table for the distribution $P(D\\ |\\ A,B,C)$ represented by the tree below.\n",
                "![](decision_tree.png)\n",
                "\n",
                "**(b)** Give the most compact tree (i.e., one with the fewest nodes) represention of the distribution $P(D\\ |\\ A,B,C)$ specified by the CPD table below.\n",
                "\n",
                "![](decision_tree_cpd.png)\n",
                "\n",
                "**(c)** Suppose that you know that the CPD $P(D\\ |\\ A,B,C)$ can be represented by the tree structure of part (a), but that you don't know the parameters at the leaves of the tree.  Now suppose you are given some training data with which to estimate the CPD.  What is the major advantage of the tree representation over the CPD table representation in estimating the parameters of the CPD?"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "p2",
                    "locked": false,
                    "points": 25,
                    "schema_version": 1,
                    "solution": true
                }
            },
            "source": [
                "###\n",
                "### solution to problem 2\n",
                "###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-da60905e0e67952f",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 3 (30 POINTS)\n",
                "\n",
                "Consider two possible Bayesian networks for two binary random variables, $X_1$ and $X_2$, shown below.\n",
                "\n",
                "![](two_var_networks.png)\n",
                "\n",
                "**(a)** Give the likelihood function, $P(D|G_0, \\theta)$, for network $G_0$ in terms of the count variables shown in the table above.\n",
                "\n",
                "**(b)** Give the likelihood function, $P(D|G_1, \\theta)$, for network $G_1$ in terms of the count variables shown in the table above.\n",
                "\n",
                "**(c)** Suppose that we estimate maximum likelihood values, $\\hat{\\theta}_{MLE}$, for the parameters of each of the two networks given a data set, $D$.  Show that $P(D|G_1, \\hat{\\theta}_{MLE}) \\geq P(D|G_0, \\hat{\\theta}_{MLE})$ for any data set, $D$, and thus that the likelihood is not a good way to score networks. *Hint: consider what happens when $\\theta_2 = \\theta_{20} = \\theta_{21}$.*\n",
                "\n",
                "**(d)** Derive the model evidence, $P(D|G_0)$ for the network $G_0$ in terms of the count variables shown in the table above.\n",
                "\n",
                "**(e)** Derive the model evidence, $P(D|G_1)$ for the network $G_1$ in terms of the count variables shown in the table above.\n",
                "\n",
                "**(f)** Consider the case in which $n = 20$ and $n_{0-} = n_{1-} = n_{-0} = n_{-1} = 10$ (i.e., each row and column of the data table sum to half of the total observations).  Compute the difference in the log model evidence between the two models, $\\log(P(D|G_1)) - \\log(P(D|G_0))$, over all possible values of $n_{00}$ (note that specifying $n_{00}$ specifies all other counts).  These values indicate for which data sets we would prefer $G_1$ over $G_0$, and vice versa.  Show your results as a plot of $\\log(P(D|G_1)) - \\log(P(D|G_0))$ vs. $n_{00}$."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "p3",
                    "locked": false,
                    "points": 30,
                    "schema_version": 1,
                    "solution": true
                }
            },
            "source": [
                "###\n",
                "### solution to problem 3\n",
                "###\n"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true,
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-bbd76a9bb92522be",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "outputs": [],
            "source": [
                "import math\n",
                "import matplotlib.pyplot as plt"
            ]
        },
        {
            "cell_type": "code",
            "execution_count": null,
            "metadata": {
                "collapsed": true,
                "nbgrader": {
                    "grade": true,
                    "grade_id": "cell-fa433559aa2bf51d",
                    "locked": false,
                    "points": 0,
                    "schema_version": 1,
                    "solution": true
                }
            },
            "outputs": [],
            "source": [
                "###\n",
                "### YOUR CODE HERE\n",
                "###\n"
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": false,
                    "grade_id": "cell-a1c731f8cc90e83b",
                    "locked": true,
                    "schema_version": 1,
                    "solution": false
                },
                "editable": false,
                "deletable": false
            },
            "source": [
                "## PROBLEM 4 (15 POINTS) \n",
                "\n",
                "\n",
                "Suppose we wish to reconstruct the gene regulatory network for three genes, $X$, $Y$, and $Z$, using the Bayesian network approach and the \u201csparse candidate\u201d algorithm. We are given data from 100 independent experiments in which the expression levels of the three genes are measured. For simplicity, we model each gene as being either \u201con\u201d (T) or \u201coff\u201d (F). Below is a table summarizing the number of times (count) each configuration of gene expression status was observed in these experiments.\n",
                "\n",
                "\n",
                "| X | Y | Z | count |\n",
                "|---|---|---|-------|\n",
                "| T | T | T |  36   |\n",
                "| T | T | F |   4   |\n",
                "| T | F | T |   2   |\n",
                "| T | F | F |   8   |\n",
                "| F | T | T |   9   |\n",
                "| F | T | F |   1   |\n",
                "| F | F | T |   8   |\n",
                "| F | F | F |  32   |\n",
                "\n",
                "\n",
                "**(a)** Suppose we wish to compute a single candidate parent for $Z$. In the first round of the \u201csparse candidate\u201d algorithm, we compute the mutual information between $Z$ and the other random variables. Compute the mutual information between $Z$ and $X$, $I(X,Z)$, based on the frequencies observed in the data.\n",
                "\n",
                "**(b)** Compute the mutual information between $Z$ and $Y$, $I(Y,Z)$, based on the frequencies observed in the data.\n",
                "\n",
                "**(c)** Based on your answers to (a) and (b), which gene would be selected as the candidate parent for Z? Briefly explain your answer."
            ]
        },
        {
            "cell_type": "markdown",
            "metadata": {
                "nbgrader": {
                    "grade": true,
                    "grade_id": "p4",
                    "locked": false,
                    "points": 15,
                    "schema_version": 1,
                    "solution": true
                }
            },
            "source": [
                "###\n",
                "### solution to problem 4\n",
                "###\n"
            ]
        }
    ],
    "metadata": {
        "celltoolbar": "Create Assignment",
        "kernelspec": {
            "display_name": "Python 3 [3.6]",
            "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.6.4"
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}