AINC Seminars - 2003

Biological neural systems achieve impressive performance and robustness using slow, unreliable components. To a computer engineer this observation demands explanation - building robust complex systems with reliable components is hard enough! What are the properties of neurons that enable brains to function without suffering from the chaos caused by all the usual hazards of symbol interference, data loss, component failure, and so on? In this talk I will speculate a little on these matters and present a design for a sparse distributed memory that can be built from spiking neurons.

A great deal of work on perception assumes that that task of a perceptual system is to provide information about geometrical and other physical or chemical properties of things in the environment. An alternative view, inspired by the psychologist, J.J.Gibson is that perception provides information about affordances, which can be construed as possibilities for and constraints on actions. Examples of positive and negative affordances include support, graspability, passage, obstruction, unreachability. I shall try to extend these ideas as follows: 1. Affordances are not intrinsic properties of entities in the environment but relational properties (hence the affordances for one organism may not exist for another) 2. Many affordances involve branching sets of possible futures and there are problems about how to represent such things in useful ways. This is linked to the problem of how to represent causal and functional relationships, and counterfactual conditionals. 3. The grasp of affordances may either be implicit in the way various mechanisms function or explicit in an ontology used by the perceiver. The latter case requires a more sophisticated information-processing architecture. Most organisms don't have this. Humans, and perhaps some other animals do. There are probably many interesting intermediate cases between insects and humans. 4. Giving robots human-like intelligence will require (a) finding out a lot more than we currently understand about what affordances humans and other animals use, (b) finding new forms of representation for affordances and (c) investigating new information-processing architectures within which they can be used at all or used fluently. 5. For biological evolution there are complex trade-offs between transmitting information about affordances genetically and producing mechanisms that can discover affordances. This is connected with the distinction between precocial and altricial species. 6. There are also trade-offs between building the ability to perceive affordances into dedicated perceptual mechanisms and allowing them to be derived by general purpose reasoning mechanisms. 7. The solutions evolution produced for humans are probably closely related to the ability of humans to do mathematics.

Genetic Programming uses a tree based representation to express solutions to problems. Trees are constructed from a primitive set which consists of a function set and a terminal set. An extension to GP is the ability to define modules, which are in turn tree based representations defined in terms of the primitives. The most well known of these methods is Koza's Automatically Defined Functions. In this paper it is proved that for a given problem, the minimum number of nodes in the main tree plus the nodes in any modules is independent of the primitive set (up to an additive constant) and depends only on the function being expressed. This reduces the number of user defined parameters in the run and makes the inclusion of a hypothesis in the search space independent of the primitive set.

Interest in the science of information hiding, or steganography, has increased dramatically over the last decade. It has become a useful tool for copyright protection purposes as well as for data integrity, authentication and fingerprinting. I will briefly review modern watermarking techniques and introduce a new approach, for both robust and fragile watermarking, based on the ICA feature space. Applications of the new approach to both digitized images and audio signals will also be presented.

This presentation offers a framework for inductive learning polynomial neural networks (PNN). The framework involves, first, finding the polynomial network structure by means of population-based search technique relying on the genetic programming paradigm, and second, further adjustment of the best discovered polynomial network weights by an especially derived backpropagation algorithm for higher-order networks with polynomial activation functions. These two stages of the PNN learning process enable us to achieve networks with good training as well as generalization performance. Empirical results show that this approach finds PNN which outperform considerably some previous constructive polynomial network algorithms on processing real-world time series.

An important problem of evolutionary algorithms is that throughout evolution they loose genetic diversity. We define here a diversity measure for genetic programs based on our metric for genetic trees. We propose a method for adaptively maintaining the diversity of a population during evolution. We then investigate the behaviour of genetic programming populations on increasingly difficult problem instances. Simple diversity measures are used to characterise population dynamics and qualities of populations that lead to better performance. The results indicate that the evolving program structures are likely to have a great effect on performance.

When using an automatic discovery method to find a good strategy in a game, we hope to find one that performs well against a wide variety of opponents. An appealing notion in the use of evolutionary algorithms to coevolve strategies is that the population represents a set of different strategies against which a player must do well. Implicit here is the idea that different players represent different "dimensions" of the domain, and being a robust player means being good in many (preferably all) dimensions of the game. Pareto coevolution makes this idea of "players as dimensions" explicit. By explicitly treating each player as a dimension, or objective, we may then use established multi-objective optimization techniques to find robust strategies. Pareto coevolution has been applied to Texas Hold'em poker, a complex real-world game of imperfect information. The performance of the Pareto coevolution algorithm is compared with that of a conventional genetic algorithm and shown to be promising.

"There is nothing as practical as a good theory" "The difference between theory and practice is that, in theory, there is no difference" The aim of this talk is to demonstrate the truth of both these statements when developing useful applications with pattern analysis techniques. The key to success is to achieve a principled pragmatism; flexibility without prejudice. We need theory to provide a wide range of models (with different motivating assumptions) and so that we can apply appropriate techniques given the structure of a problem. However, an application is not just about picking a model with the best accuracy: practical questions are not settled completely by minimising a sum-of-squares error function. In particular, a model forms part of a larger system that must be accessible to users which leads to a broader range of challenges. The main differences from purely theoretical investigations will be described and illustrated with real examples including wind field modelling, oil drilling condition monitoring, ECG arrhythmia analysis, bioinformatics and medical diagnosis.

The Prisoner's Dilemma is a simple two player game that has received much study in economics, ethics, and political science. It embodies a common situation in which individual rational self-interest leads to the worst outcome for the group. Prisoner's Dilemma has also been extended, allowing multiple rounds of the game and accomodating more players. These changes have allowed the study of the evolution of cooperation, involving computer simulations, evolutionary algorithms and replicator dynamics. We introduce a new variant involving multiple rounds, multiple players and public knowledge of all interactions. This simple variation gives rise to many new strategies that can exploit the passive or join together for mutual protection. We study the replicator dynamics and use genetic programming to examine naturally occuring strategies and their interactions. Of particular interest, there are many situations where certain strategies outperform the famous 'Tit for Tat', and we look at why this is through new generalisations of what it means to be 'nice', 'retaliatory' and 'forgiving'.

Social insects provide us with a powerful metaphor to create decentralized systems of simple interacting, and often mobile, agents. The emergent collective intelligence of social insects swarm intelligence resides not in complex individual abilities but rather in networks of interactions that exist among individuals and between individuals and their environment. The study of ant colonies behavior and of their self-organizing capabilities is of interest to knowledge retrieval/ management and decision support systems sciences, because it provides models of distributed adaptive organization which are useful to solve difficult optimization, classification, and distributed control problems, among others. In the present presentation we overview some models derived from the observation of real ants, emphasizing the role played by stigmergy as distributed and indirect communication paradigm, and we present novel strategies to tackle unsupervised data exploratory analysis as well as data retrieval problems. Moreover and according to our knowledge, this is also the first application of ant systems into digital image analysis and image retrieval problems. Contributions of these types of systems in Art and Architecture are also discussed.

Is "useful diversity" a myth? Many experiments and the little available theory on diversity in classifier ensembles are either inconclusive, too heavily assumption-bound or openly non-supportive of the intuition that diverse classifiers fare better than non-divers ones. Although a rough general tendency was confirmed in our previous studies, no prominent link appeared between diversity of the ensemble and its classification accuracy. Diversity alone is a poor predictor of the ensemble accuracy. But there is no agreed definition of diversity to start with! Can we borrow a concept of diversity from biology? How can diversity, as far as we can define and measure it, be used to improve the ensemble? Here we argue that even without a clear-cut definition and theory behind it, studying diversity may prompt viable heuristic solutions. We look into some ways in which diversity can be used in analyzing, selecting or training the ensemble.

Most work on the Gibsonian notion of affordances has looked at the relation between perceptual invariants like radial flow as signals of properties of situations, such as time-to-impact. But Gibson also proposed a more general notion of affordance, according to which to perceive an object is perceive its affordances, in the sense of those interactions of the perceiver with the world that the object mediates or affords. This idea is attractive from the point of view of a number of theoretical positions in cognitive science that emphasize the fundamental role of action in an agent's knowledge representation of the world. However, affordance in this broader, action related sense has so far lacked a satisfactory formal expression. The paper offers a representation for objects in terms of their affordances using Linear Dynamic Event Calculus (LDEC), a form of Situation Calculus for reasoning about causal relations over events. It argues that a representation of this kind, linking objects to the events which they are characteristically involved in, underlies some universal operations of natural language syntactic and semantic composition that are assumed in Combinatory Categorial Grammar (CCG). These observations in turn imply that the language faculty is more directly related to prelinguistic cognitive apparatus used for planning action than formal theories in either domain have previously seemed to suggest. Such a link is in keeping with well-known neuroanatomical observations about the localization of language functions in the brain.

The fractal protein is a new concept intended to improve evolvability, scalability, exploitability and provide a rich medium for evolutionary computation and evolutionary design. Here the idea of fractal proteins and fractal proteins with concentration levels are introduced, and a series of experiments showing how evolution can design and exploit them within gene regulatory networks is described. These show how fractal GRNs have a natural tendency towards damage tolerance, and can be successfully employed for tasks such as robot control. Patterns are crucial in development. Biological development is not simply a process to create a phenotype. It is an on-going process that shapes, adapts and repairs an organism, beginning at conception and ending at the death of the organism. Consequently, an organism is not an end-result of a developmental program, it is an ever-changing solution that is maintained by development. From a computational viewpoint, the processes of development appear to be constant, never-ending patterns, generated by gene-gene interactions in gene regulatory networks and at higher levels in cell-cell interactions, and so on. Phenotypes are the dynamic high-level results of those non-stop lower-level interactions.

Search-based testing is the name given to a set of problems where test data is to be generated using search-based algorithms, most notably genetic algorithms. There is a growing interest in search-based testing techniques, reflecting a similar increase in awareness of search-based techniques for solving a wide class of traditional problems in software engineering. The search for good quality test data is a central plank of many organisations' verification and validation strategies. It turns out that many of the criteria that define "good quality" in test data form ideal candidates for fitness functions. In this talk I will present a survey of the field, relating both academic results and industrial practice, focusing in particular, on my joint work with DaimlerChrysler's Evolutionary Testing group.

Extrapolation (defined by correct performance for data points lying outside of the convex hull of the data used for training and validation) is a challenge for connectionist models. This work describes the use of both hand-tailored and evolved representations, and their effects on extrapolation performance.

In this work, data mining techniques were applied on proteomics data collected from two different groups of people: cancer patients and control (healthy) subjects, with the ultimate goal of constructing a classifier that is able to predict cancer by analyzing the proteomic profile of tumor antigenicity of a person. However, the analysis may also enhance our understanding of the relationship between each antigen's gene and the etiology of cancer. A dimensionality reduction was necessary in order to address the curse of dimensionality problem. Three different classifiers were constructed and tested: Pruned Decision Tree, Voted Perceptron and Neural Network. These machine learning algorithms were assessed on a variety of performance tests and the results were compared statistically. The results suggest that neural networks can be effectively used in prediction of cancer from proteomic data, providing an accuracy of around 95\% on validation data. This work differs from previous studies of molecular profiling of cancer in that here we classify individuals prior to the onset of cancer when there is no apparent tumor to sample. The impact of the methods will provide a novel approach to the early detection of cancer, thus greatly improving the patient's chances of survival.

The behavioural characteristics of an individual interacting with a system over time can be captured in a user specific profile represented by appropriate summary statistics. To provide a compact generative representation of the sequential activity of a group of individuals there is a trade-off between the definition of common behaviours and traits specific to each individual. This talk presents a linear-time distributed model for finite state symbolic sequences which represent the observed interactions of individuals with a system over time. The model is based on the assumption that inter and intra individual behavioural heterogeneity within a population can be `explained' by a relatively small number of simple behavioural elements which may interleave randomly in an individual-specific distribution. An empirical study considers the modelling of large groups of individuals in three different situations, (1) Browsing a Website, (2) Word-Processor Software Usage, and (3) Telephone Service Usage. It is observed that an efficient low-complexity and intuitively interpretable representation scheme is obtained which is reflected by improved predictive performance over other appropriate models.

We consider the problem of extracting information from two or more data streams simultaneously.

Unsupervised neural networks (e.g. the self-organizing map, neural gas, or statistical counterparts) constitute valuable tools for data mining, visualization, or data preprocessing. They can deal with vectors of a finite and fixed dimensionality. Interesting application areas such as logic, language processing, chemistry, or bioinformatics, however, often use more complex structures such as sequences or trees. Whereas the generalization of supervised networks to more complex data structures is well established (recurrent and recursive networks), various different extensions of unsupervised models to sequences and tree structures have been proposed (temporal Kohonen map, recurrent SOM, recursive SOM, SOM for structured data, ...). We will present a uniform notation of unsupervised recursive models which includes several proposals from the literature as special cases and which transfers the dynamics of supervised recursive models to the unsupervised case. Based on this uniform notation, we add two further possibilities and demonstrate the properties of the models in several experiments. We then have a look at theoretical questions such as the existence of cost functions, the capacity of the models, and the induced topology.

The SimAgent toolkit, developed in this school since about 1994 (initially in collaboration with DERA) and used for a number of different projects here and elsewhere, is designed to support both teaching and exploratory research on multi-component architectures for both artificial agents (software agents, robots, etc.) and also models of natural agents. Unlike many other toolkits (e.g. toolkits associated with SOAR, ACT-R, PRS) it does not impose a commitment to a particular class of architectures but allows rapid-prototyping of novel architectures for agents with sensors and effectors of various sorts (real or simulated) and many different kinds of internal modules doing different sorts of processing, e.g. perception, learning, problem-solving, generating new motives, producing emotional states, reactive control, deliberative control, self-monitoring and meta-management, and linguistic processing. One of the things that makes this possible is the use of a powerful, interactive, multi-paradigm extendable language, Pop-11 (similar in power and generality to Common Lisp, though different in its details). This has made it possible to combine within the same package support for different styles of programming for different sub-tasks, e.g. procedural, functional, rule-based, object oriented (with multiple inheritance and generic functions), and event-driven programming, as well as allowing modules to be edited and recompiled while the system is running, which supports both incremental development and testing and also self-modifying architectures. A collaborative project between Birmingham and Nottingham is producing extensions to support distributed agents using the HLA (High Level Architecture) platform. The talk will give an overview of the aims of the toolkit, show some simple demonstrations, explain how some of it works, and provide information for anyone who wishes to try using it. The talk may be useful to students considering projects requiring complex agent architectures.

The talk will be concerned with pattern classification problems and in particular the motivations and challenges behind using and designing multiple classifier systems. Starting with an attempt to answer the question of why would one like to combine classifiers we will move to an overview of how to combine them. This will be followed by discussing the issues of majority voting limits, classifier diversity, classifier selection, multistage organisations and an alternative to combining at a decision level.

In this talk we present a novel probabilistic model for inferring multiple hidden causes from multivariate binary observations. As opposed to previous approaches to factorising binary data, which are non-linear, the model does a convex decomposition of the mean parameter of the Bernoulli distribution. Parameters are easily interpretable, a distinctive feature being that the model can infer reasons behind having observed certain attributes but also reasons behind not having observed some others. Thus, it is now possible to distinguish between the case where an attribute is 'off' by content and the case where an attribute is 'off' by occlusion. Simulation results of the analysis of artificially corrupted binary images of handwritten digits as well as the analysis and expansion of short text documents are given by way of demonstration. The results may suggest the applicability of the method to query expansion.

In applications such as vacuum cleaning, painting, humanitarian demining and foraging, a mobile robot must cover an unknown surface. The efficiency and completeness of coverage are improved via the construction of a map of covered regions while the robot covers the surface. Existing methods generally use grid maps, which are susceptible to odometry error. This paper proposes a coverage algorithm based on a qualitative topological map which is created incrementally with natural landmarks added as nodes. This partial topological map constructs an exact cell decomposition of the environment online. Complete coverage is thus achieved by covering all cells of the decomposition. Simulation tests show 100% of the surface is covered with path lengths about 10% worse than the ideal. This is within the theoretical upper bounds for approximate solutions to travelling salesman based coverage problems. Real (Khepera) robot tests show over 97% coverage with path lengths about 40% worse than ideal. The proposed algorithm generates shorter paths and covers a wider variety of environments than existing cell decomposition based coverage algorithms.

The concept of a Riemannian manifold provides a very general notion of the nonlinear dependency in the data. In my talk I will discuss how different problems of machine learning may be approached in the manifold setting. In particular, I will discuss semi-supervised learning which seems particularly suited for the manifold methods. I will also present some encouraging experimental results. This is joint work with Partha Niyogi.

I will present a computational model of human visual attention, termed SAIM (Selective Attention for Identification Model), based on the idea that there is competition between objects for recognition. SAIM uses a spatial window to select visual information for object recognition, ensuring both that parts are bound correctly within objects and that translation invariant object recognition can be achieved. I will show how such a competitive model can provide a qualitative account of a range of psychological phenomena on both normal and disordered attention. Simulations of normal attention demonstrate two-object costs on selection, spatial cueing and object-based selection. When simulated lesions are conducted, SAIM demonstrates both neglect and spatial extinction, depending on the type and extent of the lesion. I will highlight how emergent properties of competition with the model can unify (i) object- and space-based theories of normal selection, (ii) dissociations within the syndrome of visual neglect, (iii) 'attentional' and 'representational' accounts of neglect.

The talk starts with an overview of the NECA (short for: Net Environment for Embodied Emotional Conversational Agents) platform. The platform has been developed in the EU-funded NECA project, which is currently at the end of its second year. The NECA platform supports automatic generation of dialogues between embodied agents on the basis of a database with domain information and user-controllable settings for the personalities, interests and roles of the agents. Demonstrator systems based on the platform have been built in two domains: carsales dialogues (eShowroom) and social chat between students (Socialite). The overview is followed by a more detailed discussion of the language and gesture generation component, the NECA MNLG (Multimodal Natural Language Generator). I discuss both the architecture of this component, aimed at fast and flexible generation, and some pilot experiments for evaluating the gesture generation module. The talk concludes with a discussion of work in progress on enforcing global constraints in the automated generation of the NECA scripted dialogues, i.e., dialogues which are created by a single automated author for performance by a team of agents/actors.