Department of
Knowledge Engineering

**
**

**
SIKS-DKE Colloquia**

**
2013**

Title: Learning and Compiling Finite-state Controllers for Resource Constrained
Applications

Speaker: **Marek Grzes**,
University of Waterloo, Waterloo, Canada.

When and Where:

Date: Tuesday, November 19, 2013

Time: 14:00-15:00

Room: 0.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: The practical motivation for this work is the fact that execution of
POMDP policies is resource demanding when small devices, such as mobile phones
or much smaller wearable devices, are considered. As long as such devices—phones
in particular—may have a sufficient amount of memory and a fast CPU, they are
usually running out of battery very fast. I will show some experiments on one of
the latest Nexus phones where finite-state controllers are both the fastest and
least energy consuming at the same time among POMDP policies that can be used in
practice—including policies executed in the cloud. Having this interesting,
practical motivation in mind, I will show our algorithmic contributions where we
study two ways of obtaining finite-state controllers for POMDPs: (1) A direct
optimization where the controller is learned using branch-and-bound and where,
among others, we propose new methods of speeding up the branch-and-bound search
through pruning of redundant (isomorphic) solutions. (2) The second method could
be seen as an example of “knowledge compilation” where standard POMDP policies,
represented as sets of alpha-vectors or any other policies—such as UCT-like
policies—can be compiled into an equivalent or even better (than the original
policy) finite-state controller.

Title: Recent Results on Cache-Oblivious Range Searching

Speaker: **Norbert Zeh**, Faculty
of Computer Science, Dalhousie University, Halifax, Canada

When and Where:

Date: Wednesday, November 13, 2013

Time: 16:00-17:00

Room: 0.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: The cache-oblivious model is an elegant model that enables the design
of efficient algorithms for multi-level memory hierarchies by designing
algorithms in the RAM model and analyzing them in the I/O model under the
assumption of an offline optimal paging strategy.
This keeps the analysis manageable but constrains the algorithm designer
considerably and, thus, raises the question whether important fundamental
results in the I/O model can be matched by cache-oblivious algorithms and data
structures. This talk presents a
number of positive and negative results that shed light on this question for 3-d
range searching problems. First, I
will sketch how to obtain an optimal linear-space approximate range counting
data structure for halfspace and dominance queries in 3-d.
Previously, no such result was known even in the pointer machine model,
despite concerted efforts in the community.
This immediately leads to cache-oblivious range reporting data structures
for the same query types with the optimal query bound but using log n more space
than their I/O-efficient counterparts.
The second result shows how to reduce the gap to \sqrt(\log n) for 3-d
dominance queries using a novel random sampling approach.
The third result shows that it is impossible to close the gap completely
by proving an Omega(n log^eps n) space lower bound for any cache-oblivious data
structure that achieves the optimal query bound.
This is the strongest separation result between the I/O model and the
cache-oblivious model to date.

This is joint work with Peyman Afshani (MADALGO, Aarhus) and Chris Hamilton (my
former PhD student, now at Google).

Title: Entity-based Data Science

Speaker: Dr.
Lise Getoor,
University of Maryland, College Park

When and Where:

Date:
Thursday, October 3, 2013

Time: 13:00-14:00

Room: 2.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: There is a growing interest in integrating, analyzing, visualizing and
making sense of large collections structured, semi-structured and unstructured
data. In the world of big
data, data science provides tools to help with this process – tools for cleaning
the data, tools for integrating and
aligning the data, tools for finding patterns in the data and making
predictions, and tools for visualizing and interacting with the data.
In this talk, I will focus on entity-based data science, data science
techniques which support the analysis of networks of related entities.
I will introduce the tasks of entity resolution (determining when two
references refer to the same entity), collective classification (predicting
missing entity attributes in the network), and link prediction (predicting
relationships) and describe holistic approaches that take into account both
entity attributes and relationships among the entities.
I will overview of our recent work on probabilistic soft logic (PSL), a
framework for collective, probabilistic reasoning in relational domains.
Our recent results show that by using state-of-the-art optimization
methods in a distributed implementation, we can solve large-scale problems with
millions of random variables orders of magnitude more quickly than existing
approaches.

Title: Algorithms for uncovering the structure of complex stochastic networks

Speaker: Dr. **Nelly Litvak**,
Department of Applied Mathematics, University of Twente

When and Where:

Date: Thursday,
October 10, 2013

Time:
16:00-17:00.

Room: 0.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: Abstract: I will discuss several problems in the analysis of large
complex networks such as the world wide web and on-line social networks. The
analysis of the structure of these networks has many important applications. A
most prominent example is the Google PageRank that was invented to determine the
relevant web search results. I will first address the problem of finding
quickly the top k nodes with the largest degrees when the structure of the
network in unknown, as, for example, in Twitter. We propose a randomized
algorithm that finds the top degree nodes in the time, which is sublinear in the
network size, thus enabling computational savings of orders of magnitude. The
second problem is about measuring dependencies between degrees of neighbouring
nodes. It turns out that the commonly used Pearson’s correlation coefficient
decreases in magnitude with the network size. This makes it impossible to
compare the structure, for example, of two web crawls of different sizes. We
introduce an alternative degree-degree dependency measure, based on the
Spearman's rho, and demonstrate its convergence to an appropriate limit,
analytically and on the data. If time permits, I will also discuss an
interesting stochastic process, a so-called cat-and-mouse Markov chain, that
naturally arises from the analysis of an on-line method for PageRank
computation. The cat performs a Markov random walk, and the mouse moves only
when found by the cat. We derive asymptotic properties of this process and
obtain its very unusual scaling behaviour in case when the cat component behaves
as a simple reflected random walk on non-negative integers.

Title: Coordinating Multi-Agent Learners

Speaker: Professor Dr.
Victor Lesser,
University of Massachusetts, USA.

When and Where:

Date: Friday,
October 11,
2013

Time: 13:30-15:00

Room: 0.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: Multi-agent reinforcement learning (MARL) provides an attractive,
scalable, and approximate approach for agents to learn coordination policies and
adapt their behavior to the dynamics of the uncertain and evolving environment.
However, for most large-scale applications involving hundreds of agents, current
MARL techniques are inadequate. MARL may converge slowly, converge to inferior
equilibria, or even diverge in realistic settings. There are no known
distributed approaches that guarantee convergence without either very
constraining assumptions about the learning environment and the knowledge at
each agent or intractable amounts of computation and communication. These
assumptions do not hold in most realistic applications. In this lecture, I will
overview my group’s work over the last five years in melding multi-agent
coordination technology with more complex single agent reinforcement learning
for scaling MARL to large agent networks. This discussion will include the use
of non-local multi-level supervisory control to coordinate and guide the agents’
learning process, the use of approximate DCOP algorithms for peer-to-peer
learning coordination, the use of conflict resolution detection to dynamically
expand the policy space of an agent so as to incorporate additional non-local
information, and increasing the sophistication of local agent learning through
policy prediction and multiple learning contexts. This is joint work with
Chongjie Zhang, Sherief Abdallah, and Bruno Castro da Silva together with Anita
Raja and Shanjun Cheng from University of North Carolina Charlotte.

Title:
The angry birds AI competition

Speaker: Dr. **Daniel Hennes**,
European Space Agency, Noordwijk

When and Where:

Date:
Monday, September 30, 2013

Time:
14:30-15:30

Room: 0.015

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract:
Angry Birds (Rovio™) is a popular artillery game where the player's task is to
shoot birds from a slingshot at a structure that houses pigs. In this talk, I
will give an overview of the second Angry Birds AI competition held at the 2013
International Joint Conference on AI in Beijing. I will start with a brief
introduction of the basic game playing framework provided by the organizers. The
framework makes use of the Chrome version of Angry Birds and includes a computer
vision, trajectory planning and game interface component. I will highlight
different agent approaches taken by participating teams and review results.
Finally, I will describe our agent that combines various techniques from
evolutionary optimization and scored second place during the 2013 competition.

Title: The interplay of infectivity that decreases with virulence and limited
cross-immunity: (toy) models for respiratory disease evolution.

Speaker: Prof. Dr.
Hans Metz, International
Institute for Applied Systems Analysis, Austria

When and Where:

Date: Wednesday, June 26, 2013

Time: 13:00-14:00

Room: 0.009

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: Standard models for the evolution of virulence traditionally assume a
trade-off between inverse disease-induced mortality rate and infectivity,
resulting in intermediate virulence. The underlying intuition is that faster
growing agent populations do both more damage and produce more infective
particles. This intuition implicitly assumes a well-mixed host body. In reality
both damage and infectivity depend mainly on the location in the body where the
agents lodge. This is related i.a. to the surface proteins that allow agents to
dock on and penetrate into different cell types. The typical example is
respiratory diseases where more deeply seated ones are both less infective and
more harmful. With the other standard assumption, full cross-immunity between
disease strains, this would lead to evolution towards the tip of the nose. In
reality cross-immunity depends on surface antigens and hence is at least in part
connected to depth. In this talk I discuss a simple adaptive dynamics style
model taking on board the aforementioned considerations. In doing so I will also
shortly review salient aspects of the adaptive dynamics toolbox. Some tentative,
probably robust, biological conclusions are (1) higher host population densities
are conducive to a higher disease diversity, (2) disease diversity should be
higher in the upper air passages than lower in the lungs, (3) emerging
respiratory diseases will usually combine a high virulence with a low
infectivity.

Title: Communication Network Formation with Valuation Heterogeneity

Speaker:
Dr. drs. Marjolein Harmsen - van Hout,
RWTH Aachen University

When and Where:

Date: Wednesday, April 10, 2013

Time: 16:00-17:00

Room: 0.009

Location: Maastricht University, Department of Knowledge Engineering,
Bouillonstraat 8-10

Abstract: In Harmsen – van Hout et al.
(forthcoming in EJOR) we proposed a model on strategic formation of
communication networks among homogeneous agents. In this talk, I will summarize
this model, its applicability, and the results we derived from it by analysis
and simulations. Accordingly, I will introduce my work in progress in which the
model is extended as to allow for heterogeneity among agents. I will give an
overview of the results derived so far, after which there will be room for
discussion about what further results would be most interesting.

Title:
Riskiness

Speaker: Prof. Dr. **Sergiu Har**t,
Center for Rationality, Hebrew University, Jerusalem.

When and Where:

Date: Monday, 14 January, 2013

Time: 14:00-15:00

Room: H0.06 at Tongersestraat 53 (room opposite the former aula), Maastricht
University.