Note: Some questions seem straightforward or have general text answers that should be clear from R&N, and so haven't been answered. Sorry! ************************************************************ Solutions to Fall 1996 sample final ************************************************************ 1. Standard Bayes' Rule problem: Use variables G (guilty) and L (lie detected) (real), both true/false. We know: P(L=t|G=t) = .80, P(L=f|G=t) = .20 P(L=t|G=f) = .05, P(L=f|G=f) = .95 Also: P(G=t) = .01, P(G=f) = .99 Then: P(L=t|G=f)P(G=f) .05 * .99 P(G=f|L=t) = ---------------- = ---------------- P(L=t) P(L=t) P(L=t) = P(L=t|G=f)P(G=f) + P(L=t|G=t)P(G=t) = .05 * .99 + .80 * .01 = .0495 + .008 = .0575 2, 3. N/A (not responsible for A* algorithm) 4. NAND is a linearly separable function, where the only negative member is the point (1, 1, 1, ... 1). It can thus be represented by a single-layer perceptron, e.g. one in which all inputs have weight -1, and the output has a step activation function with a threshold of -n+1. 5. SAME is the complement of XOR: (0,0) and (1,1) are positive, while (0,1) and (1,0) are negative. It is not linearly separable and can't be represented by a single-layer perceptron. Proof by simple graph. 6. (Inference) 7. Standard, as in Assignment 2. It's often easiest to put formulae into conjunctive normal form (see steps on p. 281): (a) ((p => q) => p) => p === ~[~(~p OR q) OR p] OR p (=>) === ~[(p AND ~q) OR p] OR p (DeMorgan's) === [~(p AND ~q) AND ~p] OR p (DeMorgan's) === [(~p OR q) AND ~p] OR p (DeMorgan's) === (~p OR q OR p) AND (~p OR p) (distribution) === T AND T === valid (b) F => p === T OR p ==== T ==== valid (c) If validity is not directly apparent, you might find it easier to convert to CNF and then check validity: [forall x p1(x) OR forall x q1(x)] => forall x (p1(x) OR q1(x)) eliminate implication === [~forall x p1(x) AND ~forall x q1(x)] OR forall x (p1(x) OR q1(x)) move ~ inwards === [exists x ~p1(x) AND exists x ~q1(x)] OR forall x (p1(x) OR q1(x)) standardize variables apart (rename) === [exists x ~p1(x) AND exists y ~q1(y)] OR forall z (p1(z) OR q1(z)) move quantifiers left === exists x exists y forall z [~p1(x) AND ~q1(y)] OR [p1(z) OR q1(z)] remove quantifiers (X and Y are Skolem constants) === [~p1(X) AND ~q1(Y)] OR [p1(z) OR q1(z)] distribute ANDs over ORs and flatten === [~p1(X) OR p1(z) OR q1(z)] AND [~q1(Y) OR p1(z) OR q1(z)] (This is now in CNF.) Now it's easy to see that formula is valid: Either all things (z) satisfy p1 or there is some entity (X) that doesn't, and the same is true for q1. (d) forall x (p1(x) OR q1(x)) => [forall x p1(x) OR forall x q1(x)] (not valid) (e) [exists x p1(x) AND exists x q1(x)] => exists x (p1(x) AND q1(x)) (not valid) (f) exists x (p1(x) AND q1(x)) => [exists x p1(x) AND exists x q1(x)] === ~[exists x (p1(x) AND q1(x))] OR [exists x p1(x) AND exists x q1(x)] === [forall x ~p1(x) OR ~q1(x)] OR [exists x p1(x) AND exists x q1(x)] === [forall x ~p1(x) OR ~q1(x)] OR [exists y p1(y) AND exists z q1(z)] === forall x exists y exists z [~p1(x) OR ~q1(x)] OR [p1(y) AND q1(z)] === [~p1(x) OR ~q1(x)] OR [p1(Y) AND q1(Z)] === [~p1(x) OR ~q1(x) OR p1(Y)] AND [~p1(x) OR ~q1(x) OR p1(Y)] As in (c), this is clearly valid. (g) [forall x exists y p3(x,y)] => [exists y forall x p3(x,y)] (not valid) (h) [exists y forall x p3(x,y)] => [forall x exists y p3(x,y)] === [~exists y forall x p3(x,y)] OR [forall x exists y p3(x,y)] === forall y ~(forall x p3(x,y)) OR [forall x exists y p3(x,y)] === forall y exists x ~p3(x,y) OR forall x exists y p3(x,y) === forall y exists x ~p3(x,y) OR forall z exists w p3(z,w) === forall y exists x forall z exists w [~p3(x,y) OR p3(z,w)] === [~p3(F(y),y) OR p3(z,F(z)] === valid 8. This is thoroughly explained in 24.4 - using motion, binocular streopsis, texture, shading, and contour are all possible methods for extracting depth information. 9. (a) Indexical: Meet me here tomorrow. ("here" and "tomorrow" refer to contextually determined place and time.) (b) Anaphor: He bought the hot dog and ate it immediately. ("it" refers to "hot dog") (c) Lexical ambiguity: The food was way too hot for her liking. ("hot" might mean spicy hot or temperature hot.) 10. Planning (a) flexibility, specify only required, important links (b) subsequent added actions will be prevented from clobbering some necessary link (by removing precondition) and can be dealt with (by promotion, demotion) 11. feedback control 12. Question missing, but this is standard alph-beta pruning, as in Assignment 6.