1st Symposium M4D2, 11 May, 2016
Description: The main goal of M4D2 is to bring together researchers from fields of computer science that may seem at first glance rather distant but that share in fact several common points. This is particularly the case for topics pertaining to
decision making and social choice,
complex and multi-agent systems,
knowledge discovery and machine learning,
game theory and operations research, etc.
and that share the same interest in mathematical tools coming from
ordered sets and lattice theory, knowledge spaces,
clone theory and aggregation functions,
Boolean and pseudo-Boolean functions,
graph and hypergraph theory, combinatorial optimisation, etc.
With this event we hope to lay ground to fruitful discussions and expertise exchanges, and to provide a space where participants will have the chance, not only to present their recent achievements, but most importantly to share and discover different perspectives, to acquire new ideas, and to become involved in new research efforts where their expertise is welcome and needed.
M4D2 is organized by Miguel Couceiro and Amedeo Napoli in the framework of the MALOTEC seminar (the French acronym for « Seminar of mathematics and logic for knowledge discovery ») held in the ORPAILLEUR Team, at LORIA. The 1st symposium M4D2 will take place on May 11, 2016. There will be 4 presentations of foreign researchers and 4 presentations of researchers belonging to different teams and departments of LORIA. All members of LORIA, IECL, CRAN and other computer science and mathematics laboratories, are most welcome!
Localization: M4D2 will take place on May 11, 2016, in B013, at LORIA.
Program:
9:30: Welcome
9:45-10:35: Jean-Paul Doignon
Title: On the shelling antimatroids of split graphs
Abstract: Matroids and antimatroids reflect some part of the structure of various combinatorial objects. They form a general setting for many optimization problems, for instance: finding a covering forest with smallest weight in a graph with positively weighted edges becomes the problem of finding a base with smallest weight in a positively weighted matroid. In geometry, for finite sets of points in the plane (or more generally in d-dimensional space), matroids encode the linearity part of the induced structure and antimatroids encode the convexity part. While optimization problems on matroids have been thoroughly investigated, those on antimatroids are less studied. For an antimatroid whose elements are weighted with integer numbers, the problem asking for a convex subset with minimum weight contains many problems on various combinatorial structures, for instance finding a beginning set with minimum weight in a weighted poset, or finding a subtree with minimum weight in a weighted tree. Our main result consists in a polynomial-time algorithm for the case of the antimatroid formed by the convex subsets of a weighted, split graph. In view of the linear programming approach to the problem, we also pay attention to the convex polytope whose vertices are the characteristic vectors of the convex subsets of an antimatroid. It happens that another motivation for investigating the same polytope comes from models of computer-based assessment of student knowledge (as in the aleks system). This is joint work with Jean Cardinal and Keno Merckx.
10:45-11:15: Romain Pèchoux
Title: Algebra and Coalgebra in the Light Affine Lambda Calculus
Abstract: Algebras and coalgebras are widely used to model data types in functional programming languages and proof assistants. Their use allow us to better structure computations by defining inductive data types such as integers, lists, etc., and coinductive data types such as streams – infinite lists -, and also to enhance the expressivity of a language or of a proof system. The use of algebras and coalgebras in proof assistants relies on the possibility of integrating them in strongly normalizing languages such as System F or the calculus of constructions without loosing the good logical properties of the calculus. In fact, in those systems it is possible to define weak (initial) algebras and weak (final) coalgebra by using parametric polymorphism.
In this work we study the problem of defining algebras and coalgebra in Light Linear Logic, a system characterizing the complexity class P. Due to the stratified nature of Light Linear Logic, we need to consider stratified versions of (weak) algebras and coalgebras. Thanks to these notions we are able to define standard algebraic and coalgebraic data types in our language.
11:15-11:30: Coffee break
11:30-12:20: Michel Grabisch
Title: On the vertices of the core of a game (with P. Sudhölter)
Abstract: The core of a capacity or a game v on N is the set of additive games dominating v and coinciding on N. It is an important concept both in decision theory (set of compatible probability measures) and in cooperative game theory (set of coalitionally rational payoff vectors). When nonempty the core is a convex bounded and closed polyhedron. When the game is supermodular, it is well known that the vertices of the core are the so-called marginal vectors of the game. However, when the game is not supermodular, there is no general result giving the vertices of the core.
Our aim is to investigate this problem in a more general framework, that is, when the game v is not defined on the entire Boolean lattice 2N but only on a distributive sublattice of it, generated by a partially ordered set on N, which can be interpreted as a hierarchy on N. We propose a way to produce vertices of the core based on particular orders on N inducing payoff vectors maximizing or minimizing the payoff given to the current player in N in the corresponding reduced game. We show however by a counterexample that this procedure cannot produce all vertices in general.
12:30-13:00: Bernardetta Addis
Title: Introducing implicit information in optimization methods: how to make smart a simple algorithm
Abstract: Many optimization problems arising from applications turn out to be very challenging, either for their large size or for their complex structure. Whenever some nice properties can be proved, specialized optimization methods can be devised to solve these problems exactly. Nevertheless, many interesting optimization problems cannot be characterized by strong enough properties to develop exact algorithms to solve them. Still, some information on the problem exists, even if such information cannot be expressed in mathematical form. Efficient heuristic algorithms can therefore be tailored exploiting such information in the search process. In this talk, this idea will be illustrated using several global optimization problems as examples.
13:00-14:30: Lunch
14:30-15:20: Jilles Vreeken
Title: Discovering the Composition
Abstract: The goal of exploratory data analysis — or, data mining — is making sense of data. We develop theory and algorithms that help you understand your data better, with the lofty goal that this helps formulating (better) hypotheses. More in particular, our methods give detailed insight in how data is structured: characterising distributions in easily understandable terms, showing the most informative patterns, associations, correlations, etc.
My talk will consist of three parts. I will start by explaining what is a pattern composition. Simply put, databases often consist of parts, each best characterised by a different set of patterns. Young parents, for example, exhibit different buying behaviour than elderly couples. Both, however, buy bread and milk. A pattern composition jointly characterises the similarities and differences between such components of a database, without redundancy or noise, by including only patterns that are descriptive for the data, and assigning those patterns only to the relevant components of the data. In the second part of my talk I will go into the more important question of how to discover the pattern composition of a database when all we have is just a single database that has not yet been split into parts. That is, we are after that partitioning of the data by which we can describe it most succinctly using a pattern composition. In the third part I will make the connection to causal discovery, as in the end that is our real goal.
15:30-16:00: Esther Galbrun
Title: An introduction to Redescription Mining
Abstract: In scientific investigations data oftentimes have different nature. For instance, they might originate from distinct sources or be cast over separate terminologies. In order to gain insight into the phenomenon of interest, a natural task is to identify the correspondences that exist between these different aspects. This is the motivation behind redescription mining, a data analysis task that aims at finding distinct common characterizations of the same objects. In this talk I will give an overview of redescription mining, from the intuition behind the concept and its links to existing data analysis techniques to more recent developments in pattern languages, algorithms and applications.
16:00-16:30: Coffee break
16:30-17:20: Alexis Tsoukiàs
Title: What is a decision problem?
Abstract: TBA
17:30-18:00: Nazim Fatès
Title: Randomness as an ally in decision: the case of stochastic cellular automata
Abstract: At first sight, computer science and randomness does not seem to fit together well. If we take a « classical » view, algorithms are designed with a total control on their behaviour, step by step. Opposite to this view, the behaviour of biological organisms shows that they do not see randomness as an enemy to defeat, but as a source of benefits. We ask how to conciliate these two views: how can we use stochastic models in order to take advantage of their noise to perform robust computations?
Our talk aims at studying this question in the context of cellular automata. These models are formed of regular arrays of cells which interact in a local and decentralised way. We present few examples where we ask our systems to attain a consensus where all cells agree in their « answer » to a question. We show that in many cases, good solutions are difficult to obtain with deterministic models, but can be solved rather easily with stochastic models. We will then discuss to which extent such ideas can be useful for tackling problems of retrieving information in highly decentralised environments.
20:00: Dinner (TBA)