Artificial Intelligence 1 \hspace{6em} Problem Set 1 : Solutions Problem 1: Proof by contradiction. Suppose that P(H | E) > P(H) and P(H | not E) > P(H). By definition, P(H | E) = P(H and E) / P(E), so we have P(H and E) > P(E) P(H). By the same token P(H and not E) > P(not E) P(H). But then P(H) = P(H and E) + P(H and not E) > P(H) P(E) + P(H) P(not E) = P(H) (P(E) + P(not E)) = P(H), which is a contradiction. Problem 2: A. i, iv, and vi are correct. B. Abbreviate on-time as "o", late as "l", 8:00 as "0", 8:30 as "3", light as "l, heavy as "h", sitting as "s", standing as "d". i. P(M=o) = P(M=o | T=0) P(T=0) + P(M=o | T=3) P(T=3). Now P(T=0) = P(T=0, W=o, F=l) + P(T=0, W=l, F=l) + P(T=0, W=o, F=h) + P(T=0, W=l, F=h) = P(T=0 | W=o, F=l) P(W=o, F=l) + P(T=0 | W=l, F=l) P(W=l, F=l) + P(T=0 | W=o, F=h) P(W=o, F=h) + P(T=0 | W=l, F=h) P(W=l, F=h) = (since W and F are independent) P(T=0 | W=o, F=l) P(W=o) P(F=l) + P(T=0 | W=l, F=l) P(W=l) P(F=l) + P(T=0 | W=o, F=h) P(W=o) P(F=h) + P(T=0 | W=l, F=h) P(W=l) P(F=h) = 0.9*0.8*0.4 + 0.4*0.2*0.4 + 0.7*0.8*0.6 + 0.2*0.2*0.6 = 0.68. P(T=3) = 1 - P(T=0) = 0.32. So P(M=o) = P(M=o | T=0) P(T=0) + P(M=o | T=3) P(T=3) = 0.68*0.9 + 0.3*0.32 = 0.708. ii. P(M=o | W=o) = P(M=o, T=0, F=l | W=o) + P(M=o, T=0, F=h | W=o) + P(M=o, T=3, F=l | W=o) + P(M=o, T=3, F=h | W=o) = (by the conditional independence of M from F and W given T) P(M=o | T=0) P(T=0, F=1 | W=o) + P(M=o | T=0) P(T=0, F=h | W=o) + P(M=o | T=3) P(T=3, F=1 | W=o) + P(M=o | T=3) P(T=3, F=h | W=o) = (by the independence of F and W) P(M=o | T=0) P(T=0 | F=l, W=o) P(F=l) + P(M=o | T=0) P(T=0 | F=h, W=o) P(F=h) + P(M=o | T=3) P(T=3 | F=l, W=o) P(F=l) + P(M=o | T=3) P(T=3 | F=h, W=o) P(F=h) = 0.9*0.9*0.4 + 0.9*0.7*0.6 + 0.3*0.1*0.4 + 0.3*0.3*0.6 = .768 iii. P(M=o | W=l) = (by the same argument as above) P(M=o | T=0) P(T=0 | F=l, W=l) P(F=l) + P(M=o | T=0) P(T=0 | F=h, W=l) P(F=h) + P(M=o | T=3) P(T=3 | F=l, W=l) P(F=l) + P(M=o | T=3) P(T=3 | F=h, W=l) P(F=h) = 0.9*0.4*0.4 + 0.9*0.2*0.6 + 0.3*0.6*0.4 + 0.3*0.8*0.6 = .468 iv. P(W=o | M=o) = (by Bayes' Law) P(M=o | W=o) P(W=o) / P(M=o) = 0.768*0.8/0.708 = (approximately) .868 v. P(S=s | M=o) = P(S=s, T=0 | M=o) + P(S=s, T=3 | M=o) = P(S=s | T=0, M=o) P(T=0 | M=o) + P(S=s | T=3, M=o) P(T=3 | M=o) = (by independence of S and M given T) P(S=s | T=0) P(T=0 | M=o) + P(S=s | T=3) P(T=3 | M=o). Now, by Bayes' law, P(T=0 | M=o) = P(M=o | T=0) P(T=0)/P(M=o) and P(T=3 | M=o) = P(M=o | T=3) P(T=3)/P(M=o) and Hence P(S=s | M=o) = P(S=s | T=0) P(M=o | T=0) P(T=0) / P(M=o) + P(S=s | T=3) P(M=o | T=3) P(T=3) / P(M=o) = (0.8*0.9*0.68 + 0.5*0.3*0.32)/0.708 = (approximately) 0.759