Comment l’apprentissage séquentiel a transformé le ciblage des publicités en ligne

⏱ 8 min

[vc_row][vc_column][vc_column_text]

Vianney Perchet, Professeur à l’École Normale Supérieure Paris-Saclay

Le marché de la publicité sur internet croît à un rythme effréné et génère déjà des milliards de dollars par an, en plus d’un flux de données ahurissant. L’apprentissage automatique (ou machine learning) est un outil de choix pour déterminer quelles publicités afficher, où, quand et à quel prix. Dans ce marché en constante évolution, où chaque jour de nouvelles campagnes de publicités sont lancées, d’autres supprimées, ces algorithmes sont devenus, en quelques années, indispensables : ils doivent être efficaces, très rapides et réactifs. Mais les techniques d’apprentissage classique ne sont pas forcément à la hauteur. On a de plus en plus recours aux algorithmes séquentiels qui s’adaptent et apprennent en temps réel. ¹²

Qu’est-ce que l’apprentissage automatique ? Un ensemble de techniques et d’outils permettant à un ordinateur de réaliser une tâche simple qu’un humain pourrait faire quasiment instantanément comme reconnaître des chiffres manuscrits, des images, des éléments d’une vidéo, jouer à des jeux, conduire une voiture. Une des idées de base est d’avoir à sa disposition un ensemble de données correctement traitées, par exemple une multitude d’images, de chiffres manuscrits correctement étiquetés. À partir de là, les data scientists créent une règle d’étiquetage automatique de nouvelles images en essayant de découvrir naturellement leur structure. On parle d’apprentissage « batch » ou offline, qui peut se résumer ainsi :
À partir d’un grand ensemble de données correctement traitées par des humains dans le passé, trouver ou construire une règle intuitive et naturelle de traitement.

Cela dit, l’apprentissage « humain » ne fonctionne pas de cette façon-là, mais selon un système d’essais-erreurs. Prenons l’exemple d’un enfant apprenant à distinguer les chats des chiens, un exemple classique de classification d’images. Les parents ne lui fournissent pas une liste de centaines de milliers de photos d’animaux pour qu’il apprenne les différences. De la même façon, de manière générale, dans tous les problèmes qui comportent une énorme quantité de données, attendre d’en avoir amassé suffisamment manquerait cruellement de réactivité.

L’enfant procède, sans le savoir, par apprentissage séquentiel

L’apprentissage de l’enfant se fait « petit à petit » : à chaque fois qu’il observe un animal, il le catégorise comme chat ou chien. Les parents se contentent de corriger certaines de ses erreurs. On comprend d’emblée que cette forme d’apprentissage, que l’on appelle séquentiel, a de nombreux avantages. Prenons le cas du ciblage de publicité (on parle parfois de targeting ou retargeting) : procéder ainsi évite d’avoir à collecter un nombre arbitraire et souvent trop grand de données avant de commencer la phase d’apprentissage, le nombre d’exemples s’adaptant automatiquement aux besoins. L’autre intérêt de ce type d’apprentissage est que les capacités de calcul nécessaires sont relativement limitées : après chaque exemple, traité correctement ou non, l’algorithme se met à jour. Or, tout comme un enfant n’est pas capable de faire de tête des multiplications de très grands nombres, les meilleurs ordinateurs ne peuvent pas, du moins suffisamment rapidement, inverser des matrices de tailles gigantesques ou résoudre des problèmes d’optimisation complexes.

Ce concept d’apprentissage séquentiel où les données sont obtenues et traitées à la volée, a en fait été modélisé depuis bien longtemps. La première modélisation est attribuée à Thompson, dans les années 30 (il y a presque un siècle), pour traiter des essais cliniques. L’idée est simple : quand un nouveau médicament est potentiellement disponible sur le marché, il faut effectuer un test clinique pour tester son efficacité ou sa nocivité par rapport au médicament existant. La méthode statistique classique consiste à recruter, disons, 2 000 patients ; à donner à la moitié d’entre eux le nouveau médicament et, à l’autre moitié, le médicament existant. Le remède qui fait preuve du plus haut taux de guérison est déclaré comme étant le meilleur.
Ce processus a un défaut considérable : le nouveau médicament est peut-être hautement létal. Donc 1 000 patients peuvent décéder durant le test. Comment éviter cela ? Wald, dans les années 1950, a développé une théorie, proche de l’apprentissage séquentiel, qui consiste à arrêter le test au moment le plus opportun, autrement dit, bien avant 1 000 décès. Thompson, quant à lui, a affirmé qu’il n’était pas nécessaire d’affecter les patients à part égale. Selon lui, il est bien plus efficace et intéressant de leur donner l’ancien ou le nouveau médicament de manière dynamique et aléatoire, en se basant sur les observations précédentes et en augmentant progressivement la proportion allouée au meilleur médicament.

Mais la mise en pratique de ces idées est bien plus complexe qu’il n’y paraît, et de nombreux articles en débattent encore. L’un des problèmes de la procédure de Thompson est qu’elle nécessiterait souvent près d’un siècle de traitement clinique pour converger… Les patients seraient morts de vieillesse avant ! Il a donc fallu adapter ses idées aux contraintes réelles ³.

Les « bandits-manchots » à la rescousse

Ce modèle d’essai clinique aléatoire a été baptisé modèle « bandits-manchots » en référence aux machines à sous des casinos. Voici comment peut se résumer le problème du point de vue mathématique. Imaginons une personne entrant dans un casino et faisant face à une rangée de bandits-manchots. Il y a potentiellement, parmi eux, une machine dont le rendement est meilleur que les autres. L’objectif du parieur est de construire une stratégie (un algorithme) pour jouer successivement sur telle ou telle machine, dans le but de trouver la meilleure, et cela le plus rapidement possible ! Ce type de problématique se rencontre dans de multiples situations telles que le choix du chemin à prendre en voiture (petites routes ou autoroute ?), la sélection de portefeuille en finance (parier sur un actif risqué ou non ?), etc. De même, les publicités peuvent être perçues comme une multitude de machines à sous virtuelles, dont les rendements sont inconnus et probablement différents.

Revenons à nos bandits-manchots et à l’algorithme de notre parieur. La mesure de performance de l’algorithme est la différence entre le paiement cumulé obtenu grâce à la machine optimale et le paiement cumulé effectivement obtenu. On parle du « regret de l’algorithme » : c’est la différence entre ce que le parieur aurait pu gagner, s’il avait eu connaissance de la machine optimale, et ce qu’il a effectivement gagné. Autrement dit, le regret est le coût effectif de la phase d’apprentissage. Le but est évidemment de le minimiser.

La difficulté de ce problème est que les données accumulées ne concernent que les machines utilisées. Il est impossible de savoir ce qu’une machine aurait donné sans la tester. De la même façon, il est impossible de savoir si une publicité est pertinente sans jamais l’afficher. Autrement dit, pour avoir de l’information, il est nécessaire de la payer. Si le parieur se focalise sur la machine qui lui paraît la meilleure, il ne pourra pas affiner sa connaissance de la performance des autres machines (il risquera donc de se tromper pour toujours). En apprentissage séquentiel, ce concept d’acquisition ou d’utilisation de l’information, qu’on appelle le « compromis exploration/exploitation », est crucial.

Les stratégies classiques pour optimiser ce compromis reposent sur l’idée de « renforcement ». Plus une machine a été performante dans le passé, plus il est a priori intéressant d’augmenter la proportion du temps à jouer avec elle. Cela dit, l’analyse mathématique est délicate : il s’agit de trouver la proportion minimale de temps passé sur les machines sous-optimales (de sorte à minimiser les pertes), tout en laissant suffisamment de place à l’exploration (pour se rendre compte rapidement de son erreur, le cas échéant).

Ce concept qui consiste à miser de plus en plus sur les stratégies prometteuses est d’ailleurs devenu une discipline à part entière que l’on appelle l’apprentissage par renforcement. Il est très utilisé par exemple dans l’apprentissage de robots, ou plus récemment pour construire une IA capable de jouer aux jeux comme le Go ou le poker (possiblement avec l’aide d’autres techniques venant de l’apprentissage profond) ou dans les jeux vidéo pour éviter de coder à la main toutes les règles. Avec le succès considérable que l’on connaît.

Désormais au service d’internet

Les bandits-manchots ont connu leur heure de gloire dans les années 80-90 avant de tomber un peu en désuétude, notamment par manque d’applications concrètes. C’est le développement d’internet, à la fin des années 90, qui les a remis sur les devants de la scène, notamment pour cibler les publicités.

Avant cela, ils ont permis d’optimiser certains moteurs de recherche (avant d’être largement supplantés par des algorithmes offline). Chaque requête peut être formulée comme un problème de bandits-manchots, où les machines sont des pages web. L’objectif du moteur de recherche est de mettre en avant la page la plus intéressante : celle qui a la plus grande probabilité d’être cliquée, le but étant de maximiser les nombres de clics sur ses premières réponses. De la même façon, dans le cas de la publicité, les sites web sont récompensés si l’utilisateur clique sur l’une d’entre elle. Le but est donc de trouver le plus rapidement possible la publicité avec le meilleur taux de clics.

Outre la publicité en ligne, les algorithmes séquentiels ont de nombreuses applications possibles, par exemple pour tester les nouvelles fonctionnalités d’un site (nouvelle couleur, mise en page, etc.). Au lieu de faire ce qu’on appelle un « A/B test » qui consiste à couper la population des utilisateurs en deux et comparer les performances des deux modèles, on peut utiliser un découpage adaptatif. De même, l’apprentissage séquentiel est très utilisé dans les systèmes de recommandation de produits (« les utilisateurs qui ont acheté ce produit ont aussi aimé ceux-ci »).

Ces nouvelles problématiques sont très intéressantes. Elles posent des problèmes inédits qui remettent en cause les fondements mêmes des algorithmes classiques, inefficaces mais surtout inadaptés. Il y a plusieurs raisons à cela : les espaces de décision sont de taille gigantesque (à cause, par exemple, de la combinatoire de l’espace des recommandations possibles de produits), les données n’ont pas les propriétés « classiques » de stationnarité et d’indépendance (elles évoluent et peuvent même parfois s’adapter à l’algorithme), les observations ne sont pas binaires (un site affiche une liste de recommandations, l’utilisateur les parcourt dans un certain ordre et prend éventuellement une décision), les données sont obtenues avec un certain délai, etc. ⁴ Autant de caractéristiques qui imposent des algorithmes adaptatifs, évolutifs, robustes mais sans être trop rigides.

Internet a créé un véritable bac à sables de problèmes pour les data scientists, chacun ayant ses particularités et ses contraintes. Cette diversité et cette grande complexité rend leur résolution bien plus intéressante et passionnante que les modèles parfois trop théoriques et abstraits.

[/vc_column_text][/vc_column][/vc_row][vc_row][vc_column][vc_empty_space][/vc_column][/vc_row][vc_row][vc_column][vc_empty_space][vc_column_text css= ».vc_custom_1508831756462{background-color: rgba(102,102,204,0.5) !important;*background-color: rgb(102,102,204) !important;} »]

Les bandits-manchots en bannière

“L’apprentissage séquentiel est un outil indispensable pour intégrer rapidement de nouveaux clients, de nouveaux types de bannières, des produits qui viennent de sortir, etc. Cela permet d’avoir des campagnes publicitaires réactives aux changements, ce qui est crucial dans un contexte aussi dynamique que le commerce en ligne. Chez Criteo, nous utilisons des algorithmes de bandits-manchots, entre autres, pour tester tous les nouveaux formats de bannières que nous créons et ne garder que les plus performants.”

Clément Calauzènes, Lead Researcher chez Criteo, entreprise française cotée au Nasdaq, acteur majeur du marché de ciblage des publicités https://www.criteo.com/[/vc_column_text][/vc_column][/vc_row][vc_row][vc_column][vc_empty_space][/vc_column][/vc_row][vc_row][vc_column][vc_column_text css= ».vc_custom_1508831609496{background-color: rgba(102,102,204,0.5) !important;*background-color: rgb(102,102,204) !important;} »]

La guerre des publicités est en marche

Les algorithmes séquentiels n’interagissent pas seulement avec des utilisateurs d’internet. Ils sont parfois en compétition entre eux, notamment pour les publicités en ligne. Concrètement, à chaque chargement d’une page web, il y a une enchère entre les différents annonceurs pour déterminer qui a le droit d’afficher une publicité. Pour apprendre la meilleure stratégie d’enchères, les entreprises publicitaires utilisent entre autres des algorithmes séquentiels. Mais le site web peut également choisir son propre système d’enchères (au premier prix, second prix, avec ou sans réserve, etc.). Son optimisation dépend des stratégies d’enchères des entreprises en lice, autrement dit de leurs algorithmes d’apprentissage. Dans un tel système, les données sont donc obtenues suite à des interactions avec des compétiteurs aux intérêts divergents. Sans compter que tous ces agents ont également la possibilité de modifier leur stratégie pour essayer d’induire en erreur leurs adversaires, puis d’exploiter ces erreurs ! La route est encore longue pour construire des algorithmes d’apprentissage efficace et robuste contre des adversaires…[/vc_column_text][vc_empty_space][/vc_column][/vc_row][vc_row][vc_column][vc_column_text]

Références pour aller plus loin

¹ S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5:1–122, 2012. https://arxiv.org/abs/1204.5721

² M. Faure, P. Gaillard, B. Gaujal and V.Perchet. Online learning and game theory. A quick overview with recent results and applications ESAIM Proceedings and Surveys – work in Progress, 2016.
https://hal.inria.fr/hal-01237039

³ V. Perchet, P. Rigollet, S. Chassang, and E. Snowberg. Batched bandit problems. Annals of Statistics, 44 : 660-681, 2016
https://arxiv.org/abs/1505.00369

⁴ C. Vernade, V. Perchet and O. Cappé. Stochastic Bandit Models for Delayed Conversions, Conference on Uncertainty in Artificial Intelligence (UAI), 2017
https://arxiv.org/abs/1706.09186[/vc_column_text][/vc_column][/vc_row]