Rule Based Systems and Expert Systems
Consider the statement “Everyone in LPH who is not a manager and does not like poetry is a cook” from A1
Chapter 8
in Clause Form: ~in(X,lph) v manager (X) v likes(X,poetry) v cook(X)
Limitations of Clause Form
Rules
Logically this is equivalent to the original statement, but the clause form statement can be used in many different ways, only some of which were explicitly expressed in the English statement
The original statement expressed as a RULE is: IF X is in LPH, is not a manager, and does not like poetry, THEN X is a cook
The extras come from the power of logic (they are implicit in the English statement)
Take the facts that X is in LPH, is not a manager, and does not like poetry, and deduce that X is a cook (FORWARD direction)
This isn’t a good thing computationally
Or assume they’re a cook, and prove they’re in LPH, are not a manager, and do not like poetry (BACKWARD direction)
Went to clause form in the first place to use resolution to reduce the number of possible operations at each point
Limitations of FOL
In FOL: X:(in(X,lph) ^ ~manager(X) ^ ~likes(X,poetry)) cook(X)
How many ways can this be resolved?
4: with ~in, manager, likes(X,poetry), or ~cook
predicates
How many ways can this be used?
34 © 2020 J.E. Anderson © 2020 J.E. Anderson
2 © 2020 J.E. Anderson
Production Systems
Production Systems
That is why rules are such a popular representation mechanism in AI: they preserve the original semantics of a statement in ways that clause form doesn’t, they’re easily readable by people, and they are easier to work with computationally
Have three components:
Prolog uses clause form; most other more specialized systems for performing reasoning (shells) use more obvious rule-based mechanisms or even more powerful forms of knowledge rep.
A control strategy (inference engine) to somehow cycle through the rules and produce new facts
A rule is also called a production, and a rule-based system is also called a production system
The first two are pretty straightforward: rules
are just IF-THEN pairs, with a logical
condition that can be evaluated to true or
false, and some action to take (deduce a new fact, cause some action to occur) 6
identifying animals
If all conditions in a rule are satisfied, add conclusions to working memory
Control Strategies
Forward Reasoning: naive
With rules we can work either forward or backward
Let’s look at an example: a trivial domain for
Search rules, checking conditions against facts in working memory
Our rules will be of the form:
if (condition) then (conclusion)
Where each condition involves examining the attributes of objects the system knows about
Repeat with the other rules in the rule base, ignoring rules that conclude in facts that have already been asserted, until we reach the end of the rule base
e.g. IF (?x has hair) then (?x is-a mammal)
Repeat this process until no further deductions can be made or until the particular deduction we are interested in has been made
Where the ? before a name denotes a variable
We will cover the details of such object-like representations later, but if you think of it as an object/instance for now, that’s enough
Working in a forward direction involves a lot of potentially useless deductions, because it’s difficult to focus inference on the goal 8
5 © 2020 J.E. Anderson
© 2020 J.E. Anderson
7 © 2020 J.E. Anderson
© 2020 J.E. Anderson
A set of rules (productions)
A working memory to store intermediate (deduced) facts about the problem at hand
Example Rule Set
Example Rule Set
R1: if (?x has hair) then (?x is a mammal)
R2: if (?x gives milk) then (?x is a mammal)
R3: if (?x has feathers) then (?x is a bird)
R4: if (?x flies)^(?x lays eggs) then (?x is a bird)
R5: if (?x is a mammal)^(?x eats meat) then (?x is a carnivore) R6: if (?x is a mammal)^(?x has pointed teeth)^(?x has claws)
R11: if (?x is an ungulate)^(?x has long legs)^(?x has long neck) ^(?x has tawny color)^(?x has spots)
then (?x id is giraffe)
^(?x has forward-pointing-eyes) then (?x is a carnivore) R7: if (?x is a mammal)^ (?x has hoofs) then (?x is an ungulate) R8: if (?x is a mammal)^ (?x chews cud) then (?x is an ungulate) R9: if (?x is a carnivore)^(?x has tawny color)^(?x has spots)
R13: if (?x is a bird)^(?x cannot fly)^(?x has long legs)
^(?x has long neck)^(?x has black and white color) then (?x id is ostrich)
then (?x id is cheetah)
R10: if (?x is a carnivore)^(?x has tawny color)^(?x has stripes)
R14: if (?x is a bird)^(?x cannot fly)^(?x can swim) (?x has black and white color)
then (?x id is tiger)
then (?x id is penguin)
9 10
Forward Direction
Forward Direction
Working memory consists of the current set of objects about which a system can reason – facts that have been deduced thus far or are given to the system to begin with
Stretch has hair
Stretch chews cud Stretch has a long neck Stretch has a tawny color Stretch has dark spots Stretch has long legs
Any consultation with the system will consist of adding a set of facts involving the current specific problem and asking the system to draw new conclusions from it
Stretch in our case will end up getting bound to ?x in our rules (though obviously we could have >1 variable in rules and >1 object – there would just be more deductions we could make)
e.g. I might add the following facts in the representation we are using:
© 2020 J.E. Anderson
© 2020 J.E. Anderson
11 © 2020 J.E. Anderson
12 © 2020 J.E. Anderson
R12: if (?x is an ungulate)^(?x has white color)^ (?x has stripes) then (?x id is zebra)
R3…R7 fail
If R1 and R11 were exchanged, for example, we would never be able to know that Stretch was a mammal until long after we checked to see if Stretch was a giraffe – a second pass would be needed
Forward Direction
>1 Pass
Consider R1: Stretch does have hair, so we conclude stretch is a mammal
Getting a useful conclusion may require a number of passes through the rules, since earlier rules may rely on facts that can only be deduced by later rules
We can ignore R2 – it concludes in a fact we already know once the variable is bound
R8: stretch is a mammal, stretch chews cud, so stretch is an ungulate
R9-R10 fail, and then R11 succeeds: stretch is a giraffe!
Forward Reasoning: more realistic
Forward Reasoning: more realistic
In real world settings, we do not automatically use a rule to make a conclusion whenever we can during forward reasoning
Once we have the conflict set, we choose (usually) one rule from this, and cause its conclusion to be run/added (fire the rule)
We look at what we could possibly derive, and THEN make a decision as to what to do
Why one? And Why build a conflict set?
Whenever a rule could be used – i.e. has its conditions satisfied – we say it is triggered
It doesn’t mean we will use it, just that we could if we wanted to
We make a pass through the rules, creating a set of such triggered rules, which we call our conflict set
16 © 2020 J.E. Anderson
13 © 2020 J.E. Anderson
efficiency 14 © 2020 J.E. Anderson
15 © 2020 J.E. Anderson
In general, rearranging rules doesn’t change
what can be deduced, but it does affect
Non-Monotonic Systems
Conflict Resolution
Allowing one rule to fire might cause one of the conditions of the other rules to be retracted – firing order often matters very much
The process of choosing the best rule to fire from the conflict set is called conflict resolution
Having the whole set at least lets us consider all the current possibilities together and choose the best
Many schemes for this, mostly domain dependent, and often mixable
We can use meta-knowledge to choose the best (most general rule? heuristic to lead us to the goal? Some other type of control knowledge?)
There are some domain independent strategies, but remember they’re weak
We could then rebuild the conflict set and choose the best to fire again and again
• • •
refraction: rules that are fired can’t be re-fired on the same data
But we usually keep a conflict set and add/delete items from it based on what just changed in working memory, rather than regenerating from scratch
recency: choose rules involving recently added data
Backward Reasoning
Backward reasoning example
It is often convenient computationally to reason backwards if this is possible, to ensure that we are always performing reasoning relevant to our goal
Stretch has hair
Stretch chews cud Stretch has a long neck Stretch has a tawny color Stretch has dark spots Stretch has long legs
If we have a goal, check to see if it is in working memory. If it isn’t, look for a rule that concludes in it. If one is found, adopt the preconditions (antecedents) of that rule recursively as subgoals
Assume our goal is to prove stretch is a giraffe
If those subgoals fail, try to find a different rule concluding in our goal. If we can’t find any more, our goal fails.
We would look at rules that conclude in this condition: have only one, R11
Natural depth first search!
R11’s first condition is that stretch is an ungulate: prove that
17 © 2020 J.E. Anderson
18
19 © 2020 J.E. Anderson
20 © 2020 J.E. Anderson
specificity: choose rules with > #’s of premises
© 2020 J.E. Anderson
Backward Direction
Backward Direction
We try R7, the first ungulate rule
Back to R11, and prove other conditions: every other condition is in WM and we are done
This requires us to prove stretch is a Mammal
We adopt that goal and try R1: success
What if we had a more general goal? Find the ID of Stretch?
Back to R7, we need to prove stretch has hoofs: failure
We would simply have a broader range of initial rules to select from (R9…R14)
Need other ungulate rules: find R8
Or broader yet, find the ID of ?Y, where there are number of different objects (such as stretch) in working memory facts?
Need to prove stretch is a mammal (already done)
Need to prove stretch chews cud: in working memory
• We’d just have to bind variables as we do in FOL (and Prolog) 22
Easily understood and readable
Rules
Expert Systems
A very modular way of representing knowledge
A natural way to express knowledge in many
Knowledge-Based Systems are systems whose primary focus is on knowledge that is explicit and is represented separately from the problem- solving algorithm (i.e. declarative representation)
domains
Enforces separation of knowledge and control
Expert Systems are knowledge-based systems that perform at a level comparable to that of an expert in a very narrow domain
Order of rules is irrelevant logically (that’s part of the modularity), but can strongly affect efficiency
Expertise is the value that is added to basic domain knowledge (e.g textbook knowledge)
Typically easier to extend a RBS to handle more complex problems (e.g. uncertainty) than a pure logic-based system
ES development is all about emulating a human expert’s expertise
21 © 2020 J.E. Anderson
© 2020 J.E. Anderson
23 © 2020 J.E. Anderson
24 © 2020 J.E. Anderson
Advantages of Expert Systems
Advantages of Expert Systems
Problems may be solved faster by the system than by the expert
May be a significant financial advantage to solving problems using an expert system
Expertise can be widely distributed
Expert systems do not have “bad” days or
• increase the volume of production • reduce the number of mistakes
• reduce the amount of liability
miss work
An expert system provides a permanent record of the expertise
Developing an expert system may force experts to develop a better/more transparent understanding of the problem domain
• Machine learning techniques may eventually be useful in building and refining a knowledge base
ES technology can be combined with other technology (such as neural networks) to create very complex systems 26
Expert Systems
Expert System Components
The users of the expert system must be knowledgeable about the domain in order to ensure that the advice provided by the system is reasonable
Expert systems have been developed in a wide variety of domains, such as medical diagnosis, the configuration of computer systems, prospecting for minerals, process control, etc.
Expert systems are rarely if ever designed to remove the need for experts; instead, they can be used to make the expertise more widely available or where it is dangerous to send the expert
An expert system consists of a variety of components, including a knowledge base, an inference engine, and a user interface that controls the interactions with the users
• e.g. medical specialists in remote areas, chemical or geological analysis on other
production systems, but NB to remember that
planets
27 © 2020 J.E. Anderson
expert systems are not necessarily rule-based 28
25 © 2020 J.E. Anderson
© 2020 J.E. Anderson
• inference engine is the same term we used in
© 2020 J.E. Anderson
Users
Most shells use a rule-based representation, which may include support for representing uncertainty
Knowledge Engineer
The shell’s inference engine may include several control strategies, such as forward search and backward search
Expert System Components
Expert System Shells
User Interface
Knowledge Acquisition
Knowledge Base
Inference Engine
V erification & Validation
Conventional Systems
Knowledge Engineering
Knowledge Engineering
“The first principle of knowledge engineering is that the problem-solving power exhibited by an intelligent agent’s performance is primarily the consequence of its knowledge base, and only secondarily a consequence of the inference method employed. Expert systems must be knowledge-rich even if they are method-poor. This is an important result and one that has only recently become well understood in AI. For a long time AI has focused its attentions almost exclusively on the development of clever inference methods: almost any inference method will do. The power resides in the knowledge.”
Knowledge acquisition is the most difficult problem encountered when developing an expert system
• Feigenbaum, in Luger, p. 277
The knowledge engineer must become a pseudo-expert in the domain in order to be able to converse with the expert
Explanation
The components of an expert system may be purchased as a package, referred to as a “shell”
29 © 2020 J.E. Anderson
Also some interface to conventional systems
A couple of very simple examples: Clips, Jess 30
31 © 2020 J.E. Anderson
32 © 2020 J.E. Anderson
Experts frequently are not consciously aware of how they solve problems and find it difficult to verbalize the steps that they take
• They likely have not had to verbalize this, even to themselves, for many years
© 2020 J.E. Anderson
Knowledge Engineering
Prototyping
Knowledge acquisition and knowledge base refinement are an iterative process
The development of most expert systems begins with a prototype
The knowledge engineer extracts the knowledge, formalizes the knowledge, represents the knowledge, and then tests the resulting system with the expert
The use of a prototype ensures that the approach (representation technique and inference strategy) is effective and that the problem is solvable
This process continues until the expert is satisfied with the performance of the system
Verification and Validation
Explanation
The contents of the knowledge base must be inspected carefully to ensure that the knowledge base is correct and complete
One of the features that is provided by most expert systems is an explanation of why a decision was made
Tools that assist in the manual V&V of a knowledge base are available
At its simplest, this explanation consists of a summary of the steps/rules that were followed in generating the conclusion; the summary is usually provided in an English-like format
• For example, the graphical display of the knowledge base
• Consistency checking in rules
• Looking for omissions (holes in the rulebase)
Tools are being developed that will carry out some V&V tasks automatically
36 © 2020 J.E. Anderson
© 2020 J.E. Anderson
© 2020 J.E. Anderson
35 © 2020 J.E. Anderson
33 34
Performance
common sense knowledge
It is difficult for the system itself to determine when it is within its area of competence and when it has gone beyond its competence — as a result, the system may provide bad answers to problems that are outside its competence
Explanation
System Maintenance
Having an explanation available creates a higher level of confidence in the conclusion than if an explanation is not available
The maintenance of an expert system is an extremely difficult task
Having an explanation facility also makes it easier to debug a system — the steps that were taken are specified in the explanation
It is almost impossible to specify completely any complex problem – the system will evolve over time
Systems with good explanation facilities can be used as teaching tools
It is very difficult to generate an explanation when a procedural representation is used
Brittleness
Brittleness
Expert systems perform very well in narrow areas
But they rarely if ever take into account general,
The system is said to be “brittle” at the edges of the expertise
Expert systems suffer from the “falling off the edge of the cliff” syndrome: performance does not degrade gracefully as problems begin to fall outside of the scope of expertise
Expert systems that do degrade gracefully are referred to as “robust” systems
Area of Competence
39 © 2020 J.E. Anderson
40 © 2020 J.E. Anderson
37 © 2020 J.E. Anderson
38 © 2020 J.E. Anderson
These are extremely rare – require extensive knowledge of own abilities (self knowledge)
Just as our knowledge about any specific domain changes over time: not just getting better at solving problems, but new developments in the field
Surface Reasoning
Surface Reasoning
In many expert systems, the model of the domain is significantly simplified in order to make the development of the expert system easier
The knowledge often consists of heuristics — shortcuts or simplifications learned from experience
The reasoning performed in such systems is referred to as “surface” reasoning because the more complex details that lie beneath the surface of the domain are not represented in the model
If (WBC < 3000) Then
Expert systems perform well in domains where this can be done: where there is little common- sense knowledge (as soon as you start with some, there’s an enormous amount you have to add!)
42 © 2020 J.E. Anderson
Surface Reasoning
Deep Reasoning
Surface reasoning is normally quite quick because the problem space is small
In these situations, a more detailed form of reasoning, referred to as "deep" reasoning, is required
Many expert systems use surface reasoning very successfully
Deep reasoning is often defined in terms of "first principles" or laws of the domain
In some situations, the simplification (or oversimplification) of a domain may prevent the expert system from reaching the correct conclusion
Requires a much more elaborate model of the domain
41 © 2020 J.E. Anderson
43 © 2020 J.E. Anderson
44 © 2020 J.E. Anderson
This statement is normally true of medical patients but does not consider the complex chain of interactions that occurs when a patient's white-cell count is low
wbc<3000
Immunity(Compromised)
immunity(compromised)
Deep Reasoning
Everyday Example
The search process becomes much slower than when surface reasoning is used because the problem space is much larger
What’s Meringue? How do you make it?
• Similar in people – that's why we use so many surface models!
There may be multiple layers of models with increasingly complex descriptions of the interactions of the objects
Surface reasoning: take egg whites. Beat them along with some sugar until they go stiff. Then do what you want with them – e.g. pile on a pie and broil for a short time until partly browned, or bake into a cookie or whatever at a low temp for
a long period of time until hard 46
We need more sophisticated mechanisms than simple rules to even begin to handle models of this complexity!
Meringue
Meringue
This is fine and with a few more details (egg white-sugar ratio, cooking temperatures) would work in many cases
e.g. see http://whatscookingamerica.net/Eggs/perfectmeringue.htm
But other times, this would mysteriously fail without a lot more information that ultimately comes from physics and chemistry
“Whipping egg whites is much like blowing air into a balloon. Beating or whisking causes the protein in the egg whites to unfold, forming films that trap the air bubbles, and the sugar stiffens the foam. A meringue is really nothing but a foam, and foam is a big collection of bubbles.” – anything preventing bubbles collecting makes meringue fail
These are the things you’d be told when studying to be a chef (or learn from many meringue episodes, though you would still miss many details in the explanation)
The age of the eggs matters
These deeper models work when the shallow one
The fat in even a tiny bit of yolk (or oil from your fingers) will stop bubbles from being trapped - humidity in the air will limit this too
doesn’t 47 © 2020 J.E. Anderson
48 © 2020 J.E. Anderson
45 © 2020 J.E. Anderson
© 2020 J.E. Anderson
Meringue
Brittleness
Cold eggs separate more cleanly, and a plastic bowl can trap oil in fine scratches that will lead to fewer bubbles
A knowledge base that is brittle often does not have sufficient knowledge - particularly deep knowledge that can be used to handle unusual situations
• So the understanding of this extends further to the understanding of many other concepts
Surface rules handle the common problems but often do not handle the less common problems well or at all
Similarly when using meringue after mixing – putting it on a hot pie lets it cook a bit and stops it from shrinking later, etc.
The use of deep knowledge is one of the factors that separates experts in a domain from those who are knowledgeable about a domain but are not true experts
Again, you wouldn’t need to know this unless
you wanted to fix problems or had a higher importance for your goal (quality) – then it’s vital49
•
They also know when to bother referring to the deep model (or what level to go to in a multi-level model)
Knowledge Representation
Knowledge Representation
Rules are the most commonly used representation for surface reasoning in ES
In complex problems in which deep reasoning is used, a structure must be imposed on the knowledge in order to permit the knowledge engineer to concentrate on the significant aspects of a problem instead of having to concentrate on the representation itself
As problems become more complex, the use of rules as a knowledge representation language becomes more problematic because there is no structure to the knowledge base
This structuring also eventually becomes necessary simply to manage a growing base of knowledge, irrespective of deep reasoning!
For example, in a knowledge base of 10,000 rules, it is difficult to examine the knowledge base and manually determine the impact of making a change
© 2020 J.E. Anderson
50 © 2020 J.E. Anderson
51 © 2020 J.E. Anderson
52 © 2020 J.E. Anderson
Limitations of Expert Systems
Limitations of Expert Systems
The major problem encountered when developing an expert system is building the knowledge base and ensuring that it is correct and complete
Expert systems must be integrated with conventional systems (such as database management systems) if real-time response is to be provided
Not all complex problems should be attacked using ES technology
The development of expert systems is expensive -- a production system will normally require several years to develop at a cost of several million dollars
Do not use ES technology if conventional technologies can be used
• Similar to AI in general: if there's a well known algorithm, the advantages to using it are pretty strong!
However, this cost can be recovered many times over if the system is able to function at an expert level of performance
Mycin Expert System
Mycin Expert System
Mycin was developed by the AI group and medical faculty at Stanford University to diagnose and recommend therapy for infectious diseases of the blood
Mycin was developed using a rule-based representation language (developed in Lisp) that includes certainty factors
Mycin first diagnoses the disease and then selects the most appropriate antibiotic to combat the disease (or several diseases if the diagnosis can not be limited to one disease)
In blind tests, Mycin has consistently performed as well as human experts
© 2020 J.E. Anderson
© 2020 J.E. Anderson
55 © 2020 J.E. Anderson
56 © 2020 J.E. Anderson
53 54
Mycin has never been commercialized -- in part because the system is limited to only certain types of infectious diseases
Xcon Expert System
Xcon Expert System
Xcon was developed jointly by the AI group at Carnegie-Mellon and by staff at Digital Corp. to configure computer systems
Xcon generates detailed technical descriptions of each system, including a list of all components required, a diagram of spatial relationships between components, the cable lengths, etc.
Each mistake in configuring a system can cost Digital a significant amount of money as the purchaser has to wait for additional parts
Xcon can generate a complete specification in about 1 minute, it takes a team of technical specialists 20 minutes to perform the same task on average – sometimes hours
Xcon is able to recognize invalid configurations (e.g. some components may be incompatible)
Digital expects Xcon to be correct about 95% of the time -- it is realized that Xcon will never
have complete knowledge 58
One Sample XCON Rule
Lockheed Clavier System
57 © 2020 J.E. Anderson
© 2020 J.E. Anderson
59 © 2020 J.E. Anderson
differs and how to fix them 60 © 2020 J.E. Anderson
Lockheed uses an analogous process to arrange parts in a clavier (used to cure parts after moulds have been poured)
Parts must be arranged to fit a clavier load, and slight variations in temperature across area must be accounted for so that they heat evenly ($50k parts tossed if they don’t)
Uses a case-based approach (more later) – remembers previous loads and problems, remembers similar loadings that worked well, then considers individual ways this load
Polygram Expert System
Polygram Expert System
Polygram presses millions of CD's per day (but less each year...)
Workers with more than 3 years of experience average 3 runs to correct a problem with an image while workers with less than 3 years of experience average 10 runs
Each run presses and images (paints) 50 discs; discs with flawed images must be destroyed (even they'd play perfectly fine, no one is going to buy them)
A prototype ES was developed in 8 weeks and covers about 50 of the problems
There are 75-100 potential causes of flaws in generating the images on the CD's (e.g. too much paint on the arm, misalignment)
The system was developed using Level 5 Object (a shell) and uses scanned images of typical printing problems on a touch-screen monitor to direct the user to a solution to a
Polygram Expert System
Sendai Subway
The ES does not interact with any other systems and is almost completely graphically oriented
The subway in Sendai, Japan is completely automated during the day, and has operated without incident since 1987
In initial tests with the ES, workers with over 3 years experience required 2 or 3 runs to correct problems while workers with under 3 years required 4 or 5 runs
System built using knowledge of skilled operators, using predictive fuzzy logic (we’ll see fuzzy logic later - imprecision)
It is estimated that the system saves approximately $10 million per year
A skilled operator anticipates the need for change before the change is required (e.g. slow down when a hill is coming up)
© 2020 J.E. Anderson
© 2020 J.E. Anderson
63 © 2020 J.E. Anderson
64 © 2020 J.E. Anderson
problem
61 62
Stops closer to a target than a human, uses 10% less energy
Sendai Subway
Sendai Subway
System uses electronic markers on track so the system knows where a car is
Emergency rules exist in case a train needs to stop for sudden events
Fuzzy controller blends desired speed, comfort, safety
So smooth most riders apparently do not use standing straps
65 © 2020 J.E. Anderson
Hong Kong also uses an expert system to pre-screen visa applicants according to 66 specified conditions © 2020 J.E. Anderson
Other Examples:
Hong Kong uses an expert system to schedule engineers doing night maintenance on the subway (10,000 people doing 2600 operations in a week)