342
CHAPTER 9. RECOMMENDATION SYSTEMS
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
p
75/23 = 1.806 is the RMSE.
✷
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 lo-
cal minima – matrices U and V such that no allowable adjustment reduces
the RMSE. Unfortunately, only one of these local minima will be the global
minimum – the matrices U and V that produce the least possible RMSE. To
increase our chances of ﬁnding the global minimum, we need to pick many dif-
ferent starting points, that is, diﬀerent 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 adjustments to some of the entries, ﬁnding the values of those entries that
give the largest possible improvement to the RMSE. From these examples, the
general calculation should become obvious, but we shall follow the examples
by the formula for minimizing the RMSE by changing a single entry. In what
follows, we shall refer to entries of U and V by their variable names u11, and
so on, as given in Fig. 9.9.
Example 9.13 : Suppose we start with U and V as in Fig. 9.10, and we decide
to alter u11 to reduce the RMSE as much as possible. Let the value of u11 be
x. Then the new U and V can be expressed as in Fig. 9.11.


x
1
1
1
1
1
1
1
1
1


×

1
1
1
1
1
1
1
1
1
1

=


x + 1
x + 1
x + 1
x + 1
x + 1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2


Figure 9.11: Making u11 a variable
Notice that the only entries of the product that have changed are those in
the ﬁrst row. Thus, when we compare UV with M, the only change to the
RMSE comes from the ﬁrst row. The contribution to the sum of squares from
the ﬁrst row is
5 −(x + 1)
2 +
2 −(x + 1)
2 +
4 −(x + 1)
2 +
4 −(x + 1)
2 +
3 −(x + 1)
2
