Séminaire : Yacine Izza (CRIL, UArtois)
Avancées récentes en informatique à l’université de Nankin et à l’université d’Artois.
Lens, Monday, June 6th 2016
10h-10h10 : Welcome, Prof. Eric Grégoire
10h10-10h50 : Prof. Chongjun Wang
Talk title: A General Framework for Big Data Analysis and Some Examples
Discovering knowledge from data is the constant theme in the process of human civilization for the knowledge or insight discovered from data may lead us to a better life and work. With the development of technology and the progress of society, the data became to be more complex, huge and big and the system needing became to be more personalized and flat. How to deal with these challenges is an urgent problem. This talk will briefly introduce some research work of ours in data analysis and knowledge discovery and a general framework and some application cases will be given.
10h50-11h20 : Prof. Frédéric Koriche
Talk title: Online Learning of Probabilistic Graphical Models
Probabilistic graphical models (including Bayesian networks and Markov networks) are a widely accepted framework for representing, in a compact and intelligible way, high dimensional probability distributions. One of the most important problems in this setting is to extract from a series of outcomes the structure and the parameters of a graphical model that explains, as best as possible, the distribution of observed outcomes. In this talk, we shall focus on the “online” version of this learning problem, where outcomes are supplied one-by-one. Online learning is particularly suitable for large-scale domains and streamline applications. We shall present several theoretical and experimental results for online learning with different classes of graphical models, namely, tree-structured probabilistic models, Bayesian polytrees, and bounded treewidth Markov networks. Our online learning algorithms rely on both convex relaxation techniques and constraint optimization methods which exploit the polytope structure of the target model class.
11h20-11h50 : Dr. Sébastien Konieczny
Talk title: Belief Change Tools for Negotiation in Multi-Agent Systems
Belief change is a logical theory that study the evolution of beliefs of agents. In this talk we will describe how tools coming from this theory, in particular merging operators and revision operators can be used to model different abstract agreement methods. We will enumerate the different methods that we have proposed: iterated merging and conciliation operators, belief game models, conciliation operators, and belief revision games. In all these cases the problem is, starting from the initial points of view of all agents, to define the point of view of the group (or of each agent), after a (abstract) negotiation between the agents points of view.
14h-14h30 : Prof. Eric Grégoire
Talk title: Computing Consensus
Computing a consensus is a key task in various AI areas, ranging from belief fusion, social choice and negotiation, among others. Consensus operators deliver parts of the set-theoretical union of the information sources to be reconciled such that no source is logically contradicted. In this talk, the focus is on a family of consensus operators in the Boolean framework that are maximal in various ways. From a computational point of view, we propose a generic problem transformation that leads to a method that proves experimentally efficient very often, even for large conflicting sources to be reconciled.
14h30-15h10 : Prof. Linzhang Wang
Talk title: An Empirical Study on Detecting and Fixing Buffer Overflow Bugs
Buffer overflow is one of the most common types of software security vulnerabilities. Although researchers have proposed various static and dynamic techniques for buffer overflow detection, buffer overflow attacks against both legacy and newly-deployed software systems are still quite prevalent. Compared with dynamic detection techniques, static techniques are more systematic and scalable. However, there are few studies on the effectiveness of state-of-the-art static buffer overflow detection techniques. In this talk, I will introduce our in-depth quantitative and qualitative study on static buffer overflow detection techniques. (1) A quantitative study of the state-of-art static techniques for buffer overflow detection on 100 real-world bugs from 63 real-world projects totaling 28 Million LoC; (2) A qualitative analysis of the false-positives and false negatives of state-of-the-art static buffer overflow detection techniques, which can guide the design and implementation of more advanced buffer overflow detection techniques.(3) A categorization on the fix patterns of buffer overflow bugs to guide both manual and automated buffer overflow repair techniques.
15h10-15h40 : Prof. Daniel Le Berre
Talk title: Software Dependency Management with Boolean Modelling: some Use Cases
Software dependency management is the problem of installing or removing from a system a piece of software (a component) while
respecting some dependencies (constraints) : one component requires another component, one component conflicts with another component. Such problem is NP-complete, just as hard as SAT. This talk will summarize the work done since 2007 on three different use case of dependency management: Eclipse plugins, Linux packages, and the more general case of software product lines.
16h10-16h50 : Prof. Wei Hu
Talk title: Entity linkage in the Linked Data: approaches and analysis
Linked Data is about using the Web to connect related datasets, and it has reached a scale in billions of entities. Entity linkage aims to discover different entities that refer to the same real-world thing, which is a fundamental issue in knowledge graph construction, natural language understanding, query answering, etc. In this talk, I will first introduce our recent work on entity linkage using bootstrapping. Then, I will present our analytical results on the status of entity linkage in the life science domain.
16h50-17h30 : Dr. Stefan Mengel and Prof. Pierre Marquis
Talk title: Model Counting at CRIL
Counting the number of models of a propositional formula is a computationally hard problem (#P-complete) which is central to a large number of applications (reliability analysis, probabilistic inference, etc). In this talk, we will present a couple of issues related to the model counting problem which are investigated at CRIL. In particular, we will present work on structural restrictions of CNF formulas that make model counting tractable. We will explain links of these techniques to knowledge compilation, a preprocessing regime for propositional knowledge bases, and discuss how lower bounds on some classical languages in knowledge compilation can be seen as lower bounds on practical DPLL based model counting. We will also present some preprocessing techniques that prove useful for making model counting easier in practice, and a new knowledge compilation language offering tractable model counting.
Lens, Tuesday, June 7th 2016
CRIL meeting room (P304)
9h-11h : Discussion about our future collaborations
Séminaire : Sébastien Konieczny (CRIL, CNRS)
Pierre Bourhis (LIFL, CNRS)
In database management, one of the principal task is to optimize the queries to evaluate them efficiently. It is in particular the case for recursive queries for which their evaluation can lead to crawl all the database. In particular, one of the main question is to minimize the queries in order to avoid to evaluate useless parts of the query. The core theoretical question around this line of work is the problem of inclusion of a query in another. Interestedly, this question is related to an important question in IA which is to answer a query when the data is incomplete but rules are given to derive new information. This problem is called certain query answering. In both context, if both problem are undecidable in general, there are fragments based on guardedness that are decidable due to the fact there exists witness of the problems that have a bounded tree width and that their encoding in trees is regular. Furthermore, the queries can be translated in MSO. In both contexts, Courcelle’s Theorems imply the decidability of both problems. I will present to the different results on the translation of logic class of formula for our problems into tree automata to obtain tight bounds to the problems of inclusion of recursive queries or certain query answering.
Srdjan Vesic (CRIL, CNRS)
In almost all existing semantics in argumentation, a strong attack
has a lethal effect on its target that a set of several weak
attacks may not have. This paper investigates the case where
several weak attacks may compensate one strong attack. It
defines a broad class of ranking semantics, called alpha-BBS,
which satisfy compensation. alpha-BBS assign a burden number
to each argument and order the arguments with respect
to those numbers. We study formal properties of alpha-BBS, implement
an algorithm that calculates the ranking, and perform
experiments that show that the approach computes the ranking
very quickly. Moreover, an approximation of the ranking
can be provided at any time.