\n", "\n", "We implement this with the help of seven Python classes:\n", "\n", "\n", "## `BayesNet()`\n", "\n", "A `BayesNet` is a graph (as in the diagram above) where each node represents a random variable, and the edges are parent→child links. You can construct an empty graph with `BayesNet()`, then add variables one at a time with the method call `.add(`*variable_name, parent_names, cpt*`)`, where the names are strings, and each of the `parent_names` must already have been `.add`ed.\n", "\n", "## `Variable(`*name, cpt, parents*`)`\n", "\n", "A random variable; the ovals in the diagram above. The value of a variable depends on the value of the parents, in a probabilistic way specified by the variable's conditional probability table (CPT). 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*. Each row of the CPT uses the same order of variables as the list of parents.\n", "We will only allow variables with a finite discrete domain; not continuous values. \n", "\n", "## `ProbDist(`*mapping*`)`
`Factor(`*mapping*`)`\n", "\n", "A probability distribution is a mapping of `{outcome: probability}` for every outcome of a random variable. \n", "You can give `ProbDist` the same arguments that you would give to the `dict` initializer, for example\n", "`ProbDist(sun=0.6, rain=0.1, cloudy=0.3)`.\n", "As a shortcut for Boolean Variables, you can say `ProbDist(0.95)` instead of `ProbDist({T: 0.95, F: 0.05})`. \n", "In a probability distribution, every value is between 0 and 1, and the values sum to 1.\n", "A `Factor` is similar to a probability distribution, except that the values need not sum to 1. Factors\n", "are used in the variable elimination inference method.\n", "\n", "## `Evidence(`*mapping*`)`\n", "\n", "A mapping of `{Variable: value, ...}` pairs, describing the exact values for a set of variables—the things we know for sure.\n", "\n", "## `CPTable(`*rows, parents*`)`\n", "\n", "A conditional probability table (or *CPT*) describes the probability of each possible outcome value of a random variable, given the values of the parent variables. A `CPTable` is a a mapping, `{tuple: probdist, ...}`, where each tuple lists the values of each of the parent variables, in order, and each probability distribution says what the possible outcomes are, given those values of the parents. The `CPTable` for *Alarm* in the diagram above would be represented as follows:\n", "\n", " CPTable({(T, T): .95,\n", " (T, F): .94,\n", " (F, T): .29,\n", " (F, F): .001},\n", " [Burglary, Earthquake])\n", " \n", "How do you read this? Take the second row, \"`(T, F): .94`\". This means that when the first parent (`Burglary`) is true, and the second parent (`Earthquake`) is fale, then the probability of `Alarm` being true is .94. Note that the .94 is an abbreviation for `ProbDist({T: .94, F: .06})`.\n", " \n", "## `T = Bool(True); F = Bool(False)`\n", "\n", "When I used `bool` values (`True` and `False`), it became hard to read rows in CPTables, because the columns didn't line up:\n", "\n", " (True, True, False, False, False)\n", " (False, False, False, False, True)\n", " (True, False, False, True, True)\n", " \n", "Therefore, I created the `Bool` class, with constants `T` and `F` such that `T == True` and `F == False`, and now rows are easier to read:\n", "\n", " (T, T, F, F, F)\n", " (F, F, F, F, T)\n", " (T, F, F, T, T)\n", " \n", "Here is the code for these classes:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "button": false, "collapsed": true, "deletable": true, "new_sheet": false, "run_control": { "read_only": false } }, "outputs": [], "source": [ "from collections import defaultdict, Counter\n", "import itertools\n", "import math\n", "import random\n", "\n", "class BayesNet(object):\n", " \"Bayesian network: a graph of variables connected by parent links.\"\n", " \n", " def __init__(self): \n", " self.variables = [] # List of variables, in parent-first topological sort 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 have been added previously.\"\n", " parents = [self.lookup[name] for name in parentnames]\n", " var = Variable(name, cpt, parents)\n", " self.variables.append(var)\n", " self.lookup[name] = var\n", " return self\n", " \n", "class Variable(object):\n", " \"A discrete random variable; conditional on zero or more parent Variables.\"\n", " \n", " def __init__(self, name, cpt, parents=()):\n", " \"A variable has a name, list of parent variables, and a Conditional Probability Table.\"\n", " self.__name__ = name\n", " self.parents = parents\n", " self.cpt = CPTable(cpt, parents)\n", " self.domain = set(itertools.chain(*self.cpt.values())) # All the outcomes in the CPT\n", " \n", " def __repr__(self): return self.__name__\n", " \n", "class Factor(dict): \"An {outcome: frequency} mapping.\"\n", "\n", "class ProbDist(Factor):\n", " \"\"\"A Probability Distribution is an {outcome: probability} mapping. \n", " The values are normalized to sum to 1.\n", " ProbDist(0.75) is an abbreviation for ProbDist({T: 0.75, F: 0.25}).\"\"\"\n", " def __init__(self, mapping=(), **kwargs):\n", " if isinstance(mapping, float):\n", " mapping = {T: mapping, F: 1 - mapping}\n", " self.update(mapping, **kwargs)\n", " normalize(self)\n", " \n", "class Evidence(dict): \n", " \"A {variable: value} mapping, describing what we know for sure.\"\n", " \n", "class CPTable(dict):\n", " \"A mapping of {row: ProbDist, ...} where each row is a tuple of values of the parent variables.\"\n", " \n", " def __init__(self, mapping, parents=()):\n", " \"\"\"Provides two shortcuts for writing a Conditional Probability Table. \n", " With no parents, CPTable(dist) means CPTable({(): dist}).\n", " With one parent, CPTable({val: dist,...}) means CPTable({(val,): dist,...}).\"\"\"\n", " if len(parents) == 0 and not (isinstance(mapping, dict) and set(mapping.keys()) == {()}):\n", " mapping = {(): mapping}\n", " for (row, dist) in mapping.items():\n", " if len(parents) == 1 and not isinstance(row, tuple): \n", " row = (row,)\n", " self[row] = ProbDist(dist)\n", "\n", "class Bool(int):\n", " \"Just like `bool`, except values display as 'T' and 'F' instead of 'True' and 'False'\"\n", " __str__ = __repr__ = lambda self: 'T' if self else 'F'\n", " \n", "T = Bool(True)\n", "F = Bool(False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And here are some associated functions:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def P(var, evidence={}):\n", " \"The probability distribution for P(variable | evidence), when all parent variables are known (in evidence).\"\n", " row = tuple(evidence[parent] for parent in var.parents)\n", " return var.cpt[row]\n", "\n", "def normalize(dist):\n", " \"Normalize a {key: value} distribution so values sum to 1.0. Mutates dist and returns it.\"\n", " total = sum(dist.values())\n", " for key in dist:\n", " dist[key] = dist[key] / total\n", " assert 0