Fakultät für Mathematik, Informatik und Statistik - Digitale Hochschulschriften der LMU - Teil 01/02

In this thesis, we prove that many asymptotic invariants of closed manifolds depend only on the image of the fundamental class under the classifying map of the universal covering. Examples include numerical invariants that reflect the asymptotic behaviour of the universal covering, like the minimal volume entropy and the spherical volume, as well as properties that are qualitative measures for the largeness of a manifold and its coverings, like enlargeability and hypersphericity.

Another important class of invariants that share the above invariance property originates from universal volume bounds. The main example is the systolic constant, which encodes the relation between short noncontractible loops and the volume of a manifold. Further interesting examples are provided by the optimal constants in Gromov's filling inequalities, for which we show that they depend only on the dimension and orientability.

Considering higher-dimensional generalizations of the systolic constant, a complete answer to the question about the existence of stable systolic inequalities is given. In the spirit of the results mentioned already, we also prove that the stable systolic constant depends only on the image of the fundamental class in a suitable Eilenberg-Mac Lane space.

Die vorliegende Arbeit befasst sich mit der Entwicklung interaktiver 3D-Anwendungen. Interaktive 3D-Grafik wird heutzutage in den verschiedensten Domänen eingesetzt, z. B. im e-Commerce-, Unterhaltungs- und Ausbildungsbereich.

Dennoch stellt die Entwicklung einer umfangreicheren 3D-Anwendung nach wie vor eine Herausforderung dar. Programmcode und 3D-Inhalte werden i. d. R. von verschiedenen Entwicklern erstellt, die unterschiedliches Fachwissen besitzen und mit völlig verschiedenartigen Werkzeugen arbeiten. Diese Situation führt häufig zu Problemen bei der Integration der erstellten Anwendungskomponenten in ein komplexes interaktives 3D-Gesamtsystem. So können etwa Inkonsistenzen auftreten, die einen korrekten Zugriff des Programms auf die 3D-Inhalte zur Laufzeit verhindern. Zudem fehlen Konzepte und Werkzeuge zur Unterstützung einer strukturierten interdisziplinären 3D-Entwicklung.

In der vorliegenden Arbeit wird ein neuartiger Lösungsansatz für die genannten Probleme vorgestellt. Es handelt sich dabei um eine Familie domänenspezifischer Sprachen, die für einen Einsatz in der Entwurfsphase vor der Implementierung im 3D-Entwicklungsprozess konzipiert wurden. Basissprache der Familie, die durch weitere Sprachkomponenten ergänzt wird, ist die Scene Structure and Integration Modelling Language (kurz SSIML). Mittels visueller Modelle lassen sich -- werkzeuggestützt -- Verknüpfungen zwischen Programmkomponenten und 3D-Inhalten spezifizieren. Durch die automatische Erzeugung von Codeskeletten aus einem Modell, die sowohl dem 3D-Designer als auch dem Programmierer als zu vervollständigende Vorlagen dienen, kann die Konsistenz zwischen den einzelnen Anwendungsbestandteilen sichergestellt werden. Neben der Verknüpfung von Programmcode und 3D-Inhalten sind die Strukturierung und Modularisierung von 3D-Inhalten, die aufgabenorientierte 3D-Visualisierung, 3D-Verhalten und Animation und Augmented Realitiy-Anwendungen weitere wichtige Aspekte, die durch die Mitglieder der SSIML-Sprachfamilie abgedeckt werden. Außerdem wird in der vorliegenden Arbeit ein 3D-Entwicklungsprozess skizziert, der einen sinnvollen Einbezug der vorgestellten Konzepte und Werkzeuge erlaubt.

Recursive partitioning methods from machine learning are being widely applied in many scientific fields such as, e.g., genetics and bioinformatics. The present work is concerned with the two main problems that arise in recursive partitioning, instability and biased variable selection, from a statistical point of view. With respect to the first issue, instability, the entire scope of methods from standard classification trees over robustified classification trees and ensemble methods such as TWIX, bagging and random forests is covered in this work. While ensemble methods prove to be much more stable than single trees, they also loose most of their interpretability. Therefore an adaptive cutpoint selection scheme is suggested with which a TWIX ensemble reduces to a single tree if the partition is sufficiently stable. With respect to the second issue, variable selection bias, the statistical sources of this artifact in single trees and a new form of bias inherent in ensemble methods based on bootstrap samples are investigated. For single trees, one unbiased split selection criterion is evaluated and another one newly introduced here. Based on the results for single trees and further findings on the effects of bootstrap sampling on association measures, it is shown that, in addition to using an unbiased split selection criterion, subsampling instead of bootstrap sampling should be employed in ensemble methods to be able to reliably compare the variable importance scores of predictor variables of different types. The statistical properties and the null hypothesis of a test for the random forest variable importance are critically investigated. Finally, a new, conditional importance measure is suggested that allows for a fair comparison in the case of correlated predictor variables and better reflects the null hypothesis of interest.

Knowledge Discovery in Databases (KDD) is the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data. The core step of the KDD process is the application of a Data Mining algorithm in order to produce a particular enumeration of patterns and relationships in large databases. Clustering is one of the major data mining techniques and aims at grouping the data objects into meaningful classes (clusters) such that the similarity of objects within clusters is maximized, and the similarity of objects from different clusters is minimized. This can serve to group customers with similar interests, or to group genes with related functionalities.

Currently, a challenge for clustering-techniques are especially high dimensional feature-spaces. Due to modern facilities of data collection, real data sets usually contain many features. These features are often noisy or exhibit correlations among each other. However, since these effects in different parts of the data set are differently relevant, irrelevant features cannot be discarded in advance. The selection of relevant features must therefore be integrated into the data mining technique.

Since about 10 years, specialized clustering approaches have been developed to cope with problems in high dimensional data better than classic clustering approaches. Often, however, the different problems of very different nature are not distinguished from one another. A main objective of this thesis is therefore a systematic classification of the diverse approaches developed in recent years according to their task definition, their basic strategy, and their algorithmic approach. We discern as main categories the search for clusters (i) w.r.t. closeness of objects in axis-parallel subspaces, (ii) w.r.t. common behavior (patterns) of objects in axis-parallel subspaces, and (iii) w.r.t. closeness of objects in arbitrarily oriented subspaces (so called correlation cluster).

For the third category, the remaining parts of the thesis describe novel approaches. A first approach is the adaptation of density-based clustering to the problem of correlation clustering. The starting point here is the first density-based approach in this field, the algorithm 4C. Subsequently, enhancements and variations of this approach are discussed allowing for a more robust, more efficient, or more effective behavior or even find hierarchies of correlation clusters and the corresponding subspaces. The density-based approach to correlation clustering, however, is fundamentally unable to solve some issues since an analysis of local neighborhoods is required. This is a problem in high dimensional data. Therefore, a novel method is proposed tackling the correlation clustering problem in a global approach. Finally, a method is proposed to derive models for correlation clusters to allow for an interpretation of the clusters and facilitate more thorough analysis in the corresponding domain science. Finally, possible applications of these models are proposed and discussed.

In dieser Arbeit werden einige Aussagen über symplektische Strukturen auf 4-dimensionalen Mannigfaltigkeiten und Kontaktstrukturen auf 5-dimensionalen Mannigfaltigkeiten bewiesen. Wir untersuchen zunächst den Zusammenhang zwischen dem symplektischen und dem holomorphen Minimalitätsbegriff für Kählerflächen. Außerdem beweisen wir ein Resultat über die Irreduzibilität minimaler, einfach-zusammenhängender symplektischer 4- Mannigfaltigkeiten unter zusammenhängender Summe und eine Aussage über die konformen Systolen symplektischer 4-Mannigfaltigkeiten. Als nächstes betrachten wir die Konstruktion von differenzierbaren 4-dimensionalen Mannigfaltigkeiten durch die verallgemeinerte Fasersumme. Für den Fall, dass die Summation entlang eingebetteter Flächen mit trivialem Normalenbündel erfolgt, werden die ganzzahligen Homologiegruppen und im symplektischen Fall auch die kanonische Klasse der Fasersumme berechnet. Wir betrachten verschiedene Anwendungen, insbesondere hinsichtlich der Geographie einfach-zusammenhängender symplektischer 4-Mannigfaltigkeiten, deren kanonische Klasse durch eine vorgegebene natürliche Zahl teilbar ist. Wir zeigen auch, dass man mit geeigneten verzweigten Überlagerungen von komplexen Flächen vom allgemeinen Typ einfach-zusammenhängende algebraische Flächen konstruieren kann, deren kanonische Klasse eine vorgegebene Teilbarkeit besitzt. Im zweiten Teil der Arbeit betrachten wir die Boothby-Wang Konstruktion von Kontaktstrukturen auf Kreisbündeln über symplektischen Mannigfaltigkeiten. Zusammen mit den Resultaten über Geographie aus dem ersten Teil der Arbeit zeigen wir, dass es auf bestimmten einfach-zusammenhängenden 5-Mannigfaltigkeiten Kontaktstrukturen gibt, die nicht äquivalent sind, aber die in derselben (nicht-trivialen) Homotopieklasse von Fast-Kontaktstrukturen liegen.

"In this thesis we follow two fundamental concepts from the {\it higher dimensional algebra}, the {\it categorification} and the {\it internalization}. From the geometric point of view, so far the most general torsors were defined in the dimension $n=1$, by {\it actions of categories and groupoids}. In the dimension $n=2$, Mauri and Tierney, and more recently Baez and Bartels from the different point of view, defined less general 2-torsors with the structure 2-group.

Using the language of simplicial algebra, Duskin and Glenn defined actions and torsors internal to any Barr exact category $\E$, in an arbitrary dimension $n$. This actions are simplicial maps which are {\it exact fibrations} in dimensions $m \geq n$, over special simplicial objects called {\it n-dimensional Kan hypergroupoids}.

The correspondence between the geometric and the algebraic theory in the dimension $n=1$ is given by the Grothendieck nerve construction, since the Grothendieck nerve of a groupoid is precisely a 1-dimensional Kan hypergroupoid. One of the main results is that groupoid actions and groupoid torsors become simplicial actions and simplicial torsors over the corresponding 1-dimensional Kan hypergroupoids, after the application of the Grothendieck nerve functor.

The main result of the thesis is a generalization of this correspondence to the dimension $n=2$. This result is achieved by introducing two new algebraic and geometric concepts, {\it actions of bicategories} and {\it bigroupoid 2-torsors}, as a categorification and an internalization of actions of categories and groupoid torsors. We provide the classification of bigroupoid 2-torsors by {\it the second nonabelian cohomology} with coefficients in the structure bigroupoid. The second nonabelian cohomology is defined by means of the third new concept in the thesis, a {\it small 2-fibration} corresponding to an internal bigroupoid in the category $\E$. The correspondence between the geometric and the algebraic theory in the dimension $n=2$ is given by the Duskin nerve construction for bicategories and bigroupoids since the Duskin nerve of a bigroupoid is precisely a 2-dimensional Kan hypergroupoid. Finally, the main results of the thesis is that bigroupoid actions and bigroupoid 2-torsors become simplicial actions and simplicial 2-torsors over the corresponding 2-dimensional Kan hypergroupoids, after the application of the Duskin nerve functor."

Microarray-Daten werden in letzter Zeit häufig genutzt, um mit Hilfe verschiedener Verfahren Netzwerke der Gen-Gen-Interaktion zu generieren. Die vorliegende Arbeit beschäftigt sich mit Validierungsstudien solcher Verfahren. Der Startpunkt einer Validierungsstudie ist ein ungerichteter Graph, der biologische Strukturen repräsentieren soll. In dieser Arbeit wird motiviert, Graphen zu benutzen, die aus Microarray-Daten geschätzt worden sind. Nachdem ein Graph gewählt worden ist, werden Daten einer multivariaten Normalverteilung erzeugt, die durch eine zufällige Kovarianzmatrix charakterisiert ist. Diese Matrix muss symmetrisch und positiv definit sein, aber zusätzlich wird für eine nicht vorhandene Kante im Graphen gefordert, dass der zugehörige Eintrag in der Matrix Null ist.

In dieser Arbeit wird ein neuer Ansatz vorgestellt, der es ermöglicht, symmetrische, positiv definite Matrizen mit Nebenbedingungen zu erzeugen. Diese Methode beruht auf der Moralisierung eines Graphen. Ein gerichteter, azyklischer Graph wird moralisiert, indem die gerichteten Kanten durch ungerichtete Kanten ersetzt werden und zusätzlich die Eltern eines jeden Knotens paarweise miteinander verbunden werden. Der zentrale Schritt bei der

Erstellung der Matrizen mit Nebenbedingungen liegt in der Umkehrung des Moralisierungsvorganges. In dieser

Arbeit wird die Klasse der Graphen eingeführt, die Resultat einer Moralisierung sein könnten

- die prämoralisierbaren Graphen - und es wird ein Verfahren definiert, welches entscheidet, ob ein Graph

prämoralisierbar ist und gegebenenfalls eine Umkehrung der Moralisierung durchführt. Die erzeugten Matrizen

sollen als Korrelationsmatrizen für die Validierungsstudien genutzt werden. Dazu wird das vorgestellte Verfahren

an einen Optimierungsalgorithmus gekoppelt, um die gewünschten Matrizen zu erzeugen, deren Diagonalelemente

identisch 1 sind und für die die nicht als Null vorgegebenen Werte nahe 1 bzw. -1 liegen.

Nicht jeder Graph ist prämoralisierbar. Da diese Eigenschaft notwendig ist für das Verfahren zur Erzeugung der

Matrizen mit Nebenbedingungen, wird eine empirische Studie durchgeführt, die zeigt, dass ein Großteil der aus

Microarray-Daten geschätzten Graphen auch prämoralisierbar ist.

Die Arbeit schließt mit praktischen Anwendungen. Die Validierung eines bekannten Algorithmus zum Schätzen

von Netzwerken wird durchgeführt und es wird ein Ansatz vorgestellt, mit dem man graphische Strukturen, die

aus Microarray-Daten geschätzt worden sind, vergleichen kann, um signifikante Unterschiede zu finden.

This thesis studies the decidability of conversions in typed lambda-calculi, along with the algorithms allowing for this decidability. Our study takes in consideration conversions going beyond the traditional beta, eta, or permutative conversions (also called commutative conversions). To decide these conversions, two classes of algorithms compete, the algorithms based on rewriting, here the goal is to decompose and orient the conversion so as to obtain a convergent system, these algorithms then boil down to rewrite the terms until they reach an irreducible forms; and the "reduction free" algorithms where the conversion is decided recursively by a detour via a meta-language. Throughout this thesis, we strive to explain the latter thanks to the former.