Tag : Français

Kristóf Huszár

Résumé :

Topology – the area of mathematics concerned with the study of shape – has always been interspersed with combinatorial ideas, therefore it is not surprising that many of its fundamental questions call for an algorithmic solution. This is particularly the case in 3-dimensions, where problems such as UNKNOT RECOGNITION (i.e., deciding whether a closed polygonal loop embedded in the Euclidean 3-space is knotted) and 3-SPHERE RECOGNITION (i.e., deciding whether a given triangulation describes the 3-dimensional sphere) have been driven research for over a century.

In this talk we first revisit the historical connection between topology and theoretical computer science. Then we discuss some fixed-parameter tractable algorithms that can efficiently solve hard problems about 3-manifolds, provided the input triangulation is sufficiently « thin. » Finally, we elaborate on the quantitative relationship between the combinatorial parameter that quantifies the « width » of a triangulation, and classical topological invariants of the underlying 3-manifold.

Joint work with Jonathan Spreer and Uli Wagner.

Median graphs and median related structures admit many characterizations and nice properties. The cube complexes of median graphs are exactly the CAT(0) cube complexes, which represent one of the most studied object in geometric group theory. Furthermore, median graphs also arise in concurrency theory and phylogenetics. We study the computation of metric parameters on this family of graphs: median set, diameter, eccentricities and reach centralities. In particular, in a very recent result, it is shown that all eccentricities can be computed in subquadratic-time on median graphs. We introduce the algorithmic techniques employed to tackle median graphs and present some open questions related to this topic.

Le prochain séminaire de l’équipe A3SI du LIGM aura lieu jeudi 17 mars à 13h30 en mode hybride. Jhony Giraldo nous présentera ses travaux intitulés Graph-based Algorithms in Computer Vision and Machine Learning: Theory and Applications (voir résumé ci-dessous). 

Le séminaire aura lieu :

– à ESIEE Paris dans l’amphithéâtre 160 ; et
– via https://meet.google.com/ioh-krdx-uqo , pour ceux qui ne pourront pas être présents.
La présentation sera en anglais.

Title: Graph-based Algorithms in Computer Vision and Machine Learning: Theory and Applications

Abstract: Graph representation learning and its applications have gained significant attention in recent years. Notably, Graph Neural Networks (CNN) and Graph Signal Processing (GSP) have been extensively studied. GNNs extend the concepts of Convolutional Neural Networks (CNNs) to non-Euclidean data modeled as graphs. Similarly, GSP extends the concepts of classical digital signal processing to signals supported on graphs. CNN and GSP have numerous applications such as semi-supervised learning, point cloud semantic segmentation, prediction of individual relations in social networks, modeling proteins for drug discovery, image, and video processing.

In this seminar, I will present our recent works on GSP and GNNs applied to some problems in computer vision and machine learning. The motivation of these studies is to leverage the structural information we can get from the data to effectively reduce the amount of labeled information required to solve the specific problem. I will focus on the applications of moving object segmentation, image classification, and weakly-supervised semantic segmentation. To that end, we map the particular problem to a graph, and subsequently, we apply GSP/GNN ideas to solve the learning problem. Our algorithms show competitive performance against state-of-the-art methods under the paradigm of learning with minimal supervision.  

Bio: Jhony H. Giraldo received a Bachelor in Electronics Engineering in 2016 from the Universidad de Antioquia, Colombia, and a Master of Science degree with honors at the same university in 2018. He spent 15 months at the University of Delaware, USA, between 2018 and 2019, working on Graph Signal Processing as a Research Assistant. He was visiting scholar at the Università degli Studi di Napoli Parthenope, Italy, working at the CVPR Lab “Alfredo Petrosino” in 2021. Currently, he is a final-year Ph.D. student in computer science at La Rochelle Université, Laboratoire MIA (Mathématiques, Image, et Applications), France. He is also a visiting PhD student at Centre de Vision Numérique (CVN), Inria OPIS at CentraleSupélec, Université Paris-Saclay, working on Deep Graph Neural Networks. His research interests include the fundamentals and applications of Graph Neural Networks, Computer Vision, Machine Learning, and Graph Signal Processing.

Octal games are combinatorial games played on heaps of counters: two players alternate removing counters from a heap, and may split it into two nonempty heaps, under conditions expressed in the form of an octal code. The main problem is deciding which player wins (by playing the last legal move) from a heap of a given size. In order to answer to this question, the most used method consists in finding regularities in the sequence of its Grundy values (equivalence classes for games) on heaps of increasing sizes.

We propose a generalization of those games on graphs: the players remove connected subgraphs, and may disconnect the graph, under conditions similar to those of octal games. This definition includes several vertex deletion games, such as Arc-Kayles. We focus our study on subtraction games, a subfamily of octal games where the players cannot disconnect the graph.

This talk will start with an introduction to the Sprague-Grundy Theory used to study impartial combinatorial games, with a focus on octal games. I will then show how we generalized this family to play it on graphs, and how to study regularity in this context. Finally, I will focus on subtraction games on graphs, and present several of our results, from general ones (PSPACE-completeness, ultimate periodicity) to specific families of games on families of graphs. Our study is mostly focused on subdivided stars, which are already difficult to tackle: the classical game Arc-Kayles is open in the family of subdivided stars, even with only three paths with one of length 1! We determined polynomial-time algorithms which allow to decide the winner of the game 0.33 on subdivided stars and bistars.

le prochain atelier doctorant aura lieu jeudi 10/3 de 13h à 15h à ESIEE Paris dans l’amphi 260. Il sera également possible d’assister aux présentations en ligne à l’adresse https://meet.google.com/rfh-iovd-hpt

Le programme de l’atelier est le suivant :

• 13h00 – 13h30 : Thomas Belos, « MOD SLAM: Mixed Method for a More Robust SLAM Without Loop Closing »  
• 13h30 – 14h00 : Thibaut Issenhuth, « Learning disconnected manifolds with generative adversarial networks« 
• 14h00 – 14h30 : Yamna Ouchtar, « Watershed-Based Oversampling for Imbalanced Dataset Classification« 
• 14h30 – 15h00 : Mathis Petrovich, « Human motion generation« 

Résumés des présentations

Orateur : Thomas Belos

Titre de la présentation : MOD SLAM: Mixed Method for a More Robust SLAM Without Loop Closing

Résumé : In recent years, the state-of-the-art of monocular SLAM has seen remarkable advances in reducing errors and improving robustness. At the same time, this quality of results can be obtained in real-time on small CPUs. However, most algorithms have a high failure rate out-of-the-box. Systematic error such as drift remains still significant even for the best algorithms. This can be handled by a global measure as a loop closure, but it penalizes online data processing. We propose a mixed SLAM, based on ORB-SLAM2 and DSO: MOD SLAM. It is a fusion of photometric and feature-based methods, without being a simple copy of both. We propose a decision system to predict at each frame which optimization will produce the minimum drift so that only one will be selected to save computational time and resources. We propose a new implementation of the map that is equipped with the ability to actively work with DSO and ORB points at the same time. Our experimental results show that this method increases the overall robustness and reduces the drift without compromising the computational resources. Contrary to the best state-of-the-art algorithms, MOD SLAM can handle 100% of KITTI, TUM, and random phone videos, without any configuration change.

Orateur : Thibaut Issenhuth

Titre de la présentation :  Learning disconnected manifolds with generative adversarial networks

Résumé : Generative Adversarial Networks (GANs) recently achieved impressive results in unconditional image synthesis (e.g. face synthesis), but are still struggling on large-scale multi-class datasets. In this presentation, we will formalize a fundamental limitation of GANs when the target distribution is lying on disconnected manifolds. We establish a « no free lunch » theorem for the disconnected manifold learning, stating an upper bound on the precision of the generated distribution. Then, we will present two methods to improve the precision of a pre-trained generator: a heuristic method rejecting generated samples with high Jacobian Frobenius norms, and a learning-based method trained to minimize the Wasserstein distance between generated and target distributions.

Oratrice : Yamna Ouchtar

Titre de la présentation : Watershed-Based Oversampling for Imbalanced Dataset Classification

Résumé : For several real-world problems, such as credit card frauds, rare diseases, or road accidents, the provided dataset is composed of two or more imbalanced classes: a minority and a majority. With usual machine learning methods, this imbalance often leads to poor results where the minority class is misclassified. To alleviate these issues, several pre-processing methods, such as SMOTE, DBSMOTE or G-SMOTE are developed to build new artificial points.  Nevertheless, these oversampling methods explicitly or implicitly make hypotheses about the cluster’s size, shape, or density that may not fit the dataset in practice. We propose to improve these oversampling methods and reduce cluster assumptions, by relying on another classifier: the watershed-cut. We called this method WSSMOTE. Experimental results demonstrate that, although there is no silver bullet, WSSMOTE often outperforms G-SMOTE, DBSMOTE and SMOTE on several datasets composed of different minority class percentages.

Orateur :  Mathis Petrovich

Titre de la présentation : Human motion generation

Résumé : We tackle the problem of action-conditioned generation of realistic and diverse human motion sequences. In contrast to methods that complete, or extend, motion sequences, this task does not require an initial pose or sequence. Here we learn an action-aware latent representation for human motions by training a generative variational autoencoder (VAE). By sampling from this latent space and querying a certain duration through a series of positional encodings, we synthesize variable-length motion sequences conditioned on a categorical action. Specifically, we design a Transformer-based architecture, ACTOR, for encoding and decoding a sequence of parametricSMPL human body models estimated from action recognition datasets. We evaluate our approach on the NTU RGB+D, HumanAct12 and UESTC datasets and show improvements over the state of the art. Furthermore, we present two use cases: improving action recognition through adding our synthesized data to training, and motion denoising. Finally, I will present TEMOS, a recent extension of this work: generating diverse 3D human motions from textual descriptions.

A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced graph invariant called the twin-width is based on contraction sequences [BKTW, J. ACM ’22]. More precisely, if one puts error edges, henceforth red edges, between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer d such that a contraction sequence, called d-sequence, exists that keeps red degree at most d. Many well-known graph classes are shown to have bounded twin-width including unit interval graphs, a strict hereditary class of permutation graphs, posets of bounded width, proper minor-closed class, subgraphs of O(1)-dimensional grids as well as graphs of bounded tree-width and clique-width. Since its introduction two years ago, twin-width gained extensive traction across areas such as graph theory, algorithms design, logic, data structure, constraint programming and communication complexity.

In this talk, we review some algorithmic implications of twin-width on graphs of bounded twin-width and beyond such graphs.

It was proved in [BKTW, JACM ’22] that FO (first-order) model-checking is fixed-parameter tractable provided that a d-sequence is given. This unifies and extends known tractability results. Due to its generality, the running time of FO model-checking algorithm suffers a huge dependency on the (nested) quantifier depth of the input sentence. It turns out that for concrete well-known problems such as k-Dominating Set, k-Independent Set and Subgraph Isomorphism in general, slick dynamic programming can be designed so that the runtime dependency is single exponential in k provided O(1)-sequence is given [BGKTW, ICALP ’21]. The spirit of such DP algorithms is further extended in [BKRT, SODA ’22] to attain an alternative proof for the tractability MSO model-checking on graph of bounded clique-width [Courcelle, Makowsky, Rotics, TCS ’00].

The terrain of monotone (closed under taking subgraphs) graph classes is fully charted in regards to fixed-parameter tractability of FO model-checking: a monotone graph class is nowhere dense if and only if FO model-checking is fpt on it. For the more general hereditary (closed under taking induced subgraphs) graph classes, it is conjectured that a class admits an fpt algorithm for FO model-checking if and only the class “does not encode all finite graphs in a manner interpretable by FO logic” (monadically dependent). We survey a few graph classes where the conjecture is positively affirmed and the dividing line is drawn precisely by the twin-width. Such classes include ordered graphs [BGdMST, STOC ’22], permutation graphs [BKTW, JACM ’22] and circle graphs [Hlinený, Filip Pokrývka, ’22], interval graphs and rooted directed path graphs [BCKKLT, ’22].

Twin-width can be useful for designing algorithms even on graph classes of unbounded twin-width. Some structures like large bicliques, half-graphs, or independent sets are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Combined with the FPT algorithm for FO model checking on graphs given with O(1)-sequences, this give rise to a variety of algorithmic win-win arguments [BCKKLT, ’22]. For instance, we readily derive fpt algorithms for k-Independent Set on visibility graphs of simple polygons, which was addressed as an open problem.

Résumé :

Soit p un nombre premier. Dans sa forme la plus simple, le théorème de Mahler sur les séries d’interpolation stipule qu’une fonction de N dans Z est uniformément continue pour la métrique p-adique si et seulement si elle peut être approchée uniformément par des fonctions polynomiales. Nous prouvons une généralisation non-commutative de ce résultat pour les fonctions d’un monoïde libre A* dans un groupe libre F(B). L’un des défis à relever est de trouver un analogue adéquat des fonctions polynomiales dans ce cadre non commutatif.

La motivation de départ était une question de théorie des langages: peut-on décrire simplement les fonctions f de A* dans F(B) qui possèdent la propriété suivante: si L est une partie de F(B) reconnue par un p-groupe(*) fini, alors f^{-1}(L) a la même propriété. Nous verrons comment la version non commutative du résultat de Mahler permet une description élégante de ces fonctions. Travail joint avec Christophe Reutenauer.

(*) un p-groupe fini est un groupe dont l’ordre est une puissance de p

Abstract : The talk will begin with an introduction to embedded real-time computing and scheduling problems. We will use simple examples to motivate the research problems and to illustrate the key concepts of the discipline.

Then we study a problem related to the schedulability of systems with preemptive tasks for single-core architectures.We will consider the notion of simulation interval for real-time priority driven schedulers upon uniprocessor. Our study focuses on a model where preemption costs are explicitly considered, i.e., the time required by the real-time operating system (RTOS) to load the context of execution of preempted real-time jobs.We first present the model and the research question — identify simulation intervals for popular real-time schedulers (Rate Monotonic, Earliest Deadline First, Least Laxity First) with preemption delay upon uniprocessor. We then present briefly related results of the literature. Then, we present two contributions: (i) a simulation interval for priority driven schedulers, and then an interesting particular case where former results of the literature, model without  preemption delay, apply. I.e., shorter simulation intervals exist.We will end the presentation by listing other types of problems we are interested in.

Abstract : Le problème du mot pour les monoïdes à un relateur a été décrit comme l’un des problèmes non résolus les plus fondamentales de toute l’algèbre combinatoire. Il a été non résolu pendant un siècle, et P. S. Novikov l’a décrit comme « contenant de quelque chose de transcendental ». Dans mon exposé, je vais donner un aperçu de cet problème, son histoire, et quelques réductions importantes démontrées par S. I. Adian et ses doctorants. Après ça, je vais focuser sur quelques classes spéciales, et montrer certains de mes résultats récents, qui font partie d’un programme de recherche pour comprendre la théorie des langages formels d’un monoïde à un relateur. En particulier, je vais montrer que le théorème de Muller-Schupp peut être généralisé à une grande classe de monoïdes. Comme conséquence, je vais démonstrer qu’on peut décider si un monoïde à un relateur et contenant un idempotent non trivial a un problème du mot qui est une langage algébrique (« context-free »).

Résumé : La ministre Amélie de Montchalin vient d’annoncer un plan d’action logiciels libres et communs numériques pour l’administration : nous présenterons ce plan, les actions mises en place, et la façon dont vous pouvez y contribuer.

Il y aura environ 25 minutes de présentation, suivie par 35 minutes d’échanges libres.