DEPARTMENTAL SEMINAR (COMPUTER & COGNITIVE SCIENCES) AUTUMN TERM 1998 TIME AND PLACE: Thursdays 4pm (Unless otherwise stated) Lecture Room 7, School of Computer Science ORGANISER: Marta Kwiatkowska (M.Z.Kwiatkowska@cs.bham.ac.uk, ext 7264) Sammie Snow (S.Snow@cs.bham.ac.uk, ext 4774) SPEAKERS and TITLES -- Mon 7 Sep Mahesan Niranjan, Cambridge University 2pm, LR7 Sequential Learning in Nonlinear Models and some Applications -- Wed 9 Sep Greg Mulhauser, BT 11am, LR7 Puzzles of Representation and Function: Using Algorithmic Information Theory -- Thu 17 Sep Xin Yao, University of New South Wales 11am, LR7 A Population of Heads Are Better Than One -- Tue 22 Sep Andrei Voronkov, Uppsala University 4pm, LR7 Herbrand's theorem, automated reasoning and semantic tableaux -- Mon 5 Oct (Joint seminar with EEBIC) Wolfgang Banzhaf, Dortmund University, 4pm LR7 Linear Genetic Programming -- Thu 8 Oct Prof. Hans-Dieter Ehrich, Technische Universitat Braunschweig 4pm, LR7 Specifying Communication in Distributed Information Systems -- Thu 15 Oct No seminar (Accreditation visit) -- Thu 22 Oct Dr Tom Axford, Computer Science, University of Birmingham Markup Languages - Where Are They Going? -- Thu 29 Oct Dr Mark Ryan, Computer Science, University of Birmingham Features of software systems -- Thu 5 Nov Dr Colin OHalloran, DERA, Malvern Ariane 5, learning from experience -- Thu 12 Nov Dr Paul Siebert, University of Glasgow and Turing Institute 3D Research and applications at the 3D-MATIC Faraday Partnership -- Thu 19 Nov Dr Mauricio Marin, University of Oxford Adaptive Time Warp Simulation Upon Bulk-Synchronous Parallel Computers -- Thu 26 Nov Prof. Yorick Wilks, University of Sheffield ***3pm, LW7*** Human-Computer Conversation: where are we? -- Mon 30 Nov Dr Paolo Bouquet, University of Trento, Italy ***4pm, Monday*** A Logic of Contextual Reasoning -- Thu 3 Dec Dr Manfred Kerber, University of Birmingham On Knowledge, Strings, and Paradoxes -- Thu 10 Dec Prof. Graham Birtwistle, University of Leeds Specifying and Verifying TK -- Thu 17 Dec Dr Rob Hopkins, Department of Philosophy, Univ. of Birmingham Molyneux's Question ABSTRACTS ----------------------------------------------------------------------------- -- Mon 7 Sep Mahesan Niranjan, Cambridge University 2pm, LR7 Sequential Learning in Nonlinear Models and some Applications Many real life applications of nonlinear models such as neural networks are characterized by data that arrives sequentially, often from a source that is nonstationary. In such environments, many conventional tricks we know, such as cross validation (for regularisation and model selection) and bootstrap (to deal with model uncertainty), are not applicable. A convenient framework for such sequential and/or nonstationary problems is the extended Kalman filter (EKF). Regularisation can be induced by tuning the noise models in the state space formulation and model selection can be achieved by monitoring the innovation probabilities of multiple models running in parallel. In this talk, I will describe some experience with the use of algorithms centered around the EKF framework, and richer Monte Carlo Sampling based ideas for accurate characterisation of the probability densities, in a number of applications including (a) model based enhancement of speech corrupted by additive noise, in which a nonlinear model of the speech production system is estimated sequentially from data; (b) tracking the price of options contracts traded in financial markets; and (c) monitoring liver transplant patients to predict organ rejection. ----------------------------------------------------------------------------- -- Wed 9 Sep Greg Mulhauser, BT 11am, LR7 Puzzles of Representation and Function: Using Algorithmic Information Theory After introductory comments on Chaitin's rendition of algorithmic information theory, I discuss some traditional puzzles surrounding the notion of representation and the way we understand functional modularisation in complex systems. Applying standard algorithmic information theory to the first problem and a novel extension of it to the second, I argue that our usual ideas of representation and of function can and should be overhauled. If there's time, I'll also note how properties of the delightfully noncomputable number Omega might bear on debates about supervenience. The talk will be aimed at a broad audience; intimate knowledge of algorithms and Turing Machines is *not* required. I can easily be cajoled into discussing other topics before, after, or even during the talk; my web pages at http://www.labs.bt.com/people/mulhaug include notes on most of my current work. ----------------------------------------------------------------------------- -- Thu 17 Sep Xin Yao, University of New South Wales 11am, LR7 A Population of Heads Are Better Than One This talk first introduces an evolutionary system for designing artificial neural networks (ANNs) automatically. ANN architectures (connectivities) and weights are evolved simultaneously. Behavioural rather than genetic evolution is emphasised. Then it is argued that learning is different from optimisation in practice. Population information can be exploited effectively to improve ANN's generalisation. Experimental results show that a combined population of ANNs performs better than the single best ANN. In order to improve a combined population (i.e., an ensemble) of ANNs further, a new learning algorithm is proposed to design individual ANNs cooperatively and simultaneously. Relevant papers 1998: Evolving Artificial Neural Networks by Evolutionary Algorithms (X. Yao), Invited paper in Proceedings of the IEEE. Accessible locally in: ~axs/fetched/yao.ieee.ps 1997: A New Evolutionary System for Evolving Artificial Neural Networks (X. Yao and Y. Liu), IEEE TNN 8(3)694-713, 1997. ftp://www.cs.adfa.oz.au/pub/xin/tnn2770.ps.gz 1996: Evolutionary Stability in the N-Person Iterated Prisoner's Dilemma (X. Yao), BioSystems, 37(3):189-197, 1996. (More technical) ftp://www.cs.adfa.oz.au/pub/xin/biosystems.ps.Z ----------------------------------------------------------------------------- -- Tue 22 Sep Andrei Voronkov, Uppsala University 4pm, LR7 Herbrand's theorem, automated reasoning and semantic tableaux We analyze some fundamental problems arising in automated reasoning methods based on the semantic tableaux and related methods (e.g. connections or model elimination). We argue that one can get better understanding of the efficiency of these methods based on the results of such an analysis. The talk consists of the following parts: 1. Tableaux and related methods; 2. Proof-search in these methods; 3. Related decision problems; 4. Formula Instantiation; 5. Strategies; 6. Open problems and new research directions. No specific knowledge of automated reasoning or tableau-like methods is required. ----------------------------------------------------------------------------- -- Mon 5 Oct (Joint seminar with EEBIC) Wolfgang Banzhaf, Dortmund University, 4pm LR7 Linear Genetic Programming Abstract: Genetic Programming has been originally suggested in a tree-based program representation. In this talk I discuss our approach to GP using elements from imparative languages. Specifically, I will talk about the machine language approach to GP. As it turns out there are advantages to linear GP with respect to the problem of code-growth and bloat that has been uncovered over the years. The talk concludes with the discussion of some recent applications of GP in our lab. ----------------------------------------------------------------------------- -- Thu 8 Oct Hans-Dieter Ehrich, Technische Universitat Braunschweig 4pm, LR7 Specifying Communication in Distributed Information Systems Information systems design is becoming part of object technology. The latter's powerfull implementation tools and techniques are complemented by analysis, modeling and design methods like OOA&D, OMT, OOSE and their recent amalgamation, UML. These techniques are quite successful---but not perfect yet. One of the problems is that a multitude of modeling, specification and implementation concepts are employed that are not always well integrated and sometimes not well understood. The object modeling approaches are semiformal and incomplete. This is ok for the purposes they serve. The problem, however, is that there is no way to develop the descriptions smoothly into a complete and precise system specification that offers the possibility of more than rudimentary validation, e.g., by simulation, analysis or testing tools. Especially problematic are concurrency and communication aspects. Here is where the TROLL project takes its focus. TROLL consists of languages (graphic and textual) with formal syntax and semantics, a method and a workbench. The approach is being developed with an application project and fundamental research going hand in hand. Fundamental research has been and is being pursued, among others, in the context of ESPRIT Working Groups ISCORE, COMPASS and ASPIRE. In the practical project, an information system is being developed for a group at PTB (Physikalisch-Technische Bundesanstalt, the German Federal Institute of Weights and Measures). One of TROLL's particularities is its approach to communication: there is no explicit global process description, all communication is expressed by local calling of actions in other objects. In theoretical work on TROLL semantics, distributed temporal logics are being investigated, using linear-time temporal logic for specifying local (sequential) object behaviour, and adding communication expressions for specifying interaction. ----------------------------------------------------------------------------- -- Thu 22 Oct Tom Axford, School of Computer Science, Univ of Birmingham Markup Languages - Where Are They Going? I will give a quick tour of XML, XSL, SGML, HTML, CSS and some related recent developments in markup and web languages - what sort of languages they are, some simple examples of what they can do, how they relate to each other, and what types of applications they are suitable for. I will also give an outsider's view of these developments and consider the following questions (don't expect complete answers, however): "Where are these developments going?" and "How important are they?". ----------------------------------------------------------------------------- -- Thu 29 Oct Dr Mark Ryan, Computer Science, University of Birmingham Features of software systems A feature is a piece of functionality. For example, possible features of a printer include paper-out detection, duplex printing, and colour printing. Often, new systems are developed by adding features to old ones, a practice which we call "feature integration". When several features are integrated into the same system, they may interfere with each other in undesirable ways; this is called the "feature interaction problem". I will start by reviewing some known examples of feature interaction which have arisen in telecommunications, and some of the approaches to detecting and resolving it. Then I will describe the approach taken by Malte Plath and I, which consists of defining a new language construct for defining features, and the case studies we have examined. The feature construct allows the programmer to override behaviour of the base system. I will describe some of the properties of the non-monotonic inference relation that this induces, and perhaps examine feature integration in a more abstract setting. ----------------------------------------------------------------------------- -- Thu 5 Nov Dr Colin OHalloran, DERA, Malvern Ariane 5, learning from experience In 1996 the first launch of the Ariane 5 rocket ended after 40 seconds with the destruction of the rocket and its payload. The whole Ariane 5 programme was placed in jeapordy and a board of inquiry was set up by the European Space Agency to investigate the cause of the failure and to make recommendations to avoid future failures. Dr O'Halloran from the Defence Evaluation and Research Agency in Malvern was appointed to this board of inquiry. In this seminar he will discuss the causes of the failure, the consequences for the Ariane 5 programme and the lessons to be learnt for all of us. ----------------------------------------------------------------------------- -- Thu 12 Nov Dr Paul Siebert, University of Glasgow and Turing Institute 3D Research and applications at the 3D-MATIC Faraday Partnership Breakthroughs in the ability to capture high resolution 3D geometry and high quality surface texture (photographic appearance) of objects now afford a means of acquiring the raw information necessary to produce photorealisic models of the entire human body and face. However, a number of challenges remain before the dream of constructing completely life-like virtual humans can be realised. The author presents a photogrammetric method for capturing human body and face 3D capture developed by the Turing Institute and the results for the automatic integration of this information into a complete all-round model with seamless texture merging. He would then like to discuss issues and approaches to converting this all-round human model into an animatable virtual human currently under investigation within Glasgow University's 3D-MATIC Faraday Partnership. The presentation will draw upon examples of key research projects and applications being conducted within the 3D-MATIC Faraday Partnership. About 3D-MATIC -------------- The 3D-MATIC Faraday Partnership is a project supported by the Engineering and Physical Sciences Research Council (EPSRC) and administered by the Department of Computing Science, University of Glasgow and the Turing Institute. It is one of four such partnerships in the UK intended to improve links between industry and research in the UK, and 3D-MATIC is the only one based in Scotland. The purpose of 3D-MATIC is to encourage the take-up of 3D imaging technology by industry, particularly small and medium-sized businesses (SMEs). For more details: www.faraday.org , www.turing.gla.ac.uk and www.dcs.gla.ac.uk . ----------------------------------------------------------------------------- -- Thu 19 Nov Dr Mauricio Marin, University of Oxford Adaptive Time Warp Simulation Upon Bulk-Synchronous Parallel Computers Discrete-event simulation is a widely used technique for the study of complex systems. Parallel processing offers the potential for significant reduction of execution times in large scale systems. This talk describes how to synchronise the parallel simulation of events using the Time Warp (TW) protocol and the Bulk-Synchronous Parallel (BSP) model of computing. A BSP-TW protocol that is able to automatically tune its operation to the simulation work-load and follow changes in its evolution is described. The BSP model provides the protocol with scalable performance and portability across diverse parallel architectures. ----------------------------------------------------------------------------- -- Thu 26 Nov Prof. Yorick Wilks, University of Sheffield ***3pm, LW7*** Human-Computer Conversation: where are we? Human-computer conversation is a technology that has reached the same stage of development as some better-known areas of language processing by computer, like machine translation (MT) and information extraction from texts (IE): it is an area of natural language processing (NLP) technology where new and striking developments come from effectively ignoring received theories and wisdoms. It is a truism in science as a whole that this can occur, but in artificial intelligence (AI), of which NLP is part, this often takes the form of heading out towards a practical implementation of a difficult task, with all the risks that such a course of action entails. Recent examples would be the brief flowering of statistically based MT at the end of the 1980's, and the rapid growth of the IE movement at about the same time, a growth that continues. Both those movements effectively ignored the current state of theory and any search for the foundations of the subject, in favour of what one could call having-a-go. This is a n old AI tradition, sometimes called throwaway-AI, or more charitably rapid prototyping. It is widely condemned by theorists of all types, who point out yet again that climbing a tree cannot get one to the moon, even if it feels like a step in the right direction. Interestingly, too, both those movements (statistical MYT and IE) were associated with the development of strong evaluation regimes, imposed by the sponsors of much of the work. Rapid improvements over time were seen, but then these began to fall off and it was again argued how much constant evaluation can stifle theoretical creativity and novelty, all of which is certainly true, though the criticism fails to capture how little theorists had been interested in systems that were evaluable at all until this new pressure appeared. In the talk I shall look at what theory-laden and theory-free approaches have had to offer, and what the role is of competitions like the US-based Loebner competition for the most human-seeming program. ----------------------------------------------------------------------------- -- Mon 30 Nov Dr Paolo Bouquet, University of Trento, Italy ***4pm, Monday*** A Logic of Contextual Reasoning The talk is focused on the role of context in a theory of knowledge representation and reasoning (KRR). The overview of the talk is the following: - first, I will revise some of the motivations that have been proposed for considering context as a key notion in a theory of KRR. I will discuss a variety of issues, including partiality, approximation, perspective, use of different reasoning strategies; - second, I will introduce two new principles of a theory of KRR, called LOCALITY and COMPATIBILITY, and argue that they can be used as a basis for a logic of contextual reasoning which captures all the intuitions discussed in the first part; - third, I will present MultiContext (MC) Systems, a family of logical systems which formalizes the principles of locality and compatibility; - finally, I will consider examples from two important domains, i.e .reasoning about belief and reasoning about action, and show how they can be analyzed in terms of locality and compatibility and formalized using MC Systems. Related work will be discussed throughout the talk. ----------------------------------------------------------------------------- -- Thu 3 Dec Dr Manfred Kerber, University of Birmingham On Knowledge, Strings, and Paradoxes One of the key issues in artificial intelligence is the representation and processing of knowledge. The selection of an appropriate formalism for doing so is a crucial step when building a usable system. In this selection process one tries to find an optimal balance between expressiveness of the system and adequacy of the representation process on the one hand and efficiency and simplicity of the reasoning process on the other hand. Many knowledge representation formalisms are built on top of some logical system, a powerful and well-understood system is classical first-order logic. Since it has some deficiencies, extensions and alternatives have been studied. In particular modal logics have been studied in great detail in recent years. In this talk a system is advocated that is more powerful but simpler than modal logic. It is a simple extension of classical first-order logic, namely first-order logic plus strings. Although known for quite a while and in spite of its positive features, it has not attracted much attention since it is easy to formulate self-referential paradoxes within this system. In the talk the reason for self-referential paradoxes will be studied and a semantical condition on the connectives is given such that these paradoxes can be excluded. This will lead to a powerful three-valued system that makes it possible to use reasoning techniques for classical first-order logic. ----------------------------------------------------------------------------- -- Thu 10 Dec Prof. Graham Birtwistle, University of Leeds Specifying and Verifying TK The talk will present work nigh completed on designing, specifying and verifying the major subsystems of an AMULET-like micro in CCS. Like AMULET1 our micro is 2-phase, but like StrongARM, we have separate instruction memories, and like AMULET3, a wide arithmetic pipeline for greater parallelism. By following an obvious design discipline, and making use of some old theorems on the register bank (from previous work on AMULET1) and some obvious recent ones on pipelines, we have reduced the state minimisation problem by a handsome factor and the whole model now fits comfortably on the Edinburgh CWB. The pipeline theorems hold for 4-phase too. The talk will cover the basic architecture, enough on CCS to get you by, and then detail the 3 major system blocks (fetch unit, arithmetic pipeline, and writeback unit) at the RT level, and how instruction colouring was fettled. The work is being carried out with Matt Morley and Chris Tofts at Leeds University with plenty of help from young Jim Garside at Manchester. Bio: Graham Birtwistle's research interests include asynchronous hardware design, and the design and application of simulation languages. Ever the man to catch the tidal wave of research, his chief claim to fame is that of being the first person to give up object oriented programming (1983). ----------------------------------------------------------------------------- -- Thu 17 Dec Dr Rob Hopkins, Department of Philosophy, Univ. of Birmingham Molyneux's Question William Molyneux famously asked whether a congenitally blind man, restored to sight, would be able to recognize visually shapes familiar to him from touch. It is an empirical matter what the outcome of such an experiment would be, but the question of the significance of the result raises issues which are clearly philosophical. I attempt to disentangle the various issues behind Molyneux's question. I then consider evidence bearing on some of these issues from recent work with the ability of blind people to understand raised-line pictures. -----------------------------------------------------------------------------