Artificial Intelligence

CHAPTER-3
Knowledge representation
Basic Concepts
Framework For Knowledge Representation
Framework For Knowledge Representation
Uniformed Search Technique -BFS
Representation And mapping(facts and representation)
Representation of facts
Techniques of Artificial Intelligence
Techniques of Artificial Intelligence
Techniques of Artificial Intelligence
Approaches(Properties) to knowledge representation
 Representational Adequacy

•Representational adequacy refers to the ability of a knowledge representation

system to effectively and accurately represent all the necessary knowledge
within a specific domain.

•Essentially, it means the system can capture and store all the relevant
information required for an AI to understand and reason about a particular
subject area.

•Example: imagine trying to build a model of a car. Representational adequacy

would mean your model can accurately represent all the parts of the car, their
functions, and how they relate to each other. If you leave out the engine, your
model lacks representational adequacy for a car that can actually move.
 Inferential Adequacy

•A system's ability to derive new knowledge or information from existing

knowledge through logical reasoning or inference.
•It essentially means the system can manipulate the stored information to draw
conclusions and generate new insights.
•Example: If a system knows "all humans are mortal" and "Socrates is a human",
it should be able to infer that "Socrates is mortal". Another example is if a system
knows that "if it rains, the ground will be wet" and "it is raining", it should be able
to infer that "the ground is wet".
•Inferential adequacy ensures that the knowledge representation is not just a static
storage of facts, but a dynamic system capable of producing new knowledge
through reasoning.
 Inferential Efficiency

•How effectively an AI model utilizes its knowledge to make

accurate predictions or decisions from new data, especially in a
computationally efficient way.
• It's about the speed and accuracy with which the model can
process information and arrive at a conclusion, minimizing both
processing time and resource consumption.
•A highly inferentially efficient AI model is one that can quickly
and accurately draw conclusions from new data while minimizing
resource usage. This is a crucial characteristic for AI systems to
be practical and effective in real-world applications.
 Acquisitional Efficiency

•The ability of a knowledge representation system or AI model to

effectively and efficiently acquire new knowledge or information.
• In other words, an acquisitionally efficient system should be
able to rapidly and accurately learn from new data or experience.
•A system with high acquisitional efficiency can automatically
learn new information, adapt to changing circumstances, and
improve its performance over time.
Knowledge representation schemes
Generate And Test Strategy
Generate And Test Strategy
Cooking:
Knowing how to bake a cake involves a sequence of steps: preheating the oven,
mixing ingredients, baking for a specific time, etc.
Playing a musical instrument:
Learning to play a piano involves understanding how to position your fingers,
press keys, and coordinate movements.
 Issues in knowledge representation
1. Scope and Granularity: The real world is vast and complex. Deciding
which facts, objects, relationships, and processes are relevant to a given
problem is a significant challenge.
Should we represent knowledge at a high, abstract level (e.g., "Birds can
fly") or at a very detailed, low level (e.g., "A robin's wing muscles contract
to generate lift")?
2. Expressiveness vs. Tractability (Computational Efficiency):
Expressiveness: A KR language should be expressive enough to capture
all the necessary nuances of the domain. First-Order Logic (FOL), for
example, is highly expressive.
Tractability: However, the more expressive a representation, the more
computationally expensive it often becomes to perform inference and
reasoning over it. Finding a balance between what can be expressed and
what can be efficiently reasoned about is a core dilemma
 Issues in knowledge representation

3. Handling Uncertainty and Incompleteness:

Uncertainty: The real world is rarely black and white. Knowledge is
often uncertain, probabilistic, or fuzzy. Traditional logical
representations struggle with this (e.g., "It will probably rain today").
Incompleteness: AI systems rarely have complete knowledge.
They must be able to reason and make decisions even with missing
information.
Approaches: This has led to the development of probabilistic
graphical models (Bayesian networks), fuzzy logic, and other
methods for handling uncertainty.
 Issues in knowledge representation

4. Common Sense Knowledge:

Humans possess a vast amount of intuitive common sense
knowledge about how the world works (e.g., "objects fall down,"
"people have one head"). This knowledge is incredibly difficult to
formalize and represent for AI systems.
Brittleness: AI systems often lack common sense, making them
"brittle" – they perform well within their narrow domain of
programmed knowledge but fail dramatically when faced with
situations outside that scope.
 Issues in knowledge representation

5. Knowledge Acquisition and Learning:

Knowledge Acquisition Bottleneck: Manually encoding large
amounts of knowledge is extremely time-consuming, expensive,
and prone to errors. This is often called the "knowledge acquisition
bottleneck."
Integration with Learning: How can AI systems automatically
acquire, refine, and update their knowledge from data and
experience? Integrating KR with machine learning is a major
research direction, moving from static, hand-coded knowledge
bases to dynamic, adaptable ones.
 Issues in knowledge representation

6. Representing Relationships and Context:

Relationships among attributes: How do attributes of objects
relate to each other? For example, the height attribute of a person
relates to their age and gender.
Context: The meaning of knowledge often depends on the context.
Representing and reasoning about context is crucial for
understanding natural language, interpreting sensory data, and
making appropriate decisions.
7. Dealing with Time and Change:
The world is dynamic. Events happen, states change, and
knowledge evolves over time. Representing temporal information,
causality, and concurrency accurately is complex.
 Issues in knowledge representation

8. Scalability:
As the amount of knowledge increases, efficient storage, retrieval,
and reasoning become critical. Large-scale knowledge bases
require sophisticated indexing, distributed systems, and optimized
inference engines.
 Propositional Logic

Propositional logic deals with propositions, which are declarative

statements that are either definitively true or definitively false, but
not both. They are the basic building blocks of knowledge.
Key Components for Representation
Example
 Reasoning Pattern/Inference in Propositional Logic
Reasoninig/Inference is the process of deriving new, valid
conclusions from existing knowledge (a set of propositions
or a knowledge base). It allows an AI system to "reason"
and extend its understanding of the world.
 Cont..
Inference Rules /reasoning patterns: These are patterns
of logical reasoning.
•Modus Ponens:
If you know P and you know P → Q, then you can infer Q.
Example: "It is raining" (P), "If it is raining, then the ground is wet" (P → Q).
Infer: "The ground is wet" (Q).

•Modus Tollens:
If you know P → Q and you know ¬Q, then you can infer ¬P.
Example: "If it is raining, then the ground is wet" (P → Q), "The ground is NOT
wet" (¬Q). Infer: "It is NOT raining" (¬P).

•And-Introduction:
If you know P and you know Q, then you can infer P ∧ Q.
 Cont..
•And-Elimination:
If you know P ∧ Q, then you can infer P (or Q).

•Hypothetical Syllogism:
If we know two conditional statements where the consequent of the first
is the antecedent of the second (P → Q and Q → R), then we can infer
a new conditional statement (P → R)
 Cont..

•Resolution: A powerful inference rule that forms the basis of many

automated theorem provers. It works by converting sentences into
Conjunctive Normal Form (CNF) and then applying a specific rule to
derive new clauses (disjunctions of literals). It's a complete inference
procedure for propositional logic (and first-order logic too).
If you have a clause A ∨ B and another clause ¬B ∨ C, you can resolve
them to get A ∨ C.
Often used in Resolution Refutation: To prove KB ->α, you show that
KB ∧ ¬ α is unsatisfiable (leads to a contradiction, the empty clause []).
 Resolution in Propositional Logic

From Unit 2 part2

Example of Propositional Logic(PL)
Example of Propositional Logic(PL)
Limitations of Propositional Logic(PL)
Predicate Logic(First Order Logic)
Predicate Logic
Knowledge Representation in Predicate Logic(First Order Logic)
Predicate Logic
Predicate Logic
Representing simple facts in Predicate logic
Representing simple facts in Predicate logic
 Representing instance and ISA relationship
Representing "instance" and "ISA" (Is-A) relationships in predicate logic is
fundamental for building knowledge bases
1. Instance Relationship (Individual to Class)
This relationship connects a specific individual to a general class or
category it belongs to.
In Natural Language:
"Socrates is a man."
"My car is a red vehicle."
"The Eiffel Tower is a monument.“
 Cont..
In Predicate Logic: We use a unary predicate to represent the class,
and the individual is the argument of that predicate.
ClassName(individual_name)
Examples:
•"Socrates is a man."
Man(Socrates)
•"My car is a red vehicle." (Assuming 'RedVehicle' is a class)
RedVehicle(MyCar)
Alternatively, using multiple predicates: Vehicle(MyCar) and Color(MyCar,
Red)
•"The Eiffel Tower is a monument."
Monument(EiffelTower)
 Cont..
2. ISA Relationship (Class to Class / Subclass to Superclass)
This relationship expresses that one class is a subcategory of another
more general class. It implies inheritance of properties. If something is a
member of the subclass, it is also a member of the superclass.

In Natural Language:
"All men are mammals."
"A dog is a canine."
"Vehicles are modes of transport."
 Cont..
In Predicate Logic: We typically use universal quantification (∀) and
implication (→) to express that if something is a member of the subclass,
then it is also a member of the superclass.
∀x(SubClass(x)→SuperClass(x))

Examples:
•"All men are mammals."
∀x(Man(x)→Mammal(x))
•This reads: "For all things x, if x is a Man, then x is a Mammal."
"A dog is a canine."
∀x(Dog(x)→Canine(x))
•"Vehicles are modes of transport."
∀x(Vehicle(x)→ModeOfTransport(x))
 Cont..
Instance: This is a direct assertion that a specific entity belongs to a
particular category.
ISA:This represents a hierarchical relationship between categories,
where the properties of the superclass are inherited by the subclass.

Combining Instance and ISA Relationships for Reasoning

These two types of relationships work together to enable logical inference.
Example Scenario:
Given the following knowledge base:
1. Man(Socrates) (Socrates is a man)
2. ∀x(Man(x)→Mammal(x)) (All men are mammals)
3. ∀x(Mammal(x)→WarmBlooded(x)) (All mammals are warm- blooded)
 Cont..
Can we infer that Socrates is Warm-Blooded?

Yes, using rules of inference:

From (1) Man(Socrates) and (2) ∀x(Man(x)→Mammal(x)), by Universal
Instantiation we can infer:
Mammal(Socrates) (Socrates is a mammal)

From Mammal(Socrates) and (3) ∀x(Mammal(x)→WarmBlooded(x)), by

Universal Instantiation we can infer:
WarmBlooded(Socrates) (Socrates is warm-blooded)
 Computable Functions and Predicates

Computable Functions
A function is computable if there exists an algorithm (a finite, unambiguous set
of step-by-step instructions) that can, for any valid input in the function's domain,
produce the correct output in a finite amount of time.
•Turing Machine Connection: The most widely accepted formal definition states
that a function is computable if and only if it can be computed by a Turing
machine.

Examples:
•Addition(x, y) = x + y is computable.
•Factorial(n) = n! is computable.
•FindShortestPath(graph, start, end) (like Dijkstra's algorithm) is computable.
•SortList(list) is computable.
 Cont..

Computable Predicates
A predicate is a statement that can be either true or false depending on
its arguments. A predicate is computable (or decidable) if there exists an
algorithm that can, for any valid input, determine whether the predicate is
true or false in a finite amount of time.

Boolean Functions: Computable predicates are essentially computable

functions that always return a Boolean (True/False) value.
Decidability: The term "decidable" is often used interchangeably with
"computable" for predicates. A problem whose answer is a "yes" or "no"
(or True/False) is decidable if there's an algorithm to solve it.
 Resolution in predicate logic

Theory From Unit 2 Part 2

Example:
 Cont..

Prove: Hate(Marcus,Cesar)
Cont..
Cont..
 Inference Rules for FOL/Predicate Logic

1.Universal Instantiation (UI) / Universal Elimination:

Pattern: If a statement is true for all objects (universally quantified),

then it's true for any specific object.

Example:
KB: ∀x (Human(x)→Mortal(x)) (All humans are mortal)
KB: Human(Socrates) (Socrates is human)
Apply UI :
Human(Socrates) → Mortal(Socrates)
 Cont..

2. Existential Instantiation (EI) / Existential Elimination:

Pattern: If a statement is true for at least one object (existentially

quantified), then we can introduce a new, unique constant (a Skolem
constant) to represent that object.

Example:
KB: ∃x (King(x)∧Greedy(x)) (There exists a king who is greedy)
Apply EI: new constant k=King1: King(King1) ∧ Greedy(King1)
 Cont..

3.Universal Generalization (UG) / Universal Introduction:

Pattern: If a property P(c) holds true for an arbitrary (arbitrarily chosen,

not special) element c, then we can conclude that ∀xP(x) is true.

Example: c=2k
P( c ) : is divisible by 2
P(x)= even number
∀x P(x) P( c ) is true.
 Cont..

4. Existential Introduction (EI) / Existential Generalization:

Pattern: If a property P(c) holds true for a specific element c, then we

can infer that there exists at least one object for which that property
holds.

∃xP(x)P(c)​

Example:
Fact: Loves(John, Mary)
Inference: ∃x Loves(x,Mary) (Someone loves Mary)
Reasoning Strategies or pattern in Predicate Logic/FOL

1.Forward Chaining (Data-Driven):

Starts with known facts and applies inference rules (like
Generalized Modus Ponens) to derive new facts until the
query is proven or no new facts can be derived.

Analogy: "What else can I know from what I already know?“

Applications: Situations where new data arrives frequently

and you want to deduce all possible consequences (e.g.,
monitoring systems, some types of expert systems).
 Cont..

2. Backward Chaining (Goal-Driven):

Starts with the query (goal) and works backward, looking for
rules that could prove the goal. For each such rule, it tries to
prove its premises as sub-goals.

Analogy: "How can I prove this goal? What must be true for
this goal to be true?“

Applications: Question-answering systems, diagnostic

systems, logic programming (Prolog primarily uses
backward chaining)
Inference Rules for FOL/Predicate Logic
www.paruluniversity.ac.in