Research in context-aware recommender systems (CARS) usually requires the identification of the influential contextual variables in advance. In collaborative recommendation, there is a substantial trade-off between applying context very strictly and achieving good coverage and accuracy. Our prior work showed that this tradeoff can be managed by applying the contexts differentially in different components of the recommendation algorithm. In this paper, we extend our previous model and show that our differential context relaxation (DCR) model can also be used to identify demographic and item features that are linked to the contexts. We also demonstrate the application of binary particle swarm optimization as a scalable optimization technique for deriving the optimal relaxation.
Context-aware recommender systems (CARS) extends the focus of recommender systems research beyond users and items to the contexts in which items are experienced by users, attempting to model the interactions that are often influential in making good recommendations. For example, Alice may prefer causal restaurants with spicy Thai food when dining with friends, but would rather choose a quiet but upscale Italian place when entertaining work colleagues. Clearly, the occasion (work vs. personal life) and the companions (friends vs. co-workers) play a key factor in what a system should recommend. The recognition of the importance of such contextual factors is a starting point for much CARS research.
What we see in this example, however, is that these contextual factors (occasion, companions) are linked to specific features associated with the restaurant itself: the type of food, the atmosphere, perhaps the price. To the extent that such linkages are shared among many users, we call these context-linked features. When contextual information is limited, we may be able to observe context-linked features more readily, and so discovering influential context-linked features is an important goal for CARS research.
In our previous research [
In this paper, we show that context-linked features are also good
candidates for our relaxation technique. Previously, we used a data
set with only a handful of contextual variables so it was possible to
do an exhaustive search of all possible relaxations in order to find
the optimum. In this work, we show that binary particle swarm
optimization (BPSO) [
CARS researchers have sought different means of discovering
influential contextual variables. Baltrunas et al [
Comparing with explicit contextual approaches above, there are
also approaches incorporating latent factors: previously we
applied labeled-LDA to infer contexts based on review mining[
Rather than seeking to define a set of contextual variables to be
applied to the algorithm as a whole, our previous work [
We take as our starting point the well-known Resnick’s algorithm for collaborative recommendation:
Pa;i = ra + u2N
P (ru;i ru)
sim(a; u) P sim(a; u) u2N (1) where a is a user, i is an item, and N is a neighborhood of other users u similar to a. The algorithm calculates Pa;i, which is the predicted rating that user a is expected to assign to item i.
The algorithm can be understood as operating over the rating data in three different ways. ra averages over all of the ratings supplied by user a to establish an overall baseline for the target user. The formation of the neighborhood N requires selecting all users for their similarity to a. And, finally, ru is computed for each user u to establish their baseline rating to be subtracted from their individual rating of item i.
Contextual effects may enter into the algorithm in various ways. Perhaps a user has a different baseline rating in different contexts. For example, Alice, our hypothetical diner, may have relatively low expectations for her casual Thai restaurants and give a lot of high scores but give out relatively few five star ratings for her workoriented experiences. Perhaps good collaborative peer groups are context-specific – recommendations from expense-account-wielding business types might be good for her work dinners but not for anything else.
To account for this kind of variance, we start with the target context C, which is the context for which the recommendation is sought. Our prediction now is for target user a, item i, and context C: how will the user respond to this item in this context? For example, how will Alice like a fancy regional American restaurant in the “work” context with Betsy, her boss and Carl, an out-of-town client? It is unlikely that other users will have dined with exactly the same individuals before, which is why we want to think of controlling recommendation based on constraints derived from C as opposed to C itself. For example, we may want to generalize Alice’s dining occasion as a small work event, which would exclude peer experiences where the meal was a large banquet.
From the target context, we derive three sets of contextual constraints: C1; C2; C3 and apply them to these components separately, yielding the following context-sensitive formulation: Pa;i;C = ra;C3 +
P u2NC1 (ru;i;C2 ru;C2 )
sim(a; u)
P u2NC1 sim(a; u) (2)
This version of the equation replaces N with NC1 , meaning that we only consider neighbors who have rated item i in a context matching C1. Instead of averaging over all ratings when normalizing peer ratings, we select only those ratings in contexts matching C2, and we do a similar thing for the target user by matching against C3.
In our previous work, we were able to show significant
improvement in accuracy for hotel recommendation in a travel data set
(http://www.tripadvisor.com/) with the following constraints: C1
(neighbor filtering) using “state of origin”, C2 (peer baseline)
using “trip type” (e.g. business, family, etc), and no constraints on
target user baseline, C3 = fg, where trip type is known as a typical
influential context [
We model the relaxation as a process of binary selection – we represent C1, C2 and C3 as binary vectors where a bit value of one denotes that we filter the data using that feature. In extending this work to other data sets and adding context-linked features, it became clear that an optimization approach based on exhaustive search was not scalable.
To some extent, regularities in the data and dependencies between the variables can shrink the combinatorial space. For example, in our travel data set, origin city was fixed for each user, meaning that whether we restricted it or ignored it, the computation was the same when computing a user’s baseline. So, that variable only became relevant for neighborhood calculation. There were other similar simplifications for the other components, and we imagine that this would be true of most recommendation domains.
Even with such simplifications, we require a more scalable optimization technique than exhaustive search. Furthermore, the optimization space is highly non-linear and standard approaches such as gradient descent cannot be used. However, we have had success with the particle swarm optimization technique. 3.2
Particle swarm optimization (PSO) [
The basic idea behind PSO is that optimization is produced by a number of particles at different points in an optimization space. Each particle searches independently for the optimum, guided by the local value and communication with the other particles. In our case, we use RMSE as the value to be minimized and the position in the space corresponds to a set of constraints. Each particle i records its personal best performance (iBest) and corresponding best position (Pibest). The algorithm also keeps track of the global best performance (gBest) and corresponding position (Pgbest).
In each iteration of the algorithm, each particle moves through the optimization space as a function of its velocity. The velocity is a function of an inertia term and represented by functions of iBest and gBest. The inertia is gradually decreased over time so that the particles will be more influenced by the previously-located minima.
The update formulas for Vij (the velocity of jth bit in particle i) and the global inertia w are as follows:
Vij;t = wt
Vij;t 1 +
1'1
where '1 and '2 are positive random numbers drawn from a
uniform distribution between 0.0 and 1.0, 1 and 2 are
constant learning factors (set as 2.0 by empirical suggestions [
Usually velocity is restricted within range [ Vmax; Vmax]. It cannot be too fast or too slow – a small velocity will result in minor changes on the positions, where large velocity will drive the particle to move too much in the space. Vmax is suggested to be the maximum value of each bit in the position vector, where in our case it is 1 because the value switches between 0 and 1. Further experiments show that 2.0 is a better configuration.
The inertia at a given iteration t is calculated by: wt = wend + (wstart wend) (4)
Finally the bit value can be updated as follows: of change to zero should be decreased. Then the improvement can be described as follows:
If Pijbest = 1 Then di1j;1 = 1r1 and di0j;1 = 1r1 If Pijbest = 0 Then di0j;1 = 1r1 and di1j;1 = 1r1 If Pgjbest = 1 Then di1j;2 = 2r2 and di0j;2 = 2r2
If Pgjbest = 0 Then di0j;2 = 2r2 and di1j;2 = 2r2 where di1j and di0j are two temporary values and r1 and r2 are two random variable in range of (0,1). 1 and 2 are the same learning factors. With this in mind, we define two separate velocities, one in the “1” direction V 1 and one in “0” direction V 0.
We choose Vi1j or Vi0j as the velocity, depending on the current position of the particle for that bit. (Tmax
t)
Tmax
where Tmax denotes the maximum number of iterations. The
designer specifies a starting and ending weight with wstart > wend.
A large inertia weight value facilitates a global search while a
small value facilitates a local search. The linear decreasing value
means that the algorithm begins with the particles being more
influenced by their current direction and ends with them being more
influenced by their neighbors. We followed the empirical
parameter configuration: wstart = 0.9 and wend = 0.4, which is suggested
in PSO research [
The velocity is used to update the value (position) Xij of each bit in the binary vector. Basically, the higher the velocity, the greater probability of switching to 1.
Xij;t =
1; if (randt < S(Vij;t))
0; otherwise
(5)
where S(Vij;t) = 1+exp(1 Vij;t) , which is a sigmoidal function
squashes the range of velocity to a range of [
In our application, we use from 1 to 5 particles initialized with a random velocity and random bit vectors representing the possible constraints. For each iteration, every particle runs our algorithm across the training set, compares the RMSE it acquires in current iteration with the best so far (pBest and gBest), and updates them as well as the corresponding positions. Then the new position for next iteration is generated based on the equations above. The ability of the particles to communicate within the swarm reduces the total number of iterations required to reach an optimum. 3.2.1
Improved BPSO
Whether each bit value in the binary vector for each particle is 1
or 0 actually depends on the value of velocity – if the velocity is
larger, it is more like it is to switch to 1. Thus the weakness of
classical BPSO is that it only considers the possibility of change
to 1, and does not take the possibility of change to 0 into
account. Mojtaba et al [
1 1 Vi0j = wVi0j + dij;1 + dij;2
0 0 Vij;t =
Vi1j ; if (Xij;t 1 = 0) Vi0j ; if (Xij;t 1 = 1) (6) (7) (8) (9) Xij;t =
Xij;t 1; if (randt < S(Vij;t))
Xij;t 1; otherwise where Xij;t 1 denotes the 2’s complement of Xij;t 1; that is, if Xij;t 1 = 0, then Xij;t 1 =1; otherwise, Xij;t 1 =0. Our experiments show this improved version can find optimum more efficiently than classical BPSO. 4.
For this paper, we use a rating data set in the area of food, the
"AIST context-aware food preference dataset" which was used and
distributed by the author Hideki Asoh [
For our exploration of contextual recommendation, we use 6 variables. The key contextual variable is degree of hunger (real or virtual), but we also wanted to explore context-linked features including gender and various item features related to the food that were available in the data. Food genre indicates the food is Chinese, Japanese or Western food; food stuff denotes the food category is vegetable, pork, beef, or fish, and the food style contains values that represent the style of food preparation.
The data set is split into five folds where each user has at least one rating in each fold. For each fold, we used DCR to come up with the optimal combinations of context and context-linked features. We compare this technique to collaborative filtering without contexts and with contextual pre-filtering which is the similar to the Equation 2 where C2 and C3 are null are we only constrain the neighbor selection.
In order to determine the value of context-linked features, we created two additional test conditions looking at the contextual feature alone (degree of hunger) and using the contextual feature together with context-linked features (demographic and item features discussed above).
In order to assess the effectiveness of our particle swarm technique, we performed exhaustive search of the constraint space (8,192 iterations) and compared this result with that found by the optimization technique.
Recall that we want to discover influential contexts and contextlinked features, and our method for doing so is to find the optimal set of constraints and see what features are contained therein. Our results show that on this data set appropriate relaxation of contexts and features can help improve predictive performance, and incorporating context-linked features outperforms using contexts only.
The experimental results are shown in Figure 1 and Table 1. We use CO to denote contextual features (degree of hunger) and CL to denote the other demographic and item features that we suspect may be context-linked. These are the results achieved by exhaustive search; the optimization results are as below. 100.0% 99.7% 99.4% 99.1% 98.2% 97.9% 97.6% 97.3% 97.0% 98.8% 98.5% Coverage (Line) RMSE 1.155 (Bar) 1.140 1.215 1.200 1.185 1.170 1.125 1.110 1.095 1.080
Standard CF Pre!filtering Pre!filtering Pre!filtering DCR (CL) DCR (CO) DCR (CO+CL) (CL) (CO) (CO+CL)
RMSE Coverage
As the figure shows, the contextual pre-filtering and our DCR model can make improvements comparing with the standard CF without incorporating contexts, and the DCR model achieved the best RMSE among these algorithms. Besides, DCR shows better accuracy improvement when context-linked features are added, but it does not work for contextual pre-filtering. We believe the effects shown by adding context-linked features are domain-specific. And those features should be applied to appropriate components in the model, where DCR using CL only and DCR using CO and CL together provide significant improvements in terms of RMSE. But pre-filtering restricts the application of context-linked features for neighborhood filtering only. – it may not provide accuracy improvements; instead, more restrict constraints may bring lower coverage as shown in the figure above.
We also examined coverage. When the dataset is sparse, introducing contextual constraints can greatly limit coverage, an effect that we found in our previous research. With this dataset, there was little cost in coverage – the best coverage is 99.7% by standard CF model, while the best DCR model shows a 99.3% coverage. Notice that when contexts are introduced into the 1st algorithm component (neighbor filtering), the coverage may depend on which variables are selected as the relaxed ones for this component, as well as the density of contextual information in the data set. From Figure 1 and Table 1, we can see the coverage of pre-filtering using both context and context-linked features is the lowest, because real hunger and gender together as more strict constraints are selected and applied in this component.
Analysis of the Optimal Constraints Table 1 shows how the different conditions yield different optimal constraints. For pre-filtering and DCR using contextual features only, the real hunger is influential. When context-linked features are added, real hunger is still influential, but it is applied to different components in the DCR model. Context-linked features can provide accuracy improvements but it has to be applied to appropriate components – the best DCR model is using all of the algorithm components, the pre-filtering part of the algorithm retains only “gender” and the hunger-related features are applied elsewhere.
Context-linked features - gender, food genre, food stuff, food style are selected and applied in the optimal model. The position of contextual constraints in the optimal relaxation is also telling. “Gender” turns out to be the best feature for C1, indicating that same-sex peer neighborhoods work best in this domain. Also, we see that a fully restricted constraint – all contexts and food features appear in C2, which is where we choose the ratings to be used in constructing the peer user’s baseline rating. It confirms the assumption by CARS – users’ preferences differ from contexts to contexts, thus neighbor’s exactly matched contextual ratings contribute significantly to predict user’s rating on the same item under the same contexts. The optimal model took real hunger as the only constraint in 3rd component, which implies the users’ average rating under the same real hunger situation works the best as the representative of this component. 5.3
It is clear that differential context relaxation is useful both for improving algorithm performance and discovering crucial features. However, exhaustive search is not a practical or scalable way to realize this goal, although it is possible in this data set.
We used this data set as an opportunity to experiment with BPSO as an alternative method of finding the optimal context relaxation. We examined particle counts from 1 to 5, using a maximum of 100 iterations. A local minimum occurred in classical BPSO – it converged an RMSE (1.116) not quite as good as the global minimum found by exhaustive search (1.114). The improved BPSO algorithm does find the global minimum RMSE and the same set of relaxations as the exhaustive search. Figure 2 shows the learning curve of the improved version, where N -BPSO denotes we use number of N particles in the swarm. Improved BPSO finds the 1 BPSO 3 BPSO 5 BPSO optimal solutions on average around the 18th iteration using one particle, and 12th iteration using five particles. 18 iterations with 1 particles corresponds to 18 evaluations over the training set, a more than 455 reduction in computational cost. Increasing the number of particles expands the power of social contributions by other particles, and can reduce the number of iterations, but also increases the amount of computation per iteration. The selection of the number of particles and the number of iterations depends on the specific cost and computational complexity of the algorithm.
Differential context relaxation is a technique for context-aware recommendation that decomposes the recommendation algorithm into components and filters the data used in each component. The context is considered a set of constraints, which may be relaxed to achieve the best recommendation performance.
In this work, we examine an optimization technique – binary particle swarm optimization – to efficiently locate the highest performing set of contextual constraints. We show that BPSO can find the global optimum constraint set with a fraction of the iterations required by exhaustive search.
We also show that both contextual features and context-linked features can be useful in our context relaxation model. Furthermore, our algorithm highlights the different roles that contextual features play, producing some interesting results, such as the fact that same-sex neighbor populations work best in our food data set.
Future research will be focused on two parts: 1) exploring the possibility for real-valued (as opposed to binary) definition of differential context relaxation and 2) applying the same technique to additional algorithms beyond user-based collaborative filtering. 3) combine with the latent factor models, such as matrix factorization in order to alleviate the sparsity problem of contextual ratings and examine our differential model in another way. C1 = {}; C2 = {food genre, food stuff, food style}; C3 = {food genre, food stuff, food style} C1 = {real hunger}; C2 = {}; C3 = {real hunger} C1 = {gender}; C2 = {real hunger, virtual hunger, food genre, food stuff, food style}; C3 = {real hunger}