A qualidade das hipóteses induzidas pelos atuais sistemas de Aprendizado de Máquina depende principalmente da quantidade e da qualidade dos atributos e exemplos utilizados no treinamento. Freqüentemente, resultados experimentais obtidos sobre grandes bases de dados, que possuem muitos atributos irrelevantes, resultam em hipóteses de baixa precisão. Por outro lado, muitos dos sistemas de aprendizado de máquina conhecidos não estão preparados para trabalhar com uma quantidade muito grande de exemplos. Assim, uma das áreas de pesquisa mais ativas em aprendizado de máquina tem girado em torno de técnicas que sejam capazes de ampliar a capacidade dos algoritmos de aprendizado para processar muitos exemplos de treinamento, atributos e classes. Para que conceitos sejam aprendidos a partir de grandes bases de dados utilizando Aprendizado de Máquina, pode-se utilizar duas abordagens. A primeira realiza uma seleção de exemplos e atributos mais relevantes, e a segunda ´e a abordagem de ensembles. Um ensemble ´e um conjunto de classificadores cujas decisões individuais são combinadas de alguma forma para classificar um novo caso. Ainda que ensembles classifiquem novos exemplos melhor que cada classificador individual, eles se comportam como caixas pretas, no sentido de n˜ao oferecer ao usuário alguma explicação relacionada à classificação por eles fornecida. O objetivo deste trabalho é propor uma forma de combinação de classificadores simbólicos, ou seja, classificadores induzidos por algoritmos de AM simbólicos, nos quais o conhecimento é descrito na forma de regras if-then ou equivalentes, para se trabalhar com grandes bases de dados. A nossa proposta é a seguinte: dada uma grande base de dados, divide-se esta base aleatoriamente em pequenas bases de tal forma que é viável fornecer essas bases de tamanho menor a um ou vários algoritmos de AM simbólicos. Logo após, as regras que constituem os classificadores induzidos por esses algoritmos são combinadas em um único classificador. Para analisar a viabilidade do objetivo proposto, foi implementado um sistema na linguagem de programação lógica Prolog, com a finalidade de (a) avaliar regras de conhecimento induzidas por algoritmos de Aprendizado de Máquina simbólico e (b) avaliar diversas formas de combinar classificadores simbólicos bem como explicar a classificação de novos exemplos realizada por um ensemble de classificares simbólicos. A finalidade (a) é implementada pelo Módulo de Análise de Regras e a finalidade (b) pelo Módulo de Combinação e Explicação. Esses módulos constituem os módulos principais do RuleSystem. Neste trabalho, são descritos os métodos de construção de ensembles e de combinação de classificadores encontrados na literatura, o projeto e a documentação do RuleSystem, a metodologia desenvolvida para documentar o sistema RuleSystem, a implementação do Módulo de Combinação e Explicação, objeto de estudo deste trabalho, e duas aplicações do Módulo de Combinação e Explicação. A primeira aplicação utilizou uma base de dados artificiais, a qual nos permitiu observar necessidades de modificações no Módulo de Combinação e Explicação. A segunda aplicação utilizou uma base de dados reais. / The hypothesis quality induced by current machine learning algorithms depends mainly on the quantity and quality of features and examples used in the training phase. Frequently, hypothesis with low precision are obtained in experiments using large databases with a large number of irrelevant features. Thus, one active research area in machine learning is to investigate techniques able to extend the capacity of machine learning algorithms to process a large number of examples, features and classes. To learn concepts from large databases using machine learning algorithms, two approaches can be used. The first approach is based on a selection of relevant features and examples, and the second one is the ensemble approach. An ensemble is a set of classifiers whose individual decisions are combined in some way to classify a new case. Although ensembles classify new examples better than each individual classifier, they behave like black-boxes, since they do not offer any explanation to the user about their classification. The purpose of this work is to consider a form of symbolic classifiers combination to work with large databases. Given a large database, it is equally divided randomly in small databases. These small databases are supplied to one or more symbolic machine learning algorithms. After that, the rules from the resulting classifiers are combined into one classifier. To analise the viability of this proposal, was implemented a system in logic programming language Prolog, called RuleSystem. This system has two purposes; the first one, implemented by the Rule Analises Module, is to evaluate rules induced by symbolic machine learning algorithms; the second one, implemented by the Combination and Explanation Module, is to evaluate several forms of combining symbolic classifiers as well as to explain ensembled classification of new examples. Both principal modules constitute the Rule System. This work describes ensemble construction methods and combination of classifiers methods found in the literature; the project and documentation of RuleSystem; the methodology developed to document the RuleSystem; and the implementation of the Combination and Explanation Module. Two different case studies using the Combination and Explanation Module are described. The first case study uses an artificial database. Through the use of this artificial database, it was possible to improve several of the heuristics used by the the Combination and Explanation Module. A real database was used in the second case study.

A qualidade das hipóteses induzidas pelos atuais sistemas de Aprendizado de Máquina depende principalmente da quantidade e da qualidade dos atributos e exemplos utilizados no treinamento. Freqüentemente, resultados experimentais obtidos sobre grandes bases de dados, que possuem muitos atributos irrelevantes, resultam em hipóteses de baixa precisão. Por outro lado, muitos dos sistemas de aprendizado de máquina conhecidos não estão preparados para trabalhar com uma quantidade muito grande de exemplos. Assim, uma das áreas de pesquisa mais ativas em aprendizado de máquina tem girado em torno de técnicas que sejam capazes de ampliar a capacidade dos algoritmos de aprendizado para processar muitos exemplos de treinamento, atributos e classes. Para que conceitos sejam aprendidos a partir de grandes bases de dados utilizando Aprendizado de Máquina, pode-se utilizar duas abordagens. A primeira realiza uma seleção de exemplos e atributos mais relevantes, e a segunda ´e a abordagem de ensembles. Um ensemble ´e um conjunto de classificadores cujas decisões individuais são combinadas de alguma forma para classificar um novo caso. Ainda que ensembles classifiquem novos exemplos melhor que cada classificador individual, eles se comportam como caixas pretas, no sentido de n˜ao oferecer ao usuário alguma explicação relacionada à classificação por eles fornecida. O objetivo deste trabalho é propor uma forma de combinação de classificadores simbólicos, ou seja, classificadores induzidos por algoritmos de AM simbólicos, nos quais o conhecimento é descrito na forma de regras if-then ou equivalentes, para se trabalhar com grandes bases de dados. A nossa proposta é a seguinte: dada uma grande base de dados, divide-se esta base aleatoriamente em pequenas bases de tal forma que é viável fornecer essas bases de tamanho menor a um ou vários algoritmos de AM simbólicos. Logo após, as regras que constituem os classificadores induzidos por esses algoritmos são combinadas em um único classificador. Para analisar a viabilidade do objetivo proposto, foi implementado um sistema na linguagem de programação lógica Prolog, com a finalidade de (a) avaliar regras de conhecimento induzidas por algoritmos de Aprendizado de Máquina simbólico e (b) avaliar diversas formas de combinar classificadores simbólicos bem como explicar a classificação de novos exemplos realizada por um ensemble de classificares simbólicos. A finalidade (a) é implementada pelo Módulo de Análise de Regras e a finalidade (b) pelo Módulo de Combinação e Explicação. Esses módulos constituem os módulos principais do RuleSystem. Neste trabalho, são descritos os métodos de construção de ensembles e de combinação de classificadores encontrados na literatura, o projeto e a documentação do RuleSystem, a metodologia desenvolvida para documentar o sistema RuleSystem, a implementação do Módulo de Combinação e Explicação, objeto de estudo deste trabalho, e duas aplicações do Módulo de Combinação e Explicação. A primeira aplicação utilizou uma base de dados artificiais, a qual nos permitiu observar necessidades de modificações no Módulo de Combinação e Explicação. A segunda aplicação utilizou uma base de dados reais. / The hypothesis quality induced by current machine learning algorithms depends mainly on the quantity and quality of features and examples used in the training phase. Frequently, hypothesis with low precision are obtained in experiments using large databases with a large number of irrelevant features. Thus, one active research area in machine learning is to investigate techniques able to extend the capacity of machine learning algorithms to process a large number of examples, features and classes. To learn concepts from large databases using machine learning algorithms, two approaches can be used. The first approach is based on a selection of relevant features and examples, and the second one is the ensemble approach. An ensemble is a set of classifiers whose individual decisions are combined in some way to classify a new case. Although ensembles classify new examples better than each individual classifier, they behave like black-boxes, since they do not offer any explanation to the user about their classification. The purpose of this work is to consider a form of symbolic classifiers combination to work with large databases. Given a large database, it is equally divided randomly in small databases. These small databases are supplied to one or more symbolic machine learning algorithms. After that, the rules from the resulting classifiers are combined into one classifier. To analise the viability of this proposal, was implemented a system in logic programming language Prolog, called RuleSystem. This system has two purposes; the first one, implemented by the Rule Analises Module, is to evaluate rules induced by symbolic machine learning algorithms; the second one, implemented by the Combination and Explanation Module, is to evaluate several forms of combining symbolic classifiers as well as to explain ensembled classification of new examples. Both principal modules constitute the Rule System. This work describes ensemble construction methods and combination of classifiers methods found in the literature; the project and documentation of RuleSystem; the methodology developed to document the RuleSystem; and the implementation of the Combination and Explanation Module. Two different case studies using the Combination and Explanation Module are described. The first case study uses an artificial database. Through the use of this artificial database, it was possible to improve several of the heuristics used by the the Combination and Explanation Module. A real database was used in the second case study.

L'intelligence artificielle est la discipline de recherche d'imitation ou de remplacement de fonctions cognitives humaines. À ce titre, l'une de ses branches s'inscrit dans l'automatisation progressive du processus de programmation. Il s'agit alors de transférer de l'intelligence ou, à défaut de définition, de transférer de la charge cognitive depuis l'humain vers le système, qu'il soit autonome ou guidé par l'utilisateur. Dans le cadre de cette thèse, nous considérons les conditions de l'évolution depuis un système guidé par son utilisateur vers un système autonome, en nous appuyant sur une autre branche de l'intelligence artificielle : l'apprentissage artificiel. Notre cadre applicatif est celui de la conception d'un assistant opérationnel incrémental, c'est-à-dire d'un système capable de réagir à des requêtes formulées par l'utilisateur en adoptant les actions appropriées, et capable d'apprendre à le faire. Pour nos travaux, les requêtes sont exprimées en français, et les actions sont désignées par les commandes correspondantes dans un langage de programmation (ici, R ou bash). L'apprentissage du système est effectué à l'aide d'un ensemble d'exemples constitué par les utilisateurs eux-mêmes lors de leurs interactions. Ce sont donc ces derniers qui définissent, progressivement, les actions qui sont appropriées pour chaque requête, afin de rendre le système de plus en plus autonome. Nous avons collecté plusieurs ensembles d'exemples pour l'évaluation des méthodes d'apprentissage, en analysant et réduisant progressivement les biais induits. Le protocole que nous proposons est fondé sur l'amorçage incrémental des connaissances du système à partir d'un ensemble vide ou très restreint. Cela présente l'avantage de constituer une base de connaissances très représentative des besoins des utilisateurs, mais aussi l'inconvénient de n'aquérir qu'un nombre très limité d'exemples. Nous utilisons donc, après examen des performances d'une méthode naïve, une méthode de raisonnement à partir de cas : le raisonnement par analogie formelle. Nous montrons que cette méthode permet une précision très élevée dans les réponses du système, mais également une couverture relativement faible. L'extension de la base d'exemples par analogie est explorée afin d'augmenter la couverture des réponses données. Dans une autre perspective, nous explorons également la piste de rendre l'analogie plus tolérante au bruit et aux faibles différences en entrée en autorisant les approximations, ce qui a également pour effet la production de réponses incorrectes plus nombreuses. La durée d'exécution de l'approche par analogie, déjà de l'ordre de la seconde, souffre beaucoup de l'extension de la base et de l'approximation. Nous avons exploré plusieurs méthodes de segmentation des séquences en entrée afin de réduire cette durée, mais elle reste encore le principal obstacle à contourner pour l'utilisation de l'analogie formelle dans le traitement automatique de la langue. Enfin, l'assistant opérationnel incrémental fondé sur le raisonnement analogique a été testé en condition incrémentale simulée, afin d'étudier la progression de l'apprentissage du système au cours du temps. On en retient que le modèle permet d'atteindre un taux de réponse stable après une dizaine d'exemples vus en moyenne pour chaque type de commande. Bien que la performance effective varie selon le nombre total de commandes considérées, cette propriété ouvre sur des applications intéressantes dans le cadre incrémental du transfert depuis un domaine riche (la langue naturelle) vers un domaine moins riche (le langage de programmation). / Artificial Intelligence is the field of research aiming at mimicking or replacing human cognitive abilities. As such, one of its subfields is focused on the progressive automation of the programming process. In other words, the goal is to transfer cognitive load from the human to the system, whether it be autonomous or guided by the user. In this thesis, we investigate the conditions for making a user-guided system autonomous using another subfield of Artificial Intelligence : Machine Learning. As an implementation framework, we chose the design of an incremental operational assistant, that is a system able to react to natural language requests from the user with relevant actions. The system must also be able to learn the correct reactions, incrementally. In our work, the requests are in written French, and the associated actions are represented by corresponding instructions in a programming language (here R and bash). The learning is performed using a set of examples composed by the users themselves while interacting. Thus they progressively define the most relevant actions for each request, making the system more autonomous. We collected several example sets for evaluation of the learning methods, analyzing and reducing the inherent collection biases. The proposed protocol is based on incremental bootstrapping of the system, starting from an empty or limited knowledge base. As a result of this choice, the obtained knowledge base reflects the user needs, the downside being that the overall number of examples is limited. To avoid this problem, after assessing a baseline method, we apply a case base reasoning approach to the request to command transfer problem: formal analogical reasoning. We show that this method yields answers with a very high precision, but also a relatively low coverage. We explore the analogical extension of the example base in order to increase the coverage of the provided answers. We also assess the relaxation of analogical constraints for an increased tolerance of analogical reasoning to noise in the examples. The running delay of the simple analogical approach is already around 1 second, and is badly influenced by both the automatic extension of the base and the relaxation of the constraints. We explored several segmentation strategies on the input examples in order to reduce reduce this time. The delay however remains the main obstacle to using analogical reasoning for natural language processing with usual volumes of data. Finally, the incremental operational assistant based on analogical reasoning was tested in simulated incremental condition in order to assess the learning behavior over time. The system reaches a stable correct answer rate after a dozen examples given in average for each command type. Although the effective performance depends on the total number of accounted commands, this observation opens interesting applicative tracks for the considered task of transferring from a rich source domain (natural language) to a less rich target domain (programming language).

Em Aprendizado de Máquina - AM não existe um único algoritmo que é sempre melhor para todos os domínios de aplicação. Na prática, diversas pesquisas mostram que Redes Neurais Artificiais - RNAs têm um 'bias' indutivo apropriado para diversos domínios. Em razão disso, RNAs têm sido aplicadas na resolução de vários problemas com desempenho satisfatório. Sistemas de AM simbólico possuem um 'bias' indutivo menos flexível do que as RNAs. Enquanto que as RNAs são capazes de aprender qualquer função, sistemas de AM simbólico geralmente aprendem conceitos que podem ser descritos na forma de hiperplanos. Por outro lado, sistemas de AM simbólico representam o conceito induzido por meio de estruturas simbólicas, as quais são geralmente compreensíveis pelos seres humanos. Assim, sistemas de AM simbólico são preferíveis quando é essencial a compreensibilidade do conceito induzido. RNAs carecem da capacidade de explicar suas decisões, uma vez que o conhecimento é codificado na forma de valores de seus pesos e 'thresholds'. Essa codificação é difícil de ser interpretada por seres humanos. Em diversos domínios de aplicação, tal como aprovação de crédito e diagnóstico médico, prover uma explicação sobre a classificação dada a um determinado caso é de crucial importância. De um modo similar, diversos usuários de sistemas de AM simbólico desejam validar o conhecimento induzido, com o objetivo de assegurar que a generalização feita pelo algoritmo é correta. Para que RNAs sejam aplicadas em um maior número de domínios, diversos pesquisadores têm proposto métodos para extrair conhecimento compreensível de RNAs. As principais contribuições desta tese são dois métodos que extraem conhecimento simbólico de RNAs. Os métodos propostos possuem diversas vantagens sobre outros métodos propostos previamente, tal como ser aplicáveis a qualquer arquitetura ou algoritmo de aprendizado de RNAs supervisionadas. O primeiro método proposto utiliza sistemas de AM simbólico para extrair conhecimento de RNAs, e o segundo método proposto estende o primeiro, combinado o conhecimento induzido por diversos sistemas de AM simbólico por meio de um Algoritmo Genético - AG. Os métodos propostos são analisados experimentalmente em diversos domínios de aplicação. Ambos os métodos são capazes de extrair conhecimento simbólico com alta fidelidade em relação à RNA treinada. Os métodos propostos são comparados com o método TREPAN, apresentando resultados promissores. TREPAN é um método bastante conhecido para extrair conhecimento de RNAs. / In Machine Learning - ML there is not a single algorithm that is the best for all application domains. In practice, several research works have shown that Artificial Neural Networks - ANNs have an appropriate inductive bias for several domains. Thus, ANNs have been applied to a number of data sets with high predictive accuracy. Symbolic ML algorithms have a less flexible inductive bias than ANNs. While ANNs can learn any input-output mapping, i.e., ANNs have the universal approximation property, symbolic ML algorithms frequently learn concepts describing them using hyperplanes. On the other hand, symbolic algorithms are needed when a good understating of the decision process is essential, since symbolic ML algorithms express the knowledge induced using symbolic structures that can be interpreted and understood by humans. ANNs lack the capability of explaining their decisions since the knowledge is encoded as real-valued weights and biases of the network. This encoding is difficult to be interpreted by humans. In several application domains, such as credit approval and medical diagnosis, providing an explanation related to the classification given to a certain case is of crucial importance. In a similar way, several users of ML algorithms desire to validate the knowledge induced, in order to assure that the generalization made by the algorithm is correct. In order to apply ANNs to a larger number of application domains, several researches have proposed methods to extract comprehensible knowledge from ANNs. The primary contribution of this thesis consists of two methods that extract symbolic knowledge, expressed as decision rules, from ANNs. The proposed methods have several advantages over previous methods, such as being applicable to any architecture and supervised learning algorithm of ANNs. The first method uses standard symbolic ML algorithm to extract knowledge from ANNs, and the second method extends the first method by combining the knowledge induced by several symbolic ML algorithms through the application of a Genetic Algorithm - GA. The proposed methods are experimentally analyzed in a number of application domains. Results show that both methods are capable to extract symbolic knowledge having high fidelity with trained ANNs. The proposed methods are compared with TREPAN, showing promising results. TREPAN is a well known method to extract knowledge from ANNs.

Em Aprendizado de Máquina - AM não existe um único algoritmo que é sempre melhor para todos os domínios de aplicação. Na prática, diversas pesquisas mostram que Redes Neurais Artificiais - RNAs têm um 'bias' indutivo apropriado para diversos domínios. Em razão disso, RNAs têm sido aplicadas na resolução de vários problemas com desempenho satisfatório. Sistemas de AM simbólico possuem um 'bias' indutivo menos flexível do que as RNAs. Enquanto que as RNAs são capazes de aprender qualquer função, sistemas de AM simbólico geralmente aprendem conceitos que podem ser descritos na forma de hiperplanos. Por outro lado, sistemas de AM simbólico representam o conceito induzido por meio de estruturas simbólicas, as quais são geralmente compreensíveis pelos seres humanos. Assim, sistemas de AM simbólico são preferíveis quando é essencial a compreensibilidade do conceito induzido. RNAs carecem da capacidade de explicar suas decisões, uma vez que o conhecimento é codificado na forma de valores de seus pesos e 'thresholds'. Essa codificação é difícil de ser interpretada por seres humanos. Em diversos domínios de aplicação, tal como aprovação de crédito e diagnóstico médico, prover uma explicação sobre a classificação dada a um determinado caso é de crucial importância. De um modo similar, diversos usuários de sistemas de AM simbólico desejam validar o conhecimento induzido, com o objetivo de assegurar que a generalização feita pelo algoritmo é correta. Para que RNAs sejam aplicadas em um maior número de domínios, diversos pesquisadores têm proposto métodos para extrair conhecimento compreensível de RNAs. As principais contribuições desta tese são dois métodos que extraem conhecimento simbólico de RNAs. Os métodos propostos possuem diversas vantagens sobre outros métodos propostos previamente, tal como ser aplicáveis a qualquer arquitetura ou algoritmo de aprendizado de RNAs supervisionadas. O primeiro método proposto utiliza sistemas de AM simbólico para extrair conhecimento de RNAs, e o segundo método proposto estende o primeiro, combinado o conhecimento induzido por diversos sistemas de AM simbólico por meio de um Algoritmo Genético - AG. Os métodos propostos são analisados experimentalmente em diversos domínios de aplicação. Ambos os métodos são capazes de extrair conhecimento simbólico com alta fidelidade em relação à RNA treinada. Os métodos propostos são comparados com o método TREPAN, apresentando resultados promissores. TREPAN é um método bastante conhecido para extrair conhecimento de RNAs. / In Machine Learning - ML there is not a single algorithm that is the best for all application domains. In practice, several research works have shown that Artificial Neural Networks - ANNs have an appropriate inductive bias for several domains. Thus, ANNs have been applied to a number of data sets with high predictive accuracy. Symbolic ML algorithms have a less flexible inductive bias than ANNs. While ANNs can learn any input-output mapping, i.e., ANNs have the universal approximation property, symbolic ML algorithms frequently learn concepts describing them using hyperplanes. On the other hand, symbolic algorithms are needed when a good understating of the decision process is essential, since symbolic ML algorithms express the knowledge induced using symbolic structures that can be interpreted and understood by humans. ANNs lack the capability of explaining their decisions since the knowledge is encoded as real-valued weights and biases of the network. This encoding is difficult to be interpreted by humans. In several application domains, such as credit approval and medical diagnosis, providing an explanation related to the classification given to a certain case is of crucial importance. In a similar way, several users of ML algorithms desire to validate the knowledge induced, in order to assure that the generalization made by the algorithm is correct. In order to apply ANNs to a larger number of application domains, several researches have proposed methods to extract comprehensible knowledge from ANNs. The primary contribution of this thesis consists of two methods that extract symbolic knowledge, expressed as decision rules, from ANNs. The proposed methods have several advantages over previous methods, such as being applicable to any architecture and supervised learning algorithm of ANNs. The first method uses standard symbolic ML algorithm to extract knowledge from ANNs, and the second method extends the first method by combining the knowledge induced by several symbolic ML algorithms through the application of a Genetic Algorithm - GA. The proposed methods are experimentally analyzed in a number of application domains. Results show that both methods are capable to extract symbolic knowledge having high fidelity with trained ANNs. The proposed methods are compared with TREPAN, showing promising results. TREPAN is a well known method to extract knowledge from ANNs.