Tema 3: Representación del conocimientojjalvarez/asignaturas/descargados/inteligencia... · Tema...
Transcript of Tema 3: Representación del conocimientojjalvarez/asignaturas/descargados/inteligencia... · Tema...
Tema 3: Representación delconocimiento
1
• Introducción- Representación declarativa vs. procedimental- Enfoques y métodos de representación
• Métodos básicos de representación- Lógica- Sistemas de producción
• Métodos estructurados de representación- Redes semánticas- Marcos- Guiones- Dependencia conceptual
Problemas básicos en el diseño de SBC
2
• Representación del conocimiento
• Modelos de razonamiento
• Estrategias de control
•Adquisición del conocimiento
Representación declarativa vs. procedimental
3
ENFOQUE DECLARATIVO(∀X)(persona(X)) mortal(X)(∀X)(perro(X)) mortal(X)persona(Sócrates)persona(Eva)perro(Lassie)
FLEXIBILIDAD, MODULARIDAD
ENFOQUE PROCEDIMENTALfunction persona(X)
IF (X=Sócrates) or (X=Eva) THEN return true ELSE return falsefunction perro(X)
IF (X=Lassie) THEN return true ELSE return falsefunction mortal(X)
IF persona(X) or perro(X) THEN return true ELSE return falseEFICACIA DE EJECUCIÓN
Representación declarativa vs. procedimental
4
(1) Si cheque completo y portador conocido y fondos suficientes entonces pagar
(2) Si fecha correcta y firmado y fondos suficientes y portador identificado y ... entonces cheque completo
(3) Si fecha cheque es hoy o fecha cheque entre 1 y 90 días antes de hoy entonces fecha correcta
DECLARATIVOPROCEDIMENTALCliente presenta cheque
para cobrar
¿El cheque es de este banco?
¿Tiene elportadorcuenta
en este banco?¿Está totalmentecumplimentado,
firmado y endosado?
¿Tiene el portadorD.N.I.?
Utilizar el terminal:¿tiene suficiente saldo
el firmante?
Pagar
Pedir firma
No
No
No
Si
SiRechazar
No endosado
No firmado
Rechazar
SiSi
No
Paradigmas de representación del conocimiento
5
• ENFOQUES:- Lógico- Funcional- Orientado a objetos
• MÉTODOS:- Sistemas de producción- Redes semánticas- Marcos- Guiones- Dependencia conceptual
Importancia de la lógica formal en la I.A.
6
• PARA REPRESENTACIÓN- frecuentemente, modo “natural” de representación.- otros esquemas de representación pueden formalizarse
en lógica• PARA RAZONAMIENTO
- modelos matemáticos rigurosos para inferencia ydeducción
- modelos para razonamiento aproximado•PARA CONSTRUCCIÓN DE S.B.C.
- “algoritmo = lógica + control”- programación lógica
Tipos de lógica
7
• De proposiciones• De predicados de primer orden y ordenes
superiores• Modal• Temporal• Multivalorada• Borrosa• O-A-V o 0+• etc.
Lógica de proposiciones
8
• Introducción y definiciones• Formalización e interpretación• Sistema axiomático
- Definición- Teoremas útiles
• Sistema inferencial- Definición- Regla de resolución- Regla de refutación
Lógica de proposiciones: Introducción
9
• Basada en la lógica clásica:Conceptos de juicio, proposición, razonamiento.
• Proposición: enunciado declarativo (frases en indicativo)
Representación: variable proposicional (p, q, r, ...)
• Sentencia: enunciado compuesto por enunciados elementales y constructores primitivos (conectivas)
Lógica de proposiciones: Conectivas
10
Conectivas:• Unarias (o monádicas):
• Negación (⌝p)• Binarias (o diádicas):
• Conjunción (∧) • Condicional (→)• Disyunción (∨) • Bicondicional (↔)
VVVVFVVFFVFFFVFVVFVVFVVFFVFF
p↔qp→qp∨qp∧q⌝pqp
Lógica de proposiciones: Interpretación
11
Tablas de verdad
Ejemplo: “Si tengo hambre o sed entonces voy al bar”(p ∨ q) → r
VVFVFFVV
FFVFVVVF
VVVV
FFFV
VVFFVFFF
(p∨q) → rrqp
Lógica de proposiciones: Interpretación
12
Ejemplo: Muchos razonamientos consisten en obtener una conclusión a partir de una serie de premisas (p1∧p2∧....) → c. Un razonamiento es válido si es una TAUTOLOGíA.
p1: “Si Bernardo se casa entonces Florinda se suicida”.p2: “Florinda se suicida si y sólo si Bernardo no se hace monje”.c: “Si Bernardo se casa entonces no se hace monje”.
p1: c → sp2: s ↔ ⌝m Razonamiento: (c → s) ∧ (s ↔ ⌝m) → (c → ⌝m)c: c → ⌝m
Si construimos la tabla de verdad veremos que es una tautología y por tanto el razonamiento será válido.
Sistema axiomático
13
• Formalización de la lógica de proposiciones
• Elementos:- Alfabeto- Reglas de formación- Axiomas- Reglas de transformación
•Propiedades del conjunto de axiomas:- Debe ser completo.- Debe ser consistente.- Conviene que sea independiente.
Sistema axiomático
14
• Alfabeto:- variables proposicionales: p, q, r, s, ...- conectivas: → ∧ ∨↔ ⌝- ( ), [ ], { }- Metasímbolos:
- Sentencias: A, B, C, ...- Cualquier conectiva: k- Literal: l
• Expresión (o cadena):Toda secuencia finita de símbolos del alfabeto
Sistema axiomático
15
• Sentencia:- Una expresión válida- Definición (reglas de formación):
1. Una variable proposicional es una sentencia2. Si A es una sentencia, ⌝A también lo es3. Si A y B son sentencias A k B también lo es
• Equivalencia:- Dos sentencias son equivalente si “significan” lo mismo- Ejemplo: A ∨ B equivale a B ∨ A
Sistema axiomático
16
• Axiomas:- Construcciones que se admiten universalmente
como verdaderas- El sistema axiomático más conocido es el PM
A1: (p ∨ p) → pA2: q → (p ∨ q)A3: (p ∨ q) → (q ∨ p)A4: (p → q) → [(r ∨ p) → (r ∨ q)]
Sistema axiomático
17
• Demostración (o prueba formal):- Toda secuencia finita de sentencias A1, A2, ...,
An, donde cada Ai cumple, al menos una de las siguientes condiciones:1. Ai es un axioma2. Existe algún j<i y alguna sustitución S tal
que Ai es el resultado de aplicar S sobre Aj (es decir, Ai es AjS)
3. Existe h<i y j<i, tal que Ai es Ah ∧ Aj4. Existe h<i y j<i, tal que Ah es Aj → Ai
Sistema axiomático
18
• Teorema:- Toda sentencia An que no es un axioma y tal que
existe una demostración A1, A2, ..., An.- Diremos que la secuencia A1, A2, ..., An es una
demostración del teorema An.- Un teorema puede tener más de una
demostración.• Tesis (o ley):
Cualquier sentencia que sea un axioma o un teorema (⊦A).
Sistema axiomático
19
• Reglas de transformación:- Podemos definir una tesis de manera recursiva
mediante las siguientes reglas de transformación:1. Si A es un axioma, entonces es una tesis2. Si A es una tesis en la que aparecen p1, p2, ...,
pn y B1, B2, ..., Bn son sentencias, entonces A{B1/p1, B2/p2, ..., Bn/pn} es una tesis (regla de la sustitución).
3. Si A y B son tesis, entonces A ∧ B es tesis (regla de la unión).
4. Si A y A → B son tesis, entonces B es tesis (regla de la separación).
Sistema axiomático
20
• Ejemplo de demostración:Teorema: (p → q) → [(r → p) → (r → q)]
Demostración:
1. (p → q) → [(⌝r ∨ p) → (⌝r ∨ q)]Sustitución {⌝r/r} en A4
2. (p → q) → [(r → p) → (r → q)]Por la definición de →
Sistema axiomático
21
• Algunos teoremas útiles:- Ley de modus ponendo ponens (o modus ponens)
[p ∧ (p → q)] → q- Ley de modus tollendo tollens (o modus tollens)
[⌝q ∧ (p → q)] → ⌝p- Leyes de la transitividad
[(p → q) ∧ (q → r)] → (p → r)[(p ↔ q) ∧ (q ↔ r)] → (p ↔ r)
- Leyes de inferencia de la alternativa[⌝p ∧ (p ∨ q)] → q[p ∧ (⌝p ∨ ⌝q)] → ⌝q
- Ley del dilema constructivo[(p → q) ∧ (r → s) ∧ (p ∨ r)] → (q ∨ s)
Sistema axiomático
22
• Algunos teoremas útiles (II):- Leyes de DeMorgan:
⌝(p ∧ q) ↔ (⌝p ∨ ⌝q)⌝(p ∨ q) ↔ (⌝p ∧ ⌝q)
- Doble negación:⌝⌝p ↔ p
- Reducción al absurdo:[⌝p → (q ∧ ⌝q)] ↔ p
- Distributividad:[(p ∧ q) ∨ r] ↔ [(p ∨ r) ∧ (q ∨ r)][(p ∨ q) ∧ r] ↔ [(p ∧ r) ∨ (q ∧ r)][(p → q) ∨ r] ↔ [(p ∨ r) → (q ∨ r)][(p → (q ∨ r)] ↔ [(p → q) ∨ (p → r)]. . .
Sistema axiomático
23
Interpretaciones semánticas:
• El cálculo es independiente de la semántica
• Se pueden formalizar interpretaciones• Ejemplos:
- Interpretación binaria: variables = 0, 1(Álgebra de Boole)
- Lenguaje natural: razonamientos habituales
Análisis y generación de razonamientos
24
• Una vez formalizado un razonamiento, puede analizarse y, además, puede completarse con nuevas conclusiones de forma automática.
• Necesitamos un procedimiento que dados P1, P2, ... Nos permita obtener C1, C2, ... tales que:
⊦ (P1 ∧ P2 ∧ ... → C1)⊦ (P1 ∧ P2 ∧ ... → C2). . .
• Es decir, queremos poder derivar conclusiones a partir de unas premisas
Análisis y generación de razonamientos
25
• Inferencia:Proceso para obtener una conclusión a partir deunas premisas de modo que el razonamiento seaválido.
• Regla de inferencia:- Condiciones bajo las que puede hacerse una
inferencia, así como el resultado de la misma.- Ejemplo:
Razonamiento: [(p → ⌝q) ∧ (⌝q → r)] → (p → r) Es un razonamiento correcto ya que es una teorema.Dados P1: p → ⌝q y P2:⌝q → r, podemos concluir (ya que la sentencia es un teorema) C: p → r
Diferencia entre tesis y regla de inferencia
26
• Tesis: [A ∧ (A → B)] → B• Regla: De A y de A → B puede inferirse B
Es una diferencia lingüística
Para diferenciarlas, las reglas de inferencia suelen representarse así:
AA → BB
Reglas de inferencia
27
• Ejemplos:A ⌝B ⌝A A A → BA → B A → B A → B ⌝A ∨ ⌝B C → D
B ⌝ A B ⌝B A ∨ CB ∨ D
En los tratados de lógica se presentan conjuntos seleccionados de reglas de inferencia bajo el nombre de “sistemas de deducción natural”.
Un conjunto de reglas es deseable que sea:• Consistente• Completo
Sistema inferencial
28
• Formalización de los conceptos anteriores
• Elementos:- Reglas de inferencia- Metarreglas
•Propiedades del conjunto de reglas de inferencia:- Debe ser completo.- Debe ser consistente.
Forma clausulada de una sentencia
29
• Cláusula:sentencia de la forma l1 ∨ l2 ∨ l3 ∨ ... ∨ ln
• Forma clausulada (de una sentencia): Expresión de la sentencia mediante una conjunción de
cláusulas.(l11 ∨ l12 ∨ l13 ∨ ... ∨ l1n) ∧ (l21 ∨ l22 ∨ l23 ∨ ... ∨ l2n) ∧ ...
TEOREMA:Toda sentencia de la lógica proposicional tiene una sentencia equivalente en forma clausulada.
Forma clausulada de una sentencia
30
PASO DE UNA SENTENCIA A FORMA CLAUSULADA:
1. Eliminar condicionales y bicondicionales.(A → B) ↝ (⌝A ∨ B)(A ↔ B) ↝ (⌝A ∨ B) ∧ (A ∨ ⌝B)
2. Hacer que las negaciones sólo afecten a variables proposicionales (mediante leyes de DeMorgan).
3. Paso a forma clausulada mediante la ley distributiva de ∧sobre ∨.
4. Simplificar
Las cláusulas como sentencias condicionales
31
Cualquier cláusula se puede escribir como una sentencia condicional.
Cláusulas importantes:- Cláusula de Horn con cabeza: un solo literal positivo
(p1 ∧ p2 ∧ ... ∧ pn) → q1- Cláusula de Horn sin cabeza: sin literales positivos
(⌝p1 ∨ ⌝p2 ∨ ... ∨ ⌝pn) ↝ ⌝(p1 ∧ p2 ∧ ... ∧ pn) - Sin literales negativos
(q1 ∨ q2 ∨ ... ∨ qm)- Clausula vacía
(λ)
La Regla de Resolución (Robinson, 1965)
32
Se aplica a dos premisas en forma de cláusulas, tales que tengan en común un literal, positivo en una y negativo en la otra (las cláusulas se denominan generatrices).
Resolución: construir otra cláusula (resolvente) formada por todos los literales de las generatrices salvo el común.
Ejemplo:p ∨ ⌝q
⌝ p ∨ r ∨ s⌝q ∨ r ∨ s
La Regla de Resolución
33
Las reglas “clásicas” pueden escribirse como “resoluciones”:
Modus ponens: p pp → q ⌝ p ∨ qq q
Modus tollens: ⌝ q ⌝ q p → q ⌝ p ∨ q
⌝ p ⌝ p
Transitividad: p → q ⌝ p ∨ qq → r ⌝ q ∨ rp → r ⌝ p ∨ r
La Regla de Resolución
34
El sistema inferencial formado por la regla de resolución, para la lógica de proposiciones es:
• Consistente, ya que le regla de la resolución se fundamenta en una tesis.
• Completo si consideramos las conclusiones triviales (p → p ∨ q , p → p ∨ ⌝q , etc.)
Sistema inferencial
35
Ejemplo:
P1: (p ↔ q)P2: ⌝(p ∧ q ∧ r)
Inferencias posibles aplicando resolución de manera exhaustiva:
C1: ⌝p ∨ ⌝rC2: ⌝q ∨ ⌝r
Si a estas conclusiones añadimos las triviales tendremos todas las posibles inferencias.
Refutación
36
Proceso útil cuando no se quieren generar nuevas conclusiones sino comprobar si una determinada conclusión se puede deducir a partir de unas premisas dadas.
El proceso de refutación consiste en comprobar si el conjunto de cláusulas formado por las premisas y la conclusión negada es una contradicción (cláusula vacía), lo cual indica que la conclusión puede inferirse de las premisas (ley de reducción al absurdo).
Resumen
37
Sistema axiomático Sistema inferencial
ExpresionesSentencias
Variables prop.
Tesis
Concl.
Premisas
Axiomas
• REGLAScondiciones acción
Sistemas de producción: definición (Rich, 1983)
38
• Una o más B.D.
• Estrategia de control(orden de aplicación de reglas y resolución de conflictos)
Reglas de producción
39
• Componentes elementales: hechosRepresentan propiedades de objetos o relaciones entre éstos:
Vector de característicasTuplas (Objeto, Atributo, Valor)
• Acciones elementales: reglasDemostrar hipótesis o extraer conclusiones
Situación/AcciónPremisas/Conclusión
(∀ x,y) f(x) ∧ g(y) → h(x,y)
Sistemas de producción: motor de inferencias
40
CICLO DE BASE:
Detección de reglas aplicables
Elección de regla
Aplicación
Actualización BH
Sistemas de producción: motor de inferencias
41
ESTRATEGIAS BÁSICAS:
ENCADENAMIENTO HACIA ADELANTE
ENCADENAMIENTO HACIA ATRAS
(forward chaining)
(backward chaining)
Estadoinicial
Conclusionesintermedias Soluciones
Reglas y hechos
Estadoobjetivo Subobjetivos Soluciones
Reglas y hechos
Sistemas de producción: motor de inferencias
42
EJEMPLO DE SECUENCIA INFERENCIAL:
• BC: R1: A → C R6: D∧G → BR2: A → H R7: C∧F → BR3: C → D R8: A∧H → DR4: D → E R9: A∧C∧H → BR5: B∧F → X R10: A∧B∧C∧H → F
• BH0: {A}• Objetivo: X
ENCADENAMIENTO HACIA ADELANTE
BH: A C H D E B F X
R: 1 2 3 4 9 10 5
Sistemas de producción: motor de inferencias
43
EJEMPLO DE SECUENCIA INFERENCIAL (II):
ENCADENAMIENTO HACIA ATRASX
B F
G(no) A C
D C F H A A B C H
A C A A (si) A A
H
A A A B C H
A A (bucle)
Lógica de predicados: terminología
44
• Se entra en la composición de las proposiciones: en lugar de variables proposicionales, PREDICADOS aplicados a constantes o variables.
• PREDICADOS:- monádicos: P(x) (propiedades)- poliádicos: P(x,y,...) (relaciones)
• Cuantificadores:- Universal: (∀x)(P(x))- Existencial: (∃x)(P(x))
Lógica de predicados
45
•No existe un procedimiento general para determinar la validez de una sentencia: Cálculo de predicados es indecidible.
• Existe un procedimiento tal que si una sentencia es válida termina dictaminándolo y si no lo es no termina, por lo que también se dice que el cálculo de predicados es semidecidible.
Lógica de predicados: sistema inferencial
46
• Las reglas de resolución y refutación forman un sistema inferencial consistente y completo para la lógica de predicados.
• Para la obtención de todas las posibles conclusiones sería necesaria una búsqueda exhaustiva lo que nos lleva a la aparición de explosión combinatoria debido a la existencia de variables, por lo que se utilizan técnicas incompletas.
Otros tipos de lógica
47
• De predicados de ordenes superioresPredicados como variables y predicados cuantidicados
• ModalPara interpretación de mundos concebibles
• TemporalInterés para razonamiento temporal
• MultivaloradaProposiciones/predicados con múltiples valores posiblesInterés para tratamiento de la incertidumbre
• BorrosaFunciones de pertenencia no binarias
• etc.
Representaciones estructuradas del conocimiento
48
• Redes semánticasRepresentación declarativa de objetos, atributos y relaciones
• Dependencia conceptualRepresentación del significado de frases de lenguaje natural
• Marcos (frames)Combinan redes semánticas con reglas y conocimiento procedimental
• Guiones (scripts)Permiten representar secuencias de acontecimientos
Redes semánticas
49
GRAFOS ORIENTADOS
- Nodos: objetos o conceptos o propiedades (atributos)
- Arcos: relaciones binarias (es_un, parte_de, tiene, etc.)
- Herencia de propiedades como mecanismo inferencial
básico.
Redes semánticas
50
EJEMPLO:
Dependencia conceptual
51
• Schank, 1973
• Componentes básicos del universo:- Entidades: actores, acciones y sus propiedades
respectivas- Acciones: combinación de 12 acciones elementales- Casos conceptuales: objeto, receptor, instrumento, etc.- Tiempos conceptuales: presenta, pasado, futuro,
condicional, intemporal, etc.- Dependencia conceptual: relaciones entre los anteriores
• Utilización: sistemas de comprensión de textos(representación del significado de frases en lenguajenatural)
Marcos (frames)
52
• ESTRUCTURASQue representan objetos o conceptos
• CON RANURAS (SLOTS)Que representan propiedades o partes o procedimientos asociados
• VALOR DE UNA RANURA- Fijo- Por defecto- Por herencia- Activación de procedimiento
Marcos (frames)
53
• Describen objetos o conceptos en términos de atributos (slots) y los valores de éstos
• Los atributos pueden tener procedimientos asociados (demonios) que se ejecutan cuando se altera o se accede a la información del slot (valor del atributo)
• Los marcos se organizan en una jerarquía de clases incorporando mecanismos de herencia
Ranuras (slots)
54
• Cada ranura tiene facetas (facets) asociadas:-Valor del atributo (almacenado, heredado, calculado)-Constricciones que debe satisfacer-Procedimientos llamados cuando se accede a la ranura o se altera su valor-Origen de los valores heredados
• Las ranuras describen un atributo que puede ser:-Declarativo (hecho o relación)-Procedimental (llamada a un procedimiento)
• Los valores de atributos pueden estar constreñidos:-Pertenecer a una clase, combinación lógica de clases, conjunto enumerado, tipo de datos predefinido o subrango-Tener cardinalidades mínima o máxima-Tener valores por defecto
Agrupamiento de marcos
55
• Marcos organizados en una jerarquía de clases, subclase y miembros.
• Las clases y subclases son también marcos.• Los marcos que pertenecen a la misma clase tienen las
mismas ranuras básicas.• Herencia: mecanismo mediante el cual un marco (clase)
transfiere una estructura básica (conjunto de ranuras) a otro marco (subclase o miembro).
• Tipos de ranuras:-de clase (member slots): describen atributos comunes a los miembros de una clase (información heredable).-propias (own slots): describen atributos particulares (información local, no heredable).
• Un marco puede pertenecer a múltiples clases y subclases.
Guiones (scripts)
56
• Son estructuras que representan una secuencia típica de sucesos.• Un guión está constituido por ranuras:
-Conjunto de condiciones de entrada que deben satisfacerse para que se materialice el guión-Conjunto de papeles: actores típicos del guión-Conjunto de propiedades: objetos típicos que aparecen en el desarrollo del guión-Conjunto de escenas: representan la secuencia de sucesos que constituyen el guión-Conjunto de resultados: condiciones que se satisfacen tras realizarse la secuencia de escenas
• Razonamiento por guiones:-Los guiones se activan por coincidencia de nombre, precondiciones, papeles, etc.-Objetivo: inferir, por medio de razonamiento por defecto, conocimiento que no ha sido dado de forma explícita
Guiones: Ejemplo
57
• NOMBRE: Cine• PAPELES: cinéfilo, taquillero, portero, acomodador• CONDICIONES DE ENTRADA: cinéfilo desea ver película• PROPIEDADES: película, butaca, dinero, entrada• ESCENAS:
-Sacar entradaCinéfilo MTRANS “deme butaca” a taquilleroCinéfilo ATRANS dinero a taquilleroTaquillero ATRANS entrada a cinéfilo
-Entrar en salaCinéfilo ATRANS entrada a porteroPortero ATRANS entrada a cinéfiloCinéfilo PTRANS cinéfilo a sala
-Acomodarse ...................-Ver película ..................-Salir de sala ..................
• RESULTADOS:-Cinéfilo ha visto la película-Taquillero tiene más dinero-Cinéfilo tiene menos dinero