Publications of the International Max Planck Research School for Computer Science

Commonsense knowledge (CSK) about concepts and their properties is useful for AI applications such as robust chatbots. Prior works like ConceptNet, TupleKB and others compiled large CSK collections, but are restricted in their expressiveness to subject-predicate-object (SPO) triples with simple concepts for S and monolithic strings for P and O. Also, these projects have either prioritized precision or recall, but hardly reconcile these complementary goals. This thesis presents a methodology, called Ascent, to automatically build a large-scale knowledge base (KB) of CSK assertions, with advanced expressiveness and both better precision and recall than prior works. Ascent goes beyond triples by capturing composite concepts with subgroups and aspects, and by refining assertions with semantic facets. The latter are important to express temporal and spatial validity of assertions and further qualifiers. Ascent combines open information extraction with judicious cleaning using language models. Intrinsic evaluation shows the superior size and quality of the Ascent KB, and an extrinsic evaluation for QA-support tasks underlines the benefits of Ascent.

Automatic text alignment is an important problem in natural language processing. It
can be used to create the data needed to train different language models. Most research
about automatic summarization revolves around summarizing news articles or scientific
papers, which are somewhat small texts with simple and clear structure. The bigger the
difference in size between the summary and the original text, the harder the problem will
be since important information will be sparser and identifying them can be more difficult.
Therefore, creating datasets from larger texts can help improve automatic summarization.
In this project, we try to develop an algorithm which can automatically create a
dataset for abstractive automatic summarization for bigger narrative text bodies such
as movie scripts. To this end, we chose sentences as summary text units and scenes
as script text units and developed an algorithm which uses some of the latest natural
language processing techniques to align scenes and sentences based on the similarity in
their meanings.
Solving this alignment problem can provide us with important information about how
to evaluate the meaning of a text, which can help us create better abstractive summariza-
tion models. We developed a method which uses different similarity scoring techniques
(embedding similarity, word inclusion and entity inclusion) to align script scenes and sum-
mary sentences which achieved an F1 score of 0.39. Analyzing our results showed that
the bigger the differences in the number of text units being aligned, the more difficult the
alignment problem is. We also critiqued of our own similarity scoring techniques and dif-
ferent alignment algorithms based on integer linear programming and local optimization
and showed their limitations and discussed ideas to improve them.

Artificial Intelligence (AI) has become one of the most researched fields nowadays. Ma-
chine Learning (ML) is one of the most popular AI domains, where systems are created
with the capability of automatic learning and improving from the learning experience.
The current revolution in the size and cost of electronic storage allows for the existence
of enormous amount of data that can be used for ML training. Unfortunately, not all
of this data is labelled. The process of manually labelling documents can be expen-
sive, time consuming and subject to human errors. Active Learning (AL) addresses
this challenge by finding a sample of the enormous data corpus that, if labelled, can
substitute the use of the whole dataset. AL routes this sample to a human labeller to
formulate the training dataset needed for the ML model. AL assumes that there exists a
single, infallible and indefatigable labeller. These assumptions cannot cope to real world
problems. The main focus of this work is to introduce Proactive Learning (PL) to an
existing AL system. PL aims at generalizing the problem, solved by AL, by relaxing
all of its assumptions about the user. The main addition of this project is enhancing
automatic text classification by combining knowledge from the domain of PL and from
Instance Relabelling paradigms to update the currently implemented AL system. The
implemented PL system is tested on the 20 Newsgroups, Reuters and AG News datasets.
The system is capable of reaching impressive results in detecting and predicting users
actions, which allows the system to efficiently route labelling tasks to the best users,
leading to minimize the risk of receiving wrong labels.

User interface design for Virtual Reality and other embodied interaction contexts
has to carefully consider ergonomics. A common problem is that mid-air inter-
action may cause excessive arm fatigue, known as the “Gorilla arm” effect. To
predict and prevent such problems at a low cost, this thesis investigates user test-
ing of mid-air interaction without real users, utilizing biomechanically simulated
AI agents trained using deep Reinforcement Learning (RL). This is implemented
in a pointing task and four experimental conditions, demonstrating that the sim-
ulated fatigue data matches ground truth human data. Additionally, two effort
models are compared against each other: 1) instantaneous joint torques commonly
used in computer animation and robotics, and 2) the recent Three Compartment
Controller (3CC-r) model from biomechanical literature. 3CC-r yields movements
that are both more efficient and natural, whereas with instantaneous joint torques,
the RL agent can easily generate movements that are unnatural or only reach the
targets slowly and inaccurately. This thesis demonstrates that deep RL combined
with the 3CC-r provides a viable tool for predicting both interaction movements
and user experience in silico, without users.

Human motion capture data has been widely used in data-driven character animation. In
order to generate realistic, natural-looking motions, most data-driven approaches require
considerable efforts of pre-processing, including motion segmentation, annotation, and
so on. Existing (semi-) automatic solutions either require hand-crafted features for
motion segmentation or do not produce the semantic annotations required for motion
synthesis and building large-scale motion databases. In this thesis, an approach for a
semi-automatic framework for semantic segmentation of motion capture data based on
(semi-) supervised machine learning techniques is developed. The motion capture data is
first transformed into a “motion image” to apply common convolutional neural networks
for image segmentation. Convolutions over the time domain enable the extraction of
temporal information and dilated convolutions are used to enlarge the receptive field
exponentially using comparably few layers and parameters. The finally developed dilated
temporal fully-convolutional model is compared against state-of-the-art models in action
segmentation, as well as a popular network for sequence modeling. The models are
further tested on noisy and inaccurate training labels and the developed model is found
to be surprisingly robust and self-correcting.

In today’s world, bias and polarization are some of the biggest problems plaguing our
society. In such volatile environments, news media play a crucial role as the gatekeepers
of the information. Given the huge impact they can have on societal evolution, they have
long been studied by researchers. Researchers and practitioners often build political bias
datasets for a variety of tasks ranging from examining bias of news outlets and articles
to studying and designing algorithmic news retrieval systems for online platforms. Often,
researchers make certain simplifying assumptions in building such datasets.

In this thesis, we empirically validate three such common assumptions given the im-
portance of such datasets. The three assumptions are, (i) raters’ political leaning does
not affect their ratings of political articles, (ii) news articles follow the leaning of their
source outlet, and (iii) political leaning of a news outlet is stable across reporting on
different topics. We constructed a manually annotated ground-truth dataset of news
articles, published by several popular news media outlets in the U.S., on “Gun policy”
and “Immigration” along with their political bias leanings using Amazon Mechanical
Turk and used it to validate these assumptions.

Our findings suggest that, (i) in certain cases, liberal and conservative raters’ label
leanings of news articles differently, (ii) in many cases, the news articles do not follow the
political leaning of their source outlet, and (iii) for certain outlets, the political leaning
of the outlet does not remain unchanged while reporting on different topics/issues. We
believe, our work offers important guidelines for future attempts at building political
bias datasets which in turn will help them in building better algorithmic news retrieval
systems for online platforms.

Deep learning has recently become a very hot topic in Computer Science. It has invaded
many applications in Computer Science achieving exceptional performances compared
to other existing methods. However, neural networks have a strong memory limitation
which is considered to be one of its main challenges. This is why remarkable research
focus is recently directed towards model compression.

This thesis studies a divide-and-conquer approach that transforms an existing trained
neural network into another network with less number of parameters with the target of
decrasing its memory footprint. It takes into account the resulting loss in performance.
It is based on existing layer transformation techniques like Canonical Polyadic (CP) and
SVD affine transformations. Given an artificial neural network, trained on a certain
dataset, an agent optimizes the architecture of the neural network in a bottom-up man-
ner. It cuts the network in sub-networks of length 1. It optimizes each sub-network using
layer transformations. Then it chooses the most- promising sub-networks to construct
sub-networks of length 2. This process is repeated until it constructs an artificial neural
network that covers the functionalities of the original neural network.

This thesis offers an extensive analysis of the proposed approach. We tested this tech-
nique with different known neural network architectures with popular datasets. We
could outperform recent techniques in both the compression rate and network perfor-
mance on LeNet5 with MNIST. We could compress ResNet-20 to 25% of their original
size achieving performance comparable with networks in the literature with double this
size.

Sparse linear regression is often used to identify key transcriptional regulators by
predicting gene expression abundance from regulatory features such as transcription
factor (TF) binding or epigenomics data. However, a single linear model explaining
the gene expression of thousands of genes is limited in capturing the complexity of
cis-regulatory modules and gene co-expression patterns. Indeed, certain TFs are
known to act as both activators or repressors depending on associated cofactors and
neighbouring DNA-bound proteins. It is therefore desirable to identify clusters or
modules of co-regulated genes and model their regulatory profiles separately.
Finite mixtures of regression models are a popular tool for modeling hetero-
geneous data, while maintaining a linearity assumption. Unfortunately, they do
not take advantage of available data sets containing the molecular profiles of many
biological samples. We propose to combine the power of mixture modeling and
multi-task learning by using a penalized maximum likelihood framework for infer-
ring gene modules and regulators in multiple samples simultaneously. More specif-
ically, we regularize the likelihood function with a tree-structured L1/L2 penalty
to enable knowledge transfer between models of related cells. We optimize the
parameters of our models with a generalized EM algorithm. Experimental evalu-
ation of our method on synthetic data suggests that multi-task mixture modelling
is more suitable for identifying the true underlying cluster structure compared to a
single-task regression mixture model. Finally, we apply the model to a dataset from
the BLUEPRINT project consisting of various types of haematopoietic cells and
uncover interesting regulatory patterns.

Knowledge Graphs (KGs) play an important role in various information systems and
have application in many fields such as Semantic Web Search, Question Answering and Information Retrieval. KGs present information in the form of entities and relationships between them. Modern KGs could contain up to millions of entities and billions of facts, and they are usually built using automatic construction methods. As a result, despite the huge size of KGs, a large number of facts between their entities are still missing. That is the reason why we see the importance of the task of Knowledge Graph Completion (a.k.a. Link Prediction), which concerns the prediction of those missing facts.

Rules over a Knowledge Graph capture interpretable patterns in data and various
methods for rule learning have been proposed. Since KGs are inherently incomplete, rules can be used to deduce missing facts. Statistical measures for learned rules such as confidence reflect rule quality well when the KG is reasonably complete; however, these measures might be misleading otherwise. So, it is difficult to learn high-quality rules from the KG alone, and scalability dictates that only a small set of candidate rules is generated.
Therefore, the ranking and pruning of candidate rules are major problems. To address this issue, we propose a rule learning method that utilizes probabilistic representations of missing facts. In particular, we iteratively extend rules induced from a KG by relying on feedback from a precomputed embedding model over the KG and optionally external
information sources including text corpora. The contributions of this thesis are as follows:

• We introduce a framework for rule learning guided by external sources.

• We propose a concrete instantiation of our framework to show how to learn high-
quality rules by utilizing feedback from a pretrained embedding model.

• We conducted experiments on real-world KGs that demonstrate the effectiveness
of our novel approach with respect to both the quality of the learned rules and fact
predictions that they produce.

Named Entity Disambiguation (NED) is a Natural Language Processing task of linking mentions of named entities is a text to their corresponding entries in a Knowledge Base. It serves as a crucial component in applications such as Semantic Search, Knowledge Base Population, and Opinion Mining. Currently deployed tools for NED are based on sophisticated models that use coherence relation among entities and distributed vectors to represent the entity mentions and their contexts in a document to disambiguate them collectively. Factors that have not been considered yet in this track are the semantics of temporal information about canonical entity

forms and their mentions. Even though temporal expressions in a text give inherent

structural characteristic to it, for instance, it can map a topic being discussed to a certain period of known history, yet such expressions are leveraged no differently

than other dictionary words. In this thesis we propose the first time-aware NED

model, which extends a state-of-the-art learning to rank approach based on joint

word-entity embeddings. For this we introduce the concept of temporal signatures

that is used in our work to represent the importance of each entity in a Knowledge

Base over a historical time-line. Such signatures for the entities and temporal contexts for the entity mentions are represented in our proposed temporal vector space to model the similarities between them. We evaluated our method on CoNLL-AIDA and TAC 2010, which are two widely used datasets in the NED track. However, because such datasets are composed of news articles from a short time-period, they do not provide extensive evaluation for our proposed temoral similarity modeling. Therefore, we curated a dia-chronic dataset, diaNED, with the characteristic of temporally diverse entity mentions in its text collection.

Modern programming languages offer a lot of guarantees (no or few memory leaks, safe parallel programming, ...). But are they really safe ? The only solution is to formalize them and to prove that the expected properties are fulfilled. That’s why it is relevant to prove essential and general facts about programming languages like those presented in

Types and Programming Languages, a reference book on type systems, in Isabelle/HOL. Isabelle/HOL is a proof assistant, providing type checking and certifying the consistency of proofs. This environment allowed me to discover some imprecision and wrong parts.

This thesis addresses the multi-person tracking task with two types of representation:
body pose and segmentation mask. We explore these scenarios in the semi-supervised setting, where one available annotation is available per person during test time. More complex representations of people (segmentation mask and body pose) can provide richer understanding of visual scenes, and methods that leverage supervision during test time should be developed for the cases when supervision is available.

We propose HumanMaskTracker for the task of semi-supervised multi-person mask
tracking. Our approach builds on recent techniques proposed for the task of video
object segmentation. These include the mask refinement approach, training with synthetic data, fine-tuning per object and leveraging optical flow. In addition, we propose leveraging instance semantic segmentation proposals to give the tracker a better notion about the human class. Moreover, we propose modeling people occlusions inside the data synthesis process to make the tracker more robust to the challenges of occlusion and disocclusion.

For the task of semi-supervised multi-person pose tracking, we propose the method
HumanPoseTracker. We show that the task of multi-person pose tracking can benefit
significantly from using one pose supervision per track during test time. Fine-tuning
per object and leveraging optical flow, techniques proposed for the task of video object segmentation, prove to be highly effective for supervised pose tracking as well. Also, we propose a technique to remove false positive joint detections and develop tracking stopping criteria. A promising application of our work is presented by extending the method to generate dense from sparse annotations in videos.

The proliferation of IoT-devices is turning different kinds of embedded systems into

another relevant target for malware developers. Consequently, recent botnets are providing clients for multiple host architectures, making the clustering of malware samples a non-trivial task. While several approaches exist for statically comparing binaries of the same architecture, there are no proposed methods to compare binaries across different architectures.

Based on previous approaches for cross-architecture bug identification, we present

CrossDiff, a tool to compare executable binaries compiled for ARM, MIPS, PowerPC

and x86. CrossDiff detects functions in the input executables and translates their instructions into a common intermediate representation. Then, by pairwise comparing

functions based on features at IR-level and analyzing module-level properties we

compute a similarity score for pairs of binaries. Finally, we evaluate this approach

and the stages of the pipeline on the SPEC CPU2006 dataset with a build matrix that

iterates over different architectures, compilers, languages and optimization flags.

Inpainting and image denoising are two problems in image processing that can be

formulated as rather similar partial differential equations or PDE. In this work the effects of higher order smoothness constraints on the results of denoising and inpaintingvwere looked at. Methods from bi-level optimization were used in order to learn optimal smoothness constraints. The differences between the optimal smoothness

constraints for the two problems were looked at both for a linear model and a more complex non-linear model. The results for the linear model were that inpainting

favoured first order smoothness. For denoising on the other hand all of the different orders of smoothness made up a comparable part of the optimal smoothness constraint. Even with this difference the overall effect on the quality of the results was similar for both problems. For the non-linear model it was much more difficult to find a good smoothness constraint for the inpainting problem than for the denoising problem and the learned smoothness constraints looked very different.

Every year millions of confidential data records are leaked accidentally due to bugs, misconfiguration, or operator error. These incidents are common in large, complex, and fast evolving data processing systems. Ensuring compliance with data policies is a major challenge. Thoth is an information flow control system that uses coarse-grained taint tracking to control the flow of data. This is achieved by enforcing relevant declarative policies at processes boundaries. This enforcement is applicable regardless of bugs, misconfiguration, and compromises in application code, or actions by unprivileged operators. Designing policies that make sure all and only compliant flows are allowed remains a complex and error-prone process. In this work, we introduce PolSim, a simulation tool that aids system policy designers by validating the provided policies and systematically ensuring that the system allows all and only expected flows. Our proposed simulator approximates the dynamic run-time environment, semi-automatically suggests internal flow policies based on data flow, and provides debugging hints to help policy designers develop a working policy for the intended system before deployment.

This Master Thesis introduces portfolio selection trading strategy named ”Threshold

Based Online Algorithm”. A decision into which assets to invest is based on the thresh-

old calculated from previous trading periods. In this work have been proposed two

different ways for calculating the threshold. The main idea of the algorithm is to exploit

the mean reversion property of stock markets by identifying assets that are expected

to increase(decrease) in the following trading periods. We run numerical experiments

on real datasets to estimate the algorithm performance efficiency. By analysing the

empirical performance results, we figured out that TBOA trade-off between wealth per-

formance, volatility and downside risks. It performed better on portfolio that contains

highly volatile assets with low correlation between them. Evaluation results have shown,

that TBOA was able to outperform already existing algorithms on some real datasets.

Moreover TBOA has linear time complexity that makes algorithm runs fast.

Partial differential equations can model many physical phenomena and be used to

simulate under computer. Osmosis, which is in the form of convection-diffusion equa-

tion, has found itself many application areas in image processing. However, slow

convergence of this model, which depends on incompatibility of the drift vector field

used in the model, under current methods does not allow us to have a fast, and

possibly real-time application area.

Therefore, we get a deeper look into what incompatibility means and how it effects

steady states of the osmosis process in this thesis. In addition, we evaluate several

promising methods which offers substantial computational advantage over classical

iterative methods.

The problem of market equilibrium is defined as the problem of finding prices for the goods such that the supply in the market is equal to the demand. The problem is applicable to several market models, like the linear Arrow-Debreu model, which is one of the fundamental economic market models. Over the years, various algorithms have been developed to compute the market equilibrium of the linear Arrow-Debreu model. In 2013, Duan and Mehlhorn presented the first combinatorial polynomial time algorithm

for computing the market equilibrium of this model.

In this thesis, we optimize, generalize, and implement the Duan-Mehlhorn algorithm.

We present a novel algorithm for computing balanced ows in equality networks, which

is an application of parametric ows. This algorithm outperforms the current best

algorithm for computing balanced ows; hence, it improves Duan-Mehlhorn's algorithm by almost a factor of n, which is the size of the network. Moreover, we generalize Duan-Mehlhorn's algorithm by relaxing some of its assumptions. Finally, we describe our approach for implementing Duan-Mehlhorn's algorithm. The preliminary results of our implementation - based on random utility instances - show that the running time of the implementation scales significantly better than the theoretical time complexity.

Vulnerabilities in computer systems arise in part due to programmer's logical errors,

and in part also due to programmer's false (i.e., over-optimistic) expectations about the

guarantees that are given by the abstractions of a programming language.

For the latter kind of vulnerabilities, architectures with hardware or instructionlevel support for protection mechanisms can be useful. One trend in computer systems protection is hardware-supported enforcement of security guarantees/policies. Capability-based

machines are one instance of hardware-based protection mechanisms. CHERI is a recent implementation of a 64-bit MIPS-based capability architecture with byte-granularity memory protection.

The goal of this thesis is to provide a paper formal model of the CHERI architecture

with the aim of formal reasoning about the security guarantees that can be offered by

the features of CHERI. We first give simplified instruction operational semantics, then we prove that capabilities are unforgeable in our model. Second, we show that existing techniques for enforcing control-flow integrity can be adapted to the CHERI ISA. Third, we show that one notion of memory compartmentalization can be achieved with the help of CHERI's memory protection. We conclude by suggesting other security building blocks that would be helpful to reason about, and laying down a plan for potentially using this work for building a secure compiler, i.e., a compiler that preserves security properties.

The outlook and motivation for this work is to highlight the potential of using CHERI

as a target architecture for secure compilation.

When considering global illumination, material editing is a non-linear task and even in scenes with moderate complexity, the global nature of material editing makes final prediction of

appearance of other objects in the scene a difficult task.

In this thesis, a novel interactive method is proposed for object appearance design.

To achieve this, a randomized per-pixel parametrization of scene materials is defined. At rendering time, parametrized materials have different properties for every pixel. This way, encoding of multiple rendered results into one image is obtained. We call this collection of data a hyperimage.

Material editing means projecting the hyperimage onto a given parameter vector, which is achieved using non-linear weighted regression. Pixel guides based on geometry (normals, depth and unique object ID), materials and lighting properties of the scene enter the regression problem as pixel weights. In order to ensure that only relevant features are considered,

a rendering-based feature selection method is introduced, which uses a precomputed pixelfeature

function, encoding per-pixel importance of each parametrized material.

The method of hyperimages is independent of the underlying rendering algorithm, while

supporting a full global illumination and surface interactions.

Our method is not limited to parametrization of materials, and can be extended to other

scene properties. As an example, we show parametrization of position of an area light source.

The valuable information in correct order of alleles on the haplotypes has many applications in GWAS studies and population genetics. A considerable number of computational and statistical algorithms have been developed for haplotype phasing. Historically, these algorithms

were compared using the simulated population data with less dense markers which was inspired by genotype data from the HapMap project. Currently due to the advancement and reduction in cost of NGS, thousands of individuals across the world have been sequenced

in 1000 Genomes Project. This has generated the genotype information of individuals from different ethnicity along with much denser genetic variations in them. Here, we have developed

a scalable approach to assess state-of-the-art population-based haplotype phasing algorithms with benchmark data designed by simulation of the population (unrelated and related individuals), NGS pipeline and genotype calling. The most accurate algorithm was

MVNCall (v1) for phase inference in unrelated individuals while DuoHMM approach of Shapeit (v2) had lowest switch error rate of 0.298 %(with true genotype likelihoods) in the related individuals. Moreover, we also conducted a comprehensive assessment of algorithms for the imputation of missing genotypes in the population with a reference panel. For this metrics, Impute2 (v2.3.2) and Beagle (v4.1) both performed competitively under different imputation scenarios and had genotype concordance rate of >99%. However, Impute2 was better in imputation of genotypes with minor allele frequency of <0.025 in the reference panel.

Edgeware is a leading provider of video streaming solutions to network and service operators. The Edgeware Video Consolidation Platform(VCP) is a complete video streaming solution consisting of the Convoy Management system and Orbit streaming servers. The Orbit streaming

servers are purpose designed hardware platforms which are composed of a dedicated hardware streaming engine and a purpose designed flash as a storage system. The Orbit streaming server

is an accelerated HTTP streaming cache server which have up to 80 Gbps bandwidth and can stream to 128000 clients from a single rack unit. In line with the new trend of moving more and more functionalities towards a virtualized or software environment, the main goal of this thesis

is to make a performance comparison between Edgeware’s Orbit streaming server and one of the best generic HTTP accelerators(reverse proxy severs) after implementing logging functionality

of the Orbit on top of it. This is achieved by implementing test cases for the use cases that can help to evaluate those servers. Finally, after evaluating those proxy servers Varnish is selected and then compared the modified Varnish and Orbit to investigate the performance difference.

Testing is a crucial stage in the software development process that is used to

uncover bugs and potential security threats. If not conducted thoroughly, buggy

software may cause erroneous, malicious and even harmful behavior.

Unfortunately in most software systems, testing is either completely neglected

or not thoroughly conducted. One such example is Google's popular mobile

platform, Android OS, where inter-application communication is not properly

tested. This is because of the difficulty which it possesses in the development

overhead and the manual labour required by developers in setting up the testing

environment. Consequently, the lack of Android application testing continues to

cause Android users to experience erroneous behavior and sudden crashes,

impacting user experience and potentially resulting in financial losses. When

a caller application attempts to communicate with a potentially buggy

application, the caller application

will suffer functional errors or it may even potentially crash. Incidentally,

the user will

complain that the caller application is not providing the promised

functionality, resulting in a devaluation of the application's user rating.

Successive failures will no longer be considered as isolated events,

potentially crippling developer credibility of the calling application.

In this thesis we present an automated tester for inter-application

communication in

Android applications. The approach used for testing is called Intent based

Testing. Android applications are typically divided into multiple components

that communicate via intents: messages passed through Android OS to coordinate

operations between the different components. Intents are also used for

inter-application communication, rendering them relevant for security. In this

work, we designed and built a fully automated tool called IntentFuzzer, to test

the stability of inter-application communication of Android applications using

intents. Firstly, it statically analyzes the application to generate intents.

Next, it tests the inter-application communication by fuzzing them, that is,

injecting random input values that uncover unwanted behavior. In this way, we

are able to expose several new defects including potential security issues

which we discuss briefly in the Evaluation section.

Mobile and portable devices are machines that users carry with them everywhere,

they can be seen as constant personal assistants of modern human life. Today

the Android operating system for mobile devices is the most popular one and the

number of users still grows: as of September 2013, 1 billion devices have been

activated [Goob]. This makes the Android market attractive for developers

willing to provide new functionality. As a consequence, 48 billion applications

("apps") have been installed from the Google Play store [BBC].

Apps often require user data in order to perform the intended activity. At the

same

time parts of this data can be treated as sensitive private information, for

instance,

authentication credentials for accessing the bank account. The most significant

built-in security measure in Android, the permission system, provides only

little control on how the app is using the supplied data.

In order to mitigate the threat mentioned above, the hidden unintended app

activity,

the recent research goes in three main directions: inline-reference monitoring

modifies the app to make it safe according to user defined restrictions,

dynamic analysis monitors the app execution in order to prevent undesired

activity, and static analysis verifies the app properties from the app code

prior to execution.

As we want to have provable security guarantees before we execute the app, we

focus on static analysis. This thesis presents a novel static analysis

technique based on Horn clause resolution. In particular, we propose the

small-step concrete semantics for Android apps, we develop a new form of

abstraction which is supported by general theorem provers. Additionally, we

have proved the soundness of our analysis technique.

We have developed a tool that takes the bytecode of the Android app and makes it

accessible to the theorem prover. This enables the automated verification of a

variety of security properties, for instance, whether a certain functionality

is preceded by a particular one, for instance, whether the output of a bank

transaction is secured before sending it to the bank, or on which values it

operates, for instance, whether the IP-address of the bank is the only possible

transaction destination.

A case study as well as a performance evaluation of our tool conclude this

thesis.

With the emergence of big data, inducting regression trees on very large data

sets became a common data mining task. Even though centralized algorithms for

computing ensembles of Classification/Regression trees are a well studied

machine learning/data mining problem, their distributed versions still raise

scalability, efficiency and accuracy issues.

Most state of the art tree learning algorithms require data to reside in memory

on a single machine.

Adopting this approach for trees on big data is not feasible as the limited

resources provided by only one machine lead to scalability problems. While more

scalable implementations of tree learning algorithms have been proposed, they

typically require specialized parallel computing architectures rendering those

algorithms complex and error-prone.

In this thesis we will introduce two approaches to computing ensembles of

regression trees on very large training data sets using the MapReduce framework

as an underlying tool. The first approach employs the entire MapReduce cluster

to parallely and fully distributedly learn tree ensembles. The second approach

exploits locality and independence in the tree learning process.

This thesis introduces a new type of randomized search trees based on the

median-of-three improvement for quicksort (M3 quicksort). We consider the set

of trees obtained by running M3 quicksort. This thesis show how to obtain them

by a slightly changed insertion procedure for binary search trees. Furthermore,

if the input is random, it generates the same probability distribution as M3

quicksort and consequently accesses in the tree are faster than for randomized

search trees. In order to maintain randomness for any type of input sequence,

we introduce the concept of support nodes, which define a path covering of the

tree. With their help, and by storing the subtree size at each node, random

updates take O(log n). If instead of subtree sizes, each node stores a random

priority, updates take O(log2 n). Experiments show that while accesses are

indeed faster, update times take however too long for the method to be

competitive.

The problem of graph clustering is a central optimization problem with various

applications in numerous fields including computational biology, machine

learning, computer vision, data mining, social network analysis, VLSI design

and many more. Essentially, clustering refers to grouping objects with similar

properties in the same cluster. Designing an appropriate similarity measure is

currently a state of the art process and it is highly depended on the

underlying application. Generally speaking, the problem of graph clustering

asks to find subsets of vertices that are well-connected inside and sparsely

connected outside.

Motivated by large-scale graph clustering, we investigate local algorithms,

based on random walks, that find a set of vertices near a given starting vertex

with good worst case approximation guarantees. The running time of these

algorithms is nearly linear in the size of the output set and is independent of

the size of the whole graph. This feature makes them perfect subroutines in the

design of efficient parallel algorithms for graph clustering.

Multi-display environments (MDEs) of all kinds are used a lot nowadays. A

wide variety of devices helps to build a common display space. TVs, monitors,

projected surfaces, phones, tablets, everything that has the ability to display

visual information can be incorporated in multi-display environments.

While the main research emphasis so far has been on interaction techniques

and user experience within different MDEs, some research topics are dealing

with static and dynamic display reconfiguration. In fact, several studies

already work with MDEs that are capable of display reconfiguration on-the-fly.

Different frameworks can perform splitting, streaming and rendering of visual

data on large-scale displays with the ability of dynamic display

reconfiguration to calibrate multiple-projectors or to combine different

heterogeneous displays into one display wall dynamically. However, all of these

frameworks require different approaches

for display reconfiguration. Our goal is to create a model for display

reconfiguration which will be abstract, transparent, will work in real-time,

and will be easily deployable in any MDE.

In this work we present an extension to a software framework called Display as

a Service (DaaS). This extension is represented as a model for real-time

display reconfiguration using DaaS. The DaaS framework allows for generic and

transparent management of pixel-transport assuming only a network connection,

providing a simple high-level implementation for pixel-producing and

pixel-displaying applications. The main limitation of this approach is a

certain delay between pixel generation and display. However, the video encoding

and network transport are subject of improvements which will solve the problem

in the future.

As a proof of concept, we demonstrate three usage scenarios: manual dynamic

display reconfiguration, automatic display calibration, and real-time display

tracking. We also present a new algorithm for precise display calibration using

markers and a handheld camera. The calibration results are evaluated using

different tracking libraries. The additional precise calibration part for our

proposed algorithm makes the calibration accuracy several times better compared

to a naive approach.

Principal Component Analysis (PCA) is a widely used tool for, e.g., exploratory

data analysis, dimensionality reduction and clustering. However, it is well

known that PCA is strongly aected by the presence of outliers and, thus, is

vulnerable to both gross measurement error and adversarial manipulation of the

data. This phenomenon motivates the development of robust PCA as the problem of

recovering the principal components of the uncontaminated data.

In this thesis, we propose two new algorithms, QRPCA and MDRPCA, for robust PCA

components based on the projection-pursuit approach of Huber. While the

resulting optimization problems are non-convex and non-smooth, we show that

they can be eciently minimized via the RatioDCA using bundle

methods/accelerated proximal methods for the interior problem. The key

ingredient for the most promising algorithm (QRPCA) is a robust, location

invariant scale measure with breakdown point 0.5. Extensive experiments show

that our QRPCA is competitive with current state-of-the-art methods and

outperforms other methods in particular for a large number of outliers.

Autonomous Driving benefits strongly from a 3D reconstruction of the

environment in real-time, often obtained via stereo vision. Semi-Global

Matching (SGM) is a popular�method of choice for solving this task and is

already in use for production vehicles. Despite the enormous progress in the

field and the high performance of modern methods, one key challenge remains:

stereo vision in automotive scenarios during difficult weather or illumination

conditions. Current methods generate strong temporal noise,�many disparity

outliers, and false positives on a segmentation level. This work addresses

these issues by formulating a temporal prior and a scene prior and applying

them to SGM. For image sequences captured on a highway during rain, during

snowfall, or in low light, these priors significantly improve the object

detection rate while reducing the false positive rate. The algorithm also

outperforms the�ECCV Robust�Vision Challenge winner, iSGM.�

Advances in the field of systems biology have provided the biological community

with massive amounts of pathway data that describe the interplay of genes and

their products. The resulting biological networks usually consist of thousands

of entities and interactions that can be modeled mathematically as graphs.

Since these networks only provide a static picture of the accumulated

knowledge, pathways that are affected during development of complex diseases

cannot be extracted easily. This gap can be lled by means of OMICS

technologies such as DNA microarrays, which measure the activity of genes and

proteins under different conditions. Integration of both interaction and

expression datasets can increase the quality and accuracy of analysis when

compared to independant inspection of each. However, sophisticated

computational methods are needed to deal with the size of the datasets while

also accounting for the presence of biological and technological noise inherent

in the data generating process.

In this dissertation the KeyPathwayMiner is presented, a method that enables

the extraction and visualization of affected pathways given the results of a

series of gene expression studies. Specically, given network and gene

expression data, KeyPathwayMiner identies those maximal subgraphs where all

but k nodes of the subnetwork are differentially expressed in all but at most l

cases in the gene expression data. This new formulation allows users to control

the number of outliers with two parameters that provide good interpretability

of the solutions. Since identifying these subgraphs is computationally

intensive, an heuristic algorithm based on Ant Colony Optimization was designed

and adapted to this problem, where solutions are reported in the order of

seconds on a standard personal computer. The Key-PathwayMiner was tested on

real Huntingtons Disease and Breast Cancer datasets, where it is able to

extract pathways containing a large percentage of known relevant genes when

compared to other similar approaches.

KeyPathwayMiner has been implemented as a plugin for Cytoscape, one of the most

widely used open source biological network analysis and visualization

platforms. The Key-PathwayMiner is available online at

keypathwayminer.mpi-inf.mpg.de or through the plugin manager of

Cytoscape.

In this work we proposed a novel transductive method to solve the problem of

learning from partially labeled data. Our main idea was to aggregate information

obtained from several clusterings to infer the labels of the unlabeled data.

While our method is not restricted to a specific clustering method, we chose

to use in our experiments the normalized variant of 1-spectral clustering, which

was demonstrated to produce in most cases better clusterings than the standard

spectral clustering method. Our approach yielded results which were at least

comparable to, and in some cases even significantly better than the best results

obtained by state-of-the-art methods reported in the literature.

Furthermore, we proposed a novel active learning framework that is able to

query the labels of the most informative points which help in the classification

of the unlabeled points. For the majority vote scheme we provided some

guarantees on the number of points that should be drawn from each cluster in

order

to infer the correct label of the cluster with high probability. Moreover, in

the

ridge regression scheme we proposed an algorithm that in each step selects the

most uncertain point in terms of the prediction function of the classier (the

point that lies near the decision boundary of the classifier). In both cases,

experimental results show the strength of our methods and confirm our

theoretical

guarantees.

The results look very promising and open several interesting directions of

future research. For the SSL scheme, it is interesting to test the performance

of several other clustering approaches, such as k-means, standard spectral

clustering, hierarchical clustering, e.t.c. and combine them together in one

general

method. Our intuition is that the algorithm should be able to select only the

good clusterings that provide discriminative information for each specific

problem.

Apart from ridge regression, it would be beneficial to experiment with other

fitting approaches that produce sparse representations in our constructed

basis. For the active learning framework, one interesting direction is to

further generalize it into more general clusterings that take into account the

hierarchical structure of data. In that way, we will take advantage of the

underlying hierarchy and by adaptively selecting the pruning of the cluster

tree we can (potentially) further improve our sampling strategy. Additionally,

we believe that in the multi-clustering scenario extensive improvements of our

algorithm can be proposed in order to better take advantage of the variation in

the multiple clustering representations of the data. Finally, as our methods

scale to large-scale problems and partially labeled data occurs in many

different areas ranging from web documents to protein data, there is room for

many interesting applications of the proposed methods.

Variational methods are among the most successful approaches for computing

high-quality optical ow. However, there are still many ways to improve. In this

thesis we fist provide a general overview of the main ideas of existing

approaches by the example of the complementary optical ow method of Zimmer et

al. [19]. This serves us as a starting point for introducing the concept of

automatic local selection of the most suitable constancy assumption on image

features, which allows to further improve the quality of optical ow estimation.

As a main contribution, we provide the variational formulation, that directly

leads to the proposed behavior. The derived model is then analysed and

evaluated in the series of experiments.

According to the FCC, spectrum allocation will be one of the problems of future

telecommunication systems. Indeed, the available parts of the spectrum have

been assigned statically to some applications such as mobile networks and

broadcasting systems; hence finding a proper operating band for new systems is

difficult. These telecommunication systems are called primary users. However,

primary users do not always use their entire bandwidth, and therefore a lot of

spectrum holes can be detected. These spectrum holes can be utilized for

undefined systems called secondary users. Federal communication commission

(FCC) introduced cognitive radio which detects these holes and assigns

them to secondary users.

There are several techniques for detention of signals such as energy based

detection, matched filter detection and cyclostationary based detection.

Cyclostationary based detection as one of the most sensitive methods, can be

used for detection and classification of different systems. However,

traditional multi-cycle and single-cycle detectors suffer from high complexity.

Fortunately, using some prior knowledge about the signal, this shortcoming can

be solved.

In this thesis, signals of DVB-T2 as a broadcasting system and 3GPP LTE and

IEEE 802.16 (WiMAX) as mobile networks have been evaluated and two

cyclostationary based algorithms for detection and classification of these

signals in SISO and MIMO antenna configurations are proposed.

In this thesis an evaluation method on indoor positioning system called LORIOT

is presented. This positioning system combines two technologies (RFID and IR)

for positioning depending on Geo-referenced dynamic bayesian networks. LORIOT

allows the users to calculate their position on their own device without sending

any data to a server responsible for calculating the position [3]. This property

provides less complexity and fast calculation. This positioning method is

developed by placing the tags in the environment and letting the user carry the

sensors that are used to read data from these tags. The user is then able to

choose either to pass the positioning data to any third party application or

not. The main focus here is to check the actual accuracy and performance of

indoor positioning systems using the proposed evaluation method which is tested

on LORIOT. Most of the evaluation methods that have been used to test the level

of accuracy of indoor positioning systems are biased and not good enough. For

instance, the system is tested under optimal conditions of the environment. To

achieve this goal, the evaluation method will be used to test LORIOT in a

natural environment and by using data of natural traces of people walking in

the environment without giving them any task to do. This type of evaluation

criteria improves the results because the system would be installed in an

environment which has the same properties that the environment has in this

study, (where the evaluation tests are done). In addition, the system will

position people while walking naturally (unlike most evaluation methods which

test indoor positioning systems not while walking).

Nowadays, smartphones and tablets are replacing the personal computer for the

average user. As more activities move to these gadgets, so does the sensitive

data with which they operate. However, there are few data protection mechanisms

for the mobile world at the moment, especially for scenarios where the attacker

has

full access to the device (e.g. when the device is lost or stolen). In this

thesis,

we tackle this problem and propose a novel encryption system for Android, the

top-selling mobile operating system.

Our investigation of the Android platform leads to a set of observations that

motivate our effort. Firstly, the existing defense mechanisms are too weak or

too rigid in terms of access control and granularity of the secured data unit.

Secondly, Android can be corrupted such that the default encryption solution

will reveal sensitive content via the debug interface. In response, we design

and

(partially) implement an encryption system that addresses these shortcomings

and operates in a manner that is transparent to the user. Also, by leveraging

hardware security mechanisms, our system offers security guarantees even when

running on a corrupted OS. Moreover, the system is conceptually designed to

operate in an enterprise environment where mobile devices are administered

by a central authority. Finally, we provide a prototypical implementation and

evaluate our system to show the practicality of our approach.

Over the past few decades, there is a multifold increase in the amount of

digital data that is being generated. Various attempts are being made to

process this vast amount of data in a fast and efficient manner. Hadoop -

MapReduce is one such software framework that has gained popularity in the last

few years. It provides a reliable and easier way to process huge amount of data

in-parallel on large computing cluster. However, Hadoop always persists

intermediate results to the local disk. As a result, Hadoop usually suffers

from long execution runtimes as it typically pays a high I/O cost for running

jobs.

The state-of-the-art computing clusters have enough main memory capacity to

hold terabytes of data in main memory. We have built M3R (Main Memory

MapReduce) framework, a prototype for generic main memory-based data

processing. M3R can execute MapReduce jobs and also in addition it can execute

general data processing jobs.

This master thesis in particular, focuses on countering the data-skewness

problem for MapReduce jobs on M3R. Intermediate data following skewed

distribution could lead to computational imbalance amongst the reduce tasks,

resulting in longer MapReduce job execution times. This provides a scope for

rebalancing the intermediate data and thereby reducing the total job runtimes.

We propose a novel dynamic approach of data rebalancing, to counter the reducer

side data skewness. Our proposed on-the-fly skew countering approach, attempts

to detect the level of skewness in the intermediate data and rebalances the

intermediate data amongst the reduce tasks. The proposed mechanism performs all

the skew-countering related activities during the execution of actual MapReduce

job. We have implemented this reduce side skew countering mechanism as a part

of the M3R framework. The experiments conducted to study the behavior of this

M3R data-rebalancing approach shows there is a significant reduction in the

map-reduce job runtimes. In case of the data-skewed input, our proposed

skew-control approach for M3R has reduced the total map-reduce job runtime (up

to 31 ) when compared to M3R without skew-control.

Probabilistic mixture model is a powerful tool to provide a low-dimensional

representation of count data. In the context of topic modeling, this amounts to

representing the distribution of one document as a mixture of multiple

distributions known as topics. The mixing proportions are called coecients. A

common attempt is to introduce sparsity into both the topics and the coecients

for better interpretability. We first discuss the problem of recovering sparse

coecients of given documents when the topics are known. This is formulated as

a penalized least squares problem on the probability simplex, where the

sparsity is achieved through regularization. However, the typical `1

regularizer becomes toothless in this case since it is constant over the

simplex. To overcome this issue, we propose a group of concave penalties for

inducing sparsity. An alternative approach is to post-process the solution of

non-negative lasso to produce result that conform to the simplex constraint.

Our experiments show that both kinds of approaches can effiectively recover the

sparsity pattern of coefficients. We

then elaborately compare their robustness for dierent characteristics of input

data. The second problem we discuss is to model both the topics and the

coefficients of a collection of documents via matrix factorization. We propose

the LpT approach, in which all the topics and coefficients are constrained on

the simplex, and the `p penalty is imposed on each topic to promote sparsity.

We also consider procedures that post-process the solutions of other methods.

For example, the L1 approach first solves the problem where the simplex

constraints imposed on the topics are relaxed into the non-negativity

constraints, and the `p penalty is the replaced by the `1 penalty. Afterwards,

L1 normalize the estimated topics to generate results satisfying the simplex

constraints. As detecting the number of mixture components inherent in the data

is of central importance for the probabilistic mixture model, we analyze how

the regularization techniques can help us to automatically find out this

number. We compare the capabilities of these approaches to recover the low-rank

structure underlying the data, when the number of topics are correctly specied

and over-specified, respectively.

The empirical results demonstrate that LpT and L1 can discover the sparsity

pattern of the ground truth. In addition, when the number of topics is

over-specied, they adapt to the true number of topics.

We investigate load balancing games in the context of unrelated machines

scheduling. In such a game, there are a number of jobs and a number of

machines, and each job needs to be scheduled on one machine. A collection of

values pij are given, where pij indicates the processing time of job i on

machine j. Moreover, each job is controlled by a selfish player who only

wants to minimize the completion time of his job while disregarding other

players' welfare. The outcome schedule is a Nash equilibrium if no player

can unilaterally change his machine and reduce the completion time of his job.

It is known that in an equilibrium, the performance of the system can

be far from optimal. The degradation of the system performance in Nash

equilibrium is defined as the price of anarchy (PoA): the ratio of the cost

of the worst Nash equilibrium to the cost of the optimal scheduling. Clever

scheduling policies can be designed to reduce PoA. These scheduling policies

are called coordination mechanisms.

It has been posed as an open question "what is the best possible lower bound

when coordination mechanisms use preemption". In this thesis we prove a lower

bound of ( logm log logm) for all symmetric preemptive coordination mechanisms.

Moreover we study the lower bound for the unusual case when the coordination

mechanisms are asymmetric and we get the same bound

under the weak assumption that machines have no IDs. On the positive side we

prove that the inefficiency-based mechanism can achieve a constant PoA when the

maximum inefficiency of the jobs is bounded by a constant.

Designing communications protocols specifically adapted to relativistic

situations (i.e. constrained by special relativity theory) is taking advantage

of uniquely relativistic features to accomplish otherwise impossible tasks.

Kent [Ken99] has demonstrated, for example, that secure bit commitment is

possible using a protocol exploiting relativistic causality constraints, even

though it is known to be impossible otherwise. Therefore, Kent's protocol gives

a theoretical solution to the problem of finding commitment

schemes secure over arbitrarily long time intervals. The functionality only

requires from

the committer a sequence of communications, including a post-revelation

validation,

each of which is guaranteed to be independent of its predecessor.

We propose to verify the security of the relativistic commitment not as a stand

alone protocol, but as an entity which is part of an unpredictable environment.

To achieve this task we use the universal composability paradigm defined by

Canetti [Can01]. The relevant property of the paradigm is the guarantee of

security even when a secure protocol

is composed with an arbitrary set of protocols, or, more generally, when the

protocol is used as an element of a possibly complex system. Unfortunately,

Kent's relativistic bit commitment satisfies universal composability only with

certain restrictions on the adversarial model. However, we construct a

two-party universal composable commitment

protocol, also based on general relativistic assumptions.

We present a unified framework for query answering over uncertain RDF knowledge

bases. Specifically, our proposed design combines correlated base facts with a

query driven, top down deductive grounding phase of first-order logic formulas

(i.e., Horn rules) followed by a probabilistic inference phase. In addition

to static input correlations among base facts, we employ the lineage structure

obtained from processing the rules during grounding phase, in order to trace

the logical dependencies of query answers (i.e., derived facts) back to the base

facts. Thus, correlations (or more precisely: dependencies) among facts in a

knowledge base may arise from two sources: 1) static input dependencies

obtained from real-world observations; and 2) dynamic dependencies induced at

query time by the rule-based lineage structure of the query answer.

Our implementation employs state-of-the-art inference techniques: We

apply exact inference whenever tractable, the detection of shared factors,

shrink-

age of Boolean formula when feasible, and Gibbs sampling in the general case.

Our experiments are conducted on real data sets with synthetic expansion of

correlated base facts. The experimental evaluation demonstrates the practical

viability and scalability of our approach, achieving interactive query response

times over a very large knowledge base. The experimental results provide the

success guarantee of our presented framework.

Recurrent genomic amplications and deletions characterize cancer genomes and

contribute to disease evolution. Array Comparative Genomic Hybridization (aCGH)

technology allows detection of chromosomal copy number aberrations in the

genomic DNA of tumors with high resolution. The association of consistent copy

number aberrations with particular types of cancer facilitates the

understanding of the pathogenesis of the disease, and contributes towards the

improvement of diagnosis, prognosis and the development of drugs. However,

distinguishing aberrations that are relevant to cancer from random background

aberrations is a dicult task, due to the high dimensionality of the aCGH data.

Different statistical methods have been developed to identify non-random gains

and losses across multiple samples. Their approaches vary in several aspects:

requirements necessary for an aberration to be recurrent, preprocessing of the

input data, statistical approaches used for assessing signicance of a

recurrent aberration and other biological considerations they use. So far,

multiple-sample analysis methods have only been evaluated qualitatively and

their relative merits remain unknown. In this work we propose an approach for

quantitative evaluation of the performance of four selected methods. We use

simulated data with known aberrations to validate each method and we interpret

the different outcomes. We also compare the performance of the methods on a

collection of neuroblastoma tumors by quantifying the agreement between

methods. We select appropriate techniques to combine the outputs of the methods

into a meaningful aggregation in order to obtain a high condence lists of

signicant copy number aberrations.

Super resolution is the task of reconstructing one or several high resolution

images, from one or several low resolution images. A variety of super resolution

methods have been proposed over the past three decades, some following a

singleframe based methodology while the others utilizing a multiple-frame based

one. These methods are usually very sensitive to their underlying model of data

and noise, which limits their performance. In this thesis, we propose and

compare

two multiple-frame based approaches that address such shortcomings. In the rst

proposal we investigate a fast, local approach which combines the low resolution

frames via warping and then performs diusion-based inpainting. The second

proposal models the image formation process in a variational framework with

regularization that is robust to errors in motion and blur estimation. In

addition, we

introduce a brightness adaptation step which results in images with sharper

edges.

An accurate estimation of optical ow among the low resolution measurements

is a fundamental step towards high quality super resolution for both methods.

Experiments conrm the eectiveness of our method on a variety of super

resolution

benchmark sequences, as well as its superiority in performance to other

closely-related methods.

Time that an imaging device needs to produce results

is one of the most crucial factors in medical imaging.

Shorter scanning duration causes fewer artifacts such as those

created by the patient motion. In addition, it increases patient comfort and

in the case of some imaging modalities also decreases exposure to radiation.

There are some possibilities,

hardware-based or software-based, to improve the imaging speed. One way

is to speed up the scanning process by acquiring fewer measurements. A recently

developed mathematical framework called compressed

sensing shows that it is possible to accurately recover undersampled images

provided a suitable measurement matrix is used and the image itself has a

sparse representation.

Nevertheless, not only measurements are important but also good reconstruction

models are required. Such models are usually expressed as optimization

problems.

In this thesis, we concentrated on the reconstruction of the undersampled

Magnetic Resonance (MR) images.

For this purpose a complex-valued reconstruction model was provided.

Since the reconstruction should be as quick as possible,

fast methods to find the solution for the reconstruction problem are required.

To meet this objective, three popular algorithms FISTA,

Augmented Lagrangian and Non-linear Conjugate Gradient were

adopted to work with our model.

By changing the complex-valued reconstruction model slightly

and dualizing the problem, we obtained an instance of the quadratically

constrained quadratic program where both the objective function and the

constraints are twice differentiable. Hence new model opened doors to two other

methods, the first order method which resembles FISTA and is called in

this thesis Normed Constrained Quadratic FGP, and the second order

method called Truncated Newton Primal Dual Interior Point.

Next, in order to

compare performance of the methods, we set up the experiments and evaluated all

presented methods against the problem of reconstructing undersampled MR images.

In the experiments we used a number of invocations of the Fourier transform

to measure the performance of all algorithms.

As a result of the experiments we found that in the context of the original

model the performance of Augmented Lagrangian is better than the other

two methods. Performance of Non-linear Conjugate Gradient and

FISTA are about the same.

In the context of the extended model Normed Constrained Quadratic FGP

beats the Truncated Newton Primal Dual Interior Point method.

The constantly evolving Web reects the evolution of society in the cyberspace.

Projects like the Open Directory Project (dmoz.org) can be understood as a

collective memory of society on the Web. The main assumption is that such

collective Web memories evolve when a certain cognition level about a concept

has been exceeded. In the scope of our work we analyse the New York Times

archive for concept detection. There are several approaches to the concept

modelling. We introduce an alternative model for concepts, which does not make

any additional assumptions about types of contained entities or the number of

entities in the corpus. Moreover, the proposed distributed concept computation

algorithm enables the large scale archive analysis. We also introduce a model

of cognition level and explain how it can be employed to predict changes in the

category system of DMOZ.

This master's thesis investigates the benefit of utilizing depth

information acquired by a time-of-flight (ToF) camera for hand shape

recognition from unrestricted viewpoints. Specifically, we assess the

hypothesis that classical 3D content descriptors might be

inappropriate for ToF depth images due to the 2.5D nature and

noisiness of the data and possible expensive computations in 3D space.

Instead, we extend 2D descriptors to make use of the additional

semantics of depth images. Our system is based on the appearance-based

retrieval paradigm, using a synthetic 3D hand model to generate its

database. The system is able to run at interactive frame rates. For

increased robustness, no color, intensity, or time coherence

information is used. A novel, domain-specific algorithm for segmenting

the forearm from the upper body based on reprojecting the acquired

geometry into the lateral view is introduced. Moreover, three kinds of

descriptors exploiting depth data are proposed and the made design

choices are experimentally supported. The whole system is then

evaluated on an American sign language fingerspelling dataset.

However, the retrieval performance still leaves room for improvements.

Several insights and possible reasons are discussed.

The fact that birds have feathers and ice is cold seems trivially true. Yet,

most machine-readable sources of knowledge either lack such common sense facts

entirely or have only limited coverage. Prior work on automated knowledge base

construction has largely focused on relations between named entities and on

taxonomic knowledge, while disregarding common sense properties.

Extracting such structured data from text is challenging, especially due to the

scarcity of explicitly expressed knowledge. Even when relying on large document

collections, patternbased information extraction approaches typically discover

insufficient amounts of information.

This thesis investigates harvesting massive amounts of common sense knowledge

using the textual knowledge of the entire Web, yet staying away from the

massive engineering efforts in procuring such a large corpus as a Web. Despite

the advancements in knowledge harvesting, we observed that the state of the art

methods were limited in terms of accuracy and discovered insufficient amounts

of information under our desired setting.

This thesis shows how to gather large amounts of common sense facts from Web

N-gram data, using seeds from the existing knowledge bases like ConceptNet. Our

novel contributions include scalable methods for tapping onto Web-scale data

and a new scoring model to determine which patterns and facts are most reliable.

An extensive experimental evaluation is provided for three different binary

relations, comparing different sources of n-gram data as well as different

algorithms. The experimental results show that this approach extends ConceptNet

by many orders of magnitude (more than 200-fold) at comparable levels of

precision.

Time is one of the main factors in any kind of real-life systems. When a certain system is

analysed one is often interested in its evolution with respect to time. Various phenomena

can be described using a form of time-dependency. The difference between load in

call-centres is the example of time-dependency in queueing systems. The process of

migration of biological species in autumn and spring is another illustration of changing

the behaviour in time. The ageing process in critical infrastructures (which can result in

the system component failure) can also be considered as another type of time-dependent

evolution.

Considering the variability in time for chemical and biological systems one comes to

the general tasks of systems biology [9]. It is an inter-disciplinary study field which

investigates complex interactions between components of biological systems and aims

to explore the fundamental laws and new features of them. Systems biology is also

used for referring to a certain type of research cycle. It starts with the creation a

model. One tries to describe the behaviour in a most intuitive and informative way

which assumes convenience and visibility of future analysis. The traditional approach

is based on deterministic models where the evolution can be predicted with certainty.

This type of model usually operates at a macroscopic scale and if one considers chemical

reactions the state of the system is represented by the concentrations of species and

a continuous deterministic change is assumed. A set of ordinary differential equations

(ODE) is one of the ways to describe such kind of models. To obtain a solution numerical

methods are applied. The choice of a certain ODE-solver depends on the type of the

ODE system. Another option is a full description of the chemical reaction system where

we model each single molecule explicitly operating with their properties and positions

in space. Naturally it is difficult to treat big systems in a such way and it also creates

restrictions for computational analysis.

However it reveals that the deterministic formalism is not always sufficient to describe

all possible ways for the system to evolve. For instance, the Lambda phage decision

circuit [1] can be a motivational example of such system. When the lambda phage

virus infects the E.coli bacterium it can evolve in two different ways. The first one is

lysogeny where the genome of the virus is integrated into the genome of the bacterium.

Virus DNA is then replicated in descendant cells using the replication mechanism of

the host cell. Another way is entering the lytic cycle, which means that new phages

are synthesized directly in the host cell and finally its membrane is destroyed and new

phages are released. A deterministic model is not appropriate to describe this process of

choosing between two pathways as this decision is probabilistic and one needs a stochastic

model to give an appropriate description.

Another important issue which has to be addressed is the fact that the state of the

system changes discretely. It means that one considers not the continuous change of

chemical species concentrations but discrete events occuring with different probabilities

(they can be time-dependent as well).

We will use the continuous-time Markov Population Models (MPMs) formalism in

this thesis to describe discrete-state stochastic systems. They are indeed continuous-

1

time Markov processes, where the state of the system represents populations and it is

expressed by the vector of natural numbers. Such systems can have innitely many

states. For the case of chemical reactions network it results in the fact that one can

not provide strict upper bounds for the population of certain species. When analysing

these systems one can estimate measures of interest (like expectation and variance for

the certain species populations at a given time instant). Besides this, probabilities for

certain events to occur can be important (for instance, the probability for population to

reach the threshold or the probability for given species to extinct).

The usual way to investigate properties of these systems is simulation [8] which means

that a large amount of possible sample trajectories are generated and then analysed.

However it can be difficult to collect a sufficient number of trajectories to provide statistical

estimations of good quality. Besides the simulation, approaches based on the

uniformization technique have been proven to be computationally efficient for analysis

of time-independent MPMs. In the case of time-dependent processes only few results

concerning the performance of numerical techniques are known [2].

Here we present a method for conducting an analysis of MPMs that can have possibly

infinitely many states and their dynamics is time-dependent. To cope with the problem

we combine the ideas of on-the-y uniformization [5] with the method for treating timeinhomogeneous

behaviour presented by Bucholz.

Current Web technologies allow developers to create rich Web-applications.

Unlike desktop applications Web 2.0 programs are created by easily linking

several existing components. This approach, also known as mashup, allows to use

JavaScript to connect web-services and browser components together.

I have extended this development method by bringing 3D and virtual world

networking components into the browser. This allowed me to create Virtual

Worlds Web-application similar to Second Life. I have wrapped the open-source

Sirikata platform for virtual worlds into a Web-service component, created

XML3D rendering component, combined them with other browser services and thus

created a fully-featured 3D world application right inside of the browser

In this thesis a general approach for detection of symmetric structures in

images is presented. Rather than relying on some feature points to extract

symmetries, symmetries are described using a probabilistic formulation of image

self-similarity. Using a Markov random field we obtain a joint probability

distribution describing all assignments of the image to itself. Due to the high

dimensionality of this joint distribution, we do not examine this distribution

directly, but approximate its marginals in order to gather information about

the symmetries with the image. In the case of perfect symmetries this

approximation is done using belief propagation. A novel variant of belief

propagation is introduced allowing for reliable approximations when dealing

with approximate symmetries. We apply our approach to several images ranging

from perfect synthetic symmetries to real-world scenarios, demonstrating the

capabilities of probabilistic frameworks for symmetry detection.

Our main goal is to create realistically looking animation in real-time. To

that end, we are interested in fast ray tracing. Ray tracing recursively traces

photon movement from the camera (backward) or light sources (forward). To find

where the first intersection between a given ray and the objects in the scene

is we use acceleration structures, for example kd-trees. Kd-trees are

considered to perform best in the majority of cases, however due to their large

construction times are often avoided for dynamic scenes. In this work we try to

overcome this obstacle by building the kd-tree in parallel on many

cores of a GPU.

Our algorithm build the kd-tree in a top-down breath-first fashion, with many

threads processing each node of the tree. For each node we test 31 uniformly

distributed candidate split planes along each axis and use the Surface Area

cost function to estimate the best one. In order to reach maximum performance,

the kd-tree construction is divided into 4 stages. Each of them handles tree

nodes of different primitive count, differs in how counting is resolved and how

work is distributed on the GPU.

Our current program constructs kd-trees faster than other GPU implementations,

while maintaining competing quality compared to serial CPU programs. Tests have

shown that execution time scales well in respect to power of the GPU and it

will most likely continue doing so with future releases of the hardware.

Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for static derivation of precise WCET estimates is determination of upper bounds on the number of times loops can be iterated.

The idea of the parametric loop bound analysis is to express the upper loop bound as a formula depending on parameters { variables and expressions staying constant within the loop body. The formula is constructed once for each loop. Then by instantiating this formula with

values of parameters acquired externally (from value analysis, etc.), a concrete loop bound can be computed without high computational effort.

Phrase snippets of large text corpora like news articles or web search results

offer great insight and analytical value. While much of the prior work is

focussed on efficient storage and retrieval of all candidate phrases, little

emphasis has been laid on the quality of the result set. In this thesis, we

define phrases of interest and propose a framework

for mining and post-processing interesting phrases. We focus on the quality of

phrases and develop techniques to mine minimal-length maximal-informative

sequences of words.The techniques developed are streamed into a post-processing

pipeline and include exact and approximate match-based merging, incomplete

phrase detection with filtering, and heuristics-based phrase classification.

The strategies aim to prune the candidate set of phrases down to the ones being

meaningful and having rich content. We characterize

the phrases with heuristics- and NLP-based features. We use a supervised

learning based regression model to predict their interestingness. Further, we

develop and analyze ranking and grouping models for presenting the phrases to

the user. Finally, we discuss relevance and performance evaluation of our

techniques. Our framework is evaluated using a recently released real world

corpus of New York Times news articles.

In this thesis we investigate the use of uniform grids as acceleration

structures for ray tracing on data-parallel machines such as modern graphics

processors. The main focus of this work is the trade-off between construction

time and rendering performance provided by the acceleration structures,

which is important for rendering dynamic scenes. We propose several parallel

construction algorithms for uniform and two-level grids as well as a ray

triangle intersection algorithm, which improves SIMD utilization for incoherent

rays. The result of this work is a GPU ray tracer with performance

for dynamic scenes that is comparable and in some cases better than the best

known implementations today.

Constraint Satisfaction Problems (CSPs) are defined over a set of variables

whose state must satisfy a number of constraints. We study a class of

algorithms called Message Passing Algorithms, which aim at finding the

probability distribution of the variables

over the space of satisfying assignments. These algorithms involve passing

local messages (according to some message update rules) over the edges of a

factor graph constructed corresponding to the CSP. We focus on the Belief

Propagation (BP) algorithm, which

finds exact solution marginals for tree-like factor graphs. However,

convergence and exactness cannot be guaranteed for a general factor graph. We

propose a method for improving BP to account for cycles in the factor graph. We

also study another message passing algorithm known as Survey Propagation (SP),

which is empirically quite effective in solving random K-SAT instances, even

when the density is close to the satisfiability threshold. We contribute to the

theoretical understanding of SP by deriving the SP

equations from the BP message update rules.

Tracking and resolving of software bugs are very important tasks for software

developers and maintainers. Bug-tracking systems are tools which are widely

used in open source projects to support these activities. The empirical

Software Engineering research community pays considerable attention to

bug-tracking-related topics in order to provide bug-tracking systems users with

adequate software and tool support.

Bug-tracking is a highly socialized process which requires constant

communication between developers and bug reporters. However, the inherent

social structure of bug tracking systems and its influence on everyday

bug-tracking has earlier been poorly studied.

In this work I address the role of bug reporter reputation. Using publicly

available information from bug-tracking system database, I model bug reporter

reputation to check whether there is any evidence of relation between reporter

reputation and attention from developers his bugs get.

If reputation actually plays important role in bug-tracking activities and can

relatively easily be extracted, existing prediction techniques

could potentially be improved by using reputation as additional input variable;

bug-tracking software could be supported with more formal

notion of reporter reputation.

Predicting likely software defects in the future is valuable for project

managers when planning resource allocation for software testing. But building

prediction models using only code metrics may not be suffice for accurate

results. In this work, we investigate the value of code history metrics that

can be collected from the project's version archives for the purpose of defect

prediction. Our results suggest that prediction models built using code history

metrics outperform those using traditional code metrics only.

Long-term security ensures that a protocol remains secure even in the future,

when the adversarial computational power could, potentially, become unlimited.

The notion of universal composability preserves the security of a cryptographic

protocol when it is used in combination with any other protocols, in possibly

complex systems. The area of long-term universally composable secure protocols

has been developed mostly by Müller-Quade and Unruh. Their research conducted

so far has shown the existence of secure long-term UC commitments under general

cryptographic assumptions, thus without having an emphasis on the efficiency of

the protocols designed. Building on their work and using very efficient

zero-knowledge proofs of knowledge from [CL02], this thesis presents a new

long-term universally composable secure commitment protocol that is both

efficient and plausible to use in practice.

For a long time now, interactive 3D graphics has been dominated by

rasterization algorithms. However, thanks to more than a decade of research and

the fast evolution of computer hardware, ray tracing has recently achieved

real-time performance. Thus, it is likely that ray tracing will become a

commodity choice for adding complex lighting effects to real-time rendering

engines. Nonetheless, interactive ray tracing research has been mostly

concentrated on few specific combinations of algorithms and data structures.

In this thesis we present RTfact (an attempt to bring the different

aspects of ray tracing together in a component oriented, generic, and

portable way, without sacrificing the performance benefits of hand-tuned

single-purpose implementations. RTfact is a template library consisting of

packet-centric components combined into an ecient ray tracing framework. Our

generic design approach with loosely coupled algorithms and data structures

allows for seamless integration of new algorithms with maximum runtime

performance, while leveraging as much of the existing code base as possible.

The SIMD abstraction layer of RTfact enables easy porting to new

microprocessor architectures with wider SIMD instruction sets without the

need of modifying existing code. The eciency of C++ templates allows us

to achieve fine component granularity and to incorporate a flexible physically-

based surface shading model, which enables exploitation of ray coherence.

As a proof of concept we apply the library to a variety of rendering tasks and

demonstrate its ability to deliver performance equal to existing optimized

implementations.

Homogeneous structures are a well studied research area and have variety uses

like constructions in model theory and permutation group theory. Recently

Cameron and Nesetril have introduced homomorphism homogeneity by incorporating

homomorphisms in the definition of homogeneity. This has attracted a fair bit

of attention from the research community and a growing amount of research has

been done in this area for different relational structures.

The first goal of this thesis is to investigate the different classes of

homomorphism homogeneous simple undirected graphs with respect to different

kinds of homomorphisms and study the relations between these classes. Although

homogeneous graphs are heavily analyzed, little has been done for homomorphism

homogeneous graphs. Cameron and Nesetril posed two open questions when they

first defined these graphs. We answer both questions and also attempt to

classify the homomorphism homogeneous graphs. This, we believe, opens up future

possibilities for more analysis of these structures.

In the thesis we also treat the category of graphs with loop allowed and

further extend the idea of homogeneity by expanding the list of homomorphisms

that are taken into consideration in the definitions.

In this thesis, the following spelling variants clustering problem is

considered: Given a list of distinct words, called lexicon, compute (possibly

overlapping) clusters of words which are spelling variants of each other. We

are looking for algorithms that are both efficient and accurate. Accuracy is

measured with respect to human judgment, e.g., a cluster is 100 accurate if it

contains all true spelling variants of the unique correct word it contains and

no other words, as judged by a human.

We have sifted the large body of literature on approximate string searching and

spelling correction problem for its applicability to our problem. We have

combined

various ideas from previous approaches to two new algorithms, with two

distinctly

different trade-offs between efficiency and accuracy. We have analyzed both

algorithms

and tested them experimentally on a variety of test collections, which were

chosen to exhibit the whole spectrum of spelling errors as they occur in

practice (human-made, OCR-induced, garbage). Our largest lexicon, containing

roughly 25 million words, can be processed in half an hour on a single machine.

The accuracies we obtain range from 88 - 95. We show that previous

approaches, if directly applied to our problem, are either significantly slower

or significantly less accurate or both.

Our spelling variants clustering problem arises naturally in the context of

search

engine spelling correction of the following kind: For a given query, return not

only

documents matching the query words exactly but also those matching their

spelling

variants. This is inverse to the well-known �did you mean: ...� web search

engine

feature, where the error tolerance is on the side of the query, and not on the

side of

the documents. We have integrated our algorithms with the CompleteSearch

engine, and show that this feature can be achieved without significant blowup

in either index size or query processing time.

We propose a new approach for reconstructing a 2-manifold from a point sample

in R³. Compared to previous algorithms, our approach is novel in that it throws

away geometry information early on in the reconstruction process and mainly

operates combinatorially on a graph structure.

Furthermore, it is very conservative in creating adjacencies between samples in

the vicinity of slivers, still we can prove that the resulting reconstruction

faithfully resembles the original 2-manifold. While the theoretical proof

requires an extremely high sampling density, our prototype implementation

of the approach produces surprisingly good results on typical sample sets.

An often stated problem in the state-of-the-art web search is its lack of user

adaptation, as all users are presented with the same search results for a given

query string. A user submitting an ambiguous query such as ”java” with a strong

interest in traveling might appreciate finding pages related to the

Indonesian island Java. However, if the same user searched for programming

tutorials a few minutes ago, the situation would be completely different, and

call for programming-related results. Furthermore suppose our sample user

searches for ”java hashmap”. Again imposing her interest into traveling might

this time have the contrary effect and even harm the result quality. Thus the

effectiveness of a personalization of web search shows high variance in

performance depending on the query, the user and the search context. To this

end, carefully choosing the right personalization strategy in a

contextsensitive manner is critical for an improvement of search results.

In this thesis, we present a general framework that dynamically adapts the

query-result ranking to the different information needs in order to improve the

search experience for the individual user. We distinguish three different

search goals, namely whether the user re-searches known information, delves

deeper into a topic she is generally interested in, or satisfies an ad-hoc

information need. We take an implicit relevance feedback approach that makes

use of the user’s web interactions, however, vary what constitutes the examples

of relevant and irrelevant information according to the user’s search mode. We

show that incorporating user behavior data can significantly improve the

ordering of top results in a real web search setting.

This thesis presents an exact and complete approach for visualization of

segments and points of real plane algebraic curves given in implicit form

$f(x,y) = 0$. A curve segment is a distinct curve branch consisting of regular

points

only. Visualization of algebraic curves having self-intersection and isolated

points constitutes the main challenge. Visualization of curve segments involves

even more

difficulties since here we are faced with a problem of discriminating

different curve branches, which can pass arbitrary close to each other.

Our approach is robust and efficient (as shown by our benchmarks), it

combines the advantages both of curve tracking and

space subdivision methods and is able to correctly rasterize segments of

arbitrary-degree algebraic curves using double, multi-precision or exact

rational arithmetic.

In this thesis we investigate the proof assistant Scunak in order to explore
the relationship between informal mathematical texts and their Scunak
counterparts. The investigation is based on a case study in which we have
formalized parts of an introductory book on real analysis. Based on this case
study, we illustrate significant aspects of the formal representation of
mathematics in Scunak. In particular, we present the formal proof of the
example lim(1/n) = 0.
Moreover, we present a comparison of Scunak with two well-known systems for
formalizing mathematics, the Mizar System and Isabelle/HOL. We have proved the
example lim(1/n) = 0 in Mizar and Isabelle/HOL as well and we relate certain
features of formal mathematics in Mizar and Isabelle/HOL to corresponding
features of the Scunak type theory in light of this example.

Step-indexed semantic models of types were proposed as an alternative to the

purely syntactic proofs of type safety using subject-reduction. This thesis

introduces

a step-indexed model for the functional object calculus, and uses it to

prove the soundness of an expressive type system with object types, subtyping,

recursive and bounded quantified types.

Variational methods currently belong to the most accurate techniques for the

computation of the displacement field between the frames of an image sequence.

Accuracy and time performance improvements of these methods are achieved every

year. Most of the effort is directed towards finding better data and smoothness

terms for the energy functional. Usually people are working mainly with

black-and-white image sequences.

In this thesis we will consider only colour images, as we believe that the

colour itself

carries much more information than the grey value and can help us for the

better estimation of the optic flow. So far most of the research done in optic

flow computation does not consider the presence of realistic illumination

changes in the image sequences.

One of the main goals of this thesis is to find new constancy assumptions for

the data term, which overcome the problems of severe illumination changes. So

far no research has been also done on combining variational methods with

statistical moments for the purpose of optic flow computation. The second goal

of this thesis is to investigate how and to what extend the optic flow methods

can benefit from the rotational invariant moments. We will introduce a new

variational methods framework that can combine all of the above mentioned new

assumptions into a successful optic flow computation technique.

With the advance of technology, the need for fast reaction to remote attacks

gains

in importance. A common practice to help detect malicious activity is to

install an

Intrusion Detection System. Intrusion detection systems are equipped with a set

of

signatures�descriptions of known intrusion attempts. They monitor traffic and

use

the signatures to detect intrusion attempts.

To date, attack signatures are still mostly derived manually. However, to

ensure the

security of computer systems and data, the speed and quality of signature

generation has to be improved. To help achieve the task, we propose an approach

for automatic extraction of attack signatures.

In contrast to the majority of the existing research in the area, we do not

confine

our approach to a particular type of attack. In particular, we are the first to

try signature extraction for attacks resulting from misconfigured security

policies. Whereas the majority of existing approaches rely on statistical

methods and require many attack instances in order to launch the signature

generation mechanism, we use experimentation and need only a single attack

instance.

For experimentation, we combine an existing framework for capture and replay of

system calls with an appropriate minimization algorithm. We propose three

minimization algorithms: Delta Debugging, Binary Debugging and Consecutive

Binary Debugging.

We evaluate the performance of the different algorithms and test our approach

with an example program. In all test cases, our application successfully

extracts the

attack signature. Our current results suggest that this is a promising approach

that

can help us defend better and faster against unknown attacks.

Information retrieval and feedback in {XML} are rather new fields for

researchers; natural questions arise, such as: how good are the feedback

algorithms in {XML IR}? Can they be evaluated with standard evaluation tools?

Even though some evaluation methods have been proposed in the literature, it is

still not clear yet which of them are applicable in the context of {XML IR},

and which metrics they can be combined with to assess the quality of {XML}

retrieval algorithms that use feedback.

We propose a solution for fairly evaluating the performance of the {XML} search

engines that use feedback for improving the query results. Compared

to previous approaches, we aim at removing the effect of the results for which

the system has knowledge about their the relevance, and at measuring the

improvement on unseen relevant elements.

We implemented our proposed evaluation methodologies by extending a standard

evaluation tool with a module capable of assessing feedback algorithms for a

specific set of metrics. We performed multiple tests on runs from both {INEX}

2005 and {INEX} 2006, covering two different {XML} document collections.

The performance of the assessed feedback algorithms did not reach the

theoretical optimal values either for the proposed evaluation methodologies, or

for the used metrics. The analysis of the results shows that, although the six

evaluation techniques provide good improvement figures, none of them can be

declared the absolute winner. Despite the lack of a definitive

conclusion, our findings provide a better understanding on the quality of

feedback algorithms.

Autonomous, graphically embodied agents are a versatile platform for

information presentation and user interaction. This thesis presents ERIC, a

homogeneous agent framework that can be configured to provide real-time running

commentary on a dynamic environment of many and frequent events. We have

focused on knowledge reasoning with a world model, generating and expressing

affect, and generating coherent natural language, synchronised with nonverbal

modalities. The graphical and TTS output of the agent is provided by commercial

systems.

ERIC is currently implemented to commentate a simulated horse race and a

multiplayer tank combat game. With minimal modification the system is

configurable to provide commentary in any continuous dynamically changing

environment; for example, it could commentate sports matches and computer

games, or play the role of "tourist guide" during a self-guided tour of a city.

An elaborate world model is deduced from limited input by an expert system

implemented as rules in Jess. Natural language is generated using

template-based NLG.

Discourse coherence is maintained by requiring semantic relations between the

forwardlooking and backward-looking centers of successive utterances. The agent

uses a set of causal and belief relations to assign appraisals of

emotion-eliciting conditions to facts in the world model based on goals and

desires. These appraisals are used to generate an affective state according to

the OCC cognitive model of emotions; the agent�s affect is expressed via his

lexical choice, gestures and facial expressions.

ERIC was designed to be domain-independent, homogeneous, behaviourally complex,

reactive and affective. Domain-indepence was evaluated by comparing the effort

required to implement the ERIC system with the effort required to re-implement

the framework for another domain. Complexity, reactivity and affectivity were

assessed by independent experts, whose reviews are presented.

Database systems often have to deal with incomplete information as the world

they model is not always complete. This is a frequent case in data integration

applications, scientific databases, or in scenarios where information is

manually entered and constains errors or ambiguity.

In the las couple of decades different formalisms have been proposed for

representing incomplete information. These include, among other, the so called

realtions with or-sets, tables with variables (v-tables) and conditional tables

(c-tables).

However, none of the current approaches for representing incomple information

has satisfied the requirements for a powerful and effcient data management

system, which is the reason why none has found application in practice. All

models generally suffer from at least one of two weaknesses. Either they are

not strong enough for representing results of simple queries, as is the case

for v-tables and realtions with or-sets, or the handling and processing of the

data, e.g. for query evaluation, is intractable (as is the case for c-tables).

In this thesis, e present a decomposition-based approach to addressing the

problem of incompletely specified databases. we introduce world-set

decompositions (WSDs), a space-efficient formalism for repreenting any finite

set of possible worlds over relational algebra queries on WSDs. For each

relational algebra operation we present an algorithm operting on WSDs.

We also address the problem of data cleaning in the context of world set

decompositions. We present a modified version of the existing Chase algorithm,

which we use to remove inconsistent worlds in an incompletely specified

database.

We evaluate our techniques in a large census data scenario with data

originating from the 1990 USA census and we show that data processing on WSDs

is both scalable and efficient.

For the effective prevention and elemination of defects and failures in a

software system, it is important to know which parts of the software are mor

likely to contain errors, and therefore, can be considered as "risky". To

increase reliability and quality, more effort should be spent in risky

components during design, implementation, and testing.

Examining the version archive and the code of a large open-source project, we

have investigated the relation between the risk of components as measured by

post-release failures, and different code structures; such as method calls,

variables, exception handling expressions and inheritnace statements. We have

analyzed the different types of usage relations between components, and their

affects on the failures. We utilized three commonly used statistical techniques

to build failure prediction models. As a realistic opponent to our models, we

introduced a "simple prediction model" which makes use of the riskiness

information from the available components, rather than making random guesses.

While the results from the classification experiments supported the use of code

structures to predict failur-proneness, our regression analyses showed that the

design time decisions also effected component riskiness. Our models were able

to make precise predictions, with even only the knowledge of the inheritnace

relations. since inheritance relations are defined aerliest at design time;

based on the results of this study, we can say that it may be possible to

initialize preventive actions against failures even early in the design phase

of a project.

Five years ago, the human genome sequence was published, an important milestone

towards understanding human biology.

However, basic cell processes cannot be explained by the genome sequence alone.

Instead, further layers of control such

as the epigenome will be important for significant advances towards better

understanding of normal and disease-related

phenotypes.

A new research field in computational biology is currently emerging that is

concerned with the analysis of functional

information beyond the human genome sequence. Our goal is to provide biologists

with means to navigate the large

amounts of epigenetic data and with tools to screen these data for biologically

interesting associations. We developed

a statistical learning methodology that facilitates mapping of epigenetic data

against the human genome, identifies

areas of over- and underrepresentation, and finds significant correlations with

DNA-related attributes. We implemented

this methodology in a software toolkit called EpiGRAPHregression.

EpiGRAPHregression is a prototype of a genome analysis tool that enables the

user to analyze

relationships between many attributes, and it provides a quick test whether a

newly analyzed attribute can be

efficiently predicted from already known attributes. Thereby,

EpiGRAPHregression may

significantly speed up the analysis of new types of genomic and epigenomic

data.

We provide an approximation algorithm for the Maximum Weight

Planar Subgraph problem, the NP-hard problem of finding a heaviest planar

subgraph in an edge-weighted graph G. In the general case

our algorithm has performance ratio at least 1/3+1/72 matching the

best algorithm known so far, though in several special cases we prove

stronger results. In particular, we obtain performance ratio 2/3 (in-

stead of 7/12) for the NP-hard Maximum Weight Outerplanar Sub-

graph problem meeting the performance ratio of the best algorithm

for the unweighted case. When the maximum weight planar subgraph

is one of several special types of Hamiltonian graphs, we show performance

ratios at least 2/5 and 4/9 (instead of 1/3 + 1/72), and 1/2

(instead of 4/9) for the unweighted case.

In cancer research, prediction of time to death or relapse is important for a

meaningful tumor classification and selecting

appropriate therapies. The accumulation of genetic alterations during tumor

progression can be used for the assessment of the genetic

status of the tumor. ArrayCGH technology is used to measure genomic

amplifications and deletions, with a high resolution that allows the

detection of down to single genes copy number changes.

\\\\We propose an automated method for analysis of cancer mutations

accumulation based on statistical analysis of arrayCGH data. The

method consists of the four steps: arrayCGH smoothing, aberrations

detection, consensus analysis and oncogenetic tree models

estimation. For the second and third steps, we propose new

algorithmic solutions. First, we use the adaptive weights

smoothing-based algorithm GLAD for identifying regions of constant

copy number. Then, in order to select regions of gain and loss, we

fit robust normals to the smoothed Log$_2$Ratios of each CGH array

and choose appropriate significance cutoffs. The consensus analysis

step consists of an automated selection of recurrent aberrant

regions when multiple CGH experiments on the same tumor type are

available. We propose to associate $p$-values to each measured

genomic position and to select the regions where the $p$-value is

sufficiently small.

\\\\The aberrant regions computed by our method can be further used to estimate

evolutionary trees, which model the dependencies

between genetic mutations and can help to predict tumor progression

stages and survival times.

\\\\We applied our method to two arrayCGH data sets obtained from prostate

cancer and glioblastoma patients, respectively.

The results confirm previous knowledge on the genetic mutations

specific to these types of cancer, but also bring out new regions,

often reducing to single genes, due to the high resolution of

arrayCGH measurements. An oncogenetic tree mixture model fitted to

the Prostate Cancer data set shows two distinct evolutionary

patterns discriminating between two different cell lines. Moreover,

when used as clustering features, the genetic mutations our

algorithm outputs separate well arrays representing 4 different cell

lines, proving that we extract meaningful information. }

This thesis studies the problem of determining the satisfiability of a Boolean
combination of binary difference constraints of the form
x-y <= c where x and y are numeric variables and c is a constant. In
particular, we present an incremental and model-based interpreter for the
theory of difference constraints in the context of a generic Boolean
satisfiability checking procedure capable of incorporating interpreters for
arbitrary theories. We show how to use the model based approach to efficiently
make inferences with the option of complete inference.

For many application such as mathematical assistant systems, an effective

communication between the system and its users is critical for the acceptance

of a system. Explaining the computer-supported proofs in natural language can

enhance the understanding of the users. We define a function that encodes the

proofs generated from the computer-supported theorem proving system MEGA into

TWEGA, which is the input language of the proof presentation system P.rex. This

encoding enables the natural language explanation of MEGA proofs in P.rex

A triangulation of a finite set S of points in R2 is a maximal set of line

segments with disjoint interiors whose end points are in S. A set of points in

the plane can have many triangulations and it is known that a set of n points

always has more than (2.33n)[7] and fewer than 59n-(log(n)) [4]

triangulation. However, these bounds are not tight. Also, counting the

number of triangulation of a given a set of points efficiently remains an open

problem. The fastest method so far is based on the so called t-path method [5]

and it was the first algorithm having a running time sublinear on the number of

triangulations counted. In this thesis, we consider a slightly different

approach to counting the number of triangulations. Although we are unable to

prove any non-trivial result about our algorithm yet, empirical results show

that the running time of our algorithm for a set of n points is o(nlog2nT(n))

where T(n) is the number of triangulations counted, and in practice it performs

much better than the earlier algorithm.

T-cell recognition is a critical step in regulating immune response. Activation

of Cytotoxic T-cell requires the MHC class I molecules in complex with specific

peptides and present them on the surface of the cell. Identification of

potential ligands to MHC is therefore important for understanding disease

pathogenesis and aiding vaccine design.

Despite years of effort in the field, reliable prediction of MHC ligands

remains a difficult task. It is reported that only one out of 100 to 200

potential binders actually binds. Methods based on sequence data alone are fast

but fail to capture all binding patterns, while the structure based methods are

more promising but far too slow for large-scale screening of protein sequences.

In this work, we propose a new method to the prediction problem. It is based on

the assumption that peptide binding is an aggregrate effect of contributions

from independent binding of residues. Compatibility of each amino acid in the

MHC binding pockets is examined thoroughly by molecular dynamics simulation.

Values of energy terms important for binding are collected from the generated

ensembles, and are used to produce the allele-specific scoring matrix. Each

entry in this matrix represents the favorableness in terms of a particular

"feature" of an amino acid in a binding position. Prediction models based on

machine learning techniques are then trained to discriminate binders from

non-binders.

Our method is compared to two other sequence-based methods using HLA-A*0201

9-mer sequences. Three publicly available data sets are used: the MHCPEP,

SYFPEITHI data sets, and the HXB2 genome. In overall, our method successfully

improves the prediction accuracy with higher specificity. Its robustness to

different sizes and ratios of training data proves its ability to provide

reliable prediction by less dependency on the sequence data. The method also

shows better generalizability in cross-allele predictions. For predicting

peptide bound conformations, our preliminary approach based on energy

minimization gives the satisfactory result of a backbone RMSD at 1.7 to 1.88 A

as compared to the crystal structures.

As a software system evolves, programmers make changes which sometimes lead to

problems. The risk of later problems significantly depends on the location of

the change. Which are the locations where changes impose the greatest risk?

We introduce a set of automated techniques that relate a version history

archive (such as CVS) with a bus database (such as BUGZILLA) to detect those

locations where changes have been risky in the past. Our experiments show that

simple measures have low accuracy in locating files that are most risky to

change

A fundamental issue in statistics, pattern recognition, and machine learning is

that of classification. In a traditional classification problem, we wish to

assign one of k labels (or classes) to each of n objects (or documents), in a

way that is consistent with some observed data available about that problem.

For achieving better classification results, we try to capture the information

derived by pairwise realtionships between objects, in particular hyperlinks

between web documents. the usage of hyperlinks poses new problems not addressed

in the extensive text classification literature. Links contain high quality

seantic clues that a purely text-based classifier can not take advantage of.

However, exploiting link inoframtion is non-trivial because it is noisy and a

naive use of terms in the link neghborhood of a document can degrade accuracy.

The problem becomes even harder when only a very small fraction of document

labels ar known to the classifier and can be used for training, as it is the

case in a real classification scenario. Our work is based on an algorithm

proposed by Soumen Chakrabarti and uses the theory of Markov Random Fields to

derive a relaxation labelling technique for the class assignment problem. We

show that the extra information contaned in the hyperlinks between the

documents can be explited to achieve significant improvement in the performance

of classification. We implemente our algorithm in Java and ran our experiments

on to sets of data obtained from the DBLP and IMDB databases. We oberved up to

5.5 improvement in the accuracy of the classification and up the 10 higher

recall and precision resultls.

Although Information Extraction field has been in the market since almost last

two decades, it is still considered to be in its initial stage. There are at

present many algorithms that are used for Information Extraction task, and they

also have a good success rate, but there are no benchemarks or standard data on

which they can be compared among themselves. Most of the algorithms work well

in semi-structured data but they seem to fail when dealing with free text.

Other algorithms fail when different types of data is required to extract from

the same doument. One way, is to some how try to compare them all and then try

to improve and create algorithms that are domain independent and work both

efficiently and effectively. For this, we introduce an idea of formalizing

Information Extractio algorithms and then to find out where can we improve them

or what parts are still needed to improve the over all performance. We have in

the end, described what we got by formalizing the algorithms and what can we

achieve after formalinzing further algorithms.

Critical points of vector fields are important topological features, which are

characterized by the number and order of areas of different flow behavior

around it. We present an approach to detect the different sectors around

general critical points of 3D vector fields. This approach is based on a

piecewise linear approximation of the vector fields around the critical points.

We showed examples how this approach can also treat critical points of a higher

order, and we discussed the limitation of the approach as well.

Flows over time (dymanic flows) generalize standard network flows by

introducing a new element- time. They naturally model problems where travel and

transmission are not instantaneous.

I this work we consider two dynamic flows problems: The Quickest multicommodity

Dynamic Flow problem with Bounded Cost (QMDFP) ant The Maximal Multicommodity

dynamic flow problem (MMDFP). Both problems are known to be NP-hard. In the

first part we propose two methods of improving the result obtained by the

efficient two-approximation algorithm proposed by Lisa Fleischer and Martin

Skutella for solving the QMDFP. The Approximation algorithm constructs the

temporally repeated flow using so called "static average flow". In the first

method we prove that the value of the static average flow can be increased by a

factor, that depends on the length of th shortest path form a source to a sink

in the underlying network. Increasing the value of the static average flow

allows us to save time on sending the necessary amount of flow (the given

demands) from sources to sinks. The cost of the resulting temporally repeated

flow remains unchanged. In the second method we porpose an algorithm that

reconstructs the static average flow in the way that the length of the longest

path used by the flow becomes shorter. This allows us to wait for a shorter

period of time until the last sent unit of flow reaches its sink. The drawback

of the reconstructing of the flow is its increase in cost. But we give a proof

ot the fact that the cost increases at most by a factor of two.

In the second part of the thesis we deal with MMDFP. We give an instance of the

network that demonstrates that the optimal solution is not always a temporally

repeated flow. But we give an easy proof of the fact that the difference

between the optimal solution and the Maximal Multicommodity Temporally Repeated

Flow is bounded by a constant that depends on the network and not on the given

time horizon. This fact allows to approximate the optimal Maximal

Multicommodity Dynamic Flow with the Maximal Muticommodity Temporally Repeated

Flow for large enough time horizons.

All global illumination algorithms are based on rendering equation. The

rendering equation is solved in different ways in every algorithm. Most of

algorithms solve the equation by using Monte Carlo method. In this process many

samples are produced. These samples have different contribution to generated

image. If one hopes to get acceptable result with fewer samples, important

samples, which have more contribution for the nal image, must be considered in

the rst place. For example, in ordinary Light Tracing, millions of photons

have to be traced in order to obtain the distribution of illumination in the

whole scene. Actually only a part of scene can be observed most of the time,

and just photons hitting visible surfaces will contribute to the generated

image. If only a small part of entire scene is visible, we will spend most of

the time tracing and storing unimportant photons that have no any contribution

to the nal image. Even considering only visible photons, one can see that

their contribution to image is very different. Surfaces that are located closer

to viewpoint have larger image plane projected area and thus require more

photons to achieve the same noise level as surfaces located further away.

Orientation of surface in respect to view direction also affects viewdependent

photons importance. Depending on the application and used Monte Carlo algorithm

one can come up with many other different criteria to compute this importance,

which may dramatically affect the quality of produced images and computation

speed. Algorithm presented in the thesis takes only useful (visible) photons

into account, concentrating computation only on the surfaces visible by

currently active camera, balancing the distribution of photons on the image

plane, greatly improving the image quality. Using this concept, we can get

better result with fewer photons. In this way it is possible to save not only

rendering time, but also storage space because less photons need to be stored.

This idea also can be applied in other algorithms where millions of samples

have to be generated. Once the difference among these samples is found out, we

can pay more attention to the important samples that have more contribution to

the result image, while ignoring less important ones, thus using fewer samples

to get better result.

Conclusions:

In this master thesis, we have started with an informal security protocol

representation. We have demonstrated the translation of protocols into Horn

clauses by giving the well-known Otway Rees Protocol as an example. We also

defined and formalized semantics of the protocol for all participant.

For the work presented in this thesis we have assumed perfect encryption. We

also assume that the protocol is executed in the presence of the attacker that

can listen, compute new messages from the messages it has already received, and

send any message it can build.

We firmalized the abilities of attacker and we defined the view of attacker to

the message. By looking to the view of the messages, if participant can

distiguish the views then it will stop the protocol run, if participant cannot

distinguish the messages from each other then it will reply to the previous

message.

The related work has been done in the reference [5] for CAPSL ( Common

Authentication Protocol Specification Language) wich is a high-level language

for applying formal methods to the security analysis of cryptographic

protocols. Protocol is specified in a form that could be used as the input

format for any formal analysis.

We can prove termination of C programs by computing 'strong enough' transition

invariants by abastract interpretation. In this thesis, we describe basic

ingredients for an implementation of this computation. Namely, we show how to

extract models form C programs (using GCA tool [7]) and how to construct an

abstract domain of transition predicates. Furthermore, we propose a method for

'compacting' a model that improves the running time of the transtion invariant

generation algorithm.

We implement these ingredients and the proposed optimization, and practically

evaluate their effectiveness

We examine the number of triangulations that any set of n points in the plane

must have, and prove that (i) any set of n points has at least 0.00037*2.2n

triangulations, (ii) any set with three extreme points and n interior points

has at least 0.112*2.569n triangulation, and (iii) any set with n interior

points has at least 0.238 * 2.38n triangulation. The best previously known

lower bound for the number of triangulations for n points in the plane is

0.0822 * 2.0129n. We also give a method of automatically extending known

bounds for small point sets to general lower bounds.

This thesis describes a way of modeling viscoelasticity in deformable solids

for interactive haptic and display purposes. The model is based on elastostatic

deformation characterized by a discrete Green's function matrix, which is

extended using a viscoelastic add-on. The underlying idea is to replace the

linear, time-independent relationships between the matrix entries, force, and

displacement with non-linear, time-dependent relationships. A general framework

is given, in which different viscoelastic models can be devised. One such model

based on physical measurements is discussed in detail. Finally, the details and

results of a system that implements this model are described.

Summary

My diploma thesis is a part of the project "Verification of the L4 operating

system kernel". The aim of this project ist to formally verify the L4 kernel in

order to guarantee its correctness. In my thesis I have documented the

implementation of the IPC mechanism in the L4 kernel. I proved the correctness

of the message passing protocol of the IPC mechanism. This was done in three

steps: At first I have created the formal specification of that protocol. After

that I built a model of the IPC mechanism in PVS and at last I proved that the

created model fulfils the specification. The model which is built in this work

is not meant to be a precise representation of the original protocol. The proof

of such a model is not the same as proofs for the original C code, but they may

allow to write a correct source code. Therefore for software verification we

need some tool that we can work with C-code or any programming language in

order to verify its correctness.

Abstraction plays an important role for verification of computer

programs. We want to construct the right abstraction automatically.

There is a promising approach to do it, called {\it predicate abstraction}.

An insufficiently precise abstraction can be {\it automatically refined}.

There is an automated model checking method described in

[Ball, Podelski, Rajamani TACAS02] which combines both techniques,

e.g., predicate abstraction and abstraction refinement. The quality of

the method is expressed by a completeness property relative to a

powerful but unrealistic oracle-guided algorithm.

\par

In this work we want to generalize the results from

[Ball,Podelski,Rajamani TACAS02] and introduce new abstraction

functions with different precision. We implement the new

abstraction functions in a model checker and practically evaluate

their effectiveness in verifying various computer programs.

Knowledge extraction from text is a key task in natural language processing, which involves many sub-tasks, such as taxonomy induction, named entity recognition and typing, relation extraction, knowledge canonicalization and so on. By constructing structured knowledge from natural language text, knowledge extraction becomes a key asset for search engines, question answering and other downstream applications. However, current knowledge extraction methods mostly focus on prominent real-world entities with Wikipedia and mainstream news articles as sources. The constructed knowledge bases, therefore, lack information about long-tail domains, with fiction and fantasy as archetypes. Fiction and fantasy are core parts of our human culture, spanning from literature to movies, TV series, comics and video games. With thousands of fictional universes which have been created, knowledge from fictional domains are subject of search-engine queries - by fans as well as cultural analysts. Unlike the real-world domain, knowledge extraction on such specific domains like fiction and fantasy has to tackle several key challenges: - Training data: Sources for fictional domains mostly come from books and fan-built content, which is sparse and noisy, and contains difficult structures of texts, such as dialogues and quotes. Training data for key tasks such as taxonomy induction, named entity typing or relation extraction are also not available. - Domain characteristics and diversity: Fictional universes can be highly sophisticated, containing entities, social structures and sometimes languages that are completely different from the real world. State-of-the-art methods for knowledge extraction make assumptions on entity-class, subclass and entity-entity relations that are often invalid for fictional domains. With different genres of fictional domains, another requirement is to transfer models across domains. - Long fictional texts: While state-of-the-art models have limitations on the input sequence length, it is essential to develop methods that are able to deal with very long texts (e.g. entire books), to capture multiple contexts and leverage widely spread cues. This dissertation addresses the above challenges, by developing new methodologies that advance the state of the art on knowledge extraction in fictional domains. - The first contribution is a method, called TiFi, for constructing type systems (taxonomy induction) for fictional domains. By tapping noisy fan-built content from online communities such as Wikia, TiFi induces taxonomies through three main steps: category cleaning, edge cleaning and top-level construction. Exploiting a variety of features from the original input, TiFi is able to construct taxonomies for a diverse range of fictional domains with high precision. - The second contribution is a comprehensive approach, called ENTYFI, for named entity recognition and typing in long fictional texts. Built on 205 automatically induced high-quality type systems for popular fictional domains, ENTYFI exploits the overlap and reuse of these fictional domains on unseen texts. By combining different typing modules with a consolidation stage, ENTYFI is able to do fine-grained entity typing in long fictional texts with high precision and recall. - The third contribution is an end-to-end system, called KnowFi, for extracting relations between entities in very long texts such as entire books. KnowFi leverages background knowledge from 142 popular fictional domains to identify interesting relations and to collect distant training samples. KnowFi devises a similarity-based ranking technique to reduce false positives in training samples and to select potential text passages that contain seed pairs of entities. By training a hierarchical neural network for all relations, KnowFi is able to infer relations between entity pairs across long fictional texts, and achieves gains over the best prior methods for relation extraction.

In this thesis we explore pattern mining and deep learning. Often seen as orthogonal, we show that these fields complement each other and propose to combine them to gain from each other’s strengths. We, first, show how to efficiently discover succinct and non-redundant sets of patterns that provide insight into data beyond conjunctive statements. We leverage the interpretability of such patterns to unveil how and which information flows through neural networks, as well as what characterizes their decisions. Conversely, we show how to combine continuous optimization with pattern discovery, proposing a neural network that directly encodes discrete patterns, which allows us to apply pattern mining at a scale orders of magnitude larger than previously possible. Large neural networks are, however, exceedingly expensive to train for which ‘lottery tickets’ – small, well-trainable sub-networks in randomly initialized neural networks – offer a remedy. We identify theoretical limitations of strong tickets and overcome them by equipping these tickets with the property of universal approximation. To analyze whether limitations in ticket sparsity are algorithmic or fundamental, we propose a framework to plant and hide lottery tickets. With novel ticket benchmarks we then conclude that the limitation is likely algorithmic, encouraging further developments for which our framework offers means to measure progress.

Social media communities like Reddit and Twitter allow users to express their views on
topics of their interest, and to engage with other users who may share or oppose these views.
This can lead to productive discussions towards a consensus, or to contended debates, where
disagreements frequently arise.
Prior work on such settings has primarily focused on identifying notable instances of antisocial
behavior such as hate-speech and “trolling”, which represent possible threats to the health of
a community. These, however, are exceptionally severe phenomena, and do not encompass
controversies stemming from user debates, differences of opinions, and off-topic content, all
of which can naturally come up in a discussion without going so far as to compromise its
development.
This dissertation proposes a framework for the systematic analysis of social media discussions
that take place in the presence of controversial themes, disagreements, and mixed opinions from
participating users. For this, we develop a feature-based model to describe key elements of a
discussion, such as its salient topics, the level of activity from users, the sentiments it expresses,
and the user feedback it receives.
Initially, we build our feature model to characterize adversarial discussions surrounding
political campaigns on Twitter, with a focus on the factual and sentimental nature of their
topics and the role played by different users involved. We then extend our approach to Reddit
discussions, leveraging community feedback signals to define a new notion of controversy
and to highlight conversational archetypes that arise from frequent and interesting interaction
patterns. We use our feature model to build logistic regression classifiers that can predict future
instances of controversy in Reddit communities centered on politics, world news, sports, and
personal relationships. Finally, our model also provides the basis for a comparison of different
communities in the health domain, where topics and activity vary considerably despite their
shared overall focus. In each of these cases, our framework provides insight into how user
behavior can shape a community’s individual definition of controversy and its overall identity.

As machine learning (ML) is increasingly used for decision making in scenarios that impact humans, there is a growing awareness of its potential for unfairness. A large body of recent work has focused on proposing formal notions of fairness in ML, as well as approaches to mitigate unfairness. However, there is a growing disconnect between the ML fairness literature and the needs to operationalize fairness in practice. This thesis addresses the need for responsible ML by developing new models and methods to address challenges in operationalizing fairness in practice. Specifically, it makes the following contributions. First, we tackle a key assumption in the group fairness literature that sensitive demographic attributes such as race and gender are known upfront, and can be readily used in model training to mitigate unfairness. In practice, factors like privacy and regulation often prohibit ML models from collecting or using protected attributes in decision making. To address this challenge we introduce the novel notion of computationally-identifiable errors and propose Adversarially Reweighted Learning (ARL), an optimization method that seeks to improve the worst-case performance over unobserved groups, without requiring access to the protected attributes in the dataset. Second, we argue that while group fairness notions are a desirable fairness criterion, they are fundamentally limited as they reduce fairness to an average statistic over pre-identified protected groups. In practice, automated decisions are made at an individual level, and can adversely impact individual people irrespective of the group statistic. We advance the paradigm of individual fairness by proposing iFair (individually fair representations), an optimization approach for learning a low dimensional latent representation of the data with two goals: to encode the data as well as possible, while removing any information about protected attributes in the transformed representation. Third, we advance the individual fairness paradigm, which requires that similar individuals receive similar outcomes. However, similarity metrics computed over observed feature space can be brittle, and inherently limited in their ability to accurately capture similarity between individuals. To address this, we introduce a novel notion of fairness graphs, wherein pairs of individuals can be identified as deemed similar with respect to the ML objective. We cast the problem of individual fairness into graph embedding, and propose PFR (pairwise fair representations), a method to learn a unified pairwise fair representation of the data. Fourth, we tackle the challenge that production data after model deployment is constantly evolving. As a consequence, in spite of the best efforts in training a fair model, ML systems can be prone to failure risks due to a variety of unforeseen reasons. To ensure responsible model deployment, potential failure risks need to be predicted, and mitigation actions need to be devised, for example, deferring to a human expert when uncertain or collecting additional data to address model’s blind-spots. We propose Risk Advisor, a model-agnostic meta-learner to predict potential failure risks and to give guidance on the sources of uncertainty inducing the risks, by leveraging information theoretic notions of aleatoric and epistemic uncertainty. This dissertation brings ML fairness closer to real-world applications by developing methods that address key practical challenges. Extensive experiments on a variety of real-world and synthetic datasets show that our proposed methods are viable in practice.

Deep learning is becoming increasingly relevant for many high-stakes applications such as autonomous driving or medical diagnosis where wrong decisions can have massive impact on human lives. Unfortunately, deep neural networks are typically assessed solely based on generalization, e.g., accuracy on a fixed test set. However, this is clearly insufficient for safe deployment as potential malicious actors and distribution shifts or the effects of quantization and unreliable hardware are disregarded. Thus, recent work additionally evaluates performance on potentially manipulated or corrupted inputs as well as after quantization and deployment on specialized hardware. In such settings, it is also important to obtain reasonable estimates of the model's confidence alongside its predictions. This thesis studies robustness and uncertainty estimation in deep learning along three main directions: First, we consider so-called adversarial examples, slightly perturbed inputs causing severe drops in accuracy. Second, we study weight perturbations, focusing particularly on bit errors in quantized weights. This is relevant for deploying models on special-purpose hardware for efficient inference, so-called accelerators. Finally, we address uncertainty estimation to improve robustness and provide meaningful statistical performance guarantees for safe deployment. In detail, we study the existence of adversarial examples with respect to the underlying data manifold. In this context, we also investigate adversarial training which improves robustness by augmenting training with adversarial examples at the cost of reduced accuracy. We show that regular adversarial examples leave the data manifold in an almost orthogonal direction. While we find no inherent trade-off between robustness and accuracy, this contributes to a higher sample complexity as well as severe overfitting of adversarial training. Using a novel measure of flatness in the robust loss landscape with respect to weight changes, we also show that robust overfitting is caused by converging to particularly sharp minima. In fact, we find a clear correlation between flatness and good robust generalization. Further, we study random and adversarial bit errors in quantized weights. In accelerators, random bit errors occur in the memory when reducing voltage with the goal of improving energy-efficiency. Here, we consider a robust quantization scheme, use weight clipping as regularization and perform random bit error training to improve bit error robustness, allowing considerable energy savings without requiring hardware changes. In contrast, adversarial bit errors are maliciously introduced through hardware- or software-based attacks on the memory, with severe consequences on performance. We propose a novel adversarial bit error attack to study this threat and use adversarial bit error training to improve robustness and thereby also the accelerator's security. Finally, we view robustness in the context of uncertainty estimation. By encouraging low-confidence predictions on adversarial examples, our confidence-calibrated adversarial training successfully rejects adversarial, corrupted as well as out-of-distribution examples at test time. Thereby, we are also able to improve the robustness-accuracy trade-off compared to regular adversarial training. However, even robust models do not provide any guarantee for safe deployment. To address this problem, conformal prediction allows the model to predict confidence sets with user-specified guarantee of including the true label. Unfortunately, as conformal prediction is usually applied after training, the model is trained without taking this calibration step into account. To address this limitation, we propose conformal training which allows training conformal predictors end-to-end with the underlying model. This not only improves the obtained uncertainty estimates but also enables optimizing application-specific objectives without losing the provided guarantee. Besides our work on robustness or uncertainty, we also address the problem of 3D shape completion of partially observed point clouds. Specifically, we consider an autonomous driving or robotics setting where vehicles are commonly equipped with LiDAR or depth sensors and obtaining a complete 3D representation of the environment is crucial. However, ground truth shapes that are essential for applying deep learning techniques are extremely difficult to obtain. Thus, we propose a weakly-supervised approach that can be trained on the incomplete point clouds while offering efficient inference. In summary, this thesis contributes to our understanding of robustness against both input and weight perturbations. To this end, we also develop methods to improve robustness alongside uncertainty estimation for safe deployment of deep learning methods in high-stakes applications. In the particular context of autonomous driving, we also address 3D shape completion of sparse point clouds.

Personal knowledge is a versatile resource that is valuable for a wide range of downstream applications. Background facts about users can allow chatbot assistants to produce more topical and empathic replies. In the context of recommendation and retrieval models, personal facts can be used to customize the ranking results for individual users. A Personal Knowledge Base, populated with personal facts, such as demographic information, interests and interpersonal relationships, is a unique endpoint for storing and querying personal knowledge. Such knowledge bases are easily interpretable and can provide users with full control over their own personal knowledge, including revising stored facts and managing access by downstream services for personalization purposes. To alleviate users from extensive manual effort to build such personal knowledge base, we can leverage automated extraction methods applied to the textual content of the users, such as dialogue transcripts or social media posts. Mainstream extraction methods specialize on well-structured data, such as biographical texts or encyclopedic articles, which are rare for most people. In turn, conversational data is abundant but challenging to process and requires specialized methods for extraction of personal facts. In this dissertation we address the acquisition of personal knowledge from conversational data. We propose several novel deep learning models for inferring speakers’ personal attributes: • Demographic attributes, age, gender, profession and family status, are inferred by HAMs - hierarchical neural classifiers with attention mechanism. Trained HAMs can be transferred between different types of conversational data and provide interpretable predictions. • Long-tailed personal attributes, hobby and profession, are predicted with CHARM - a zero-shot learning model, overcoming the lack of labeled training samples for rare attribute values. By linking conversational utterances to external sources, CHARM is able to predict attribute values which it never saw during training. • Interpersonal relationships are inferred with PRIDE - a hierarchical transformer-based model. To accurately predict fine-grained relationships, PRIDE leverages personal traits of the speakers and the style of conversational utterances. Experiments with various conversational texts, including Reddit discussions and movie scripts, demonstrate the viability of our methods and their superior performance compared to state-of-the-art baselines.

Knowledge Graphs (KGs) have applications in many domains such as Finance, Manufacturing, and Healthcare. While recent efforts have created large KGs, their content is far from complete and sometimes includes invalid statements. Therefore, it is crucial to refine the constructed KGs to enhance their coverage and accuracy via KG completion and KG validation. It is also vital to provide human-comprehensible explanations for such refinements, so that humans have trust in the KG quality. Enabling KG exploration, by search and browsing, is also essential for users to understand the KG value and limitations towards down-stream applications. However, the large size of KGs makes KG exploration very challenging. While the type taxonomy of KGs is a useful asset along these lines, it remains insufficient for deep exploration. In this dissertation we tackle the aforementioned challenges of KG refinement and KG exploration by combining logical reasoning over the KG with other techniques such as KG embedding models and text mining. Through such combination, we introduce methods that provide human-understandable output. Concretely, we introduce methods to tackle KG incompleteness by learning exception-aware rules over the existing KG. Learned rules are then used in inferring missing links in the KG accurately. Furthermore, we propose a framework for constructing human-comprehensible explanations for candidate facts from both KG and text. Extracted explanations are used to insure the validity of KG facts. Finally, to facilitate KG exploration, we introduce a method that combines KG embeddings with rule mining to compute informative entity clusters with explanations.

Our increasing reliance on complex algorithms for recommendations calls for models and methods for explainable, scrutable, and trustworthy AI. While explainability is required for understanding the relationships between model inputs and outputs, a scrutable system allows us to modify its behavior as desired. These properties help bridge the gap between our expectations and the algorithm’s behavior and accordingly boost our trust in AI. Aiming to cope with information overload, recommender systems play a crucial role in filtering content (such as products, news, songs, and movies) and shaping a personalized experience for their users. Consequently, there has been a growing demand from the information consumers to receive proper explanations for their personalized recommendations. These explanations aim at helping users understand why certain items are recommended to them and how their previous inputs to the system relate to the generation of such recommendations. Besides, in the event of receiving undesirable content, explanations could possibly contain valuable information as to how the system’s behavior can be modified accordingly. In this thesis, we present our contributions towards explainability and scrutability of recommender systems: • We introduce a user-centric framework, FAIRY, for discovering and ranking post-hoc explanations for the social feeds generated by black-box platforms. These explanations reveal relationships between users’ profiles and their feed items and are extracted from the local interaction graphs of users. FAIRY employs a learning-to-rank (LTR) method to score candidate explanations based on their relevance and surprisal. • We propose a method, PRINCE, to facilitate provider-side explainability in graph-based recommender systems that use personalized PageRank at their core. PRINCE explanations are comprehensible for users, because they present subsets of the user’s prior actions responsible for the received recommendations. PRINCE operates in a counterfactual setup and builds on a polynomial-time algorithm for finding the smallest counterfactual explanations. • We propose a human-in-the-loop framework, ELIXIR, for enhancing scrutability and subsequently the recommendation models by leveraging user feedback on explanations. ELIXIR enables recommender systems to collect user feedback on pairs of recommendations and explanations. The feedback is incorporated into the model by imposing a soft constraint for learning user-specific item representations. We evaluate all proposed models and methods with real user studies and demonstrate their benefits at achieving explainability and scrutability in recommender systems.

Most of the images one finds in the media, such as on the Internet or in textbooks and magazines, contain humans as the main point of attention. Thus, there is an inherent necessity for industry, society, and private persons to be able to thoroughly analyze and synthesize the human-related content in these images. One aspect of this analysis and subject of this thesis is to infer the 3D pose and surface deformation, using only visual information, which is also known as human performance capture. Human performance capture enables the tracking of virtual characters from real-world observations, and this is key for visual effects, games, VR, and AR, to name just a few application areas. However, traditional capture methods usually rely on expensive multi-view (marker-based) systems that are prohibitively expensive for the vast majority of people, or they use depth sensors, which are still not as common as single color cameras. Recently, some approaches have attempted to solve the task by assuming only a single RGB image is given. Nonetheless, they can either not track the dense deforming geometry of the human, such as the clothing layers, or they are far from real time, which is indispensable for many applications. To overcome these shortcomings, this thesis proposes two monocular human performance capture methods, which for the first time allow the real-time capture of the dense deforming geometry as well as an unseen 3D accuracy for pose and surface deformations. At the technical core, this work introduces novel GPU-based and data-parallel optimization strategies in conjunction with other algorithmic design choices that are all geared towards real-time performance at high accuracy. Moreover, this thesis presents a new weakly supervised multiview training strategy combined with a fully differentiable character representation that shows superior 3D accuracy. However, there is more to human-related Computer Vision than only the analysis of people in images. It is equally important to synthesize new images of humans in unseen poses and also from camera viewpoints that have not been observed in the real world. Such tools are essential for the movie industry because they, for example, allow the synthesis of photo-realistic virtual worlds with real-looking humans or of contents that are too dangerous for actors to perform on set. But also video conferencing and telepresence applications can benefit from photo-real 3D characters, as they can enhance the immersive experience of these applications. Here, the traditional Computer Graphics pipeline for rendering photo-realistic images involves many tedious and time-consuming steps that require expert knowledge and are far from real time. Traditional rendering involves character rigging and skinning, the modeling of the surface appearance properties, and physically based ray tracing. Recent learning-based methods attempt to simplify the traditional rendering pipeline and instead learn the rendering function from data resulting in methods that are easier accessible to non-experts. However, most of them model the synthesis task entirely in image space such that 3D consistency cannot be achieved, and/or they fail to model motion- and view-dependent appearance effects. To this end, this thesis presents a method and ongoing work on character synthesis, which allow the synthesis of controllable photoreal characters that achieve motion- and view-dependent appearance effects as well as 3D consistency and which run in real time. This is technically achieved by a novel coarse-to-fine geometric character representation for efficient synthesis, which can be solely supervised on multi-view imagery. Furthermore, this work shows how such a geometric representation can be combined with an implicit surface representation to boost synthesis and geometric quality.

Graph data nowadays easily become so large that it is infeasible to study the underlying structures manually. Thus, computational methods are needed to uncover large-scale structural information. In this thesis, we present methods to understand and summarise large networks.
We propose the hyperbolic community model to describe groups of more densely connected nodes within networks using very intuitive parameters. The model accounts for a
frequent connectivity pattern in real data: a few community members are highly interconnected; most members mainly have ties to this core. Our model fits real data much better than previously-proposed models. Our corresponding random graph generator, HyGen, creates graphs with realistic intra-community structure.
Using the hyperbolic model, we conduct a large-scale study of the temporal evolution of communities on online question–answer sites. We observe that the user activity within a community is constant with respect to its size throughout its lifetime, and a small group of users is responsible for the majority of the social interactions.
We propose an approach for Boolean tensor clustering. This special tensor factorisation is restricted to binary data and assumes that one of the tensor directions has only non-overlapping factors. These assumptions – valid for many real-world data, in particular time-evolving networks – enable the use of bitwise operators and lift much of the computational complexity from the task.

Text and images are the two most common data modalities found on the Internet. Understanding the synergy between text and images, that is, seamlessly analyzing information from these modalities may be trivial for humans, but is challenging for software systems. In this dissertation we study problems where deciphering text-image synergy is crucial for finding solutions. We propose methods and ideas that establish semantic connections between text and images in multimodal contents, and empirically show their effectiveness in four interconnected problems: Image Retrieval, Image Tag Refinement, Image-Text Alignment, and Image Captioning. Our promising results and observations open up interesting scopes for future research involving text-image data understanding.Text and images are the two most common data modalities found on the Internet. Understanding the synergy between text and images, that is, seamlessly analyzing information from these modalities may be trivial for humans, but is challenging for software systems. In this dissertation we study problems where deciphering text-image synergy is crucial for finding solutions. We propose methods and ideas that establish semantic connections between text and images in multimodal contents, and empirically show their effectiveness in four interconnected problems: Image Retrieval, Image Tag Refinement, Image-Text Alignment, and Image Captioning. Our promising results and observations open up interesting scopes for future research involving text-image data understanding.

Abstract
Humans are at the centre of a significant amount of research in computer vision.
Endowing machines with the ability to perceive people from visual data is an immense
scientific challenge with a high degree of direct practical relevance. Success in automatic
perception can be measured at different levels of abstraction, and this will depend on
which intelligent behaviour we are trying to replicate: the ability to localise persons in
an image or in the environment, understanding how persons are moving at the skeleton
and at the surface level, interpreting their interactions with the environment including
with other people, and perhaps even anticipating future actions. In this thesis we tackle
different sub-problems of the broad research area referred to as "looking at people",
aiming to perceive humans in images at different levels of granularity.
We start with bounding box-level pedestrian detection: We present a retrospective
analysis of methods published in the decade preceding our work, identifying various
strands of research that have advanced the state of the art. With quantitative exper-
iments, we demonstrate the critical role of developing better feature representations
and having the right training distribution. We then contribute two methods based
on the insights derived from our analysis: one that combines the strongest aspects of
past detectors and another that focuses purely on learning representations. The latter
method outperforms more complicated approaches, especially those based on hand-
crafted features. We conclude our work on pedestrian detection with a forward-looking
analysis that maps out potential avenues for future research.
We then turn to pixel-level methods: Perceiving humans requires us to both separate
them precisely from the background and identify their surroundings. To this end, we
introduce Cityscapes, a large-scale dataset for street scene understanding. This has since
established itself as a go-to benchmark for segmentation and detection. We additionally
develop methods that relax the requirement for expensive pixel-level annotations, focusing
on the task of boundary detection, i.e. identifying the outlines of relevant objects and
surfaces. Next, we make the jump from pixels to 3D surfaces, from localising and
labelling to fine-grained spatial understanding. We contribute a method for recovering
3D human shape and pose, which marries the advantages of learning-based and model-
based approaches.
We conclude the thesis with a detailed discussion of benchmarking practices in
computer vision. Among other things, we argue that the design of future datasets
should be driven by the general goal of combinatorial robustness besides task-specific
considerations.

I develop a formal framework for propositional satifisfiability with the conflict-driven clause learning (CDCL) procedure using the Isabelle/HOL proof assistant. The framework offers a convenient way to prove metatheorems and experiment with variants, including the Davis-Putnam-Logemann-Loveland procedure. The most noteworthy aspects of my work are the inclusion of rules for forget and restart and the refinement approach. I use the formalization to develop three extensions: First, an incremental solving extension of CDCL. Second, I verify an optimizing CDCL (OCDCL): Given a cost function on literals, OCDCL derives an optimal model with minimum cost. Finally, I work on model covering. Thanks to the CDCL framework I can reuse, these extensions are easier to develop. Through a chain of refinements, I connect the abstract CDCL calculus first to a more concrete calculus, then to a SAT solver expressed in a simple functional programming language, and finally to a SAT solver in an imperative language, with total correctness guarantees. The imperative version relies on the two-watched-literal data structure and other optimizations found in modern solvers. I used the Isabelle Refinement Framework to automate the most tedious refinement steps. After that, I extend this work with further optimizations like blocking literals and the use of machine words as long as possible, before switching to unbounded integers to keep completeness.

Modern deep learning has enabled amazing developments of computer vision in recent years (Hinton and Salakhutdinov, 2006; Krizhevsky et al., 2012). As a fundamental task, semantic segmentation aims to predict class labels for each pixel of images, which empowers machines perception of the visual world. In spite of recent successes of fully convolutional networks (Long etal., 2015), several challenges remain to be addressed. In this thesis, we focus on this topic, under different kinds of input formats and various types of scenes. Specifically, our study contains two aspects: (1) Data-driven neural modules for improved performance. (2) Leverage of datasets w.r.t.training systems with higher performances and better data privacy guarantees. In the first part of this thesis, we improve semantic segmentation by designing new modules which are compatible with existing architectures. First, we develop a spatio-temporal data-driven pooling, which brings additional information of data (i.e. superpixels) into neural networks, benefiting the training of neural networks as well as the inference on novel data. We investigate our approach in RGB-D videos for segmenting indoor scenes, where depth provides complementary cues to colors and our model performs particularly well. Second, we design learnable dilated convolutions, which are the extension of standard dilated convolutions, whose dilation factors (Yu and Koltun, 2016) need to be carefully determined by hand to obtain decent performance. We present a method to learn dilation factors together with filter weights of convolutions to avoid a complicated search of dilation factors. We explore extensive studies on challenging street scenes, across various baselines with different complexity as well as several datasets at varying image resolutions. In the second part, we investigate how to utilize expensive training data. First, we start from the generative modelling and study the network architectures and the learning pipeline for generating multiple examples. We aim to improve the diversity of generated examples but also to preserve the comparable quality of the examples. Second, we develop a generative model for synthesizing features of a network. With a mixture of real images and synthetic features, we are able to train a segmentation model with better generalization capability. Our approach is evaluated on different scene parsing tasks to demonstrate the effectiveness of the proposed method. Finally, we study membership inference on the semantic segmentation task. We propose the first membership inference attack system against black-box semantic segmentation models, that tries to infer if a data pair is used as training data or not. From our observations, information on training data is indeed leaking. To mitigate the leakage, we leverage our synthetic features to perform prediction obfuscations, reducing the posterior distribution gaps between a training and a testing set. Consequently, our study provides not only an approach for detecting illegal use of data, but also the foundations for a safer use of semantic segmentation models.

Answering complex natural language questions with crisp answers is crucial towards satisfying the information needs of advanced users. With the rapid growth of knowledge bases (KBs) such as Yago and Freebase, this goal has become attainable by translating questions into formal queries like SPARQL queries. Such queries can then be evaluated over knowledge bases to retrieve crisp answers. To this end, three research issues arise: (i) how to develop methods that are robust to lexical and syntactic variations in questions and can handle complex questions, (ii) how to design and curate datasets to advance research in question answering, and (iii) how to efficiently identify named entities in questions. In this dissertation, we make the following five contributions in the areas of question answering (QA) and named entity recognition (NER). For issue (i), we make the following contributions: We present QUINT, an approach for answering natural language questions over knowledge bases using automatically learned templates. Templates are an important asset for QA over KBs, simplifying the semantic parsing of input questions and generating formal queries for interpretable answers. QUINT is capable of answering both simple and compositional questions. We introduce NEQA, a framework for continuous learning for QA over KBs. NEQA starts with a small seed of training examples in the form of question-answer pairs, and improves its performance over time. NEQA combines both syntax, through template-based answering, and semantics, via a semantic similarity function. %when templates fail to do so. Moreover, it adapts to the language used after deployment by periodically retraining its underlying models. For issues (i) and (ii), we present TEQUILA, a framework for answering complex questions with explicit and implicit temporal conditions over KBs. TEQUILA is built on a rule-based framework that detects and decomposes temporal questions into simpler sub-questions that can be answered by standard KB-QA systems. TEQUILA reconciles the results of sub-questions into final answers. TEQUILA is accompanied with a dataset called TempQuestions, which consists of 1,271 temporal questions with gold-standard answers over Freebase. This collection is derived by judiciously selecting time-related questions from existing QA datasets. For issue (ii), we publish ComQA, a large-scale manually-curated dataset for QA. ComQA contains questions that represent real information needs and exhibit a wide range of difficulties such as the need for temporal reasoning, comparison, and compositionality. ComQA contains paraphrase clusters of semantically-equivalent questions that can be exploited by QA systems. We harness a combination of community question-answering platforms and crowdsourcing to construct the ComQA dataset.
For issue (iii), we introduce a neural network model based on subword units for named entity recognition. The model learns word representations using a combination of characters, bytes and phonemes. While achieving comparable performance with word-level based models, our model has an order-of-magnitude smaller vocabulary size and lower memory requirements, and it handles out-of-vocabulary words.

Following a period of expedited progress in the capabilities of digital systems, the society begins to realize that systems designed to assist people in various tasks can also harm individuals and society. Mediating access to information and explicitly or implicitly ranking people in increasingly many applications, search systems have a substantial potential to contribute to such unwanted outcomes. Since they collect vast amounts of data about both searchers and search subjects, they have the potential to violate the privacy of both of these groups of users. Moreover, in applications where rankings influence people's economic livelihood outside of the platform, such as sharing economy or hiring support websites, search engines have an immense economic power over their users in that they control user exposure in ranked results. This thesis develops new models and methods broadly covering different aspects of privacy and fairness in search systems for both searchers and search subjects. Specifically, it makes the following contributions: (1) We propose a model for computing individually fair rankings where search subjects get exposure proportional to their relevance. The exposure is amortized over time using constrained optimization to overcome searcher attention biases while preserving ranking utility. (2) We propose a model for computing sensitive search exposure where each subject gets to know the sensitive queries that lead to her profile in the top-k search results. The problem of finding exposing queries is technically modeled as reverse nearest neighbor search, followed by a weekly-supervised learning to rank model ordering the queries by privacy-sensitivity. (3) We propose a model for quantifying privacy risks from textual data in online communities. The method builds on a topic model where each topic is annotated by a crowdsourced sensitivity score, and privacy risks are associated with a user's relevance to sensitive topics. We propose relevance measures capturing different dimensions of user interest in a topic and show how they correlate with human risk perceptions. (4) We propose a model for privacy-preserving personalized search where search queries of different users are split and merged into synthetic profiles. The model mediates the privacy-utility trade-off by keeping semantically coherent fragments of search histories within individual profiles, while trying to minimize the similarity of any of the synthetic profiles to the original user profiles. The models are evaluated using information retrieval techniques and user studies over a variety of datasets, ranging from query logs, through social media and community question answering postings, to item listings from sharing economy platforms.

Although all the cells in an organism posses the same genome, the regulatory mechanisms lead to highly specific cell types. Elucidating these regulatory mechanisms is a great challenge in systems biology research. Nonetheless, it is known that a large fraction of our genome is comprised of regulatory elements, the precise mechanisms by which different combinations of regulatory elements are involved in controlling gene expression and cell identity are poorly understood. This thesis describes algorithms and approaches for modeling and analysis of different modes of gene regulation. We present POSTIT a novel algorithm for modeling and inferring transcript isoform regulation from transcriptomics and epigenomics data. POSTIT uses multi-task learning with structured-sparsity inducing regularizer to share the regulatory information between isoforms of a gene, which is shown to lead to accurate isoform expression prediction and inference of regulators. Furthermore, it can use isoform expression level and annotation as informative priors for gene expression prediction. Hence, it constitute a novel accurate approach applicable to gene or transcript isoform centric analysis using expression data. In an application to microRNA (miRNA) target prioritization, we demonstrate that it out-competes classical gene centric methods. Moreover, pinpoints important transcription factors and miRNAs that regulate differentially expressed isoforms in any biological system. Competing endogenous RNA (ceRNA) interactions mediated by miRNAs were postulated as an important cellular regulatory network, in which cross-talk between different transcripts involves competition for joint regulators. We developed a novel statistical method, called SPONGE, for large-scale inference of ceRNA networks. In this framework, we designed an efficient empirical p-value computation approach, by sampling from derived null models, which addresses important confounding factors such as sample size, number of involved regulators and strength of correlation. In an application to a large pan-cancer dataset with 31 cancers we discovered protein-coding and non-coding RNAs that are generic ceRNAs in cancer. Finally, we present an integrative analysis of miRNA and protein-based posttranscriptional regulation. We postulate a competitive regulation of the RNAbinding protein IMP2 with miRNAs binding the same RNAs using expression and RNA binding data. This function of IMP2 is relevant in the contribution to disease in the context of adult cellular metabolism. As a summary, in this thesis we have presented a number of different novel approaches for inference and the integrative analysis of regulatory networks that we believe will find wide applicability in the biological sciences.

The treatment of infections with HIV or HCV is challenging. Thus,
novel drugs and new computational approaches that support the
selection of therapies are required. This work presents methods that
support therapy selection as well as methods that advance novel
antiviral treatments.
geno2pheno[ngs-freq] identifies drug resistance from HIV-1
or HCV samples that were subjected to next-generation sequencing
by interpreting their sequences either via support vector machines
or a rules-based approach. geno2pheno[coreceptor-hiv2] determines the coreceptor that is used for viral cell entry by analyzing a
segment of the HIV-2 surface protein with a support vector machine.
openPrimeR is capable of finding optimal combinations of primers
for multiplex polymerase chain reaction by solving a set cover problem and accessing a new logistic regression model for determining
amplification events arising from polymerase chain reaction.
geno2pheno[ngs-freq] and geno2pheno[coreceptorhiv2] enable the personalization of antiviral treatments and support
clinical decision making. The application of openPrimeR on human
immunoglobulin sequences has resulted in novel primer sets that
improve the isolation of broadly neutralizing antibodies against
HIV-1. The methods that were developed in this work thus constitute
important contributions towards improving the prevention and
treatment of viral infectious diseases.

Epigenetics is the field of biology that investigates heritable factors regulating gene expression without being directly encoded in the genome of an organism. The human genome is densely packed inside a cell's nucleus in the form of chromatin. Certain constituents of chromatin play a vital role as epigenetic factors in the dynamic regulation of gene expression. Epigenetic changes on the chromatin level are thus an integral part of the mechanisms governing the development of the functionally diverse cell types in multicellular species such as human. Studying these mechanisms is not only important to understand the biology of healthy cells, but also necessary to comprehend the epigenetic component in the formation of many complex diseases. Modern wet lab technology enables scientists to probe the epigenome with high throughput and in extensive detail. The fast generation of epigenetic datasets burdens computational researchers with the challenge of rapidly performing elaborate analyses without compromising on the scientific reproducibility of the reported findings. To facilitate reproducible computational research in epigenomics, this thesis proposes a task-oriented metadata model, relying on web technology and supported by database engineering, that aims at consistent and human-readable documentation of standardized computational workflows. The suggested approach features, e.g., computational validation of metadata records, automatic error detection, and progress monitoring of multi-step analyses, and was successfully field-tested as part of a large epigenome research consortium. This work leaves aside theoretical considerations, and intentionally emphasizes the realistic need of providing scientists with tools that assist them in performing reproducible research. Irrespective of the technological progress, the dynamic and cell-type specific nature of the epigenome commonly requires restricting the number of analyzed samples due to resource limitations. The second project of this thesis introduces the software tool SCIDDO, which has been developed for the differential chromatin analysis of cellular samples with potentially limited availability. By combining statistics, algorithmics, and best practices for robust software development, SCIDDO can quickly identify biologically meaningful regions of differential chromatin marking between cell types. We demonstrate SCIDDO's usefulness in an exemplary study in which we identify regions that establish a link between chromatin and gene expression changes. SCIDDO's quantitative approach to differential chromatin analysis is user-customizable, providing the necessary flexibility to adapt SCIDDO to specific research tasks. Given the functional diversity of cell types and the dynamics of the epigenome in response to environmental changes, it is hardly realistic to map the complete epigenome even for a single organism like human or mouse. For non-model organisms, e.g., cow, pig, or dog, epigenome data is particularly scarce. The third project of this thesis investigates to what extent bioinformatics methods can compensate for the comparatively little effort that is invested in charting the epigenome of non-model species. This study implements a large integrative analysis pipeline, including state-of-the-art machine learning, to transfer chromatin data for predictive modeling between 13 species. The evidence presented here indicates that a partial regulatory epigenetic signal is stably retained even over millions of years of evolutionary distance between the considered species. This finding suggests complementary and cost-effective ways for bioinformatics to contribute to comparative epigenome analysis across species boundaries.

Search systems help users locate relevant information in the form of text documents for keyword queries. Using text alone, it is often difficult to satisfy the user's information need. To discern the user's intent behind queries, we turn to semantic annotations (e.g., named entities and temporal expressions) that natural language processing tools can now deliver with great accuracy. This thesis develops methods and an infrastructure that leverage semantic annotations to efficiently and effectively search large document collections. This thesis makes contributions in three areas: indexing, querying, and mining of semantically annotated document collections. First, we describe an indexing infrastructure for semantically annotated document collections. The indexing infrastructure can support knowledge-centric tasks such as information extraction, relationship extraction, question answering, fact spotting and semantic search at scale across millions of documents. Second, we propose methods for exploring large document collections by suggesting semantic aspects for queries. These semantic aspects are generated by considering annotations in the form of temporal expressions, geographic locations, and other named entities. The generated aspects help guide the user to relevant documents without the need to read their contents. Third and finally, we present methods that can generate events, structured tables, and insightful visualizations from semantically annotated document collections.

There is a wealth of schema-free tables on the web. The text accompanying these tables explains and qualifies the numerical quantities given in the tables. Despite this ubiquity of tabular data, there is little research that harnesses this wealth of data by semantically understanding the information that is conveyed rather ambiguously in these tables. This information can be disambiguated only by the help of the accompanying text. In the process of understanding quantity mentions in tables and text, we are faced with the following challenges; First, there is no comprehensive knowledge base for anchoring quantity mentions. Second, tables are created ad-hoc without a standard schema and with ambiguous header names; also table cells usually contain abbreviations. Third, quantities can be written in multiple forms and units of measures. Fourth, the text usually refers to the quantities in tables using aggregation, approximation, and different scales. In this thesis, we target these challenges through the following contributions: - We present the Quantity Knowledge Base (QKB), a knowledge base for representing Quantity mentions. We construct the QKB by importing information from Freebase, Wikipedia, and other online sources. - We propose Equity: a system for automatically canonicalizing header names and cell values onto concepts, classes, entities, and uniquely represented quantities registered in a knowledge base. We devise a probabilistic graphical model that captures coherence dependencies between cells in tables and candidate items in the space of concepts, entities, and quantities. Then, we cast the inference problem into an efficient algorithm based on random walks over weighted graphs. baselines. - We introduce the quantity alignment problem: computing bidirectional links between textual mentions of quantities and the corresponding table cells. We propose BriQ: a system for computing such alignments. BriQ copes with the specific challenges of approximate quantities, aggregated quantities, and calculated quantities. - We design ExQuisiTe: a web application that identifies mentions of quantities in text and tables, aligns quantity mentions in the text with related quantity mentions in tables, and generates salient suggestions for extractive text summarization systems.

We look at some graph problems related to covering, partition, and connectivity. First, we study the problems of covering and partitioning edges with bicliques, especially from the viewpoint of parameterized complexity. For the partition problem, we develop much more efficient algorithms than the ones previously known. In contrast, for the cover problem, our lower bounds show that the known algorithms are probably optimal. Next, we move on to graph coloring, which is probably the most extensively studied partition problem in graphs. Hadwiger’s conjecture is a long-standing open problem related to vertex coloring. We prove the conjecture for a special class of graphs, namely squares of 2-trees, and show that square graphs are important in connection with Hadwiger’s conjecture. Then, we study a coloring problem that has been emerging recently, called rainbow coloring. This problem lies in the intersection of coloring and connectivity. We study different variants of rainbow coloring and present bounds and complexity results on them. Finally, we move on to another parameter related to connectivity called spanning tree congestion (STC). We give tight bounds for STC in general graphs and random graphs. While proving the results on

Matrix factorizations are an important tool in data mining, and they have been used extensively for finding latent patterns in the data. They often allow to separate structure from noise, as well as to considerably reduce the dimensionality of the input matrix. While classical matrix decomposition methods, such as nonnegative matrix factorization (NMF) and singular value decomposition (SVD), proved to be very useful in data analysis, they are limited by the underlying algebraic structure. NMF, in particular, tends to break patterns into smaller bits, often mixing them with each other. This happens because overlapping patterns interfere with each other, making it harder to tell them apart. In this thesis we study matrix factorization over algebraic structures known as dioids, which are characterized by the lack of additive inverse (“negative numbers”) and the idempotency of addition (a + a = a). Using dioids makes it easier to separate overlapping features, and, in particular, it allows to better deal with the above mentioned pattern breaking problem. We consider different types of dioids, that range from continuous (subtropical and tropical algebras) to discrete (Boolean algebra). Among these, the Boolean algebra is perhaps the most well known, and there exist methods that allow one to obtain high quality Boolean matrix factorizations in terms of the reconstruction error. In this work, however, a different objective function is used – the description length of the data, which enables us to obtain compact and highly interpretable results. The tropical and subtropical algebras, on the other hand, are much less known in the data mining field. While they find applications in areas such as job scheduling and discrete event systems, they are virtually unknown in the context of data analysis. We will use them to obtain idempotent nonnegative factorizations that are similar to NMF, but are better at separating the most prominent features of the data.

Synthesizing novel views from image data is a widely investigated topic in both computer graphics and computer vision, and has many applications like stereo or multi-view rendering for virtual reality, light field reconstruction, and image post-processing. While image-based approaches have the advantage of reduced computational load compared to classical model-based rendering, efficiency is still a major concern. This thesis demonstrates how concepts and tools from artificial intelligence can be used to increase the efficiency of image-based view synthesis algorithms. In particular it is shown how machine learning can help to generate point patterns useful for a variety of computer graphics tasks, how path planning can guide image warping, how sparsity-enforcing optimization can lead to significant speedups in interactive distribution effect rendering, and how probabilistic inference can be used to perform real-time 2D-to-3D conversion.

Graph decomposition has always been a very important concept in machine learning and computer vision. Many tasks like image and mesh segmentation, community detection in social networks, as well as object tracking and human pose estimation can be formulated as a graph decomposition problem. The multicut problem in particular is a popular model to optimize for a decomposition of a given graph. Its main advantage is that no prior knowledge about the number of components or their sizes is required. However, it has several limitations, which we address in this thesis: Firstly, the multicut problem allows to specify only cost or reward for putting two direct neighbours into distinct components. This limits the expressibility of the cost function. We introduce special edges into the graph that allow to define cost or reward for putting any two vertices into distinct components, while preserving the original set of feasible solutions. We show that this considerably improves the quality of image and mesh segmentations. Second, multicut is notorious to be NP-hard for general graphs, that limits its applications to small super-pixel graphs. We define and implement two primal feasible heuristics to solve the problem. They do not provide any guarantees on the runtime or quality of solutions, but in practice show good convergence behaviour. We perform an extensive comparison on multiple graphs of different sizes and properties. Third, we extend the multicut framework by introducing node labels, so that we can jointly optimize for graph decomposition and nodes classification by means of exactly the same optimization algorithm, thus eliminating the need to hand-tune optimizers for a particular task. To prove its universality we applied it to diverse computer vision tasks, including human pose estimation, multiple object tracking, and instance-aware semantic segmentation. We show that we can improve the results over the prior art using exactly the same data as in the original works. Finally, we use employ multicuts in two applications: 1) a client-server tool for interactive video segmentation: After the pre-processing of the video a user draws strokes on several frames and a time-coherent segmentation of the entire video is performed on-the-fly. 2) we formulate a method for simultaneous segmentation and tracking of living cells in microscopy data. This task is challenging as cells split and our algorithm accounts for this, creating parental hierarchies. We also present results on multiple model fitting. We find models in data heavily corrupted by noise by finding components defining these models using higher order multicuts. We introduce an interesting extension that allows our optimization to pick better hyperparameters for each discovered model. In summary, this thesis extends the multicut problem in different directions, proposes algorithms for optimization, and applies it to novel data and settings.

With the development of chromosome conformation capture-based techniques, we now know that chromatin is packed in three-dimensional (3D) space inside the cell nucleus. Changes in the 3D chromatin architecture have already been implicated in diseases such as cancer. Thus, a better understanding of this 3D conformation is of interest to help enhance our comprehension of the complex, multipronged regulatory mechanisms of the genome. The work described in this dissertation largely focuses on development and application of interpretable machine learning methods for prediction and analysis of long-range genomic interactions output from chromatin interaction experiments. In the first part, we demonstrate that the genetic sequence information at the ge- nomic loci is predictive of the long-range interactions of a particular locus of interest (LoI). For example, the genetic sequence information at and around enhancers can help predict whether it interacts with a promoter region of interest. This is achieved by building string kernel-based support vector classifiers together with two novel, in- tuitive visualization methods. These models suggest a potential general role of short tandem repeat motifs in the 3D genome organization. But, the insights gained out of these models are still coarse-grained. To this end, we devised a machine learning method, called CoMIK for Conformal Multi-Instance Kernels, capable of providing more fine-grained insights. When comparing sequences of variable length in the su- pervised learning setting, CoMIK can not only identify the features important for classification but also locate them within the sequence. Such precise identification of important segments of the whole sequence can help in gaining de novo insights into any role played by the intervening chromatin towards long-range interactions. Although CoMIK primarily uses only genetic sequence information, it can also si- multaneously utilize other information modalities such as the numerous functional genomics data if available. The second part describes our pipeline, pHDee, for easy manipulation of large amounts of 3D genomics data. We used the pipeline for analyzing HiChIP experimen- tal data for studying the 3D architectural changes in Ewing sarcoma (EWS) which is a rare cancer affecting adolescents. In particular, HiChIP data for two experimen- tal conditions, doxycycline-treated and untreated, and for primary tumor samples is analyzed. We demonstrate that pHDee facilitates processing and easy integration of large amounts of 3D genomics data analysis together with other data-intensive bioinformatics analyses.

Despite being a vast resource of valuable information, the Web has been polluted by the spread of false claims. Increasing hoaxes, fake news, and misleading information on the Web have given rise to many fact-checking websites that manually assess these doubtful claims. However, the rapid speed and large scale of misinformation spread have become the bottleneck for manual verification. This calls for credibility assessment tools that can automate this verification process. Prior works in this domain make strong assumptions about the structure of the claims and the communities where they are made. Most importantly, black-box techniques proposed in prior works lack the ability to explain why a certain statement is deemed credible or not. To address these limitations, this dissertation proposes a general framework for automated credibility assessment that does not make any assumption about the structure or origin of the claims. Specifically, we propose a feature-based model, which automatically retrieves relevant articles about the given claim and assesses its credibility by capturing the mutual interaction between the language style of the relevant articles, their stance towards the claim, and the trustworthiness of the underlying web sources. We further enhance our credibility assessment approach and propose a neural-network-based model. Unlike the feature-based model, this model does not rely on feature engineering and external lexicons. Both our models make their assessments interpretable by extracting explainable evidence from judiciously selected web sources. We utilize our models and develop a Web interface, CredEye, which enables users to automatically assess the credibility of a textual claim and dissect into the assessment by browsing through judiciously and automatically selected evidence snippets. In addition, we study the problem of stance classification and propose a neural-network-based model for predicting the stance of diverse user perspectives regarding the controversial claims. Given a controversial claim and a user comment, our stance classification model predicts whether the user comment is supporting or opposing the claim.

Technologies for motion and performance capture of real actors have enabled the creation of realisticlooking virtual humans through detail and deformation transfer at the cost of extensive manual work and sophisticated in-studio marker-based systems. This thesis pushes the boundaries of performance capture by proposing automatic algorithms for robust 3D skeleton and detailed surface tracking in less constrained multi-view outdoor scenarios. Contributions include new multi-layered human body representations designed for effective model-based time-consistent reconstruction in complex dynamic environments with varying illumination, from a set of vision cameras. We design dense surface refinement approaches to enable smooth silhouette-free model-to-image alignment, as well as coarse-to-fine tracking techniques to enable joint estimation of skeleton motion and finescale surface deformations in complicated scenarios. High-quality results attained on challenging application scenarios confirm the contributions and show great potential for the automatic creation of personalized 3D virtual humans.

Visual search is an important task, and it is part of daily human life. Thus, it has been a long-standing goal in Computer Vision to develop methods aiming at analysing human search intent and preferences. As the target of the search only exists in mind of the person, search intent prediction remains challenging for machine perception. In this thesis, we focus on advancing techniques for search target and preference prediction from implicit human cues. First, we propose a search target inference algorithm from human fixation data recorded during visual search. In contrast to previous work that has focused on individual instances as a search target in a closed world, we propose the first approach to predict the search target in open-world settings by learning the compatibility between observed fixations and potential search targets. Second, we further broaden the scope of search target prediction to categorical classes, such as object categories and attributes. However, state of the art models for categorical recognition, in general, require large amounts of training data, which is prohibitive for gaze data. To address this challenge, we propose a novel Gaze Pooling Layer that integrates gaze information into CNN-based architectures as an attention mechanism – incorporating both spatial and temporal aspects of human gaze behaviour. Third, we go one step further and investigate the feasibility of combining our gaze embedding approach, with the power of generative image models to visually decode, i.e. create a visual representation of, the search target. Forth, for the first time, we studied the effect of body shape on people preferences of outfits. We propose a novel and robust multi-photo approach to estimate the body shapes of each user and build a conditional model of clothing categories given body-shape. We demonstrate that in real-world data, clothing categories and body-shapes are correlated. We show that our approach estimates a realistic looking body shape that captures a user’s weight group and body shape type, even from a single image of a clothed person. However, an accurate depiction of the naked body is considered highly private and therefore, might not be consented by most people. First, we studied the perception of such technology via a user study. Then, in the last part of this thesis, we ask if the automatic extraction of such information can be effectively evaded. In summary, this thesis addresses several different tasks that aims to enable the vision system to analyse human search intent and preferences in real-world scenarios. In particular, the thesis proposes several novel ideas and models in visual search target prediction from human fixation data, for the first time studied the correlation between shape and clothing categories opening a new direction in clothing recommendation systems, and introduces a new topic in privacy and computer vision, aimed at preventing automatic 3D shape extraction from images.

The Internet infrastructure relies on the correct functioning of the basic underlying protocols, which were designed for functionality. Security and privacy have been added post hoc, mostly by applying cryptographic means to different layers of communication. In the absence of accountability, as a fundamental property, the Internet infrastructure does not have a built-in ability to associate an action with the responsible entity, neither to detect or prevent misbehavior. In this thesis, we study accountability from a few different perspectives. First, we study the need of having accountability in anonymous communication networks as a mechanism that provides repudiation for the proxy nodes by tracing back selected outbound traffic in a provable manner. Second, we design a framework that provides a foundation to support the enforcement of the right to be forgotten law in a scalable and automated manner. The framework provides a technical mean for the users to prove their eligibility for content removal from the search results. Third, we analyze the Internet infrastructure determining potential security risks and threats imposed by dependencies among the entities on the Internet. Finally, we evaluate the feasibility of using hop count filtering as a mechanism for mitigating Distributed Reflective Denial-of-Service attacks, and conceptually show that it cannot work to prevent these attacks.

Eye tracking and gaze-based human-computer interfaces have become a practical modality in desktop settings, since remote eye tracking is efficient and affordable. However, remote eye tracking remains constrained to indoor, laboratory-like conditions, in which lighting and user position need to be controlled. Mobile eye tracking has the potential to overcome these limitations and to allow people to move around freely and to use eye tracking on a daily basis during their everyday routine. However, mobile eye tracking currently faces two fundamental challenges that prevent it from being practically usable and that, consequently, have to be addressed before mobile eye tracking can truly be used by everyone: Mobile eye tracking needs to be advanced and made fully functional in unconstrained environments, and it needs to be made socially acceptable. Numerous sensing and analysis methods were initially developed for remote eye tracking and have been successfully applied for decades. Unfortunately, these methods are limited in terms of functionality and correctness, or even unsuitable for application in mobile eye tracking. Therefore, the majority of fundamental definitions, eye tracking methods, and gaze estimation approaches cannot be borrowed from remote eye tracking without adaptation. For example, the definitions of specific eye movements, like classical fixations, need to be extended to mobile settings where natural user and head motion are omnipresent. Corresponding analytical methods need to be adjusted or completely reimplemented based on novel approaches encoding the human gaze behaviour. Apart from these technical challenges, an entirely new, and yet under-explored, topic required for the breakthrough of mobile eye tracking as everyday technology is the overcoming of social obstacles. A first crucial key issue to defuse social objections is the building of acceptance towards mobile eye tracking. Hence, it is essential to replace the bulky appearance of current head-mounted eye trackers with an unobtrusive, appealing, and trendy design. The second high-priority theme of increasing importance for everyone is privacy and its protection, given that research and industry have not focused on or taken care of this problem at all. To establish true confidence, future devices have to find a fine balance between protecting users’ and bystanders’ privacy and attracting and convincing users of their necessity, utility, and potential with useful and beneficial features. The solution of technical challenges and social obstacles is the prerequisite for the development of a variety of novel and exciting applications in order to establish mobile eye tracking as a new paradigm, which ease our everyday life. This thesis addresses core technical challenges of mobile eye tracking that currently prevent it from being widely adopted. Specifically, this thesis proves that 3D data used for the calibration of mobile eye trackers improves gaze estimation and significantly reduces the parallax error. Further, it presents the first effective fixation detection method for head-mounted devices that is robust against the prevalence of user and gaze target motion. In order to achieve social acceptability, this thesis proposes an innovative and unobtrusive design for future mobile eye tracking devices and builds the first prototype with fully frame-embedded eye cameras combined with a calibration-free deep-trained appearance-based gaze estimation approach. To protect users’ and bystanders’ privacy in the presence of head-mounted eye trackers, this thesis presents another first-of-its-kind prototype. It is able to identify privacy-sensitive situations to automatically enable and disable the eye tracker’s first-person camera by means of a mechanical shutter, leveraging the combination of deep scene and eye movement features. Nevertheless, solving technical challenges and social obstacles alone is not sufficient to make mobile eye tracking attractive for the masses. The key to success is the development of convincingly useful, innovative, and essential applications. To extend the protection of users’ privacy on the software side as well, this thesis presents the first privacy-aware VR gaze interface using differential privacy. This method adds noise to recorded eye tracking data so that privacy-sensitive information like a user’s gender or identity is protected without impeding the utility of the data itself. In addition, the first large-scale online survey is conducted to understand users’ concerns with eye tracking. To develop and evaluate novel applications, this thesis presents the first publicly available long-term eye tracking datasets. They are used to show the unsupervised detection of users’ activities from eye movements alone using novel and efficient video-based encoding approaches as well as to propose the first proof-of-concept method to forecast users’ attentive behaviour during everyday mobile interactions from phone-integrated and body-worn sensors. This opens up possibilities for the development of a variety of novel and exciting applications. With more advanced features, accompanied by technological progress and sensor miniaturisation, eye tracking is increasingly integrated into conventional glasses as well as virtual and augmented reality (VR/AR) head-mounted displays, becoming an integral component of mobile interfaces. This thesis paves the way for the development of socially acceptable, privacy-aware, but highly functional mobile eye tracking devices and novel applications, so that mobile eye tracking can develop its full potential to become an everyday technology for everyone.

First-order logic is one of the most prominent formalisms in computer science and mathematics. Since there is no algorithm capable of solving its satisfiability problem, first-order logic is said to be undecidable. The classical decision problem is the quest for a delineation between the decidable and the undecidable parts. The results presented in this thesis shed more light on the boundary and open new perspectives on the landscape of known decidable fragments. In the first part we focus on the new concept of separateness of variables and explore its applicability to the classical decision problem and beyond. Two disjoint sets of first-order variables are separated in a given formula if none of its atoms contains variables from both sets. This notion facilitates the definition of decidable extensions of many well-known decidable first-order fragments. We demonstrate this for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In two cases the succinctness gap cannot be bounded using elementary functions. This fact already hints at computationally hard satisfiability problems. Indeed, we derive non-elementary lower bounds for the separated fragment, an extension of the Bernays-Schönfinkel-Ramsey fragment (E*A*-prefix sentences). On the semantic level, separateness of quantified variables may lead to weaker dependences than we encounter in general. We investigate this property in the context of model-checking games. The focus of the second part of the thesis is on linear arithmetic with uninterpreted predicates. Two novel decidable fragments are presented, both based on the Bernays-Schönfinkel-Ramsey fragment. On the negative side, we identify several small fragments of the language for which satisfiability is undecidable.

Proteins participate in most of the important processes in cells, and their ability to perform their function ultimately depends on their three-dimensional structure. They usually act in these processes through interactions with other molecules. Because of the importance of their role, proteins are also the common target for small molecule drugs that inhibit their activity, which may include targeting protein interactions. Understanding protein interactions and how they are affected by mutations is thus crucial for combating drug resistance and aiding drug design. This dissertation combines bioinformatics studies of protein interactions at both primary sequence and structural level. We analyse protein-protein interactions through linear motifs, as well as protein-small molecule interactions, and study how mutations affect them. This is done in the context of two systems. In the first study of drug resistance mutations in the protease of the human immunodeficiency virus type 1, we successfully apply molecular dynamics simulations to estimate the effects of known resistance-associated mutations on the free binding energy, also revealing molecular mechanisms of resistance. In the second study, we analyse consensus profiles of linear motifs that mediate the recognition by the mitogen-activated protein kinases of their target proteins. We thus gain insights into the cellular processes these proteins are involved in.

Over the years, computer systems and applications have grown significantly complex while handling a plethora of private and sensitive user information. The complexity of these applications is often assisted by a set of (un)intentional bugs with both malicious and non-malicious intent leading to information leaks. Information flow control has been studied extensively as an approach to mitigate such information leaks. The technique works by enforcing the security property of non-interference using a specified set of security policies. A vast majority of existing work in this area is based on static analyses. However, some of the applications, especially on the Web, are developed using dynamic languages like JavaScript that make the static analyses techniques stale and ineffective. As a result, there has been a growing interest in recent years to develop dynamic information flow analysis techniques. In spite of the advances in the field, dynamic information flow analysis has not been at the helm of information flow security in dynamic settings like the Web; the prime reason being that the analysis techniques and the security property related to them (non-interference) either over-approximate or are too restrictive in most cases. Concretely, the analysis techniques gen- erate a lot of false positives, do not allow legitimate release of sensitive information, support only static and rigid security policies or are not general enough to be applied to real-world applications. This thesis focuses on improving the usability of dynamic information flow techniques by presenting mechanisms that can enhance the precision and permissiveness of the analyses. It begins by presenting a sound improvement and enhancement of the permissive-upgrade strategy, a strategy widely used to enforce dynamic information flow control, which improves the strategy’s permissiveness and makes it generic in applicability. The thesis, then, presents a sound and precise control scope analysis for handling complex features like unstructured control flow and exceptions in higher-order languages. Although non-interference is a desired property for enforcing information flow control, there are program instances that require legitimate release of some parts of the secret data to provide the required functionality. Towards this end, this thesis develops a sound approach to bound information leaks dynamically while allowing information release in accordance to a pre-specified budget. The thesis concludes by applying these techniques to an information flow control-enabled Web browser and explores a policy specification mechanism that allows flexible and useful information flow policies to be specified for Web applications.

Computers become increasingly complex. Current and future systems feature configurable hardware, multiple cores with different capabilities, as well as accelerators. In addition, the memory subsystem becomes diversified too. The cache hierarchy grows deeper, is augmented with scratchpads, low-latency memory, and high-bandwidth memory. The programmer alone cannot utilize this enormous potential. Compilers have to provide insight into the program behavior, or even arrange computations and data themselves. Either way, they need a more holistic view of the program. Local transformations, which treat the iteration order, computation unit, and data layout as fixed, will not be able to fully utilize a diverse system. The polyhedral model, a high-level program representation and transformation framework, has shown great success tackling various problems in the context of diverse systems. While it is widely acknowledged for its analytical powers and transformation capabilities, it is also widely assumed to be too restrictive and fragile for real-world programs. In this thesis we improve the applicability and profitability of polyhedral-model-based techniques. Our efforts guarantee a sound polyhedral representation and extend the applicability to a wider range of programs. In addition, we introduce new applications to utilize the information available in the polyhedral program representation, including standalone optimizations and techniques to derive high-level properties.

While general-purpose Knowledge Bases (KBs) have gone a long way in compiling comprehensive knowledgee about people, events, places, etc., domain-specific KBs, such as on health, are equally important, but are less explored. Consequently, a comprehensive and expressive health KB that spans all aspects of biomedical knowledge is still missing. The main goal of this thesis is to develop principled methods for building such a KB and enabling knowledge-centric applications. We address several challenges and make the following contributions: - To construct a health KB, we devise a largely automated and scalable pattern-based knowledge extraction method covering a spectrum of different text genres and distilling a wide variety of facts from different biomedical areas. - To consider higher-arity relations, crucial for proper knowledge representation in advanced domain such as health, we generalize the fact-pattern duality paradigm of previous methods. A key novelty is the integration of facts with missing arguments by extending our framework to partial patterns and facts by reasoning over the composability of partial facts. - To demonstrate the benefits of a health KB, we devise systems for entity-aware search and analytics and for entity-relationship-oriented exploration. Extensive experiments and use-case studies demonstrate the viability of the proposed approaches.

Genomics has paved a new way to comprehend life and its evolution, and also to investigate causes of diseases and their treatment. One of the important problems in genomic analyses is haplotype assembly. Constructing complete and accurate haplotypes plays an essential role in understanding population genetics and how species evolve. In this thesis, we focus on computational approaches to haplotype assembly from third generation sequencing technologies. This involves huge amounts of sequencing data, and such data contain errors due to the single molecule sequencing protocols employed. Taking advantage of combinatorial formulations helps to correct for these errors to solve the haplotyping problem. Various computational techniques such as dynamic programming, parameterized algorithms, and graph algorithms are used to solve this problem. This thesis presents several contributions concerning the area of haplotyping. First, a novel algorithm based on dynamic programming is proposed to provide approximation guarantees for phasing a single individual. Second, an integrative approach is introduced to combining multiple sequencing datasets to generating complete and accurate haplotypes. The effectiveness of this integrative approach is demonstrated on a real human genome. Third, we provide a novel efficient approach to phasing pedigrees and demonstrate its advantages in comparison to phasing a single individual. Fourth, we present a generalized graph-based framework for performing haplotype-aware de novo assembly. Specifically, this generalized framework consists of a hybrid pipeline for generating accurate and complete haplotypes from data stemming from multiple sequencing technologies, one that provides accurate reads and other that provides long reads.

Abstract
In this thesis, we deal with two packing problems: the online bin packing
and the geometric knapsack problem. In online bin packing, the aim is to pack
a given number of items of dierent size into a minimal number of containers.
The items need to be packed one by one without knowing future items. For
online bin packing in one dimension, we present a new family of algorithms
that constitutes the rst improvement over the previously best algorithm in
almost 15 years. While the algorithmic ideas are intuitive, an elaborate analysis
is required to prove its competitive ratio. We also give a lower bound for the
competitive ratio of this family of algorithms. For online bin packing in higher
dimensions, we discuss lower bounds for the competitive ratio and show that the
ideas from the one-dimensional case cannot be easily transferred to obtain better
two-dimensional algorithms.
In the geometric knapsack problem, one aims to pack a maximum weight
subset of given rectangles into one square container. For this problem, we consider
oine approximation algorithms. For geometric knapsack with square items,
we improve the running time of the best known
PTAS
and obtain an
EPTAS
.
This shows that large running times caused by some standard techniques for
geometric packing problems are not always necessary and can be improved.
Finally, we show how to use resource augmentation to compute optimal solutions
in
EPTAS
-time, thereby improving upon the known
PTAS for this case.

From autonomous driving cars to surgical robots, robotic system has enjoyed significant growth over the past decade. With the rapid development in robotics alongside the evolution in the related fields, such as computer vision and machine learning, integrating perception, anticipation and manipulation is key to the success of future robotic system. In this thesis, we explore different ways of such integration to extend the capabilities of a robotic system to take on more challenging real world tasks. On anticipation and perception, we address the recognition of ongoing activity from videos. In particular we focus on long-duration and complex activities and hence propose a new challenging dataset to facilitate the work. We introduce hierarchical labels over the activity classes and investigate the temporal accuracy-specificity trade-offs. We propose a new method based on recurrent neural networks that learns to predict over this hierarchy and realize accuracy specificity trade-offs. Our method outperforms several baselines on this new challenge. On manipulation with perception, we propose an efficient framework for programming a robot to use human tools. We first present a novel and compact model for using tools described by a tip model. Then we explore a strategy of utilizing a dual-gripper approach for manipulating tools – motivated by the absence of dexterous hands on widely available general purpose robots. Afterwards, we embed the tool use learning into a hierarchical architecture and evaluate it on a Baxter research robot. Finally, combining perception, anticipation and manipulation, we focus on a block stacking task. First we explore how to guide robot to place a single block into the scene without collapsing the existing structure. We introduce a mechanism to predict physical stability directly from visual input and evaluate it first on a synthetic data and then on real-world block stacking. Further, we introduce the target stacking task where the agent stacks blocks to reproduce a tower shown in an image. To do so, we create a synthetic block stacking environment with physics simulation in which the agent can learn block stacking end-to-end through trial and error, bypassing to explicitly model the corresponding physics knowledge. We propose a goal-parametrized GDQN model to plan with respect to the specific goal. We validate the model on both a navigation task in a classic gridworld environment and the block stacking task.

Today in this Big Data era, overwhelming amounts of textual information across different sources with a high degree of redundancy has made it hard for a consumer to retrospect on past events. A plausible solution is to link semantically similar information contained across the different sources to enforce a structure thereby providing multiple access paths to relevant information. Keeping this larger goal in view, this work uses Wikipedia and online news articles as two prominent yet disparate information sources to address the following three problems: • We address a linking problem to connect Wikipedia excerpts to news articles by casting it into an IR task. Our novel approach integrates time, geolocations, and entities with text to identify relevant documents that can be linked to a given excerpt. • We address an unsupervised extractive multi-document summarization task to generate a fixed-length event digest that facilitates efficient consumption of information contained within a large set of documents. Our novel approach proposes an ILP for global inference across text, time, geolocations, and entities associated with the event. • To estimate temporal focus of short event descriptions, we present a semi-supervised approach that leverages redundancy within a longitudinal news collection to estimate accurate probabilistic time models. Extensive experimental evaluations demonstrate the effectiveness and viability of our proposed approaches towards achieving the larger goal.

Machine learning is transforming the world. Its application areas span privacy
sensitive and security critical tasks such as human identification and self-driving
cars. These applications raise privacy and security related questions that are not
fully understood or answered yet: Can automatic person recognisers identify people
in photos even when their faces are blurred? How easy is it to find an adversarial
input for a self-driving car that makes it drive off the road?
This thesis contributes one of the first steps towards a better understanding of
such concerns. We observe that many privacy and security critical scenarios for
learned models involve input data manipulation: users obfuscate their identity by
blurring their faces and adversaries inject imperceptible perturbations to the input
signal. We introduce a data manipulator framework as a tool for collectively describing
and analysing privacy and security relevant scenarios involving learned models.
A data manipulator introduces a shift in data distribution for achieving privacy or
security related goals, and feeds the transformed input to the target model. This
framework provides a common perspective on the studies presented in the thesis.
We begin the studies from the user’s privacy point of view. We analyse the
efficacy of common obfuscation methods like face blurring, and show that they
are surprisingly ineffective against state of the art person recognition systems. We
then propose alternatives based on head inpainting and adversarial examples. By
studying the user privacy, we also study the dual problem: model security. In model
security perspective, a model ought to be robust and reliable against small amounts
of data manipulation. In both cases, data are manipulated with the goal of changing
the target model prediction. User privacy and model security problems can be
described with the same objective.
We then study the knowledge aspect of the data manipulation problem. The more
one knows about the target model, the more effective manipulations one can craft.
We propose a game theoretic manipulation framework to systematically represent
the knowledge level on the target model and derive privacy and security guarantees.
We then discuss ways to increase knowledge about a black-box model by only querying
it, deriving implications that are relevant to both privacy and security perspectives.

With the goal of lifting model-based guidance from the propositional setting to first-
order logic, I have developed an approximation theorem proving approach based on
counterexample-guided abstraction refinement. A given clause set is transformed
into a simplified form where satisfiability is decidable. This approximation extends
the signature and preserves unsatisfiability: if the simplified clause set is satisfi-
able, so is the original clause set. A resolution refutation generated by a decision
procedure on the simplified clause set can then either be lifted to a refutation in
the original clause set, or it guides a refinement excluding the previously found
unliftable refutation. This way the approach is refutationally complete.
The monadic shallow linear Horn fragment, which is the initial target of the
approximation, is well-known to be decidable. It was a long standing open prob-
lem how to extend the fragment to the non-Horn case, preserving decidability, that
would, e.g., enable to express non-determinism in protocols. I have now proven de-
cidability of the non-Horn monadic shallow linear fragment via ordered resolution.
I further extend the clause language with a new type of constraints, called
straight dismatching constraints. The extended clause language is motivated by an
improved refinement of the approximation-refinement framework. All needed oper-
ations on straight dismatching constraints take linear or linear logarithmic time in
the size of the constraint. Ordered resolution with straight dismatching constraints
is sound and complete and the monadic shallow linear fragment with straight dis-
matching constraints is decidable.
I have implemented my approach based on the SPASS theorem prover. On cer-
tain satisfiable problems, the implementation shows the ability to beat established
provers such as SPASS, iProver, and Vampire.

The ability to interconnect multiple knowledge repositories within a single framework is a key asset for various use cases such as document retrieval and question answering. However, independently created repositories are inherently heterogeneous, reflecting their diverse origins. Thus, there is a need to align concepts and entities across knowledge repositories. A limitation of prior work is the assumption of high afinity between the repositories at hand, in terms of structure and terminology. The goal of this dissertation is to develop methods for constructing and curating alignments between multi-cultural knowledge repositories. The first contribution is a system, ACROSS, for reducing the terminological gap between repositories. The second contribution is two alignment methods, LILIANA and SESAME, that cope with structural diversity. The third contribution, LAIKA, is an approach to compute alignments between dynamic repositories. Experiments with a suite ofWeb-scale knowledge repositories show high quality alignments. In addition, the application benefits of LILIANA and SESAME are demonstrated by use cases in search and exploration.

Persistent Homology is a tool to analyze and visualize the shape of data from a topological viewpoint. It computes persistence, which summarizes the evolution of topological and geometric information about metric spaces over multiple scales of distances. While computing persistence is quite efficient for low-dimensional topological features, it becomes overwhelmingly expensive for medium to high-dimensional features. In this thesis, we attack this computational problem from several different angles. We present efficient techniques to approximate the persistence of metric spaces. Three of our methods are tailored towards general point clouds in Euclidean spaces. We make use of high dimensional lattice geometry to reduce the cost of the approximations. In particular, we discover several properties of the Permutahedral lattice, whose Voronoi cell is well-known for its combinatorial properties. The last method is suitable for point clouds with low intrinsic dimension, where we exploit the structural properties of the point set to tame the complexity. In some cases, we achieve a reduction in size complexity by trading off the quality of the approximation. Two of our methods work particularly well in conjunction with dimension-reduction techniques: we arrive at the first approximation schemes whose complexities are only polynomial in the size of the point cloud, and independent of the ambient dimension. On the other hand, we provide a lower bound result: we construct a point cloud that requires super-polynomial complexity for a high-quality approximation of the persistence. Together with our approximation schemes, we show that polynomial complexity is achievable for rough approximations, but impossible for sufficiently fine approximations. For some metric spaces, the intrinsic dimension is low in small neighborhoods of the input points, but much higher for large scales of distances. We develop a concept of local intrinsic dimension to capture this property. We also present several applications of this concept, including an approximation method for persistence. This thesis is written in English.

Languages shape thoughts. This is true for human spoken languages as much as for programming languages. As computers continue to expand their dominance in almost every aspect of our lives, the need to more adequately express new concepts and domains in computer languages arise. However, to evolve our thoughts we need to evolve the languages we speek in. But what tools are there to create and upgrade the computer languages? How can we encourage developers to define their own languages quickly to best match the domains they work in? Nowadays two main approaches exists. Dedicated language tools and parser generators allows to define new standalone languages from scratch. Alternatively, one can “abuse” sufficiently flexible host languages to embed small domain- specific languages within them. Both approaches have their own respective limitations. Creating standalone languages is a major endeavor. Such languages cannot be combined easily with other languages. Embedding, on the other hand, is limited by the syntax of the host language. Embedded languages, once defined, are always present without clear distinction between them and the host language. When used extensively, it leads to one humungous conglomerate of languages, with confusing syntax and unexpected interactions. In this work we present an alternative: ManyDSL. It is a unique interpreter and compiler taking strength from both approaches, while avoiding the above weaknesses. ManyDSL features its own LL1 parser generator, breaking the limits of the syntax of the host language. The grammar description is given in the same host language as the rest of the program. Portions of the grammar can be parametrized and abstracted into functions, in order to be used in other language definitions. Languages are created on the fly during the interpretation process and may be used to parse selected fragments of the subsequent source files. Similarly to embedded languages, ManyDSL translates all custom languages to the same host language before execution. The host language uses a continuation- passing style approach with a novel, dynamic approach to staging. The staging allows for arbitrary partial evaluation, and executing code at different phases of the compilation process. This can be used to define domain-specific optimiza- tions and auxiliary computation (e.g. for verification) — all within an entirely functional approach, without any explicit use of abstract syntax trees and code transformations. With the help of ManyDSL a user is able to create new languages with distinct, easily recognizable syntax. Moreover, he is able to define and use many of such languages within a single project. Languages can be switched with a well-defined boundary, enabling their interaction in a clear and controlled way. ManyDSL is meant to be the first step towards a broader language pluralism. With it we want to encourage developers to design and use languages that best suit their needs. We believe that over time, with the help of grammar libraries, creating new languages will become accessible to every programmer.

This doctoral thesis aims towards distributed natural computing inspired by the slime mold Physarum polycephalum. The vein networks formed by this organism presumably support efficient transport of protoplasmic fluid. Devising models which capture the natural efficiency of the organism and form a suitable basis for the development of natural computing algorithms is an interesting and challenging goal. We start working towards this goal by designing and executing wet-lab experi- ments geared towards producing a large number of images of the vein networks of P. polycephalum. Next, we turn the depicted vein networks into graphs using our own custom software called Nefi. This enables a detailed numerical study, yielding a catalogue of characterizing observables spanning a wide array of different graph properties. To share our results and data, i.e. raw experimental data, graphs and analysis results, we introduce a dedicated repository revolving around slime mold data, the Smgr. The purpose of this repository is to promote data reuse and to foster a practice of increased data sharing. Finally we present a model based on interacting electronic circuits including current controlled voltage sources, which mimics the emergent flow patterns observed in live P. polycephalum. The model is simple, distributed and robust to changes in the underlying network topology. Thus it constitutes a promising basis for the development of distributed natural computing algorithms.

The evolution of search from keywords to entities has necessitated the efficient harvesting and management of entity-centric information for constructing knowledge bases catering to various applications such as semantic search, question answering, and information retrieval. The vast amounts of natural language texts available across diverse domains on the Web provide rich sources for discovering facts about named entities such as people, places, and organizations.

A key challenge, in this regard, entails the need for precise identification and disambiguation of entities across documents for extraction of attributes/relations and their proper representation in knowledge bases. Additionally, the applicability of such repositories not only involves the quality and accuracy of the stored information, but also storage management and query processing efficiency. This dissertation aims to tackle the above problems by presenting efficient approaches for entity-centric knowledge
acquisition from texts and its representation in knowledge repositories.

This dissertation presents a robust approach for identifying text phrases pertaining to the same named entity across huge corpora, and their disambiguation to canonical entities present in a knowledge base, by using enriched semantic contexts and link validation encapsulated in a hierarchical clustering framework. This work further presents language and consistency features for classification models to compute the credibility of obtained textual facts, ensuring quality of the extracted information. Finally, an encoding algorithm, using frequent term detection and improved data locality, to represent entities for enhanced knowledge base storage and query performance is presented.

We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.

Two-dimensional, conventional images are gradually losing their hegemony, leaving room for novel formats. Among these, 8 bit images give place to high dynamic range (HDR) image formats, allowing to improve colour gamut and visibility of details in dark and bright areas leading to a more immersive viewing experience. It opens wide opportunities for post-processing, which can be useful for artistic rendering, enhancement of viewing experience or medical applications. Simultaneously, light-field scene representation as well is gaining importance, propelled by the recent reappearance of virtual reality, the improvement of both acquisition techniques, and computational and storage capabilities. Light-field data as well allows to achieve a broad range of effects in post-production: among others, it enables a change of a camera position, an aperture or a focal length. It facilitates object insertions and simplifies visual effects workflow by integrating 3D nature of visual effects with 3D nature of light fields. Content generation is one of the stumbling blocks in these realms. Sensor limitations of a conventional camera do not allow to capture wide dynamic range. This especially is the case for mobile devices, where small sensors are optimised for capturing in high-resolution. The “HDR mode” often encountered on such devices, relies on techniques called “exposure fusion” and allows to partially overcome the limited range of a sensor. The HDR video at the same time remains a challenging problem. We suggest a solution for an HDR video capturing on a mobile device. We analyse dynamic range of motion regions, the regions which are the most prone to reconstruction artefacts, and suggest a real-time exposure selection algorithm. Further, an HDR content visualization task often requires an input to be in absolute values. We address this problem by presenting a calibration algorithm that can be applied to existent imagery and does not require any additional measurement hardware. Finally, as light fields use becomes more common, a key challenge is the ability to edit or modify the appearance of the objects in the light field. To this end, we propose a multidimensional filtering approach in which the specular highlights are filtered in the spatial and angular domains to target a desired increase of the material roughness.

Knowledge Bases are one of the key components of Natural Language Understanding systems. For example, DBpedia, YAGO, and Wikidata capture and organize knowledge about named entities and relations between them, which is often crucial for tasks like Question Answering and Named Entity Disambiguation. While Knowledge Bases have good coverage of prominent entities, they are often limited with respect to relations. The goal of this thesis is to bridge this gap and automatically create lexicons of textual representations of relations, namely relational phrases. The lexicons should contain information about paraphrases, hierarchy, as well as semantic types of arguments of relational phrases. The thesis makes three main contributions. The first contribution addresses disambiguating relational phrases by aligning them with the WordNet dictionary. Moreover, the alignment allows imposing the WordNet hierarchy on the relational phrases. The second contribution proposes a method for graph construction of relations using Probabilistic Graphical Models. In addition, we apply this model to relation paraphrasing. The third contribution presents a method for constructing a lexicon of relational paraphrases with fine-grained semantic typing of arguments. This method is based on information from a multilingual parallel corpus.

Graph is a vital abstract data type that has profound significance in several applications. Because of its versitality, graphs have been adapted into several different forms and one such adaption with many practical applications is the “Labeled Graph”, where vertices and edges are labeled. An enormous research effort has been invested in to the task of managing and querying graphs, yet a lot challenges are left unsolved. In this thesis, we advance the state-of-the-art for the following query models, and propose a distributed solution to process them in an efficient and scalable manner.
• Set Reachability. We formalize and investigate a generalization of the basic notion of reachability, called set reachability. Set reachability deals with finding all reachable pairs for a given source and target sets. We present a non-iterative distributed solution that takes only a single round of communication for any set reachability query. This is achieved by precomputation, replication, and indexing of partial reachabilities among the boundary vertices.
• Basic Graph Patterns (BGP). Supported by majority of query languages, BGP queries are a common mode of querying knowledge graphs, biological datasets, etc. We present a novel distributed architecture that relies on the concepts of asynchronous executions, join-ahead pruning, and a multi-threaded query processing framework to process BGP queries in an efficient and scalable manner.
• Generalized Graph Patterns (GGP). These queries combine the semantics of pattern matching and navigational queries, and are popular in scenarios where the schema of an underlying graph is either unknown or partially known. We present a distributed solution with bimodal indexing layout that individually support efficient processing of BGP queries and navigational queries. Furthermore, we design a unified query optimizer and a processor to efficiently process GGP queries and also in a scalable manner.
To this end, we propose a prototype distributed engine, coined “TriAD” (Triple Asynchronous and Distributed) that supports all the aforementioned query models. We also provide a detailed empirical evaluation of TriAD in comparison to several state-of-the-art systems over multiple real-world and synthetic datasets.

Markov Decision Processes (MDPs) constitute a mathematical framework for modelling systems featuring both probabilistic and nondeterministic behaviour. They are widely used to solve sequential decision making problems and applied successfully in operations research, arti?cial intelligence, and stochastic control theory, and have been extended conservatively to the model of probabilistic automata in the context of concurrent probabilistic systems. However, when modeling a physical system they suffer from several limitations. One of the most important is the inherent loss of precision that is introduced by measurement errors and discretization artifacts which necessarily happen due to incomplete knowledge about the system behavior. As a result, the true probability distribution for transitions is in most cases an uncertain value, determined by either external parameters or con?dence intervals. Interval Markov decision processes (IMDPs) generalize classical MDPs by having interval-valued transition probabilities. They provide a powerful modelling tool for probabilistic systems with an additional variation or uncertainty that re?ects the absence of precise knowledge concerning transition probabilities. In this dissertation, we focus on decision algorithms for modelling and performance evaluation of such probabilistic systems leveraging techniques from mathematical optimization. From a modelling viewpoint, we address probabilistic bisimulations to reduce the size of the system models while preserving the logical properties they satisfy. We also discuss the key ingredients to construct systems by composing them out of smaller components running in parallel. Furthermore, we introduce a novel stochastic model, Uncertain weighted Markov Decision Processes (UwMDPs), so as to capture quantities like preferences or priorities in a nondeterministic scenario with uncertainties. This model is close to the model of IMDPs but more convenient to work with in the context of bisimulation minimization. From a performance evaluation perspective, we consider the problem of multi-objective robust strategy synthesis for IMDPs, where the aim is to ?nd a robust strategy that guarantees the satisfaction of multiple properties at the same time in face of the transition probability uncertainty. In this respect, we discuss the computational complexity of the problem and present a value iteration-based decision algorithm to approximate the Pareto set of achievable optimal points. Moreover, we consider the problem of computing maximal/minimal reward-bounded reachability probabilities on UwMDPs, for which we present an ef?cient algorithm running in pseudo-polynomial time. We demonstrate the practical effectiveness of our proposed approaches by applying them to a collection of real-world case studies using several prototypical tools.

Visual object detection has seen substantial improvements during the last years due to the possibilities enabled by deep learning. While research on image classification provides continuous progress on how to learn image representations and classifiers jointly, object detection research focuses on identifying how to properly use deep learning technology to effectively localise objects. In this thesis, we analyse and improve different aspects of the commonly used detection pipeline. We analyse ten years of research on pedestrian detection and find that improvement of feature representations was the driving factor. Motivated by this finding, we adapt an end-to-end learned detector architecture from general object detection to pedestrian detection. Our deep network outperforms all previous neural networks for pedestrian detection by a large margin, even without using additional training data. After substantial improvements on pedestrian detection in recent years, we investigate the gap between human performance and state-of-the-art pedestrian detectors. We find that pedestrian detectors still have a long way to go before they reach human performance, and we diagnose failure modes of several top performing detectors, giving direction to future research. As a side-effect we publish new, better localised annotations for the Caltech pedestrian benchmark. We analyse detection proposals as a preprocessing step for object detectors. We establish different metrics and compare a wide range of methods according to these metrics. By examining the relationship between localisation of proposals and final object detection performance, we define and experimentally verify a metric that can be used as a proxy for detector performance. Furthermore, we address a structural weakness of virtually all object detection pipelines: non-maximum suppression. We analyse why it is necessary and what the shortcomings of the most common approach are. To address these problems, we present work to overcome these shortcomings and to replace typical non-maximum suppression with a learnable alternative. The introduced paradigm paves the way to true end-to-end learning of object detectors without any post-processing. In summary, this thesis provides analyses of recent pedestrian detectors and detection proposals, improves pedestrian detection by employing deep neural networks, and presents a viable alternative to traditional non-maximum suppression.

An information retrieval (IR) system assists people in consuming huge amount of data, where the evaluation and the construction of such systems are important. However, there exist two difficulties: the overwhelmingly large number of query-document pairs to judge, making IR evaluation a manually laborious task; and the complicated patterns to model due to the non-symmetric, heterogeneous relationships between a query-document pair, where different interaction patterns such as term dependency and proximity have been demonstrated to be useful, yet are non-trivial for a single IR model to encode. In this thesis we attempt to address both difficulties from the perspectives of IR evaluation and of the retrieval model respectively, by reducing the manual cost with automatic methods, by investigating the usage of crowdsourcing in collecting preference judgments, and by proposing novel neural retrieval models. In particular, to address the large number of query-document pairs in IR evaluation, a low-cost selective labeling method is proposed to pick out a small subset of representative documents for manual judgments in favor of the follow-up prediction for the remaining query-document pairs; furthermore, a language-model based cascade measure framework is developed to evaluate the novelty and diversity, utilizing the content of the labeled documents to mitigate incomplete labels. In addition, we also attempt to make the preference judgments practically usable by empirically investigating different properties of the judgments when collected via crowdsourcing; and by proposing a novel judgment mechanism, making a compromise between the judgment quality and the number of judgments. Finally, to model different complicated patterns in a single retrieval model, inspired by the recent advances in deep learning, we develop novel neural IR models to incorporate different patterns like term dependency, query proximity, density of relevance, and query coverage in a single model. We demonstrate their superior performances through evaluations on different datasets.

In this thesis, we investigate a certain type of local similarities between geometric shapes. We analyze the surface of a shape and find all points that are contained inside identical, spherical neighborhoods of a radius r. This allows us to decompose surfaces into canonical sets of building blocks, which we call microtiles. We show that the microtiles of a given object can be used to describe a complete family of related shapes. Each of these shapes is locally similar to the original, meaning that it contains identical r-neighborhoods, but can have completely different global structure. This allows for using r-microtiling for inverse modeling of shape variations and we develop a method for shape decomposi
tion into rigid, 3D manufacturable building blocks that can be used to physically assemble shape collections. We obtain a small set of constructor pieces that are well suited for manufacturing and assembly by a novel method for tiling grammar simplification: We consider the connection between microtiles and noncontext-free tiling grammars and optimize a graph-based representation, finding a good balance between expressiveness, simplicity and ease of assembly. By changing the objective function, we can re-purpose the grammar simplification method for mesh compression. The microtiles of a model encode its geometrically redundant parts, which can be used for creating shape representations with minimal memory footprints. Altogether, with this work we attempt to give insights into how rigid partial symmetries can be efficiently computed and used in the context of inverse modeling of shape families, shape understanding, and compression.

Much progress has been made in image and video segmentation
over the last years. To a large extent, the success can be attributed to
the strong appearance models completely learned from data, in particular
using deep learning methods. However,to perform best these methods require
large representative datasets for training with expensive pixel-level
annotations, which in case of videos are prohibitive to obtain. Therefore,
there is a need to relax this constraint and to consider alternative forms
of supervision, which are easier and cheaper to collect. In this thesis,
we aim to develop algorithms for learning to segment in images and videos
with different levels of supervision.
First, we develop approaches for training convolutional networks with weaker
forms of supervision, such as bounding boxes or image labels, for object
boundary estimation and semantic/instance labelling tasks. We propose to
generate pixel-level approximate groundtruth from these weaker forms of
annotations to train a network, which allows to achieve high-quality
results comparable to the full supervision quality without any
modifications of the network architecture or the training procedure.
Second, we address the problem of the excessive computational and memory
costs inherent to solving video segmentation via graphs. We propose
approaches to improve the runtime and memory efficiency as well as the
output segmentation quality by learning from the available training data
the best representation of the graph. In particular, we contribute with
learning must-link constraints, the topology and edge weights of the graph
as well as enhancing the graph nodes - superpixels - themselves.
Third, we tackle the task of pixel-level object tracking and address the
problem of the limited amount of densely annotated video data for training
convolutional networks. We introduce an architecture which allows training
with static images only and propose an elaborate data synthesis scheme
which creates a large number of training examples close to the target
domain from the given first frame mask. With the proposed techniques we
show that densely annotated consequent video data is not necessary to
achieve high-quality temporally coherent video segmentationresults.
In summary, this thesis advances the state of the art in weakly supervised
image segmentation, graph-based video segmentation and pixel-level object
tracking and contributes with the new ways of training convolutional
networks with a limited amount of pixel-level annotated training data.