1 of 28

Inteligencia Artificial

Agentes Basados en el Conocimiento

Adaptado de: Martin Marchetta�martin.marchetta@ingenieria.uncuyo.edu.ar

Hernán Garrido�carloshernangarrido@gmail.com

2 of 28

Introducción

  • Los agentes pueden basarse en representaciones con distintos niveles de expresividad
    • Atómicas
    • Factorizadas
    • Estructuradas
  • Algoritmos de búsqueda se basan principalmente en representaciones atómicas
    • Poca flexibilidad (ej: cambiar comportamientos, objetivos, función de utilidad, etc.)
    • Poca potencialidad de reutilización → desarrollos son casi one-of-a-kind (ej: modelos de transición, heurísticas, etc)
    • Expresividad limitada → algunos problemas no pueden resolverse (ej: problemas en entornos parcialmente observables)
    • No se prestan para modelado de conocimiento de forma intuitivo y que permita explicaciones

2

3 of 28

Introducción

  • Satisfacción de restricciones / Algoritmos genéticos
    • Primera evolución → representaciones factorizadas�
    • Aportan más flexibilidad
      • Heurísticas más generales, independientes del dominio (más reutilizables)
      • Representaciones más generales, para distintos dominios (ej: restricciones)
      • Posibilidad de alterar comportamientos (ej: cambiando la función de fitness)�
    • Siguen teniendo problemas
      • Expresividad limitada para representar conocimiento general
      • Imposibilidad de razonar de formas no previstas
      • Dificultad o imposibilidad de alterar comportamientos dinámicamente

3

4 of 28

Introducción

  • Algunas propiedades deseables de un agente
    • Explotar conocimiento disponible
    • Combinar y recombinar conocimiento e información para múltiples usos
    • Aceptar nuevos objetivos, muchas veces no previstos, y satisfacerlos
    • Mejorar / Expandir su rendimiento a través de nuevo conocimiento recibido o aprendido de la experiencia, el entorno o la propia inferencia
    • Representación declarativa del dominio (vs. representación procedural de los algoritmos de búsqueda)�
  • “Los humanos parecen saber cosas, y lo que saben los ayuda a hacer cosas [...] no como reflejo puro, sino a través de procesos de razonamiento que operan en representaciones internas de conocimiento” (S. Russel y P.Norvig, Artificial Intelligence: a Modern Approach)� → Knowledge-based Agents�

4

5 of 28

Introducción

  • Ejemplo�Conocimiento de base:�...�Presion Tuberia A = Presion Tuberia B + 1/2 Presion Tuberia C�Presion Tuberia B = 100 si Valvula A abierta o 50 si Valvula A cerrada�Presion Tuberia C = 90���Sensado:�Valvula A cerrada���Pregunta:�Presion Tuberia A? → → 95

​

5

Entorno parcialmente observable

Valor percibido

Valor inferido

6 of 28

Introducción

  • Ejemplo�Conocimiento de base:�…�Tuberias explotan si Presion > 70�Presion Tuberia A = Presion Tuberia B + 1/2 Presion Tuberia C�Presion Tuberia B = 100 si Valvula A abierta o 50 si Valvula A cerrada�Presion Tuberia C = 90��Sensado:�Valvula A cerrada���Pregunta:�Explota alguna tuberia? → → [A, C]

​

6

Nuevo conocimiento

Nuevas Respuestas

7 of 28

Introducción

  • Knowledge-based Agents: Qué hace falta
    • Un lenguaje de representación de conocimiento → Knowledge Base (Base de Conocimientos)
    • Un mecanismo que permita operar sobre ese conocimiento para
      • Obtener conclusiones
      • Elegir acciones
      • Responder preguntas
      • Etc�
  • Lógica
    • Proposicional
    • Primer Orden
    • Difusa
    • Etc.

​

7

8 of 28

Introducción

  • Una KB está formada por oraciones lógicas
  • Lógica
    • Sintaxis: define las oraciones que están bien formadas → oraciones “legales”
      • Ej:
        • X + 4 = 10 vs. X41+0=
        • A > B ^ B > C vs. A>^>BBC
    • Semántica: define el significado de las oraciones lógicas → valor de verdad de cada oración en cada “mundo posible” (en cada modelo posible: asociación de valores de verdad)
      • Ej: x+y=4 es Verdadera cuando {(x=1, y=3), (x=2,y=2), …} y Falsa cuando {(x=3,y=3)...}

​

8

9 of 28

Introducción

  • Lógica (cont.)
    • Inferencia
      • Permite implementar el razonamiento
      • Se basa en el llamado entailment (implicancia) → una conclusión ɑ se deriva de la base de conocimientos KB: KB ⊨ ɑ
      • El algoritmo de inferencia será válido (sound) si se basa en reglas de inferencia válidas y la KB es válida ⇒ en cada modelo en que la KB es válida, ɑ también lo es
      • El algoritmo de inferencia será completo (complete) si puede derivar (o concluir) cualquier oración lógica implicada (entailed) por la base de conocimientos

​

9

10 of 28

Introducción

  • Lógica (cont.)
    • Base de conocimientos
      • Tiene 2 grandes tipos de conocimiento
        • Background knowledge�Axiomas, relaciones, reglas del dominio, etc.���
        • Ground truth�Hechos que se dan en una instancia específica del dominio

10

Sensores

Conocimiento incorporado

Aprendizaje Automático

11 of 28

Lógica Proposicional

12 of 28

Lógica Proposicional

  • Sintaxis
    • Oraciones atómicas
      • Valores especiales Verdadero (V) y Falso (F)
      • Símbolos proposicionales que pueden ser V o F
        • Ej: ValvulaA, TuberiaA, PresionTuberiaA50
    • Operadores lógicos
      • ¬ (no)
      • ^ (y, conjunción)
      • v (o, disyunción)
      • ⇒ (implicación). El término a la izquierda se llama antecedente, el término a la derecha se llama consecuente. Ej: PresionTuberiaA100 ⇒ TuberiaAExplota
      • ⇔ (bicondicional o doble implicación). “Si y solo si” (también llamada equivalencia lógica)

​

12

13 of 28

Lógica Proposicional

  • Sintaxis
    • Oraciones complejas
      • Se forman combinando oraciones atómicas con los conectores anteriores
        • Ej: PresionTuberiaA70 ^ PresionTuberiaB90 ⇒ ExplotaTuberiaC

13

14 of 28

Lógica Proposicional

  • Semántica
    • Reglas para determinar el valor de verdad de una oración lógica para un modelo concreto
    • Esas reglas se definen mediante tablas de verdad

14

15 of 28

Lógica Proposicional

  • Equivalencias
    • 2 sentencias 𝛼 y β son equivalentes si tienen los mismos valores de verdad en el mismo conjunto de modelos (recordemos: modelo → asociación de valores de verdad a cada proposición)

​

15

16 of 28

Lógica Proposicional

  • Reglas de inferencia
    • Son patrones de razonamiento�
    • Se demuestra que son sound, demostrando que son verdaderas en todos los casos (a.k.a. tautologías) mediante sus tablas de verdad�
    • Algunos ejemplos
      • Modus ponens�𝛼, 𝛼 ⇒ β ⊨ β�
      • Eliminación-^�𝛼 ^ β ⊨ 𝛼�𝛼 ^ β ⊨ β

16

17 of 28

Lógica Proposicional

  • Inferencia práctica
    • Existen algoritmos de inferencia completos (algoritmo de resolución, resolution)�
    • En ocasiones su costo computacional puede ser elevado�
    • Muchas KB del mundo real no necesitan toda la expresividad de la lógica
      • Frecuentemente pueden crearse grandes KB hechas con cláusulas de Horn
        • Una cláusula de Horn es una disyunción de literales en la que como máximo uno es positivo
          • ¬A v ¬B v C ≡ A ^ B ⇒ C

17

Cabeza

Cuerpo

18 of 28

Lógica Proposicional

  • Inferencia práctica
    • Encadenamiento hacia adelante: dirigido por datos
      • Parte de los hechos hacia las consecuencias�
    • Encadenamiento hacia atrás: dirigido por objetivos
      • Parte de una consulta y trata de demostrarla��

​

18

19 of 28

Lógica de Primer Orden (LPO)

20 of 28

Lógica de Primer Orden

  • Problema de la Lógica Proposicional
    • Expresividad muy limitada: solo permite proposiciones (hechos) V o F
      • Ej:
        • Presión en Tubería A = 100
          • PresionTuberiaA100
        • Si presión en Tuberia X > 100 → Explota tubería X
          • PresionTuberiaA101 → ExplotaTuberiaA
          • PresionTuberiaA102 → ExplotaTuberiaA
          • …
          • PresionTuberiaB101 → ExplotaTuberiaB
          • …
    • Explosión combinatoria no sólo en la búsqueda, también en el modelado!�

20

21 of 28

Lógica de Primer Orden

  • Lógica de Primer Orden (LPO)
    • La ontología de la LPO, incluye objetos y relaciones entre ellos, con lo que se modelan hechos que pueden ser V o F
    • Esto permite simplificar mucho el modelado y achicar las bases de conocimiento
      • Ej: Presión en Tubería A = 100 � presion(tuberiaA, 100)�
      • Si presión en Tuberia X > 100 → Explota tubería X� KB:� presion(TuberiaX, P) ^ P > 100 ⇒ Explota(TuberiaX)� presion(tuberiaA, 110)

Consulta:�explota(tuberiaA)?

21

22 of 28

Lógica de Primer Orden

  • Sintaxis de la LPO

22

23 of 28

Lógica de Primer Orden

  • Programación lógica
    • PROLOG es el lenguaje más utilizado�
    • Parte de la sintaxis de la LPO
      • Variables
      • Predicados
      • Conectores lógicos
      • Manejo de listas y números
    • Es una versión simplificada
      • Sólo admite cláusulas de Horn
      • No hay cuantificadores
      • Tiene otras limitaciones respecto a la LPO�
    • Ejemplos�

​

23

24 of 28

Lógica de Primer Orden

  • Prolog. Algunas características
    • Admite cláusulas Positivas (cláusulas de Horn con cabeza positiva)�
    • Algoritmo de control: encadenamiento hacia atrás con búsqueda en profundidad → riesgo de recursión infinita (por lo tanto no es completo si no se toman precauciones)�
    • Permite incrementar o reducir la KB con hechos (assert/1, retract/1)�
    • Negación: caso particular→ negación como fallo�
    • Las oraciones tienen una relación implícita de conjunción�
    • La coma (,) representa ^ y el punto y coma (;) v

​

24

25 of 28

Lógica de Primer Orden

  • Prolog. Algunas características
    • Soporta manejo de listas con []�
    • Funciones built-in para aritmética�
    • Es posible integrarlo con otros lenguajes de programación
      • Es posible usar el motor de inferencia como parte de un agente más complejo, instanciando y consultando
        • Ej: un agente de búsqueda puede consultar la KB para saber cuáles son los estados consistentes que pueden visitarse
          • Agentes híbridos
      • Es posible hacer llamadas “hacia afuera” desde Prolog.
        • Ej: Un predicado puede resolverse tomando una lectura de un sensor

�

25

26 of 28

Ingeniería de Conocimiento

27 of 28

Ingeniería de conocimiento

  • Identificar la tarea
    • Funcionalidad (responder preguntas? Elegir acciones?) → actuadores; tipo de sensores; tipos de datos a manipular
  • Recopilar conocimiento relevante
    • No se codifica aun, solo se busca entender el dominio
  • Definir el vocabulario de predicados, funciones y constantes
    • Se define cómo se representa cada pieza de conocimiento, cuando más de una representación es factible (ej: como un predicado, como una constante, etc) → Ontología del dominio
  • Codificar el conocimiento general del dominio
    • Se empieza a crear la KB → “programar” el conocimiento recopilado
  • Codificar una descripción de la instancia de un problema específico
    • Se incorporan ground facts similares a los que se obtendrían de los sensores
  • Plantear peticiones al proceso de inferencia y obtener respuestas
    • Probar la KB con el conocimiento del dominio y la ground truth para obtener respuestas
  • Depurar la KB

27

28 of 28

Preguntas? �Opiniones?