Seminars

Forthcoming Seminars – Spring Term 2012

All seminars take place on Wednesday's at 4.00pm (unless otherwise stated).

Locations will be given in the Seminar details.

25th January - Geometric Semantic Genetic Programming
1st February - The Formal Characterisation of Socio-Economic Principles for Self-Organising Electronic Institutions
9th February (Thursday) - Computation of the Shapley Value for Centrality in Networks
15th February - Temporal Dynamics of Social and Technological Networks
22nd February - NO SEMINAR
29th February - NO SEMINAR
7th March - Game Competitions at Essex: Designing AI Controllers to play Ms PacMan and the Physical Travelling Salesman Problem
14th March - Artificial Stock Market with Crisp and Fuzzy Kalman Filtering Q-Learning Traders
21st March - Link Prediction based on Subgraph Evolution in Dynamic Social Networks

25th January 
Speaker: Alberto Moraglio (School of Computer Science, University of Birmingham, UK, albmor@gmail.com)
Title: Geometric Semantic Genetic Programming
Location: 1N.1.4.1
Abstract:

Traditional Genetic Programming (GP) searches the space of functions/programs by using search operators that manipulate their syntactic representation (eg, parse trees), regardless of their semantic.  Recently, semantically aware search operators have been shown to outperform purely syntactic operators.  In this work, using a formal geometric view on search operators and representations, we bring the semantic approach to its extreme consequences and introduce a novel form of GP - Semantic GP (SGP) - that searches directly the space of the underlying semantic of the programs.  This perspective provides new insights on the relation between syntax, semantic, search operators and fitness landscape, and allows for the principled formal design of semantic search operators for different classes of problems.  We derive specific forms of SGP for a number of classic GP domains and report preliminary experimental results.  Furthermore, we show that the search of SGP is equivalent to the search of a traditional Genetic Algorithm on the One-Max problem.

1st February  
Speaker: Jeremy Pitt (Department of Electrical & Electronic Engineering, Imperial College London, j.pitt@imperial.ac.uk)
Title: The Formal Characterisation of Socio-Economic Principles for Self-Organising Electronic Institutions
Location: LTB 9
Abstract: We address the problem of deciding resource allocation policies in open embedded systems, whereby the system components have to form an opportunistic alliance and collectively agree a policy that is congruent with the state of the environment in which the system is embedded.  This problem  arises in a number of systems and applications, including sensor networks, cloud computing, and infrastructure management for water, energy, and transport.  We begin be presenting a methodology for the formal characterisation and operationalisation of social science theories in a computationally tractable framework.  We apply the methodology to Ostrom's socio-economic principles for self-governing institutions, demonstrating how the institutional rules can be represented in a framework for specifying dynamic norm-governed systems.  We then show how
six out of eight of Ostrom's principles can be given a formal characterisation through an axiomatisation in the Event Calculus, an action language from artificial intelligence used for representing and reasoning about agency, action and change.  Finally we examine three propositions: that open, embedded and resource-constrained systems can be considered from the perspective of institutions for management of common pool resources (CPR); secondly, that socio-economic principles for enduring institutions can formally characterised and operationalised as norm-governed systems; and thirdly that such an axiomatisation can be used as a basis for systematic experiments to test whether these principles are necessary and sufficient conditions for enduring electronic institutions.
Biography: Jeremy Pitt is Reader in Intelligent Systems in the Department of Electrical & Electronic Engineering at Imperial College London, where he is also Deputy Head of the Intelligent Systems & Networks Group, Director of the Information Systems Engineering course, and an Associate Director of Institute for Security Science and Technology.  His research interests focus on the foundations and applications of computational logic in multi-agent systems, in particular agent societies, agent communication languages, and self-organising electronic institutions.  He has been an investigator on more than 30 research projects and has published more than 150 articles in journals and conferences.  He is a Senior Member of the ACM, a Fellow of the BCS, and a Fellow of the IET, and is on the editorial board of ACM TAAS.

9th February (Thursday)
Speaker: Tomasz Michalak (Institute of Informatics, University of Warsaw)
Title: Computation of the Shapley Value for Centrality in Networks
Location: LTB 4 
Abstract: The Shapley Value is arguably the most important normative solution concept in coalitional games.  One of its applications is in the domain of networks, where the Shapley Value is used to measure the relative importance of individual nodes.  This measure, which is called node centrality, is of paramount significance in many real-world application domains including social and organisational networks, biological networks, communication networks and the internet.  Whereas computational aspects of the Shapley Value have been analyzed in the context of conventional coalitional games, this paper presents the first such study of the Shapley Value for network centrality.  Our results demonstrate that this particular application of the Shapley Value presents unique opportunities for efficiency gains, which we exploit to develop exact analytical formulas for Shapley Value based centrality computation in both weighted and unweighted networks.  These formulas not only yield efficient (polynomial time) and error-free algorithms for computing node centralities, but their surprisingly simple closed form expressions also offer intuition into why certain nodes are relatively more important to a network.
 

15th February
Speaker: Mirco Musolesi (Department of Computer Science University of Birmingham, m.musolesi@cs.bham.ac.uk)
Title: Temporal Dynamics of Social and Technological Networks
Location: 1N.1.4.1
Abstract: The analysis of social and technological networks has attracted a considerable attention as social networking applications and mobile sensing devices have given us a wealth of real data about people interactions.  Classic studies looked at analysing static or aggregated networks, ie, networks that do not change over time or built as the result of aggregation of information over a certain period of time.  Given the soaring number of collections of measurements related to very large real network traces, researchers are quickly starting to realise that connections are inherently varying over time and exhibit more dimensionality than static analysis can capture.
We have recently proposed a novel theoretical framework to study this class of networks in order to quantify for example the speed/delay of information diffusion processes and structural properties, such as the presence of connected components.  We have showed how these metrics are able to capture the temporal characteristics of time-varying graphs, such as delay, duration and time order of interactions, compared to the metrics used in the past on static graphs.
In this talk I will give an overview of the proposed conceptual framework and I will present some initial ideas about the calculation of centrality metrics for characterising network robustness by means of matrix computations using the transformation of temporal graphs into reachability graphs.
More information about my research work and interests can be found in my homepage: http://www.cs.bham.ac.uk/~musolesm/

22nd February - NO SEMINAR

29th February - NO SEMINAR

 
7th March
Speaker: Philipp Rohlfshagen
Title: Game Competitions at Essex: Designing AI Controllers to play Ms PacMan and the Physical Travelling Salesman Problem
Location: 1N.1.4.1
Abstract: Video games are amongst the fastest growing industries in the world but despite significant advances in level design, graphics and sounds, the game-AI used remains relatively simplistic: the majority of blockbuster games rely on hand-coded rule-based systems, finite state machines and behaviour trees.  Although more advanced approaches such as planning are now used more widely, other techniques such as evolutionary algorithms, neural networks or temporal difference learning remain largely untouched.  The significant trend towards online gaming where human players compete against one another rather than AI-controlled characters highlights the need for more sophisticated game-AI.
To allow researchers to test and evaluate novel AI techniques in the realm of real-time video games, we have been organising game competitions at various international conferences in recent years: the "Ms. Pac-Man vs Ghost Team Competition" requires participants to write AI controllers for either Ms. Pac-Man or the ghosts in the classical arcade game Ms. Pac-Man.  The Physical Travelling Salesman Problem, which we are organising for the first time this year, is a single-player game based loosely on the well-known game "Asteroids".  Here one needs to navigate a ship through numerous obstacles to reach a series of waypoints as quickly as possible.
We have had a great deal of interest in these competitions in recent years as well as several enquiries for our frameworks to be used as tools for teaching and assessment in various AI university courses.  We would like to attract a similar degree of interest from the University of Essex.  In this talk I will demonstrate how to use the open-source software that is distributed with the competitions and will focus on creating simple yet fully functional controllers for both games.

14th March
Speaker: Irakli Gogatishvili (University of Torino, i.gogatishvili@unito.it)
Title: Artificial Stock Market with Crisp and Fuzzy Kalman Filtering Q-Learning Traders
Location: LTB 9
Abstract: Current work proposes two new types of Q-learning (QL) robotic traders for high-frequency stock market: (1) QL Crisp Kalman Filtering (QL-CK) and (2) QL Fuzzy Kalman Filtering (QL-FK) agents.  Kalman QL-s (QL-K) use Unscented Transform Kalman Filter (UTKF) algorithm to approximate value function.  QL-FK-s regard observations and state estimates as fuzzy variables.  QL-K-s are expected to perform better, than QL.  Their advantage should be more realistic apprehension of states, hence higher quality of learning and more precise predictions.  Comparison between the QL-CK and QL-FK is also a crucial objective.  Simulated data should be controlled for self-fulfilling forecasting.  Simulation script is developed in Python using SLAPP (Swarm-Like Agent Protocol in Python).  For data analysis and visualization it integrates R libraries (via RPy2, i.e. Python interface to the R Programming Language).

21st March
Speaker: Katarzyna Musial - Kings College London
Title: Link Prediction based on Subgraph Evolution in Dynamic Social Networks
Location: 1N.1.4.1
Abstract: We propose a new method for characterizing the dynamics of complex networks with its application to the link prediction problem.  Our approach is based on the discovery of network subgraphs (in this study: triads of nodes) and measuring their transitions during network evolution.  We define the Triad Transition Matrix (TTM) containing the probabilities of transitions between triads found in the network, then we show how it can help to discover and quantify the dynamic patterns of network evolution.  We also propose the application of TTM to link prediction with an algorithm (called TTM-predictor) which shows good  performance, especially for sparse networks analyzed in short time scales.  The future applications and research directions of our approach are also proposed and discussed.