Le travail réalisé au cours de ces trois années de thèse n'aurait jamais pu avoir lieu sans la présence et l'accompagnement de nombreuses personnes.

Mes remerciements vont tout d'abord à mes deux maîtres de thèse, Alessandro Lazaric et Jérémie Mary, d'accepté de me suivre dans cette aventure de thèse CIFRE quelque peu originale. Nos discussions m'ont énormément apporté. J'ai eu l'impression de redécouvrir le machine learning tous les vendredis. Je remercie grandement Michèle Sebag et Liva Ralaivola d'avoir accepté d'être mes rapporteurs, surtout que la période n'était pas forcément la meilleure pour relire une thèse. Je remercie aussi Florence D'Alche-Buc et Rémi Gilleron d'avoir accepté d'être membres du jury.

Je remercie également toutes les personnes de l'équipe SequeL qui m'ont accueilli dans leur bureau, notamment Michal Valko, toujours à l'écoute de ma recherche et prêt à aider de toutes les manières possibles.

Cette thèse CIFRE n'aurait évidemment pas pu exister sans la présence de fifty-five. Un grand merci à Arnaud Massonnie pour ce déjeuner où tu m'as aiguillé sur le droit chemin, pour ces déjeuners où tu as écouté avec attention toutes mes propositions les plus improbables. Chacune de ces discussions me redonne toujours de l'énergie, de l'envie et de la confiance. Merci à Jean-François Wassong, toujours présent pour écouter également mes idées aléatoires et soucieux de l'équilibre entre mon travail de recherche et mon travail industriel.

Merci à mes collègues de fifty-five, notamment ceux de mon équipe. Merci Martin et Paul de m'avoir fait grandir en data science. Merci Bettina et Bridget pour tous les projets qu'on a fait ensemble et toutes ces pauses qui m'ont bien aidé pendant ces années... Sans vous quatre ces années auraient été bien tristes.

Merci à mes anciens colocs++, Chris, Keurcien, Matthieu, Maxime, Pierre (t'étais pas à la coloc mais je te compte dedans quand même), Thibaud, et surtout William bien sûr. Merci pour nos vacances, votre soutien à tout moment pour tout problème, pour Fifa, pas pour LoL, pour la coloc et pour tout ce qu'on va vivre ensemble dans le futur. Merci également à Anaïs de parler plus vite que moi et à Aude pour m'avoir apporté des Monster Munch.

Henri, la prépa c'est censé être dur, les colles aussi, mais passer deux ans à partager mes colles avec toi, c'était le pire. Heureusement j'ai fait 5/2 et pas toi, j'ai pu profiter un peu de la prépa. Tu te souviens de rien alors je te donne quelques-uns de mes souvenirs: merci pour le Michelson, pour notre première colle This PhD was written inside the company fifty-five as part of a CIFRE (Conventions Industrielles de Formation par la REcherche) project.

Part of You & Mr Jones, the world's first brandtech group, fifty-five is a data company helping brands to collect, analyse and activate their data across paid, earned and owned channels to increase their marketing ROI and improve customer acquisition and retention. Headquartered in Paris with offices in London, Hong Kong, New York and Shanghai, the data company was named by Deloitte as one of the fastest-growing tech firms in Europe, thanks to its unique technology approach combining talent with software and service expertise.

fifty-five data expertise is leveraged by data science in order to solve marketing issues in order to optimize user value thanks to product recommendation, website personnalization, churn detection, marketing user clustering or website pain points detection.

avec Charmont, de m'avoir insulté après t'avoir dit "à tes souhaits" en colle avec Dumas.

Merci à ma famille, papa, maman, Lucie, Vincent, qui m'a soutenu durant toute ma scolarité, merci de m'avoir toujours poussé. Merci maman pour tout ce que tu as fait de la maternelle à l'ENS en passant par la prépa où tu as passé beaucoup de ton temps à faire en sorte que j'en aie.

Merci à Mimi, Zizie et bien évidemment Melwenn. Merci d'avoir laissé ta lumière allumée, merci de m'avoir écouté soir après soir parler de ma thèse, je n'en parlerai plus. Merci d'avoir relu ma thèse. Merci d'aimer les chats. Merci d'avoir de la caisse.

Merci à tous.

Résumé court en français. Cette thèse, réalisée en entreprise en tant que thèse CIFRE dans l'entreprise fifty-five, étudie les algorithmes des systèmes de recommandation. Nous avons proposé trois nouveaux algorithmes améliorant l'état de l'art que ce soit en termes de performance ou de prise en compte des contraintes industrielles. Pour cela nous avons proposé un premier algorithme basé sur la factorisation de tenseur, généralisation de la factorisation de matrice couramment appliquée en filtrage collaboratif. Cette extension permet de prendre en compte simultanément différents types d'interaction entre les utilisateurs et les produits et dans des contextes différents. L'algorithme proposé est également hautement parallélisable ce qui le rend facilement utilisable sur des données réelles très volumineuses. Nous avons ensuite proposé un nouvel algorithme permettant d'améliorer l'état de l'art des solutions de complétion de paniers. L'objectif des algorithmes de complétion de paniers est de proposer à l'utilisateur un nouveau produit à ajouter au panier qu'il/elle est en train d'acheter permettant ainsi d'augmenter la valeur d'un utilisateur. Pour cela nous nous sommes appuyés sur les processus ponctuels déterminantal (DPP), c'est à dire une mesure de probabilité dont la probabilité d'observer un ensemble est proportionnel au déterminant d'un noyau. Nous avons généralisé l'approche de la complétion de paniers par DPP en utilisant une approche tensorielle couplée à une régression logistique. Enfin nous avons proposé un algorithme d'apprentissage par renforcement permettant d'alterner entre différents algorithmes de recommendation. En effet, utiliser toujours le même algorithme peut avoir tendance à ennuyer l'utilisateur pendant un certain temps, ou à l'inverse lui donner de plus en plus confiance en l'algorithme. Ainsi la performance d'un algorithme donné n'est pas stationnaire et dépend de quand et à quelle fréquence celui-ci a été utilisé. Nous avons alors modélisé la performance future d'un algorithme par une régression linéaire définie par un polynôme en une fonction de récence, c'est à dire une fonction qui mesure la fréquence d'utilisation d'un algorithme dans un historique récent. Notre algorithme d'apprentissage par renforcement apprend alors en temps réel à alterner entre divers algorithmes de recommendations dans le but de maximiser les performances sur le long terme, c'est à dire de continuer d'intéresser l'utilisateur le plus longtemps possible. Cet algorithme peut être vu comme un algorithme de recommendation hybride.

Cette thèse ayant été réalisée en entreprise, nous avons toujours recherché à respecter les contraintes industrielles lors du développement de nouvelles solutions. Ainsi chaque chapitre présentant un nouvel algorithme contiendra une section dans laquelle nous présenterons comment la solution a été utilisée ou pourrait être utilisée en pratique. Short English abstract. This thesis, written in a company as a CIFRE thesis in the company fifty-five, studies recommender systems algorithms. We propose three new algorithms that improved over state-of-the-art solutions in terms of performance or matching industrial constraints. To that end, we proposed a first algorithm based on tensor factorization, a generalization of matrix factorization, commonly used on collaborative filtering. This extension allows to take into account simultaneously several types of feedbacks as well as different contexts. The proposed algorithm is also highly parallelisable thus suitable for real life large datasets. We then proposed a new algorithm that improves basket completion state-of-the-art algorithms. The goal of basket completion algorithms is to recommend a new product to a given user based on the products she is about to purchase in order to increase the user value. To that end we leverage Determinantal Point Processes (DPP), i.e., probability measure where the probability to observe a given set is proportional to the determinant of a kernel matrix. We generalized DPP approaches for basket completion using a tensorial point of view coupled with a logistic regression. Finally, we proposed a reinforcement learning algorithm that allows to alternate between several recommender systems algorithms. Indeed, using always the same algorithm may either bore the user for a while or reinforce her trust in the system. Thus, the algorithm performance is not stationary and depends on when and how much the algorithm has been used in the past. We then model the future performance of an algorithm according to linear function which is a polynomial in a recency function, that is a function that measures the frequency of use of an algorithm in a recent history. Our reinforcement learning algorithm learns in real time how to alternate between several recommender system algorithms in order to maximize long term performances, that is in order to keep the user interested in the system as long as possible. This algorithm can be seen as an hybrid recommender system.

This thesis having been written in a company, we always looked for considering industrial contraints when developing new algorithms. Thus, each chapter that introduces a new algorithm will contain a section in which we present how the solution has been used or could be used in practice.

List of Tables

fifty-five Introduction 1.1 Overview of Recommender Systems

People who liked this product also liked ... -According to your recent browsing history you may like ... -Because you watch this movie you may also enjoy ... With the increasing amount of choices, especially on the internet, recommender systems play an important role in helping users to find relevant items according to their taste and such advertising are spreading everywhere. Indeed having a tremendous amount of choices creates a positive feeling of freedom but also overwhelms users and leads them to make poor decisions [START_REF] Ricci | Recommender Systems Handbook[END_REF]. To overcome this problem, recommender systems have emerged at the intersection of computer science and the machine learning community, in order to guide the user into her search. Many companies use recommender systems with success everyday like e-commerce websites (Amazon, Wallmart), News websites (e.g. Yahoo), Subscription Video On Demand services (e.g. Netflix, Amazon, HBO Go, Hulu), crowd-sourcing reviews providers (e.g. Yelp, TripAdivsor), Massive Open Online Courses (e.g. Coursera, edX), music streaming services (e.g. Spotify, Deezer, SoundCloud), retargetings (e.g. Criteo) in order to provide personalized content to each user and improve user experience.

The research field of recommender systems emerged in the mid-1990s, and has kept increasing ever since, with thousands of research papers on the topic (see Figure 1.1). Conferences are now dedicated to this field like the ACM Recommender System (RecSys) since 2007, and international machine learning and artificial intelligence conferences like ICML, AAAI, KDD, NIPS, ..., include sessions dedicated to recommender systems. However recommendation was not invented with machine learning and the Internet. Everyday we get recommendations from people around us who share their experience that we trust more or less given our personal similarity with the person and the information they provide on the experience. Before watching a movie we read newspapers critics to make our decision, and likewise we are more willing to trust some journalist or newspaper than others. That is what recommender systems are trying to mimic by finding similarities between thousands or millions of users in order to collaboratively infer our tastes on items we do not know of but some similar -yet to define -users consumed and filter out the possibilities. The underlying simple idea being: if we agreed in the past, we are likely to agree in the future.

In order to perform effective recommendations, machine learning algorithms leverage knowledge from historical data to infer rules, correlations, descriptors, preferences and use those to pick the right item(s) to present to each user, where an "item" is the generic term to denote what the system is trying to recommend to users, such as books, songs, news, movies, clothes, restaurants, ... Historical data can be very heterogeneous, such as specific information on the user (i.e., gender, age, occupation, zip), item characteristics (i.e., genre, year, actors, color, texture, price, discount), explicit feedback from users on items (i.e., rating, like/dislike) that indicate their feeling or implicit feedback gathered through users interactions with items (i.e., view, click, add to cart, purchase, zoom) that can be interpreted as a sign of interest. By interacting with the system, the user keeps giving new information about its preferences that is used to update the system and provide better future recommendations. Leveraging this information to provide a personalized experience to users is the challenge of recommender systems. This dissertation aims at improving state-of-the-art solutions in adequation with industrial constraints.

Limitations and open questions

On October 2, 2006 the Netflix Challenge officially started. IT rewarded anyone who improved the accuracy (in terms of RMSE) of their current algorithm, called Cinematch, by 10% with a million dollar price. During three years many teams and people gathered and competed to propose recommender system solutions. This led to many valuable lessons but also showed the limitations of current methods and introduced many open questions.

In this challenge, matrix factorization techniques proved their effectiveness to address the recommendation problem and led to many tuning in the following years. Among others, taking into account the date in multiple ways also showed interesting improvements underlying non-stationarity in recommender systems. Finally blending many different algorithms, i.e ensemble methods, proved their effectiveness and was the key to win the competition. Indeed, the final winning submission is actually made of more than 500 algorithms where each algorithm has good performance in some specific regions of the possibilites. Merging all the predictions according to extra knowledge, like the number of feedback the user had previously provided, the number of feedback the movie had received, the date, etc ..., gave the extra-performance boost to beat Cinematch by more than 10%.

However several critics have arised during and after this challenge. First, the ensemble method proposed by the winning team is actually unusable in practiceand is not used by Netflix -because it requires far too much computational power to be used in the real world. Second the choice of the evualation metric, the root mean squared error, was critized because it does not really reflect how the system will be used in practice. Following work then focused on different optimization solutions, like learning to rank instead of learning to predict an affinity, and different evaluation metrics that we will detail in the next chapter.

Besides those critics, state-of-the-art recommender system algorithms suffer from other limits that nurtured reflection for this thesis. The first limit that penalize recommender systems is the poverty of user historical data, called cold-start problem. Indeed in web application, user identication is performed using cookie tagging (a small code placed in the user browser). Those cookies have an expiration date of 13 months by law, are not consistent through different devices -that is a user using two devices will be seen as two different users -and they can be manually deleted. Since users preferences are learned using past feedback on items, users in cold-start situations will receive poor recommandation. This problem is less true for applications were people have to login in order to access the website and have frequent interactions like Netflix or Facebook. To overcome this issue we extend state-of-theart algorithm 3.6.1 to take into account multiple types of interactions within the same framework and thus limit the poverty of available feedback per user. Indeed in practice users can interact with items in a various number of ways and thus limiting the analysis to only one type of feedback lessens the possibilities.

A second limit is the computational complexity of basket completion algorithm. State-of-the-art solutions are mostly based on explicitly computing co-occurences that are untractable in practice. Some solutions have been developed in the recent years based on Determinantal Point Process and on Recurrent Neural Network for the more general problem of session based recommender system (see 4.5.1). In this dissertation, we propose a new algorithm that adresses the basket completion issue and opens the door to more generalization of Determinantal Point Processes.

A third limit comes from online model evaluation. Usually people perform tests, that is different users will be exposed to a different model, but always the same one for a given user, and success rate is monitored through time to output the best model. Comparing several solutions in order to find the best one is a very active domain since exploration optimization among a (fix) set of solutions is the core interest of the bandit community (section 2.1.3). However the question of the non stationary behaviour of the action (here the recommender system that is being tested) and the impact of past pulled (past recommender systems choices for a user) on next pull performance had received little attention in recommender system and will be studied in this dissertation.

Partially adressed by this dissertation, the filter bubble problem is a main limit of recommender system. This designed the fact that recommender systems lock user in their past tastes and prevent them from discovering new areas and diversifing their viewpoints. To adress the question, machine learning researcher focus on the trade off between exploitation (taking the best action) and exploration (gathering new information) without degrading too much short term reward and hoping to maximize future long term ones.

Overview of the dissertation

In the rest of the dissertation we first provide more machine learning background on recommender systems before presenting various works that address previoulsy introduced state-of-the-art recommender systems limitations.

• chapter 2 provides more machine learning related background on recommender systems. After introducing the different purposes and categories of recommender systems, we then introduce the classic measurement protocol for performance evaluation that will be used in the experiments.

• chapter 3: this chapter proposes an extension of matrix factorization based algorithm to tensor factorization in order to deal with multiple types of feedback at the same time and alleviate the cold-start problem. We proposed two algorithms for Tucker and parafac tensor factorization, respectively called tucker and parafac Hoals that are highly parallelizable and appropriately deal with missing data, two problems that were not correctly tackled by tensor factorization state-of-the-art. Performance evaluation on open data and fifty-five propriaritary data highlight the effectiveness of the proposed methods, that also have the major advantage of being easily implemented using available matrix factorization libraries like spark recommendation module.

• chapter 4: this chapter introduces an extension of Determinantal Point Process algorithms, called Multi-Task dpp, for basket completion with two complementary updates that allows more accurate basket completion that is also scalable to large item catalogs. The first one consists in using a logistic function upon the Determinantal Point Process to better model the supervision task. The second one is a low rank tensor approach for multi task prediction.

Although we focused on basket completion problem, where each task is a candidate item to add to someone basket, this algorithm can be tested for many different applications and can be the starting point to other generalizations of Determinantal Point Process for machine learning.

• chapter 5: always using the same strategy to personalize user experience is likely to cause users boredom or more generally non-stationary performances because of the evolution of user's preferences. A better idea is then to alternate between several personalization strategies. For instance, one could use an algorithm that focuses on serendipity, or on recommending very similar items.

Changing the number of recommended items can also fight users' boredom. Which variation to test and when to change is however an open question. This chapter proposes an algorithm, called LinUCRL to effectively learn the right way to alternate between several available algorithms in order to maximize user interest.

All those contributions are ultimately used together to fully personalize the user interaction with the brand at different level of its engagement. At first, when the user is completly unknown from the brand, fifty-five does not hold any personal feedback from this user to provide good personalisation. The user is then engaged using different media strategies like retargeting. Once the user reaches the website, a first customization is performed using popularity based algorithms until the user reaches the basket page where basket completion algorithms, like Logistic dpp, are used to increase the user value. Now that the user is known to the brand, fiftyfive can use other recommender system algorithms, like the ones of Hoals, first on e-mailing or mobile application notification, to give the user the incentive to come back on the website, where those algorithms are again used on the landing page. The journey now enters to a loop when the user reaches the basket page and basket completion algorithms are used again. At each personalization stage, LinUCRL algorithm is used to fight user boredom.

From an algorithm to a recommendation system

In a general sense, a good algorithm is not enough to have a good recommender system. Indeed feedbacks must be collected to feed the algorithm and recommendations must be displayed to the users. Thus the place of the user, the choice of the interface, the way data is collected, treated, used is essential. Here we discuss those questions that each brand asks whenever recommender systems come up into the discussion.

User interface and feedback collection

First recommender systems applications like BellCore's video recommender system used to give recommendation through e-mail: users had to e-mail their ratings on movies and would receive back an e-mail with recommendations ( [START_REF] Hill | Recommending and evaluating choices in a virtual community of use[END_REF]). While quite obsolete this technique is still used by various e-commerce websites or in the food industry, but it asks too much effort for the user leading to low response rates thus limiting the interest of the method.

More modern solutions put more effort into the design of the interface both to display recommendations and collect feedbacks. For instance, Youtube and Netflix use recommender systems to fully personalize the user's content and use a similar display technique: the items are ordered by row where each row corresponds to items that are related according to some notion of similiarity, such as the same genre, a common actor, related to an other movie, ... This display technique has the advantage of simplifying the navigation so that a user can skip categories that she is not interested in at the moment. Furthermore this particular display also provides new types of feedbacks, since scrolling in a row also shows users' interest in a specific theme. Youtube and Netflix present the advantage of having very engaged signed-in users with lots of navigation, thus an easy way to know the characteristics of their user base. Other companies do not have this advantage and cannot achieve such a deep level of personalization. Banners are then used at different moments of the navigation, like on the home page, on the product page, or on the basket confirmation page, to provide personalized contents with few items along with a catch phrase like "Users who liked this also liked ...". The navigation interaction collected from those interfaces provide implicit user interest with items, called implicit feedbacks. But gathering explicit feedbacks that is an explicit information from the user on how much she likes the item, is always valuable for the system. Some websites like Jester ( [START_REF] Goldberg | Eigentaste: A constant time collaborative filtering algorithm[END_REF]) provided a continuous bar where the level informs the users' affinity with the joke. However in most applications binary feedbacks, like thumbs up and down, are used. Indeed, even Netflix let down its world famous 5 star rating system in 2017 mainly for clarity reasons. In fact rating a movie 4 stars does not mean the same for everybody. From a machine learning point of view this problem is easy to solve since it only requires scaling each user ratings around 0 and now 0 means average for everybody. The second problem comes from ambiguity with other websites like IMDB or Amazon for instance. Indeed when Netflix presents a new movie to some users with 4 stars, for them it says "I think that you will rate this movie 4 stars" whereas for others it meant "The rest of world gave it 4 stars". That is the main reason why Netflix adopted the thumbs up/down rating system and provides recommendation with an affinity score as a percentage. This change led to lots of debate on online social networks with people threatening to leave Netflix because they wanted to give 2 stars to some movie. A survey from the exstreamist reported that 71% of the Netflix subscribers dislike the new rating system. The main critic is that people want to have more flexibility in the rating system instead of just yes or no. This event highlights the importance of the rating system and the difficulty to find a good one. The thumbs up/down system is also used on Youtube and Spotify for instance, but obtaining a good explicit feedback it still an open question... However for some applications like TV shows or music, explicit feedbacks are not the most valuable information. Indeed, the completion rate of the TV show or listening frequency to a singer are much more informative than a rating or a thumb up. Someone may rate some TV shows 2 by shame but actually love to watch it. Implicit feedbacks are more reliable in that case.

Two other questions always arise when displaying recommendations are: how many items to show and should only new items be displayed? In practice there is no general truth and testing on several options is required. For instance, some users will be exposed to banners/e-mails with 4 items, others with 6. In some displays there will be 1 or 2 items that the users already interacted with, in some others none. Previous tests showed that it is always a good idea to show at least 1 item that the user knows in order to catch the eye and give her confidence that the recommendation can suit her.

Privacy and security issues

As we have previously seen, feedbacks are the cornerstone of recommender systems. The more feedbacks and detailed information the system has about users and items, the more accurate it will be. But all this information raises privacy concerns. The question on how to keep privacy in recommender systems and tradeoff between personalization and data privacy is attracting the interest of the machine learning community and in 2017, the RecSys conference dedicated a tutorial on the question. [START_REF] Ramakrishnan | Privacy risks in recommender systems[END_REF], [McSherry and Mironov, 2009a], [START_REF] Lam | Do You Trust Your Recommendations? An Exploration of Security and Privacy Issues in Recommender Systems[END_REF], [START_REF] Koene | Ethics of Personalized Information Filtering[END_REF] discuss several issues regarding privacy and security.

A first privacy issue can come from hacking attacks that could leak highly sensitive information. Collecting less information about the user without degrading the performance too much was proposed to prevent this risk from occuring. The concept of VOI metric (Value Of Information) was introduced in order to tune a system to optimize data collection on precise items and stop collecting once the system has enough information on the user to make good personalized recommendations. Other kinds of attacks are also a concern in recommender systems. For instance shilling attacks, where someone gives high positive feedbacks to its own products that are sold on a platform in order to increase its chance to be recommended to others and high negative feedbacks to competitors. Creating lots of fake accounts to provide feedbacks is also a well known attack called Sybil attack. Such attacks can bias the model toward suboptimal recommendations. In 2002 Amazon was the victim of a similar attack when a few motivated users intentionally viewed the page for a spiritual guide by Christian televangelist Pat Robertson and "The Ultimate Guide to Anal Sex for Men" one after the other in order to push recommendation of the latter on the page of the former. Being able to identify such attacks are of main concern in recommender systems applications.

A second issue is identification or re-identification that enables to uniquely identify someone based on her feedbacks without any explicit Personally Identifiable Information (PII). [START_REF] Lam | Do You Trust Your Recommendations? An Exploration of Security and Privacy Issues in Recommender Systems[END_REF]] also mention the risk of quasi-identifiers, i.e., information that can almost uniquely identify a person. For instance, the triplet (zipcode, birth data, gender) is a quasi-identifier. Massachusetts governor William Weld former governor was re-identify with this technique between a voter registration and a supposedly anonymous medical record dataset given to researchers [Sweeney, 2002]. [START_REF] Narayanan | How to break anonymity of the netflix prize dataset[END_REF] proposed two algorithms to identify records in a public database using an auxiliary partial knowledge on some records and proved successful identifications on the Netflix dataset. With this issue also comes the problem of inference. For instance [START_REF] Kosinski | Private traits and attributes are predictable from digital records of human behavior[END_REF] shows that highly sensitive information like sexual orientation, political views and age among others can be retrieved using Facebook Likes. In order to cope with those problems several approaches uses randomization and cryptographic techniques ( [START_REF] Polat | Svd-based collaborative filtering with privacy[END_REF], McSherry and Mironov, 2009a, Erkin et al., 2011, Dwork, 2008, Berkovsky et al., 2007, Shokri et al., 2009, Aïmeur et al., 2008[START_REF] Mcsherry | Differentially private recommender systems: Building privacy into the netflix prize contenders[END_REF]) to trade off between privacy, accuracy, and efficiency. Another solution is user-centric solutions. For instance [Canny, 2002] relied on a model where item latent factors are first locally downloaded by the user, then her own machine performs relevant computation according to its locally stored information in order to find the items that should be recommended to her. After interacting with the system, updates are done using encryption techniques. However such solutions can hardly be used in practice because of very large catalog size which prevents computation from being done on the user's machine and because of product availabilities that evolve almost in real time, and thus that require frequent calls to an external server to get such information.

Outside machine learning research, some commissions exist to try to guarantee user's privacy and rights or at least regulate how data is gathered and exchanged. In France this role is led by the CNIL (Commission Nationale de l'Informatique et des Libertés or National Commission of Informatics and Freedom) and has six main missions: inform, regulate, protect, control, sanction and anticipate. The Federal Trade Commision is the American counterpart but is not focused solely on informatics since its main mission is the promotion of the consumer protection in general. More recently, European Union developed a General Data Protection Regulation (GDPR), released in 2018, to define a set of text laws focusing on personal data processing in order to provide data protection and privacy for all individuals inside the European Union (not only European Citizens). We can also cite e-Privacy, a European text regulation released in 2002, specific to online data and more precisely cookie management.

Filter bubble issues

Filter bubble is a term coined by the internet activist Eli Pariser in 2010 [Pariser, 2011]. In his book he argues that with recommender systems like Google, Facebook or Yahoo, users experience a very personalized content that is different from everyone else. This creates a unique filter bubble for everyone that is invisible and hard to escape from. Such critics have also been raised for the US 2016 election of Donald Trump ( [Baer, 2016], [Jackson, 2017], [Hern, 2017]). Those articles claim that users with similar opinions as a candidate will only see news in favour of this candidate and will therefore reinforce their opinion. Besides if their candidate loses, they will not see the defeat arrive since they only saw articles communicating positively about this candidate. Unfortunately little research has been dedicated to investigate this question. Indeed today's research is mainly driven by available data where filter bubble is difficult to test. To the best of our knowledge, the only study on the filter bubble's impact on diversity has been made by [START_REF] Nguyen | Exploring the filter bubble: The effect of using recommender systems on content diversity[END_REF]. In this article, authors use the movieLens dataset where one can have access to which movies have been recommended to which users. They then defined a methodology to measure the impact of the recommendation on the user content diversity and satisfaction comparing group of users that used the recommendation with a similar strength. Surprisingly, the narrow effect has been observed not only for users that used the recommender systems but also for users who did not and the diversity reduction was lower for user that used the recommender system than for others. However the movieLens website is quite particular since it is not a consumption website but only a rating platform where it is impossible to know if a user rated a movie because she just watched it or because she thinks of rating it now but watched it a while ago. Integrating filter bubble consideration into every day recommender systems in production would be an interesting step. Coping with filter bubble remains an issue that recommender systems should address. This can be done by introducing diversity in the proposed items at the recommendation time.

For instance a solution is to compute a trade off between the item relevance and its similarity with previously displayed items. Similarly, selecting globally diverse sets of items is studied using mathematicals tools borrowed from statistical physics used to model repulsion between particles. Finally, improvement can also be done on the transparency of the user interface that could indicate the level of similarity of an item with a previously consumed one and highlight dissimilar ones, but this could also come with a performance cost that the company may not be willing to take.

After working at fifty-five, first as an intern then full time, I became quickly interested in the user personnalization problem. However facing real world application constraints, those limitations prevent me from efficiently applying state-of-the-art solutions. Extending state-of-the-art solution to match industrial constraints and objectives was then a main motivation and focus of this work. Consequently the starting point of all reflection was fifty-five available data, the data distribution and the production constraints. In following contribution we will then highlight in a decicated section the industrial learnings that this work brought.

Recommender Systems

Machine Learning in Recommender Systems

Broadly speaking, the objective of recommender systems algorithms is to present relevant items to users where relevance can have two different meanings. The first one is measured in terms of affinity, thus the goal is to show item(s) that users may like. The second one is measured in terms of coherence with other items that users will consume together. The main difference from a data perspective is that affinity will be captured based on all the interactions between users and items no matter when they occured, while for coherence the algorithm will focus on co-occurence for instance in the same session for web application. Both objectives require past data in order to learn relevance of items in each context in order to present those items to users. Thus future data will directly depend on the recommender system past choices which can bias future learning. To avoid such problem, recommender systems must balance between exploration, that is testing different possibilities to gather new information, and exploitation, that is acting according to previously gathered data. Bandit learning provides a framework in order to effectively balance exploration and exploitation.

On predicting user-item affinity

In order to predict future user-item affinities, algorithms rely on any available information on users and items: this could be any kind of contextual information like age, gender, genre, date, or previous user-item interaction. Once the model is learned, the system outputs the affinity between one user and either all possible items or only items unknown to the user and picks the best one(s), that is the one(s) with the highest affinity. Indeed, for some applications, like movie recommendation, it does not make sense to recommend a movie that the user has already seen and rated in the past, thus the recommendation will focus on selecting new items. In other applications, like music recommendation or restaurant recommendation, the system may recommend a previously known item if it is predicted to be the most suitable at the current moment.

There are three families of recommender systems that depend on how the algorithm learns affinities between users and items:

• content-based model (see figure 2.1a): user and item are characterized by contextual knowledge. For instance a user is defined by its gender, age, town of residence, occupation, ..., and an item by its color, shape, recency, ...,

• collaborative filtering (see figure 2.1b): user (respectively item) is characterized by the items they interacted with (respectively users that interacted with it),

• hybrid model: mix several models together.

Content-based

Content-based models ( [START_REF] Pazzani | The adaptive web. chapter Content-based Recommendation Systems[END_REF]) are simple models to perform recommendation. Any supervised learning techniques can be used in order to perform the recommendation. In supervised learning one assumes that there is a functional relationship between the output Y (or the endogenous variable) and the input X (or the (explicative) variables, the exogenous variables), this function being noted f * . The goal is to find the best approximation f ∈ F, with F a set of possible functions, of the function f * based on past observations, i.e the training set, (X train , Y train ) ∈ R n×p × R n , with n the number of samples and p the number of variables, that is one must solve:

f = arg min f ∈F d Y train , f (X train ) (2.1)
where d is a distance function.

For recommender systems, the output variable is the feedback provided by a user on an item and the input variables are the descriptive vector of the user and x y male female age action thriller drama romantic output 1 0 32 0 1 1 0 3 These models present the advantage of being very simple, easy to interpret and and easy to implement by leveraging available supervised learning libraries and techniques. Furthermore, for web applications, the user's information can easily be stored in a cookie and has the advantage of being fix in time (or at least do not change very quickly like age) thus real-time prediction is made easier. In practice content-based methods are used in specific cases when many users have provided little feedback on items, when rich contextual information is available for users and items, or when computing individual predictions is not possible because of timeresponse constraints. In many e-commerce applications, there is not that much contextual information available on products. Price, discount, color, brand and few product categories are available, but this is still too little to learn a model using just those information. To overcome this problem, deep learning is frequently used to compute latent descriptors of the product image and/or the product text, which results in a good item descriptor [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], Le and Mikolov, 2014, Vasile et al., 2016]). For users on the contrary, there is not much to be done and contextual information is often lacking. One can have access to device information, but not much more, which limits the interest of such algorithms. However there exist specific cases where using a content based algorithm is a good solution and is almost the only one: when user-item interaction is very rare but very meaningful, the catalog is quite small (hundreds of items) and a lot of contextual information are available on both users and items. Applications where all those criteria are met are the luxury and the automobile industries. For instance in automobile, brands have years of data on users with detailed contextual information, users have bought very few cars during those years but each purchase is very meaningful and lots of information are available on each car. On the other hand, in online applications collaborative filtering and hybrid methods usually provide better performances.

Collaborative Filtering

In Collaborative Filtering [START_REF] Schafer | The adaptive web. chapter Collaborative Filtering Recommender Systems[END_REF], Ekstrand et al., 2011]) no contextual information about users and items is assumed. Users are only defined by the items they interact with in the past and items by the users who interacted with them. This "definition" is much more precise and personalized than content-based methods since users are defined by their own personal tastes instead of descriptive features chosen by a human designer. The drawback is that the system needs to have collected enough feedback per user and item in order to learn information more precise than classic content-based models. Those more complex algorithms bring more precise prediction but also more complicated rules and are widely studied by the machine learning community. Another drawback on collaborative filtering is that the system learns hidden (or latent) descriptors that are much harder to understand by a human. On the contrary those latent descriptors create valuable embedding of users and items that can be used for other (marketing) applications like users and items clustering. Improving and generalizing state-of-the-art performance of collaborative filtering will be one of the main points of focus of this thesis.

Early methods, detailed in section 3.6.1, were based on explicit similarity measure between either users or items. Current methods are based on matrix factorization and rank minimisation using linear algebra or probabilistic models and will be detailed in section 3.6.1 and are one of the main points of focus of current recommender system research. Taking into account more and more types of information on users and items to improve performance is also a wide research area in the recommender systems community. This leads to the third familiy of hybrid methods.

Hybrid methods

Hybrid methods ( [Burke, 2007]) goal is to mix together several models. Most of the time the goal of hybrid methods is to gather content-based methods and a collaborative filtering one to make one recommender system with the advantages of each. A simple solution consists in computing a weighted mean between a contentbased model and a collaborative filtering one. The content-based model is denoted CB and the collaborative filtering model CF such that CB(u, i) and CF (u, i) returns the affinity prediction between user u and item i for each model. A hybrid model Hy can then be specified as follows:

Hy(u, i) = αCB(u, i) + (1 -α)CF (u, i) (2.2)
where α ∈ (0, 1) is a tuning parameter that puts more or less weight to each model. But weighted hybrid methods are only one of the seven types of hybdrid recommender systems identified by the survey [Burke, 2002]. Other types are switching methods where for each prediction the system first chooses a recommendation component then applies it, mixed methods where recommendations of the different component are concatenated, features combination methods that consists in combining feature from multiple sources to create one algorithm, feature augmentation methods that create features that will serve as an input for a next model, cascade methods that prioritizes models according to a set of rules, and meta level methods where the output of a first model serves as the input of a next model. For instance, it is frequent that content-based models perform better than collaborative filtering on users and/or items with little feedback. Hence one would apply a cascade hybrid recommender system by prioritizing content based methods to predict user-item affinity with little feedback and collaborative filtering methdods otherwise. An automated solution consists in learning a new model on top of those two using any supervised learning techniques (for instance a decision tree, but in practice xgboost is often used) with the prediction of the previous models and some extra features (like the number of feedback provided by the user and on the item) as the input in order to learn to predict the true rating. This new model can now be considered as a meta-level hybrid recommender system that will distribute the weight among the different previous algorithms. Combining models effectively has proved with the Netflix challenge to lead to very effective recommender systems but also much more complicated ones since several models must be computed and combined before making a recommendation. As discussed in the previous section, deep learning techniques are now the state of the art to get better feature representation to be integrated into feature augmentation hybrid recommender systems [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], Le and Mikolov, 2014, Vasile et al., 2016]).

On predicting sets coherence

The main objective of predicting sets coherence is to suggest a new item for a user to add to her cart, that is to increase the value of users already well engaged with the brand but can also be used to generate set of items to be consumed together like a music playlist. This particular recommender systems problem belongs to the more general framework of session-based recommender systems which define all recommender systems designed at the session level. Session-based recommender systems have received more and more attention in the recent years, for instance in 2015 the RecSys Challenge was dedicated to session-based recommender systems. Unlike affinity based algorithms whose goal is to present one or several items that the user could buy independently, in basket completion the notion of set of items is crucial in order to present an item that is coherent with the items already in the basket since the goal is that the whole set will be purchased together.

Three main categories exist to tackle the basket completion issue: associative classification, collaborative filtering variations and Determinant Point Processes. Besides, more recently deep learning techniques have been developed using recurrent neural network [START_REF] Hidasi | Session-based recommendations with recurrent neural networks[END_REF]).

Associative Classification

Associative Classification ( [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], Hipp et al., 2000, Liu et al., 1998]) are simple methods that are based on association rules that compute sets supports to perform recommendation. The general idea is to count co-occurences of two sets using all past observed baskets in order to find the most frequent associations compared with the occurence of one of the two sets. Then, if this occurence ratio is high enough, the second set is considered to be a good recommendation when the first set is in a user basket. However, relying only on such a ratio may reduce to recommending only must popular items. Additional criteria are then defined to produce different rules that will define what to recommend.

Such approaches have several strong limits: the different criteria are arbitrarily defined and require a manual choice of thresholds, like the minimal value of the two sets co-occurence over one set occurence ratio, the impossibility to scale to large dataset and finally the necessity to update all previously computed rules whenever a new basket is observed, which can be very time consuming.

Adaptation of Collaborative Filtering

In order to scale to large item catalogs, a solution can consist in using collaborative filtering by considering each basket as one unique user. However in applications where baskets are very small (for instance in e-commerce it is very rare that people buy more than three products at the same time) the extreme sparsity of the matrix can prevent from learning correclty. Another solution consists in using the item latent factors obtained by the collaborative filtering algorithm in order to compute item-to-item similarities using for instance the cosinus between the two items. Then the most similar item is proposed to the user. The limit of such an approach is that recommending similar items may not be relevant since people are more likely to buy complementary items instead of two very similar ones. To that extent, people often add constraints to the recommendation like forcing the additional item to recommend to be in a different category than the initial item ( [START_REF] Teo | Adaptive, personalized diversity for visual discovery[END_REF]).

Determinantal Point Processes

More advanced methods based on Determinantal Point Processes (dpps) ( [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], Gartrell et al., 2016]) have shown very good accuracy and improved diversity in the recommendation. Determinantal Point Processes are probability measure over set of points defined by the determinant of a kernel matrix of the size of the item catalogs where each entry (i, j) of the kernel matrix encodes the similarity between product i and j. Based on past observed baskets, the kernel matrix of the dpp is learned, using for instance maximimization of the likelihood, and items to recommend are sampled from the obtained probability distribution. In order to scale to large item catalogs, [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], Gartrell et al., 2016] assumed a low rank constraint on the kernel matrix. This assumption proved to be both more effective to learn and predict and also produced more accurate recommendations.

Effective exploration-exploitation with bandit learning

When future observation directly depends on the output of the system, one must take care of the exploration vs exploitation dilemma in order to collect new information while also providing accurate recommendation. Besides in recommender systems applications, new users and new items arrive frequently and exploiring those users and items must be done appropriately. Recommender systems then leverage results and solutions from multi-arm bandit to solve this issue.

Multi-arm bandit

The exploration-exploitation dilemma is studied in the reinforcement learning theory and more specifically in the multi-arm bandit theory. Concretely the problem is to select the next action a (called arm, which in our case corresponds to an item) within a set of possible actions A in order to maximize the cumulative reward (i.e., the sum of the previously collected rewards) on the long term rather than maximize the immediate next step reward. Each arm is characterized by an unknown distribution and at each step the system observes the reward of the pulled arm.

A simple solution to introduce exploration in the system is to pull an arm at random a small fraction of the time and pull the best expected arm the rest of the time. This strategy is called ε-greedy where ε stands for the small fraction of time that random pulling is used, in practice ε ≈ 1%.

A more advanced solution is to use the Upper Confidence Bound (ucb) algorithm ( [Auer, 2003]) that follows the optimism in face of uncertainty principle to select the next arm that increases the chance to select an arm with a lot of uncertainty. Intuitively when pulling the arm which in the best case scenario has the highest reward, there are two possible outcomes: either we did select the best arm and so we are good, either we did not and we gain knowledge on a good candidate. On the contrary a greedy strategy could stop pulling the best arm because of a few bad results in the first attempts. More formally, the ucb algorithm pulls at time t the arm I t that follows equation 2.3.

I t = arg max a∈A μa,s + 3 log t 2s (2.3)
where s is the number of times arm a has been pulled before time t and μa,s is the empirical mean rewards observed by pulling arm a. This equation comes from a high-probability upper bound on the expected reward of each arm. See figure 2.2 for an illustration of ucb state at a given time step.

A similar approach can be developed in a bayesian framework using Thompson Sampling [START_REF] Kaufmann | Thompson sampling: An asymptotically optimal finite-time analysis[END_REF], Russo et al., 2017]). In such a framework one assumes that the reward obtained by pulling an arm follows a certain distribution with unknown parameters. At each time step, for each arm, a reward is sampled according to the current estimation of the distribution, and the arm with the highest sampled reward is pulled. Then its distributions parameters are updated following Bayes' rule, and one moves to the next step.

In this multi-arm bandit framework all arms are independent from each other, thus pulling one arm does not provide any information on the other arms performance which can be an issue when dealing with a lot of arms. Linear bandit allows to overcome this problem.

Linear bandit

The multi-arm bandit framework has then been extended to linear problem where each arm is defined by a vector x a ∈ R d . After each pull the system observes the reward r a =< θ * , x a > +η of the pulled arm, where θ * ∈ R d is an unknown parameter common to all arms and η is a conditionally R-sub-Gaussian noise, see [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], [START_REF] Li | A contextual-bandit approach to personalized news article recommendation[END_REF]. In such a model, pulling any arm gives information on all other arms thanks to the common parameter θ. Then similarly to UCB for multi-arm bandit, one can compute a confidence ellipsoid on θ in order to obtain a confidence interval on rewards and pick the arm with the highest upper bound.

Similarly to multi-arm bandit, one can use Bayesian ideas for linear bandit. [Agrawal and Goyal, 2013a] analyzed generalization of Thompson Sampling to linear bandit in algorithms called linear Thompson Sampling or Thompson Sampling for Contextual Bandits.

Bandit in recommender systems

In recommender systems application, linear bandit can be used in content based models where items are the arms of the bandit, and x a represents the contextual information of a particular item. However learning a linear bandit per user can be very uneffective. To that end [Li et al., 2010c] propose a hybrid version of linear bandit where the reward is the aggregation of two linear terms: a first one with a contextual vector that jointly represents user and item weighted by an unknown coefficient common to all items and a second one with a contextual vector containing user features only weighted by an unknown coefficient different for each item. On the other hand, [START_REF] Cesa-Bianchi | A gang of bandits[END_REF] build upon linear bandit and assumed the existence of a user social graph in order to share information among each user linear bandit.

On some applications, it is frequent that the system must recommend several items at the same time. The user sequentially examines each item one after the other and clicks on the first one she likes. This problem, called cascading bandits, was studied by [START_REF] Zong | Cascading bandits for large-scale recommendation problems[END_REF] using UCB and Thompson Samping like algorithms for multi-arm bandit and using linear UCB and linear Thompson Sampling like algorithms for linear bandit.

Using collaborative filtering, [START_REF] Guillou | Large-scale bandit recommender system[END_REF] relied on ε-greedy method to perform exploration in their recommendations, whereas [START_REF] Mary | Bandits warm-up cold recommender systems[END_REF] adapt linear bandit to select item to recommend in applications where each item can be recommended several times to the same user.

Measure, performance and open datasets 2.2.1 Measure and performance

Evaluating the performance of a recommender system is not straightforward. Ideally one would like to A/B test the system, that is (version A) a certain portion of users see products chosen by the recommender system and others (version B) according to an other rule (random, popularity, a different recommender system), to assess which version is the best all other things being equal. But, as for any machine learning solution, one would rather have an offline evaluation protocol before testing any solution live. The classic supervised learning approach consists in selecting at random a fraction of the input data to train the model and to evaluate the model precision on the remaining data. Applying this protocol several times and computing the mean precision over all the different tests, gives a good idea on the model precision. This offline evaluation protocol, called K-cross validation, where K stands for the number of times this protocol is performed, is very classic in supervised learning, but must be executed carefully for recommender systems. In classic supervised learning settings, there are two possibilities (see figure 2.3) to perform K-cross validation. The first one consists in partitioning the input dataset into K non overlapping subsets, learning the model on K -1 subsets and computing the difference between the true value in the left subset and the predicted ones. A second option is to learn the model on x% of the input chosen at random and measure the performance on the left (100 -x)%. However directly applying one of those two solutions can lead to some issues for recommender system offline evaluation. Indeed, when selecting input at random, some users (resp. items) may never be selected in the training set, thus making the prediction infeasible for those users (resp. items).

A possibility could be to remove users and items with little feedback from the whole dataset. This option is often criticized because it is considered as removing hard entries and thus keeping only the easy ones. However, it depends on the goal of the recommender system: if the main goal is to improve accuracy on users and items with sufficient knowledge, that is finding the best model on "warm" users and items, it makes sense; on the contrary if the main goal is to find the best global model it does not. A solution consists in selecting for each user x% of its feedback at random and at least one (some users may have only one feedback in the dataset) and likewise for items. The union of this sub-selection for each user and item forms the final training set and the remaining values define the test set. This protocol, called stratified cross validation, ensures to have feedback for each user and item.

We will refer to this version as stratified cross validation. However this selection is still not perfect since there could exist time bias in the provided feedback: users' future ratings can depend on previous ratings, thus having ratings in the training set that are posterior to ratings in the test set could lead to bias the model and to a poor generalization performance in real applications. Thus a more appropriate splitting protocol would be to remove last rated items for each user. Once the training set and test set are obtained and the model learned, an error measure has to be chosen to define the precision. At the beginning, recommender systems used to be evaluated according to the Root Mean Squared Error (RMSE), as it is often the most adequate performance measure in supervised learning. Let note T the set of prediction to make, the RM SE is

RM SE . = 1 |T | i∈T (y i -ŷi ) 2 (2.4)
where y i is the true value of the i th observation and ŷi is the prediction according to the learned model. However in most applications the system will choose only K items to recommend, and the RM SE does not gives guarantees on the relevance on those K recommended items. In such application the real goal is to preserve the preference ordering of each user and especially for the items that the user likes the most. Indeed, two models with the same RM SE can have (relatively) different items ordering and thus two really different performances in practice. Suppose that the true ratings for a user are 3; 4; 1; 5. If model 1 predicts respectively 3.4; 3.3; 1; 4 and model 2 predicts 2.6, 3.3; 2; 5, both models have a RM SE = 0.4125 but only model 2 preserved the right order and thus will provide the best possible top-K recommendation. There exists lots of more suitable metrics for such applications that compute the ordering of the prediction instead of the value predicted, like Kendall's τ , Spearman correlation and other many classic correlation measures. In the recommender systems field a classic measure is the rank measure that weights the ordering of the predictions according to the true feedback:

ρ . = u,i∈T r u,i ρ u,i u,i r u,i , (2.5)
where ρ u,i denotes the percentile-ranking of the item i of all items previously seen by user u ordered according to the predicted values from the most suitable item to the least suitable one, and r u,i the true feedback. For instance, if item i is predicted to be the most (resp. the least) suitable for user u, then ρ u,i = 0% (resp. ρ u,i = 100%).

If the predictions are made at random, the expected rank-measure is 50%. Low values of ρ indicate that most of highly seen items have been predicted to be the most suitable and thus correspond to a good recommendation. On the other hand, ρ above 50% means that the algorithm is no better than a random strategy. Another popular evaluation measure, commonly used in information retrieval, is the DCG@k for Discounted Cumulative Gain at k:

DCG u @k . = k i=1 2 rel u,i -1 log 2 (i + 1) (2.6)
where rel u,i is the relevance of the i th recommended item for user u, that is in our case the true feedback. This function measures the relevance of the top K recommended items for a user, and then only focuses on the top of the list. This measure is particularly interesting for recommender systems since the user interacts with top products, and thus we want to know how relevant top predictions are, no matter what the other ones are. However this measure is not consistent through users that may have different test set lengths or rating behaviours. We thus use the NDCG@k, the Normalize Discounted Cumulative Gain, where the DCG@k is divided by the best value of DCG@k that is when the items are in the best possible order, also called the Ideal DCG (IDCG):

N DCG u @k = DCG u @k IDCG u @k (2.7)
Computing the mean N DCG u @k over all users gives the global performance of the model: N DCG@k = mean u N DCG u @k.

In the particular case of K = 1 two others measure are often used: the Mean Percentile Rank (MPR) and the Precision at k (precision@k), where here k denotes the top k predictions. The MPR measure sorts all possible items to recommend to a user u according to their predicted scores and output the percentile rank (PR) of the item j u , where j u is the item the user actually consumed, among candidates items C -that is items that have not been consumed by the user -that the user actually consumed:

P R ju = i∈C I(r u,ju ≥ ru,i ) |C| × 100%, (2.8)
Taking the average over all users in the set set T gives the mean percentile rank

M P R = u∈T P R u,ju |T | (2.9)
A M P R of 100% means that the actual consumed item always gets the highest score, and a M P R of 50% corresponds to a random model. Finally, the precision@k counts how many times the target item was in the top K predicted ones. Let note rank u,ju the rank of the target item j u of user u, thus

precision@k = u∈T I(rank u,ju ≤ K) ju 1 × 100%
(2.10)

A common limit to all offline evaluation mesures is that they can only be computed on observed ratings which introduces a bias because ratings are missing not a random. Indeed in most available datasets, available ratings are ratings that users deliberately decided to rate and have a different distribution from missing values. [Steck, 2013] worked more in details on this problem and thanks to Yahoo! Music data that explicitly asked users to rate some songs at random and emphasized this bias: the average rating of randomly selected songs is 1.8 whereas the average rating of deliberately rated ones is 2.9. Consequently a model with a low test set RMSE may not achieve a low RMSE on the whole possibilities. More problematic, the system that achieves the best performance on observed ratings may not be the one that achieves the best performance on all the possibilities and thus should not be used in pratice (see Table 1 of [Steck, 2013]).

The metrics introduced above only measured the current precision/performance of the model according to the current state of users and can be suitable to measure the performance of the system in a particular setting, for instance on little engaged users. However in some applications one can be interested in the dynamic of the algorithm that is its ability to produce recommendations that both please the users and collect valuable feedback for future prediction. For instance for a cold user, the systems may provide poor recommendations at the beginning but acquire very informative feedback that will produce good recommendations on the long term. This can be measured by the cumulative reward that is the sum of feedback received after each recommendation up to time t:

cum reward u (T ) t = T k=t+1 r u,i(t)
(2.11)

where i(t) is the t th recommended item to the user. In practice measuring the cumulative reward on offline data is complicated. Indeed one must have access to the rating that the user in the test would have given to the item recommended by the system, which may not be available. The first trick consists in updating the model if and only if the recommended item for a given user was indeed available in the dataset. This strategy called replay has been studied by [Li et al., 2010a] that proved that it was an unbiased offline evaluation when the data stream was infinite and when the logging policy, that is the way data was actually collected, picked arm at random. The second trick consists in keeping in the test set only users with the highest amount of feedback in order to reduce the risk of not having the observation. However this second trick can create bias since very engaged users may have a very different behaviour from the rest of the world. Another direction consists in building a simulator. The idea is to first estimate the reward of each arm according to all available data. Then those estimates are supposed to be the actual reward (plus some noise) that one would get when pulling each arm. Then, to test the policy, the system starts with an empty history and picks an arm according to the policy to test. A reward is then sampled according to the previously computed simulator and the system is updated. In practice, constructing a simulator can be difficult and requires a large history in order to have an unbiased estimator.

All those error metrics only measure some definition of the accuracy of the recommender system, however in practice one may be interested in other performances. For instance the diversity of the recommended items introduced by the system can be a desired criterion as well as the novelty of the system that is the capacity of the system to recommend items that are new to a user, or the catalog coverage that measures the proportion of the catalog that is actualy recommended, and the serendipity that defines the fact of being both useful and unexpected. Obviously it is impossible to simultaneously maximize accuracy, diversity, novelty, coverage and serendipity and each measure is not necessarily positively correlated to the real online performance of the system. [START_REF] Maksai | Predicting online performance of news recommender systems through richer evaluation metrics[END_REF] proposed a model to link the online performance to all those different performance measures in order to help decision makers to decide what model to test online.

To sum up, in recommender systems experimental protocol definition plays an important role in the model evaluation from the train-test split to the choice of the performance measure and must be done carefully and according to the desired application goal.

Available datasets

A limited number of open datasets are available for everybody to evaluate and compare their own models with the state of the art on a common basis. These different datasets allow to test different objectives and assumptions. Here is a nonexhaustive list of some useful ones.

• MovieLens [START_REF] Harper | The movielens datasets: History and context[END_REF]: There exist five differents Movie-Lens datasets containing either 100k, 1M, 10M , 20M and more than 20M (frequently updated) movie ratings. Each dataset contains 4-tuple (user id, item id, rating, timestamp) as well as user and item contextual information like gender and genres.

• Last.fm [Celma, 2010]: Several music datasets are available with Last.fm.

A first sparse one is formed of 1k users listening history with timestamp, artist and song resulting in around 19k rows, and a second denser one of 360k users resulting in around 17k rows. An API is also available to obtain extra information like song tags.

• Yahoo [yah, 2013]: Eight datasets containing ratings are available on Yahoo's website. Four datasets contain ratings on music on different time periods and sizes (from several thousand to a few millions of users). One dataset contains movies ratings, one bookmarked website on del.icio.us website and two datasets contain clicks on Yahoo! front page today module.

• Yoochoose [START_REF] Ben-Shimon | Recsys challenge 2015 and the yoochoose dataset[END_REF]: This dataset was realeased during RecSys 2015 Challenge and is formed of two files extracted gathering event from an unknown e-commerce website of more than 9M sessions. The first one contains click events with a session id, a timestamp an item id and an item category. The second one contains buy events that is price, timestamp and quantity of the bought item id of a given session id.

• Netflix [START_REF] Bennett | The netflix prize[END_REF]: Released for the Netflix Challenge, this dataset is no longer public since the closure of the challenge. More information on this challenge is provided in the following section.

• Amazon Baby Registries [START_REF] Gillenwater | Expectation-maximization for learning determinantal point processes[END_REF]: is a public dataset consisting of 110, 006 registries of 15 disjoints registry categories like diaper, apparel or feedings, with 100 items per category. The categories are disjoints meaning that a basket with products of one category cannot contain products of another category. The average basket size in one category is between 2 and 3 depending on the category.

• Belgian Retail Supermarket [START_REF] Brijs | Using association rules for product assortment decisions: A case study[END_REF]: is a public dataset that contains 88, 163 sets of items that have been purchased together, with a catalog of 16, 470 unique items. Each basket contains 9.6 items on average.

• UK retail [START_REF] Chen | Data mining for the online retail industry: A case study of rfm model-based customer segmentation using data mining[END_REF]: is a public dataset that contains 22, 034 sets of items that have been purchased together, among a catalog of 4, 070 unique items. This dataset contains transactions from a non-store online retail company that primarily sells unique all-occasion gifts, and many customers are wholesalers. Each basket contains 18.5 items on average, with some very large baskets.

• Instacart [ins, 2017]: is, as far as we know, the only public dataset that contains the order in which the product have been added to someone basket.

It is formed of three datasets containg online grocery shopping of more than 200, 000 Instacart users: a "train" dataset with around 131, 000 baskets, the last basket of each user, a "prior" dataset with all past baskets for each user (around 3.2 millions baskets) and a "test" dataset with around 75, 000 baskets reserved for machine learning competitions. All those orders are made on approximately 50, 000 products and each basket contains 10.5 products on average.

As seen previously, recommender systems rely on past feedbacks to provide personalized recommendations. The feedbacks may take different forms, such as the rating of a movie, or the number of times a user listened to the songs of a given music band. Improving precision and theoretical guarantees of recommender systems has been widely studied in cases in which users can provide a single type of feedback on items. Nonetheless, in some situations, the user can perform several actions on each item, resulting in a multidimensional feedback (e.g., the user of an e-commerce website can either click on a product, add the product to her cart or buy it). However state-of-the-art algorithms rely on matrix factorization where each row of the matrix represents a user, each column an item and each entry is either empty or contains the corresponding feedback. In the case of multidimensional feedback, such algorithms can not be applied any more, unless the problem is reduced to a series of multiple independent problems, thus loosing the correlation between the different actions. The most suitable approach is to use a tensor approach to learn all dimensions of the feedback simultaneously. In this section, we propose a specific instance of tensor completion and we show how it can be heavily parallelized over both the dimensions (i.e., items, users, actions) and within each dimension (i.e., each item separately). We validated the proposed method both in terms of prediction accuracy and scalability to large datasets.

Introduction

The aim of personalized recommender systems (RSs) is to discover the preferences of each user and to predict which items, among those available in the system, she likes the most. The collaborative filtering approach [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF], Zhou et al., 2008, Koren et al., 2009, Mackey et al., 2011, Salakhutdinov and Mnih, 2008] relies on user-item interactions to infer implicit descriptions suitable for prediction. Since its success in the Netflix Prize competition [START_REF] Bennett | The netflix prize[END_REF], one of the most popular collaborative-filtering method is based on matrix factorization techniques for latent factor models. In this approach, the recommender system problem is reduced to the problem of completing a highly sparse user/item matrix (i.e., each entry records the feedback of the user for a specific item) under low-rank assumptions, where rows refer to the users and columns refer to the items available in the system. In general, the feedback can be either explicit (e.g., a rating on a scale from 1 to 5) or implicit (e.g., number of views, number of times a song is listened to, number of clicks).

Despite its success, matrix factorization cannot always capture the full complexity of the problem. In several domains, users can perform several actions on the items. For instance, in e-commerce applications, while the user-item affinity is often predicted on the basis of the number of times the user clicked on the item, the action one would like to predict is whether the user will actually add the product to her cart and/or buy it. Unfortunately, these actions are much sparser than the clicks, thus far more difficult to predict, and they are not necessarily positively correlated with them, so predicting clicks will not make an effective recommender system. As a result, applying matrix factorization only on the click action may result in poor recommendation for the actual actions of interest (i.e., buy). Indeed, a high number of clicks on a product may not mean that the user is really interested in the product but rather that she is hesitant. Another scenario in which matrix factorization is not satisfactory is for recommender systems where the recommendation needs to be related, e.g., with a specific moment of the day or the season. For instance, previous studies on music recommendation [START_REF] Baltrunas | Towards time-dependant recommendation based on implicit feedback[END_REF] have shown that people listen to different artists depending on the moment of the day or of the week (while working, driving, resting at home). Again, ignoring this dimension and applying matrix factorization directly on the user-item matrix, may severely affect the final performance of the system. Of course all those actions can also happen in the same time, one may want to take into account the "add to cart" based on the day of week or the season of the year resulting in a three dimensional feedback.

An effective approach in case of multidimensional feedback is to use tensor factorization techniques, which extend matrix factorization by taking into consideration all actions/contexts at the same time. In particular, the user-item matrix is expanded by adding one or more modes, which contains the additional type of actions available, like the number of clicks, add to cart and purchase of each item. Tensor factorization is considerably more complicated than matrix factorization and it requires extending previous methods. [START_REF] Symeonidis | Tag recommendations based on tensor dimensionality reduction[END_REF] rely on a generalization of the singular value decomposition for tensors called higher-order singular value decomposition (Hosvd) introduced by [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF], and it is part of the general family of Tucker decomposition. In Hosvd, the n-order tensor is unfolded into n matrices on which classic svd is applied. Its decomposition is then used to reconstruct the full tensor factorization. An alternative approach is to perform tensor decomposition using PARAFAC (parallel factor analysis). For instance, [START_REF] Hu | Personalized recommendation via cross-domain triadic factorization[END_REF] performed cross-domain recommendation using an alternating least squares algorithm on the PARAFAC model called cp-als-r (PARAFAC is also called CANDECOMP, that is what the CP stands for here). However, recommendation problems always come with missing values (otherwise there would be nothing to learn) and this problem has not been taken into account neither in cp-als-r nor Hosvd. This problem has been studied for tensor decomposition for instance in the chemometric field for the PARAFAC decomposition [Acar et al., 2010, Tomasi andBro, 2005] and the Tucker decomposition [START_REF] Filipović | Tucker factorization with missing data with application to low-n-rank tensor completion[END_REF]. Finally, [START_REF] Romera-Paredes | A new convex relaxation for tensor completion[END_REF] studied the tensor completion problem not with tensor factorization but working on the trace norm regularization and introduced a new convex relaxation method for tensor completion. Unfortunately, most of these techniques suffer from different shortcomings when applied to recommender systems: 1) they may not properly manage missing values (i.e., by filling unknown feedback with arbitrary values), 2) they do not allow for modes with latent factors of different sizes (i.e., constraining to a single dimension for all factors), 3) they do not scale to large tensors (both in size and number of modes) because of algorithm complexity and storage issues.

Contributions. In this chapter, we focus on an adaptation of the alternating least squares approach used in matrix factorization. In dealing with matrix factorization for recommender systems, alternating least squares with λ regularization (als-wr) introduced by [START_REF] Zhou | Large-scale parallel collaborative filtering for the netflix prize[END_REF] proved to perform much better than svd. While both approaches assume a low-rank constraint on the matrix, they differ in the way they deal with unknown values. While svd implicitly sets all unknown values to 0, the als-wr minimizes the 2 -norm error between the true feedback and the factorized matrix only for the available entries, so no assumption is made on the unobserved values. If all unknown values are set to 0, meaning that unknown feedback is equivalent to a negative feedback, the best factorization of the input matrix into two rank-k matrices in the Frobenious norm sense is given by the svd algorithm. However, when the sparsity level of the input matrix is very high, such an hypothesis introduces a large bias which prevents the svd algorithm to find a good factorization. Besides, the als-wr also introduces a penalty term based on Tikhonov regularization which penalizes large parameters in order to prevent from overfitting. This regularization is further weighted based on the number of feedback provided by a user and the number of feedback received by an item. This simple modification showed much better performance in practice since it puts different regularizations on users and items based on the size of their history in order to have a stronger regularization on very popular items and very engaged users that are more likely to be overfitted. It also helps generalisation since the regularization parameter will automatically be adjusted for each user as soon as she provides a feedback. Building on this observation, we study a method called Hoals, for Higher Order Alternating Least Squares, that leverages alternating least-squares to perform tensor factorization. Aside from being better designed for recommender systems, we Figure 3.1: Example of the input matrix in recommender system with a sparsity level of 90%. Each row represents a user, each column an item and each square the feedback. White squares are missing value, the darker the higher the affinity is.

prove that Hoals can be easily parallelized both over tensor modes and within each dimension, thus allowing it to be applied to large recommender systems. Finally, we showed that the Hoals formulation allows us to manage implicit feedback along the line of [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF]. To the best of our knowledge, Hoals is the only tensor factorization model that allows to perform tensor factorization for implicit feedback, that is able to deal with missing data and is scalable to large problems.

Background

Recommender Systems as matrix completion

State-of-the-art methods focus on the problem of filling the sparse input matrix R ∈ R n×p , with n the number of users and p the number of items, see figure 3.1, according to the known entries of the matrix. Each row represents a user u

∈ U = (1, . . . , n) . = [n], each column an item i ∈ I = (1, . . . , p) . = [p]
and each entry r u,i , if available, the user-item affinity. We denote D = {(u, i) such that r u,i is known } ⊂ U × I. In practice the matrix is highly sparse, for instance the matrix on the Netflix challenge has only 1.2% available entries. The matrix completion problem in recommender system is particularly difficult because unlike image completion one

𝑅 𝑈 𝑉 = 𝑝 items 𝑛 users 𝐾 𝐾 × Figure 3.2: Matrix Factorization.
can not use local information since the rows and columns ordering is random and available input is not uniformly distributed. Indeed some items are very popular and will have been rated by many users when some others will be almost never rated which can results in having some blank area very difficult to fill appropriately. This behaviour is called MNAR for Missing Not At Random. Learning is then performed by minimizing some distance between the model predictions and the available entries. However some structure assumptions on the matrix are required otherwise any matrix that has the exact same values at the known coordinates and random values elsewhere will have exactly zero error but no good completion can be expected. The more realistic the regularization is, the better the performance of the algorithm. A usual assumption is that the input matrix is low rank, which means that there exist some correlation among users and among items. Consequently the matrix can be factorized into two sub matrices U and V such that R = U V T where U ∈ R n×K and V ∈ R p×K has as many columns as the assumed rank K of R, see figure 3.2. U contains users latent descriptors and V items latent descriptors. The low rank decomposition has the advantage to reduce the memory since (n + p)K (with K n, p) values need to be stocked instead of np. Indeed the full matrix has never to be computed, since to decide what to recommend to one user, only its latent factors and the items latent factors are required. The problem then falls back to learning the two matrices U and V . Historically, matrix factorisation is learned through Singular Value Decomposition (svd) where only largest eigenvalues are kept, which also allows to reduce the noise that can lie in the small eigenvalues. However such techniques are not really reliable for applications with sparse matrices. Consequently, the input matrix have to be filled with arbitrary values, often zero or the mean of the available values, before applying svd, which can lead to poor performance. A better approach consists in learning the factorization using only values in D like als-wr. als-wr [START_REF] Zhou | Large-scale parallel collaborative filtering for the netflix prize[END_REF] -Alternating Least Square with Weighted-λregularization is one of the most popular collaborative filtering algorithm thanks to its high scalability and the available machine learning libraries that imple-ment this method like mahout or spark. als-wr relies on two main ideas. First, since some users provided more feedback than other and likewise some items received more feedback than others, the regularization should not be the same for each user and item but should rather depend on this number of feedback. With n u and n i respectively the number of feedback provided by user u and provided for item i, the objective function is then:

min U ∈R n×K ,V ∈R n×K u,i∈D r ui -U u V T i 2 + λ n u ||U u || 2 + n i ||V i || 2 (3.1)
We see that users with lots of feedback will have a stronger regularization than others. The second idea of als-wr is as the name suggest, to use an alternating algorithm to solve 3.1. We first fix V with small random numbers and solve the objective function on U . The problem can be rewritten as n independent penalized linear regressions (one for each user) and can be solved in parallel.

For instance, once V is fixed, the minimization problem to find the user u latent factor is min

Uu∈R K i∈Iu r ui -U u V T i 2 + λn u ||U u || 2 (3.2) thus U u = (V T Iu V Iu + λn u Id K ) -1 V T Iu R u,Iu (3.3)
Then we fix U to solve V which is again p independent penalized linear regressions, one for each item. The convergence is usually obtained within 10 or 20 steps and thanks to parallelization is easily scalable to very large problem. [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] adapt this algorithm to implicit feedback that can take very large values. Such large values can cause learning issues when minimizing the square residuals since the model will only try to fit those values and completely disregard other part of the matrix. implicit als-wr solves this problem by changing the objective function to fit the value 1 when the feedback is available, which indicate that the user likes the item, with a confidence weight proportional to the original feedback:

min U ∈R n×K ,V ∈R n×K (1 + αr ui ) u,i∈D 1 -U u V T i 2 + λ n u ||U u || 2 + n i ||V i || 2 (3.4)
where α ∈ R is a scaling weight. To prevent from fitting only positives value equal to 1, one can sample a small percentage of missing values and treat them as 0. Thus let note l ui = 1 if r ui is known, and 0 only ε% of the time when r ui is missing. We then defined

D ε = {(u, i), l ui ≥ 0} such that D ⊂ D ε ⊂ U × I. R n p q n p pq R (1) n p q q n nq R (2) n p q q p np R (3)
Figure 3.3: Mode matrix unfolding of a 3-order tensor. For instance, X 1 is the result of stacking all the lateral slices of the tensor.

We end up with the slightly modified objective function:

min U ∈R n×K ,V ∈R n×K (1+αr ui ) u,i∈D ε l ui -U u V T i 2 +λ n u ||U u || 2 + n i ||V i || 2 (3.5)

Recommender systems as tensor completion.

Here we extend the definition of a recommender system with an extra dimension A = (1, . . . , q) . = [q], the set of actions the user can take over items (e.g., a binary value such as click, add to cart (ATC), purchase, or a number as in the case of a rating), such that a recommender system is now defined as a tuple U, I, A . In the following, we only consider one action dimension, but in general other dimensions could be available. For instance, we could consider the rating attributed by a user to the food, to the service and to the decoration of a restaurant in a specific season (i.e., an additional dimension of interest) resulting in a 4-order tensor. We will use u, i, and a to index the elements in the sets U, I, and A respectively. Each feedback is a scalar value r uia ∈ R, which denotes the feedback provided by user u on item i through action a. For instance, r uia may be the rating provided by user u to the feature a of a restaurant i. Once organized along the sets U, I, A, all the possible feedback take the form of a tensor (i.e., a multidimensional array) R of dimension n × p × q. Nonetheless, only a limited number of feedback is available to the system. We denote by D ⊆ U × I × A the set of triples (user, item, action) for which a feedback is available. Starting from the feedback available for the tuples in D, the objective of a recommender system is to complete the tensor R with all missing entries and propose the best recommendations for each user. While in the case of one single action, for any user u the recommender system simply recommends the item i with the largest value r ui , when multiple actions are available, the recommender system should combine different values r uia to find a global index of preference. For instance, a recommender system can choose to recommend the restaurant with the best average rating over all features (i.e., average of ratings for the service, the food, and the decoration) or one can introduce a filtering on the rating of different actions (e.g., filter out restaurants with decoration rated less than 7/10) and then pick one according to a chosen feature (e.g., the one with the best rated food) or again compute a weighted average based on feature relevance for each user. In other cases, only one action is actually interesting, for instance buy or not, whereas other actions are only here to provide context and additional information on user-item affinity. Thus, recomendations are done by sorting the desired action prediction.

Tensor notation. In the following, we use bold upper case letters, such as X, to denote tensors, whereas matrices are denoted by upper case letters such as X. The pseudo-inverse of a matrix is denoted by X * . The entry of a third-order tensor is written with a lower case (e.g., x i 1 ,i 2 ,i 3 ) where first, second and third indices represent respectively row, column and depth (similar for matrices, x i 1 ,i 2 denotes the element in row i 1 and column i 2 ). In the general n-order tensor we may use fiber instead of row, column and depth, to denote one dimensional part of the tensor, which can not find equivalent name when n is greater than 3. A particular fiber is called mode-i. For instance, for a two-order tensor the column corresponds to mode-1 and row to mode-2. Moreover a two dimensional part of the tensor is called a slice. In the special case of matrices, we denote the uth row of X by X u . We recall some basic definitions and operations on tensors. Let X ∈ R I 1 ו••×I N be a N -dimensional tensor, we define the mode-n product of tensor X by a matrix

U ∈ R Jn×In , denoted X × n U , as the tensor of dimension (I 1 × • • • × I n-1 × J n × I n+1 × • • • × I N ) obtained as Definition 1 (mode-n product of tensor). X × n U i 1 •••i n-1 jni n+1 •••i N = In in=1 X i 1 •••in•••i N U jn,in .
The mode-n product is commutative when applied in distinct modes, i.e. for m = n,

(X × n A) × m B = (X × m B) × n A.
while for m = n we have,

(X × n A) × n B = X × n (BA).
Another important operation is the matrix unfolding of the tensor. There are N different ways to unfold a N -order tensor into a matrix called 1-mode, 2-mode,. . . , N -mode matrix unfolding. For instance for N = 3, one can stack the row, the column, or the depth as shown in Figure 3.3. In general, the d-mode matrix unfolding results in a matrix

X (d) ∈ R I d ×I 1 •••I d-1 I d+1 •••I N .
Tensor factorization. Unlike matrix factorization, tensor decomposition does not have a unique formulation and many different methods exist to recover a tensor as a combination of multiple factors (see e.g., [START_REF] Kolda | Tensor decompositions and applications[END_REF]). The two principals tensor decomposition formulations are the CANDECOMP-PARAFAC (CP for short) decomposition and the Tucker decomposition. The CP decomposition factorizes a n-order tensor into a sum of rank-one tensors. More precisely, a three-order tensor X ∈ R N ×M ×P is decomposed as

Definition 2 (CP decomposition). X = [A, B, C] = K k=1 A :,k ⊗ B :,k ⊗ C :,k , where A ∈ R N ×K , B ∈ R M ×K , C ∈ R P ×K
, K an arbitrarily chosen dimension, and ⊗ denotes the outer product. As a result, the entries of the tensor can be computed as

X ijp = K k=1 A i,k B j,k C p,k .
The minimal value of K for which such a decomposition exists defines the rank of the tensor. On the contrary, the Tucker decomposition assumes that the tensor X can be factorized as Definition 3 (Tucker decomposition).

X = W × 1 U (1) × 2 U (2) × 3 U (3)
where U (d) contains orthonormal vectors called the d-mode singular values and W is the core tensor. In general, for any d ∈ {1, 2, 3} the matrices are

U (d) ∈ R I d ×K d and the core tensor is W ∈ R K 1 ×K 2 ×K 3 , where K 1 , K 2 , and K 3 are dimensions arbitrarily chosen.
In general, computing the CP and the Tucker decompositions is a computationally challenging problem. In the next section we present an efficient parallel algorithm, called higher order alternating least-squares (Hoals), to perform the general tensor factorisation. In the following section we compare Hoals to other state of the art methods. Construct the initial (sparse) 3-order tensor R from D Initialize W, I and A with small random numbers while Not at convergence do Fix W, I, A and update U (see equations 3.9 and 3.11) Fix W, U , A and update I (see equations 3.9 and 3.11) Fix W, U , I and update A (see equations 3.9 and 3.11

= 𝐴 :,1 (I 1 × 1) + + ⋯ 𝐵 :,1 (𝐼 2 × 1) 𝐶 :,1 (I 3 × 1) 𝐶 :,𝐾 𝐵 :,𝐾 𝐴 :,𝐾 1 𝑿 𝐼 1 × 𝐼 2 × 𝐼 3 (a) CANDECOMP-PARAFAC decomposition 𝑿 = 𝑾 𝑈 2 𝑇 𝑈 1 𝑈 3 𝐼 1 × 𝐼 2 × 𝐼 3 𝐼 1 × 𝐾 1 𝐾 1 × 𝐾 2 × 𝐾 3 𝐾 2 × 𝐼 2 𝐼 3 × 𝐾 3 (
) Compute W . = R × 1 U * × 2 I * × 3 A * end while Return full tensor R . = W × 1 U × 2 I × 3 A Algorithm 2

Higher Order Alternating Least Squares

Hoals is a tensor completion algorithm suitable for Tucker or CP decomposition. While the algorithm applies for any n-order tensor, we describe it for n = 3 for the sake of simplicity. The main idea of Hoals is that the decomposition of an n-order tensor can be parallelized over each of its modes independently, thus reducing it to a series of matrix decomposition operations. Furthermore, each matrix decomposition can be further parallelized across each component. The resulting process can be easily split over multiple machines, whose jobs are completely independent and whose results are merged only at the last step. Merging only at the last step also has the additional advantage of not having to synchronize the machine that is wait other machines to finish to continue.

A recommender system is provided with a tensor R which is only partially filled with the feedback in D (i.e., feedback for triples (user, item, action)) and the objective is to construct a full tensor R with entries that are as close as possible to the "true" ones (i.e., the feedback a user would give to an item for a specific action). Similar to the case of matrix completion, this problem is ill-posed (i.e., all tensors R with the same entries as R in D are equivalent) unless constraints on the structure of the tensor R are introduced. In particular, we introduce rank-constraints in the decomposition of R either following Tucker or CP.

Following the definition of CP decomposition, we try to complete R using tensors R that can be decomposed as

R CP . = [U, I, A] = K k=1 U :,k ⊗ I :,k ⊗ A :,k ,
where U ∈ R n×K , I ∈ R p×K , A ∈ R q×K and K explicitly constraint the rank of the tensor and of the feature matrices representing respectively users, items, and actions. The entries of the approximated tensor are then

R CP uia = K k=1 U u,k • I i,k • A a,k .
Following the definition of Tucker decomposition, we work on tensors R that can be decomposed as

R Tucker . = W × 1 U × 2 I × 3 A, where U ∈ R n×K U , I ∈ R p×K I , A ∈ R q×K A are
feature matrices for users, items, and actions, and W ∈ R K U ×K I ×K A is the core tensor, which encodes the interactions between the latent factors. In this case, the entries of the approximated tensor can be computed as

R Tucker uia = K U m=1 K I l=1 K A s=1 W m,l,s • U u,m • I i,l • A a,s .
Unlike CP decomposition, in this case we have the flexibility of choosing the ranks K U , K I , and K A of each of the latent factors independently. This is particularly interesting in recommender systems where the set of users, items, and actions have different complexity and require different degrees of freedom in their description.

For instance it is frequent to have million of users, several thousands of items and around 10 actions. Once a specific decomposition is chosen, the objective is to find the tensor R that minimizes the squared loss with a penalty term related to the latent factors weighted by the number of observed interactions. For instance, in the case of Tucker decomposition we want to find the components latent factors U , I, and A and the core tensor W that minimize the following loss function Construct the initial (sparse) 3-order tensor R from D Compute the three matrices unfolding

L(W, U, I, A) = u,i,a∈D R uia -R uia 2 (3.6) + λ   n u=1 n U u ||U u || 2 + p i=1 n I i ||I i || 2 + q a=1 n A a ||A a || 2
R (1) , R (2) , R (3) In parallel apply 2 ALS-WR on R (1) , R (1) = M 1 V 1 and set U = M 1 ALS-WR on R (2) , R (2) = M 2 V 2 and set I = M 2 ALS-WR on R (3) , R (3) = M 3 V 3 and set A = M 3 Compute W . = R × 1 U * × 2 I * × 3 A * Return full tensor R . = W × 1 U × 2 I × 3 A Algorithm 4 Parallel-HOALS for CP factorization. Input: dataset D, desired rank K Construct the initial (sparse) 3-order tensor R from D Compute the three matrices unfolding R (1) , R (2) , R (3) In parallel apply 2 ALS-WR on R (1) , R (1) = M 1 V 1 and set U = M 1 ALS-WR on R (2) , R (2) = M 2 V 2 and set I = M 2 ALS-WR on R (3) , R (3) = M 3 V 3 and set A = M 3 Return full tensor R . = [U, I, A]
where n U u (respectively n I i , n A a ) is the number of known entries for user u (respectively item i, action a) in D and λ is a regularization parameter. As for als-wr this weighted penalisation allows to have stronger regularization to latent factors that have been observed a lot and thus are more likely to be overfitted.

Direct-HOALS. The loss function in Eq. 3.6 can be minimized with an alternating scheme similar to als-wr for matrix factorization (see Alg. 1). In this case, instead of repeating an alternate update on users and items only, also the action mode is updated while keeping the other two modes fixed. While a simple and smooth generalization of als-wr to tensor factorization, this algorithm, called Direct-Hoals, increases the complexity of the original als-wr by adding an update over the action mode. This process may be computationally expensive and prevent from scaling this algorithm to tensors of higher modes.

Parallel-HOALS. Instead of running als-wr over all modes iteratively, we design an alternative algorithm, called Parallel -Hoals, which runs als-wr separately on each unfolded tensor and collect its result to obtain the final tensor decomposition. The idea is to first construct the three unfolded tensors R (1) , R (2) , and R (3) and perform als-wr on each of them to find a suitable factorization of the corresponding matrix. The first factors of each of these decompositions can then be collected to construct the factorization of the initial tensor. The resulting algorithm is illustrated in Alg. 3. Despite its difference with the sequential implementation of the als-wr idea of Direct-Hoals, the following theorem shows that (the proof is reported in a later section) Parallel -Hoals returns relevant matrices in all directions. Notice that since this result applies separately for each mode it can be extended to an arbitrary number of modes and it applies to both Tucker and CP decompositions. The biggest advantage of this version of Hoals is that the three applications of als-wr on R (1) , R (2) , and R (3) can be computed in parallel. Furthermore, since als-wr itself is highly parallelizable [START_REF] Zhou | Large-scale parallel collaborative filtering for the netflix prize[END_REF], each instance of als-wr associated to any mode can be further parallelized, thus making Hoals very efficient without suffering any major overhead from the number of modes and elements in each mode. The update complexity for each event (i.e., update of the latent factor for one user, one item, or one action) for matrix

R (d) is O K d 2 n d s + K d 3 ,
(K d 2 n d s + K d 3 ) .
Additional advantages. Finally, we would like to emphasize some features that make the specific tensor decomposition in Hoals particularly suitable for recommender systems, unlike other tensor factorization methods. First, our method use Tikhonov regularization with different weights on each mode that regularized appropriately each dimension and is crucial for such application since the number of actions provided by each user can be highly heterogeneous. Second, tensor decompositions may appear difficult in practice because of memory issues that can arise from the additional modes. However thanks to its appropriate treatment of missing values and the low rank decomposition, memory is not an issue in practice since Hoals never requires to store the full tensor which is not the case with nuclear norm minimization approaches. Besides the full tensor never really need to be computed since the ratings of a user can be computed with the decomposition formula.

Algorithm guarantee

Theorem 1. Solving U (resp. I, A) with alternating least square and k U (resp. k I , k A ) latent factor on the tensor R is equivalent to applying alternating least square on R (1) (resp. R (2) , R (3) ) with k U (resp. k I , k A ) latent factor and identify U (resp. I, A) as the left side matrix in the matrix factorization.

Remark For sake of clarity this theorem means that at any step of the update, updating U using als-wr on R (1) will give the same results as updating U using Direct-Hoals. However once the right matrix of R (1) decomposition is fully updated using als-wr (that is we update both matrices of the matrix factorization)

we have no guarantee that the right matrix of the decomposition will contains the same values than the re-organisation of U , A and W after an update using Direct-Hoals. Nonetheless, this theorem shows that applying als-wr to compute the latent factors of a given dimension allows to improve their estimates provided that als-wr converges. Although interesting, we did not get the time to answer convergence question of Hoals but we feel like it should be related to the convergence of matrix factorization algorithms and more precisely of als-wr. See appendix A for an introduction to matrix completion convergence works.

Tucker Decomposition For sake of space, we use the following short summation notation

k U ,k I ,k A m,l,s=1 . = k U m=1 k I l=1 k A s=1 .
Besides, we recall that

L(W, U, I, A) = u,i,a∈D R uia -R uia 2 + λ   n u=1 n U u ||U u || 2 + p i=1 n I i ||I i || 2 + q a=1 n A a ||A a || 2   ,
Computing the partial derivative of L in Eq.3.6 w.r.t. U u 0 ,k 0 , we get:

1 2 ∂L ∂U u0,k0 = (i,a)∈Iu 0 k U ,k I ,k A m,l,s=1 W m,l,s U u0,m I i,l A a,s -R u0,i,a (3.7) × k I ,k A l,s=1 W k0,l,s I i,l A a,s + λn U u0 U u0,k0 , (3.8)
where I u 0 denotes the items and actions seen by user u 0 . Let us denote

V i,a m = k I l=1 k A s=1 W m,l,s I i,l A a,s (3.9)
and equalize the derivative above to 0, then we get the equation

(i,a)∈Iu 0 k U m=1 U u 0 ,m V i,a m V i,a k 0 + λn U u 0 U u 0 ,k 0 = (i,a)∈Iu 0 V i,a k 0 R u 0 ,i,a (3.10)
We introduce the mapping g 1 function:

g 1 : [p] × [q] → {1, • • • , pq} (i, a) → 1-mode unfolding corresponding column index
which maps item and action indices to a common index used to refer to the column of the 1-mode unfolding of the tensor. We can use this function to re-index

R 1 ∈ R n,pq such that R 1 u,g 1 (i,a) = r u,i,a and V 1 ∈ R pq,k U such that V 1 g 1 (i,a),m = V i,a m . Let G u 0 = {g : 1 ≤ g ≤ pq, R 1
u 0 ,g = 0} we can then rewrite the left side (LS) of Eq. 3.10 and obtain ∀u 0 , ∀k 0 :

(LS) = k U m=1 g∈Gu 0 V 1 g,k 0 V 1 g,m U u 0 ,m + λn U u 0 E k 0 U u 0 = k U m=1 [V 1 Gu 0 V 1 Gu 0 ] k 0 ,m U u 0 ,m + λn U u 0 E k 0 ,: U u 0 = [V 1 Gu 0 V 1 Gu 0 ] k 0 U u 0 + λn V u 0 E k 0 U u 0
Similarly for the right side

(RS) = g∈Gu 0 R 1 u 0 ,g V 1 g,k 0 = V 1 Gu 0 ,k 0 R 1 u 0 ,Gu 0 .
Thus ∀u 0 , Eq. 3.10 becomes

V 1 Gu 0 V 1 Gu 0 + λn U u 0 E U u 0 = V 1 Gu 0 R 1 u 0 ,Gu 0
And finally,

U u 0 = V 1 Gu 0 V 1 Gu 0 + λn U u 0 E -1 V 1 Gu 0 R 1 u 0 ,Gu 0 , (3.11)
which is exactly the classic ALS-WR formula for matrix factorization applied to the 1-mode matrix unfolding (3.3), which concludes the proof. CP Decomposition Computing the partial derivative of L in Eq.3.6 w.r.t. U u 0 ,k 0 , we get:

1 2 ∂L ∂U u 0 ,k 0 = (i,a)∈Iu 0 K k=1 U u 0 ,k I i,k A a,k -R u 0 ,i,a × I i,k A a,k + λn U u 0 U u 0 ,k 0 , (3.12)
where I u 0 denotes the items and actions seen by user u 0 . As previously, let us denote

V i,a k = I i,k A a,k (3.13)
and set the derivative above to 0, then we get the equation

(i,a)∈Iu 0 K k=1 U u 0 ,k V i,a k V i,a k 0 + λn U u 0 U u 0 ,k 0 = (i,a)∈Iu 0 V i,a k 0 R u 0 ,i,a
We use again the function

g 1 to re-index R 1 ∈ R n,pq such that R 1 u,g 1 (i,a) = r u,i,a and V 1 ∈ R pq,K such that V 1 g 1 (i,a),k = V i,a k . Let G u 0 = {g : 1 ≤ g ≤ pq, R 1 u 0 ,g = 0}
, we rewrite the left side (LS) of Eq. 3.14 and obtain ∀u 0 , ∀k 0

(LS) = K k=1 g∈Gu 0 V 1 g,k 0 V 1 g,k U u 0 ,k + λn U u 0 E k 0 U u 0 = K k=1 [V 1 Gu 0 V 1 Gu 0 ] k 0 ,k U u 0 ,k + λn U u 0 E k 0 ,: U u 0 = [V 1 Gu 0 V 1 Gu 0 ] k 0 U u 0 + λn V u 0 E k 0 U u 0
Similarly for the right side

(RS) = g∈Gu 0 R 1 u 0 ,g V 1 g,k 0 = V 1 Gu 0 ,k 0 R 1 u 0 ,Gu 0 .
We can then conclude as previously.

Experiments

We tested both the accuracy and the scalability of our method on different types of datasets:

• rather small datasets for recommendation problem but still large for common machine learning problem. These datasets allowed us to make a lot of experiments on a substantial number of algorithms and tune them quite effectively. These datasets also emphasize the benefit of using tensor decomposition instead of matrix decomposition.

• a bigger dataset to test the scalability performance as a function of the dataset size and the number of machines used.

Testing accuracy

We report an empirical comparison of a number of matrix and tensor decomposition methods. The objective is two-fold: 1) investigate whether tensor completion enables an effective transfer across different actions that improves over matrix completion where each action is treated separately, 2) compare Hoals to state-of-the-art methods.

Dataset. We use two real-world datasets:

• E-commerce dataset [Warlop, 2016]: this dataset contains historical interactions (click, add to cart, purchase) from a real e-commerce website of 1290 users and 390 items, resulting in around 120k (user, item, action, value) quadruplets. The value is the number of times the user performed the action on the item.

• Last.fm Dataset -1K users [Celma, 2009]: it is formed of around 20M lines representing the track of an artist that a user is listening to at a given timestamp. We transformed the dataset in order to get the quadruplets (user, artist, moment, value), where the moment represents the time of day clustered into three periods: morning from 6 a.m. to 2 p.m., afternoon from 2 p.m. to 10 p.m., and night from 10 p.m. to 6 a.m. The value counts the number of times the user listened to that artist in that period. The final dataset is composed of 510k quadruplets.

Algorithms. Beside Hoals, we tested four other state-of-the-art algorithms, two with different initialization

• MI-SVD: multiple independent svd applied to each slice of the tensor,

• HOSVD v0/vMean: as proposed by [START_REF] Symeonidis | Tag recommendations based on tensor dimensionality reduction[END_REF], filling missing values with either 0 or the mean of the modes,

• MI-ALS-WR: the classic als-wr applied to each slice of the tensor, that is three independent als-wr,

• CP-ALS-R v0/vMean (aka PARAFAC-ALS) as in Alg.1 of [START_REF] Hu | Personalized recommendation via cross-domain triadic factorization[END_REF], filling missing values with 0 or the mean of the modes. The algorithm is detailed in section 3.6.2. We used the cp als python code from the sktensor package,

• tucker/CP-HOALS, our parallel algorithm described in Alg. 3. The implementation is available at [Warlop, 2016].

• parafac-HOALS, our model. The code of Alg. 4 is available at [Warlop, 2016].

The vMean versions had only been tested on the E-commerce dataset because filling with non zero values require much more memory, since sparse representations of the structures cannot be used any more. As introduced in section 3.2, a more suitable version of als-wr for implicit feedback like the Last.fm dataset is the algorithm proposed by [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] called implicit als-wr. In the following, we use exactly the same approach to obtain an implicit version of Hoals. Experiments test both classic and implicit methods for als-wr and Hoals, which are referred to MI-als-wr and Hoals for the classic version and imp-MI-als-wr and imp-Hoals for the implicit counterparts. Finally, we also tried the algorithms proposed by [START_REF] Romera-Paredes | A new convex relaxation for tensor completion[END_REF] and [START_REF] Acar | Scalable tensor factorizations with missing data[END_REF] but their solutions could not scale to the size of our datasets. Experimental protocol. We first executed a preprocessing step.

1. We filtered out items seen by less than 5 users, 2. We define a maximum threshold for each action used to cap all the values (i.e., r uai = min{r uai , threshold a }). This prevents from having outliers that tend to degrade the performance. The click threshold was set to 50, the ATC to 20 and buy to 10.

3. We scaled all values between 0 and 10 in order to have comparable slices. This is needed since click, ATC, and buy actions are at very different scales.

For this experiment we performed 5-cross validation using the stratified cross validation introduce in 2.2.1 with 80% of users in the training sets and 20% of users in the test set and 70% of their ratings added to the training set. For evaluating the recommendation performance, we use the rank-measure (2.5) error, noted ρ, introduced by [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF], which is more suitable for implicit feedback datasets.

Results. The results are reported in Table 3.1. For Tucker models we tried 10, 50, 100 and 200 number of latent vectors for each possible tuning combination for the user and item slice, and 2 latent vectors for the action slice, since the depth of the tensor is always 3 in our cases. For CP decompositions, given that the rank has to be the same for all modes, we tried 2, 3, 4, 5 and 10 latent vectors for all modes.

We were not able to test higher number of latent vectors because of memory issue when trying to factorize the third unfolding matrix of size (q × np), which illustrates one of the drawbacks of CP decompositions. Furthermore, notice that increasing the number of latent vectors for the CP decomposition is not really meaningful since the action mode only contains three different actions. Finally for matrix decomposition we tried 10, 50, 100 and 200 number of latent vectors for each slice. For the sake of space we do not provide the parameters tuning results for each combination (several hundreds) and only report the performance for each model in their best configuration for each action. E-commerce dataset. In e-commerce applications, recommendations are usually performed using only the click action because of the sparsity of the buy action. For instance, in this dataset the sparsity level for click, ATC, and buy are respectively 85%, 94% and 98%. However, the results in Table 3.1 show that Tucker Hoals (implicit or not) outperformed every other model obtaining a ρ measure around 28% for the implicit version, even for the buy action, while other models are around 35%. The implicit Tucker Hoals improves the classic Tucker Hoals performance by more than two points, which illustrates the benefit of such a modelisation. Even the CP models outperformed the other factorization methods with a ρ measure around 32%. This indicates that the Hoals is able to perform better recommendation for the optimization of the purchase and is more suitable than the other tensor factorization methods thanks to its ability to deal with missing values. Furthermore, tensor factorization methods achieve better results than their matrix factorization counterparts (Hoals vs als-wr and Hosvd vs svd), which shows the advantage of transferring information across actions within this dataset. However, the Hosvd improvement over MI-svd is relatively small, about 1 point, whereas the tucker Hoals improvement over MI-als-wr is around 5 points for the classic algorithm and 12 points for the implicit one. These results show the effectiveness of Hoals in overcoming the sparsity issue by sharing knowledge across the different actions.

Finally, we see no real improvement in the initialisation of missing values with 0 or with mean values.

Last.fm dataset -1K users. For the Last.fm dataset (Table 3.2), tucker Hoals (implicit or not) obtains the best results with a ρ measure around 25%, two points better than Hosvd which is the next best model. Surprisingly, it is not the implicit version that achieve the best performance but the classic one, although both methods have really close performance (less than 0.6 point). Our CP method achieves relatively bad performance with a ρ measure around 32%. We think this can come from three reasons. The first one is due to the constraint of CP decomposition that imposes to have the same number of latent factors for each mode, which is a strong drawback for very imbalance tensor's dimensions, as it is the case here. The second one is the low number of features for the users and items modes that we could not increase because of computational issues. Both these explanations are common to cp-als-r and CP-Hoals. Finally, given the good performance of the Hosvd decomposition, we conjecture that treating missing values as 0 as done by the svd composition models is not completely unreasonable in this case, since a user never listens to an artist if he/she never heard about or do not like her. The combination of the two precedents reasons and this observation explain the bad performance of CP-Hoals on this dataset that has difficulty to learn good user and item representation in a very low dimension with only the known entries. However, once again the good performance of the tensor factorization models prove the effectiveness of transfer learning in this context. Indeed the gain between the best als-wr and the best tucker Hoals is around 7 points.

Other results. Besides those algorithms we also tried other techniques and algorithm that did not lead to satisfying results. For our Hoals implementation, we tried to model the movie recommendation problem as a tensor completion problem where each slice would represent a rating value and implement this technique on the movielens-1M dataset. To clarify things, if a movie can be rated between 1 and 5, we would have a tensor with five slices, where entries r u,i,a = 1 is user u rated movie i with a rating of a, and 0 otherwise. To infer the final user-item rating we first tried to select the maximum value in the rating fiber, thus the predicted rates are integers between 1 and 5 while classic matrix factorization outputs real values. This give a worse RMSE than classic als-wr on matrix completion. We assume that this come from the fact that ratings are normally distributed around 3.5 thus when als-wr predict 3.5 it is often a good prediction whether the actual rating is 3 or 4 with a squared error of 0.25 whereas with our technique if we predict 4 instead of 3 the squared error contribution is 1. To overcome this problem we computed the weighted average on the fiber. For instance if the predicted value of user u on movie i for each of the five slices are respectively 0.15, 0.2, 0.5, 0.3, 0.2 (it does not sum to 1), the predicted rating is r u,i . = 0.15×1+0.2×2+0.5×3+0.3×4+0.2×5 0.15+0.2+0.5+0.3+0.2 ≈ 3.15. This technique gave similar RMSE to classic als-wr on matrix completion but no real improvement. Another technique we studied for Hoals is to use contextual information as additional slice, where each slice represent one contextual. For instance if we know that movie i is a thriller, then r u,i,a = 1 for all users if slice a correspond to the thriller context. Unfortunately this modelisation consumed too much memory for the computer and did not run even on a small dataset like movielens-100k. In addition to Hoals, we tried the algorithms proposed by [START_REF] Romera-Paredes | A new convex relaxation for tensor completion[END_REF] and [START_REF] Acar | Scalable tensor factorizations with missing data[END_REF] but their solutions could not scale to our large datasets.

Testing scalability

For this experiment we used a real world dataset referred as big E-commerce dataset [Warlop, 2016]. The full dataset is composed of 100k users, around 25k items and 4 actions (view the product, click on the product, add it to cart or buy it) resulting in around 53M (user, item, action, value) quadruplets. The view action is a passive action, a user is exposed to an item by the website but cannot directly decide to see it or not. Thus this action is not really interesting to predict but can be very informative. Indeed a user may be more likely to click, add to her cart or buy a product if she sees it a lot. It is then a valuable context information that can be easily taken into account using tensor decomposition.

To test the scalability we measured the execution time when varying the size of the dataset and number of machines. For the size of the dataset we selected either 1k, 2k or 3k users and all the items (since the files are split every 1k users), knowing that 1k users result in a dataset of around 9Mo and 530k lines, i.e., quadruplets. We performed our experiments on Google Cloud on the n1-standard-2 machine, which is standard 2-CPU machine with 2 virtual CPUs and 7.5 GB of memory. When running the three decompositions in three independent cluster, the execution time depends on the execution time of the longest decomposition. We then report here the execution time of the longest decomposition for each dataset size.

Results. Fig. 3.5 compares Direct and Parallel -Hoals. We see that the execution times decreases linearly as the number of workers increases. Doubling the number of workers does not divide the execution time by a factor of 2 (for instance 2 workers, 1k users need 1200 seconds and with 4 workers it need 780 seconds) because of the set up and the communication time. Adding 1CPU decreases the running time in average of 200 (resp. 300 and 400) seconds for 1k users (resp. 2k and 3k). Thus adding users affect mainly the set up and communication time but the parallelisation is more and more effective. We thus see that the Hoals algorithm scale easily for big dataset thanks to its high parallelisation power. Furthermore, this improvement would be greatly amplified as the number of modes increases. For instance, the performance of RS in e-commerce can be significantly improved by adding new contexts such as the day of the week and the season of the year, thus resulting in a 5-order tensor completion problem. Table 3.1: ρ a measure (rank-measure) on the E-commerce dataset ordered by decreasing performance. For matrix factorization and CP tensor factorization, dim1 refers to the common latent space. For tensor factorization, dimension 1 and dimension 2 refers to the number of latent vectors for the user and item space respectively and dimension 3 is always equal to 2.

Related Works

As introduce in subsection 2. refers to the common latent space. For tensor factorization, dimension 1 and dimension 2 refers to the number of latent vectors for the user and item space respectively and dimension 3 is always equal to 2. Due to memory limitations, we were not able to perform a cp-als-r in dimension greater than 10, we thus compare to Hoals in dimension 10 as well.

of contextual information but the latent factors obtained with Hoals could be used in a hybrid methods if combine with other algorithms.

Collaborative Filtering

Early methods

At the beginning of recommender systems, algorithms explicitly rely on the idea that users that agreed in the past will agreed in the future. All the problem was then to find for each user the set of users with whom she agreed in the past, that is find similar user. In machine learning this problem consist in finding the neighbourhood of each user and leads to number of neighbourhood-based Collaborative Filtering methods. For instance [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF] used the Pearson correlation measure to compute the similarity w a,u between the active user a and the user u based on the set of commonly rated items I a,u :

w a,u = i∈Ia,u (r a,i -r a )(r u,i -r u ) i∈Ia,u (r a,i -r a ) 2 i∈Ia,u (r u,i -r u ) 2 (3.14)
where r x is the average rating given by user x. Then to compute the rating prediction of item i for the active user a, ra,i , the K most similar user according to w a,u that have rated item i, denoted N K (a), are mixed to compute the following weighted prediction:

ra,i = r a + u∈N K (a) w a,u (r u,i -r u ) u∈N K (a) w a,u (3.15)
Many other similarity measures have been investigated such as the cosine angle between users, the Spearman rank correlation, Kendall's τ correlation, mean squared differences, entropy, adjusted cosine similarity, ... [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF], [START_REF] Su | A survey of collaborative filtering techniques[END_REF]). Along the years, such techniques have been improved to take into account more precise information. Significance Weighting ( [START_REF] Herlocker | An algorithmic framework for performing collaborative filtering[END_REF]) and Default Voting ( [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative filtering[END_REF]) have been used to reduce the bias of computing correlation based on very few co-rated items.

Inverse User Frequency ( [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative filtering[END_REF]) to give a specific weight on each item based on the user that have rated this item. Finally Case Amplification ( [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative filtering[END_REF]) exponentially multiply the weight to give higher importance to highly similar users. All those techniques are also called User-User collaborative filtering because the rating prediction is based on user-user similarity measure. One can also perform Item-Item collaborative filtering (see [START_REF] Linden | Amazon.com recommendations: Item-to-item collaborative filtering[END_REF]) by reversing the formula to compute item-item similarity and compute similar weighted mean using item in the neighbourhood of the active item previously rated by the active user to compute the desired user-item rating. The choice of User-User collaborative filtering or Item-Item collaborative filtering will depend on the available data. If there are much more users than items, item-item similarities will be more precise than user-user similarities because they will be more likely to have a denser vector.

In general such techniques really suffer from scaling issues when the number of users or items is high, which is almost always the case in recommender systems. Indeed, to predict just one rating for a given user, one must find the subset of user that have rated the same item, select the top K similar user and then compute the weighted mean. This computation make the solution infeasible in practice. Besides, this solution has the drawback to rely a lot on human definition of similarity and importance measure. Finally, those methods can also suffer from blind spots as some items never intersect with the user neighbourhood in case of User-User collaborative filtering. Current methods on the other hand focus on scalability, data defined users and items descriptors and global prediction. They will be the focus of the following section.

State-of-the-art

To solve those issues, many methods rely on variations of the common idea of low rank matrix and thus perform matrix factorization. Here we present most common algorithms, except als-wr that has already been introduced. [START_REF] Toh | An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[END_REF]] -Accelerated Proximal Gradient algorithm for matrix completion problems solve a nuclear norm regularized least square problem in order to obtain the full matrix. Ideally, the CF problem should be to find the matrix X with the smallest possible rank that fit the known values: min

1-APG

X∈R n×p {rank(X); X u,i = R u,i , ∀(u, i) ∈ D} (3.16)
which is an NP-hard nonconvex optimization problem. However, a convex relaxation of this problem is to minimize the nuclear norm (sum of the singular values of the matrix), [Fazel, 2002], which is the best convex approximation of the rank function over the unit ball matrices, over the same constraints:

min X∈R n×p {||X|| * ; X u,i = R u,i , ∀(u, i) ∈ D} (3.17)
More generally, APG algorithm optimize the unconstrained nonsmooth convex minimization problem of the form: min

X∈R n×p F (X) . = f (X) + P (X) (3.18)
where P : R n×p → (-∞, ∞] is a proper, convex, lower semicontinuous function and f is convex smooth. Thus for matrix completion problem we have

P (X) = µ||X|| * and F (X) = u,i∈D ||R u,i -X u,i || 2 .
The solution is obtained by iteratively using the singular value thresholding algorithm (see [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF]) on a quadratic approximation of F . [Rendle, 2010] -Factorization Machines is a generalization of matrix factorization. Here the entries are not arrange in a matrix but in a array X ∈ R m×q whose lines contains the context and a vector Y ∈ R m that stock the feedback as in classic supervised learning. For instance the first n values of observation X l will encode the user id as a binary vector (that is X l [1 : n] = 0 except at position u for user u), the next p values will encode the item id as a binary vector (p zeros except at position n + i for item i), the following value can for instance represent the age of the user, the next one the category of the item, etc., and Y l is the feedback of user u on item i. In FM the function that link observation to output has the following form:

2-FM

ŷ(x) = w 0 + q j=1 w j x j + q j=1 q s=j+1 < V j , V s > x j x s (3.19) Where < V j , V s >= K k=1 V j,k V s,k
In particular, if q = n + p and thus the context is restricted to user and item ids, then x is not zero only at position u for user u and n + i for item i, and then ŷ(x) = w 0 + w u + w n+i + V u V T n+i which falls back to classic matrix factorization with bias terms. Parameters estimation is then done using a fast SGD that use a optimization rewritting of the equation of the following objective function for each parameter:

min θ∈Θ x,y∈S ŷ(x) -y 2 + θ∈Θ λ θ θ 2 (3.20)
where λ θ is a regularization (hyper-)parameter for the model parameter θ. To summarize, FM is a simple way to express pairwise interaction in sparse dataset and thus very suitable for recommender systems application. Even though the equation is written for 2-way FM, the formula can be extended to dimension d as follow:

ŷ(x) = w 0 + q j=1 w j x j + d l=2 q i 1 =1 • • • q i l =i l-1 +1   l j=1 x i j     k l f =1 l j=1 v (l) i j ,f   (3.21)
3-LLORMA [START_REF] Lee | Llorma: Local low-rank matrix approximation[END_REF] -Local Low-Rank Matrix Approximation extend the concept of low rank matrix approximation using ensemble methods.

LLORMA algorithm learn q independent weighted LRMA where the weight depend on the distance between each user and a user anchor and each item and an item anchor. For instance the distance can be computed using the angle between the latent factors that have been previously computed using one LRMA. The user (resp. item) anchor is chosen at random among all users (resp. items). The distance is then pass through a kernel (for instance the Epanechnikov kernel):

K (t) user u = (1 -d(anchor (t) , u) 2 )1 {d(anchor (t) ,u)<h} (3.22) K (t) item i = (1 -d(anchor (t) , i) 2 )1 {d(anchor (t) ,i)<h} (3.23)
That is if the user (resp. item) is far from the current anchor, the weight will be null and close to 1 otherwise. Thus, at a given step, only part of the users and items will be selected to form the input. The objective function solved by LLORMA for the t th LRMA is then:

min U ∈R n×K ,V ∈R n×K [K (t) user ] u [K (t) item ] i u,i∈D r ui -U u V T i 2 (3.24) + λ U ||U u || 2 + λ V ||V i || 2
The idea is that, with a sufficiently large value of q, the model will learn different factorization of subset of the initial matrix, where each subset is more likely to be low rank than the full initial matrix. Eventually, the prediction is obtained by computing the weighted mean as follow:

Rui = q t=1 K (t) user u K (t) item i q j=1 K (j) user u K (j) item i Û (t) u V (t) i (3.25)
This algorithm showed very good performances but this come with a much higher computational cost.

4-Logistic MF [Johnson, 2014] -Logistic Matrix Factorization focus on implicit feedback and adopt a probabilistic point of view of matrix factorization. [Johnson, 2014] is at [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] what logistic regression is at linear regression. Let l ui be the event that the user u interacted with item i. This event is then model has a logistic function of the inner product of user and item latent factors plus an user and item biases (respectively β u , and β i ):

P(l ui |U u , V i , β u , β i ) = exp(U u V T i + β u + β i ) 1 + exp(U u V T i + β u + β i ) (3.26)
The user and item biases allows to capture user engagement and item popularity. Besides, as [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF], the authors introduced a confidence weight on the entries proportional to the true value r ui , for instance c ui = αr ui . Then each non-zero entries serve as c ui positive entries, and each zero entries as a single negative one. Further assuming that all entries of R are independent lead to the following likelihood:

L(R|U, V, β) = u,i P(l ui |U u , V i , β u , β i ) αr ui (1 -P(l ui |U u , V i , β u , β i )) (3.27)
Placing zero-mean spherical Gaussian priors on user and item latent factors as:

P(U, σ 2 ) = u N (U u |0, σ 2 u I), P(V, σ 2 ) = i N (V i |0, σ 2 i I), (3.28)
lead to the following log-likelihood:

log P(R|U, V, β) = u,i αr ui (U u V T i + β u + β i ) (3.29) -(1 + αr ui ) log(1 + exp(U u V T i + β u + β i )) (3.30) - λ 2 (||U u || 2 + ||V i || 2 ) (3.31)
where constant term are replaced by the scaling parameter λ. We see that the zero mean Gaussian prior is equivalent to 2 -regularization. The final objective is then to maximize the log posterior of 3.29:

arg max U,V,β log P(R|U, V, β) (3.32)
The parameters can then be learned by alternating gradient descent, and optimized by choosing an adaptive gradient step size via AdaGrad. Note that in this formulation missing values are actually treated as 0 that is negative feedback. Besides introducing bias this assumption can lead to infeasible computation and memory issues. To limit those phenomenon, the authors proposed to only sample some missing values to be considered as 0 entries.

5-RSVD [Paterek, 2007] -Regularized Singular Value Decomposition solve the sparse matrix factorization problem using stochastic gradient descent on the regularized sum of squared residuals:

min U ∈R n×K ,V ∈R n×K u,i∈D r ui -U u V T i 2 + λ ||U u || 2 + ||V i || 2 (3.33)
Thus, unlike als-wr that has a closed form solution, RSVD update the user and item latent factors with SGD one feature at a time. Thus the update equation rule for one feature of user u is

U uk = U uk + lrate (r ui -rui )U uk -λU uk ,
where lrate is the learning rate, usually 0.001. One can find the formula for V by symmetry of the problem. Adding user (b u ∈ R), item (b i ∈ R) and global bias to the formula (r ui = U u V T i + b u + b i + µ) lead to the Improved RSVD model also referred as RSVD2. The global bias can be seen as the average rating of the database, the user bias measure the tendency of the user to give higher or lower feedback values than other users, the item bias the tendency of an item to receive a higher or lower feedback than other, which then leave the model to measure separately the join user-item interaction.

6-SVD++ [Koren, 2008] extend the latent factor model of [Paterek, 2007] by incorporating implicit feedback. In this context an implicit feedback is an information of an interaction of the user with the system without explicitly rating the items. For instance we can know that the user has viewed some movies but we do not know the ratings, or click on a product but we do not know if she bought it or not. Let N u be the set of item that user u interacted with, I u ⊂ N u , and Y i ∈ R K the latent factor of item i for the implicit feedback. Then the desired output is defined as

rui = µ + b u + b i + V T i   U u + |N u | -1 2 j∈Nu Y j   (3.34)
where µ is the global bias, b u and b i the user and item bias and |N u | the cardinality of N u . The parameters are then learn by SGD on the residuals squared errors:

min µ,b,U,V,Y u,i∈D (r ui -rui ) 2 (3.35) + λ   b 2 u + b 2 i + u∈I i ||U u || 2 + i∈Iu ||V i || 2 + j∈Nu ||Y j || 2  

Tensor Factorization

PARAFAC decomposition without missing data.

1-CP-ALS-R In [START_REF] Hu | Personalized recommendation via cross-domain triadic factorization[END_REF], the authors focus on the problem on cross domain recommendation, for instance books, musics and movies simultaneously for the same users. Instead of concatenating the domain in order to create a very wide matrix, they look for a tensor formulation of the problem where each slice of a tensor capture a domain that will be filled by CP decomposition. The advantage is that each domain will have its own latent factors that will not have to be shared with other domains. The problem of finding a CP decomposition of a generic tensor X ∈ R n×p×q is restated as a least-squares problem, i.e., finding the factors

A ∈ R n×K , B ∈ R p×K , C ∈ R q×K that minimize the loss f (A, B, C) = 1 2 ||X -[A, B, C]|| 2 F + λ A 2 ||A|| 2 F + λ B 2 ||B|| 2 F + λ C 2 ||C|| 2 F . (3.36)
Computing the derivative and setting it to zero yields to a closed-form expression for each matrix, based on the pseudo-inverse property of Khatri-Rao product. For instance, when fixing matrices B and C, the derivative with respect to A is:

∂f ∂A = (X (1) -Y (1) )(C B) + λ A A (3.37)
where Y = [A, B, C] and then

A = X (1) (C B)(B T B ⊗ C T C + λ A I) * (3.38)
where ⊗ stand for the element-wise product. Similar solutions can be found for B and C using the other unfolded matrices. One can then alternately learn each of these matrices until convergence, see algorithm 5. However this algorithm can not be directly applied to their framework. Indeed the number of items in each domain is inconsistent. To solve this issue they introduce a column-wise orthonormal matrix for each domain of size the number of items in the domains times the rank of the tensor. For example let consider domain k with sparse matrix

X k ∈ R n×p k , that can be factorize into X k ≈ U Σ k V T k . Using P k ∈ R p k ×K we can reformulate the factorization as X k ≈ U Σ k (P k V ) T ,
which also introduce the matrix V ∈ R K×K that does not vary by slice. Thus looking at the factorization of each X k , k ∈ [κ] with this formulation is equivalent to a PARAFAC decomposition:

min U,V,Σ,P k κ k=1 ||X k -U Σ k (P k V ) T || 2 ⇔ min U,V,Σ,P k κ k=1 ||X k P k -U Σ k V T || 2 (3.39) Algorithm 5 CP-ALS-R(X, λ A , λ B , λ C ).
Input: X the tensor to factorize, λ A , λ B , λ C , the regularization parameters, the rank constraint K Initial (sparse)

X(d) = U (d) Sd V d end for Compute W . = X × 1 U (1) × 2 U (2) × 3 U (3) Return full tensor X . = W × 1 U (1) × 2 U (2) × 3 U (3)
with X k P k ∈ R n×K . Writing Z the corresponding n × K × κ tensor where each slice corresponds to a X k P k and define C ∈ R K×K such that Σ k . = diag(C k ), one can rewrite equation (3.39) as a PARAFAC decomposition following equation (3.36) (with A = U and B = V ) and apply cp-als-r. cp-als-r has the advantage to be simple and easily implemented. However, this approach suffers from major limitations. First, the definition of the least-squares problem does not deal with missing values and the tensor is assumed to be full. In recommender systems, this means that the initial sparse tensor is usually filled with zeros or the mean over each mode which can also cause memory issues. Furthermore, cp-als-r directly inherits one of the major drawbacks of the CP decomposition: each rank constraint must be the same for each mode. When the dimensions of the tensor are highly unbalanced, as in the case of e-commerce or restaurants, where we may have millions of users, thousand of products but only few actions, the rank constraint is either far too high for the action dimensions or far too low for the other modes preventing the model from learning appropriately.

Tucker decomposition without missing data.

One of the most popular approach to perform Tucker decomposition is the generalization of svd to n-order tensors called Hosvd [START_REF] Lathauwer | A multilinear singular value decomposition[END_REF], for which multiple versions have been proposed. We recall that the svd of a matrix is the product of three matrices U , S and V , where U and V are orthonormal matrices of the left and right singular values and S is the diagonal matrix of (ordered) singular values of X such that X = U SV . In recommender systems, we preserve only the k largest singular values to get an approximation of X defined as X .

= U SV , where S is the truncated value of S where we replaced the K + 1, • • • , min(n, p) largest singular value by 0, thus X is the orthogonal projection of X on the space of rank-K matrices.

2-HOSVD

In order to compute the Tucker decomposition, [START_REF] Symeonidis | Tag recommendations based on tensor dimensionality reduction[END_REF] proposed to apply SVD on unfolded versions of the tensor as illustrated in algoritm 6. Once the SVD of each matrix is obtained, the core tensor is approximated by reversing the formula: 3) . Their application focus on tag recommendation that is the first dimension encode users, the second encode the items and the third dimensions the tags. Each time a user give a tag to an item, the corresponding entry of the tensor is filled with a 1 whereas the missing values are implicitly translated into 0 entries. In many recommender systems, this may significantly bias the result and return poor prediction performance like svd for matrix factorization.

W = X × 1 U (1) × 2 U (2) × 3 U (

Dealing with missing values.

Both previous tensor factorization algorithms can be adapted to take into consideration missing values. Let P a binary 3-order tensor defined as (see [START_REF] Acar | Scalable tensor factorizations with missing data[END_REF], [START_REF] Tomasi | Parafac and missing values[END_REF])

P ijk = 1, if (i, j, k) ∈ D 0, else
3-CP-WOPT Using P, [START_REF] Acar | Scalable tensor factorizations with missing data[END_REF] adapts the objective function of the CP decomposition as

f P (A, B, C) = I,J,K i,j,k=1   Pijk   X ijk - R r=1 A ir B jr C kr      2 = ||Y -Z|| 2 with Y = P * X and Z = P * [A, B, C] ,
where * represent the element by element multiplication. They propose to use nonlinear conjugate gradient method after having vectorized the two tensors (by concatenating all the modes into a long vector). The resulting algorithm has the advantage to use a simple firstorder optimization method. Nevertheless it suffers from different drawbacks. First, this approach can be really memory greedy since for each step of the algorithm very long vectors with all the known values need to be stored, while for each update, HOALS store only the values related to a particular user (resp. item, or action), and thus fail in large recommender systems. Indeed, they show experiments on a 64 × 4392 × 28 tensor that is very small compared to stateof-the-art recommender systems like Amazon or Netflix. Second, the algorithm proceeds sequentially and it can not be parallelized. This is also a major drawback in recommender systems that deal with millions of user and entries that cannot be managed by a unique non-parallel method. Having very time consuming learning may not be dramatic for some machine learning application like image recognition with neural network as long as the prediction is very effective, but for recommender systems users arrive everyday, items are added everyday and thus feedback are continuously provided. One may not have to update the model online after one feedback is acquired (however it could be very valuable for cold-start user/item) but should update it very frequently (in practice every night) in order to prevent user from being recommended already seen or purchased items and improve recommendation accuracy with those fresh information.

A similar approach can be followed for the Tucker decomposition by defining the objective

f P (W, U, I, A) = 1 2 ||P * (X -W × 1 U × 2 I × 3 A)|| 2 F
4-Tucker decomposition with missing data In order to learn the decomposition, [START_REF] Filipović | Tucker factorization with missing data with application to low-n-rank tensor completion[END_REF] used nonlinear conjugate gradient with HOSVD initialization. The gradients of the objective function are (similar for I and A)

∇ U f P = [P * (W × 1 U × 2 I × 3 A -X)] (1) • [(W × 2 I × 3 A) (1) ] ∇ W f P = P * (W × 1 U × 2 I × 3 U -X) × 1 U × 2 I × 3 A
Although interesting, this method has several limitations when applied to recommender systems. First, it does not include any regularization in the objective function and this may lead to overfitting data. Second, as for the CP models, the algorithm cannot be parallelized and this hinders its applicability to large scale recommender systems.

Finally, when dealing with multi-relational data, the problem can be seen as a particular tensor completion problem where each slice is a squared matrix. [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF] studied this specific problem by leveraging this particularity of the tensor in their RESCAL algorithm. Let consider the tensor X ∈ R n×n×p , where for instance each slice indicate whether or not two users shared the same attribute (hair color, occupation, friendship, ..) and unknown values are set to 0. This particular problem lead the authors to consider a rank-K factorization of each slice X k such that

5-RESCAL

X k ≈ AR k A T , ∀k ∈ [p]
(3.40)

with A ∈ R n×K is common to each slice and contains the latent component of the users and R k ∈ R K×K is an arbitrary squared matrix that weights the latent components for the k-th attribute. The matrices A and (R k ) k∈[p] are then learned in order to minimize the regularized squared loss:

min A,R k k ||X k -AR k A T || 2 F + λ(||A|| 2 F + k ||R k || 2 F (3.41)
which is optimize following an alternating least squares approach. Although the authors filled the missing values by 0, one could derived a modified version that only minimize the error on the known entries. However interesting we could not compare with this approach because of the squared matrix constraint that make no sense in our case. We could use the same trick as [START_REF] Hu | Personalized recommendation via cross-domain triadic factorization[END_REF] and detailed above in order to make the rectangular tensor square but it would make no sense to force users and items which have the same arbitrary index to have the same latent vectors.

Transfer Learning

Our work can also be related to transfer learning ( [START_REF] Pan | A survey on transfer learning[END_REF]) which aims at transferring knowledge learned in some task in order to improve learning of a new task. This broad concept can served different purposes like metalearning or multi-task learning and has been widely studied in supervised learning ( [START_REF] Mitov | A fused elastic net logistic regression model for multi-task binary classification[END_REF], [START_REF] Bakker | Task clustering and gating for bayesian multitask learning[END_REF], [START_REF] Evgeniou | Learning multiple tasks with kernel methods[END_REF]) and reinforcement learning ( [START_REF] Wilson | Multitask reinforcement learning: A hierarchical bayesian approach[END_REF], Lazaric, 2008, Lazaric et al., 2008, Lazaric and Ghavamzadeh, 2010]). Transfer learning also receive attention in recommender systems. In order to fill the matrix R (t) of a target domain, [Pan et al., 2010] assumed the existence of two dense auxiliary matrices, R (1) and R (2) which are similar to the target domain, that is R (t) and R (1) share the same users whereas R (t) and R (2) share the same items. In order to approximate the factorisation of the target matrix R (t) . = U (t) B (t) V T (t) , their algorithm called Coordinate System Transfer (CST) first learn the decomposition of R (i) .

= U (i) B (i) V T (i) , i ∈ {1, 2} using classic matrix factorization techniques on sparse data in order to obtain good starting point to learn the factorization of R (t) : U 0 = U (1) and V 0 = V (2) , where U 0 and V 0 are the starting point in the learning of U (t) and V (t) . U 0 and V 0 are also used to regu-larize the objective function -the square loss on the known entries -by adding a penalty term of the form λ||U -U 0 || 2 F + λ||V -V 0 || 2 F in order to force the algorithm to output values for U (t) (respectively V (t) ) that are in the ball of center U 0 (respectively V 0 ) which are learn alternatively together with B (t) with alternating gradient descent until convergence. If the domains are indeed correlated, the latent factors of U (1) and V (2) does contains good approximations of the one U (t) and V (t) that simplifies the learning of the target matrix. Similarly, the approach introduced in [Li et al., 2009a] assumes the existence of a related dense source but it is not assumed that source and target domains actually share the same user nor item which prevent from transfering user and item latent factors. They introduce the notion of Codebook: Codebook is a k × l matrix (k, l ≤ n, p) which compresses the cluster-level user-item rating patterns of k user clusters and l item clusters in the original rating matrix. In other word the objective is to find a bi-clustering of user and item of the source domain into a small matrix, that contains user cluster-item cluster affinities in order to transfer it to the target domain that will leverage this new information to learn the decomposition. This codebook B is create from the orthogonal nonnegative matrix tri-factorization [START_REF] Ding | Orthogonal nonnegative matrix t-factorizations for clustering[END_REF] of the source matrix R (s) ≈ U (s) S (s) V T (s) with U (s) ∈ rr n×k + , V (s) ∈ rr p×l + , and S (s) ∈ rr k×l

+ such that U T (s) U (s) = V T (s) V (s) = I, note that by definition each row of U (s) (resp. V (s)
) can only have one entry equal to 1 and the other equal to 0 which indicate the cluster the user (resp. item) belongs to. Thus,

B = [U T (s) R (s) V (s) ] [U T (s) 11 T V (s) ] (3.42)
where means entry-wise division. The simplify objective of the target domain will then be to factorize the target matrix R (t) using the codebook B:

min U,V ||[R (t) -U BV T ] • W || 2 F such that U 1 = V 1 = 1 (3.43)
where W is the binary matrix that worth 1 on the known entries and 0 elsewhere. In words, equation (3.43) look to which cluster each target user and item belong to in order to predict the missing values. When Q dense sources are available, [START_REF] Moreno | Talmud: Transfer learning for multiple domains[END_REF] extend codebook transfer method by computing a codebook (B q ) q∈[Q] for each source and look for a mix of them in the target domain:

min Uq,Vq,αq ||[R (t) - Q q=1 α q U q B q V T q ] • W || 2 F such that ∀q ∈ [Q], U q 1 = V q 1 = 1 (3.44)
Finally, [START_REF] Li | Transfer learning for collaborative filtering via a rating-matrix generative model[END_REF] further developed a similar idea using projection of a hyperstructure that is transferred in order to capture non-linear correlation between domains.

Cold-start

Using multiple type of interaction has also the advantage to increase the number of feedback available per user and item, especially when among the differ-ent interaction only one is of interest for the selection choice. The cold-start problem have been studied along two directions. The first consist in relying on other source of information like using images or textual information and construct hybrid models ( [START_REF] Grbovic | E-commerce in your inbox: Product recommendations at scale[END_REF][START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], Le and Mikolov, 2014, Vasile et al., 2016]). Transfer learning introduced above can also be considered as tackling the cold-start issue by transfering users (respectively items) latent factors from an other application with the same users to the current task where users (respectively items) are in a cold-start situation. However in practice this situation almost never happens especially with the GDPR reinforcement law on data sharing between brands. Sharing personal data and personal feedback on items between brands is usually not possible. Thus such approaches are only possible for huge brand like Amazon and Wallmart who can "transfer" users information from different categories of their own brand. Other techniques to gather knowledge on new users consist in asking questions to users ( [START_REF] Elahi | Personality-based active learning for collaborative filtering recommender systems[END_REF]) but asking effort to new user could increase the rebound rate, that is the number of users leaving the website after only seeing one page. Finally sometimes it is possible to have access to social graph in order to improve learning in cold-start situation. For instance [START_REF] Sedhain | Social collaborative filtering for cold-start recommendations[END_REF] used social graph information to first compute similarity between cold-start and non cold-start users and then leverage non cold-start users prediction to output cold-start users prediction. Graph regularized matrix factorization can also be used when social information are available ( [START_REF] Cai | Graph regularized nonnegative matrix factorization for data representation[END_REF]).

The second direction to solve cold-start problem is to apply explorationexploitation methods that perform recommandation both to collect valuable feedback for future training and to satisfy users. Those question are related to bandit learning (see subsection 2.1.3) and best arm identification problems ( [Soare et al., 2014, Jamieson andTalwalkar, 2016]). However application to collaborative filtering is not trivial. Indeed in linear bandit the output is a linear combination between a fix vector x that encode item information and a vector θ to learn. Even though in collaborative filtering the output is also a linear combination between two vectors here both vectors need to be learned and thus classic linear bandit proof can not be applied any more. A second difficulty is that in most recommender system application, one item can not be recommended multiple time to the same users, thus it is impossible to compute a confidence interval around this entry by pulling it multiple times. Aware of those limits, [START_REF] Mary | Bandits warm-up cold recommender systems[END_REF] propose a version where each entry can be sampled multiple times, for instance in music application or retargeting and focus on one cold-start: either user cold-start or item cold-start. For instance, in the case of user cold-start, they assume a sufficient number of feedback for each item thus the uncertainty on U is much more important than on V and the problem can be expressed using the linear bandit theory. For instance let consider user u and consider the K × K matrix A:

A = V T Iu V Iu + λn u I
constructed with the latent factors of the items previously rated by user u. Then the UCB strategy select next item j following:

j . = arg max j∈Iu U u • V T j + α V j A -1 V T j (3.45)
where α ∈ R is an exploration parameter to be tuned. The simple ε-greedy algorithm can also be applied to matrix factorization as done by [START_REF] Guillou | Large-scale bandit recommender system[END_REF]. In this case, the matrix decomposition is periodically recomputed, and ε/f (t)% of the time, with f (t) some fonction increasing with time like f (t) = t or f (t) = log t, an item is picked at random to be recommended to the active user. This modified version of the ε-greedy algorithm is called ε n -greedy algorithm where ε is decreasing over time in order to allow lots of exploration at the beginning of the user journey and less and less over time when the system start to know the user very well. This algorithm called SeALS for Sequential ALS-WR experimentally proved to reduce the cumulative regret on several datasets like Movielens and Yahoo.

An other direction is proposed by [START_REF] Li | Collaborative filtering bandits[END_REF] that derived a sort of coclustering algorithm with bandit techniques. In their framework, each item is defined by a known vector x ∈ R d , and the affinity between user u and item i of vector x is the scalar product between the user unknown vector U u ∈ R d and x plus sum noise:

r ui (x) = U T u x + ε u (x).
In simple words, in order to estimate the affinity between the active user and every available items, the system will rely on a user clustering that depend on each item (all users that have close predicted affinity on this item will form a cluster) to compute an average estimate of U u and of the V u matrix (see Theorem 7) of past observation to compute a UCB reward. After choosing an item and observing the feedback, the system will update the clusters for the next step. This formula allows to leverage information from other users in order to alleviate from cold-start issues.

Industrial learnings

From an industrial point of view, we exploited Hoals in several applications at fifty-five. Two applications were realised for a coupon/offer reduction recommendation problem for a food and a mall industry. In both cases the number of available coupons were not very large compared to classic e-commerce application, and users contextual information not reliable becauses users had to register online and often provided fake information or only an e-mail. Thus content-based models were not really an option. Users can interact with coupons in several ways. For the food industry the actions were the possibility to download on the website, download from an e-mail from a previous campaign a coupon, and finally actually purchase something using those coupons. For the mall industry there are clicks on the website page, clicks on the mobile application, Facebook likes and finally purchase. Classic matrix factorization was also not really an option because the real target action -the purchase -was a really rare event. Hoals was thus an interesting alternative and put into production for the campaign. Introduction of other dimensions like season of the year were considered for next steps of the activation. Hoals has also been used in order to create embedding of retailers for the mall industry to get insight on retailer correlations. Without Hoals it would have been difficult to get a global embedding of items since we would either have to (1) create an embedding for the mobile application based on mobile clicks and an other embedding based on the clicks on the website or (2) using only conversion. With the first solution, the two embeddings can be aggregated (sum or concatenated) but with Hoals all the feedback is used to compute one emdebding which is thus learned with more feedback than each separate embedding of this first solution and thus is more reliable. The second solution was not possible because conversions were very rare in the dataset, since most online users are not linked to offline conversions. Finally, using bandit methods to solve the cold-start problem although interesting in theory suffer from several industrial constraints. The first is that bandit learning are useful to achieve good long term performance but most of the time one cannot wait for long term and a recommender system must leverage very few user sessions. Thus using all information provided by each user during a session like click, add to cart, conversion, zoom, reading of comments or time on the page is often a better approach than applying linear bandit using only the conversion as a target to be maximized. Today, in order to work around the cold start issue, the trend is to collect feedback using new technologies to interact and engage users like chatbot or virtual/augmented reality.

Conclusion

In this chapter we introduced a parallel tensor factorization algorithm for recommender systems built on an extension of alternating least squares. For e-commerce, the purchase action is the most preferable action to predict but also the most difficult for matrix factorization given its high sparsity. However, our Hoals model proved to be effective to predict any action by leveraging knowledge from the other actions and thus make it an efficient transfer learning algorithm for RSs. An important advantage of Hoals over state-of-the-art methods such as cp-als-r and Hosvd is its high ability to be parallelized, and thus its feasible for large RSs dealing with millions of users and items. For instance, for a n-order tensor, since cp-als-r computes matrices one after the other, Hoals is n times more parallelizable. We also extended the implicit feedback strategy introduced in [START_REF] Hu | Collaborative filtering for implicit feedback datasets[END_REF] to tensor factorization, making our algorithm a very effective approach to solve efficiently RSs with implicit and multiple feedback. Finally, Hoals can also be used to create embedding of users or items using all available feedback at the same time in order to be integrated into an hybrid recommender system or provide clustering information.

Basket completion with multi-task Determinantal Point Process

Determinantal point processes (dpps) have received significant attention in the recent years as an elegant model for a variety of machine learning tasks, due to their ability to model set diversity and item quality or popularity. Recent works have shown that dpps can be effective models for product recommendation and basket completion tasks. We present an enhanced dpp model that is specialized for the task of basket completion, the Multi-Task dpp. We view the basket completion problem as a multi-task classification problem, and leverage ideas ideas from tensor factorization and multi-class classification to design the Multi-Task dpp model. We evaluate our model on several real-world datasets, and find that the Multi-Task dpp provides significantly better predictive quality than a number of state-of-the-art models.

Introduction

Increasing the number of items in the average shopping basket is a major concern for online retailers. While there are a wide range of possible strategies, this work focuses on the algorithm responsible for proposing a set of items that is best suited to complete the current shopping basket of the user.

Basket analysis and completion is a very old task for machine learning. For many years association rule mining [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], Hipp et al., 2000, Liu et al., 1998] has been the state-of-the-art. Even though there are different variants of this algorithm, the main principle involves computing the conditional probability of buying an additional product by counting co-occurrences in past observa-tions. Because of the computational cost and robustness, modern approaches favor item-to-item collaborative filtering [START_REF] Linden | Amazon.com recommendations: Item-to-item collaborative filtering[END_REF], or using logistic regression to predict if a user will purchase an item based on binary purchase scores obtained from market baskets [START_REF] Lee | Classificationbased collaborative filtering using market basket data[END_REF].

As reported in related work, vanilla collaborative filtering needs to be extended to correctly capture diversity among products. Pracitioners often mitigate this problem by adding constraints to the recommended set of items. As an example, when using categorical information it is possible to always recommend one pair of matching shoes when trousers are added to the basket, even if natural co-sales could lead to the recommendation of other trousers. In this situation the presence of diversity in the recommendations is not directly driven by the learning algorithm, but by side information and expert knowledge. Ref. [START_REF] Teo | Adaptive, personalized diversity for visual discovery[END_REF] proposes an effective Bayesian method for learning the weights of the categories in the case of visual search when categories are known.

Sometimes we need to learn diversity without relying on extra information. Naive learning of diversity directly from the data without using side information comes at a high computational cost because the number of possible sets grows exponentially with the number of items. The issue is not trivial, even when we want to be able to add only one item to an existing set, and becomes even harder when we want to add more than one item with the idea of maximizing the diversity of the final recommended set.

Refs. [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], Gartrell et al., 2016] address this combinatorial problem using a model based on Determinantal Point Processes (dpps) for basket completion. dpps are elegant probabilistic models of repulsion from quantum physics, which are used for a variety of tasks in machine learning [START_REF] Gautier | Zonotope hit-and-run for efficient sampling from projection dpps[END_REF], Kulesza and Taskar, 2012, Foulds and Görür, 2013]. They allow sampling a diverse set of points, with similarity being encoded using a positive semi-definite matrix called the kernel. Efficient algorithms for marginalization and conditioning dpps are available. From a practical perspective, learning the dpp kernel is a challenge because the associated likelihood is not convex, and learning it from observed sets of items is conjectured to be NP-hard [START_REF] Kulesza | Determinantal Point Processes for Machine Learning[END_REF].

For basket completion it is natural to consider that sets are the baskets which converted to sales. In this setting, the dpp is parametrized by a kernel matrix of size p × p, where p is the size of the catalog. Thus the number of parameters to fit grows quadratically with the number of items and the computational complexity cublicly. As learning a full-rank dpp is hard, [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF] proposes regularizing the dpp by constraining the kernel to be low rank. This regularization also improves generalization and offers more diversity in recommendations without hurting predictive performance. In fact in many settings the predictive quality is also improved, making the dpp a very desirable tool for modeling baskets. Moreover, the low rank asumption also enables substantially better runtime performance compared to a full-rank DPP.

Nevertheless, because of the definition of dpp, as described in Section 4.3, this low-rank assumption for the kernel means that any possible baskets with more items than the chosen rank will receive a probability estimation of 0. This technique is thus impossible to use for large baskets, and some other regularizations of the dpp kernel can be more intersting. The contribution of this chapter is threefold:

• We modify the constraints over the kernel to support large baskets.

• We model the probability over all baskets by adding a logistic function on the determinant computed from the DPP kernel. We adapt the training procedure to handle this nonlinearity, and evaluate our model on four popular basket datasets.

• By leveraging tensor factorization we propose a new way to regularize the kernel among a set of tasks. This approach also leads to enhanced predictive quality.

We also show that these ideas can be combined for further improvements to predictive quality, allowing our Multi-Task dpp model to outperform state-of-the-art models by a large margin.

In the next section we introduce Determinantal Point Processes in order to give the appropriate background before presenting our proposed algorithm in the following section which effectiveness is validatating on various real world dataset in the next section. We then discuss related work before concluding and introducing possible future works.

Background

Generally a Point Process P is a probability measure over a set of points, and Determinantal Point Processes (dpps) compute these probabilities using determinants. dpps were originally used to model a distribution over particles that exhibit a repulsive effect [START_REF] Vershik | Asymptotic Combinatorics with Applications to Mathematical Physics[END_REF]. Recently, interest in leveraging this repulsive behavior led to dpps receiving increasing attention within the machine learning community. Mathematically, discrete dpps are distributions over discrete sets of points (note that dpps can be defined for the continuous case), or in our case items, where the model assigns a probability to observe a given set of items

I ⊂ [p] . = [1, •, p],
with p the number of items. A process P is called a determinantal point process if it follows definition 4.

Definition 4 (Determinantal Point Process). If for all Y random subsets drawn according to P, we have

∀I ⊂ [p], P(I ⊂ Y ) = det(K I ) (4.1)
with K ∈ R p×p a real symmetric positive semidefinite matrix, then P is a Determinantal Point Process. K I denotes the principal submatrix of K indexed by the elements in I.

A dpp is then a probability measure on 2 p (the power set, or set of all subsets of p). However in practice it is more convenient to define a dpp through L-ensembles, that defines a dpp according to a real, symmetric matrix L, that directly output the probability to observe a given set I:

P(I) ∝ det L I (4.2)
The equality is obtained by dividing the right part of equation 4.2 by det(L + I), because it can be shown that I det L I = det(L + I) (see Theorem 2.1 of [START_REF] Kulesza | Determinantal Point Processes for Machine Learning[END_REF]) such that P(I) = det L I / det(L + I). Those two definitions are equivalent and one can show that K = L(L + I) -1 (see Theorem 2.2 of [START_REF] Kulesza | Determinantal Point Processes for Machine Learning[END_REF]). The repulsive behaviour of dpps can be easily seen in the particular case of selecting two items i and j together, since this probability is

P[{i, j}] ∝ L ii L ji L ji L jj = P[{i}]P[{j}] -L 2 ij (4.3)
In equation 4.3 we can see that the more similar i and j are -that is the higher L ij is -the less likely they are to be sampled together. The definition of the entries L ij will therefore determine the replusive behavior of the kernel for the task. For instance, if similarity is defined using image descriptors such that L ij = V i V T j with V i ∈ R K the embedding of item i, then images of differing appearance will be more likely to be sampled by a dpp. On the other hand, if the entries L ij are learned using previously observed sets, such as e-commerce baskets [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], then co-purchased items i and j will are likely to be sampled by the dpp, and thus the "similarity" L ij will be low. In an application such as a search engine or in document summarization, the kernel may be defined using feature descriptors V i ∈ R D (i.e tf-idf of the text with D the size of the dictionary), and a relevance score q i ∈ R + of each item i, such that L ij = q i V T i V j q j , which favors relevant items (large q i ) and discourages lists composed of similar items.

We see that kernel of the dpp can either be explicitly defined in order to induce diversity in future samples, or be learned in order to measure set correlation in some data. In the following we will focus on the later for the basket completion application.

Model

Logistic DPP

Our objective is to find a set of items that are most likely to be purchased together. We formulate this as a classification problem, where the goal is to predict if a specific set of items will generate a conversion from the user, which we denote as Y ∈ {0, 1}.

We model the class label Y as a Bernoulli random variable of parameter φ(I), where I is the set of items and φ is a function that we will define later:

p(y|I) = φ(I) y (1 -φ(I)) 1-y (4.4)
We model the function φ using a dpp. We assume that there exists a latent space such that diverse items in this space are likely to be purchased together. Similarly to [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], we assume a low-rank factorization of the kernel matrix L ∈ R p×p according to the following definition:

Definition 5 (L kernel matrix of Logistic DPP).

L = V V T + D 2 (4.5)
where V ∈ R p×r is a latent matrix where each row vector i encodes the r latent factors of item i. D is a diagonal matrix that, and together with ||V i ||, represents the intrinsic quality or popularity of each item.

The squared exponent on D in definition 5 insures that we always have a valid positive semi-definite kernel. We then define φ(I) ∝ det(V I,: V T I,: + D 2 ) ≥ 0. Note that without the diagonal term, the choice of r would restrict the cardinality of the observable set, because |I| > r would imply φ(I) = 0 when D ≡ 0. Using this term will ensure that the success probability of any set will be positive, but the crosseffects will be lower for sets of cardinality higher than r. We also see that items with similar latent vectors are less likely to be sampled than items with different latent vectors, since similar vectors will produce a parallelotope with a smaller volume. To normalize the probability and encourage separation between vectors we define Φ according to a logistic function as follow:

Definition 6 (Success probability of Logistic DPP). Let L be defined according to definition 5

φ(I) = P(y = 1|I) . = 1 -exp(-w det L I ) (4.6) . = σ(w det L I ) (4.7)
Usually the logistic function is of the form σ(x) = 1/(1 + exp(-x)). However, in our case the determinant is always positive since L is positive semi-definite, which would result in P(y = 1|I) always greater than 0.5 with such a function. By construction, our formulation allows us to obtain a probability between 0 and 1. Finally, w ∈ R is a scaling parameter to be learned by cross-validation that insures that the exponential does not explode. Indeed, popular items will have a value L ii > 1 in order to increase the determinant when in a set. Consequently the determinant of a set containing multiple independant popular items would be of the order of α q with α > 1 and q the number of items and thus could explode.

Learning. In order to learn the matrix V we assume the existence of historical data {I m , y m } 1≤m≤M , where I m is a set of items, and y m is a label set to 1 if the set has been purchased and 0 otherwise. This training data allows us to learn the matrices V and D by maximizing the log-likelihood of the data. To do so, we first write the click probability for all y as

P(y|I) = σ(w det L I ) y (1 -σ(w det L I )) 1-y (4.8)
The penalized log-likelihood f (V, D) can then be written as

f (V, D) = log M m=1 P(y m |I m ) - α 0 2 p i=1 α i (||V i || 2 + ||D i || 2 ) (4.9) = M m=1 log P(y m |I m ) - α 0 2 p i=1 α i (||V i || 2 + ||D i || 2 ) (4.10) = M m=1 y m log σ(det L Im ) + (1 -y m ) log(1 -σ(det L Im )) (4.11) - α 0 2 p i=1 α i (||V i || 2 + ||D i || 2 )
Following [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], α i is an item regularization weight that is inversely proportional to item popularity, that prevent from overfitting.

Optimization. We maximize the log-likelihood using stochastic gradient ascent with Nesterov's Accelerated Gradient, which is a form of momemtum. To simplify notation, we define

[m] . = I m and σ m = σ(w det L [m] ). Let i ∈ {1, • • • , p}, k ∈ {1, • • • , r},
Lemma 2. When D is fixed, the gradient of (4.9) with respect to V ik is

∂f ∂V ik = 2w m,i∈[m] ([L -1 [m] ] :,i V :,k ) y m -σ m σ m det L Im -α 0 α i V ik (4.12)
Proof Without the regularization term we have

∂f ∂V ik = m,i∈[m] y m σ m ∂σ m ∂V ik + 1 -y m 1 -σ m - ∂σ m ∂V ik (4.13) = w m,i∈[m] y m -σ m σ m ∂ det L [m] ∂V ik (4.14) = w m,i∈[m] y m -σ m σ m tr L -1 [m] ∂L [m] ∂V ik det L Im (4.15) = 2w m,i∈[m] ([L -1 [m] ] :,i V :,k ) y m -σ m σ m det L Im (4.16)
where (4.16) follows from

∂L [m] ∂V ik s,t = V sk δ i,t + V tk δ i,s (4.17) Therefore, tr L -1 [m] ∂L [m] ∂V ik = s,t (V sk δ i,t + V tk δ i,s )[L -1 [m] ] s,t (4.18) = s [L -1 [m] ] s,i V sk + t [L -1 [m] ] i,t V tk = 2 s [L -1 [m] ] s,i V sk (4.19)
adding the derivative of the regularization concludes the proof.

Lemma 3. When V is fixed, the gradient of (4.9) with respect to

D i is ∂f ∂D ii = 2w m,i∈[m] ([L -1 [m] ] i,i D i,i ) y m -σ m σ m det L [m] -α 0 α i D ii (4.20)
Proof As shown previously and without the regularization term we have

∂f ∂V ik = w m,i∈[m] y m -σ m σ m tr L -1 [m] ∂L [m] ∂D i,i det L Im (4.21) Since, ∂L [m] ∂D i,i s,t = 2D i,i δ s,i δ t,i (4.22) we see that tr L -1 [m] ∂L [m] ∂D i,i = 2[L -1 [m] ] i,i D i,i (4.23)
adding the derivative of the regularization concludes the proof.

Multi-Task DPP

We now propose a modification to the previously introduced model that is better suited for the basket completion task. To do so we enhance the Logistic dpp for the basket completion scenario, where we model the probability that the user will purchase a given set of items. Here we formulate this with a Multi-Task dpp, where the goal is to predict whether the user will purchase a given target item Set V 0 ∼ N (0, 0.01) everywhere and Ṽ0 ≡ 0 the gradient accumulation on V .

while not converged do if b(t + 1) > M (T + 1) then Shuffle D and set based on the user's basket. We think that such a model is more suitable for basket completion because it will capture directed completion rules. Indeed, in some cases it may be a good idea to recommend item B to basket containing item A, but not the other way around. See the pillow-couch example in the related work. In this setting, there are as many slices in the tensor as there are items in the catalog that is p. Learning one kernel per item would be impossible in practice and suffer from sparsity issues. Indeed, with one kernel per item, each target item would be present in only a fraction of the baskets, and thus dramatically reduce the size of the training set per kernel. To solve this issue we use a low-rank tensor point of view. We define a cubic tensor L ∈ R p×p×p , where each slice τ (noted L τ ) of L is the target item (low-rank) kernel. By assuming that the tensor L is low-rank, we are able to implement sharing of learned parameters between target items, as defined by the following equation:

T = T + 1 end if Update ( Ṽt+1 , Dt+1 ) = β( Ṽt , Dt ) + (1 -β)ε f (V t + β Ṽt , D t + β
Definition 7 (L kernel matrix of Multi-Task DPP, figure 4.1).

L τ = V R 2 τ V T + D 2 (4.24)
where V ∈ R p×r are the item latent factors that are common to all items, and R τ ∈ R r×r is a target specific matrix that models the interactions between the latent components of each target item. In order to balance the degrees of freedom between targets and items, we further assume that R τ is a diagonal matrix. Therefore, the diagonal vector of R τ models the latent factors of each target, and the latent factors of the item can be seen as the relevance of the product for each latent factor.

As in the case for the matrix D, the squared exponent on R τ in definition 4.24 ensures that we always have a valid kernel. This decomposition is similar to the RESCAL decomposition [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF], introduced in section 3.6.2) without the additional bias term and a diagonal constraint on the slice specific matrix. Besides we also have a different learning procedure due to the use of the logistic function.

Finally, the probability that a set of items I will be successful for target τ is

P(y τ = 1|I) = σ(w det L τ,I ) = 1 -exp(-w det L τ,I ) (4.25)
Therefore, the log-likelihood is

g(V, D, R) = log M m P(y τ |[m]) - α 0 2 p i=1 α i (||V i || 2 + ||D i || 2 + ||R i || 2 ) (4.26) = M m log P(y τ |[m]) - α 0 2 p i=1 α i (||V i || 2 + ||D i || 2 + ||R i || 2 ) (4.27)
Since each observation m is attached to a task, we denote τ m the task that corresponds to observation m. Thus we have σ m = σ(det L τm,[m] ). When there is no ambiguity, we also denote

L [m] . = L τm,[m] . Let i ∈ {1, • • • , p}, k ∈ {1, • • • , r},
Lemma 4. When D and R are fixed, the gradient of (4.26) with respect to V ik is

∂g ∂V ik = 2w m,i∈[m] y τm -σ m σ m R 2 τm,k,k [L -1 τm,[m] ] :,i • V :,k det L τm,[m] (4.28) -α 0 α i V ik
Proof Without the regularization term we have

∂g ∂V ik = m,i∈[m] y τm σ m ∂σ m ∂V ik + 1 -y τm 1 -σ m - ∂σ m ∂V ik (4.29) = w m,i∈[m] y τm -σ m σ m ∂ det L [m] ∂V ik (4.30) = w m,i∈[m] y m -σ m σ m tr L -1 [m] ∂L [m] ∂V ik det L [m] (4.31) (4.32) Since, [L τ ] s,t -D 2 s,t = r j=1 [V R 2 τ ] s,j V t,j = r j=1 V s,j R 2 τ,j,j V t,j (4.33) we have ∂L [m] ∂V ik s,t = R 2 τ,k,k (V t,k δ s,i + V s,k δ t,i ) (4.34) Thus, tr L -1 [m] ∂L [m] ∂V ik = 2R 2 τ,k,k s∈[m] [L -1 τm,[m] ] s,i V s,k (4.35)
adding the regularization concludes the proof.

Lemma 5. When V and R are fixed, the gradient of (4.26) with respect to D i,i is

∂g ∂D i,i = 2w m,i∈[m] y τm -σ m σ m [L -1 tm,[m] ] i,i D i,i det L Im (4.36) -α 0 α i D ii
Proof Similarly without the regularization term we have

∂g ∂D i,i = w m,i∈[m] y m -σ m σ m tr L -1 [m] ∂L [m] ∂D i,i det L [m] (4.37) Using (4.33) ∂L [m] ∂D i,i s,t = 2D i,i δ s,i δ t,i (4.38) thus tr L -1 [m] ∂L [m] ∂D i,i = 2[L -1 tm,[m] ] i,i D i,i (4.39)
adding the regularization concludes the proof.

Lemma 6. When V and D are fixed, the gradient of (4.26) with respect to R k,k is

∂g ∂R τ,k,k = 2w m,τ ∈[m] y τ -σ m σ m R τ,k,k L -1 [m] • V :,k • V T :,k det L [m] (4.40) -α 0 α τ R τ,k,k,
Proof Similarly without the regularization we have

∂g ∂R τ,k,k = w m,i∈[m] y τ -σ m σ m tr L -1 [m] ∂L [m] ∂R τ,k,k det L [m] (4.41) (4.42) Using (4.33) ∂L [m] ∂R τ,k,k s,t = 2R τ,k,k V s,k V t,k (4.43) we obtain tr L -1 [m] ∂L [m] ∂R τ,k,k = 2R τ,k,k s,t∈[m] [L -1 [m] ] s,t V s,k V t,k (4.44)
adding the regularization concludes the proof.

Prediction

As previsouly discussed, sampling from a dpp can be a difficult problem, and various solutions have been proposed [START_REF] Han | Faster greedy MAP inference for determinantal point processes[END_REF], Gillenwater et al., 2014, Gautier et al., 2017, Chen et al., 2017]. Although sampling the best set among all possible set has been conjectured to be NP-hard, our goal is to find only the best item to complete the basket. In such applications a greedy approach can be applied effectively, especialy with the low-rank structure of our model. In addition, [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF] proposed an effective method for the basket completion scenario that involves conditioning the dpp, which can be applied to our Logistic dpp model.

Experiments

We evaluated the performance of our models on the basket completion problem on several real-world datasets, and compared it to several state-of-the-art baselines.

MODELS

• Our models. To understand the impact of the different components of our model compared to the low-rank dpp model, we evaluated the following versions of our model: Set V 0 ∼ N (0, 0.01) everywhere and Ṽ0 ≡ 0 the gradient accumulation on V . Set R τ,0 ∼ N (1, 0.01) on the diagonal for each task and Rτ,0 ≡ 0 the gradient accumulation on R τ .

while not converged do if b(t + 1) > M (T + 1) then Shuffle D and set

T = T + 1 end if Update Ṽt+1 , Dt+1 , ( Rτ,t+1 ) τ = β Ṽt , Dt , ( Rτ,t ) τ +(1-β)ε g(V t +β Ṽt , D t +
β Dt , (R τ,t + β Rτ,t ) τ ) according to formulas (4.28), (4.36) and ( 4 To determine what item to recommend we use a greedy approach, where we select the next item such that the probability of the basket completed with this item is the largest.

.40) Update V t+1 = V t + Ṽt+1 Update D t+1 = D t + Dt+1 Update R τ,t+1 = R τ,t + Rτ,
-Multi-Task log-DPP without bias: In this version we set D ≡ 0, which allows us to measure the impact of capturing the item bias in a separate matrix. The matrix V encodes the latent factors of items present in the basket, while each matrix R τ encodes the latent factors of each target item τ to add to a basket.

-Multi-Task log-DPP: This is the full version of our model, with bias enabled.

Our datasets do not provide explicit negative information. To generate negative feedback for our models we created negatives targets from observed baskets by sampling a random item among those items not in the basket. This approach could be improved through better negative sampling strategies, but since this is not part of our primary contributions we leave this investigation for future work.

• Baselines. The primary goal of our work is to improve state-of-the-art results provided by dpps and introduce new modeling enhancements to dpps. However, for the sake of completness we also compare with other strong baseline models provided by state-of-the-art collaborative filtering approaches.

-Poisson Factorization (PF) [START_REF] Gopalan | Scalable recommendation with poisson factorization[END_REF] is a probabilistic matrix factorization model generally used for recommendation applications with implicit feedback. Since our datasets contain no user id information, we consider each basket to be a different user, and thus there are as many users as baskets in the training set. In practice this can cause memory issues, since the number of baskets can be very large.

-Factorization Machines (FMs) [Rendle, 2010] is a general approach that models dth-order interactions using low-rank assumptions. FMs are usually used with d = 2, since this corresponds to classic matrix factorization, which is the value we use here. As with PF, to learn the FM we consider each basket as a unique user. For fairness in comparison with our models, we also tried a FM with negative sampling based on item popularity. However, we did not see any substantial improvement in model performance using this negative sampling technique.

-Low-Rank DPP [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF] is a low-rank dpp model, suitable for basket completion and other tasks, where the determinant of the subkernel corresponds to the probability that all the items will be bought.

-Bayesian Low-RankDPP [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF] is the Bayesian version of the low-rank dpp model.

-Associative Classifier (AC), detailed in section 4.5.1, is a algorithm that computes support of bought set items in order to obtain completion rules. As [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], we used the Classification Based on Associations (CBA) algorithm [START_REF] Liu | Integrating classification and association rule mining[END_REF]], available at [Coenen, 2005], with minimum support of 1.0% and maximum confidence thresholds of 20.0%. Unlike other models, AC do not provide estimates for all possibles sets. Thus some metrics can not be computed like the MPR, detailed below, that we will use.

-Recurrent Neural Network (RNN) [START_REF] Hidasi | Session-based recommendations with recurrent neural networks[END_REF] adapted for session-based recommender system. RNN requires ordered sequences, thus we will only test this model performance on our dataset where the ordering of the purchases within each basket is available. We use the code of [START_REF] Songweiping | Songweiping[END_REF].

In the interest of reproducibility, all model implementations codes are available at [Warlop, 2018].

DATASETS. For our basket completion experiments we use the following three datasets, previously describe in section 2.2.2:

• Amazon Baby Registries For the purposes of comparison with [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF], we perform two experiments. The first experiment is conducted using the diaper category, which contains 100 products and approximately 10k baskets, composed of 2.4 items per basket on average. The second experiment is performed on the concatenation of the diaper, apparel, and feeding categories (sometimes noted here D.A.F for Diaper+Apparel+Feedings), which contains 300 products and approximately 17k baskets, composed of 2.6 items per basket on average. Let recall that since the categories are disjoint, no basket containing diaper products will be observed containing apparel products, for example. This concatenation of disjoint categories may present difficulties for classic matrix factorization models [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF], which may prevent these models from learning a good embedding of items.

• Belgian Retail Supermarket the entire dataset was used. AC could not be trained on this dataset because AC does not scale with large item catalogs.

• UK retail the entire dataset was used. Because of the presence of very large baskets, low-rank dpp requires a very large number of latent factors leading to somewhat poor results for this model. This is not an issue for our model, due to the item bias that is captured in a separate matrix. However, for purposes of comparison, we have removed all baskets containing more than 100 items, but the low-Rank dpp still requires 100 latent factors to model these baskets. AC could not be trained on this dataset because AC does not scale with large item catalogs.

• Instacart is the only public dataset that we know of, that contains ordered sequences of purchase. Because of memory issues, we only used the "train" dataset, removed items that appeared less than 15 times and basket of size lower than 3.

We tested both the accuracy of our models and the ability of our Multi-Task dpp algorithm to capture directed completion rules. For accuracy we used Amazon, Belgian Retail Supermarket and UK retail datasets and compared all previously introduced algorithms except the RNN model since it requires ordered sequences which is not the case with these datasets. The Instacart dataset was then used to validate our hypothesis on capturing directed completion rules by comparing the performance of Low-Rank dpp, RNN and Multi-Task dpp on various experimental protocols.

Accuracy

For model evaluation we use a random split of 70% of the data for training, and 30% for testing. For each basket in the test set we remove one item at random. We then evaluate the model prediction according to the predicted score of this removed item using the metrics described below.

METRICS.

To evaluate the performance of each model we compute the Mean Percentile Rank (equation 2.9) and precision@k (equation 2.10) for k = 5, 10 and 20. 4.1 we see that classic collaborative filtering models sometimes have difficulty providing good recommendations in this basket-completion setting. Perhaps more surprising, but already described in [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF], is that except for the Belgian dataset, PF provides MPR performance that is approximately equivalent to a random model. For the Amazon diaper dataset this poor performance may be a result of the small size of each basket (around 2.4 items per basket on average), thus each "user" is in a cold start situation, and it is difficult to provide good predictions. Poor performance on the diaper+apparel+feedings Amazon's dataset may result from the fact that, apart from the small basket size of 2.61 items on average, this dataset is composed of three disjoint categories. These disjoint categories can break the low-rank assumption for matrix factorization-based models, as discussed in [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF]. This issue is somewhat mitigated by FM, due to the integration of an item bias into the model. This item bias allows the model to capture item popularity and thus provide acceptable performance in some cases. Low Rank DPP vs Multi-Task DPP. We now turn to a performance comparison between our primary baseline, the low-rank dpp model, and our model, where the relative improvements are highlighted in Table 4.2. We see that our approaches provide a substantial increase in performance for both Amazon datasets, with improvements between 10% and 70%. The first reason is that unlike the low-rank dpp, which models the probability that a set of items will be bought together, our approach directly models the basket completion task. In our Multi-Task dpp model, the extra dimensions allow the model to capture the correlation between each item in the basket and the target item, as well as the global coherence of the set.

RESULTS. Looking at Table

Regarding the three-category Amazon dataset, a good model should not be impacted by the fact the all the three categories are disjoint. Thus the precision@K scores should be approximately the same for both the single category and three-category datasets, since we observed similar performance for each category independantly. Since the MPR is 78% for one category, the MPR on the three-category dataset should be around 93%, since on average for each category the target item is in 22nd position over 100 items. Therefore, the target item should be in 22nd position over the 300 items, resulting in a MPR of 1 -22/300 = 93%. Our models come close to those numbers, but still exhibit some small degradation for the three-category dataset. Finally, we note that for this dataset, a model that samples an item at random from the right category would have a precision @20 of 20%, since there are 100 items per category. The low-rank dpp model provides close to this level of performance. Taken together, these observations indicate that our model is robust to the disjoint category problem, and explains the 70% relative improvement we see for our model on the precision@20 metric. On the UK retail dataset the improvements of our algorithm are still substantial for precision@K, model r MPR Prec.@5 Prec.@10 Prec.@20 with relative improvement between 20% and 30% (MPR is down by 5%). We also observe the same decrease in MPR for our Logistic dpp model, but precision@K similar to the low-rank dpp. Finally, on the Belgian Retail dataset we see that all models provide similar performance. For this dataset, baskets come from an offline supermarket, where it is possible that customers commonly purchased similar products at specific frequencies. Consequently it may be easy to capture frequent associations between purchased items, but very difficult to discover more unsual associations, which may explain why all models provide approximately the same performance.

Logistic DPP vs Multi-Task DPP. To better understand the incremental performance of our model, we focus on the results of the Logistic dpp and the Multi-Task dpp models. We see that the single-task model does not improve over the low-rank dpp on average, indicating that the logistic component of the model does not contribute to improved performance. However, we argue that this formulation may still be valuable in other classification applications, such as those with explicit negative feedback. For the Multi-Task dpp model, we see that the version of this model without bias is responsible for almost all of the performance improvement. Some additional lift is obtained when capturing the item popularity bias in a separate matrix. Since most of the gain comes from the multi-task kernel, one may ask if we could use the multi-task kernel without the logistic function and obtain similar results. We believe that this is not the case for two reasons. First, since we are clearly in a classification setting, it is more appropriate to use a logistic model that is directly tailored for such applications. Second, without the logistic function, each slice of the tensor should define a probability distribution, meaning that the probability of purchasing an additional product should sum to one over all possible baskets. However, we could add an arbitrarly bad product that no one would ever buy, resulting in a probability of 0 for buying that item in any basket, which would break the distributional assumption. model protocol MPR Prec.@5 Prec.@10 Prec.@20 Low Rank DPP

(

Capturing directed completion rules

In order to validate the capacity of our model to capture directed completion rules we performed three experimental protocols on the Instacart dataset, which is the only one to have ordered sequences. Each protocol vary in the way we removed the item to predict from the basket:

1. As for previous experiements, we removed one item at random. For Low-Rank dpp this is done only in the test set, for Multi-Task dpp both for training and test sets.

2. We removed the last added item to the basket. For Low-Rank dpp this is done only in the test set, for Multi-Task dpp both for training and test sets.

Since we considered ordered sequence, we also tested the RNN model here.

3. We removed one item at random in the training set, and the last added item in the test set. Here we only evaluate the performance of our Multi-Task dpp.

RESULTS. First, looking at table 4.3 and comparing Multi-Task dpp results of protocols ( 2) and (3), we see that the algorithm is much more precise to predict the last added item in the test set when training is also done by removing the last added item. This support the idea that the order in which the items are added in the basket plays an important role, otherwise both protocols would give similar results. Second, comparing results of protocols ( 1) and ( 2), we see that Multi-Task dpp performance is lower when trained to predict a randomly removed item than when trained to predict the last added item whereas it is the other way around for Low-Rank dpp but by a smaller margin. This further support the fact that Low-Rank dpp, although well suited to compute co-occurence probabilities, misses directed completion rules. Finally, we see that, quite surprisingly, RNN model does not obtain a good performance. This poor performance may come from the fact that the basket length are too small for the RNN to learn correctly.

Related Work

The topics of dpps, basket completion, and diversity have received significant attention in the past several years.

Basket Completion

The problem of basket completion, introduce in subsection 2.1.2 is a particular problem in session-based recommender systems, where the basket (also called the cart) refers to all of the products that a user has saved and is about to purchase. The goal is to recommend one or several items that the user could add to the basket.

Theoretically this problem could be addressed using MDPs, where one would look for the next item to show based on the items the user has previously interacted with [START_REF] Shani | An mdpbased recommender system[END_REF]) but those techniques are very difficult to scale with very large items catalogs, since the state space is large and learning transition probabilities and rewards will be infeasible. One solution for addressing the basket completion problem would be to use the classic collaborative filtering approach that considers each basket as a new user. However such an approach has many drawbacks. From a computational and storage point of view, this approach would hugely increase the size and the sparsity of the user-item interaction matrix, making matrix completion very difficult. Other limitations include short dependencies and the global coherence of the set of items (basket) required for basket completion, which are not taken into account with a conventional collaborative filtering approach. Indeed, the first choice of the user must condition the rest of the recommendations, which may not be possible if the recommendation are only updated in an offline fashion (for instance every night). Additionally, item associations may be directed links: if a user is buying a couch, she may add a pillow to her cart, but the other direction is much less likely. Such directed interactions are not tackled by state-of-the-art collaborative filtering approaches like matrix factorization. Since the similarity computation using latent factors in a matrix factorization model is commutative, there is nothing that prevents the system from recommending a couch to someone who is about to purchase a pillow. Furthermore, if one pillow is frequently purchased with one couch and just as frequently with another couch, matrix factorization is likely to recommend a second couch to someone about to purchase the first one, which is even more uncommon.

Associative classification is a simple method that uses association rules to solve basket completion. More advance methods based on dpps have shown very good accuracy and improve diversity in the recommendation. Recently deep learning techniques based on recurrent neural networks have been developed for this task.

With Associative Classification

To solve the basket completion problem, Associative Classifiers have long been the state-of-the-art [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], Hipp et al., 2000, Liu et al., 1998], despite requiring very heavy computational load for training, and manual tuning for key pa-rameter choices such as lift and confidence thresholds. The objective of the Associative Classifier is to find frequent itemsets in order to extract association rules, for instance "Propose item A to anyone that has B and C in her basket". In our application this mean that many different users have purchased the same set of products within one session. However, the basket completion problem is a directed problem, if the itemset (A, B) (where A and B can represent one or several items) appeared frequently, it does not necessarily means that one must recommend B to anyone who bought A. With associative classification this problem is addressed by computing the confidence of a rule ( [START_REF] Hahsler | arules -A computational environment for mining association rules and frequent item sets[END_REF]):

Definition 8 (Confidence rule). conf(A → B) = supp(A ∪ B) supp(A) (4.45)
where supp(A) is the support of A, that is, the number of times product A has been observed in a basket. The idea is to weight the support of the item set (A, B) based on the support of A. Indeed, the associations (A, B) may have been observed frequently only because A is one of the most popular items. Let us illustrate this by the "pillow-couch" problem shown in table 4.4. The set (pillow, couch) appears quite often, and one may recommend one of these items if someone has purchased the other item. However conf (pillow → couch) = 2575/12432 ≈ 0.21, and conf (couch → pillow) = 2575/3021 ≈ 0.85, which shows that one may recommend a pillow to a couch buyer but not the other way around. This confidence score can be seen as an estimate of the probability of (observing the association) A ∪ B, knowing A ( [START_REF] Hipp | Algorithms for association rule mining -a general survey and comparison[END_REF]). In practice one must fix a threshold in order to select only relevant rules. A good association rule must satisfy both a minimum support and confidence score at the same time. However in order to not reduce to most popular associations and loose the interest of users, the selection must be made among medium to low support thresholds, and too many associations may be returned by this selection strategy. Among other possibilities, a common solution is to filter out association rules based on an additional relevancy measure. [START_REF] Brin | Dynamic itemset counting and implication rules for market basket data[END_REF] proposed a measure, called lift, that weights the support of the set union by the support of each subset independantly:

Definition 9 (Lift rule).

lift(A → B) = supp(A ∪ B) supp(A)supp(B) (4.46)
Thus high lift indicates strong association. Association Classification has several limits. The first one is that one must manually choose thresholds for minimum support, confidence, and lift before outputing the recommendation. The second is the high computational load of the system, which increases with the number of transactions, the length of the average transaction, and the number of recommendations to produce (see [START_REF] Tan | Association analysis: Basic concepts and algorithms[END_REF]). Because of these constraints, it is in practice impossible to apply Association Classification to large item catalogs. To overcome these issues, some work uses Determinantal Point Processes to model and learn the distribution of items co-occurences.

With Determinantal Point Processes

Several previous works proposed the use of dpps and leverage their repulsive behaviour to model the probability of observing a set of items, and then use this model to produce basket-completion recommendation. In contrast to this work, we directly model the probability of purchasing a particular item according to the products in the basket. [START_REF] Gillenwater | Expectation-maximization for learning determinantal point processes[END_REF] proposed an Expectation-Maximization algorithm to learn a full-rank kernel while [START_REF] Mariet | Fixed-point algorithms for determinantal point processes[END_REF] relied on a fixedpoint algorithm. However when dealing with very large item catalogs learning a full-rank kernel can be infeasible. To resolve this issue, [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF] (respectively [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF]) proposed a (respectively bayesian) low-rank dpp.

They assume that the kernel K can be factorized into K = V V T where the number of columns of V , that is the rank of the kernel, is much smaller than the catalog size, which enables faster learning and predication algorithms that can scale to larger catalog. Furthermore, low-rank dpps often have better predictive performance than full-rank dpp due to the use of an appropriate regularization.

With Recurrent Neural Networks

Recently, deep learning techniques have been investigated to provide solutions for session-based recommender systems. The problem can be seen as predicting the next item, and has already been investigated in natural language processing to produce word embeddings by learning to predict the next word using deep learning ( [Mikolov et al., 2013a[START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF], Chen, 2017]). In both applications (words or recommender systems) each item is map to its unique position in a dictio-

𝑖 1,2 𝑖 1,1 𝑖 1,4 𝑖 1,3 𝑖 2,2 𝑖 2,1 𝑖 2,4 𝑖 2,3 𝑖 3,2 𝑖 3,1 𝑖 3,3 𝑖 4,2 𝑖 4,1 𝑖 5,2 𝑖 5,1 𝑖 5,4 𝑖 5,3 𝑖 2,5 session 1 session 2 session 3 session 4 session 5 Mini-batch 1 Mini-batch 2 Mini-batch 3 Mini-batch 4 input output 𝑖 1,1 𝑖 2,1 𝑖 3,1 𝑖 1,2 𝑖 2,2 𝑖 3,2 𝑖 1,2 𝑖 2,2 𝑖 3,2 𝑖 1,3 𝑖 2,3 𝑖 4,1 𝑖 5,1 𝑖 2,4 … 𝑖 1,3 𝑖 2,3 𝑖 3,3 𝑖 1,4 𝑖 2,4 𝑖 4,2 𝑖 5,2 𝑖 2,5 … Figure 4.2: Session-parallel mini-batch creation.
nary of size the vocabulary or catalog size. [START_REF] Hidasi | Session-based recommendations with recurrent neural networks[END_REF] proposed a Recurrent Neural Network solution to tackle the session-based recommendation problem. For such models, the training set usually consists of a unique very long sentence by concatenating all sentences and mini-batch learning is applied by extracting a portion of the text with a sliding window. When applied to session-based recommendation, [START_REF] Hidasi | Session-based recommendations with recurrent neural networks[END_REF] observed poor performance with this approach. This problem comes from the fact that sessions can have very different length that can be very short or very long and significant amounts of information are lost when breaking down sessions. This issue can be solved with an appropriate mini-batching logic: first sessions are ordered, then the first mini-batch is created by selecting the first event of the first X sessions with the second event as an output. The second minibatch is then formed from the second and third events and so on. When a session comes to an end the next available session is appended to it. See Figure 4.2. Several variations of this appraoch have been developed to further improved RNNs for the basket-completion task, by adding multiple types of features like text and image ( [START_REF] Hidasi | Parallel recurrent neural network architectures for feature-rich sessionbased recommendations[END_REF], with explicit context ( [Twardowski, 2016]) or by taking some temporal dynamics into account ( [START_REF] Smirnova | Contextual sequence modeling for recommendation with recurrent neural networks[END_REF]).

Determinantal Point Processes

In addition to the previously discussed work, dpps have been used for natural language processing in order to discover diverse threads of documents [START_REF] Gillenwater | Discovering diverse and salient threads in document collections[END_REF], and to enhance diversity in recommender systems [Foulds andGörür, 2013, Chen et al., 2017]. Unlike our application where we learn the kernels, in these applications the kernel is provided using previously obtained latent factors, for instance using tf-idf for [START_REF] Gillenwater | Discovering diverse and salient threads in document collections[END_REF]. These latent factors are scaled by a relevance score learned in a more conventional fashion. For example, these relevance scores may represent the predicted ratings of a particular user on each item/document, or the similarity between the text in a document and the user query. Ultimately, these applications involve sampling from the dpp specified by this kernel, where the kernel parameters trade off between relevance and diversity. However, sampling from such a dpp efficiently is difficult, and this has lead to work on different sampling techniques.

Ref. [START_REF] Han | Faster greedy MAP inference for determinantal point processes[END_REF], Gillenwater et al., 2014, Gautier et al., 2017] rely on MCMC sampling, while [START_REF] Chen | Improving the diversity of top-n recommendation via determinantal point process[END_REF] proposes a greedy solution based on Cholesky decomposition.

Several algorithms have been proposed for learning the dpp kernel matrix. Ref. [START_REF] Gillenwater | Expectation-maximization for learning determinantal point processes[END_REF] uses an expectation-maximization (EM) algorithm to learn a non-parametric form of the dpp kernel matrix. Ref. [START_REF] Mariet | Fixed-point algorithms for determinantal point processes[END_REF] proposed a fixed-point algorithm called Picard iteration, which proved to be much faster than EM, but still slower than [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF]. Bayesian learning methods have also been proposed to learn the dpp kernel [START_REF] Gartrell | Bayesian low-rank determinantal point processes[END_REF], Affandi et al., 2014].

Diversity

Improving diversity in recommender systems has also been studied without the use of dpps, including, among other work, in [START_REF] Christoffel | Blockbusters and wallflowers: Accurate, diverse, and scalable recommendations with random walks[END_REF], Puthiya Parambath et al., 2016, Teo et al., 2016, Vargas and Castells, 2014, Paudel et al., 2017]. For instance, [START_REF] Christoffel | Blockbusters and wallflowers: Accurate, diverse, and scalable recommendations with random walks[END_REF] relies on random walk technics to enhance diversity. In [Puthiya Parambath et al., 2016], the authors propose trading off between the relevance of the recommendation and diversity by introducing a coverage function to force the algorithm to produce recommendations that cover different centers of interests of each user. Ref. [START_REF] Paudel | Fewer flops at the top: Accuracy, diversity, and regularization in two-class collaborative filtering[END_REF] proposes extensions of logistic matrix factorization for two-class collaborative filtering. One of the methods presented in this paper learns two sets of latent item factors, one for each class, that represent positive and negative feedback, and show the effectiveness of this approach in producing recommendations that better cover the catalog while maintaining accurate recommendations. Finally, the authors of [START_REF] Vargas | Improving sales diversity by recommending users to items[END_REF] propose transforming the problem of recommending items to users into recommending users to items. They introduce a modification of nearest-neighbor methods, and a probabilistic model that allows isolation of the popularity bias and favors less popular items.

Industrial learnings

For a long time, associative classifiers have been used at fifty-five for basket completion problems. However, large catalog sizes and large number of baskets to process always made associative classifiers difficult to use. Other limits for industrial applications include the choice of the different thresholds which blur the results and the infeasibility of performing real-time predictions. Indeed with associative classifers, the associations rules have to be computed offline and recommendation are generated thanks to a look up table, which is impossible in practice. Low-rank dpp and the solution of [START_REF] Gartrell | Lowrank factorization of determinantal point processes[END_REF] then became the new production solution and subsequently Logistic dpp because of its better accuracy. dpp solutions have the advantage in terms of computation time and prediction time. Indeed it is easy to generate a recommendation for a basket that has never been previously seen.

Conclusion

In this section we have proposed an extension of the dpp model that leverages ideas from tensor factorization. While our model can be applied to a number of machine learning problems, we focus on the problem of basket completion. We have shown through experiments on several datasets that our model provides signficant improvements in predictive quality compared to a number of competing state-ofthe-art approaches. Besides, we showed that for basket completion, there may be a significant signal in the order in which items are added to the basket, and, unlike state-of-the-art dpps solutions, our Multi-Task dpp appropriately captures this signal. In future work we plan to investigate other applications of our model, such as user conversion prediction, attribution, and adversarial settings in games. We also plan to investigate better negative sampling methods for positive-only and unlabelled data. Finally, we also plan to investigate other types of loss functions, such as hinge loss, and other types of link functions for dpps, such as the Poisson function, to tailor dpps for regression problems. We believe that this work will allow us to customize dpps so that they are suitable for many additional applications.

Fighting Boredom in Recommender Systems with Linear Reinforcement Learning

The goal of A/B testing is to discover the best option between two alternative strategies. This implicitly assumes that the best option is indeed to exclusively execute either A or B. We argue that this assumption, which is common in many recommender systems, is rarely verified in practice and that alternating between different solutions (possibly more than two solutions) with the right frequency may significantly improve the performance with respect to sticking to the best fixed one. This performance improvement is rooted into the dynamics of the recommendation process. A user may get bored if shown too many movies of the same genre in a short time, while she may get interested in it again, if enough time passed since the last time she watched a movie of that genre. While fatigue variables are commonly integrated in recommender systems, their impact on the recommendation is often limited and they do not effectively take into consideration how recommendations themselves influence the preferences of users. In this section, we show that it is critical to estimate the dependency between the rewards (e.g., ratings, clicks, time usage, ...) and the past recommendations produced by the system in order to accurately make recommendation that will interest the user on the long term. We first cast the problem as a Markov Decision Process, where the rewards are a linear function of the recent history of actions, and we show that a policy taking into consideration how recommendations influence the rewards in the long run, may achieve a much better performance with respect to either fixed-action or even greedy policies (i.e., choosing the best action at each time step). We then introduce an extension of the ucrl algorithm (LinUCRL) for which we derive a regret bound that is independent of the number of states. Finally, we experimentally validate the model assumptions and the algorithm in a number of realistic scenarios.

Introduction

Consider a movie recommendation problem, where the recommender system selects the genre of movie to suggest to a user and then picks a movie from this genre. A very basic strategy is to evaluate user's preferences on genres and then keep recommending movies of the preferred genre. While this strategy is sensible in the short term, it completely overlooks the dynamics of the user's preferences due to the recommendation process itself. In fact, the user would rapidly get bored of the proposed genre and reduce the ratings accordingly. Notice that this is due to the recommendation strategy and not because of an actual change in the preferences of the user, as she would still like the genre as before had it not been proposed so often recently. Despite being clearly suboptimal and basic, the existence of an optimal fixed strategy is often assumed in recommender systems using, e.g., matrix factorization to estimate users' ratings and the best (fixed) item. Even learning strategies based on the multi-armed bandit (mab) model assume constant rewards and pursue the objective of selecting the (fixed) optimal arm as often as possible. Similarly, in A/B testing, we implicitly assume that once the best option (either A or B) is found, it should be constantly executed. An alternative approach is to estimate the state of the user (e.g., her level of boredom) as a function of the movies recently watched and determine how her preferences are affected by that. Thus we could design a contextual strategy that recommends the best genre depending on the actual state of the user. This strategy could be effectively learned using a linear bandit model, where the reward of an arm is a linear combination between the context and some unknown vector. While this could partially address the previous issue, we argue that in practice it may not be satisfactory. In fact, the state of the user directly depends on the sequence of movies recommended in the recent past and a recommendation strategy should take into consideration this dynamics to "drive" the user's state in the most favorable condition to gain as much reward in the long term, instead of following greedy strategy that selects the best "instantaneous" action at each step. For instance, consider a user with preferences 1) action, 2) drama, 3) comedy. After showing a few action and drama movies, the user may get bored. At this point a greedy contextual strategy would successfully move to recommending comedy, but as soon as it estimates that action or drama are better again (i.e., since they have not been watched for a while, their reward would go back to a higher value), it would immediately switch back to them. On the other hand, a more farsighted strategy may prefer to stick to comedy for a little longer to increase the preference of the user for action to its higher level, so as to fully exploit its potential. In this section, we propose to use a reinforcement learning model to fully capture this dynamical structure, where the reward (e.g., the average rating of a genre) depends on a state that summarizes the effect of the movies recently watched by the user on her preferences. We introduce a novel learning algorithm that effectively trades off exploration and exploitation and we derive theoretical guarantees for its performance.

Background

Linear bandit

We already discussed about multi-arm bandit and linear bandit in section 2.1.3. We will now introduce more theoretical background on linear bandit that will be leveraged in this chapter. Let recall that in linear bandit when arm a is pulled, the learner received a stochastic reward r a which is a linear function of a vector x a ∈ R d characterizing arm a, i.e, r a =< θ * , x a > +η, where θ * ∈ R d is an unknown parameter.

Following the principle of optimism in face of uncertainty leads to a solution called OFUL (Optimism in the Face of Uncertainty Linear bandit algorithm) the algorithm will select the next arm according to a trade-off between the prediction of the linear regression and a confidence interval on the prediction. Let X t be the matrix whose rows are x a 1 , • • • , x at with a τ is the arm pulled at time τ , Y t = [r a 1 , • • • , r at ], and let θt be the 2 -regularized least-squares estimate of θ * at time t with regularization parameter λ, then θt = (X T t X t + λI) -1 X T t Y t (5.1)

Then one can construct a confidence ellipsoid around θt where θ * lies with high probability:

Theorem 7 (simplify Theorem 2 of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF]).

Assume that ||θ * || 2 ≤ S and ||x a || 2 ≤ L for all arm a, then, for any δ > 0, with probability at least 1 -δ, for all t > 0 θ * lies in the set

C t =    θ ∈ R d : || θt -θ|| Vt ≤ R d log 1 + tL 2 /λ δ + λ 1/2 S    with V t = X T t X t + λI
Finally the system pulls the arm at time t according to the following rule (a, θt ) = arg max (a,θ)∈A×C t-1 < θ, x > (5.2)

Reinforcement Learning

In reinforcement learning, an agent interacts with the environment in order to maximize long term performance (see figure 5.1). To do that the agent selects an action to execute in each environment state in order to simultaneously learn the environment -the transition between states and the value of each state -and gather as much reward as possible. In such context, the agent choices have a direct impact on future observations that is future states. The agent is given a set of possible actions A, a set of possible states X of cardinality N but does not know anything about the dynamics -that is the transition probabilities between states and the reward available in each state. By moving inside this environment the agent collects information to estimate this dynamic. This environment is then defined as an MDP M = X , A, p, r , with p : X × X × A → R 3 which value p(y, x, a) holds the transition probability of moving to state y from state x when playing action a, and r : X × A → R is the (stochastic) reward obtained when playing a given action in a given state. A greedy approach can consist in exploring the environment randomly during a fixed amount of time and then decide what policy π : X → A to runwhat action to execute in each state -given gathered knowledge. In order to link collected knowledge with policy and dynamic, some definitions must be introduced.

Definition 10 (State value function in infinite time horizon with discount).

V π (x) = E[ ∞ t=0 γ t r(x t , π(x t ))|x 0 = x; π]
where 0 ≤ γ ≤ 1 is a discount factor, x t the state at time t and π the policy, that is the function that output which action to perform in state x.

Algorithm 9 The Value Iteration algorithm.

Input: reward function r and transition probabilities p. Initialization: Let V 0 ∈ R N while not converge do V k+1 = T V k end while Compute greedy policy after K updates: π K (x) = arg max a∈A [r(x, a) + γ y p(y|x, a)V K (y)] Definition 11 (Optimal policy and optimal value function).

π * = arg max π∈Π V π
in all the states x ∈ X , where Π is some policy set of interest. The corresponding value function is the optimal value function V * = V π .

Based on definition 10 we see that the value function measures the cumulated reward gathered by a given policy. The objective is then to find the optimal policy (or equivalently the optimal value function) that is the policy that gathers the maximal amount of rewards. To compute the optimal value function a solution consists in using the Bellman operator.

Definition 12 ((Optimal) Bellman Operator). For any W ∈ R N , the Bellman operator T π : R N → R N is defined as Proposition 8 ( [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF]). Under several common assumptions, the optimal value function is bounded, i.e ||V * || ∞ < ∞ and it is the unique fixed point of the optimal Bellman operator T . Furthermore, we have that ∀W ∈ R N , V * = lim k→∞ (T ) k W .

T π W (x) =
It can be shown that the (optimal) Bellman operator is a contraction, thus one can use the fixed-point theorem to estimate the optimal value function and the associated policy. The protocol to achieve this goal is called Value Iteration, see algorithm 9.

In practice Value Iteration is run until a certain difference between two sucessive values of the value function is reached. The proposition 9 gives guarantee on the policy once such a difference is reached.

Proposition 9 ( [Puterman, 1994]). If value iteration is stopped at iteration n when max s (u i+1 (s) -u i (s)) -min s (u i+1 (s) -u i (s)) ≤ ε/2 , then the greedy policy π n (s) = max a∈[K] [r(s, a) + u n (f (s, a))] is ε optimal (i.e., η π ≥ η * -ε).

After some exploration of the states, an estimation of the reward function r and transitions p can be computed. One can then applied the Value Iteration algorithm to decide how to behave in the future. However such an exploration can be really unefficient and take a very long time. An alternative can consist in applying an εgreedy policy that is acting at random ε% of the time and accordly to the computed policy otherwise. The policy can then be recomputed using Value Iteration from time to time. More efficient than the previous strategy, this variation can still be very suboptimal. To overcome this issue, [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]] leveraged a classic idea in reinforcement learning, optimism in face of uncertainty, to provide a more efficient exploration-exploitation algorithm. Indeed instead of acting accordly to a policy that has been evaluated using few feedbacks, their algorithm called ucrl, compute confidence intervals around rewards and transitions probabilities. This defined a set of plausible MDPs, each with an associated mean reward when playing the associated policy for an infinite time. The ucrl algorithm chooses the optimistic environment to select the new policy that is the MDP that obtain the highest mean reward. A new policy is then computed whenever a confidence interval is halved.

Problem Formulation

We consider a finite set of actions a ∈ {1, . . . , K} = [K]. We define the state s t at time t as the history of the last w actions, i.e., s t = (a t-1 , • • • , a t-w ), where for w = 0 the state reduces to the empty history. As described in the introduction, and unlike the standard mab setting, we expect the reward of an action a to depend on how often a has been recently selected (e.g., a user may get bored the more a recommendation is used). More formally, we introduce the recency function ρ(s t , a) = w τ =1 1{a t-τ = a}/τ , where the recency of an action decreases as 1/τ as it is selected τ steps ago. The choice of this 1/τ decrease is quite arbitrary and must be validated with the data. One may choose other form of decrease to define how fast users forget about the past, like for instance 1/τ2 , 1/ √ τ , or 1/ exp(τ ). If an action is often selected the recency is large, and the more recent the larger, while it decreases if not selected for a while. We define the (expected) reward function associated to an action a in state s as1 r(s t , a) = d j=0 θ * a,j ρ(s t , a) j = x T s,a θ * a , (5.5) where x s,a = [1, ρ(s, a), • • • , ρ(s, a) d ] ∈ R d+1 is the context vector associated to action a in state s and θ * a ∈ R d+1 is an unknown vector. Notice that for d = 0 or w = 0, this model reduces to the standard mab setting, where the first component θ * a,0 represents the expected reward associated to arm a. Eq. ( 5.5) extends this setting by assuming that the reward of an action is the sum between the "stationary" expected reward θ * a,0 and a polynomial of the recency ρ(s t , a). Such a formulation allows to capture any kind of evolution. With d = 1 their could be only decreasing or only increasing reward, but increasing the value of d allows to model more complexe evolution shapes. While the algorithmic solution we propose is agnostic to the definition of recency, in the next section we validate this model with real data that display some typical relationships between rewards and recency (i.e., monotonically decreasing or increasing and then decreasing) can be accurately approximated by a polynomial of small degree.

The formulation in Eq. (5.5) may suggest that this is just a specific instance of a linear bandit problem, where x st,a is the context for action a at time t and θ * a is the unknown vector. Nonetheless, in linear bandit the sequence of contexts {x st,a } t is not affected by the actions selected over time and the optimal action at time t is a * t = arg max a∈[K] x T st,a θ * a , 2 while in our model, x st,a actually depends on the state s t which summarizes the history of actions selected up to w steps in the past and an optimal policy should take into account its effect on the state to maximize the longterm average reward. We thus introduce the deterministic Markov decision process (MDP) M = S, [K], f, r with state space S enumerating the possible histories of actions of length w (note that |S| = K w which can be really large), action space [K], noisy reward function in Eq. (5.5), and a deterministic transition function f : S × [K] → S that simply drops the action selected w steps ago and appends the last action to the state, such that f

([a t-1 , • • • , a t-w ], a t ) = [a t , • • • , a t-w-1 ]. A policy π : S → [K]
is evaluated according to its long-term average reward as

η π = lim n→∞ E 1 n n t=1 r t (5.6)
where r t is the (random) reward associated to state s t and action a t = π(s t ). The optimal policy is thus π * = arg max π η π . While an explicit form for π * cannot be obtained in general, intuitively in our model an optimal policy may select an action with suboptimal instantaneous reward (i.e., action a t = π(s t ) is s.t. r(s t , a t ) < max a r(s t , a)) so as to let other (potentially more rewarding) actions "recharge" and select them later on. In general, this results into a policy that alternates actions with a fixed schedule/frequency. Indeed since the number of states and actions are finite, eventually one will visit a certain state twice and choose the same action as last time that will transite to the same next state as first time since transition are deterministic. More insights about this behavior are provided in the experimental section. Let η * = η π * be the optimal average reward, if the parameters θ * a were known, we could compute the optimal policy by using value iteration where a value function u 0 ∈ R S is iteratively updated as

u i+1 (s) = max a∈[K] r(s, a) + u i f (s, a) ,
(5.7) and a nearly-optimal policy is obtained after n iterations as π(s) = max a∈[K] [r(s, a)+ u n (f (s, a))]. Note that here the iteration process is ease because of the determinisc transition function. The objective of a learning algorithm is to approach the performance of the optimal policy as quickly as possible. This can be measured by the regret of an algorithm Alg, which compares the reward cumulated by Alg over T steps to the reward obtained by the optimal policy over the same amount of time, i.e.,

∆(Alg, T ) = T η * - T t=1 r(s t , a t ), (5.8)
where (s t , a t ) is the sequence of states and actions observed and selected by Alg and r(s t , a t ) is computed as in Eq. 5.5.

Model Validation on Real Data

In order to test the validity of our model to actually capture non stationnary behaviour in the recommendation process choices, we use the movielens-100k dataset [Herlocker et al., 1999a]. We consider a recommender system that decides the genre of movie to recommend to a user. The model introduced in the previous section predicts that user's preferences are strictly related to the number of movies of the same genre a user have recently watched (e.g., she may get bored about a genre after seeing too many of such movies and then getting interested again as time goes by without watching that genre). In order to verify this intuition, we sort ratings for each user using their timestamps to produce an ordered sequence of ratings. For different genres observed more than 10, 000 times, we compute the average rating (the reward) among all users for each value of the recency function ρ(s t , a) corresponding to the different states s t encountered in the dataset for a history window w = 10. The charts of Fig. 5.2 provides a first qualitative support for our model. In fact, the rating for comedy, action, and thriller genres is a monotonically decreasing function of the recency, hinting to the existence of a boredom-effect, so that the rating of a genre decreases with how many movies of that kind have been recently watched. On the other hand, drama shows a more sophisticated behavior where users "discover" the genre and increase the ratings as they watch more movies, but get bored if they recently watched "too many" drama movies. This suggests that in this case there is a critical frequency at which users enjoy movies of this genre. In order to capture the multiple shapes of dependency between rating and recency for different genre, in Eq. 5.5 we defined the reward as a polynomial of ρ(s t , a) with coefficients that are specific for each action a. In Table 5.1 we report the coefficient of determination R 2 of fitting the model of Eq. 5.5 to the dataset for different values of d and different genres. The results show how our model becomes more and more accurate as we increase the complexity of the model. Fig. 5.2 shows that even a small degree (d = 5) actually produces accurate reward predictions, suggesting that the recency does really capture the key elements of the state s and that a relatively simple function of ρ is enough to accurately predict the rating. This result also suggests that standard approaches in recommender systems, such as matrix factorization, where the rating is contextual (as it depends on features of both users and movies/genres) but static, potentially ignore a critical dimension of the problem that is related to the dynamics of the recommendation process itself.

In practice, this genre recommender system learned using our LinUCRL algorithm can be coupled with a classic recommender system (for instance using matrix factorization) that compute user-movie affinities to form an hybrid recommender system. Indeed, the genre recommender system first decide what genre to recommend in order to keep the user interesting by diversifying the recommendation, then the second system decides exactly what movie to recommend that match the genre. In july 2018, Netflix encourage its users through a little ad (see figure 5.3) to create different profiles according to the genre of movie their are in the mood to watch, which illustrate the interest of our algorithm that directly model the genre mood of a user.

We now have showed that our model can indeed capture dynamic dependency between preference and past choices. However in practice such historical data are not available and thus must be collected while minimizing the regret 5.8. This is what we solve in the next section.

Linear Upper-Confidence bound for Reinforcement Learning

The Learning Algorithm. LinUCRL directly builds on the ucrl algorithm [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and exploits the linear structure of the reward function and the deterministic and known transition function f . The core idea of LinUCRL is to construct confidence intervals on the reward function and apply the optimismin-face-of-uncertainty principle to compute an optimistic policy. The structure of LinUCRL is illustrated in Alg. 10. Let us consider an episode k starting at time t, LinUCRL first uses the current samples collected for each action a separately to compute an estimate θ t,a by regularized least squares, i.e., θ t,a = min θ τ <t:aτ =a x T sτ ,a θ -r τ 2 + λ θ 2 2 , (5.9) where x sτ ,a is the context vector corresponding to state s τ and r τ is the (noisy) reward observed at time τ . Let be R a,t the vector of rewards obtained up to time t when a was executed and X a,t the feature matrix corresponding to the contexts observed so far, then V t,a = X T t,a X t,a + λI ∈ R (d+1)×(d+1) is the design matrix. The closed-form solution of the estimate is θ t,a = V -1 t,a X T t,a R t,a , which gives an estimated reward function r t (s, a) = x T s,a θ t,a . Instead of computing the optimal policy according to the estimated reward, we compute the upper-confidence bound

r t (s, a) = r t (s, a) + c t,a x s,a V -1 t,a ,
(5.10) where c t,a is a scaling factor whose explicit form is provided in Prop. 11. Since the transition function f is deterministic and known, we then simply apply the value iteration scheme in Eq. 5.7 to the MDP M k = S, [K], f, r k and compute the corresponding optimal (optimistic) policy π k . It is simple to verify that ( M k , π k ) is the pair of MDP and policy that maximizes the average reward over all "plausible" MDPs that are within the confidence intervals over the reward function. More formally, let

M k = {M = S, [A], f, r , |r(s, a) -r t (s, a)| ≤ c t,a x s,a V -1 t,a
, ∀s, a}, Algorithm 10 The LinUCRL algorithm.

Notation: c t,a = R (d + 1) log Kt α 1 + taL 2 w λ + λ 1/2 B Init: Set t = 0, T a = 0, θ a = 0 ∈ R d+1 , V a = λI for rounds k = 1, 2, • • • do Initialize round k Set t k = t, ν a = 0 Compute θ a = V -1 a X T a R a Set optimistic reward r k (s, a) = x T s,a θ a + c t,a x s,a V -1 a Compute optimal policy π k for MDP (S, [K], f, r t ) Execute chosen policy πt k while ∀a ∈ [K], T a < ν a do Choose action a t = π k (s t ) Observe reward r t and next state s t+1 Update X at ← [X at , x st,at ], R at ← [R at , r t ], V at ← V at + x st,at x T st,at Set ν at ← ν at + 1, t ← t + 1 end while Set T a ← T a + ν a , ∀a ∈ [K] end for then we have that η π k ( M k ) ≥ max π,M ∈M k η π (M ).
Finally, LinUCRL execute π k until the number of samples for an action is doubled w.r.t. the beginning of the episode. The specific structure of the problem makes LinUCRL more efficient than ucrl, since each iteration of Eq. 5.4 thanks to Eq.5.7 has O(dSK) computational complexity compared to O(S 2 K) of extended value iteration (used in ucrl) due to the randomness of the transitions and the optimism over f . Theoretical Analysis. We prove that LinUCRL successfully exploits the structure of the problem and reduce its cumulative regret w.r.t. basic ucrl. We first make explicit the confidence interval in Eq. 5.10. Let assume that there exist (known) constants B and R such that θ * a 2 ≤ B for all actions a ∈ [K] and the noise is sub-Gaussian with parameter R. Let w = log(w) + 1, where w is the length of the window in the state definition, and L 2 w = 1-d+1 w 1-w , where d is the degree of the polynomial describing the reward function. Then, we run LinUCRL with the scaling factor

c t,a = R (d+1) log Kt α 1 + T t,a L 2 w λ + λ 1/2 B (5.11)
where T t,a is the number of samples collected from action a up to t. Then we can prove the following.

Theorem 10. If LinUCRL runs with a scaling factor in Eq. 5.11 over T rounds, then its cumulative regret is bounded as

∆(LinUCRL, T ) ≤ Kw log 2 8T K + 2c max 2KT log 1 + T L 2 w λ(d + 1) ,
where c max = max t,a c t,a which is obtained by replacing T t,a by T in Eq. 5.11.

We first notice that the per-step regret ∆/T decreases to zero as 1/ √ T , showing that as time increases, the reward approaches the optimal average reward. Furthermore, by leveraging the specific structure of our problem, LinUCRL greatly improves the dependency on other elements characterizing the MDP. In the general MDP case, ucrl suffers from a regret O(DS √ KT ), where D is the diameter of the MDP, which in our case is equal to the history window w. In the regret bound of LinUCRL the dependency on the number of states (which is exponential in the history window S = K w ) disappears and it is replaced by the number of parameters d + 1 in the reward model. Furthermore, since the dynamics is deterministic and known, the only dependency on the diameter w is in a lower-order logarithmic term. This result suggests that we can take a large window w and a complex polynomial expression for the reward (i.e., large d) without compromising the overall regret. Furthermore, LinUCRL compares favorably with a linear bandit approach. First, η * is in general much larger than the optimal average reward of a greedy policy selecting the best instantaneous action at each step. Second, apart from the log(T ) term, the regret is the same of a linear bandit algorithm (e.g., LinUCB). This means that LinUCRL approaches a better target performance η * almost at the same speed as linear bandit algorithms reach a worse greedy policy.

In order to prove Thm. 10, we first need the following proposition about the confidence intervals used in computing the optimistic reward r(s, a).

Proposition 11. Let assume θ * a 2 ≤ B. If θ t,a is computed as in Eq. 5.9 and c t,a is defined as in Eq. 5.11, then

P r(s, a) < r(s, a) -c t,a x s,a V -1 t,a ≤ t -α K Proof. By definition of ρ(s, a) we have 0 ≤ ρ(s, a) ≤ w τ =1 1 τ < log(w) + 1 . = w . Thus 1 ≤ x s,a 2 2 ≤ d j=0 j w = 1-d+1 w 1-w = L 2 w . Using Thm. 2 of [Abbasi-yadkori et al., 2011], we have with probability 1 -δ, θ t,a -θ * a Vt,a ≤ R (d + 1) log 1 + T t,a L 2 w /λ δ + λ 1/2 B
Thus for all s ∈ S we have,

|r(s, a) -r(s, a)| = |x T s,a θ t,a -x T s,a θ * a | = |x T s,a V -1 t,a V t,a ( θ t,a -θ * a )| ≤ x V -1 t,a V t,a ( θ t,a -θ * a ) V -1 t,a using Cauchy-Schwarz ≤ x V -1 t,a θ a -θ * a Vt,a since ||V ta,a ( φa -φ a )|| V -1 ta,a = || φa -φ a || Vt a,a
Using δ = t -α K concludes the proof.

An immediate result of Prop. 11 is that the estimated average reward of π k in the optimistic MDP M k is an upper-confidence bound on the optimal average reward, i.e., for any t (the probability follows by a union bound over actions)

P η * > η π k ( M k ) ≤ t -α .
(5.12)

We are now ready to prove the main result.

Proof of Thm. 10. We follow similar steps as in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. We split the regret over episodes as

∆(A, T ) = m k=1 t k+1 -1 t=t k η * -r(s t , a t ) = m k=1 ∆ k .
Let T k,a = {t k ≤ t < t k+1 : a t = a} be the steps when action a is selected during episode k. We upper bound the per-episode regret as

∆ k = a∈[K] t∈T k,a η * -r(s t , a) ≤ t k+1 -1 t=t k η k -r k (s t , a) (5.13) + a∈[K] t∈T k,a r k (s t , a) -r(s t , a) , (5.14)
where the inequality directly follows from the event that η k ≥ η * (Eq. 5.12) with probability 1 -T -α . Notice that the low-probability event of failing confidence intervals can be treated as in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. We proceed by bounding the term in Eq. 5.13. Since we are dealing with deterministic MDPs, the optimal policy converges to a loop over states. When starting a new policy, we may start from a state outside its loop. Nonetheless, it is easy to verify that starting from any state s, it is always possible to reach any desired state s in at most w steps (i.e., the size of the history window). As a result, the difference between the cumulative reward ( t r k (s t , a)) and the optimal cumulative reward ((t k+1 -t k ) η k ) in the loop never exceeds w. Furthermore, since episodes terminate when one action doubles its number of samples, using a similar proof as [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], we have that the number of episodes is bounded as m < K log 2 ( 8T K ). As a result, the contribution of Eq. 5.13 to the overall regret can be bounded as

m k=1 t k+1 -1 t=t k η k -r k (s t , a) ≤ Kw log 2 8T K .
(5.15)

The second term in Eq. 5.14 refers to the (cumulative) estimation error in the reward function. We further decompose the error as

| r k (s t , a) -r(s t , a)| ≤ | r k (s t , a) -r k (s t , a)| + | r k (s t , a) -r(s t , a)|.
We can bound the cumulative sum of the second term as (similar for the first, since r k belongs to the confidence interval of r k by construction)

m k=1 a∈[K] t∈T k,a | r k (s t , a) -r(s t , a)| ≤ m k=1 a∈[K] t∈T k,a c t,a x st,a V -1 a,t ≤ max t,a c t,a a∈[K] m k=1 t∈T k,a x st,a V -1 a,t ≤ c max a∈[K] m k=1 t∈T k,a x st,a 2 V -1 a,t T a ,
where the first inequality follows from Prop. 11 with probability 1 -T -α , and T a is the total number of times a has been selected at step T . Let T a = ∪ k T k,a , then using Lemma 11 of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], we have

t∈Ta x st,a || 2 V -1 t,a
≤ 2 log det(V T,a ) det(λI) .

Furthermore by Lemma 10 of [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF], we have

det(V t,a ) ≤ (λ + tL 2 w /(d + 1)) d+1 , which leads to m k=1 a∈[K] t∈T k,a | r k (s t , a) -r(s t , a)| ≤ c max a∈[K] T a 2(d + 1) log λ + tL 2 w λ(d + 1) ≤ c max 2KT (d + 1) log λ + tL 2 w λ(d + 1) .
Bringing all the terms together gives the regret bound. Figure 5.5: Optimal policy vs. greedy and fixed-action. The fixed-action policy selects the action with the largest "constant" reward. The greedy policy selects the action with the highest immediate reward (depending on the state). The optimal policy is computed with value iteration. Parameters c 1 = 2, c 2 = 0.01, α = 2.

Experiments

We empirically validated our model and compared LinUCRL to existing baselines in three different scenarios. Toy experiment: A simulated environment with two actions and different parameters, with the objective of illustrating when the optimal policy could outperform a fixed-action and greedy strategies. Movielens: We derived model parameters from the movielens dataset and we compared the learning performance (i.e., cumulative reward) of LinUCRL to baseline algorithms. Real-world A/B testing data: We used a real-world A/B testing dataset where our model assumptions are no longer satisfied. We investigated how a long-term policy alternating A and B on the basis of past choices can outperform each solution individually. All codes are available at [Warlop, 2017].

Optimal vs. fixed-action and greedy policy. We first illustrate the potential improvement coming from a non-static policy that takes into consideration the recent sequence of actions and maximizes the long-term reward, compared to a greedy policy that selects the action with the higher immediate reward at each step. Intuitively, the gap may be large whenever an action has a large instantaneous reward that decreases very fast as it is selected (e.g., boredom effect). A long-term strategy may prefer to stick to selecting a sub-optimal action for a while, until the better action goes back to its initial value. We consider the simple case K = 2, w = 8 and

d = 1. Let θ * 1 = (1, -c 1 ), θ * 2 = (1/α, -c 2 ).
We study the optimal policy maximizing the average reward η, a greedy policy that always selects a t = arg max a r(s t , a), and a fixed-action policy a

t = arg max{1 -c 1 ρ M , 1/α -c 2 ρ M } with ρ M = w τ =1 1 τ , that
is the action that have the highest mean reward when always pulled. Notice that the fixed-action policy is what a recommender system would execute once the A/B testing phase is over and the (supposedly) best strategy is determined. We first set c 1 = 0.3 ≈ c 2 = 0.4 and α = 1.5, for which the "boredom" effect (i.e., the decrease in reward) is very mild. In this case (see Fig. 5.4), the fixed-action policy performs very poorly, while greedy and optimal policy smartly alternates between actions so as to avoid decreasing the reward of the "best" action too much. In this case, the difference between greedy and optimal policy is very narrow. In fact, switching action as soon as the instantaneous reward is better, already allows an action to "recharge" its reward enough to obtain an overall good performance. However in Fig. 5.5, with c 1 = 2 c 2 = 0.01 and α = 2, we see that the greedy policy switches to action 1 too soon to gain immediate reward (plays action 1 for 22% of the time) whereas the optimal policy stick to action 2 longer (plays action 1 for 11% of the time) so as to allow action 1 to regain reward and then go back to select it again. Indeed the "fresh" reward -that is the reward when the arm as not been pulled since w steps -of first arm is twice as big as the second one but it decreases really fast. It then must be pick at a very precise cadence to keep providing positive rewards. As a result, the optimal policy exploits the full potential of action 1 better and eventually gains higher average reward. While here we only leveraged on the "boredom" effect, with a reward linearly decreasing with the recency, we can imagine large range of scenarios where the greedy policy is highly suboptimal compared to the optimal policy. For instance reward function in a inverse U-shape could pose serious problem for short term strategy to successfully stay in the peak area.

Learning on movielens dataset. The standard offline evaluation of a learning algorithm on historical data, is to use a replay or counterfactual strat- egy [Li et al., 2011, Swaminathan andJoachims, 2015], which consist in updating the model whenever the learning algorithm takes the same action as in the logged data, and only update the state (but not the model) otherwise. In our case this replay strategy can not be applied because the reward depends on the history of selected actions and we could not evaluate the reward of action if the algorithm generated a sequence that is not available in the dataset, which is quite likely, and thus the model will be very rarely updated. For instance if at one step the model choose a different action than the one in the logged data, the model will only be updated in best case scenario in w steps if the next w choices are exactly the same as in the logged data. Thus in order to compare the learning performance of LinUCRL to existing baselines, we use the movielens100k dataset to estimate the parameters of our model and construct the corresponding "simulator". That is we first fit our model in order to predict the average observed reward for a genre for each value of the recency function based on all available data. Then whenever an arm is pulled in a specific context the simulator return the "true" reward according to equation 5.5 plus a Gaussian noise, but of course the parameter of the simulator are kept unkown to all the learning algorithm. Unlike a fully synthetic experiment, this gives a configuration which is "likely" to appear in practice, as the parameters are directly estimated from real data. We choose K = 4 actions corresponding to three different genres of movies plus one arbitrary bad action, and we set d = 5 and w = 5, which results into K w = 1024 states. We recall that w has a mild impact on the learning performance of LinUCRL as it does not need to repeatedly try the same action in each state (as ucrl) to be able to estimate its reward. This is also confirmed by the regret analysis that shows that the regret only depends on w in the lower-order logarithmic term of the regret. The parameters that described the dependency of the reward function on the recency (i.e., θ * j,a for j > 0) are computed by using the ratings averaged over all users for each state encountered and for three different genres in the dataset. The first component of the vectors θ * a is chosen to simulate different user's preferences and to create complex dynamics in the reward functions. The resulting parameters are θ * action = [3.4, 0.24, -1.2, 1.2, -0.45, 0.03], θ * comedy = [3.6, 0.66, -3.48, 3.6, -1.35, 0.15], θ * thriller = [3.8, 0.6, -2.85, 3.12, -1.62, 0.3]. The additional "bad" genre (e.g., section children for an adult user) is defined with θ * bad = [2.9, -0.1, -0.1, -0.01, -0.01, -0.01] to introduce diversity in the action set. Again, the observed reward is obtained by adding a small random Gaussian noise to the linear function. The resulting rewards as a function of the recency are illustrated in Fig. 5.6(a) and as a Markov Chain in Fig. 5.7 for the comedy genre. We notice that apart from the "bad" action, the reward slightly improves as a genre is seen a bit more (we can see that by noticing that θ * a,1 > 0 which is the predominant coefficient when the recency function is lower than 1, that is the arm has been pulled only a while ago, so a positive impact occurs) and then they all tend to decrease (with different slopes) implying that the user gets bored (θ * a,2 < 0 which is the predominant coefficient when the recency function is greater than 1). The results are obtained by averaging 4 independent runs.

We compare LinUCRL to the following algorithms: oracle optimal (optimal policy given the true parameters θ * a ), oracle greedy (greedy policy given the true parameters θ * a ), LinUCB [START_REF] Abbasi-Yadkori | Improved algorithms for linear stochastic bandits[END_REF] (learn the parameters using LinUCB for each action and select the one with largest instantaneous reward), ucrl [START_REF] Auer | Near-optimal regret bounds for reinforcement learning[END_REF] (considering each action and state independently). shows the average reward at the beginning of the learning process up to T = 200 and after T = 2000 steps. We first notice that as in the previous experiment the oracle greedy policy is suboptimal compared to the optimal policy that maximizes the long-term reward. Despite the fact that ucrl targets the optimal policy, the learning process is very slow as the number of states is too large and even after 2000 steps the learned policy (Fig. 5.6(b)) is still erratic, implying that the algorithm is far from convergence. On the other hand, at early learning stages LinUCRL is slightly worse than LinUCB, as it is trying to learn a more complex policy. Nonetheless, its performance rapidly improves and after 2000 steps the average reward is already better than LinUCB and it closely approaches the average reward of the optimal policy (3.567 for the optimal policy vs. 3.544 for LinUCRL). Qualitatively, we see that the greedy policy selects thriller and comedy -that have the highest immediate rewards -too often, which prevents from exploiting their full potential, that could be achieved by selecting action a few times more as done by LinUCRL. Similarly, LinUCB gets stuck in selecting only thriller and comedy, while LinUCRL executes almost the optimal policy by integrating action into the loop of genres proposed to the user.

Large scale A/B testing dataset. We also validate our approach on another real world A/B testing dataset. We collected 15 days of click on ads history of a Criteo's test, where users have been proposed two variations on the display denoted as A and B. User can either click or not click on the display, which result in a binary reward of 1 for a click and 0 otherwise. Unlike a classical A/B testing each unique user has been exposed to both A and B but with different frequencies. This dataset is formed of 350M tuples (user id, timestamp, version, click) and will be released for the community as soon as possible. Remark that the system is already heavily optimized and that even a small improvement in the click-rate is very desirable. As in the movielens experiment it is not relevant to use replay strategy because model updates will be very rare, but thanks to the large size of the dataset, we can define an experiment close to real conditions where the experiment should excatly follow logged data ordering. To do so, whenever an arm (A or B) is pulled by the algorithm in a given state (we set w = 10, for a total of 2 10 = 1024 states), we simulate a reward according to a Bernoulli with probability corresponding to the observed click rate of this action in this state. This define a new simulator based on the data, but unlike the previous experiment where we fit a simulator according to our model, here we do not impose any linear assumption on the simulator (as in Eq. 5.5) Thus with this simulator, if the environment does not follow our model we will not be able to correctly learn our model and thus make suboptimal choices.

Using this simulator we compute oracle greedy and optimal policies and we compare LinUCB, LinUCRL, which is no longer able to learn the "true" model, since it does not satisfy the linear assumption, and ucrl, which may suffer from the large number of states but targets a model with potentially better performance. Indeed ucrl does not impose any regularity on the environment thus it can fit any behaviour with a sufficient amont of time. We report the results (averaged over 5 runs) as a relative improvement to the worst fixed option (i.e., in this case A). Since different users may have different intrinsic click probability, averaging over all users may blur the impact of context and individual users click probability. To prevent from that, we clustered users based on their exposition frequency on A and based on their global click rate on A and on B. The simulator was then learned on the largest cluster in order to have sufficient observation per state. Fig. 5.8(a) shows the reward averaged over T = 2, 000 steps and Fig. 5.8(b) shows the performance of the policy learned at the end of the experiment. We notice that despite the fact that the simulator breaks our modelling assumptions, LinUCRL is still the most competitive algorithm as it achieves the best performance among the learning algorithms and it also outperforms the greedy policy.

Related Work

While the mab model and regret minimization [Auer, 2003] or best-arm identification algorithms [Jamieson andTalwalkar, 2016, Soare et al., 2014] have been often proposed to learn effective recommender system, they all rely on the underlying assumption that the optimal recommendation strategy is to keep selecting one single arm. Likewise our work is also related to the linear bandit model [Li et al., 2010c, Abbasi-yadkori et al., 2011[START_REF] Agrawal | Thompson sampling for contextual bandits with linear payoffs[END_REF] (section 2.1.3), where the reward of an arm is a linear function of a context and an unknown target vector. Despite producing context-dependent policies, this model does not consider the influence that the arms selected over time may have on the state and thus overlook the potential of long-term reward maximization. However some works proposed non stationary settings for mab and recommender systems. Finally, their also have been some reinforcement learning algorithms developed for the recommender system task.

Non stationarity in multi-arm bandit

Time-varying rewards in multi-arm bandit have been studied by [START_REF] Heidari | Tight policy regret bounds for improving and decaying bandits[END_REF]. In their settings each time an arm is pulled, its reward can only increase with decreasing marginal returns. More formally to each arm a is associated an increasing reward function f a (t) where t indicates the number of times arm a have been pulled, such that ∀t ≥ 1, f a (t+1)-f a (t) ≤ f a (t)-f a (t-1). Their setting can correspond to someone learning a task and thus perform better and better. However, unlike our scenario, the reward never decreases back even if the arm has not been pulled for a long time nor depends on the pulls frequency. An other limit of their setting is that they assumed the existence of a known time horizon T such that the goal is to maximize the reward from time 0 to T . But once T is reached, one does not know what to do next (one cannot use T = ∞). Their learning algorithm leverage the decreasing marginal returns property of each arm to compute a lower and an upper bound on the cumulative reward one would get by playing only this arm from now until T . If one arm is dominated by an other arm, meaning that is upper bound is lower then the lower bound of an other arm, it is removed from the candidate set of arms. Each candidate arm is then pulled once and lower and upper bound estimates are updated until T is reached or there is only one arm left. The authors also proposed the case with decreasing rewards but again all arms must be decreasing and always decreasing. [START_REF] Komiyama | Time-Decaying Bandits for Non-stationary Systems[END_REF]] also consider a model where the reward continuously decreases over time whether it is pulled or not (e.g., modeling novelty effects, where new products naturally loose interest over time). Let consider arm a that first appears at time t a and let assume their exists a set of d known decreasing functions f 1 (t), • • • , f d (t), then the reward r a,t of arm a at time t (here t increases whether or not the arm has been pulled, it is the true time) is defined by r a,t = r a + d j=1 w a,j f j (t) where w a,j are weights to be learned and r a the arm bias to be learned. This formulation can then be rewritten as a linear bandit as described in section 2.1.3, thus their algorithm, called time-decaying ucb, introduce the adequate confidence ellipsoid on rewards to decides which arm to pull at each step. However unlike our scenario, future rewards are not influence by past choices and they consider only simple decays whereas we let the model learn the shape of the reward evolution. This model fits into the more general case of restless bandit (see e.g., [START_REF] Filippi | Optimally Sensing a Single Channel Without Prior Information: The Tiling Algorithm and Regret Bounds[END_REF], Tekin and Liu, 2012, Ortner et al., 2014]), where each arm has an (partially observable) internal state that evolves as a Markov chain independently from the arms that are selected over time.

Non stationarity in recommender systems

Time dependency has also been studied in RS, for instance [Koren, 2009] further extend SVD++ model (see section 3.6.1) by making bias terms and user latent factors time dependant: b u → b u (t), b i → b i (t), U uk → U uk (t) where t represent a timestep (a day in Netlfix dataset). Indeed, in the Netflix dataset [Koren, 2009] noticed that the ratings tends to increase when the user rates/see the movie a long time after his released which lead to consider a time dependent item bias.

Besides some product may be more suitable for specific season of the year making the item bias periodical. On the user hand, her way of rating can be drifting over time leading to consider a time depend user bias. Also the taste of the user can also be changing over time, one user may like horror movie at a given time of her life and move to drama movie later, making her user latent factor time dependent. Finally, item characteristic are expected to be fixed over time since we do not expend the item to change over time. [Koren, 2009] j∈Nu Y j and learn all the parameters by SGD on the same objective function as (3.35). [START_REF] He | Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering[END_REF] extend over timeSVD++ by adding a visual interaction term, that is they augmented the user-item affinity function with a temporal visual interaction term θ u (t) T θ i (t). θ i (t) ∈ R K , with K the latent space dimension, represent the item visual features learn from the item image with Deep Convolutional Neural Network and further mulitply by temporal weights, and θ u (t) ∈ R K account for the temporal interest of user u of those visual features.

Other works focus on time as a context, for instance [START_REF] Baltrunas | Towards time-dependant recommendation based on implicit feedback[END_REF] proposed to split the timeline into different seasonality -within the day, within the week, within the year -and learn a separate model per season. Altough it showed better performance than the global model, a tensor approach would be more effective as shown in section 3 with Hoals.

Reinforcement Learning

The closest related work to our approach has been proposed by [Auer andOrtner, 2006, Jaksch et al., 2010] where they build an algorithm called ucrl(2). Our approach is at ucrl what linear bandit is at bandit. Indeed, ucrl is a learning algorithm for undiscounted reinforcement learning where each state is independent of each user. That is the reward of an action in a given state as no link whatsoever with other states and actions and thus learning must be done for each (action, state) independently. Their algorithm thus construct confidence interval around reward and transition probabilities based on previous pulled similar to Eq. 2.3, that are used to compute an optimistic policy. The policy is then played until an (action,state) pair has been observed twice as much from the beginning as since last update (in our case it is only one action that must be observed twice as much). This algorithm allows to always find the optimal policy since it does not assume any specific behaviour of reward but learning can be really long if the number of (state,action) is large as it is the case in our environment. This can be highlight looking at their regret bound in O(DS √ KT log T ) where D is the diameter of the MDP and correspond to w in our case, K the number of actions and S = K w the number of states whereas our algorithm suffer from a regret bound in O( KT log(T )).

[ [START_REF] Shani | An mdpbased recommender system[END_REF] proposed an MDP-based Recommender System that decide what item to recommend based on the last k items that the user saw. However their work can be seen as an early heuristic variant of ucrl algorithm. As such, it has no theoretical guarantee, while LinUCRL comes with strong regret guarantee independent from the number of states. The first limit of [START_REF] Shani | An mdpbased recommender system[END_REF] is that in recommender systems there are millions of items and thus considering each item independently results in an extremely large state space that could never be learnt. Our solution solves the issue thanks to a linear model on the reward function. Leveraging on this structure we can solve MDPs with huge number of states, as shown by the regret, which is linear in the number of actions and window size, while [START_REF] Shani | An mdpbased recommender system[END_REF] would suffer from an exponential regret (see [Auer andOrtner, 2006, Jaksch et al., 2010]). In their approach, they have to find alternate ways to approximate the transition matrix, as clustering on states, to deal with large state space. Finally, they completely ignore the exploration-exploitation trade-off as they solve the MDP based on estimated transitions and rewards. This may lead to an overall linear regret, i.e., failing to learn the optimal policy. Also related to our work, [START_REF] Kapoor | Just in time recommendations: Modeling the dynamics of boredom in activity streams[END_REF] propose a semi-markov model to decide what item to recommend to a user based on her latent psychological state toward this item. They assumed two possible states: sensitization, state during which she is highly engaged with the item, and boredom, state during which she is not interested in the item. Thanks to the use of a semi-markov model, the next state of the user depends on how long she has been in the current state. However, like [START_REF] Shani | An mdpbased recommender system[END_REF], they ignore the exploration-exploitation trade-off. Indeed, in their experiment they first gather 3 months of data per user in order to learn the model parameters.

Finally, this work can also be related to linearity assumptions in reinforcement learning that usually appears in approximate dynamic programming when doing representation approximation when state space are really large. A common approximation consist in considering that the state (or state-action) value function belong to a function space F that is a linear function of d features φ 1 , • • • , φ d : X × A → R such that F . = {V α (x) = d j=1 α j φ j (x), α ∈ R d }. [START_REF] Williams | Tight performance bounds on greedy policies based on imperfect value functions[END_REF] provide approximation error guarantee on the value function in applying the Bellman Residual Minimization which approximates the optimal value function by looking for the V ∈ F that minimizes the distance ||T V -V ||. [START_REF] Bertsekas | Temporal differences-based policy iteration and applications in neuro-dynamic programming[END_REF] studied the approximation error of approximate value iteration that modify algorithm 9 in order to constraint V k+1 to belong to F, thus V k+1 = arg inf V ∈F ||T V k -V ||. In order to perform value function learning, we can also mention extension of TD(λ) ( [START_REF] Tsitsiklis | Feature-based methods for large scale dynamic programming[END_REF]), or Least-squares temporal difference (LSTD) learning ( [Boyan, 1999, Ghavamzadeh et al., 2010]). More recently, [START_REF] Osband | Generalization and exploration via randomized value functions[END_REF] proposed a randomized least-squares value iteration (RLSVI) algorithm with linearly parametrized value functions. As LinUCRL, their algorithm is splitted into episodes where parameters are sampled according to a Bayesian posterior whose confidence interval are constructed similarly to our reward function condifence interval. However, in LinUCRL we only assumed linearity on the reward function and we do not need the overall value function to be linear. One of their experiment considered the item recommendation problem, but did not considered the impact of past recommendations on future user interest. Their experiment is as follow: let consider a user who provided binary feedbacks on items (+1 for likes and -1 for dislikes, missing values are seen as 0) store in a vector x ∈ R p , with p the number of items. The probability that this user likes item i is given by P(i|x) = 1 1+exp(-[β i p j=1 γ i,j x j ]) , with β i ∈ R the item bias and γ i,j ∈ R the "correlation" between items i and j. With such a model the state space size is exponential in the number of items to recommend which justify the need to perform approximate dynamic programming. They further create a simulator that, unlike our experiment, is not constructed using real past data, but, choose arbitrarly random values for β and γ in order to simulate user interest in a given context x and prove effectiveness of their model in learning the optimal policy while minimizing the regret compared to different bandit and reinforcement learning algorithms.

Industrial learnings

The non stationnarity of the performence of a solution is commonly accepted in the industrial world. However tests do not take into account this phenomenom for multiple reasons. The first one is the absence of solid solutions to tackle the problem. The second is that many tests are often performed for attribution purpose, that is measuring the impact of one version against one other, thus population is splitted in as many disjoints groups as versions to tests. The goal of attribution is then to decide the budget to invest for different solutions. However we think that when multiple solutions are available and running, it is a good idea to have an alternating strategy using LinUCRL, but the company may not be mature enough to implement it at scale. However LinUCRL as the nice property that every computed policy end up in a loop. Thus it is only required to stock this loop and the position of the user in the loop to decide what solution to use at next. The policy can then be updated every night if updated condition are matched, that is one action has been observed twice as much as since last update of the policy. Even though LinUCRL have not been used for a client at fifty-five for now, we are implementing the solution for an in mall navigation recommendation where the objective is to suggest a new store to visit to a user that explicitly provide the information of the stores she is willing to go to. Using only one recommender system to complete the journey could results in locking the users in always the same journey because of lack of diversity. Indeed in such application, most users always go to see the same few stores and thus using only one recommender systems would most of the time recommend the same additional store.

Conclusion

In this chapter, we showed that estimating the influence of the recommendation strategy on the reward functions and computing a policy maximizing the reward in the long term can significantly outperform fixed-action or greedy policies. We introduced a novel learning algorithm, LinUCRL, to effectively learn such optimal policy and we prove that its regret is much smaller than for standard reinforcement learning algorithms (ucrl). We validated our model and its usefulness on the movielens dataset and on a novel A/B testing dataset. Our results illustrate how the optimal policy effectively alternates between different options, in order to keep the interest of the users as high as possible. Furthermore, we compared LinUCRL to a series of learning baselines on simulators satisfying our linearity assumptions (movielens) or not (A/B testing). A venue for future work is to extend the current model to take into consideration correlations between actions. Furthermore, given its speed of convergence, it could be interesting to run a different instance of LinUCRL per user -or group of users -in order to be able to offer personalized "boredom" curves. Finally, using different models of the reward as a function of the recency (e.g., logistic regression) could be used in case of binary rewards.

Conclusion 6.1 Contributions

Recommender Systems have been widely studied and many algorithms have been proposed to improve state-of-the-art performances. However several industrial constraints were not appropriately tackled by state-of-the-art algorithms. In this thesis we aimed at proposing novel algorithms to answer those unsolved issues or improve existing solutions.

The main contributions of this thesis to the research in recommender systems can be summarized as follows:

• a higher order matrix factorization algorithm using tensor factorization introduced in chapter 3 that can be used at scale in order to tackle multiple types of user-item interactions and in multiple types of context. Such tensor factorization methods are very suitable for online applications where most of the time the targeted action is very scarce but many other actions are available at the same time. Besides, context is also often an important feature to take into account especially in e-commerce application where users does not have the same behaviour during the different seasons of the year, during sales period and during holidays time. Our Hoals algorithm allows to deal with both contextual bias and multiple types of information without increasing the algorithm complexity too much and proved to increase performance. This is done by adding additional slice to a tensor that originally has two dimensions (user and item) for each new type of feedback and new context. Leveraging tensor unfolding and als-wr allow to effectively complete the tensor missing values.

• a basket completion algorithm introduced in chapter 4 that builds upon dpps to directly model the objective that is to score the relevance of adding a given item to a cart instead of the global probability of buying a set of items as it was done in previous dpp solutions for basket completion. Our solution is both effective to train and to perform recommendation thanks to the tensor low rank assumption. Each slice of the tensor is used to compute the probability to add a particular target item according to the user basket. Using a logistic function on top of the kernel allows to separate item latent factors to predict if the target is relevant to add in the basket or not. Finally, we hope that our generalization of dpp using a logistic link function could lead to other generalizations like poisson dpp for instance with a logarithmic link function.

• a linear reinforcement learning algorithm introduced in chapter 4 to alternate between different solutions and fight user non stationary interest in each solution. We introduced a recency function that captures the fatigue of continuously using the same action and used it to defined a polynomial reward function in each state-action pair. The parameters of those polynomials are then learned in an optimistic in face of uncertainty idea to trade off between exploration and exploitation in order to maximize long term performances. We leveraged ideas from ucrl to provide a reinforcement learning algorithm and from LinUCB to compute confidence interval around rewards. Our LinUCRL algorithm has the advantage of having a regret independent from the number of states that can grow exponentially fast with the number of arms and to have a policy that is often a short loop and thus easy to implement in practice.

Future Works

In addition to the previous enhanced contributions of this thesis, several directions can be investigated to develop and improve this work. Possible future investigations are:

• proof convergence of Hoals. Convergence of matrix completion algorithm has long been an open question and several works tackled this issue (see appendix A) using mostly nuclear norm minimization and alternating least square approaches. Leveraging ideas from those works could allow to give some convergence guarantee for Hoals.

• negative sampling for Logistic dpp. In this thesis we used random sampling to produce negative samples examples for Logistic dpp experiments. However it could be interesting to investigate more dynamic methods to generate different negative samples as the algorithm learns to help differentiate between real candidates item and bad candidates that receive a relative high score. Ideas from generative adversarial networks can be an interested direction to improve negative sampling.

• new applications for Logistic dpp. For now we focused on the application of basket completion however the model can be used to other classification applications. Investigating the performance of Logistic dpp against state of the art of such applications would be interesting to have.

• generalized dpp model. With other types of link functions, ideas of Logistic dpp can be extended to model new problems. Using logarithmic link function can produce poisson dpp in order to model for instance the number of different products that a user may purchase according to the items she clicked on during the session. We also thought about application for games but we did not have the time to further test the model on such problems. A possible direction is to have a kernel of size the number of players in the universe (instead of the items in the catalog) and the determinant will capture the winning probability of a team. In an adversarial setting, each team will have their own subkernel matrix defined by the users in each team, and the difference of the two determinants will be proportional to the first team winning probability. When position exists in the game, player i latent factors in position p, noted V p i ∈ R K can be further splitted into the multiplication of two vectors such that V p i = K k=1 Ṽi,k R p,k with R p ∈ R K capturing position specifities and Ṽi ∈ R k player's i performance in such position. In such application dpp may be relevant to capture global coherence of the team.

• more personalization in LinUCRL. In practice one would like to learn one LinUCRL per user. However it could ask too much effort and resources to be feasible. Being able to dynamically split population into subgroups with similar fatigue patern could be a good solution. Another solution could be to define a reward as a sum of linear reward for different cluster of users and both learn the parameters of each cluster and the cluster to which each user belongs.

• new applications for LinUCRL. We believe that LinUCRL can be used in other applications than alternating between several recommender systems.

For instance it could be used for human task scheduling in order to increase productivity by changing task at the right moment that is a sufficiently long time after the task starts for the human to have time to master the task and before getting fed up. Applications in resource balancing can also be thought about in order to change exploited area before the resource is exhausted and in order to guarantee a long term equilibrium.

• take into account all past w actions to model the state-action reward function instead of only the corresponding action. For instance instead of defining the reward r(s t , a i ) of action a i in state s t as a polynomial function of the recency function ρ(s t , a i ), it could be defined as a sum of polynomial function of all recency functions (ρ(s t , a j )) j∈ [K] .

matrix completion with and without side information: min Z∈R ra×r b ,X∈R n×p i,jD

([AZB T ] ij + X ij , M ij ) + λ Z ||Z|| * + λ X ||X|| * (A.9)
where is any loss function (most of the time the square loss) and λ Z , λ X parameters to balance between side information or not. λ Z = ∞ will force Z to be 0 and thus side information will have no impact, and on the contrary λ X = ∞ will put all the learning on the side information. Let X the constant such that ||X|| * ≤ X , then with O(min(X √ n, X 2 log n)/ε 2 ) entries one can recover an ε approximation of M . This bound shows condition on the goodness of the side information. Indeed, with very good side information, X will be close to 0 since all the learning will be done by Z and thus X will be really low. However with really bad side information, all the learning will be done by X and ||X|| * ∼ ||M || * = O(n) so one would need O(n (3/2) ) entries to recover the matrix which is consistent with past results.

Algorithm Sample Complexity

Computation Complexity [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]

2. 1

 1 Content-based input training example . . . . . . . . . . . . . . . . . 3.1 ρ a measure (rank-measure) on the E-commerce dataset ordered by decreasing performance. . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 ρ a measure (rank-measure) on the Last.fm dataset ordered by decreasing performance. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Performance of all models on all datasets. Best results within each dataset are in bold. r denotes the number of latent factors. . . . . . 4.2 Improvement of Multi-Task DPP over Low Rank DPP performances in percentage. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Performance of the models on Instacart dataset. All models used 80 latent factors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Example of a several basket observations . . . . . . . . . . . . . . . . 5.1 R 2 for the different genres and values of d on movielens-100k and a window w = 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Comparisons of various results on matrix completion on sample complexity and computation complexity. . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Number of match by year of the search Recommender+system on Google Scholar

  Figure 1.2: Some real world recommender systems

  (a) Content Based model -users and items are described with contextual information. (b) Collaborative Filtering model -users are described based on their past interactions with items, items are described based on the past users that interacted with them.

Figure 2 . 1 :

 21 Figure 2.1: Illustation of content-based and collaborative filtering models.

Figure

  Figure 2.2: Upper Confidence Bound at a given timestep. In this situation the greedy solution would pull arm B because it has the highest estimated reward, and ucb would pull arm C because it has the highest upper bound.

  Figure 3.4: Factorization of 3-order tensor.

  Parallel-HOALS for Tucker factorization. Input: dataset D, desired ranks {k d } 3 d=1

Figure 3 . 5 :

 35 Figure 3.5: Result of the scalability test of parallel Hoals ran with the implicit version with rank constraints of 200 for users and items and 2 for actions. Each workers has 2CPUs.

Algorithm 7

 7 Optimization algorithm for Logistic DPP model. Input: w ∈ R the scaling weight, α 0 ∈ R, β ∈ R the momemtum coefficient, b ∈ N the minibatch size, ε ∈ R the gradient step, t = 0 the iteration counter, T = 0, past data D = {I m , y m } 1≤m≤M . Initialization: Compute item popularity and output regularization weights α i . Set D 0 ∼ N (1, 0.01) on the diagonal and D0 ≡ 0 the gradient accumulation on D.

Figure 4 . 1 :

 41 Figure 4.1: Multi-Task DPP factorization.

Algorithm 8

 8 Optimization algorithm for Multi-Task DPP model. Input: w ∈ R the scaling weight, α 0 ∈ R, β ∈ R the momemtum coefficient, b ∈ N the minibatch size, ε ∈ R the gradient step, t = 0 the iteration counter, T = 0, past data D = {I m , y m } 1≤m≤M . Initialization: Compute item popularity and output regularization weights α i . Set D 0 ∼ N (1, 0.01) on the diagonal and D0 ≡ 0 the gradient accumulation on D.

  t+1 for all τ end while -Logistic DPP: This version is similar to the low-rank dpp model, with the addition of the logistic function.

Figure 5

 5 Figure 5.1: The Agent-Environment Interaction Protocol

  r(x, π(x)) + γ y p(y|x, π(x))W (y), (5.3) and the optimal Bellman operator is defined as T W (x) = max a∈A [r(x, a) + γ y p(y|x, a)W (y)] (5.4)

Figure 5

 5 Figure 5.2: Reward (average rating) as a function of the recency for different genre of movies (w = 10) and predictions of our model for d = 5 in red. From left to right, top: drama and comedy, bottom: action and thriller. The confidence intervals are constructed based on the amount of samples available at each state s and the red curves are obtained by fitting the data with the model in Eq. 5.5.

Figure 5 . 3 :

 53 Figure 5.3: Screenshot of Netflix ad to encourage users create multiple genre profiles.

  Figure5.4: Optimal policy vs. greedy and fixed-action. The fixed-action policy selects the action with the largest "constant" reward. The greedy policy selects the action with the highest immediate reward (depending on the state). The optimal policy is computed with value iteration. Parameters c 1 = 0.3, c 2 = 0.4, α = 1.5.

  Figure 5.6: Results of learning experiment based on movielens dataset.

Figure 5

 5 Figure 5.7: Impact of pulling an arm on next reward on movielens dataset. Here we focus on the comedy genre. Each dot represent a particular value of the recency function (equivalently a state) of comedy in the x-axis and correspond reward value if playing comedy in this state in the y-axis. Each arrow going to the right (resp. eft) indicates what will be the next state and reward of comedy if comedy is pulled (resp. not pulled) in the current state.

  proposed several modelisation of the time dependence with linear effects (i.e b u (t) = b u + α u sign(t -t u )|t -t u | β with t u the mean date of rating of user u, U uk (t) = U uk + α u sign(t -t u )|t -t u | β + U uk,t , b i (t) = b i + b i,Bin(t)where Bin(t) is just a group of days like month, quarter, ...), spline effects (b u (t) = b u + ku l=1 e -γ|t-t u l | the user time line into k u periods) or periodical term (adding b u,period(t) , b i,period(t) ). Finally the author try different combination of all those terms in order to compute rui (t) = µ + b u (t) + b i (t) + V T i U u (t) + |N u | -1 2

2 )[

 2 5 n log n log K||M || F ε ) O((|D|K + nK 3 ) log(1/ε))[START_REF] Gunasekar | Noisy Matrix Completion Using Alternating Minimization[END_REF] (2013) ALS O(κ 6 M K 7 n log n log ||M || F ε ) O((|D|K + nK 3 )log(1/ε)) [Hardt, 2013] (2014) ALS O(nK(K + log(n/ε)γ 5 K O((|D|K + nK 3 )log(1/ε)) ||M || F +||V || F /ε σ K Keshavan et al., 2010] (2009) OptSpace O(κ 2 M nK log n) O(|D|K log n) (per iter) [Keshavan et al., 2010] (2012) OptSpace O(κ 2 M nK log n) O(|D|K log n) (per iter) [Jain and Netrapalli, 2014] (2014) SVP O(nK 5 log 3 n) O(nK 7 log 3 n log(1/ε)) Table A.1: Comparisons of various results on matrix completion on sample complexity and computation complexity. ε is the error between the recovered matrix and the true matrix in the Frobenius norm. γ K = 1 -σ K+1 σ K . indicates that noise was taken into account. NN = Nuclear Norm.

  Overview of Recommender Systems . . . . . . . . . . . . . . . . . . . 1.2 Limitations and open questions . . . . . . . . . . . . . . . . . . . . . 1.3 Overview of the dissertation . . . . . . . . . . . . . . . . . . . . . . . 1.4 From an algorithm to a recommendation system . . . . . . . . . . . Higher Order Alternating Least Squares . . . . . . . . . . . . . . . . 3.4 Algorithm guarantee . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Testing accuracy . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Testing scalability . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Tensor Factorization . . . . . . . . . . . . . . . . . . . . . . . 3.6.3 Transfer Learning . . . . . . . . . . . . . . . . . . . . . . . . 3.6.4 Cold-start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Industrial learnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Contents
	1 Introduction
	1.1

2 Recommender Systems 2.1 Machine Learning in Recommender Systems . . . . . . . . . . . . . . 2.1.1 On predicting user-item affinity . . . . . . . . . . . . . . . . . 2.1.2 On predicting sets coherence . . . . . . . . . . . . . . . . . . 2.1.3 Effective exploration-exploitation with bandit learning . . . . 2.2 Measure, performance and open datasets . . . . . . . . . . . . . . . . 2.2.1 Measure and performance . . . . . . . . . . . . . . . . . . . . 2.2.2 Available datasets . . . . . . . . . . . . . . . . . . . . . . . . 3 Learning Affinities From Multiple Type of Feedbacks 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Recommender Systems as matrix completion . . . . . . . . . 3.2.2 Recommender systems as tensor completion. . . . . . . . . . 3.3

Table 2 .

 2 1: Content-based input training example the item. For instance if the contextual variables available for a user are her gender and age and for the item (let us consider a movie) the genre among action, thriller, drama and romantic. The length of the input vector is then 7 where the first 3 values encode the user characteristics and the last 4 values encode the item features. For

example, if a 32-year-old male user rated a thriller-action movie 3 stars, we would get the (x, y) training point of table 2.1.

  2.2: Upper Confidence Bound at a given timestep. In this situation the greedy solution would pull arm B because it has the highest estimated reward, and ucb would pull arm C because it has the highest upper bound.

	Estimated
	Rewards
	ෞ 𝜇 𝐴	ෞ 𝜇 𝐵	ෞ 𝜇 𝐶	ෞ 𝜇 𝐸
				Estimated
			ෞ 𝜇 𝐷	reward and its confidence
				interval
					arms
	A	B	C	D	E
		B: greedy choice
		C: UCB choice

  Direct-HOALS for CP factorization.

Input: dataset D, desired rank K Construct the initial (sparse) 3-order tensor R from D Initialize I and A with small random numbers while Not at convergence do Fix I, A and update U (see equations 3.13 and 3.11) Fix U , A and update I (see equations 3.13 and 3.11) Fix U , I and update A (see equations 3.13 and 3.11) end while Return full tensor R . = [U, I, A]

  wheren ds is the number of non-zero elements on row R (d),s and K d is the rank constraint. Since in Hoals we can parallelize the computation of each matrix and within each matrix, the complexity of one update is due to the largest latent dimension over the

	three dimensions, i.e., O	max
		d∈{1,2,3},s

Table 3 .

 3 2: ρ a measure (rank-measure) on the Last.fm dataset ordered by decreasing performance. For matrix factorization and CP tensor factorization, dimension1

	1.1 there are three families of algorithms to predict
	user-item affinities: content-based, collaborative filtering and hybrid methods. This
	work is more related to collaborative filtering since we do not assume the existence

  HOSVD for tensor factorization. Input: dataset D, desired rank {k d } 3 d=1 Construct the initial (sparse) 3-order tensor X from D for d ∈ {1, 2, 3} (modes) do Compute the matrix unfolding X (d) Apply SVD on X (d) and select the k d largest singular values

	A, B, C
	while not converged do
	Fix B, C, update A according to equation 3.38
	Fix A, C, update B according to equation 3.38 replacing (1) by (2)
	Fix A, B, update C according to equation 3.38 replacing (1) by (3)
	end while
	Algorithm 6

Table 4 .

 4 1: Performance of all models on all datasets. Best results within each dataset are in bold. r denotes the number of latent factors.

	dataset	MPR	Prec.@5 Prec.@10 Prec.@20
	Amazon (diaper)	9.43% 36.28% 32.47%	25.2%
	Amazon (D.A.F)	28.11% 56.71% 66.01%	70.11%
	Belgian Retail Supermarket -0.9%	-0.1%	0.34%	1.52%
	UK Retail	-5.43% 30.29% 30.53%	23.68%
	Table 4.2: Improvement of Multi-Task DPP over Low Rank DPP performances
	in percentage.

Remark that the previous main loop is now embedded in each of the ALS-WR computation, the equivalence is granted by Th. 1

The actual reward observed when selecting a at st is rt = r(st, a) + ε, with ε a zero-mean gaussian noise.

We will refer to this strategy as "greedy" policy thereafter.

Remerciements

On Convergence of Matrix Completion

In previous chapters we show that the problem of collaborative filtering was generally studied as matrix completion problem using a small fraction of its entries. We stated that such a general problem is ill posed because it is impossible to recover missing entries without any assumption about the matrix because the degree of liberty would be n × p and thus one would need to see the entire matrix to recover it... To solve this problem we introduced the common assumption that the matrix to recover is low rank (or approximately low rank). This assumption makes sense since it implies correlation between users (and items) and that only few factors contributes to define user-item affinity. However, we never discuss if given this assumption the recovery problem was now possible nor condition on the number of entries one would need to recover a good approximation of the full matrix. In this chapter we then would like to present main works that addressed these questions in order to give the reader a better understanding of the matrix completion problem.

A.1 Background

Let consider a rank-K matrix M ∈ R n×p to be recovered from m entries, stored in the set D . = {(i, j), M ij is observed}. A first lower bound on the minimal number of entries m needed to recover M can easily be obtained. Considering the SVD decomposition of M such that M = U SV T , with U ∈ R n×K the matrix with the left singular vectors, V ∈ R p×K the matrix with the right singular vectors, and S ∈ R K×K the diagonal matrix whose diagonal contains the singular values σ 1 ≥ • • • ≥ σ K . Then the singular values depends on K degrees of freedom, U on (n -1) + (n -2) + • • • + (n -K) = nK -K(K + 1)/2 degrees of freedom and likewise for V which result in (n + p)K -K 2 degrees of freedom. Thus, lemma If m < (n + p)K -K 2 , there exist an infinite number of rank-K matrices with exactly the same entries as the one available in M . So exact recovering is impossible if m < (n + p)K -K 2 . Actually because of the coupon collector's effect that state that to observe all the x distinct values of an urn when sampling with replacement, one must pull in average x log x times. Thus in our case m must rather be of the order of (n + p)K log(n + p) = O(nK log n) (assuming that n ≥ p).

In order to prove efficient matrix completion some additional hypothesis are needed. For instance, [START_REF] Candès | Exact matrix completion via convex optimization[END_REF], in the extreme case of the rank-1 matrix M = e 1 e T n (where (e i ) i∈ [n] is the canonical basis), then

this matrix cannot be recovered unless almost all entries have been sampled and especially the last entry of the first row which have very low probability to be sampled if sampling is done at random. Another interesting example is proposed by [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. Let consider the rank-2 matrix,

√ 2 and u 2 = (e 1 -e 2 )/ √ 2. Then, we have

and one would also need to see almost all entries in order to recover M . These examples illustrate the fact that in order to be efficiently recovered, the singular vectors need to be sufficiently spread, that is uncorrelated or incoherent with the canonical basis. Let us then introduce commons additional assumptions for matrix completion.

Definition 13. (Condition number) Consider a matrix M of rank-K, with singular values,

The condition number of the matrix M , denoted by κ M is defined as Remark Let M be µ incoherent according to definition 15. Then since P u = U U T ,

Thus M is √ µ incoherent according to defintion 14.

Definition 16. (Strong incoherence of a matrix). Let M = U SV T be the SVD of M , P U be the orthogonal projection on U and E = U V T . Then M is strongly incoherent with parameter µ if

In order to give recovery condition of low-rank matrices, two researches direction emerged: nuclear norm minimization and alternating least square. The first solution as the advantage to theoretically require less samples that the second but is computationally much more greedy. Eventually, other approaches tries to reduce the number of required samples while keeping an efficient algorithm.

A.2 Nuclear norm minimization

Initially the matrix completion problem in collaborative filtering is to find the minimal rank matrix that have the same values as the initial matrix on the given points D. More formally, let M be the sparse input matrix whose revealed entries are stocked in the set

However this problem is in general an NP-hard problem. To solve this issue, several authors ( [START_REF] Candès | Exact matrix completion via convex optimization[END_REF], Candès and Tao, 2009, Recht, 2009]) studied the problem of nuclear norm minimization relaxation:

that is the sum of the singular values. Indeed the nuclear norm can be thought as a convex relaxation of the number of non-zero eigenvalues that is the rank. This problem has the advantage of being convex and is then studied as a surrogate of the rank minimization problem.

These authors assumed different hypothesis on the input matrix M (incoherence or strong incoherence mostly) resulting in different guarantees on the reconstruction but always assumed that entries were sampled at random. Here is a short summary of their works and results.

Exact Matrix Completion via Convex Optimization

In 2008, [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] are the first to provide theoretical guarantee for low-rank matrix completion given partially observed matrix. The matrix is assumed to be exactly low-rank and entries are observed without noise. Under incoherence assumption, the authors gives condition on the number of entries to recover the full matrix that closely compare with the minimal theoretical value nK log n by proving that if the number of samples m is O(n 1.2 K log n) then one can recover the input matrix with high probability.

Theorem 12 (Theorem 1.3 of [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]). Let M ∈ R n×p be a rank-K matrix with singular value decomposition U SV T , and let n = max(n, p). Assume that M is µ 0 -incoherent (definition 14), and that there is µ 1 > 0 such that ||U V T || ∞ ≤ µ 1 r/(np). Suppose entries of M are observed with locations sampled uniformly at random. If

for some β > 2 and constant C > 0, then the minimizer of the problem

is unique and equal to M with probability at least 1 -cn -β . For r ≤ µ -1/2 0 n 1.5 , this estimate can be improved to Cµ 1/2 n 1.2 Kβ log n with the same probability of success.

The Power of Convex Relaxation: Near-Optimal Matrix Completion

Trying to get closer to nK log n bound, in 2009 [START_REF] Candès | The power of convex relaxation: Near-optimal matrix completion[END_REF] relied on strong incoherence assumption of the matrix in order to recover the input matrix with high probability. This allowed them to further reduce the number of required samples to O(nK log 6 n) which improve the dependence on n over previous result.

151

Theorem 13 (Theorem 1.2 of [START_REF] Candès | The power of convex relaxation: Near-optimal matrix completion[END_REF]). Let M ∈ R n×p be a fixed matrix of rank K = O(1) such that M is µ-strongly incoherent and n = max(n, p). Suppose we observe m entries of M with locations sample uniformly at random. Then there is a positive numerical constant C such that if m ≥ Cµ 2 nK log 6 n then with probability at least 1 -n-3 , M is the unique solution of (A.2).

A Simpler Approach to Matrix Completion

Finally in 2009, [Recht, 2009] relaxed the strong incoherence assumption of [START_REF] Candès | The power of convex relaxation: Near-optimal matrix completion[END_REF] to a incoherence assumption on the matrix to recover and come closer to the theoretical lower bound on the number of entries up to a log n factor (m = O(nK log 2 n)). Thus under the same hypothesis it is not possible to further improve this theoretical guarantees. However they assumed an additional assumptions that assumed that U V T is bounded.

Theorem 14 (Theorem 1.1 of [Recht, 2009]). Let M ∈ R n×p be a rank-K matrix with singular value decomposition U SV T . Without loss of generality, impose convention n ≥ p, S ∈ R K×K , U ∈ R n×K , and V ∈ R p×K . Assume that M is µ 0 -incoherent (definition 14), and that there is

Suppose entries of M are observed with locations sampled uniformly at random. If

for some β > 1, then the minimizer of the problem

is unique and equal to M with probability at least 1 -6(n + p) 2-2β log(p)p 2-2β 1/2 .

A.3 Alternating Least Square

As seen previously, in collaborative filtering application, the alternating least square (ALS) algorithm is used very oftenly for its simplicity. Indeed in order to update the latent factors of one row of U or V , one just need to perform a linear regression of dimension K. [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF] are the first to provide recovery guarantee of this algorithm. In the ALS algorithm the goal is to find the two matrices U ∈ R n×K and V ∈ R p×K such that the input matrix R = U V T given a set of observed point D. This is done by minimizing the squared loss between the observed value and the scalar product of the corresponding lines of U and V :

Algorithm 11 ALSM Input: dataset D, q probability to observe each entry. Create 2τ + 1 subsets from D:D 0 , D 1 , • • • , D 2τ each of size |D| with the element of D belonging to one of the D t 's with equal probability and sampled independently Set Û (0) = SV D( MD /q, K) that is the top-K left singular values of MD /q where unknown entries are fill with 0.

Clipping step: Set all the elements of Û 0 that have magnitude greater than 2µ √ k n to zero and orthonormalize the columns Û 0 (using QR decomposition).

Low-rank Matrix Completion using Alternating Minimization

In 2012, [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF] were the first to provide theoretical analysis of the alternating least square algorithm for matrix completion and matrix sensing (recovering matrix M given linear measurements b i = tr(A T i M ), where (A i ) 1≤i≤d are called sensing matrices). To perform their analysis, they showed that the alternating least square can be viewed as a noisy power method to compute the singular vectors.

For analysis constraint, they proposed a modification of ALS where each update is done using a sample subset of D with the same cardinality (see algorithm 11) in order to be able to analyse each iteration independently, but this is not required in practice. Using this algorithm they were able to prove the following theorem:

Theorem 15 (Theorem 2.5 of [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF]). Let M = U SV T ∈ R n×p be a rank-K, µ-incoherent matrix (definition 14). Also, let each entry of M be observed uniformly and independently with probability q, if

, that is

) to recover the true matrix with an error of ε.

Noisy Matrix Completion Using Alternating Minimization

Building upon the work of [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF], [START_REF] Gunasekar | Noisy Matrix Completion Using Alternating Minimization[END_REF] are the first to provide recovery guarantee of the alternating least square algorithm under noisy observations. Noise. Let M be the true low rank matrix and N the noise matrix such that the observed entries come from the matrix M .

= M + N . The noise is assumed to be distributed arbitrarily but bounded by some constant

Using this noise definition and pursuing the power method idea, [START_REF] Gunasekar | Noisy Matrix Completion Using Alternating Minimization[END_REF] obtained the following results regarding the recoverability of the matrix.

Theorem 16 (Theorem 2 of [START_REF] Gunasekar | Noisy Matrix Completion Using Alternating Minimization[END_REF]). Let M = U SV T ∈ R n×p be a rank-K, µ-incoherent matrix (definition 14). Further, it is assumed that

Additionally, let each entry of M = M + N be observed uniformly and independently with probability

where κ M = σ 1 σ K is the condition number of M , δ 2k ≤ σ K 64σ 1 and C > 0 is a global constant. Then with high probability with τ ≥ C log ||M || F ε the outputs Û (τ ) and V (τ ) of Algorithm 11 with input D satisfy

, that is

entries to recover a noisy low-rank µ-incoherent matrix with error ε plus noise. Let note that one must have n << K 7 however the number of required entries is larger than the total number of entries. Unfortunately, this is rarely the case in practice where K ≈ 100.

Understanding Alternating Minimization for Matrix Completion

In 2014, [Hardt, 2013] reduced the number of needed entries in order to recover a low-rank matrix using an alternating minimization algorithm. The improvement is achieved using a careful analysis of QR factorization (which is used in [START_REF] Jain | Low-rank matrix completion using alternating minimization[END_REF]) and proposing a smooth version inspired by [START_REF] Dunagan | Smoothed analysis of condition numbers and complexity implications for linear programming[END_REF]. They discussed the fact that applying QR-factorization directly to the singular vector matrix can lead to large incoherent parameter of the matrix (so to a more coherent matrix) and thus increase the number of samples needed to recover the matrix. However small Gaussian perturbations have proved to lead to well-conditioned matrix, which was no harm for their analysis since the matrix to recover is already noisy. Their alternating algorithm uses this trick to prove a low coherence number at each iteration of the alternating scheme. Noise. Let M = M + N where M is the low-rank matrix to recover such that M = U SU T , and N the noise matrix. Thus N = (I -U U T ) M . N is suppose to be an arbitrary deterministic matrix that satisfies two constraints:

This assumption is weaker than the noise assumption of [START_REF] Gunasekar | Noisy Matrix Completion Using Alternating Minimization[END_REF] since if max ij |N ij | ≤ N max then constraints (A.4) are also verified.

Theorem 17 (Theorem 1.2 of [Hardt, 2014]). Let M = U SU T ∈ R n×n be a rank-K, µ-incoherent matrix (definition 14) and M = M + N with the noise N = (I -U U T ) M satisfying (A.4) and whose largest singular values is denoted σ k+1 . Additionally, let each entry of M be observed uniformly and independently with probability q, if

then the alternating least square algorithm output (X, Y ) such that ||(I -

Remark Although the theorem focus on square symmetric matrices, the results can be extended to rectangular matrices. Let consider a rectangular matrix B then one can construct a symmetric square block matrix A from B:

and apply results on A. When recovering A, the algorithm will also produce an approximation of B with the same error.

A.4 Other Approaches

Minimizing the trace norm in order to recover the input matrix proved to be a very efficient algorithm in number of needed samples since it converges with O(nr log 2 n) samples. However these solutions have trouble to scale with very large matrices that occur frequently in collaborative filtering. Later works have Algorithm 12 OptSpace Input: dataset D, M D . = M filled with 0 on unknown entries Trim M D and let M D be the ouput Compute SVD of M D = U 0 SV T 0 Clean residuals errors by minimizing the discrepancy F (U, V ) initialized in U 0 , V 0 (see equation A.5) then try to reach the minimal number of samples, while others focus on alleviating the dependence on the condition number that could be problematic in practice. Finally, some works were also dedicated to matrix completion with side information.

Matrix Completion from a Few Entries

In 2009, in an algorithm called OptSpace, [START_REF] Keshavan | Matrix completion from a few entries[END_REF], [Hulikal Keshavan, 2012], proposed to recover the input matrix by first computing an SVD decomposition on a matrix whose rows and columns that contained more information than the average rows or columns where entirely set to 0. Although surprising, this technique makes the underlying low rank structure of the matrix more apparent. The intuition is that over-observed rows or columns can lead to overestimation of the top singular values and thus lead to poor initial points. This is somehow related to the overfitting concept. Then, they refined the decomposition by minimizing a function (by gradient descent) defined over the cartesian product of two Grassmann manifolds which minimizes the square distance between the reconstruction and the known entries (see algorithm 12:

Under incoherence condition and provided that ∀(i, j)

, they showed that if O(nKκ 2 M log n) entries were revealed uniformly at random then their algorithm converges to the true matrix M with high probability. Apart from the condition number we see that algorithm 12 obtains the lower bound on the number of entries to be revealed at random of O(nK log n). However this algorithm can be quite computationally heavy and only guarantees asymptotic convergence unlike alternating least square solutions. Matrix Completion from Noisy Entries Later, the authors extend the analysis of the OptSpace algorithm (with a slight modification with a regularization in F ) to the case of approximately low rank matrix that M = M + N where M is lowrank and N is small in some sense ( [START_REF] Keshavan | Matrix completion from noisy entries[END_REF]). They show that with O(nκ 2 M max(K log n, κ 4 M K 2 )) entries (which again disregarding the condition number dependence achieved the O(nK log n) lower bound) one can obtain the following reconstruction error bound:

Fast Exact Matrix Completion with Finite Samples Several works have tried to obtain close to optimal results using the well used alternating least square algorithm. However results showed dependence on the condition number of the matrix that can be arbitrarily large. Different approaches have been investigated to improve these performances. For instance [START_REF] Jain | Fast exact matrix completion with finite samples[END_REF] relied on using Singular Value Projection on rank-k matrix in a loop over k (see Algorithm 2 of [START_REF] Jain | Fast exact matrix completion with finite samples[END_REF] for the detailed algorithm). Their main result is as follow:

Theorem 18 (Theorem 1 of [START_REF] Jain | Fast exact matrix completion with finite samples[END_REF]). Let M ∈ R n×p be a rank-K, µ-incoherent matrix (definition 14). Also, let each entry of M be observed uniformly and independently with probability q, if q > Cα µ 4 K 5 (n + p) log 3 (n + p) p

where α > 1 and C > 0 is a global constant. Then with probability 1-n -10-log α , the output M of their Algorithm 2 satisfies || M -M || F ≤ ε. Moreover the run time of the algorithm is O(|D|r 2 log(1ε)

Using Side Information

Several work studied the problem of matrix completion assuming the existence of side information. For instance one could have gender, age, or location information about each users and price, color, category, or provenance information for the items. With good side information they proved that the number of samples needed to reconstruct the matrix can be drastically reduce. For instance [START_REF] Xu | Speedup matrix completion with side information: Application to multi-label learning[END_REF] proved that only O(log n) information are necessary to recover the matrix but under strong assumptions. They assumed the existence of two matrices A ∈ R n×ra and B ∈ R n×r b that respectively contains users and items side information, with min(r a , r b ) ≥ r. They further assumed that the true matrix M and the matrices A and B share the same latent information, that is the span of the column vectors of A (resp. B) contains the span of rows (resp. columns) of M . Those assumptions are really strong and hard to meet in practice. Thus their objective is to find the small matrix Z ∈ R ra×r b satisfying: minimize trace(Z) (A.8) such that ∀(i, j) ∈ D, [AZB T ] ij = M ij [START_REF] Chiang | Matrix completion with noisy side information[END_REF] relaxed those assumptions by assuming that the side information may not be perfect and thus look for a solution that balance between classic

A.5 Conclusion

We have seen different works that studied the matrix completion problem from a theoretical point of view. Nuclear norm minimization approaches succeeded to prove that only O(nK log n) entries were needed to recover the entire matrix. This bound was closely approached by alternating least square algorithms but never met. However all those approaches suffer from several issues when applied to collaborative filtering. First the incoherence assumptions on the matrix can be a too strong hypothesis for collaborative filtering since it implies that all users (resp. all items) are really close, which limits the interest of performing individual recommendation. Second, papers on alternating least square algorithm did not take regularizations into account and were sometimes left as future work. Third, in collaborative filtering entries are not reveal at random, some users are much more active than others and likewise some items are much more popular than others. Thus some part of the matrix can be better reconstructed than other parts. Some researches take another direction and focused on the problem of sampling actively relevant entries in the matrix ( [START_REF] Bhojanapalli | Tighter low-rank approximation via sampling the leveraged element[END_REF], Wang and Singh, 2015, Chakraborty et al., 2013]) instead of sampling randomly, and removed incoherence condition. Indeed incoherence condition implies that every entry amount for the same level of information leaving no space for active sampling. We believe that a very good understanding of matrix completion and active sampling can lead to very interesting algorithms in order to improve cold-start performances.