Department of
Knowledge Engineering

SIKS-DKE Colloquia

2010

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.

__Abstract:
__
In
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

__Abstract:
__
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

__Abstract:
__
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.