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 Hart, 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.