Ph.D Guillaume BOSC
Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search
Download Draft here
Defended on September 11th 2017 at INSA Lyon
Committee
Dr. Sihem AMER-YAHIA, CNRS, Présidente
Résumé. La découverte de motifs qui caractérisent fortement une classe vis à vis d’une autre reste encore un problème difficile en fouille de données. La découverte de sous-groupes (Subgroup Discovery, SD) est une approche formelle de fouille de motifs qui permet la construction de classifieurs intelligibles mais surtout d’émettre des hypothèses sur les données. Cependant, cette approche fait encore face à deux problèmes majeurs : (i) comment définir des mesures de qualité appropriées pour caractériser l’intérêt d’un motif et (ii) comment sélectionner une méthode heuristique adaptée lorsqu’une énumération exhaustive de l’espace de recherche n’est pas réalisable. Le premier problème a été résolu par la fouille de modèles exceptionnels (Exceptional Model Mining, EMM) qui permet l’extraction de motifs couvrant des objets de la base de données pour lesquels le modèle induit sur les attributs de classe est significativement différent du modèle induit par l’ensemble des objets du jeu de données. Le second problème a été étudié en SD et EMM principalement avec la mise en place de méthodes heuristiques de type recherche en faisceau (beam-search) ou avec des algorithmes génétiques qui permettent la découverte de motifs non redondants, diversifiés et de bonne qualité. Dans cette thèse, nous soutenons que la nature gloutonne des méthodes d’énumération précédentes génère cependant des ensembles de motifs manquant de diversité. Nous définissons formellement la fouille de données comme un jeu que nous résolvons par l’utilisation de la recherche arborescente de Monte Carlo (Monte Carlo Tree Search, MCTS), une technique récente principalement utilisée pour la résolution de jeux et de problèmes de planning en intelligence artificielle. Contrairement aux méthodes traditionnelles d’échantillonnage, MCTS donne la possibilité d’obtenir une solution à tout instant sans qu’aucune hypothèse ne soit faite que ce soit sur la mesure de qualité ou sur les données. Cette méthode d’énumération converge vers une approche exhaustive si les budgets temps et mémoire disponibles sont suffisants. Le compromis entre l’exploration et l’exploitation que propose cette approche permet une augmentation significative de la diversité dans l’ensemble des motifs calculés. Nous montrons que la recherche arborescente de Monte Carlo appliquée à la fouille de motifs permet de trouver rapidement un ensemble de motifs diversifiés et de bonne qualité à l’aide d’expérimentations sur des jeux de données de référence et sur un jeu de données réel traitant de l’olfaction. Nous proposons et validons également une nouvelle mesure de qualité spécialement conçue pour des jeux de donnée multi labels présentant une grande variance de fréquences des labels.
Abstract.
The discovery of patterns that strongly distinguish one class label
from another is still a challenging data-mining task. Subgroup
Discovery (SD) is a formal pattern mining framework that enables the
construction of intelligible classifiers, and, most importantly, to
elicit interesting hypotheses from the data. However, SD still faces
two major issues: (i) how to define appropriate quality measures to
characterize the interestingness of a pattern; (ii) how to select an
accurate heuristic search technique when exhaustive enumeration of the
pattern space is unfeasible. The first issue has been tackled by
Exceptional Model Mining (EMM) for discovering patterns that cover
tuples that locally induce a model substantially different from the
model of the whole dataset. The second issue has been studied in SD and
EMM mainly with the use of beamsearch strategies and genetic algorithms
for discovering a pattern set that is non-redundant, diverse and of
high quality. In this thesis, we argue that the greedy nature of most
such previous approaches produces pattern sets that lack diversity.
Consequently, we formally define pattern mining as a game and solve it
with Monte Carlo Tree Search (MCTS), a recent technique mainly used for
games and planning problems in artificial intelligence. Contrary to
traditional sampling methods, MCTS leads to an any-time pattern mining
approach without assumptions on either the quality measure or the data.
It converges to an exhaustive search if given enough time and memory.
The exploration/exploitation trade-off allows the diversity of the
result set to be improved considerably compared to existing heuristics.
We show that MCTS quickly finds a diverse pattern set of high quality
in our application in neurosciences. We also propose and validate a new
quality measure especially tuned for imbalanced multi-label data.
Publications liées à la thèse
Journal papers
Guillaume Bosc, Jean-François Boulicaut, Chedy Raïssi, Mehdi Kaytoue. Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search. Data Mining and Knowledge Discovery journal 32(3):604-650, 2018, Springer. On line since December 12th 2017.
Guillaume Bosc, Philip Tan, Jean-François Boulicaut, Chedy Raïssi, Mehdi Kaytoue. A Pattern Mining Approach to Study Strategy Balance in RTS Games. IEEE Transactions on Computational Intelligence and Artificial Intelligence in Games 9(2):123-132, 2017, IEEE computer Press.
Guillaume Bosc, Mehdi Kaytoue, Chedy Raïssi, Jean-Francois Boulicaut, Philip Tan. Mining
balanced sequential patterns from zero-sum game interactions. Proc.
European Conference on Artificial Intelligence ECAI 2014.
August 2014, Praha, Czech Republic, T. Schaub et al. (Eds), short paper, pp. 975-976, IOS.