Re: SUO: Sowa's piece and thoughts on tractability
John,
Thank you for your helpful comments. I want to clarify that I didn't intend to make general remarks about the suitability of FOL or HOL for the purposes of AI, but to suggest that the choice of a language ought to be governed by the specific goals of the group. These goals as stated (see the 'Scope and Purpose' section on the SUO page) have a strong emphasis on the development of knowledge-based applications and on the facilitation of interoperability of existing applications by the provision of a common set of concepts. Now, the question I have is whether something like FOL-HOL is the most suitable choice here. This isn't just obvious, I suggest.
One of the challenges we face is that there is a lack of shared assumptions among software developers and researchers in AI. Software developers don't (typically) share the theoretical background necessary for discussing and creating ontologies for use in computational systems, and AI folks historically have shown a lack of enthusiasm for "bottom up" approaches that scale existing architectures or that make more modest assumptions about the language and notation required to express computer-readable knowledge. One of the reasons for the difference is the professed difference in goals-- creating better or 'next-generation' software by making use of ontologies is different than creating a computer program that exhibits human-like intelligence. For the latter, FOL may in fact be necessary (as many AI researchers, or at least those in the 'logicist' camp, have often contended). For the former, it's!
not obvious at all.
You made some comments on my original note that cover some of this ground, and I should address them. In particular, your point that "you must never throw away information that may be useful later." I'm willing to grant this as a general methodological principle in knowledge-based development, but note that it is not, by itself, an argument for using FOL. Such an argument requires a premise that the sorts of facts included in an ontology and the application problems that rely on that ontology for their solution require treatment in FOL (and possibly HOL). In other words, I might accept your principle but apply it not in order to embrace FOL but as a way of choosing, say, between a simplified KIF and a more-simplified KIF.
Another objection to my previous points is that a reduction in language expressivity would doom the long-term goals of KR. That certainly is a legitimate concern, but it again presupposes the very thing I'm trying to consider: must KR be wedded to FOL to succeed? Given the gap between industry software development and the aspirations of KR (or the goals of SUO), another plausible threat to the long-term success of KR is a lack of sustained attempts to provide workable bridges between current software development tools and research in AI. This is beginning to change, true, but it's fair to say that certain convictions among the AI or KR community (e.g., the need for highly expressive, undecideable languages to express knowledge) and the software development enterprise haven't been adequately reconciled and integrated. This work needs to be done.&!
nbsp; Such efforts may yield more long term fruit than one might imagine...
Erik
"John F. Sowa" <sowa@bestweb.net> wrote:
Erik,
I strongly believe in the importance of analyzing the computational
complexity of various kinds of problems and the algorithms used to
deal with them. But I strongly disagree with the following statement:
> One of the things I've faced in my own development efforts and in
> thinking about effective representational schemes for AI applications
> is the tradeoff between computational tractability and
> representational expressivity.
This fallacy results from a common misunderstanding. People observe
that problems stated in a more expressive language A are sometimes more
complex than problems stated in a less expressive language B. Therefore,
they try to solve the complexity problems by forcing people to use B
rather than A.
But the essential point is that restricting the expressive power of
the language does absolut!
ely nothing to solve the problems. It merely
makes the more complex problems impossible to state.
Furthermore, there are many easily solvable problems that require
the more expressive language. By restricting the language, many
kinds of easy problems also become impossible to state. That is not
a good way to design a general purpose communication system that is
going to be used for an open-ended number of purposes.
> I appreciate that Sowa has included a section on complexity
> considerations in his article.
I included that section for many different reasons, and intractability
is only one. For many kinds of problems, the crucial distinction is
not between polynomial time and exponential time, but between linear
time and logarithmic time. Focusing only on the high end tends to put
blinders on some people who have spent years proving that certain
kinds of classification problems could be solved in polynomial time,when, in fact, many very important problems require logarithmic
algorithms -- even linear time (polynomial of degree 1) is too slow.
> But he seems to pass over this
> material a bit too quickly himself--hastily pointing out that
> undecideability in FOL does not apply to many problems formulated in
> FOL and hence is misleading as an objection.
This is a very important point, which many people who focus only on
one type of problem have forgotten.
> Perhaps, but given a general enough formulation of a domain using FOL
> (let alone quantification over sets), you're bound to end up with
> queries that won't terminate.
That is true. But that is not a fault of FOL, but a fault of the
kind of query that is being asked.
> Given that the aim of the development of a "standard upper ontology"
> is expressly for "enabling computers to utilize it for applications
> such as data interoperabil!
ity, information search and retrieval,
> automated inferencing, and natural language processing", I believe
> the group ought to be very clear about not just the expressivity
> requirements but also conditions of successful! inference
This is where the error comes in: the expressivity requirements of
the language should not be confused with the computational complexity
of the problems and the kinds of inference. Some queries that require
full FOL to state can be answered very efficiently. The SQL language,
for example, supports full FOL, but queries stated in SQL can be
answered against a relational DB in at most polynomial time.
> (must well-formed queries all terminate? How long is too long? What
> sort of applications should be built using a KB? What will the
> typical users of these applications require by way of inferential
> efficiency and quickness?).
Those are very good question to ask and to !
consider. But it is
important to remember that they depend primarily on the nature of
the problems to be solved, not on the language used to express them.
> There are a few (very few) companies that have tackled these issues in
> their language and implementation choices, choosing smart or at any
> rate necessary tradeoffs between tractability and expressivity in the
> quest to develop real applications (i.e., ones that work). See for
> instance the OWL language promulgated by OntologyWorks (no I'm not
> affiliated with them).
It is a very serious mistake to impose expressibility constraints
on the language that people use for stating problems. A much better
solution is to apply simple syntactic checks that can be used to
classify the complexity class of the problem (or query) statement
and then to issue a warning to the user if the statement happens to
be in one of the slow or even intractable classes.
> There is much more to say here, but my point in sending this to the
> discussion group is that I think it would be helpful to discuss
> representational issues with inferential considerations in mind.
I agree that these issues are important, and it is essential to bring
them out into the open. Too many people have been ignoring them or
proposing restricted languages when they should be focusing on the
kinds of problems rather than the exressive power of the language.
John Sowa
Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax