Dependency-directed reconsideration: an anytime algorithm for hindsight knowledge-base optimization

Dependency-directed reconsideration (DDR) is an efficient, anytime algorithm for performing the knowledge-base optimizing operation of reconsideration in an implemented computational system. Any computational system that stores and reasons with information must have some means for making changes to that information. These changes include (1) adding new information, (2) changing existing information, and (3) removing information---which can be used to resolve contradictions (called consistency maintenance). Many fields of computer science use revision techniques---examples include artificial intelligence (AI), robotics, diagnosis, databases, security, and constraint satisfaction problems; and techniques may be applicable across disciplines. This research takes an AI approach by referring to data as beliefs, and it assumes that there is a distinction between base beliefs (information that enters the system from some outside source) and derived beliefs (information produced solely by reasoning from some set of base beliefs and dependent upon those base beliefs). The belief state of such a system includes its currently believed base beliefs (its belief base) as well as the base beliefs that have been disbelieved. Information is rarely entered into a system all at once, and changing the order of the incoming information can alter the resulting state of the system in the case where consistency maintenance is ongoing. Assuming that the optimal base is the base that would result from deferring consistency maintenance until all incoming data is assimilated, any deviation from this optimal base is a negative effect of operation order, and the resulting state is sub-optimal. The two main contributions of this research are (1) the introduction and formalization of the hindsight, belief-base-optimizing operation of reconsideration and (2) the development of dependency-directed reconsideration (DDR)---an efficient, anytime algorithm for performing reconsideration in an implemented system. Reconsideration optimizes the base of a sub-optimal belief state by eliminating the negative effects of operation order. There no longer needs to be a choice between having a consistent base ready for reasoning and having an optimal base (by delaying consistency maintenance until all information is gathered). Reconsideration also improves the performance of belief change operations for finite belief bases. DDR optimizes an already consistent base by using a queue that contains a small, yet relevant, subset of the removed base beliefs. Processing the beliefs on the queue in decreasing order of preference (or credibility) results in the optimization of the base in a computationally friendly way: (1) a consistent base is always available for reasoning; (2) DDR optimizes the most important parts of the base first; (3) the base is always improving as DDR progresses; and (4) DDR can be performed in multiple stages that can interleave with the addition of (and reasoning with) new information. A measure of confidence in an existing base can be determined by the top element in the DDR queue---the lower its credibility, the higher the confidence in the base. DDR works for monotonic logics, but it is not restricted to classical propositional logic or ideal reasoning systems---it works for first-order predicate logic and relevance logics, and it works for systems whose reasoning is not guaranteed to be complete.