AI UNIT-2
AI UNIT-2
AI UNIT-2
UNIT II
1
Unit II- Two Marks
1. What is knowledge based agent?
The central component of a knowledge-based agent is. Its knowledge base or KB.
Informally, a knowledge base is a set of representations of facts about the world. Each
individual representation. SENTENCE" is called a sentence the sentences are expressed in a
language called a knowledge representation language.
2
reasoning, which we will call logical inference or deduction. Logical inference is a process
that implements the entailment relation between sentences.
7. Define Validity?
A sentence is valid or necessarily true if and only if it is true under all possible
interpretations in all possible worlds, that is, regardless of what it is supposed to mean and
regardless of the state of affairs in the universe being described.
8. Define Satisfiability?
A sentence is satisfiable if and only if there is some interpretation in some world for
which it is true. The sentence "there is a wumpus at [1, 2]" is satisfiable because there might
well be a wumpus in that square, even though there does not happen to be one in
Sentence that is not satisfiable is unsatisfiable. Self-contradictory sentences are
unsatisfiable, if the contradictoriness does not depend on the meanings of the symbols.
9. Define Logic?
Logic consists of the following:
1. A formal system for describing states of affairs, consisting of
(a) The syntax of the language, which describes how to make sentences, and
(b) The semantics of the language, which states the systematic constraints on
how sentences. Relate to states of affairs.
2. The proof theory—a set of rules for deducing the entailments of a set
of sentences.
4
Use logical connectives to construct more complex sentences, just as in
propositional calculus. The semantics of sentences formed using logical connectives is
identical to that in the propositional case.
SUBST ({v/g}, )
For example, from x, Likes(x, Ice Cream), we can use the substitution {x/Ben} and infer
Likes (Ben, Ice Cream).
SUBST ({v/k}, )
5
For example, from x Kill(x, Victim), we can infer Kill (Murderer, Victim), as long as
Murderer does not appear elsewhere in the knowledge base.
v SUBST ({g/v}, )
7
• Slot Reader
9
50. What is forward chaining?
Forward Chaining is the process of moving from if pattern to the then pattern.
10
56. What is Resolution (Apr – May’15)
Rules used in the resolution procedure are:
(A V B, 7B V C) / (A V C)
(7A B, B C) / (7A C)
Resolution inference rule: two disjunctions of any length, if one of the disjunct in the
clauses (Pj) unifies with the negation of the disjunct in the other class, then the disjunction of
all the disjuncts except for those two.
Knowledge:
11
– Reasoning, that is, inferring the implications of what it knows and of the choices it has,
and
Representation of knowledge and the reasoning process are central to the entire field of
artificial intelligence. The primary component of a knowledge-based agent is its knowledge-
base. A knowledge-base is a set of sentences.
Each sentence is expressed in a language called the knowledge representation language.
Sentences represent some assertions about the world. There must mechanisms to derive
new sentences from old ones. This process is known as inferencing or reasoning.
Inference must obey the primary requirement that the new sentences should follow
logically from the previous ones. Logic is the primary vehicle for representing and reasoning
about knowledge. Specifically, we will be dealing with formal logic.
The advantage of using formal logic as a language of AI is that it is precise and definite.
This allows programs to be written which are declarative - they describe what is true and not
how to solve problems. This also allows for automated reasoning techniques for general
purpose inferencing. This, however, leads to some severe limitations. Clearly, a large portion
of the reasoning carried out by humans depends on handling knowledge that is uncertain.
Logic cannot represent this uncertainty well.
Similarly, natural language reasoning requires inferring hidden state, namely, the
intention of the speaker. When we say, "One of the wheel of the car is flat.” we know that it
has three wheels left. Humans can cope with virtually infinite variety of utterances using a
finite store of commonsense knowledge.
– A logic consists of two parts, a language and a method of reasoning. The logical
language, in turn, has two aspects, syntax and semantics. Thus, to specify or define a
particular logic, one needs to specify three things:
– Syntax: The atomic symbols of the logical language, and the rules for constructing well-
formed, non-atomic expressions (symbol structures) of the logic. Syntax specifies
12
the symbols in the language and how they can be combined to form sentences. Hence
facts about the world are represented as sentences in logic.
– Semantics: The meanings of the atomic symbols of the logic, and the rules for
determining the meanings of non-atomic expressions of the logic. It specifies what
facts in the world a sentence refers to. Hence, also specifies how you assign a truth
value to a sentence based on its meaning in the world. A fact is a claim about the
world, and may be true or false.
– Facts are claims about the world that are True or False, whereas a representation is
an expression (sentence) in some language that can be encoded in a computer
program and stands for the objects and relations in the world. We need to ensure that
the representation is consistent with reality, so that the following figure holds:
There are a number of logical systems with different syntax and semantics. We list
below a few of them.
– Propositional logic
– All objects described are fixed or unique
"John is a student" student (john) Here John refers to one unique person.
E.g. for All (A, B) [brother (A, B) -> brother (B, A)]
Knowledge based systems: systems that depend on rich base of knowledge to perform
difficult tasks.
A knowledge based agent can combine general knowledge with current percepts to
infer hidden aspects of the current state prior to selecting actions. Eg. Physician diagnoses a
patient. The central component of a knowledge-based agent is its knowledge base. There
must be a way to add new sentences to the knowledge base and a way to query what is
known. Inference is deriving new sentences from old.
14
The agent must be able to:
– Represent states, actions, etc.
– Incorporate new percepts
– Update internal representations of the world
– Deduce hidden properties of the world
– Deduce appropriate actions
Entailment
– Entailment means that one thing follows from another: KB ╞ α
– Knowledge base KB entails sentence α if and only if α is true in all worlds where KB is
true
– E.g., the KB containing “the Giants won” and “the Reds won” entails “Either the Giants
won or the Reds won”
– E.g., x+y = 4 entails 4 = x+y
– Entailment is a relationship between sentences (i.e., syntax) that is based on semantics
Inference
– KB ├i α = sentence α can be derived from KB by procedure i
– Soundness: i is sound if whenever KB ├i α, it is also true that KB╞ α
– Completeness: i is complete if whenever KB╞ α, it is also true that KB ├i α
– Preview: we will define a logic (first-order logic) which is expressive enough to say
almost anything of interest, and for which there exists a sound and complete
inference procedure.
– That is, the procedure will answer any question whose answer follows from what is
known by the KB.
15
3. DISCUSS PROPOSITIONAL LOGIC? (APR-MAY’15)
– Propositional logic is the simplest logic – illustrates basic ideas
Symbols:
The symbols of propositional logic are the logical contacts, true and false.
Eg: P, Q
Connectivities:
1. ∧ (and) : Conjunction
Eg: P۸Q
2. ∨(or) : Disjunction
Eg: P∨Q
3 => (or) (Implies): Implication or Conditional
Eg: (P∧Q) => R
R – Conclusion or consequent
4 (equivalent) – Equivalence or Biconditional
Eg: (P∧Q) (Q∧P)
5. 7 (not) – Negotion is the only connective that operates on a single sentence.
Eg: 7P
Sentence Atomic Sentence and complex sentence
Atomic sentence True/False/P/Q/R/
Complex Sentence (Sentence)
/sentence connective sentence
16
/ 7 sentence
Connective ∧/∨/ /=>
Order of Procedure: (from highest to lowest)
7, ∧, ∨, => and
Eg: 7P∨Q∧R => S is equivalent to ((7P) ∨) Q∧R)) => S
TRUTH TABLE:
P Q 7P P∧Q P∨Q P=>Q P Q
F F T F F T T
F T T F T T F
T F F F T F F
T T F T T T T
α β (or) α/β – This notation represents that β can be derived from α by inference. The
propositional logic has seven inference rules.
They are:
17
iv). or – Introduction:
From a disjunction, if one of the disjoints is false, then the true one is inferred.
vii). Resolution:
Implication is transitive
The proposition logic has a very limited ontology that is fact in the world and simple
sentences are represented.
FOL makes a stronger set of ontological and functions of the world belongings to be
represented.
18
Terms: First order logic has sentence, but it also has terms which represents objects.
Constant symbols, variables and function symbols are used to build terms and quantifiers
and predicate symbols are used to build sentences.
Sentence Atomic sentence
׀Sentence connective sentence
׀Quantifier variable,….sentence
7 ׀sentence
(׀sentence).
Atomic sentence Predicate (Term,)
Term Term
Term Function (Term…)
׀constant
׀variable
Connective =>׀∨׀∧׀
Quantifier ׀
Constant ׀λcon ׀john׀
Variable a ׀x ׀s …׀..
Predicate Before ׀Hascolour ׀Raining
Function Mother ׀Left-hand of׀........
1. Constants: Each constant symbol denotes exactly one object not necessarily one
name, might be represented by several names.
2. Variables: Assumes different valves in the domain during the inference technique.
3. Predicate symbols: It refers to a particular relation in the model.
19
4. Tuple: In a model the relation is defined by the set of tuple of objects. Tuple is a
collection of objects arranged in a fixed order.
5. Function symbol: A type of relation that is exactly related to one of the other objects
by the relation.
6. Atomic Sentences: An atomic sentence is formed from a predicate symbol.
7. Complex sentence: Logical connectives are used to construct move complex
sentence in which the semantic of given sentence has to be satisfied.
QUANTIFIERS:
Quantifiers are used to express properties of entire collection of objects, rather than
represent the object by names. FOL contains two standard quantifiers,
# Universal quantifier ( )
# Existential quantifier ( )
UNIVERSAL QUANTIFIERS:
Examples:
All cats are mammals => X cat (X) mammals(X)
That is, all the cats in the universe belongs to the type of mammals and hence the variable
X may be replaced by any of the cat name (object, Name)
Examples:
Spot is a cat
Spot is a mammal
Cat (spot)
Mammal (spot)
20
Cat (spot) mammal (spot)
Spot – Name of the cat.
Existential Quantifiers:
Example:
sister (
cat(X)
That is, the spot’s sister is a cat, implies spot is also a cat and hence X may be replaced by,
sister of spot, if it exists.
Example:
Felix is a cat.
Cat (Felix)
Sister (Felix, spot) cat (Felix).
NESTED QUANTIFIERS:
Example:
21
# Everybody loves somebody
Y loves (X, Y)
The two Quantifiers ( and ) are actually connected with each other through negation.
Example:
The De Morgan rules for quantified and unquantified sentences are as follows,
# Quantified sentences:
X7P ≡ 7 XP
7 XP ≡ X7P
XP ≡ 7 X 7P
XP ≡ 7 X 7P
#Unquantified sentence:
7(P∧Q) ≡ 7P ∨ 7Q
7P ∧ 7Q ≡ 7(P∨Q)
P ∧ Q ≡ 7(7P ∨ 7Q)
22
P∨ Q ≡ 7(7P ∧ 7Q)
The require findings substitutions that make different logical expression. This proves
is called unification and is a key component of all first order inference algorithms. The UNIFY
algorithm takes two sentences and returns a unifier for them if one exists:
Here are the results of unification with four different sentences that might be in
knowledge
base.
The last unification fails because x cannot take on the values john and Elizabeth at the
sametime. Now remember that knows (x,Elizabeth) means “everyone knows Elizabeth”, so
we should be able to infer that john knows Elizabeth. The problem arises only because the
two sentences happen to use the same variable name, x. the problem can be avoided by
standardizing apart one of the two sentences being unified, which means remaining its
variable to avoid name clashes
– We can get the inference immediately if we can find a substitution θ such that King(x)
and Greedy(x) match King(John) and Greedy(y)
θ = {x/John,y/John} works
– Unify(α,β) = θ if αθ = βθ
p q θ Knows(John,x) Knows(John,Jane)
Knows(John,x) Knows(y,OJ) Knows(John,x)
Knows(y,Mother(y))
23
Knows(John,x) Knows(x,OJ)
p q θ
Knows(John,x) Knows(John,Jane) {x/Jane}}
Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}
Knows(John,x) Knows(y,Mother(y))
Knows(John,x) Knows(x,OJ)
p q θ
Knows(John,x) Knows(John,Jane) {x/Jane}}
24
Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}
Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}}
Knows(John,x) Knows(x,OJ)
– Standardizing apart eliminates overlap of variables, e.g., Knows(z17,OJ)
– We can get the inference immediately if we can find a substitution θ such that King(x)
and Greedy(x) match King(John) and Greedy(y)
θ = {x/John,y/John} works
– Unify(α,β) = θ if αθ = βθ
p q θ
Knows(John,x) Knows(John,Jane) {x/Jane}}
Knows(John,x) Knows(y,OJ) {x/OJ,y/John}}
Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}}
Knows(John,x) Knows(x,OJ) {fail}
25
Generalized Modus Ponens (GMP)
p1', p2', … , pn', ( p1 p2 … pn q)
qθ
p1' is King(John) p1 is King(x)
p2' is Greedy(y) p2 is Greedy(x)
θ is {x/John,y/John} q is Evil(x) ``
q θ is Evil(John)
– GMP used with KB of definite clauses (exactly one positive literal)
– All variables assumed universally quantified
Soundness of GMP
– Need to show that
p1', …, pn', (p1 … pn q) ╞ qθ
provided that pi'θ = piθ for all I
– Lemma: For any sentence p, we have p ╞ pθ by UI
– (p1 … pn q) ╞ (p1 … pn q)θ = (p1θ … pnθ qθ)
– p1', \; …, \;pn' ╞ p1' … pn' ╞ p1'θ … pn'θ
– From 1 and 2, qθ follows by ordinary Modus Ponens
(A V B, 7B V C) / (A V C)
(7A B, B C) / (7A C)
26
Resolution inference rule: two disjunctions of any length, if one of the disjunct in the
clauses (Pj) unifies with the negation of the disjunct in the other class, then the disjunction of
all the disjuncts except for those two.
P1 V……..Pj….….VPm, Q1V……..Qk……….VQn
P1 ∧ ………..Pj………Pn1 r1V……..rn2
S1∧ ………….Sn3 Q1V………Qk……….Qn4
Implicative normal form (INF): all the conjunction of atoms on the left and a
disjunction of atoms on the right
• Elimination implications
27
• Move 7 inwards
• Move quantifiers left
• Skimolize
• Distribute ∧ over V
• Flatten nested conjunctions and disjunctions
• Convert disjunctions to implications.
7. Explain Weak slot - filler structure (Apr-May’14)
We have seen using rules for knowledge representation. While rules have been
widely used, there are several other important approaches to knowledge
representation.
– Structured objects
– Semantic nets.
– frames;
– logic;
Structured Objects
– The graphical depiction associated with a semantic network is a big reason for their
popularity.
28
A semantic (or associative) network is a simple representation scheme which uses a graph of
labeled nodes and labeled, directed arcs to encode knowledge.
– Labeled nodes: objects/classes/concepts.
– Labeled links: relations/associations between nodes
– Labels define the semantics of nodes and links
– Large # of node labels (there are many distinct objects/classes)
Small # of link labels (types of associations can be merged into a few)
Buy, sale, give, steal, confiscation, etc., can all be represented as a single relation of
“transfer ownership” between recipient and donor
– Usually used to represent static, taxonomic, concept dictionaries
– Semantic networks are typically used with a special set of accessing procedures which
perform “reasoning”
– e.g., inheritance of values and relationships
– Often much less expressive than other KR formalisms
These values can also be represented in logic as: is a(person, mammal), instance(Mike-Hall,
person) team(Mike-Hall, Cardiff)
29
We have already seen how conventional predicates such as lecturer (dave) can be written as
instance (dave, lecturer) Recall that is a and instance represent inheritance and are popular in
many knowledge representation schemes. But we have a problem: How we can have more
than 2 place predicates in semantic nets? E.g. score (Cardiff, Llanelli, 23-6) Solution:
• Create new nodes to represent new objects either contained or alluded to in the
knowledge, game and fixture in the current example.
• Relate information to nodes and fill up slots.
As a more complex example consider the sentence: John gave Mary the book. Here we have
several aspects of an event.
30
Two methods to do this:
1. Intersection search
-- The notion that spreading activation out of two nodes and finding their intersection
finds relationships among objects. This is achieved by assigning a special tag to each
visited node.
2. Inheritance
Inheritance also provides a means of dealing with default reasoning. E.g. we could represent:
In making certain inferences we will also need to distinguish between the link that
defines a new entity and holds its value and the other kind of link that relates two existing
entities. Consider the example shown where the height of two people is depicted and we also
wish to compare them.
31
We need extra nodes for the concept as well as its value.
Special procedures are needed to process these nodes, but without this distinction the
analysis would be very limited.
Here we will consider some extensions to Semantic nets that overcome a few problems (see
Exercises) or extend their expression of knowledge.
Basic idea: Break network into spaces which consist of groups of nodes and arcs and regard
each space as a node. Nodes and arcs to link this space the rest of the network to represent
Andrew's belief.
Consider the following: Andrew believes that the earth is flat. We can encode the proposition
the earth is flat in a space and within it have nodes and arcs the represent the fact. We can the
32
have now consider the quantified expression: Every parent loves their child to represent this
we:
child(y) loves(x,y)
Here we have to construct two spaces one for each x, y. NOTE: We can express variables as
existentially qualified variables and express the event of love having an agent p and receiver b
for every parent p which could simplify the network
Also If we change the sentence to Every parent loves child then the node of the object
being acted on (the child) lies outside the form of the general statement. Thus it is not viewed
as an existentially qualified variable whose value may depend on the agent. (See Exercises
and Rich and Knight Book for examples of this) So we could construct a partitioned network
as in following figure:
33
Fig. Partitioned network
Multiple Inheritance
A node can have any number of super classes that contain it, enabling a node to inherit
properties from multiple parent nodes and their ancestors in the network. It can cause
convicting inheritance.
Nixon Diamond
34
Problems with of Semantic Nets II
Other problematic statements. . .
Examples:
Attempted Improvements
Building search heuristics into the network. More sophisticated logical structure, involving
partitioning. These improvements meant that the formalism’s -original simplicity was lost.
Frames
Frames. Semantic net with properties and methods Devised by Marvin Minsky, 1974.
35
Incorporates certain valuable human thinking characteristics:
o A name
36
Reasoning
o How to reason with frame systems?
In the lower levels, the value in a slot may be a specific value, to overwrite the value which
would otherwise be inherited from a higher frame. An instance of an object is joined to its
class by an instance relationship. A class is joined to its superclass by is a relationship.
It has been used by many programs that portend to understand English (MARGIE, SAM, PAM).
CD developed by Schank et al. as were the previous examples.
37
CD provides:
Six primitive conceptual categories provide building blocks which are the set of allowable
dependencies in the concepts in a sentence:
38
PA -- Attributes of objects.
T -- Times.
LOC -- Locations.
relationships: o -- object.
R -- recipient-donor.
– Double arrows ( ) indicate two-way links between the actor (PP) and action (ACT).
– The actions are built from the set of primitive acts (see above).
The use of tense and mood in describing events is extremely important and schank
introduced the following modifiers:
p -- past
f -- future
39
t -- transition
-- start transition
-- finished transition
k -- continuing
? -- interrogative
/ -- negative
delta -- timeless
c -- conditional
The has an object (actor), PP and action, ACT. I.e. PP ACT. The triplearrow ( ) is
also a two link but between an object, PP, and its attribute, PA. I.e. PP PA.
Primitive states are used to describe many state descriptions such as height, health, mental
state, physical state.
There are many more physical states than primitive actions. They use a numeric scale.
E.g. John height(+10) John is the tallest John height(< average) John is short Frank
Zappa health(-10) Frank Zappa is dead Dave mental_state(-10) Dave is sad Vase
physical_state(-10) The vase is broken
40
You can also specify things like the time of occurrence in the relationship.
Now let us consider a more complex sentence: Since smoking can kill you, I stopped Lets look
at how we represent the inference that smoking can kill:
– Have a conditional, c causality link. The triple arrow indicates dependency of one
concept on another.
41
Advantages of CD:
Disadvantages of CD:
Dave bet Frank five pounds that Wales would win the Rugby World Cup.
Applications of CD:
MARGIE (Meaning Analysis, Response Generation and Inference on English) -- model natural
language understanding.
SAM (Script Applier Mechanism) -- Scripts to understand stories. See next section.
42
9.Explain forward and backward Reasoning (or) Forward and backward chaining
QUESTION BANK & UNIVERSITY QUESTIONS
43