Tuesday, March 31, 2009

Google develops worlds first artificial intelligence tasked-array system...

Research group switches on world's first "artificial intelligence" tasked-array system.

For several years now a small research group has been working on some challenging problems in the areas of neural networking, natural language and autonomous problem-solving. Last fall this group achieved a significant breakthrough: a powerful new technique for solving reinforcement learning problems, resulting in the first functional global-scale neuro-evolutionary learning cluster.


Glow-in-the-Dark Lenny & Watery Squishies

The probability of glow-in-the-dark employees given a meltdown is 0.5, and the probability of glow-in-the-dark employees given Homer is an idiot is 0.05 (P(Homer is an Idiot) = 1.0). Should these combine in a fashion similar to the noisy-or combination of inferior Pu and heavy water, i.e. is P(GitD|MD,Homer) = 0.525 or simply 0.5?
Also, is the same true of Apu's bad Squishie machine, the meltdown, and watery squishies?

mandatory Readings for next class:

For First order logic, we will cover

8.1, 8.2, 9.1, 9.2, 9.4 and 9.5

read at least the first three sections before coming to class on Thursday


Monday, March 30, 2009

(at-home) optional midterm marks


 Here are the marks on the at-home version of the mid-term. I juxtaposed them with
the in-class one just so you have an idea.  Note that the marks are not completely comparable
since the at-home one is graded by Yunsong.



Thursday, March 26, 2009

An article about the Loebner Prize Turing Test Competition


Re: clarification?

On Thu, Mar 26, 2009 at 12:21 PM, student wrote
Hi professor,
Could you help me get a breakdown of the marks allotted to homeworks and projects and exams? I think you mentioned in class today that the homework is about 5 points each and that the exam is worth 20 points. Could you also tell me approximately how many projects are left before the finals and how much the final would be worth?
Thank you so much!

The "default", as I announced at the beginning, is  20pts for all homeworks together; 35-40 for projects, and 40-45  for exams and 5-10 points for class/blog participation.

homeworks are typically worth 5pts each

projects are, on the average, worth 10 points each (bayes net project doesnt
involve coding and will probably have a little less weight than 10)

After the bayes net project, we will either have at least one more longer project (more likely; will be on first order logic) or
two B.N. like coding-light projects; haven't quite decided.

Hope this helps.


ps: I am broadcasting my answer as others might also be interested in it

Wednesday, March 25, 2009

Current cumulatives


 With two homeworks, project 0, project 1 and mid-term graded, here are the current cumulatives.
Note that I scaled the project 0 to be 1 percentage point, each homework to be 5 perecentage points,
the project 10 percentage points and the midterm 20 percentage points--so you have completed 41 points

The "percentage" column just shows your score (over 41 points) as a percentage.

Note that this is meant to be a rough estimate. The exact weightings for the projects/homeworks/midterm may change.
We will also make room for class/blog participation grade. Nevertheless, you can get a feel for how you are doing right now.



URL for midterm solutions

Here are the solutions for the midterm. Feel free to question them in the blog...



Midterm grade distribution...

Here are the stats for midterm:

 Average: 43.75;  Standard Deviation: 16
 Max: 69.5    Min: 15.5
     70-80: 0 
     60-70: 6
     50-60: 1
     40-50: 10
     30-40: 1
     20-30: 5
     10-20: 1

 Average: 55.3   Standard Dev: 18.35
 Max: 76.5   Min: 21.5
   70-80: 4
   60-70: 0
   50-60: 3
   40-50: 2
   30-40: 1
   20-30: 1

I will distribute the graded midterms in the class tomorrow.


Tuesday, March 24, 2009

Status of midterm grading.. (for the in-class version)


 I am about three-quarters way through grading the midterm. I expect to post the grades and bring the exams for distribution next class.

If any of you need to know your midterm grade earlier than that, please do let me know by email and I will let you know your grade asap.


Mandatory reading for next class: sections 14.4 and 14.5 in the textbook


 Please make sure to read sections 14.4 and 14.5 before coming to the class on Thursday. It is only 12 pages
and even a cursory reading will significantly increase your chances of following the lecture.


Saturday, March 21, 2009

Another cool course

This is what I found is being taught in John hopkins ATM... Very cool course structure...


Thursday, March 19, 2009

An exam so nice, some do it twice... or the low-down on the at-home version of the in-class exam...

The at-home-version-of-the-in-class-exam (ahvotice) is a pedagogical innovation
next only to the socket-open-socket-close-homework-assignments and blunt-force-trauma-causing
thinking-cap questions. Here is the standard FAQ on ahvotice

0. What are the ground rules for doing this--

Only that (a) you work independently and (b) you
submit it at the beginning of the class
on Tuesday 3/24

1. Can I just do the parts that I thought I didn't do well in the in-class version?

No. The at-home and in-class versions are graded as full papers.

2. Do I lose anything if I don't do it at home?

No (okay--you do lose the satisfaction of doing it twice;-). Your
grade in in-class will stand.

3. How is the effective midterm grade computed?

Eff = max( in-class; w*in-class+(1-w)*at-home )

4. What is the range of w?

0.5 < w <1

(typical values in the past ranged between .6 and .666)

5. But if everyone else does it at home and improve their grade, and
I decide to watch Simpsons/Seinfeld reruns instead, don't I lose out?

No. First of all, *nobody* ever loses out by watching reruns of Simpsons (Channel 6, weeknights 10 & 10:30) and
Seinfeld (Channel 10; week nights 10:30 and again at 11:30).

The difference between your inclass score and the Eff score will be
considered as your _extra credit_ on the mid term (and thus those
points wont affect grade cutoffs).

6. How do you device these ludicrously complex schemes?

Well, I had a relaxing spring break ;-)

7. Okay. I have no life outside of this course anyways. Tell me where I can find the exam?

Here: http://rakaposhi.eas.asu.edu/cse471/s09-midterm-athome.pdf


Thinking Cap qns on Bayes Networks...

0. In class, we seemed to convince ourselves that the CPT entries don't have to add up to 1. Suppose you have a boolean node with m boolean parents. What is the maximum value of the sum of CPT entries? When does it happen?
1. You have been given the topology of a bayes network, but haven't yet gotten the conditional probability tables
    (to be concrete, you may think of the pearl alarm-earth quake scenario bayes net).
    Your friend shows up and says he has the joint distribution all ready for you. You don't quite trust your
    friend and think he is making these numbers up. Is there any way you can prove that your friends' joint
    distribution is not correct?

2. Continuing bad friends, in the question above, suppose a second friend comes along and says that he can give you
   the conditional probabilities that you want to complete the specification of your bayes net. You ask him a CPT entry,
   and pat comes a response--some number between 0 and 1. This friend is well meaning, but you are worried that the
   numbers he is giving may lead to some sort of inconsistent joint probability distribution. Afterall, your friend is a bayesian and is making up is *personal* probabilities that may not have any interpretation from a frequency point of view. Is your worry justified ( i.e., can your
   friend give you numbers that can lead to an inconsistency?)

  (To understand "inconsistency", consider someone who insists on giving you P(A), P(B), P(A&B) as well as P(AVB)  and they
wind up not satisfying the P(AVB)= P(A)+P(B) -P(A&B)
[or alternately, they insist on giving you P(A|B), P(B|A), P(A) and P(B), and the four numbers dont satisfy the bayes rule]

Your other friend (okay--your social life is full of geeks ever since you started taking this course) heard your claims that Bayes Nets can represent any possible conditional independence assertions exactly. She comes to you
and says he has four random variables, X, Y, W and Z, and only TWO conditional independence assertions:

X .ind. Y |  {W,Z}
W .ind. X  |  {X, Y}

She dares you to give him a bayes network topology on these four nodes that exactly represents these and only these conditional independencies.
Can you? (Note that you only need to look at 4 vertex directed graphs).
4. If your  answer to 3 above is going to be "No", how serious an issue do you think this is? In particular, suppose your domain has exactly set A of conditional independencies. You have two bayes network configurations B1 and B2. The CIA(B1) is a superset of
A and CIA(B1) is a subset of A.   Clearly, neither B1 nor B2 exactly represent what you know about the domain. If you have to choose one to model the domain, what are the tradeoffs in choosing B1 vs. B2?

Wednesday, March 18, 2009

Forward Checking and ARC Consistency.. Now for Rao's version

Looks like the confusions are begetting more confusions in the FC/AC discussion. Let me stop the buck...

Terminology: If you have n variables x1...xn; and if you have assigned x1,x2...xi-1; and are about to assign xi,
then current variable: xi  ; past variables: x1...xi-1  ; future variables xi+1....xn

Forward checking:

The idea: For each *future* variable, remove from its domain any values that are conflicting with the assignments you have done  until now (i.e., past variables and current variable).

In the special case of binary CSPs, notice that the only way a value can be deleted from the domain of the future variable is if it conflicts with the assignments made to the current variable.

In the case of n-ary CSPs, it is possible that the current variable's assignment along with some of the past variable assignments will rule out a value from the future variable's domain.
(e.g. suppose we have a constraint  x1=a& x4=b => x9 !=c ; so if x1 is a past variable and was assigned a; and x4 is the current variable and got assigned b, we can remove c from the domain of x9)

ARC Consistnency:

 The idea: Make sure that for every variable, xi; and every other variable xj (different from xi), for every value that
  xi can take, there is a value that xj can take without conflicting with xi.
So, if you find that when xi takes a, xj cannot take *any value*, then you *remove* a from the domain of xi. In this sense of  "pruning values from domains" ARC Consistency is similar to Forward checking.

 However, unlike FC, which is with respect to a given search branch--with past, current and future variables, Arc Consistency is a *preproessing technique* and does not differentiate between past/current/future variables)

It is easy to see that if you have a binary CSP and you already ensured ARC consistency on it, then doing Forward checking will not remove any more values--no matter in what order you wind up assigning variables.

hope this helps

ps: So is sudoku a binary CSP or not?


  "My student came to me with a desire to know the time, and
    I taught her how to make a watch"
                                -Chris in the morning (Northern Exposure)

Regarding Forward Checking and Arc Consistency

Since so many students asked questions about Forward Checking and Arc Consistency today,
I think it is necessary to make sure everyone are on the same boat. Let me try to clarify, correct me if
I am wrong:

Forward Checking:
Keep a list of all possible values for each unassigned variables, every time before assigning a value to a variable,
check whether that value is the only possible value for neighbor variables (Don't permanently delete that
value from neighbor's possible value), if none of them is the case, make the assignment, and update the possible
values for other variables (Now you can delete the value just assigned). And keep going.

Arc Consistency:
Keep all possible values for unassigned variables, and propagate constraints to each of the variable.
Remove any possible value that has no support from neighbors, and check all variables each round.
End if no value was removed in one round. (For one round, I mean update all variables) 

Teaching Assistant

Tuesday, March 17, 2009

regarding second project deadline

Dear all:

 Apparently CSE 471 student-body is turning into a veritable California electorate with voter-sponsored initiatives aimed at the evil deadlines.. I wish people divert part of this enthusiasm to blog-participation on thinking cap questions..

Anyways, while the blog makes it sound as if there is uniform and vocal support for deadline change, I have also received direct mails asking that the deadline *not be shifted* since the students in question have worked their schedules around to get done with the project.

To be fair to people who have completed their work as well as allow a little more time to those who want to complete the project, I will take the project until Tuesday with a 20% late penalty. (Please resist the temptation to ask us questions such as "Can reduce my penalty to 5pi% if I turn in the project only pi days late")


Monday, March 16, 2009

MRV and forward checking

What exactly is the difference between MRV and forward checking. They seem to be almost the same thing. It seems that forward checking is redundant since MRV will find the variably with the empty domain as soon as it arises and thus fail and begin back tracking.

Re: Statistics of homework 2 and project 1

Homework 2 

  total: 100

               min            max         average      
Grad:       41              96            75.9           
Under:      41              91            69.5

Project 1 without extra points

  total: 50

               min            max         average
Grad:       40              50            45.9
Under:     15               50            40.8

Project 1 with extra points

  total: 63
               min            max         average
Grad:       42              60             51
Under:     15               61            42.4

Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Statistics of homework 2 and project 1

Homework 2 

  total: 100

               min            max         average      
Grad:       41              96            75.9           
Under:      41              91            69.5

Project 1 without extra points

  total: 50

               min            max         average
Grad:       40              50            45.9
Under:     15               50            40.8

Project 1 extra points

  total: 63
               min            max         average
Grad:       42              60            51
Under:     15               61            42.4

Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

CSE471/598 TA office hours update

A reminder, I will have office hour on Wednesday for project 2, 2:00PM-3:00PM.

Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Homework2 pickup

Hi guys, 
    Homework 2 is ready for picking up from 2:00PM- 4:00PM today in my office (BY513BA) and after 4:00PM in 510 during view session. Rest of them will be giving back on Thursday.

Teaching Assistant
Department of Computer Science and Engineering
School of Computing & Informatics
Arizona State University

Project 2 Deadline

In leui of the exam this week, and exams in other courses this week, is there any way to get an extension on project 2? I know we got an extension on the first project and it seems unfair to ask for another, but I'm finding it difficult to find any time right now. The extension for the last project helped greatly and I was able to learn a great deal more given that I had more time, and it would be unfortunate (for my grade and for my education) to have to rush this project.

If anyone else is having difficulty with the courseload this week please leave comments, if for no other reason than to give my misery some company :)

Friday, March 13, 2009

Confirming the pre-midterm review session [4pm, Monday, BY 510, taught by Will Cushing--cc'd here]

 A bunch of you responded saying you would like to have the review session. It is going to be held on Monday
at 4pm in Brickyard seminar room 510--when you get out of the elevators on the 5th floor just turn right

Will Cushing, a senior graduate student, kindly agreed to do the review session.
[The last time I had Will do review/tutoring sessions for 471 students, some people apparently
liked them so much that there were a few comments on the feedback survery asking me
why I don't let him do the whole shebang instead--so you know I am putting my very job on the line in letting
Will come and tech you ;-).

Will (wcushing@asu.edu, cc'd above) asked me to ask you to send him any topics that you particularly want to
see reviewed so he has a heads-up.


ps: To those of you who wanted to attend the review session and said you have conflicts at 4--sorry. I couldn't take the
chance of trying another time slot and introduce a fresh set of conflicts, and decided to settle for this local minima of sorts.
The room itself is reserved from 4 to 6pm. So, if you are late in coming you may still find the session going.

Tuesday, March 10, 2009

Possibility of a pre-mid-term review session on Monday 16th ~4pm (RSVP)


 I am trying to find out if there would be sufficient interest in having a review session before the midterm.

Such a review session might happen on Monday 16th at 4pm, and will be offered by a senior graduate student.

Let me know, by replying to this email,  if you would be interested in attending such a session.

If there is sufficient interest, I will let you know where it will be held.


Saturday, March 7, 2009

Universal grammar

We had a digression yesterday about statistics vs. probability yesterday where I wound up discussing about
learning, bias in learning as well as universal grammar as a basis for language learning.

If you found any of that intriguing, you might like the following post from a previous year that talks about
universal grammars:



Wednesday, March 4, 2009

Questions on project 2

I have a question about the meaning of the "main diagonal constraint" on project 2.

1. What's the precise meaning of main diagonal? For example, for a 4x4 board:

1 2 3 4
5 6 7 8
4 5 6 7
2 3 4 5

is the main diagonal 1 6 6 5 ?

2. Does this apply to each block or to the entire board?

Readings for next class: 13.6; 14.1 and 14.2

 Too many of you seemed dazed and half-or-fully asleep yesterday (it must rank as one of the sleepiest classes I have taught in ages :-(

To make sure this doesn't happen again tomorrow, please read (or at least skim) sections 13.6, 14.1 and 14.2 in the text before coming to class.


Tuesday, March 3, 2009

Thinking Cap Questions on Propositional & Probabilistic logic

See if you can answer these on the blog

0.  If I have n propositions, how many possible clauses are there? (Assume that clauses of the form A V A are automatically simplified to A).
     Does this help in convincing you that the resolution theoremproving search procedure is *complete* in that it will terminate whether or not
     the theorem you are trying to prove actually holds?

1. We saw that propositional logic is monotonic and that real world requried "defeasible" or "non-monotonic" reasoning. Is probabilistic reasoning
    monotonic or non-monotonic? Explain.

2. You obviously heard the two words "Probability" and "statistics". What is the difference between them? (or are they basically synonyms?)

3. We made a big point about the need for representing joint distribution compactly. Much of elementary probability/statistics handles
    continuous and multi-valued variables, where specifying the distribution of the single variable itself will need a huge number of numbers.
    How is this normally side-stepped in elementary probability?