| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
Some thoughts inspired by John Sowa's 'Architectures for Intelligent Systems' piece:
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. Typically, it goes like this: any set of facts and rules complex enough to yield interesting (i.e., non-toy) results requires intractable inference-- not just in worse-case but in the sort of cases that matter to users. Everyone is aware of the standard text-book complexity results from logic and graph theory. Many if not most of these problems are so simple that they don't even qualify as interesting discussion in 'AI' (i.e., on a list such as this),yet they are nonetheless sitting in NP, P-SPACE and worse complexity classes. ! These observations apply mainly to propositional logic; when you throw in quantification you've got the bug-bear of undecideability. Most people that I know and talk to in this field--knowledge representation, that is--typically give a quick nod to these sorts of observations and then get on to the important business of deciding on a representational language of sufficient expressivity to allow genuine intelligent inference in non-toy domains.
I appreciate that Sowa has included a section on complexity considerations in his article. 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. 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. Given that the aim of the development of a ‘standard upper ontology’ is expressly for “enabl[ing] 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 (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?). 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).
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. Perhaps this has already been done... if so, then flame away...
Erik