Day 24 - Bayesian Network Structures/Solution/notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-1b8f133bd2642668",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Day 24 notebook\n",
    "\n",
    "The objectives of this notebook are to practice\n",
    "\n",
    "* computing the probablity of data given the graph (the model evidence)\n",
    "* counting the number of possible Bayesian network structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-9fce1bb08a29e010",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Modules used for this assignment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c4fca047940fa76c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# standard library modules\n",
    "import math             # for log and lgamma\n",
    "\n",
    "# course modules\n",
    "import bayesian_network # for the BayesianNetwork class"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-9843bef3440ecb81",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 1: Computing the score (model evidence) of Bayesian network structure\n",
    "\n",
    "In this notebook we will compute $\\log P(D | G)$ (the model evidence) for a particular data set, $D$, and a particular Bayesian network graph, $G$.  This value is the score of the Bayesian network in the structure learning task.  In practice, we would want to find the Bayesian network structure that has the highest score, but for now we will focus simply on computing the score for one particular structure, given a data set.\n",
    "\n",
    "We will be modeling three binary random variables $X_1, X_2,$ and $X_3$ for which we have data.  Here is the data set we will be using to compute the score of a graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-983dd7920ed48f3a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    },
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first 6 (out of 1000 total) observations:\n",
      "(0, 0, 0)\n",
      "(0, 1, 0)\n",
      "(0, 1, 0)\n",
      "(0, 0, 1)\n",
      "(1, 1, 1)\n",
      "(0, 0, 0)\n"
     ]
    }
   ],
   "source": [
    "# read in the data set as a list of tuples \n",
    "# (each tuple is one joint observation of the three variables)\n",
    "data = [tuple(map(int, line.split())) for line in open(\"data.txt\")]\n",
    "\n",
    "# here are the first six observations\n",
    "num_first = 6\n",
    "print(\"The first %d (out of %d total) observations:\" % (num_first, len(data)))\n",
    "print(*data[:num_first], sep=\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-f5a2e0962ab0924c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Each tuple is an observation of the three random variables $(x_1, x_2, x_3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-5d7be66cc6646665",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "You are to compute $\\log P(D | G)$ for the Bayesian network, $G$, defined below.  We will be using flat, i.e., $Beta(1,1)$, prior distributions for all parameters of the network.  The formula (and its derivation) for this value is given in the Day 24 Structure scoring example.\n",
    "\n",
    "In the Bayesian network instantiated below, you should ignore the parameter values in the CPDs.  The only important aspect of the network is its structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-2eff81a84a81f614",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"toyplot\" id=\"t4ea2d1d9d96e40fb8a229019fc2290f3\" style=\"text-align:center\"><svg class=\"toyplot-canvas-Canvas\" height=\"600px\" id=\"tcf07e11c033245e781fb42d2daa1cadd\" preserveAspectRatio=\"xMidYMid meet\" style=\"background-color:transparent;border-color:#292724;border-style:none;border-width:1.0;fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:Helvetica;font-size:12px;opacity:1.0;stroke:rgb(16.1%,15.3%,14.1%);stroke-opacity:1.0;stroke-width:1.0\" viewBox=\"0 0 600 600\" width=\"600px\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:toyplot=\"http://www.sandia.gov/toyplot\" xmlns:xlink=\"http://www.w3.org/1999/xlink\"><g class=\"toyplot-coordinates-Cartesian\" id=\"t4a6c029534ca4efea0697620e95c716b\"><clipPath id=\"t938dc55d7d544ff0a27b81c42fbc96e1\"><rect height=\"600.0\" width=\"600.0\" x=\"0.0\" y=\"0.0\"></rect></clipPath><g clip-path=\"url(#t938dc55d7d544ff0a27b81c42fbc96e1)\"><g class=\"toyplot-mark-Graph\" id=\"t90e57077e7644f3a847c0dee83a772dd\"><g class=\"toyplot-Edges\"><path d=\"M 81.06681901230881 477.562637615384 L 268.8891882677882 325.2320799324304\" style=\"fill:none;stroke:rgb(0%,0%,0%);stroke-opacity:1.0;stroke-width:1.0\"></path><path d=\"M 518.933195054523 122.43737972889818 L 331.022812225574 274.8394934352881\" style=\"fill:none;stroke:rgb(0%,0%,0%);stroke-opacity:1.0;stroke-width:1.0\"></path><g class=\"toyplot-HeadMarkers\"></g><g class=\"toyplot-MiddleMarkers\"></g><g class=\"toyplot-TailMarkers\"><g style=\"fill:rgb(0%,0%,0%);fill-opacity:1.0;stroke:rgb(0%,0%,0%);stroke-opacity:1.0;stroke-width:1.0\" transform=\"translate(268.8891882677882, 325.2320799324304) rotate(-39.043269938364645) translate(-5.0, 0)\"><polygon points=\"-5.0,5.0 0,-5.0 5.0,5.0\" transform=\"rotate(90)\"></polygon></g><g style=\"fill:rgb(0%,0%,0%);fill-opacity:1.0;stroke:rgb(0%,0%,0%);stroke-opacity:1.0;stroke-width:1.0\" transform=\"translate(331.022812225574, 274.8394934352881) rotate(140.9566980739899) translate(-5.0, 0)\"><polygon points=\"-5.0,5.0 0,-5.0 5.0,5.0\" transform=\"rotate(90)\"></polygon></g></g></g><g class=\"toyplot-Vertices\"><g class=\"toyplot-Datum\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1.0;opacity:1.0;stroke:rgb(0%,0%,0%);stroke-opacity:1.0\" transform=\"translate(50.0, 502.75892219181407)\"><circle r=\"40.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1.0;opacity:1.0;stroke:rgb(0%,0%,0%);stroke-opacity:1.0\" transform=\"translate(550.0, 97.24107780818593)\"><circle r=\"40.0\"></circle></g><g class=\"toyplot-Datum\" style=\"fill:rgb(100%,100%,100%);fill-opacity:1.0;opacity:1.0;stroke:rgb(0%,0%,0%);stroke-opacity:1.0\" transform=\"translate(299.956007280097, 300.03579535600034)\"><circle r=\"40.0\"></circle></g></g><g class=\"toyplot-Labels\"><g class=\"toyplot-Datum\" transform=\"translate(50.0,502.75892219181407)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:12.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.336000000000001\" y=\"3.066\">x1</text></g><g class=\"toyplot-Datum\" transform=\"translate(550.0,97.24107780818593)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:12.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.336000000000001\" y=\"3.066\">x2</text></g><g class=\"toyplot-Datum\" transform=\"translate(299.956007280097,300.03579535600034)\"><text style=\"fill:rgb(16.1%,15.3%,14.1%);fill-opacity:1.0;font-family:helvetica;font-size:12.0px;font-weight:normal;stroke:none;vertical-align:baseline;white-space:pre\" x=\"-6.336000000000001\" y=\"3.066\">x3</text></g></g></g></g></g></svg><div class=\"toyplot-behavior\"><script>(function()\n",
       "{\n",
       "var modules={};\n",
       "modules[\"toyplot/tables\"] = (function()\n",
       "    {\n",
       "        var tables = [];\n",
       "\n",
       "        var module = {};\n",
       "\n",
       "        module.set = function(owner, key, names, columns)\n",
       "        {\n",
       "            tables.push({owner: owner, key: key, names: names, columns: columns});\n",
       "        }\n",
       "\n",
       "        module.get = function(owner, key)\n",
       "        {\n",
       "            for(var i = 0; i != tables.length; ++i)\n",
       "            {\n",
       "                var table = tables[i];\n",
       "                if(table.owner != owner)\n",
       "                    continue;\n",
       "                if(table.key != key)\n",
       "                    continue;\n",
       "                return {names: table.names, columns: table.columns};\n",
       "            }\n",
       "        }\n",
       "\n",
       "        module.get_csv = function(owner, key)\n",
       "        {\n",
       "            var table = module.get(owner, key);\n",
       "            if(table != undefined)\n",
       "            {\n",
       "                var csv = \"\";\n",
       "                csv += table.names.join(\",\") + \"\\n\";\n",
       "                for(var i = 0; i != table.columns[0].length; ++i)\n",
       "                {\n",
       "                  for(var j = 0; j != table.columns.length; ++j)\n",
       "                  {\n",
       "                    if(j)\n",
       "                      csv += \",\";\n",
       "                    csv += table.columns[j][i];\n",
       "                  }\n",
       "                  csv += \"\\n\";\n",
       "                }\n",
       "                return csv;\n",
       "            }\n",
       "        }\n",
       "\n",
       "        return module;\n",
       "    })();\n",
       "modules[\"toyplot/root/id\"] = \"t4ea2d1d9d96e40fb8a229019fc2290f3\";\n",
       "modules[\"toyplot/root\"] = (function(root_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + root_id);\n",
       "    })(modules[\"toyplot/root/id\"]);\n",
       "modules[\"toyplot/canvas/id\"] = \"tcf07e11c033245e781fb42d2daa1cadd\";\n",
       "modules[\"toyplot/canvas\"] = (function(canvas_id)\n",
       "    {\n",
       "        return document.querySelector(\"#\" + canvas_id);\n",
       "    })(modules[\"toyplot/canvas/id\"]);\n",
       "modules[\"toyplot/menus/context\"] = (function(root, canvas)\n",
       "    {\n",
       "        var wrapper = document.createElement(\"div\");\n",
       "        wrapper.innerHTML = \"<ul class='toyplot-context-menu' style='background:#eee; border:1px solid #b8b8b8; border-radius:5px; box-shadow: 0px 0px 8px rgba(0%,0%,0%,0.25); margin:0; padding:3px 0; position:fixed; visibility:hidden;'></ul>\"\n",
       "        var menu = wrapper.firstChild;\n",
       "\n",
       "        root.appendChild(menu);\n",
       "\n",
       "        var items = [];\n",
       "\n",
       "        var ignore_mouseup = null;\n",
       "        function open_menu(e)\n",
       "        {\n",
       "            var show_menu = false;\n",
       "            for(var index=0; index != items.length; ++index)\n",
       "            {\n",
       "                var item = items[index];\n",
       "                if(item.show(e))\n",
       "                {\n",
       "                    item.item.style.display = \"block\";\n",
       "                    show_menu = true;\n",
       "                }\n",
       "                else\n",
       "                {\n",
       "                    item.item.style.display = \"none\";\n",
       "                }\n",
       "            }\n",
       "\n",
       "            if(show_menu)\n",
       "            {\n",
       "                ignore_mouseup = true;\n",
       "                menu.style.left = (e.clientX + 1) + \"px\";\n",
       "                menu.style.top = (e.clientY - 5) + \"px\";\n",
       "                menu.style.visibility = \"visible\";\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        function close_menu()\n",
       "        {\n",
       "            menu.style.visibility = \"hidden\";\n",
       "        }\n",
       "\n",
       "        function contextmenu(e)\n",
       "        {\n",
       "            open_menu(e);\n",
       "        }\n",
       "\n",
       "        function mousemove(e)\n",
       "        {\n",
       "            ignore_mouseup = false;\n",
       "        }\n",
       "\n",
       "        function mouseup(e)\n",
       "        {\n",
       "            if(ignore_mouseup)\n",
       "            {\n",
       "                ignore_mouseup = false;\n",
       "                return;\n",
       "            }\n",
       "            close_menu();\n",
       "        }\n",
       "\n",
       "        function keydown(e)\n",
       "        {\n",
       "            if(e.key == \"Escape\" || e.key == \"Esc\" || e.keyCode == 27)\n",
       "            {\n",
       "                close_menu();\n",
       "            }\n",
       "        }\n",
       "\n",
       "        canvas.addEventListener(\"contextmenu\", contextmenu);\n",
       "        canvas.addEventListener(\"mousemove\", mousemove);\n",
       "        document.addEventListener(\"mouseup\", mouseup);\n",
       "        document.addEventListener(\"keydown\", keydown);\n",
       "\n",
       "        var module = {};\n",
       "        module.add_item = function(label, show, activate)\n",
       "        {\n",
       "            var wrapper = document.createElement(\"div\");\n",
       "            wrapper.innerHTML = \"<li class='toyplot-context-menu-item' style='background:#eee; color:#333; padding:2px 20px; list-style:none; margin:0; text-align:left;'>\" + label + \"</li>\"\n",
       "            var item = wrapper.firstChild;\n",
       "\n",
       "            items.push({item: item, show: show});\n",
       "\n",
       "            function mouseover()\n",
       "            {\n",
       "                this.style.background = \"steelblue\";\n",
       "                this.style.color = \"white\";\n",
       "            }\n",
       "\n",
       "            function mouseout()\n",
       "            {\n",
       "                this.style.background = \"#eee\";\n",
       "                this.style.color = \"#333\";\n",
       "            }\n",
       "\n",
       "            function choose_item(e)\n",
       "            {\n",
       "                close_menu();\n",
       "                activate();\n",
       "\n",
       "                e.stopPropagation();\n",
       "                e.preventDefault();\n",
       "            }\n",
       "\n",
       "            item.addEventListener(\"mouseover\", mouseover);\n",
       "            item.addEventListener(\"mouseout\", mouseout);\n",
       "            item.addEventListener(\"mouseup\", choose_item);\n",
       "            item.addEventListener(\"contextmenu\", choose_item);\n",
       "\n",
       "            menu.appendChild(item);\n",
       "        };\n",
       "        return module;\n",
       "    })(modules[\"toyplot/root\"],modules[\"toyplot/canvas\"]);\n",
       "modules[\"toyplot/io\"] = (function()\n",
       "    {\n",
       "        var module = {};\n",
       "        module.save_file = function(mime_type, charset, data, filename)\n",
       "        {\n",
       "            var uri = \"data:\" + mime_type + \";charset=\" + charset + \",\" + data;\n",
       "            uri = encodeURI(uri);\n",
       "\n",
       "            var link = document.createElement(\"a\");\n",
       "            if(typeof link.download != \"undefined\")\n",
       "            {\n",
       "              link.href = uri;\n",
       "              link.style = \"visibility:hidden\";\n",
       "              link.download = filename;\n",
       "\n",
       "              document.body.appendChild(link);\n",
       "              link.click();\n",
       "              document.body.removeChild(link);\n",
       "            }\n",
       "            else\n",
       "            {\n",
       "              window.open(uri);\n",
       "            }\n",
       "        };\n",
       "        return module;\n",
       "    })();\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t90e57077e7644f3a847c0dee83a772dd\",\"vertex_data\",\"graph vertex data\",[\"x\", \"y\"],[[-0.47688788527822734, 0.5479202621958376, 0.03542602026323291], [-0.3951972742260698, 0.43595870751485427, 0.020307349899450464]],\"toyplot\");\n",
       "(function(tables, context_menu, io, owner_id, key, label, names, columns, filename)\n",
       "        {\n",
       "            tables.set(owner_id, key, names, columns);\n",
       "\n",
       "            var owner = document.querySelector(\"#\" + owner_id);\n",
       "            function show_item(e)\n",
       "            {\n",
       "                return owner.contains(e.target);\n",
       "            }\n",
       "\n",
       "            function choose_item()\n",
       "            {\n",
       "                io.save_file(\"text/csv\", \"utf-8\", tables.get_csv(owner_id, key), filename + \".csv\");\n",
       "            }\n",
       "\n",
       "            context_menu.add_item(\"Save \" + label + \" as CSV\", show_item, choose_item);\n",
       "        })(modules[\"toyplot/tables\"],modules[\"toyplot/menus/context\"],modules[\"toyplot/io\"],\"t90e57077e7644f3a847c0dee83a772dd\",\"edge_data\",\"graph edge data\",[\"source\", \"target\"],[[0, 1], [2, 2]],\"toyplot\");\n",
       "})();</script></div></div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "random_variables = [\"x1\", \"x2\", \"x3\"]\n",
    "g = bayesian_network.BayesianNetwork(random_variables)\n",
    "\n",
    "g.set_cpd(\"x1\",\n",
    "          [], [0, 1],\n",
    "          {(): [0.75, 0.25]})\n",
    "g.set_cpd(\"x2\",\n",
    "          [], [0, 1],\n",
    "          {(): [0.75, 0.25]})\n",
    "g.set_cpd(\"x3\",\n",
    "          [\"x1\", \"x2\"], [0, 1],\n",
    "          {(0, 0): [0.9, 0.1],\n",
    "           (0, 1): [0.3, 0.7],\n",
    "           (1, 0): [0.2, 0.8],\n",
    "           (1, 1): [0.1, 0.9]})\n",
    "\n",
    "g.plot()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-88e98833a7181917",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "To answer this question, assign the value of $\\log P(D | G)$ for this graph and the given dataset to the variable `log_prob_data_given_graph` below.  You will likely want to make use of the function `logbinom` provided below, which computes the natural logarithm of a [binomial coefficient](http://mathworld.wolfram.com/BinomialCoefficient.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-97be6985fc2a1654",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def logbinom(n, k):\n",
    "    \"\"\"The natural logarithm of the binomial coefficient (n choose k)\"\"\"\n",
    "    return math.lgamma(n + 1) - math.lgamma(k + 1) - math.lgamma(n - k + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-0e8d6f0b81aa96c6",
     "locked": false,
     "schema_version": 1,
     "solution": true
    },
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{(): [733, 267]},\n",
      " {(): [738, 262]},\n",
      " {(0, 0): [479, 63],\n",
      "  (0, 1): [177, 14],\n",
      "  (1, 0): [56, 140],\n",
      "  (1, 1): [22, 49]}]\n"
     ]
    }
   ],
   "source": [
    "### BEGIN SOLUTION TEMPLATE=log_prob_data_given_graph=?\n",
    "import itertools\n",
    "import pprint\n",
    "\n",
    "def sufficient_statistics(bn, data):\n",
    "    ss = []\n",
    "    for i in range(bn.num_vertices()):\n",
    "        parent_possible_values = [bn.possible_values[j] for j in bn.parents(i)]\n",
    "        vertex_ss = {parent_vals: [0] * len(bn.possible_values[i])\n",
    "                     for parent_vals in itertools.product(*parent_possible_values)}\n",
    "        ss.append(vertex_ss)\n",
    "\n",
    "    for values in data:\n",
    "        encoded_values = bn.encode_values(values)\n",
    "        for i, value in enumerate(encoded_values):\n",
    "            parent_values = tuple(encoded_values[j] for j in bn.parents(i))\n",
    "            ss[i][parent_values][value] += 1\n",
    "    return ss\n",
    "\n",
    "def model_evidence(bn, data):\n",
    "    \"\"\"assumes binary random variables\"\"\"\n",
    "    ss = sufficient_statistics(bn, data)\n",
    "    me = 0\n",
    "    for i, vertex_ss in enumerate(ss):\n",
    "        for count_vector in vertex_ss.values():\n",
    "            total_counts = sum(count_vector)\n",
    "            me -= (math.log(total_counts + 1) + logbinom(total_counts, count_vector[0]))\n",
    "    return me\n",
    "\n",
    "log_prob_data_given_graph = model_evidence(g, data)\n",
    "pprint.pprint(sufficient_statistics(g, data), width=20)\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "prob_data_given_graph",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# test for prob_data_given_graph\n",
    "assert isinstance(log_prob_data_given_graph, float)\n",
    "assert -2000 < log_prob_data_given_graph < 0\n",
    "### BEGIN HIDDEN TESTS\n",
    "assert round(log_prob_data_given_graph) == -1579\n",
    "### END HIDDEN TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-11a03b7a24b6bd67",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## PROBLEM 2: Counting the number of possible Bayesian network structures (1 POINT)\n",
    "For a Bayesian network of *three* random variables (like the one in Problem 1), how many possible Bayesian network structures are there?  Assign your answer to the variable `num_3var_networks` below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-6ba838b3200968c2",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "### BEGIN SOLUTION TEMPLATE=num_3var_networks=?\n",
    "num_3var_networks = 25\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true,
    "nbgrader": {
     "grade": true,
     "grade_id": "num_3var_networks",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# test for num_3var_networks\n",
    "assert isinstance(num_3var_networks, int)\n",
    "assert num_3var_networks > 0\n",
    "### BEGIN HIDDEN TESTS\n",
    "assert num_3var_networks == 25\n",
    "### END HIDDEN TESTS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-13bebab3829908af",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## BONUS PROBLEM: Find the Bayesian network structure with maximum score\n",
    "For the dataset in Problem 1, find the Bayesian network structure that gives the maximum score (model evidence)."
   ]
  }
 ],
 "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
}