Re: SUO: Sowa's piece and thoughts on tractability
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 absolutely 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 interoperability, 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