{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Graphical Models" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "###### COMP4670/8600 - Introduction to Statistical Machine Learning - Tutorial 6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Setting up the environment" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# you may need to install tikzmagic, try the following:\n", "#\n", "# https://github.com/robjstan/tikzmagic\n", "# https://anaconda.org/conda-forge/tikzmagic\n", "\n", "import numpy as np\n", "import tikzmagic" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reviewing discrete probability\n", "\n", "Recall the meaning of the following terms:\n", "* Joint probability distribution\n", "* Marginal distribution\n", "* Conditional distribution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the following table defining the joint probability distribution of two variables $A$ and $B$.\n", "\n", "| | A=$\\square$ | A=$\\bigcirc$ | A = $\\clubsuit$ | A = $\\heartsuit$ | A = $\\triangle$ |\n", "|--|:--:|:--:|:--:|:--:|:--:|\n", "|**B**=$p$|0.01|0.01|0.12|0.01|0.14|\n", "|**B**=$q$|0.03|0.15|0.01|0.01|0.01|\n", "|**B**=$r$|0.13|0.11|0.07|0.18|0.01|\n", "\n", "Compute the following distributions:\n", "* $p(B=p | A = \\bigcirc)$\n", "* $p(B | A = \\bigcirc)$\n", "* $p(B)$\n", "\n", "You may do this calculation by hand or using python.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Bayes Rule\n", "\n", "Recall that there are only two rules of probability, the sum rule and the product rule. Using these two rules, prove Bayes rule.\n", "$$p(Y|X) = \\frac{p(X|Y)p(Y)}{\\sum_Y p(X,Y)}$$\n", "Observe that the left hand side is a function of $Y$ and the right hand side is a function of $X$ and $p(Y)$ only." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Empirical verification of Bayes rule\n", "\n", "Using the distribution $p(A,B)$ above, compute the all terms in Bayes rule, and verify your theorem." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dependent random variables\n", "\n", "Consider the following problem with 5 random variables.\n", "* **A**ches with states (False, True)\n", "* **B**ronchitis with states (none, mild, severe)\n", "* **C**ough with states (False, True)\n", "* **D**isease with states (healthy, carrier, sick, recovering)\n", "* **E**mergency with states (False, True)\n", "\n", "How much memory is needed to store the joint probability distribution if:\n", "* All variables were dependent?\n", "* All variables were independent?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the following graphical model." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "%%tikz\n", "\\tikzstyle{vertex}=[circle, draw=black, fill=white, line width=0.5mm, minimum size=10pt, inner sep=0pt]\n", "\\tikzstyle{edge} = [draw, line width=0.25mm, ->]\n", "\n", "\\node[vertex,label=left:{Aches}] (a) at (0,0) {};\n", "\\node[vertex,label=above:{Bronchitis}] (b) at (1,1) {};\n", "\\node[vertex,label=above:{Cough}] (c) at (3,1) {};\n", "\\node[vertex,label=left:{Disease}] (d) at (2,0) {};\n", "\\node[vertex,label=right:{Emergency}] (e) at (3,-1) {};\n", "\n", "\\foreach \\source/ \\dest in {b/a, b/d, c/d, d/e}\n", " \\path[edge] (\\source) -- (\\dest);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How much memory is needed to store the joint probability distribution? Identify the conditional independences in the graph. Consider both cases: when variables are observed and when they are unobserved. \n", "\n", "*A random variable $X$ is independent of $Y$ given $Z$ (written $X\\perp Y | Z$) if and only if\n", "$$p(X|Y,Z) = p(X|Z).$$\n", "Equivalently this can be seen as a generalisation of the factorisation property when you have independence,\n", "\\begin{align*}\n", " p(X,Y|Z) & = p(X|Y,Z) p(Y|Z)\\\\\n", " & = p(X|Z) p(Y|Z)\n", "\\end{align*}\n", "The first equality above is just the product rule.*\n", "\n", "By observing the structure of the graphical model and using the sum rule and product rule, prove the conditional independences that you have identified." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the following tables.\n", "\n", "|$p(B)$ | B=n | B=m | B=s |\n", "|:-----:|:--:|:--:|:--:|\n", "|marginal| 0.97 | 0.01 | 0.02 |\n", "\n", "|$p(C)$ | C=False | C=True |\n", "|:-----:|:--:|:--:|\n", "|marginal| 0.7 | 0.3 |\n", "\n", "| $p(A|B)$ | B=n | B=m | B=s |\n", "|:-----:|:--:|:--:|:--:|\n", "|**A**=False |0.9|0.8|0.3|\n", "|**A**=True |0.1|0.2|0.7|\n", "\n", "| $p(D|B,C)$ | B=n, C=F | B=m, C=F | B=s, C=F | B=n, C=T | B=m, C=T | B=s, C=T |\n", "|:-----:|:--:|:--:|:--:|:--:|:--:|:--:|\n", "|**D**=healthy |0.9 |0.8 |0.1 | 0.3 |0.4 |0.01|\n", "|**D**=carrier |0.08|0.17|0.01| 0.05|0.05|0.01|\n", "|**D**=sick |0.01|0.01|0.87| 0.05|0.15|0.97|\n", "|**D**=recovering|0.01|0.02|0.02| 0.6 |0.4 |0.01|\n", "\n", "| $p(E|D)$ | D=h | D=c | D=s | D=r |\n", "|:-----:|:--:|:--:|:--:|\n", "|**E**=False |0.99|0.99|0.4|0.9|\n", "|**E**=True |0.01|0.01|0.6|0.1|\n", "\n", "\n", "Compute the following:\n", "* p(A,B,C,D,E)\n", "* p(E)\n", "* p(E|B=s)\n", "* p(E|B=s, C=T)\n", "\n", "Note that there are two ways of arriving at the distributions:\n", "1. By computing p(A,B,C,D,E) and marginalising and conditioning appropriately\n", "2. By only computing the required distributions directly using the graphical model structure.\n", "Check that both ways give the same answer." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sampling a Discrete PMF\n", "1. Code a class which represents a PMF, and has a sample method which draws a sample from the PMF.\n", "2. Use it to draw samples from $p(C)$ and empirically compute and print the probability that your sampler returns the value False." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "## Markov Random Field\n", "\n", "Convert the Bayesian Network above to a Markov Random Field. Draw the resulting network in tikz." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Identify the maximal cliques in the graph and write down the corresponding clique potentials. Compare the conditional independence statements of the MRF with the BN." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "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.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }