3.1 – Contexte

9Notre objectif est de construire un système permettant de capturer des données pertinentes à partir des API proposées par les médias sociaux. Étant donné que les API limitent généralement le nombre d’utilisateurs pouvant être suivis de façon simultanée, l’objectif est de sélectionner dynamiquement ceux qui sont susceptibles de publier des contenus pertinents relativement à un besoin prédéfini. Il est important de noter que, quand bien même il n’y aurait pas de telles restrictions, notre approche reste valide vu l’énorme quantité de données publiées. La principale difficulté est donc de sélectionner efficacement les comptes à suivre étant donné le grand nombre d’utilisateurs et sachant qu’au début du processus, aucune information sur ces derniers n’est connue. En outre, même si certains comptes spécifiques pourraient être trouvés manuellement, le changement dynamique des sources semble complexe à réaliser manuellement. Pour ces raisons, la construction d’une solution automatique pour orienter le choix des sources apparaît pertinente.

3.2 – Un processus de décision sous contraintes

10Notre tâche revient à sélectionner à chaque itération t un sous-ensemble K_t de k profils à suivre parmi l’ensemble de tous les utilisateurs

11

12Notons que, contrairement à la majorité des tâches classiques en recherche information, nous ne nous préoccupons pas ici de la précision des informations collectées. L’objectif est de maximiser le volume de messages pertinents collectés, un filtrage pouvant être éventuellement appliqué a posteriori. Cet aspect diffère des tâches habituelles en recherche d’information. Les scores de pertinence considérés dépendent d’un besoin d’information, défini par l’utilisateur du système, pouvant prendre des formes variées. Par exemple, l’utilisateur pourrait souhaiter suivre des profils actifs sur des thématiques précises, ou bien des profils influents (au sens où leurs messages sont souvent repostés par d’autres utilisateurs). Ces scores peuvent soit être assignés manuellement, relativement à une évaluation humaine des contenus, ou bien automatiquement, par exemple à l’aide d’un classifieur (voir section 5). Dans (Gisselbrecht et al., 2015) les auteurs se basent sur une hypothèse de stationnarité des scores associés à chaque utilisateur, ce qui parait une hypothèse peu réaliste sur des réseaux sociaux généralistes tels que Twitter, où les utilisateurs peuvent changer de centre d’intérêt à tout moment. Nous supposons ici qu’il est possible de mieux anticiper le comportement futur des utilisateurs (i.e. les contenus futurs) en considérant leur activité présente (i.e. les contenus déjà postés). En d’autres termes, si l’on représente l’activité de l’utilisateur a au temps t – 1 par un vecteur z_a,t ∈ ℝ^d, il existe une fonction h : ℝ^d → ℝ permettant d’expliquer le score de a au temps t. Cette fonction de corrélation doit être apprise au fur et à mesure du processus de décision. Cependant, la maximisation de la fonction définie dans la formule 1 est contrainte par différents facteurs :

• les scores de pertinences r_a,t sont seulement définis pour les utilisateurs suivis à l’itération t (i.e. pour les a ∈ K_t) ;
• les vecteurs de contextes z_a,t sont seulement observés pour un sous-ensemble O_t des utilisateurs (i.e. il est impossible d’observer la totalité de l’activité du réseau).

13Ces contraintes proviennent des restrictions liées aux API de streaming que nous utilisons pour la collecte des données :

• d’une part, une API Sample streaming, qui renvoie en temps réel 1 % de tous les tweets publics. Nous utilisons cette API pour découvrir de nouveaux utilisateurs mais aussi pour récolter les contextes (activités) d’un grand nombre d’utilisateurs actifs à un moment donné ;
• d’autre part, une API Follow streaming, qui permet d’obtenir en temps réel les contenus produits par 5000 utilisateurs définis. Nous utilisons cette API pour capturer les données produites par les utilisateurs sélectionnés par notre système.

14Pour les profils appartenant à O_t, les scores de pertinences peuvent être estimés grâce à la fonction de corrélation h, qui traduit les variations temporelles de la qualité d’un utilisateur. En revanche, pour les autres, nous proposons de considérer le cas stationnaire, en introduisant une tendance générale (ou qualité intrinsèque) pour chaque utilisateur. Nous sommes alors face à un problème hybride, où les contextes observés sont utilisés pour prédire des variations autour d’une utilité moyenne estimée.

3.3 – Description du système

15La figure 1 illustre le fonctionnement général du système. Ce dernier réitère les mêmes actions à chacune des itérations (trois itérations sont représentées). Au début de chaque étape, la politique de sélection des sources choisit un ensemble d’utilisateurs à suivre (K_t) parmi tous les utilisateurs connus du système (K), selon des observations et des connaissances fournies par un module d’apprentissage. Ensuite, les messages postés par les k profils sélectionnés sont collectés via l’API Follow streaming. Comme nous pouvons le voir dans la partie centrale du schéma, après avoir suivi les utilisateurs de K_t pendant l’itération courante t, les messages collectés sont analysés (soit par un humain, soit automatiquement) et le résultat - traduisant la pertinence - est renvoyé au module d’apprentissage. En parallèle, à chaque itération, l’activité courante de certains utilisateurs est capturée par l’API Sample streaming. Cela nous offre la possibilité d’enrichir la base des utilisateurs potentiels K, mais aussi de construire l’ensemble des utilisateurs dont on connaît le contexte. Chaque profil ayant publié au moins un message parmi ceux qui ont été collecté via l’API Sample streaming à l’étape t sont inclus dans O_t+1, les messages d’un même auteur a étant concaténés pour former z_a,t+1 (voir la partie 5 pour des exemples de construction de vecteurs de contexte à partir des messages). À cet ensemble sont ajoutés les utilisateurs de K_t, puisque leur activité complète a été suivie pendant l’étape t.

Figure 1

Illustration du système

Illustration du système

4.1 – Une approche de bandit contextuel

16Dans le problème du bandit contextuel, l’hypothèse classique considère l’existence d’un vecteur inconnu β ∈ ℝ^d permettant d’estimer l’espérance de récompense que l’on peut observer pour chaque action et à chaque itération du processus :

17

18Cette formulation correspond à un cas particulier de l’algorithme LinUCB hybride proposé dans (L. Li et al., 2010) en considérant une valeur de 1 pour la valeur du contexte propre à chaque action. Il est important de noter que plusieurs paramètres individuels auraient pu être considérés dans notre étude, cependant cette approche ne nous semble pas adaptée étant donné le nombre très élevé d’actions disponibles (qui mènerait à un apprentissage d’autant plus complexe). D’autre part, l’utilisation d’un vecteur de paramètres commun permet une exploration facilitée, cela permettant la généralisation de corrélations observées pour des utilisateurs à l’ensemble des utilisateurs à l’activité courante proche. Ainsi, nous restreignons la modélisation individuelle à un terme unique de biais. Comme précisé plus haut, notre tâche nécessite la sélection de multiples actions simultanément et donc à chaque itération t, l’algorithme doit sélectionner k (k < K) utilisateurs parmi un ensemble de K, selon les contextes observés et les qualités intrinsèques de ces derniers. Le gain obtenu après une période d’écoute correspond donc à la somme des gains individuels. Dans notre cas, une difficulté majeure provient du fait que tous les contextes ne sont pas observables, contrairement aux problèmes de bandits contextuels traditionnels. Dans la suite de ce travail, nous considérons pour chaque utilisateur une probabilité p_a (0 < p_a < 1) de révéler son contexte. Notons que cette probabilité est contrainte par le problème considéré. Il s’agit alors de choisir à chaque itération t les k meilleurs utilisateurs à suivre parmi les K utilisateurs de

4.2 – Une approche contextuelle pour la collecte de données dynamique

19Afin de dériver notre algorithme de collecte, nous considérons les hypothèses suivantes :

• Vraisemblance : les scores de récompense sont identiquement et indépendamment distribués selon les contextes observés : , avec λ_a correspondant à la variance de l’écart entre la récompense r_a,t et l’application linéaire de prédiction  ;
• Prior : les paramètres inconnus sont normalement distribués autour de l’origine : et , où b et ρ_a permettent de contrôler la variance des paramètres et est la matrice identité de taille d (taille des vecteurs de contexte).

20L’idée est alors de construire un estimateur des paramètres β et θ par maximum a posteriori connaissant les récompenses collectées, et les contextes associés, jusqu’à l’itération courante. Pour simplifier, nous fixons b, ρ_a et λ_a à 1 pour tout a. Cependant, tous les résultats peuvent être étendus à des cas plus complexes.

21Proposition 1. — En notant T_a l’ensemble des itérations où a a été choisi durant les n premières étapes

22

23Preuve 2. — Voir Annexe A.

24Notons que tous ces paramètres possèdent une dépendance en t, que nous avons volontairement omise afin d’alléger les notations. De plus tous ces paramètres peuvent être mis à jour de façon peu coûteuse à mesure que de nouveaux exemples d’apprentissage arrivent (la complexité de la mise à jour des paramètres est constante sur l’ensemble du processus). En combinant les équations 2, 3 et 4, la valeur espérée

25

26Théorème 3. — Pour tout 0 < δ < 1 et

27

28Preuve 4. — Voir Annexe B.

29Cette formule peut directement être utilisée pour définir une borne supérieure de l’intervalle de confiance (UCB - Upper Confidence Bound) de la récompense espérée pour chaque utilisateur dont le contexte a été observé pour l’itération t :

30

31De manière classique, les approches type UCB étant des approches optimistes, l’idée est alors de sélectionner à chaque instant t les k utilisateurs ayant les k bornes s_a,t les plus élevées. Nous rappelons qu’une formulation similaire est utilisée dans le bandit contextuel traditionnel. Dans la partie suivante, nous proposons une méthode permettant d’adapter cette dernière au cas où l’on ne peut pas observer tous les contextes.

4.3 – Prise en compte des utilisateurs avec contexte caché

32Ces scores permettant de sélectionner les utilisateurs à écouter ne peuvent pas être calculés lorsque les contextes z_a,t ne sont pas observés (i.e. lorsque les utilisateurs ne sont pas dans O_t). Cela nécessite donc une méthode permettant de qualifier les personnes dont le contexte est inconnu. De plus, cela implique des problématiques de mise à jour des paramètres appris lorsqu’un utilisateur a été écouté mais dont le contexte n’a pas été révélé. Bien qu’il soit tentant de penser que le paramètre β commun à tous et les paramètres individuels θ_a peuvent être appris séparément, ces derniers sont en réalité corrélés, comme le montrent les formules 3 et 4. Il est important de remarquer que pour conserver les garanties probabilistes, les paramètres du problème ne devraient être mis à jour que lorsqu’un profil appartient à K_t ∩ O_t. Remplacer T_a par

33Nouvelles notations

• L’ensemble des itérations où le contexte de a a été observé au bout de n étapes est noté avec  ;
• La moyenne empirique des vecteurs de contexte de l’utilisateur a est noté avec . Remarquons que est différent de car le premier est mis à jour à chaque fois que le contexte est observé tandis que le second l’est uniquement lorsque l’utilisateur a été observé et sélectionné lors d’une même itération.

34Hypothèses supplémentaires

• Sans perte de généralité, nous supposons que β est borné par M ∈ ℝ^+∗, i.e. ||β|| ≤ M, où || || désigne la norme L² sur ℝ^d ;
• Pour tout a et à chaque t, les contextes z_a,t ∈ ℝ^d sont iid depuis une distribution inconnue de moyenne et variance Σ_a finie, et que Trace(Σ_a) ≤ S, avec S ∈ ℝ^+∗.

35Théorème 5. — Étant donné 0 < δ < 1, 0 < δ₁ < 1. Alors pour tout a après t itérations du processus :

36

37Où

38Preuve 6. — Voir Annexe C.

39Ainsi, l’inégalité ci-dessus nous donne une borne relativement serrée de l’intervalle de confiance associé à la récompense espérée de l’utilisateur a, d’où nous pouvons dériver un nouveau score de sélection. À chaque itération t, si le contexte de a n’est pas observé :

40

41Notons que le terme d’exploration supplémentaire

4.4 – Algorithme de capture de connées contextuel

42Les ensembles et paramètres manipulés sont tout d’abord initialisés :

• A₀ par une matrice identité de taille d × d et b₀ par un vecteur nul de taille d, avec d la taille des vecteurs de contexte ;
• K par l’ensemble vide ;
• O₁ par les utilisateurs auteurs de messages collectés au cours d’une première utilisation de l’API Sample pendant une période de temps d’une durée L. La représentation des messages de ces utilisateurs a ∈ O₁ correspondent à leur contexte z_a,1.

43L’algorithme complet est disponible en Annexe D, il procède, pour chaque itération t de la collecte selon :

1. Insertion dans K de chaque utilisateur de O_t n’en faisant pas encore partie (en limitant le nombre de nouveau entrants à newMax utilisateurs par itération afin d’éviter une sur-exploration pour le cas des très grands réseaux tels que Twitter) ;
2. Mise à jour des moyennes empiriques des contextes pour les profils de O_t ;
3. Calcul de l’estimateur du paramètre (voir proposition 1) ;
4. Calcul des scores de sélection s_a,t de tous les utilisateurs dans K, selon la formule 7 pour les utilisateurs de O_t et selon la formule 9 ceux de . Le score des nouveaux utilisateurs est fixé à +∞ pour forcer le système à les choisir une première fois ;
5. Sélection des k profils ayant les meilleurs scores s_a,t ;
6. Capture simultanée via les APIs Sample et Follow pendant une période de durée L. L’API Follow écoute les k utilisateurs sélectionnés K_t ;
7. Calcul des récompenses des messages collectés pour les utilisateurs de K_t à partir de l’API Follow, puis mise à jour des paramètres du modèle ;
8. Mise à jour de l’ensemble des utilisateurs observés O_t+1, et des contextes associés, en considérant tous les utilisateurs pour lesquels au moins un message a été collecté pendant l’itération t (provenant soit de l’API Sample soit de l’API Follow) ;

5.1 – Description générale

44Outre une politique (appelée Random) sélectionnant uniformément les utilisateurs à suivre à chaque itération, nous comparons notre approche de collecte à deux autres algorithmes de bandits : CUCB et CUCBV respectivement proposés dans (Qin et al., 2014) et (Gisselbrecht et al., 2015). Ces algorithmes ne prennent pas en compte les contextes des actions. Dans toutes nos expérimentations, nous fixons les paramètres suivants : 1) Le terme d’exploration à α = 1, 96, ce qui correspond à un intervalle de confiance à 95 % pour l’estimation de l’espérance de la récompense d’une action lorsque son contexte est observé ; 2) Le nombre d’utilisateurs pouvant être ajoutés à K à chaque itération à newMax = 200.

5.2 – Expérimentations hors ligne

45Deux jeux de données sont utilisés pour nos expérimentations hors ligne :

1. USElections : jeu de données de 2 148 651 messages collectés pendant les dix jours précédents les élections présidentielles américaines de 2012. Ces messages correspondent à la totalité de ceux postés pendant cette période par les 5 000 premiers utilisateurs à avoir utilisé les mots “Obama”, “Romney” ou “#USElections” ;
2. Libya : jeu de données de 1 211 475 messages provenant de 17 341 utilisateurs. Ces messages correspondent à l’ensemble de ceux postés sur une période de trois mois contenant le mot clé “Libya”.

46Modèle de contexte : dans nos expérimentations, nous considérons que le contexte z_a,t d’un utilisateur a pour une itération t correspond à une représentation de la concaténation des messages collectés pour cet utilisateur pendant l’étape t − 1 selon l’une des deux APIs. Plutôt que d’utiliser directement une représentation fréquentielle en sac de mots, ce qui impliquerait de très longs vecteurs de contextes et un coût important lié à l’inversion des matrices requise lors de la mise à jour des paramètres, nous appliquons une réduction de dimensions à un espace de 30 concepts par l’emploi de l’algorithme LDA (Blei et al., 2003). Outre une réduction de la complexité, l’utilisation de cet algorithme permet une meilleure généralisation des observations en regroupant sous un même concept des mots sémantiquement proches.

47Modèle de récompense : nous nous intéressons à des modèles de collecte visant à récompenser les messages ayant un fort impact sur une thématique donnée. Quatre thématiques sont considérées (correspondant à 4 différents modèles de récompense) : politique, religion, sport et science. L’appartenance à l’une de ces 4 thématiques se fait par l’application d’un classifieur linéaire entraîné sur le corpus 20 Newsgroups. Ainsi, si un message correspond à la classe de la thématique recherchée, le score de récompense qui y est associé est alors égal au nombre de fois où ce message est reposté (retweeté sur Twitter) par d’autres utilisateurs pendant l’itération courante.

48Afin d’obtenir des résultats généralisables, nous avons expérimenté plusieurs configurations de collecte en considérant plusieurs valeurs pour p, la probabilité d’observation des contextes, k, le nombre d’utilisateurs pouvant être suivis simultanément, et L, la durée d’une itération. Plus précisément nous avons testé toutes les combinaisons possibles avec p ∈ {0, 1 ; 0, 5 ; 1}, k ∈ {50 ; 100 ; 150} et L ∈ {2 ; 3 ; 6 ; 10} minutes. Néanmoins, pour des raisons de places, nous reportons seulement les résultats pour k = 100, L = 2. De la même façon, pour le jeu de données USElections, seule les expérimentations considérant le modèle de récompense centré sur la classe politique sont reportées, tandis que pour le jeu de données Libya, seul celui centré sur la classe religion l’est. Des tendances similaires ont été observées pour les autres configurations et modèles de récompense.

49Résultats : les figures 2a et 2b représentent le gain cumulé en fonction du temps respectivement pour USElections et Libya. Tout d’abord, nous remarquons que chaque politique fonctionne mieux que la politique Random, ce qui est un premier élément pour affirmer la pertinence des algorithmes de bandit pour la tâche en question. Nous notons également que CUCBV fonctionne mieux que CUCB, ce qui confirme les résultats obtenus dans (Gisselbrecht et al., 2015) sur une tâche similaire de capture de données ciblée. Plus intéressant, lorsque chaque contexte est observable (p = 1), notre algorithme contextuel fonctionne mieux que les approches CUCB et CUCBV. Ce résultat montre que nous sommes en mesure de mieux anticiper les utilisateurs qui vont être les plus pertinents à l’étape suivante, compte tenu de ce qu’ils ont dit juste avant. Cela confirme aussi le comportement non-stationnaire des utilisateurs. Par exemple, les utilisateurs peuvent parler de science au cours de la journée tout en étant plus axé sur le sport quand ils reviennent à la maison. Considérer les contextes permet également de converger plus rapidement vers les utilisateurs intéressants puisque tous les comptes partagent le même paramètre β. En outre, les résultats montrent que, même pour de faibles probabilités d’observation des contextes p, notre politique contextuelle se comporte beaucoup mieux que les approches non-contextuelles, ce qui valide empiriquement notre approche : il est possible de tirer parti de l’information contextuelle, même si une grande partie de cette information est cachée. En particulier, pour le jeu de données Libya où aucune différence significative entre les deux algorithmes CUCB et CUCBV n’est remarquable, notre algorithme semble plus approprié. En donnant la possibilité de sélectionner des utilisateurs même si leur contexte est inconnu, nous permettons à l’algorithme de compléter sa sélection en choisissant les utilisateurs dont le contexte moyen correspond à un profil appris. Si aucun utilisateur dans O_t ne semble actuellement pertinent, l’algorithme peut alors compter sur les utilisateurs avec une bonne qualité intrinsèque moyenne. Numériquement pour k = 100, le nombre moyen d’utilisateurs sélectionnés pour lesquels le contexte a été observé à chaque pas de temps est de 43 pour p = 0, 1 et 58 pour p = 0, 5, ce qui confirme que l’utilisation de contextes intéressants lorsque ceux-ci sont disponibles, tout en conservant une probabilité de sélection non négligeable pour les utilisateurs de qualité dont le contexte n’est pas connu.

5.3 – Expérience en ligne

50Nous considérons notre tâche de collecte dans une expérimentation en ligne sur Twitter prenant en compte l’ensemble du réseau social ainsi que les contraintes de l’API. Pour ces expériences, nous avons utilisé tout le potentiel de l’API Twitter, à savoir 1 % de tous les tweets publics pour l’API Sample, qui s’exécute en arrière-plan, et 5 000 utilisateurs suivis simultanément (k = 5000) pour l’API Follow. À chaque itération, les utilisateurs sélectionnés sont suivis pendant L = 15 minutes. Compte tenu des restrictions de Twitter, chaque expérience nécessite un compte développeur, ce qui limite le nombre de politiques que nous pouvons tester en parallèle. Nous avons choisi de tester les quatre stratégies suivantes : notre approche contextuelle, CUCBV, Random et une autre appelée Static, qui suit les mêmes 5 000 comptes, sélectionnés a priori, à chaque étape du processus. Les 5 000 comptes suivis par l’approche Static ont été choisis en sélectionnant les 5 000 utilisateurs ayant cumulé le plus fort volume de récompenses selon les messages collectés par l’API Sample sur une période de 24 heures. Pour information, certains comptes célèbres tels que @dailytelegraph, @Independent ou @CNBC en faisaient partie.

51Résultats : la figure 2c représente l’évolution du gain cumulé sur deux semaines pour les quatre algorithmes. On remarque le très bon comportement de notre algorithme dans un scénario réel, car la somme des récompenses qu’il accumule croît beaucoup plus rapidement que celle des autres politiques, surtout après les 500 premières itérations. Après ces premières itérations, notre algorithme semble avoir acquis une bonne connaissance sur les distributions de récompenses en fonction des contextes observés sur les différents utilisateurs du réseau. Afin d’analyser le comportement des politiques expérimentées pendant les premières itérations, nous représentons aussi dans la figure 2d un zoom des mêmes courbes sur les 150 premiers pas de temps. Au début, la politique Static est plus performante que toutes les autres, ce qui peut s’expliquer par deux raisons : 1) les algorithmes de bandits utilisés ont besoin de sélectionner tous les utilisateurs au moins une fois pour initialiser les scores et 2) les utilisateurs faisant partie de l’ensemble Static sont supposés être des sources relativement pertinentes étant donné la façon dont ils ont été choisis. Vers l’itération 80, aussi bien l’algorithme CUCBV que l’algorithme contextuel deviennent meilleurs que Static, ce qui correspond au moment où ils commencent à pouvoir exploiter des “bonnes” actions identifiées. Ensuite, une période d’environ 60 itérations est observée (approximativement entre les itérations 80 et 140), au cours de laquelle l’algorithme CUCBV et notre approche contextuelle ont des performances comparables. Cette période s’explique par le fait que notre approche nécessite un certain nombre d’itérations pour apprendre des corrélations efficaces entre contextes et récompenses afin d’en tirer avantage. Enfin, après cette période d’initialisation, on peut remarquer un changement significatif de pente pour la courbe correspondant à notre algorithme, ce qui souligne sa faculté à être bien plus réactif dans un environnement dynamique.

Figure 2

Récompense cumulée en fonction du temps. (a) USElections/politique. (b) Libya/religion. (c) expérience en ligne. (d) expérience en ligne avec un zoom sur les premiers pas de temps