(CSSE 413                 

  (Quiz # 2 Answers))

 

 

1.  Explain why it is a good heuristic to choose the variable that is most constrained, but has the value that is least constraining in a CSP search.

 

This is problem 5.3.  Russell says, “The most constrained variable makes sense because it chooses a variable that is (all other things being equal) likely to cause a failure, and it is more efficient to fail as early as possible (thereby pruning large parts of the search space).  The least constraining value heuristic makes sense because it allows the most chances for future assignments to avoid conflict.”

 

Part credit was awarded for getting the first part right, or lumping both without saying what each part contributed.  If you talked about optimizing search results, I took off.  In most CSP problems, the normal goal is to find any solution at all, and depth-first is generally used.

 

 

2. Russell & Norvig assert that “for every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN will never be lower than the utility obtained against an optimal MIN.”  Why is that?

 

This is the first part of problem 6.2.  Russell says, “Consider a MIN node whose children are terminal notes.  If MIN plays suboptimally, then the value of the node is greater than or equal to the value it would have if MIN played optimally.  Hence, the value of the MAX node that is the MIN node’s parent can only be increased.  This argument can be extended by a simple induction all the way to the root.”

 

I took off if you got into pruning, which probably meant you were discussing alpha-beta.  And I took off a lot if you simply talked about how optimizing was always better than suboptimizing, without relating the specific issues at hand here about this process.

 

 

3.  Modus Ponens is one process which can be applied to generate new sentences that a KB entails:

 

 a Þ b,   a

---------------     ,

        b


How do we know that this procedure is sound?

Modus Ponens is introduced on p. 211. The procedure is sound (p. 208) if the top two clauses taken together “entail” the bottom clause.  And this will hold if, anded together as a KB, they imply the bottom clause (p. 210).  Using truth tables, we have:

 

a         b          a Þ b      (a Þ b) Ù a     [(a Þ b) Ù a] Þ b

true      true      true                  true                  true

true      false    false                false                true

false    true      true                  false                true

false    false    true                  false                true

 

You might say, well, what if the real KB we are dealing with has lots of other sentences in it, besides   a Þ b  and  a ?  These will also be “anded” with those two clauses, and so can only reduce further the instances of where the KB gives a “true” in the truth table.  So all of those clauses together will also imply b !

 

Lots of people also answered this by pointing out the logic is always sound, and clearly one could substitute an implication where the “entails” is done in the process (the line separating the givens from the result).


Is it complete?  Why or why not (informal arguments touching on the issues are acceptable, but sound as convincing as you can!)?

This one was hard enough I ended up counting it as 10 points of extra credit (E.C.), and so you received 20 points if you got the first part of question 3, above, correct.

 

Completeness is introduced on p. 209, and doubt is cast on whether Modus Ponens, among other procedures, is complete, on p. 213.  Completeness says we can derive any sentence that is entailed by a KB, using this procedure.  Arguing informally, this is a rather tall order.  We’d likely have to show that Modus Ponens is equivalent to something like the full resolution rule, and the latter is only complete in the limited sense described on p. 214.  It’s mathematically possible that applications of Modus Ponens by itself could derive any sentence, but it’s unlikely.  How would we convert any other rule in a KB to a simple implication, in order to show that we could derive anything from Modus Ponens which came from those rules?  Consider the KB that has only A Ù B in it.  We would know from the And-Elimination rule (also p. 211) that A is therefore entailed.  But how could we have derived that from Modus Ponens alone?

 

If you answered “No” and had a start on this kind of argument, you got the extra credit.

 

4.  Convert the following English sentences into FOL:

 

The answers shown are examples – a range of answers were considered acceptable.  I counted them as 7 points each, so you really could have scored 21 on this problem:

 

a.  Some students took Japanese 4 in spring 2003.

 

$ x Student(x) ^ Takes(x, Japanese4, Spring2003).

 

(This one was similar to 8.6 a) Almost anything that looked close to me got full credit.

 

b.  Anytime you see glitter, your best action is to grab for something then.

 

" t Glitter(t) Þ BestAction(Grab, t).

 

(This one appears on p. 258.)  I took off if you didn’t mention something about the time, which is characterized in the English here, or some similar situational identifier like what square you are in.

 

c.  There is an agent who sells policies only to people who are not insured.

 

$ x  Agent(x) Ù " y, z  Policy(y) Ù Sells(x, y, z) Þ (Person(z)  Ù  Ø Insured(z)).

 

(This one is problem 8.6 g.)  The most common mistake on this one was reversing the positions of the Sells and the Ø Insured  parts of this logic.  It is the selling which implies the people aren’t insured.  Also, some answers reversed the order of the quantifiers.   Putting the $ inside the " is not the same thing!

 

5.  Russell & Norvig define sets recursively as follows:

 

" s   Set(s)  Û  (s = { })  Ú  ($ x, s2, Set(s2) Ù s = {x | s2}).

 

Describe an axiom you could add to the above, so that things like {x  y  x} would be disallowed from being a set (assume you have also defined what set membership means):

 

The goal of this problem was to see if you understood what Russell & Norvig said about sets in Ch. 8, something we noted as being important to know.

 

Russell & Norvig prevent multiples of the same element in a set (“things like {x  y  x} ”) by their axiom # 3 on p. 257, which amends the above rule as follows:

 

" x, s  x Î s Û s = {x | s},

 

That is, adjoining an element already in the set has no effect.  The “hint” allows you to assume you have a definition of what x Î s means, so this makes sense!

 

Many people also solved this just by adding x Ï s2 to the definition given in the problem.

 

You had trouble if you tried to say something like, if x Î s2 and y Î s2 then x ¹ y.  What prevents the same x  from being selected each time in {x  y} ?  This really needed to be fixed up with something like y Î s2 – {x} to work.

 

A few people interpreted the question literally as looking to exclude a pattern exactly like the {x  y  x}  shown.  If you did this, I graded your answer primarily on how well it answered that interpretation.