Describa las características de un agente lógico y basado en conocimiento

El agente lógico es un tipo de agente que tiene como propiedades adicionales:

• estar basado en un base de conocimiento, que es un conjunto de sentencias o términos formales que dan aserciones sobre un dominio.

• actúa según sus consultas a esa base de conocimiento a tráves de un motor de inferencia.

Describa con sus propias palabras la Base de conocimientos (Knowledge base) y la Máquina de inferencias (Inference engine)

La base de conocimiento es un conjunto de conjunto de sentencias formales y declarativas sobre un dominio específico. Dichas sentencias suelen ser derivadas de la grámatica de la lógica de primer orden o de orden zero.

Mientras que la máquina de inferencias es un conjunto de algoritmos y estructuras de datos independientes del dominio que infiere nuevas sentencias formales desde dicha base de conocimiento. Esto habilita que las sentencias sean declarativas.

Considere un modelo de lógica proposicional con cuatro símbolos: A, B, C y D

Para cada una de las siguientes opciones indiqué cuántos mundos posibles (combinaciones de valores de entrada) las vuelven verdaderas.

• (A ∨ B) ∨ (C ∧ D)

$(A \lor B)$ es 1 en tres situaciones por lo que la expresión es 1 sin importar el valor proposicional de $(C\land D)$. Para esta última, existen 4 combinaciones. Aplicamos la regla del producto y obtenemos $12$ casos que satisfacen la fórmula.

La conjunción es $1$ cuando los símbolos son 1. Por lo tanto, $C\land D$ es 1 solo una vez.

En total, existen $12+1=13$ modelos satisfactibles.

• ¬(A ∨ B ∨ C ∨ D)

Un solo un modelo satisfactible porque $A \lor B \lor C \lor D$ es 1 cuando por lo menos un símbolo es 1, de los $2^4=16$ mundos, eso ocurre 15 veces y el caso donde todos son 0 ocurre 1 vez. Invertimos (aplicamos la negación) y obtenemos el resultado.

• A ⇒ (B ∧ C)

Aunque la fórmula no se encuentra $D$, el total de mundos posibles sigue siendo $2^4=16$. Con esto presente, buscamos los modelos satisfactibles.

La expresión es falsa cuando es $A$ es verdadera que ocurre lo cual ocurre 8 veces y $(B\land C)$ falsa lo cual ocurre 3 veces. Por lo tanto, la expresión completa es falsa 6 veces (2 veces por $D$ combinaciones) y es verdadera las $10$ restantes.

Suponga que está diseñando un procedimiento para convertir una fórmula booleana a formato CNF a través pasos que se basan en equivalencias lógicas.

Para cada paso que se indica a continuación, seleccionar el ejemplo válido en equivalencia lógica.

• Paso 1. Sustituir las doble implicaciones (⇔).
  • (𝛂 ⇔ 𝛃) ≡ ((𝛂 ⇒ 𝛃) ∧ (𝛃 ⇒ 𝛂))
  • (𝛂 ⇔ 𝛃) ≡ ((𝛂 ⇒ 𝛃) ∨ (𝛃 ⇒ 𝛂))
  • (𝛂 ⇔ 𝛃) ≡ (𝛂 ∧ 𝛃)

• Paso 2. Sustituir las implicaciones (⇒).
  • (𝛂 ⇒ 𝛃) ≡ (𝛂 ∨ ¬𝛃)
  • (𝛂 ⇒ 𝛃) ≡ (¬𝛂 ∨ 𝛃)
  • (𝛂 ⇒ 𝛃) ≡ (¬𝛂 ∧ 𝛃)

• Paso 3. Integrar las negaciones (¬) al interior de las cláusulas.
  • ¬(𝛂 ∨ 𝛃) ≡ (¬𝛂 ∧ ¬𝛃)
  • ¬(𝛂 ∨ 𝛃) ≡ (¬𝛂 ∨ ¬𝛃)
  • ¬(𝛂 ∧ 𝛃) ≡ (¬𝛂 ∨ ¬𝛃)

• Paso 4. Integrar las disyunciones (∨) al interior de las cláusulas y las conjunciones (∧) al exterior.
  • (𝛂 ∨ (𝛃 ∧ 𝛄)) ≡ (𝛂 ∨ 𝛃 ∨ 𝛄)
  • (𝛂 ∨ (𝛃 ∧ 𝛄)) ≡ ((𝛂 ∨ 𝛃) ∧ (𝛂 ∨ 𝛄)
  • (𝛂 ∨ (𝛃 ∧ 𝛄)) ≡ ((𝛂 ∧ 𝛃) ∨ (𝛂 ∧ 𝛄)

Considerando la fórmula booleana

[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party], responder los siguientes puntos:

1. Utilice la enumeración (fuerza bruta) para ilustrar si puede o no satisfacerse.

+--------+---------+----------+----------------------------------------------------------------------------------------------+
|  Food  |  Party  |  Drinks  |  ((Food implies Party) or (Drinks implies Party)) implies ((Food and Drinks) implies Party)  |
|--------+---------+----------+----------------------------------------------------------------------------------------------|
|   1    |    1    |    1     |                                              1                                               |
|   1    |    1    |    0     |                                              1                                               |
|   1    |    0    |    1     |                                              1                                               |
|   1    |    0    |    0     |                                              1                                               |
|   0    |    1    |    1     |                                              1                                               |
|   0    |    1    |    0     |                                              1                                               |
|   0    |    0    |    1     |                                              1                                               |
|   0    |    0    |    0     |                                              1                                               |
+--------+---------+----------+----------------------------------------------------------------------------------------------+

La fórmula es una tautología o válida por lo que si puede satisfacerse.

1. Utilice equivalencias lógicas para que la parte izquierda y la parte derecha de la fórmula lógica queden en formato CNF.

Usaremos una representación de árbol (AST).

Parte izquierda [(Food ⇒ Party) ∨ (Drinks ⇒ Party)].

Or
├── Implies
│   ├── BooleanSymbol
│   │   └── Food
│   └── BooleanSymbol
│       └── Party
└── Implies
    ├── BooleanSymbol
    │   └── Drinks
    └── BooleanSymbol
        └── Party

Aplicamos los pasos sobre este AST.

1. (𝛂 ⇒ 𝛃) ≡ (¬𝛂 ∨ 𝛃)

Or
├── Or
│   ├── BooleanSymbol
│   │   └── Party
│   └── Not
│       └── BooleanSymbol
│           └── Food
└── Or
    ├── BooleanSymbol
    │   └── Party
    └── Not
        └── BooleanSymbol
            └── Drinks

2. Paso 1, 2 y 3 no modifican la expresión por lo que hemos terminado.

En la forma de la notación inicial:

$Party \lor \lnot Food \lor Party \lor \lnot Drinks$

Parte derecha [(Food ∧ Drinks) ⇒ Party].

Implies
├── And
│   ├── BooleanSymbol
│   │   └── Food
│   └── BooleanSymbol
│       └── Drinks
└── BooleanSymbol
    └── Party

1. Aplicamos el Paso 2 (equivalencia de la implicación material).

Or
├── BooleanSymbol
│   └── Party
└── Not
    └── And
        ├── BooleanSymbol
        │   └── Food
        └── BooleanSymbol
            └── Drinks

2. Aplicamos la regla 3.

Or
├── BooleanSymbol
│   └── Party
└── Or
    ├── Not
    │   └── BooleanSymbol
    │       └── Food
    └── Not
        └── BooleanSymbol
            └── Drinks

3. La regla 1 y 4 no modifican la expresión por lo que hemos terminado.

En la forma de la notación inicial:

$Party \lor \lnot Food \lor \lnot Drinks$

Hemos terminado.

Investigue y describa al menos una aplicación práctica que tendría un método/algoritmo resolvedor del problema SAT

Primero, recordemos cuál es el problema SAT (problema de satisfacibilidad booleana): dado una fórmula booleana -normalmente expresada en su forma normal conjuntiva- $F(x_1,x_2,...,x_n)$, determine si satisfactible o no. Satisfactible significa que existe al menos un modelo, un mundo, o combinación o valores de entrada tal que $F$ sea verdadero. Insatisfactible signfica que no existe ningún modelo donde eso pase. En general, para $n$ símbolos, hay $2^N$ mundos posibles. Un algoritmo que resuelve bien en la práctica el problema es el algoritmo DPLL.

Ahora una aplicación donde aparece el problema SAT y por tanto, donde necesitamos su resolvedor. Generalmente, si podemos convertir un problema a un conjunto de proposiciones, entonces podemos usar un resolvedor de SAT. Dichos problemas suelen ser de combinatoria: 8 reinas, Hanoi, Soduku, horarios, encontrar si $p$ sigue de $q$ en una base de conocimiento, …

TODO: https://www.youtube.com/watch?v=cI5lkif-V1c&ab_channel=ALEXonScience

En otras palabras, los pasos que nos conciernen es cambiar de representación -a esto, suele ser llamar codificación-: una codificación que sea aceptada por los resolvedores y la codificación del problema original.

Así, la representación estandár de los resolvedores de SAT es CNF (para ser más exactos CNF en formato DIMACS) y la representación de la instancia de solución que cumple las condiciones pedidas.

Como un algoritmo:

resolver(instancia_de_problema)
   cnf_en_formato_dimacs = codificar_a_cnf_en_formato_dimacs(instancia_de_problema)
   modelos = resolver_sat(cnf_en_formato_dimacs)
   return codificar_a_instancia_de_soluciones(modelos)

Nuestros problemas se reducen a encontrar codificar_a_cnf_en_formato_dimacs y codificar_a_instancia_de_soluciones.

Supongamos que la CNF es de la forma $(\lnot x_1 \lor x2) \land (\lnot x2 \lor x3)$, los mundos posibles son:

+------+------+------+-------------------------------------+
|  x1  |  x2  |  x3  |  (not x1 or x2) and (not x2 or x3)  |
|------+------+------+-------------------------------------|
|  1   |  1   |  1   |                  1                  |
|  1   |  1   |  0   |                  0                  |
|  1   |  0   |  1   |                  0                  |
|  1   |  0   |  0   |                  0                  |
|  0   |  1   |  1   |                  1                  |
|  0   |  1   |  0   |                  0                  |
|  0   |  0   |  1   |                  1                  |
|  0   |  0   |  0   |                  1                  |
+------+------+------+-------------------------------------+

Donde nosotros estamos interesados en los modelos satisfactibles (donde la CNF es 1). Por ejemplo, un modelo es $x_1=0,x_2=1,x_3=1$ porque es 1 su CNF. Como $x_1$ es 0, es ignorada a la hora de codificar a instancia de soluciones y las combinaciones útiles son aquellos donde los símbolos son iguales a 1 -$x_2,x_3$-.

En los problemas de combinaciones, tenemos un predicado que dado una instancia de un problema, se convierte a preposición, de ahí obtenemos nuestra CNF.

Minisudoku

Dado una secuencia de tamaño 4, encuentre las secuencias de números enteros entre 1 y 4 tal que cada número aparezca una sola vez. Donde $?$ significa valores a rellenar.

Ejemplo.

Entrada: $[?,1,?,4]$

Salida: $[2,1,3,4]$, $[3,1,2,4]$

Resolución

Un primera representación bastante informal es:

$\text{ya esta en la lista}(X)\land\text{esta en alguna lista}(X) \land \text{solo aparece exactamente una vez}(X).$

donde $X$ son los valores permitidos.

Las proposiciones las nombraremos como $x_{ij}$ donde $i$ es la celda y $j$ como el valor, solo será verdadera cuando cuando exista un valor en dicha celda. Esto significa que dado un arreglo $[1,?]$ es $x_{11}$ verdadero, mientras $x_{2?}$ es falsa.

$\text{ya esta en la lista}(X)$ es un predicado sobre si $X$ es número o es distinto de $?$ y que se encuentra en la lista. Por tanto, es la conjunción de todas los valores $x_{ij}$.

Ejemplo: $[1,?,2]$

$\text{ya esta en la lista}(1)$ es verdadero.

$\text{ya esta en la lista}(2)$ es verdadero.

Entonces, $\text{ya esta en la lista(X) }=x_{11}\land x_{32}$.

Quedando:

$x_{11} \land x_{32} \land\text{esta en alguna lista}(X) \land \text{solo aparece exactamente una vez}(X).$

$\text{esta en alguna lista}(X)$ es un predicado sobre si en alguna combinación (sin importar si cumple o no la restricción) de la lista, $X$ se encuentra. Ignoramos aquellos ya conocidos.

Supongamos la entrada de nuestro algoritmo es: $[1,?,2]$.

Las combinaciones son: $[1,1,2],[1,2,2],[1,3,2]$.

Las preposiciones son aquellas donde 1,2 y 3 aparecen en la lista $(x_{11} \lor x_{11} \lor x_{21} \lor x_{11})\land (x_{32} \lor x_{32} \lor x_{22} \lor x_{32}) \land x_{23}$.

Entonces, $\text{esta en alguna lista}(X)=(x_{11} \lor x_{11} \lor x_{21} \lor x_{11})\land (x_{32} \lor x_{32} \lor x_{22} \lor x_{32}) \land x_{23}$.

Obtenemos:

$(x_{11} \land x_{32}) \land ((x_{11} \lor x_{11} \lor x_{21} \lor x_{11})\land (x_{32} \lor x_{32} \lor x_{22} \lor x_{32}) \land (x_{23}) ) \land \text{solo aparece exactamente una vez}(X).$

$\text{solo aparece exactamente una vez}(X)$ es un predicado sobre si $X$ aparece exactamente una vez. Otra manera de verlo, es que no hay celda que contenga más de un número (xor).

$\lnot x_{ij} \lor \lnot x_{ij'}$ donde $j \neq j'$.

Usamos la entrada: $[1,?]$. Con todas las combinaciones listadas: $[1,1],[1,2],[2,1],[2,2]$. Cuya CNF y su tabla de verdad es

-------+-------+-------+-------+-------------------------------------------------+
|  x11  |  x21  |  x12  |  x22  |  (not x21 or not x11) and (not x12 or not x22)  |
|-------+-------+-------+-------+-------------------------------------------------|
|   1   |   1   |   1   |   1   |                        0                        |
|   1   |   1   |   1   |   0   |                        0                        |
|   1   |   1   |   0   |   1   |                        0                        |
|   1   |   1   |   0   |   0   |                        0                        |
|   1   |   0   |   1   |   1   |                        0                        |
|   1   |   0   |   1   |   0   |                        1                        |
|   1   |   0   |   0   |   1   |                        1                        |
|   1   |   0   |   0   |   0   |                        1                        |
|   0   |   1   |   1   |   1   |                        0                        |
|   0   |   1   |   1   |   0   |                        1                        |
|   0   |   1   |   0   |   1   |                        1                        |
|   0   |   1   |   0   |   0   |                        1                        |
|   0   |   0   |   1   |   1   |                        0                        |
|   0   |   0   |   1   |   0   |                        1                        |
|   0   |   0   |   0   |   1   |                        1                        |
|   0   |   0   |   0   |   0   |                        1                        |
+-------+-------+-------+-------+-------------------------------------------------+

Ahora seguimos el procedimiento, aplicamos algún resolvedor de SAT, y a los modelos le aplicamos una inversa.

Una versión completa en Python puede encontrarse en: https://gist.github.com/sanchezcarlosjr/ab024459b6b78ade77733115354f5e93

Suponga que tiene como base de conocimiento:

KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D), a partir de ella responda los siguientes puntos: (15 puntos)

1.Ilustre los pasos del algoritmo Forward Chaining para demostrar que a partir de la base de conocimientos (KB) se puede inferir D, es decir KB ⊨ D (KB entails D).

$A \implies True$ (cláusula 1, símbolos en la premisa $count[1]=1$)

$A\implies B$ (cláusula 2, símbolos en la premisa $count[2]=1$)

$A \implies C$ (cláusula 3, símbolos en la premisa $count[3]=1$)

$(B \land C) \implies D$ (cláusula 4, símbolos en la premisa $count[4]=2$)

Este algoritmo es parecido al BFS, excepto por la manera de evitar el bucle infinito -usando inferred- y otros detalles propios del dominio (contar el número de premisas necesarias que no hay sido demostradas con count), porque Forward Chaining es un algoritmo de búsqueda en un grafo cuyos nodos son los símbolos y las aristas la relación antecedente-consecuente de la implicación donde el objetivo es encontrar el símbolo $q$. Esto significa que para nuestro caso, nos detendremos cuando $q=D$.

El grafo inicial para nuestra base de conocimientos:

Al inicio del algoritmo $queue=\{A\}$, $inferred[s]=false$ donde $s\in \{A,B,C,D\}$.

Entonces, debemos explorar $A$ primero:

Las cláusulas que tienen como premisa $A$ son la 1, 2 y la 3. Decrementamos en uno el número de símbolos en cada cláusula. Esto es, ya no consideramos en el futuro el símbolo $A$.

Quedando como sigue:

$A \implies True$ (cláusula 1, símbolos en la premisa $count[1]=0$)

$A\implies B$ (cláusula 2, $count[2]=0$)

$A \implies C$ (cláusula 3, $count[3]=0$)

$(B \land C) \implies D$ (cláusula 4, $count[4]=2$)

Como comentamos, ignoraremos a la premisa 1 ya que es redudante en este punto. Agregamos a nuestra cola (alguna veces llamada agenda) las nuevas conclusiones por inferir:

Agregamos estas conclusiones porque ya satifacemos el antedecente (ya lo demostramos).

Ahora toca explorar el símbolo $B$:

Como podemos apreciar en el grafo, $B$ es inferido. $B$ es contenida en la cláusula 4, por lo que $count[4]=1$.

$(B \land C) \implies D$ (cláusula 4, $count[4]=1$).

Aquí no agregamos ninguna nueva conclusión porque la cláusula 4 (la única cláusula que contiene en las premisas al símbolo $B$) no es satisfecha.

Así continuamos con el símbolo en la agenda:

El grafo indica que $C$ es inferido. Ahora si satisfacemos a la cláusula 4, esto es reflejado en nuestra tabla: $count[4]=0$.

$(B \land C) \implies D$ (cláusula 4, $count[4]=0$).

Con seguridad agregamos el símbolo $D$ a la cola. Pero, un momento, ese es el símbolo que estabamos buscando.

Hemos terminado porque hemos demostrado que $KB \vDash D$.

2.Cómo utilizaría un resolvedor de SAT para demostrar que KB ⊨ D (Tip: La solución se puede plantear de forma simple en una línea).

KB ⊨ D si y solo si ($KB \land \lnot D$) es insatisfactible.

De lo que sigue:

Pero SAT solo acepta CNF, así el argumento de entrada para un resolvedor de SAT es

Describa con sus palabras el paradigma de programación lógica del lenguaje PROLOG y compárelo al menos con otro paradigma.

El paradigma lógico es un modelo de computación fundamentado en la unificación y predicados (functores y variables), esto es, un programa lógico se compone de una base de datos (hechos, átomos, variables y reglas), un mecanismo de inferencia (unificación, motor de inferencia, forward chaining, backward chaining) y una consulta a dicha base de datos.

Más precisamente, los programas lógicos son un conjunto de cláusulas de Horn, una restricción de las fórmulas de primer orden, agregando un mecanismo de deducción llamado resolución (en PROLOG, resolución SLD, que es en esencia backtracking buscando un objetivo) usando la regla de inferencia Modus ponens cuando se consulta la base de datos.

Las cláusulas de Horn son de la forma: $consecuente\text{ :- } antecedente$ donde el antecedente está en la forma conjuntiva. Note que si el cuerpo es siempre verdadero, solo escribimos el antecedente, lo cual es un axioma o hecho.

Al igual que el paradigma funcional, los paradigmas lógicos son declarativos, esto es, el programador escribe que es lo que necesita, a diferencia del paradigma imperativo, que escribe como computarlo. Que un lenguaje sea declarativo NO significa que no haya instrucciones imperativas por debajo (al final las máquinas de Von Neumann siguen paradigmas imperativos), sino que alguien ha agregado una capa extra de abstracción.

La principal diferencia entre un paradigma funcional y el lógico es el modelo computacional que siguen, el primero cálculo lambda, el segundo la unificación, la lógica de primer orden y toda la maquinaria vista anteriormente. Por supuesto, de esto se deriva la manera en el cómo se escriben los programas.

Describa con sus propias palabras a los Sistemas Expertos así como sus componentes

«Sistema experto» es un software caracterizado por usar una base de conocimientos expresada en reglas lógicas (hechos, heurísticas, predicados, reglas si-entonces) en un dominio específico y de ahí extraer respuestas o tomar decisiones.

La base de conocimientos es creada por un ingeniero del conocimiento que a su vez la obtene vía un experto en la materia, aunque en teoría, es posible otras fuentes. El sistema experto es explotado por las consultas de un usuario.

El sistema experto es compuesto de una máquina de inferencias, base de conocimientos y memoria de trabajo.

La máquina de inferencias -un sistema de razonamiento automático- son el conjunto de algoritmos independientes del dominio (forward chaining, backward chaining) que buscan en la base del conocimiento para conseguir el objetivo (la consulta del usuario), dar recomendaciones e implementar un plan al respecto.

La base de conocimientos es una base de hechos, heurísticas y predicados; más que un código procedural, solo son reglas si-entonces.

La memoria de trabajo es la estructura de datos que representa el estado actual del problema o consulta, lo cual es usada principalmente por la máquina de inferencias.

En general, un sistema experto puede tener más sentido que otros enfoques más modernos -machine learning- cuando existe un conocimiento bien establecido sobre el tema, pero no datos.