CHAPTER 4

MACHINE LEARNING
INSTRUCTOR: SERKALEM M.

TARGET GROUP: G4 SOFTWARE ENGINEERING

1
ΑΙ and KR
• A description of Artificial
Intelligence is:
– The study and development of
systems that demonstrate intelligent
behavior

• Based on the above, a description of

KR&R is the part of AI that is
Knowledge Representation & concerned with thinking and
Reasoning is: how thinking contributes to
– The study of ways to represent kg and intelligent behavior
reason with information in order to
achieve intelligent behavior
Knowledge Representation

• Knowledge representation, then, is the field of study concerned with using

formal symbols to represent a collection of propositions believed by some
agent.

3
Reasoning
• In general, it is the formal manipulation of the symbols representing a
collection of believed propositions to produce representations of new ones.

– We might start with the sentences “John loves Mary” and “Mary is
coming to the party” and after a certain amount of manipulation
produce the sentence, “Someone John loves is coming to the party.”
– We would call this form of reasoning logical inference because the
final sentence represents a logical conclusion of the propositions
represented by the initial ones.
• Reasoning is a form of calculation, not unlike arithmetic, but over symbols
standing for propositions rather than numbers. 4
Knowledge-Based Agents
• Knowledge-based agents are those agents who have the capability of
maintaining an internal state of knowledge, reason over that knowledge,
update their knowledge after observations and take actions.
• Central component of a Knowledge-Based Agent is a Knowledge-Base
– A set of sentences in a formal language
• Sentences are expressed using a knowledge representation language
• Two generic functions:
– TELL - add new sentences to the KB
• “Tell it what it needs to know”
– ASK - query what is known from the KB
• “Ask what to do next” 5
Knowledge based agent
• Is composed of:
1. Knowledge base: Domain Specific
2. Inference Mechanism: Domain independent algorithm

6
Knowledge-Based Agents
• Declarative
– You can build a knowledge-based agent simply by “TELLing”
it what it needs to know
• Procedural
– Encode desired behaviours directly as program code
• Simple world example:
– Wumpus World

7
 WUMPUS World
PEAS description of Wumpus world

• Performance Measure
– Gold +1000, Death – 1000
– Step -1, Use arrow -10
• Environment
– Square adjacent to the Wumpus are smelly
– Squares adjacent to the pit are breezy
– Glitter iff gold is in the same square
– Shooting kills Wumpus if you are facing it
– Shooting uses up the only arrow
– Grabbing picks up the gold if in the same square
– Releasing drops the gold in the same square
• Actuators
– Left turn, right turn, forward, grab, release, shoot
• Sensors
– Breeze, glitter, and smell
8
Wumpus World PEAS description
• Fully Observable No – only local perception
• Deterministic Yes – outcomes exactly specified
• Episodic No – sequential at the level of actions
• Static Yes – Wumpus and Pits do not move
• Discrete Yes
• Single-agent? Yes – Wumpus is essentially a natural feature

9
 Exploring the Wumpus World

1. The KB initially contains the rules of the environment.

2. [1,1] The first percept is [none, none,none,none,none], Move to safe cell e.g. 2,1

3. [2,1] Breeze indicates that there is a pit in [2,2] or [3,1] Return to [1,1] to try next safe cell 10
 …

4. [1,2] Stench in cell: wumpus is in [1,3] or [2,2]

YET … not in [1,1]
• Thus … not in [2,2] or stench would have been detected in [2,1]
• Thus … wumpus is in [1,3]
• Thus … [2,2] is safe because of lack of breeze in [1,2]
• Thus … pit in [3,1]
11
• Move to next safe cell [2,2]
…..

5. [2,2] Detect nothing

Move to unvisited safe cell e.g. [2,3]
6. [2,3] Detect glitter , smell, breeze
Thus… pick up gold
Thus… pit in [3,3] or [2,4] 12
How can knowledge be represented ?
• There are mainly four ways of knowledge representation
– Logical Representation
– Semantic Representation
– Frame Representation
– Production Rules
Logical Representation
• It is a language with some concrete rules which deals with
propositions & has no ambiguity in representation
• It consists of precisely defines Syntax and Semantics .
• each sentence can be translated into logics using syntax and
semantics.
– Syntax: defines well- formedness sentence in the language
– Semantics: defines the truth or meaning of sentence in world

14
Basic Idea of Logic

• Logic can be defined as the proof or validation behind any reason

provided.
• It was important to include logic in Artificial Intelligence because we
want our agent (system) to think and act humanly, and for doing so, it
should be capable of taking any decision based on the current situation.

15
Logical Representation
• Can be explained by:
1. Propositional logic
2. Predicate logic

16
Propositional Logic (PL)

• Is the simplest logic

• Declarative statement, either it can be true or false.
• It is a technique of knowledge representation in logical and mathematical form.
• Syntax
• Propositions, e.g. “it is wet”
• Logical Connectives: and (conjuction), or(disjunction), not (negation), implies (implication), iff ( biconditional)
• Brackets, T (true) and F (false)
• Semantics
– Define how connectives affect truth
– “P and Q” is true if and only if P is true and Q is true
– Use truth tables to work out the truth of statements

17
 Logical connectives
Logical connectives are used to connect two simpler propositions or representing a sentence logically.
1. Negation: A sentence such as ¬ P is called negation of P. A literal can be either Positive literal or negative literal.
2. Conjunction: A sentence which has ∧ connective such as, P ∧ Q is called a conjunction.
Example: Rohan is intelligent and hardworking. It can be written as,
P= Rohan is intelligent,
Q= Rohan is hardworking. → P∧ Q.
3. Disjunction: A sentence which has ∨ connective, such as P ∨ Q. is called disjunction, where P and Q are the
propositions.
Example: "Ritika is a doctor or Engineer",
Here P= Ritika is Doctor. Q= Ritika is Engineer, so we can write it as P ∨ Q.
4. Implication: A sentence such as P → Q, is called an implication. Implications are also known as if-then rules. It can
be represented as
If it is raining, then the street is wet.
Let P= It is raining, and Q= Street is wet, so it is represented as P → Q
5. Biconditional: A sentence such as P⇔ Q is a Biconditional sentence, example If I am breathing, then I am alive
P= I am breathing, Q= I am alive, it can be represented as P ⇔ Q.
18
…continued
• Truth Table

• E.g. • Conditions
P – It is hot  If it is humid, then it is hot QP
Q – It is humid  If it is hot and humid then it is not raining (P Ʌ Q)  ¬R
R – It is raining

19
 …
• Example: WUMPUS worlds using propositional logic
1,4 2,4 3,4 4,4

S B
1,3 2,3 3,3 4,3

W S
GB P B
There is no pit in [1,1]: 1,2 2,2 3,2 4,2
R1: ¬P1,1 S B
A square is breezy if and only if there is a pit in a neighbouring square.
1,1 2,1 3,1 4,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1).
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) A B P B
The preceding sentences are true in all Wumpus worlds
R4 : ¬ B1,1
R5 : B2,1 20
First Order Predicate Logic

• FOL is another way of knowledge representation in A I

• It is an extension to PL( Propositional Logic)
• It is a powerful language that develops information about the object in a more
easy way and can also express the relationship between those objects
• FOL doesn’t only assume that the world contains facts like PL but also assume
– Objects: A, B, people, numbers, colors, wars, theories, pits, wumpus, ......
– Relations: It can be unary relation such as: red, round, is adjacent, or n-any
relation such as: the sister of, brother of, has color, comes between
– Function: Father of, best friend, third inning of, end of, ......

21
…continued
• As a natural language, first-order logic also has two
main parts:
– Syntax
– Semantics
• The syntax of FOL determines which collection of
symbols is a logical expression in first-order logic.
• The basic syntactic elements of FOL are symbols.
22
First Order Logic
• More expressive logic than propositional
• Constants are objects: john, apples
• Predicates are properties and relations:
– likes(john, apples)
• Functions transform objects:
– likes(john, fruit_of(apple_tree))
• Variables represent any object: likes(X, apples)
• Quantifiers qualify values of variables
– True for all objects (Universal): X. likes(X, apples)
– Exists at least one object (Existential): X. likes(X, apples)

23
 …
Constant 1, 2, A, John,
Addisababa, cat,....

Variables x, y, z, a, b,....

Basic Elements of First- Predicates Brother, Father, >,....

order logic
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃ 24
…
• Sentence in FOL can be
– Atomic or
– Complex
• Atomic Sentences:
– are most basic sentences of FOL
– Formed from a predicate symbol followed by a parenthesis with a sequence
of terms.
– We can represent atomic sentences as Predicate (term1, term2, ......, term n).
– Example:
• John and David are brothers: => Brothers(John, David).
• Jack is a dog: => dog(Jack).
25
…
• Complex Sentences:
– are made by combining atomic sentences using
connectives.
– Example:
• Sibling(KingJohn, Richard) ⇒ Sibling(Richard, KingJohn)
• >(1, 2) ∨ ≤(1, 2)

26
Quantifiers in First-order logic:

• A quantifier is a language element which generates quantification, and

• quantification specifies the quantity of specimen in the universe of
discourse.
• These are the symbols that permit to determine or identify the range and
scope of the variable in the logical expression.
• There are two types of quantifier:
– Universal Quantifier, (for all, everyone, everything)
– Existential quantifier, (for some, at least one).

27
 Quantifiers in First-order logic:
• Universal quantifier
– is a symbol of logical representation, which specifies that the statement within its
range is true for everything or every instance of a particular thing.
– is represented by a symbol ∀, which resembles an inverted A.
– In universal quantifier we use implication " ⇒ "
– If x is a variable, then ∀x is read as:
• For all x
• For each x
• For every x.
– Example: All man drink coffee.
• Let a variable x which refers to a man so all x can be represented in: ∀x man(x) → drink (x, coffee).
• It will be read as: There are all x where x is a man who drink coffee.
28
Quantifiers in First-order logic:
• Existential quantifiers
– are the type of quantifiers, which express that the statement within its scope
is true for at least one instance of something.
– It is denoted by the logical operator ∃, which resembles as inverted E.
– In Existential quantifier we always use AND or Conjunction symbol (∧).
– If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be
read as:
• There exists a 'x.'
• For some 'x.'
• For at least one 'x.‘
– Example: Some boys are intelligent.
• ∃x: boys(x) ∧ intelligent(x)
29
• It will be read as: There are some x where x is a boy who is intelligent.
Some Examples of FOL using quantifier:
– All birds fly.
the predicate is "fly(bird)."
And since there are all birds who fly so it will be represented as follows.
∀x bird(x) →fly(x).
– Every man respects his parent.
the predicate is "respect(x, y)," where x=man, and y= parent.
Since there is every man so will use ∀, and it will be represented as follows:
∀x man(x) → respects (x, parent).
– Some boys play football.
the predicate is "play(x, y)," where x= boys, and y= game. Since there are some boys so we will
use ∃, and it will be represented as:
∃x boys(x) ∧ play(x, football).
– Not all students like both Mathematics and Science.
the predicate is "like(x, y)," where x= student, and y= subject.
Since there are not all students, so we will use ∀ with negation, so following representation for this:
¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)]. 30
 Inference in FOL
• Inference in FOL is used to deduce new facts or sentences from existing sentences
Terminologies:
• Substitution:
– is a fundamental operation performed on terms and formulas.
– It occurs in all inference systems in first-order logic.
– The substitution is complex in the presence of quantifiers in FOL.
– If we write F[a/x], so it refers to substitute a constant "a" in place of variable "x".
• Equality:
– FOL does not only use predicate and terms for making atomic sentences but also uses another way, which
is equality in FOL.
– For this, we can use equality symbols which specify that the two terms refer to the same object.
– Example: Brother (John) = Smith.
• As in the above example, the object referred by the Brother (John) is similar to the object referred by Smith.
• The equality symbol can also be used with negation to represent that two terms are not the same objects.
– Example: ￢ (x=y) which is equivalent to x ≠y.
31
FOL inference rules for quantifier:
• Basic inference rules in FOL are:
– Universal Generalization
– Universal Instantiation
– Existential Instantiation
– Existential introduction

32
 ND
E 33