Thursday, May 28, 2009

Fulton course/instructor evaluations

Dear all:

Hope you are starting to have a good break and all your mental bruises are slowly healing.

I just received the results of the  teaching evaluations that you folks filled and enjoyed reading them.

Thanks to all of you who took time to fill the evaluations!

It is my somewhat quixotic custom to allow access to the evaluations to the class students for a limited time. It might give you a feel as to how your individual
views stacked up with the rest of the class (you know--sorrow desires company and all that).

In keeping with it, here are links to the full evaluations--warts and all--in case you are interested:

http://rakaposhi.eas.asu.edu/cse471/cse471-s09-ug.htm   (471 section)

http://rakaposhi.eas.asu.edu/cse471/cse471-s09-g.htm      (598 section)

Regarding the comments about the difficulty level of the course, the following is the link for a comparable course taught by the textbook author http://www.eecs.berkeley.edu/~russell/classes/cs188/f05/ 

So look at the bright side--you got almost all that, with a lower tuition, fewer projects, easier exams, *and*  a suaver accent! ;-)

cheers
Rao





Monday, May 18, 2009

sayanora...

Folks:

 I agonized for some three days and  just submitted your grades; you should be able to see them on the registrar's site.

 It has been fun teaching you folks; I hope to see some of you in other classes. Feel free to drop by if I can be of any help.

Good luck with your degree programs (or real life, if you were so unlucky as to graduate already :).
Hope you get to recall and use at least some of the things we talked about this semester
down the line somewhere.

cheers
Rao


Sunday, May 17, 2009

Go Huygens! A new world record in a difficult game for computers

From the article:
At the Taiwan Open 2009, held in Taiwan from Feb. 10-13, the Dutch national supercomputer Huygens, which is located at SARA Computing and Networking Services in Amsterdam, defeated two human Go professionals in an official match.
Here's more:
http://www.sciencecodex.com/french_software_and_dutch_national_supercomputer_huygens_establish_a_new_world_record_in_go_0

specimen solutions for the final..

In case you are interested, here is a link to specimen solutions for the final (note that these are solutions written by the student
scoring the highest, but not perfect, on the final).

http://rakaposhi.eas.asu.edu/cse471/s09-final-soln.pdf

Rao

Saturday, May 16, 2009

Full spreadsheet of the final gradebook

Someone wanted to have one last look at the final grade book I am operating with. Here it is...

Rao

Emacs!

Final cumulatives (with the final exam scores thrown in)

Folks:

 Here are the final cumulatives (with final exam scores thrown in). The highest for final in UG is 102 and in grad is 104 (out of 110).
The averages are 64 and 84 respectively.

The top students in CSE471 and the CSE598 categories are both guaranteed A+ grades (assuming their photo-finish holds up ;-)).
They both are welcome to offer me (non-binding) advice on where to put grade cutoffs for the rest of the class...

As for the rest, they shall find out their letter grades from the registrar come Tuesday.


regards
Rao

Emacs!

Thursday, May 14, 2009

a brain aphorism based on the final..

There is a quote I used to like, and it goes like this:
 
 "If our brains are so simple that we can understand them,
    we will be so simple that we can't"

(Of course, I don't believe it, but I like the sound of it ;-)

Anyways, I was thinking about it, as I am grading the final and several of you wrote
"True" for the question which says that an agent has the best chance of success when
all the variables are independent.. yes you can do reasoning fast, but to what end? You
can't change a thing in the world...


----------

Another short-answer question that only a few people got right is the last one. The point there is that
if you add a random number to the h value, then you are likely to make the h-value of each node unique.
Which means there can be as many distinct f-values as there are nodes.  This is a death-knell of IDA*


Rao

Saturday, May 9, 2009

Re: Regarding graph planning in Homework 5

First of all, since I discussed mutual exclusion propagation only briefly in the class, you are not responsible for that part.

Since you asked however, just because two actions are mutex doesn't mean that  their effects are mutex--since after all the effects may also have been given by other actions.

Consider for example a situation where p is given by m different actions, and q is given by n different actions.

In order for p and q to be mutex, it must be the case that every pair of actions in the cartesian product must be
mutex--ie there must be m*n mutexes.  If there exists even one pair--say ai giving p and bk giving q such that
ai and bk are not mutex, then p and q are not mutex.

[Suppose you started with the belief that you shouldn't hit people because god might punish you. If you then went on to become an atheist, it doesn't necessarily mean that you should now believe that hitting people is fine. You may have found other reasons why hitting people is not reasonable.]

[In contrast, if *any* pair of preconditions of two actions are mutex, then the actions themselves are mutex.
I.e. if action a has m precods and action b has n preconds, if any of the m*n precondition pairs are mutex, then the action a and b are mutex. ]

Rao


On Sat, May 9, 2009 at 3:05 PM, Sidharth Gupta <sgupta47@asu.edu> wrote:
The mutexes shown between variables at level 2  in the problem in planning graph for homework 5 solutions dont quite seem right.... Shouldnt there be a mutexes between all the pairs of variables whose actions were also having a mutex...? Many seem to be missing like between R and S whose actions o1 and o2 are also in mutex?

Regards
Sidharth Gupta



(yet another mail about) Undergraduate research opportunity...

Folks:

 I just learned that we will be getting a National Science Foundation grant to support some work on stochastic planning.
This is based on the ideas in the  paper  http://rakaposhi.eas.asu.edu/ffhop.pdf

This grant also has a "Research Experiences for Undergraduates" component (through which UG students can take part in research projects, and also get a modest stipend of about 4K/semester ).

If you are interested, let me know. This can start as early as this summer.

Rao

Friday, May 8, 2009

Final pep-rally.. (and anxiety amelioration)

Some of you have started wondering whether it makes sense to plan to stand in the interminable security checks in your nice polyester cookers (err graduation gowns) and get into the Obammencement given your worrisome cumulatives in this class.

My suggestion is that you quit worrying and  focus on the final and do that well.

As I said after the mid-term, I am much more interested in torturing (I mean educating)  you during the semester than in haunting your GPA after it.
I have  a lot of respect for students who had the perseverance to stay with what people tell me is a challenging course.

Good luck
Rao
----------
  "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"




Cumulatives for everything other than participation and final..

Folks:

 Here are the cumulatives for 75% of your grade (the participation credit and the final exam marks are missing).
Note that some of you still have project 4 points missing--this is because TA had contacted you for your source code and
has to complete grading after that.

Emacs!

Re: Final exam question

Yes. Sorry for the typo.

Sent from my iPod

On May 8, 2009, at 2:38 PM, cameronlarue@gmail.com wrote:

> On Qn VII (1), Given a database D and a fact f, if D does not entail
> p, then D entails ~p.
>
> Is fact f supposed to be fact p?
>
> Thanks,
> Cameron

Fwd: CSE Undergraduate Research Scholarship Fall 2009 - deadline today!

Let me know if any of you UG students are interested in being nominated.

Rao

---------- Forwarded message ----------
From: Amy Sever <Amy.Sever@asu.edu>
Date: Fri, May 8, 2009 at 7:55 AM
Subject: CSE Undergraduate Research Scholarship Fall 2009 - deadline today!
To: CSEFaculty@asu.edu


CSE Faculty,

 

I'm writing to remind you that today is the deadline to nominate a student or students for the CSE Undergraduate Research Scholarship for Fall 2009.  See details and get the application form at: http://sci.asu.edu/undergraduate/research.php.

 

Please consider supporting one of our top students!

 

Thanks,

 

 

Amy Sever

Assistant Director, Academic Services

School of Computing and Informatics

480-965-3199

http://sci.asu.edu   

 

 

 

 

 

From: Amy Sever
Sent: Tuesday, April 28, 2009 1:51 PM
To: 'CSEFaculty@asu.edu'
Cc: Sandra Hoeffer
Subject: CSE Undergraduate Research Scholarship - nominate a student for Fall 2009!

 

CSE Faculty,

It is time to nominate exceptional students for the CSE Undergraduate Research Scholarship! This program supports strong academic performance among our undergraduate students and to encourage interest in graduate studies. Please review the following guidelines.

  1. Faculty must initiate all applications and turn them into department. These applications will not be accepted from students. However, if students find any potential opportunities on this site or elsewhere, they can come to you to initiate the application.
  2. Faculty overseeing research must commit $1,000 to student support.
  3. Students can work a maximum of ten hours per week in lab.
  4. The department will award an additional $1,000 to the student based on a competitive process.
  5. Monies will be awarded on a semester basis.
  6. All applications must be received by May 8th for the Fall 2009 term.
  7. All students must meet the qualifications listed below.

Student Qualifications:

  • Grade Point Average of 3.25 or above
  • Must be registered for at least 12 credit hours in the Fall 2009 term
  • Junior/Senior level in program
  • Every student receiving this award is expected to produce a poster at the end of the semester in which they received financial support through the FURI Symposium. Instructions for completing these posters will be provided.

The application can be downloaded at: http://sci.asu.edu/undergraduate/research.php.  Please share as much information as possible about the student you are nominating, as there are a limited number of awards and the selection process is competitive!

Please turn in the application for the Fall 2009 semester to me in the SCI Advising Center, BYENG 208, by May 8th. I've attached a query of students who are juniors and seniors with a 3.25 GPA or higher. Perhaps one of the names is of a promising student from one of your classes!  Please contact me if you know of a student that is not on this list that you believe is a junior or senior in the program.

Here are other ways students can engage in research:

1)      Mentor a student in Fulton Undergraduate Research Initiative (FURI).  Application deadline for Fall 2009 is May 15th.   This is a student-initiated process. See http://www.fulton.asu.edu/fulton/departments/furi/ for more information.

2)      Supervise a student in CSE 499 Independent Study: For CS and CSE seniors with a 3.0 GPA or higher in their major area. Form is at http://sci.asu.edu/forms/undergraduate.php.

3)      Supervise an honors student in CSE 492 Research and CSE 493 Thesis.  Form is at http://sci.asu.edu/forms/undergraduate.php.

4)      Post any available research positions for undergraduates (and graduate students) at: http://sci.asu.edu/employee/studentjobposting.php

Thanks for your help in supporting our students to engage in undergraduate research.

Sincerely,

 

Amy Sever

Assistant Director, Academic Services

480-965-3199

http://sci.asu.edu

 

 

 

Amy Sever

Assistant Director, Academic Services

School of Computing and Informatics

480-965-3199

http://sci.asu.edu 

 

 

 


What is the difference....?

A nice FAQ on the differences between functional, logic and procedural languages....

1. What makes a language functional, logic programming or procedural ?


A procedural or imperative language focuses on telling the computer
what to do, step by step. These are descended from Turing machines
and assembly language. You knew a lot about them before this course.

A logic programming language focuses on computation as constructive
proofs, i.e., proving a term that says that two employees or three
numbers are in a particular relationship. Typically unification and
backtracking are used to help efficiently construct the proofs, but
there are other possible strategies. These languages are descended
from Prolog, and you have been learning about them.

A functional language focuses on computation as the evaluation of
mathematical functions. These are descended from the lambda calculus
and Lisp. I'll say a little more below in answer to your questions.

In a purely functional language, a program simply defines a bunch of
functions, in the mathematical sense of "function." The return value
of a function depends only on its arguments; the function has no side
effects and is not sensitive to side effects, so it returns the same
value every time it's called.

Of course, you can program in this functional style in other
languages, too. But programming in a actual functional language
forces you to learn this style. :-) More important, compilers for a
functional language can take advantage of the guaranteed lack of side
effects to introduce optimizations -- including memoization and lazy
evaluation.

In a really pure functional language, the only thing that happens
within a function is to call other functions -- e.g., you would define
f(x,y) as g(h(x),f(x,minus(y,1))). This is just putting f,g,h, and
minus together by wiring the outputs of some functions into the inputs
of others. Note that minus is presumably a built-in function. So are
conditionals: if(condition, then-value, else-value).

Similarly, in a really pure logic language, the only thing that a
query can do is to combine other queries by unifying their arguments,
which is similar to the way that a function call in a functional
language combines other function calls by wiring their inputs and
outputs together. A query may also have nondeterminism, e.g., there
may be a choice of several ways to answer it (e.g., several clauses
with the same head). This is why constructing a proof may involve
backtracking.

So in both pure functional and pure logic programming languages, there
is no mechanism for modifying values. This rules out side effects,
but it actualy rules out more than that, because there's not even a
way to modify values privately within the definition of a function.
Objects can't be modified once they're created. Indeed, there is no
way even to change the value of a variable! (You can introduce a
LOCAL variable as a temporary name for something, but once you've
introduced it, its value will never change (except perhaps for being
specialized through unification), and it goes away once you leave the
scope where the variable was introduced.)

As an example, you can't write loops since you can't change the loop
variable. You use recursion instead. This introduces new local
variables on every recursive call rather than changing the value of
your loop variable. The compiler may secretly turn the recursive
calls back into loops where it can, of course.

As another example, you can't write a destructive function to append
two lists A and B, i.e., changing the last pointer of A to point to
the start of B, because this would be a side effect. You have to
write a function that leaves A and B intact and returns a new list C,
which is basically the list that you would get if you made a copy of A
and changed the last pointer of the copy to point to the start of B.
(There is no need to copy B.)

As another example, you can't easily memoize the result of a function,
because it would be a side effect to store the result in an global
array that would be accessible to future calls of that function. To
avoid handling this as a side effect, you would have to pass the array
as an argument to the function, and the function would return a
modified array that you could pass to the next call of the function.
Some functional or logic languages do have memoization built in,
however -- the lack of side effects means that the memo will remain
valid.

Many functional and logic languages are not pure, though -- they are
extended with some ability to have side effects. In Prolog, there are
"assert" and "retract" predicates which actually modify the program as
it's running (e.g., adding new facts to the database) if you query
them. The original functional language Lisp allows modification fo
both local and global variables. Several recently developed
functional languages like OCaml and Haskell have more principled or
careful ways to let side effects into the language in restricted
circumstances.

Is it ability to use functions as arguments to other functions ?


No, but this is indeed a feature commonly found in functional
languages. That is because the feature is useful, and because those
languages are mainly descended from the lambda calculus, in which
functions are the only objects in the language.

A language "has first-class functions" if functions can be treated
like any other object, e.g.,
* as the argument to another function
* as the return value of another function
* as the value of a variable
* as fair game for type checking (i.e., if there is a strong type
system, then it must distinguish different types of functions, e.g.,
by their input and output types)

A "higher-order function" is a particular function that has other
functions as arguments or return values. A language that has
first-class functions obviously allows higher-order functions.

If it is then what is python ?


Python is a procedural, object-oriented language that has first-class
functions, recursion, and other things that make it easy to program in
a functional style if you choose not to use any side effects.

2. How important is the concept of immutability to any functional
programming language ?


Immutability means that objects can be created but not subsequently
modified. In pure functional languages, everything is immutable, as
noted above.

3. How is functional programming different from logic programming ?


Logic programming usually has nondeterminism (backtracking) and
unification as built-in features. Few functional programming
languages have this.

Logic programming doesn't have return values; it describes relations
like times(A,B,C) (which is either provable or not) rather than
functions like times(A,B).

Logic programming generally does *not* have higher-order functions,
since it doesn't have functions. But there are logic programming
languages that do, like lambda-Prolog.

Thursday, May 7, 2009

*FINAL EXAM RELEASED**

Folks:

 Here is the URL for the final exam. Please read the instructions on the front page carefully. You can return the exam to either the front office
or push it under my door.

Please note that giving the fianl exam as a  take-home is a mark of trust I have in your academic honesty. Please don't give me any reason to regret it.

regards
Rao


Final (Word document) http://rakaposhi.eas.asu.edu/cse471/s09-final-jm.doc
(pdf form)    http://rakaposhi.eas.asu.edu/cse471/s09-final-jm.pdf


Wednesday, May 6, 2009

My availability this week

Folks:

 I should be in my office much of the day tomorrow (Thursday) as well as before noon on Friday.  If you have questions related to the course and exam
feel free to stop by. If you want to make sure I am in my office before you come, call 965-0113 to confirm.

rao

Solutions for the final homework posted online

FYI

Chess game showing which moves the computer is considering

I stumbled across this chess game this morning
http://transition.turbulence.org/spotlight/thinking/chess.html
Every time you make a move, it shows you what moves the program is considering. The brighter the lines are, the better the move.

On the "About" page, they say this:

The chess engine we built is simple and uses only basic algorithms from the 50s (alpha-beta pruning and quiescence search). The program's unconventional initial moves may raise eyebrows among experts: we did not give it an "opening book" of standard lines since we wanted it to think through every position.

Although I wouldn't recommend using this if you actually wanted to complete an entire game in less than a couple of hours, it's pretty cool seeing all of the moves being analyzed in real time.

Tuesday, May 5, 2009

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

[[extra-curricular]]

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


We talked a lot about the role of biases in making learning feasible. When the kid jumps to the conclusion that the
whole big thing his mommy is pointing to and crying "BUS" must be the bus, or when you assume that the rabbit-like thing
that jumped into your line of vision, as you stood in the African savannah with a masai irrationally screaming "GAVAGAI" in your ears, must
be gavagai, you seemed to be making both computationally efficient and correct generalizations.

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, after the wisdom of this class, should we really wear complaints of biases in our behavior
as badges of honor?

Hmm..  Where does this leave us vis-a-vis
stereotypes and racial profiles--of the type
 "all Antarciticans are untrustworthy" or "all
Krakatoans are smelly" variety.

Afterall, they too are instances of
our mind's highly useful ability to induce patterns from limited
samples. How can we legitimately ask our mind not to do the thing it is so darned good at doing?

So, what, if any, is the best computational argument against stereotyping?

One normal argument is that the stereotype may actually be wrong--in
other words, 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 does incur 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 the appearance of  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 staring 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...





Decision regarding final being a take-home or in-class is made (democratically) today in class...

...show up and think about which option you would want.

rao

Heads up: Participation sheet that you will be asked to fill in the class today

Folks:

 Each of you will be asked to fill in the participation sheet below in the class today. Please get ready with the relevant numbers:

thanks
rao
---------------

CSE 471/598   Participation Evaluation Sheet

 

 

As you recall, the participation credit for this class is measured in terms of attendance, attentiveness and active participation (either through questions in class or via comments on the blog). Please help me evaluate your participation by providing answers to the following.

 

You will have to return this to me, in hard copy, in the last class.

 

 

Attendance:

 

 

How many regular classes (i.e., not counting the one makeup class), did you miss:

 

 

(Please look at http://rakaposhi.eas.asu.edu/cse471 if you have trouble remembering which classes, if any, you missed)

 

 

How many of the above classes did you miss with prior notification:

 

Class participation:

 

Approximately how many times did you ask a question (or respond to one asked):

 

 

 

Blog participation:

 

 

How many times did you post on the blog (not counting times you posted questions asking for clarifications on the homework)?

 

 

 

(I know quantity does not equal quality; but you can count on me to take quality into account ;-). It is the quantity I want help with.)


Monday, May 4, 2009

My digression has a digression--a change-of-heart re: "Gang Leader for a Day"

Paraphrasing the woman in Brazil (who says "my complications started having complications"), I feel compelled to make
a digression about a digression.

I mentioned the book "Gang Leader For a Day" in passing last class, and put it in a positive light. Well, I was half-way through at that time.
Over the weekend, I read the rest of the book and was quite disturbed by several things.

I then looked around on the internet for critical reviews, and found the following which summarizes some of my concerns.

http://tenured-radical.blogspot.com/2009/04/puff-magic-sociologist-review-of-sudhir.html

Anyways, just on the off chance that I may have convinced any of you to read the book, I want to take it back. You are
welcome to read it of course, just don't blame me for it.

This *does not* change the point about gamma=0; just the generally positive tone of my description of the book.
Like Columbus, the author seems to take his own (re)discovery of known ideas a tad too seriously.

I know you didn't sign-up for this course to be swayed by  my biases, but I am afraid you might nonetheless, if I am any good at this
teaching thing. So, I felt compelled to send this note.

We now return you to the regularly scheduled homework.

Rao



The learning question in hw 4 is not required (as we have not covered the material yet in the class)


Sunday, May 3, 2009

Homework 4 Part 5f-5i

I don't believe we discussed neural networks yet. Are parts 5f-5i still required for this homework?

Reminder: Mandatory blog posting of homework 4 question

Just a reminder that the answer to the following homework 4 question must be posted onto the blog by Tuesday's class.

rao


[Mandatory] [Answer to this question *must* also be posted on the class blog as a comment to my post (see the link below)]. List upto five non-trivial ideas you were able to appreciate during the course of this semester. (These cannot be "I thought Bayes Nets were Groovy" variety--and have to include a sentence of justification). (Here is the link to the blog comment section: http://cse471-s09.blogspot.com/2009/04/interactive-review-qn-added-to-homework.html )

(im)Possibility of an *optional* extra class on "Learning" [Monday 10:30--11:45, BY 210] Free Food Event. [RSVP]

Folks:

Just to let you know that there will not be an extra class tomorrow (Monday).

 Apparently the recession isn't hitting the ASU students all that hard. Even offers of free food are able to
rustle-up only a couple of students to warm the seats of an extra class.

See you Tuesday.

Rao


On Thu, Apr 30, 2009 at 3:45 PM, Subbarao Kambhampati <rao@asu.edu> wrote:
Folks:

 I felt a little queasy that I may not have the full opportunity to sufficiently brainwash you with my view of learning.

So, I am offering to run a completely optional extra class on Monday 5/4 morning in BY 210 (10:30--11:45AM) *if* there is
sufficient interest.

As a clarification, nothing I discuss in this class would be included in the final exam, so if you skip it, you won't be in anyway
disadvantaged with respect to your course grade.

Also, the Tuesday regular class will not depend on what is discussed on Monday; it will take off from where we left today.

What I want to do is give a bigger picture about learning, that I didn't get to do because of time constraints.

*if* you are interested and will be able to attend, let me know by email.*************

If I get sufficient interest, I will confirm by Sunday if the meeting is going to be held.

Since I cannot use sticks, I will dangle the carrot of free food if you show up ;-)


cheers
Rao


Saturday, May 2, 2009

Fwd: [cse471/598 Intro to AI Spring 2009 Blog] Homework 5 alpha-beta

Yes--please show where the cutoffs occurs and what the backedup value and corresponding move is (as was shown in the examples done in the class)

rao



---------- Forwarded message ----------
From: Cameron L <cameronlarue@gmail.com>
Date: Sat, May 2, 2009 at 5:05 PM
Subject: [cse471/598 Intro to AI Spring 2009 Blog] Homework 5 alpha-beta
To: subbarao2z2@gmail.com


The power point slide doesn't really have any instructions. I'm assuming just show which nodes get pruned and the final value at A. But as we're traversing the tree, do we know that all values on a given level are ordered from least to most as we go left to right?

--
Posted By Cameron L to cse471/598 Intro to AI Spring 2009 Blog at 5/02/2009 05:01:00 PM

Homework 5 alpha-beta

The power point slide doesn't really have any instructions. I'm assuming just show which nodes get pruned and the final value at A. But as we're traversing the tree, do we know that all values on a given level are ordered from least to most as we go left to right?

Homework 5 MDP 1c

In question 1c of the MDP section of the homework what is meant by synchronous? Does that mean that state 2 depends on the result of state 1, or does it mean that state 1 and state 2 should be evaluated independently.

Friday, May 1, 2009

Is DeepBlue intelligent? Some extra-curricular philosophy

(Folks--
This is a mail I had sent to the class in Fall 2003. As they say
about re-runs, if you haven't seen it, it is *new* for you ;-)

Rao

==============
Here is an article that discusses the question whether Deep Blue--the
Kasparov-beating chess program--that we are discussing in the class--is
"intelligent".

I send this to you because this is pretty much my bias/position too on
this issue (plus I like Drew McDermott's style--if you ever get a
chance, you should read his paper "Artificial Intelligence meets
Natural Stupidity"--which can be found at
http://rakaposhi.eas.asu.edu/mcdermott.pdf -- and was written in the
early days of AI (~1978) to criticize researchers' tendency to
self-delude... (which is also related to the AI/Thermos Flask
joke--ask me about it sometime).

Bottom line: Introspection is a lousy way to theorize about thinking.

See the end for a pointer to a different perspective

Rao
[9/26/2003]
]]


How Intelligent is Deep Blue?

Drew McDermott

http://cs-www.cs.yale.edu/homes/dvm/

[This is the original, long version of an article that appeared in the
May 14, 1997 New York Times with more flamboyant title.]

IBM's chess computer, Deep Blue, has shocked the world of chess by
defeating Garry Kasparov in a six-game match. It surprised many in
computer science as well. Last year, after Kasparov's victory against
the previous version, I told the students in my class, ``Introduction
to Artificial Intelligence,'' that it would be many years before
computers could challenge the best humans. Now that I and many others
have been proved wrong, there are a lot of people rushing to assure us
that Deep Blue is not actually intelligent, and that its victory this
year has no bearing on the future of artificial intelligence as such.
I agree that Deep Blue is not actually intelligent, but I think the
usual argument for this conclusion is quite faulty, and shows a basic
misunderstanding of the goals and methods of artificial intelligence.

Deep Blue is unintelligent because it is so narrow. It can win a
chess game, but it can't recognize, much less pick up, a chess piece.
It can't even carry on a conversation about the game it just won.
Since the essence of intelligence would seem to be breadth, or the
ability to react creatively to a wide variety of situations, it's hard
to credit Deep Blue with much intelligence.

However, many commentators are insisting that Deep Blue shows no
intelligence whatsoever, because it doesn't actually ``understand'' a
chess position, but only searches through millions of possible move
sequences ``blindly.'' The fallacy in this argument is the assumption
that intelligent behavior can only be the result of intelligent
cogitation. What the commentators are failing to acknowledge is that
if there ever is a truly intelligent computer, then the computations
it performs will seem as blind as Deep Blue's. If there is ever a
nonvacuous explanation of intelligence, it will explain intelligence
by reference to smaller bits of behavior that are not themselves
intelligent. Presumably *your brain* works because each of its
billions of neurons carry out hundreds of tiny operations per second,
none of which in isolation demonstrates any intelligence at all.

When people express the opinion that human grandmasters do not examine
200,000,000 move sequences per second, I ask them, ``How do you
know?'' The answer is usually that human grandmasters are not *aware*
of searching this number of positions, or *are* aware of searching
many fewer. But almost everything that goes on in our minds we are
unaware of. I tend to agree that grandmasters are not searching the
way Deep Blue does, but whatever they are doing would, if implemented
on a computer, seem equally ``blind.'' Suppose most of their skill
comes from an ability to compare the current position against 10,000
positions they've studied. (There is some evidence that this is at
least partly true.) We call their behavior insightful because they
are unaware of the details; the right position among the 10,000 ``just
occurs to them.'' If a computer does it, the trick will be revealed;
we will see how laboriously it checks the 10,000 positions. Still, if
the unconscious version yields intelligent results, and the explicit
algorithmic version yields essentially the same results, then they
will be intelligent, too.

Another example: Most voice-recognition systems are based on a
mathematical theory called Hidden Markov Models. Consider the
following argument: ``If a computer recognizes words using Hidden
Markov Models, then it doesn't recognize words the way I do. I don't
even know what a Hidden Markov Model is. I simply hear the word and
it sounds familiar to me.'' I hope this argument sounds silly to you.
The truth is that we have no introspective idea how we recognize
spoken words. It is perfectly possible that the synaptic connections
in our brains are describable, at least approximately, by Hidden
Markov Models; if they aren't, then some other equally
counterintuitive model is probably valid. Introspection is a lousy
way to theorize about thinking. There are fascinating questions about
why we are unaware of so much that goes on in our brains, and why our
awareness is the way it is. But we can answer a lot of questions
about thinking before we need to answer questions about awareness.

I hope I am not taken as saying that all the problems of artificial
intelligence have been solved. I am only pointing out one aspect of
what a solution would look like. There are no big breakthroughs on
the horizon, no Grand Unified Theory of Thought. Doing better and
better at chess has been the result of many small improvements (as was
the proof of a novel theorem last year by a computer at Argonne Lab.)
There have been other such developments, such as the
speech-recognition work I referred to earlier, and many results in
computer vision, but few ``breakthroughs.'' As the field has matured,
it has focused more and more on incremental progress, while worrying
less and less about some magic solution to all the problems of
intelligence. A good example is the reaction by AI researchers to
neural nets, which are a kind of parallel computer based on ideas from
neuroscience. Although the press and some philosophers hailed these
as a radical paradigm shift that would solve everything, what has
actually happened is that they have been assimilated into the AI
toolkit as a technique that appears to work some of the time --- just
like Hidden Markov Models, game-tree search, and several other
techniques. Of course, there may be some breakthroughs ahead for the
field, but it is much more satisfying to get by on a diet of solid but
unglamorous results. If we never arrive at a nonvacuous theory of
intelligence, we will no doubt uncover a lot of useful theories of
more limited mental faculties. And we might as well aim for such a
theory.

So, what shall we say about Deep Blue? How about: It's a ``little
bit'' intelligent. It knows a tremendous amount about an incredibly
narrow area. I have no doubt that Deep Blue's computations differ in
detail from a human grandmaster's; but then, human grandmasters differ
from each other in many ways. On the other hand, a log of Deep Blue's
computations is perfectly intelligible to chess masters; they speak
the same language, as it were. That's why the IBM team refused to
give game logs to Kasparov during the match; it would be equivalent to
bugging the hotel room where he discussed strategy with his seconds.
Saying Deep Blue doesn't really think about chess is like saying an
airplane doesn't really fly because it doesn't flap its wings.

It's entirely possible that computers will come to seem alive before
they come to seem intelligent. The kind of computing power that fuels
Deep Blue will also fuel sensors, wheels, and grippers that will allow
computers to react physically to things in their environment,
including us. They won't seem intelligent, but we may think of them
as a weird kind of animal --- one that can play a very good game of
chess.


==========
[[
For a radically different view point, see

http://www.cs.yale.edu/op-ed/how_hard_is_chess.html

This one is by David Gelernter, who, get this, is a colleague of Drew
McDermott at Yale. On an unrelated note, Gelernter is also one of the
scientists who was targeted by the Unabomber--Kazinscky(?), and was
seriously injured by a letter bomb--thus the title of his book at the
end of the article.]]

------