Databases Reference
In-Depth Information
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 finding the global minimum, we need to pick many dif-
ferent starting points, that is, different 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, finding 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 u
11
, 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 u
11
to reduce the RMSE as much as possible. Let the value of u
11
be
x. Then the new U and V can be expressed as in Fig. 9.11.
2
3
2
3
x
1
x + 1
x + 1
x + 1
x + 1
x + 1
4
5
×
4
5
1
1
2
2
2
2
2
1
1
1
1
1
1
1
=
2
2
2
2
2
1
1
1
1
1
1
1
2
2
2
2
2
1
1
2
2
2
2
2
Figure 9.11: Making u
11
a variable
Notice that the only entries of the product that have changed are those in
the first row. Thus, when we compare U V with M , the only change to the
RMSE comes from the first row. The contribution to the sum of squares from
the first row is
2
+
2
+
4−(x + 1)
2
+
2
+
2
5−(x + 1)
2−(x + 1)
4−(x + 1)
3−(x + 1)
This sum simplifies to
(4−x)
2
+ (1−x)
2
+ (3−x)
2
+ (3−x)
2
+ (2−x)
2
