Database Reference
In-Depth Information
Example 8.2
Let us consider
the following factorization for Example 8.1
with
r ¼ 1
:
0
@
1
A
0
@
1
A
:
:
:
:
1
0
0
23
2
76
9
65
5
17
:
ð Þ
|
{z
}
Y
:
:
:
:
¼
:
:
:
:
2
0
23
2
76
9
65
5
17
0
05
0
55
1
93
1
03
0
:
1
0
:
02
0
:
28
0
:
97
0
:
52
|
{z
}
X
|
{z
}
A
0
@
1
A
01 05
1511
0501
|
{z
}
A
While the initial matrix
A
consists of 12 elements, the factors
X
and
Y
taken
together contain only 7 elements. Now we have to assess whether our rank-1
approximation
XY ¼ A
is a sufficiently good approximation to
A
. If not, we may
increase the rank
r
, which, of course, entails an increase of complexity of the factors.
It is obvious, however, that for large
n
p
and
n
s
and a moderate rank, the factorized
representation is by orders of magnitude more compact than the explicit one.
■
In terms of CF, a commonly encountered intuitive interpretation is as follows:
the matrix
Y
maps the sessions to their virtual profiles, the number of which is given
by the rank
r
, and the matrix
X
maps profiles to their products of reference.
It is also noteworthy that optimal factors are almost never unique, even if their
product is. This is only a minor difficulty since we are eventually interested in the
latter and may choose among the corresponding optimal factors arbitrarily.
Please note that the framework stipulated by (
8.1
) is of profound generality.
It encompasses a vast majority of commonly deployed factorization models.
In particular, we stress that the computational complexity of a factorization (
8.1
)
depends crucially on the choice of
f
and
C
1
,
C
2
. For example, the factorization
model related to PCA, which we shall focus on in what follows, may be reduced to a
rather “simple” algebraic problem capable of being solved optimally by algorithms
of polynomially bounded complexity. On the other hand, it is possible to state the
well-known clustering or vector quantization problem in terms of the above frame-
work. This problem, however, is NP-hard.
As opposed to the control theoretic varieties discussed in the foregoing chapters,
REs based on CF are “na¨ve-old fashioned.” Why, you may ask yourself, after so
keenly campaigning for the latter, do we suddenly address so unsophisticated and
outdated approach? The reasons for doing so are as follows:
• In recent research, we have found a way to perform PCA-based CF in a realtime
adaptive fashion. Since this topic is intended to be about adaptive rather than
only about the smaller class of control theoretic recommendation systems, this
fits well into the framework.
• We are currently working on higher-order (i.e., tensor) generalization of
PCA-based CF. This enables to deploy CF in a less behavioristic fashion.
