Fast Context-aware Recommendations
with Factorization Machines
Steffen Rendle
Social Network Analysis
University of Konstanz
78457 Konstanz, Germany

steffen.rendle@uni-konstanz.de

Zeno Gantner, Christoph Freudenthaler,Lars Schmidt-ThiemeInformation Systems and Machine Learning Lab
University of Hildesheim
31141 Hildesheim, Germany{gantner,freudenthaler,schmidtthieme}@ismll.de
ABSTRACT

Keywords

The situation in which a choice is made is an important
information for recommender systems. Context-aware recommenders take this information into account to make predictions. So far, the best performing method for contextaware rating prediction in terms of predictive accuracy isMultiverse Recommendation based on the Tucker tensor factorization model. However this method has two drawbacks:(1) its model complexity is exponential in the number of context variables and polynomial in the size of the factorizationand (2) it only works for categorical context variables. On
the other hand there is a large variety of fast but specializedrecommender methods which lack the generality of contextaware methods.
We propose to apply Factorization Machines (FMs) tomodel contextual information and to provide context-aware
rating predictions. This approach results in fast contextaware recommendations because the model equation of FMs
can be computed in linear time both in the number of context variables and the factorization size. For learning FMs,
we develop an iterative optimization method that analytically finds the least-square solution for one parameter given
the other ones. Finally, we show empirically that our approach outperforms Multiverse Recommendation in prediction quality and runtime.

Context-Aware Recommender System, Factorization Machine,
Rating Prediction, Tensor Factorization

Categories and Subject Descriptors
H.3.3 [Information Systems]: Information Search and Retrieval—Information filtering; I.2.6 [Artificial Intelligence]:
Learning—Parameter Learning

General Terms
Algorithms, Experimentation, Measurement, Performance

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SIGIR’11, July 24–28, 2011, Beijing, China.
Copyright 2011 ACM 978-1-4503-0757-4/11/07 ...$10.00.

1. INTRODUCTION
Rating prediction in recommender systems relies primarily on the information of how (which rating, e.g. on a scalefrom 1 to 5 starts) who (which user) rated what (which item,
e.g. movie, news article, or product). There are many methods that take additional data about the who (demographic
information about the user, age, profession, gender) or thewhat (item attributes like movie genres or keywords fromthe product description) into account.
Besides such data about the entities involved in the rating
events, there is possibly also information about the situationin which the rating event happens, e.g. the current location,
the time, who is nearby, or the current mood of the user.
Such situational information is usually called context. Because it is known from decision psychology that the setting
and the mood of a person do influence their behavior, it
is desirable to exploit context information in recommendersystems. Context-aware rating prediction relies on the information of how who rated what in which context (see also
figure 1).
Classical recommender system methods do not take context information into account. Some approaches perform
pre- or post-processing of the data to make standard methods context-aware. While such ad-hoc solutions may workin practice, they have the shortcoming that all steps in theprocess need supervision and fine-tuning. Methods that integrate all kinds of input data into one model are morepractical in this respect, as well as theoretically more elegant. Currently, the most flexible and strongest approachin terms of prediction accuracy is Multiverse Recommendation [5] that relies on Tucker decomposition and allows to
work with any categorical context. However, for real-world
scenarios its computational complexity is too high as it isin O(km ) where k is the dimensionality of the factorizationand m the number of modes/variables involved.
In this paper, we propose a context-aware rating predictor that is based on Factorization Machines (FM) [14].
FMs include and can mimic the most successful approaches
in recommender systems including matrix factorizion [18],SVD++ [6] or PITF [15]. We show how FMs can be applied
to a wide variety of context domains including categorical,

set categorical or real-valued domains. Besides this flexibility in modeling, the complexity of FMs is linear bothin k and m which allows fast prediction and learning with
context-aware data. For learning the model parameters ofFMs, we propose a new algorithm that is based on alternating least squares (ALS). Our algorithm directly finds the
optimal solution for one model parameter given all the otherones and a joint optimum is found within a few iterations.
Like for stochastic gradient descent (SGD), the complexity
for one iteration of our ALS algorithm is in O(|S| m k) where|S| is the number of training examples. The main advantage
of our new ALS algorithm over SGD is that no learning rate
has to be determined. This is very important in practice,because the quality of SGD learning relies largely on a goodlearning rate and thus an expensive search has to be done.
This is not necessary for ALS.
In our experiments, we show empirically that contextaware FMs can capture context information and improvepredictive accuracy. Furthermore, FMs outperform the stateof-the-art method Multiverse Recommendation both in prediction quality and largely in runtime.
1. In contrast to other context-aware rating predictors,
FMs are easily applicable to a wide variety of contexts.
We show how to generate feature vectors for context
of categorical, set categorical and real-valued domains.
2. We develop a new learning algorithm for FMs that directly computes the least-square solution of a model
parameter given the remaining parameters. The advantage of our ALS algorithm over SGD is that it
works without a learning rate.
3. Compared to the state-of-the-art context-aware rating
prediction method Multiverse Recommendation, FMs
have a linear complexity and empirically provide a better prediction quality in much less time.

2.

CONTEXT-AWARE RATING
PREDICTION

We first describe the standard rating prediction task andthen extend it to context-aware rating prediction. Next weshow how this task can be expressed as a regression task
from real-valued feature vectors under extreme sparsity. We
also discuss shortly why standard regression models are noteffective in this setting.

2.1 Rating prediction
Standard rating prediction can be defined as a regression
task over users U = {u1 , u2 , . . .} and items I = {i1 , i2 , . . .},where a target function y : U × I → R has to be estimated.
The target function represents the rating, e.g. y(u, i) is therating of user u for item i. We denote the observed partof y by S ⊂ U × I; i.e. for all (u, i) ∈ S, we know therating y(u, i) in advance. The task of rating prediction is toestimate a function ŷ that can predict ŷ(u, i) for any useritem combination.

2.2 Context
In context-aware recommender systems, it is assumed thatsome additional information is available that influences therating behavior. We define a context as a variable c ∈ C.
Examples are the mood the user was in when (s)he rated an

item (e.g. C = {happy, sad, . . .}), the time at which a rating
was given (e.g. C = R+ ), the last items seen (e.g. C = P(I))
or the location (e.g. C = R2 ).

2.3 Context-aware rating prediction
If multiple contexts C3 , . . . , Cm are allowed the task is toestimate the following rating function:y : U × I × C3 . . . × Cm → R(1)

Note that we start the index of the context variables with 3
because from a technical point of view, users and items canbe seen as the first and second ‘context’.
Figure 2 shows an example for context-aware data on theleft side. There are users U in mood C3 watching movies I
together with other users C4 :U = {Alice, Bob, Charlie}
I = {TItanic, Notting Hill, Star Wars, Star Trek}
C3 = {Sad, Normal, Happy}
C4 = P(U )The first tuple in Fig. 2 states that Alice rated TItanic with5 stars and that she has watched this movie with Charlie
while she was Happy.

3. RELATED WORK
Most research in recommender systems focus on contextunaware methods that analyze only the user-item interaction. Here matrix factorization approaches (e.g. [18, 6])
have become very popular as they usually outperform traditional k-nearest neighbor methods (e.g. [17]). There isalso research in incooperating meta-data like user or item
attributes into the prediction, like Stern et al. [19] who
extend a matrix factorization model. However meta-dataoften yields in only little or no improvement over strong
baseline methods for rating prediction if enough feedback
data is present [12]. The difference between such user/ item
attributes and context is that attributes are attached only
to either an item or user (e.g. a genre is attached to a movie)
whereas context is attached to the whole rating event (e.g.
the mood of a user when rating an item).
In contrast to the huge literature on standard recommender systems, there is only little research on contextaware recommender systems. The most basic approaches
are contextual pre-filtering and post-filtering where a standard context-unaware recommender system is applied andthe data is either preprocessed based on the context of interest before applying the recommender or the results are
postprocessed [11]. Examples for pre-processing are itemsplitting [3] or the multidimensional model of Adomavicius
et al. [1] which is based on OLAP cubes. More sophisticated approaches use all the context and user-item information simultaneously to make predictions. Oku et al. [9]use SVMs for context-aware predictions – which have limitations in sparse applications like recommender systems as
no 2-way interaction between items and users can be estimated directly [14]. Li et al. [8] suggest to see context
as a user feature which is dynamic, i.e. can change. Thereis also some research on context-aware recommendation systems for item prediction [16], which is a ranking task insteadof a regression task like the problem we are dealing with in
this paper.

3.1 Multiverse Recommendation
Recently, Karatzoglou et al. [5] have proposed to apply
the Tucker decomposition [20] to factorize the tensor overuser, items and all categorical context variables directly.
They called their approach Multiverse Recommendation andhave shown empirically that their approach results in better
prediction accuracy than item-splitting [3] and the OLAP
approach [1]. In our evaluation, we will compare our Factorization Machine approach to Multiverse Recommendation.
As both our approach and Multiverse Recommendation
are based on factorization models, we shortly recapitulate
their approach and highlight the differences. Their model
equation is the Tucker Decomposition, which decomposes anm-mode tensor into a smaller core tensor B and one factor
matrix V(m) per mode. For context-aware recommendersystems, the first mode is the user, the second the item andthe remaining m − 2 modes are the context variables. The
model equation can be written as:ŷ(u, i, c3 , . . . , cm ) :=

k1
X

...

f1

km
X

(U )
(I)
bf1 ,...,fm vu,f1 vi,f2

fm

m
Y

vcCll,fl ,

l=3

with
B ∈ Rk1 ×...×km ,V(U ) ∈ R|U |×k1

V(I) ∈ R|I|×k2 ,V(Cl ) ∈ R|Cl |×kl .

The major drawback
Q of this model is that its computational
complexity is in O( ml=1 kl ). Assuming factorization dimensions of equal size, i.e. k := kl , this means a computational
complexity of O(km ). Thus the complexity of computing
one context-aware rating is exponential in the number ofmodes and polynomial in the number of factors. This leads
to both poor learning and poor prediction runtime as soon
as the number of factors growths. In Figure 5 we compare
the learning runtime of Multiverse Recommendation empirically to our FM approach. A second limitation of Multiverse
Recommendation in comparison to our approach is that only
categorical context can be modeled – e.g. categorical set
variables or real-valued variables are not possible. Finally,in the related task of item or tag recommendation (which
is a ranking task), it has been shown that often it is betterto factorize several lower variable interactions (e.g. pairwise
ones [15]) instead of one m-ary relation (like the Tucker Decomposition). The reason is that under high sparsity, factorized pairwise relations can be estimated well but factorized
m-ary relations are harder to estimate. Our FM approach
follows this idea and models all nested interactions up to
pairwise ones.

3.2 Attribute-aware Recommendation
In contrast to the little work on general context-aware
methods, there is much more research on attribute-aware or
specialized recommender systems. For example [19] or [2]present extensions of the matrix factorization model that
can handle user and item attributes. There are also several works on taking time-effects into account, e.g. [7, 21].
However, all of these approaches are designed only for specific problems and cannot handle the general problem settingof context-aware recommendation that we examine in thiswork. For sure for specific and important problems (e.g.
time-aware or attribute-aware recommendation) it is beneficial to investigate specialized methods that are supposed

Figure 1: Attribute-aware methods can take additional information about the user or the item separately into account (left), whereas context-aware
methods are more general and can analyze data thatis simultaneously attached to all ‘modes’, i.e. thewhole rating event (right).

to be the best models for a certain problem, but on theother hand also research on general methods like contextaware recommenders is important as they offer the largest
flexibility and may serve as (strong) baselines for specialized
models.

3.3 Alternating Least Square Optimization
For the model class of matrix factorization, Bell and Koren[4] proposed an ALS method that alternates between optimizing all user factors and all item factors. As the whole
factor matrix of all users (resp. items) is optimized jointly,
the computation complexity is O(k3 ). This complexity issue of standard ALS is the reason why SGD approaches are
more popular in the recommender system literature than
ALS. Pilászy et al. [13] have proposed to optimize the factors within each user (resp. item) one after the other which
results in an ALS algorithm constant in k, i.e. O(k) because
the matrix inversion is avoided. The general idea of optimizing one factor at a time is the same idea that we apply for
our ALS algorithm for FMs. Both approaches [4, 13] work
only for matrix factorizations and thus cannot handle any
context like our proposed FMs which model all interactions.
Furthermore our ALS algorithm also learns the global bias
and basic 1-way effects.

4. CONTEXT-AWARE RATING
PREDICTION WITH FMS
FMs are a generic model class that subsumes and can
mimic several of the most successful recommender systems,
among them matrix factorization [18], SVD++ [6] or PITF
[15]. We shortly recapitulate the FM model and then show
in detail how it can be applied to context-aware data andwhat happens inside an FM using such context-aware data.
In the second main part, we propose a new fast alternating
least square (ALS) optimization algorithm that makes FMmuch easier applicable compared to SGD algorithms because
it works without any learning rate.

4.1 Rating Prediction with FMs
A factorization machine (FM) [14] models all interactions
between pairs of variables with the target, including nested

ones, by using factorized interaction parameters1 :ŷ(x) := w0 +nX

wi x i +

i=1

n
n
X
X

ŵi,j xi xj(2)

i=1 j=i+1

where ŵi,j are the factorized interaction parameters between
pairs:
ŵi,j := hvi , vj i =kXvi,f · vj,f

(3)

f =1

and the model parameters Θ that have to be estimated are:w0 ∈ R,

n

w∈R ,

V∈R

n×k

(4)

That means w0 is the global bias, wi models the interactionof the i-th variable to the target and ŵi,j models the factorized interaction of a pair of variables with the target. Notealso that unlike other factorization models like matrix factorization or PARAFAC, FMs can work with any continuous
input data x.
In [14] it has also been shown that a FM (eq. 2) can becomputed very efficiently in O(k · m(x)) as it is equivalent
to:
!2
!
k
n
n
n
X
X
X
1X
2
2
ŷ(x) = w0 +−vi,f xi
wi x i +vi,f xi
2 f =1
i=1
i=1
i=1
(5)

For the task of regression, the most widely used loss function is square loss. To prevent overfitting it is common to
add a regularization term – usually L2. In total, we use thefollowing regularized least square criterion for optimization:XX
λ(θ) θ2(6)(ŷ(x) − y)2 +RLS-Opt =(x,y)∈S• Real valued domains: If a domain is already a number (e.g. C ⊆ R), we can directly use the real number
as feature, e.g. z(3.141) = 3.141.
The final feature vector x can be obtained by concatenating
the single mappings:
x(u, i, c3 , . . . , cm ) = (z1 (u), z2 (i), z3 (c3 ), . . . , zm (cm )) (7)This data vectors x are then the input for the FM (eq. 2).

Example.
Figure 2 shows a complete example how to transform thecontext-aware data of section 2.3 into a prediction problem
from real-valued features. The example contains the categorical domains user U , item I and mood C3 as well as a setcategorical domain, the friends the movie has been watched
with, C4 . To get an insight of how an FM will work, weinvestigate shortly the model equation of an FM applied tothis data2 . When we look at the feature vector x of our
example, one can see that most of them are 0 and thus the
FM model equation can be rewritten as:ŷ(x(u, i, c3 , c4 )) = w0 + wi + wu + wc3 +4.2 Context-aware FMs
A wide variety of context-aware data can be transformed
into such a prediction task using real valued feature vectors
x ∈ Rn (see figure 2, right side for an example). We willshow possible mappings z : C → Rnz for different kind of
domains:• Categorical domain: A categorical variable domain
C like users U , items I, or mood can be transformed
into a real-valued vector z using one indicator variable
per categorical level. E.g. in our example the mooddomain C3 has three states, so we can express Alice’s
mood Happy with the vector z(Happy) = (0, 0, 1), or
if she is in a Sad context with: z(Sad) = (1, 0, 0).
• Categorical set domain: if the realization of a variable can be sets of categorical variables (e.g. Alicehas watched Star Wars with Bob and Charlie), theWe restrict our discussion to 2-way FMs (d = 2).

X

x t wtt∈c4+ hvi , vu i + hvi , vc3 i + hvi ,X

x t vt i

t∈c4

θ∈Θ

where λ(θ) is a regularization (hyper-)parameter for the model
parameter θ. In general, the regularization term can be chosen individually for each model parameter. But in practice
it makes sense to use the same regularization parameters
for similar model parameters – in our experiments we use:λ(w0 ) = 0 as there is no need to regularize the global bias;
the same λ(w) for all parameters wi ∈ w and the same λ(V)for all parameters vi,f ∈ V.

1

transformation can be made by using one indicatorvariable per context level. E.g. z({Bob, Charlie}) =(0, 0.5, 0.5); here we suggest to normalized z for nonempty context values such that all vectors sum up to 1.
This makes sure that all vectors have the same weight
which is often desirable.

+ hvu , vc3 i + hvu ,

X

t∈c4

xt vt i + hvc3 ,X

x t vt it∈c4

That means the FM model contains the bias term for theindividual item i, user u, mood c3 and the average bias of
the co-watchers c4 . Furthermore it factorizes all pairwise interactions between these four variables. Comparing the FMmodel with the standard matrix factorization model (e.g.
[18]) for the user u and the item i, one can see that the FM
contains also exactly this factorization: hvi , vu i. Additionally, it factorizes all pairwise interactions with all context
variables. This shows how FMs automatically include oneof the best performing recommender system models, the matrix factorization model.

4.3 Fast Learning
As the model equation of FMs can be calculated in linear
time (see eq. 5), it is straightforward to develop a stochastic
gradient descend (SGD) optimization algorithm for a variety of loss functions. However SGD requires to find a goodlearning rate which is big enough to have convergence aftera reasonable amount of iterations and small enough that thegradient steps are made towards the minimum which is especially important in latter iteration stages. In the following,2
Please note that we do this analysis only to explain what
happens implicitly in the FM – nothing has to be done explicitly when applying an FM. The end-user (domain expert)
has only to specify the input features (i.e. the x vector) andrun a generic FM tool with this data.

Figure 2: Context-aware recommendation data (left side) is transformed into a prediction problem from realvalued features (right side) by encoding the categorical and set categorical variables (left side) with indicatorvariables (right side). Here in the feature vector x, the first three values indicate the user, the next four ones
the movie, the next three ones the mood and the last three ones the other users a movie has been watchedwith.
we suggest a new alternating least square (ALS) learning algorithm that finds the optimal value for a model parameter
given the remaining ones.

4.3.1 Alternating Least Square
The analytical least-square solution for a model parametercan be found for FMs because they are linear functions (ineach model parameter) and there is an analytic solution forevery linear function. We will show this in the following twolemmas.
Lemma 1 (Linearity in θ ). A FM is a linear function with respect to every single model parameter θ ∈ Θ andthus can be reexpressed as:ŷ(x|θ) = g(θ) (x) + θ h(θ) (x)(8)
3where g(θ) and h(θ) are independent of the value of the parameter θ.
Proof. We proof this by stating g and h explicitly forthe model parameters. For the global bias w0 , the FM canbe rewritten as:ŷ(x|w0 ) = w0

+
1
|{z}

h(w ) (x)0for wl :ŷ(x|wl ) = wl

n
X
i=1

|

wi x i +nnXXg(w ) (x)0h(vzŷ(x|vl,f ) := vl,f xl+ w0 +nX

wi x i +

l,f )

(x)

X}|

{
vi,f xi

i=1,i6=ln
XnX

i=1 j=i+1

i=1

|

g(v

k
X

vi,f ′ vj,f ′ xi xj

f ′ =1(f ′ 6=f )∨(l6∈{i,j})

{z

l,f )

}

(x)

Remark 1. For linear decomposable functions like ŷ of aFM, the function h(θ) (x) is the gradient of ŷ with respect toθ:h(θ) (x) =∂ŷ(x|θ)∂θ

(9)Differentiating ŷ leads directly to this result.

ŵi,j xi xj

i=1 j=i+1{z

And for the factorized 2-way interactions vl,f :

}

n
n
n
X
X
X
wi x i +ŵi,j xi xj
x l + w0 +|{z}
i=1 j=i+1
i=1,i6=lh(w ) (x){z}|lg(w ) (x)l3
The functions g and h are indexed with the name of theparameter θ because their form depends on the variable θ(e.g. is different for w0 and wl ) but it does not depend on
the value of θ.

Lemma 2 (Optimal value for θ ). The regularized leastsquare solution of a single parameter θ for a linear modelŷ(x|θ) is:θ=−P(x,y)∈SP
g(θ) (x) − y h(θ) (x)2(x,y)∈S h(θ) (x) + λ(θ)(10)

Proof. To gain the regularized least-square solution analytically, the first derivative of the optimization criterion(eq. 6) w.r.t. θ has to be found:∂
RLS-Opt =∂θX(x,y)∈S

2 (ŷ(x) − y) h(θ) (x) + 2 λ(θ) θThe minimum is where this derivative is 0:X
2 (ŷ(x) − y) h(θ) (x) + 2 λ(θ) θ = 0(x,y)∈S⇔X(x,y)∈S⇔θ = −Xθ h2(θ) (x) + λ(θ) θ = 0
g(θ) (x) − y h(θ) (x) +(x,y)∈SP(x,y)∈SP
g(θ) (x) − y h(θ) (x)2(x,y)∈S h(θ) (x) + λ(θ)

4.3.2 Learning Algorithm
Lemma 2 with the gradients h(θ) (see remark 1 and eq.
(10)) allows to analytically find the optimal value of eachmodel parameter θ of the FM given the remaining model
parameters. A joint optimum of all model parameters Θ
can be found iteratively by calculating the optimum of eachmodel parameter one after another and repeating this several times. In figure 3 such an algorithm is sketched – themeaning and purpose of e and q will be explained later.
First the model parameters are initialized, where the 0- and1-way interactions (w0 and wl ) can be initialized with 0 andthe factorization parameters with small 0-centered random
values. In the main loop the parameters are optimized one
after the other. The idea here is to optimize first lower interactions and then higher ones because for lower interactions
more data is observed and thus their estimates are morereliable. Within the factors of the 2-way interactions, first
all features of the first factor dimension are optimized, thenthe features of the second factor dimension, etc. This allows
the f -th factor to find the residuals for the 1st to (f − 1)thfactor dimensions. This optimization main loop us repeatedseveral times to converge to the joint optimum of all model
parameters.

4.3.3 Fast Calculation
Straightforward computation of the optimum for each parameter with eq. (10) would mean to calculate g and h foreach training example and in each parameter update. Now,
we show how to calculate the values efficiently for FMs. This
involves three improvements: (1) precomputing error terms,(2) precomputing h-terms for 2-way interactions and (3) using the sparsity in S. In total, this will lead to an update
algorithm where a full iteration over all parameters is in
O(|S| mS k) – i.e. linear in the number of non-zero elementsin the whole dataset and the number of factors.

1: procedure LearnALS(S)2:w0 ← 0⊲ Initialize the model parameters3:w ← (0, . . . , 0)
4:V ∼ N (0, σ)
5:for (x, y) ∈ S do
⊲ Precompute e and q6:e(x, y|Θ) ← ŷ(x, y) − y7:
for f ∈ {1, . . . , k}P do
8:q(x, f |Θ) ← n
i=1 vi,f xi
9:
end for10:
end for11:
repeat⊲ Main optimization loopP(e(x,y|Θ)−w0 )12:w0∗ ← − (x,y)∈S⊲ global bias
|S|+λ
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

(w0 )

e(x, y|Θ∗ ) ← e(x, y|Θ) + (w0∗ − w0 )w0 ← w0∗
for l ∈ {1, .P. . , n} do⊲ 1-way interactions
wl ← −(x,y)∈S (e(x,y|Θ)−wl xl )xlP2(x,y)∈S xl +λ(wl )e(x, y|Θ∗ ) ← e(x, y|Θ) + (wl∗ − wl ) xl
wl ← wl∗end forfor f ∈ {1, . . . , k} do⊲ 2-way interactions
for l ∈ {1, . . . , n} do


∗ ← −
vl,f

P
(x,y)∈S e(x,y|Θ)−vl,f h(vl,f ) (x) h(vl,f ) (x)P2(x)+λ(v(x,y)∈S h(v
l,f )
l,f )

∗
23:
e(x, y|Θ∗ ) ← e(x, y|Θ) + (vl,f− vl,f ) xl∗∗
24:q(x, f |Θ ) ← q(x, f |Θ) + (vl,f− vl,f ) xl∗
25:
vl,f ← vl,f
26:
end for27:
end for28:
until stopping criterion is met
29:
return w0 , w, V
30: end procedure

Figure 3: Alternating least algorithm that optimizes
the model parameters w0 , w and V for least-squarein O(|S| m|S| k) time (see section 4.3.3) where |S| are
the number of training examples and m|S| the average number of non-zero elements in an input vectorx.

Which can be used in the nominator of eq. (10). We store
the error in a vector e ∈ R|S| over all training examples andprecompute it at the beginning. After changing the valueof a model parameter from θ to θ∗ , the error also changes.
This change on the error can be computed analytically by:Precomputing error terms.
The first bottleneck in updating the parameter θ witheq. (10) is calculating (g(θ) (x) − y) for each training case(x, y) ∈ S. Obviously, a trivial computation of this is inO(m(x) k).
Now we will show, how to compute this in constant timeO(1) if the error is known. Lets define for each training case,the error4 e(x, y|Θ) of the model given the model parameteras:e(x, y|Θ) := ŷ(x|Θ) − y(11)This allows to rewrite:g(θ) (x) − y = e(x, y|Θ) − θ h(θ) (x)(12)

4Actually, e is not the error, but e2 is. Nevertheless, we use
the term error for convenience.

e(x, y|Θ∗ ) = e(x, y|Θ) + (θ∗ − θ) h(θ) (x)(13)

where Θ∗ is the set of all model parameters where only thevalue of θ has changed to θ∗ .

Precomputing h-terms.
After storing error terms, the computation complexity
only depends on the complexity of the h(θ) -functions. For
the parameters w0 and wi , the complexity of h(θ) is constant, thus also computing the terms within the sums of thenominator and denominator as well as the error update isin constant time. But for the factorized parameters, computing h contains a loop over all variables. We will show
now how to compute this in constant time. First, we canreformulate h(vl,f ) as:h(vl,f ) (x) = xlnXvi,f xi − x2l vl,fi=1

= xl q(x, f |Θ) − x2l vl,f

(14)
(15)

with
q(x, f |Θ) :=nXvi,f xi(16)

i=1

if (s)he imagines to be hungry or (s)he really is) and thesecond one how hungry the user is. The Adom. dataset
contains 1524 rating events (1 to 15 stars) for movies withfive context variables about companion, the weekday andother time information. For the Yahoo! Webscope dataset(221367 rating events) we follow [5] and apply their method
to generate datasets with an increasing number of dependency of the target on the context – we generate 9 datasetsfor α = β ∈ {0.1, . . . , 0.9}.

Methods. We compare context-aware FMs to Multiverse

Again Θ∗ are the new parameters after the value of vl,f∗changed to vl,f
, while the rest of the parameters keep unchanged.

Recommendation. Note that Multiverse Recommendation
has been shown to outperform other context-aware recommender systems on the Yahoo! webscope, Food and Adom.
dataset [5]. As context-unaware baseline we use FMs (FM(nocontext)) where only the user and item variables are usedgenerating the feature vectors which is equivalent to matrix
factorization with bias terms (see [14] for a proof) which
is one of the strongest context-unaware recommender algorithms. All models are optimized for regularized leastsquares (eq. 6). The FMs are optimized with our proposed
ALS algorithm. Multiverse Recommendation is learned withan SGD algorithm similar to the one proposed in [5].

Sparsity in S .

Protocol. We remove a 5% sample from each dataset which

This term q is independent of l and can be precomputedfor each training case and factor in a matrix Q ∈ R|S|×k .
With a precomputation of the q-terms, the h-function can becomputed in constant time with eq. (14). When updating a∗parameter vl,f to vl,f, we have to update the corresponding
q-term as well. This can be done in constant time with:∗
q(x, f |Θ∗ ) = q(x, f |Θ) + (vl,f− vl,f ) xl

(17)

With the two enhancements described so far, the computation of each term within the sums of the nominator anddenominator of the update rules eq. (10) can be calculated
in constant time. Now, we investigate the overall complexity.
First, for the w0 parameter, the optimization complexity is
O(|S|). Secondly, for each update (eq. (10)) of the 1- and 2way interactions of the l-th parameter, one has to loop only
over training examples where h is nonzero – these are thetraining examples where xl 6= 0. Thus the complexity for
updating a 1-way or 2-way parameter is in O(ml )5 . In total
there are n 1-way and n k 2-way parameters, so the complexity for one whole iteration (i.e. updating all parameters) isO(ml n k) = O(|S| m|S| k).

5.

EVALUATIONIn this section, we empirically investigate if the greatermodel flexibility and better runtime of FMs comes to theprice of less prediction quality compared to the state-ofthe-art context-aware method Multiverse Recommendation.
Furthermore we want to examine the sensitivity of SGD tothe choice of the learning rate and if our ALS optimization
can successfully work without this hyperparameter.

5.1 Methodology
Datasets. Even though the problem of context-aware rating prediction is highly relevant in practice, there are only
a few publicly available datasets: the Food dataset [10], theAdom. dataset [1] as well as the Yahoo! Webscope dataset6enriched with context-aware information by [5]. The Fooddataset contains 6360 ratings (1 to 5 stars) by 212 users
for 20 menu items where one context variable captures if
the situation in which the user rates is virtual or real (i.e.
5Remind that ml is the number of training cases in S wherexl 6= 0 which is usually low in our sparse setting
6
http://research.yahoo.com/Academic_Relations
ydata-ymovies-user-movie-ratings-content-v1 0

is used as validation set for tuning the hyperparameters for
optimal MAE. After hyperparameter search, we make a 5fold cross validation on the remaining 95% of the dataset –i.e. the validation set for hyperparameter tuning is not used
any more. We report the mean RMSE and MAE over the
5 experiments. All methods are implemented in C++ andwere run on the same hardware.

Experimental Reproducibility. Our FM implementation
with ALS optimization, a Multiverse Recommendation implementation and the dataset generation scripts can be downloaded from our website7 .

5.2 Results
5.2.1 ALS vs. SGD Learning
In figure 4, we compare the test error of an SGD implementation to our ALS-approach on the Webscope dataset8 .
The leftmost figure shows the prediction quality on the test
set after each iteration. The two plots on the right side show
the minimal RMS error on the test set for several learning
rates after 10 and 100 iterations. One can see that the prediction quality of SGD depends largely on the learning rate
and the number of iterations that is chosen. If the SGD
learning rate is chosen too large (e.g., here 0.01), the qualityof ALS cannot be reached. With a small learning rate one
can reach the quality of ALS – provided that the number of
iterations is large enough (see rightmost graphs) and thatone stops learning near the minimum (see leftmost graph)on a validation set to prevent overfitting.
This experiment shows that SGD needs a careful and timeconsuming search for the learning rate. In contrast to this,
ALS requires no such search because it does not have this7

http://www.libfm.org/
The model is a context-aware FM with k = 64; the regularization parameters have been tuned individually for eachlearning method.
8

Training: 10 Iterations

Training: 100 Iterations

0

10

20

30

40

Learning time in seconds

50

60

1.6

ALS
SGD

1.4
1.3
1.2
1.1
1.0

1.1

1.2

1.3

1.4

Minimal Test Error (RMSE)

1.5

ALS
SGD

1.0

Minimal Test Error (RMSE)

1.00
0.95

Test Error (RMSE)

1.05

ALS
SGD (learn rate 0.01)
SGD (learn rate 0.005)
SGD (learn rate 0.002)

1.5

1.6

Yahoo! Webscope dataset

1e−05

1e−03

1e−01

1e−05

1e−03

learning rate (for SGD)

1e−01

learning rate (for SGD)

Figure 4: On the left side test error curves are plotted for three choices of learning rates. The two plots on
the right show the best RMSE found after 10 and 100 iterations respectively for several choices of learning
rates. This shows that for applying typical stochastic gradient descent (SGD) algorithms an appropriate
learning rate has to be found. Usually an expensive search over hyperparameters is performed. Our ALS
algorithm works without such a hyperparameter.
hyperparameter. With regard to prediction quality, SGD
can perform as good as ALS but only with the right choiceof the learning rate. This makes ALS clearly favorable inapplication.

Food data
2.20

Adom. data

5.2.3 Prediction Quality
Finally, we want to investigate if the flexibility and fast
runtime of context-aware FMs comes to the price of poor
prediction quality compared to the Multiverse Recommendation method. Therefore we compare the prediction quality on the Food, Adom and Webscope dataset9 . Figure 6
9
For the Adom. dataset our implementation of Multiverse Recommendation performed much worse than reported
in [5]. Thus in favor of Multiverse Recommendation we report their (better) MAE value.

Error

2.10
2.05

0.9

2.00

0.8

One of the main disadvantages of Multiverse Recommendation for practical use is that the computation complexityof the model is in O(km ) which is an issue for both learningand prediction. That means even for standard non-contextaware recommender systems, the runtime is quadratic in thedimensionality of the factorization k and for context-aware
problems at least cubic. This makes it hard to apply forlarger number of factors k. In contrast to this, the computational complexity of factorization machines is linear inboth k and m: O(k m).
In this experiment, we compare the runtime for one fulliteration over all training examples of Multiverse Recommendation to context-aware FMs. As dataset, we used Yahoo! Webscope with m = 4. To show the polynomial
growth of the runtime with an increasing number of thedimensionality factorization, we run both models with k ∈{1, 2, 4, 8, 16, 32, 64, 128} – for Multiverse Recommendation
the maximal k we use was 32. In figure 5, the results arereported. These empirical results match to the theoreticalcomplexity analysis. The runtime of the FM is linear and
one full iteration over all training examples can be madefor example in about 11 seconds (for k = 128) whereas thecomplexity of Multiverse Recommendation growths with k4
such that the runtime for k = 16 is already 30 minutes andfor k = 32 about 8 hours.

0.7

5.2.2 Runtime

Error

1.0

2.15

1.1

FM (no context)
Fact. Machine
Multiverse Rec.

RMSE

MAE

MAE

Figure 6: The context-aware methods Multiverse
Recommendation [5] and our proposed contextaware Factorization Machine benefit from incooperating the context-information into the rating prediction.
shows that context-aware FMs and Multiverse Recommendation have comparable prediction quality for the Food andAdom. datasets. Furthermore, both methods outperformthe context-unaware method (here equivalent to a matrix
factorization model).
In a third experiment, we investigate the artificially enriched Yahoo! Webscope dataset (see [5]) with an increasing
influence of context variables on the rating. Figure 7 showsthat both context-aware FM and Multiverse Recommendation benefit from ratings that have a stronger dependence
on the context. In contrast to this, the prediction qualityof context-unaware FM gets worse when the rating depends
stronger on the context because for context-unaware FMs
the context is unobserved and thus they cannot explain thisdependency.
Comparing both context-aware methods among each other,
one can see that FMs throughout generate much better predictions than Multiverse Recommendation. E.g. for RMSE
the difference is about 0.10 to 0.15 points whereas for MAE
it is about 0.08 to 0.10 points. This matches to results fromthe related area of tag recommendation, where a pairwiseinteraction model (PITF) outperforms the Tucker decomposition empirically in sparse problems [15]. Note that theYahoo! Webscope dataset

1

2

5

10

20

50

100

k (dimensionality)

25000
20000
15000
10000
5000

Learning runtime per iteration (in seconds)
Factorization Machine
Multiverse Recommendation

Factorization Machine
Multiverse Recommendation

0

1e+03
1e+01
1e−01

Learning runtime per iteration (in seconds)

30000

Yahoo! Webscope dataset

0

20

40

60

80

100

120

k (dimensionality)

Figure 5: Learning runtime in seconds for one iteration over the whole training dataset (the left side is in
log-log scale). The runtime of the Factorization Machine is linear in the number of latent factors k whereas forMultiverse Recommendation [5] it is polynomial (here O(k4 )). E.g. for a factorization size of k = 16 (k = 32),
one iteration with the FM takes only 1.1 second (2.2 seconds), whereas for Multiverse Recommendation it
takes about 30 minutes (8 hours).
Multiverse Recommendation model is the Tucker decomposition and the FM includes all possible pairwise interactions(like PITF).

applied in many different scenarios and high prediction accuracy due to factorized interactions with fast and scalable
computation due to the linear model complexity.

5.2.4 Summary

7. ACKNOWLEDGMENTS

Our experiments have shown that context-aware FMs areable to take contextual information into account to enhance
predictions like the state-of-the-art method Multiverse Recommendation. In terms of runtime, FMs are linear whichmakes them applicable to a large dimensionality of factors,
many context-variables and many observations. In contrast
to this Multiverse Recommendation cannot handle a large
number of factorization dimensions or modes. The advantage in terms of runtime is not traded in for prediction quality. Instead, on the dense datasets (Food and Adom.) the
prediction quality of both methods is comparable whereas
FMs outperform Multiverse Recommendation largely in sparsesettings (Yahoo! Webscope). Finally, ALS optimized FMs
are easily applicable as they do not require an expensive
search for the learning rate like SGD optimized FMs or Multiverse Recommendation.

We would like to thank Hideki Asoh, Gediminas Adomavicius and Alexander Tuzhilin for sharing their data sets.

6.

CONCLUSION

In this paper, we have shown how to apply factorization
machines to the task of context-aware recommender systems. FMs are easily applicable to a wide variety of context by specifying only the input data. This allows themto solve scenarios where standard tensor factorization approaches cannot be applied (e.g. categorical set domains,real-valued domains). We have developed a new learningalgorithm for FMs that analytically solves the least-square
problem for each model parameter independently. This isespecially helpful in practice as no learning rate has to be
specified like in SGD approaches. Compared to Multiverse
Recommendation which is the best-performing method forcontext-aware rating prediction so far, our approach achievesmuch faster runtime both in training and prediction (O(k m)instead of O(km )) as well as a better prediction quality. Tosummarize, context-aware FMs combine the flexibility to be

8. REFERENCES[1] G. Adomavicius, R. Sankaranarayanan, S. Sen, and
A. Tuzhilin. Incorporating contextual information inrecommender systems using a multidimensional
approach. ACM Transactions on Information Systems,
23(1):103–145, 2005.
[2] D. Agarwal and B.-C. Chen. Regression-based latent
factor models. In KDD ’09: Proceedings of the 15th
ACM SIGKDD international conference on Knowledge
discovery and data mining, pages 19–28, New York,NY, USA, 2009. ACM.
[3] L. Baltrunas and F. Ricci. Context-based splitting of
item ratings in collaborative filtering. In RecSys ’09:
Proceedings of the third ACM conference on
Recommender systems, pages 245–248, New York, NY,
USA, 2009. ACM.
[4] R. M. Bell and Y. Koren. Scalable collaborative
filtering with jointly derived neighborhoodinterpolation weights. In Proceedings of the 7th IEEE
International Conference on Data Mining (ICDM
2007), October 28-31, 2007, Omaha, Nebraska, USA,pages 43–52. IEEE Computer Society, 2007.
[5] A. Karatzoglou, X. Amatriain, L. Baltrunas, and
N. Oliver. Multiverse recommendation: n-dimensional
tensor factorization for context-aware collaborative
filtering. In RecSys ’10: Proceedings of the fourth
ACM conference on Recommender systems, pages
79–86, New York, NY, USA, 2010. ACM.
[6] Y. Koren. Factorization meets the neighborhood: amultifaceted collaborative filtering model. In KDD ’08:
Proceeding of the 14th ACM SIGKDD international

Yahoo! Webscope dataset

0.75

Error (MAE)

0.65

0.70

1.00
0.95

Factorization Machine
Factorization Machine (no context)
Multiverse Recommendation
0.2

0.4

0.6

0.60

0.85

0.90

Error (RMSE)

1.05

0.80

1.10

0.85

1.15

Yahoo! Webscope dataset

0.8

context influence

Factorization Machine
Factorization Machine (no context)
Multiverse Recommendation
0.2

0.4

0.6

0.8

context influence

Figure 7: Prediction error with an increasing influence of the context on the rating. Context-aware FMs
largely outperform Multiverse Recommendation [5] in quality. Secondly, context-aware FMs profit from anincreasing influence of the context on the rating whereas non-contextaware FMs suffer from having no data(context) to explain the shift in the ratings.
conference on Knowledge discovery and data mining,
pages 426–434, New York, NY, USA, 2008. ACM.
[7] Y. Koren. Collaborative filtering with temporal
dynamics. In KDD ’09: Proceedings of the 15th ACM
SIGKDD international conference on Knowledge
discovery and data mining, pages 447–456, New York,NY, USA, 2009. ACM.
[8] Y. Li, J. Nie, Y. Zhang, B. Wang, B. Yan, and
F. Weng. Contextual recommendation based on text
mining. In Proceedings of the 23rd International
Conference on Computational Linguistics: Posters,
COLING ’10, pages 692–700, Stroudsburg, PA, USA,2010. Association for Computational Linguistics.
[9] K. Oku, S. Nakajima, J. Miyazaki, and S. Uemura.
Context-aware svm for context-dependent information
recommendation. In MDM ’06: Proceedings of the 7thInternational Conference on Mobile DataManagement, page 109, Washington, DC, USA, 2006.
IEEE Computer Society.
[10] C. Ono, Y. Takishima, Y. Motomura, and H. Asoh.
Context-aware preference model based on a study ofdifference between real and supposed situation data.
In UMAP ’09: Proceedings of the 17th International
Conference on User Modeling, Adaptation, andPersonalization, pages 102–113, Berlin, Heidelberg,
2009. Springer-Verlag.
[11] U. Panniello, A. Tuzhilin, M. Gorgoglione,
C. Palmisano, and A. Pedone. Experimental
comparison of pre- vs. post-filtering approaches incontext-aware recommender systems. In RecSys ’09:
Proceedings of the third ACM conference on
Recommender systems, pages 265–268, New York, NY,
USA, 2009. ACM.
[12] I. Pilászy and D. Tikk. Recommending new movies:
even a few ratings are more valuable than metadata.
In RecSys ’09: Proceedings of the third ACM
conference on Recommender systems, pages 93–100,
New York, NY, USA, 2009. ACM.
[13] I. Pilászy, D. Zibriczky, and D. Tikk. Fast als-based
matrix factorization for explicit and implicit feedback

datasets. In RecSys ’10: Proceedings of the fourth
ACM conference on Recommender systems, pages
71–78, New York, NY, USA, 2010. ACM.
[14] S. Rendle. Factorization machines. In Proceedings ofthe 10th IEEE International Conference on Data
Mining. IEEE Computer Society, 2010.
[15] S. Rendle and L. Schmidt-Thieme. Pairwiseinteraction tensor factorization for personalized tag
recommendation. In WSDM ’10: Proceedings of thethird ACM international conference on Web searchand data mining, pages 81–90, New York, NY, USA,2010. ACM.
[16] A. Said, S. Berkovsky, and E. W. De Luca. Putting
things in context: Challenge on context-aware movie
recommendation. In CAMRa2010: Proceedings of the
RecSys ’10 Challenge on Context-aware Movie
Recommendation, New York, NY, USA, 2010. ACM.
[17] B. Sarwar, G. Karypis, J. Konstan, and J. Reidl.
Item-based collaborative filtering recommendation
algorithms. In Proceedings of the 10th international
conference on World Wide Web, pages 285–295, New
York, NY, USA, 2001. ACM Press.
[18] N. Srebro, J. D. M. Rennie, and T. S. Jaakola.
Maximum-margin matrix factorization. In Advances in
Neural Information Processing Systems 17, pages
1329–1336. MIT Press, 2005.
[19] D. H. Stern, R. Herbrich, and T. Graepel. Matchbox:
large scale online bayesian recommendations. In
Proceedings of the 18th international conference on
World wide web, WWW ’09, pages 111–120, New
York, NY, USA, 2009. ACM.
[20] L. Tucker. Some mathematical notes on three-mode
factor analysis. Psychometrika, 31:279–311, 1966.
[21] L. Xiong, X. Chen, T.-K. Huang, J. Schneider, andJ. G. Carbonell. Temporal collaborative filtering withbayesian probabilistic tensor factorization. In
Proceedings of the SIAM International Conference on
Data Mining (SDM 2010), pages 211–222. SIAM,
2010.