1. Introduction and JUnit
Rule-based Systems
1
Despite their success, technologies like neural nets and SVM’s are knowledge free—”dumb” in many ways. To illustrate this, suppose that your child answered “105” when asked “how much is 98 + 9?” But when you ask “why”, he answers … because I just happen to know that 97 + 9 = 106 as well as 99 + 9 = 108, and 98 is evenly between 97 and 99, so the answer should be evenly between 106 and 108. In other words, they are entirely data-driven, and unaware of the rules of addition. Even in the non-mathematical world, we strive for understanding. For example, we look to rules of history when engaging in diplomacy.
1
Learning Objectives
Understand …
… how to design rule-based systems
… how to collect knowledge
Adapted from Savich
2
In this section, we will learn about rule-based systems but we will also need to discuss the issue of where the knowledge base comes from. Sources for expert systems–a type of rule-based systems—have been mainly human. This may appear to be inconsistent with machine learning. However, for many applications such as medicine, in order for machine-learned artifacts to be acceptable to society they must be explainable. For this reason, there are strong ties between machine learning and knowledge-based systems.
2
Rule-based Systems
3
Definition
Knowledge for Rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
Definition of Rule-based System
Knowledge can be represented as rules
Knowledge separated from inference process
4
Additional Properties
Can explain its reasoning
Typically shallow knowledge
The great advantage of rule-based systems is that they can explain their reasoning.
There is little limit on how deep reasoning can go, though rule-based systems in practice have seldom been found to go very deep.
5
Typical Origin of rule-based System
Give users a step-by-step method of analyzing their physical fitness, offering techniques and strategies which lead to enhanced fitness practices and habits.
Allow long-term use of the tool to track progress and to adapt the system’s advice.
The figure shows an example of how an exoert rule-based system can come about. There is typically an individual whose knowledge and expertise are considered valuable, and a desire to codify it.
6
Alternatives to rule-based Systems
Straight processing
hard to adapt to new expertise
must build reasoning into every new part
long time to prototype
Model and simulate
insufficient understanding of the process
Spreadsheet/existing tool
lacks symbolic processing
Unexplained deep learning
Rule-based systems are used when traditional processing, simulation etc. are not practical, but expertise is available.
7
Rule-based Systems
8
Definition
Knowledge for rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
Definition
Knowledge for Rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
In this section, we will discuss a common structure of knowledge.
Data /Facts
Data in context, e.g.,
Fact: Antonio is an animal
Fact: Antonio has stripes
The most elementary form of knowledge is data. You can think of this as an entry in a table—more specifically, as the value of a field in a record. For example, if each record corresponds to a name, and there is a type field, then the Antonio record has “animal” for the value of its type. The record has “stripes” in its characteristic field.
In the context of rule-based systems, we use the word fact for data that’s provided in context—in other words “Antonio has stripes,” not just “stripes” or “24.”
9
Facts (Data)
“Animal has stripes”
Typically converts, in Animal object, to
pattern = “striped”
Attribute
Value
Facts are generally of the form
field (or variable, typically attribute of an object) has value ….
We have already seen “facts” in the context of propositional logic.
10
What is Knowledge?
Factual knowledge
e.g. “there were two snowstorms in MA between August 1994 and December 1994”
Non-data Declarative knowledge
e.g. “Liberal kings are rare”
(Non-data) Procedural knowledge
e.g. “To replace a bike chain, first …”
Meta-knowledge
knowledge about knowledge
factual
declarative
meta
procedural
Rule-based systems are based on knowledge (and are more generally referred to as knowledge-base systems). Knowledge includes facts, but is more general. Here, we give examples.
Declarative knowledge consists of statements that (depending on the circumstances) can be either true or false. In other words, they are booleans.
Rule-based systems usually deal with factual and declarative knowledge, although there are systems that deal with procedural knowledge (how to do something) and meta-knowledge (knowledge about knowledge).
11
Definition of Non-fact Knowledge
A function which, given input data,
produces output data.
Sore muscles
should be rested
Chuck has a sore shoulder
Chuck rest his shoulder
A unit of knowledge that isn’t a fact is a kind of generator: given fact(s), it may produce other fact(s), as in the figure. We have already seen knowledge in the form of first-order logic.
12
Shallow vs. Deep Knowledge
e.g. “dropped objects fall to the ground”
deeper: “any two bodies in space attract each other”
deeper: “any pair of entities exist in a space-time curve”
Deeper = increased understanding
We generally think of knowledge as having depth, as in the example. There has always been an attempt to drive rule-based system knowledge deeper, though most rule-based systems I have encountered do not reason as deeply as they could in theory.
13
Rule-based Systems
14
Definition
Knowledge for rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
Definition
Knowledge for Rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
In this section, we will discuss a common structure of knowledge.
The Players
Knowledge
Base
Knowledge
Engineer
Rule-based
Traditionally, expert system knowledge has been encoded in a pre-arranged format by a knowledge engineer interviewing the rule-based. A knowledge engineer is a little like a business analyst, but more technical because they encode the knowledge.
There is usually a single rule-based. When there are more than one, they typically do not agree on everything, which leaves open the question of who selects.
15
Problems to be Handled
Separate knowledge from reasoning
Represent knowledge
Decide reasoning method
Integrate user interface
The most important feature of expert systems is that they confine the knowledge and the reasoning mechanism to separate modules. The question of how, exactly, to represent (express ) the knowledge has also to be decided. There is more than one way to perform reasoning.
16
Separating Knowledge & Inference
Knowledge
base
Inference
(A => B) & A true
=>
B true
The inference mechanism, known as the inference engine, performs logic such as modus ponens Modus ponens is the following logical operation:
If it is known that
statement A implies statement B,
and also that statement A is true,
then it follows that
statement B must be true.
The most common way to represent knowledge is to express it in multiple “If … then…” rules, as shown in the example. We shall describe such rules in detail.
17
Separating Knowledge & Inference
Knowledge
base
Inference
“IF out of breath,
THEN training is light”
(A => B) & A true
=>
B true
Fact List
out of breath
The inference engine infers new facts from the knowledge base and the fact list. For example, the inference engine uses modus ponens to infer the fact “training is light” from the rule “IF out of breath, THEN training is light” and the fact “out of breath.” The fact “training is light” is then added to the fact list.
18
Separating Knowledge & Inference
Knowledge
base
Inference
control
data
User
interface
Control
The figure shows the three principal components of expert systems. Date flows are shown with solid lines: data flows everywhere except from the inference engine. On the other hand, the inference engine tends to be a center of control (expect for overall control of the expert system).
19
Expert System Architectures
Rule-based
Model-based
Case-based
Other
We will discuss the expert system types listed in the figure. The most important one is rule-based. We discuss model-based below. Case-based is used to solve problems for which there is an existing set of problem-solution pairs (typically mush more complex than simple input-output pairs for neural nets).
20
Rule Terminology
IF
animal has stripes antecedent (fact)
AND conjunction
animal roams in large herds antecedent
THEN
animal is zebra consequent
OR disjuction
animal is okapi consequent
Rules are the basic form for many knowledge bases. A rule is composed of a conjunction (AND-ing) of facts in the IF part and a disjunction (OR-ing) of facts in the THEN part. This form can’t be decomposed into simpler rules. (An OR-ing of facts in the IF part and an AND-ing of facts in the THEN part can be decomposed).
21
Example
22
http://www.expertise2go.com/e2g3g/wine/
Includes explanation
Model-based Expert Systems
Knowledge
base
Inference
User
interface
control
data
(Classical) Model
“If bicep is weak, weight routine 12 is good”
“bicep weak?”
“If A=>B and A is true, then B & use model for consequences”
The body’s muscular map… (e.g. shows stress points from weight routine 12)
Pure expert systems are based on knowledge about the problem (the knowledge base, in one module) and a means for reasoning about it (inference, in another module). This is different from most programs, which are built around models. A model is a conception that’s either described in writing or else in the heads of developers. For example, a train-scheduling program is based on a conception of trains and stations and passengers taking trips.
A model-based expert system combines both. The design depends on the problem, but the inference engine calls on the model as well as the knowledge base.
23
Rule-based Systems
24
Definition
Knowledge for rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
Definition
Knowledge for Rule-based Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
In this section, we will discuss a common structure of knowledge.
Inference
Forward chaining
Backward chaining
There are two principal kinds of rule-based system reasoning. In forward chaining, the known facts are used as the starting point. In backward chaining, the fact we want to know the truth of (there must be one) is the starting point.
Knowledge = facts + rules
Knowledge
base
Inference
Engine
User
interface
rules
facts
Rule base
(given)
given
deduced
The collection of rules (the rule base) for a rule-based system is given, and typically does not change. Some facts are given—when the system begins or else supplied by the user at runtime in response to prompts from the system. Additional facts may be deduced at runtime, as in the example above. In a sense, the latter are learned.
26
1. Forward Chaining
Initial fact list: Brian is a manager
Rules:
1) IF X has a large office THEN X is happy
2) IF X is a manager THEN X has a large office
Goal: Generate all consequents
In this example, there are two rules and a single known fact.
27
Mechanics of Forward Chaining
Apply all rules repeatedly, adding to fact list
each time, until no new fact are found.
Initial fact list: Brian is a manager
After first application of all rules:
1) Brian is a manager
2) Brian has a large office
After second application of all rules:
1) Brian is a manager
2) Brian has a large office
3) Brian is happy
Forward chaining cycles through the two rules. On the first cycle, the additional fact Brian has a large office is deduced because Rule 2 “fires.” The two rules are tried again, and this time Rule 1 fires, deducing Brian is happy.
Rather than generate every deducible fact, one sometimes has a target fact such as Brian has a large office. The process stops when that target fact is deduced.
28
Rule-based Systems
29
Definition
Knowledge for Expert Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
2. Backward Chaining
Initial fact list:
Brian is a manager
Rules:
1) IF X has a large office THEN X is happy
2) IF X is a manager THEN X has a large office
Goal: Answer query:
Is Brian happy?
Backward chaining requires a target fact such as Brian is happy. We look at every rule containing this fact as consequent. This is only rule 1 in the example (in general there could be several such rules). Now we try (recursively) to prove every antecedent—they are the new target facts.
30
Backward Chaining
Initial fact list: Brian is a manager
Rules: 1) IF X has a LargeOffice THEN X is happy
2) IF X is a manager THEN X has a LargeOffice
Goal: Answer query: is Brian happy?
Brian is happy
Brian has a
LargeOffice
Brian is a manager
i
ii
This figure shows the backward chain of reasoning (steps i and ii).
Notes to Precede Backchaining Alg.
2.1
2.3
2.2
Q
f*
2.2.1
2.2.2
f
2.2.1.1
f
2.3.1
f
*n = not consequent
*f = known fact
1.1
1.2
n*
f
i
This schematic shows a set of five rules and a target fact Q.
There are two rules that infer Q. The first is of the form IF 1.1 AND 1.2 THEN Q (we are dispensing with full English statement of facts in order to emphasize the logic). We now try to establish fact 1.1. According to the figure, this is known. However, fact 1.2 is not known, nor is it a consequent (so there is no hope of proving it). For this reason, we abandon the rule IF 1.1 AND 1.2 THEN Q as a means for proving Q, and move on to seeing whether we can establish the antecedents of the rule IF 2.1 AND 2.2 AND 2.3 THEN Q.
32
33
1
2
3
4
5
7
8
9
11
12
13
14
6
10
2.1
2.3
2.2
Q
f*
2.2.1
2.2.2
f
2.2.1.1
f
2.3.1
f
1.1
1.2
n*
f
This figure shows the order in which facts are “visited.” It turns out that the antecedents of the rule “IF 2.1 AND 2.2 AND 2.3 THEN Q” can indeed be established, and so Q has been established. Note that backward chaining does not add new facts to the fact list. Instead, it stacks recursive calls.
The appendix describes a Java implementation of backward chaining.
33
Rule-based Systems
34
Definition
Knowledge for Expert Systems
Architecture
Inference Methods
Forward Chaining
Backward Chaining
Knowledge Engineering
Rules References
Knowledge Engineering
Acquire
& encode
knowledge
Test
knowledge
State
problem & UI
Structure
knowledge
Process of soliciting expert’s knowledge
The process of knowledge acquisition is cyclic in nature, as in the figure, and necessarily agile. You typically start by specifying the problem, then structuring the knowledge, acquiring and encoding a batch, and then showing it to the expert.
35
Example: Fitness E. S.
State problem
& UI
Structure
knowledge
Acquire & encode
knowledge
Test
knowledge
Problem: Give the user a step-by-step way of analyzing his/her fitness. UI: be able to jump at will between categories (e.g. definitions, symptoms & recommendations
Knowledge is divided into Status, Journal, Difficulties and Recommendations
If you experience two or more of the following characteristics, you are a “Complete Beginner” etc.
Show expert what you have done so far.
This figure is an example that illustrates this process for a physical fitness advisor.
36
Expert System Shell Example: pyCLIPS
37
>>> import clips
>>> clips.Reset()
>>> clips.Assert(“(duck)”)
>>> clips.BuildRule(“duck-rule”, “(duck)”, “(assert (quack))”, “the Duck Rule”)
>>> clips.PrintRules()
MAIN:
duck-rule
Expert system shells facilitate the expression of facts and rules, and they control chaining. Python-base shells include PyKE and PyCLIPS. A simple PyCLIPS rule is shown above (“IF quack THEN duck”). PyClips allows for sophisticated facts, coded as objects.
Other systems use XML.
37
Demonstration of CLIPS
38
(turn off sound??)
Making decisions on bacteria type
http://www2.hawaii.edu/~milica/ics491_spring04/clips.txt
pyknow
39
Diabetes diagnosis example:
Appendix: Expert System Example
40
Ex: Interview Radar Expert—Repair E.S.
41
Knowledge engineer: The question is, supposing everything is up and running, and that same thing happened?
Expert: Well, because of, let’s say, and intermittent cable or a cable that is briefly grounded, suppose that the clock stops for a few milliseconds and then restarts. If it is literally a few milliseconds, like 3 or 4, or something like that, you may not notice; you wouldn’t notice that symptom. For this to happen, and to be sure that you would recognize it, you would have to be there for, like 12 seconds.
Knowledge engineer: To bring down the track module?
Expert: Yeah.
The figure is an edited transcript of an interview of a radar expert on problems that seamen may encounter. It illustrates the contrast between an expert’s view of problems and their mode of expression with the desire of the knowledge engineer to encode it. This gap is bridged by skillful channeling.
41
Kn. Acquisition Interview II
Knowledge engineer: What else could it mean?
Expert: Well, there, is the track — all right, there are some other cases. If you have an extremely large number of redundant tracks, one of the functions the track association module does is to monitor the track file for, you know, redundant tracks that have gotten into the system. You know, if two tracks crossing each other may become redundant, it’s possible, as we have seen in the past few days, where if they turn off XXX in a severe environment, what tends to happen …
Turn into Diagram
Computer crashes within minutes of loading
&
Track association module error 17
Track association —–> Navigation
module timeout clock down
&
XXX turned off
&
Severe
environment
Track association
module overload ——> Turn on XXX & reload
The knowledge engineer may draw an implication diagram as in the figure.
43
Turn into Rules
CCWSL & TAN17 –> TAMT
TAMT –> NCD
TAMT & XXXOFF & CENV –> TAMO
TAMO –> TOXXXR
— add uncertainty
The diagram is then converted to rules. This example used an expert system shell developed at Rutgers University but there are many shells, that make it relatively easy to encode once the knowledge is understood
44
/docProps/thumbnail.jpeg