[go: up one dir, main page]
Scribd
Upload
496 views22 pages

6.induction As Inverted Deduction

Uploaded by

Shiva L
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
496 views22 pages

6.induction As Inverted Deduction

Uploaded by

Shiva L
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 22

Content::

Induction as inverted deduction


Induction and Deduction
A second approach to inductive logic programming is based
on the simple observation that induction is just the inverse
of deduction.
machine learning involves building theories that explain the
observed data.
Induction is, in fact, the inverse operation of deduction, and
cannot be conceived to exist without the corresponding
operation, so that the question of relative importance
cannot arise.
The significance of Equation is that it casts the learning problem in the
framework of deductive inference and formal logic.
In the case of propositional and first-order logics, there exist well-
understood algorithms for automated deduction.
Induction as Inverted
Deduction
Induction is finding h such that
(<xi,f(xi)>  D) B  h  xi |– f(xi)
where
xi is the ith training instance
f(xi) is the target function value for xi
B is other background knowledge

So let’s design inductive algorithms by inverting operators for


automated deduction!
Induction as Inverted
Deduction
Positives:
Subsumes earlier idea of finding h that “fits” training data
Domain theory B helps define meaning of “fit” the data
B  h  xi |– f(xi)
Suggests algorithms that search H guided by B

Negatives:
Doesn’t allow for noisy data. Consider
(<xi,f(xi)>  D) B  h  xi |– f(xi)
First order logic gives a huge hypothesis space H
◦ overfitting…
◦ intractability of calculating all acceptable h’s
Induction as Inverted
Deduction
“pairs of people, <u,v> such that child of u is v,”

f(xi) : Child(Bob,Sharon)
xi : Male(Bob),Female(Sharon),Father(Sharon,Bob)
B : Parent(u,v)  Father(u,v)

What satisfies (<xi,f(xi)>  D) B  h  xi |– f(xi)?


h1 : Child(u,v)  Father(v,u)
h2 : Child(u,v)  Parent(v,u)
Induction as Inverted
Deduction
We have mechanical deductive operators
F(A,B) = C, where A  B |– C

need inductive operators


O(B,D) = h where
(<xi,f(xi)>  D) B  h  xi |– f(xi)
INVERTING RESOLUTION
A general method for automated deduction is the resolution rule
introduced by Robinson (1965).
The resolution rule is a sound and complete rule for deductive inference
in first-order logic. Therefore, it is sensible to ask whether we can invert
the resolution rule to form an inverse entailment operator. The answer
is yes, and it is just this operator that forms the basis of the CIGOL
program introduced by Muggleton and Buntine (1988)
Resolution operator (propositional form). Given
clauses C1 and C2, the resolution operator constructs
a clause C such that C1 and C2 implies C.
Deduction : Resolution Rule
P  L
L  R
P  R

1. Given initial clauses C1 and C2, find a literal L from clause


C1 such that L occurs in clause C2.
2.Form the resolvent C by including all literals from C1 and C2,
except for L and L.
C = (C1 - {L})  (C2 - {L })
Inverting Resolution
C1: PassExam  ¬KnowMaterial C2: KnowMaterial  ¬Study

C: PassExam  ¬Study
Inverted Resolution
(Propositional)
1. Given initial clauses C1 and C, find a literal L that occurs in clause C1,
but not in clause C.

2. Form the second clause C2 by including the following literals

C2 = (C - (C1 - {L}))  {¬ L}
Induction As Inverted Deduction (1)
Induction is Finding h such that

( xi , f (xi )  D) (B  h  xi )ㅏ f (xi )


where
◦ xi is ith training instance
◦ f(xi) is target function value for xi
◦ B is other background knowledge
Induction As Inverted Deduction (2)
Designing Inverse Entailment Operators
O(B, D) = h such that
( xi , f (xi )  D) (B  h  xi )ㅏ f (xi )
Minimum Description Length Principle
◦ to choose hypothesis among hypotheses which satisfying

( xi , f (xi )  D) (B  h  xi )ㅏ f (xi )


Practical Difficulty
◦ Do not Allow Noisy Training Data
◦ No. of Hypotheses satisfying
is so large (xi , f (xi ) D) (B  h  xi )ㅏf (xi )
◦ Complexity of Hypothesis Space Increases as B is Increased.
Inverse Resolution Operator
Not Deterministic
◦ Multiple C2 such that C1 and C2 produce C
◦ Prefer Shorter One

1. Given initial clause C1 and C, find a literal L that occurs in


C1, but not in C2.
2. Form the second clause C2 by including the following
literals
C2 = (C - (C1 - {L})  {L }

You might also like