Ph.D Romain MATHONAT

 
Rule Discovery in Labeled Sequential Data: Application to Game Analytics

Download Draft here

Defended on September 29th 2020 at INSA Lyon

Committee

Dr. Sihem AMER-YAHIA, CNRS, Présidente
Prof. Martin ATZMULLER, Osnabrueck University
Prof. Jean-François BOULICAUT, INSA Lyon, Directeur de thèse
Prof. Germain FORESTIER, Université de Haute-Alsace
Prof. Anne LAURENT, Université de Montpellier
Dr. Mehdi KAYTOUE, INSA Lyon, Co-directeur de thèse
Dr. Chedy RAISSI, UBISOFT et INRIA Grand Est
Prof. Alexandre TERMIER, Université de Rennes

Résumé. Exploiter des jeux de données labelisés est très utile, non seulement pour entrainer des modèles et mettre en place des procédures d’analyse prédictives, mais aussi pour améliorer la compréhension d’un domaine. La découverte de sous-groupes a été l’objet de recherches depuis deux décennies. Elle consiste en la découverte de règles couvrants des ensembles d’objets ayant des propriétés intéressantes, qui caractérisent une classe cible donnée. Bien que de nombreux algorithmes de découverte de sous-groupes aient été proposés à la fois dans le cas des données transactionnelles et numériques, la découverte de règles dans des données séquentielles labelisées a été bien moins étudiée. Dans ce contexte, les stratégies d’exploration exhaustives ne sont pas applicables à des cas d’application réels, nous devons donc nous concentrer sur des approches heuristiques. Dans cette thèse, nous proposons d’appliquer des modèles de bandit manchot ainsi que la recherche arborescente de Monte Carlo à l’exploration de l’espace de recherche des règles possibles, en utilisant un compromis exploration-exploitation, sur différents types de données tels que les séquences d’ensemble d’éléments, ou les séries temporelles. Pour un budget temps donné, ces approches trouvent un ensemble des top-k règles découvertes, vis-à-vis de la mesure de qualité choisie. De plus, elles ne nécessitent qu’une configuration légère, et sont indépendantes de la mesure de qualité utilisée. A notre connaissance, il s’agit de la première application de la recherche arborescente de Monte Carlo au cas de la fouille de données séquentielles labelisées. Nous avons conduit des études approfondies sur différents jeux de données pour illustrer leurs plus-values, et discuté leur résultats quantitatif et qualitatif. Afin de valider le bon fonctionnement d’un de nos algorithmes, nous proposons un cas d’utilisation d’analyse de jeux vidéos, plus précisément de matchs de Rocket League. La découverte de règles intéressantes dans les séquences d’actions effectués par les joueurs et leur exploitation dans un modèle de classification supervisé montre l’efficacité et la pertinence de notre approche dans le contexte difficile et réaliste des données séquentielles de hautes dimensions. Elle permet la découverte automatique de techniques de jeu, et peut être utilisée afin de créer de nouveaux modes de jeu, d’améliorer le système de classement, d’assister les commentateurs de "e-sport", ou de mieux analyser l’équipe adverse en amont, par exemple.

Abstract. It is extremely useful to exploit labeled datasets not only to learn models and perform predictive analytics but also to improve our understanding of a domain and its available targeted classes. The subgroup discovery task has been considered for more than two decades. It concerns the discovery of rules covering sets of objects having interesting properties, e.g., they characterize a given target class. Though many subgroup discovery algorithms have been proposed for both transactional and numerical data, discovering rules within labeled sequential data has been much less studied. In that context, exhaustive exploration strategies can not be used for real-life applications and we have to look for heuristic approaches. In this thesis, we propose to apply bandit models and Monte Carlo Tree Search to explore the search space of possible rules using an exploration/exploitation trade-off, on different data types such as sequences of itemsets or time series. For a given budget, they find a collection of top-k best rules in the search space w.r.t chosen quality measure. They require a light configuration and are independent from the quality measure used for pattern scoring. To the best of our knowledge, this is the first time that the Monte Carlo Tree Search framework has been exploited in a sequential data mining setting. We have conducted thorough and comprehensive evaluations of our algorithms on several datasets to provide an empirical feedback, and we discuss their qualitative and quantitative results. To assess the added-value of one or our algorithms, we propose a use case of game analytics, more precisely Rocket League match analysis. Discovering interesting rules in sequences of actions performed by players and using them in a supervised classification model shows the efficiency and the relevance of our approach in the difficult and realistic context of high dimensional data. It supports the automatic discovery of skills and it can be used to create new game modes, to improve the ranking system, to help e-sport commentators, or to better analyze opponent teams, for example.

Publications liées à la thèse

Journal papers

Papers in proceedings of international events
Papers in proceedings of national events
Submitted