FOAI Unit-3 4350704

Unit-3 Knowledge Representation

 Knowledge Representation (What is Knowledge Representation?)

 Knowledge Representation in AI describes the representation of knowledge. Basically, it is a

study of how the beliefs, intentions, and judgments of an intelligent agent can be expressed
suitably for automated reasoning. One of the primary purposes of Knowledge Representation
includes modeling intelligent behavior for an agent.

 Knowledge Representation and Reasoning (KR, KRR) represents information from the real
world for a computer to understand and then utilize this knowledge to solve complex real-life
problems like communicating with human beings in natural language. Knowledge
representation in AI is not just about storing data in a database, it allows a machine to learn
from that knowledge and behave intelligently like a human being.

 The different kinds of knowledge that need to be represented in AI include:

o Object: All the facts about objects in our world domain. E.g., Guitars contains
strings, trumpets are brass instruments.

o Events: Events are the actions which occur in our world.

o Performance: It describes behavior which involves knowledge about how to do
things.

o Meta-knowledge: It is knowledge about what we know.

o Facts: Facts are the truths about the real world and what we represent.

o Knowledge-Base: The central component of the knowledge-based agents is the

knowledge base. It is represented as KB. The Knowledgebase is a group of the
Sentences (Here, sentences are used as a technical term and not identical with the
English language)

SPR 1
 FOAI Unit-3 4350704

What do you mean by Knowledge?

 Knowledge is awareness or familiarity gained by experiences of facts, data, and

situations. Following are the types of knowledge in artificial intelligence:

 Types of knowledge

 There are 5 types of Knowledge such as:

 Declarative Knowledge:

o Declarative knowledge is to know about something.

o It includes concepts, facts, and objects.

o It is also called descriptive knowledge and expressed in declarative sentences.

o It is simpler than procedural language.

 Procedural Knowledge

o It is also known as imperative knowledge.

o Procedural knowledge is a type of knowledge which is responsible for knowing

how to do something.

SPR 2
 FOAI Unit-3 4350704

o It can be directly applied to any task.

o It includes rules, strategies, procedures, agendas, etc.

o Procedural knowledge depends on the task on which it can be applied.

 Meta-knowledge:

o Knowledge about the other types of knowledge is called Meta-knowledge.

 Heuristic knowledge:

o Heuristic knowledge is representing knowledge of some experts in a filed or

subject.

o Heuristic knowledge is rules of thumb based on previous experiences, awareness

of approaches, and which are good to work but not guaranteed.

 Structural knowledge:

o Structural knowledge is basic knowledge to problem-solving.

o It describes relationships between various concepts such as kind of, part of, and
grouping of something.

o It describes the relationship that exists between concepts or objects.

What is the relation between knowledge and intelligence?

 Knowledge of real-worlds plays a vital role in intelligence and same for creating artificial
intelligence. Knowledge plays an important role in demonstrating intelligent behavior in AI
agents. An agent is only able to accurately act on some input when he has some knowledge or
experience about that input.

 Let's suppose if you met some person who is speaking in a language which you don't know,
then how you will able to act on that. The same thing applies to the intelligent behavior of the
agents.

SPR 3
 FOAI Unit-3 4350704

 As we can see in above diagram, there is one decision maker which act by sensing the
environment and using knowledge. But if the knowledge part will not present then, it cannot
display intelligent behavior.

 AI knowledge cycle:

 An Artificial intelligence system has the following components for displaying intelligent
behavior:

o Perception

o Learning
o Knowledge Representation and Reasoning

o Planning

o Execution

SPR 4
 FOAI Unit-3 4350704

 The above diagram is showing how an AI system can interact with the real world and what
components help it to show intelligence. AI system has Perception component by which it
retrieves information from its environment. It can be visual, audio or another form of sensory
input.

 The learning component is responsible for learning from data captured by Perception
comportment. In the complete cycle, the main components are knowledge representation and
Reasoning. These two components are involved in showing the intelligence in machine-like
humans. These two components are independent with each other but also coupled together. The
planning and execution depend on analysis of Knowledge representation and reasoning.

 Approaches to knowledge representation:

 There are mainly four approaches to knowledge representation, which are given below:
 1. Simple relational knowledge:

 It is the simplest way of storing facts which uses the relational method, and each fact
about a set of the object is set out systematically in columns.

 This approach of knowledge representation is famous in database systems where the

relationship between different entities is represented.

 This approach has little opportunity for inference.

 Example: The following is the simple relational knowledge representation.

SPR 5
 FOAI Unit-3 4350704

Player Weight Age

Player1 65 23
Player2 58 18
Player3 75 24

Inheritable knowledge:

 In the inheritable knowledge approach, all data must be stored into a hierarchy of classes.

 All classes should be arranged in a generalized form or a hierarchal manner.

 In this approach, we apply inheritance property.

 Elements inherit values from other members of a class.

 This approach contains inheritable knowledge which shows a relation between instance and
class, and it is called instance relation.

 Every individual frame can represent the collection of attributes and its value.

 In this approach, objects and values are represented in Boxed nodes.

 We use Arrows which point from objects to their values.

 Example:

SPR 6
 FOAI Unit-3 4350704

Inferential knowledge:

 Inferential knowledge approach represents knowledge in the form of formal logics.

 This approach can be used to derive more facts.

 It guaranteed correctness.

 Example: Let's suppose there are two statements:

 Marcus is a man

 All men are mortal

 Then it can represent as;

man(Marcus)

∀x = man (x) ---------- > mortal (x)s

SPR 7
 FOAI Unit-3 4350704

4. Procedural knowledge:
 Procedural knowledge approach uses small programs and codes which describes how to do
specific things, and how to proceed.

 In this approach, one important rule is used which is If-Then rule.

 In this knowledge, we can use various coding languages such as LISP language and
Prolog language.

 We can easily represent heuristic or domain-specific knowledge using this approach.

 But it is not necessary that we can represent all cases in this approach.

Issues in Knowledge Representation

 The issues that arise while using KR techniques are many. Some of these are explained
below.

 Important Attributes:

 Any attribute of objects so basic that they occur in almost every problem domain.

 There are two attributed “instance” and “isa”, that are general significance. These
attributes are important because they support property inheritance.

 Relationship among attributes:

 Any important relationship that exists among object attributes.

 The attributes we use to describe objects are themselves entities that we represent.

 The relationship between the attributes of an object, independent of specific knowledge they
encode, may hold properties like:

o Inverse — This is about consistency check, while a value is added to one

attribute. The entities are related to each other in many different ways.
o Existence in an isa hierarchy — This is about generalization-specification, like,

SPR 8
FOAI Unit-3 4350704

classes of objects and specialized subsets of those classes, there are attributes and
specialization of attributes. For example, the attribute height is a specialization of general
attribute physical-size which is, in turn, a specialization of physical- attribute. These
generalization-specialization relationships are important for attributes because they support
inheritance.

o Technique for reasoning about values — This is about reasoning values of attributes
not given explicitly. Several kinds of information are used in reasoning, like, height:
must be in a unit of length, Age: of a person cannot be greater than the age of
person’s parents. The values are often specified when a knowledge base is created.

o Single valued attributes — This is about a specific attribute that is guaranteed to

take a unique value. For example, a baseball player can at time have only a single
height and be a member of only one team. KR systems take different approaches to
provide support for single valued attributes.

 Choosing Granularity:

 At what level of detail should the knowledge be represented?

 Regardless of the KR formalism, it is necessary to know:

o At what level should the knowledge be represented and what are the primitives?

o Should there be a small number or should there be a large number of low-level

primitives or High-level facts.

o High-level facts may not be adequate for inference while Low-level primitives may
require a lot of storage.

 Example of Granularity:

 Suppose we are interested in following facts:

o John spotted Sue.

o This could be represented as

SPR 9
 FOAI Unit-3 4350704

 Spotted (agent (John), object (Sue))

 Such a representation would make it easy to answer questions such are:

o Who spotted Sue?

o Suppose we want to know:

 Did John see Sue?

 Given only one fact, we cannot discover that answer.

o We can add other facts, such as

 Spotted (x, y) -> saw (x, y)

Representing Set of objects:

 How should sets of objects be represented?

 There are certain properties of objects that are true as member of a set but not as individual;

 Example: Consider the assertion made in the sentences:

o “There are more sheep than people in Australia”, and

o “English speakers can be found all over the world.”

 To describe these facts, the only way is to attach assertion to the sets representing people, sheep,
and English.

 The reason to represent sets of objects is: if a property is true for all or most elements of a set,
then it is more efficient to associate it once with the set rather than to associate it explicitly with
every element of the set.

 This is done in logical representation through the use of universal quantifier, and in hierarchical
structure where node represent sets and inheritance propagate set level assertion down to
individual.

 Finding Right structure:

SPR 10
 FOAI Unit-3 4350704

 Given a large amount of knowledge stored in a database, how can relevant parts be accessed
when they are needed?

 This is about access to right structure for describing a particular situation.

 This requires, selecting an initial structure and then revising the choice.

 While doing so, it is necessary to solve following problems:

o How to perform an initial selection of the most appropriate structure.

o How to fill in appropriate details from the current situations.

o How to find a better structure if the one chosen initially turns out not to be
appropriate.What to do if none of the available structures is appropriate.
o When to create and remember a new structure.

 FIRST ORDER LOGIC 

SPR 11
FOAI Unit-3 4350704

SPR 12
FOAI Unit-3 4350704


SPR 13
FOAI Unit-3 4350704


SPR 14
FOAI Unit-3 4350704


SPR 15
FOAI Unit-3 4350704


SPR 16
FOAI Unit-3 4350704

SPR 17
FOAI Unit-3 4350704

SPR 18
FOAI Unit-3 4350704

SPR 19
FOAI Unit-3 4350704

SPR 20
FOAI Unit-3 4350704

SPR 21
FOAI Unit-3 4350704

SPR 22
FOAI Unit-3 4350704

SPR 23
FOAI Unit-3 4350704

SPR 24
 FOAI Unit-3 4350704

What is Forward Reasoning?

 Forward reasoning is a process in artificial intelligence that finds all the possible solutions of a
problem based on the initial data and facts. Thus, the forward reasoning is a data-driven task as
it begins with new data.

 The main objective of the forward reasoning in AI is to find a conclusion that would follow. It
uses an opportunistic type of approach.

 Forward reasoning flows from initial to the consequence. The inference engine searches the
knowledge base with the given information depending on the constraints. The precedence of
these constraints has to match the current state.

 In forward reasoning, the first step is that the system is given one or more constraints. The rules
are then searched for in the knowledge base for every constraint. The rule that fulfils the
condition is selected. Also, every rule can generate a new condition from the conclusion which
is obtained from the invoked one. These new conditions can be added and are processed again.

SPR 25
 FOAI Unit-3 4350704

 The step ends if no new conditions exist. Hence, we can conclude that forward reasoning
follows the top-down approach.

What is Backward Reasoning?

 Backward reasoning is the reverse process of the forward reasoning in which a goal or
hypothesis is selected and it is analyzed to find the initial data, facts, and rules. Therefore,
the backward reasoning is a goal driven task as it begins with conclusions or goals that are
uncertain. The main objective of the backward reasoning is to find the facts that support the
conclusions.

 Backward reasoning uses a conservative type of approach and flows from consequence to the
initial. The system helps to choose a goal state and reasons in a backward direction. The
first step in the backward reasoning is that the goal state and rules are selected. Then, sub-goals
are made from the selected rule, which need to be satisfied for the goal state to be true.

 The initial conditions are set such that they satisfy all the sub-goals. Also, the established states
are matched to the initial state provided. If the condition is fulfilled, the goal is the solution,
otherwise the goal is rejected. Therefore, backward reasoning follows bottom- up technique.

 Backward reasoning is also known as a decision-driven or goal-driven inference

technique because the system selects a goal state and reasons in the backward direction.

 Difference between Forward and Backward Reasoning:

S.No. Forward Reasoning Backward Reasoning

1. It is a data-driven task. It is a goal driven task.
It begins with new data. It begins with conclusions that are
2.
uncertain.
The objective is to find a conclusion The objective is to find the facts that
3.
that would follow. support the conclusions.
It uses an opportunistic type of It uses a conservative type of approach.
4.
approach.

SPR 26
 FOAI Unit-3 4350704

It flows from incipient to the It flows from consequence to the

5.
consequence. incipient.
Forward reasoning begins with the Backward reasoning begins with some
6.
initial facts. goal (hypothesis).
7. Forward reasoning tests all the rules. Backward reasons test some rules.
Forward reasoning is a bottom-up Backward reasoning is a top-down
8.
approach. approach.
Forward reasoning can produce an Backward reasoning produces a finite
9.
infinite number of conclusions. number of conclusions.
In the forward reasoning, all the data is In the backward reasoning, the data is
10.
available. acquired on demand.
Forward reasoning has a small number Backward reasoning has a smaller
11. of initial states but a large number of number of goals and a larger number of
conclusions. rules.
In forward reasoning, the goal In backward reasoning, it is easy to
12.
formation is difficult. form a goal.
Forward reasoning works in forward Backward reasoning work in backward
13. direction to find all the possible direction to find the facts that justify the
conclusions from facts. goal.
Forward reason is suitable to answer Backward reasoning is suitable for
14. the problems such as planning, control, diagnosis like problems.
monitoring, etc.

Logic programming

 Prolog is a logic programming language. It has important role in artificial intelligence. Unlike
many other programming languages, Prolog is intended primarily as a declarative programming
language.

 In prolog, logic is expressed as relations (called as Facts and Rules). Core heart of prolog lies

SPR 27
 FOAI Unit-3 4350704

at the logic being applied. Formulation or Computation is carried out by running a query over
these relations.

Syntax and Basic Fields:

 In prolog, we declare some facts. These facts constitute the Knowledge Base of the system. We
can query against the Knowledge Base. We get output as affirmative if our query is already in
the knowledge Base or it is implied by Knowledge Base, otherwise we get output as negative.

 So, Knowledge Base can be considered similar to database, against which we can query. Prolog
facts are expressed in definite pattern. Facts contain entities and their relation. Entities are
written within the parenthesis separated by comma (,). Their relation isexpressed at the start
and outside the parenthesis. Every fact/rule end’s with a dot (.). So, a typical prolog fact goes as follows:

 Key Features:
o Unification: The basic idea is, can the given terms be made to represent the same
structure.

o Backtracking: When a task fails, prolog traces backwards and tries to satisfy
previous task.

o Recursion: Recursion is the basis for any search in program.

SPR 28
 FOAI Unit-3 4350704

 Running queries:
 A typical prolog query can be asked as:

 Advantages:

o Easy to build database. Doesn’t need a lot of programming effort.

o Pattern matching is easy. Search is recursion based.

o It has built in list handling. Makes it easier to play with any algorithm involving
lists.

 Disadvantages:

o LISP (another logic programming language) dominates over prolog with respect
to I/O features.

o Sometimes input and output is not easy.

 Applications:

o Prolog is highly used in artificial intelligence (AI). Prolog is also used for pattern
matching over natural language parse trees.

SPR 29
 FOAI Unit-3 4350704

Explain the algorithm of resolution in propositional logic. 4m or

Explain the algorithm of resolution in predicate logic. 7m

 The algorithm for resolution can be outlined as follows:

Explanation of the Algorithm:

 Input: The inputs to the algorithm are the knowledge base (KB) and the query (α).
The knowledge base is a collection of facts in propositional logic, and the query is the
proposition we want to prove.

 Clause Conversion: The algorithm starts by converting KB ∧ ¬α into a set of clauses

in CNF. This step is crucial because resolution operates only on CNF.

 Loop and Resolution: In each iteration, the algorithm selects pairs of clauses and
applies the resolution rule. If the resolution of two clauses results in the empty clause
(denoted as False), the algorithm returns true, indicating that the knowledge base
entails the query.

 Termination: If no new clauses can be added (i.e., new ⊆ clauses), the

algorithm returns false, implying that the query is not entailed by the knowledge base

SPR 30