1 I A 4. Métodos de representación del conocimiento e inferenciaJorge Cabrera Gámez Departamento de Informática y Sistemas Universidad de Las Palmas de Gran Canaria © Todos los derechos reservados
2 Contenidos 4. Métodos de representación del conocimientoe inferencia. (10 horas) 4.1 Representación e inferencia en la lógica de predicados. 4.2 Sistemas basados en reglas. 4.3 Redes asociativas y objetos. Razonamiento basado en casos. 4.4 Sistemas de pizarras. 4.5 Bibliografía básica: [Gonz-93], [Rich-91]. 2
3 Objetivos: Relevancia del problema de la representación del conocimiento en la IA Presentar los formalismos de representación más empleados Discutir ventajas e inconvenientes de los formalismos de representación 3
4 El conocimiento. Para que un agente inteligente sea capaz de resolver las tareas asignadas (interpretar escenas, diagnosticar enfermedades, reconocer el habla, ...) es necesario que dispongan de cierta información específica al domino de actividad. Conocimiento: Información específica a un dominio que permite la realización de una actividad. Representación del Conocimiento: El problema de cómo un agente puede incorporar y utilizar eficazmente volúmenes de información. 4
5 Representación + ControlEl conocimiento. Los problemas fundamentales: Cómo se adquiere el conocimiento. Cómo se accede al conocimiento. Cómo se puede modificar la base de conocimiento. Cómo se garantiza la coherencia de la base de conocimiento Cómo se “usa”, cómo se razona (qué procesos de inferencia se pueden desarrollar sobre la base de conocimiento) Representación + Control 5
6 Tipos de conocimiento Conocimiento de Entidades: Referido a las propiedades y estructura física de los objetos o entes del mundo real. Conocimiento de Eventos: Referido a la secuencia y distribución en el tiempo de sucesos, así como de las relaciones de causalidad entre los mismos. Conocimiento de Conducta: Considera el comportamiento o modo de proceder de los entes en el mundo real. Conocimiento Procedimental: Referido a cómo deben realizarse determinados procesos o transformaciones 6
7 Tipos de conocimiento Conocimiento de la Incertidumbre: Aquel que es relevante a la hora de considerar la verosimilitud de ciertos hechos o, propiedades, o de razonar en situaciones con incertidumbre. Metaconocimiento: Designa el conocimiento cuyo objeto de referencia es el propio conocimiento, es decir, un conocimiento acerca de las propiedades del conocimiento. 7
8 Fases de utilización El uso del conocimiento en un agente inteligente se realiza en varias etapas Adquisición Estructuración Acceso Selección Razonamiento 8
9 Fases de utilización Adquisición (aprendizaje).Se extrae el conocimiento de alguna fuente. * Un experto * Mediante un proceso de aprendizaje autónomo Estructuración. Diseño de una estructura de datos que soporte de manera eficaz el conocimiento y que permita añadir nuevo conocimiento a otro ya existente garantizando la coherencia y corrección de la base de conocimiento. 9
10 Acceso. Debe garantizarse un acceso rápido y eficaz al conocimiento. Este aspecto es críticamente dependiente de cómo se haya estructurado la base de conocimento. Selección. Cómo se selecciona el conocimiento relevante ante una situación concreta. La capacidad de poder seleccionar el conocimiento adecuado requiere de la intervención de algún tipo de metaconocimiento. Razonamiento. Cuando el conocimiento se emplea para derivar una conclusión o seleccionar una tarea. 10
11 Propiedades de las representacionesÁmbito. El ámbito de aplicación de un sistema de representación está relacionado con el área de la IA en que es aplicable o útil el conocimiento representado. Granularidad. Se refiere al gránulo o tamaño mínimo de la unidad de representación. Gránulos de gran tamaño: Más sencillo representar conceptos de alto nivel Más complicado el tratarlas o razonar con ellas Gránulos de pequeño tamaño: Más sencillo representar conceptos de bajo nivel y estructuras jerarquizadas Difícil representar conceptos de alto nivel 11
12 Redundancia. Está asociada a la posibilidad de poder representar un mismo conocimiento en múltipes formas. Esto puede ser un inconveniente ya que no existe unicidad en la expresión, pero también una ventaja al poder expresar el conocimiento en una forma que facilite su identificación ante ciertas situaciones. Modularidad. Depende de la facilidad con la que se pueda añadir, modificar o eliminar información de la base de conocimiento. Comprensión. Relacionada con la capacidad de interpretación en términos humanos de las estructuras de representación. 12
13 Representación e inferencia en la lógica de predicadosIdea: La lógica como sistema de representación del conocimiento y de obtención de consecuencias (control) Cálculo de predicados de primer orden Fórmulas atómicas Fórmulas Conectores 13
14 Fórmulas atómicas Términos autor(quijote, cervantes)escritor(cervantes) autor(quijote, Quién) autor(quijote, mejor(novelista, españa)) Predicado: Un predicado es un símbolo cuyo valor se encuentra en el dominio lógico (verdadero o falso) y representa alguna cualidad semántica, en un cierto contexto, acerca de las relaciones entre objetos o entidades 14
15 Fórmulas atómica :: Predicado | Predicado(Términos) Términos :: Término | Término, Términos Término :: Variable | Constante | Functor Functor :: NombreFunctor(Términos) Normas léxicas: Las variables siempre empiezan por mayúscula las constantes por minúscula Constante: Representa un término con un valor semántico determinado Functor: Es un símbolo que posee valor en el dominio de las variables y constantes, pero que no es ni una variable ni una constante. Variable: Representa un término cuyo valor no está determinado inicialimente y su dominio de definición debe coincidir con el de los términos constantes 15
16 Conectores Permiten construir fórmulas complejas a partir de fórmulas o expresiones atómicas Negación : (~) Disyunción : (OR) Conjunción : (AND) Implicación : () Equivalencia : 16
17 autor(hamlet, cervantes) Negación: Genera una fórmula que posee valores lógicos complementarios alos de la fórmula sobre la que se aplica. Estrictamente no es un conector, pues no conecta dos fórmulas sino que transforma una. autor(hamlet, cervantes) Disyunción: Genera una fórmula cuyo valor lógico es el “OR” de los valores de las dos fórmulas que conecta. estado(bombilla, encendida) estado(bombilla, apagada) Conjunción: Genera una fórmula cuyo valor lógico es el “AND” de los valores de las dos fórmulas que conecta. color(coche, rojo) color(camisa, azul) 17
18 p q es equivalente a p q p q p q p p q 0 0 1 1 1 0 1 1 1 1 Implicación: Genera una fórmula compuesta no-simétrica que es cierta siempre, salvo cuando el antecedente es cierto y el consecuente falso. p q es equivalente a p q p q p q p p q está(cielo, azul) lloverá(hoy) está(cielo, azul) lloverá(hoy) 18
19 p q es equivalente a (p q) (q p) Equivalencia o doble implicación: Genera una fórmula que es cierta sólo si las dos componentes poseen idéntico valor. p q es equivalente a (p q) (q p) p q p q q p (p q) (q p) llueve(hoy) está(cielo, nublado) 19
20 Equivalencias Complemento: p p 1 Doble negación: ( p ) pConmutativa: p q q p p q q p Distributiva: p (q r) (p q) (p r) p (q r) (p q) (p r) Asociativa: p (q r) (p q) r p (q r) (p q) r Leyes de De Morgan: (p q) p q (p q) p q Ley del contrapositivo: p q q p 20
21 Cuantificadores Establecen el ámbito de existencia de las variablesCuantificador Universal (): Cuando acompaña a una variable X establece que la fórmula es siempre para cada valor posible de la variable X. La variable X se dice entonces cuantificada universalmente. “Todo cuerpo con masa cae” (X) ( [cuerpo(X) posee(masa, X)] cae(X) ) 21
22 Cuantificadores Establecen el ámbito de existencia de las variablesCuantificador Existencial (): Establece que como mínimo existe un valor de la variable cuantificada que hace cierta la fórmula. La variable se dice cuantificada existencialmente. “Alguién descubrió la penicilina” ( X) ( descubrió( X, penicilina ) 22
23 Reglas de precedencia entre operadores , , , menor precedencia Forma Normal de una fórmula Una fórmula se dice que está en forma normal si todos los cuantificadores han sido desplazados al principio de la fórmula. 23
24 Forma normal de una fórmulaUna fórmula se dice que está en forma normal si todos los cuantificadores han sido desplazados al principio de la fórmula. Algunas equivalencias útiles para alcanzar una forma normal [ ( X) p(X) ] (X) [ p(X) ] [ (X) p(X) ] ( X) [ p(X) ] ( X) [ p(X) q(X) ] [ (X) p(X) ] [ (X) q(X) ] ( X) [ p(X) q(X) ] [ ( X) p(X) ] [ ( X) q(X) ] 24
25 Reglas de Inferencia Especialización Universal: siempre es posible deducir la verificación de un caso concreto a partir de un cuantificador universal. (X) p(X) p(a) Sustitución: permite la sustitución de cualquier proposición en una fórmula por otra biequivalente. Modus ponens: de una implicación de la verificación de la premisa se verifica la conclusión. Axioma: p q Axioma: p Teorema: q 25
26 Introducción: la fbf pq puede ser inferida de las fbf p y q. Modus tollens: de una implicación y de la no verificación del consecuente, se concluye la no verificación de la premisa. Axioma: p q Axioma: ¬q Teorema: ¬p Introducción: la fbf pq puede ser inferida de las fbf p y q. Eliminación: la fbf p puede ser inferida de la fbf pq. Introducción: la fbf p q puede ser inferida de la fb p o de la fbf q. 26
27 Lógica de orden superior: Lógica de orden cero: Los predicados carecen de términos y el cálculo de predicados se reduce al cálculo de proposiciones o proposicional. Lógica de orden uno: Los predicados poseen términos que pueden ser constantes, variables o functores. Lógica de orden superior: Los predicados lógicos pueden ser en sí mismos variables. 27
28 B. Marco era pompeyano (de Pompeya). Ejercicios. Expresar como fbf en lógica de predicados los siguientes hechos A. Marco era un hombre. B. Marco era pompeyano (de Pompeya). C. Todos los pompeyanos eran romanos. D. César era un dirigente. E. Todos los romanos o bien eran leales a César o bien le odiaban. F. Todo el mundo es fiel a alguien. G. La gente sólo trata de asesinar a aquellos dirigentes a los que no son leales. H. Marco intentó asesinar a César. I. Algún romano odia a César. 28
29 C. (X)(pompeyano(X) romano(X)) D. dirigente(césar) A. hombre(marco) B. pompeyano(marco) C. (X)(pompeyano(X) romano(X)) D. dirigente(césar) E. (X)(romano(X) leal(X,césar) odia(X,césar)) F. (X)(hombre(X) (Y) leal(X,Y) G. (X)(Y) (hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) H. intenta_asesinar(marco, césar) I. (X) (romano(X) odia(X, césar)) 29
30 Teorema + Axiomas (como fórmulas bien formadas, fbf)Lo que queremos hacer ... Teorema + Axiomas (como fórmulas bien formadas, fbf) + Teorema + Axiomas (como cláusulas) + Método de resolución por refutación Unificación Demostración automática de teoremas 30
31 Fórmulas bien formadas (fbf)Son aquellas que cumplen ciertos requisitos en su estructura y definen la sintaxis del cálculo de predicados Una fórmula se dice bien formada si puede derivarse de alguna de las siguientes reglas de formación: 1. Cualquier fórmula atómica es una fbf. 2. Si p y q son fbf, entonces también serán fbf las siguientes: ¬p, p q, p q, p q 3. Si X es una variable libre en la fbf p, entonces son fbf : (X) p(X), (X) p(X) 4. Cualquier fórmula que no pueda formarse a partir de estas reglas no es una fbf. 31
32 Cláusula Es una fórmula que sólo contiene operadores disyuntivos y posiblemente negaciones sobre los átomos. Este tipo de fórmulas pueden ser expresadas por una única implicación. Así la fórmula: a1 a2 ... an b1 b2 ... bm se puede transformar en : ¬(¬ a1 ¬ a2 ... ¬ an ) b1 b2 ... bm ¬ a1 ¬ a2 ... ¬ an b1 b2 ... bm Cláusula de Horn, aquellas cuyo consecuente tiene un único predicado. a1 a2 ... an b 32
33 Transformación a cláusulasPara ilustrar el proceso paso a paso emplearemos la siguiente fómula compleja como ejemplo: (X){p(X) {(Y)[p(Y) p(f(X,Y))] (Y)[q(X,Y) p(Y)]}} 1. Eliminar los símbolos de implicación, sustituyendo p q por p q. Tras este primer paso, nuestra fómula se transforma en: (X){p(X) {(Y)[ p(Y) p(f(X,Y))] (Y)[ q(X,Y) p(Y)]}} 33
34 Aplicándolo sobre el ejemplo:2. Mover las negaciones hasta las fórmulas atómicas, para ello se emplean las leyes de Morgan y las transformaciones de cuantificadores existenciales y universales. (p q) p q (p q) p q [ ( X) p(X) ] (X) [ p(X) ] [ (X) p(X) ] ( X) [ p(X) ] Aplicándolo sobre el ejemplo: (X){ p(X) {(Y)[ p(Y) p(f(X,Y))] (Y)[q(X,Y) p(Y)]}} 34
35 Así nuestro ejemplo se transforma en:3. Renombrar variables, en aquellos casos en los que varias varables se hayan nombrado de igual forma. En nuestro caso esto ocurre con la variable Y que renombramos como Z en su segunda ocurrencia. Así nuestro ejemplo se transforma en: (X){ p(X) {(Y)[ p(Y) p(f(X,Y))] (Z)[q(X,Z) p(Z)]}} 35
36 P.e. (Z) q(X,Z) se transforma en q(X, g(X)) 4. Eliminar los cuantificadores existenciales. Las variables cuantificadas por este tipo de cuantificadores serán sustituidas por un tipo de función comodín denominada función de Skolem (proceso de skolemización). P.e. (Z) q(X,Z) se transforma en q(X, g(X)) en donde g(X) es la función de Skolem para este caso. Nótese que no sólo se eliminan los cuantificadores existenciales sino también las variables ligadas a los mismos. La función de Skolem introducida debe ser nueva en el universo de discurso, y además deberá ser función de todas las variables cuantificadas universalmente cuyos ámbitos incluyan el ámbito del cuantificador existencial que se pretende eliminar. 36
37 Así nuestro ejemplo se transforma en:(X){ p(X) {(Y)[ p(Y) p(f(X,Y))] [q(X, g(X)) p(g(X))]}} Si el cuantificador existencial no se encuentra en el ámbito de ningún cuantificador universal, se usará una función de Skolem sin argumentos. Como en el siguiente ejemplo: (Z) q(Z) se transforma en q(a) Donde el símbolo constante a referencia a la entidad que sabemos existe. Evidentemente a debe ser un símbolo que no haya sido empleado con anterioridad. 37
38 Este paso se ejecuta sobre el ejemplo en dos pasos:5. Desplazar los cuantificadores universales, de manera que queden al comienzo de la fórmula (prenex form). Estre proceso puede ser realizado por cuanto no existen ya variables distintas con el mismo nombre. (X) (Y){ p(X) { [ p(Y) p(f(X,Y))] [q(X, g(X)) p(g(X))]}} 6. Convertir los operadores conjuntivos (AND) en los más externos, para lo que se emplean las leyes distributivas. A la forma resultante se le denomina forma normal conjuntiva. Este paso se ejecuta sobre el ejemplo en dos pasos: 38
39 Partiendo de la última expresión,(X)(Y){ p(X) { [ p(Y) p(f(X,Y))] [q(X, g(X)) p(g(X))]}} se aplica primero la ley distributiva: (X)(Y){ { p(X) [ p(Y) p(f(X,Y))]} { p(X) [q(X, g(X)) p(g(X))]}} Aplicando de nuevo la ley distributiva y la asociativa: (X)(Y){ [ p(X) p(Y) p(f(X,Y))] [ p(X) q(X, g(X)) ] [ p(X) p(g(X))]} 39
40 7. Eliminar los cuantificadores universales7. Eliminar los cuantificadores universales. Se trata de una eliminación convencional, no teórica, pues se asume que toda variable que aparezca está cuantificada universalmente. La función de Skolem adquiere sentido, dado que al no aparecer otras variablesque las universales, pueden eliminarse sus cuantificadores por convenio. En nuestro ejemplo: [ p(X) p(Y) p(f(X,Y))] [ p(X) q(X, g(X)) ] [ p(X) p(g(X))] 40
41 8. Eliminar los conectores conjuntivos (AND). Dado que la fómula se corresponde con una conjunción de subfómulas, éstas deberán verificarse por separado para que se verifique la fórmula principal. Esto produce, en nuestro caso, el siguiente conjunto de fórmulas: p(X) p(Y) p(f(X,Y)) p(X) q(X, g(X)) p(X) p(g(X)) 41
42 9. Renombrar las variables9. Renombrar las variables. para que no aparezca la misma variable en dos cláusulas. p(X) p(Y) p(f(X,Y)) p(U) q(U, g(U)) p(W) p(g(W)) * * * Mediante este proceso se termina en una representación en forma de cláusulas. Así de una una única fórmula pueden resultar varias cláusulas que son más modulares y de estructura más simple. 42
43 Proceso de paso a cláusulas 1. Eliminar los símbolos de implicación 2. Mover las negaciones hasta las fórmulas atómicas 3. Renombrar variables 4. Eliminar los cuantificadores existenciales. 5. Desplazar los cuantificadores universales 6. Convertir los operadores AND en los más externos 7. Eliminar los cuantificadores universales. 8. Eliminar los conectores conjuntivos (AND). 9. Renombrar las variables. 43
44 Un ejemplo del mundo de los bloquesAcerca de los bloques conocemos tres cosas: A. Que un bloque está encima de algo que no es una pirámide. B. Que no existe ningún objeto que esté debajo de un bloque y, a la vez, encima del mismo. C. Que no hay nada que no sea un bloque y que también sea lo mismo que el bloque. (X) { bloque(X) [(Y) (encima(X,Y) piramide(Y)) (Y) (encima(X,Y) encima(Y,X)) (Y) ( bloque(Y) igual(X,Y))]} 44
45 1. Eliminar las implicaciones0. La fórmula inicial (X) { bloque(X) [ (Y) (encima(X,Y) piramide(Y)) (Y) (encima(X,Y) encima(Y,X)) (Y) ( bloque(Y) igual(X,Y))]} 1. Eliminar las implicaciones (X) { bloque(X) [ (Y) (encima(X,Y) piramide(Y)) (Y) (bloque(Y) igual(X,Y))]} 2. Mover las negaciones hasta las fórmulas atómicas (X) { bloque(X) [ (Y) (encima(X,Y) piramide(Y)) (Y) ( encima(X,Y) encima(Y,X)) (Y) (bloque(Y) igual(X,Y))]} 45
46 3. Renombrar las variables(X) { bloque(X) [ (Y) (encima(X,Y) piramide(Y)) (Z) ( encima(X,Z) encima(Z,X)) (W) (bloque(W) igual(X,W))]} 4. Eliminar los cuantificadores existenciales (X) { bloque(X) [ (encima(X,g(X)) piramide(g(X))) 5. Desplazar los cuantificadores universales (X)(Z)(W){ bloque(X) [ (encima(X,g(X)) piramide(g(X))) ( encima(X,Z) encima(Z,X)) (bloque(W) igual(X,W))]} 46
47 6. Convertir los operadores AND en los más externos(X)(Z)(W){ bloque(X) [ (encima(X,g(X)) piramide(g(X))) ( encima(X,Z) encima(Z,X)) (bloque(W) igual(X,W))]} paso 1. (X)(Z)(W){( bloque(X) (encima(X,g(X)) piramide(g(X)))) ( bloque(X) encima(X,Z) encima(Z,X)) ( bloque(X) bloque(W) igual(X,W))]} paso 2. (X)(Z)(W){( bloque(X) encima(X,g(X))) ( bloque(X) piramide(g(X))) 47
48 7. Eliminar los cuantificadores universales( bloque(X) encima(X,g(X))) ( bloque(X) piramide(g(X))) ( bloque(X) encima(X,Z) encima(Z,X)) ( bloque(X) bloque(W) igual(X,W)) 8. Eliminar los conectores AND bloque(X) encima(X,g(X)) bloque(X) piramide(g(X)) bloque(X) encima(X,Z) encima(Z,X) bloque(X) bloque(W) igual(X,W) 48
49 9. Renombrar las variables bloque(X) encima(X,g(X)) bloque(Y) piramide(g(Y)) bloque(U) encima(U,Z) encima(Z,U) bloque(V) bloque(W) igual(V,W) Nótese que la función de Skolem tiene la semántica de identificar el apoyo de X. Si la renombramos a “soporte(X)” y representamos las cláusulas como implicaciones obtenemos: bloque(X) encima(X, soporte(X)) bloque(Y) piramide(soporte(Y)) bloque(U) encima(U,Z) encima(Z,U) bloque(V) bloque(W) igual(V,W) 49
50 C. (X)(pompeyano(X) romano(X)) D. dirigente(césar) A. hombre(marco) B. pompeyano(marco) C. (X)(pompeyano(X) romano(X)) D. dirigente(césar) E. (X)(romano(X) leal(X,césar) odia(X,césar)) F. (X)(hombre(X) (Y) leal(X,Y) G. (X)(Y) (hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) H. intenta_asesinar(marco, césar) I. (X) (romano(X) odia(X, césar)) 50
51 Proceso de paso a cláusulas1. Eliminar los símbolos de implicación A. hombre(marco) B. pompeyano(marco) C. (X)( pompeyano(X) romano(X)) D. dirigente(césar) E. (X)( romano(X) leal(X,césar) odia(X,césar)) F. (X)( hombre(X) (Y) leal(X,Y) G. (X){ (Y) (hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) } H. intenta_asesinar(marco, césar) I. (X) (romano(X) odia(X, césar)) 51
52 Proceso de paso a cláusulas2. Mover las negaciones hasta las fórmulas atómicas A. hombre(marco) B. pompeyano(marco) C. (X)( pompeyano(X) romano(X)) D. dirigente(césar) E. (X)( romano(X) leal(X,césar) odia(X,césar)) F. (X)( hombre(X) (Y) leal(X,Y) G. (X)(Y) ( hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) H. intenta_asesinar(marco, césar) I. (X) (romano(X) odia(X, césar)) 3. Renombrar las variables 52
53 Proceso de paso a cláusulas4. Eliminar los cuantificadores existenciales A. hombre(marco) B. pompeyano(marco) C. (X)( pompeyano(X) romano(X)) D. dirigente(césar) E. (X)( romano(X) leal(X,césar) odia(X,césar)) F. (X)( hombre(X) leal(X, g(X)) G. (X)(Y) ( hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) H. intenta_asesinar(marco, césar) I. romano(f) odia(f, césar)) 53
54 Proceso de paso a cláusulas5. Desplazar los cuantificadores universales 6. Convertir los operadores AND en los más externos A. hombre(marco) B. pompeyano(marco) C. (X)( pompeyano(X) romano(X)) D. dirigente(césar) E. (X)( romano(X) leal(X,césar) odia(X,césar)) F. (X)( hombre(X) leal(X, g(X)) G. (X)(Y) ( hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y)) H. intenta_asesinar(marco, césar) I. romano(f) odia(f, césar)) 54
55 Proceso de paso a cláusulas7. Eliminar los cuantificadores universales A. hombre(marco) B. pompeyano(marco) C. pompeyano(X) romano(X) D. dirigente(césar) E. romano(X) leal(X,césar) odia(X,césar) F. hombre(X) leal(X, g(X)) G. hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y) H. intenta_asesinar(marco, césar) I. romano(f) odia(f, césar)) 55
56 Proceso de paso a cláusulas8. Eliminar los conectores AND A. hombre(marco) B. pompeyano(marco) C. pompeyano(X) romano(X) D. dirigente(césar) E. romano(X) leal(X,césar) odia(X,césar) F. hombre(X) leal(X, g(X)) G. hombre(X) dirigente(Y) intenta_asesinar(X,Y) leal(X,Y) H. intenta_asesinar(marco, césar) I1. romano(f) I2. odia(f, césar)) 56
57 Proceso de paso a cláusulas8. Renombrar las variables A. hombre(marco) B. pompeyano(marco) C. pompeyano(X) romano(X) D. dirigente(césar) E. romano(Y) leal(Y,césar) odia(Y,césar) F. hombre(Z) leal(Z, g(Z) G. hombre(W) dirigente(K) intenta_asesinar(W,K) leal(W,K) H. intenta_asesinar(marco, césar) I1. romano(f) I2. odia(f, césar)) 57
58 Teorema + Axiomas (como fórmulas bien formadas, fbf)Lo que queremos hacer ... Teorema + Axiomas (como fórmulas bien formadas, fbf) + Teorema + Axiomas (como cláusulas) + Método de resolución por refutación Unificación Unificación Demostración automática de teoremas 58
59 Unificación y sustituciónEjemplos: Definir las sustituciones necesarias para unificar el predicado p(X, f(Y), b) con cada uno de los siguientes predicados: P1: p(g(Z), f(a), b) P2: p(X, f(a), b) P3: p(Z, f(U), b) P4: p(c, f(a), b) 59
60 Unificación y sustituciónEl proceso de unificación determina las condiciones y posibilidades de sustitución de un predicado por otro. Por ejemplo, en el caso de los siguientes axiomas: p(X) q(X) p(a) la demostración de q(a) es consecuencia de la regla de especialización Universal aplicada a: para producir p(a) q(a) También puede interpretarse como que se ha procedido a realizar la sustitución de p(X) por p(a), previa unificación de X con a. El proceso de sustitución de términos, denominado Unificación, para lograr que dos expresiones sean idénticas es fundamental en el proceso de demostración de teoremas en la lógica de predicados de primer orden. 60
61 Unificación y sustituciónUn proceso de unificación puede ser representado mediante un operador constituido por un conjunto de pares de términos ordenados por: = { v1 t1, v2 t2, ..., vn tn} donde el par vi ti, indica que la variable vi es sustituida por el término ti. Así el predicado p se transforma mediante la sustitución indicada por en p(... , vk, ...) = p(... , tk, ...). NOTA: También es muy habitual la notación equivalente = { v1/ t1, v2/ t2, ..., vn/ tn} 61
62 Unificación y sustituciónEjemplos: Definir las sustituciones necesarias para unificar el predicado p(X, f(Y), b) con cada uno de los siguientes predicados: P1: p(g(Z), f(a), b) P2: p(X, f(a), b) P3: p(Z, f(U), b) P4: p(c, f(a), b) 1 = { X g(Z), Y a } 2 = { Y a } 3 = { X Z, Y U } 4 = { X c, Y a } 62
63 Unificación y sustituciónEl proceso de unificación implica la sustitución de una variable por otro término que puede ser variable, constante o functor, En este último caso el functor no puede contener la variable sustituida. Es evidente que no siempre es posible unificar dos realizaciones de un mismo predicado. Por ejemplo q(a, f(X), X) y q(c, f(d), b) no son unificables. La composición de dos sustituciones 1 y 2, se denota por 1 2 y es la sustitución que resulta de aplicar la sustitución 2 a los términos de 1 y de añadir a continuación los pares de sustituciones de 2 sobre las variables no contenidas entre las variables de 1. { Z f(X,Y), U X } { X a, Y b, W c, Z d } { Z f(a,b), U a, X a, Y b, W c } 63
64 Unificación y sustituciónSe puede demostrar que : A. [L1]2 = L [12] B. (12) 3 = 1 (23), Asociatividad C. 12 21 no es conmutativa Diremos que dos predicados, E1 y E2, son unificables, y lo representaremos por {E1, E2}, si existe una sustitución tal que se verifica: E1 = E2 A la sustitución la denominaremos Unificador de E1 y E2. Ejemplo: Dados p(X, f(Y), b) y p(X, f(b), b) y la sustitución = { X a, Y b }, decimos que es un unificador de estos dos predicados porque los convierte en p(a, f(b), b). 64
65 Unificación y sustituciónAunque = { X a, Y b } es un unificador de estos dos predicados no es el más simple de los unificadores posibles (se le podría denominar alternativamente “más general”) para este conjunto, que este caso sería = { Y b }. Así si es el más simple unificador de { Ei } se verifica que si es un unificador de { Ei } entonces existe una sustitución s tal que: { Ei } s = { Ei } Un algoritmo recursivo que nos permite descubrir si dos predicados son unificables o no, y, en su caso, hallar el unificador más simple. 65
66 Algoritmo de UnificaciónEtapas del algoritmo. 1. Comprobaremos si los símbolos de los predicados son los mismos. En caso negativo los predicados no son unificables. 2. Si los predicados son iguales, han de tener la misma aridad (nº de argumentos). En caso negativo los predicados no son unificables. 3. Comprobaremos los argumentos por pares correspondientes, aplicando el algoritmo recursivamente (es necesario si los argumentos contienen functores), abortando el proceso desde el momento en que un par de argumentos no sea unificable. 66
67 Algoritmo de UnificaciónUnifica(e1, e2) { 1. Si e1 o e2 son ambos variables o constantes, entonces 1.a Si e1 y e2 son idénticos, entonces devolver { }. 1.b Si e1 es una variable, entonces 1.b.1 Si e1 aparece dentro de e2 entonces devolver {FALLO} en otro caso, devolver { e1 e2 }. 1.c Si e2 es una variable, entonces 1.c.1 Si e2 aparece dentro de e1 entonces devolver {FALLO} en otro caso, devolver { e2 e1 }. 1.d Devolver {FALLO} 2. Si los símbolos de los predicados e1 y e2 son diferentes o tienen diferente aridad entonces devolver {FALLO}. 3. Hacer SUBS = NIL (al final del proceso SUBS contendrá las sustituciones necesarias para unificar e1 y e2). (continúa ...) 67
68 Algoritmo de UnificaciónUnifica(e1, e2) { ... 4. Para cada uno de los argumentos de e1 (indexados por i) 4.a Invocar Unifica con los i-ésimos argumentos de e1 y e2, poniendo el resultado en s. 4.b Si s es igual a FALLO, entonces devolver {FALLO}. 4.c Si s es diferente de { }, entonces 4.c.1 Aplicar la sustitución s sobre el resto de argumentos de e1 y e2 4.c.2 Añadir s a las sustituciones ya contenidas en SUBS. 5. Devolver SUBS. } 68
69 Algoritmo de UnificaciónEjercicios: Tracear la operación del algoritmo de unificación para cada uno de los siguientes pares de predicados. A. f(marcos), f(césar) B. f(X), f(g(Y)) C. f(marcos, g(X,Y)), f(X, g(césar, marcos)) D. p(X, X), p( g(X), g(X)) E. p(X, X), p( Y, g(X)) F. p(X, f(x)), p(Y, Y) G. p(Y, Y, b), p(Z, X, Z) H. p(f(X,X), a), p(f(Y, f(Y,a)), a) 69
70 Resolución por refutaciónMétodo de demostración de teoremas Robinson, 1965 Basado en el principio de refutación Relativamente sencillo de automatizar IDEA. Si queremos demostrar un teorema dado en base a un conjunto de axiomas que suponemos consistente, podemos hacerlo mostrando que el conjunto formado por la negación del teorema y el conjunto de axiomas es inconsistente. Si tal inconsistencia se demuestra será porque el teorema era cierto. 70
71 Decidibilidad y ConsistenciaSistema formal: Validez de una expresión: Decidibilidad: Un conjunto de expresiones básicas y un conjunto de reglas de generación de nuevas expresiones procedimientos efectivos : desarrollos que involucran un número finito de operaciones elementales y de posiciones de memoria Se dice que una expresión es válida en un sistema formal si es posible derivar la misma a partir de las expresiones básicas Un sistema formal U se dice decible si existen procedimientos efectivos para determinar la validez dentro de U de las expresiones V y V 71
72 Decidibilidad y ConsistenciaIndecidibilidad: Semi-decibilidad: Consistencia: Un sistema formal U se dice indecible si no es posible determinar la validez V y V de forma efectiva Cuando sólo es posible determinar de forma efectiva la validez de una de las expresiones V o V Un sistema formal U se dice consistente en sentido fuerte, si sólo una de las expresiones V o V es válida en U. Es evidente que un sistema consistente debe ser Decible. 72
73 Decidibilidad y ConsistenciaInconsistencia: Un sistema formal U se dice inconsistente si ambas expresiones V y V son válidas en U. Un sistema lógico L compuesto de fórmulas básicas o axiomas y reglas de inferencia constituye un sistema formal. Un sistema lógico L que contiene las expresiones F y F constituye un sistema inconsistente por cuanto F y F son válidas en L. 73
74 Decidibilidad y ConsistenciaSe han desarrollado procedimientos efectivos capaces de demostrar la inconsistencia de un sistema lógico. Sin embargo, no existen tales procedimientos para demostrar su consistencia. Por ello un sistema lógico es un sistema Semi-decible y no pueden definirse criterios de consistencia fuerte, usándose en su defecto otro criterio de consistencia débil. Definición: un sistema lógico que no es Inconsistente se dice que es consistente en sentido débil 74
75 Decidibilidad y ConsistenciaSi A es un conjunto de cláusulas lógicas consistentes, denominadas Axiomas, y T es otra cláusula, denominada Teorema, entonces si T es una consecuencia lógica de A se debe verificar: 1. El conjunto A T es consistente 2. El conjunto A T es inconsistente Sólo la segunda propiedad es verificable de forma efectiva, de donde se deduce intuitivamente un procedimiento de demostración de teoremas que consiste en demostrar la inconsistencia de A T . A este procedimiento se le denomina de Resolución por Refutación del Teorema. 75
76 Cláusula resolvente Sean dos cláusulas, que denominaremos cláusulas padres, que contengan respectivamente, una misma proposición, negada y sin negar, cada una de ellas. Como es el caso de la proposición p1 en el siguiente ejemplo: p1 v p2 v ... v pn p1 v q2 v ... v qm Ambas cláusulas forman parte de un sistema que se asume consistente y, por tanto, son ciertas. Puede construirse entonces una nueva cláusula, denominada cláusula resolvente a partir de la disyunción de ambas eliminando la proposición que aparece doblemente. Esto es: (p1 v p2 v ... v pn) v ( p1 v q2 v ... v qm) (p1 v p1) v (p2 v ... v pn v q2 v ... v qm) p2 v ... v pn v q2 v ... v qm 76
77 Cláusula resolvente La nueva cláusula (cláusula resolvente) debe ser cierta por cuanto las cláusulas padre forman un conjunto de cláusulas consistente con lo que el conjunto que resulta de añadir la cláusula resolvente al conjunto de cláusulas anterior sigue siendo consistente. Los siguientes son algunos ejemplos de la aplicación del método de la cláusula resolvente: ( p v q) v p q (modus ponens) (p v q) v ( p v q) q ( p v p) nil (inconsistencia) ( p v q) v ( q v r) p v r (encadenamiento de reglas) (p v q) v ( p v q) q v q (tautología) Nótese que en el último caso, también podría resolverse sobre q y obtendríamos como cláusula resolvente p v p. Lo que no es correcto es resolver doblemente sobre p y q y obtener un resolvente nulo. 77
78 Cláusula resolvente (p v q) v ( p v q) q v q (tautología)Una forma de ver que la doble resolución es un error es considerar el caso sencillo anterior cuando se resuelve doblemente. En ese caso obtendríamos la cláusula nula, indicando una inconsistencia. Sin embargo, podemos comprobar que ambas cláusulas son consistentes cuando ambos predicados son verdaderos, lo que indica que la conclusión de inconsistencia que se deriva de la doble resolución es incorrecta. La idea que subyace en el método de resolución se basa en que la fórmula ((p v ) ( p v )) ( v ) es una tautología (demostrarlo empleando una tabla de verdad). Por el contrario, puede comprobarse que la fórmula similar que debería sustentar la doble resolución, ((p v r v ) ( p v r v )) ( v ) , donde r es q o q, no es válida. 78
79 Resolución por RefutaciónLa resolución por refutación consiste esencialmente en aplicar el método de la cláusula resolvente para eventualmente alcanzar el resolvente nulo. Si esto es posible se habrá demostrado la inconsistencia del conjunto formado por los axiomas (cuya validez está garantizada) y el teorema negado, en cuyo caso el teorema se considera demostrado. a v b b v c a c a v c c nil 79
80 Resolución por RefutaciónPara poder aplicar el método de la cláusula resolvente a predicados y no sólo a proposiciones es preciso primeramente unificar las cláusulas para conseguir que los términos de los predicados complementarios sean idénticos. Ejemplo: Sean las siguientes cláusulas padre. p(X, f(a)) p(X, f(Y)) q(Y) p(Z, f(a)) q(Z) Se puede encontrar un resolvente empleando bien p o bien q como predicados complementarios. Si elegimos p, el unificador será: { p(X, f(a)), p(Z, f(a)) } con la sustitución = { X Z } que produce la cláusula resolvente: p(Z, f(Y)) q(Y) q(Z) 80
81 Resolución por RefutaciónOtra forma de generar una cláusula resolvente más sencilla consiste en eliminar alguna de las realizaciones del mismo predicado p en alguna de las cláusulas padre. Por ejemplo, encontrando un unificador y absorbiendo una de las realizaciones. p(X, f(a)) p(X, f(Y)) q(Y) p(Z, f(a)) q(Z) Así : { p(X, f(a)), p(X, f(Y)) } con la sustitución = { Y a } convierte las cláusulas padre en: p(X, f(a)) q(a) Aplicando el unificador = { Z X } resolviendo, obtenemos como resolvente: q(a) q(X) 81
82 Resolución por RefutaciónUna idea clave: Si el par de cláusulas padre se toma de un conjunto de cláusulas consistentes, entonces, dado que la cláusula resolvente es una consecuencia lógica de las anteriores, también es consistente el conjunto resultante de añadir el resolvente al conjunto original. 82
83 Resolución por RefutaciónIdea sobre la que se desarrolla el algoritmo: Hasta que se encuentre la cláusula nula se exploran pares de cláusulas padre, incluyendo - en caso de fracaso - el resolvente en el conjunto de cláusulas. El proceso para si: 1. El resolvente generado es nulo: se ha demostrado el teorema. 2. Si no existe ningún par de cláusulas que se puedan producir un resolvente, entonces no se puede demostrar la inconsistencia del conjunto y se dice que el conjunto no es completo. Esto significa que el teorema no es una consecuencia lógica de los axiomas y, por tanto, se puede suponer falso. 83
84 Algoritmo: Resolución por Refutación0. Se supone que tanto los axiomas como la negación del teorema han sido transformados en cláusulas. 1. Incluir en el conjunto de cláusulas TRABAJO el conjunto de axiomas y el teorema negado. 2. Repetir hasta que se produzca la cláusula nula, o no se encuentre ningún resolvente: 2.a Encontrar en TRABAJO un par de cláusulas que puedan resolverse y obtener el resolvente. Eliminar los elementos duplicados. 2.b Descartar la cláusula si contiene un predicado y su negación. 2.c Si el resolvente no está en TRABAJO, añadirlo. 3. Si se ha encontrado la cláusula nula, el teorema es cierto. En caso contrario, el teorema se supone falso. 84
85 A.1 “Cualquiera que puede leer es un ilustrado” (X)(r(X) l(X)) Ejemplo: Axiomas A.1 “Cualquiera que puede leer es un ilustrado” (X)(r(X) l(X)) A.2 “Los delfines no son ilustrados” (X)(d(X) l(X)) A.3 “Algunos delfines son inteligentes” (X)(d(X) i(X)) Teorema. T. “Algunos que son inteligentes, no pueden leer” (X)(i(X) r(X)) Axiomas. A.1 “Cualquiera que puede leer es un ilustrado” A.2 “Los delfines no son ilustrados” A.3 “Algunos delfines son inteligentes” Teorema. T. “Algunos que son inteligentes, no pueden leer” 85
86 Ejemplo: Paso a cláusulasAxiomas A.1 (X)(r(X) l(X)) A.2 (X)(d(X) l(X)) A.3 (X)(d(X) i(X)) Teorema. T. (X)(i(X) r(X)) r(X) l(X) d(Y) l(Y) d(a) i(a) i(Z) r(Z) donde a es una función de Skolem constante 86
87 Ejemplo: Grafo de resolución i(Z) r(Z) i(a) {Z a} r(a) r(X) l(X) {X a} d(Y) l(Y) l(a) {Y a} d(a) d(a) { } 87
88 Obtención de respuestasEl procedimiento de Resolución por Refutación demuestra teoremas del tipo (X) p(X) para los que, además de concluir si el teorema es verdadero o falso, interesa conocer el valor de X que satisface el teorema. A este proceso se le denomina obtención de repuestas Se pueden emplear dos procedimientos 88
89 Obtención de respuestasProcedimiento A: 1. Demostrar el teorema por el procedimiento ya explicado. 2. Añadir al conjunto de cláusulas inicial, no el teorema negado (p(X)), sino la disyunción de éste con su negado, es decir, (p(X) p(X)) (una tautología). 3. Seguir los mismos pasos que condujeron a la demostración del teorema. Dado que la cláusula del teorema contiene una tautología no se concluirá en el resolvente nulo, sino que se concluirá en la cláusula del teorema. 4. La respuesta es el resolvente final. 89
90 Axiomas: A1. (X)( juega(pedro, X) juega(luis, X)) Ejemplo: Axiomas: A1. (X)( juega(pedro, X) juega(luis, X)) A2. juega(pedro, fútbol). Teorema: T. (X) juega(luis, X) El problema consiste en demostrar el teorema y, además, en saber a qué juega luis. 90
91 Expresados en forma clausular y negando el teorema: A1. juega(pedro, X) juega(luis, X)) A2. juega(pedro, fútbol). T. juega(luis, Y) El árbol de refutación sería: juega(luis, Y) juega(pedro, X) juega(luis, X) {YX} juega(pedro, X) juega(pedro, fútbol). {Xfútbol} {} 91
92 Y la obtención de la respuesta sería: juega(luis, Y) juega(luis, Y) juega(pedro, X) juega(luis, X) {YX} juega(pedro, X) juega(luis, X) juega(pedro, fútbol). {Xfútbol} juega(luis, fútbol) 92
93 (p(X) respuesta(X)) Puede generalizarse el procedimiento anterior de manera que en lugar de incluir la tautología (p(X) p(X)), se incluya la cláusula: (p(X) respuesta(X)) donde “respuesta” es un predicado comodín, que no puede aparecer en el conjunto de axiomas. Dado que este predicado no aparece en el resto del conjunto es imposible que pueda desaparecer del árbol modificado de refutación y, por tanto, no se concluirá en la cláusula nula. 93
94 Obtención de respuestasProcedimiento B: 1. Añadir al conjunto de cláusulas de los axiomas la cláusula (p(X) respuesta(X)). El predicado comodín debe contener tantos términos como respuestas se deseen, p.e. (p(X,Y) respuesta(X,Y)) 2. Realizar la demostración del teorema, utilizando como objetivo no la cláusula nula, sino una cláusula que contiene solamente el predicado comodín “respuesta”. 3. Las respuestas son los términos del predicado comodín en el estado final. 94
95 Con este procedimiento, la obtención de la respuesta sería: juega(luis, Y) respuesta(Y) juega(pedro, X) juega(luis, X) {YX} juega(pedro, X) respuesta(X) juega(pedro, fútbol). {Xfútbol} respuesta(fútbol) 95
96 A partir del siguiente conjunto de axiomas, A1. X (c(X) s(X)) Problema: A partir del siguiente conjunto de axiomas, A1. X (c(X) s(X)) A2. X ( g(X) d(X)) A3. (X (g(X) c(X))) Aplicar el método de resolución por refutación para demostrar los siguientes teoremas: TEOREMA 1. X (s(X) d(X)) TEOREMA 2. X ( s(X) d(X)) NOTA: Es importante detallar bien cada paso del proceso de demostración 96
97 Convirtiendo en cláusulas: A1. c(X) s(X) A2. g(Y) d(Y) Problema: Convirtiendo en cláusulas: A1. c(X) s(X) A2. g(Y) d(Y) A3. g(Z) c(Z) Negando los teoremas: T1. (X (s(X) d(X))) T2. (X ( s(X) d(X))) Conviertiendo los teoremas negados en cláusulas: T1. s(g) d(g) T2. s(g) d(g) 97
98 Resolvamos primero para el T2 d(g) g(Y) d(Y) {Y g} g(g) g(Z) c(Z) {Z g} c(g) c(X) s(X) {X g} s(g) s(g) {} 98
99 OJO: No se puede resolver doblementeResolvamos para el T1 s(g) d(g) g(Y) d(Y) {Y g} g(Z) c(Z) s(g) g(g) {Z g} s(g) c(g) c(X) s(X) {X g} c(g) c(g) OJO: No se puede resolver doblemente 99
100 Sistemas Basados en Reglas (SBRs)Elemento común a todos los SBRs es la utilización de la estructura elemental: SI Antecedentes ENTONCES Consecuentes mediante este tipo de estructura es fácil capturar en la base de conocimiento de un sistema Relaciones de Dependencia. Mecanismos de razonamiento Dirigidos por los hechos o datos Dirigidos por hipótesis u objetivos 100
101 batería no_descargada Entonces realiza test_del_motor_de_arranque Ejemplo: R1. Si motor no_arranca y batería no_descargada Entonces realiza test_del_motor_de_arranque R2. Si motor no_arranca Entonces realiza test_de_la_batería R3. Si batería descargada Entonces respuesta “cambiar la batería” y FIN. 101
102 Mecanismos de razonamiento Dirigidos por los hechos o datos Se comienza considerando las piezas de evidencias disponibles, hechos o datos, hast alcanzar una conclusión. Dirigidos por hipótesis u objetivos Cuando existe un gran número de datos puede ser muy ineficiente considerar todos los datos, algunos de los cuales pueden ser irrelevantes. Se puede, en cambio, seleccionar una posible conclusión y tratar de probar su validez viendo si los datos apoyan esta hipótesis. 102
103 R7: IF TipoFruta = frutoDeSuelo AND Superficie = suave AND Color = amarillo THEN Fruta = calabaza R8: IF TipoFruta = frutoDeSuelo AND Superficie = rugosa AND THEN Fruta = melón R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R10: IF TipoFruta = frutoDeArbol AND TipoSemilla = múltiple THEN Fruta = naranja R11: IF TipoFruta = frutoDeArbol AND Color = rojo AND TipoSemilla = nuez THEN Fruta = cereza R12: IF TipoFruta = frutoDeArbol AND Color = naranja AND THEN Fruta = melocotón R13: IF TipoFruta = frutoDeArbol AND Color = naranja OR rojo OR verde AND TipoSemilla = múltiple THEN Fruta = manzana R14: IF TipoFruta = frutoDeArbol AND Color = púrpura AND THEN Fruta = ciruela R7: IF TipoFruta = frutoDeSuelo AND Superficie = suave AND Color = amarillo THEN Fruta = calabaza R8: IF TipoFruta = frutoDeSuelo AND Superficie = rugosa AND THEN Fruta = melón R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R10: IF TipoFruta = frutoDeArbol AND TipoSemilla = múltiple THEN Fruta = naranja R1: IF Forma = larga AND Color = verde OR amarillo THEN Fruta = plátano R2: IF Forma = redonda OR ovoide AND Diámetro > 10 cm THEN TipoFruta = frutoDeSuelo R3: IF Forma = redonda AND Diámetro < 10 cm THEN TipoFruta = frutoDeArbol R4: IF NumeroSemillas = 1 THEN TipoSemilla = nuez R5: IF NumeroSemillas > 1 THEN TipoSemilla = múltiple R6: IF TipoFruta = frutoDeSuelo AND Color = verde THEN Fruta = sandía 103
104 Mecanismos de razonamiento Dirigidos por los hechos o datos Se selecciona una regla para ejecutarla cuando sus premisas se verifican. Este tipo de razonamiento resulta adecuado en problemas en los que se requiera una tarea de síntesis (planificación, diseño, configuración, ...). En estos problemas los datos conducen el proceso y potencialmente existen muchas soluciones que resultarían aceptables. En el ejemplo de las frutas se trataría de llegar a la identificación de la fruta a partir de una serie observaciones iniciales. 104
105 Mecanismos de razonamiento Dirigidos por hipótesis u objetivos Con esta aproximación, se selecciona primero un posible objetivo o hipótesis y se intenta verificar si los datos la corroboran. Resulta adecuado en problemas de diagnóstico en los que el número de conclusiones es pequeño frente al potencial número de datos. En el ejemplo de las frutas, se seleccionaría primero una hipótesis de fruta y se intentaría verificar que la hipótesis es compatible con los datos. 105
106 Arquitectura de un SBR Usuario Intérprete Intérprete Entidades(Base de datos o hechos) Entidades (Base de datos o hechos) Selector Selector Reglas Reglas Agenda Agenda Metaconocimiento Metaconocimiento Intérprete: “Ejecuta“ la Agenda y, eventualmente, interactúa con el usuario. Agenda: Contiene las reglas activadas y pendientes de ejecutar. Metaconocimiento: Criterios de selección de reglas a utilizar por el selector. Base de reglas: Base de conocimiento donde cada elemento es una regla que expresa una relación de dependencia entre los objetos y sus valores (en algunos sistemas con coeficientes de certeza). Selector: Selecciona las reglas candidatas a ser activadas (se verifica el antecedente). Esta operación puede estar guida por metaconocimiento. Procesos Base de datos: tuplas del tipo
107 R7: IF TipoFruta = frutoDeSuelo AND Superficie = suave AND Color = amarillo THEN Fruta = calabaza R8: IF TipoFruta = frutoDeSuelo AND Superficie = rugosa AND THEN Fruta = melón R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R10: IF TipoFruta = frutoDeArbol AND TipoSemilla = múltiple THEN Fruta = naranja R11: IF TipoFruta = frutoDeArbol AND Color = rojo AND TipoSemilla = nuez THEN Fruta = cereza R12: IF TipoFruta = frutoDeArbol AND Color = naranja AND THEN Fruta = melocotón R13: IF TipoFruta = frutoDeArbol AND Color = naranja OR rojo OR verde AND TipoSemilla = múltiple THEN Fruta = manzana R14: IF TipoFruta = frutoDeArbol AND Color = púrpura AND THEN Fruta = ciruela R7: IF TipoFruta = frutoDeSuelo AND Superficie = suave AND Color = amarillo THEN Fruta = calabaza R8: IF TipoFruta = frutoDeSuelo AND Superficie = rugosa AND THEN Fruta = melón R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R10: IF TipoFruta = frutoDeArbol AND TipoSemilla = múltiple THEN Fruta = naranja R1: IF Forma = larga AND Color = verde OR amarillo THEN Fruta = plátano R2: IF Forma = redonda OR ovoide AND Diámetro > 10 cm THEN TipoFruta = frutoDeSuelo R3: IF Forma = redonda AND Diámetro < 10 cm THEN TipoFruta = frutoDeArbol R4: IF NumeroSemillas = 1 THEN TipoSemilla = nuez R5: IF NumeroSemillas > 1 THEN TipoSemilla = múltiple R6: IF TipoFruta = frutoDeSuelo AND Color = verde THEN Fruta = sandía 107
108 Dirigidos por los hechos o datos Dirigidos por hipótesis u objetivosInferencia en SBRs Razonamiento hacia-adelante o guiado por los datos Hasta que se obtenga la verificación del objetivo: 1. Aplicar la primera regla de la Agenda, realizando las operaciones especificadas en el consecuente de la regla. 2. Verificar los antecedentes de alguna regla, considerada adecuado por el Selector. Si tal es el caso, añadir la regla a la Agenda de acuerdo con algún criterio de inserción (ver más abajo). 3. Si no existen reglas en la Agenda y no se activa ninguna otra regla, entonces no se puede alcanzar el Objetivo. En este caso, ejecutar alguna acción específica. Dirigidos por los hechos o datos Dirigidos por hipótesis u objetivos 108
109 Estrategias de inserción en la Agenda Considerando la Agenda como una lista ... 1. Insertar por la cabeza de la lista Estrategia en profundidad 2. Insertar por la cola de la lista Estrategia en anchura 3. Insertar de acuerdo a algún criterio de prioridad (metaconocimiento) Estrategia heurística en escalada Criterios de poda Podar las reglas que se activan empleando un umbral sobre la certeza de los antecedentes. De esta manera es posible aumentar la eficiencia del selector. Acción de las meta-reglas Los consecuentes de ciertas meta-reglas pueden fijar los criterios de funcionamiento del selector. Un algoritmo más eficiente para la selección de reglas RETE (ver una descripción en el cap. 5 de [GONZ-93]) 109
110 Ejemplo de las frutas (forward reasoning): Base de datos: Diámetro 2.5 cm, NúmeroSemilla = 1 Forma = redonda, Color = rojo R3: IF Forma = redonda AND Diámetro < 10 cm THEN TipoFruta = frutoDeArbol R4: IF NumeroSemillas = 1 THEN TipoSemilla = nuez R11: IF TipoFruta = frutoDeArbol AND Color = rojo AND TipoSemilla = nuez THEN Fruta = cereza Ciclo Reglas aplicables Regla seleccionada Hechos derivados , TipoFruta = frutoDeArbol , TipoSemilla = nuez , 4, Fruta = cereza , 4, 110
111 Razonamiento hacia-atrás o guiado por objetivo En este caso las acciones pendientes contenidas en la Agenda son configuraciones de trabajo del Objetivo. Inicialmente la Agenda contiene la forma primitiva del Objetivo. 1. Introducir el Objetivo en la Agenda 2. Hasta que se alcance el objetivo vacío o la Agenda esté vacía. 2.a Seleccionar el primer objetivo de la Agenda 2.b Si algún subobjetivo se verifica, reducir el Objetivo y añadir la forma reducida a la Agenda en base a algún criterio. 2.c Si algún subobjetivo está presente en los consecuentes de alguna regla, considerada adecuada, generar nuevos Objetivos reemplazando el subobjetivo inicial por los antecedentes de la regla en cuestión. Añadir los nuevos Objetivos a la Agenda empleando algún criterio. 2.d Si el primer objetivo no puede verificarse, entonces eliminarlo de la Agenda. 3. Si la Agenda está vacía, entonces no se puede alcanzar el Objetivo. En este caso, ejecutar alguna acción específica 111
112 Estrategias específicas En el esquema de inferencia guiado por objetivos es necesario definir múltiples estrategias específicas: 1. Inserción de nuevas formas del objetivo en la Agenda 2. Criterios de priorización de los subobjetivos 3. Orden de consideración de las reglas en la base de conocimiento Observación En un esquema guiado por objetivos, las acciones procedimentales se incluyen en el antecedente. Por contra, en un esquema guiado por los datos, las acciones procedimentales se incluyen en los consecuentes. 112
113 Ejemplo con razonamiento hacia-atrás:Ciclo Objetivos Hechos conocidos Reglas Activas 1 (Fruta) () 1,6,7,8,9,10,11,12,13,14 Regla seleccionada: 1 Valor para el atributo Forma redonda (USUARIO) Ciclo Objetivos Hechos conocidos Reglas Activas 2 (Fruta) (Forma = redonda ) 1,6,7,8,9,10,11,12,13,14 Regla seleccionada: 6 Atributo TipoFruta derivable de las reglas 2 y 3 Ciclo Objetivos Hechos conocidos Reglas Activas 3 (TipoFruta Fruta) (Forma = redonda ) 2,3 R2: IF Forma = redonda OR ovoide AND Diámetro > 10 cm THEN TipoFruta = frutoDeSuelo R3: IF Forma = redonda AND Diámetro < 10 cm THEN TipoFruta = frutoDeArbol Regla seleccionada: 2 Valor para el atributo Diámetro 2.5 cm (USUARIO) 113
114 Ejemplo con razonamiento hacia-atrás:R6: IF TipoFruta = frutoDeSuelo AND Color = verde THEN Fruta = sandía R7: IF TipoFruta = frutoDeSuelo AND Superficie = suave AND Color = amarillo THEN Fruta = calabaza R8: IF TipoFruta = frutoDeSuelo AND Superficie = rugosa AND THEN Fruta = melón Ejemplo con razonamiento hacia-atrás: R2: IF Forma = redonda OR ovoide AND Diámetro > 10 cm THEN TipoFruta = frutoDeSuelo R3: IF Forma = redonda AND Diámetro < 10 cm THEN TipoFruta = frutoDeArbol Regla seleccionada: 2 Valor para el atributo Diámetro 2.5 cm (USUARIO) Ciclo Objetivos Hechos conocidos Reglas Activas 4 (TipoFruta Fruta) ((Forma = redonda ) (Diámetro = 2.5 cm)) 3 Regla seleccionada: 3 Valor para el atributo TipoFruto frutoDeArbol (conclusión R3) Ciclo Objetivos Hechos conocidos Reglas Activas 5 (Fruta) ((Forma = redonda ) (Diámetro = 2.5 cm) (TipoFruta = frutoDeArbol)) ,7,8,9,10,11,12,13,14 114
115 Ejemplo con razonamiento hacia-atrás:R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R11: IF TipoFruta = frutoDeArbol AND Color = rojo AND TipoSemilla = nuez THEN Fruta = cereza Regla seleccionada: 9 Valor para el atributo Color rojo (USUARIO) Ciclo Objetivos Hechos conocidos Reglas Activas 6 (Fruta) ((Forma = redonda ) (Diámetro = 2.5 cm) (Color = rojo) (TipoFruta = frutoDeArbol)) ,12,13,14 Regla seleccionada: 11 Valor para el atributo TipoSemilla nuez (USUARIO) 115
116 Ejemplo con razonamiento hacia-atrás:R9: IF TipoFruta = frutoDeArbol AND Color = naranja AND TipoSemilla = nuez THEN Fruta = albaricoque R11: IF TipoFruta = frutoDeArbol AND Color = rojo AND TipoSemilla = nuez THEN Fruta = cereza Ciclo Objetivos Hechos conocidos Reglas Activas 7 (Fruta) ((Forma = redonda ) (Diámetro = 2.5 cm) (Color = rojo) (TipoSemilla = nuez) (TipoFruta = frutoDeArbol)) ,12,13,14 Regla seleccionada: 11 Valor para el atributo Fruta cereza de R11 En ese momento la lista de objetivos se vacía y el proceso de razonamiento cesa. 116
117 Tipologías de reglas A. Extended MYCIN (EMYCIN)
118 Ventajas e Inconvenientes de los SBRsLas reglas, como unidades de representación de los SBRs presentan las siguientes propiedades: 1. Baja granularidad: unidad de representación muy simple y de escasa capacidad. 2. Alta Independencia: las unidades que componen la base de conocimiento presentan un alto grado de independencia De estas propiedades se derivan las siguientes ventajas e inconvenientes. 118
119 representación uniforme del conocimientoVentajas de los SBRs cada unidad es independiente del resto de la base de conocimiento. Su definición es independiente de su utilización. Modularidad Uniformidad Comprensión Sencillez Generalidad representación uniforme del conocimiento alta inteligibilidad en la semántica de la unidad de conocimiento en los procesos de inferencia por su simplicidad resultan aplicables en casi todos los ámbitos 119
120 Desventajas de los SBRsde los procesos de inferencia, lo que deriva del acceso a un conocimiento altamente disperso y poco estructurado Ineficiencia Bajo nivel Problemas prácticos en la descripción, por lo que no resulta adecuado para representar conocimiento de alto nivel y muy estructurado. El conocimiento es “opaco” Encadenamiento infinito Adición de conocimiento contradictorio Extensión con modificación de reglas 120
121 Conclusiones Los sistemas de producciones o basados en reglas resultan apropiados en dominios donde: el conocimiento está disperso y consiste en muchos hechos y reglas particulares los procesos pueden representarse como un conjunto de acciones independientes el conocimiento puede expresarse con independencia de la forma en la que se utiliza 121
122 Redes Semánticas es_un es_un vehículo coche avión parte_de parte_derueda carrocería motor parte_de parte_de maletero ventana 122
123 Redes Semánticas autor objeto “La insoportable levedad del ser” es_unMilan Kundera evento libro actor acto receptor Juan regalar María es_un es_un persona 123
124 Redes Semánticas Quillian (1967): Modelo de la memoria humanaSchank (1974): Modelos conceptuales del lenguaje humano Una red semántica es una estructura de datos compuesta de: Nodo: una estructura que tiene asociada una correspondencia con un objeto, evento,actor, ..., o en general, con una entidad del ámbito de representación. Arco o enlace: elemento que da estructura al relacionar las entidades representadas por los dos nodos que une. En general es una estructura direccional. 124
125 Ejemplo: “Juan regaló a María un libro en el parque”Proceso de construcción: 1. Identificar las entidades: {juan, libro, parque, maría, regalar, evento} 2. Formular las relaciones binarias entre entidades: acto(e, regalar) actor(e, juan) objeto(e, libro) receptor(e, maría) localización(e, parque) 3. Asociar un nodo a cada elemento. 4. Asociar un enlace a cada relación localización parque objeto libro evento actor acto receptor Juan regalar María 125
126 Ejemplo: Las aves son animalesVolar es la forma normal de desplazamiento para las aves Las aves suelen estar activas durante el día Un albatros es un ave los albatros son blancos y negros Albert y Ross son albatros Un kiwi es un ave los kiwis se desplazan caminando Los kiwis son de color marrón Los kiwis están activos durante la noche Kim es un kiwi 126
127 Ejemplo: animal es_un actividad desplazamiento día ave volar es_unalbatros kiwi Kim color color marrón es_un es_un blanco_negro desplazamiento actividad Albert Ross camina noche 127
128 Ejemplo: La herencia es_un(ave, animal). actividad(ave, día).actividad(kiwi, noche). desplazamiento(ave, volar). desplazamiento(kiwi, caminar). color(albatros, blanco_negro). color(kiwi, marrón). es_un(albatros, ross). es_un(albatros, albert). es_un(kiwi, kim). actividad desplazamiento día ave volar es_un es_un es_un albatros kiwi Kim color color marrón blanco_negro es_un es_un desplazamiento actividad ?- hecho(desplazamiento(kim, Metodo). Metodo = caminar ?- hecho(desplazamiento(ross, Metodo). Metodo = volar Albert Ross caminar noche hecho(Hecho):- Hecho, !. % Propiedad declarada: no se hereda hecho(Hecho):- Hecho =.. [Rel, Arg1, Arg2], es_un(Arg1, SuperArg), % Se escala la jerarquía SuperHecho =.. [Rel, SuperArg, Arg2], hecho(SuperHecho). 128
129 Marcos y Objetos (Frames)Frame AUTOMÓVIL Especialización_de: VEHÍCULO Generalización_de: (BERLINA RANCHERA MONOVOLUMEN) Fabricante: Rango: (FORD MAZDA BMW SAAB) Defecto: MAZDA País_de_fabricación: Rango: (USA JAPÓN ALEMANIA SUECIA) Defecto: JAPÓN Modelo: Rango: () Color: Rango: (NEGRO BLANCO BEIGE ROJO) Si_necesario: (PREGUNTAR_VENDEDOR MIRAR_COCHE) Consumo: Rango: (0-200) Fiabilidad: Rango: (ALTA MEDIA BAJA) Propietario: Rango: Nombre_Persona Si_añadido: (VERIFICAR_PAGO y MATRICULAR) 129
130 Marcos y Objetos (Frames)Marvin Minsky (1975) IDEA: “El mundo es regular”. Numerosas situaciones se pueden tratar en base a tres ideas sencillas: 1. En el “mundo” el conocimiento puede estructurarse con frecuencia asignando valores a los atributos declarados en un estereotipo o plantilla. 2. Los objetos y situaciones del mundo pueden definir jerarquías. Por tanto la especialización (generalización) de esterotipos así como la herencia de propiedades son dos ideas a considerar. 3. Suele ser posible definir procedimientos de manipulación del conocimiento como métodos asociados con un cierto estereotipo u objeto. 130
131 Ejemplo: [Frame BMW Especialización_de: AUTOMÓVILPaís_de_fabricación: Alemania Fiabilidad: Alta ] [Frame BMW320 Especialización_de: BMW Consumo: 12 ] [Frame GC1234A Especialización_de: BMW320 Fiabilidad: Media Consumo: 15 Color: Rojo ] [Frame AUTOMÓVIL Especialización_de: VEHÍCULO Generalización_de: (BERLINA RANCHERA MONOVOLUMEN) Fabricante: Rango: (FORD MAZDA BMW SAAB) Defecto: MAZDA País_de_fabricación: Rango: (USA JAPÓN ALEMANIA SUECIA) Defecto: JAPÓN Modelo: Rango: () Color: Rango: (NEGRO BLANCO BEIGE ROJO) Si_necesario: (PREGUNTAR_VENDEDOR MIRAR_COCHE) Consumo: Rango: (0-200) Fiabilidad: Rango: (ALTA MEDIA BAJA) Propietario: Rango: Nombre_Persona Si_añadido: (VERIFICAR_PAGO y MATRICULAR) ] 131
132 Marcos y Objetos (Frames)FRAME: Una estructura de datos que representa una situación o fragmento de conocimiento Contiene: A. Toda la información relacionada con la situación, evento o entidad. B. La información necesaria para manipular el propio objeto. nombre del objeto slot1 slot2 ... slotn Slots: Cada Slot contiene información referente a un determinado “aspecto” del objeto y refleja el conocimiento disponible acerca de su estructura: sus relaciones con otros objetos, el modo de manipulación del mismo y los procesos asociados 132
133 Proporcionar valores: valor, defecto, procedimientos, reglas Facetas: Recogen una característica particular de la definición del Slot. Son facetas usuales: Proporcionar valores: valor, defecto, procedimientos, reglas Caracterización de la información asociada: dominio, rango, cardinalidad ... nombre del objeto slot1 faceta1: valor faceta2: valor slot2 ... slotn facetan: valor 133
134 Ejemplo de frame con slots y facetas:[Frame COMPUTADOR_PC Especialización_de: COMPUTADOR Cpu: Dominio: uno de (i386, i486, ipentium, ipentiumII) Defecto: ipentium Memoria: Dominio: entero Rango: (1-1024) Defecto: 32 Monitor: Dominio: alguno de (monocromo, color_vga, color_svga) Cardinalidad: máximo 2 Defecto: color_vga Disco_duro: Modelo: alguno de [Seagate, Quantum, IBM ] Defecto: Quantum ] 134
135 Procedimientos y MétodosUna de las ventajas de la representación basada en frames (objetos) sobre otras representaciones del conocimiento es que pueden especificarse qué procedimientos deben ejecutarse en diversas circunstancias Dos tipos: Procedimientos para manipular objetos externos y/o obtener valores Procedimientos para manipular los objetos mismos 135
136 escribe_slot: put_slot() ] mensaje(barco, caso, titanic) [Frame BARCO matrícula: ... tonelaje: ... ruta: ... métodos: caso: crea_caso() lee_slot: get_slot() escribe_slot: put_slot() ] mensaje(barco, caso, titanic) mensaje(titanic, lee_slot, ruta, Londres, NY) mensaje(titanic, escribe_slot, tonelaje, 90000) La clase de objeto “barco” contiene un conjunto de métodos (procedimientos) para crear casos particulares del mismo, así como para definir y obtener valores. La ejecución de los procedimientos asociados suele resolverse definiendo mensajes. Un mensaje es una señal transmitida a un objeto y cuya finalidad es desencadenar un método o demonio asociado al mismo. 136
137 Ventajas de los sistemas de frames o marcos Alta estructuración del conocimiento Control preciso del procesamiento: procedimientos asociados Una representación que puede acomodar la evolución del entorno Consistencia Desventajas de los sistemas de frames o marcos No es fácil tratar problemas donde las entidades puedan diferir de manera importante de los prototipos Acomodación de nuevas situaciones para las que no existen prototipos Es difícil depositar conocimiento heurístico: más fácil con reglas. 137
138 Sistemas Blackboard Oportunismo Especialista 1 Asincronismo actuadoresEncapsulamiento Reactividad (?) Especialista 1 actuadores PIZARRA Demonio A Especialista 2 Demonio B sensores Especialista 2 138
139 Sumario. La lógica de predicados, los sistemas basados en reglas (SBRs), las redes semánticas y los sistemas de marcos son alternativas para la representación del conocimiento. En la lógica de predicados y los SBRs no es posible estructurar el conocimiento. Sin embargo, definen “per se” mecanismos de control e inferencia. Los SBRs pueden razonar “hacia-adelante” o “hacia-atrás”. La idoneidad de estos mecanismos dependerá del contexto de aplicación. Los mecanismos de herencia presentes en redes semánticas y marcos pueden conferir una gran potencia a la representación. Los sistemas de marcos permiten una alta estructuración del conocimiento y control procedimental. 139
140 Bibliografía. [Mend-92] J. Méndez Apuntes del Curso de I.A. U.L.P.G.C.[Rich-91] E. Rich, K. Knight Artificial Intelligence McGraw-Hill, 1991. [Gonz-93] A. J. Gonzalez, D.D. Dankel The Engineering of Knowledge-Based Systems Prentice-Hall, 1993. 140