Representing Knowledge Using rules/AI
1. Representing knowledge using rules: Procedural Vs Declarative
knowledge
We have discussed various search techniques in previous units. Now we would
consider a set of rules that represent,
1. Knowledge about relationships in the world and
2. Knowledge about how to solve the problem using the content of the rules.
Procedural vs Declarative Knowledge
Procedural Knowledge
A representation in which the control information that is necessary to use the
knowledge is embedded in the knowledge itself for e.g. computer programs,
directions, and recipes;
these indicate specific use or implementation;
The real difference between declarative and procedural views of knowledge lies in
where control information reside.
For example, consider the following
Man (Marcus)
Man (Caesar)
Person (Cleopatra)
∀x: Man(x) → Person(x)
Now, try to answer the question. ?Person(y)
The knowledge base justifies any of the following answers.
Y=Marcus
Y=Caesar
Y=Cleopatra
We get more than one value that satisfies the predicate.
If only one value needed, then the answer to the question will depend on the order
in which the assertions examined during the search for a response.
If the assertions declarative then they do not themselves say anything about how
they will be examined. In case of procedural representation, they say how they
will examine.
1
Representing Knowledge Using rules/AI
Declarative Knowledge
A statement in which knowledge specified, but the use to which that knowledge is to
be put is not given.
For example, laws, people’s name; these are the facts which can stand alone, not
dependent on other knowledge;
So to use declarative representation, we must have a program that explains what is to
do with the knowledge and how.
For example, a set of logical assertions can combine with a resolution theorem prover
to give a complete program for solving problems but in some cases, the logical
assertions can view as a program rather than data to a program.
Hence the implication statements define the legitimate reasoning paths and automatic
assertions provide the starting points of those paths.
These paths define the execution paths which is similar to the ‘if then else “in
traditional programming.
So logical assertions can view as a procedural representation of knowledge.
2. Logic programming
Logic Programming – Representing Knowledge Using Rules
Logic programming is a programming paradigm in which logical assertions viewed
as programs.
These are several logic programming systems, PROLOG is one of them.
A PROLOG program consists of several logical assertions where each is a horn
clause
i.e. a clause with at most one positive literal.
Ex : P, P V Q, P → Q
The facts are represented on Horn Clause for two reasons.
1. Because of a uniform representation, a simple and efficient interpreter can write.
2. The logic of Horn Clause decidable.
Also, The first two differences are the fact that PROLOG programs are actually sets
of
Horn clause that have been transformed as follows:-
1. If the Horn Clause contains no negative literal then leave it as it is.
2
Representing Knowledge Using rules/AI
2. Also, Otherwise rewrite the Horn clauses as an implication, combining all of
the negative literals into the antecedent of the implications and the single
positive literal into the consequent.
Moreover, This procedure causes a clause which originally consisted of a disjunction
of literals (one of them was positive) to be transformed into a single implication
whose antecedent is a conjunction universally quantified.
But when we apply this transformation, any variables that occurred in negative literals
and so now occur in the antecedent become existentially quantified, while the
variables in the consequent are still universally quantified.
For example the PROLOG clause P(x): – Q(x, y) is equal to logical expression ∀x:
∃y: Q (x, y) → P(x).
The difference between the logic and PROLOG representation is that the PROLOG
interpretation has a fixed control strategy. And so, the assertions in the PROLOG
program define a particular search path to answer any question.
But, the logical assertions define only the set of answers but not about how to choose
among those answers if there is more than one.
Consider the following example:
1. Logical representation
∀x : pet(x) ۸ small (x) → apartmentpet(x)
∀x : cat(x) ۸ dog(x) → pet(x)
∀x : poodle (x) → dog (x) ۸ small (x)
poodle (fluffy)
2. Prolog representation
apartmentpet (x) : pet(x), small (x)
pet (x): cat (x)
pet (x): dog(x)
dog(x): poodle (x)
small (x): poodle(x)
poodle (fluffy)
3. Forward Vs Backward reasoning
Forward versus Backward Reasoning
A search procedure must find a path between initial and goal states.
There are two directions in which a search process could proceed.
3
Representing Knowledge Using rules/AI
The two types of search are:
1. Forward search which starts from the start state
2. Backward search that starts from the goal state
The production system views the forward and backward as symmetric processes.
Consider a game of playing 8 puzzles. The rules defined are
Square 1 empty and square 2 contains tile n. →
o Also, Square 2 empty and square 1 contains the tile n.
Square 1 empty Square 4 contains tile n. →
o Also, Square 4 empty and Square 1 contains tile n.
We can solve the problem in 2 ways:
1. Reason forward from the initial state:
o Step 1. Begin building a tree of move sequences by starting with the initial
configuration at the root of the tree.
o Step 2. Generate the next level of the tree by finding all rules whose left-hand side
matches against the root node. The right-hand side is used to create new
configurations.
o Step 3. Generate the next level by considering the nodes in the previous level and
applying it to all rules whose left-hand side match.
2. Reasoning backward from the goal states:
o Step 1. Begin building a tree of move sequences by starting with the goal node
configuration at the root of the tree.
o Step 2. Generate the next level of the tree by finding all rules whose right-hand side
matches against the root node. The left-hand side used to create new configurations.
o Step 3. Generate the next level by considering the nodes in the previous level and
applying it to all rules whose right-hand side match.
o So, The same rules can use in both cases.
o Also, In forwarding reasoning, the left-hand sides of the rules matched against the
current state and right sides used to generate the new state.
o Moreover, In backward reasoning, the right-hand sides of the rules matched against
the current state and left sides are used to generate the new state.
4
Representing Knowledge Using rules/AI
There are four factors influencing the type of reasoning. They are,
1. Are there more possible start or goal state? We move from smaller set of sets to the
length.
2. In what direction is the branching factor greater? We proceed in the direction with
the lower branching factor.
3. Will the program be asked to justify its reasoning process to a user? If, so then it is
selected since it is very close to the way in which the user thinks.
4. What kind of event is going to trigger a problem-solving episode? If it is the arrival
of a new factor, the forward reasoning makes sense. If it is a query to which a
response is desired, backward reasoning is more natural.
Example 1 of Forward versus Backward Reasoning
It is easier to drive from an unfamiliar place from home, rather than from home to an
unfamiliar place. Also, If you consider a home as starting place an unfamiliar place as
a goal then we have to backtrack from unfamiliar place to home.
Example 2 of Forward versus Backward Reasoning
Consider a problem of symbolic integration. Moreover, The problem space is a set of
formulas, which contains integral expressions. Here START is equal to the given
formula with some integrals. GOAL is equivalent to the expression of the formula
without any integral. Here we start from the formula with some integrals and proceed
to an integral free expression rather than starting from an integral free expression.
Example 3 of Forward versus Backward Reasoning
The third factor is nothing but deciding whether the reasoning process can justify its
reasoning. If it justifies then it can apply. For example, doctors are usually unwilling
to accept any advice from diagnostics process because it cannot explain its reasoning.
Example 4 of Forward versus Backward Reasoning
Prolog is an example of backward chaining rule system. In Prolog rules restricted to
Horn clauses. This allows for rapid indexing because all the rules for deducing a
given fact share the same rule head. Rules matched with unification procedure.
Unification tries to find a set of bindings for variables to equate a sub-goal with the
head of some rule. Rules in the Prolog program matched in the order in which they
appear.
5
Representing Knowledge Using rules/AI
Combining Forward and Backward Reasoning
Instead of searching either forward or backward, you can search both simultaneously.
Also, That is, start forward from a starting state and backward from a goal state
simultaneously until the paths meet.
This strategy called Bi-directional search. The following figure shows the reason for a
Bidirectional search to be ineffective.
Forward versus Backward Reasoning
Also, The two searches may pass each other resulting in more work.
Based on the form of the rules one can decide whether the same rules can apply to
both forward and backward reasoning.
Moreover, If left-hand side and right of the rule contain pure assertions then the rule
can reverse.
And so the same rule can apply to both types of reasoning.
If the right side of the rule contains an arbitrary procedure then the rule cannot
reverse.
So, In this case, while writing the rule the commitment to a direction of reasoning
must make.
4. Matching
Conflict resolution
The result of the matching process is a list of rules whose antecedents
Preferences based on rules:
Specificity of rules
Physical order of ruIes
Preferences based on objects:
Importance of objects
Position of objects
6
Representing Knowledge Using rules/AI
Preferences based on action:
Evaluation of states
The individual preconditions of the rule can be
matched Son(x,y) A son(y,z) grandparent(x,z)
Can be matched, but not in a manner that satisfies the constraint imposed by the variable
y.
5. Control knowledge.
Knowledge about which paths are most likely to find the goal state is often called
search control knowledge
— Which states are more preferable to others.
— Knowledge about which rules to apply in a given situation.
— Knowledge about the order in which to pursue sub goals.
— Knowledge about useful sequence of rules to apply.
Search control knowledge = Meta knowledge
1. Long term memory Rules
2. Short erm memory Working memory