{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Inference and Reasoning with Bayesian Networks" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "###### COMP4670/8600 - Introduction to Statistical Machine Learning - Assignment 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Name: SOLUTION FILE\n", "\n", "Student ID:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Instructions\n", "\n", "| |Notes|\n", "|:------------|:--|\n", "|Maximum marks| 19|\n", "|Weight|19% of final grade|\n", "|Format| Complete this ipython notebook. Do not forget to fill in your name and student ID above|\n", "|Submission mode| Use [wattle](https://wattle.anu.edu.au/)|\n", "|Formulas| All formulas which you derive need to be explained unless you use very common mathematical facts. Picture yourself as explaining your arguments to somebody who is just learning about your assignment. With other words, do not assume that the person marking your assignment knows all the background and therefore you can just write down the formulas without any explanation. It is your task to convince the reader that you know what you are doing when you derive an argument. Typeset all formulas in $\\LaTeX$.|\n", "| Code quality | Python code should be well structured, use meaningful identifiers for variables and subroutines, and provide sufficient comments. Please refer to the examples given in the tutorials. |\n", "| Code efficiency | An efficient implementation of an algorithm uses fast subroutines provided by the language or additional libraries. For the purpose of implementing Machine Learning algorithms in this course, that means using the appropriate data structures provided by Python and in numpy/scipy (e.g. Linear Algebra and random generators). |\n", "| Cooperation | All assignments must be done individually. Cheating and plagiarism will be dealt with in accordance with University procedures (please see the ANU policies on [Academic Honesty and Plagiarism](http://academichonesty.anu.edu.au)). Hence, for example, code for programming assignments must not be developed in groups, nor should code be shared. You are encouraged to broadly discuss ideas, approaches and techniques with a few other students, but not at a level of detail where specific solutions or implementation issues are described by anyone. If you choose to consult with other students, you will include the names of your discussion partners for each solution. If you have any questions on this, please ask the lecturer before you act. |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\newcommand{\\dotprod}[2]{\\left\\langle #1, #2 \\right\\rangle}$\n", "$\\newcommand{\\onevec}{\\mathbb{1}}$\n", "\n", "Setting up the environment (there is some hidden latex which needs to be run in this cell)." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import itertools, copy\n", "import matplotlib.pyplot as plt\n", "import numpy as np\n", "from IPython.display import display, Image\n", "\n", "%matplotlib inline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 1: Graphical Models\n", "\n", "### Problem setting\n", "\n", "We are interested to predict the outcome of the election in an imaginary country, called Under Some Assumptions (USA). There are four candidates for whom the citizens can **Vote** for: Bernie, Donald, Hillary, and Ted. The citizens live in four **Region**s: north, south, east and west. We have general demographic information about the people, namely: **Gender** (male, female) and **Hand**edness (right, left). Based on surveys done by an external company, we believe that the **Region** and **Gender** affects whether the people use their **Jacket**s full time, part time or never. Surprisingly, the company told us that the **Age** of their shoes (new, worn, old) depends on how often they wear their **Jacket**s. Furthermore, the **Gender** and their preferred **Hand** affects the **Colour** of their hat (white, black). Finally, surveys say that the citizens will **Vote** based on their **Region**, **Age** of their shoes and **Colour** of their hats.\n", "\n", "The directed graphical model is depicted below:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "Image(url=\"https://machlearn.gitlab.io/isml2017/assignments/election_model.png\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Conditional probability tables\n", "\n", "After paying the survey firm some more money, they provided the following conditional probability tables.\n", "\n", "|$p(R)$ | R=n | R=s | R=e | R=w |\n", "|:-----:|:--:|:--:|:--:|:--:|\n", "|marginal| 0.2 | 0.1 | 0.5 | 0.2 |\n", "\n", "|$p(G)$ | G=m | G=f |\n", "|:-----:|:--:|:--:|\n", "|marginal| 0.3 | 0.7 |\n", "\n", "|$p(H)$ | H=r | H=l |\n", "|:-----:|:--:|:--:|\n", "|marginal| 0.9 | 0.1 |\n", "\n", "| $p(J|R,G)$ | R=n,G=m | R=n,G=f | R=s,G=m | R=s,G=f | R=e,G=m | R=e,G=f | R=w,G=m | R=w,G=f |\n", "|:-----:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|\n", "|**J**=full $\\quad$ |0.9 |0.8 |0.1 | 0.3 |0.4 |0.01| 0.02 | 0.2 |\n", "|**J**=part $\\quad$ |0.08|0.17|0.03| 0.35|0.05|0.01| 0.2 | 0.08 |\n", "|**J**=never $\\quad$ |0.02|0.03|0.87| 0.35|0.55|0.98| 0.78 | 0.72 |\n", "\n", "| $p(A|J)$ | J=full | J=part | J=never |\n", "|:-----:|:--:|:--:|:--:|\n", "|**A**=new |0.01|0.96|0.3|\n", "|**A**=worn |0.98|0.03|0.5|\n", "|**A**=old |0.01|0.01|0.2|\n", "\n", "| $p(C|G,H)$ | G=m,H=r | G=m,H=l | G=f,H=r | G=f,H=l |\n", "|:-----:|:--:|:--:|:--:|:--:|\n", "|**C**=black $\\quad$ |0.9 |0.83 |0.17 | 0.3 |\n", "|**C**=white $\\quad$ |0.1 |0.17|0.83 | 0.7 |\n", "\n", "The final conditional probability table is given by the matrix below. The order of the rows and columns are also given below." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "vote_column_names = ['north,new,black', 'north,new,white', 'north,worn,black', 'north,worn,white', \n", " 'north,old,black', 'north,old,white', 'south,new,black', 'south,new,white', \n", " 'south,worn,black', 'south,worn,white', 'south,old,black', 'south,old,white', \n", " 'east,new,black', 'east,new,white', 'east,worn,black', 'east,worn,white', \n", " 'east,old,black', 'east,old,white', 'west,new,black', 'west,new,white', \n", " 'west,worn,black', 'west,worn,white', 'west,old,black', 'west,old,white']\n", "\n", "vote_outcomes = ('bernie','donald','hillary','ted')\n", "\n", "vote_pmf_array = np.array(\n", " [\n", " [0.1,0.1,0.4,0.02,0.2,0.1,0.1,0.04,0.2,0.1,0.1 ,0.1,0.4 ,0.1 ,0.1,0.1 ,0.1,0.04,0.3,0.2,0.1,0.3,0.34,0.35],\n", " [0.3,0.4,0.2,0.5 ,0.1,0.2,0.1,0.5 ,0.1,0.2,0.5 ,0.3,0.2 ,0.42,0.2,0.67,0.4,0.4 ,0.1,0.1,0.5,0.1,0.1 ,0.1],\n", " [0.5,0.4,0.3,0.3 ,0.5,0.6,0.6,0.3 ,0.5,0.4,0.36,0.3,0.28,0.3 ,0.4,0.1 ,0.4,0.16,0.4,0.2,0.3,0.3,0.4 ,0.5],\n", " [0.1,0.1,0.1,0.18,0.2,0.1,0.2,0.16,0.2,0.3,0.04,0.3,0.12,0.18,0.3,0.13,0.1,0.4 ,0.2,0.5,0.1,0.3,0.16,0.05],\n", " ]\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The 7 conditional probability tables in are encoded in python below. \n", "\n", "**Base your subsequent computations on these objects**." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "class RandomVariable(object):\n", " def __init__(self, name, parents, outcomes, pmf_array):\n", " assert isinstance(name, str)\n", " assert all(isinstance(_, RandomVariable) for _ in parents)\n", " assert isinstance(outcomes, tuple)\n", " assert all(isinstance(_, str) for _ in outcomes)\n", " assert isinstance(parents, tuple)\n", " assert isinstance(pmf_array, np.ndarray)\n", " keys = tuple(map(tuple, itertools.product(*[_.outcomes for _ in parents])))\n", " assert np.allclose(np.sum(pmf_array, 0), 1)\n", " expected_shape = (len(outcomes), len(keys))\n", " assert pmf_array.shape == expected_shape, (pmf_array.shape, expected_shape)\n", " pmfs = {k: {outcome: probability for outcome, probability in zip(outcomes, probabilities)} \n", " for k, probabilities in zip(keys, pmf_array.T)}\n", " self.name, self.parents, self.outcomes, self.pmfs = name, parents, outcomes, pmfs\n", "\n", "\n", "class BayesianNetwork(object):\n", " def __init__(self, *random_variables):\n", " assert all(isinstance(_, RandomVariable) for _ in random_variables)\n", " self.random_variables = random_variables\n", " \n", "\n", "region_pmf_array = np.array([[0.2, 0.1, 0.5, 0.2]]).T\n", "region = RandomVariable(\n", " name='region',\n", " parents=tuple(),\n", " outcomes=('north', 'south', 'east', 'west'), \n", " pmf_array = region_pmf_array,\n", ")\n", "\n", "gender_pmf_array = np.array([[0.3, 0.7]]).T\n", "gender = RandomVariable(\n", " name='gender',\n", " parents=tuple(),\n", " outcomes=('male', 'female'), \n", " pmf_array = gender_pmf_array\n", ")\n", "\n", "hand_pmf_array = np.array([[0.9, 0.1]]).T\n", "hand = RandomVariable(\n", " name='hand',\n", " parents=tuple(),\n", " outcomes=('left', 'right'), \n", " pmf_array = hand_pmf_array\n", ")\n", "\n", "jacket_pmf_array = np.array(\n", " [\n", " [0.9,0.8,0.1,0.3,0.4,0.01,0.02,0.2],\n", " [0.08,0.17,0.03,0.35,0.05,0.01,0.2,0.08],\n", " [0.02,0.03,0.87,0.35,0.55,0.98,0.78,0.72],\n", " ]\n", " )\n", "jacket = RandomVariable(\n", " name='jacket',\n", " parents=(region, gender),\n", " outcomes=('full', 'part', 'never'), \n", " pmf_array = jacket_pmf_array\n", ")\n", "\n", "age_pmf_array = np.array(\n", " [\n", " [0.01,0.96,0.3],\n", " [0.98,0.03,0.5],\n", " [0.01,0.01,0.2],\n", " ]\n", " )\n", "age = RandomVariable(\n", " name='age',\n", " parents=(jacket, ),\n", " outcomes=('new', 'worn', 'old'), \n", " pmf_array = age_pmf_array\n", ")\n", "\n", "colour_pmf_array = np.array(\n", " [\n", " [0.9,0.83,0.17,0.3],\n", " [0.1,0.17,0.83,0.7],\n", " ]\n", " )\n", "colour = RandomVariable(\n", " name='colour',\n", " parents=(gender, hand),\n", " outcomes=('black', 'white'),\n", " pmf_array = colour_pmf_array\n", ")\n", "\n", "vote = RandomVariable(\n", " name='vote',\n", " parents=(region, age, colour),\n", " outcomes=vote_outcomes,\n", " pmf_array = vote_pmf_array\n", ")\n", "\n", "\n", "election_model = BayesianNetwork(region, gender, hand, jacket, age, colour, vote)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1A (1 mark) Joint distribution of a subset\n", "\n", "- Compute the joint distribution of **Jacket**, **Region** and **Gender**. Print in a tab separated format the resulting distribution." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B1 (2 marks) Variable Ordering\n", "\n", "1. Implement a function which determines an appropriate ordering of the variables for use in the following scheme:\n", " - For the first node R, draw a sample from p(R).\n", " - For each subsequent node, draw a sample from the conditional distribution $p(X \\,|\\, \\text{parents}(X))$ where $\\text{parents}(X)$ are the parents of the variable $X$ in the graphical model.\n", "- Use your function to compute such an ordering and print the result in a human friendly format." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B2 (2 marks) Sampling\n", "\n", "1. Given the ordering you have determined above, implement the sampler described in the previous question. If you were unable to compute the ordering in the previous question, use ordering = (hand, region, gender, colour, jacket, age, vote).\n", "2. Draw a single sample and print the result in a human friendly format." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B3 (2 marks) Marginals\n", "\n", "1. Calculate (and show in LaTeX) the marginal distribution for **Jacket**.\n", "- Implement a function which computes the marginal distribution of each variable. It should make use of the ordering used by your sampler.\n", "- Implement a function which takes a list of samples the model and computes the empirical marginal distribution of each variable.\n", "- Plot the theoretical and approximate marginals which you obtain along with the absolute percent error between the two, in the format below:" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "region\n", "outcome\texact\tapprox\terror (%)\n", "north\t0.20\t0.20\t0.4\n", "south\t0.10\t0.10\t0.1\n", "east\t0.50\t0.50\t0.4\n", "west\t0.20\t0.20\t0.6\n", "\n", "gender\n", "outcome\texact\tapprox\terror (%)\n", "male\t0.30\t0.30\t0.1\n", "female\t0.70\t0.70\t0.0\n", "\n", "etc." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B4 (1 mark) Easy conditional probabilities\n", "\n", "Compute $p(X \\,|\\, G=\\text{female})$ for all $X$ other than $G$,\n", "1. Approximately, using your sampler\n", "- Exactly, using your marginal calculating function from the previous question. Hint: what happens if you set $p(G=\\text{female})=1$ in your model?\n", "- Plot the results side by side in the same format as the previous question.\n", "- State for which variables other than $G$ the theoretical scheme above can be used to compute such conditionals, and why." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B5 (3 marks) General conditional probabilities\n", "\n", "1. Write down the expression of the joint probability $p(R,G,H,J,A,C,V)$ in terms of the conditional probabilities in the graphical model.\n", "- Derive $p(G = male \\,|\\, V = Donald)$ in terms of the conditional probabilities of the graphical model.\n", "- Compute and display in a human friendly format the conditional distributions $p(G=g \\,|\\, V=v)$ for all genders $g$ and votes $v$, by naively marginalising the other variables (other than $G$ and $V$, that is)." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Solution description" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B6 (2 marks) Variable elimination\n", "\n", "Denote the graphical model consider thus far $\\mathcal{M}$.\n", "\n", "1. Derive $p(R,G,J,A,C,V)$ by marginalising over $H$ in $\\mathcal{M}$. \n", "- Describe how the structure (connectivity) of the new graphical model (call it $\\mathcal{M}_H$) over all variables other than $H$ changes after eliminating $H$ in this way.\n", "- Describe which conditional(s) in the new graphical model differ from the original model.\n", "- Encode the $\\mathcal{M}_H$ in python similarly to $\\mathcal{M}$. " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1B6 (3 marks) General estimation of conditional probabilities (revisited)\n", "\n", "1. As you did earlier, compute and display in a human friendly format the conditional distributions $p(G=g \\,|\\, V=v)$ for all genders $g$ and votes $v$, by naively marginalising the other variables (other than $G$ and $V$, that is). This time however, do so using $\\mathcal{M}_H$ rather than $\\mathcal{M}$.\n", "- Quantify the computational advantages of using $\\mathcal{M}_H$ in this way rather than $\\mathcal{M}$.\n", "- Which variable (or variables) would be the best to eliminate in this way, in terms of the aforementioned computational advantages, and why?\n", "- Pick a (best) variable from the previous question and call it $X$. Assuming we have eliminated $X$, which would be the \"best\" variable to subsequently eliminate in a similar fashion?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# Solution goes here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 2: Theory" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2A (3 marks) Functions of random variables\n", "\n", "$u$ and $v$ are independently sampled from the standard uniform distribution on the unit interval, $[0,1]$. \n", "\n", "If $s=(2u-1)^2+(2v-1)^2 \\geq 1$ then $x$ is sampled from the standard normal distribution, $\\mathcal{N}(0,1)$. Otherwise $x=(2u-1)\\sqrt{-2 \\log(s)/s}$.\n", "\n", "How is $x$ distributed?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution description" ] } ], "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 }