NL-KR Digest, Volume 15 No. 24

Skip to first unread message

Al Whaley

May 14, 1996, 3:00:00 AM5/14/96

NL-KR Digest Tue May 14 07:30:27 PDT 1996 Volume 15 No. 24

Today's Topics:

Position: University of Rochester Post Doc in Language
Announcement: Research Studentship available in NLP, York
CFP: PAKM Wkshp Information Filtering, Oct 96, Basel

* * *

Subcriptions: listserv-style administrative requests to
Submissions, policy, questions:
To speed up processing of your submission write to with the message:
GET nl-kr style

Back issues:
Gopher:, Port 70, in directory /pub/nl-kr
Email: write to LIST...@AI.SUNNYSIDE.COM, omit subject, mail command:
GET nl-kr nl-kr_file_list
Al Whaley ( and
Chris Welty (


Date: Sun, 5 May 1996 14:36:32 -0400
From: (James Allen)
Subject: Position: University of Rochester Post Doc in Language

Post-Doc Position at the University of Rochester

The Center for Language Sciences at the University of Rochester anticipates
having one NIH post-doc available beginning July 1. The center brings
together faculty and students with interests in spoken and signed languages
from the departments of Linguistics, Computer Science, Brain and Cognitive
Sciences and Philosophy; and the interdisciplinary programs in Cognitive
Science and Neuroscience. We will consider applicants from any of the
disciplines who are interested in contributing to an interdisciplinary
language community. However, we are particularly interested in
post-doctoral fellows who have interests in computational approaches to
language, including both stochastic and traditional approaches in
computational linguistics and natural language processing.

Applications should be sent to James Allen, University of Rochester,
Department of Computer Science, Computer Studies Building Rochester, NY
14627. Include a vita, sample reprints and/or pre-prints, a statement of
research and training interests, and arrange for letters of reference from
at least three referees. Applications must be citizens or permanent
residents of the USA. Applications will be considered as soon as they are
complete. The University of Rochester is an equal opportunity employer. We
encourage applications from women and from minorities.


Date: Tue, 7 May 96 15:39:53 BST
From: Suresh Manandhar <>
To: DG-...@UGA.CC.UGA.EDU,,,
Subject: Announcement: Research Studentship available in NLP, York





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

Those wishing to discuss opportunities for postgraduate studies within
the Intelligent Systems Group should contact either Alan Frisch
(, +44 1904 432745), Derek Bridge
( or Suresh Manandhar
( 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
( by email or at the above postal address.

------------------------- + -------------------------



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.

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
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
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.


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


Derek Bridge, Lecturer. ( Natural language
processing, case-based reasoning.
David Duffy, Research Associate. ( Automated
reasoning and requirements analysis, proof by induction.
Alan Frisch, Reader in Intelligent Systems. (
Automated reasoning, constraint solving, constraint logic
programming, knowledge representation.
Suresh Manandhar, Lecturer. ( Natural language
processing, constraint programming, knowledge representation.
Hugh Osborne, Research Associate. ( Novel
applications of formal methods, especially to case-based


Further information and research papers can be accessed on the World
Wide Web at URL 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.

------------------------- + -------------------------




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.


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.

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.

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

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.


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

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.

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

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


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.

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.


Date: 08 May 1996 14:16:03 +0000 (GMT)
Subject: CFP: PAKM Wkshp Information Filtering, Oct 96, Basel

Call for Papers

Workshop on Practical Applications of Information Filtering

to be held in conjunction with

First International Conference on Practical Aspects of Knowledge Management

Basel, Switzerland

October 30-31, 1996

Information filtering is an aspect of knowledge management which has been the
focus of concerted research in recent times. This has arisen because of the
increasing volumes of electronically stored information being made available.
Unlike information retrieval or data mining, both of which address problems
associated with static document databases, filtering applies to transiently
occurring information on a computer network. The basic aim of information
filtering is to route through to a user those source documents deemed relevant
to his/her needs, possibly ranking them by estimated relevance; documents
deemed not to be relevant are filtered out. Estimation of relevance is carried
out by comparing a user profile - embodying knowledge of a userUs ongoing
interests - with incoming documents in an information stream. It may be
expected that, as a userUs interests change or evolve, the corresponding user
profile is adjusted accordingly.

Example user scenarios in which information filtering would be an appropriate
tool might include the following:

- A journalist in a newsroom may be following developments of a certain
story - or particular aspects of a story - over a prolonged time period.
As such, he/she may wish to have relevant newswire articles filtered
through. Also, as certain aspects of the story begin to assume
importance to the journalist, the nature of articles received might be
expected to change.

- A financial institution trades stock internationally. Beside the normal
world-wide monitoring of stock exchanges, it also needs to have knowledge
of world events which might affect stock prices: weather conditions in a
particular location; earthquakes; military coups; government changes or
collapses; interest rate changes. Toward this end, the institution may
employ people to monitor the API and FT newswires, pertinent USENET
Newsgroups, etc.

- The manager of the Information Systems division of a company needs to
keep up to date regarding the relative benefits of a competing range of
software and hardware products. To do this, he/she wishes to monitor
computer mailing lists and USENET News to locate articles containing
meaningful comparisons. As with the other cases, the important issue is
that only relevant articles are presented, with irrelevant contributions
screened out, i.e., filtering takes place on the incoming information.
Also, as the manager's needs change (e.g. a hardware purchase is made or
a software product is eliminated from further consideration), the nature
of information being routed through should automatically adapt.

The purpose of this workshop is to examine currently available practical
applications of information filtering, to assess the impact of the technology,
to evaluate its successes and failures and to appraise its future utility as
a practical application of knowledge management. Papers are invited on any
aspect of information filtering, but emphasis will be placed on real-world
systems and approaches. It is thus desirable that the paper be linked to some
specific user scenario, such as one of those listed above. A non-exhaustive
list of topics is included below:

* Applications of Filtering * Filter System Architectures
* Profile / Document Representation * Profile / Document Comparison
* Profile Adaptation * Profile Optimisation
* User Interfaces * User Modelling
* Evaluation Techniques * Multimedia/Hypermedia Filtering

Paper Submission Details:
Paper Length: 5000 words maximum
Submission Date: June 28, 1996
Notification of Acceptance: August 1, 1996
Final Papers Due: September 15, 1996

Software demonstrations related to the workshop topics are also encouraged.
These may or may not be associated with a paper being presented. Conference
organisers will provide a room where such demonstrations can be given during
lunch breaks and at other times. Lunch, exhibitions and demonstrations will
take place in the same or adjacent rooms.

Submission deadlines for software demonstrations are as for papers, given

Beside being open to people presenting papers and demonstrating systems, the
workshop will be open to practitioners interested in concretely applying
information filtering strategies. Workshop participants presenting a paper
will, however, qualify for a reduced conference fee. Refer to the main
conference's general information (URL below) for participation details.

Alan Smeaton Humphrey Sorensen
School of Computer Applications, Computer Science Department,
Dublin City University, University College,
Dublin 9, Cork,
Ireland. Ireland.

Web Information on PAKM Conference:

End of NL-KR Digest

Reply all
Reply to author
0 new messages