Keywords: collaborative filtering, recommender system, distribution, bloom filter, cold-start, active learning

For this dissertation, I would like to thank őrst of all Raja Chiky. She was the őrst person in my professional, she took an non-experienced Spanish student and give him trust and the possibility to learn and grow. I would not be here today without her support and conődence. I thank my thesis director, Elisabeth Métais, for her encourage during these years and the intern-ship opportunity she ofered me at the University of Salford, Manchester. I also thank my supervisor in this intern-ship, Farid Meziane, for his contribution to my work and for receiving me in Salford as I was one of his own team. I warmly thank ISEP for receiving me, specially to every member of the team RDI. I want to give special thank Sylvain Lefebvre for his help, his support, our long talks and his friendship, and Maria Trocan for taking care of me.

I thank my family. Thank my father for being a model of cleverness and intelligence.

Thank my mother for learning me the afection. Thank my brother for reminding me that hard-work and achievements come together. My self-exigence often blinds me and my family always remind me who I am and what I am capable of.

Thank my other family, my friends. Those who are far-away and those who are nearby. Sathiya, Amadou, Rayane, Loïc and Denis, thank you for the daily smiles we shared together and your unconditional help whenever it was needed (or not). One day, Zakia told me that "phd collegues are friends for the whole life", and I already started missing you. I want to thank my love, Virginia, for supporting me anytime and helping me to put the last and hard period to this thesis.

Finally, thank FIORA project, "DGCIS" and "Conseil Regional de l'Île de France" for funding this thesis.

Abstract

Recommender Systems aim at pre-selecting and presenting őrst the information in which users might be interested. This has raised the attention of the e-commerce, where the interests of users are analysed in order to predict future interests and to personalize the ofers (a.k.a. items). Recommender systems exploit the current preferences of users and the features of items/users in order to predict their future preference in items.

Although they demonstrate accuracy in many domains, these systems still face great challenges for both academia and industry; they require distributed techniques to deal with a huge volume of data, they aim to exploit very heterogeneous data, and they sufer from cold-start, situation in which the system has not (enough) information about (new) users/items to provide accurate recommendations.

Among popular techniques, Matrix Factorization has demonstrated high accurate predictions and scalability to parallelize the analysis among multiple machines. However, it has two main drawbacks: (1) diiculty of integrating external heterogeneous data such as items' features, and (2) the cold-start issue.

The objective of this thesis is to answer to many challenges in the őeld of recommender systems: (1) recommendation techniques deal with complex analysis and a huge volume of data; in order to alleviate the time consumption of analysis, these techniques need to parallelize the process among multiple machines, (2) collaborative őltering techniques do not naturally take into account the items' descriptions in the recommendation, although this information may help to perform more accurate recommendations, (3) users' and items' descriptions in very large dataset contexts can become large and memory-consuming; this makes data analysis more complex, and ( 4) the new user cold-start is particularly important to perform new users' recommendations and to assure new users ődelity.

Our contributions to this area are given by four aspects: (1) we improve the distribution of a matrix factorization recommendation algorithm in order to achieve better scalability, [START_REF]2 Recommender System Libraries[END_REF] we enhance recommendations performed by matrix factorization by studying the implicit interest of the users in the attributes of the items, [START_REF]Experimentation results[END_REF] we propose an accurate and low-space binary vector based on Bloom Filters for representing users/items through a high quantity of features in low memory-consumption, and ( 4) we cope with the new user cold-start in collaborative őltering by using active learning techniques.

The experimentation phase uses the publicly available MovieLens dataset and IMDb database, what allows to perform fair comparisons to the state of the art. Our contributions demonstrate their performance in terms of accuracy and eiciency.

Résumé

Les systèmes de recommandation visent à présélectionner et présenter en premier les informations susceptibles d'intéresser les utilisateurs. Ceci a suscité l'attention du commerce électronique, où l'historique des achats des utilisateurs sont analysés pour prédire leurs intérêts futurs et pouvoir personnaliser les ofres ou produits (appelés aussi items) qui leur sont proposés. Dans ce cadre, les systèmes de recommandation exploitent les préférences des utilisateurs et les caractéristiques des produits et des utilisateurs pour prédire leurs préférences pour des futurs items.

Bien qu'ils aient démontré leur precision, ces systèmes font toujours face à de grands déős tant pour le monde académique que pour l'industrie: ces techniques traitent un grand volume de données qui exige une parallélisation des traitements, les données peuvent être également très hétérogènes, et les systèmes de recommandation soufrent du démarrage à froid, situation dans laquelle le système n'a pas (ou pas assez) d'informations sur (les nouveaux) utilisateurs/items pour proposer des recommandations précises.

La technique de factorisation matricielle a démontré une précision dans les prédictions et une simplicité de passage à l'échelle. Cependant, cette approche a deux inconvénients: la complexité d'intégrer des données hétérogènes externes (telles que les caractéristiques des items) et le démarrage à froid pour un nouvel utilisateur.

Cette thèse a pour objectif de proposer un système ofrant une précision dans les recommandations, un passage à l'échelle pour traiter des données volumineuses, et permettant d'intégrer des données variées sans remettre en question l'indépendance du système par rapport au domaine d'application. De plus, le système doit faire face au démarrage à froid utilisateurs car il est important de ődéliser et satisfaire les nouveaux utilisateurs.

Cette thèse présente quatre contributions au domaine des systèmes de recommandation: (1) nous proposons une implémentation d'un algorithme de recommandation de factorisation matricielle parallélisable pour assurer un meilleur passage à l'échelle, [START_REF]2 Recommender System Libraries[END_REF] nous améliorons la précision des recommandations en prenant en compte l'intérêt implicite des utilisateurs dans les attributs des items, (3) nous proposons une représentation compacte des caractéristiques des utilisateurs/items basée sur les őltres de bloom permettant de réduire la quantité de mémoire utile (4) nous faisons face au démarrage à froid d'un nouvel utilisateur en utilisant des techniques d'apprentissage actif.

La phase d'expérimentation utilise le jeu de données MovieLens et la base de données IMDb publiquement disponibles, ce qui permet d'efectuer des comparaisons avec des techniques existantes dans l'état de l'art. Ces expérimentations ont démontré la précision et l'eicacité de nos approches.

Résumé étendu

Introduction

Le contenu web est devenu très vaste et les utilisateurs rencontrent des diicultés pour trouver une information pertinente. Les utilisateurs d'Internet lisent environ 10 Mo d'information par jour (par exemple, les actualités), entendent 400 Mo par jour (par exemple, musique) et voient, en géneral, 1 Mo d'information par seconde (par exemple, des vidéos)1 . Ils peuvent se sentir débordés en cherchant parmi ce contenu ceux qui sont les plus adaptés à leur proől parce qu'ils n'ont pas le temps ou simplement ils n'ont pas la connaissance pour trouver le plus approprié.

Les systèmes de recommandation réduisent radicalement la quantité d'information présentée aux utilisateurs. Ils analysent leur intêret et présentent d'abord les items (un produit ou un service tels qu' une vidéo, une image, etc) qui les intéresseraient le plus [START_REF] Kantor | Recommender systems handbook[END_REF].

L'intérêt des utilisateurs pour quelques items peut être donné de façon explicite ou implicite appelé également "score". D'une part, l'intérêt explicite, comme une note ou un "rating", est une déclaration formelle de l'intérêt de l'utilisateur. Ces données sont le plus utilisées dans la littératuree. Les utilisateurs peuvent noter des items (par exemple des őlms) utilisant une note entre 1 et 5, où "1" représente le manque d'intérêt et "5" représente un fort intérêt pour l'item. D'autre part, l'intérêt implicite est une déduction donnée par l'interaction web entre des utilisateurs et des items [START_REF] Oard | Implicit feedback for recommender systems[END_REF]]. En efet, il est possible de mesurer les comportements des utilisateurs par les pages Web. Ceci permet de connaître combien de clics un item a reçu ou combien de temps un utilisateur 0.1. INTRODUCTION a passé à consulter un item. De plus, les systèmes de recommandation peuvent incorporer les descriptions des items (par exemple le genre d'un őlm, le chanteur des chansons, les écrivains des livres), les données démographiques des utilisateurs (par exemple l'âge, le sexe, le niveau d'études) et des données venant d'autres contextes, comme Wikipédia, des réseaux sociaux, des coordonées gps, etc, ce qui peut aussi améliorer les recommandations.

Challenges

Les systèmes de recommandation font face à de multiples problématiques tels que la volumétrie et analyse de la donnée, l'hétérogénéité de la donnée, ainsi que la précision de recommandations. Ces déős sont résumés par la suite: Adaptabilité et passage à l'échelle: le grand nombre d'utilisateurs, d'items et de scores supposent l'analyse d'une grande volumétrie de données, ce qui nécessite beaucoup de ressources et de temps. Il est nécessaire de créer des techniques de recommandation où le calcul est facilement parallélisable et incremental [START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF], Koren, 2010, Owen et al., 2011].

Hétérogénéité de la donnée: les systèmes de recommandation peuvent utiliser des informations hétérogènes externes autres que les intérêts des utilisateurs. Ces systèmes utilisent typiquement des ressources d'information multiples pour améliorer les recommandations [START_REF] Kantor | Recommender systems handbook[END_REF], par exemple les descriptions des items, les descriptions des utilisateurs, etc. Le déő de ces systèmes est de récupérer, classiőer et intégrer ces informations, ce qui implique davantage de complexité, et afecte les performances du système. Démarrage à froid: c'est la situation dans laquelle le système n'a pas (ou pas assez) d'informations sur un nouvel utilisateur/item, c'est-à-dire leur score; et par conséquence, les recommandations de l'utilisateur (ou de l'item) ne sont pas pertinentes [START_REF] Su | [END_REF]Khoshgoftaar, 2009, Kantor et al., 2011].

L'objectif de cette thèse est d'améliorer les systèmes de recommandations en répondant aux déős cités précédemment.

ÉTAT DE L'ART

État de l'art

Les systèmes de recommandation se doivent de sélectionner les informations les plus intéressantes en fonction du but recherché, tout en conciliant nouveauté, surprise et pertinence. Un système de recommandation se base sur des caractéristiques de références acquises de manière automatisée selon des méthodes diférentes. Elles peuvent provenir de:

• L'item (l'objet à recommander) lui-même, on parle alors "d'approche basée sur le contenu" (ou content-based approach) [START_REF] Balabanović | Fab: contentbased, collaborative recommendation[END_REF]. Le őltrage basé sur le contenu calcule la similarité entre les objets aőn de trouver l'objet correspondant le plus aux goûts de l'utilisateur. Dans ce cas, l'utilisateur se voit recommander des items similaires à ceux qu'il a préférés dans le passé.

• L'utilisateur et l'environnement social, on parle alors "d'approche de őltrage collaboratif" (ou collaborative őltering). Le principe du őltrage collaboratif [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative őltering[END_REF]] consiste à implanter informatiquement le principe du "bouche-à-oreille". Il utilise les comportements connus d'une population pour prévoir les futurs agissements d'un individu. La méthode collaborative présente des avantages par rapport au őltrage basé sur le contenu: elle est plus eicace dans la pratique et simple à mettre en oeuvre. Notamment, il a été prouvé que les techniques de factorisation de matrice fournissent des résultats précis et ont l'avantage d'être facilement parallélisable (pour la montée en charge et le passage à l'échelle) [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

Les milieux académiques et l'industrie ont investi leurs eforts dans le champ de la recommandation. Plusieurs études ont montré que la technique de factorisation matricielle est l'une des plus importantes contributions. Elle est apparue pendant le prix de "Netŕix" et elle a aidé les nouveaux systèmes à améliorer la précision et le passage à l'échelle des techniques de recommandation. Cette technique n'utilise pas les descriptions, donc n'aide pas à l'incorporation de données hétérogènes. De plus, elle est très sensible aux situations de démarrage à froid et "sparsité". En conséquence, plusieurs travaux dans le milieu industriel mais aussi académique la combinent avec d'autres approches, notamment des approches utilisant le contenu des items, pour améliorer la performance globale des recommandations.

DESCENTE DE GRADIENT STOCHASTIQUE ET DISTRIBUÉE

Cette thèse assume la factorisation matricielle comme la technique de principe dans les systèmes de recommandation et vise à aller au-delà de cette technique. Nos contributions se concentrent (1) sur le passage à l'échelle de la factorisation matricielle pour réaliser la meilleure performance dans des clusters Hadoop, (2) l'intérêt implicite d'utilisateurs dans les descriptions des items et comment réduire l'impact du domaine de recommandations,

(3) les représentations des items et utilisateurs dans des très grands contextes de données et (4) le démarrage à froid orienté aux nouveaux utilisateurs pour des techniques de őltrage collaboratives pures. Notre but őnal est que ces contributions aident les systèmes de recommandation à mieux manipuler des données et comprennent mieux les utilisateurs pour améliorer la performance du système et la précision des recommandations.

Descente de gradient stochastique et distribuée

Le nombre d'utilisateurs et d'items dans un système de recommandation est habituellement très élevé. Par exemple, Netŕix dispose de plus de 20 millions de clients, 80 milliers de őlms et 5 milliards de notes [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. En général, les utilisateurs notent uniquement certains de ces items et cela crée un grand volume d'évaluations manquantes/inconnues pour prédire. Ainsi, ces prédictions peuvent afecter le temps ede traitement. Les nouveaux systèmes de recommandation devraient être précis dans leurs prédictions mais aussi parallélisables pour soulager la montée en charge et le temps de traitement des données.

Ce travail se concentre sur la technique de factorisation matricielle appelée la descente distribuée et stochastique de gradient (Distributed Stochastic Gradient Descent (DSGD)), contrairement aux technnique de optmisation par moindres carrés (Alternating Least Squares (ALS) [START_REF] Zhou | Large-scale parallel collaborative őltering for the netŕix prize[END_REF]). Les contributions dans ces aspects sont: (1) une mise en oeuvre de cette technique dans Hadoop/MapReduce, et [START_REF]2 Recommender System Libraries[END_REF] nous avons étudié cette technique pour améliorer son adaptabilité dans un ensemble de machines et ainsi améliorer la performance des recommandations.

DESCENTE DE GRADIENT STOCHASTIQUE ET DISTRIBUÉE

Contribution et résultats

L'idée proposée dans [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], Makari et al., 2014] consiste à diviser une matrice initiale composée d'utilisateurs, d'items et de ratings en plusieurs blocs, de façon à ce qu'il y ait un certain nombre de blocs qui soient complètement indépendants (qui ne partagent pas d'utilisateurs ni d'items). Ces blocs indépendants forment un ensemble appelé "stratum". Lorsque les blocs sont indépendants, leur analyse est indépendante et leurs résultats sont aussi indépendants et agrégeables. Par conséquent, l'analyse des ratings (des blocs) dans le stratum peut être distribuée parmi plusieurs machines. Au maximum, autant de machines que de blocs dans le stratum sont éxéctuées en parallèle. En créant diférents stratums (avec d'autres blocs indépéndants) il est possible de faire l'analyse de la matrice initiale complète.

Le problème que nous avons soulevé réside dans la décomposition de la matrice initiale en blocs. Imaginez une matrice de dimensions n u x n i , le point-clé dans la décomposition de bloc est la divisibilité des dimensions dans des parties d'un entier. Cela signiőe que les dimensions pourraient être divisibles par b ("b" étant la quantité de machines disponibles à utiliser en parallèle) pour proprement créer des blocs (n u %b = 0 et n i %b = 0). Mais ceci n'est souvent pas le cas.

Dans [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], Makari et al., 2014], l'efacement de rangées/colonnes (c'està-dire des utilisateurs/items) résout cette condition de divisibilité. Cependant, ceci peut créer une perte d'exactitude: si le nombre de données supprimées est élevé, le système peut perdre des informations importantes. En fait, cela représente un compromis entre précision et ŕexibilité. Au contraire, l'ajout de dimensions peut augmenter le temps d'exécution de l'algorithme. Cependant, ceci n'afecte pas la précision, vu que l'insertion de la dimension vide n'ajoute pas d'information.

En utilisant ces idées, nous avons développé un aspect plus ŕexible dans la distribution.

Nous proposons trois modes de décomposition de blocs qui afectent la création des "stratums": (1) sous-dimension, (2) dimension supérieure et (3) dimension ŕexible. Dans ce contexte, une dimension est un utilisateur (dimension de rangées) ou un item (dimension de colonnes). La sous-dimension est la proposition donnée par [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. Ce

L'INTÉRÊT IMPLICITE DES UTILISATEURS DANS LES ATTRIBUTS DES ITEMS

mode redimensionne la matrice en supprimant des dimensions. La dimension supérieure redimensionne la matrice en insérant des dimensions vides jusqu'à l'accomplissement de la condition de décomposition. Finalement, la technique de dimension ŕexible est un hybride de ces deux techniques. Elle cherche la dimension la plus proche (dessus ou dessous) des dimensions réelles.

Nous évaluons la performance de nos propositions en utilisant le jeu des données publiques de MovieLens2 , qui a 10 millions d'évaluations appliquées par 69878 utilisateurs sur 10667 őlms. Nous créons une matrice de rangées et des colonnes avec les notes des utilisateurs aux items. L'évaluation et les comparaisons sont efectuées en termes de précision et d'adaptabilité au nombre de machines dans le cluster.

Nos techniques donnent un meilleur résultat en termes de précision lorsqu'elles évitent l'efacement de données (utilisateurs, items et ratings). Le Tableau 1 présente une comparaison de nos résultats avec des autres techiniques de factorisation matricielle, où la mesure de précision utilisée est le erreur moyenne quadratique (RMSE). Nous gagnons environ 1% d'amélioration en exploitant les machines dans le cluster (quantité de noueds b).

L'intérêt implicite des utilisateurs dans les attributs des items

Les technologies de recommandation font aujourd'hui face à des déős scientiőques majeurs: comment intégrer l'hétérogénéité des sources d'information pour modéliser les préférences, comment découvrir des nouvelles préférences, comment traiter eicacement ces masses d'information, quels types d'interfaces faut-il considérer?

Par ailleurs, les approches őltrage collaboratif et basé sur le contenu citées précédemment présentent des inconvénients principalement liés à l'hétérogénéité des sources d'information et à la montée en charge du système d'où la nécessité de mettre en place des algorithmes performants et robustes. Ceci est l'objectif de cette étude en vue d'améliorer la qualité des systèmes de recommandation en introduisant de la "sémantique" aux données et en 0. distribuant les traitements aőn de minimiser les temps de calcul. La "sémantique" est ici déőnie comme une extension dans le sens de la donnée courante, les scores (ratings), aőn de créer des "ratings sémantiques". La couche sémantique exploite cette nouvelle information ainsi que le rating données par les utilisateurs pour les items. Ceci se traduit par la transformation sémantique des notes des utilisateurs. Nous nous intéressons tout d'abord au nombre d'occurrence des attributs qui ont été notés par un utilisateur. Nous appelons cette occurrence ń la fréquence d'apparition ż ou ń coïncidence ż : cette valeur correspond au nombre de fois que les valeurs des attributs se répètent dans les items notés par l'utilisateur. Cette valeur est extraite à partir des compteurs déjà précalculés. La transformation du rating consiste en l'addition de ce nouvel intérêt implicite à l'intérêt explicite, à travers l'équation suivante:

Contribution et résultats

sv u,i = r u,i + E[r u, * ] * ⏐ ⏐ ⏐ ∑ F j=1 C j * W j ⏐ ⏐ ⏐ N u (1)
Avec F le nombre total des attributs, N u le nombre total des items notés par l'utilisateur "u". C j est la fréquence d'apparition de l'attribut j dans l'ensemble des items qui ont été notés par l'utilisateur et W j étant un poids calculé à partir d'une phase de sélection des attributs par une analyse des composantes principales. E[r u, * ] est la moyenne des notes de l'utilisateur et r u,i est la valeur du rating initial donnée à l'item "i".

MODÈLE DE SIMILARITÉ AVEC DES FILTRES DE BLOOM

En efet, cette technique a montré son eicacité comme méthode de őltrage collaboratif pour la recommandation [START_REF] Koren | Advances in collaborative őltering[END_REF].

Dans la phase d'expérimentation, nous comparons nos approches (appliquer la "sémantique" aux ratings initiaux, ou bien aux prédictions dans le top-K) et la technique de factorisation matricielle de base sans l'utilisation de l'équation sémantique. Nous utilisons les métriques de précision et rappel, parce que ces techniques n'évaluent pas la qualité de la prédiction des notes, mais la pertinence des items qui sont proposés aux utilisateurs.

La précision calcule la probabilité qu'un item pertinent soit choisi et le rappel étant la probabilité qu'un item choisi soit pertinent. Nous utilisons aussi la F-mesure pour combiner le rappel et la précision dans une seule métrique aőn de faciliter la comparaison. Nos approches donnent de meilleurs résultats que la technique de matrice de factorisation sans sémantique.

De plus, nous nous sommes interessés à l'impact de nouveaux ratings sémantiques sur la similarité des items à recommander. Nous utilisons la métrique d'ILS (Intra-List Similarity), appelée également ILD (Intra-List Diversity) pour mesurer la diversité/similarité entre les items dans la liste des top-K présentée à l'utilisateur.

Un bon système de recommandation doit trouver l'équilibre entre ces deux concepts diversité et similarité. En efet, des items trop diversiőés peuvent provoquer une confusion chez l'utilisateur, alors que recommander toujours les mêmes items peut ennuyer celuici. La matrice de factorisation a tendance à faire de recommandation diversiőées. Notre approche permet, dans cette diversité, de retourner des items plus similaires dans le top-K.

Ceci est du au fait que nous prenons en compte l'intérêt pour les attributs aőn d'identiőer les items susceptibles d'intéresser l'utilisateur.

Modèle de similarité avec des filtres de Bloom

La description des items et d'utilisateurs peut être très précise puisqu'un grand nombre de caractéristiques peut être utilisé (par exemple des acteurs, des directeurs, des auteurs).

On peut même imaginer l'incorporation de données externes telles que les données ouvertes ou des données provenant de réseaux sociaux, etc. pour mieux décrire les items/les utilisa-0.5. MODÈLE DE SIMILARITÉ AVEC DES FILTRES DE BLOOM teurs [START_REF] Kantor | Recommender systems handbook[END_REF], Peis et al., 2008, Dahimene et al., 2014]

Contribution et résultats

Nous proposons d'utiliser des représentations de őltre de bloom. Un őltre de bloom est une structure de bit qui représente "n"-éléments d'un même ensemble "S" dans un espace plus réduit de "m"-bits [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. Initialement, les m-bits sont mis à "0" ce qui représente l'absence des éléments insérés dans le őltre. Puis, on utilise "k" fonctions de hachage pour distribuer eicacement l'insertion des éléments: pour insérer un élément, celui-ci est "haché", ce qui retourne "k" positions de la structure de bits à passer à "1". obtenir des données (ratings) de grande qualité [START_REF] Elahi | Active learning in collaborative őltering recommender systems[END_REF]. Un questionnaire simple est utilisé pour obtenir les premiers ratings rapidement, par exemple: aimez-vous ce őlm? pouvez-vous noter ce livre?. Donc, on demande aux utilisateurs de répondre à ces questions en donnant leur avis, de cliquer par exemple sur "j'aime", "je n'aime pas" ou "je ne connais pas".

Cependant, les utilisateurs ne souhaitent pas évaluer beaucoup d'items et poser beaucoup de question car cela peut supposer une perte de temps pour eux [START_REF] Harpale | [END_REF]Yang, 2008, Karimi et al., 2011a]. En conséquence, les questionnaires devraient être courts et rapides dans l'analyse. Il faudra donc poser des questions soigneusement choisies pour récuperer le plus d'information des utilisateurs [START_REF] Zhou | Functional matrix factorizations for cold-start recommendation[END_REF], Karimi et al., 2011a].

Nous proposons une technique d'apprentissage actif basée sur le concept des arbres de décision. Le but des arbres de décision dans l'apprentissage actif est de diviser la population d'utilisateurs selon leurs préférences sur quelques produits.

Ainsi, des utilisateurs dans le noeud de l'arbre ont tendance à partager des préférences semblables. En descendant dans l'arbre, ces groupes sont rainés et les préférences sont mieux détectées. Ces techniques, dans un contexte de őltrage collaboratif, ont seulement accès aux notes des utilisateurs sur les items, i.e. ratings. Par conséquent, ces techniques ont pour but de découvrir des items dans chaque noeud de l'arbre, qui séparent eicacement la population des utilisateurs selon leurs ratings pour ces items.

Cette idée est très utile pour améliorer la performance du système de recommandation dans un contexte de démarrage à froid. Un noeud est représenté par une question (l'item), par exemple "aimez-vous ce őlm?". Le nouvel utilisateur peut donc répondre à ces questions. En donnant la réponse, le système identiőe mieux les préférences de cet utilisateur et peut trouver une meilleure nouvelle question à lui poser en utilisant l'arbre de décision.

Contribution et résultats

Les techniques d'arbres de décision actuelles exploitent seulement les ratings existant dans R pour (1) la découverte de questions à poser, (2) la segmentation de la population 0.7. CONCLUSIONS ET PERSPECTIVES à partir de questions et (3) le calcul de prédiction de ratings que le nouvel utilisateur pourrait donner (la prédiction de la réponse). Le problème est donc, à chaque noeud de l'arbre de décision, de trouver un item qui permettra de mieux identiőer les préférences d'un nouvel utilisateur. Ceci est un problème d'optimisation qui se sert des ratings existant dans chaque noeud de l'arbre pour trouver le meilleur item à proposer comme question.

Cette technique utilisée dans l'état de l'art est simple pour que l'arbre de décision soit rapide à construire. Elle utilise uniquement les ratings des utilisateurs pour prédire la moyenne et ainsi évaluer la pertinence à poser cet item comme question.

Nous proposons d'utiliser non seulement le rating r d'un utilisateur u pour un item j, mais aussi une prédiction p de rating d'un utilisateur u pour un item j, de sorte qu'il y ait toujours un rating r u,j associé à une prédiction p u,j .

Nous proposons d'utiliser des évaluations r u,j uniquement pour diviser la population d'utilisateurs. Les prédictions p u,j seront ainsi utilisées pour découvrir des items à poser comme question.

Notre approche est implementée en utilisant une technique d'arbres de décision non supervisée et une autre technique supervisée. Nous comparons les deux approches avec l'état de l'art existant. Nos approches sont capables de trouver des items plus pertinents que les items trouvés par les approches de l'état de l'art. Ainsi, nos approches identiőent les préférences des nouveaux utilisateurs plus rapidement (en un moindre nombre de questions). En efet, la qualité de la représentation d'utilisateurs et des items est afectée tout comme les opérations de similarité parmi les items. Nous avons proposé de représenter des items/utilisateurs dans des structures spatiales de très basse consomation de mémoire appelées őltre de bloom. De plus, ceci nous permet de déőnir deux mesures de similitude: "AND", pour prendre en compte des caractéristiques communes, et "XNOR", pour prendre en compte des caractéristiques communes et des caractéristiques manquantes communes.

Conclusions et Perspectives

• Amélioration de la précision et de l'adaptabilité d'une technique de factorisation matricielle en proposant une approach distribuée basée sur MapReduce.

Introduction and Motivation

"We are leaving the age of information and entering the age of recommendation"

-Chris Anderson in "The Long Tail"

Introduction

The web content has become so vast that users hardly őnd the information they are looking for. People read around 10 MB of data per day, hear 400 MB of audio per day, and see 1 MB of information every second1 . In 2015, the media information consumption was estimated to 74 GB per consumer and per day2 . Users may feel overwhelmed by this huge content because they may not have the time or simply they do not have the knowledge about what őts better to their needs.

Recommender Systems (RS) emerge from the Information Search and Retrieval (IR) őeld in order to cope with this information overload and decision-making issues. The information retrieval systems seek and őlter information depending on users' queries [START_REF] Baeza-Yates | Modern information retrieval[END_REF]. These systems used to represent textual content (e.g. web pages and articles) as a set of words that are then matched with users' requests to return the relevant information for the user in a non user personalized experience; all users receive the same information for the same queries. Recommender Systems aim to cope with these issues by personalizing the content in webs for users [START_REF] Kantor | Recommender systems handbook[END_REF]. Indeed, they

DEFINITION AND PROCESS OF RECOMMENDER SYSTEMS

analyze the interaction of users with the information in webs in order to predict the future interactions that suit the users' interests. This allows to őlter and organize items in order to present őrst the items of users' interest, i.e. recommendations.

Recommender systems dramatically reduce the amount of information presented to users and "delivers the correct information to the correct users" [START_REF] Zhou | Functional matrix factorizations for cold-start recommendation[END_REF]. The őrst recommender system, "Tapestry" [START_REF] Goldberg | Using collaborative őltering to weave an information tapestry[END_REF], appeared in 1990 and it also worked looking for text-similarities and automatically learning from the users preferences.

However, it did not contemplate non-text-similarities; it only analyzed text-content but not other contents such as videos, audio, etc. New techniques to aford this singularity emerged and the concept of "item" appeared to involve textual and non-textual information. Hence, it attracted the interest from many őelds, such as e-commerce, service providers and media services, with the aim of personalizing the services and users' experience.

Nowadays, recommender systems are well studied in the academia and the industry.

They are daily present almost everywhere giving suggestion of where to eat, which movie to watch, which articles to read, whose to be friend with, the publicity we receive, etc. The Internet is moving from the era of search to the era of recommendations; the searching allows to look for a speciőc information, whereas the recommendations allow to discover information you are not speciőcally looking for although it is of your interest. We stop looking for information, and information starts őnding us.

As introduction to this thesis work, we őrst formally deőne recommender systems and present the recommendation actors and the recommendation process in Section 1.2. Section 1.3 presents the trend challenges for recommender systems. Section 1.4 presents our motivation and the main guidelines of our researches.

Definition and process of recommender systems

Recommender systems analyse the interests of users and present őrst the items in which they might be more interested [START_REF] Kantor | Recommender systems handbook[END_REF]. Their main purpose is to assist users in their daily decision-makings by presenting a reduced set of options in the form of recommendations or advices [START_REF] Chee | Rectree: An eicient collaborative őltering method[END_REF].

DEFINITION AND PROCESS OF RECOMMENDER SYSTEMS

The users' interests represent the strength of their relations with items. They are also known as "score" or "feedback". On the one hand, the explicit feedback is a formal declaration of the user. The most typical explicit interests are the rating systems, where users can evaluate/rate items (e.g. movies) using a 0-5 stars scale. Other shorter and larger scales are possible, such as 'like, dislike, unknown', 0-10 stars, 0-20 stars. Another kind of explicit feedback may rely on comments and opinions. This feedback is usually processed using Natural Language Programming (NLP) to really understand the meaning of users' sentences, such as sentiment analysis. On the other hand, the implicit feedback is an interest deduction given by the interaction between users and items [START_REF] Oard | Implicit feedback for recommender systems[END_REF]]. The so-called tracking systems measure the users' behaviors through the web-pages and collect users' examination (e.g. item selection), retention (e.g. save item, print page)

and reference (e.g. share). This is based on the count of number of clicks, time spent on exploring an item, users' location, etc. It is worth to mention that recommender systems can use other kind of information to enhance the accuracy of recommendations [START_REF] Kantor | Recommender systems handbook[END_REF]. For instance, it is possible to incorporate the items' descriptions (e.g. the genre of a movie, the singer of songs, the author of books), the users' demographics (e.g.

the age, the sex, the education) and data coming from other contexts, such as Wikipedia, social networks, gps-locations, etc.

Recommender systems are good to őnd a set of items in which the user can be interested, and to guess the interest (e.g. rating) that a user would have in a particular item. On the one hand, the term "user" is often used to deőne the (active) user for whom recommendations are currently required. On the contrary, the term "item" is very large and depends on the domain of the recommendation. For instance, recommender systems dealing only with movies would consider a movie as an item. Moreover, an item can be one user, such as the suggestions of a "friend" or a contact in social networks.

The users, items and feedbacks are the core-stone of the information used in recommender systems. This data is formatted, treated and analyzed by using techniques from data mining and machine learning őelds in order to generate recommendations. Figure 1.1

shows the typical workŕow representing the recommendation system process.

The incoming data is composed of, at least, the users' interests in items. Other data 1.3. CHALLENGES IN RECOMMENDER SYSTEMS fake ratings to promote or degrade items) [START_REF] Lam | Shilling recommender systems for fun and proőt[END_REF]. Moreover, how many recommendations to present to users can be also a challenge: a few items may not be enough for the users' needs, and too many items may be too much. Where to place these recommendation to optimize the site-look and users' experience is also an interesting challenge.

In this section we consider the most simplistic representation of a recommender system process which assumes to have prepared incoming data ready to be analyzed by recommendation techniques in order to produce recommendation to users. As a consequence, we mainly focus on the challenges related to the recommendation techniques.

Scalability

The number of users, items and feedback can increase rapidly. Recommendation techniques may become computationally expensive and very time-consuming. It is necessary to parallelize the computation of these techniques among several processors or machines and to create easily incremental models in order to receive new data [START_REF] Sarwar | Incremental singular value decomposition algorithms for highly scalable recommender systems[END_REF], Koren, 2010, Owen et al., 2011].

Data heterogeneity

Recommender systems can use external heterogeneous information in addition to users' interests in items. These systems typically use multiple information resources to enhance the recommendations to users [START_REF] Kantor | Recommender systems handbook[END_REF], e.g. the items' descriptions, users' keywords for items, users' descriptions, etc. The challenge of these systems is to retrieve, classify and integrate this big, heterogeneous and diverse information to the sake of recommendations, what usually induce more complexity and has a negative impact on the scalability of the system.

Similarity/Diversity

Recommendations to one user should not be always similar (e.g. comedy movies), otherwise the user could get bored. On the contrary if recommendations are too diverse, it can generate an untrusted feeling in the user. This is part of a similarity/diversity trade-of that a recommender system should take into account [START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF].

CHALLENGES IN RECOMMENDER SYSTEMS

Sparsity

This often happens when the number of items is much larger than the number of users;

and thus it is very complicated to have feedback for all items, e.g. there are millions of books in Amazon but a user may have bought hundreds of books. This situation generates poor informative datasets [START_REF] Su | [END_REF]Khoshgoftaar, 2009, Kantor et al., 2011].

Cold start

The cold-start is the situation in which the recommender system has no or not enough information about the (new) users/items, i.e. their ratings/feedback; hence, the recommendation to users (or of items) are not well performed [START_REF] Su | [END_REF]Khoshgoftaar, 2009, Kantor et al., 2011]. Particularly, the new user cold-start is the lack of users' preferences and the new item cold-start is the lack of ratings for this item.

Time-aware recommendations

Recommendation techniques exploit the current known users' interest in items. These may be linked to timestamps and thus it is possible to identify long time distant preferences as well as very recent ones. Generating proper recommendations by taking this information into account makes proposed recommendation to evolve accordingly to the users' preferences [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF].

Multi-type and multi-criteria recommendations

On the one hand, multi-type recommendations aim to recommend not only the item itself, but also relevant information related to this item [START_REF] Zhuo | A framework for multi-type recommendations[END_REF]. For instance, in a restaurant recommendation it is interesting to suggest the route to go to the restaurant.

On the other hand, common recommender systems are considered single-criterion, because they only analyze the interest of users in items. Multi-criteria recommendations suggest that users' feedback are a result of combinations of several interests [START_REF] Lakiotaki | Uta-rec: a recommender system based on multiple criteria analysis[END_REF], Kantor et al., 2011]. For instance, the rating of a movie (considered as an item) may depend on precise aspects, such as the main story and the special efects. However,

CHALLENGES IN RECOMMENDER SYSTEMS

the feedback for these other criterion are also required. Indeed, this method assumes that collecting more diversiőed data results in more accurate recommendations. In addition, multi-criteria systems may go further considering cross-domain recommendations, where ratings of users in one item's domain (e.g. movies) can be used for other completely diferent domains (e.g. restaurants) by looking for similarities in the interests of this user and other users in both domains (e.g. users who liked the same movies and they agree in one restaurant, may agree in other restaurants as well).

Exploration versus exploitation

In fact, recommender systems tend to be more accurate in predicting very popular items (i.e. items from which many ratings are known), and hence these items are more recommended as well. As a consequence, less rated items are little by little forgotten by the system. Under this context, the exploration paradigm consists in letting the user freely navigate among the items to discover and rate new unexpected items. On the contrary, the exploitation paradigm refers to the usage of the users' interest (explicit or implicit) and the persistence of recommendations, e.g. to continuously recommend the same items to users when these suggestions have not been taken in several occasions. How intrusive the recommender system may be in the life of users is an interesting exploration-exploitation trade-of to take into consideration [Balabanović, 1998, Rubens et al., 2011].

Users' experience: explanations and data privacy

The explanation of recommendations is an important factor for users decision-makings process [START_REF] Tintarev | Designing and evaluating explanations for recommender systems[END_REF]. The perception of quality and variety in recommendation is part of the users' experience. In some cases, this may create a lack of trustiness and conődence due to associated risks in accepting recommendations, e.g. to buy a book against to buy a car. In fact, users are not willing to risk much based on recommendations they do not understand [START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF]. The explanation of recommendations may alleviate this issue and it helps the users to make reasonable decisions [START_REF] Herlocker | Explaining collaborative őltering recommendations[END_REF].

In addition, the explanations come across three axis that recommender system should 1.3. CHALLENGES IN RECOMMENDER SYSTEMS accomplish [START_REF] Bonhard | [END_REF]Sasse, 2006, Knijnenburg et al., 2012]: (1) transparency, to explain how the recommendation was performed, e.g. the users and/or items correlations involved;

(2) trust, to encourage the user to accept recommendations; and (3) scrutability, which allows the user to interact with the system to communicate possible mistakes to avoid in the future. To deal with these axis is a complex challenge in recommender systems due to the heterogeneity of data and the representation of the information to explain (e.g. visualization). However, this challenge has to take the privacy of the user and his data into consideration.

Users' classification: grey sheep and black sheep

The grey sheep and black sheep are user classiőcation issues where the system has not a clear understanding of some users' preferences because they are too diverse (grey sheep)

or too speciőc (black sheep), what makes diicult to compare to other users' preferences [START_REF] Su | A survey of collaborative őltering techniques[END_REF]. These challenges are complex to detect and sometimes are considered as acceptable drawbacks in recommender systems.

Other challenges

There are other challenges in recommender systems. For instance, there is a need to trust in the explicit ratings made by users. This data has a strong impact on recommendations, and hence more accurate rating lead to better recommendations. These challenges rely on the quality of the ratings. Some authors assume and accept this property of the data, although other authors aim to test and qualify this data [START_REF] Amatriain | Rate it again: increasing recommendation accuracy by user re-rating[END_REF], e.g. by asking users to re-rate a known item. Another example is the recommendation to/in groups of users/items. This challenge requires to satisfy several needs from users or to adapt items for users in order to create a unique but successful recommendation.

The recommendation to groups deals with many users under the same current context.

For instance, what kind of music to recommend in a party [Masthof, 2011], or what TV programme suits to all members of the family. On the contrary, the recommendation in groups try to create mini set of items to propose together to the same user [START_REF] Konstan | Recommender systems: from algorithms to user experience[END_REF]. One example is the often ofered tourism package of ŕight, hotel and rental 1.4. MOTIVATION car set, or the bought-together package of Amazon.

Motivation

This chapter has introduced recommender systems and has given the őrst guidelines about the recommendation process and the challenges currently existing in this őeld.

Our main concern is the volume and variety that these systems face. On the one hand, the huge quantity of information (users, items, feedback and external data) makes the recommendation process analysis complex and time-consuming for one single machine. It is necessary that recommendation techniques become scalable and parallelizable among multiple machines to alleviate this issue. On the other hand, using heterogeneous data is not trivial in recommender systems. There are techniques that are explicitly designed to exploit it and others which simply assume it is not necessary. We believe that recommender system would evolve to improve the integration of all kind of data in order to achieve better accuracy and larger recommendation contexts. In addition, this heterogeneity together with the high volume of data induce to complex users and items representations. In fact, it is possible to highly detail users' and items' descriptions, however this data representation would become very diicult to deal with in terms of memory-space-consumption and exploitation of representations. Finally, there is a major challenge in recommender systems which is the cold start, particularly, the new user cold start. This typically occurs when new users sign up to the system and recommendations are required. As long as the recommender systems has not information about this user and/or his preferences, proper recommendation are nearly impossible.

Our role of this thesis is to answer to these challenges in terms of research and development. Chapter 2 presents the state of the art in the őeld of recommender systems. We őrst explain the assumptions, advantages and disadvantages of diferent recommendation techniques. Second, we give related works in the academic and industrial researches. In addition, recommender systems libraries are presented.

Chapter 3 deals with the scalability and parallelization of recommendation techniques.

We analyze the matrix factorization techniques, which have demonstrated to be highly 1.4. MOTIVATION parallelizable, and its scalability within a cluster of machines. Our goal is to enhance the parallelization of one particular matrix factorization technique called Stochastic Gradient Descent, which have demonstrated better accuracy in recommendations than other matrix factorization techniques but a more complex parallelization.

Chapter 4 focuses on the integration of heterogeneous data into the recommendation process. Our goal is that, collaborative őltering techniques, such as the matrix factorization, may exploit the items' description as well in the beneőt of users' recommendations.

We propose extract a new source of knowledge from past users' interests by using the items' descriptions: we analyze the interests of users in the description of items and not only in the item itself. This new information is added to the current interests of users in item and used by collaborative őltering approaches to compute more accurate recommendation for users.

In Chapter 5 we discuss that the integration of heterogeneous data to describe users and items may have an efect in the accuracy of such descriptions. Typically, the more data the system uses the better the users and items are detailed. However, this could lead to very long and diicult to handle descriptions. Our goal in this context is to create a low-memory space model that takes into account the high detailed descriptions and makes easy to compare users and items to compute similarities. Particularly, our model can őnd similarities of two items by looking for common descriptions (e.g. one actors who plays in two diferent movies), and by looking for common missing-descriptions (e.g. one actor who does not appear in two movies). We consider that these can be interesting aspects in recommender systems: one user may declare that he does not like sport movies by showing low interest in these movies, however, other users who do not like sport movies simply do not watch/show interests in them.

Chapter 6 focuses entirely on the new users cold-start issue. New users who do not receive pertinent recommendations may abandon the system. In order to cope with this issue, we propose to use active learning techniques into recommender systems. These methods make the new users to interact with the system by presenting a questionnaire that aim to understand their preferences. Questions are related to items, e.g. "do you like this book?". The answers reŕect the degree of interest of users in the item, e.g. "yes", "no", 1.4. MOTIVATION "I have not read it (unknown)". As a consequence, the system can learn from these answers the preferences of users. The goal of active learning is to correctly choose the questions (items) for users. Thus it is necessary to personalize the questionnaires to retrieve the maximum of information possible (i.e. to avoid "unknown" answers). Under this context, we propose an active learning technique that exploits past users' interests and past users' predictions in order to őnd out the best questions to pose.

Finally, this thesis has been funded under the context of a collaborative project called "FIORA"3 , which aims to build a generic (to be exchangeable to diferent domains), robust (to be eicient and trustworthy) and scalable (to deal with high quantity of data)

recommender system. The applications of this project are oriented to the e-nutrition4 and e-tourism domains [START_REF] Cherő | Enrichissement d'une base documentaire pour un système de recommandation dans le tourisme. I2D-Information[END_REF]. Our main goal in this project was to provide a robust collaborative őltering algorithm and to cope with the cold-start issues. Under this context, we have delivered algorithms, development code and technical reports. As long as the FIORA project was in progress and the data from users and items was not available, we decided to use public datasets for the experimentation purposes, e.g. Movielens5 and IMDb6 . Thus, in this thesis we only present the contributions made to the őeld of recommender systems. Particularly, we do not present the FIORA project and we do not show the performances on this project.

Chapter 2

Recommender Systems: State of the Art

Motivation

Recommender Systems aim at personalizing the content in webs depending on users' preferences. Their main goal is to predict which items (e.g. movies, books, songs) are of the user's interests and present them őrst. The challenges that recommender systems have to cope with are very diverse and complex to accomplish them all in one single solution.

[ Manouselis andCostopoulou, 2007, Manouselis et al., 2013] have already presented a categorization framework for recommender systems. They have studied around 40 recommender systems and classify them in multiple categories and sub-categories, such as the services provided (e.g. single recommendation, top-K recommendations, őnd most similar items), the architecture (e.g. centralized, distributed, storage mode, etc) and the recommendation techniques (e.g. user/item classiőcation, data representation, etc). However, this last category is the most extended and analyzed in literature [Burke, 2002, Kantor et al., 2011]. The categorization of recommender systems by the recommendation techniques cares, among other topics, about the data used to perform recommendations, the representation of this data, the algorithms of personalization and the output of recommendations.

A second and more simple categorization of recommended systems was given in [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF]. The authors propose to divide existing recommendation techniques in three Hybrid methods [START_REF] Kantor | Recommender systems handbook[END_REF]. This categorization takes into account the two most common recommendation techniques (collaborative őltering and content-based) and suggests several techniques to combine them [Burke, 2002]. In this chapter we follow this categorization, we explain them and we show their possible variations under an academic and industrial point of view.

This chapter aims to present the related work in the őeld of recommender systems.

Section 2.2 explains the techniques' assumptions and the main background. Section 2.3 presents the approaches made by researches in the academy. On the other hand, Section 2.4

shows some recommender systems in the industry. It is also interesting to compare current existing libraries in order to establish a development reference, which appears in Section 2.5. Finally, we conclude this state of the art in Section 2.6 by giving some discussion about the studied approaches and how our thesis is placed in this context. Other approaches in literature more linked to each speciőc contribution of this thesis are discussed inside the proper chapters.

Techniques and assumptions

This section aims to resume the most known recommendation techniques. We aim to lay down the ground to better understand the assumptions of the diferent techniques and how this afects to the recommendation techniques their-selves. We give special emphasis to collaborative őltering and content-based techniques. Nevertheless, other approaches though further of our scope are also described. Finally, hybrid approaches are also highly

TECHNIQUES AND ASSUMPTIONS

Collaborative Filtering (CF)

Collaborative őltering is probably the most known and common technique [START_REF] Shambour | A hybrid multi-criteria semantic-enhanced collaborative őltering approach for personalized recommendations[END_REF]. It is based on the assumption that people who share similar preferences in the past would agree also with new preferences in the future. Another interesting point of view is based on the proverb "tell me who your friends are, and I will tell you who you are". As long as these techniques rely on users' correlations, they are also called social-based methods. In brief, these techniques analyze only the users' personal interests (e.g. ratings, clicks) and őnd out users' sharing similar interests. Hence, it recommends items to users that other users in this group have liked in the past. Figure 2.1 illustrates this process: users rate items (e.g. from 1 to 5) which represent their interest in such item. Thus, we aim to predict tastes for the active user (a) in items and extract the more interesting items to him.

There are two main categories of collaborative őltering techniques: similarity-based (a.k.a. memory-based or neighborhood-based) and model-based (a.k.a. latent factor models) [Breese et al., 1998, Su and[START_REF] Su | [END_REF].

TECHNIQUES AND ASSUMPTIONS

ratings and create an optimized mathematical model to predict future users and items ratings. They have gained popularity because they are accurate, they avoid dense data storage and they have easy implementations [Koren andBell, 2011, Konstan and[START_REF] Konstan | [END_REF]. Other interesting model-based technique use neuronal networks [Kim et al., 2004] and Support Vector Machine (SVM) [START_REF] Xia | Support vector machines for collaborative őltering[END_REF].

In general, collaborative őltering have demonstrated their accuracy in exploiting and predicting users' interests. They are considered as "domain independent" techniques [START_REF] Shambour | A hybrid multi-criteria semantic-enhanced collaborative őltering approach for personalized recommendations[END_REF], since no items' description is used, and it represents an advantage in large and multi-domain recommendations (e.g. Amazon e-commerce) because it highly reduces the complexity of the system. However, they sufer from sparsity and cold-start issues.

On the one hand, warm-users have a low number of ratings regarding the whole set of items, what creates a sparse set of data to correlate. On the other hand, new items are not known (rated) yet by users and new users do not have rated items for computing good recommendations. These are the main drawbacks to deal with in collaborative őltering. Some variations focus on how to őnd and group users of similar interests. For instance, one may take a more restrictive őlter into account, such as communities and friend-relationships only [START_REF] Kantor | Recommender systems handbook[END_REF], and perform users' correlation among this subset of users. In case of new users (from whose preferences are still unknown), to know some of the new users' friends may allow to generate recommendations based on the friend's preferences.

As a consequence, it has became popular in social networks as well [START_REF] Arias | Recommender systems for the social web[END_REF].

It is worth to note that model-based techniques overcome similarity-based in accuracy

and scalability [START_REF] Su | [END_REF]Khoshgoftaar, 2009, Koren andBell, 2011]. In fact, the model construction can be distributed to alleviate time consumption, and recommendations can be stored of-line. On the contrary, similarity-based techniques have to deal with similarity and prediction functions which do not scale well in large datasets.

Content-Based (CB)

Content-based techniques assume that the preference of users do not dramatically change over time, and thus, they recommend similar items to the ones that the active 2.2. TECHNIQUES AND ASSUMPTIONS user liked in the past. These techniques analyze the users' ratings and the items' descriptions. The former allows to know which items the user likes/dislikes. The latter allows to describe the item, and thus, to őnd similar items.

As it was explained in similarity-based collaborative őltering techniques, content-based techniques also perform a two-step recommendation process. First, a similarity function allows to identify the closeness of items in the database. The description of items can be very large abstract concepts, such as words in text documents, URLs, keywords, or more domain oriented attributes, such as the movie's genre or the author's book; hence this description is composed of very heterogeneous data [START_REF] Tiroshi | Recommender systems and the social web[END_REF]. One very notorious and used technique is the Term Frequency-Inverse Document Frequency (TF-IDF). This technique looks for common words and their word's derivations and count the occurrences of such terms in order to weight how important are words. The second step uses past user's ratings and items' similarities to predict the interest in other items. In this case, predictions have a single user and they are always item-oriented. Thus, voting systems take into account this user only, e.g. the user's average rating.

Content-based őltering is user-independent because there is no users correlation and it bases its recommendations on items similarities only. In addition, the new item coldstart is easy to solve: new item's similarities can be computed and similar items can be recommended to the adequate users. Furthermore, the items' attributes allow to perform easy explicative recommendations: "this item is suggested because you liked this other item". However, they sufer from overspecialisation (or lack of item diversity): these techniques recommend always very similar items, what may bore users who need more diversity in recommendations. In addition, these techniques sufer from new user cold start, since new users have not declared yet enough interests, and thus recommendations are not personalized or diversity is almost in-existent. Moreover, as seen for similaritybased collaborative őltering, these techniques do not scale well in large datasets due to the high volume of computations.

TECHNIQUES AND ASSUMPTIONS

Other recommendation techniques

Context-Aware

Researchers have pointed out that the contextual variables from the environment, e.g. GPS location or weather, play an important role in recommendations since they inform about the users' situation [START_REF] Bonhard | knowing me, knowing you' -using proőles and social networking to improve recommender systems[END_REF]. For instance in a hotel recommendation, it could be interesting to know if the user is going for business or leasure.

They are divided into pre-őltering, post-őltering and context modeling methods. The őrst approach uses the variables to reduce the number of items to analyze at the input. This helps to reduce the amount of computations and to focus on particularly interesting items. The second method őlters the output of the system using the actual context. As a result, it is possible to adapt some details of the recommendations to users, for instance to delete recipes which contains allergens for the user. Finally, context modeling may include the context variables in the computation of recommendations [START_REF] Kantor | Recommender systems handbook[END_REF], e.g. inside similarity functions, prediction function or complex models. For instance, it is possible to learn not to recommend umbrellas to people visiting Miami in summer.

Pre-őltering and post-őltering techniques are simple to implement because they simply add new layer to the recommender system (at the input or at the output, respectively).

On the contrary, context modeling methods may introduce complexity because of the fact of adding new variables to take into account in the recommendation models.

Demographic

The demographic őltering techniques are either social-based or context-based techniques. This technique uses demographic personal data to compute a recommendation, such as the age or the nationality [Pazzani, 1999, Vozalis and[START_REF] Vozalis | [END_REF]. They assume that recommendations should depend on particular niches, for instance, people of the same age may follow similar movie tendencies. These techniques are similar to contentbased techniques, although they are user-oriented based on users' personal descriptions.

As long as these descriptions are vague and common among the whole community, these techniques lack of precision and are often part of hybrid recommender systems.

TECHNIQUES AND ASSUMPTIONS

Knowledge-based

The knowledge-based systems are either content-based, context-based and/or demographical techniques. These techniques use the whole set of knowledge available in order to analyze the interaction between users and items, i.e. rated items, ratings' values and ratings' patterns [Trewin, 2000]. These techniques use to be linked to reasoning systems that apply association rules and other data mining techniques to generate adequate content to be recommended, as well as to explain recommendations.

The two most important techniques are case-based and constraint-based. The main goal of these techniques is to solve a problem for which the solution is a recommendation.

The problem has a user description (e.g. explicit queries or implicit needs). Case-based techniques use similarity-based functions to adapt current recommendations (cases) to the user [START_REF] Bridge | Casebased recommender systems[END_REF], Zhuo et al., 2011]. The case has a static description. The system looks for the closest cases to a given one that best őt the user's needs. On the contrary, constraint-based deal with constraint satisfaction (users or items constraints) [START_REF] Felfernig | Constraint-based recommender systems: technologies and research issues[END_REF]. They usually apply association rules over the description of items in order to őnd out the set of items which answers to the user's problem. These techniques can be considered complex content-based technique, and they sufer from the same drawbacks as content-based techniques, particularly the overspecialisation issue.

Social Network based

These systems are social-based and they are specially linked to collaborative őltering techniques [START_REF] Kautz | Referral web: combining social networks and collaborative őltering[END_REF], Bernardes et al., 2015]. Collaborative őltering methods assume that users are independent and identically distributed [START_REF] Mcpherson | Birds of a feather: Homophily in social networks[END_REF]. On the contrary, social network techniques assume that social inŕuences are very important in human choices.

The main diference between collaborative őltering and social network based systems is that the latter take into account more heterogeneous data coming from user social interactions. This has a positive impact on the acceptance of recommended items [Zheng et al., 2.2. TECHNIQUES AND ASSUMPTIONS 2008]. For instance, [START_REF] Bonhard | knowing me, knowing you' -using proőles and social networking to improve recommender systems[END_REF]] stated that carefully controlled familiar proőles and ratings similarities help the system in explanatory recommendations and lead the user in better decision makings. Indeed, social network techniques focus on the analysis of inŕuence, deőned as "the power or capacity of people or things in causing an efect in indirect or intangible ways"1 .

For instance, group of life-friends tend to be friends in social networks (e.g. Twitter or Facebook) and tend to comment on the same subjects and follow the same people. In addition, by using these techniques, it is possible to identify the users who have especial inŕuence over the mass. This has especially raised the attention of the sociology and marketing őelds [START_REF] Mcpherson | Birds of a feather: Homophily in social networks[END_REF], since őnding out these people may help in the propagation of publicity and campaigns.

Hybrid methods

The hybrid approaches combine two or more techniques in order to improve the general behavior of the recommender system. It aims to overcome the constraints of one technique with the advantages of the others. For instance, a common hybrid approach is a combination of collaborative őltering and content-based techniques. The former are very accurate and introduce diversity in large number of recommendations, although they sufer from sparsity and cold-start problems. The latter exploit the items' descriptions but they sufer from overspecialisation. As a result, the content-based techniques may use this additional data of items to address cold-start problems and the collaborative őltering introduce some diversity in recommended items.

In [Burke, 2002, Burke, 2007], the author presented 7 diferent hybridization of techniques, that we will brieŕy discuss. This categorization has been also well discussed in [Meyer, 2012]. Some examples of hybrid approaches will be given in the next section. The weighted approach uses "N" recommendation techniques, each of them used under its own assumptions. For instance, to use demographic techniques over users' descriptions and content-based methods over items' descriptions. Then, these techniques separately suggest a set of items to recommend, which can be joint or intersected to create a single recommendation set. The őnal predicted rating of one item in the set is given by a weighted combination of the predicted ratings from the diferent techniques.

The cascade hybridization method allows to sequentially enhance the recommendations given by one technique by using another technique. For instance, it is possible to change the order of top-K recommendations given by collaborative őltering by using content-based approaches. Finally, the meta-level hybridization method provides to a recommendation technique the model generated by a diferent recommendation technique. For instance, content-based models (ratings and predictions) can be analyzed by collaborative őltering techniques.

Recommender Systems in the Academy

This section describes the recommendation techniques and the recommendation issues addressed by academic researches. We particularly focus on the scalability and parallelization of techniques, the sparsity and cold-start challenges and the heterogeneity of data used in their approaches. The őrst recommender system in 1992 (Tapestry [START_REF] Goldberg | Using collaborative őltering to weave an information tapestry[END_REF]) was based

RECOMMENDER SYSTEMS IN THE ACADEMY

of users' neighbors would improve the accuracy of recommendations. [START_REF] Ortega | Improving collaborative őltering-based recommender systems results using pareto dominance[END_REF] propose "Pareto" dominance to perform a pre-őltering process that eliminates less representative users from a K-Nearest Neighbors selection and keep the most similar ones. [START_REF] Xu | An exploration of improving collaborative recommender systems via user-item subgroups[END_REF] highlight that users with similar tastes in some items may have completely diferent tastes in other group of items. To face this issue, they propose to őnd meaningful subgroups by using a multi-clustering techniques over users' ratings and items. This őnds accurate cluster of users. [START_REF] Chatzicharalampous | Exploriometer: Leveraging personality traits for coverage and diversity aware recommendations[END_REF] also realize that users' preferences tend to be distributed among the same group of items. In order to increase the recommendation of other items (coverage) and also have diversity in top-K recommendations, the authors use an user-biased collaborative őltering that favour explorer users in neighborhood memory based techniques.

Other authors agreed with the accuracy of collaborative őltering techniques but focus on more diverse challenges. For instance, [Ben-Shimon, 2013] care about the trade-of between the computation time of the recommendation techniques and the quality of the solution these provide. They propose a memory based collaborative őltering algorithm which can be stopped at anytime. The more the computation time, the better the predictive performance that is achieved. Given suicient time, the solution becomes optimal. [START_REF] Herlocker | Explaining collaborative őltering recommendations[END_REF], Hernando et al., 2013] focus on the explanation in recommendations to increase the acceptance of recommended items. They use visualizations and clustering techniques to identify attractiveness and closest related users.

In addition, it is worth to highlight that merging a set of collaborative őltering can overcome simple collaborative őltering approaches [START_REF] Jahrer | Combining predictions for accurate recommender systems[END_REF], and may co-operate to alleviate each other's particular issues.

Hybrid approaches propose to combine diferent recommendation technique assumptions, such as content-based and collaborative őltering techniques. [Uchyigit, 2009] and [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF] show a state of the art in recommender systems that combine semantic web technologies (usually for content-based recommendations) and collaborative őltering.

They claim that these technologies may help to interconnect items and users information in other diferent levels, such as reasoning and recommendation explanations, and they can alleviate cold-start and sparsity. In fact, this may make easier to integrate heterogeneous data to the system, although it also makes the domain independence and scalability of the system more complex. Many of these techniques sufer from large vector representation of items and/or users which increases the memory consumption.

For instance, [START_REF] Middleton | Ontological user proőling in recommender systems[END_REF] create user proőles that represent users' interest in terms of concepts in ontologies. They use collaborative recommendation algorithms to recommend papers seen by similar people and based on their current topics of interest.

[ [START_REF] Berkovsky | Distributed collaborative őltering with domain specialization[END_REF] explore the content-dependency of items proposed by collaborative őltering techniques. They propose an item's partitioning by topic (e.g. the genre of a movie). They apply one collaborative őltering technique per partition by taking into account only the data from users and items in the partition. Diferently, [START_REF] Tso-Sutter | Tag-aware recommender systems by fusion of collaborative őltering algorithms[END_REF], Zhang et al., 2011] enlarge the topics of items. They claim that items' descriptions can be global (i.e. inherit items' attributes, such as the attribute of a movie), or and/or local (i.e. inherit from one particular user for one particular item, such as tags). Their goal is to incorporate tags to diferent memory based collaborative őltering approaches by creating a "user-tag", "item-tag" and "user-item" matrices. [START_REF] Mabroukeh | Ontology-based web recommendation from tags[END_REF] also exploit the users' tags. They map tags into concepts within one domain ontology.

This allows to map items to concepts and to match users to concepts in order to obtain the relevant items for the users.

More approaches regarding hybrid approaches (mainly content-based and collaborative őltering combinations) and the heterogeneity and representation of data are discussed in Chapter 4 and Chapter 5.

As it was discussed in the previous section, the social network techniques may enhance the performance of recommender systems mainly by improving their accuracy, items acceptance and explanation of recommendations [START_REF] Kautz | Referral web: combining social networks and collaborative őltering[END_REF]. For instance, [START_REF] Aranda | An online social network-based recommendation system[END_REF] use a simple social friendship voting system and matrix factorization: the recommendation score for the active user is the sum of the scores of his friends. This enhances the users' similarity research. [START_REF] Ma | Recommender systems with social regularization[END_REF] propose to extend matrix factorization to take into account users' social regularizations. They modiőed the user-features matrix to introduce "social weights" and make that users latent feature vectors and users' friends latent feature vectors to be closer to each other.

RECOMMENDER SYSTEMS IN THE INDUSTRY

Another trending challenge among researches is the cold start situation, specially sensible in collaborative őltering techniques. [START_REF] Kim | Probabilistic model estimation for collaborative őltering based on items attributes[END_REF] focus on the new item cold start by using association rule in items' preferences and collaborative őltering probabilistic rating distributions among group of users. Items are partitioned into groups and predictions for users are made by considering the Gaussian distribution of user ratings in each group. [START_REF] Sobhanam | Addressing cold start problem in recommender systems using association rules and clustering technique[END_REF] use association rules to create users' proőle and solve new user cold start and clustering techniques to alleviate the new item cold start.

However, current tendencies to cope with cold-start are based on active learning techniques, in which the users can interact with the system and give a few initial ratings to analyze [START_REF] Boutilier | Active collaborative őltering[END_REF]. The cold start and particularly the active learning techniques are more discussed in Chapter 6.

We conclude this section by presenting some contextual recommender systems approaches. They are interesting because they can adapt recommendations to very particular users' situations [START_REF] Adomavicius | Contextaware recommender systems[END_REF]. For instance, [START_REF] Sarwat | Lars*: An eicient and scalable location-aware recommender system[END_REF] deduce that there exist users preferences depending on spatial regions (e.g. a school, a neighborhood, etc.). In addition, they discovered that the need to move into diferent regions looking for special needs is accepted by users. [START_REF] Braunhofer | Parsimonious and adaptive contextual information acquisition in recommender systems[END_REF] propose to identify (or query to users) the contextual factors that could inŕuence users' ratings and recommendations acceptance, e.g., the time or the GPS location. Then, they create a predictive model to predict ratings under various contextual situations.

Recommender Systems in the Industry

This section presents how recommender systems have been adopted by the industry.

We focus on big companies dealing with large amount of users and information. We try to dig into the recommendations that these companies perform. However, this is often diicult due to a lack of public published information, hidden intentions or protected intellectual properties which give competitive edges. In fact recommender systems increase sales (more purchases from catalogues), attract audience (more click on catalogues) and improve users' satisfaction. Thus, the industry cares about the coverage of items and users and the impact of recommendations in the business and the users.

Video Service Providers: Netflix, Youtube and Canal+

Netŕix is probably one of the most important actors in the development of recommender systems. This media service provider has organized from 2006 to 2009 the "Netŕix Price" competition. The goal was to, given a large movie's dataset, enhance performance of recommendations in terms of the RMSE metric (which computes the square diference between the techniques' predicted ratingsin some items and the ratings the users would have given to these items) by at least 10%. This challenge has contributed by proposing many algorithms (e.g. Matrix Factorization) and many hybrid algorithms, which are combinations of diferent techniques.

The current recommender engine uses, among others, a linear combination of two very interesting and important techniques: a Singular Value Decomposition for matrix factorization (SVD++) and a Restricted Boltzmann Machines (RBM). The former is explained in [START_REF] Koren | Advances in collaborative őltering[END_REF]. It is a matrix factorization technique that uses gradient descent techniques to optimize the model research. An extended version was proposed to take into account not only explicit users' feedback (e.g. ratings), but also implicit feedback (e.g. clicks, time spent in items, etc) and other time-oriented users' evolutions. The latter was proposed in [START_REF] Salakhutdinov | Restricted boltzmann machines for collaborative őltering[END_REF]. It is an artiőcial neural network that learns the distribution probability of ratings among the dataset in order to generate predictions.

Google faces a diferent problem in video recommendations. For instance, the big ammount of uploaded videos and their poor metadata (e.g. incomplete or irrelevant titles and descriptions). The recommendation system is presented in [START_REF] Davidson | The youtube video recommendation system[END_REF]. It uses contextual informations as well as item-to-item collaborative őltering techniques, i.e. the users who watched this video also watched these others, for long-period recommendations and association rules for short periods of users' navigation (usually 24 hours).

Canal+ aims to ofer personalized video content to individuals and groups, i.e. families, in services of "video on demand". They face users interest identiőcation problems as well as video-media players identiőcation (smartphones, tablets, computers and TV's).

They developed "Eureka!"2 , a TV programme recommender system of very high content Moreover, it allows to interact with users to enrich its user's preference knowledge.

"Eureka!" captures the devices usages, the diferent users, the preferences in social networks and the meta-data of their TV programmes. They propose to adapt the content for the family as well by using a cluster approach of TV programmes. This allows to group TV programmes into diferent categories and to justify recommendations in much easier way. Under a more technical point of view, we consider that this service consists on a set of algorithms to analyze users' interactions with programmes. Thus, they may use a detailed TV programme description and detailed users' experiences interaction to be exploited by content-based and collaborative őltering techniques.

E-commerce: Amazon and eBay

Amazon e-commerce web site ofers a very heterogeneous catalogue of products. The recommendation engine is based on collaborative őltering techniques and contextual information. [START_REF] Linden | Amazon. com recommendations: Item-to-item collaborative őltering[END_REF] popularized the use of item-to-item collaborative őltering recommendations based on log purchases, e.g. customers who bought this item also bought these others items, which are also used nowadays. Rather than matching the user to similar customers, it matches each of the user's purchased and rated items to similar items, then combines those similar items into a recommendation list. Today, a content-based system is also integrated to reőne recommendations.

Very recently, Amazon realizes that users may purchase items not for personal usage and that many users keep products in to-buy lists. Thus, it is possible to stop certain purchases from inŕuencing users' recommendations. In addition, Amazon take into account the items in the created lists, as well as the new feature of "wishes" lists.

Social Networks: Linkedin, Twitter and Mendeley

Linkedin 3 aims to connect people and industries in order to help users and companies in job őnding and hiring tasks. It ofers several recommendation levels. They propose a "job recommendation", in which the user's proőle helps to őlter and makes appear interesting jobs. On the other hand, the "talent match" helps human resources to őnd out interesting candidates. In addition, they ofer "news/updates recommendations", "companies you may want to follow", "people you may know", and "similar proőles". These recommendations use collaborative őltering based on users' connections and content based techniques to exploit the users' proőles (such as schools, companies, experiences, skills, etc) 4 .

Twitter allows users to post short text messages and pictures. Users can follow other users to be updated about the last posts. The recommendation engine uses users' connections and the short textual information to perform collaborative őltering and content based recommendations [START_REF] Hannon | Recommending twitter users to follow using content and collaborative őltering approaches[END_REF]. It performs a users' proőling using users' own tweets, users' followees and users' followers. The engine is based on an open source search engine called Apache Lucene 5 . Mendeley6 is a free reference manager and academic social network. Their goal is to connect users, put researcher in the correct content context and help to őnd out new publications. The data used comes from Mendeley's libraries, researcher's publications, social network, co-authors network, citations' network, group of researchers and individual proőles. This allows to compute collaborative őltering, content based and social network approach for diferent use cases, as long as collaborative őltering and content hybrid approaches. For instance, őnding similar papers, highlight inter-linked articles, suggesting a group of papers and to őnd a correct journal to publish an article.

Other social networks, such as Facebook7 , use collaborative őltering to recommend new friends, groups, and other social connections.

Music

Other industrial recommender systems

Yelp aims to recommend restaurant to users. They use collaborative őltering to analyze users' ratings and content-based to proőle restaurants12 . They propose a cascade hybrid system that uses a matrix factorization technique and K-Nearest Neighbors, as long as other learning algorithms.

Orange Labs13 has demonstrated also a big interest in recommender systems to enhance their services. In fact, they propose a similar architecture as Yelp. They propose Reperio, a generic recommender system that aims to help users in decision making, comparison, discovery and exploration [Meyer, 2012]. The recommendation engine uses a K-Nearest Neighbours (KNN) approach based on an item oriented collaborative őltering using a modiőed Pearson Correlation similarity measure. A combination of KNN and a fast matrix factorization is used to deal with scalability issues. To cope with cold-start, they propose a hybrid technique to deal with content-based recommendations for small users' proőle (few ratings).

Recommender System's Libraries

Recommender systems have been widely studied in the past few years and have demonstrated their capabilities and accuracy. The academy and industry have both participated in the development of these tools by creating algorithms and proposing new challenges. As a result, there is a great community of researchers and independent users who contribute to make recommender systems more accessible by anyone.

Open source libraries have appeared to create and deőne a recommendation service architecture. Typically, these libraries do not only focus on recommendations, but they ofer data mining, machine learning and data processing paradigms as well. The main goal is to propose libraries to analyze small and very big datasets, by taking into account accuracy and scalability issues.

The most widely known library is Apache Mahout [START_REF] Owen | Mahout in Action[END_REF]. This open source project started in 2010 and it aims to build fast and scalable machine learning applications.

On the one hand, the recommendation engine started in the Taste Project There are some libraries that contribute with some diferent recommendation features.

For instance, CARSKit is the őrst open-source library to implement context-aware recommender systems [START_REF] Zheng | Carskit: A java-based context-aware recommendation engine[END_REF]. EasyRec23 [EasyRec, 2013] is a recommendation engine which is wrapped to websites and makes easier to capture, store and analyze the interaction of users and items in the web pages, i.e. implicit interest.

Other libraries are interesting for prototyping algorithms. RecommenderLab [Hahsler, 2011] provides a set of multidisciplinary functions to easily handle users, items and rating in order to develop and test recommender algorithms. It also implements users' and items' similarity based collaborative őltering as well as a matrix factorization technique based on Singular Value Decomposition [Funk, 2006]. LensKit24 [START_REF] Ekstrand | Lenskit: a modular recommender framework[END_REF] [START_REF] Gantner | Mymedialite: A free recommender system library[END_REF] allows to exploit the item's descriptions as well.

The developer community plays an important role in the development of libraries. This has guaranteed the success of libraries as Apache Mahout. However, the lack of support makes some libraries to stop quickly evolving, such as Carleton27 Vogoo28 [Vogoo, 2013],

Wales [Gashler, 2011], Colő29 [START_REF] Brozovsky | Recommender system for online dating service[END_REF], MyMedia [START_REF] Voß | Mymedia: Dynamic personalization of multimedia[END_REF],

and SVDFeature30 [START_REF] Chen | Svdfeature: A toolkit for feature-based collaborative őltering[END_REF].

Finally, there are some libraries which are now inactive or simply outdated, such as Coő [Lemire, 2003], Duine31 [Instituut/Novay, 2009], or Crab32 [Caraciolo, 2012].

Table 2.2 sums up these engines and their properties. An extended and more detailed comparison of some of these frameworks has been very recently published by [Nguyen, 2015]. In addition, [START_REF] Said | Comparative recommender system evaluation: benchmarking recommendation frameworks[END_REF] show the performances of Mahout, Lenskit and MyMediaLite over several collaborative őltering implementations and metrics. They note that same implementations on diference libraries may result diferent metric values. As a consequence, the choice of which libraries to use become a problem of adaptability to the developer's expertise (e.g. the languages mastered) and the development environment (e.g.

to be easily wrapped to other features, such as architectures to distribute the analysis of data). In this thesis, we have specially used Apache Mahout (as long as Myrrix and Oryx)

for its simplicity, RecommenderLab for its prototyping features and we brieŕy analyzed MLib for its integration into Apache Spark architecture.

Discussions

In 4) the new user cold start for pure collaborative őltering techniques. Our őnal goal is that these contributions help recommender systems to better handle data and better understand users in order to enhance the performance of the system and the accuracy of recommendations.

Chapter 3

Analysis of the Parallelization of Matrix Factorization techniques

This chapter is mainly extracted from the conference paper: "An implementation of a Distributed Stochastic Gradient Descent for Recommender Systems based on Map-Reduce"; Manuel Pozo and Raja Chiky; IWCIM 2015.

Motivation

Recommender systems are based on the interaction between users and items. These interactions are given explicitly (i.e. ratings) and implicitly (i.e. tracking navigational behaviour). These sources of information and the large number of users and items imply that recommender systems have to deal with huge data analysis. As a result, recommendations are computationally expensive. For instance, the video media service provider Netŕix has around 20 millions customers, 80 thousands movies and 5 billions ratings [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. In addition, this kind of dataset is typically sparse because users often only rate some of these items. Thus, recommenders should be accurate to predict users interests, and scalable to alleviate time processing.

In general, the recommendation techniques focus on accuracy challenges. Matrix Factorization (MF) is a recommendation technique particularly interesting because it has demonstrated great accuracy in recommendations and a high scalability to suit very large users/items datasets [Koren, 2009, Koren et al., 2009]. This technique has become the main reference in the state of the art. The two most known matrix factorization based

RELATED WORK

techniques for recommender systems are Alternating Least Squares (ALS) and Distributed Stochastic Gradient Descent (DSDG). We particularly focus on the latter one because it has demonstrated better accuracy [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. However, the distribution of the computation among multiple machines is complex to achieve and the current technique to parallelize the process has a negative impact in the accuracy of the system.

In this chapter we analyze the scalability of matrix factorization. Our contribution proposes a modiőcation of the current distribution of stochastic gradient descent techniques for a Hadoop/MapReduce cluster. Our goal is to render more ŕexible the distribution of these techniques in order to better exploit the capabilities of the cluster and to achieve a high accuracy in recommendations. At the best of our knowledge, this paradigm has not been openly detailed under this context. Thus, we detail the implementation of our approach. The experimentation has been performed using the publicly available MovieLens

Related Work

This state of the art focuses on scalable recommendation techniques. Particularly, collaborative őltering approaches based on matrix factorization technique have demonstrated high scalability and high accuracy predicting recommendations [Koren, 2009]. In brief, this technique relies on collaborative őltering assumptions: users who agreed in past tend to agree in future. Hence, it groups people of similar tastes, and it recommends past liked items from people with the same preferences. On the contrary, it does not exploit the items' and/or users' attributes to enhance recommendations.

RELATED WORK

The matrix factorization technique decomposes a matrix R into two random matrices, P and Q, in such a way that the multiplication of both matrices gives approximately the original one [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. Typically, r u,i denotes known ratings in R, where u stands for a user (row) and i for an item (column). Thus, ratings are obtained by the multiplication of a vector p u from matrix P and a vector q i from matrix Q: r u,i = p u •q t i . By using this technique, known ratings are approximated or unknown ratings are predicted:

ru,i = p u • q t i .
The quality of the model is given by the closeness between approximated ratings ru,i r u,i and real observed ratings r u,i . The goal is to őnd the matrices P and Q that best approximate known ratings in R: the technique looks for the best P and Q that minimize the quadratic error of the diference between real and approximated ratings. The baseline model is then deőned as: min

∑ r u,i ∈R (r u,i -ru,i ) 2 .
As a consequence, the matrix factorization paradigm becomes an optimization problem to solve. The two most known optimization techniques that may őnd out accurate predictions are based on alternating minimization and gradient descent [START_REF] Koren | Advances in collaborative őltering[END_REF]].

Alternating minimization for the matrix factorization

The alternating minimization technique has simple algebraic resolution. It was popularized by the Alternating Least Square (ALS) technique, studied in [START_REF] Schafer | Collaborative őltering recommender systems[END_REF], Zhou et al., 2008, Pilászy et al., 2010, Takács and Tikk, 2012, Jain et al., 2013].

This technique decomposes the problem into two simple optimization problems represented in P and Q. The main idea is that knowing the ratings in R and supposing P or Q őxed, the non őxed matrix can be guessed. By alternating the őxed matrix in order to guess the other one yields in an approximated result for R. Thus, one alternating minimization iteration is completed when P and Q have been guessed/őxed one time. Highlight that this alternating minimization exploits R two times in one iteration: to guess P and to guess Q. New iterations repeat all this process until a maximum number of iterations or a convergence threshold has been achieved.

RELATED WORK

Gradient descent minimization for matrix factorization

The gradient descent optimization technique was popularized as Gradient Descent (GD)

and Stochastic Gradient Descent (SGD) for recommender systems in [Funk, 2006, Takács et al., 2007, Koren, 2008, Koren, 2010, Koren and Bell, 2011]. In other references it is also known as Singular Value Decomposition for recommender systems.

This technique is typically more complex. It decomposes R into two matrices P and Q and add dedicated users/items learning-parameters to study the ratings patterns. This technique iterates over each rating r u,i in R, one by one, looking for a global minimum.

After each rating, the u user's parameters and the i item's parameters are updated by taking the negative gradient of the function into account. These little steps (single rating and consequent update) improve the accuracy of the system towards the global minimum.

One algorithm's iteration is completed when all ratings have been analyzed. One may notice that huge number of ratings may cause slow time performances. To solve this, the stochastic gradient descent suggests a faster convergence optimization: it iterates over a batch of ratings before updating the parameters in matrices. This afects to the quality of the convergence1 , although it has minor efects in very large ratings datasets.

The complexity of the scalability of these techniques relies on the ratings iterations and updating steps. In fact, the iteration over ratings and the followed updates are interdependent because they use and cross users and items parameters. If two ratings sharing similar users or items are computed in parallel, the users/items update step represents a problem. This paradigm is detailed in [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], Makari et al., 2014].

The main idea behind the parallelization of this algorithm is the division of the R matrix into blocks, stratums and iterations. A block is a batch of ratings that should be computed. It is computed by only one processor, and hence, the update of parameters are available within the same processor and there is no dependency problems inside 2 . It is possible to note that there are blocks 3.3. BACKGROUND creation process.

Our contribution aims to tackle this problem by slightly changing the distribution paradigm and to ofer an implementation of a distributed stochastic gradient descent.

Background

This section goes deeper into the stochastic gradient descent technique in order to better understand the troubleshooting in its distribution for scalable recommender systems.

Gradient Descent (GD) for recommender systems is based on the matrix factorization technique. It aims to explain the ratings in a matrix R by using two matrices P and Q.

The baseline predictor is deőned as

ru,i = µ + b u + b i + p u • q t i .
Where µ is the average of the ratings in the matrix R. b u , b i are biases of the user u and the item i respectively and represent a deviation from the average rating value. Finally, p u , q i are the latent space vectors from P and Q matrices. The goal is to minimize the λ-regularized squared error of:

min bu,bi,pu,q i ∑ r u,i ∈R (r u,i -ru,i ) 2 + λ • (b 2 u + b 2 i + ∥p u ∥ 2 + ∥q i ∥ 2 )
The gradient descent optimization analyzes all the ratings one by one by computing the error in the prediction, e u,i = r u,i -ru,i . It updates the current parameters' status after each rating by taking the negative gradient. This process is controlled by a learning-rate parameters called γ. The update phase is given by:

• b u := b u + γ • (e u,i -λ • b u ) • b i := b i + γ • (e u,i -λ • b i ) • p u := p u + γ • (e u,i • p u -λ • q i ) • q i := q i + γ • (e u,i • q i -λ • p u )
The stochastic version proposes to iterate over a batch of ratings before updating the parameters, what allows a faster convergence in very large datasets. However, either simple [ [START_REF] Gemulla | Large-scale matrix factorization with distributed stochastic gradient descent[END_REF], Makari et al., 2014] have demonstrated that it is possible to avoid this dependency by looking for independent ratings, i.e. ratings r u,i that do not share rows (users) and/or columns (items). As a consequence, they have no common parameters; hence, there is no dependency; and thus, they can be computed in parallel. As explained above, the distribution of this technique follows a stratiőcation paradigm. One stratum is composed of blocks. One block is composed of a batch of ratings. Blocks in the same stratum do not share rows (users) and/or columns (items), i.e. one user/item belongs only to one block in a given stratum, and thus one user/item is contained in only one block per stratum. On the one hand, one block is computed in one node, i.e. ratings are in the same machine, and it is possible to safely update parameters. On the other hand, blocks in one stratum do not share users/items and thus can be computed in separated machines, and the updates for future stratum's analysis are possible and the interdependence is avoided.

We highlight that the performance of the distribution depends on the number of independent blocks and the number of nodes to analyze the block. We assume that one node analyzes only one block at a time, and that one node is uni-threaded (not divisible). For instance, one node can be one cluster in a multi-machine environment, or one thread in a multi-threaded single machine. Hence, having b nodes, the goal is to őnd b independent blocks in the matrix to maximize the eiciency of the distribution. For instance, let's represent a matrix R of dimensions n u = 12 users (rows) and n i = 12 items (columns). In this section we őrst formalize the ŕexibility aspect of the distribution, and second we focus on development and implementation details of the approach.

Flexibility and adaptation of blocks to the clusters

Let's n r be the number of rows (users) and n c the number of columns (items). b is the number of nodes, machines or clusters, and thus, the number of possible independent blocks. Our goal is to deőne new n ′ r and n ′ c in such a way that n ′ r %b = 0 and n ′ c %b = 0. In fact, by doing this we set the number of blocks in which the matrix R will be decomposed and the size of these blocks.

The under dimensionality setting deletes rows and/or columns, and thus users/items; hence, ratings and information. Highlight that gradient descent usually performs a random shuling in the matrix R, and thus which users/items are deleted is not controlled. This mode resizes the matrix by deleting dimensions, and thus resized dimension are equal or minor to the real one to accomplish the decomposing condition. This is also used in [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. As a result, the number of rows/columns to use in the resized matrix is given by n

′ r = n r -n r %b and n ′ c = n c -n c %b.
The upper dimensionality setting adds new rows and/or columns, and thus users/tems; however, these new dimensions do not contain ratings. This may possibly create an unbalanced block in every stratum in which the number of ratings is lower. As a result, it may cause extra time consumption due to the fact that the block needs to be sent to the node anyway. However, this time is normally insigniőcant compared to the time-consumption of the algorithm and it does not carry out any loss of ratings and hence any loss of accuracy.

The number of rows/columns to keep in the matrix is given by n

′ r = n r + (b -n r %b) and n ′ c = n c + (b -n c %b).
The ŕexible dimensionality setting is a hybrid between both approaches above. It deletes/adds users and/or columns depending on the number of nodes b. It looks for the

FLEXIBLE DISTRIBUTED STOCHASTIC GRADIENT DESCENT

Algorithm 1 Looking for the closest value which return zero remainder.

1: function ClosestZeroRemainder(dimension, rule) ▷ rule is the number of nodes available.

2:

underResidual = dimension % rule;

3:

upperResidual = rule -dimension % rule; 4:
if underResidual < upperResidual then ▷ Picking up the closest for zero remainder.

DSGD Hadoop/MapReduce implementation

In this section, we present the technical details of our implementation in MapReduce.

Three parameters have to be set: row original matrix dimension n r , column original matrix dimension n c , and the number of nodes b (non divisible threads or clusters). We focus on three parts of our implementation: (1) the block decomposition of the R matrix, (2) the stratum assignment of decomposed blocks, and (3) the execution of these stratums and the end of the algorithm.

Matrix Block Decomposition

The őrst goal is to decompose the R matrix into blocks, in such a way that independent blocks can be found and grouped into stratums. Our approach allows three decomposition modes, which have been explained before. This step takes the chosen mode and applies it.

As a consequence, this step adds/removes rows and/or columns in order to accomplish the decomposition condition and make the rating matrix decomposable in blocks.

Furthermore, solving the decomposing condition makes possible to determine the size the number of nodes. Second, we shrink or enlarge the original matrix R according to these dimensions. Finally, the new dimensions and the number of nodes allow to compute a step size to follow to build blocks in the matrix.

Stratum Assignment

The second step is to őnd out the independent blocks and to assign them to the same stratum. Note that, the number of the stratums is actually the number of nodes b, and thus, up to b blocks are in the same stratum and can be executed in parallel.

We use a straightforward strategy: blocks found are numbered one after the other, which are used as blocks identiőcation and to őnd out blocks inter-dependencies. In fact, the decomposition of the matrix has been done per column step and per row step, in this precise order. This makes identiőcators to increase őrst by column and second by row.

Figure 3.4 exempliőes this explanation.

The stratum assignment takes beneőt of this numbering by implementing a priority list.

FLEXIBLE DISTRIBUTED STOCHASTIC GRADIENT DESCENT

Algorithm 4 Execution of iterations and stratums. P and Q are the users/items features matrices respectively.

1: function RunIterations(P , Q, maxIterations, numberOfStratums) ▷ Note that numberOf Stratums is equal to the number of nodes.

2:

for iteration = 1; iteration ≤ numIterations; iteration + + do The M ap -f unction uses a simple key-value pair as input. The key is a pair of values itself, which represent the entries of the R matrix (row/column identiőcation or user/item identiőcation). The value is the rating encoded in a double variable. This function iterates among ratings and internally updates the users/items parameters, however it does not notify this update. Once all ratings have been analyzed, a clean-map process is computed to prepare the őnal output of the function. The output is composed of a key-value pairs as well. The key is a pair of values representing the user or item identiőcation. The value is a vector which contains the updated user's/item's parameters. This paradigm makes unnecessary to use Combiners or Reduce -f unctions. Finally, the parameters are joint to the original P and Q matrices and updated locally for next stratums.

The end of the algorithm is given by number of iterations to compute. One iteration 3.5. EXPERIMENTATION is őnished when all stratums have been computed. As a consequence, this makes stratums to be computed several times and to enhance the accuracy of recommendations after each iteration.

Experimentation

The experimentation phase uses the publicly available MovieLens 10M dataset 3 . It contains 69878 users, 10667 movies and 10 million ratings. We focus on collaborative őltering techniques only, and thus there is no domain data or external information to aggregate. By using this dataset, we create a matrix of rows (users) and columns (items) that contains the available ratings. The evaluation and comparisons are carried out in terms of accuracy and scalability as follows.

On the one hand, we split the dataset into 90% training set and 10% test set. This split is done randomly by ratings, and thus one user/item can be both in training and test set, although the rating of one user in one item belongs to one of the sets only. In order to evaluate the accuracy of the recommendations, we use Root Mean Square Error (RMSE). This metric computes the square error between the diference of predicted values and real observed values. As a consequence, we use the training set to train and create a recommendation model, and the test set to evaluate the performance of the model. As long as the split of the dataset is random and afects to the creation of predictive models, we split, run and evaluate algorithms 10 times. Then, we take the average value of the RMSE to compare the techniques.

On the other hand, the time-consuming and scalability parameters depend on machines and clusters. We vary the number of nodes in the cluster and see how the recommender systems perform. We use b = 1, 2, 5, 7, 15, which afect the number of machines to use as well as the number of blocks in which we decompose the matrix of ratings. In this analysis we run the experimentation in single node cluster which uses a MacOS 4Go RAM with 2 cores (2.53GHz). This makes mappers in map-reduce to be computed sequentially, thus time-consumption is higher than in a multi-cluster environment.

EXPERIMENTATION

We compare the performance of the three stochastic gradient descent explained in this chapter: under dimensionality (underDSGD), upper dimensionality (upperDSGD), and ŕexible dimensionality (ŕexDSGD). Highlight that underDSGD is the technique in [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF]. All these techniques use similar training parameters obtained by cross-validation: overőtting is λ = 0.025 and learning rate is γ = 0.0075. In addition, the matrix factorization is allowed to run 30 iterations and to create a latent space model of 30 features. Moreover, we ofer a comparison to the alternating minimization technique ALS in Apache Mahout4 , implementation of [START_REF] Schafer | Collaborative őltering recommender systems[END_REF], Zhou et al., 2008]. This probes the superiority of distributed stochastic gradient descent techniques in terms of accuracy and scalability. The technique's settings uses the overőtting λ = 0.025, obtained by crossvalidation. In addition, in this case the technique is also allowed to run 30 iterations and to use 30 latent features.

It is expected that upperDSGD obtains slightly better results in terms of RMSE, since it does not delete data. Yet, underDSGD might get slightly better time performance.

FlexDSGD will show intermediary results in both comparisons. Table 3.1 shows the performance in terms of RMSE and the time achieved in computing one iteration in a single node cluster are presented. Moreover, it shows the number of rows/columns (users/items) that has been added or removed (denoted by "+" or "-", respectively) in order to achieve the divisibility "condition": n u %b = 0 and n i %b = 0.

As it was expected, the stochastic gradient descent techniques perform better than alternating minimization techniques showing better accuracy and faster computations. Highlight that the time show in Table 3.1 when b > 1 correspond to the time of executing b blocks in sequence as long as this experimentation was perform in a single machine. In real multi-clusters environment this time should be exponentially reduced while increasing the number of nodes, until őnding an asymptote. In addition, the upperDSGD and ŕexDSGD approaches slightly overcome the underDSGD in terms of accuracy. Indeed, these two modes deal with more ratings, what allows achieving (tiny 1%) better results. This fact explains as well the little extra time taken in computation. Highlight that less or none rows/columns are deleted. For instance, focus in the case of 15 number of units, which has 3.6. DISCUSSION 15 independent blocks per stratum. In order to achieve this decomposition, underDSGD has deleted 8 rows (users) and 2 columns (items), yielding in a loss of data. In addition, the deletion is not controlled, and thus one may delete very informativeness rows and columns.

Discussion

The current most widely used recommendation technique is matrix factorization because it is scalable and accurate. This technique decomposes the users' ratings in items into two matrices, in such a way that the multiplication of both matrices result (an approximation of) the original one. Finding these two matrices becomes an optimization problem which can be used using alternating least squares and gradient descent techniques.

In addition, the large quantity of users, items and ratings highlight the need of a scalable and distributed technique to analyse and process this data. In this chapter we have analyzed the scalability of alternating least squares and gradient descent techniques for recommender systems. We highlighted that the latter was more complex to distribute although it leaded to slightly more accurate recommendations.

DISCUSSION

The current distribution paradigm for gradient descent does not properly parallelize the algorithm among an existing Hadoop cluster of machines because it may lead to a loss of users, items and ratings. This causes a light loss in accuracy. We have developed a Distributed Stochastic Gradient Descent (DSGD) algorithm based on this technique and this paradigm that solves this issue. This technique also overcomes alternating minimization optimizations of the matrix factorization problem. The experimentation phase uses the public MovieLens dataset. The evaluations show the good performance of the approach in terms of accuracy and scalability.

One important fact for future work is the capability of the SGD to be extended. One may incorporate more heterogeneous data (e.g. implicit feedbacks and timestamps) in order to improve its accuracy. This has proved to increase the accuracy of recommendations in several techniques. In addition, this is a complex challenge in collaborative őltering recommendation techniques. The next chapter (Chapter 4) suggests a solution to incorporate the users' interests in the items' attributes into collaborative őltering approaches, although reducing the impact of the domain dependency in recommendation processes.

Chapter 4

The implicit interest of users in the attributes of items

Motivation

Recommender systems exploit the interest of users in items to recommend other items, unknown by the users, which could be of their interest as well. There are many approaches to retrieve and deduce the users' interest, a.k.a. feedback, although they can be summarized into explicit and implicit. Both of them are item-oriented, i.e. the interest of the user in the item.

The current recommender systems use these feedbacks to generate recommendations.

However, these feedbacks show only the interest of the user in the item (e.g. movie, song, book) and not in the item's attributes (e.g. actor, composer, writer). In addition to this, users are not willing to rate many items, and thus asking for rating items' features is 4.1. MOTIVATION not suitable [START_REF] Elahi | Active learning in collaborative őltering recommender systems[END_REF]. Similarly, the implicit feedback captured from users are typically item-oriented as well [START_REF] Oard | Implicit feedback for recommender systems[END_REF]]. As a consequence, we highlight a lack of knowledge in users' feedback: the interest of users in the attributes of items is hardly captured.

Indeed, items contain many attributes, and moreover they may take several values (such as a comedy genre or a concrete actor). For simplicity, we call "features" all kind of information that may describe items (or users). We claim that the interest of users in items' features may enhance the accuracy of recommendations. We believe that recommendations taking into account the users' interest in the item's features are generally more accepted, as long as the user can easily recognize these liked features. For instance, users preferring a particular actor will better accept a movie recommendation where this actor is playing.

However, őnding out the users' interest in the features of items is challenging. The large amount of features makes explicit feedback in features inappropriate. For instance, users hardly would rate every actor in a movie. In addition, this information is very large and heterogeneous, what may cause a complex integration into recommender systems as long as scalability issues and the increase of the domain dependency of the system.

Our main contribution is the deőnition and application of the implicit interest of users in items' attributes. This information is deduced by the number of times one has been in contact with an item's feature. Consciously or unconsciously. As a consequence, this number of occurrences is obtained by analyzing the existence of this feature among the whole set of past rated items. Thus, the higher number of occurrences the higher implicit interest of the user in the features.

Our goal is three fold: (1) to obtain the users' interest in the items' features implicitly,

(2) to integrate this information into a recommendation process, and (3) to decrease the impact of the domain dependency in the recommendation process. For this purpose, we present a ŕexible and generic recommender system that relies on a collaborative őltering matrix factorization technique and implicit relations in data. We exploit the description of items to discover the implicit interest of the user in the items' features. The framework scores-up recommendations regarding not only the preferences of users in items, but also their implicit preference in the feature of the items. As a result, the most scored items 4.2. RELATED WORK reŕect the users' interest in items and in the features of the items. Indeed, we transform ratings into "semantic values", which better represent the general users' interests. The concept of semantic used here indicates the expansion in the meaning of ratings, rather than the presence of semantic technologies. That is, this semantic concept does not lead to inferences nor reasonings. A similar semantic concept was used in [START_REF] Mobasher | Semantically enhanced collaborative őltering on the web[END_REF].

The experimentations use the well known Movielens and IMDb database, both publicly available. The results show the good performance of our approach compared to a standard matrix factorization approach. In fact, we particularly improve the precision and recall of this technique having little impact on the similarity among the items that are recommended.

This chapter is structured as follows: Section 4.2 presents the related work. Section 4.3 explains our approach. Section 4.4 gives the experimentations and results performed.

Finally, we close this chapter by giving some discussions in Section 4.5.

Related Work

This section focuses on the state of the art of recommender systems dealing with explicit and implicit feedback, as well as the items' descriptions, in order to improve the recommendations. We are interested in which of these sources are exploited and how they afect the recommendation process. Particularly, we evaluate the related work in terms of scalability, heterogeneity and domain dependency of the systems.

Collaborative őltering techniques rely on the explicit or implicit users' interests in items.

The most popular technique, Matrix Factorization (MF), has been very studied in the literature due to its accuracy and scalability. [START_REF] Zhou | Large-scale parallel collaborative őltering for the netŕix prize[END_REF] and [START_REF] Schafer | Collaborative őltering recommender systems[END_REF] are matrix factorization techniques that only use users' ratings or users' implicit feedback (e.g. clicks). Recently, [START_REF] Koren | Advances in collaborative őltering[END_REF] have proposed a method to take into account both explicit and implicit users' interest in items under the same algorithm. Normally, matrix factorization techniques are scalable and some of them are widely implemented. However, despite being accurate, they do not simplify the incorporation of external heterogeneous data. Particularly, these techniques do not exploit the heterogeneous data which may enhance the recommendations (e.g. the features of users/items).

RELATED WORK

Pure content-based techniques make easier to deal with the items' features, although they are not as accurate as collaborative őltering and they have scalability issues. Thus, many authors focus on hybrid techniques. [START_REF] Barjasteh | Cold-start item and user recommendation with decoupled completion and transduction[END_REF] aim to insert to the matrix factorization technique the information given by the similarity between items' descriptions or users' descriptions, i.e. attributes. In fact, matrix factorization decomposes the rating matrix into two matrices: the users-features matrix, "P", and the items-features matrix, "Q". An item (or a user) is then deőned by a vector of features, and hence it is possible to compute items' similarities. The authors propose to decouple this already built matrices ("P", "Q" or both) and make the features inside to evolve. These features change regarding other similarity matrices based on items' descriptions (or users' descriptions) in a phase called "transduction". As a result, this approach integrates external information into matrix factorization. In addition, this approach copes with cold-start: when users' ratings (or items' ratings) are not declared yet, the similarity between users' (or items) based on their description allows to correctly generate recommendations.

[ [START_REF] Adomavicius | New recommendation techniques for multicriteria rating systems[END_REF], Li et al., 2008, Lakiotaki et al., 2008, Mikeli et al., 2013a[START_REF] Mikeli | A multi-criteria recommender system incorporating intensity of preferences[END_REF] explain the concept of "multi-criteria" recommendations. This idea considers the explicit ratings of users as a solution for an equation where the variables are some items' attributes. These attributes are also linked to other explicit ratings, and thus it is possible to generate predictions in term of users' explicit interest in attributes.

This helps to explain the overall rating value given by a user to an item. In addition, they change the concept of rating from an interest value representation to an ordinal representation. Thus, rating values of 5 and 4 stars are equally preferred to 2, etc. However, these approaches assume the existence of explicit ratings for the attributes of items. These ratings are hard to get in real-life since users are not willing to rate many items/attributes [START_REF] Oard | Implicit feedback for recommender systems[END_REF]]. In addition, it is diicult to compute this approach in a distributed way.

[ [START_REF] Liu | Enhancing collaborative őltering by user interest expansion via personalized ranking[END_REF] propose to detail users' interest in items as well. They suggest a threelayer representation, user-interest-item. For a user, an interest is a characteristic (a feature, such as an actor in a movie) that an item must have. For an item, an interest is one of its features. Then, they apply a Latent Dirichlet Allocation (LDA) algorithm based on "topic 4.2. RELATED WORK models" from text domains (see [START_REF] Blei | Latent dirichlet allocation[END_REF]) in order to tackle the similar multiple "theme" problem. Hence, the authors interpret that the text documents are users, the words are items, and the topics are the (latent) interests. This approach extracts hidden users' interests by establishing a correlation matrix graph between items and interests.

Despite its good performance, the complexity is not acceptable for large-scale applications.

[ [START_REF] Ziegler | Taxonomy-driven computation of product recommendations[END_REF]] suggest a recommender system that exploits an item taxonomy to establish a common base in the items' descriptions. By using past users' ratings in items, this technique allows to compute users' similarities even when users do not share any common rated item. The main idea is to interconnect users through the common content of items in order to predict unknown users' ratings. This is an application of the "collaboration via content" paradigm in [Pazzani, 1999]. [START_REF] Weng | Exploiting item taxonomy for solving cold-start problem in recommendation making[END_REF] is a very similar approach to [START_REF] Ziegler | Taxonomy-driven computation of product recommendations[END_REF]] that use items' taxonomies (typically used for content classiőcation) to őnd out the relations between users' preferences in items and the structure of the taxonomy as well. They verify that users who share similar item preferences may also share similar taxonomic preferences. This helps to cope with cold start and to understand the implicit preferences of users. This deőnition is similar to our implicit users' interest with a major diference: rather than interconnecting users ("users' collaboration") through items' description ("content") we interconnect items' descriptions ("items' collaboration") to őnd out the best items for users ("content").

The analysis of the users' interest in the items' attributes is a great challenge due to the lack of explicit users' feedback and the huge amount of attributes and the values these may take. This interest has not been successfully captured in the literature, although it certainly afects to the items that the user will choose in the future.

The main diference of our work to the current state of the art is the deőnition and use of the implicit interest of users in the items' attributes. In addition, we exploit the strengths of matrix factorization by adding an external and scalable layer, which allows to (1) distribute the analysis over the users' interests in the attributes of items, and (2)

reduce the domain dependency of the system by separating the mentioned analysis from the collaborative őltering technique. We transform the input or the output of this technique in order to better adapt the recommendation for users. This reduces the complexity of the 4.3. ARCHITECTURE OF OUR APPROACH system, integrates the new users' interests and improves the recommendations.

Architecture of our approach

The external heterogeneous information of users or items can enhance recommender systems [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF]. The main issue is the impact of this data in the recommendation process. For instance, hybrid recommender systems based on collaborative őltering and content-based introduce more complexity, more domain dependency and decreases the scalability. We aim to achieve three goals to improve recommender systems: a capacity for incorporating heterogeneous information, a high level domain genericity and a scalable system. As a consequence, we aim to enhance the performance and accuracy of recommender systems.

In this work we take advantage of the domain independence and the scalability of matrix factorization. Our goal is to use it together with heterogeneous data, although reducing its impact in the recommendation process. As a consequence, we propose to separate the recommendation algorithm from the usage of the heterogeneous data. We dedicate an external layer, where all the users, items and items' features are analyzed together in order to őnd the implicit relations in data. The main task is to integrate this new data in such a way that standard matrix factorization can deal with. We introduce the concept of "semantic values" or "semantic ratings". Note that the term "semantic" indicates an expansion in the meaning of ratings. In fact, we transform ratings into "semantic values", and thus this new value represents the interests of the users in items and the attributes of the items.

We suggest a three-layer recommender architecture: a pre-analysis layer, a semantic layer and a recommender layer. Figure 4.1 shows our system's architecture. Since the number of attributes and the number of values for the attributes might be huge (e.g. all the actors in movies, or all movies' tags), the pre-analysis module implements a feature selection and a counting algorithm to quickly obtain the implicit interest of users in the selected features. The semantic module uses the information deduced in the previous layer in order to transform the ratings of users: we expand the meaning of ratings by adding the implicit relation in data. Finally, the recommender module contains the recommendation

ARCHITECTURE OF OUR APPROACH

We focus on how the variance of these attributes afect the rating of items. Thus, the variances are indicators (weights) of relevancy over the global dataset. We use them to balance the importance of attributes in the transformation of ratings into semantic values, and thus, in the recommendations.

Counting module

The typical ratings show the interest of users in items. It is important to understand their item rating-reasons in order to better serve the users. However, an item is composed of several attributes and getting feedback for all of them is complicated. Indeed, users are not willing to rate every single attribute of a movie. As a consequence, we suggest to implicitly gather this information using the past rated items. We count the number of occurrences of a given features among all the past rated items for a given user.

Databases or semantic technologies as ontologies describe the items' environment and they can easily return their unique properties. This fact gives free access to navigate through items' features, and thus we can őnd out the implicit interest of users easily.

However, this task is slow for large number of users, items and features, and the number of requests to perform is large. As a consequence, this implicit interest should be computed of-line and stored in order to have it quickly available. In addition, this implicit information tend to be incremental. New rated movies carry out more implicit interest in features.

The counting module aims to őnd out the implicit interest of users in items and to store it in Counting Bloom Filters, which are bit-structures that represent "n"-elements of the same set "S" in a lower space of "m"-bits (see Annexe B.2 and B.3, or the paper [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF] for more details about bloom őlters). This structure evolves from standard bloom őlters by incorporating a separated bit-structure to count the number of repetitions of the same element "n".

The steps of this module are as follows:

1. For each user we create an empty counting bloom őlter;

2. For each rated item by this user, we extract its features (i.e. all possible description of the item given by atributes values and other sources)

ARCHITECTURE OF OUR APPROACH

3. Finally we insert these features in the counting őlter. Thus, the őlter contains all the items' features which have had an interaction with the user. Highlight that each user has his own counting bloom őlter, and these őlters are used by the semantic module in order to improve recommendations.

Semantic module

This module aims to expand the meaning of ratings by incorporating the implicit interest of users in the attributes of items. As said above, an item is composed of several attributes and getting feedbacks for all of them is complicated. The counting bloom őlter of a user contains the implicit interest of the user in the attributes of an item. We aim to exploit this information in order to add a new sense to the user's feedback.

The semantic module transforms the initial rating given by users into a new semantic rating value. Indeed, this new value takes into account not only the user preference in the item but also her/his preference in the attributes of the item. For instance, an item rated as 4 out of 5 may transform its rating value into 4.5. This fact reŕects that this item has several attributes in common with the rest of items rated by the user. As a consequence, this boosts the recommendation of items which contain similar attributes to the ones the user liked in the past. Hence, recommended items are more suitable and acceptable by users because they may recognize relevant features for them.

The transformation of the ratings into "semantic values (sv)" follows the Equation 4.1.

We call it "semantic equation".

sv u,i = r u,i + E[r u, * ] * ⏐ ⏐ ⏐ ∑ F j=1 C j * W j ⏐ ⏐ ⏐ N u (4.1)
Here, r u,i is the real rating for item "i" given by user "u". N u is the total number of items rated by user "u". E[r u, * ] is the average of the ratings given by user "u". F is the number of selected attributes. W j are the weights for these attributes computed by the feature selection module. C j are the number of times that the value of an attribute has appeared for a user, easily retrieved by taking advantage of the computed counting module. Besides, since parameters are pre-calculated, the number of attributes does not 4.3. ARCHITECTURE OF OUR APPROACH have a relevant impact on the execution time of the module. In addition, the process of this equation is easy to parallelize using a Hadoop/Map-Reduce paradigm [START_REF] Dean | Mapreduce: simpliőed data processing on large clusters[END_REF].

Moreover, we use this equation in two diferent levels of the recommendation. On the one hand, we apply it to all the ratings available in the original training dataset, which is the input approach. On the other hand, we apply the semantic equation to the output of the recommender system to modify the recommendations predicted by the standard collaborative őltering algorithm.

Semantic Dataset (input approach)

This approach implements the semantic module at the input of the recommender module. Brieŕy, it transforms the feedback (i.e. ratings) in the training dataset into a semantic feedback, according to Equation 4.1.

For each rating a new "semantic rating" is computed. Hence, a "semantic dataset" is built from the original one. Figure 4.2 shows this approach. The semantic module takes a training dataset, which contains the "original dataset", and generates a new "semantic dataset", which contains the new "semantic ratings". This latter is used to train the recommender module and create a prediction model to exploit. As the incoming dataset has changed, the recommendation module returns diferent items.

Collaborative őltering őnds out patterns in the users' ratings in items to group users with similar preferences. Our approach scores up items depending on their features and the interest of users in these features. This has two main consequences over the predictions given by the system. On the one hand, items are still chosen by seeking patterns in the users' feedback. On the other hand, predicted items suit the users regarding not only the community of users with similar preferences but also the features that these recommended items contain. We involve not only items but also attributes and features. In fact, by increasing the ratings of items in which users are interested (according to their interest in the attributes of items), one helps the recommendation technique to focus on such accuracy and predictions. 4.5 to represent the top-K recommended items for a user (user "1"). The goal is to modify the predicted ratings in the top-K by using the Equation 4.1. We already know that E[r 1, * ] = 2.50, W 1 = 0.4 and W 2 = 0.6. The current value to modify is one of the predicted recommendations, for instance the prediction of movie 10 (r u,i = r 1,10 = 4.5).

ARCHITECTURE OF OUR APPROACH

Now we get the implicit occurrences stored in counting bloom őlter:

• The user 1 has rated the items 1, 2, 3 and 4, and these items contain actors and genres.

• Focus on the item 10 and its genres: comedy. The movies 1, 2 and 4 already rated by user 1 are comedies. . Hence, the occurrences count is C 1 = 3.

• Focus on the item 1 and its actors: actor 3. The actor 3 appears on movie 3. Thus, the occurrences count in this attribute is C 2 = 1.

Putting everything into Equation 4.1, we obtain the new "semantic rating":

sv 1,10 = 4.5 + 2.50 * |3 * 0.4 + 1 * 0.6| 4 = 5.625 (4.4)
Applied to the whole top-K', this process creates a new order in the top-K. These new recommendations are more personalized to the user according to the interest in the attributes of items.

Recommender module

The recommender module contains the recommendation algorithm, which analyzes the ratings or "semantic values" in order to generate recommendations. Our architecture uses a standard matrix factorization approach.

EXPERIMENTATIONS

Experimentations

We suggest to use the GroupLens dataset proposed by [START_REF] Cantador | 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011)[END_REF] We őrst explain the module settings (feature selection, counting and recommender modules) and second we show the context and evaluations of our experimentation.

Module settings

Principle Component Analysis

This step aims to (1) reduce the high number of attributes (if required), and ( 2) compute a weight to represent the relevancy of attributes in the semantic equation.

We use a subset of ratings. We extract the 100 users who have rated the highest number of movies and we obtain 169155 ratings, which represent almost the 19.77% of the total ratings in MovieLens dataset. This module analyzes the relevancy of items' attributes over this data and returns the most representative features. In addition, it returns ceiledweights for these attributes based on their contribution to the feature selection model. Table 4.6 shows the results of the feature selection analysis, as long as the attributes' variance contributions to this analysis. The two main dimensions in which the dataset can be plot are composed mainly of actor, country, director, genre and location, and thus the tags attribute contribute very less. We decided to avoid using this attribute "tags" in our experimentation. The counting bloom őlters are built in of-line in order to speed up the semantic equation. The dataset contains 2113 users and 112881 diferent values for the attributes. Regarding the parameters of the bloom őlter we consider to accept a very low false-positive ratio of 0.01%. In addition, we set the counter parameters to 6 bits, and thus, the maximum number of appearances of a feature for one user is set to 64 times. As a result, the size of one őlter corresponding to one single user is around 1.3 Mb. Hence, for the 2113 users the total size of all őlters is around 2.7 Gb. This space consumption allows to increase the speed of the semantic module.

EXPERIMENTATIONS

Recommendation technique

We use a matrix factorization algorithm in Apache Mahout3 which uses a gradient descent optimization technique to solve the matrix factorization paradigm and to build the recommender core. This algorithm will iterate a maximum of 30 times to őnd out the best 30 latent space dimensions that better explain the ratings. However, the semantic module uses this recommender as a black box, either modifying the input or the output of the recommendation algorithm.

Evaluation

Our baseline is a pure collaborative őltering technique based on matrix factorization.

It is compared to our approaches, which use the same technique as the core of recommendations to predict ratings. Our system analyzes and obtains the users' implicit interest in the items' attributes in a layer separated from the collaborative őltering technique. This 4.4. EXPERIMENTATIONS reduces the domain dependency of the system and enhance collaborative őltering recommendations.

We do not implement any content-based technique to deal with the implicit interest of users in the attributes of items. Indeed, our approaches analyze and obtain this information separately in order to enhance collaborative őltering recommendations. This reduces the domain dependency of the system. Due to this assumption, we do not consider our approach a hybrid method: the core of recommendations remains a pure collaborative őltering technique.

Our system relies on the analysis of the training data. The more users' ratings (higher training datasets), the better one can őnd the implicit interest of users. Therefore, for the evaluation of the systems we use the full MovieLens dataset containing 855598 ratings over 10197 movies. In order to represent diferent training sets (i.e. sparsity levels), we randomly split the dataset into 90%, 80%, 70%, 60% and 50% training sets. The remaining percentage in each level is the test set4 . As a consequence, we can train systems and compare the predictions in the model with the real-observed values in the test set.

We evaluate our approach under four contexts. First we aim to show an outline where recommendations given by our approach are pertinent and likely to be accepted by users.

We develop an example using a user in the dataset. Second, we aim to measure the performance of recommendations using three diferent evaluations: a rating prediction accuracy, a ranking accuracy and a top-K intra-similarity evaluation. Finally, the charts show the results of three approaches: (1) the standard matrix factorization which is denoted as "mf", ( 2) the implementation of the semantic model at the input, denoted as "semantic dataset", where matrix factorization ingests semantic ratings, and ( 3) the implementation of the semantic module at the output of the matrix factorization predictions, denoted as "semantic top-K", where the semantic module transforms predicted ratings.

EXPERIMENTATIONS

Illustrative example

This section aims to give a deployed example of what the recommender systems return.

It visually compares top-K returned items from the diferent approaches. The interest of this outline is to compare the items that diferent recommenders may show to the same user.

The example focuses on the user 6757 due to his large number of ratings. This user has evaluated 119 items with the maximum rating score (ratings equal to 5). We extract 60 out of this 119 from the training set. Our goal is that the recommender system predicts some of these taken movies.

We train the three systems under this context. The matrix factorization creates a model using this training set, the semantic dataset őrst applies the semantic equation to the training set and then creates a model, and the semantic top-K approach modiőes the recommendations returned by the standard matrix factorization. Finally, we ask the systems to retrieve a top-60 items for user 6757. It is expected that in this top appears some of the 60 before extracted items. Table 4.7 shows a shorter top-10 items (over these top-60 movies) and Figure 4.4 shows the movies behind IDs, which visually compares the top-10 movies. The standard matrix factorization returns 2 items (858 and 912) which belong to the extracted items. However, the semantic approaches improve this fact: the semantic dataset returns 4 items (858, 912, 1213 and 1221) and the semantic top-K returns 3 items (858, 912 and 1221). In addition, we notice the appearance of diferent items in the semantic approaches (such as item 3462). Especially, we highlight a new order in items of the semantic top-K (items 912 or 2624). In fact, we have scored up items which contain interesting attributes for the user, and thus, less interesting items regarding attributes get down in the list. These results show our assumptions: by adding the implicit interest of users in items, recommendations are more suitable and acceptable to users, i.e. more items out of the extracted high scored items set are predicted.

EXPERIMENTATIONS

Root Mean Square Error (RMSE)

The RMSE measure evaluates the system in terms of accuracy of the ratings prediction.

It represents the standard deviation in the error of the prediction. This error is the diference between predicted values and real-observed values in the test set. Thus, the lower is this error, the better is this metric.

The semantic module scores up items due to the presence of attributes, yet it does not penalize the absence of them or it does not penalize the presence of non desirable attributes.

Thus, the semantic rating is always higher than the explicit ratings. This yield indeed to a change of rating's scale. As a result, our framework does not overcome this measure. In fact, our techniques are not adapted to outperform individual rating predictions due to the rating's transformation. Future work consists on improving this metric as well. In fact, the semantic module only scores up items regarding the positive interest of users in the attributes of items, although it does not score down items regarding a negative interest.

This fact, together with a normalization within a ratings scale may improve this measure.

This perspective is explained in Chapter 7.

Precision, Recall and F-Measure

Precision and Recall techniques measure the relevancy of items in a previously selected top-K. This relevancy is a binary value associated to the item: an item is relevant if the rating/prediction overpass a certain predeőned threshold, i.e. to be greater or equal to 4-5.

Precision represents the percentage of relevant items (items that should be recommended őrst) over the recommended top-K items. Recall represents the percentage of relevant items over the whole set of items. Figures 4.5 show the results in precision and recall measures of a top-20 recommended items. Note that results are the average for all users top-20 precision and recall.

On the one hand, the precision is high in matrix factorization due to the good RMSE.

It easily puts relevant items in the top-K. However, the semantic top-K approach slightly overcomes this precision, since it scores-up items and thus other relevant items are likely to appear (making less relevant items disappear from the top). On the other hand, our 4.5. DISCUSSION the users have an implicit interest in their features, we help the collaborative őltering to focus on such kind of items and interests.

The latter aims to apply the semantic layer in the output of the system. Typically, recommender systems provide top-K items ordered by predicted user's preference. This approach better adapts top-K to users' especial interests in items' attributes.

The experimentation uses MovieLens dataset and IMDb database. The results show the performance of the approach over diferent measures. Specially, our approaches enhance the fact of taking relevant items for users. Thus, users might be more likely to click on recommendations because they may contain features they know and they are interested in.

Finally, in this chapter we have proposed to use the implicit interest of users in the items' attributes to enhance the accuracy of rank-based recommendations. The scalability issue has been addressed as well, the presented approach can be parallelized among multiple machines and the distribution of the recommender core has been explained in Chapter 3.

In addition, this chapter has allowed to deőne users through a large quantity of interests and represent it into a bloom őlter. The next chapter (Chapter 5) focuses and exploits the bloom őlter representation of items and/or users to reduce memory consumption in large items'/users' descriptions.

Chapter 5

Coping with large vector representations of users and items in very large datasets.

Motivation

The recommender systems exploit the users' feedback in items to predict future users' interests. In addition, content-based or hybrid methods, use the items' and/or users' attributes, a.k.a. features, to enhance the correlation among items/users. These features can be very heterogeneous. For instance, in the domain of movies one őlm (considered as an item) can be described by its genre (e.g. romantic drama comedy), by the actors who play in (main actors, secondary actors), and by the directors and staf who participated in the project. Furthermore new tendencies add data from contextual and external sources, such as locations, open data, Wikipedia, Twitter and Facebook, in order to better describe items/users [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF], Kantor et al., 2011, Dahimene et al., 2014]. However, this could create very large heterogeneous descriptions and render computations more diicult to handle.

MOTIVATION

The most known recommendation techniques are collaborative őltering, content-based and hybrid methods [START_REF] Kantor | Recommender systems handbook[END_REF]. Especially content-based and hybrid recommendation techniques deal with the above mentioned challenge. They typically represent items/users as a vector of features or keywords, and thus, vector similarity methods can be computed [START_REF] Kantor | Recommender systems handbook[END_REF]. The accuracy of the similarity between items/users will depend on the selected features to compare and will afect the recommendation. For example, comparing two movies only by their genre, such as comedy and drama, is less accurate than involving also their actors in the similarity process.

Indeed, the number of features to describe items/users afects the correlation of data.

Generally the more attributes are used the better the accuracy of the similarity is. For example, two movies may share staf, genre and main actors, although they do not have common secondary actors. In a recommender context it may happen that one user is especially sensible to a particular actor, what has an efect (positive or negative) in the user's interest. This sort of particularities are skipped in recommender systems due to the short items/users descriptions.

On the contrary, one may notice that large resources contribute to large item/user descriptions, thus making the representation diicult to deal with in terms of sparsity and space-consumption. In fact, new features may not appear in other items, for instance, a new actor that has played only in one movie, and increasing the number of features increases the size of vectors that will eventually become larger and more sparse. Furthermore, increasing vector sizes makes similarity computations slower.

Current data analysis systems (e.g. expert systems and feature selection models) reduce data representation into a lower space in order to reduce both the sparsity and space complexity. However, reducing features may yield to a loss of quality in the item representation, and consequently, in items similarity. Besides, the enormous size of the datasets involves big memory resources and a very large time analysis while building these models.

In this chapter we deal with the representation of items/users. Our goal is to represent items/users by a high quantity of features in order to have a great detailed description.

This makes the similarity process in recommender systems more accurate. In order to cope with this big representation, sparsity and space-consumption issues, we propose to

MOTIVATION use a compressed yet high quality data representation for items/users based on Bloom

Filters [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. A Bloom Filter (BF) is a bit structure that allows to represent a set of elements in very low space. To the best of our knowledge, these őlters have not been used for items/users descriptions in the őeld of recommender systems.

The motivation and the three following contributions are applied to a recommendation process:

1. Bloom őlters highly reduce the size of item representations while having a great number of features. This fact involves a detailed items/users descriptions in a lower space complexity;

2. Bloom őlters allow a fast bitwise AND operation to compare common features of items that we use to compute an accurate similarity measure;

3. Items' and users' similarities are not only in common features, but also in common missing features. To address this issue, a bitwise XNOR similarity operation is proposed and takes into account both common features, and common missing features.

In our experimentations we use the MovieLens dataset and IMDb database, which are publicly available [START_REF] Cantador | 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011)[END_REF]. The tests have been performed for: (1)

analysing the pertinence of bloom őlters in recommender systems, [START_REF]2 Recommender System Libraries[END_REF] enhancing the usage of a bitwise AND similarity instead of the common vector cosine/jaccard similarities and (3) using a bitwise XNOR similarity. We compare our bloom őlter item representation against two models: a vector similarity model that uses all available features and a dimension reduction technique based on Singular Value Decomposition (SVD). The results show that our approach highly reduces the size of vector representations (97% per vector) while keeping a high ődelity in item similarity (accuracy of 98%). In addition, it outperforms the results of SVD.

The structure of this chapter is as follows: Section 5.2 gives the related work in similarity processes and the representation of items/users applied to recommender systems.

In Section 5.3, the proposed similarity model based on bloom őlter representations is explained in details. In Section 5.4, the experimentation phase and the achieved results are

RELATED WORK

presented. Finally, we discuss the researches in this chapter in Section 5.5.

Related Work

This related work focuses on researches especially using a similarity computation process in recommender systems. Particularly, we focus on the representation of items/users in these systems, the resources which they aim to exploit and how they deal with description complexity.

On the one hand, similarity-based collaborative őltering methods represent items/users as a vector of feedbacks, as stated in [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative őltering[END_REF], Sarwar et al., 2001, Lemire and Maclachlan, 2005, Su and Khoshgoftaar, 2009]. Then in order to őnd out similar items/users, correlations and similarities among these vectors are performed. The modelbased collaborative őltering techniques make this vector representation obsolete [Hofmann, 2003, Su and Khoshgoftaar, 2009, Koren, 2009, Koren et al., 2009, Koren and Bell, 2011].

The already explained matrix factorization family belongs to this group. These methods build a model which represent the items and users feedback in a lower space rank.

However, typical model based techniques solely rely on the interest of users in items. Particularly, they do not exploit other resources such as the domain of recommendation (e.g. movie's domain) or the general context of the recommendation (e.g. localization, users' afordability).

In general, collaborative őltering has already demonstrated simplicity and better accuracy than content-based, although hybrid methods may enhance these techniques by incorporating heterogeneous data. In content-based techniques, items are represented by a vector of keywords/features [START_REF] Tiroshi | Recommender systems and the social web[END_REF]. Hybrid methods may combine both techniques to get stronger performance. Consequently, they also exploit the features of items/users and may use a vector to represent them.

The similarity process in recommender system helps to group and classify items and users. [Boim et al., 2011a[START_REF] Boim | Diversiőcation and reőnement in collaborative őltering recommender[END_REF] propose a framework to control the similarity (versus diversity) factor in a top-K recommended items. They create "trees of interests" that allow creating a "zoom-in" technique to see more items of the same tree, which tend 5.2. RELATED WORK to be similar. Thus, the better is this similarity accuracy the better is possible to group similar items. [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF] present other tendencies in recommendations that use semantic technologies, like ontologies, to better describe users and items [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF].

For instance, [START_REF] Fernández | Avatar: An improved solution for personalized tv based on semantic inference[END_REF] and [START_REF] Pan | The development of an ontology-based adaptive personalized recommender system[END_REF] propose a hybrid method to describe users and items through ontologies structures in order to compute an inference similarity. Again, the better is the ontology description the better is the inference extracted.

Other authors propose to incorporate more heterogeneous data from external resources.

[ [START_REF] Katz | Using wikipedia to boost collaborative őltering techniques[END_REF] use item-item similarity based on the context in Wikipedia pages to compute "artiőcial ratings" for an item. [START_REF] Werner | Ontology-based recommender system of economic articles[END_REF] characterize economic articles using attributes as keywords. Then, they compute articles cosine vector similarity regarding their keywords. Finally, articles that match better with a user proőle are recommended.

The description of items can be very large and sparse due to the numerous and diverse resources, e.g. movies genre, actors, directors, writer, locations and social network tags. To deal with such quantity of features, some authors propose to perform a features selection which can be supported by domain experts or by using explanatory analysis, such as topic modelling, Singular Value Decomposition (SVD) or Principle Component Analysis (PCA).

For instance, [START_REF] Vozalis | Using svd and demographic data for the enhancement of generalized collaborative őltering[END_REF] propose to add demographical and context information to the recommendation. They create users and/or items demographic vectors in order to represent information. If the dimension of these vectors is too high, they reduce it by applying the SVD technique. A cosine similarity method is later used to compute user and item similarities. [START_REF] Mobasher | Semantically enhanced collaborative őltering on the web[END_REF] suggest a hybrid recommendation technique based on content-based item-similarities and an item-based collaborative őltering technique. This similarity uses semantic sources to exploit the attributes of items. They create an item-attribute matrix, but it may be too noisy and attributes may be correlated.

Thus, the authors reduce it by using SVD and compute items similarities.

One may observe that most similarity processes do not take all possible or available attributes information into account. The item similarity measure might sufer from a loss of accuracy since less features have been taken into consideration for this comparison.

Although larger number of features may improve similarity, the computation might become more expensive. In addition, approaches dealing with space reduction or latent space 5.3. BLOOM FILTER SIMILARITY MODEL models may lose information.

We propose to use a representation of items/users based on bloom őlters. This reduces the size of vector representations and compute accurate and faster similarities. [Bloom, 1970] introduced the concept of bloom őlter and many research őelds and applications have taken beneőt of this structure due to its memory-eiciency and fast-capabilities [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF], for instance databases queries or computer networks. Recently, [START_REF] Geravand | An eicient and scalable plagiarism checking system using bloom őlters[END_REF]] applied these őlters to create a fast, accurate and private plagiarism system that compares the similarity among documents of diferent databases.

[ [START_REF] Jain | Using bloom őlters to reőne web search results[END_REF] used them for web search őeld. Typically web browsers return to users' request top websites which tend to be very similar. The authors propose to group similar websites results in order to allow the return of other diverse sites in the top results.

To the best of our knowledge, the only reference of bloom őlters in recommender systems is in [START_REF] Pagare | Recommendation system using bloom őlter in mapreduce[END_REF], where the authors apply this structure to improve a parallelization MapReduce paradigm rather than to enhance any part in a recommendation process. Hence, this structure has not been used yet in the core őeld of recommender systems.

Bloom Filter Similarity Model

The Bloom Filter Similarity Model, a.k.a. Bloom Model, aims to alleviate the aforementioned issues. This approach relies on bloom őlter representations of items/users. By exploiting bloom őlter's properties, it is possible to compute similarity measures to know the similarity among two őlters, and thus, among the items/users theirselves.

In this chapter, we consider that the reader is already familiar with bloom őlters, and particularly, with the mathematical and probabilistic properties behind (i.e. near optimal false positive, intersection and union). However, Annexe B explains the concept of bloom őlters. Table 5.1 resumes the notation we use in this chapter. In addition, comparisons and references to the simple vector similarity model are also given.

In order to deőne the context our bloom őlter similarity model, let S N be the set of all possible items features in a database used in a similarity comparison, so that the number of features in this set. Moreover, let S i be the set of active features of an item "i", and |S i | = n the number of features in this set. As a consequence, S i ⊂ S N . In addition, within this context we assume that n ≪ N .

|S N | = N is 5.3. BLOOM FILTER SIMILARITY MODEL
For instance, "N " can be the total number of actors, directors, editors and tags in a movie database. However, a single movie only has "n" of these features, a.k.a. active features. Normally increasing the features in the database has more impact over "N " than over "n". Indeed, incorporating external information increases the value of N , but only few items will increase their active entries "n" signiőcantly. Thus, vector representations are larger and sparser.

Under this context and deőnitions, the state of the art proposes (1) to represent items/users as vector of attributes/keywords/values, and (2) to reduce the size of vectors by using some feature selection criterion. However, this may lead into large vectors or a loss of description accuracy. We suggest the bloom őlters to represent items/users as a set of features. Indeed, these structures are low-size hashed binary vectors representing a huge set of elements. Therefore, we represent one item by one bloom filter which contain all the "n" active features for this item. Thus, the number of expected insertions is equal to the number of active features for one item only, and items can be compared by using their associated őlters to compute items' similarities. Figure 5.1 represents the diference between the vector similarity model and the bloom model.

Our goal is to analyse the impact of diferent bloom őlter settings in an item similarity process. We őrst detail the necessary conditions for creating a bloom model. Second, two similarity measures are presented: AND bitwise and XNOR bitwise operations. We conclude this section by presenting the consideration of the similarity measures in rec-

BLOOM FILTER SIMILARITY MODEL

insertion of an element, and (2) the maximum false positive f p max is given by the maximum insertions n.

However, the items do not have the same expected number of active features. As long as m and k have to be equal for every őlter, the predeőned number of insertions should be őxed as well to achieve the maximum desired false positive f p max in the bloom model.

As the false positive increases with new insertions, it is necessary to look for the item which contains the maximum number of active features n max . The őlters having the largest number of active features will achieve larger false positive, yet the upper bound false positive is limited to f p max . According to this discussion, we establish the necessary condition to use a bloom őlter model when every őlter is built using the same n max , m and k.

In the following sections, we discuss the similarity measures of the bloom model and how this new condition afects to the false positive of these operations, a.k.a. false positive similarity.

Bitwise AND Similarity

The intersection of two bloom őlters performs a bitwise AND operation between two őlters (Annexe B.2.2) to őnd out common insertions in both bloom filters. Intuitively, one element which is inserted into two diferent bloom őlters will activate the same bits positions in both structures. Figure 5.2 gives an example to represent this fact. As long as one őlter represents the active features of one item, the intersection of two bloom őlters represents the common active features of two items. Thus, we deőne a bitwise AND similarity as:

Definition 1 The AND similarity between two items, A and B, represented by two bloom filters, BF A = ⃗ a and BF B = ⃗ b, is given by:

sim(A, B) = card(⃗ a ∩ ⃗ b) = ⃗ a • ⃗ b
The low size of őlters (regarding real vector representations) and the fast bitwise operations allow to rapidly compare the similarity of two very large item descriptions. This

BLOOM FILTER SIMILARITY MODEL

Thus, we deőne the false positive similarity as the maximum error in the similarity in Equation 5.3, which is the combination of all possible bit states using k hash functions.

Note that this error highly depends on k, due to the bit-to-bit comparisons.

f p = q(bit = 1) k = ( 1 -(1 - 1 m ) k•nmax ) k (5.3)

Negating a Bloom Filter

Negating a bloom őlter will help us to perform and explain the XNOR similarity measure. Theoretically, the negation of a őlter BF A (BF A ) results in another őlter where entries take their complementary value of BF A . Thus BF A might only contain the noninserted elements of BF A .

However, due to the k hash functions, insertions may share at most k-bits in the őlter BF A . Therefore, negating a bloom őlter has two consequences: (1) inserted elements will appear as non-inserted elements, and ( 2) non-inserted elements may appear as inserted elements only if all their k indexes are set to 0. Otherwise, non-inserted elements also appear as non-inserted in the negated őlter. This fact is represented in Figure 5.3. However, this problem might be minimized by reducing the number of shared bits per element (m/kn).

In addition, since the number of bits set to 1 has changed, the false positive of A also changes, and it is given by the probability that a specific bit is zero in the original filter :

f p = p(bit = 0) k (Equation B.1 in Annexe B.2.2).

Bitwise XNOR Similarity

Common similarity methods measure the intersection of elements to őnd out mutual similarities. The AND intersection takes common-inserted elements of two sets into account. That is, given two sets, S A = {x1, x3} and S B = {x2, x3}, the intersection of both sets is S A ∩ S B = {x3}. However, sets S A and S B have more in common than this intersection. Actually, the element x4 is not in any of these sets, and hence, x4 is a common non-inserted element.

As a consequence, we propose to go further in the similarity by considering also the com-123 5.3. BLOOM FILTER SIMILARITY MODEL ity could be potentially inőnite. However, it does not mean they are as similar as an orange and a mandarin can be, and indeed they also have inőnitely uncommon features. Thus, a dataset containing rock, paper, orange and mandarin may represent a problem for this measure. Yet, this fact does not happen when the domain of recommendation is őxed and the features to use are deőned. In case of multiple recommendation domains, a semantic analysis can be performed in order to limit the features.

Again, we deőne the false positive similarity as the maximum error in the similarity.

For simplicity, let's consider the complementary probability P (XOR) = 1 -P (XN OR)

(fact shown in Figure 5.5):

P (XOR) = P (BF A ) + P (BF B ) -P (BF A ∩ BF B )
Where P (BF A ) and P (BF B ) are the already known probabilities that a specific bit is still one, q(bit = 1) = 1 -p(bit = 0) in őlters BF A and BF B (explained in Annexe B.2.1.

Moreover, P (BF A ∩ BF B ) is the probability that a specific bit is set to one in both őlters, explained in last Equation 5.1. Taking into account the bloom model condition n = n max , one may apply that q(bit = 1) = P (A) = P (B) = P (A ∩ B). Hence, the probability that a specific bit is set to one in the őnal resulted vector in the XOR operation is P (XOR) = q(bit = 1). As a result, the probability that a specific bit is set to one in the XNOR operation is:

P (XN OR) = 1 -q(bit = 1) = ( 1 - 1 m ) k•nmax (5.4)
Thus, the false positive similarity is given by P (XN OR) k . Operations between identical őlters are a singular case. Since all possible elements are represented, this operation results in a totally full vector of 1 being the highest similarity. Hence, membership queries return always true.

Similarity measures and recommender systems

The bloom similarity model does assist the system to deal with high number of items/users features in order to have detailed items/users descriptions. These descriptions are stored 5.3. BLOOM FILTER SIMILARITY MODEL in bloom őlters, what allows to reduce the size of descriptions and to perform fast bitwise oriented similarities. The impact on recommender systems are, on the one hand, a lower space complexity and faster similarity operations, and on the other hand, an accurate similarity ődelity. The space complexity and bitwise operations have been already addressed in this section. We would like to develop the second concept of similarity ődelity and how this afects to recommender systems.

Imagine that a recommender system has access to a large number of features to deőne items and users. The vector representation becomes very large and a feature selection may cause a loss of accuracy in these descriptions. The bloom model allows to make items and users comparisons in very detailed contexts.

On the one hand, the AND similarity measures is fast and accurate enough while comparing very large number of features. Having three items item 1 , item 2 and item 3 , one can detect that item 1 is more similar to item 3 than to item 2 due to very precise details, such as an ingredient which is in two similar recipes. On the other hand, the XNOR similarity shows comparisons from a diferent point of view. In this case, one can detect again very particular details that make items similar or diferent. Another example in this situation is to take into account the similarity about the aspects said in one item/user but not mentioned in others. For example, having three users user 1 , user 2 and user 3 , one can detect that all users liked drama-comedy movies. However, we know user 1 and user 2 also like sports, whereas this aspect was never captured for user 3 . In fact, user 3 simply does not like sports and thus interaction with these kind of subjects were never taken. As a consequence, it may be likely that a sport-comedy movie is present to user 1 and user 2 but not to user 3 .

We conclude highlighting that these similarities allow to better adapt recommendation to users, since users may be (positively or negatively) aware and sensible to these little details. In this chapter we analyse the accuracy of these similarities regarding other similarities. Other studies to see the impact in real recommendation contexts are part of future work.

BLOOM FILTER SIMILARITY MODEL

Bloom Model Settings and Trade-Offs

The bloom model clearly depends on the parameters of bloom őlters as long as our similarity model relies on the deőned AND and OR bitwise operations. It is necessary to analyse the impact of these parameters over the deőned bloom similarities. Particularly, we are interested in how these parameters afect the false positive of őlters, which is directly related to the false positive similarity between őlters, as it has been theoretically demonstrated.

The size m of a bloom őlter deőnes the size of the bit structure, which afects the false positive probability. Larger őlter sizes reduce the probability of taking a speciőc bit (1/m).

Therefore, the false positive is reduced as long as the probability of setting the same bit position is reduced as well. Furthermore, the number of hash functions k has also a great impact on the false positive probability. Higher values may reduce rapidly the false positive, but they will quickly őll up the bloom őlter. In addition, the hash functions particularly afect a bit-to-bit similarity. In fact, the number of shared bits per insertion (m/kn) should be reduced. As long as insertions are associated to k-bits in the bloom őlter, higher values in a őxed őlter size makes it easier for elements to share some bits positions. Thus, it makes easier to compare a wrong bit state, and hence a true similarity match is more complicated to őnd.

This m and k trade-of can be seen as a space-time trade-of. Space is represented by the size of the őlter. On the contrary, k is the number of hash functions to execute, and hence, higher values entail more time-consumption. Thus, correctly choosing these parameters is crucial in order to have a good performance in a bloom similarity model.

However, the choices depend on the requirements of the application and the size of datasets.

In the experimentation phase we compare the performance of diferent bloom őlter and bloom model settings. However, we may conclude that, as long as bit-to-bit operations can be easily compromised by large values of k, we suggested to use larger őlters with fewer hash functions to improve similarity matchings.

EXPERIMENTATION

is formed by one or more bloom őlters. Thus, these őlters are built by blocks, and hence by adding new blocks to the őlter one may add a new set of features. As a consequence, this avoid to re-build the bloom model when new features are added. In addition, similar probability inductions given in this section can be applied to scalable and dynamic probabilities, and thus our bloom model remains possible in these cases. On the other hand, counting insertions is possible as well by using counting bloom őlters [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. These őlters contains new bit-sets to count the insertions performed.

Thus, if one insertion has been made several times, őlters may approximate the counting.

As a result, one may compare counting őlters to frequency vectors, with more complexity.

Other variances of bloom őlters deal with extra compression [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. These are also interesting őlters that can be used for computing items similarity.

In this chapter we consider using standard bloom őlters due to the nature of our dataset and experimentations, in order to have an easy comparable dataset and reproducible experimentations. This may be complicated in other dynamic circumstances, e.g. bloom őlters in very large datasets using multiple resources, where non public datasets are accessible.

Experimentation

The experimentations use the dataset given by GroupLens [START_REF] Cantador | 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011)[END_REF] in the domain of movies, which is a merge of the very well known MovieLens and IMDb datasets in the recommendation research őeld. The dataset is composed of 2113 users, 10197 items, 855598 ratings, 6 features and 104957 possible diferent values, which are all the available features used to describe our items. In this experimentation we only focus on similarity tasks and we do not take into account users.

Our goal is to compare the performance of the bloom model against two other models namely: a vector model1 using jaccard/cosine similarities and an order reduction model.

The former uses a binary/boolean representation of an item. It takes into account all available features. The latter tries to reduce the size of features by performing a SVD analysis. This experimentation compares four aspects of these models: (1) size, compres- This section goes through two kinds of tests. On the one hand, we aim to prove that the őlter similarities in bloom model are close to the ones computed by vector similarities (using cosine or jaccard measures) in the vector model. On the other hand, we evaluate the pertinence of bloom őlters in recommender systems by comparing the accuracy of several top-K similarities (5,10,20,50,100,150,200,300 and 500 most similar items to a given one). Notice that a simple top 20 or top 50 is enough in most of recommendation contexts. Then, we compare if our approach reproduces such top-K under the same contexts (similar items and similar features).

The results show that the bloom model reduces the size of vectors up to 97%, keeping a similarity accuracy of 98%. In addition, bloom model outperforms feature reduction methods in terms of similarity ődelity and time performance.

Bloom Filter Representation

This section shows the advantages of using our approach in terms of compression, timeconsumption and accuracy.

Trade-Off: Compression and Time Analysis

The size of vectors in a vector representation model is given by the total number of features in the database, N = 104957. However, the number of active entries in these big vectors is very reduced. The item 3246 has the maximum number of active entries over all items, n = n max = 237 (notice that n max << N ). This shows the maximum information of items in a vector and the worst bloom őlter case as well.

As a consequence, to validate the usage of bloom őlters against the vector representation model one needs to obtain more reduced őlter sizes (m < N ) and still be able to compute accurate items similarities (low false positive similarities f p). Several conőgurations are presented in order to compare and őnd out the best trade-of:

(1) Optimal bloom őlters in Table 5.2 computes őlter parameters by using the near 5.4. EXPERIMENTATION optimal false positive value. Indeed, we őx the maximum insertions n max and the desired false positive f p to őnd the best size m and number of hash functions k. Notice that in the case of using a false positive of 0.001 we obtained 3408 bits, which represents almost 3% of N , thus around 97% of size reduction. This tiny false positive and reduced space is given by the 10 hash functions. On the contrary, this high value may afect our AND or XNOR similarities. In addition, the more hash functions to perform, the slower the system is to build őlters.

(2) Non-Optimal bloom őlters in Table 5.3 are built by őxing insertions (n), őlter size (m) and number of hash functions (k) in order to seek the desired false positive. We vary m and k based on the last optimal computed bloom őlter (m = 3408 and k = 10) to őnd a good balance in terms of size and number of hash functions for the bit-to-bit operations goal. Notice that for the same false positive 0.001, we obtained a size of 7000 bits, which represents almost 6% of N by only using 3 hash functions. This setting is a priori the most interesting for our comparison purposes Table 5.4 shows interesting comparisons in terms of space and time-consumption. The machine used is a MacOS 4Go RAM with 2 cores (2.53GHz). Three models are compared: Vector Model (VM), Optimal Bloom Model (OPM) and Non-Optimal Bloom Model (NOPM). To build vectors and őlters, a database access was required. Query time was around 200 ms (not included in these results). One may observe that building bloom model takes extra time due to the hash functions, however, this is acceptable as there is a high space reduction. In addition, operations among bloom models can perform faster due to two facts: (1) bitwise operation are faster than jaccard/cosine similarities, and (2) bitsets are smaller.

Moreover, it might be interesting to reconstruct a vector from a bloom őlter to compare 5.4. EXPERIMENTATION This is also shown in Table 5.4.

Singular Value Decomposition (SVD) model

As explained in Chapter 4, the SVD is a dimension reduction technique. Indeed, it is a factorization model that decomposes a big matrix in three smaller matrices (lefteigenvectors, eigenvalues and right eigenvectors) in such a way that the multiplication of the three is an approximation of the original matrix. The eigenvalues shows which are the principal axes to consider, and thus the rank of the matrix may be reduced.

In the őeld of recommender systems this model helps to focus on particular attributes and features to represent items/users instead of using large and sparse representations.

The main goal is to focus only on the important axes of the model which well represents items/users. However, this model losses some precision while neglecting features in order to gain in space. We applied SVD to the set of items-features (a matrix of 10197 items and 104957 features) to őnd an accurate reduced matrix representation and to compare its size and similarity ődelity against the vector representation model and our bloom model.

The threshold we impose to SVD is the number of eigenvalues and eigenvectors to seek. We only consider the bit-size of eigenvalues for simplicity in size and compressions comparisons to the bloom őlter representations. Each eigenvalue has a double bit precision by using a 32 bits representation. Thus the total rank representation may use 9600 bits,

EXPERIMENTATION

which is already larger than the 7000 bits of our biggest bloom őlter. This makes that the number of the number of non-zero eigenvalues to őnd should not overpass 300.

The comparisons were stopped because the item similarities that one may achieve by using the reduced SVD model were not accurate. Indeed, the items-features matrices are so sparse that the SVD can not őnd a very low rank model. This may be solved by increasing the rank of the matrix, yet the bloom model have already demonstrated very good similarity ődelity in a much more reduced item space representation. In addition, the large dataset made the SVD model very memory and timely expensive.

Fidelity of the AND similarity

Our bloom model ofers two relevant performances: reduced size and similarity ődelity.

In this section, we evaluate the accuracy of the AND Similarity measure.

We compute the similarity between őlters, and thus items, by performing the two-bytwo bitwise AND operation. First, the bit operation returns the intersected őlter between two őlters. There are two ways to exploit such results: the cardinality representation and the set representation of the bloom őlter. The former compares two őlters by using their bit-set vectors. It is fast but it highly depends on low values of k. The latter compares two őlters by their set representations. In fact, it reconstructs the AND intersected bloom őlter into a N dimensional vector by querying it. Hence, it is slower, yet it allows to compare bloom model and vector model similarities under the same conditions, since items in both models are represented as vectors of dimension N.

On the one hand, we reconstruct the set representation of the resulted AND operation.

The őrst test aims to check whether the bloom model is loyal to the similarity degree of items, i.e. similarity ődelity. Hence, we compare item similarities in both models: vector similarity model (using jaccard similarity) and bloom similarity model (using AND bitwise similarity). We focus on item 3426 which has more active features, and thus the bloom őlter with the most insertions and highest false positive ratio. This is our worst case comparison, since it is more likely to have bits conŕicts in a őlter comparison. Figure 5.7

shows the degree of similarity of this item to other items in the dataset for both approaches.

It demonstrates the high ődelity in the similarity of the bloom model (case bloom 0.001 in 5.4. EXPERIMENTATION tops: the same items should appear in both tops (in this test the order of items is not taken into account). As a result, by comparing tops, one knows the correct presence of items (True Positive (TP)), the correct absence of items (True Negative (TN)), and the errors (False Negative (FN) and False Positive (FP)). As a consequence, the accuracy of the system is deőned by Equation 5.5:

Accuracy = T P + T N T P + T N + F P + F N (5.5)
The values for this accuracy vary between 0 and 1, where the value of 1 is the highest possible accuracy.

The most important parameters of our bloom model for similarity comparisons purposes is the false positive in bloom őlters because it may derives in false positive similarities.

Thus, in order to compare both similarity models under the same conditions, we reconstruct the bloom őlter representations from Table 5.2 into vector representations of size N . The false positive ratio will make the diference between a real vector and a reconstructed vector, and hence, comparisons in similarities are possible to perform.

Figure 5.10 shows the results for these tops comparisons. Notice that bloom őlter representations may achieve almost a perfect accuracy ődelity in very reduced sizes. In fact, the bloom őlter with a false positive of 0.001 and 3408 bits achieves an almost perfect score in these presented top similarities.

The XNOR similarity

The XNOR Similarity shows common insertions in two bloom őlters, but it also shows the features that likely have not been inserted in any of the bloom őlters, i.e. common insertions and common non-insertions. In this test we compare whether the bloom model correctly őnd similar items by using this XNOR operation. Again, the false positive ratio of bloom őlters has impact over the őlter similarities. We consider the settings of Table 5.2 to compare our performances.

We compute the XNOR operation in vector models, and we compare this to the XNOR operation in the bloom őlter similarity model. Once the bloom őlter operations have been 5.5. DISCUSSION goal is to use bloom őlters in order to alleviate these constraints and to create similarity measures based on bloom őlters. As a result, we focused on three aspects: (1) the size compression of bloom őlters in a recommender system context, (2) the usage of AND operations as a similarity measure in bloom őlters to consider common insertions, and ( 3)

the usage of XNOR operations as a similarity measure that takes into account not only common inserted items, but also common non-inserted items.

The experimentations performed on a public dataset [START_REF] Cantador | 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011)[END_REF] show that the bloom őlter representation highly reduces the size of vector representations (94-97% per vector) while keeping a high ődelity in the item similarity (accuracy of 98%) in comparison with standard approaches.

This chapter has faced the items' and users' large vector representation challenge. Our approach allows to reduce memory consumption in recommendation process as long as to use very detailed items' and users' descriptions.

Motivation

Recommender Systems have demonstrated a great accuracy while predicting the interests of "warm-users", i.e. users whose some interests are known. However, they still sufer from cold-start problems, such as the new user cold-start and new item cold-start, a.k.a.

"cold-user" and "cold-item" respectively.

The cold-start is the situation in which the recommender system has no or not enough information about the (new) users/items, i.e. their ratings/feedback; hence, the recommendation to users (or of items) are not well performed. On the one hand, the item cold-start can be alleviated by using the item's attributes in content-based and hybrid recommendation techniques. Moreover, this information is easily available. On the contrary, the user cold start is more diicult to deal with since the new user needs to deliberately present 6.1. MOTIVATION her attributes (e.g. age, genre, studies, etc.) and/or expresses her interests in items (i.e. ratings/feedback). However, users are not willing to give much information and evaluate many items [START_REF] Rubens | Active learning in recommender systems[END_REF], Elahi et al., 2014].

This issue is commonly encountered in collaborative őltering recommendations as they rely mainly on the users' feedback to predict future users' interests [START_REF] Su | A survey of collaborative őltering techniques[END_REF]. Moreover, the recommendations' accuracy is directly related to the users' satisfaction and ődelity [START_REF] Rubens | Active learning in recommender systems[END_REF]. New users start evaluating the system from their őrst usage and this makes the recommendation process a challenge for both academia and industry [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. Users may do not trust the recommendations given and may leave before the system learns to return proper recommendations.

The current techniques to cope with the new users cold-start are categorized into passive learning and active learning:

• Passive collaborative őltering techniques learn from sporadic users' ratings; hence learning new users preferences is slow [Karimi et al., 2015a]. Other techniques propose correlations between users and/or items by using the users/items attributes [START_REF] Kantor | Recommender systems handbook[END_REF], such as content-based [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF] and hybrid methods [Karim, 2014]. Many of these techniques were discussed in the Chapter 2. However, dealing with such features slows down the process and adds complexity and domain dependency.

• Active techniques interact with the new users in order to retrieve a bunch of ratings that allows to learn the users' preferences. A naive but extended approach is to question users about their interests and get their answers [START_REF] Rashid | Getting to know you: learning new user preferences in recommender systems[END_REF].

Such questions may include: 'Do you like this movie?', with possible answers such as:

'Yes, I do'; 'No, I do not'; 'I have not seen it'. In fact, this process can be applied for cold-users in a sign-up process (a.k.a. Standard Interaction Model) or for warm-users (a.k.a. Conversational and Collaborative Model) where users can provided new preferences to the system; hence the system can better learn all users preferences [START_REF] Rubens | Active learning in recommender systems[END_REF]. users are not willing to answer many questions [START_REF] Rubens | Active learning in recommender systems[END_REF], Elahi et al., 2014].

Therefore, the main challenge in active learning is to present short but very informative questionnaires (a maximum of 5-7 questions [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]). This maximizes the information retrieved from users and minimizes users' eforts [START_REF] Harpale | Personalized active learning for collaborative őltering[END_REF].

The personalization of the questionnaires lead to a progressive understanding of the user's preferences. In fact, the personalization of the questionnaires is close to a recommender system concept, although the latter seeks the items the user likes and the former seeks the items the user recognizes. In this context, we speciőcally focus on an optimization of the prediction accuracy, since it is directly linked to users' satisfaction [START_REF] Rubens | Active learning in recommender systems[END_REF].

Current techniques for personalizing questionnaires in active learning collaborative őltering are based on decision trees. These techniques analyze the available warm users' ratings in order to őnd out which items to propose to users. However, their efectiveness in small datasets has not been probed. Moreover, we believe that taking into account warm users' predictions may enhance these techniques. In this chapter we suggest to exploit both available warm users' ratings and warm users' ratings predictions in order to improve the questionnaire. The experimentation shows that our approach enhances previously suggested ones in terms of accuracy and in using a smaller number of questions.

The remaining structure of this chapter is organized as follows: Section 6.2.2 presents the state of the art for active learning using decision trees techniques. Section 6.3 gives the background and notation used for decision trees. Section 6.4 presents our contribution to enhance active learning based on past warm users' rating predictions. Section 6.5 shows the experimentations performed and the results of our approach. Finally we conclude and present our future works in Section 6.6.

Related Work in Active Learning

Active learning is a data acquisition method that not only helps the system to learn cold users preferences, but it lets warm users to clarify and better express their preferences as well. Thus, the user is more self-conscious about her own preferences while the system

RELATED WORK IN ACTIVE LEARNING

a new user by posing as less questions as possible [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF].

Personalization of questionnaires and strategies in active learning

On the one hand, the personalization of the questionnaire increases the information retrieved from users. Randomly selected candidate items (questions) are possibly not recognized by the new users. The static non personalized questionnaires show always the same candidate items regardless the user (eg. most sold items), and hence the evolution of her tastes is not well captured. Personalized questionnaires alleviate these drawbacks.

On the contrary, they may carry out a waiting time between questions [Karimi et al., 2011a],

and the users are not willing to wait. Thus, the ideal questionnaire may intelligently present personalized candidate items and be fast to react to answers.

On the other hand, the active learning techniques have one or many strategies to pick up adequate candidate items. Some of them are given below, for a further detailed classiőcation of these criterion strategies please refer to [START_REF] Rashid | Getting to know you: learning new user preferences in recommender systems[END_REF], Elahi et al., 2014]:

• Popularity, Variance and Coverage. Most popular items tend to have higher number of ratings, and thus they are more recognized. Popularity-based questionnaires increase the "ratability" [START_REF] Carenini | Towards more conversational and collaborative recommender systems[END_REF] of candidate items in order to obtain more number of feedback, although very particular interests of new user preferences, out of popular items, are not captured. In addition, items with low rating variances are less informative. Thus, variance-based questionnaires show the uncertainty of the system about the prediction of an item [START_REF] Boutilier | Active collaborative őltering[END_REF]. On the other hand, the item's coverage (i.e. number of users related to this item) can lead to create interesting rating's correlation patterns between users.

• Entropy. This strategy uses information theories, such as the Shannon's Theory [Shannon, 2001], to measure the dispersion of items ratings and hence to evaluate items informativeness. This technique tends to select rarely known items. In addition, entropy and popularity are correlated, and they are very inŕuenced by the users' ratability (capacity of users to know/rate the proposed items) [START_REF] Rashid | Getting to know you: learning new user preferences in recommender systems[END_REF].

RELATED WORK IN ACTIVE LEARNING

answers. However, these models do not perform well in on-line questionnaires because questions' answers lead into a time-consuming model update. In [Karimi et al., 2011a] this idea was extended by questioning only about the most popular items. This reduces the number of items to focus on and results in faster models. In [START_REF] Karimi | Non-myopic active learning for recommender systems based on matrix factorization[END_REF] they applied active learning for matrix factorization. They believe that solving the new user cold-start is an optimization problem, which explores the latent space given by the matrix factorization to get new users parameters, then it exploits and adjusts these users parameters. Recomputing the whole matrix with each new rating is not tractable, and hence they propose a fast-online updating [START_REF] Rendle | Onlineupdating regularized kernel matrix factorization models for large-scale recommender systems[END_REF]] after each answer.

One technique that is very meaningful in active learning is user partitioning. It allows to group users of similar tastes into clusters or nodes, and then tries to őnd out to which group the new user belongs to. In [START_REF] Rashid | Learning preferences of new users in recommender systems: an information theoretic approach[END_REF] the authors assumed that őnding the correct users neighbors will improve the information gain of the questions presented to users. They presented the Information Gain through Clustered Neighbors (IGCN) algorithm to adjust the entropy of the items by taking into account only those users who match with the new user's proőle.

In [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF] the authors use non supervised ternary decision trees to model the questionnaire. The decision trees are built of-line to be completely available for new users that receive the questions sequentially. To move to a new question they answer the current one by clicking on one of the three possible answers ('like', 'hate' and 'unknown'). The users' answers lead to a diferent child node of the ternary decision trees. This creates a personalized tree path that depends on the past users' answers. On the other hand, this technique uses a collaborative őltering approach to build the decision trees. Using available users' ratings, they seek the best discriminative item in order to split the population of users into three nodes (users who liked, those who hated and those who do not know this item). The best item is the one which minimizes a statistical error within the users' ratings of the node. In order to evaluate the performance of the tree, the authors add labels to the candidate items by using the item average prediction method and demonstrated that their technique improves the accuracy of the system.

Recent literature seems to focus on decision trees to handle questionnaires and on

RELATED WORK IN ACTIVE LEARNING

matrix factorization as a prediction model. The authors in [START_REF] Zhou | Functional matrix factorizations for cold-start recommendation[END_REF] suggest to integrate decision trees construction into the matrix factorization model. They call it "Functional Matrix Factorization". The őrst step is to learn about the underlying item feature vectors. In the second step, the users are deőned as ratings' vectors and one function maps these users into an underlying users features vector. This function is responsible for creating a ternary decision tree ('like', 'dislike', 'unknown'). Hence, matrix factorization is applied to learn both function and items-features through an iterative alternating minimization process, which is performed in each node of the three. In [START_REF] Karimi | Factorized decision trees for active learning in recommender systems[END_REF], the authors claim that [START_REF] Zhou | Functional matrix factorizations for cold-start recommendation[END_REF] is computationally too expensive.

On the contrary, they suggested incorporating the matrix factorization into decision trees.

They őrst build the decision tree as in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. Each node represents an item with an associated rating prediction label. The goal of the matrix factorization is to improve this label. Indeed, they train one matrix factorization model for each level of the tree, and aggregate users within the nodes into a pseudo-user for whom a prediction about the candidate item in the node is performed. This new predicted label replaces the last one.

Very recently, in [Karimi et al., 2015b] the authors assumes that warm users can be thought as new users from whom some ratings are known. Thus, this is seen as a supervised decision trees which internally reduces the accuracy of the technique by picking the best discriminative items. Moreover, they split the tree nodes into six, a 1-5 natural scale rating and an unknown node. This technique improves [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], and is later enhanced by (1) taking into account the most popular items only [Karimi et al., 2011a],

and (2) using matrix factorization to improve the prediction labels assigned to the tree nodes [START_REF] Karimi | Factorized decision trees for active learning in recommender systems[END_REF].

The approaches in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], Karimi et al., 2015b] use the big but not available Netŕix dataset [START_REF] Narayanan | Robust deanonymization of large sparse datasets[END_REF]. However, these approaches are not tested on smaller datasets, especially in terms of the number of users/ratings. In fact, a low number of users and ratings may produce an early pruning of some brunches of the tree. Moreover, early nodes with less data reduce the accuracy of the item's average method and the discriminative items choice. Set of item's predictions in node t

ACTIVE LEARNING DECISION TREES

Active Learning Decision Trees

This section introduces our contribution. We suggest exploiting not only the available ratings from warm users, but also the predictions made by collaborative őltering algorithms over these available ratings. We őrst give some considerations to decision trees for small datasets as long as the current state of the art has not been tested in these environments.

Second, we illustrate our core idea using a real use-case for a better discussion and understanding. We use two datasets from MovieLens1 . Besides, we show the properties of the Netŕix dataset [START_REF] Narayanan | Robust deanonymization of large sparse datasets[END_REF] for datasets' size comparisons. These datasets are later used in Section 6.5 to evaluate our approach and their properties are given in Table 6.3. Third, we present the techniques and algorithms for decision trees in non supervised and supervised techniques. In addition, a complexity analysis of our algorithms is provided.

ACTIVE LEARNING DECISION TREES

items, to őnd out the best discriminative items and to assign a prediction label to them.

This factor is used in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF] as a stopping criteria. The authors claim that there is a very little gain in going further in analyzing nodes with few ratings. Nevertheless, we consider that the number of users should be taken into considerations as well.

The number of ratings in a node is directly related to the number of users in this node.

This is important in the őeld of recommender systems since users' preferences with higher number of ratings are better detected. On the contrary, having less number of ratings per user may lead to a bad understanding of users' preferences. In decision trees, nodes containing few users but many ratings perform better in preference detection than nodes containing many users with fewer ratings. As a result, taking into account ratings only may yield to unstable performances in small datasets.

Warm users predictions in decision trees

Users are not willing to rate too many items. Hence, the main challenge of active learning is to learn the (new) users' preferences as soon as possible by creating a short but informative questionnaire. In this section we explain the core of our contribution which is to use the prediction of available ratings to enhance active learning using decision trees.

Current decision trees techniques exploit only the available ratings in R in order to (1) őnd the discriminative items, (2) split the users' population, and (3) compute predictions over the candidate items. For instance, let us őx the decision trees analysis into the node t. These techniques iterate among items in I t and analyze their impact in R t . This impact is typically measured by associating an error when splitting users using their preferences to these candidate items. The goal is to őnd out, for each node of the tree, the best discriminative item that optimizes this error.

In addition, these techniques use a simple item prediction method based on the "item rating average" in order to evaluate a prediction accuracy and to compute prediction labels for candidate items. Note that this technique is adequate for large datasets, which allows a quick and acceptable generation of predictions from the available ratings in R t . On the other hand, using more accurate prediction techniques is possible but (1) it is very expensive and time consuming to do it for every node of the tree, and (2) the predictions (2) the matrix factorization (MF), and (3) the matrix factorization average (MF-Avg).

The őrst sets the item's rating average as the item's prediction. The second decomposes a matrix R into two random matrices in such a way that the multiplication of both matrices gives approximately the original R [START_REF] Zhou | Large-scale parallel collaborative őltering for the netŕix prize[END_REF]. The third uses a matrix of predictions over available ratings given by the matrix factorization to set the item's prediction average as the item's prediction. Our goal is to show that (1) as demonstrated, the matrix factorization performs better in terms of accuracy than the item rating average method, and (2) the item prediction average predictions are close to the item rating average predictions.

This analysis is performed as follows. First, we obtain P by performing the matrix factorization over the available R. Second, we count the number of ratings per user and we divide the users into groups; users having less than 50 ratings, less than 100 ratings, etc.

Highlight that these groups are incremental and thus one user may belong to more than one group. For each of these groups, the users' ratings and the corresponding users' predictions are taken from R and P into separated sets R ′ and P ′ . Third, we evaluate the performance of predictions in P ′ by computing the root mean square error (RMSE). Moreover, we perform the item rating average over R ′ , and item prediction average (MF-Avg) over P ′ , in order to observe their performance as well. The results are given in Figures 6.4(a) and 6.4(b). As expected, MF outperforms the item rating average method. In addition, we observed that MF-Avg attempts to imitate the behavior of the item rating average method.

Hence, the item prediction average is also an acceptable predictor regarding the item rating average. In fact, one can observe that item rating average and item prediction average are closer while dealing with more users and ratings. This behavior is perfect in decision trees since the top of the tree is more populated by users and ratings. On they contrary, they 6.4. ACTIVE LEARNING DECISION TREES sumes that warm-users can be considered as cold-user from which some ratings are known, and hence, the known users' ratings can be used to validate the technique. As a consequence, it is possible to compute an error based on the prediction accuracy, such as RMSE.

On the contrary, since non supervised techniques do not have any validation, they compute a statistical error based on the available ratings in the node. Nevertheless, in both approaches a validation is not possible in the 'unknown' nodes, since by deőnition, there is no rating label for these users to this item. As a consequence, the statistical error is mandatory in this case. Our approach uses similar statistics as [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF].

Non Supervised Decision Trees for Active Learning

In [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], the authors deőne a set of statistics and an internal error using these statistics to őnd out the best discriminative item. In this approach, the best item is the one which reduces this error. In addition, as long as the tree nodes contain many ratings, they use the item rating average method to compute item label predictions for items.

We suggest to use the predictions P over the available ratings in R in order to enhance this technique. Formally, given the node t, there are ratings r u,i ∈ R t so that u ∈ U t and i ∈ I t . In addition, for each rating r u,i there is an associated prediction p u,i ∈ P t . The goal is to őnd out, among all candidate items j ∈ I t , the best discriminative item i * . To do that, we compare the current state of the node t to the impact of picking j as discriminative item, as it is explained below.

On the one hand, the current status of the node j is given by all the items' ratings in P t . The properties of this status are given by the statistics presented in 6.1, which consider separately all items in the node. This allows to glimpse a current state error as 6.2, which is indeed the error contribution of every item j in the node t: e 2 (t

) j = sum 2 (t) j -(sum(t) j ) 2 /n(t) j . ∀j ∈ I -i : sum(t) j = ∑ u∈Ut∩P (j)
p u,j (6.1)

sum 2 (t) j = ∑ u∈Ut∩P (j) p 2 u,j n(t) j = |u ∈ U t ∩ P (j)| e 2 (t) = ∑ j sum 2 (t) j -(sum(t) j ) 2 /n(t) j (6.2)
On the other hand, we look for the best candidate item that minimizes this current error. Thus, we analyze the impact of every item j within this node t and the child nodes.

We őrst suppose that j is a discriminative item and we split U t into 3 childs: tL for users who liked j (r u,j ≥ 4), tD for users who did not like (r u,j ≤ 4)) and tU for users who do not know the item (absence of rating). Highlight that we use R t to split the users' population.

In addition, we delete the presence of discriminative item ratings in child nodes. As a consequence, one has 3 rating subsets R tL , R tD and R tU in child nodes U tL , U tD and U tU , respectively. The impact of picking j as candidate item is given by the error of these three nodes: Err t (j) = e 2 (tL) + e 2 (tD) + e 2 (tU ). This means that one evaluates the status of the given child nodes by using the Equation 6.2 and associated subsets P tL , P tD and P tU . However, the number of users in the unknown node tU is normally much larger than in other groups, and hence, the computation is heavier in this node. To avoid this, it is possible to deduce statistics for tU from the node t and the other child nodes tL and tD, as follows:

sum(t u ) j = sum(t) j -sum(t L ) j -sum(t D ) j (6.3) sum 2 (t u ) j = sum 2 (t) j -sum 2 (t L ) j -sum 2 (t D ) j n(t u ) j = n(t) j -n(t L ) j -n(t D ) j
By doing this analysis with every candidate item j ∈ I t , one obtains an associated impact Err t (j). The discriminative item is the one which minimizes such error, i * = 6.4. ACTIVE LEARNING DECISION TREES argminErr t (j), and then it is used as the real splitter to continue the construction of the tree in lower levels.

Finally, once the discriminative item is chosen, the prediction label associated to the tree is given by the item prediction average, i.e. average value of P t (i * ).

This approach is similar to [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], with two major diferences. First, the available ratings are only used to split the population of users. As a consequence, the statistics and the items predictions are computed by using the proposed set of predictions P . Second, once a discriminative item is chosen in a parent node it does not pass to the child nodes. This is done for two reasons: (1) to avoid to choose the same item, and hence, to avoid to pose twice the same question to the same user, and ( 2) to delete the inŕuence of the items' ratings in the child nodes. In fact, one can avoid choosing an item without deleting their ratings as done in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. Algorithm 5 shows this approach.

Supervised Decision Trees for Active Learning

In [Karimi et al., 2015b], the authors suggested using warm-users as cold-users from whom some interests are known. This assumption allows to create a supervised decision trees where some labels are known for validation purposes.

We again suggest to use the predictions P over the available ratings in R in order to enhance this technique. Given the current node t, there are warm users in U t who have ratings in R t and predictions in P t . This technique considers warm users as cold-users from who some ratings are known. Thus, we split the users ratings into training ratings R t-train and validation ratings R t-validation . The former represents the interests of the warm users.

The latter are the items labels given when considered as cold-users. Note that we consider the perfect case where a user u and and item j and in U t-train , U t-validation and I t-train , I t-validation respectively. As long as for each rating r u,i there is an associated prediction p u,i ∈ P t , it is possible to obtain P t-train as well.

As a result, the current node t contains ratings in R t-train , predictions in P t-train , and ratings for validation purposes in R t-validation . The goal is to őnd out, among all candidate return i * 27: end function items j ∈ I t , the best discriminative item i * . To do that, we compare the current state of the node t to the impact of picking j as discriminative item, as it is explained below.

On the one hand, the state of the node t is given by the Root Mean Square Error (RMSE), which computes the squared diference between current predictions and real observed ratings. Predictions are computed by using the "item predicion average" method over P t-train . Observed ratings are taken from R t-validation . Therefore, each user u ∈ U t is associated to one error RM SE1 u . The current error in the node is the sum of all user's errors.

On the other hand, we look for the best candidate item that minimizes this current error. Thus, we analyze the impact of every item j within this node t and the child nodes.

ACTIVE LEARNING DECISION TREES

We őrst suppose that j is a discriminative item and we split U t into 3 childs: tL for users who liked j (r u,j ≥ 4), tD for users who did not like (r u,j ≤ 4)) and tU for users who do not know the item (absence of rating). Highlight that we use R t-train to split the users' population. In addition, we delete the presence of discriminative item ratings in child nodes. As a consequence, one has 3 rating subsets R t-train-L , R t-train-D and R t-train-U in child nodes U t-train-L , U t-train-D and U t-train-U , respectively. Hence, it is possible to compute the state of the child nodes as it was performed before. This creates a second user error, RM SE2 u . The impact of picking j as candidate item for the user u is △ u,i = RM SE1 u -RM SE2 u . Thus the impact of picking j as candidate item for the node t is given by the sum aggregation of all impacts of j.

The number of candidate items to analyze can be very large. We take into account only the 200 most popular items, as done in [Karimi et al., 2015b]. This yields in very acceptable accuracy and a great reduction in the time analysis. Therefore, after the analysis of all users and candidate items, the item in R t-train associated to a higher overall impact is picked as discriminative item i * , since the maximum value here means a higher error diference. Finally, the predicted label for this discriminative items is given by the item prediction average over current node P t . This approach is similar to [Karimi et al., 2015b], with two major diferences: (1) P is used to validate the approach, and to obtain items label for the chosen discriminative items, and (2) we split the nodes into 3 child nodes ('like', 'dislike', 'unknown') rather than 6. This warrants a minimum number of users in child nodes to avoid fast pruning in small datasets. Algorithm 6 shows this approach.

Complexity of the algorithm and Time analysis

The complexity of our approaches for non-supervised decision trees and supervised decision trees is very similar to [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], Karimi et al., 2015b]. In fact, despite some diferences in the way of computing the error that needs to be improved, these algorithms follow a similar procedure. return i * 24: end function In fact, adding the prediction set P does not afect the complexity of the algorithms, although, it does afect the memory footprint of the approaches. Considering that ratings R and predictions P sets are coded equally, our approach consumes double of the memory size to store the set P . In addition, extra runtime is required to split both R and P accordingly.

The time-consumption of the algorithms is similar as well. A little extra time is needed in our approaches in order to deal with the split of the prediction in P . In addition, in comparison to [Karimi et al., 2015b] our supervised approach is faster due to the reduced number of child nodes.

Experimentation

The goal of our experimentation is two-fold (i) to present the behaviour of current techniques in smaller datasets and (ii) to show the performance of our presented approach.

Recent techniques have presented their results using Netŕix dataset. However, this dataset is no longer available for research. Hence, we use two versions of the Movielens dataset. Table 6.3 describes the properties of these datasets.

Since our approach considers external techniques prediction as a new source, in order to build our decision trees we use matrix factorization [START_REF] Zhou | Large-scale parallel collaborative őltering for the netŕix prize[END_REF] due to its accuracy.

We compare our approach in non supervised decision trees, as in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF],

and in supervised decision trees, as in [Karimi et al., 2015b]. The latter will not be largely explained due to a lack of space.

The technique in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], denoted "Golbandi", uses two parameters:

bias overőtting λ 1 and rating overőtting λ 2 . We set empirically these parameters to λ 1 = 7

and λ 2 = 200. The technique in [Karimi et al., 2015b], denoted "Karimi", uses a rating overőtting parameter λ 2 . Our approaches are identiőed as "Pozo Non Supervised" and "Pozo Supervised", and they do not contain any parameters, which represents an advantage in comparison to the state of the art.

As long as non supervised decision trees and supervised decision trees require diferent settings, we explain these experimentations separately. In order to compare the approaches we use the RMSE metric oriented to users, which measures the squared diference between the real ratings and the predicted ratings:

6.5. EXPERIMENTATION RM SE u = √ 1 N ∑ (r u,i -p i ) 2
Where N is the number of ratings of the user u, p i is the predicted label value of the candidate item in the question node and r u,i is the real rating of the user u for the item i. Hence, the evaluation of the error in one question is the average of the users error in this question number. As a consequence, for this metric the lower is the better.

Knowing that the experimentation may depend on the split of the dataset, we run it 50 times and then used the mean value of the RMSE. We use this process to evaluate the performance for the MovieLens 1M and MovieLens 10M.

Non supervised decision trees

The experimentation carried out in [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF] The process we have followed to run this experimentation is as follows. First we split the dataset into U train and U test . Second, we compute the collaborative őltering algorithms over ratings R in U train and we extract the associated predictions P . Third, we train the approach of "Golbandi" by using U train . Our approach is trained by using both ratings in training set R and the prediction of the training set P . Finally, the performance of the decision trees is evaluated by using the test set U test . The users in this set are used to answer the questions. If the item is known, we compute the RMSE associated to this answer and this question. Then, the user answers a new question. At the end, we compute the average of the accumulated nodes RMSE. On the one hand, our approach achieves a lower error in less number of questions. This 6.6. DISCUSSION time consumtion of Karimi by around 50% due to the reduced number of child taken into consideration.

Discussion

Recommender Systems sufers from new user cold-start. This issue is more acute in collaborative őltering techniques since they only rely on users' ratings to generate recommendations. In order to learn the (new) users' preferences, passive recommender systems wait for sporadic ratings from users. On the contrary, active learning is proposed as a data acquisition method that gathers users' ratings by presenting a simple questionnaire to users. For instance, 'Do you like this movie?': 'Yes, I do like'; 'No, I do not like'; 'I have not seen it'. However, users are not willing to answer many questions or to rate many items. Therefore, the main goal of active learning is to create a short but eicient and informative questionnaire.

The state of the art has evolved from non personalized batch-oriented techniques (giving many questions at once and the same questions to any user) to personalized sequentialoriented questionnaires (giving questions one by one taking into account the past current users' answers). In our point of view, the personalization of the active learning technique is crucial to better learn the new users preferences and current methods based on decision trees are interesting techniques to model questionnaires. Indeed, the personalization of decision trees allows to predict with which items the new user has been in contact, and present them to the users.

However, active learning techniques based on decision trees have not been applied to small datasets. Less number of users and ratings afect the performance of these algorithms.

In addition, we consider that recent approaches do not properly consider the prediction of candidate items. On the one hand, they use very simple prediction methods to make the decision trees tractable. On the other hand, they only exploit the users' ratings.

In this chapter we proposed using two sources in the decision trees active learning technique. The main idea is to train an accurate collaborative őltering techniques with a ratings dataset to generate a prediction dataset. Both ratings and predictions dataset 6.6. DISCUSSION are used inside the decision trees. The former properly split the users' population while building the tree. The latter enhances the seek of the best discriminative items (questions)

and better predict the associated labels. We have tested this approach in non supervised decision trees and supervised decision trees techniques.

The experimentation uses two publicly available datasets: Movielens 1 million ratings and Movielens 10 million ratings. We show that our approach enhances the state of the art in terms of RMSE and the related number of questions. In fact, we őnd better questions and better predictions that make it quicker reduce the error. This is especially useful in small dataset contexts, where the low number of users and ratings do not allow to create big decision trees.

Finally, the approach suggested in this chapter allows to alleviate the new user cold start, issue that, together with the scalability and large items/users representations, is a big challenge in the domain of recommender systems.

Chapter 7

Conclusions and Perspectives

Conclusions

Recommender systems help users to deal with information overload and in the decision making processes. They aim to reduce the huge amount of information that users of the Internet have to face by studying their interests and presenting őrst the information in which they may be more interested [START_REF] Kantor | Recommender systems handbook[END_REF]. This has raised the attention of the e-commerce and services providers in order to personalize the products, the services and the users' experience.

In Chapter 2 we have presented some techniques and approaches coming from the state of the art in academia and industry environments. The collaborative őltering methods are one of the most widely used approaches [START_REF] Kantor | Recommender systems handbook[END_REF]. Particularly, the matrix factorization techniques have been very well received in the recommendation őeld due to their great accuracy and scalability. However, these techniques do not exploit the heterogeneous data coming from items' descriptions or users' descriptions. In addition, the integration of this information into the matrix factorization process is complex and it afects to the domain dependency and scalability of the system. Another challenge of collaborative őltering techniques is the cold start [START_REF] Su | [END_REF]Khoshgoftaar, 2009, Elahi et al., 2014]. This issue has been typically addressed in the state of the art by implementing hybrid recommender systems in order to alleviate the drawback of techniques with the advantages of the others.

This thesis has focused mainly on collaborative őltering approaches. We have chosen 7.1. CONCLUSIONS factorization. The results of this proposition demonstrate a great improvement in rankbased recommendations, where it overcomes the precision, recall and f-measure metrics.

The side efect of this approach is that top-K recommended items tend to be more similar, regarding an intra-similarity list metric.

In Chapter 5 we discussed that items and users can be described by very large amounts of data linked to items/users characteristics or other external resources such as social networks [START_REF] Peis | Semantic recommender systems. analysis of the state of the topic[END_REF], Kantor et al., 2011, Dahimene et al., 2014]. Indeed, the number of features to describe items/users afects the correlation of data. Generally the more attributes are used the better the accuracy of the similarity is. Particularly similaritybased recommender systems (e.g. content-based and other hybrid approaches) represent items/users as a vector of features or keywords, and thus, vector similarity methods can be computed. Thus, these vectors can be very large, sparse and memory-consuming. To avoid this issue, the state of the art uses feature selection techniques. However, reducing the number of features may yield to a loss of quality in the item representation, and consequently, in items similarity. We proposed to use a compressed yet high quality data representation for items/users based on Bloom Filters [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF].

We exploit the bloom őlters' properties in order to create two fast an accurate similarity measures: AND and XNOR. The former takes into account the common descriptions of items/users, which are inserted in their own őlters. The latter takes into account both common insertions and common missing insertions. The most interesting of this approach is that őlters consumes almost the 96% of the size of standard vector representations, and they achieve the 98% ődelity while computing similarities.

Our fourth challenge was to cope with cold-start issue. The new items cold start and the new users cold start are both present in recommender systems, although they are more acute in collaborative őltering techniques [START_REF] Rubens | Active learning in recommender systems[END_REF], Elahi et al., 2014].

Besides, the new items cold start can be more easily alleviated by taking into account the description of items, and thus using hybrid approaches. However the new user coldstart in collaborative őltering methods need to incrementally, adaptively and quickly őnd out the new users' preferences. In Chapter 6 we dealt with this issue by proposing an active learning technique based on collaborative őltering decision trees. In this method the 7.2. PERSPECTIVES (new) users interact with the system that presents a personalized questionnaire, i.e. which changes depending on the users' answers. The goal is to retrieve informative answers which represent the users interest in order to adapt next questions and increase the knowledge about the users' preferences. Compared to other approaches, we suggest to exploit two sources of data: the warm users' ratings and the warm users' predictions over these ratings.

Our approach is faster in understanding the users' preferences what allows to reduce the number of questions to pose.

Finally, the four aforementioned challenges and approaches are possible to be merged.

One can easily imagine an active learning technique that captures the őrst users' preferences in order to slowly feed a matrix factorization technique which generate useful recommendations. In addition, the implicit interest of users in items' attributes can be taken into account in both active learning and matrix factorization. Furthermore, these interests are large descriptions of users through the items' descriptions, i.e. what a user like from items.

This can be exploited by recommender systems in order to give explanatory recommendations (e.g. you may like this movie because it is a comedy and you liked the actors who play in it); and hence to increase the acceptance of recommendations. We are aware of the scalability of the system as well, and thus recommendation processes and memoryconsumptions may be taken into account in the whole deployment of the recommender system.

The next section presents the perspectives and the on-going work of our research.

Perspectives

FIORA Project

In Chapter 1 we noted that this thesis is part of a collaborative project called FIORA1 , which aims to build a generic, robust and scalable recommender system. The domains in which this project will be applied are e-nutrition and e-tourism. As long as data from these domains were not available, we have experimented and published our contributions by using public datasets such as Movielens2 .

PERSPECTIVES

Our őrst perspective focuses on testing our approaches under the context of FIORA, in particular the domain of e-nutrition. Indeed, one of the partners has recently launched a website called "My coach nutrition"3 , which aims to help users in the nutritional decisions in the every-day-life. It takes into account the users' proőle and preferences, such as tastes and allergies, in order to suggest healthy and balanced diets and to teach the users to cook recipes and to correctly treat ingredients. Today, this site is open and data is being collected.

Positive and Negative implicit users' interests

Chapter 4 discussed the concept of the implicit users' interests in the items' attributes.

We have seen that this interest comes from the number of occurrences of attributes (i.e.

attributes' values, such as a particular movie genre or actor) in the past rated items.

In addition, in order to be processed by collaborative őltering approaches, we transform ratings into "semantic ratings" by using a "semantic equation". However, this equation only provokes an addition in the original ratings.

The state of the art presents a special way of assuming whenever users like or not (binary assumption) an item depending on the rating the user gave to the item [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. Thus, there is a more-less established threshold: ratings' values greater or equal to 4 (in a scale of 5) are considered to be liked and not liked in other case (assuming that 0 is the absence of rating and thus the absence of preference). It could be possible to exploit this assumption in order to őnd out positive and negative implicit users' interest in the items' attributes:

• Positive. The implicit positive interest of users' in the items' attributes is given by the number of occurrences of attributes over the past rated and liked items (rating greater or equal to 4 out of 5).

• Negative. The implicit negative interest of users' in the items' attributes is given by the number of occurrences of attributes over the past rated and disliked items (rating lower to 4 out of 5).

Exploration, exploitation and explanation in recommender systems

The exploration paradigm consists in letting the user freely navigate among the items to discover and rate new unexpected items [START_REF] Kantor | Recommender systems handbook[END_REF]. On the contrary, the exploitation paradigm refers to the usage of the users' interest (explicit or implicit) and the persistence of recommendations, e.g. to continuously recommend the same items to users when these suggestions have not been taken in several occasions.

We consider that recommender systems would perform better recommendations by using very detailed descriptions of users and items [START_REF] Mikeli | A multi-criteria recommender system incorporating intensity of preferences[END_REF]. Thus, the exploration and exploitation trade-of will become more important, e.g. to let the users discover new actors and avoid to recommend movies where similar actors from movies he did not like also play. However, in our opinion, there is a third player in this trade-of: the explanation.

The explanation paradigm allows the user to understand and accept the recommendations.

In Chapter 4 we talked about the implicit interest in very detailed items' attributes, which are very diicult to capture in current systems. For instance, the interest of the user in the photography department of a movie. These details could become very interesting in the explanation of recommendations and would open other paths to understand the exploration and exploitation under very users' and items' detailed descriptions. The user could explore new items under a new regard (e.g. to watch a movie and evaluate the photography department). The system can exploit these new interactions accordingly to learn more about the users interests.

As a consequence, the assumptions in Chapters 4 and 5 can be useful to explain the recommendations: on the one hand, the preference of users in the attributes of items are known ("collaboration via content"); on the other hand, the bloom őlter representation of user/items may allow to perform correlations exploiting the big information inserted in the bloom őlters. The challenge is to develop a system which can exploit this information and compute detailed explanations about why users should accept recommended items based on the attributes that the users liked in the past.

PERSPECTIVES

Slope-One questionnaires for active learning

In Chapter 6 we have presented active learning techniques to tackle the new user cold start issue. These methods suggest to present a questionnaire to new users. The user is asked to rate some items and the system learns these őrst users' preferences [START_REF] Elahi | Active learning in collaborative őltering recommender systems[END_REF]. The goal is to őnd the best questions to pose in order to maximize the information gain of the system, i.e. quickly learn the users' preferences. Thus, these techniques look for the items which are informative and recognized by the user in order to retrieve as much information as possible.

Questionnaires should be eicient, short (low number of questions) and quickly react to users answers [START_REF] Rubens | Active learning in recommender systems[END_REF], Elahi et al., 2014]. Due to these constraints, the current state of the art proposes to create the questionnaires of-line by using decision trees techniques [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. As a result, the new user can answer őrst questions and new questions are presented immediately after. This methodology has demonstrated good results, however the current techniques use very simple prediction methods, such as the "item's rating average prediction", in order to build questionnaires in a reasonable time.

Better prediction for active learning methods can be used, such as the Slope-One methods that have demonstrated a better performance in cold-start situations and good prediction accuracy [START_REF] Lemire | Slope one predictors for online rating-based collaborative őltering[END_REF] Another perspective idea is to detect the new users preferences directly on the ŕy. We propose Slope-One methods (which are incremental and scalable) to adapt of-line decision tree questionnaire to on-line questionnaires.

PERSPECTIVES

Time-aware active learning techniques

Active learning techniques for collaborative őltering based on decision trees only take into account the past users' ratings to create questionnaires [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF]. Then, the new users navigate through the questionnaires by answering (i.e. rating) questions (i.e. items).

We consider that there are other resources that appear in questionnaires and may be very useful and informative in collaborative őltering active learning techniques. We especially believe that the time (new) users spent to answer a question is very signiőcant for extracting the users' preferences. Thus, we focus on "time-aware" recommendation techniques and decision trees to retrieve and exploit not only the users' answers but also the users' behavior. On the one hand, we study new Slope-One techniques to create time-aware of-line questionnaires due to their scalability and reactivity. On the other hand, other collaborative őltering techniques have already demonstrated their compatibility with timestamped preferences [START_REF] Koren | Advances in collaborative őltering[END_REF]. However, time-aware techniques tend to be timely expensive whereas active learning techniques require of fast adaptability to the current users' answers. As a result, the challenge is to create accurate, scalable recommendation models that evolves in real-time to cope with cold-start issues. Set of item's ratings r u,i

A.2. PREDICTION ORIENTED EVALUATIONS

Rating of user u in item i ru,i )

Predicted rating of user u in item i ru,i )

Predicted rating of user u in item i r max

Maximum possible rating value r min Maximum possible rating value r threshold Rating threshold to assume the relevancy of an item for a user, rel u,i top -K Set of K items to recommend possible evaluate the performance and quality of the recommendations. This appendix aims to cover most of the evaluation methods used in the recommender systems őeld. Table A.1 shows the notation used in this appendix.

A.2 Prediction oriented evaluations

This evaluation is the most widely used in literature [START_REF] Kantor | Recommender systems handbook[END_REF]. Recommender systems predict the interest of users in items, ru,i ), which are the deduction of how a user would rate an item. This allows to aim to particular user and item. Prediction oriented approaches aim to evaluate the closeness between these predictions and real observed values. Thus, they use the training set to train a get recommendations and the test set to compare if recommendations were correct, regarding their predicted ratings and the real observed ratings from the test set.

A.2. PREDICTION ORIENTED EVALUATIONS

A.2.2 RMSE: Root Mean Square Error

This method measures the squared diference between predictions (r u,i )) and observations (r u,i ): e u,i = |r u,i -ru,i |. In particular, it represents the standard deviation of this diference, thus it is also dubbed Root Mean Square Deviation (RMSD). Compared to MAE, this technique provokes higher penalizations when both values are distant. As a result, the lower is this error, the better is the prediction. The measure is computed for all the ratings in the test set; thus it represents the average of the squared diference. In fact, one may compute a user oriented metric (RM SE u ) or an item oriented metric (RM SE i ), and then normalize by the number of users or items that contributed to this metric. In our model we use standard bloom őlters for simplicity and explanation, yet these drawbacks can be addressed by other bloom őlter approaches.

RM SE =    √ 1 |R| * ∑ r u,i ⊂R (r u,i -ru,i ) 2 =    √ 1 |R| * ∑

RM SE

u =    √ 1 |R u | * ∑
On the one hand, dynamic datasets are possible to model by using dynamic/scalable bloom őlters [START_REF] Guo | The dynamic bloom őlters. Knowledge and Data Engineering[END_REF], Almeida et al., 2007]. The main idea is that a scalable bloom őlter is formed by one or more bloom őlters. Thus, these őlters are built by blocks, and hence by adding new blocks to the őlter one may add a new set of features. As a consequence, this avoid to re-build the bloom model when new features are added. In addition, similar probability inductions given in this section can be applied to scalable and dynamic probabilities, and thus our bloom model remains possible in these cases. On the other hand, counting insertions is possible as well by using counting bloom őlters [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. These őlters contains new bit-sets to count the insertions performed.

Thus, if one insertion has been made several times, őlters may approximate the counting.

As a result, one may compare counting őlters to frequency vectors, with more complexity.

Other variances of bloom őlters deal with extra compression [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]].

  Aőn de fournir une généricité dans le domaine d'application, un passage à l'échelle et une recommandation précise, nous proposons un système à trois couches: une couche de pré-analyse, une couche "sémantique" et une couche de recommandation. Dans une première étape, nous nous intéressons aux préférences des utilisateurs pour le contenu des items. Cette information est souvent manquante lorsque ce contenu peut être très large et varié, et donc diicile d'attirer d'information de score explicite. Nous proposons d'étudier l'intérêt implicite des utilisateurs dans le contenu des items en étudiant les préférences passées sur les items. Ceci est fait à travers un module de comptage qui met en lien chaque utilisateur avec le contenu des items. Lorsqu'un contenu est répété (le même 0.4. L'INTÉRÊT IMPLICITE DES UTILISATEURS DANS LES ATTRIBUTS DES ITEMS acteur qui apparaît dans deux őlms diférents), le compteur d'intérêt de cet utilisateur pour ce contenu est incrémenté aussi.

  Les systèmes de recommandation sélectionne, parmi une grande quantité de données, les informations pour lesquelles les utilisateurs pourraient être les plus intéressés. Ils exploitent les préférences connues d'utilisateurs dans des items, qui sont donnés de façon explicite ou le retour d'information implicite d'utilisateurs, pour prévoir les préférences futures d'utilisateurs dans d'autres items (inconnus). De plus, il est possible pour certaines techniques de recommandation d'utiliser la description d'items ou d'autres données hétérogènes aőn d'améliorer ces recommandations. 0.7. CONCLUSIONS ET PERSPECTIVES Typiquement ces techniques sont classiőées par: őltrage à base de contenu, őltrage collaboratif et méthodes hybrides. Cependant, la technique la plus utilisée est de nos jours une technique de őltrage collaborative appelée la mactorisation matricielle. Cette technique a démontré une grande pécision et une grande facilité pour traiter la montée en charge et le passage à l'échelle. Cependant, elle ne facilite pas l'utilisation de données hétérogènes. De plus, elle soufre du démarrage à froid. Nos travaux de recherche se concentrent sur plusieurs aspects diférents que tout système de recommandation devrait prendre en compte: (1) la qualité et la précision des recommandations, (2) la représentation d'items/utilisateurs, (3) la distribution et l'adaptabilité du système, et (4) le démarrage à froid. Nos contributions ont fait face à ces problèmes:• L'amélioration de techniques de őltrage collaboratives en ajoutant une couche externe pour analyser l'intérêt implicite des utilisateurs dans l'attribut des items. Cette méthode réduit l'impact de la dépendance de domaine dans des recommandations et améliore la qualité des recommandations. En fait, nous croyons que les recommandations d'items qui contiennent des caractéristiques plus connues pour l'utilisateur (par exemple les acteurs, des réalisateurs) vont plus probablement être acceptables.• Particulièrement dans des systèmes à base de contenu et hybrides, traiter la grande quantité de données de caractéristiques peut devenir problématique. La sélection de caractéristiques et des techniques de réduction spatiales sont utilisés pour faire face à ce problème, pourtant ils cèdent inévitablement à une perte d'informations.

2. 2 .

 2 TECHNIQUES AND ASSUMPTIONS simple categories: social-based, content-based and economic-based, also called contextbased. The social-based methods use similarities between users to compute recommendations. The content-based techniques compute similarities between items regarding their attributes. The context-based methods base their recommendations on concrete particular variables such as the price of items and the budget of users, or the current location of users (e.g. to boost recommendations of currently visited shops). However, the categorization most widely used simply divides recommendation techniques into Collaborative Filtering techniques (CF), Content-Based (CB) techniques and

  Switching is the most simple hybridization and it consist on selecting one technique to use among set of established recommendations techniques. The choice of the technique depends on predeőned rules and the situation, such as the cold-start. The mixed hybridization proposes to select recommended items from diferent recom-2.3. RECOMMENDER SYSTEMS IN THE ACADEMY mendation techniques and put them together into a recommendation list.

  The data's combination (a.k.a. feature's combination) hybridization technique uses the data typically exploited in one recommendation technique into another diferent recommendation context. For instance, the web logs contain implicit feedback normally used in collaborative őltering, but content based technique may use them together with items' descriptions. The interest of this technique is to discover new usages for data. The data augmentation (a.k.a. feature's augmentation) technique consists on adding new users or items data (e.g. new ratings), not previously used in other recommendation techniques, before the recommendation process.

2. 4 .

 4 RECOMMENDER SYSTEMS IN THE INDUSTRY granularity. It adapts constantly programmes depending on interest, wishes and humours.

  dataset. The results indicate the good performance of the system compared to current state of the art. This chapter focuses on matrix factorization techniques from the point of view of scalability and accuracy. Section 3.2 starts by presenting a brief state of the art. The necessary background to understand the troubleshooting in the distribution of stochastic gradient descent is given in Section 3.3. The contribution and implementation details of our approach are in Section 3.4. The experimentations and comparisons are in Section 3.5. Finally, we conclude and discuss this chapter in Section 3.6.

Figure 3 .

 3 2 represents an example of the presented paradigm, which is described below.

3. 3 .

 3 BACKGROUND iteration or batch iterations, one can highlight the interdependency of the new updated values and previous values [Makari et al., 2014]. For instance, a new value for b u depends on the last computed value of b u for this user u. In a single machine, new updated values after one iteration are ready for a new iteration. On the contrary, non sharing memory systems may have diiculties to scale the algorithm and it may lead in miss-updated values or lack of synchronization.

Figures 3 .

 3 3(a) and3.3(b) show the block decomposition when 3 and 4 nodes (b = 3 and b = 4) are available. One can highlight that the size of block has been changed and adapted due to the number of nodes.However, (1) what would happen if there are 5 nodes in the cluster?, and (2) what would happen if R is not a square matrix, n u ̸ = n i ? In fact, the key point for the block 3.4. FLEXIBLE DISTRIBUTED STOCHASTIC GRADIENT DESCENT might be performed. However, this does not yield to a loss of data, since inserting empty dimension does not add any noisy information. Based on these ideas, we have developed a ŕexible distributed stochastic gradient descent.

  function closest dimension (above or below) to the real one. Whether the algorithm deletes or adds rows/columns depends on the remainder n ′ r %b = 0 and n ′ c %b = 0. Algorithm 1 shows the process to őnd the closest dimension either below (under) or above (upper) the original dimension. The "rule" is the number nodes b which is the divisor to divide dimensions towards a zero remainder.

3. 4 .

 4 FLEXIBLE DISTRIBUTED STOCHASTIC GRADIENT DESCENT Algorithm 2 Decomposition of the matrix R into blocks. 1: function BlockDecomposition(R, numberOfNodes, mode)▷ mode can be: underDimension, upperDimension or ŕexDimension.

2 :

 2 rowDimension = decCondition(R.rowDim, numberOfNodes, mode); 3: columnDimension = decCondition(R.columnDim, numberOfNodes, mode); row = 0; row ≤ rowDimension; row + + do 8: for column = 0; row ≤ columnDimension; column + + do 9: createNewBlock(row, rowStep, column, columnStep, R ′ ); function of blocks given R and the number of nodes. This is useful to go all over the matrix R extracting the corresponding blocks. The row step size of a block is given by rowStep = n ′ r b and the column step size is given by columnStep = n ′ c b . Algorithm 2 describes the complete block decomposition process. First we őnd the appropriate number of rows and columns (regarding the underDimension, upperDimension or ŕexDimension) which őt with

3 :

 3 for stratum = 1; stratum ≤ numberOf Stratums; stratum + + do this sequence can be random.Running one stratum means to compute the stochastic gradient descent among the ratings in blocks and then updates parameters in P and Q at the end of their execution. This guarantees the integrity and independence of parameters. Algorithm 4 describes this pseudo-code.The doSGDJob is a MapReduce job that analyzes the ratings in the blocks within a stratum to compute the gradient descent optimization. One block is sent to a diferent cluster and thus one block is deőned by one single map. However, all stratum's blocks are computed in parallel. Hence, there are b clusters executing b diferent blocks, which are b map tasks.

  Figures 5.6(a) and 5.6(b) illustrate both cases.

5. 4 .

 4 EXPERIMENTATIONsion or space complexity, (2) operation time and model time, (3) the similarity ődelity of the AND measure, and (4) the similarity accuracy of the XNOR measure.

Figure 6 .

 6 Figure 6.1 represents a functional diagram for both passive and active learning ap-

Figures 6 .

 6 Figures 6.5(a) and 6.5(b) show the results (the mean point values and tendency curves) of this experimentation for MovieLens 1M dataset and MovieLens 10M dataset respectively.

  . These methods are incremental, what allows very fast adaptation of the current models to the answers of users; they are scalable, what allows to parallelize the process among multiple machines; and they tend to recommend popular items őrst, what is very interesting in active learning contexts since they seek for recognizable items by users. It is possible to create a Slope-One model based on the current warm users' ratings. This model would quickly vary together with the construction of the questionnaire creating an of-line questionnaire. In addition, it can incorporate new users' answers to the model making new questions more aware of the new users' preference.

  Square Error (NRSME) is the RMSE divided by the range of the variable.N RM SE = RM SE r max -r min (A.8)Finally, datasets may contain users or items that appear more frequently. This afects the distribution of users and items in training and test sets. It is possible to compute and normalize the MAE depending on users or items (instead of the overall number of ratings).

  i ⊂R i (r u,i -ru,i ) 2 (A.11) B.3. TYPES OF BLOOM FILTERS frequency vector representations.

Table 1 :

 1 4. L'INTÉRÊT IMPLICITE DES UTILISATEURS DANS LES ATTRIBUTS DES ITEMS Résultats de nos expérimentations en termes de précision et quantité de noueds utilisés.

	Technique	RMSE	Quantité de noueds (b)
	ALS	0.79603	1
	Sous-dimension DSGD	0.77571	1
	Dimension ŕexible DSGD	0.77571	1
	Dimension supérieure DSGD	0.77571	1
	Sous-dimension DSGD	0.77611	2
	Dimension ŕexible DSGD	0.77555	2
	Dimension supérieure DSGD	0.77559	2
	Sous-dimension DSGD	0.77626	5
	Dimension ŕexible DSGD	0.77617	5
	Dimension supérieure DSGD	0.77597	5
	Sous-dimension DSGD	0.77586	7
	Dimension ŕexible DSGD	0.77548	7
	Dimension supérieure DSGD	0.77565	7
	Sous-dimension DSGD	0.77593	15
	Dimension ŕexible DSGD	0.77596	15
	Dimension supérieure DSGD	0.77555	15

•

  Nous avons utilisé une technique d'apprentissage actif basé sur les arbres de décision pour faire face au problème de démarrage à froid dans le contexte d'un nouvel utilisa-Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Flexible Distributed Stochastic Gradient Descent . . . . . . . . . . . . . . . 3.5 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Precision and Recall metrics comparisons regarding a top-20 items. . . . . . 4.6 F-Measures for top 20 items. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 ILS metric comparisons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Vector Similarity Model versus Bloom Filter Similarity Model. One item is represented by one vector/őlter. Items' similarities are computed by using these vectors/őlters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	LIST OF FIGURES LIST OF FIGURES
	teur. Cette technique permet d'améliorer les questionnaires présentés aux nouveaux utilisateurs en posant des questions plus pertinentes. De plus, elle permet de plus rapidement capter les préférences de cet utilisateur (une faible quantité de questions seraient posées). 7 Conclusions and Perspectives 7.1 Bibliography Annexes 5.11 Accuracy of the Bloom Filter Similarity Model against the Vector Similarity Model. This similarity uses the XNOR operation. . . . . . . . . . . . . . . . 6.1 Passive and Active Learning pipelines [Rubens et al., 2011]. . . . . . . . . . 6.3 Illustration of our approach and comparison to the state of the art. . . . . . 6.4 Prediction techniques and average comparisons regarding the RMSE. . . . . 6.5 Questionnaire performance in RMSE. . . . . . . . . . . . . . . . . . . . . . . 6.6 Questionnaire performance in RMSE. . . . . . . . . . . . . . . . . . . . . . . B.1 Example of bloom őlter. Initially the bloom őlter is empty (bits set to "0"). Elements X, Y are inserted by hashing them and by setting adequate bits to "1". One membership query for element X returns true, while for a non-inserted element Z returns false. . . . . . . . . . . . . . . . . . . . . . 4.5 5.8 Trade-Ofs for a Bloom Similarity Model. . . . . . . . . . . . . . . . . . . . 6.2 Example of candidate items and close-form show to users. . . . . . . . . . . Chapter 1
	5.9 Bloom Filter (m=7000, k=3). Trade-Of for a Bloom Similarity Model. . . .
	5.10 Accuracy of the Bloom Filter Similarity Model against the Vector Similarity
	Model. Bloom Filters with fewer false positive values achieve better accuracy
	in tops comparisons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Les perspectives qui se présentent sont variées. Nous voulons continuer ces travaux pour analyser et étudier les systèmes de recommandation dans une logique explicative (comment expliquer aux utilisateur la pertinence des recommandations proposées), de compromis d'exploration et d'exploitation (côté recherche et découverte des intérêts d'un utilisateur, versus, côté sur-exploitation de la donnée et monotonie dans les recommandations) dans un contexte de grand hétérogénéité de données, et des nouvelles techniques d'apprentissage actif pour le problème de démarrage à froid tel qu'une analyse du temps de réponse des utilisateurs aux questions posées dans le questionnaire. 1 Introduction and Motivation 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Deőnition and process of recommender systems . . . . . . . . . . . . . . . . 1.3 Challenges in Recommender Systems . . . . . . . . . . . . . . . . . . . . . . 1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Recommender Systems: State of the Art 2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Techniques and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Recommender Systems in the Academy . . . . . . . . . . . . . . . . . . . . . 2.4 Recommender Systems in the Industry . . . . . . . . . . . . . . . . . . . . . 2.5 Recommender System's Libraries . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Analysis of the Parallelization of Matrix Factorization techniques 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS 3.2 4 The implicit interest of users in the attributes of items 4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Architecture of our approach . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Experimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Coping with large vector representations of users and items in very large datasets. 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Bloom Filter Similarity Model . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Active Learning to Cope with New User Cold-Start 6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Related Work in Active Learning . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Background and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Active Learning Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Experimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CONTENTS 6.6 A Evaluating the performance of Recommender Systems A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Prediction oriented evaluations . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Ranking oriented evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Content oriented evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . B Bloom Filters B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Deőnition and properties of Bloom Filters . . . . . . . . . . . . . . . . . . . B.3 Types of Bloom Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Glossaire

List of Figures

1 Représentation et exemple de la simitlarité "AND" en utilisant un modèle de őltres de bloom. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Représentation et exemple de la simitlarité "XNOR" en utilisant un modèle de őltres de bloom. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Example of recommendation workŕow. . . . . . . . . . . . . . . . . . . . . . 2.1 Collaborative Filtering matching process . . . . . . . . . . . . . . . . . . . . 2.2 Matrix factorization of R (users, items, ratings) into P (users, features) and Q (items, features). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Alternating Least Squares technique. Methodology and scalability. . . . . . 3.2 Stratiőcation and Block decomposition. Blocks 1,5,9 do not share rows neither columns, thus, they form a stratum to run in parallel. Once computed, another stratum (2,6,7 or 3,4,8) can run. Single iteration. . . . . . . . . . . 3.3 Diving the matrix R into independent blocks per stratum . . . . . . . . . . 3.4 Block Stratum Assignment technique. . . . . . . . . . . . . . . . . . . . . . 4.1 Global architecture of the recommender system. . . . . . . . . . . . . . . . . 4.2 Semantic Dataset: input approach . . . . . . . . . . . . . . . . . . . . . . . 4.3 Semantic top-K: output approach . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Experimentation: Recommended Top-10 movies for user 6757. Visual comparison. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 AND intersection of two bloom őlters. BF A contains two inserted elements: X1 and X3.BF B contains two inserted elements: X2 and X3. Thus, the intersected őlter contains only one inserted element: X3. . . . . . . . . . . . . 5.3 Negation of a Bloom Filter (BF). Element X1 is inserted in BF A . Elements X2 and X3 are not inserted in BF A . The negation of BF A , BF A , contains the element X2 and does not contain the element X1. Yet, X3 is not inserted because it shares a bit with an element which is inserted in BF A . . . . . . . 5.4 XNOR intersection of two bloom őlters BF A and BF B . BF A contains two inserted elements: X1 and X3. BF B contains other two inserted elements:

X2 and X3. Thus, the XNOR operation will result in common inserted elements and common non-inserted elements: X3 and X4. . . . . . . . . . . 5.5 Representation of how the XOR and XNOR operations can be extracted from AND and OR operations. . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Evolution of the false positive under diferent settings k, m. The number of insertions is őxed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Degree of Similarity of the item 3246 with several items. Bloom Filter (n=237, fp=0.001) has been reconstructed into a vector of size N . . . . . . .

Table 2 .

 2 1: Recommendation's techniques. Main classiőcation and properties.

	Technique	Classiőcation	Advantage	Disadvantage
	Collaborative Filtering	Social-based	Domain independence	Sparsity
				Cold-start
	Content-based	Content-based	User independence	Overspecialisation
	Context-Aware	Context-based	Items reduction	Complexity
	Demographic	Social-based	Light storage	Poor quality
		Context-based	Domain independence
	Knowledge-based	Content-Based Accurate users' adaptation	Complexity
		Context-based		Overspecialisation
	Social Networks	Social-based	Particular niches	Complexity
	Hybrids	Hybrid	Overcome shortcomings	Complexity
				More information
	taken into consideration.

Table 2

 2

.1 gives a brief summary of all techniques.

  Service Providers: Last.fm, Pandora and Spotify Last.fm 8 uses collaborative őltering approaches. It creates a "station" of recommended songs by (1) observing what bands and individual tracks the user has listened to on a regular basis and (2) comparing those against the listening behavior of other users. It RECOMMENDER SYSTEMS IN THE INDUSTRY plays tracks that do not appear in the user's library, but are often played by other users with similar interests. Pandora 9 , on the contrary, uses content-based techniques to create "stations", which contain songs with similar attributes [Tingle et al., 2010]. It allows positive and negative feedbacks to reőne songs in stations. For further details about these recommender systems, readers can read "Pandora and Last.fm: Nature vs. Nurture in Music Recommenders" 10 . Spotify ofers diferent levels of recommendations as well, e.g. songs and other users' songs' lists. They use a content based recommender system 11 . Unlike from other engines,

	4 Conference	Hadoop	World	2011.	http://www.slideshare.net/cloudera/
	2-abhishek-gupta-linkedin-leveraging-hadoop-to-transform-raw-data-into-rich-features-at-linked-in-final

5 https://lucene.apache.org/core/ 2.4. Spotify uses deep learning techniques based on neural networks to generate recommendations [van den Oord et al., 2013].

  Myrrix 19 and Oryx 20 . Myrrix is a full-stack recommender system, which extends 2.5. RECOMMENDER SYSTEM'S LIBRARIES and improves Mahout to create a scalable recommender system using Hadoop MapReduce.

	This project is őnished and was replaced by Oryx, which has enhanced it and adapted to
	Apache Spark distribution paradigms.
	Another younger (2012) but promising library is MLib 21 , which is part of Apache Spark
	and is easy to deploy in Hadoop architectures as well. It implements a matrix factorization
	approach based on alternating minimization called Alternating Least Squares (ALS), and
	this library is growing by implementing more and more algorithms.

14

, which mainly focused on several collaborative őltering approaches in non-distributed environments. This project has evolved inside Apache Mahout by implementing new techniques, such as item based collaborative őltering and matrix factorization approaches. On the other hand, Taste was designed to be run in single machines, although the need to parallelize the data and analysis of recommendation techniques very rapidly arises. Thus, Apache Mahout ofers a scalable architecture to perform parallelized analysis on top of Hadoop MapReduce 15 . Currently, it is being adapted to other architectures, like Apache Spark 16 , H2O 17 and Flink 18 . For further details about these architectures and their performance in large datasets, readers can refer to

[START_REF] Gopalani | [END_REF] Arora, 2015, Liu, 2015]

.

There are two recent open source recommender systems which are based on Mahout's libraries:

GraphLab

[START_REF] Low | Graphlab: A new framework for parallel machine learning[END_REF]

is a graph based framework for distributed machinelearning, powered by the open source project PowerGraph

[START_REF] Gonzalez | Powergraph: Distributed graph-parallel computation on natural graphs[END_REF]

. It has recently evolved to GraphLab Create in the environment Dato 22 . This library has became proprietary in order to sell services and solutions.

  libraries allow to build a recommender application and to evaluate new recommendation algorithms as well. The strongest point of this libraries is its community of researchers, since it has collaborated with other GroupLens Research projects.

	2.6. DISCUSSIONS
	MyMediaLite 26
	Other libraries simply implement the current state of the art of recommendation tech-
	niques. PREA 25 [Lee et al., 2012] ofers several collaborative őltering methods whereas

Table 2 .

 2 this chapter we have explained the assumptions and techniques behind recommender systems. On the one hand, the most popular methods are collaborative őltering and content based. The former relies on the relations among users and users' interest in the past to generate recommendations. It is easily scalable but it does not exploit the items' 2: Recommender System Libraries. Table updated on June 10th, 2016.

	2.6. DISCUSSIONS
	Library	Recommendation techniques	Language	Last updated
	Apache Mahout	Similarity-based CF	Java
		Model-based CF (Matrix Factorization)
	MLib	ALS Matrix Factorization	Scala/Java
	GraphLab Create / Dato Item Similarity-based CF	Python/C++
		Model-based CF (Matrix Factorization)
		Popularity based algorithms
	RecommenderLab	Similarity-based CF	R
		Simple SVD Factorization
	LensKit	Similarity-based CF	Java
		Matrix Factorization
		Slope-One
	MyMediaLite	Collaborative őltering	C#/Mono
	CARS-Kit	Context aware	Java
	PREA	Similarity-based CF	Java
		Matrix Factorization
	EasyRec	Item-based CF	Java
	Colő	Similarity-based CF	Java
	Vogoo	Item-based CF	PHP
	Wales	Collaborative őltering	C++
	SVDFeature	Model-based CF (Matrix Factorization) C++
	Crab	Component to create RS	Python	-Inactive
	MyMedia	Collaborative őltering	C#
		Social Networks based őlters
	Duine	User-based CF	Java	-Inactive
		Content-based
	Carleton	Similarity-based	Java	-Inactive
		Simple SVD Factorization
		Association rules
	Coő	CF techniques	Java	-Inactive
	descriptions to better adapt recommendations. The latter recommends similar items to
	the ones the current user liked in the past. The heterogeneous data sources increase
	the complexity of these approaches. In addition, recommendations tend to sufer from
	overspecialisation (very similar items are always recommended to the users). A third
	very important category are the hybrid recommendations, which combine two or more
	techniques to alleviate the drawbacks and enhance the accuracy of recommendations.
	Both academy and industry have invested their eforts in the recommendation őeld. One
	of the most important contributions is the matrix factorization technique, which appeared

during the Netŕix price and which has helped researches to overcome with scalability and accuracy issues. Currently, it is considered as the baseline state of the art in collaborative better performance in Hadoop clusters, (2) the implicit interest of users in the items' descriptions and how this can be softly used in collaborative őltering techniques, (3) the items' and users' representations in very large data contexts, and (

Table 3 .

 3 1: Experimentation results.

	Technique	RMSE	Time (min)	Number of nodes (b) Rows Columns
	ALS	0.79603	3.019	1	=	=
	Under DSGD	0.77571	1.303	1	=	=
	Flex DSGD	0.77571	1.303	1	=	=
	Upper DSGD	0.77571	1.303	1	=	=
	Under DSGD	0.77611	1.850	2	=	-1
	Flex DSGD	0.77555	1.852	2	=	+1
	Upper DSGD	0.77559	1.885	2	=	+1
	Under DSGD	0.77626	5.518	5	-3	-2
	Flex DSGD	0.77617	5.524	5	+2	-2
	Upper DSGD	0.77597	5.525	5	+2	+3
	Under DSGD	0.77586	8.978	7	-4	-6
	Flex DSGD	0.77548	8.985	7	+3	+1
	Upper DSGD	0.77565	9.024	7	+3	+1
	Under DSGD	0.77593	28.506	15	-8	-2
	Flex DSGD	0.77596	28.526	15	+7	-2
	Upper DSGD	0.77555	28.536	15	+7	+13

Table 4 .

 4 5: Example. Top-3 recommendations for the user "1"

	Top-3	Movie 21 Movie 10 Movie 64
	Predicted Rating	5	4.5	4
	4.3.2.4 Example
	Again, we use Tables 4.2, 4.3 and 4.4 to represent our dataset example. In addition, we
	use Table

  , which merges ratings in MovieLens dataset 1 and movies' attributes in IMDb 2 database. The

	dataset is composed of 2113 users, 10197 items and 855598 ratings within a scale of 1-5. It
	ofers six attributes: genre, directors, actors, countries, locations and tags. It has 112881
	diferent attributes' values (i.e. features): 20 movie genres, 95321 actors, 72 countries,
	4266 locations and 13222 tags.

Table 4 .

 4 6: Experimentation: Weights % for variables in dimensions. Approximate values.

	Variables	actor	country director genre location total
	Dimension D 1 19.537 12.719	19.896	0.000 5.064	57,25
	Dimension D 2 4.785	8.3732	5.303	6.459 17.823	42.75
	Total (%)	24	21	25	6	23	100
	4.4.1.2 Counting Bloom Filter

Table 5

 5

		.1: Notation used for bloom őlters
	Notation Description
	BF	Bloom Filter
	n	Number of expected insertions
	m	Size in bits
	k	Number of hash functions
	fp	false positive

Table 5 .

 5 2: Optimal Bloom Filters.

	Bloom Filter n max	fp	k	m
	bloom 0.2	237	0.2	3	794
	bloom 0.1	237	0.1	4 1136
	bloom 0.01	237	0.01	7 2272
	bloom 0.001	237 0.001 10 3408

Table 5 .

 5 3: Non Optimal Bloom Filters.

	Bloom Filter	n max	fp	k	m
	bloom M3000K3 237	0.01	3
	bloom M3000K4 237	0.005	4
	bloom M7000K3 237	0.001	3
	bloom M7000K4 237 0.00026 4

Table 5 .

 5 4: Vector and Bloom Models trade-ofs.

	Item Representation	VM OPM NOPM
	Size (bits)	104957	3408	7000
	Hash Functions	-	10	3
	Building model (sec)	6.58	8.94	8.32
	AND Similarity (ms)	-	0.001	0.003
	XNOR Similarity (ms)	-	0.004	0.006
	Reconstruction (ms)	-127.28 141.27
	Jaccard Similarity (ms)	0.4	2.6	2.3
	vector and bloom models under the same conditions and similarities. Reconstruction time
	is given by the features loading (140 ms) and the features hashing (145 ms), which are
	performed only once. Then, a single vector reconstruction is created by querying őlters.

  The next chapter (Chapter 6) focuses on the cold-start challenge in recommender systems. Particularly, we focus on collaborative őltering techniques only, which do not exploit the items' and/or users' descriptions.

	Chapter 6
	Active Learning to Cope with New
	User Cold-Start
	"A man must be big enough to admit his mistakes, smart enough to proőt from them,
	and strong enough to correct them."
	-John C. Maxwell
	One paper derived from this chapter has been submitted to ICDM 2016: "Enhancing
	New User Cold-Start based on Decision Trees Active Learning by Using Past Warm-Users
	Predictions"; Manuel Pozo, Raja Chiky, Elisabeth Métais and Farid Meziane. Acceptance
	Notiőcation on September 9th.

Table 6

 6

		.1: Notation used in decision trees.
	Notation Description
	R	Set of ratings
	P	Set of predictions
	u	User
	i	Item
	r u,i	Rating of user u in item i
	p u,i	Predicted rating of user u in item i
	t	Current node of the tree
	R t	Set of ratings in node t
	P t	Set of predictions in node t
	U t	Set of users in node t
	I t	Set of items in node t
	R t (u)	Set of user's ratings in node t
	R t (i)	Set of item's ratings in node t
	P t (u)	Set of user's predictions in node t
	P t (i)

Table 6 .

 6 2: Statistics for available ratings and matrix factorization predictions. MF1 and MF2 denote predictions over Movielens 1M and Movielens 10M, respectively.

	6.4. ACTIVE LEARNING DECISION TREES
	Statistic	MovieLens 1M MF1 MovieLens 10M MF2
	1st Quartile	3.00	3.18	3.00	3.13
	Median	4.00	3.66	4.00	3.58
	Mean	3.58	3.58	3.51	3.51
	3rd Quartile	4.00	4.05	4.00	3.96

  6.4. ACTIVE LEARNING DECISION TREESAlgorithm 5 Non-supervised decision tree algorithm 1: function BuildDecisionTree(R t , P t , currentTreeLevel )

	2:	for rating r u,i in R t do
	3:	accumulate statistics for i in node t using p u,i
	4:	end for
	5:	for candidate item j in I t do
	6:	for r u,j in R t (j) do
	7:	obtain P t (u)
	8:	split U t into 3 child nodes based on j
	9:	őnd the child node where u has moved into
	10:	for rating p u,i in P t (u) do
	11:	accumulate statistics for i in node t -child using p u,i
	12:	end for
	13:	end for
	14:
	16:	end for
	17: discriminative item i 24: end for
	25:	end if
	26:

derive statistics for j in node tU from the tL and tD statistics 15:

candidate error: e t (j) = e tL (j) + e tD (j) + e tU (j) * = argmin i e t (i) 18: compute p i * by using item prediction average 19: if currentTreeLevel < maxTreeLevel then 20: create 3 child nodes U t-child based on i * ratings 21: for child in child nodes do 22: exclude i * from R t-child

23:

BuildDecisionTree( R t-child , P t-child , currentTreeLevel +1 )

  The complexity of splitting the users in node t As a consequence, the complexity to build a tree of N questions is O(N ∑ Supervised decision tree algorithm 1: function BuildDecisionTree(U t , R t-train , R t-validation , P t , currentTreeLevel )

	6.4. ACTIVE LEARNING DECISION TREES
	Algorithm 6 2: for user u ∈ U t do 3: compute RM SE 1 u on R t-validation (u) and P t (u)
	4:	end for
	5:	for candidate item j from R t-train do
	6:		split U t into 3 child nodes based on j
	7:		for user u ∈ U t do
	8:		őnd the child node where u has moved into
	9: 10:		compute RM SE 2 u on R t-validation (u) and P t (u) △ u,i = RM SE 1 u -RM SE 2 u
	11:		end for
	12:	end for
	13: 14: discriminative item i 21: δ = aggregate all △ u,i end for
	22:	end if
	23:
		is O(	∑

u∈Ut |R t (u)| 2 ), and thus, for all the nodes in the same level we use O(

∑ u∈U |R(u)| 2 ). u∈U |R(u)| 2 ). * = argmax i δ i 15:

compute p i * by using item prediction average 16: if currentTreeLevel < maxTreeLevel and △ i * ≥ 0 then 17: create 3 child nodes U t-child based on based on i * ratings 18:

for child in child nodes do 19:

exclude i * from R t-child 20:

BuildDecisionTree( U t-child , R t-child-train , R t-child-validation , P t-child , cur-rentTreeLevel +1 )

Table 6 .

 6 3: Properties of diferent movie datasets.

	6.5. EXPERIMENTATION
	Property MovieLens1M MovieLens10M	Netŕix
	Users	6040	71567	480000
	Items	3900	10681	17000
	Ratings	1 million	10 millions	100 millions
	Sparsity	0,042%	1,308%	1,225%
	Scale	Integer 1-5	1-5 by 0.5	Integer 1-5

  splits the datasets into 90% training set, D train and 10% test set, D test . However, this is not a real cold-start context since the same user may appear in both training and test set. We suggest a real cold-start situation. We split the set of users in the datasets into 90% training set, U train and 10% test set, U test . Hence, the users in the training set help to build the decision trees and the users in the test set are considered as new user to evaluate the performance of the approach.

Table A .

 A 1: Notation used in the evaluation metrics for recommender systems.

	Notation Description
	R	Set of ratings
	|R|	Number of ratings
	U	Set of users
	|U |	Number of users
	u	particular user
	I	Set of items
	|I|	Number of items
	i	particular item
	r u, *	Set of user's ratings
	r * ,i

http://www.economist.com/node/8312260

http://grouplens.org/datasets/movielens/

L'équation sémantique peut être appliquée à deux niveaux dans la recommandation. D'une part, nous pouvons appliquer cette équation à toutes les notes disponibles dans la base de données initiale, ce qui permet de mieux expliquer l'intérêt des utilisateurs pour les caractéristiques déőnissant les items notés (ajouter du sens à la note). D'autre part, nous pouvons faire le choix d'appliquer l'équation sémantique à la sortie de la recommandation.Supposons que le module de recommandation renvoie un résultat des top K items (les K items les plus pertinents) pour un utilisateur donné, avec une estimation de la note pour ces top K. Ces notes seront transformées en une note sémantique suivant l'équation précédente et les items proposés seront réordonnés en conséquence en top K', K' pouvant être inférieur ou égal à K.Enőn, le module de recommandation utilise une technique de őltrage collaboratif basée sur une méthode de factorisation de la matrice pour générer des recommandations précises.

http://www.economist.com/node/8312260

http://ucsdnews.ucsd.edu/pressrelease/u.s._media_consumption_to_rise_to_15.5_hours_a_ day_per_person_by_2015

http://www.fiora.pro

https://www.mycoachnutrition.com

http://grouplens.org/datasets/movielens/

http://imdb.com

1.4. MOTIVATION

http://www.merriam-webster.com/dictionary/influence

Recommender Systems Conference at CNAM, Mars 2015. http://www.lesoffrescanal.fr/ service-canal-plus/eureka-idee-film

www.linkedin.com

Recommender Systems Conference at CNAM, Mars 2014. https://www.mendeley.com

Facebook help system. https://www.facebook.com/help/www/501283333222485

http://www.last.fm

http://www.pandora.com/restricted

http://blog.stevekrause.org/2006/01/pandora-and-lastfm-nature-vs-nurture-in.html

Blog of Spotify Developer, August 2015. http://benanne.github.io/2014/08/05/spotify-cnns. html

Student Research Study for Yelp.com. http://www.math.uci.edu/icamp/summer/research/student_ research/recommender_systems_slides.pdf

F. Meyer working at Orange Labs -Recommender Systems Conference at CNAM, Mars 2014.

http://incubator.apache.org/ip-clearance/mahout-taste.html

http://hadoop.apache.org

https://spark.apache.org

Artificial Intelligence. http://www.h2o.ai

Distributed stream flows and batch data processing. https://flink.apache.org

https://github.com/myrrix/myrrix-recommender

Cloudera Oryx Project. GitHub. https://github.com/cloudera/oryx

https://spark.apache.org/mllib/

Machine learning and predictive services in a graph scalable platform. https://dato.com

http://easyrec.org/

http://lenskit.grouplens.org/

http://prea.gatech.edu/

http://mymedialite.net

http://www.cs.carleton.edu/cs_comps/0607/recommend/recommender/index.html

http://sirius.cs.put.poznan.pl/~inf59829/vogoo/docs/MANUAL.html

http://savannah.nongnu.org/projects/cofi/

http://svdfeature.apexlab.org/wiki/Main_Page

This framework and site are no longer available. http://duineframework.org

http://muricoca.github.io/crab/

see http://ufldl.stanford.edu/tutorial/supervised/OptimizationStochasticGradientDescent/ for further details.

We consider that processors do not directly share memory.

http://grouplens.org/datasets/movielens/

https://mahout.apache.org

http://grouplens.org/datasets/movielens

http://www.imdb.com/

https://mahout.apache.org

Denote that, since the convergence of the collaborative filtering has been already proved and the semantic approaches do not modify this convergence capability, we do not need a cross-validation set.

We use typical vector definition. Highlight that sparse map implementation of vectors may reduce space complexity, yet it increases programming and time complexity in terms of vector similarities.

http://grouplens.org/datasets/movielens/

www.fiora.pro

http://grouplens.org/datasets/movielens/

www.mycoachnutrition.com/

B.3. TYPES OF BLOOM FILTERS

Acknowledgments

ACKNOWLEDGMENTS

(r ui -q T i p u ) 2 + λ(∥ q i ∥ 2 + ∥ p u ∥ 2 ) (2.1)

Matrix factorization has been considered a core-stone and it has been used by many authors in literature. For instance, [START_REF] Takács | Alternating least squares for personalized ranking[END_REF] propose a ranking-based prediction by minimizing a ranking based objective function instead of the user's rating prediction oriented function. [START_REF] Hu | Collaborative őltering for implicit feedback datasets[END_REF] has modiőed matrix factorization to exploit the implicit interest of users in items rather that the users' ratings. They build a binary like-dislike sparsity matrix from an implicit dataset. [START_REF] Koren | Advances in collaborative őltering[END_REF] suggest similar and enhanced techniques based on matrix factorization. More details of these techniques are given in Chapter 3.

On the other hand, a very famous memory based technique is SlopeOne [START_REF] Lemire | Slope one predictors for online rating-based collaborative őltering[END_REF]. This item-based collaborative őltering technique suggests to model users' ratings within a slope function. It takes into account users' ratings in items and the ratings received by items to favour the recommendation of popular items. This technique is fast to update and it is resistant to cold start. Other variations consider the high co-rated items [START_REF] Lemire | Slope one predictors for online rating-based collaborative őltering[END_REF], the bi-polar ("like", "dislike") approaches [START_REF] Lemire | Slope one predictors for online rating-based collaborative őltering[END_REF], the integration of clustering techniques to improve users' correlations [START_REF] Mi | A recommendation algorithm combining clustering method and slope one scheme[END_REF], and apply users' trustiness and items' recommendation usefulness to enhance recommendations [START_REF] Menezes | Weighted slope one predictors revisited[END_REF].

Other collaborative őltering techniques focus on diferent challenges, such as sparsity.

[ [START_REF] Wang | Unifying userbased and item-based collaborative őltering approaches by similarity fusion[END_REF]] suggest a memory-based technique rather than performing users' ratings or items' ratings aggregations to perform users/items similarities, they mix both and they create the rating-based similarity. For a given prediction, both users and items aggregations are used together. [START_REF] Massa | Trust-aware collaborative őltering for recommender systems[END_REF] claims that in large datasets it is diicult to őnd users who rate the same items with similar ratings. They propose to create a trustiness-graph based on users' ratings and users' connections to increase the number of comparable users.

Some authors focus on these user-user connections and claim that enhancing the seek who has rated N u = 4 movies: Secondly, we get the weight for attributes computed by the feature principle component analysis (e.g. W 1 = 0.4 and W 2 = 0.6 for genres and actors respectively). The third step is to get the implicit occurrences stored in the counting bloom őlter:

• The user 1 has rated the items 1, 2, 3 and 4, and these items have actors and genres.

• Focus on the item 1 and its genres: comedy and fantasy. The movies 2 and 4 already rated by user 1 are comedies. Besides, the movie 4 is also a fantasy movie. Hence, the occurrences count is C 1 = 3.

• Focus on the item 1 and its actors: actor 1 and actor 3. The actor 1 also appears on movies 2 and 4. Thus, the occurrences count in this attribute is C 2 = 2, because the actor 3 does not appear on any other movie.

Putting everything into Equation 4.1, we obtain the new "semantic rating":

Collaborative őltering are good techniques to guess the interest of users in items. However, recommender systems usually present a top-K items to users. This top-K is typically ordered by the predicted interest value for users, hence the őrst item is likely preferred to the second one, etc. The user is free to pick up any of these K items. Our approach in this context aims to re-order this top-K (and eventually make new items appear) to present őrst the items containing the most relevant features for the user. As a result, by using the semantic module at the output (i.e. predictions) of the recommender system we adapt the recommendations to users based on his implicit feedback in the features of items.

RELATED WORK IN ACTIVE LEARNING

• Optimization. The system selects the items from whose new feedbacks may improve a prediction error rate, such as MAE or RMSE. Indeed, this is a very important aspect in recommender systems since error reduction is directly related to users' satisfaction [START_REF] Rubens | Active learning in recommender systems[END_REF]. Other strategies may focus on the inŕuence of queried item evaluations (inŕuence based [START_REF] Rubens | Inŕuence-based collaborative active learning[END_REF]), the user partitioning generated by these evaluations (user clustering [START_REF] Rashid | Learning preferences of new users in recommender systems: an information theoretic approach[END_REF],

decision trees [START_REF] Golbandi | On bootstrapping recommender systems[END_REF]) or simply analyse the impact of the given rating for future predictions (impact analysis [START_REF] Mello | Active learning driven by rating impact analysis[END_REF]).

Three very well known non-personalized and batch-oriented strategies are: (1) En-tropy0 relaxes the entropy constraints by supposing that unknown ratings are ratings equal to '0' (changing a 1-5 rating scale to 0-5 rating scale), hence a high frequency of '0' tends to decrease the entropy, ( 2) "LPE" (Logarithmic Popularity Entropy) chooses candidate items regarding their popularity and rating entropy [START_REF] Rashid | Getting to know you: learning new user preferences in recommender systems[END_REF], and

(3) "HELF" (Harmonic Entropy Logarithmic Frequency) balances the entropy of candidate items against the frequency of rating repetitions [START_REF] Rashid | Learning preferences of new users in recommender systems: an information theoretic approach[END_REF]. However, the need of personalization in questionnaires has changed batch-oriented into sequential-oriented based questionnaires. This evolution is shown in the works: [Karimi et al., 2011a[START_REF] Karimi | Non-myopic active learning for recommender systems based on matrix factorization[END_REF][START_REF] Karimi | Towards optimal active learning for matrix factorization in recommender systems[END_REF]] [Karimi et al., 2012] [Karimi, 2014]. Within these papers, the authors have explained the importance of rapid online questionnaires and the ratability factor over candidate items in order to capture the users preferences. In the next section we focus on personalized questionnaires only.

Active Learning for Collaborative Filtering

The őrst appearance of active learning for new users cold-start was in [START_REF] Kohrs | Improving collaborative őltering for new users by smart object selection[END_REF], although the őrst step for creating sequential personalized questionnaires was suggested in [START_REF] Harpale | Personalized active learning for collaborative őltering[END_REF]. In this paper, the authors enhance a similar approach in [Jin and Si, 2004] by assuming that users may do not be able to rate presented items and thus relaxing initial assumptions. They suggest a probabilistic collaborative őltering that uses bayesian networks to learn the candidate items entropy. The candidate items are presented sequentially and the whole model is re-adjusted according to past

Background and Notation

The goal of decision trees in active learning is to split the users' population in groups of users' preferences. Thus, the users within the same tree's node tend to share similar preferences. By going deeper inside the tree, these groups are reőned and preferences are better detected. These techniques in a collaborative őltering context have only access to the available users/items feedback, i.e. ratings. As a consequence, they aim to őnd out the discriminative items that, in each node of the tree, eiciently split the users' population depending on the users' feedback to these items.

This idea is very useful to cope with the new users cold start. One node is represented by one question about the discriminative item, e.g. 'Do you like this movie?'. The answers are the possible feedback of the new user to this item, e.g. 'like', 'dislike' and 'unknown'. Every answer leads to a diferent question. Therefore, when new users őll-out the questionnaire, they are indeed following a personalized path which tries to detect to which group of users' preferences they match the best.

In this chapter we will use the following notation for active learning using decision trees algorithms. Formally, let R be the available ratings. The rating of a user u in an item i is deőned by r u,i ∈ R. In addition, let t be a node in the decision trees. We deőne U t , I t , and R t as the set of (warm) users, items and ratings currently in the node t. Furthermore, R t (u) and R t (i) are ratings of the user u and item i in the node t. In addition, our main contribution exploits the predictions over the existing R. Thus, we deőne P as the predicted set of R, so that for each r u,i ∈ R there is a prediction p u,i ∈ P . The set P is computed by using collaborative őltering techniques, e.g matrix factorization. Highlight that the number of users, items, and entries in R and P are the same. Particularly, we do not aim to predict sparse values or not known ratings from all possibles entry combinations of U t , I t . Finally, P t is the set of predictions currently in the node t, and P t (u) and P t (i) are the set of users and items predictions in the node t. Table 6.1 resumes these notations.

needed in decision trees are item-oriented regardless of the user (the same item prediction value to any user) rather than user-item oriented (items' predictions depend on users' interests).

We propose to change this paradigm by using more accurate predictions over the available ratings R. The main idea is to introduce the prediction P as a new source of useful data. Hence, R and P are available from the root node of the tree. Then, when the node

As long as we want to preserve that for every rating r u,i ∈ R t there is an associated prediction p u,i ∈ P t , for every node t we split P t into P t-child as well. This idea is illustrated in Figure 6.3. In addition, we propose to use the available ratings in R only to split the users population, and P to őnd out the best discriminative items to enhance the prediction label of candidate items.

This makes sense since őnding discriminative items and label predictions are associated with computing an error. As long as P is built by using more accurate methods than the "item rating average", this error is minimized eiciently. We propose using eicient algorithms, such as matrix factorization [START_REF] Zhou | Large-scale parallel collaborative őltering for the netŕix prize[END_REF]. The main drawback of using matrix factorization is that it computes diferent item predictions for diferent users. The decision trees require a unique item prediction value to be applied to any user. In [START_REF] Golbandi | Adaptive bootstrapping of recommender systems using decision trees[END_REF], Karimi et al., 2015b] the authors use the "item rating average" within R t .

We suggest using a similar method, with a major diference that is computing the "item prediction average", which is indeed the average of the predictions within P t .

Collaborative őltering methods are very accurate for recommending items to users by replicating the users' rating behavior. As a consequence, they are good as well in guessing the average prediction of users, items, and in general the average rating value of the dataset.

We illustrate this by using a real use-case. We perform the matrix factorization (MF)

predictions over the Movielens 1M dataset in Table 6.3 to obtain the predicted values P for R. Table 6.2 summarizes statistics over R and P . One can see how close the statistic values such as the mean and quartiles between the available ratings and the predicted ratings are.

In addition, we want to go further by considering diferent users' populations. We compare the performance of three diferent predictors: (1) the item rating average (Item-Avg), "Karimi" chose these experimentation settings in order to publish and compare results using the pre-deőned D train and D test Netŕix dataset. In addition, we consider that picking up 25% of users the for test set, U test is concerned with the posteriori search of R answer and R perf ormance . The more users in the test set the more probability to pick up ratings from D train and D test for R answer and R perf ormance , respectively. Thus, more test points are possible possible to use.

We simplify the setting above. The process we have followed in the Movielens datasets is as follows. We split the dataset into 90% user training set, U train and 10% user test set U test , where users in one set are not present in the other. Then, the ratings in U train are split into 90% rating training set, R train , and 10% ratings validation set R validation . The U test is not split into "answer" and "performance" and it is completely used for probing the approach.

We train "Karimi" by using these settings. In addition, we train a modiőcation of "Karimi" to take into account only 3 child nodes, denoted "Karimi 3 childs". Figures 6.6(a) and 6.6(b) show the results (the mean values and tendency curves) of this experimentation for both MovieLens datasets.

On the one hand, one may observe that our approach achieves a lower error (around 1%) in less number of questions; hence we better capture the preferences of new users.

Therefore, our approach still matches with the needs of active learning: short but very informative questionnaires. This is possible due to the higher accuracy of the matrix factorization based predictions. In addition, it is expected to have an asymptotic behavior in large number of questions for both Movielens datasets.

7.1. CONCLUSIONS matrix factorization as the baseline method. In the context of collaborative őltering we were interested in (1) the scalability of techniques and the distribution of them among multiple machines to alleviate the time analysis consumption, (2) discovering the interest of users in the attributes of items and integrate it in such a way that the domain dependency impact is reduced, (3) the representation of items and users through large dimension vectors, and ( 4)

the new user cold start issue in active learning techniques based on collaborative őltering assumptions.

In Chapter 3 we have presented an analysis of the matrix factorization scalability and suggested one technique to distribute the recommendation process among multiple machines in a Hadoop/MapReduce cluster environment. Our matrix factorization technique uses stochastic gradient descent algebra to őnd users' interests and users' predictions. In order to parallelize the process, we decompose the matrix of ratings into blocks. Then, we deőne stratum as sets of blocks which are mutually independent (they do not share common users and items). Stratums can be computed parallely, where all blocks are analyzed by one diferent machine at every time. Our approach avoids the deletion of data compared to the state of the art [START_REF] Makari | Shared-memory and shared-nothing stochastic gradient descent algorithms for matrix completion[END_REF], what slightly improves the recommendation accuracy.

The matrix factorization technique described in Chapter 3, a.k.a. Singular Value Decomposition for Recommender Systems [Funk, 2006], is used in this thesis as a baseline algorithm, for which we aim to perform more improvements. In Chapter 4 we proposed a new source of knowledge which is later exploited by the matrix factorization approach: the implicit interest of users in the attribute of items. In fact, the interest of users is often itemoriented [START_REF] Oard | Implicit feedback for recommender systems[END_REF]], e.g. to rate a book, to watch a movie, to click on a video, etc.

The users' interests in the items' attributes is diicult to capture due to the big quantity of possibilities. Our approach extracts this knowledge from past users' ratings and items'

descriptions. The goal is to integrate it into matrix factorization techniques yet reducing the impact of domain dependency of the system. A few possibilities were discussed, and a layered architecture was chosen for our approach. We propose to transform existing ratings into "semantic ratings" that extends the sense of ratings to denote the interest of users in items and items' attributes. These new semantic ratings are then used in the matrix

PERSPECTIVES

As a consequence, it is possible to separately store and exploit this information. We point out that some attributes' values may appear in both positive and negative sets, as long as, for instance one actor can play on one movie liked by the user and one other movie not liked by the same user. However, since this information is implicit, the number of occurrences in these sets will be diferent. The new goal would be to őnd a new "semantic equation" to take both positive and negative interests into account. Hence, this equation would promote items containing positive implicit users' interest and would refrain the recommendation of negative implicit users' interest.

Large description of users through the items' descriptions

Some research works have proposed the "collaboration via content" [Pazzani, 1999] in which, users are correlated regarding the description of the items they rate, in addition to the typical rating-oriented correlations.

Chapter 4 suggests to extract the implicit interest of users in the items' attributes.

This information is then inserted into bloom őlters to be quickly available. However, in this chapter we have exploited bloom őlters by simply querying it. Specially, we do not perform users' correlations or users' similarities regarding a possible "collaboration via content".

On the other hand, in Chapter 5 the items' and users' bloom őlter representations are useful to alleviate memory-consumption in large users' and items' descriptions. In addition, we proposed the AND and XNOR similarities among items/users. As a consequence, we consider that it can be interesting to merge both ideas in order to perform "collaboration via content" users' similarities by using the bloom őlter representations and bloom őlter similarity measures.

Furthermore, together with the perspective mentioned above, this would explain not only the positive and negative implicit interest of users (e.g. whether a user has special ainity to one actor), but also the positive and negative lack of interest (e.g. if a user has never been in contact with one actor he may like, or if a user has never been in contact with sportive content simply because he is not interested in it and never interacted with it).

Annexes

Appendix A

Evaluating the performance of Recommender Systems

A.1 Introduction

Recommender systems answer to diferent challenges depending on the context and on the goal. For instance, recommendations may need to be suited in terms of attributes, e.g.

to avoid user's allergies in recipes recommendations. As a consequence, there are many method and techniques to evaluate the performance of these systems. In general, one can sum up these techniques into: prediction-oriented, raking-oriented and content-oriented metrics. For further explanations about evaluation metrics in recommender systems please refer to [START_REF] Shani | Evaluating recommendation systems[END_REF] In order to evaluate a recommender system, the most common approach is to split the current dataset into training set and test set 1 . The main idea is to train the recommendation technique using the ratings of users (u) in items (i) within the training set, i.e. r u,i .

The technique identiőes users, items and rating patterns following the recommendation technique assumption, and hence it is possible to predict the users' ratings in items (r u,i ))

which are absent in the training set. On the other hand, the test set contains (normally 2 ) other ratings from same users and items that appear in the training set. As a consequence, by comparing the predictions computed for users and items to the ratings in test set, it is

1 Further dataset's split are possible and sometimes required to validate algorithm's parameters and hyper-parameters.

2 Odd cases and exceptions may appear when users' and/or items' ratings is low.

A.2. PREDICTION ORIENTED EVALUATIONS

A.2.1 MAE: Mean Absolute Error

This method measures the absolute diference between predictions (r u,i )) and observations (r u,i ): e u,i = |r u,i -ru,i |. As a consequence, the lower is this error, the better is the prediction. The measure is computed for the all the ratings in the test set; thus it represents the average of the absolute diference.

Other variances propose to compute the squared root of MAE. In addition, it is possible to deőne a Normalized Mean Absolute Error (NMAE) as the MAE divided by the range of the ratings values.

Finally, datasets may contain users or items that appear more frequently. This afects the distribution of users and items in training and test sets. It is possible to compute and normalize the MAE depending on users or items (instead of the overall number of ratings). In fact, one may compute a user oriented metric (M AE u ) or an item oriented metric (M AE i ), and then normalize by the number of users or items that contributed to this metric.

A.3 Ranking oriented evaluations

Ranking evaluation are related to usefulness of recommendations. They do not predict singular user item ratings, but try to collect and present a set of items of the user's interest.

This set of items are likely to be "consumed" (e.g. visited, watched, etc) by the user in a close future.

The presence of items in this set depends on three factors: the rating prediction value (r u,i ), the size of the set (K), a.k.a. top-K, and the relevancy threshold (r threshold ). The predictions are inherit to the model. The size of the set is a trade-of, short values make short list of items to choose over whether large values make more diicult to the user the decision makings. The relevancy threshold sets whether an item is relevant or not for a given user, and thus whether the item should be or not inserted in the list.

As a result, the rel u,i is a binary value to represent whether an item i is relevant or not for a user u. It is possible compare the item's prediction with user's ratings in the test set.

If the real observed rating in the test is equal or above r threshold , the item i is relevant for the user, and rel u,i = 1, otherwise rel u,i = 0.

A.3.1 Precision, Recall and F-Measures

Precision and Recall evaluates the relevancy of recommendations in terms of probabilities, regarding the top-K items or the users' ratings.

Precision is the probability that an item i in top-K is relevant for the user u over all other items in top-K. The higher the probability is, the better is the precision. An overall value of 1.0 means that every item recommended in top-K is relevant. Yet, it does not say that all relevant information have been suggested.

P recision

The overall precision of the system is given by the users' precision average.

Recall is the probability that an item i in top-K is relevant for the user u over all other users' items ratings. The average value of 1.0 means all the good recommendations are in the top-K, and thus the higher, the better.

The overall recall of the system is given by the users' recall average.

The F-β-measure refers also to the top-K elements. It is the Harmonic Mean of Precision and Recall and it might balance or weight precision and recall values. The weight value is denoted as β. Typically, the F-Measure uses β = 1 in order to equally balance precision and recall.

F -βmeasure@K = (1 + β 2 ) * P recision@K * Recall@K β 2 * P recision@K + Recall@K (A.17)

A.3.2 DCG: Discounted Cumulative Gain

Discounted Cumulative Gain (DCG) measures also the relevancy of items [START_REF] Järvelin | Cumulated gainbased evaluation of ir techniques[END_REF]. This measure takes into account the position of items. It is based on two assumptions: (1) most relevant items should appear higher in the user's top K recommendations since they are more useful for the user, and (2) the relevancy is a marginal factor for irrelevant items. In this measure, the higher, the better. We calculate the overall value for all users U .

Finally, the Normalized Discounted Cumulative Gain (NDCG) is the current status of DCG@K compared to the IdealDCG@K.

N DCG@K = DCG@K IdealDCG@K (A.20)

A.4 Content oriented evaluations

The recommender systems use to suggest users a set of items (top-K) that best suits their interests. Depending on the domain of recommendation, it is interesting to balance the degree of similarity of the items which are recommended to the user. For instance, to recommend very similar movies to one user might bore her. On the contrary, to recommend very diferent movies may confuse her and give the impression of bad recommendations.

This trade-of is called similarity/diversity [START_REF] Su | A survey of collaborative őltering techniques[END_REF].

In addition, users may appreciate as well that recommendation are renew even if they are not consumed. Novelty metrics show the diference between the information presented and the information that usually is presented [START_REF] Castells | Novelty and diversity metrics for recommender systems: choice, discovery and relevance[END_REF].

A.4.1 ILS: Intra-List Similarity

It is also called ILD (Intra-List Diversity). It measures the diversity/similarity of items in top-K [START_REF] Ziegler | Improving recommendation lists through topic diversiőcation[END_REF]. The similarity sim(i, j) between two items i, j depends on the characteristics they share. For instance, two movies of the same genre or belonging to the same saga are considered to be similar. The higher the value is, the more similar the items in the top are.

The global similarity for the system is given by the users' average ILS:

A.4.2 EBN: Entropy-Based Novelty

It measures the quantity of information of K presented items [START_REF] Bellogín | A study of heterogeneity in recommendations for a social music service[END_REF].

This technique sees items as variables with associated probabilities (entropy). We might consider that items have an equal probability of appearance p i = 1/K . Hence, the combination C i of all probabilities generates the global entropy. The higher, the better.

When the probabilities are not equal, the entropy is weighted by these probabilities.

Thus, the global EBN for the system is given by the users' average:

A.4.3 MSI: Normalized Mean Self-Information

This metric evaluates the information novelty between predictions in the top K and known user's preferences R u [START_REF] Zhou | Solving the apparent diversity-accuracy dilemma of recommender systems[END_REF]. The higher, the better.

Thus, the global EBN for the system is given by the users' average:

Bloom Filters

B.1 Introduction

The concept of bloom őlter was őrst introduced by Burton H. Bloom in 1970 [Bloom, 1970]. It has been used in many diferent applications, such as databases queries or computer networks, due to its memory-eiciency and fast-capabilities [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. To the best of our knowledge, this structure has not been used yet in the őeld of recommender systems.

B.2 Definition and properties of Bloom Filters

A bloom őlter is a bit-structure, which represents "n"-elements of the same set "S" in a lower space of "m"-bits [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF]. Initially, the m-bits are set to "0" representing the absence of elements in the őlter. Then, "k"-independent hash functions eiciently distribute the insertion of elements among the bit-structure. This modiőes the status of "k" bits in the structure (one bit for each hash function used). In other words, to insert an element it is hashed to get the "k"-positions of the structure to set to "1".

Bloom őlter structure allows fast membership queries. It works as follows: the requested element is hashed with the "k" hash functions and the "k" resulted indexes are checked in the bit-structure. If any of these indexes is set to "0", the bloom őlter assures that the element has not been inserted. When all indexes are set to "1", one can assume that B.2. DEFINITION AND PROPERTIES OF BLOOM FILTERS

B.2.1 Near Optimal False Positive

As explained above, one may assure that an element has not been inserted in the őlter if any of the associated indexes is set to "0". On the other hand, the probability of a false positive can be estimated. Indeed, the false positive ratio depends on three parameters:

(1) the quantity of expected insertions "n", (2) the size of the bit structure "m", and ( 3) the number of hash functions "k". After all the "n" elements have been inserted, some bits in the structure remain set to "0" but others are set to "1". The probability that a specific bit is still zero is given by Equation B.1 [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF].

Moreover, the probability that a specific bit is set to one is given by q(bit = 1) = 1 -p(bit = 0). Thus, the false positive probability is deőned through this probability and the number of hash functions 1 , as in Equation B.2.

Further eforts to őnd out near-optimal values for the false positive ratio can demonstrate the existence of a global minimum [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF] for "k", k = m • ln2 n . In addition, "m" can be estimated by: m ≥ -n • log 2 (f p) ln2 . Note that in a real application "k", "m" and "n" are integer numbers. These equations are used to build and initialize any bloom őlter.

B.2.2 Intersection property

The intersection of two bloom őlters, BF A and BF A , aims to őnd common elements of two diferent sets, S A and S B . One bit will be set to one if: (1) the element belongs to the intersection of BF A and BF B : (BF A ∩BF B ), or (2) this bit is set simultaneously to one in BF A -BF A ∩ BF B and BF B -BF A ∩ BF B . Indeed, it represents the AND operation of the two őlters A and B, and the result is a new bloom őlter containing their common 1 Assuming perfectly random hash functions insertions. Thus, the probability that a specific bit is set to one in both filters is given by the simpliőed Equation 5.1 [START_REF] Broder | Network applications of bloom őlters: A survey[END_REF] and the false positive of this intersection is given by f p = q(bit = 1) k .

B.2.3 Union property

The union of two bloom őlters, BF A and BF A , aims to join two diferent sets, S A and S B . This is the OR operation of these őlters and results in a new bloom őlter joining both őlters. Therefore, the resulted őlter union represents a new set S A ∪ S B . It is possible to approximate the size of the expected total insertion in a bloom őlter [START_REF] Swamidass | Mathematical correction for őngerprint similarity measures to improve chemical retrieval[END_REF]. Equation B.4 shows this approximation, where card(X) denotes the number of bits set to "1" in the bloom őlter "X". By considering both Equations B.4 and B.2, it is possible to know the false positive ratio of the union of two bloom őlters.

B.3 Types of Bloom Filters

In this section we have explained a very simple case of representing items based on the standard deőnition of bloom őlters, where we have supposed a static dataset. In fact, when new features need to be taken into consideration the number of insertions raises.

However, the current bloom őlter parameters (size "m" and hash functions "k") can not face such raise and yield to a false positive raise as well. Indeed, these parameters cannot be modiőed, hence when new features are added to the system all bloom őlters need to be re-built according to new parameters. In addition, standard bloom őlters do not count the number of insertions of the same element, if necessary. Thus, these őlters can not be compared to frequency vectors.

In fact, these situations correspond to static versus dynamic datasets and binary versus Mots clés : filtrage collaboratif, système de recommandation, distribution, filtre de bloom, demarrage à froid, apprentissage actif Abstract :

Recommender Systems őlter and present őrst the information in which users may be interested. This has raised the attention of the e-commerce to predict future interests and to personalize the ofers (a.k.a. items). These systems face great challenges: they require distributed techniques to deal with a huge volume of data, they aim to exploit very heterogeneous data, and they sufer from cold-start. Among popular techniques, Matrix Factorization has demonstrated high accurate predictions and scalability. Our contributions are given by four aspects: (1) the distribution of a matrix factorization algorithm, [START_REF]2 Recommender System Libraries[END_REF] the implicit interest of the users in the attributes of the items to be used by matrix factorization, (3) the representation of users/items through a high quantity of features in low memory-consumption, and (4) the active learning techniques to cope with cold-start. We demonstrate their performance in terms of accuracy and eiciency using a publicly available dataset.