Folks:
Project 4--which will involve doing backward chaining generalized modus ponens (as discussed in the class with the apartment pet example today)--is available in the projects page for preview. The due date is not yet decided.
Rao
Wednesday, October 31, 2007
sqrt(2)^sqrt(2) is actually irrational (so you now know two irrationals p & q so p^q is rational)
First of all, my apologies for the confusion I caused today by not acknowledging the convention of right-associativity for exponentiation. There is really
no excuse--2^2^n (as in the number of boolean functions over n variables, or the size of the search space of when you have n state variables and you can't observe
the value of any of the) is up there in the haloween nightmares of computer scientists.
Part 1:
Coming back to the original question, the existential proof that I showed didn't quite tell you any specific irrational numbers p and q for which p^q is rational (we had two pairs of
possibilities for p and q).
In case you are dying to know, sqrt(2)^sqrt(2) is actually
irrational (actually transcendental (*)). So a constructive proof for
our theorem is with p=sqrt(2)^sqrt(2) and q=sqrt(2)
see http://www.math.hmc.edu/funfacts/ffiles/10004.3-5.shtml
(which also points out a more general and easy to understand constructive proof. Consider
e^{log_e q} for any transcendental number e and rational number q--which will be q. All you need to show is log_e(q) is irrational and you can show this easily (If log_e(q) = m/n with integers m and n without common factors, then
q = e^{m/n}. This would mean that e is the root of an algebraic equation x^m - q^n = 0. But the definition of trancendental number is that it cannot be the root of any algebraic equation!).
(*) By the way, transcendental => irrational but not vice versa. In particular, transcendentals are those irrational numbers that cannot be roots of any algebraic equation. Two famous examples of course are e and pi. Notice that proving that a number e *is* transcendental involves showing that e^r for any rational number r cannot be rational (since if it is, then e will be the root of an algebraic equation). Thus, proving transcendentality is not all that easy.
Part 2:
for a nice discussion on the Constructive vs. Classical mathematics--and how during Hilbert's time there was a pretty big controversy in mathematics--with mathematicians such as Brouer insisted that all math that depended on existential proofs be thrown out.Papa Hilbert had to come to rescue--pretty heady stuff.
You might also look at
http://plato.stanford.edu/entries/mathematics-constructive/
which also talks about the "slick" irrational power irrational can be rational proof...
no excuse--2^2^n (as in the number of boolean functions over n variables, or the size of the search space of when you have n state variables and you can't observe
the value of any of the) is up there in the haloween nightmares of computer scientists.
Part 1:
Coming back to the original question, the existential proof that I showed didn't quite tell you any specific irrational numbers p and q for which p^q is rational (we had two pairs of
possibilities for p and q).
In case you are dying to know, sqrt(2)^sqrt(2) is actually
irrational (actually transcendental (*)). So a constructive proof for
our theorem is with p=sqrt(2)^sqrt(2) and q=sqrt(2)
see http://www.math.hmc.edu/funfacts/ffiles/10004.3-5.shtml
(which also points out a more general and easy to understand constructive proof. Consider
e^{log_e q} for any transcendental number e and rational number q--which will be q. All you need to show is log_e(q) is irrational and you can show this easily (If log_e(q) = m/n with integers m and n without common factors, then
q = e^{m/n}. This would mean that e is the root of an algebraic equation x^m - q^n = 0. But the definition of trancendental number is that it cannot be the root of any algebraic equation!).
(*) By the way, transcendental => irrational but not vice versa. In particular, transcendentals are those irrational numbers that cannot be roots of any algebraic equation. Two famous examples of course are e and pi. Notice that proving that a number e *is* transcendental involves showing that e^r for any rational number r cannot be rational (since if it is, then e will be the root of an algebraic equation). Thus, proving transcendentality is not all that easy.
Part 2:
Check out
http://digitalphysics.org/Publications/Cal79/html/cmath.htm
for a nice discussion on the Constructive vs. Classical mathematics--and how during Hilbert's time there was a pretty big controversy in mathematics--with mathematicians such as Brouer insisted that all math that depended on existential proofs be thrown out.Papa Hilbert had to come to rescue--pretty heady stuff.
You might also look at
http://plato.stanford.edu/entries/mathematics-constructive/
which also talks about the "slick" irrational power irrational can be rational proof...
Grade anxiety amelioration program..
Several of you wanted some guidance about how the scores translate into
letter grades at the end of the semester.
As I mentioned there is no automatic translation program. It requires all the deliberative powers of a bleary-eyed full professor to convert them into letter grades.
If it helps, the following are the cumulative scores and lower-bound grade cutoffs that were used once before ( Fall 2003)
This is strictly to give you a non-binding example. Every class is different and
the actual grades this time will again be determined adaptively. (In particular, the last times lowerbounds may or may not be admissible heuristics on this times grades...)
Feel free to ask me questions/express concerns either anonymously or in person. Like I said, at this point, after these many classes, tests, projects, exams and endurance of those never-ending lectures, if you are still enjoying the class, it will be a shame to lose you purely because of grade anxiety...
[I should be in my office much of the time tomorrow, but will be out of office and on travel on Friday. I will be checking my mail though.]
regards
Rao
============================================
From: Subbarao Kambhampati <rao@asu.edu>
To: cse471-f03@parichaalak.eas.asu.edu
Date: Fri, 19 Dec 2003 08:52:33 -0700
Subject: Admissible heuristic for letter grades...
People started asking me for letter grades.
Your final letter grades will be available sometime next week online.
However, I think it is reasonable to give you a lowerbound on your grade.
Here then is an admissible--and reasonably informed (since I am making it
;-) heuristic on estimating your grade:
For Graduate students:
If your cumulative is >80% your lower bound grade will be an A
Above 70, lowerbound grade is B.
For UG students:
If your cumulative is >75% your lower bound grade will be an A
if your cumulative is > 65, your lowerbound grade will be B
if your cumulative is >50, your lowerbound grade will be C
if your cumulative is >35, your lowerbound grade will be D
else E.
***In both cases, if your cumulative+extra credit pushes you over a threshold, then
you get that higher grade.
Rao
ps: I am willing to take comments from people about grade thresholds that
are _below_ the category they
are in (i.e., A folks can tell me whether the A,B,C thresholds should be
changed. B folks can tell me if B and C thresholds can be changed
and so on). You can comment on whether the current thresholds are too
generous or too tight etc.
======================================
letter grades at the end of the semester.
As I mentioned there is no automatic translation program. It requires all the deliberative powers of a bleary-eyed full professor to convert them into letter grades.
If it helps, the following are the cumulative scores and lower-bound grade cutoffs that were used once before ( Fall 2003)
This is strictly to give you a non-binding example. Every class is different and
the actual grades this time will again be determined adaptively. (In particular, the last times lowerbounds may or may not be admissible heuristics on this times grades...)
Feel free to ask me questions/express concerns either anonymously or in person. Like I said, at this point, after these many classes, tests, projects, exams and endurance of those never-ending lectures, if you are still enjoying the class, it will be a shame to lose you purely because of grade anxiety...
[I should be in my office much of the time tomorrow, but will be out of office and on travel on Friday. I will be checking my mail though.]
regards
Rao
============================================
From: Subbarao Kambhampati <rao@asu.edu>
To: cse471-f03@parichaalak.eas.asu.edu
Date: Fri, 19 Dec 2003 08:52:33 -0700
Subject: Admissible heuristic for letter grades...
People started asking me for letter grades.
Your final letter grades will be available sometime next week online.
However, I think it is reasonable to give you a lowerbound on your grade.
Here then is an admissible--and reasonably informed (since I am making it
;-) heuristic on estimating your grade:
For Graduate students:
If your cumulative is >80% your lower bound grade will be an A
Above 70, lowerbound grade is B.
For UG students:
If your cumulative is >75% your lower bound grade will be an A
if your cumulative is > 65, your lowerbound grade will be B
if your cumulative is >50, your lowerbound grade will be C
if your cumulative is >35, your lowerbound grade will be D
else E.
***In both cases, if your cumulative+extra credit pushes you over a threshold, then
you get that higher grade.
Rao
ps: I am willing to take comments from people about grade thresholds that
are _below_ the category they
are in (i.e., A folks can tell me whether the A,B,C thresholds should be
changed. B folks can tell me if B and C thresholds can be changed
and so on). You can comment on whether the current thresholds are too
generous or too tight etc.
======================================
Current Cumulatives (as of Haloween day)
Folks:
To give you an idea of your standing in the class, here are the current cumulatives
(471 and 598 students are put in two different groups).
Note that to get you a scaled score, I gave 1% point to Proj 0, 10% to Proj 1, 5,5 and 3 points
to the three homeworks and 20pts to Midterm. The specific points may change a bit, but this should
give you a good idea.
Note that extra credit points are not converted now (these are "unrealized gains" that will be realized only after
final grades are set up).
In terms of grades, note that (1) I have no fixed thresholds for grades (2) I plan to give all grades--
A+/A/A-/B+/B/B- etc--the works..
Let me know if you have specific questions.
Rao
To give you an idea of your standing in the class, here are the current cumulatives
(471 and 598 students are put in two different groups).
Note that to get you a scaled score, I gave 1% point to Proj 0, 10% to Proj 1, 5,5 and 3 points
to the three homeworks and 20pts to Midterm. The specific points may change a bit, but this should
give you a good idea.
Note that extra credit points are not converted now (these are "unrealized gains" that will be realized only after
final grades are set up).
In terms of grades, note that (1) I have no fixed thresholds for grades (2) I plan to give all grades--
A+/A/A-/B+/B/B- etc--the works..
Let me know if you have specific questions.
Rao
Tuesday, October 30, 2007
Midterm grades statistics..
Folks
Here are the stats on the midterm:
471: Max: 64; Min: 12 Avg:42 St.dev: 15
(Marks in rank order:
64; 57; 51.5; 41.5; 41; 39; 37; 36; 12
598: Max: 73.5 Min: 9 Avg: 52 St.dev: 16
(Marks in rank order:
73.5; 70; 66.5; 64.5; 64; 61.5; 61; 59; 58.5; 58.5; 57; 49; 49; 48;
48; 39; 38.5; 36; 26.5; 9
I will return the graded exams in class tomorrow.
Check out http://rakaposhi.eas.asu.edu/cse471/exam-philosophy.jpg for my half-baked philosophy on exams and grades might mean.
If you need to vent, feel free to use the anonymous channel http://rakaposhi.eas.asu.edu/cgi-bin/mail?rao
If, after seeing your exam tomorrow, you are worried about how you are doing, come and talk to me in the office hours (like I said, it would
be wise to talk to me before taking any drop decisions).
Finally, if either of the students who ranked at the top of the 471 or 598 list can guess who they are and send me an email I will buy them a geek present
(read "a book") for doing well *and* being brash. (I promise not to subtract any marks from your total even if you guess wrong ;-).
cheers
Rao
Here are the stats on the midterm:
471: Max: 64; Min: 12 Avg:42 St.dev: 15
(Marks in rank order:
64; 57; 51.5; 41.5; 41; 39; 37; 36; 12
598: Max: 73.5 Min: 9 Avg: 52 St.dev: 16
(Marks in rank order:
73.5; 70; 66.5; 64.5; 64; 61.5; 61; 59; 58.5; 58.5; 57; 49; 49; 48;
48; 39; 38.5; 36; 26.5; 9
I will return the graded exams in class tomorrow.
Check out http://rakaposhi.eas.asu.edu/cse471/exam-philosophy.jpg for my half-baked philosophy on exams and grades might mean.
If you need to vent, feel free to use the anonymous channel http://rakaposhi.eas.asu.edu/cgi-bin/mail?rao
If, after seeing your exam tomorrow, you are worried about how you are doing, come and talk to me in the office hours (like I said, it would
be wise to talk to me before taking any drop decisions).
Finally, if either of the students who ranked at the top of the 471 or 598 list can guess who they are and send me an email I will buy them a geek present
(read "a book") for doing well *and* being brash. (I promise not to subtract any marks from your total even if you guess wrong ;-).
cheers
Rao
Monday, October 29, 2007
Required reading for Wednesday
Folks
Please read the following parts from the text for Wednesday's class. We will likely do just one class on FOPC inference and so it will help if you have read this stuff before.
9.1. Propositional vs. First-Order Inference ... 272
Inference rules for quantifiers ... 273
Reduction to propositional inference ... 274
9.2. Unification and Lifting ... 275
A first-order inference rule ... 275
Unification ... 276
9.4. Backward Chaining ... 287
A backward chaining algorithm ... 287
9.5. Resolution ... 295
Conjunctive normal form for first-order logic ... 295
The resolution inference rule ... 297
Example proofs ... 297
Resolution strategies ... 304
Unit preference ... 305
Set of support ... 305
Input resolution ... 305
Subsumption ... 306
Please read the following parts from the text for Wednesday's class. We will likely do just one class on FOPC inference and so it will help if you have read this stuff before.
9.1. Propositional vs. First-Order Inference ... 272
Inference rules for quantifiers ... 273
Reduction to propositional inference ... 274
9.2. Unification and Lifting ... 275
A first-order inference rule ... 275
Unification ... 276
9.4. Backward Chaining ... 287
A backward chaining algorithm ... 287
9.5. Resolution ... 295
Conjunctive normal form for first-order logic ... 295
The resolution inference rule ... 297
Example proofs ... 297
Resolution strategies ... 304
Unit preference ... 305
Set of support ... 305
Input resolution ... 305
Subsumption ... 306
Friday, October 26, 2007
Project 2 submission date/late submission etc..
Folks
We are getting tons of mails on project 2. So we thought we will send
a single mail to the entire class
1. Project 2 will be accepted without penalty until close of business
today (the department office closes 5pm).
2. If you have not used your extension, you can exercise it and submit
the project by Monday *in class* (just write that you are using your
extension).
3. If you have already used your extension and still can't complete it
by today, try to submit it by Monday morning in class. There *will be*
a late penalty on this submission.
Note that I am not trying to be mean--but rather fair to those
(minority of) people who did change their schedule around to complete
the project already.
Happy sudoku
Rao
[Oct 26, 2007]
Tuesday, October 23, 2007
Entailment status and learning
Here is something that came up at the review session today that is probably bears repeating to a wider audience.
Consider an agent which has a current knowledge base KB, and you are trying to "tell" it another fact f
We can distinguish between three types of entailment status between KB and f:
1. KB |= f [the agent is being told what it already implicitly knows]
2. KB |= ~f [the agent is being told the opposite of what it already implicitly knows]
3. Neither 1 nor 2. [The agent is being told something "completely new" ]
Let us ask the question---in which of these cases can you say that the agent "learned" something?
In case 3 ( i.e., the KB neither entails f nor entails ~f), it is easy to see that f is truly new knowledge being added to the agent.
So, learning clearly occurs here. This is called "knowledge level learning".
In case 2, KB already entails ~f. Now the agent is being told f is true. If it goes ahead and adds f, then it will have an inconsistent
KB. To resolve the inconsistency, either the agent should refuse to believe f, or "lobotomize" itself so that it can no longer prove ~f.
To do the latter, the agent needs to consider all ways of proving ~f and for each of those proofs, remove at least one axiom taking part in the
proof (so that that proof doesn't go through). Thus, in this case, the agent "learns" what part of its existing knowledge base is faulty and should
be thrown out-- (this is called "theory revision"). It is obvious that we do it ourselves..
In case 1, f is already entailed by the KB, so in a sense there is no learning taking place (the agent is being told what it already knows). However,
if checking the entaiment of f takes a long time, then remembeing the proved theorem can improve the agent's performance (in as much as it can
stop it from having to do this computation again). This is a form of "speedup learning" (and the "factor tables" that are computed and stored by the variable
elimination algorithm we just talked in the class is a form of speedup learning).
Rao
ps: If you are wondering "By what stretch of imagination can this stuff be construed as 'review', I offer you the following quote from Northern Exposure
(for those of you old enough to have seen the show ;-)
"My student came to me with a desire to know the time, and
I taught her how to make a watch"
-Chris in the morning..
Consider an agent which has a current knowledge base KB, and you are trying to "tell" it another fact f
We can distinguish between three types of entailment status between KB and f:
1. KB |= f [the agent is being told what it already implicitly knows]
2. KB |= ~f [the agent is being told the opposite of what it already implicitly knows]
3. Neither 1 nor 2. [The agent is being told something "completely new" ]
Let us ask the question---in which of these cases can you say that the agent "learned" something?
In case 3 ( i.e., the KB neither entails f nor entails ~f), it is easy to see that f is truly new knowledge being added to the agent.
So, learning clearly occurs here. This is called "knowledge level learning".
In case 2, KB already entails ~f. Now the agent is being told f is true. If it goes ahead and adds f, then it will have an inconsistent
KB. To resolve the inconsistency, either the agent should refuse to believe f, or "lobotomize" itself so that it can no longer prove ~f.
To do the latter, the agent needs to consider all ways of proving ~f and for each of those proofs, remove at least one axiom taking part in the
proof (so that that proof doesn't go through). Thus, in this case, the agent "learns" what part of its existing knowledge base is faulty and should
be thrown out-- (this is called "theory revision"). It is obvious that we do it ourselves..
In case 1, f is already entailed by the KB, so in a sense there is no learning taking place (the agent is being told what it already knows). However,
if checking the entaiment of f takes a long time, then remembeing the proved theorem can improve the agent's performance (in as much as it can
stop it from having to do this computation again). This is a form of "speedup learning" (and the "factor tables" that are computed and stored by the variable
elimination algorithm we just talked in the class is a form of speedup learning).
Rao
ps: If you are wondering "By what stretch of imagination can this stuff be construed as 'review', I offer you the following quote from Northern Exposure
(for those of you old enough to have seen the show ;-)
"My student came to me with a desire to know the time, and
I taught her how to make a watch"
-Chris in the morning..
Monday, October 22, 2007
(optional) Review session for midterm-- starts 4pm in BY 576 on Tuesday
As per the popular demand, I will hold a "review" session starting 4pm in BY 576 (in the same corridor as my office)
rao
rao
Sunday, October 21, 2007
Reminder: *Important*--required reading for Monday's class
---------- Forwarded message ----------
From: Subbarao Kambhampati <subbarao2z2@gmail.com>
Date: Oct 17, 2007 4:42 PM
Subject: [Blog for Fall 2007 ASU CSE 471/598 Introduction to AI] *Important*--required...
To: subbarao2z2@gmail.com
Make sure to read pages 504 to 515-- especially pages 507-509 before coming to the class on Monday
(when we will discuss inference in bayes networks)
rao
--
Posted By Subbarao Kambhampati to Blog for Fall 2007 ASU CSE 471/598 Introduction to AI at 10/17/2007 04:42:00 PM
Re: Project 3 assigned and Homework 3 socket opened.. (I meant homework 4)
I meant homework 4 of course...
rao
rao
On 10/21/07, Subbarao Kambhampati <rao@asu.edu> wrote:
Folks
Project 3 --which is really a mini-project--(Bayes networks to save christmas in springfield) is assigned. It doesn't require any coding (!).
Homework 3 socket is opened and I added questions on Bayes Networks. It is also likely to be due around the same time as project 3.
Rao (trying out for the "most popular professor" award ;-)
Project 3 assigned and Homework 3 socket opened..
Folks
Project 3 --which is really a mini-project--(Bayes networks to save christmas in springfield) is assigned. It doesn't require any coding (!).
Homework 3 socket is opened and I added questions on Bayes Networks. It is also likely to be due around the same time as project 3.
Rao (trying out for the "most popular professor" award ;-)
Project 3 --which is really a mini-project--(Bayes networks to save christmas in springfield) is assigned. It doesn't require any coding (!).
Homework 3 socket is opened and I added questions on Bayes Networks. It is also likely to be due around the same time as project 3.
Rao (trying out for the "most popular professor" award ;-)
Re: Homework 3 solutions posted online
You are right.. I proved the soundness of ~B => ~A (and in fact said so in the solutions).
But that is not what I asked for :-(
I have now modifed the online solutions.
rao
But that is not what I asked for :-(
I have now modifed the online solutions.
rao
On 10/21/07, Kyle Luce <kyle.luce@asu.edu> wrote:
Hi,
I am confused by HW3 solution 1, part 2.
I got:
A => B can be written as: ~A V B
~A => ~B can be written as: A V ~B
A
B
~A V B
A V ~B
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
1
Am I wrong in my conversion of the implication ~A => ~B to A V ~B or is it obvious where I went wrong? Also, is it true that for soundness, every time A => B is true, that ~A => ~B should also be true? I just want to double check even my basic understanding.On 10/21/07, Subbarao Kambhampati < rao@asu.edu > wrote:Folks
Homework 3 solutions are now posted online.
With this, you have all the solutions for all the homeworks that can help you with Wedneday's exam
Rao
Homework 3 solutions posted online
Folks
Homework 3 solutions are now posted online.
With this, you have all the solutions for all the homeworks that can help you with Wedneday's exam
Rao
Homework 3 solutions are now posted online.
With this, you have all the solutions for all the homeworks that can help you with Wedneday's exam
Rao
Saturday, October 20, 2007
[cse 471] Instructions for submitting project-2
Hi all,
The submission procedure for project-2 is same as the previous projects.
I have opened a link in the "Assignments" section in the blackboard section, for project-2 (Sudoku using LISP). You should all submit your LISP code there. Name file as <firstname>_<Lastname>.lisp.
And you should turn in the hard copy of the project report (commented code + test runs + detailed analysis) before the class.
Thanks,
Aravind
Wednesday, October 17, 2007
*Important*--required reading for Monday's class pp 504--515 in the text book
Make sure to read 504 to 515-- especially 507-509 before coming to the class on Monday
(when we will discuss inference in bayes networks)
rao
(when we will discuss inference in bayes networks)
rao
links promised in today's class
1. The Martian life "paradox" (and how you can avoid the paradox by assessing only enough probabilities to avoid internal inconsistency)
see http://rakaposhi.eas.asu.edu/gardner-indifference.pdf
2. Causality and graphical models -- a nice talk by Judea Pearl:
http://singapore.cs.ucla.edu/IJCAI99/index.html
(has the great example of "a suitcase with two locks")
3. Atul Gawande (a practising doctor who proves that good writing doesn't have to be associated with non-technical professions ;-) talks about the inevitable progress of medicine where machines become doctors and doctors become machines:
http://www.newyorker.com/archive/1998/03/30/1998_03_30_074_TNY_LIBRY_000015236
(only an abstract is available online. If you are interested, I can dig out a hard copy, or you can plunk for his book
http://www.amazon.com/Complications-Surgeons-Notes-Imperfect-Science/ in which this article appears as
"The Computer and the Hernia Factory" )
(I forgot what other references I promised to send you--if you recall, remind me)
Rao
[cse 471] Homework-2 Announcements (grade distribution, marking scheme and a missing solution..)
Hi,
Grade Distrubution for Homework-2 :
| Grad | avg:87.4 | 96(H) | 74(L) |
| | | | |
| UG | avg:84.8 | 96(H) | 72(L) |
And marking scheme is as follows::
Total : 100 points
PART A:
1. 5
2. 6 (2+2+2)
3.
Part A: 4 (2+2)
Part B: 4
Part C: 8
4.
Part A: 3
Part B: 3
5. 4
PART B: (true or flase )
18 (3 X 6)
[CSP1]
i. 5
ii. 3
iii. 6
[CSP2]
1.1 6
1.2 4
1.3 4
Qn. II (Pattern DB Heuristics)
A.
A.1 2
A.2 2
A.3 3
A.4 5
B.
5
--------------------
And, first part of the CSP solution is missing from the solutions page on the course web-site. I am writing it down below:
[CSP1]
1.
Let Jobs be J1, J2, J3 and J4 and days are d1,d2,d3.
Domains: J1 = {d1,d2,d3}, J2 = {d1,d2,d3}, J3 = {d1,d2,d3}
Constraints as no-goods:
(J1>=J2), (J2>=J3 & J2>=J4), (J3=J2) (J3=J4), (|J4 - J1| < 1)
2. No its not binary. (There is a ternary constraint)
3.
Using forward checking and dynamic variable ordering:
path1 at root: pickup J2=d1, using forward checking J1={ } => this a FAIL case
path2 at root: pickup J2 = d2. [ D(J1) = {d1} D(J3)= {d1,d3} D(J4) = {d1,d2,d3} ]
--> Followed by J1=d1 [ D(J3) = {d1,d3} D(J4) = {d3} ]
--> Followed by J4=d3 [ (D(J3) = {d1} ]
--> Followed by J3=d1 --> all variables are exhausted with no contraints => SUCCESS
So, the assignment is { J1,J3 = d1 ; J2 = d2; J4 = d3 }
----------------
Let me know if you have any questions.
Thanks,
Aravind
Monday, October 15, 2007
[Thinking cap questions on bayes networks]
0.1. Gi ven a 5 boolean random variables, how many different joint distributions can you write on them?
If now I give the topology of a bayes network on these 5 variables, how many different joint distributions can you write?
0.2. Given a bayes network on 5 nodes that has *no* edges (i.e., all nodes are disconnected), exactly many different conditional independence assertions does the network capture? (linear? polynomial or exponential?)
1. You have been given the topology of a bayes network, but haven't yet gotten the conditional probability tables
(to be concrete, you may think of the pearl alarm-earth quake scenario bayes net).
Your friend shows up and says he has the joint distribution all ready for you. You don't quite trust your
friend and think he is making these numbers up. Is there any way you can prove that your friends' joint
distribution is not correct?
2. Continuing bad friends, in the question above, suppose a second friend comes along and says that he can give you
the conditional probabilities that you want to complete the specification of your bayes net. You ask him a CPT entry,
and pat comes a response--some number between 0 and 1. This friend is well meaning, but you are worried that the
numbers he is giving may lead to some sort of inconsistent joint probability distribution. Is your worry justified ( i.e., can your
friend give you numbers that can lead to an inconsistency?)
(To understand "inconsistency", consider someone who insists on giving you P(A), P(B), P(A&B) as well as P(AVB) and they
wind up not satisfying the P(AVB)= P(A)+P(B) -P(A&B)
[or alternately, they insist on giving you P(A|B), P(B|A), P(A) and P(B), and the four numbers dont satisfy the bayes rule]
3. (mentioned in the class)
(to be concrete, you may think of the pearl alarm-earth quake scenario bayes net).
Your friend shows up and says he has the joint distribution all ready for you. You don't quite trust your
friend and think he is making these numbers up. Is there any way you can prove that your friends' joint
distribution is not correct?
2. Continuing bad friends, in the question above, suppose a second friend comes along and says that he can give you
the conditional probabilities that you want to complete the specification of your bayes net. You ask him a CPT entry,
and pat comes a response--some number between 0 and 1. This friend is well meaning, but you are worried that the
numbers he is giving may lead to some sort of inconsistent joint probability distribution. Is your worry justified ( i.e., can your
friend give you numbers that can lead to an inconsistency?)
(To understand "inconsistency", consider someone who insists on giving you P(A), P(B), P(A&B) as well as P(AVB) and they
wind up not satisfying the P(AVB)= P(A)+P(B) -P(A&B)
[or alternately, they insist on giving you P(A|B), P(B|A), P(A) and P(B), and the four numbers dont satisfy the bayes rule]
3. (mentioned in the class)
Your friend heard your claims that Bayes Nets can represent any possible conditional independence assertions exactly. He comes to you
and says he has four random variables, X, Y, W and Z, and only TWO conditional independence assertions:
X .ind. Y | {W,Z}
W .ind. X | {X, Y}
He dares you to give him a bayes network topology on these four nodes that exactly represents these and only these conditional independencies.
Can you? (Note that you only need to look at 4 vertex directed graphs).
and says he has four random variables, X, Y, W and Z, and only TWO conditional independence assertions:
X .ind. Y | {W,Z}
W .ind. X | {X, Y}
He dares you to give him a bayes network topology on these four nodes that exactly represents these and only these conditional independencies.
Can you? (Note that you only need to look at 4 vertex directed graphs).
4. As foreshadowed in the class, the answer to 3 above is going to be "No". How serious an issue do you think this is? In particular, suppose your domain has exactly set A of conditional independencies. You have two bayes network configurations B1 and B2. The CIA(B1) is a superset of
A and CIA(B1) is a subset of A. Clearly, neither B1 nor B2 exactly represent what you know about the domain. If you have to choose one to model the domain, what are the tradeoffs in choosing B1 vs. B2?
Rao
-------------
Thursday, October 11, 2007
Homework 3 socket closed; Due 10/17
As per my previous mail, I added one question on k-consistency to Homework 3, and closed its
socket. It is now due on 10/17 (next wednesday).
I will make the solutions to the homework available soon after that.
The midterm on 10/24 will involve all the material covered until 10/8.
Rao
socket. It is now due on 10/17 (next wednesday).
I will make the solutions to the homework available soon after that.
The midterm on 10/24 will involve all the material covered until 10/8.
Rao
(Important) Proposed schedule for the semester+midterm on 10/24
Folks
I put up an approximate schedule for the rest of the semester (in the lecture notes page--below the lecture notes).
Assuming I got the dates right, we have 16 more classes (including the make-up class for 9/24 to be scheduled).
As for the mid-term: Here is my thinking.
I would like to include all the material discussed upto and including 10/8 (basically propositional logic) into the midterm.
I normally prefer to have you do homeworks on the topics that are being tested in the in-class midterm.
So, I am closing the homework 3 socket and making it due by next week (it is clearly a shorter homework than the other two).
This makes the optimal date for the midterm be 10/24
Since the homework deadline is sneaking up before the project 2 deadline, I am okay with accepting project 2 until 10/26
(Friday).
Speak up very soon if you see any major problems with this plan
Rao
I put up an approximate schedule for the rest of the semester (in the lecture notes page--below the lecture notes).
Assuming I got the dates right, we have 16 more classes (including the make-up class for 9/24 to be scheduled).
As for the mid-term: Here is my thinking.
I would like to include all the material discussed upto and including 10/8 (basically propositional logic) into the midterm.
I normally prefer to have you do homeworks on the topics that are being tested in the in-class midterm.
So, I am closing the homework 3 socket and making it due by next week (it is clearly a shorter homework than the other two).
This makes the optimal date for the midterm be 10/24
Since the homework deadline is sneaking up before the project 2 deadline, I am okay with accepting project 2 until 10/26
(Friday).
Speak up very soon if you see any major problems with this plan
Rao
Readings from the text book updated..
Folks
My apologies for the confusion(s) caused by the fact that the "Readings" tab in the course page leads to readings from/for Fall 2006
edition, and we are doing things in a different order.
I have now edited the "Lecture notes" page so for each week, the chapters/sections form R&N that are "covered" that week are explicitly
listed. To avoid any future confusion, I removed the "readings" link from the web page.
I should make the following disclaimer
For the class test(s), you are only responsible for the material/topics that is actually covered in the class.
I did my best to make pointers to the text sections that correspond to what was covered. However, I will not
ask topics that were not discussed in the class, even if they were discussed in those sections in the text.
On the other hand, if I discussed something that is not explicitly present in the text, you are still responsible for it.
regards
Rao
My apologies for the confusion(s) caused by the fact that the "Readings" tab in the course page leads to readings from/for Fall 2006
edition, and we are doing things in a different order.
I have now edited the "Lecture notes" page so for each week, the chapters/sections form R&N that are "covered" that week are explicitly
listed. To avoid any future confusion, I removed the "readings" link from the web page.
I should make the following disclaimer
For the class test(s), you are only responsible for the material/topics that is actually covered in the class.
I did my best to make pointers to the text sections that correspond to what was covered. However, I will not
ask topics that were not discussed in the class, even if they were discussed in those sections in the text.
On the other hand, if I discussed something that is not explicitly present in the text, you are still responsible for it.
regards
Rao
Wednesday, October 10, 2007
[cse 471] Recitation Session for Project-2 (tomorrow 3-4 PM)
Hello all,
I will be holding a recitation session for project-2 tomorrow during my regular office hours (3-4 PM thursday).
We will meet in BYENG 210. (classroom next to open lab)
Thanks,
Aravind
Monday, October 8, 2007
A specimen midterm exam
Here is a specimen midterm for your edification:
http://rakaposhi.eas.asu.edu/cse471/specimen-midterm.pdf
rao
http://rakaposhi.eas.asu.edu/cse471/specimen-midterm.pdf
rao
[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.
Rao
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.
Rao
[cse 471] Proj-1 statistics, grading scheme and comments
Hi all,
Here are some details on project-1 evaluation:
Grade distribution:
| Grad: 93.4 | (Avg) | 100 (H) | 74 (L) |
| | | | |
| UG: 90.5 | (Avg) | 99 (H) | 74 (L) |
ExtraCredit: UG (Highest - 14) Grad (Highest - 40)
Grading Scheme:
Part-1 -- 32 pts ( 2+5+5+5+5+10 - for the tasks)
Part 2 -- 36 pts
A* function - 10 pts
1. Code to collect different statistics - (3+3+3+4+2) - 15 pts
2. Print path - 5 pts
(efficiency + quality of code ) - 6 pts
Part 3 -- Analysis (32 pts)
Correct runs for given 5 test cases with all heuristics and metrics -- 10 pts
Comparison of various heuristics / comments on trends in computed statistics -- 10 pts
Other interesting findings, observations, exceptions and proposed improvements -- 12 pts
Extra Credit: (40 pts)
1. DFS -- 5 pts
2. Weighted F-function -- 8 pts
3. Redundant ancestral removal -- 7 pts
4. Pattern Database heuristic -- 20 pts
Comments::
* Most of you did well (following all the instructions I had sent earlier) and submitted a good report with formatted code, implementation details and analysis of various methods and heuristics.
* 2 students completed all the extra credit problems. In fact, one of them additionally implemented 'pancake sorting' using A* search to test its working on problems with higher branching factor. You're highly encouraged to try such new things, especially to look for exceptions in the given methods/trends, and suggestions for improving the solutions etc.
* Some of you have to follow better coding practices.
- A couple of students coded three different child generation functions (one for each heuristic) -- which is a very bad coding practice. You should write generalized functions.
- And, hard coding the values should be avoided.
- While printing results to the console, you should format the results properly. (ex: printing the path to goal node, some of you just printed the LISP representation of arrays)
Please let me know if you have any questions on grading.
Thanks,
Aravind
Wednesday, October 3, 2007
Project 2 assigned; description of what you need to do is online now. Due Oct 22nd.
Please note that the mid-term is likely to be around 10/17 timeframe. So, you might want to get cracking
on the project to get it out of your way.
Rao
on the project to get it out of your way.
Rao
*Real slides* for today's class now available online..
Folks
Since today's class went into a long and unplanned (but nevertheless very important) detour,
I added slides that actually correspond to the discussion that was done in the class
I strongly encourage you to look at those slides. Among other things, the slides give you clear
comparisons between k-consisteny and forward checking, as well as a full example of enforcing arc-consistency.
rao
Since today's class went into a long and unplanned (but nevertheless very important) detour,
I added slides that actually correspond to the discussion that was done in the class
I strongly encourage you to look at those slides. Among other things, the slides give you clear
comparisons between k-consisteny and forward checking, as well as a full example of enforcing arc-consistency.
rao
Monday, October 1, 2007
Results of class survey
Folks:
Here are the tabulated results from the class survey that Kartik sent me. I am sharing them with you so you can see how you stack up with the "majority" view in the class on various operational issues.
On first glance, I don't quite see any alarming trends in the survey (other than, perhaps, the fact that most of our graduate students are "one sided" ;-) ) So I guess I can--like Brother Bush--stick to the course as it were.. If you see trends I am missing, let me know (you can use the anonymous mail service).
Note that the sheet shows both percentages over all students and also over 471/598 groups separately. About the only place there is a significant divergence between 471 and 598 students is (1) whether the projects should be made less challenging and (2) depth vs. breadth of lecture material
Rao
------------------------------
Notes from Kartik:
Here are the tabulated results. A few notes:
1. Quite a few of the graduate students didn't flip over to see that there was another side.
2. Not everyone answered everything
3. For the multiple answers OK questions, I used the total responses received as the denominator for the percentages, but for the single answer ones, the denominator was always either the number of UG and G students.
4. There were a lot of hand-written comments, especially from the grad section. I didn't know what to do with these vis-a-vis the excel sheet.
Kartik
---------------------
---------------------
Sheet1
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 1 | CSE 471/598 Fall 2007 | UG | UG % | Grad | G % | Total % |
| 2 | Class Survey | |||||
| 3 | Please Circle the appropriate choice for each questions | |||||
| 4 | ||||||
| 5 | ABOUT YOU | |||||
| 6 | Qn0 I am taking the course as | |||||
| 7 | CSE471 | 9 | 31.03 % | 31.03 % | ||
| 8 | CSE598 | 20 | 68.97 % | 68.97 % | ||
| 9 | ||||||
| 10 | QN1 The pace of the class/lectures is | |||||
| 11 | somewhat slow | 1 | 11.11 % | 3 | 15.00 % | 13.79 % |
| 12 | too slow | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 13 | somewhat fast | 3 | 33.33 % | 6 | 30.00 % | 31.03 % |
| 14 | too fast | 1 | 11.11 % | 1 | 5.00 % | 6.90 % |
| 15 | just right | 4 | 44.44 % | 9 | 45.00 % | 44.83 % |
| 16 | ||||||
| 17 | QN2 The lecture(s) that you liked most until now (you can circle multiple) | |||||
| 18 | The intro lectures | 4 | 16.00 % | 3 | 7.69 % | 10.94 % |
| 19 | The Agent Lectures | 2 | 8.00 % | 4 | 10.26 % | 9.38 % |
| 20 | The Blind search lectures | 4 | 16.00 % | 6 | 15.38 % | 15.63 % |
| 21 | The informed search (A*) lectures | 8 | 32.00 % | 17 | 43.59 % | 39.06 % |
| 22 | The CSP Lectures | 7 | 28.00 % | 9 | 23.08 % | 25.00 % |
| 23 | Pattern Databases | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 24 | They are all bad | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 25 | ||||||
| 26 | QN3 The lecture(s) that you liked *least* until now (you can circle multiple) | |||||
| 27 | The intro lectures | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 28 | The Agent Lectures | 3 | 30.00 % | 6 | 33.33 % | 32.14 % |
| 29 | The Blind search lectures | 1 | 10.00 % | 1 | 5.56 % | 7.14 % |
| 30 | The informed search (A*) lectures | 1 | 10.00 % | 1 | 5.56 % | 7.14 % |
| 31 | The CSP Lectures | 2 | 20.00 % | 5 | 27.78 % | 25.00 % |
| 32 | Pattern Databases | 1 | 10.00 % | 0 | 0.00 % | 3.57 % |
| 33 | They are all great | 2 | 20.00 % | 5 | 27.78 % | 25.00 % |
| 34 | ||||||
| 35 | QN4 Which type of lectures did you follow better | |||||
| 36 | The lectures done with slides | 2 | 22.22 % | 2 | 10.00 % | 13.79 % |
| 37 | The lectures done with white-board | 1 | 11.11 % | 4 | 20.00 % | 17.24 % |
| 38 | Those with a mix | 6 | 66.67 % | 13 | 65.00 % | 65.52 % |
| 39 | ||||||
| 40 | QN5 The lecture style | |||||
| 41 | Keeps you engaged | 2 | 22.22 % | 9 | 45.00 % | 37.93 % |
| 42 | overwhelms you | 1 | 11.11 % | 3 | 15.00 % | 13.79 % |
| 43 | reasonable | 6 | 66.67 % | 8 | 40.00 % | 48.28 % |
| 44 | Conducive to a pre-prandial snooze | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 45 | ||||||
| 46 | QN6 The class is | |||||
| 47 | Too much "Teacher Talking" | 4 | 44.44 % | 2 | 10.00 % | 20.69 % |
| 48 | Sufficiently interactive | 5 | 55.56 % | 17 | 85.00 % | 75.86 % |
| 49 | Too interactive | 0 | 0.00 % | 1 | 5.00 % | 3.45 % |
| 50 | ||||||
| 51 | QN7 The material (as of now) is | |||||
| 52 | Exciting | 1 | 11.11 % | 10 | 50.00 % | 37.93 % |
| 53 | Boring | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 54 | okay | 8 | 88.89 % | 10 | 50.00 % | 62.07 % |
| 55 | ||||||
| 56 | QN8 The presentation level | |||||
| 57 | Goes right over my head | 1 | 11.11 % | 4 | 20.00 % | 17.24 % |
| 58 | Spoonfeeds me by repeating every little thing | 1 | 11.11 % | 1 | 5.00 % | 6.90 % |
| 59 | Just right for me | 7 | 77.78 % | 15 | 75.00 % | 75.86 % |
| 60 | ||||||
| 61 | QN9 Most of the the extra discussion on the blog is, for the most part, | |||||
| 62 | lapped-up by me | 2 | 22.22 % | 9 | 45.00 % | 37.93 % |
| 63 | ignored by me | 6 | 66.67 % | 8 | 40.00 % | 48.28 % |
| 64 | What extra stuff? | 1 | 11.11 % | 0 | 0.00 % | 3.45 % |
| 65 | ||||||
| 66 | QN10 I am able to get help when needed from the Instructor | |||||
| 67 | Strongly agree | 0 | 0.00 % | 9 | 45.00 % | 31.03 % |
| 68 | Okay | 7 | 77.78 % | 11 | 55.00 % | 62.07 % |
| 69 | Not really.. | 1 | 11.11 % | 0 | 0.00 % | 3.45 % |
| 70 | ||||||
| 71 | QN11 I am able to get help when needed from the TA | |||||
| 72 | Strongly agree | 1 | 11.11 % | 11 | 55.00 % | 41.38 % |
| 73 | Okay | 5 | 55.56 % | 9 | 45.00 % | 48.28 % |
| 74 | Not really.. | 2 | 22.22 % | 0 | 0.00 % | 6.90 % |
| 75 | ||||||
| 76 | ||||||
| 77 | QN12 The expectations/demands of the course/instructor are | |||||
| 78 | Unreasonably high | 2 | 22.22 % | 2 | 10.00 % | 13.79 % |
| 79 | Unreasonably low | 0 | 0.00 % | 0 | 0.00 % | 0.00 % |
| 80 | Challenging but reasonable | 7 | 77.78 % | 18 | 90.00 % | 86.21 % |
| 81 | ||||||
| 82 | QN13 The lecture material is | |||||
| 83 | Too depth oriented | 2 | 22.22 % | 0 | 0.00 % | 6.90 % |
| 84 | Too breadth oriented | 3 | 33.33 % | 5 | 25.00 % | 27.59 % |
| 85 | Just right | 3 | 33.33 % | 15 | 75.00 % | 62.07 % |
| 86 | ||||||
| 87 | QN14 The lectures are | |||||
| 88 | Too much intuition and too little formal detail | 1 | 11.11 % | 3 | 15.00 % | 13.79 % |
| 89 | Too much formal detail, too little intuition | 3 | 33.33 % | 2 | 10.00 % | 17.24 % |
| 90 | Balanced between intuition and detail | 4 | 44.44 % | 11 | 55.00 % | 51.72 % |
| 91 | ||||||
| 92 | Qn 15. The lectures | |||||
| 93 | Complement the textbook | 6 | 66.67 % | 15 | 75.00 % | 72.41 % |
| 94 | Repeat the textbook | 2 | 22.22 % | 0 | 0.00 % | 6.90 % |
| 95 | Are mostly disjoint from the textbook | 0 | 0.00 % | 1 | 5.00 % | 3.45 % |
| 96 | ||||||
| 97 | QN16 In your opinion there should be | |||||
| 98 | More frequent homeworks | 0 | 0.00 % | 2 | 10.00 % | 6.90 % |
| 99 | Less frequent homeworks | 2 | 22.22 % | 8 | 40.00 % | 34.48 % |
| 100 | Current schedule is fine | 6 | 66.67 % | 7 | 35.00 % | 44.83 % |
| 101 | ||||||
| 102 | QN17 In your opinion there should be (multiple answers okay) | |||||
| 103 | There should be more frequent projects | 4 | 33.33 % | 1 | 5.00 % | 17.24 % |
| 104 | There should be less frequent projects | 2 | 16.67 % | 12 | 60.00 % | 48.28 % |
| 105 | The projects should be more challenging | 0 | 0.00 % | 4 | 20.00 % | 13.79 % |
| 106 | The projects should be way less challenging | 6 | 50.00 % | 1 | 5.00 % | 24.14 % |
| 107 | ||||||
| 108 | ||||||
| 109 | QN18 Your stress/anxiety level about this course relative to your other courses | |||||
| 110 | Very high | 4 | 44.44 % | 7 | 35.00 % | 37.93 % |
| 111 | Very low | 0 | 0.00 % | 2 | 10.00 % | 6.90 % |
| 112 | About the same | 4 | 44.44 % | 8 | 40.00 % | 41.38 % |
| 113 | ||||||
| 114 | QN 19 (only if you have taken an Intro to AI course before somewhere) | |||||
| 115 | I think this course is | |||||
| 116 | Pretty much similar to what I have done | 0 | 0.00 % | 2 | 10.00 % | 6.90 % |
| 117 | Much deeper than what I have done | 0 | 0.00 % | 5 | 25.00 % | 17.24 % |
| 118 | Much more of a cake-walk than what I have done | 1 | 11.11 % | 1 | 5.00 % | 6.90 % |
| 119 | ||||||
| 120 | QN 20: (Only if you are taking it as 471 -- i.e., UG Credit) | |||||
| 121 | Tick any that apply | |||||
| 122 | I think this course is geared too much towards graduate students | 2 | 22.22 % | 6.90 % | ||
| 123 | The demands of this course are grossly unreasonable for a 4-level course | 1 | 11.11 % | 3.45 % | ||
| 124 | Fine as it is, more or less. | 6 | 66.67 % | 20.69 % | ||
| 125 | ||||||
| 126 | QN 21 Will it help to have recitation sessions to discuss homework problems? | |||||
| 127 | Yes - I will attend | 2 | 22.22 % | 10 | 50.00 % | 41.38 % |
| 128 | Yes - I might attend | 4 | 44.44 % | 4 | 20.00 % | 27.59 % |
| 129 | Not really | 2 | 22.22 % | 3 | 15.00 % | 17.24 % |
| 130 | ||||||
| 131 | QN 22 If you are a 471 student รข€¦ | |||||
| 132 | I would like to get more help from the UG grader / tutor Kartik | 3 | 33.33 % | 10.34 % | ||
| 133 | I want Kartik to leave me alone | 0 | 0.00 % | 0.00 % | ||
| 134 | I am already getting enough help | 4 | 44.44 % | 13.79 % | ||
| 135 | ||||||
| 136 | ||||||
| 137 | If you have additional comment/feedback, either write below or send a mail | |||||
| 138 | using http://rakaposhi.eas.asu.edu/cgi-bin/mail?rao |
Subscribe to:
Posts (Atom)