Recommendation Systems - Mining of Massive Datasets - page 314

EXAMPLE 9.12 Suppose we guess that U and V should each have entries that are all 1s, as
shown in Fig. 9.10 . This is a poor guess, since the product, consisting of all 2s, has entries
that are much below the average of the entries in M . Nonetheless, we can compute the
RMSE for this U and V ; in fact the regularity in the entries makes the calculation espe-
cially easy to follow. Consider the first rows of M and UV . We subtract 2 (each entry in
UV ) from the entries in the first row of M , to get 3 , 0 , 2 , 2 , 1. We square and sum these to
get 18. In the second row, we do the same to get 1 , −1 , 0 , 2 , −1, square and sum to get 7.
In the third row, the second column is blank, so that entry is ignored when computing the
RMSE. The differences are 0 , 1 , −1 , 2 and the sum of squares is 6. For the fourth row, the
differences are 0 , 3 , 2 , 1 , 3 and the sum of squares is 23. The fifth row has a blank entry
in the last column, so the differences are 2 , 2 , 3 , 2 and the sum of squares is 21. When we
sum the sums from each of the five rows, we get 18 + 7 + 6 + 23 + 21 = 75. Generally,
we shall stop at this point, but if we want to compute the true RMSE, we divide by 23 (the
number of nonblank entries in M ) and take the square root. In this case is

the RMSE. □

Figure 9.10 Matrices U and V with all entries 1

9.4.3 Incremental Computation of a UV-Decomposition

Finding the UV-decomposition with the least RMSE involves starting with some arbitrarily
chosen U and V , and repeatedly adjusting U and V to make the RMSE smaller. We shall
consider only adjustments to a single element of U or V , although in principle, one could
make more complex adjustments. Whatever adjustments we allow, in a typical example
there will be many local minima - matrices U and V such that no allowable adjustment re-
duces the RMSE. Unfortunately, only one of these local minima will be the global minim-
um - the matrices U and V that produce the least possible RMSE. To increase our chances
of finding the global minimum, we need to pick many different starting points, that is, dif-
ferent choices of the initial matrices U and V . However, there is never a guarantee that our
best local minimum will be the global minimum.
We shall start with the U and V of Fig. 9.10 , where all entries are 1, and do a few adjust-
ments to some of the entries, finding the values of those entries that give the largest pos-
sible improvement to the RMSE. From these examples, the general calculation should be-
come obvious, but we shall follow the examples by the formula for minimizing the RMSE