Sistemas Expertos de Primera Generación (II)

Tareas basadas en conocimiento: clasificación

2

Contenidos

1. Tipología de tareas: tareas genéricas de Clancey

2. Modelos y métodos de clasificación simbólica

1. Clasificación simple2. Clasificación jerárquica

3. Modelos y métodos de diagnosis1. Árboles de fallos

3

Tipología de tareas

Rango limitado de tipos de tareasSe limita a tareas que hacen un uso intensivo del conocimiento

Objeto de estudio de las ciencias cognitivas/psicología Existen numerosas propuestasPropuesta de Clancey: tipología basada en la noción de sistema

4

Noción de “Sistema”

Término abstracto que describe aquello sobre lo que se aplica una tarea

diagnosis médica: cuerpo humanodiagnosis técnica: artefacto o dispositivoconfiguración ascensores: ascensor a configurar

No necesita existir (aún)

5

Tareas analíticas/sintéticas

Tareas analíticasEl sistema ya existeEntrada: datos sobre el sistemaSalida: alguna caracterización del sistema

Tareas sintéticasEl sistema aún no existeEntrada: requisitos del sistema a construirSalida: descripción del sistema

Subdivisión adicionalEn función del tipo de problema

6

Tareas genéricas de Clancey

Tareas que hacen uso intensivo del conocimiento

Tarea Analítica

clasificación

evaluación

Tarea Sintética

diagnosis

monitorización

predicción

modelado

planificación

scheduling

asignacióndiseño

configuración

7

Tareas Analíticas

Tipo de tarea

Entrada Salida Conocimiento Características

Análisis Observaciones del sistema

Caracterización del sistema

Modelo del sistema Se proporciona la descripción del sistema

Clasifi-cación

Propiedades de objetos

Clase Asociación características-clases

Conjunto de clases predefinidas

Diagnosis Síntomas, quejas

Categoría de fallo

Modelo de comportamiento

Distintos tipos de salidas: cadena causal, estado, componente

Evaluación Descripción caso

Clase de decisión

Criterios, normas Se realiza en un instante temporal

Monito-rización

Datos del sistema

Clase de discrepancia

Comportamiento normal del sistema

Se realiza repetidamente

Predicción Datos del sistema

Estado del sistema

Modelo de comportamiento

Proporciona una descripción del sistema en el futuro

8

Clasificación

La tarea de clasificación se caracteriza por seleccionar una clase

entre un conjunto finito –y habitualmente pequeño–de posibles clasesconociendo las características de las clases y las del objeto a clasificar

Ejemplosla clasificación taxonómica de seres vivos en familias y especies clasificación de objetos celestes a partir de imágenes de satélites

9

Interés clasificación

Rango:Los problemas que se puedan solucionar sin

necesidad de construir nuevas soluciones, sino eligiendo una entre un catálogo de posibles soluciones ya conocidas, son susceptibles de ser abordadas como una tarea de clasificación.

Sencilleztanto los modelos de clasificación como los

métodos que los utilizan son conceptualmente simples

10

Modelos y métodos de clasificación

Clasificación simpleModelo conceptualmente sencilloIlustra naturaleza de la tarea

Clasificación jerárquica

11

Clasificación simple

Un modelo de clasificación por recubrimiento es una quíntupla <D, S, C+, C-, OBS>, siendo:

D, Espacio de Datos, un conjunto finito de datos {D1, D2,... ...,Dk}.S, Espacio de Soluciones, un conjunto finito de soluciones {S1, S2,... ...Sm} o candidatos.C+, C-, son Relaciones de Recubrimiento, C+⊂SxD, C-⊂SxD, con C+∩ C- =∅.OBS el conjunto de valores que toman los datos Dide D.

12

Datos, observaciones y soluciones

Los elementos de D representan las observaciones que podemos realizar directamente sobre el sistema

valores en el conjunto {0, 1, ?} indicando su ausencia, su presencia o la no disponibilidad de la observación.

Ejemplo, Si Di representa el síntoma “fiebre” y observamos que el paciente no tiene fiebre, en el conjunto OBS tendremos Di=0.

Los elementos de S, candidatos, representan posibles soluciones del problema, por ejemplo bronquitis o asma

13

Ejemplo SM

D = {A=3, B=2, C=2, D=3, X=6, Y=6, F=12}OBS={1, 1, 1, 1, ?, ?, 0}S= {M1, M2, A1}

M1

M2

A1

X

Y

A

B

D

C F [10]

[3]

[2]

[2]

[3]

14

Relaciones de recubrimiento (I)

Elementos de C+ y C-

pares (Sj, Di) que representan condiciones necesarias para la consistencia de una solución con un conjunto de observaciones

C+ y C- definen un patrón de observaciones necesarias para la consistencia de un candidato con los datos

15

Relaciones de recubrimiento (II)

Para cada par (Sj, Di) solo puede darse uno de los siguientes casos:

(Sj, Di) ∈ C+. Sj es consistente con la observación Di =1

si Di =0, Sj no puede ser solución.

(Sj, Di) ∈ C-. Sj es consistente con la observación Di =0

si Di =1, Sj no puede ser solución.

(Sj, Di)∉C+, (Sj, Di)∉C-. Di es irrelevante para la solución Sj; (En cualquier otro caso, el dato Di es relevante para la solución Sj)

16

Consistencia

Un candidato, Sj, es consistente con un conjunto de observaciones OBS si y sólo si Sj es consistente con todas las observaciones disponibles; en caso contrario, Sj es inconsistente.

17

Explicación

Un candidato, Sj, es una explicaciónde OBS si y sólo si Sj es consistente con las observaciones de todos sus datos relevantes.

18

Solución

El modelo de recubrimiento secuencial proporciona de forma explicita un mecanismo para rechazar candidatos

los candidatos inconsistentes pueden eliminarse del conjunto de posibles soluciones

Solución del problema de clasificacióncriterios adicionales, que pueden depender del dominio de aplicación

19

Representación gráfica

1

1

0

0

0

D1

D2

D3

D4

D5

OBS-1

1

1

0

?

1

OBS-2

e

r

r

r

r

CAN-1

e

r

c

e

c

CAN-2

S1

S2

S3

S4

S5

Elementos de C+

Elementos de C-

e: explicaciónc: consistenter: rechazado

20

Solución problema de clasificación por recubrimiento

Candidatos simples, compuestosSimples: elementos de S

Mutuamente excluyentes: un único elemento de SNo mutuamente excluyentes: un subconjunto de S

Compuestos: combinación elementos de SExplosión combinatoriaPosibles soluciones: 2|S|

21

Solución problema de clasificación por recubrimiento

Criterio de inclusiónConsistencia

se incluyen todas las clases consistentes con algún dato observado.

Conservadorase incluyen todas las soluciones consistentes, aunque no se disponga de ninguna de sus observaciones relevantes.

Explicaciónsolo se incluyen las soluciones que son explicaciones.

Completala solución ha de explicar todas las observaciones.

Por eliminaciónsólo se acepta una solución cuando todas las demás han sido rechazadas.

22

Solución problema de clasificación por recubrimiento

Preferencia de candidatosEvidencia

preferir las soluciones consistentes con más datos.

Minimalidaddefinir la solución como los subconjuntos minimales de las soluciones compuestas.

Ponderaciónutilizar alguna función adicional para priorizar las hipótesis. Por ejemplo, probabilidad a priori, a posteriori o alguna medida de certeza.

23

Ejemplo SM

1

1

1

1

?

A=3

B=2

C=2

D=3

X=6

OBS-1

1

1

1

1

1

OBS-2

c

c

c

CAN-1

r

c

c

CAN-2

M1

M2

A1

Y=6

F=12

?

0

?

0

M1

M2

A1

X

Y

A

B

D

C F [10]

[3]

[2]

[2]

[3]

24

Soluciones

OBS-2Criterio inclusión: consistencia

M2, A1

Candidatos simples, no excluyentes: {M2, A1}Candidatos compuestos: {M2, A1, [M2, A1]}Candidatos compuestos, minimales: {M2, A1} ([M2, A1] también es solución, pero no se representa)

25

Clasificación simple mediante generación y prueba exhaustivas

El método se basa en tres suposiciones:Todas las observaciones necesarias están disponibles al principio del proceso.El espacio de soluciones, S, es suficientemente pequeño para poder considerar cada candidato individualmente.Candidatos simples, no excluyentes

26

Método degeneración y prueba exhaustivas

1. Soluciones ← ∅ 2. Obtener OBS 3. Para cada Candidato ∈ S hacer 4. Si Prueba(Candidato) Entonces Soluciones ← Soluciones ∪ Candidato 5. Fin Si 6. Fin Para 7. Devolver(Soluciones)

el procedimiento prueba rechaza los candidatos no consistentes con las observaciones actuales

Ejercicio: ejemplo SM, OBS-3=<1, 1, 1, 1, 1, 0, 0>.

27

Clasificación simple mediante generación guiada por datos

Mejora de la eficacia computacional generación y prueba exhaustivas

Utilizar conjunto reducido de observaciones para generar los candidatosProbar la consistencia de los candidatos con las observaciones restantes

Introducir procedimientosMonitor

Obtiene el valor de un conjunto reducido de observaciones (OBSdistinguidas)para las que existen candidatos consistentes.

Este conjunto de candidatos es mucho menor que el conjunto de posibles soluciones.

GenerarCandidatosGenera eficientemente las soluciones que son consistentes con OBSdistinguidas

28

Clasificación simple mediante generación guiada por datos

El método se basa en las siguientes suposiciones:

Disponemos de procedimientos eficientes Monitor y GenerarCandidatosTodas las observaciones necesarias están disponibles al principio del proceso.Candidatos simples, no excluyentes.

29

Método de generación guiada por datos

1. Soluciones ← ∅ 2. OBSdistinguidas ← Monitor( ) 3. Si OBSdistinguidas ≠ ∅ Entonces 4. Obtener OBS 5. Candidatos ← GenerarCandidatos(OBSdistinguidas) 6. Para cada Candidato ∈ Candidatos hacer 7. Si Prueba(Candidato) Entonces Soluciones ← Soluciones ∪

Candidato 8. Fin Si 9. Fin Para 10. Fin Si 11. Devolver(Soluciones)

30

Ejemplo SM

D={A=3, B=2, C=2, D=3, X=6, Y=6, F=12}.Se observan, A=[3], B=[2], C=[2], D=[3], X=[6], Y=[5], F=[10] que corresponden a OBS-3=<1, 1, 1, 1, 1, 0, 0>. Monitor devuelve las observaciones de X, Y, F: <1, 0, 0>GenerarCandidatos devuelve {M2, A1}Prueba rechaza A1Solución: {M2}

31

SM, guiado por datos

A=3

B=2

C=2

D=3

X=6

OBS-3

1

Monitor

r

c

c

GenerarCandicados CAN-3

M1

M2

A1

Y=6

F=12

0

0

1

1

1

1

1

0

0

r

c

r

32

Clasificación jerárquica

También clasificación heurísticaVariante clasificación simple

Modelo de recubrimientoJerarquía de abstracción de datosJerarquía de refinamiento de soluciones

33

Jerarquía de abstracción de datos

Abstracción Cualitativa“recuento leucocitario de 2500” se abstrae a “recuento leucocitario bajo”

Abstracción por Definición“recuento leucocitario bajo” se abstrae a “Leucopenia”, pues así se define la Leucopenia

Abstracción por Generalización“Leucopenia” se abstrae a “Inmunodepresión”, pues la Leucopenia es un tipo de inmunodepresión

OtrasCombinar dos sensores en un único dato…

34

Jerarquía de refinamiento de soluciones

Dotar al espacio de soluciones de estructura

Manipular clases de soluciones, que se van refinando

El modelo de recubrimiento no cambia:Se hace explícita la jerarquía implícita en el modelo de recubrimientoAñadiendo, si es necesario, clases abstractas

35

Modelo gráfico clasificación jerárquica

AD5

AD4

R1

D1

D2

D3

Datos sin procesar

S1

Datos Abstractos

Soluciones Abstractas

R2 R3 R4

AD1

AD2 AD3 S2

D4

R7

S3

S4

S5

S6

S7

D5

D6

D7

R8 R5

AD6

R6

Espacio de datos Espacio de soluciones

Soluciones Refinadas

36

Ejemplo

OBS:<1, ?, ?, ?, ?, ?, ?> Consistente con todas las clases: S1 es consistente

OBS: <0, ?, ?, ?, ?, ?, ?> Inconsistente con todas las clases: S1 es inconsistente

OBS: <1, 0, ?, ?, ?, ?, ?> Inconsistente con S2 y sus sucesoresConsistente con S1, S3 y sus sucesores

37

Eliminación jerárquica

Eliminar candidatos sucesores de nodos inconsistentesCondición necesaria

El conjunto de tuplas de las relaciones de recubrimiento de una subclase son una extensión de las tuplas de su clase padre:

si la tupla (Sj, Di) pertenece a C+ (C-), la tupla (SkDi) ha de pertenecer a C+ (C-) para todo Sk hijo de Sj

38

Clasificación jerárquica y obtención de observaciones

Estrategia sencilla y efectiva de obtener nuevas observaciones

buscar aquellas observaciones que nos permiten seguir refinando los candidatos consistentes de más alto nivel

EjemploOBS:<1, 0, 1, ?, ?, ?, ?> Consistentes S1 y S3

No necesitamos observaciones D4 y D5

Basta observar D6 y D7 para obtener la clasificación

39

Clasificación jerárquica mediante generación guiada por datos

Parte de conjunto reducido de observaciones obtenidas por MonitorAbstrae las observaciones con AbstraerGenera candidatos más abstractos con GenerarNuevosCandidatosSolicita nuevas observaciones, Obtener, para refinar candidatos, hasta llegar a nodos terminalesSi las nuevas observaciones son consistentes con candidatos abstractos no considerados, se repite el proceso

40

Clasificación jerárquica mediante generación guiada por datos

El método se basa en las siguientes suposiciones:

Disponemos de los procedimientos, Monitor, ObtenerAbstraer y GenerarNuevosCandidatosEl espacio de datos se organiza jerárquicamente facilitando la abstracción de datos. Las soluciones se organizan en una jerarquía de refinamiento que divide las clases de soluciones.En cada nivel del espacio de soluciones existe un conjunto de datos que permite discriminar entre ellas. Es posible obtener dichos datosCandidatos simples, no excluyentes.

41

Método degeneración guiada por datos

1. Soluciones ← ∅ 2. OBSdistinguidas ← Monitor( ) 3. OBS ← Abstraer(OBSdistinguidas) 4. Si OBS ≠ ∅ Entonces 5. Mientras se puedan generar nuevos candidatos raíz hacer 6. Candidatos ← GenerarNuevosCandidatosRaiz(OBS) 7. Soluciones ← ProbarDiscriminar(Candidatos) ∪ Soluciones 8. Mientras sea posible refinar candidatos hacer 9. Soluciones ← Soluciones – {Candidato_a_refinar} 10. Candidatos ← hijos de Candidato_a_refinar en la jerarquía de

soluciones 11. Soluciones ← PorbarDiscriminar(Candidatos) ∪ Soluciones 12. Fin Mientras 13. Fin Mientras 14. Fin Si 15. Devolver(Soluciones)

42

Obtener nuevas observaciones para discriminar entre candidatos

1. ProbarDiscriminar(Candidatos) 2. NuevasSoluciones ← ∅ 3. Obtener OBSadicionales, observaciones necesarias para discriminar entre las

hipótesis de Candidatos 4. NuevasObservaciones ← Abstraer(OBSadicionales) 5. OBS ← Nuevas observaciones ∪ OBS 6. Para cada Candidato ∈ Candidatos hacer 7. Si Prueba(Candidato) Entonces NuevasSoluciones ← NuevasSoluciones ∪

Candidato 8. Fin Si 9. Fin Para 10. Devolver(NuevasSoluciones)