🚀 go-pugleaf

From: "Alfred Kobsa" <ak@sbsvax.uucp>
To: mod-ki@unido.uucp
Date: Fri, 24 Nov 89 22:48:56 +0100 (MET)
Subject: Workshop on Term Subsumption Languages in KR
Keywords: Berichte

mod-ki message 0336
************************************************************************
              Workshop on Term Subsumption Languages
                    in Knowledge Representation
 
              Thorn Hill Inn, Jackson Village, NH, USA
                          Oct. 18-20, 1989
 
          Bernd Owsnicki-Klewe              Alfred Kobsa
     PHILIPS Research Lab, Hamburg   CS Dept., Univ. of Saarbrucken

The   workshop   on   "Term   Subsumption   Languages    in    Knowledge
Representation", sponsored by AAAI, was held from Oct. 18-20 at the  Inn
at Thorn Hill, located in the White Mountain region  in  New  Hampshire,
USA. It was organized by Peter F. Patel-Schneider  of  AT&T  Bell  Labs,
Marc Vilain of MITRE, Ramesh S. Patil of MIT, and Bill Mark of  Stanford
University.

The workshop brought together about 30 researchers in the field who came
from the United States, Germany, Austria, Italy, Canada and  Korea.  Its
primary goal was to review the field after about 10 years  of  work,  to
exchange ideas and to set up research directions for the future.

 
Term Subsumption Languages

This term (which will be abbreviated to "TSL"  throughout  this  report)
refers to  all  kinds  of  knowledge  representation  systems  based  on
Brachman's original idea of KL-ONE. In the last five years many  systems
based on this  ideas  have  emerged,  like  KRYPTON  (Levesque),  KL-TWO
(Vilain), NIKL (Neches, Schmolze),  BACK  (Luck,  Nebel,  Schmiedel  and
Peltason), MESON (Owsnicki-Klewe),  SB-ONE  (Kobsa),  LOOM  (MacGregor),
QUIRK  (Bergmann,  Gerlach,  Poesio),  and   CLASSIC   (Patel-Schneider,
Resnick, McGuinness).

These systems usually employ a formal "Term Description Language", and a
mechanism that decides about  subsumption  relationships  between  these
terms (the so-called `classifier'). Almost all of them have incorporated
assertional languages that enable the systems to reason about  instances
of terms. Historically, term subsumption languages are a  generalization
of both semantic networks and frames, equipped  with  a  model-theoretic
semantics.


Outline of the workshop

The workshop was divided into six plenary sessions, and  three  sessions
with three parallel tracks aimed at  in-depth  discussions  of  a  small
number of participants. Each session was introduced  by  short  position
statements (at least they were encouraged to be short!) and enough  time
was left for intensive discussions. Since some of the sessions could not
be completed within the allotted time-frame, they had to be continued in
the evenings.


Report on the sessions

The workshop started with introductory  statements  which  outlined  the
scope of problems in the field:

Ramesh Patil (MIT) spoke on behalf of the system users. He advocated the
idea of "Knowledge Representation as a Service": KR systems should offer
specialized  services  for  the  application  designer   in   terms   of
definitions, assertions and queries (as opposed to XPS-shells  in  which
KR dominates the applications). His claim was  that  KR  systems  suffer
from lack of knowledge about what the user wants to do with  an  answer,
thus being forced to do almost complete deductions even in  cases  where
an incomplete but fast answer would be preferable. He pointed  out  that
it is not sufficient  to  look  for  local  runtime  optimization  only;
instead, the overall performance of the system should be improved.

Bill Swartout (ISI) reported on his experience with  the  NIKL  systems,
which he used to provide  enhanced  explanation  facilities  for  expert
systems. He -- like many participants --  questioned  an  overly  strict
distinction between  terminological  and  assertional  reasoning  within
these systems as being hard to comprehend, incoherent, and  an  obstacle
to  rich  expressiveness.  He  criticized   that   the   importance   of
classification had been overrated until now, and -- as did Ramesh  Patil
-- questioned the point of complete inferences which are traded  in  for
limited expressiveness. Such an approach enforces "model hacks"  of  the
user which make it impossible to generate  explanations.  Swartout  also
presented some design ideas of his HIFI system which is supposed to be a
user-configurable problem solver.

Bob MacGregor (ISI), the main developer  of  LOOM,  took  up  Swartout's
critique of classification and pointed out that modern  term  definition
KR systems tend to  put  strong  emphasis  on  capabilities  other  than
classification.  Such  services  include  forward  chained   inferences,
semantic   unification,   inconsistency    detection,    object-oriented
programming and the integration of highly tuned and fast special-purpose
reasoners. He emphasized his opinion that this technology could serve as
a good basis for both next-generation expert systems or very high  level
programming languages, the main obstacle being the lack  of  integration
with existing  tools,  databases  and  programming  languages.  He  also
pointed out that, in the last  few  years,  TSL  became  more  and  more
similar with Guiseppe Attardi's OMEGA language, and suggested that  this
relationship should be more thoroughly investigated.

Bernhard Nebel (IBM, Germany) reviewed the  broad  theoretical  work  on
TSLs, which in the past years focused  on  analyzing  computability  and
computational complexity of  the  subsumption  problem  for  differently
expressive  languages.  Recent  results  showed  that   all   reasonable
terminological  languages  have  the  property   of   being   worst-case
intractable, i.e. a complete algorithm may come up with  an  exponential
time behavior. He proposed as a new direction an  analysis  of  "normal"
and "average" cases, since exponential time  consumption  occurs  rarely
in practical applications.

The  section  on  "Using  Systems  based   on   terminological   logics"
(Moderator: Ramesh Patil) gave some impression of the structure and  the
usage of developed terminological knowledge bases. Lewis Norton  briefly
reported on a knowledge base in the KNET formalism which is  planned  to
be used for hardware configuration. This knowledge base  contains  about
2000 concepts and 150 different roles, each concept possessing about  35
roles on an average. The depth of the hierarchy is  below  10,  and  the
classifier is not frequently employed by users. Ramesh  Patil  estimated
that, in a large knowledge base he is familiar with, 75% of the concepts
are primitive because  of  the  limited  expressive  power  of  the  TSL
employed. He therefore strongly opposed any attempt to further  restrict
the  expressiveness  of  TSLs.  Marc  Vilain  reported   that   in   his
natural-language  parser  nearly  100%  of  the  interaction  with   the
terminological knowledge base was  classification,  while  Alfred  Kobsa
estimated  that  in  the  XTRA NL  system  (which   also   comprises   a
natural-language generator and a user modeling  component)  this  amount
does not exceed 20-30%.

In the session on "What Expressive Power is Desirable?" (Moderator:  Jim
Schmolze), a great number of new representational elements  were  listed
which  one  would  like  to  see  in  enhanced  TSLs.   These   included
representations  for  time,  belief,  goals,  plans,   disjunction   and
negation, quantification, lambda abstraction, time intervals, a sequence
operator, and many more.

One of the first day's divided sessions  covered  the  area  of  "System
Implementations" (chaired by Bob  MacGregor  of  ISI)  where  issues  of
implementational details were discussed. It was discovered  that  almost
all of the systems presented in this session, viz. LOOM (Bob  MacGegror,
ISI), CLASSIC (Lori Alperin Resnik, AT&T), MESON (Bernd  Owsnicki-Klewe,
PHILIPS) and BACK (Albrecht Schmiedel, TU Berlin),  used  quite  similar
algorithms, the main differences being those with respect to  time/space
trade-off, i.e. with respect to what information should be cached  (i.e.
permanently stored with concepts  and  instances)  and  what  should  be
recomputed. Also, the syntax of these languages  has  become  much  more
similar in the last few years. Additionally, issues  of  the  usefulness
of truth maintenance and potentials for parallelism were discussed.

The session  on  "TSL  and  Natural  Language  Processing"  (chaired  by
Marc  Vilain)  featured   presentations   on   "Feature   Grammars   and
Classification-Based  Representation"  (Bob  Kasper,   ISI),   "Referent
Finding"   (Manfred   Gehrke,   Siemens)   and   "Lexical   Acquisition"
(Howard  Beck,  Univ.  of  Florida).  It  showed   the   usefulness   of
classification-based systems for a broad area  of  NLP.  The  discussion
centered around the degree  to  which  linguistic  knowledge  should  be
encoded in TSL (e.g., should a  terminological  knowledge  base  contain
lexical  items?),  and  whether  or  not  proximity  of  concepts  in  a
terminological knowledge base would correspond to "linguistic proximity"
of the denoted objects (an issue which is important  e.g.  for  anaphora
resolution).

The session on "TSL and Other Computing Paradigms" (chaired by John  Yen
of the Univ. of Texas) focussed on aspects of an integration of TSL  and
rule-based and object-oriented programming (aspects  of  databases  were
explicitly excluded and treated in a separate session). Presentations on
Consul (Bill Mark, Stanford), SB-ONE (Alfred Kobsa, Univ.of Saarbrucken)
and LOOM (John Yen, formerly at ISI) showed different approaches to both
the integration and the usage of rules in a TSL context. The  discussion
emphasized the  importance  of  a  "semantical  pattern  matcher"  in  a
rule-based system, i.e. a classification of  the  left-hand  sides  in a
terminological   knowledge-base.   With   respect   to   object-oriented
programming, the need for a semantical integration  of  the  notions  of
"protocol" and "message" into the formal framework of TSLs was felt.

Bernhard Nebel of IBM Germany chaired the session about "Consequences of
Intractability or Undecidability". Discussions focused on questions like
why tractability and decidability problems are interesting for the  work
in the TSL field, what could be done in cases  of  intractable  problems
and  why  undecidability  seems  to  be  a  more  severe  problem   than
intractability. As far as tractability is concerned,  the  need  for  an
identification of the "sources" of  intractability  by  theoretical  and
runtime analysis was stressed. The user could then be  discouraged  from
using  certain  language  constructions  which  raise  the   danger   of
intractability. Marc  Vilain  suggested  that  existing  knowledge  base
corpora should be distributed and used  for  this  analysis.  Jon  Doyle
(MIT) additionally brought up ideas from decision  theory,  particularly
that the system should be aware of the cost/utility ratio  when  solving
problems.

The session on "TSL and Databases" (chaired by Rich Fritzson  of  Unisys
Corp.), centered on topics of data/knowledge  persistency,  namely  mass
data and sharability on one hand and on access  of  a  KRS  to  existing
databases on the other hand. It was proposed to view a DB as a  kind  of
"instance server" where DB entries are transformed into a non-persistent
internal form. It was additionally stated that  in  a  normal  DBMS  the
notion of a query (few queries, large answers) differs widely  from  the
one usually employed in a KRS (many  queries,  small  answers)  so  that
issues of query optimization in the latter  context  do  not  make  much
sense.

Peter  Patel-Schneider  chaired  the  session  on  "Aspects  of   Formal
Semantics" which treated issues on the usefulness of a formal  semantics
of a KR language, a topic on which all participants agreed.  A semantics
gives a better understanding of what  a  TSL  is  able  to  express  and
probably also reveals points where problems might occur. Patel-Schneider
prefers a model-theoretic semantics  to  a  proof-theoretic  one  since,
according to him, a semantics should capture our  intuitions  about  how
the world is structured rather than describe the algorithms used  in the
knowledge  representation  system.  Questions  about   how   to   handle
inconsistencies also showed the need  to  characterize  how  the  system
prevents pollution of the KB and how to remedy it in terms other than of
implementation.

The session on  "Extensions  to  Standard  TSLs"  (chaired  by  Albrecht
Schmiedel of TU Berlin), had presentations about "Incorporating  Default
Reasoning into TSL" by Lee Spector (Univ. of Maryland), and by  Bernhard
Pfahringer (Univ. of Vienna) on  typicality  implication  links  between
concepts, based on Touretzky's notion of  "skeptical  inheritance".  The
problems  of  multiple  extensions  within  default  theories  and  fast
computation  were  also  discussed.  Furthermore,   Albrecht   Schmiedel
introduced his notion of "temporally constrained  concepts"  and  Sangki
Han  (Samsung  Corp.)  presented  the  extension   to   an   multi-agent
environment including consistent representations of the agent's  beliefs
and knowledge, based on Konolidge's deduction model of belief.

Deborah McGuinness (AT&T) chaired the session on "User Interfaces to TSL
Systems" which treated a large variety of problems. First, Alfred  Kobsa
gave an overview of design criteria  for  interfaces  to  terminological
knowledge bases. Three different interfaces (mostly graphics-based) were
then presented by Alfred Kobsa, John Yen (A&M Univ. of Texas) and  Lewis
Norton (UNISYS). Presentation problems within  the  TSL  framework  that
were discussed included the appropriate use of interactive graphics,  as
well as questions about user vs. system control  over  the  presentation
method chosen. The point was brought up that for very large  KBs  issues
of  fast  layout,  navigation  by   description   and   explanation   of
classification results are important but not yet  satisfactorily  solved
in many systems. Also, the claim was made that many designers  of  large
knowledge bases simply do not use interactive interfaces, but design the
knowledge base with a simple text editor.

In the session on "Hybrid Architectures" (chaired by Nicola  Guarino  of
Univ.of Padova) discussion concentrated on a conceptual characterization
of the differences between  terminological  and  assertional  knowledge,
rather than on  a  distinction  of  different  formalisms.  One  of  the
proposed  characterizations  was  to  replace  this   distinction   with
"persistent" vs. "changing in time", but that was  still  controversial.
Another  proposal   was   to   describe   it   by   "definitional"   vs.
"non-definitional", but the point  brought  up  was  that  it  would  be
desirable to have definitions which use instances (e.g., a definition of
an IBM PC should refer to the instance `IBM'),  and  A-Box  terms  which
refer to intensional concepts (e.g., `Mark found  the  phone  number  of
John'). Both seems to be impossible in current TSL implementations.

The last concluding session on "Future Directions" was chaired  by  Bill
Mark. It dealt with how to bring KR systems based on TSLs to the  users.
He brought up the point of systems quickly springing  into  use  because
they are small, clean and easy to understand.

Jon Doyle proposed to gather and analyze several problem  solving  tasks
with respect to the utility of TSLs in solving them. This again led to a
controversial discussion about providing a collection of tasks, problems
and models (the "corpus") contributed  by  and  accessible  for  anybody
engaged in TSL research, development and application.

Peter Patel-Schneider was optimistic about the future of these  systems,
mainly because they seem to hold a middle position between databases  on
one side and theorem provers  on  the  other  side.  He  urged  adapting
systems to both programmers and users by forcing robustness as  well  as
integration with programming languages.

Bob MacGregor spotted some important points in  transferring  TSL  based
systems to users, like going away  from  research  systems  to  end-user
systems. This requires that the system design becomes "frozen", that the
utility of classification-based reasoning is demonstrated  by  comparing
it to other tools for exactly identical problems, by providing  training
facilities and documentation,  and  by  achieving  an  integration  with
databases and programming languages.


Conclusions

Despite  being  --  at  least  locally  --  separated  for  many  years,
researchers in TSLs seemed to have reached a  good  common  standard  of
thinking  about  the  field,  and  the  systems  evolved  have  shown  a
remarkable compatibility in terms of expressiveness and  implementation.
Systems seem to differ mainly with respect to the services  provided  in
addition to the standard  TSL  services.  Such  extra  services  include
assertional reasoners, integration with rule-based  and  object-oriented
programming, etc.

On the other hand, this fact seems to have given rise to a great  amount
of agreement in the sessions; controversial  discussions  were  somewhat
rare! Thus, to a certain extent, the workshop may mark  an  "historical"
event in TSL research: thinking might  henceforth  focus  on  issues  of
integration, transfer and applications; theoretical considerations  will
take into account normal cases rather than worst cases.

Unanimous agreement existed that the organization of  the  workshop  was
near to perfect. The organizers fully achieved their goal  of  having  a
strongly  discussion-oriented   workshop   rather   than   yet   another
mini-conference. Certainly, the atmosphere of the 100-year old Victorian
country inn which hosted the workshop,  its  fabulous  cuisine  and  its
great selection of wines contributed to this success. And the organizers
even managed to keep  the  weather  cold  and  rainy  during  the  whole
workshop (so that everybody was forced to work),  except  for  one  free
afternoon when they permitted three hours of sunshine for a hike in  the
beautiful White Mountains.


List of Participants

Howard Beck, University of Florida, USA
Guilherme Bittencourt, University of Karlsruhe, WEST GERMANY
Jon Doyle, MIT, USA
Rich Fritzson, Unisys Research, USA
Manfred Gehrke, Siemens AG, WEST GERMANY
Nicola Guarino, LADSEB-CNR, ITALY
Sangki Han, Samsung, SOUTH KOREA
Yeona Jang, MIT, USA
Robert Kasper, ISI, USA
Alfred Kobsa, University of Saarbrucken, WEST GERMANY
Manolis Koubarakis, University of Toronto, CANADA
Kai v. Luck, IBM, Stuttgart, WEST GERMANY
Robert MacGregor, ISI, USA
Bill Mark, Stanford, USA
Eric Mays, IBM, Yorktown Heights, USA
Deborah McGuinness, AT&T, Murray Hill, USA
Bernhard Nebel, IBM, Stuttgart, WEST GERMANY
Lewis Norton, Unisys Research, USA
Bernd Owsnicki-Klewe, PHILIPS Research, WEST GERMANY
Peter Patel-Schneider, AT&T, Murray Hill, USA
Ramesh Patil, MIT, USA
Bernhard Pfahringer, University of Vienna, AUSTRIA
Massimo Poesio, University of Rochester, USA
Lori Alperin Resnick, AT&T, Murray Hill, USA
Albrecht Schmiedel, TU Berlin, WEST GERMANY
James Schmolze, Tufts University, USA
Gert Smolka, IBM, Stuttgart, WEST GERMANY
Luca Spampinato, Quinary, ITALY
Lee Spector, University of Maryland, USA
Bill Swartout, ISI, USA
Mark Vilain, MITRE, Bedford, USA
William A. Woods, Harvard University, USA
John Yen, A&M University of Texas, USA
 
--------------------
Thanks are due to Bernhard Pfahringer for his comments on this report.
************************************************************************