Database Reference
In-Depth Information
therein, all short sessions have been removed and fewer products (namely, those of
the core assortment) are considered.
■
Despite the disappointing results, the question arises of whether the two
approaches to factorization, i.e., the Markov chain-based approach and collaborative
filtering according to the two previous examples, may be combined in a meaningful
way. This, indeed, is possible and will be studied in the course of the chapter in
connection with tensor factorization.
Another way is to use techniques different from matrix factorization, like
hierarchical decompositions, in order to exploit the structure of the probability
matrix and develop corresponding representations based on a small number of
parameters. Interesting combinations of both approaches are
hierarchical matrices
(H-
matrices
) introduced by Wolfgang Hackbusch which rely on local low-rank
approximations, i.e., blocks of the matrix are represented in factorized formats.
H-matrices are a very powerful technique for matrix compression and a topic of
current research. Since it is not a direct factorization technique, we will no further
delve into this topic but refer to the literature [Beb08, GH03, Ha99, HK00].
However, there is still another interesting aspect of matrix factorization important
for recommendation engines - incomplete data. This brings us to the task of
exact matrix completion that has become recently very popular because of some
outstanding and surprising results that have been achieved. Motivated by the revolu-
tionary work on
compressed sensing
[CRT06, Don06], a signal processing technique
for efficiently reconstructing a signal, some of its pioneers, especially Emmanuel
Candes, Benjamin Recht, and Terence Tao, have leveraged basic ideas to the problem
of exact matrix completion. The matrix completion problem will be discussed in the
next section.
8.5 Back to Netflix: Matrix Completion
In many practical applications, one would like to recover a matrix from a sample of
its entries. In case of recommendation engines, the best known example is the
Netflix price. Users are given the opportunity to rate movies, but users typically rate
only very few movies so that there are very few scattered observed entries of the
data matrix. Yet one would like to complete the matrix so that Netflix might
recommend titles that any particular user is likely to be willing to order. In the
Netflix competition, for each of the users under consideration, a part of her/his ratings
was provided in the training set. For evaluation, the remaining movies the user has
rated were provided, and the task was to guess her/his actual ratings. The Netflix
price was awarded to the recommendation solution of highest prediction rate on the
test set. So the Netflix competition constitutes a classical matrix completion problem.
In mathematical terms, the matrix completion problem may be formulated as
follows: we again consider a data matrix
A
mn
which we would like to know as
precisely as possible. Unfortunately, the only information about
A
is a sampled set
∈R
