Aprendizaje Automatico 6

259

Aprendizaje basado en casos

Captulo 8 Aprendizaje basado en casos La experiencia en la resolucion de problemas es una cualidad que poseen los humanos y que es necesario capturar para poder crear un modelo de comportamiento inteligente. Un principiante y un experto pueden resolver correctamente un problema pero el segundo lo hara de una manera mas e ciente que el primero. El experto recoge los datos mas utiles o aquellos que le pueden guiar para saber cuales son los datos mas relevantes de un problema y, con pocos datos, puede generar las hipotesis mas verosmiles. El principiante, sin embargo, solicita datos a ciegas, necesita muchos datos y observaciones, y genera muchas hipotesis poco probables. Todos los expertos han sido en su da principiantes, por lo que es logico suponer que existe un proceso mediante el cual un principiante llega a ser experto. Si analizamos en el diccionario la palabra "experto", vemos que signi ca "versado en el conocimiento de una cosa por la practica" [DLLC85]. Por lo tanto, la practica es la clave de la experiencia. En efecto, se ha observado que cuando aprenden realmente los alumnos es en las clases practicas. Concretamente, en la ense~nanza de medicina en las universidades espa~nolas, despues de cinco a~nos de estudios teoricos, los alumnos aprenden de nuevo todo su conocimiento en el ultimo a~no (sexto), en el llamado curso rotatorio, donde realizan diferentes turnos de practicas en todas las disciplinas (ginecologa, cardiologa, etc.). La resolucion de problemas es, pues, una manera de adaptar los conocimientos para ser aplicados adecuadamente. Aunque un experto y un principiante dispongan de unos conocimientos basicos sobre un dominio en concreto (conocimientos teoricos, basados en principios basicos, etc.), la organizacion de los conocimientos es diferente: el experto tiene sus conocimientos organizados mediante caractersticas que favorecen la resolucion de los problemas con los que se encuentra habitualmente, y el principiante organiza sus conocimientos de acuerdo a caractersticas super ciales, esto es, no directamente vinculadas a la resolucion de problemas. Por ejemplo, el experto tiene en cuenta el coste de los recursos disponibles para encontrar una solucion, la urgencia de encontrar una solucion (por ejemplo, si el paciente esta deshidratado el medico debe proporcionar un diagnostico rapido), etc. El principiante, en cambio, se ja en detalles super ciales como la edad del paciente. La organizacion de los conocimientos en el experto es una consecuencia de su experiencia en la resolucion de una importante cantidad de problemas o casos. Entre las diferentes disciplinas de la ciencia cognitiva1, la psi1 La ciencia cogniva estudia la mente, la inteligencia, el pensamiento y el conocimiento. La idea central reside en suponer que la mente procesa smbolos. Es una ciencia multi disciplinar donde se encuentran, entre otros, linguistas, psicologos, e informaticos, [GADN88, KUHN78]. En particular, la ciencia cognitiva compara la inteligencia humana con la arti cial con el proposito de comprender mejor el modelo cognitivo

© Los autores, 1998; © Edicions UPC, 1998.

260

Aprendizaje Automatico

cologa cognitiva ha demostrado ampliamente la importancia del aprendizaje por la experiencia ([CAPL90, ROSS90, SCHI89], etc.). En Inteligencia Arti cal MacCarthy anunciaba en 1958: "Nuestro ultimo objetivo es el de construir programas que aprendan de su propia experiencia tan efectivamente como lo hacen los humanos" P.R. Cohen and E.A. Faigenbaum, editors. Handbook of Arti cial Intelligence. Pitman, 1982.

El aprendizaje basado en casos [BARL91, KOLO93a, RIES89, AAMO94] consiste precisamente en aprender a partir de experiencias precedentes o casos. El aprendizaje basado en casos tambien se conoce como razonamiento basado en casos por el hecho de que este tipo de aprendizaje no se concibe sin el proceso de razonamiento que conlleva la obtencion de una nueva experiencia. De alguna manera, en el razonamiento basado en casos se supone la existencia de un ciclo razonamiento-aprendizaje llevado a cabo por un mismo agente. Por ello, y por ser el termino mas difundido, utilizaremos razonamiento basado en casos (abreviado RBC) para referirnos al aprendizaje basado en casos. En este captulo se presenta el RBC de acuerdo con la siguiente estructura. En primer lugar (seccion 8.1), se proporciona una introduccion a los fundamentos del RBC, las etapas de que se compone y sus aplicaciones. A continuacion se explica que son los casos, como se representan y organizan (seccion 8.2), y se detallan cada una de las etapas que tienen lugar en el RBC (secciones 8.3 a 8.6). Finalmente (seccion 8.7) se proporcionan breves descripciones de algunos de los sistemas basados en casos mas conocidos.

8.1 Introduccion En esta seccion se presenta, en primer lugar, cuales son los fundamentos del RBC, que etapas lo componen, destacando cuando y como tiene lugar el aprendizaje dentro del ciclo razonamientoaprendizaje. A continuacion se muestra como se aplica el RBC para resolver diferentes clases de problemas. Y, por ultimo, se explica como el RBC es facil de integrar con otros metodos, tanto de resolucion de problemas como de aprendizaje.

8.1.1 Fundamentos del razonamiento basado en casos El razonamiento basado en casos signi ca, pues, resolver problemas a partir de experiencias precedentes (casos), adaptando soluciones antiguas para resolver problemas nuevos, o recuperando casos anteriores para iluminar aspectos de la situacion actual. El razonamiento basado en casos es una clase particular de razonamiento analogico (ver captulo 3). Las caractersticas diferenciales del RBC versus el resto de metodos analogicos radican en el hecho que el RBC realiza analogas entre casos de un mismo dominio, mientras humano[COHE82].

© Los autores, 1998; © Edicions UPC, 1998.

261

Aprendizaje basado en casos

que el resto de metodos analogicos realizan analogas inter-dominio. Por ejemplo, en el razonamiento analogico la comprension del movimiento de los planetas alrededor del sol se utiliza para entender el comportamiento de los electrones de un atomo alrededor de su nucleo. El RBC, sin embargo, cuando conoce el comportamiento de un atomo, por ejemplo de hidrogeno, utiliza este conocimiento para derivar el comportamiento de otro atomo, como por ejemplo de oxgeno. En el primer caso se estan realizando analogas entre diferentes dominios: el planetario y el atomico; mientras que en el segundo caso las analogas se establecen dentro de un mismo dominio: el atomico. Otra caracterstica distintiva del RBC es la capacidad de aprendizaje. Como se ha visto en el captulo 3, los metodos analogicos consisten en diferentes etapas: recuperacion, adaptacion, evaluacion y aprendizaje. El RBC hace de la ultima etapa, el aprendizaje, el centro de todo el proceso analogico2. Aunque el razonamiento basado en casos es una tecnica relativamente reciente (se inicio hacia 1982 con los trabajos de memoria dinamica de R. Schank [SCHA82]), esta teniendo un gran eco en la comunidad de Inteligencia Arti cial porque presenta, entre otras, las siguientes ventajas: 1. El RBC como tecnica de adquisicion de conocimientos (a) libera al experto humano de la tarea de facilitar datos de entrenamiento propiamente dichos, caracterstica de otras tecnicas de aprendizaje tradicionales, y es su ciente que el sistema observe casos resueltos, eventualmente, por un maestro, y (b) facilita la interaccion hombre-maquina, ya que la comunicacion se puede realizar mediantes casos concretos y no con trozos parciales de conocimiento, como son las reglas (el experto suele tener mas facilidad para utilizar representaciones basadas en episodios que en reglas, dada la cantidad de esfuerzo que encierra la abstraccion de una regla general a partir de un caso particular). 2. El RBC como mecanismo de resolucion de problemas permite, como veremos mas adelante, aprender de la experiencia propia del sistema, de manera que un sistema inicialmente no-experto puede llegar a ser experto. Otra ventaja del RBC, aunque no menos importante, es que se ha demostrado que el RBC permite trabajar en dominios de problemas de difcil estructuracion y representacion, caractersticas que normalmente presentan las aplicaciones del mundo real. Por ejemplo, un abogado tiene el codigo legislativo sobre el cual apoyarse para poder defender a sus clientes. Ahora bien, en este codigo solamente estan recogidas reglas de aplicacion general. Un abogado necesita conocer en que circunstancias se han aplicado las leyes, cuando ha habido una excepcion respecto a ellas, etc. Este conocimiento no son mas que casos que complementan la informacion general representada en las leyes. Expresar todo el conocimiento contenido en los casos mediante leyes resultara un problema intratable. Tambien es cierto que no todo son ventajas respecto al RBC. El RBC resulta costoso en cuanto a memoria. Esto es, este tipo de razonamiento se basa en recordar casos que para tal proposito deben estar almacenados en algun lugar. La informacion de los casos suele ser extensa tanto por su cantidad como por la variedad de datos que contienen, como se ha podido intuir en

2 De hecho, el RBC no es un metodo unico, sino una famlia de metodos donde cada cual hace una instanciacion diferente de las etapas que conforman el razonamiento analogico.

© Los autores, 1998; © Edicions UPC, 1998.

262

Aprendizaje Automatico

Problema

? ?

Caso nuevo Aprendizaje

6

k

Caso aprendido

s

Caso comprobado/ Base de casos reparado Caso resuelto Evaluacion 

 R

Recuperacion Caso nuevo Caso recuperado

?

Adaptacion

Figura 8.1: Etapas del RBC que con guran el ciclo razonamiento-aprendizaje. el ejemplo del abogado. Otro tipo de representacion, como pueden ser las reglas, resulta mas economica. Otra desventaja importante del RBC que es necesario resaltar, es que hasta el momento no han habido trabajos exitosos para la manipulacion de la incertidumbre.

8.1.2 Etapas del RBC Dado un problema a resolver (problema actual) y una base de casos, se realizan las siguientes etapas para resolver el problema: 1. 2. 3. 4.

Recuperacion. Adaptacion. Evaluacion. Aprendizaje.

En la gura 8.1 se muestra como el ciclo razonamiento-aprendizaje se cierra con estas etapas. En las secciones siguientes se estudian en mayor profundidad las caractersticas y metodos que permiten implementar la recuperacion, la adaptacion, la evaluacion y el aprendizaje. Antes de proseguir, sin embargo, es conveniente remarcar en que consiste el aprendizaje en este tipo de sistemas.

8.1.3 RBC y aprendizaje En los sistemas basados en casos existen diferentes ocasiones para el aprendizaje. En primer lugar, para poder iniciar el proceso de razonamiento, es necesario disponer de un conjunto

© Los autores, 1998; © Edicions UPC, 1998.

263

Aprendizaje basado en casos

de casos precedentes o librera de casos. Como obtenerlos y como organizarlos (por ejemplo mediante el uso de ndices) es un problema de adquisicion de conocimientos que se puede resolver mediante tecnicas de aprendizaje. En segundo lugar, los casos pertenecen a un determinado dominio que es necesario conocer para poder interpretar la informacion contenida en ellos. Por tanto no es descabellado obtener una descripcion del dominio bien como consecuencia del propio mecanismo de aprendizaje basado en casos, bien mediante otras tecnicas de aprendizaje diferentes (por ejemplo EBL o induccion). Finalmente, cada nuevo caso resuelto por el sistema presenta una nueva ocasion para aprender. En este sentido se pueden aprender nuevosndices para reorganizar los casos, puede tener lugar la generalizacion de diversos casos individuales en prototipos o casos esquematicos, etc. Todas estas ocasiones de aprendizaje las encontramos soportadas bien por metodos ad hoc, bien por otras tecnicas de aprendizaje estudiadas en otros captulos de este libro.

8.1.4 Aplicaciones El RBC se puede aplicar para resolver los siguientes tipos de problemas [KOLO91]:

 Problemas legales.

Los problemas legales consisten en construir argumentos persuasivos para convencer que una determinada posicion (la que se de ende) es la correcta. Existen reglas, como ya se ha mencionado, pero son poco espec cas y hasta se contradicen entre s. Eso hace que la unica forma que disponen los abogados para interpretar las leyes es recurrir a casos anteriores. Estos sistemas justi can por s mismos el RBC. Resultados de aplicar el RBC a este tipo de problemas son, por ejemplo, los sistemas HYPO [KOLO91] y JUDGE [RIES89].  Diagnostico. La tarea de diagnosis consiste en explicar un conjunto de sntomas. Por ejemplo, un medico analiza los sntomas que presenta un paciente, lo que le lleva a justi car su manifestacion por la presencia de alguna anomala en el enfermo. Un mecanico construye una explicacion de la presencia de unos determinados sntomas que presenta un motor, que le sugiere que piezas debe reponer o reparar. Los casos proporcionan una manera e ciente de realizar la diagnosis, ya que, como se ha visto al principio de este captulo, los expertos recurren a sus experiencias anteriores para reducir rapidamente el espacio de posibles explicaciones a tener en cuenta. El sistema CASEY, que se describe en la seccion 8.7.1 en mayor detalle, es un ejemplo de RBC aplicado al diagnostico medico.  Clasi cacion. Un problema de clasi cacion comporta identi car a que grupo pertenece un individuo de acuerdo con el conjunto de caractersticas que presenta. En particular, el diagnostico se puede reducir a un caso particular de clasi cacion en el que a partir de un conjunto de caractersticas (sntomas) se clasi ca un objeto (enfermedad, pieza que no funciona bien, : : :). En la seccion 8.7.2 se detalla PROTOS, un sistema basado en casos aplicado a la clasi cacion.

© Los autores, 1998; © Edicions UPC, 1998.

264

Aprendizaje Automatico

 Plani cacion.

Un problema de plani cacion se de ne como la busqueda de la secuencia de acciones (o pasos) a realizar a partir de una situacion inicial (actual) para llegar a una situacion nal (u objetivo). Dos puntos importantes a tener en cuenta en el momento de decidir sobre una accion son los siguientes: 1) las condiciones bajo las que la accion es aplicable deben satisfacerse en el momento en que esta se lleve a cabo, y 2) las acciones del nal de la secuencia no deben deshacer los resultados de las primeras. El razonamiento basado en casos aplicado a la plani cacion se conoce como plani cacion basada en casos (case-based planning). La plani cacion basada en casos se caracteriza por construir los planes conforme a los conocimientos que tiene el plani cador sobre planes empleados en experiencias pasadas (casos). La construccion de un plan consiste en la busqueda de un plan en la memoria del plani cador que satisfaga todos los objetivos. CHEF y SMART, descritos en la seccion 8.7.3, son sistemas que aplican el RBC para resolver problemas de plani cacion.

 Dise~no.

Los problemas de dise~no se de nen por un conjunto de restricciones que el resolvedor de problemas debe tratar para proporcionar un modelo que las satisfaga. Normalmente el espacio de busqueda para el resolvedor de problemas es grande y las restricciones solamente le sirven de gua. La tactica mas habitual es descomponer el problema (modelo) en piezas y, una vez conseguidas estas, reconsiderar el modelo completo. En el modelo nal no deben existir incompatibilidades entre las partes. El RBC permite acelerar la obtencion de una solucion teniendo en cuenta los casos precedentes donde se ha dado el mismo conjunto de restricciones, o una parte de ellas, reduciendo as el problema. Puede ocurrir, tambien, que el problema este sobredimensionado (exceso de restricciones), y entonces los casos proporcionan ayudas para conocer que restricciones se relajaron en situaciones semejantes anteriores a la actual. JULIA, descrito en la seccion 8.7.4, es un ejemplo de la aplicacion del RBC a este tipo de problemas.

Esta lista no es exhaustiva, ni mucho menos. En general, el RBC resuelve los mismos tipos de problemas planteados en otras disciplinas de la IA.

8.1.5 Integracion del RBC con otros metodos El RBC, por sus caractersticas, es un metodo que integra resolucion de problemas y aprendizaje. Sin embargo, en un sistema que posea pocos casos (un sistema novato o aprendiz), puede ser conveniente disponer de un resolvedor de problemas alternativo que se utilice cuando no haya casos disponibles y permita generar casos sobre los cuales aprender. Este es el caso de SMART (ver seccion 8.7.3 y 4.5.4) y CASEY (ver seccion 8.7.1). Estos sistemas usan el razonamiento basado en casos como un mecanismo para hacer mas e ciente la resolucion de problemas, pero disponen de metodos alternativos (un plani cador de caracter general en el primer caso, y un mecanismo de razonamiento causal en el segundo) para generar soluciones mas costosas cuando no exista una experiencia anterior. Respecto al aprendizaje, ya se ha indicado que puede haber diferentes tipos: aprendizaje de ndices, de caractersticas, etc. Cada tipo de aprendizaje se puede llevar a cabo mediante

© Los autores, 1998; © Edicions UPC, 1998.

265

Aprendizaje basado en casos

juguete de trapo

 6I

juguete 1 Mi

juguete de carton

6

juguete de madera

}

mu~neca pelota recortable tren de de trapo de trapo madera juego de osito construcci o n de peluche Figura 8.2: Organizacion de los juguetes segun el material con que estan hechos. metodos de los estudiados en otros captulos de este libro, como por ejemplo metodos inductivos (ver el captulo 2) o metodos basados en explicaciones (ver el captulo 4). Toda la potencia del RBC reside en la organizacion de los casos en su memoria. Pero para conseguir estructuras y de niciones mejores, nuevo vocabulario, etc. necesita apoyarse en otros metodos de aprendizaje. Por ejemplo, supongase que existen dos instancias (casos) de juguete adecuado para una guardera infantil: pelota de trapo y mu~neca de trapo. En la base de casos se pueden guardar los dos casos. Pero quizas resulte mas interesante almacenar la informacion siguiente: un juguete de trapo es un juguete adecuado para una guardera. Este proceso de obtener juguete de trapo a partir de pelota de trapo y de mu~neca de trapo solo es posible si el RBC hace uso de metodos de abstraccion apoyados por una teora del dominio (ver gura 8.2).

8.2 La librera de casos En el RBC la organizacion de los casos precedentes en la memoria es una cuestion fundamental para poder utilizar los casos en problemas futuros. Cuando se contruye un mecanismo de razonamiento basado en casos debe pensarse en una organizacion dinamica de los casos en memoria, ya que la incorporacion de un nuevo caso puede in uir en la disposicion de los casos precedentes. Entre las diferentes organizaciones de memoria, podemos encontrar una organizacion plana, donde los casos estan almacenados secuencialmente en una lista o chero ( gura 8.3a), o una organizacion jerarquica donde los casos estan organizados de acuerdo con sus caractersticas ( gura 8.3b), de manera que cada nodo corresponda a una caracterstica compartida por un conjunto de casos (redes de discriminacion o arboles de decision, ver la seccion 2.3.1). Analicemos primero que es un caso, y como representarlo; y a continuacion como se pueden de nir ndices para su manipulacion.

© Los autores, 1998; © Edicions UPC, 1998.

266

Aprendizaje Automatico

Caso n ::: Caso 3 Caso 2 Caso 1

:::

 Tos > 37

s Fiebre

< 37



Caso n

w

Caso 1

(a)

Rno

Caso 2 (b)

Figura 8.3: Ejemplos de organizacion de casos.

8.2.1 Representacion de los casos El elemento basico en el RBC es el caso. Pero, >que es y como lo podemos representar? Un caso es una experiencia que puede estar representada por diferentes caractersticas, como la descripcion de un problema (los objetivos y/o restricciones a satisfacer), las soluciones (la solucion propiamente dicha o acompa~nada de un conjunto de anotaciones, justi caciones, etc.), los datos iniciales, y hasta incluso una traza que indique como se ha llevado a cabo la resolucion del caso (ver gura 8.4). Las caractersticas de los casos (individuos o prototipos) son la clave para la construccion de ndices que hagan exible la memorizacion de los casos y su futura reutilizacion. La representacion de los casos consiste bien en retener la informacion tal cual ha sido proporcionada al sistema (individuos) o realizando algun proceso de generalizacion entre los casos precedentes en memoria (prototipos). En el segundo caso se requiere menor cantidad de memoria ya que solamente se almacenara un caso cuando no se asemeje a otro existente en la memoria. Si ya existe un caso similar, resultante de la generalizacion de casos anteriores, esto es un prototipo, se actualizara la informacion del prototipo con la informacion del nuevo caso. En la gura 8.5a se muestra un ejemplo de individuo mientras que en la gura 8.5b se proporciona un ejemplo de prototipo. En el momento de resolver un problema, es importante distinguir entre casos en memoria y un nuevo caso. Los casos en memoria, tambien conocidos como casos de entrenamiento o, simplemente, casos, son los que el sistema dispone en la librera para resolver nuevos problemas. El termino nuevo caso, tambien llamado caso actual o caso de test, se re ere al problema que en un determinado momento se quiere solucionar. Esta terminologa estara presente a lo largo del captulo.

© Los autores, 1998; © Edicions UPC, 1998.

267

Aprendizaje basado en casos

Descripcion de la situacion Fecha: 29{8{94 Partes: USM esun: corporacion competidores: Marson lista{productos: maquina{USM un{tipo{de: maquina{remaches uso: produccion{remaches mercado: compradores{remaches tecnologa{empleada: dise~no{remaches produccion{remaches productos{competidores: maquina{marson constructor: USM inicio{proyecto: 1954 n{proyecto: 1959 conocimiento{empleado: sobre{maquinas{USM medidas{seguridad: medidas{mnimas acceso{premisas{controlado restricciones{entrada{visitantes acuerdo{empleados{no{revelar violacion{seguridad : nil similitudes{productos{competitivos: nil Marson esun: corporacion competidores: USM lista{productos: maquina{Marson un{tipo{de: maquina{remaches uso: produccion{remaches mercado: compradores{remaches tecnologa{empleada: dise~no{remaches produccion{remaches productos{competidores: maquina{USM constructor: USM inicio{proyecto: 1961 n{proyecto: 1964 papel{partes: (demandante USM) (defendido Marson) demanda: (demanda USM (tra co{secretos{inapropiado Marson)) resultados: (ganancia{competitiva Marson) (medidas{seguridad{adoptadas USM)

Figura 8.4: Un caso legal.

© Los autores, 1998; © Edicions UPC, 1998.

268

Aprendizaje Automatico

RECETA1 Ingredientes: Besugo(1) Tocino(2 tiras) Pimiento-morron(2 tiras) Limon(1) Aceite-oliva(1dl) Vino-blanco(1dl) Sal Perejil Ajos(2) Pan-rallado(1cuch) Mantequilla(1cuch) Solucion: Besugo-al-horno (a)

RECETA2 Ingredientes: Pescado(1) Tocino(2 tiras) Pimiento(2 tiras) Ctrico(1) Aceite(1dl) Vino(1dl) Especies Espesante(1cuch) Grasa-animal(1cuch) Solucion: Pescado-al-horno (b)

Figura 8.5: Receta recomendada. Caso individual (a) y prototipo (b).

8.2.2 Indices Los ndices son las caractersticas de los casos que se utilizan para recuperarlos de memoria en situaciones que puedan ser de utilidad. Dichas caractersticas vienen determinadas por el vocabulario disponible del dominio sobre el que se esta trabajando. No resultara e ciente pensar en indexar los casos por el conjunto completo de caractersticas, sino que los ndices deben elegirse entre aquellas caractersticas disponibles teniendo en cuenta las siguientes propiedades [KOLO93a]: 1. Prediccion. Los ndices deben distinguir un caso del resto, en el sentido de que su recuperacion sea coherente con los problemas que resuelve y/o los posibles contratiempos que presente. 2. Utilidad. Los ndices deben ser utiles para la consecucion de un objetivo o una tarea. 3. Abstraccion. Los ndices deben permitir que el caso sea aplicable (recuperado) en una variedad amplia de situaciones. 4. Concrecion. Losndices deben ser generales, pero tambien lo su cientemente concretos como para que se puedan reconocer con un coste inferencial peque~no3 . Por ejemplo, los siguientes ndices pueden ser considerados:

3 El proceso de relacionar un ndice abstracto con una caracterstica del caso actual repercute en un coste inferencial.

© Los autores, 1998; © Edicions UPC, 1998.

269

Aprendizaje basado en casos

    

objetivos restricciones combinacion de caractersticas que determinan la solucion caractersticas responsables de fracasos caractersticas responsables de la aparicion de efectos no deseados

8.3 Recuperacion de casos La clave del razonamiento analogico, y consecuentemente, la del RBC, radica en determinar cuando dos casos (C M en memoria y C el caso actual) son semejantes. Entre dos casos existen diferentes tipos de similitud: estructural, semantica, organizativa y hasta incluso pragmatica. Por ejemplo, una similitud estructural entre la Tierra y una pelota, reside en el hecho que la estructura de ambas es una esfera. Una similitud semantica entre una pelota de baloncesto y una de futbol, es que ambas son pelotas que sirven para practicar un deporte. Para determinar si un caso es similar a otro, se de ne una funcion de comparacion (matching) donde se confrontan las caractersticas de un caso con las del otro. El resultado del procedimiento de matching nos informa si la similitud es exacta o parcial. Exacta signi ca que ambos casos son identicos. Parcial quiere decir que existe una semejanza entre los casos determinada por un grado de semejanza o similitud. Por ejemplo, si comparamos la pelota de baloncesto de reglamento de Javier con la pelota de baloncesto de reglamento de Monica, el matching es exacto: las dos son pelotas identicas, con la misma funcionalidad, el mismo color, etc. Ahora bien, si comparamos la pelota de futbol de Javier que le ha regalado su abuelo, con la pelota de futbol de reglamento de Monica, el matching es parcial: es cierto que las dos son pelotas y sirven para jugar al futbol, pero la primera es de color azul y esta hecha de plastico, mientras que la segunda es blanca y negra y esta hecha de piel. En el procedimiento de matching se pueden utilizar un conjunto de heursticas que ayuden a determinar que caractersticas son mas relevantes, que indiquen como tratar una determinada caracterstica que posee un caso pero que esta ausente en el otro caso con el que lo estamos comparando, etc. Para la determinacion de una caracterstica f presente en C y ausente en C M la heurstica mas utilizada consiste en buscar en C M una caracterstica f 0 mas abstracta que f y entonces comparar f con f 0 . Por ejemplo supongamos que C tiene el siguiente conjunto de caractersticas: f hombre, edad(61), antecedentes(alcoholico) g, y C M = f hombre, viejo, antecedentes(alcoholico) g. La caracterstica presente en C y ausente en C M es edad(61). Ahora bien, en C M existe una caracterstica mas abstracta, viejo, que podemos suponer que en su de nicion incluye a los hombres de 61 a~nos de edad. Por tanto viejo y edad(61) pueden compararse. Algunos sistemas utilizan metodos mas so sticados para resolver el problema de la caracterstica ausente como, por ejemplo, un modelo causal que la deduzca usando el resto de datos del caso (ver CASEY en la seccion 8.7.1). En muchas ocasiones existe no uno, sino un conjunto de casos en memoria (C1M , C2M , : : :, CnM ) que obtienen un resultado parcial en el proceso de matching con el caso actual C. Finalmente

© Los autores, 1998; © Edicions UPC, 1998.

270

Aprendizaje Automatico

se elige un solo caso de entre todos ellos, de acuerdo con una serie de criterios, para adaptar la solucion al problema actual.

8.3.1 Procedimiento de comparacion o matching Aunque de nir un metodo de matching para recuperar casos en memoria es fundamental para cualquier RBC, existen pocos estudios formales al respecto. El matching se basa en una funcion de similitud que se de ne entre dos casos. Su formula mas simple consiste en de nir una funcion de similitud entre las caractersticas de un caso y las del otro, y calcular el valor medio de todas ellas. Por ejemplo, supongamos que tenemos los casos, C y C M , donde C es el caso actual y C M el caso recuperado de memoria. Las caractersticas de cada uno de los casos son: C = ff1 ; : : :; fn g; C M = ff1M ; : : :; fmM g En particular, las caractersticas de C M constituyen los ndices con los que el caso C M es recuperado de memoria. Se de ne una funcion de similitud, sim, entre dos caractersticas, fi de C y fjM de C M , como:  fi = fjM sim(fi ; fjM ) = 10 si en cualquier otro caso Entonces, la similitud global, simg , entre dos casos se determina como: P P M sim(f ; f M ) i j M simg (C; C ) = i2C j 2CjC j Donde jC j es el numero de caractersticas de C. Para ilustrar este concepto con un ejemplo, observar los casos de la gura 8.6, y suponer que se intenta saber a que categora pertenece el juguete siguiente: OSO edad: 3 material-principal: trapo piezas-peque~nas: s  proposito: diversion lugar: interior jugadores: 1 categora: ? Para ello se calcula la similitud de los casos en memoria (PELOTA y COCHE) con el caso actual (OSO):

 PELOTA tiene en comun con OSO las caractersticas edad, material-pral y proposito. Esto es:

sim(edad(OSO); edad(P ELOT A)) = 1 sim(material ; pral(OSO); material ; pral(P ELOT A)) = 1 sim(proposito(OSO); proposito(PELOTA)) = 1

© Los autores, 1998; © Edicions UPC, 1998.

271

Aprendizaje basado en casos

JUGUETE edad: [0..3] material-pral: [plastico, madera, trapo, hierro, : : :] piezas-peque~nas: [si,no] proposito: [diversion, educacion, deporte] lugar: [interior, exterior] jugadores: [1..n] categora: [OK, belico, peligroso] PELOTA edad: 3 material-pral: trapo piezas-peque~nas: no proposito: diversion lugar: jugadores: categora: OK

COCHE edad: material-pral: hierro piezas-peque~nas: s proposito: diversion lugar: jugadores: 1 categora: peligroso

Figura 8.6: Un caso de juguete correcto (PELOTA) y otro peligroso (COCHE). Y para cualquier otra caracterstica fi de PELOTA diferente de las anteriores y toda caracterstica fj de OSO, sim(fi ; fj ) = 0  Mientras que COCHE tiene en comun con OSO las caractersticas: piezas-peque~nas, proposito y jugadores. Entonces, sim(piezas-peque~nas(OSO); piezas-peque~nas(COCHE)) = 1 sim(proposito(OSO); proposito(COCHE)) = 1 sim(jugadores(OSO); jugadores(COCHE)) = 1 Y para cualquier otra caracterstica, la funcion de similitud se evalua a 0. Por tanto, la similitud global de cada caso es, por tanto, la misma: simg (OSO; P ELOTA) = 73 simg (OSO; COCHE) = 37 El siguiente paso para hacer mas precisa la recuperacion de casos consiste en ponderar la similitud entre caractersticas. Las caractersticas pueden considerarse relevantes si tienen asociado un peso alto, e irrelevantes en caso contrario. Por ejemplo, la caracterstica nombre es irrelevante para determinar la enfermedad de un paciente, por lo que se le asocia un peso muy

© Los autores, 1998; © Edicions UPC, 1998.

272

Aprendizaje Automatico

Caracterstica Relevancia edad 0.1 material-pral 0.8 piezas-peque~nas 0.7 proposito 0.5 lugar 0.3 jugadores 0.1 categora 1 Tabla 8.1: Caractersticas y su importancia al determinar la peligrosidad de un juguete. bajo. Mientras que ebre tiene una importancia mayor y, consecuentemente, mayor sera su peso. Los pesos conllevan proporcionar al sistema conocimientos adicionales que debe aportar el experto. Aunque, para liberar al experto de esta tarea de adquisicion de conocimientos, puede ser mas conveniente obtener los pesos mediante la utilizacion de metodos de aprendizaje automatico (como por ejemplo, en BOLERO [LOPE93a]). Usando pesos asociados a las caractersticas (ndices), la similitud global entre dos casos se de ne como: P P M w sim(f ; f M ) i j C i M simg (C; C ) = i2C j 2P i2C wi donde wi es el peso asociado a la caracterstica fi de C. En el ejemplo de los juguetes, si ahora se supone que la relevancia de las caractersticas vara de acuerdo con los datos que se muestran en la tabla 8.1, se obtienen los resultados siguientes: simg (OSO; PELOTA) = 0:1+03::58+0:5 = 0:4

:1 = 0:37 simg (OSO; COCHE) = 0:7+03::5+0 5

Por tanto, el caso de memoria mas similar al caso actual, OSO, es PELOTA. Otro paso adelante para re nar la funcion de similitud consiste en evaluar la semejanza entre dos caractersticas, fi y fjM , dentro del intervalo [0,1] (ver por ejemplo BOLERO en [LOPE93b]). El calculo ahora se basa, no en saber si las caractersticas son identicas, sino por ejemplo, en su proximidad semantica o estructural. Y as sucesivamente se pueden elaborar medidas de similitud mas so sticadas. Por ejemplo, Bonissone [BONI92] propone el uso de valores lingusticos asociados a valores semanticos para indexar y recuperar casos de memoria. Con su metodo, en lugar de determinar el peso de una caracterstica numericamente (como por ejemplo, sim(fi ; fjM ) = 0:45), se utilizan conceptos como indexacion fuerte o muy-fuerte; y, en lugar de obtener un valor numerico como grado de similitud, se obtiene una etiqueta lingustica como por ejemplo completo para indicar un matching exacto, o casi-completo.

© Los autores, 1998; © Edicions UPC, 1998.

273

Aprendizaje basado en casos

8.3.2 Seleccion del caso idoneo Cuando existen varios casos que tienen un matching parcial con el caso actual, es conveniente elegir entre todos ellos el caso mas adecuado. Para ello, es necesario realizar los siguientes pasos: 1. Eliminar aquellos casos cuyos grados de similitud sean bajos respecto al resto. Esto es, dejar solamente los casos mas semejantes al caso actual. 2. Ordenar los casos. En la ordenacion de casos se pueden aplicar diferentes criterios como, por ejemplo:

 valorar mas las caractersticas que aparecen siempre conjuntamente,  hacer un balance (trade-o) entre el numero de caractersticas presentes y el numero de ausentes,  valorar mejor el caso que tenga una solucion inferencial menos costosa,  considerar los casos mas espec cos antes que los mas generales.

En general, se puede aplicar cualquier heurstica que consiga los propositos que se pretendan. Por ejemplo, cuando, en el dominio de los juguetes, se ha obtenido el mismo grado de similitud entre OSO y los dos casos en memoria (PELOTA y COCHE) para la funcion de similitud mas primitiva, una heurstica aplicable para decidir que caso seleccionar es: escoger el caso de mas frecuente aparicion.

8.4 Adaptacion de casos La elaboracion o adaptacion consiste en acomodar la solucion del caso C M recuperado de la memoria para obtener la solucion del caso C. En la adaptacion es necesario tener en cuenta las diferencias entre C M y C (por ejemplo si hay caractersticas de C M ausentes en C, o viceversa). Los metodos de adaptacion son numerosos, pero basicamente se pueden agrupar en dos tipos: los que realizan la adaptacion de la solucion y aquellos que vuelven a aplicar los pasos inferenciales que han conducido a la solucion del caso recuperado de memoria.

8.4.1 Adaptar la solucion Para adaptar la solucion se puede seguir, por ejemplo, cualquiera de los siguientes metodos:

 Reinstanciacion o substitucion de una caracterstica por otra.  Busqueda local de caractersticas en una red de discriminacion.  Uso de crticos que de nen un conjunto especial de reglas de adaptacion para manipular caractersticas que interaccionan (ver CHEF en seccion 8.7.3).

© Los autores, 1998; © Edicions UPC, 1998.

274

Aprendizaje Automatico

 Eliminacion de una caracterstica espuria (no util). En el ejemplo de los juguetes, se ha obtenido nalmente que PELOTA es el caso de memoria mas similar a OSO. Existen caractersticas de OSO que no aparecen en pelota pero que no se consideran importantes para el proceso de clasi cacion del juguete en su categora. Por ello se trans ere directamente la solucion de PELOTA a OSO. Por tanto, OSO es un juguete adecuado para una guardera infantil (categora = OK).

8.4.2 Reaplicar el proceso de razonamiento Este tipo de adaptacion ya se ha estudiado en el captulo 3 , con los metodos analogicos. Sin animo de ser redundante, es conveniente remarcar que reaplicar el proceso de razonamiento consiste en veri car las condiciones que han hecho posible la aplicacion de determinados metodos, reglas o pasos inferenciales, en el caso recuperado de memoria. Si estas se cumplen para el caso actual, se reaplica el metodo, regla o inferencia.

8.5 Evaluacion de los resultados La etapa de evaluacion determina si la solucion del caso elaborada en la etapa de adaptacion es plausible. A pesar de la importancia de la evaluacion, pues en ella se basa el cierre del ciclo razonamiento-aprendizaje del RBC (ver gura 8.1), muy pocos sistemas basados en casos van mas alla de consultar a un oraculo (maestro, experto humano) para determinar la validez de la solucion. Por ejemplo, una vez clasi cada la enfermedad de un paciente, PROTOS (ver seccion 8.7.2) pregunta a su maestro si la clasi cacion ha sido correcta. Si la tarea del sistema basado en casos es la plani cacion, a menudo la evaluacion de los planes se realiza mediante la ejecucion de los planes en el mundo y comparando los resultados. Sistemas mas so sticados permiten simular los planes antes de ejecutarlos y realizar las correcciones oportunas. En el ejemplo de los juguetes se ha preguntado a una puericultora, que ha indicado que la clasi cacion ha sido incorrecta. El OSO posee piezas peque~nas, como los ojos, que resultan peligrosas (el bebe se las puede comer). El resultado de la evaluacion es, por tanto, o bien un nuevo caso cuya solucion ha sido con rmada, o un caso reparado.

8.5.1 Reparacion El proceso de reparacion es similar a la adaptacion pues tambien consiste en modi car una solucion para adecuarla a una situacion dada [RIES89]. En la reparacion, sin embargo, se dispone no solamente de la solucion a modi car, sino se conoce que ha fracasado y, posiblemente, una justi cacion o explicacion del fracaso. En la reparacion deben realizarse las acciones oportunas para eliminar el fallo que se haya podido detectar y llegar a la solucion deseada. Para poder realizar las reparaciones es necesario disponer del conocimiento espec co del

© Los autores, 1998; © Edicions UPC, 1998.

275

Aprendizaje basado en casos

dominio, o general, que permita extraer de la explicacion del fracaso las caractersticas que faciliten su reparacion. Estas reparaciones han de venir expresadas (o indexadas, como en el caso de CHEF) para poder ser recuperadas una vez se detectan las caractersticas relevantes que han conducido al fracaso. Despues de recuperar la informacion su ciente para reparar el caso actual (casos espec cos de reparacion, o metodos espec cos para reparar el fallo concreto que ha tenido lugar), este se repara haciendo uso de metodos semejantes a los de la adaptacion: substitucion de una caracterstica por otra, eliminacion de una caracterstica, etc., obteniendose nalmente el caso reparado.

8.6 Aprendizaje por casos La consolidacion del RBC consiste en almacenar el caso nuevo C resultado del proceso analogico. Es en este proceso de almacenamiento donde surge la oportunidad de reorganizar la memoria y, en consecuencia, de aprender de la nueva experiencia. Si la solucion adaptada ha resultado correcta, el nuevo caso proporcionara nuevos conocimientos al sistema. Si no ha sido correcta, se tendran que reorganizar los casos en memoria para que no se vuelvan a producir los mismos errores en un futuro. No todos los sistemas de aprendizaje a partir de casos consideran las dos oportunidades de aprendizaje.

8.6.1 Acumulando nuevas experiencias Una caso acabado de resolver por el sistema no tiene porque ser necesariamente identico a uno en memoria. Existen tres razones fundamentales. En primer lugar, un matching parcial durante el proceso de recuperacion indica que no existe un caso identico; ya que entonces se hubiera obtenido un matching exacto. En segundo lugar, la existencia de un proceso de adaptacion indica que la solucion no se tras ere "tal cual", sino que se reemplazan unas caractersticas de un caso por otras, etc. Y, en tercer lugar, pueden adaptarse diferentes partes de casos diferentes para resolver un problema. Esto es, si el conocimiento de un problema se enriquece con su resolucion, se puede desestimar un caso C1M recuperado de memoria en un momento t cuando eran conocidas un conjunto de caractersticas F, por otro caso C2M en un momento t0 cuando el conjunto de caractersticas se ha ampliado a F 0. As funciona, por ejemplo, JULIA (ver seccion 8.7.4). Si una experiencia no esta en memoria, es necesario, en primer lugar, considerar si es necesario almacenarla o no. Si se guardan todos los casos, la memoria crece desmesuradamente y su tratamiento resulta, a la larga, ine ciente para la resolucion de problemas. Por ello debe establecerse un mecanismo, basado por ejemplo en una estimacion de la utilidad del caso, para decidir que casos deben retenerse. Si el caso a incorporar es diferente pero bastante similar a uno precedente en memoria C M , se puede apostar, si la representacion de casos lo permite, por construir un nuevo prototipo o esquema que generalice el conocimiento contenido en los dos casos. Este prototipo tendra ndices mas generales que los casos de los cuales se obtiene. Por tanto, sera aplicable al menos, la misma cantidad de veces que hasta el momento lo es C M .

© Los autores, 1998; © Edicions UPC, 1998.

276

Aprendizaje Automatico

8.6.2 Aprendizaje de errores Cuando se ha recuperado un caso de memoria, adaptado su solucion y esta ha fracasado es necesario aprender las condiciones que han dado lugar al fracaso para que no se repita. Existen dos ocasiones basicas para aprendizaje: 1. Aprender el error 2. Actualizar los ndices para no volver a recuperar el caso en las mismas circunstancias

Aprender el error El aprendizaje del error consiste en relacionar las caractersticas causantes del error y el caso fracasado, almacenando el caso indexado por estas. De esta manera, cuando la misma combinacion de caractersticas se de en un nuevo caso, el caso erroneo se activara y prevendra del error. Si existe en memoria un error similar al caso erroneo actual, y no se ha activado, se puede proceder con dos actuaciones:

 actualizar (mejorar) los ndices del caso en memoria para que se active la proxima vez,

y  generalizar las caractersticas (y consecuentemente actualizar tambien los ndices) de los dos casos, construyendo un prototipo de caso erroneo mas general.

Actualizacion de ndices Si la solucion ha sido erronea signi ca que el caso recuperado a partir de la librera de casos no ha sido el correcto. La recuperacion de casos se basa en la funcion de similitud que, a su vez, se basa en los ndices o caractersticas de los casos. Por lo tanto, con la actualizacion de los ndices se espera obtener un mejor rendimiento del sistema en el futuro. Los ndices involucrados en la actualizacion corresponden a las caractersticas que aparecen en el caso actual C pero es necesario distinguir entre:

 ndices que han recuperado un caso C E , del cual se ha adaptado la solucion al caso actual C y ha resultado erronea; y  ndices que no han recuperado el caso deseado C D .

Existenndices comunes a C E y a C D , por lo que disminuir la in uencia de todos losndices que han recuperado C E puede no ser una estrategia correcta. Por esta razon es necesario de nir heursticas o mecanismos que determinen que ndices deben modi carse. As, se realizan dos tipos de actualizaciones:

 unas que aumentan la importancia de unndice, haciendolo mas espec co, o asociandole un peso mayor; y

© Los autores, 1998; © Edicions UPC, 1998.

277

Aprendizaje basado en casos

 otras que disminuyen la in uencia de un ndice haciendolo mas general, o asociandole un peso menor.

En el ejemplo de los juguetes se observa que el caso que se tena que haber recuperado de memoria, C D , es COCHE; mientras que el caso que se ha recuperado erroneamente, C E , es PELOTA. Es facil observar que si se aumenta la importancia de la caracterstica piezaspeque~nas y se disminuye la importancia de las caractersticas edad y material-pral, en una situacion futura se evitara repetir el error.

8.7 Sistemas basados en casos clasicos Entre todos los sistemas basados en casos que se han desarrollado hasta el momento, se ha hecho un estudio de acuerdo con la importancia y trascendencia que han tenido en el desarrollo de este paradigma de la IA, y han sido seleccionados CASEY, PROTOS, CHEF, SMART y JULIA para ser tratados en este captulo. A continuacion se proporciona una breve descripcion de ellos basada en su funcionalidad, la representacion de casos que utilizan, y la implementacion particular que hace cada sistema de las diferentes etapas del RBC. Una descripcion, al nivel de conocimientos, de algunos de estos sistemas se puede encontrar en [ARME94].

8.7.1 Diagnostico: CASEY Descripcion y funcionamiento CASEY [KOTO88a, KOTO88b, KOTO88c] es un sistema basado en casos para el diagnostico de enfermedades. CASEY se ha integrado con un sistema de razonamiento causal4 . El razonamiento basado en casos proporciona e ciencia, mientras que el razonamiento causal proporciona robustez (degradacion gracil de las respuestas del sistema, exibilidad ante situaciones no anticipadas, facilidad de explicacion, facilidad de mantenimiento, etc.). El componente causal del sistema integrado es el programa Heart Failure. Por un lado, CASEY resuelve problemas mediante el uso de experiencias anteriores. Solamente cuando las experiencias precedentes no pueden ser utilizadas para determinar la solucion de un problema, CASEY utiliza Heart Failure para buscar una solucion. Heart Failure es un sistema pensado para la diagnosis de enfermedades coronarias que posee un modelo del dominio basado en hechos ( ndings, datos observables y valores de entrada) y estados. Los hechos y los estados estan asociados, y entre los estados se establecen relaciones causales. Heart Failure resuelve un problema mediante la construccion de una explicacion (como por ejemplo la de la gura 8.7) en la que un conjunto de estados justi ca la presencia de hechos anormales en un caso. A partir de la explicacion, Heart Failure encuentra una solucion (esto es, un diagnostico).

Librera de casos. En CASEY los casos (ver gura 8.8) estan representados por los hechos, las soluciones y los estados relacionados causalmente con los hechos anormales (esto es, estados

4 Un modelo causal codi cala estructuray el comportamientode un sistema haciendoexplcitas las relaciones (causales, asociativas, de especializacion, etc.) entre los componentes del sistema. En un modelo causal no aparecen conocimientos de control, sino que los conocimientos se representan tpicamente como redes de descripciones estructurales.

© Los autores, 1998; © Edicions UPC, 1998.

278

Aprendizaje Automatico

SALIDA CARDIACA LIMITADAAFECCIO N VA LVULA AO RTICA

? dispnea en esfuerzo

K

R ESTENOSIS AORTICA  +

ALTA RESIST.TUBO SALIDA FIJADA

= ? ? ANGINA INESTABLE ?

DE FICIT GENERAL DE FLUJO

R

EXPULSIO N LENTA

?

impulso apex prolongado

dolor de angina de pecho inestable Figura 8.7: Explicacion causal generada por Heart Failure para un diagnostico. que justi can la presencia de anomalas). Los casos en memoria estan indexados por los hechos y las soluciones. Cada hecho tienen asociada una importancia que indica el numero de veces que aparece el hecho dando soporte a un estado determinado.

Recuperacion. Los pasos que realiza un sistema basado en casos, es decir, la recuperacion

de un caso de memoria, la adaptacion, la evaluacion de las soluciones y el almacenamiento, se particularizan en CASEY por ser metodos basados en conocimientos causales. La funcion de similitud que emplea para recuperar los casos de memoria se basa en el numero de caractersticas relacionadas causalmente en el caso de memoria (C M ), la importancia de las caractersticas relacionadas, las caractersticas anormales que presenta el caso actual (C), y el numero total de caractersticas que C M y C tienen en comun. Una vez se recuperan casos de memoria, CASEY evalua las diferencias entre un caso de memoria C M y el caso actual C en un proceso que se llama justi cacion y que se basa en un conjunto de principios de evidencia. Por ejemplo, el principio de exclusion indica que un estado de C M no se puede transferir a C si existe alguna caracterstica en C que lo hace incompatible. En la justi cacion se distinguen diferencias insigni cantes y diferencias signi cantes. Una diferencia insigni cante es aquella que no afecta la explicacion de los estados que aparecen en C M . Por ejemplo, supongamos que tenemos un nuevo caso C con los datos: f dispnea-en-esfuerzo, dolor-angina-de-pecho-inestable, pulso-con-ritmo-lento g que soportan  el estado EXPULSION-LENTA. Este caso se diferencia del caso C representado en la gura 8.7 por los hechos impulso-apex-prolongado y pulso-con-ritmo-lento. Los datos del caso C M y C son diferentes pero el caso C, de acuerdo con los conocimientos causales, tambien soporta  el estado EXPULSION-LENTA con los hechos pulso-con-ritmo-lento. Por tanto, a pesar de que los hechos no son los mismos en ambos casos, los estados soportados en C M continuan siendo validos en C. Una diferencia signi cativa ocurre cuando no existe ningun hecho de C que soporte un estado de C M .

© Los autores, 1998; © Edicions UPC, 1998.

279

Aprendizaje basado en casos

(defpaciente "Newman" HISTORIA (edad 65) (sexo hombre) (dispnea en-esfuerzo) (ortopnea ausente) (dolor-pecho anginal) (anginal-entre-horas inestable) (sncope/cerca-sncope en-esfuerzo) (resfriado ausente) DATOS-LABORATORIO (ekg lvh seno-normal) (cxr calci cacion) (calci cacion mitral valvula-aortica) SIGNOS-VITALES (presion-sangunea 138 80) (ritmo-cardaco 90) (monitor-arritmia normal) (resp 20) (temp 98.4) EXAMEN FISICO (abdomen normal) (pulso bajo) (extremidades normales)) Figura 8.8: Descripcion de un paciente.

© Los autores, 1998; © Edicions UPC, 1998.

280

Aprendizaje Automatico

Adaptacion. Algunas diferencias son reparables. La adaptacion de las soluciones consiste

en aplicar a las discrepancias un conjunto de estrategias de reparacion. Por ejemplo, la regla elimina estado, elimina un estado de C M no soportado por ninguna caracterstica de C. Existen otras reglas que incluyen estados, relaciones, etc. entre elementos de C hasta obtener una explicacion que justi ca los hechos anormales de los casos con unos determinados estados.

Evaluacion. Una vez se ha resuelto un nuevo caso, se incorpora en memoria. No existe

una etapa diferenciada de evaluacion de la solucion, ya que Koton confa en la justi cacion elaborada por las diferencias entre los casos para decidir la validez de la solucion, esto es, el proceso de justi cacion asegura que los conocimientos causales dan soporte a la solucion adaptada (ver similitud con el metodo EBL descrito en el captulo 4).

Aprendizaje. El aprendizaje consiste en la modi cacion de la importancia de los hechos y

en la construccion de generalizaciones. La importancia de un hecho se ve aumentada cada vez que el hecho aparece en un nuevo caso (por tanto, la importancia de las caractersticas mide la tipicalidad de estas). La incorporacion de un nuevo caso en memoria puede resultar en la generalizacion de mas de un caso. La generalizacion permite agrupar caractersticas comunes a diferentes casos. Las generalizaciones hacen posible que CASEY genere explicaciones parciales cuando la informacion de un problema es incompleta. CASEY utiliza todas las caractersticas del caso para realizar generalizaciones, razon por la cual puede considerar caractersticas no re ejadas en el modelo causal. Esto signi ca que CASEY extiende el modelo causal a otras caractersticas que puedan aparecer en casos futuros.

Discusion CASEY se ha probado experimentalmente en la diagnosis de enfermedades coronarias. Para evaluar la correccion de CASEY se han comparado las soluciones de los casos con las soluciones que hubiese proporcionado Heart Failure basandose en una busqueda exhaustiva de todos los estados posibles. Los casos disponibles han sido 45 para el diagnostico de 15 enfermedades diferentes. Y el porcentaje de exito en CASEY es del 86%, es decir, el 86% de los casos obtienen la misma solucion que Heart Failure, a excepcion de algunas caractersticas que no se pueden justi car. La e ciencia de CASEY se ha evaluado por la comparacion entre el numero de estados generados en CASEY y el numero de estados generados por Heart Failure. CASEY siempre genera menos estados, razon por la cual resulta mas e ciente. La aportacion importante de CASEY es, pues, que ha demostrado la e ciencia del sistema basado en casos respecto al razonamiento causal: cuantos mas casos se han procesado, menos esfuerzo es necesario para resolver nuevos casos, ya que es mas probable encontrar un caso muy semejante en memoria y no es necesario recurrir a Heart Failure (esto es, a la busqueda exhaustiva de soluciones). Es necesario observar, sin embargo, que no se conoce con detalle el proceso de evaluacion experimental realizado en CASEY (como por ejemplo, el orden de los ejemplos, complejidad de los casos, etc.) Una caracterstica preocupante en el aprendizaje de la importancia de las caractersticas es que, como el autor de CASEY apunta, puede provocar sesgos (biases). Por ejemplo, si siempre se procesa un mismo tipo de caso, las caractersticas presentes en los casos adquiriran una

© Los autores, 1998; © Edicions UPC, 1998.

281

Aprendizaje basado en casos

importancia injusti cadamente relevante. El motivo de este desajuste es que la importancia de los ndices en CASEY se basa en la tipicalidad de los casos.

8.7.2 Clasi cacion: PROTOS Descripcion y funcionamiento PROTOS [BARE89, BARE87, PORT86] es un aprendiz que, mediante el establecimiento de un dialogo con un maestro, aprende conocimientos de un dominio. En particular, PROTOS aprende una de nicion extensional de conceptos polimor cos (conceptos difciles de describir por un conjunto enumerado de caractersticas) a partir de casos proporcionados por un maestro. Esto quiere decir que, como resultado del aprendizaje, se obtiene una de nicion implcita del concepto (categora) en un conjunto de ejemplares (un ejemplar es un caso retenido en memoria). Despues de realizado el aprendizaje, PROTOS debe ser capaz de clasi car un concepto nuevo a partir de la lista de sus caractersticas.

Librera de casos. Un caso esta constitudo por un identi cador, un conjunto de carac-

tersticas y el identi cador de la categora (concepto) a la que pertenece. PROTOS organiza los casos en memoria en una red. En cada nodo de la red hay una categora, un ejemplar o una caracterstica ( gura 8.9). Los ndices se construyen a partir de las explicaciones proporcionadas por un maestro y justi can el hecho de que una caracterstica pertenezca a un ejemplar o categora. La memoria de PROTOS es, pues, una red de categoras donde se de nen cuatro mecanismos de indexacion ( gura 8.10):

 Remindings: son ndices que relacionan caractersticas con ejemplares o categoras a

las que pertenecen (por ejemplo, en la gura 8.10 asiento es un reminding de silla).  Restricciones (censors): son ndices entre caractersticas y categoras a las que la caracterstica no pertenece (exclusion mutua entre una caracterstica y una categora).  Prototipicalidad: son ndices de frecuencia con los que un ejemplar aparece como miembro de una categora.  Diferencias: sonndices entre ejemplares de una misma categora (intracategora) o entre categoras (intercategora) y relacionan las caractersticas diferentes entre ejemplares o categoras. Cadandice tiene asociada una importancia en la que se re eja la certeza con la que se establece el enlace entre, por ejemplo, una caracterstica y un ejemplar o categora.

Recuperacion. El proceso de razonamiento consiste en interpretar un caso nuevo y clasi-

carlo. La clasi cacion consta de dos etapas: la formacion de hipotesis y la con rmacion de estas. En la formacion de hipotesis se recuperan categoras de la memoria mediante los remindings y las restricciones a partir de las caractersticas del nuevo caso. Entre las categoras

© Los autores, 1998; © Edicions UPC, 1998.

282

Aprendizaje Automatico

hecho-de

ejemplar = silla1

= metal 

?

silla

 jejemplar silla2

~

funcion hecho-de

U

ruedas N asiento ? maderaR pedestal pies(4) brazo respaldo funcion permite especializ. 6 ? permite espureo ? R ? soporte lateral asoc. - aguanta(persona) 6permite especializ. U especializ. - material rgido  soporte de asiento especializ. Figura 8.9: Conocimientos del dominio en PROTOS.

asiento

? )

respaldo

silla

ejemplar ejemplar ) diferencia(respaldo,pedestal) z silla1 - silla2  I diferencia(pies(4)) 6 brazo pedestal pies(4) Figura 8.10: Indices para la recuperacion de ejemplares.

© Los autores, 1998; © Edicions UPC, 1998.

283

Aprendizaje basado en casos

recuperadas, PROTOS selecciona solamente un subconjunto de los ejemplares de cada categora teniendo en cuenta su prototipicalidad. Entonces, los ejemplares recuperados se ordenan de acuerdo al grado de importancia de sus remindings. La con rmacion de hipotesis se basa en un proceso de comparacion de patrones (pattern matching) basado en los conocimientos sobre el caso y los ejemplares recuperados. En este proceso de comparacion se elabora una explicacion que justi ca que el caso corresponde al ejemplar recuperado, Er , usando el medodo de aprendizaje basado en explicaciones (EBL, ver captulo 4). Se parte de una caracterstica de un ejemplar y se recorren los enlaces hacia atras desde la caracterstica hasta encontrar la caracterstica del caso. La cadena de enlaces que se ha recorrido constituye la explicacion de como el caso implica al ejemplar. La calidad e importancia de los enlaces recorridos determinan, al mismo tiempo, el grado de similitud entre el caso y el ejemplar. Si en la elaboracion de las explicaciones alguna de las caractersticas F = ff1 ; : : :; fng del caso no corresponde al ejemplar Er (esto es, ocurre un matching imperfecto), PROTOS puede utilizarndices diferencia para buscar ejemplares proximos a Er que presenten alguna de estas caractersticas fi (la estrategia de busqueda de ejemplares en memoria es, pues, hill-climbing).

Adaptacion. Una vez se ha recuperado el ejemplar mas adecuado, se asocia su solucion, esto es, la clase a la que pertenece, al caso actual.

Evaluacion. Los casos resueltos por PROTOS son evaluados por un experto humano, su

maestro, que con rma o no la solucion generada para el problema actual. La evaluacion es, por tanto, un proceso externo a PROTOS.

Aprendizaje. PROTOS aprende a partir del fracaso, es decir, cuando no existe ningun ejemplar en memoria similar al caso actual o cuando clasi ca erroneamente un caso. Un fracaso proporciona cuatro ocasiones de aprendizaje:

1. Aprendizaje de ejemplares: cuando un caso no se puede clasi car porque no existe ningun ejemplar similar en memoria, se retiene el caso conviertiendose en un nuevo ejemplar. Un caso se considera similar a un ejemplar en memoria si presenta todas las caractersticas del ejemplar excepto aquellas que se consideren de poca importancia o de importancia irrelevante. En cualquier circunstancia, PROTOS pregunta al maestro sobre la conveniencia de la creacion de un nuevo ejemplar, y es este quien nalmente decide o no retener el nuevo caso en memoria. 2. Generalizaciones: cuando un caso no se retiene en memoria porque es muy similar a un ejemplar, entonces se generaliza el ejemplar. La generalizacion se realiza bien por la extension de los conocimientos del dominio a las caractersticas de nuevo caso o bien por la modi cacion de la importancia de las caractersticas. 3. Aprendizaje de conocimientos del dominio: cuando el matching es imperfecto (pero correcto) se pueden adquirir explicaciones del maestro para relacionar las caractersticas del caso ausentes en el ejemplar recuperado. Aprendiendo explicaciones, PROTOS aprende conocimientos del dominio.

© Los autores, 1998; © Edicions UPC, 1998.

284

Aprendizaje Automatico

4. Aprendizaje de ndices: cuando PROTOS clasi ca erroneamente un caso, entonces aprende ndices o modi ca su importancia para adecuar la memoria y evitar la recuperacion del ejemplar erroneo en un futuro. El aprendizaje de la importancia de las caractersticas y el aprendizaje de ndices condicionan en gran medida la e ciencia del sistema. La importancia de las caractersticas de un ejemplar se determina cuando este se a~nade a una categora y se basa en el proceso de matching que genera la explicacion que justi ca porque una caracterstica forma parte de un ejemplar. La explicacion es evaluada de acuerdo con unas heursticas y, entonces, PROTOS asigna a la caracterstica un valor de importancia entre 0 y 1 (normalmente los valores iniciales son bajos). Cuando PROTOS fracasa en la clasi cacion de un caso, se revisa la importancia de las caractersticas del ejemplar que han dirigido la clasi cacion. De hecho, la modi cacion de las caractersticas se realiza caracterstica a caracterstica y bajo el asesoramiento del maestro. El maestro proporciona la importancia de las caractersticas cali candolas con los valores siguientes: necesaria, alta, moderada, baja y espuria. PROTOS transforma estos valores en una certeza numerica. Cuando una caracterstica se reconoce en un ndice de tipo diferencia, es decir, como elemento discriminativo entre dos ejemplares, entonces la importancia de la caracterstica se incrementa (i.e., se considera mas relevante). El aprendizaje de los diferentes tipos de ndices (remindings, restricciones, prototipicalidad y diferencias) y los grados de importancia correspondientes tienen lugar en diferentes circunstancias. Los remindings se aprenden analticamente de los casos de entrenamiento y se modi can cuando causan una clasi cacion incorrecta. La utilizacion de un conjunto de heursticas gua el aprendizaje de remindings. Cuando un reminding recuerda un ejemplar equivocadamente, entonces la importancia del reminding se decrementa. Cuando un reminding indexa adecuadamente un ejemplar, entonces la importancia del reminding se incrementa. Si el valor de la importancia de un reminding se decrementa a menudo, el reminding puede llegar a eliminarse. Las restricciones se aprenden por indicacion del maestro. La importancia de las restricciones oscila entre debil, moderada, fuerte y absoluta. Una restriccion con importancia absoluta, puede provocar la eliminacion de los remindings implicados con la restriccion. La prototipicalidad de un ejemplar esta relacionada con la similitud de un ejemplar a los miembros de la categora a la cual pertenece. Cada vez que un ejemplar se utiliza para clasi car un caso, se modi ca la prototipicalidad del ejemplar respecto a la categora que representa. Los ndices diferencia se aprenden como consecuencia de una clasi cacion incorrecta en el proceso de resolucion de un caso (ndice intercategora) o como consecuencia de un matching imperfecto (ndice intracategora). En cualquier caso, PROTOS aprende por el establecimiento de un dialogo con el experto.

Discusion El sistema PROTOS se ha aplicado en audiloga para el aprendizaje de transtornos en el odo. PROTOS se ha evaluado experimentalmente con 200 casos de entrenamiento y 26 casos de test. Todos los casos de test se han resuelto correctamente (i.e. el diagnostico obtenido ha sido aceptado por el maestro). La cantidad de ejemplares recuperados de memoria aumenta con el numero de casos de entrenamiento. Pero de acuerdo con lo que sus propios autores indican, esto es consecuencia de que los 50 ultimos casos de entrenamiento son casos atpicos. Con ello se puede observar que PROTOS, como la mayoras de los sistemas de aprendizaje, es

© Los autores, 1998; © Edicions UPC, 1998.

285

Aprendizaje basado en casos

susceptible al orden de los casos de entrenamiento. Sin embargo, una vez mas, no esta claro cual ha sido la metodologa de la evaluacion experimental del sistema. El aprendizaje de PROTOS esta fuertemente sujeto al dialogo con el experto. Respecto al aprendizaje de la importancia de las caractersticas, es interesante destacar la contribucion negativa de la importancia de estas (ver [MALL89]). Esto es, la importancia de las caractersticas se ve disminuda mas que aumentada. Generalmente se asigna un valor bajo a una importancia de una caracterstica y, dado que el mecanismo de PROTOS es e ciente (PROTOS fracasa pocas veces en la clasi cacion de un caso), entonces existen pocas posibilidades de modi car la importancia de las caractersticas (i.e. aumentarla).

8.7.3 Plani cacion: CHEF y SMART La utilizacion del razonamiento basado en casos para la resolucion de problemas de plani cacion cuenta con precedentes importantes en los sistemas CHEF y SMART.

CHEF Descripcion y funcionamiento. CHEF [HAMM89] es el primer sistema donde se integra

el razonamiento basado en casos y la plani cacion, resultando la plani cacion basada en casos. CHEF esta dise~nado para el aprendizaje de recetas de cocina china: a partir de los ingredientes y el tipo de plato que se desea cocinar, CHEF es capaz de construir una receta (plan) basandose en recetas realizadas anteriormente.

Librera de casos. Como sistema basado en casos, lo mas destacable de CHEF es su peculiar

organizacion en la memoria de las experiencias anteriores (casos). CHEF estructura los casos en tres organizaciones dinamicas de memoria (organizaciones actualizables con la presencia de nuevas experiencias, esto es, nuevos casos) y una organizacion estatica (no modi cada por nuevas experiencias). Entre las dinamicas se encuentran una memoria de planes, una memoria de errores (fracasos) y una memoria de modi caciones. La memoria estatica esta constituida por un conjunto de estrategias de reparacion de planes. Las diferentes memorias comparten estructuras de datos como son los objetos, estados, objetivos, operadores (que en CHEF se llaman pasos, steps) y los planes. Los objetos representan cosas del mundo como los ingredientes y los utensilios de cocina. Los objetos tienen diferentes estados o caractersticas: textura, gusto, etc. Los objetivos se re eren al estado que se desea conseguir de los objetos, como por ejemplo un pollo crujiente o un soue esponjoso. Los pasos son un conjunto de precondiciones mas un conjunto de acciones. Cada plan o caso ( gura 8.11) es un conjunto de pasos, mas un conjunto de condiciones que los hacen posible (ingredientes). Existen diferentes tipos de enlaces entre las diferentes estructuras, como por ejemplo: entre un paso y los objetos que modi ca, entre estados y caractersticas deseables de los objetos, etc. En la memoria de planes se organizan los planes de acuerdo con el tipo que tienen asociado y los objetivos que solucionan. Es decir, cada plan debe ser de un tipo predeterminado, como por ejemplo un plan de frituras, soues, etc. El tipo de plan sirve para indexar los planes en la memoria conjuntamente con los objetivos que satisface el plan. Para manipular la memoria de

© Los autores, 1998; © Edicions UPC, 1998.

286

Aprendizaje Automatico

(def: rec brecol-con-costillas (ingredientes ingr1 (costillas lb .5) ingr2 (salsa-soja cucharada 2) ingr3 (vino-arroz cucharilla 1) ingr4 (maicena cucharada .5) ingr5 (azucar cucharilla 1) ingr6 (brecol lb 1) ingr7 (pimiento-rojo piezas 6)) (actions acc1 (cortar objeto (ingr1) tama~no (grueso)) acc2 (marinar objeto (resulta acc1) en (& (ingr2) (ingr3) (ingr4) (ingr5)) tiempo (20)) acc3 (cortar objeto (ingr6 tama~no (grueso)) acc4 (freir objeto (&result acc2) (ingr7)) tiempo (1)) acc5 (a~nadir objeto (result acc3) a (result acc4)) acc6 (freir objeto (result acc5) tiempo (2))) (stile fritura))

Figura 8.11: Plan (receta) para cocinar brecol con costillas. (a~nadir:crit gamba unida (gamba *nuevo-tem*) pasos ((antes (paso-coccion objeto *nuevo-tem*) hacer (quitar-cascara objeto *nuevo-tem))))

Figura 8.12: Regla de aplicacion espec ca sobre el ingrediente gamba. planes, CHEF dispone de unos conocimientos generales (role speci cations) que determinan los tipos de objetivos que pueden a~nadirse a un tipo de plan y los resultados que se esperan de la ejecucion de este. En la memoria de errores se organizan, como su propio nombre indica, los errores, pero tambien una explicacion causal del error y las caractersticas predictivas del error (caractersticas que se encontraban en memoria cuando el error se produjo). Un error es un objetivo no consolidado en un plan o un estado no deseado que ha surgido en la ejecucion de un plan. Los errores se reconocen por la activacion de las caractersticas que los predicen y que activan, a la vez, planes. La memoria de modi caciones la constituyen una tabla de reglas y un conjunto de crticos. La tabla de reglas esta indexada por los tipos de planes y objetivos, y en cada celda se situa el conjunto de pasos necesarios para a~nadir un objetivo a un plan. Los crticos son reglas de aplicacion espec ca sobre objetos ( gura 8.12). La memoria de reparaciones organiza estrategias de reparacion de planes bajo descripciones de los diferentes problemas que reparan. La organizacion de esta memoria es realmente compleja. Nos bastara saber que a partir de una explicacion causal de un fracaso (error) es posible

© Los autores, 1998; © Edicions UPC, 1998.

287

Aprendizaje basado en casos

recuperar una estrategia que repara el plan en curso.

Recuperacion. CHEF recupera un caso de la memoria de planes a partir del tipo de plan

que se pretende construir (por ejemplo una fritura) y los ingredientes (por ejemplo ternera y patatas). A partir de los ingredientes y el tipo, CHEF deduce los objetivos a satisfacer (como por ejemplo, obtener unas patatas crujientes). Con los objetivos y el tipo de plan, CHEF accede a la memoria de planes y recupera un plan del mismo tipo donde todos los objetivos se consolidan.

Adaptacion. Una vez recuperado un plan, CHEF lo adapta al problema actual a partir

de la memoria de modi caciones. As, si falta algun ingrediente se accede a la memoria de modi caciones para incluir el tratamiento oportuno en el plan recuperado.

Evaluacion. Una vez adaptado el plan, CHEF lo almacena en la memoria de planes. A

continuacion, el plan es ejecutado por un simulador que utiliza un conjunto de reglas de inferencia construdas para este proposito. Si en un paso aparece algun error no esperado, se considera que el plan es erroneo, esto es, que fracasa.

Aprendizaje. El fracaso de los planes proporciona a CHEF la oportunidad de aprender.

CHEF es capaz, a partir de las mismas reglas que el simulador utiliza, de generar una explicacion causal del mal funcionamiento del plan. Una vez conocida la causa del fracaso del plan, CHEF utiliza la memoria de reparaciones para recuperar una estrategia de reparacion que repare el plan. Este nuevo plan se almacena en la memoria de planes. La explicacion causal del fracaso tambien se utiliza para actualizar la memoria de errores y as evitar que se vuelva a repetir el error en una situacion similar. De esta manera, cuando CHEF resuelve un problema nuevo, accede a la memoria de errores y averigua si existe la posibilidad de que se produzca algun error ocurrido en una experiencia anterior con los mismos datos (esto es, ingredientes y tipos de plan). Si es as, se genera un objetivo nuevo (prediccion) que se a~nade a la lista de objetivos del problema a resolver. Resolviendo todos los objetivos se esta evitando a la vez el fracaso del plan. Es importante destacar que todos los planes que se almacenan en CHEF tienen los ndices generalizados. Esto quiere decir que cualquiera de los ingredientes de las recetas se generalizan antes de ser almacenados. Por ejemplo, una receta con ternera y brecol, estara almacenada bajo los ndices carne y verduras. En la recuperacion de una receta, tambien se accede a la memoria de planes mediante un proceso de abstraccion de los ingredientes. Por ejemplo, si el ingrediente es coli or se accede a la memoria por el ndice verdura, y a partir de estos se deducen las caractersticas deseables (textura, etc.) o objetivos.

Discusion. CHEF es un sistema de plani cacion basada en casos donde la idea principal es la reusabilidad de los planes ejecutados en experiencias anteriores mas que la construccion de planes nuevos. El aprendizaje en CHEF se realiza cuando un plan resulta erroneo en su ejecucion. Los errores se organizan en la memoria para tratar de evitarlos en el futuro. CHEF, sin embargo, no aprende a partir de planes exitosos.

© Los autores, 1998; © Edicions UPC, 1998.

288

Aprendizaje Automatico

La aportacion principal de CHEF fue la de integrar por primera vez la plani cacion y el razonamiento basado en casos. Asimismo, la representacion de los conocimientos en CHEF es muy compleja, como lo demuestran sus cuatro memorias (tres dinamicas y una estatica), mas otros tipos de conocimientos (crticos, reglas de simulacion, etc.) que intervienen en el proceso de resolucion de un problema nuevo. Sin embargo, el dominio de aplicacion de CHEF es un dominio particular y no se han proporcionado curvas de aprendizaje del coste de la resolucion de problemas. Toda la funcionalidad de CHEF esta basada en ejemplos particulares. El simulador incorporado en CHEF para evaluar los planes que se construyen ha sido eliminado en los sistemas sucesores TRUCKER y RUNNER [HAMM88]. En estos sistemas la ejecucion de los planes se monitoriza y se permite la suspension y continuacion de los objetivos cuando las circunstancias lo requieren. Esta monitorizacion de la ejecucion no esta vinculada a la adecuacion de los cambios que se puedan producir en el entorno (como en los plani cadores reactivos, vease [MITC90]), sino que se utiliza para llevar a cabo aquellas partes de los planes que no han podido satisfacerse en el momento de su construccion y que se aplazan hasta que las condiciones que permiten aplicarlas se cumplan.

SMART Descripcion y funcionamiento SMART [VELO92] es un sistema basado en la experi-

encia pensado para hacer mas e ciente la plani cacion en PRODIGY (speed-up learning). PRODIGY es una arquitectura de proposito general donde la representacion del conocimiento esta constituida por operadores, reglas de inferencia y reglas de control (para mas informacion sobre PRODIGY ver la seccion 4.5.4 del captulo 4). SMART interacciona con NoLimit, el plani cador no-lineal de PRODIGY, en la resolucion de problemas. NoLimit resuelve un problema por la aplicacion de operadores, reglas de inferencia y reglas de control mediante el analisis de medios y nes (means-ends analysis) y encadenamiento hacia atras (backward chaining) de las reglas y/o operadores. Dado un estado inicial E y los objetivos, NoLimit aplica operadores o reglas a E, transformandolo en un nuevo estado E 0 que se acerca mas a un estado nal donde todos los objetivos se satisfacen. La resolucion de un problema es, pues, la secuencia de operadores necesaria para llegar del estado inicial al estado nal. En la resolucion de un problema se producen decisiones sobre la aplicabilidad de los operadores o reglas, y NoLimit desarrolla un arbol donde se recogen todas las decisiones que se toman ( gura 8.13). Para empezar a resolver un problema se de ne un estado inicial y los objetivos que se quieren conseguir ( gura 8.14), que constituyen la raz del arbol de busqueda. Cada decision que se realiza durante la resolucion de un problema da lugar a un nuevo nodo. Es decir, para cada operador, regla de inferencia o regla de control que NoLimit aplica o cada vez que NoLimit se encuentra una instancia de las precondiciones de los operadores (o regla), se crea un nuevo nodo. Siempre que se llegue a un estado en el que no se pueda continuar la resolucion de un problema (impasse), NoLimit puede recuperar un estado anterior gracias a un sistema de mantenimiento del razonamiento (reason maintenance system) incorporado en la arquitectura de PRODIGY. NoLimit, como plani cador no lineal5, trabaja con un conjunto de objetivos en un mismo ciclo.

5 Un plani cador no lineal es aquel que resuelve de forma simultanea diferentes objetivos con el proposito de controlar las interacciones entre ellos. En contrapartida, un plani cador lineal construye un plan solucionando de forma secuencial cada uno de los objetivos.

© Los autores, 1998; © Edicions UPC, 1998.

289

Aprendizaje basado en casos

cn0:

(realizado)

cn1:

(*terminar*)

cn2: cn3: cn4: cn5: cn6: cn7: cn8: cn9: cn10: cn11: cn12: cn13: cn14: cn15: cn16: cn17:

? ? (cerca-de robot caja3) ? (ir-hacia caja3) ? (en robot hab4) ? (atravesar puerta34) ? (en robot ha3) ? (atravesar puerta13) ? (ATRAVESAR puerta13) ? (puerta-ab puerta34) ? (abrir-puerta puerta34) ? (ABRIR-PUERTA puerta34) ? (ATRAVESAR puerta34) ? (puerta-cer puerta34) ? (cerrar-puerta puerta34) ? (CERRAR-PUERTA puerta34) ? (IR-HACIA caja3) ? (*terminar*)

? ? (puerta-ab puerta24) ? (abrir-puerta puerta24) ? (no (puerta-cer-llave puerta24)) ? (atravesar puerta24)

Fracaso: no operadores aplicables

? ? (puerta-cer puerta34) ? (cerrar-puerta puerta34) ? (IR-HACIA puerta34) ? (IR-HACIA caja3)

Fracaso: bucle

Figura 8.13: Traza generada por NoLimit durante la resolucion de un problema.

© Los autores, 1998; © Edicions UPC, 1998.

290

Aprendizaje Automatico

R

12

12

34

34

(a) (en robot hab1) (en caja2 hab3) (puerta-ab puerta12) (puerta-cer puerta34) (en caja1 hab1) (en caja3 hab4) (puerta-ab puerta13) (puerta-cer-llave puerta24)

R

(b) (& (puerta-cer puerta34) (cerca-de robot caja3))

Figura 8.14: Plani cacion en PRODIGY (a) Estado inicial. (b) Objetivo. Wi,G



Wf,S

Wi,G

NoLimit

 Analogos Feedback

SMART

-

Figura 8.15: Interaccion entre NoLimit y SMART. Ademas, NoLimit sigue una estrategia de compromiso casual (casual commitment strategy) que trata de tomar decisiones (que objetivo expandir, que operador elegir, que asignaciones aplicar, etc.) mediante el uso de reglas de control, mediante la intervencion del usuario o mediante la interaccion con SMART ( gura 8.15). NoLimit puede interaccionar con SMART para obtener analogos (experiencias o casos anteriores) que le permitan tomar decisiones siguiendo las que han sido tomadas en el analogo, y as evitar repetir los errores que puedan haberse cometido en experiencias previas. Si no es posible encontrar un analogo, entonces NoLimit resuelve el problema utilizando el resto de sus conocimientos.

Librera de casos. NoLimit proporciona una traza que contiene el arbol de busqueda de-

sarrollado para construir un plan. SMART utiliza las trazas ( gura 8.13) para generar casos ( gura 8.16). En los casos, SMART representa el camino de la solucion junto con anotaciones de los puntos de decisiones (esto es, los motivos y el contexto que han dado lugar a las decisiones, as como las alternativas inexploradas o abandonadas). Por ejemplo, la aplicacion de un

© Los autores, 1998; © Edicions UPC, 1998.

291

Aprendizaje basado en casos

operador O se registra como un nodo en el cual se almacena informacion sobre los operadores alternativos, los objetivos que se estan estudiando y los argumentos que justi can porque se aplica precisamente el operador O. SMART organiza los casos en memoria indexados por el estado inicial (constitudo por un conjunto de hechos) y los objetivos.

Recuperacion. Dado un problema nuevo P, se recupera de memoria un caso analogo haciendo uso de los datos del estado inicial y el objetivo. Para recuperar un analogo, SMART utiliza una medida de similitud basada en "huellas" (foot-print) y substituciones. Una huella de un objetivo la constituyen los hechos del estado inicial que son relevantes en la validacion del objetivo. El grado de similitud entre el problema actual P y un caso en memoria C, se determina por el numero de hechos que comparten las huellas de los objetivos comunes a P y C. Para comparar las huellas se utiliza el concepto de substitucion [MANY94]. Dados dos conjuntos de hechos F1 y F2 (huellas), se busca una sustitucion  que se aplica a F2 , y se cuenta el numero de hechos identicos entre F1 y F20 , siendo F20 el resultado de aplicar  a F2 . Por ejemplo, si F1 = f (dentro-de llave12 habitacion1), (dentro-de caja1 habitacion1) g, F2 = f (dentro-de llave13 habitacion4), (dentro-de llave14 habitacion2), (dentro-de caja53 habitacion4) g y  = f llave12/llave13, habitacion1/habitacion4, caja1/caja53 g, el grado de similitud es 2. Adaptacion. NoLimit utiliza el analogo para derivar analogicamente (ver el captulo 3) una

solucion. As, en lugar de generar un arbol de busqueda para el caso actual, se vuelve a generar el camino solucion del caso analogo, y en esta reconstruccion se veri ca que las condiciones que han dado paso a las decisiones en el analogo se cumplen para el caso actual. Si todas las justi caciones explicitadas en el analogo se satisfacen, el plan del analogo se copia directamente para resolver el caso nuevo. Si alguna condicion sobre algun operador no se cumple, entonces existen tres posibilidades: replani car el operador que fracasa, reestablecer las condiciones que faltan como objetivos anteriores o experimentar para justi car dichas condiciones con el modulo de aprendizaje por experimentacion de PRODIGY [CARB87].

Evaluacion. Si los objetivos del analogo no se cumplen para el caso actual, o si las justi caciones almacenadas en el caso recuperado no se satisfacen para el caso actual, signi ca que no ha sido adecuada su recuperacion. Es el plani cador NoLimit quien comprueba de nuevo las condiciones, y retorna, a manera de feedback el resultado a SMART.

Aprendizaje. El aprendizaje por la experiencia en SMART se produce con la incorporacion

de un caso nuevo resuelto por NoLimit (interaccionando o no con SMART) y consiste en la reorganizacion de la memoria. NoLimit proporciona un feedback en el que se registra cual ha sido la utilidad del analogo. La utilidad del analogo puede ser: 1. completamente su ciente: ha bastado copiar el plan del analogo para resolver el problema, 2. extensional: se ha copiado el plan del analogo y se ha extendido a~nadiendo algunos pasos mas, 3. localmente divergente: algunos pasos del analogo han sido invalidados, y

© Los autores, 1998; © Edicions UPC, 1998.

292

Aprendizaje Automatico

Tipo objetivo elegir-op objetivo elegir-op objetivo elegir-op objetivo elegir-op aplicar-op objetivo elegir-op aplicar-op aplicar-op objetivo elegir-op aplicar-op aplicar-op aplicar-op

# nodo cn0 cn1 cn2 cn3 cn4 cn5 cn6 cn7 cn8 cn9 cn10 cn11 cn12 cn13 cn14 cn15 cn16 cn17

:eleccion (realizado) (*terminar*) (cerca-de robot caja3) (ir-hacia caja3) (en robot hab4) (atravesar puerta34) (en robot hab3) (atravesar puerta13) (ATRAVESAR puerta13) (puerta-ab puerta34) (abrir-puerta puerta34) (ABRIR-PUERTA puerta34) (ATRAVESAR puerta34) (puerta-cer puerta34) (cerrar-puerta puerta34) (CERRAR-PUERTA puerta34) (IR-HACIA caja3) (*terminar*)

Elegir-op nodo cn5 :eleccion (atravesar puerta34) :op-alternativos-relevantes (((atravesar puerta24) (:no-ops-relevante (no (puerta-cer-llave puerta24))))) :porque-op ((funcion (adyacente hab3 hab4)) (adyacente hab3 hab4)) ((funcion (conecta puerta34 hab3 hab4))) :relevante-para cn4 (a)

:p cn1 cn3 cn5 cn5 cn1

:r cn0 cn2 cn4 cn6 cn9 cn13

Objetivo nodo cn13 :eleccion (puerta-cerrada puerta34) :objetivos-activos nil :ops-aplicables (((IR-HACIA caja3) (:estado-bucle))) :porque-subobjetivo nil :porque-objetivo nil :precond-de cn1 (b)

Figura 8.16: Representacion de un caso en el sistema SMART.

© Los autores, 1998; © Edicions UPC, 1998.

293

Aprendizaje basado en casos

4. globalmente divergente: el resolvedor de problemas ha tenido que realizar marcha atras en alguno de los pasos copiados del analogo. La utilidad del analogo consiste en que es una informacion utilizada para incluir el nuevo caso en memoria y ajustar los ndices de este. Esta parte del aprendizaje, sin embargo, no esta totalmente desarrollada en SMART.

Discusion SMART proporciona e ciencia a NoLimit. Los resultados obtenidos con SMART

indican que la utilizacion de experiencias anteriores permiten ahorrar a NoLimit hasta 20 veces el esfuerzo de busqueda. Posiblemente, estos resultados puedan ser mejorados cuando se termine el desarrollo del mecanismo de aprendizaje por la experiencia. SMART ha sido aplicado en problemas de laboratorio (toy problems) y en problemas reales, y se ha demostrado que funciona adecuadamente con un numero elevado de casos. Sin embargo hay cuestiones de las aplicaciones en el mundo real, como la informacion incompleta, incierta e imprecisa que no estan contempladas en la representacion del conocimiento en SMART. Incluir la manipulacion de este tipo de conocimiento es una cuestion pendiente de todos los sitemas basados en casos, en general, y de la mayora de los plani cadores.

8.7.4 Dise~no: JULIA Descripcion y funcionamiento JULIA [KOLO87] es un sistema de ayuda al abastecimiento de menus (catering). El objetivo principal del sistema es la obtencion de una comida. Este objetivo puede ser subdividido en diferentes partes, como por ejemplo: determinar el tipo de cocina, aperitivo, plato principal, y postre. A su vez cada subobjetivo puede dividirse en otros, como por ejemplo, el aperitivo se puede subdividir en encontrar el ingrediente principal, la manera mas adecuada de prepararlo, y nalmente buscar la receta. Para construir una solucion JULIA comparte una pizarra o blackboard con un conjunto de procesos: un sistema de satisfaccion de restricciones, un sistema de propagacion de restricciones, un sistema de reduccion del problema, un sistema de control conversacional, un plani cador de objetivos y por supuesto, un sistema basado en casos (ver gura 8.17). En la pizarra se escriben los datos correspondientes al caso actual, y en ella tambien se re eja el estado de los objetivos y subobjetivos del sistema en un momento dado. Cada proceso puede tomar de la pizarra la informacion que crea que pueda tratar y resolver, y a la vez introducir nuevos objetivos para que otros sistemas lo resuelvan. El RBC interviene en el dise~no de la comida como un proceso mas. As, por ejemplo, si en un determinado momento detecta un conjunto de restricciones que le recuerdan un caso anterior donde ya fueron tratadas, recupera el caso correspondiente y adapta la solucion al caso actual.

Librera de casos. Un caso esta representado mediante un frame, en donde cada slot repre-

senta una decision tomada a lo largo de su resolucion (ver gura 8.18). El tipo de informacion asociada a cada slot puede ser: su valor (la decision tomada), las alternativas existentes en

© Los autores, 1998; © Edicions UPC, 1998.

294

Aprendizaje Automatico

sistema de satisfaccion de  restricciones sistema de propagacion de restricciones sistema de reduccion del problema

-

Pizarra

controlador - conversacional - plani cador de objetivos

-

RBC

Figura 8.17: Componentes de JULIA el momento, las excludas, condiciones de la eleccion, metodo de inferencia aplicado (o regla), etc. Los casos se organizan por los objetivos y las restricciones que satisfacen.

Recuperacion. Como ya se ha mencionado, la recuperacion de casos es paralela a la reso-

lucion de un problema. La pizarra contiene informacion del caso actual en un momento dado. Con esta informacion se recuperan los casos de memoria que comparten los mismos objetivos y restricciones. Entre todos los casos recuperados se seleccionan aquellos que: 1) comparten el mayor numero de objetivos, y 2) comparten el mayor numero de restricciones y las mas importantes. Cuantos mas datos se conocen del caso actual, es posible encontrar casos mas espec cos que resulten mas e cientes para resolver el problema. Por esta razon la solucion al problema actual no se genera a partir de un solo caso, sino mediante un conjunto de casos.

Adaptacion. Dependiendo del grado de similitud con respecto al caso actual, se adapta una parte u otra del caso recuperado de memoria. As, por ejemplo, si el caso recuperado consiguio sus objetivos, se reexaminan las condiciones sobre las que se tomaron las decisiones y si se satisfacen para el caso actual, se adapta la solucion al caso nuevo. La adaptacion del caso puede llevarse a cabo de cuatro maneras diferentes: 1. 2. 3. 4.

transferir la solucion; transferir la solucion y modi carla de acuerdo con la diferencia existente entre los casos; transferir el metodo inferencial con el que se calculo la solucion del caso recuperado; crear una abstraccion de la descripcion de los dos casos, extenderla para adecuar la solucion del caso recuperado, y aplicarla nalmente sobre el nuevo caso para generar la solucion.

Si por el contrario, el caso fracaso, se adaptaran las partes del caso responsables del fracaso, con el n de evitarlo.

© Los autores, 1998; © Edicions UPC, 1998.

295

Aprendizaje basado en casos

Frame # Nombre: COMIDA80 Esun: () Categora: Individual Slots: RESULTADO-ACTUAL: CARACTER: (?ANFITRION ?INVITADOS ?PARTICIPANTES) RESTRICCIONES: () SLOTS-DEFINIDOS: NIL DESCRIPTOR: RESULTADO-ESPERADO: REPETICION: NIL OBJETIVOS: (<S-HAMBRIENTOS80> <E-SERVIDOS80>) INVITADOS: (<*JLK*S-PADRES>) ANFITRION: <*JLK*> ENCARGO: ((<SC-ENSALADA80> <SC-PLATO-PRINCIPAL80>)) PARTICIPANTES: (?ANFITRION ?INVITADOS) LUGAR: <*JLK*S-CASA> PASOS: (<SC-ENSALADA80> <SC-PLATO-PRINCIPAL80>) Figura 8.18: Representacion de un caso en JULIA.

Evaluacion. La evaluacion, como en la mayora de los sistemas de aprendizaje, reside

tambien en un maestro que le dictamina si la solucion ofrecida ha sido acertada o, por el contrario, erronea.

Aprendizaje. El aprendizaje consiste simplemente en recordar la nueva experiencia, para que sirva de precedente y haga mas e ciente la resolucion de problemas en un futuro. Sin embargo, para evitar que el sistema se colapse por una excesiva acumulacion de casos, el mismo autor de JULIA sugiere que es conveniente pensar en un futuro en la integracion con otros metodos de aprendizaje como SBL (ver la seccion 2.2.1), o EBL (ver el captulo 4) que produzcan generalizaciones y abstracciones. Discusion JULIA ha sido uno de los primeros sistemas basados en casos exitosos, sin olvidarnos de su antecesor MEDIATOR [KOLO85]. Un aspecto fundamental de este sistema es la integracion que implementa del RBC junto con otros metodos de razonamiento, como la satisfaccion de restricciones. Ademas, la solucion a un problema no se consolida con un solo caso, sino con la intervencion de mas de un caso. Esto introduce una resolucion de problemas dinamica y adaptable a la situacion actual. Sin embargo, no todo son alabanzas al sistema, ya que la capacidad de aprendizaje de JULIA es limitada y se reduce, como ya se ha mencionado anteriormente, a recordar los casos tal y como se han solucionado. Una cuestion importante que es tambien interesante remarcar es la existencia de una version posterior a JULIA, el sistema PARADYME [KOLO88], donde se hace una implementacion

© Los autores, 1998; © Edicions UPC, 1998.

296

Aprendizaje Automatico

paralela del metodo de recuperacion de casos de memoria. La implementacion de PARADYME presupone, pues, la utilizacion existosa de tecnologas avanzadas, como arquitecturas paralelas, en el desarrollo de metodos para la Inteligencia Arti cial.

8.8 Resumen A lo largo de este captulo se han expuesto los aspectos fundamentales del razonamiento basado en casos. La reciente aparicion de este paradigma del aprendizaje hace que sus metodos esten todava poco estandarizados. As, los metodos explicados en este captulo distan mucho de ser formales, y en ocasiones se proporcionan ideas intuitivas mas que metodos concretos. Recurrir al estudio de las implementaciones ad hoc realizadas en sistemas existentes es, a menudo, la unica manera de mostrar el funcionamiento de las diferentes etapas (recuperacion, adaptacion, evaluacion y aprendizaje) que tienen lugar en el RBC. No obstante, el interes por desarrollar sistemas basados en casos va en aumento. Anualmente se celebran dos whorkshops espec cos sobre el razonamiento basado en casos, uno en Europa (EWCBR) y otro en Estados Unidos (patrocinado por DARPA), ademas de las secciones particulares dedicadas a este tipo de aprendizaje dentro de las conferencias generales tanto de Inteligencia Arti cial como de Aprendizaje. No existe, sin embargo, hasta el momento ninguna revista especializada para este concepto. Normalmente se publican artculos de RBC en revistas de caracter general como Arti cial Intelligence o AI Magazine (si se desea el lado mas aplicado del tema), o revistas especializadas en aprendizaje como Machine Learning. Precisamente, el numero de marzo de 1993 de esta revista esta dedicado al RBC [KOLO93b]. Su lectura permite realizar una puesta al da de los ultimos sistemas basados en casos desarrollados. Otras ocasiones para aprender sobre RBC son los cursos de verano sobre aprendizaje que organiza el ECAI (European Conference on Arti cial Intelligence), como por ejemplo [SYCA91], as como tutorials que tienen lugar antes de conferencias importantes como IJCAI (International Joint Conference on Arti cial Intelligence), y otros [KOLO91]. El futuro del RBC no se dirige solamente a la creacion de herramientas para la construccion de este tipo de sistemas y a su aplicacion en problemas reales y complejos, sino que se dirige a considerar el RBC como contenedor de arquitecturas cognitivas generales6 [KOLO93a]. Esto es, el RBC como mecanismo que articula la integracion entre diferentes metodos de resolucion de problemas y de aprendizaje. Este es el caso de la arquitectura MMA (Massive Memory Architecture, [PLAZ93]) donde la resolucion de problemas se basa en la busqueda de metodos aplicados en experiencias (episodios) anteriores.

8.9 Ejercicios 1. Supongamos que se desea construir un sistema capaz de proporcionar la con guracion hardware adecuada para un cliente, conociendo sus necesidades de software y de comunicaciones. > Como sera util una herramienta basada en casos ? > Que ventajas presentara respecto a otros metodos ? 6 Arquitecturas que trabajan para un amplio rango de tareas, que utilizan una extensa gama de metodos y representaciones, y que aprenden sobre aspectos de las tareas y su e ciencia. En este tipo de arquitecturas se hace uso de la economa cognitiva[LENA79]: la economa de recursos mentales, memoria y potencia de calculo.

© Los autores, 1998; © Edicions UPC, 1998.

297

Aprendizaje basado en casos

T1

T2

C1

C2

Figura 8.19: Figuras geometricas 2. Se dispone del conjunto siguiente de guras geometricas: Cada gura se describe por su trazo ( no, grueso o punteado) y su forma. Estudiar cual de las dos medidas de similitud proporcionadas en la seccion 8.3.1 de este captulo es la mas apropiada para compararlos. Se supone que la semejanza entre dos triangulos o dos cuadrados es mayor que la que existe entre un triangulo y un cuadrado. Para la medida de similitud basada en la importancia de cada caracterstica suponer los pesos adecuados para que se establezca la semejanza deseada (trazo es menos importante que forma). 3. Suponer ahora que la descripcion de las mismas guras geometricas se basa en el numero de angulos. De manera que la funcion de comparacion entre los casos es la siguiente: dif(angulos(C i ); angulos(C j )) simg (C i; C j ) = 1 ; max(angulos(C i ); angulos(C j )) donde dif(i; j) = max(i; j) ; min(i; j). (a) Determinar si esta funcion es apropiada. (b) Observar que con esta medida, la semejanza entre un cuadrado y un pentagono es mayor que la que existe entre un triangulo y un cuadrado. > Es correcto ? 4. Para organizar los casos del ejercicio 2 en memoria se dispone del siguiente conocimiento: Polgono

Cuadrilatero

 }i

* i K :::

Triangulo

* 6Y

Cuadrado Rectangulo : : : Isosceles Equilatero : : : Figura 8.20: A rbol de generalizacion. (a) Si esta permitido el uso de prototipos, >que procedimiento ha de tener lugar para abstraer las caractersticas comunes entre casos ? (b) > Tiene sentido generalizar, o se puede llegar al absurdo de generar un prototipo que no resulte util para distinguir cuadrados de triangulos ?

© Los autores, 1998; © Edicions UPC, 1998.

298

Aprendizaje Automatico

(c) > Que pasara si se incorpora en este conjunto de casos una gura conica ? 5. Explicar que consecuencias puede tener la presencia de conocimiento irrelevante en un sistema basado en casos, tanto para la indexacion como para la e ciencia general del sistema. 6. Comparar el razonamiento basado en casos con las bases de datos. Pista: pensar en el tipo de inputs (completo/incompleto) y en el matching de casos (parcial/total).

© Los autores, 1998; © Edicions UPC, 1998.