'Natural' Heuristic Search Techniques
Mark Nicholson
University of York
Heuristic techniques can be used to find 'good', if not optimal, solutions to problems that can be structured as a function of a set of decision variables and which may be subject to constraints. Such problems may be formulated, in general, as:
| Minimize c(s) such that | |
| g_i(s) >= b_1, | i=1,...,m |
| h_j(s) = c_j, | j=1,...,n |
where s is the vector of decision variables, characterising a solution, which is a member of the set of potential solutions, S. If, for instance, the decision variables are constrained to be discrete we are solving combinatorial optimization problems.
Simple exhaustive searches are not applicable to many of the problems that need to be addressed in computer science. For instance, the task allocation problem incorporates a number of NP-complete problems. Local search techniques, such as neighbourhood search, have been shown to fall into local optima and generally produce poor solutions for examples of this class of problem.
In this talk I will consider a number of approaches that attempt to enhance local searches, in order to escape local optima, and to produce solutions in a reasonable time. Many of the approaches mimic natural processes to enhance the search. Variants include: Simulated Annealing, Tabu Search, Genetic Algorithms, and Artificial Neural Networks. I will show how these 'natural' techniques can be modeled within a single paradigm and how they can be applied to a very wide range of problems.
Intelligent Support for Competitive Telecommunications Services
Trevor Burbridge
University of York
In the future of telecommunications, a vast range of services will emerge from a large number of operators. In a global marketplace, services will compete using mediated transactions in an uncertain environment. In order to gain competitive advantage in such a marketplace, we must be able to implement strategic policies across the spectrum of services. This requires an under- standing of the processes involved, and the ability to monitor and control those factors that affect business.
This talk covers some of the background already presented in the first year student seminar conference, and goes on to identify some of the major problem areas, and to propose a line of research.
Valid Generalisation of Sets and Functions
Martin Anthony
London School of Economics
In this talk, I discuss the basic PAC model of generalisation, applicable to {0,1}-valued functions (equivalently, sets), and some extensions of PAC generalisation to real-valued functions.
The basic PAC model, which will be familiar to some, is defined and the importance of the Vapnik-Chervonenkis dimension is highlighted. Approaches to developing corresponding notions for classes of real functions are discussed. Recent results on `generalisation from interpolation' are presented.
Industrial Exploitation of Prolog
Clive Spenser
Logic Programming Associates
Towards Process-theoretic Planning
David Pym
Queen Mary and Westfield College, University of London
We propose a representation for plans and actions based on the algebraic theory of processes. We argue that the basic building blocks of plans should be the processes by which changes occur rather than the more widely used state-change representation of actions. Our emphasis is on the demands that the execution of plans makes on their representation. We describe a simple algebra of plans, based on process-combinators, and show it to be adequate for a wide variety of the plans found in the literature. We discuss the implications of this type of plan representation and outline its advantages for meta-reasoning, including plan-comparison and plan-construction.
?
Mike Brown
?
How to Extract Cube-Routes
Rob Dormer - rdd@minster.york.ac.uk
University of York
A hypercube domain is a graph, the nodes of which represent the vertices of an n-cube. Only those pairs of nodes denoting adjacent vertices may be connected by directed arcs. A subset of the nodes are distinguished as being 'goal nodes'.
We are investigating the problem of synthesising search algorithms for simple classes of hypercube domains. These algorithms generate minimal paths connecting randomly chosen nodes with goal nodes. The approach we take is inductive in that the synthesis process generalises from random samples of example paths. We exploit results and techniques from the burgeoning field of PAC-learnability theory to quantify the efficiency and accuracy of induction.
In this talk I will summarise the preliminary results we have obtained, and identify promising new lines of future investigation.
On Concept Space and Hypothesis Space in Case-Based Learning
Algorithms
Tony Griffiths
University of York
In order to learn more about the behaviour of case-based reasoners as learning systems, we formalise a simple case-based learner as a PAC learning algorithm. We show that the case-based representation <CB,s> is rich enough to express any boolean function. We define a family of simple case-based learning algorithms which use a single, fixed similarity measure and we give necessary and sufficient conditions for the consistency of these learning algorithms in terms of the chosen similarity measure. Finally, we consider the way in which these simple algorithms, when trained on target concepts from a restricted concept space, often output hypotheses which are outside the chosen concept space. A case study investigates this relationship between concept space and hypothesis space and concludes that the case-based algorithm studied is a less than optimal learning algorithm for the chosen, small, concept space.
Heterogeneous Knowledge Manipulation Systems
Derek Bridge - dgb@minster.york.ac.uk
University of York
Participating in MUC-6 with the LaSIE System
Robert J. Gaizauskas
University of Sheffield
Within the NLP community `information extraction' (IE) has come to refer to the activity of processing large volumes of short natural-language texts, typically newswire reports, and extracting from them prespecified key information. Research in this area has been stimulated over the last eight years by a series of quantitative evaluation exercises for IE systems called `Message Understanding Conferences' (MUC), organised by ARPA in the US. These have slowly moved from being peripheral events, attended by a few specialist NL researchers, to being central activities which are strongly influencing the direction and the character of NL research. MUC-6, the most challenging of these evaluations yet, is currently under way and the University of Sheffield is participating with a system called LaSIE (Large Scale Information Extraction from Text).
In this talk I shall first give a brief overview of MUC-6, describing its component tasks, resources, and scoring methodology. Then the architecture for the LaSIE system will be introduced and each of its components considered in turn. LaSIE's overall approach involves partial parsing using a corpus-derived feature-based grammar and the use of a powerful world model to perform reference resolution and other discourse-related tasks. LaSIE is still very much under development, so only preliminary results can be presented. The talk will end by considering the challenges with which we are currently wrestling.
Cognitive Robotics -- Integrating Reasoning, Perception and Action
Ray Reiter
University of Toronto (Canada)
| The overhead slides of this lecture are avaliable (in postscript) | |||||
| A videotape of this lecture is available from the library of | |||||
|
Virtually all current research in robotics concerns basic level tasks like sensory processing, path planning, manipulator design and control. In contrast, cognitive robotics is concerned with endowing a robotic agent with higher level cognitive functions that involve reasoning, for example, about goals, actions, when to perceive and what to look for, and the cognitive states of other agents. In short, cognitive robotics is concerned with integrating reasoning, perception and action within a uniform theoretical and implementation framework.
This talk will describe the approach to cognitive robotics being developed by Prof. Reiter and his colleagues (Yves Lesperance, Hector Levesque, Fangzhen Lin, Daniel Marcu and Richard Scherl). This consists of a theory of complex actions, including perceptual actions, and their effects on the world and on an agent's mental state. These theoretical considerations lead to GOLOG, a novel logic programming language suitable for discrete event simulation and high level robot control.
What is STRIPS? -- Semantics for Planning Systems
Ray Reiter
University of Toronto (Canada)
Although STRIPS has been an extremely influential technique for plan generation ever since its introduction 24 years ago, its logical semantics has been problematic. There have been many proposals in the literature, most of which have in common a reliance on meta-theoretic operations on logical theories in order to capture the add and delete lists of STRIPS operators. Alas, it has never been clear exactly what these add/delete operations correspond to declaratively, especially when they are applied to logically incomplete theories. This talk shall provide a semantics for STRIPS-like systems in terms of a purely declarative situation calculus axiomatization for actions and their effects. The intuition leading to this semantics is that STRIPS is a mechanism for computing the progression of an initial situation calculus database under the effects of an action. This idea will be illustrated by describing two different STRIPS mechanisms, one of which admits open world databases, and proving their correctness with respect to their situation calculus specifications. En route, we shall discover some intriguing connections with relational database theory and the notion of what it means for a logical theory to forget some of its information. (Joint work with Fangzhen Lin.)
Machine Learning Using the Case-Based Representation
Tony Griffiths
University of York
In this talk I will summarise results from our work in which we attempt to understand better the adaptive behaviour of a case-based reasoning system by considering the pair <CB,s> of case-base and similarity measure as a representation to be manipulated by a machine learning algorithm. This allows case-based reasoning systems to be compared with better understood means of `learning from experience' within the PAC learning framework. The results will be reported in three sections. Firstly I will describe some partial results which we have been able to establish which have implications for the learning behaviour of a simple case-based learner. Secondly, I will consider a special case of this original framework which is significant because on the one hand it simplifies issues of representation enough for additional results to be acheived and on the other because it demonstrates the operation of inductive bias in a case-based learner. Finally I will describe our most recent work concerning a two-fold generalisation of the concept learning framework assumed in the first two sections. In this final section of work we drop the notion that the `target concept' for the learner is a {0,1}-valued function and consider instead the learning (using the case-based representation) of a possibly relational mapping to a large but finite range.
Ordering Constrained Formulas
Alan Frisch
University of York
Instantiation orderings over formulas (the relation of one formula being an instance of another) have long been central to the study of automated deduction and logic programming, and are of rapidly-growing importance in the study of database systems, machine learning, and computational learning theory. A variety of instantiation orderings are now in use, many of which incorporate some kind of background information in the form of a constraint theory. Even a casual examination of these instantiation orderings reveals that they are somehow related, but in exactly what way?
This talk presents a general instantiation ordering of which all these orderings are special cases, as are other instantiation orderings. The talk shows that this general ordering has the semantic properties we desire in an instantiation ordering, implying that the special cases have these properties as well. The extension to this general ordering is useful in applications to inductive logic programming, automated deduction and logic programming, knowledge-base vivification, and database systems.
Complete University Modular Timetabling using Constraint Logic Programming
Gyuri Lajos
University of Leeds
In preparation for the changeover to a new modular degree structure, at the University of Leeds, a new modular timetable for the 1993-94 academic session had to be constructed from scratch. In my talk I will describe our experience in constructing a large scale modular timetable using Constraint Logic Programming techniques.
Learning to break simple ciphers
Robert Dormer
University of York
In this talk Robert will discuss the application of computational learning theory techniques to the statistical analysis of simple cipher breaking schemes. The ciphers considered are constructed from transposition and substitution functions. The ciphers are broken by an attack from (plaintext,ciphertext) pairs.
Update Plans - a high level low level specification language
Hugh Osborne
University of York
Abstract
An Overview of Inductive Logic Programming Systems
Simon Anthony
University of York
This talk aims to provide a relatively high level overview of Inductive Logic Programming - a new research area formed from ideas in Machine Learning and Logic Programming. Initially, some motivation for studying ILP will be provided before focussing on particular ILP systems. The underlying theories of ILP will be drawn out and discussed, with the relative strengths and weaknesses of the competing approaches highlighted. Successful applications of ILP systems in interesting real-world domains will be briefly examined and some concluding remarks will complete the talk.