Submitted by Lucelia Lucena (lucelia.lucena@ufpe.br) on 2015-03-06T19:46:46Z No. of bitstreams: 2 DISSERTAÇÃO Denys Lins de Farias.pdf: 1587908 bytes, checksum: 56b81933533aed8f8d9f5f11c66976e1 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-06T19:46:47Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Denys Lins de Farias.pdf: 1587908 bytes, checksum: 56b81933533aed8f8d9f5f11c66976e1 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-09-04 / A diversão dos jogos digitais está relacionada com a proposição de níveis adequados de desafios, para que o jogador não se frustre com desafios muito difíceis, nem fique entediado com desafios muito fáceis. As soluções propostas na literatura para este problema, chamado de Ajuste Dinâmico de Dificuldade (Dynamic Difficulty Adjustment, DDA), utilizam agentes adaptativos que buscam adequar seu comportamento às capacidades do jogador humano contra quem jogam. Algumas técnicas (aprendizagem por reforço, algoritmos genéticos, Dynamic Scripting) podem ser adaptadas para que o agente atue de forma sub-ótima, isto é, que ele jogue menos bem diante de um jogador humano pouco experiente ou pouco habilidoso. Porém, quando se enfrenta jogadores muito experientes ou habilidosos, tais agentes não conseguem atuar no nível do jogador. Estas técnicas podem ser vistas, simplificadamente, como sistemas de regras condição-ação em que se pode aprender os pesos de tais regras ou criar novas regras. Nessa estrutura, existe uma classe de algoritmos de aprendizagem online, os chamados Sistemas Classificadores (SCs), que permite tanto aprender pesos de regras quanto criar novas regras, mas que, até onde sabemos, ainda não foi utilizada em DDA. Diante deste cenário, o objetivo deste trabalho foi de avaliar a aplicabilidade de SC a DDA. Como sabemos que SC, a exemplo de Dynamic Scripting, pode ser facilmente adaptada para ter um desempenho subótimo, nós nos focamos em avaliar se SC poderia ter uma competência melhor do que os outros, em particular do que aprendizagem por reforço, a melhor das técnicas em avaliação anterior. Para tanto, tivemos de enfrentar o conhecido problema da parametrização dos SCs, e o fizemos utilizando a técnica de otimização F-Race, o que gerou dois agentes baseados em SCs com parâmetros diferentes. Como caso de estudo, adotamos o jogo de luta em tempo real Knock’em, utilizado em outros trabalhos. Conduzimos um experimento para avaliar a competência entre os agentes baseados em SCs e um baseado em Q-Learning, contra agentes de comportamento aleatório e previsível. Os resultados indicaram que o agente parametrizado pelo F-Race obteve melhor desempenho que o agente de referência contra oponente previsível, perdendo contra o agente de comportamento aleatório. Verificamos a viabilidade do uso de SCs em DDA, em uma série de partidas, na qual o agente operou no nível dos oponentes, mas apresentou razoável variação nos resultados. Realizamos mais um experimento entre o agente proposto parametrizado pelo F-Race e o baseado em Q-Learning, contando com avaliação quantitativa e qualitativa. Ambos agentes apresentaram bons resultados, com o agente de referência obtendo maior vantagem inicial, porém os jogadores foram capazes de reverter a situação ao longo do experimento.

Classificação é, provavelmente, a tarefa mais estudada na área de Aprendizado de Máquina, possuindo aplicação em uma grande quantidade de problemas reais, como categorização de textos, diagnóstico médico, problemas de bioinformática, além de aplicações comerciais e industriais. De um modo geral, os problemas de classificação podem ser categorizados quanto ao número de rótulos de classe que podem ser associados à cada exemplo de entrada. A abordagem mais investigada pela comunidade de Aprendizado de Máquina é a de classes mutuamente exclusivas. Entretanto, existe uma grande variedade de problemas importantes em que cada exemplo de entrada pode ser associado a mais de um rótulo ou classe. Esses problemas são denominados problemas de classificação multirrótulo. Os Learning Classifier Systems(LCS) constituem uma técnica de Indução de Regras de Classificação que tem como principal mecanismo de busca um Algoritmo Genético. Essa técnica busca encontrar um conjunto de regras que tenha alta precisão de classificação, que seja compreensível e que possua regras consideradas interessantes sob o ponto de vista de classificação. Apesar de existirem na literatura diversos trabalhos sobre os LCS para problemas de classificação com classes mutuamente exclusivas, pouco se tem conhecimento sobre um LCS que seja capaz de lidar com problemas multirrótulo. Dessa maneira, o objetivo desta monografia é apresentar uma proposta de LCS para problemas multirrótulo, que pretende induzir um conjunto de regras de classificação que produza um resultado eficaz e comparável com outras técnicas de classificação. De acordo com esse objetivo, apresenta-se também uma revisão bibliográfica dos temas envolvidos na proposta, que são: Sistemas Classificadores Evolutivos e Classificação Multirrótulo / Classification is probably the most studied task in the Machine Learning area, with applications in a broad number of real problems like text categorization, medical diagnosis, bioinformatics and even comercial and industrial applications. Generally, classification problems can be categorized considering the number of class labels associated to each input instance. The most studied approach by the community of Machine Learning is the one that considers mutually exclusive classes. However, there is a large variety of important problems in which each instance can be associated to more than one class label. This problems are called multi-label classification problems. Learning Classifier Systems (LCS) are a technique for rule induction which uses a Genetic Algorithm as the primary search mechanism. This technique searchs for sets of rules that have high classification accuracy and that are also understandable and interesting on the classification point of view. Although there are several works on LCS for classification problems with mutually exclusive classes, there is no record of an LCS that can deal with the multi-label classification problem. The objective of this work is to propose an LCS for multi-label classification that builds a set of classification rules which achieves results that are efficient and comparable to other multi-label methods. In accordance with this objective this work also presents a review of the themes involved: Learning Classifier Systems and Multi-label Classification

Classificação é, provavelmente, a tarefa mais estudada na área de Aprendizado de Máquina, possuindo aplicação em uma grande quantidade de problemas reais, como categorização de textos, diagnóstico médico, problemas de bioinformática, além de aplicações comerciais e industriais. De um modo geral, os problemas de classificação podem ser categorizados quanto ao número de rótulos de classe que podem ser associados à cada exemplo de entrada. A abordagem mais investigada pela comunidade de Aprendizado de Máquina é a de classes mutuamente exclusivas. Entretanto, existe uma grande variedade de problemas importantes em que cada exemplo de entrada pode ser associado a mais de um rótulo ou classe. Esses problemas são denominados problemas de classificação multirrótulo. Os Learning Classifier Systems(LCS) constituem uma técnica de Indução de Regras de Classificação que tem como principal mecanismo de busca um Algoritmo Genético. Essa técnica busca encontrar um conjunto de regras que tenha alta precisão de classificação, que seja compreensível e que possua regras consideradas interessantes sob o ponto de vista de classificação. Apesar de existirem na literatura diversos trabalhos sobre os LCS para problemas de classificação com classes mutuamente exclusivas, pouco se tem conhecimento sobre um LCS que seja capaz de lidar com problemas multirrótulo. Dessa maneira, o objetivo desta monografia é apresentar uma proposta de LCS para problemas multirrótulo, que pretende induzir um conjunto de regras de classificação que produza um resultado eficaz e comparável com outras técnicas de classificação. De acordo com esse objetivo, apresenta-se também uma revisão bibliográfica dos temas envolvidos na proposta, que são: Sistemas Classificadores Evolutivos e Classificação Multirrótulo / Classification is probably the most studied task in the Machine Learning area, with applications in a broad number of real problems like text categorization, medical diagnosis, bioinformatics and even comercial and industrial applications. Generally, classification problems can be categorized considering the number of class labels associated to each input instance. The most studied approach by the community of Machine Learning is the one that considers mutually exclusive classes. However, there is a large variety of important problems in which each instance can be associated to more than one class label. This problems are called multi-label classification problems. Learning Classifier Systems (LCS) are a technique for rule induction which uses a Genetic Algorithm as the primary search mechanism. This technique searchs for sets of rules that have high classification accuracy and that are also understandable and interesting on the classification point of view. Although there are several works on LCS for classification problems with mutually exclusive classes, there is no record of an LCS that can deal with the multi-label classification problem. The objective of this work is to propose an LCS for multi-label classification that builds a set of classification rules which achieves results that are efficient and comparable to other multi-label methods. In accordance with this objective this work also presents a review of the themes involved: Learning Classifier Systems and Multi-label Classification