Blog for Fall 2007 ASU CSE 471/598 Introduction to AI

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

2007-12-17T11:17:00.000-08:00

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

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

2007-12-12T11:07:00.000-08:00

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

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

2007-12-11T16:55:00.001-08:00

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

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

2007-12-07T02:42:00.001-08:00

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

2007-12-07T02:25:00.000-08:00

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

Final exam released

2007-12-06T10:27:00.001-08:00

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

2007-12-06T09:15:00.001-08:00

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

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

2007-12-05T15:10:00.001-08:00

just confirming--for what its worth.

rao

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

2007-12-05T10:11:00.000-08:00

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

Solutions to the last homework posted online

2007-12-04T19:53:00.000-08:00

Solutions to the last homework are now online.

rao

A note on raw cumulatives etc.

2007-12-03T23:30:00.001-08:00

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

2007-12-03T23:26:00.000-08:00

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

2007-12-03T23:15:00.000-08:00

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

2007-12-03T13:03:00.001-08:00

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

---------------------------

An optional question on learning has been added to homework 5

2007-11-28T16:27:00.000-08:00

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

2007-11-28T13:40:00.001-08:00

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

2007-11-28T13:26:00.000-08:00

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

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

2007-11-27T09:33:00.000-08:00

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

-------
Amy Sever says:

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

----------

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

2007-11-26T16:55:00.000-08:00

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

2007-11-26T14:29:00.000-08:00

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

2007-11-26T13:10:00.000-08:00

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

2007-11-26T12:52:00.001-08:00

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

2007-11-26T12:35:00.001-08:00

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

[cse 471] Instructions for project-4 submission

2007-11-25T02:04:00.001-08:00

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

Information regarding CSE574 being offered next semester..

2007-11-21T18:49:00.001-08:00

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

[Thinking Cap] MDPs etc...

2007-11-19T20:19:00.001-08:00

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

2007-11-19T10:38:00.001-08:00

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

(Thinking cap) Complexity of planning

2007-11-18T13:33:00.001-08:00

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

2007-11-18T06:23:00.001-08:00

Thinking Cap questions (comment on the blog)

2007-11-15T06:18:00.001-08:00

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

Project-2 grading scheme and statistics

2007-11-14T09:58:00.001-08:00

Hi,

Following is the grading scheme for project-2 (Sudoku using CSP):

part I: Implementation: (45 pts)

(a) Diagonal constraint - 10

(b) MRV - 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

A blind carbon copy

2007-11-12T18:55:00.001-08:00

This is a blind carbon copy.

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

2007-11-12T06:25:00.001-08:00

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

2007-11-12T06:18:00.001-08:00

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

Video recording of the makeup class is on google videos

2007-11-10T05:22:00.001-08:00

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

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

2007-11-09T20:45:00.001-08:00

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

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

2007-11-07T12:09:00.001-08:00

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

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

2007-11-06T05:19:00.000-08:00

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

2007-11-06T05:17:00.001-08:00

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

Re: Regarding Project 3

2007-11-04T16:27:00.001-08:00

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

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

2007-11-01T07:05:00.001-07:00

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

2007-11-01T06:26:00.000-07:00

Midterm solutions are available at

http://rakaposhi.eas.asu.edu/cse471/f07-midterm-sols-kq.pdf

FYI
Rao

Project 4 available for preview

2007-10-31T20:57:00.001-07:00

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)

2007-10-31T20:08:00.001-07:00

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

2007-10-31T18:57:00.001-07:00

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)

2007-10-31T15:32:00.000-07:00

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

Midterm grades statistics..

2007-10-30T20:10:00.001-07:00

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

Required reading for Wednesday

2007-10-29T20:44:00.001-07:00

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

Project 2 submission date/late submission etc..

2007-10-26T11:14:00.000-07:00

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]

Entailment status and learning

2007-10-23T20:56:00.001-07:00

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

(optional) Review session for midterm-- starts 4pm in BY 576 on Tuesday

2007-10-22T20:19:00.001-07:00

As per the popular demand, I will hold a "review" session starting 4pm in BY 576 (in the same corridor as my office)

rao

Reminder: Important--required reading for Monday's class

2007-10-21T16:09:00.000-07:00

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

2007-10-21T12:25:00.000-07:00

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

2007-10-21T12:09:00.001-07:00

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

2007-10-21T10:38:00.001-07:00

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

2007-10-21T08:51:00.001-07:00

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

[cse 471] Instructions for submitting project-2

2007-10-20T14:30:00.000-07:00

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

Important--required reading for Monday's class pp 504--515 in the text book

2007-10-17T16:42:00.001-07:00

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

2007-10-17T16:31:00.001-07:00

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

2007-10-17T14:57:00.001-07:00

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)

Part A: 4 (2+2)

Part B: 4

Part C: 8

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

A.2 2

A.3 3

A.4 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]

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)

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

[Thinking cap questions on bayes networks]

2007-10-15T15:18:00.001-07:00

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

-------------

Homework 3 socket closed; Due 10/17

2007-10-11T20:18:00.000-07:00

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

2007-10-11T20:10:00.001-07:00

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

2007-10-11T14:41:00.000-07:00

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

[cse 471] Recitation Session for Project-2 (tomorrow 3-4 PM)

2007-10-10T14:03:00.000-07:00

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

A specimen midterm exam

2007-10-08T20:05:00.001-07:00

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

2007-10-08T20:01:00.001-07:00

Solutions to homework 2 posted on the homepage..

2007-10-08T19:35:00.001-07:00

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

2007-10-08T14:42:00.001-07:00

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

2007-10-08T11:59:00.000-07:00

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

Project 2 assigned; description of what you need to do is online now. Due Oct 22nd.

2007-10-03T15:03:00.000-07:00

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

2007-10-03T13:16:00.001-07:00

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

Results of class survey

2007-10-01T16:23:00.001-07:00

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

Extension on homework 2: Due now on Wednesday Oct 3rd

2007-09-30T07:17:00.001-07:00

Folks

Since I have been away on last Monday and didn't hold office hours,
I will extend the deadline for hw2 submission to Wednesday's class.

This will give time for people who had questions on homework 2 and couldn't
get me during office hours

(I realize I am grasping at the straws here, considering how student-less and maytag-repairman-like my
office hours are even at the best of circumstances.. nevertheless..)

Rao

there is no typo/erro in the pattern database question..

2007-09-30T07:12:00.001-07:00

Gavin's comments notwithstanding, there are no typos in the pattern database
question. You should do it the way it is given

(by the way, it is fine for h*(n) to be \infinity. You can still talk about admissiblity and
relative informedness of h1(n) and h2(n) ).

rao

[cse 471] Instructions for your project report --plus-- Announcements on submission

2007-09-20T18:19:00.001-07:00

Hello all,

I hope everybody is doing great with project-1! I have opened a link for it under the "Assignments" section in blackboard for submitting your code part of this project. Please submit only your "CODE" (name the files as firstname_lastname.lisp) there.

You have to submit a hardcopy of your project report in the class next wednesday. The report should contain your code, sample runs for input cases, statistics collected (as required in the project tasks) and your analysis on the results etc. Please note that the purpose of the project (and a report) is not to test your LISP/programming skills, but to make you understand, analyze and explore the various methods you study in the course. So, your report is expected to contain good *analysis* and *observations*, and not just the code with outputs.

Here are some general suggestions for preparing your report:

1. Write the report clearly so that I can find out what you did for each task. A brief description of your implementation would be appreciated.

2. Give the output of some sample test calls to show that you code has no bugs.

3. Given the output, do some thorough analysis. A comparison of various methods used, the effects of varying parameters (if any) on the experimental results etc would be necessary.

4. You can plot some figures to show the difference of different methods, to check whether it is consistent with the theoretical result (like the time complexity, space complexity, order of increase etc.) What are the conclusions? Does it make sense and why?

5. Did you encounter any problem during the project? Any unexpected results? Are there possible ways you tried or suggest to get better solutions?

Please let me know if you have any questions.

Thanks,

Aravind

The solutions to homework 1 are posted on the homepage (see the homeworks page)

2007-09-19T15:57:00.001-07:00

Homework 2--CSP and Pattern database questions added and socket closed. Due date: October 1st.

2007-09-19T15:18:00.000-07:00

[cse 471] grading scheme for homework-1

2007-09-19T13:45:00.001-07:00

Hello all,

Grade distribution for homework-1:

Grad:	43.5	(mean)	50 (H)	36 (L)

UG:	43.8	(mean)	50 (H)	29 (L)

And, the grading scheme is as follows: (total is for 50 points + 5 e.c)

1. 8

2. 2+2+2

3. 4

4. 5

5.i 1

5.ii 1

5.iii 2 + 2

5.2 (1+1+2+2) = 6

6. 5

7.1 2

7.2

7.2.1 2

7.2.2 3

7.2.3 3

Extra credit: 5

I have written comments as to what is wrong with your solution in some cases. However, the complete solutions will be posted shortly. Please refer to them.

You can meet me during my office hours if you have any questions with the evaluation.

Thanks,

Aravind

[CSP Thinking cap]

2007-09-17T16:53:00.001-07:00

Here are some things you can think of:

1. Have you played Sudoku--if so, can you illustate how what you do in sudoku wind up being equivalent to the various CSP heuristics?

2. Suppose we have three CSP problems:

1. 20 variables and 5 (binary) constraints.

2. 40 variables and 200 (binary) constraints

3. 200 variables and 199,000 (binary) constraints

Which of the CSP problems above do you think will be easiest to solve? Which will be the hardest?

(assume that all constraints have about the same tightness).

3. For the CSP search algorithms we discussed in the class, does it matter whether the constraints are represented as (a) legal partial assignments (b) illegal partial assignments (c) pieces of code that take a partial assignment and return a boolean saying Yes/No.

4. A subclass S of a problem class P is considered canonical if every instance of P can be "compiled down" to a *finite* instance of S. For example, the class of "programs written in Intel m/c language" is a canonical class of all programs. (Instead of "finite" we might also consider compilations that are only *polynomially larger*--but ignore it for now).

4.1 (easy) Argue that SAT (i.e., boolean stisfiability problems) are a canonical class of CSP problems.

4.2 (harder) Argue that *Binary CSP* problems are a canonical class of CSP problems

5. (If you know Linear programming and Integer Programming). Argue that every 0-1 integer programming problem with constant objective function can be compiled down to CSP.

Rao

CSP Applet that you can play with..

2007-09-17T13:16:00.001-07:00

Try
http://www.cs.ubc.ca/labs/lci/CIspace/Version4/Constraint/index.html

for a java applet that allows you to specify CSPs and solve them.

(The link http://www.cs.ubc.ca/labs/lci/CIspace/index.html also has a variety of applets for search, logic etc etc that you may enjoy)

Rao

Homework 2 socket opened--qns on A* search added

2007-09-17T09:05:00.001-07:00

Re: Recitation session for project-I today (reminder) [cse 471/598]

2007-09-13T11:55:00.001-07:00

(for students who have a time clash during proj-1 recitation session today.. )..

I would be in Open lab (214 BYENG) from 5 PM today evening. We can sit together and go through the recitation slides, plus discuss your questions/doubts on proj-1.

Thanks,

Aravind

Dear Aravind Krishna :

I have a class between 3PM and 4PM today..

Is it possible to have that recitation for me or other people who are not available between 3 and 4 after 4:30PM again if you do not mind?

Thank you for your time.

On 9/13/07, Aravind Krishna <Aravind.Kalavagattu@asu.edu > wrote:

Hi everyone,

I will be holding a recitation session for project-1 during my office hours today, i.e., 3 to 4 PM. The venue is room no. 455 BYENG bldg 4th floor. (.. the conference room right opposite to the elevators)

Cheers,

Aravind

Recitation session for project-I today (reminder) [cse 471/598]

2007-09-13T01:16:00.001-07:00

Hi everyone,

I will be holding a recitation session for project-1 during my office hours today, i.e., 3 to 4 PM. The venue is room no. 455 BYENG bldg 4th floor. (.. the conference room right opposite to the elevators)

Cheers,

Aravind

[Thinking cap topic for 9/12]: Pattern databases etc.

2007-09-12T13:11:00.001-07:00

Hold forth on these... I am especially interested in seeing blog comments from 471 students..

First a diversion: Check out the following mail from earlier years on the history of n-puzzle problems and how these grabbed popular imagination at one time..
http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00023.html

Now the thinking-cap questions

0. Should h*(n) be zero for *all* goal nodes or only optimal goal nodes?

1. We argued that computing the optimal cost for getting each tile into its position and summing the distances will not give an admissible heuristic. However, Manhattan distance is doing the same thing--except in an abstract space. How come it is admissible?

1.1*****ADDED NEW (By EDITING BLOG POST)**********
[INTERACTIONS and Heuristics]

The reason we said we can't just add up true costs of putting individual tiles in the right position
is that the tiles have interactions. There are really *two* kinds of interactions

Positive interactions--getting one tile to its position makes it easier to get another tile to its position

Negative interactions--getting one tile to its position makes it *harder* to get another tile to its position.

How do positive and negative interactions affect the informedness and admissibility of the heuristics that *ignore* them?

2. The pattern we considered in the class was left and bottom edges. If instead we considerd the two diagonals of the goal position, will the resulting pattern database heuristic make sense?

3. Suppose there is a new 24-puzzle competition. You are all supposed to use the same hardware (computer memory etc) to solve
test instances optimally. Whoever solves the problem in the shortest time gets a prize (a "platinum-coated 24-puzzle, suitable for framing").
Before the competition starts however, everyone is given about 3 hours of time on the computer for any pre-computation. You want to use the pattern database heuristics, but you know that you don't quite have all the time needed to compute the pattern heuristic for all the possible states in the three hours. Is there any way you can use the precomputation time gainfully?

4. In the problem above, suppose for each team, they allowed two computers during pre-computation time. This obviously suggests the idea that you can compute two different pattern databases (say the left and bottom edges in one, and the right and top edges in the other). Can you imagine a way of using both the databases to improve search further?

--------------

[cse471/598] clarification on using blackboard (myasu) for the course

2007-09-10T21:19:00.001-07:00

Hi all,

You might want to note that blackboard portal would be used *ONLY* for project submissions (and moreover, only your code part of the projects goes in there). This is why there would not be any separate links opened for other exercises like homeworks and exams, on the blackboard. (so avoid relying on the links in blackboard as pointers to see what are the current active exercises & their deadlines)

You must keep checking the course website regularly for announcements and *submission deadlines* for the exercises.

Thanks,

Aravind

[cse471/598] Announcements (LISP recitation for proj1 -- plus -- grade distribution of assgn-0 )

2007-09-10T21:04:00.001-07:00

Hi all,

I hope you're all progressing well with LISP project-1 on search algorithms. I will hold a recitation session for project-1 during my office hours on thursday. (I will send you a reminder again with more details). You can also always email me your doubts / schedule an appointment separately in case you can't meet me during my office hours.

Please find the statistics of assignment-0 (LISP refresher) grading below:

Total: Required (30 points) + Extra Credit {e.c} (13 points)

Grade distribution: (most of you did great & scored full in the required portion)

UG:

Highest was ( 30 + 13 e.c ) : Least was 22 : Mean was 28.4

Grad:

Highest was (30 + 12 e.c ) : Least was 24 : Mean was 29.2

And the detailed evaluation scheme for each question is as follows:

1. 3

2.1 2

2.2 2

2.3 2

( 1 point extra credit for implementing "middle" in linear time )

3. 5

4. 5

5.a 2

5.b 2

5.c 2

5.d 2 (e.c)

6. 5

7. 5 (e.c)

8. 5 (e.c)

Let me know if you have any questions.

Thanks,

Aravind

[Thinking Cap]: Optimal Sub-structure;

2007-09-10T19:06:00.001-07:00

1. We talked about the fact that all our search algorithms use "optimal-substructure" property. Because of this we never have to maintain more than the "current best path" to a node. Give an example of a scenario where optimal substructure doesn't hold--and argue that in that case, (1) the markov property also doesn't hold ( i.e., where you can go from a state depends not just on the state, but how you got there) and (2) argue that you will need to maintain more than the best path to the intermediate nodes so as to be able to find the optimal path to the goal node.

1.1. In your example above, see if you can change the definition of "State" so that the optimal sub-structure property holds again (and so does markov property).

Rao

Important: Late homework/project acceptance policy..

2007-09-10T12:44:00.000-07:00

I have already started getting late submission requests.

To be fair to everyone as well as allow for human fallibility, here is the procedure we will follow.

Each of you will be allowed

* one extension for the homeworks and
* one extension for the projects.

The extension will allow you to submit the homework/project within two days from the deadline without penality
(if the due date is Monday, you will do the late submission by Wed class; if it is Wed, you come and deliver it
by Friday 10:40 to the CS office).

All you need to do is to send a mail to the TA or me *by the day of original due date* saying that
you plan to exercise that option (so we will wait before posting solutions).

No substitutions or negotiations; and the extensions are non-transferable..

regards
Rao

New thinking cap question(s)

2007-09-09T11:09:00.001-07:00

1. Your friend was doing an iterative deepening uniform cost search on a graph representing the
distances between various landmarks in town (presumably to find optimal paths between any pair of
landmarks). Originally he had a graph where all the road distances were measured in multiples of integral
miles (i.e. each edge cost was an integer). After a while, your friend decided to represent the distances
more accurately and so went and found all distances correct to four decimal places. All of a sudden he found that
the efficiency of his search worsened quite dramatically. He was perplexed at this since the underlying graph
topology was the same and distances were just more accurate. Can you explain what happened?

2. What, if any, are the differences between uniform cost search algorithm as we described in the class and "Dijkstra's algorithm" on

graphs that you have probably learned in CSE310?

Rao

Question 7.2.1

2007-09-08T22:59:00.000-07:00

"7.2.1. Argue that this search is likely to do better on the average than the best search you picked in 2.1"

Is it safe to assume that the "2.1" above is 7.1? Likewise, for 7.2.3, should it be 7.2, rather than 2.2?

Agenda and readings for tomorrow.

2007-09-04T20:34:00.001-07:00

TOmorrow we will complete the discussion of IDDFS, revisit answers to the blog questions, and shift to
discussing uniform cost search and A* search.

Assuming you already read 3.1 to 3.5, you should go ahead and read 4.1 and 4.2 (in the textbook)

rao

[cse 471] Instructions on submitting Assignment-0 (LISP refresher)

2007-08-30T18:22:00.001-07:00

Hello all,

I hope all of you are progressing well with the first LISP project (a.k.a assignment-0). Here are the instructions for its submission.

- You must submit a hardcopy of your report in the class. The report should have your code with a sample run of the solution for each problem. (say 2-3 input cases). You can add short comments for your solutions if you think it's necessary.

- And, you should submit only the "Code" part of the report in the blackboard section of this course (on http://my.asu.edu). I have opened a link for uploading your file -- check under "Assignments" section on blackboard. Put all your functions in a .lisp file, name the file as <firstname_lastname>.lisp and upload it. (Note that you can submit only once).

Let me know if you have any questions.

Thanks,
Aravind

[Announcement][Important]: Missing Question 5 added to Homework 1

2007-08-30T08:31:00.001-07:00

Question 5 was missing from homework (you had 6 after 4). I added question5--
please retrieve it again if you already retrieved it yesterday.

Rao

[Announcement] Project 1 assigned and is available on the homepage..

2007-08-29T15:59:00.001-07:00

You should be able to get started on Task 1. Task 2 (and 3) will be easy to start after next class.

rao

[Announcement]: Additional problems added to Homework 1. It is now due on 9/10

2007-08-29T15:02:00.001-07:00

[8/29 Discussion/Thinking Cap topic for BLOG] Search algorithms...

2007-08-29T14:52:00.001-07:00

Here are a few things that you can think about and/or comment on.

[0] (optional ;-) Estmate how near-sighted an instructor needs to be to not
notice that you are sleeping and/or doing something below the desk. The estimate can
be analytical, and can depend on your height, distance from the podium, decibels of snoring etc.

[1] (Iterative deepening search)

The following are two of the characteristics of iterative deepening search:

a. It uses depth-first search in each of its iterations
b. it increments the "depth cutoff" for the tree uniformly (i.e., there is one single depth limit
for all branches)

If I am considering the following changes to IDDFS

a': Instead of use depth-first search, use breadth first in each iteration
b': instead of using a uniform depth cutoff, use non-uniform depth cutoffs (i.e, the "search fringe" will
go to varying depths in different branches).

How do a' and b' affect

(i) completeness (ii) optimality (iii) time complexity (iv) space complexity properties?

[2](Effect of the goal distribution)
In the discussion we did in the class, I assumed that the goal node(s) can appear at any level of the
search tree, and anywhere in that level. If I happen to know that all goal nodes will appear only at level (depth) "m"
would it change the relative tradeoffs between breadth-first and depth-first? Can you think of some problems where
this type of property holds?

[3](search on finite graphs with cycles)
We noticed that even if the number of states is finite, it is possible for a search to "loop"--i.e., go back and forth between
the same state multiple times. This is a problem for both breadth-first and depth-first, but is a bigger problem for depth-first
(since it may not even terminate). One way of stopping this problem is to maintain a "CLOSED" list that contains all the nodes that have
been already expanded. Before adding any new node to the queue (i.e., OPEN list), we check to make sure if the state for that
node already exists on the CLOSED list. If it does, we don't put it back on the OPEN.

How does this simple idea affect the time and space complexity of depthfirst and breadth-first search?

Rao

Understanding the brain and then building intelligent agents

2007-08-27T22:18:00.000-07:00

This is regarding the discussion we had in class the other day. Here is a talk by a guy who's trying to do model the brain to help build intelligent agents.

(more on) whether we have strong linguistic knowledge ingrained at birth..(optional reading)

2007-08-27T21:25:00.000-07:00

In the class, I mentioned that all human infants come into this world with what can be thought of as a "universal grammar" that they can "tune" to the local language that they are hearing around them. In otherwords, language is not wholly learned outside--contrary to the common wisdom (the story of how "universal grammar" came about is also a fascinating one--see the mail that I sent to the class last year http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00090.html )

One question is whether there is really something special about the set of "human languages" as a whole that is different from any other languages.

In particular, if the human baby were to be given away to martians (or other aliens that regularly visit Area 51 and certain phoenix suburbs), would the baby be able to master the martian language? Conversely, if the human babies were to get together--without any intervention from adults, and were to make a brand new language, would it be closer to all the other human languages than it is to any other language?

We can answer the latter very much in affirmative thanks to the fascinating real life story of Nicaraguan Sign Language. A bunch of nicaraguan deaf kids who were ignored by their war-torn society and over a period of time developed a new sign language all their own from scratch. And it is *very* similar to other human languages (see the URL http:/ /en.wikipedia.org/wiki/Nicaraguan_Sign_Language ).

We don't yet have a clear and convincing evidence that babies can't learn martian and other alien languages, but we do know that human kids brought up without human contact are unable to develop language (see http://en.wikipedia.org/wiki/Feral_child )--in otherwords, the underlying universal grammar is able to identify and adapt only to "human" languages!

In our zeal to accentuate differences, we fail to note that in the spectrum of possible languages, all human languages form a really tight cluster--and would be seen so by a martian visiting earth..

Rao

[Discussion Topic--must comment] Optimality ; prior knowledge; discounted rewards; Environment vs. Agent complexity..

2007-08-27T13:36:00.001-07:00

[[Folks:
By now you all had enough time to get yourself signed up to the class blog. As I said, participation is "required" in this class. Participation involves
doing assigned readings, asking questions (as needed) in the class and most importantly, taking part in the class blog discussions. Here is the first discussion topic
for your edification.

As for the quanity vs. quality of your comments, I suggest you go by the Woody Allen quote below for guidance.. ;-)]]

Here are some of the things that I would like to see discussion/comments from the class

1. Optimality--given that most "human agents" are anything but provably optimal, does it make sense for us to focus on optimality of our agent algorithms? Also, if you have more than one optimality objective ( e.g., cost of travel and time of travel), what should be the goal of an algorithm that aims to get "optimal" solutions?

2. Prior Knowledge--does it make sense to consider agent architectures where prior knowledge and representing and reasoning with it play such central roles? Also, is it easy to compare the "amount" of knowledge that different agents start with?

3. Environment vs. Agent complexity--One big issue in agent design is that an agent may have very strong limitations on its memory and computational resources. A desirable property of an agent architecture should be that we can instantiate it for any <agent, enviornment> pair, no matter how complex the enviornment and how simplistic the agent. Comment on whether or not whether or not this property holds for the architectures we saw. Also, check out "Simon's Ant" on the web and see why it is related to this question.

4. Learning--In the class, we said that an agent can learn (and improve) its knowledge about how the world evolves and how its actions affect the world etc. One thing that was not clarified is whether "utilities" are learned or given/hard-wired. Any comments (using your knowledge of humans)?

5. Anything else from the first three classes that you want to hold-forth on.

Rao

----------------

"The question is have I learned anything about life. Only that human being are divided into mind and body. The mind embraces all the nobler aspirations, like poetry and philosophy, but the body has all the fun. The important thing, I think, is not to be bitter... if it turns out that there IS a God, I don't think that He's evil. I think that the worst you can say about Him is that basically He's an underachiever. After all, there are worse things in life than death. If you've ever spent an evening with an insurance salesman, you know what I'm talking about. The key is, to not think of death as an end, but as more of a very effective way to cut down on your expenses. Regarding love, heh, what can you say? It's not the quantity of your sexual relations that counts. It's the quality. On the other hand if the quantity drops below once every eight months, I would definitely look into it. Well, that's about it for me folks. Goodbye. "
---Boris in Love & Death (1975 http://us.imdb.com/title/tt0073312/ )

Blog for Fall 2007 ASU CSE 471/598 Introduction to AI

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

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

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

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

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

Final exam released

(important) Information about the final..

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

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

Solutions to the last homework posted online

A note on raw cumulatives etc.

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

Links from the last class

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

An optional question on learning has been added to homework 5

*Important* Headsup: Interactive review in the next class

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

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

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

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

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

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

Project 4 late submission requests..

[cse 471] Instructions for project-4 submission

Information regarding CSE574 being offered next semester..

[Thinking Cap] MDPs etc...

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

(Thinking cap) Complexity of planning

Solutions to Homework 4 posted..

Thinking Cap questions (comment on the blog)

Project-2 grading scheme and statistics

A blind carbon copy

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

Reading for the next class..

Video recording of the makeup class is on google videos

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

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

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

Fwd: Link to the slides and audio

Re: Regarding Project 3

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

Midterm solutions are available..

Project 4 available for *preview*

sqrt(2)^sqrt(2) is actually irrational (so you now know two irrationals p & q so p^q is rational)

Grade anxiety amelioration program..

Current Cumulatives (as of Haloween day)

Midterm grades statistics..

Required reading for Wednesday

Project 2 submission date/late submission etc..

Entailment status and learning

(optional) Review session for midterm-- starts 4pm in BY 576 on Tuesday

Reminder: *Important*--required reading for Monday's class

Re: Project 3 assigned and Homework 3 socket opened.. (I meant homework 4)

Project 3 assigned and Homework 3 socket opened..

Re: Homework 3 solutions posted online

Homework 3 solutions posted online

[cse 471] Instructions for submitting project-2

*Important*--required reading for Monday's class pp 504--515 in the text book

links promised in today's class

[cse 471] Homework-2 Announcements (grade distribution, marking scheme and a missing solution..)

[Thinking cap questions on bayes networks]

Homework 3 socket closed; Due 10/17

(Important) Proposed schedule for the semester+midterm on 10/24

Readings from the text book updated..

[cse 471] Recitation Session for Project-2 (tomorrow 3-4 PM)

A specimen midterm exam

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

[cse 471] Proj-1 statistics, grading scheme and comments

Project 2 assigned; description of what you need to do is online now. Due Oct 22nd.

*Real slides* for today's class now available online..

Results of class survey

Sheet1

Extension on homework 2: Due now on Wednesday Oct 3rd

there is no typo/erro in the pattern database question..

[cse 471] Instructions for your project report --plus-- Announcements on submission

The solutions to homework 1 are posted on the homepage (see the homeworks page)

Homework 2--CSP and Pattern database questions added and socket closed. Due date: October 1st.

Important Headsup: Interactive review in the next class

Project 4 available for preview

Reminder: Important--required reading for Monday's class

Important--required reading for Monday's class pp 504--515 in the text book

Real slides for today's class now available online..

Important: Late homework/project acceptance policy..

[Announcement][Important]: Missing Question 5 added to Homework 1