Programming Collective Intelligence 74
Joe Kauzlarich writes "In 2006, the on-line movie rental store Netflix proposed a $1 million prize to whomever
could write a movie recommendation algorithm that offered a ten
percent improvement over their own. As of this writing, the
intriguingly-named Gravity
and Dinosaurs team holds first place by a slim margin of .07
percent over BellKor,
their algorithm an 8.82 percent
improvement on the Netflix benchmark. So, the question remains,
how do they write these so-called recommendation algorithms? A new
O'Reilly book gives us a thorough introduction to the basics of this
and similar lucrative sciences." Keep reading for the rest of Joe's review.
Among the chief ideological mandates of the Church of Web 2.0 is that
users need not click around to locate information when that
information can be brought to the users. This is achieved by
leveraging 'collective intelligence,' that is, in terms of
recommendations systems, by computationally analyzing statistical
patterns of past users to make as-accurate-as-possible guesses about
the desires of present users. Amazon, Google and certainly many other
organizations, in addition to Netflix, have successfully edged out
more traditional competitors on this basis, the latter failing to pay
attention to the shopping patterns of users and forcing customers to
locate products in a trial and error manner as they would in, say, a
Costco. As a further illustration, if I go to the movie shelf at Best
Buy, and look under 'R' for Rambo, no one's going to come up to
me and say that the Die Hard Trilogy now has a special-edition
release on DVD and is on sale. I'd have to accidentally pass the 'D'
section and be looking in that direction in order to notice it. Amazon
would immediately tell me, without bothering to mention that Gone
With The Wind has a new special edition.
| Programming Collective Intelligence | |
| author | Toby Segaran |
| pages | 334 |
| publisher | O'Reilly Media Inc. |
| rating | 9/10 |
| reviewer | Joe Kauzlarich |
| ISBN | 9780596529321 |
| summary | Introduction to data mining algorithms and techniques |
Programming Collective Intelligence is far more than a guide to building recommendation systems. Author Toby Segaran is not a commercial product vendor, but a director of software development for a computational biology firm, doing data-mining and algorithm design (so apparently there is more to these 'algorithms' than just their usefulness in recommending movies?). Segaran takes us on a friendly and detailed tour through the field's toolchest, covering the following topics in some depth:
Recommendation Systems
Discovering Groups
Searching and Ranking
Document Filtering
Decision Trees
Price Models
Genetic Programming
... and a lot more
As you can see, the subject matter stretches into the higher levels of mathematics and academia, but Segaran successfully keeps the book intelligible to most software developers and examples are written in the easy-to-follow Python language. Further chapters cover more advanced topics, like optimization techniques and many of the more complex algorithms are deferred to the appendix.
The third chapter of the book, 'Discovering Groups,' deserves some explanation and may enlighten you as to how the book may be of some use in day-to-day software designs. Suppose you have a collection of data that is interrelated by a 'JOIN' in two sets of data. For example, certain customers may spend more time browsing certain subsets of movies. 'Discovering Groups' refers to the computational process of recognizing these patterns and sectioning data into groups. In terms of music or movies, these groups would represent genres. The marketing team may thus become aware that jazz enthusiasts buy more music at sale prices than do listeners of contemporary rock, or that listeners of late-60's jazz also listen to 70's prog, or similar such trends.
Certainly the applications of such tools as Programming Collective Intelligence provides us are broader than my imagination can handle. Insurance companies, airlines and banks are all part of massive industries that rely on precise knowledge of consumer trends and can certainly make use of the data-mining knowledge introduced in this book.
I have no major complaints about the book, particularly because it fills a gap in popular knowledge with no precursor of which I'm aware. Presentation-wise, even though Python is easy to read, pseudo-code is more timeless and even easier to read. You can't cut & paste from a paper book into a Python interpreter anyway. It may 've been more appropriate to use pseudo-code in print and keep the example code on the website (I'm sure it's there anyway).
If you ever find yourself browsing or referencing your algorithms text from college or even seriously studying algorithms for fun or profit, then I would highly recommend this book depending on your background in mathematics and computer science. That is, if you have a strong background in the academic study of related research, then you might look elsewhere, but this book, certainly suitable as an undergraduate text, is probably the best one for relative beginners that is going to be available for a long time.
You can purchase Programming Collective Intelligence from amazon.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
How is it quantified (Score:4, Insightful)
So, the question remains, how do they write these so-called recommendation algorithms?
For now I'm more interested to know how they quantify these improvements.
Re:How is it quantified (Score:4, Informative)
Re:How is it quantified (Score:5, Informative)
Which improvements? The Netflix competition?
They basically have a large dataset consisting of User, Movie, Rating. Of this set, they split it into two data sets. In the smaller subset they removed the ratings and didn't release these to the public. They didn't modify the larger subset at all. They had cinematch make predictions on the smaller subset (without having been told the real predictions) and use this as the baseline. Next, people that compete in the competition make predictions on the missing data and improvements can be calculated. They calculate the percent improvement as 100 * [Submission's Error] / [Cinematch's Error]
There are a number of ways to calculate the error but for the Netflix competition they use MASE (Mean Average Squared Error). Basically you take the sum of the squared difference between what was predicted and what the real rating was then divide it by the number of ratings.
Detailed information can be found on the Netflix Prize rules page [netflixprize.com] and there are a number of good posts on the forums as well.
Re: (Score:2)
God, then look it up.
Muahaha, you're new here aren't you? Why look anything up when you can just ask knowledgable people who'll be happy to tell you and in the process inform people who'd be interested to know too?
Re:How is it quantified (Score:4, Informative)
Quantification is fun field in itself, and by no means trivial. As other posters have noted, there are many leave-n-out approaches: basically, divide the dataset into a training set and a test set, and rank by how accurately the code predicts the test set given the training set.
These types of tests are good in that they are easy to understand by the judges and participants. The problem, of course, is that over repeated trials, information about the test set leaks out in the scoring, and the participants slowly overfit their algorithms to the test set based on scoring feedback (in the extreme case, there is no training data, only test data - the winning algorithms are just maps of matched test inputs to correct outputs.)
Even if you manage to ameliorate this problem (e.g by requiring submission of a function that will be applied to an unknown training set to produce a set of predictions,) there is still the risk that the high scoring functions are not very useful (e.g. predicting someones rating of "The Matrix" is easy and has a low RMS error, but do you even care about error from most peoples rating of "Mr Lucky," most have never heard of it?)
So, to be really useful, you want your rating (objective) function to be weighted by usefulness from the point of view of your business (e.g. yes, everyone like the current blockbuster, but will John Q Random be happy geting "Bringing Up Baby" instead?) Here, "happy" is defined as maximizing profits for the firm
So, you often a prize with a simple (but wrong) objective function. Then offer the winners a chance a real money if they work on the actual hard problems the firm is facing (this is what we do on Wall St, anyway
Who Cares About 0.1 Stars Difference? (Score:5, Interesting)
Re: (Score:2)
Re: (Score:1)
Re: (Score:3, Insightful)
Re: (Score:1)
Re: (Score:2, Insightful)
Of course people who still decide to rate The Wedding Singer seven stars can throw the whole thing off, like on iTunes where *no* album scores under a four or a five. But that's the problem isn't it, humans are entering these things. Not only do differenc
Re: (Score:1)
Re: (Score:2)
The fallacy is allowing extreme votes to be worth more than moderate votes, because moderate votes are more likely to be accurate.
It's better to use a simple up/down vote system. Everyone's vote is worth as much that way.
Re: (Score:1)
http://www.wired.com/techbiz/media/magazine/16-03/mf_netflix?currentPage=all [wired.com]
The algorithm wants to analyze your habits and then recommend the best movie for you. The interest to netflix is if you can get more people interested in movies that they haven't seen then they will rent more movies.
Re: (Score:3, Interesting)
I was initially intrigued by reccomendation algorithms.
Me too. Last time this topic rolled around I took a brief look at the Netflix competition and was disappointed. The star rating system was limited but more importantly there was a remarkable lack of data. Many of the teams that edged out some improvement did so by importing lots of data from other sources - with lots of holes in that process - and trying to discern patterns from that.
On the whole the exercise seems to be a variation of a couple
Re: (Score:2)
Sure, but that's why people import "lots of data from other sources," so why do you call that a bad thing? Yes, collecting more and better data is often more important than additional algorithm de
Re: (Score:2)
The winner of Netflix will probably be someone that took the problem from a completely new angle. Eventually the increments will reach there, as new algorithms are tweaked and edited to reach the milestone, but I'm guessing that someone will come along and take the prize another way before t
Re: (Score:1)
Re: (Score:2, Informative)
Re: (Score:2)
I think it's reasonable to expect that a 0.5 star accuracy improvement on a 5 star system would be noticeable by enough people (although not all) to make a difference - presumably resulting in better confidence in the
Re: (Score:1)
Re: (Score:1)
Re: (Score:1)
Thank you, Caption Obvious!
Re: (Score:1)
a.) do not understand the difference between a recommendation system and a ratings system
-or-
b.) do not know English well enough to coherently phrase a meaningful question
My answer to you assumed "a". I'm sorry it turns out it was "b".
The fact is, Netflix isn't trying to change a rating from 3.0 to 3.1 or 2.9. They just want to know if you will like that movie regardless of its average rating.
Re: (Score:1)
What question did I post that you thought you were answering? The last sentence of your last post shows a complete misunderstanding on your part. Is English your first language? Based on your sig, I wouldn't have thou
Numbers? (Score:2, Informative)
BellKor: 9.08%
Gravity/Dinosaurs: 8.82%
BigChaos: 8.80%
How are they judging "improvement?" (Score:1)
Re: (Score:1)
Re: (Score:1)
With 35535 entrants, this may just be noise (Score:3, Interesting)
There are now 35535 entries in the Netflix competition. If they all used roughly the same algorithm, with some randomness in the tuning variables, we'd expect to see results about like what we've seen. I think we're looking at noise here.
The same phenomenon shows up with mutual funds. Some outperform the market, some don't, but prior year results are not good predictors of future results.
Re: (Score:3, Insightful)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Netflix is a subscription all-you-can-eat service. So they would most prefer if you got a large plan and never used it. Since the only thing that keeps you renewing your subscription is your enjoyment of the movies, and since it costs them money every time you rent a movie, they have a vested interest in trying to maximize enjoyment per movie.
Actually, they'd probably rather you really enjoy 1/3 of the
Re: (Score:3, Insightful)
Re: (Score:3, Informative)
I bought this book (Score:5, Informative)
I was at the Borders and was looking for something to pass the weekend, and I'd been doing some sound effects library work, so I took a look at this.
It has a lot of statistics; it's essentially a statistics-in-use book , with code examples in Python of all of the algorithms. That said, it makes all of the topics very accessible, and proposes many different ways of solving different wisdom-of-crowds type problems, and gives you enough knowledge so you'd be able to hear someone pitch you their dataset, and you'd be able to say "Oh, you wanna do full-text relevance ranking" or "You need decision tree for that" or "you just want the correlation." The book very much has a sort of statistics-as-swiss-army-knife approach.
Also, I'm not Pythonic, but I was able to translate all of the algorithms into Ruby as I went, even turning the list comprehensions into the Rubyish block/yield equivalents, so his style is not too idiomatic.
Re: (Score:3, Informative)
The examples are practical and described quite well, even if ones math skills are not that great.
And the example in Python are almost looking pseudo-code like, even if one has little to no Python skills, the language is not a huge barrier.
5 stars out of 5!
The reviews at amazing are also quite quite good:
http://www.amazon.com/review/product/0596529325/ref=pd_bbs_sr_1_cm_cr_acr_txt?_encoding=UTF8&showViewpoints=1 [amazon.com]
23 ratings
Re: (Score:2)
Yeah, good reviews there.
A point the reviewers make that I didn't very clearly is that it does have a bunch of statistics, but it also has neural networks, and a bunch of other stuff that are more along the lines of "machine learning." One of the reviewers said it was the "best book on machine learning ever written," which may be true, but if and only if you're not a theorist or academic computer scientist.
Re: (Score:2)
I might call it "the best PRACTICAL/APPLIED book on machine learning ever written".
For a more theoretical approach, this book is quite nice: Machine Learning, Tom Mitchell, McGraw Hill, 1997.
( http://www.cs.cmu.edu/~tom/mlbook.html [cmu.edu] )
(Btw: great signature.
Where to bet your money (Score:2)
Re: (Score:1)
Re: (Score:2, Insightful)
Re: (Score:2, Insightful)
A million dollars? This is what happens when business people dabble in science. Artificial Intelligence grad students and professors have been studying these kinds of problems for decades.
I think that is the point - academia has been studying this for decades and has yet to produce meaningful results. I'm not saying that universities haven't contributed their fair share of technological advances through the years, but doing so in a practical and timely manner isn't exactly what they're known for. When business and/or money gets thrown into the mix, the pace of progress tends to rapidly accelerate.
X Prize Foundation [xprize.org]
Millennium Problems [claymath.org]
2008 Templeton Prize [nytimes.com]
Netflix could have saved a boatload of money by throwing some cash at a university with an established AI group and asking them to research the current state-of-the-art
According to the Netfli [netflixprize.com]
Re:Ever been to grad school? (Score:4, Insightful)
This is an attempt to bring out new solutions.
Eivind.
Re: (Score:1)
Amazon is best here (Score:1)
This can only be done with a shopping cart style, where as Netflickshas to wait for them to select their movie before they can recommend anything, seriously they should partner up with Amazon,
the people who rented this movie from Netf
"As of this writing" (Score:3, Interesting)
Come on already... (Score:2, Insightful)
Seriously. It's a trend to create websites with more dynamic and shared content. That's it. No church, no ideology, no 2.0.
This book offers a great fundation (Score:1)
Good introduction to pattern recognition (Score:2, Informative)
Why has no one beat the Netflix algorithm yet (Score:3, Interesting)
The Netflix competition, in principle, is an example of an interesting class of prediction algorithms. There is a lot of good work in academia in this area and on the face of it one might be surprised that no one has beat Netflix yet.
Unfortunately Netflix restricts the data that can be applied to prediction. You have to use their data which includes only movie title and genre. A much better job could be done if something like the Internet Movie Database were fused with the title selection information. This would allow the algorithm to predict based on actors, directors and detailed genre. For example, I see all movies directed by John Woo. Given that I've seen all of his movies, it's not hard to predict that I'm going to see his next movie.
it works (Score:2)
"A teacher is offering empirical evidence that when you're mining data, augmenting data is better than a better algorithm. He explains that he had teams in his class enter the Netflix challenge, and two teams went two different ways. One team used a better algorithm while the other harvested augmenting data on movies from the Internet Movie Database. And this team, which used a simpler algorithm, did much better -- nearly as well as the best
Re: (Score:1)
Does Netflix restrict what you can use in your algorithm now? I haven't checked the rules recently, but I know at first a lot of people were using IMDB and other sites for extra predictors.
Re: (Score:1)
Moreover the problem with the Netflix dataset is they have intentionally inserted misinformation into the dataset for whatever reason.
Our answer was to have someone (read:me) to comb over each of the 17,000 entries and screen for basic accuracy. For ins
Re: (Score:1)
Just an Idea (Score:1)
The L Word (Score:1)
Of course maybe The L Word is about lesbian alien spies with super powers. Huh. I'm gonna go check it out.
Another Review of Collective Intelligence (Score:2)
~~~~
Have you ever wondered how:
* Google comes up with its search results
* Amazon recommends you books/movies/music
* spam filters decide good from bad
Well, Toby Segaran not only explains these topics and more in Collective Intelligence, but he does so in a way accessible to software developers t