Department of Knowledge Engineering


SIKS-DKE Colloquia


December 15, 10:30
Cees Witteveen, TU Delft
Decomposition of Constraint Systems: Three equivalent perspective
Abstract:  Decomposition is a technique to split a problem in a number of parts such some global property of the problem can be obtained or preserved by independent, distributed, processing of parts of the problem. Decomposition has been used in the database and constraint community to allow distributed parties to find solutions for a set of constraints or to modify a set of constraints independently from each other. We consider the complexity of finding suitable decompositions in constraint systems distinguishing different decomposition aims. One such an aim, especially popular in the artificial intelligence community, is finding solutions for constraint systems by distributed computations. Decomposition then should preserve solutions, that is local solutions should be mergeable to a global solution. Another aim, often encountered in the database community, is to be able to preserve consistency while allowing each party to add arbitrary local constraints to its local constraint store. We show that contrary to intuition these two modes do not differ from each other. Furthermore, we address some computational complexity results w.r.t. finding solutions for constraint systems by applying decomposition techniques.

December 15, 11:15
Tristan Cazenave, Université Paris-Dauphine
Single Player Monte-Carlo Tree Search
Abstract:  Monte-Carlo Tree Search has recently been very successful for game playing particularly for games where the evaluation of a state is difficult to compute, such as Go or General Games. In this talk I compare Nested Monte-Carlo Search (NMC), Upper Confidence bounds for Trees (UCT-T), UCT with transposition tables (UCT+T) and a simple combination of NMC and UCT+T (MAX) on single-player games of the past GGP competitions. I show that transposition tables improve UCT and that MAX is the best of these four algorithms. Using UCT+T, the program Ary won the 2009 GGP competition. MAX and NMC are slight improvements over this 2009 version.

November 16, 11.00
Oleg Okun
High Dimensional, Small Sample Size Data Classification Using Advanced Machine Learning Methods
Abstract:  In this talk, I will present my latest research on one of the main machine learning tools – classifier ensembles - when applied to challenging problems where the number of features far exceeds the number of available data instances. The main messages of the talk include a simple yet powerful ensemble generation technique and low bias, low variance technique for assessment of classification error.
The practical application where both messages were successfully delivered is cancer classification.

October 6, 14:00
Frank Bruggeman, CWI and UvA, Amsterdam
Theory for optimal responses of metabolic pathways
Abstract:  Upon environmental changes organisms display a remarkable capacity to adapt.
Upon detection and processing of the environment dynamics, protein activities are adjusted through changes in protein levels, allosteric regulation, and levels of reactants. In this work, we develop a number of theoretical approaches and concepts for understanding of experimental data on adaptive changes and for predicting adaptations of metabolic pathways.

July 15, 10:00
Avi Shmida, Hebrew University of Jerusalem
Flowers and Sex; can we learn something from game theory?
Abstract:  We will go out to some nice natural spots in Maastricht, where we will discuss the topic by means of the flowers we encounter.
First station: The garden on the city wall near the Faculty of Economics, Stadspark.
Second and main station, arrival around 10.45: Jekerdal Gardens (CNME), Drabbelstraat 7.
Wear comfortable shoes and bring water for it may still be quite warm.


June 16, 16:00
Laurent Bako, Ecole des Mines de Douai and Universite de Lille
Identification of switched linear systems: a sparse optimization approach

Abstract:  A switched dynamical system consists of a finite set of interacting linear or nonlinear subsystems. The interaction of the constituent subsystems is made possible by a supervisory switching signal that can be exogenous, state-driven, event-driven, time-driven, deterministic, or even totally random. This talk will concern the identification of switched linear systems from input-output data. The main challenge with this problem lies in the fact that the collected measurements are available only as a mixture of observations generated by different subsystems. That is, since the switching signal is unknown, one does not know a priori which subsystem has generated which data.
To overcome this difficulty, we present in this work a sparse optimization approach inspired by very recent developments from the community of compressed sensing. The application of the proposed method does not require any prior classification of the data according to their respective generating-submodels. We formally pose the problem of identifying each linear as a combinatorial L0 norm optimization problem that fits all the data to a single parameter vector. However as such, the problem is known to be NP-hard. Nevertheless it can be interestingly relaxed into a convex L1-norm minimization problem. Applying this idea leads to a final algorithm that allows us to extract one after another, the parameter vectors associated with the different subsystems, by means of convex optimization.


June 15, 16:00
Michel Grabisch,  Sorbonne Economic Centre, Université Paris 1 (Panthéon-Sorbonne)
A coalition formation value
Abstract:  Coalition formation is an important topic related to game theory, multi-agent systems and economics. Supposing that coalitions earn some benefit or pay some cost for using goods or services, a central problem is how to determine the allocation of the benefit or cost among all participating players/agents. Our talk will consist of two parts, dealing with two particular situations. We put N, the set of all players, of cardinality n.
The first part considers the case of games with externalities, best modelled under partition function form game: it is assumed that the worth of a coalition depends on the organization of the society of the remaining players. Furthermore, we suppose that the starting point is the society of all individual players (no coalition is formed), and that step by step this society evolves till attaining the grand coalition (all players are in a single coalition). We introduce the notion of scenario and process. A process is a sequence of partitions  of players, starting from the finest partition (the society of all individual players) and finishing at the coarsest partition, that is, the set of players itself, and between two steps, there is one and only one merging of two blocks of the current partition. Each process gives rise to n scenarios, one per player, which are simply the process under the viewpoint of a given player. The original point of our approach is to define a value for scenarios, considered as an elementary brick, then from this a value for process, and finally for the game itself. We propose two axiomatizations of the scenario value, reflecting well the idea of coalition formation.
In the second part, we do not consider externalities, but coalitions can be formed completely freely. That is, the sequence of coalitions is arbitrary, and in particular need not be a chain.  The model behind  this is  a  Markovian approach of coalition formation,  i.e., coalitions are viewed as states  and therefore from the transition matrix, we can compute for each sequence of coalitions its probability of occurrence.  Such sequences with positive probabilities correspond to scenarios of the first part. We define a value for scenarios, and the value of the game under a given Markov process is the expectation of all scenario values. We give also axiomatizations of the scenario value.


June 9, 16.00
Bettina Klaus, Department of Economics, University of Lausanne, Switzerland
Allocation via Deferred-Acceptance under Responsive Priorities.
n many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource-monotonicity with two-agent consistent conflict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.


May 19, 16:00
Frank Bruggeman, Centrum voor Wiskunde en Informatica, Amsterdam
Cells play dice!
Abstract:  Upon environmental changes organisms display a remarkable capacity to adapt.
Upon detection and processing of the environment dynamics, protein activities are adjusted through changes in protein levels, allosteric regulation, and levels of reactants. In this work, we develop a number of theoretical approaches and concepts for understanding of experimental data on adaptive changes and for predicting adaptations of metabolic pathways.

May 10, 16:00
Bruno Bouzy, LIPADE - UFR de mathematiques et d'informatique, Universite Paris Descartes
Multi-Agent Learning and Repeated Matrix Games.
Abstract:  This talk presents a work in the field of multi-agent learning (MAL) by using repeated matrix games (RMG). In a first part, basic game theory concepts such as one-shot matrix game, correlated and Nash Equilibria are presented. A second part lists the main approaches of MAL algorithms playing RMG. Then a third part describes experiments to evaluate MAL playing repeated matrix games. Previous works assessed that Q-learning surpassed Nash-based MAL algorithms. Our work shows that M-Qubed, S and bandit-based algorithms such as UCB are the best algorithms on general-sum games, Exp3 being the best on cooperative games and zero-sum games. Moreover, our experiments show that two features - forgetting the far past, and using recent history with states - improve most of the algorithms. Finally, the best algorithms are Q-learning and UCB, enhanced with the two features, and M-Qubed.

April 28, 16:00
Pieter Collins, Centrum voor Wiskunde en Informatica, Amsterdam
Computational Analysis of Nonlinear Hybrid Systems.
Abstract:  In this talk I will give an overview of the tool Ariadne for reachability analysis and verification of nonlinear and hybrid systems.
This is especially an important problem for embedded systems, where software-driven devices need to interact with a physical environment.
Among other issues, I will discuss the data structures for describing numbers, functions, sets and systems, the main computational sub-problems and the algorithms used for each one. I will also indicate how the capabilities of the tool might be used to study other questions about dynamical systems, with some examples from systems biology.

April 9, 14:00
Kurt Driessens, Department of Computer Science, K.U. Leuven
Modularity in reinforcement learning using functional gradient boosting.
Abstract:  In this talk I will present non-parametric policy gradients and illustrate the opportunity they provide for learning and re-using modular policies in model-free reinforcement learning. Non-parametric policy gradients use functional gradient boosting to avoid the need for a fixed parameterization that is standard in typical policy gradient learning techniques. By representing the learned policy using the sum of arbitrary potential functions, it becomes possible to join multiple representation and generalization techniques into a single gradient-based policy search algorithm. In theory, this makes it simple to produce and re-use partial potential functions (and thus partial policies) that can be combined to address non-disjoint goals.
I will introduce a test-bed proposal based on stunt-kite control which would allow to test, verify and illustrate the applicability of this type of autonomous incremental learning and its possibly beneficial combination with learning from demonstrations.


January 25, 16.00
Robert P. Gilles, Queen's University Belfast, UK
Partial Cooperation and Pollution Abatement: A Game Theoretic Approach
We consider a normal form game in which there is a single coalition of cooperating players who can write a binding agreement. The coalition under consideration only writes a binding agreement with regard to a particular (collective) action, while the other actions remain under the complete, individual control of the players. Two equilibrium concepts are developed and analyzed.
First, we extend the standard Nash equilibrium to this case of partial cooperation in which all players and the coalition of cooperators make simultaneous decisions. Second, we consider a leadership equilibrium in which the coalition of cooperators writes a contract concerning the collective action before all players decide about their individual choices. The latter extends a similar concept developed by Malozzi and Tijs. For both equilibrium concepts we provide existence theorems.
We apply this game theoretic framework to the issue of pollution abatement. We consider the development of green production technologies under sharing agreements. We consider Nash equilibrium as well as the two newly introduced equilibrium concepts to analyze the adoption of green production technologies.


January 25, 14:00
Michael Rovatsos, University of Edinburgh, UK
Towards a "Strategic" Web
Strategic reasoning and decision making, i.e. reasoning in environments in which one is interacting with other agents who may have conflicting views or objectives, is ubiquitous in large-scale multiagent environments such as the Web. Yet, in the current Web landscape, users are not supported by existing Web technologies in the process of managing their strategic interactions, and this constitutes a major technological barrier to better exploitation of  the "strategic layer" of the Web.
In this talk, I will present a vision of what could be termed the "Strategic" Web, i.e. knowledge-based methods based on multiagent systems, AI planning, and game theory that may have the potential of scaling up sufficiently well to be used in real-world applications in complex domains of strategic interaction.
I will present some recent contributions, both from our own work as from the literature that give a flavour for the kinds of techniques that could be relevant, and discuss the main challenges of potential future work.