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 – – – – – – –
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 – – – – – – – – – +
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
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).
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).
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)
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
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)
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).
Ejemplo Bongard Casificación de ejemplos basada en su estructura pos neg
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
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, …
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:
Un ejemplo del mundo real Algunos ejemplos de moléculas:
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 siguiente |