9 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: Todos los hombres son mortales, Sócrates es un hombre, Por lo tanto, Sócrates es mortal. Representación del Conocimiento
10 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 ? x M(x,s(x))
Representación del Conocimiento
11 Lógica:
Lógica de predicados: Camión(x) x es un camión Carro(x) x es un carro Bicicleta(x) x es una bicicleta Caro(x,y) x es más caro que y Rápido(x,y) x es 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)))) Representación del Conocimiento
12 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 “Existe un hermano de Ana que le gusta a Blanca” Representación del Conocimiento
13 Lógica:
Lógica de predicados: “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” Representación del Conocimiento
14 Lógica:
Lógica Difusa: 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. Representación del Conocimiento
15 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. Representación del Conocimiento
16 Lógica:
Lógica Difusa: Representación del Conocimiento
17 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)
Representación del Conocimiento
18 Lógica:
Lógica Difusa: Fuentes de incertidumbre: 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
Representación del Conocimiento
19 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. Representación del Conocimiento
20 Lógica:
Lógica Difusa:
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. Representación del Conocimiento
21 Representación del Conocimiento Lógica:
Lógica Difusa:
Es ésta probablemente una elipse, o es ambiguamente una elipse
22 Representación del Conocimiento Lógica:
Lógica Difusa:
23 Representación del Conocimiento Lógica:
Lógica Difusa:
24 Representación del Conocimiento Lógica:
Lógica Difusa: Atributo (objeto, valor del objeto) Edad (Juan, 50)
Edad (X, [30,50])
Edad (X, Mediana)
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)
26 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 Representación del Conocimiento
27 Representación del Conocimiento
28 Representación del Conocimiento
29 Representación del Conocimiento
30 Búsqueda:
Taxonomías de los sistemas de producción / búsqueda / estrategia de control:
Hacia adelante / hacia atrás / bidireccional Irrevocable / tentativa Informada / no informada Representación del Conocimiento
31 Búsqueda:
Representación del Conocimiento Búsqueda Una ruta
Ruta optima
Juegos Profundidad primero Amplitud primero
Ascenso de colina Búsqueda en haz Primero el mejor Museo británico Ramificación y cota Programación dinámica A* Minimax Poda Alfa-beta Continuación heurística Profundidad progresiva A tientas
Heuristicos
32 Búsqueda:
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
Representación del Conocimiento (Gp:) s (Gp:) a (Gp:) d (Gp:) e (Gp:) b (Gp:) c (Gp:) f (Gp:) g (Gp:) 3 (Gp:) 3 (Gp:) 4 (Gp:) 4 (Gp:) 4 (Gp:) 4 (Gp:) 5 (Gp:) 5 (Gp:) 2
33 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.
Representación del Conocimiento
34 Búsqueda:
Representación del Conocimiento (Gp:) s (Gp:) a (Gp:) d (Gp:) a (Gp:) e (Gp:) b (Gp:) d (Gp:) c (Gp:) e (Gp:) b (Gp:) f (Gp:) b (Gp:) e (Gp:) d (Gp:) f (Gp:) b (Gp:) f (Gp:) d (Gp:) e (Gp:) a (Gp:) c (Gp:) g (Gp:) g (Gp:) c (Gp:) g (Gp:) f (Gp:) g (Gp:) Trayectoria s-d-a-b-e-f-g
35 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.
Representación del Conocimiento
36 Búsqueda:
búsqueda ciega:
Objetivos: 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.
Características: No dejar (a priori) ningún nodo sin explorar. No explorar un nodo más de una vez
Representación del Conocimiento
37 Búsqueda:
búsqueda en profundidad primero:
Para llevar a cabo una búsqueda en profundidad, Inserte en una pila el elemento raíz (nodo de partida) Hasta que el elemento tope sea el nodo meta, o se vacié la pila Si nodo tope tiene hijos, insertar el hijo siguiente aun no visitado, según ordenamiento. Si no, entonces eliminar nodo tope. Si el nodo meta se alcanza, mencione éxito, de lo contrario, notifique el fracaso. Representación del Conocimiento
38 Búsqueda: búsqueda en profundidad primero:
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.
Representación del Conocimiento
39 Búsqueda: búsqueda en profundidad primero:
Representación del Conocimiento (Gp:) s (Gp:) a (Gp:) d (Gp:) a (Gp:) e (Gp:) b (Gp:) d (Gp:) c (Gp:) e (Gp:) b (Gp:) f (Gp:) b (Gp:) e (Gp:) d (Gp:) f (Gp:) b (Gp:) f (Gp:) d (Gp:) e (Gp:) a (Gp:) c (Gp:) g (Gp:) g (Gp:) c (Gp:) g (Gp:) f (Gp:) g (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7
40 Búsqueda:
búsqueda en profundidad primero:
Ventajas: 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.
Desventajas: 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. Representación del Conocimiento
41 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. Representación del Conocimiento
42 Búsqueda:
búsqueda en amplitud primero:
Para llevar a cabo una búsqueda en amplitud, Inserte en una cola el elemento raíz (nodo de partida) Hasta que el elemento frontal sea el nodo meta, o se vacié la cola Si nodo frontal tiene hijos, insertar todos sus hijos al final de la cola. Eliminar nodo frontal. Si el nodo meta se alcanza, mencione éxito, de lo contrario, notifique el fracaso. Representación del Conocimiento
43 Búsqueda: búsqueda en amplitud primero:
Representación del Conocimiento (Gp:) s (Gp:) a (Gp:) d (Gp:) a (Gp:) e (Gp:) b (Gp:) d (Gp:) c (Gp:) e (Gp:) b (Gp:) f (Gp:) b (Gp:) e (Gp:) d (Gp:) f (Gp:) b (Gp:) f (Gp:) d (Gp:) e (Gp:) a (Gp:) c (Gp:) g (Gp:) g (Gp:) c (Gp:) g (Gp:) f (Gp:) g (Gp:) 1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 6 (Gp:) 7 (Gp:) 8 (Gp:) 9 (Gp:) 10 (Gp:) 11 (Gp:) 12 (Gp:) 13 (Gp:) 14 (Gp:) 15 (Gp:) 16 (Gp:) 17 (Gp:) 18 (Gp:) 19 (Gp:) 20 (Gp:) 21
44 Búsqueda:
búsqueda en amplitud primero:
Ventajas: 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)
Desventajas: 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. Representación del Conocimiento
45 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: Ascenso de colina (-> profundidad primero), Búsqueda en Haz (-> anchura primero), Primero el mejor
Representación del Conocimiento
46 Tarea:
Lógica de predicados: P(x) x es par Q(x) x es primo R(x,y) x + y par x, y son enteros Traducir e indicar si es verdadera o falsa:
?x ?y R(x,y) ?x ?y R(x,y) ?(?x P(x)) ?(?x Q(x))
Representación del Conocimiento
47 Tarea:
Buscar f:
En profundidad primero
En amplitud primero
Representación del Conocimiento (Gp:) s (Gp:) a (Gp:) d (Gp:) a (Gp:) e (Gp:) b (Gp:) d (Gp:) c (Gp:) e (Gp:) b (Gp:) f (Gp:) b (Gp:) e (Gp:) d (Gp:) f (Gp:) b (Gp:) f (Gp:) d (Gp:) e (Gp:) a (Gp:) c (Gp:) g (Gp:) g (Gp:) c (Gp:) g (Gp:) f (Gp:) g
| Página siguiente |