[Artificial Intelligence] Strong Method

Strong Method

• Strong Method Problem Solving
  • Ref. Artificial Intelligence, Structures and strategies for complex problem solving, George F Luger, Addison Wesley
• Knowledge based system : tend to be specialist
• Knowledge is both theoretical and practical

1. Support inspection of their reasoning process
2. Allow easy modification in adding and deleting skills from the knowledge base
3. Reasoning heuristically, using(often imperfect) knowledge to get useful solutions

Knowledge based Systems

Overview of Knowledge based System Technology

• Design of rule based expert system
• User interface : simplifies communication and hides much of the complexity, such as the internal structure of the rule base
• Knowledge base : heart of the expert system. contains the knowledge of a particular application domain
• Rule based system : if … then rules General knowledge and case specific knowledge
• Inference engine : applies the knowledge to the solution of actual problems

Knowledge based System Architecture

Separation of the knowledge base and inference engine

1. separation makes it possible to represent knowledge in a more natural fashion
2. expert system builders can focus on capturing and organizing problem solving knowledge
3. separation of knowledge and control allows changes to be made in one part of the knowledge base without creating side effects in others
4. separation of the knowledge and control elements of the program allows the same control and interface software to be used in a variety systems

Selecting a Problem and the knowledge Engineering Process

• The need for the solution justifies the cost and effort of building an expert
• Human expertise is not available in all situations where it is needed
• Problem may be solved using symbolic reasoning
• Problem domain is well structured and does not require commonsense reasoning
• Problem may not be solved using traditional computing methods
• Cooperative and articulate expert exists
• Problem of proper size and scope
• Knowledge engineer to be a novice in the problem domain

Rule Based Systems

• Production System and Goal-Driven Problem

• Solver

• If premise then conclusion ($P \rightarrow Q$)
  • Case specific data can be kept in the working memory
  • Inference engine implements the recognize-act cycle of the production system → Control may be either data driven or goal driven

Goal Driven Reasoning(backward chaining)

• Goal is initially placed in working memory
• System matches rule conclusions with the goal
• Select one rule
• Place it’s premises in the working memory
  • Decomposition of the problem’s goal into simpler sub goal, subgoals can be solved by asking the user for information

Order of Premises

• Order of premises encodes important procedural information for solving the problem

$[(\sim A)\wedge(\sim B)] \rightarrow C$

① Place the top level goal, the problem is X in working memory ② X : variable that can match with any phrase in favor of the lowest numbered rule → rule 1 will fire ③ Premise of rule 1 placed in the working memory

• Entries in working memory that do not match any rule conclusion → expert system will query the user directly about these subgoals
  • Ease of modification is supported by the syntactic independence of production rules
  • Each rule is chunk of knowledge that can be independently modified

AND/OR Graph

Data-Driven Reasoning(Forward chaining)

• Breath first search in data driven reasoning

① If the premise of a rule is not the conclusion of some other rule then that fact will be askable ‘engine is getting gas’ is not askable rule 1 fails

② ‘engine does not turn over’ of rule2 is askable

→ If answer is false then ‘the engine will turn over’ is placed in working memory

③ First of two premises is false, moves to rule 3

④ First premise fails. Moves to rule 4

⑤ At rule 4, both premises are askable.

If answer to both questions is true then – ‘there is gas in the fuel tank’, ‘there is gas in the carburetor’ are placed in working memory – Conclusion of the rule ‘the engine is getting gas’ is placed

• All rules are considered. Search returns.

Rule 1 is fired → ‘the problem is spark plugs’ is placed in working memory

• No more rules are matched → session is completed

First pass of rules

Second pass of rules

Conclusion

• Opportunistic search : whenever rule fires to conclude new information, control moves to consider those rules which has that new information as a premise
• Data-driven reasoning is much less “focused” in its search → the explanation available to the user is quite limited

1. Procedural method of rule interpretation if p, q,, and r then s

→ to do s, first do p, then do q, then do r

Order the premises of a rule so that what is most likely to fail or is easiest to confirm is tried first

(ex) rule 1 : inefficient

1. Domain specific approach groups set of rules according to stages of solution process

(ex) organize situation, data collection, data analysis stages

– Place the assertion “organize” in working memory – All the rules in organize situation have their first premise, if stage is organize and…. – Last rule retract “organize”, and assert “data collection” in working memory

1. RETE : optimize search for usable rules