2020


Retour à la vue des calendrier
Lundi 16 Mars
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: What (many kinds of) graphs can contribute to explainable machine learning
Description: Tiphaine Viard AI and machine learning are commonly described as "black boxes" that are efficient, but opaque. While complete opacity would be an exaggeration, it is true that many methods for explainability rely on forms of retro-engineering: we try to infer the model from its (partial, intermediary, final) results. These methods are typically based on large-scale, efficient matrix manipulation.

Graphs and their extensions have shown to be visualisable and interpretable, even at large scales. In their classical formulation, they are also very similar to matrices, but also versatile: they can be directed, weighted, multilayered, temporal, etc. Each of those extensions giving rise to interesting algorithmic and data-driven questions.
To date, few machine learning methods, harness the expressive power of graphs, in part due to the complexities of graph algorithms, typically having polynomial running times, which is incompatible with the scale of data at hand.

However, the situation has changed: (i) the impact of AI on society makes it no longer acceptable to only favour efficiency despite explainability, and (ii) recent advances in algorithmic methods on graphs demonstrates that due to the nature of real-world graphs, even some NP-hard problems become tractable.

The aim of this talk is to explore this avenue of research. We will discuss the state-of-the art as well as some past results in real-world (temporal) graph modeling and in explainability, and will then discuss some recent results on pattern mining on temporal graphs.
Jeudi 26 Mars
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Multi-period Hub Location Problem with Serial Demands: A Case Study of Humanitarian Aids Distribution in Lebanon
Description: Shahin Gelareh We address the problem of humanitarian aids distribution across refugee camps in war-ridden areas from a network design perspective. We show that the problem can be modeled as a variant of multi-period hub location problem with a particular demand pattern resulted by the user's behavior. The problem has been motivated by a case study of Lebanese experience in Syrian war refugee accommodation. We elaborate on the complexity and real-life constraints and, propose a compact formulation of a mathematical model of the problem. We then show that modeling the problem using a Benders paradigm drives O(n^3) variables of the original compact model unnecessary in addition to the constraints that are being projected out in a typical Benders decomposition. Additionally, we identify several classes of valid inequalities together with efficient separation procedures leading to a cut-and-Benders approach. Our extensive computational experiments on the case study with real data as well as randomly generated instances proves the performance of proposed solution methods.
Jeudi 16 Avril
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Décomposition et recherche Monte Carlo en General Game Playing
Description: Nicolas Jouandeau Les jeux permettent de définir des problèmes non triviaux dans un cadre fini et maîtrisé, et offrent de fait un cadre intéressant pour l’étude des algorithmes de décision. Pour réduire l'influence de connaissances expertes spécifiques à un jeu et stimuler une analyse logique des problèmes, le General Game Playing (GGP) propose de jouer à des jeux inconnus en partant uniquement de la description logique de leurs règles. Dans ce contexte, nous proposons deux méthodes générales de décomposition des jeux décrits en Game Description Language (GDL), l'une s’appuyant sur une analyse logique des règles et l'autre sur une analyse statistique d’informations collectées pendant des simulations. Enfin nous présentons une variation de la méthode Monte Carlo Tree Search exploitant ces décompositions dans un joueur GGP et permettant de résoudre simplement certains jeux.
Jeudi 23 Avril
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Méthodes primal-dual avec la programmation linéaire des configurations
Description: Nguyen Kim Thang Primal-duale est une méthode élégante et puissante en optimisation et en algorithmique. La méthode consiste à établir de manière interactive des solutions primals et duales, puis un algorithme, ainsi que son analyse, sont guidés naturellement par l'interaction primal-duale. Dans cet exposé, je vais présenter les approches primal-dual comme techniques unifiées afin d'étudier et de développer les algorithmes les domaines de la théorie des jeux algorithmiques et de l'algorithmique en ligne.