Séminaires des doctorants -Archives
Planning - Présentation - ArchivesSur les solutions de Kalai-Smorodinsky pour le problème d'arbre couvrant bi-objectif
Thanh Loan NGUYEN, Doctorante
Ce travail étudie le problème d'arbre couvrant bi-objectif (BSTP), une extension du problème classique de l'arbre couvrant minimal avec diverses applications. Dans ce problème, chaque arête d'un graphe donné est associée à deux poids distincts, et l'objectif est de trouver un arbre couvrant qui minimise simultanément les deux poids totaux. En tant que cas particulier d'optimisation bi-objective, nous pouvons être intéressés par l'énumération de toutes les solutions Pareto-optimales du BSTP. Cependant, comme le nombre de solutions Pareto-optimales peut être exponentiel, toutes les approches existantes pour énumérer les solutions efficaces ne peuvent pas atteindre un temps de calcul polynomial. Dans cet exposé, nous proposons une nouvelle approche pour trouver des solutions efficaces préférées où le pire des rapports des deux valeurs objectives à leurs valeurs maximales possibles respectives est minimum. Cette approche est basée sur la solution de Kalai-Smorodinsky (KS), un concept bien connu en théorie des jeux coopératifs. Plus précisément, nous considérons une extension du concept de solution KS au cas discret qui peut être trouvée en optimisant des combinaisons convexes de deux objectifs. Nous caractérisons d'abord les propriétés de cette (ces) solution(s) KS pour le BSTP. Ensuite, nous présentons un algorithme de temps polynomial faible pour trouver la (les) solution(s) KS pour le BSTP. Enfin, nous présentons les résultats computationnels sur quelques instances et discutons des résultats. Au-delà du cas particulier du BSTP, cet article offre une approche efficace et explicable pour résoudre les problèmes d'optimisation combinatoire bi-objectifs.
Towards Faithful Knowledge-Based Explainability For Deep Neural Networks
Rim EL CHEIKH, Doctorante
Avec l'adoption croissante des modèles d'apprentissage profond dans les applications réelles, la demande de transparence dans leurs résultats augmente. Le domaine de l'IA explicable (XAI) a connu des avancées notables, comme les méthodes basées sur les caractéristiques telles que SHAP et LIME. Cependant, une nouvelle vague d'approches XAI émerge, intégrant des connaissances explicitespour une meilleure interprétabilité. Ces méthodes visent à fournir des informations sur des résultats spécifiques ou le fonctionnement général du modèle expliqué en incorporant des connaissances du domaine avant ou après l'entraînement du modèle. Cette présentation passera en revue ces approches en fonction du niveau auquel les connaissances sont intégrées dans le pipeline DL/XAI. De plus, nous explorerons les méthodes d'évaluation, avec un accent particulier sur l'aspect de la fidélité de l'XAI basée sur les connaissances.
Représentation des connaissances pour les écosystèmes de jumeaux numériques
Samuele BURATTINI, Doctorant Invité
Les jumeaux numériques sont un sujet en constante progression en informatique ainsi que dans plusieurs autres domaines d'application. L'idée de pouvoir créer des répliques virtuelles des objets que nous souhaitons suivre dans le monde réel est fascinante et attrayante pour plusieurs raisons, notamment la surveillance et la prévision grâce aux prédictions et aux simulations. Nous pouvons bientôt imaginer un monde où plusieurs jumeaux numériques d'objets différents seront disponibles, mais que se passera-t-il ensuite ? Comment pouvons-nous les rendre interopérables et utiles pour d'autres applications ? Lors de mon séjour à l'École des Mines, j'ai essayé de comprendre comment la représentation des connaissances peut permettre cela, et quel est l'écart actuel pour décrire efficacement les jumeaux numériques à cette fin.
Évaluation de la qualité des données pour les tâches de classification
Roxane JOUSEAU, Doctorante
La qualité des données est un élément crucial pour la construction et l'optimisation de bons modèles d'apprentissage. Malgré de nombreuses tentatives pour caractériser la qualité des données, une formalisation rigoureuse et une mesure efficace de la qualité à partir des observations disponibles font toujours défaut, ce qui se reflète dans les outils de qualité des données disponibles. En effet, sans une compréhension claire des processus de formation et de test, il est difficile d'évaluer la performance intrinsèque d'un modèle. Cette présentation introduit et explique une nouvelle métrique pour mesurer la qualité des données. Cette métrique est basée sur l'évolution corrélée entre la performance de la classification et la détérioration des données. La méthode proposée présente l'avantage significatif d'être indépendante du modèle et de ne pas nécessiter de métadonnées ou de connaissances d'experts. En outre, nous fournissons une interprétation de notre métrique. Nous confirmons l'utilité de la métrique proposée par des expériences numériques intensives et détaillons quelques cas illustratifs avec des qualités contrôlées et interprétables.
Introduction aux modèles de plongement des graphes de connaissances
IFERROUDJENE Mouloud, Doctorant
Les KGE sont devenus un outil puissant pour l'apprentissage de représentations de graphes. Ils permettent d'encoder les entités et les relations dans des graphes étiquetés et dirigées . Nous examinerons les principes de conception sous-jacents des modèles KGE, explorant pourquoi ils gagnent en popularité pour la représentation de graphes. Nous discuterons des fondements théoriques des KGE : comment ils représentent les entités et les relations sous forme de vecteurs dans un espace vectoriel. Nous mettrons l'accent sur leurs applications pratiques actuelles, comme la complétion de graphes, la classification de liens, etc. Nous aborderons également les limites actuelles des KGE : difficultés à représenter certains types de relations, passage à l'échelle, intégration de connaissances externes. Enfin, nous présenterons les orientations futures de la recherche pour surmonter ces limites, comme de nouvelles fonctions de scores, l'injection de connaissances, l'apprentissage non supervisé.
L’information géographique volontaire au service de l’accessibilité
Jeremy KALSRON
OpenStreetMap est une carte collaborative du monde. Surnommée « Wikipédia des cartes », elle est aujourd’hui largement utilisée par la recherche, les administrations et l’industrie. Mais comment OpenStreetMap fonctionne ? Comment peut-on y contribuer ? Et que peut-on faire de cette donnée ? Cette présentation tentera de répondre en partie à ces questions et présentera un cas d’usage : décrire un carrefour à une personne en situation de handicap visuel.
Heterogeneous wireless networks coexistence techniques
Ali MAMADOU MAMADOU
Application physique de preuves à divulgation nulle de connaissance et preuve de np-completeness
Léo Robert
Suguru est un jeu qui ressemble au sudoku; vous devez remplir une grille avec des chiffres selon certaines règles. Le problème qui se pose est le suivant : comment pouvez-vous me convaincre que vous avez la solution sans révéler la moindre information sur cette solution ?
La présentation sera en deux parties. Dans un premier temps, nous verrons un protocole qui utilise des objets du quotidien (cartes, enveloppes) pour vise à prouver qu'un personne détient (ou non) la solution sans révéler la moindre information.
Dans un second temps, nous verrons comment prouver mathématiquement que la résolution d'un tel jeu est "difficile".
Bayesian Inference Approach For an Efficient Data Sharing among IoT devices
Cristanel RAZAFIMANDIMBY (Inria Lille)
Nowadays, Internet of Things (IoT) coupled with cloud computing begins to take an important place in economic systems and in society daily life. It has got a large success in several application areas, ranging from smart city applications to smart grids. One major challenge that should be addressed is the huge amount of data generated by the sensing devices, which make the control of sending useless data very important. To face this challenge, we present a Bayesian Inference Approach (BIA), which allows avoiding the transmission of high spatio-temporal correlated data. The proposed BIA is based on a hierarchical architecture with simple nodes, smart gateways and data centers. Belief Propagation algorithm has been chosen for performing an approximate inference on our model in order to reconstruct the missing sensing data. BIA is evaluated based on the data collected from real sensors and according to different scenarios. The results show that our proposed approach reduces drastically the number of transmitted data and the energy consumption, while maintaining an acceptable level of data prediction accuracy.|
Cycle de poids minimum : Polytopes et algorithmes dans les graphes série-parallèles
Henri Perret du Cray (Limos)
Un cycle simple est un graphe connexe où tous les sommets ont degré 2. Résoudre le problème du cycle de poids minimum consiste à trouver un cycle simple minimisant une fonction poids sur les arêtes d’un graphe G=(V,E). Je présenterai une formulation linéaire compacte du problème, et montrerai que cette formulation décrit le polytope des cycles lorsque le graphe considéré et série-parallèle. Je présenterai également un algorithme linéaire pour résoudre le problème du cycle de poids minimum dans les graphes séries parallèles, ainsi qu’une variante du problème où le cycle recherché doit avoir une taille fixée.|
An introduction on RPL : IPv6 Routing Protocol for Low-Power and Lossy Networks
Jinpeng Wang
In the recent years, Low Power and Lossy Networks (LLNs) have become one of the most interesting research areas. They typically operate with strict resource constraints in communication, computation, memory, and energy. IP smart object networks are undoubtedly one of the key components of the next wave of the Internet, with an endless number of new opportunities and applications according to newly designed IP based protocols. Routing Protocol for Low-Power and Lossy Networks (RPL) is an ad-hoc on-Demand Distance Vector routing protocol for LLNs that optimizes IPv6 in order to run on over of IEEE 802.15.4 standard, which has an acronym 6LoWPAN. It specifies how to construct Destination Oriented Directed Acyclic Graphs (DODAG) by using an objective function through a set of metrics. In this study, we mainly make an introduction on the mechanism and the most influential parameters of RPL.
Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem
Maël Minot
Le problème de somme coloration est un problème NP-difficile dérivé du problème bien connu de coloration de graphe. Il consiste à trouver une coloration qui minimise la somme d’entiers correspondant aux couleurs affectées plutôt que le nombre de couleurs utilisées. Ce problème survient notamment dans les domaines de la planification et de l’allocation de ressources. Nous avons mené une évaluation des capacités qu’ont la programmation linéaire (ILP) et la programmation par contraintes (CP) pour résoudre ce problème, et proposé plusieurs améliorations. Nous explorons également les possibilités offertes par une combinaison d’ILP et de CP dans une décomposition arborescente de hauteur bornée, et évaluons des méthodes visant à obtenir rapidement une solution de qualité par combinaison de solutions partielles à partir d’une telle décomposition. Enfin, certaines de ces méthodes peuvent être combinées au sein d’un portfolio visant à tirer partie de leur importante complémentarité.
Fast loop-free transition of routing protocols
Nina Pelagie Bekono :
A routing protocol determines the routes followed by packets to their destination. In networks that operate during a long time, the routing protocol might have to be changed. This change might be required to apply a security update of the protocol, to take into account significant modifications of the topology and link metrics, or to handle urgent traffic in wireless sensor network monitoring applications. The transition from one routing protocol to another involves reconfiguring all routers in a given order. It is a complex and critical task : if the transition is not performed carefully, transient routing loops can occur, and the performance of the network can drastically decrease (decreased bandwidth, increased congestion, loss of packets...). We present a loop-free transition algorithm called ACH (avoiding cycles heuristic), which is able to perform the transition in avery small number of steps.
Process and data based approaches for knowledge discovery : Application to Healthcare
Benjamin DALMAS :
The forecast about the increase of the elderly population in French rural regions implies elderly-related healthcare processes to be more efficient. Data and process mining techniques have proven to discover useful knowledge when applied in the healthcare domain. However, it remains challenging because of the complex nature of its processes. In our work, in collaboration with the University Hospital Center of Clermont-Ferrand, we focus on the impact of choices and ordering of activities in the execution of healthcare processes.
Practical Passive Leakage-Abuse Attacks Against Symmetric Searchable Encryption
Matthieu GIRAUD :
The problem of securely outsourcing client data with search functionality has given rise to efficient solutions called Symmetric Searchable Encryption (SSE) schemes. These schemes are provably secure with respect to an explicit leakage profile , however, determining how much information can be inferred in practice from this leakage remains difficult. First, we refine and formalize the leakage hierarchy introduced by Cash et al. in 2015. Second, we further the analysis of existing attacks to better understand their real-world efficiency and the practicality of their hypothesis. Finally, we present the first complete practical attacks on L4, L3 and L2 leakage profiles. These attacks are passive and only assume the very realistic knowledge of a small sample of plaintexts , moreover, we show their devastating effect on real-world datasets.
FCA for Software Product Lines representation
Jessie Carbonnel (LIRMM) :
Software Product Line Engineering (SPLE) is a software engineering domain in which families of similar softwares (called products) are built reusing common artifacts. This requires to analyze commonalities and variabilities, for example to detect which parts are common to several products and which parts differ from one product to another. Such software characteristics that may be present or not in a product are called features. Several approaches in the literature exist to organize features and product configurations in terms of features. In this paper we review those approaches and show that concept lattices are a relevant structure to organize features and product configurations. We also address scaling issues related to formal context computation in the domain of SPLE.
Traitement des conflits dans des problèmes d’optimisation discrète
Alexis CORNET :
De nombreux problèmes d’optimisation sur les graphes, comme le vertex cover connexe, l’arbre de steiner ou les dominants sont NP-complets. Cependant, l’existence d’une solution est garantie - ou il est polynomial d’en déterminer l’existence, et de calculer une solution indépendamment de la valeur de la fonction objectif. Cependant, avec l’ajout de sommets interdits conditionnels, ou conflits - des paires dont les sommets ne peuvent apparaître simultanément dans la solution - l’existence d’une solution n’est plus garantie. Dans les problèmes cités, déterminer l’existence d’une solution a été prouvé NP-complet. Cependant, ces réductions utilisent des graphes quelconques, et un grand nombre de conflits. Nous précisons ces résultats en montrant la NP-complétude des problèmes cités plus haut dans des classes de graphes plus restreintes, et en utilisant un minimum de conflits.
Apache Spark, l’étincelle du big data
Carlos CEPEDA :
Apache Spark est un framework open source de big data : il permet d’effectuer un traitement distribué sur un cluster de plusieurs machines. Spark met facilement en place une architecture de calcul distribué et propose des interfaces de programmation en Scala, Java, Python et R. Il dispose de quelques particularités et de plusieurs fonctionnalités que l’on va aborder. Par exemple, contrairement à MapReduce de Hadoop, le calcul est réalisé à partir de données chargées dans des RDD (resilient distributed datasets) et gardées en mémoire vive. Cela limite le nombre d’entrées/sorties avec les disques durs et rend Spark généralement plus rapide que Hadoop(MapReduce). De plus, Spark peut lire plusieurs sources de données différentes : HDFS, HBase, Hive, Cassandra, Amazon S3.
Candidate Keys Enumeration of a Relational Database Schema.
Karima ENNAOUI :
We investigate the problem of candidate keys enumeration of a relational database schema. We consider the case where the input is a relation schema, composed of pairs of attributes subsets representing the functional dependencies among attributes. The notion of candidate keys is also known as minimal generators in lattice or FCA terminologies.Lucchesi and Osborn gave in 1978 a polynomial incremental algorithm with an exponential space to enumerate all candidate keys of a relation schema. Saiedian and Spencer in 1996, introduced the notion of attribute graph of a set of functional dependencies and showed that candidate keys are union of candidate keys of strongly connected components of the attribute graph.We exploit the presence of unary functional dependencies that form a partial order over the set of attributes. We introduce the notion of key-ideal set : an ideal associated to a candidate key and distinguish the set of minimal key-ideal sets (minimal inclusion-wise). There is a one to one mapping between key-ideal sets and candidate keys. We show that the number of key-ideal sets can be exponential in the number of minimal key- ideal sets. Moreover, if there is a polynomial delay algorithm to enumerate minimal key-ideal sets then there is one for all candidate keys. We also give an incremental polynomial algorithm to enumerate all minimal key-ideal sets. As a consequence, if the number of minimal key-ideal sets is polynomial in the size of the relational schema, then there is a polynomial delay algorithm to enumerate minimal key-ideal sets.
Fouille de donnees
Vanel Siyou (Limos) :
Les méthodes traditionnelles de fouille de données utilisent des vecteurs d’attributs à valeurs déterministes, et ignorent l’aspect incertain des données dans la formulation du problème à traiter (classification supervisée ou non supervisée, recherche de motifs, etc.). Or les données collectées peuvent contenir des erreurs ou être incomplètes (Lindley, 2006), du simple fait des équipements de collecte. Ignorer l’incertitude des données peut engendrer des conclusions approximatives ou inexactes, d’où la nécessité de mettre en œuvre des techniques de gestion de données incertaines (Aggarwal et Yu, 2009). S’il existe des travaux récents dédiés à certaines techniques de fouille de données : indexation de données (Angiulli et Fassetti, 2012), plus proches voisins (Angiulli et Fassetti, 2013), détection d’outliers (Aggarwal et Yu, 2008), arbres de décisions (Tsang et al., 2011), séparateurs à vaste marge (Bing et Zhang, 2004), à notre connaissance, aucun n’est dédié à l’extraction de motifs séquentiels et temporels. L’objet de cette thèse consistera à explorer et à développer de nouveaux modèles d’extraction de motifs séquentiels et temporels, adaptés au contexte d’incertitude de données de la locomotion en FRM. Une des originalités de l’approche résidera dans la prise en compte de l’incertitude dans la formulation du problème (Angiulli et Fassetti, 2013), et pas simplement par la définition de métriques de similarité pour données incertaines (Aggarwal, 2007). Une autre méthode développée au LIMOS sera également examinée et adaptée au problème du FRM (Fournier et al., 2012). La compréhension des relations induites entre ces facteurs permettra la mise en œuvre de modèles optimaux de déplacement des utilisateurs du FRM.
Scheduling resource-constrained projects with transportation constraints.
Marina Vinot (Limos) :
In this paper, the traditional resource-constrained project scheduling problem (RCPSP) is extended with transportation constraints on the resources between activities. The assignment of resources problem and the routing scheduling problem (which involves the strategic (i.e., assignment of resources) and tactical/operational (i.e., routing scheduling) decision levels in supply chain management) are interdependent problems. Assuming that the project structure (location, duration and demand of activities) is provided it is also considered that decisions are known at the strategic level of the transportation problem. The routing of resources from a production facility to another is achieved by a heterogeneous fleet of vehicles. To solve the scheduling resource-constrained project with transportation constraints, we take advantage of a flow network model. By starting with a flow structure for the RCPSP with an insertion algorithm, we can propose a giant trip representation for the routing problem. This approach falls into the indirect split resolution scheme and a new splitting algorithm is introduced to obtain the routing solution of the specific pickup and delivery problem (PDP) which can be extended to the dial-a-ride problem (DARP). To improve this solution a local search is defined on the flow structure. A new set of instances is introduced and numerical experiments prove the efficiency of the approach. This work is the first step to solve problems with more than one resource and to minimize several objectives simultaneously. Keywords : RCPSP , Routing.
no title
Loukmen Regainia (Limos) :
Abstract—The last decade has witnessed Keywords—Model , UML , Security Patterns , Verification
Parameterized complexity is a recent branch of computational complexity theory.
Benjamin Bergougnoux (Limos)
Contrary to the classical approach, we study the complexity of a problem w.r.t. the size of the instance and a parameter (or a collection of parameter). This parameter can take many forms : the size of the solution, the size of a minimum vertex-cover, the treewidth...This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured by the number of bits in the input. The main goal when we study a problem is to find a parameter k such that there is an algorithm that resolves the problem in a polynomial time w.r.t. the size of the instance. We call such an algorithm fixed-parameter tractable and we say that the problem in question parameterized by k is FPT. Such an algorithm allows us to solve the problem on arbitrary large instance whenever the parameter is reasonably small. In another words, we try to hunt the difficulty of a problem by trapping it with a parameter. We will see an example of fixed-tractable algorithm that I created during my master thesis. It solves the problem Common. This problem is a global constraint of the well-know constraint satisfaction problem (CSP). Common is a constraint that takes in input two sets of variables X and Y and two sets of values N and M. This constraint is satisfied iff once assigned the number of variables of X (resp. Y) that take a value assigned to a variable in Y (resp. X) is a value in N (resp. M). This algorithm uses a variant of the well know Max Flow problem where each arc has two attributes : the capacity but also the minimum amount of flow that must pass through the arc. There are a lot of new notions, not necessary hard to understand, but I will try to make this talk easy to understand. If the time permits it, I will talk also about the exponential time hypothesis (ETH), a stronger version of P different to NP. This hypothesis states that we can not solve 3-SAT in subexponential-time. ETH allows us to find a lower bound for the time complexity of many problems. And if the time has mercy, I will also talk about the notion of kernelization. This is a recent branch of the parameterized complexity where we study the performance of the preprocessing. Here we do not want to solve the problem but to reduce the size of the instance of a problem parameterized by a parameter k such that : -The original instance is a Yes-instance iff the reduced instance is a Yes-instance. -The size of the reduced instance is bounded by a function depending only of k.
Survey of distance bounding protocols and threats
David Gerault (Limos) :
Contactless communications are widely used, from parking badges to electronic passports. Such technologies are subject to attacks where an adversary can impersonnate the owner of a tag to a reader by relaying the messages between them. In the last decades, several distance bounding (DB) protocols have been proposed to counter such attacks. However, they are vulnerable to new threats. In this paper, we present the relations between the threat models and, based on the analysis of more than forty existing protocols, we show the most common attack strategies and their counters. Finally, we give general guidelines to build safer distance bounding protocols.
CoLBA : a Collaborative Load Balancing Algorithm to avoid queue overflow in WSNs
Hamadoun Tall (Limos) :
Abstract—Most wireless sensor networks (WSNs) are used for data collection applications. WSNs are known for their ease of deployment which make them very popular. In most data collection applications, traffic is destined towards one node, usually known as the sink. With high data rate, this many-to- one traffic scenario causes queue overflow in the nodes located near the sink. Sensor nodes are known for their limited storage capacities which makes the packet queue overflow even more critical. This issue is often avoided by the routing protocol. Several efforts have recently led to the proposal of several traffic load balancing routing protocols to avoid queue overflow in WSNs. These protocols use various metrics in order to guide the routing mechanism such as the next hop neighbor queue occupancy rate or the next hop current number of children. In this paper, we propose a new routing protocol based on a Collaborative Load Balancing Algorithm (CoLBA). CoLBA uses the time spent by data packets in the queues as a routing metric. In addition to this metric, each node is aware of its queue occupancy rate. In case the receiving node queue is close to be full, all transmitting neighbors will be alerted and asked to choose another next hop. Simulation results on Contiki OS Cooja simulator showed that CoLBA achieves a better packet delivery rate and much less queue overflow compared to a standard routing protocol based on minimal hop counts.
Preuve à divulgation nulle de connaissance
Xavier Bultel (Limos) :
-J’ai résolu ton problème, mais je ne veux pas te montrer la solution... Ha, pas de preuve, pas de chocolat !' Les preuves à divulgation nulle de connaissance permettent de prouver la connaissance d’une solution à une instance d’un problème difficile sans révéler la moindre information sur cette solution. Par exemple, le sudoku est un problème NP. À un concours de sudoku, vous résolvez une grille particulièrement difficile. Vous voulez prouver au jury que vous avez réussi, mais vous craignez que celui-ci soit corrompu et vole votre solution... Que faire ? On s’intéressera d’abord aux preuves de connaissance sur des problèmes classiques de graphes (isomorphisme, k-coloration...), puis on s’intéressera aux cas des problèmes cryptographiques et aux implications de ces preuves.