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.

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

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

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

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:

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

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:

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})

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

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:
def obs_model_A(state): pass # your code here def obs_model_B(state): pass # your code here

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:

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'?
-- The belief becomes uniform. It is as if no observation was made. A Python divide-by-zero error is generated. The belief becomes somewhat more uniform. The belief becomes peaked on a particular location.

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'?
-- The belief becomes uniform. It is as if no observation was made. A Python divide-by-zero error is generated. The belief becomes somewhat more uniform. The belief becomes peaked on a particular location.

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'?
-- It is as if there was no observation made. A Python divide-by-zero error is generated. The belief becomes ` [1/3., 0, 0, 1/3., 1/3.]`. The belief becomes something between ` [1/3., 0, 0, 1/3., 1/3.] ` and uniform. The belief becomes peaked on a particular location.

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

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.
-- True False

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'?
-- It is as if there was no observation made. A Python divide-by-zero error is generated. The belief becomes ` [1/3., 0, 0, 1/3., 1/3.]`. The belief becomes something between ` [1/3., 0, 0, 1/3., 1/3.] ` and uniform. The belief becomes peaked on a particular location.

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'?
-- It is as if there was no observation made. A Python divide-by-zero error is generated. The belief becomes ` [1/3., 0, 0, 1/3., 1/3.]`. The belief becomes something between ` [1/3., 0, 0, 1/3., 1/3.] ` and uniform. The belief becomes peaked on a particular location.

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'? -- It is as if there was no observation made. A Python divide-by-zero error is generated. The likelihood of states 1 and 2 increases. The likelihood of states 1 and 2 decreases.

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

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.
-- True False

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)`