DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF YORK
INTELLIGENT SYSTEMS GROUP
OPPORTUNITIES FOR
POSTGRADUATE STUDY IN ARTIFICIAL INTELLIGENCE
The Intelligent Systems Group in the Department of Computer Science at
the University of York would like to hear from exceptional candidates
interested in pursuing a postgraduate research degree (MSc, MPhil,
PhD) in areas related to the Group's research interests as outlined on
the following pages.
The Department has a number of EPSRC-funded fellowships for doctoral
candidates and another fellowship that, unlike EPSRC fellowships,
provides a stipend to nationals of any EC country.
The Department of Computer Science at the University of York provides
an outstanding environment for research and postgraduate study. The
Department is one of the few computer science departments in the UK
whose research has been awarded the top rating of "5" in the most
recent Research Assessment Exercise and whose teaching has been
awarded the top rating of "excellent" in the HEFCE Teaching Quality
Assessment. Based on its evaluation of the Department's research
programme, the EPSRC has increased the Department's allocation of
research studentships over the past few years, while nationally the
total number of studentships has declined. The Department's doctoral
program has maintained an extremely high graduation rate: in recent
years almost all EPSRC-supported students have submitted a thesis
within four years and earned a doctoral degree.
Further information on the Group, as well as the Department, can be be
accessed on the World Wide Web via URL
http://dcpu1.cs.york.ac.uk:9876/isg/home.html
Those wishing to discuss opportunities for postgraduate studies within
the Intelligent Systems Group should contact either Alan Frisch
(frisch@minster.york.ac.uk, +44 1904 432745), Derek Bridge
(dgb@minster.york.ac.uk) or Suresh Manandhar
(suresh@minster.york.ac.uk) by email or at the Department of Computer
Science, University of York, York YO1 5DD, UK.
General enquiries about the postgraduate programmes of the Department
of Computer Science should be made to Maggie Burton
(maggie@minster.york.ac.uk) by email or at the above postal address.
------------------------- + -------------------------
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF YORK
INTELLIGENT SYSTEMS GROUP
The research of the Intelligent Systems Group is concerned with the
theoretical principles of artificial intelligence and their application
to real-world domains. The Group's research focuses on three core areas
of artificial intelligence--knowledge representation and reasoning,
machine learning and natural language processing--though most of the
Group's projects span these areas.
KNOWLEDGE REPRESENTATION AND REASONING is the area of study concerned
with determining what knowledge a system requires to produce a certain
behaviour, how this knowledge can be encoded and structured for rapid
access, and how a system can reason with what it knows.
We have developed a framework for enhancing general-purpose
deductive systems by embedding into them powerful, special purpose
constraint-solving methods. Using this framework, we have developed and
studied reasoning systems for knowledge retrieval, constraint logic
programming, modal logic deduction, parsing feature-based grammars,
inductive learning and planning. In addition to furthering this
research, we are investigating constraint-solving algorithms.
MACHINE LEARNING is the area of study concerned with how a computational
system can acquire knowledge by learning from its experiences and
observations.
Intuition tells us that a system can learn by generalising what it
knows or observes. We have been studying this intuition and its
computational consequences in a mathematically rigorous manner. We have
formalised the notion of generalisation, studied algorithms for
computing generalisations, and identified conditions under which
generalisation is an effective mechanism for learning.
A major challenge of artificial intelligence is the construction of
systems that can find efficient plans of action for accomplishing given
tasks. We are developing, and studying the complexity of, algorithms
that learn to plan efficiently from examples of optimal plans.
Case-based reasoning (CBR) systems solve new problems by analogy to
past problems. The theoretical framework we are developing answers
questions such as whether the accuracy of these systems necessarily
improves as more problems are encountered. We are also developing novel
CBR architectures and applying CBR to a number of real domains.
NATURAL LANGUAGE PROCESSING research investigates computational methods
for understanding and generating human language and has important
applications in document processing and user interfaces.
We are developing languages for stating the morphological, syntactic
and semantic constraints central to modern grammatical theories. We are
also developing efficient algorithms for reasoning with these
constraints.
By combining our work in natural language processing with our
expertise in machine learning we are developing methods for learning
large-coverage grammars (semi-)automatically from large collections of
text. We have already shown how inductive and deductive learning
techniques can be combined to give a system that can learn parts of a
high quality, wide-coverage natural language grammar.
RESEARCH ACTIVITIES
The members of the Intelligent Systems Group have been highly active,
supervising the completion of six PhD students--all of whom now hold
university positions--patenting an architecture for generating
navigation directions in natural language, and currently producing their
third book. The group has attracted research grants for four projects,
one studying methods for representing and reasoning about changing
requirements, one studying distributed architectures for case-based
reasoning, and two studying applications of case-based reasoning.
The ISG maintains close contacts with leading researchers and research
groups, both nationally and internationally. During the past three
years the group hosted approximately 25 visiting speakers from the UK,
US, Canada, Germany, Australia and the Netherlands. The ISG is a member
of ESPRIT's COMPULOG NET, the Network of Excellence in Computational
Logic. The group co-sponsored AISB's First Workshop on Automated
Reasoning and hosted the Fourth European Workshop on Logics in
Artificial Intelligence.
The ISG has particularly good links with the nearby Division of
Artificial Intelligence at the University of Leeds. In addition to
conducting collaborative research, the two groups co-sponsor a number of
events including the Annual Knowledge Representation and Reasoning
Distinguished Lecturer, inviting a leading international AI researcher
to visit and speak at the two universities.
At York, the ISG collaborates with researchers in the Dept. of
Linguistics and in other groups in the Dept. of Computer Science,
including the High-Integrity Systems Engineering Group, the Human
Computer Interaction Group, and the Advanced Computer Architectures
Group.
ACADEMIC AND RESEARCH STAFF
Derek Bridge, Lecturer. (dgb@minster.york.ac.uk) Natural language
processing, case-based reasoning.
David Duffy, Research Associate. (dad@minster.york.ac.uk) Automated
reasoning and requirements analysis, proof by induction.
Alan Frisch, Reader in Intelligent Systems. (frisch@minster.york.ac.uk)
Automated reasoning, constraint solving, constraint logic
programming, knowledge representation.
Suresh Manandhar, Lecturer. (suresh@minster.york.ac.uk) Natural language
processing, constraint programming, knowledge representation.
Hugh Osborne, Research Associate. (hugh@minster.york.ac.uk) Novel
applications of formal methods, especially to case-based
reasoning.
FURTHER INFORMATION
Further information and research papers can be accessed on the World
Wide Web at URL http://dcpu1.cs.york.ac.uk:9876/isg/home.html. To
discuss educational and research opportunities contact Alan Frisch
(phone: +44 1904 432745) or any members of the group at either the email
address listed above or at The Department of Computer Science,
University of York, Heslington, York YO1 5DD, United Kingdom.
------------------------- + -------------------------
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF YORK
INTELLIGENT SYSTEMS GROUP
ONGOING RESEARCH PROJECTS
This document provides brief descriptions of research projects that
are representative of those conducted within the Intelligent Systems
Group. For convenience the document is divided into three
sections--knowledge representation and reasoning, machine learning,
and natural language processing--although there is significant overlap
among these.
KNOWLEDGE REPRESENTATION AND REASONING
DEDUCTION WITH CONSTRAINTS
Alan Frisch
One of the most widely-used and successful approaches to
increasing the efficiency of general-purpose automated reasoning
systems has been that of integrating special-purpose reasoning systems
into them, resulting in what are often called hybrid reasoning
systems. Though the resulting hybrid reasoning systems are appealing,
their construction and analysis can be difficult. Our research helps
to remedy this problem for a particular class of hybrid reasoners that
we have identified and dubbed ``substitutional reasoners''.
Substitutional reasoners share certain architectural features;
most notably they (1) operate on a language that contains a
distinguished set of symbols for representing constraints on the
values over which quantified variables range, and (2) employ a special
purpose reasoning system to test the satisfiability of these
constraints. One of the distinguishing features of substitutional
reasoners is that the constraints are manipulated exclusively by the
special-purpose reasoner.
Though the substitutional architecture has been one of the most
common and successful architectures for hybrid reasoning, our research
is the first to identify these reasoners as a single class and to
investigate their common properties and the general principles that
underly them. Our results support a framework that enables the
systematic production of substitutional reasoners and their
completeness proofs from certain kinds of non-hybrid reasoners and
their completeness proofs.
Within the substitutional framework we have studied reasoning
systems for knowledge retrieval, constraint logic programming, modal
logic deduction, parsing feature-based grammars, inductive learning
with background information and planning in temporally rich domains.
CONSTRAINT SOLVING
Alan Frisch
In contrast to our results on deduction with constraints, which
have been obtained by abstracting away from algorithmic issues and
concentrating on architectural issues, we are taking a growing
interest in constraint-solving algorithms. Our previous work has
studied sorted unification, an operation that lies at the heart of all
automated deduction systems for sorted logic, and which can be seen as
jointly solving membership and equational constraints.
Our current work studies the relationship of deduction to the
problem of simultaneously satisfying a set of symbolic constraints on
finite domains. Future efforts will concentrate on integrating
deductive methods and traditional constraint satisfaction techniques
to effectively solve large constraint satisfaction problems.
REASONING ABOUT CHANGING REQUIREMENTS
David Duffy
This project is concerned with the representation of requirements
and design decisions, and the rationale associated with them, in a way
that is amenable to automated reasoning. The goal is to develop a
methodology both for reasoning about the implications (and hence
costs) of changes to requirements, and for assessing the opportunities
for changes in order to adapt and improve system designs. Early work
concentrated on the development of a goal-based framework for
combining informal and formal representations of requirements and
ensuring their integrity. Subsequently, we have focused on the
problems of extracting formal descriptions from requirements expressed
using controlled natural languages, and the use of proof mechanisms
for assessing the sensitivity of requirements to change. This work
forms part of a broader project (in conjunction with the High
Integrity Systems Group at York, with Newcastle and Loughborough
Universities and with a number of industrial partners) on processes
for dealing with changing requirements, which is now coming to
completion.
KNOWLEDGE-BASED SYSTEMS DESIGN
Derek Bridge, Hugh Osborne
Our early work included the use of object-orientation to structure
logic databases, but more recently all our work has taken on a
case-based reasoning (CBR) flavour.
A short project with BT Plc investigated how the services provided
by Help Desks could be improved by the use of knowledge based
techniques. We built a small prototype system which used CBR to assist
a Help Desk Operator carry out a partial diagnosis of a customer's
problem. Subsequent work, carried out in the Human-Computer
Interaction Group undertook the formal specification, using Z, of a
variety of properties of case-based systems. These specifications gave
insight into the `space' of possible case-based systems, and
elucidated human interaction properties.
Finally, in collaboration with the Advanced Architectures Group,
we are working on a project entitled `Architectures for Heterogeneous
Knowledge Manipulation Systems', which is part of the EPSRC-funded
special research programme Architectures for Knowledge Manipulation
Systems. The knowledge-based systems side of this project will
characterise functional properties of stand alone CBR systems and the
circumstances under which these properties are preserved in integrated
systems and in distributed environments. The properties will be
characterised both formally and empirically. So far we have devised a
rich set of human-interpretable similarity measures and derived normal
forms for these that allow their parallel evaluation. Industrial
support for the project comes in the form of a PARAMID multi-processor
from Transtech Ltd., and the supply of example data from a U.K. bank.
In the future, we intend to continue to blend both formal and
empirical methods in our research in this area.
MACHINE LEARNING
LEARNING TO PLAN AND ACT
Derek Bridge, Robert Dormer, Klaas Schilstra
Planning has traditionally been treated within the artificial
intelligence community with a focus on search: finding a sequence of
operators which will transform an initial state into a goal state.
For complex systems, however, the computational cost of this approach
is prohibitive. Humans on the other hand are able to plan in complex
environments, by using skills and techniques learned from analogous
situations that have been encountered previously. The aim of this work
is to investigate the use of learning techniques, such as inductive
logic programming, for improving the efficiency of logic-based
planners. We are also looking at the use of statistical learning
theories (such as PAC learning) to obtain bounds on problem
complexity.
More recently, we have turned to case-based reasoning and learning as
a way of furnishing planners with knowledge of plan execution
experience that can be used to build more robust plans.
CASE-BASED LEARNING
Derek Bridge, Tony Griffiths
Using the PAC-learning model of machine learning, we are attempting
to answer questions such as whether the performance of a case-based
reasoning system necessarily improves as more cases are added to the
case base. In particular, we have formalised the knowledge content of
case-based systems, shown that they often have concept spaces that are
different from their hypothesis spaces, and shown how the similarity
measure encodes learning bias. More recently we have described two
algorithms whose average-case learning behaviours (which we have been
able to characterise precisely) we propose should act as yardsticks
against which the observed performance of case-based learners can be
measured.
INDUCTIVE CONSTRAINT LOGIC PROGRAMMING
Alan Frisch, Simon Anthony
Inductive Logic Programming (ILP) is concerned with learning logic
programs from sets of examples and, often, some background knowledge.
Though ILP systems have been applied with great success to a number of
real-world problems, they inherit some of the shortcomings inherent in
the traditional logic programming paradigm. In particular, with
traditional logic programming languages it is difficult to naturally
express computations over domains other than the Herbrand universe
(the set of variable-free logical terms). Thus logic programming
languages usually require extra-logical constructions to express
operations such as arithmetic ones. Consequently, the major results
of ILP, which are formulated for pure logic programs, cannot be
applied directly to non-Herbrand domains.
Constraint logic programming generalises the ideas of ordinary
logic programming to allow computation over non-Herbrand domains in a
principled and natural manner. This is achieved by replacing the
unification procedure of ordinary logic programming with more general
constraint-solving mechanisms.
Our research is attempting to take the the major ideas and results
from ILP and generalise them to the learning of constraint logic
programs. Our goal is to demonstrate that the resulting
enterprise--Inductive Constraint Logic Programming--provides useful
methods for learning in non-Herbrand domains such as numerical
domains.
NATURAL LANGUAGE PROCESSING
CONSTRAINT LOGICS FOR NATURAL LANGUAGE PROCESSING
Suresh Manandhar, Alan Frisch
Ambiguity arises at all levels of linguistic
knowledge--morphology, phonology, syntax, semantics and discourse. A
natural language processing system incurs heavy penalties if its
implementation does not employ a representation that is largely
non-committal. Our recent work has focussed on the use of
underspecified representations to represent and reason efficiently
with ambiguities. We have developed constraint logics that provide
logically sound and efficient mechanisms to represent and reason with
such underspecified structures.
Our future work will concentrate on formulating a general purpose
constraint-solving scheme suitable for specifying complex
constraint-based grammars for use in a generic parsing and generation
architecture. We will also attempt to develop a hybrid constraint
logic that combines constraint reasoning with probabilistic
information. Such a logic could be used to obtain the most probable
interpretation of a highly ambiguous representation. Our goal is to
specify and implement a future proof formalism that subsumes current
constraint-based formalisms by allowing development of large hybrid
constraint-based grammars.
MACHINE LEARNING OF CONSTRAINT-BASED GRAMMARS
Suresh Manandhar, Derek Bridge
Modern constraint-based grammatical theories, such as Head-driven
Phrase Structure Grammar (HPSG), employ a complex range of constraints
for representing linguistic knowledge. On the one hand, such a rich
grammatical theory makes it possible to write grammars that contain
very rich linguistic knowledge. On the other hand, it is not entirely
clear how constraint-based grammars can be learned
(semi-)automatically from large corpora. This means that there is a
need to study the complexity/learnability divide and come up with a
refined but equally expressive grammatical theory that has the
advantage of being acquired automatically from corpora.
Our efforts so far have been devoted towards combining deductive
and inductive techniques for learning unification grammars in the
style of Generalised Phrase-Structure Grammar. This approach was
successful in learning grammars that reduced overgeneration and
undergeneration, and which assigned linguistically plausible analyses
to sentences.
Future work will build on our past work and other existing work in
corpus linguistics, constraint-based grammars, knowledge
representation and machine learning with a view to learning HPSG-style
unification grammars.