INTELIGENCIA ARTIFICIAL
REDES
SEMANTICAS Y
BUSQUEDAS
Ing. Jaime Polo Romero
1
Redes Semánticas
• Son esquemas de representación
en Red, compuesta por nodos
donde cada nodo representa un
dato. Se relacionan entre sí por
medio de enlaces (flechas en el
diagrama).
Ing. Jaime Polo Romero
2
• Los nodos representan objetos
del dominio del problema y los
arcos (flechas) sus relaciones o
asociacion
Ing. Jaime Polo Romero
3
• Ejemplo
Pájaro
Animal
donde la saeta significa "es un"
Ing. Jaime Polo Romero
4
•Las redes semánticas son
estructuras utilizadas para la
representación de conocimiento
en Inteligencia Artificial.
•Son especialmente útiles para
representar conocimiento de
taxonomías.
Ing. Jaime Polo Romero
5
• Los nodos corresponden a
Constantes de relaciónes tales
como clases, propiedades e
•Instancias (elementos de una
clase).
• Las aristas en la red semántica
representan asociaciones entre
clases.
Ing. Jaime Polo Romero
6
Ejemplo
Ing. Jaime Polo Romero
7
Tenemos dos objetos, Piolín y Pedro.
Intuitivamente podemos inferir que Piolín es
un ave dado que canario es una subclase
de ave y Piolín es un canario, podemos
inferir también que Piolín tiene alas.
No hay un significado preciso para una red
semántica cualquiera, este dependerá de la
aplicación y debe ser especificado por el
diseñador de la red.
Ing. Jaime Polo Romero
8
Redes Semánticas en PROLOG
Para modelar redes semánticas en PROLOG, necesitamos
codificar el grafo que la representa. En nuestro ejemplo
podemos utilizar los predicados:
instancia(Objeto,Clase)
utilizado para decir que el argumento
Objeto pertenece al argumento Clase. En
nuestro ejemplo tendremos los hechos
instancia(piolin,canario).
instancia(pedro,halcon).
Ing. Jaime Polo Romero
9
subclase(Clase1,Clase2)
para indicar que la clase Clase1 está
contenida en, o forma parte de la clase
Clase2. En nuestro ejemplo tendremos:
subclase(canario,ave).
subclase(halcon,ave).
Ing. Jaime Polo Romero
10
• tiene p(Clase1,Propiedad, Clase2)
Representa una relación entre dos clases,
indica que la clase Clase1 está
relacionada con la clase Clase2 mediante
la caracteristica Propiedad.
• En nuestro ejemplo:
• tiene_p(canario,come,semillas).
• tiene_p(ave,tiene,alas).
• tiene_p(ave,tiene,plumas).
• tiene_p(halcon,tiene,deseos).
Ing. Jaime Polo Romero
11
Como se ve en este ejemplo, un grafo
cualquiera puede ser codificado con un
pequeño programa en PROLOG en el que
los nodos, y los arcos (junto con sus
etiquetas) son modelados como conjuntos
de hechos.
Los ejemplos de árboles genealógicos que
hemos visto son una clase particular de red
semántica en donde la mayoría de los
nodos
son
instancias
que
están
relacionadas por propiedades como ser hijo
de.
Ing. Jaime Polo Romero
12
REDES Y BUSQUEDAS
BASICAS
Ing. Jaime Polo Romero
13
Estrategias de búsquedas
•No Informadas ó a Ciegas: No se tiene
información adicional acerca de los estados.
La única información es la que proporciona
la formulación del problema.
•Sólo generan sucesores y distinguen si han
llegado al objetivo ó no.
•Informadas ó Heurísticas: Se conoce
cuando un estado no es objetivo, y si es
mas “prometedor” que otro.
Ing. Jaime Polo Romero
14
Criterios para evaluar las estrategias:
Completitud
¿La estrategia garantiza encontrar una
solución, si es que esta existe?
Complejidad en tiempo
¿Cuánto tiempo se necesitara para encontrar
una solución?
Complejidad en espacio
¿Cuánta memoria se necesita para efectuar la
búsqueda?
Optimización
¿Con esta estrategia se encontrará una
Solución Óptima?
Ing. Jaime Polo Romero
15
Medición de buen éxito en la
solución del problema
costo de búsqueda = tiempo/memoria para encontrar la
solución
costo total = costo de trayectoria + costo de búsqueda
Ing. Jaime Polo Romero
16
Nodo Raíz
S
A
B
C
D
E
E
D
F
El nodo raíz denota la trayectoria
que comienza y termina en el nodo
inicial S.
El hijo del nodo raíz con etiqueta A
Representa la trayectoria S-A.
Las trayectorias como S-A, que no
alcanzan las metas se conocen
como trayectorias Parciales. Las
trayectorias que alcanzan la meta
se llaman trayectorias completas, y
el nodo correspondiente es un
nodo meta.
Nodo Hoja
Ing. Jaime Polo Romero
17
METODOS CIEGOS
Búsqueda en Profundidad
Búsqueda en Amplitud
Búsqueda no Deterministica
Ing. Jaime Polo Romero
18
Búsqueda en Profundidad
Toma los hijos de cada nodo y avanza a
partir de ese hijo.
Otras alternativas del mismo nivel se
ignoran por completo, en tanto haya
posibilidades de alcanzar la meta mediante
la selección original. Se busca en las ramas
de izquierda a derecha.
Ing. Jaime Polo Romero
19
Búsqueda en Profundidad
1
2
3
7
9
10
4
13
8
12
11
14
15
16
17
18
goal
5
6
Ing. Jaime Polo Romero
20
Búsqueda en Amplitud
Revisa todas las trayectorias de una
longitud dada antes de avanzar a una
trayectoria más larga.
Ing. Jaime Polo Romero
21
Búsqueda en Amplitud
1
2
5
11
4
3
6
7
12
8
13
9
10
14
goal
Ing. Jaime Polo Romero
22
Búsqueda no Deterministica
Se puede tener tan poca información sobre
un problema al grado de que no sea
posible descartar un factor de ramificación
grande o trayectorias largas carentes de
utilidad.
La busqueda no deterministica consiste en
buscar un termino medio entre la
búsqueda en profundidad y la búsqueda en
amplitud.
Ing. Jaime Polo Romero
23
Problema del Laberinto
En el siguiente laberinto, se puede pasar
desde una casilla a otra de las posibles
adyacentes (arriba, abajo, izquierda,
derecha), salvo si existe una barrera entre
ellas
Ing. Jaime Polo Romero
24
Objetivo: ir de I a F
Ing. Jaime Polo Romero
25
Busqueda en Profundidad
Ing. Jaime Polo Romero
26
Descargar

Inteligencia artificial