CSE 494/598 Fall 2008 Blog

sayanora..

2008-12-23T07:57:00.000-08:00

Folks:

The grades have been submitted, and I assume several of you already know yours.

Judging from a sampling of mails prior to the grades, it is possible that several of you
received better grades than you suspected. This is all part of a carefully cultivated delusion
on my part that this class is somehow harder than your other classes and should have
more christmasey grades.. :->

If you did get a grade better than you suspected, just remember the climactic scene from Saving Private Ryan
and just "... earn it" (which could, for example, involve listening to the final exam answers audio so you don't
carry misunderstandings forward).

I also wanted to take this opportunity to publicly thank Garrett--your long suffering TA. He had to grade
three projects, four long homeworks and see a demo, and voluntarily held additional office hours over weekends
to help you with your projects.

I wish you all great holidays and hope our paths will cross again in future (and that we won't glare at each other, if they do ;-)

I myself am off to Hawaii where I expect to catch golf balls for my buddy Barack.

cheers
Rao

Final exam answers

2008-12-22T16:56:00.000-08:00

As you wait to see your grades, I thought this is pretty much the last chance I have to get you to hear the answers for the final exam

Here it is in audio form (imagine--you can put it on your ipod and hear it instead of those cloying christmas songs...), and just 31min long.

http://rakaposhi.eas.asu.edu/cse494/notes/cse494-final-exam-answers-podcast.WAV

Seriously, if you got a low score on the final, then you probably want to listen to this so you won't carry the misunderstandings with you.

cheers
Rao

Cumulatives with late penalties and participation

2008-12-22T13:59:00.000-08:00

Folks:

There were a bunch of cases of late submissions for which we had forgotten to include the late submission penalty. The version below includes that. Also, the total+P column is total that includes participation credit.

regards
Rao

Project 3

2008-12-22T10:21:00.000-08:00

If anyone wants to stop by to pickup project 3, I am here in the lab now (557AD).

Garrett

Final Cumulatives (sans extra credit)--

2008-12-22T08:08:00.000-08:00

Folks:

Here are the final "real" cumulatives (with the final exam marks thrown in). These are computed
with 40% for projects, 20% for homeworks and 40% for exams. [The participation credit is a subjective credit
given out of 5 points. It is not currently added into the cumulatives]

*****I am willing to hear from the students at the top of each list (598 and 471) as to what should be the grade cutoffs
for the rest of the class (these two students are guaranteed an A at least).**** (Those two can send me email with their suggestions)

cheers
Rao

final exam points

2008-12-22T07:48:00.000-08:00

Here are the stats on the final exam that I just finished grading.

Project 3

2008-12-20T16:22:00.000-08:00

If anyone needs their project 3, please send me an mail…

Garrett

Cumulatives (sans the final exam grade)

2008-12-20T15:12:00.000-08:00

Folks:

Here are the current cumulatives (I am still grading the final--so those are not included). If you find any errors, please let me and garrett know ASAP.

rao

Blowing Steam Topic: Questions on the final that may have infuriated you etc.

2008-12-16T16:54:00.000-08:00

Folks

Here is a last topic for the blog where you are encouraged to discuss any questions on the final that you found insulting/infuriating/intriguing -- or just want to know what is supposed to be the right answer.

cheers
Rao

Attendance statistics...

2008-12-16T12:04:00.000-08:00

According to the participation survey,

Avg # classes missed: 1.3 (average missed with prior notification: 0.3) Standard Dev: 1.4
Max: 6 Min: 0 [11 students had perfect attendance; so surprisingly, did Rao!]

rao

Re: Semantics and schemas

2008-12-15T21:34:00.000-08:00

Not an easy question to answer via email, but I will try..

All I meant when I said databases and/or XML don't have semantics is that the columns don't have any meaning that you might associated based on their "english" names.

Databases do have semantics--they have basically "look-up" semantics. Each tuple describes a complete world and you can do
selection/projection/join/count etc inference (queries). However, just because the database tuple says the person is "dead", you can't assume that the database can answer a query "is the person currently reading a paper?".

The more background knowledge you provide, the more deeper (i.e., non-lookup) inferences you can do. [A set of RDF triples provide no more inferential power than a set of relational tables conforming to a single schema. For example, a database tuple
<id=345, grade=A, gender=male> corresponds to the RDF triples t1--id--345; t1--grade--A; t1--gender--male.
It is the background knowledge--via RDF-Schema--that allows you to do more inferences.]

--look at it another way. If you remember the magellan story-- after hearing that magellan is an explorer and he went around the world three times, a look-up inference can answer "Is magellan an explorer?" and "how many trips did he make?". A look-up inference however cannot answer the query "in which trip did magellan die?"--that requires more background knowledge. [Of course, if you are happy with just look-up inferences, then you don't need background knowledge. However, when you have multiple autonomous databases, and you wan't to "integrate" then, you in essense at least need a special type of background knowledge that at least maps the columns in both databases]

if you want a really clean grasp of what it means to talk about inference and semantics, I would recommend that you take intro to AI ( http://rakaposhi.eas.asu.edu/cse471 )

Rao

On Sat, Dec 13, 2008 at 10:42 PM, Pierre Bucher <Pierre.Bucher@asu.edu> wrote:

Dear Mr Kambhampati,

The answers to the question you put on the blog some time ago, about whether relational DB had semantics, made me doubt about the meaning of "semantics". I guess that XML Schema don't have semantics, because (1) we would not need RDF if it was the case (2) there is no concept of property and of inheritance in XML Schema, which seems to be the base of semantics. Then I would guess that relational DB don't have semantics either: they just have meta-data without meaning like XML and XML Schema. Is it true?

Moreover, is the fact that we have properties and relationships that gives RDF semantics? Then the concept of inheritance made possible by RDF Schema would not give semantics, but just makes easier the processing of semantics (and actually we could do little without it). Is that right too?

Thank you.

Pierre Bucher.

Re: One question about Authority/Hub computation

2008-12-15T21:16:00.000-08:00

By "different", I assume you referring to them having different results during intermediate iterations, right?
We are not really interested in a1 and h1--but rather in a* and h*. Both reach the same fix point. [I suspect the rate of convergence for the first method is going to be faster--for the same reason asynchronous iterations on pagerank make it converge faster.]

rao

On Sun, Dec 14, 2008 at 5:05 PM, Jianhui Chen <Jianhui.Chen@asu.edu> wrote:

Hello, Dear Dr. Rao,

I have a question about the computation of Authority / Hub score as below:
-----------------------------------------------
If a0 and h0 are pre-given, let A be the adjacent matrix, we can
compute a1 and h1 via
following two approaches theoretically

1. a1 = A' * h0, h1 = A * a1
2. a1 = (A' * A) * a0, h1 = (A * A') * h0.

However, in generally, the two approaches would generate different result.

Could you please help to advice which one we should take for the computation?

Sorry for disturbing you during the weekend. Many thanks.

Jianhui

Re: Regarding the discussion

2008-12-15T15:34:00.000-08:00

Basically yes..

What is interesting is that you need to have a pretty strong bias to begin with if you are learning only from positive examples if you want to avoid over-generalizing..

Consider, for example, that your most general grammar hypothesis allows both languages that constraint word order (e.g. english) as well as those that don't (e.g. hindi," spanish -- where you can, in essense say "Tom Mary hit"--while in english you have to say "tom hit mary" or "mary hit tom".) If I only give you positive examples of usage in English, you would not know that English doesn't allow sentences like "Tom mary hit". In order to do do that, you will need to bias your
learner saying that word order dependence and word order independence are mutually exclusive (so you won't over generalize).

Of course, this is not just idle speculation---our current understanding is that children come into this world with a universal grammar which has all these kinds of constraints embedded, so they are able to learn grammar from mostly positive examples.

Rao

On Mon, Dec 15, 2008 at 4:13 PM, Shruti Gaur <sgaur2@asu.edu> wrote:

Dr.Rao,
From the version space idea you explained, it seems the more positive examples we have, the more we can generalize (whereas the negative examples will break the current hypothesis we hold into the next level where we can evaluate each of them and remove the false ones.) which I guess is true in human learning as well.
This made the idea of generating grammar from positive examples more clear as grammar is also kind of a generalization of all the syntactically valid sentences we can make.eg (subject verb object) is the grammar or generalization where each constituent can have different values.

Please correct me if I am wrong
Regards
Shruti

--
Thanks & Regards

Shruti Gaur
Graduate Student
MS(Computer Science)
Dept of Computer Science & Engineering
Arizona State University

Homework 4

2008-12-15T14:12:00.000-08:00

If you would like to pickup your graded homework 4 before the final exam, please stop by the lab on the 5th floor. 557AD

Garrett

REMINDER: Exam tomorrow Tuesday 12/16 12:10--2:00pm same room

2008-12-15T08:55:00.000-08:00

availability today for final-exam-related questions..

2008-12-15T08:46:00.000-08:00

I will be mostly in my office until about 3pm today. If you have questions, feel free to drop by.

(if you want to check before showing up, my office number is 480 965 0113)

rao

The final exam will be closed-book (as had been agreed in the class)

2008-12-15T08:45:00.001-08:00

Some of you sent mails asking whether the final will be open or closed book.

As had been agreed in the class a couple of weeks back, the final will be closed book. You just bring your
brains to the exam (fill them up first though..)

You can use standard (non-matrix) calculators during the exam.

cheers
Rao

Final exam coverage..

2008-12-11T07:15:00.000-08:00

The final exam is going to be comprehensive, but with significantly higher emphasis on the
topics not covered by the midterm.

regards
Rao

in praise of intellectual swagger..

2008-12-09T21:21:00.000-08:00

Folks:

Just got done going through all your comments on the top-k ideas you appreciated. Thanks for the many thoughtful
comments.

I should probably sign-off on that chummy note and resist my curmudgeon-like urge to kvetch (especially on the eve of teaching evaluations ;-), but I can't.

Despite the semester-long attempts to foster skepticism, there still was a little too much google-swooning in the reviews for my taste. While I don't mean to legislate your predilections, I do want to suggest that it would be way much more fun to be path-breakers rather than be groupies. For the former you would need more skepticism and a lot more intellectual swagger.
No one ever changed/improved anything that they are smitten with.

cheers
Rao

Fwd: CEAS teaching evaluations..

2008-12-08T13:09:00.000-08:00

Dear all:

As per the below, I encourage you to take part in the CEAS teaching evaluations.
I take the feedback seriously and particularly pay attention to written comments on what worked and didn't.

Here is hoping for a 110% turnout ;-)

cheers
Rao

---------- Forwarded message ----------
From: James Collofello <JAMES.COLLOFELLO@asu.edu>
Date: Mon, Dec 1, 2008 at 12:09 PM
Subject:
To: "DL.WG.CEAS.Faculty" <DL.WG.CEAS.Faculty@mainex1.asu.edu>
Cc: Ann Zell <ann.zell@asu.edu>

Colleagues,

The Fall 2008 teaching evaluations became available to students today, Monday, Dec 1, around 10:00 a.m. and will close on Wednesday, Dec 10 (reading day) at 12:00 midnight. Students will be able to access the evaluation tool at: https://fultonapps.asu.edu/eval

Please encourage your students to complete the evaluations or face several nagging email requests. Good luck on your scores!

Chairs – please distribute this message to your faculty associates.

Thanks,

jim

James S. Collofello

Associate Dean of Academic and Student Affairs

Professor of Computer Science and Engineering

Ira A. Fulton School of Engineering

Arizona State University

Re: question about hw q3

2008-12-08T08:39:00.000-08:00

Sorry for the confusion. You can (and should) have room information in the mediator schema.

[I didn't specifically mean to require that mediator schema not have room attribute (it would seem rather silly to have a course schema that doesn't give room information). ]

rao

On Mon, Dec 8, 2008 at 9:31 AM, Mijung Kim <Mijung.Kim.1@asu.edu> wrote:

Hi Professor,

I have a question regarding hw q3.

In the question,

"We have another source called ASU-CS-S02-Catalog- which exports the set of CS courses being taught in Spring 2003, the instructor who will be teaching them, and the rooms in which the classes will be taught. Write this source too as a materialized view on the mediator schema."

According to the mediator schema, we don't have "room" attribute. In this case, should we update mediator schema adding the room to it?

Could you enlighten me on this??

Thanks,

Mijung

participation evaluation sheet (please return in hardcopy on Tuesday)

2008-12-06T15:00:00.001-08:00

Folks:

I put up a participation self-evaluation sheet at

http://rakaposhi.eas.asu.edu/cse494/participation-08.pdf

Please print it, fill it and bring it to class on Tuesday (I am sending this now rather than just bring it to Tuesday's class since
the form asks you to remember how many classes you missed etc. and I would prefer getting better than order-of-approximation answers).

Rao

Rescheduled Demo Slots

2008-12-04T14:44:00.000-08:00

I forgot to block out the time slots which overlap with Tuesday's class so would the 5 students who signed up during that time please contact me and let me know when you would like to do your demo.

Just to remind everyone, you will only have 20 minutes to complete the demo. I completed one of the demos earlier today in about 12 minutes. The demo was very thorough and included some waiting time as well as time to demo several extra credit functions, so 20 minutes should be more than enough time to complete it.

Keep in mind that if you plan on using one of the lab machines for the demo, that they sometimes take a while to boot/login.

I look forward to seeing everyone's demo next week.

Garrett

The demo signup sheet

2008-12-04T14:27:00.001-08:00

Hi Garrett (and the class)

Here is the demo sign-up sheet with information on who took which slot.

I just noticed that several of those slots are right during the class time on Tue. This is a clear no-no (and I have already black-listed the folks who decided to sign-up for them :-> ). Anyways, please reschedule those to times outside the class time.

thanks
Rao

Blog qn for Homework 4 (You should post your answer as a comment to this thread and also enclose it in your hw 4 submission)

2008-12-03T07:40:00.001-08:00

Here is the "interactive review" question for homework 4 that I promised.

"List five nontrivial ideas you came to appreciate during the course of this semester"
(You cannot list generic statements like "I thought pagerank was kewl". Here is an example:

The deep connection between feature selection and dimensionality reduction: By
understanding LSI, LDA and MI based feature selection, I was able to see the deep
connections between dimensionality reduction (which works without taking any particular
classification task into account) and feature selection (which typically take the classification task
into account).
)

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

Topic for this week: Information Integration --slides available online..

2008-12-02T09:15:00.001-08:00

Folks:

This week we will discuss issues in information integration; tthis will also be the last major topic for the semester.
I put up the slides for the class online. I strongly suggest
that you take a look at them before coming.

cheers
Rao

Project Demos

2008-11-30T15:44:00.001-08:00

There have been a few questions regarding the demos so here's some information you may need. The demos will each be 20 minutes and will be held between Dec 4th and Dec 9th...a sign up sheet with time slots will be passed around. Please show up early to the demo so you can be ready to go when your time begins (there are 35 demos so any delays can quickly add up).

For the demo I will ask to see vector space, page rank, auth/hubs, kmeans, and buckshot (or other if you chose something else). I will ask you to run a few queries, explain some of the algorithmic details of your implementation, and possibly other related things. Your program should be robust in terms of allowing for configurable parameters (c, w, k, n, etc.). I will also verify those who implemented a GUI and/or other extra credit items.

Make sure you have your code running smoothly before the demo as each student will only have 20 minutes. I will hold the demo session in the 2nd floor lab so if you need to run it on one of the lab machines, you should have pleanty of time to setup early. You may also run it on your personal laptops.

Several students showed up yesterday and today for the additional office hours but for those who couldn't make it, I will have the final office hours on Wednesday before the project submission.

Thanks,
Garrett

Sunday Office Hours

2008-11-30T08:54:00.001-08:00

A few of you were interested in meeting today so I will be available from around 2:30pm until at least 4:00pm so feel free to stop by with any questions…

Garrett

Office Hours

2008-11-28T14:41:00.000-08:00

I’ll be down in the 2^nd floor lab in about 30 minutes for those students who were requesting to meet with me…I’ll also be there on Sunday later in the afternoon…I’ll send out a time by tomorrow.

Garrett

Shadow-play video of the make-up class online..

2008-11-26T14:17:00.001-08:00

Folks:

A "functional" video of today's class is now online (in the lecture notes page). The video isn't exactly going to win any
cinematography prizes (except perhaps in the shadow-play category), but it is sufficient for you to follow the lectures as well as
identify which specific slides are being shown (the slides themselves are available online).

I would like to once again thank the hardy souls who showed up today *and* waited for close to 30 minutes while I tried to set right all
the things that went wrong in the last minute (those of you who weren't there can commiserate by listening to the first three minutes ;-).

A one-level grade-hike for them would seem entirely warranted...

Happy thanksgiving!
Rao

Additional Sunday Office Hours

2008-11-26T12:56:00.001-08:00

If there are students who would find it useful for me to have additional office hours on Sunday later in the afternoon, please let me know and I’ll fix a time to be available.

Garrett

Reminder: Make-up class today at 10:30AM in BY 210 (near advising office)

2008-11-26T07:27:00.000-08:00

See you there. We will continue the discussion of Information Extraction

(I decided to modify the coverage a bit--and plan to do a broader overview of information extraction
from unstructured text before going into specific projects like semtag/seeker)

rao

Re: Doubt in homework

2008-11-23T18:29:00.001-08:00

rdf actual standard format would be good; but normal triples are fine as a second choice.

rao

On Sun, Nov 23, 2008 at 6:02 PM, Shruti Gaur <sgaur2@asu.edu> wrote:

Hi Dr.Rao

In the question
Write down some of the RDF triples relating the URIs &r12, &r13 and &r14 in form.

Should the triples be in XML or the form(object x, predicate, object y)?
--
Thanks & Regards

Shruti Gaur
Graduate Student
MS(Computer Science)
Dept of Computer Science & Engineering
Arizona State University

Re: HomeWork 4

2008-11-23T09:32:00.000-08:00

You have to write an xquery that does this reformatting (and run it and show it does)

Rao

On Sun, Nov 23, 2008 at 10:25 AM, Mithila Nagendra <mnagendr@asu.edu> wrote:

Good Morning Dr. Rao

On Homework 4, Question 1 Query 4 - I was wondering if have to produce an output that matches the format given or actually go into the file bib.xml and reformat it.

Thank you
Mithila

Re: CSE494/598 Project C clarification

2008-11-22T05:53:00.000-08:00

Hi Michael (and the rest of the class):

By default, task 6 will be buckshot algorithm as mentioned in the specification.

It is okay to replace task 6 with another task with *similar* complexity (for example, you can replace 6 with bisecting k-means, but not with "small extensions of K-means").
The replacement for task 6 doesn't necessrily have to be a clustering task.

If you are interested in replacing task 6 with something else, to be on the safe side, you might check with the TA as to whetehr or not the replacement is of similar complexity.

hope this helps.

rao

On Fri, Nov 21, 2008 at 11:00 AM, Balzer, Michael J (Mike) <Michael.Balzer@asu.edu> wrote:

Dr. Rao,

When project C was assigned, I thought I remembered you mentioned that you may change Task 6 such that the student may choose what to implement, instead of everyone doing Buckshot. As it stands now, the class webpage shows Task 6 as Buckshot only, and a list of extra credit tasks. Another student told me that we are not required to do Buckshot, and can choose something else for Task 6 (e.g. relevance feedback, bisecting k-means, etc.). Can you clarify?

Thanks,

Mike Balzer

Thinking Cap: From the latest NYT magazine: Netflix prize; Collaborative filtering, Singular value decomposition and recommendation systems

2008-11-21T11:59:00.001-08:00

Did you think that NYT can explain SVD and LSI in its articles?
Now you can show your parents and friends this article when they ask
what is that strange course you are taking ;-)

The benefits of having NYT work in tandem with the course ;-)

See if you can agree/disagree and/or spot simplistic explanations in the article

Rao

http://www.nytimes.com/2008/11/23/magazine/23Netflix-t.html

November 23, 2008

The Screens Issue

If You Liked This, Sure to Love That

By CLIVE THOMPSON

THE "NAPOLEON DYNAMITE" problem is driving Len Bertoni crazy. Bertoni is a 51-year-old "semiretired" computer scientist who lives an hour outside Pittsburgh. In the spring of 2007, his sister-in-law e-mailed him an intriguing bit of news: Netflix, the Web-based DVD-rental company, was holding a contest to try to improve Cinematch, its "recommendation engine." The prize: $1 million.

Cinematch is the bit of software embedded in the Netflix Web site that analyzes each customer's movie-viewing habits and recommends other movies that the customer might enjoy. (Did you like the legal thriller "The Firm"? Well, maybe you'd like "Michael Clayton." Or perhaps "A Few Good Men.") The Netflix Prize goes to anyone who can make Cinematch's predictions 10 percent more accurate. One million dollars might sound like an awfully big prize for such a small improvement. But in fact, Netflix's founders tried for years to improve Cinematch, with only incremental results, and they knew that a 10 percent bump would be a challenge for even the most deft programmer. They also knew that, as Reed Hastings, the chief executive of Netflix, told me recently, "getting to 10 percent would certainly be worth well in excess of $1 million" to the company. The competition was announced in October 2006, and no one has won yet, though 30,000 hackers worldwide are hard at work on the problem. Each day, teams submit their updated solutions to the Netflix Prize Web page, and Netflix instantly calculates how much better than Cinematch they are. (There's even a live "leader board" ranking the top contestants.)

In March 2007, Bertoni decided he wanted to give it a crack. So he downloaded a huge set of data that Netflix put online: an enormous list showing how 480,189 of the company's customers rated 17,770 Netflix movies. When Netflix customers log into their accounts, they can rate any movie from one to five stars, to help "teach" the Netflix system what their preferences are; the average customer has rated around 200 movies, so Netflix has a lot of information about what its customers like and don't like. (The data set doesn't include any personal information — names, ages, location and gender have been stripped out.) So Bertoni began looking for patterns that would predict customer behavior — specifically, an algorithm that would guess correctly the number of stars a given user would apply to a given movie. A year and a half later, Bertoni is still going, often spending 20 hours a week working on it in his home office. His two children — 12 and 13 years old — sometimes sit and brainstorm with him. "They're very good with mathematics and algebra," he told me, chuckling. "And they think of interesting questions about your movie-watching behavior." For example, one day the kids wondered about sequels: would a Netflix user who liked the first two "Matrix" movies be just as likely to enjoy the third one, even though it was widely considered to be pretty dreadful?

Each time he or his kids think of a new approach, Bertoni writes a computer program to test it. Each new algorithm takes on average three or four hours to churn through the data on the family's "quad core" Gateway computer. Bertoni's results have gradually improved. When I last spoke to him, he was at No. 8 on the leader board; his program was 8.8 percent better than Cinematch. The top team was at 9.44 percent. Bertoni said he thought he was within striking distance of victory.

But his progress had slowed to a crawl. The more Bertoni improved upon Netflix, the harder it became to move his number forward. This wasn't just his problem, though; the other competitors say that their progress is stalling, too, as they edge toward 10 percent. Why?

Bertoni says it's partly because of "Napoleon Dynamite," an indie comedy from 2004 that achieved cult status and went on to become extremely popular on Netflix. It is, Bertoni and others have discovered, maddeningly hard to determine how much people will like it. When Bertoni runs his algorithms on regular hits like "Lethal Weapon" or "Miss Congeniality" and tries to predict how any given Netflix user will rate them, he's usually within eight-tenths of a star. But with films like "Napoleon Dynamite," he's off by an average of 1.2 stars.

The reason, Bertoni says, is that "Napoleon Dynamite" is very weird and very polarizing. It contains a lot of arch, ironic humor, including a famously kooky dance performed by the titular teenage character to help his hapless friend win a student-council election. It's the type of quirky entertainment that tends to be either loved or despised. The movie has been rated more than two million times in the Netflix database, and the ratings are disproportionately one or five stars.

Worse, close friends who normally share similar film aesthetics often heatedly disagree about whether "Napoleon Dynamite" is a masterpiece or an annoying bit of hipster self-indulgence. When Bertoni saw the movie himself with a group of friends, they argued for hours over it. "Half of them loved it, and half of them hated it," he told me. "And they couldn't really say why. It's just a difficult movie."

Mathematically speaking, "Napoleon Dynamite" is a very significant problem for the Netflix Prize. Amazingly, Bertoni has deduced that this single movie is causing 15 percent of his remaining error rate; or to put it another way, if Bertoni could anticipate whether you'd like "Napoleon Dynamite" as accurately as he can for other movies, this feat alone would bring him 15 percent of the way to winning the $1 million prize. And while "Napoleon Dynamite" is the worst culprit, it isn't the only troublemaker. A small subset of other titles have caused almost as much bedevilment among the Netflix Prize competitors. When Bertoni showed me a list of his 25 most-difficult-to-predict movies, I noticed they were all similar in some way to "Napoleon Dynamite" — culturally or politically polarizing and hard to classify, including "I Heart Huckabees," "Lost in Translation," "Fahrenheit 9/11," "The Life Aquatic With Steve Zissou," "Kill Bill: Volume 1" and "Sideways."

So this is the question that gently haunts the Netflix competition, as well as the recommendation engines used by other online stores like Amazon and iTunes. Just how predictable is human taste, anyway? And if we can't understand our own preferences, can computers really be any better at it?

IT USED TO BE THAT if you wanted to buy a book, rent a movie or shop for some music, you had to rely on flesh-and-blood judgment — yours, or that of someone you trusted. You'd go to your local store and look for new stuff, or you might just wander the aisles in what librarians call a stack search, to see if anything jumped out at you. You might check out newspaper reviews or consult your friends; if you were lucky, your local video store employed one of those young cinéastes who could size you up in a glance and suggest something suitable.

The advent of online retailing completely upended this cultural and economic ecosystem. First of all, shopping over the Web is not a social experience; there are no clever clerks to ask for advice. What's more, because they have no real space constraints, online stores like Amazon or iTunes can stock millions of titles, making a stack search essentially impossible. This creates the classic problem of choice: how do you decide among an effectively infinite number of options?

But Web sites have this significant advantage over brick-and-mortar stores: They can track everything their customers do. Every page you visit, every purchase you make, every item you rate — it is all recorded. In the early '90s, scientists working in the field of "machine learning" realized that this enormous trove of data could be used to analyze patterns in people's taste. In 1994, Pattie Maes, an M.I.T. professor, created one of the first recommendation engines by setting up a Web site where people listed songs and bands they liked. Her computer algorithm performed what's known as collaborative filtering. It would take a song you rated highly, find other people who had also rated it highly and then suggest you try a song that those people also said they liked.

"We had this realization that if we gathered together a really large group of people, like thousands or millions, they could help one another find things, because you can find patterns in what they like," Maes told me recently. "It's not necessarily the one, single smart critic that is going to find something for you, like, 'Go see this movie, go listen to this band!' "

In one sense, collaborative filtering is less personalized than a store clerk. The clerk, in theory anyway, knows a lot about you, like your age and profession and what sort of things you enjoy; she can even read your current mood. (Are you feeling lousy? Maybe it's not the day for "Apocalypse Now.") A collaborative-filtering program, in contrast, knows very little about you — only what you've bought at a Web site and whether you rated it highly or not. But the computer has numbers on its side. It may know only a little bit about you, but it also knows a little bit about a huge number of other people. This lets it detect patterns we often cannot see on our own. For example, Maes's music-recommendation system discovered that people who like classical music also like the Beatles. It is an epiphany that perhaps make sense when you think about it for a second, but it isn't immediately obvious.

Soon after Maes's work made its debut, online stores quickly understood the value of having a recommendation system, and today most Web sites selling entertainment products have one. Most of them use some variant of collaborative filtering — like Amazon's "Customers Who Bought This Item Also Bought" function. Some setups ask you to actively rate products, as Netflix does. But others also rely on passive information. They keep track of your everyday behavior, looking for clues to your preferences. (For example, many music-recommendation engines — like the Genius feature on Apple's iTunes, Microsoft's Mixview music recommender or the Audioscrobbler program at Last.fm — can register every time you listen to a song on your computer or MP3 player.) And a few rare services actually pay people to evaluate products; the Pandora music-streaming service has 50 employees who listen to songs and tag them with descriptors — "upbeat," "minor key," "prominent vocal harmonies."

Netflix came late to the party. The company opened for business in 1997, but for the first three years it offered no recommendations. This wasn't such a big problem when Netflix stocked only 1,000 titles or so, because customers could sift through those pretty quickly. But Netflix grew, and today, it stocks more than 100,000 movies. "I think that once you get beyond 1,000 choices, a recommendation system becomes critical," Hastings, the Netflix C.E.O., told me. "People have limited cognitive time they want to spend on picking a movie."

Cinematch was introduced in 2000, but the first version worked poorly — "a mix of insightful and boneheaded recommendations," according to Hastings. His programmers slowly began improving the algorithms. They could tell how much better they were getting by trying to replicate how a customer rated movies in the past. They took the customer's ratings from, say, 2001, and used them to predict their ratings for 2002. Because Netflix actually had those later ratings, it could discern what a "perfect" prediction would look like. Soon, Cinematch reached the point where it could tease out some fairly nuanced — and surprising — connections. For example, it found that people who enjoy "The Patriot" also tend to like "Pearl Harbor," which you'd expect, since they're both history-war-action movies; but it also discovered that they like the heartstring-tugging drama "Pay It Forward" and the sci-fi movie "I, Robot."

Cinematch has, in fact, become a video-store roboclerk: its suggestions now drive a surprising 60 percent of Netflix's rentals. It also often steers a customer's attention away from big-grossing hits toward smaller, independent movies. Traditional video stores depend on hits; just-out-of-the-theaters blockbusters account for 80 percent of what they rent. At Netflix, by contrast, 70 percent of what it sends out is from the backlist — older movies or small, independent ones. A good recommendation system, in other words, does not merely help people find new stuff. As Netflix has discovered, it also spurs them to consume more stuff.

For Netflix, this is doubly important. Customers pay a flat monthly rate, generally $16.99 (although cheaper plans are available), to check out as many movies as they want. The problem with this business model is that new members often have a couple of dozen movies in mind that they want to see, but after that they're not sure what to check out next, and their requests slow. And a customer paying $17 a month for only one movie every month or two is at risk of canceling his subscription; the plan makes financial sense, from a user's point of view, only if you rent a lot of movies. (My wife and I once quit Netflix for precisely this reason.) Every time Hastings increases the quality of Cinematch even slightly, it keeps his customers active.

But by 2006, Cinematch's improving performance had plateaued. Netflix's programmers couldn't go any further on their own. They suspected that there was a big breakthrough out there; the science of recommendation systems was booming, and computer scientists were publishing hundreds of papers each year on the subject. At a staff meeting in the summer of 2006, Hastings suggested a radical idea: Why not have a public contest? Netflix's recommendation system was powered by the wisdom of crowds; now it would tap the wisdom of crowds to get better too.

AS HASTINGS HOPED, the contest has galvanized nerds around the world. The Top 10 list for the Netflix Prize currently includes a group of programmers in Austria (who are at No. 2), a trained psychologist and Web consultant in Britain who uses his teenage daughter to perform his calculus (No. 9), a lone Ph.D. candidate in Boston who calls himself My Brain and His Chain (a reference to a Ben Folds song; he's at No. 6) and Pragmatic Theory — two French-Canadian guys in Montreal (No. 3). Nearly every team is working on the prize in its spare time. In October, when I dropped by the house of Martin Chabbert, a 32-year-old member of the Pragmatic Theory duo, it was only 8:30 at night, but we had to whisper: his four children, including a 2-month-old baby, had just gone to bed upstairs. In his small dining room, a laptop sat open next to children's books like "Les Robots: Au Service de L'homme" and a "Star Wars" picture book in French.

"This is where I do everything," Chabbert said. "After the kids are asleep and I've packed the lunches for school, I come down at 9 in the evening and work until 11 or 12. It was very exciting in the beginning!" He laughed. "It still is, but with the baby now, going to bed at midnight is not a good idea."

Pragmatic Theory formed last spring, when Chabbert's longtime friend Martin Piotte — a 43-year-old electrical and computer engineer — heard about the Netflix Prize. Like many of the amateurs trying to win the $1 million, they had no relevant expertise. ("Absolutely no background in statistics that was useful," Piotte told me ruefully. "Two guys, absolutely no clue.") But they soon discovered that the Netflix competition is a fairly collegial affair. The company hosts a discussion board devoted to the prize, and competitors frequently help one another out — discussing algorithms they've tried and publicly brainstorming new ways to improve their work, sometimes even posting reams of computer code for anyone to use. When someone makes a breakthrough, pretty soon every other team is aware of it and starts using it, too. Piotte and Chabbert soon learned the major mathematical tricks that had propelled the leading teams into the Top 10.

The first major breakthrough came less than a month into the competition. A team named Simon Funk vaulted from nowhere into the No. 4 position, improving upon Cinematch by 3.88 percent in one fell swoop. Its secret was a mathematical technique called singular value decomposition. It isn't new; mathematicians have used it for years to make sense of prodigious chunks of information. But Netflix never thought to try it on movies.

Singular value decomposition works by uncovering "factors" that Netflix customers like or don't like. Say, for example, that "Sleepless in Seattle" has been rated by 200,000 Netflix users. In one sense, this is just a huge list of numbers — user No. 452 gave it two stars; No. 985 gave it five stars; and so on. But you could also think of those ratings as individual reactions to various aspects of the movie. "Sleepless in Seattle" is a "chick flick," a comedy, a star vehicle for Tom Hanks; each customer is reacting to how much — or how little — he or she likes "chick flicks," comedies and Tom Hanks. Singular value decomposition takes the mass of Netflix data — 17,770 movies, ratings by 480,189 users — and automatically sorts the films. The programmers do not actively tell the computer what to look for; they just run the algorithm until it groups together movies that share qualities with predictive value.

Sometimes when you look at the clusters of movies, you can deduce the connections. Chabbert showed me one list: at the top were "Sleepless in Seattle," "Steel Magnolias" and "Pretty Woman," while at the bottom were "Star Trek" movies. Clearly, the computer recognized some factor that suggests that someone who likes the romantic aspect of "Pretty Woman" will probably like "Sleepless in Seattle" and dislike "Star Trek." Chabbert showed me another cluster: this time DVD collections of the TV show "Friends" all clustered at the top of the list, while action movies like "Reindeer Games" and thrillers like "Hannibal" clustered at the bottom. Most likely, the computer had selected for "comic" content here. Other lists appear to group movies based on whether they lean strongly to the ideological right or left.

As programmers extract more and more values, it becomes possible to draw exceedingly sophisticated correlations among movies and hence to offer incredibly nuanced recommendations. "We're teasing out very subtle human behaviors," said Chris Volinsky, a scientist with AT&T in New Jersey who is one of the most successful Netflix contestants; his three-person team held the No. 1 position for more than a year. His team relies, in part, on singular value decomposition. "You can find things like 'People who like action movies, but only if there's a lot of explosions, and not if there's a lot of blood. And maybe they don't like profanity,' " Volinsky told me when we spoke recently. "Or it's like 'I like action movies, but not if they have Keanu Reeves and not if there's a bus involved.' "

MOST OF THE LEADING TEAMS competing for the Netflix Prize now use singular value decomposition. Indeed, given how quickly word of new breakthroughs spreads among the competitors, virtually every team in the Top 10 makes use of similar mathematical ploys. The only thing that separates their scores is how skillfully they tweak their algorithms. The Netflix Prize has come to resemble a drag race in which everyone drives the same car, with only tiny modifications to the fuel injection. Yet those tweaks are crucial. Since the top teams are so close — there is less than a tenth of a percent between each contender — even tiny improvements can boost a team to the top of the charts.

These days, the competitors spend much of their time thinking deeply about the math and psychology behind recommendations. For example, the teams are grappling with the problem that over time, people can change how sternly or leniently they rate movies. Psychological studies show that if you ask someone to rate a movie and then, a month later, ask him to do so again, the rating varies by an average of 0.4 stars. "The question is why," Len Bertoni said to me. "Did you just remember it differently? Did you see something in between? Did something change in your life that made you rethink it?" Some teams deal with this by programming their computers to gradually discount older ratings.

Another common problem is identifying overly punitive raters. If you're a really harsh critic and I'm a much more easygoing one, your two-star rating may be equal to my four-star rating. To compensate, an algorithm might try to detect when a Netflix customer tends to hand out only one- or two-star ratings — a sign of a strict, pursed-lip customer — and artificially boost his or her ratings by a half-star or so. Then there's the problem of movie raters who simply aren't consistent. They might be evenhanded most of the time, but if they log into Netflix when they're in a particularly bad mood, they might impulsively decide to rate a couple of dozen movies harshly.

TV shows, which are hot commodities on Netflix, present yet another perplexing issue. Customers respond to TV series much differently than they do to movies. People who loved the first two seasons of "The Wire" might start getting bored during the third but keep on watching for a while, then stop abruptly. So when should Cinematch stop recommending "The Wire"? When do you tell someone to give up on a TV show?

Interestingly, the Netflix Prize competitors do not know anything about the demographics of the customers whose taste they're trying to predict. The teams sometimes argue on the discussion board about whether their predictions would be better if they knew that customer No. 465 is, for example, a 23-year-old woman in Arizona. Yet most of the leading teams say that personal information is not very useful, because it's too crude. As one team pointed out to me, the fact that I'm a 40-year-old West Village resident is not very predictive. There's little reason to think the other 40-year-old men on my block enjoy the same movies as I do. In contrast, the Netflix data are much more rich in meaning. When I tell Netflix that I think Woody Allen's black comedy "Match Point" deserves three stars but the Joss Whedon sci-fi film "Serenity" is a five-star masterpiece, this reveals quite a lot about my taste. Indeed, Reed Hastings told me that even though Netflix has a good deal of demographic information about its users, the company does not currently use it much to generate movie recommendations; merely knowing who people are, paradoxically, isn't very predictive of their movie tastes.

As the teams have grown better at predicting human preferences, the more incomprehensible their computer programs have become, even to their creators. Each team has lined up a gantlet of scores of algorithms, each one analyzing a slightly different correlation between movies and users. The upshot is that while the teams are producing ever-more-accurate recommendations, they cannot precisely explain how they're doing this. Chris Volinsky admits that his team's program has become a black box, its internal logic unknowable.

There's a sort of unsettling, alien quality to their computers' results. When the teams examine the ways that singular value decomposition is slotting movies into categories, sometimes it makes sense to them — as when the computer highlights what appears to be some essence of nerdiness in a bunch of sci-fi movies. But many categorizations are now so obscure that they cannot see the reasoning behind them. Possibly the algorithms are finding connections so deep and subconscious that customers themselves wouldn't even recognize them. At one point, Chabbert showed me a list of movies that his algorithm had discovered share some ineffable similarity; it includes a historical movie, "Joan of Arc," a wrestling video, "W.W.E.: SummerSlam 2004," the comedy "It Had to Be You" and a version of Charles Dickens's "Bleak House." For the life of me, I can't figure out what possible connection they have, but Chabbert assures me that this singular value decomposition scored 4 percent higher than Cinematch — so it must be doing something right. As Volinsky surmised, "They're able to tease out all of these things that we would never, ever think of ourselves." The machine may be understanding something about us that we do not understand ourselves.

Yet it's clear that something is still missing. Volinsky's momentum has slowed down significantly, as everyone else's has. There's some X factor in human judgment that the current bunch of algorithms isn't capturing when it comes to movies like "Napoleon Dynamite." And the problem looms large. Bertoni is currently at 8.8 percent; he says that a small group of mainly independent movies represents more than half of the remaining errors in the way of winning the prize. Most teams suspect that continuing to tweak existing algorithms won't be enough to get to 10 percent. They need another breakthrough — some way to digitally replicate the love/hate dynamic that governs hard-to-pigeonhole indie films.

"This last half-percent really is the Mount Everest," Volinsky said. "It's going to take one of these 'aha' moments."

SOME COMPUTER SCIENTISTS think the "Napoleon Dynamite" problem exposes a serious weakness of computers. They cannot anticipate the eccentric ways that real people actually decide to take a chance on a movie.

The Cinematch system, like any recommendation engine, assumes that your taste is static and unchanging. The computer looks at all the movies you've rated in the past, finds the trend and uses that to guide you. But the reality is that our cultural tastes evolve, and they change in part because we interact with others. You hear your friends gushing about "Mad Men," so eventually — even though you have never had any particular interest in early-'60s America — you give it a try. Or you go into the video store and run into a particularly charismatic clerk who persuades you that you really, really have to give "The Life Aquatic With Steve Zissou" a chance.

As Gavin Potter, a Netflix Prize competitor who lives in Britain and is currently in ninth place, pointed out to me, a computerized recommendation system seeks to find the common threads in millions of people's recommendations, so it inherently avoids extremes. Video-store clerks, on the other hand, are influenced by their own idiosyncrasies. Even if they're considering your taste to make a suitable recommendation, they can't help relying on their own sense of what's good and bad. They'll make more mistakes than the Netflix computers — but they're also more likely to have flashes of inspiration, like pointing you to "Napoleon Dynamite" at just the right moment.

"If you use a computerized system based on ratings, you will tend to get very relevant but safe answers," Potter says. "If you go with the movie-store clerk, you will get more unpredictable but potentially more exciting recommendations."

Another critic of computer recommendations is, oddly enough, Pattie Maes, the M.I.T. professor. She notes that there's something slightly antisocial — "narrow-minded" — about hyperpersonalized recommendation systems. Sure, it's good to have a computer find more of what you already like. But culture isn't experienced in solitude. We also consume shows and movies and music as a way of participating in society. That social need can override the question of whether or not we'll like the movie.

"You don't want to see a movie just because you think it's going to be good," Maes says. "It's also because everyone at school or work is going to be talking about it, and you want to be able to talk about it, too." Maes told me that a while ago she rented a "Sex and the City" DVD from Netflix. She suspected she probably wouldn't really like the show. "But everybody else was constantly talking about it, and I had to know what they were talking about," she says. "So even though I would have been embarrassed if Netflix suggested 'Sex and the City' to me, I'm glad I saw it, because now I get it. I know all the in-jokes."

Maes suspects that in the future, computer-based reasoning will become less important for online retailers than social-networking tools that tap into the social zeitgeist, that let customers see, in Facebook fashion, for example, what their close friends are watching and buying. (Potter has an even more intriguing idea. He says he thinks that a recommendation system could predict cultural microtrends by monitoring news events. His research has found, for example, that people rent more movies about Wall Street when the stock market drops.) In the world of music, there are already several innovative recommendation services that try to analyze buzz — by monitoring blogs for repeated mentions of up-and-coming bands, or by sifting through millions of people's playlists to see if a new band is suddenly getting a lot of attention.

Of course, for a company like Netflix, there's a downside to pushing exciting-but-risky movie recommendations on viewers. If Netflix tries to stretch your taste by recommending more daring movies, it also risks annoying customers. A bad movie recommendation can waste an evening.

Is there any way to find a golden mean? When I put the question to Reed Hastings, the Netflix C.E.O., he told me he suspects that there won't be any simple answer. The company needs better algorithms; it needs breakthrough techniques like singular value decomposition, with the brilliant but inscrutable insights it enables. But Hastings also says he thinks Maes is right, too, and that social-networking tools will become more useful. (Netflix already has one, in fact — an application that lets users see what their family and peers are renting. But Hastings admits it hasn't been as valuable as computerized intelligence; only a very small percentage of rentals are driven by what friends have chosen.) Hastings is even considering hiring cinephiles to watch all 100,000 movies in the Netflix library and write up, by hand, pages of adjectives describing each movie, a cloud of tags that would offer a subjective view of what makes films similar or dissimilar. It might imbue Cinematch with more unpredictable, humanlike intelligence.

"Human beings are very quirky and individualistic, and wonderfully idiosyncratic," Hastings says. "And while I love that about human beings, it makes it hard to figure out what they like."

Clive Thompson, a contributing writer for the magazine, writes frequently about technology.

Homework 3 solutions posted; two questions for Homework 4 posted

2008-11-20T14:40:00.000-08:00

FYI

rao

Today's Office Hours

2008-11-19T13:08:00.001-08:00

Since several students have expressed interested in talking during today’s office hours, I’ll plan on sitting in the 2^nd floor lab rather than on the 5^th floor. I’m also planning to extend the office hours from 3pm – 5pm to make sure all the questions get answered. If you have questions/concerns about project 3, feel free to stop by.

Garrett

Thinking Cap questions: The Lame-Duck edition

2008-11-19T06:08:00.001-08:00

First, a link:

Here is a link to the "Chinese room" argument: http://en.wikipedia.org/wiki/Chinese_Room

-------------------

Here are some points to ponder on the recent topics:

0 (don't need to answer on blog): We talked a lot about syntax and semantics. Using English as the example, think of (a) whether
an ungrammatical sentence can have semantics (b) a sentence with "no meaning" can be grammatically correct.
Consider the famous example: "Colorless green ideas sleep furiously." (Check out
http://rakaposhi.eas.asu.edu/f06-cse471-mailarchive/msg00090.html for the history of that sentence...)

1. We talked about the fact that XML is a syntactic standard and doesn;t have semantics. Do relational databases have
semantics? (And if so, then won't a conversion of a relational database to an XML form preserve those semantics?)

Consider the case of the use of the database by someone who knows and understands the database schema as well as a
lay user that doesn't

[In thinking about semantics, it is useful to think in terms of the "worlds" that are consistent with a data/knowledge base.
You will say that a formal sentence has semantics if you can enumerate worlds where it is going to be true (or alternately,
given a completely specified world, you can tell whether or not that sentence is "true" in that world. As you add more and more
sentences to a knowledge base, you constrain the number of worlds that are consistent with it.]

2. Here is a question that one of the students asked after the class: We said XML can be viewed either as ordered or unordered.
From a DB perspective, we would like to see it as unordered and from an IR perspective we would like to see it as ordered.
The question is what, if any, is the disadvantage of assuming that XML is always ordered? More specifically what is the loss from the
database side if we unilaterally decide that XML is ordered whether or not it was intended in such a way?

Current Cumulatives

2008-11-14T07:45:00.000-08:00

Folks:

To give you an idea of where things stand, and also to catch any errors in the current grade sheet, I am enclosing a current snapshot.

I combined the project/homework/midterm marks into a cumulative--currently I took midterm to be 20%, homeworks to be 5% each and projects
to be 10% each. Please note that this weighting is subject to change (I have, in the past, computed cumulatives with three or four different
weigtings and taken the maximum of those). Nevertheless, they will give you an approximate idea of your class standing.

Let me know if you have questions.

regards
Rao

ps: The 598 students are listed first and then 494 students (separated from them). Each list is sorted in the descending order of cumulative.
The "percentage" column shows the current percentage (i.e. your current total out of 50, extrapolated to 100).

Farenheit 451 and other references from today's class...

2008-11-13T14:23:00.001-08:00

Folks
Sorry--I mis-spoke re: the title of Ray Bradbury's book. It is Farenheit 451-- (451 being the temperature where paper burns).

http://en.wikipedia.org/wiki/Fahrenheit_451

Also, we are finally coming to the part of the course that actually intersects with research done in my group (which also means I am likely to be
less objective--caveat emptor..).

Relevant publications from my group can be found at http://rakaposhi.eas.asu.edu/i3/

cheers
Rao

Re: NBC question

2008-11-12T13:51:00.001-08:00

Probability of example--yes--that can be ignored. Just show k*what you got

Rao

ps:

[Notice that it is not all that hard to compute it too.

Suppose you are computing P(C|E) and you write it as k*0.33
Now, suppose you also compute P(~C|E) (where ~C means it is not in class C)-- this too will have P(E) in the denominator and so it too will have the same k factor. Suppose it is k*0.44

now, you know that P(C|E) + P(~C|E) will be 1.0.

So k*0.33+k*0.44 = 1
k = 1/0.77

On Wed, Nov 12, 2008 at 2:43 PM, Balzer, Michael J (Mike) <Michael.Balzer@asu.edu> wrote:

Hi Dr. Rao,

Regarding P(E), or, P(D) in NBC, just wanted to clarify – since this is a common factor, then it can be safely ignored, correct? In your example slide (willwait), I think you show this as "k" in the calculation. In the homework, do we just show this as k in the final answer?

Thanks again,

Mike Balzer

Re: Doubt about Q3 of homework 3

2008-11-11T20:12:00.001-08:00

You use the same distance/similarity measure as in Qn 2.

Rao

On Tue, Nov 11, 2008 at 5:06 PM, Durga Bidaye <dbidaye@asu.edu> wrote:

Hello Prof Rao

I have a doubt about Q3 of Homework 3. In Q3, we are supposed to do agglomerative clustering on documents given in the previous question. Also, for inter-cluster similarity, we are supposed to use single link distance. However, nothing has been specified about the similarity measure to be used for finding the similarity(distance) between the individual documents themselves. Are we supposed to use the same measure as the previous question ie. 'Bag based similarity' or we are supposed to use something else. Thank you.

Regards
Durga

Re: Doubt Q2

2008-11-11T08:30:00.001-08:00

Yes, taking (1-sim(c,d)) would be a fine way to convert similarity into distance (assuming of course that the similarity is between 0 and 1).

Rao

On Mon, Nov 10, 2008 at 7:25 PM, suganthi cidambaram <Suganthi.Cidambaram@asu.edu> wrote:

Dear Dr. Rao

Question2 asks us to find cluster dissimilarity measure ( which is defined as the sum of similarities of docs from their resp. cluster centers). But here we are using Jaccard similarity, so was wondering how would the sum of similarity give the dissimilarity. Summation seems to make sense for Euclidean Dist.

So should I be doing summation of (1-sim(c,d)) when using Jaccard Sim.

Thank You.

Regards

Suganthi

homework 3 assigned; due next thursday Nov 13th

2008-11-06T09:34:00.001-08:00

Folks:

I posted homework 3--with five questions. The homework is due in class next Thursday (it is a "traditional" homework in that I posted all questions at once).

To give you a heads-up, there will be one more homework before the end of the semester. For this one, I will try to add questions as soon as topics are covered in the class. The last homework will be due before the end of the semester.

Rao

Fwd: (this time with 598/494 demarcation shown) midterm grades (marks by posting-id)

2008-11-05T11:20:00.001-08:00

---------- Forwarded message ----------
From: Subbarao Kambhampati <rao@asu.edu>
Date: Wed, Nov 5, 2008 at 12:17 PM
Subject: midterm grades (marks by posting-id)
To: Rao Kambhampati <rao@asu.edu>

Midterm
65pts	Posting ID [598Section]
31.5	1662 489
34	7309 235
32.5	2863 440
41	9443 694
40	8868 882
49.5	2568 845
57.5	4005 448
26	3902 511
53.5	1483 115
44	5123 179
57	4621 611
28	6760 290
49	2446 400
42	9882 896
46.5	7381 412
47.5	2550 408
46.5	2908 344
27	7712 852
43	6111 673
47.5	3823 434
40.5	5052 059
48	5980 640
58.5	0721 546
42.5	2429 154
31.5	9993 347
54	0819 963
22	8121 455
45	2979 440
30.5	0657 616
48.5	6348 736

54	3397 715 [494section]
27	4119 801
44.5	2816 467
45	6201 263
	2775 346
	9807 132
10	4726 012
52.5	1385 631

2
	Stats All
58.5	max
10	min
41.60	avg
11.23	stddev
	Just 598
58.5	max
22	min
42.53	avg
10.06	stddev
	just 494
52.5	max
10	min
35.8	avg
17.19	stddev

midterm grades (marks by posting-id)

2008-11-05T11:17:00.001-08:00

Midterm
65pts	Posting ID
31.5	1662 489
34	7309 235
32.5	2863 440
41	9443 694
40	8868 882
49.5	2568 845
57.5	4005 448
26	3902 511
53.5	1483 115
44	5123 179
57	4621 611
28	6760 290
49	2446 400
42	9882 896
46.5	7381 412
47.5	2550 408
46.5	2908 344
27	7712 852
43	6111 673
47.5	3823 434
40.5	5052 059
48	5980 640
58.5	0721 546
42.5	2429 154
31.5	9993 347
54	0819 963
22	8121 455
45	2979 440
30.5	0657 616
48.5	6348 736
54	3397 715
27	4119 801
44.5	2816 467
45	6201 263
	2775 346
	9807 132
10	4726 012
52.5	1385 631

2
	Stats All
58.5	max
10	min
41.60	avg
11.23	stddev
	Just 598
58.5	max
22	min
42.53	avg
10.06	stddev
	just 494
52.5	max
10	min
35.8	avg
17.19	stddev

Office Hours Location

2008-10-29T14:38:00.001-07:00

Given that the project is due tomorrow there's a chance more students might show up to today's office hours so if you plan to come, I'll be having my office hours in the 2nd floor lab instead of on the fifth floor.

Thanks,
Garrett

Next topic: Text classification (required reading: Chapter 14 of Manning et al's book)

2008-10-29T09:51:00.001-07:00

Our next topic is classification techniques. Classification is an enormous area and entire courses are devoted to it.
We will only spend about 1.5 classes on it and get a birds eye view of the main issues, and look at Naive Bayes Classifier--a techniques that works about as well
as a default strategy in text classification as K-means does as a default strategy for clustering.

The classification techniques are also useful in content-based filtering (which will come up in the discussion of recommender systems to start next week).

The reading for tomorrow is chapter 14 of Manning et al's book

rao

Lost Backpack

2008-10-28T18:33:00.001-07:00

I noticed a backpack sitting on the ground in the second floor lab near where I was sitting for office hours. Did one of you leave your bag by chance?

Garrett

Project 2 Fix

2008-10-28T13:55:00.000-07:00

It was pointed out that some of the pages in the LinkExtract file have a space at the beginning of their name and therefore might not be matched when provided with the name w/o the space. Some of you have worked around this but if you are having problems, there are two quick solutions to this problem.

1) Simply edit the Hashedlinks file replacing ", " with "," (replace comma followed by space with just a comma)

2) Edit the LinkExtract.java file and add the following after this line in the constructor sin = sin.substring(sin.indexOf("[")+1,sin.indexOf("]"));

sin = sin.replace(", ", ",").trim();

You can add this line yourself and recompile or you can download the updated file from here (didn't want the java file to get caught by virus checker)

http://asu.mine.nu/CSE494/LinkExtract.zip

Garrett

Additional Office Hours

2008-10-28T12:20:00.001-07:00

Just a reminder that today I'll be holding additional office hours in
the 2nd floor lab. I will be there right after today's class for
those that may have last minute questions regarding the project 2.

Garrett

Additional Office Hours

2008-10-27T19:53:00.000-07:00

Several students have expressed interest in meeting tomorrow so I will be holding additional office hours right after the class. Due to the number of students I’m planning to meet, I’ll be holding the office hours in the 2^nd floor lab. I’ll be answering questions regarding the project and the basic approach/algorithm or other similar issues you may be having. Please don’t come expecting a lesson in Java or help debugging your code as I want to give priority to those students who are having trouble with the actual approach or who need some clarification regarding the project description.

Thanks,

Garrett

GAAP (Grade Anxiety Amelioration Program)

2008-10-27T15:27:00.000-07:00

As the drop date is approaching, I am getting mails from people worried about their grades.
I haven't completed mid-term grading and am not likely to get done this week because of some other
pressing deadlines.

As I said, I don't go with 95-->A+; 90-->A sort of scale. So, you shouldn't worry too much based just on your
cumulatives.

I also recognize that people who can't keep up with the demands of the course leave--thus I normally don't have the
same kind of bottom distribution as might be present in other classes.

My general advice to anyone who has come up to this point in the course and has done all assignments, and is enjoying the
course, is to de-stress (note the "de" not "di") and continue. Your personal mileage of course may vary.

Rao

ps: If it helps, here are the final cumulatives and the actual reported grades for a previous offering of this course. The first
three are 471 and the rest are 598. This is for illustrative purposes.
There are *no* implicit guarantees that if you get those points, you will get those grades. If you have other questions, feel free to
send me email either directly are anonymously.




88.40	A+
79.57	A
62.83	B

91.97	A+
90.61	A+
87.55	A+
85.76	A
85.11	A
84.34	A
84.00	A
83.88	A
83.85	A
81.27	A-
79.92	B+
78.76	B+
78.63	B+
74.76	B
69.64	B
69.35	B

Project 2 Due Date Approaching

2008-10-27T10:49:00.000-07:00

I’ve heard from a few of you regarding project 2, so I’m assuming the rest of you aren’t having any issues so far. If it would be helpful, I can hold additional office hours before or after the class tomorrow because as you know, the project due date is posted as this Thursday the 30^th.

If anyone is interested, let me know and I will fix a time.

Garrett

Fwd: Faculty Seminar Series Presentation on October 24th 2008 (Friday) by Professor Arun Sen: ORG-ENG-CSE_Online_Com

2008-10-23T22:16:00.001-07:00

Folks:

We have an embarrassment of riches tomorrow--as far as talks relevant to CSE494 go. You already know about Zaiqing Nie's talk on Object level search in the morning.
This talk by Prof. Sen will likely be connected to and/or extend the class discussion on social networks. Hope you can make it and enjoy both talks.

Rao

---------- Forwarded message ----------
From: Chitta Baral <chitta.baral@asu.edu>
Date: Thu, Oct 23, 2008 at 9:57 PM
Subject: Faculty Seminar Series Presentation on October 24th 2008 (Friday) by Professor Arun Sen: ORG-ENG-CSE_Online_Com
To: "ORG-ENG-CSE_Online_Com"

(Students are most welcome to these Faculty seminar series presentations.)

Date: Oct 24th 2008
Time: 3:00 PM (cookies and coffee from 2:45 PM)
Place: BYAC 110 (Same place as in previous weeks)

Title : A hitchhiker's guide to Network Science

By: Prof. Arun Sen

Abstract:

Network Science is a newly emerging discipline that draws upon a variety of well established disciplines, such as, Graph theory, Game Theory, Probability Theory, Algorithms and Complexity Theory, Machine Learning and Data Mining. The techniques from Network Science can be applied to a variety of application domains, Computer Networks, Electric Power Grid Networks, Social Networks, Transportation Networks and Biological Networks, to just name a few. In this talk we will undertake a journey through the galaxy of networks and find out how basic tenets of Network Science rule all these different planets.

Next topic: Clustering--readings are chapters 16&17 from manning et al IR book (as linked)

2008-10-23T10:29:00.000-07:00

My slides are up.

rao

Reminder: Talk tomorrow by Zaiqing Nie (ASU Alumnus; currently at Microsoft Research) on 10/24 on "Object-level Web Search"

2008-10-23T09:52:00.001-07:00

[If you are interested in talking to Nie one-on-one, let me know.]

Title: Object-level Web Search

Speaker: Zaiqing Nie, Lead Researcher, Microsoft Research Asia.

Venue: Room BY 210; 10/24; 10:30 AM

Abstract:

Current Web search engine can be considered a page-level general search engine whose main functionality is to rank web pages according to their relevance to a given query. However, there are various kinds of objects embedded in static Web pages or Web databases. Typical objects are people, products, papers, organizations, etc. We can imagine that if these objects can be extracted and integrated from the Web, powerful object-level search engines can be built to meet users' information needs more precisely. In this talk, I will discuss this new trend on building what we call "object-level search engines". The research problems that we need to address include large scale web classification, object-level information extraction, object identification and integration, and object relationship mining and ranking. I introduce the overview and core technologies of object-level search engines that have been implemented in three working systems: Libra Academic Search (http://libra.msra.cn), Windows Live Product Search (http://products.live.com), and Guanxi – a search engine for entity relationship discovery (http://renlifang.msra.cn).

Bio:

Zaiqing Nie is a lead researcher in the Web Search & Mining Group at Microsoft Research Asia. He graduated in May 2004 with a Ph.D. in Computer Science from Arizona State University. He received both his Master and Bachelor of Engineering degree in Computer Science from Tsinghua University. His research interests include data mining, machine learning, Web information integration and retrieval. Nie has many publications in prestigious conferences and journals including SIGKDD, ICML, WWW, CIDR, ICDE, TKDE, and JMLR. His recent academic activities include program committee co-chair of IIWeb 2007 and program committee member of KDD 2008, SIGIR 2008, WWW 2008, ICML 2008, ACL 2008, AAAI 2008 etc. Some technologies he developed have been transferred to Microsoft products/services including Windows Live Product Search and Windows Live Search in China, Libra Academic Search, and Renlifang Guanxi Search.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Re: About Calculator

2008-10-21T12:52:00.001-07:00

Rainforests schmainforests. What'd they ever done for us other than providing a breeding ground for billiard-ball sized mosquitoes?

But if you insist, use of laptops to look at slides and calc.exe is fine (I thought I already mentioned this..but may be not)

Rao

On Tue, Oct 21, 2008 at 12:14 PM, Nicholas Vaidyanathan <Nicholas.Vaidyanathan@asu.edu> wrote:

Similarly, I store all my notes on my laptop and would like to avoid contributing to wasted paper and destruction of rainforests...can I keep the slides and calc.exe open and use it (no trawling the net, etc etc)?

On Tue, Oct 21, 2008 at 7:42 AM, Subbarao Kambhampati <rao@asu.edu> wrote:

This would be fine. Honor code will be enforced.

rao

ps: The innumeracy of America seems to be on the raise. The "calculator" related questions seem to be the single largest class of questions I have received :-( May be on Thursday we should do Kumon...

On Mon, Oct 20, 2008 at 11:26 PM, Farooq Khera <fkhera@asu.edu> wrote:

can we use a regular calculator and just promise not to use the matrix functionality cuz i'm sure most engineers only own one calculator, usually the texas instruments kind.

On Mon, Oct 20, 2008 at 9:43 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

Yes--basic calculators will be allowed (but not those with matrix or vector operations).

rao

On Mon, Oct 20, 2008 at 3:30 PM, Shuiwang Ji <shuiwang.ji@gmail.com> wrote:

Prof. Rao,

Is calculator (with basic arithmetic functionality) allowed for the exam?

Thanks,

Shuiwang

--
Namaste,
Nicholas Vaidyanathan
Doctoral Student @ Arizona State University
President of IEEE CS Society (2008)
School of Computing and Informatics

Re: About Calculator

2008-10-21T07:42:00.001-07:00

This would be fine. Honor code will be enforced.

rao

ps: The innumeracy of America seems to be on the raise. The "calculator" related questions seem to be the single largest class of questions I have received :-( May be on Thursday we should do Kumon...

On Mon, Oct 20, 2008 at 11:26 PM, Farooq Khera <fkhera@asu.edu> wrote:

can we use a regular calculator and just promise not to use the matrix functionality cuz i'm sure most engineers only own one calculator, usually the texas instruments kind.

On Mon, Oct 20, 2008 at 9:43 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

Yes--basic calculators will be allowed (but not those with matrix or vector operations).

rao

On Mon, Oct 20, 2008 at 3:30 PM, Shuiwang Ji <shuiwang.ji@gmail.com> wrote:

Prof. Rao,

Is calculator (with basic arithmetic functionality) allowed for the exam?

Thanks,

Shuiwang

Re: About Calculator

2008-10-20T21:43:00.001-07:00

Yes--basic calculators will be allowed (but not those with matrix or vector operations).

rao

On Mon, Oct 20, 2008 at 3:30 PM, Shuiwang Ji <shuiwang.ji@gmail.com> wrote:

Prof. Rao,

Is calculator (with basic arithmetic functionality) allowed for the exam?

Thanks,

Shuiwang

Re: Doubt on random graphs

2008-10-20T20:38:00.001-07:00

Sorry. The 1/2*N^2 is a mistake That is the *total number* of edges in a complete graph. k is the average degree--i.e. the number of edges each vertex is involved in. For complete graphs, it is N-1 or approx N (there is an edge from each vertex to each of the other vertices).

I corrected the slide.

Rao

On Mon, Oct 20, 2008 at 8:21 PM, Mithila Nagendra <mnagendr@asu.edu> wrote:

Hello Dr. Rao

In the slides for random graphs, there is point where the expected degree k for p=1.0 is given as equal to 1/2N^2. The following slide says that k=N for p=1.0, this makes sense since k=pN. I dont understand how p can also equal 1/2N^2.

Thank you

Mithila Nagendra

(should work now) Re: answers to qn 5 & 6 of hw2 posted online

2008-10-20T15:09:00.000-07:00

it should work now...

rao

On Mon, Oct 20, 2008 at 2:51 PM, Garrett Wolf <Garrett.Wolf@asu.edu> wrote:

FYI - the link to the additional solutions is not working...

On Mon, Oct 20, 2008 at 2:45 PM, Subbarao Kambhampati <rao@asu.edu> wrote:

answers to qn 5 & 6 of hw2 posted online

2008-10-20T14:45:00.001-07:00

qn re: the use of Rocchio method

2008-10-20T13:13:00.001-07:00

while doc-doc similarity computation can be costlier than doc-short-query similarity, it is still considered small (afterall you will have to do that to cluster documents, for example).

Having said that, the most obvious place the current search engines use this method is when you click "similar results" link under any result. (see also the discussion in http://nlp.stanford.edu/IR-book/html/htmledition/relevance-feedback-on-the-web-1.html )

rao

On Mon, Oct 20, 2008 at 10:58 AM, Liang Sun <sun.liang@asu.edu> wrote:

Dear Prof.
I have one question about the Rocchino method. In Rocchino method, we use document to update the query. Initially, the query is very short. However, after feedback, the query is very long, and its length is comparable to that of the document. Thus, it may take a long time to compute the similarity between the new query and the documents. My question is, is Rocchino method used in real IR system, e.g., Google? Thanks.

On Mon, Oct 20, 2008 at 9:23 AM, Subbarao Kambhampati <rao@asu.edu> wrote:

Recall that in relevance feedback, we show K docs to the user, who marks r of them to be relevant (and thus K-r of them to be irrelevant). We then compute the new query as alpha* old query + beta* (sum of relevant doc vectors)/r + gamma * (sum of irrelevant doc vectors)/(K-r).

Since we are showing only *one* document to the user (K=1) , and the user says it is relevant (r=1), we have to assume that the number of irrelevant documents that we have shown until now is 0; which means that gamma factor becomes zero.
[You can't assume that 1023 are irrelevant documents--we haven't shown them to the user--so how do we know that she would have found them to be irrelevant?]

3.[3pt] Suppose the user is shown D in response to the query Q, and the user says
that D is relevant to his query. If we now use relevance feedback to modify Q, what
will the query vector become? Assume that alpha, beta and gamma are all 1.

rao

On Wed, Oct 15, 2008 at 8:59 AM, Farooq Khera <fkhera@asu.edu> wrote:

You were going to provide some insight about the specimen midterm about the question of Relevance feedback in reference to Irrelevant documents?
I was confused about how you calculate the sum of the irrelevant documents. It would seem there are 1023 irrelvant documents.
and so we know the size of irrelvant documents, such that part of the formula is Gama/#of irrelvant documents * (Sum of (irrelvant document vectors))

However its not well defined what the irrelevant document vectors are?
Unless somehow you can just take the whole corpus as a vector and then just subtract whatever the relevant document parts... which makes sense now i think lol...

-Farooq Khera

--
Liang Sun
Research Associate
Department of Computer Science & Engineering
Arizona State University

Re: midterm is open notes/book?

2008-10-20T09:33:00.001-07:00

Yes (but I already said that this was a very high probability event..)

rao

On Mon, Oct 20, 2008 at 9:29 AM, Farooq Khera <fkhera@asu.edu> wrote:

You said you would clarify this before day of the midterm.
Is the midterm open notes/book?

Re: question about midterm

2008-10-20T09:23:00.001-07:00

Recall that in relevance feedback, we show K docs to the user, who marks r of them to be relevant (and thus K-r of them to be irrelevant). We then compute the new query as alpha* old query + beta* (sum of relevant doc vectors)/r + gamma * (sum of irrelevant doc vectors)/(K-r).

Since we are showing only *one* document to the user (K=1) , and the user says it is relevant (r=1), we have to assume that the number of irrelevant documents that we have shown until now is 0; which means that gamma factor becomes zero.
[You can't assume that 1023 are irrelevant documents--we haven't shown them to the user--so how do we know that she would have found them to be irrelevant?]

3.[3pt] Suppose the user is shown D in response to the query Q, and the user says
that D is relevant to his query. If we now use relevance feedback to modify Q, what
will the query vector become? Assume that alpha, beta and gamma are all 1.

rao

On Wed, Oct 15, 2008 at 8:59 AM, Farooq Khera <fkhera@asu.edu> wrote:

You were going to provide some insight about the specimen midterm about the question of Relevance feedback in reference to Irrelevant documents?
I was confused about how you calculate the sum of the irrelevant documents. It would seem there are 1023 irrelvant documents.
and so we know the size of irrelvant documents, such that part of the formula is Gama/#of irrelvant documents * (Sum of (irrelvant document vectors))

However its not well defined what the irrelevant document vectors are?
Unless somehow you can just take the whole corpus as a vector and then just subtract whatever the relevant document parts... which makes sense now i think lol...

-Farooq Khera

Homework 2

2008-10-19T23:33:00.001-07:00

You can pickup your graded homework 2 from my desk (557AD) between 12pm and 5pm. I may also be at my desk prior to 10:30am if you want to stop by and check.

I apologize for the delay in grading, something important came up and I wasn't able to have them graded in time. I also needed to go back and re-grade several of them. One suggestion I would like to make is to please keep your homework in the order of the problems assigned. A large number of students handed in homework which wasn't in order. Also, please be sure to circle your answers and leave some space between problems. I found it very difficult to determine the start/end of problems for many students this time around.

Here are the stats:

Total Points: 43

Max: 43
Min: 7
Avg: 36.4

Extra office hours on Monday 2-3pm

2008-10-19T07:16:00.001-07:00

I will be available for exam-related consultations between 2-3pm tomorrow (Monday).

Rao

Results of poll on "discussion" classes--FYI

2008-10-17T06:36:00.001-07:00

In your opinion, are dicussion classes like the one today, have any utility?

	40% (12)	Yes. Let us have more of them.
	60% (18)	Some what. But let us not get carried away
	0% (0)	Mostly a vehicle to slow the class down. Nothing really learned.

30 voters have answered this question.

If you have more nuanced comments, feel free to write down (these will be anonymous)

Many of the questions were very interesting. I was really benefited from the discussion.

well i liked the way today's session went..but something was lacking..im not able to pinpoint..maybe the next go would turn out better..

Helps get a general overview of the subject at hand. Definitely interesting!

Re-stating the question is usefull, as we often can't hear other people.

I would prefer shorter in-class discussions. We do already have opportunity to discuss everything in the blog. If there were hot blog discussions probably it would have sense to bring them in class.

The idea of discussions in itself seems good, but today's discussion was more like summarizing what we've been doing in the class. Most of the questions/comments were at very high level of abstraction, and not targeted on the core technical points.

Many people felt forced to talk and spoke without having any opinion.

I feel, in future, such discussion should/could be conducted after every topic gets completed

Discussion classes could be really fruitful if well directed and planned and used only for very important issues. I consider that they are specially useful for issues that have not been completely understood or are still kind of obscure. Probably, next time, the class could be polled to know whether a discussion is worthy an entire class session.

I did think that it was very helpful. One problem I had is that certain students were bringing up irrelevant issues that were (a) not pertinent to the discussion topic and (b) probably would be covered later in class. I think a perhaps better solution would be to interject discussion topics WITHIN lectures. So dedicate 5-10 minutes of open discussion about a lecture topic. That way we do not fall behind on the subject matter, we don't miss out on your amazing (and funny) lectures, BUT DO have the opportunity to talk about things that we do not understand.

I think the discussions are good once and a while to mix up the regular routine.

Discussions like these help put everything that we learn in class together and see the whole picture.

Too many questions, not a really discussion. Maybe it should be moderated more and there should be predefined specific topics that the discussion is about.

Online poll on discussion class effectiveness

2008-10-16T15:25:00.001-07:00

Please vote on the effectiveness of having discussion classes like today's in the online--single question--poll available at

http://www.misterpoll.com/polls/362296

Vote early, but *not* often.

regards
Rao

To the people who suddenly found that they cannot post to the blog..

2008-10-15T08:55:00.001-07:00

To those of you who have realized recently that you cannot post to the blog:

This is because you never bothered to accept the invitation that was sent to you. After the 14-day drop-add date, I flushed all the pending an unaccepted invitations (since
the invites were sent also to students who eventually dropped). So, if you didn't accept the invite by the 14 days, then you
don't have permission, and you will have to be issued a new invitation. Ask either Garrett or me for it.

(I also find it disappointing hat the realization that you didn't have permission to post came only after I requested for a mandatory post
to the blog.This seems to suggest that you never even *considered* responding to the many thinking-cap questions before because they were not mandatory.)

Rao

Links brought about by PageRank paper

2008-10-15T00:00:00.000-07:00

I prescribe to the alien time machine theory myself...

Talking about systems design, here's a great article about search engines from former Stanford Scientist, then Google Employee, and now Cuil owner Anna Patterson

But will all this really be necessary? What about when mashups start doing the heavy lifting for us? Enter the Ubiquitous experience...

Mid-term postponed to Tuesday (In-class); Thursday will be mandatory discussion (+rationale for the decision)

2008-10-14T18:04:00.001-07:00

I have decided to postpone the mid-term exam to next Tuesday 10/21. It will be held in class.

On Thursday, 10/16, we will continue your discussion of the google paper. If the discussion runs dry, I will start the
next topic (on clustering).

In addition to the google paper you already read, I highly encourage you to read the following two documents too (both are optional readings
in the "overall search engine" topic)

http://rakaposhi.eas.asu.edu/cse494/henzinger02challenges.pdf

http://googleblog.blogspot.com/2008/07/technologies-behind-google-ranking.html

--------------------------
Here is the rationale for the decision--in the order of importance--if you care:

1. Garrett said he will have the homeworks graded by Thursday. Since some of you wanted graded homeworks in hand, it makes sense to
have the exam after thursday.

2. It would make sense to complete the discussion of the google paper now, before you forget what you read, than next Tuesday. Also, the discussion might also
serve as a review of sorts for most of the topics we have done until now (and thus may help in your exam preparation).

3. Of the three people who expressed a preference against shift of the exam to Tuesday, two have since changed their mind. One of them did make travel plans
that would have taken them out of town on Tuesday. I have offered them a make-up exam (it is a wash for me since I had to give a make-up for another person who
would have missed exam if it was on Thursday..)

...

...

...

100. Having thrice as much time to prepare the exam will help me make it a third as easy.

...
.
...

1000. It seems the honorable thing to do is to "suspend" the exam so all of you will have a chance to hear the final Obama-McCain debate tomorrow and see the two
gentlemen viciously tear each other down (so Ralph Nader will get elected and everyone gets a free membership in CostCo.).

regards
Rao

IMPORTANT re: the midterm exam date (please read)

2008-10-14T15:24:00.001-07:00

Folks

I seem to have made a terrible faux pas by asking the questions about exam postponement preferences in the order I did.

If I was thinking clearly, I would have *first* asked whether anyone has irreconcilable conflicts if the exam date is shifted to Tuesday, and only if no one has irreconcilable conflicts should I have asked if the majority prefer shifting.

By asking the questions in the opposite order, I apparently created a bit of social pressure to the
people who said they have irreconcilable conflicts. The upshot is that one of them came by my office and changed their vote!

Creating social pariahs has not been my intention, and I apologize.

Nevertheless, since the damage has been done, if the others who voted to express irreconcilable preferences also want to change their
vote, they should let me know by tonight.

*Unless* you get a mail stating otherwise, we will be having the mid-term exam on Thursday.

cheers
rao

ps: This episode makes the point that once you make your plans public, they are no longer your plans and other agents can make commitments
based on your plans. See http://rakaposhi.eas.asu.edu/replan-08.pdf about how an intelligent agent has to keep commitments to other agents in mind while
trying to exploit opportunities.. (this is from the other part of my research life).

a specimen midterm exam (from the past)

2008-10-12T08:01:00.001-07:00

Can be found at

http://rakaposhi.eas.asu.edu/s07-specimen-exam.pdf

Note that the coverage of topics was a bit different that time around--so the specimen exam has questions on link-analysis and clustering
(as I said, link-analysis will not be covered in this exam, and clustering hasn't been done yet). We instead have done more on indexing and
tolerant dictionaries and also more on social networks.

cheers
Rao

Re: Midterm syllabus

2008-10-12T07:55:00.001-07:00

Mid-term syllabus is everything covered by the two homeworks (i.e., all topics until the end of social networks).

Link-analysis topics (page-rank; authorities/hubs etc) are not included.

Rao

On Sun, Oct 12, 2008 at 3:43 AM, Vijayakrishnan Nagarajan <vnagara5@asu.edu> wrote:

Dear Professor,

Can you tell us what is the syllabus for midterm?

Thanks,
Vijay

Solutions for homework 2 posted online (hw1 solutions were posted a while back)

2008-10-10T22:02:00.001-07:00

New Search Engine

2008-10-09T23:21:00.000-07:00

This is a new search engine which searches our web memory.

www.infoaxe.com

Vijay

Links from today's class..

2008-10-09T22:02:00.001-07:00

1. Here is a link about the Search King/Google lawsuit:

http://www.pandia.com/sw-2003/21-searchking.html

2. Here is a link to an NYT article where Amit Singhal--google search fellow--admits that page rank is but just one of 240 odd pieces of information they combine in making their ranking

http://rakaposhi.eas.asu.edu/s07-cse494-mailarchive/msg00082.html

3. Here is interesting, but dated, information about the mechanics of Google dance (when google would update its index, link matrix and page ranks)

http://dance.efactory.de/

4. Here is a link--back from late 2005--when Google first started tweaking its index for China--because China asked it so nicely that Google just couldn't refuse ;-)

http://rakaposhi.eas.asu.edu/f05-cse494-mailarchive/msg00106.html

(here is a more complete article from BBC http://news.bbc.co.uk/2/hi/technology/4645596.stm )

Here is a general wikipedia article that also discusses current search engine status in China:

http://en.wikipedia.org/wiki/Internet_censorship_in_mainland_China

cheers
Rao

Results of the class survey

2008-10-09T21:39:00.001-07:00

Dear all:

Thanks for taking the time to complete the class feedback survey. Thanks to Vijaykrishnan Nagarajan's exceedingly prompt and free service, we already have the tabulated results from the survey. Here are two links. The first one contains the stats of the entire class. The second one contains stats just for the 494 students.

http://rakaposhi.eas.asu.edu/cse494/survey-08-results-all.htm <--the whole class

http://rakaposhi.eas.asu.edu/cse494/survey-08-494-alone.htm <--just the 494 students

My cursory reading didn't raise any major red-flags. I will look at them more carefully and respond and/or fine-tune the remaining semester. You might also want to look at them to see how your perceptions stack up with the rest of the class's.

As before, you can use the anonymous email link sent to you earlier to give any other feedback you want to provide.

cheers
Rao

VERY Important: Mandatory reading/review/discussion for next class 10/14

2008-10-09T15:18:00.001-07:00

Folks:

A large part of next Tuesday's class will be devoted to a discussion of the paper

http://rakaposhi.eas.asu.edu/cse494/google-paper.pdf

(this is the top one in the "overall search engine" category).

You should all

(1) read it and

(2) bring to the class a an at-most one page review to the class with questions and/or observations about
the paper given all that you know about how search engines could work).
Focus on what are aspects of the architecture that surprised you
and/or different from what we discussed in the class.

(3) Post your comments also onto the blog (as comments on this post)---Preferably before the class.
This will also serve as a good review of a lot of what we have done in the last several weeks.

The class itself will consist of

1. A short first part where I will complete the discussion of Trust Rank and Efficient computation of Pagerank

and

2. Us discussing the questions you bring up.

This is a mandatory class and your participation is mandatory..

cheers
Rao

More on how pagerank paper got rejected from SIGIR (and some philosophy on conferences)--comments?

2008-10-08T08:53:00.000-07:00

[You can read the following either as a discussion of conference reviews etc., or as a discussion of importance estimation in
social networks using link-analysis.]

I mentioned in passing yesterday that the original pagerank paper was rejected from SIGIR (the 1998 conference). It never did
get published as a separate paper. All the cites to the idea are redirected instead to their WWW 1998 paper.

This brings up the issue of how we are supposed to judge the importance of a conference (and researcher). Here are two methods:

1. Consider the importance of a conference in terms of it's *acceptance ratio*--i.e., what exceedingly small fraction of the papers submitted to the conference
are actually accepted for publication. The researchers can then be judged in terms of how many hard-to-get-into conferences did they get their papers into.
The attractiveness of this approach of course is its very immediacy--as soon as the conference acceptance decisions are made, we have the acceptance ratios--which can be
used to judge the conferences as well as researchers. The disadvantage is that there is really no connection between the long term impact of a paper/conference and the acceptance ratio. The page rank paper example above says that just because SIGIR is very selective doesn't mean it is right (actually there is anecdotal evidence that the total sum of citations to all SIGIR papers is smaller than the citations to the pagerank paper it rejected ;-).
Similarly, high acceptance ratio doesn't necessarily mean that the selection process is easy. consider that if Presidential race were to be seen as a conference, it has a whopping 50% acceptance ratio (I hope the Ralph Nader fans will forgive me for saying this). In the end, acceptance ratios tell us how much of a fad the area currently is.

2. Consider the importance of a conference in terms of the citations to the papers appearing in that conference. This is link-analysis--except generalized to a "cluster" of nodes (corresponding to the papers of that conference) rather than to individual nodes. The importance of a researcher then is in terms of the aggregate citations to their papers
(an example measure is H-index http://en.wikipedia.org/wiki/Hirsch_number ). This statistic is *not* immediately obvious--since citations are a "lagging" measure. [The day after
Lincoln's gettysburg address, the news papers around the country were split almost 50-50 in their judgement of the importance of that address--with many papers calling it a
lack luster speech by a third rate politician). The advantage is that citations do tell us about the long-term importance/half-life of the paper (and a conference's ability to select such papers). I tell my students that if ever they find themselves writing a paper for a confernce A and find that they are mostly citing papers from conferences B and C, they should re-consider their decision to send the paper to A--or admit that they are second-class ;-).

Of course, even this measure can be further improved. There may be conferences on Scientology and/or Creationism whose papers are very well cited--by other papers appearing in those conferences--but the world at large completely ignores it. To evaluate this, you need to separate citations from within the conference/domain and across domains [Notice the connection to the idea of giving separate weights to intra-domain and transverse links that we mentioned in yesterday's class].

Not surprisingly, this is what serious ranking sites go by citations rather than acceptance ratios (although authors tend to put the acceptance ratios in their CVs!). See

http://citeseer.ist.psu.edu/impact.html for a ranking of impact of about 1200 CS publication venues (and check where your conference occurs)

see http://libra.msra.cn for a more refined ranking--where each conference/researcher are ranked with respect to each area (considering in-domain vs. inter-domain citations). Zaiqing Nie--who is the architect of the Libra system--will be here on October 24th to give a talk partly about how this system is built.

===========
1 and 2 above also have an impact on the way conferences are run (and researchers do research). Coming to conferences--it is easy enough to optimize for lower acceptance ratios. But if what we want to optimize for is longer term expected impact, then how does the conference--and its reviewers--do this? Notice that by rejecting just the page-rank paper SIGIR lost about half its cumulative citations. The essay by Ken Church -- at http://rakaposhi.eas.asu.edu/church-precision-reviews.pdf provides a few thoughtful suggestions.
One important point the paper makes is that while precision is easier to judge, recall is harder (you can tell if there are relevant results in the top-10 pages returned by a search engine, but you can't tell if it left out any really important pages from the top-10). [Another related article is http://rakaposhi.eas.asu.edu/patterson-conferences.pdf )

cheers
Rao

Thinking Cap questions on Page rank/ Authorities/hubs..

2008-10-07T19:21:00.001-07:00

------
Digression:

Here is the link to the Montana history professor who took "sponsorship" from a burrito joint for his class:

http://www.missoulian.com/articles/2008/10/01/news/top/news01.txta

(Check out "Wait Wait Don't Tell me" on NPR on Sundays if you want to be kept abreast of this kind of important news ;-)
----------

Here is a thinking cap question:

The following are several "comparisons" between page rank and Authorities/hubs methods for computing page importance. Comment on whether or not these comparisons make sense.

1. A/H analysis is too costly because it has to be done for each query, while page-rank analysis, which can be done off-line and once for all queries, is much better.

2. page rank analysis is not as good in taking importance in the context of the queries, while A/H analysis is much better.

3. A/H analysis has major issues with stability (i.e., its ranking can change a lot with just small random changes to link structure), while page rank is much more stable.

4. Its all a bunch of ballyhoo, and underneath it all, A/H and pagerank both give same ranking of importance to all the pages.

------------
Rao

Talk by Zaiqing Nie (ASU Alumnus; currently at Microsoft Research) on 10/24 on "Object-level Web Search"

2008-10-07T07:38:00.001-07:00

Abstract:

Bio:

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Re: [CSE 494/598 Fall 2008 Blog] New comment on Re: Question about Homework 2 on document coordina....

2008-10-06T16:03:00.001-07:00

I added the following hint to that question for those of you who are confused by the U,S,V notation

[[Oct 6, 2008] Note that M here is t-d so the SVD of M will be of the
form t-d = t-f * f-f * d-f' So, U=t-f, S=f-f and V is d-f]

cheers
Rao

ps: There is nothing wrong with U,S,V notation--it is in fact the standard notation for SVD. However, the d-f, f-f, t-f notation is more mnemonic

On Mon, Oct 6, 2008 at 3:49 PM, Mike Balzer <mjbalzer@asu.edu> wrote:

Mike Balzer has left a new comment on your post "Re: Question about Homework 2 on document coordina...":

Then, should the wording for question 3.1 Homework 2 be changed, as it references U, S, and V?

Posted by Mike Balzer to CSE 494/598 Fall 2008 Blog at October 6, 2008 3:49 PM

Re: Question about Homework 2 on document coordinates in LSI space

2008-10-06T14:01:00.000-07:00

[[Folks--please make sure that you are not looking at hidden slides--as these may have inconsistencies and incomplete statements]

SVD gives

d-t = d-f * f-f * t-f'

the new coordinates of the docs are d-f * f-f

I pointed this out in the class when doing the main animated slide.. (I think you and the student are looking at some hidden slides which may have been left over there from long back--I did all my discussion in terms of d-f * f-f * t-f' and not in terms of
u sigma and v!)

rao

On Mon, Oct 6, 2008 at 1:51 PM, Garrett Wolf <garrett.wolf@asu.edu> wrote:

Rao I've had two students ask me this question today, and after looking through the slides I wasn't clear which they should be using for the homework as both were mentioned in the slides (one seemed to be marked as the one to use, but I just wanted to check to be sure).

Garrett

---------- Forwarded message ----------
From: Jianhui Chen <jchen74@asu.edu>
Date: Mon, Oct 6, 2008 at 1:48 PM
Subject: Question about Homework 2
To: Garrett.Wolf@asu.edu

Hi, Garrett,

I am a student in Dr. Rao's information retrieval class. I have a question regarding the homework.

In LSI, assume X is the doc-term matrix and denote its SVD by X = U \Sigma V'.

Should we use "U \Sigma" as the new documents representation or only "U" as the new documents

representation?

Seems both approaches are mentioned in Dr. Rao's slides. And in the homework, we need to use

the new documents representation to compute the similarity and plot the documents.

Please help to advice. Thanks.

Jianhui

Homework 1 Stats and Comments

2008-10-06T00:53:00.001-07:00

Here are a few stats homework 1:

Max: 40

Min: 27

Avg: 36.7

Stddev: 3.7

Overall, people did well on this first homework but I had a few suggestions for future homework:

· Make sure to show your work because without it, I cannot tell how severe of a mistake has been made, and thus a wrong answer is not likely to get partial credit.

· For most of the questions (obviously not all), some sort of explanation is expected (went easy on this for the first homework but later homework will be more strict). If you have to compute an answer for a question, it’s always good to include some text describing the answer rather than just providing a number.

· For the relevance feedback question, in the beta/|Dr| and gamma/|Dn| part of the question, |Dr| and |Dn| are the number of relevant and irrelevant documents respectively (not the norms of the relevant and irrelevant documents). For question 3.4, where d4 and d6 are shown to the user and the user clicks on d6 but not d4, keep in mind that |Dr| = 1 and |Dn| = 1. Some people put |Dr| = 2 and I’m assuming this came from the 2 documents being shown to the user. However, just because the system thinks the documents are relevant and thus shows them to the user, they are not considered relevant in terms of the relevance feedback calculation, unless the user says so.

Some people may have answers which differ from those in the slides for problem 3. I had sent out the updated doc-term matrix yet some people used the matrix from the slides for answering the questions. If you did this, I used the original matrix when grading your homework. Please use any updated versions if they are sent out for future homework.

Finally, the grading scale in the solutions are not the ones I used. Here are the grading scale used for this homework. If you have any questions or think something was graded incorrect, then please let me know (but as I mentioned, I went a little easier on this first homework).

Total Points 40

Q1.1 1

Q1.2 1

Q1.3 2

Q1.4 3

Q1.5 3

Q1.6 3

Q1.7 3

Q1.8 3

Q2.1 4

Q3.1 3

Q3.2 3

Q3.3 3

Q3.4 4

Q3.5 4

Garrett

Homework 1 solutions posted; graded homeworks will be returned on Tuesday

2008-10-05T15:58:00.000-07:00

Homework 1 solutions posted; graded homeworks will be returned on Tuesday.

(I should mention that the hard-working TA gave me the graded homeworks on last tuesday. I wanted to go over them once
and return them to you on Thursday. I forgot the returning part).

rao

Homework 2--three questions added. Due Thursday in class

2008-10-05T15:48:00.000-07:00

Folks:
I added three questions to the homework--one on social networks, one on string distances and one on inverted indexes. These questions are not exactly very hard but are put there to make you look at the notes.

the homework as a whole is due on Thursday 10/9 in class

Rao

Where the Web is Going: Web 2.0, 3.0 and Beyond

2008-10-03T03:08:00.000-07:00

Interesting round table style panel on Web 3.0 and beyond...

http://link.brightcove.com/services/link/bcpid980795693/bctid1790936412

(If you watch far enough through, you'll notice Peter Norvig happens to mention his spelling corrector that was shown in the "Indexing and Tolerant Dictionaries" lecture)

Beyond Text Ranking

2008-10-02T18:05:00.001-07:00

I am personally more interested in applying ranking and retrieval techniques developed in IR for image ranking. In particular, I am working on a project which, given a query biological image, the task is to find similar images in the database. You can find more information about this project at: http://www.flyexpress.net/

Recently, it seems that people is beginning to apply text retrieval techniques to image ranking and I noticed two papers which I found interesting and want to share with you.

@article{ 10.1109/TPAMI.2008.121,
author = {Yushi Jing and Shumeet Baluja},
title = {VisualRank: Applying PageRank to Large-Scale Image Search},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {30},
number = {11},
year = {2008},
pages = {1877-1890},
}

@ARTICLE{Sivic:PAMI08,
AUTHOR = {J. Sivic and A. Zisserman},
TITLE = {Efficient Visual Search of Videos Cast as Text Retrieval},
JOURNAL = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
VOLUME = {},
NUMBER = {},
PAGES = {},
YEAR = {2008},
NOTE = {In press},
}

Shuiwang

added new slides at the beginning of page-importance measures lecture

2008-10-02T17:55:00.001-07:00

Folks:

I revised the first slide and added a new second slide in the page-importance measures. I encouarge you to look at them.

rao

Regarding Page Importance

2008-10-02T16:13:00.000-07:00

Sir,

When you were discussing about page importance you mentioned about the amount of access a page gets as one of the criteria for evaluating importance. I have 2 questions on that.

1. There are lots of websites which display the number of visitors for that page. How do they compute that?
2. Is there any relevance to that for computing the page rank for that page? If yes can this make the website owners to increase the page rank of their website by logging in again and again themselves and make it to the top of the rank?

On the question of when eigen values are guaranteed to be positive (and the property of positive definiteness)

2008-10-02T16:06:00.001-07:00

There was a question in the class (by Dmitry I think) as to when can we be sure that eigen values of a matrix are all positive.

Here is the answer

All symmetric matrices are guaranteed to have real valued eignen values, but are not all guaranteed to have positive eigen values.

Having positive eigen values turns out to be closely related to a *very* important property of matrices called "positive definiteness"

However, if the symmetric matrix M under consideration can be written as B*B' where B is a non-singular matrix (i.e., has non-zero determinant),
then it is guaranteed to have +ve eigen values. (Notice that the matrices we power-iterated on in A/H computation are of this form).

-------------

While we are at it, we should note that the property of having positive eigen values is intimately linked to another very deep and useful property called
"positive definiteness"

A matrix M is called positive definite, if for *any* vector u,

u * M * u' > 0 (it is called positive semi-definite if "greater than" is replaced by "greater than or equal to")

It turns out that M is +ve definite if and only if it has all positive eigen values (you can sort of see the "if" case in terms of viewing vector/matrix multiplication in terms of
stretching vector's projections in the eigen vector directions by the amount equal to eigen values).

cheers
Rao

Search on google's 2001 index

2008-10-01T16:18:00.000-07:00

hi all

If you all dont know yet..google has put up its 2001 index for searching as a means to celebrate its 10th birthday..for searching back in time.. you can visit

http://www.google.com/search2001.html

and for more on their 10th birthday, visit

http://www.google.com/tenthbirthday/

I searched for apple ipod and got 36 documents as results with none of them pointing to apple.com

An somewhat erroneous statement I made in today's class..

2008-09-30T19:26:00.000-07:00

In today's class, I said that it is possible to make poisson distribution as "peaked" as you want by
reducing the variance parameter (as part of making the point that the "drop off" in the power law distribution
is not as important as the "slow decay/long tail).

Well--not exactly. Poisson distribution, as you saw, has only *one* parameter--lambda, and the
means as well as the variance of the distribution will be lambda (this is unlike normal distribution,
for example, where you can set the mean and variance parameters indepdendently). The only way to reduce
the variance is thus to reduce the mean... (you may also recall that for random networks, lambda is p*N (i.e., the expected degree))

Here is a link on poisson distribution as well as how it is the limiting case of binomial distribution:

http://en.wikipedia.org/wiki/Poisson_distribution

cheers
rao

Speaking of the Long Tail...

2008-09-30T14:16:00.001-07:00

http://www.thelongtail.com/the_long_tail/2005/09/long_tail_101.html

This article a while back sparked quite the frenzy in the business world...it can be seen as the direct cause of the renewed interest in non-Google engines and other businesses trying to capitalize on the Long Tail.

Project Deliverables

2008-09-30T09:51:00.001-07:00

Just a reminder to bring a printout of your commented source code, example query results, and report to today’s class.

We are not using digital drop box or any other electronic submission for the course…remaining homeworks/projects will also be submitted in class.

Garrett

Project Help - Sunday

2008-09-28T13:05:00.000-07:00

It seems as though several people are interested in meeting today regarding the project so I will plan on being in the brickyard from around 3pm – 5pm. I’ll plan on sitting in the second floor lab during this time (assuming I have access…otherwise I’ll be on the 5^th floor in which case you can just send me an email and I’ll come down and meet you on the second floor).

Garrett

CSE 494/598 Fall 2008 Blog

sayanora..

Final exam answers

Cumulatives with late penalties and participation

Project 3

Final Cumulatives (sans extra credit)--

final exam points

Project 3

Cumulatives (sans the final exam grade)

Blowing Steam Topic: Questions on the final that may have infuriated you etc.

Attendance statistics...

Re: Semantics and schemas

Re: One question about Authority/Hub computation

Re: Regarding the discussion

Homework 4

REMINDER: Exam tomorrow Tuesday 12/16 12:10--2:00pm same room

availability today for final-exam-related questions..

The final exam will be closed-book (as had been agreed in the class)

Final exam coverage..

in praise of intellectual swagger..

Fwd: CEAS teaching evaluations..

Re: question about hw q3

participation evaluation sheet (please return in hardcopy on Tuesday)

Rescheduled Demo Slots

The demo signup sheet

Blog qn for Homework 4 (You should post your answer as a comment to this thread and also enclose it in your hw 4 submission)

Topic for this week: Information Integration --slides available online..

Project Demos

Sunday Office Hours

Office Hours

Shadow-play video of the make-up class online..

Additional Sunday Office Hours

Reminder: Make-up class today at 10:30AM in BY 210 (near advising office)

Re: Doubt in homework

Re: HomeWork 4

Re: CSE494/598 Project C clarification

Thinking Cap: From the latest NYT magazine: Netflix prize; Collaborative filtering, Singular value decomposition and recommendation systems

If You Liked This, Sure to Love That

Homework 3 solutions posted; two questions for Homework 4 posted

Today's Office Hours

Thinking Cap questions: The Lame-Duck edition

Current Cumulatives

Farenheit 451 and other references from today's class...

Re: NBC question

Re: Doubt about Q3 of homework 3

Re: Doubt Q2

homework 3 assigned; due next thursday Nov 13th

Fwd: (this time with 598/494 demarcation shown) midterm grades (marks by posting-id)

midterm grades (marks by posting-id)

Office Hours Location

Next topic: Text classification (required reading: Chapter 14 of Manning et al's book)

Lost Backpack

Project 2 Fix

Additional Office Hours

Additional Office Hours

GAAP (Grade Anxiety Amelioration Program)

Project 2 Due Date Approaching

Fwd: Faculty Seminar Series Presentation on October 24th 2008 (Friday) by Professor Arun Sen: ORG-ENG-CSE_Online_Com

Next topic: Clustering--readings are chapters 16&17 from manning et al IR book (as linked)

Reminder: Talk tomorrow by Zaiqing Nie (ASU Alumnus; currently at Microsoft Research) on 10/24 on "Object-level Web Search"

Re: About Calculator

Re: About Calculator

Re: About Calculator

Re: Doubt on random graphs

(should work now) Re: answers to qn 5 & 6 of hw2 posted online

answers to qn 5 & 6 of hw2 posted online

qn re: the use of Rocchio method

Re: midterm is open notes/book?

Re: question about midterm

Homework 2

Extra office hours on Monday 2-3pm

Results of poll on "discussion" classes--FYI

Online poll on discussion class effectiveness

To the people who suddenly found that they cannot post to the blog..

Links brought about by PageRank paper

Mid-term postponed to Tuesday (In-class); Thursday will be mandatory discussion (+rationale for the decision)

*IMPORTANT* re: the midterm exam date (please read)

a specimen midterm exam (from the past)

Re: Midterm syllabus

Solutions for homework 2 posted online (hw1 solutions were posted a while back)

IMPORTANT re: the midterm exam date (please read)

VERY Important: Mandatory reading/review/discussion for next class 10/14