TY - THES
AB - We study partially observable Markov decision processes (POMDPs) with objectives used in verification and artificial intelligence. The qualitative analysis problem given a POMDP and an objective asks whether there is a strategy (policy) to ensure that the objective is satisfied almost surely (with probability 1), resp. with positive probability (with probability greater than 0). For POMDPs with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards, we consider two types of path constraints: (i) a quantitative limit-average constraint defines the set of paths where the payoff is at least a given threshold L1 = 1. Our main results for qualitative limit-average constraint under almost-sure winning are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative limit-average constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We present a prototype implementation of our EXPTIME algorithm. For POMDPs with w-regular conditions specified as parity objectives, while the qualitative analysis problems are known to be undecidable even for very special case of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. Based on our theoretical algorithms we also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of well-known POMDP examples for robotics applications. For POMDPs with a set of target states and an integer cost associated with every transition, we study the optimization objective that asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely. We show that for general integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double and exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms that extend existing algorithms for POMDPs with finite-horizon objectives. We show experimentally that it performs well in many examples of interest. We study more deeply the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a strategy to ensure that the target set is reached almost surely. While in general the problem EXPTIME-complete, in many practical cases strategies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. We first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. Decentralized POMDPs (DEC-POMDPs) extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. In this work we consider Goal DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the real-time dynamic programming approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. In the end we present a short summary of a few other results related to verification of MDPs and POMDPs.
AU - Chmelik, Martin
ID - 1397
TI - Algorithms for partially observable markov decision processes
ER -
TY - THES
AB - Hybrid zones represent evolutionary laboratories, where recombination brings together alleles in combinations which have not previously been tested by selection. This provides an excellent opportunity to test the effect of molecular variation on fitness, and how this variation is able to spread through populations in a natural context. The snapdragon Antirrhinum majus is polymorphic in the wild for two loci controlling the distribution of yellow and magenta floral pigments. Where the yellow A. m. striatum and the magenta A. m. pseudomajus meet along a valley in the Spanish Pyrenees they form a stable hybrid zone Alleles at these loci recombine to give striking transgressive variation for flower colour. The sharp transition in phenotype over ~1km implies strong selection maintaining the hybrid zone. An indirect assay of pollinator visitation in the field found that pollinators forage in a positive-frequency dependent manner on Antirrhinum, matching previous data on fruit set. Experimental arrays and paternity analysis of wild-pollinated seeds demonstrated assortative mating for pigmentation alleles, and that pollinator behaviour alone is sufficient to explain this pattern. Selection by pollinators should be sufficiently strong to maintain the hybrid zone, although other mechanisms may be at work. At a broader scale I examined evolutionary transitions between yellow and anthocyanin pigmentation in the tribe Antirrhinae, and found that selection has acted strate that pollinators are a major determinant of reproductive success and mating patterns in wild Antirrhinum.
AU - Ellis, Thomas
ID - 1398
TI - The role of pollinator-mediated selection in the maintenance of a flower color polymorphism in an Antirrhinum majus hybrid zone
ER -
TY - THES
AB - Computer graphics is an extremely exciting field for two reasons. On the one hand,
there is a healthy injection of pragmatism coming from the visual effects industry
that want robust algorithms that work so they can produce results at an increasingly
frantic pace. On the other hand, they must always try to push the envelope and
achieve the impossible to wow their audiences in the next blockbuster, which means
that the industry has not succumb to conservatism, and there is plenty of room to
try out new and crazy ideas if there is a chance that it will pan into something
useful.
Water simulation has been in visual effects for decades, however it still remains
extremely challenging because of its high computational cost and difficult artdirectability.
The work in this thesis tries to address some of these difficulties.
Specifically, we make the following three novel contributions to the state-of-the-art
in water simulation for visual effects.
First, we develop the first algorithm that can convert any sequence of closed
surfaces in time into a moving triangle mesh. State-of-the-art methods at the time
could only handle surfaces with fixed connectivity, but we are the first to be able to
handle surfaces that merge and split apart. This is important for water simulation
practitioners, because it allows them to convert splashy water surfaces extracted
from particles or simulated using grid-based level sets into triangle meshes that can
be either textured and enhanced with extra surface dynamics as a post-process.
We also apply our algorithm to other phenomena that merge and split apart, such
as morphs and noisy reconstructions of human performances.
Second, we formulate a surface-based energy that measures the deviation of a
water surface froma physically valid state. Such discrepancies arise when there is a
mismatch in the degrees of freedom between the water surface and the underlying
physics solver. This commonly happens when practitioners use a moving triangle
mesh with a grid-based physics solver, or when high-resolution grid-based surfaces
are combined with low-resolution physics. Following the direction of steepest
descent on our surface-based energy, we can either smooth these artifacts or turn
them into high-resolution waves by interpreting the energy as a physical potential.
Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new
workflow where practitioners can re-simulate part of an existing simulation, such
as removing a solid obstacle, adding a new splash or locally changing the resolution.
Such changes can easily lead to new waves in the re-simulated region that would
reflect off of the new simulation boundary, effectively ruining the illusion of a
seamless simulation boundary between the existing and new simulations. Our
non-reflecting boundaries makes sure that such waves are absorbed.
AU - Bojsen-Hansen, Morten
ID - 1122
TI - Tracking, correcting and absorbing water surface waves
ER -
TY - THES
AB - Traditionally machine learning has been focusing on the problem of solving a single
task in isolation. While being quite well understood, this approach disregards an
important aspect of human learning: when facing a new problem, humans are able to
exploit knowledge acquired from previously learned tasks. Intuitively, access to several
problems simultaneously or sequentially could also be advantageous for a machine
learning system, especially if these tasks are closely related. Indeed, results of many
empirical studies have provided justification for this intuition. However, theoretical
justifications of this idea are rather limited.
The focus of this thesis is to expand the understanding of potential benefits of information
transfer between several related learning problems. We provide theoretical
analysis for three scenarios of multi-task learning - multiple kernel learning, sequential
learning and active task selection. We also provide a PAC-Bayesian perspective on
lifelong learning and investigate how the task generation process influences the generalization
guarantees in this scenario. In addition, we show how some of the obtained
theoretical results can be used to derive principled multi-task and lifelong learning
algorithms and illustrate their performance on various synthetic and real-world datasets.
AU - Pentina, Anastasia
ID - 1126
TI - Theoretical foundations of multi-task lifelong learning
ER -
TY - THES
AB - The process of gene expression is central to the modern understanding of how cellular systems
function. In this process, a special kind of regulatory proteins, called transcription factors,
are important to determine how much protein is produced from a given gene. As biological
information is transmitted from transcription factor concentration to mRNA levels to amounts of
protein, various sources of noise arise and pose limits to the fidelity of intracellular signaling.
This thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical
description of complex promoters responsible for the stochastic production of biomolecules,
(ii) fundamental limits to information processing the cell faces due to the interference from multiple
fluctuating signals, (iii) how the presence of gene expression noise influences the evolution
of regulatory sequences, (iv) and tools for the experimental study of origins and consequences
of cell-cell heterogeneity, including an application to bacterial stress response systems.
AU - Rieckh, Georg
ID - 1128
TI - Studying the complexities of transcriptional regulation
ER -