Introducción:Programación Lógica Inductiva
ILP
=
Aprendizaje Inductivo de Conceptos (I)
?
Programación Lógica (LP)
Características:
los ejemplos y la teoría de base son cláusulas.
La teoría aprendida es un cjto de cláusulas.
Ventajas ILP:
la lógica de primer orden es un campo
matemático ampliamente desarrollado.
proporciona una representación uniforme
y expresiva.
Inducción
Lógica
Programación
Introducción: aprendizaje inductivo de conceptos
Inducción predictiva
+
+
+
+
+
–
–
–
–
–
–
–
H
Introducción: aprendizaje inductivo de conceptos
Inducción predictiva
+
+
+
+
+
–
–
–
?
?
?
?
–
H
Introducción: aprendizaje inductivo de conceptos
Inducción predictiva
aprender la definición de
un concepto
+
+
+
+
+
–
–
–
–
–
–
–
H
Inducción descriptiva
aprender las relaciones entre
conceptos
+
+
+
+
+
+
H
Introducción: aprendizaje inductivo de conceptos (predictivo)
Dado:
Un cjto de observaciones
ejemplos positivos E+
ejemplos negativos E –
conocimiento de base B
lenguaje de hipótesis LH
relación de cobertura
Encontrar:
Una hipótesis H? LH tal que (dado B) H cubre todos los ejemplos positivos y negativos
En lógica:
?e ? E+: B ? H ??? e (H es completo)
?e ? E-: B ? H ??/? e (H es consistente)
En ILP, E son hechos básicos, B y H cjtos de cláusulas definidas
+
+
+
+
+
+
H
–
–
–
–
–
–
–
Introducción: aprendizaje inductivo de conceptos (predictivo)
Dado:
Un cjto de observaciones
ejemplos positivos E+
ejemplos negativos E –
conocimiento de base B
lenguaje de hipótesis LH
relación de cobertura
criterio de calidad
Encontrar:
Una hipótesis H? LH tal que (dado B) H es óptima w.r.t. Algún criterio de calidad (p.ej. maximizar la precisión predictiva)
+
+
+
+
+
+
H
–
–
–
–
–
–
–
–
–
+
Introducción: aprendizaje inductivo de conceptos (descriptivo)
Dado:
Un cjto de observaciones (ejemplos positivos E+)
conocimiento de base B
lenguaje de hipótesis LH
relación de cobertura
Encontrar:
Una hipótesis (la más específica) H? LH tal que (dado B) H cubre todos los ejemplos positivos
En lógica, encontrar H tal que ?c ? H, c es cierto en algún modelo preferido de B? E+ (p. ej. el modelo mínimo de Herbrand)
En ILP, E son hechos básicos, B y H cjtos de cláusulas generales
+
+
+
+
+
+
H
Introducción: ejemplo de programación lógica
E+ = {sort([2,1,3],[1,2,3])}
E – = {sort([2,1],[1]),sort([3,1,2],[2,1,3])}
B contiene las definiciones permutation/2 y sorted/1
ILP predictivo
sort(X,Y)? permutation(X,Y), sorted(Y).
ILP descriptivo
sorted(Y) ? sort(X,Y).
permutation(X,Y) ? sort(X,Y).
sorted(X)? sort(X,X).
Introducción: ejemplo de descubrimiento de conocimiento
E+ = {daughter(mary,ann),daughter(eve,tom)}
E – = {daughter(tom,ann),daughter(eve,ann)}
B = {mother(ann,mary),mother(ann,tom),father(tom,eve),
father(tom,ian),female(ann),female(mary),female(eve),
male(pat),male(tom),parent(X,Y)?mother(X,Y), parent(X,Y)?father(X,Y)}
ILP predictivo
daughter(X,Y)? female(X),parent(Y,X).
o un cjto de cláusulas definidas
daughter(X,Y)? female(X),mother(Y,X).
daughter(X,Y)? female(X),father(Y,X).
ILP descriptivo
? daughter(X,Y),mother(X,Y).
female(X) ? daughter(X,Y).
mother(X,Y);father(X,Y)? parent(X,Y).
Introducción: definición empírica de ILP
Dado:
Un cjto de ejemplos E de un predicado objeto p
Hechos básicos verdaderos E+
Hechos básicos falsos E –
Un conocimiento de base B que define predicados qi ? p
Un lenguaje de hipótesis L, un subcjto. de cláusulas definidas
Encontrar:
Una hipótesis H que defina el predicado p, expresado en L como un cjto. de cláusulas de la forma
p(X1,…,Xn) ? L1,…,Li,…,Lm
tal que
H es completo: ?e ? E+: B ? H ??? e (suficiencia a posteriori)
H es consistente: ?e ? E-: B ? H ??/? e (satisfacibilidad a posteriori)
?e ? E+: B ??/? e (necesidad a priori)
?e ? E-: B ??/? e (satisfacibilidad a priori)
Introducción: un problema ILP simple
El problema
Dados:
ejemplos de la relación daughter(X,Y)
conocimiento de base definiciones (extensionales) de las relaciones parent(X,Y) y female(X)
Encontrar: la definición de la relación daughter
daughter(X,Y)? female(X),parent(Y,X).
ann
mary
tom
eve
ian
f
f
f
Introducción: un problema ILP simple
Representación ILP estándar
ejemplos: hechos básicos de la relación daughter
conocimiento de base: hechos básicos que definen las relaciones parent(X,Y) y female(X)
Introducción: un problema ILP simple
Representación como una base de datos relacional
Ejemplos como implicaciones:
daughter(mary,ann)? female(mary),female(ann),
parent(ann,mary),parent(ann,tom).
Hipótesis inducida:
daughter(X,Y)? female(X),parent(Y,X).
Introducción: ejemplo Bongard
Casificación de ejemplos basada en su estructura
pos
neg
Introducción: ejemplo Bongard (cont.)
Representación en lógica de primer orden
contains(1, o1).
contains(1, o2).
triangle(o1).
points(o1, down).
circle(o2).
pos(1).
pos(X) :- contains(X,Y), triangle(Y), points(Y, down).
el uso de variables proporciona un adecuado nivel de abstracción para la hipótesis
permitido cualquier
número de objetos
Dibujo 1
Introducción: un ejemplo del mundo real
Identificar subestructuras en las moléculas que hacen que
se adhieran a otras moléculas
La descripción de las moléculas es la lista de sus átomos, relaciones,
El conocimiento de base define el cómputo de la distancia euclidea,
Introducción: un ejemplo del mundo real
active(A) :- zincsite(A,B), hacc(A,C), hacc(A,D), hacc(A,E),
dist(A,C,B,4.891,0.750), dist(A,C,D,3.753,0.750), dist(A,
C,E,3.114,0.750), dist(A,D,B,8.475,0.750), dist(A,D,E,
2.133,0.750), dist(A,E,B,7.899,0.750).
…
hacc(M,A):- atm(M,A,o,2,_,_,_).
hacc(M,A):- atm(M,A,o,3,_,_,_).
hacc(M,A):- atm(M,A,s,2,_,_,_).
hacc(M,A):- atm(M,A,n,ar,_,_,_).
zincsite(M,A):-
atm(M,A,du,_,_,_,_).
hdonor(M,A) :-
atm(M,A,h,_,_,_,_),
not(carbon_bond(M,A)), !.
…
atm(m1,a1,o,2,3.430400,-3.116000,0.048900).
atm(m1,a2,c,2,6.033400,-1.776000,0.679500).
atm(m1,a3,o,2,7.026500,-2.042500,0.023200).
…
bond(m1,a2,a3,2).
bond(m1,a5,a6,1).
bond(m1,a2,a4,1).
bond(m1,a6,a7,du).
…
Descripción de las moléculas:
Conocimiento de Base:
-> Hipótesis:
Introducción: un ejemplo del mundo real
Algunos ejemplos de moléculas:
Introducción: conclusión
Para ciertos tipos de aprendizaje…
algunas veces llamado aprendizaje estructural: ejemplos que tienen una estructura compleja (no simplemente un vector de valores) o aprendizaje relacional
… es necesario un formalismo de representación para hipótesis y datos más expresivo
la lógica de primer orden proporciona esta expresividad
-> estudiar la inducción en lógica de primer orden.
Página anterior | Volver al principio del trabajo | Página siguiente |