Proximidad entre cláusulas en programación lógica inductiva

Proximidad entre lausulas en Programaion Logia Indutiva M.A. Gutierrez Naranjo J.A. Alonso Jimenez ? J. Borrego Daz  Dpto. Cienias de la Computaion e Inteligenia Artiial { Universidad de Sevilla E{mail: f magutier,jalonso,jborrego g ia.es WWW: http://www-s.us.es/ f naranjo,  jalonso,  jborrego g Abstrat En este artulo estudiamos la idea de proximidad en el onjunto de lausulas de un lengua je donde dos lausulas equivalentes por subsunion se onsideran la misma. La formalizaion de proximidad que presentamos esta basada en una quasi{metria (una metria en la que no onsideramos la ondiion de simetra) d : C R =   C R =  ! [0 ; + 1 ℄ donde C =  es el espaio o iente obtenido a partir del onjunto de lausulas C p or la relaion de equivalenia basada en subsunion. Palabras lave: Programai  on L  ogia Indutiva, Quasi-m  etria 1 Intro duion En Aprendiza je Automatio hay una reiente neesidad de formalizar el onepto de proximidad en espaios ada vez mas abstratos. En Programaion Logia Indutiva (ILP), el problema de uantiar la proximidad entre lausulas ya ha sido estudiado on anterioridad p or A. Huthinson [4℄ y S.{H.Nienhuys{Cheng [6℄, ofreiendo distintas alternativas de soluion al problema. En ambos asos se dene primero una distania entre literales y luego se usa la metria de Hausdor para obtener a partir de esta una distania entre lausulas. Esto tiene dos desventa jas. Por un lado la metria de Hausdor dep ende exlusivamente de los puntos extremos (ver [1℄) y p or otro, estos literales se onsideran aislados y en ningun momento se onsideran las p osibles relaiones entre los literales de la misma lausula. En este artulo, proponemos una soluion al problema de uantiar la proximidad entre lausulas, onsiderandolas omo elementos de un entramado de relaiones va subsunion que nos va a p ermitir aeder de una lausula a otra, en ierto sentido, p or el amino mas orto. Esta aproximaion representa una imp ortante diferenia on [4℄ y [6℄, que onsideran los literales omo elementos aislados. Para ello, proponemos  Parialmente naniados por DGES, proyetos PB96{0098-C04{04 y PB96{1345 1. Que dos lausulas equivalentes ba jo subsunion se onsideren identias. Este planteamiento es muho mas fuerte que la equivalenia modulo renombramiento y nos va a permitir denir nuestra funion sobre lases de equivalenia. 2. Siguiendo la intuiion geometria, la distania entre dos puntos sera la longitud del amino mas orto entre ellas, onsiderando que dos lausulas estan a distania innita si no existe un amino que las una. 2 Clausulas A ontinuaion reordamos algunas deniiones sobre lausulas que usaremos mas adelante. Una vision general puede obtenerse en [7℄. En nuestra onstruion onsideraremos un lengua je L de primer orden. V ar y T er m son, resp etivamente, los onjuntos de variables y terminos de L . Una lausula es un onjunto nito de literales y C es el onjunto de las lausulas del lengua je. Sea S  V ar un onjunto nito de variables. Una sustituion es una apliaion  : S ! T er m tal que ( 8 x 2 S )[ x 6 = x ℄. Un renombramiento es una sustituion inye- tiva  tal que ( 8 x 2 S ) [ x 2 V ar ℄. Si C es una lausula y  es un renombramiento, C y C  = f L j L 2 C g son variantes . Sean C y D dos lausulas. C subsume a D , C  D , si existe una sustituion  tal que C   D . Si C  D y D  C entones C y D son equivalentes p or subsunion y lo esribiremos C  D . Si C  D y D 6 C esribiremos C  D . Una lausula reduida es una lausula C tal que no tiene ning un sub onjunto propio D tal que D  C . Plotkin [9℄ probo que dos lausulas reduidas equivalentes son variantes. Puesto que  es una relaion de equivalenia, denotaremos p or C =  el espaio o iente y, si C 2 C , [ C ℄ = f D 2 C j C  D g . Denimos el orden parial   sobre C =  omo ( 8 [ C ℄ ; [ D ℄ 2 C =  ) ([ C ℄   [ D ℄ , C  D ) El orden   esta bien denido y no ausara onfusion si usamos  en lugar de   . 3 ILP La Programaion Logia Indutiva (ILP) puede denirse omo el area de investigaion en la interseion del Aprendiza je Automatio y la Logia Computaional uyo prinipal ob jetivo es el desarrollo de teoras y algoritmos pratios para el aprendiza je indutivo de programas logios (N. Lavra y L. De Raedt, 1995). Del Aprendiza je Automatio toma sus ob jetivos, esto es, la sntesis de ono imientos a partir de la exp erienia. En este ontexto, el aprendiza je de oneptos intenta obtener deniiones de oneptos a partir de instanias p ositivas (ejemplos que verian la propiedad que queremos denir) e instanias negativas (ejemplos que no la verian) on la intenion de obtener una lasiaion de las instanias observadas as omo de predeir la posible lasiaion de instanias no observadas. De la Logia Computaional, la ILP toma su representaion formal, su orientaion semantia y sus tenias. La deniion de un onepto se representa mediante un programa logio, que no es mas que un onjunto nito ordenado de lausulas denidas, que puede ser visto omo el onjunto de axiomas de una teora. Si nuestra deniion (i.e. nuestro programa logio) es demasiado general, esto es, engloba ejemplos que no deseamos, deb emos 2 espeializarlo . Si p or el ontrario es demasiado esp eo, esto es, deja fuera instanias que deb era onsiderar, entones deb e ser generalizado. Estas generalizaiones y espeializa- iones se realizan apliando a alguna lausula del programa un op erador adeuado. De este modo se esp era que tras la suesiva apliaion de op eradores la suesion de programas onverja a uno que ubra todos los ejemplos positivos y ninguno de los negativos. En [8℄ Nienhuys{Cheng y Van der Laag denieron un op erador de renamiento  r que tomaba omo dato de entrada una lausula reduida C y devolva un onjunto de lausulas reduidas  r ( C ): Deniion 1 (Adaptada de [8℄) Sea C una lausula reduida. Entones D 2  r ( C ) si D es reduida y se veria una de las siguientes ondiiones:  1 r : C  D y existen dos lausulas C 0 2 [ C ℄ y D 0 2 [ D ℄ tales que C 0  = D 0 , donde  es la sustituion  = f x=f ( y 1 ;:::;y n ) g , f es un smbolo de funion 1 , x ourre en C 0 , y las variables y 1 ;:::;y n son variables distintas que no ourren en C 0 .  2 r : C  D y existen dos lausulas C 0 2 [ C ℄ y D 0 2 [ D ℄ tales que C 0  = D 0 , donde  = f x=y g y ademas las variables x e y ourren en C 0 .  3 r : D = C [ f L g donde L solo tiene variables distintas que no ourren en C y para todo literal M 2 C , L diere de M en el smbolo de prediado o en el signo. Una  r {adena de longitud n de C a D es una suesion nita C = C 0 ; C 1 ;:::;C n = D tal que para todo i 2 f 1 ; : : : ; n g , C i 2  ( C i  1 ) . Por ejemplo, onsideremos la lausula enendida ( x ) bombil l a ( x ) ; abl e ( x; y ) ; or r iente ( y ) que expresada omo onjunto de literales es C = f enendida ( x ) ; : bombil l a ( x ) ; : abl e ( x; y ) ; : or r iente ( y ) g . Si esta lausula fuera demasido general p o demos haerla mas esp ea apliando alguno de los operadores de renamiento. Por el op erador  1 r , si apliamos la sustituion  1 = f y =bater ia g , donde bater ia es un smbolo de funion de aridad ero, tendramos la lausula C = f enendida ( x ) ; : bombil l a ( x ) ; : abl e ( x; bater ia ) ; : or r iente ( bater ia ) g . Por el op erador  2 r , si apliamos la sustituion  2 = f y =x g , tendramos la lausula C = f enendida ( x ) ; : bombil l a ( x ) ; : abl e ( x; x ) ; : or r iente ( x ) g . El op erador  3 r es mas tenio. Nos p ermite a ~nadir literales nuevos omo no f undida ( z ) y onseguir lausulas omo C 1 = f enendida ( x ) ; : bombil l a ( x ) ; : abl e ( x; y ) ; : or r iente ( y ) ; no f undida ( z ) g , para despues apliar otros op eradores, p or ejemplo  3 r mediante la sustituion la sustituion  3 = f z =x g y obtener C 1  3 = f enendida ( x ) ; : bombil l a ( x ) ; : abl e ( x; y ) ; : or r iente ( y ) ; no f undida ( x ) g . 4 Quasi{metrias Las funiones de distania no simetrias ya fueron onsideradas p or Hausdor [3℄ a prinipios de siglo. Wilson [12℄ intro dujo el termino quasi{metris para estas funiones en 1931. A 1 Consideramos las onstantes omo smb olos de funion de aridad ero. 3 lo largo del siglo diversos investigadores han ontribuido al desarrollo de las distanias no simetrias, reibiendo reientemente un nuevo empuje on los traba jos en omputaion teoria de Lawson [5℄ o Smyth [11℄ entre otros. Deniion 2 ([11℄) Una quasi{metria sobre un onjunto X es una apliaion de X  X en los reales no negativos, inluyendo posiblemente + 1 tal que  ( 8 x 2 X ) [ d ( x; x ) = 0℄  ( 8 x; y 2 X ) [ d ( x; y ) = d ( y ; x ) = 0 ) x = y ℄  ( 8 x; y ; z 2 X ) [ d ( x; z )  d ( x; y ) + d ( y ; z )℄ Notese que una quasi{metria veria las ondiiones de metria de Frehet [2℄, exepto la ondiion de simetra. Veamos algunos ejemplos (otros ejemplos mas sostiados pueden enontrarse en [11℄). Ejemplo 1: Dado ualquier onjunto parialmente ordenado h P ; i , la quasi{metria disreta se dene omo d ( x; y ) =  0 si x  y 1 e.o.. Ejemplo 2: En el intervalo unidad [0 ; 1℄ p o demos denir la quasi{metria siguiente, uya metria asoiada es la distania euldea en el onjunto. d ( x; y ) =  0 si x  y x  y si y < x 5 Una quasi{metria sobre las lases de equivalenia En [8℄ Nienhuys-Cheng y y Van der Laag probaron que si C y D son lausulas reduidas y C  D entones existe una  r {adena de C a D . Vamos a usar esas adenas para formalizar la proximidad entre lausulas. En nuestra deniion, la distania entre dos lausulas vendra determinada p or la longitud del amino mas orto entre ellas, onsiderando omo amino la suesion de lases de equivalenia aso iada a una  r {adena. Deniion 3 Diremos que la suesion C = h [ C 0 ℄ ;:::; [ C n ℄ i , on [ C i ℄ 2 C =  para todo i 2 f 0 ;:::;n g es una L {adena de [ C 0 ℄ a [ C n ℄ si podemos elegir omo representantes de dihas lases las lausulas reduidas C 0 ;:::;C n y dihas lausulas forman una  r {adena. En ese aso diremos que la L {adena C tiene longitud n y lo denotaremos por jC j = n . Denotaremos omo L ([ C ℄ ; [ D ℄) el onjunto de todas las L {adenas de [ C ℄ a [ D ℄ . El unio elemento de L ([ C ℄ ; [ C ℄) es la suesion de longitud ero h [ C ℄ i . Es trivial omprobar que si C 1 = h [ C 0 ℄ ;:::; [ C n ℄ i es una L {adena de [ C 0 ℄ a [ C n ℄ y C 2 = h [ D 0 ℄ ;:::; [ D m ℄ i es una L {adena de [ D 0 ℄ a [ D m ℄ on [ C n ℄ = [ D 0 ℄, entones C 3 = h [ C 0 ℄ ;:::; [ C n ℄ ; [ D 1 ℄ ;:::; [ D m ℄ i es una L {adena de [ C 0 ℄ a [ D m ℄ de longitud n + m que llamaremos la onatenaion de C 1 y C 2 . Sab emos que si C y D son lausulas reduidas y C  D , entones existe una  r {adena de C a D . Como onseuenia inmediata tenemos el siguiente teorema: 4 Teorema 4 Consideremos [ C ℄ ; [ D ℄ 2 C =  tales que [ C ℄  [ D ℄ . Entones existe una L { adena de [ C ℄ a [ D ℄ . Demostraion: Sean [ C ℄ ; [ D ℄ 2 C =  tales lases de equivalenia y sean C 0 y D 0 dos lausulas reduidas tales que C 0 2 [ C ℄ y D 0 2 [ D ℄. Puesto que C 0  D 0 , se tiene que existe una  r {adena de C 0 a D 0 . Las lases de equivalenia aso iadas a los elementos de la  r {adena forman una L {adena de [ C ℄ a [ D ℄. A ontinuaion denimos nuestra quasi{metria. Si [ C ℄  [ D ℄ entones existe al menos una L {adena de [ C ℄ a [ D ℄, (el onjunto L ([ C ℄ ; [ D ℄) no es vao) y tiene sentido onsiderar el mnimo del onjunto de longitudes de aminos en L ([ C ℄ ; [ D ℄). Siguiendo la intuiion geometria, si onsideramos esas L {adenas omo aminos de [ C ℄ a [ D ℄, po demos denir nuestra quasi{metria omo la longitud del amino mas orto de [ C ℄ a [ D ℄. Si no existe ning un amino, p ensamos que [ D ℄ no puede ser alanzado desde [ C ℄, as que estan separados p or una distania innita. Deniion 5 Denimos la apliaion d : C =   C = ! [0 ; + 1 ℄ de la siguiente manera d ([ C ℄ ; [ D ℄) =  min fjC j : C 2 L ([ C ℄ ; [ D ℄) g si [ C ℄  [ D ℄ + 1 e.o.. Teorema 6 d es una quasi{metria Demostraion: (1) Puesto que [ C ℄  [ C ℄ para to do [ C ℄ 2 C =  , se tiene que la L {adena h [ C ℄ i 2 L ([ C ℄ ; [ C ℄). Ademas jh [ C ℄ ij = 0, luego d ([ C ℄ ; [ C ℄) = 0. (2) Si d ([ C ℄ ; [ D ℄) = d ([ D ℄ ; [ C ℄) = 0, entones [ C ℄  [ D ℄ y por tanto [ C ℄ = [ D ℄. (3) Tenemos que probar que d ([ C 1 ℄ ; [ C 3 ℄)  d ([ C 1 ℄ ; [ C 2 ℄) + d ([ C 2 ℄ ; [ C 3 ℄). Si [ C 1 ℄ 6 [ C 2 ℄ o [ C 2 ℄ 6 [ C 3 ℄ el resultado se tiene trivialmente, luego supongamos [ C 1 ℄  [ C 2 ℄ y [ C 2 ℄  [ C 3 ℄. Sean C 1 = h [ D 0 ℄ ;:::; [ D n ℄ i una L {adena de [ C 1 ℄ a [ C 2 ℄ (esto es, [ D 0 ℄ = [ C 1 ℄ y [ D n ℄ = [ C 2 ℄) tal que n = jC 1 j = d ([ C 1 ℄ ; [ C 2 ℄) y C 2 = h [ D 0 0 ℄ ;:::; [ D 0 m ℄ i una L {adena de [ C 2 ℄ a [ C 3 ℄ (i.e., [ D 0 0 ℄ = [ C 2 ℄ y [ D m ℄ = [ C 3 ℄ ) tal que m = jC 2 j = d ([ C 2 ℄ ; [ C 3 ℄) Si onatenamos C 1 y C 2 obtenemos C 12 = h [ D 0 ℄ ;:::; [ D n ℄ ; [ D 0 1 ℄ ;:::; [ D 0 m ℄ i que es una L {adena de [ C 1 ℄ a [ C 3 ℄ de longitud n + m , luego d ([ C 1 ℄ ; [ C 3 ℄)  jC 12 j = n + m = d ([ C 1 ℄ ; [ C 2 ℄) + d ([ C 2 ℄ ; [ C 3 ℄) Por tanto es una quasi{metria. Si ahora volvemos a onsiderar las lausulas aisladas y no las lases de equivalenia tendremos una funion b d : C  C ! [0 ; + 1 ℄ h C; D i 7! b d ( C; D ) = d ([ C ℄ ; [ D ℄) en la ual dos lausulas equivalentes estan a distania ero (teniamente una pseudo{quasi{ distania) en la ual mantenemos las siguientes propiedades: 5 1. b d ( C; D ) = 0 , C  D 2. b d ( C; D ) = + 1 , C 6 D 3. ( 8 C 1 ; C 2 ; C 3 2 C ) [ b d ( C 1 ; C 3 )  b d ( C 1 ; C 2 ) + b d ( C 2 ; C 3 )℄ Pensamos que de esta manera, b d ( C; D ) o dia de manera numeria suiente informaion sobre la relaion de subsunion entre C y D y p ermite un tratamiento algebraio de la relaion de proximidad. 6 Traba jos relaionados Como apuntabamos en la intro duion, en la literatura puede enontrarse diversas aproximaiones al problema de uantiar la relaion de proximidad entre lausulas. Nuestra propuesta se suma al esfuerzo de arro jar luz sobre el problema. 6.1 Nienhuys{Cheng [6℄ y Ramon y Bruyno oghe [10℄ En [6℄, Nienhuys-Cheng dene una distania para atomos errados  d n;g ( e; e ) = 0  p=n 6 = q =m ) d n;g ( p ( s 1 ;:::;s n ) ; q ( t 1 ;:::;t m )) = 1  d n;g ( p ( s 1 ;:::;s n ) ; p ( t 1 ;:::;t n )) = 1 2 n P n i =1 d n;g ( s i ; t i ) y luego onsidera la metria de Hausdor para trasladar esa distania a onjuntos de atomos. d h ( A; B ) = max f max a 2 A f min f d n;g ( a; b ) j b 2 B gg ; max b 2 B f min f d n;g ( a; b ) j a 2 A ggg El ob jetivo de esta distania era denir una metria entre interpretaiones de Herbrand, as que d n;g estaba solo denida sobre atomos errados. En [10℄, Ramon y Bruyno oghe extendieron esta distania a una funion sobre expresiones erradas y no erradas:  d n ( e 1 ; e 2 ) = d n;g ( e 1 ; e 2 ) si e 1 ; e 2 son expresiones erradas.  d n ( p ( s 1 ;:::;s n ) ; X ) = d n ( X ; p ( s 1 ;:::;s n )) = 1 on X una variable.  d n ( X ; Y ) = 1 y d n ( X ; X ) = 0 para todo X 6 = Y on X e Y variables. Apliando a d n la metria de Hausdor tenemos una distania sobre lausulas, omo muestra el siguiente ejemplo C 1 = f p ( f ( U ) ; X ; f ( a )) g C 2 = f p ( f ( a ) ; X ; f ( a )) g C 3 = f p ( f ( a ) ; X ; f ( a )) ; p ( Z; X ; Z ) g C 4 = f p ( f ( a ) ; X ; f ( a )) ; p ( f ( a ) ; V ; f ( a )) g 6 on d h ( C 1 ; C 2 ) = 1 12 , d h ( C 1 ; C 3 ) = 1 3 , d h ( C 1 ; C 4 ) = 1 4 . Se observa que los tres valores son muy distintos a p esar de que C 2 , C 3 y C 4 son equivalentes ba jo subsunion. Con nuestra funion se tiene b d ( C 1 ; C 2 ) = b d ( C 1 ; C 3 ) = b d ( C 1 ; C 4 ) = 1 puesto que [ C 2 ℄ = [ C 3 ℄ = [ C 4 ℄ on [ C 1 ℄ 6 = [ C 2 ℄ y C 1  = C 2 on  = f U =a g . 6.2 Huthinson [4℄ En [4℄, Huthinson da una pseudo-metria sobre el onjunto de terminos y la extiende al onjunto de literales. Entones, onsidera la metria de Hausdor sobre el onjunto de lausulas usando su pseudo{metria sobre literales. En su deniion de distania sobre terminos, usa una funion del onjunto de sustitu- iones sobre R llamada size . Da las ondiiones que tiene que satisfaer una funion para ser una size y da una funion onreta on esas araterstias S (  ) = X f w f =n j ( 9 x ) ( x 2 V ar y f =n o urre en x ) g donde w f =n es un p eso p ositivo para el smb olo de funion f =n . Con la metria de Hausdor basada en esa pseudo{metria tenemos que para las lausulas C 1 = f p ( X ; X ; Y ; Y ) g C 2 = f p ( U; V ; U; V ) g obtenemos los valores d h ( C 1 ; C 1 ) = 0 y d h ( C 1 ; C 2 ) = 0 a p esar de que C 1 y C 2 no son ni siquiera omparables ba jo subsunion. Con nuestra funion b d , al no existir ning un amino de C 1 a C 2 , esa relaion de ina- esibilidad se o dia on el smb olo + 1 . b d ( C 1 ; C 2 ) = b d ( C 2 ; C 1 ) = + 1 7 Conlusiones Este es un traba jo preliminar sobre omo uantiar la relaion de proximidad entre lausulas y se suma a otras aproximaiones en un intento de arro jar luz sobre el problema. La idea de nuestra aproximaion es aprovehar la relaion preexistente entre las lausulas para denir una funion de manera natural. Al ser esta relaion de subsunion no simetria, esta formalizaion de la proximidad tamp o o tiene p or que serlo. Consideramos que denir una distania entre lausulas apliando la metria de Hausdor sobre una distania entre literales quiza no sea lo mas aertado ya que depende exlusivamente de valores extremos. Por otro lado, quiza la formalizaion de distania de Frehet [2℄ sea demasiado estrita para espaios donde la prinipal relaion es la de orden parial. En este sentido, pensamos que este artulo abre una puerta a esa nueva onep ion en la formalizaion de proximidad. Nuestra investigaion se entra en estableer riterios de proximidad en el onjunto de lasulas y estudiar sus propiedades. Para ello deb emos dotar al onjunto de lausulas de una top ologa apropiada y onsiderar los op eradores de generalizaion (y esp eializaion) omo funiones del onjunto de lausulas en s mismo. 7 Esta formalizaion se fundamenta en un estudio top ologio de op eradores entre programas logios (o sub onjuntos de ellos) y p ermitira una mejor omprension del onepto de proximidad mas alla de los espaios metrios y esperamos que ayude a mejorar los algoritmos de b usqueda de soluiones en ILP. Referenias [1℄ T. Eiter and H. Mannila: Distane Measures for Point Sets and Their Computation . Ata Informatia 34, 2, pp.: 109{133, 1997. [2℄ M. Frehet. Sur quelques points du alul fontionnel . Reudiont del Cirulo Matematio di Palermo, vol 22, 1906. [3℄ F. Hausdor. Grundzuge der Mengenlehre . Leipzig, 1914. [4℄ A. Huthinson. Metris on Terms and Clauses . Pro . ECML{97 Prague April 1997 (Springer). ftp.//ftp.ds.kl.a.uk/pub/ teh-reports/ tr96-11.ps.gz [5℄ J.D. Lawson. Order and strongly sober ompatiations. In. G.M. Reed, A.W. Rosoe and R.F. Wahter (Eds.), Top ology and Category Theory in Computer Siene, Oxford University Press, pp. 179{205, 1991. [6℄ S-H. Nienhuys-Cheng. Distane between Herbrand interpretations. a measure for approximations to a target onept . Tehnial Rep ort EUR{FEW{CS{97{05. Department of Computer Siene, Erasmus University, the Netherlands, 1997. www.few.eur.nl/few /researh/pubs/s/1997/eur-few-s-97-05.pdf [7℄ S-H. Nienhuys-Cheng and R. de Wolf. Foundations of Indutive Logi Programming . LNCS 1228. Springer, 1997 [8℄ P.R.J. van der Laag, S.-H. Nienhuys-Cheng. Completeness and properness of renement operators in Indutive Logi Programming . Journal of Logi Programming, Vol 34, n.3, pp.. 201{225, Marh 1998 [9℄ G.D. Plotkin. A Note on Indutive Generalization . In Mahine Intelligene 5, pp.. 153{163. Edinburgh University Press, Edinburgh, 1970. [10℄ J. Ramon and M. Bruyno oghe. A framework for dening distanes between rst{order logi{objets. Rep ort CW 263, Department of Computer Siene, Katholieke Universiteit Leuven, May 1998. http.//www.s.kuleuven.a.be/publiaties/rapporten /w/CW263.ps.gz [11℄ M.B. Smyth. Total ly bounded spaes and ompat ordered spaes as domains of omputation. In. G.M. Reed, A.W. Roso e and R.F. Wahter (Eds.), Top ology and Category Theory in Computer Siene, Oxford University Press, pp. 207-229, 1991. [12℄ W.A. Wilson. On quasi{metri spaes . Amer. J. Math. 53, pp. 675{684, 1931. 8