Tim.UPenn%Rand-Relay@sri-unix.UUCP (11/16/83)
From: Tim Finin <Tim.UPenn@Rand-Relay>
From: Stanley T. Shebs <SHEBS@UTAH-20.ARPA>
Subject: Pattern Matchers
... My next puzzle is about pattern matchers. Has anyone looked carefully
at the notion of a "non-failing" pattern matcher? By that I mean one that
never or almost never rejects things as non-matching. ...
There is a long history of matchers which can be asked to "force" a match.
In this mode, the matcher is given two objects and returns a description
of what things would have to be true for the two objects to match. Two such
matchers come immediately to my mind - see "How can MERLIN Understand?" by
Moore and Newell in Gregg (ed), Knowledge and Cognition, 1973, and also
"An Overview of KRL, A Knowledge Representation Language" by Bobrow and
Winograd (which appeared in the AI Journal, I believe, in 76 or 77).SHEBS@UTAH-20.ARPA (11/21/83)
From: Stanley T. Shebs <SHEBS@UTAH-20.ARPA>
Thanks for the replies about loop detection; some food for thought
in there...
My next puzzle is about pattern matchers. Has anyone looked carefully
at the notion of a "non-failing" pattern matcher? By that I mean one
that never or almost never rejects things as non-matching. Consider
a database of assertions (or whatever) and the matcher as a search
function which takes a pattern as argument. If something in the db
matches the pattern, then it is returned. At this point, the caller
can either accept or reject the item from the db. If rejected, the
matcher would be called again, to find something else matching, and
so forth. So far nothing unusual. The matcher will eventually
signal utter failure, and that there is nothing satisfactory in the
database. My idea is to have the matcher constructed in such a way
that it will return things until the database is entirely scanned, even
if the given pattern is a very simple and rigid one. In other words,
the matcher never gives up - it will always try to find the most
tenuous excuse to return a match.
Applications I have in mind: NLP for garbled and/or incomplete sentences,
and creative thinking (what does a snake with a tail in its mouth
have to do with benzene? talk about tenuous connections!).
The idea seems related to fuzzy logic (an area I am sadly ignorant
of), but other than that, there seems to be no work on the idea
(perhaps it's a stupid one?). There seem to be two main problems -
organizing the database in such a way that the matcher can easily
progress from exact matches to extremely remote ones (can almost
talk about a metric space of assertions!), and setting up the
matcher's caller so as not to thrash too badly (example: a parser
may have trouble deciding whether a sentence is grammatically
incorrect or a word's misspelling looks like another word,
if the word analyzer has a nonfailing matcher).
Does anybody know anything about this? Is there a fatal flaw
somewhere?
Stan Shebs
BTW, a frame-based system can be characterized as a semantic net
(if you're willing to mung concepts!), and a semantic net can
be mapped into an undirected graph, which *is* a metric space.