Category: Blogs and Web

Netflix Prize Update

I previously wrote about the Netflix prize: come up with a better system to recommend movies based on a large amount of data, and win $1 million. Tim Spey has a wonderful article on the dataset and the competition (though I can’t see a couple of the graphs he talks about). It is clear the dataset is pretty strange:

  • Customer 2170930 has rated 1963 titles and given each and every one a rating of one (very bad). You would think they would have cancelled their subscription by now.
  • Five customers have rated over 10,000 of the 17,770 titles selected – and presumably they also have rated some of the others among the 60,000 or so titles Netflix had available when they released the ratings. Are these real people?
  • Customer 305344 had rated 17654 titles. Even though Netflix make it easy to rate titles that you have not rented from them (so they can get a handle on your preferences) can this be real?
  • Customer 1664010 rated 5446 titles in a single day (October 12, 2005).

The main point of the entry, however, is that it is unclear that these sort of recommender systems can be useful in predicting consumer preferences. One striking point made is that a naive algorithm (predict the average value so far) is not that much worse than the Netflix system:

A simple algorithm that uses the average rating for each title as the prediction – “let’s see, the average rating for the 104,000 customers who rated Mean Girls was 3.514, so I predict you will give it a rating of 3.514” – gets an RMSE [Root Mean Squared Error] of 1.0540. Netflx’s Cinematch algorithm has an RMSE of 0.9525. Netflix set the prize target at a 10% improvement over that, which is an RMSE 0.8563. So the range that recommendation systems can realistically cover – from naively simple to cutting-edge research – seems to be [a] narrow band

To put that in perspective, here is the effect that sort of decrease in error has:

Anyway, if the errors followed a normal distribution (which they don’t, but we’re talking back-of-envelope here) then if a customer actually rated a title as 2 (poor), an algorithm with an RMSE of 1.0 would predict somewhere between 1 and 3 about 70% of the time. Not bad, but not startling. If the algorithm gave ten recommended movies, then it would get on average seven out of ten within one unit of the customer’s actual rating. Meanwhile, the RMSE=0.8563 algorithm would get 7.6 out of ten. While this is an improvement, and while it may be a remarkable technical accomplishment, it does not seem to be exactly a revolutionary leap compared to the really simple algorithms as far as customers go.

In short, would a customer even notice the difference? He concludes:

I’m no futurist, but I see little evidence from the first 300 days of the Netflix Prize that recommender systems are the magic ingredient that will reveal the wisdom of crowds.

This is an excellent blog entry that really goes to the heart of the value (or lack thereof) in these sorts of models.

LinkedIn and Operations Research

Don Kleinmuntz of Strata Decision Technology and USC has made a concerted effort to get people in operations research to join LinkedIn. Since Don was a founding co-editor of Decision Analysis and has been Treasurer for INFORMS among many other jobs, he has an extensive contact list, and a number of us have joined. I was a latecomer, just joining today. Don so far has found it interesting, but he is holding back a decision on its importance.

I was surprised how many people were on it. There are dozens of “Trick”s alone, which is unusual. It definitely has cornered the market on 30-something IT people. But a search on “operations research” tagged 177 people, so it seems there are some of our type there (or just Don’s buddies!).

If you are on it, send me (Mike Trick) an invite and we can get our our little social network going.

OR in Comics

I sometimes fantasize about writing the Great American Novel (New Zealand version).  In such a novel, naturally the hero would use operations research to achieve success and insight.  But when I think about such a novel, my imagination fails me:  how can I possibly make OR interesting in the context of fiction?

She:  Oh Biff, How can we ever be together?

Biff: Well, if I just solve this Traveling Salesman Problem using Concorde, I will be there as quickly as I can.

She: My hero!

Ummm…. no.  But the comic xkcd periodically has an OR theme, like solving knapsack problems.  You know you are a nerd when you solve the instance given by the comic (hint:  they better like fruit in one solution, but the solution is not unique).

Getting dumber?

Stephen Baker at Business Week points to a post by Jeff Jonas on how companies are generating so much data so quickly that companies can’t make sense of it, leading to “enterprise-amnesia“.  Both use this as a call for faster, smarter algorithms.  Now far be it for me to be negative about such a cry (I like algorithms!) but I think they are missing an important step in the process:  the modeling step.  Modeling is formulating the objectives, constraints, and decisions in order for the algorithms to go to work.   We’ve had lots of algorithms hanging around for decades that would address business issues, if only people would create appropriate models to use them.  Not every problem needs a fancy new algorithm!

Jonas’ blog has a number of interesting posts on things like persistent analytics.  This is all from a heavily information technology perspective, but OR should have a role to play in the issues he brings up.

Conference reviews, in perspective

I am just back from Prague: after another 36 hour travel marathon, I think it will take a day or so for my brain to catch up with me!

While I was gone, Scott Aaronson, a graduating doctoral student in quantum computing, had a brilliant article on computer science conference reviewing. From the 1936 Foundations of Computer Science (FOCS) review process:

Dear Mr. Turing,

We regret to inform you that your submission
“On Computable Numbers, With an Application to the Entscheidungsproblem”
was not accepted to appear in FOCS 1936. The Program Committee received a record 4 submissions this year, many of them of high quality, and scheduling constraints unfortunately made it impossible to accept all of them.

The reviews would be a great satire of computer science reviews except they are far too close to the truth:

—————————————- review 1 —————————————-

seems like a trivial modification of godel’s result from STOC’31

—————————————- review 2 —————————————-

The author shows that Hilbert’s Entscheidungsproblem (given a mathematical statement, decide whether it admits a formal proof) is unsolvable by any finite means. While this seems like an important result, I have several concerns/criticisms:

1. The author defines a new “Turing machine” model for the specific purpose of proving his result. This model was not defined in any previous papers; thus, the motivation is unclear.

See Scott’s post for the rest of this and for the other reviews. Many OR conferences are not reviewed (IFORS, EURO, and IFORS conferences accept practically anything submitted on time), but there are some that I am involved with (like CP, CPAIOR, MISTA, and PATAT) that have a review process, and it is clear that the review processes are very hit-and-miss.

With the exception of Scott’s ill-tempered diatribe against babies at conferences (perhaps as forty-something father of three-year-old, I am a little more sympathetic to the pressures of combining parenthood and academia), the entries in Scott’s blog are something I look forward to tremendously: he is opinionated, intelligent, amusing, and self-deprecating by turns, and generally teaches me something when I read him. He is about to join the faculty at MIT: lucky MIT!

Six Key Ideas of Operations Research?

For most of us, teaching a first course in operations research involves trotting out our old friends linear programming, sensitivity analysis, integer programming, and so on. Twenty years ago, we used linear algebra; today, we concentrate more on modeling. But it is not clear that students get the Big Picture. Like “Modeling is useful” or “Decisions can (sometimes) be made on marginal information” or even “If you add constraints, the best solution gets worse”.

Steven Baker, whose Blogspotting I regularly visit and which often provides material here, has a posting entitled Economics and Braille Keyboards pointing to an interview with the economist Robert Frank. Frank has a new book out based on the idea that there are really only about six key ideas in economics, and if you can get students to think about and apply those six ideas, then you have really had a successful introductory course. The title comes from a student essay on why drive-through banks have braille on the keyboard. If blind people can’t drive, why provide braille? The answer is in cost-benefit analysis: it would cost more to have two types of keyboards, so standardization is better (assuming putting on those dots is not costly in itself). As for benefits, this holds even if the benefit is zero. If the benefit is positive (blind people in cabs, say), then it holds even stronger.

What would be the six key ideas/insights about operations research? I listed a few above. Some others might include “If there is randomness, systems without slack run out of control” and “Nonbinding constraints don’t affect the optimal solution” (these are more insights than key ideas). As a prescriptive science (rather than the descriptive science of most economists), it is not clear that this method of teaching works as well, but it is useful for us to think about what we really want to get across in our classes.

Slashdot discussion on “High Paying Jobs in Math and Science”

Slashdot is having a very active discussion (naturally degenerating into nonsense at times, but generally pretty good) about high paying jobs for those will a college degree in math or science. Operations research gets a good plug or two among the discussants. One response (from “MoneyCityManiac”):

Applied math is a good bet. Operations Research (“OR”), as Wikipedia defines it, is “an interdisciplinary science which uses scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and execution of the operations within an organization.” It’s a mixture of math, stats, CS, and engineering.

There’s OR applications in areas such as health-care, environmental management, forestry management, transportation, and much more. Environmental management, in particular, is something that operations research is going to play a huge role as government and industry focus on reducing greenhouse gas emissions.

And because there’s such a practical role towards it, there’s plenty of support from government and industry, not just in terms of jobs at the end but also scholarships, fellowships, etc. Ask around a math, CS, or engineering department! I’m sure it won’t be hard to find someone who can point you in the right direction.

OR, Poker, and Teaching

It is a lovely morning here in New Zealand, and the sun is rising over the bay that my house overlooks. So naturally I am wandering around the web.

Gary Carson’s Math and Poker blog is one that I regularly follow (not the least because he points to this blog). He writes about the role OR plays in understanding poker and about how OR is taught:

Part of the problem that operations research has in getting recognition is the way we teach it — it’s taught as a bunch of algorithms for the most part. Even when it’s taught as a bunch of models to be applied to real problems, the models are taught as members of a tool kit. Seldom do we teach OR as a process of using models to abstract or isolate the elements of a problem that are critical to decision making related to that problem.

…

I think OR education needs to put more of a focus on using the model and less focus on solving the model. I think students would form a deeper grasp of what OR is all about if that was done. Stuff like analysis of residuals and sensitivitey of LP solutions are just too important to be glossed over.

I teach at a business school and we have moved much more to teaching about using models for real-world business decisions. Things like sensitivity do end up taking a backseat, however, since without understanding the underlying algorithm/mathematics things like dual values are just mysterious black boxes. The challenge is, I think, how to get enough of the fundamentals across so people can confidently and correctly use the resulting models. And I think we are all over the map on this at the moment, to the detriment of the field.

Quantum Computing and Learning from Blogs

Scott AaronsonEver since I heard about quantum computing (it arose in the 1970s, but most of the really visible stuff started in the mid 1980s, see the Wiki timeline), I have been skeptical. This skepticism arose from a view that quantum computers could solve NP-complete problems in polynomial time. I was randomly wandering the blogosphere when I can across “Shtetl-Optimized” by Scott Aaronson, with the subtitle “Quantum computers are not known to be able to solve NP-complete problems in polynomial time”. Well, perhaps everyone else knew that, but it was somewhat annoying that something I knew for two decades was dead wrong. While practical quantum computers still seem some time away (it seems the state of the art is factoring 15=3×5), trying to determine the effect of quantum computing on OR seems like an interesting question.

One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ“, where he lists some of the questions he was asked in his job search (he is a postdoc at my alma mater, the University of Waterloo’s Department of Combinatorics and Optimization). I’ve interviewed for a job or two in the couple years this blog has been going, but I have not been bold enough to talk about it. Scott uses the entry as a very quick survey of what he believes in, and the interviewers don’t come across like idiots (I guess I would have asked about half the questions myself).

Check out also his article “NP-Complete Problems and Physical Reality“published a couple of years ago in the SIGACT News complexity column. Having lived through an era when NP-completeness results were being churned out by the boatload with only a few providing real insight and advance (kinda like approximation results these days), I have not advanced very much beyond what I knew ten years ago, but Scott’s writing make this look pretty interesting again.

Finally, I am jealous of Scott’s ability to write well enough and intriguingly enough to generate dozens of comments on each of his posts. He points to the following review of his blog:

OK, on to the second breakfast link. Bill Gasarch has reviewed my blog for SIGACT News (scroll down to page 15), together with Lance Fortnow’s and Luca Trevisan’s. Favorite quotes:

Lance is Walter Cronkite. Scott is Stephen Colbert.

The name of the blog, ‘Shtetl-Optimized’ does not really say what it is about. With this in mind one can never say Scott has gone ‘off topic’ since its [sic] not clear what the topic should be.

Perhaps I am sticking to the topic too much!

Videos and Operations Research

Dick Larson has a very nice editorial in the April 2007 OR/MS Today on the use of videos in disseminating information about our field. One big point he makes is that the Edelman videos, a tremendous resource for our field, are not easily and freely available. This frustrates the heck out of me too! I do not understand why videos of the contestants are not up on YouTube right after the competition. There are some issues of ownership of the various INFORMS entities, but some INFORMS President will eventually be able to work them out and suddenly the world will be able to see how amazing we are.

Until then, Larson has another article on MIT World, where MIT professors give lectures on various topics. Arnie Barnett and Yossi Sheffi, along with Larson, are among those giving OR-oriented talks.

Incidentally, there are some “Operations Research” videos at YouTube but only 8 at the moment. Let’s see if things improve in the next year.