From: Daniel Lowd (lowd_at_cs.washington.edu)
Date: Wed Oct 22 2003 - 02:47:03 PDT
This work was largely a refutation of claims made by Levesque and Brachman
that general knowledge systems should be limited to ensure polynomial-time
inference while maintaining soundness and completeness.
Their essential ideas are that the utility of a system depends on more than
the cost of a worst-case query, and that different systems may be better
suited to different needs. Both of these ideas are contingent upon the
observation that there is a tradeoff between expressiveness and computational
efficiency. Theoretically, this paper could have a significant impact
on guiding people towards the most useful system rather than simply
the most efficient one.
Unfortunately, the exact tradeoff is never formalized, only induced from the
limitations of KL-one and oblique references to the work of others. While
the examples of KL-one's limitations are convincing (though perhaps
exaggerated, given the authors' clear bias), one is left to wonder to what
extent can we guarantee effeciency and still have a useful representation?
Is there a continuous spectrum from fully efficient to fully powerful, or
is it a more complicated space of expressiveness tradeoffs?
The paper also seemed to focus excessive attention on attacking one particular
system that the authors found annoying. Other knowledge systems were
mentioned as well, and occasionally given the attention of a sentence for
comparison, but the True Enemy was clear -- they might as well have titled
this paper "KL* Considered Harmful."
After reading this paper I am left wondering to what extent a single
system can be made general by allowing different levels of efficiency
and expressiveness. Could one turn on or off different language features
to ensure safety or flexibility as necessary?
Furthermore, to what extent can we automate a translation from a more
expressive system to a less expressive one (such as KL-one), so that we
have the benefits of both worlds. Since the translation could be done
offline, we could afford to let it take exponential time. The efficient
representation would thus be a cached, pre-processed inference machine.
Some additional translation might yet be required to make the results
readable, but this might be a reasonable solution.
This archive was generated by hypermail 2.1.6 : Wed Oct 22 2003 - 02:47:16 PDT