Report on MASCOS One-Day Symposium

Multi-Agent Systems and Machine Learning

The University of Queensland
Friday 26th November 2004

General   The fields of probability and statistics, computer science and information technology are becoming increasingly intertwined. A major driving force is the fast growing development and application of new probabilistic and information theoretical approaches to solve complex problems in a wide rage of areas. Applications can be found everywhere: in information technology, applied probability and statistics, engineering, biotechnology, management science, computational science, financial mathematics, economics, physics, machine learning and artificial intelligence.

This workshop, sponsored by the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS) and the University of Queensland School of Physical Sciences, brought together researchers and students working in the general area of Multi-Agent systems. There were 45 participants, from Academia, Government and Industry.

Invited speakers

• Andre Costa (MASCOS, University of Melbourne)
• Kelly Fleetwood (University of Queensland)
• Michael Gagen (IMB, University of Queensland)
• Marcus Gallagher (University of Queensland)
• Jonathan Keith (University of Queensland)
• Dirk Kroese (University of Queensland)
• Alex Smola (NICTA, ANU)
• Thomas Taimre (MASCOS, University of Queensland)

[There were no contributed papers]

Venue   Room 141, Priestley Building (Building 67), St Lucia Campus, University of Queensland

Organizers   Dirk Kroese (University of Queensland) and Phil Pollett (MASCOS, University of Queensland)

Programme  

	08:45	-Registration-
	09:00	Andre Costa	Exploration, robustness and optimality of network routing algorithms which employ "ant-like" mobile agents
	10:00	Kelly Fleetwood	An introduction to differential evolution
	10:30	-Break-	[Refeshments provided]
	10:45	Michael Gagen	Non-myopic multi-player optimization with application to the iterated prisoner's dilemma
	11:15	Dirk Kroese	The Cross-Entropy Method and mathematical programming
	12:15	-Lunch Break-	[Lunch provided (barbeque)]
	13:30	Alex Smola	Exponential families in feature space
	14:30	Jon Keith	Sequence alignment by rare event simulation
	15:00	-Break-	[Refeshments provided]
	15:15	Marcus Gallagher	Explicit modelling in metaheuristic optimization
	15:45	Thomas Taimre	Application of the Cross-Entropy Method to clustering and vector quantization
	16:15	-Close-

Abstracts

• Andre Costa

  Exploration, robustness and optimality of network routing algorithms which employ "ant-like" mobile agents

  Abstract: Interest in adaptive and distributed systems for routing control in networks has led to the development of a new class of algorithms, which is inspired by the "emergent" shortest path finding behaviours observed in biological ant colonies. This class utilizes ant-like agents, which autonomously traverse the network and collectively construct a distributed routing policy. Agent-based routing algorithms belonging to this class do not require a complete model of the network, and are able to adapt autonomously to network changes in dynamic and unpredictable environments. Some important aspects and limitations of this class of algorithms can be modelled and understood in the context of Markov decision problems, reinforcement learning, and game theory. We present an analytic modelling approach for agent-based routing algorithms, and in particular, we discuss the effect that randomized exploration strategies can have on the routing policies that are generated by the agents.

  [talk]

• Kelly Fleetwood

  An Introduction to Differential Evolution

  Abstract: Differential Evolution (DE) was introduced in 1996 by Price and Storn. It is a stochastic, population-based optimisation method that belongs to the class of Evolutionary Algorithms. It can be used to minimise real, integer, discrete and mixed parameter functions and it has recently been applied to problems in engineering, chemistry and agriculture. On classic optimisations test problems it has been shown to be more efficient than annealing methods and genetic algorithms. This talk provides a thorough introduction to the basic Differential Evolution algorithm including an example of its performance.

  [talk|movie]

• Michael Gagen

  Non-myopic multi-player optimization with application to the iterated prisoner's dilemma

  Abstract: In 1944, von Newmann and Morgenstern formalized the functional optimization algorithms used in game theory, economics and artificial intelligence. They did this by (essentially) borrowing the functional optimization methods used in physics where, for instance, actions are minimized under the assumption that Lagrangians are continuous and differentiable and functionals of uncorrelated fields to avoid non-local outcomes. In developing their strategic economic optimization algorithms, von Newmann and Morgenstern likewise assumed that the functionals to be optimized were continuous and differentiable and uncorrelated. This is essentially the myopic agent assumption. However, economic rational players are not electrons, and can exploit correlations to render their optimization space non-continuous and non-differentiable. In this work, we drop the myopic assumption arbitrarily imposed by von Neumann and Morgenstern, and demonstrate that non-myopic optimization leads to rational cooperation in the iterated prisoner's dilemma in contrast to myopic optimization outcomes insisting that defection is the sole rational choice of play.

  [talk]

• Marcus Gallagher

  Explicit modelling in metaheuristic optimization

  Abstract: Statistical modelling and Machine Learning methods have seen some application to solving optimization problems. In general, this involves explicitly modelling the data produced by a search algorithm, and using the model (e.g) to increase the speed of the search, to find better solutions, or to gain insight into the problem by examining the model produced. In the field of Metaheuristics (inc. Evolutionary Computation), density estimation techniques and probabilistic graphical models have been used to perform model-based optimization. This work is usually referred to as Estimation of Distribution Algorithms (EDAs). Model-based optimization has also been considered outside the machine learning community (e.g, using response surfaces).

  In this talk I will mention briefly some of the existing approaches in learning-based optimization algorithms. In particular, I will describe the mechanisms of some well-known EDAs. I will also mention one approach to constructing a framework for EDAs, based on minimization of the KL-divergence between the model (probability distribution) and a distribution that depends on the objective function of the optimization problem.

  [talk]

• Jonathan Keith

  Sequence alignment by rare event simulation

  Abstract: I present a new stochastic method for finding the optimal alignment of DNA sequences. The method works by generating random paths through a graph (the edit graph) according to a Markov chain. Each path is assigned a score, and these scores are used to modify the transition probabilities of the Markov chain. This procedure converges to a fixed path through the graph, corresponding to the optimal (or near-optimal) sequence alignment. The rules with which to update the transition probabilities are based on the Cross-Entropy Method, a new technique for stochastic optimization. This leads to very simple and natural updating formulas. Due to its versatility, mathematical tractability and simplicity, the method has great potential for a large class of combinatorial optimization problems, in particular in biological sciences.

  [talk]

• Dirk Kroese

  The Cross-Entropy Method and mathematical programming

  Abstract: Many practical problems in Science involve solving complicated mathematical programming questions, including multi-extremal continuous, mixed-integer and constrained optimisation problems. The Cross-Entropy (CE) method [1] gives a versatile and powerful new approach to solving these problems.

  In this talk I will explain how the CE method works. I will start with a simple example in rare event simulation, which will explain the concept of cross-entropy and motivate the optimisation idea behind the CE method. I will then illustrate the simplicity and elegance of the method through various easy examples in continuous multi-extremal and combinatorial optimisation.

  [1] Rubinstein, R.Y. and Kroese, D.P. (2004) The Cross-Entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation and Machine Learning, Springer-Verlag, New York.

  [talk]

• Alex Smola

  Exponential families in feature space

  Abstract: In this talk I will discuss how exponential families, a standard tool in statistics, can be used with great success in machine learning to unify many existing algorithms and to invent novel ones quite effortlessly. In particular, I will show how they can be used in feature space to recover Gaussian Process classification for multiclass discrimination, sequence annotation (via Conditional Random Fields), and how they can lead to Gaussian Process Regression with heteroscedastic noise assumptions.

  [talk]

• Thomas Taimre

  Application of the Cross-Entropy Method to clustering and vector quantization

  Abstract: We apply the Cross-Entropy (CE) method to problems in clustering and vector quantization. Through various numerical experiments we demonstrate the high accuracy of the CE algorithm and show that it can generate near-optimal clusters for fairly large data sets. We compare the CE method with well-known clustering and vector quantization methods such as K-means, fuzzy K-means and linear vector quantization. Each method is applied to benchmark and image analysis data sets for this comparison.

  [talk]