Aquesta memòria s'ha escrit amb l'ànim d'exposar els punts de vista i els resultats nous que l'autor ha pogut obtenir. No s'hi troba, per tant, una descripció detallada de tots els temes que conformen la teoria dels operadors de T-indistingibilitat, el Raonament Aproximat ni, per descomptat, la Lògica Difusa. S'ha glossat només els aspectes necessaris per fer la memòria autocontinguda, i s'ha reforçat l'exposició amb un conjunt ampli de referències bibliogràfiques. L'excel·lència de moltes d'elles fa absolutament innecesari i pretenciós l'intent de l'autor de reescriure sobre els mateixos temes amb l'ànim de fer-los entenedors.La memòria està dividida en dues parts: 1) Operadors de T-indistingibilitat (Capítols 1, 2 i 3)2) Aplicacions al Raonament Aproximat (Capítols 4 i 5)En la primera part s'estudia qüestions relatives a l'estructura dels operadors de T-indistingibilitat.El Capítol 1 tracta dels aspectes previs: les t-normes i, sobre tot, les seves quasi-inverses. Són les operacions bàsiques sobre les que es construeixen els operadors de T-indistingibilitat.En el Capítol 2 s'estudia l'estructura del conjunt HE dels generadors d'una T-indistingibilitat E, des del punt de vista reticular i dimensional. Finalment, el Capítol 3 està dedicat als morfismes entre operadors de T-indistingibilitat i a l'estructura dual.A la segona part es proposa un principi general de Raonament Aproximat que es basa en els operadors de T-indistingibilitat. En el Capítol 4, s'analitza les diferents formes de CRI a través d'aquest principi, i es proposa nous mecanismes d'inferència diferents de CRI (Operador Natural d'Inferència), mentre que en el Capítol 5 s'estudia l'estructura dels nous mecanismes introduïts i el seu comportament en interpolació, en presència de múltiples regles.Cada capítol s'encapçala amb una introducció en forma de sumari i amb un llistat de les aportacions de la memòria (resultats nous).

Aquest treball presenta una classe de funcions que serveixen de models neuronals generalitzats per ser usats en xarxes neuronals artificials. Es defineixen com una mesura de similitud que actúa com una definició flexible de neurona vista com un reconeixedor de patrons. La similitud proporciona una marc conceptual i serveix de cobertura unificadora de molts models neuronals de la literatura i d'exploració de noves instàncies de models de neurona. La visió basada en similitud porta amb naturalitat a integrar informació heterogènia, com ara quantitats contínues i discretes (nominals i ordinals), i difuses ó imprecises. Els valors perduts es tracten de manera explícita. Una neurona d'aquesta classe s'anomena neurona heterogènia i qualsevol arquitectura neuronal que en faci ús serà una Xarxa Neuronal Heterogènia.En aquest treball ens concentrem en xarxes neuronals endavant, com focus inicial d'estudi. Els algorismes d'aprenentatge són basats en algorisms evolutius, especialment extesos per treballar amb informació heterogènia. En aquesta tesi es descriu com una certa classe de neurones heterogènies porten a xarxes neuronals que mostren un rendiment molt satisfactori, comparable o superior al de xarxes neuronals tradicionals (com el perceptró multicapa ó la xarxa de base radial), molt especialment en presència d'informació heterogènia, usual en les bases de dades actuals. / This work presents a class of functions serving as generalized neuron models to be used in artificial neural networks. They are cast into the common framework of computing a similarity function, a flexible definition of a neuron as a pattern recognizer. The similarity endows the model with a clear conceptual view and serves as a unification cover for many of the existing neural models, including those classically used for the MultiLayer Perceptron (MLP) and most of those used in Radial Basis Function Networks (RBF). These families of models are conceptually unified and their relation is clarified. The possibilities of deriving new instances are explored and several neuron models --representative of their families-- are proposed. The similarity view naturally leads to further extensions of the models to handle heterogeneous information, that is to say, information coming from sources radically different in character, including continuous and discrete (ordinal) numerical quantities, nominal (categorical) quantities, and fuzzy quantities. Missing data are also explicitly considered. A neuron of this class is called an heterogeneous neuron and any neural structure making use of them is an Heterogeneous Neural Network (HNN), regardless of the specific architecture or learning algorithm. Among them, in this work we concentrate on feed-forward networks, as the initial focus of study. The learning procedures may include a great variety of techniques, basically divided in derivative-based methods (such as the conjugate gradient)and evolutionary ones (such as variants of genetic algorithms).In this Thesis we also explore a number of directions towards the construction of better neuron models --within an integrant envelope-- more adapted to the problems they are meant to solve.It is described how a certain generic class of heterogeneous models leads to a satisfactory performance, comparable, and often better, to that of classical neural models, especially in the presence of heterogeneous information, imprecise or incomplete data, in a wide range of domains, most of them corresponding to real-world problems.

Information Extraction (IE) can be defined as the task of automatically extracting preespecified kind of information from a text document. The extracted information is encoded in the required format and then can be used, for example, for text summarization or as accurate index to retrieve new documents.The main issue when building IE systems is how to obtain the knowledge needed to identify relevant information in a document. Today, IE systems are commonly based on extraction rules or IE patterns to represent the kind of information to be extracted. Most approaches to IE pattern acquisition require expert human intervention in many steps of the acquisition process. This dissertation presents a novel method for acquiring IE patterns, Essence, that significantly reduces the need for human intervention. The method is based on ELA, a specifically designed learning algorithm for acquiring IE patterns from unannotated corpora.The distinctive features of Essence and ELA are that 1) they permit the automatic acquisition of IE patterns from unrestricted and untagged text representative of the domain, due to 2) their ability to identify regularities around semantically relevant concept-words for the IE task by 3) using non-domain-specific lexical knowledge tools such as WordNet and 4) restricting the human intervention to defining the task, and validating and typifying the set of IE patterns obtained.Since Essence does not require a corpus annotated with the type of information to be extracted and it does makes use of a general purpose ontology and widely applied syntactic tools, it reduces the expert effort required to build an IE system and therefore also reduces the effort of porting the method to any domain.In order to Essence be validated we conducted a set of experiments to test the performance of the method. We used Essence to generate IE patterns for a MUC-like task. Nevertheless, the evaluation procedure for MUC competitions does not provide a sound evaluation of IE systems, especially of learning systems. For this reason, we conducted an exhaustive set of experiments to further test the abilities of Essence.The results of these experiments indicate that the proposed method is able to learn effective IE patterns.

This thesis is structured in four parts for a total of ten chapters. The first part, introduction and review (Chapters 1 to 4), presents an extensive state-of-the-art review of both symbolic and connectionist GI methods, that serves also to state most of the basic material needed to describe later the contributions of the thesis. These contributions constitute the contents of the rest of parts (Chapters 5 to 10). The second part, contributions on symbolic and connectionist techniques for regular grammatical inference (Chapters 5 to 7), describes the contributions related to the theory and methods for regular GI, which include other lateral subjects such as the representation oí. finite-state machines (FSMs) in recurrent neural networks (RNNs).The third part of the thesis, augmented regular expressions and their inductive inference, comprises Chapters 8 and 9. The augmented regular expressions (or AREs) are defined and proposed as a new representation for a subclass of CSLs that does not contain all the context-free languages but a large class of languages capable of describing patterns with symmetries and other (context-sensitive) structures of interest in pattern recognition problems.The fourth part of the thesis just includes Chapter 10: conclusions and future research. Chapter 10 summarizes the main results obtained and points out the lines of further research that should be followed both to deepen in some of the theoretical aspects raised and to facilitate the application of the developed GI tools to real-world problems in the area of computer vision.

L'extracció d'informació és l'àrea del processament de llenguatge natural l'objectiu de la qual és l'obtenir dades estructurades a partir de la informació rellevant continguda en fragments textuals. L'extracció d'informació requereix una quantitat considerable de coneixement lingüístic. La especificitat d'aquest coneixement suposa un inconvenient de cara a la portabilitat dels sistemes, ja que un canvi d'idioma, domini o estil té un cost en termes d'esforç humà. Durant dècades, s'han aplicat tècniques d'aprenentatge automàtic per tal de superar aquest coll d'ampolla de portabilitat, reduint progressivament la supervisió humana involucrada. Tanmateix, a mida que augmenta la disponibilitat de grans col·leccions de documents, esdevenen necessàries aproximacions completament nosupervisades per tal d'explotar el coneixement que hi ha en elles. La proposta d'aquesta tesi és la d'incorporar tècniques de clustering a l'adquisició de patrons per a extracció d'informació, per tal de reduir encara més els elements de supervisió involucrats en el procés En particular, el treball se centra en el problema de la detecció de relacions. L'assoliment d'aquest objectiu final ha requerit, en primer lloc, el considerar les diferents estratègies en què aquesta combinació es podia dur a terme; en segon lloc, el desenvolupar o adaptar algorismes de clustering adequats a les nostres necessitats; i en tercer lloc, el disseny de procediments d'adquisició de patrons que incorporessin la informació de clustering. Al final d'aquesta tesi, havíem estat capaços de desenvolupar i implementar una aproximació per a l'aprenentatge de patrons per a detecció de relacions que, utilitzant tècniques de clustering i un mínim de supervisió humana, és competitiu i fins i tot supera altres aproximacions comparables en l'estat de l'art. / Information extraction is the natural language processing area whose goal is to obtain structured data from the relevant information contained in textual fragments. Information extraction requires a significant amount of linguistic knowledge. The specificity of such knowledge supposes a drawback on the portability of the systems, as a change of language, domain or style demands a costly human effort. Machine learning techniques have been applied for decades so as to overcome this portability bottleneck¿progressively reducing the amount of involved human supervision. However, as the availability of large document collections increases, completely unsupervised approaches become necessary in order to mine the knowledge contained in them. The proposal of this thesis is to incorporate clustering techniques into pattern learning for information extraction, in order to further reduce the elements of supervision involved in the process. In particular, the work focuses on the problem of relation detection. The achievement of this ultimate goal has required, first, considering the different strategies in which this combination could be carried out; second, developing or adapting clustering algorithms suitable to our needs; and third, devising pattern learning procedures which incorporated clustering information. By the end of this thesis, we had been able to develop and implement an approach for learning of relation detection patterns which, using clustering techniques and minimal human supervision, is competitive and even outperforms other comparable approaches in the state of the art.

Aquesta tesi tracta l'adquisició automàtica de classes semàntiques per a adjectius. La tesi es basa en dues hipòtesis. La primera, que alguns aspectes de la semàntica dels adjectius no són totalment impredictibles, sinó que corresponen a un conjunt de tipus denotacionals, o classes semàntiques. En conseqüència, els adjectius es poden agrupar en funció de la seva classe semàntica. La segona hipòtesi de treball és que la classe semàntica es reflecteix en més d'un nivell de descripció lingüística. Les interfícies entre morfologia i semàntica i entre sintaxi i semàntica són les que s'exploren en detall a la tesi. Com que no ens podíem basar en una classificació establerta prèviament, bona part dels esforços van dirigits precisament a definir una classificació adequada. La proposta de classificació s'assoleix mitjançant una metodologia iterativa. Es combinen aproximacions deductives i inductives, cosa que permet evolucionar d'una classificació inicial basada en la bibliografia teòrica a una classificació final que té en compte els resultats empírics dels diversos experiments. / Esta tesis versa sobre la adquisición automática de clases semánticas para adjetivos. La tesis se basa en dos hipótesis. La primera, que algunos aspectos de la semántica de los adjetivos no son totalmente impredecibles, sino que corresponden a un conjunto de tipos denotacionales, o clases semánticas. En consecuencia, los adjetivos se pueden agrupar en función de su clase semántica. La segunda hipótesis de trabajo es que la clase semántica se refleja en más de un nivel de descripción lingüística. Las interfaces entre morfología y semántica y entre sintaxis y semántica son las que se exploran en detalle en la tesis. Dado que no nos podíamos basar en una clasificación establecida previamente, buena parte de los esfuerzos van dirigidos precisamente a definir una clasificación adecuada. La propuesta de clasificación se logra mediante una metodología iterativa. Se combinan aproximaciones deductivas e inductivas, cosa que permite evolucionar de una clasificación inicial basada en la bibliografía teórica a una clasificación final que tiene en cuenta los resultados empíricos de los diversos experimentos. / This thesis concerns the automatic acquisition of semantic classes for adjectives. Our work builds on two hypotheses: first, that some aspects of the semantics of adjectives are not totally unpredictable, but correspond to a set of denotational types (semantic classes). Therefore, adjectives can be grouped together according to their semantic class. Second, that the semantic class of an adjective can be traced in more than one linguistic level. In particular, the morphology-semantics and syntax-semantics interfaces are explored for clues that lead to the acquisition of the targeted semantic classes.Since we could not rely on a previously established classification, a major effort is devoted to defining an adequate classification. The classification proposal is reached through an iterative methodology. By combining deductive and inductive approaches, we evolve from an initial classification based on literature review to a final classification proposal that takes advantage of the insight gained through a set of experiments.

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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.