Monday, December 17, 2007

(Important) Final Cumulatives (Everything included--sans letter grades)

Folks:

 I am done grading the final exam, and also assigning participation grades. Enclosed please find the final cumulatives for
both  the sections.


Participation grade is based on 1. three letter grades for attendance, attentiveness and blog participation and
2. conversion of those three to a single number between 0 and 10.

Note that I included two "grand totals"--one which includes everything except participation
and the other which also includes participation grade and scales everything down by a factor of 11/10
(since participation grade is more subjective than the other grades, I wanted to see how many people's
relative standings got significantly affected by the participation grade).

I will now ponder over these numbers and await super-natural enlightenment to dawn on me between now and
11:59pm when the grades are due.

I will tell you this much. The students at the top of the 471 and 598 lists will both get A+ grades.

***************Those two are also are invited to *suggest* grade cutoffs for both sections (as well as what should be the lowest grade awarded in
either of the sections). [I

Rao

Emacs!

Wednesday, December 12, 2007

Cumulatives (including everything except the final exam and class participation)--Please let us know if you see any errors

Folks
 Enclosed please find the cumulatives of as of now (including everything except the final exam and class participation). The last homework and project can be picked up from TA's desk.

Please check and let us know if you see any discrepancies in the recorded marks (note that in a couple of cases, the correct late penalty has not been factored-in yet--those are shown in red).

The current total includes 23 points for all homeworks together and 37 points for all projects together 20 points for the mid-term.

Note that the extra credit points in all categories are shown but are not factored into the totals as yet (as per my promise we do that only after the letter grade thresholds are determined).

Rao
---------------

Emacs!

Tuesday, December 11, 2007

Feh Java (just when you thought the blog is dead and gone...)

Huan Liu pointed me to this article ("rant") which I sort of see the point of...
at any rate, it is moderately funny (I think Structure and Interpretation of Programs
should be the only text to teach real programming with..)

http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

Rao

Friday, December 7, 2007

[cse 471] Grading scheme for project-4 (prolog theorem prover)

Hi,

Grading scheme for project-4 is as follows:

Total: 100 + 40 (extra credit)

Coding + Testing + Documentation:
Task1:   5
Task2:  20
Task3:  25

code  quality: 5

Domains: 15 pts (5+10)

Edited Trace - with analysis - and comments: 15 pts
Correct outputs for test cases: 10 pts
Other Analysis (observations): 5 pts

Extra Credit: 10 points for each of the 4 tasks

Let me know if you have any questions.

(Since  few of you used the late extension, I  will send the statistics once I am done with grading them.)

Good luck for the final take home exam.

Thanks,
Aravind

[cse 471] Grading scheme of homework-4 and statistics

Hi,

Here is the marking scheme for homework-4.

Total: 70 points

1. 29 (3+4+5+4+3+3+7)
2. 8
3. 10 (4+2+4)
4. 7 (4+3)
5. 4
6. 12 (2+1+2+5+2)

And the grade distribution is as follows:

UG: 41.33(Avg)  62(H)  40 (L)

Grad: 55.28(Avg)  70(H)  46(L)

Let me know if you have any questions.

Thanks,
Aravind

Thursday, December 6, 2007

Final exam released

Folks
 The final exam is available at http://rakaposhi.eas.asu.edu/cse471/f07-final-qq.pdf

Please print it single-sided and do all your work on the exam.

It is due back by Monday 5pm in hardcopy

Please monitor your email for any errata corrections.

Good luck

Rao
----------

(important) Information about the final..

Folks
 Here is information about the final. It will be released this afternoon (after 12noon). It mostly focuses on the material covered after the
midterm.The final will be due back by Monday 5pm in hard copy (there are exception clauses for people who may have too many other exams between now
and Monday--see the instructions on whether you qualify to *request* for extension).

I am in my office until noon today and you can come by to ask me any questions on the material.

Once the final is released, I will only answer clarification questions on the exam (and not general questions on topics covered--this is so that there is less
temptation to  just try to understand the material needed to do fine on the exam..)

rao

Wednesday, December 5, 2007

I am going to be available 4:30--6:30 as planned (for additional office hours)

just confirming--for what its worth.

rao

Today;s office hours--11:30--12:30

I will hold office hours today from 11:30 to 12:30.

I also intend to be around from 4:30--6:30 today. However, there is a small variable that might change my plans.
(I will let you know if I am unable to be around; you can also call 965-0113)

rao

Tuesday, December 4, 2007

Solutions to the last homework posted online

Solutions to the last homework are now online.

rao

Monday, December 3, 2007

A note on raw cumulatives etc.

Someone asked whether or not I plan to send another mail giving the current standings of students.

The answer is *yes*. We will send you one this week--that will take all graded work--including participation grade--
into account. We will again send the final totals next week after final has been graded. You will have plenty of time to
point out any inadvertent errors in the gradebook.

rao

Re: [Blog for Fall 2007 ASU CSE 471/598 Introduction to AI] Links from the last c...

Also, here is the full simpson's episode (almost full) from where the little song comes

  http://youtube.com/watch?v=k9_iQim8Mtw

May you be able to "outsource" everything (except, of course, the final for this class!)

Rao


On 12/4/07, Subbarao Kambhampati <subbarao2z2@gmail.com> wrote:
0. The ending utube video of Simpsons that didn't play in the class (it iseems to play fine on youtube)
              http://youtube.com/watch?v=uI1LtTtRV7s
     (for those who know hindi-- no, I am not attempting subliminal messages ;-)

1. Here is the link I promised on whether or not Deepblue has "intelligence"
  http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00043.html

2. Coverage of Russell's own course on intro to  AI for undergrads some place out further west:
    http://www.cs.berkeley.edu/~russell/classes/cs188/f05/
 (the syllabus followed is at http://www.cs.berkeley.edu/~russell/classes/cs188/f05/syllabus.html )

My philosophy is that *what* is taught in a course shouldn't depend on *where* it is taught. The demands and
coverage of the course should not be diluted based on anyone's reduced expectations of a student population
(since this is a vicious slippery slope and is ultimately detrimental to the students themselves). 

Your grade may well depend on who else took the course with you, but the material and demands should not.


3. On my aborted experiment with providing Java code:
   Here, FYI, is the Java version of the code for the first project we provided in 2003.

http://rakaposhi.eas.asu.edu/prj1-partial-code.java

No one who actually completed the project wound up using it. So, we discontinued the practice after one other project.

regards
Rao








--
Posted By Subbarao Kambhampati to Blog for Fall 2007 ASU CSE 471/598 Introduction to AI at 12/03/2007 11:15:00 PM

Links from the last class

0. The ending utube video of Simpsons that didn't play in the class (it iseems to play fine on youtube)
              http://youtube.com/watch?v=uI1LtTtRV7s
     (for those who know hindi-- no, I am not attempting subliminal messages ;-)

1. Here is the link I promised on whether or not Deepblue has "intelligence"
  http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00043.html

2. Coverage of Russell's own course on intro to  AI for undergrads some place out further west:
    http://www.cs.berkeley.edu/~russell/classes/cs188/f05/
 (the syllabus followed is at http://www.cs.berkeley.edu/~russell/classes/cs188/f05/syllabus.html )

My philosophy is that *what* is taught in a course shouldn't depend on *where* it is taught. The demands and
coverage of the course should not be diluted based on anyone's reduced expectations of a student population
(since this is a vicious slippery slope and is ultimately detrimental to the students themselves). 

Your grade may well depend on who else took the course with you, but the material and demands should not.


3. On my aborted experiment with providing Java code:
   Here, FYI, is the Java version of the code for the first project we provided in 2003.

http://rakaposhi.eas.asu.edu/prj1-partial-code.java

No one who actually completed the project wound up using it. So, we discontinued the practice after one other project.

regards
Rao






Last thinking cap: Opportunity to do your interactive review on the blog

Folks
For those of you who didn't get a chance to do the interactive review in class due to time running out, my apologies.
Please feel free to add your tuppence as comments to this blog thread (and I promise to respond to them as needed--just as I did in the class).
To kick it off, here is the summary of the part of the review that did get said in class--according to Kartik:
-------------------
                                                                    


CSE471 Interactive Review

Transcription

Randy Compton

- Bayes Nets
- The tool
- Connections between search and theorem proving interesting

Nishant Singh

- MDPs should be covered more
- They are practical
- WHY DO WE HAVE TO USE LISP?
- Rao: People who are bad at programming are bad at every *kind* of programming
- Lisp does not push users into one paradigm; logic, functional etc. everything are used

Ryan Braley

- Too much focus on optimality

Tuan Nguyen

- Factored representation vs. Black box
- Internal state representation makes a difference!
- Rao: we mostly went from black boxes to factored representations; except for when we considered MDPs, because MDPs consider states as black boxes.

Ravi Gummadi

- Heuristics
- Discussion was very limited
- Rao: Beyond a certain level, discussion on heuristics is problem-dependent

Jeff Plummer

- Class should be divided into 2 sections
- Requires a lot of learning
- Practical applications;
- for e.g, how do MDPs fit into real-world
- Rao: We fall in the middle of the distribution of courses on AI; we do about 2/3rds of Russell's course at UCB

Matt Bisgard

- Differences in perception between what human mind can do vs. what computers can
- Rao: self-serving descriptions of whatever we do
- Rao: Go is hard for machines vs. chess being easy; but its not clear that Go is somehow more human than chess
- Rao: Drew McDermott's article on Deep Blue; Marvin Minsky's quote "With understanding comes a sense of loss"
- Rao: This entire course was ambivalent about humans, but we need to come back to humans once

Kyle Luce

- Randomization leading to better results
- Random restart hill climbing search
- Rao: works because there are many solutions

Gavin Lewis

- Bayes' Theorem
- Writing real-life situations is much harder than it seems
- Links between cognitive psychology and AI
- Lot less overlap between what AI seems to be (after this class) and the perception of AI
- Rao: Many of the concepts covered present in mathematics way before AI

Anupam Khulbe

- Connections between research techniques and planning
- More discussion on planning would have been nice

Richard Sealy

- Algorithmic optimality: For search through states etc
- Rao: Problem is most of the algorithms used are NP-Complete
- Rao: AI doesn't pay as much attention to system-building and optimization

Ina Sen

- New-found respect for 2^n

Sushma Dittakavi

- Classifiers, Learning

Juraj

- Enjoyed homeworks
- Did NOT enjoy projects that required Lisp

- ON LISP
---------------------------
   

Wednesday, November 28, 2007

An optional question on learning has been added to homework 5

An optional question on learning has been added to homework 5. It is *Optional*--ie.,
you don't have to do that. Although you won't forgive yourself for not doing it if you are
seinfeld fan.
 
rao
 

*Important* Headsup: Interactive review in the next class

Folks:
 
 Please note that rather than me doing a dry summary of the course, I prefer to have the students do an interactive summary of the course--in terms of what they got.
Me saying that such and such a topic is beautiful is not as effective as one of your peers saying it (as you are likely to then go back and pick it up if you didn't the first time).
 
Each of you will get about 2min to hold forth on any of the following: 
 
 -->topics covered in the course that particularly caught your fancy (and  why) 
 
  --> intriguing connections *between* the various topics covered in the course that struck you
 
  --> what topics--if any--got overplayed or should have gotten more  coverage

You should come to the class prepared with a sheet that answers these questions--that you will turn in at the end of the class (in addition to sharing them verbally in the class).
 
 
Please note that this is a *review* session--not an course/instructor evaluation session. For the latter, you have the college evaluations (that you are highly encouraged to take part in).
 
Please also note that depending on how effective I am about keeping people to their two minutes, we may go over time. (Note that strictly speaking, the allotted final exam time is also considered part of the contact hours--so you can think of the extra time you spend next Monday as just a way of buying yourselves out of the 2 hours
of contact time the following monday).
 
 
 
Rao
 
 
 
 

heads up: you will be asked to fill an participation evaluation sheet next class

Folks:
 
 As you may recall,  10% of the grade for the course is based on participation which is measured in terms of attendance and 
attentiveness.  In order to give that part of your
grade, I will be asking all students to fill up a participation form that will have the folowing questions. Please have your
data ready so you can give accurate answers to the following (*Don't reply now--you will fill hard-copy forms in the class*)
 
Attendance: How many classes did you miss:__________  (exact number preferred--see http://rakaposhi.eas.asu.edu/cse471
  to see what was done on what days so you can recollect which classes you missed)
 
 How many of these cases did you notify the instructor prior to the absence:_______________
 
Attentiveness: How many classes did you ask meaningfu questions:___________________
 
Blog participation: How many times did you post meaningful responses to the thinking cap questions:_____________
 
If you take the 5th and not give answers, I will have to go by my recollections and samples. But note that my estimates of class abseences tend to be
inaccurate--if you miss a couple I might think you mised half-a-dozen, and if you slept in the class once, I assume you never paid any attention ;-)
 
 
cheers
Rao
 

Tuesday, November 27, 2007

For the Undergraduate students: Fulton Undergradute Research Initiative deadline...

I have been asked to relay this information to the UG students.

-------
Amy Sever says:

Applications for Spring 2008 FURI program due on November 30th (this Friday) – see here for more info: http://www. fulton.asu.edu/fulton/departments/furi/.  Please encourage your undergraduate students to participate.

----------

Monday, November 26, 2007

[Thinking Cap] on learning.. (May be the last or penultimate chance to don that cap) [4th qn added]

Qn 4. added below.


Qn 0. [George Costanza qn] Consider two learners that are trying to solve the same classification problem with two classes (+  and -). L1 seems to be averaging about 50% accuracy on the test cases while L2 seems to be averaging 25% accuracy. Which learner is good?  Why is this called the George Costanza question? ;-)
 
 
Qn 1. Consider a scenario where the training set examples have been labeled by a slightly drunk teacher--and thus they sometimes have wrong labels (e.g. +ve are wrongly labelled negative etc.).  Of course, for the learning to be doable, the percentage of these mislabelled instances should be quite small.  We have two learners, L1 and L2. L1 seems to be 100% correct on the *training* examples. L2 seems to be 90% correct on the training examples. Which learner is likely to do well on test cases?
 
Qn 2.  Compression involves using the pattern in the data to reduce the storage requirements of the data.  One way of doing this would be to find the rule underlying the data, and keep the rule and throw the data out. Viewed this way, compression and learning seem one and the same. After all, learning too seems to take the training examples, find a hypothesis ("pattern"/"rule") consistent with the examples, and use that hypothesis instead of the training examples.  What, if any, differences do you see between Compression and Learning?
 
Qn 3. We said that most human learning happens in the context of prior knowledge. Can we view prior knowledge as a form of bias?
In particular, can you say that our prior knowledge helps us focus on certain hypotheses as against other ones in explaining the data?
 
 
Qn 4.  We test the effectiveness of a learner on the test cases. Obviously, the test can be made "unfair" in that the test examples are somehow unconnected with training examples. 
 
One way of ensuring fairness, the the learner would love, is to pick a subset of training examples and give them back as test examples. (This is like your good old grade school days where the teacher would give "review" sheet and the exam
will ask a subset of questions from the review sheet). Obviously, this makes the test a litle too dull (from the sadistic teacher's point of view). 
 
A way of ensuring fairness that the teacher would love is to actually give test cases that have not been seen in the training cases (e.g. set exams that don't just repeat homework questions). However, it is too easy to get into unfair tests this way.
 
***What is the most general restriction you can put on the test so that it is considered "FAIR"? Can you argue that your definition works well with your gut feelign about "fair" vs. "unfair" exams/tests?
 
 (Anecdote on "unfair tests":  When my wife took a class on algorithms and complexity in her UofMD days, the teacher--who I won't name--spent one class at the end of the semester on NP-completeness proofs, and set the entire final exam on NP-completeness proofs. She never realized how riled up she was about this until she met another student from the same class, who is a faculty member at Duke at a DARPA meeting 15 years later--and found themselves talking about the sheer unfairness of the test in the first couple of seconds. Apparently we remember unfair tests quite well ;-).
 
that is all for now.
Rao
 

Required reading for 11/28: Sec 18.3 and Sec 20.5


Homework 5 first four problems due on Dec 3rd in class

I added a game tree problem and one morealpha-beta pruning problem. These four are due on Dec 3rd.
 
I will add a couple of problems on learning but these will not have to be submitted.
 
All the answers for the homework will be provided by Dec 3rd evening.
 
Rao
 

Bias, generalization and stereotypes: A half-baked lesson in Ethics

[[extra-curricular]]

[ACM suggests that some percentage of Undergraduate CS courses should be spent on discussing
ethics. May be this will fill that role... At any rate, I have been sending it since Fall 2003, and I see no reason
to break the tradition this year ;-) ]


Inductive generalizations are what allow the
organisms with their limited minds to cope with the staggering complexity
of the real world. Faced with novel situations, our ancestors had to
make rapid "fight or flight" decisions, and they had to do biased
learning to get anywhere close to survival. So, we can't really
seriously ask people not to generalize or not to have biases!

The problem of course is where does this leave us vis-a-vis
stereotypes--the "all Antarciticans are untrustworthy", "all
Krakatoans are smelly" variety. Afterall, they too are instances of
our mind's highly useful ability to induce patterns from limited
samples.

So, what, if any, is the best computational argument against stereotyping? One
normal argument is that the stereotype may actually be wrong--in
otherwords, they are actually wrong (non-PAC) generalizations, either
because they are based on selective (non-representative) samples, or
because the learner intentionally chose to ignore training samples
disagreeing with its hypothesis. True, some
stereotypes--e.g. "women
can't do math", "men can't cook" variety--are of this form.

However, this argument alone will not suffice, as it leaves open the
possibility that it is okay to stereotype if the stereotype is
correct. (By correct, we must, of course, mean "probably approximately
correct," since there are few instances where you get metaphysical
certainty of generalization.)

What exactly could be wrong in distrusting a specific Antarcitican because
you have come across a large sample of untrustworthy Antarciticans?

I think one way to see it is perhaps in terms of "cost-based
learning". In these types of scenarios, you, the learning agent, have
a high cost on false negatives--if you missed identifying an
untrustworthy person, or a person who is likely to mug you on a dimly
lit street, or a person who is very likely to be a "bad" employee in
your organization, your success/survival chances slim down.
 
At the same time, the agent has much less cost on false positives, despite
the fact that the person who is classifed falsely positive by your
(negative) stereotype suffers a very large cost. Since the false
positive *is* a member of the society, the society incurs a cost for
your false positives, and we have the classic case of individual good
clashing with societal good.

This then is the reason civil societies must go the extra mile to
discourage acting on negative stereotypes, so we do not round up all
antarciticans and put them in bootcamps, or stop all Krakatoans at
airport securities and douse them with Chanel 5. And societies, the
good ones, by and large do, or at least try to do. The golden rule,
the "let a thousand guilty go free than imprison one innocent", and
the general societal strictures about negative streotypes--are all

measures towards this.

You need good societal laws (economists call these "Mechanism Design")
 precisely when the individual good/instinct clashes with the societal good.

So, you are forced to learn to sometimes avoid acting on the highly
efficient, probably PAC, generalizations that your highly evolved
brain makes. I think.


Yours illuminatingly... ;-)
Rao

Epilogue/can skip:

It was a spring night in College Park, Maryland sometime in
1988. Terrapins were doing fine.  The Len Bias incident was slowly
getting forgotten.  It was life as usual at UMD. About the only big
(if a week-old) news was that of a non-caucasian guy assaulting a
couple of women students in parking lots.  I was a graduate student,
and on this particular night I did my obligatory late-evening visit to
my lab to feign some quality work. My lab is towards the edge of the campus;
just a couple more buildings down the Paint Branch Drive, and you get
to the poorly lit open-air parking lots.

On that night I parked my car, walked down the couple of blocks to my
lab, only to remember that I left a book in the car. So, I turned, and
started walking back to the parking lot. As I was walking, I noticed
that this woman walking in front turned a couple of times to look back at me. I remembered
that I had passed her by in the opposite direction. Presently I
noticed her turning into the cryogenics building, presumably her
lab. As I passed by the cryo lab, however, I saw the woman standing
behind the glass doors of the lab and looking at me.


Somewhere after I took a few more steps it hit me with lightning
force--I was a false positive! The woman was  ducking into
the lab to avoid the possibility that I might be the non-caucasian
male reportedly assaulting campus women. I knew, at a rational level,
that what she was exhibiting is a reasonably rational survival
instinct. But it did precious little to assuage the shock and
diminution I felt (as evidenced by the fact that I still remember the
incident freshly, after these many years.).
 
There is no substitute for assessing the cost of false positives than being a false positive
yourself sometime in your life...

--------------
     ....not to make up your minds, but to open them.

    To make the agony of decision-making so intense that 
    you can escape only by thinking. 
                        -Tag line from Columbia School of Journalism Seminars

   "Induction  extends your expectation, not your experience"
 

Project 4 late submission requests..

Folks
 
 Several of you sent mails this morning (or asked me after the class today) for extensions on project 4.
Given that many students did submit the project already, here is the policy we will follow:
 
1. If you have extension days left for either the project or the homework, you can use them (Note that the last
homework is due on next monday, and it can't be extended. So, if you have a homework extension day left
you can use it for the project. Just state that).
 
2. If you don't have any extension days left, then recall that I did encourage everyone to use the time between 11/26 and
12/3 to complete any projects that they have not submitted--so they can get partial (rather than zero) credit. This offer
extends also to the current project.
 
 
regards
Rao
 

Sunday, November 25, 2007

[cse 471] Instructions for project-4 submission

Hi,
 
I have opened a link in blackboard for submitting your LISP code for proj-4.
 
Few questions in the project require you to submit traces of the working code on certain domains. You should include them in the project report (hard-copy). Only a *short* and edited trace showing the important steps is needed. (do not submit the full trace).
 
Thanks,
Aravind

Wednesday, November 21, 2007

Information regarding CSE574 being offered next semester..

Some people asked for information on CSE 574, and I thought the information may be of wider interest since
the course hasn't been offered since before Bush's re-election.

The course home page from the last offering is at http://rakaposhi.eas.asu.edu/cse574 
and will give a reasonable idea of what we might do.

If you liked the material  on planning, CSP and markov decision processes in CSE 471
then you will likely like 574.

It is going to be run as a "Real" (TM) graduate course (read "real easy") but I am happy to have qualified undergraduate students register for the class (you will need to fill a special form from the department and have it signed by me).

You may have to register real quick though; now that I managed to get the word out through the  State Press  that I teach real easy courses, I expect this course to fill up real fast with real honors students (http://www.statepress.com/issues/2007/11/21/opinions )

Happy thanksgiving!
Rao


ps: The course might experiment with a novel grading scheme where grades depend directly on how many papers the student can publish in  top venues  (with significant bonuses involved in listing the instructor as a co-author ;-).





Monday, November 19, 2007

[Thinking Cap] MDPs etc...

Consider the following:
 
0. Consider the  MDP applet demo we saw in the class today. The default discount factor was set to 0.9, and the reward states were made "absorbing". What do you think will happen if you make the discount factor to be 1.  Confirm your intuition with the applet. Now, do this part again but without any absorbing states. Again, try to guess what will happen, and confirm your intuition.

1. What happens to MDPs if the underlying dynamics are "deterministic"? Can we still talk about value and policy iteration? Do we still have non-stationary policies for finite horizon deterministic MDPs?
 
 
2. We talked about how infinite horizon case is easier than finite horizon case, and said, in passing, that here is one case where "infinite" is easier to handle. Consider the following two cases:
 
2.1. CSPs where the variables are "real valued", and constraints between variables are expressed as linear inequalities. Clearly, the number of potential assignments for the CSP variables is infinite. What do you think will be the complexity of finding a satisfying assignment of the variables? (recall that discrete variable CSP is NP-complete) If the complexity is "low" by AI standards, what can you do to increase it? (hint: consider modifying constraints).

2.2. Planning problem where (some of) the variables are real valued. Actions have effects that can increment and decrement the variables by arbitrary amounts. What do you think will be the complexity of planning in this case? (recall that discrete variable planning is PSPACE-complete, i.e., it is among the hardest problems that can be solved with polynomial space).


3. The MDPs we considered until now are called "Fully observable"--in that during execution, the agent can tell which state it is in (thus the policy needs to only map states to actions).  What happens if the domain is only "partially observable".
Note that this means that the agent may not know which unique state it is in, but knows the  "probability distribution" over the possible states it could be in. When the agent does an action, it effect of the action is to modify the distribution into a new distribution over states (with some states being more likely and others less.

Notice that the "distribution" is fully observable although the underlying states aren't.
So, one idea will be to consider the distributions as the states. What happens to the complexity of MDPs? How is this connected to MDPs over "continuous" state spaces?

[Notice that the above still works for the special case fully observable domain. The initial distribution will be a delta function--with probablity being 1.0 for a single state, and 0.0 for all others. Doing an action converts into another delta function--with the 1.0 for a different state].

That is all for now...


Rao


[cse471] Proj-3 (Bayes Nets) grading scheme and distribution

Hi,
 
Following is the grading scheme for proj-3 (Inference using Bayes nets):
 
Total: 42 + 6 (extra credit)
 
Part I:
1. 1 (bayes net picture) + 1 (.bn file) + 1 (monitored probability values)
2. 5 (1 for each probabiltiy value) + 3 (comments)
 
Part II:
1. 2 (.bn file)
2. 5 (propositional logic statements)
3. 3 (prob. values asked)
4. 2 (comments)
 
Part III:
1. 2 (bayes net figure) + 2 (.bn file) + 5 (1 for each probability value) + 2 (comments)
 
Part IV:
1. 1 (bayes net figure) + 2 (.bn file) + 2 (bayes net figure) + 3 (.bn file)
 
Extra Credit: 2 (Qn A) + 4 (Qn B)
 
 
Grade Distribution:
 
UG:
36.6(Avg)  42(H) 26(L)
 
Grad:
36.3(Avg) 42(H) 21(L)
 
 
Please let me know if you have any questions.
 
Thanks,
Aravind
 
 

Sunday, November 18, 2007

(Thinking cap) Complexity of planning

 We saw that Planning can be modeled as a search problem--where the state involves
state variables, and actions are "STRIPS" actions with preconditions and effects.
 
We had also seen that CSP too can be posed as a search problem, but unlike normal search problems,
which can have *any* complexity (recall that theorem proving can be cast as a search--and it is only semi-decidable),
CSP is *only* NP-complete.
 

What is the complexity of action planning? Is it NP-complete? More?
 
Before answering this, consider the tower of hanoi problem. Can you write the legal moves for
the tower of hanoi problem as STRIPS actions? If you can, what does it tell you about the complexity of planning?
 
 
Consider the "Bounded-length planning" problem, which takes a planning problem and a length bound "b" and attempts to find if there is a plan of length "b" or less that can solve the problem. How might the complexity of bounded length planning be related to the complexity of  normal STRIPS planning?
 
 

Solutions to Homework 4 posted..


Thursday, November 15, 2007

Thinking Cap questions (comment on the blog)



Here are some thinking cap questions.

(1) Underlying much of the discussion on MDP is a fundamental principle about decision making under uncertainty--that a rational decision maker does the action that maximises the  *expected* utility. For example, if you have two actions, A1, which gets you to S1 with 0.9 prob, and S2 with 0.1 prob, and A2 which gets you to S2 with 0.2 prob and S3 with 0.8 prob, and the utilities of the states are S1=10 S2=100 S3=-20.
Then the expected utility of doing action A1 is .9*10+0.1*100=19;  and that of doing A2 is 0.2*100+.8*-20= 20-16=4. So, a rational agent must pick A1 over A2.

Consider a typical lottery. You buy a ticket for 1$, and you get a 1 in ten million chance of winning 1million. You have  two possible actions: Buy the ticket or Not buy the ticket. Expected return of buying the ticket seems to be a loss of 90 cents while expected return of not buying the ticket is 0.

Despite this, we know that lotteries are flourishing everywhere. Does the success of lotteries show that the underlying assumption of decision theory is irrevocably flawed in accounting for what humans do? Or is there a decision-theoretic explanation for why some humans seem to go for lotteries?



(2) In today's class we agreed that the "optimal policy" is simply a mapping from states to actions. However, if two people, one 20 years old and another 60 years old, but otherwise completely identical in their financial situation, go to a financial advisor, the advisor will give differing advice to the 20yr and the 60yr one (typically, for the 20 year old, it will be to invest all in stocks and for the 60 yr one, it will be to invest in bonds or even put it under the pillow).
To the extent MDPs can be thought of as a model of our everyday decision making, how can you explain this difference between policies for two agents that seem to be identical in all respects?



(3) When we come into this world, we probably don't have a  very good model of the world (a kid, for example, doesn't quite know what the outcomes of many different actions are. So, the kid will eagerly try putting their hand on the red glowing thing--even if the glowing thing in question happens to be the cooking range. So, presumably we learn the model. How about the "reward" model? Is the reward model also completely learned from scratch?

Comments, on the blog, welcome.

cheers
Rao


     

Wednesday, November 14, 2007

Project-2 grading scheme and statistics

Hi,
 
Following is the grading scheme for project-2 (Sudoku using CSP):
 
part I: Implementation:  (45 pts)
 
(a) Diagonal constraint -  10
(b) MRV - 12
(c) LCV  -  12
(d) FC    -  11
 
Code quality(like comments, efficiency) : 5
 
Part II:
 
Results and Presentation: (20 pts)
[computing the required statistics for given test cases]
a  2
b  4
c  4
d  3
e  4
f   3
 
Analysis (30 pts)
* Observations on individual heuristics, their performance and trends for various test cases :  10 pts
* Comparison between the heuristics :  10 pts
* Other non-trivial observations, exceptions, and improvements suggested : 10 pts
 
Extra Credit:  30 pts
 
Comments::
1. Unlike project-1, some of you did not provide any comments on their code or implementation details. It would definitely help me to check them to see what are your assumptions. (especially when the computed statistics don't match with the expected ones).
2. Some students had mentioned that your program ran out of memory for some test cases, which is actually not the case. (and the test run completes in a decent amount of time.)
---------
 
Grade Statistics:
 
UG:    Avg (85.2)  Highest(94)  Highest{with extra credit} (91 + 22)  Least: 60
 
Grad: Avg (80.8)  Highest(99 + 26)   Least: 57
 
Let me know if you have any questions.
 
Thanks,
Aravind
 
 
 
 
 

Monday, November 12, 2007

A blind carbon copy

This is a blind carbon copy.

Project 4 due date set 11/26 (and opportunity to finish earlier incomplete projects)

Folks:

   I have set the project 4 due date to 11/26.  Given that we have just one week of classes left after that,
we will not have time for project 5 (I know--it is very disappointing).

 I will likely include some mini-project like things into the last homework.

 Those of you who have failed complete any of the earlier projects are highly encouraged to use the time to complete them
and turn them in by 3rd December (end of the semester).


Rao

Reading for the next class..

The readings for the next class(es) are:

Sequential Decision Making & Markov Decision Processes (17.1--17.3)

followed by

Adversarial Search  (6.1--6.4)


You will be best served if you have read the material before showing up.

rao

Saturday, November 10, 2007

Video recording of the makeup class is on google videos

For the benefit of those people who couldn't make it to the make-up class because of prior commitments
(and were nice enough to respond to my mail and let me know that they can't make it)
we recorded yesterday's class and uploaded it onto Google Videos. Here is the link

http://video.google.com/videoplay?docid=-912129121787012966

With the video and a copy of the ppt slides, you get the full picture of the class


cheers
Rao



Friday, November 9, 2007

Makeup class lecture and audio up on web + Homework 5 socket opened with a planning question

Folks
 The slides and audio from today's class are online. I also opened Homework 5 socket and put in a multi-part question on planning
domains and heuristics.

We also made a video recording of the class but it is 728mb. I am trying to post it on google video. If I succeed, I will send you a link.

Rao

Wednesday, November 7, 2007

Please reply to this message if you don't expect to be able to attend Friday's makeup class

Folks
 For planning purposes, I am trying to figure out who will *not* be able to attend Friday's makeup class (10:40--11:55 in the same room).

If you can't attend, please let me know by replying to this message.

regards
Rao

Tuesday, November 6, 2007

A talk on "future of AI" (resending with a more informative subject)



---------- Forwarded message ----------
From: Subbarao Kambhampati <rao@asu.edu>
Date: Nov 6, 2007 6:17 AM
Subject: Fwd: Link to the slides and audio
To: Rao Kambhampati <rao@asu.edu>

Folks:

 Last Friday, I got a chance to pontificate on the "Future of AI" at the eponymous Univesity of Washington  seminar
(http://www.cs.washington.edu/education/courses/590a/07au/ )

The title of my talk was "Human-Aware AI (Darned Humans--Can't live with them, Can't live Without them)"

In case you are interested, the slides and audio for the talk are available at the following links:


http://rakaposhi.eas.asu.edu/uw-haai-talk.ppt 

http://rakaposhi.eas.asu.edu/rao-uw-talk.WAV

cheers
Rao

Fwd: Link to the slides and audio

Folks:

 Last Friday, I got a chance to pontificate on the "Future of AI" at the eponymous Univesity of Washington  seminar
(http://www.cs.washington.edu/education/courses/590a/07au/ )

The title of my talk was "Human-Aware AI (Darned Humans--Can't live with them, Can't live Without them)"

In case you are interested, the slides and audio for the talk are available at the following links:


http://rakaposhi.eas.asu.edu/uw-haai-talk.ppt 

http://rakaposhi.eas.asu.edu/rao-uw-talk.WAV

cheers
Rao

Sunday, November 4, 2007

Re: Regarding Project 3

Hi all,
 
Since there is no source code involved in this project, you should just turn in the hardcopy of your report in the class.  ASU-Blackboard submission is not required. Include all the .bn files in the report itself. 
 
Thanks,
Aravind

 
On 11/4/07, Nishant Singh <Nishant.Singh@asu.edu> wrote:
Hi
 
Can u plz post the guidelines of submission of project 3
like do we have to submit the .bn of all the parts on my ASU or print out of it to prof Rao

thanks
 
with regards
Nishant Singh

Thursday, November 1, 2007

State-of-the-art in solving crosswords using AI techniques..

After the CSP question on the exam, you might be interested in getting an idea of the state of the art on
using AI techniques to solve cross word puzzles. If you are, check out the following page:

http://www.oneacross.com/proverb/

The 6+ page conference paper

http://www.oneacross.com/proverb/papers/keim99proverb.pdf

is a great read and shows how they set it up as a probabilistic constraint satisfaction problem (using web to
get the words ;-)

Rao

Midterm solutions are available..

Midterm solutions are available at
 
http://rakaposhi.eas.asu.edu/cse471/f07-midterm-sols-kq.pdf


FYI
Rao

Wednesday, October 31, 2007

Project 4 available for *preview*

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

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:

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.

======================================

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

Emacs!

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





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


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..


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

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


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 ;-)


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


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

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

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)
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).
 
 
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

(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

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

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

Homework 3 socket opened--4 questions on propositional logic added


Solutions to homework 2 posted on the homepage..


[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

[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

*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

 

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          
Please Circle the appropriate choice for each questions          
           
ABOUT YOU          
Qn0  I am taking the course as          
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