Monday, April 30, 2012
Homework 3 Grading
--
Kartik Talamadupula
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).
RaoOn 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
Hello,Will the take-home final exam be turned in at your office?Thank you
Sunday, April 29, 2012
Missing image in part G of homework 3 Re: CSE 471: Homework 3 solution
Hi,In the solution for part G of homework 3, the image cannot be displayed. Can you check this, please?Thank you--
Phien Pham
Saturday, April 28, 2012
Reminder about the "NO CONSULTATIONS WITH OTHER STUDENTS" clause of the take-home
Friday, April 27, 2012
Final Exam released..
Thanks for all the ballot stuffing ;-)
Thursday, April 26, 2012
Heads up on Final Exam release..
Wednesday, April 25, 2012
Cumulatives with homework 3 grades
Monday, April 23, 2012
Fwd: course evaluations
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..
Sunday, April 22, 2012
Saturday, April 21, 2012
Re: Question related to previous lecture.
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.").
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 onDeep Blue is this paper:RaoOn 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
Friday, April 20, 2012
Re: Question related to previous lecture.
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
Thursday, April 19, 2012
*Mandatory* Interactive Review Question (Must answer as a comment on the BLOG)
=============
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.
A cool Java applet for Chess that shows the computer "thinking" its moves using min-max and alpha-beta & Quiescence search
Office hours 2-3pm today..
Monday, April 16, 2012
Bayes Net Project Answers and Stats
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)
Sunday, April 15, 2012
Applets URL corrected for homework 3
Saturday, April 14, 2012
Thinking Cap: A Post-Easter Resurrection..
Thursday, April 12, 2012
Next topic: Search in perfect information games: Chapter 5.1--5.3
Tuesday, April 10, 2012
Last homework-cum-micro-mini-project released
My mis-statement in class about the standard resolution refutation proof error
Grading for your homework 2
Monday, April 9, 2012
Current Grade Book (with test 2 and homework 2 scores)
Saturday, April 7, 2012
An easter egg in the form of Test 2 do-over..
Wednesday, April 4, 2012
Availability tomorrow
Some errata corrected in the Spring Field problem solution
Part B.[4pt] Given your network above, which of the following (conditional) independences hold? Briefly justify your answer in each case:
- 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.
- 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)
- 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.
Tuesday, April 3, 2012
Cleaned up most of the UTF-8 error chars in the springfield bayesnet example
Forgot to tell you about the Turing award for PAC...
Re: Review for Thursday
If you cannot make those times work for you, let me know and we can arrange to meet individually at another time.
-Will