2.

Semantic Networks
A semantic network represents knowledge in the form of a graph in which the nodes represent
objects, situations, or events, and the arcs represent the relationships between them.
Note: Labels on the arcs specify what type of relationship exists

Nodes and Arcs

Arcs define binary relationship that hold between objects denoted by the nodes

Example 1 (binary relations)

Represent the following sentences into a semantic network
1. Marcus was a man
2. Marcus was a Pompeian
3. All Pompeians were Romans
4. Caesar was a ruler
8. Marcus tried to assasinate Caesar
9. All men are persons
10. The height of Marcus was 72
Solution
Roman person

isa isa

Pompeian man
ruler
instance-of instance-of
instance-of
height tryassassinate
72 Marcus Caesar

Relationships
The most important relations between concepts are:
• Subclass – between classes i.e. The relationship "isa" asserts that a class, ("man"), is a
subclass of another class ("person") (Denotes inheritance).

• Instance – between a particular object (Marcus, Caesar) and its parent class i.e. the
relationship "instance-of" asserts that an individual is an instance (element) of a class.

Types of Nodes
• Generic node: This refers to a general node. e.g. Roman, Pompeian, etc
• Individual Nodes / Instance Nodes: This are nodes that explicitly state that they are
specific instances of a generic node

Wainaina ~ KBS Page 1 of 9

Example 2
The following is a semantic network representing knowledge about the solar system.
yellow

color

mass Sun temperature

MSun TSun

attracts
greater-than greater-than
revolves-
arround

3500 value MEarth TEarth

mass Earth temperature

Multiple inheritance
It is possible for a concept to have more than one parent. This enables to inherit properties from
multiple parents’ nodes and their ancestors in the network.

Default inheritance
There are some domains of knowledge in which exceptions to general rules exist. E.g. it is
usually useful to assume that all birds can fly. However certain birds such as the ostrich and the
kiwi cannot fly.
In such a case, it is reasonable to use a representation scheme in which properties associated with
concepts in a hierarchy are assumed to be true of all subclasses, unless specifically overridden by
a denial or modification associated with the subclass.
Example
In the figure below the fact that a woodpecker flies is inherited from bird. On the other hand, the
ostrich does not inherit this property from bird because it is explicitly represented that the ostrich
does not fly. This overrides the default which is further up in the tree.

animal

fly
mammal bird true

fly false
woodpecker wren ostrich

Wainaina ~ KBS Page 2 of 9

Reasoning in Semantic Network
Reasoning using semantic network involves specifying the start node. From the initial node other
nodes are pursued using the links until the final node is reached. This type of arriving at results
by matching nodes and arcs and utilization of inheritance property helps to great extent in
reasoning process.

Exercises
1. Represent the following sentences into a semantic network.
Birds are animals.
Birds have feathers, fly and lay eggs.
Albatros is a bird.
Donald is a bird.
Tracy is an albatros.

2. Represent the following sentences into a semantic network:

Palco is a calico.
Herb is a tuna.
Charlie is a tuna.
All tunas are fishes.
All calicos are cats.
All cats like to eat all kinds of fishes.
3. Represent the following sentences into a semantic network:
Circus elephants are elephants
Elephants have head
Elephants have trunks
Heads have mouths
Elephants are animals
Animals have hearts
Circus elephants are performers
Performers have costumes
Costumes are cloths
Horatio is a circus elephant

3. Frames
It refers to a knowledge representation in which all relevant information about a particular a
particular concept is stored in a single complex entity called a frame.
Basically, frames are variants of semantic networks and they also support inheritance.
.

Wainaina ~ KBS Page 3 of 9

Example Frame representation

Objects Mammal:
Slots Subclass: Animal
Has_part: head
Elephant:
Subclass: Mammal
Color: grey Slot values
Size: large (facets)
Nellie:
Instance: Elephant
Likes: apple

Relation with OO Programming

• Terms and ideas (e.g. class and inheritance) used for frames had been adopted in object
oriented programming.
• OO languages were influenced by frame systems.
• OO manipulate specific ‘object’ in well-defined ways;
• Frames represent knowledge about conceptual categories.

Relationship between Semantic Nets and Frames

Semantic Networks Frames

Nodes Objects
Slots Links
Node at the other end of the link Slot value

Example
Animals eat, breath and have skin. Birds are special kind of animal which have
wings, feathers and normally can fly. Crows are black and can fly. Penguins are
black and white and ostriches are brown. Penguins and ostriches are birds but
they cannot fly. Tom, a human being, owns a pet crow called ‘black-head’.

Animals:
can_eat: true
can_breath: true
have_skin: true
Birds:
sub_class: Animals
have_wings: true
have_feathers: true
* can_fly: true
Crows:
sub_class: Birds
colour: black

Wainaina ~ KBS Page 4 of 9

Penguins:
sub_class: Birds
colour: black_and_white
can_fly: false
Ostriches:
sub_class: Birds
can_fly: false
black-head:
instance: Crows
owned_by: tom
tom:
instance: human_being
owns: black_head
black_head:
instance: crow

4. Production systems
A production system is used to represent knowledge in the form of condition-action pairs called
production rules.

General format
If the condition C is satisfied, then the action A is appropriate

Example
i) If it is raining, then you should open the umbrella.
ii) IF the ‘traffic light’ is green
THEN the action is go
IF the ‘traffic light’ is red
THEN the action is stop

The action will be carried out if the condition is true and the condition and action can both be
composed of several parts.

A Typical Rule(A rule from the MYCIN expert system)

IF the strain of the organism is gramneg
AND the morphology of the organism is rod
AND the aerobicity of the organism is aerobic
THEN there is strong suggestive evidence that the class of the organism is
enterobacteriaceae

Architecture of a Production System

A production system consists of three parts:

a) A short-term memory of facts.

Wainaina ~ KBS Page 5 of 9

b) A rule base composed of a set of production rules of the form "antecedent -->
consequent". The antecedents comprise conditions that characterize the short-term
memory and the consequents comprise actions that manipulate the short-term memory. If
the antecedent of a production rule is satisfied by the short-term memory then the
production may be executed (fired). The consequent of the production rule will change
the content of the short-term memory so that other rules will have their conditions
satisfied.
c) An interpreter that represents a mechanism to examine the short-term memory and to
determine which rules to fire.

The following diagram represents the architecture of a production system.

Interpreter

condition 1 action 1
condition 2 action 2 Short
. . Term
. .
. . Memory
condition n action n
Rule Base

Types of production rules:

i). Situation-action rules: - The antecedent is a logical combination of assertions about
the data in the short-term memory and the consequent is a collection of actions that
change the memory.

ii). Inference rules: - Both the antecedents and the consequents are assertions about the
data in the short-term memory.

The production systems based on situation-action rules can be run only in forward chaining and
are therefore called antecedent-driven systems.
The production systems based on inference rules may be run in either forward chaining or
backward chaining, since both sides of a production consist of the same constructs.

Note
i) Goal driven reasoning or backward chaining – an inference technique which uses IF
THEN rules to repetitively break a goal into smaller sub-goals, which are easier to prove;

ii) Data driven reasoning or forward chaining – an inference technique that uses IF THEN
rules to deduce a problem solution from initial data;

Wainaina ~ KBS Page 6 of 9

Execution in a Production System
The execution of a production system can be defined as a series of recognize-act cycles. It
involves the following:
i) Match: - determines the rules that can be fired. The set of rules that can be fired is called
the conflict set.
ii) Conflict resolution:- It involves selecting one rule from the conflict set
iii) Apply the rule:- A rule is executed (fired). Since the effect of executing the actions may
change the short-term memory, different rules may fire on successive cycles.

Conflict Resolution Strategies:

Several strategies may be used to choose the rule to fire from the conflict set:
1. Rule order: -The first encountered rule that matches the short-term memory.
2. Priority: - The highest priority rule (assuming that each rule has an associated priority).
3. Specificity: - The most specific rule, that is, the one with the most detailed condition part
that matches the current short term memory.
4. Recent: - The rule that refers to the element most recently added to the short-term memory.
5. New rule: - Occurs in a rule-binding instantiation for a rule that has not occurred previously;

Note
A rule that would not modify the content of the short-term memory should not be fired (e.g. a
rule that would infer a fact that is already in the short term memory).

Exercises
Consider the following a production system characterized by
- Initial short term memory: C5, C1, C3
- Production rules: C1 & C2 --> C4
C3 --> C2
C1 & C3 --> C6
C4 --> C6
C5 --> C1

Show a possible sequence of two recognize-act cycles. Which will be the new content of the
short-term memory after these two cycles ?

Solution
1. Match: determines the rules that can be fired
C3 --> C2
C1 & C3 --> C6 conflict set.
C5 --> C1

2. Conflict resolution: select one rule from the conflict set (use rule order)
C3 --> C2
3. Apply the rule:
- new short term memory: C5, C1, C3, C2

Wainaina ~ KBS Page 7 of 9

1. Match: determines the rules that can be fired
C1 & C2 --> C4
C3 --> C2
C1 & C3 --> C6
C5 --> C1
2. Conflict resolution: select one rule from the conflict set
C1 & C2 --> C4
3. Apply the rule:
- new short term memory: C5, C1, C3, C2, C4

Exercise
Suppose that you decide to develop a rule-based system to help someone to choose elective
courses. Accordingly, you create rules that award points to various courses. The course with the
highest number of points becomes the first choice. Here is a sample rule:

R1: If subject of x is interesting

then add 10 points to x

Create five other rules that reflect your own taste.

Choosing a Representation Schema:

When evaluating knowledge representation alternatives one should consider:
• The naturalness, uniformity and understanding of the representation
• The degree to which knowledge is explicit or embedded in procedural code
• The modularity and flexibility of knowledge base
• The efficiency of knowledge retrieval and the heuristic power of inference procedure

Other Knowledge Representation Schemes

− Scripts
− Lists
− Decision tables
− Decision trees
− Object attribute value(OAV) triplet

Hybrid Representation
• No single representation will be suitable for representing every problem domain i.e. every
representation schema has its own advantages and disadvantages. Therefore a hybrid
representation schema may be better than any single schema.
• A.I. programming tools containing rules, frames and logic are now available

Wainaina ~ KBS Page 8 of 9

Comparison of the Various Knowledge Schemes

Scheme Advantages Disadvantages

1 Formal Logic • Facts asserted independent of use
• Separation of processing
• Assurance that only valid • Inefficient with large datasets
consequences are asserted • Very slow with large
• completeness knowledge bases
2 Production • Simple syntax • Hard to follow hierarchy
Rules • Easy to understand • Inefficient for large systems
• Simple interpreter • Not all knowledge can be
• Highly modular expressed as rules
• Flexible (i.e. easy to add or • Poor at representing structure
modify) descriptive knowledge
3 Semantic • Easy to follow hierarchy • Meaning attached to nodes
Networks • Easy to trace association may be ambiguous
• Flexible • Exception handling is difficult
• It is difficult to program
4 Frames • Expressive power • Difficult to program
• Easy to set up slots from new • Difficult to inference
properties and relations
• Easy to include default
information and detect missing
values

Wainaina ~ KBS Page 9 of 9