Home / Software Lab 9 (All Your Bayes Are Belong to Us)

Software Lab 09: All Your Bayes Are Belong To Us

The questions below are due on Tuesday April 09, 2019; 08:25:00 PM.
 
You are not logged in.

If you are a current student, please Log In for full access to this page.
music for this lab

Files

This lab description is available as a PDF file here. The code distribution may be downloaded (in zip format) here, or by running athrun 6.01 getFiles from an Athena machine or a 6.01 lab laptop.

Goals: Over the next few weeks in 6.01, we will work toward making a robot that will be able to park itself in a small parking space in the world. As a part of this process, we will program the robot to determine its location based on sonar readings it makes as it moves throughout the world.

In this lab, we will take our first steps toward this behavior by experimenting with Bayes' Rule and the Law of Total Probability in a simplified version of this problem, both by hand and in software.

1) Getting Started

**You should do this lab with a partner of your choosing.** You will need a laptop that reliably runs lib601.

Get today's files by running

$ athrun 6.01 getFiles

2) Hallway World

For today's lab, we will work in the context of an abstract simulation of a color-sensing robot moving up and down a finite one-dimensional hallway. The robot can move forward and backward, but it never rotates. Thus the x coordinate of its location can change, but the y coordinate does not change. We discretize the robot's x position, and represent it as an integer value between 0 and a constant num_states - 1, inclusive. This integer will be the state of our system. The idea is that, although we cannot observe the robot's state directly, we can make observations that are related to the robot's state and use those (along with our initial belief and information about the robot's motion) to estimate the state. Specifically, we will assume that the walls of the hallway in each state have a particular color, and that we have a robot with a sensor that it can use to sense the color of the room it's in.

Assume that:

  • The robot starts out knowing how many rooms there are, and the color of the rooms, but not knowing what state it is in.
  • The robot will observe a color. The robot knows, for each state, what an ideal color sensor would read (i.e., it knows the layout of the world and the colors of the rooms).
  • The robot will never move backward, and if it tries to move past the end of the hallway, it will stay in the forward-most location.

The ultimate goal is for the robot to use its observations, as well as what it knows about the structure of the hallway, to determine its location.

3) Software Framework

Throughout this unit, we will use a specific software framework for representing and manipulating probability distributions. You will implement this representation in design lab this week, but first, let's get some practice with using it.

The main class in this representation is called DDist (short for "discrete distribution"). It represents a discrete probability distribution. When initialized, it takes as its sole argument a dictionary mapping elements to their associated probabilities. For example, the following would represent a distribution over possibilities from flipping a fair coin:

coin_dist = DDist({'heads': 0.5, 'tails': 0.5})

We will represent joint distributions \Pr(A,~B) as DDist instances over tuples (a, b), where a and b represent the values of the two random variables.

We will represent conditional distributions \Pr(A~|~B) as functions that take a value of a random variable B and return a distribution over values of a random variable A.

Among other things, the framework provides functions bayes_rule and total_probability, which implement Bayes' Rule and the Law of Total Probability, respectively.

Throughout this lab, you may find the documentation for the dist module of lib601 helpful. Some examples are also given on the last page of the physical handout.

4) Hallways

Remember that our goal is to have the robot figure out its location in a 1-dimensional world based on a sequence of observations.

In this first example, we will put the robot in a world with 4 states. The ideal color readings in states 0 through 3 are 'yellow', 'red', 'blue', and 'green', respectively, for this world. In code, this world is simply represented as:

ideal = ['yellow', 'red', 'blue', 'green']

Below, the robot is pictured in this world, in state 3:

4.1) Belief

We will characterize the robot's uncertainty about its location with a belief, which is a probability distribution over states the robot could be in.

Let's imagine the case where the robot exists in the world above, but it has no idea which state it is in. In this case, this initial belief is represented by the following distribution:

`Pr(S = 0)`
`Pr(S = 1)`
`Pr(S = 2)`
`Pr(S = 3)`
0.25 0.25 0.25 0.25

Create an instance of DDist representing this initial belief, and enter your answer in the box below:

Assuming that the robot's belief was stored as a variable called belief, enter an expression using the methods from DDist to find the probability that the robot is in state 2.

4.2) Observations

We can represent the relationship between states and observations with an _observation model_, which is a conditional distribution over observations, given a state.

For now, we will also assume that the robot is guaranteed to observe the ideal value for the location it is in (we are assuming that the robot's sensor is perfect). We can model this assumption with the following observation model, where O represents the observation the robot makes, and S represents the state the robot is in:

\Pr(O=o~|~S=s) = \begin{cases} 1, & \text{if}~o = \mathtt{ideal[}s\mathtt{]} \\ 0, & \text{otherwise} \end{cases}

Note that we could also represent this conditional distribution in code, using the DDist framework:


def perfect_obs_model(s):
    return DDist({ideal[s]: 1.0})

For the following questions, enter your answers as instances of `DDist`:
`DDist({0:` $\Pr(S=0)$ `, 1:` $\Pr(S=1)$ `, 2:` $\Pr(S=2)$ `, 3:` $\Pr(S=3)$ `})`

Solve by hand: Starting from the uniform belief shown above, if the robot makes an observation of 'yellow', what is the new distribution over locations the robot could be in?

Using the framework in the dist module, and assuming that the starting belief is stored in a variable called belief and that perfect_obs_model is defined for you, enter a Python expression that would have computed the distribution above (when the robot makes an observation of 'yellow'):

Solve by hand: Now imagine a different world with ideal = ['yellow', 'red', 'blue', 'yellow']. In this world, starting from a uniform belief, if the robot observes 'yellow', what is the new belief?

Solve by hand: How would your answer to the previous question change if the robot's initial belief was:

`Pr(S = 0)`
`Pr(S = 1)`
`Pr(S = 2)`
`Pr(S = 3)`
0.3 0.25 0.25 0.2

5) Observation Models

NOTE that the `lib601.dist` module contains many useful functions for building distributions (`triangle_dist`, `uniform_dist`, `delta_dist`, and `mixture`, among others), which may be helpful for implementing the models in the following section. In all of the code boxes below, the `lib601.dist` module is imported with the following code:

from lib601.dist import *

An observation model is a conditional probability distribution, \Pr (O_t ~|~S_t)

  • Given a state, it tells us how likely a given observation would be if the robot were in that state.

Consider two observation models, which we will refer to as observation model A and observation model B:

  • Observation model A characterizes a sensor that returns the ideal value with probability 0.7, and returns 'grey' with probability 0.3.
  • Observation model B characterizes a sensor that returns the ideal value with probability 0.7, and, with probability 0.3, returns a random color from the following list (distributed uniformly):
    ['yellow', 'white', 'green', 'blue', 'red', 'grey', 'orange', 'pink', 'periwinkle', 'chartreuse']
    You may assume this list is stored in a variable called POSSIBLE_COLORS, as in swLab09.py.

Implement obs_model_A and obs_model_B in swLab09.py.

Paste your definitions of obs_model_A and obs_model_B in the box below:

Answer the following questions about `obs_model_A` and `obs_model_B` in an environment with `ideal = ['red', 'blue', 'blue', 'red']`. Note that you can use the code `dist` framework to test your hypotheses, but you should try to solve these questions first without using the code.

We will say that two models behave equivalently if, for all possible observations, the two models result in the same belief.

Observation Model A

With ideal = ['red', 'blue', 'blue', 'red']:

Under observation model A, what is \Pr (O=\mathtt{'red'}~|~S=0)?

Under observation model A, what is \Pr (O=\mathtt{'red'}~|~S=1)?

Solve by hand: In the world with ideal=['red','blue','blue','red'], if the robot starts with an initial belief of:
belief = DDist({0:0.1, 1:0.3, 2:0.2, 3:0.4})

what is its updated belief after observing a 'blue', using obs_model_A? Enter your answer below, as an instance of DDist:

Solve by hand: In the world with ideal=['red','blue','blue','red'], if the robot starts with an initial belief of:
belief = DDist({0:0.1, 1:0.3, 2:0.2, 3:0.4})

what is its updated belief after observing a 'grey', using obs_model_A? Enter your answer below, as an instance of DDist:

Check Yourself 1:

Are these results at all surprising? Use the `DDist` framework on your own machine to verify the answers from above.

Under observation model A in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0, 0.5, 0.5, 0, 0], what happens when the sensor reads 'grey'?

Under observation model A in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0, 0.5, 0.5, 0, 0], what happens when the sensor reads 'periwinkle'?

Under observation model A in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0.2, 0.2, 0.2, 0.2, 0.2], what happens when the sensor reads 'red'?

True or False: All colors in POSSIBLE_COLORS can be observed from every location under observation model A.

True or False: A system with a sensor and observation model described by model A behaves exactly the same as a system with a perfect sensor and perfect observation model.

Observation Model B

With ideal = ['red', 'blue', 'blue', 'red']:

Under observation model B, what is \Pr (O=\mathtt{'red'}~|~S=0)?

Under observation model B, what is \Pr (O=\mathtt{'red'}~|~S=1)?

Using the DDist framework on your own machine, answer the following: In the world with ideal=['red','blue','blue','red'], if the robot starts with an initial belief of:
belief = DDist({0:0.1, 1:0.3, 2:0.2, 3:0.4})

what is its updated belief after observing a 'blue', using obs_model_B?

Paste in the resulting DDist below:

Using the DDist framework on your own machine, answer the following: In the world with ideal=['red','blue','blue','red'], if the robot starts with an initial belief of:
belief = DDist({0:0.1, 1:0.3, 2:0.2, 3:0.4})

what is its updated belief after observing a 'green', using obs_model_B?

Paste in the resulting DDist below:

Under observation model B in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0.2, 0.2, 0.2, 0.2, 0.2], what happens when the sensor reads 'red'?

Under observation model B in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0.2, 0.2, 0.2, 0.2, 0.2], what happens when the sensor reads 'green'?

Under observation model B in a world with ideal = ['red','blue','blue','red','red'], and assuming the current belief state is [0.2, 0.2, 0.2, 0.2, 0.2], what happens when the sensor reads 'blue'?

True or False: All colors in POSSIBLE_COLORS can be observed from every location under observation model B.

True or False: A system with a sensor and estimator described by model B behaves exactly the same as a system with a perfect sensor and perfect observation model.

Check Yourself 2:

Do the answers from above make sense? If not, talk with a staff member.

6) Appendix: Notes on Distributions

6.1) Distribution

  • Function from elements $a$ of domain $A$ into probabilities
  • Math: whole distribution : $\Pr(A)$
  • Math: probability of element : $\Pr(A = a)$
  • Python: whole distribution : `pr_A = DDist({'a1' : 0.1, 'a2' : 0.9})`
  • Python: probability of element : `pr_A.prob('a2')`

6.2) Conditional Distribution

  • Function from elements $b$ of domain $B$ into distributions over $A$
  • Math: whole conditional distribution : $\Pr(A \mid B)$
  • Math: distribution conditioned on $B = b$ : $\Pr(A \mid B = b)$
  • Math: probability of element conditioned on $B = b$ : $\Pr(A = a\mid B = b)$
  • Python: whole conditional distribution
        def pr_A_given_B(b):
            if b == 'foo':
                return DDist({'a1' : 0.2, 'a2' : 0.8})
            elif b == 'bar':
                return DDist({'a3' : 0.4, 'a2' : 0.6})
            else:
                print('Error:', b, 'not in domain of pr_A_given_B')
    
  • Python: distribution conditioned on `b`: `pr_A_given_B(b)`
  • Python: probability of element conditioned on `b`: `pr_A_given_B(b).prob(a)`

6.3) Joint Distribution

  • Probability distribution over pairs of elements (which may themselves have more complex structure.)
  • Math: $\Pr(A, B)$
  • Math: $\Pr(A = a, B = b) = \Pr(B = b \mid A = a) \Pr(A = a)$
  • Python: whole distribution :
    pr_A_B = DDist({('a1', 'b2') : 0.1, ('a2', 'b1') : 0.5, ('a2', 'b3') : 0.4})
  • Python: whole distribution: `make_joint_distribution(pr_A, pr_A_given_B)`
  • Python: probability of element: `pr_A_B.prob(('a1', 'b2'))`

6.4) Projection

  • Given a probability distribution over elements in one space,
  • find a related distribution over functions of those elements.
  • Math: Old random var $A$; New random var $B = f(A)$
  • Math: Element of distribution $\Pr(B = b) = \sum_{{a : f(a) = b}} \Pr(A = a)$
  • Python: `pr_A.project(f)`

6.5) Marginalization

  • Given a probability distribution over elements in a joint distribution, project into a distribution on one of the dimensions.
  • Math: Go from $\Pr(A, B)$ to $\Pr(A) = \sum_b \Pr(A, B)$
  • Python: `pr_A = pr_A_B.project(m)` (determining `m` is a tutor problem.)

6.6) Conditioning

  • Given a joint probability distribution, condition on one random variable having a particular value
  • Math: Go from joint $\Pr(A, B)$ and evidence $b$ to whole distribution $\Pr(A \mid B = b)$; this is a new distribution on $(A, B)$
  • Math: Individual elements of the distribution $$\Pr((A = a \mid B = b) = \frac{\Pr(A = a, B = b)}{\Pr(B = b)}$$
  • Python: whole distribution
    pr_A_B_given_B = pr_A_B.condition(lambda ab : ab[1] == b)

6.7) Total Probability

  • Given a conditional distribution and a marginal, compute the other marginal
  • Math: Go from $\Pr(B \mid A)$ and $\Pr(A)$ to $\Pr(B)$
  • Math: Individual elements $$\Pr(B = b) = \sum_a \Pr(A = a, B = b) = \sum_a \Pr(B = b \mid A =a) \Pr(A = a)$$
  • Python: whole distribution : `pr_B = total_probability(pr_A, pr_B_given_A)`

6.8) Bayes' Rule

  • Use conditional probability to switch the conditioning relationship
  • Math: Go from $\Pr(H)$ and $\Pr(E \mid H)$ to $\Pr(H \mid E = e)$
  • Math: You should be able to do the derivation using definition of conditional probability
  • Python: `pr_H_given_E = bayes_rule(pr_H, pr_E_given_H, e)`