Sample Questions For Term Test 2 Covers Backtracking Search and Uncertainty
November 26, 2020
1. A latin square of size m is an m×m matrix containing the numbers 1–m such that no number occurs more than once in any row or column. For example
1234 4123 3412 2341
is a latin square of size 4. Specify this the problem of finding a latin square of size m as a CSP. That is, give the variables, the variable domains, and the constraints for a CSP representing this problem.
2. Consider the N -Queens problem. That is, the problem of placing N Queens on an N × N chess-board so that no two Queens can attack each other.
Find the first solution to the 5-Queens problem by using the Forward Checking algorithm using Minimum Remaining Values heuristic (always instantiate next the variable with smallest remaining number of elements in its current domain). Also breaking ties in favour of the lowest numbered variable.
(Note, use the same CSP formulation as that used in class. That is, we have 5 variables, Q1, . . . , Q5 each with domain [1, 2, 3, 4, 5]. Each variable Qi represents the queen in the i-th row, and the assignment Qi = j means that the queen in the i-th row has been placed in the j-th column.
Draw the search tree explored by this algorithm. At each node indicate
(a) The variable being instantiated, and the value it is being assigned.
(b) A list of the variables that have had at least one of their values pruned by the new assignment, and for such variable a list of its remaining legal values. Note, you must follow the forward checking algorithm precisely: only prune values that would be pruned by the algorithm.
(c) Mark any node where a deadend occurs because of a domain wipe out (use the symbol DWO).
1
3. Repeat the same problem of 5-Queens but this time use GAC. This time show the initial domains after GAC Enforce is run at the root, then show the search tree as before, specifying the variable branched on and the value assigned, list of variables pruned by GAC Enforce by that decision, and the list of remaining values for the pruned variables.
4. Say we have 4 variables X , Y , Z , and W , with the following domains of values:
(a) Dom[X]={1,2,3,4} (b) Dom[Y]={1,2,3,4} (c) Dom[Z]={1,2,3,4}
(d) Dom[W] = {1,2,3,4,5} And 3 constraints:
(a) C1(X, Y, Z) which is satisfied only when X = Y + Z (b) C2(X, W ) which is satisfied only when W > X
(c) C3(X,Y,Z,W)whichissatisfiedonlywhenW =X+Z+Y
Enforce GAC on these constraints, and give the resultant GAC consistent variable domains.
5. Two astronomers in different parts of the world make measurements M1 and M2 of the number of stars N in some small region of the sky, using their telescopes. Normally, there is a small probability e or error of up to one star in each direction. Each telescope can also be badly out of focus with probability f. Let F1 and F2 be boolean variables with Fi = true being that the i-th telesope is out of focus. If the telescope is out of focus then the scientist will always undercount by 3 or more stars (or, if N is 3 or less, fail to detect any stars at all). Consider the three networks:
F1
F2 F1 N F2 M1
M2
M1 M2
N
M1 M2
N F1F2
(i)
(ii)
(iii)
(a) Which of these Bayesian Networks can correctly representation the preceeding informa- tion? (Note that additional edges in a network do not make the network incorrect, they only make the network redundant). Note this question was done in tutorial
(b) Which is the best network? Explain. Note this question was done in tutorial
(c) Write out the CPT for Pr(M1|N,F1) for the case where M1 ∈ {0,1,2,3,4} and N ∈
{1,2,3}. Express the entries in terms of e and f. 2
(d) Use your CPT for Pr(M1|N,F1) to compute the CPT for Pr(M1|N) (again expressed in terms of e and f). Hint, use summing out rule for conditional probabilities and knowledge of independencies in this domain.
(e) Suppose M1 = 1 and M2 = 3. What are the possible numbers of stars.
6. Consider the Bayes Network given below.
X1
X4
X6
X2
X3
X5
X7
(a) What is the product decomposition specified by this network?
(b) Say that variable X7 has 3 possible values, X6 has 2 possible values, and X4 has 4 possible values. How many values will be contained in the conditional probability table for X6.
(c) Are X1 and X5 conditionally independent given X2, given X7, given X6, given X4?
(d) What are the relevant variables given the query X3 and the evidence items X6, given
evidence X5, given evidence X4?
7. Consider the Bayes Net given below.
(a) Which of the following statements are asserted by this Bayes net. i. P(A,D) = P(A)P(D)
ii. P(E|C,D) = P(E|C,D,B) iii. P(E|D,B)=P(E|D)
iv. P(C|A,B) = P(C|A,B,D)
(b) Say we want to use variable elimination to compute the probability of P(E) given no evidence, what would be the elimination width of the following orderings. (The variables are to be eliminated in the order listed).
i. A,B,C,D,E. ii. C,A,B,D,E.
AB
D C
E
3
iii. B,D,C,A,E.
iv. E,B,A,D,C.
(c) List the pairs of variables that are conditionally independent in this network given.
i. No evidence ii. Given C
iii. Given D.
8. Consider the Bayes net given below.
EB
S
WG
In this network all variables are binary with values true and false. E represents the occurrence of an Earthquake, B a burglary, S an alarm sound, W your neighbour Mr. Watson phones you to inform you that he heard an alarm at your house, and G your neighbour Mrs. Gibbons phones you to inform you that she heard an alarm at your house. We use upper case to indicate a variable and lower case to indicate the values of a variable. When you are asked to give a probability involving some variables, you must the value of this probability for all values of the variables. Hint, many of the questions can be answered directly without any numeric calculations.
Let the conditional probability tables for the network be:
E
e
-e
9/10
B
b
-b
S
e∧b
s
-s
1/10
W
w
-w
1/10
1/10
9/10
9/10
s
8/10
2/10
e ∧ -b
2/10
8/10
-s
2/10
8/10
-e ∧ b
8/10
2/10
-e ∧ -b
0
1
G
g
-g
s
1/2
1/2
-s
0
1
(a) Given that Mrs. Gibbons phones you (g) what is the probability that the alarm went off (s)?
(b) Say that there was a burglary (b) and but no earthquake (-e), what is the expression specifying the posterior probability of Dr. Watson phoning you (w) given the evidence. (You do not need to calculate a numeric answer, just give the probability expression).
(c) What is P(G|S)? (i.e., the four probability values P(g|s), P(−g|s), P(g|−s), P(−g|−s).
4
(d) What is P(G|S ∧ W )? (i.e., the 8 probability values P(g|s ∧ w), P(g|s ∧ −w), . . . , P(−g| − s ∧ −w)).
(e) What do these values tell us about the relationship between G, W and S?
(f) What is P(G|W )? (i.e., the four probability values P(g|w), P(−g|w), P(g| − w), and
P(−g| − w)).
(g) What do these values tell us about the relationship between G and W, and why does
this relationship differ when we know S?
5