UNIT – IV

Logic concepts: First order logic. Inference in first order logic, propositional vs. first order
inference, unification & lifts forward chaining, Backward chaining, Resolution, Learning from
observation Inductive learning, Decision trees, Explanation based learning, Statistical Learning
methods, Reinforcement Learning.

First-Order Logic in Artificial intelligence:

In the topic of Propositional logic, we have seen that how to represent statements using
propositional logic. But unfortunately, in propositional logic, we can only represent the facts,
which are either true or false. PL is not sufficient to represent the complex sentences or natural
language statements. The propositional logic has very limited expressive power. Consider the
following sentence, which we cannot represent using PL logic.

"Some humans are intelligent", or

"Sachin likes cricket."

To represent the above statements, PL logic is not sufficient, so we required some more powerful
logic, such as first-order logic.

First-Order logic:

 First-order logic is another way of knowledge representation in artificial intelligence. It is

an extension to propositional logic.
 FOL is sufficiently expressive to represent the natural language statements in a concise
way.
 First-order logic is also known as Predicate logic or First-order predicate logic. First-
order logic is a powerful language that develops information about the objects in a more
easy way and can also express the relationship between those objects.
 First-order logic (like natural language) does not only assume that the world contains facts
like propositional logic but also assumes the following things in the world:

Objects: A, B, people, numbers, colors, wars, theories, squares, 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, ......

As a natural language, first-order logic also has two main parts:

 Syntax
 Semantics

Syntax of First-Order logic:

The syntax of FOL determines which collection of symbols is a logical expression in first-order
logic. The basic syntactic elements of first-order logic are symbols. We write statements in short-
hand notation in FOL.

Basic Elements of First-order logic:

1
Following are the basic elements of FOL syntax:

Atomic sentences:

 Atomic sentences are the most basic sentences of first-order logic. These sentences are
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: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).

Chinky is a cat: => cat (Chinky).

Complex Sentences:

 Complex sentences are made by combining atomic sentences using connectives.

First-order logic statements can be divided into two parts:

 Subject: Subject is the main part of the statement.

 Predicate: A predicate can be defined as a relation, which binds two atoms together in a
statement.

Consider the statement: "x is an integer.", it consists of two parts, the first part x is the subject
of the statement and second part "is an integer," is known as a predicate.

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).

Universal Quantifier:

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.

The Universal quantifier is represented by a symbol ∀, which resembles an inverted A.

Note: 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.
2
Example:

All man drink coffee.

Let a variable x which refers to a cat so all x can be represented in UOD as below:

∀x man(x) → drink (x, coffee).

It will be read as: There are all x where x is a man who drink coffee.

Existential Quantifier:

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. When it is used with a
predicate variable then it is called as an existential quantifier.

Note: 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.

3
 ∃x: boys(x) ∧ intelligent(x)

It will be read as: There are some x where x is a boy who is intelligent.

Points to remember:

The main connective for universal quantifier ∀ is implication →.

The main connective for existential quantifier ∃ is and ∧.



Properties of Quantifiers:

In universal quantifier, ∀x∀y is similar to ∀y∀x.

In Existential quantifier, ∃x∃y is similar to ∃y∃x.


∃x∀y is not similar to ∀y∃x.




Some Examples of FOL using quantifier:

1. All birds fly.

In this question the predicate is "fly(bird)."

∀x bird(x) →fly(x).
And since there are all birds who fly so it will be represented as follows.

2. Every man respects his parent.

Since there is every man so will use ∀, and it will be represented as follows:
In this question, the predicate is "respect(x, y)," where x=man, and y= parent.

∀x man(x) → respects (x, parent).

3. Some boys play cricket.

some boys so we will use ∃, and it will be represented as:

In this question, the predicate is "play(x, y)," where x= boys, and y= game. Since there are

∃x boys(x) → play(x, cricket).

4. Not all students like both Mathematics and Science.

Since there are not all students, so we will use ∀ with negation, so following representation for
In this question, the predicate is "like(x, y)," where x= student, and y= subject.

¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

this:

4
5. Only one student failed in Mathematics.
In this question, the predicate is "failed(x, y)," where x= student, and y= subject.
Since there is only one student who failed in Mathematics, so we will use following

∃(x) [ student(x) → failed (x, Mathematics) ∧∀ (y) [¬(x==y) ∧ student(y) → ¬failed (x,
representation for this:

Mathematics)].

Free and Bound Variables:

The quantifiers interact with variables which appear in a suitable way. There are two types of
variables in First-order logic which are given below:

 Free Variable: A variable is said to be a free variable in a formula if it occurs outside the
scope of the quantifier.

Example: ∀x ∃(y)[P (x, y, z)], where z is a free variable.

 Bound Variable: A variable is said to be a bound variable in a formula if it occurs within

the scope of the quantifier.

Example: ∀x [A (x) B( y)], here x and y are the bound variables.

Inference in First-Order Logic:

Inference in First-Order Logic is used to deduce new facts or sentences from existing sentences.
Before understanding the FOL inference rule, let's understand some basic terminologies used in
FOL.

Substitution:

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".

Note: First-order logic is capable of expressing facts about some or all objects in the universe.

Equality:

First-Order logic 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.

FOL inference rules for quantifier:

5
As propositional logic we also have inference rules in first-order logic, so following are some
basic inference rules in FOL:

 Universal Generalization
 Universal Instantiation
 Existential Instantiation
 Existential introduction

1. Universal Generalization:

any arbitrary element c in the universe of discourse, then we can have a conclusion as ∀ x P(x).
 Universal generalization is a valid inference rule which states that if premise P(c) is true for

 It can be represented as: .

 This rule can be used if we want to show that every element has a similar property.
 In this rule, x must not appear as a free variable.

Example: Let's represent, P(c): "A byte contains 8 bits",

so for ∀ x P(x) "All bytes contain 8 bits.", it will also be true.

2. Universal Instantiation:

 Universal instantiation is also called as universal elimination or UI is a valid inference rule. It

can be applied multiple times to add new sentences.
 The new KB is logically equivalent to the previous KB.
 As per UI, we can infer any sentence obtained by substituting a ground term for the
variable.

constant within domain x) from ∀ x P(x) for any object in the universe of discourse.
 The UI rule state that we can infer any sentence P(c) by substituting a ground term c (a

 It can be represented as: .

Example:1.

IF "Every person like ice-cream"=> ∀x P(x)

so we can infer that "John likes ice-cream" => P(c)

Example: 2.

Let's take a famous example,

"All kings who are greedy are Evil." So let our knowledge base contains this detail as in the form
of FOL:

∀x king(x) ∧ greedy (x) → Evil (x),

So from this information, we can infer any of the following statements using Universal
Instantiation:

 King(John) ∧ Greedy (John) → Evil (John),

6
 King(Richard) ∧ Greedy (Richard) → Evil (Richard),
King(Father(John)) ∧ Greedy (Father(John)) → Evil (Father(John)),



3. Existential Instantiation:

 Existential instantiation is also called as Existential Elimination, which is a valid inference

rule in first-order logic.
 It can be applied only once to replace the existential sentence.
 The new KB is not logically equivalent to old KB, but it will be satisfiable if old KB was

 This rule states that one can infer P(c) from the formula given in the form of ∃x P(x) for a
satisfiable.

new constant symbol c.

 The restriction with this rule is that c used in the rule must be a new term for which P(c ) is
true.

 It can be represented as:

Example:

From the given sentence: ∃x Crown(x) ∧ OnHead(x, John),

So we can infer: Crown(K) ∧ OnHead( K, John), as long as K does not appear in the
knowledge base.

 The above used K is a constant symbol, which is called Skolem constant.

 The Existential instantiation is a special case of Skolemization process.

4. Existential introduction

 An existential introduction is also known as an existential generalization, which is a valid

inference rule in first-order logic.
 This rule states that if there is some element c in the universe of discourse which has a
property P, then we can infer that there exists something in the universe which has the property P.

 It can be represented as:

Example: Let's say that,

"Priyanka got good marks in English."
"Therefore, someone got good marks in English."

Generalized Modus Ponens Rule:

For the inference process in FOL, we have a single inference rule which is called Generalized
Modus Ponens. It is lifted version of Modus ponens.

Generalized Modus Ponens can be summarized as, " P implies Q and P is asserted to be true,
therefore Q must be True."

According to Modus Ponens, for atomic sentences pi, pi', q. Where there is a substitution θ such
that SUBST (θ, pi',) = SUBST(θ, pi), it can be represented as:

7
Example:

We will use this rule for Kings are evil, so we will find some x such that x is king, and x is
greedy so we can infer that x is evil.

1. Here let say, p1' is king(John) p1 is king(x)

2. p2' is Greedy(y) p2 is Greedy(x)
3. θ is {x/John, y/John} q is evil(x)
4. SUBST(θ,q).

What is Unification?

 Unification is a process of making two different logical atomic expressions identical by

finding a substitution. Unification depends on the substitution process.

 Let Ψ1 and Ψ2 be two atomic sentences and 𝜎 be a unifier such that, Ψ1𝜎 = Ψ2𝜎, then it can
 It takes two literals as input and makes them identical using substitution.

be expressed as UNIFY(Ψ1, Ψ2).

Example: Find the MGU for Unify{King(x), King(John)}

Let Ψ1 = King(x), Ψ2 = King(John),

Substitution θ = {John/x} is a unifier for these atoms and applying this substitution, and both
expressions will be identical.

 The UNIFY algorithm is used for unification, which takes two atomic sentences and
returns a unifier for those sentences (If any exist).
 Unification is a key component of all first-order inference algorithms.
 It returns fail if the expressions do not match with each other.
 The substitution variables are called Most General Unifier or MGU.

E.g. Let's say there are two different expressions, P(x, y), and P(a, f(z)).

In this example, we need to make both above statements identical to each other. For this, we will
perform the substitution.

P(x, y)......... (i)

P(a, f(z))......... (ii)

 Substitute x with a, and y with f(z) in the first expression, and it will be represented
as a/x and f(z)/y.
 With both the substitutions, the first expression will be identical to the second expression and
the substitution set will be: [a/x, f(z)/y].

Conditions for Unification:

Following are some basic conditions for unification:

8
  Predicate symbol must be same, atoms or expression with different predicate symbol can
never be unified.
 Number of Arguments in both expressions must be identical.
 Unification will fail if there are two similar variables present in the same expression.

Unification Algorithm:

Algorithm: Unify(Ψ1, Ψ2)

Step. 1: If Ψ1 or Ψ2 is a variable or constant, then:

a) If Ψ1 or Ψ2 are identical, then return NIL.
b) Else if Ψ1is a variable,
a. then if Ψ1 occurs in Ψ2, then return FAILURE
b. Else return { (Ψ2/ Ψ1)}.
c) Else if Ψ2 is a variable,
a. If Ψ2 occurs in Ψ1 then return FAILURE,
b. Else return {( Ψ1/ Ψ2)}.
d) Else return FAILURE.
Step.2: If the initial Predicate symbol in Ψ1 and Ψ2 are not same, then return FAILURE.
Step. 3: IF Ψ1 and Ψ2 have a different number of arguments, then return FAILURE.
Step. 4: Set Substitution set(SUBST) to NIL.
Step. 5: For i=1 to the number of elements in Ψ1.
a) Call Unify function with the ith element of Ψ 1 and ith element of Ψ2, and put the
result into S.
b) If S = failure then returns Failure
c) If S ≠ NIL then do,
a. Apply S to the remainder of both L1 and L2.
b. SUBST= APPEND(S, SUBST).
Step.6: Return SUBST.

Implementation of the Algorithm:

Step.1: Initialize the substitution set to be empty.

Step.2: Recursively unify atomic sentences:

a. Check for Identical expression match.

b. If one expression is a variable vi, and the other is a term ti which does not contain variable vi, then:

c. Substitute ti / vi in the existing substitutions

d. Add ti /vi to the substitution setlist.

e. If both the expressions are functions, then function name must be similar, and the number
of arguments must be the same in both the expression.

For each pair of the following atomic sentences find the most general unifier (If exist).

1. Find the MGU of {p(f(a), g(Y)) and p(X, X)}

Sol: S0 => Here, Ψ1 = p(f(a), g(Y)), and Ψ2 = p(X, X)

SUBST θ= {f(a) / X}

9
 S1 => Ψ1 = p(f(a), g(Y)), and Ψ2 = p(f(a), f(a))
SUBST θ= {f(a) / g(y)},

Unification failed.

Unification is not possible for these expressions.

2. Find the MGU of {p(b, X, f(g(Z))) and p(Z, f(Y), f(Y))}

Here, Ψ1 = p(b, X, f(g(Z))) , and Ψ2 = p(Z, f(Y), f(Y))

S0 => { p(b, X, f(g(Z))); p(Z, f(Y), f(Y))}
SUBST θ={b/Z}

S1 => { p(b, X, f(g(b))); p(b, f(Y), f(Y))}

SUBST θ={f(Y) /X}

S2 => { p(b, f(Y), f(g(b))); p(b, f(Y), f(Y))}

SUBST θ= {g(b) /Y}

S2 => { p(b, f(g(b)), f(g(b)); p(b, f(g(b)), f(g(b))}

Unified Successfully.
And Unifier = { b/Z, f(Y) /X , g(b) /Y}.

3. Find the MGU of {p (X, X), and p (Z, f(Z))}

Here, Ψ1 = {p (X, X), and Ψ2 = p (Z, f(Z))

S0 => {p (X, X), p (Z, f(Z))}
SUBST θ= {X/Z}
S1 => {p (Z, Z), p (Z, f(Z))}
SUBST θ= {f(Z) / Z},

Unification Failed.

Hence, unification is not possible for these expressions.

4. Find the MGU of UNIFY(prime (11), prime(y))

Here, Ψ1 = {prime(11) , and Ψ2 = prime(y)}

S0 => {prime(11) , prime(y)}
SUBST θ= {11/y}

S1 => {prime(11) , prime(11)} ,

Successfully unified.
Unifier: {11/y}.

5. Find the MGU of Q(a, g(x, a), f(y)), Q(a, g(f(b), a), x)}

Here, Ψ1 = Q(a, g(x, a), f(y)), and Ψ2 = Q(a, g(f(b), a), x)

S0 => {Q(a, g(x, a), f(y)); Q(a, g(f(b), a), x)}
SUBST θ= {f(b)/x}
S1 => {Q(a, g(f(b), a), f(y)); Q(a, g(f(b), a), f(b))}
10
SUBST θ= {b/y}
S1 => {Q(a, g(f(b), a), f(b)); Q(a, g(f(b), a), f(b))},

Successfully Unified.

Unifier: [a/a, f(b)/x, b/y].

6. UNIFY(knows(Richard, x), knows(Richard, John))

Here, Ψ1 = knows(Richard, x), and Ψ2 = knows(Richard, John)

S0 => { knows(Richard, x); knows(Richard, John)}
SUBST θ= {John/x}
S1 => { knows(Richard, John); knows(Richard, John)},

Successfully Unified.
Unifier: {John/x}.

Resolution in FOL:

Resolution:

Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs
by contradictions. It was invented by a Mathematician John Alan Robinson in the year 1965.

 Resolution is used, if there are various statements are given, and we need to prove a
conclusion of those statements. Unification is a key concept in proofs by resolutions.
Resolution is a single inference rule which can efficiently operate on the conjunctive
normal form or clausal form.
 Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known as a
unit clause.
 Conjunctive Normal Form: A sentence represented as a conjunction of clauses is said to
be conjunctive normal form or CNF.

Note: To better understand this topic, firstly learns the FOL in AI.

The resolution inference rule:

The resolution rule for first-order logic is simply a lifted version of the propositional rule.
Resolution can resolve two clauses if they contain complementary literals, which are assumed to
be standardized apart so that they share no variables.

Where li and mj are complementary literals.

This rule is also called the binary resolution rule because it only resolves exactly two literals.

Example:

We can resolve two clauses which are given below:

11
 [Animal (g(x) V Loves (f(x), x)] and [￢ Loves(a, b) V ￢Kills(a, b)]

Where two complimentary literals are: Loves (f(x), x) and ￢ Loves (a, b)

These literals can be unified with unifier θ= [a/f(x), and b/x] , and it will generate a resolvent
clause:

[Animal (g(x) V ￢ Kills(f(x), x)].

Steps for Resolution:

1. Conversion of facts into first-order logic.

2. Convert FOL statements into CNF
3. Negate the statement which needs to prove (proof by contradiction)
4. Draw resolution graph (unification).

To better understand all the above steps, we will take an example in which we will apply
resolution.

Example:

a. John likes all kind of food.

b. Apple and vegetable are food
c. Anything anyone eats and not killed is food.
d. Anil eats peanuts and still alive
e. Harry eats everything that Anil eats.
Prove by resolution that:
f. John likes peanuts.

Step-1: Conversion of Facts into FOL:

In the first step we will convert all the given statements into its first order logic.

Step-2: Conversion of FOL into CNF:

In First order logic resolution, it is required to convert the FOL into CNF as CNF form makes
easier for resolution proofs.

[Link] all implication (→) and rewrite: (formula[(a->b)= ¬avb.])

12
a. ∀x ¬ [food(x)] V likes(John, x)

∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)

b. food(Apple) Λ food(vegetables)
c.

∀x ¬ eats(Anil, x) V eats(Harry, x)
d. eats (Anil, Peanuts) Λ alive(Anil)

∀x¬ [¬ killed(x) ] V alive(x)

e.

∀x ¬ alive(x) V ¬ killed(x)
f.
g.
h. likes(John, Peanuts).
[Link] negation (¬)inwards and rewrite:

a. ∀x ¬ food(x) V likes(John, x)

∀x ∀y ¬ eats(x, y) V killed(x) V food(y)

b. food(Apple) Λ food(vegetables)
c.

∀x ¬ eats(Anil, x) V eats(Harry, x)
d. eats (Anil, Peanuts) Λ alive(Anil)

∀x killed(x) V alive(x)
e.

∀x ¬ alive(x) V ¬ killed(x)
f.
g.
h. likes(John, Peanuts).
[Link] variables or standardize variables:

a. ∀x ¬ food(x) V likes(John, x)

∀y ∀z ¬ eats(y, z) V killed(y) V food(z)

b. food(Apple) Λ food(vegetables)
c.

∀w¬ eats(Anil, w) V eats(Harry, w)

d. eats (Anil, Peanuts) Λ alive(Anil)

∀g ¬killed(g) ] V alive(g)
e.

∀k ¬ alive(k) V ¬ killed(k)
f.
g.
h. likes(John, Peanuts).

In this step, we will eliminate existential quantifier ∃, and this process is known
[Link] existential instantiation quantifier by elimination:

as Skolemization. But in this example problem since there is no existential quantifier so all the
statements will remain same in this step.

[Link] Universal quantifiers:

In this step we will drop all universal quantifier since all the statements are not implicitly
quantified so we don't need it.

i. ¬ food(x) V likes(John, x)
j. food(Apple)
k. food(vegetables)
l. ¬ eats(y, z) V killed(y) V food(z)
m. eats (Anil, Peanuts)
n. alive(Anil)
o. ¬ eats(Anil, w) V eats(Harry, w)
p. killed(g) V alive(g)
q. ¬ alive(k) V ¬ killed(k)
r. likes(John, Peanuts).

Note: Statements "food(Apple) Λ food(vegetables)" and "eats (Anil, Peanuts) Λ alive(Anil)" can
be written in two separate statements.

13
[Link] conjunction ∧ over disjunction ¬:
This step will not make any change in this problem.

Step-3: Negate the statement to be proved:

In this statement, we will apply negation to the conclusion statements, which will be written as
¬likes(John, Peanuts)

Step-4: Draw Resolution graph:

Now in this step, we will solve the problem by resolution tree using substitution. For the above
problem, it will be given as follows:

Hence the negation of the conclusion has been proved as a complete contradiction with the given
set of statements.

Explanation of Resolution graph:

 In the first step of resolution graph, ¬likes(John, Peanuts) , and likes(John, x) get
resolved(canceled) by substitution of {Peanuts/x}, and we are left with ¬ food(Peanuts)
 In the second step of the resolution graph, ¬ food(Peanuts) , and food(z) get resolved
(canceled) by substitution of { Peanuts/z}, and we are left with ¬ eats(y, Peanuts) V killed(y) .
 In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get
resolved by substitution {Anil/y}, and we are left with Killed(Anil) .
 In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve by
substitution {Anil/k}, and we are left with ¬ alive(Anil) .
 In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

Forward Chaining and backward chaining in AI

In artificial intelligence, forward and backward chaining is one of the important topics, but before
understanding forward and backward chaining lets first understand that from where these two
terms came.

Inference engine:

The inference engine is the component of the intelligent system in artificial intelligence, which
applies logical rules to the knowledge base to infer new information from known facts. The first
14
 inference engine was part of the expert system. Inference engine commonly proceeds in two
modes, which are:

a. Forward chaining
b. Backward chaining

Horn Clause and Definite clause:

Horn clause and definite clause are the forms of sentences, which enables knowledge base to use a
more restricted and efficient inference algorithm. Logical inference algorithms use forward and
backward chaining approaches, which require KB in the form of the first-order definite clause.

Definite clause: A clause which is a disjunction of literals with exactly one positive literal is
known as a definite clause or strict horn clause.

Horn clause: A clause which is a disjunction of literals with at most one positive literal is
known as horn clause. Hence all the definite clauses are horn clauses.

Example: (¬ p V ¬ q V k). It has only one positive literal k.

It is equivalent to p ∧ q → k.

A. Forward Chaining:

Forward chaining is also known as a forward deduction or forward reasoning method when using
an inference engine. Forward chaining is a form of reasoning which start with atomic sentences in
the knowledge base and applies inference rules (Modus Ponens) in the forward direction to extract
more data until a goal is reached.

 The Forward-chaining algorithm starts from known facts, triggers all rules whose premises
are satisfied, and add their conclusion to the known facts. This process repeats until the
problem is solved.

Properties of Forward-Chaining:

 It is a down-up approach, as it moves from bottom to top.

 It is a process of making a conclusion based on known facts or data, by starting from the
initial state and reaches the goal state.
 Forward-chaining approach is also called as data-driven as we reach to the goal using
available data.
 Forward -chaining approach is commonly used in the expert system, such as CLIPS,
business, and production rule systems.

Consider the following famous example which we will use in both approaches:

Example:1

"As per the law, it is a crime for an American to sell weapons to hostile nations. Country A,
an enemy of America, has some missiles, and all the missiles were sold to it by Robert, who is
an American citizen."

Prove that "Robert is criminal."

15
To solve the above problem, first, we will convert all the above facts into first-order definite
clauses, and then we will use a forward-chaining algorithm to reach the goal.

Facts Conversion into FOL:

 It is a crime for an American to sell weapons to hostile nations. (Let's say p, q, and r are

American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p)

variables)
...(1)

 Country A has some missiles. ?p Owns(A, p) ∧ Missile(p). It can be written in two

definite clauses by using Existential Instantiation, introducing new Constant T1.
Owns(A, T1) ......(2)
Missile(T1) .......(3)

?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)

 All of the missiles were sold to country A by Robert.
......(4)
 Missiles are weapons.
Missile(p) → Weapons (p) .......(5)
 Enemy of America is known as hostile.
Enemy(p, America) →Hostile(p) ........(6)
 Country A is an enemy of America.
Enemy (A, America) .........(7)
 Robert is American
American(Robert). ..........(8)

Forward chaining proof:

Step-1:

In the first step we will start with the known facts and will choose the sentences which do not
have implications, such as: American(Robert), Enemy(A, America), Owns(A, T1), and
Missile(T1). All these facts will be represented as below.

Step-2:

At the second step, we will see those facts which infer from available facts and with satisfied
premises.

Rule-(1) does not satisfy premises, so it will not be added in the first iteration.

Rule-(2) and (3) are already added.

Rule-(4) satisfy with the substitution {p/T1}, so Sells (Robert, T1, A) is added, which infers from
the conjunction of Rule (2) and (3).

Rule-(6) is satisfied with the substitution(p/A), so Hostile(A) is added and which infers from
Rule-(7).
16
Step-3:

At step-3, as we can check Rule-(1) is satisfied with the substitution {p/Robert, q/T1, r/A}, so we
can add Criminal(Robert) which infers all the available facts. And hence we reached our goal
statement.

Hence it is proved that Robert is Criminal using forward chaining approach.

Example:2

Rule 1: If F and B then Z Database(or)Facts: KnowledgeBase:

Rule 2: If C and D then F

F&B ->Z
A
Rule 3: If A then D
E C&D ->F
Goal State:Z B A ->D

17
Problem: Does situation Z exists or not ?
The first rule that fires is A->D because A is already in the database. Next we infer D.
Existence of C and D causes second rule to fire and as a consequence F is inferred and placed
in the database. This in turn, causes the third rule F?B->Z to fire, placing Z in the database.
This technique is called forward chaining.

A very simple Forward chaining Algorithm

Given m facts F1,F2,....,Fm? N RULES
R1,R2,......Rn
repeat
for i ?- 1 to n do
if one or more current facts match the antecedent of Ri then
1 ) add the new fact(s) define by the consequent
2 ) flag the rule that has been fired
3 ) increase m
until no new facts have been produced.

Forward Chaining (Example 3)

Rule 1
IF the car overheats , THEN the car will stall.
Rule 2
IF the car stalls
THEN it will cost me money
AND I will be late getting home
Now, the question is
How do you arrive at conclusion that this situation will cost money and cause you to be late ?
The condition that triggers the chain of events is the car overheating.

B. Backward Chaining:

Backward-chaining is also known as a backward deduction or backward reasoning method when

using an inference engine. A backward chaining algorithm is a form of reasoning, which starts
with the goal and works backward, chaining through rules to find known facts that support the
goal.

Properties of backward chaining:

18
 It is known as a top-down approach.
 Backward-chaining is based on modus ponens inference rule.
 In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts true.
 It is called a goal-driven approach, as a list of goals decides which rules are selected and
used.
 Backward -chaining algorithm is used in game theory, automated theorem proving tools,
inference engines, proof assistants, and various AI applications.
 The backward-chaining method mostly used a depth-first search strategy for proof.

Example:

In backward-chaining, we will use the same above example, and will rewrite all the rules.

 American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)

Owns(A, T1) ........(2)

?p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)

 Missile(T1)
 ......(4)
 Missile(p) → Weapons (p) .......(5)
 Enemy(p, America) →Hostile(p) ........(6)
 Enemy (A, America) .........(7)
 American(Robert). ..........(8)

Backward-Chaining proof:

In Backward chaining, we will start with our goal predicate, which is Criminal(Robert), and then
infer further rules.

Step-1:

At the first step, we will take the goal fact. And from the goal fact, we will infer other facts, and at
last, we will prove those facts true. So our goal fact is "Robert is Criminal," so following is the
predicate of it.

Step-2:

At the second step, we will infer other facts form goal fact which satisfies the rules. So as we can
see in Rule-1, the goal predicate Criminal (Robert) is present with substitution {Robert/P}. So we
will add all the conjunctive facts below the first level and will replace p with Robert.

Here we can see American (Robert) is a fact, so it is proved here.

19
Step-3:t At step-3, we will extract further fact Missile(q) which infer from Weapon(q), as it
satisfies Rule-(5). Weapon (q) is also true with the substitution of a constant T1 at q.

Step-4:

At step-4, we can infer facts Missile(T1) and Owns(A, T1) form Sells(Robert, T1, r) which
satisfies the Rule- 4, with the substitution of A in place of r. So these two statements are proved
here.

20
Step-5:

At step-5, we can infer the fact Enemy(A, America) from Hostile(A) which satisfies Rule- 6.
And hence all the statements are proved true using backward chaining.

Backward Chaining (Example 2):

Rule 1
IF the car is not tuned AND the battery is weak
THEN not enough current will reach the starter.
Rule 2
IF not enough current reaches the starter
21
 THEN the car will not start.

Given facts:
The car is not tuned
The battery is weak.
Now, the question is
How would you arrive at the conditions that have resulted in the car failing to
start?

Backward Chaining(Example 3):

In such a situation backward chaining might be more cost-effective. With this inference
method the system starts with what it wants to prove, e.g., that situation Z exists, and only
executes rules that are relavent to establishing it. Figure following shows how backward
chaining would work using the rules from the forward chaining example.
In step 1 the system is told to establish (if it can) that situation Z exists, It first checks the
data base for Z, and when that fails, searches for rules that conclude Z, i.e., have Z on the right
side of the arrow. It finds the rule F?B->Z, and decides that it must establish F and B in order to
conclude Z.

In step 2 the system tries to establish F, first checking the data base and then finding a rule
that concludes F. From this rule, C?D->F, the system decides it must establish C and D to
conclude F.

In steps 3 through 5 the system finds C in the data base but decides it must establish A
before it can conclude D. It then finds A in the data base.

In steps 6 through 8 the system executes the third rule to establish D, then executes the
second rule to establish the original goal, Z. The inference chain created here is identical to the
one created by forward chaining. The difference in two approaches hinges on the method in
which data and rules are searched.

22
23
Difference between backward chaining and forward chaining.

Following is the difference between the forward chaining and backward chaining:

 Forward chaining as the name suggests, start from the known facts and move forward by
applying inference rules to extract more data, and it continues until it reaches to the goal, whereas
backward chaining starts from the goal, move backward by using inference rules to determine the
facts that satisfy the goal.
 Forward chaining is called a data-driven inference technique, whereas backward chaining is
called a goal-driven inference technique.
 Forward chaining is known as the down-up approach, whereas backward chaining is known
as a top-down approach.
 Forward chaining uses breadth-first search strategy, whereas backward chaining
uses depth-first search strategy.
 Forward and backward chaining both applies Modus ponens inference rule.
 Forward chaining can be used for tasks such as planning, design process monitoring,
diagnosis, and classification, whereas backward chaining can be used for classification and
diagnosis tasks.
 Forward chaining can be like an exhaustive search, whereas backward chaining tries to avoid
the unnecessary path of reasoning.
 In forward-chaining there can be various ASK questions from the knowledge base, whereas
in backward chaining there can be fewer ASK questions.
 Forward chaining is slow as it checks for all the rules, whereas backward chaining is fast as it
checks few required rules only.

24
What is Reinforcement Learning?

 Reinforcement Learning is a feedback-based Machine learning technique in which an

agent learns to behave in an environment by performing the actions and seeing the results
of actions. For each good action, the agent gets positive feedback, and for each bad action,
the agent gets negative feedback or penalty.
 In Reinforcement Learning, the agent learns automatically using feedbacks without any
labeled data, unlike supervised learning.
 Since there is no labeled data, so the agent is bound to learn by its experience only.
 RL solves a specific type of problem where decision making is sequential, and the goal is
long-term, such as game-playing, robotics, etc.
 The agent interacts with the environment and explores it by itself. The primary goal of an
agent in reinforcement learning is to improve the performance by getting the maximum
positive rewards.
 The agent learns with the process of hit and trial, and based on the experience, it learns to
perform the task in a better way. Hence, we can say that "Reinforcement learning is a
type of machine learning method where an intelligent agent (computer program)
interacts with the environment and learns to act within that." How a Robotic dog learns
the movement of his arms is an example of Reinforcement learning.
 It is a core part of Artificial intelligence, and all AI agent works on the concept of
reinforcement learning. Here we do not need to pre-program the agent, as it learns from its
own experience without any human intervention.

Example:

 Suppose there is an AI agent present within a maze environment, and his goal is to find the
diamond. The agent interacts with the environment by performing some actions, and based
on those actions, the state of the agent gets changed, and it also receives a reward or
penalty as feedback.
 The agent continues doing these three things (take action, change state/remain in the
same state, and get feedback), and by doing these actions, he learns and explores the
environment.
25
  The agent learns that what actions lead to positive feedback or rewards and what actions
lead to negative feedback penalty. As a positive reward, the agent gets a positive point,
and as a penalty, it gets a negative point.

Terms used in Reinforcement Learning:

 Agent(): An entity that can perceive/explore the environment and act upon it.
 Environment(): A situation in which an agent is present or surrounded by. In RL, we
assume the stochastic environment, which means it is random in nature.
 Action(): Actions are the moves taken by an agent within the environment.
 State(): State is a situation returned by the environment after each action taken by the
agent.
 Reward(): A feedback returned to the agent from the environment to evaluate the action
of the agent.
 Policy(): Policy is a strategy applied by the agent for the next action based on the current
state.
 Value(): It is expected long-term retuned with the discount factor and opposite to the
short-term reward.
 Q-value(): It is mostly similar to the value, but it takes one additional parameter as a
current action (a).

Key Features of Reinforcement Learning:

 In RL, the agent is not instructed about the environment and what actions need to be taken.
 It is based on the hit and trial process.
 The agent takes the next action and changes states according to the feedback of the
previous action.
 The agent may get a delayed reward.
 The environment is stochastic, and the agent needs to explore it to reach to get the
maximum positive rewards.

Approaches to implement Reinforcement Learning:

There are mainly three ways to implement reinforcement-learning in ML, which are:

1. Value-based:
The value-based approach is about to find the optimal value function, which is the
maximum value at a state under any policy. Therefore, the agent expects the long-term
return at any state(s) under policy π.
2. Policy-based:
Policy-based approach is to find the optimal policy for the maximum future rewards
26
 without using the value function. In this approach, the agent tries to apply such a policy
that the action performed in each step helps to maximize the future reward.
The policy-based approach has mainly two types of policy:
 Deterministic: The same action is produced by the policy (π) at any state.
 Stochastic: In this policy, probability determines the produced action.

1. Model-based: In the model-based approach, a virtual model is created for the

environment, and the agent explores that environment to learn it. There is no particular solution or
algorithm for this approach because the model representation is different for each environment.

Elements of Reinforcement Learning:

There are four main elements of Reinforcement Learning, which are given below:

1. Policy
2. Reward Signal
3. Value Function
4. Model of the environment

1) Policy: A policy can be defined as a way how an agent behaves at a given time. It maps the
perceived states of the environment to the actions taken on those states. A policy is the core
element of the RL as it alone can define the behavior of the agent. In some cases, it may be a
simple function or a lookup table, whereas, for other cases, it may involve general computation as
a search process. It could be deterministic or a stochastic policy:

For deterministic policy: a = π(s)

For stochastic policy: π(a | s) = P[At =a | St = s]

2) Reward Signal: The goal of reinforcement learning is defined by the reward signal. At each
state, the environment sends an immediate signal to the learning agent, and this signal is known as
a reward signal. These rewards are given according to the good and bad actions taken by the
agent. The agent's main objective is to maximize the total number of rewards for good actions.
The reward signal can change the policy, such as if an action selected by the agent leads to low
reward, then the policy may change to select other actions in the future.

3) Value Function: The value function gives information about how good the situation and action
are and how much reward an agent can expect. A reward indicates the immediate signal for each
good and bad action, whereas a value function specifies the good state and action for the
future. The value function depends on the reward as, without reward, there could be no value.
The goal of estimating values is to achieve more rewards.

4) Model: The last element of reinforcement learning is the model, which mimics the behavior of
the environment. With the help of the model, one can make inferences about how the environment
will behave. Such as, if a state and an action are given, then a model can predict the next state and
reward.

The model is used for planning, which means it provides a way to take a course of action by
considering all future situations before actually experiencing those situations. The approaches for
solving the RL problems with the help of the model are termed as the model-based approach.
Comparatively, an approach without using a model is called a model-free approach.

How does Reinforcement Learning Work?

27
To understand the working process of the RL, we need to consider two main things:

 Environment: It can be anything such as a room, maze, football ground, etc.

 Agent: An intelligent agent such as AI robot.

Let's take an example of a maze environment that the agent needs to explore. Consider the below
image:

In the above image, the agent is at the very first block of the maze. The maze is consisting of an
S6 block, which is a wall, S8 a fire pit, and S4 a diamond block.

 The agent cannot cross the S6 block, as it is a solid wall. If the agent reaches the S 4 block,
then get the +1 reward; if it reaches the fire pit, then gets -1 reward point. It can take
four actions: move up, move down, move left, and move right.
 The agent can take any path to reach to the final point, but he needs to make it in possible
fewer steps. Suppose the agent considers the path S9-S5-S1-S2-S3, so he will get the +1-
reward point.
 The agent will try to remember the preceding steps that it has taken to reach the final step.
To memorize the steps, it assigns 1 value to each previous step. Consider the below step:

Now, the agent has successfully stored the previous steps assigning the 1 value to each previous
block. But what will the agent do if he starts moving from the block, which has 1 value block on
both sides? Consider the below diagram:

28
It will be a difficult condition for the agent whether he should go up or down as each block has the
same value. So, the above approach is not suitable for the agent to reach the destination. Hence to
solve the problem, we will use the Bellman equation, which is the main concept behind
reinforcement learning.

The Bellman Equation:

The Bellman equation was introduced by the Mathematician Richard Ernest Bellman in the
year 1953, and hence it is called as a Bellman equation. It is associated with dynamic
programming and used to calculate the values of a decision problem at a certain point by
including the values of previous states.

It is a way of calculating the value functions in dynamic programming or environment that leads
to modern reinforcement learning.

The key-elements used in Bellman equations are:

 Action performed by the agent is referred to as "a"

 State occurred by performing the action is "s."
 The reward/feedback obtained for each good and bad action is "R."
 A discount factor is Gamma "γ."

The Bellman equation can be written as:

1. V(s) = max [R(s,a) + γV(s`)]

Where,

V(s)= value calculated at a particular point.

R(s,a) = Reward at a particular state s by performing an action.

γ = Discount factor

V(s`) = The value at the previous state.

In the above equation, we are taking the max of the complete values because the agent tries to find
the optimal solution always.

29
So now, using the Bellman equation, we will find value at each state of the given environment.
We will start from the block, which is next to the target block.

For 1st block:

V(s3) = max [R(s,a) + γV(s`)], here V(s')= 0 because there is no further state to move.

V(s3)= max[R(s,a)]=> V(s3)= max[1]=> V(s3)= 1.

For 2nd block:

V(s2) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 1, and R(s, a)= 0, because there is no
reward at this state.

V(s2)= max[0.9(1)]=> V(s)= max[0.9]=> V(s2) =0.9

For 3rd block:

V(s1) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.9, and R(s, a)= 0, because there is no
reward at this state also.

V(s1)= max[0.9(0.9)]=> V(s3)= max[0.81]=> V(s1) =0.81

For 4th block:

V(s5) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.81, and R(s, a)= 0, because there is no
reward at this state also.

V(s5)= max[0.9(0.81)]=> V(s5)= max[0.81]=> V(s5) =0.73

For 5th block:

V(s9) = max [R(s,a) + γV(s`)], here γ= 0.9(lets), V(s')= 0.73, and R(s, a)= 0, because there is no
reward at this state also.

V(s9)= max[0.9(0.73)]=> V(s4)= max[0.81]=> V(s4) =0.66

Consider the below image:

30
Now, we will move further to the 6 th block, and here agent may change the route because it always
tries to find the optimal path. So now, let's consider from the block next to the fire pit.

Now, the agent has three options to move; if he moves to the blue box, then he will feel a bump if
he moves to the fire pit, then he will get the -1 reward. But here we are taking only positive
rewards, so for this, he will move to upwards only. The complete block values will be calculated
using this formula. Consider the below image:

Types of Reinforcement learning:

There are mainly two types of reinforcement learning, which are:

 Positive Reinforcement
 Negative Reinforcement

Positive Reinforcement:

 The positive reinforcement learning means adding something to increase the tendency that
expected behavior would occur again. It impacts positively on the behavior of the agent
and increases the strength of the behavior.
 This type of reinforcement can sustain the changes for a long time, but too much positive
reinforcement may lead to an overload of states that can reduce the consequences.

Negative Reinforcement:

 The negative reinforcement learning is opposite to the positive reinforcement as it

increases the tendency that the specific behavior will occur again by avoiding the negative
condition.

31
  It can be more effective than the positive reinforcement depending on situation and
behavior, but it provides reinforcement only to meet minimum behavior.

Reinforcement Learning Applications:

[Link]:

RL is used in Robot navigation, Robo-soccer, walking, juggling, etc.

[Link]:

RL can be used for adaptive control such as Factory processes, admission control in
telecommunication, and Helicopter pilot is an example of reinforcement learning.

[Link] Playing:

RL can be used in Game playing such as tic-tac-toe, chess, etc.

[Link]:

RL can be used for optimizing the chemical reactions.

[Link]:

RL is now used for business strategy planning.

[Link]:

In various automobile manufacturing companies, the robots use deep reinforcement learning to
pick goods and put them in some containers.

[Link] Sector:

The RL is currently used in the finance sector for evaluating trading strategies.

Conclusion:

From the above discussion, we can say that Reinforcement Learning is one of the most interesting
and useful parts of Machine learning. In RL, the agent explores the environment by exploring it
without any human intervention. It is the main learning algorithm that is used in Artificial
32
Intelligence. But there are some cases where it should not be used, such as if you have enough
data to solve the problem, then other ML algorithms can be used more efficiently. The main issue
with the RL algorithm is that some of the parameters may affect the speed of the learning, such as
delayed feedback.

LEARNING FROM OBSERVATIONS:

Introduction:

What is learning?

 Learning denotes changes in the system that are adaptive in the sense that they enable
the system to do the same task or tasks drawn from the same population more
effectively the next time (Simon, 1983).
 Learning is making useful changes in our minds (Minsky, 1985).
 Learning is constructing or modifying representations of what is being experienced

(Michalski, 1986).

 A computer program learns if it improves its performance at some task through

experience

(Mitchell, 1997).

So what is learning?

(1) acquire and organize knowledge (by building, modifying and organizing internal
representations of some external reality);

(2) discover new knowledge and theories (by creating hypotheses that explain some data
or phenomena);

(3) acquire skills (by gradually improving their motor or cognitive skills through repeated
practice,

sometimes involving little or no conscious thought).

(4) Learning results in changes in the agent (or mind) that improve its competence and/or
efficiency.

(5) Learning is essential for unknown environments, (1) i.e., when designer lacks
omniscience

 Learning is useful as a system construction method,

 Expose the agent to reality rather than trying to write it down
 Learning modifies the agent's decision mechanisms to improve performance

FORMS OF LEARNING:

Learning agents:

33
  Four Components:

1. Performance Element: collection of knowledge and procedures to decide on the next action

E.g. walking, turning, drawing, etc.

[Link] Element: takes in feedback from the critic and modifies the performance element
accordingly.

3. Critic: provides the learning element with information on how well the agent is doing based
on a fixed performance standard. E.g. the audience

[Link] Generator: provides the performance element with suggestions on new actions to
take. Components of the Performance Element

• A direct mapping from conditions on the current state to actions

• Information about the way the world evolves

• Information about the results of possible actions the agent can take

• Utility information indicating the desirability of world states

Learning element

• Design of a learning element is affected by

–Which components of the performance element are to be learned

–What feedback is available to learn these components

–What representation is used for the components

34
Type of feedback:

–Supervised learning: correct answers for each example

–Unsupervised learning: correct answers not given

–Reinforcement learning: occasional rewards

INDUCTIVE LEARNING:

Inductive Learning in supervised learning we have a set of {xi, f (xi)} for 1≤i≤n, and our aim is to
determine 'f' by some adaptive algorithm. It is a machine learning approach in which rules are
inferred from facts or data. In logic, reasoning from the specific to the general Conditional or
antecedent reasoning. Theoretical results in machine learning mainly deal with a type of inductive
learning called supervised learning. In supervised learning, an algorithm is given samples that are
labeled in some useful way. In case of inductive learning algorithms, like artificial neural
networks, the real robot may learn only from previously gathered data. Another option is to let the
bot learn everything around him by inducing facts from the environment. This is known as
inductive learning. Finally, you could get the bot to evolve, and optimise his performance over
several generations.

f(x) is the target function

An example is a pair [x, f(x)]

Learning task: find a hypothesis h such that h(x)

1.F(x) gives a training set of examples D = {[xi, f(xi) ]}, i = 1,2,…,N Construct h so that it agrees
with f.

[Link] hypothesis h is consistent if it agrees with f on all observations.

Ockham’s razor: Select the simplest consistent hypothesis.

How achieve good generalization?

35
Simplest: Construct a decision tree with one leaf for every example = memory based
learning. Not very good generalization.

Advanced: Split on each variable so that the purity of each split increases (i.e. either only yes
or only no)

DECISION TREE LEARNING:

INTRODUCTION:

 Decision Tree is a Supervised learning technique that can be used for both classification
and Regression problems, but mostly it is preferred for solving Classification problems. It
is a tree-structured classifier, where internal nodes represent the features of a dataset,
branches represent the decision rules and each leaf node represents the outcome.
 In a Decision tree, there are two nodes, which are the Decision Node and Leaf Node.
Decision nodes are used to make any decision and have multiple branches, whereas Leaf
nodes are the output of those decisions and do not contain any further branches.
 The decisions or the test are performed on the basis of features of the given dataset.
 It is a graphical representation for getting all the possible solutions to a problem/decision
based on given conditions.
 It is called a decision tree because, similar to a tree, it starts with the root node, which
expands on further branches and constructs a tree-like structure.
 In order to build a tree, we use the CART algorithm, which stands for Classification and
Regression Tree algorithm.
 A decision tree simply asks a question, and based on the answer (Yes/No), it further split
the tree into sub trees.

36
APPROPRIATE PROBLEMS FOR DECISION TREE LEARNING :

Decision tree learning is generally best suited to problems with the following characteristics:

1. Instances are represented by attribute-value pairs – Instances are described by a fixed set of
attributes and their values

2. The target function has discrete output values – The decision tree assigns a Boolean
classification (e.g., yes or no) to each example. Decision tree methods easily extend to learning
functions with more than two possible output values.

3. Disjunctive descriptions may be required -Decision trees naturally represent disjunctive

expressions.

4. The training data may contain errors – Decision tree learning methods are robust to errors, both
errors in classifications of the training examples and errors in the attribute values that describe
these examples.

5. The training data may contain missing attribute values – Decision tree methods can be used
even when some training examples have unknown values

THE BASIC DECISION TREE LEARNING ALGORITHM:

The basic algorithm is ID3 which learns decision trees by constructing them top-down

ID3(Examples, Target_attribute, Attributes)

Examples are the training examples. Target_attribute is the attribute whose value is tobe
predicted by the tree. Attributes is a list of other attributes that may be tested by the learned
decision tree. Returns a decision tree that correctly classifies the given Examples.

• Create a Root node for the tree

• If all Examples are positive, Return the single-node tree Root, with label = +

• If all Examples are negative, Return the single-node tree Root, with label = -

37
• If Attributes is empty, Return the single-node tree Root, with label = most common value of
Target_attribute in Examples

• Otherwise Begin

• A ← the attribute from Attributes that best* classifies Examples

• The decision attribute for Root ← A

• For each possible value, vi, of A,

• Add a new tree branch below Root, corresponding to the test A = vi

• Let Examples vi, be the subset of Examples that have value vi for A

• If Examples vi , is empty

• Then below this new branch add a leaf node with label = most common value of
Target_attribute in Examples

• Else below this new branch add the subtree ID3(Examples vi, Targe_tattribute,
Attributes – {A}))

• End

• Return Root

* The best attribute is the one with highest information gain

TABLE: Summary of the ID3 algorithm specialized to learning Boolean-valued functions. ID3 is
a greedy algorithm that grows the tree top-down, at each node selecting the attribute that best
classifies the local training examples. This process continues until the tree perfectly classifies the
training examples, or until all attributes have been used

Which Attribute Is the Best Classifier?

• The central choice in the ID3 algorithm is selecting which attribute to test at each node in the
tree.

• A statistical property called information gain that measures how well a given attribute separates
the training examples according to their target classification.

• ID3 uses information gain measure to select among the candidate attributes at each step while
growing the tree.

ENTROPY MEASURES HOMOGENEITY OF EXAMPLES:

To define information gain, we begin by defining a measure called entropy. Entropy measures the
impurity of a collection of examples.

Given a collection S, containing positive and negative examples of some target concept, the
entropy of S relative to this Boolean classification is

38
Where, p+ is the proportion of positive examples in S

p-is the proportion of negative examples in S.

The entropy is 0 if all members of S belong to the same class

• The entropy is 1 when the collection contains an equal number of positive and negative
examples

• If the collection contains unequal numbers of positive and negative examples, the entropy is
between 0 and 1

INFORMATION GAIN MEASURES THE EXPECTED REDUCTION IN ENTROPY:

• Information gain, is the expected reduction in entropy caused by partitioning the examples
according to this attribute.

• The information gain, Gain(S, A) of an attribute A, relative to a collection of examples S, is

defined as

An Illustrative Example:

• To illustrate the operation of ID3, consider the learning task represented by the training
examples of below table.

• Here the target attribute PlayTennis, which can have values yes or no for different days.

• Consider the first step through the algorithm, in which the topmost node of the decision tree is
created.

39
• ID3 determines the information gain for each candidate attribute (i.e., Outlook, Temperature,
Humidity, and Wind), then selects the one with highest information gain.

[Link]=outlook:

s=[9+,5-]

Entropy(s)=-[ 9/14 log2 9/14 - 5/14 log2 5/14 ]

= 0.409+0.530 = 0.940

values(outlook)=sunny,rain,overcast

[Link]:(s sunny)=[2+,3-]

entropy(s sunny)=-[2/5 log2 2/5 -3/5 log2 3/5 ]

=0.970

[Link]:(s overcast)=[4+,0-]

entropy(s overcast)=-[4/4 log2 4/4 - 0/4 log2 0/4 ]

=0

[Link]:(s rain)=[3+,2-]

entropy(s rain)=-[3/5 log2 3/5 - 2/5 log2 2/5 ]

=0.970

I.G(s,outlook)=entropy(s)-5/14entropy(s sunny)-5/14entropy(s rain)-4/14entropy(s overcast)

=0.246

we have to perform the same process for temperature, humidity, wind and find their information
gain values.

• The information gain values for all four attributes are

40
Gain(S, Outlook) = 0.246

Gain(S, Humidity) = 0.151

Gain(S, Wind) = 0.048

Gain(S, Temperature) = 0.029

• According to the information gain measure, the Outlook attribute provides the best prediction of
the target attribute, PlayTennis, over the training examples. Therefore, Outlook is selected as the
decision attribute for the root node, and branches are created below the root for each of its
possible values i.e., Sunny, Overcast, and Rain.

41
 Rain Mild High Strong No

so, this is the final decision tree.

THE BASIC DECISION TREE LEARNING ALGORITHM:

42
Decision Tree algorithm belongs to the family of supervised learning algorithms. Unlike other
supervised learning algorithms, the decision tree algorithm can be used for solving regression
and classification problems too.

The goal of using a Decision Tree is to create a training model that can use to predict the class
or value of the target variable by learning simple decision rules inferred from prior
data(training data).

In Decision Trees, for predicting a class label for a record we start from the root of the tree. We
compare the values of the root attribute with the record’s attribute. On the basis of comparison,
we follow the branch corresponding to that value and jump to the next node.

Types of Decision Trees:

Types of decision trees are based on the type of target variable we have. It can be of two types:

1. Categorical Variable Decision Tree: Decision Tree which has a categorical target variable
then it called a Categorical variable decision tree.

2. Continuous Variable Decision Tree: Decision Tree has a continuous target variable then it
is called Continuous Variable Decision Tree.

Example:- Let’s say we have a problem to predict whether a customer will pay his renewal
premium with an insurance company (yes/ no). Here we know that the income of customers is a
significant variable but the insurance company does not have income details for all customers.
Now, as we know this is an important variable, then we can build a decision tree to predict
customer income based on occupation, product, and various other variables. In this case, we are
predicting values for the continuous variables.

Important Terminology related to Decision Trees :

1. Root Node: It represents the entire population or sample and this further gets divided into
two or more homogeneous sets.

2. Splitting: It is a process of dividing a node into two or more sub-nodes.

3. Decision Node: When a sub-node splits into further sub-nodes, then it is called the decision
node.

4. Leaf / Terminal Node: Nodes do not split is called Leaf or Terminal node.

5. Pruning: When we remove sub-nodes of a decision node, this process is called pruning. You
can say the opposite process of splitting.

6. Branch / Sub-Tree: A subsection of the entire tree is called branch or sub-tree.

7. Parent and Child Node: A node, which is divided into sub-nodes is called a parent node of
sub-nodes whereas sub-nodes are the child of a parent node.

43
Decision trees classify the examples by sorting them down the tree from the root to some
leaf/terminal node, with the leaf/terminal node providing the classification of the example.

Each node in the tree acts as a test case for some attribute, and each edge descending from the
node corresponds to the possible answers to the test case. This process is recursive in nature
and is repeated for every sub tree rooted at the new node.

EXPLANATION BASED LEARNING:

Explanation-based learning in artificial intelligence is a branch of machine learning that

focuses on creating algorithms that learn from previously solved problems. It is a problem-
solving method that is especially helpful when dealing with complicated, multi-faceted issues
that necessitate a thorough grasp of the underlying processes.

INTRODUCTION

Since its beginning, machine learning has come a long way. While early machine-learning
algorithms depended on statistical analysis to spot patterns and forecast outcomes,
contemporary machine-learning models are intended to learn from subject experts'
explanations. Explanation-based learning in artificial intelligence has proven to be a potent tool
in its development that can handle complicated issues more efficiently.

What is Explanation-Based Learning?

Explanation-based learning in artificial intelligence is a problem-solving method that involves

agent learning by analyzing specific situations and connecting them to previously acquired
information. Also, the agent applies what he has learned to solve similar issues. Rather than
relying solely on statistical analysis, EBL algorithms incorporate logical reasoning and domain
knowledge to make predictions and identify patterns.

Explanation-based learning architecture:

44
The environment provides two inputs to the EBL architecture:

1. A specific goal, and

2. A partial solution.

The problem solver analyses these sources and provides reasoning to the generalizer.

The generalizer uses general ideas from the knowledge base as input and compares them to the
problem solver's reasoning to come up with an answer to the given problem.

Explanation-based learning System Representation:

 Problem Solver: It takes 3 kinds of external inputs: The goal idea is a complex
problem statement that the agent must learn. Training instances are facts that illustrate a
specific instance of a target idea. Inference rules reflect facts and procedures that
demonstrate what the learner already understands.
 Generalizer: The problem solver's output is fed into the generalizer, which compares
the problem solver's explanation to the knowledge base and outputs to the operational
pruner.
 Operational pruner: It takes two inputs, one from generalized and the other from
operationally standard. The operational standard describes the final concept and defines
the format in which the learned concept should be conveyed.

a) The Explanation-Based Learning Hypothesis

45
According to the Explanation based learning hypothesis, if a system has an explanation for how
to tackle a comparable problem it faced previously, it will utilize that explanation to handle the
current problem more efficiently. This hypothesis is founded on the concept that learning via
explanations is more successful than learning through instances alone.

b) Standard Approach to Explanation-Based Learning

The typical approach to explanation-based learning in artificial intelligence entails the

following steps:

1. Determine the problem to be solved

2. Gather samples of previously solved problems that are comparable to the current
problem.
3. Identify the connections between the previously solved problems and the new problem.
4. Extraction of the underlying principles and rules used to solve previously solved
problems.
5. Apply the extracted rules and principles to solve the new problem.

c) Examples of Explanation-Based Learning

 Medical Diagnosis: Explanation-based learning can be used in medical diagnosis to

determine the underlying causes of a patient's symptoms. Explanation-based learning
algorithms can find trends and produce more accurate diagnoses by analyzing
previously diagnosed instances.
 Robot Navigation: Explanation-based learning may be used to educate robots on how
to navigate through complicated settings. Explanation-based learning algorithms can
discover the rules and principles that were utilized to navigate those settings and apply
them to new scenarios by analyzing prior successful navigation efforts.
 Fraud Detection: Explanation-based learning may be utilized in fraud detection to
discover patterns of fraudulent conduct. Explanation-based learning algorithms can find
the rules and principles that were utilized to detect prior cases of fraud and apply them
to new cases by analyzing previous incidents of fraud.

Conclusion

 Explanation-based learning in artificial intelligence is a powerful tool for solving

complex problems efficiently.
 By learning from explanations provided by domain experts, EBL algorithms can
identify the underlying principles and rules that govern a particular domain and apply
them to new situations.
 Explanation-based learning in the artificial intelligence approach has a wide range of
applications, from medical diagnosis to fraud detection, and is poised to play an
increasingly important role in the development of advanced AI systems.

STATISTICAL LEARNING METHODS:

Learn probabilistic theories of the world from experience:

♦ We focus on the learning of Bayesian networks

♦ More specifically, input data (or evidence), learn probabilistic theories of the world (or
hypotheses)
46
View learning as Bayesian updating of a probability distribution over the hypothesis space

H is the hypothesis variable, values h1, h2, . . ., prior P(H) jth observation dj gives the outcome
of random variable Dj training data d = d1, . . . , dN

Given the data so far, each hypothesis has a posterior probability:

P(hi|d) = αP(d|hi)P(hi)

where P(d|hi) is called the likelihood

Predictions use a likelihood-weighted average over all hypotheses:

P(X|d) = Σi P(X|d, hi)P(hi|d) = Σi P(X|hi)P(hi|d)

Example

Suppose there are five kinds of bags of candies: 10% are h1: 100% cherry candies

20% are h2: 75% cherry candies + 25% lime candies 40% are h3: 50% cherry candies + 50%
lime candies 20% are h4: 25% cherry candies + 75% lime candies 10% are h5: 100% lime
candies

Then we observe candies drawn from some bag:

What kind of bag is it? What flavour will the next candy be?

[Link] true hypothesis eventually dominates the Bayesian prediction given that the true
hypothesis is in the prior

[Link] Bayesian prediction is optimal, whether the data set be small or large[?]

On the other hand

[Link] hypothesis space is usually very large or infinite summing over the hypothesis space is
often intractable.

[Link] when the hypothesis space is too expressive such that some hypotheses fit the
date set well.

[Link] prior to penalize complexity.

47