probability-4e.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "import itertools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Bayesian Networks\n",
    "\n",
    "A Bayesian network, or Bayes net for short, is a data structure to represent a joint probability distribution, and do inference on it. For example, here is a network with five nodes, each with its conditional probability table, and with arrows from parent to child variables. The story, from Judea Pearl, is that Judea has a burglar alarm, and it can be triggered by either a burglary or an earthquake. If the alarm sounds, one or both of Judea's neighbors, John and Mary, might call him to let him know.\n",
    "\n",
    "<p><img src=\"http://norvig.com/ipython/burglary2.jpg\">\n",
    "\n",
    "This topic of Bayes nets can be confusing, because there are many different concepts to keep track of:\n",
    "\n",
    "* `BayesNet`: A graph, where each node represents a variable, and is pointed to by zero or more *parents*. (See diagram above.)\n",
    "\n",
    "* `Variable`: A random variable; the ovals in the diagram above. We will only allow variables with a finite discrete domain of possible values; in the diagram all the variables are Boolean, meaning their domain is the set $\\{t, f\\}$. The value of a variable depends on the value of the parents, in a probabilistic way specified by the variable's conditional probability table. Given the parents, the variable is independent of all the other variables. For example, if I know whether *Alarm* is true or false, then I know the probability of *JohnCalls*, and evidence about the other variables won't give me any more information about *JohnCalls*.\n",
    "\n",
    "* `ProbDist`: A probability distribution enumerates each possible value in the domain of a variable,\n",
    "and the probability of that value. For example, `{True: 0.95, False: 0.05}` is a probability distribution for a Boolean variable.\n",
    "\n",
    "* `CPTable`: A conditional probability table is a a mapping, `{tuple: ProbDist, ...}`, where each tuple lists the values of each of the parent variables, in order, and the probability distribution says what the possible outcomes are for the variable, given those values of the parents. For example, for the variable *Alarm*, the top row of the `CPTable` says \"*t, t*, .95\", which means that when *Burglary* is true and *Earthquake* is true, the probability of *Alarm* being true is .95. Think of this row entry as an abbreviation that makes sense for Boolean variables, but to accomodate non-Boolean variables, we will represent this in the more general format: `{(True, True): {True: 0.95, False: 0.05}}`.\n",
    "\n",
    "* `Evidence`: A mapping, `{Variable: value, ...}`, which denotes which variables we have observed known values for.\n",
    "\n",
    "We will introduce implementations of these concepts:\n",
    "\n",
    "# `BayesNet`\n",
    "\n",
    "A `BayesNet` is a graph of variables, where each variable is specified by a triple of `(name, parentnames, cpt)`, where the name is a string, the `parentnames` is a sequence of strings, and the CPT is in a format we will explain soon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "button": false,
    "collapsed": true,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "class BayesNet(object):\n",
    "    \"Bayesian network: a graph with an ordered list of variables.\"\n",
    "     \n",
    "    def __init__(self): \n",
    "        self.variables = [] # List of variables, in parent-first topological order\n",
    "        self.lookup = {}    # Mapping of {variable_name: variable} pairs\n",
    "            \n",
    "    def add(self, name, parentnames, cpt):\n",
    "        \"Add a new Variable to the BayesNet. Parentnames must already have been added.\"\n",
    "        parents = [self.lookup[name] for name in parentnames]\n",
    "        var = Variable(name, parents, cpt)\n",
    "        self.variables.append(var)\n",
    "        self.lookup[name] = var\n",
    "        return self"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# `Variable` \n",
    "\n",
    "The `Variable` data structure holds a name, a list of parents (which are actual variables, not names), and a conditional probability table. The order of the parent variables is important, because you will have to use the same order in the CPT. For convenience, we also store the* domain* of the variable: the set of possible values (all our variables are discrete). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "class Variable(object):\n",
    "    \"A discrete random variable in a BayesNet.\"\n",
    "    \n",
    "    def __init__(self, name, parents, cpt):\n",
    "        \"A variable has a name, list of parent variables, and a CPT.\"\n",
    "        self.name    = name\n",
    "        self.parents = parents\n",
    "        self.cpt     = CPT(cpt, parents)\n",
    "        self.domain  = set(v for row in self.cpt for v in self.cpt[row])\n",
    "        \n",
    "    def P(self, evidence):\n",
    "        \"The full probability distribution for P(variable | evidence).\"\n",
    "        return self.cpt[tuple(evidence[var] for var in self.parents)]\n",
    "\n",
    "    def __repr__(self): return self.name"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "#  `ProbDist` and `Evidence`\n",
    "\n",
    "A `ProbDist` is a mapping of `{outcome: probability}` for every outcome of a random variable. You can give it the same arguments that you would give to the `dict` constructor. As a shortcut for Boolean random variables, you can say `ProbDist(0.2)` instead of `ProbDist({False: 0.8, True: 0.2})`.\n",
    "\n",
    "`Evidence` is just a dict of `{variable: value}` pairs, describing the exact values for a set of variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "class ProbDist(dict):\n",
    "    \"A Probability Distribution; an {outcome: probability} mapping.\"\n",
    "    def __init__(self, mapping=(), **kwargs):\n",
    "        if isinstance(mapping, float):\n",
    "            mapping = {True: mapping, False: 1 - mapping}\n",
    "        self.update(mapping, **kwargs)\n",
    "        total = sum(self.values())\n",
    "        normalize(self)\n",
    "        \n",
    "def normalize(dic):\n",
    "    \"Make sum to values of dic sum to 1.0; assert no negative values.\"\n",
    "    total = sum(dic.values())\n",
    "    for key in dic:\n",
    "        dic[key] = dic[key] / total\n",
    "        assert dic[key] >= 0\n",
    "            \n",
    "class Evidence(dict): pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'heads': 0.6, 'tails': 0.4}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An example ProbDist\n",
    "ProbDist(heads=6, tails=4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.75, True: 0.25}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# A Boolean ProbDist\n",
    "ProbDist(0.25) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "#  `CPT`: Conditional Probability Table\n",
    "\n",
    "A `CPT` is a mapping from tuples of parent values to probability distributions. Every possible tuple must be represented in the table. We allow shortcuts for the case of `CPT`s with zeron or one parent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "class CPT(dict):\n",
    "    \"\"\"A mapping of {row: ProbDist, ...} where each row is a tuple\n",
    "    of possible values of the parent variables.\"\"\"\n",
    "    \n",
    "    def __init__(self, data, parents=None):\n",
    "        \"\"\"Provides two shortcuts for writing a Conditional Probability Table. \n",
    "        With no parents, CPT(dist) =>  CPT({(): dist}).\n",
    "        With one parent, CPT({val: dist,...}) => CPT({(val,): dist,...}).\"\"\"\n",
    "        def Tuple(row): return row if isinstance(row, tuple) else (row,)\n",
    "        if not parents and (not isinstance(data, dict) or set(data.keys()) != {()}):\n",
    "            data = {(): data}\n",
    "        for row in data:\n",
    "            self[Tuple(row)] = ProbDist(data[row])\n",
    "        if parents:\n",
    "            assert set(self) == set(expected_tuples(parents)), (\n",
    "           \"CPT must handle all possibile tuples of parent values\")\n",
    "\n",
    "def expected_tuples(parents):\n",
    "    \"The set of tuples of one value from each parent (in order).\"\n",
    "    return set(itertools.product(*[p.domain for p in parents]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(): {False: 0.75, True: 0.25}}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# An example of a CPT with no parents, and thus one row with an empty tuple\n",
    "CPT({(): 0.25})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# An Example Bayes Net\n",
    "\n",
    "Now we are ready to define the network from the burglary alarm scenario:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "T = True\n",
    "F = False\n",
    "\n",
    "alarm_net = (BayesNet()\n",
    "    .add('Burglary', [], 0.001)\n",
    "    .add('Earthquake', [], 0.002)\n",
    "    .add('Alarm', ['Burglary', 'Earthquake'],\n",
    "         {(T, T): 0.95, (T, F): 0.94, (F, T): 0.29, (F, F): 0.001})\n",
    "    .add('JohnCalls', ['Alarm'], {T: 0.90, F: 0.05})\n",
    "    .add('MaryCalls', ['Alarm'], {T: 0.70, F:0.01}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "button": false,
    "collapsed": true,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "globals().update(alarm_net.lookup)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(False, False): {False: 0.999, True: 0.001},\n",
       " (False, True): {False: 0.71, True: 0.29},\n",
       " (True, False): {False: 0.06000000000000005, True: 0.94},\n",
       " (True, True): {False: 0.050000000000000044, True: 0.95}}"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Alarm.cpt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.999, True: 0.001}"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Alarm.P({Burglary:False, Earthquake:False})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.001"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Alarm.P({Burglary:False, Earthquake:False})[True]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Inference in Bayes Nets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "def enumeration_ask(X, e, bn):\n",
    "    \"Given evidence e, ask what the probability distribution is for X in bn.\"\n",
    "    assert X not in e, \"Query variable must be distinct from evidence\"\n",
    "    Q = {}\n",
    "    for xi in X.domain:\n",
    "        Q[xi] = enumerate_all_vars(bn.variables, extend(e, X, xi), bn)\n",
    "    return ProbDist(Q)\n",
    "\n",
    "def enumerate_all_vars(vars, e, bn):\n",
    "    \"\"\"Return the sum of those entries in P(vars | e_{others})\n",
    "    consistent with e, where P is the joint distribution represented\n",
    "    by bn, and e_{others} means e restricted to bn's other variables\n",
    "    (the ones other than vars). Parents must precede children in vars.\"\"\"\n",
    "    if not vars:\n",
    "        return 1.0\n",
    "    Y, rest = vars[0], vars[1:]\n",
    "    if Y in e:\n",
    "        y = e[Y]\n",
    "        return P(Y, e, y) * enumerate_all_vars(rest, e, bn)\n",
    "    else:\n",
    "        return sum(P(Y, e, y) * enumerate_all_vars(rest, extend(e, Y, y), bn)\n",
    "                   for y in Y.domain)\n",
    "    \n",
    "def extend(dic, var, val):\n",
    "    \"\"\"Return a copy of the dict, with {var: val} added.\"\"\"\n",
    "    dic2 = dic.copy()\n",
    "    dic2[var] = val\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.7158281646356071, True: 0.2841718353643929}"
      ]
     },
     "execution_count": 185,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumeration_ask(Burglary, {JohnCalls:T, MaryCalls:T}, alarm_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.9438825459610851, True: 0.056117454038914924}"
      ]
     },
     "execution_count": 189,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumeration_ask(Burglary, {MaryCalls:T}, alarm_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.8499098822502404, True: 0.15009011774975956}"
      ]
     },
     "execution_count": 190,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumeration_ask(Alarm, {MaryCalls:T}, alarm_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.9641190847135443, True: 0.03588091528645573}"
      ]
     },
     "execution_count": 191,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumeration_ask(Earthquake, {MaryCalls:T}, alarm_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.7029390000000001, True: 0.29706099999999996}"
      ]
     },
     "execution_count": 193,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumeration_ask(JohnCalls, {Earthquake:T}, alarm_net)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "button": false,
    "collapsed": true,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "def enumeration_ask(X, e, bn):\n",
    "    \"Given evidence e, ask what the probability distribution is for X in bn.\"\n",
    "    assert X not in e, \"Query variable must be distinct from evidence\"\n",
    "    Q = {}\n",
    "    for xi in X.domain:\n",
    "        Q[xi] = enumerate_all_vars(bn.variables, extend(e, X, xi), bn)\n",
    "    return ProbDist(Q)\n",
    "\n",
    "def enumerate_all_vars(vars, e, bn):\n",
    "    \"\"\"Return the sum of those entries in P(vars | e_{others})\n",
    "    consistent with e, where P is the joint distribution represented\n",
    "    by bn, and e_{others} means e restricted to bn's other variables\n",
    "    (the ones other than vars). Parents must precede children in vars.\"\"\"\n",
    "    if not vars:\n",
    "        return 1.0\n",
    "    Y, rest = vars[0], vars[1:]\n",
    "    if Y in e:\n",
    "        y = e[Y]\n",
    "        return P(Y, e, y) * enumerate_all_vars(rest, e, bn)\n",
    "    else:\n",
    "        return sum(P(Y, e, y) * enumerate_all_vars(rest, extend(e, Y, y), bn)\n",
    "                   for y in Y.domain)\n",
    "    \n",
    "def extend(dic, var, val):\n",
    "    \"\"\"Return a copy of the dict, with {var: val} added.\"\"\"\n",
    "    dic2 = dic.copy()\n",
    "    dic2[var] = val\n",
    "    return dic2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Full Joint ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({(False, False, False, False, False): 0.9367427006189999,\n",
       "  (False, False, False, False, True): 0.009462047481,\n",
       "  (False, False, False, True, False): 0.049302247401000004,\n",
       "  (False, False, False, True, True): 0.0004980024990000001,\n",
       "  (False, False, True, False, False): 2.9910059999999997e-05,\n",
       "  (False, False, True, False, True): 6.979013999999998e-05,\n",
       "  (False, False, True, True, False): 0.00026919054,\n",
       "  (False, False, True, True, True): 0.0006281112599999999,\n",
       "  (False, True, False, False, False): 0.00133417449,\n",
       "  (False, True, False, False, True): 1.3476510000000001e-05,\n",
       "  (False, True, False, True, False): 7.021971e-05,\n",
       "  (False, True, False, True, True): 7.0929e-07,\n",
       "  (False, True, True, False, False): 1.73826e-05,\n",
       "  (False, True, True, False, True): 4.055939999999999e-05,\n",
       "  (False, True, True, True, False): 0.00015644340000000003,\n",
       "  (False, True, True, True, True): 0.0003650346,\n",
       "  (True, False, False, False, False): 5.631714000000005e-05,\n",
       "  (True, False, False, False, True): 5.688600000000004e-07,\n",
       "  (True, False, False, True, False): 2.9640600000000024e-06,\n",
       "  (True, False, False, True, True): 2.994000000000003e-08,\n",
       "  (True, False, True, False, False): 2.8143599999999996e-05,\n",
       "  (True, False, True, False, True): 6.566839999999998e-05,\n",
       "  (True, False, True, True, False): 0.00025329240000000004,\n",
       "  (True, False, True, True, True): 0.0005910156,\n",
       "  (True, True, False, False, False): 9.405000000000008e-08,\n",
       "  (True, True, False, False, True): 9.500000000000009e-10,\n",
       "  (True, True, False, True, False): 4.950000000000005e-09,\n",
       "  (True, True, False, True, True): 5.0000000000000054e-11,\n",
       "  (True, True, True, False, False): 5.699999999999999e-08,\n",
       "  (True, True, True, False, True): 1.3299999999999993e-07,\n",
       "  (True, True, True, True, False): 5.130000000000001e-07,\n",
       "  (True, True, True, True, True): 1.197e-06},\n",
       " 32,\n",
       " 0.9999999999999999)"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def full_joint(net):\n",
    "    rows = itertools.product(*[var.domain for var in net.variables])\n",
    "    return {row: joint_probability(row, net)\n",
    "            for row in rows}\n",
    "\n",
    "def joint_probability(row, net):\n",
    "    evidence = dict(zip(net.variables, row))\n",
    "    def Pvar(var): \n",
    "        return var.cpt[tuple(evidence[v] for v in var.parents)][evidence[var]]\n",
    "    return prod(Pvar(v) for v in net.variables)\n",
    "    \n",
    "def prod(numbers):\n",
    "    product = 1\n",
    "    for x in numbers:\n",
    "        product *= x\n",
    "    return product\n",
    "\n",
    "j = full_joint(alarm_net)\n",
    "j, len(j), sum(j.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({(False, False, False, True, True): 0.23895323731595236,\n",
       "  (False, False, True, True, True): 0.3013824614795795,\n",
       "  (False, True, False, True, True): 0.0003403339180750413,\n",
       "  (False, True, True, True, True): 0.17515213192200013,\n",
       "  (True, False, False, True, True): 1.4365911696438334e-05,\n",
       "  (True, False, True, True, True): 0.2835830968876924,\n",
       "  (True, True, False, True, True): 2.399116849772601e-08,\n",
       "  (True, True, True, True, True): 0.00057434857383556},\n",
       " 8,\n",
       " 1.0)"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def joint_distribution(net, evidence={}):\n",
    "    \"Given a Bayes net and some evidence variables, return the joint distribution over all variables.\"\n",
    "    values = [({evidence[var]} if var in evidence else var.domain)\n",
    "              for var in net.variables]\n",
    "    return ProbDist({row: joint_probability(row, net)\n",
    "                     for row in itertools.product(*values)})\n",
    "\n",
    "def joint_probability(row, net):\n",
    "    evidence = dict(zip(net.variables, row))\n",
    "    def Pvar(var): \n",
    "        return var.cpt[tuple(evidence[v] for v in var.parents)][evidence[var]]\n",
    "    return prod(Pvar(v) for v in net.variables)\n",
    "    \n",
    "def prod(numbers):\n",
    "    product = 1\n",
    "    for x in numbers:\n",
    "        product *= x\n",
    "    return product\n",
    "\n",
    "j = joint_distribution(alarm_net, {JohnCalls:True, MaryCalls:True})\n",
    "j, len(j), sum(j.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Burglary, Earthquake, Alarm, JohnCalls, MaryCalls]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alarm_net.variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'tests pass'"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def tests():\n",
    "    ProbDist({'heads': 1, 'tails': 1}) == ProbDist(heads=2, tails=2) == {'heads': 0.5, 'tails': 0.5}\n",
    "    ProbDist(0.2) == ProbDist({False: 0.8, True: 0.2})\n",
    "    \n",
    "    CPT(0.2, []) == CPT({(): {False: 0.8, True: 0.2}}, [])\n",
    "    \n",
    "    return 'tests pass'\n",
    "    \n",
    "tests()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "The entries in a `CPTable` are all of the form `{(parent_value, ...): ProbDist}`. You could create such a table yourself, but we provide the function `CPT` to make it slightly easier. We provide functions to verify CPTs and ProbDists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "button": false,
    "collapsed": true,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "The one method, `P`, gives the probability distribution for the variable, given evidence that specifies the values of all the parents.\n",
    "(If you don't know the values for all the parents, later we will see that `enumeration_ask` can still give you an answer.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{False: 0.7, True: 0.3}"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ProbDist(.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "T = True \n",
    "F = False\n",
    "\n",
    "def CPT(data, \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "button": false,
    "collapsed": false,