Author: "Inria Lille - Nord Europe" / Topic: 0202 electrical engineering, electronic engineering, information engineering - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Inria Lille - Nord Europe"' showing total 1,980 results

Start Over Author "Inria Lille - Nord Europe" Topic 0202 electrical engineering, electronic engineering, information engineering

1,980 results on '"Inria Lille - Nord Europe"'

1. Regular Matching and Inclusion on Compressed Tree Patterns with Constrained Context Variables

Author: Iovka Boneva, Joachim Niehren, Momar Sakho, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), This work was partially supported by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020., Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Matching (statistics), Theoretical computer science, Computational complexity theory, tree patterns, computer.internet_protocol, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, tree automata, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0202 electrical engineering, electronic engineering, information engineering, Time complexity, Computer Science::Databases, computational complexity, Context variable, Xml, Hedge (linguistics), streams, Computer Science Applications, Tree (data structure), Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Inclusion (education), computer, XML, grammar compression, Information Systems
Abstract: International audience; We study the complexity of regular matching and inclusion for compressed tree patterns with context variables subject to regular constraints. Context variables with regular constraints permit to properly generalize on unranked tree patterns with hedge variables. Regular inclusion on unranked tree patterns is relevant to certain query answering on Xml streams with references. We show that regular matching and inclusion with regular constraints can be reduced in polynomial time to the corresponding problem without regular constraints.
Published: 2022

2. Strategic bidding in price coupled regions

Author: Jérôme De Boeck, Luce Brotcorne, Bernard Fortz, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Graphes et Optimisation Mathématique [Bruxelles] (GOM), Université libre de Bruxelles (ULB), This research benefited from the support of the FMJH Program PGMO and from the support of EDF,Thales, Orange., Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: 021103 operations research, 020209 energy, General Mathematics, Bilevel optimization, MILP reformulation, 0211 other engineering and technologies, 02 engineering and technology, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, Extended formulations, 0202 electrical engineering, electronic engineering, information engineering, Strategic bidding, MPEC, Software
Abstract: International audience; With the emerging deregulated electricity markets, a part of the electricity trading takes place in dayahead markets where producers and retailers place bids in order to maximize their profit. We present a price-maker model for strategic bidding from the perspective of a producer in Price Coupled Regions (PCR) considering a capacitated transmission network between local day-ahead markets. The aim for the bidder is to establish a production plan and set its bids taking into consideration the reaction of the market. We consider the problem as deterministic, that is, the bids of the competitors are known in advance. We are facing a bilevel optimization problem where the first level is a Unit Commitment problem, modeled as a Mixed Integer Linear Program (MILP), and the second level models a market equilibrium problem through a Linear Program. The problem is first reformulated as a single level problem. Properties of the optimal spot prices are studied to obtain an extended formulation that is linearized and tightened using new valid inequalities. Several properties of the spot prices allow to reduce significantly the number of binary variables. Two novel heuristics are proposed, the first applicable in PCR, the second for general formulations with Special Ordered Sets (SOS) of type 1. Our computational experiments highlights the risk of a loss for the bidder if some aspects usually not considered in the literature, such as Price Coupled Regions, or an accurate UC problem, are not taken into account. They also show that the reformulation techniques, combined with new valid inequalities, allow to solve much larger instances than the current state-of-the-art. Finally, our experiments also show that the proposed heuristics deliver very high quality solutions in a short computation time.
Published: 2022

3. An exact dynamic programming approach to segmented isotonic regression

Author: Víctor Bucarey, Salvador Pineda, Martine Labbé, Juan M. Morales, Data Analytics Laboratory, Vrije Universiteit Brussel (VUB), Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Département d'informatique [Bruxelles], Université libre de Bruxelles (ULB), Department of Applied Mathematics, Universidad de Málaga [Málaga] = University of Málaga [Málaga], Department of Electrical Engineering, This research has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovationprogramme (grant agreement no. 755705). This work was also supported in part by the Spanish Ministry of Economy, Industry and Competitiveness and the European Regional Development Fund (ERDF) through project ENE2017-83775-P. Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant(s) no PDR T0098.18., European Project: 755705,FlexAnalytics(2018), University of Málaga, Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: G.4, Mathematical optimization, Information Systems and Management, Computer science, 020209 energy, Strategy and Management, 0211 other engineering and technologies, isotonic regression, Context (language use), 02 engineering and technology, Management Science and Operations Research, Data clustering, Electric power system, Informatique de gestion, Análisis de regresión, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Théorie de la décision et des choix collectifs, segmented regression, Inverse optimization, Mathematics - Optimization and Control, Cardinality-constrained shortest path problem, 90C39, 021103 operations research, consumers' price-response, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Bidding, Management, Dynamic programming, Data point, Monotone polygon, Smart grid, Segmented regression, inverse optimization, data clustering, Consumers’ price-response, Optimization and Control (math.OC), Curve fitting, Isotonic regression, Recherche opérationnelle
Abstract: This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on dynamic programming and is built on the basis that said curve-fitting task can be tackled as a shortest-path type of problem. Numerical results on synthetic and realistic data sets reveal that our algorithm is able to provide the globally optimal monotone stepwise curve fit for samples with thousands of data points in less than a few hours. Furthermore, the algorithm gives a certificate on the optimality gap of any incumbent solution it generates. From a practical standpoint, this piece of research is motivated by the roll-out of smart grids and the increasing role played by the small flexible consumption of electricity in the large-scale integration of renewable energy sources into current power systems. Within this context, our algorithm constitutes an useful tool to generate bidding curves for a pool of small flexible consumers to partake in wholesale electricity markets., SCOPUS: ar.j, info:eu-repo/semantics/published
Published: 2021

4. Still No Free Lunches: The Price to Pay for Tighter PAC-Bayes Bounds

Author: Louis Pujol, Benjamin Guedj, University College of London [London] (UCL), Computer science department [University College London] (UCL-CS), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris-Saclay, Department of Computer science [University College of London] (UCL-CS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), ANR-18-CE23-0015,APRIORI,Une Perspective PAC-Bayésienne de l'Apprentissage de Représentations(2018), and ANR-18-CE40-0016,BEAGLE,Apprentissage PAC-bayésien agnostique(2018)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, no free lunch theorems, Science, QC1-999, Yield (finance), Robust statistics, Probably approximately correct learning, General Physics and Astronomy, PAC-Bayes theory, Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), 02 engineering and technology, Astrophysics, 01 natural sciences, Article, Machine Learning (cs.LG), 010104 statistics & probability, Bayes' theorem, statistical learning theory, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, 020204 information systems, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, No free lunch in search and optimization, Applied mathematics, 0101 mathematics, Impossibility, Mathematics, Physics, State (functional analysis), [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH], QB460-466, Statistical learning theory
Abstract: “No free lunch” results state the impossibility of obtaining meaningful bounds on the error of a learning algorithm without prior assumptions and modelling, which is more or less realistic for a given problem. Some models are “expensive” (strong assumptions, such as sub-Gaussian tails), others are “cheap” (simply finite variance). As it is well known, the more you pay, the more you get: in other words, the most expensive models yield the more interesting bounds. Recent advances in robust statistics have investigated procedures to obtain tight bounds while keeping the cost of assumptions minimal. The present paper explores and exhibits what the limits are for obtaining tight probably approximately correct (PAC)-Bayes bounds in a robust setting for cheap models.
Published: 2021
Full Text: View/download PDF

5. Exact Boolean Abstraction of Linear Equation Systems

Author: Emilie Allart, Joachim Niehren, Cristian Versari, BioComputing, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Computer Science, program analysis, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Constraint programming, abstract interpretation, Mathematics, Applied Mathematics, Solution set, 020207 software engineering, systems biology, Function (mathematics), QA75.5-76.95, 16. Peace & justice, Abstract interpretation, Abstraction (mathematics), Algebra, 010201 computation theory & mathematics, Modeling and Simulation, Electronic computers. Computer science, Computer Science::Programming Languages, Rewriting, Linear equation systems, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Boolean data type, Linear equation
Abstract: We study the problem of how to compute the boolean abstraction of the solution set of 1 a linear equation system over the positive reals. We call a linear equation system φ exact for the 2 boolean abstraction if the abstract interpretation of φ over the structure of booleans is equal to the 3 boolean abstraction of the solution set of φ over the positive reals. Abstract interpretation over 4 the booleans is thus complete for the boolean abstraction when restricted to exact linear equation 5 systems, while it is not complete more generally. We present a new rewriting algorithm that makes 6 linear equation systems exact for the boolean abstraction while preserving the solutions over the 7 positive reals. The rewriting algorithm is based on the elementary modes of the linear equation 8 system. The computation of the elementary modes may require exponential time in the worst 9 case, but is often feasible in practice with freely available tools. For exact linear equation systems 10 we can compute the boolean abstraction by finite domain constraint programming. This yields a 11 solution of the initial problem that is often feasible in practice. Our exact rewriting algorithm has 12 two further applications. First, it can be used to compute the sign abstraction of linear equation 13 systems over the reals, as needed for analysing function programs with linear arithmetics. And 14 second it can be applied to compute the difference abstraction of a linear equation system as used 15 in change prediction algorithms for flux networks in systems biology.
Published: 2021

6. On Polynomial Recursive Sequences

Author: Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, Géraud Sénizergues, School of Computing [DePaul] (SOC), DePaul University [Chicago], Max-Planck-Institut für Mathematik (MPI), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Max Planck Institute for Software Systems (MPI-SWS), Warsaw University of Technology [Warsaw], Université de Bordeaux (UB), Michał Pilipczuk: This work is a part of project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 677651., European Project: 677651,H2020,ERC-2015-STG,TOTAL(2016), Artur Czumaj, Anuj Dawar, Emanuela Merelli, and Max Planck Institute for Software Systems
Subjects: FOS: Computer and information sciences, Class (set theory), Polynomial, Recursive sequences, Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Expressive power, Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Mathematics, Discrete mathematics, Sequence, Theory of computation → Models of computation, Extension (predicate logic), 16. Peace & justice, Automaton, Higher-order pushdown automata, Nonlinear system, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, 020201 artificial intelligence & image processing, Weighted automata
Abstract: We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.
Published: 2021

7. PG-Keys: Keys for Property Graphs

Author: Keith W. Hare, George H. L. Fletcher, Sławek Staworko, Michael Schmidt, Leonid Libkin, Jan Hidders, Stefania Dumbrava, Angela Bonifati, Victor E. Lee, Bei Li, Filip Murlak, Juan F. Sequeda, Wim Martens, Ognjen Savkovic, Dominik Tomaszuk, Renzo Angles, Josh Perryman, Universidad de Talaca, Université Claude Bernard Lyon 1 - Faculté des sciences (UCBL FS), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Institut Polytechnique de Paris (IP Paris), Eindhoven University of Technology [Eindhoven] (TU/e), JCC Consulting Inc, Neo4j, Birkbeck College [University of London], TigerGraph, Google LLC, Laboratory for the Foundations of Computer Science [Edinburgh] (LFCS), University of Edinburgh, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL), University of Bayreuth, Uniwersytet Warszawski, Interos Inc., Free University of Bozen-Bolzano, Amazon Web Services [Seattle] (AWS), data.world, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Bialystok, Réponse efficace aux requêtes sous mises à jourEQUUS - ANR-19-CE48-0019AAPG2019 - 2019, Université Claude Bernard Lyon 1 - Faculté des sciences et technologies (UCBL FST), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), École normale supérieure - Paris (ENS Paris), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Focus (computing), Property (philosophy), [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Standardization, Computer science, business.industry, key constraints, 0102 computer and information sciences, 02 engineering and technology, Linked data, 01 natural sciences, 010201 computation theory & mathematics, 020204 information systems, Data integrity, Benchmark (surveying), 0202 electrical engineering, electronic engineering, information engineering, Position (finance), Use case, Software engineering, business, property graphs
Abstract: International audience; We report on a community effort between industry and academia to shape the future of property graph constraints. The standardization for a property graph query language is currently underway through the ISO Graph Query Language (GQL) project. Our position is that this project should pay close attention to schemas and constraints, and should focus next on key constraints. The main purposes of keys are enforcing data integrity and allowing the referencing and identifying of objects. Motivated by use cases from our industry partners, we argue that key constraints should be able to have different modes, which are combinations of basic restriction that require the key to be exclusive, mandatory, and singleton. Moreover, keys should be applicable to nodes, edges, and properties since these all can represent valid real-life entities. Our result is PG-Keys, a flexible and powerful framework for defining key constraints, which fulfills the above goals. PG-Keys is a design by the Linked Data Benchmark Council's Property Graph Schema Working Group, consisting of members from industry, academia, and ISO GQL standards group, intending to bring the best of all worlds to property graph practitioners. PG-Keys aims to guide the evolution of the standardization efforts towards making systems more useful, powerful, and expressive. CCS CONCEPTS • Information systems → Integrity checking; • Theory of computation → Data modeling; Database constraints theory.
Published: 2021

8. Pattern mining‐based pruning strategies in stochastic local searches for scheduling problems

Author: Vincent Clerc, Damien Lamy, Arnaud Laurent, Benjamin Dalmas, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), Institut Henri Fayol (FAYOL-ENSMSE), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), FAYOL-ENSMSE - Département Génie mathématique et industriel, Centre Ingénierie et Santé (CIS-ENSMSE), Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Institut National de Recherche en Informatique et en Automatique (Inria), Département Génie mathématique et industriel (FAYOL-ENSMSE), Ecole Nationale Supérieure des Mines de St Etienne-Institut Henri Fayol, École des Mines, Centre Ingénierie Santé, Saint-Étienne (CIS - MINES), and Institut Henri Fayol-Ecole Nationale Supérieure des Mines de St Etienne
Subjects: Mathematical optimization, Speedup, Computer science, Job shop, Strategy and Management, 0211 other engineering and technologies, Scheduling (production processes), 02 engineering and technology, Management Science and Operations Research, Scheduling Problem, Machine Learning, Local optimum, Knowledge extraction, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Management of Technology and Innovation, 0202 electrical engineering, electronic engineering, information engineering, Local search (optimization), Resource Constrained Project Scheduling Problem, Pruning (decision trees), Business and International Management, 021103 operations research, Job shop scheduling, business.industry, Job-shop, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Pattern Mining, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Stochastic Local Search, Computer Science Applications, job‐shop, 020201 artificial intelligence & image processing, business
Abstract: International audience; Scheduling problems are a subclass of combinatorial problems consisting of a set of tasks/activities/jobs to be processed by a set of resources usually to minimize a time criterion. Some optimization methods used to solve these problems are hybridized with knowledge discovery techniques to extract information during the optimization process and enhance it. However, most of these hybrid techniques are custom‐designed and lack generalization. In this paper, a module for knowledge extraction in Stochastic Local Searches is designed, aiming to be problem independent and plugged into optimization methods that relies on multiple Stochastic Local Search replications. The objective is to prune parts of the search space for which the exploration is likely to lead to poor solutions. This is performed through the extraction of high‐quality patterns occurring in locally optimal solutions. Benchmarked on two well‐known scheduling problems, the Job‐shop Problem and the Resource Constrained Project Scheduling Problem, the results show both a speed up in the convergence and the reaching of better local optima solutions.
Published: 2021

9. Multiview Boosting by Controlling the Diversity and the Accuracy of View-specific Voters

Author: Emilie Morvant, Massih-Reza Amini, Pascal Germain, Anil Goyal, Analyse de données, Modélisation et Apprentissage automatique [Grenoble] (AMA ), Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Région Rhone-Alpes, ANR-15-CE23-0026,LIVES,Apprendre avec des vues interactionnelles(2015), CNRS, Université de Lille, Laboratoire Paul Painlevé [LPP], Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, 0209 industrial biotechnology, Boosting (machine learning), Computer science, Cognitive Neuroscience, Machine Learning (stat.ML), 02 engineering and technology, Machine learning, computer.software_genre, Machine Learning (cs.LG), Boosting, 020901 industrial engineering & automation, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Artificial Intelligence, 0202 electrical engineering, electronic engineering, information engineering, Multiview Learning, business.industry, PAC-Bayes, Computer Science Applications, 020201 artificial intelligence & image processing, Artificial intelligence, business, computer
Abstract: International audience; In this paper we propose a boosting based multiview learning algorithm, referred to as PB-MVBoost, which iteratively learns i) weights over view-specific voters capturing view-specific information; and ii) weights over views by optimizing a PAC-Bayes multiview C-Bound that takes into account the accuracy of view-specific classifiers and the diversity between the views. We derive a generalization bound for this strategy following the PAC-Bayes theory which is a suitable tool to deal with models expressed as weighted combination over a set of voters. Different experiments on three publicly available datasets show the efficiency of the proposed approach with respect to state-of-art models.
Published: 2019

10. Real-Time monophonic and polyphonic audio classification from power spectra

Author: Maxime Baelde, Raphaël Greff, Christophe Biernacki, A-Volute [Roubaix], MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, CNRS, Université de Lille, Laboratoire Paul Painlevé - UMR 8524, and Laboratoire Paul Painlevé [LPP]
Subjects: Computer science, Feature extraction, 02 engineering and technology, 01 natural sciences, Real-time, Audio classification, Generative model, Polyphonic, Nonparametric estimation, Monophonic, Machine learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Artificial Intelligence, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Maximum a posteriori estimation, Polyphony, 010306 general physics, business.industry, Pattern recognition, Kernel (statistics), Classification rule, Signal Processing, Benchmark (computing), 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Artificial intelligence, business, Software
Abstract: International audience; This work addresses the recurring challenge of real-time monophonic and polyphonic audio source classification. The whole normalized power spectrum (NPS) is directly involved in the proposed process, avoiding complex and hazardous traditional feature extraction. It is also a natural candidate for polyphonic events thanks to its additive property in such cases. The classification task is performed through a nonparametric kernel-based generative modeling of the power spectrum. Advantage of this model is twofold: it is almost hypothesis free and it allows to straightforwardly obtain the maximum a posteriori classification rule of online signals. Moreover it makes use of the monophonic dataset to build the polyphonic one. Then, to reach the real-time target, the complexity of the method can be tuned by using a standard hierarchical clustering preprocessing of the prototypes, revealing a particularly efficient computation time and classification accuracy trade-off. The proposed method, called RARE (for Real-time Audio Recognition Engine) reveals encouraging results both in monophonic and polyphonic classification tasks on benchmark and owned datasets, including also the targeted real-time situation. In particular, this method benefits from several advantages compared to the state-of-the-art methods including a reduced training time, no feature extraction, the ability to control the computation - accuracy trade-off and no training on already mixed sounds for polyphonic classification.
Published: 2019

11. Determinization and Minimization of Automata for Nested Words Revisited

Author: Joachim Niehren, Momar Sakho, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 0209 industrial biotechnology, Nested word, lcsh:T55.4-60.8, Computer science, Nested Words, Logical Queries, Tree Automata, 02 engineering and technology, lcsh:QA75.5-76.95, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, lcsh:Industrial engineering. Management engineering, XPath, Regular expression, Time complexity, Numerical Analysis, Regular Expressions, Hedges, Tree (graph theory), Automaton, Nondeterministic algorithm, Computational Mathematics, Computational Theory and Mathematics, Streams, Benchmark (computing), 020201 artificial intelligence & image processing, lcsh:Electronic computers. Computer science, Algorithm, Computer Science::Formal Languages and Automata Theory, Word (computer architecture)
Abstract: International audience; We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs). The determinization of these NWAs, however, fails to produce reasonably small automata. In the best case, huge deterministic NWAs are produced after few hours, even for relatively small NREs of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata SHAs) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize SHAs, yielding reasonably small deterministic automata for the NREs from the XPath benchmark. The size of deterministic SHAs automata can be reduced further by a novel minimization algorithm for a subclass of SHAs. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between NWAs and SHAs further. Clearly, deterministic SHAs can be compiled to deterministic NWAs in linear time, and conversely, NWA_s can be compiled to nondeterministic SHAs in polynomial time. Therefore, we can use SHAs as intermediates for determinizing NWAs, while avoiding the huge size increase with the usual determinization algorithm for NWAs. Notably, the NWAs obtained from the SHAs perform bottom-up and left-to-right computations only, but no top-down computations. This NWA-behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between SHAs and single-entry NWAs. In particular, it turns out that the usual determinization algorithm for NWAs behaves well for single-entry NWAs, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry NWAs enjoys unique minimization. The subclass of deterministic SHAs to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed SHAs we propose schema-based cleaning and symbolic representations based on apply-else rules, that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark.
Published: 2021

12. Forecasting elections results via the voter model with stubborn nodes

Author: Shi Zhou, Benjamin Guedj, Antoine Vendeville, Department of Computer science [University College of London] (UCL-CS), University College of London [London] (UCL), The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Computer science department [University College London] (UCL-CS), Laboratoire Paul Painlevé - UMR 8524 (LPP), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, social networks, Computer Networks and Communications, Mean absolute error, Voter model, Model parameters, 02 engineering and technology, Elections, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Machine Learning (cs.LG), voter model, Politics, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], 020204 information systems, Side product, 0202 electrical engineering, electronic engineering, information engineering, Econometrics, Economics, Popular vote, Social and Information Networks (cs.SI), Multidisciplinary, Markov chain, Markov chains, lcsh:T57-57.97, Computer Science - Social and Information Networks, 16. Peace & justice, Computational Mathematics, Work (electrical), lcsh:Applied mathematics. Quantitative methods, 020201 artificial intelligence & image processing, opinion dynamics
Abstract: 15 pages; International audience; We explore a method to influence or even control the diversity of opinions within a polarised social group. We leverage the voter model in which users hold binary opinions and repeatedly update their beliefs based on others they connect with. Stubborn agents who never change their minds (\zealots") are also disseminated through the network, which is modelled by a connected graph. Building on earlier results, we provide a closed-form expression for the average opinion of the group at equilibrium. This leads us to a strategy to inject zealots into a polarised network in order to shift the average opinion towards any target value. We account for the possible presence of a backfire effect, which may lead the group to react negatively and reinforce its level of polarisation in response. Our results are supported by numerical experiments on synthetic data.
Published: 2021

13. Clustering spatial functional data

Author: Vandewalle, Vincent, Preda, Cristian, Dabo-Niang, Sophie, MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), J. Mateu and R. Giraldo, Université de Lille, Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Dabo-Niang, Sophie, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, and Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)
Subjects: [STAT]Statistics [stat], 010104 statistics & probability, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 02 engineering and technology, 0101 mathematics, 01 natural sciences, [MATH.MATH-ST] Mathematics [math]/Statistics [math.ST], [STAT.ME]Statistics [stat]/Methodology [stat.ME], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021

14. A Fokker-Planck approach to the study of robustness in gene expression

Author: Pierre Degond, Sepideh Mirrahimi, Maxime Herda, Department of Mathematics [Imperial College London], Imperial College London, Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), PD acknowledges support by the Engineering and Physical Sciences Research Council (EPSRC) under grants no. EP/M006883/1 and EP/N014529/1, by the Royal Society and the Wolfson Foundation through a Royal Society Wolfson Research Merit Award no. WM130048 and by the National Science Foundation (NSF) under grant no. RNMS11-07444 (KI-Net). PD is on leave from CNRS, Institut de Mathématiques de Toulouse, France. MH acknowledges support by the Labex CEMPI (ANR-11-LABX-0007-01). SM acknowledges support by the CNRS–Royal Society exchange projects 'CODYN' and 'Segregation models in social sciences' and the Chaire Modélisation Mathématique et Biodiversité of Véolia Environment - Ecole Polytechnique - Museum National d’Histoire Naturelle - Fondation X., ANR-11-LABX-0007,CEMPI,Centre Européen pour les Mathématiques, la Physique et leurs Interactions(2011), Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), PD acknowledges support by the Engineering and Physical Sciences Research Council (EPSRC) under grants no. EP/M006883/1 and EP/N014529/1, by the Royal Society and the Wolfson Foundation through a Royal Society Wolfson Research Merit Award no. WM130048 and by the National Science Foundation (NSF) under grant no. RNMS11-07444 (KI-Net). PD is on leave from CNRS, Institut de Math\'ematiques de Toulouse, France. MH acknowledges support by the Labex CEMPI (ANR-11-LABX-0007-01). SM acknowledges support by the CNRS–Royal Society exchange projects ``CODYN' and ``Segregation models in social sciences' and the Chaire Mod\'elisation Math\'ematique et Biodiversit\'e of V\'eolia Environment - \'Ecole Polytechnique - Museum National d’Histoire Naturelle - Fondation X., The Royal Society, Engineering & Physical Science Research Council (EPSRC), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Inria Lille - Nord Europe, Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)
Subjects: MICRORNAS, 0904 Chemical Engineering, 02 engineering and technology, Fokker-Planck Equation, 0903 Biomedical Engineering, Joint probability distribution, 0102 Applied Mathematics, Gene expression, 0202 electrical engineering, electronic engineering, information engineering, Gene Regulatory Networks, Statistical physics, inverse gamma distributions, microRNA, Applied Mathematics, 05 social sciences, General Medicine, Numerical Analysis (math.NA), Quantitative Biology::Genomics, Computational Mathematics, Modeling and Simulation, INEQUALITIES, 020201 artificial intelligence & image processing, Fokker–Planck equation, Marginal distribution, General Agricultural and Biological Sciences, Life Sciences & Biomedicine, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Biotechnology, Analysis of PDEs (math.AP), Micro RNA, math.NA, Bioinformatics, [SDV.BC]Life Sciences [q-bio]/Cellular Biology, Mathematics - Analysis of PDEs, 0502 economics and business, Gene expression level, QA1-939, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Mathematics - Numerical Analysis, cs.NA, math.AP, Science & Technology, Robustness (evolution), [SDV.BBM.BM]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Molecular biology, Inverse Gamma distribution, Systems modeling, BRUNN-MINKOWSKI, 35Q84, 92C40, 92D20, 35Q92, 65M08, Mathematical & Computational Biology, Fokker-Planck equations, TP248.13-248.65, Mathematics, 050203 business & management
Abstract: We study several Fokker-Planck equations arising from a stochastic chemical kinetic system modeling a gene regulatory network in biology. The densities solving the Fokker-Planck equations describe the joint distribution of the messenger RNA and micro RNA content in a cell. We provide theoretical and numerical evidences that the robustness of the gene expression is increased in the presence of micro RNA. At the mathematical level, increased robustness shows in a smaller coefficient of variation of the marginal density of the messenger RNA in the presence of micro RNA. These results follow from explicit formulas for solutions. Moreover, thanks to dimensional analyses and numerical simulations we provide qualitative insight into the role of each parameter in the model. As the increase of gene expression level comes from the underlying stochasticity in the models, we eventually discuss the choice of noise in our models and its influence on our results., Comment: Minor revisions
Published: 2020

15. Consistency and Certain Answers in Relational to RDF Data Exchange with Shape Constraints

Author: Iovka Boneva, Jose Lozano, Sławek Staworko, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), ANR-15-CE39-0009,DataCert,Spécification intensive en Coq d'intégration de données orientée sécurité(2015), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 050101 languages & linguistics, Class (set theory), Theoretical computer science, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Computer science, Relational database, Computation, 05 social sciences, 02 engineering and technology, computer.file_format, Constructive, Consistency (database systems), Data exchange, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Regular expression, RDF, computer, Computer Science::Databases
Abstract: International audience; We investigate the data exchange from relational databases to RDF graphs inspired by R2RML with the addition of target shape schemas. We study the problems of consistency i.e., checking that every source instance admits a solution, and certain query answering i.e., finding answerspresent in every solution. We identify the class of constructive relational to RDF data exchange that uses IRI constructors and full tgds (with no existential variables) in its source to target dependencies. We show that the consistency problem is coNP-complete. We introduce the notion of universal simulation solution that allows to compute certain query answers to any class of queries that is robust under simulation. One such class are nested regular expressions (NREs) that are forward i.e., do not use the inverse operation. Using universal simulation solution renders tractable the computation of certain answers to forward NREs (data-complexity). Finally, we present a number of results that show that relaxing the restrictions of the proposed framework leads to an increase in complexity.
Published: 2020

16. Connecting Knowledge Compilation Classes and Width Parameters

Author: Mikaël Monet, Pierre Senellart, Antoine Amarilli, Florent Capelli, Data, Intelligence and Graphs (DIG), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Value from Data (VALDA ), Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)
Subjects: FOS: Computer and information sciences, Boolean circuit, Treewidth, H.2, Pathwidth, 0102 computer and information sciences, 02 engineering and technology, Arity, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Computer Science - Databases, 020204 information systems, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Knowledge compilation, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Boolean circuits, Mathematics, Discrete mathematics, Degree (graph theory), Databases (cs.DB), OBDDs, d-DNNFs, Monotone polygon, Computational Theory and Mathematics, 010201 computation theory & mathematics
Abstract: The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that bounded-treewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs)., 46 pages. Extended version of arXiv:1709.06188. Up to the stylesheet, page/environment numbering, minor formatting, and publisher-induced changes, this is the exact content of the paper in Theory of Computing Systems . The difference in the titles (missing "and") is an error introduced by the publisher
Published: 2020

17. Non-linear aggregation of filters to improve image denoising

Author: Benjamin Guedj, Juliette Rengot, Department of Computer science [University College of London] (UCL-CS), University College of London [London] (UCL), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), École des Ponts ParisTech (ENPC), Guedj, Benjamin, Computer science department [University College London] (UCL-CS), Laboratoire Paul Painlevé - UMR 8524 (LPP), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Santé publique : épidémiologie et qualité des soins-EA 2694 (CERIM), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, CNRS, Université de Lille, and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies
Subjects: Scheme (programming language), FOS: Computer and information sciences, Computer Science - Machine Learning, Statistical aggregation, Ensemble methods, Image denoising, Collaborative filtering, Computer science, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, Machine Learning (stat.ML), 02 engineering and technology, 010501 environmental sciences, 01 natural sciences, Machine Learning (cs.LG), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, 0105 earth and related environmental sciences, computer.programming_language, [STAT.ME] Statistics [stat]/Methodology [stat.ME], Pixel, Aggregate (data warehouse), Image and Video Processing (eess.IV), [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], Electrical Engineering and Systems Science - Image and Video Processing, Ensemble learning, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Nonlinear system, [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Metric (mathematics), 020201 artificial intelligence & image processing, computer, Algorithm, [STAT.ME]Statistics [stat]/Methodology [stat.ME]
Abstract: We introduce a novel aggregation method to efficiently perform image denoising. Preliminary filters are aggregated in a non-linear fashion, using a new metric of pixel proximity based on how the pool of filters reaches a consensus. We provide a theoretical bound to support our aggregation scheme, its numerical performance is illustrated and we show that the aggregate significantly outperforms each of the preliminary filters., Comment: To appear at Computing Conference 2020
Published: 2020

18. Nested Regular Expressions can be Compiled to Small Deterministic Nested Word Automata

Author: Iovka Boneva, Momar Sakho, Joachim Niehren, Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data [LINKS], Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), and Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Nested word, Computer science, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 0102 computer and information sciences, 02 engineering and technology, Hedge (linguistics), 01 natural sciences, Automaton, Nondeterministic algorithm, 010201 computation theory & mathematics, Path (graph theory), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Regular expression, MESH: Nested Words, Streams, Automata, XML, Computer Science::Databases, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; We study the problem of whether regular expressions for nested words can be compiled to small deterministic nested word au-tomata (NWAs). In theory, we obtain a positive answer for small deter-ministic regular expressions for nested words. In practice of navigational path queries, nondeterministic NWAs are obtained for which NWA de-terminization explodes. We show that practical good solutions can be obtained by using stepwise hedge automata as intermediates.
Published: 2020

19. Multi-Partitions Subspace Clustering

Author: Vincent Vandewalle, MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)
Subjects: Computer science, General Mathematics, 02 engineering and technology, Latent variable, 01 natural sciences, 010104 statistics & probability, Expectation–maximization algorithm, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), 0101 mathematics, Cluster analysis, factorial discriminant analysis, EM algorithm, Engineering (miscellaneous), Class variable, mixture model, business.industry, lcsh:Mathematics, Probabilistic logic, Pattern recognition, Mixture model, lcsh:QA1-939, Linear subspace, [STAT]Statistics [stat], ComputingMethodologies_PATTERNRECOGNITION, 020201 artificial intelligence & image processing, Artificial intelligence, business, Subspace topology, clustering
Abstract: In model based clustering, it is often supposed that only one clustering latent variable explains the heterogeneity of the whole dataset. However, in many cases several latent variables could explain the heterogeneity of the data at hand. Finding such class variables could result in a richer interpretation of the data. In the continuous data setting, a multi-partition model based clustering is proposed. It assumes the existence of several latent clustering variables, each one explaining the heterogeneity of the data with respect to some clustering subspace. It allows to simultaneously find the multi-partitions and the related subspaces. Parameters of the model are estimated through an EM algorithm relying on a probabilistic reinterpretation of the factorial discriminant analysis. A model choice strategy relying on the BIC criterion is proposed to select to number of subspaces and the number of clusters by subspace. The obtained results are thus several projections of the data, each one conveying its own clustering of the data. Model&rsquo, s behavior is illustrated on simulated and real data.
Published: 2020
Full Text: View/download PDF

20. Textual data summarization using the Self-Organized Co-Clustering model

Author: Christophe Biernacki, Julien Jacques, Margot Selosse, Entrepôts, Représentation et Ingénierie des Connaissances (ERIC), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Lumière - Lyon 2 (UL2), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Santé publique : épidémiologie et qualité des soins-EA 2694 (CERIM), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), and Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies
Subjects: Computer science, Document-term matrix, Inference, 02 engineering and technology, computer.software_genre, 01 natural sciences, Biclustering, document-term matrix, Latent Block Model * Corresponding author, Artificial Intelligence, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, 010306 general physics, Cluster analysis, coclustering, Interpretability, Latent Block Model, Model selection, Probabilistic logic, Automatic summarization, Signal Processing, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Data mining, computer, Software
Abstract: International audience; Recently, different studies have demonstrated the use of co-clustering, a data mining technique which simultaneously produces row-clusters of observations and column-clusters of features. The present work introduces a novel co-clustering model to easily summarize textual data in a document-term format. In addition to highlighting homogeneous co-clusters as other existing algorithms do we also distinguish noisy co-clusters from significant co-clusters, which is particularly useful for sparse document-term matrices. Furthermore, our model proposes a structure among the significant co-clusters, thus providing improved interpretability to users. The approach proposed contends with state-of-the-art methods for document and term clustering and offers user-friendly results. The model relies on the Poisson distribution and on a constrained version of the Latent Block Model, which is a probabilistic approach for co-clustering. A Stochastic Expectation-Maximization algorithm is proposed to run the model’s inference as well as a model selection criterion to choose the number of coclusters. Both simulated and real data sets illustrate the eciency of this model by its ability to easily identify relevant co-clusters.
Published: 2020

21. Multi-kernel unmixing and super-resolution using the Modified Matrix Pencil method

Author: Stéphane Chrétien, Hemant Tyagi, National Physical Laboratory (NPL), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Hemant Tyagi’s work was supported by EPSRC grant EP/N510129/1., Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Santé publique : épidémiologie et qualité des soins-EA 2694 (CERIM), and Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies
Subjects: FOS: Computer and information sciences, Point spread function, sampling, Computer Science - Information Theory, General Mathematics, Star (game theory), super-resolution, 02 engineering and technology, unmixing kernels, 01 natural sciences, Combinatorics, symbols.namesake, signal recovery Mathematics, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Numerical Analysis, 0101 mathematics, Matrix Pencil, mixture models, [MATH]Mathematics [math], approximation, Mathematics, Group (mathematics), Information Theory (cs.IT), Applied Mathematics, 010102 general mathematics, Order (ring theory), 020206 networking & telecommunications, Numerical Analysis (math.NA), Function (mathematics), Fourier transform, Fourier analysis, Matrix pencil, symbols, Analysis
Abstract: Consider $L$ groups of point sources or spike trains, with the $l^{\text{th}}$ group represented by $x_l(t)$. For a function $g:\mathbb{R} \rightarrow \mathbb{R}$, let $g_l(t) = g(t/��_l)$ denote a point spread function with scale $��_l > 0$, and with $��_1 < \cdots < ��_L$. With $y(t) = \sum_{l=1}^{L} (g_l \star x_l)(t)$, our goal is to recover the source parameters given samples of $y$, or given the Fourier samples of $y$. This problem is a generalization of the usual super-resolution setup wherein $L = 1$; we call this the multi-kernel unmixing super-resolution problem. Assuming access to Fourier samples of $y$, we derive an algorithm for this problem for estimating the source parameters of each group, along with precise non-asymptotic guarantees. Our approach involves estimating the group parameters sequentially in the order of increasing scale parameters, i.e., from group $1$ to $L$. In particular, the estimation process at stage $1 \leq l \leq L$ involves (i) carefully sampling the tail of the Fourier transform of $y$, (ii) a \emph{deflation} step wherein we subtract the contribution of the groups processed thus far from the obtained Fourier samples, and (iii) applying Moitra's modified Matrix Pencil method on a deconvolved version of the samples in (ii)., 50 pages, 10 figures, made notational changes and corrected typos after reviewer feedback, to appear in Journal of Fourier Analysis and Applications
Published: 2020

22. ShExML: improving the usability of heterogeneous data mapping languages for first-time users

Author: Iovka Boneva, Juan Manuel Cueva Lovelle, Sławek Staworko, Herminio García-González, José Emilio Labra Gayo, Universidad de Oviedo [Oviedo], Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), This work has been funded by the Principality of Asturias through the Severo Ochoa call (grant BP17-29), by the Ministry of Economy, Industry and Competitiveness under the call of ‘‘Programa Estatal de I+D+i Orientada a los Retos de la Sociedad’’ (project TIN2017-88877-R), the CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015–2020, and the ANR project DataCert ANR-15-CE39-0009. There was no additional external funding received for this study. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript., ANR-15-CE39-0009,DataCert,Spécification intensive en Coq d'intégration de données orientée sécurité(2015), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Computer Science, Computer science, Usability, 02 engineering and technology, computer.software_genre, 01 natural sciences, Field (computer science), World Wide Web and Web Science, SPARQL-Generate, Artificial Intelligence, Human–computer interaction, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Representation (mathematics), [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], business.industry, ShExML, 010401 analytical chemistry, 0104 chemical sciences, Data mapping, Human-Computer Interaction, YARRRML, Programming Languages, Data integration, business, computer
Abstract: Integration of heterogeneous data sources in a single representation is an active field with many different tools and techniques. In the case of text-based approaches—those that base the definition of the mappings and the integration on a DSL—there is a lack of usability studies. In this work we have conducted a usability experiment (n = 17) on three different languages: ShExML (our own language), YARRRML and SPARQL-Generate. Results show that ShExML users tend to perform better than those of YARRRML and SPARQL-Generate. This study sheds light on usability aspects of these languages design and remarks some aspects of improvement.
Published: 2020

23. PAC-Bayes and Domain Adaptation

Author: Emilie Morvant, Amaury Habrard, François Laviolette, Pascal Germain, MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Department of Computer Science and Software Engineering [Québec], Université Laval [Québec] (ULaval), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), NSERC discovery grant 262067, ANR-15-CE23-0026,LIVES,Apprendre avec des vues interactionnelles(2015), European Project: 308036,EC:FP7:ERC,ERC-2012-StG_20111012,L3VISU(2013), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), CNRS, and Université de Lille
Subjects: FOS: Computer and information sciences, PAC-Bayesian Theory, Domain Adaptation, 0209 industrial biotechnology, Majority rule, Generalization, Cognitive Neuroscience, Machine Learning (stat.ML), 02 engineering and technology, Measure (mathematics), Upper and lower bounds, Computer Science Applications, Bayes' theorem, 020901 industrial engineering & automation, Perspective (geometry), Distribution (mathematics), [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Artificial Intelligence, Specialization (logic), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Algorithm, Mathematics
Abstract: We provide two main contributions in PAC-Bayesian theory for domain adaptation where the objective is to learn, from a source distribution, a well-performing majority vote on a different, but related, target distribution. Firstly, we propose an improvement of the previous approach we proposed in Germain et al. (2013), which relies on a novel distribution pseudodistance based on a disagreement averaging, allowing us to derive a new tighter domain adaptation bound for the target risk. While this bound stands in the spirit of common domain adaptation works, we derive a second bound (introduced in Germain et al., 2016) that brings a new perspective on domain adaptation by deriving an upper bound on the target risk where the distributions' divergence-expressed as a ratio-controls the trade-off between a source error measure and the target voters' disagreement. We discuss and compare both results, from which we obtain PAC-Bayesian generalization bounds. Furthermore, from the PAC-Bayesian specialization to linear classifiers, we infer two learning algorithms, and we evaluate them on real data., Neurocomputing, Elsevier, 2019. arXiv admin note: substantial text overlap with arXiv:1503.06944
Published: 2020

24. Decentralized Learning with Budgeted Network Load Using Gaussian Copulas and Classifier Ensembles

Author: Olivier Colot, Benjamin Guedj, Mahmoud Albardan, John Klein, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS), MOdel for Data Analysis and Learning (MODAL), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), University College of London [London] (UCL), Department of Computer science [University College of London] (UCL-CS), CNRS, Centrale Lille, Université de Lille, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL], Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189, Laboratoire Paul Painlevé [LPP], Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, and Computer science department [University College London] (UCL-CS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, classifers ensemble, copulas, Computer Science - Artificial Intelligence, Decentralized learning, Computer science, Gaussian, Machine Learning (stat.ML), 02 engineering and technology, 010501 environmental sciences, Machine learning, computer.software_genre, 01 natural sciences, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], symbols.namesake, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Robustness (computer science), 0202 electrical engineering, electronic engineering, information engineering, Classifier ensemble, Copulas, Classifers ensemble, 0105 earth and related environmental sciences, computer.programming_language, business.industry, Statistical model, Python (programming language), Ensemble learning, Artificial Intelligence (cs.AI), machine learning, classifier ensemble, Computer Science - Distributed, Parallel, and Cluster Computing, symbols, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer, Classifier (UML), [PHYS.PHYS.PHYS-DATA-AN]Physics [physics]/Physics [physics]/Data Analysis, Statistics and Probability [physics.data-an]
Abstract: International audience; We examine a network of learners which address the same classification task but must learn from different data sets. The learners can share a limited portion of their data sets so as to preserve the network load. We introduce DELCO (standing for Decentralized Ensemble Learning with COpulas), a new approach in which the shared data and the trained models are sent to a central machine that allows to build an ensemble of classifiers. The proposed method aggregates the base classifiers using a probabilistic model relying on Gaussian copulas. Experiments on logistic regressor ensembles demonstrate competing accuracy and increased robustness as compared to gold standard approaches. A companion python implementation can be downloaded at https://github.com/john-klein/DELCO
Published: 2020

25. Recommendations for Evolving Relational Databases

Author: Stéphane Ducasse, Anne Etien, Julien Delplanque, Nicolas Anquetil, Analyses and Languages Constructs for Object-Oriented Application Evolution (RMOD), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille, Contributions of the Data parallelism to real time (DART), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: SQL, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Information retrieval, Impact analysis, Plain text, Computer science, Relational database, Database schema, InformationSystems_DATABASEMANAGEMENT, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 02 engineering and technology, computer.file_format, computer.software_genre, Article, Relational database management system, 020204 information systems, Schema (psychology), 0202 electrical engineering, electronic engineering, information engineering, Information system, Stored procedure, Semi-automatic evolution, computer, Meta-model, computer.programming_language
Abstract: International audience; Relational databases play a central role in many information systems. Their schemas contain structural and behavioral entity descriptions. Databases must continuously be adapted to new requirements of a world in constant change while: (1) relational database management systems (RDBMS) do not allow inconsistencies in the schema; (2) stored procedure bodies are not meta-described in RDBMS such as PostgreSQL that consider their bodies as plain text. As a consequence , evaluating the impact of an evolution of the database schema is cumbersome , being essentially manual. We present a semi-automatic approach based on recommendations that can be compiled into a SQL patch fulfilling RDBMS constraints. To support recommendations, we designed a meta-model for relational databases easing computation of change impact. We performed an experiment to validate the approach by reproducing a real evolution on a database. The results of our experiment show that our approach can set the database in the same state as the one produced by the manual evolution in 75% less time.
Published: 2020

26. Data structures based on k-mers for querying large collections of sequencing datasets

Author: Mikaël Salson, Christina Boucher, Paul Medvedev, Rayan Chikhi, Camille Marchet, Simon J. Puglisi, Bioinformatics and Sequence Analysis (BONSAI), Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Department of Computer and Information Science and Engineering [Gainesville] (UF|CISE), University of Florida [Gainesville] (UF), Helsinki Institute for Information Technology (HIIT), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, University of Pennsylvania, Centre de Bioinformatique, Biostatistique et Biologie Intégrative (C3BI), Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Aalto University-University of Helsinki, University of Pennsylvania [Philadelphia], and Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS)
Subjects: European Nucleotide Archive, Information retrieval, Computer science, 020204 information systems, 0206 medical engineering, 0202 electrical engineering, electronic engineering, information engineering, Petabyte, 02 engineering and technology, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Data structure, 020602 bioinformatics
Abstract: High-throughput sequencing datasets are usually deposited in public repositories, e.g. the European Nucleotide Archive, to ensure reproducibility. As the amount of data has reached petabyte scale, repositories do not allow to perform online sequence searches; yet such a feature would be highly useful to investigators. Towards this goal, in the last few years several computational approaches have been introduced to index and query large collections of datasets. Here we propose an accessible survey of these approaches, which are generally based on representing datasets as sets of k-mers. We review their properties, introduce a classification, and present their general intuition. We summarize their performance and highlight their current strengths and limitations.
Published: 2019

27. Comparison of formulations for the two-level uncapacitated facility location problem with single assignment constraints

Author: Bernard Gendron, Frédéric Semet, Paul-Virak Khuong, Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT), École Polytechnique de Montréal (EPM)-Université de Montréal (UdeM)-HEC Montréal (HEC Montréal), Université de Montréal (UdeM), AppNexus, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL)
Subjects: Mathematical optimization, Relaxations, 021103 operations research, General Computer Science, 0211 other engineering and technologies, Formulations, Mixed-integer programming, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 02 engineering and technology, Extension (predicate logic), Management Science and Operations Research, Facility location problem, Two-level uncapacitated facility location, Modeling and Simulation, 0202 electrical engineering, electronic engineering, information engineering, Programming paradigm, [INFO]Computer Science [cs], 020201 artificial intelligence & image processing, Relaxation (approximation), Integer programming, Single assignment, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.6: Optimization/G.1.6.4: Integer programming, Mathematics
Abstract: International audience; We consider the two-level uncapacitated facility location problem with single assignment constraints (TUFLP-S), an extension of the uncapacitated facility location problem. We present six mixed-integer programming models for the TUFLP-S based on reformulation techniques and on the relaxation of the integrality of some of the variables associated with location decisions. We compare the models by carrying out extensive computational experiments on large, hard, artificial instances, as well as on instances derived from an industrial application in freight transportation.
Published: 2017

28. Differentiable PAC–Bayes Objectives with Partially Aggregated Neural Networks

Author: Felix Biggs, Benjamin Guedj, Computer science department [University College London] (UCL-CS), University College of London [London] (UCL), The Inria London Programme (Inria-London), University College of London [London] (UCL)-University College of London [London] (UCL)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria-CWI (Inria-CWI), Centrum Wiskunde & Informatica (CWI)-Institut National de Recherche en Informatique et en Automatique (Inria), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Department of Computer science [University College of London] (UCL-CS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), ANR-18-CE23-0015,APRIORI,Une Perspective PAC-Bayésienne de l'Apprentissage de Représentations(2018), and ANR-18-CE40-0016,BEAGLE,Apprentissage PAC-bayésien agnostique(2018)
Subjects: FOS: Computer and information sciences, Scheme (programming language), Computer Science - Machine Learning, Mathematical optimization, Computer science, Science, QC1-999, General Physics and Astronomy, Machine Learning (stat.ML), 02 engineering and technology, Astrophysics, Article, Machine Learning (cs.LG), Bayes' theorem, statistical learning theory, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Differentiable function, Stochastic neural network, computer.programming_language, Artificial neural network, business.industry, Physics, Deep learning, deep learning, Estimator, PAC–Bayes theory, QB460-466, ComputingMethodologies_PATTERNRECOGNITION, Statistical learning theory, 020201 artificial intelligence & image processing, Artificial intelligence, business, computer
Abstract: We make two related contributions motivated by the challenge of training stochastic neural networks, particularly in a PAC–Bayesian setting: (1) we show how averaging over an ensemble of stochastic neural networks enables a new class of partially-aggregated estimators, proving that these lead to unbiased lower-variance output and gradient estimators, (2) we reformulate a PAC–Bayesian bound for signed-output networks to derive in combination with the above a directly optimisable, differentiable objective and a generalisation guarantee, without using a surrogate loss or loosening the bound. We show empirically that this leads to competitive generalisation guarantees and compares favourably to other methods for training such networks. Finally, we note that the above leads to a simpler PAC–Bayesian training scheme for sign-activation networks than previous work.
Published: 2021

29. Models for the piecewise linear unsplittable multicommodity flow problems

Author: Martim Joyce-Moniz, Bernard Fortz, Luis Borges Gouveia, Graphes et Optimisation Mathématique [Bruxelles] (GOM), Université libre de Bruxelles (ULB), Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centro de Investigação Operacional (CIO), Universidade de Lisboa = University of Lisbon (ULISBOA), Universidade de Lisboa (ULISBOA), Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL)
Subjects: Mathematical optimization, Combinatorial optimization, Information Systems and Management, General Computer Science, Linear programming, 0211 other engineering and technologies, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, Piecewise linear function, 0202 electrical engineering, electronic engineering, information engineering, OR in telecommunications, Integer programming, Mathematics, 021103 operations research, Unsplittable Flows, 020206 networking & telecommunications, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Multi-commodity flow problem, Flow (mathematics), Modeling and Simulation, Relaxation (approximation), Networks, Routing (electronic design automation)
Abstract: International audience; In this paper, we consider multicommodity flow problems, with unsplit-table flows and piecewise linear routing costs. We first focus on the case where the piecewise linear routing costs are convex. We show that this problem is N P-hard for the general case, but polynomially solvable when there is only one commodity. We then propose a strengthened mixed-integer programming formulation for the problem. We show that the linear relaxation of this formulation always gives the optimal solution of the problem for the single commodity case. We present a wide array of computational experiments, showing this formulation also produces very tight linear programming bounds for the multi-commodity case. Finally, we also adapt our formulation for the non-convex case. Our experimental results imply that the linear programming bounds for this case, are only slightly than the ones of state-of-the-art models for the splittable flow version of the problem.
Published: 2017

30. Robust Altitude and Attitude Sliding Mode Controllers for Quadrotors

Author: Denis Efimov, Maan El Badaoui El Najjar, Boussad Abci, Gang Zheng, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Non-Asymptotic estimation for online systems (NON-A), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Deformable Robots Simulation Team (DEFROST ), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: quadrotors, Lyapunov stability, Lyapunov function, 0209 industrial biotechnology, Newton-Euler equations, 020208 electrical & electronic engineering, Sliding-mode control, robustness, 02 engineering and technology, stability analysis, Sliding mode control, symbols.namesake, Formalism (philosophy of mathematics), 020901 industrial engineering & automation, Control and Systems Engineering, Robustness (computer science), Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, symbols, Uniform boundedness, Altitude control, Newton–Euler equations, Mathematics
Abstract: International audience; This paper considers the problem of attitude and altitude control of quadrotors using the sliding mode control theory. The mathematical model of the quadrotor is derived using the Euler-Newton formalism with extended assumptions on disturbing aerodynamical forces (not necessary uniformly bounded). The proposed control demonstrates an enhanced robustness against such disturbances. The comparison between the classical controller and the proposed one is demonstrated analytically, through Lyapunov theory, and in simulations to validate the proposed sliding mode control algorithm.
Published: 2017

31. Supervisory acceleration of convergence for homogeneous systems

Author: Arie Levant, Andrei Polyakov, Wilfrid Perruquetti, Denis Efimov, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), School of Mathematical Sciences [Tel Aviv], Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University [Tel Aviv]-Tel Aviv University [Tel Aviv], Systèmes Non Linéaires et à Retards (SyNeR), Centrale Lille, ANR-15-CE23-0007,Finite4SoS,Commande et estimation en temps fini pour les Systèmes de Systèmes(2015), School of Mathematical Sciences [Tel Aviv] (TAU), Raymond and Beverly Sackler Faculty of Exact Sciences [Tel Aviv] (TAU), Tel Aviv University (TAU)-Tel Aviv University (TAU), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 0209 industrial biotechnology, 02 engineering and technology, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Computer Science Applications, Acceleration, 020901 industrial engineering & automation, Exponential stability, Exponential growth, Rate of convergence, Control and Systems Engineering, Homogeneous, Control theory, Bounded function, Integrator, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Mathematics
Abstract: International audience; The rate of convergence to the origin for a chain of integrators stabilized by homogeneous feedback is accelerated by a supervisory switching of control parameters. The proposed acceleration algorithm ensures a fixed-time convergence for otherwise exponentially or finite-time stable homogeneous closed-loop systems. Bounded disturbances are taken into account. The results are especially useful in the case of exponentially stable systems widespread in the practice. The proposed switching strategy is illustrated by computer simulation.
Published: 2016

32. Computing Difference Abstractions of Metabolic Networks Under Kinetic Constraints

Author: Cristian Versari, Emilie Allart, Joachim Niehren, Université de Lille, BioComputing, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Luca Bortolussi, Guido Sanguinetti, Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 050101 languages & linguistics, Gene knockout prediction, Steady state, Computer science, 05 social sciences, Metabolic network, 02 engineering and technology, Reaction networks, Abstract interpretation, Domain (software engineering), Constraint (information theory), Metabolism, Ask price, Constraints, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, [INFO]Computer Science [cs], [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Heuristics, Systems biology, Algorithm, Linear equation, Synthetic biology
Abstract: International audience; Algorithms based on abstract interpretation were proposed recently for predicting changes of reaction networks with partial kinetic information. Their prediction precision, however, depends heavily on which heuristics are applied in order to add linear consequences of the steady state equations of the metabolic network. In this paper we ask the question whether such heuristics can be avoided while obtaining the highest possible precision. This leads us to the first algorithm for computing the difference abstractions of a linear equation system exactly without any approximation. This algorithm relies on the usage of elementary flux modes in a nontrivial manner, first-order definitions of the abstractions, and finite domain constraint solving.An extended version is available at: http://researchers.lille.inria.fr/niehren/journal-CMSB-2019.pdf
Published: 2019

33. Oblivious and Semi-Oblivious Boundedness for Existential Rules

Author: Sophie Tison, Marie-Laure Mugnier, Lily Gallois, Michel Leclère, Federico Ulliana, Pierre Bourhis, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Self-adaptation for distributed services and large software systems (SPIRALS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Graphs for Inferences on Knowledge (GRAPHIK), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), DataLens - Projet CNRS Momentum Gérer des données sans fuite d’information, ANR-18-CE23-0003,CQFD,Requêtes Ontologiques Complexes sur des Fédérations de Données Hétérogènese(2018), ANR-15-CE39-0009,DataCert,Spécification intensive en Coq d'intégration de données orientée sécurité(2015), ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, This work was supported by ANR projects CQFD (ANR-18-CE23-0003), DataCert (ANR-15-CE39-0009), DeLTA (ANR-16- CE40-0007) and the CNRS-Momentum project Managing-Data., and LIRMM (UM, CNRS)
Subjects: FOS: Computer and information sciences, Chase, Computer Science - Artificial Intelligence, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, Upper and lower bounds, Existentialism, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Set (abstract data type), Computer Science - Databases, 0202 electrical engineering, electronic engineering, information engineering, Existential rules, Mathematics, Discrete mathematics, Boundedness, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Databases (cs.DB), First-order rewritability, 16. Peace & justice, Computer Science - Computational Complexity, Artificial Intelligence (cs.AI), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Bounded function, 020201 artificial intelligence & image processing
Abstract: We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure , that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 [Bourhis et al., 2019] and an appendix with full proofs.
Published: 2019

34. Containment of Shape Expression Schemas for RDF

Author: Sławek Staworko, Piotr Wieczorek, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), University of Wrocław [Poland] (UWr), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer science, counter-example, 02 engineering and technology, 01 natural sciences, RDF, containment, Schema (psychology), Schema, 0202 electrical engineering, electronic engineering, information engineering, Rdf graph, Computer Science::Databases, Discrete mathematics, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], 010401 analytical chemistry, ShEx, computer.file_format, Graph, Logic in Computer Science (cs.LO), 0104 chemical sciences, Decidability, Embedding, 020201 artificial intelligence & image processing, computer, MathematicsofComputing_DISCRETEMATHEMATICS, Counterexample
Abstract: International audience; We study the problem of containment of shape expression schemas (ShEx) for RDF graphs. We identify a subclass of ShEx that has a natural graphical representation in the form of shape graphs and whose semantics is captured with a tractable notion of embedding of an RDF graph in a shape graph. When applied to pairs of shape graphs, an embedding is a sufficient condition for containment, and for a practical subclass of deterministic shape graphs, it is also a necessary one, thus yielding a subclass with tractable containment. Containment for general shape graphs is EXP-complete. Finally , we show that containment for arbitrary ShEx is decid-able. CCS CONCEPTS • Information systems → Graph-based database models ; Resource Description Framework (RDF); • Theory of computation → Database theory; Database interoper-ability.
Published: 2019

35. Attributing and Referencing (Research) Software: Best Practices and Outlook from Inria

Author: Pierre Alliez, Roberto Di Cosmo, Benjamin Guedj, Alain Girault, Nicolas P. Rougier, Mohand-Said Hacid, Arnaud Legrand, Geometric Modeling of 3D Environments (TITANE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Software Heritage, Computer science department [University College London] (UCL-CS), University College of London [London] (UCL), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Sound Programming of Adaptive Dependable Embedded Systems (SPADES), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Base de Données (BD), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Mnemonic Synergy (Mnemosyne), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut des Maladies Neurodégénératives [Bordeaux] (IMN), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Department of Computer science [University College of London] (UCL-CS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, CNRS, Université de Lille, and Laboratoire Paul Painlevé [LPP]
Subjects: FOS: Computer and information sciences, Reference software, Reference, 010504 meteorology & atmospheric sciences, General Computer Science, Computer science, Best practice, 02 engineering and technology, computer.software_genre, 01 natural sciences, Computer Science - Software Engineering, Software, 020204 information systems, Taxonomy (general), 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DL]Computer Science [cs]/Digital Libraries [cs.DL], Digital Libraries (cs.DL), 0105 earth and related environmental sciences, Debugger, business.industry, General Engineering, Software development, Computer Science - Digital Libraries, Software reference, Data science, Authorship, Software Engineering (cs.SE), Software citation, Development process, business, Software architecture, Citation, computer
Abstract: International audience; Software is a fundamental pillar of modern scientific research, not only in computer science, but actually across all fields and disciplines. However, there is a lack of adequate means to cite and reference software, for many reasons. An obvious first reason is software authorship, which can range from a single developer to a whole team, and can even vary in time. The panorama is even more complex than that, because many roles can be involved in software development: software architect, coder, debugger, tester, team manager, and so on. Arguably, the researchers who have invented the key algorithms underlying the software can also claim a part of the authorship. And there are many other reasons that make this issue complex. We provide in this paper a contribution to the ongoing efforts to develop proper guidelines and recommendations for software citation, building upon the internal experience of Inria, the French research institute for digital sciences. As a central contribution, we make three key recommendations. (1) We propose a richer taxonomy for software contributions with a qualitative scale. (2) We claim that it is essential to put the human at the heart of the evaluation. And (3) we propose to distinguish citation from reference.
Published: 2019

36. Counting Minimal Transversals of β-Acyclic Hypergraphs

Author: Florent Capelli, Mamadou Moustapha Kanté, Benjamin Bergougnoux, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, Computer Networks and Communications, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Dominating sets, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Chordal graph, 020204 information systems, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Strongly chordal graphs, Time complexity, Computer Science::Databases, Mathematics, Applied Mathematics, β-Acyclic Hypergraphs, Computational Theory and Mathematics, Counting problem, 010201 computation theory & mathematics, Line (geometry), Minimal transversals
Abstract: International audience; We prove that one can count in polynomial time the number of minimal transversalsof β-acyclic hypergraphs. In consequence, we can count in polynomial timethe number of minimal dominating sets of strongly chordal graphs, continuingthe line of research initiated in [M.M. Kanté and T. Uno, Counting MinimalDominating Sets, TAMC'17].
Published: 2019

37. BEARS: An Extensible Java Bug Benchmark for Automatic Program Repair Studies

Author: Fernanda Madeiral, Marcelo de Almeida Maia, Martin Monperrus, Simon Urli, Federal University of Uberlândia [Uberlândia] (UFU), Self-adaptation for distributed services and large software systems (SPIRALS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria), and Royal Institute of Technology [Stockholm] (KTH )
Subjects: FOS: Computer and information sciences, Java, business.industry, Computer science, 020207 software engineering, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], 02 engineering and technology, Commit, Maintenance engineering, Pipeline (software), Software Engineering (cs.SE), Computer Science - Software Engineering, Software bug, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Benchmark (computing), Test suite, State (computer science), Software engineering, business, computer, computer.programming_language
Abstract: Benchmarks of bugs are essential to empirically evaluate automatic program repair tools. In this paper, we present Bears, a project for collecting and storing bugs into an extensible bug benchmark for automatic repair studies in Java. The collection of bugs relies on commit building state from Continuous Integration (CI) to find potential pairs of buggy and patched program versions from open-source projects hosted on GitHub. Each pair of program versions passes through a pipeline where an attempt of reproducing a bug and its patch is performed. The core step of the reproduction pipeline is the execution of the test suite of the program on both program versions. If a test failure is found in the buggy program version candidate and no test failure is found in its patched program version candidate, a bug and its patch were successfully reproduced. The uniqueness of Bears is the usage of CI (builds) to identify buggy and patched program version candidates, which has been widely adopted in the last years in open-source projects. This approach allows us to collect bugs from a diversity of projects beyond mature projects that use bug tracking systems. Moreover, Bears was designed to be publicly available and to be easily extensible by the research community through automatic creation of branches with bugs in a given GitHub repository, which can be used for pull requests in the Bears repository. We present in this paper the approach employed by Bears, and we deliver the version 1.0 of Bears, which contains 251 reproducible bugs collected from 72 projects that use the Travis CI and Maven build environment., Comment: Proceedings of the 26th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER '19)
Published: 2019

38. Logics for Unordered Trees with Data Constraints

Author: Adrien Boiret, Ralf Treinen, Vincent Hugot, Joachim Niehren, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Sécurité des Données et des Systèmes (SDS), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Preuves, Programmes et Systèmes (PPS), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), ANR-15-CE25-0001,Colis,Correction de scripts Linux(2015), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Class (set theory), Reduction (recursion theory), Computer Networks and Communications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Databases, string comparisons, Mathematics, Discrete mathematics, Applied Mathematics, String (computer science), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Automaton, Undecidable problem, Decidability, Prefix, Tree (data structure), logics, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, data trees, Counting Mso
Abstract: International audience; We study counting monadic second-order logics (CMso) for unordered data trees. Our objective is to enhance this logic with data constraints for comparing string data values. Comparisons between data values at arbitrary positions of a data tree quickly lead to undecidability. Therefore, we restrict ourselves to comparing sibling data values of unordered trees. But even in this case CMso remains undecidable when allowing data comparisons that can check the equality of string factors. However, for more restricted data constraints that can only check the equality of string prefixes, it becomes decidable. This decidability result is obtained by reduction to WSkS. Furthermore, we exhibit a restricted class of constraints which can be used in transitions of tree automata, resulting in a model with tractable complexity, which can be extended with structural equality tests between siblings. This practical restriction is relevant to applications such as checking well-formedness properties of file system trees.
Published: 2019

39. Knowledge Compilation Languages as Proof Systems

Author: Florent Capelli, Linking Dynamic Data (LINKS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Polynomial hierarchy, Theoretical computer science, Computer Science - Artificial Intelligence, Computer science, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Computer Science - Computational Complexity, Artificial Intelligence (cs.AI), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Maximum satisfiability problem, 0202 electrical engineering, electronic engineering, information engineering, Knowledge compilation, [INFO]Computer Science [cs], 020201 artificial intelligence & image processing, ComputingMilieux_MISCELLANEOUS
Abstract: In this paper, we study proof systems in the sense of Cook-Reckhow for problems that are higher in the polynomial hierarchy than coNP, in particular, #SAT and maxSAT. We start by explaining how the notion of Cook-Reckhow proof systems can be apply to these problems and show how one can twist existing languages in knowledge compilation such as decision DNNF so that they can be seen as proof systems for problems such as #SAT and maxSAT.
Published: 2019

40. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables

Author: Iovka Boneva, Joachim Niehren, Momar Sakho, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 050101 languages & linguistics, Matching (statistics), Theoretical computer science, Computational complexity theory, automata, Computer science, computer.internet_protocol, data streams, Complex event processing, 02 engineering and technology, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], 0202 electrical engineering, electronic engineering, information engineering, patterns, 0501 psychology and cognitive sciences, tree languages and tree automata, queries, computational complexity, Data stream mining, 05 social sciences, String (computer science), trees, Automaton, Tree (data structure), 020201 artificial intelligence & image processing, computer, XML
Abstract: International audience; We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on Xml streams with references.
Published: 2019

41. Constraining kernel estimators in semiparametric copula mixture models

Author: Gildas Mazo, Yaroslav Averyanov, Mathématiques et Informatique Appliquées du Génome à l'Environnement [Jouy-En-Josas] (MaIAGE), Institut National de la Recherche Agronomique (INRA), Université Paris Saclay (COmUE), MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Mazo, Gildas, Université Paris-Saclay, Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Laboratoire Paul Painlevé - UMR 8524 (LPP), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Santé publique : épidémiologie et qualité des soins-EA 2694 (CERIM), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, and Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)
Subjects: Statistics and Probability, [SDV]Life Sciences [q-bio], Kernel density estimation, 02 engineering and technology, 01 natural sciences, Clustering, Copula (probability theory), 010104 statistics & probability, Semiparametric, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, Nonparametric, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Cluster analysis, Mathematics, Pointwise, Mixture model, [STAT.ME] Statistics [stat]/Methodology [stat.ME], Applied Mathematics, Nonparametric statistics, Estimator, [STAT] Statistics [stat], [STAT]Statistics [stat], Computational Mathematics, Kernel, Computational Theory and Mathematics, Rate of convergence, Copula, 020201 artificial intelligence & image processing, copula, kernel, semiparametric, nonparametric, mixture model, clustering, [STAT.ME]Statistics [stat]/Methodology [stat.ME]
Abstract: Working paper Il s'agit d'un preprint qui a été soumis dans une revue à comité de lecture; This paper presents a novel algorithm for performing inference and/or clustering in semiparametric copula-based mixture models. The algorithm replaces the standard kernel density estimator by a weighted version that permits to take into account the constraints put on the underlying marginal densities. Lower misclassification error rates and better estimates are obtained on simulations. The pointwise consistency of the weighted kernel density estimator is established under an assumption on the rate of convergence of the sample maximum.
Published: 2019

42. L2-stability criterion for systems with decentralized asynchronous controllers

Author: Nathan van de Wouw, Christophe Fiter, Jijju Thomas, Laurentiu Hetel, Jean-Pierre Richard, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centrale Lille, Non-Asymptotic estimation for online systems (NON-A-POST), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Eindhoven University of Technology [Eindhoven] (TU/e), Université de Lille, Non-Asymptotic estimation for online systems (NON-A), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Dynamics and Control
Subjects: 0209 industrial biotechnology, Computer science, Stability criterion, 020208 electrical & electronic engineering, Sampling (statistics), 02 engineering and technology, Asynchrony (computer programming), LTI system theory, 020901 industrial engineering & automation, Asynchronous communication, Control theory, Computer Science::Systems and Control, Control system, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, Actuator
Abstract: International audience; This paper deals with the stability analysis of decentralized sampled-data Linear Time Invariant (LTI) control systems with asynchronous sensors and actuators. We consider the case where each controller in the decentralized setting has its own sampling and actuation frequency which translates to asynchrony between sensors and actuators. The errors induced due to sampling and asynchronicity are modelled using two different operator approaches, leading to simple L2-stability criteria for the overall decentralized control system. The simplicity of the obtained criteria is illustrated by an example and simulation results exhibit the effectiveness of the approach.
Published: 2018

43. A Framework for Understanding the Role of Morphology in Universal Dependency Parsing

Author: Pascal Denis, Mathieu Dehouck, Machine Learning in Information Networks (MAGNET), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: Morphology (linguistics), Parsing, Computer science, business.industry, 02 engineering and technology, 010501 environmental sciences, computer.software_genre, 01 natural sciences, Measure (mathematics), Syntax, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Simple (abstract algebra), Dependency grammar, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Artificial intelligence, [SHS.LANGUE]Humanities and Social Sciences/Linguistics, business, computer, Word (computer architecture), Natural language processing, 0105 earth and related environmental sciences
Abstract: This paper presents a simple framework for characterizing morphological complexity and how it encodes syntactic information. In particular, we propose a new measure of morphosyntactic complexity in terms of governordependent preferential attachment that explains parsing performance. Through experiments on dependency parsing with data from Universal Dependencies (UD), we show that representations derived from morphological attributes deliver important parsing performance improvements over standard word form embeddings when trained on the same datasets. We also show that the new morphosyntactic complexity measure is predictive of the gains provided by using morphological attributes over plain forms on parsing scores, making it a tool to distinguish languages using morphology as a syntactic marker from others.
Published: 2018

44. Classes of languages generated by the Kleene star of a word

Author: Laure Daviaud, Charles Paperman, Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Italiano, G., Pughizzini, G., and Sannella, D.
Subjects: QA75, Of the form, 0102 computer and information sciences, 02 engineering and technology, Decidability, Lattice (discrete subgroup), 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, QA76, Combinatorics, symbols.namesake, Regular language, Kleene star, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Profinite equations, 0101 mathematics, QA, Quotient, Mathematics, Automata theory, 060201 languages & linguistics, Discrete mathematics, Boolean algebra (structure), 010102 general mathematics, Abstract family of languages, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 06 humanities and the arts, Regular languages, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, 0602 languages and literature, symbols, 020201 artificial intelligence & image processing, Word (computer architecture), Information Systems
Abstract: International audience; In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them.
Published: 2018

45. Stability analysis of some classes of input-affine nonlinear systems with aperiodic sampled-data control

Author: Françoise Lamnabhi-Lagarrigue, Jean-Pierre Richard, Mihaly Petreczky, Laurentiu Hetel, Hassan Omran, École des Mines de Douai (Mines Douai EMD), Institut Mines-Télécom [Paris] (IMT), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Non-Asymptotic estimation for online systems (NON-A), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire des signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: sampled-data systems, 0209 industrial biotechnology, Polynomial, Explained sum of squares, Stability (learning theory), Linear matrix inequality, 02 engineering and technology, stability analysis, Upper and lower bounds, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Stability conditions, Nonlinear system, 020901 industrial engineering & automation, emulation approach, Control and Systems Engineering, Control theory, aperiodic sampling, Nonlinear systems, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Affine transformation, Electrical and Electronic Engineering, Mathematics
Abstract: International audience; In this paper we investigate the stability analysis of nonlinear sampled-data systems, which are affine in the input. We assume that a stabilizing controller is designed using the emulation technique. We intend to provide sufficient stability conditions for the resulting sampled-data system. This allows to find an estimate of the upper bound on the asynchronous sampling intervals, for which stability is ensured. The main idea of the paper is to address the stability problem in a new framework inspired by the dissipativity theory. Furthermore, the result is shown to be constructive. Numerically tractable criteria are derived using linear matrix inequality for polytopic systems and using sum of squares technique for the class of polynomial systems.
Published: 2016

46. Finite-time position and velocity estimation adapted to noisy biased acceleration measurements from periodic motion

Author: Antonio Estrada, Wilfrid Perruquetti, Denis Efimov, Consejo Nacional de Ciencia y Tecnología [Mexico] (CONACYT), Non-Asymptotic estimation for online systems (NON-A), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: Physics, periodic signals, Work (physics), Spatial acceleration, 020206 networking & telecommunications, 02 engineering and technology, 01 natural sciences, Noise (electronics), [SPI.AUTO]Engineering Sciences [physics]/Automatic, Computer Science Applications, 010309 optics, Periodic function, estimation adaptation, Acceleration, Control and Systems Engineering, Position (vector), Control theory, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Finite time, Finite-time, Constant (mathematics)
Abstract: International audience; The present work focuses on the problem of velocity and position estimation. A solution is presented for a class of oscillating systems in which position, velocity and acceleration are zero mean signals. The proposed scheme considers that the dynamic model of the system is unknown. Only noisy acceleration measurements, that may be contaminated by zero mean noise and constant bias, are considered to be available. The proposal uses the periodic nature of the signals obtaining finite-time estimations while tackling integration drift accumulation.
Published: 2016

47. Observability of singular time-delay systems with unknown inputs

Author: Gang Zheng, Francisco Javier Bejarano, Escuela Superior de Ingeniería Mecánica y Eléctrica - Unidad Profesional Ticomán (ESIME-UPT), Instituto Politecnico Nacional [Mexico] (IPN), Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 0209 industrial biotechnology, Commensurate delay systems, General Computer Science, Mechanical Engineering, Polynomial ring, State vector, 02 engineering and technology, Singular systems, Observability analysis, 020901 industrial engineering & automation, Control and Systems Engineering, Control theory, Singular solution, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, 020201 artificial intelligence & image processing, Observability, Electrical and Electronic Engineering, Singular linear systems, Mathematics
Abstract: International audience; In this manuscript we give sufficient conditions guaranteeing the observability of singular linear systems with commensurable delays affected by unknown inputs appearing in both the state equation and the output equation. These conditions allow for the reconstruction of the entire state vector using past and actual values of the system output. The obtained conditions coincide with known necessary and sufficient conditions of singular linear systems without delays.
Published: 2016

48. Unknown input observer for linear time-delay systems

Author: Francisco Javier Bejarano, Jean-Pierre Richard, Gang Zheng, Wilfrid Perruquetti, Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Non-Asymptotic estimation for online systems (NON-A), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Escuela Superior de Ingeniería Mecánica y Eléctrica - Unidad Profesional Ticomán (ESIME-UPT), Instituto Politecnico Nacional [Mexico] (IPN), Centrale Lille, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: commensurate delays, Large class, 0209 industrial biotechnology, Observer (quantum physics), Linear system, observer, unknown inputs, 02 engineering and technology, Sense (electronics), 020901 industrial engineering & automation, Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, State observer, Electrical and Electronic Engineering, Time complexity, Delay systems, Mathematics
Abstract: International audience; This paper investigates an unknown input observer design for a large class of linear systems with unknown inputs and commensurate delays. A Luenberger-like observer is proposed by involving only the past and actual values of the system output. The required conditions for the proposed observer are considerably relaxed in the sense that they coincide with the necessary and sufficient conditions for the unknown input observer design of linear systems without delays.
Published: 2015

49. A tractable multi-partitions clustering

Author: Matthieu Marbac, Vincent Vandewalle, CHU Lille, Université de Lille, METRICS : Evaluation des technologies de santé et des pratiques médicales - ULR 2694, Evaluation des technologies de santé et des pratiques médicales - ULR 2694 [METRICS], Centre de Recherche en Economie et Statistique [Bruz] (CREST), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille, and Vandewalle, Vincent
Subjects: Statistics and Probability, FOS: Computer and information sciences, Computer science, Information Criteria, Feature selection, 02 engineering and technology, 01 natural sciences, Methodology (stat.ME), 010104 statistics & probability, Model-based clustering, Block (programming), 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Cluster analysis, Class variable, ComputingMilieux_MISCELLANEOUS, Statistics - Methodology, Model choice, Mixture model, [STAT.ME] Statistics [stat]/Methodology [stat.ME], Applied Mathematics, Model selection, Latent class model, [STAT] Statistics [stat], [STAT]Statistics [stat], Computational Mathematics, Mixed-data, Computational Theory and Mathematics, Conditional independence, 020201 artificial intelligence & image processing, Variables selection, Algorithm, [STAT.ME]Statistics [stat]/Methodology [stat.ME]
Abstract: International audience; In the framework of model-based clustering, a model allowing several latent class variables is proposed. This model assumes that the distribution of the observed data can be factorized into several independent blocks of variables. Each block is assumed to follow a latent class model ({\it i.e.,} mixture with conditional independence assumption). The proposed model includes variable selection, as a special case, and is able to cope with the mixed-data setting. The simplicity of the model allows to estimate the repartition of the variables into blocks and the mixture parameters simultaneously, thus avoiding to run EM algorithms for each possible repartition of variables into blocks. For the proposed method, a model is defined by the number of blocks, the number of clusters inside each block and the repartition of variables into block. Model selection can be done with two information criteria, the BIC and the MICL, for which an efficient optimization is proposed. The performances of the model are investigated on simulated and real data. It is shown that the proposed method gives a rich interpretation of the dataset at hand ({\it i.e.,} analysis of the repartition of the variables into blocks and analysis of the clusters produced by each block of variables).
Published: 2018

50. Assessing primitives performance on multi-stage execution

Author: Clément Béra, Stéphane Ducasse, Sophie Kaleba, Informatics and Applied Informatics, Software Languages Lab, Analyses and Languages Constructs for Object-Oriented Application Evolution (RMOD), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Computer science, Optimizing compiler, 02 engineering and technology, computer.software_genre, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, Set (abstract data type), 0202 electrical engineering, electronic engineering, information engineering, 0501 psychology and cognitive sciences, 050107 human factors, Smalltalk, computer.programming_language, Programming language, Virtual ma-chine, 05 social sciences, String (computer science), primitive, 020207 software engineering, Managed runtime, Computer Science Applications, Just-in-Time compiler, Just-in-time compilation, Computational Theory and Mathematics, Virtual machine, Virtual Machine, Compiler, computer, Interpreter
Abstract: International audience; Virtual machines, besides the interpreter and just-in-time compiler optimization facilities, also include a set of primitive operations that the client language can use. Some of these are essential and cannot be performed in any other way. Others are optional: they can be expressed in the client language but are often implemented in the virtual machine to improve performance when the just-in-time compiler is unable to do so (start-up performance, speculative optimizations not implemented or not mature enough, etc.). In a hybrid runtime, where code is executed by an interpreter and a just-in-time compiler, the implementor can choose to implement optional primitives in the client language , in the virtual machine implementation language (typically C or C++), or on top of the just-in-time compiler back-end. This raises the question of the maintenance and performance trade-offs of the different alternatives. As a case study, we implemented the String comparison optional primitive in each case. This paper describes the different implementations , discusses the maintenance cost of each of them and evaluates for different string sizes the execution time in Cog, a Smalltalk virtual machine.
Published: 2018

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

1,980 results on '"Inria Lille - Nord Europe"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources