Project topics and materials
Get Complete Project Material File(s) Now! »
Recommendation Systems
In this chapter, we first present and define Recommendation Systems (RS): their goals, the variety of data they use for their tasks, and their applica-tions. An overview is given over the wide range of approaches traditionally applied to perform recommendation. An emphasis is especially put on Col-laborative Filtering (CF) methods based on Matrix Factorization, which are the most popular among RS methods, and will be used in our approaches in the following chapters of this thesis. The second focus is put on evaluation metrics and scenarios commonly used in the field of RS, since our evalua-tion scheme will distinctly differ from these traditional methodologies.
Definition: The Recommendation Problem
Recommendation (or Recommender) Systems (RS) are techniques or soft-ware programs which aim at providing accurate or useful suggestions of some items to a user (Resnick and Varian, 1997). User is the general term to designate the entity to which the recommendation is provided, while Item labels the product being recommended. Depending on the field of applica-tion for the system, the user is usually an individual, but this term can also designate a group of people, a company. . . while recommended items can be as various as a computer to buy, a movie to watch, a song to listen to, a news to read, etc.
After the user navigated on the RS or accepted a recommendation, some feedback (a rating for example) is given to the system about the item pur-chased or consumed. In order to suggest more personalized and appropri-ate recommendations in future appearances of this user, the RS will make use of all past interactions and feedback of the user. If available, the system can potentially use as input other diverse sources of data, such as informa-tion about the user or item. For instance, demographic information given by the user to fill in his profile, like his age, gender, profession can be used as User Model, while information about the item like the genre of a movie or its director and actors can be used to build an Item Model. Social net-work of a given user and his relations to other users can also be a source of information. Finally, some information coming from the context, like the location of the user or temporal information (the season, the current time of the day. . . ) can be included to improve the model and the recommendation accuracy. A survey about the use of this additional information is available in (Shi et al., 2014). However, the main information leading to personalized recommendation to the user resides in the feedback he gives to the RS.
Feedback
Once an item has been recommended, a feedback is usually requested from the RS to the user, in order to improve its model and make future recom-mendations more accurate. The feedback given by a user to the RS can take various forms and is usually divided into two sorts:
• The explicit Feedback is a feedback directly given by the user to the system: the user’s involvement is thus required to obtain such infor-mation. It is often given in the form of a rating on a numerical scale such as the one-five stars scale often used in movie RS. Other forms of explicit feedback exist (Schafer et al., 2007): a unary (or binary) an-swer such as a « like » (and possibly « dislike ») button, or on an ordinal scale like « strongly disagree / disagree / neutral / agree / strongly agree » answer to a questionnaire. Another possible explicit feedback consists in a tag or a text comment about an item: this is possibly a more helpful form of feedback for the system or other users as it con-tains more information than a simple rating. However, such type of feedback is more complex to integrate into the model.
• The implicit Feedback (Oard et al., 1998) can be collected without the user giving directly his opinion to the system. It can be inferred from any detectable user’s behavior, such as clicking on an item, book-marking a page or news, putting an item into the basket, watching a video or listening to a song entirely. . . The main advantage of im-plicit feedback is that it does not require the user’s involvement, but it can be more noisy than explicit feedback and needs to be treated more carefully.
Notice that implicit feedback is more abundant than explicit feedback due to its nature, but it is also less reliable as the true user’s preferences are not directly expressed. Moreover, a feedback (especially implicit one) usually needs to be preprocessed to be used correctly by algorithms.
Representation and Solutions
The feedback given by the user is usually represented in the form of a ma-trix of ratings, where each user is a row of the matrix, each item is a column of the matrix, and the entry in the matrix represents the rating given by the user on a given item.
We now introduce some notations for the following sections about the recommendation problem. We consider :
• N = fu1; : : : ; uN g is the set of N users,
• M = fi1; : : : ; iM g is the set of M items,
• R of size N M is the matrix of ratings representing users’ prefer-ences,
• ru;i in R represents the tastes of user u with regards to item i,
• S designates the set of known entries of R,
• I(u) is the set of items i for which (u; i) 2 S (the items for which the user u gave a rating),
• J (i) is the set of users u for which (u; i) 2 S (the users who have rated item i).
The illustration in Figure 2.1 displays a recommendation scenario with N = 5 and M = 6.
FIGURE 2.1: Example of a matrix of preferences used in a RS, for five users and six items and with a 1 to 5 stars rating.In this example, I(u3) = fi1; i2; i3; i5g and J (i3) = fu2; u3g. An empty rating in the matrix signifies that no preference were given by the user on the item (for example, user u1 did not indicate his preference about item i3). The matrix of ratings is actually usually very sparse: the number of items and users in a real-word RS grows very large, and a user will give his preferences about a small fraction of all the items in the system.
From all the information available, the RS has to maximize a utility func-tion f over the set Lu of items which can be recommended for each user u. This function predicts how much a user would like the items. Algorithm 1 displays an algorithm for recommendation.
The set of possible items to recommend depends on the type of appli-cation, and an item already rated does not always imply it cannot be rec-ommended again. In a movie RS for example, it is not really advisable to recommend movies for which the feedback has already been given recently, as it is unlikely that people would want to watch the same movie one more time right after watching it. On the opposite, a music RS can recommend a song for which a high rating has recently been given, as the user would probably like to listen to the song again if it suits his mood or current tastes.
Once the RS has a user and the list of possible items to recommend as in-put, the recommendation problem is usually solved following two possible sort of techniques:
• The first way is by doing Matrix completion, which means filling the empty entries in the matrix of ratings. This is the most widespread approach. The system will first make a prediction of the rating value for every recommendable item for the target user, and then provide the recommendation based on these predictions. In this case, the util-ity function in the Algorithm 1 attempts to predict the rating.
• Another way is by using Ranking approaches, which is detailed in Sec-tion 2.7. These approaches tackle the problem from a different per-spective, assuming there is no need to predict a rating for all items. In fact, only finding the correct order of preferences between items which are being recommended is sufficient to satisfy the user. Rank-ing approaches and evaluation are starting to gain ground due to the flaws noticed in predictive evaluation (cf. Section 2.6 for more de-tails).
Note that it is possible to create a ranking approach from the first method which predicts ratings, simply by ranking items based on the predicted rat-ings. However, there are more natural methods directly targeting at op-timizing the order of recommended items. Regardless of the perspective used, all Recommendation Systems aim to achieve the same goals which are detailed in the next section.
Goals of Recommendation Systems
From a business point of view, the primary goal of a RS is of course to increase the profit of the company, through a higher number of sales. To reach this objective, the system has to be able to meet some requirements:
• Know what the user wants / Relevance: quite obviously, the RS has to suggest items that are relevant to the users’ tastes, because users are more likely to buy or consume items they have interest in. However, solving this task alone is not sufficient to satisfy a user, as it is ex-plained in the next point.
• Diversity, Novelty and Serendipity: firstly, if the RS always suggests items of the same sort to a user, there is a risk that this user would get bored or would not like any item. Thus, the system has to pay at-tention to put items of different types, bringing diversity. Advertising more diverse items also helps the system to gather feedback about a wider set of products, and can be beneficial for future recommendation.
Secondly, even if it can be relevant, the recommended item also has to be something the user has not already bought or experienced in the past: some novelty is required.
Lastly, the serendipity implies to surprise the user by recommend-ing items he does not expect. Compared to novelty, the suggested item would belong to a category the user did not expect at all. This can sometimes lead the user to widen its area of interest, and help to increase sales diversity. Serendipity is tightly related to the explo-ration/exploitation dilemma addressed in Chapter 3.
• User satisfaction and fidelity: finally, another goal of the RS is to in-crease the user satisfaction and fidelity. A good user interface and accurate recommendations might encourage the user to connect and use the site again. Giving explanations about why a specific recom-mendation has been provided is also usually appreciated by users. User fidelity to a RS implies more feedback is received from this user, leading to more refined knowledge of his tastes and consequently to better recommendations for this particular user.
These key goals are common to all RS in any application case, and they need to be integrated carefully during the implementation of the system.
Table of contents :
1 Introduction
1.1 Motivations
1.2 Overview of the thesis
2 Recommendation Systems
2.1 Definition: The Recommendation Problem
2.1.1 Feedback
2.1.2 Representation and Solutions
2.1.3 Goals of Recommendation Systems
2.1.4 Applications
2.2 Approaches to Recommendation
2.2.1 Content-Based Filtering
2.2.2 Demographic Filtering
2.2.3 Knowledge-Based Recommendation
2.2.4 Neighborhood-Based Collaborative Filtering
2.3 Collaborative Filtering: Matrix Factorization Techniques
2.3.1 Matrix Factorization and Low-Rank Approximation
2.3.2 Matrix Factorization Methods
Objective
Optimization Methods
Incorporating Bias
Other Models
2.3.3 Limitations
2.4 Cold Start Issue
2.4.1 Hybrid Recommendation Systems
2.4.2 Active Learning
2.5 Incorporate Contextual Information
2.6 Evaluation of Recommendation Systems
2.6.1 Metrics
2.6.2 Evaluation Scenarios
2.7 Learning to Rank
2.8 Conclusion
3 Recommendation as a Multi-Armed Bandit
3.1 Sequential Recommendation
3.1.1 Formulation of the Sequential Recommendation Scenario
3.2 Related Work
3.3 Multi-Armed Bandits
3.3.1 Setting
3.3.2 Approaches
3.4 Explore-exploit Recommendation System
3.5 Experimental Investigation
3.5.1 Experimental Setting and Remarks
Datasets
3.5.2 Baselines
3.5.3 Impact of Exploration
3.5.4 Impact of the Update Strategy
3.6 Concluding Remarks
4 Ranking Using (No-)Click Implicit Feedback
4.1 Sequential Recommendation of Multiple Items
4.2 Related Work
4.2.1 Online Ranking in Information Retrieval
4.2.2 Recommendation with Ranking Approaches
4.2.3 Mixing Explicit and Implicit Data
4.3 Ranking Recommender System Using Click Feedback
4.3.1 Setting
4.3.2 Feature Engineering
4.3.3 Dual Matrix Factorization
4.4 Experimental Investigation with ERR Click Model
4.4.1 Evaluation Metrics
4.4.2 Datasets
4.4.3 Baselines
4.4.4 Results and Discussion
4.5 Experimentation with Other Click Models
4.5.1 The navigational click model
4.5.2 The informational click model
4.5.3 The almost random click model
4.6 Concluding Remarks
5 About Challenges in Real Recommendation Systems
5.1 Some Aspects of Real-world RS
5.1.1 Power-law Distributions
5.1.2 « Replay » Aspect
5.1.3 Large Set of Possible Recommendations
5.1.4 Stock Availability
5.1.5 Past and New Users/Items
5.1.6 The Influence of the Recommendation System
5.2 Realistic Offline Sequential Recommendation
5.2.1 Setting
5.2.2 Results and Discussion
Impact of Exploration
Update of the Model
5.2.3 Final Remarks
5.3 Some Lessons from a Real Case RS Challenge
5.3.1 RecSys Challenge 2014: Data and Protocol
5.3.2 Method
5.3.3 Experiments and Discussion
Experimental Results
Relevant Features
Discussions
5.4 Concluding Remarks
6 Conclusion
6.1 Thesis Contributions
6.2 Future Work
A About UCB1 and Popular baselines
Bibliography
