Re: Decidability
Leo,
Those are good points. Thanks for mentioning them.
I would also like to point out that the paper by
Petersen, Andersen, and Engel, which I mentioned in
my earlier note, is closely related to, but somewhat
different from the approaches mentioned in the following:
> Cf. http://www.cirl.uoregon.edu/research/knowledgeComp.html:
> "Starting with Lipski's ideas about reasoning with deductive
> databases, there has been a growing trend aimed at addressing
> the inherent computational complexity of many reasoning
> problems by compiling knowledge bases and/or queries into
> restricted forms where query-answering is easier than in the
> original language. In this way, computational effort at compile
> time (presumably at the system's leisure) can be traded for
> quick response at query time. In general,these approaches also
> involve some form(s) of approximation, because the target
> language for the compilation is less expressive than the
> original language of the knowledge base."
At the end of this note, I include a more detailed excerpt
from another paper, in which I describe the P., A., & E. work.
In any case, all this research supports some points I have
been making for a long time:
1. An ontology for a subject domain may be used for many
different purposes that may be totally unlike any that
were intended at the time the ontology was written.
2. The idea of optimizing an ontology for a particular use
or reasoning algorithm may be necessary for one purpose,
but it may be wrong or even disastrous for another purpose.
3. In program development, there is an important slogan:
"Premature optimization is the root of all evil."
See Google for 3,060 web pages that discuss this slogan.
4. Premature optimization of an ontology is just as evil
(or misguided) as a premature optimization of any kind
of software.
5. Ontology languages that are optimized for some reasoning
algorithm should *not* be used as the primary knowledge
representation languages. Instead, they should be the
*output* languages generated by knowledge compilers or
similar tools.
6. The primary languages for knowledge representation should be
as closely related as possible to the way that people think
and talk about the subject. That means they should be very
expressive versions of logic with optional representations
in some version of controlled natural language.
7. The focus of computational research should be directed at
methods of extracting relevant knowledge from rich ontologies
and automatically compiling or translating it to forms that
are efficient for some particular algorithm for some particular
purpose. The efficiency optimizations should be deferred until
the final stages of software development, not the initial stage.
John Sowa
___________________________________________________________________
Excerpt from:
http://www.jfsowa.com/pubs/arch.htm
Architectures for Intelligent Systems
Mapping a smaller logic to a more expressive logic is always possible,
but the reverse mapping usually requires some restrictions. To map
information from a large, rich knowledge base to a smaller, more
efficiently computable one, Peterson, Andersen, and Engel (1998)
developed a system they called the knowledge bus. Their source was the
CYC knowledge base (Lenat & Guha 1990; Lenat 1995), which contains over
500,000 axioms expressed in full FOL with temporal, higher-order, and
nonmonotonic extensions. Their target was a hybrid system that combined
a relational database with an inference engine based on the Horn-clause
subset of FOL. To map from one to the other, the knowledge bus performs
the following transformations:
* Extracting a subontology. To extract an ontology for a particular
application, the knowledge bus starts with a seed consisting of the
concept types explicitly mentioned in the application. Then it searches
through CYC to determine which axioms might deduce information about any
of the seed types. Finally, it extracts those axioms together with the
types and predicates used in them. For the sample application, it
extracted approximately 1% of the total CYC knowledge base: 1531 types,
1267 predicates, and 5532 axioms.
* Separating rules and constraints. Since the Horn-clause inference
engine cannot process arbitrary FOL statements, the knowledge bus
separates the axioms into two classes: 4667 Horn-clause rules that are
used for inferences, and 875 FOL statements that are used as database
constraints. Both the inferencing and the constraint checking can be
done efficiently, in at most polynomial time.
* Restrictions and modifications. For temporal reasoning, the
knowledge bus adds extra arguments for starting and ending times to the
CYC time-dependent predicates. To eliminate the higher-order features,
it introduces constants of type Assertion. And to simulate the CYC
nonmonotonic features, it uses a version of negation as failure.
For a particular application, the knowledge bus extracts a small subset
of the CYC knowledge base that can be processed more efficiently by
simpler tools. Although some information and some potential inferences
are lost, the extracted subset has a well-founded semantics that is
guaranteed to be free of contradictions. Furthermore, the resulting
subset is more portable: the inference engine can be used as an
extension to any relational database, and Engel (1999) has developed
techniques for mapping the definitions and axioms to Java classes that
can be used in web-based applications.
References:
Peterson, Brian J., William A. Andersen, & Joshua Engel (1998)
"Knowledge bus: generating application-focused databases from large
ontologies," Proc. 5th KRDB Workshop, Seattle, WA. Available from
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-10/
Engel, Joshua (1999) Programming for the Java Virtual Machine,
Addison-Wesley, Reading, MA.