University of Calgary
Rob Kremer
Q & A

CPSC 433: Artifical Intelligence
Fall 2013
Department of Computer Science
Computer
Science

  1. "Theory"
    1. Erw expressions: Syntax and semantics
    2. Or tree Search: Erw expression 3
    3. Or tree Search: Erw expressions 4
  2. Assignment
    1. Ambiguous soft constraints

"Theory"

Erw expressions: Syntax and semantics

There's still the proper notation that confuses me; I really need to be familiar with it to understand the notes (OrTreeSearchModel p.5).  In the first Erw operation (Or-tree notes),  there are two tuples: Erw((pr, ?), (pr, yes)). Why is the first tuple there? I see the same thing with the second operation.

A relation is like a function where the first element of the tuple is the input and the second element is the result.  Only in a relation, the result may be ambiguous, in that there may be more than one possible result for any particular input. 

So, when we see Erw((pr, ?), (pr, yes)), that means if we see an argument (ie: input) that looks like (pr, ?), then we could have an output (pr, yes). (I said could because we have to pay attention to the qualifier, "if G(pr)==yes", to check that possibility.)

The expressions (pr, ?), (pr, yes), and (pr, no), all describe childless nodes in our tree (ie: leaf nodes).  If we want to describe an internal node that has (say) 3 children, we merely extend the tuple to list them: (pr, ?, pr1, pr2, pr3).

Or tree Search: Erw expression 3

In or tree Erw number three (which I assume is the function to find the child nodes), there is the first tuple (pr, ?), and then a second tuple with nested tuples. What does the enumeration mean (pr1, pr2, etc.)? Also, what does "if Altern() holds" mean? Finally, why isn't the third operation recursive, since it trying to find all the child nodes?

The 3rd Erw describes that for a pr without child nodes, ie: looks like (pr, ?), we can expand it by adding children, ie: looks like (pr, ?, pr1, pr2, ... prn)Altern() is a relation, Prob x Prob, ie: a relation from Prob to Prob, that has pairs (just like Erw does).  Instances of the pairs will look like this: (pr, pr). These pairs define that from one (possible partially solved problem) we can go to any of a set of (partially solved) problems that is (hopefully) closer to a complete solution.  The definition of Altern() is, of course, completely dependent on the specific problem domain.  So, what we are saying with the 3rd Erw is along the lines of "We can expand a childless node to the same node with children, and we will use Altern() to tell us exactly what these children will be."  The 3rd Erw is not recursive because nowhere in the the description of it do we call on Erw() itself again.

Or tree Search: Erw expression 4

The last or tree Erw, the fourth, which I assume is the one that actually pics the child node, has two tuples that contain enumerations of b (b1, b2, etc.). What are these, and why is there a b' symbol in the second one.

The 4th Erw describes that for a pr with children, we can choose one, and recursively apply Erw to it (meaning we can mark it yes, mark it no, expand it, or choose one of it's children to recurse on).  (The last choice here, is really not applicable because it won't have any children.)  The primes are used in the second element because the bi's in the first are not necessarily the same as the b'i's in the second, because we chose (and changed) only one of them. 

Assignment

Ambiguous soft constraints

I was looking at the soft constraints for the assignment today and have a question. For certain soft constraints they could be applied multiple times, for example multiple TAs could have first choices which aren't met. Should the penalty be applied for every violation, or just once for if there is any violation?
   Just in case that isn't clear enough, consider a case where TA Dave has picked CPSC 433 as his first choice and TA Lisa has picked CPSC 449 as her first choice, and currently no assignments have been made. Would the penalty be 10, because two TAs don't have their first choice, or just 5 because it only is added once?

Yes, I'm aware of the ambiguities in the specs for the constraints.  I leave these in because that's what you get in real life.  You need to interpret the specs logically.  For example, in you example, ask yourself is it worse that 2 (or 100) TAs don't get there way than if only didn't get their way?  Obviously, the answer is "yes", so you should go with multiplying the penalty.  There are other cases where it might not make a lot of sense to multiply the penalties.  
  If any event, in the final deliverable, your program's output will be compared to other groups' output using MY fitness function.  Minor differences between your fitness function and mine are unlikely to make much difference to your ranking, and even less to your mark.  


UofC
CPSC 433: Artificial Intelligence
Department of Computer Science

Last updated 2013-01-08 23:32
Rob Kremer