Ed, (01)
The first sentence is critical: (02)
JFS>> Your comments raise three kinds of issues: theoretical points
>> about computational complexity, compiler-based methods for
>> dealing with them, and methodologies for the humans who use
>> the KR languages. All three of them are very important, but
>> the idea that all three should be addressed by the brute force
>> method of restricting the KR language is hopelessly misguided. (03)
EB> Well, John, then DARPA and others have poured a lot of money into
> hopelessly misguided research in the area of knowledge engineering,
> and a very large group of would-be ontologists are doing hopelessly
> misguided things that have proved to be valuable. (04)
Note that computational complexity, compiler-based methods, and
methodologies are very distinct issues. Restricting expressiveness
is not a silver bullet that can hit the target on all three. I
believe that a lot of money and R & D effort was wasted in trying. (05)
EB> Let's start with Horn clauses and rules engines and work our way
> through description logics to FOL reasoners. It seems to me they
> all restrict the KR language. (06)
Of course they do. But not for all three of the above reasons. (07)
I'll jump ahead in the comments to the following point (and then
come back to some of the earlier ones): (08)
EB> Any reasonably interesting ontology is easier to write in CLIF
> and easier to understand in CLIF than in OWL. All OWL practitioners
> also use some kind of drawing aid, analogous to CGIF, to make it
> easier to "grok" segments of the ontology. And when you have to
> do work-arounds in OWL, even the drawings are ugly. (09)
I'm happy that we agree on something. And by the way, that medical
example that I translated to CLCE, CLIF, and CGIF required many,
many work-arounds in OWL. In fact, the person who wrote the OWL
was initially unsure that the task was even possible -- but he
managed to do it with more work-arounds than straightforward code. (010)
EB> Have you never heard knowledge engineers talk about
> "avoiding disjunctions" or "adding helper axioms" or "steering
> the reasoner"? Outside of DL land, I have never met an AI student
> who doesn't understand those concepts, and the need for them. (011)
Anybody who is doing that is actually writing programs in an
inadequate version of Prolog. I strongly approve of using Prolog
as a very high-powered *programming* language, which happens to
have some features of logic. (012)
EB> It is all about tuning the reasoning process to a class of
> problem, after you realize that writing down the problem the way
> you understood it did not produce acceptable performance from
> the reasoner(s). (013)
Once you do that, you are no longer writing an ontology. You
are writing a program. In our work at VivoMind, we use three
programming languages: Prolog, Java, and C++. We also write
ontologies in one or more CL dialects. Sometimes we map parts
of those ontologies to Prolog, and sometimes we reason with and
about them in an inference engine written in Prolog. But when
we write Prolog, we never say that we're writing an ontology;
we say we're writing a program. (014)
Jumping back to an earlier point: (015)
EB> For example, in Description Logic land, it took more than 10
> years of research to determine maximal combinations of specialized
> extensions that were still computationally bounded. And that work
> is still going on. (016)
Description logics are an extension of Aristotle's syllogisms, and
most current OWL ontologies don't use anything beyond Aristotle.
Modern DLs were introduced by Bill Woods in 1975 and Ron Brachman
in 1979. That's 30 years of R & D. There are always finer and
finer incremental improvements, but the basic points are clear. (017)
EB> With respect to knowledge of complexity, therefore, I think
> Huxley's comment applies: "Who is so rich in that commodity as
> to be out of danger?" (018)
One of the most significant points is that the issues of decidability
and computational complexity, which are very important in theory, are
a red herring when it comes to practice. The people working on Cyc
have found that undecidable problems, which are theoretically possible
with a rich language such as CycL, rarely, if ever, occur in practice.
The major difficulties they encountered: (019)
1. Managing and organizing a very large knowledge base and finding
the relevant axioms necessary to solve any specific problem. (020)
2. Missing information that had not been anticipated by the kn.
engineers who developed the KB. (021)
3. Mismatches between the ontology as implemented and the raw data
and problems that must be addressed. (022)
4. Nonmonotonic issues of defaults, exceptions, and uncertainty. (023)
Cyc has implemented a few dozen different algorithms in specialized
inference engines, all of which run quite fast. But what slows down
the Cyc system is the difficulty of determining which of the two
million axioms are relevant to a particular problem and accessing
them at the instant they are needed. (024)
Those practical problems are vastly more significant than the
hundreds of papers and dissertations that prove that a certain
algorithm on a certain kind of problem is "tractable" -- that
means solvable in polynomial time. Those problems #1 to #4 with
Cyc are all "tractable". But polynomial time is not good enough. (025)
What is needed are logarithmic methods for indexing and finding
relevant data and axioms. Good indexing methods made relational
databases practical, but the path-based access methods with RDF,
OWL, and SPARQL are merely "tractable". They cannot compete with
the logarithmic times of a well-indexed system. (026)
EB> Knuth's barb is cute, but it presumes that you can define
> "mature optimization". (027)
When Knuth was talking about "premature optimization", he meant
that nobody can know in advance what optimization is needed.
Current theorem provers are fairly good at "mature optimization": (028)
As an example, consider the WHERE-clause of an SQL query, which
has the expressive power of full FOL. That same WHERE-clause
can be used with many different SELECT statements. Depending
on which columns of which tables are being selected, very
different optimizations are necessary. A premature choice of
optimization can take orders of magnitude more time than the
correct choice. (029)
Exactly the same issues are involved in a theorem prover.
In effect, each axiom of an ontology is similar to a WHERE-
clause of an SQL statement, but unlike an SQL query, the WHERE-
clause does not have an attached SELECT-clause. That means it is
*impossible* for a machine or even an educated human to determine
in advance which optimization is appropriate. The correct choice
can only be determined at the instant when the axiom is invoked. (030)
EB> But CycL itself is a strange combination of small FOL restrictions
> and canned extensions. It was designed to do just what you describe,
> recognize and solve certain kinds of subproblems rapidly. (031)
The core of CycL is a logic that is very similar to Common Logic,
and it has some features that require the IKRIS extensions (which
basically consists of one additional operator beyond CL). In fact,
some of the Cyc people participated in the two-year project that
defined IKRIS, at the end of which they claimed that they could
map CycL to CL + the additional operator added for IKRIS. (032)
I agree that there are many crufty things in Cyc, and many things
I would do differently. But I don't want to get started in commenting
on Cyc, which has gone through 24 years of evolution. (033)
EB> It is all about tuning the reasoning process to a class of
> problem, after you realize that writing down the problem the way
> you understood it did not produce acceptable performance from
> the reasoner(s). (034)
I would not call that writing an ontology. I would call it programming,
and I would recommend ISO standard Prolog as a far better language for
such work than OWL, RuleML, or even CLIF or CGIF. (035)
However, I would recommend tools for both fully automated (knowledge
compilers) and semi-automated (design & development aids) translations
from an ontology written in any dialect of CL to Prolog and even
lower-level programming languages (Java and C++). (036)
John (037)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (038)
|