Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-03T12:49:19Z No. of bitstreams: 1 TeseMCD.pdf: 1564245 bytes, checksum: fbb9eb1099a1b38351371c97e8e49bb4 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2017-01-16T16:47:27Z (GMT) No. of bitstreams: 1 TeseMCD.pdf: 1564245 bytes, checksum: fbb9eb1099a1b38351371c97e8e49bb4 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2017-01-16T16:47:38Z (GMT) No. of bitstreams: 1 TeseMCD.pdf: 1564245 bytes, checksum: fbb9eb1099a1b38351371c97e8e49bb4 (MD5) / Made available in DSpace on 2017-01-16T16:47:46Z (GMT). No. of bitstreams: 1 TeseMCD.pdf: 1564245 bytes, checksum: fbb9eb1099a1b38351371c97e8e49bb4 (MD5) Previous issue date: 2016-01-04 / Não recebi financiamento / NELL is a computer system that has the goal of learn to learn 24 hours per day, continuously and learn more an better than the last day, to perform the knowledge base (KB). NELL is running since January 12 of 2010. Furthermore, NELL goals is have hight precision to be able to continue the learning. NELL is developed in macro-reading context, because this NELL needs very much redundancy to run. The first step to run NELL is to have an big (all-pairs-data). An all-pairs-data is a preprocessed base using Natural Language Processing (NLP), that base has all sufficient statistics about a corpus of web pages. The proposal of this project was to create a instance of NELL (currently in English) in Portuguese. For this, the first goal was the developing an all-pairs-data in Portuguese. The second step was to create a new version of Portuguese NELL. And finally, the third goal was to develop a coreference resolution hybrid method focused in features semantics and morphologics. This method is not dependent of a specific language, it is can be applied for another languages with the same alphabet of Portuguese language. The NELL in Portuguese was developed, but the all-pairs-data is not big enough. Because it Portuguese NELL is not running for ever, like the English version. Even so, this project present the steps about how to develop a NELL in other language and some ideas about how to improve the all-pairs-data. By the way, this project present a coreference resolution hybrid method with good results to NELL. / A NELL é um sistema de computador que possui o objetivo de executar 24 horas por dia, 7 dias por semana, sem parar. A versão atual da NELL foi iniciada em 12 de Janeiro de 2010 e continua ativa. Seu objetivo é aprender cada vez mais fatos da web para popular sua base de conhecimento (Knowlegde Base - KB). Além de aprender cada vez mais, a NELL também objetiva alcançar alta confiança no aprendizado para garantir a continuidade do aprendizado. A NELL foi desenvolvida e atua no contexto da macroleitura, no qual é necessária uma grande quantidade e redundância de dados. Para que o sistema possa aprender, o primeiro passo é criar uma base preprocessada (all-pairs-data) a partir do uso de técnicas linguísticas. O all-pairs-data deve possuir todas as estatísticas suficientes para a execução da NELL e também deve ser de um tamanho suficientemente grande para que o aprendizado possa ocorrer. Neste projeto, foi proposta a criação de uma nova instância da NELL em português. Inicialmente foi proposta a criação de um all-pairs-data e, em seguida, a criação de uma abordagem híbrida para a resolução de correferências independente de língua por base em características semânticas e morfológicas. A proposta híbrida objetivou aperfeiçoar o processo atual de tratamento de correferências na NELL, melhorando assim a confiabilidade no aprendizado. Todas as propostas foram desenvolvidas e a NELL em português obteve bons resultados. Tais resultados evidenciam que a leitura da web em português poderá se tornar um sistema de aprendizado sem-fim. Para que isso ocorra são também apresentadas as futuras abordagens e propostas. Além disso, este projeto apresenta a metodologia de criação da instância da NELL em português, uma proposta de resolução de correferência que explora atributos linguisticos,bem como a ontologia da NELL, além de apontar trabalhos futuros, nos quais inclui-se processos de adição de outras línguas na NELL, principalmente para aquelas que possuem poucas páginas web disponíveis para o aprendizado.

Made available in DSpace on 2014-12-17T14:56:04Z (GMT). No. of bitstreams: 1 DennisBA.pdf: 1210954 bytes, checksum: f42a19fb396d47e801ab673ab1f88887 (MD5) Previous issue date: 2005-10-14 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / In multi-robot systems, both control architecture and work strategy represent a challenge for researchers. It is important to have a robust architecture that can be easily adapted to requirement changes. It is also important that work strategy allows robots to complete tasks efficiently, considering that robots interact directly in environments with humans. In this context, this work explores two approaches for robot soccer team coordination for cooperative tasks development. Both approaches are based on a combination of imitation learning and reinforcement learning. Thus, in the first approach was developed a control architecture, a fuzzy inference engine for recognizing situations in robot soccer games, a software for narration of robot soccer games based on the inference engine and the implementation of learning by imitation from observation and analysis of others robotic teams. Moreover, state abstraction was efficiently implemented in reinforcement learning applied to the robot soccer standard problem. Finally, reinforcement learning was implemented in a form where actions are explored only in some states (for example, states where an specialist robot system used them) differently to the traditional form, where actions have to be tested in all states. In the second approach reinforcement learning was implemented with function approximation, for which an algorithm called RBF-Sarsa($lambda$) was created. In both approaches batch reinforcement learning algorithms were implemented and imitation learning was used as a seed for reinforcement learning. Moreover, learning from robotic teams controlled by humans was explored. The proposal in this work had revealed efficient in the robot soccer standard problem and, when implemented in other robotics systems, they will allow that these robotics systems can efficiently and effectively develop assigned tasks. These approaches will give high adaptation capabilities to requirements and environment changes. / Em sistemas multi-rob?s a arquitetura de controle e a estrat?gia de trabalho representam um desafio para os pesquisadores. ? importante que a arquitetura de controle seja robusta, de forma que se adapte naturalmente ?s mudan?as nas caracter?sticas do problema e tamb?m que a estrat?gia de trabalho permita aos rob?s desenvolver as tarefas atribu?das eficaz e eficientemente, levando em considera??o a restri??o de que os rob?s v?o interagir diretamente em ambientes povoados de seres humanos. Neste contexto, este trabalho explora duas abordagens para a coordena??o de uma frota de rob?s desenvolvendo tarefas cooperativas. Ambas as abordagens s?o baseadas em uma mistura de aprendizado por imita??o e por experi?ncia. Assim, na primeira abordagem desenvolveu-se uma arquitetura de controle, uma m?quina de infer?ncia difusa para reconhecimento de fatos em jogos de futebol, um software narrador de jogos baseado na m?quina de infer?ncia difusa, e a implementa??o de aprendizado por imita??o a partir de observa??o e an?lise de outros times rob?ticos. Al?m disso, aplicou-se eficientemente abstra??o de estados em aprendizado por refor?o no problema padr?o de futebol de rob?s. Finalmente, o aprendizado por refor?o foi implementado de forma que as a??es somente s?o executadas em certos estados (por exemplo os estados onde algum sistema rob?tico especialista j? as utilizou) diferentemente da forma tradicional onde as a??es no banco de conhecimento t?m que ser testadas em todos os estados. No caso da segunda abordagem, implementou-se aprendizado por refor?o com aproxima??o de fun??es, para o que foi criado um algoritmo chamado RBF-Sarsa($lambda$). Em ambas as abordagens implementou-se o aprendizado por refor?o em lotes e o aprendizado por imita??o como semente para aprendizado por refor?o. Al?m disso, explorou-se o aprendizado com times de rob?s controlados por seres humanos. As propostas deste trabalho mostraram-se eficientes no problema padr?o de futebol de rob?s, e ao serem implementadas em outros sistemas rob?ticos permitir?o que os mesmos sejam eficazes e eficientes no desenvolvimento das tarefas atribu?das com um alto grau de adapta??o ?s mudan?as dos requerimentos e do ambiente.

[pt] Predição de porosidade em reservatórios de óleo e gás representa em uma tarefa crucial e desafiadora na indústria de petróleo. Neste trabalho é proposto um novo modelo não-linear para predição de porosidade que trata fácies sedimentares como variáveis ocultas ou latentes. Esse modelo, denominado Transductive Conditional Random Field Regression (TCRFR), combina com sucesso os conceitos de Markov random fields, ridge regression e aprendizado transdutivo. O modelo utiliza volumes de impedância sísmica como informação de entrada condicionada aos valores de porosidade disponíveis nos poços existentes no reservatório e realiza de forma simultânea e automática a classificação das fácies e a estimativa de porosidade em todo o volume. O método é capaz de inferir as fácies latentes através da combinação de amostras precisas de porosidade local presentes nos poços com dados de impedância sísmica ruidosos, porém disponíveis em todo o volume do reservatório. A informação precisa de porosidade é propagada no volume através de modelos probabilísticos baseados em grafos, utilizando conditional random fields. Adicionalmente, duas novas técnicas são introduzidas como etapas de pré-processamento para aplicação do método TCRFR nos casos extremos em que somente um número bastante reduzido de amostras rotuladas de porosidade encontra-se disponível em um pequeno conjunto de poços exploratórios, uma situação típica para geólogos durante a fase exploratória de uma nova área. São realizados experimentos utilizando dados de um reservatório sintético e de um reservatório real. Os resultados comprovam que o método apresenta um desempenho consideravelmente superior a outros métodos automáticos de predição em relação aos dados sintéticos e, em relação aos dados reais, um desempenho comparável ao gerado por técnicas tradicionais de geo estatística que demandam grande esforço manual por parte de especialistas. / [en] Estimating porosity in oil and gas reservoirs is a crucial and challenging task in the oil industry. A novel nonlinear model for porosity estimation is proposed, which handles sedimentary facies as latent variables. It successfully combines the concepts of conditional random fields (CRFs), transductive learning and ridge regression. The proposed Transductive Conditional Random Field Regression (TCRFR) uses seismic impedance volumes as input information, conditioned on the porosity values from the available wells in the reservoir, and simultaneously and automatically provides as output the porosity estimation and facies classification in the whole volume. The method is able to infer the latent facies states by combining the local, labeled and accurate porosity information available at well locations with the plentiful but imprecise impedance information available everywhere in the reservoir volume. That accurate information is propagated in the reservoir based on conditional random field probabilistic graphical models, greatly reducing uncertainty. In addition, two new techniques are introduced as preprocessing steps for the application of TCRFR in the extreme but realistic cases where just a scarce amount of porosity labeled samples are available in a few exploratory wells, a typical situation for geologists during the evaluation of a reservoir in the exploration phase. Both synthetic and real-world data experiments are presented to prove the usefulness of the proposed methodology, which show that it outperforms previous automatic estimation methods on synthetic data and provides a comparable result to the traditional manual labored geostatistics approach on real-world data.

O aprendizado de máquina consiste de conceitos e técnicas que permitem aos computadores melhorar seu desempenho com a experiência, ou, em outras palavras, aprender com dados. Um dos principais tópicos do aprendizado de máquina é o agrupamento de dados que, como o nome sugere, procura agrupar os dados de acordo com sua similaridade. Apesar de sua definição relativamente simples, o agrupamento é uma tarefa computacionalmente complexa, tornando proibitivo o emprego de algoritmos exaustivos, na busca pela solução ótima do problema. A importância do agrupamento de dados, aliada aos seus desafios, faz desse campo um ambiente de intensa pesquisa. Também a classe de fenômenos naturais conhecida como comportamento coletivo tem despertado muito interesse. Isso decorre da observação de um estado organizado e global que surge espontaneamente das interações locais presentes em grandes grupos de indivíduos, caracterizando, pois, o que se chama auto-organização ou emergência, para ser mais preciso. Os desafios intrínsecos e a relevância do tema vêm motivando sua pesquisa em diversos ramos da ciência e da engenharia. Ao mesmo tempo, técnicas baseadas em comportamento coletivo vêm sendo empregadas em tarefas de aprendizado de máquina, mostrando-se promissoras e ganhando bastante atenção. No presente trabalho, objetivou-se o desenvolvimento de técnicas de agrupamento baseadas em comportamento coletivo. Faz-se cada item do conjunto de dados corresponder a um indivíduo, definem-se as leis de interação local, e então os indivíduos são colocados a interagir entre si, de modo que os padrões que surgem reflitam os padrões originalmente presentes no conjunto de dados. Abordagens baseadas em dinâmica de troca de energia foram propostas. Os dados permanecem fixos em seu espaço de atributos, mas carregam certa informação a energia , a qual é progressivamente trocada entre eles. Os grupos são estabelecidos entre dados que tomam estados de energia semelhantes. Este trabalho abordou também o aprendizado semissupervisionado, cuja tarefa é rotular dados em bases parcialmente rotuladas. Nesse caso, foi adotada uma abordagem baseada na movimentação dos próprios dados pelo espaço de atributos. Procurou-se, durante todo este trabalho, não apenas propor novas técnicas de aprendizado, mas principalmente, por meio de muitas simulações e ilustrações, mostrar como elas se comportam em diferentes cenários, num esforço em mostrar onde reside a vantagem de se utilizar a dinâmica coletiva na concepção dessas técnicas / Machine learning consists of concepts and techniques that enable computers to improve their performance with experience, i.e., enable computers to learn from data. Data clustering (or just clustering) is one of its main topics, which aims to group data according to their similarities. Regardless of its simple definition, clustering is a complex computational task. Its relevance and challenges make this field an environment of intense research. The class of natural phenomena known as collective behavior has also attracted much interest. This is due to the observation that global patterns may spontaneously arise from local interactions among large groups of individuals, what is know as self-organization (or emergence). The challenges and relevance of the subject are encouraging its research in many branches of science and engineering. At the same time, techniques based on collective behavior are being employed in machine learning tasks, showing to be promising. The objective of the present work was to develop clustering techniques based on collective behavior. Each dataset item corresponds to an individual. Once the local interactions are defined, the individuals begin to interact with each other. It is expected that the patterns arising from these interactions match the patterns originally present in the dataset. Approaches based on dynamics of energy exchange have been proposed. The data are kept fixed in their feature space, but they carry some sort of information (the energy), which is progressively exchanged among them. The groups are established among data that take similar energy states. This work has also addressed the semi-supervised learning task, which aims to label data in partially labeled datasets. In this case, it has been proposed an approach based on the motion of the data themselves around the feature space. More than just providing new machine learning techniques, this research has tried to show how the techniques behave in different scenarios, in an effort to show where lies the advantage of using collective dynamics in the design of such techniques

Métodos baseados em grafos consistem em uma poderosa forma de representação e abstração de dados que proporcionam, dentre outras vantagens, representar relações topológicas, visualizar estruturas, representar grupos de dados com formatos distintos, bem como, fornecer medidas alternativas para caracterizar os dados. Esse tipo de abordagem tem sido cada vez mais considerada para solucionar problemas de aprendizado de máquina, principalmente no aprendizado não supervisionado, como agrupamento de dados, e mais recentemente, no aprendizado semissupervisionado. No aprendizado supervisionado, por outro lado, o uso de algoritmos baseados em grafos ainda tem sido pouco explorado na literatura. Este trabalho apresenta um algoritmo não paramétrico baseado em grafos para problemas de classificação com distribuição estacionária, bem como sua extensão para problemas que apresentam distribuição não estacionária. O algoritmo desenvolvido baseia-se em dois conceitos, a saber, 1) em uma estrutura chamada grafo K-associado ótimo, que representa o conjunto de treinamento como um grafo esparso e dividido em componentes; e 2) na medida de pureza de cada componente, que utiliza a estrutura do grafo para determinar o nível de mistura local dos dados em relação às suas classes. O trabalho também considera problemas de classificação que apresentam alteração na distribuição de novos dados. Este problema caracteriza a mudança de conceito e degrada o desempenho do classificador. De modo que, para manter bom desempenho, é necessário que o classificador continue aprendendo durante a fase de aplicação, por exemplo, por meio de aprendizado incremental. Resultados experimentais sugerem que ambas as abordagens apresentam vantagens na classificação de dados em relação aos algoritmos testados / Graph-based methods consist in a powerful form for data representation and abstraction which provides, among others advantages, representing topological relations, visualizing structures, representing groups of data with distinct formats, as well as, supplying alternative measures to characterize data. Such approach has been each time more considered to solve machine learning related problems, mainly concerning unsupervised learning, like clustering, and recently, semi-supervised learning. However, graph-based solutions for supervised learning tasks still remain underexplored in literature. This work presents a non-parametric graph-based algorithm suitable for classification problems with stationary distribution, as well as its extension to cope with problems of non-stationary distributed data. The developed algorithm relies on the following concepts, 1) a graph structure called optimal K-associated graph, which represents the training set as a sparse graph separated into components; and 2) the purity measure for each component, which uses the graph structure to determine local data mixture level in relation to their classes. This work also considers classification problems that exhibit modification on distribution of data flow. This problem qualifies concept drift and worsens any static classifier performance. Hence, in order to maintain accuracy performance, it is necessary for the classifier to keep learning during application phase, for example, by implementing incremental learning. Experimental results, concerning both algorithms, suggest that they had presented advantages over the tested algorithms on data classification tasks

[pt] Esta dissertação de mestrado consiste em um estudo avançado sobre aprendizado profundo por reforço visual para robôs autônomos através de técnicas de transferência de aprendizado. Os ambientes de simulação testados neste estudo são ambientes realistas complexos onde o robô tinha como desafio aprender e transferir conhecimento em diferentes contextos para aproveitar a experiência de ambientes anteriores em ambientes futuros. Este tipo de abordagem, além de agregar conhecimento ao robô autônomo, diminui o número de épocas de treinamento do algoritmo, mesmo em ambientes complexos, justificando o uso de técnicas de transferência de aprendizado. / [en] This master s thesis consists of an advanced study on deep learning by visual reinforcement for autonomous robots through transfer learning techniques. The simulation environments tested in this study are highly realistic environments where the challenge of the robot was to learn and tranfer knowledge in different contexts to take advantage of the experiencia of previous environments in future environments. This type of approach besides adding knowledge to the autonomous robot reduces the number of training epochs the algorithm, even in complex environments, justifying the use of transfer learning techniques.

[pt] O aprendizado supervisionado é, hoje, o ramo do aprendizado de máquina central para a maioria das inovações nos negócios. A abordagem depende de ter grandes quantidades de dados rotulados, suficiente para ajustar funções com a precisão necessária. No entanto, pode ser caro obter dados rotulados ou criar os rótulos através de um processo de anotação. O aprendizado semisupervisionado (SSL) é usado para rotular com precisão os dados a partir de pequenas quantidades de dados rotulados utilizando técnicas de aprendizado não supervisionado. Uma técnica de rotulagem é a propagação de rótulos. Neste trabalho, usamos especificamente o algoritmo Consensus rate-based label propagation (CRLP). Este algoritmo depende do uma função de consenso para a propagação. Uma possível função de consenso é a matriz de co-associação que estima a probabilidade dos pontos i e j pertencem ao mesmo grupo. Neste trabalho, observamos que a matriz de co-associação contém informações valiosas para tratar esse tipo de problema. Quando nenhum dado está rotulado, é comum escolher aleatoriamente, com probabilidade uniforme, os dados a serem rotulados manualmente, a partir dos quais a propagação procede. Este trabalho aborda o problema de seleção de um conjunto de tamanho fixo de dados para serem rotulados manualmente que propiciem uma melhor precisão no algoritmo de propagação de rótulos. Três técnicas de seleção, baseadas em princípios de amostragem estocástica, são propostas: Stratified Sampling (SS), Probability (P), and Stratified Sampling - Probability (SSP). Eles são todos baseados nas informações embutidas na matriz de co-associação. Os experimentos foram realizados em 15 conjuntos de benchmarks e mostraram resultados muito interessantes. Não só, porque eles fornecem uma seleção mais equilibrada quando comparados a uma seleção aleatória, mas também melhoram os resultados de precisão na propagação de rótulos. Em outro contexto, essas estratégias também foram testadas dentro de um processo de aprendizagem ativa, obtendo também bons resultados. / [en] Supervised learning is, today, the branch of Machine Learning central to most business disruption. The approach relies on having amounts of labeled data large enough to learn functions with the required approximation. However, labeled data may be expensive, to obtain or to construct through a labeling process. Semi-supervised learning (SSL) strives to label accurately data from small amounts of labeled data and the use of unsupervised learning techniques. One labeling technique is label propagation. We use specifically the Consensus rate-based label propagation (CRLP) in this work. A consensus function is central to the propagation. A possible consensus function is a coassociation matrix that estimates the probability of data points i and j belong to the same group. In this work, we observe that the co-association matrix has valuable information embedded in it. When no data is labeled, it is common to choose with a uniform probability randomly, the data to manually label, from which the propagation proceeds. This work addresses the problem of selecting a fixed-size set of data points to label (manually), to improve the label propagation algorithm s accuracy. Three selection techniques, based on stochastic sampling principles, are proposed: Stratified Sampling (SP), Probability (P), and Stratified Sampling - Probability (SSP). They are all based on the information embedded in the co-association matrix. Experiments were carried out on 15 benchmark sets and showed exciting results. Not only because they provide a more balanced selection when compared to a uniform random selection, but also improved the accuracy results of a label propagation method. These strategies were also tested inside an active learning process in a different context, also achieving good results.

[pt] Este trabalho busca usar o comitê de algoritmos de aprendizado por reforço profundo (deep reinforcement learning) sob uma nova perspectiva. Na literatura, a técnica de comitê é utilizada para melhorar o desempenho, mas, pela primeira vez, esta pesquisa visa utilizar comitê para minimizar a dependência do desempenho de aprendizagem por reforço profundo no ajuste fino de hiperparâmetros, além de tornar o aprendizado mais preciso e robusto. Duas abordagens são pesquisadas; uma considera puramente a agregação de ação, enquanto que a outra também leva em consideração as funções de valor. Na primeira abordagem, é criada uma estrutura de aprendizado online com base no histórico de escolha de ação contínua do comitê com o objetivo de integrar de forma flexível diferentes métodos de ponderação e agregação para as ações dos agentes. Em essência, a estrutura usa o desempenho passado para combinar apenas as ações das melhores políticas. Na segunda abordagem, as políticas são avaliadas usando seu desempenho esperado conforme estimado por suas funções de valor. Especificamente, ponderamos as funções de valor do comitê por sua acurácia esperada, calculada pelo erro da diferença temporal. As funções de valor com menor erro têm maior peso. Para medir a influência do esforço de ajuste do hiperparâmetro, grupos que consistem em uma mistura de diferentes quantidades de algoritmos bem e mal parametrizados foram criados. Para avaliar os métodos, ambientes clássicos como o pêndulo invertido, cart pole e cart pole duplo são usados como benchmarks. Na validação, os ambientes de simulação Half Cheetah v2, um robô bípede, e o Swimmer v2 apresentaram resultados superiores e consistentes demonstrando a capacidade da técnica de comitê em minimizar o esforço necessário para ajustar os hiperparâmetros dos algoritmos. / [en] This work seeks to use ensembles of deep reinforcement learning algorithms from a new perspective. In the literature, the ensemble technique is used to improve performance, but, for the first time, this research aims to use ensembles to minimize the dependence of deep reinforcement learning performance on hyperparameter fine-tuning, in addition to making it more precise and robust. Two approaches are researched; one considers pure action aggregation, while the other also takes the value functions into account. In the first approach, an online learning framework based on the ensemble s continuous action choice history is created, aiming to flexibly integrate different scoring and aggregation methods for the agents actions. In essence, the framework uses past performance to only combine the best policies actions. In the second approach, the policies are evaluated using their expected performance as estimated by their value functions. Specifically, we weigh the ensemble s value functions by their expected accuracy as calculated by the temporal difference error. Value functions with lower error have higher weight. To measure the influence on the hyperparameter tuning effort, groups consisting of a mix of different amounts of well and poorly parameterized algorithms were created. To evaluate the methods, classic environments such as the inverted pendulum, cart pole and double cart pole are used as benchmarks. In validation, the Half Cheetah v2, a biped robot, and Swimmer v2 simulation environments showed superior and consistent results demonstrating the ability of the ensemble technique to minimize the effort needed to tune the the algorithms.

[pt] Essa tese é composta por dois capítulos. O primeiro deles refere-se ao problema de aprendizado sequencial, útil em diversos campos de pesquisa e aplicações práticas. Exemplos incluem problemas de apreçamento dinâmico, desenhos de leilões e de incentivos, além de programas e tratamentos sequenciais. Neste capítulo, propomos a extensão de uma das mais populares regras de aprendizado, epsilon-greedy, para contextos de alta-dimensão, levando em consideração uma diretriz conservadora. Em particular, nossa proposta consiste em alocar parte do tempo que a regra original utiliza na adoção de ações completamente novas em uma busca focada em um conjunto restrito de ações promissoras. A regra resultante pode ser útil para aplicações práticas nas quais existem restrições suaves à adoção de ações não-usuais, mas que eventualmente, valorize surpresas positivas, ainda que a uma taxa decrescente. Como parte dos resultados, encontramos limites plausíveis, com alta probabilidade, para o remorso cumulativo para a regra epsilon-greedy conservadora em alta-dimensão. Também, mostramos a existência de um limite inferior para a cardinalidade do conjunto de ações viáveis que implica em um limite superior menor para o remorso da regra conservadora, comparativamente a sua versão não-conservadora. Adicionalmente, usuários finais possuem suficiente flexibilidade em estabelecer o nível de segurança que desejam, uma vez que tal nível não impacta as propriedades teóricas da regra de aprendizado proposta. Ilustramos nossa proposta tanto por meio de simulação, quanto por meio de um exercício utilizando base de dados de um problema real de sistemas de classificação. Por sua vez, no segundo capítulo, investigamos efeitos de tratamento determinísticos quando a regra de aloção é complexa e desconhecida, talvez por razões éticas, ou para evitar manipulação ou competição desnecessária. Mais especificamente, com foco na metodologia de regressão discontínua sharp, superamos a falta de conhecimento de pontos de corte na alocação de unidades, pela implementação de uma floresta de árvores de classificação, que também utiliza aprendizado sequencial na sua construção, para garantir que, assintoticamente, as regras de alocação desconhecidas sejam identificadas corretamente. A estrutura de árvore também é útil nos casos em que a regra de alocação desconhecida é mais complexa que as tradicionais univariadas. Motivado por exemplos da vida prática, nós mostramos nesse capítulo que, com alta probabilidade e baseado em premissas razoáveis, é possível estimar consistentemente os efeitos de tratamento sob esse cenário. Propomos ainda um algoritmo útil para usuários finais que se mostrou robusto para diferentes especificações e que revela com relativa confiança a regra de alocação anteriormente desconhecida. Ainda, exemplificamos os benefícios da metodologia proposta pela sua aplicação em parte do P900, um programa governamental Chileno de suporte para escolas, que se mostrou adequado ao cenário aqui estudado. / [en] Sequential learning problems are common in several fields of research and practical applications. Examples include dynamic pricing and assortment, design of auctions and incentives and permeate a large number of sequential treatment experiments. In this essay, we extend one of the most popular learning solutions, the epsilon-greedy heuristics, to high-dimensional contexts considering a conservative directive. We do this by allocating part of the time the original rule uses to adopt completely new actions to a more focused search in a restrictive set of promising actions. The resulting rule might be useful for practical applications that still values surprises, although at a decreasing rate, while also has restrictions on the adoption of unusual actions. With high probability, we find reasonable bounds for the cumulative regret of a conservative high-dimensional decaying epsilon-greedy rule. Also, we provide a lower bound for the cardinality of the set of viable actions that implies in an improved regret bound for the conservative version when compared to its non-conservative counterpart. Additionally, we show that end-users have sufficient flexibility when establishing how much safety they want, since it can be tuned without impacting theoretical properties. We illustrate our proposal both in a simulation exercise and using a real dataset. The second essay studies deterministic treatment effects when the assignment rule is both more complex than traditional ones and unknown to the public perhaps, among many possible causes, due to ethical reasons, to avoid data manipulation or unnecessary competition. More specifically, sticking to the well-known sharp RDD methodology, we circumvent the lack of knowledge of true cutoffs by employing a forest of classification trees which also uses sequential learning, as in the last essay, to guarantee that, asymptotically, the true unknown assignment rule is correctly identified. The tree structure also turns out to be suitable if the program s rule is more sophisticated than traditional univariate ones. Motivated by real world examples, we show in this essay that, with high probability and based on reasonable assumptions, it is possible to consistently estimate treatment effects under this setup. For practical implementation we propose an algorithm that not only sheds light on the previously unknown assignment rule but also is capable to robustly estimate treatment effects regarding different specifications imputed by end-users. Moreover, we exemplify the benefits of our methodology by employing it on part of the Chilean P900 school assistance program, which proves to be suitable for our framework.

[pt] Esta dissertação investiga a aplicação dos métodos de Reinforcement Learning na descoberta de rotas ótimas em uma rede de comunicação. Uma rede de comunicação real possui um comportamento dinâmico, mudando seu estado com o tempo. Os algoritmos de roteamento devem, portanto, oferecer rapidez na resposta às mudanças do estado da rede. O objetivo do trabalho é avaliar a aplicação de técnicas de Reinforcement Learning (RL) como base de algoritmos adaptativos de roteamento de pacotes. O problema de roteamento de pacotes sob a visão de RL consiste na definição de cada nó na rede como um agente RL, sendo que este agente deve definir ações de forma a minimizar uma função objetivo que pode ser o tempo de roteamento dos pacotes. Um dos objetivos do RL é precisamente aprender a tomar as ações que minimizem uma função. O trabalho consistiu de 4 etapas principais: um estudo sobre a área de Reinforcement Learning (RL); um estudo sobre a área de redes de comunicação e roteamento de pacotes; a modelagem do problema de roteamento como um sistema RL e implementação de diferentes métodos de RL para obter algoritmos de roteamento; e o estudo de casos. O estudo na área de Reinforcement Learning abrangeu desde as definições mais fundamentais: suas características, os elementos de um sistema RL e modelagem do ambiente como um Processo de Decisão de Markov, até os métodos básicos de solução: Programação Dinâmica, método de Monte Carlo, e o método de Diferenças Temporais. Neste último método, foram considerados dois algoritmos específicos: TD e Q-Learning. Em seguida, foi avaliado o parâmetro Eligibility Traces como uma alternativa para apressar o processo de aprendizado, obtendo o TD(lambda) e o Q(lambda) respectivamente. O estudo sobre Redes de Comunicação e Roteamento de pacotes envolveu os conceitos básicos de redes de comunicações, comutação por pacotes, a questão do roteamento de pacotes e os algoritmos existentes adaptativos e não adaptativos, que são utilizados na atualidade. Nas redes de comunicação, definidas como um conjunto de nós ligados através de enlaces de comunicação, para se enviar uma mensagem de um nó a outro, geralmente, a mensagem é quebrada em pedaços, chamados pacotes, e enviados através de outros nós, até chegar ao destino. Deste modo surge o problema de escolher os nós que levem o pacote o mais rápido possível até o nó destino. Os algoritmos analisados foram: Shortest Path Routing que procura os caminhos com menor número de nós intermediários, não sendo sensível às mudanças na carga nem na topologia da rede; Weighted Shortest Path Routing, que oferece um melhor desempenho a partir de uma visão global do estado da rede, que nem sempre é fácil de obter em redes reais e o algoritmo de Bellman-Ford, baseado em decisões de roteamento locais e atualizações periódicas, com algumas limitações para obter políticas em altas cargas. Este último é um dos algoritmos mais utilizados na atualidade, sendo base de muitos protocolos de roteamento existentes. A modelagem do problema de roteamento como um sistema RL foi inspirada por uma característica na definição de um sistema RL: um agente que interage com o ambiente e aprende a atingir um objetivo. Assim, a modelagem dos algoritmos tem como objetivo aprender a descobrir as rotas que minimizem o tempo de roteamento de pacotes desde uma origem até um dado destino. A avaliação de uma rota escolhida não pode ser obtida antes que o pacote alcance o seu destino final. Este fato faz com que os processos de aprendizado supervisionado tenham dificuldade de se aplicar a esse problema. Por outro lado, o Reinforcement Learning não necessita de um par entrada-resposta para fazer o aprendizado, permitindo-lhe abordar o problema com relativa facilidade. Na modelagem efetuada, cada nó na rede se comporta como um agente de RL que age na própria rede, a qual é o ambiente. A informação das rotas é armazenada nas funções de valor existentes em todos os nós da rede para / [en] This dissertation investigates the application of Reinforcement Learning methods to the discovery of optimal routes in communication networks. Any current communication network displays dynamic behavior, changing its states over time. Therefore, the routing algorithms must react swiftly to changes in the network status. The objective of this work is to evaluate the application of some Reinforcement Learning techniques to define adaptive packet routing algorithms. The packet routing problem under the RL vision consists in the definition of each node on network as an RL agent. Thus, each agent must take actions in order to minimize an objective function such as end to end packet routing delay. One main objective of the RL is precisely learning to take the actions that minimize a given function. This thesis is consists of 4 main parts: first, a study of Reinforcement Learning (RL); a study of the communication networks and packet routing; the routing problem model as a RL system and the implementation of several RL methods in order to obtain some routing algorithms; e finally, the case study. The study of Reinforcement Learning extends from the more basic definitions, Reinforcement Learning features, elements of a RL system and environment modeling as a Markovian Decision Process, to the basic methods of solution: Dynamic Programming, Monte Carlo methods and Temporal Differences methods. In this last case, two specific algorithms have been considered: TD and Q-Learning, and, finally, the Eligibility Traces are evaluated as a useful tool that permits us to accelerate the learning process leading to the TD(lambda) and the Q(lambda) routing algorithms. The study on communication networks and packet routing involves the foundations of communication networks, packet switching, the packet routing problem, and adaptive and non- adaptive routing algorithms used at the present time. Communication networks are defined as a set of nodes connected through communication links. In order to send a message from a source node to a destination node usually the message is broken into segments called packets, and these are sent through other nodes until arriving at the destination. In this way the problem appears to choose the path which takes the shortest possible time for the packet to reach the destination node. The following algorithms have been analyzed: Shortest Path Routing that looks for paths with minimal hop number, not being sensible to the changes of load level and network topology; Weighted Shortest Path Routing that offers better performance from a global vision of the state of the network, which is not always easy to get in real networks; on the other hand, the Bellman- Ford routing algorithm was studied, this is based on local routing decisions and periodic updates, with some limitations to obtain policies in high load conditions. Bellman-Ford is one of the algorithms most used at the present time, being the basis for many existing routing protocols. The modeling of the routing problem as a RL system was inspired by one of the main features of the definition of an RL system: an agent who interacts with the environment and learns to reach an objective; therefore, the modeling of the routing algorithms has as its objective to learn to discover the paths that minimize packet routing time from an origin to an destination. The evaluation of a chosen route cannot be completed before the package reaches its final destination. This fact implies that supervised learning cannot be applied to the routing problem. On the other hand, Reinforcement Learning does not need a input-output pair for the learning process, allowing it to approach the problem with relative ease. In the modeling, each network node is viewed as a RL agent that acts in the same network; the network is the environment. The routing information is stored in the existing value functions in all nodes in the network, for each node and all another destination node / [es] Esta disertación investiga la aplicación de los métodos de Reinforcement Learning en la determinación de rutas óptimas en una red de comunicación. Una red de comunicación real posee un comportamiento dinámico, donde su estado varia en el tiempo. Los algoritmos de ruta óptima deben, por lo tanto, ofrecer rapidez en la respuesta a las variaciones del estado de la red. El objetivo de este trabajo es evaluar la aplicación de técnicas de Reinforcement Learning (RL) como base de algoritmos adaptativos de problemas de ruteamiento en redes. Este problema consiste en la definición de cada nodo de la red como un agente RL. Este agente debe definir acciones de modo a minimizar una función objetivo que puede ser el tiempo de ruteamiento. El trabajo consta de 4 etapas principais: un estudio sobre el área de Reinforcement Learning (RL); un estudio sobre redes de comunicación y problema de ruteamiento; el modelo de ruta óptima como un sistema RL y la implementación de diferentes métodos de RL para obtener algoritmos de ruta óptima; y un estudio de casos. El estudio en el área de Reinforcement Learning va desde las definiciones fundamentales: características, elementos de un sistema RL y modelaje del ambiente como un Proceso de Decisión de Markov, hasta los métodos básicos de solución: Programación Dinámica, método de Monte Carlo, y método de Diferencias Temporales. En este último método, fueron considerados dos algoritmos específicos: TD e Q-Learning. A seguir, fue evaluado el parámetro Eligibility Traces como una alternativa para agilizar el proceso de aprendizaje, obteniendo el TD(lambda) y el Q(lambda) respectivamente. El estudio sobre Redes de Comunicación y Problema de Transporte incluye los conceptos básicos de redes de comunicaciones, la cuestión de la ruta óptima y los algoritmos adaptativos y no adaptativos existentes, que se utilizan actualmente. Los algoritmos analizados fueron: Shortest Path Routing, que busca los caminos con menor número de nodos intermedios, no siendo sensible a variaciones en la carga ni en la topología de la red; Weighted Shortest Path Routing, que ofrece un mejor desempeño a partir de una visión global del estado de la red, que no siempre es fácil de obtener en redes reales; y el algoritmo de Bellman-Ford, que tiene como base decisiones de rutas locales y actualizaciones periódicas, con algunas limitaciones para obtener políticas en altas cargas. Este último es uno de los algoritmos más utilizados en la actualidad, siendo base de muchos protocolos de trazado de ruta existentes. La solución para modelar el problema de ruteamiento como un sistema RL fue inspirada por una característica en la definición de un sistema RL: un agente que interactúa con el ambiente y aprende a alcanzar un objetivo. Así, el modelo tiene como objetivo aprender a determinar las rutas que minimizen el timpo desde el origen hasta un destino dado. La evaluación de uma ruta seleccionada no puede ser obtenida antes que el paquete alcance su destino final. Esto hace que los procesos de aprendizaje supervisionado tengan dificultades para ser aplicados a este problema. Por otro lado, Reinforcement Learning no necesita de un par entrada-salida para el aprendizaje, permitiendo así, abordar el problema con relativa facilidad. En el modelo establecido, cada nodo en la red se comporta como un agente de RL que actúa en la propria red. La información de las rutas se almacena en las funciones de valor existentes en todos los nodos de la red para cada nodo destino diferente. Esta información contiene un valor estimado del tiempo requerido para un paquete para llegar hasta el nodo destino. La actualización de esos valores se realiza durante la transición del paquete hasta el vecino seleccionado. En este trabajo se implementaron varios algoritmos de ruta óptima. Cada uno de los algoritmos aplica características de las técnicas en Reinforcement Learning: o Q(lambda)-Routing, y el TD-Routing. En el estudio d