Seats in 571 for Fall

Sorry if you are getting this twice. 

Some of you have asked for seats in 571. The dept is apparently going to increase the capacity today by some 7 seats and offered to directly add students.

If you want you can send me your name and student id and I will pass it to the advising office to add you. (Alternately, you can just wait and try to add yourself once the capacity is increased)

Rao

Common errors on the final: One last mail before grades

Since you will be in no mood to think about any more AI once you get your grades, here is one cram-chance for two near universal errors:

1. Even after you are given the topology of a bayes network, you can reduce the number of independent parameters by using "parameterized" distributions

 (such as Noisy-OR) rather than CPTs.  For example, given a node with n parents, a CPT will need 2^n independent parameters, while if we decide to go with a NOISY-OR distribution, then we only need to give n parameters. (only one or two students got this right).

2. Even if a proposition p occurs in a planning graph with mutexes, it may still actually not be achievable by that level since standard mutexes only consider interactions between a pair of propositions at a time. If you have actions with >2 preconditions, it is possible that each pair of them are non-mutex, and yet all of them together are not possible. In that case, if that action gives the proposition p, you will add p in the next level, even though the action itself is not actually executable in the previous level.

Rao

*CORRECTED* Re: Final Cumulatives

The cumulative calculation for the UG students was messed up in the snapshot I sent earlier. Here is the correct one.

Also, the maximum points could could have got are 110 (not 106.). I will however act as if the cumulative totals are percentages. 

Rao

On Mon, May 7, 2012 at 11:39 AM, Subbarao Kambhampati <rao@asu.edu> wrote:

Folks:

 

 Attached please find the final cumulatives (with the marks from take-home final also put in).

The total is calculated with 20% weightage for the final.   So the maximum points one could have got on cumulative was

106.6. 

The current cumulative totals are shown. 

The students at the top of each of the sections are guaranteed an A+.  They (i.e., these two student) 

 are welcome to suggest  grade cutoffs for the rest of the class

in their respective sections. (The suggestion will only be non-binding of course; however I find that the students tend to have a better idea of the

comparative ease/difficulty of the courses--and so it is reasonable to consider their input on the grade cutoffs)

The final letter grades will be posted sometime tonight.

regards

Rao

Final Cumulatives

Folks:

 

 Attached please find the final cumulatives (with the marks from take-home final also put in).

The total is calculated with 20% weightage for the final.   So the maximum points one could have got on cumulative was

106.6. 

The current cumulative totals are shown. 

The students at the top of each of the sections are guaranteed an A+.  They (i.e., these two student) 

 are welcome to suggest  grade cutoffs for the rest of the class

in their respective sections. (The suggestion will only be non-binding of course; however I find that the students tend to have a better idea of the

comparative ease/difficulty of the courses--and so it is reasonable to consider their input on the grade cutoffs)

The final letter grades will be posted sometime tonight.

regards

Rao

A little levity after the final

I saw this and thought I had to share it with the class. Enjoy.

http://xkcd.com/1046/

Homework 3 Grading

Folks,

Homework 3 has been graded (the points were entered last week before the grade snapshot was sent to you) and can now be picked up from the AI lab at BY 557 (the homeworks are in a pile on the circular table).

The grading scheme was as follows:

A. 2+3

B. 2+3+5

C. 5

D. 4+1

E. 2+3

F. 5

G. 1+2+5

H. 3+2+2

Total: 50

If you have questions about the grading, please let me know soon. You can send me an email to set up a time to meet if required.

Thanks
--
Kartik Talamadupula

Re: CSE471: Where to Turn In Final

Also, I understand that the dept office will be closed from 4pm today (Monday). If you come after 4, you can slide your exam under my office door.

Rao

On Mon, Apr 30, 2012 at 3:56 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

yes. If  I am not in my office, you can turn it in at the main office and ask them to put it in my mailbox (they will put a stamp and put it in my mailbox).

Rao

On Mon, Apr 30, 2012 at 3:47 PM, Kevin Wong <kkwong5@asu.edu> wrote:

Hello,

Will the take-home final exam be turned in at your office?

Thank you

Re: CSE471: Where to Turn In Final

yes. If  I am not in my office, you can turn it in at the main office and ask them to put it in my mailbox (they will put a stamp and put it in my mailbox).

Rao

On Mon, Apr 30, 2012 at 3:47 PM, Kevin Wong <kkwong5@asu.edu> wrote:

Hello,

Will the take-home final exam be turned in at your office?

Thank you

Missing image in part G of homework 3 Re: CSE 471: Homework 3 solution

Here is the image that is missing.. I am just simulating XOR with OR and AND gates (both of which are linearly separable and so can be simulated by

the perceptrons)

Rao

On Sun, Apr 29, 2012 at 12:56 PM, Phien Pham <pdpham@asu.edu> wrote:

Hi,

In the solution for part G of homework 3, the image cannot be displayed. Can you check this, please?

Thank you

--
Phien Pham

Reminder about the "NO CONSULTATIONS WITH OTHER STUDENTS" clause of the take-home

Folks

 I just wanted to repeat that the final take-home must be done by you without consulting anyone (other than request for clarifications from me).

You can use the class resources such as the text, notes, videos etc, but are not allowed to trawl for answers on the whole-wide-web. Your signature on the front page

of the exam is your oath that you followed the rules. 

This is not a homework, but a test that gives you ample time and learning opportunity. 

I reserve the right to interview you on your answers to verify your understanding.

regards

Rao

Final Exam released..

Folks

 The final exam is available at http://rakaposhi.eas.asu.edu/cse471/final-12.html 

Please note that there may be a few changes and potential additions. 

In the interests of giving you plenty of time to work on the exam, I am releasing the exam right now rather than waiting until it is completely set in stone.

regards

Rao

Thanks for all the ballot stuffing ;-)

To 

  The students who took classes with me in 2011-12:

Dear all:

 I have been told by the department that I was voted by the students as the best teacher in CSE for 2011-12 year. 

Assuming that my constituency would have been the students who took classes with me this year, which includes you, I would like to thank you for all the  energetic ballot stuffing ;-)

I am supposed to get the (no doubt very substantial cash)  award on Monday during the CIDSE awards shindig.

Cheers

Rao

 

Heads up on Final Exam release..

Folks

 I am planning to release the final exam tomorrow morning (Friday) and it will be due Tuesday.

Rao

Cumulatives with homework 3 grades

Folks

HW3 has already been graded. 

 Attached please find the cumulatives with the homework 3 grade included.

Rao

Fwd: course evaluations

As per the message attached below, the Dean requested that we remind you about taking part in teaching evaluations. So, I am sending you this message. 

I do take your comments on the teaching evaluations seriously and thus encourage you to take the time to complete the evaluations. 

For those of you who are new to ASU, note that  evaluations are returned to us, in an anonymized form, much after your grades are reported. So your comments cannot affect your course grades in any way. 

regards

Rao

---------- Forwarded message ----------
From: James Collofello <JAMES.COLLOFELLO@asu.edu>
Date: Mon, Apr 9, 2012 at 9:20 AM
Subject: course evaluations
To: "DL.WG.FSE.Faculty" <DL.WG.FSE.Faculty@mainex1.asu.edu>

Colleagues,

 

I sent the message below to all of our students.  Please reinforce this messaging with your students.

 

Engineering Students,

 As this semester comes to an end, you will soon be receiving requests to complete engineering course evaluations.  We are committed to continuously improving the educational experience of our students.  Your course evaluations provide important input to this process which is reviewed by Program Chairs and School Directors as they evaluate curriculum.  Your course evaluations are also an important component in faculty performance evaluations impacting decisions regarding reappointment, tenure, promotion and merit.  Please complete your evaluations.

 

James S. Collofello

Associate Dean of Academic and Student Affairs

Professor of Computer Science and Engineering

School of Computing Informatics and Decision Systems Engineering

Ira A. Fulton Schools of Engineering

Arizona State University

 

Agenda for tomorrow's class---is in your hands..

Folks

 Tomorrow being the last meeting of CSE471, I have two alternative agendas we can follow:

1. You can come equipped with questions about the whole semester (questions about connections between topics, 

about state of art in various areas, about deeper issues in areas are welcome; very specific questions about

"can you show me one more worked out example of X" are probably better done during office hours)

2. I can do a  fast introduction to First order logic--a topic I normally cover but didn't get to this year. 

I am fine with either alternative. You can vote with your questions (or lack there of, as the case might be).

You have been forewarned (and I hope you won't be forearmed). 

Rao

If not a Turing Test, at least a Robo Grader..(only we can fool ETS too easily apparently ;-)

http://www.nytimes.com/2012/04/23/education/robo-readers-used-to-grade-test-essays.html?hpw

Re: Question related to previous lecture.

---------- Forwarded message ----------
From: William Cushing <william.cushing@gmail.com>
Date: Fri, Apr 20, 2012 at 11:25 PM
Subject: Re: Question related to previous lecture.
To: Subbarao Kambhampati <rao@asu.edu>
Cc: Juan Guzman <jcguzma1@asu.edu>


Well I suppose Rao CC'd me since I know a bit about games.  So here's info...but perhaps more than you wanted...

Opponent modeling is (very, very, ...) hard; an opponent can figure out that you've figured them out (or just get worried about the possibility) and suddenly change their style of play (for example, play randomly for a spell).

Last time I checked the case of Poker, which is perhaps as much as 5 years ago (or more!), the state-of-the-art had shifted back to not using opponent modeling, partially because of this sort of issue,
and partially because the state-of-the-art in finding the optimal line of play had advanced.
Specifically the advance that I'm aware of is to use state abstraction in order to produce a smaller, simpler game.
One that can be brute-force solved for the optimal strategy.
In that instance, it beat the then reigning approach based on opponent modeling.

One thing to keep in mind about Poker is that `bluffing' is a part of optimal play---in the Nash sense---and is something that two infinitely computationally powerful and rational agents would do to one another.
In *real-life* poker, the people who make the money are the people who ``play the odds''. 
It is only in popular culture that we imagine Poker to be a game largely about opponent modeling. 
In truth it is a fantastic exercise in relatively complicated statistical theory---and self-control.
The practical variant is of course investing in the stock market.

The most interesting work in opponent modeling that I'm aware of is for Rock Paper Scissors.
Here the Nash strategy is easy to compute, so, in a tournament setting, if you want to win the tournament, you *have* to be better at opponent modeling than everyone else is.
That is, the Nash player(s) for RPS will place in the dead-middle of a tournament.
Those who attempt to win will make profit off of each other; half will place above average, and half below.
The winner of the year I looked at in detail is called Iocaine (a reference to Princess Bride, and descriptive of its algorithm).
You may have seen the relevant Star Trek episode concerning Data playing against a grand master of a made-up game (Stratagus?).
(The lesson is that the only way to lose is to try to win.)

--

Final word on opponent modeling: No one really wants to play in such lopsided settings.
Either the stronger player is teaching, in which case the point is far from trying to punish the student as much as possible for making mistakes,
or a handicap is imposed---which is still a form of teaching, in that the stronger player isn't going to be upset by losing (but they also aren't going to make any hasty or kind moves).
Kasparov against a not-chess-genius 10-year-old at a two-rook and queen handicap, for example, could be excused for taking 10 minutes to think.

Some like to look at a handicap as a challenge in opponent modeling; how can you provoke the weaker player into mistakes, working towards getting rid of their material advantage?
But the better way is just to play normally, and let the mistakes happen naturally, if they do.
If they don't, then play another game, and reduce the handicap :).

Long story short, even when you far outclass your opponent in domain knowledge or raw computational ability, in almost all situations (but not tournament-RPS) it still makes sense to pretend that you don't.

-Will

P.S. Oh, and regarding Deep Blue, basically IBM hired every grandmaster they could get their hands on, especially those with the most experience playing Kasparov, and they collaborated on extensive study of all of his games ever recorded (something such masters of course had already spent years of their life doing), largely to produce what is known as an ``opening book'' geared especially towards playing Kasparov, that is, one containing the greatest pertinent details on every game he has ever played (and has since been analyzed to death).  I think little about the hardware or algorithms was very specifically targeted at Kasparov; after all, how can you?  He wouldn't be best if he had blind spots that anyone else can identify.  Recently much that was mysterious about Deep Blue is no longer `classified', but still much about the whole affair is hush-hush.  Whether or not that opening book helped at all is debatable, obviously the games were not repeats of past games.  From what I understand, the modern assessment is that Kasparov was defeated by his own humanity; the final games he lost in frustration, that is, it seems he should have been able to force a win if not for the unusual stress he had no experience in dealing with.  (The type of stress is hilarious: he couldn't stare-down Deep Blue; his inability to intimidate the opponent befuddled him, or so the story goes.  The poor technician tasked with implementing the computer's moves on the physical board describes his fear and trepidation upon approaching Kasparov quite colorfully.)

Modern chess-playing software is largely held to have surpassed Deep Blue, without resorting to special hardware, nor with any concerns about possibly being opponent-specific.
I don't know what the current reigning champ is, but for a spell I know Fritz was used as a study tool by most grandmasters (read: "Is stronger than.").

On Fri, Apr 20, 2012 at 5:51 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

Opponent modeling is done a lot of time (and for games like Poker, it is pretty much de rigueur. )

It may be less critical in chess where, at least at the grand master level, "optimal opponent" is a reasonable assumption.

I don't off hand know whether Deep Blue did opponent modeling to any extent--the classic reference on 

Deep Blue is this paper:

http://commonsenseatheism.com/wp-content/uploads/2011/02/Campbell-Deep-Blue.pdf

Rao

On Fri, Apr 20, 2012 at 5:02 PM, Juan Guzman <jcguzma1@asu.edu> wrote:

I had this thought during class, but I wasn't sure if it was necessarily relevant to the lecture.
Do agents like deep blue always assume an optimal opponent such as Kasparov? It seems to me that one would be able to deduce the expertise level of an opponent using the existing information of the game tree and analyzing the opponent's moves. Like the example you gave in class, If Kasparov would take 10 minutes to make a move against a 5 year old, we would consider it silly; If deep blue saw that the opponent kept making moves that were highly in its favor (mistakes) could we use that information to make the agent execute moves more suited to the situation? Rather than assuming that it's playing against a grand master and using min max, we can calculate the possibility of the opponent making an arbitrary (non optimal) move and make "bolder" moves as a result? Or does deep blue already make optimal moves regardless of the skill level of opponents?

- Juan
Sent from my mobile device

Re: Question related to previous lecture.

Opponent modeling is done a lot of time (and for games like Poker, it is pretty much de rigueur. )

It may be less critical in chess where, at least at the grand master level, "optimal opponent" is a reasonable assumption.

I don't off hand know whether Deep Blue did opponent modeling to any extent--the classic reference on 

Deep Blue is this paper:

http://commonsenseatheism.com/wp-content/uploads/2011/02/Campbell-Deep-Blue.pdf

Rao

On Fri, Apr 20, 2012 at 5:02 PM, Juan Guzman <jcguzma1@asu.edu> wrote:

I had this thought during class, but I wasn't sure if it was necessarily relevant to the lecture.
Do agents like deep blue always assume an optimal opponent such as Kasparov? It seems to me that one would be able to deduce the expertise level of an opponent using the existing information of the game tree and analyzing the opponent's moves. Like the example you gave in class, If Kasparov would take 10 minutes to make a move against a 5 year old, we would consider it silly; If deep blue saw that the opponent kept making moves that were highly in its favor (mistakes) could we use that information to make the agent execute moves more suited to the situation? Rather than assuming that it's playing against a grand master and using min max, we can calculate the possibility of the opponent making an arbitrary (non optimal) move and make "bolder" moves as a result? Or does deep blue already make optimal moves regardless of the skill level of opponents?

- Juan
Sent from my mobile device

*Mandatory* Interactive Review Question (Must answer as a comment on the BLOG)

As mentioned in the class today, all of you are required to answer the following Interactive Review question on the Blog.

It has to be done by 2PM on Tuesday (notice that this is *before* the start of the last class).

===========

List five or more non-trivial ideas you were able to appreciate during the course of this semester. 

(These cannot be gratuitous jargon dropping of the "I thought Bayes Nets were Groovy" variety--and have to include some justification).  

The collection of your responses will serve as a form of interactive review of the semester.

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


If you need to refresh the memory, the class notes page at http://rakaposhi.eas.asu.edu/cse471 has description of what was covered in each of the lectures. 

Rao

A cool Java applet for Chess that shows the computer "thinking" its moves using min-max and alpha-beta & Quiescence search

Here is a cool applet that allows you to play chess with the computer, and shows all the moves that

the computer is considering and their relative strength..

http://transition.turbulence.org/spotlight/thinking/chess.html

See the "About" link on the page for information on what they use..

Rao

Office hours 2-3pm today..

Folks

 I have to attend an event until 1:30pm today, so I will hold office hours 2-3pm today.

rao

Bayes Net Project Answers and Stats

Max Possible Points: 69

Undergrad:
 max 64.5
 min 42
 avg 56.5
 stddev ~7.2

Grad:
 max 67.5
 min 41.5
 avg 61
 std dev ~7

--

Check marks are one point, slashes are half points, and x's are no points. 
Plus and Minus are for exceptional answers.

Showing the screenshots is worth a point, except for part 3, which is worth two points, and part 2, which is worth no points.
Every `interesting' number in a CPT is worth a point.
Short answer questions are one point each.

The following is a detailed breakdown and meant only as a reference, not gospel --- it may contain errors since I wrote it from memory.

--

Question 1:
The correct numbers are straightforward, very few lost points. 
1 point for the diagram, 10 more for the CPTs, 5 for the calculations, 2 for the short answers.

Intuition:
Our belief in inferior plutonium should increase if we see that the slushies are liquified, as a possible cause of that is core meltdown, and in turn, a possible cause of core meltdown is inferior plutonium.
Of course if we directly observe a core meltdown then our belief should only be that much stronger in inferior plutonium.
At that point the state of the slushies is irrelevant, since slushie liquification is just a poor man's test for predicting whether core meltdown occurred.
Interestingly, if we know that a core meltdown has occurred and the water is poor quality, then we already have a good explanation for the core meltdown and so our belief should be somewhat lessened in the possible fault with the plutonium.
(For two things to both have gone wrong at the same time is harder to believe then just one thing going wrong!)

D-SEP: Regarding irrelevence of slushies once we know core meltdown: The formal test is to cut every path between the two nodes (with or without evidence depending on the type of path). 
There is just one path connecting IP and SL, going through CM, and the configuration is not -> CM <-.  Then knowing CM cuts that, and thus all, paths between IP and SL and we have that they are D-separated.

--

Question 2:

All but a handful got this wrong, so, a little theory first.
There are two key words: "perfect" and "exhaustive".
For a cause to be perfect it gives its effects with 100% probability, or, in propositional logic, a forward implication. 
For causes to be exhaustive means that the effect occurs with 0% probability in the absence of all causes.  In propositional logic, one could write a backwards implication (the converse), or the inverse.

So, encoding 1 (effects+converses):
 (LW or IP) <=> CM
 CM <=> GD
 CM <=> SL

Or encoding 2 (effects+inverses):
 (LW or IP) => CM
 CM => GD
 CM => SL
not (LW or IP) => not CM
 not CM => not GD
 not CM => not SL

There were 6 possible points for the encoding, 3 points for the calculations, and 2 points for the short answers.

Interpretation:
1) If SL, since causes are exhaustive, a cause had to be true, and there is only one: Core meltdown.  Again there must be a cause, but, there are two possible causes.  In the lack of any further evidence the best we can do is count those situations where IP is true versus false and infer the appropriate ratio, i.e., the best we can do is compute the probability.  Assuming you didn't change the priors, then, the number is 0.52.
2) As before, but now we have additional evidence ruling out bad water as a cause.  Left with only one possible explanation, again by the assumption of "exhaustive", it must be that the plutonium was bad.  So the probability is 1.0.
3) The probability is 0, because there is no possible world in which IP holds given the evidence.  This query is special though, because the probability of any and all queries given the evidence ~GD and SL is 0. 
By exhaustive causes and SL, CM must be true.  By perfect causes, then GD must also be true.  But since ~GD is given, there cannot be any world satisfying any property. 

Relation to Propositional Logic:
1) We could count possible worlds even in propositional logic, but, not in a `weighted' way (otherwise we are just doing straight up probabilistic propositional calculus already). 
One can get the tool to tell you what the right numbers are by giving priors on IP and LW that are fair coin flips.
2) Exactly the same as in the probabilistic case, formally: SL => CM and SL gives CM; CM => (LW or IP) and CM gives (LW or IP), finally (LW or IP) and ~LW gives IP.
3) Given a contradiction, we can infer anything we like, the opposite of the Bayes Net situation.  (In the net, IP either true or false is probability 0.  In the propositional encoding, one could infer that it is simultaneously true and false.)


One could of course still get points for shorter answers, I am just being verbose.  It was very unlikely to get points for either interpretation or relation to propositional logic if your encoding was wrong to begin with.

As a total freebie the CPTs were given 10 points for this question, where one was even permitted to change the priors around somewhat on IP and LW.

--

Question 3:

2 points is for giving GD just the parent CM, LW the parent CM, and IP the parents LW and CM.
1.5 points is for extra edges.
Less is for downright wrong networks. 

In the ideal network there are 11 probabilities that need to be assessed, and there are 11 points awarded if your network includes those values in the right places (duplicated however many times needed by redundant parents).
Note that you can use the original network as an oracle for more than just values --- you can also test conditional independence assumptions in order to figure out that GD does not need SL as a parent, yet, IP does need LW as a parent.

1 point if you said this network was worse than the original, or implied it well enough. 

1 point if you demonstrated that your network reproduced the right values.

--

Question 4:
part a) 1 point for the diagram; 5 more points for the `interesting' numbers, i.e., the CPTs that are new/different.
part b) 1 point for the diagram; 8 more points for the differing numbers. 
  I was kind here regarding rounding---not that there was a choice since only one student noticed that one needed to provide 8 digits of precision to do the question justice.
  (In general throughout the assignment any answer rounded consistently was acceptable.)

--

I was not kind regarding simple oversights, like swapping two numbers; the tool+assignment are too easy to use and complete and anyways there were tons of freebie points.


-Will

Latest cumulatives (with the project 3 as well as the at home version of the test 2 included)

Folks

 Thanks to your hardworking TAs, here are the latest cumulatives for the course (out of approximately 84 points) 

These include Project 3--which was included at a 10% weight, and the at home version of test 2.

The formula for effective grade of test 2 is

max(in-class,  w*in-class+(1-w)*at-home)   where w=.5 for 471 and .6 for 598 section 

The max is there so that the lowest you can get is your in-class score (thus the couple of people who didn't do

the test at home don't lose any effective points). 

The only other grades to be entered are the homework 3, final exam and participation credit. 

If you find any discrepancies, please let us know. 

regards

Rao

Applets URL corrected for homework 3

As some of you pointed out, the URL for the applets specified in the homework 3 last part has changed.

The correct address is http://www.aispace.org/mainTools.shtml

I modified the homework writeup also to reflect this.

Rao

Thinking Cap: A Post-Easter Resurrection..

Considering that this is the last quiet weekend before the beginning of the end of the semester, I could sense a collective yearning

for one last thinking cap. So here goes...

1. We talked about classification learning in the class last couple of days. One important issue in classification learning is access to training data that is "labeled" --i.e., training examples that are pre-classified.   Often, we have a lot of training data, but only part of it is pre-classified.

Consider for example, spam mails. It is easy to get access to a lot of mails, but only some of them may be known for sure to be spam vs. non-spam.   It would be great if learning algorithms can use not just pre-labeled data, but also unlabeled one. Is there a  technique that you can think of that can do this?  (Hint; Think a bit back beyond decision trees..)  

(Learning scenarios where we get by with some labeled and some unlabeled data are are "sem-supervised learning tasks").

Okay. One is enough for now, I think..

Rao

Next topic: Search in perfect information games: Chapter 5.1--5.3

Folks

 Rather than do first-order logic, I decided you might enjoy hearing about game tree search (and how Deep Blue works, for example) --as it also gives us a chance to think about scenarios that involve more than one agent. 

 So we will do Chapter 5--section 5.1--5.3 next. 

Rao

Last homework-cum-micro-mini-project released

Folks

 I added the third homework with one multi-part question that asks you to do decision trees, naive bayes classifier and perceptrons for a Seinfeld party example.

Note that the last part asks you to experiment with applets. 

This will be due on the last day of the class.

I might add some First order logic questions, for which I will provide answers--but you won't need to submit your answers.

Rao

My mis-statement in class about the standard resolution refutation proof error

In class, I said that a standard error that I had pointed out to you during resolution refutation class was still made by 3-4 people in the class.

Actually I mis-spoke. 

The error that students did in the exam was  to say that

~(A V B) resolves with A VB to give empty clause.

This is semantically correct (~(A V B) is indeed inconsistent with A V B and allows us to derive false) but syntactically wrong in that ~(A V B) is not in the clausal form.

If you put it in clausal form you will get two clauses, ~A and ~B which can then be resolved with AV B in sequence to get empty clause.

The error I had pointed out in the class earlier was a more egregious one in that it is both syntactically and semantically incorrect.

This one involves saying  ~A V ~B resolves with A V B  giving empty clause. 

Here ~A V ~B is not actually inconsistent with A V B (The world  A=True, B =False, is a model of both formulas, for example). 

Rao

Grading for your homework 2

Hi all:

You will receive the grading for your homework 2 today. The maximal point is 81. Here are the stats:

- Undergrad: max = 60, min = 9, average = 37.6, stdev = 15.5 (excluding one student not submitting the homework)

- Graduate: max = 79, min = 37, average = 65.2, stdev = 10.4.

And here are the detailed points for each question and some observations that I have:

Question 1: totally 14

e, f: 3 each

g: 4 (1 for each heuristic)

h: 4 (2 for the mutex propagation, 1 for each heuristic)

Most of you did well for this planning question (some students however did not know the difference between a relaxed planning graph and a transition graph on the state space).

Question 2: totally 8

Soundness using truth table: 4 (you should be able to explain it correctly to get the full credits). Wrong explanation: -2

Completeness: 2. Wrong explanation: 0 (many students are confused between the completeness of an inference rule with the "equivalence" relation between two formula).

Resolution: 2

Question 3: totally 13

Propositional theory: 2

Clause form: 2

Resolution refutation: 3 for each. Total: 9

One mistake that I saw was that some students represented "mortal mammal" with a single proposition. Although with this KB, you can still prove/disprove the conjectures about "magical", "horned" and "mythical", doing so means that "mortal mammal" and "immortal" are two independent propositions, but apparently they are not.

Question 4: Totally 30

4.1 (Short answer questions): Totally 7

A: 3

B: 4 (2 for each question)

4.2 (Modeling the Springfield nuclear power plant): Totally 23

A: 5

B: 4 (1 point for the first two, 2 points for the last)

C: 3

D: 3

E: 8

Most of you did well in this question (however some student didn't even write Bayesian rule correctly for 4.1.A). For 4.2.C, many students used the argument that knowing "inferior plutonium" reduces the belief in "low quality heavy water" to claim that p3 < p1 (or the opposite), which is not true. It only means that p3 <= p2.

Question 5: Totally 16. Four for each part.

Many of you didn't convince me that you actually knew why P(AC) != P(A)P(C) for both 5a and 5c to get the full credits; fortunately the other two were easier. Also note that if you didn't actually try to prove these parts using probability and Bayesian rule, you won't get any credits.

Please let me know if you have any questions.

Thanks,

Tuan

Current Grade Book (with test 2 and homework 2 scores)

Folks

 Attached please find the current gradebook with test 2 and homework 2 scores. 

The current "totals" are computed with 20% weight for each of the tests, 10% weight for each of the projects and 5% weight for each of the homeworks, and 1% for the initial lisp homework.

(thus a 71%).   This is only roughly indicative of the cumulatives--the weights for the tests will have to come down to make room for the project 3 (which is still being graded), the final test as well as

the last homework/project. 

Rao

An easter egg in the form of Test 2 do-over..

Folks

 If you want a second coming of Thursday's test, here is your opportunity. 

I am attaching a pdf version of the test. You can do it  and submit it on Tuesday, and your test grade will be a weighted average of

your in-class and at-home grades. Note that if you already thought you did well, this may not be worth the time for you.

The at-home version will be open book and notes, but you are required to do it yourself without consulting anyone else.

Happy easter..

Rao

Availability tomorrow

I will be generally available most of the day tomorrow for any last minute exam related questions. Just drop by my office (BY 560)

(You can call 965-0113 if you want to confirm that I am there before coming)

Rao

Some errata corrected in the Spring Field problem solution

The following parts are corrected (this is the correct version)

Part B.[4pt] Given your network above, which of the following (conditional) independences hold? Briefly justify your answer in each case:

1. Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant

Given no evidence at all, they are independent of each other.

2. Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant, given watery slurpees over at Apu's.

Using D-SEP, we can see that once SL is given, IP and LH are not independent (the "common-effect" case; since neither CM nor any of its descendants can be in the evidence for IP and LH to be independent)

3. Independence of low-quality heavy-water and wateryness of slurpees at Apu's, given core-meltdown

Using D-Sep again, LH is indepedent of SL given CM (since the only path from LH to SL goes through CM, and it is an inter-causal path, and it gets blocked once CM is known). Another way of seeing this is that CM is the markov blanket of SL, and so given CM, SL is independent of everything else.

Cleaned up most of the UTF-8 error chars in the springfield bayesnet example

Folks

 I cleaned up most of the annoying UTF-8 error chars (the dreaded question mark in the diamond thingies)--you may want to reload the page for a less annoying

(but not any more correct) version

rao

Forgot to tell you about the Turing award for PAC...

In my haste to complete the class on time, I forgot to mention that the Turing award for last year

went to Leslie Valiant for inventing the notion of PAC (probably approximately correct) as part of his work

on the theory of the learnable.

see http://www.acm.org/press-room/news-releases/2011/turing-award-10

(I hope you still remember that the Turing award for this year went to Judea Pearl for his work on

bayes networks)

Rao

ps: I misspoke a bit when talking about "sample complexity"--it is the least number of examples needed to learn the

     concept by any algorithm (not the "most"). You saw that the inequality on the slide was N >= 

Re: Review for Thursday

Some students expressed an interest in having a review session prior to the thursday test.  I'll be holding a review in BYENG 210 from 12:00 to 1:00 pm tomorrow (and normal office hours before that). 

If you cannot make those times work for you, let me know and we can arrange to meet individually at another time.

-Will

Project 2 Grading

Hello,

Project 2 will be returned to you in class tomorrow. Most of you did quite well.

The project was graded out of a total of 100 points. The undergrad section average was 87.8, and the graduate average was 95.8.

If you've had points marked off, I have indicated in most places why that is if it isn't fairly obvious already. Extra credit has been assigned based on the nature of the extensions (if any), and is marked separate from your total points on the main part.

If I have asked for clarifications from you (via comments on the report), or if you have questions about the grading, please send me an email at krt@asu.edu.

Thanks

Solutions to Homework 2 posted online

FYI 

Rao

Geo-centric model and limit of Occam's razor.

I mentioned geo-centric model of the planetary motion a couple of times about how a sufficiently complex model can always be invented to fit the data.

In case you haven't seen a geo-centric model before, here is a Ptolemaic one

http://upload.wikimedia.org/wikipedia/en/2/24/Ptolemaic-geocentric-model.jpg

http://www.flickr.com/photos/mr_t_in_dc/4115860027/lightbox/

(see wikipedia entry for Occam's razor--another term I used in class about Nature's predilection for simplicity--which interestingly also uses helio-centric and geo-centric models as examples:  http://en.wikipedia.org/wiki/Occam's_razor ) 

Rao

ps: interestingly, nature doesn't always seem to go for the "simplest" model--or at least not necessarily as we will model "simple". An interesting case in point is how the genes code the 20 amino acids. The original idea Crick had involved coming up with exactly 20 "unambiguous" triplets that can be placed next to each other and you will still be able to decode the sequence correctly even though there is no obvious delimiters between each amino acid code. This "comma free" version turned out not to be the one nature uses--which uses ambiguous triplets but ensures correct translation by using  specific starting/stopping  delimiters (see for example  http://www.emunix.emich.edu/~rwinning/genetics/code.htm).  The original Crick code was so compelling that it has been called the "greatest wrong theory". 

Re: Project 3 bn/bif question

I think .bif is fine (the .bn was the format they used to support in the past...).

Rao

On Tue, Mar 27, 2012 at 10:16 AM, Ivan Zhou <izhou@asu.edu> wrote:

Hi,

 

Quick question: In the project when it is asking for .bn, is it refering to the .bif text since that is the first option under the edit toolbar command? Or is it just copying only the probabilities section that the .bif text shows at the bottom? I'm confused since I cannot seem to find any "bn" reference in the applet.

 

Thanks,

--
Ivan Zhou

Graduate Student

Graduate Professional Student Association (GPSA) Assembly Member

Eta Kappa Nu (HKN) Active Member 

School of Computing, Informatics and Decision Systems Engineering

Ira A. Fulton School of Engineering

Arizona State University

Project 3 submission instructions..

I received some questions on project 3 submission format. 

As mentioned in the project description, all we need from you is a report (in hard copy) showing your answers/observations to all the tasks.

In all cases, include the copy of the bayes network (and CPTs) that the applet showed.

Rao

Re: Dawkins' rant on coin-toss superstitions

yes that is interesting reading ;-) 

On Sun, Mar 18, 2012 at 4:09 PM, Srinath Raghavan <sraghav4@asu.edu> wrote:

Hello Professor,

I read this after the last class. What a coincidence! Couldn't resist sharing it with you.

Page 235/271
Prof Richard Dawkins' rant on coin tossing superstition  http://i.imgur.com/zyWfv.jpg 

Thanks,
Srinath

textbook writeup on D-Sep condition

As some of you pointed out, the latest edition of R&N doesn't have discussion on the D-Sep condition--which I

did in the class. 

You can get the discussion from an earlier edition at http://rakaposhi.eas.asu.edu/cse471/dsep-condition.pdf 

Rao

Homework 2 will be due on 3/29

As discussed in the class, 

Homework 2, on topics of planning graph, propositional logic and bayes networks, will be due on Thursday after springbreak.

Rao

Grading for your project 1

Hi all:

You will receive the grade for your project 1 today. Here is the stats:

- Undergrad: max = 120, min = 30, avg = 98.7, stdev = 27.4

- Graduate: max = 126 (including 5% bonus), min = 55, avg = 107.3, stdev = 17.8

The detail of each part is as follows:

PART 1: Total = 40

Task 1: 5, task 2: 15 (for the right, up and down moves), task 3: 5, task 4: 10 (5 for each heuristic function), and task 5: 5.

If your code produced the correct sequence of moves for the 5 instances, then you will very likely get the full credits. One exception I saw was that some student implemented the heuristics incorrectly, and thus the statistics and the corresponding analysis did not make sense.

PART 2: Total = 38 

Task 1A, B, C, E: 5 for each, task 1D: 8. Task 2: 10.

This is perhaps the easiest part of the code, though some students got the branching factors wrong.

PART 3: Total = 42

For each item listed in part 2, you need to have the statistical numbers and reasonable comments on the difference between (a) the blind search and the informed search algorithms, and (b) contrasting the A* search with the two heuristics. The full credit for each one is as follows: 1A: 10, 1B: 6, 1CE: 6, 1D: 15 and 5 for the running time. 

Initially, I expected to see the statistics when running your code with a large number of test cases (not only the one provided)---large enough to see especially the clear distinction between the two heuristics; however, the reality is that very few had additional test cases. So my "relaxation" for this part is that you will get 1/3 credits for each of the followings: (a) correctly reported the numbers for the test cases provided, (b) correctly described the difference between the breath-first and the informed search approaches based on your data, and (c) similar to (b) but between the Manhattan and the misplaced tiles heuristics. 

Please let me know if you have any question.

Tuan

Project 3 released; Due 3/27

Folks

 I released the next project--this will involve modeling with Bayes networks (and using a bayes net applet).  It will be due the Tuesday after the Spring Break. 

This project is also modeling rather than a coding project. It dovetails well with the bayes network homework question (you can use the applet to check your homework question answers, for example).

I may add another small coding part to the project before the due date.

Rao

A worked out example on variable elimination

Here is a write-up that explains the operation of variable elimination algorithm in excruciating detail

http://rakaposhi.eas.asu.edu/cse471/varelim-example.pdf

Rao

Office hours tomorrow from 2:30--3:30pm (instead of 1-2pm)

Folks

 I have to shift my office hours to 2:30pm tomorrow.

regards

rao

Project 2: Extra Credit

Hello,

We've had a few questions about possible extra credit for Project 2. Here's a clarification that may (or may not) help you.

Loosely, what we are looking at is for you to explore the boundaries of what you can and cannot model with PDDL. Given that, something like just throwing a larger number of objects into a problem simply to make a bigger instance is probably not very interesting. 

However, exploring the things you can do (for example) using the type hierarchies in the definition of the object types, defining different actions from the ones mentioned, extending the domain itself - these are all interesting things to do. These will of course lead to problem instances different from the ones that we have provided. Of course, these are only some suggestions.

Please do include a detailed explanation of whatever extra credit you choose to do (if at all) in your project report. We will try our best to provide you support if you run into problems while pursuing the extra credit, but in the interests of fairness we will try to help students who have questions about the mandatory portion of the project first.

Good luck.

Project 2: Submission Instructions

Hello -

Here are some instructions on submitting project 2. We will be using Blackboard for the submision (like Project 1). There should be a link to submit it under course content on the Blackboard page. Please read through this entire mail.

Please include all your deliverables in one zipped folder, which you will name proj2_lastname_firstname.zip (so if your name is 'John Smith', your zip file should be proj2_smith_john.zip). The list of deliverables is available on the specification webpage.

Please make sure that you only submit once, as this makes it much easier for us all. The due date is Thursday March 8th 2012 before class (so any time before 4:30pm Arizona time is fine).

Additionally, you will turn in a printed copy of your project report in class. If you find that you are unable to make it to class that day, please hand it to one of the TAs or leave it in Dr. Rao's mailbox before then.

Thanks and good luck.

Flip-flopping--from a cognitive, social and effectiveness stand points..

The last couple of classes, we had occasion to talk about "flip-flopping" as an analogy for the monotonicity of logical inference. 

This morning, I heard a very interesting news story on NPR about how people perceive inconsistency as well 

as whether consistent people are more effective than inconsistent ones.  Here is a link; you might enjoy it:

http://www.npr.org/blogs/health/2012/03/05/147807206/inconsistency-the-real-hobgoblin

Rao

As promised, the Theory of worlds.. according to George..

http://www.youtube.com/watch?v=uPG3YMcSvzo

and

http://www.youtube.com/watch?v=3afZip4BTRc

Rao

Thinking Cap: Why don't we talk of independence assertions in Propositional Logic..

So we made a big deal about the importance of independence assertions in deciding the shape of the joint 

distribution. 

How come we didn't need to think about independence assertions while in propositional logic?

Rao

Project 2 FAQs

Hello,

We've had a few questions from students on Project 2, so we've made a small 'FAQs' section on the project page. Please take a look at it as it may answer some of your own questions. If you have others, please send them in to the TA help address. We will update the FAQs as we get more questions, so do keep track of that particular section.

Thanks.

Re: Questions on Project 2

Hi Srijith,

1. Yes, it supports preconditions. The problem with UMTS is the "or" that is present in that precondtion line that you've pasted below - Sapa Replan doesn't support those. Right now, if you want an action that supports 'or' kind of semantics, you have to implement it as two different actions with no 'or'.

More generally, for things of the nature of connected, if you don't want to manually encode (a conn. b) <-> (b conn. a), then you can think about some kind of 'domain axiom' action that fires and gives that effect. That is one way, the other of course is to just manually encode it.

If you are downloading the IPC3 domains, you might want to try something from the "Tests1" or "Tests2" suite. "Tests3" may not always work. Also, please stick to the "Strips" sub-folder (since the others have some features that Sapa Replan may not currently support, and that we don't need for this project).

2. Yes, you can give in object types as parameters. See the sample files for examples. Not too sure what your question is ... if you mean "can I use one action for reporting in both rooms and hallways", yes, you can. Think about the line where I said they are both subtypes of the larger 'location' type. Does that help?

Thanks.

On Sun, Feb 26, 2012 at 1:10 AM

1. Does the planner jar you gave us support in preconditions? I seam to get error on the ones that is available in http://planning.cis.strath.ac.uk/competition/domains.html (UMTranslog-2)
Here is my code:
:precondition (and (at ?p) (or (connected ?h ?p) (connected ?p ?h)))

Output:
Exception while parsing domain robby!
edu.asu.sapa.parsing.ParseException: Encountered "(" at line 13, column 29.
Was expecting:
   ")" ...

       at edu.asu.sapa.parsing.PDDL21Parser.generateParseException(PDDL21Parser.java:4230)
       at edu.asu.sapa.parsing.PDDL21Parser.jj_consume_token(PDDL21Parser.java:4109)
       at edu.asu.sapa.parsing.PDDL21Parser.AllIConditions(PDDL21Parser.java:1063)
       at edu.asu.sapa.parsing.PDDL21Parser.InstantAct(PDDL21Parser.java:1139)
       at edu.asu.sapa.parsing.PDDL21Parser.Action(PDDL21Parser.java:843)
       at edu.asu.sapa.parsing.PDDL21Parser.ActionList(PDDL21Parser.java:835)
       at edu.asu.sapa.parsing.PDDL21Parser.parse_domain_pddl(PDDL21Parser.java:62)
       at edu.asu.sapa.Planner.main(Planner.java:73)

It works if I change to and instead of or.

2. Is there a way to give or in the parameters? For example Report needs to take in room and hallway. Currently I solved it using two actions report-room and report-hallway. I feel there should be a better way.


I checked the tutorials you had attached in the bottom of the project description. I couldn't find direct answer to my question there which is why I am mailing you.


Regards,
Srijith Ravikumar

Homework 2 problems

Homework 2 socket is open and there are three problems there on planning graphs, inference rules and propositional resolution refutation. 

You should do the problems when the material is fresh in your minds. I can only guarantee 1 week lead time before I close the socket and make it due.

cheers

Rao

Project 2: Tutorial

Hello,

We've put up a short 16 minute tutorial to help you get started with the project. We'd strongly recommend going through this before you start on the project, as it will answer a lot of your questions about PDDL and the project. The tutorial can also be accessed on the project 2 specification page.

Please start early!

Thanks.

Readings for next topic: Chapters 13 and 14 in 3e

For our next topic on probabilistic propositional logics, you can start reading chapters 13 and 14.

Sections 13.2--13.5 are a quick revision of your high school probability theory; we will go through it fast--you should read to make sure that

your memory is refreshed.

Rao 

Project 2 Preview available; Due March 8th; in class

Folks

 Project 2 is available for preview from the projects page. It becomes officially assigned tomorrow, and will be due on March 8th. 

Please note that this project doesn't require any coding, but rather requires writing a domain model (like we did for blocks world in the class), and feeding it to a planner we provide for you. 

Please note that I do not plan to do an extension of deadline for this project. We think it takes about one week, and so we are in a way already giving you double time. 

Please don't wait until the last minute to get started--we really do not have the infrastructure to hold your hands the night before the deadline.

Regards

Rao

Undergraduate research opportunity with my group..

This is meant for the students in the 471 section.

I have funds  from National Science Foundation through their Research 

Experiences for Undergraduates program that can support undergraduate  students at 10$/hour; 10hours/week, 

and get research experience. 

My group works in AI and Information Integration. With respect to this class (CSE471), the topic that is closest

to our research interests is planning (which we discussed, and you will do a project next). 

If you either liked planning or are finding AI interesting, and want to explore the opportunity, talk to me. 

Rao 

ps: A list of students in my group can be accessed by the URL

http://rakaposhi.eas.asu.edu/rao.html#students

A list of recent publications from the group can be found at http://rakaposhi.eas.asu.edu/papers.html

-----

Subbarao Kambhampati

http://rakaposhi.eas.asu.edu 

Thinking Cap 2: Search, Theorem Proving and SAT

Just when you thought the cap is gone for good.. Here are some thinking cap questions you can think/comment on: 

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

2. Suppose you have a propositional knowledge base KB, and you just proved a theorem alpha. Now more facts are added to the KB to give KB'. Will the theorem you proved in KB  still hold in KB'? What if the facts I added made KB' *inconsistent*? [The property we are talking of here is called "Monotonicity"--propositional logic is monotonic.]

2.1.  Question 2 points out that propositional logic is no John Kerry (or Mitt Romney--for you dems)--in that it doesn't "flip-flop". But is not "flip-flopping" really all that great a property? Consider this.  I tell you Tweety is a bird. Do you think Tweety flies?

Now I tell you Tweety is an ostrich. Do you think it flies?  Now I tell you Tweety is a magical ostrich. Do you think it flies? Now I tell you Tweety just got cursed by the local witch/druid. Do you think it flies?   

Do you think it would be good to not "flip-flop" in the example above?

3. The "informedness" of a heuristic is not as great an idea as it is touted to be. You will likely found, during your project 1, that the search with manhattan distance heuristic sometimes does *more* expansions than the search with misplaced tiles

heuristic! In this thinking-cap question you will try to understand why this happens. 

Consider a search problem, for which you have two *admissible* heuristics. h1(n) is h*(n)/5 ;  h2(n) is a constant C (except of course at goal nodes, where it has to be zero), such that h2(n) is always higher than h1(n).  Which is more informed? Which do you think is a better heuristic?

In particular, given a heuristics h2 which is more informed than h2 (in that forall nodes n, h2(n) >= h1(n)), we can only show that the "interior f-contour" nodes expanded by search with h1 are also expanded by h2. 

Specifically, consider a node n' such that f2(n') = g(n') + h2(n') <  f*   (where f*, the optimal cost of the goal node, is the same for both heuristics). So, n' will clearly be expanded by the search with h2. Since h1 <= h2, clearly  f1(n') is also less than f*, and so search with h1 also expands node n'. This shows that the number of nodes on the interior f-contours for h1 can not be fewer than the nodes on the interior f-contours for h1. (An interior f-contour is the set of equi-f-value nodes with  f-values less than f*)

The tricky part is that this subsumption doesn't necessrily hold for nodes that are on the "f* contour"--i.e. nodes that have
f1 or f2 equal to f*. Based on the tie-breaking strategy, a subset of these nodes will likely be expanded before the search terminates. If the subset expanded by h2 is more than that expanded by h1, search with h2 can do more expansions even though it is more informed.

See if you can think of possible reasons why this could happen. [hint: there is a slide in the informed search lecture--with annotation "advanced"--that gives the insights needed, if you are having trouble..]

Rao

Re: Anonymous feedback opportunity

At the risk of stating the obvious, note that you have to click the submit vote for your input

to be recorded.

rao

On Tue, Feb 21, 2012 at 9:38 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

Folks:

 Here is a mr. poll link where you can give anonymous text-based feedback on the course. 

<Removed from Blog; see email for link>

I encourage you to participate in it.

Rao

Anonymous feedback opportunity

Folks:

 Here is a mr. poll link where you can give anonymous text-based feedback on the course. 

<Link Removed from blog; see email for the link>

I encourage you to participate in it.

Rao

Exam solutions video (just 46MB!) and doc available online

Before we forget all about the exam, I thought I should post the solutions.  So I did.

There is both a khan academy style 41min recording of me developing the solutions (just

46MB--very easy download), and the pdf file that got developed that way.

Note that I only guarantee the completeness of the video--the doc is like trace left on the

board..

I highly encourage you to view the video.

Rao

ps: ..and you thought Bill Gates is busier than me! Tsk. Tsk. The guy is retired, you know...

Test 1 grades..

I graded test 1. I will return them today in class. 

Here are the statistics:

471 section

 Avg    32.73

Stdev  17.37

Max     62

Min      4.5

598 section

Avg  47.6

Stdev 12.3

Max   64

Min    23.5

Rao

office hours change for today: will be available 2:30--3:30

Instead of 1-2, I will be available 2:30--3:30 for office hours today

rao

Homework Grading Rubric

The maximum possible points are 76. 
The maximum homework scores are 65 and 64.  After that are a handful of mid-50s.  The median score is something like 43. 
The mean is 39ish, the mean excluding the lowest scores is 41ish.  The vast majority of the class scored in the mid 30s to mid 40s. 
(The minimums are several 0s, of course, and among actual assignments are several sub-20 scores such as 6 and 12, as I recall.)

So a mid 40 is something like a B or B+.  Low 50s and higher is definitely an A; I think there are about 7 such scores.

--

As I'm sure you can tell I began the grading in `reviewer' mode, i.e., how I would review a submission to an international conference or journal on artificial intelligence.
This is a mistake which was fortunately halted before total catastrophe ensued.  Please
don't take my comments personally, indeed, feel free to entirely ignore them.  Note that the grading is consistent and fair, at least, as well as can be expected
from a human being.  In particular the drastic change in the level of commentary between the first and second halves means little besides a drastic change
in the level of commentary --- the grading itself was just as `harsh'. 

It is worth noting that at least one (if not several) student(s) got a perfect (or above perfect) score on any given question (not the same students each time).
Also, the entire class average would likely go up by 10 or even 15 points had all the assignments been in fact complete.

The following is a break-down of how the final judgments were converted into points.  This varies a little from question to question,
but the general idea is that correctness is worth a point and justification is worth a point, and that each question no matter 
how large or how small was worth 2.  Except question 1, where its 8 sub-questions are only worth 1 each.

--

All rounding is rounding up; all sub-scores are truncated to the maximum possible where scoring over maximum was possible.

Question 1: 8 possible points. 
  0/3 of a point for no example,
  1/3 of a point for a flawed example,
  2/3 of a point for a dubious example,
  3/3 of a point for a fine example.

For any agent whatsoever in any domain, say X, a fine example consists of:
  X with faulty/good sensors, with/without multiple agents, and with faulty/good effectors.

Other idioms are more appropriate for certain domains.  For driving, for example, one might say:
  Driving (not) in a blizzard, (not) on a closed course, and (not) drunk.

For poker:
  Poker with(out) Extra-sensory perception, with(out) opponent's families as hostages, and drunk/sober.  (Or dealer/not-dealer.)



Question 2: 6 possible points.
  1/4 of a point for a incorrect answer with faulty explanation.
  2/4 of a point for a correct answer with faulty explanation, or, for an incorrect answer with a good explanation.
  3/4 of a point for a correct answer with a dubious explanation, and in some cases perhaps even for an incorrect answer (with fantastic explanation).
  4/4 of a point for a correct answer with correct explanation.

The correct answers are that accessibility and determinism depend on the agent design, respectively due to sensor and motor/effector quality, while staticness is an environmental
parameter usually independent from agent design.  (But there are exceptions.)



Questions 3 through 6: 22 possible points. 
These are summed and rounded in one group.  There are three possible marks in three possible positions:
  A leading +/- indicates that the answer provided was deemed technically correct/incorrect.  (X for not committing to a single clear answer.)
  The following +/- indicates that the explanation provided was deemed adequate/inadequate. (X for not giving any explanation at all, or in some cases, an explanation worse than nothing at all.)
Each of those is worth a point.
  Optionally a trailing +/- is a positive or negative half-point, modifying the score for the explanation. 
All combinations are possible.  In particular one could give an interesting explanation for a wrong answer and receive as much as 1.5 out of 2 points.
It is also possible to score 2.5 out of 2 points, which is the point of summing all of the questions together before rounding and truncating to the maximum score.
As the score "- - -" would be worse than no answer, these are first altered to "- - X", removing the negative modifier.
Most of the time the trailing modifiers cancel out or nearly so.

In theory one could have scored 2.5 points on questions 3 and 4, 10 points on 5.1 and 5.2, and another 2.5 points on question 6, which I may have neglected to truncate to the maximum score
which should be possible on the entire set: 2+2+8+8+2 = 22.  If you have a sub-score above 22 on that part, you might want to avoid bringing my attention to it ;).



Question 7: 8 points total. 
7.1 used the scale above.  The correct answer to 7.1 is of course DFS, because of its vastly superior space-complexity and no loss of quality under these ideal-for-DFS conditions.

The other 3 parts were marked using +/- letter grades with the following meaning, as I recall:
 A+ = 2.5
 A- to A = 2
 B+ = 1.5
 C+ to B = 1
 D to C = 0.5
 X = 0.

The order these are listed in is 7.2.1, 7.2.3, and 7.2.2.  A+ on 7.2 was for drawing the tree to depth 3 proper (and getting everything else right).

The correct answers to 7.2.1 and .3 are virtually the same; a barren sub-tree is effectively a special case of a highly non-uniform goal distribution at the leaves.  The grading was
looking for non-uniformity as the reason to prefer iterative-broadening over DFS in 7.2.1, and the grading was looking for an appropriate connection to barrenness being made in
the answer to 7.2.3.  Many answers were extremely difficult to parse or understand.  Using specific examples greatly benefited those students who did so. 
It was also a good observation to note that: if the left-most goal is halfway through the leaves in such a way that it is found at the cutoff b'=b/2 then IBDFS has a huge (astronomical for, say, b=100)
advantage.  Note the solution guide suggests that the 3.1 etc. nodes are good for IBDFS --- this is incorrect.  b'=b is the worst-case for IBDFS.  For b=3 and d=3 there are actually
only 4 possible leftmost goals for which IBDFS would perform better than DFS, and so, `on average' it likely would not perform better except of course that we have little idea what
`on average' means except that it *isn't* a straight average over the leaves of the tree treating each as having equal likelihood of being the leftmost goal.




Questions 8-12: 32 possible points.
2 points per question mark plus 2 more for "Is the manhattan distance heuristic admissible." which I think was missing a question mark.
+ means full credit, i.e., 2.
- means partial credit, i.e., 1.
x means no credit.

These were all pretty straightforward.



-Will


Further notes on what was considered correct/incorrect:

Question 8 (2 points): There were quite a few similar strategies for attempting to prove question 8 using simpler arguments than the standard of "consider any other path at the time A* returns". 
Virtually no one got points for this question.

Question 3 (2 points): In order of difficulty: partial-accessibility, complete inaccessibility, full accessibility.  With partial-accessibility one has the option of designing the agent to pre-plan for contingencies, or re-plan when
the unexpected happens.  With no sensors, neither is possible, so neither need be implemented.  Not implementing is of course easier than implementing.

Question 4 (2 points): Detail is not always helpful.  Up to a point a better model can help an agent improve its performance --- but a model of the entire universe at nanometer resolution is too far.  There are two points: the computational burden
of too much detail, also, the more precise your model the more likely it is that it is inaccurate, perhaps gravely so.  (In learning theory this is called *overfitting*, and deliberate simplification of a model to avoid such is called regularization. In planning
one would say abstraction rather than regularization.)

Question 5.2:  There was a lot of confusion on this question.  One point in particular is that the solution guide uses a very strict notion of what it means
to achieve a goal -- ruling out stochastic achievement almost as a matter of definition.  It also isn't very clear that A2 isn't meant to be doubly handicapped.

Question 6 (2 points):  IDDFS is a complete algorithm and so cannot possibly be performing infinitely more work than DFS --- the conclusion doesn't make sense. 
The actual ratio is the ratio between the sum of the integers from 1 to D (which is D choose 2) by just D, which is (D+1)/2.  (Where D=d+1, the number of vertices in the single path that is the entire search tree.)

EC (4 points): The ratio (b+1)/(b-1) stems from an average-case analysis, which involves much more annoying algebra than the far easier worst-case analysis. 
I think that everyone who made a serious attempt got at least 1 point?  Elegant psuedo-proofs got 2.

Re: [CSE471] Instructions for your Project-1 CODE

Hello:

We got one question yesterday as to whether you can submit your project both today and the next Tuesday. If the announcement was not clear enough, the answer is that please submit your project only one time. If you have already submitted (which I saw some on the blackboard), you are done.

Best,

Tuan

On 13 February 2012 12:01, Tuan A. Nguyen <tanguye1@asu.edu> wrote:

Hi all:

I have created a link on Blackboard so that you can submit your Project-1 *code* (your report should be submitted before class, and in hard-copy). Please name your file as <first_name>_<last_name>.lisp.

And as a reminder: the "early" deadline is 4:30pm, 2/14; and the extended one is exactly one week later.

Please let me know if you have any question.

Thanks,

Tuan

[CSE471] Instructions for your Project-1 CODE

Hi all:

I have created a link on Blackboard so that you can submit your Project-1 *code* (your report should be submitted before class, and in hard-copy). Please name your file as <first_name>_<last_name>.lisp.

And as a reminder: the "early" deadline is 4:30pm, 2/14; and the extended one is exactly one week later.

Please let me know if you have any question.

Thanks,

Tuan

Readings for this week: Chapter 7 (Logical Agents)

Folks

 As you know if you attended the planning graph class and/or viewed the video afterwards, our next topic is

knowledge representation--and in particular representations based on logic. Please read Chapter 7 (3rd ed--or equivalent

in earlier editions).

Rao

One week extension on Project 1; due 2/21

Dear all:

 In view of the continuing questions about project 1,  we will extend the deadline for submission by one week (i.e., due 2/21).

I realize that dead-line extensions like this can be seen to be unfair to those who actually got their lives structured to get the project done by the original deadline.  In view of this, we will give a 5% extra credit for anyone who turns in the completed project tomorrow (note that this will be 5% of the grade you get on the project--so turning in an empty project will only get you 0 extra credit). 

To those of you who are just about done, you might consider using the additional time to improve your analysis and/or do additional extra-credit tasks.

regards

Rao

[CSE471] Instructions for your project-1 report

Hello all:

I hope you are doing well on your project 1, which will be due on the lovely Valentine's Day.

You will need to submit both the code and the hard copy of your report. I will have to send another email on how you will submit your code, but for your report please make sure that it includes:

(1) the commented code, 

(2) the sample runs for input cases, 

(3) the statistics as required in the project description, and 

(4) your analysis based on the results.

Although there will not be any specific point on what to address in your report, it should at least show that you understand the search algorithms and the differences between them, and give us a feeling that your code is actually working (which will also be tested). Here are some guidelines:

- What are your observations on the performance of the search strategies (both individually and in comparing to each other), in terms of running time, space, completeness, the admissibility/informness of heuristics etc. Do they actually match the theories you learned in the class?

- Displaying the results on graphs, especially for those comparing different approaches, would be very helpful.

- Some runs to show that your code is correct (part of the trajectory, for example).

- Any suggestion on how to improve the algorithms, data structures etc.

- Write your report as clearly as possible (for the code, fonts like courier seem nicer, and you can reduce the font size and space between lines as well).

Also, please print your report in the 2-sided format.

Thanks,

Tuan