Publications by Marcus Frean

Note: any documents you can download from this page should be assumed to be late drafts of the published papers. Otherwise email me and I can send reprints of anything here. Papers are divided into those on machine learning and neural computation, on theoretical biology, and others .

others

Software Graphs and Programmer Awareness

Gareth Baxter and Marcus Frean
Submitted , 2008.

Dependencies between types in object-oriented software can be viewed as directed graphs, with types as nodes and dependencies as edges. A programmer working on a node is almost certainly more aware of its out-degree, which is immediately evident, than its in-degree, which is not. This fundamental asymmetry of information is reflected in the software graph in the large, with the in-degree and out-degree distributions of such graphs having quite different forms; the former resembles a power-law distribution and the latter an exponential distribution. We give a simple generative model for software graphs that essentially ignores all aspects of programmer behaviour and software functionality other than this asymmetry of awareness, and show that it reproduces the in-degree and out-degree distributions observed across 14 different type relationships spanning 12 large and varied Java applications.

Understanding the Shape of Java Software

Gareth Baxter, Marcus Frean, James Noble, Mark Rickerby, Hayden Smith, Matt Visser, Hayden Melton and Ewan Tempero
OOPSLA , 2006.

Large amounts of Java software have been written since the language's escape into unsuspecting software ecology more than ten years ago. Surprisingly little is known about the structure of Java programs in the wild: about the way methods are grouped into classes and then into packages, the way packages related to each other, or the way inheritance and composition are used to put these programs together. We present the results of the first in-depth study of the structure of Java programs. We have collected a number of Java programs and measured their key structural attributes. We have found evidence that some relationships follow power-laws, while others do not. We have also observed variations that seem related to some characteristic of the application itself. (etc...)

Though conventional OO design suggests programs should be built from many small objects, like Lego bricks, they are instead built from objects that are scale-free, like fractals, and unlike Lego bricks.

theoretical biology

Religion as Superorganism: On David Sloan Wilson's Darwin's Cathedral

Joseph Bulbulia and Marcus Frean
Chapter to appear in: M. Stausberg (Ed.) Contemporary Theories of Religion: A Critical Companion. New York: Routledge. , 2008.

One of the most important biological theories of religion is also the most controversial. Here we describe and partially defend David Sloan Wilson's group selectionist model. According to Wilson, religions are best explained as "superorganisms" adapted to succeed in competition against others. The evolutionary history of religion is a battle of these titans.

Emergence of cyclic competitions in spatial ecosystems

Frean, M.R.
SIRC 2006: Interactions and Spatial Process (Eighteenth Colloquium hosted by the Spatial Information Research Centre, November 6-7 2006, held in Dunedin, New Zealand).
download gzipped postscript

This paper considers ways in which cyclic competitions between species might emerge from other systems. An approach is suggested that begins with a single species. In some regimes it leads to networks of competing species, while in others it generates evolutionary dynamics that are akin to the ``red queen'' effect, but within a single species. I speculate on whether these behaviours might arise from a more realistic model, and sketch the form this model might take.

A model for adjustment of the retinotectal mapping, based on Eph-dependent regulation of ephrin levels.

Frean, M.R.
CNS 2006 (Fifteenth Annual Computational Neuroscience Meeting, Edinburgh, July 16-20, 2006).

(3 page extended abstract)

The formation of a topographically ordered map in the retinotectal system, independent of neural activity, has long been thought to rely on the matching of molecular cues between the innervating retinal ganglion cell axons and their targets in the tectum. In the last few years Eph-ephrin signalling has emerged as the likely substrate for this matching process. For example, Eph-A receptors are expressed in a decreasing gradient along the naso-temporal axis of the retina while their ephrin A ligands increase along the caudal-rostral axis of the tectum. In principle this allows a retinal axon to be targetted to a particular termination zone within the tectum. There are several plausible mechanisms for how this targetting might occur. These models are able to account to varying degrees for recent key findings, but do not address a number of experiments carried out even before the discovery of Eph-ephrin signalling. The experiments involved recovery of the topographic projection following ablation of portions of the retina or tectum, in which the resulting mapping is seem to expand or contract appropriately, apparently making optimal use of the remaining areas. This paper describes a model for the formation of topographic mappings that incorporates the recent discoveries about Eph-ephrin signalling and is able to account for the expansion and contraction experiments. The model features (a) regulation of ephrin expression in cells that are innervated from the retina, with changes acting to match the current ephrin value to a target level, and (b) smoothing of ephrin levels in the tectum via a local diffusion process. It also incorporates a continuous tectum and `soft' competition between RGC axons for tectal space, as well as a tendency - rather than a hard constraint - for those axons to terminate in the tectum. An appealing feature is that since the ephrin levels are being reset, an axon growing from the retina at a later time should still find the correct position in the tectum.

Adaptation and enslavement in host-endosymbiont associations.

Frean, M.R. and Abraham,E. (2004)
Physical Review E, 69, (051913) (6 pages).

This paper has been fairly widely cited, e.g. in Nature, P.N.A.S., Proceedings B., Am. Nat. , Ecology, JTB, etc.

In the children's game of rock-scissors-paper, players each choose one of three strategies. A rock beats a pair of scissors, scissors beat a sheet of paper and paper beats a rock, so the strategies form a competitive cycle. Although cycles in competitive ability appear to be reasonably rare among terrestrial plants, they are common among marine sessile organisms and have been reported in other contexts. Here we consider a system with three species in a competitive loop and show that this simple ecology exhibits two counter-intuitive phenomena. First, the species that is least competitive is expected to have the largest population and, where there are oscillations in a finite population, to be the least likely to die out. As a consequence an apparent weakening of a species leads to an increase in its population. Second, evolution favours the most competitive individuals within a species, which leads to a decline in its population. This is analogous to the tragedy of the commons, but here, rather than leading to a collapse, the 'tragedy' acts to maintain diversity.

A voter model of the spatial prisoner's dilemma.

Frean, M.R. and E. Abraham (2001)
IEEE Transactions on Evolutionary Computation. 5 , (2), 117-121.

The prisoner's dilemma (PD) involves contests between two players, and may naturally be played on a spatial grid using voter model rules. In the model of spatial PD discussed here, the sites of a 2 dimensional lattice are occupied by strategies. At each time-step a site is chosen to play a PD game with one of its neighbors. The strategy of the chosen site then invades its neighbor with a probability which is proportional to the pay-off from the game. Using results from the analysis of voter models, it is shown that with simple linear strategies this scenario results in the long-term survival of only one strategy. If three non-linear strategies have a cyclic dominance relation between one-another, then it is possible for relatively cooperative strategies to persist indefinitely. With the voter model dynamics, however, the average level of cooperation decreases with time if mutation of the strategies is included. Spatial effects are not in themselves sufficient to lead to the maintenance of cooperation.

Survival of the unfit.

Frean, M.R. and Abraham,E. (2000)
Invited paper, Workshop on Evolutionary Computation and Cognitive Science, Melbourne, Feb 2000. gzipped postscript

In genetic algorithms it is often taken for granted that selection of the most successful members of a population will result in individuals whose fitness is higher than their ancestors. On the contrary, there exist circumstances in which "survival of the fittest" is catastrophically bad, and survival of the least fit leads to the highest population fitness over time. Such situations are succinctly described in terms of the Prisoner's Dilemma concept from game theory. We discuss the evolution of behaviour under selection pressures which amount to the prisoner's dilemma, with particular attention to the case of evolution in spatially structured environments. The Voter model provides a particularly exacting scenario for the evolution of cooperation, in which most existing results about the evolution of "tit-for-tat" and related simple strategies fail to hold. Despite this, the model can exhibit complex cooperative behaviour including cycles of invasion. We show that these cycles give rise to self-similar (fractal) spatially structured populations. Surprisingly, it pays each member of such a cycle to be minimally aggressive towards the species it can invade.

The evolution of degrees of cooperation.

Frean, M.R. (1996)
Journal of Theoretical Biology , 182, 549 - 559.

The Prisoner's Dilemma has been widely studied as a model for the evolution of cooperation, and most of this work has dealt with agents who either cooperate or not. In this paper we look at the consequences of allowing agents to have intermediate levels of cooperation, and to update these levels over time. The familiar strategy of ``tit for tat'' emerges as a robust mode of behaviour, yet there are important differences between this case and that of ``all or nothing'' cooperation.

The Prisoner's Dilemma without synchrony

Frean, M.R. (1994)
Proceedings of the Royal Society of London (B) , 257, ,75 - 79.

There are many situations in which biological organisms cooperate despite obvious incentives to do otherwise. Such situations are commonly modelled using a paradigm known as the Prisoner's Dilemma. In this way cooperative behaviour has previously been shown to emerge in a model population of strategies. If players can make probabilistic choices taking into account their co-player's previous action, a strategy known as `Generous Tit For Tat' dominates the long-term behaviour of such a population. If they can also take into account their own previous action, a strategy of `win stay, lose shift' dominates instead.
These models assumed that participants make their decisions in synchrony, which seems improbable in many biological situations. Here we show that the timing of decisions is critical in determining which strategy emerges in the long run. If individuals make their decisions at different times, neither of the above strategies survives given the usual payoffs. In the former case Generous Tit For Tat succumbs to inveterate defectors, and in the latter a new strategy takes over. This `firm but fair' strategy is retaliatory yet highly cooperative. In particular, continued exploitation of a sucker is no longer a successful behaviour.

machine learning and neural computation

Using Gaussian Processes to Optimize Expensive Functions

Marcus Frean and Phillip Boyle
Lecture Notes in Computer Science (LNCS 5360). Proceedings Springer 2008, ISBN: 978-3-540-89377-6., pp 258-267.
(AI-08, 21st Australasian Joint Conference on Artificial Intelligence, 3-5 Dec, Auckland, New Zealand, 2008).

The task of finding the optimum of some function f(x) is commonly accomplished by generating and testing sample solutions iteratively, choosing each new sample x heuristically on the basis of results to date. We use Gaussian processes to represent predictions and uncertainty about the true function, and describe how to use these predictions to choose where to take each new sample in an optimal way. By doing this we were able to solve a difficult optimization problem - finding weights in a neural network controller to simultaneously balance two vertical poles - using an order of magnitude fewer samples than reported elsewhere.

Implementing Gaussian Process inference with neural networks

Marcus Frean, Matt Lilley and Phillip Boyle (2006)
International Journal for Neural Systems , Special Issue on Adaptive Neural Methods for Intelligent Data Analysis,
Editors H. Yin, M. Gallagher and M. Magdon-Ismail

Gaussian processes compare favourably with backpropagation neural networks as a tool for regression, and Bayesian neural networks have Gaussian process behaviour when the number of hidden neurons tends to infinity. We describe a simple recurrent neural network with connection weights trained by one-shot Hebbian learning. This network amounts to a dynamical system which relaxes to a stable state in which it generates predictions identical to those of Gaussian process regression. In effect an infinite number of hidden units in a feed-forward architecture can be replaced by a merely finite number, together with recurrent connections.

A comparison of spiking neuron models for the control of unstable systems

Tod, R. and Frean, M.R. (2005)
Motor Control and Cognitive Neuroscience Conference, Dunedin, 7-9 Dec 2005.

Although there is much current interest in the neurodynamics of biologicaly plausible spiking neurons, there has been very little work investigating the role these properties might play in solving low-level physical control problems of the kind that living systems (and robots) face.
We investigated four computationally inexpensive models of spiking neurons from the literature. Simple controllers with a feed forward architecture of spiking neurons were arrived at through an evolutionary process, and tested on tasks involving the control of unstable physical systems. Two models were readily able to solve a challenging version of the benchmark pole-balancing problem, in which two poles are balanced simultaneously, and agents have no direct access to the cart or pole velocities. These velocities are required to solve the task in principle, and must therefore be inferred by the controller itself.
Spike frequency adaptation, a distinctive feature of biological neurons, was found to be a crucial neuro-computational property. Spiking neurons models without spike frequency adaptation were unable to solve this task. Neuron models that exhibit adaptation have negative feedback to membrane potential, which dampens pole oscillations and leads to stable control. In effect, velocities are included in the computation implicitly via this adaptation, rather than explicitly as in most other standard controllers. Moreover, in successful agents the networks of spiking neurons were simpler that those arrived at by evolving conventional recurrent neural networks.

Neural Networks: a replacement for Gaussian Processes?

Lilley, M. and Frean, M.R. (2005)
Lecture Notes in Computer Science
Springer-Verlag (ISSN: 0302-9743), Volume 3578, p 95-103, 2005
(Proc. Sixth Int. Conf. Intelligent Data Engineering and Automated Learning IDEAL'05, 6-8 July, Brisbane, Australia, July 6-8, 2005. Proceedings Editors: Marcus Gallagher, James Hogan, Frederic Maire)

Gaussian processes have been favourably compared to backpropagation neural networks as a tool for regression. We show that a recurrent neural network can implement exact Gaussian process inference using only linear neurons that integrate their inputs over time, inhibitory recurrent connections, and one-shot Hebbian learning. The network amounts to a dynamical system which relaxes to the correct solution. We prove conditions for convergence, show how the system can act as its own teacher in order to produce rapid predictions, and comment on the biological plausibility of such a network.

Dependent Gaussian Processes

Boyle, P.K. and Frean, M.R. (2004)
Neural Information Processing Systems (NIPS)

See also the NIPS poster

Gaussian processes are usually parameterised in terms of their covariance functions. However, this makes it difficult to deal with multiple outputs, because ensuring that the covariance matrix is positive definite is problematic. An alternative formulation is to treat Gaussian processes as white noise sources convolved with smoothing kernels, and to parameterise the kernel instead. Using this, we extend Gaussian processes to handle multiple, coupled outputs.

Population-based Continuous Optimization, Probabilistic Modelling and Mean Shift.

Gallagher, M.G. and Frean, M.R. (2005)
Evolutionary Computation , 13: 1, 29-42. Spring 2005.

Evolutionary algorithms perform optimization using a population of sample solution points. An interesting development has been to view population-based optimization as the process of evolving an explicit, probabilistic model of the search space. This paper investigates a formal basis for continuous, population-based optimization in terms of a stochastic gradient descent on the Kullback-Leibler divergence between the model probability density and the objective function, represented as an unknown density of assumed form. This leads to an update rule that is related and compared with previous theoretical work, a continuous version of the population-based incremental learning algorithm, and the generalized mean shift clustering framework. Experimental results are presented that demonstrate the dynamics of the new algorithm on a set of simple test problems.

A key issue in using connectionist models is the choice of which network architecture to use. There are a number of ways this choice can be made automatically, driven by the problem at hand.

Boosting algorithms as gradient descent in function space.

Mason,L., Baxter,J., Bartlett,P. and Frean, M.R. (2000)
In Neural Information Processing Systems, 1999. 12, 512-518. MIT Press, 2000. gzipped postscript

Much recent attention, both experimental and theoretical, has been focussed on classification algorithms which produce voted combinations of classifiers. Recent theoretical work has shown that the impressive generalization performance of algorithms like AdaBoost can be attributed to the classifier having large margins on the training data. We present abstract algorithms for finding linear and convex combinations of functions that minimize arbitrary cost functionals (i.e functionals that do not necessarily depend on the margin). Many existing voting methods can be shown to be special cases of these algorithms. Then, (etc)...

Real-valued evolutionary optimization using a flexible probability estimator.

Gallagher,M., Frean, M.R. and Downs,T. (1999).
Proceedings of the Genetic and Evolutionary Computation Conference, Orlando, Florida, July 1999. Volume 1, 840-846. gzipped postscript

Population-based Incremental Learning (PBIL) is an abstraction of a genetic algorithm, which solves optimization problems by explicitly constructing a probabilistic model of the promising regions of the search space. At each iteration the model is used to generate a population of candidate solutions and is itself modified in response to these solutions. Through the extension of PBIL to real-valued search spaces, a more powerful and general algorithmic framework arises which enables the use of arbitrary probability density estimation techniques in evolutionary optimization. To illustrate the usefulness of this framework, we propose and implement an evolutionary algorithm which uses a finite Adaptive Gaussian mixture model density estimator (etc)...

Catastrophic forgetting in simple networks: an analysis of the pseudorehearsal solution.

Frean, M.R. and Robins,A.V. (1999)
Network: Computation in Neural Systems , 10, 227 - 236.

Catastrophic forgetting is a major problem for sequential learning in neural networks. One very general solution to this problem, known as `pseudorehearsal', works well in practice for non-linear networks but has not been analysed before. This paper formalises pseudorehearsal in linear networks. We show the method can fail in low dimensions but is guaranteed to succeed in high dimensions under fairly general conditions. In this case an optimal version of the method is equivalent to a simple modification of the `delta rule'.

A simple cost function for boosting.

Frean, M.R. and Downs,T. (1998)
Technical report, Dept. of Computer Science and Electrical Engineering, University of Queensland. gzipped postscript

For two-class classification problems the boosting algorithm "AdaBoost" is equivalent to minimizing the cost-function: (..see the postscript...). Using this we show that the D variables are unnecessary for AdaBoost to work, and that `re-boosting' of previous classifiers is straightforward.

Local learning algorithms for sequential learning tasks in neural networks.

Robins,A.V. and Frean, M.R. (1998).
Journal of Advanced Computational Intelligence, 2, (6), 107 - 111. gzipped postscript

In this paper we explore the concept of sequential learning and the efficacy of global and local neural network learning algorithms on a sequential learning task. Pseudorehearsal, a method developed by Robins (1995) to solve the catastrophic forgetting problem which arises from the excessive plasticity of neural networks, is significantly more effective than other local learning algorithms for the sequential task. We further consider the concept of local learning and suggest that pseudorehearsal is so effective because it works directly at the level of the learned function, and not indirectly on the representation of the function within the network. We also briefly explore the effect of local learning on generalisation within the task.

Learning and generalization in a stable network.

Robins,A.V. and Frean, M.R. (1998)
In Progress in Connectionist-Based Information Systems: Proc. 1997 Conference on Neural Information Processing and Intelligent Information Systems, Kasabov et. al. (Eds), Singapore: Springer-Verlag, pp. 314-317. gzipped postscript

Most neural networks suffer from excessive plasticity: the learning of new information interferes with information already stored in the network. In this paper we review the pseudorehearsal solution to this problem, proposed by Robins (1995). By localising the changes to the function learned by the network pseudorehearsal allows networks to be stable in the face of new learning, successfully integrating both new and previously learned information. In this paper we explore the impact that this mechanism has on the ability of the network to generalise.

A 'thermal' perceptron learning rule.

Frean, M.R. (1992)
Neural Computation, 4, (6), 946 - 957. PDF of scan

The thermal perceptron is a simple extension to Rosenblatt's perceptron learning rule for training individual linear threshold units. It finds stable weights for non-separable problems as well as separable ones. Experiments indicate that if a good initial setting for a temperature parameter, $T_{0}$, has been found, then the thermal perceptron outperforms the Pocket algorithm and methods based on gradient descent. The learning rule stabilises the weights (learns) over a fixed training period. For separable problems it finds separating weights much more quickly than the usual rules.

The Upstart Algorithm: a method for constructing and training feed-forward neural networks.

Frean, M.R. (1990)
Neural Computation, 2 (2), 189 - 209. gzipped postscript

A general method for building and training multi-layer perceptrons composed of linear threshold units is proposed. A simple recursive rule is used to build the net's structure by adding units as they are needed, while a modified Perceptron algorithm is used to learn the connection strengths. Convergence to zero errors is guaranteed for any Boolean classification on patterns of binary variables. Simulations suggest that this method is efficient in terms of the numbers of units constructed, and the networks it builds can generalise over patterns not in the training set.

Small Nets and Short Paths: Optimising Neural Computation.

Frean, M.R. (1990)
PhD Thesis, University of Edinburgh, Scotland. 1990. gzipped postscript

This thesis explores two aspects of optimisation in neural network research.
1. The question of how to find the optimal feed-forward neural network architecture for learning a given binary classification is addressed. The so-called constructive approach is reviewed whereby intermediate, hidden units are built as required for the particular problem. Current constructive algorithms are compared, and three new methods are introduced. One of these, the Upstart algorithm, in shown to outperform all other constructive algorithms of this type. This work led on to the ancillary problem of finding a satisfactory procedure for changing the weights values of an individual unit in a network. The new thermal perceptron rule is described and shown to compare favorably with its competitors. Finally, the spectrum of possible learning rules is surveyed.
2. Neurobiologically inspired algorithms for mapping between spaces of different dimensionality are applied to a classic optimisation problem, the Travelling Salesman Problem. Two new methods are described that can tackle the general symmetric form of the TSP, thus overcoming the restriction on other neural networks to the geometric case.

publications

others

theoretical biology

See also: Virtual Journal of Biological Physics Research, 7, (11) - under "Statistical and nonlinear physics".
See also the article in the "Physics Update" section (page 9) of Physics Today, June 2004

This paper has been fairly widely cited, e.g. in Nature, P.N.A.S., Proceedings B., Am. Nat. , Ecology, JTB, etc.

machine learning and neural computation

publications

others

theoretical biology

See also: Virtual Journal of Biological Physics Research, 7, (11) - under "Statistical and nonlinear physics". See also the article in the "Physics Update" section (page 9) of Physics Today, June 2004

This paper has been fairly widely cited, e.g. in Nature, P.N.A.S., Proceedings B., Am. Nat. , Ecology, JTB, etc.

machine learning and neural computation

See also: Virtual Journal of Biological Physics Research, 7, (11) - under "Statistical and nonlinear physics".
See also the article in the "Physics Update" section (page 9) of Physics Today, June 2004