Transcript Document

Another example of recursive
learning:
E+:
boss(mary,john). boss(phil,mary).boss(phil,john).
E-:
boss(john,mary). boss(mary,phil). boss(john,phil).
BK:
employee(john, ibm). employee(mary,ibm). employee(phil,ibm).
reports_to_imm(john,mary). reports_to_imm(mary,phil).
h: boss(X,Y):-
employee(X,O), employee(Y,O),reports_to(Y, X).
reports_to(X,Y):-reports_to_imm(X,Z), reports_to(Z,Y).
reports_to(X,X).
1
How is learning done: covering algorithm
Initialize the training set T to all k-tuples of constants
while the global training set contains + tuples:
find a clause that describes part of relationship Q
remove the +tuples covered by this clause
Finding a clause:
initialize the clause to Q(V1,…Vk) :while T contains –tuples
find a literal L to add to the right-hand side of the
clause
Finding a literal : greedy search
2
• ‘Find a clause’ loop describes search –
bottom up or top down –
• Need to structure the search space
– generality – semantic and syntactic
• since logical generality is not decidable, a
stronger property of -subsumption
• then search from general to specific
(refinement)
3
Refinement
Heuristics:
link to head
new variables
boss(X,Y):-
boss(X,Y):-empl(X,O).
boss(X,Y):-X=Y
…
boss(X,Y):-reports_to(X,Y).
…
boss(X,Y):-empl(X,O),empl(Y,O1).
boss(X,Y):-empl(X,O),empl(Y,O).
boss(X,Y):empl(X,O),empl(Y,O),rep_to(Y,X).
boss(X,Y):empl(X,O),empl(Y,O),rep_to(X,Y).
4
How is learning done: covering
algorithm
• Inner loop describes search – bottom up and
top down - we do the latter
• Need to structure the search space –
generality – semantic and syntactic – theta
subs.
5
Constructive learning
•
•
•
•
Do we really learn something new?
Hypotheses are in the same language as examples
constructive induction
How do we learn multiplication from examples? We
need to invent plus –we have shown [IJCAI93] that
true constructivism requires recursion, i.e. in
mult(X,s(Y),Z) :- mult(X,Y,T), newp(T,Y,Z)
mult(X,0) :- 0.
• Newp – plus - must be recursive.
6
Philosophical motivation
• Constructive induction is analogical to “revolution” in the
methodology of science
• Kuhn’s Structure of Scientific Revolution:
normal science -> crisis -> revolution -> normal science
• Normal science = learning a “theory” in a fixed language
• Crisis = failure to cope with anomalies observed, due to
inadequate language
• Revolution = introduction of new terms into the language
(cannot be done in AV)
7
Example: predicting colour in flowers
• Language: r, y; a is any red flower, b is any yellow
flower; col(X,Y) X is of colour Y; ch(X,Y) = result of
breeding of X and Y
• Observations (that Czech monk and his peas…)
1. col(a,r) % Adam and Eve
2. col(b,y).
3. col(ch(a,a),r). % first generation
4. col(ch(a,b),r).
5. col(ch(b,b),b).
6. col(ch(a,ch(b,b),r).%original and 1st
7. …
8. col(ch(ch(a,b)ch(a,b),y). 1st and 1st
9. ….
10.:-col(ch(a,a),y).
8
col(ch(a,X),r).
col(ch(X,Y),a) :- col(X,r), col(Y,r).
col(ch(b,b),y).
col(ch(X,Y), y) :- col(X,y),col(Y,y).
• But in some generations y and r
produce r, and in some – y
• We need either infinitely many clauses,
or infinitely long clauses
• A revolution is necessary
9
A new necessary predicate is invented
• n00 represents purebred flowers with
recessive character, n11 – with
dominant, and n10 – hybrid with
dominant
• In fact, the invented predicates
represent the concept of a gene!
10
Success story: mutagenicity
• heterogeneous chemical compounds –
their structure requires relational
representation
• BK: properties of specific atoms and bonds
between them (relation!) and generic
organic chemistry info (e.g. structure of
benzene rings, etc.)
conjugated
• Regression-unfriendly
double bond in
A learned rule has been published in a five-member
Science
ring
11
problems
• Expressivity – efficiency
• Dimensionality reduction
• Therefore, interest in feature selection
12