Search

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $\epsilon$-spectral sparsifier in sublinear time $\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for $k$-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut., Comment: v2: several small improvements to the text. An extended abstract will appear in FOCS'20; v3: corrected a minor mistake in Appendix A; v4: final version as published in SICOMP

Fuel cell durability being one of the technical bolts regarding the technology industrialization in the automotive sector, durabilityimprovement methods are particularly relevant. Fault tolerant control process enables to increase fuel cell durability by detecting and correcting fuel cell faults in real time. Fuel cells are prone to faults because they are very sensitive to operating conditions. In vehicle application, fault risk is exacerbated as dynamic conditions are often encountered. Dynamic conditions make the fuel cell control harder because it impacts reactants supply, thermal management, water management… If not corrected, those faults degrade the fuel cell and reduce its remaining useful lifetime

Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is when compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. The objective of this paper is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1.We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing 2-approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1., Les solveurs directs creux utilisant de la compression low-rank ont montré leur efficacité pour résoudre de grands systèmes. Les améliorer permetde 1) résoudre de plus grands problèmes et 2) accélérer la résolution. Une caractéristique principale de ces solveurs est quand la compression est réalisée. Il existe deux approches: (1) tous les blocs sont compressés avant le début de la factorisation, ce qui minimise la consommation mémoire, ou (2) chaque bloc est compressé au plus tard, ce qui permet d’avoir de meilleures performances. L’objectif de cet article est de proposer une approche intermédiaire, qui accélère les calculs au maximum tout en restant en dessous d’une limite mémoire donnée. Cela devrait permettre de résoudre de grands problèmes que l’approche 2 ne peut pas résoudre ou de réduire le temps d’exécution de l’approche 1. Nous proposonsune stratégie memory-aware où chaque bloc peut ˆêtre compressé au début ou au plus tard. Nous commençons par considérer le problème où toutes les informations (consommation mémoire et temps d’exécution en version compressée ou non) sont parfaitement connues. Nous montrons que ce problème est une variante du problème NP-complet Knapsack et adaptons une 2-approximation pour notre problème. Malheureusement, toutes ces informations dépendent de propriétés numériques et ne sont pas connues `a l’avance. Des modèles sont donc introduits afin d’estimer ces valeurs. Des expérimentations avec le solveur PaStiX montrent que notre approche permet d’avoir un excellent compromis entre consommation mémoire et temps d’exécution. Par exemple, pour la matrice Geo1438, l’approche 2 utilise trois fois plus de mémoire que l’approche 1, qui est trois fois plus lente. Notre nouvelle méthode permet d’obtenir à la fois un temps d’exécution seulement 30% supérieur à celui de l’approche 2 tout en ayant une consommation mémoire seulement supérieure de 30% à celle de l’approche 1.

We show that simple modifications to van der Hoeven's forward and inverse truncated Fourier transforms allow the algorithms to be performed in-place, and with only a linear overhead in complexity.

In order to improve link prediction process in a knowledge graph, we tackle the problem of learning representations of entities and relations. The strength of the existing models in this domain mainly relies on its ability of modeling and inferring the patterns of the relations. In this paper, we propose a new knowledge graph embedding approach called TransModE that has the ability to represent all simple and complex relation patterns. Inspired by TransE, TransModE represents the relations between the entities of a knowledge graph as a transition in the modulus space. Experimenting our model on multiple benchmark knowledge graphs shows the simplicity and the scalability of TransModE. It also shows that TransModE outperforms existing state-of-the-art models by being able to infer and model all types of relations.

Computing persistent homology using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, contrary to the case of computing persistent homology using the Euclidean distance or even the $k$-distance, it is not known how to compute the persistent homology of high dimensional data using Gaussian kernels. In this paper, we consider a power distance version of the Gaussian kernel distance (GKPD) given by Phillips, Wang and Zheng, and show that the persistent homology of the \v{C}ech filtration of $P$ computed using the GKPD is approximately preserved. For datasets in $d$-dimensional Euclidean space, under a relative error bound of $\varepsilon \in [0,1]$, we obtain a dimensionality of $(i)$ $O(\varepsilon^{-2}\log^2 n)$ for $n$-point datasets and $(ii)$ $O(D\varepsilon^{-2}\log (Dr/\varepsilon))$ for datasets having diameter $r$ (up to a scaling factor). We use two main ingredients. The first one is a new decomposition of the squared radii of \v{C}ech simplices using the kernel power distance, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second one is the Random Fourier Features (RFF) map of Rahimi and Recht [NeurIPS 2007], as used by Chen and Phillips [ALT 2017].

An improved bound for one of the founding relations of HGCD-D algorithm is presented. This allows to put a lower limit on the iteration count of the first sdiv loop, to impose a particular structure on the accumulated quotients and to bound the size of the largest matrix element. The matrix product M.M' is proved to have its upper and lower size bound differ by at most two bits.

Setting up IoT monitoring solutions requires a significant workforce for deployment and maintenance. This becomes particularly costly when a massive number of sensors are deployed. In this paper, we propose a generic solution based on energyautonomous LPWAN sensors deployed on the fly. On one side, we propose an efficient management strategy that adapts the transmission period of sensors in order to receive a chosen amount of information on each sensor cluster that emits similar information. Moreover, we develop a method that generates realtime estimates based on the sensor message history. After showing the relevance of our estimation method, we show that our sensor management method is efficient by comparing it to a baseline. Additionally, our tools are robust to the hazards occurring in the IoT: sensor arrivals and departures, noisy measuring in a highly variable environment, misplacement of sensors. Overall, this paper proposes a way to scale up IoT, breaking the deployment cost barrier and paving the way for universal and versatile monitoring solutions.

International audience; La décomposition tensorielle a récemment fait l'objet d'une attention croissante dans la communauté de l'apprentissage automatique en raison de sa polyvalence dans le traitement des données à grande échelle. Cependant, cette tâche devient plus difficile lorsqu'il s'agit de prendre en comte la dimension temporelle. Dans cet article, nous étendons la décomposition tensorielle à l'extraction de phénotypes temporels, décrits comme un combinaison de caractéristiques sur une fenêtre de temps. Nous proposons un nouveau modèle de décomposition intégrant plusieurs régularisations pour améliorer l'interprétabilité des phénotypes extraits. Nous validons ce dernier sur des données synthétiques et réelles provenant de l'Assistance Publique-Hôpitaux de Paris (AP-HP). Les résultats montrent qu'il est plus performant que les modèles les plus récents de décomposition et qu'il découvre des phénotypes intéressants pour les cliniciens.

During the two last decades, sustainability of IT infrastructures like datacenters became a major concern for computer giants like Google or Amazon. Datacenters powered with renewable energy have been proposed. But because of the intermittency of these power alternatives, these platforms remains connected to the classical power grid. IT structure and electrical constraints were often questioned separately, leading to a non-efficient global system. In this paper, an energy self-sufficient green datacenter is modeled and designed, by proposing an electrically autonomous infrastructure including wind turbines, solar panels and its own short and longterm storage devices mainly based on batteries and hydrogen system. Existing sizing approaches limit themselves to a perfect QoS leading to an overestimation of the needed equipment. In this paper we show how to reduce and combat this overprovioning by questioning its impact on the QoS and needed equipment: decreasing the number of computing or storage elements (servers and batteries). As an example, decreasing the targeted QoS from 100 to 95% more than halves the needed number of servers, while a decrease of 30% of the battery capacity has a negligible impact on the electrical infrastructure., Au cours des deux dernières décennies, la durabilité des infrastructures informatiques telles que les centres de données est devenue une préoccupation majeure pour les géants de l'informatique comme Google ou Amazon. Des centres de données alimentés par des énergies renouvelables ont été proposés. Mais en raison de l'intermittence de ces alternatives énergétiques, ces plateformes restent connectées au réseau électrique classique. La structure informatique et les contraintes électriques ont souvent été questionnées séparément, conduisant à un système global non efficace. Dans cet article, un centre de données vert autosuffisant en énergie est modélisé et conçu, en proposant une infrastructure électriquement autonome comprenant des éoliennes, des panneaux solaires et ses propres dispositifs de stockage à court et long terme principalement basés sur des batteries et un système à hydrogène. Les approches de dimensionnement existantes se limitent à une qualité de service parfaite, ce qui conduit à une surestimation des équipements nécessaires. Dans cet article, nous montrons comment réduire et combattre cette surestimation en questionnant son impact sur la qualité de service et les équipements nécessaires : en diminuant le nombre d'éléments de calcul ou de stockage (serveurs et batteries). A titre d'exemple, la diminution de la qualité de service visée de 100 à 95% réduit de plus de la moitié le nombre de serveurs nécessaires, tandis qu'une diminution de 30% de la capacité des batteries a un impact négligeable sur l'infrastructure électrique.

Background Reliable and interpretable automatic extraction of clinical phenotypes from large electronic medical record databases remains a challenge, especially in a language other than English. Objective We aimed to provide an automated end-to-end extraction of cohorts of similar patients from electronic health records for systemic diseases. Methods Our multistep algorithm includes a named-entity recognition step, a multilabel classification using medical subject headings ontology, and the computation of patient similarity. A selection of cohorts of similar patients on a priori annotated phenotypes was performed. Six phenotypes were selected for their clinical significance: P1, osteoporosis; P2, nephritis in systemic erythematosus lupus; P3, interstitial lung disease in systemic sclerosis; P4, lung infection; P5, obstetric antiphospholipid syndrome; and P6, Takayasu arteritis. We used a training set of 151 clinical notes and an independent validation set of 256 clinical notes, with annotated phenotypes, both extracted from the Assistance Publique-Hôpitaux de Paris data warehouse. We evaluated the precision of the 3 patients closest to the index patient for each phenotype with precision-at-3 and recall and average precision. Results For P1-P4, the precision-at-3 ranged from 0.85 (95% CI 0.75-0.95) to 0.99 (95% CI 0.98-1), the recall ranged from 0.53 (95% CI 0.50-0.55) to 0.83 (95% CI 0.81-0.84), and the average precision ranged from 0.58 (95% CI 0.54-0.62) to 0.88 (95% CI 0.85-0.90). P5-P6 phenotypes could not be analyzed due to the limited number of phenotypes. Conclusions Using a method close to clinical reasoning, we built a scalable and interpretable end-to-end algorithm for extracting cohorts of similar patients.

International audience; Route planning represents a major challenge with a substantial impact on safety, economy, and even climate. An ever-growing urban population caused a significant increase in commuting times, therefore, stressing the prominence of efficient real-time route planning. In essence, the goal is to compute the fastest route to reach the target location in a realistic environment where traffic conditions are time-evolving. Consequently, a large volume of traffic data is potentially required and the route continuously updated. We thereby address the rerouting problem to answer questions such as when, how often, and where is rerouting worthwhile. We base our study on a real dataset, comprising the travel times of the road segments of New York, London, and Chicago, collected over three months. By exploiting this dataset, we implement an optimal algorithm, able to mimic ideal predictions of road segment speeds in the network. Thereby, allowing us to compute the lower bound of travel-time to serve as a reference against other routing techniques. Mainly, we quantify the achieved travel-time gain of a static, no rerouting , and continuous rerouting strategies. Surprisingly, we find that traffic conditions are sufficiently stable for short time windows, and rerouting a vehicle is very seldom useful when exploiting accurate statistics at departure time. Typically, real-time rerouting should only be triggered during rush hours, for long routes, passing through well-identified road segments.

International audience; Inspired by the recent success of parallelized exact methods to solve difficult scheduling problems, we present a general parallel beam search framework for combinatorial optimization problems. Beam search is a constructive metaheuristic traversing a search tree layer by layer while keeping in each layer a bounded number of promising nodes to consider many partial solutions in parallel. We propose a variant which is suitable for intra-node parallelization by multithreading with data parallelism. Diversification and inter-node parallelization are combined by performing multiple randomized runs on independent workers communicating via MPI. For sufficiently large problem instances and beam widths our pro-totypical implementation in the JIT-compiled Julia language admits speed-ups between 30 − 42× on 46 cores with uniform memory access for two difficult classical problems, namely Permutation Flow Shop Scheduling (PFSP) with flowtime objective and the Traveling Tournament Problem (TTP). This allowed us to perform large beam width runs to find 11 new best feasible solutions for 22 difficult TTP benchmark instances up to 20 teams with an average wallclock runtime of about one hour per instance.

Personalized designs bring added value to the products and the users. Meanwhile, they also pose challenges to the product design process as each product differs. In this paper, with the focus on personalized fit, we present an overview as well as details of the personalized design process based on design practice. The general workflow of personalized product design is introduced first. Then different steps in the workflow such as human data/parameters acquisition, computational design, design for digital fabrication, and product evaluation are presented. Tools and methods that are often used in different steps in the process are also outlined where in human data acquisition, 3D scanning, and digital human models are addressed. For computational design, the use of computational thinking tools such as abstraction, decomposition, pattern recognition and algorithms are discussed. In design for digital fabrication, additive manufacturing methods (e.g. FDM), and their requirements on the design are highlighted. For product evaluation, both functional evaluation and usability evaluation are considered and the evaluation results can be the starting point of the next design iteration. Finally, several case studies are presented for a better understanding of the workflow, the importance of different steps in the workflow and the deviations in the approach regarding different contexts. In conclusion, we intend to provide designers a holistic view of the design process in designing personalized products as well as help practitioners trigger innovations regarding each step of the process.

To study the propagation of information from individual to individual, we need mobility datasets. Existing datasets are not satisfactory because they are too small, inaccurate or target a homogeneous subset of population. To draw valid conclusions, we need sufficiently large and heterogeneous datasets. Thus we aim for a passive non-intrusive data collection method, based on sniffers that are to be deployed at some well-chosen street intersections. To this end, we need optimization techniques for efficient placement of sniffers. We introduce a heuristic, based on graph theory notions like the vertex cover problem along with graph centrality measures., Will be published to IEEE International Smart Cities Conference 2022

In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches., Dans ce travail, nous étendons une méthode de type Burer-Monteiro pour calculer des minorants convexes (relaxation demi-définie positive) pour le problème de Maximum d'a Posteriori dans des modèles graphiques discrets où les variables ont un nombre d'états et des potentiels binaires arbitraires. Nous considérons une méthode incluant une contrainte pénalisée et une algorithme de type descente en coordonnées par bloc qui évite l’apparition de coefficient de magnitude importante dans la matrice de coûts. Nous montrons que l'algorithme est décroissant. Une évaluation empirique montre que l'approche BCD se compare favorablement à l'approche pénalisée et des minorants linéaires usuels, tels que ceux basés sur des approches de type "message passing" convergentes.

Infinite dimensional systems allow to model a large panel of physical phenomena for which the state variables evolve both temporally and spatially. This manuscript deals with the evaluation of the stability of their equilibrium point. Two case studies are treated in particular: the stability analysis of ODE-transport, and ODE-reaction-diffusion interconnected systems. Theoretical tools exist for the stability analysis of these infinite-dimensional linear systems and are based on an operator algebra rather than a matrix algebra. However, these existence results raise a problem of numerical constructibility. During implementation, an approximation is performed and the results are conservative. The design of numerical tools leading to stability guarantees for which the degree of conservatism is evaluated and controlled is then a major issue. How can we develop reliable numerical criteria to rule on the stability or instability of infinite-dimensional linear systems? In order to answer this question, one proposes here a new generic method, which is decomposed in two steps. First, from the perspective of Legendre polynomials approximation, augmented models are built and split the original system into two blocks: on the one hand, a finite-dimensional approximated system is isolated, on the other hand, the infinite-dimensional truncation error is preserved and modeled. Then, frequency and time tools of finite dimension are deployed in order to propose stability criteria that have high or low numerical load depending on the approximated order. In frequencies, with the aid of the small gain theorem, sufficient stability conditions are obtained. In temporal, with the aid of the Lyapunov theorem, an under estimate of the stability regions is proposed as a linear matrix inequality and an over estimate as a positivity test. Our two case studies have been treated with this general methodology. The main result concerns the case of ODE-transport interconnected systems, for which the approximation and stability analysis using Legendre polynomials leads to exponentially fast converging estimates of stability regions. The method developed in this manuscript can be adapted to other types of approximations and exported to other infinite-dimensional linear systems. Thus, this work opens the way to obtain necessary and sufficient finite-dimensional conditions of stability for infinite-dimensional systems., Les systèmes de dimension infinie permettent de modéliser un large spectre de phénomènes physiques pour lesquels les variables d'états évoluent temporellement et spatialement. Ce manuscrit s'intéresse à l'évaluation de la stabilité de leur point d'équilibre. Deux études de cas seront en particulier traitées : l'analyse de stabilité des systèmes interconnectés à une équation de transport, et à une équation de réaction-diffusion. Des outils théoriques existent pour l'analyse de stabilité de ces systèmes linéaires de dimension infinie et s'appuient sur une algèbre d'opérateurs plutôt que matricielle. Cependant, ces résultats d'existence soulèvent un problème de constructibilité numérique. Lors de l'implémentation, une approximation est réalisée et les résultats sont conservatifs. La conception d'outils numériques menant à des garanties de stabilité pour lesquelles le degré de conservatisme est évalué et maîtrisé est alors un enjeu majeur. Comment développer des critères numériques fiables permettant de statuer sur la stabilité ou l'instabilité des systèmes linéaires de dimension infinie ? Afin de répondre à cette question, nous proposons ici une nouvelle méthode générique qui se décompose en deux temps. D'abord, sous l'angle de l'approximation sur les polynômes de Legendre, des modèles augmentés sont construits et découpent le système original en deux blocs : d'une part, un système de dimension finie approximant est isolé, d'autre part, l'erreur de troncature de dimension infinie est conservée et modélisée. Ensuite, des outils fréquentiels et temporels de dimension finie sont déployés afin de proposer des critères de stabilité plus ou moins coûteux numériquement en fonction de l'ordre d'approximation choisi. En fréquentiel, à l'aide du théorème du petit gain, des conditions suffisantes de stabilité sont obtenues. En temporel, à l'aide du théorème de Lyapunov, une sous-estimation des régions de stabilité est proposée sous forme d'inégalité matricielle linéaire et une sur-estimation sous forme de test de positivité. Nos deux études de cas ont ainsi été traitées à l'aide de cette méthodologie générale. Le principal résultat obtenu concerne le cas des systèmes EDO-transport interconnectés, pour lequel l'approximation et l'analyse de stabilité à l'aide des polynômes de Legendre mène à des estimations des régions de stabilité qui convergent exponentiellement vite. La méthode développée dans ce manuscrit peut être adaptée à d'autres types d'approximations et exportée à d'autres systèmes linéaires de dimension infinie. Ce travail ouvre ainsi la voie à l'obtention de conditions nécessaires et suffisantes de stabilité de dimension finie pour les systèmes de dimension infinie.

Learning to reach goals is a competence of high practical relevance to acquire for intelligent agents. For instance, this encompasses many navigation tasks ("go to target X"), robotic manipulation ("attain position Y of the robotic arm"), or game-playing scenarios ("win the game by fulfilling objective Z"). As a living being interacting with the world, I am constantly driven by goals to reach, varying in scope and difficulty.Reinforcement Learning (RL) holds the promise to frame and learn goal-oriented behavior. Goals can be modeled as specific configurations of the environment that must be attained via sequential interaction and exploration of the unknown environment. Although various deep RL algorithms have been proposed for goal-oriented RL, existing methods often lack principled understanding, sample efficiency and general-purpose effectiveness. In fact, very limited theoretical analysis of goal-oriented RL was available, even in the basic scenario of finitely many states and actions.We first focus on a supervised scenario of goal-oriented RL, where a goal state to be reached in minimum total expected cost is provided as part of the problem definition. After formalizing the online learning problem in this setting often known as Stochastic Shortest Path (SSP), we introduce two no-regret algorithms (one is the first available in the literature, the other attains nearly optimal guarantees).Beyond training our RL agent to solve only one task, we then aspire that it learns to autonomously solve a wide variety of tasks, in the absence of any reward supervision. In this challenging unsupervised RL scenario, we advocate to "Set Your Own Goals" (SYOG), which suggests the agent to learn the ability to intrinsically select and reach its own goal states. We derive finite-time guarantees of this popular heuristic in various settings, each with its specific learning objective and technical challenges. As an illustration, we propose a rigorous analysis of the algorithmic principle of targeting "uncertain" goals which we also anchor in deep RL.The main focus and contribution of this thesis are to instigate a principled analysis of goal-oriented exploration in RL, both in the supervised and unsupervised scenarios. We hope that it helps suggest promising research directions to improve the interpretability and sample efficiency of goal-oriented RL algorithms in practical applications., Apprendre à atteindre des buts est une compétence à acquérir à grande pertinence pratique pour des agents intelligents. Par exemple, ceci englobe de nombreux problèmes de navigation (se diriger vers telle destination), de manipulation robotique (atteindre telle position du bras robotique) ou encore certains jeux (gagner en accomplissant tel objectif). En tant qu'être vivant interagissant avec le monde, je suis constamment motivé par l'atteinte de buts, qui varient en portée et difficulté.L'Apprentissage par Renforcement (AR) est un paradigme prometteur pour formaliser et apprendre des comportements d'atteinte de buts. Un but peut être modélisé comme une configuration spécifique d'états de l'environnement qui doit être atteinte par interaction séquentielle et exploration de l'environnement inconnu. Bien que divers algorithmes en AR dit "profond" aient été proposés pour ce modèle d'apprentissage conditionné par des états buts, les méthodes existantes manquent de compréhension rigoureuse, d'efficacité d'échantillonnage et de capacités polyvalentes. Il s'avère que l'analyse théorique de l'AR conditionné par des états buts demeurait très limitée, même dans le scénario basique d'un nombre fini d'états et d'actions.Premièrement, nous nous concentrons sur le scénario supervisé, où un état but qui doit être atteint en minimisant l'espérance des coûts cumulés est fourni dans la définition du problème. Après avoir formalisé le problème d'apprentissage incrémental (ou ``online'') de ce modèle souvent appelé Plus Court Chemin Stochastique, nous introduisons deux algorithmes au regret sous-linéaire (l'un est le premier disponible dans la littérature, l'autre est quasi-optimal).Au delà d'entraîner l'agent d'AR à résoudre une seule tâche, nous aspirons ensuite qu'il apprenne de manière autonome à résoudre une grande variété de tâches, dans l'absence de toute forme de supervision en matière de récompense. Dans ce scénario non-supervisé, nous préconisons que l'agent sélectionne lui-même et cherche à atteindre ses propres états buts. Nous dérivons des garanties non-asymptotiques de cette heuristique populaire dans plusieurs cadres, chacun avec son propre objectif d'exploration et ses propres difficultés techniques. En guise d'illustration, nous proposons une analyse rigoureuse du principe algorithmique de viser des états buts "incertains", que nous ancrons également dans le cadre de l'AR profond.L'objectif et les contributions de cette thèse sont d'améliorer notre compréhension formelle de l'exploration d'états buts pour l'AR, dans les scénarios supervisés et non-supervisés. Nous espérons qu'elle peut aider à suggérer de nouvelles directions de recherche pour améliorer l'efficacité d'échantillonnage et l'interprétabilité d'algorithmes d'AR basés sur la sélection et/ou l'atteinte d'états buts dans des applications pratiques.

International audience; L'Étiquetage en Composantes Connexe (ECC) est une opération fondamentale de la vision numérique depuis des décennies. Bien que la majeure partie de la littérature traite des algorithmes en 2D, sur des applications telles que la vidéo-surveillance ou la conduite autonome, il y a de plus en plus besoin d'algorithmes pour traiter des images en 3D, notamment pour des applications médicales. Bien que les algorithmes d'ECC en 2D génèrent un nombre important d'accès mémoire et de comparaisons, le problème empire avec algorithmes en 3D. Il s'agit de la malédiction de la dimension. La mise en place d'un algorithme efficace doit donc résoudre ce problème. Ce papier introduit un algorithme utilisant des segments pour étiqueter des volumes en 3D. Les équivalences entre les étiquettes sont accélérées à l'aide d'une nouvelle stratégie atténuant l'impact de la dimension supérieure. Ce nouvel algorithme surpasse les algorithmes de l'État-de-l'art d'un facteur allant de ×1.5 à ×3.1 sur des images médicales et sur des images aléatoires.

One of the main performance issues faced by highperformance platforms is the delay caused by concurrent applications performing I/O. When this happens, applications sharing the I/O bandwidth create congestion, which delays the execution time and affects the platform's overall performance. Several solutions have been proposed to tackle I/O congestion. Among those solutions, I/O scheduling strategies are an essential solution to this problem in HPC systems. Currently, their main drawback is the amount of information needed. In this work, we propose a novel framework for I/O management, IO-SETS. We present the potential of this framework through a simple scheduling solution called SET-10, an I/O scheduling solution that demands minimum information from users and can be easily integrated into HPC environments.

We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders P_v and P_p defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with P_v (resp., P_p). Posets P_v and P_p aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., P_v and P_p are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem., LIPIcs, Vol. 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 21:1-21:17

The drug discovery process is long, costly and very risky. The objective of this doctoral thesis is to improve the relevance of the primary phases of drug discovery by developing computational methods. The first contribution concerns the development of the Pegasus knowledge graph in order to capitalize on the heterogeneous and multi-sourced pharmaco-biological data of the pharmaceutical sector. The industrial applications of Pegasus address the problems of therapeutic projects and allow to characterize off-target effects of perturbators, to design a new experiment, and to identify focused screening libraries. The second contribution concerns the development of an algorithm for the identification of positive control compounds and a normalization algorithm to improve the design and analysis of high content phenotypic screening experiments. These algorithms allow the normalization of phenotypic signatures obtained from screening campaigns and the integration of informative phenotypic similarities in the Pegasus knowledge graph. The third contribution concerns the development of a mathematical model of the microtubule tyrosination cycle which explains, on the one hand, the inactivity of chemical compounds shown to be active outside the cell, and on the other hand, suggests the need to activate two reactions of this cycle, in synergy, to obtain an effect in cellular models. This illustrates the contribution of mathematical modeling to, on the one hand, predict and understand the counter-intuitive dynamics of biochemical processes that are not representable by static knowledge graphs as in Pegasus, and on the other hand, guide the design of new screening experiments. The scientific contributions and industrial applications of this thesis are developed in the context of the primary phases of drug discovery and are intended to extend to the clinical phases of the pharmaceutical process., Le processus de découverte de nouveaux médicaments est long, coûteux et très risqué. L’objectif de cette thèse de doctorat est d’améliorer la pertinence des phases primaires de recherche pharmaceutique en développant des méthodes computationnelles. La première contribution porte sur le développement du graphe de connaissances Pegasus afin de capitaliser sur les données pharmaco-biologiques hétérogènes et de provenances multiples du secteur pharmaceutique. Les applications industrielles de Pegasus répondent à des problématiques de projets thérapeutiques et permettent de caractériser des effets hors cibles de perturbateurs, de concevoir une nouvelle expérience, et d’identifier des librairies de criblage focalisées. La deuxième contribution porte sur le développement d’un algorithme d’identification de composés contrôles positifs et d’un algorithme de normalisation afin d’améliorer la conception et l’analyse d’expériences de criblage phénotypiques à haut contenu. Ces algorithmes permettent de normaliser les signatures phénotypiques obtenues à partir de campagnes de criblage et d’intégrer des similarités phénotypiques informatives dans le graphe de connaissances Pegasus. La troisième contribution porte sur le développement d’un modèle mathématique du cycle de tyrosination des microtubules qui explique, d’une part, l’inactivité de composés chimiques dans les cellules montrés actifs hors cellule, et d’autre part, suggère la nécessité d’activer deux réactions de ce cycle, en synergie, pour obtenir un effet dans les modèles cellulaires. Ceci illustre l’apport de la modélisation mathématique pour, d’une part, prédire et comprendre la dynamique contre-intuitive de processus biochimiques qui n’est pas représentable par des graphes de connaissances statiques comme dans Pegasus, et d’autre part, guider la conception de nouvelles expériences de criblage. Les contributions scientifiques et les applications industrielles de cette thèse sont développées dans le cadre des phases primaires de recherche de nouveaux médicaments et ont vocation à s’étendre aux phases cliniques du processus pharmaceutique.

International audience; Objective: Waiting time for a consultation for chronic pain is a widespread health problem. This paper present the design of an ontology use to assess patients referred to a consultation for chronic pain. Methods: We designed OntoDol, an ontology of pain domain for patient triage based on priority degrees. Terms were extracted from clinical practice guidelines and mapped to SNOMED-CT concepts through the Python module Owlready2. Selected SNOMED-CT concepts, relationships, and the TIME ontology, were implemented in the ontology using Protégé. Decision rules were implemented with SWRL. We evaluated OntoDol on 5 virtual cases. Results: OntoDol contains 762 classes, 92 object properties and 18 SWRL rules to assign patients to 4 categories of priority. OntoDol was able to assert every case and classify them in the right category of priority. Conclusion: Further works will extend OntoDol to other diseases and assess OntoDol with real world data from the hospital.

International audience; Nous nous intéressons au problème du rendezvous de deux robots autonomes à capacités réduites. Il a été démontré dans la littérature que le problème n'admet pas de solution déterministe dans le modèle semi-synchrone si les robots sont amnésiques et que leur système de coordonnées est symétrique. Dans cet article, nous montrons qu'il suffit que les robots admettent des unités de distance différentes pour que le problème devienne soluble. Mots-clefs : Réseaux de robots, rassemblement, désaccord † Ce travail a été financé en partie par le projet ANR project SAPPORO, ref. 2019-CE25-0005-1 et par le projet ANR ESTATE, ref. ANR-16-CE25-0009-03.

International audience; Cet article traite de l'exploration perpétuelle d'une grille par un petit nombre de robots ayant des capacités très limitées. Ces robots ont une vision à portée bornée, sont désorientés (ils n'ont pas de système de coordonnées commun), et ne savent pas distinguer leur droite de leur gauche. Ils exécutent le même algorithme de manière synchrone et sont équipés de lumières capables de changer de couleur. En outre, chaque robot dispose d'un panel réduit de couleurs et ces couleurs constituent les seules informations pouvant être mémorisées par le robot et capturées par les robots alentour. Dans ce cadre restreint, on souhaite que les robots visitent infiniment souvent et de manière exclusive chaque noeud d'une grille. Notre but est de trouver des solutions mobilisant le moins de ressources possibles. En supposant une portée de 1, nous proposons un algorithme utilisant seulement 3 robots et nous prouvons que ce nombre est optimal. Nous avons aussi élaboré un algorithme utilisant seulement une couleur (optimalité en nombre de couleurs). Ce dernier fonctionne avec 5 robots et suppose une portée de visibilité à distance 2. Cette hypothèse a été montrée nécessaire dans un article précédent.

This thesis is carried out within the frame of the CoolMagEvo ANR project, which aims at developing of magneto cooling systems. In this context, we consider the two following simulation models as time-consuming optimization problems: a model of Magneto Caloric Materials (MCMs) and a model of an Active Magnetic Regenerator (AMR). According to the defined requirements of the problems, we develop three special optimization algorithms. Then, we develop the software tool based on the proposed algorithms for easily solving different problems of these simulation models. Next, using this tool, we present the new method based on optimization, for reproducing physical properties of different MCMs. Finally, we study the impact of the control and design parameters of the AMR model on its performance in two application modes., Cette thèse est réalisée dans le cadre du projet ANR CoolMagEvo, qui se donne comme objectif le développement de systèmes de réfrigération magnétique. Nous disposons de deux modèles de simulation dont on a assigné une fonction de problèmes d'optimisation: un modèle de Matériaux Magnetocaloriques (MMCs) et un modèle d'un Régénérateur Magnétique Actif (AMR). Selon les exigences des modèles, nous avons développé trois algorithmes d'optimisation. Par la suite, nous avons développé un outil basé sur les algorithmes proposés pour résoudre facilement et efficacement différents problèmes de ces modèles de simulation. Ensuite, à l'aide de cet outil, nous avons eu la possibilité d'ériger la nouvelle méthode basée sur l'optimisation, qui permet de reproduire les propriétés physiques de différents MMCs. Enfin, nous avons étudié l'impact des paramètres de contrôle et de désign du modèle de l'AMR sur ses performances pour deux modes d'application.

Let G be an undirected bipartite graph with positive integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al., for computing maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O(\sqrt{|V|}W'/k(|V|,W'/N))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where |V| and N denote the number of nodes and the maximum edge weight of G, respectively and k(x,y)=log(x) /log(x^2/y). The parameter W' is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second-largest edge weight in the current working graph in any decomposition step of the algorithm. In best the case, W'=O(|E|) where |E| is the number of edges of G and in the worst case, W'=W, that is, |E| \leq W' \leq W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W'. Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.

International audience

We consider the list update problem as defined in the seminal work on competitive analysis by Sleator and Tarjan [13] . An instance of the problem consists of a sequence of requests to access items in a linked list. After an item is accessed, that item can be moved to any position forward in the list at no cost (a move called free exchange), and, at any time, any two adjacent items can be swapped at a cost of 1 (a move called paid exchange). The cost to access an item is equal to its current position in the list. The goal is to dynamically rearrange the list so as to minimize the total cost (accrued from accesses and exchanges) over the request sequence. We show a lower bound of 12/11 on the worst-case ratio between the performance of an (offline) optimal algorithm that can only perform free exchanges and that of an (offline) optimal algorithm that can perform both paid and free exchanges. This answers the question of the asymptotic relative power of the two models which has been open since Reingold and Westbrook [11] showed in 1996 that Sleator and Tarjan erred in [13] when they claimed that the two models are equivalent.

We introduce the Red-Blue Separation problem on graphs, where we are given a graph $G=(V,E)$ whose vertices are colored either red or blue, and we want to select a (small) subset $S \subseteq V$, called red-blue separating set, such that for every red-blue pair of vertices, there is a vertex $s \in S$ whose closed neighborhood contains exactly one of the two vertices of the pair. We study the computational complexity of Red-Blue Separation, in which one asks whether a given red-blue colored graph has a red-blue separating set of size at most a given integer. We prove that the problem is NP-complete even for restricted graph classes. We also show that it is always approximable in polynomial time within a factor of $2\ln n$, where $n$ is the input graph's order. In contrast, for triangle-free graphs and for graphs of bounded maximum degree, we show that Red-Blue Separation is solvable in polynomial time when the size of the smaller color class is bounded by a constant. However, on general graphs, we show that the problem is $W[2]$-hard even when parameterized by the solution size plus the size of the smaller color class. We also consider the problem Max Red-Blue Separation where the coloring is not part of the input. Here, given an input graph $G$, we want to determine the smallest integer $k$ such that, for every possible red-blue coloring of $G$, there is a red-blue separating set of size at most $k$. We derive tight bounds on the cardinality of an optimal solution of Max Red-Blue Separation, showing that it can range from logarithmic in the graph order, up to the order minus one. We also give bounds with respect to related parameters. For trees however we prove an upper bound of two-thirds the order. We then show that Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can be approximated in polynomial time within a factor of $O(\ln^2 n)$.

Au cours des deux dernières décennies, la résilience des infrastructures informatiques telles que les centres de données est devenue une préoccupation majeure pour les géants de l'informatique comme Google ou Amazon. Des centres de données alimentés par des énergies renouvelables ont été proposés. Mais en raison de l'intermittence de ces alternatives énergétiques, ces plate-formes restent connectées au réseau électrique classique. La structure informatique et les contraintes électriques ont souvent été questionnées séparément, conduisant à un système global non efficace. Dans cet article, un centre de données décarboné auto-suffisant en énergie est modélisé et conçu, en proposant une infrastructure électriquement autonome comprenant des éoliennes, des panneaux solaires et des dispositifs de stockage à court (batteries) et à long terme (systèmes à hydrogène). Le dimensionnement d'une telle infrastructure est l'une des principales questions du projet DATAZERO2. Cet article montre comment réduire et combattre le surdimensionnement en questionnant l'impact de la réduction d'éléments de calcul ou de stockage (serveurs et batteries) sur la qualité de service.

A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $\gamma(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set edges $A\subseteq E(G)$ such that $\gamma(G-A)=\gamma(G)+1$. A chordal graph is a graph with no induced cycle of length four or more. In this paper, we prove that the bondage number of a chordal graph $G$ is at most the order of its maximum clique, that is, $b(G)\leq \omega(G)$. We show that this bound is best possible.

International audience

Currently, most of the piezoelectric structures are designed under deterministic conditions, where the influence of uncertain factors on the output motion accuracy is ignored. In this work, a probabilistic reliability-based topology optimization method for piezoelectric structure is proposed to deal with the working voltage uncertainty. A nested double-loop optimization algorithm of minimizing the total volume while satisfying the reliability requirement of the displacement performance is established, where the PEMAP-P (piezoelectric material with penalization and polarization) model is used for parameterization of stiffness matrix, piezoelectric coupling matrix, and polarization direction. This strategy consists of an inner loop for reliability analysis and an outer loop for topology optimization. The reliability index approach based on most probable point (MPP) is used for realizing the evaluation of reliability constraint in reliability analysis. The sensitivities of reliability constraint with respect to the random variables and design variables are detailed using the adjoint variable method. Typical examples are performed to illustrate the effectiveness of the proposed RBTO method. A comparison of the optimization results for different reliability indexes, standard deviations of the voltage, spring stiffnesses, and displacement limits are conducted, as well as the deterministic topology optimization results.

Metaheuristics are resolution algorithms with a large number of parameters that allow them to adapt to any type of optimization problem. In order to obtain the best performance, the parameters must be chosen scrupulously, which generates a very tedious parameterization work. It is in this context that parameter tuning approaches have been developed in the literature, where a learning phase allows to explore different sets of parameters to select the best one, and parameter control approaches where the values change adaptively during the execution. In this thesis, we propose to use simultaneously these two parameterization approaches by proposing an approach called automatic multi-configuration of algorithms. In particular, we explore several strategies based on sequential or probabilistic models and compare them to classical approaches for automatic algorithm configuration and adaptive algorithms. Experiments have been conducted on the permutation flowshop scheduling problem and the traveling salesman problem and show the relevance of the proposed approach., Les métaheuristiques sont des algorithmes de résolution présentant un grand nombre de paramètres qui leur permettent de s'adapter à tout type de problème d'optimisation. Afin d'obtenir les meilleures performances, les paramètres doivent être choisis scrupuleusement ce qui engendre un travail de paramétrage très fastidieux. C'est dans ce contexte qu'ont été développées dans la littérature les approches de réglage de paramètres où une phase d'apprentissage permet d'explorer différents jeux de paramètres pour sélectionner le meilleur, et de contrôle de paramètres où les valeurs changent de manière adaptative pendant l'exécution. Dans cette thèse, nous proposons d'utiliser simultanément ces deux approches de paramétrage en proposant une approche appelée multi-configuration automatique d'algorithmes. En particulier, nous explorons plusieurs stratégies basées sur des modèles séquentiels ou probabilistes et nous les comparons aux approches classiques de la configuration automatique d'algorithmes et d'algorithmes adaptatifs. Des expérimentations ont été conduites sur le problème d'ordonnancement de type flowshop de permutation et le problème de voyageur de commerce et montrent la pertinence de l'approche proposée.

National audience; Faut-il être un bon algorithmicien pour être un bon programmeur ? Et inversement, faut-il être un bon programmeur pour être un bon algorithmicien ? Ceci n'est pas le sujet de philosophie ou de NSI du bac 2021 mais ce sont les questions auxquelles s'intéresse cet article.

Air quality is one of the major risk factors in human health. Mobile Crowd Sensing (MCS), which is a new paradigm based on the emerging connected micro-sensor technology, offers the opportunity of the assessment of personal exposure to air pollution anywhere and anytime. This leads to the continuous generation of geolocated data series, which results in a big data volume. Such data is deemed to be a mine of information for various analysis, and a unique opportunity of knowledge discovery about pollution exposure. However, achieving this analysis is far from straightforward. In fact, there is a gap to fill between the raw sensor data series and usable information: raw data is highly uneven, noisy, and incomplete. The major challenge addressed by this thesis is to fill this gap by providing a holistic approach for data analytics and mining in the context of MCS. We establish an end-to-end analytics pipeline, which encompasses data preprocessing, their enrichment with contextual information, as well as data modeling and storage. We implemented this pipeline while ensuring its automatized deployment. The proposed approaches have been applied to real-world datasets collected within the Polluscope project., La qualité de l'air est l'un des principaux facteurs de risque pour la santé humaine. La collecte participative ou Mobile Crowd Sensing (MCS) en anglais, un nouveau paradigme basé sur la technologie émergente des micro-capteurs connectés, offre la possibilité de mesurer l'exposition individuelle à la pollution de l'air n'importe où et n'importe quand. Cela amène à générer en continu des séries de données géo-localisées, qui finissent par former une grande masses de données. Celle-ci constitue une mine d'information pour des analyses variées et une opportunité unique d'extraction de connaissances sur l'exposition à la pollution. Toutefois, cette analyse est loin d'être simple, car il y a un gap entre les séries de données brutes des capteurs et les informations exploitables. En effet, les données brutes sont irrégulières, bruitées et incomplètes. Le défi majeur que cette thèse cherche à relever est de combler ce gap en proposant une approche holistique d'analyse et d'extraction de connaissance des données collectées dans le contexte du MCS. Nous mettons en oeuvre un processus analytique complet comprenant le prétraitement des données, leur enrichissement avec des informations contextuelles, ainsi que la modélisation et le stockage de ces données. Nous l'avons implémenté en veillant à automatiser son déploiement. Les approches proposées sont appliquées sur des données réelles collectées au sein du projet Polluscope.

This work investigates the technical requirement for the actuation of the bi-directional rotational motion (BRM) of engineering-material-based non-rigid origami robots. While the vast majority of previously published results have focused on paper-based origami structures driven by translation-motion, polypropylene (PP) is implemented in this research to investigate its ability to respond to engineering requirements according to BRM. Following this objective, three experiments are proposed to identify the technical performances of PP-based origami and kirigami robots based on Kresling pattern. First, the stabilization test shows that two hundred full folding cycles are required to reach a repeatable mechanical response. Second, the BRM test characterizes the various mechanical performances of both origami and kirigami structure: the PP-based origami outperforms existing structures in the literature. Third, the actuation test shows that the actuation mechanical requirements can be described using three key parameters: the required torque for folding, the shape-blocking stiffness, and the bistable portion. Finally, in order to support the development of PP-based origami/kirigami robots, a ‘Bar and Hinge’ reduced-order model is implemented for the description of the nonlinear hysteretic behavior and bistability. This method constitutes a useful tool for the design of highly nonlinear/bistable engineering structures based on PP origami and kirigami.

An increasing number of datasets are published on the Web, expressed in the standard languages proposed by the W3C such as RDF, RDF (S), and OWL. These datasets represent an unprecedented amount of data available for users and applications. In order to identify and use the relevant datasets, users and applications need to explore them using queries written in SPARQL, a query language proposed by the W3C. But in order to write a SPARQL query, a user should not only be familiar with the query language but also have knowledge about the content of the RDF dataset in terms of the resources, classes or properties it contains. The goal of this thesis is to provide approaches to support the exploration of these RDF datasets. We have studied two alternative and complementary exploration techniques, keyword search and summarization of an RDF dataset. Keyword search returns RDF graphs in response to a query expressed as a set of keywords, where each resulting graph is the aggregation of elements extracted from the source dataset. These graphs represent possible answers to the keyword query, and they can be ranked according to their relevance. Keyword search in RDF datasets raises the following issues: (i) identifying for each keyword in the query the matching elements in the considered dataset, taking into account the differences of terminology between the keywords and the terms used in the RDF dataset, (ii) combining the matching elements to build the result by defining aggregation algorithms that find the best way of linking matching elements, and finally (iii), finding appropriate metrics to rank the results, as several matching elements may exist for each keyword and consequently several graphs may be returned. In our work, we propose a keyword search approach that addresses these issues. Providing a summarized view of an RDF dataset can help a user in identifying if this dataset is relevant to his needs, and in highlighting its most relevant elements. This could be useful for the exploration of a given dataset. In our work, we propose a novel summarization approach based on the underlying themes of a dataset. Our theme-based summarization approach consists of extracting the existing themes in a data source, and building the summarized view so as to ensure that all these discovered themes are represented. This raises the following questions: (i) how to identify the underlying themes in an RDF dataset? (ii) what are the suitable criteria to identify the relevant elements in the themes extracted from the RDF graph? (iii) how to aggregate and connect the relevant elements to create a theme summary? and finally, (iv) how to create the summary for the whole RDF graph from the generated theme summaries? In our work, we propose a theme-based summarization approach for RDF datasets which answers these questions and provides a summarized representation ensuring that each theme is represented proportionally to its importance in the initial dataset., Un nombre croissant de sources de données sont publiées sur le web, exprimées dans les langages proposés par le W3C comme RDF, RDF (S) et OWL. Ces sources représentent un volume de données sans précédent disponible pour les utilisateurs et les applications. Afin d’identifier les sources les plus pertinentes et de les utiliser, il est nécessaire d’en connaître le contenu, par exemple au moyen de requêtes écrites en Sparql, le langage d’interrogation proposé par le W3C pour les sources de données RDF. Mais cela nécessite, en plus de la maîtrise du langage Sparql, de disposer de connaissances sur le contenu de la source en termes de ressources, classes ou propriétés qu’elle contient. L’objectif de ma thèse est d’étudier des approches permettant de fournir un support à l’exploration d’une source de données RDF. Nous avons proposé deux approches complémentaires, la recherche mots-clés et le résumé d’un graphe RDF.La recherche mots-clés dans un graphe RDF renvoie un ou plusieurs sous-graphes en réponse à une requête exprimée comme un ensemble de termes à rechercher. Chaque sous-graphe est l’agrégation d’éléments extraits du graphe initial, et représente une réponse possible à la requête constituée par un ensemble de mots-clés. Les sous-graphes retournés peuvent être classés en fonction de leur pertinence. La recherche par mot-clé dans des sources de données RDF soulève les problèmes suivants : (i) l’identification pour chaque mot-clé de la requête des éléments correspondants dans le graphe considéré, en prenant en compte les différences de terminologies existant entre les mots-clés et les termes utilisés dans le graphe RDF, (ii) la combinaison des éléments de graphes retournés pour construire un sous-graphe résultat en utilisant des algorithmes d’agrégation capable de déterminer la meilleure façon de relier les éléments du graphe correspondant à des mots-clés, et enfin (iii), comme il peut exister plusieurs éléments du graphe qui correspondent à un même mot-clé, et par conséquent plusieurs sous-graphes résultat, il s’agit d’évaluer la pertinence de ces sous-graphes par l’utilisation de métriques appropriées. Dans notre travail, nous avons proposé une approche de recherche par mot-clé qui apporte des solutions aux problèmes ci-dessus.Fournir une vue résumée d’un graphe RDF peut être utile afin de déterminer si ce graphe correspond aux besoins d’un utilisateur particulier en mettant en évidence ses éléments les plus importants ; une telle vue résumée peut faciliter l’exploration du graphe. Dans notre travail, nous avons proposé une approche de résumé originale fondée sur l’identification des thèmes sous-jacents dans un graphe RDF. Notre approche de résumé consiste à extraire ces thèmes, puis à construire le résumé en garantissant que tous les thèmes sont représentés dans le résultat. Cela pose les questions suivantes : (i) comment identifier les thèmes dans un graphe RDF ? (ii) quels sont les critères adaptés pour identifier les éléments les plus pertinents dans les sous-graphes correspondants à un thème ? (iii) comment connecter les éléments les plus pertinents pour créer le résumé d’une thème ? et enfin (iv) comment générer un résumé pour le graphe initial à partir des résumés de thèmes ? Dans notre travail, nous avons proposé une approche qui fournit des réponses à ces questions et qui produit une représentation résumée d’un graphe RDF garantissant que chaque thème y est représenté proportionnellement à son importance dans le graphe initial.

Edge computing is a new paradigm in which data are locally collected, aggregated and preprocessed before being sent to a Cloud platform. Edge devices, typically IoT objects, are characterized by limited computational capabilities, alongside high energy efficiency operations. In smart building or smart city applications, the overall amount of available IoT devices may account for an important computational capacity. Aggregating the idle CPU cycles of several devices would allow performing on-site parallel and distributed computing, while reusing the available resources in the network. Timely and important computational tasks such as video surveillance processing, HPC jobs, or deep neural network training, can be performed with local available resources. This includes local servers or a private, on-site cloud, as opposed to the use of public clouds, thus avoiding security issues and fostering energy efficiency. An ongoing research topic in such a distributed and volatile context is to design novel algorithms for resource provisioning that allow tasks to be distributed over a set of available IoT devices in an efficient manner. This work presents two online, adaptive and robust scheduling techniques, based on the UCB and EXP3 Multi-Armed Bandit algorithms (MABs), for resource management in Cloud-Edge Computing based environments while improving performance and reducing energy consumption. The novelty of our adapted algorithms lies in the fact that we explicitly account for unavailable computing IoT devices resulting in a time-varying available set of arms at each stage. Our numerical results show the high relevance of our approach in reaching optimal provisioning policies in time-varying environments.

Les éléments qui sont présentés dans ce document s’inscrivent dans une stratégie générale de recherche sur ce qu’on pourrait désormais appeler les « humanités numériques de 2ème génération ». Ces dernières sont au croisement des sciences humaines et sociales et de l’intelligence artificielle, avec une attention portée vers l’exploitation de grandes masses de données (ou Big Data en anglais).Dans ce contexte, les données proviennent principalement des travaux de recherche, créés, gérés et relatés (via des plateformes, bibliothèques, réseaux sociaux, des forums, des blogs, des sites, etc.) par des chercheurs, sur toutes sortes de sujets et de thèmes. Les données ont généralement un caractère multiculturel, multilingue et multidisciplinaire. Les phénomènes d’analyse des données et en particulier des humanités dans le contexte du « Big Data », pour les besoins d’exploitation, de compréhension et de renseignement, questionnent les méthodes et démarches traditionnelles de modélisation, de conception, d’implémentation et d’évaluation des systèmes d’information et de décision. L’analyse de ces données est devenue un enjeu majeur. Les institutions de recherche devront investir massivement dans des systèmes d’analyse et de fouilles automatiques des données de la recherche, afin de parvenir à s’adapter aux exigences des chercheurs pour améliorer leurs recherches ; dans le nouveau monde ouvert des données (Open Data) et de l’intelligence artificielle (IA) qui est le Web. De plus, malgré des avancées dans ce domaine, plusieurs études récentes montrent que peu d’institutions, plus particulièrement dans l’espace Francophone, exploitent les données dans leur prise de décision. Ceci est dû à plusieurs problèmes, liés principalement à la nature des solutions existantes qui ne sont pas encore assez mûres, et aussi à leurs coûts de mise en place, encore trop élevés.A titre d’exemple, si on se restreint aux données textuelles, leur traitement pose encore un certain nombre de défis. En effet, la signification (sens) exacte des mots et donc des textes dans leurs contextes est très difficile à détecter et à exploiter automatiquement. Ces problèmes sont encore plus accentués dans le cas des textes scientifiques rédigés souvent avec des styles particuliers, des formules, des abréviations, des sigles, etc., pouvant aller dans certains cas jusqu’à l’intégration d’autres éléments de discours tels que l’ironie, humour, sarcasme, etc.Les solutions numériques et scientifiques, dans ce domaine, doivent donc s’inscrire dans une démarche globale, dont l’objectif est de mettre en place de nouvelles méthodes innovantes et intelligentes pour faire face aux problèmes spécifiques posés par l’analyse sémantique des données textuelles au service de la recherche en humanités et de la prise de décision. Le but est d’apporter des améliorations aux procédures existantes en matière de création, d’analyse et d’exploitation des données pour permettre des facilités et des aides aux chercheurs, d’une part, et d’autre part, permettre des décisions mieux motivées et tirer profit des données massives de la recherche. Cela permettra aux institutions de connaître, à partir des tendances, des indicateurs, etc., comment orienter leurs politiques scientifiques ainsi que les services aux chercheurs et de les adapter en fonction des exigences et des besoins des tutelles et des chercheurs.

As cities continue to grow and evolve, so must their digital aspects as Internet of Things (IoT) applications and devices grow in number, usage, and ability to measure the world around us. Traditional ways of representing information, even virtually, have started to become obsolete, as there is a need to handle both the static and dynamic properties of real life environments. In this paper, we model the dynamic properties of smart buildings, their structural components, and data produced from IoT devices using the NGSI-LD protocol. To facilitate the modeling of existing buildings and further enhance them with IoT aspects, we introduce the IFC2NGSI-LD parser which converts existing IFC-based data models to NGSI-LD. The usefulness of our NGSI-LD models towards creating smart spaces, is demonstrated by executing complex IoT queries using the NGSI-LD API. Such queries can be applied in large-scale buildings, as enabled via the IFC2NGSI-LD parser.

A Finite Discrete-time Dynamical System (DDS) consists of a finite set X , called state space, and a function f, called next-state map (which associates to a state v the state f(v)). DDS are a formal tool for modelling phenomena that appear in Physics, Mathematics, Biology, and, of course, in Computer Science. While the mathematical formalisation and the results that have been found up to nowadays are elegant and meaningful, often they are not very suitable in practice because of their high computational cost. In the literature, it is known that DDS equipped with appropriate sum and product operations form a commutative semiring. This algebraic structure allows us to write polynomial equations in which the coefficients and unknowns are DDS. In particular, if we are interested in some dynamics derived from experimental data, we can write an equation with this as a constant right-hand term and model assumptions about the function f (or its properties) in a polynomial left-hand term. Finding solutions to this equation allow us to better understand the phenomenon and its properties. This approach is interesting but it has important limitations from a computational point of view. Solving a polynomial equation (with several variables) is, in general, undecidable, and even if we focus on the case of hypothesis validation, the computational cost remains high. The idea is then to look for approximations that give relevant information about the solutions of the original equation. It is possible to introduce three abstractions (simpler equations) to identify: the number of states of the variables, the asymptotic behaviour, or the transient behaviour (what happens before the system stabilises). Each one is built from a theoretical and algorithmic point of view to introduce a method to perform hypothesis validation on DDS. In this thesis, it is shown that through algebraic transformations, it is possible to enumerate the solutions of a polynomial equation with a constant term by enumerating a finite number of simpler equations. Finally, the connection between the solution of these simple equations and the cancellation problem known in graph theory is explored. This allowed us to find a linear upper bound on the number of solutions., Un Système Dynamique Fini à temps Discret (SDD) est constitué d'un ensemble fini X, dit espace des états, et d'une fonction f, dite fonction de mise à jour (associant à un état v l'état f(v)). Les SDD sont un outil formel pour modéliser de nombreux phénomènes en physique, en mathématique, en biologie, et, bien sûr en informatique. Si la formalisation mathématique et les résultats qui en découlent sont élégants et parlants, souvent, ces résultats sont peu applicables en pratique à cause de leur coût computationnel élevé. Dans la littérature, il est connu que les SDD équipés d'opérations de somme et de produit appropriées forment un semi-anneau commutatif. Cette structure algébrique nous permet d'écrire des équations polynomiales dans lesquelles les coefficients et les inconnues sont des SDD. En particulier, si nous sommes intéressés par une certaine dynamique dérivée de données expérimentales, nous pouvons écrire une équation avec celle-ci comme terme de droite constant et modéliser des hypothèses sur la fonction f (ou ses propriétés) dans un terme de gauche polynomial. Trouver des solutions à cette équation permet de mieux comprendre le phénomène et ses propriétés. Cette approche est intéressante mais pose des limites computationnelles importantes. En effet, résoudre une équation polynomiale (à plusieurs variables) est, en général, indécidable et même en se concentrant sur le cas de la validation des hypothèses, le coût computationnel reste élevé. L'idée est alors de chercher des approximations donnant des informations pertinentes sur les solutions de l'équation originale. Trois abstractions (équations plus simples) sont introduites afin d'identifier : le nombre d'états des variables, le comportement asymptotique ou le comportement transient (comportement avant que le système se stabilise). Chaque abstraction est construite d'un point de vue théorique et algorithmique dans le but d'introduire une méthode pour effectuer la validation d'hypothèses sur SDD. Dans cette thèse, il est montré qu'au moyen de transformations algébriques, il est possible d'énumérer les solutions d'une équation polynomiale avec un terme droit constant par l'énumération d'un nombre fini d'équations plus simples. Enfin, le lien entre la résolution ces équations simples et le problème de la cancellation connu en théorie des graphes est exploré. Cela a permis de trouver une borne supérieure linéaire sur le nombre de solutions.

The main goal of this note is to provide a First-Order Logic with Betweenness (FOLB) axiomatization of the main classes of graphs occurring in Metric Graph Theory, in analogy to Tarski's axiomatization of Euclidean geometry. We provide such an axiomatization for weakly modular graphs and their principal subclasses (median and modular graphs, bridged graphs, Helly graphs, dual polar graphs, etc), basis graphs of matroids and even $\Delta$-matroids, partial cubes and their subclasses (ample partial cubes, tope graphs of oriented matroids and complexes of oriented matroids, bipartite Pasch and Peano graphs, cellular and hypercellular partial cubes, almost-median graphs, netlike partial cubes), and Gromov hyperbolic graphs. On the other hand, we show that some classes of graphs (including chordal, planar, Eulerian, and dismantlable graphs), closely related with Metric Graph Theory, but defined in a combinatorial or topological way, do not allow such an axiomatization.

In this paper, we address the calibration of a family of magnetic manipulation systems composed of several coils that are moved around by serial robot manipulators. We show in this paper that the calibration of the whole system ultimately results in calibrating the manipulator and coil separately up to an unknown rigid transformation. For calibration of the coil, we propose to use a model that has not been used so far in the literature; a control-oriented model which is su ciently accurate and computes the magnetic field in real time. A protocol for calibrating the magnetic manipulation system using the Nelder-Mead algorithm to estimate the model parameters is presented. Calibration was performed through simulations and validated experimentally on a physical system. It was observed that the root mean square error was reduced by 37% after calibration of the physical system, indicating an improvement in accurately estimating the magnetic model.

International audience; The Christoffel–Darboux kernel, a central object in approximation theory, is shown to have many potential uses in modern data analysis, including applications in machine learning. This is the first book to offer a rapid introduction to the subject, illustrating the surprising effectiveness of a simple tool. Bridging the gap between classical mathematics and current evolving research, the authors present the topic in detail and follow a heuristic, example-based approach, assuming only a basic background in functional analysis, probability and some elementary notions of algebraic geometry. They cover new results in both pure and applied mathematics and introduce techniques that have a wide range of potential impacts on modern quantitative and qualitative science. Comprehensive notes provide historical background, discuss advanced concepts and give detailed bibliographical references. Researchers and graduate students in mathematics, statistics, engineering or economics will find new perspectives on traditional themes, along with challenging open problems.

Automatic detection of relevant groups of nodes in large real-world graphs, i.e. community detection, has applications in many fields and has received a lot of attention in the last twenty years. The most popular method designed to find overlapping communities (where a node can belong to several communities) is perhaps the clique percolation method (CPM). This method formalizes the notion of community as a maximal union of $k$-cliques that can be reached from each other through a series of adjacent $k$-cliques, where two cliques are adjacent if and only if they overlap on $k-1$ nodes. Despite much effort CPM has not been scalable to large graphs for medium values of $k$. Recent work has shown that it is possible to efficiently list all $k$-cliques in very large real-world graphs for medium values of $k$. We build on top of this work and scale up CPM. In cases where this first algorithm faces memory limitations, we propose another algorithm, CPMZ, that provides a solution close to the exact one, using more time but less memory., Comment: 15 pages, 5 figures, 1 table

Estimating the model evidence - or mariginal likelihood of the data - is a notoriously difficult task for finite and infinite mixture models and we reexamine here different Monte Carlo techniques advocated in the recent literature, as well as novel approaches based on Geyer (1994) reverse logistic regression technique, Chib (1995) algorithm, and Sequential Monte Carlo (SMC). Applications are numerous. In particular, testing for the number of components in a finite mixture model or against the fit of a finite mixture model for a given dataset has long been and still is an issue of much interest, albeit yet missing a fully satisfactory resolution. Using a Bayes factor to find the right number of components K in a finite mixture model is known to provide a consistent procedure. We furthermore establish the consistence of the Bayes factor when comparing a parametric family of finite mixtures against the nonparametric 'strongly identifiable' Dirichlet Process Mixture (DPM) model.