352
CHAPTER 9. RECOMMENDATION SYSTEMS
gives values for all user-item pairs, that value can be used to predict the
value of a blank in the utility matrix. The intuitive reason this method
makes sense is that often there are a relatively small number of issues (that
number is the “thin” dimension of U and V ) that determine whether or
not a user likes an item.
✦Root-Mean-Square Error: A good measure of how close the product UV
is to the given utility matrix is the RMSE (root-mean-square error). The
RMSE is computed by averaging the square of the diﬀerences between
UV and the utility matrix, in those elements where the utility matrix is
nonblank. The square root of this average is the RMSE.
✦Computing U and V : One way of ﬁnding a good choice for U and V in a
UV-decomposition is to start with arbitrary matrices U and V . Repeat-
edly adjust one of the elements of U or V to minimize the RMSE between
the product UV and the given utility matrix. The process converges to
a local optimum, although to have a good chance of obtaining a global
optimum we must either repeat the process from many starting matrices,
or search from the starting point in many diﬀerent ways.
✦The Netﬂix Challenge: An important driver of research into recommenda-
tion systems was the Netﬂix challenge. A prize of $1,000,000 was oﬀered
for a contestant who could produce an algorithm that was 10% better
than Netﬂix’s own algorithm at predicting movie ratings by users. The
prize was awarded in Sept., 2009.
9.7
References for Chapter 9
[1] is a survey of recommendation systems as of 2005. The argument regard-
ing the importance of the long tail in on-line systems is from [2], which was
expanded into a book [3].
[8] discusses the use of computer games to extract tags for items.
See [5] for a discussion of item-item similarity and how Amazon designed
its collaborative-ﬁltering algorithm for product recommendations.
There are three papers describing the three algorithms that, in combination,
won the NetFlix challenge. They are [4], [6], and [7].
1. G. Adomavicius and A. Tuzhilin, “Towards the next generation of rec-
ommender systems: a survey of the state-of-the-art and possible exten-
sions,” IEEE Trans. on Data and Knowledge Engineering 17:6, pp. 734–
749, 2005.
2. C. Anderson,
http://www.wired.com/wired/archive/12.10/tail.html
