Re: SUO: Re: Sowa's piece and thoughts on tractability
I'll weigh in here and underscore John and Erik's points.
There are two problems, solutions to which are often confused and in
fact the inability to solve one problem reflects negatively on the other
problem, at least by external nay-sayers who don't believe knowledge
representation and logical inference are legitimate solutions to any
real-world problem:
1) the knowledge expressivity problem, i.e., encoding declarative
representations which are close to the human conceptual level
2) the efficient run-time execution of such expressive knowledge
Many nay-sayers point to the lack of solutions to (2) to bash the
possibility of (1). But to me, that is wrong-headed. The area known as
knowledge representation addresses (1), whereas knowledge compilation
addresses (2. To confuse the two is to prematurely write off knowledge
technologies. However, I know of very many engineers and scientists who
have done so.
You (we) need both, we need solutions to both. Now one solution to (2)
is in fact to reduce the expressivity of the languages that address (1).
Description logics are a research thread devoted to this (expressivity
and intractability being nearly in an inverse relation). Prolog (using
the Horn-clause subset) in logic programming is another thread.
Knowledge compilation research has suffered, at least compared to
knowledge representation research. OntologyWorks is perhaps the only
commercial company (that I know of, though Teknowledge also has worked
on this) focusing on this (though obviously the expert system shell
folks dealt with this question earlier, cf. the Rete algorithm for
production rules, a quasi-logical formalism). In the research community,
however, knowledge compilation techniques such as extensionalization
(attempting to push rule inference toward table-lookup), caching
subproofs, prime implicates and implicants, theory approximation, etc.,
have been investigated. And SAT-related research should be included here
too. Logic programming, again, has focused on this: most Prolog
implementations today use the (notion of the) Warren Abstract Machine,
and convert Prolog expressions into an underlying "logical assembly
language" which is itself usually implemented in C-macros, which in turn
then get compiled (in a sense it's double compilation).
My point in all this: you need both (1) and (2). Now, will the rich
expressivity you have (in a very expressive FOL/HOL language)
in (1) get lost or vitiated when you transform it based on (2)? Yes, but
again there are smart things you can do to minimize this. But we need
(1), i.e., we need expressivity and if you force knowledge workers to
encode their human conceptual level representations to some "tractable"
level of expressivity, ultimately you doom the field of KR to a fatal
irrelevance.
Leo
"John F. Sowa" wrote:
>
> Gerard,
>
> As you know, I agree with you:
>
> > Research as much as you want into sublanguages and build specialist
> > subsumption, unification, reasoning algorithms (this is all good
> > stuff, and we do make use of it) as much as you want, but please use
> > an expressive (hopefully standardised) representation so you are not
> > limited to those techniques.
>
> And in my note to Erik Larson, I forgot to mention one of the most
> important reasons why it is essential to use a highly expressive
> input language for knowledge acquisition and knowledge engineering:
>
> **You must never throw away any information that may be useful later.**
>
> In the architecture paper ( http://www.jfsowa.com/pubs/arch.htm ),
> I make a strong plea against the old-fashioned (i.e., 20th century)
> approach that assumed separate domain experts and knowledge engineers
> (as illustrated in Figure 4). In that illustration, the domain
> expert provided the background knowledge, which the kn. engineer
> was supposed to encode in some AI language.
>
> In that scenario, there was no restriction on what the domain expert
> could say, but the kn. engineer was only allowed to code the subset
> that was expressible in the given expert system language. That was
> a colossal waste of valuable information (and valuable time that
> most highly trained and highly paid domain experts are unlikely
> to make available in repeated sessions).
>
> Later in that paper (at the end of Section 5), I discussed the
> techniques used in the knowledge bus project (Petersen, Andersen,
> & Engel, 1998). They used Cyc as a resource, which represents
> knowledge in CycL -- a language that uses full FOL plus metalevels.
> But they were able to extract the axioms from Cyc and separate
> the Horn clauses (used for inferences in their system) from the
> more expressive statements (used for database constraints).
>
> In Section 4, I also mentioned your former student, Steve Callaghan,
> who used syntactic criteria to classify information in order to
> determine which inference algorithms to use. That technique has
> been used in many theorem provers and inference engines in AI.
>
> Bottom line: Let people enter information in any form they see fit,
> and let computers sort it into complexity classes suitable for various
> problems and algorithms.
>
> John Sowa
--
_____________________________________________
Dr. Leo Obrst The MITRE Corporation
mailto:lobrst@mitre.org Intelligent Information Management/Exploitation
Voice: 703-883-6770 7515 Colshire Drive, M/S W640
Fax: 703-883-1379 McLean, VA 22102-7508, USA