Filtrage Top k

Top-k est une fonctionnalité de Pub/Sub permettant d’envoyer une publication uniquement aux k meilleurs abonnés. Le filtrage Top-k calcule le score de chacun, puis les classe par ordre décroissant et choisit les k meilleurs abonnés. Le filtrage Top-k a été utilisé dans certains travaux précédents, comme dans Shraer, Gurevich, Fontoura & Josifovski (2014), où les auteurs proposent d’afficher seulement les Top-k tweets sur chaque story social dans un site Web proposant un nombre élevé de d’actualités et de vues, afin de réduire les coûts de ressources. La sélection des tweets est basée d’abord sur le modèle Pub/Sub puis sur une fonction de score évaluant le contenu et la récence. D’une autre manière, Top-k est défini dans Zhang, Sadoghi, Muthusamy & Jacobsen (a) pour fournir une publication uniquement aux k abonnés les mieux classés en utilisant la notion de couverture des abonnements (covering) pour les applications à grande échelle. Le filtrage Top-k est également utilisé dans Zhang, Sadoghi, Muthusamy & Jacobsen (2013) pour réduire le nombre de notifications envoyées dans les réseaux sociaux. Dans Chen, Cong, Cao & Tan (2015), les auteurs proposent une nouvelle solution pour gérer un grand nombre de requêtes de type Temporal Spatial-Keyword Top-k TaSK dans le flux d’objets de type géographique. Mais, le filtrage Top-k n’a été jamais utilisé auparavant dans le contexte de la publicité RTB selon notre connaissance. Dans notre travail, nous l’utilisons comme méthode pour sélectionner les DSPs les plus offrants pour une publication donnée.

Dans cette section, nous avons présenté un bref résumé des solutions les plus pertinentes par rapport à notre problème de recherche. D’abord, les solutions proposées dans le domaine de RTB sont presque toutes dirigées vers l’optimisation des algorithmes ou des stratégies d’enchères des DSPs afin de garantir les profits de ses annonceurs, sans prendre en considération l’AdX qui est responsable du bon déroulement d’enchère et le choix du meilleur prix dans un temps précis. Dans ce mémoire, nous intégrons dans AdX un système Pub/Sub basé sur le contenu (modèle de correspondance) et subscription-based (modèle de routage), afin de filtrer les requêtes d’enchères par rapport aux abonnements des DSPs, pour réduire ses coûts de calcul et de communication, ainsi que pour diminuer le délai d’attente. Notre travail est parfaitement cohérent avec les stratégies d’enchères proposées dans la littérature ainsi que la publicité Header Bidding. Ensuite, nous proposons d’ajouter une extension de filtrage Top-k dans AdX, qui n’a été jamais utilisé dans le contexte de publicité RTB selon notre connaissance, pour lui permettre de sélectionner un sous-ensemble de DSPs les plus compétitifs.

Modèle de prédiction des scores

Afin de prédire la performance d’un DSP, nous avons besoin d’estimer son prix d’offre et son temps de réponse en utilisant des données historiques des requêtes des enchères (par exemple : la base de données iPinYou) qui fournissent des informations sur l’espace publicitaire et l’utilisateur (variables indépendantes), ainsi que les réponses correspondantes des DSPs, incluant les prix des offres et les temps des réponses (variables dépendantes). Nous utilisons l’analyse de régression 35 pour prédire le prix d’offre et le temps de réponse comme étant deux variables continues dans R≥0. Tout d’abord, nous sélectionnons les attributs de la base de données iPinYou à utiliser pour la régression, en utilisant la méthode du filtre (KAUSHIK). Cette méthode consiste à étudier les corrélations entre chaque pair d’attributs à l’aide de la matrice de corrélation (tableau 3.1), puis supprimer un attribut dans chaque pair fortement corrélé (coefficient de corrélation |c| > 0,5 coloré en rouge), on choisit celui le moins corrélé avec le prix d’enchère et le temps de réponse. Nous obtenons donc les attributs suivants : Timestamp, AdExchange, AdSlotHeight, CityID, AdSlotVisibility, AdSlotFloorPrice et UserProfileIDs. Pour prédire le prix d’enchère et le temps de réponse, nous implémentons avec Python les algorithmes de régression vue dans la section 1.6.1.1 : régression linéaire, arbre de régression et K voisins les plus proches (pour régression) sur notre base de données générée dans la section 4.3 et l’historique des réponses des DSPs, et nous comparons leurs résultats en utilisant Python pour avoir les métriques de régression vu dans la section 1.6.1.2 afin de choisir le meilleur algorithme permettant de donner les résultats les plus précises. Nous obtenons les résultats de Python cités dans le tableau 3.2. Nous remarquons que la régression linéaire donne de meilleurs résultats 36 pour le prix d’offre avec 𝑀𝐴𝐸 −3.50 et 𝑅2 0.88, et KNN pour temps de réponse avec 𝑀𝐴𝐸 −6.54 et 𝑅2 −13.57. Par conséquent, nous mettons en oeuvre ces deux techniques dans notre évaluation

EXPÉRIENCE PERSONNELLE

Le but principal de notre recherche est l’intégration du modèle Publish/Subscribe avec Top-k dans Real-Time Bidding. Dans ce cadre, nous avons lu plusieurs articles liés à notre sujet et qui s’intéressent au système Publish/Subscribe et ses différents fonctionnalités expressives tels que l’agrégation, l’abonnement évolutif et le filtrage Top-k ainsi que Real-Time Bidding pour comprendre ses concepts et son fonctionnement. Ensuite, nous avons commencé à chercher une implémentation de RTB, mais malheureusement nous n’avons pas trouvé beaucoup de projets open source. La seule implémentation disponible est celle de OpenRTB, mais elle ne contient pas l’implémentation d’AdX qui est un composant principal dans RTB où nous allons intégrer Pub/Sub. Alors, nous avons implémenté un AdX selon la spécification décrite dans OpenRTB. En outre, le DSP implémenté dans OpenRTB est de type simple comme nous avons vu dans la section 4.1 donc nous avons cherché d’autres implémentations open source de DSP, mais nous n’avons pas trouvé, et par conséquent nous avons développé deux autres types basiques qui sont Random et Below_eCPC. Puis, nous avons dû choisir l’implémentation de Pub/Sub la plus convenable pour l’intégrer dans OpenRTB qui doit être au premier lieu basé sur le contenu pour exprimer les intérêts des DSPS. Après avoir étudié les implémentations existantes, nous avons choisi Header exchange de RabbitMQ, qui non seulement efficace dans notre cas, mais aussi caractérisé par une documentation claire 1 et une implémentation complète. Après avoir choisi l’implémentation de RTB et de Pub/Sub, nous avons eu besoin d’une base de données pour tester nos solutions. Selon notre connaissance, la seule base de données de RTB réelle et publique disponible est iPinYou dataset 2. Donc il y a un manque de base de données de test dans le domaine de RTB.

Pour commencer le développement, nous avons installé RabbitMQ ainsi que Erlang indispensable pour son fonctionnement, en suivant le guide d’installation disponible dans son site web officiel. Ensuite, nous avons développé nos solutions avec Java/J2EE en utilisant l’IDE Eclipse. Cet IDE est massivement utilisé en entreprise et un outil puissant, gratuit, libre et multiplateforme. Pour exécuter nos projets, nous avons eu besoin de mettre en place un serveur d’applications.Nous avons choisi au début d’utiliser Tomcat, car c’est un serveur léger, gratuit, libre, multiplateforme. En exécutant nos solutions avec iPinYou dataset, nous avons constaté que le serveur Tomcat ne peut pas exécuter toute la base de données voire qu’il a un temps maximal alloué. Nous avons essayé d’augmenter ce temps, mais ça n’a pas marché. Donc nous avons changé Tomcat par Glassfish qui est plus puissant puisque ce problème est disparu après. Nous avons également eu d’autres erreurs d’exécution et des exceptions, mais nous les avons résolus grâce aux forums surtout Stackoverflow. Nous avons testé avec iPinYou dataset jusqu’à que nous avions l’idée de créer un générateur de requêtes d’enchères ajustables issu de la base de données de départ, en créant de nouvelles données avec les mêmes distributions de leurs attributs. Donc, d’abord nous avons eu besoin de savoir les distributions des attributs de iPinYou dataset, qui sont presque toutes discrètes. Or en utilisant Python, nous avons constaté que ses frameworks sont capables d’ajuster seulement des données continues aux distributions théoriques. Alors, nous avons cherché d’autres outils qui extraient la distribution des données discrètes, mais nous n’avons trouvé que des logiciels non gratuits parmi eux JMP qui fournit une version d’essai, donc nous l’avons utilisé pour extraire toutes les distributions de iPinYou dataset. En conclusion, nous avons résumé les étapes et les problèmes rencontrés lors de la réalisation de notre projet de recherche. Cela a été une expérience intéressante pour nous et elle nous a beaucoup appris de nouvelles connaissances.

Dans la spécification 2.5 de RTB, AdX diffuse les requêtes des enchères à tous les DSPs, ce qui génère un surcoût de communication et de calcul massifs. Nous avons proposé d’utiliser le modèle Pub/Sub pour exprimer les intérêts des DSPs sous forme d’abonnements basés sur le contenu, afin d’éliminer les réponses vides. De plus, nous avons réduit davantage le nombre de DSPs contactés en diminuant les offres non compétitives ou ayant des temps de réponse lents. Nous avons formulé le problème du nombre optimal de réponses aux enchères et montrons comment le filtrage Top-k peut être utilisé pour résoudre ce problème dans le cadre réel. Nous avons également proposé trois types de filtrage Top-k : le premier est basé sur le calcul de score et repose sur l’analyse de régression avec des variables continues, afin d’estimer quels DSPs devraient participer à une telle enchère, tandis que les deux autres modèles basés sur le rang et la sélection binaire utilisent une analyse discrète. Notre évaluation a confirmé l’efficacité de nos approches pour réduire le nombre de messages (en éliminant toutes les réponses vides) et le temps des enchères, tout en maintenant des prix gagnants optimaux ou quasi optimaux (dans le cas de Top-k). En somme, la solution la plus efficace est OpenRTB avec Pub/Sub basé sur le contenu avec un filtrage Top-k basé sur la sélection binaire. Pour nos travaux futurs, nous souhaitons tester l’applicabilité de notre approche avec d’autres de bases de données au-delà d’iPinYou, et mettre en oeuvre des stratégies d’enchères plus sophistiquées qui pourraient contester la précision de nos modèles de Top-k. Nous chercherons également à rendre notre solution autoadaptative, en ajustant dynamiquement ses paramètres (par exemple, la valeur de k) selon les conditions actuelles.