New Challenges in Learning Classifier Systems: Mining Rarities and Evolving Fuzzy Models

Abstract

Durant l'última dècada, els sistemes classificadors (LCS) d'estil Michigan - sistemes d'aprenentatge automàtic que combinen tècniques de repartiment de crèdit i algorismes genètics (AG) per evolucionar una població de classificadors online- han renascut. Juntament amb la formulació dels sistemes de primera generació, s'han produït avenços importants en (1) el disseny sistemàtic de nous LCS competents, (2) la seva aplicació en dominis rellevants i (3) el desenvolupament d'anàlisis teòriques. Malgrat aquests dissenys i aplicacions importants, encara hi ha reptes complexos que cal abordar per comprendre millor el funcionament dels LCS i per solucionar problemes del món real eficientment i escalable.<br/>Aquesta tesi tracta dos reptes importants - compartits amb la comunitat d'aprenentatge automàtic - amb LCS d'estil Michigan: (1) aprenentatge en dominis que contenen classes estranyes i (2) evolució de models comprensibles on s'utilitzin mètodes de raonament similars als humans. L'aprenentatge de models precisos de classes estranyes és crític, doncs el coneixement clau sol quedar amagat en exemples d'aquestes, i la majoria de tècniques d'aprenentatge no són capaces de modelar la raresa amb precisió. La detecció de rareses sol ser complicat en aprenentatge online ja que el sistema d'aprenentatge rep un flux d'exemples i ha de detectar les rareses al vol. D'altra banda, l'evolució de models comprensibles és crucial en certs dominis com el mèdic, on l'expert acostuma a estar més interessat en obtenir una explicació intel·ligible de la predicció que en la predicció en si mateixa.<br/>El treball present considera dos LCS d'estil Michigan com a punt de partida: l'XCS i l 'UCS. Es pren l'XCS com a primera referència ja que és l'LCS que ha tingut més influencia fins al moment. L'UCS hereta els components principals de l'XCS i els especialitza per aprenentatge supervisat. Tenint en compte que aquesta tesi especialment se centra en problemes de classificació, l'UCS també es considera en aquest estudi. La inclusió de l'UCS marca el primer objectiu de la tesi, sota el qual es revisen un conjunt de punts que van restar oberts en el disseny del sistema. A més, per il·lustrar les diferències claus entre l'XCS i l'UCS, es comparen ambdós sistemes sobre una bateria de problemes artificials de complexitat acotada.<br/>L'estudi de com els LCS aprenen en dominis amb classes estranyes comença amb un estudi analític que descompon el problema en cinc elements crítics i deriva models per facetes per cadascun d'ells. Aquesta anàlisi s'usa com a eina per dissenyar guies de configuració que permeten que l'XCS i l'UCS solucionin problemes que prèviament no eren resolubles. A continuació, es comparen els dos LCS amb alguns dels sistemes d'aprenentatge amb més influencia en la comunitat d'aprenentatge automàtic sobre una col·lecció de problemes del món real que contenen classes estranyes. Els resultats indiquen que els dos LCS són els mètodes més robustos de la comparativa. Així mateix, es demostra experimentalment que remostrejar els conjunts d'entrenament amb l'objectiu d'eliminar la presencia de classes estranyes beneficia, en mitjana, el rendiment de les tècniques d'aprenentatge.<br/>El repte de crear models més comprensibles i d'usar mecanismes de raonament que siguin similars als humans s'aborda mitjançant el disseny d'un nou LCS per aprenentatge supervisat que combina les capacitats d'avaluació de regles online, la robustesa mostrada pels AG en problemes complexos i la representació comprensible i mètodes de raonament fonamentats proporcionats per la lògica difusa. El nou LCS, anomenat Fuzzy-UCS, s'estudia en detall i es compara amb una bateria de mètodes d'aprenentatge. Els resultats de la comparativa demostren la competitivitat del Fuzzy-UCS en termes de precisió i intel·ligibilitat dels models evolucionats. Addicionalment, s'usa Fuzzy-UCS per extreure models de classificació acurats de grans volums de dades, exemplificant els avantatges de l'arquitectura d'aprenentatge online del Fuzzy-UCS.<br/>En general, les observacions i avenços assolits en aquesta tesi contribueixen a augmentar la comprensió del funcionament dels LCS i en preparar aquests tipus de sistemes per afrontar problemes del món real de gran complexitat. Finalment, els resultats experimentals ressalten la robustesa i competitivitat dels LCS respecte a altres mètodes d'aprenentatge, encoratjant el seu ús per tractar nous problemes del món real.

Durante la última década, los sistemas clasificadores (LCS) de estilo Michigan - sistemas de aprendizaje automático que combinan técnicas de repartición de crédito y algoritmos genéticos (AG) para evolucionar una población de clasificadores online - han renacido. Juntamente con la formulación de los sistemas de primera generación, se han producido avances importantes en (1) el diseño sistemático de nuevos LCS competentes, (2) su aplicación en dominios relevantes y (3) el desarrollo de análisis teóricos. Pese a eso, aún existen retos complejos que deben ser abordados para comprender mejor el funcionamiento de los LCS y para solucionar problemas del mundo real escalable y eficientemente.<br/>Esta tesis trata dos retos importantes - compartidos por la comunidad de aprendizaje automático - con LCS de estilo Michigan: (1) aprendizaje en dominios con clases raras y (2) evolución de modelos comprensibles donde se utilicen métodos de razonamiento similares a los humanos. El aprendizaje de modelos precisos de clases raras es crítico pues el conocimiento clave suele estar escondido en ejemplos de estas clases, y la mayoría de técnicas de aprendizaje no son capaces de modelar la rareza con precisión. El modelado de las rarezas acostumbra a ser más complejo en entornos de aprendizaje online, pues el sistema de aprendizaje recibe un flujo de ejemplos y debe detectar las rarezas al vuelo. La evolución de modelos comprensibles es crucial en ciertos dominios como el médico, donde el experto está más interesado en obtener una explicación inteligible de la predicción que en la predicción en sí misma.<br/>El trabajo presente considera dos LCS de estilo Michigan como punto de partida: el XCS y el UCS. Se toma XCS como primera referencia debido a que es el LCS que ha tenido más influencia hasta el momento. UCS es un diseño reciente de LCS que hereda los componentes principales de XCS y los especializa para aprendizaje supervisado. Dado que esta tesis está especialmente centrada en problemas de clasificación automática, también se considera UCS en el estudio. La inclusión de UCS marca el primer objetivo de la tesis, bajo el cual se revisan un conjunto de aspectos que quedaron abiertos durante el diseño del sistema. Además, para ilustrar las diferencias claves entre XCS y UCS, se comparan ambos sistemas sobre una batería de problemas artificiales de complejidad acotada.<br/>El estudio de cómo los LCS aprenden en dominios con clases raras empieza con un estudio analítico que descompone el problema en cinco elementos críticos y deriva modelos por facetas para cada uno de ellos. Este análisis se usa como herramienta para diseñar guías de configuración que permiten que XCS y UCS solucionen problemas que previamente no eran resolubles. A continuación, se comparan los dos LCS con algunos de los sistemas de aprendizaje de mayor influencia en la comunidad de aprendizaje automático sobre una colección de problemas del mundo real que contienen clases raras.<br/>Los resultados indican que los dos LCS son los métodos más robustos de la comparativa. Además, se demuestra experimentalmente que remuestrear los conjuntos de entrenamiento con el objetivo de eliminar la presencia de clases raras beneficia, en promedio, el rendimiento de los métodos de aprendizaje automático incluidos en la comparativa.<br/>El reto de crear modelos más comprensibles y usar mecanismos de razonamiento que sean similares a los humanos se aborda mediante el diseño de un nuevo LCS para aprendizaje supervisado que combina las capacidades de evaluación de reglas online, la robustez mostrada por los AG en problemas complejos y la representación comprensible y métodos de razonamiento proporcionados por la lógica difusa. El sistema que resulta de la combinación de estas ideas, llamado Fuzzy-UCS, se estudia en detalle y se compara con una batería de métodos de aprendizaje altamente reconocidos en el campo de aprendizaje automático. Los resultados de la comparativa demuestran la competitividad de Fuzzy-UCS en referencia a la precisión e inteligibilidad de los modelos evolucionados. Adicionalmente, se usa Fuzzy-UCS para extraer modelos de clasificación precisos de grandes volúmenes de datos, ejemplificando las ventajas de la arquitectura de aprendizaje online de Fuzzy-UCS.<br/>En general, los avances y observaciones proporcionados en la tesis presente contribuyen a aumentar la comprensión del funcionamiento de los LCS y a preparar estos tipos de sistemas para afrontar problemas del mundo real de gran complejidad. Además, los resultados experimentales resaltan la robustez y competitividad de los LCS respecto a otros métodos de aprendizaje, alentando su uso para tratar nuevos problemas del mundo real.

During the last decade, Michigan-style learning classifier systems (LCSs) - genetic-based machine learning (GBML) methods that combine apportionment of credit techniques and genetic algorithms (GAs) to evolve a population of classifiers online - have been enjoying a renaissance. Together with the formulation of first generation systems, there have been crucial advances in (1) systematic design of new competent LCSs, (2) applications in important domains, and (3) theoretical analyses for design. Despite these successful designs and applications, there still remain difficult challenges that need to be addressed to increase our comprehension of how LCSs behave and to scalably and efficiently solve real-world problems.<br/>The purpose of this thesis is to address two important challenges - shared by the machine learning community - with Michigan-style LCSs: (1) learning from domains that contain rare classes and (2) evolving highly legible models in which human-like reasoning mechanisms are employed. Extracting accurate models from rare classes is critical since the key, unperceptive knowledge usually resides in the rarities, and many traditional learning techniques are not able to model rarity accurately. Besides, these difficulties are increased in online learning, where the learner receives a stream of examples and has to detect rare classes on the fly. Evolving highly legible models is crucial in some domains such as medical diagnosis, in which human experts may be more interested in the explanation of the prediction than in the prediction itself.<br/>The contributions of this thesis take two Michigan-style LCSs as starting point: the extended classifier system (XCS) and the supervised classifier system (UCS). XCS is taken as the first reference of this work since it is the most influential LCS. UCS is a recent LCS design that has inherited the main components of XCS and has specialized them for supervised learning. As this thesis is especially concerned with classification problems, UCS is also considered in this study. Since UCS is still a young system, for which there are several open issues that need further investigation, its learning architecture is first revised and updated. Moreover, to illustrate the key differences between XCS and UCS, the behavior of both systems is compared % and show that UCS converges quickly than XCS on a collection of boundedly difficult problems.<br/>The study of learning from rare classes with LCSs starts with an analytical approach in which the problem is decomposed in five critical elements, and facetwise models are derived for each element. The analysis is used as a tool for designing configuration guidelines that enable XCS and UCS to solve problems that previously eluded solution. Thereafter, the two LCSs are compared with several highly-influential learners on a collection of real-world problems with rare classes, appearing as the two best techniques of the comparison. Moreover, re-sampling the training data set to eliminate the presence of rare classes is demonstrated to benefit, on average, the performance of LCSs.<br/>The challenge of building more legible models and using human-like reasoning mechanisms is addressed with the design of a new LCS for supervised learning that combines the online evaluation capabilities of LCSs, the search robustness over complex spaces of GAs, and the legible knowledge representation and principled reasoning mechanisms of fuzzy logic. The system resulting from this crossbreeding of ideas, referred to as Fuzzy-UCS, is studied in detail and compared with several highly competent learning systems, demonstrating the competitiveness of the new architecture in terms of the accuracy and the interpretability of the evolved models. In addition, the benefits provided by the online architecture are exemplified by extracting accurate classification models from large data sets.<br/>Overall, the advances and key insights provided in this thesis help advance our understanding of how LCSs work and prepare these types of systems to face increasingly difficult problems, which abound in current industrial and scientific applications. Furthermore, experimental results highlight the robustness and competitiveness of LCSs with respect to other machine learning techniques, which encourages their use to face new challenging real-world applications.