Le CRIL en bref
Le Centre de Recherche en Informatique de Lens (CRIL UMR 8188) est un laboratoire de l’Université d’Artois et du CNRS qui regroupe plus de cinquante membres : chercheurs, enseignants-chercheurs, doctorants et personnels administratifs et techniques.
Recherches en intelligence artificielle et applications
Actualités (RSS)
Séminaire Collective Singleton-based Consistency for Qualitative Constraint Networks: Theory and Practice
Michael Sioutis (Örebro University)
Partial singleton weak path-consistency is essential for tackling challenging fundamental reasoning problems
associated with qualitative constraints networks. Briefly put, partial singleton weak path-consistency
ensures that each base relation of each of the constraints of a qualitative constraint network can define a
singleton relation in its corresponding partially weakly path-consistent subnetwork. In this talk, we propose
a stronger local consistency that couples partial singleton weak path-consistency with the idea of collectively
deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for
enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency, both of which outperform the respective algorithm for enforcing partial singleton weak path-consistency in a given qualitative constraint network . With respect to the lazy algorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability.
We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network.
Soutenance de thèse de Valentin Montmirail - Practical resolution of satisfiability testing for modal logics
Le 17 septembre 2018, à 10h, salle des thèses de la faculté Jean Perrin
Résumé
In this thesis, we explored the idea to use modern SAT technology that has seen considerable progress over the last years for solving various kinds of Modal Logics.
We tackled the problem from various directions. For the NP-complete variants of Modal Logics it is a natural choice to encode them to SAT and use a SAT solver to decide them. In order to get an efficient Modal Logic solver, it requires several optimisations because otherwise the formulas will get too huge.
In the next step, we asked the question how to obtain smallest models when the considered formula is satisfiable and we came up with several solutions but we did not stop our work with the NP-complete logics.
For going beyond NP, we suggested a novel approach inspired by the successful CEGAR techniques that we named RECAR for Recursive Explore and Check Abstraction Refinement. We instantiated the framework RECAR within the solver MoSaiC and we demonstrated how, with efficient over- and under- abstractions, a SAT-based approach can solve PSPACE modal logics.
Soutenance de thèse de Abdelhamid Boudane - Fouille de données par contraintes
Le 13 septembre 2018, à 14h, salle des thèses de la faculté Jean Perrin
Résumé
Dans cette thèse, nous abordons les problèmes bien connus de clustering et de fouille de règles
d’association. Notre première contribution introduit un nouveau cadre de clustering, où les objets complexes
sont décrits par des formules propositionnelles. Premièrement, nous adaptons les deux fameux
algorithmes de clustering, à savoir, le k-means et l’algorithme hiérarchique ascendant, pour traiter ce type
d’objets complexes. Deuxièmement, nous introduisons un nouvel algorithme hiérarchique descendant
pour le clustering des objets représentés explicitement par des ensembles de modèles. Enfin, nous
proposons un encodage basé sur la satisfiabilité propositionnelle du problème de clustering des formules
propositionnelles sans avoir besoin d’une représentation explicite de leurs modèles. Dans une seconde
contribution, nous proposons une nouvelle approche basée sur la satisfiabilité pour extraire les règles
d’association en une seule étape. La tâche est modélisée comme une formule propositionnelle dont les
modèles correspondent aux règles à extraire. Pour montrer la flexibilité de notre cadre, nous abordons
également d’autres variantes, à savoir, l’extraction des règles d’association fermées, minimales non
redondantes, les plus générales et les indirectes. Les expérimentations sur de nombreux jeux de données
montrent que sur la majorité des tâches de fouille de règles d’association considérées, notre approche
déclarative réalise de meilleures performances que les méthodes spécialisées.
Mots-clés : fouille de données, clustering, règles d’association, satisfiabilité propositionnelle.
Papiers acceptés à KR'18
Cette année, ce seront 4 papiers et 3 posters co-écrits par des membres du CRIL qui seront présentés à KR 2018.
Quatre papiers seront présentés dans la conférence générale :
Leila Amgoud, Elise Bonzon, Jérôme Delobelle, Dragan Doder, Sébastien Konieczny and Nicolas Maudet Gradual semantics accounting for similarity between arguments
Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny and Nicolas Maudet Combining Extension-based semantics and Ranking-based semantics for Abstract Argumentation
Nicolas Schwind, Sébastien Konieczny and Pierre Marquis On Belief Promotion
Giovanni Casini, Thomas Meyer, Eduardo Fermé and Ivan Varzinczak A Semantic Perspective on Belief Change in a Preferential Non-Monotonic Framework
Les trois posters suivants seront également présentés :
Sébastien Konieczny, Pierre Marquis and Srdjan Vesic New inference relations from maximal consistent subsets
Jean Marie Lagniez, Daniel Le Berre, Tiago de Lima and Valentin Montmirail Space-Awareness in a SAT-Based Approach For PSPACE Modal Logics
Nicolas Schwind, Tenda Okimoto, Katsumi Inoue, Katsutoshi Hirayama, Jean-Marie Lagniez and Pierre Marquis Probabilistic Coalition Structure Generation
Ivan Varzinczak reçoit le prix de logique Louis Couturat
Ivan Varzinczak recevra le prix de la logique Louis Couturat lors de la prochaine
édition de la conférence UNILOG’18 le 24 juin, pour son article
“A note on a description logic of concept and role typicality”.