Aprendizaje en sistemas clasificadores Trabajo basado en la Arquitectura de Sistemas Clasificadores propuesta por Holland en 1986. Realizado para la asignatura IA2, asignatura de 4º Curso de Ingeniería Informática de la Escuela Politécnica Superior de la Universidad de Sevilla.
Contenido
Introducción 3
Arquitectura de Sistemas Clasificadores (Holland, 1986) 4
Consideraciones en el algoritmo genético: 5
Función Objetivo del algoritmo genético para generar reglas 8
Codificación Binaria estimada para el ejemplo de las Lentes 8
Variaciones en el algoritmo de pago "bucket-brigade": 9
Problemas encontrados al hacer este trabajo: 11
Posibles mejoras en el algoritmo: 12
Anexo I. Ficheros entregados 13
fileFunctions.lisp 13
clasificador.lisp 15
genetico.lisp 21
listaFuerzas.lisp 25
listaClasificadores.lisp 26
listaMensajes.lisp 27
Anexo II: Ejemplo de log generado por el algoritmo con 10 iteraciones. 29
Anexo III. Enunciado del trabajo propuesto. 34
Aprendizaje en Sistemas Clasificadores 34
Desarrollo del trabajo 34
Criterios de evaluación 35
Bibliografía 35
Introducción
En el presente documento se realiza una explicación del trabajo que hemos realizado para la asignatura Inteligencia Artificial II, asignatura troncal de 4º curso de Ingeniería Informática, impartida en la Escuela Técnica Superior de Ingeniería Informática de la Universidad de Sevilla.
El trabajo realizado, Aprendizaje en Sistemas Clasificadores, se centra principalmente en la implementación de la arquitectura de sistemas clasificadores propuesta por Holland en 1986. Para ello previamente hemos tenido que hacer un trabajo de investigación para definir el algoritmo, cabe destacar la dificultad que hemos encontrado a la hora de realizar el trabajo de investigación, pues dicho sistema clasificador no aparece descrito con un grado suficiente de detalle en el artículo de Holland, y los demás artículos que hemos ido localizando hacen breves aclaraciones para más adelante dedicarse a hacer recopilaciones de otros artículos en los que no hemos localizado las aclaraciones que necesitábamos.
A continuación mostramos un breve repaso de la arquitectura de sistemas clasificadores (Holland, 1986) para más adelante explicar los puntos que hemos considerado más interesantes. El algoritmo desarrollado ha sido explicado método a método mediante comentarios, para una comprensión más sencilla del mismo, por lo que hemos colocado directamente el código comentado en el Anexo I (junto a los demás métodos que conforman nuestro trabajo).
Arquitectura de Sistemas Clasificadores (Holland, 1986)
En este apartado nos centraremos en dar una visión general de la arquitectura de Sistemas Clasificadores planteada por Holland en 1986.
En dicho sistema, se distinguen claramente tres fases:
Algoritmo genético. Mediante el algoritmo genético obtenemos una serie de reglas que serán usadas por el algoritmo como entradas, a la vez que una lista de ejemplos a clasificar mediante dichas reglas.
Bucket Brigade. Método encargado de ajustar la fuerza de cada regla, así como de generar nuevas reglas.
Cada algoritmo tendrá inicialmente una determinada fuerza. En cada iteración cada regla hace una puja, las reglas que más hayan pujado (de entre las reglas candidatas) serán las seleccionadas, de forma que añadirán su cabeza al entorno. Las reglas que ganan la puja, pierden la cantidad de fuerza que hayan pujado, y las reglas que hayan perdido dicha puja son compensadas en la misma cantidad de la mayor puja efectuada (es decir, la que ha ganado).
Sistema clasificador. Podría definirse como el director de orquesta. Es el encargado de controlar el número de iteraciones que se tendrán en cuenta para generar las reglas de clasificación. En nuestro caso, obtendrá los detectores, ejecutará el método bucket-brigade por cada iteración y añadirá nuevos mensajes en el caso de que bucket-brigade no pueda añadir ninguno.
Consideraciones en el algoritmo genético:
Cuando comenzamos con la implementación del algoritmo genético tuvimos el inconveniente de elegir un problema donde la función objetivo no tenía ningún tipo de medida que nos dijera si una clasificación era mejor que otra.
En nuestro caso, escogimos el problema de las transparencias del tema 2 de teoría de IA2 de las lentes (RIGIDA o BLANDA):
Como las cadenas binarias se generan aleatoriamente, castigamos a aquellas que no cumplen con el formato de nuestra codificación, pero a las que cumplen con el formato no las destacamos unas sobre otras.
Una posible mejora hubiera sido considerar que un tipo de lente es más barata que la otra, y premiar las reglas que implican menor coste.
En un problema que encontramos sobre si un perro ladraba, corría, se quedaba quieto etc, en función de las características del cartero, se premiaban aquellas reglas que suponían un menor gasto de energía para el perro. Este ejemplo nos pareció bueno pero por un problema que comentamos más adelante no supimos como codificarlo.
Función Objetivo del algoritmo genético para generar reglas
Aunque usamos el algoritmo genético como una especie de generador aleatorio avanzado en nuestro caso, al usarlo para generar nuevas reglas, no tenemos una heurística a priori para determinar que una regla sea mejor que otra a la hora de clasificar.
Hemos tomado la decisión de aplicar un F-Objetivo de forma que si la regla generada cumple el formato adecuado (presentado en este documento) entonces la puntuación es muy alta y en caso contrario, la puntuación para ese cromosoma es nula.
De esa forma las reglas bien formadas son las que irán pasando de generación en generación, pero todas las reglas bien formadas tienen la misma posibilidad de ser elegidas.
Aunque existe una probabilidad muy baja que a través de las generaciones se haya colado una regla mal codificada para nuestro ejemplo concreto, se ha puesto una comprobación de forma que el método MEJOR solo devuelve el mejor de todos los cromosomas que además está bien codificado.
El método que comprueba el formato del cromosoma es propio de cada problema así como f-objetivo.
Codificación Binaria estimada para el ejemplo de las Lentes
Aunque finalmente no hemos podido realizar las pruebas con este ejemplo, hemos querido comentar el planteamiento que habíamos hecho para poder hacer uso de dicho ejemplo.
La idea es codificar el ejemplo en genes de longitud 7 bits de la siguiente forma:
(X X X X X X X)
El símbolo para indicar que no importa el valor de un campo es: - (guión o símbolo menos)
Los 2 últimos bits subrayados en negro son especiales ya que realmente son la cabeza de la regla o lo que es lo mismo, la clasificación de ese ejemplo.
En esos 2 bits no puede haber símbolos especiales de “dont care”.
EDAD JOVEN : 00
EDAD PRE PRESBICIA: 01
EDAD PRESBICIA : 10
DIAGNOSTICO MIOPE: 0
DIAGNOSTICO HIPERMETROPE: 1
ASTIGMATISMO SI: 1
ASTIGMATISMO NO : 0
LAGRIMA NORMAL: 0
LAGRIMA REDUCIDA: 1
LENTE RIGIDA: 00
LENTE BLANDA : 01
LENTE NINGUNA: 10
Variaciones en el algoritmo de pago "bucket-brigade":
En los sistemas clasificadores habituales, se incrementa el crédito de todos aquellos clasificadores que están activos en el momento del pago. Esto genera el problema de que muchos clasificadores reciben crédito tan solo porque su condición coincide con algún mensaje en la lista de mensajes pero si no ganan la apuesta y no insertan un nuevo mensaje, no han hecho nada para alcanzar la solución.
Para evitar este problema hemos añadido una "memoria" de forma que vamos guardando qué mensajes ha insertado cada clasificador. De esta forma, si ese mensaje activa nuevos clasificadores, se realiza un pago a aquellos clasificadores que previamente lo habían insertado.
Haciéndolo de este modo solo se incrementa el crédito de los clasificadores que han insertado un mensaje y que además dicho mensaje ha servido para activar otros clasificadores, logrando con esto que nuestro algoritmo sea algo más eficiente.
Problemas encontrados al hacer este trabajo:
El problema principal a la hora de buscar en los artículos que se adjuntan con este proyecto es que los detectores y efectores no vienen detallados en ningún aspecto.
Esto plantea el problema de que para hacer el algoritmo de matching, la longitud de la cabeza y la condición de cada regla debe ser la misma, de forma que podamos buscar que reglas se activan según los mensajes de la lista de mensajes.
Esta igualdad en la longitud de las dos partes que componen una regla nos hacía imposible concebir un ejemplo útil que encajara y optamos por jugar con cadenas binarias de igual longitud pero sin un significado concreto.
Los detectores y efectores parece que hacen de traductores y por ello en otros trabajos que hemos estudiado aparecen ejemplos con distinta longitud.
Algunos de estos ejemplos son:
En MACHINE LEARNING USING A GENETIC-BASED APPROACH. (Michael O. Odetayo): Según una serie de propiedades se debe clasificar en un tipo u otro de objeto.
Es un ejemplo que no sabíamos representar con 2 cadenas binarias de la misma longitud para cabeza y cuerpo de las reglas aunque en el propio artículo enuncian esta igualdad de longitud K.
En el ejemplo original del artículo de Holland sobre la rana ocurre lo mismo. La codificación binaria para las condiciones en las que la rana debía realizar uno u otro movimiento no coincidían en longitud y los efectores y defectores se presentan como una caja negra que normaliza la entrada y salida del algoritmo.
En algunos otros artículos y libros la longitud de la cabeza y el cuerpo de la regla no coinciden, pero no explican entonces como hacer el algoritmo de matching o coincidencias con el que los clasificadores son activados a través de mensajes.
Posibles mejoras en el algoritmo:
En cada iteración tras del algoritmo se comprueba que la lista de mensajes sigue evolucionando. Si llega un punto donde no hay nuevos mensajes que activen reglas, entonces se vuelve a llamar al algoritmo genético para que inserte nuevas reglas (distintas a las que ya existen).
Una posible mejora en este punto sería la de eliminar de la lista de reglas a aquellas que no están colaborando para alcanzar una solución. Esto podemos saberlo con el crédito de cada uno de los clasificadores.
Como se ha comentado previamente, al no contar con ejemplos reales y no poder hacer pruebas experimentales, no hemos podido establecer que umbral sería bueno para dicha criba.
Anexo I. Ficheros entregados
Aprovechamos este anexo para explicar la estructura así como la función de cada uno de los ficheros .lisp generados durante la realización del presente proyecto.
fileFunctions.lisp
Agrupamos en este fichero todas las funciones encargadas del tratamiento con fichero, así como el buffer que usamos para la generación de los logs generados por el algoritmo:
. Log en el que mostramos las principales características del algoritmo tras su ejecución.
*Nota:
clasificador.lisp
Tal y como se observa, cada una de las funciones han sido descritas en el mismo código (mediante comentarios) para lograr una mayor comprensión del mismo.
genetico.lisp
listaFuerzas.lisp
Agrupación de funciones usadas para la gestión de la tabla de mensajes.
listaClasificadores.lisp
Agrupación de funciones para la gestión de la tabla de clasificadores.
listaMensajes.lisp
Agrupación de funciones para la gestión de la tabla de mensajes.
Anexo II: Ejemplo de log generado por el algoritmo con 10 iteraciones.
El objetivo principal del trabajo es implementar en Lisp la arquitectura de Sistemas Clasificadores introducida por Holland en 1986, que consiste básicamente en dotar a un sistema de producción (basado en reglas) de algoritmos genéticos que le permitan "adaptarse" a su entorno interaccionando con éste y realizando un aprendizaje con refuerzo.
Concretamente, Holland ideó un sistema con varios componentes interconectados. Por un lado está el sistema de producción con sus reglas, que cuenta con canales de comunicación con el entorno. Al sistema le llegan mensajes con observaciones, que vienen representadas como listas de valores de ciertos atributos. Las reglas con las que se trabaja tienen la siguiente forma
(v1,...,vn) : ci
En el cuerpo de la regla, cada vi indica el valor de un atributo, o bien se puede dejar ese valor libre, utilizando un símbolo comodín (por ejemplo, # o *). La cabeza de la regla, ci, puede interpretarse como la clasificación asignada por el sistema a todas las instancias que encajen con ese patrón. Por ello las reglas se denominan "clasificadores".
El aprendizaje puede consistir en una competición entre las reglas para que al final se elija la mejor ("Pittsburg approach"); o bien se puede considerar que las reglas van a trabajar todas en conjunto, aunque el sistema le asigna a cada una un valor de crédito/credibilidad, y el proceso de aprendizaje trata un conjunto de reglas como un individuo ("Michigan approach").
Desarrollo del trabajo
La primera fase del trabajo consiste en estudiar la bibliografía para aclarar el concepto de Sistemas Clasificadores y para consultar las distintas adaptaciones que se han hecho de la idea original de Holland. Se podrán tomar decisiones para simplificar el diseño siguiendo las indicaciones de alguna de las referencias consultadas, siempre que estas decisiones queden debidamente explicadas en la memoria.
El trabajo se presentará en forma de dos ficheros: un fichero .lsp con todo el código Lisp (implementación del sistema de producción, algoritmo genético, etc), que deberá estar bien comentado, y una memoria en pdf donde se especifiquen los detalles de la implementación realizada: representación elegida, mecanismo de actualización de las credibilidades de las reglas, algoritmo genético implementado, etc.
Se deberá elegir algún ejemplo para trabajar con él y realizar pruebas, bien sea tomado de la bibliografía o de cualquier otra fuente.
Criterios de evaluación
Se valorará la eficiencia en la implementación, claridad en la documentación y el buen estilo de programación en Lisp.
También se tendrá en cuenta la claridad con que se elabore la memoria, así como el dominio del trabajo que se demuestre en la defensa.
Cualquier material que se consulte, sea de las referencias proporcionadas o de otras fuentes deberá ser convenientemente referenciado en la memoria.
Se valorará cualquier aportación original que se incluya en el trabajo de manera adicional, aparte de los requisitos mínimos aquí descritos.
Bibliografía
A. Moreno et al. "Aprendizaje Automático". Edicions UPC,1994.
D.E. Goldberg. "Genetic Algorithms in Search, Optimization and Machine Learning". Addison-Wesley, 1989.
Z. Michalewicz. "Genetic Algorithms + Data Structures = Evolution Programs" (3a ed.). Springer, 1999.
S.W. Wilson. "Classifier Fitness Based on Accuracy". Evolutionary Computation 3(2), pp. 149-175.
La Casa de los Siete Tejados introduccion «The Custom House», introducción a The Scarlet Letter, que se gestó entonces, aunque tenga claros precedentes en escritos anteriores,...
