[Link]

ie

Recommender Systems
COMP 9065

Dr. Diarmuid Grimes

Primary source material for these slides is the Aggarwal book, Recommender Systems
Handbook, Francesco Ricci module on Information Retrieval, and Derek Bridge
module on Intelligent Media Systems
Regression

§ Basic CF method can be viewed as a heuristic regression

method:
§ Predicted rating is a weighted linear combination of (subset) of other
ratings
§ Weight is decided heuristically rather than through learning on a set
of training data like in typical regression
§ Regression method is optimisation approach, choose weights such
that the prediction error is minimised on a set of training data.
§ User-based: predicted rating is linear combination of column values
§ Item-based: predicted rating is linear combination of row values
§ Therefore standard neighborhood CF method can be viewed as
heuristic variant of lin reg where regression coefficients are
heuristically set to similarity values for related (neighboring)
items/users and to 0 for unrelated items/users
User-based Nearest Neighbor Regression

§ One area of research in Recommender Systems is

investigating whether we could learn better weights
through a standard regression approach compared to the
more common heuristic method.

§ Let’s consider the user based

𝑢,𝑖 = 𝑟𝑢 + ' w𝑣u x (𝑟𝑣,𝑖 − 𝑟
𝑟$ *𝑣)
,∈..

§ Same as before except the neighborhood is defined

independent of whether or not the other users have rated a
specific item
User-based Nearest Neighbor Regression

§ Least squares approach, find values of w𝑣u such that the

following is minimised:
∑ (𝑟 − $
𝑟 )2
,∈Pu(i) u𝑖 𝑢𝑖

§ Same as before except the neighborhood is defined

independent of whether or not the other users have rated a
specific item
Regression: Sparsity and Bias issues

§ One problem with this regression approach is that the size

of the Pu(i) can be vastly different for the same user u and
varying item indices (denoted by i).
§ This is because of the extraordinary level of sparsity
inherent in ratings matrices.
§ As a result, the regression coefficients become heavily
dependent on the number of peer users that have rated a
particular item i along with user u.
Regression: Sparsity and Bias issues

§ For example, consider a scenario where the target user u

has rated both Gladiator and Nero.
§ Out of the k nearest neighbors of the target u, only one user
might rate the movie Nero, whereas all k might have rated
Gladiator.
§ As a result, the regression coefficient wuv of the peer user v
who rated Gladiator will be heavily influenced by the fact
that they are the only user who have rated Gladiator.
§ This will result in overfitting because this (statistically
unreliable) regression coefficient might add noise to the
rating predictions of other movies.
Alternatives Nearest Neighbor Regression

§ Item-based
§ Same as user based: Learn the similarity weight instead of using
adjusted cosine

§ Combined item and user!

§ Same as above, but learn weights regarding the items and the users
Model-Based Collaborative Filtering
Model-Based Collaborative Filtering

§ Summarized data model built up front.

§ Training phase separate from prediction phase.

§ Models produced by traditional ML methods can be

generalised to collaborative filtering problem:
§ Data classification problem, given mxn matrix where first (n-1)
columns are features (fully specified values), and last column is
dependent variable, predict the missing values in the nth column.
Model-Based Collaborative Filtering
72 CHAPTER 3. MODEL-BASED COLLABORATIVE FILTERING

TRAINING
ROWS
NO
DEMARCATION
BETWEEN
TRAINING AND
TEST ROWS

TEST
ROWS

INDEPENDENT DEPENDENT NO DEMARCATION BETWEEN DEPENDENT

VARIABLES VARIABLE AND INDEPENDENT VARIABLES

(a) Classification (b) Collaborative filtering

Figure 3.1: Revisiting Figure 1.4 of Chapter 1. Comparing the traditional classification
problem with Recommender Systems,
collaborative filtering. Aggarwal,
Shaded entries Pg. 72, Figure
are missing and3.1
need to be predicted.
Model-Based Collaborative Filtering

§ Summarized data model built up front.

§ Training phase separate from prediction phase.

§ Models produced by traditional ML methods can be generalised

to collaborative filtering problem.

§ Traditional meta-algorithm methods for classification problem

like bagging, boosting and model-combination methods have also
been extended to collaborative filtering.

§ However, important to note that methods that work well in CF

are not necessarily those that work well in data classification
problem (e.g. latent factors model).
Model-Based vs Neighborhood-Based

§ Space efficiency:
§ Size of the learned model is much smaller than the original matrix.

§ Training time and prediction time:

§ Typically much faster in the preprocessing phase of constructing the
trained model.
§ Also, the compact and summarized model can usually be used to
make predictions efficiently.

§ Overfitting:
§ Summarization approach of model-based methods can often help in
avoiding overfitting.
Latent Factor Models

§ Mentioned previously in the context of dimensionality

reduction
§ Basic idea is to exploit the fact that significant portions of
the rows and columns of data matrices are highly
correlated.
§ As a result, the data has built-in redundancies and the
resulting data matrix is often approximated quite well by a
low-rank matrix.
§ Because of the inherent redundancies in the data, the fully
specified low- rank approximation can be determined even
with a small subset of the entries in the original matrix.
§ This fully-specified low rank approximation often provides a
robust estimation of the missing entries.
Latent Factor Models and Dimensionality
Reduction
§ State-of-the-art in recommender systems!
§ These models leverage well-known dimensionality reduction
methods to fill in the missing entries.
§ Dimensionality reduction methods are used commonly in other
areas of data analytics to represent the underlying data in a small
number of dimensions.
§ The basic idea of dimensionality reduction methods is to rotate
the axis system, so that pairwise correlations between
dimensions are removed.
§ The important aspect is that this reduced, rotated, and
completely specified representation can be robustly estimated
from an incomplete data matrix.
§ Once the completely specified representation has been obtained,
one can rotate it back to the original axis system in order to
obtain the fully specified representation
Matrix factorization

§ It is always possible to decompose a given matrix R into

R = U λ VT
§ Here, U is an m×m matrix with columns containing the m
orthonormal eigenvectors of RRT.
§ The matrix V is an n × n matrix with columns containing the n
orthonormal eigenvectors of RTR.
§ λ is an m × n diagonal matrix in which only diagonal entries are
nonzero and they contain the square-root of the nonzero
eigenvalues of RTR (or equivalently, RRT).
§ It is noteworthy that the eigenvectors of RTR and RRT are not the
same and will have different dimensionality when m != n.
§ However, they will always have the same number of (nonzero)
eigenvalues, which are identical in value. The values on the
diagonal of λ are also referred to as singular values.
Matrix factorization

§ Furthermore, one can approximately factorize the matrix by

using truncated SVD, where only the eigenvectors
corresponding to the d ≤ min{m, n} largest singular values
are used.
§ Truncated SVD is computed as follows:
R ≈ Ud λd VdT

where Ud, λd, VdT are m×d, d×d, and n×d matrices, respectively.
§ The matrices Ud and Vd, respectively, contain the d largest
eigenvectors of RRT and RTR, whereas the matrix λd contains
the square-roots of the d largest eigenvalues of either
matrix along its diagonal.
Matrix factorization

R ≈ Ud λd VdT

where Ud, λd, VdT are m×d, d×d, and n×d matrices, respectively.
§ The matrix Vd contains the top eigenvectors of RTR, which is the
reduced basis representation required for dimensionality
reduction.
§ Furthermore, the matrix Ud λd contains the transformed and
reduced m × d representation of the original ratings matrix in the
basis corresponding to Vd.
§ It can be shown that such an approximate factorization has the
least mean-squared error of the approximated entries as
compared to any other rank-d factorization.
§ Therefore, if we can approximately factorize the ratings matrix R
in the form above, it provides us with the reduced basis as well
as the representation of the ratings in the reduced basis.
Matrix factorization

§ Factorization is only defined for fully specified matrix.

§ Solution: Recast the formulation as an optimization
problem, in which the squared error of factorization is
optimized only over the observed entries of the ratings
matrix.
§ It is also possible to explicitly solve this modified
formulation using nonlinear optimization techniques.
§ This results in a robust and unbiased lower dimensional
representation.
Matrix factorization and rank for latent factors
modeling
§ The key idea is that any m × n matrix R of rank k ≪ min{m, n} can
always be expressed in the following product form of rank-k
factors:
R = UVT

where U, VT are m×k and n×k matrices, respectively.

§ The rank of both the row space and the column space of R is k.
§ Each column of U can be viewed as one of the k basis vectors of
the k-dimensional column space of R, and the jth row of V
contains the corresponding coefficients to combine these basis
vectors into the jth column of R.
§ Alternatively, one can view the columns of V as the basis vectors
of the row space of R, and the rows of U as the corresponding
coefficients.
 Rank matrix factorization
3.6. LATENT FACTOR MODELS 95

SLEEPLESS IN SEATTLE
PRETTY WOMAN
JULIUS CAESAR

CASABLANCA
CLEOPATRA

SLEEPLESS IN SEATTLE
ROMANCE
HISTORY

PRETTY WOMAN
NERO

JULIUS CAESAR

CASABLANCA
CLEOPATRA
1 1 1 1 0 0 0 1 1 0

NERO
HISTORY 2 1 1 1 0 0 0 2 1 0

3 1 1 1 0 0 0 3 1 0
HISTORY 1 1 1 0 0 0
4 1 1 1 1 1 1 1 1
BOTH 4
X ROMANCE 0 0 1 1 1 1
5 -1 -1 -1 1 1 1 5 -1 1
VT
ROMANCE 6 -1 -1 1 1 1 1 6 -1 1

7 -1 -1 -1 1 1 1 7 -1 1

R U
(a) Example of rank-2 matrix factorization
ATTLE
IN SEA

Recommender Systems, Aggarwal, Pg. 95, Figure 3.7

N
OMAN
ESAR

CA
A
Matrix factorization and rank

§ So basic principle is to approximately factor R into U and V:

R ≈ UVT
where U, VT are m×k and n×k matrices, respectively.
§ Each column of U (or V ) is referred to as a latent vector or
latent component
§ Each row of U (or V) is referred to as a latent factor.
§ The ith row, 𝑢*𝑖 , of U is referred to as a user factor, and it
contains k entries corresponding to the affinity of user i
towards the k concepts in the ratings matrix.
§ The ith row, 𝑣*𝑖 , of V is referred to as an item factor, and it
contains k entries corresponding to the affinity of item i
towards the k concepts in the ratings matrix.
Matrix factorization and rank

§ Approximation so what is the error?

§ The error of this approximation is equal to
||R − UVT ||2
where || · ||2 represents the sum of the squares of the
entries in the resulting residual matrix (R − U VT).
§ This quantity is also referred to as the (squared)
Frobenius norm of the residual matrix.
§ The residual matrix typically represents the noise in the
underlying ratings matrix, which cannot be modeled by
the low-rank factors.
Matrix factorization and rank

§ So each rating in R can be approximated by the dot product

of the associated user and item factors:
𝑟56 ≈ 𝑢*𝑖 7 𝑣*𝑗
§ Note that 𝑢*𝑖 is (𝑢𝑖1, …, 𝑢𝑖𝑘 ) and similarly 𝑣*𝑗
§ Therefore
𝑟56 ≈ ∑<=>? 𝑢𝑖𝑠 ∗ 𝑣𝑖𝑠

which is equivalent to the sum of the affinity of the user to the

concept times the affinity of the item to the concept over the
k concepts.
Matrix factorization and rank

§ A latent vector may often be an arbitrary vector of positive

and negative values and it can be difficult to give it a
semantic interpretation.
§ However, it does represent a dominant correlation pattern
in the ratings matrix.
Finding U and V

§ How do we find our U and V?

§ Optimisation problem, find U and V such that the following
is minimised:
0.5*||R − UVT ||2
§ But Frobenius norm cannot be computed on a matrix
with missing entries!
§ So objective function needs to be rewritten in terms of
observed values alone.
Adapted Error Function

§ Let S set of the observed user-item pairs

§ Error for observed entries
∑ <
𝑒56 = 𝑟56 − 𝑟$
56 = 𝑟56 − D>? 𝑢𝑖𝑝 ∗ 𝑣𝑗𝑝
§ Objective (error) function
1 1
J= ' 𝑒56 = ' (𝑟56 − 𝑟$
F
56 ) F
2 2
(5,6)∈H (5,6)∈H
F
<
1
= ' 𝑟56 − (' 𝑢𝑖𝑞 ∗ 𝑣𝑗𝑞)
2
(5,6)∈H J>?
Gradient
98
Descent Approach
CHAPTER 3. MODEL-BASED COLLABORATIVE FILTERING

Algorithm GD(Ratings Matrix: R, Learning Rate: α)

begin
Randomly initialize matrices U and V ;
S = {(i, j) : rij is observed};
while not(convergence) do
begin
Compute each error eij ∈ S as the observed entries of R − U V T ;
for each user-component pair (i, q) do u+iq ⇐ uiq + α · j:(i,j)∈S eij · vjq ;
+
for each item-component pair (j, q) do vjq ⇐ vjq + α · i:(i,j)∈S eij · uiq ;
for each user-component pair (i, q) do uiq ⇐ u+iq ;
+
for each item-component pair (j, q) do vjq ⇐ vjq ;
Check convergence condition;
end
end

Figure 3.8: Gradient descent

Recommender Systems, Aggarwal, Pg. 98, Figure 3.8

unknown variables, which need to be learned to minimize the objective function. This can
be achieved simply with gradient descent methods. Therefore, one needs to compute the
partial derivative of J with respect to the decision variables uiq and vjq :
Overfitting and Regularization

§ One of the main problems with this approach arises

when the ratings matrix R is sparse and relatively few
entries are observed.
§ In such cases, the set S of observed ratings is small,
which can cause overfitting.
§ A common approach for addressing this problem is to
use regularization.
§ Regularization reduces the tendency of the model to
overfit at the expense of introducing a bias in the
model.
Regularization

§ In regularization, the idea is to discourage very large values of the

coefficients in U and V in order to encourage stability.
§ Therefore, a regularization term
𝜆
𝑈 F+ 𝑉 F
2
is added to the objevtive function, where λ > 0 is the regularization
parameter and as before ||*||denotes the (squared) Frobenius
norm of the matrix.
Regularization

§ The basic idea is to create a bias in favor of simpler solutions by

penalizing large coefficients.
§ This is a standard approach, which is used in many forms of
classification and regression, and also leveraged by collaborative
filtering.
§ The parameter λ is always non-negative and it controls the
weight of the regularization term.
Regularized Objective Function
N < O <
1 F 𝜆 𝜆
J= ' 𝑒56 + ' ' 𝑢𝑖𝑞 + ' ' 𝑣𝑗𝑞 F
F
2 2 J>?
2 J>?
(5,6)∈H 5>? 6>?

? < F P N
= ∑ 𝑟56 − (∑J>? 𝑢𝑖𝑞 ∗ 𝑣𝑗𝑞 ) + ∑5>? ∑<J>? 𝑢𝑖𝑞 F +
F (5,6)∈H F
P O
∑6>? ∑<J>? 𝑣𝑗𝑞 F
F
 UpdatedCHAPTER
Gradient
3. Descent approach
MODEL-BASED COLLABORATIVE FILTERING

gularized) updates in Figure 3.8to include regularization terms. The modified updates
be written as follows:
⎛ ⎞
#
uiq ⇐ uiq + α ⎝ eij · vjq −λ · uiq ⎠ ∀q ∈ {1 . . . k}
j:(i,j)∈S
⎛ ⎞
#
vjq ⇐ vjq + α ⎝ eij · uiq −λ · vjq ⎠ ∀q ∈ {1 . . . k}
i:(i,j)∈S

updates can be executed to convergence. One can also write these updates in terms of
m × n error matrix E = [eij ] in which unobserved entries of E are set to 0:

U ⇐ U (1 −α · λ) + αEV
V ⇐ V (1 −α · λ) + αE T U

that the multiplicative term (1 −α · λ) shrinks the parameters in each step, which is
ult of regularization. If the matrix form is to be used for updates, care must be taken
Parameter tuning for α

§ α > 0 represents the step size.

§ A small constant value can work reasonably well
§ For example, a value of 0.005 was found to result in good
performance in the case of the Netflix Prize data set.
§ Alternatively, one might use the bold driver algorithm to select α
adaptively in each iteration in order to avoid local optima and
speed up convergence:
§ error rate decreased => increase α
§ error rate increased => decrease α and reset values to previous iteration
Parameter tuning for λ

§ The simplest method to select λ is to hold out a fraction of the

observed entries in the ratings matrix and not use them to train
the model.
§ The prediction accuracy of the model is tested over this subset of
held out entries.
§ Different values of λ are tested, and the value of λ that provides
the highest accuracy is used.
§ Alternatively could use cross-validation.
§ Finally, for better results, different regularization parameters λ1
and λ2 may be used for the user factors and item factors.
Baseline predictors and Mean Centering

§ Earlier mentioned notion of user/item biases that are

independent of the user-item interaction.

§ We can use mean-centering to remove some of these biases, and

apply our latent factor model to the result.

§ How do we compute missing ratings?

Baseline predictors and Mean Centering

§ Associated with each user i, we have a variable oi, which

indicates the general bias of users to rate items.
§ For example, if user i is a generous person, who tends to rate all items
highly, then the variable oi will be a positive quantity.
§ On the other hand, the value of oi will be negative for a curmudgeon who
rates most items negatively.
§ Similarly, the variable pj denotes the bias in the ratings of item j.
§ Highly liked items (e.g., a box-office hit) will tend to have larger
(positive) values of pj, whereas globally disliked items will have
negative values of pj.
§ It is the job of the factor model to learn the values of oi and pj in a
data-driven manner.
Baseline predictors and Mean Centering

§ The main change to the original latent factor model is that a part
of the (i,j)th rating is explained by oi + pj and the remainder by
the (i,j)th entry of the product UVT of the latent factor matrices.
§ Therefore, the predicted value of the rating of entry (i,j) is given
by the following:
<

𝑟$
56 = 𝑜5 + 𝑝6 + ' 𝑢5J 7 𝑣6J
J>?
§ And so the error is given by:
<

𝑒56 = 𝑟56 − 𝑟$
56 = 𝑟56 − 𝑜5 − 𝑝6 − ' 𝑢5J 7 𝑣6J
J>?
Baseline predictors and Mean Centering

§ Note that these variables oi and pj also need to be learnt.

§ So our objective function is

N < O <
1 F 𝜆 𝜆
J= ' 𝑒56 + ' ' 𝑢𝑖𝑞 + ' ' 𝑣𝑗𝑞F
F
2 2 J>?
2 J>?
(5,6)∈H 5>? 6>?

? F
= ∑(5,6)∈H 𝑟56 − 𝑜5 − 𝑝6 − (∑<J>? 𝑢𝑖𝑞 ∗ 𝑣𝑗𝑞 )
F
P
+ ∑N
5>? ∑ <
J>? 𝑢 𝑖𝑞
F + ∑O6>? ∑<J>? 𝑣𝑗𝑞 F + ∑N 𝑜
5>? 𝑖
F + ∑O 𝑝 F
6>? 𝑗
F