Written Problems 6

1. This problem asks you to do Filtering, Prediction, and MLE using the algorithms we looked at in class.
   
   You are up in your friend's apartment building, watching vehicles on the street below.  They are far enough away that all you can see is their color.  You want to catch a taxi home, so you are trying to reason about the probability that a given vehicle in the distance is a taxi, given it's color.
   
   You know that 75% of all taxis are yellow, and that only 10% of all cars are yellow.  You also know that taxis are not likely to bunch up: The vehicle following a taxi is only another taxi 25% of the time.  However, normal cars are followed by taxis 50% of the time (assume there are only cars and taxis on the road).
   
   We formulated the above problem as an HMM in class.  Now your tasks are the following:
   1. Give the transition model and the evidence model as conditional probability tables.
   2.  You just saw a red vehicle, and now you see a yellow vehicle. What is the probability that the vehicle you see is a taxi? (Assume taxis and cars are equally likely when you start looking.)
   3. What is the probability that the next vehicle will be a taxi?
   4. Taking your two observations together, what is the most likely sequence of vehicles that you have seen.  Be sure to show your work.
   5. Now you see another yellow vehicle, and when you apply the smoothing algorithm to estimate the probability that the second vehicle you saw was a taxi, you find that this probability has dropped!  Explain qualitatively why this lower estimate makes sense, given your evidence and transition models (I am looking for an English description here).
2. (from http://www-nlp.stanford.edu/~grenager/cs121//handouts/hw3.pdf)
   An appealing use of HMMs is for localization: in other words, given a map, and a set of observations of your environment, figure out where you are. Suppose we are walking around the Claremont Colleges campus, which is roughly a 1x1 mile square (5280 feet by 5280 feet) (OK, not quite, but close enough...). We’ve been given a map, and we’d like to figure out where we are every ten seconds, down to a resolution of 1 foot.
   
   (a) Let’s formalize this as an HMM. What does each of the hidden states Xt represent? What is the domain of each state variable? How big is this domain?
   
   (b) Suppose that we’re walking with a blindfold on, at roughly 2 miles per hour, trying to go straight. You can ignore obstacles (such as buildings) for now. What’s a reasonable transition model, P(Xt|Xt−1)?
   
   (c) Assume that we get dropped off somewhere on the campus blindfolded but we don’t know
   where. What’s a good starting distribution P(X1)?
   
   (d) Suppose that every ten seconds we can stop and take our blindfold off, and look for Smith
   Tower (on Pomona's campus). If we can see it, we measure approximately how far
   away it is by measuring its apparent height. We then report the approximate distance in 100
   foot increments. What should each evidence variable Et represent? What is the domain of each
   evidence variable? How big is this domain?
   
   (e) Formalize the emission model P(Et|Xt).
   
   (f) Suppose we walk “straight” for 1 minute (60 seconds). How many computations will the forward algorithm take to compute a distribution over our possible locations at the last time step?
   (Hint: this is the “filtering” task from lecture.) Given a computer that can process 1 billion
   computations per second, how long will this computation take?