1. No category

Departamento de
Informá
Informática
Tema 1: Introducció
Introducción a los Sistemas Basados en el
Conocimiento
Departamento de
Informá
Informática
Ingeniería del Conocimiento (Primer Parcial)
• Parte I: Descripción de Sistemas Basados en Conocimiento, herramientas
de representación y posibilidades de razonamiento, modelado del
Conocimiento experto.
• Modelo computacional
• Origen
Tema 1
Introducción a los sistemas basados en el conocimiento (SBC).
• Conocimiento y Técnicas Heurísticas
Tema 2
La lógica como herramienta para la representación e inferencia
del conocimiento.
• Definición de SBC
Tema 3
Sistemas de representación del conocimiento basados en
reglas.
• Tipos de Conocimiento Experto
• Ventajas e Inconvenientes de los SSBBC
Tema 4
Introducción a las metodologías de modelado de conocimiento.
CommonKADS
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Tema 1: Introducció
Introducción a los Sistemas Basados en el
Conocimiento
• Referencias Bibliográficas:
Jorge Puente Peinador
Departamento de
Informá
Informática
Tipos de conocimiento en resolución de problemas
Humanos
– "The engineering of Knowledge-based Systems. Theory and practice".
González, Avelino J; Dankel, Douglas D. Prentice Hall International Editions. 1993.
• Conocimiento General
– Clasificar el problema en un Dominio del Problema concreto
– "Inteligencia Artificial e Ingeniería del Conocimiento".
Pajares Martinsanz, Gonzalo; Santos Peña, Matilde. Editorial Ra-Ma, 2005.
– "Desarrollo de Sistemas Basados en Conocimiento. CLIPS y FuzzyCLIPS"
Carbó Rubiera, Javier; Molina López, José M.; Martínez Tomás, Rafael. Ed. Sanz y
Torres 2005.
• Conocimiento Específico
– Resolución de problemas en dicho Dominio
• Conocimiento General sobre Resolución de Problemas
– Como aplicar los conocimientos anteriores para la resolución
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Modelo Computacional de un SBC
Componentes de un SBC
• Motor de Inferencias
PROGRAMA INTELIGENTE
MOTOR
DE
INFERENCIAS
Usuario
– Conocimiento General de Resolución de Problemas
– Como alcanzar la solución del problema
– Manipula el conocimiento representado en la Base de Conocimientos
para desarrollar una solución al problema descrito en la Base de
Hechos
Conocimiento General
Resolución de Problemas
BASE DE HECHOS
• Base de Conocimientos
– Conocimiento específico del dominio del problema
– Como se resuelven problemas en este dominio
Estado del Problema
Actual
• Base de Hechos
– Datos del problema específico
– La información inicial del problema
– La información derivada progresivamente en la resolución.
BASE DE CONOCIMIENTOS
Conocimiento Específico
del Dominio
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Potencia de los SSBBC
Esquemas de Representación del Conocimiento
• Separación entre el Conocimiento y el Uso del Conocimiento
•
– Cambia sólo la Base de Conocimientos
•
Base de Conocimientos: Específica
Ejemplo:
EPSIG – Ingeniería del Conocimiento
•
Médico de enfermedades
Jorge Puente Peinador
Lógica
Reglas
Frames
Objetos
Estudio de un esquema:
–
–
–
–
Mecánico de averías
Hechos
Relaciones entre Hechos
Algorítmica
Heurística (estrategias/trucos para mejorar la eficiencia en la resolución)
Esquemas generales de representación del conocimiento
–
–
–
–
Motor de Inferencias: Común
Sistema de
Diagnóstico
Información del Dominio y el problema:
–
–
–
–
• Permite el desarrollo de aplicaciones diferentes
SBC
Jorge Puente Peinador
Técnicas de Inferencia
Organización
Ventajas/Inconvenientes
Tipos de problemas más adecuados
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Métodos de resolución de problemas
• Métodos Algoritímicos
Métodos Algorítmicos
•
Resolución:
– Desarrollo de modelo lógico/matemático del problema
– Definición del Algoritmo de resolución
• Métodos de Búsqueda en I.A.
• Sistemas Basados en Conocimiento (I.A.)
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
•
Algoritmo:
•
Base de los sistemas de Software convencional
“Secuencia estructurada de pasos que nos garantice alcanzar una solución en un
tiempo finito”
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Métodos Algorítmicos
Meta
Salida
EPSIG – Ingeniería del Conocimiento
•
Conocemos
•
•
Departamento de
Informá
Informática
Métodos de Búsqueda en I.A.
Meta
•
Conocemos
Objetivo:
•
Objetivo:
Necesitamos:
•
Necesitamos:
–
–
–
–
Salida: Aulario
No conocemos la ciudad
Aspecto del Elogio
Encontrar un camino hasta el Elogio
a través de la ciudad desde el
campus
–
Callejero:
–
Saber como usarlo
•
modelo del sistema de rutas de la
ciudad
Jorge Puente Peinador
–
–
–
–
–
Sin Callejero
“No hablo su idioma”
Aspecto del Elogio
Encontrar un camino hasta el Elogio
a través de la ciudad desde el
campus
Método alternativo al algorítmico
Salida
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Métodos de Búsqueda en I.A.
Elementos de la búsqueda
Espacio del Problema
• ¿Qué resuelven?
– Problemas resueltos habitualmente por los “limitados” humanos
• ¿Cuándo usarlos?
– No hay Solución algorítmica
– Existe pero es excesivamente compleja
Inicial
– Conjunto de estados (infinito) por los
que puede pasar el problema
• Camino Solución
– Secuencia de pasos a seguir para
resolver el problema
• Diferencias con solución algorítmica
– Algoritmo: busca un elemento de información en una estructura de
datos
– Búqueda I.A.: busca un camino entre problema inicial y la solución en el
espacio del problema
EPSIG – Ingeniería del Conocimiento
• Espacio del Problema
Jorge Puente Peinador
• Espacio Solución
– Conjunto de estados del espacio del
problema desarrollados en la
búsqueda
Espacio
Solución
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Definición procedimental del dominio del problema
Solución
Departamento de
Informá
Informática
Definición procedimental del dominio del problema
Ejemplo:
“Vamos por la mañana a coger el coche y no funciona …”
• Dominio del problema ↔ El espacio de búsqueda
– Definición (generalmente) procedimental
– (Versión algorítmica: estructura de datos predefinida)
• Estado Inicial del problema: “el coche no funciona”
• Objetivo/Estado final: “el coche funciona al girar la llave de contacto”
• Generación por exploración:
• Problemas: Múltiples
– Inicio: Estado inicial
– Procedimientos: Definen siguientes estados posibles
– Final: definidos explícitamente sólo los caminos recorridos
• Soluciones: Múltiples
Espacio del problema
• Objetivo: Diagnosis y Corrección
– Identificar y solucionar el problema
– Identificar camino entre Est. Inicial y Est. Final
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Definición procedimental del dominio del problema
Representación:
–
Arcos: acciones a realizar por
el usuario
–
–
Departamento de
Informá
Informática
Búsqueda en un espacio de estados
• Situación:
– Objetivo: el Elogio
Nodos: [algunos] resultados
– Origen: el Aulario
“posibles” de las acciones
– Sin mapa
Los caminos: una única
avería y reparación
• Límites del espacio de búsqueda
– Rutas geográficas (infinitas)
– Límites geográficos (vías muertas)
• Norte: Mar
• Sur: La Ronda Sur
• Este / Oeste: límite del callejero
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Búsqueda en un espacio de estados
• Control de la búsqueda
Jorge Puente Peinador
Departamento de
Informá
Informática
Búsqueda en un espacio de estados
• Estrategia de búsqueda
– Operadores que definen los caminos legales a seguir
¿Qué camino tomar al llegar a una intersección?
– Leyes del tráfico
– Azar / Aleatorio
• Intersección: misma calle u otra de la intersección
• Cambio de calle al azar
• No hay direcciones prohibidas
• Problema: caminos infinitos por bucles
– Sistemática /a ciegas
• Recorremos todas y cada una de las intersecciones una sola vez
• No utiliza ningún conocimiento de la proximidad al objetivo
– Dirigida / basada en conocimiento
• Utilizamos nuestro conocimiento de “como es el Elogio”
• Suponemos que siempre está visible
• Escogemos la calle que nos lleva en su dirección
• Fundamento de la I.A.
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Métodos clásicos de búsqueda
Métodos de búsqueda a ciegas
• A ciegas
• A ciegas
– Primero en Profundidad
– Primero en Profundidad: Traza caminos hasta una solución o una vía
– Primero en Anchura
muerta (backtracking)
– Primero en Anchura: Recorrido por niveles
• Dirigida / basada en conocimiento
A
A
– Primero en Anchura y uso de conocimiento (rayo de búsqueda)
– Hill-Climbing
B
C
D
B
C
D
– Ramificación y Poda (Branch & Bound)
– Primero el mejor
E
– A*
F
G
H
I
J
K
L
M
E
F
ABEFGCHIJDKLM
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
G
H
I
J
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Métodos de búsqueda dirigida
• Primero en Anchura y uso de conocimiento (rayo de búsqueda)
– Similar a la búsqueda en anchura
• Hill-Climbing
– Similar a búsqueda en profundidad
– Como sucesor: se escoge siempre el sucesor más prometedor
– Se limita el número de sucesores a W (ancho de rayo)
• Heurístico: estimación distancia a la solución
– Selección de sucesores por un heurístico
– Bactracking al alcanzar una vía muerta
• Mejor cuanto más cerca esté de la solución
– No asegura encontrar el camino más corto
• Desde donde menos cueste alcanzarla
– Inconveniente: máximos locales
A
E
F
C
G
EPSIG – Ingeniería del Conocimiento
M
Departamento de
Informá
Informática
Métodos de búsqueda dirigida
B
L
ABCDEFGHIJKLM
Departamento de
Informá
Informática
W=2
K
f
h(B)<h(C)
D
K
Ej: max(f)
h(D)<h(C)
L
Max
?
M
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Métodos de búsqueda dirigida
Departamento de
Informá
Informática
Métodos de búsqueda dirigida
• Ramifica y Poda (Branch & Bound)
– Similar a Hill-Climbing
• Primero el mejor
– Dirección de la búsqueda: coste camino recorrido
– Similar a Hill-Climbing
– Siguiente nodo: sucesor del camino con coste mínimo
– Dirección de la búsqueda: estimación distancia a la solución (heurístico)
– Siguiente nodo: nodo por expandir más cercano a la solución
Gainesville
Jacksonville
1
2
2
Orlando
4
3
3
4
Tampa
Orlando
4
3
Ft.Pierce
Key West
3
EPSIG – Ingeniería del Conocimiento
4
2
Ft.Pierce
5
3
Miami
– No nos asegura encontrar el camino más corto
2
3
2
5
Key West
Jacksonville
1
2
3
Tampa
Gainesville
3
Miami
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Métodos de búsqueda dirigida
Jorge Puente Peinador
Departamento de
Informá
Informática
Sistemas Basados en Conocimiento
• A*
• 1960s : Desarrollo de los sistemas de búsqueda
– Combina toda la información disponible: B&B + Primero el Mejor
– Planificador de la búsqueda:
• 1970s : Inadecuados para aplicaciones de resolución de problemas
Coste estimado del viaje = Coste(inicio, nodo_actual) +
Coste estimado(nodo_actual, objetivo)
– Heurísticos admisibles
– Utilizan conocimiento general aplicable a distintos dominios
• Solución: Los Sistemas Basados en Conocimiento
• Características
– Utilizan conocimiento específico del dominio del problema
– Valores lo más cercanos a los reales
– Conocimiento del experto en el dominio
– Siempre >0 y nunca > valores reales
• Búsqueda A*
• Naturaleza relacional (causa-efecto)
• Encuentra el camino más corto
• Reglas empíricas basadas en experiencias anteriores -> Heurísticos
• Un número menor de pasos (HC, B&B, Primero el Mejor)
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Heurísticos en los SSBBC
Departamento de
Informá
Informática
Comportamiento de los Heurísticos en los SSBBC
•
•
Heurístico:
– No realiza un análisis exhaustivo
“Conocimiento informal o atajos que permiten al experto alcanzar rápidamente la
•
Comportamiento
– “Muchas veces” lleva (rápidamente) a la solución correcta
solución al problema sin necesidad de un análisis detallado”
– “A veces” nos lleva a solución incorrecta
Origen: Su experiencia
– “A veces” es incapaz de alcanzar la solución correcta
– Enfoques que permitieron resolver problemas similares
– Intentos fallidos en problemas similares
•
•
¿Porqué?
1. El número de posibilidades a examinar es excesivamente elevado
Ejemplo: Avería mecánica
2. La función algorítmica de evaluación de cada caso es excesivamente
– No hizo análisis detallado
compleja
– No sepa como funciona un motor de combustión
3. Dicha función es desconocida y nosotros presentamos una aproximación
– No empleó método de búsqueda
– SI empleó conocimiento heurístico basado en su experiencia previa
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Técnicas heurísticas vs algorítmicas
•
Heurísticas de I.A.
–
•
•
Jorge Puente Peinador
Una Definición de S.B.C.
•
Conocimiento General para dirigir la búsqueda
Definición:
“Un sistema informático que emplea conocimiento de un dominio para alcanzar una
solución a un problema de dicho dominio. Donde esta solución es esencialmente la
Algorítmicas
+ Muy detallado
misma que concluye una persona que se maneja en el domino del problema
–
Susceptible de errores
cuando se enfrenta al mismo problema”
–
Coste excesivo
•
Heurísticas de un S.B.C.
Software convencional -> Sistema Basado en Conocimiento
+ Conocimiento del experto en un dominio concreto
–
+ Un experto es capaz de identificar rápidamente la naturaleza del problema
–
Calcula: Voltajes en circuitos, análisis de stress en estructuras, riesgo de fallos en
producción, riesgo de pérdidas en préstamos
+ Precisión similar a la algorítmica
–
Pascal, Fortran, C++, Java
posibles errores de cálculo (depende del experto)
–
Análisis exhaustivo como un experto en su campo (más rápido)
–
Mismo conocimiento: fórmulas, tablas, …
Ej.: Estimación contrato de construcción de una casa por un contratista de obra
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Una Definición de S.B.C.
Factores identificativos de un SBC
•
Un SBC es mucho más que duplicar el conocimiento del experto en el dominio
•
Definición (PRECISA):
•
¿Qué diferencia un SBC del software convencional y los S.B. de I.A.?
1. La clara separación entre el conocimiento y como se utiliza.
•
–
“Un sistema experto refleja la habilidad del experto humano en la resolución de
problema en dicho dominio y emplea dichas habilidades para resolver problemas
Sistema de búsqueda con conocimiento específico en los operadores
2. El empleo de conocimiento altamente específico de un dominio
de igual forma que el experto humano”
•
GPS: General Problem Solver (1950s-1960s)
•
DENDRAL (1960s-1970): Identify Organic Compounds from Mass Spectrometer Data
•
Meta-DENDRAL (1980): Infiere reglas para DENDRAL
Definición (INICIAL):
3. El uso de conocimiento de naturaleza heurística más que algorítmica
“Un sistema informático que emplea conocimiento de un dominio para alcanzar una
solución a un problema de dicho dominio. Donde esta solución es esencialmente la
•
MYCIN (1972-80): Diagnostico y Tratamiento de enfermedades en la sangre
•
EMYCIN (1974-79): Núcleo de MYCIN para diagnostico y tratamiento de problemas
–
misma que concluye una persona que se maneja en el domino del problema
cunado se enfrenta al mismo problema”
1ª fusión de los tres factores
Medicina: CASNET, INTERNIST, PUFF, TEIRESIAS
Geología: PROSPECTOR
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Lenguaje: HEARSAY
Manufactura: XCON
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Los distintos tipos de “experto”
•
Conocimiento Asociativo
Experto
–
Definición: Capacidad o habilidad de desenvolverse en un determinado dominio con un grado
alto de destreza.
•
Tipo
–
Ámbito: cualquier area de conocimiento (ej.: cirujano, escanciador de sidra,…)
– El más fácil de representar en un SBC
–
Comparación: Sólo dentro de un mismo dominio (ej: neuro cirujano frente a medico residente
– Basado en la habilidad heurística adquirida a través de la observación
en prácticas)
•
Jorge Puente Peinador
•
– Puede no entender como funciona internamente un sistema
Conocimiento experto
–
–
El experto
– Es capaz de relacionar las entradas del sistema con sus salidas
Tipos
•
Conocimiento asociativo (caja negra)
•
Conocimiento sobre habilidades motoras
•
Conocimiento teórico (en profundidad)
– Ej: reparación de televisiones
•
En un Sistema Basado en Conocimiento
•
¿Características?
•
¿Quién lo tiene?
•
¿Cómo se consigue?
•
¿Capacidad para reflejar su conocimiento?
EPSIG – Ingeniería del Conocimiento
Representación
– Reglas IF-THEN
– Cubriendo todas las posibilidades conocidas
– Es el más utilizado en un SBC
Jorge Puente Peinador
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Conocimiento sobre habilidades motoras
•
•
Tipo
Conocimiento teórico (en profundidad)
•
– Innovación y creatividad: resolución de problemas nuevos
– Habilidad adquirida a través de su práctica de forma persistente
– Habilidad adquirida tras años de estudio teórico y ejercicio profesional
– Fácilmente olvidable
El experto
•
– Respuesta automática e instintiva ante cada caso
– Ej: jugador profesional de un deporte
•
Tipo
– Naturaleza física más que cognitiva
– Profesionales en el campo de la ciencia.
– Ej: ingenieros, físicos, matemáticos, …
Representación
•
– Sencillo de representar y razonar sobre él
Falta de precisión y velocidad en los sensores
•
Falta de capacidad de ejecución
EPSIG – Ingeniería del Conocimiento
Representación
– Muy compleja de representar
– Limitaciones de la robótica: sensoriales y motoras
•
El experto
– Técnicas específicas:
Jorge Puente Peinador
•
Mejora la solución
•
Sistema de razonamiento basado en modelos
EPSIG – Ingeniería del Conocimiento
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Ventajas e Inconvenientes de los S.B.C.
•
Ventajas de los S.B.C.
•
Ventajas
– Ampliar distribución de conocimiento experto “de acceso restringido”
– Facilidad de modificación
– Consistencia de las respuestas
•
– Servicio permanente
– Preservación del conocimiento experto
– Solución a problemas que contienen datos incompletos
– Explicación de la solución
•
Jorge Puente Peinador
•
Inconvenientes
– Las respuestas pueden no ser siempre correctas
Amplia distribución de conocimiento experto “de acceso restringido”
–
Distribución a un coste razonable.
–
Ej: Experto en impuestos (coste vs servicio)
Facilidad de modificación
–
Carácter variable del conocimiento heurístico (ej: impuestos)
–
SBC facilitan la realización de cambios
Consistencia de las respuestas
–
SBC consistente en su habilidad de resolución
–
Humanos sensibles ante cambios (salud, estados emocionales, stress)
– Conocimiento limitado al dominio de conocimiento experto
•
– Falta de sentido común
EPSIG – Ingeniería del Conocimiento
Servicio permanente
–
Jorge Puente Peinador
SBC: no enferman, no piden vacaciones (24h x 365d)
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Departamento de
Informá
Informática
Ventajas de los S.B.C. (y II)
Inconvenientes de los S.B.C.
•
•
–
•
Las respuestas pueden no ser siempre correctas
–
Preservación del conocimiento experto
Una vez desaparecido el experto humano
Utilizan información parcial
–
No tienen las soluciones a todos los problemas
Solución a problemas que contienen datos incompletos
–
•
Naturaleza heurística del conocimiento representado
Conocimiento limitado al dominio de conocimiento experto
–
•
Explicación de la solución
–
Misma línea de razonamiento que el experto humano
–
Facilita la compresión del usuario inexperto
•
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
Departamento de
Informá
Informática
Ejemplo clásico de SBC: GenAID
•
Los SBC cometen fallos como los expertos
–
GenAID: Generador de diagnósticos de Inteligencia Artificial
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador
El SBC siempre trata de encontrar una solución
–
Aunque se salga de su dominio
–
Los usuarios inexpertos pueden interpretar como cierto
Falta de sentido común
–
No identifica conocimiento de partida absurdo
–
Siempre trata de buscar una solución
–
Ej: agua en estádo líquido a -10ºC
EPSIG – Ingeniería del Conocimiento
Jorge Puente Peinador