CCS 3400 Knowledge Based Systems Kaje David Murithi

Meru University of Science and

Technology School of Computing
and Informatics Department of
Information Technology

LECTURE 6
Inference and Knowledge Processing

Outline

• Process of reasoning and reasoning types

• Reasoning methods

– Deductive Reasoning

* Single inference
* Multiple inference
– Inductive reasoning

6.1. The Process of Reasoning

Reasoning: The process of drawing inferences or conclusions; moving

from what is known (fact) to what is unknown (inference).

6.1.1. Types of Reasoning:

1. Reasoning from signs:

2. Cause and effect:

3. Reasoning by analogy:

4. Reasoning by example:
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Reasoning from signs:

Assuming that a sign or symbol represents or indicates something specific.

• Example: making a phone call and receiving a busy signal. The assumption
is that someone is already on the line.

The sign, busy signal is used to infer that someone is on the

phone. There should be enough information to relate the sign
to the inference

• Beware of stereotypes like: “Luos are proud and loudmouthed”. E.g. given
Wafula is a Luo, then you infer Wafula is proud and loudmouthed.
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Cause and effect:

Inferring that one event causes another

• “I was late because my alarm didn’t go off.”

or reasoning with the result in mind

• “If I don’t study, I will fail the test.”

Important that there is enough information to link the events.

Beware of assuming that things that happen sequentially are causally related

• “I got HIV/AIDS because I had unprotected sex”

• Reasoning by analogy:

Drawing a parallel between two similar events, people, or

traits. Based on comparisons.

• Example: If all mothers are women, and Ann is a mother, then Ann must be
a woman.

Care should be taken to always check analogies for validity, because

these don’t always work backwards.

• Example: Because Ann is a woman doesn’t mean she’s a mother.

• Reasoning by example:

Basing conclusions on facts, illustrations, or cases.

• Example: Conclusions drawn from the results of polls or surveys.

• Example: Mende has an approval rating of 40%, which is 15% more them
his closest challenger Mbu; so he will be elected in the next election.”

When drawing conclusions, always ask, “Do I have enough facts to support this?”
CCS 3400 Knowledge Based Systems Kaje David Murithi

6.2. Reasoning Methods

Knowledge Representation allows encoding or formalization of

quantitative facts and knowledge.
Reasoning and inference allows generation of new and useful knowledge,
conclu- sions and recommendation.
Inference methods fall into two general categories.
• Deductive Reasoning.

• Inductive Reasoning.

6.2.1. Deductive Reasoning

• The method used in propositional and predicate calculus.

• The inference engine combines the rule (or predicates) to arrive at the final
answer.

• Starts with a set of axioms, or commonly accepted premises that one cannot
derive from a system itself.

• Using the axioms and proven formulae, deductive reasoning can deduce new
conclusions.

• Deductive Reasoning: Example Axiomatic System

1. Akidiva is a man.

2. Akidiva is a Luhya

3. All Luhyas are Kenyans.

4. Kibaki is a leader.

5. All Kenyans are either loyal to Kibaki or hate him.

6. Everyone is loyal to someone.

7. People only try to cheat leaders they are not loyal to.

8. Akidiva tried to cheat Kibaki.

9. All men are persons

CCS 3400 Knowledge Based Systems Kaje David Murithi

Deductive Reasoning: Axiomatic Systems

• Process of Deductive Reasoning

The Inference process consists of two

parts Single Inference.

• Process of applying inference rules to combine two pieces of knowledge to

derive a new premise.

• May be an intermediate step or the final recommendation.

• Multiple Inference
• The sequence or order of applying the single inference process to the entire
knowledge base in order to derive final conclusions.

Note: The knowledge-processing capability of an intelligent system is composed by

the two parts above.

• Inference in Propositional Logic and Calculus

There are a number of rules of inference in propositional logic that allow

derivation of new statements from combining two previously accepted
ones.

• Modus ponens
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Hypothetical syllogism
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Modus tollens

Modus Ponens has to be a tautology for it to be true.

Tautology: The truth value of a statement form is always T no matter
what the truth values of its components are.
Contradiction: Opposite of tautology. Always F.

• Inference in Predicate Calculus

Predicate calculus uses rules of inference in propositional calculus.

Modus ponens and hypothetical syllogism are used.
Predicate calculus has predicates and quantifiers (Existential and
Universal) that do not exist in propositional calculus.

• Quantifiers: Provide more power for the system because the content of propo-
sitions can be broken into predicates - unification and resolution.

6.2.2. Rules of Inference

CCS 3400 Knowledge Based Systems Kaje David Murithi

• Deductive Reasoning: Axiomatic Systems

A system using the below approach is called a natural deductive system

• Resolution and Clausal Form

6.2.3. Resolution in FOL

An algorithms for proving facts true or false by virtue of contradiction

e.g. to prove X is true, we show that the negation of X is not true e.g.
Fact:
CCS 3400 Knowledge Based Systems Kaje David Murithi
• Not feathers (X) or bird (X)
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Feathers (X)

Sentence 1 states “ either X does not have feathers or else X is a

bird “ Sentence 2: X has feathers.
To prove “X is a bird”, we first add an assumption that is the negative of
that predi- cate. The facts then become:

• Same as above.

• Same as above

• Not bird (X)

In sentences 1 & 2, not feathers (X) and feathers (X) cancel each other
out. Resolv- ing 1 & 2 produces the resolved, sentence and which is
added.

• Same as above.

• Same as above

• Same as above

• bird(X)

It is clear 3 & 4 cannot both be true: either X is a bird or not-thus a

contradiction. Thus we have just proved our first assumption -3 is false,
4 must be true.

6.2.4. Unification

Takes two sentences in FOL and finds a substitution that makes them look
the same- required to prove theorems using resolution.
If two predicates are identical, then they match by definition.
If one or both contain variables, then appropriate substitutions must be
found using unification as follows:-

• A variable can be replaced by a constant.

CCS 3400 Knowledge Based Systems Kaje David Murithi

• A variable can be replaced by another variable.

• A variable can be replaced by a predicate, as long as the predicate does not

contain that variable.
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Unification Example

Consider hates (X, Y)

• hates (Onyango, Kales)

• hates (Okeyo, Cabbage)

Unify 2 with 1 by binding Onyango to X and Kales Y, also unify 3 with 1
by binding Okeyo to X and Cabbage to Y.
• Hates (X, Vegetable (Y))

• Hates (Onyango, Vegetable (Kales))

• Hates (Z, Kales)

Unify 6 with 1- X with Z, Y with Kales.
Unify 4 and 5, bind Onyango to X, Kales
to Y.
Note: Prolog uses a generalized version of unification algorithm called match.

6.2.5. Multiple inference in deductive reasoning

Single inference has a solid theoretical foundation.

• Applying rules of inference to the entire knowledge base requires tools for
analysis and heuristics that could improve the speed of system response - MI
Multiple Inference (MI)- Involves testing rules or predicates to find the
one which must fire next.
The commonly used methods of multiple inference are: Graphs, Trees,
and the And/Or
• Graph.

• Backward Chaining.

• Forward Chaining.

6.2.6. Graphs

• Uses graph theory.

CCS 3400 Knowledge Based Systems Kaje David Murithi
• Easily understandable.

• Consists of nodes connected by arcs

CCS 3400 Knowledge Based Systems Kaje David Murithi

• Directed Graph:

The direction of an arc connecting two nodes is important.

• Path: The sequence of nodes and arcs connecting the beginning node of the
path to the end node of the path

• Cycle: The ending node of the path is the same as the beginning node.

• Tree

A directed graph with no cycles which starts with a beginning node (root)
and ends with ending nodes (leaves).
Paths start from the root and end with leaves in a
tree There is only one path from the root to each
leaf.
Used extensively in A.I. And Expert Systems e.g. and/or graph and decision tree.

• And/Or Graph

Rules and predicates are shown with nodes and arcs.

The two arcs in the AND diagram are connected by another arc signifying
that both A and B must be true to reach conclusion C from this rule.
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Examples

6.2.7. Backward and Forward Chaining.

Two well known and commonly used methods of multiple inference in

expert sys- tems are

• Backward Chaining.

• Forward Chaining.

6.2.8. Inferencing

The process of accessing the knowledge stored in the knowledge base in

order to make conclusions.
The program for inferencing is typically called the inference engine or
control pro- gram.
In rule based systems it is also called a rule interpreter.
Purpose: Direct the search through the knowledge base. The engine determines

• Which rules to investigate,

• Which to eliminate, and

• Which will attribute to a match.

6.2.9. Criteria for choosing inferences

• The logical reasoning process.

CCS 3400 Knowledge Based Systems Kaje David Murithi
• Design features of the system.
CCS 3400 Knowledge Based Systems Kaje David Murithi

• The inputs and where they come from.

• The outputs and where they go.

• How the inputs and outputs map to forward or backward chaining.

6.2.10. Forward Chaining

The system requires the user to provide facts pertaining to the problem.
The inference engine tries to match each fact with the antecedent or if part
of a rule. If the match succeeds, the rule fires and the consequent of that rule
is established and is added to the known facts of the case. The process
continues until the inference engine has drawn all possible conclusions by
matching facts to antecedents of rules in the knowledge base.
Among these could be goals of the system.

• The Forward Chaining algorithm

1. Enter new data

2. Fire forward chaining rules

3. Rule actions infer new data values

4. Go to step 2

5. Repeat until no new data can be inferred

6. If no solution, rule base is insufficient

CCS 3400 Knowledge Based Systems Kaje David Murithi

• Reasons for forward chaining

When everything that can possibly be concluded about a set of data

needs to be known.
Many conclusions are possible from a single data item.
It is important to communicate new conclusions to the user immediately.

• Characteristics of forward chaining:

• Good for monitoring, planning, and control

• Looks from present to future.

• Works from antecedent to consequent.

• Is data-driven, bottom-up reasoning.

• Works forward to find what solutions follow from the facts.

• It facilitates a breadth-first search.

• The antecedents determine the search.

• It does not facilitate explanation.

6.2.11. Backward Chaining

The multiple inference starts with a question or goal.

The inference engine starts from the consequent of a rule and goes
backward to the antecedent or IF part of the rule.

• The Backward Chaining algorithm

1. State a specific goal (question)

2. Find rules which resolve the goal

3. At runtime, answer questions to satisfy the antecedents of the rules as re-

quired

4. Obtain a result (goal resolved or not)

CCS 3400 Knowledge Based Systems Kaje David Murithi

• Backward Chaining example (see diagram in the exercise)

The goal is to establish whether G is true.
The inference engine checks to see which rule has G as its consequent.
• Rule 4 fires

To conclude from this that G is true, E or F must be shown

to be true. E becomes the current goal of the system
The inference engine checks to see which rule has E as its consequent
• Rule 2 fires

The current goal becomes D

The inference engine checks to see which rule has D as its
consequent There is none.
It asks the user to provide information
about D D is True
The inference engine concludes that E is true and G is
also true. D is False The system fails to establish the
truth of E
In this case, it backtracks and picks up F to get at the goal G.
B and C become the current goal. B is not the consequent of any rule and
the system asks the user if it is true.
B is False
CCS 3400 Knowledge Based Systems Kaje David Murithi

• No matter what C is, the conditional part of rule 3 is false and the inference
engine fails to establish whether G is true.
CCS 3400 Knowledge Based Systems Kaje David Murithi

B is True
• The inference engine pursues C etc

• Reasons for Backward Chaining

• There is a clear set of statements which must be confirmed or denied.

• A large number of questions could be asked of the user, but typically only a
few are necessary to resolve a situation.

• It is desirable to have interactive dialogue with the user.

• Rule execution depends on data gathering which may be expensive or diffi-

cult.

• Characteristics of backward chaining:

• Good for Diagnosis.

• Looks from present to past.

• Works from consequent to antecedent.

• Is goal-driven, top-down reasoning.

• Works backward to find facts that support the hypothesis.

• It facilitates a depth-first search. The consequents determine the search.

• Facilitates explanation.

• Backward vs. Forward chaining

Backward Chaining

• Useful when the number of goals is small and the and/or graph does not have
numerous levels.

• In some systems, the user has the choice of telling the inference engine which
goal it must pursue - Goal selection by the user.

Forward Chaining Performs well when the number of goals is large,

the user has a given set of facts at the start and wants to find the
CCS 3400 Knowledge Based Systems Kaje David Murithi

implications of these facts.

CCS 3400 Knowledge Based Systems Kaje David Murithi

6.2.12. Inductive Reasoning

Most inference rules in A.I. have their theoretical basis in deductive

reasoning. Most learning is through experience which is an inductive
process.

• Exposure to a number of similar circumstances that lead to a certain conse-

quence leads to generalization and development of rules for dealing with that
group of circumstances.

Inductive Reasoning: The process of going from specific cases to general

rules. Example: Qualitative methods e.g. statistics.

6.2.13. Methods for inductive reasoning in expert systems include

• Decision trees.

• ID3

• Case-based approach: reasoning by analogy

• Decision trees

Must have a set of representative cases for which the goal or decision value is known

E.g. the following data for the possible cases in the Mortgage Loan Case.

• ID3

The tree in its raw form is inefficient. Try to find a tree with the
minimum number of nodes. Method used is called ID3 developed by
Quinlan. Example is as shown.
CCS 3400 Knowledge Based Systems Kaje David Murithi

• Case-based approach: reasoning by analogy

• Intuition – You don’t pursue theory – the answer just appears

• Heuristics – Based on rules of thumb based upon experience

• Generate and test – trial and error.

• Abduction – reasoning back from a true conclusion to the premises that may
have caused the conclusion.

• Default – assume general or common knowledge by default.

• Auto epistemic – Self-knowledge, reasoning about your own knowledge.

• Non-monotonic – Previous knowledge may be revised when new evidence is

obtained.

• Formal reasoning – Synthetic manipulation of data structures to deduce new

facts by following prescribed rules of inferences.

• Metalevel reasoning – manipulating knowledge about knowledge.

CCS 3400 Knowledge Based Systems Kaje David Murithi

Revision questions

Example ✐. ForwardChainingexample

Solution:
CCS 3400 Knowledge Based Systems Kaje David Murithi

E XERCISE 9. Learning Activities

What is inference?
Is inference
problem solving?
What are AI
inference
strategies?
Describe forward and backward chaining
inference controls. What does an inference
engine do?