Wednesday, November 28, 2007

An optional question on learning has been added to homework 5

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

*Important* Headsup: Interactive review in the next class

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

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

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

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

Tuesday, November 27, 2007

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

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

-------
Amy Sever says:

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

----------

Monday, November 26, 2007

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

Qn 4. added below.


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

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


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

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

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

[[extra-curricular]]

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


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

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

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

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

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

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

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

measures towards this.

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

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


Yours illuminatingly... ;-)
Rao

Epilogue/can skip:

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

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


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

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

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

   "Induction  extends your expectation, not your experience"
 

Project 4 late submission requests..

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

Sunday, November 25, 2007

[cse 471] Instructions for project-4 submission

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

Wednesday, November 21, 2007

Information regarding CSE574 being offered next semester..

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

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

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

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

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

Happy thanksgiving!
Rao


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





Monday, November 19, 2007

[Thinking Cap] MDPs etc...

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

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

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


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

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

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

That is all for now...


Rao


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

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

Sunday, November 18, 2007

(Thinking cap) Complexity of planning

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

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

Solutions to Homework 4 posted..


Thursday, November 15, 2007

Thinking Cap questions (comment on the blog)



Here are some thinking cap questions.

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

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

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



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



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

Comments, on the blog, welcome.

cheers
Rao


     

Wednesday, November 14, 2007

Project-2 grading scheme and statistics

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

Monday, November 12, 2007

A blind carbon copy

This is a blind carbon copy.

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

Folks:

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

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

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


Rao

Reading for the next class..

The readings for the next class(es) are:

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

followed by

Adversarial Search  (6.1--6.4)


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

rao

Saturday, November 10, 2007

Video recording of the makeup class is on google videos

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

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

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


cheers
Rao



Friday, November 9, 2007

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

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

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

Rao

Wednesday, November 7, 2007

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

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

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

regards
Rao

Tuesday, November 6, 2007

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



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

Folks:

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

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

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


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

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

cheers
Rao

Fwd: Link to the slides and audio

Folks:

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

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

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


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

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

cheers
Rao

Sunday, November 4, 2007

Re: Regarding Project 3

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

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

thanks
 
with regards
Nishant Singh

Thursday, November 1, 2007

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

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

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

The 6+ page conference paper

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

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

Rao

Midterm solutions are available..

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


FYI
Rao