## Introduction to Artificial Intelligence: Problem Set 5

Assigned: Feb. 26

Due: Mar 5

### Problem 1:

Consider the following problem: I get to work, but I can't find the keys
to my office in my pockets. Call this event K. There are three possible
explanations:
- The keys are actually in my pants pocket, where they're supposed to be,
but buried under other junk. (Event P)
- The keys are actually in my coat pocket,
but buried under other junk. (Event C)
- I left the keys at home. (Event H)

We estimate the relevant probabilities as follows:
Prob(P) = 0.8
Prob(C) = 0.19
Prob(H) = 0.01
Prob(K | P) = 0.1
Prob(K | C) = 0.2
Prob(K | H) = 1.0.

A. Evaluate Prob(P | K), Prob(C | K), and Prob(H | K).
B. I check my pockets again, and again don't find the keys. Suppose that
the two checks of my pockets are independent and identical. That is,
let M be the event that I will miss my keys twice in checking the pocket
twice. We suppose that

Prob(M | P) = (Prob(K | P))^{2} = 0.01
Prob(M | C) = (Prob(K | C))^{2} = 0.04
Prob(M | H) = (Prob(M | H))^{2} = 1.0.

Evaluate Prob(P | M), Prob(C | M), and Prob(H | M).
C. Estimate how many times I have to check my pockets before I am 90% sure
that I have left my keys at home.

### Problem 2

The overall syntax of a sentence often constrains the part-of-speech of
the particular words in ways that are not captured by the k-gram model
of tagging parts of speech. For instance, the sentence "I can fish and
tomatoes" can only be given a synactic parse if "can" is labelled
a verb and "fish" is labelled a noun. However, the trigram model will
probably decide that the most likely parse is that "can" is a modal and "fish"
is a verb.
A. Give an example to show that

P(Tag[5]=noun | Tag[3]=verb, Tag[4]=conjunction)

is not zero. (All I'm asking for is one sentence with those
three elements in a row.)

B. Propose a method that will allow you to combine probablistic information
from the trigram model with syntactic constraints. Explain how this would
fix this problem.