La présente invention concerne un système et un procédé de recommandation d'un produit à un utilisateur. Elle trouve notamment une application au domaine de la vente de produits en ligne, et vise plus particulièrement à formuler une recommandation la plus pertinente possible dans un temps le plus court possible.

On connaît des systèmes et procédés permettant de dégager un conseil d'association d'un produit avec un utilisateur. Classiquement, les systèmes connus collectent d'abord des données de manière aléatoire, ou selon une stratégie prédéterminée, avant d'initier le processus de recommandation. A chaque recommandation, l'avis de l'utilisateur est recueilli, sous la forme d'un score sur une échelle déterminée par exemple, ou encore sous une forme binaire de type « no- click / click ». Ensuite, des régularités statistiques dans les données recueillies après les premières recommandations sont identifiées, puis exploitées pour les prochaines recommandations. Eventuellement, un aléa peut continuer d'être introduit régulièrement dans les recommandations pour prendre en compte le besoin de mise à jour du modèle.

Dans le domaine des systèmes de recommandation pour de la vente en ligne, le modèle statistique le plus courant est celui fourni par la décomposition régularisée de la matrice des goûts des utilisateurs. Une telle matrice comprend des lignes regroupant chacune les évaluations données par un utilisateur donné à une série de produits, et des colonnes regroupant chacune les évaluations données par une série d'utilisateurs à un produit donné.

Ce modèle statistique présente notamment l'avantage de pouvoir être codé de manière efficace.

Le problème rencontré par tous les systèmes et procédés de recommandation est celui communément appelé du démarrage à froid ou « cold start » : initialisation du système pour un nouveau produit qui n'a pas encore, ou peu, été évalué par les utilisateurs, et/ou pour un nouvel utilisateur qui n'a pas encore, ou peu, évalué de produits. Bien sûr, l'initialisation complète du système présente simultanément les deux difficultés.

L'approche classique consiste à établir en amont des regroupements "experts" sur les produits et les utilisateurs, à partir d'une source tierce de données (comptes utilisateurs sur les réseaux sociaux, sexe, âge, mots clés utilisés lors d'une recherche, etc .).

A partir de telles données, on identifie d'autres utilisateurs ou produits déjà présents dans le système. Dans un premier temps, on choisit d'agir comme si ce nouvel utilisateur ou ce nouveau produit mal connu correspondait à la moyenne des utilisateurs ou produits « proches », qui sont quant à eux mieux connus.

On peut également, pour favoriser les nouveaux produits, leur accorder un « bonus » dans le système.

Dans le cas où les produits sont complètement décrits, il est possible de suivre une stratégie consistant à construire des ellipsoïdes de confiances autour des goûts des utilisateurs. La recommandation se fait alors en choisissant la description semblant la plus favorable à l'intérieur de cet ellipsoïde.

Ces approches sont connues sous le nom de bandits (UCB, KL-UCB, ...) et sont réputées dans le domaine du réglage du compromis exploration (amélioration du modèle) /exploitation (utilisation du modèle).

On peut citer par exemple le système et le procédé décrits dans US 2012/016642. Le problème principal posé par tous les systèmes et procédés connus, y compris dans US 2012/016642, est qu'ils nécessitent l'utilisation de données externes pour initier le processus de recommandation, et que le temps d'apprentissage pour que le système puisse délivrer des recommandations pertinentes à un nouvel utilisateur et/ou pour un nouveau produit est relativement long.

Ce problème est particulièrement important lorsqu'il est question de travailler sur des produits à durée de vie très courte. Avec de tels produits, les systèmes et procédés connus n'ont pas le temps de dégager des conseils d'association pertinents.

Nous considérons par exemple le problème de la recommandation de produits à des utilisateurs visitant des sites internet. Ces produits peuvent être des publicités, des informations, de la musique, des vidéos, des films, des livres, etc ..

De façon quotidienne, le plus souvent plusieurs fois par jour, les systèmes de recommandation doivent faire face à l'arrivée d'utilisateurs qui n'ont jamais visité le site web en question, ainsi qu'à l'introduction de nouveaux produits dans le catalogue.

Le problème du démarrage à froid déjà présenté plus haut peut aussi être formulé de la façon suivante : l'appétence des nouveaux utilisateurs par rapport aux produits disponibles, et l'attractivité des nouveaux produits par rapport aux utilisateurs connus, doivent être estimées aussi rapidement que possible.

Les approches connues sous le nom de bandits (UCB, KL-UCB, ...), également mentionnées plus haut, sont traditionnellement appliquées dans des domaines de dimension faible. Dans le cas des systèmes de recommandation tels que présentés plus haut, le nombre des bandits est renouvelé de façon continue et le nombre de ces bandits peut être très important (jusqu'à plusieurs centaines de millions de bras). Plus généralement, pour des raisons évidentes, la stratégie consistant à présenter aux utilisateurs tous les produits disponibles jusqu'à ce que l'évaluation semble estimée avec suffisamment de précision, n'est pas satisfaisante.

Il est nécessaire de prendre en compte le dilemme entre exploration et exploitation. L'exploration consiste en l'acquisition d'informations, en vue de leur exploitation ultérieure pour augmenter les performances du système. Ainsi, il est nécessaire d'explorer des recommandations qui n'ont pas encore été formulées en vue d'améliorer les performances du système, et non de se contenter d'exploiter les recommandations connues.

Par ailleurs, la question est posée de la fonction à optimiser pour déterminer une recommandation. Dans le domaine de l'apprentissage, le problème de la recommandation est souvent réduit à un problème de factorisation matricielle réalisée par lots, avec apprentissage sur un ensemble de données d'entraînement et minimisation de l'erreur quadratique moyenne sur un ensemble de données de test.

Cependant, l'utilisation de l'erreur quadratique moyenne présente des failles importantes.

La méthode consistant à minimiser l'erreur quadratique moyenne ne fait pas la différence entre les produits qui sont très bien évalués (obtention d'un très bon score) par un utilisateur et ceux qui sont très mal évalués (obtention d'un très mauvais score) par le même utilisateur.

Pourtant, pour un utilisateur donné, il existe une grande différence entre les produits bien notés et les autres. L'utilisateur souhaite en effet se voir recommander des produits qu'il ou elle va évaluer avec un très bon score. L'utilisateur ne se soucie pas des produits peu attractifs.

Pour illustrer ce point, dans un système d'évaluation des produits sur une échelle de 1 à 5, on peut dire qu'une erreur entre un score de 4 et un score de 5 est qualitativement très différente d'une erreur entre un score de 1 et un score de 2.

En outre, l'ensemble restreint des scores possibles implique par exemple qu'un score de 4 correspond plus ou moins à une évaluation assez bonne. Si les scores étaient des nombres réels, les produits obtenant un score de 4 se répartiraient par exemple sur les trois scores 3.5, 4, et 4.5.

Par ailleurs, on sait que les utilisateurs ont tendance à évaluer plutôt les produits qu'ils aiment que ceux qu'ils n'aiment pas.

D'autre part, la méthode consistant à minimiser l'erreur quadratique moyenne ne fait pas la différence entre le résultat d'une recommandation d'un produit à un utilisateur « lourd » (un utilisateur qui a déjà évalué beaucoup de produits) et le résultat de la première recommandation à un utilisateur lors de sa première visite sur le site web concerné.

Un autre problème de la minimisation de l'erreur quadratique moyenne est que l'ensemble des données d'entraînement et l'ensemble des données de test sont généralement non ordonnés et ne tiennent pas compte de l'historique des interactions.

Ainsi, la notion d'appétence moyenne d'un utilisateur pour un produit sur une période de temps donnée néglige complètement le fait qu'un produit donné ne présente pas la même attractivité entre le moment de sa mise en ligne initiale et le moment de son retrait de la vente. En effet, au moins dans certaines catégories de produits comme les téléphones portables par exemple, un produit récent est plus attirant qu'un produit ancien.

Par ailleurs, cette notion d'appétence moyenne d'un utilisateur pour un produit sur une période de temps donnée ne prend pas en compte le fait que l'attractivité des produits est souvent corrélée avec l'ensemble des produits disponibles à un moment donné ainsi que ceux disponibles dans le passé.

Par ailleurs, bien que la recommandation d'un produit à un utilisateur soit souvent présentée comme un problème de prédiction, il s'agit en fait d'un problème de classement. Or, la méthode de la minimisation de l'erreur quadratique moyenne n'est pas faite pour évaluer un classement.

Un des buts de l'invention est donc de résoudre les problèmes précités. Ainsi, l'invention a notamment pour objectif de proposer un système et un procédé de recommandation d'un produit à un utilisateur qui optimise l'équilibre entre exploration et exploitation, sur la base d'une matrice des évaluations factorisée pour se focaliser sur les termes les plus utiles de cette factorisation.

Nous introduisons dans ce qui suit un certain nombre de notations et le vocabulaire utilisés dans la suite de la présente description :

• Les lettres majuscules et en caractères gras désignent des matrices, telles que la matrice A.

• A ^r désigne la matrice transposée de A.

• Les lettres minuscules en caractères gras désignent des vecteurs, tels que le vecteur u.

• #u désigne le nombre d'éléments (la dimension) de u.

• Les lettres en caractères normaux désignent des valeurs scalaires.

• A l'exception de ζ , les lettres grecques désignent des paramètres d'algorithmes.

• Les lettres calligraphiques désignent des ensembles, tels que 5 ^* .

· #S désigne le nombre d'éléments dans l'ensemble S . Pour un vecteur u et un ensemble d'entiers S tels que Vs e S, s <#u , u _s désigne le sous-vecteur deu composé des éléments deu dont les indices forment^ . En conséquence, si U est une matrice etS un ensemble d'entiers inférieurs ou égaux au nombre de lignes de U , V _s désigne la sous-matrice comprenant les lignes de U dont les indices forment S (l'ordre des éléments dans S n'a pas d'importance, mais on peut supposer que les éléments de l'ensemble sont ordonnés).

Dans la mesure où nous considérons un nombre d'utilisateurs et de produits évoluant dans le temps, on note n le nombre courant d'utilisateurs et m le nombre courant de produits. Ces deux nombres doivent être indicés par t pour désigner cette évolution dans le temps. Mais dans la plupart des cas, on ne mentionnera pas l'indice f pour simplifier la notation.

/ ^' indice les utilisateurs et j indice les produits.

Sans perdre en généralisation, nous supposons que n <N et m<M, N et M correspondant aux seuils supérieurs respectivement du nombre d'utilisateurs et de produits jamais observés (ces deux nombres peuvent être très grands).

R ^* représente la matrice réelle de toutes les évaluations déjà observées de tous les produits possibles par tous les utilisateurs possibles. Dans une application réelle, cette matrice est (au moins partiellement) inconnue. Chaque ligne est associée à un seul et unique utilisateur, et chaque colonne est associée à un seul et unique produit. Aussi, on utilise ces indices de lignes et de colonnes pour désigner respectivement les utilisateurs et les produits.

R ^* est donc de taille N M.

r^. désigne l'évaluation donnée par l'utilisateur / ^' au produit j, ou encore le score obtenu par le produit j auprès de l'utilisateur / ^' .

Nous supposons, de façon standard, qu'il existe un entier k et des matrices U de taille N x k et V de taille M x k telles que R ^* = UV ^r .

A un instant donné, la totalité des évaluations n'a pas encore été observée. Soit S l'ensemble des éléments qui ont été observés jusqu'à présent. Soit R définie de la façon suivante :

où 7 , ₇ est un bruit de moyenne nulle et de variance finie, (les η _έ . sont des variables indépendantes et identiquement distribuées). Dans la pratique, la grande majorité des éléments de R est donc inconnue.

Nous supposons que R ^* est fixée à tout moment. A un certain moment, seule une sous-matrice de n lignes et m colonnes est en fait utile. Cette partie utile de R ^* qui est observée augmente avec le temps. Ainsi, l'ensemble S grossit avec le temps.

J(z ^' ) désigne l'ensemble des indices de colonnes pour lesquelles la matrice R contient une valeur à la ligne /. Il s'agit donc de l'ensemble des indices des produits évalués par l'utilisateur /.

De la même façon, désigne l'ensemble des indices de lignes pour lesquelles la matrice R contient une valeur à la ligne j. Il s'agit donc de l'ensemble des indices des utilisateurs ayant évalué le produit j.

Les symboles/ et/ font donc référence à des utilisateurs, donc à des lignes de la matrice d'évaluation, alors que les symboles j and J font référence à des produits, donc à des colonnes de la matrice d'évaluation.

Û et V désignent des estimations (au sens statistique) respectivement des matrices U et V . Leur produit ÛV ^r est noté R .

R ^* etR ont pour dimensions n _t x m _t à un temps ί donné. Aussi: U e R"' ^xi et V e R ^m,xt

A titre d'exemple, considérons « = 4 utilisateurs, m = 8 produits, et R ^* comme suit :

Supposons que : S = {(1,3),(1,6),(2,1),(2,4), (2,6),(3,2),(4,4),(4,6),(4,7)},

Alors, R est la matrice suivante (en supposant l'absence de bruit):

Une observation désigne un triplet (utilisateur, produit, évaluation du produit par l'utilisateur). Chaque valeur connue de la matrice R est en fait une observation.

Le système de recommandation reçoit donc un flux d'observations.

On utilise le terme de score ou d'évaluation pour désigner la valeur associée par un utilisateur à un produit. Il peut s'agir d'un score à proprement parler sur une échelle donnée, ou encore d'une information binaire telle qu'une information de type « no- click / click » ou « no-sale / sale ».

• Par souci de clarté, on omettra la plupart du temps l'indice f relatif à la dépendance temporelle. En particulier, S , Û , V , n , m devraient être indicés par f.

Ainsi, l'invention a pour objet, selon un premier aspect, un procédé informatisé de recommandation, par un moteur de recommandation, d'un produit à un utilisateur à partir d'une matrice de valeurs d'évaluation R stockée dans des moyens de stockage et dont chaque ligne représente un vecteur de valeurs d'évaluation de produits par un utilisateur donné, et chaque colonne représente un vecteur de valeurs d'évaluation d'un produit donné par des utilisateurs, le procédé comprenant :

- une étape de sélection d'au moins un produit j _t à recommander à au moins un utilisateur i _t , parmi tous les produits j pour lesquels la valeur d'évaluation ¾ par l'utilisateur i _t n'est pas présente dans la matrice R, au cours de laquelle, pour tous lesdits produits j, le moteur de recommandation,

- génère des valeurs estimées d'évaluation r _itj desdits produits j par l'utilisateur i _t ,

- détermine un intervalle de confiance pour chacune des valeurs estimées r _itj ,

- sélectionne le produit j _t , parmi lesdits produits j, pour lequel la somme de la valeur estimée r ^t et de l'intervalle de confiance de cette valeur estimée r ^t, est maximale,

- une étape de recommandation à l'utilisateur i _t du produit j _t sélectionné par le moteur de recommandation, par l'intermédiaire d'une interface,

- une étape de récupération, par l'intermédiaire de l'interface, de la valeur d'évaluation r _itj t par l'utilisateur i _t du produit j _t recommandé, et de mise à jour par le moteur de recommandation de la matrice d'évaluation R en ligne i _t et colonne j _t avec la valeur d'évaluation r _itj t récupérée,

Préalablement à la génération des valeurs estimées r _itj , le moteur de recommandation détermine deux matrices U et V telles que R = U x V ^T .

Pour générer chaque valeur estimée r _itj , le moteur de recommandation réalise le produit vectoriel du vecteur U _it correspondant à la ligne i _t de la matrice U, avec le vecteur transposé V _j ^T correspondant à la ligne j transposée de la matrice V.

La détermination de l'intervalle de confiance de chacune des valeurs estimées r _itj par le moteur de recommandation est fonction soit des lignes de la matrice V correspondants aux produits pour lesquels une valeur d'évaluation par l'utilisateur i _t a déjà été récupérée, soit des lignes de la matrice U correspondant aux utilisateurs ayant déjà évalué le produit j. Suivant certains modes de réalisation, le procédé comprend en outre une ou plusieurs des caractéristiques suivantes, prise(s) isolément ou suivant toutes les combinaisons techniquement possibles :

- la détermination des matrices U et V est réalisée en sélectionnant parmi tous les couples de matrices U, V possibles celui qui minimise la somme

∑(r, ₇ . - lV Vj ) ² + A . Q(U,V), où λ est un paramètre réel positif déterminé, et Q(U,V) =∑#J(/ ) Il U, f +∑# /( / ) Il V . f ,

avec U, et V _j correspondant respectivement à la ligne i de la matrice U et à la ligne j de la matrice V.

- la détermination de l'intervalle de confiance de chacune des valeurs estimées r _itj est o lisant le calcul suivant :

où

- A = (V _J( . ₎ ) ^r - V _j¾) + max(l;A.#J( - Id)

- J(i _t ) est l'ensemble des produits évalués par l'utilisateur i _t ,

- λ est un paramètre réel positif déterminé,

- Id est la matrice identité.

- la détermination de l'intervalle de confiance de chacune des valeurs estimées r _itj est o t le calcul suivant :

où

- BU) = (Û _/0 , Û _/0 , + max(l;A-#/(/) · Id)

- est l'ensemble des indices des utilisateurs ayant évalué le produit j,

- λ est un paramètre réel positif déterminé,

- Id est la matrice identité.

L'invention a également pour objet, selon un deuxième aspect, un produit programme d'ordinateur stocké sur des moyens de stockage et comprenant un jeu d'instructions chargeable dans la mémoire d'un ordinateur, tel que, lorsque ledit jeu d'instructions est exécuté sur ledit ordinateur, le produit programme met en œuvre le procédé présenté plus haut.

L'invention a encore pour objet, selon un troisième aspect, un système de recommandation d'un produit à un utilisateur, comprenant des moyens de stockage dans lesquels est stockée une matrice de valeurs d'évaluation R dont chaque ligne représente un vecteur de valeurs d'évaluation de produits par un utilisateur donné, et chaque colonne représente un vecteur de valeurs d'évaluation d'un produit donné par des utilisateurs, une interface de recommandation, et un moteur de recommandation apte à

- sélectionner au moins un produit j _t à recommander à au moins un utilisateur i _t , parmi tous les produits j pour lesquels la valeur d'évaluation ¾ par l'utilisateur i _t n'est pas présente dans la matrice R, en

— générant des valeurs estimées d'évaluation r _itj desdits produits j par l'utilisateur i _t ,

— déterminant un intervalle de confiance pour chacune des valeurs estimées r _itj ,

— sélectionnant le produit j _t , parmi lesdits produits j, pour lequel la somme de la valeur estimée r _itj t et de l'intervalle de confiance de cette valeur estimée r ^t, est maximale,

- recommander le produit sélectionné j _t à l'utilisateur i _t par l'intermédiaire de l'interface,

- récupérer, par l'intermédiaire de l'interface, la valeur d'évaluation r _itj t par l'utilisateur i _t du produit j _t recommandé, et à mettre à jour la matrice d'évaluation R en ligne i _t et colonne j _t avec la valeur d'évaluation r _itj t récupérée,

Le moteur de recommandation est apte à

- préalablement à la génération des valeurs estimées r _itj , déterminer deux matrices U et V telles que S = U x V ^T

- pour générer chaque valeur estimée r _itj , réaliser le produit vectoriel du vecteur U _it correspondant à la ligne i _t de la matrice U, avec le vecteur transposé V _j ^T correspondant à la ligne j transposée de la matrice V,

- déterminer l'intervalle de confiance de chacune des valeurs estimées r _itj en fonction soit des lignes de la matrice V correspondant aux produits pour lesquels une valeur d'évaluation par l'utilisateur i _t a déjà été récupérée, soit des lignes de la matrice U correspondant aux utilisateurs ayant déjà évalué le produit j.

Suivant certains modes de réalisation, le système comprend en outre une ou plusieurs des caractéristiques suivantes, prise(s) isolément ou suivant toutes les combinaisons techniquement possibles : - le moteur de recommandation est apte à déterminer (aO) les matrices U et V en sélectionnant parmi tous les couples de matrices U, V possibles celui qui minimise la somme

∑(r, ₇ . - l V; ) ² + A . Q(U,V), où λ est un paramètre réel positif déterminé, et

Q(U,V) =∑#J(/ ) il U, f +∑#I(j ) il v. f ,

' j

avec U, et V _j correspondant respectivement à la ligne i de la matrice U et à la ligne j de la matrice V.

- le moteur de recommandation est apte à déterminer l'intervalle de confiance de chacu en réalisant le calcul suivant :

où

- A = (\ _J( . _} f ^■ \ _J( . ₎ + max(l;A-#J ) . Id)

J(i _t ) est l'ensemble des produits évalués par l'utilisateur i _t ,

- λ est un paramètre réel positif déterminé,

Id est la matrice identité.

- le moteur de recommandation est apte à déterminer l'intervalle de confiance de chacu en réalisant le calcul suivant :

où

- B(j) = (Û _/0 ,) ^r Û _/0 , + max(l;A-#/(/) · Id)

est l'ensemble des indices des utilisateurs ayant évalué le produit j,

- λ est un paramètre réel positif déterminé,

- Id est la matrice identité.

Ainsi, selon l'invention, on utilise la factorisation de la matrice R des évaluations, telle que présentée plus haut, pour construire en ligne la représentation des valeurs d'évaluation estimées, sans faire appel à des sources d'information extérieures quelconques.

Le procédé et le système de l'invention permettent donc de fonctionner sur un système complètement « froid », sans aucune information de contexte ou information provenant de sources extérieures, grâce à la factorisation de la matrice R des évaluations, et à la stratégie de maximisation de l'intervalle de confiance associé aux valeurs d'évaluation estimées.

Les caractéristiques et avantages de l'invention apparaîtront à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple, et non limitative, en référence aux figures annexées suivantes :

- figure 1 : représentation schématique d'un exemple de système selon l'invention ;

- figure 2 : représentation schématique des étapes principales du procédé selon l'invention ;

- figure 3 : représentation schématique plus détaillée d'une des étapes du procédé selon l'invention,

- figure 4 : représentation schématique de l'utilisation de la notion d'intervalle de confiance dans le cas d'un nouvel utilisateur,

- figure 5 : représentation schématique de l'utilisation de la notion d'intervalle de confiance dans le cas d'un nouveau produit.

La figure 1 représente schématiquement un exemple de système de recommandation selon l'invention, avec ses principaux composants.

Un moteur de recommandation 1 , qui peut par exemple être implémenté sur un serveur, est associé à des moyens de stockage 2.

Le moteur de recommandation 1 peut notamment lire et écrire des données respectivement depuis et dans les moyens de stockage 2, et est connecté à un réseau 4, comme par exemple le réseau Internet.

Des utilisateurs i _t sont également connectés au réseau 4, par exemple par l'intermédiaire de moyens informatiques 3 tels que des ordinateurs, des téléphones portables, des tablettes, etc ..

L'ensemble des moyens informatiques 3 et réseau 4 constitue, au sens de la présente description, une interface 3, 4 entre l'utilisateur i _t et le moteur de recommandation 1 , permettant à cet utilisateur i _t de recevoir et d'envoyer des données respectivement de la part et vers le moteur de recommandation 1.

Ainsi, par exemple, mais pas uniquement, sur requête de l'utilisateur i _t , le moteur de recommandation 1 va sélectionner un produit j _t susceptible de présenter un intérêt pour l'utilisateur i _t .

Ce produit j _t peut par exemple être sélectionné dans un catalogue ou une liste de produits, non représentée dans la figure 1 , qui serait stocké dans les moyens de stockage 2 ou dans des moyens de stockage distincts également non représentés. Les moyens de stockage 2 stockent une matrice d'évaluation R, déjà présentée plus haut.

Cette matrice R contient des valeurs d'évaluation r _itjt d'un produit j _t par un utilisateur i _t .

Comme on le verra plus en détail par la suite, et également en référence à la figure 2, le moteur de recommandation 1 utilise les valeurs de la matrice R pour sélectionner au moins un produit j _t , parmi les produits que l'utilisateur i _t n'a pas encore évalué, susceptible de présenter un intérêt pour l'utilisateur i _t , lors d'une étape a de sélection.

Ce produit j _t est soumis à l'utilisateur i _t par le moteur de recommandation 1 , lors d'une étape b de recommandation, par l'intermédiaire de l'interface 3, 4.

L'utilisateur i _t peut alors donner son appréciation du produit, par exemple par une note, un commentaire, une action de type « no-click / click » ou « no-sale / sale », traduite en une valeur d'évaluation r _itjt transmise en retour au moteur de recommandation 1 via l'interface 3, 4, lors d'une étape c de récupération de cette valeur d'évaluation r _itjt -

La matrice R est alors mise à jour avec cette nouvelle valeur d'évaluation r _itjt ainsi récupérée par le moteur (1 ).

Tel que représenté schématiquement à la figure 3, pour sélectionner le produit j _t à recommander à l'utilisateur i _t lors de l'étape a, le moteur de recommandation 1 génère, lors d'une sous-étape a1 , une valeur estimée d'évaluation r _itj des produits j par l'utilisateur i _t .

Le moteur de recommandation 1 détermine également, lors d'une sous-étape a2, un intervalle de confiance pour chacune des valeurs estimées r _itj .

Pour déterminer le produit j _t susceptible d'intéresser l'utilisateur i _t , le moteur de recommandation 1 sélectionne, lors d'une sous-étape a3, le produit j _t , parmi les produits j, pour lequel la somme de la valeur estimée r ^ _t et de l'intervalle de confiance de cette valeur estimée r _it jt, est maximale.

Mais dans un premier temps, le moteur de recommandation 1 réalise une factorisation de la matrice R, qui consiste, lors d'une sous-étape aO, à déterminer deux matrices U et V telles que R = U x V ^T .

La sous-étape suivante a1 de génération des valeurs estimées r _itj par le moteur de recommandation 1 , utilise alors cette factorisation de la matrice R, en réalisant le produit vectoriel du vecteur U _it correspondant à la ligne i _t de la matrice U, avec le vecteur transposé V _j ^T correspondant à la ligne j transposée de la matrice V.

Par ailleurs, la détermination de l'intervalle de confiance de chacune des valeurs estimées r _itj par le moteur de recommandation 1 , réalisée lors de la sous-étape a2, est fonction soit des lignes de la matrice V correspondant aux produits pour lesquels une valeur d'évaluation par l'utilisateur i _t a déjà été récupérée, soit des lignes de la matrice U correspondant aux utilisateurs ayant déjà évalué le produit j.

Pour obtenir la factorisation de la matrice R en le produit U x V ^T , et dans la mesure où la plupart des valeurs d'évaluation r _it jt dans cette matrice R sont inconnues (on considère que le nombre de produits et d'utilisateurs est relativement important, et qu'à un instant t, il y a un nombre relativement important de produits qui ont été peu évalués par les utilisateurs et/ou un nombre relativement important d'utilisateurs qui ont peu évalué de produits), on peut résoudre le problème de minimisation régularisé suivant :

_{Λ Λ} def def , * - (V,\) = argmin _v ^ (V,\) avec £ (U,V) = ∑ (r, . - Υ' ) + λ ·Ω(ϋ,ν),

avec pour paramètre λ e R ⁺ .

Le terme de régularisation Ω peut être défini comme suit :

def

Ω(ϋ, V) = il u il ² + il v =∑ il u, il ² +∑ il v. il ² ,

' j

dans lequel U _; désigne la ligne i de la matrice U, et V. désigne la ligne j de la matrice V.

La fonction ζ n'est pas convexe. On peut par exemple réaliser la minimisation par une méthode de type gradient stochastique descendant, ou encore de type méthode des moindres carrés alternés.

Dans notre exemple, on utilise :

def

Ω(ϋ, V) =∑#J(i) Il U, II ² +∑#/(/) Il V. Il ² .

Ce type de régularisation est considéré comme présentant un bon comportement empirique, avec un sur-apprentissage limité, un réglage du paramètre relativement facile, et une faible erreur quadratique moyenne.

Pour déterminer l'intervalle de confiance de la valeur estimée r _it jt, on s'intéresse à la théorie des « bandits manchots », ou théorie des bandits, par analogie au contexte des machines à sous ou bandits dans un casino.

Nous considérons donc une machine de type bandit avec m bras indépendants. Lorsque le joueur actionne le bras j, il reçoit une récompense comprise dans l'intervalle

[0 ; 1 ] qui présente une distribution de probabilités V _j .

def

Soit i _; , qui désigne la moyenne de V _j , et f = argmaX _j ^ _j qui désigne le meilleur bras. Les paramètres {v _; } , {μ -} , f et μ ^* sont inconnus. Le but du joueur est de maximiser sa récompense cumulée après T coups consécutifs. Plus précisément, si j _t désigne le bras actionné au temps f et r _t désigne la récompense obtenue au temps f, le joueur cherche à maximiser la quantité suivante :

CumRew _T = fi-

Dans la mesure où les paramètres sont inconnus, à chaque temps f (sauf au dernier), l'utilisateur fait face au dilemme suivant :

soit « exploiter » en actionnant le bras qui semble le meilleur selon les valeurs estimées des paramètres,

soit « explorer » pour améliorer l'estimation des paramètres de la distribution de probabilités d'un bras en l'actionnant.

Pour gérer ce dilemme et trouver un compromis entre exploration et exploitation, on utilise une stratégie basée sur la notion d'intervalle de confiance. Ainsi, on va actionner le bras j tel que :

avec μ . qui désigne une estimation de μ . au temps t et t qui correspond au nombre d'actionnements du bras j depuis le temps t = 1 .

Cette stratégie est optimale, à une constante près. L'équation ci-dessus exprime clairement le compromis entre exploration et exploitation : alors que le terme ( μ . ) de la somme tend à favoriser l'exploitation du bras qui semble optimal, le second terme de la somme tend à favoriser l'exploration des bras les moins actionnés.

On considère alors qu'à chaque bras j est associé un contexte sous la forme d'un vecteur de nombres réels v _; e R ^k , et que l'espérance de récompense associée à un bras est déterminée par :

avec u qui est un vecteur inconnu.

La stratégie optimale est alors d'actionner le bras présentant le plus grand intervalle de confian mpense attendue, soit :

j _t = argmax .û · y ^T . +

avec :

û qui désigne une estimation de u ,

a qui est un paramètre, A = ^T j _t + Id (où Id désigne la matrice identité).

Le produit û.v^ correspond à une estimation de la récompense attendue, alors que correspond à une correction optimiste de cette estimation.

L'objectif de cette stratégie est donc de maximiser la récompense cumulée, mais on peut aussi l'exprimer en termes de regret cumulé en s'intéressant à la somme des différences à chaque temps f entre la meilleure récompense attendue et la récompense réelle. Le regret mesure alors combien le joueur est susceptible de perdre par comparaison avec l'utilisation de la stratégie optimale.

Dans le cadre de l'invention, l'application de cette stratégie de maximisation de l'intervalle de confiance sur la récompense attendue, basée sur la théorie des bandits contextuels, est réalisée sans aucune information contextuelle sur les produits et les utilisateurs, contrairement aux systèmes et procédés connus qui utilisent par exemple des connaissances d'experts, la notion de catégorisation de produits, les profils des utilisateurs sur les réseaux sociaux, la notion de « feedback » implicite, comme il a été expliqué en première partie de cette description.

Selon l'invention, on utilise la factorisation de la matrice R des évaluations, telle que présentée plus haut, pour construire en ligne la représentation des valeurs d'évaluation estimées.

Par conséquent, le procédé et le système de l'invention permettent de fonctionner sur un système complètement « froid », sans aucune information de contexte ou information provenant de sources extérieures.

On considère d'abord le cas d'un « démarrage à froid » pour un nouvel utilisateur i _t , c'est-à-dire un utilisateur i _t qui n'a pas ou peu évalué de produits, par exemple qui a évalué un nombre de produits inférieur à un seuil donné.

Comme il a déjà été expliqué, le procédé de recommandation consiste, à chaque temps t, à recommander à un utilisateur i _t un produit j _t parmi les produits qui n'ont pas encore été recommandés à l'utilisateur i _t , par exemple sur une requête de cet utilisateur/, , puis à récupérer la valeur d'évaluation r. = r. ,. donnée par l'utilisateur L pour

'

ce produit j _t .

L'objectif du procédé est de maximiser la récompense cumulée, pour reprendre les termes présentés plus haut, exprimée de la façon suivante : CumRew _T = ^ _{t= t} . L'approche de la factorisation de la matrice R d'évaluations, également présentée plus haut, permet de recommander le produit j _t qui présente la meilleure valeur estimée de l'évaluation par l'utilisateur i _t .

Cela correspond alors à une stratégie purement d'exploitation, qui est sous- optimale puisqu'elle ne prend pas en compte la nécessité d'exploration, c'est-à-dire une stratégie équilibrée entre exploitation et exploration.

Pour proposer à l'utilisateur i _t le produit j _t qui correspond au meilleur compromis entre exploration et exploitation, on se base donc dans un premier temps sur la factorisation de la matrice d'évaluations R en le produit ÛV ^r tel qu'expliqué plus haut.

On détermine alors un intervalle de confiance pour chacune des valeurs d'évaluation estimées r. . = U, - Vf pour chaque produit / ^' .

On considère que l'on a déjà observé un nombre suffisant d'évaluations pour chaque produit, mais pas ou peu d'évaluations de la part de l'utilisateur^ , comme expliqué plus haut.

Par conséquent, l'incertitude sur U. est bien plus importante que l'incertitude sur

V, . En d'autres termes, l'incertitude sur r. . provient principalement de l'incertitude sur

U. , et l'on va exprimer cette incertitude.

On introduit donc la matrice A de dimensions k x k :

^{A =} ∑ vJ -v ₇ . + A-#J )-id.

(où λ est un paramètre déterminé) qui permet de définir l'intervalle de confiance autour de l'estimation U, des valeurs réelles de U _it .

On va alors choisir le produit j tel que :

avec a e R qui est un paramètre exploratoire.

Ainsi, le calcul des intervalles d'incertitude, ou intervalle de confiance, utilise la même régularisation que celle utilisée pour la décomposition matricielle de la matrice R.

On parle ici d'un ellipsoïde de confiance, dans l'espace R* , tel que représenté à la figure 4.

Sur cette figure, les utilisateurs et les produits sont représentés par des vecteurs dans l'espace R* . Les points arrondis correspondent à des vecteurs produits connus. La zone de l'ellipsoïde correspond à la zone de confiance pour le vecteur inconnu associé à l'utilisateur.

L'évaluation optimiste de l'utilisateur pour le produit 1 correspond au produit scalaire maximum entre ^" V^ et un point dans l'ellipsoïde. Par une simple démonstration géométrique basée sur les iso-contours du produit scalaire, on obtient ce produit scalaire maximum en calculant le produit scalaire entre ^" V^ et ïï ⁽¹⁾ représenté par un point de forme carrée.

La recommandation optimiste par le procédé et le système de l'invention porte sur le produit qui maximise le produit scalaire <ïï ⁰⁾ , V _; ) .

L'estimation du centre de l'ellipsoïde et la taille de cet ellipsoïde peuvent être influencées par l'utilisation d'un autre terme de régularisation que celui qui a été présenté plus haut pour la factorisation de la matrice R des valeurs d'évaluation.

On peut aussi choisir de remplacer #J(.) par 1 . En fait, toute régularisation qui garantit que U. est une combinaison linéaire des valeurs d'évaluation peut être utilisée.

On considère également le cas d'un « démarrage à froid » pour un nouveau produit j, c'est-à-dire un produit j qui n'a pas encore ou peu été évalué, par exemple qui a été évalué par un nombre d'utilisateurs inférieur à un seuil donné.

Dans un cas extrême de démarrage à froid, il peut être question de combiner l'arrivée d'un ou plusieurs nouveaux utilisateurs et l'introduction d'un ou plusieurs nouveaux produits.

Lorsqu'un nouveau produit est introduit, la description de ce produit est une source d'incertitude plus importante que la description des utilisateurs

Pour en tenir compte, on détermine un intervalle de confiance sur les produits plutôt que sur les utilisateurs. De la même façon, on obtient cette fois une matrice B(j) pour chaque produit j qui n'a pas encore été recommandé à l'utilisateur i _t , et à chaque temps t, telle que :

def

Β(7) = (ΰ _/ω ) ^Γ ΰ _/( . _{) +} λ·#/( ₇ ·) · Μ

(où λ est un paramètre déterminé) qui permet de définir l'intervalle de confiance autour de l'estimation V. des valeurs réelles de V _j . Si l'on considère alors l'ellipsoïde de confiance surV , l'intervalle de confiance pour l'estimation de la valeur d'évaluation par l'utilisateur i _t sur le produit j est : Û. -Vj + a^B T ¹ ^ . avec a e R qui est un paramètre exploratoire.

On va alors choisir le produit tel que :

Ici encore, le calcul des intervalles d'incertitude, ou intervalle de confiance, utilise la même régularisation que celle utilisée pour la décomposition matricielle de la matrice R.

La figure 5 illustre l'utilisation de l'ellipsoïde de confiance pour la sélection d'un produit dans le contexte de l'introduction d'un ou plusieurs produits nouveaux ou récents.

Le vecteur associé à l'utilisateur (point de forme carrée) est cette fois connu et les vecteurs produits se trouvent dans l'ellipsoïde de confiance. La recommandation optimiste par le procédé et le système de l'invention porte sur le produit qui maximise le produit scalaire (U, , ν ^ω ) .

Dans un cas extrême de démarrage à froid, il peut être question de combiner la partie du procédé qui gère l'arrivée d'un ou plusieurs nouveaux utilisateurs et celle qui gère l'introduction d'un ou plusieurs nouveaux produits, pour enrichir le plus rapidement possible le modèle.

Dans le cas d'un «démarrage à froid pour un nouvel utilisateur / ^' », on constate que la recommandation est optimale même si le moteur de recommandation 1 fonctionne dans ce mode alors que l'utilisateur / ^' a déjà évalué beaucoup de produits.

De même, dans le cas d'un «démarrage à froid pour un produit j », on constate que la recommandation est optimale même si le moteur de recommandation 1 fonctionne dans ce mode alors que le produit y a déjà été évalué par beaucoup d'utilisateurs.

Aussi, le moteur de recommandation 1 fonctionne dans l'un ou l'autre des deux modes, voire dans les deux modes successivement ou en parallèle.

Le moteur de recommandation 1 est toujours actif, car il alloue dynamiquement la juste proportion d'exploration et se concentre donc sur les produits les plus adaptés une fois la confiance dans le modèle suffisamment élevée.

La décision de faire fonctionner le moteur de recommandation 1 en mode «démarrage à froid pour un nouveau produit y » ou en mode «démarrage à froid pour un nouvel utilisateur / ^' » peut être une décision de la personne qui gère le système de recommandation, en fonction du contexte.

Lorsque le moteur de recommandation 1 fonctionne dans les deux modes successivement, ou en parallèle, on choisit la meilleure recommandation des deux, c'est- à-dire celle pour laquelle la somme calculée à l'étape a3 est la plus grande. Dans ce cas, la détermination de cette recommandation la meilleure peut être manuelle, ou réalisée automatiquement par le moteur de recommandation 1 lui-même.

Le cas le plus extrême correspond à l'initialisation complète de la matrice R, avec un ou plusieurs nouveaux utilisateurs et un ou plusieurs nouveaux produits, sans aucune information de contexte ou provenant de sources extérieures.

Des tests ont été réalisés sur des données réelles. Ils montrent que le procédé de l'invention tend à favoriser les produits nouveaux ou récents, par rapport aux plus anciens. Cela permet donc d'enrichir rapidement le modèle, en obtenant rapidement des nouvelles valeurs d'évaluation pour ces produits qui n'ont pas encore été suffisamment évalués.

On peut donc considérer que le procédé de l'invention donne un coup de pouce à ces produits nouveaux ou récents. Ceci est précisément ce que l'on recherche dans le contexte par exemple de la vente de produits en ligne par Internet. Si le gestionnaire d'un site de vente en ligne accepte des nouveaux produits, c'est parce qu'il pense que ces nouveaux produits sont potentiellement meilleurs que les plus anciens.

De plus, ceci va permettre une stratégie de recommandation qui utilise au mieux l'effet nouveauté. Or, l'on sait que l'attraction naturelle des utilisateurs par rapport aux nouveaux produits peut être très forte.

La présente description est donnée à titre d'exemple et n'est pas limitative de l'invention. En particulier, l'architecture du système présentée en référence à la figure 1 est purement fonctionnelle. La structure de ce système peut varier, par exemple en tenant compte du fait que les données nécessaires à son fonctionnement peuvent être stockées de façon répartie dans différents moyens de stockage proches ou distants, et que le moteur de recommandation peut lui-même être développé selon une architecture répartie qui utilise plusieurs moyens de calculs distants, éventuellement de façon parallèle.