Lab 5: Bayes Nets

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(Getting information from a BayesNet)
(Iterating over a BayesNet: topo sort can't take list of vars)
Line 144: Line 144:
== Iterating over a BayesNet ==
== Iterating over a BayesNet ==
-
<tt>net.</tt>'''topological_sort'''(<tt>variables=None</tt>): Returns an ordered list of variables such that each variable
+
<tt>net.</tt>'''topological_sort'''(<!--<tt>variables=None</tt>-->): Returns an ordered list of all variables such that each variable
-
comes after all its parents. If the list <tt>variables</tt>
+
comes after all its parents. <!--If the list <tt>variables</tt> isn't specified, uses the list of all variables.-->
-
isn't specified, uses the list of all variables.
+

Revision as of 19:24, 27 November 2015

Contents


This is an entirely optional lab for you to practice manipulating Bayes nets and probabilities computationally. This lab is worth no credit whatsoever. There will be no online tests. If you would like to provide feedback to improve this new lab for next year, see below.

To get the code...

Your answers will go in the main file lab_bayes.py.

Problems

Descendants and non-descendants

Implement a function that returns a set containing the descendants of the variable in the network. This set should include the variable's children, its children's children, etc.

def get_descendants(net, var)

Implement a function that returns a set containing the non-descendants of the variable. Note that a variable is neither a descendant nor a non-descendant of itself.

def get_nondescendants(net, var):


Probability

Hypotheses and givens are expressed as dicts assigning variables to values. For example, P(A=False | B=True, C=False) is represented as the two dicts:

hypothesis = {A: False}
givens = {B: True, C: False}

First, write a helper function:

def remove_nondescendants_given_parents(net, var, givens):

If all parents of var are given, this function returns a new dict of givens with var's non-descendants (except parents) removed. Otherwise, the function returns False. In either case, it should not modify the original dict of givens.

Hint: The set method .issubset may be useful here.


Now, we will implement a function that looks up probabilities in the net's conditional probability tables:

def probability_lookup(net, hypothesis, givens=None):

If the probability can be looked up directly (or reduced to a form that can be looked up directly) in the network's probability tables, return it; otherwise return None.

Remember that you can simplify some probability expressions using the independence assumptions of the Bayes net.

Hint: Note that net.probability will raise a ValueError if the hypothesis contains multiple variables, or if the givens do not contain exactly the parents of var. You may want to use a try/except block to catch this error and decide when to return None.


Given a dict assigning every variable in the network to a value, compute its joint probability (e.g. {"A": True, "B": False, "C": False}):

probability_joint(net, hypothesis)

Use the chain rule to compute joint probabilities in terms of values produced by probability_lookup. You may assume that the hypothesis represents a valid joint probability (that is, contains every variable in the Bayes net).


A marginal probability can be represented as a sum of joint probabilities:

probability_marginal(net, hypothesis)

Compute marginal probabilities as sums of joint probabilities produced by probability_joint.

Hint 1: The BayesNet method net.combinations may be useful. (See the API below for details.)

Hint 2: To combine two dictionaries d1 and d2 to form a third dict d3, you can use d3 = dict(d1, **d2).


Some conditional probabilities can be looked up in the Bayes net using probability_lookup. The rest can be computed as ratios of marginal probabilities.

probability_conditional(net, hypothesis, givens=None)


Use all of the above types of probability to produce a function that can compute any probability expression in terms of the Bayes net parameters:

def probability(net, hypothesis, givens=None) :

Parameter-counting and independence

Here are two more things we can do with Bayes nets.


First, implement a function that returns the number of parameters in the network. Note that we are no longer assuming boolean variables, so some variables can take on more than two values.

def number_of_parameters(net) :

Hint: The helper function product may be helpful here.



Second, implement a function that checks independence:

is_independent(network, var1, var2, givens=None)

If givens are supplied, return True if var1 and var2 are conditionally independent given the givens. If givens are not supplied, return True if var1 and var2 are marginally independent. Otherwise, return False.


Recall that variables can be independent either because of the topology of the network (structural independence), or because of their conditional probability table entries (numerical independence). It is sufficient to check only numerical independence, because variables that are structurally independent are guaranteed to also be numerically independent. (That is, you can implement by computing and comparing probabilities -- no need to code d-separation.)


Hint: The helper function approx_equal may be useful for comparing probabilities, which are floats.

API

The file bayes_api.py defines the BayesNet class, as well as some helper functions, all described below.

Getting information from a BayesNet

  • net.variables: A list of all variables in the Bayes net.
  • net.get_parents(var): Return the set of variables that are the parents of var.
  • net.get_children(var): Return the set of variables that are the children of var.
  • net.get_domain(var): Return the domain of the variable. For example, if the variable is boolean, the function will return (False, True).
  • net.is_neighbor(var1, var2): Returns True if var1 and var2 are directly connected by an edge in the Bayes net, otherwise returns False. In other words, returns True just if var1 is a parent of var2, or var2 is a parent of var1.
  • net.probability(hypothesis, parents_vals=None, infer_missing=True): Given the value of a variable and all its parents, looks up and returns a probability in the network's conditional probability tables. For example, suppose A, B, C are boolean variables in a particular network, and C is the child of A and B; you can look up P(C = True | A=False, B=False) using net.probability({"C" : True}, {"A": False, "B" : False}). If infer_missing is True, the function will try to infer missing entries in the table using the fact that certain probabilities must sum to one.


To view the structure of a BayesNet, you can print its variables and edges directly using print.

To print a conditional probability table: net.CPT_print(var=None): Pretty-prints the Bayes net's conditional probability table for var. If var is not specified, prints every conditional probability table in the net.

Iterating over a BayesNet

net.topological_sort(): Returns an ordered list of all variables such that each variable comes after all its parents.


net.combinations(variables, initial_bindings=None): Given a list of variables, returns a list of every possible binding of those variables. For example, if you have three boolean variables "A", "B", "C", this function will return a list of eight possible bindings :

  • {"A" : False, "B" : False, "C" : False}
  • {"A" : True, "B" : False, "C" : False}
  • {"A" : False, "B" : True, "C" : False}
  • {"A" : False, "B" : False, "C" : True}
  • {"A" : True, "B" : True, "C" : True}


Each binding in the list will also include the entries in initial_bindings, if specified. For example, passing initial_bindings = {"D" : False, "E" : True} as an argument would include the entries {"D" : False, "E" : True} in every one of the above eight bindings.

Helper functions

approx_equal(a, b, epsilon=0.0000000001): Returns True if two numbers a and b are approximately equal (within some margin epsilon), otherwise False.

Sample usage: approx_equal(0.4999999999999999, 0.5) -> True


product(factors): Computes the product of a list of numbers, similar to the Python built-in function sum


filter_dict(pred, dictionary): Returns a new dictionary containing only the keys matching pred(key).

For example, filter_dict({"A" : 0, "B" : 1, "C" : 2, "D" : 3}, lambda x : x in ["A", "D"]) will return the map {"A" : 0, "D" : 3}

Feedback

Do you want to help us improve this new lab for next year? If so, here are two ways you can help:

  • Email your feedback (and optionally your lab_bayes.py file, so we can use it to improve the tests) to Jessica at jmn@mit.edu with the subject line "lab_bayes feedback" (shortcut).
  • If you would prefer to provide feedback anonymously, you can do so through this form.

If you want to provide additional feedback on previous labs, we're happy to receive that as well!

Personal tools