Surrogate models for discrete optimization problems See

Surrogate models are crucial tools for many real-world optimization problems. An optimization algorithm can evaluate a data-driven surrogate model instead of an expensive objective function. While surrogate models are well-established in the continuous optimization domain, they are less frequently applied to more complex search spaces with discrete or combinatorial solution representations. The main goal of this thesis is to fill this gap. We develop and improve methods for data-driven su...

K-best enumeration - theory and application See

Where an optimal solution does not contain sufficient information about a given problem instance, enumerating good solutions is a common coping strategy. In combinatorial optimization, k-best enumeration, or ranking, has been studied and applied extensively. The k shortest simple path problem in directed, weighted graphs (kSSP), introduced in 1963 by Clarke, Krikorian and Rausen, is particularly well known. Efficient existing algorithms are based on Yen's algorithm for this problem; they all ...

Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem See

In this thesis, we are concerned with multiobjective combinatorial optimization (MOCO) problems. We attempt to fill the gap between theory and practice, which comes from the lack of a deep complexity theory for MOCO problems. In a first part, we consider a complexity notion for multiobjective optimization problems which derives from output-sensitive complexity. The primary goal of such a complexity notion is to classify problems into easy and hard problems. We show that the multiobjectiv...

Partially supervised learning of models for visual scene and object recognition See

When creating a visual recognition system for a novel task, one of the main burdens is the collection and annotation of data. Often several thousand samples need to be manually reviewed and labeled so that the recognition system achieves the desired accuracy. The goal of this thesis is to provide methods that lower the annotation effort for visual scene and object recognition. These methods are applicable to traditional pattern recognition approaches as well as methods from the field of deep ...

On large-scale probabilistic and statistical data analysis See

In this manuscript we develop and apply modern algorithmic data reduction techniques to tackle scalability issues and enable statistical data analysis of massive data sets. Our algorithms follow a general scheme, where a reduction technique is applied to the large-scale data to obtain a small summary of sublinear size to which a classical algorithm is applied. The techniques for obtaining these summaries depend on the problem that we want to solve. The size of the summaries is usually paramet...

Exploring regular structures in strings See

This thesis is dedicated to string processing algorithms and to combinatorics on words. With respect to the former, we devise Lempel-Ziv (LZ) factorization and sparse suffix sorting algorithms. With respect to the latter, we search for all distinct squares, all maximal α-gapped repeats, and all maximal α-gapped palindromes. The topics of the presented approaches are related: for instance, our results for the LZ factorization have applications for finding all distinct squares, whereas our spar...

Markov decision processes with uncertain parameters See

Markov decision processes model stochastic uncertainty in systems and allow one to construct strategies which optimize the behaviour of a system with respect to some reward function. However, the parameters for this uncertainty, that is, the probabilities inside a Markov decision model, are derived from empirical or expert knowledge and are themselves subject to uncertainties such as measurement errors or limited expertise. This work considers second-order uncertainty models for Markov decisi...

Methods for efficient resource utilization in statistical machine learning algorithms See

In recent years, statistical machine learning has emerged as a key technique for tackling problems that elude a classic algorithmic approach. One such problem, with a major impact on human life, is the analysis of complex biomedical data. Solving this problem in a fast and efficient manner is of major importance, as it enables, e.g., the prediction of the efficacy of different drugs for therapy selection. While achieving the highest possible prediction quality appears desirable, doing so is o...

Efficient implementation of resource-constrained cyber-physical systems using multi-core parallelism See

The quest for more performance of applications and systems became more challenging in the recent years. Especially in the cyber-physical and mobile domain, the performance requirements increased significantly. Applications, previously found in the high-performance domain, emerge in the area of resource-constrained domain. Modern heterogeneous high-performance MPSoCs provide a solid foundation to satisfy the high demand. Such systems combine general processors with specialized accelerators ran...

Exponential families on resource-constrained systems See

This work is about the estimation of exponential family models on resource-constrained systems. Our main goal is learning probabilistic models on devices with highly restricted storage, arithmetic, and computational capabilities—so called, ultra-low-power devices. Enhancing the learning capabilities of such devices opens up opportunities for intelligent ubiquitous systems in all areas of life, from medicine, over robotics, to home automation—to mention just a few. We investigate the inhe...

Advances in next-track music recommendation See

Technological advances in the music industry have dramatically changed how people access and listen to music. Today, online music stores and streaming services offer easy and immediate means to buy or listen to a huge number of songs. One traditional way to find interesting items in such cases when a vast amount of choices are available is to ask others for recommendations. Music providers utilize correspondingly music recommender systems as a software solution to the problem of music overloa...

Acoustic sensor network geometry calibration and applications See

In the modern world, we are increasingly surrounded by computation devices with communication links and one or more microphones. Such devices are, for example, smartphones, tablets, laptops or hearing aids. These devices can work together as nodes in an acoustic sensor network (ASN). Such networks are a growing platform that opens the possibility for many practical applications. ASN based speech enhancement, source localization, and event detection can be applied for teleconferencing, camer...

Ein skalierbares agglomeratives Clusterverfahren basierend auf erste Nachbarschaftsbeziehungen See

Eine der revolutionären Veränderungen des 20. und 21. Jahrhunderts der Menschheit ist die Computerisierung und Digitalisierung der Welt. Tagtäglich werden große Menge von Daten erzeugt. Es ist unmöglich für uns Menschen, ohne anspruchsvolle Verfahren und Algorithmen, aus diesen enorm großen Datenmengen versteckte Strukturen (Wissen) herauszufiltern. Datamining, Machine Learning und Pattern Recognition sind ähnliche Disziplinen, mit denen man versuchen will, diese Herausforderung zu bewältige...

Solving two-stage stochastic network design problems to optimality See

The Steiner tree problem (STP) is a central and well-studied graph-theoretical combinatorial optimization problem which plays an important role in various applications. It can be stated as follows: Given a weighted graph and a set of terminal vertices, find a subset of edges which connects the terminals at minimum cost. However, in real-world applications the input data might not be given with certainty or it might depend on future decisions. For the STP, for example, edge costs representing ...

Arbeitsmaterialien zum Buch Python 3 See

Resource-constrained analysis of ion mobility spectrometry data See

During the past decades numerous spectrometry devices, e.g. mass spectrometry or liquid or gas chromatography, have been engineered to measure the different properties of molecules, compounds or even complex structures. One device exploits the different mobilities of ionized analytes, the so-called ion mobility spectrometer. The advantages of this device are the low costs of production and maintenance (e.g. a high vacuum as in mass spectrometry is not required), the fast capture (a few millis...

Automatisierte Verfeinerung von Energiemodellen für eingebettete Systeme See

Bei der Entwicklung und Nutzung von eingebetteten Systemen werden häufig Energiemodelle der einzelnen Systemkomponenten benötigt, um den Energiebedarf des Gesamtsystems abschätzen zu können. Die Erstellung und Verfeinerung solcher Modelle bedeutet meist aufwändige Handarbeit, da die notwendigen Mess- und Auswertungsschritte von den jeweiligen Komponenten abhängen. Diese Arbeit zeigt, dass es trotz der Unterschiede zwischen verschiedenen Peripheriegeräten möglich ist, mit einem generische...

Context-free games on strings and nested words See

Kontextfreie Spiele sind ein formales Modell, welches in seiner einfachsten Form den Ableitungsmechanismus kontextfreier Grammatiken zu einem Spiel für zwei Spieler (genannt Juliet und Romeo) verallgemeinert; dabei wählt in einer gegebenen Satzform (d.h. einer Zeichenkette aus Terminal- und Nichtterminalsymbolen) jeweils Juliet ein zu ersetzendes Nichtterminalsymbol aus, worauf Romeo jeweils entsprechend den Ableitungsregeln entscheidet, wodurch dieses Nichtterminalsymbol ersetzt werden soll....

On algorithms for large-scale graph and clustering problems See

Gegenstand dieser Arbeit sind algorithmische Methoden der modernen Datenanalyse. Dabei werden vorwiegend zwei übergeordnete Themen behandelt: Datenstromalgorithmen mit Kompressionseigenschaften und Approximationsalgorithmen für Clusteringverfahren. Datenstromalgorithmen verarbeiten einen Datensatz sequentiell und haben das Ziel, Eigenschaften des Datensatzes (approximativ) zu bestimmen, ohne dabei den gesamten Datensatz abzuspeichern. Unter Clustering versteht man die Partitionierung eines Da...