Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T10:12:53Z (GMT). No. of bitstreams: 1 Peixoto_RobsonRobertoSouza_M.pdf: 1268588 bytes, checksum: ff8a093aa133696dcd5bbe31bc4d6e78 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas / Abstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-min / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-30T20:07:56Z No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-01T11:51:04Z (GMT) No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) / Made available in DSpace on 2017-06-01T11:51:04Z (GMT). No. of bitstreams: 1 robertocarlossoaresnalonpereirasouza.pdf: 1346845 bytes, checksum: e248f967f42f4ef763b613dc39ed0649 (MD5) Previous issue date: 2013-02-21 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho apresenta-se uma nova formulação para regressão ortogonal. O problema é definido como a minimização do risco empírico em relação a uma função de perda com tubo desenvolvida para regressão ortogonal, chamada ρ-insensível. Um algoritmo para resolver esse problema é proposto, baseado na abordagem da descida do gradiente estocástica. Quando formulado em variáveis duais o método permite a introdução de funções kernel e flexibilidade do tubo. Até onde se sabe, este é o primeiro método que permite a introdução de kernels, através do chamado “kernel-trick”, para regressão ortogonal. Apresenta-se ainda um algoritmo para regressão clássica que usa a função de perda ε-insensível e segue também a abordagem da descida do gradiente. Para esse algo ritmo apresenta-se uma prova de convergência que garante um número finito de correções. Finalmente, introduz-se uma estratégia incremental que pode ser usada acoplada com ambos os algoritmos para obter soluções esparsas e também uma aproximação para o “tubo mínimo”que contém os dados. Experimentos numéricos são apresentados e os resultados comparados a outros métodos da literatura. / In this work, we introduce a new formulation for orthogonal regression. The problem is defined as minimization of the empirical risk with respect to a tube loss function de veloped for orthogonal regression, named ρ-insensitive. The method is constructed via an stochastic gradient descent approach. The algorithm can be used in primal or in dual variables. The latter formulation allows the introduction of kernels and soft margins. To the best of our knowledge, this is the first method that allows the introduction of kernels via the so-called “kernel-trick” for orthogonal regression. Also, we present an algorithm to solve the classical regression problem using the ε-insensitive loss function. A conver gence proof that guarantees a finite number of updates is presented for this algorithm. In addition, an incremental strategy algorithm is introduced, which can be used to find sparse solutions and also an approximation to the “minimal tube” containing the data. Numerical experiments are shown and the results compared with other methods.

No description available.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.

<p>Online decision making with switching costs has received considerable attention in many practical problems that face uncertainty in the inputs and key problem parameters. Because of the switching costs that penalize the change of decisions, making good online decisions under such uncertainty is known to be extremely challenging. This thesis aims at providing new online algorithms with strong performance guarantees to address this challenge.</p> <p><br></p> <p>In part 1 and part 2 of this thesis, motivated by Network Functions Virtualization and smart grid, we study competitive online convex optimization with switching costs. Specifically, in part 1, we focus on the setting with an uncertainty set (one type of prediction) and hard infeasibility constraints. We develop new online algorithms that can attain optimized competitive ratios, while ensuring feasibility at all times. Moreover, we design a robustification procedure that helps these algorithms obtain good average-case performance simultaneously. In part 2, we focus on the setting with look-ahead (another type of prediction). We provide the first algorithm that attains a competitive ratio that not only decreases to 1 as the look-ahead window size increases, but also remains upper-bounded for any ratio between the switching-cost coefficient and service-cost coefficient.</p> <p><br></p> <p>In part 3 of this thesis, motivated by edge computing with artificial intelligence, we study bandit learning with switching costs where, in addition to bandit feedback, full feedback can be requested at a cost. We show that, when only 1 arm can be chosen at a time, adding costly full-feedback is not helpful in fundamentally reducing the Θ(<em>T</em>2/3) regret over a time-horizon <em>T</em>. In contrast, when 2 (or more) arms can be chosen at a time, we provide a new online learning algorithm that achieves a significantly smaller regret equal to <em>O</em>(√<em>T</em>), without even using full feedback. To the best of our knowledge, this type of sharp transition from choosing 1 arm to choosing 2 (or more) arms has never been reported in the literature.</p>

Die Interaktion zwischen Maschinen und ihrer Umgebung sollte zuverlässig, sicher und ökologisch adequat sein. Um das in komplexen Szenarien langfristig zu gewährleisten, wird eine Theorie adaptiven Verhaltens benötigt. In der Entwicklungsrobotik und verkörperten künstlichen Intelligenz wird Verhalten als emergentes Phänomen auf der fortlaufenden dynamischen Interaktion zwischen Agent, Körper und Umgebung betrachtet. Die Arbeit untersucht Roboter, die in der Lage sind, schnell und selbständig einfache Bewegungen auf Grundlage sensomotorischer Information zu erlernen. Das langfristige Ziel dabei ist die Wiederverwendung gelernter Fertigkeiten in späteren Lernprozessen um damit ein komplexes Interaktionsrepertoire mit der Welt entstehen zu lassen, das durch Entwicklungsprozesse vollständig und fortwährend adaptiv in der sensomotorischen Erfahrung verankert ist. Unter Verwendung von Methoden des maschinellen Lernens, der Neurowissenschaft, Statistik und Physik wird die Frage in die Komponenten Repräsentation, Exploration, und Lernen zerlegt. Es wird ein Gefüge für die systematische Variation und Evaluation von Modellen errichtet. Das vorgeschlagene Rahmenwerk behandelt die prozedurale Erzeugung von Hypothesen als Flussgraphen über einer festen Menge von Funktionsbausteinen, was die Modellsuche durch nahtlose Anbindung über simulierte und physikalische Systeme hinweg ermöglicht. Ein Schwerpunkt der Arbeit liegt auf dem kausalen Fussabdruck des Agenten in der sensomotorischen Zeit. Dahingehend wird ein probabilistisches graphisches Modell vorgeschlagen um Infor- mationsflussnetzwerke in sensomotorischen Daten zu repräsentieren. Das Modell wird durch einen auf informationtheoretischen Grössen basierenden Lernalgorithmus ergänzt. Es wird ein allgemeines Modell für Entwicklungslernen auf Basis von Echtzeit-Vorhersagelernen präsentiert und anhand dreier Variationen näher besprochen. / The interaction of machines with their environment should be reliable, safe, and ecologically adequate. To ensure this over long-term complex scenarios, a theory of adaptive behavior is needed. In developmental robotics, and embodied artificial intelligence behavior is regarded as a phenomenon that emerges from an ongoing dynamic interaction between entities called agent, body, and environment. The thesis investigates robots that are able to learn rapidly and on their own, how to do primitive motions, using sensorimotor information. The long-term goal is to reuse acquired skills when learning other motions in the future, and thereby grow a complex repertoire of possible interactions with the world, that is fully grounded in, and continually adapted to sensorimotor experience through developmental processes. Using methods from machine learning, neuroscience, statistics, and physics, the question is decomposed into the relationship of representation, exploration, and learning. A framework is provided for systematic variation and evaluation of models. The proposed framework considers procedural generation of hypotheses as scientific workflows using a fixed set of functional building blocks, and allows to search for models by seamless evaluation in simulation and real world experiments. Additional contributions of the thesis are related to the agent's causal footprint in sensorimotor time. A probabilistic graphical model is provided, along with an information-theoretic learning algorithm, to discover networks of information flow in sensorimotor data. A generic developmental model, based on real time prediction learning, is presented and discussed on the basis of three different algorithmic variations.