Truth Maintenance Systems

inferences drawn by the knowledge representation system will have only default status, rather than being absolutely certain. Inevitably, some of these inferred "facts" will turn out to be wrong and will have the be retracted in the face of new information. this process is called belief revision

The Difficulty of Belief Revisioning

suppose that a knowledge base KB contains a sentence P (perhaps a default conclusion recorded by a forward-chaining algorithm, or perhaps just an incorrect assertion) and we want to execute TELL(KB, ¬P). To avoid creating a contradiction, we must first execute RETRACT(KB, P). This sounds easy enough. Problems arise, however, if any additional sentences were inferred from P and asserted in the KB. For example, the implication P ⇒ Q might have been used to add Q. The obvious “solution”—retracting all sentences inferred from P—fails because such sentences may have other justifications besides P. For example, if R and R ⇒ Q are also in the KB, then Q does not have to be removed after all.

Truth Maintenance Systems (TMSs)

§  are designed to handle the difficulty of belief revisioning

types of TMSs:

§  justification-based truth maintenance system (JTMS)

§  assumption-based truth maintenance system (ATMS)

justification-based truth maintenance system (JTMS)

§  each sentence in the knowledge base is annotated with a justification consisting of the set of sentences from which it was inferred

§  for example, if the knowledge base already contains P ⇒ Q, then TELL(P) will cause Q to be added with the justification {P, P ⇒ Q}

§  a sentence can have any number of justifications

§  justifications make retraction efficient. Given the call RETRACT(P), the JTMS will delete exactly those sentences for which P is a member of every justification

§  So:

§  if a sentence Q had the single justification {P, P ⇒ Q}, it would be removed

§  if it had the additional justification {P, P ∨ R ⇒ Q}, it would still be removed

§  but if it also had the justification {R, P ∨ R ⇒ Q}, then it would be spared

§  In this way, the time required for retraction of P depends only on the number of sentences derived from P rather than on the number of other sentences added since P entered the knowledge base

assumption-based truth maintenance system (ATMS)

§  are efficient in context-switching between hypothetical worlds

JTMS vs ATMS

In a JTMS, the maintenance of justifications allows you to move quickly from one state to another by making a few retractions and assertions, but at any time only one state is represented. An ATMS represents all the states that have ever been considered at the same time. Whereas a JTMS simply labels each sentence as being in or out, an ATMS keeps track, for each sentence, of which assumptions would cause the sentence to be true. In other words, each sentence has a label that consists of a set of assumption sets. The sentence holds just in those cases in which all the assumptions in one of the assumption sets hold

TMSs also provide a mechanism for generating explanations - an explanation of a sentence P is a set of sentences E such that E entails P