348
CHAPTER 9. RECOMMENDATION SYSTEMS
Gradient Descent
The technique for ﬁnding a UV-decomposition discussed in Section 9.4
is an example of gradient descent. We are given some data points – the
nonblank elements of the matrix M – and for each data point we ﬁnd
the direction of change that most decreases the error function: the RMSE
between the current UV product and M. We shall have much more to
say about gradient descent in Section 12.3.4. It is also worth noting that
while we have described the method as visiting each nonblank point of
M several times until we approach a minimum-error decomposition, that
may well be too much work on a large matrix M. Thus, an alternative
approach has us look at only a randomly chosen fraction of the data when
seeking to minimize the error. This approach, called stochastic gradient
descent is discussed in Section 12.3.5.
Avoiding Overﬁtting
One problem that often arises when performing a UV-decomposition is that we
arrive at one of the many local minima that conform well to the given data, but
picks up values in the data that don’t reﬂect well the underlying process that
gives rise to the data. That is, although the RMSE may be small on the given
data, it doesn’t do well predicting future data. There are several things that can
be done to cope with this problem, which is called overﬁtting by statisticians.
1. Avoid favoring the ﬁrst components to be optimized by only moving the
value of a component a fraction of the way, say half way, from its current
value toward its optimized value.
2. Stop revisiting elements of U and V well before the process has converged.
3. Take several diﬀerent UV decompositions, and when predicting a new
entry in the matrix M, take the average of the results of using each
decomposition.
9.4.6
Exercises for Section 9.4
Exercise 9.4.1: Starting with the decomposition of Fig. 9.10, we may choose
any of the 20 entries in U or V to optimize ﬁrst. Perform this ﬁrst optimization
step assuming we choose: (a) u32 (b) v41.
Exercise 9.4.2: If we wish to start out, as in Fig. 9.10, with all U and V
entries set to the same value, what value minimizes the RMSE for the matrix
M of our running example?
