ing. conocimiento uc3m, 2004 tema 5- diseño e implementación vimos cómo el ic produce el modelo...

Ing. Conocimiento UC3M, 2004

Tema 5- Diseño e Implementación

Vimos cómo el IC produce el modelo de conocimiento del experto, hoy cómo se relaciona con el modelo de diseño y la implementación del SBC.

Indice del tema: Arquitectura de un SBC y subsistemas típicos. Pasos de

diseño Formalismos de representación del conocimiento Herramientas para la implementación de SBC


Modelos de KADS

Modelo de organización

Modelo de aplicaciónModelo de aplicación

Modelo de aplicación

Modelo de tarea

Modelo de concimiento experto

Modelo de cooperación

Modelo conceptual

Modelo de diseño

Modelo de agentes


El modelo de diseño.

Consiste en añadir detalles específicos de la implementación al modelo conceptual.

Entradas Modelo de conocimiento del experto Modelo de comunicación Otros modelos.

Salidas Especificación de una arquitectura del sistema. Diseño de la aplicación de acuerdo a esa arquitectura

(estructuras de datos, algoritmos, lenguajes, plataformas, etc.).


Objetivos del modelo de diseño

Separación del análisis y la implementación Garantiza la calidad: evaluar viabilidad, costes y

organización de la programación. Especificación de un sistema con transición desde los

aspectos conceptuales a los de implementación: diseño de la aplicación, la arquitectura y la plataforma.

Descomposición de tareas a realizar en implementación. Inclusión de requisitos del entorno, la interfaz y la

interacción.


Principios generales de diseño

Preservar el contenido y la estructura del modelo conceptual.

Minimizar la superposición Maximizar la cohesión Transparencia Capacidad auto-explicativa Reutilización de componentes de diseño o SW. Facilidad de mantenimiento y adaptación.


Arquitectura del sistema

Descripción del software en términos de: Descomposición en subsistemas. Elección de mecanismos de control Descomposición de los subsistemas en módulos SW.

Arquitectura propuesta para los SBC construidos con KADS.


Pasos en el diseño del SBC

Arquitectura global

Especificar plataforma

Arquitectura detallada

Diseño final


Paso 1 Especificar arquitectura global

Separar la funcionalidad del interfaz.

Controlador de entrada Vistas al exterior

Aplicación

Sensores Entradas de agentes Interfaz de usuarioSalidas de agentes


Subsistemas vista, control y aplicación

Vistas al exterior: multiples visualizaciones de datos y funciones, requiere mecanismos de verificación de la integridad de los objetos mostrados al usuario.

Controlador de entrada: gestiona las entradas, y puede tener un reloj y agenda asociados.

Aplicación: datos (conceptos y relaciones) +funciones (inferencias y tareas). Dos implementaciones: programación funcional, orientada a objetos.


Subsistema aplicación visto de forma orientada a objetos

Tareametaclases I/O

método

Método de tareametaclases interm

especif. control

Metaclasemetaclases I/O

método

Inferenciametaclases I/Ovista-dominio

Conceptometaclases I/O

método


Paso 2 Identificar plataforma HW- SW

Requisitos de usuario Elección de SW más importante que HW, excepto en

aplicaciones en tiempo real. Disponibilidad de código pre-existente para su reutilización

en el subsistema de vistas al exterior. Disponibilidad de código pre-existente para su reutilización

al representar el conocimiento del dominio. Facilidad de integración con otro software. Lenguaje fuertemente/debilmente 'tipado' Existencia de mecanismos complejos de control de

ejecución. Herramientas CASE disponibles.


Ejemplo de evaluación plataforma SW

Java vs. Prolog. Java más librerías para el interfaz que prolog. Prolog más facilidad para representar conocimiento. Tipado de java más fuerte que prolog. Protocolos de control de ejecución más complejos en Java.


Paso 3 especificar componentes de la arquitectura

Vistas al exterior: Especificar los componentes del interfaz. Diseñar mecanismos de actualización y verificación de

integridad de la información mostrada en la misma. Interfaz de usuario/interfaz de experto.

Control de entradas: Determinar condiciones de activación/terminación de

funciones de la aplicación. Gestión de funciones de transferencia. Interrupciones del usuario permitidas.


Especificar componentes del subsistema de la aplicación

Tarea: métodos para inicializar y ejecutar la tarea. Inferencia: métodos para ejecutar, new-solution, has-

solution, relación de con conceptos del dominio. Transferencia: mediante paso de mensajes a los otros dos

subsistemas. Metaclases: tipos de datos (elemento, conjunto o lista),

operaciones de acceso: asignación, add, select, substract, etc.

Conceptos: métodos de acceso y modificación de atributos.


Paso 4 concretar diseño final

Dos subpasos: Establecer correspondencia entre elementos del modelo

conceptual y componentes de la arquitectura del sistema: controlador, vistas y aplicación

Añadir detalles concretos al diseño para hacer operativa a la arquitectura.


Correspondencia del controlador

Debe preservar lo establecido por el modelo de cooperación. A menudo es necesario hacerlo 'ad-hoc' y con mucho trabajo

manual. Lo mínimo es la gestión de interrupciones. Adicionalmente:

Dar respuesta a petición de explicaciones. Permitir un cierto control del usuario sobre el proceso de

razonamiento. Posibilitar el enunciado de variantes de un escenario.


Correspondencia de las vistas al exterior

Seleccionar una o varias formas de mostrar la información.

Para el usuario final, es preciso mostrar la información con un formato lo más próximo posible al dominio.

Ajustar la representación de la información a la práctica cotidiana del dominio.


Correspondencia con la aplicación

Mínimo conjunto de actividades:

Para cada método de tarea, construir un algoritmo que ejecute fielmente la estructura de control.

Para cada concepto, escoger y construir el tipo estructurado de datos correspondiente.

Para cada inferencia, escribir un método que la invoque y modifique las estructuras de datos de forma adecuada.


Un ejemplo de diseño detallado

Implementación en prolog de frágmento de SBC de diagnóstico médico (ejemplo completo en Schreiber, 1992).

2 inferencias abstraer y especificar. 2 conceptos: datos-cuantitativos y datos-cualitativos, subtipos

de datos paciente. 2 relaciones: definición, abstracción.


Conceptos

CONCEPT datos-paciente;

ATTRIBUTES:

nombre: STRING;

END CONCEPT. CONCEPT datos-cuantitativos;

SUB-TYPE-OF datos-paciente;

ATTRIBUTES:

temperatura: NUMBER-RANGE(35-42);

presión: NUMBER-RANGE(0-300);

END CONCEPT.


Conceptos

CONCEPT datos-cualitativos;

SUB-TYPE-OF datos-paciente;

ATTRIBUTES:

fiebre: BOOLEAN;

presion-sangre:

VALUE-TYPE elevacion;

TYPE: NOMINAL;

VALUE-LIST: {normal, elevada};

END VALUE-TYPE.

hipertensión: elevacion;

END CONCEPT;


Conceptos - Prolog

concepto(nombre, super)

concepto(datos_paciente, []).

concepto(datos_cualitativos, [datos_paciente]).

concepto(datos_cuantitativos, [datos_paciente]). atributos(concepto, nombre, valores)

atributos(datos_cuantitativos, temperatura, numberrange(35.0,42.0)).

atributos(datos_cualitativos, hipertension, [normal, elevada]).

...


Relaciones

RELATION abstraccion;

ARGUMENTS: datos-cuantitativos. Datos-cualitativos.

AXIOMS: fiebre:= temperatura>38.0;

END RELATION. CONCEPT datos-cualitativos ...

AXIOMS: hipertension:= presion-sangre;


Relaciones - Prolog

relacion(nombre, arg1, arg2)

relacion(abstraccion, datos-cuantitativos, datos-cualitativos) axioma(concepto/relacion, expresion)

axioma(abstraccion, fiebre= (temperatura>38)).

axioma(datos-cualitativos, hipertension= presion-sangre)).


Inferencias

INFERENCE especificar

ROLES:

INPUT: evidencia-abstracta

OUTPUT:hipotesis

DOMAIN-VIEW: abstraccion INFERENCE abstraer

ROLES:

INPUT: evidencia

OUTPUT: evidencia-abstracta

DOMAIN-VIEW: definicion


Inferencias - Prolog

inferencia (nombre, descripcion)

inferencia (abstraer, 'hacer una generalización de los datos').

inferencia (especificar, 'concretar una propiedad'). metaclase (inferencia, tipo I/O, nombre, descripcion)

metaclase(abstraer, entrada, evidencia, 'sintoma observado'). vista-dominio (inferencia, concepto/relacion)

vista-dominio(especificar, definicion). papel (concepto/relacion, metaclase)

papel(evidencia, datos-cuantitativos).


Tareas

TASK diagnosticar;

ROLES:

INPUT: evidencia;

OUTPUT: hipotesis;

INTERMEDIATE: evidencia-abstracta;

CONTROL-STRUCTURE:

abstraer(evidencia->evidencia-abstracta);

especificar(evidencia-abstracta->hipotesis);

END TASK.


Tareas - Prolog

nombre_tarea(Var_Entrada, Var_Salida) :-

inferencias, condiciones. Ejemplo:

diagnosticar (Evidencia, Hipotesis) :-

inferencia_call(abstraer, Evidencia, Evidencia-abstracta), inferencia_call (especificar, Evidencia-abstracta, Hipotesis).

inferencia_call (Nombre, Mentrada, Msalida) :-

inferencia(Nombre, _X), metaclase(Mentrada, entrada, Nombre), metaclase(Msalida, salida, Nombre), papel(Concepto,Mentrada), concepto(Concepto ...


Tema 5- Diseño e Implementación

Indice del tema: Arquitectura de un SBC y subsistemas típicos. Pasos de

diseño Formalismos de representación del conocimiento Herramientas para la implementación de SBC


Sistemas de producción

Una regla no es más que la transcripción del conocimiento de una persona a un formato lógico.

Cadena de Inferencia: reglas que están interconectadas pues las conclusiones de unas son premisas para otras.

Intérprete : idenfica reglas aplicables y selecciona el orden en el que serán ejecutadas. Dos tipos:

Forward chaining o dirigido por los datos. Backward chaining o dirigido por el resultado.


Lógica proposicional

La lógica proposicional se basa en determinar la verdad o falsedad de una proposición a partir de otras proposiciones.

Un hecho es una sentencia del modo:

proposición : los pájaros vuelan La falsedad o verdad de una proposición vendrá dada por uno

de los dos posibles valores: Cierto o Falso. Sobre los hechos se pueden aplicar distintos operadores:

Conjunción (AND), Disyunción (OR), Negación (NOT), Igualdad, (=), Implicación (=>).


Inferencia en la lógica proposicional

Modus Ponens:

p es T y p=>q es T podemos inferir : q es T Modus Tollens

q es F y p=>q es T podemos inferir : p es F Modus Ponendo Tollens

q es F y p OR q es T podemos inferir : p es T Modus Tollendo Ponens

q es T y p AND q es T podemos inferir : p es T


Lógica de predicados de 1er orden

Permite razonar sobre las relaciones entre entidades, sirve para razonar sobre partes del universo del discurso.

La sintaxis está formada por constantes, variables, predicados, funciones, operadores lógicos y cuantificadores.

La inferencia permite, además de los mecanismos de la lógica proposicional, utilizar la especialización o instanciación.

Otras lógicas son: Lógica modal que incluye estructuras del tipo “es

necesario” “es posible” Lógicas temporales con proposiciones del tipo “siempre”

“a veces”


Programación lógica con restricciones

Un conjunto de atributos con un dominio de valores posibles finito.

Un conjunto de restricciones que condicionan los valores que pueden tomar los atributos anteriores.

Filtrado de hipótesis que asignan combinaciones de valores a los atributos anteriores.

Razonamiento temporal: puntual, intervalos, restricciones temporales.


Marcos o 'Frames'

Humanos agrupamos conocimiento en marcos conceptuales (Minsky, 1975). Tratar nuevas situaciones a partir del parecido con situaciones anteriores.

Marco o Frame con atributos valorados en un rango, con posible valor por defecto.

El valor de un atributo puede calcularse mediante procedimientos asociados (demonios) que se ejecutan cuando:

Se necesita. Se añade un determinado valor. Se cambia un determinado valor.

Jerarquía de marcos permite representar especialización y generalización.

Equiparación de marco pregunta con el que más encaje.


Redes semánticas

(Quillian,1968) para representar el conocimiento en frases. Representan desde la semántica hasta relaciones causales. Grafo dirigido etiquetado. Etiquetas de nodos son nombres

(conceptos), de los arcos son verbos (relaciones). Inferencia mediante herencia y equiparación de patrones. Ventajas : Explícitas y sucintas. Reducen el tiempo de

búsqueda. Desventajas : No hay interpretaciones estándar. Se producen

inferencias inválidas. Explosión combinatoria.


Incertidumbre

Sistemas de producción utilizan afirmaciones (hechos) sobro el mundo modelizado en la base de conocimientos.

¿Cómo tratar con conceptos que van más allá de las etiquetas “verdadero” y “falso”?

Los expertos aplican reglas de inferencia basadas en sus impresiones de las que no son capaces de afirmar la veracidad o falsedad.

¿De donde surge la incertidumbre? Datos Incompletos Datos ambiguos Representación imprecisa de los datos


Razonamiento con incertidumbre

El objetivo es introducir esa incertidumbre en los SBC: cómo se representa, cómo se calcula y cómo se propaga por las reglas (desde las premisas a las conclusiones).

Métodos de representación de la incertidumbre: Teorema de bayes: probabilidades Factores de certidumbre Teoría de Demster-Shafer Conjuntos borrosos y lógica difusa


Repaso de Probabilidad

La probabilidad está entre 0 y 1. 1 es el espacio total. La probabilidad de la unión de dos conjuntos disjuntos es la

suma de las probabilidades. La probabilidad condicional se define por: p(A X) =

p(A/X) * p(X) = p(X/A) * p(A) El teorema de Bayes consiste en: p(A/ X) = p(X/A) *

p(A) / p(X) La probabilidad total se define por: p(X) = p(Xx1) +

p(Xx2) + .. = p(X/x1) * p(x1) + p(X/x2) * p(x2) + ... Luego Bayes queda: p(A/ X) = p(x1/A) * p(x1) / p(X/x1)

* p(x1) + p(X/x2) * p(x2) + ...


Reglas probabilísticas

• IF Hipotesis H es Verdad THEN Evidencia E puede

concluirse con probabilidad p.

• Se puede escribir: H => E(p) donde p(E/H) = p

• Y con el teorema de Bayes se puede aplicar un razonamiento

abductivo t.q. P(H/E) = P(E/H) * p(H) / p(E)


Ejemplo de aplicación de Bayes

• Dados: p(resfriado) = 0.2; p(estornudo/no resfriado) = 0.75;

p(estornudo/resfriado) = 0.2.

• Podemos calcular:

• p(estornudo) = 0.75 * 0.2 + 0.2 * 0.8 = 0.31

• p(resfriado/haya estornudado) = 0.75 * 0.2 / 0.31 = 0.48387

• p(resfriado/no haya estornudado)=(1-0.75)*0.2/(1-0.31)=0.07246


Bayes con múltiples hipótesis y evidencias

Dadas m hipótesis y n evidencias independientes, tenemos:

P(Hi/E1 E2 ....En) = P(E1 E2 ....En/Hi) * p(Hi) / P(E1 E2 ....En) =

P(E1 /Hi) * P(E2 /Hi) * ... * P(En/Hi) * p(Hi)___________________________________ P(E1 /Hk) * P(E2 /Hk) * ... * P(En/Hk) * p(Hk)


Ejemplo de aplicación de Bayes con múltiples hipótesis y evidencias

Evidencias: estornudar (E1) y fiebre (E2) Hipótesis: resfriado (H1), alergia (H2) y sensibilidad a la luz

(H3). Dados a priori:

p(H1) = 0.6, p(H2) = 0.3, p(H3) = 0.1

p(E1/H1) = 0.3, p(E1/H2) = 0.8, p(E1/H3) = 0.3

p(E2/H1) = 0.6, p(E2/H2) = 0.9, p(E2/H3) = 0.0

Podremos calcular P(H1/E1E2), P(H2/E1E2) y P(H3/E1E2)


Aplicación en Prospector

SBC pionero en aplicar probabilidad a un sistema de producción (Duda, Hart y Nilsson, 1978).

El conocimiento se representa como una red de inferencias. Tipos de nodos: hechos (evidencias e), o deducibles

(hipótesis h). A partir de las probabilidades a priori de ambos tipos y de

las relaciones causales entre los nodos, determina: Grado de suficiencia de e para que se dé h Grado de necesidad de e para que se dé h

Con estos datos Prospector era capaz de propagar la probabilidad en la ejecución de sus reglas.


Redes bayesianas

(Pearl, 1986) Representación mediante nodos (atributos y valores) y arcos (relaciones de causa-efecto)

Permiten: tanto razonar con la certeza de causa como con la certeza de efecto. Representadas con una matriz.

Motor de inferencias no modus ponens, en su lugar propagaremos certeza sobre causas y efectos en una red utilizando teorema de bayes.

Posibles estructuras de la red: Cadena: una causa, un efecto. Arbol: una causa, varios efectos Red simplemente conexa: varias causas, varios efectos pero

sin bucles.


Redes bayesianas

Creencia en hecho x dada una cadena de aconticimientos e. La evidencia e se descompone e+ (causas) y e- (efectos)=>

p(x / e+ , e- ) = p(e- / x, e+ ) * p(x / e+ ) / p(e- / e+ )

Consumo de drogas

Estado de ánimo

asesino huellas

NuloEsporádicoHabitual

ApacibleIrritadoFurioso

SiNo

SeguroPosibleDifícil

Apacible Irritado FuriosoNulo 0.7 0.2 0.1Esporádico 0.5 0.3 0.2Habitual 0.3 0.4 0.3

Si NoApacible 0.4 0.6Irritado 0.6 0.4Furioso 0.8 0.2

Seguro Posible DifícilSi 0.7 0.2 0.1No 0.1 0.2 0.7


Limitaciones del razonamiento probabilístico

• Necesidad de demasiados datos para conseguir una base de

conocimiento probabilístico.

• ¿En qué se basan las probabilidades a priori?.

• Reducción de la relación entre conceptos a un conjunto de

números.

• Está reducción hace imposible de seguir el razonamiento.


Factores de certidumbre

(Mycin, 1979). FC: grado de creencia en las hipótesis dadas las evidencias:

IF EVIDENCIA THEN HIPÓTESIS (FC) Creencia positiva (0,1) grado en el que la creencia en la

hipótesis es soportada por la evidencia: CP= ( p(h/e) -p(h) ) / (1 - p(h) ) .

Creencia negativa (0,1) grado en el que la no-creencia en la hipótesis es soportada por la evidencia CN= (p(h) - p(h/e) ) / p(h).

Factor de Certidumbre (-1, 1 )

FC= (CP-CN) / (1- min(CP,CN))



Las evidencias son verdaderas o falsas en un cierto grado. Las evidencias disparan ‘n’ reglas con un cierto grado. El FC de una hipótesis es la acumulación de la evidencia de

varias reglas. Grado de hipótesis viene de los grados de las evidencias, de

los FC y de la acumulación de la evidencia de varias reglas. Cómo se propagan:

FC de premisa = min(FC de las premisas ) para el AND FC de premisa = max(FC de las premisas ) para el OR FC de conclusión = FC de la premisa * FC de la regla



Como se acumulan los FC: FC revisado ( FCr ) es función de FC antiguo ( FCa ) y el FC

nuevo ( FCn ):

Si FCa y FCn son > 0 entonces FCr = FCa + FCn * (1-FCa)

Si los dos son negativos entonces FCn = -FCr( -FCn, -FCa )

Si uno es negativo FCn = (FCa + FCn ) / (1 - min(|FCa|, |FCn| ) )


Ejemplo de factores de certidumbre

• Robo del coche de Tim.R1: IF el acusado tiene un motivo AND el acusado tiene oportunidad

THEN el acusado es culpable del crimen (FC = 0.6)R2: IF el acusado tiene coartada

THEN el acusado es culpable (FC = -0.8)R3: IF las huellas dactilares del acusado están en el coche

THEN el acusado es culpable (FC = 0.4)R4: IF las llaves están en el coche

THEN el acusado tiene oportunidad (FC = 0.9)R5: IF al acusado no le gusta Tim

THEN el acusado tiene un motivo (FC = 0.5)R6: IF el acusado necesita transporte

THEN el acusado tiene motivo (FC = 0.9)R7: IF las huellas dactilares del acusado están en las llaves del coche

THEN el acusado es culpable (FC = 0.7)



E1: Mike necesita transporte (FC = 1.0) E2: John no necesita transporte (FC = 1.0)

E3: Las huellas digitales de Mike están en el coche (FC = 1.0)

E4: Las huellas digitales de John no están en el coche (FC = 1.0)

E5: Las huellas digitales de Mike no están en las llaves del coche (FC = 1.0)

E6: Las huellas digitales de John están en las llaves del coche (FC = 1.0)

E7: Las llaves de Tim estaban en el coche (FC = 1.0)

E8: A Mike no le gusta Tim (FC = 0.6) E9: A John le gusta Tim (FC = 0.8)

E10: Mike tiene una coartada (FC = 0.85) E11: John no tiene una coartada (FC = 0.2)


Ejemplo de factores de certidumbreEl acusado necesita transporte

Al acusado no le gusta Tim

Las llaves están en el coche

R6 R5 R4

El acusado tiene motivo

0.50.9

El acusado tiene oportunidad

0.9

R1

El acusado tiene coartada

R2

El acusado es culpable

R3

Las huellas del acusado están en las llaves del coche

R7

Las huellas del acusado están en el coche

-0.80 0.6 0.4 0.7



• Hipótesis H1: Mike robó el coche de Tim (FC=0).

• Subhipótesis H11: Mike tiene un motivo (FC=0).

• Con la regla R6 (FC=0.9) sobre E1 (Necesidad de transporte,

FC=1):

FCn(H11) = 0.9 * 1.0 = 0.9

FCr(H11) = 0 + 0.9 * (1 - 0) = 0.9

• Con la regla R5 (FC= 0.5) sobre E8 (No le gusta Tim, FC=0.6)

FCn(H11) = 0.5 * 0.6 = 0.3

FCr(H11) = 0.9 + 0.3 * (1 - 0.9) = 0.93



• Subhipótesis H12: Mike tiene la oportunidad (FC=0)

• Con la regla R4 (FC= 0.9) sobre E7 (Llaves en el coche, FC=1):

FCn(H12) = 0.9 * 1.0 = 0.9

FCr(H12) = 0 + 0.9 * ( 1 - 0) = 0.9

• Con la regla R1 (FC=0.6) sobre las subhipótesis H11 (FC=0.93 )

y H12 (FC=0.9), tenemos:

FC(H1)= min (0.9, 0.93)*0.6= 0.54

FCr(H1)= 0 + 0.54 * (1-0) = 0.54



Con la regla R2 (FC= -0.8) sobre la evidencia E10 (FC=0.85), tenemos:

FCn(H1) = 0.85 * (-0.8) = -0.68

FCr(H1) = (0.54 – 0.68) / (1- 0.54) = -0.3 Con la regla R3 (FC= 0.4) sobre la evidencia E3 (FC= 1) tenemos:

FCn(H1) = 1 * 0.4 = 0.4

FCr(H1) = (0.4 –0.3) / (1- 0.3) = 0.14 Con la regla R7 (FC= 0.7) sobre la evidencia E5 (FC=1) tenemos:

FCn(H1)= 1 * 0.7 = 0.7

FCr(H1) = 0.14 + 0.7 * (1 – 0.14) = 0.74 Se deja planteado como ejercicio calcular el FC de la hipótesis H2 de

que John robó el coche de Tim.


Teoría de Dempster-Shafer

• Se parte de un conjunto de posibles conclusiones : = {1,

2, ...., n} Mutuamente exclusivo y exhaustivo.

• Masa m, valor entre 0 y 1, probabilidad de que ocurra una de

todas las posibles combinaciones de posibles soluciones.

• Creencia en A ={1, 2}: Bel(A) = m(1) + m(2) + m(1, 2 )

• Plausabilidad de A ={1, 2}: P*(A) = 1- Bel(Ac)

• Certidumbre definida por el intervalo : [Bel(A), P*(A)]


Limitaciones de Dempster-Shafer

Representa certidumbre sobre la certidumbre La creencia en A y Ac no agota todas las posibilidades,

puede existir un grado de ignorancia. Es un procedimiento complejo Necesita de la enumeración de todos los casos posibles No se define el origen de la masa de probabilidad.


Lógica borrosa o difusa: Zadeh

Justificación: Vaguedad: dificultad para establecer los límites precisos

de la definición de un término. Por ejemplo ‘joven’ Ambigüedad: en las relaciones que se establecen de un

término a varios, elección entre varias alternativas. Propuesta de Zadeh (1964) para operar con términos vagos:

El concepto borroso o difuso (p.e. ‘alto’) se representa mediante una función de pertenencia de un objeto (p.e. ‘juan’) a dicho concepto. Esta función establece el grado de compatibilidad de la afirmación de que ‘juan es alto’ con valores distintos de 0 y 1.


Lógica borrosa o difusa: Sugeno

Propuesta de Sugeno (1977) para aplicar el concepto ‘difuso’ en el contexto de la ambigüedad:

Dado un objeto x del universo X, dividido en conjuntos no borrosos A,

cada uno de estos conjuntos tiene asignado una función gx(A) entre 0 y 1, que representa el grado de ‘borrosidad’ de la afirmación ‘x pertenece a A’.

Este grado puede ser interpretado como una probabilidad, creencia o posibilidad.


Lógica borrosa o difusa: Unificación

Unificación de Zadeh (1978): Distribución de posibilidad inducica por un conjunto borroso.

La distribución de posibilidad sobre el universo X, asocia a cada elemento x la posibilidad de que sea un valor de la variable v definida sobre x: (v=x) = (x) = A(x)

Así la expresión de la distribución de posibilidad es equivalente a un conjunto borroso, por lo que se pueden aplicar los conceptos de la lógica borrosa sobre las distribuciones de posibilidad.


Un conjunto borroso o difuso

Distancia

Normal

6 8

1.0

CONJUNTO

TRADICIONAL

Distancia

Normal

6 9

1.0

CONJUNTO

DIFUSO


Compatibilidad de un valor con un conjunto borroso

dato numérico

dato numérico

1

x


Compatibilidad de un conjunto borroso con otro

x

A(x)

1.0 A*(x)0.6


Operaciones con conjuntos borrosos

Sean los conceptos borrosos A y B definidos por A y B:

• “NOT A” se representa mediante : 1 - A(x)

• Luckasiewicz A=>B(x,y)= min{1, 1 - A(x) + B(y)}

• Mamdani A=>B(x,y)= min{ A(x), B(y) }

A AND B A OR BMin-Max Min{A(x), B(x)} Max{A(x), B(x)}Prod-Prod*

A(x) B(x) A(x) + B(x) - A(x) B(x)

W-W* Max{0, A(x) + B(x) - 1} Min{1, A(x) + B(x) }


Inferencia borrosa o difusa

Inferencia clásica Modus Ponens: A AND (A => B). Así cuando ‘x es A’ es verdad y ‘A=>B’ también,

entonces B es verdad. Y al contrario, cuando ‘x es A*’ es verdad, entonces B

resulta ser falso. Utilizando las fórmulas de MAX-MIN y Mamdani,

obtendremos finalmente:

B*(y) = Sup{ Min{ Min{A*(x), A(x)}, B(y) } }


Inferencia borrosa gráficamente

A

B

A’

B’


Sistema borroso

Reglas

Entradasnuméricas

Fuzzyfication SalidasBorrosas

Defuzzification Salidasnuméricas

VL L M H VH

VL L M H VH

1

Variable lingüística de entrada

Etiquetas

EntradasBorrosas

Variable lingüística de salida

Etiquetas


Defuzzificación

Centro de gravedad Singletons Centroides

VL L M H VH


Ejemplo de lógica borrosa

SI (distancia_1 es LEJOS OR distancia_2 es MUY LEJOS) ENTONCES Velocidad_1 es NORMAL

• Los antecedentes tienen un grado de pertenencia de 0.6 y 0.4• La conclusión tiene un grado de activación, :

distancia_1 es LEJOS OR distancia_2 es MUY LEJOSmax{0.6,0.4}= 0.6Por tanto el grado de activación de (Velocidad_1 es NORMAL) es: = 0.6SI (distancia_2 es MUY LEJOS) ENTONCES

Velocidad_1 es ALTO• La conclusión tiene un grado de activación, = 0.6



1.0

0.6

0.4

0 10 20 30 40 50 60 70 80 90 100

NORMAL ALTO

EVIDENCIAPROPAGADA



NORMAL: Centro: 40 Pertenencia: 0.6

Área: [ 0.6 * (40+28) ] / 2 = 20.4

ALTO:

Centro: 70 Pertenencia: 0.4

Área: [ 0.4 * (40+32) ] / 2 = 14.4

Centroide:

20.4 * (40) + 14.4 * (70)

------------------------------ = 52.41

20.4 +14.4


Limitaciones de la lógica borrosa

• Se permite la representación de conceptos definidos con límites precisos así como definidos con límites imprecisos

• Se permiten calificadores del modo mucho, poco, varios,... que se representan mediante modificaciones de la función de pertenencia del conjunto básico. Por ejemplo de cerca ( (x)) el concepto muy cercano es el cuadrado ((x)2) del conjunto cerca.

• En los sistemas lógicos bi-valuados una proposición está asociada con un valor de verdad, en lógica borrosa está asociada con: una verdad borrosa, resultado de aplicar la tabla de verdad de la implicación lógica que se escoja.


Sistemas de mantenimiento de la verdad

Razonamiento no monótono: existencia de excepciones, redefinición de proposiciones, procedimientos para restar evidencia a premisas, etc.

Los sistemas de mantenimiento de la verdad procuran evitar trabajos inútiles de comprobación de que se verifican unas condiciones. Se ocupan de mantener de forma consistente las creencias relevantes en función de las modificaciones e identifica contradicciones.


Mecanismos de Control

Los mecanismos de control ayudan a manejar los conocimientos del dominio: aplicar estrategias, resolver excepciones.

Muchas veces no es suficiente con la base de conocimiento y el motor de inferencias.

Estos mecanismos pueden ser: De bajo nivel: La creación y resolución del conjunto

conflicto. De alto nivel: decisiones estratégicas (cambio de objetivo

o de subproblema).


Control de bajo nivel

Para la resolución del conjunto conflicto: Especificidad, novedad, refracción, prioridades.

Para la creación del conjunto conflicto: Algoritmos de búsqueda: en amplitud, en profundidad,

escalada, etc.


Búsqueda en profundidad

Generate - and – Test: prueba y error Hill Climbing (Escalada)

1. Se genera la primera solución propuesta como antes. Si lo es acaba sino continuamos.

2. Aplicamos al nodo un conjunto de reglas posibles y tenemos un conjunto de soluciones propuestas.

3. Para cada elemento de ese conjunto:

a) Aplicamos la función de escalada, si es solución fin,

b) si no, ver si es mejor que los anteriores

4. Tomar el mejor y utilizarlo como solución propuesta.

5. Volver a 1


Búsqueda en amplitud

Consiste en examinar todos los nodos de un mismo nivel del árbol de búsqueda de solución, antes que cualquiera de los nodos del siguiente nivel. Este método garantiza encontrar la solución si esta existe, pero: Requiere gran cantidad de memoria, gran cantidad de trabajo y además operadores irrelevantes pueden aumentar el número de nodos a explorar.

Búsqueda en amplitud + profundidad : Best - FirstEn cada paso se selecciona el nodo más prometedor de todos

los generados, aplicando una función heurística. Este nodo se expande, y todos lo nuevos nodos se agrupan con los anteriormente generados, escogiendo entre todos el más prometedor.


Control de alto nivel

Cuando el problema es complejo puede no ser suficiente. La complejidad se debe a:

La cantidad de conocimiento implicado. La necesidad de combinar el uso de conocimiento

representado mediante distintos formalismos. Dificultad de representar y manejar el estado de un

problema. Tratan de:

Cambiar de estado parcialmente Centrarse en una parte del estado Divide y vencerás


Control de alto nivel: metarreglas

Con los formalismos de representación habituales, por ejemplo: reglas de producción.

En este caso podemos distinguir el control implícito del explícito. Cuando las reglas y el conocimiento de control está claramente diferenciado en un módulo de control metarreglas.

Normalmente se ocupan de: Parar/activar ejecución Añadir/reordenar/eliminar reglas o metas Modificar criterios resolución conjunto conflicto


Arquitecturas de control de alto nivel

Se utilizan arquitecturas específicas para resolver los problemas de control en SBC complejos.

Sirven para coordinar el conocimiento de diversas fuentes para resolver el problema.

Veremos tres arquitecturas: agendas, pizarras y sistemas de agentes.


Agendas

La idea general es la utilización por parte del sistema de una estructura global en la que se anotan las acciones a realizar y en la que se registran todos los cambios que se van produciendo.

Por lo tanto una agenda es una lista de tareas que puede realizar el sistema. Asociado a cada acción tenemos: una lista de razones y una medida de la utilidad de la acción.

Un problema muy importante es el dimensionamiento de la tarea ni muy grandes, ni muy pequeñas.

La comunicación entre los distintos módulos se realiza a través de la agenda, los módulos comparten información sobre las tareas a realizar, pero no saben nada de los otros módulos.


Pizarra

Es una abstracción de un grupo de expertos colaborando para resolver un problema.

Cada uno de los cuales posee conocimiento que puede ser relevante en algún momento del proceso de solución.

Todos ven en la pizarra la última solución parcial. Cualquiera puede escribir una contribución parcial a la solución. La solución final va surgiendo al combinarse todas las contribuciones de los expertos.

Se necesita un método para evaluar la contribución de cada experto y determinar a quién se le permite escribir.

La información debe escribirse de modo que todos los expertos la comprendan.


Componentes de la pizarra

La pizarra puede dividirse en diferentes niveles de abstracción organizados de forma jerárquica.

Las fuentes de conocimiento: examinan la pizarra para generar conclusiones y modificar

el foco de atención del problema. Cada una se dispara cuando puede contribuir a la solución,

al cumplir condiciones separadas en dos campos: Están aisladas unas de otras, excepto por la pizarra.

En general el proceso de control funciona porque las fuentes: modifican el contenido de la pizarra. indican la contribución que puede hacer a la solución.


Ejemplos de pizarra

Alumnoo Alumnoo Alumnoo Alumnoo

Profesoro

Pizarrao


Ejemplo de pizarra

Corredoro Corredoro Corredoro Corredoro

Operadoro

Pizarrao


Pizarras

Ventajas: Los expertos actúan en orden determinado por el progreso de

la solución. Es fácil añadir nuevos expertos. Diferentes aspectos del problema se pueden considerar

simultáneamente por diferentes grupos de expertos usando diferentes áreas de la pizarra (p.e. puzzle).

Como todas las interacciones entre los expertos se producen a través de la pizarra el control del proceso de solución se puede ejercer determinando el orden de acceso de los expertos.


Arquitecturas multiagentes

Mediante fuentes de conocimiento dotadas de autonomía (agentes).

Redes: Resolución distribuida de problemas

Proceso autónomo: Agente Software

Con objetivo común: MAS

A semejanza humana: Agente Inteligente

¿qué agentes?


Objetivos y necesidades

Persiguen mejorar la eficacia global de las fuentes de conocimiento.

Necesitan un sistema de mantenimiento de la verdad distribuido para garantizar la consistencia:

Elemento central: coordinador, ontología. Asignación de roles Descripción de secuencia y dependencia de la división

del problema en partes Sincronización


Tipos de Sistemas de agentes

Coordinación centralizada (comunicación intermediada): Fuertemente: agente planificador Débilmente: agente negociador

Coordinación distribuida (comunicación directa): con objetivos en común: cooperación Sin objetivos en común: competición


Un agente por dentro

Dos tipos de arquitecturas internas de un agente:

- Por sus frutos los conoceréis: reactivas

- Las obras sin fe están muertas: deliberativas


Herramientas para construir agentes

JAM: docencia de agentes Aglets de IBM JATlite Univ. de Stanford. JAFMAS, Univ. de Cincinnati JADE: Comunicación JADEX: Deliberativos.


Historia

Hoy día utilizamos motores de inferencia ya programados. Antes se programaban tb al construir el SBC Pionero fue EMYCIN: con encadenamiento hacia atrás,

factores de certeza y facilidades de explicación. Otro fue R1/Xcon del que surgió OPS5.


Lenguajes

Lenguajes: Common-Lisp: ANSI, UFA-Soft, Allegro, etc., Prolog: www.swi-prolog.org, CLIPS y FuzzyCLIPS: www.ghg.net/clips

ai.iit.nrc.ca/IR_public/ fuzzy/fuzzyClips JESS: herzberg.ca.sandia.gov/jess


Entornos

Entornos integrados con facilidades e interfaz. Algunas muy orientadas a la adquisición: OPAL, SALT Características:

Versatilidad de representación. Depuración Eficiencia Ayuda para incorporar capacidad explicativa Integración con otros lenguajes/aplicaciones.


FOCL

FOCL escrito en Common Lisp. Incluye facilidad para apredizaje automático desde ejemplos, un interfaz gráfico para modificar/escribir reglas y hechos, y un intérprete con encadenamiento hacia atrás.

Disponible mediante ftp anónimo en: ics.uci.edu:/pub/machine-learning-programs/


RT-Experts

Rápida ejecución. Real Time Expert Facilidad para integrarse con programas escritos en C. Encadenamiento hacia atrás. Incluye librería en C para ejecutar motor de inferencias. world.std.com:/vendors/rtis/rtexpert


MIKE

Micro interpreter for knowledge engineering Implementada en prolog por la Open Univ. (Reino Unido). Conflictos definidos por usuario. Encadenamiento hacia atrás y hacia adelante. Facilidad para representar marcos y para integrar

autoexplicación. Herramientas gráficas para seguimiento de la ejecución Disponible mediante ftp anónimo en: hcrl.open.ac.uk


MOBAL

Representaciones del dominio en lógica de primer orden. Facilidad para la adquisición de conocimiento y para su

verificación mediante interfaz gráfico. Incluye herramientas de aprendizaje automático. Mediante ftp anónimo en: ftp.gmd.de:/gmd/mlt/Mobal/


Babylon

Incluye facilidades para marcos, programación con restricciones.

Está escrito en Common Lisp Disponible en: http://www.gmd.de/


Entornos comerciales

Acquire: énfasis en adquisición http://vvv.com/ai/ Art: Integración con C, ADA y Lisp. Acceso a BBDD

http://www.brightware.com/ GBB: pizarras. ftp.cs.umass.edu:/gbb/ GURU: fuzzy y BBDD

http://www.savitar.com/prod_guru.htm KEE: reglas y marcos. Búsqueda. Integrable en lisp. Smart elements o Nexpert object: notación gráfica muy rica.

Marcos.


Entornos comerciales

Goldworks: integración con c. Marcos, reglas. http://www.goldhill-inc.com/goldworks.htm

G2: tiempo real, OO y reglas (atrás y adelante). Integración con C y Fortran

M.4: http://www.teknowledge.com/M4/proddesc.html Blaze Advisor:

http://www.fairisaac.com/Fairisaac/Solutions ILOG Jrules: http://www.ilog.com/products/jrules

ing. conocimiento uc3m, 2004 tema 5- diseño e implementación vimos cómo el ic produce el modelo...

Documents