Truth management system

AI and expert system
What is TMS?
Enforcing logical relations among beliefs.
Generating explanations for conclusions.
Finding solutions to search problems
Supporting default reasoning.
Identifying causes for failure and recover from inconsistencies.
TMS applications

1. Presentation on Truth Maintenance System in AI Group Members: Sl. No Name ID 1 Najmul Hasan 1109013 2 Noormohammed 1109009 3 Md. Kamrul Hasan 1109010 4 Mesbah Uddin 1109011

2. What is TMS? A TMS deals with uncertainty by permitting new knowledge to replace old knowledge which is believed to be outdated or erroneous. A Truth Maintenance System (TMS) is a Problem Solver module responsible for: Enforcing logical relations among beliefs. Generating explanations for conclusions. Finding solutions to search problems Supporting default reasoning. Identifying causes for failure and recover from inconsistencies .

3. 1. Enforcement of logical relations AI problem -> search. Search utilizes assumptions. Assumptions change. Changing assumptions -> updating consequences of beliefs. TMS: mechanism to maintain and update relations among beliefs . ( Every AI problem which is not completely specified requires search. Search utilizes assumptions, which may eventually change. Changing assumptions requires updating consequences of beliefs. Re-derivation of those consequences is most often not desirable, therefore we need a mechanism to maintain and update relations among beliefs.)

4. 1. Enforcement of logical relations Example : If (ICT-601 ) and (math-218) then (ICT-570 ). If (ICT-570 ) and (ICT) then (TMS). If (TMS) then (AI-experience). The following are relations among beliefs: (AI-experience) if (TMS). (TMS) if (ICT-570 ), (ICT). (ICT-570 ) if (ICT-501 ), ( math-218) Beliefs are propositional variables TMS is a mechanism for processing large collections of logical relations on propositional variables .

5. 2. Generation of explanations Solving problems is what Problem Solvers do. However, often solutions are not enough. The PS is expected to provide an explanation TMS uses cached inferences for that aim. TMS is efficient: Generating cached inferences once is more beneficial than running inference rules that have generated these inferences more than once.

6. 2. Generation of explanations Example: Q: Shall I have an AI experience after completing the ICT program? A: Yes, because of the TMS course. Q : What do I need to take a TMS course? A : ICT-611 and AI and Expert system. There are different types of TMSs that provide different ways of explaining conclusions ( JTMS vs ATMS ). In this example, explaining conclusions in terms of their immediate predecessors works much better . ( Solving problems is what PSs do. However, often solutions are not enough -the PS is expected to provide an explanation for the proposed solution so that the user can identify the cause of a problem if something goes wrong. To provide explanations, a TMS uses cached inferences.)

7. 3. Finding solutions to search problems A B E C D Color the nodes: red (1), green (2) yellow (3). Adjacent nodes are of different colors. The set of constraints describe this problem: A1 or A2 or A3 not (A1 and B1) not (A3 and C3) not (D2 and E2) B1 or B2 or B3 not (A2 and B2) not (B1 and D1) not (D3 and E3) C1 or C2 or C2 not (A3 and B3) not (B2 and D2) not (C1 and E1) D1 or D2 or D3 not (A1 and C1) not (B3 and D3) not (C2 and E2) E1 or E2 or E2 not (A2 and C2) not (D1 and E1) not (C3 and E3) ( Assume you want to color the nodes so that every node is red, or green, or yellow , and adjacent nodes are of different colors. Let "1" means "red", " 2“ means "green", and "3" means "yellow". Then, the following set of constraints describe this problem 

8. To find a solution we can use search: 3. Finding solutions to search problem A is red A is green A is yellow B is red B is green B is yellow C is green C is red C is yellow D is red D is yellow D is green E is red E is green E is yellow

9. 4. Default reasoning and TMS PS must make conclusions based on incomplete information. “Closed-World Assumption” (CWA) X is true unless there is an evidence to the contrary. CWA helps us limit the underlying search space. The reasoning scheme that supports CWA is called “default (or non-monotonic) reasoning”.

10. 4. Default reasoning and TMS Many real-world problems cannot be completely specified. That is, the PS must make conclusions based on incomplete information. Typically the assumption under which such conclusions are drawn is that X is true unless there is an evidence to the contrary. This is known as the “Closed-World Assumption” ( CWA). Notice that the CWA helps us limit the underlying search space by assuming only a certain choice and ignoring the others. The reasoning scheme that utilizes this assumption is called “default (or non-monotonic) reasoning”. Example : Consider the following knowledge base Bird(tom ) and not Abnormal(tom)  Can_fly (tom) Penguin(tom )  Abnormal(tom) Ostrich(tom )  Abnormal(tom) Bird(tom) Under the CWA, we assume not Abnormal(tom) (because there is no evidence that Tom is abnormal). Therefore, we can derive can_fly (tom ). Non-monotonic TMS supports this type of reasoning .

11. 5. Identifying causes for failures and recov ering from inconsistencies Inconsistencies among beliefs in the KB are always possible: wrong data (example: “Outside temperature is 320 degrees.”) Impossible constraints (example: Big-house and Cheap-house and Nice-house ). TMS maintains help identify the reason for an inconsistency Non-monotonic inference. PS is forced to “jump” to a conclusion, because of the lack of information, or lack of time to derive the conclusion . “ dependency-directed backtracking” allows the TMS to recover.

12. Noormohammed

13. TMS applications Constraint Satisfaction Problems (CSP) Set of variables Domain over each variable Constraints between variables’ domain Goal: find “solution”: assignments to the variables that satisfy the constraint s Scenario and Planning Problems Find a path of state transitions lead from initial to final states. (games, strategies). TMS – identifies of applicable rules .

14. Problem Solver Architecture Inference engine TMS Poblem solver Knowledge base Tell Ask The TMS / PS relationship is the following:

15. How the TMS and the PS communicate? The PS works with: assertions (facts, beliefs, conclusions, hypotheses) inference rules procedures Each one of these is assigned a TMS node. Example: N1: (rule (student ?x) (assert (and (underpaid ?x) (overworked ?x)))) N2: (student Bob) Given N1 and N2, the PS can infer N3: (and (underpaid Bob) (overworked Bob)) PS treats nodes as logical formulas, While TMS treats nodes as propositional variables.

16. TMS Nodes Different types of TMS support types of nodes: Premise nodes . These are always true. Datum nodes . These are either a currently assumed or IE derived belief. Justification nodes . These are the belief supports, consisting of supporting antecedent node links and a consequent node link. Assumption nodes . PS believes no matter whether or not they are supported by the existing evidence. Node has a label associated with it. The contents and the structure of the label depends on the type of TMS . Other properties are node type (premise, assumption, etc.), node support (justifications, antecedents), node consequences, etc.

17. TMS Nodes Belief Network node meanings Premises Assumptions Datum Justifications

18. TMS justifications If N3, is created by the PS, it reports to the TMS together with the fact that it follows from N1, N2. justification : (N3  N2 N1) Here N3 is called the consequent , N1 and N2 are the antecedents of the justification. Justifications record relations among beliefs or explaining consequents and identifying causes for inconsistencies. The general format of justifications is the following: (<consequent> <antecedents>)

19. Propositional specification of a TMS As we have already seen, TMS nodes are propositional variables. Therefore, we can view TMS justifications as propositional formulas (implications) of the form: N1 & N2 & … & Ni  Nj Here N1, N2, …, Ni, Nj are positive literals, therefore this implication is a Horn formula. TMS can be viewed as a set of Horn formulas

20. PS / TMS interaction Responsibilities of the PS: Adds assertions and justifications. Makes premises and assumptions. Retracts assumptions. Provides advise on handling contradictions Responsibilities of the TMS: Cashes beliefs and consequences and maintains labels. Detects contradictions. Performs belief revision. Generates explanations.

21. Md. Kamrul Hasan

22. Families of TMSs There are several families of TMSs. Only two is defined here: Justification Based TMS Assumption based TMS

23. Justification-based TMS Justifications are used for: Belief update purpose, when belief state of a node changes. Handle contradiction : Justification is added to the dependency-directed backtracking system Then search through the dependency network for the assumptions of the contradiction Contradiction is removed.

24. Justification-based TMS A justification contains inlist and outlist for a justified node to be believed: inlist – a set of nodes that must be in outlist – a set of nodes that must be out Syntax: {( inlist ),( outlist )} Premises hold universally: empty in and out Only one context includes the set of assumptions currently believed.

25. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night PS concludes “nice weather” from A and C At the beginning Mak believes that A ,C and E

26. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} New node in the JTMS

27. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} PS concludes “swim” from E and G

28. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} H: Swim {(E,G),()}

29. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} H: Swim {(E,G),()}

30. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} H: Swim {(E,G),()} I: Contradiction {(C),()} Dependency-directed backtracking system PS provides a contradiction and the JTMS makes dependency-directed backtracking in order to infer that C caused to the contradiction. Therefore a TMS contradiction node is added and C is in its inlist which means C supports the contradiction

31. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),( D)} D: Raining E: Day {(),( F)} F: Night G: Nice weather {(A,C),()} H: Swim {( E,G),()} I: Contradiction {(C),()} X: Handle {(),()} //premise D: Raining {( X),()} Context: {(A,D,E), (B,C,F,G,H,I)} The backtracking finds D in the outlist of C and so D is justified by the contradiction of C.In order to solve the contradiction JTMS add the premise X as the inlist of D to make it assumed

32. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),( B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),( F)} F: Night G: Nice weather {( A,C),()} H: Swim {( E,G),()} I: Contradiction {( C),()} X: Handle {(),()} //premise D: Raining {( X),()} J: Read {( D,E),()} K: Contradiction {( J),()} //becomes tired Dependency-directed backtracking system PS provides read as justified by D and E After a while it became tired and so stopped to read, and the PS produced a contradiction to J. The backtracking finds the assumption E as faulty (because E is antecedent of J and D is supported by premise X in the inlist which is always true)

33. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),(D)} D: Raining E: Day {(),(F)} F: Night G: Nice weather {(A,C),()} H: Swim {( E,G),()} I: Contradiction {(C),()} X: Handle {(),()} //premise D: Raining {(X),()} J: Read {( D,E),()} K: Contradiction {(J),()} //becomes tired F: Night {( X),()} Context: {(A,D,F), (B,C,E,G,H,I,J,K)} Then node F is added since it backtracked from the outlist of the contradiction E, and node F is justified.

34. Justification-based TMS – Example Propositions: Justifications: A: Temperature>=25 {(),(B)} B: Temperature< 25 C: Not raining {(),( D)} D: Raining E: Day {(),( F)} F: Night G: Nice weather {( A,C),()} H: Swim {( E,G),()} I: Contradiction {( C),()} X: Handle {(),()} //premise D: Raining {( X),()} J: Read {( D,E),()} K: Contradiction {( J),()} //becomes tired F: Night {( X),()} L: Sleep {( F),()} The PS provides L as consequence of F

35. Mesbah Uddin

36. Assumption-based TMS ATMS is a general search – control mechanism , that can be coupled with domain-specific problem to solve a wide range of problem Start with a JTMS Label become more complex than: in, out

37. ATMS data structures Assumption Environments Labels

38. Justifications Justifications is a relationships among assumptions and nodes 1 l1 & l2 & K & ln n 2 l1 & l2 & K & ln where : 1 – truth of the node 2 - inconsistensy

39. New Definitions Environments = set of assumption Label = set of environments

40. Type of labels Sound - All assumptions in any environment within the label of a node being true is a sufficient condition to derive that node: Consistent - No environment in the label of a node, other than the nogood node , describes an impossible world: Minimal - The label does not contain possible worlds that are less general than one of the other possible worlds it contains (i.e. environments that are supersets of other environments in the label ): Complete - The label of each node, other than the nogood node, describes all possible worlds in which that node can be inferred:

41. Conclusions JTMS is used to maintain well fondness and assumption based TMS (ATMS) for coherence No possible to tell which TMS is the best without analysing the problem at hand and the resources available TMS in general handle knowledge, updates and revisions efficiently TMS can be used to speed up the analysis of multiple hypothetical situations.