Búsqueda de cláusulas del programa: noción de generalidad El conjunto de las cláusulas es un retículo C1 es más general que C2 iff para alguna sustitución ?: C1 ? ? C2 especialización: aplicar una sustitución y/o añadir un literal generalización: aplicar una sustitución inversa y/o eliminar un literal m(X,Y) m(X,X) m(X,[Y|Z]) m([X|Y],Z) m(X,Y):-m(Y,X) m(X,[X|Z]) m(X,[Y|Z]):-m(X,Z)
Búsqueda de cláusulas del programa: noción de generalidad Una teoría G es más general que una teoría S iff G ?= S G ?= S: en cada interpretación en la que G es cierto, S también lo es “G implica lógicamente S”
Todas las frutas saben bien ?= Todas las manzanas saben bien (asumiendo que las manzanas son frutas)
Búsqueda de cláusulas del programa: deducción versus inducción Hay operadores deductivos ?- que implementan (o aproximan) ?= resolución Invertir estos operadores conduce a operadores inductivos Técnica básica en muchos sistemas de programación lógica inductiva
Búsqueda de cláusulas del programa: varios marcos para la generalidad Dependiendo de la forma de G y S 1 cláusula / cjto de cláusulas / cualquier teoría de primer orden
Dependiendo en el mecanismo deductivo ?- a invertir Theta-subsunción Resolución Implicación
Métodos Bottom-up: theta-subsunción (Plotkin) Subsunción Sustitución: ? = {X1/t1,…,Xn/tn} es una asignación de los términos ti a las variables Xi
Subsunción: Sean C y D cláusulas. C (?-)subsume D (C =? D) iff existe ? tal que C? ? D Ejemplo: p(a,b)? r(b,a) es subsumida por p(X,Y)? r(Y,X) p(X,Y)? r(Y,X) subsume p(X,Y)? r(Y,X),q(X)
Métodos Bottom-up: theta-subsunción (Plotkin) Ejercicio: C1: father(X,Y) ?parent(X,Y). C2: father(X,Y) ?parent(X,Y),male(X). C3: father(luc,Y) ?parent(luc,Y). C1 =? C2 (? ={ }) C1 =? C3 (? ={X/luc}) C2 =/? C3 C3 =/? C2
Métodos Bottom-up: theta-subsunción (Plotkin) Ejercicio: C1: p(X,Y) ?q(X,Y). C2: p(X,Y) ?q(X,Y),q(Y,X). C3: p(Z,Z) ?q(Z,Z). C4: p(a,a) ?q(a,a). C1 =? C2 (? ={ }) C1 =? C3 (? ={X/Z,Y/Z}) C1 =? C4 (? ={X/a,Y/a}) C3 =? C4 (? ={Z/a})
Métodos Bottom-up: theta-subsunción (Plotkin) Ejercicio: C1: p(f(X),g(X)) ? C2: p(f(3),g(3)) ?
Ejercicio: C1: p(f(X),g(X)) ? C2: p(f(3),g(Y)) ?
C1 =? C2 (? ={X/3}) C1 =/? C2 C2 =/? C1
Métodos Bottom-up: theta-subsunción (Plotkin) Propiedades de la Q-subsunción Correcta: si C =< D entonces C |= D Incompleta: puede que C |= D y sin embargo C =/< D C: p(f(X)) ? p(X) D: p(f(f(X))) ? p(X) Reflexiva, transitiva y antisimétrica ? relación de semi-orden clases de equivalencia con un orden parcial
c1?c2 sii c1 =< c2 y c2 =< c1 Si c?[C] y d?[D] ? c =< d ó d =< c ó (c =/< d y d =/< c)
Métodos Bottom-up: theta-subsunción (Plotkin) Las clases de equivalencia forman un retículo p(X,Y) :- m(X,Y),r(X) p(X,Y) :- m(X,Y), m(X,Z),r(X) … p(X,Y) :- m(X,Y),s(X) p(X,Y) :- m(X,Y), m(X,Z),s(X) … p(X,Y) :- m(X,Y) p(X,Y) :- m(X,Y), m(X,Z) p(X,Y) :- m(X,Y),m(X,Z),m(X,U) … p(X,Y) :- m(X,Y),s(X),r(X) p(X,Y) :- m(X,Y), m(X,Z),s(X),r(X) … lgg glb
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Generalización menos general (lgg) C es la generalización menos general (lgg) de D bajo ?-subsunción si C =? D y para cada E tal que E =? D se cumple E =? C. Computación de lgg Cuando nos restringimos a átomos con el mismo signo y el mismo símbolo de predicado (compatibles) la lgg es el dual de la unificación lgg(f1(l1,…,ln),f2(m1,…,mn) = v si f1? f2 = f1 (lgg(l1,m1),…,lgg(ln,mn)) si f1= f2
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Ejemplo: l = member(3,cons(2,cons(3,nil))) l’ = member(3,cons(4,cons(5,cons(6,nil)))) m = member(3,cons(v2,4,cons(v3,5,vnil,cons(6,nil)))) m = member(3,cons(x,cons(y,z)))
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Ejercicio l: p(f(5,3),g(2,3)) l’: p(f(1,2),g(3,2)) l’’: p(f(1,4),g(5,4))
lgg = p(f(X,W),g(Y,Z))
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Sean C y D dos cláusulas. El lgg de C y D en el orden de subsunción es lgg(C,D)= ?lgg(l,m) | l?C y m?D y l y m son compatibles} Dadas dos cláusulas, el lgg es la cláusula simple más específica que es mas general que ambas. Ejemplo: f(t,a)? p(t,a), m(t),f(a) f(j,p)? p(j,p), m(j),m(p) lgg = f(X,Y) ? p(X,Y),m(X),m(Z)
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Ejemplo rev([2,1],[3],[1,2,3])? rev([1],[2,3],[1,2,3])
rev([a],[ ],[a])? rev([ ],[a],[a])
Ejercicio a([1,2],[3,4],[1,2,3,4])? a([2],[3,4],[2,3,4]) a([a],[ ],[a])? a([ ],[ ],[ ])
lgg = rev([A,B],C,[D|E]) ? rev(B,[A|C]),[D|E]) A B C D E B A C D E lgg = a([A|B],C,[A|D]) ? a(B,C,D)
Métodos Bottom-up: generalización menos general – lgg (Plotkin) Ejercicio m(c,[a,b,c])? m(c,[b,c]), m(c,[c]) m([a],[a,b])? m(a,[a])
lgg = m(P,[a,b|Q]) ? m(P,[R|Q]),m(P,[P])
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin) Generalización menos general relativa (rlgg) relativa a la teoría de conocimiento B rlgg(e1,e2)=lgg(e1?B,e2?B) Ejemplo: C1: uncle(X,Y):-brother(X,father(Y)). C2: uncle(X,Y):-brother(X,mother(Y)). B: parent(father(X),X). parent(mother(X),X). lgg(C1,C2) = uncle(X,Y):-brother(X,Z). rlgg(C1,C2) = uncle(X,Y):-brother(X,U),parent(U,Y).
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin) Una cláusula C es más general que D con respecto a una teoría T si T ? C |- D.
Un átomo A es una lgg de un átomo B con respecto a una teoría T si existe un unificador ? tal que T |- A? ? B (A=?T B). Una cláusula C es una lgg de una cláusula D con respecto a una teoría T (rlgg) si T |- C? ? D para alguna sustitución ?.
Métodos Bottom-up: generalización menos general relativa- rlgg (Plotkin) Problema: no siempre existe rlgg de un conjunto de cláusulas con respecto a una teoría. C1: q(f(a)). C2: q(g(a)). B: p(f(X),Y). p(g(X),Y). C : q(X):-p(X,g1(X)),…,p(X,gn(X)) es una generalización
Excepción: rlgg existe siempre si T es básica (GOLEM).
Métodos Bottom-up: generalización de Buntine rlgg puede conducir a conclusiones contraintuitivas. EJEMPLO: C: pequeño(X):-gato(X). D: muñeco_mascota(X):- de_peluche(X), gato(X). P: mascota(X):- gato(X). muñeco_mascota(X):-pequeño(X),de_peluche(X),mascota (X). C =?P D Si asumimos que una cláusula C es más general que otra D si cualquier interpretación de C permite obtener las mismas conclusiones que con D. En el ejemplo anterior C no es más general que D.
Métodos Bottom-up: generalización de Buntine Subsunción generalizada (cláusulas definidas) Una cláusula C es más general que otra D w.r.t. un programa P C =?BP D si para cualquier interpretación de Herbrand I modelo de P, entonces TD(I) ? TC(I). En el ejemplo anterior C y D no pueden compararse ya que tienen distintas cabezas.
Métodos Bottom-up: generalización de Buntine Visión operacional Sean C y D cláusulas con variables disjuntas y sea P un programa lógico. Sea ? una sustitución que asigna a las variables de D nuevas constantes (que no aparecen en C,D ni P).Entonces, C =?BP D sii existe una sustitución ? tal que: Chead ? = Dhead ? P ? Dbody ??? ? (Cbody ??)
Métodos Bottom-up: generalización de Buntine Procedimiento: C es más general que D wrt P si C puede convertirse en D aplicando repetidamente: Transformar las variables en constantes o en otros términos Añadir átomos al cuerpo Evaluar parcialmente el cuerpo resolviendo cláusulas en P contra un átomo del cuerpo.
Métodos Bottom-up: generalización de Buntine Subsunción generalizada versus generalización de Plotkin. C =?B? D sii C =? D
Subsunción generalizada versus generalización menos general relativa. C =?BP D sii C aparece en la raíz de una refutación en la demostración de P ?? (C ? D) =?BP un caso especial de rlgg
Métodos Bottom-up: resolución inversa Resolución C1 C2
?1 ?2
C
RESOLUCIÓN: C = C1 ? C2 ?l1 ? C1 ? l2 ? C2 | C1 y C2 variables disjuntas ? ? = mgu(l1, l2) s.t. l1? = l2?, ? = ?1 ?2 ? l1?1 = l2?2 C=(C1-??l1?)? 1 ? (C2-?l2?)? 2
Métodos Bottom-up: resolución inversa Ejemplo: p(X)?q(X) y q(X) ? r(X,Y) conduce a p(X)? r(X,Y) p(X)?q(X) y q(a) conduce a p(a) Inversión de la resolución: obtención de C1 (o C2) a partir de C y C2 (C1). No hay una solución única EJEMPLO: C2 = B ? E,F C = A ? E,F,C,D C1 = A ? B,C,D C1’ = A ? B,C,D,E C1’’ = A ? B,C,D,F C1’’’ = A ? B,C,D,E,F
Métodos Bottom-up: resolución inversa El problema es aún más agudo para cláusulas de primer orden EJEMPLO: C1 = ? mas_pesado(martillo,pluma) C = ? mas_denso(martillo,pluma),mas_grande(martillo,pluma) C2 = mas_pesado(martillo,pluma) ? mas_denso(martillo,pluma), mas_grande(martillo,pluma) C’2 = mas_pesado(A,B) ? mas_denso(A,B), mas_grande(A,B) Para generar C2 debemos decidir qué términos se convierten en variables y cómo
Métodos Bottom-up: resolución inversa El operador V
C1 C2 ?1 ?2
C OPERADOR V: Produce C2 a partir de C y C1
dadas dos cláusulas C1 y C, el V-operador encuentra C2 tal que C es una instancia de un resolvente de C1 y C2. Generaliza ?C1,C} a ?C1, C2}
Métodos Bottom-up: resolución inversa Absorción desde q?A y p ?A,B inferir p ?q,B
Identificación desde p?q,B y p ?A,B inferir q ?A
p?q,B q ?A p?A,B p?q,B q ?A p?A,B
Métodos Bottom-up: resolución inversa Absorción: el cuerpo de C1 es absorbido en el cuerpo de C (después de una unificación) y reemplazado por su cabeza EJEMPLO:
C:pajaro(tweety):-tiene_plumas(tweety), tiene_alas(tweety),tiene_pico(tweety). C1:vuela(X):- tiene_plumas(X),tiene_alas(X). ? = ? X/tweety}
C2:pajaro(tweety):-vuela(tweety), tiene_pico(tweety).
Métodos Bottom-up: resolución inversa Ejemplo: P={animal(tiburon) nadar(tiburon)} e={pez(tiburon)} Encontrar dos cláusulas que tengan un resolvente del que pez(tiburon) es una instancia
Cláusula de entrada: una cláusula de P (nadar(tiburon)) Cláusula central: Por ejemplo, la menos general (pez(tiburon) ? nadar(tiburon))
P |/=e
Métodos Bottom-up: resolución inversa Cláusula de entrada: una cláusula de P (animal(tiburon)) Cláusula central: Por ejemplo, la menos general (pez(X) ? animal)X),nadar(X)).
pez(x) ? animal(x), nadar(x) animal(tiburon)
pez(tiburon) ? nadar(tiburon) nadar(tiburon)
pez(tiburon)
Métodos Bottom-up: resolución inversa Identificación: identificar parte del cuerpo de C2 en el cuerpo de C a través de una sustitución ?. Encontrar un literal l en el cuerpo de C2 que no ocurre en el de C. La identificación construye C1 con cabeza l y cuerpo la parte de C que no está en C2. EJEMPLO: C:pajaro(tweety):-tiene_plumas(tweety), tiene_alas(tweety),tiene_pico(tweety). C2: pajaro(tweety):- vuela(tweety),tiene_pico(tweety). l: vuela(tweety) C-C2: { tiene_plumas(tweety), tiene_alas(tweety)} C1: vuela(tweety):- tiene_plumas(tweety), tiene_alas(tweety).
Métodos Bottom-up: resolución inversa El operador W
C1 A C2 ?C1 ?A,1 ?A,2 ?C2
B1 B2 OPERADOR W
Dadas dos cláusulas ?B1,B2} encontrar ?C1,A,C2} tal que B1 es una instancia de un resolvente de C1 y A, y B2 es una instancia de un resolvente de A y C2. Generaliza ?B1, B2} a ?C1, A,C2}
Métodos Bottom-up: resolución inversa Intra-construcción desde p?A,B y p ?A,C inferir q ?B y p?A,q y q?C
Inter-construcción desde p?A,B y q ?A,C inferir p ?r,B y r?A,q y q?r,C
p?r,B r ?A q ?r,C p?A,B q?A,C q?B p ?A,q q ?C p?A,B p?A,C
Métodos Bottom-up: resolución inversa Cuando l no está ni en B1 ni en B2, el operador W se inventa predicados.
Métodos Bottom-up: implicación inversa Sean dos cláusulas C y D. decimos que C implica D (C ? D) iff cada modelo de C es modelo de D (C ?? D). C es una generalización bajo implicación de D.
la generalización bajo ?–subsunción es incompleta. C ?? D y C =/? D Inversión implicación es una forma completa de generalización. ? indecidible ? computacionalmente caro ? cláusulas recursivas
Métodos Bottom-up: implicación inversa Diferencia entre implicación y ?–subsunción: cláusulas ambivalentes. Una cláusula es ambivalente sii contiene un par (C, ?D) de literales ambivalentes, es decir, C y D tienen el mismo símbolo de predicado y signo. p(X):-p(X). q(a):-q(s(s(a))).
Sean C y D no ambivalentes. Entonces, C ? D sii C =? D.
Métodos Bottom-up: implicación inversa RELACIÓN ENTRE IMPLICACIÓN Y RESOLUCIÓN
C ? D ? D es una tautología ? C =? D ? E =? D y E se obtiene resolviendo C consigo misma.
| Página siguiente |