Copy Link
Add to Bookmark
Report
NL-KR Digest Volume 03 No. 01
NL-KR Digest (7/02/87 03:32:20) Volume 3 Number 1
Today's Topics:
CLP(R) Distribution Announcement
replies to query on inexact structure-matching
----------------------------------------------------------------------
Date: Fri, 26 Jun 87 16:18 EDT
From: "The CLP(R) Personae" <munnari!moncsbruce.oz!clp@seismo.CSS.GOV>
Subject: CLP(R) Distribution Announcement
[Excerpted from AIList]
DISTRIBUTION NOTICE
___________________
We are pleased to announce the availability of our
interpreter for CLP(R), the new Constraint Logic Programming
language. This is being distributed in source code written
in C and it is compatible with most machines running UNIX,
eg. Vaxen, Pyramids and Suns. This is not intended to be a
commercial announcement and is targeted at educational or
research usage.
The distribution includes:
1. CLP(R) interpreter (source code);
2. Example CLP(R) programs;
3. Installation Manual and Programmer's Manual (hard
copies).
Further information can be found in the following papers:
1. J. Jaffar and J-L. Lassez, "Constraint Logic
Programming", Proc. 14th ACM-POPL, Munich, January
1987.
2. J. Jaffar and S. Michaylov, "Methodology and
Implementation of a CLP System", Proc. 4th ICLP,
Melbourne, May 1987.
3. N.C. Heintze, S. Michaylov and P.J. Stuckey, "CLP(R)
and Some Electrical Engineering Problems", Proc. 4th
ICLP, Melbourne, May 1987.
4. C. Lassez, K. McAloon and R. Yap, "Constraint Logic
Programming and Option Trading", IEEE Expert, Fall
Issue 1987, to appear.
If you would like a Site licence for educational or research
purposes, please send a request for more information to
either,
(a) Electronic Mail address:
ACSNET: clp@moncsbruce.oz
ARPANET,CSNET: clp@moncsbruce.oz.au
UUCP: seismo!munnari!moncsbruce.oz!clp
(b) Paper Mail address:
CLP(R) Distribution
Department of Computer Science
Monash University
Clayton
Victoria 3168
Australia
In order to cover distribution and media costs, a license
fee of $150 will apply.
------------------------------
Date: Sat, 27 Jun 87 17:36 EDT
From: Roland Zito-Wolf <RJZ@JASPER.PALLADIAN.COM>
Subject: replies to query on inexact structure-matching
Replies to this request re approximate structure-matching:
I am looking for references regarding the matching of complex structures
(matching on semantic networks or portions of networks) such as arise in doing
retrieval operations on knowledge-bases so represented.
Since the general mathcing problem is most likely intractable, I'm
looking for approximate or incomplete techniques, such as partial match,
resource-bounded match, matches using preference rules, etc.
References which explore algorithms in detail, and implemented systems,
would be especially useful. For example, does anyone know of a detailed description
of the KRL matcher?
Information on the more general problem of query/data-retrieval from
semantic networks would also be useful.
Date: 29 May 87 15:48:17 GMT
From: tanner@osu-eddie.UUCP (Mike Tanner)
Subject: Re: Philosophy, Artificial Intelligence and Complexity Theory
To: AIList@STRIPE.SRI.COM
We have a paper to appear in this year's IJCAI called "On the
computational complexity of hypothesis assembly", by Allemang, Tanner,
Bylander, and Josephson.
Hypothesis assembly is a part of many problem solving tasks. Eg, in
medical diagnosis the problem is to find a collection of diseases
which are consistent, plausible, and collectively explain the
symptoms.
Our paper analyzes a particular algorithm we've developed for solving
this problem. The algorithm turns out to be polynomial under certain
assumptions. But the problem of hypothesis assembly is shown to be
NP-Complete, by reduction to 3-SAT, when those assumptions are
violated. In particular, if there are hypotheses which are
incompatible with each other it becomes NP-complete. (Another well
known algorithm for the same problem, Reggia's generalized set
covering model, is shown to be NP-complete also, by reduction to
vertex cover.)
The interesting part of the paper is the discussion of what this
means. The bottom line is, people solve problems like this all the
time without apparent exponential increase in effort. We take this to
mean human problem solvers are taking advantage of features of the
domain to properly organize their knowledge and problem solving
strategy so that these complexity issues don't arise.
In the particular case discussed in the paper the problem is the
identification of antibodies in blood prior to giving transfusions.
There exist pairs of antibodies that people simply cannot have both
of, for genetic reasons. So we're in the NP-complete case. But, it
is possible to reason up front about the antibodies and typically rule
out one of each pair of incompatible antibodies (the hypotheses).
Then do the assembly of a complete explanation. This results in
assembly being polynomial.
If you send me your land mail address I can send you a copy of the
paper. Or you can wait for the movie. (Dean Allemang will present it
in Milan.)
-- mike
ARPA: tanner@ohio-state
UUCP: ...!cbosgd!osu-eddie!tanner
Date: Fri, 29 May 87 13:35:32 edt
From: Lisa Rau <rau%kbsvax.tcpip@csbvax>
Subject: NLKR request for information
Roland,
I have done some work on partial/inexact matching on a semantic-net
type formalism (called KODIAK, from UCBerkeley, similar to KRL and
KLONE). Although the general problem is intractable, planar graph
matching is tractable (I dont know under what conditions a representation
will turn out to be planar). Also, semantic constraints (a person
could match a person, for example) help decrease the complexity of
the problem in the general case. That is, once you know what nodes
can match what nodes, the potential relative orientation of the two
graphs is narrowed down, and second-order (i.e., is NodeA/NodeB
connected in the same way to NodeC/NodeD) matching can be computed.
I am still debugging and working on the matcher I built for my
purposes and can send you some papers on the subject if you are
interested. The graph-matcher is tied to the method of retrieval
fairly closely. Retrieval is a two-pass operation. The first pass
is a marker-passing operation that yields the node-to-node potential
matches, and narrows down which graphs to look at more closely.
The second pass computes the matching operation. If you are interested,
let me know and I will send you the papers.
I am *very interested* in obtaining a copy of your other replies -
if you could forward the pointers to me I would appreciate it.
Thanks in advance,
Lisa Rau
rau@ge-crd.ARPA
Date: Mon, 1 Jun 87 08:57:46 pdt
From: levinson%saturn.UCSC.EDU@ucscc.UCSC.EDU (Bob Levinson)
Subject: structure matching
Roland,
See my article "A Self-Organizing Retrieval System for Graphs" in Proc.
AAAI-84 and/or my thesis of the same title available form the AI Lab at
the University of Texas at Austin available for free as tech report AI-85-05.
I'd be glad to answer any questions you may have.
Prof. Robert Levinson
CIS Board Office
Applied Sciences Building
University of California at Santa Cruz
Santa Cruz, CA 95064
(408)429-2087
ARPANET:levinson%saturn@ucscc.ucsc.edu
UUCP:ucbvax!ucsc!saturn!levinson
[The paper describes a graph database based on a partial ordering of
graphs for use in a KB in organic chemistry.
Its classification via partial ordering is related to KL-1 in both style and intent.
It also introduces the idea of a Universal Graph (UG) which
is a supergraph of every graph in the system. This allows graphs
to be represented simply as SUBSETS of the nodes of the UG, so that
under certain conditions one can compare graphs using set-inclusion
rather than actual matching. These ideas are interesting,
and raised a number of questions; answers follow.
-rjz]
Roland:
Questions:
What do you do when a given graph can be a subset of the UG in more than
one way? A subset of another graph in more than one way?
ANSWER:
This is indeed the major difficulty with the UG scheme. I store all
instances of a graph in the UG. The UG is constructed with the hope of
minimizing the # of instances. Obviously, this increases storage and
insertion costs. As I was only able to gain between 25%-33% retrieval
time with the UG scheme (with about the same total storage), I have abandoned it in
recent versions of my retrieval system, though I hope to resurrect it at a
later date. If you get my dissertation, you will see that I discuss
the system at an "Abstract Level". It is this abstract level that
is currently being developed at UCSC.
The representation is no longer restricted to graphs. By the way,
we are also working on an improved retrieval/insertion algorithm,
and plan on doing at least twice as well.
I am especially interested in "close matches". In the paper, regarding close
matches, you say that you "use a heuristic maximal-common-subgraph algorithm
to extract larger close matches". Can you give further detail?
ANSWER:
The basic idea was to start with the biggest match before the
subgraph-isomorphism test failed and add or delte nodes from there. If you want more details
I'll have to refresh my memory of the algorithm by examining the code.
One problem is the cost of classifying all the graphs. How much of a burden was this?
ANSWER:
This has not been a burden. I have always envisioned the system running
n two modes: Interactive - query processing Batch (overnight) - classification,
deletions. We are still working on finding the best way to do the classification.
Two things have worked well: a) When a new graph is added, find the graph
it is most similar to (among the close matches) and add the minimal difference
graph to the database. This graph can be found by looking at borders of the
maximal common subgraph of the two graphs.
b) Store query structures themselves. Queries tend to be small structures, and
if they are ever asked again the system responds efficiently.
Another idea mentioned in the thesis is "complete differentiating" - finding
enough differentiating structures to give every element a unique set of
predecessors.
This system seems closely related to Brachman's KL-1 and classification methods,
especially the requirement that there be a partial-oredering defineable on the
graphs. Also, his system depends on the fact that structures dont change (you just
create new ones, as your system does, when a new structure becomes interesting.)
Comments?
ANSWER:
I discuss KL-ONE several times in the thesis.
You mention that "relaxed-matching" is more difficult, since you dont have the
full information needed to determine supergraphs. How much does the matching
depend on predefined equivalence classes?
Is there a sense in which one could
define an abstract "resemblance metric" between two graphs?
As I understand it, your algorithms depend on graphs having well-defined "primitive"
components, ie, particular atom-types or subgraphs composed of same.
What would it mean to relax this constraint (ie, to deal with tokens
whose type is incompletely known or subject to update.)
(I have a side-interest: what does a "type" ultimately mean?)
ANSWER:
In the current implementation we are employing a type hierarchy for node
labels. This allows more flexible graph matching. There are still problems
when labels themselves can represent subgraphs in handling potential overlaps.
Relaxed Matching: One metric that I think would be useful would incorporate
weights for all the graphs in the database, and then base similarity on the
sum of the weighted graphs for the immediate predecessors of the maximal
common subgraph. This should produce a higher-level criteria for similarity
than simply counting nodes, edges etc.
Can you suggest a good reference for graph-comparing algorithms? ; ultimately
ANSWER:
I have found surprisingly little written about this. Most of the AI stuff
is ad hoc and/or domain specific. There is a reference to a Tarjan paper in
the thesis. I have learned some useful heuristics by looking at code some
people have written. Also, I had a student write a subgraph-isomorphism
algorithm based on Dependency-directed-backtracking and other backtraccking
improvements. I have not incorporated this in the system yet.
As I am sure you are aware, there are a lot of issues here.
Keep me posted with progress/questions.
Bob
Date: Mon 1 Jun 87 08:26:52-PDT
From: Len Friedman <FRIEDMAN@vaxa.isi.edu>
Subject: Matching Complex Structures
ISI has been developing a knowledge representation language called NIKL which is
a descendent of KL-ONE. Its most distinctice feature is a classifier which matches
inputs against a classification hierarchy automatically. For more information, contact
Bob MacGregor, MacGregor@VAXA.ISI.EDU. He is developing a more powerful version called
LOOM.
Len Friedman
Date: 1 JUN 87 13:40-N
From: INDUGERD%CNEDCU51.BITNET@wiscvm.wisc.edu
Subj: structure matching
Hello Roland,
I saw your request on the AILIST this morning.
I am actually working on a object-oriented-based knowledge representation
language, in with I would like to incorporate a mecanism of matching classes
and instances of the Knowledge Base.
So I would be interested on any information you get on the subject. Thank you.
The only reference I have is an informal description of the language KL-ONE,
and another about the classifier of KL-ONE. I give them below but you surely
already have them.
About KL-one :
Brachman R.J. and Schmolze J.G.
An overview of the KL-ONE Knowledge Representation System.
Cognitive Science vol.9 pp. 171-216, 1985
About the classifier of KL-ONE:
Schmolze J.G. and Lipkis T.A.
Classification in the KL-ONE Knowledge Representation System.
Proc IJCAI-83, Karlsruhe, W-Germany.
Regards.
Philippe Dugerdil
Inst. Informatique
Univ. of Neuchatel
Switzerland
(bitnet : INDUGERD@CNEDCU51)
Date: Tue, 02 Jun 87 11:16:22 PDT
From: macgreg@vaxa.isi.edu
Roland,
I'm afraid that I can't be of much help to you, but
I will tell you what it is we are doing here.
The kind of matching you're describing would, using our
vocabulary, be called matching "instances" with "descriptions".
The assertional component of the LOOM system will store
instances in a semantic net, and allows one to retrieve instances
using a predicate-calculus-based query language. Thus, this
somewhat resembles the problem you are describing. However,
we aren't currently looking at any of the variations you
described (resource-bounded, etc.). Unfortunately, we haven't
written anything yet describing this component, and in any
case, we would be unlikely to go into the kind of depth that
you seem to be looking for. In general, papers describing how
to build something don't get past the referees.
The "classifier" in NIKL and LOOM matches descriptions against
descriptions (patterns against patterns). This is a much harder
problem, where intractability is a given, and we are flirting
with undecidability. Ron Brachman and Hector Levesque have
written the most about the intractability issues associated with this
problem.
Good luck in your search,
Bob
Date: Tue, 2 Jun 87 17:38 EDT
From: Peter Szolovits <psz@ZERMATT.LCS.MIT.EDU>
Subject: references re (approximate) structure matching
Look at Dan Brotsky's SM thesis from a few years ago at the AI Lab. He
did a parser for net grammars, to use in Winston-analogy reasoning. I'm
sure there's been more stuff along these lines since then, but I haven't
followed it. --Pete
Date: Fri, 5 Jun 87 10:37 EDT
From: LEN MOSKOWITZ <MOSKOWITZ%TSD%atc.bendix.com@RELAY.CS.NET>
Subject: structure matching
The problem you mention is addressed by Lisa Rau, up at GE Corporate
Research and Development (rau@ge-crd.arpa) in her program SCISOR. SCISOR uses
a semantic network to represent and retrieve concepts and instances thereof.
Retrieval is essentially a two step process. The first she calls priming; it
is a constrained spreading activation. The second is a pretty straight graph
match operation. It's the priming that limits the search. She's presenting at
AAAI and IJCAI this summer and has a GE-internal technical report that goes into
considerable detail.
> Information on the more general problem of query/data-retrieval from
> semantic networks would also be useful.
You might look into Janet Kolodner's work on CYRUS (I think she's currently
at Georgia Tech), and Michael Lebowitz's (at Columbia) work on UNIMEM and IPP.
Date: Wed 10 Jun 87 09:50:00-PDT
From: WINOGRAD@CSLI.STANFORD.EDU
Subject: Re: approximate structure matching
Unfortunately, no detailed descriptions of the KRL matcher were every
written up. WE were in the midst of development when for local reasons
(LISP-machine development) work was suspended and then for more general
reasons (divergence of interests) never continued. There must be some
old files of code back at PARC, but I am no longer a consultant there.
You might check with Danny Bobrow (BOBROW@XEROX.COM). --t
From: Austin Tate <bat%aiva.edinburgh.ac.uk@Cs.Ucl.AC.UK>
Date: Mon, 22 Jun 87 13:00:23 bst
To: rjz <@Cs.Ucl.AC.UK,@live-oak.lcs.mit.edu:rjz@jasper>
Subject: partial match retrieval reference
Cc: bat%aiva.edinburgh.ac.uk@Cs.Ucl.AC.UK
One reference that comes to mind is the work done by John lloyd and his team at
Department of Computer Science, University of Melbourne, Melbourne, NSW,
Australia. Ask them for reports such as
Partial-match retrieval for dynamic files TR 81/5
Dynamic hashing schemes TR 86/6
Partial-match retrieval using hashing and descriptors TR 82/1
All these techniques are used in MU-prolog from Melbourne University.
The papers give an extensive and relevant further reference list.
Austin
------------------------------
End of NL-KR Digest
*******************
