Download Representación del conocimiento

PLANTEL CHAPULTEPEC
LICENCIATURAS EJECUTIVAS - LSCA
INTRODUCCIÓN A LA INTELIGENCIA
ARTIFICIAL
Profesor: Joel Pérez González
22/AGO/2009
UVM - CHAPULTEPEC
1
Representación del
Conocimiento
 Representación del conocimiento:
•
3.1
Lógica de predicados
•
3.2
Lógica difusa
•
3.3
Redes de búsqueda
•
3.4
Redes de búsqueda óptima
•
3.5
Árboles de búsqueda con adversario
22/AGO/2009
UVM - CHAPULTEPEC
2
Representación del
Conocimiento

Lógica:
 Tipos de lógica








22/AGO/2009
De proposiciones
De predicados de primer orden y ordenes superiores
Modal
Temporal
Multivalorada
Borrosa
O-A-V o 0+
etc.
UVM - CHAPULTEPEC
3
Representación del
Conocimiento

Lógica:
 Lógica de proposiciones



Introducción y definiciones
Formalización e interpretación
Sistema axiomático


22/AGO/2009
Definición
 Teoremas útiles
Sistema inferencial

Definición

Regla de resolución

Regla de refutación
UVM - CHAPULTEPEC
4
Representación del
Conocimiento

Lógica:
 Lógica de proposiciones



22/AGO/2009
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)
UVM - CHAPULTEPEC
5
Representación del
Conocimiento

Lógica:

Lógica de proposiciones

Conectivas:

Unarias (o monádicas):


Binarias (o diádicas):




22/AGO/2009
Negación (⌝p)
Conjunción ()
Disyunción ()
Condicional (→)
Bicondicional (↔)
UVM - CHAPULTEPEC
6
Representación del
Conocimiento

Lógica:

Lógica de proposiciones

Tablas de verdad


22/AGO/2009
Ejemplo: “Si tengo hambre o sed entonces voy al bar”
(p  q) → r
UVM - CHAPULTEPEC
7
Representación del
Conocimiento

Lógica:
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 → s
p2: 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.
22/AGO/2009
UVM - CHAPULTEPEC
8
Representación del
Conocimiento

Lógica:

Lógica de proposiciones

La lógica proposicional maneja bien afirmaciones compuestas de
no, y, o, si . . . entonces.

En situaciones con un conjunto finito (pequeño) de elementos, esto
es suficiente para hablar de existe, todo, para todo.

Ejemplo: si tenemos 3 estudiantes A, B y C, tomando
22/AGO/2009



p=“A tiene ojos cafés”,
q=“B tiene ojos cafés”,
r=“C tiene ojos cafés”

la afirmación “existe un estudiante con ojos cafés” se puede representar
por p  q  r
UVM - CHAPULTEPEC
9
Representación del
Conocimiento

Lógica:

Lógica de proposiciones

En situaciones con conjuntos infinitos (muy grandes)
requríamos formulas infinitas, p.e. “cada persona es hombre o
mujer” se traduciría como:
 (p0q0) (p1  q1)  (p2  p2)  …

Que pasa si queremos representar el argumento:



22/AGO/2009
Todos los hombres son mortales,
Sócrates es un hombre,
Por lo tanto, Sócrates es mortal.
UVM - CHAPULTEPEC
10
Representación del
Conocimiento

Lógica:

Lógica de predicados:

La lógica de predicados (también llamada logica de primer orden) es
una extensión de la lógica proposicional que usa variables para los objetos.

Si usamos x para representar a algún humano, la afirmación “cada persona
es hombre o mujer” se puede representar como

x(H(x)M(x))


Donde:
H(x)= “x es hombre”,
M(x)= “x es mujer”

Estas variables se pueden combinar con símbolos de función para
representar objetos nuevos y con símbolos de predicado para describir
relaciones entre objetos.



Ejemplo: si s(x) representa “el padre de x”, y
M(x,y) representa “x es menor que y”, entonces
“toda persona es menor que su padre” se representa

por
22/AGO/2009
 x M(x,s(x))
UVM - CHAPULTEPEC
11
Representación del
Conocimiento

Lógica:

Lógica de predicados:






Camión(x)
Carro(x)
Bicicleta(x)
Caro(x,y)
Rápido(x,y)
x
x
x
x
x
es
es
es
es
es
un camión
un carro
una bicicleta
más caro que y
mas rápido que y
Traducir:



x(Bicicleta(x)  y(Carro(y)  Caro(y,x)))
xy(Camión(x)  Bicicleta(y)  Rápido(x,y) )
z (Carro(z)  xy((Camión(x)  Bicicleta(y)) 
(Rápido(z,x)  Rápido(z,y)  Caro(z,x)  Caro(z,y))))
22/AGO/2009
UVM - CHAPULTEPEC
12
Representación del
Conocimiento

Lógica:

Lógica de predicados:

Ejercicio


“no todas las aves pueden volar”
Ejercicio


Todos los hombres son mortales.

Sócrates es un hombre.

Por lo tanto Sócrates es mortal.
Ejercicio

22/AGO/2009
“Existe un hermano de Ana que le gusta a Blanca”
UVM - CHAPULTEPEC
13
Representación del
Conocimiento

Lógica:

Lógica de predicados:
22/AGO/2009

“no todas las aves pueden volar”



Todos los hombres son mortales.
Sócrates es un hombre.
Por lo tanto Sócrates es mortal.

“Existe un hermano de Ana que le gusta a Blanca”
UVM - CHAPULTEPEC
14
Representación del
Conocimiento

Lógica:

Lógica Difusa:



22/AGO/2009
La lógica difusa o borrosa (Fuzzy logic) descansa en la idea
que en un instante dado, no es posible precisar el valor de una
variable X, sino tan solo conocer el grado de pertenencia a
cada uno de los conjuntos en que se ha participado el rango de
variación de la variable.
El grado de pertenencia se cuantifica mediante la función de
pertenencia f, que normalmente se escoge de una forma
trapezoide.
Ejemplo de funciones de pertenencia:

TB: Temperatura.


TM: Temperatura media.
TA: Temperatura alta.
UVM - CHAPULTEPEC
15
Representación del
Conocimiento

Lógica:

Lógica Difusa:

La lógica de conjuntos difusos (ó borrosos) trabaja con conjunto de
datos que no tienen límites perfectamente definidos, es decir la
pertenencia ó no de una variable a un conjunto no es precisa.

Se caracteriza por funciones de pertenencia que dan flexibilidad a la
modelación, utilizando expresiones como: mucho, poco, leve, escaso,
suficiente, caliente, frío, tibio, joven, viejo.

En estos problemas, donde la información es imprecisa la matemática y
la lógica tradicional no son suficientes.

La lógica difusa es un lenguaje que permite trasladar sentencias
sofisticadas del lenguaje natural a un formalismo matemático.
22/AGO/2009
UVM - CHAPULTEPEC
16
Representación del
Conocimiento
 Lógica:
 Lógica Difusa:
22/AGO/2009
UVM - CHAPULTEPEC
17
Representación del
Conocimiento

Lógica:

Lógica Difusa:
Si fA(x) indica la función de pertenencia de x al conjunto A, entonces:
fA(x) esta entre 0 y 1
si fA(x)=1, x pertenece totalmente a A
si fA(x)=0, x no pertenece a A
A partir de esta definición es posible comprobar que se cumplen las
siguientes propiedades:
f AorB(x)=max (fA(x), fB(x))
fAandB(x)=min (fA(x), fB(x))
fnorA(x)=1-fA(x)
22/AGO/2009
UVM - CHAPULTEPEC
18
Representación del
Conocimiento
 Lógica:
 Lógica Difusa:
Fuentes de incertidumbre:









22/AGO/2009
Confiabilidad de la información
Difusificidad
Aleatoriedad
Imprecisión del leguaje de representación mediante reglas lingüísticas
Información incompleta
Información agregada
Precisión de la representación
Declaración en conflicto
Reglas de combinación evidentes
UVM - CHAPULTEPEC
19
Representación del
Conocimiento

Lógica:

Lógica Difusa:

Difusifisidad es incertidumbre determinística

Difusifisidad esta relacionada al grado con el cual los eventos
ocurren sin importar la probabilidad de su ocurrencia.

Por ejemplo, el grado de juventud de una persona es un
evento difuso sin importar que sea un elemento aleatorio.
22/AGO/2009
UVM - CHAPULTEPEC
20
Representación del
Conocimiento

Lógica:

Lógica Difusa:



22/AGO/2009
Difusifisidad
es
una
incertidumbre
determinística,
la
probabilidad es no determinística.
La incertidumbre probabilística se disipa con el incremento del
numero de ocurrencias y la difusifisidad no.
La difusifisidad describe eventos ambiguos, La probabilidad
describe los eventos que ocurren. Si un evento ocurre es
aleatorio. El grado con el cual ocurre es difuso.
UVM - CHAPULTEPEC
21
Representación del
Conocimiento

Lógica:

Lógica Difusa:
Es ésta probablemente una elipse, o es ambiguamente una elipse
22/AGO/2009
UVM - CHAPULTEPEC
22
Representación del
Conocimiento

Lógica:

Lógica Difusa:
Logica
Clasico
Difuso
Manipulacion simbolica
Manipulacion simbolica y calculos numericos
Razonamiento Exacto
Razonamiento Aproximado
22/AGO/2009
UVM - CHAPULTEPEC
23
Representación del
Conocimiento

Lógica:

Lógica Difusa:
Logica difusa
Probabilidad
Cuantos elementos?
Cardinal
22/AGO/2009
Posibilidad
Donde estan las fronteras
UVM - CHAPULTEPEC
24
Representación del
Conocimiento

Lógica:

Lógica Difusa:
Atributo (objeto, valor del objeto)

22/AGO/2009
Edad (Juan, 50)

Edad (X, [30,50])

Edad (X, Mediana)
UVM - CHAPULTEPEC
25
Representación del
Conocimiento

Lógica:

Lógica Difusa:

a and b
min (membresia (a), membresia (b))

a or b
max (membresia (a), membresia (b))

not a
1 - membresia (a)
22/AGO/2009
UVM - CHAPULTEPEC
26
Representación del
Conocimiento

Lógica:

Lógica Difusa:

Comúnmente se usa para toma de decisiones en presencia de
datos o conocimientos inciertos.

Reconocimiento de patrones ambiguos .

Como un componente de sistemas expertos difusos
22/AGO/2009
UVM - CHAPULTEPEC
27
Representación del
Conocimiento
22/AGO/2009
UVM - CHAPULTEPEC
28
Representación del
Conocimiento
22/AGO/2009
UVM - CHAPULTEPEC
29
Representación del
Conocimiento
22/AGO/2009
UVM - CHAPULTEPEC
30
Representación del
Conocimiento

Búsqueda:

Taxonomías de los sistemas de producción / búsqueda /
estrategia de control:



22/AGO/2009
Hacia adelante / hacia atrás / bidireccional
Irrevocable / tentativa
Informada / no informada
UVM - CHAPULTEPEC
31
Representación del
Conocimiento

Búsqueda:
A tientas
Profundidad primero
Amplitud primero
Heuristicos
Ascenso de colina
Búsqueda en haz
Primero el mejor
Una ruta
Ruta optima
Museo británico
Ramificación y cota
Programación dinámica
A*
Juegos
Minimax
Poda Alfa-beta
Continuación heurística
Profundidad progresiva
Búsqueda
22/AGO/2009
UVM - CHAPULTEPEC
32
Representación del
Conocimiento

Búsqueda:
4
4
a
b
c
3
4

5
5
s
3
d
2
4
e
g
f
Encontrar una trayectoria del punto S al punto G involucra dos
costos:

El costo del cálculo para encontrar la trayectoria

El costo del viaje cuando se sigue la trayectoria
22/AGO/2009
UVM - CHAPULTEPEC
33
Representación del
Conocimiento

Búsqueda:

Árbol de búsqueda: Es una representación que considera todas las
trayectorias posibles en la red:

Los nodos representan trayectorias, y las ramas conectan trayectorias a
extensiones de trayectoria de un solo paso.

La Idea es construir este árbol, siguiendo una estrategia de búsqueda.

El número total de trayectorias de un árbol con factor de ramificación b
y profundidad d es bd.
22/AGO/2009
UVM - CHAPULTEPEC
34
Representación del
Conocimiento

s
Búsqueda:
a
d
b
c
e
d
d
a
e
b
f
b
f
g
c
g
d
e
b
e
a
f
c
g
f
Trayectoria s-d-a-b-e-f-g
22/AGO/2009
UVM - CHAPULTEPEC
g
35
Representación del
Conocimiento

Búsqueda:

Búsquedas
sin
información
del
dominio
(búsqueda
ciega):realizan una búsqueda sistemática y objetiva (en el sentido
de que el control del proceso no depende del problema concreto
que se esté resolviendo).

Búsqueda heurística realizan una búsqueda informada e
intentan optimizar dicho proceso eligiendo los caminos que a priori
van a suponer un menor coste.
22/AGO/2009
UVM - CHAPULTEPEC
36
Representación del
Conocimiento

Búsqueda:

búsqueda ciega:

Objetivos:



Características:


22/AGO/2009
Encontrar el camino óptimo entre la descripción del problema o estado
inicial y el estado meta.
A veces basta con devolver el estado meta y no es necesario conocer
todo el camino.
No dejar (a priori) ningún nodo sin explorar.
No explorar un nodo más de una vez
UVM - CHAPULTEPEC
37
Representación del
Conocimiento

Búsqueda:

búsqueda en profundidad primero:

Para llevar a cabo una búsqueda en profundidad,
1.
Inserte en una pila el elemento raíz (nodo de partida)
2.
Hasta que el elemento tope sea el nodo meta, o se vacié la pila
a)
Si nodo tope tiene hijos, insertar el hijo siguiente aun no
visitado, según ordenamiento.
b)
3.
Si no, entonces eliminar nodo tope.
Si el nodo meta se alcanza, mencione éxito, de lo contrario,
notifique el fracaso.
22/AGO/2009
UVM - CHAPULTEPEC
38
Representación del
Conocimiento

Búsqueda:

búsqueda en profundidad primero:




22/AGO/2009
Es aquél procedimiento de control en el que se centra en expandir un único camino
desde la raíz.
En el caso de llegar a un callejón sin salida se retrocede hasta el nodo más cercano
desde donde se puede tomar una ruta alternativa para poder seguir avanzando.
Para llevar a cabo este tipo de búsqueda debe utilizarse una estructura de tipo pila
(LIFO) que vaya almacenando los nodos generados.
Suele establecerse el llamado límite de exploración, que marca la máxima longitud
que puede alcanzar cualquier camino desde la raíz durante el proceso de búsqueda.
UVM - CHAPULTEPEC
39
Representación del
Conocimiento

Búsqueda:

búsqueda en profundidad primero:
s
1
a
d
2
b
3
c
e
5d
4
6
f b
7
g c
d
a
e
b
f
g
d
e
b
e a
f
c
g
f
g
22/AGO/2009
UVM - CHAPULTEPEC
40
Representación del
Conocimiento

Búsqueda:

búsqueda en profundidad primero:

Ventajas:


Desventajas:


22/AGO/2009
La principal ventaja de esta algoritmo radica en el reducido valor de su
complejidad espacial. Cuando existen múltiples soluciones posibles la eficiencia
del algoritmo aumenta.
La dificultad estriba en el tiempo requerido. El algoritmo puede dedicarse a
recorrer un camino demasiado largo que no conduzca a ninguna solución. Es
más, si no se guarda constancia de los nodos que forman el camino recorrido
se podría caer en ciclos y el proceso no acabaría.
El problema por tanto es determinar cuál debe ser lp. Si éste
es inferior a la longitud real del camino de la solución, ésta
nunca se encontraría, y si es mucho mayor sería ineficiente.
Esta es la razón por la que lp debería llamarse límite de
exploración.
UVM - CHAPULTEPEC
41
Representación del
Conocimiento

Búsqueda:

búsqueda en amplitud primero:

Es aquél procedimiento de control en el que se revisan todas las trayectorias de una
determinada longitud antes de crear una trayectoria más larga.

Es decir, no se genera ningún nodo de nivel N hasta que no se hayan obtenido
todos los del nivel N-1.
22/AGO/2009
UVM - CHAPULTEPEC
42
Representación del
Conocimiento

Búsqueda:

búsqueda en amplitud primero:

Para llevar a cabo una búsqueda en amplitud,
1.
Inserte en una cola el elemento raíz (nodo de partida)
2.
Hasta que el elemento frontal sea el nodo meta, o se vacié la cola
a)
Si nodo frontal tiene hijos, insertar todos sus hijos al final de
la cola.
b)
3.
Eliminar nodo frontal.
Si el nodo meta se alcanza, mencione éxito, de lo contrario,
notifique el fracaso.
22/AGO/2009
UVM - CHAPULTEPEC
43
Representación del
Conocimiento

Búsqueda:

búsqueda en amplitud primero:
1
s
2
a
d
3
4
b
7
c
d
e
13
d
5
8
e
14 15
9
6
a
e
10
11
b
16
f b
f
g c
g
17
d
b
18 19
e a
f
20
c
f
g
22/AGO/2009
UVM - CHAPULTEPEC
44
g
12
21
Representación del
Conocimiento

Búsqueda:

búsqueda en amplitud primero:

Ventajas:



Desventajas:


22/AGO/2009
si el problema tiene una solución este procedimiento garantiza el
encontrarla.
Si hubiera varias soluciones se obtiene la de menor coste (la
óptima), es decir, la que requiere un menor número de pasos (si
consideramos un coste uniforme de aplicación de los operadores)
si el nivel de profundidad asociado a la solución es
significativamente menor que el factor de ramificación se
expandirían demasiados nodos inútilmente.
Por otro lado la principal desventaja de este método es el espacio
de almacenamiento requerido. Esto lo hace prácticamente inviable
para problemas complejos, como suelen ser los del mundo real.
UVM - CHAPULTEPEC
45
Representación del
Conocimiento

Búsqueda:

Métodos heurísticos:

La búsqueda se puede mejorar si existe una forma de ordenar
las posibilidades de modo que las más prometedoras se
exploren primero.

Mayor conocimiento, menor tiempo de búsqueda

Tres métodos muy conocidos:
22/AGO/2009

Ascenso de colina (-> profundidad primero),

Búsqueda en Haz (-> anchura primero),

Primero el mejor
UVM - CHAPULTEPEC
46
Representación del
Conocimiento
Tarea:

Lógica de predicados:





x es par
x es primo
x + y par
Traducir e indicar si es verdadera o falsa:




22/AGO/2009
P(x)
Q(x)
R(x,y)
x, y son enteros
x y R(x,y)
x y R(x,y)
⌝(x P(x))
⌝(x Q(x))
UVM - CHAPULTEPEC
47
Representación del
Conocimiento
Tarea:

s
a
Buscar f:
d
b
1.
En profundidad
primero
2.
En amplitud
primero
c
e
d
d
a
e
b
f
b
f
g
c
g
d
e
b
e
a
f
c
f
g
22/AGO/2009
UVM - CHAPULTEPEC
48
g