Monday, October 8, 2007

[Thinking Cap] for probabilistic propositional logic+Important reading assignment for next class

See if you can answer these on the blog

0.  If I have n propositions, how many possible clauses are there? (Assume that clauses of the form A V A are automatically simplified to A).
     Does this help in convincing you that the resolution theoremproving search procedure is *complete* in that it will terminate whether or not
     the theorem you are trying to prove actually holds?

1. We saw that propositional logic is monotonic and that real world requried "defeasible" or "non-monotonic" reasoning. Is probabilistic reasoning
    monotonic or non-monotonic? Explain.

2. You obviously heard the two words "Probability" and "statistics". What is the difference between them? (or are they basically synonyms?)

3. We made a big point about the need for representing joint distribution compactly. Much of elementary probability/statistics handles
    continuous and multi-valued variables, where specifying the distribution of the single variable itself will need a huge number of numbers.
    How is this normally side-stepped in elementary probability?

[Reading assignment] Make sure to read/review chapter 13 which reviews elementary probability.



Kyle Luce said...

1. Hopefully I am not way off here, but.. I think probabilistic reasoning is non-monotonic. When another truth is added to a set of probability statements, this can further restrict the 'world', therefore providing less truths to find, and shrinking our world as to what is possible.

2. From what I recall, Probability is the raw calculation of certainty, and given one probability, the set of other prob can be calculated. Statistics would be the use and analysis of the probabilities, in greater depth.

3. We can model the certainty/prob of things using "probability factors". This allows us to model situation without considering every possible condition (which could be infinite in real world situations).

RANDY said...

0. With n propositions there can be formulas with length 0-n. Each proposition in each formula can be either positive or negative. This yields sum(2^i,i=0..n)=2^(n+1)-1 total formulas. Since resolution can generate at most all these formulas given formulas only involving n variables, it must terminate.

1. It is non-monotonic - constraints can interact to reduce or increase probabilities, as does actually observing the variables in question.

2. Probability gives the properties of individual observations, while statistics gives the overall properties that result from combining the results of many observations.

Subbarao Kambhampati said...

To Randy-
answer to 0--not quite right. Why is the number of clauses of length i
2^i ? It will be

(n \choose i) 2^i

(there are (n \choose i) ways of getting i variables out of n variables, and we can make a clause with them by taking the variable in each polarity, so there are 2^i clauses.

So, we have the sum

SUM (n \choose i) 2^i

Which can be written as

SUM (n \choose i) 2^i 1^(n-i)

which is just

(1 + 2)^n = 3^n

(of course there is a much simpler way to get to this answer--
in each clause, each variable can occur in three ways: positively, negatively or not at all. This gives 3^n clauses

(can you tell that I am teaching my son permutations/combinations ? ;-)


Answer 2 is fine. Answer 3 is not so fine--I will discuss tomorrow