KNOWLEDGE
REPRESENTATION
Introduction
·
Most AI systems are made up of two basic parts: a
knowledge base and an inference mechanism (engine).
·
The knowledge base contains facts about objects in
the chosen domain and their relationships.
·
Most AI programs focus on a specific domain or
sphere of interest.
·
The knowledge base can also contain concepts,
theories, practical procedures, and their associations.
·
The knowledge base forms the system’s source of
intelligence and is used by the inference mechanism to reason and draw
conclusions.
·
The inference mechanism is a set of procedures that
are used to examine the knowledge base in an orderly manner to answer
questions, solve problems, or make decisions within the domain.
·
Much of the inference knowledge is generic and it
can be used to solve many different problems, especially if they have a similar
structure.
Knowledge Representation Methods
An Overview
o
Knowledge captured from experts and other sources
must be organized in such a fashion that a computer inferencing program will be
able to access this knowledge whenever needed and draw conclusions.
o
There are several methods of representing knowledge
in AI.
o
Many of these are pictorial representations.
o
Carrico et al. list seven benefits of pictorial
representations:
1. Validation through enhanced, uniform
communication between development team and users
2. Testing and debugging system logic because
of clean design and documentation
3. Completeness because methodologies encourage
complete documentation and quality assurance reviews with users
4. Accuracy of solutions because of documented
and tested logic
5. Ease of maintenance because reduced effort
is needed to understand and interpret someone else’s code
6. Programming productivity through enhanced,
uniform communication and documentation
7. Ease in coding system because of structured
approach
o
There are two general types of knowledge
representations: those that support analysis and those that are used in actual
coding.
o
Knowledge analysis techniques are usually used to
support knowledge acquisition during scope establishment and initial knowledge
gathering.
o
Most of these techniques are pictorial.
o
They help in the preliminary analysis of knowledge.
o
The knowledge, once organized, is ultimately coded
in one (or more) of the coding techniques.
o
Typical analysis techniques are semantic networks,
scripts, lists, decision tress, and decision tables.
o
The working code of a knowledge-based system is
usually represented either in the form of production rules or as frames.
o
A frame represents all relevant knowledge about a
particular object in one data structure.
o
Knowledge recorded in any of the analysis techniques
can be easily translated into rules or frames.
o
For example, there are software tools that
assimilate decision tables to rules or convert decision trees to rules.
Semantic Networks
·
One of the oldest and easiest-to-understand
knowledge representation schemes is the semantic network, or semantic net,
which is composed of nodes and links.
·
Semantic networks are basically graphic depictions
of knowledge that show hierarchical relationships between objects.
·
A simple semantic network is shown in the following
figure:
Representation of Knowledge in a
Semantic Network
·
It is made up of a number of circles, or nodes,
which represent objects and descriptive information about those objects.
·
Objects can be any physical item such as a book,
car, desk, or even a person.
·
Nodes can also be concepts, events, or actions.
·
A concept might be Ohm’s Law, an event such as a
picnic or an election, or an action such as building a house or writing a book.
·
Attributes of an object can also be used as nodes.
·
These might represent size, color, class, age,
origin, or other characteristics.
·
In this way, detailed information about objects can
be presented.
·
The nodes in a semantic network are also interconnected
by links, or arcs.
·
These arcs show the relationships between the
various objects and descriptive factors.
·
Some of the most common arcs are of the is-a or
has-a type.
·
Is-a, usually just designated as isa, is used to
show class relationship, that is, that an object belongs to a larger class or
category of objects.
·
Has-a links are used to identify characteristics or
attributes of the object nodes.
·
Other arcs are used for definitional purposes.
·
Now refer to the example in the above figure.
·
As you can see, the central figure in the domain of
knowledge is a person called Sam.
·
One link shows that Sam is a man and that man is a
human being or is part of a class called humans.
·
Another arc from Sam shows that he is married to
Kay.
·
Additional arcs show that Kay is a woman and that a
woman is, in turn, a human being.
·
Other links show that they have a child, Joe, who is
a boy and goes to school.
·
Some nodes and arcs show other characteristics about
Sam.
·
For example, he is a vice president for Acme, a
company that is a subsidiary of Ajax, a large corporation.
·
We also see that Sam plays golf, which is a sport.
·
Further, Sam owns a Mercedes Benz whose color is
silver.
·
We also see that Mercedes Benz is a type of car that
is made in Germany.
·
One of the most interesting and useful facts about a
semantic network is that it can show inheritance.
·
Since the semantic network is basically a hierarchy,
the various characteristics of some nodes actually inherit the characteristics
of others.
·
As an example, consider the links showing that Sam
is a man and a man is, in turn, a human being.
·
Here, Sam inherits the property of human being.
·
We can ask the question, "Does Sam need
food?"
·
Because of the inheritance links, we can say that he
needs food if human beings need food.
·
Another example of inheritance is the relationship
between Acme for whom Sam works and its parent corporation, Ajax.
·
Again we can ask the question, "Does Sam work
for the Ajax Corporation?"
·
The answer is yes, because Ajax owns Acme.
·
This inheritance characteristic of semantic networks
makes it possible to make a variety of deductions from the information
provided.
·
The amount of detail that you include in a semantic
network depends on the kinds of problems that must be solved.
·
If the problems are general, less detail is
required.
·
If the problems involve a lot of nitty-gritty, more
explanation must be given in the original network.
·
For example, the link showing that Sam owns a car
might be expanded to show that he owns many other things.
·
Following figure illustrates the idea:
Addition of Detail to a Semantic
Network
·
Here, Sam is linked to a new node called
"owns."
·
Another example involves the attributes of various
objects in the network.
·
For example, suppose that we want to show the ages
of Sam and Kay.
·
This could be done by the network shown in the
following figure:
Expansion of the Knowledge in a
Semantic Network
·
The ages are given as numeric values in related
nodes.
·
A more flexible way of representing this information
is given in the following figure:
Expansion of the Knowledge in a
Semantic Network
·
Here, we assign both Sam and Kay an age node.
·
The age node, in turn, is given the actual value.
·
This representation is much better because a factor
such as age will change.
·
Furthermore, we can show the relationship between
ages better in this format.
·
The "greater than" link accomplishes that.
·
Although the semantic network is graphic in nature,
it does not appear this way in a computer.
·
Instead, the various objects and their relationships
are stated in verbal items, and these are programmed into the computer using
one of several different kinds of languages.
·
Searching semantic networks (especially large ones)
may be difficult.
·
Therefore, the technique is used mainly for analysis
purposes.
·
Then, a transformation to rules or frames is
executed.
·
Semantic nets are used basically as a visual
representation of relationships, and they can be combined with other
representation methods.
Scripts
·
A script is a knowledge representation scheme
similar to a frame, but instead of describing an object, the script describes a
sequence of events.
·
Like the frame, the script portrays a stereotyped
situation.
·
Unlike the frame, it is usually presented in a
particular context.
·
To describe a sequence of events, the script uses a
series of slots containing information about the people, objects, and actions
that are involved in the events.
·
Some of the elements of a typical script include
entry conditions, props, roles, tracks, and scenes.
·
The entry conditions describe situations that must
be satisfied before events in this script can occur or be valid.
·
Props refer to objects that are used in the sequence
of events that occur.
·
Roles refer to the people involved in the script.
·
The result is conditions that exist after the events
in the script have occurred.
·
Track refers to variations that might occur in a
particular script.
·
And finally, scenes describe the actual sequence of
events that occur.
·
A typical script is shown in the following figure:
Typical Script
·
It is a variation of the well-known restaurant
example that has been used in AI to show how knowledge is represented in script
format.
·
Going to a restaurant is a stereotyped situation
with predictable entry conditions, props, roles, and scenes.
·
As you can see, such a script accurately describes
what occurs in almost every fast-food restaurant situation.
·
The scenes are miniscripts within the main script
that describes the various subdivisions of the entire process.
·
Note the optional scene that describes a take-out
situation rather than an eat-in situation.
·
Another option may be a drive-through scene.
·
Finally, note the results.
·
A script is useful in predicting what will happen in
a specific situation.
·
Even though certain events have not been observed,
the script permits the computer to predict what will happen to whom and when.
·
If the computer triggers a script, questions can be
asked and accurate answers derived with little or no original input knowledge.
·
Like frames, scripts are a particularly useful form
of knowledge representation because there are so many stereotypical situations
and events that people use every day.
·
Knowledge like this is generally taken for granted,
but in computer problem-solving situations, such knowledge must often be
simulated to solve a particular problem using AI.
·
To use the script, you store knowledge in the
computer in symbolic form.
·
This is best done using LISP or another symbolic
language.
·
You can then ask questions about various persons and
conditions.
·
A search and pattern-matching process examines the
script for the answers.
·
For example, what does the customer do first?
·
Well, he parks the car, then goes into the restaurant.
·
Whom does he pay?
·
The server, of course.
·
The whole thing is totally predictable.
·
Script representation is interrelated with
case-based reasoning.
Objects, Attributes, and Values
·
A common way to represent knowledge is to use objects,
attributes, and values, the O-A-V triplet.
·
Objects may be physical or conceptual.
·
Attributes are the characteristics of the objects.
·
Values are the specific measures of the attributes
in a given situation.
·
The following table presents several O-A-V triplets:
Representative O-A-V Items
·
An object may have several attributes.
·
An attribute itself may be considered as a new
object with its own attributes.
·
For example, in the above table a bedroom is an
attribute of a house but also an object of its own.
·
O-A-V triplets are used both in frame and semantic
network representations.
·
The O-A-V triplet can be viewed as a variation of
either frames or semantic networks.
·
For example, the representation in the figure of
semantic network includes a segment which is shown in the following figure:
O-A-V Triplet Representation
·
We added to this segment the O-A-V triplet.
·
Thus, objects and values are designated as nodes,
while attributes are designated as arcs.
·
The O-A-V triplet can be used in both static and
dynamic presentations (in dynamic presentations the object value portions can
change).
·
O-A-V triplets can be used to show order and
relationships by using a tree structure.
·
For example, they can show inheritance, casual
relationships, or part-to-subpart links.
Lists and Trees
·
Lists and trees are simple structures used for
representing hierarchical knowledge.
Lists
o
A list is a written series of related items.
o
It can be a list of names of people you know, things
to buy at the grocery store, things to do this week, or products in a catalog.
o
Lists are normally used to represent knowledge in
which objects are grouped, categorized, or graded according to rank or
relationship.
o
Objects are first divided into groups or classes of
similar items.
o
Then, their relationships are shown by linking them
together.
o
The simplest form is one list, but a hierarchy is
created when two or more related lists are combined.
o
The following figure shows a generalized format for
a list:
Lists Representing Hierarchical
Knowledge
o
The list has a name to identify it (List A) and two
or more elements.
o
You can see that an element in one list can be the
name of another list containing subelements.
o
One or more of the subelements can, in turn, be the
name of another list and so on.
o
Another way to look at related lists is as an
outline.
o
An outline is nothing more than a hierarchical
summary of some subject.
o
The various segments of the outline are lists.
Decision Tables
o
Another method of knowledge representation is the
decision table, which is organized in a spreadsheet format, using columns and
rows.
o
The table is divided into two parts.
o
First, a list of attributes is developed, ands for
each attribute all possible values are listed.
o
Then, a list of conclusions is developed.
o
Finally, the different configurations of attributes
are matched against the conclusion.
o
A simple example is shown in the following figure:
Decision Table Based on Dialogue
with a Fruit Expert
o
Knowledge for the table is collected in knowledge acquisition
sessions.
o
Once constructed, the knowledge in the table can be
used as input to other knowledge representation methods.
o
It is not possible to make inferences with the
domain tables by themselves, except when rule induction is used.
o
Decision tables are easy to understand and program.
Decision Trees
o
Decision trees are related to tables and are used
frequently in system analysis (in non-AI systems).
o
According to Carrico et al., a decision tree may be
thought of as a hierarchical semantic network bound by a series of rules.
o
It couples search strategy with knowledge
relationships.
o
The trees are similar to the decision trees used in
decision theory.
o
They are composed of nodes representing goals and
links representing decisions.
o
The root of the tree is on the left and the leaves
are on the right.
o
All terminal nodes except the root node are
instances of a primary goal.
o
Decision trees, like rules, depict a strong sense of
cause and effect.
o
Their major advantage is that they can simplify the
knowledge acquisition process.
o
Knowledge diagramming is frequently more natural to
experts than formal representation methods (such as rules or frames).
o
Decision trees can easily be converted to rules.
o
The conversion can be executed by a computer
program.
o
The equivalence of a simple decision tree and a rule
is shown in the following figure:
Decision Tree for Fruit
Identification
o
The problem depicted is fruit identification.
o
Using heuristics, one starts by smelling the fruit;
if it smells acidy then the fruit is known to be a citrus.
o
A round shape will narrow the search to either an
orange or grapefruit, etc.
o
There are several variations of decision trees.
o
For example, the lists shown earlier can be shown as
trees.
o
Following figure represents the same knowledge shown
in the figure of lists (nodes correspond to list names and arcs show the relationships).
Tree Graph for Illustrating
Hierarchical Knowledge
o
Lists, and trees, are so commonly used to represent knowledge
that you will deal with them regularly in virtually every area of AI.
o
In fact, lists are so widely used that a special
programming language has been created to deal with them.
o
It is called LISP, for list processing.
o
LISP is a main programming language for AI work.
Frames
Definitions and
Overview
o
A frame is a data structure that includes all the
knowledge about a particular object.
o
This knowledge is organized in a special
hierarchical structure that permits a diagnosis of knowledge independence.
o
Frames are basically an application of
object-oriented programming for AI and ES.
o
Each frame describes one object.
o
To describe what frames are and how the knowledge is
organized in a frame we need to use a special terminology, which is presented
in the following table:
Terminology for Frames
o
Frames, as in frames of reference, provide a
concise, structural representation of knowledge in a natural manner.
o
In contrast to other representation methods, the
values that describe one object are grouped together into a single unit called
a frame.
o
Thus, a frame encompasses complex objects, entire
situations, or a management problem as a single entity.
o
The knowledge is partitioned in a frame into slots.
o
A slot can describe declarative knowledge (such as
the color of a car) or procedural knowledge (such as "activate a certain
rule if a value exceeds a given level").
o
The major capabilities of frames are summarized in
the following table:
Capabilities of Frames
o
A frame is a relatively large block or chunk of
knowledge about a particular object, event, location, situation, or other
element.
o
The frame describes that object in great detail.
o
The detail is given in the form of slots which
describes the various attributes and characteristics of the object or
situation.
o
Frames are normally used to represent stereotyped
knowledge or knowledge built on well-known characteristics and experiences.
o
We all have a great deal of commonsense knowledge
and experiences stored away in our brains that we call on to analyze a new object
or experience to solve a problem.
o
Frames can be used to represent that kind of
knowledge.
o
A frame provides a means of organizing knowledge in
slots that contain characteristics and attributes.
o
In physical form, a frame is somewhat like an
outline with categories and subcategories.
o
A typical frame describing an automobile is shown in
the following figure:
Frame Describing an Automobile
o
Note the slots describing attributes such as name of
manufacturer, model, origin of manufacturer, type of car, number of doors,
engine, and other characteristics.
Content of a Frame
o
A frame includes two basic elements: slots and
facets.
o
A slot is a set of attributes that describe the
object represented by the frame.
o
For example, in the automobile frame, there are
weight and engine slots.
o
Each slot contains one or more facets.
o
The facets (sometimes called subslots) describe some
knowledge or procedures about the attribute in the slot.
o
Facets may take many forms:
Values
o
These describe the attributes such as blue, red, and
yellow for a color slot.
Default
o
This facet is used if the slot is empty, that is,
without any description.
o
For example, in the car frame one default value is
that the number of wheels on the car is four.
o
It means that we can assume the car has four wheels
unless otherwise indicated.
Range
o
Range indicates what kind of information can appear
in a slot (e.g., integer numbers only, two decimal points, 0 to 100).
If Added
o
This facet contains procedural information or
attachments.
o
It specifies an action to be taken when a value in
the slot is added (or modified).
o
Such procedural attachments are called demons.
If Needed
o
This facet is used in a case when no slot value is
given.
o
It triggers, much like the if-added situation, a
procedure that goes out and gets or computes a value.
Other
o
Slots may contain frames, rules, semantic networks,
or any type of information.
o
Certain procedures can be attached to slots and used
to derive slot values.
o
For example, slot-specific heuristics are procedures
for deriving slot values in a particular context.
o
An important aspect of such procedures is that they
can be used to direct the reasoning process.
o
In addition to filling in slots, they can be
triggered when a slot is filled.
o
In the above figure, both acceleration and gas
mileage are procedural attachments.
o
They refer to a step-by-step procedure that would
define how to acquire this information.
o
For example, to determine acceleration, timing runs
for both 0 to 60 mph and quarter-mile elapsed time and speed would be
described.
o
A procedural attachment to determine gas mileage
would state a procedure for filling the gas tank, driving a certain number of
miles, determining the amount of gasoline used, and then computing the gas
mileage in terms of miles per gallon.
Hierarchy of Frames
o
Most AI systems use a collection of frames that are
linked together in a certain manner.
o
These relationships create a hierarchy of frames.
o
The hierarchy is not necessarily on a one-to-one
basis.
Inheritance
o
The hierarchical arrangement of frames permits
inheritance.
o
Following figure show a set of vehicles that are
organized in a tree:
Hierarchy of Frames Describing
Vehicles
o
The root of the tree is at the top, where the
highest level of abstraction is represented.
o
Frames at the bottom are called leaves of the tree.
o
The hierarchy permits inheritance of
characteristics.
o
Each frame usually inherits the characteristics of
all related frames of higher levels.
o
These characteristics are expressed in the internal
structure of the frame.
o
Parent frames provide a more general description of
the entities.
o
The higher one is in the hierarchy, the more general
is the description.
o
Parent frames contain the attribute definitions.
o
When we describe actual, physical objects, we
instantiate the child’s frame.
o
The instances (child frames) contain actual values
of the attributes.
o
An example is shown in the following figure:
Parent and Child Frames
o
Note that every parent is a child of a higher-level
parent.
o
In building a frame it is possible to have a frame
where different slots are related to different parents.
o
The only frame without a parent is the one at the
top of the hierarchy.
o
This frame is called a master frame.
o
It is the root frame and it has the most general
characteristics.
Using Frames
o
A frame representation is based on the theory that
previous situational experiences create certain expectations about objects and
events associated with new situations.
o
Frames provide frameworks within which new
information can be interpreted.
o
For example, based on previous experience, a chair
is generally expected to be a kind of furniture with arms, legs, and a back.
o
Expectations represent things that are always true
about chairs and provide the context within which other objects can be
interpreted.
o
These expectations are represented as slots.
o
Obviously, before a frame can be used it must be
identified as applicable to the current situation.
o
Generally speaking, this can be done by matching the
frame system against the facts in the knowledge base.
o
The selected frame will be the one with the greatest
number of lower-level slots filled in.
o
Then, an attempt is made to fill in higher-level
slots and if this fails, another frame is selected.
o
For example, a "room" with very short
walls and no windows or artificial light might better fit the
"closet" frame than a "room" frame.
o
To use the frame system, the frame itself is programmed
using an AI programming language.
o
A slot hierarchy is set up, say using the LISP
language, then addressed to derive the answer to a question.
o
Special frame-based software development tools are
also available.
o
A tool is a program that helps a user create another
program.
o
Tools require no programming skill as they provide a
preestablished format of slots that simply permit you to enter the various
characteristics.
o
Once the frames are stored in memory, various search
and pattern-matching techniques are invoked to answer questions or otherwise
make deductions from the knowledge available.
o
The use of frame-based tools to build expert systems
is demonstrated in Level 5 Object.
Multiple Knowledge Representation
·
Knowledge representation should be able to support
the tasks of acquiring and retrieving knowledge as well as subsequent
reasoning.
·
Several factors must be taken into account in
evaluating knowledge representations for these three tasks:
Naturalness, uniformity, and understandability of the
representation
Degree to which knowledge is explicit (declarative) or
embedded in procedural code
Modularity and flexibility of the knowledge base
Efficiency of knowledge retrieval and the heuristic
power of the inference procedure (Heuristic power is the reduction of the
search space achieved by a heuristic mechanism.)
·
No single knowledge representation method is ideally
suited by itself for all tasks.
·
When using several sources of knowledge simultaneously,
the goal of uniformity may have to be sacrificed in favor of exploiting the
benefits of multiple knowledge representations, each tailored to a different
subtask.
·
The necessity of translating among knowledge
representations becomes a problem in such cases.
·
Nevertheless, some recent ES shells use two or more
knowledge representation schemes.
·
A rather successful combination of knowledge
representation methods is that of production rules and frames.
·
By themselves, production rules do not provide a totally
effective representation facility for many ES applications.
·
In particular, their expressive power is inadequate
for defining terms and for describing domain objects and static relationships
among objects.
·
The major inadequacies of production rules are in
areas that are effectively handled by frames.
·
A great deal of success, in fact, has been achieved
by integrating frame and production-rule languages to form hybrid
representation facilities that combine the advantages of both components.
·
Systems such as KEE, Level 5 Object, and Nexpert
Object have shown how a frame language can serve as powerful foundation for a
rule language.
·
The frames provide a rich structural language for
describing the objects referred to in the rules and a supporting layer of generic
deductive capability about those objects that does not need to be explicitly
dealt with in the rules.
·
Frame taxonomies can also be used to partition,
index, and organize a system’s production rules.
·
This capability makes it easier for the domain expert
to construct and understand rules, and for the system designer to control when
and for what purpose particular collections of rules are used by the system.
·
An example of combining rule-based representation
and frame representation is given by Harmon.
·
As shown in the following figure, the integration
allows the creation of pattern-matching rules that can increase the speed of
search.
Two Basic Techniques in
Knowledge-based System Development and the Programming Techniques that Emerged
from the Combination of the Technologies
·
The integration allows much more complex
representation that can be made when pure frames are used, even when tools such
as C++ are utilized.
·
More recently, knowledge representation researchers
have become increasingly concerned with the need to formally understand the
representational adequacy of various knowledge representation schemes.
·
When various knowledge representations are
"recast" in terms of logic, they can be compared and the strengths
and weaknesses of logic for knowledge representations can be better understood.
·
These investigations have already led to a better
understanding of knowledge representation and to the development of logic than
can handle incompleteness and default reasoning.
