Non-Monotonic and Truth Maintenance: Reasoning System | AI

In this article we will discuss about the reasoning system with uncertain knowledge:- 1. Non-Monotonic Reasoning 2. Truth Maintenance System (TMS).

Non-Monotonic Reasoning:

In a non-monotonic reasoning system new information can be added which will cause the deletion or alteration of existing knowledge. For example, imagine you have invited someone to your house for dinner. In the absence of any other information you may make an assumption that your guest eats meat and will like chicken. Later you discover that the guest is in fact a vegetarian and the inference that your guest likes chicken becomes invalid.

The two non-monotonic reasoning systems:

1. Abduction and

2. Property inheritance.

Recall that abduction involves inferring some information on the basis of current evidence. This may be changed if new evidence comes to light, which is a characteristic of non-monotonic reasoning. So, for example, we might infer that a child who has spots has measles. However, if evidence comes to light to refute this assumption (for example, that the spots are yellow and not red), then we replace the inference with another.

Property inheritance is also non-monotonic. An instance or subclass will inherit the characteristics of the parent class, unless it has alternative or conflicting values for that characteristic. So, on knowledge representation under semantics that dogs bark and that Rottweilers and Basenjis are dogs. However, we also know that Basenjis don’t bark. We can therefore infer that Rottweilers bark (since they are dogs and we have no evidence to think other wise) but we cannot infer that Basenjis do, since the evidence refutes it.

A system to deal with such a non-monotonic knowledge is the Truth Maintenance System (TMS). The main object of the TMS is the maintenance of the knowledge base. A TMS is a mechanism for keeping track of dependencies and detecting inconsistencies. It is also called reason maintenance system.

Truth Maintenance System (TMS):

The logics are known as monotonic logics. The conclusions derived using such logics are valid deductions, and they remain so for all times. Adding new axioms increases the amount of knowledge contained in the knowledge base. Therefore, the set of facts and inferences in such systems can only grow larger; they cannot be reduced; that is, they increase monotonically.

The form of reasoning referred to above, on the other hand, is non-monotonic. New facts become known which can contradict and can invalidate the old knowledge. The old knowledge is retracted causing other dependent knowledge to become invalid, thereby requiring further retractions. The retractions lead to a shrinkage or growth of knowledge base, called non-monotonic growth in the knowledge, at times.

This can be illustrated by a real-life situation. Suppose a young boy Sahu enjoys seeing movie in a cinema hall on the first day of its release. He insists upon his grand father, Mr. Girish in accompanying him. Mr. Girish has agreed to accompany Sahu there on the following Friday evening. On the Thursday, when forecasts predicted heavy snow.

Now, believing the weather would discourage most senior citizens, Girish changed his mind of joining Mr. Sahu. But, unexpectedly, on the given Friday, the forecasts proved to be false; so Mr. Girish once again went to see movie. This is the case of non-monotonic reasoning.

It is not reasonable to expect that all the knowledge needed for a set of tasks could be acquired, validated, and loaded into the system at the outset. More typically, the initial knowledge will be incomplete, contain redundancies, inconsistencies, and other sources of uncertainty. Even if it were possible to assemble complete, valid knowledge initially, it probably would not remain valid forever, more so in a continually changing environment.

In an attempt to model real-world, commonsense reasoning, researchers have proposed extensions and alternatives to traditional logics such as Predicate Logic and First Order Predicate Logic. The extensions accommodate such real time forms of uncertainty and non-monotony as experienced by our subject, Mr. Girish.

We now give a description of Truth maintenance systems (TMS), which have been implemented to permit a form of non-monotonic reasoning by permitting the addition of changing (even contradictory) statements to a knowledge base. Truth maintenance system (also known as belief revision system) is a companion component to inference system.

The main object of the TMS is the maintenance of the knowledge base used by the problem solving system and not to perform any inference. As such, it frees the problem solver from any concerns of knowledge consistency check when new knowledge gets added or deleted and allows it to concentrate on the problem solution aspects.

The TMS also gives the inference component the latitude to perform non­-monotonic inferences. When new discoveries are made, this more recent information can displace the previous conclusions which are no longer valid.

In this way, the set of beliefs available to the problem solver will continue to be current and consistent.

Fig. 7.1 illustrates the role played by the TMS as a part of the problem solving system. The Inference Engine (IE) from the expert system or decision support system solves domain specific problems based on its current belief set, maintained by the TMS. The updating process is incremental. After each inference, information is exchanged between the two components the IE and the TMS.

The IE tells the TMS what deductions it has made. The TMS, in turn, asks questions about current beliefs and reasons for failure of earlier statements. It maintains a consistent set of beliefs for the IE to work with when the new knowledge is added or removed.

For example, suppose the knowledge base (KB) contained only the propositions P and P → Q, and modus ponens. From this, the IE would rightfully conclude Q and add this conclusion to the KB. Later, if it was learned that ∼P become true it would be added to the KB resulting in P becoming false leading to a contradiction. Consequently, it would be necessary to remove P to eliminate the inconsistency. But, with P now removed, Q is no longer a justified belief. It too should be removed. This type of belief revision is the job of the TMS.

Actually, the TMS does not discard conclusions like Q as suggested. That could be wasteful, since P may again become valid, which would require that Q and facts justified by Q be re-derived. Instead, the TMS maintains dependency records for all such conclusions.

These records determine which set of beliefs are current and are to be used by the IE. Thus, Q would be removed from the current belief set by making appropriate updates to the records and not by erasing Q. Since Q would not be lost, its re-derivation would not be necessary if and when P became valid once again.

The TMS maintains complete records of reasons or justifications for beliefs. Each proposition or statement having at least one valid justification is made a part of the current belief set. Statements lacking acceptable justifications are excluded from this set.

When a contradiction is discovered, the statements responsible for the contradiction are identified and an appropriate one is retracted. This in turn may result in other reactions and additions. The procedure used to perform this process is called dependency directed back tracking which will be explained shortly.

The TMS maintains records to show retractions and additions so that the IE will always know its current belief set. The records are maintained in the form of a dependency network. The nodes in the network represent KB entries such as premises, conclusions, inference rules etc.

To the nodes are also attached justifications which represent the inference steps from which the node was derived. Nodes in the belief set must have valid justifications. A premise is a fundamental belief which is assumed to be always true and need no justifications. In fact, they form a base from which all other currently active nodes can be explained in terms of valid justification.

There are two types of justification records maintained for nodes:

1. Support Lists (SL) and

2. Conceptual Dependencies (CP).

SLs are more common. They provide the supporting justifications for nodes. The SL contains two lists of other dependent node names, an in-list and an out-list. It has the form.

SL <in-list> <out-list>

For a node to be active (labeled as IN the belief set), its SL must have at least one valid node in its in-list, and all nodes named in its out-list, if any, must be marked OUT of the belief set. For example, a current belief set which represents that Oosho is a non-flying bird (an ostrich) might have the nodes and justifications listed in Table 7.1.

Each IN-node given in Table 7.1, is part of the current belief set. Nodesn 1 and n5 are premises. They have empty support lists since they do not require justifications. Node n2, the belief that Oosho can fly is out because n3; a valid node, is in the out-list of n2.

Suppose later on it is discovered that Oosho is not an ostrich, thereby causing n 5 to be retraced as OUT. Then n3, which depends on n5, must be also retracted. This, in turn, changes the status of n2 to be a justified node. The resultant belief set is now that the bird Oosho can fly.

For representation of a belief network the symbol conventions shown in Fig. 7.2 are quite often used.

The meaning of the nodes shown in the figure are:

(1) A premise is a true proposition requiring no justification,

(2) An assumption is a proposition which is held true because there is no evidence against that,

(3) A datum is either a currently assumed or IE derived belief, and

(4) Justifications are the belief nodes consisting of supporting antecedent node links and a consequent node link.

An example of a typical network representation is given in Fig. 7.3. Nodes T, U, and W are OUT since they lack needed support from P. If the node labeled P is made IN for some reason, the TMS would update the network by propagating the “in ness” support provided by node P to make T, U, and WIN.

When a contradiction is discovered, the TMS locates the source of the contradiction and corrects it by retracting one of the contributing sources. It does this by checking the support lists of the contradictory node and going directly to the source of the contradiction.

It goes directly to the source by examining the dependency structure supporting the justification and fixing the annoying nodes, (‘guilty’ premises), thereby dismantling the justification for the contradiction.

This is in contrast to the chronological backtracking approach mentioned many times, which would search a deduction tree sequentially, node-by-node until the contradictory node is reached. Backtracking directly to the node causing the contradiction is known as Dependency-Directed Backtracking (DDB). This is clearly a more efficient search strategy than chronological backtracking. By backtracking directly to the source of a contradiction extra search time is saved.

TMS discussed above concentrates on maintaining a single, consistent world, model. However, sometimes it is convenient to perform reasoning in the context of different hypothetical worlds, which may or may not resemble the way the world actually is. For example, in doing diagnosis, it is often worthwhile to assume that a certain fault has occurred and then make predictions on the basis of this assumption and see if they are backed up by evidence.

This strategy is particularly useful if there are a large number of hypothesis competing to account for the observations, with the possibility that a composite hypothesis may be required to cover all of them. Another domain of application might be arrangement problems/where the hypothetical worlds represent different ways of arranging objects to satisfy a set of constraints.

To maintain multiple contexts more sophisticated systems are Logic-based TSM and assumption based TMS among others. Other more sophisticated systems are Logic-based TMS (LTMS), assumption-based TMS (ATMS) among others.