UNIVERSIDAD TECNOLÓGICA AMÉRICA
FACULTAD DE CIENCIAS DE LA COMPUTACIÓN Y ELECTRÓNICA
Hugo Leon
OCTAVO NIVEL
3.1 El Problema de la Representación del Conocimiento
3.1.1 Aspectos Generales
Punto clave en la Inteligencia Artificial:
• Uso de conocimiento y de mecanismos para representarlo manejarlo computacionalmente
• Diferencia con informática convencional:
->uso extensivo de conocimiento del dominio
Hasta ahora (búsqueda espacios estados) hemos visto representaciones ”ad-hoc” para cada problema concreto
(a) Jerarquía del Conocimiento
Metaconocimiento
(b) Uso del conocimiento en Inteligencia Artificial
Sistemas Basados en el Conocimiento: Sistemas de Inteligencia Artificial que hacen un uso extensivo del conocimiento específico de un dominio.• base de conocimiento: conjunto de representaciones de hecho y relaciones relevantes en un dominio
Identificar conocimiento necesario para resolver un problema
Seleccionar un lenguaje con el que representar ese conocimiento
Traducir conocimiento a ese lenguaje de representación
Usar las consecuencias derivadas de ese conocimiento pararesolver el problema
Pasos Generales:
3.1.2 Objetivos de los Métodos de Representación del Conocimiento
Representación del conocimiento
Todo lenguaje de representación debe definir 2 aspectos
• semántica: determina la relación entre los elementos del lenguajey su interpretación en el dominio
•sintaxis: posibles formas de construir y combinar los elementosdel lenguaje para representar los hechos del dominio real
3.1.3 Propiedades de los Esquemas de Representación
ADECUACIÓN DE LA REPRESENTACIÓN:
Capacidad del esquema derepresentación para
representar adecuadamente todo el conocimiento
pertinente de un dominio
ADECUACIÓN INFERENCIAL: Posibilidad de manipular
las estructuras de representación de forma que
se puedan derivar nuevasestructuras asociadas
con nuevo conocimiento inferido a partir del
antiguo
EFICIENCIA INFERENCIAL: Posibilidad de mejora del proceso inferencialmediante la inclusión de heurísticas y guías
que agilicen lainferencia
EFICIENCIA ADQUISICIONAL: Capacidad del esquema
para incorporarfácilmente nuevo conocimiento
3.1.1 Clasificación de los Esquemas de Representación
ESQUEMAS
DECLARATIVOS:• Énfasis en
representación de los hechos relevantes del dominio
ESQUEMAS
PROCEDIMENTALES
Énfasis en representar y soportar
las relaciones inferencial
es deldominio
Tipos de modelos de representación del conocimiento
Modelos formales (lógica clásica)
Modelos estructurados
Uso de técnicas de representación especializadas
Uso de la lógica formal como lenguaje de representación
Método de representación del conocimiento bien conocido y muy usado
base teórica muy sólida mecanismos inferencia conocidos y potentes
Toda lógica que sea usada como mecanismo de representación deberá constar de 3 elementos:
1. Una sintaxis, que explica cómo construir los elementos del lenguaje de representación (oraciones lógicas)
2. Una semántica, que asocia los elementos del lenguaje con los elementos reales del dominio
asocia una interpretación (significado) a los símbolos
3. Un conjunto de reglas de inferencia, que permiten inferir conocimiento nuevo a partir del ya existente
3.2 Representaciones Formales Lógica
TIPOS DE LÓGICAS
Lógica de proposiciones Lógica de predicados
de 1er orden
Lógica más sencilla
Más potente y con mayor utilidad práctica
3.2.1 Lógica de Proposiciones
(a) SINTAXIS ELEMENTOSÁtomos
• constantes lógicas: verdadero (V), Falso (F) • proposiciones lógicas:
(strings de caracteres)
(b) SEMÁNTICA
En todas las lógicas la semántica
de una oración depende de la interpretación concreta
que se le asigne a los símbolos
(proposiciones /predicados + conectivas),
semántica composicional.
Correspondencia entre elementos del lenguaje y los elementos del mundo real que representan
En lógica proposicional -> semántica directa
Interpretación = asignación valores de verdad a proposiciones
Una f.b.d. (oración) es verdadera o falsa según los valores de verdad o falsedad de los símbolos que la componen
(c) REGLAS DE INFERENCIA
Mecanismos sintácticos que permiten deducir f.b.d. a partir de otras
f.b.d. distintas
•Representan patrones de inferencias usados comúnmente•Procedimientos formales: nuevas f.b.d. resultan de transformar sintácticamente la forma de las f.b.d. de partida•No se tiene en cuenta el significado de los elementos de la lógica (proposiciones en este caso)
Reglas más comunes
DEMOSTRACIÓN
METATEOREMAS
Teoremas a cerca del cálculo proposicional (no son parte de la lógica de proposiciones)
DEDUCCIÓN:
•Por tabla de verdad de la conectiva ”!”, el resultado delimplica ser´a siempre V
REDUCCIÓN AL ABSURDO:
•proporcionan criterios para determinar si se cumple o no la relación de consecuencia lógica
COMPLETITUD Y SOLIDEZ (propiedades reglas de inferencia)
”Una regla de inferencia Res solida si siempre que `R ,
Entonces |= ”Solido Correcto (sound)
La regla sólo genera/demuestra f.b.d. que son consecuencia lógica
de Genera oraciones que siempre
son verdaderas en el dominio actual
”Si siempre que |= existe una demostración que usando R permite que `R , se diría que R es
completa” La regla R es capaz de proporcionar una demostración a todas las f.b.d. que son consecuencia lógica de .
en resumen:Si una regla R es sólida y completa podremos determinar todas las f.b.d. que son consecuencia lógica de (base de conocimiento actual), mediante la búsqueda de una demostración.
Tengo 5 pesos, si compro dos manzanas a 1 peso c/u ¿Cuánto me queda?
Tenemos datos y aplicamos una serie de operaciones sobre ellos para resolverlo
En este caso realizamos una abstracción y tomamos los datos importantes para resolver el problema ¿Cuánto dinero tengo inicialmente? ¿Cuántas manzanas quiero y cuanto cuestan? Multiplicamos y restamos
Representando para resolver
No fue necesario pensar en manzanas para resolverlo, sólo en enteros y a ellos les aplicamos una serie de operaciones bien conocidas
El verbo [comprar] estrictamente hablando nunca fue representado pero fue indispensable para saber lo que se deseaba hacer con los datos.
Necesitamos conocimiento y mecanismos para manipularlo y así resolver el problema en el caso de los humanos esta distinción no es fácil, es
por ello que no es algo obvio para nosotros hacer esta diferencia
Representando para resolver
Esquema general de la representación
Dos niveles:
El nivel del conocimiento – real
El nivel del formalismo – abstracción
Esquema general de la representación
Hechos: verdades en un cierto mundo. Es aquello que queremos representar.
Esquema general de la representación
Hechos: verdades en un cierto mundo. Es aquello que queremos representar.
Representaciones de los hechos en un determinado formalismo. Éstas son las entidades que realmente seremos capaces de manipular.
Esquema general de la representación
Caso concreto: la programación
tenemos un problema, lo analizamos, proponemos un algoritmo, lo programamos en un lenguaje e interpretamos los resultados
Suficiencia de la representación: La capacidad de representar todos los tipos de conocimiento necesarios en el dominio.
Suficiencia deductiva: La capacidad para manipular las estructuras de la representación con el fin de obtener nuevas estructuras que correspondan con un nuevo conocimiento deducido a partir del antiguo.
Propiedades de un Sistema de Representación completo
Eficiencia deductiva: La capacidad de incorporar información adicional en las estructuras de conocimiento con el fin de que los mecanismos de inferencia puedan seguir las direcciones más prometedoras.
Eficiencia en la adquisición: La capacidad de adquirir nueva información con facilidad. El caso más simple es aquél en el que una
persona inserta directamente el conocimiento en la base de datos.
Idealmente, el programa sería capaz de controlar la adquisición de conocimiento por sí mismo.
Propiedades de un Sistema de Representación completo
Conocimiento relacionalMarco – conocimiento heredableRedes semánticasConocimiento Deductivo
Algunos ejemplos
Conocimiento relacional simpleColumnas que identifican atributos de un objeto
(fila)Problemas: altamente estructurado
Se trata de un sistema de marcos o una red semántica
Es a través de atributos especiales como instancia-de, es-un, tipo-de que podemos mejorar la propagación del conocimiento
Conocimiento heredable
Lo que tenemos es una jerarquía de especialización-generalización
¿cuál es la altura de Pee Wee Reese?
Algoritmo: Herencia de propiedades Para acceder al valor V de un atributo A en
una instancia I: 1. Encontrar I en la base de conocimiento. 2. Si el atributo A tiene algún valor asignado,
devolver ese valor. 3. En caso contrario, comprobar si el atributo
instancia tiene algún valor asignado. Si no lo tiene entonces fallar.
4. En caso contrario, ir al nodo identificado por ese valor y comprobar si allí existe algún valor para el atributo A. Si lo hay, devolverlo.
5. En caso contrario, repetir hasta que el atributo es-un no tenga valor asignado o hasta encontrar una respuesta:
Obtener el valor del atributo es-un e ir a ese nodo.
Comprobar si el atributo A tiene algún valor. Si lo tiene, devolverlo.
¿cuál es la altura de Pee Wee Reese?
Conocimiento Deductivo 1. Marco era un hombre.
hombre(Marco)
2. Marco era un pompeyano.pompeyano(Marco)
3. Todos los pompeyanos eran romanos. x : romano(x) romano(x)
4. César fue un gobernante. gobernante(César)
5. Todos los romanos o eran leales a César o le odiaban.
x : romano(x) leal(x, César) odia(x, César)
6. Todo el mundo es leal a alguien. x : y : leal(x, y)
7. La gente sólo intenta asesinar a los gobernantes a los que no es leal.
x : y : persona(x) gobernante(y) intenta_asesinar(x,y)
leal(x, y)
8. Marco intentó asesinar a César.intenta_asesinar(Marco, César).
Lógica de predicados de primer ordenEl proceso de inferencia más usado se llama
resolución
Conocimiento Deductivo
Conocimiento deductivo heredable
Conocimiento Procedural
Existen formalismos que nos permiten expresarse el conocimiento a través de procedimientos
las reglas de producción
No son mejores ni peores sólo más adecuados para ciertos problemas
Conocimiento Procedural
¿a qué nivel representar nuestro dominio?
Queremos resolver el problema de los caníbales con sus nombres, o no?
Podemos representar el hecho que un caníbal es un ser humano que como seres humanos
Podemos representar el concepto de misionero… como?
Podemos representar el río… a que nivel es un cauce de agua
Problemas: la Granularidad
Juan vislumbro a María
Vislumbrar( Juan, María )Vislumbrar(x,y) ver(x,y)Ver(Juan, María, breve)Y breve?
Problemas: la Granularidad
Usar primitivas de bajo nivel nos acerca a una forma canónica ganamos en generalidad
PERO La cantidad de espacio para almacenar un hecho
simple El enorme trabajo a realizar en la transformacion
de una representación en alto nivel a su forma primitiva
No siempre es claro que primitivas vamos a utilizar Por ejemplo en el de parentesco: padre, hermano,
hijo Pero como representar primo…
Hija(hermano(madre(pedro)))Hija(hermano(padre(pedro)))
Problemas: la Granularidad
… a la circunstancia
Fui a la Oriental ayer por la noche, pedí de comer y pagué la cuenta
¿cené ayer?¿iba acompañado?¿qué comí?
Seleccionar la estructura más apropiada dependiendo de objetivo, de la tarea a resolver.
Adecuar la estructura…
Lógica de Proposiciones
Las expresiones que contienen conectivos lógicos se interpretan siguiendo el orden
de precedencia que corresponde al mostrado en la tabla anterior.
Por ejemplo: ~P ^Q v R ⇒ S equivale a:
(~(P) ^(Q v R)) ⇒ S
Además, se emplean los paréntesis para evitar
ambigüedades.
Lógica de Proposiciones
La semántica nos define las reglas que permiten determinar el valor de verdad de un enunciado respecto de algún modelo.
Con dos símbolos proposicionales existen 4 modelos posibles para cada uno de los 5 conectivos lógicos, ¿Cómo quedarían las tablas de verdad?
Lógica en Wumpus
Regresemos al mundo del Wumpus para visualizar la construcción de la base de conocimiento.
Notación: Bij indica que hay brisa en la celda (i,j).
Pij indica que hay un pozo en la celda (i,j).
A partir de un conocimiento inicial: E1: ~P11
Lógica en WumpusCuando hay brisa en una casilla implica que en
una casilla contigua hay un pozo: E2: B11 ⇔ P12 v P21
Ahora agregamos la primera percepción, no se percibe brisa en la celda (1,1): E3: ~B11
¿Cómo relacionar los enunciados 2 y 3 para obtener nuevo conocimiento?
Lógica de ProposicionesCuando los resultados de una Tabla de Verdad
son todos verdaderos, a esa proposición compuesta se le llama Tautología. Como ejemplo tenemos a: (p v ~p)
Cuando los resultados de una Tabla de Verdad son todos falsos, a esa proposición compuesta se le llama Contradicción. Como ejemplo tenemos a: (p ^ ~p)
Lógica de ProposicionesBásicamente la inferencia es la implementación
de una implicación.
Los enunciados conocidos como verdaderos forman parte del antecedente.
El consecuente es un nuevo enunciado cuya veracidad se desprende de los anteriores. Simbólicamente se representa así:
antecedente :: consecuente
Lógica de ProposicionesLa equivalencia lógica se presenta cuando dos
enunciados α y β tienen los mismos valores de verdad para el mismo conjunto de modelos.
A continuación mostramos una tabla con las equivalencias lógicas más comunes:
Doble Negación: ~( ~p ) ≡ p
Lógica de ProposicionesLeyes Conmutativas
( p v q ) ≡ ( q v p )( p ^ q ) ≡ ( q ^ p )
Leyes Asociativas( p v q ) v r ≡ p v ( q v r )
( p ^ q ) ^ r ≡ p ^ ( q ^ r )
Lógica de ProposicionesLeyes Distributivas
p v ( q ^ r ) ≡ ( p v q ) ^ ( p v r )p ^ ( q v r ) ≡ ( p ^ q ) v ( p ^ r )
Leyes de Idempotencia( p v p ) ≡ p( p ^ p ) ≡ p
Lógica de ProposicionesLeyes de DeMorgan
~( p v q ) ≡ ~p ^ ~q~( p ^ q ) ≡ ~p v ~q
Leyes de Identidad( p v ~p ) ≡ t( p ^ ~p ) ≡ f( p v f ) ≡ p( p v t ) ≡ t
Lógica de ProposicionesLeyes de Identidad
( p v f ) ≡ f( p v t ) ≡ p
Leyes de la Implicación(p ⇔ q) ≡ (p ⇒ q) ^ (q ⇒ p)
(p ⇒ q) ≡ (~q ⇒ ~p)(q ⇒ p) ≡ (~p ⇒ ~q)(p ⇒ q) ≡ (~p v q)
Lógica de ProposicionesReglas de InferenciasLa siguiente implicación lógica se llama Modus
Ponens y corresponde a la siguiente inferencia:p ^ ( p ⇒ q ) :: q
Ejemplo:p: Estudiop ⇒ q: Si estudio aprobaré Matemáticasq: Entonces, Aprobaré Matemáticas
Lógica de ProposicionesLa siguiente implicación lógica se llama Modus
Tollens y corresponde a la siguiente inferencia:( p ⇒ q ) ^ ~q :: ~p
Ejemplo:p ⇒ q: Si estudio apruebo Matemáticas~q: No aprobé Matemáticas~p: Entonces, no Estudié
Lógica de ProposicionesLa siguiente implicación lógica se llama
Silogismo Hipotético y corresponde a la siguiente inferencia:
( p ⇒ q ) ^ ( q ⇒ r ) :: ( p ⇒ r )
Ejemplo:p ⇒ q: Si estudio apruebo Matemáticasq ⇒ r: Si apruebo Matemáticas me regalan un autop ⇒ r: Entonces, Si estudio me regalan un auto
Lógica de ProposicionesLa siguiente implicación lógica se llama
Silogismo Disyuntivo y corresponde a la siguiente inferencia:
( p v q ) ^ ~p :: q
Ejemplo:p v q: Hay que estudiar Francés o Alemán~p: No estudio Francésq: Entonces, Estudio Alemán
Lógica de ProposicionesLa simplificación conjuntiva consiste en eliminar
uno de los términos de una conjunción:( p ^ q ) :: q o también: ( p ^ q ) :: p
Por el otro lado, la amplificación disyuntiva permite agregar un nuevo término:
p :: ( p v q )
Lógica en WumpusSe tiene que:E2: B11 ⇔ P12 v P21E3: ~ B11
Por lo que tenemos el siguiente razonamiento:E4: (B11 ⇒ (P12 v P21)) ^ ((P12 v P21) ⇒ B11)E5: ((P12 v P21) ⇒ B11)E6: ~B11 ⇒ ~(P12 v P21)E7: ~(P12 v P21)E8: ~P12 ^ ~P21
Lógica en WumpusDel razonamiento anterior concluimos que no
hay un pozo en la casilla (1,2) ni en la (2,1).
Ahora veamos el razonamiento cuando el agente llega a la celda (1,2).
E9: ~B12E10: B12 ⇔ P11 v P13 v P22E12: ~P22
Lógica en Wumpus
Concluimos que no hay pozo ni en la casilla (1,3) ni en la (2,2).
E11: ~P13
E12: ~P22
Pero cuando el agente visitó la celda (2,1) percibió una brisa:
E13: B21
E14: B21 ⇔ P11 v P31 v P22
Lógica en WumpusDado que ya verificamos que no hay pozo en las
celdas (1,1) y (2,2), resulta evidente la conclusión que:
E15: P31
Es conveniente que nuestra base de conocimiento esté basada solamente en conjunciones y disyunciones.
Lógica Proposicional
Cualquier enunciado compuesto puede ser transformado a uno equivalente que esté en la FNC
La Forma Normal Conjuntiva es la conjunción de n disyunciones de k elementos:
( p11 v … v p1k ) ^ … ^ ( pn1 v … v pnk )
Lógica ProposicionalA continuación se describe un procedimiento
para convertir a nuestra FNC:
Eliminar ⇔ usando la equivalencia:(p ⇔ q) ≡ (p ⇒ q) ^ (q ⇒ p)
Eliminar ⇒ usando la equivalencia:(p ⇒ q) ≡ (~p v q)
Lógica ProposicionalSimplificar ~ usando las equivalencias:
~( ~p ) ≡ p~( p v q ) ≡ ~p ^ ~q~( p ^ q ) ≡ ~p v ~q
Finalmente, aplicar la ley distributiva donde sea necesario.
p v ( q ^ r ) ≡ ( p v q ) ^ ( p v r )
Lógica ProposicionalE2: B11 ⇔ (P12 v P21)
(B11 ⇒ (P12 v P21)) ^ ((P12 v P21) ⇒ B11 )(~B11 v P12 v P21) ^ (~(P12 v P21) v B11 )(~B11 v P12 v P21) ^ ((~P12 ^ ~P21) v B11 )
(~B11 v P12 v P21) ^ (~P12 v B11) ^ (~P21 v B11)
Lógica ProposicionalPara demostrar que una implicación BC :: α es
válida, se utiliza el método de reducción al absurdo.
Esto es, probar que su negación: BC ^ ~α es una contradicción.
Para ello se lleva a la FNC y luego se prueba que es equivalente a una cláusula vacía.
Lógica ProposicionalProbar que: E2 ^ E4 :: ~P12.
(B11 ⇔ (P12 - P21)) ^ ~B11 :: ~P12
Se convierte a FNC:(~B11 v P12 v P21) ^ (~P12 v B11) ^ (¿P21 v
B11) ^ ~B11 :: ~P12
Lógica ProposicionalY para probar por reducción al absurdo, tenemos
la negación:(~B11 v P12 v P21) ^ (~P12 v B11) ^ (~P21 v
B11) ^ ~B11 ^ P12
El proceso de simplificación funciona como sigue:
Si tomamos los primeros dos paréntesis, observamos que contienen a: ~B11 y B11, respectivamente.
Lógica ProposicionalComo no pueden ser ambos verdaderos
simultáneamente, entonces, o (P12 v P21) o bien (~P12 ) son verdaderos, lo que se reduce a la siguiente expresión:
(P12 v P21 v ~P12)
Como (P12 v ~P12 ) es una tautología, la expresión anterior se reduce a: (P21)
Lógica ProposicionalSimilarmente, los dos paréntesis siguientes,
también contienen a: ~B11 y B11, por lo que laexpresión simplificada queda: (~P21)
Como ambas no pueden ser verdaderas, la conjunción resulta en una expresión nula.
GRACIAS