Graduate AI Class: Question and Answers

Answer: The numbers in those probability tables come from a domain expert. There's no automatic way to create them. the idea is that the structure of the Bayes net helps you choose a set of conditional probabilies to ask your expert to supply. This almost always results in you needing to request far fewer numbers from the expert than if you'd asked them to specify the entire joint distribution.

Question: What is the meaning of first order logic? Is there something called second order logic? This term comes up in the slides here and there (e.g planning slides - "first order deductive theorem proving does not scale well"), but I dont quite know what it is

Answer One: First Order Logic is also known as Predicate Logic and it is a syntax with a set-theoretically defined meaning to the syntax for representing general purpose knowledge. You can read about it in Russell and Norvig. This is the first year the the grad AI class will *not* be teaching it (and not expecting you to know it) because although it's moderately interesting, it has not turned out to have as much practical use in AI as people expected it would back in the 70s and 80s.

Answer Two: Yes, there is second-order logic. It will be one where you can quantify over functions/predicates, rather than only over variables.

Here are two examples of second-order logic.

Let P be the class of all polynomial functions. 

A false proposition is:

forall p in P, exists x, s.t. p (x) = 0  

A true proposition is:

exists p in P, exists x and y, s.t. p(x)=p(y)

Question: 2 lectures ago, you taught about robot motion planning. Latombe's Numerical Pot ential Field Method was one of the topic covered. Do you have a journal paper c oncerning NPF? I would like to read up about this topic. Appreciate your assis tance. Thanks.

Answer: Let me know if you have trouble getting a copy of the following answer. If you do, you're welcome to copy my copy.

@article{ltmb:nmrc,
Author      = "J. Barraquand and J. Latombe and B. Langlois",
Title       = "{Numerical Potential Field Techniques for
                Robot Path Planning}",
Journal = "{IEEE Transactions on Systems, Man and Cybernetics}",
Volume = "22",
Number = "2",
Month = "March",
Pages = "224--241",
Year        = "1992"
}

@Book{ltmb:rbtm,
Author      = "J. Latombe",
Title       = "{Robot Motion Planning}",
Publisher   = "{Kluwer}",
Year        = "1991"
}

Question: I am having problems resolving the direction of the arrows in Bayes Nets ...

If we have

1) M: Manuela teaches the class

2) L: The lecturer is late

and we know

1) Andrew is more often late than Manuela

Does the arrow point from M to L (The fact that we know Manuela taught the class influences the fact as to whether the lecturer was late. ... or from L to M (The fact that the lecturer was late helps us decide whether Manuela is teaching the class! (The notes show the link from M to L)

Answer: This is a good question. The semantics of Bayesian Networks do not care which way you draw the arrows in the case where we have two nodes (like M and L) which are correlated. Either of these would be fine:

    M ---> L

or

    L ---> M

In general, when you devise a Bayes Net structure, there are many Bayes Net structures that reflect the same conditional independence assumptions. So there is rarely a unique single correct structure to reflect your independence and conditional independence assumptions. There are usually many.

In the case of two variables there are three possible DAG structures, but only two possible independence assumptions. So two of those structures map onto the same independence assumptions:

   L     M            means    "L and M are independent"

   L --> M            means    "L and M are not necessarily independent"

   L <-- M            means    "L and M are not necessarily independent"

    A ---+           
         |               means something           A ---> C ----> B
         +----> C        very different from
         +----> 
         |
    B ---+

For example, in the left structure A and B are necessarily independent

in the right structure they are not necessarily independent

Another example: in the left structure C could be defined as A XOR B. It could not be defined that way by the right structure.

If you have a moment, look at Figure 2 in http://research.microsoft.com/~dmax/publications/uai96-equiv.pdf

That shows you, for three nodes, all the equivalence classes. You see from that example, unless the thing you want to say about the distribution is "all independence and conditional independence relations hold" (in which case you have a structure with no arcs), in all other cases, the choice of Bayes net structure is not unique.

So what's the bottom line? Bayes nets are a syntax for expressing independence and conditional independence facts about a distribution in a way that is:

(a) Compact, and easy to visually depict

(b) Guarantees that you produce a legal probability distribution

(c) Is suited to certain types of automatic inference

Using this syntax, there is usually more than one way to express the independence or Conditional independence that you the domain expert know about.

Please let me know if this issue remains unclarified, or if it brings up any further questions.

Question: Just checking if I have this right ...

"Bayes Nets for representing and reasoning with uncertainty" Slide 74.

What you are trying to illustrate here is that if the required probability does not contain all the parents of the node ( P(R|T,~S) does not have the parent of R in the apriori section), then one must go back to looking at the joint distrib ution which may still turn out to be EXPENSIVE.

Answer: Completely correct.

Question: Are NPF (Latombe's path planning method) and Bayes Net Inference (slides 8+ of t he Independence and Inference slides) part of the Midterm?

Answer: No, only slides I actually talked through in class will be included in the exam.

Question: Just a quick question on slide #71 in the Bayes Nets for Representing and Reasonoing.

On the last three steps you have (at the end terms):

= ... P(L|~M^S) * P(~M^S)
= ... P(L|~M^S) * P(~MS) * P(S)
= ... P(L|~M^S) * P(~M) * P(S)

Answer: That's an error. It should say P(~M|S) instead of P(~MS). I'll make the change to the slides.. thanks.