Institutes
Refine
Year of publication
Document Type
- Doctoral Thesis (91)
- Article (54)
- Bachelor Thesis (17)
- Book (13)
- Master's Thesis (10)
- Conference Proceeding (4)
- Contribution to a Periodical (4)
- Habilitation (2)
- Preprint (2)
- Diploma Thesis (1)
Has Fulltext
- yes (198)
Is part of the Bibliography
- no (198)
Keywords
- Machine Learning (5)
- NLP (4)
- ALICE (3)
- Annotation (3)
- Text2Scene (3)
- TextAnnotator (3)
- Virtual Reality (3)
- mathematics education (3)
- Artificial intelligence (2)
- Blockchain (2)
Institute
The recognition of pharmacological substances, compounds and proteins is an essential preliminary work for the recognition of relations between chemicals and other biomedically relevant units. In this paper, we describe an approach to Task 1 of the PharmaCoNER Challenge, which involves the recognition of mentions of chemicals and drugs in Spanish medical texts. We train a state-of-the-art BiLSTM-CRF sequence tagger with stacked Pooled Contextualized Embeddings, word and sub-word embeddings using the open-source framework FLAIR. We present a new corpus composed of articles and papers from Spanish health science journals, termed the Spanish Health Corpus, and use it to train domain-specific embeddings which we incorporate in our model training. We achieve a result of 89.76% F1-score using pre-trained embeddings and are able to improve these results to 90.52% F1-score using specialized embeddings.
Tasks are a key resource in the process of teaching and learning mathematics, which is why task design continues to be one of the main research issues in mathematics education. Different settings can influence the principles underlying the formulation of tasks, and so does the outdoor context. Specifically, a math trail can be a privileged context, known to promote positive attitudes and additional engagement for the learning of mathematics, confronting students with a sequence of real-life tasks, related to a particular mathematical theme. Recently, mobile devices and apps, i.e., MathCityMap, have been recognized as an important resource to facilitate the extension of the classroom to the outdoors. The study reported in this paper intends to identify the principles of design for mobile theme-based math trails (TBT) that result in rich learning experiences in early algebraic thinking. A designed-based research is used, through a qualitative approach, to develop and refine design principles for TBT about Sequences and Patterns. The iterative approach is described by cycles with the intervention of the researchers, pre-service and in-service teachers and students of the targeted school levels. The results are discussed taking into account previous research and data collected along the cycles, conducing to the development of general design principles for TBT tasks.
Despite the great importance of the Latin language in the past, there are relatively few resources available today to develop modern NLP tools for this language. Therefore, the EvaLatin Shared Task for Lemmatization and Part-of-Speech (POS) tagging was published in the LT4HALA workshop. In our work, we dealt with the second EvaLatin task, that is, POS tagging. Since most of the available Latin word embeddings were trained on either few or inaccurate data, we trained several embeddings on better data in the first step. Based on these embeddings, we trained several state-of-the-art taggers and used them as input for an ensemble classifier called LSTMVoter. We were able to achieve the best results for both the cross-genre and the cross-time task (90.64% and 87.00%) without using additional annotated data (closed modality). In the meantime, we further improved the system and achieved even better results (96.91% on classical, 90.87% on cross-genre and 87.35% on cross-time).
Linking mathematics with reality is not new. It is also not new to use outdoor activities to learn mathematics. It seems to be new, to combine such mathematical outdoor activities with mobile technology, like the geocache community which makes use of GPS technology to guide their members to special places and points of interest. The use of mobile technologies to learn at any time and any location is known as “mobile learning”. This type of learning can be seen as an extension of eLearning. Considering the definition of O’Malley one notices that this definition does not exactly match with the idea of the MathCityMap-Project (MCM), because the learning environment in the MCM-Project is predetermined. Combined with the math trail method the project enables mobile learning within math trails with latest technology.In the MCM-Project students experience mathematics at real places and within real situations in out-of-school activities,with help of GPS-enabled smartphones and special math problems. In contrast to the paper versions of math trails we are able to give direct feedback on the solutions by using “mobile devices” such as smartphones or tablets. If the user has difficulties in solving the modeling task, stepped hints can be provided. The teacher is able to use the MCM-Portal to upload tasks developed by himself or by his students and he is also able to build a personal math trail for his students.
Abstract: The human visual cortex enables visual perception through a cascade of hierarchical computations in cortical regions with distinct functionalities. Here, we introduce an AI-driven approach to discover the functional mapping of the visual cortex. We related human brain responses to scene images measured with functional MRI (fMRI) systematically to a diverse set of deep neural networks (DNNs) optimized to perform different scene perception tasks. We found a structured mapping between DNN tasks and brain regions along the ventral and dorsal visual streams. Low-level visual tasks mapped onto early brain regions, 3-dimensional scene perception tasks mapped onto the dorsal stream, and semantic tasks mapped onto the ventral stream. This mapping was of high fidelity, with more than 60% of the explainable variance in nine key regions being explained. Together, our results provide a novel functional mapping of the human visual cortex and demonstrate the power of the computational approach.
Author Summary: Human visual perception is a complex cognitive feat known to be mediated by distinct cortical regions of the brain. However, the exact function of these regions remains unknown, and thus it remains unclear how those regions together orchestrate visual perception. Here, we apply an AI-driven brain mapping approach to reveal visual brain function. This approach integrates multiple artificial deep neural networks trained on a diverse set of functions with functional recordings of the whole human brain. Our results reveal a systematic tiling of visual cortex by mapping regions to particular functions of the deep networks. Together this constitutes a comprehensive account of the functions of the distinct cortical regions of the brain that mediate human visual perception.
The recently introduced Lipschitz–Killing curvature measures on pseudo-Riemannian manifolds satisfy a Weyl principle, i.e. are invariant under isometric embeddings. We show that they are uniquely characterized by this property. We apply this characterization to prove a Künneth-type formula for Lipschitz–Killing curvature measures, and to classify the invariant generalized valuations and curvature measures on all isotropic pseudo-Riemannian space forms.
Die Emergenz digitaler Netzwerke ist auf die ständige Entwicklung und Transformation neuer Informationstechnologien zurückzuführen.
Dieser Strukturwandel führt zu äußerst komplexen Systemen in vielen verschiedenen Lebensbereichen.
Es besteht daher verstärkt die Notwendigkeit, die zugrunde liegenden wesentlichen Eigenschaften von realen Netzwerken zu untersuchen und zu verstehen.
In diesem Zusammenhang wird die Netzwerkanalyse als Mittel für die Untersuchung von Netzwerken herangezogen und stellt beobachtete Strukturen mithilfe mathematischer Modelle dar.
Hierbei, werden in der Regel parametrisierbare Zufallsgraphen verwendet, um eine systematische experimentelle Evaluation von Algorithmen und Datenstrukturen zu ermöglichen.
Angesichts der zunehmenden Menge an Informationen, sind viele Aspekte der Netzwerkanalyse datengesteuert und zur Interpretation auf effiziente Algorithmen angewiesen.
Algorithmische Lösungen müssen daher sowohl die strukturellen Eigenschaften der Eingabe als auch die Besonderheiten der zugrunde liegenden Maschinen, die sie ausführen, sorgfältig berücksichtigen.
Die Generierung und Analyse massiver Netzwerke ist dementsprechend eine anspruchsvolle Aufgabe für sich.
Die vorliegende Arbeit bietet daher algorithmische Lösungen für die Generierung und Analyse massiver Graphen.
Zu diesem Zweck entwickeln wir Algorithmen für das Generieren von Graphen mit vorgegebenen Knotengraden, die Berechnung von Zusammenhangskomponenten massiver Graphen und zertifizierende Grapherkennung für Instanzen, die die Größe des Hauptspeichers überschreiten.
Unsere Algorithmen und Implementierungen sind praktisch effizient für verschiedene Maschinenmodelle und bieten sequentielle, Shared-Memory parallele und/oder I/O-effiziente Lösungen.
Proteins are biological macromolecules playing essential roles in all living organisms.
Proteins often bind with each other forming complexes to fulfill their function. Such protein complexes assemble along an ordered pathway. An assembled protein complex can often be divided into structural and functional modules. Knowing the order of assembly and the modules of a protein complex is important to understand biological processes and treat diseases related to misassembly.
Typical structures of the Protein Data Bank (PDB) contain two to three subunits and a few thousand atoms. Recent developments have led to large protein complexes being resolved. The increasing number and size of the protein complexes demand for computational assistance for the visualization and analysis. One such large protein complex is respiratory complex I accounting for 45 subunits in Homo sapiens.
Complex I is a well understood protein complex that served as case study to validate our methods.
Our aim was to analyze time-resolved Molecular Dynamics (MD) simulation data, identify modules of a protein complex and generate hypotheses for the assembly pathway of a protein complex. For that purpose, we abstracted the topology of protein complexes to Complex Graphs of the Protein Topology Graph Library (PTGL). The subunits are represented as vertices, and spatial contacts as edges. The edges are weighted with the number of contacts based on a distance threshold. This allowed us to apply graph-theoretic methods to visualize and analyze protein complexes.
We extended the implementations of two methods to achieve a computation of Complex Graphs in feasible runtimes. The first method skipped checks for contacts using the information which residues are sequential neighbors. We extended the method to protein complexes and structures containing ligands. The second method introduced spheres encompassing all atoms of a subunit and skipped the check for contacts if the corresponding spheres do not overlap. Both methods combined allowed skipping up to 93 % of the checks for contacts for sample complexes of 40 subunits compared to up to 10 % of the previous implementation. We showed that the runtime of the combined method scaled linearly with the number of atoms compared to a non-linear scaling of the previous implementation We implemented a third method fixing the assignment of an orientation to secondary structure elements. We placed a three-dimensional vector in each secondary structure element and computed the angle between secondary structure elements to assign an orientation. This method sped up the runtime especially for large structures, such as the capsid of human immunodeficiency virus, for which the runtime decreased from 43 to less than 9 hours.
The feasible runtimes allowed us to investigate two data sets of MD trajectories of respiratory complex I of Thermus thermophilus that we received. The data sets differ only by whether ubiquinone is bound to the complex. We implemented a pipeline, PTGLdynamics, to compute the contacts and Complex Graphs for all time steps of the trajectories. We investigated different methods to track changes of contacts during the simulation and created a heat map put onto the three-dimensional structure visualizing the changes. We also created line plots to visualize the changes of contacts over the course of the simulation. Both visualizations helped spotting outstandingly flexible or rigid regions of the structure or time points of the simulation in which major dynamics occur.
We introduced normalizations of the edge weights of Complex Graphs for identi-fying modules and predicting the assembly pathway. The idea is to normalize the number of contacts for the number of residues of a subunit. We defined five different normalizations.
To identify structural and functional modules, we applied the Leiden graph clustering algorithm to the Complex Graphs of respiratory complex I and the respiratory supercomplex. We examined the results for the different normalizations of the weights of the Complex Graphs. The absolute edge weight produced the best result identifying three of four modules that have been defined in the literature for respiratory complex I.
We applied agglomerative hierarchical clustering to the edges of a Complex Graph to create hypotheses of the assembly pathway. The rationale was that subunits with an extensive interface in the final structure assemble early. We tested our method against two existing methods on a data set of 21 proteins with reported assembly pathways. Our prediction outperformed the other methods and ran in feasible runtimes of a few minutes at most.
We also tested our method on respiratory complex I, the respiratory supercomplex and the respiratory megacomplex. We compared the results for the different normalizations with an assembly pathway of respiratory complex I described in the literature. We transformed the assembly pathways to dendrograms and compared the predictions to the reference using the Robinson-Foulds distance and clustering information distance. We analyzed the landscape of the clustering information distance by generating random dendrograms and showed that our result is far better than expected at random. We showed in a detailed analysis that the assembly prediction using one normalization was able to capture key features of the assembly pathway that has been proposed in the literature.
In conclusion, we presented different applications of graph theory to automatically analyze the topology of protein complexes. Our programs run in feasible runtimes even for large complexes. We showed that graph-theoretic modeling of the protein structure can be used to analyze MD simulation data, identify modules of protein complexes and predict assembly pathways.
In the human brain, the incoming light to the retina is transformed into meaningful representations that allow us to interact with the world. In a similar vein, the RGB pixel values are transformed by a deep neural network (DNN) into meaningful representations relevant to solving a computer vision task it was trained for. Therefore, in my research, I aim to reveal insights into the visual representations in the human visual cortex and DNNs solving vision tasks.
In the previous decade, DNNs have emerged as the state-of-the-art models for predicting neural responses in the human and monkey visual cortex. Research has shown that training on a task related to a brain region’s function leads to better predictivity than a randomly initialized network. Based on this observation, we proposed that we can use DNNs trained on different computer vision tasks to identify functional mapping of the human visual cortex.
To validate our proposed idea, we first investigate a brain region occipital place area (OPA) using DNNs trained on scene parsing task and scene classification task. From the previous investigations about OPA’s functions, we knew that it encodes navigational affordances that require spatial information about the scene. Therefore, we hypothesized that OPA’s representation should be closer to a scene parsing model than a scene classification model as the scene parsing task explicitly requires spatial information about the scene. Our results showed that scene parsing models had representation closer to OPA than scene classification models thus validating our approach.
We then selected multiple DNNs performing a wide range of computer vision tasks ranging from low-level tasks such as edge detection, 3D tasks such as surface normals, and semantic tasks such as semantic segmentation. We compared the representations of these DNNs with all the regions in the visual cortex, thus revealing the functional representations of different regions of the visual cortex. Our results highly converged with previous investigations of these brain regions validating the feasibility of the proposed approach in finding functional representations of the human brain. Our results also provided new insights into underinvestigated brain regions that can serve as starting hypotheses and promote further investigation into those brain regions.
We applied the same approach to find representational insights about the DNNs. A DNN usually consists of multiple layers with each layer performing a computation leading to the final layer that performs prediction for a given task. Training on different tasks could lead to very different representations. Therefore, we first investigate at which stage does the representation in DNNs trained on different tasks starts to differ. We further investigate if the DNNs trained on similar tasks lead to similar representations and on dissimilar tasks lead to more dissimilar representations. We selected the same set of DNNs used in the previous work that were trained on the Taskonomy dataset on a diverse range of 2D, 3D and semantic tasks. Then, given a DNN trained on a particular task, we compared the representation of multiple layers to corresponding layers in other DNNs. From this analysis, we aimed to reveal where in the network architecture task-specific representation is prominent. We found that task specificity increases as we go deeper into the DNN architecture and similar tasks start to cluster in groups. We found that the grouping we found using representational similarity was highly correlated with grouping based on transfer learning thus creating an interesting application of the approach to model selection in transfer learning.
During previous works, several new measures were introduced to compare DNN representations. So, we identified the commonalities in different measures and unified different measures into a single framework referred to as duality diagram similarity. This work opens up new possibilities for similarity measures to understand DNN representations. While demonstrating a much higher correlation with transfer learning than previous state-of-the-art measures we extend it to understanding layer-wise representations of models trained on the Imagenet and Places dataset using different tasks and demonstrate its applicability to layer selection for transfer learning.
In all the previous works, we used the task-specific DNN representations to understand the representations in the human visual cortex and other DNNs. We were able to interpret our findings in terms of computer vision tasks such as edge detection, semantic segmentation, depth estimation, etc. however we were not able to map the representations to human interpretable concepts. Therefore in our most recent work, we developed a new method that associates individual artificial neurons with human interpretable concepts.
Overall, the works in this thesis revealed new insights into the representation of the visual cortex and DNNs...
A convex body is unconditional if it is symmetric with respect to reflections in all coordinate hyperplanes. We investigate unconditional lattice polytopes with respect to geometric, combinatorial, and algebraic properties. In particular, we characterize unconditional reflexive polytopes in terms of perfect graphs. As a prime example, we study the signed Birkhoff polytope. Moreover, we derive constructions for Gale-dual pairs of polytopes and we explicitly describe Gröbner bases for unconditional reflexive polytopes coming from partially ordered sets.
Collaboration is an important 21st Century skill. Co-located (or face-to-face) collaboration (CC) analytics gained momentum with the advent of sensor technology. Most of these works have used the audio modality to detect the quality of CC. The CC quality can be detected from simple indicators of collaboration such as total speaking time or complex indicators like synchrony in the rise and fall of the average pitch. Most studies in the past focused on “how group members talk” (i.e., spectral, temporal features of audio like pitch) and not “what they talk”. The “what” of the conversations is more overt contrary to the “how” of the conversations. Very few studies studied “what” group members talk about, and these studies were lab based showing a representative overview of specific words as topic clusters instead of analysing the richness of the content of the conversations by understanding the linkage between these words. To overcome this, we made a starting step in this technical paper based on field trials to prototype a tool to move towards automatic collaboration analytics. We designed a technical setup to collect, process and visualize audio data automatically. The data collection took place while a board game was played among the university staff with pre-assigned roles to create awareness of the connection between learning analytics and learning design. We not only did a word-level analysis of the conversations, but also analysed the richness of these conversations by visualizing the strength of the linkage between these words and phrases interactively. In this visualization, we used a network graph to visualize turn taking exchange between different roles along with the word-level and phrase-level analysis. We also used centrality measures to understand the network graph further based on how much words have hold over the network of words and how influential are certain words. Finally, we found that this approach had certain limitations in terms of automation in speaker diarization (i.e., who spoke when) and text data pre-processing. Therefore, we concluded that even though the technical setup was partially automated, it is a way forward to understand the richness of the conversations between different roles and makes a significant step towards automatic collaboration analytics.
People can describe spatial scenes with language and, vice versa, create images based on linguistic descriptions. However, current systems do not even come close to matching the complexity of humans when it comes to reconstructing a scene from a given text. Even the ever-advancing development of better and better Transformer-based models has not been able to achieve this so far. This task, the automatic generation of a 3D scene based on an input text, is called text-to-3D scene generation. The key challenge, and focus of this dissertation, now relate to the following topics:
(a) Analyses of how well current language models understand spatial information, how static embeddings compare, and whether they can be improved by anaphora resolution.
(b) Automated resource generation for context expansion and grounding that can help in the creation of realistic scenes.
(c) Creation of a VR-based text-to-3D scene system that can be used as an annotation and active-learning environment, but can also be easily extended in a modular way with additional features to solve more contexts in the future.
(d) Analyze existing practices and tools for digital and virtual teaching, learning, and collaboration, as well as the conditions and strategies in the context of VR.
In the first part of this work, we could show that static word embeddings do not benefit significantly from pronoun substitution. We explain this result by the loss of contextual information, the reduction in the relative occurrence of rare words, and the absence of pronouns to be substituted. But we were able to we have shown that both static and contextualizing language models appear to encode object knowledge, but require a sophisticated apparatus to retrieve it. The models themselves in combination with the measures differ greatly in terms of the amount of knowledge they allow to extract.
Classifier-based variants perform significantly better than the unsupervised methods from bias research, but this is also due to overfitting. The resources generated for this evaluation are later also an important component of point three.
In the second part, we present AffordanceUPT, a modularization of UPT trained on the HICO-DET dataset, which we have extended with Gibsonien/telic annotations. We then show that AffordanceUPT can effectively make the Gibsonian/telic distinction and that the model learns other correlations in the data to make such distinctions (e.g., the presence of hands in the image) that have important implications for grounding images to language.
The third part first presents a VR project to support spatial annotation respectively IsoSpace. The direct spatial visualization and the immediate interaction with the 3D objects should make the labeling more intuitive and thus easier. The project will later be incorporated as part of the Semantic Scene Builder (SeSB). The project itself in turn relies on the Text2SceneVR presented here for generating spatial hypertext, which in turn is based on the VAnnotatoR. Finally, we introduce Semantic Scene Builder (SeSB), a VR-based text-to-3D scene framework using Semantic Annotation Framework (SemAF) as a scheme for annotating semantic relations. It integrates a wide range of tools and resources by utilizing SemAF and UIMA as a unified data structure to generate 3D scenes from textual descriptions and also supports annotations. When evaluating SeSB against another state-of-the-art tool, it was found that our approach not only performed better, but also allowed us to model a wider variety of scenes. The final part reviews existing practices and tools for digital and virtual teaching, learning, and collaboration, as well as the conditions and strategies needed to make the most of technological opportunities in the future.
Die vorliegende Arbeit beschäftigt sich mit dem Thema Stemmatologie, d.h. primär der Rekonstruktion der Kopiergeschichte handschriftlich fixierter Dokumente. Zentrales Objekt der Stemmatologie ist das Stemma, eine visuelle Darstellung der Kopiergeschichte, welche i.d.R. graphtheoretisch als Baum bzw. gerichteter azyklischer Graph vorliegt, wobei die Knoten Textzeugen (d.s. die Textvarianten) darstellen während die Kanten für einzelne Kopierprozesse stehen. Im Mittelpunkt des Wissenschaftszweiges steht die Frage des Autorenoriginals (falls ein einziges solches existiert haben sollte) und die Frage der Rekonstruktion seines Textes. Das Stemma selbst ist ein Mittel zu diesem Hauptzweck (Cameron 1987). Der durch für manuelle Kopierprozesse kennzeichnende Abweichungen zunehmend abgewandelte Originaltext ist meist nicht direkt überliefert. Ziel der Arbeit ist es, die semi-automatische Stemmatologie umfassend zu beschreiben und durch Tools und analytische Verfahren weiterzuentwickeln. Der erste Teil der Arbeit beschreibt die Geschichte der computer-assistierten Stemmatologie inkl. ihrer klassischen Vorläufer und mündet in der Vorstellung eines einfachen Tools zur dynamischen graphischen Darstellung von Stemmata. Ein Exkurs zum philologischen Leitphänomen Lectio difficilior erörtert dessen mögliche psycholinguistische Ursachen im schnelleren lexikalischen Zugriff auf hochfrequente Lexeme. Im zweiten Teil wird daraufhin die existenziellste aller stemmatologischen Debatten, initiiert durch Joseph Bédier, mit mathematischen Argumenten auf Basis eines von Paul Maas 1937 vorgeschlagenen stemmatischen Models beleuchtet. Des Weiteren simuliert der Autor in diesem Kapitel Stemmata, um den potenziellen Einfluss der Distribution an Kopierhäufigkeiten pro Manuskript abzuschätzen.
Im nächsten Teil stellt der Autor ein eigens erstelltes Korpus in persischer Sprache vor, welches ebenso wie 3 der bekannten artifiziellen Korpora (Parzival, Notre Besoin, Heinrichi) qualitativ untersucht wird. Schließlich wird mit der Multi Modal Distance eine Methode zur Stemmagenerierung angewandt, welche auf externen Daten psycholinguistisch determinierter Buchstabenverwechslungswahrscheinlichkeiten beruht. Im letzten Teil arbeitet der Autor mit minimalen Spannbäumen zur Stemmaerzeugung, wobei eine vergleichende Studie zu 4 Methoden der Distanzmatrixgenerierung mit 4 Methoden zur Stemmaerzeugung durchgeführt, evaluiert und diskutiert wird.
The 𝒮-cone provides a common framework for cones of polynomials or exponen- tial sums which establish non-negativity upon the arithmetic-geometric inequality, in particular for sums of non-negative circuit polynomials (SONC) or sums of arithmetic- geometric exponentials (SAGE). In this paper, we study the S-cone and its dual from the viewpoint of second-order representability. Extending results of Averkov and of Wang and Magron on the primal SONC cone, we provide explicit generalized second- order descriptions for rational S-cones and their duals.
The sketch map tool facilitates the assessment of OpenStreetMap data for participatory mapping
(2021)
A worldwide increase in the number of people and areas affected by disasters has led to more and more approaches that focus on the integration of local knowledge into disaster risk reduction processes. The research at hand shows a method for formalizing this local knowledge via sketch maps in the context of flooding. The Sketch Map Tool enables not only the visualization of this local knowledge and analyses of OpenStreetMap data quality but also the communication of the results of these analyses in an understandable way. Since the tool will be open-source and several analyses are made automatically, the tool also offers a method for local governments in areas where historic data or financial means for flood mitigation are limited. Example analyses for two cities in Brazil show the functionalities of the tool and allow the evaluation of its applicability. Results depict that the fitness-for-purpose analysis of the OpenStreetMap data reveals promising results to identify whether the sketch map approach can be used in a certain area or if citizens might have problems with marking their flood experiences. In this way, an intrinsic quality analysis is incorporated into a participatory mapping approach. Additionally, different paper formats offered for printing enable not only individual mapping but also group mapping. Future work will focus on advancing the automation of all steps of the tool to allow members of local governments without specific technical knowledge to apply the Sketch Map Tool for their own study areas.
The $p$-adic section conjecture predicts that for a smooth, proper, hyperbolic curve $X$ over a $p$-adic field $k$, every section of the map of étale fundamental groups $\pi_1(X) \to G_k$ is induced by a unique $k$-rational point of $X$. While this conjecture is still open, the birational variant in which $X$ is replaced by its generic point is known due to Koenigsmann. Generalising an alternative proof of Pop, we extend this result to certain localisations of $X$ at a set of closed points $S$, an intermediate version in between the full section conjecture and its birational variant. As one application, we prove the section conjecture for $X_S$ whenever $S$ is a countable set of closed points.
For an abeloid variety A over a complete algebraically closed field extension K of Qp, we construct a p-adic Corlette–Simpson correspondence, namely an equivalence between finite-dimensional continuous K-linear representations of the Tate module and a certain subcategory of the Higgs bundles on A. To do so, our central object of study is the category of vector bundles for the v-topology on the diamond associated to A. We prove that any pro-finite-étale v-vector bundle can be built from pro-finite-étale v-line bundles and unipotent v-bundles. To describe the latter, we extend the theory of universal vector extensions to the v-topology and use this to generalise a result of Brion by relating unipotent v-bundles on abeloids to representations of vector groups.
We show that throughout the satisfiable phase the normalized number of satisfying assignments of a random 2-SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to “true” under a uniformly random satisfying assignment.
The present paper is concerned with the half-space Dirichlet problem [...] where ℝ𝑁+:={𝑥∈ℝ𝑁:𝑥𝑁>0} for some 𝑁≥1 and 𝑝>1, 𝑐>0 are constants. We analyse the existence, non-existence and multiplicity of bounded positive solutions to (𝑃𝑐). We prove that the existence and multiplicity of bounded positive solutions to (𝑃𝑐) depend in a striking way on the value of 𝑐>0 and also on the dimension N. We find an explicit number 𝑐𝑝∈(1,𝑒√), depending only on p, which determines the threshold between existence and non-existence. In particular, in dimensions 𝑁≥2, we prove that, for 0<𝑐<𝑐𝑝, problem (𝑃𝑐) admits infinitely many bounded positive solutions, whereas, for 𝑐>𝑐𝑝, there are no bounded positive solutions to (𝑃𝑐).
The novel coronavirus (SARS-CoV-2), identified in China at the end of December 2019 and causing the disease COVID-19, has meanwhile led to outbreaks all over the globe with about 2.2 million confirmed cases and more than 150,000 deaths as of April 17, 2020 [37]. In view of most recent information on testing activity [32], we present here an update of our initial work [4]. In this work, mathematical models have been developed to study the spread of COVID-19 among the population in Germany and to asses the impact of non-pharmaceutical interventions. Systems of differential equations of SEIR type are extended here to account for undetected infections, as well as for stages of infections and age groups. The models are calibrated on data until April 5, data from April 6 to 14 are used for model validation. We simulate different possible strategies for the mitigation of the current outbreak, slowing down the spread of the virus and thus reducing the peak in daily diagnosed cases, the demand for hospitalization or intensive care units admissions, and eventually the number of fatalities. Our results suggest that a partial (and gradual) lifting of introduced control measures could soon be possible if accompanied by further increased testing activity, strict isolation of detected cases and reduced contact to risk groups.
The World Wide Web is increasing the number of freely accessible textual data, which has led to an increasing interest in research in the field of computational linguistics (CL). This area of research addresses theoretical research to answer the question of how language and knowledge must be represented in order to understand and produce language. For this purpose, mathematical models are being developed to capture the phenomena at various levels in human languages. Another field of research experiencing an increase in interest that is closely related to CL is Natural Language Processing (NLP), which is primarily concerned with developing effective and efficient data structures and algorithms that implement the mathematical models of CL.
With increasing interest in these areas, NLP tools are rapidly and frequently being developed incorporating different CL models to handle different levels of language. The open source trend has benefited all those in the scientific community who develop and use these tools. Due to yet undefined I/O standards for NLP, however, the rapid growth leads to a heterogeneous NLP landscape in which the specializations of the tools cannot benefit from each other because of interface incompatibility. In addition, the constantly growing amount of freely accessible text data requires a high-performance processing solution. This performance can be achieved by horizontal and vertical scaling of hardware and software. For these reasons the first part of this thesis deals with the homogenization of the NLP tool landscape, which is achieved by a standardized framework called TextImager. It is a cloud computing based multi-service, multi-server, multi-pipeline, multi-database, multi-user, multi-representation and multi-visual framework that already provides a variety of tools for various languages to process various levels of linguistic complexity. This makes it possible to answer research questions that require the processing of a large amount of data at several linguistic levels.
The integrated tools and the homogenized I/O data streams of the TextImager make it possible to combine the built-in tools in two dimensions: (1) the horizontal dimension to achieve NLP task-specific improvement (2) the orthogonal dimension to implement CL models that are based on multiple linguistic levels and thus rely on a combination of different NLP tools. The second part of this thesis therefore deals with the creation of models for the horizontal combination of tools in order to show the possibilities for improvement using the example of the NLP task of Named Entity Recognition (NER). The TextImager offers several tools for each NLP task, most of which have been trained on the same training basis, but can produce different results. This means that each of the tools processes a subset of the data correctly and at the same time makes errors in another subset. In order to process as large a subset of the data as possible correctly, a horizontal combination of tools is therefore required. Machine learning-based voting mechanisms called LSTMVoter and CRFVoter were developed for this purpose, which allow a combination of the outputs of individual NLP tools so that better partial data results can be achieved. In this thesis the benefit of Voter is shown using the example of the NER task, whose results flow
back into the TextImager tool landscape.
The third part of this thesis deals with the orthogonal combination of TextImager tools to accomplish the verb sense disambiguation (VSD). The CL question is investigated, how verb senses should be modelled in order to disambiguate them computatively. Verbsenses have a syntagmatic-paradigmatic relationship with surrounding words. Therefore, preprocessing on several linguistic levels and consequently an orthogonal combination of NLP tools is required to disambiguate verbs on a computational level. With TextImager’s integrated NLP landscape, it is now possible to perform these preprocessing steps to induce the information needed for the VSD. The newly developed NLP tool for the VSD has been integrated into the TextImager tool landscape, enabling the analysis of a further linguistic level.
This thesis presents a framework that homogenizes the NLP tool landscape in a cluster-based way. Methods for combining the integrated tools are implemented to improve the analysis of a specific linguistic level or to develop tools that open up new linguistic levels.
The annotation of texts and other material in the field of digital humanities and Natural Language Processing (NLP) is a common task of research projects. At the same time, the annotation of corpora is certainly the most time- and cost-intensive component in research projects and often requires a high level of expertise according to the research interest. However, for the annotation of texts, a wide range of tools is available, both for automatic and manual annotation. Since the automatic pre-processing methods are not error-free and there is an increasing demand for the generation of training data, also with regard to machine learning, suitable annotation tools are required. This paper defines criteria of flexibility and efficiency of complex annotations for the assessment of existing annotation tools. To extend this list of tools, the paper describes TextAnnotator, a browser-based, multi-annotation system, which has been developed to perform platform-independent multimodal annotations and annotate complex textual structures. The paper illustrates the current state of development of TextAnnotator and demonstrates its ability to evaluate annotation quality (inter-annotator agreement) at runtime. In addition, it will be shown how annotations of different users can be performed simultaneously and collaboratively on the same document from different platforms using UIMA as the basis for annotation.
Ein aktuelles Forschungsthema ist die automatische Generierung von 3D-Szenen ausgehend von Beschreibungen in natürlicher Sprache. S.g. Text2Scene-Anwendungen sollen Objekte und räumliche Relationen in einer Texteingabe identifizieren und mit 3D-Modellen eine visuelle Repräsentation der Beschreibung konstruieren. Bisherige Ansätze kombinieren eine
stichwortbasierte Erkennung von explizit gemachten Angaben mit vorher gelerntem Allgemeinwissen über die sinnvolle Anordnung von Objekten. Den Anwendungen fehlt jedoch ein tiefergehendes Verständnis von räumlicher Sprache.
Mit dem Annotationsschema ISOSpace können Texte mit detaillierten räumlichen Informationen angereichert und so für NLP-Anwendungen verständlicher gemacht werden. Bereits in einer früheren Arbeit wurde der SemAF-Annotator zum Erstellen von ISOSpaceAnnotationen als Modul für den TextAnnotator entwickelt. In dieser Arbeit wurde der SemAF-Annotator zusätzlich um eine Funktionalität zur Szenenerstellung erweitert: Benutzer können einzelnen Wörtern in der Weboberfläche des TextAnnotators Objekte aus dem ShapeNet Datensatz zuordnen und diese in einer zweidimensionalen Darstellung einer Szene räumlich anordnen. Trotz einiger Einschränkungen durch die fehlende dritte Dimension lassen sich in vielen Fällen gute Ergebnisse erzielen. Die auf diese Weise erzeugten Szenen sollen später in Kombination mit den ISOSpace-Annotionen verwendet werden, um Text2SceneAnwendungen zu entwickeln, die ein umfassenderes räumliches Verständnis aufweisen.
Kleinere Nebenaufgaben dieser Arbeit waren die Erweiterung des SemAF-Annotators um zusätzliche Annotationstypen sowie diverse Nachbesserungen der bereits bestehenden Funktionalität zur ISOSpace Annotation.
Die folgende Arbeit handelt von einer Text2Scene Anwendung, welche in der Virtual Reality (VR) umgesetzt wurde. Das System ermöglicht es den Usern aus einer Beschreibung einer Szene, diese virtuell nachzustellen. Dies bietet eine neue Art der Interaktion mit einem Text, die die visuelle Komponente hervorhebt und somit eine Geschichte auf neue Wege erfahrbar macht.
Dazu kann der User einen fertigen Text entweder vom Server zu laden oder einen eigenen erstellen, der dann automatisch verarbeitet wird. Dabei werden die vorhanden physischen Objekte im Text automatisch erkannt und dem User als 3D-Objekte in der virtuellen Umgebung zur Verfügung gestellt. Diese können dann manuell platziert werden und erzeugen dadurch die Szene, die im Ausgangstext beschrieben wurde. Das Ziel der Textverarbeitung ist eine möglichst genaue Beschreibung der Objekte, damit diese zielgerichtet in der Objektdatenbank gesucht werden können.
Bei der Textverarbeitung wird besonderer Wert auf das Erkennen von Teil-Ganz Beziehungen gelegt. Sodass Objekte, die im Text vorkommen und ein Holonym besitzen, automatisch mit diesem verknüpft werden. Gleichzeitig wird die Teil-Ganz Beziehung aber auch in die andere Richtung genauer betrachtet. Die Textverarbeitung soll ferner dazu in der Lage sein, Objekte genauer zu spezifizieren und an den Kontext des Textes anzupassen. Weiterhin wurde das Natural Language Processing (NLP) so ausgebaut, dass der Kontext des Textes erkannt wird und die Objekte entsprechend kategorisiert werden. Die Textverarbeitung wird mithilfe eines Neuronalen Netzes implementiert. Die verwendeten Tools zur Erkennung von Teil-Ganz Beziehungen, Kontext und Spezifikation von Objekten wurden anhand von Texteingaben nach der Genauigkeit der Ausgabe evaluiert.
Zur Nutzung der Textverarbeitung wurde eine virtuelle Szene entwickelt, die das Erstellen von eigenen Szenen aus vorher geladenen beziehungsweise eingegebenen Texten ermöglicht.
Dazu kann der Nutzer manuell oder automatisch Objekte laden lassen, die er dann platzieren kann.
In 2020, Germany and Spain experienced lockdowns of their school systems. This resulted in a new challenge for learners and teachers: lessons moved from the classroom to the children’s homes. Therefore, teachers had to set rules, implement procedures and make didactical–methodical decisions regarding how to handle this new situation. In this paper, we focus on the roles of mathematics teachers in Germany and Spain. The article first describes how mathematics lessons were conducted using distance learning. Second, problems encountered throughout this process were examined. Third, teachers drew conclusions from their mathematics teaching experiences during distance learning. To address these research interests, a questionnaire was answered by N = 248 teachers (N1 = 171 German teachers; N2 = 77 Spanish teachers). Resulting from a mixed methods approach, differences between the countries can be observed, e.g., German teachers conducted more lessons asynchronously. In contrast, Spanish teachers used synchronous teaching more frequently, but still regard the lack of personal contact as a main challenge. Finally, for both countries, the digitization of mathematics lessons seems to have been normalized by the pandemic.
We present a symmetry result to solutions of equations involving the fractional Laplacian in a domain with at least two perpendicular symmetries. We show that if the solution is continuous, bounded, and odd in one direction such that it has a fixed sign on one side, then it will be symmetric in the perpendicular direction. Moreover, the solution will be monotonic in the part where it is of fixed sign. In addition, we present also a class of examples in which our result can be applied.
This thesis is concerned with the study of symmetry breaking phenomena for several different semilinear partial differential equations. Roughly speaking, this encompasses equations whose symmetries are not necessarily inherited by their solutions, which is particularly interesting for ground state solutions.
The results of this thesis lie in the area of convex algebraic geometry, which is the intersection of real algebraic geometry, convex geometry, and optimization.
We study sums of nonnegative circuit polynomials (SONC) and their related cone, both geometrically and in application to polynomial optimization. SONC polynomials are certain sparse polynomials having a special structure in terms of their Newton polytopes and supports, and serve as a certificate of nonnegativity for real polynomials, which is independent of sums of squares.
The first part of this thesis is dedicated to the convex geometric study of the SONC cone. As main results we show that the SONC cone is full-dimensional in the cone of nonnegative polynomials, we exactly determine the number of zeros of a nonnegative circuit polynomial, and we give a complete and explicit characterization of the number of zeros of SONC polynomials and forms. Moreover, we provide a first approach to the study of the exposed faces of the SONC cone and their dimensions.
In the second part of the thesis we use SONC polynomials to tackle constrained polynomial optimization problems (CPOPs).
As a first step, we derive a lower bound for the optimal value of CPOP based on SONC polynomials by using a single convex optimization program, which is a geometric program (GP) under certain assumptions. GPs are a special type of convex optimization problems and can be solved in polynomial time. We test the new method experimentally and provide examples comparing our new SONC/GP approach with Lasserre's relaxation, a common approach for tackling CPOPs, which approximates nonnegative polynomials via sums of squares and semidefinite programming (SDP). The new approach comes with the benefit that in practice GPs can be solved significantly faster than SDPs. Furthermore, increasing the degree of a given problem has almost no effect on the runtime of the new program, which is in sharp contrast to SDPs.
As a second step, we establish a hierarchy of efficiently computable lower bounds converging to the optimal value of CPOP based on SONC polynomials. For a given degree each bound is computable by a relative entropy program. This program is also a convex optimization program, which is more general than a geometric program, but still efficiently solvable via interior point methods.
Sublinear circuits are generalizations of the affine circuits in matroid theory, and they arise as the convex-combinatorial core underlying constrained non-negativity certificates of exponential sums and of polynomials based on the arithmetic-geometric inequality. Here, we study the polyhedral combinatorics of sublinear circuits for polyhedral constraint sets. We give results on the relation between the sublinear circuits and their supports and provide necessary as well as sufficient criteria for sublinear circuits. Based on these characterizations, we provide some explicit results and enumerations for two prominent polyhedral cases, namely the non-negative orthant and the cube [− 1,1]n.
Conditional Sums-of-AM/GM-Exponentials (conditional SAGE) is a decomposition method to prove nonnegativity of a signomial or polynomial over some subset X of real space. In this article, we undertake the first structural analysis of conditional SAGE signomials for convex sets X. We introduce the X-circuits of a finite subset A⊂Rn , which generalize the simplicial circuits of the affine-linear matroid induced by A to a constrained setting. The X-circuits serve as the main tool in our analysis and exhibit particularly rich combinatorial properties for polyhedral X, in which case the set of X-circuits is comprised of one-dimensional cones of suitable polyhedral fans. The framework of X-circuits transparently reveals when an X-nonnegative conditional AM/GM-exponential can in fact be further decomposed as a sum of simpler X-nonnegative signomials. We develop a duality theory for X-circuits with connections to geometry of sets that are convex according to the geometric mean. This theory provides an optimal power cone reconstruction of conditional SAGE signomials when X is polyhedral. In conjunction with a notion of reduced X-circuits, the duality theory facilitates a characterization of the extreme rays of conditional SAGE cones. Since signomials under logarithmic variable substitutions give polynomials, our results also have implications for nonnegative polynomials and polynomial optimization.
The thesis deals with the analysis and modeling of point processes emerging from different experiments in neuroscience. In particular, the description and detection of different types of variability changes in point processes is of interest.
A non-stationary rate or variance of life times is a well-known problem in the description of point processes like neuronal spike trains and can affect the results of further analyses requiring stationarity. Moreover, non-stationary parameters might also contain important information themselves. The goal of the first part of the thesis is the (further) development of a technique to detect both rate and variance changes that may occur in multiple time scales separately or simultaneously. A two-step procedure building on the multiple filter test (Messer et al., 2014) is used that first tests the null hypothesis of rate homogeneity allowing for an inhomogeneous variance and that estimates change points in the rate if the null hypothesis is rejected. In the second step, the null hypothesis of variance homogeneity is tested and variance change points are estimated. Rate change points are used as input. The main idea is the comparison of estimated variances in adjacent windows of different sizes sliding over the process. To determine the rejection threshold functionals of the Brownian motion are identified as limit processes under the null of variance homogeneity. The non-parametric procedure is not restricted to the case of at most one change point. It is shown in simulation studies that the corresponding test keeps the asymptotic significance level for a wide range of parameters and that the test power is remarkable. The practical applicability of the procedure is underlined by the analysis of neuronal spike trains.
Point processes resulting from experiments on bistable perception are analyzed in the second part of the thesis. Visual illusions allowing for than more possible perception lead to unpredictable changes of perception. In the thesis data from (Schmack et al., 2015) are used. A rotating sphere with switching perceived rotation direction was presented to the participants of the study. The stimulus was presented continuously and intermittently, i.e., with short periods of „blank display“ between the presentation periods. There are remarkable differences in the response patterns between the two types of presentation. During continuous presentation the distribution of dominance times, i.e., the intervals of constant perception, is a right-skewed and unimodal distribution with a mean of about five seconds. In contrast, during intermittent presentation one observes very long, stable dominance times of more than one minute interchanging with very short, unstable dominance times of less than five seconds, i.e., an increase of variability.
The main goal of the second part is to develop a model for the response patterns to bistable perception that builds a bridge between empirical data analysis and mechanistic modeling. Thus, the model should be able to describe both the response patterns to continuous presentation and to intermittent presentation. Moreover, the model should be fittable to typically short experimental data, and the model should allow for neuronal correlates. Current approaches often use detailed assumptions and large parameter sets, which complicate parameter estimation.
First, a Hidden Markov Model is applied. Second, to allow for neuronal correlates, a Hierarchical Brownian Model (HBM) is introduced, where perception is modeled by the competition of two neuronal populations. The activity difference between these two populations is described by a Brownian motion with drift fluctuating between two borders, where each first hitting time causes a perceptual change. To model the response patterns to intermittent presentation a second layer with competing neuronal populations (coding a stable and an unstable state) is assumed. Again, the data are described very well, and the hypothesis that the relative time in the stable state is identical in a group of patients with schizophrenia and a control group is rejected. To sum up, the HBM intends to link empirical data analysis and mechanistic modeling and provides interesting new hypotheses on potential neuronal mechanisms of cognitive phenomena.
Powerful environment perception systems are a fundamental prerequisite for the successful deployment of intelligent vehicles, from advanced driver assistance systems to self-driving cars. Arguably the most essential task of such systems is the reliable detection and localization of obstacles in order to avoid collisions. Two particularly challenging scenarios in this context are represented by small, unexpected obstacles on the road ahead, and by potentially dynamic objects observed from a large distance. Both scenarios become exceedingly critical when the ego-vehicle is traveling at high speed. As a consequence, two major requirements placed on environment perception systems are the capability of (a) high-sensitivity generic object detection and (b) high-accuracy obstacle distance estimation. The present thesis addresses both requirements by proposing novel approaches based on stereo vision for spatial perception.
First, this work presents a novel method for the detection of small, generic obstacles and objects at long range directly from stereo imagery. The detection is based on sound statistical tests using local geometric criteria which are applicable to both static and moving objects. The approach is not limited to predefined sets of semantic object classes and does not rely on restrictive assumptions on the environment, such as oversimplified global ground surface models. Free-space and obstacle hypotheses are evaluated based on a statistical model of the input image data in order to avoid a loss of sensitivity through intermediate processing steps. In addition to the detection result, the algorithm simultaneously yields refined estimates of object distances, originating from an implicit optimization of the geometric obstacle hypothesis models. The proposed detection system provides multiple flexible output representations, ranging from 3D obstacle point clouds to compact mid-level obstacle segments to bounding box representations of object instances suitable for model-based tracking. The core algorithm concept lends itself to massive parallelization and can be implemented efficiently on dedicated hardware. Real-time execution is demonstrated on a test vehicle in real-world traffic. For a thorough quantitative evaluation of the detection performance, two dedicated datasets are employed, covering small and hard-to-detect obstacles in urban environments as well as distant dynamic objects in highway driving scenarios. The proposed system is shown to significantly outperform current general purpose obstacle detection approaches in both setups, providing a considerable increase in detection range while reducing the false positive rate at the same time.
Second, this work considers the high-accuracy estimation of object distances from stereo vision, particularly at long range. Several new methods for optimizing the stereo-based distance estimates of detected objects are proposed and compared to state-of-the-art concepts. A comprehensive statistical evaluation is performed on an extensive dedicated dataset, establishing reference values for the accuracy limits actually achievable in practice. Notably, the refined distance estimates implicitly provided by the proposed obstacle detection system are shown to yield highly accurate results, on par with the top-performing dedicated stereo matching algorithms considered in the analysis.
Motivated by Gröbner basis theory for finite point configurations, we define and study the class of standard complexes associated to a matroid. Standard complexes are certain subcomplexes of the independence complex that are invariant under matroid duality. For the lexicographic term order, the standard complexes satisfy a deletion-contraction-type recurrence. We explicitly determine the lexicographic standard complexes for lattice path matroids using classical bijective combinatorics.
In this thesis we introduce the imaginary projection of (multivariate) polynomials as the projection of their variety onto its imaginary part, I(f) = { Im(z_1, ... , z_n) : f(z_1, ... , z_n) = 0 }. This induces a geometric viewpoint to stability, since a polynomial f is stable if and only if its imaginary projection does not intersect the positive orthant. Accordingly, the thesis is mainly motivated by the theory of stable polynomials.
Interested in the number and structure of components of the complement of imaginary projections, we show as a key result that there are only finitely many components which are all convex. This offers a connection to the theory of amoebas and coamoebas as well as to the theory of hyperbolic polynomials.
For hyperbolic polynomials, we show that hyperbolicity cones coincide with components of the complement of imaginary projections, which provides a strong structural relationship between these two sets. Based on this, we prove a tight upper bound for the number of hyperbolicity cones and, respectively, for the number of components of the complement in the case of homogeneous polynomials. Beside this, we investigate various aspects of imaginary projections and compute imaginary projections of several classes explicitly.
Finally, we initiate the study of a conic generalization of stability by considering polynomials whose roots have no imaginary part in the interior of a given real, n-dimensional, proper cone K. This appears to be very natural, since many statements known for univariate and multivariate stable polynomials can be transferred to the conic situation, like the Hermite-Biehler Theorem and the Hermite-Kakeya-Obreschkoff Theorem. When considering K to be the cone of positive semidefinite matrices, we prove a criterion for conic stability of determinantal polynomials.
Spin(9)-invariant valuations
(2013)
The first aim of this thesis is to give a Hadwiger-type theorem for the exceptional Lie group Spin(9). The space of Spin(9)-invariant k-homogeneous valuations is studied through the construction of an exact sequence involving some spaces of differential forms. We present then a description of the spin representation using the properties of the 8-dimensional division algebra of the octonions. Using this description as well as representation-theoretic formulas, we can compute the dimensions of the spaces of differential forms appearing in the exact sequence. Hence we obtain the dimensions of the spaces of k-homogeneous Spin(9)-invariant valuations for k=0,1,...,16.
In the second part of this work, we construct one new element for a basis of one of these spaces. It is clear, that the k-th intrinsic volume is also Spin(9)-invariant. The last chapter of this work presents the construction of a new 2-homogeneous Spin(9)-invariant valuation. On a Riemannian manifold (M,g), we construct a valuation by integrating the curvature tensor over the disc bundle. We associate to this valuation on M a family of valuations on the tangent spaces. We show that these valuations are even and homogeneous of degree 2. Moreover, since the valuation on M is invariant under the action of the isometry group of M, the induced valuation on the tangent space in a point p in M is invariant under the action of the stabilisator of p for all p in M. In the special case where M is the octonionic projective plane, this construction yields an even, homogeneous of degree 2, Spin(9)-invariant valuation, whose Klain function is not constant, i.e. which is linearly independent of the second intrinsic volume.
We obtain spectral inequalities and asymptotic formulae for the discrete spectrum of the operator 12log(−Delta) in an open set OmegaERd, d≥2, of finite measure with Dirichlet boundary conditions. We also derive some results regarding lower bounds for the eigenvalue Lambda1(Omega) and compare them with previously known inequalities.
We present new results on nonlocal Dirichlet problems established by means of suitable spectral theoretic and variational methods, taking care of the nonlocal feature of the operators. We mainly address: First, we estimate the Morse index of radially symmetric sign changing bounded weak solutions to a semilinear Dirichlet problem involving the fractional Laplacian. In particular, we derive a conjecture due to Bañuelos and Kulczycki on the geometric structure of the second Dirichlet eigenfunctions. Secondly, we study a small order asymptotics with respect to the parameter s of the Dirichlet eigenvalues problem for the fractional Laplacian. Thirdly, we deal with the logarithmic Schrödinger operator. In particular, we provide an alternative to derive the singular integral representation corresponding to the associated Fourier symbol and introduce tools and functional analytic framework for variational studies. Finaly, we study nonlocal operators of order strictly below one. In particular, we investigate interior regularity properties of weak solutions to the associated Poisson problem depending on the regularity of the right-hand side.
In this thesis, we cover two intimately related objects in combinatorics, namely random constraint satisfaction problems and random matrices. First we solve a classic constraint satisfaction problem, 2-SAT using the graph structure and a message passing algorithm called Belief Propagation. We also explore another message passing algorithm called Warning Propagation and prove a useful result that can be employed to analyze various type of random graphs. In particular, we use this Warning Propagation to study a Bernoulli sparse parity matrix and reveal a unique phase transition regarding replica symmetry. Lastly, we use variational methods and a version of local limit theorem to prove a sufficient condition for a general random matrix to be of full rank.
Embedding spanning structures into the random graph G(n,p) is a well-studied problem in random graph theory, but when one turns to the random r-uniform hypergraph H(r)(n,p) much less is known. In this thesis we will examine this topic from different perspectives, providing insights into various aspects of the theory of random graphs. Our results cover the determination of existence thresholds in two models, as well as an algorithmic approach. For the embeddings, we work with random and pseudorandom structures.
Together with Person we first notice that a general result of Riordan can be adapted from random graphs to hypergraphs and provide sufficient conditions for when H(r)(n,p) contains a given spanning structure asymptotically almost surely. As applications, we discuss several spanning structures such as cubes, lattices, spheres, and Hamilton cycles in hypergraphs.
Moreover, we study universality, i.e. when does an r-uniform hypergraph contain every hypergraph on n vertices with maximum vertex degree bounded by [delta]? For H(r)(n,p), it is shown with Person that this holds for p = w(ln n/n)1/[delta]) asymptotically almost surely by combining approaches taken by Dellamonica, Kohayakawa, Rödl, and Ruciński, of Ferber, Nenadov, and Peter, and of Kim and Lee.
Any hypergraph that is universal for the family of bounded degree r-uniform hypergraphs has to contain [omega](nr-r/[delta]) edges. With Hetterich and Person we exploit constructions of Alon and Capalbo to obtain universal r-uniform hypergraphs with the optimal number of edges O(nr-r/[delta]) when r is even, r | [delta], or [delta] = 2. Furthermore, we generalise the result of Alon and Asodi about optimal universal graphs for the family of graphs with at most m edges and no isolated vertices to hypergraphs.
In an r-uniform hypergraph on n vertices a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. In collaboration with Allen, Koch, and Person we provide a first deterministic polynomial time algorithm, which finds asymptotically almost surely tight Hamilton cycles in random r-uniform hypergraphs with edge probability at least C log3 n/n. This result partially answers a question of Nenadov and Skorić and of Dudek and Frieze who proved that tight Hamilton cycles exist already for p = w(1/n) for r = 3 and p [größer/gleich] (e + o(1))/n for r [größer/gleich] 4 using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa, and Person and Nenadov and Skorić.
Lastly, we study the model of randomly perturbed dense graphs introduced by Bohman, Frieze and Martin, that is, the union of any n-vertex graph G[alpha] with minimum degree at least [alpha]n and G(n,p). For any fixed [alpha] > 0, and p = w(n-2/([delta]+1)), we show with Böttcher, Montgomery, and Person that G[alpha] UG(n,p) almost surely contains any single spanning graph with maximum degree [delta], where [delta] [größer/gleich] 5. As in previous results concerning this model, the bound used for p is lower by a log-term in comparison to the conjectured threshold for the general appearance of such subgraphs in G(n,p) alone. The new techniques we introduce also give simpler proofs of related results in the literature on trees and factors.
Space optimizations in deterministic and concurrent call-by-need functional programming languages
(2020)
In this thesis the space consumption and runtime of lazy-evaluating functional programming languages are analyzed.
The typed and extended lambda-calculi LRP and CHF* as core languages for Haskell and Concurrent Haskell are used. For each LRP and CHF* compatible abstract machines are introduced.
Too lower the distortion of space measurement a classical implementable garbage collector is applied after each LRP reduction step. Die size of expressions and the space measure spmax as maximal size of all garbage-free expressions during an LRP-evaluation, are defined.
Program-Transformations are considered as code-to-code transformations. The notions Space Improvement and Space Equivalence as properties of transformations are defined. A Space Improvement does neither change the semantics nor it increases the needed space consumption, for a space equivalence the space consumption is required to remain the same. Several transformations are shown as Space Improvements and Equivalences.
An abstract machine for space measurements is introduced. An implementation of this machine is used for more complex space- and runtime-analyses.
Total Garbage Collection replaces subexpressions by a non-terminating constant with size zero, if the overall termination is not affected. Thereby the notion of improvement is more independent from the used garbage collector.
Analogous to Space Improvements and Equivalences the notions Total Space Improvement and Total Space Equivalence are defined, which use Total Garbage Collection during the space measurement. Several Total Space Improvements and Equivalences are shown.
Space measures for CHF* are defined, that are compatible to the space measure of LRP. An algorithm with sort-complexity is developed, that calculates the required space of independent processes that all start and end together. If a constant amount of synchronization restrictions is added and a constant number of processors is used, the runtime is polynomial, if arbitrary synchronizations are used, then the problem is NP-complete.
Abstract machines for space- and time-analyses in CHF* are developed and implementations of these are used for space and runtime analyses.
This thesis presents research which spans three conference papers and one manuscript which has not yet been submitted for peer review.
The topic of 1 is the inherent complexity of maintaining perfect height in B-trees. We consider the setting in which a B-tree of optimal height contains n = (1−ϵ)N elements where N is the number of elements in full B-tree of the same height (the capacity of the tree). We show that the rebalancing cost when updating the tree—while maintaining optimal height—depends on ϵ. Specifically, our analysis gives a lower bound for the rebalancing cost of Ω(1/(ϵB)). We then describe a rebalancing algorithm which has an amortized rebalancing cost with an almost matching upper bound of O(1/(ϵB)⋅log²(min{1/ϵ,B})). We additionally describe a scheme utilizing this algorithm which, given a rebalancing budget f(n), maintains optimal height for decreasing ϵ until the cost exceeds the
budget at which time it maintains optimal height plus one. Given a rebalancing budget of Θ(logn), this scheme maintains optimal height for all but a vanishing fraction of sizes in the intervals between tree capacities.
Manuscript 2 presents empirical analysis of practical randomized external-memory algorithms for computing the connected components of graphs. The best known theoretical results for this problem are essentially all derived from results for minimum spanning tree algorithms. In the realm of randomized external-memory MST algorithms, the best asymptotic result has I/O-complexity O(sort(|E|)) in expectation while an empirically studied practical algorithm has a bound of O(sort(|E|)⋅log(|V|/M)). We implement and evaluate an algorithm for connected components with expected I/O-complexity O(sort(|E|))—a simplification of the MST
algorithm with this asymptotic cost, we show that this approach may also yield good results in practice.
In paper 3, we present a novel approach to simulating large-scale population protocol models. Naive simulation of N interactions of a population protocol with n agents and m states requires Θ(nlogm) bits of memory and Θ(N) time. For
very large n, this is prohibitive both in memory consumption and time, as interesting protocols will typically require N > n interactions for convergence. We describe a histogram-based simulation framework which requires Θ(mlogn) bits of memory instead—an improvement as it is typically the case that
n ≫ m. We analyze, implement, and compare a number of different data structures to perform correct agent sampling in this regime. For this purpose, we develop dynamic alias tables which allow sampling an interaction in expected amortized
constant time. We then show how to use sampling techniques to process agent interactions in batches, giving a simulation approach which uses subconstant time per interaction under reasonable assumptions.
With paper 4, we introduce the new model of fragile complexity for comparison-based algorithms. Within this model, we analyze classical comparison-based problems such as finding the minimum value of a set, selection (or finding the median), and sorting. We prove a number of lower and upper bounds and in particular, we give a number of randomized results which describe trade-offs not achievable by deterministic algorithms.
Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming
(2021)
Several applications in medical imaging and non-destructive material testing lead to inverse elliptic coefficient problems, where an unknown coefficient function in an elliptic PDE is to be determined from partial knowledge of its solutions. This is usually a highly non-linear ill-posed inverse problem, for which unique reconstructability results, stability estimates and global convergence of numerical methods are very hard to achieve. The aim of this note is to point out a new connection between inverse coefficient problems and semidefinite programming that may help addressing these challenges. We show that an inverse elliptic Robin transmission problem with finitely many measurements can be equivalently rewritten as a uniquely solvable convex non-linear semidefinite optimization problem. This allows to explicitly estimate the number of measurements that is required to achieve a desired resolution, to derive an error estimate for noisy data, and to overcome the problem of local minima that usually appears in optimization-based approaches for inverse coefficient problems.
Bei der Bekleidungsmodellierung geht es um den Entwurf von Bekleidung von Personen, die beispielsweise in Szenen dargestellt werden können. Dabei stützt sich der Entwurf auf Informationen aus einer Datengrundlage. Die Darstellung von Szenen, in denen Personen dargestellt werden, stellt sich grundsätzlich als Zusammenspiel komplexer Teilaspekte dar. Dabei wird die Nachvollziehbarkeit einer modellierten Szene oder modellierter Avatare im Auge des Betrachters ganz wesentlich durch den Faktor passend gewählter Kleidung bestimmt.
In dieser Arbeit werden Ansätze und Verfahren vorgestellt, die zur Bekleidungsmodellierung auf Grundlage von Textdokumenten basieren. Dafür werden Möglichkeiten erörtert, die es erlauben Informationen aus Texten zu extrahieren und für die Modellierung einzusetzen.
Zur Bearbeitung der Aufgabenstellung wird zunächst ein aus dem Machine Learning bekanntes kontextuelles Modell hinsichtlich einer Mehrklassen-Klassifizierung trainiert und angewendet. Daraufhin wird die Erstellung einer eigenen Wissensressource, die sich auf textlicher Ebene mit dem Thema der Bekleidung auseinandersetzt, aufgebaut und mit zahlreichen Informationen aus bereits bestehenden Ressourcen popularisiert. Die neue Ressource wird in Form einer Graphdatenbank entworfen. Dabei werden Relationen zwischen den einzelnen Elementen mithilfe von statischen Modellen sowie einem kontextuellen Modell, dem BERT-Modell, erstellt. Schließlich wird auf Grundlage der entwickelten Graphdatenbank ein in der Programmiersprache Python entwickeltes Programm vorgestellt, dass Eingabetexte unter Hinzunahme der Informationen und Relationen innerhalb der Graphdatenbank verarbeitet und Kleidungsstücke detektiert.
Nach der theoretischen Aufarbeitung der entwickelten Ansätze werden die daraus resultierenden Ergebnisse diskutiert und bestehende Problematiken bei der Bearbeitung der Aufgabenstellung angesprochen. Abschließend wird die Arbeit zusammengefasst und Anregungen für die weitere Bearbeitung dieser Thematik vorgestellt.
In this paper, we introduce an approach for future frames prediction based on a single input image. Our method is able to generate an entire video sequence based on the information contained in the input frame. We adopt an autoregressive approach in our generation process, i.e., the output from each time step is fed as the input to the next step. Unlike other video prediction methods that use “one shot” generation, our method is able to preserve much more details from the input image, while also capturing the critical pixel-level changes between the frames. We overcome the problem of generation quality degradation by introducing a “complementary mask” module in our architecture, and we show that this allows the model to only focus on the generation of the pixels that need to be changed, and to reuse those that should remain static from its previous frame. We empirically validate our methods against various video prediction models on the UT Dallas Dataset, and show that our approach is able to generate high quality realistic video sequences from one static input image. In addition, we also validate the robustness of our method by testing a pre-trained model on the unseen ADFES facial expression dataset. We also provide qualitative results of our model tested on a human action dataset: The Weizmann Action database.
Due to the resurrection of data-hungry models (such as deep convolutional neural nets), there is an increasing demand for large-scale labeled datasets and benchmarks in the computer vision fields (CV). However, collecting real data across diverse scene contexts along with high-quality annotations is often expensive and time-consuming, especially for detailed pixel-level label prediction tasks such as semantic segmentation, etc. To address the scarcity of real-world training sets, recent works have proposed the use of computer graphics (CG) generated data to train and/or characterize performance of modern CV systems. CG based virtual worlds provide easy access to ground truth annotations and control over scene states. Most of these works utilized training data simulated from video games and pre-designed virtual environments and demonstrated promising results. However, little effort has been devoted to the systematic generation of massive quantities of sufficiently complex synthetic scenes for training scene understanding algorithms. In this work, we develop a full pipeline for simulating large-scale datasets along with per-pixel ground truth information. Our simulation pipeline constitutes of mainly two components: (a) a stochastic scene generative model that automatically synthesizes traffic scene layouts by using marked point processes coupled with 3D CAD objects and factor potentials, (b) an annotated-image rendering tool that renders the sampled 3D scene as RGB image with a chosen rendering method along with pixel-level annotations such as semantic labels, depth, surface normals etc. This pipeline is capable of automatically generating and rendering a potentially infinite variety of outdoor traffic scenes that can be used to train convolutional neural nets (CNN).
However, several recent works, including our own initial experiments demonstrated that the CV models that are trained naively on simulated data lack generalization capabilities to real-world scenes. This opens up several fundamental questions about what is it lacking in simulated data compared to real data and how to use it effectively. Furthermore, there has been a long debate since 1980’s on the usefulness of CG generated data for tuning CV systems. Primarily, the impact of modeling errors and computational rendering approximations, due to various choices in the rendering pipeline, on trained CV systems generalization performance is still not clear. In this thesis, we take a case study in the context of traffic scenarios to empirically analyze the performance degradations when CV systems trained with virtual data are transferred to real data. We first explore system performance tradeoffs due to the choice of the rendering engine (e.g., Lambertian shader (LS), ray-tracing (RT), and Monte-Carlo path tracing (MCPT)) and their parameters. A CNN architecture, DeepLab, that performs semantic segmentation, is chosen as the CV system being evaluated. In our case study, involving traffic scenes, a CNN trained with CG data samples generated with photorealistic rendering methods (such as RT or MCPT), shows already a reasonably good performance on real-world testing data from CityScapes benchmark. Use of samples from an elementary rendering method, i.e., LS, degraded the performance of CNN by nearly 20%. This result conveys that training data must be photorealistic enough for better generalizability of the trained CNN models. Furthermore, the use of physics-based MCPT rendering improved the performance by 6% but at the cost of more than three times the rendering time. This MCPT generated dataset when augmented with just 10% of real-world training data from CityScapes dataset, the performance levels achieved are comparable to that of training CNN with the complete CityScapes dataset.
The next aspect we study in the thesis involves the impact of choice of parameter settings of scene generation model on the generalization performance of CNN models trained with the generated data. Towards this end, we first propose an algorithm to estimate our scene generation model parameters given an unlabeled real world dataset from the target domain. This unsupervised tuning approach utilizes the concept of generative adversarial training, which aims at adapting the generative model by measuring the discrepancy between generated and real data in terms of their separability in the space of a deep discriminatively-trained classifier. Our method involves an iterative estimation of the posterior density of prior distributions for the generative graphical model used in the simulation. Initially, we assume uniform distributions as priors over parameters of a scene described by our generative graphical model. As iterations proceed the uniform prior distributions are updated sequentially to distributions for the simulation model parameters that leads to simulated data with statistics that are closer to the distributions of the unlabeled target data.
...
Netzwerkmodelle spielen in verschiedenen Wissenschaftsdisziplinen eine wichtige Rolle und dienen unter anderem der Beschreibung realistischer Graphen.
Sie werden häufig als Zufallsgraphen formuliert und stellen somit Wahrscheinlichkeitsverteilungen über Graphen dar.
Meist ist die Verteilung dabei parametrisiert und ergibt sich implizit, etwa über eine randomisierten Konstruktionsvorschrift.
Ein früher Vertreter ist das G(n,p) Modell, welches über allen ungerichteten Graphen mit n Knoten definiert ist und jede Kante unabhängig mit Wahrscheinlichkeit p erzeugt.
Ein aus G(n,p) gezogener Graph hat jedoch kaum strukturelle Ähnlichkeiten zu Graphen, die zumeist in Anwendungen beobachtet werden.
Daher sind populäre Modelle so gestaltet, dass sie mit hinreichend hoher Wahrscheinlichkeit gewünschte topologische Eigenschaften erzeugen.
Beispielsweise ist es ein gängiges Ziel die nur unscharf definierte Klasse der sogenannten komplexen Netzwerke nachzubilden, der etwa viele soziale Netze zugeordnet werden.
Unter anderem verfügen diese Graphen in der Regel über eine Gradverteilung mit schweren Rändern (heavy-tailed), einen kleinen Durchmesser, eine dominierende Zusammenhangskomponente, sowie über überdurchschnittlich dichte Teilbereiche, sogenannte Communities.
Die Einsatzmöglichkeiten von Netzwerkmodellen gehen dabei weit über das ursprüngliche Ziel, beobachtete Effekte zu erklären, hinaus.
Ein gängiger Anwendungsfall besteht darin, Daten systematisch zu produzieren.
Solche Daten ermöglichen oder unterstützen experimentelle Untersuchungen, etwa zur empirischen Verifikation theoretischer Vorhersagen oder zur allgemeinen Bewertung von Algorithmen und Datenstrukturen.
Hierbei ergeben sich insbesondere für große Probleminstanzen Vorteile gegenüber beobachteten Netzen.
So sind massive Eingaben, die auf echten Daten beruhen, oft nicht in ausreichender Menge verfügbar, nur aufwendig zu beschaffen und zu verwalten, unterliegen rechtlichen Beschränkungen, oder sind von unklarer Qualität.
In der vorliegenden Arbeit betrachten wir daher algorithmische Aspekte der Generierung massiver Zufallsgraphen.
Um Anwendern Reproduzierbarkeit mit vorhandenen Studien zu ermöglichen, fokussieren wir uns hierbei zumeist auf getreue Implementierungen etablierter Netzwerkmodelle,
etwa Preferential Attachment-Prozesse, LFR, simple Graphen mit vorgeschriebenen Gradsequenzen, oder Graphen mit hyperbolischer (o.Ä.) Einbettung.
Zu diesem Zweck entwickeln wir praktisch sowie analytisch effiziente Generatoren.
Unsere Algorithmen sind dabei jeweils auf ein geeignetes Maschinenmodell hin optimiert.
Hierzu entwerfen wir etwa klassische sequentielle Generatoren für Registermaschinen, Algorithmen für das External Memory Model, und parallele Ansätze für verteilte oder Shared Memory-Maschinen auf CPUs, GPUs, und anderen Rechenbeschleunigern.
AI-based computer vision systems play a crucial role in the environment perception for autonomous driving. Although the development of self-driving systems has been pursued for multiple decades, it is only recently that breakthroughs in Deep Neural Networks (DNNs) have led to their widespread application in perception pipelines, which are getting more and more sophisticated. However, with this rising trend comes the need for a systematic safety analysis to evaluate the DNN's behavior in difficult scenarios as well as to identify the various factors that cause misbehavior in such systems. This work aims to deliver a crucial contribution to the lacking literature on the systematic analysis of Performance Limiting Factors (PLFs) for DNNs by investigating the task of pedestrian detection in urban traffic from a monocular camera mounted on an autonomous vehicle. To investigate the common factors that lead to DNN misbehavior, six commonly used state-of-the-art object detection architectures and three detection tasks are studied using a new large-scale synthetic dataset and a smaller real-world dataset for pedestrian detection. The systematic analysis includes 17 factors from the literature and four novel factors that are introduced as part of this work. Each of the 21 factors is assessed based on its influence on the detection performance and whether it can be considered a Performance Limiting Factor (PLF). In order to support the evaluation of the detection performance, a novel and task-oriented Pedestrian Detection Safety Metric (PDSM) is introduced, which is specifically designed to aid in the identification of individual factors that contribute to DNN failure. This work further introduces a training approach for F1-Score maximization whose purpose is to ensure that the DNNs are assessed at their highest performance. Moreover, a new occlusion estimation model is introduced to replace the missing pedestrian occlusion annotations in the real-world dataset. Based on a qualitative analysis of the correlation graphs that visualize the correlation between the PLFs and the detection performance, this study identified 16 of the initial 21 factors as being PLFs for DNNs out of which the entropy, the occlusion ratio, the boundary edge strength, and the bounding box aspect ratio turned out to be most severely affecting the detection performance. The findings of this study highlight some of the most serious shortcomings of current DNNs and pave the way for future research to address these issues.
Precise timing of spikes between different neurons has been found to convey reliable information beyond the spike count. In contrast, the role of small phase delays with high temporal variability, as reported for example in oscillatory activity in the visual cortex, remains largely unclear. This issue becomes particularly important considering the high speed of neuronal information processing, which is assumed to be based on only a few milliseconds, or oscillation cycles within each processing step.
We investigate the role of small and imprecise phase delays with a stochastic spiking model that is strongly motivated by experimental observations. Within individual oscillation cycles the model contains only two signal parameters describing directly the rate and the phase. We specifically investigate two quantities, the probability of correct stimulus detection and the probability of correct change point detection, as a function of these signal parameters and within short periods of time such as individual oscillation cycles.
Optimal combinations of the signal parameters are derived that maximize these probabilities and enable comparison of pure rate, pure phase and combined codes. In particular, the gain in detection probability when adding imprecise phases to pure rate coding increases with the number of stimuli. More interestingly, imprecise phase delays can considerably improve the process of detecting changes in the stimulus, while also decreasing the probability of false alarms and thus, increasing robustness and speed of change point detection.
The results are applied to parameters extracted from empirical spike train recordings of neurons in the visual cortex in response to a number of visual stimuli. The results suggest that near-optimal combinations of rate and phase parameters can be implemented in the brain, and that phase parameters could particularly increase the quality of change point detection in cases of highly similar stimuli.
In order to address security and privacy problems in practice, it is very important to have a solid elicitation of requirements, before trying to address the problem. In this thesis, specific challenges of the areas of social engineering, security management and privacy enhancing technologies are analyzed:
Social Engineering: An overview of existing tools usable for social engineering is provided and defenses against social engineering are analyzed. Serious games are proposed as a more pleasant way to raise employees’ awareness and to train them.
Security Management: Specific requirements for small and medium sized energy providers are analyzed and a set of tools to support them in assessing security risks and improving their security is proposed. Larger enterprises are supported by a method to collect security key performance indicators for different subsidiaries and with a risk assessment method for apps on mobile devices. Furthermore, a method to select a secure cloud provider – the currently most popular form of outsourcing – is provided.
Privacy Enhancing Technologies: Relevant factors for the users’ adoption of privacy enhancing technologies are identified and economic incentives and hindrances for companies are discussed. Privacy by design is applied to integrate privacy into the use cases e-commerce and internet of things.
Reproducible annotations
(2022)
This bachelor thesis presents a software solution which implements reproducible annotations in the context of the UIMA framework. This is achieved by creating an automated containerization of arbitrary analysis engines and annotating every analysis engine configuration in the processed CAS document. Any CAS document created by this solution is self sufficient and able to reproduce the exact environment under which it was created.
A review of the state-of-the art software in the field of UIMA reveals that there are many implementations trying to increase reproducibility for a given application relying on UIMA, but no publication trying to increase the reproducibility of UIMA itself. This thesis improves upon that technological gap and provides a throughout analysis at the end which shows a negligible overhead in memory consumption, but a significant performance regression depending on the complexity of the analysis engine which was examined.
Diese Arbeit beschäftigt sich mit linearen inversen Problemen, wie sie in einer Vielzahl an Anwendungen auftreten. Diese Probleme zeichnen sich dadurch aus, dass sie typischerweise schlecht gestellt sind, was in erster Linie die Stabilität betrifft. Selbst kleinste Messfehler haben enorme Konsequenzen für die Rekonstruktion der zu bestimmenden Größe.
Um eine robuste Rekonstruktion zu ermöglichen, muss das Problem regularisiert, dass heißt durch eine ganze Familie abgeänderter, stabiler Approximationen ersetzt werden. Die konkrete Wahl aus der Familie, die sogenannte Parameterwahlstrategie, stützt sich dann auf zusätzliche ad hoc Annahmen über den Messfehler. Typischerweise ist dies im deterministischen Fall die Kenntnis einer oberen Schranke an die Norm des Datenfehlers, oder im stochastischen Fall, die Kenntnis der Verteilung des Fehlers, beziehungsweise die Einschränkung auf eine bestimmte Klasse von Verteilungen, zumeist Gaußsche. In der vorliegenden Arbeit wird untersucht, wie sich diese Informationen unter der Annahme der Wiederholbarkeit der Messung gewinnen lassen. Die Daten werden dabei aus mehreren Messungen gemittelt, welche einer beliebigen, unbekannten Verteilung folgen, wobei die zur Lösung des Problems unweigerlich notwendige Fehlerschranke geschätzt wird. Auf Mittelwert und Schätzer wird dann ein klassisches Regularisierungsverfahren angewandt. Als Regularisierungen werden größtenteils Filter-basierte Verfahren behandelt, die sich auf die Spektralzerlegung des Problems stützen. Als Parameterwahlstrategien werden sowohl einfache a priori-Wahlen betrachtet, als auch das Diskrepanzprinzip als adaptives Verfahren. Es wird Konvergenz für unbekannte beliebige Fehlerverteilungen mit endlicher Varianz sowie für Weißes Rauschen (bezüglich allgemeiner Diskretisierungen) nachgewiesen. Schließlich wird noch die Konvergenz des Diskrepanzprinzips für ein stochastisches Gradientenverfahren gezeigt, als erste rigorose Analyse einer adaptiven Stoppregel für ein solches nicht Filter-basiertes Regularisierungsverfahren.
Ultrarelativistic Quantum Molecular Dynamics is a physics model to describe the transport, collision, scattering, and decay of nuclear particles. The UrQMD framework has been in use for nearly 20 years since its first development. In this period computing aspects, the design of code, and the efficiency of computation have been minor points of interest. Nowadays an additional issue arises due to the fact that the run time of the framework does not diminish any more with new hardware generations.
The current development in computing hardware is mainly focused on parallelism. Especially in scientific applications a high order of parallelisation can be achieved due to the superposition principle. In this thesis it is shown how modern design criteria and algorithm redesign are applied to physics frameworks. The redesign with a special emphasise on many-core architectures allows for significant improvements of the execution speed.
The most time consuming part of UrQMD is a newly introduced relativistic hydrodynamic phase. The algorithm used to simulate the hydrodynamic evolution is the SHASTA. As the sequential form of SHASTA is successfully applied in various simulation frameworks for heavy ion collisions its possible parallelisation is analysed. Two different implementations of SHASTA are presented.
The first one is an improved sequential implementation. By applying a more concise design and evading unnecessary memory copies, the execution time could be reduced to the half of the FORTRAN version’s execution time. The usage of memory could be reduced by 80% compared to the memory needed in the original version.
The second implementation concentrates fully on the usage of many-core architectures and deviates significantly from the classical implementation. Contrary to the sequential implementation, it follows the recalculate instead of memory look-up paradigm. By this means the execution speed could be accelerated up to a factor of 460 on GPUs.
Additionally a stability analysis of the UrQMD model is presented. Applying metapro- gramming UrQMD is compiled and executed in a massively parallel setup. The resulting simulation data of all parallel UrQMD instances were hereafter gathered and analysed. Hence UrQMD could be proven of high stability to the uncertainty of experimental data.
As a further application of modern programming paradigms a prototypical implementa- tion of the worldline formalism is presented. This formalism allows for a direct calculation of Feynman integrals and constitutes therefore an interesting enhancement for the UrQMD model. Its massively parallel implementation on GPUs is examined.
Diese Arbeit beschäftigt sich mit inversen Problemen für partielle Differentialgleichungen. Moderne Lösungsverfahren solcher inversen Probleme müssen die zugehörige partielle Differentialgleichung (PDGL) oft sehr häufig lösen. Mit Hinblick auf die Rechenzeit solcher Verfahren stellt das häufige Lösen der PDGL den Hauptanteil der benötigten Rechenzeit dar. Daraus resultiert die Grundidee dieser Arbeit: es sollen Lösungsverfahren von inversen Problemen beschleunigt werden, indem die für die Vorwärtslösung benötigte Rechenzeit verringert wird. Genauer gesagt soll anstatt der Vorwärtslösung eine Approximation an diese, welche kostengünstig zu berechnen ist, verwendet werden. Für die Bestimmung einer kostengünstigen Annäherung an die Vorwärtslösung wird die Reduzierte Basis Methode, eine Modellreduktionstechnik, verwendet.
Das Ziel der klassischen Reduzierten Basis Methode ist es einen globalen Reduzierte Basis Raum (RB-Raum) zu konstruieren. Dabei handelt es sich um einen niedrigdimensionalen Teilraum des Lösungsraumes der PDGL, welcher für jeden Parameter aus dem Parameterraum eine gute Näherung der PDGL-Lösung liefert. Eine beispielhafte Methode zur Konstruktion eines solchen Raumes ist es, geschickt Parameter auszuwählen und die dazu gehörigen PDGL-Lösungen als Basisvektoren des RB-Raumes zu verwenden. Die orthogonale Projektion der PDGL auf diesen RB-Raum liefert die entsprechenden Reduzierte Basis Lösungen. Das Besondere in dieser Arbeit ist, dass die betrachteten PDGLn einen sehr hochdimensionalen und unbeschränkten Parameterraum besitzen, und es ist bekannt, dass dies für die Reduzierte Basis Methode eine immense Schwierigkeit darstellt.
In Kapitel 1 wird ein schlechtgestelltes inverses Modellproblem, die Rekonstruktion der Wärmeleitfähigkeit eines Gegenstandes aus der Messung der Temperatur desselben, eingeführt und das nichtlineare Landweber-Verfahren als iteratives Regularisierungsverfahren zur Lösung dieses inversen Problems vorgestellt. Die Grundlagen der Reduzierten Basis Methode werden dargelegt und es wird erläutert, warum die klassische Variante der Methode in diesem Kontext der Bildrekonstruktion versagt. Daraufhin wird der neuartig Ansatz, ein adaptiver Reduzierte Basis Ansatz, entwickelt. Die folgenden Schritte bilden die Grundlage dieses adaptiven Reduzierte Basis Ansatzes:
1. Sei ein RB-Raum gegeben, so projiziere den Lösungsalgorithmus des inversen Problems auf diesen RB-Raum.
2. Generiere mit Hilfe dieses projizierten Verfahrens neue Iterierte bis entweder eine Iterierte das inverse Problem löst oder bis der RB-Raum erweitert werden muss.
3. Im ersten Fall wird das Verfahren beendet, im zweiten Fall wird die zur aktuellen Iterierten gehörige Vorwärtslösung verwendet um den RB-Raum zu verbessern. Danach wird mit dem ersten Schritt fortgefahren.
Es wird also nach und nach ein lokal approximierender RB-Raum konstruiert, indem Parameter für neue Basisvektoren mittels einer projizierten Variante des Lösungsalgorithmus des inversen Problems gefunden werden. Das neuartige Reduzierte Basis Landweber-Verfahren ist das Hauptresultat von Kapitel 1, wobei das Verfahren ausführlich numerisch untersucht und mit dem ursprünglichen Landweber-Verfahren verglichen wird.
In Kapitel 2 dieser Arbeit soll der zuvor entwickelte adaptive Reduzierte Basis Ansatz auf ein komplexes und praxisrelevantes Problem angewandt werden. Insbesondere soll die dadurch entstehende neue Methode mit Hinblick auf Konvergenz theoretisch ausführlich untersucht werden. Daher widmet sich der zweite Teil dieser Arbeit dem Problem der Magnet Resonanz Elektrischen Impedanztomographie (MREIT).
Bei der MREIT handelt es sich um ein Bildgebungsverfahren, welches während der letzten drei Jahrzehnte entwickelt wurde. Dabei wird ein Gegenstand, an welchen Elektroden angeheftet sind, in einen Kernspintomographen gelegt und es ist das Ziel des Verfahrens die elektrische Leitfähigkeit des Gegenstandes zu bestimmen. Die dazu benötigten Daten werden folgendermaßen gewonnen: indem Strom an einer der Elektroden angelegt wird, wird ein Stromfluss erzeugt, welcher wiederum eine Änderung der Magnetflussdichte induziert. Diese kann mit Hilfe des Kernspintomographen gemessen werden, wodurch man einen vollen Satz innerer Daten zur Hand hat, sodass hoch aufgelöste Bilder der elektrischen Leitfähigkeit des Gegenstandes rekonstruiert werden können.
Als Lösungsalgorithmus für dieses praxisrelevante Problem wird der bereits bekannte Harmonische Bz Algorithmus vorgestellt. Das Problem und der Algorithmus werden mit Hinblick auf Konvergenz des Verfahrens untersucht und ein Konvergenzresultat, welches die bestehende Konvergenztheorie hin zu einem approximativen Harmonischen Bz Algorithmus erweitert, wird bewiesen. Dabei hängt das Resultat nicht davon ab welche Art von Approximation an die Vorwärtslösung der entsprechenden PDGL im approximativen Harmonischen Bz Algorithmus verwendet wird solange diese einer Regularitäts- und einer Qualitätsbedingung genügt. Damit folgt das zweite Hauptresultat dieser Arbeit: die numerische Konvergenz des Harmonischen Bz Algorithmus. Es soll dabei hervorgehoben werden, dass Konvergenzresultate im Bereich der inversen Probleme (sofern es sie gibt) meistens die Kenntnis der exakten Vorwärtslösung annehmen, sodass keine numerische Konvergenz des zugehörigen Verfahrens folgt (in einer numerischen Implementation wird stets eine Approximation an die Vorwärtslösung verwendet). Somit ist dieses Konvergenzresultat ein Schritt hin zur numerischen Konvergenz anderer Lösungsverfahren von inversen Problemen.
Da das theoretische Resultat von der Art der Approximation nicht abhängt, erhält man ebenfalls die Konvergenz des neuartigen Reduzierte Basis Harmonischen Bz Algorithmus, welcher die Kombination des in Kapitel 1 entwickelten adaptiven Reduzierte Basis Ansatzes und des Harmonischen Bz Algorithmus ist. In einer kurzen numerischen Untersuchung wird festgestellt, dass dieser Reduzierte Basis Harmonische Bz Algorithmus schneller als der Harmonische Bz Algorithmus ist, wobei die Qualität der Rekonstruktion gleichbleibend ist. Somit funktioniert der entwickelte adaptive Reduzierte Basis Ansatz auch angewandt auf dieses komplexe praxisrelevante inverse Problem der MREIT.
For the class of balanced, irreducible Pólya urn schemes with two colours, say black and white, limit theorems for the number of black balls after n steps are known. Depending on the ratio of the eigenvalues of the replacement matrix, two regimes of limit laws occur: almost sure convergence to a non-degenerate random variable whose distribution depends on the initial composition of the urn and that is known to be not normally distributed and weak convergence to the normal distribution. In this thesis, upper bounds on the rates of convergence in both the non-normal limit case and the normal limit case are given.
The Project European Privacy Open Space (PrivacyOS) aims at bringing together industry, SMEs, Government, Academia and Civil Society to foster development and deployment of privacy infrastructures for Europe. The general objectives of PrivacyOS are to create a longterm collaboration in the thematic network and establish collective interfaces with other EU projects. Participants exchange research and best practices, as well as develop strategies and joint projects following four core policy goals: Awareness-rising, enabling privacy on the Web, fostering privacy-friendly Identity Management, and stipulating research.
...
This report focuses on the 3rd PrivacyOS conference, which was held in Vienna, October 26th and 27th 2009, co-located with the Austrian Big Brother Awards. 50 participants attended the conference and devised the agenda with 21 presentations in two parallel tracks. The topics of the presentations discussed included, amongst others: data protection awareness, data protection in healthcare, data protection in the Web 2.0, privacy-related technologies such as EnCoRe, TOR or Microformats as well as regulatory, cultural and sociological implications of data protection. Also at the 3rd PrivacyOS conference the software product “KiwiSecurity” was awarded the EuroPriSe Seal (European Privacy Seal, www.european-privacy-seal.eu). EuroPriSe is an initiative of the data protection authority Unabhängiges Landeszentrum für Datenschutz Schleswig-Holstein (ULD), Germany. It has been started as a European Project under the eTEN programme.
We thoroughly study the properties of conically stable polynomials and imaginary projections. A multivariate complex polynomial is called stable if its nonzero whenever all coordinates of the respective argument have a positive imaginary part. In this dissertation we consider the generalized notion of K-stability. A multivariate complex polynomial is called K-stable if its non-zero whenever the imaginary part of the respective argument lies in the relative interior of the cone K. We study connections to various other objects, including imaginary projections as well as preservers and combinatorial criteria for conically stable polynomials.
Recently, Aumüller and Dietzfelbinger proposed a version of a dual-pivot Quicksort, called "Count", which is optimal among dual-pivot versions with respect to the average number of key comparisons required. In this master's thesis we provide further probabilistic analysis of "Count". We derive an exact formula for the average number of swaps needed by "Count" as well as an asymptotic formula for the variance of the number of swaps and a limit law. Also for the number of key comparisons the asymptotic variance and a limit law are identified. We also consider both complexity measures jointly and find their asymptotic correlation.
Principles of cognitive maps
(2021)
This thesis analyses the concept of a cognitive map in the research fields of geography. Cognitive mapping research is essential as it investigates the relations between cognitive maps and external representations of space that people regularly use by acquiring spatial knowledge, such as maps in geographic information systems. Moreover, cognitive maps, when expanded on semantic maps, explain the relations between people and things in a non-physically environment, where the considered space is not spanned by distance but with other non-spatially variables. Nevertheless, cognitive maps are often distorted. Although a good formation of a cognitive map is vital in navigation processes, cognitive distortions are barely investigated in the field of geography. By analyzing the relevant work, especially Tobler’s first law of geography, a new lexical variant of Tobler’s first law could be stated that could presumably describe a specific distortion in the processing of landmarks in cognitive maps.
The technology of advanced driver assistance systems (ADAS) has rapidly developed in the last few decades. The current level of assistance provided by the ADAS technology significantly makes driving much safer by using the developed driver protection systems such as automatic obstacle avoidance and automatic emergency braking. With the use of ADAS, driving not only becomes safer but also easier as ADAS can take over some routine tasks from the driver, e.g. by using ADAS features of automatic lane keeping and automatic parking. With the continuous advancement of the ADAS technology, fully autonomous cars are predicted to be a reality in the near future.
One of the most important tasks in autonomous driving is to accurately localize the egocar and continuously track its position. The module which performs this task, namely odometry, can be built using different kinds of sensors: camera, LIDAR, GPS, etc. This dissertation covers the topic of visual odometry using a camera. While stereo visual odometry frameworks are widely used and dominating the KITTI odometry benchmark (Geiger, Lenz and Urtasun 2012), the accuracy and performance of monocular visual odometry is much less explored.
In this dissertation, a new monocular visual odometry framework is proposed, namely Predictive Monocular Odometry (PMO). PMO employs the prediction-and-correction mechanism in different steps of its implementation. PMO falls into the category of sparse methods. It detects and chooses keypoints from images and tracks them on the subsequence frames. The relative pose between two consecutive frames is first pre-estimated using the pitch-yaw-roll estimation based on the far-field view (Barnada, Conrad, Bradler, Ochs and Mester 2015) and the statistical motion prediction based on the vehicle motion model (Bradler, Wiegand and Mester 2015). The correction and optimization of the relative pose estimates are carried out by minimizing the photometric error of the keypoints matches using the joint epipolar tracking method (Bradler, Ochs, Fanani and Mester 2017).
The monocular absolute scale is estimated by employing a new approach to ground plane estimation. The camera height over ground is assumed to be known. The scale is first estimated using the propagation-based scale estimation. Both of the sparse matching and the dense matching of the ground features between two consecutive frames are then employed to refine the scale estimates. Additionally, street masks from a convolutional neural network (CNN) are also utilized to reject non-ground objects in the region of interest.
PMO also has a method to detect independently moving objects (IMO). This is important for visual odometry frameworks because the localization of the ego-car should be estimated only based on static objects. The IMO candidate masks are provided by a CNN. The case of crossing IMOs is handled by checking the epipolar consistency. The parallel-moving IMOs, which are epipolar conformant, are identified by checking the depth consistency against the depth maps from CNN.
In order to evaluate the accuracy of PMO, a full simulation on the KITTI odometry dataset was performed. PMO achieved the best accuracy level among the published monocular frameworks when it was submitted to the KITTI odometry benchmark in July 2017. As of January 2018, it is still one of the leading monocular methods in the KITTI odometry benchmark.
It is important to note that PMO was developed without employing random sampling consensus (RANSAC) which arguably has been long considered as one of the irreplaceable components in a visual odometry framework. In this sense, PMO introduces a new style of visual odometry framework. PMO was also developed without a multi-frame bundle adjustment step. This reflects the high potential of PMO when such multi-frame optimization scheme is also taken into account.
Polarization of Λ and ¯Λ hyperons along the beam direction in Pb-Pb collisions at √sNN=5.02 TeV
(2022)
The polarization of the Λ and ¯Λ hyperons along the beam (z) direction, Pz, has been measured in Pb-Pb collisions at √sNN=5.02 TeV recorded with ALICE at the Large Hadron Collider (LHC). The main contribution to Pz comes from elliptic flow-induced vorticity and can be characterized by the second Fourier sine coefficient Pz,s2=⟨Pzsin(2φ−2Ψ2)⟩, where φ is thhyperon azimuthal emission angle and Ψ2 is the elliptic flow plane angle. We report the measurement of Pz,s2 for different collision centralities and in the 30%–50% centrality interval as a function of the hyperon transverse momentum and rapidity. The Pz,s2 is positive similarly as measured by the STAR Collaboration in Au-Au collisions at √sNN=200 GeV, with somewhat smaller amplitude in the semicentral collisions. This is the first experimental evidence of a nonzero hyperon Pz in Pb-Pb collisions at the LHC. The comparison of the measured Pz,s2 with the hydrodynamic model calculations shows sensitivity to the competing contributions from thermal and the recently found shear-induced vorticity, as well as to whether the polarization is acquired at the quark-gluon plasma or the hadronic phase.
The thesis is about random Constraint Satisfaction Problems (rCSP). These are random instances of classical problems in NP. In the literature the study of rCSP involve identifying-locating phase transition phenomena as well as investigating algorithmic questions.
Recently, some ingenious however mathematically non-rigorous theories from statistical physics have given the study of rCSP a new perspective; the so-called Cavity Method makes some very impressing predictions about the most fundamental properties of rCSP.
In this thesis, we investigate the soundness of some of the most basic predictions of the Cavity Method, mainly, regarding the structure of the so-called Gibbs distribution on various rCSP models. Furthermore, we study some fundamental algorithmic problem related to rCSP. This includes both analysing well-known dynamical process (dynamics) like Glauber Dynamics, Metropolis Process, as well as proposing new algorithmic approaches to some natural problems related to rCSP.
In this thesis we discuss the group Out(Gal_K) of outer automorphism of the absolute Galois group Gal_K of a p-adic number field K. Using results about the mapping class group of a surface S, as well as a result by Jannsen--Wingberg on the structure of the absolute Galois group Gal_K, we construct a large subgroup of Out(Gal_K) arising as images of certain Dehn twists on S.
Die Arbeit befasst sich mit zwei funktionalen Grenzwertsätzen für skalierte Linienzählprozesse von anzestralen Selektionsgraphen. Dazu werden zwei Modelle aus der mathematischen Populationsgenetik betrachtet. Wir führen zuerst das Moran-Modell mit gerichteter Selektion mit konstanter Populationsgröße N in kontinuierlicher Zeit und den Linienzählprozess des anzestralen Selektionsgraphen (MASP) gemäß Krone und Neuhauser (Theor. Popul. Biol. 1997) ein. Die Hauptaussage dieser Abschlussarbeit besagt, dass der passend standardisierte MASP im Fall der moderaten Selektion für N gegen unendlich in Verteilung gegen einen Ornstein-Uhlenbeck-Prozess konvergiert. Das zweite betrachtete Modell ist das Cannings-Modell mit gerichteter Selektion in diskreter Zeit, das gemäß Boenkost, González Casanova, Pokalyuk und Wakolbinger (Electron. J. Probab. 2021) eingeführt wird. Für ein Teilregime der moderat schwachen Selektion wird bewiesen, dass die reskalierten Fluktuationen des Linienzählprozesses des anzestralen Selektionsgraphen im Cannings-Modell ebenfalls in Verteilung gegen einen Ornstein-Uhlenbeck-Prozess konvergieren.
Aufgrund der §§20, 44 Abs. 1 Nr. 1 des Hessischen Hochschulgesetzes in der Fassung vom 14. Dezember 2009 (GVBl. I, S. 666), zuletzt geändert durch Art. 2 des Gesetzes vom 18. Dezember 2017 (GVBl. I, S. 284), hat der Fachbereichsrat des Fachbereichs Informatik und Mathematik der Johann Wolfgang Goethe-Universität Frankfurt am Main am 25. Mai 2020 die folgende Ordnung für den Bachelorstudiengang Mathematik beschlossen. Diese Ordnung hat das Präsidium der Goethe-Universität gemäß §37 Abs. 5 Hessisches Hochschulgesetz am 30. Juni 2020 genehmigt. Sie wird hiermit bekannt gemacht.
This thesis presents various algorithms which have been developed for on-line event reconstruction in the CBM experiment at GSI, Darmstadt and the ALICE experiment at CERN, Geneve. Despite the fact that the experiments are different — CBM is a fixed target experiment with forward geometry, while ALICE has a typical collider geometry — they share common aspects when reconstruction is concerned.
The thesis describes:
— general modifications to the Kalman filter method, which allows one to accelerate, to improve, and to simplify existing fit algorithms;
— developed algorithms for track fit in CBM and ALICE experiment, including a new method for track extrapolation in non-homogeneous magnetic field.
— developed algorithms for primary and secondary vertex fit in the both experiments. In particular, a new method of reconstruction of decayed particles is presented.
— developed parallel algorithm for the on-line tracking in the CBM experiment.
— developed parallel algorithm for the on-line tracking in High Level Trigger of the ALICE experiment.
— the realisation of the track finders on modern hardware, such as SIMD CPU registers and GPU accelerators.
All the presented methods have been developed by or with the direct participation of the author.
Die zentralen Objekte der Dissertation sind Translationsflächen. Dabei handelt es sich um Riemann’sche Flächen, die aus in die euklidische Ebene eingebetteten Polygonen durch Verkleben von parallelen gleichlangen Seiten entstehen. Zwei Translationsflächen sind gleich, wenn es möglich ist, die Polygone durch ”Zerschneiden und mittels Translationen neu Zusammenkleben“ ineinander zu überführen. Die Gruppe GL_2(R) operiert auf der Menge der Translationsflächen via der linearen Abbildungen auf den Polygonen. Der Stabilisator einer Translationsfläche X unter dieser Operation wird die Veech-Gruppe von X genannt und mit SL(X) bezeichnet. Die Veech-Gruppe ist eine diskrete Untergruppe von SL_2(R) und damit eine Fuchs’sche Gruppe.
Fuchs’sche Gruppen werden je nach ihrer Limesmenge in elementare und nicht-elementare Gruppen eingeteilt. Letztere wiederum unterteilt man in Gruppen erster oder zweiter Art. Fuchs’sche Gruppen mit endlichem co-Volumen heißen Gitter und sind genau die endlich erzeugten Gruppen erster Art. Translationsflächen, deren Veech-Gruppe ein Gitter ist, heißen Veech-Flächen und sind von besonderem Interesse, da für sie die Veech Alternative gilt.
Ein feineres Maß für die Größe einer Fuchs’schen Gruppe ist der kritische Exponent. Er ist definiert als das Infimum aller reellen Zahlen, für die die Poincaré Reihe konvergiert und liegt für alle unendlichen Fuchs’schen Gruppen zwischen 0 und 1. Hauptziel der Dissertation ist der Beweis von Theorem 1. Es gibt Translationsflächen, für die der kritische Exponent ihrer Veech-Gruppe echt zwischen 1/2 und 1 liegt.
Der kritische Exponent von elementaren Gruppen ist höchstens 1/2, Translationsflächen mit elementaren Veech-Gruppen sind also als Kandidaten für das Theorem ausgeschlossen. Der kritische Exponent von Gittern ist 1. Also scheiden auch Veech-Flächen für das Theorem aus.
Bis zum Jahr 2003 waren Gitter die einzigen bekannten nicht-elementaren Veech-Gruppen. McMullen klassifizierte die Veech-Flächen vom Geschlecht 2 und zeigte, dass jede solche Fläche, die nur eine Singularität besitzt, in der GL_2(R)-Bahn der Fläche L_D liegt, die aus einem L-förmigen Polygon mit geeigneten von D abhängigen Seitenlängen entsteht.
Während auch heute noch keine Translationsfläche mit Veech-Gruppe zweiter Art bekannt ist, fanden McMullen und unabhängig davon Hubert und Schmidt Konstruktionen unendlich erzeugter Veech-Gruppen erster Art. Eine Abschätzung des kritischen Exponenten dieser Gruppen war 10 Jahre lang eine wichtige offene Frage, die nun durch Theorem 1 beantwortet wird.
Zentral in der Konstruktion von Hubert und Schmidt sind spezielle Punkte, nämlich Verbindungspunkte. Hubert und Schmidt konstruieren Translationsflächen, deren Veech-Gruppen kommensurabel zum Stabilisator SL(X;P) von P sind und damit den gleichen kritischen Exponenten haben. Für Verbindungspunkte mit unendlicher SL(X)- Bahn (diese Punkte heißen nicht-periodisch) ist SL(X;P) unendlich erzeugt und von erster Art.
Wir zeigen Theorem 1, indem wir zeigen, dass für jedes D kongruent 0 mod 4, (kein Quadrat), und jeden nicht-periodischen Verbindungspunkt P in L_D der kritische Exponent der Gruppe SL(L_D;P) echt zwischen 1/2 und 1 liegt.
Eine natürliche Frage in diesem Zusammenhang ist die Abhängigkeit von P: Punkte Q in der SL(L_D)-Bahn von P sind auch er nicht-periodische Verbindungspunkte und die zugehö̈rigen Gruppen SL(L_D;P) und SL(L_D;Q) sind konjugiert zueinander. Daher widmen wir uns in Kapitel 4 der Bestimmung der Bahnen nicht-periodischer Verbindungspunkte.
Die Verbindungspunkte haben die Form P=(x_r+x_iw;y_r+y_iw) mit x_r,x_i,y_r,y_i aus Q. Wir zeigen, dass der Hauptnenner N(P) dieser (gekürzten) Brüche eine Invariante der Bahn ist. Daraus folgt:
Theorem 2. Es gibt unendlich viele verschiedene Bahnen von Verbindungspunkten von L_D.
Wir kennen die Operation der horizontalen und der vertikalen Scherungen A und B aus SL(L_D). Im Spezialfall D=8 erzeugen diese beiden Elemente die ganze Gruppe und wir geben je ein Verfahren an, um eine untere und eine obere Schranke an die Anzahl der Bahnen von nicht-periodischen Verbindungspunkten P mit fixiertem Hauptnenner N(P) zu finden. Damit zeigen wir:
Theorem 3. Die Menge der Verbindungspunkte P mit festem Wert N(P) zerfällt in eine endliche Anzahl von SL(L_8)-Bahnen.
Im Beweis von Theorem 1 ist es nötig, die Nicht-Mittelbarkeit eines Graphen zu zeigen. Da wir nur sehr wenige Informationen über dessen Struktur in unserer konkreten Situation haben, entwickeln wir in Kapitel 1 die folgende Methode:
Theorem 4. Sei G ein Graph, den man durch Weglassen von Kanten in einen Wald G′ ohne Blätter überführen kann, bei dem das Supremum der Längen von zusammenhängenden Valenz-2-Teilgraphen von G′ beschränkt ist. Dann ist G nicht mittelbar.
Um diese Methode anzuwenden, ordnen wir jeder Ecke P von G ein Komplexitätsmaß s(P) zu und weisen nach, dass dieser Wert für die Operation von Worten in A- und B-Potenzen mit wachsender Wortlänge ”tendenziell wächst“.
When we browse via WiFi on our laptop or mobile phone, we receive data over a noisy channel. The received message may differ from the one that was sent originally. Luckily it is often possible to reconstruct the original message but it may take a lot of time. That’s because decoding the received message is a complex problem, NP-hard to be exact. As we continue browsing, new information is sent to us in a high frequency. So if lags are to be avoided and as memory is finite, there is not much time left for decoding. Coding theory tackles this problem by creating models of the channels we use to communicate and tailor codes based on the channel properties. A well known family of codes are Low-Density Parity-Check codes (LDPC codes), they are widely used in standards like WiFi and DVB-T2. In practical settings the complexity of decoding a received message can be heavily reduced by using LDPC codes and approximative decoding algorithms. This thesis lays out the basic construction of LDPC codes and a proper decoding using the sum-product algorithm. On this basis a neural network to improve decoding is introduced. Therefore the sum-product algorithm is transformed into a neural network decoder. This approach was first presented by Nachmani et al. and treated in detail by Navneet Agrawal in 2017. To find out how machine learning can improve the codes, the bit error rates of the trained neural network decoder are compared with the bit error rates of the classic sum-product algorithm approach. Experiments with static and dynamic training datasets of diverse sizes, various signal-to-noise ratios, a feed forward as well as a recurrent architecture show how to tune the neural network decoder even further. Results of the experiments are used to verify statements made in Agrawal’s work. In addition, corrections and improvements in the area of metrics are presented. An implementation of the neural network to facilitate access for others will be made available to the public.
Within the last thirty years, the contraction method has become an important tool for the distributional analysis of random recursive structures. While it was mainly developed to show weak convergence, the contraction approach can additionally be used to obtain bounds on the rate of convergence in an appropriate metric. Based on ideas of the contraction method, we develop a general framework to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. In essence, we present three different versions of convergence theorems: a general version, an improved version for normal limit laws (providing significantly better bounds in some examples with normal limits) and a third version with a relaxed independence condition. Moreover, concrete applications are given which include parameters of random trees, quantities of stochastic geometry as well as complexity measures of recursive algorithms under either a random input or some randomization within the algorithm.
The sum of Lyapunov exponents Lf of a semi-stable fibration is the ratio of the degree of the Hodge bundle by the Euler characteristic of the base. This ratio is bounded from above by the Arakelov inequality. Sheng-Li Tan showed that for fiber genus g≥2 the Arakelov equality is never attained. We investigate whether there are sequences of fibrations approaching asymptotically the Arakelov bound. The answer turns out to be no, if the fibration is smooth, or non-hyperelliptic, or has a small base genus. Moreover, we construct examples of semi-stable fibrations showing that Teichmüller curves are not attaining the maximal possible value of Lf.
The sum of Lyapunov exponents Lf of a semi-stable fibration is the ratio of the degree of the Hodge bundle by the Euler characteristic of the base. This ratio is bounded from above by the Arakelov inequality. Sheng-Li Tan showed that for fiber genus g≥2 the Arakelov equality is never attained. We investigate whether there are sequences of fibrations approaching asymptotically the Arakelov bound. The answer turns out to be no, if the fibration is smooth, or non-hyperelliptic, or has a small base genus. Moreover, we construct examples of semi-stable fibrations showing that Teichmüller curves are not attaining the maximal possible value of Lf.
On development, feasibility, and limits of highly efficient CPU and GPU programs in several fields
(2013)
With processor clock speeds having stagnated, parallel computing architectures have achieved a breakthrough in recent years. Emerging many-core processors like graphics cards run hundreds of threads in parallel and vector instructions are experiencing a revival. Parallel processors with many independent but simple arithmetical logical units fail executing serial tasks efficiently. However, their sheer parallel processing power makes them predestined for parallel applications while the simple construction of their cores makes them unbeatably power efficient. Unfortunately, old programs cannot profit by simple recompilation. Adaptation often requires rethinking and modifying algorithms to make use of parallel execution. Many applications have some serial subroutines which are very hard to parallelize, hence contemporary compute clusters are often homogeneous, offering fast processors for serial tasks and parallel processors for parallel tasks. In order not to waste the available compute power, highly efficient programs are mandatory.
This thesis is about the development of fast algorithms and their implementations on modern CPUs and GPUs, about the maximum achievable efficiency with respect to peak performance and to power consumption respectively, and about feasibility and limits of programs for CPUs, GPUs, and heterogeneous systems. Three totally different applications from distinct fields, which were developed in the extent of this thesis, are presented.
The ALICE experiment at the LHC particle collider at CERN studies heavy-ion collisions at high rates of several hundred Hz, while every collision produces thousands of particles, whose trajectories must be reconstructed. For this purpose, ALICE track reconstruction and ALICE track merging have been adapted for GPUs and deployed on 64 GPU-enabled compute-nodes at CERN.
After a testing phase, the tracker ran in nonstop operation during 2012 providing full real-time track reconstruction. The tracker employs a multithreaded pipeline as well as asynchronous data transfer to ensure continuous GPU utilization and outperforms the fastest available CPUs by about a factor three.
The Linpack benchmark is the standard tool for ranking compute clusters. It solves a dense system of linear equations using primarily matrix multiplication facilitated by a routine called DGEMM. A heterogeneous GPU-enabled version of DGEMM and Linpack has been developed, which can utilize the CAL, CUDA, and OpenCL APIs as backend. Employing this implementation, the LOEWE-CSC cluster ranked place 22 in the November 2010 Top500 list of the fastest supercomputers, and the Sanam cluster achieved the second place in the November 2012 Green500 list of the most power efficient supercomputers. An elaborate lookahead algorithm, a pipeline, and asynchronous data transfer hide the serial CPU-bound tasks of Linpack behind DGEMM execution on the GPU reaching the highest efficiency on GPU-accelerated clusters.
Failure erasure codes enable failure tolerant storage of data and real-time failover, ensuring that in case of a hardware defect servers and even complete data centers remain operational. It is an absolute necessity for present-day computer infrastructure. The mathematical theory behind the codes involves matrix-computations in finite fields, which are not natively supported by modern processors and hence computationally very expensive. This thesis presents a novel scheme for fast encoding matrix generation and demonstrates a fast implementation for the encoding itself, which uses exclusively either integer or logical vector instructions. Depending on the scenario, it is always hitting different hard limits of the hardware: either the maximum attainable memory bandwidth, or the peak instruction throughput, or the PCI Express bandwidth limit when GPUs or FPGAs are used.
The thesis demonstrates that in most cases with respect to the available peak performance, GPU implementations can be as efficient as their CPU counterparts.
With respect to costs or power consumption, they are much more efficient. For this purpose, complex tasks must be split in serial as well as parallel parts and the execution must be pipelined such that the CPU bound tasks are hidden behind GPU execution. Few cases are identified where this is not possible due to PCI Express limitations or not reasonable because practical GPU languages are missing.
A lot of software systems today need to make real-time decisions to optimize an objective of interest. This could be maximizing the click-through rate of an ad displayed on a web page or profit for an online trading software. The performance of these systems is crucial for the parties involved. Although great progress has been made over the years in understanding such online systems and devising efficient algorithms, a fine-grained analysis and problem specific solutions are often missing. This dissertation focuses on two such specific problems: bandit learning and pricing in gross-substitutes markets.
Bandit learning problems are a prominent class of sequential learning problems with several real-world applications. The classical algorithms proposed for these problems, although optimal in a theoretical sense often tend to overlook model-specific proper- ties. With this as our motivation, we explore several sequential learning models and give efficient algorithms for them. Our approaches, inspired by several classical works, incorporate the model-specific properties to derive better performance bounds.
The second part of the thesis investigates an important class of price update strategies in static markets. Specifically, we investigate the effectiveness of these strategies in terms of the total revenue generated by the sellers and the convergence of the resulting dynamics to market equilibrium. We further extend this study to a class of dynamic markets. Interestingly, in contrast to most prior works on this topic, we demonstrate that these price update dynamics may be interpreted as resulting from revenue optimizing actions of the sellers. No such interpretation was known previously. As a part of this investigation, we also study some specialized forms of no-regret dynamics and prediction techniques for supply estimation. These approaches based on learning algorithms are shown to be particularly effective in dynamic markets.
Matroids are combinatorial objects that generalize linear independence. A matroid can be represented geometrically by its Bergman fan and we compare the symmetries of these two objects. Sometimes, the Bergman fan has additional automorphisms, which are related to Cremona transformations in projective space. Their existence depends on a combinatorial property of the matroid, as has been shown by Shaw and Werner, and we study the consequences for the structure of such matroids. This allows us to gain a better understanding of the so-called Cremona group of a matroid and we apply our results to root system matroids.
Statistical shape models learn to capture the most characteristic geometric variations of anatomical structures given samples from their population. Accordingly, shape models have become an essential tool for many medical applications and are used in, for example, shape generation, reconstruction, and classification tasks. However, established statistical shape models require precomputed dense correspondence between shapes, often lack robustness, and ignore the global surface topology. This thesis presents a novel neural flow-based shape model that does not require any precomputed correspondence. The proposed model relies on continuous flows of a neural ordinary differential equation to model shapes as deformations of a template. To increase the expressivity of the neural flow and disentangle global, low-frequency deformations from the generation of local, high- frequency details, we propose to apply a hierarchy of flows. We evaluate the performance of our model on two anatomical structures, liver, and distal femur. Our model outperforms state-of-the-art methods in providing an expressive and robust shape prior, as indicated by its generalization ability and specificity. More so, we demonstrate the effectiveness of our shape model on shape reconstruction tasks and find anatomically plausible solutions. Finally, we assess the quality of the emerging shape representation in an unsupervised setting and discriminate healthy from pathological shapes.
Biodiversity information is contained in countless digitized and unprocessed scholarly texts. Although automated extraction of these data has been gaining momentum for years, there are still innumerable text sources that are poorly accessible and require a more advanced range of methods to extract relevant information. To improve the access to semantic biodiversity information, we have launched the BIOfid project (www.biofid.de) and have developed a portal to access the semantics of German language biodiversity texts, mainly from the 19th and 20th century. However, to make such a portal work, a couple of methods had to be developed or adapted first. In particular, text-technological information extraction methods were needed, which extract the required information from the texts. Such methods draw on machine learning techniques, which in turn are trained by learning data. To this end, among others, we gathered the BIOfid text corpus, which is a cooperatively built resource, developed by biologists, text technologists, and linguists. A special feature of BIOfid is its multiple annotation approach, which takes into account both general and biology-specific classifications, and by this means goes beyond previous, typically taxon- or ontology-driven proper name detection. We describe the design decisions and the genuine Annotation Hub Framework underlying the BIOfid annotations and present agreement results. The tools used to create the annotations are introduced, and the use of the data in the semantic portal is described. Finally, some general lessons, in particular with multiple annotation projects, are drawn.
Das adaptive Immunsystem schützt den Menschen vor extra- wie auch intrakorporal auftretenden Pathogenen und Krebszellen. Die Funktionalität dieses Prozesses geht hierbei auf die Interaktion und Kooperation einer Vielzahl verschiedener Zelltypen des Körpers zurück und ist vorwiegend innerhalb der Lymphknoten lokalisiert. Ist auch nur ein Bestandteil dieses sensiblen Prozesses gestört, kann dies zu einem teilweisen oder vollständigen Verlust der immunologischen Fitness des Menschen führen. Daher war es das Ziel dieser Arbeit, solche Aberrationen des humanen Lymphknotengewebes umfassend digital-pathologisch zu detektieren und zu definieren.
Hierfür wurde zunächst eine digitale Gewebedatenbank etabliert. Diese basiert auf dem im Rahmen dieser Arbeit implementierten Content-Management-System Digital Tissue Management Suite. Weiterhin wurde die Software Feature analysis in tissue histomorphometry entwickelt, welche die Analyse von zweidimensionalen whole slide images ermöglicht. Hierbei werden Methoden aus dem Bereich Computer Vision und Graphentheorie eingesetzt, um morphologische und distributionale Eigenschaften der Zelltypen des Lymphknotens zu charakterisieren. Darüber hinaus enthält diese Software Plug-ins zur Visualisierung und statistischen Analyse der Daten.
Aufbauend auf der eigens implementierten, digitalen Infrastruktur, in Kombination mit der Software Imaris wurden zweidimensional und dreidimensional gescannte, reaktive und neoplastische Gewebeproben digital phänotypisiert. Hierbei konnten neue mechanische Barrieren zur Kompartimentalisierung der Keimzentren aufgeklärt werden. Weiterhin konnte der Erhalt des quantitativen Verhältnisses einzelner Zellpopulationen innerhalb der Keimzentren beschrieben werden. Ausgehend von den reaktiven Phänotypen des Lymphknotens, wurden pathophysiologische Aberrationen in verschiedenen lymphatischen Neoplasien untersucht. Hierbei konnte gezeigt werden, dass speziell die strukturelle Destruktion häufig mit einer morphologischen Veränderung der fibroblastischen Retikulumzellen einhergeht.
Neben strukturellen Veränderungen sind auch zytologische Veränderungen der Tumormikroumgebung zu verzeichnen. Eine besondere Rolle spielen hierbei sogenannte Tumor-assoziierte Makrophagen. Im Rahmen dieser Arbeit konnte gezeigt werden, dass speziell Makrophagen in der Tumormikroumgebung des diffus großzelligen B-Zell-Lymphoms und der chronisch lymphatischen Leukämie spezifische pathophysiologische Veränderungen aufzeigen. Auch konnte gezeigt werden, dass genetische Änderungen neoplastischer B-Zellen mit einer generellen Reduktion der CD20-Antigendichte einhergehen.
Zusammenfassend ermöglichten die Ergebnisse die Generierung eines umfassenden digital-pathologischen Profils des klassischen Hodgkin-Lymphoms. Hierbei konnten morphologische Veränderungen neoplastischer, CD30-positiver Hodgkin-Reed-Sternberg-Zellen validiert und beschrieben werden. Auch konnten pathologische Veränderungen des Konnektoms und der Tumormikroumgebung dieser Zellen parametrisiert und quantifiziert werden. Abschließend wurde unter Anwendung eines Random forest-Klassifikators die diagnostische Potenz digital-pathologischer Profile evaluiert und validiert.
As an integral part of ALICE, the dedicated heavy ion experiment at CERN’s Large Hadron Collider, the Transition Radiation Detector (TRD) contributes to the experiment’s tracking, triggering and particle identification. Central element in the TRD’s processing chain is its trigger and readout processor, the Global Tracking Unit (GTU). The GTU implements fast triggers on various signatures, which rely on the reconstruction of up to 20 000 particle track segments to global tracks, and performs the buffering and processing of event raw data as part of a complex detector readout tree.
The high data rates the system has to handle and its dual use as trigger and readout processor with shared resources and interwoven processing paths require the GTU to be a unique, high-performance parallel processing system. To achieve high data taking efficiency, all elements of the GTU are optimized for high running stability and low dead time.
The solutions presented in this thesis for the handling of readout data in the GTU, from the initial reception to the final assembly and transmission to the High-Level Trigger computer farm, address all these aspects. The presented concepts employ multi-event buffering, in-stream data processing, extensive embedded diagnostics, and advanced features of modern FPGAs to build a robust high-performance system that can conduct the high- bandwidth readout of the TRD with maximum stability and minimized dead time. The work summarized here not only includes the complete process from the conceptual layout of the multi-event data handling and segment control, but also its implementation, simulation, verification, operation and commissioning. It also covers the system upgrade for the second data taking period and presents an analysis of the actual system performance.
The presented design of the GTU’s input stage, which is comprised of 90 FPGA-based nodes, is built to support multi-event buffering for the data received from the 18 TRD supermodules on 1080 optical links at the full sender aggregate net bandwidth of 2.16 Tbit/s. With careful design of the control logic and the overall data path, the readout on the 18 concentrator nodes of the supermodule stage can utilize an effective aggregate output bandwidth of initially 3.33 GiB/s, and, after the successful readout bandwidth upgrade, 6.50 GiB/s via 18 optical links. The high possible readout link utilization of more than 99 % and the intermediate buffering of events on the GTU helps to keep the dead time associated with the local event building and readout typically below 10%. The GTU has been used for production data taking since start-up of the experiment and ever since performs the event buffering, local event building and readout for the TRD in a correct, efficient and highly dependable fashion.
Viele Methoden wurden in dieser Arbeit vorgestellt, die sich mit dem Hauptziel der automatischen Dokumentenanalyse auf semantischer Ebene befassen. Um das Hauptziel zu erreichen, mussten wir jedoch zunächst eine solide Basis entwickeln, um das Gesamtbild zu vervollständigen. So wurden verschiedene Methoden und Werkzeuge entwickelt, die verschiedene Aspekte des NLP abdecken. Das Zusammenspiel dieser Methoden ermöglichte es, unser Ziel erfolgreich zu erreichen. Neben der automatischen Dokumentenanalyse legen wir großen Wert auf die drei Prinzipien von Effizienz, Anwendbarkeit und Sprachunabhängigkeit. Dadurch waren die entwickelten Tools für die Anwendungen bereit. Die Größe und Sprache der zu analysierenden Daten ist kein Hindernis mehr, zumindest für die im Bezug auf die von Wikipedia unterstützten Sprachen.
Einen großen Beitrag dazu leistete TextImager, das Framework, dass für die zugrunde liegende Architektur verschiedener Methoden und die gesamte Vorverarbeitung der Texte verantwortlich ist. TextImager ist als Multi-Server und Multi-Instanz-Cluster konzipiert, sodass eine verteilte Verarbeitung von Daten ermöglicht wird. Hierfür werden Cluster-Management-Dienste UIMA-AS und UIMA-DUCC verwendet. Darüber hinaus ermöglicht die Multi-Service-Architektur von TextImager die Integration beliebiger NLP-Tools und deren gemeinsame Ausführung. Zudem bietet der TextImager eine webbasierte Benutzeroberfläche, die eine Reihe von interaktiven Visualisierungen bietet, die die Ergebnisse der Textanalyse darstellen. Das Webinterface erfordert keine Programmierkenntnisse - durch einfaches Auswählen der NLP-Komponenten und der Eingabe des Textes wird die Analyse gestartet und anschließend visualisiert, so dass auch Nicht-Informatiker mit diesen Tools arbeiten können.
Zudem haben wir die Integration des statistischen Frameworks R in die Funktionalität und Architektur von TextImager demonstriert. Hier haben wir die OpenCPU-API verwendet, um R-Pakete auf unserem eigenen R-Server bereitzustellen. Dies ermöglichte die Kombination von R-Paketen mit den modernsten NLP-Komponenten des TextImager. So erhielten die Funktionen der R-Pakete extrahierte Informationen aus dem TextImager, was zu verbesserten Analysen führte.
Darüber hinaus haben wir interaktive Visualisierungen integriert, um die von R abgeleiteten Informationen zu visualisieren.
Einige der im TextImager entwickelten Visualisierungen sind besonders herausragend und haben in vielen Bereichen Anwendung gefunden. Ein Beispiel dafür ist PolyViz, ein interaktives Visualisierungssystem, das die Darstellung eines multipartiten Graphen ermöglicht. Wir haben PolyViz anhand von zwei verschiedenen Anwendungsfällen veranschaulicht.
SemioGraph, eine Visualisierungstechnik zur Darstellung multikodaler Graphen wurde auch vorgestellt. Die visuellen und interaktiven Funktionen von SemioGraph wurden mit einer Anwendung zur Visualisierung von Worteinbettungen vorgestellt. Wir haben gezeigt, dass verschiedene Modelle zu völlig unterschiedlichen Grafiken führen können. So kann Semiograph bei der Suche nach Worteinbettungen für bestimmte NLP-Aufgaben helfen.
Inspiriert von all den Textvisualisierungen im TextImager ist die Idee für text2voronoi geboren. Hier stellten wir einen neuartigen Ansatz zur bildgetriebenen Textklassifizierung vor, der auf einem Voronoi-Diagram linguistischer Merkmale basiert. Dieser Klassifikationsansatz wurde auf die automatische Patientendiagnose angewendet und wir haben gezeigt, dass wir das traditionelle Bag-Of-Words-Modell sogar übertreffen. Dieser Ansatz ermöglicht es, die zugrunde liegenden Merkmale anschließend zu analysieren und damit einen ersten Schritt zur Lösung der Black Box zu machen.
Wir haben text2voronoi auf literarische Werke angewendet und die entstandenen Visualisierungen auf einer webbasierten Oberfläche (LitViz) präsentiert. Hier ermöglichen wir den Vergleich von Voronoi-Diagrammen der verschiedenen Literaturen und damit den visuellen Vergleich der Sprachstile der zugrunde liegenden Autoren.
Mit unserer Kompetenz in der Vorverarbeitung und der Analyse von Texten sind wir unserem Ziel der semantischen Dokumentenanalyse einen Schritt näher gekommen. Als nächstes haben wir die Auflösung der Sinne auf der Wortebene untersucht. Hier stellten wir fastSense vor, ein Disambigierungsframework, das mit großen Datenmengen zurecht kommt. Um dies zu erreichen, haben wir einen Disambiguierungskorpus erstellt, der auf Wikipedias 221965 Disambiguierungsseiten basiert, wobei die sich auf 825179 Sinne beziehen. Daraus resultierten mehr als 50 Millionen Datensätze, die fast 50 GB Speicherplatz benötigten. Wir haben nicht nur gezeigt, dass fastSense eine so große Datenmenge problemlos verarbeiten kann, sondern auch, dass wir mit unseren Wettbewerbern mithalten und sie bei einigen NLP-Aufgaben sogar übertreffen können.
Jetzt, da wir den Wörtern Sinne zuordnen können, sind wir der semantischen Dokumentenanalyse einen weiteren Schritt näher gekommen. Je mehr Informationen wir aus einem Text und seinen Wörtern gewinnen können, desto genauer können wir seinen Inhalt analysieren. Wir stellten zudem einen netzwerktheoretischen Ansatz zur Modellierung der Semantik großer Textnetzwerke am Beispiel der deutschen Wikipedia vor. Zu diesem Zweck haben wir einen Algorithmus namens text2ddc entwickelt, um die thematische Struktur eines Textes zu modellieren. Dabei basiert das Modell auf einem etablierten Klassifikationsschema, nämlich der Dewey Decimal Classification. Mit diesem Modell haben wir gezeigt, wie man aus der Vogelperspektive die Hervorhebung und Verknüpfung von Themen, die sich in Millionen von Dokumenten manifestiert, darstellt. So haben wir eine Möglichkeit geschaffen, die thematische Dynamik von Dokumentnetzwerken automatisch zu visualisieren. Die Trainings- und Testdaten, die wir in diesem Kapitel hatten, bestanden jedoch hauptsächlich aus kurzen Textausschnitten. Zudem haben wir DDC Korpora erstellt, indem wir Informationen aus Wikidata, Wikipedia und der von der Deutschen Nationalbibliothek verwalteten Gemeinsamen Normdatei (GND) vereinigt haben. Auf diese Weise konnten wir nicht nur die Datenmenge erhöhen, sondern auch Datensätze für viele bisher unzugängliche Sprachen erstellen. Wir haben text2ddc so weit optimiert, dass wir einen F-score von 87.4% erzielen für die 98 Klassen der zweiten DDC-Stufe. Die Vorverarbeitung von TextImager und die Disambiguierung durch fastSense hatten einen großen Einfluss darauf. Für jedes Textstück berechnet text2ddc eine Wahrscheinlichkeitsverteilung über die DDC-Klassen berechnen
Der klassifikatorinduzierte semantische Raum von text2ddc wurde auch zur Verbesserung weiterer NLP-Methoden genutzt. Dazu gehört auch text2wiki, ein Framework für automatisches Tagging nach dem Wikipedia-Kategoriensystem. Auch hier haben wir einen klassifikatorinduzierten semantischen Raum, aber diesmal basiert er auf dem Wikipedia-Kategoriensystem. Ein großer Vorteil dieses Modells ist die Präzision und Tiefe der behandelten Themen und das sich ständig weiterentwickelnde Kategoriesystem. Damit sind auch die Kriterien eines offenen Themenmodells erfüllt. Um die Vorteile von text2wiki zu demonstrieren, haben wir anschließend die von text2wiki bereitgestellten Themenvektoren verwendet, um text2ddc zu verbessern, so dass sich beide Systeme gegenseitig verbessern können. Die Synergie zwischen den erstellten Methoden in dieser Dissertation war entscheidend für den Erfolg jeder einzelnen Methode.
Monte Carlo methods : barrier option pricing with stable Greeks and multilevel Monte Carlo learning
(2021)
For discretely observed barrier options, there exists no closed solution under the Black-Scholes model. Thus, it is often helpful to use Monte Carlo simulations, which are easily adapted to these models. However, as presented above, the discontinuous payoff may lead to instability in option's sensitivities for Monte Carlo algorithms.
This thesis presents a new Monte Carlo algorithm that can calculate the pathwise sensitivities for discretely monitored barrier options. The idea is based on Glasserman and Staum's one-step survival strategy and the results of Alm et al., with which we can stably determine the option's sensitivities such as Delta and Vega by finite-differences. The basic idea of Glasserman and Staum is to use a truncated normal distribution, which excludes the values above the barrier (e.g.\ for knock-up-out options), instead of sampling from the full normal distribution. This approach avoids the discontinuity generated by any Monte Carlo path crossing the barrier and yields a Lipschitz-continuous payoff function.
The new part will be to develop an extended algorithm that estimates the sensitivities directly, without simulation at multiple parameter values as in finite-difference.
Consider the local volatility model, which is a generalisation of the Black-Scholes model. Although standard Monte Carlo algorithms work well for the pricing of continuously monitored barrier options within this model, they often do not behave stably with respect to numerical differentiation.
To bypass this problem, one would generally either resort to regularised differentiation schemes or derive an algorithm for precise differentiation. Unfortunately, while the widespread solution of using a Brownian bridge approach leads to accurate first derivatives, they are not Lipschitz-continuous. This leads to instability with respect to numerical differentiation for second-order Greeks.
To alleviate this problem - i.e. produce Lipschitz-continuous first-order derivatives - and reduce variance, we generalise the idea of one-step survival to general scalar stochastic differential equations. This approach leads to the new one-step survival Brownian bridge approximation, which allows for stable second-order Greeks calculations.
To show the new approach's numerical efficiency, we present a new respective Monte Carlo pathwise sensitivity estimator for the first-order Greeks and study different methods to compute second-order Greeks stably. Finally, we develop a one-step survival Brownian bridge multilevel Monte Carlo algorithm to reduce the computational cost in practice.
This thesis proves unbiasedness and variance reduction of our new, one-step survival version with respect to the classical, Brownian bridge approach. Furthermore, we will present a new convergence result for the Brownian bridge approach using the Milstein scheme under certain conditions. Overall, these properties imply convergence of the new one-step survival Brownian bridge approach.
In recent years, deep learning has become pervasive in various fields. As a family of machine learning methods it is used in a broad set of applications, such as image processing, voice recognition, email filtering, computer vision. Most modern deep learning algorithms are based on artificial neural networks inspired by the biological neural networks constituting animal brains. Also in computational finance deep learning may be of use: Consider there is no closed-solution available for an option price, Monte Carlo simulations are substantially for estimation. Instead of persistently contributing new price computations arising from an updated volatility term, one could replace these by evaluating a neural network.
If an according neural network is available, the evaluation could lead to substantial savings and be highly efficient. I.e., once trained, a neural network could save further expensive estimations. However, in practice, the challenge is the training process of the neural network.
We study and compare two generic neural network training algorithms' computational complexity. Then, we introduce a new multilevel training algorithm that combines a deep learning algorithm with the idea of multilevel Monte Carlo path simulation. The idea is to train several neural networks with training data computed from the so-called level estimators of the multilevel Monte Carlo approach introduced by Giles. We show that the new method can reduce computational complexity by formulating a complexity theorem.
The main topic of the present thesis is scene flow estimation in a monocular camera system. Scene flow describes the joint representation of 3D positions and motions of the scene. A special focus is placed on approaches that combine two kinds of information, deep-learning-based single-view depth estimation and model-based multi-view geometry.
The first part addresses single-view depth estimation focussing on a method that provides single-view depth information in an advantageous form for monocular scene flow estimation methods. A convolutional neural network, called ProbDepthNet, is proposed, which provides pixel-wise well-calibrated depth distributions. The experiments show that different strategies for quantifying the measurement uncertainty provide overconfident estimates due to overfitting effects. Therefore, a novel recalibration technique is integrated as part of the ProbDepthNet, which is validated to improve the calibration of the uncertainty measures. The monocular scene flow methods presented in the subsequent parts confirm that the integration of single-view depth information results in the best performance if the neural network provides depth distributions instead of single depth values and contains a recalibration.
Three methods for monocular scene flow estimation are presented, each one designed to combine multi-view geometry-based optimization with deep learning-based single-view depth estimation such as ProbDepthNet. While the first method, SVD-MSfM, performs the motion and depth estimation as two subsequent steps, the second method, Mono-SF, jointly optimizes the motion estimates and the depth structure. Both methods are tailored to address scenes, where the objects and motions can be represented by a set of rigid bodies. Dynamic traffic scenes are one kind of scenes that essentially fulfill this characteristic. The method, Mono-Stixel, uses an even more specialized scene model for traffic scenes, called stixel world, as underlying scene representation.
The proposed methods provide new state of the art for monocular scene flow estimation with Mono-SF being the first and leading monocular method on the KITTI scene flow benchmark at the time of submission of the present thesis. The experiments validate that both kind of information, the multi-view geometric optimization and the single-view depth estimates, contribute to the monocular scene flow estimates and are necessary to achieve the new state of the art accuracy.
Antimicrobial resistant infections arise as a consequential response to evolutionary mechanisms within microbes which cause them to be protected from the effects of antimicrobials. The frequent occurrence of resistant infections poses a global public health threat as their control has become challenging despite many efforts. The dynamics of such infections are driven by processes at multiple levels. For a long time, mathematical models have proved valuable for unravelling complex mechanisms in the dynamics of infections. In this thesis, we focus on mathematical approaches to modelling the development and spread of resistant infections at between-host (population-wide) and within-host (individual) levels.
Within an individual host, switching between treatments has been identified as one of the methods that can be employed for the gradual eradication of resistant strains on the long term. With this as motivation, we study the problem using dynamical systems and notions from control theory. We present a model based on deterministic logistic differential equations which capture the general dynamics of microbial resistance inside an individual host. Fundamentally, this model describes the spread of resistant infections whilst accounting for evolutionary mutations observed in resistant pathogens and capturing them in mutation matrices. We extend this model to explore the implications of therapy switching from a control theoretic perspective by using switched systems and developing control strategies with the goal of reducing the appearance of drug resistant pathogens within the host.
At the between-host level, we use compartmental models to describe the transmission of infection between multiple individuals in a population. In particular, we make a case study of the evolution and spread of the novel coronavirus (SARS-CoV-2) pandemic. So far, vaccination remains a critical component in the eventual solution to this public health crisis. However, as with many other pathogens, vaccine resistant variants of the virus have been a major concern in control efforts by governments and all stakeholders. Using network theory, we investigate the spread and transmission of the disease on social networks by compartmentalising and studying the progression of the disease in each compartment, considering both the original virus strain and one of its highly transmissible vaccine-resistant mutant strains. We investigate these dynamics in the presence of vaccinations and other interventions. Although vaccinations are of absolute importance during viral outbreaks, resistant variants coupled with population hesitancy towards vaccination can lead to further spread of the virus.
Der Inhalt dieser Arbeit ist die Entwicklung und Evaluation einer mobilen Webanwendung für die Annotation von Texten. Dem Benutzer ist es durch diese Webanwendung, im folgenden auch MobileAnnotator genannt, möglich Wörter und Textausschnitte zu kategorisieren oder auch mit Wissensquellen, zum Beispiel Wikipedia, zu verknüpfen. Der MobileAnnotator ist dabei für mobile Endgeräte ausgelegt und insbesondere für Smartphones optimiert worden.
Für die Funktionalität verwendet der MobileAnnotator die Architektur des bereits existierenden und etablierten TextAnnotators. Dieser stellt bereits eine Vielzahl von Annotations Werkzeugen bereit, von denen zwei auf den MobileAnnotator übertragen wurden. Da der TextAnnotator vollständig für einen Desktopbetrieb ausgelegt wurde, ist es jedoch nicht möglich diese Werkzeuge ohne Anpassungen für ein mobiles Gerät umzubauen. Der MobileAnnotator beschränkt sich somit auf ein Mindestmaß an Funktionen dieser Werkzeuge um sie dem Benutzer in geeigneter Art und Weise verfügbar zu machen.
Für die Evaluation der Benutzerfreundlichkeit des MobileAnnotator und dessen Werkzeuge wurde anschließend eine Studie durchgeführt. Den Probanten war es innerhalb der Studie möglich Aussagen über die Bedienbarkeit des MobileAnnotators zu treffen und einen Vergleich zwischen dem Mobile- und TextAnnotator zu ziehen.
Biologische Signalwege bilden komplexe Netzwerke aus, um die Zellantwort sensibel regulieren zu können. Systembiologische Ansätze werden eingesetzt, um biologische Systeme anhand von Computer-gestützten Modellen zu untersuchen. Ein mathematisches Modell erlaubt, neben der logischen Erfassung der Regulation des biologischen Systems, die systemweite Simulation des dynamischen Verhaltens und Analyse der Robustheit und Anfälligkeit.
Der TNFR1-vermittelte Signalweg reguliert essenzielle Zellvorgänge wie Entzündungsantworten,
Proliferation und Zelltod. TNFR1 wird von dem Zytokin TNF-α stimuliert und fördert daraufhin die Bildung verschiedener makromolekularer Komplexe, welche unterschiedliche Zellantworten einleiten, von der Aktivierung des Transkriptionsfaktors NF-κB, welcher die Expression von proliferationsfördernden Genen reguliert, bis zu zwei Formen des Zelltods, der Apoptose und der Nekroptose. Die Regulation der verschiedenen Zellantworten wird auch als molekularer Schalter bezeichnet. Die exakten molekularen Vorgänge, welche die Zellantwort modulieren, sind noch nicht vollständig entschlüsselt. Eine Fehlregulation des Signalwegs kann chronische Entzündungen hervorrufen oder die Entstehung von Tumoren fördern.
In dieser Thesis haben wir die neuesten Erkenntnisse der Forschung des TNFR1-Signalwegs anhand von umfangreichen Interaktionsdaten aus der Literatur erstmals in einem Petrinetz-Modell erfasst und analysiert. Das manuell kuratierte Modell umfasst die sequenziellen Prozesse der NF-κB-Aktivierung, Apoptose und Nekroptose und berücksichtigt den Einfluss posttranslationaler Modifikationen.
Weiterhin wurden Analysemethoden für Signalwegs-Modelle entwickelt, welche die spezifischen Anforderungen dieser biologischen Systeme berücksichtigen und eine biologisch motivierte Netzwerkanalyse ermöglichen. Die Manatee-Invarianten identifizieren Signalflüsse im Gleichgewichtszustand in Modellen, die Zyklen aufweisen, und werden als Linearkombination von Transitions-Invarianten gebildet. Diese Signalflüsse erfassen idealerweise einen Prozess von der Rezeptorstimulation zur Zellantwort in einem Modell eines Signalwegs. Die Bestimmung aller möglichen Signalflüsse in Modellen von Signalwegen ist eine notwendige Voraussetzung für weitere biologisch motivierte Analysen, wie die in silico-Knockout Analyse. Wir haben ebenfalls ein neues Konzept zur Untersuchung von in silico-Knockouts vorgestellt. Die Effekte der in silico-Knockouts auf einzelne Komplexe und Prozesse des Signalwegs werden in der in silico-Knockout-Matrix repräsentiert. Wir haben die Software-Anwendung isiKnock entwickelt, welche beide Konzepte kombiniert und eine systematische Knockout-Analyse von Petrinetz-Modellen unterstützt.
Das Petrinetz-Modell des TNFR1-Signalwegs wurde auf seine elementaren Eigenschaften geprüft und die etablierten Analysen wie Platz-Invarianten und Transitions-Invarianten durchgeführt. Hierbei konnten die Transitions-Invarianten nicht in allen Fällen komplette biologische Signalflüsse beschreiben. Wir haben ebenfalls die neu vorgestellten Methoden auf das Petrinetz-Modell angewandt. Anhand der Manatee-Invarianten konnten wir die zusammenhängenden Signalflüsse identifizieren und nach ihrem biologischen Ausgang klassifizieren sowie die Auswirkungen der Rückkopplungen untersuchen. Wir konnten zeigen, dass die survival-Antwort durch die Aktivierung von NF-κB am häufigsten auftritt, danach die Apoptose, gefolgt von der Nekroptose. Die alternativen Signalflüsse in Form der Manatee-Invarianten spiegeln die Robustheit des biologischen Systems wider. Wir führten eine ausgiebige in silico-Knockout-Analyse basierend auf den Manatee-Invarianten durch, um die Proteine des Signalwegs nach ihrem Einfluss einzustufen und zu gruppieren. Die Proteine des Komplex I wiesen hierbei den größten Einfluss auf, angeführt von der Rezeptorstimulation und RIP1. Wir betrachteten und diskutierten die Regulation des molekularen Schalters anhand der Knockout-Analyse von selektierten Proteinen und deren Auswirkung auf wichtige Komplexe im Modell. Wir identifizierten die Ubiquitinierung in Komplex I sowie die NF-κB-abhängige Genexpression als die wichtigen Kontrollpunkte des TNFR1-Signalwegs. In Komplex II ist die Regulation der Aktivierung der Caspase-Aktivität entscheidend.
Die umfangreiche Netzwerkanalyse basierend auf Manatee-Invarianten und systematischer in silico-Knockout-Analyse verifizierte das Petrinetz-Modell und erlaubte die Untersuchung der Robustheit und Anfälligkeit des Systems. Die neu entwickelten Methoden ermöglichen eine fundierte, biologisch relevante Untersuchung von in silico-Modellen von Signalwegen. Der systembiologische Ansatz unterstützt die Aufklärung der Regulation und Funktion des verflochtenen Netzwerks des TNFR1-Signalwegs.