C677: Reasoning About Uncertainty - Fall '05


Instructor:
Joe Halpern, 4144 Upson, halpern@cs, 5-9562
Admin:
Cindy Robinson, 4146 Upson, cindy@cs, 5-0985
Grader: Leandro Rego (lcr26@ece.cornell.edu)
Classes:
Tuesday, Thursday 1:25 - 2:40, Upson 109 *NOTE ROOM CHANGE*
Office hours:
Wednesday, 11-12, or by appointment *NOTE TIME CHANGE*
Text:
Reasoning About Uncertainty (Halpern). (It should be available in the bookstore.) It is now out in paperback (as of Aug. 15), although the bookstore might not have the paperback copy yet. Either the hardcover or paperback would be fine for the course. (The paperback corrects a few typos in the hardcover and is significantly cheaper.)
Course Description and Outline:
Agents must reason and act in an uncertain world. In order to do so intelligently, they need to deal with and reason about this uncertainty. This course discusses modeling and reasoning about uncertainty, going from purely qualitative notions (an event is either possible or it is not) to quantitative notions such as probability (an event has probability .8), with some consideration of in-between notions of plausibility. I'll consider various logics of reasoning about uncertainty, both propositional and first-order, and discuss the subtleties they reveal. Finally, depending on time, I'll discuss how these approaches give us tools to understand and analyze central problems in the literature, including nonmonotonic reasoning, belief change, counterfactual reasoning, and problems of statistical inference, particularly that of going from statistical information to degrees of belief. Although many of the examples will be drawn from the AI literature, the material is also relevant to distributed systems, philosophy, statistics, and game theory; I will try to make connections to work in all these areas. We will be following the text very closely. (It was based on the course.) We'll definitely cover the first 7 chapters of the text; where we go from there depends partly in class interest.
Prerequisites:
None, beyond basic background in propositional logic and probability theory. (Understanding truth assignments is enough for propositional logic; for probability theory, it's enough to know basic probability, and conditional probability.) However, mathematical maturity is strongly advised. What that means is familiarity with writing up proofs. Any solid theoretical math course will give you that, as will theoretically-oriented CS courses.
Grading:
There will be no tests or final examination. There will be problems handed out (roughly 2-3/week). In order to get a grade, you must sign a form saying you've done all the required reading. There will be problems handed out, typically 2-3 every Thursday, from the book. The grade will be based completely on your performance on the problems. Problems are always due two weeks after they're handed out. If you hand them in one week after they're handed out (strongly recommended!), I will grade them and return them the following week, and you get to hand them in again, to improve your grade. On a redo, you can get a maximum of 1 point less than the original value of the problem. (That is, if the problem was originally out of 10, the most you can get is 9.) I will take the higher grade.
Academic Integrity:
It's OK to discuss the problems with others, but you MUST write up solutions on your own, and understand what you are writing.
Homework
Breaking news