2 - Representacion Proposicional y Razonamiento PDF

Preview

Summary

Tema 2...

Description

Representación del Conocimiento y Razonamiento Automático

Representación Proposicional y Razonamiento

Contenidos:

Lógica Proposicional Sintaxis La sintaxis de lógica preposicional se define comenzando con un conjunto que vamos a llamar la signatura o signatura proposicional Ʃ, esta contiene todas las proposiciones o átomos que son símbolos que pueden ser cierto o falso, por ejemplo: Ʃ = {happy, rain, weekend}. Una vez teniendo esta signatura de partida podemos definir las fórmulas bien formadas, que son todas las expresiones de nuestro lenguaje proposicional LƩ. Fórmulas bien formadas pueden ser: • • • • • •

Cualquier átomo p ∈ Ʃ. La Tautología Τ. La Contradicción ⊥. La negación de cualquier fórmula bien formada (¬α). La disyunción (α ∨ β), conjunción (α ∧ β), implicación (α → β) y doble implicación (α ↔ β). Y una fórmula entre paréntesis (α).

En donde α, β ∈ LƩ. Además podemos ver notaciones ambiguas como: • •

Implicación: →, ⊃, ⇒. Equivalencia ≡, =, ↔, ⇔:

La precedencia de operadores sigue el siguiente orden: ≡, →, ∨, ∧, ¬. Todos los operadores binarios encadenados supondremos que son asociativos por la izquierda. Definiremos un literal, como cualquier átomo p o su negación ¬p y una teoría como un conjunto de fórmulas que forman un subconjunto de un lenguaje Γ ⊆ LΣ.

Semántica Definiremos la semántica como una función que nos hace corresponder expresiones sintácticas a otros objetos matemáticos como valores de certeza o conjuntos. Sería lo que llamamos una interpretación, que es una correspondencia entre átomos del lenguaje y valores de certeza cierto o falso I : Σ → {1, 0}. Por ejemplo, podríamos aplicar los siguientes valores de certeza al ejemplo anterior: I (happy) = 1, I (rain) = 0, I (weekend) = 1, que significa que estoy feliz, no está lloviendo y es fin de semana. Una forma alternativa de representar la interpretación es en vez de para cada átomo decir su valor de certeza, utilizar un conjunto donde solo reflejamos los átomos que son ciertos I ⊆ Σ. Esta será la forma más común de representación, en el ejemplo anterior sería I = {happy, weekend}.

La interpretación la podemos ampliar a cualquier fórmula I : LΣ → {0, 1}, podemos decir cuando una fórmula es cierta o falsa si sabemos su interpretación para cada átomo. Lo que hacemos es coger la fórmula que nos den I (α) y reemplazar cada átomo p ∈ Ʃ por su valor de certeza I (p) y aplicar las tablas de los operadores booleanos:

Por ejemplo, nos dan I = {happy, weekend} y queremos evaluar la fórmula I (¬rain → ¬weekend), reemplazamos por sus valores de certeza y aplicamos las tablas: I (1 → 0) → 0.

Podemos definir la relación de satisfacción del siguiente modo, decimos que una interpretación I satisface una fórmula α, cuando al evaluar α devuelve 1, I |= α, I (α) = 1. Pero también es muy normal definirla de forma independiente o inductiva de esta manera:

Decimos que la interpretación I es modelo de un conjunto de fórmulas de una teoría Γ, si satisfice todas y cada una de las formulas de Γ. Es decir, podemos definir el conjunto de modelos M(Γ) de la teoría Γ, es decir, todo el conjunto de interpretaciones que hacen cierta la teoría Γ. Por ejemplo: M(a ∨ b) = {{a, b}, {a}, {b}}. Podemos definir los modelos de una fórmula en función de los modelos de sus subfórmulas (inducción estructural). Los modelos de una disyunción son la unión de todos los modelos de sus subfórmulas M(α ∨ β) = M(α) ∪ M(β).

Dos fórmulas α, β son equivalentes si tienen los mismos modelos M(α) = M(β).

Dado un conjunto de interpretaciones S, ¿se podría sacar una fórmula α tal que M(α) = S? Por ejemplo, si tenemos estos tres modelos {{a,b},{b,c},{a,b,c}}, ¿hay una fórmula α que cubra esos modelos? Podríamos sacar la fórmula (a v b) ˄ c a ojo, ¿pero sabemos que esa fórmula siempre existe? Sí, y siempre está garantizado, podemos usar los mapas de Karnaugh, o mínterms, para sacar estas fórmulas. Para encontrar una fórmula siempre podemos coger los términos y hacer la disyunción de estos, no tendríamos por qué usar Karnaugh o minterms. Por ejemplo: (a ˄ ¬ b ˄ c) v (¬ a ˄ b ˄ c) v (a ˄ b ˄ c) ≡ (a v b) ˄ c

Decimos que α es una consecuencia lógica, o se concluye de la teoría Γ (Γ |= α) cuando los modelos de Γ están incluidos en los modelos de α (M(Γ) ⊆ M(α)). Por ejemplo {happy, (rain → ¬happy)} |= ¬rain. ¿Qué ocurre cuando la fórmula no tiene modelos (M(α) = ∅)? Diremos que la fórmula α es insatisfactible o inconsistente, por ejemplo, no podemos decir rain ˄ ¬rain. Por el contrario, si cualquier interpretación es modelo de α (M(α) = 2Σ), esa fórmula no dice ninguna información por lo tanto se puede suponer cualquier interpretación. Esta fórmula diremos que es válida o una tautología, por ejemplo, rain v ¬rain. Para escribir una tautología la escribimos como |= α, que quiere decir que α se sigue de nada, es decir que α se sigue siempre. Decir que de α se sigue β, α |= β, es lo mismo que decir que |= α → β es siempre cierto. Cuando esto ocurre, también podemos decir que M(α) ⊆ M(β), por lo que decimos que α es más fuerte que β, o que β es más débil que α. La fórmula más fuerte posible, sería aquella que contuviese los modelos que estuviesen incluidos en cualquier conjunto de modelo, es decir, que siempre cumpla M(α) ⊆ M(β). La fórmula que más información contiene, o que más fuerte es, es la inconsistencia M(α) = ∅ , dado que de una inconsistencia se puede derivar cualquier cosa. La fórmula más débil posible, tiene que ser superconjunto de cualquier conjunto de modelos, es decir, el conjunto de interpretaciones M(α) = 2Σ, en este caso sería añadir una tautología.

Ejemplos: ¿Qué fórmula es más fuerte?

En el último par de fórmulas ninguna es más fuerte que otra.

Razonamiento Proposicional El razonamiento proposicional consiste en saber si dada una conclusión y una base de conocimiento, podemos concluir C de ese conjunto de premisas. ¿Sigue la conclusión C las premisas en la base del conocimiento {P1, P2, ..., PN} = KB? {P1, P2, ..., PN} |= C Por ejemplo, dado un KB: • • •

P1: los fines de semana no veo la tele. P2: Estoy contento cuando llueve, menos el fin de semana. P3: Estoy viendo la tele, pero no estoy feliz.

¿Podemos concluir C: “no está lloviendo”? Tendremos que pasar el lenguaje humano a lógica formal para saberlo:

Por lo tanto tendremos algo así: • • • •

P1: w → ¬tv P2: r ˄ ¬w → h P3: tv ˄ ¬h C: ¬r

Comprobar {P1, P2, ..., PN} |= C, es lo mismo que comprobar P1 ˄ P2 ˄ ... ˄ PN ˄ ¬C es una inconsistencia. Esto se puede resolver usando un problema de decisión que es el problema de decisión SAT, a este solver se le da una fórmula SAT(α) ϵ {yes, no} y contesta sí o no dependiendo de si tiene o no algún modelo. La complejidad de este problema de decisión es NP-completo. Cuando queramos mirar si {P1, P2, ..., PN} |= C, sería lo mismo que mirar que SAT (P1 ˄ P2 ˄ ... ˄ PN ˄ ¬C) = no, ya podemos asegurar que la conclusión se sigue de las premisas. Otra manera de comprobar esto sería hacer la tabla de verdad.

El coste computacional de hacer la tabla de verdad es exponencial es decir 2n con n = | Σ |, tampoco podemos hacerlo mejor puesto que es un problema NP-completo, con lo cual en el peor de los casos será NP-completo. El problema de hacer la tabla de verdad es que siempre forzamos el peor caso puesto que para desarrollar la tabla de verdad tenemos que desarrollar las 2n interpretaciones. En casos particulares lo podríamos hacer mejor. En nuestro ejemplo tv ˄ ¬h y r fija el valor de verdad de esos 3 átomos: I(h) = 0, I(tv) = 1 y I(r) = 1. Por lo tanto, solo tenemos que comprobar w.

Tan sólo con esos tres valores de certeza, ya llegamos a que la teoría era inconsistente sin tener que saber el valor de w.

El punto clave de SAT es que en vez de usar un algoritmo ad hoc de búsqueda, busca una manera de traducir un problema a lógica proposicional, es decir usar un SAT como backend. Los SAT solvers representan la entrada como una conjunción de cláusulas, donde una cláusula es una disyunción de literales. A esto le llamamos Forma Normal Conjuntiva (FNC). Para pasar a FNC tenemos que seguir la siguiente jerarquía:

Cuando una base de conocimiento ya es un conjunto de hechos e implicaciones con literales está casi en Forma Normal Conjuntiva. Por ejemplo:

Una restricción es una negación de una cláusula de la FNC, por ejemplo:

Razonamiento basado en reglas Las reglas son una parte sustancial del razonamiento del sentido común. El modo de funcionar cuando utilizamos reglas no siempre es el mismo que tenemos si usamos lógica clásica. Por ejemplo, una regla podría ser decir que el fuego causa humo, o humo si fuego, o humo :- fire en notación lógica.

Podemos tener dos posibles lecturas de una regla: •

Lectura hacia arriba o disparado de regla: “Cuando enciendo un fuego, ese fuego va a producir humo”, una forma de verlo es pensar en una regla de inferencia Modus Ponens:

Esta forma se usa en Answer Set Programming, que es un método que tiene más conexión con la inferencia causal. •

De arriba hacia abajo o goal achievement: “¿Cómo puedo conseguir humo? La única manera es hacer fuego”, entonces tenemos que si queremos conseguir humo, tenemos que hacer fuego. Esta segunda forma de ver las reglas como una forma de satisfacer objetivos, mediante backtracking, es el que usa el lenguaje Prolog.

Reglas como Fórmulas lógicas Una primera observación es que una regla se parece mucho a una implicación lógica, la primera opción podría ser traducir la regla como una implicación material en lógica clásica.

Esto tiene una ventaja y es que en lógica clásica tenemos el Modus Ponens, que es la forma de aplicar la regla que dijimos antes. Pero tiene una desventaja, y es desde el punto de vista de la semántica, los modelos de esa expresión no están alineados con la forma de comportarse cuando hacemos razonamiento basado en reglas. Si solamente sabemos que KB = {smoke ← fire}, si no tenemos más información en principio suponemos que fire es falso porque no tenemos ninguna regla para derivar fuego y como sólo tenemos que smoke solo es derivable con fuego, pues también es falso. Por lo tanto, con razonamiento basado en reglas no obtenemos nada de la formula anterior. Sin embargo, con lógica clásica tenemos tres modelos, {smoke, fire}, {smoke}, ∅. No obtener ningún modelo, otro en el que smoke es cierto y otro en el que los dos son ciertos. ¿De dónde hemos sacado esos hechos?

Es interesante observar que el más pequeño, el que menos átomos ciertos hace es el que nos interesaba desde el punto de vista de razonamiento basado en reglas. Tanto que podríamos plantearnos coger siempre de los modelos clásicos aquellos que tienen un conjunto de átomos más pequeño, que es lo que llamamos modelos minimales y cubren muy bien recursividad positiva en las reglas. Otro ejemplo:

Programación Lógica Positiva Un programa lógico positivo es un conjunto de reglas en donde cada una tiene una cabeza y un cuerpo, formado por una secuencia de átomos:

El orden entre las reglas es irrelevante, podemos cambiarlas de orden en el momento que queramos, así como los átomos del cuerpo. Cuando no tenemos cuerpo, llamaremos a esa regla hecho. Estas reglas escritas en formato de texto (para clingo) se escribirían así: p :- q1, …, qn. En donde n es mayor o igual a 0 y p, q1, …, qn, son átomos. Las comas en el cuerpo representan conjunciones. En cualquier momento nos puede interesar leer la regla desde el punto de vista de lógica clásica: (p ← q1, . . . , qn) → (q1 ∧ · · · ∧ qn → p). Para la semántica nos podría interesar coger siempre los modelos más pequeños posibles, esta hipótesis es lo que se llama Hipótesis de Mundo Cerrado (CWA) que es minimizar la certeza, y dice “de todos los modelos coge aquellos que tengan el subconjunto más pequeño de átomos”. En general podemos tener varios modelos minimales, por ejemplo M(p ∨ q) = {{p}, {q}, {p, q}}, tiene dos modelos mínimos {p}, {q}. Los programas positivos cumplen una propiedad muy interesante, un programa positivo (un conjunto de implicaciones) tiene siempre un único modelo minimal y es lo que llamaríamos el modelo mínimo.

Para calcular el least model o modelo mínimo, podemos utilizar la aplicación de reglas o cierre deductivo. Para esto podemos utilizar el operador de consecuencias directas, que dado un programa P y una interpretación (conjunto de átomos) I, devuelve un nuevo conjunto de átomos que son todas las cabezas, cuando la regla de esa cabeza es satisfecha por la interpretación.

Una vez tenemos ese operador podemos ir calculando una secuencia de interpretaciones I0, I1, I2, … Empezaríamos con I0 = ∅ (todos los átomos son falsos). Y repetiríamos Ik+1 = TP(Ik) hasta que lleguemos a un punto en el que Ik+1 = Ik. Un ejemplo:

Negación Por Defecto Nuestro objetivo original era permitir razonamiento por defecto, en cierta manera ya tenemos algo de razonamiento por defecto porque la hipótesis del mundo cerrado nos permite concluir que cualquier átomo es falso si no tenemos una forma de derivarlo. Sin embargo, cuando un átomo es falso no podemos comprobarlo en las condiciones de las reglas. La idea es introducir los literales negativos en los cuerpos de las reglas, escribiremos “not p” para indicar que no hay evidencia para el átomo p. También podemos verlo como que la fórmula “¬p” es una hipótesis posible. Un programa lógico normal es aquel en el cual hemos añadido en el cuerpo de las reglas literales negativos, pero seguimos manteniendo la posibilidad de que no haya ningún literal negativo y en ese caso tendríamos la situación anterior (regla positiva).

Un ejemplo, supongamos que nos dicen que podemos rellenar el depósito si está vacío y no hay evidencia de que hay fuego. Además, nos dan el hecho de que el depósito está vacío.

Si seguimos usando la semántica que teníamos hasta ahora, quedarnos con los modelos más pequeños de las interpretaciones de las reglas del programa lógico. Pero esto no es suficiente, los modelos mínimos de la fórmula (empty ∧ (fill ∨ fire)) serían {empty, fill} y {empty, fire}. Nosotros esperábamos obtener tan solo {empty, fill}. Esto no es que esté mal, hacer la hipótesis de que puede haber un fuego está bien siempre y cuando después esta hipótesis se vea referendada por las reglas. El problema es que no hemos proporcionado ninguna regla para que el átomo fire sea cierto. Además, siempre queremos mantener la propiedad de que todo átomo que se vuelva cierto esté justificado. Esperamos además que el comportamiento sea no monótono, es decir, si en cualquier momento añadimos el hecho fire, tenemos una regla que permita derivar la fire y {empty, fill} ya no debería de ser válido y {empty, fire} pasaría a ser el correcto, es decir, puedo retractarme de una conclusion anterior.

Todos estos problemas surgen del hecho de que la implicación material, la implicación clásica no es direccional, no tiene una dirección de antecedente a consecuente si no que es un tipo de disyunción. Por ejemplo, tenemos que las siguientes fórmulas son equivalentes:

Y de la que podemos derivar que si el tanque está vacío y hay evidencia de que rellene, encendemos un fuego:

A veces este tipo de reglas por defecto pueden entrar en conflicto, un ejemplo clásico es lo que se conoce como el diamante de Nixon. Este problema tiene las siguientes premisas: • • •

“quakers are normally pacifist” (unless bellicose) “republicans are normally bellicose” (unless pacifist) “Richard Nixon is a both a Quaker and a Republican”

Fijándonos en el conjunto de reglas, no tenemos forma constructiva de aplicar las reglas.

¿Cómo podemos dar semántica a este nuevo literal? La idea clave se recoge en “the stable model semantics for logic programming.” que vamos a definir informalmente usando tres pasos. 1. Hacer una hipótesis, supondremos que nuestras hipótesis son p, q y r y tenemos que not b es cierto. 2. Reducir el programa de acuerdo a las hipótesis que tenemos. Tenemos que p ← q, not b (not b es cierto) y que b ← r, not p (not p es falso), por lo tanto, podríamos quitar not b de la primera regla y eliminar la segunda regla. Nos queda un programa positivo. 3. Y ahora comprobamos los modelos mínimos, que en este caso es nuestra hipótesis inicial {p, q, r}, por lo tanto, es un modelo estable.

Aunque también tenemos que {b, q, r} también es estable con otra hipótesis.

La definición de reducto sería, de todas las reglas del programa, nos quedamos con la parte positiva de aquellas reglas que cumplen todos sus not. Formalmente, un el reducto de un programa P con respecto a una interpretación I es:

El reducto es un programa positivo por lo tanto siempre tiene un least model. I es un modelo estable de un programa P si es el modelo mínimo del reducto de P sobre I, LM(PI) = I. Recordamos que M(P) son los modelos clásicos de una fórmula (siendo P los modelos clásicos del programa P interpretados como fórmulas de lógica clásica) y SM(P) como los modelos estables del programa P. Una propiedad muy importante es que todo modelo estable es un modelo clásico del programa P, pero no al revés, SM(P) ⊆ M(P). Cuando tenemos un programa normal (podemos usar después en la cabeza), tenemos que los modelos estables son minimales, si I es un modelo estable, no hay ningún otro modelo clásico más pequeño que otro, tampoco tendremos que un modelo estable está incluido en otro. Formalmente tenemos que si I ∈ SM(P) entonces no hay ningún J ∈ M(P) tal que J ⊂ I. En un programa normal, decidir si un programa tiene o no un modelo estable (SM(P) = ∅ ?) es un problema NP-completo, la misma complejidad que teníamos en SAT.

Modelos estables

Volviendo al ejemplo, tenemos que P tiene dos reglas: En principio tendríamos que hacer 23 supuestos ya que tenemos tres átomos {fill, empty, fire}.

Sin embargo, hay una propiedad clave que acabamos de ver y es que todo modelo estable tiene que ser también un modelo clásico de esta teoría SM(P) ⊆ M(P). Entonces ya no tiene sentido que empecemos planteando hipótesis que no son modelos clásicos porque tampoco serán modelos estables. Para la teoría anterior teníamos estos tres modelos clásicos, y calculamos el reducto para cada uno de ellos y vemos si es o no estable.

Supongamos ahora que varían el escenario y que una chispa enciende el fuego, entonces ahora P tiene 4 reglas:

Y, ¿cuántos modelos hay ahora? Aunque hay más átomos, realmente hay menos modelos clásicos, puesto que, si spark es cierto y este implica fire, el único átomo que queda sin decidir es fill. Nos quedan las siguientes dos combinaciones:

En el primer caso el modelo mínimo coincide con la suposición inicial, pero en el segundo no puesto no hay ninguna evidencia de que fill sea cierto.

Decimos que un programa normal es estratificado si no aparecen ciclos a través de negación. Si nunca se produce un ciclo a través de negación podríamos organizar el programa en capas o stratos de tal manera que cada vez que aparece una negación tenemos un salto de capa. Podemos ver que las reglas para a y b están en un nivel y luego c depende de a y d depende de c, estamos mirando las dependencias a través de la negación. Este programa se puede organizar en tres capas, y se puede proceder por capas, como vemos cada capa dispara su propia regla. La capa uno dispara la regla a → b, y con esto obtenemos el modelo {a, b}, una vez sabemos que a es cierto, podemos proceder a la segunda capa en donde vemos que not a es falso y por lo tanto la regla no se dispara. Como no hemos deducido la regla c, le damos un valor falso por lo que la regla de la capa tres se dispara y nos queda el modelo {a, b, d}. Cuando no hay ciclos a través de negación se puede proceder por capas y este razonamiento es correcto respecto a los modelos estables. Un programa estratificado tiene un único modelo estable |SM(P)| = 1.

Si P no es estr...