C'est la définition d'un ensemble de caractéristiques permettant de
- Connaître ses besoins/préfèrences
- Connaître son comportement
Voir aussi sur wikipedia : User modeling
Contexte général
Un modèle utilisateur
Business Intelligence
Modèles utilisateurs
Benjamin Piwowarski
Lundi 28 mars 2022
$\def \argmin {\mathop{\textrm{argmin}}}
\def \argmax {\mathop{\textrm{argmax}}}
\def \RR {\mathbb{R}}$
Contexte et principe général
Besoins et préfèrences
Motivations
Connaître les préfèrences et/ou besoins permet :
- Recommendation (cf cours)
- Personnalisation (moteur de recherche)
- Campagne de pub
- e-commerce
- e-learning
- e-santé
- ...
Campagne d'Obama de 2008
Les développeurs du site Internet de la campagne ont
ainsi testé à la fois différents boutons, différentes images, et ont également
testé l’influence de vidéos à la place des images.
Comment faire ?
Une variété de techniques...
- AnalyseRegroupement (clustering)...puis statistiques exploratoires et visualisation (cf cours précédents)
- Comparaison Permet de comparer l'effet de traitements (ex. interface) sur une population d'utilisateursex. A/B Testing
- Prédiction : Apprentissage superviséClassification (l'utilisateur aime, ou non)Régression (note attribuée)
- Modélisation des utilisateursModèles génératifsModèles de clic
Analyse
Analyse des données
Approches purements qualitatives ( = visualisation)
Plusieurs types de stratégies :
Aggrégation des utilisateurs
On résume l'activité de tous les utilisateurs
Visualisation directe
On représente les utilisateurs par leurs caractéristiques
Et on les visualise (ACP, t-SNE, Isomap, etc.)
Regroupement (clustering)
Permet d'identifier des groupes d'utilisateur et de les caractériser (visualisation)
Aggrégation : traces d'activités
On peut visualiser ce que font les utilisateurs
Exemple : flot des utilisateurs
Visualisation des traces utilisateur agrégées
Exemple : Clustering et visualisation
Wang, G. et al.
2016. Unsupervised Clickstream Clustering for User Behavior Analysis.
Analyse du réseau social Renren et Whisper (Chine)
Chaque utilisateur est représenté comme par une série d'événements
send-request(5s), visit album(10s), etc.
- Définition d'une distance dans l'espace des séquences
- Clustering
Exemple : Clustering et visualisation
Wang, G. et al.
2016. Unsupervised Clickstream Clustering for User Behavior Analysis.
Résultats
Conclusion
Conclusion rapide sur l'analyse
Utile pour visualiser dans un premier temps
Ne permet pas de comparer ou prédire
Comparaison - A/B Testing
Problématique
On veut comparer deux systèmes (A et B)
Mise en production
On a deux alternatives (ex. deux moteurs de recherche)
- Le premier (A) est en production
- Le second (B) est expérimental
Comment peut-on savoir si B > A ?
Test A/B
On modifie un aspect (interface, etc.)
On mesure le changement de comportement des utilisateurs
Méthodologie
Pour savoir si A est mieux que B, on utilise des tests statistiques
- On peut utiliser des valeurs appariées ou nonapparié : Mesure du revenu pour un même utilisateur avec A et B
- On suppose une distribution on peut utiliser un test d'adéquation, ex. le test du χ²
- On utilise le test statistique approprié
Exemple : moteurs de recherche
Contexte
On compare deux moteurs de recherche A et B
Le clic c'est chic
On compte le nombre de clics par utilisateur
On suppose que plus on a de clics = mieux
Exemple : moteurs de recherche
Nombre de clics
L'utilisateur clique avec une probabilité $p$ sur $n$ résultats de recherche (Distribution binomiale)
Utilisation du test exact de Fisher pour mesure si la variable aléatoire "clic" est indépendante du moteur de recherche
| A | B | |
| Clic | 520 | 601 |
| Pas de Clic | 120 | 232 |
Test = est-ce que les deux événements sont liés (A/B et Clic/Pas de clic) ?
Hypothèse nulle = loi hypergéométrique de paramètres $(n, p, N)$
$$ \mathbb{P}(X=k)= \frac{{pN\choose k}{qN\choose n-k}}{{N\choose n}} $$
qui correspond à la probabilité de tirer $k$ boules vertes en tirant dans un ensemble de $N$ boules avec $pN$ boules vertes et $qN$ boules d'une autre couleur
Exemple : moteurs de recherche
Avec clic = succès et $X$ le nombre de clics pour A, on a
- $N$ le nombre total d'impressions
- $n$ nombre d'impressions pour A
- $p$ la probabilité d'un clic (hypothèse nulle)
Conclusion (A/B testing)
Facile à mettre en place
Possibilité de l'utiliser en continu
On ne compare que deux systèmes à la fois
Si B est trop expérimental... les utilisateurs peuvent être mécontents
Peu sensible (si A et B sont très proches, il faudra beaucoup d'observations)
Alternatives
- A/B testing "light" = Interleaving (dans des cas particuliers)Transparents suivants
- Modèles utilisateurscf plus tard dans ce cours
Interleaving : moteurs de recherche
Modèle utilisateur
Pour pouvoir utiliser des modèles d'interleaving, il faut faire certaines hypothèses :
Exemple (d'autres seraient possibles)
- Un utilisateur parcourt la liste du début à la fin
- Après son dernier clic, on ne sait pas ce qu'il a fait
Cela permet d'établir des règles de préférence
Pertinence et clics: Click > Skip Above
Joachims, T. et al.
2007. Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web search.
Pour un ordonnancement $(l_1, l_2, l_3, ...)$, et un ensemble $C$ de documents cliqués, on peut définir un ordre $$ rel(l_i) > rel(l_j)\mbox{ si }l_i\in C \mbox{ et } l_j \not\in C\mbox{ et } 1 \le j < i$$
interleaving
Radlinski, F. et al.
2008. How does clickthrough data reflect retrieval quality? Proceedings of the 17th ACM conference on Information and knowledge management.
Mêler les listes
On mélange les listes de deux moteurs de recherche A et B
On compte le nombre de clics sur les résultats de A et B
Comparaison des sytèmes
Notion de "A ou B gagne"
$$\Delta _ { A B } = \frac { \operatorname { wins } ( A ) + \frac { 1 } { 2 } \operatorname { ties } ( A , B ) } { \operatorname { wins } ( A ) + \operatorname { wins } ( B ) + \operatorname { ties } ( A , B ) } - 0.5$$
interleaving - comment mélanger ?
Balanced Interleaving
Gagnant :
- on regarde le $k$ qui permet d'inclure tous les clics de l'utilisateur
- on compte le nombre de clics dans pour A ou B (dans le top-$k$)
Interleaving - comment mélanger ? Correction des biais
Bias potentiel, ex. A = (a, b, c, d) et B = (b, c, d, a)
On obtient les listes (a, b, c, d) ou (b, a, c, d )
On veut qu'un utilisateur qui clique au hasard ne favorise ni A ni B...
mais ici, $p(A\mbox{ gagne}) = \frac 2 8 < p(B\mbox{ gagne}) = \frac 6 8$
interleaving - comment mélanger ? Team Draft
Analogie sportive = chaque modèle tire son "meilleur" document (au sens du rang) en alternant
Comptage = on comptabilise un clic pour un modèle si le modèle a proposé ce
Avec le même exemple A = (a, b, c, d) et B = (b, c, d, a)
On obtient les listes (a/A, b/B, c/A, d/B), (a/A, b/B, c/B, d/A), (b/B, a/A, c/A, d/B), ...
clics aléatoire = égalité (par construction)
Interleaving - exemple
Interleaving - résultats
Comparaison de la nDCG avec le $\Delta_{AB}$
Avec une estimation des intervalles par bootstrap
- On échantillone $k$ fois (avec remplacement) pour estimer $\Delta_{AB}$ ou $nDCG$
- Estimation des quantiles ($0.05$ et $0.95$)
Interleaving et Apprentissage d'ordonancement
Utiliser $Delta_{AB}$ pour apprendre
Un algorithme simple de "descente de gradient"
Yue, Y. and Joachims, T.
2009. Interactively optimizing information retrieval systems as a dueling bandits problem.
Conclusion
A/B Testing et interleaving
A/B Testing permet de comparer deux systèmes
Applicable à tout
Sensibilité à la différence
Interleaving
Sensibilité à la différence
Applicable à l'ordonnancement seulement
Bandits
la semaine prochaine
Comment apprendre à explorer et exploiter ?
Modèle prédictifs
Introduction
Utilisation de modèle supervisés
Un utilisateur est défini par un ensemble de caractéristiques
On prédit une valeur d'intérêt
Rétention des utilisateurs
Une entreprise de telecom veut s'assurer de garder ses clients
Mesure des caractéristiques d'un client
- âge,
- sexe,
- nombre d'appels au service client et durée,
- etc.
On veut prédire la probabilité que le client s'en aille
Méthodologie
- Collection des données
- Pré-traitement
- Normalisation des données (centrer-réduire)
- Encodage "One-hot" pour les mesures catégorielles (ex. sexe)$$x=(0 0 \ldots 0 \underbrace{1}_{i^{\grave{e}me}} 0 \ldots 0)$$
- Utilisation d'un modèle d'apprentissage statistique
- Arbre de décision
- Machine à vecteur de support
- Réseau de neurones
- ...
Exemple
Conclusion
Prédiction de valeurs d'intérêt
- Est-ce que le client va se désabonner
- Quel produit/promotions proposer ?
- ...
Simple à mettre en place
Sensible aux données d'entraînement
Il faut s'assurer de bien échantillonner
Biais possible (ex. jugements aux USA)
On peut utiliser des approches qui corrigent cela (Fairness (machine learning))
Modèles génératifs
Introduction
Modèle génératif
Étant donné les actions $a_1,\ldots,a_{n-1}$ d'un utilisateur, quel va être sa $n+1$ action ?
Les modèles génératifs sont des modèles probabilistes, i.e. on estime
$$P(a_{t+1} | a_1, \ldots, a_t, E) = P(a_{t+1} | a_{1:t}, E)$$où $E$ est l'environnement (i.e. code de la page Web affichée, type d'utilisateur, etc.)
À quoi ça sert ?
Si on sait prédire l'action suivante...
On peut simuler l'utilisateur !
- Comparaison : plus besoin d'A/B testing
- Prédiction : on peut essayer de classifier les utilisateurs
Les deux grandes catégories de modèles utilisateurs
Les modèles sans état
Les utilisateurs ne sont pas spécifiques (un modèle pour tous)
La seule chose qui compte, c'est l'historique $a_{1:t}$
Espaces latents
Les utilisateurs se comportent de façon différente suivant leur type
On représente chaque utilisateur par un vecteur dans $\RR^n$
Les modèles de recommendation (factorisation matricielle)
Cas d'étude : clics d'un utilisateur
Contexte
Modéliser les clics d'un utilisateur
- Dans le cadre d'un moteur de recherche
- On suppose qu'on a une série de $n$ liens
- Sur quels document va t-il/elle cliquer ?
Cas d'étude : clics d'un utilisateur
Il existe beaucoup de modèles : en voici un
Dupret, G. and Piwowarski, B.
2008. A user browsing model to predict search engine click data from past observations. ACM SIGIR.
Après avoir posé une question q, un utilisateur clique sur un document au rang $r$ si
- L'utilisateur examine le document
- Le document est attractif
On estime la probabilité que l'utilisateur clique $c=1$ sachant $d, q$ et $r$ :
$$\begin{eqnarray} P(c = 1 | d, q, r) & = & \sum_{a,e} P(c = 1, a, e | d, q, r) \\ & = & \sum_{a,e} P(c = 1| a, e, {\color{gray} d, q, r}) p(a | d, q, {\color{gray} r, e }) p(e | r, {\color{gray} d, q}) \\ & = & p(a = 1 | d, q) p(e = 1 | r) \end{eqnarray}$$$p(a=1 | d, q) = \alpha_{q,d}$ = probabilité que le document $d$ soit attractif étant donné que la question est $q$
$p(e = 1 | r) = \beta_r$ = probabilité que l'utilisateur examine le rang $r$ ?
Cas d'étude : à quoi ça sert
Apprentissage
On apprend les $\alpha_{q,d}$ et $\beta_r$
par maximum de vraissemblance car on sait si l'utilisateur
a cliqué ou non (utilisation des journaux)
$$\mathcal{L}
= \sum_{(c,q,d,r)\in \mathcal D} \log p(c | q, d, r)
= \sum_{(c,q,d,r)\in \mathcal D} c \times log (\alpha_{q,d} \beta_r) + (1-c) \times log (1-\alpha_{q,d} \beta_r)
$$Utilisation
On peut utiliser $p(a=1 | d, q) = \alpha_{q,d}$ pour estimer la pertinence d'un document (utilisation en Learning To Rank)
On peut estimer une métrique étant donné le comportement d'un utilisateur (i.e. nombre de clics)
Cas d'étude : estimation de métriques
On suppose que la pertinence des documents est connue
$$\mathbb{E}(DCG | L, c_1, \ldots, c_r) = \sum_r G_r c_r$$
Cela correspond à la somme des gains $G_r$ pour les documents cliqués
Avec un modèle plus complexe (l'utilisateur consulte la liste jusqu'à un rang $r$ quoi qu'il arrive)
$$\mathbb{E} ( \text {DCG} | L, C _ { 1 : R } ) = \sum _ { r = 1 } ^ { R } \frac { G _ { r } } { P ( c ^ { + } | e ^ { + } ; L_ { r } ) } c _ { r }$$
Cas d'étude : modèles neuronaux
Modèles à état
Si la tâche est plus complexe, on peut utiliser des modèles... plus complexes
Possibilités
- Modélisation plus fine (variables aléatoires)
- Utilisation de modèles neuronaux (cf. M2 DAC)
Exemple - prédiction de questions
Prédiction de questions (exemple)
- Série de questions
- Modèle = prédiction de la question suivante
Conclusion
Modèles utilisateur
Il en existe plein (probabilistes / neuronaux / ...)
Idée = si on sait simuler l'utilisateur, on peut estimer plein de quantités intéressantes (sans A/B testing)
Moins fiable que A/B testing
Conclusion
Conclusion
La modélisation utilisateur est un sujet très vaste
Ce qu'on a vu (rapidement)
- Visualisation
- A/B testing et interleaving
- Méthodes supervisées
- Modèles utilisateurs