This thesis is concerned with the problem of how to make decisions in an uncertain world. We use a model of uncertainty based on Markov decision problems, and develop a number of algorithms for decision-making both for the planning problem, in which the model is known in advance, and for the reinforcement learning problem in which the decision-making agent does not know the model and must learn to make good decisions by trial and error. The basis for much of this work is the use of structural representations of problems. If a problem is represented in a structured way we can compute or learn plans that take advantage of this structure for computational gains. This is because the structure allows us to perform abstraction. Rather than reasoning about each situation in which a decision must be made individually, abstraction allows us to group situations together and reason about a whole set of them in a single step. Our approach to abstraction has the additional advantage that we can dynamically change the level of abstraction, splitting a group of situations in two if they need to be reasoned about separately to find an acceptable plan, or merging two groups together if they no longer need to be distinguished. We present two planning algorithms and one learning algorithm that use this approach. A second idea we present in this thesis is a novel approach to the exploration problem in reinforcement learning. The problem is to select actions to perform given that we would like good performance now and in the future. We can select the current best action to perform, but this may prevent us from discovering that another action is better, or we can take an exploratory action, but we risk performing poorly now as a result. Our Bayesian approach makes this tradeoff explicit by representing our uncertainty about the values of states and using this measure of uncertainty to estimate the value of the information we could gain by performing each action. We present both model-free and model-based reinforcement learning algorithms that make use of this exploration technique. Finally, we show how these ideas fit together to produce a reinforcement learning algorithm that uses structure to represent both the problem being solved and the plan it learns, and that selects actions to perform in order to learn using our Bayesian approach to exploration. / Science, Faculty of / Computer Science, Department of / Graduate

Orientador: Yuzo Iano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-22T04:02:03Z (GMT). No. of bitstreams: 1 CanahuireCabello_FrankAlexis_M.pdf: 3500312 bytes, checksum: b7dd89de471972ad2d550cd52847e9f5 (MD5) Previous issue date: 2013 / Resumo: A área que trata de detectar falhas mecânicas em circuito impresso é, atualmente, de grande importância. Isso se deve ao fato de que cada dia as empresas procuram de novas maquinas mais eficientes e rápidas para detectar falhas em placas. Existem diferentes tipos de falhas mecânicas em placas de circuitos impressos, como por exemplo, falta de componentes, falta de soldadura, má colocação de dispositivos, etc. Este trabalho dará uma contribuição para solucionar o problema de má colocação de dispositivos nas placas de circuito impresso. Para isso serão usadas imagens de placas de circuito impresso e será usado um algoritmo de detecção de características chamado SIFT o qual será modificado para esse propósito. A modificação do método SIFT será na etapa de matching (encontrar correspondências semelhantes entre duas imagens) e será desenvolvido um algoritmo usando métodos geométricos para eliminar as correspondências que não pertencem à mesma característica. Será comparado o SIFT modificado com os métodos SURF, SIFT e RANSAC para determinar seu desempenho em variações de escala, rotação, ruído gaussiano e brilho. Será usado o método SIFT desenvolvido neste trabalho para solucionar o problema de má colocação de dispositivos em placas de circuito impresso / Abstract: The area which comes to detect mechanical failures in printed circuit board is currently of great importance. This is due to the fact that every day companies seek new machines more efficient and quick to detect flaws in printed circuit boards. There are different types of mechanical faults in printed circuit boards, such as lack of components, poor weld, and bad placement devices and so on. This work will provide a contribution to solve the problem of poor placement of devices on printed circuit boards. For this, are used images of printed circuit boards and will use a method of feature detection called SIFT which will be modified for our purpose. The modification of the method SIFT is in the stage of matching (finding similar correspondences between two images) and will be developed an algorithm using geometric methods to eliminate the matches that do not belong to the same feature. Will be compared the modified SIFT with the methods SURF, SIFT and RANSAC to determine their performance in variations of scale, rotation, Gaussian noise and brightness. The SIFT method developed in this work will be used to solve the problem of poor placement of devices on printed circuit boards / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

The traveling salesman problem (TSP) has become a classic in the field of combinatorial optimization. Attracting computer scientists and mathematicians, the problem involves finding a minimum cost Hamiltonian cycle in a weighted graph.

This thesis presents and evaluates a new parallel algorithm that computes all single cosets in the double coset M₂₄ P M₂₄, where P is a permutation on n points of a certain cycle structure, and M₂₄ is the Mathieu group related to a Steiner system S(5, 8, 24) as its automorphism group. The purpose of this work is not to replace the existing algorithms, but rather to explore a possibility to extend calculations of single cosets beyond the limits encountered when using currently available methods.

Reinforcement learning (RL) is a generic paradigm for the modeling and optimization of sequential decision making. In the recent decade, progress in RL research has brought about breakthroughs in several applications, ranging from playing video games, mastering board games, to controlling simulated robots. To bring the potential benefits of RL to other domains, two elements are critical: (1) Efficient and general-purpose RL algorithms; (2) Formulations of the original applications into RL problems. These two points are the focus of this thesis. We start by developing more efficient RL algorithms. In Chapter 2, we propose Taylor Expansion Policy Optimization, a model-free algorithmic framework that unifies a number of important prior work as special cases. This unifying framework also allows us to develop a natural algorithmic extension to prior work, with empirical performance gains. In Chapter 3, we propose Monte-Carlo Tree Search as Regularized Policy Optimization, a model-based framework that draws close connections between policy optimization and Monte-Carlo tree search. Building on this insight, we propose Policy Optimization Zero (POZero), a novel algorithm which leverages the strengths of regularized policy search to achieve significant performance gains over MuZero. To showcase how RL can be applied to other domains where the original applications could benefit from learning systems, we study the acceleration of integer programming (IP) solvers with RL. Due to the ubiquity of IP solvers in industrial applications, such research holds the promise of significant real life impacts and practical values. In Chapter 4, we focus on a particular formulation of Reinforcement Learning for Integer Programming: Learning to Cut. By combining cutting plane methods with selection rules learned by RL, we observe that the RL-augmented cutting plane solver achieves significant performance gains over traditional heuristics. This serves as a proof-of-concept of how RL can be combined with general IP solvers, and how learning augmented optimization systems might achieve significant acceleration in general.

This paper explores how an all pair shortest path can be obtained in a wireless sensor network when sensors fail. Sensors are randomly deployed in a predefined geographical area, simulating the deployment of sensors from an airplane, and finding shortest path between all the sensors deployed based on distance. A major problem to address in wireless sensor networks is the impact of sensor failures on existing shortest paths in the network. An application is developed to simulate a network and find shortest paths affected by a sensor failure and find alternative shortest path. When a sensor fails, all the shortest paths and all the remaining sensors in the network are checked to see if the sensor failure has any impact on the network. Alternative shortest path is calculated for those paths affected by sensor failures.

We design efficient algorithms for computational problems over strings in several models where the algorithms have limited access to the input. These models, and algorithms developed respecting these constraints, are becoming increasingly relevant due to the rapidly increasing size of datasets in myriad applications. Our first problem of interest is \emph{trace reconstruction}. This is an important problem in learning theory and coding theory, and has applications in computational biology. In this problem, the goal is to recover an unknown string given independent samples (\emph{traces}) of it generated via a probabilistic noise process called the deletion channel. We give state-of-the-art algorithms for this problem in several settings. Then we consider the problem of estimating the \emph{longest increasing subsequence (LIS)} of a given string in sublinear time, given query access to the string. While the LIS of a string can be computed exactly in near-linear time, the optimal complexity of approximating the LIS length, especially when the LIS is much less than the string length, is still open. We significantly improve upon prior work in terms of both approximation and time complexity in this regime. The runtime of our algorithm essentially matches the trivial query complexity lower bound as a function of the length of the LIS. Finally, we consider the problem of local decoding, or random access, on compressed strings. The Burrows-Wheeler Transform (BWT) is an important preprocessing step in lossless text compression that rearranges a string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings. However, the decoding process of the BWT is inherently sequential, and prevents fast random access to the original string. We design a succinct data structure for locally decoding short substrings (and answering several other queries) of a given string under its compressed BWT efficiently.

Big data systems such as relational databases, data science platforms, and scientific workflows all process queries over large and complex datasets. Skew is common in these real-world datasets and workloads. Different types of skew can have different impacts on the performance of query processing. Although skew sometimes causes load imbalance in a parallel execution environment, negatively impacting query performance, we demonstrate in this thesis that, in many cases we can actually improve the query performance in the presence of skew. To optimize query processing under skew, we develop a set of techniques to exploit the positive effects of skew and to avoid the negative effects. In order to exploit skew, we propose techniques including: (a) intentionally creating skew and clustering data in a distributed database system; (b) optimizing data layout for better caching in main-memory databases; and (c) adaptive execution techniques that are responsive to the underlying data in the context of compilers. In order to ameliorate skew, we study optimized hash-based partitioning that alleviate outliers in a genomic data context, as well as parallel prefix sum algorithms that used to develop skew-insensitive algorithms. We evaluate the effectiveness of our techniques over synthetic data, standard benchmarks, as well as empirical datasets, and show that the performance of query processing under skew can be greatly improved. Overall this thesis has made a concrete contribution to skew-related query processing.

No description available.

The rapid rise of digital platforms has transformed communication and information sharing. As social networks become increasingly integral to modern society, social media platforms are motivated to implement algorithms that both enhance user experience and bolster advertising. Yet, the intricate nature of social networks poses significant algorithmic design challenges: How can network data be used to predict node attributes? Which graph representations contain the best prediction power? Of paramount concern is the potential for these algorithms to reinforce biases against marginalized groups. Social networks often mirror societal biases tied to gender, race, socioeconomic status, and other factors. Algorithms that unintentionally enhance these biases can detrimentally affect individuals and broader communities. Recognizing these implications, this dissertation delves into four projects, each addressing distinct aspects of these challenges. Through our investigations, we propose innovative solutions aimed at bolstering the fairness, accuracy, and predictive prowess of social network algorithms.