Apprentissage séquentiel pour la diffusion d’information

Motivés par les scénarios de diffusion de l’information et de publicité dans les réseaux sociaux, nous étudions un problème de maximisation de l’influence (MI) dans lequel on suppose que l’on en sait peu sur le réseau de diffusion ou sur le modèle qui détermine comment l’information peut se propager. Dans un tel environnement incertain, on peut se concentrer sur des campagnes de diffusion à plusieurs tours, avec l’objectif de maximiser le nombre d’utilisateurs distincts qui sont influencés ou activés, à partir d’une base de nœuds influents. Au cours d’une campagne, les graines de propagation sont sélectionnées séquentiellement lors de tours consécutifs, et les commentaires sont collectés sous la forme des nœuds activés à chaque tour L’impact (récompense) d’un tour est alors quantifié par le nombre de nœuds nouvellement activés. En général, il faut maximiser la propagation totale de la campagne, comme la somme des récompenses des tours. Nous considérons deux sous-classes de d’IM, Contextual Influence Maximization with Persistence (CIMP) et Episodic Contextual Influence Maximization with Persistence (ECIMP), où (i) la récompense d’un tour d’une campagne en cours consiste uniquement en de nouvelles activations (non observées lors des tours précédents de cette campagne), (ii) le contexte du tour et les données historiques des tours précédents peuvent être exploités pour apprendre la meilleure politique, et (iii) ECIMP est CIMP répété plusieurs fois, ce qui permet d’apprendre également des campagnes précédentes. Ce problème est directement motivé par les scénarios du monde réel de la diffusion de l’information dans le marketing d’influence, où (i) seule la première / unique activation d’un utilisateur cible présente un intérêt (et cette activation persistera comme une activation acquise, latente, tout au long de la campagne). (ii) de précieuses informations secondaires sont disponibles pour l’agent d’apprentissage Dans ce contexte, une approche d’exploration-exploitation pourrait être utilisée pour apprendre les principaux paramètres de diffusion sous-jacents, tout en exécutant les campagnes. Pour CIMP, nous décrivons et comparons deux méthodes de bandits à bras multiples contextuels, avec des limites supérieures de confiance sur le potentiel restant des influenceurs, l’une utilisant un modèle linéaire généralisé et l’estimateur de Good-Turing pour le potentiel restant (GLM-GT-UCB), et l’autre adaptant directement l’algorithme LinUCB à notre cadre (LogNorm-LinUCB). Pour ECIMP, nous proposons l’algorithme LSVI-GT-UCB qui implémente le principe d’optimisme face à l’incertitude pour l’apprentissage par renforcement, avec approximation linéaire. L’agent d’apprentissage estime pour chaque nœud de départ son potentiel restant avec un estimateur de Good-Turing, modifié par une fonction Q estimée. Nous montrons qu’ils surpassent les performances des méthodes de base utilisant les idées les plus récentes, sur des données synthétiques et réelles, tout en présentant un comportement différent et complémentaire, selon les scénarios dans lesquels ils sont déployés.

Composition du jury

• Michalis VAZIRGIANNIS, Rapporteur & Examinateur, Professeur, École Polytechnique / LIX
• Stratis IOANNIDIS, Rapporteur & Examinateur, Professeur, Northeastern University, Boston, MA, USA / SPIRAL
• Pablo PIANTANIDA, Examinateur, CNRS, Professeur, Université Paris-Saclay / ILLS
• Vincent TAN, Examinateur, Professeur, National University of Singapore / IDS
• Fatiha SAÏS, Examinatrice?Professeur, Université Paris-Saclay / LISN