In recent years, we started to define our life through experiences we make instead of objectswe buy. To attend a concert of our favorite musician may be more important for us thanowning an expensive stereo system. Similarly, we define interactive systems not only by thequality of the display or its usability, but rather by the experiences we can make when usingthe device. A cell phone is primarily built for making calls and receiving text messages,but on an emotional level it might provide a way to be close to our loved ones, even thoughthey are far away sometimes. When designing interactive technology, we do not only haveto answer the question how people use our systems, but also why they use them. Thus,we need to concentrate on experiences, feelings and emotions arising during interaction.Experience Design is an approach focusing on the story that a product communicates beforeimplementing the system. In an interdisciplinary team of psychologists, industrial designers, product developers andspecialists in human-computer interaction, we applied an Experience Design process to theautomotive domain. A major challenge for car manufacturers is the preservation of theseexperiences throughout the development process. When implementing interactive systemsengineers rely on technical requirements and a set of constraints (e.g., safety) oftentimescontradicting aspects of the designed experience. To resolve this conflict, Experience Prototypingis an important tool translating experience stories to an actual interactive product. With this thesis I investigate the Experience Design process focusing on Experience Prototyping.Within the automotive context, I report on three case studies implementing threekinds of interactive systems, forming and following our approach. I implemented (1) anelectric vehicle information system called Heartbeat, communicating the state of the electricdrive and the batteries to the driver in an unobtrusive and ensuring way. I integrated Heartbeatinto the dashboard of a car mock-up with respect to safety and space requirements butat the same time holding on to the story in order to achieve a consistent experience. With (2)the Periscope I implemented a mobile navigation device enhancing the social and relatednessexperiences of the passengers in the car. I built and evaluated several experience prototypesin different stages of the design process and showed that they transported the designed experiencethroughout the implementation of the system. Focusing on (3) the experience offreehand gestures, GestShare explored this interaction style for in-car and car-to-car socialexperiences. We designed and implemented a gestural prototypes for small but effectivesocial interactions between drivers and evaluated the system in the lab and and in-situ study. The contributions of this thesis are (1) a definition of Experience Prototyping in the automotivedomain resulting from a literature review and my own work, showing the importanceand feasibility of Experience Prototyping for Experience Design. I (2) contribute three casestudies and describe the details of several prototypes as milestones on the way from a anexperience story to an interactive system. I (3) derive best practices for Experience Prototypingconcerning their characteristics such as fidelity, resolution and interactivity as well asthe evaluation in the lab an in situ in different stages of the process. / Wir definieren unser Leben zunehmend durch Dinge, die wir erleben und weniger durchProdukte, die wir kaufen. Ein Konzert unseres Lieblingsmusikers zu besuchen kann dabeiwichtiger sein, als eine teure Stereoanlage zu besitzen. Auch interaktive Systeme bewertenwir nicht mehr nur nach der Qualität des Displays oder der Benutzerfreundlichkeit, sondernauch nach Erlebnissen, die durch die Benutzung möglich werden. Das Smartphone wurdehauptsächlich zum Telefonieren und Schreiben von Nachrichten entwickelt. Auf einer emotionalenEbene bietet es uns aber auch eine Möglichkeit, wichtigen Personen sehr nah zusein, auch wenn sie manchmal weit weg sind. Bei der Entwicklung interaktiver Systememüssen wir uns daher nicht nur fragen wie, sondern auch warum diese benutzt werden. Erlebnisse,Gefühle und Emotionen, die während der Interaktion entstehen, spielen dabei einewichtige Rolle. Experience Design ist eine Disziplin, die sich auf Geschichten konzentriert,die ein Produkt erzählt, bevor es tatsächlich implementiert wird. In einem interdisziplinären Team aus Psychologen, Industrie-Designern, Produktentwicklernund Spezialisten der Mensch-Maschine-Interaktion wurde ein Prozess zur Erlebnis-Gestaltung im automobilen Kontext angewandt. Die Beibehaltung von Erlebnissen über dengesamten Entwicklungsprozess hinweg ist eine große Herausforderung für Automobilhersteller.Ingenieure hängen bei der Implementierung interaktiver Systeme von technischen,sicherheitsrelevanten und ergonomischen Anforderungen ab, die oftmals dem gestaltetenErlebnis widersprechen. Die Bereitstellung von Erlebnis-Prototypen ermöglicht die Übersetzungvon Geschichten in interaktive Produkte und wirkt daher diesem Konflikt entgegen. Im Rahmen dieser Dissertation untersuche ich den Prozess zur Erlebnis-Gestaltung hinsichtlichder Bedeutung von Erlebnis-Prototypen. Ich berichte von drei Fallbeispielen im automobilenBereich, die die Gestaltung und Implementierung verschiedener interaktiver Systemenumfassen. (1) Ein Informationssystem für Elektrofahrzeuge, der Heartbeat, macht den Zustanddes elektrischen Antriebs und den Ladestand der Batterien für den Fahrer visuell undhaptisch erlebbar. Nach der Implementierung mehrerer Prototypen wurde Heartbeat unterBerücksichtigung verschiedener technischer und sicherheitsrelevanter Anforderungen in dieArmaturen eines Fahrzeugmodells integriert, ohne dass dabei das gestaltete Erlebnis verlorengegangen ist. (2) Das Periscope ist ein mobiles Navigationsgerät, das den Insassensoziale Erlebnisse ermöglicht und das Verbundenheitsgefühl stärkt. Durch die Implementierungmehrere Erlebnis-Prototypen und deren Evaluation in verschiedenen Phasen des Entwicklungsprozesseskonnten die gestalteten Erlebnisse konsistent erhalten werden. (3) ImProjekt GestShare wurde das Potential der Interaktion durch Freiraumgesten im Fahrzeuguntersucht. Dabei standen ein Verbundenheitserlebnis des Fahrers und soziale Interaktionenmit Fahrern anderer Fahrzeuge im Fokus. Es wurden mehrere Prototypen implementiert undauch in einer Verkehrssituation evaluiert. Die wichtigsten Beiträge dieser Dissertation sind (1) eine intensive Betrachtung und Anwendungvon Erlebnis-Prototypen im Auto und deren Relevanz bei der Erlebnis-Gestaltung,beruhend auf einer Literaturauswertung und der eigenen Erfahrung innerhalb des Projekts; (2) drei Fallstudien und eine detaillierte Beschreibung mehrere Prototypen in verschiedenenPhasen des Prozesses und (3) Empfehlungen zu Vorgehensweisen bei der Erstellung vonErlebnis-Prototypen hinsichtlich der Eigenschaften wie Nähe zum finalen Produkt, Anzahlder implementierten Details und Interaktivität sowie zur Evaluation im Labor und in tatsächlichenVerkehrssituationen in verschiedenen Phasen des Entwicklungsprozesses.

IT infrastructures can be quantitatively described by attributes, like performance or energy efficiency. Ever-changing user demands and economic attempts require varying short-term and long-term decisions regarding the alignment of an IT infrastructure and particularly its attributes to this dynamic surrounding. Potentially conflicting attribute goals and the central role of IT infrastructures presuppose decision making based upon reasoning, the process of forming inferences from facts or premises. The focus on specific IT infrastructure parts or a fixed (small) attribute set disqualify existing reasoning approaches for this intent, as they neither cover the (complex) interplay of all IT infrastructure components simultaneously, nor do they address inter- and intra-attribute correlations sufficiently. This thesis presents a process model for the integrated reasoning about quantitative IT infrastructure attributes. The process model’s main idea is to formalize the compilation of an individual reasoning function, a mathematical mapping of parametric influencing factors and modifications on an attribute vector. Compilation bases upon model integration to benefit from the multitude of existing specialized, elaborated, and well-established attribute models. The achieved reasoning function consumes an individual tuple of IT infrastructure components, attributes, and external influencing factors to expose a broad applicability. The process model formalizes a reasoning intent in three phases. First, reasoning goals and parameters are collected in a reasoning suite, and formalized in a reasoning function skeleton. Second, the skeleton is iteratively refined, guided by the reasoning suite. Third, the achieved reasoning function is employed for What-if analyses, optimization, or descriptive statistics to conduct the concrete reasoning. The process model provides five template classes that collectively formalize all phases in order to foster reproducibility and to reduce error-proneness. Process model validation is threefold. A controlled experiment reasons about a Raspberry Pi cluster’s performance and energy efficiency to illustrate feasibility. Besides, a requirements analysis on a world-class supercomputer and on the European-wide execution of hydro meteorology simulations as well as a related work examination disclose the process model’s level of innovation. Potential future work employs prepared automation capabilities, integrates human factors, and uses reasoning results for the automatic generation of modification recommendations. / IT-Infrastrukturen können mit Attributen, wie Leistung und Energieeffizienz, quantitativ beschrieben werden. Nutzungsbedarfsänderungen und ökonomische Bestrebungen erfordern Kurz- und Langfristentscheidungen zur Anpassung einer IT-Infrastruktur und insbesondere ihre Attribute an dieses dynamische Umfeld. Potentielle Attribut-Zielkonflikte sowie die zentrale Rolle von IT-Infrastrukturen erfordern eine Entscheidungsfindung mittels Reasoning, einem Prozess, der Rückschlüsse (rein) aus Fakten und Prämissen zieht. Die Fokussierung auf spezifische Teile einer IT-Infrastruktur sowie die Beschränkung auf (sehr) wenige Attribute disqualifizieren bestehende Reasoning-Ansätze für dieses Vorhaben, da sie weder das komplexe Zusammenspiel von IT-Infrastruktur-Komponenten, noch Abhängigkeiten zwischen und innerhalb einzelner Attribute ausreichend berücksichtigen können. Diese Arbeit präsentiert ein Prozessmodell für das integrierte Reasoning über quantitative IT-Infrastruktur-Attribute. Die grundlegende Idee des Prozessmodells ist die Herleitung einer individuellen Reasoning-Funktion, einer mathematischen Abbildung von Einfluss- und Modifikationsparametern auf einen Attributvektor. Die Herleitung basiert auf der Integration bestehender (Attribut-)Modelle, um von deren Spezialisierung, Reife und Verbreitung profitieren zu können. Die erzielte Reasoning-Funktion verarbeitet ein individuelles Tupel aus IT-Infrastruktur-Komponenten, Attributen und externen Einflussfaktoren, um eine breite Anwendbarkeit zu gewährleisten. Das Prozessmodell formalisiert ein Reasoning-Vorhaben in drei Phasen. Zunächst werden die Reasoning-Ziele und -Parameter in einer Reasoning-Suite gesammelt und in einem Reasoning-Funktions-Gerüst formalisiert. Anschließend wird das Gerüst entsprechend den Vorgaben der Reasoning-Suite iterativ verfeinert. Abschließend wird die hergeleitete Reasoning-Funktion verwendet, um mittels “What-if”–Analysen, Optimierungsverfahren oder deskriptiver Statistik das Reasoning durchzuführen. Das Prozessmodell enthält fünf Template-Klassen, die den Prozess formalisieren, um Reproduzierbarkeit zu gewährleisten und Fehleranfälligkeit zu reduzieren. Das Prozessmodell wird auf drei Arten validiert. Ein kontrolliertes Experiment zeigt die Durchführbarkeit des Prozessmodells anhand des Reasonings zur Leistung und Energieeffizienz eines Raspberry Pi Clusters. Eine Anforderungsanalyse an einem Superrechner und an der europaweiten Ausführung von Hydro-Meteorologie-Modellen erläutert gemeinsam mit der Betrachtung verwandter Arbeiten den Innovationsgrad des Prozessmodells. Potentielle Erweiterungen nutzen die vorbereiteten Automatisierungsansätze, integrieren menschliche Faktoren, und generieren Modifikationsempfehlungen basierend auf Reasoning-Ergebnissen.

Music has been the subject of formal approaches for a long time, ranging from Pythagoras’ elementary research on tonal systems to J. S. Bach’s elaborate formal composition techniques. Especially in the 20th century, much music was composed based on formal techniques: Algorithmic approaches for composing music were developed by composers like A. Schoenberg as well as in the scientific area. So far, a variety of mathematical techniques have been employed for composing music, e.g. probability models, artificial neural networks or constraint-based reasoning. In the recent time, interactive music systems have become popular: existing songs can be replayed with musical video games and original music can be interactively composed with easy-to-use applications running e.g. on mobile devices. However, applications which algorithmically generate music in real-time based on user interaction are mostly experimental and limited in either interactivity or musicality. There are many enjoyable applications but there are also many opportunities for improvements and novel approaches. The goal of this work is to provide a general and systematic approach for specifying and implementing interactive music systems. We introduce an algebraic framework for interactively composing music in real-time with a reasoning-technique called ‘soft constraints’: this technique allows modeling and solving a large range of problems and is suited particularly well for problems with soft and concurrent optimization goals. Our framework is based on well-known theories for music and soft constraints and allows specifying interactive music systems by declaratively defining ‘how the music should sound’ with respect to both user interaction and musical rules. Based on this core framework, we introduce an approach for interactively generating music similar to existing melodic material. With this approach, musical rules can be defined by playing notes (instead of writing code) in order to make interactively generated melodies comply with a certain musical style. We introduce an implementation of the algebraic framework in .NET and present several concrete applications: ‘The Planets’ is an application controlled by a table-based tangible interface where music can be interactively composed by arranging planet constellations. ‘Fluxus’ is an application geared towards musicians which allows training melodic material that can be used to define musical styles for applications geared towards non-musicians. Based on musical styles trained by the Fluxus sequencer, we introduce a general approach for transforming spatial movements to music and present two concrete applications: the first one is controlled by a touch display, the second one by a motion tracking system. At last, we investigate how interactive music systems can be used in the area of pervasive advertising in general and how our approach can be used to realize ‘interactive advertising jingles’. / Musik ist seit langem Gegenstand formaler Untersuchungen, von Phytagoras‘ grundlegender Forschung zu tonalen Systemen bis hin zu J. S. Bachs aufwändigen formalen Kompositionstechniken. Vor allem im 20. Jahrhundert wurde vielfach Musik nach formalen Methoden komponiert: Algorithmische Ansätze zur Komposition von Musik wurden sowohl von Komponisten wie A. Schoenberg als auch im wissenschaftlichem Bereich entwickelt. Bislang wurde eine Vielzahl von mathematischen Methoden zur Komposition von Musik verwendet, z.B. statistische Modelle, künstliche neuronale Netze oder Constraint-Probleme. In der letzten Zeit sind interaktive Musiksysteme populär geworden: Bekannte Songs können mit Musikspielen nachgespielt werden, und mit einfach zu bedienenden Anwendungen kann man neue Musik interaktiv komponieren (z.B. auf mobilen Geräten). Allerdings sind die meisten Anwendungen, die basierend auf Benutzerinteraktion in Echtzeit algorithmisch Musik generieren, eher experimentell und in Interaktivität oder Musikalität limitiert. Es gibt viele unterhaltsame Anwendungen, aber ebenso viele Möglichkeiten für Verbesserungen und neue Ansätze. Das Ziel dieser Arbeit ist es, einen allgemeinen und systematischen Ansatz zur Spezifikation und Implementierung von interaktiven Musiksystemen zu entwickeln. Wir stellen ein algebraisches Framework zur interaktiven Komposition von Musik in Echtzeit vor welches auf sog. ‚Soft Constraints‘ basiert, einer Methode aus dem Bereich der künstlichen Intelligenz. Mit dieser Methode ist es möglich, eine große Anzahl von Problemen zu modellieren und zu lösen. Sie ist besonders gut geeignet für Probleme mit unklaren und widersprüchlichen Optimierungszielen. Unser Framework basiert auf gut erforschten Theorien zu Musik und Soft Constraints und ermöglicht es, interaktive Musiksysteme zu spezifizieren, indem man deklarativ angibt, ‚wie sich die Musik anhören soll‘ in Bezug auf sowohl Benutzerinteraktion als auch musikalische Regeln. Basierend auf diesem Framework stellen wir einen neuen Ansatz vor, um interaktiv Musik zu generieren, die ähnlich zu existierendem melodischen Material ist. Dieser Ansatz ermöglicht es, durch das Spielen von Noten (nicht durch das Schreiben von Programmcode) musikalische Regeln zu definieren, nach denen interaktiv generierte Melodien an einen bestimmten Musikstil angepasst werden. Wir präsentieren eine Implementierung des algebraischen Frameworks in .NET sowie mehrere konkrete Anwendungen: ‚The Planets‘ ist eine Anwendung für einen interaktiven Tisch mit der man Musik komponieren kann, indem man Planetenkonstellationen arrangiert. ‚Fluxus‘ ist eine Anwendung, die sich an Musiker richtet. Sie erlaubt es, melodisches Material zu trainieren, das wiederum als Musikstil in Anwendungen benutzt werden kann, die sich an Nicht-Musiker richten. Basierend auf diesen trainierten Musikstilen stellen wir einen generellen Ansatz vor, um räumliche Bewegungen in Musik umzusetzen und zwei konkrete Anwendungen basierend auf einem Touch-Display bzw. einem Motion-Tracking-System. Abschließend untersuchen wir, wie interaktive Musiksysteme im Bereich ‚Pervasive Advertising‘ eingesetzt werden können und wie unser Ansatz genutzt werden kann, um ‚interaktive Werbejingles‘ zu realisieren.

We present methods for improved handling of morphologically rich languages (MRLS) where we define MRLS as languages that are morphologically more complex than English. Standard algorithms for language modeling, tagging and parsing have problems with the productive nature of such languages. Consider for example the possible forms of a typical English verb like work that generally has four four different forms: work, works, working and worked. Its Spanish counterpart trabajar has 6 different forms in present tense: trabajo, trabajas, trabaja, trabajamos, trabajáis and trabajan and more than 50 different forms when including the different tenses, moods (indicative, subjunctive and imperative) and participles. Such a high number of forms leads to sparsity issues: In a recent Wikipedia dump of more than 400 million tokens we find that 20 of these forms occur only twice or less and that 10 forms do not occur at all. This means that even if we only need unlabeled data to estimate a model and even when looking at a relatively common and frequent verb, we do not have enough data to make reasonable estimates for some of its forms. However, if we decompose an unseen form such as trabajaréis `you will work', we find that it is trabajar in future tense and second person plural. This allows us to make the predictions that are needed to decide on the grammaticality (language modeling) or syntax (tagging and parsing) of a sentence. In the first part of this thesis, we develop a morphological language model. A language model estimates the grammaticality and coherence of a sentence. Most language models used today are word-based n-gram models, which means that they estimate the transitional probability of a word following a history, the sequence of the (n - 1) preceding words. The probabilities are estimated from the frequencies of the history and the history followed by the target word in a huge text corpus. If either of the sequences is unseen, the length of the history has to be reduced. This leads to a less accurate estimate as less context is taken into account. Our morphological language model estimates an additional probability from the morphological classes of the words. These classes are built automatically by extracting morphological features from the word forms. To this end, we use unsupervised segmentation algorithms to find the suffixes of word forms. Such an algorithm might for example segment trabajaréis into trabaja and réis and we can then estimate the properties of trabajaréis from other word forms with the same or similar morphological properties. The data-driven nature of the segmentation algorithms allows them to not only find inflectional suffixes (such as -réis), but also more derivational phenomena such as the head nouns of compounds or even endings such as -tec, which identify technology oriented companies such as Vortec, Memotec and Portec and would not be regarded as a morphological suffix by traditional linguistics. Additionally, we extract shape features such as if a form contains digits or capital characters. This is important because many rare or unseen forms are proper names or numbers and often do not have meaningful suffixes. Our class-based morphological model is then interpolated with a word-based model to combine the generalization capabilities of the first and the high accuracy in case of sufficient data of the second. We evaluate our model across 21 European languages and find improvements between 3% and 11% in perplexity, a standard language modeling evaluation measure. Improvements are highest for languages with more productive and complex morphology such as Finnish and Estonian, but also visible for languages with a relatively simple morphology such as English and Dutch. We conclude that a morphological component yields consistent improvements for all the tested languages and argue that it should be part of every language model. Dependency trees represent the syntactic structure of a sentence by attaching each word to its syntactic head, the word it is directly modifying. Dependency parsing is usually tackled using heavily lexicalized (word-based) models and a thorough morphological preprocessing is important for optimal performance, especially for MRLS. We investigate if the lack of morphological features can be compensated by features induced using hidden Markov models with latent annotations (HMM-LAs) and find this to be the case for German. HMM-LAs were proposed as a method to increase part-of-speech tagging accuracy. The model splits the observed part-of-speech tags (such as verb and noun) into subtags. An expectation maximization algorithm is then used to fit the subtags to different roles. A verb tag for example might be split into an auxiliary verb and a full verb subtag. Such a split is usually beneficial because these two verb classes have different contexts. That is, a full verb might follow an auxiliary verb, but usually not another full verb. For German and English, we find that our model leads to consistent improvements over a parser not using subtag features. Looking at the labeled attachment score (LAS), the number of words correctly attached to their head, we observe an improvement from 90.34 to 90.75 for English and from 87.92 to 88.24 for German. For German, we additionally find that our model achieves almost the same performance (88.24) as a model using tags annotated by a supervised morphological tagger (LAS of 88.35). We also find that the German latent tags correlate with morphology. Articles for example are split by their grammatical case. We also investigate the part-of-speech tagging accuracies of models using the traditional treebank tagset and models using induced tagsets of the same size and find that the latter outperform the former, but are in turn outperformed by a discriminative tagger. Furthermore, we present a method for fast and accurate morphological tagging. While part-of-speech tagging annotates tokens in context with their respective word categories, morphological tagging produces a complete annotation containing all the relevant inflectional features such as case, gender and tense. A complete reading is represented as a single tag. As a reading might consist of several morphological features the resulting tagset usually contains hundreds or even thousands of tags. This is an issue for many decoding algorithms such as Viterbi which have runtimes depending quadratically on the number of tags. In the case of morphological tagging, the problem can be avoided by using a morphological analyzer. A morphological analyzer is a manually created finite-state transducer that produces the possible morphological readings of a word form. This analyzer can be used to prune the tagging lattice and to allow for the application of standard sequence labeling algorithms. The downside of this approach is that such an analyzer is not available for every language or might not have the coverage required for the task. Additionally, the output tags of some analyzers are not compatible with the annotations of the treebanks, which might require some manual mapping of the different annotations or even to reduce the complexity of the annotation. To avoid this problem we propose to use the posterior probabilities of a conditional random field (CRF) lattice to prune the space of possible taggings. At the zero-order level the posterior probabilities of a token can be calculated independently from the other tokens of a sentence. The necessary computations can thus be performed in linear time. The features available to the model at this time are similar to the features used by a morphological analyzer (essentially the word form and features based on it), but also include the immediate lexical context. As the ambiguity of word types varies substantially, we just fix the average number of readings after pruning by dynamically estimating a probability threshold. Once we obtain the pruned lattice, we can add tag transitions and convert it into a first-order lattice. The quadratic forward-backward computations are now executed on the remaining plausible readings and thus efficient. We can now continue pruning and extending the lattice order at a relatively low additional runtime cost (depending on the pruning thresholds). The training of the model can be implemented efficiently by applying stochastic gradient descent (SGD). The CRF gradient can be calculated from a lattice of any order as long as the correct reading is still in the lattice. During training, we thus run the lattice pruning until we either reach the maximal order or until the correct reading is pruned. If the reading is pruned we perform the gradient update with the highest order lattice still containing the reading. This approach is similar to early updating in the structured perceptron literature and forces the model to learn how to keep the correct readings in the lower order lattices. In practice, we observe a high number of lower updates during the first training epoch and almost exclusively higher order updates during later epochs. We evaluate our CRF tagger on six languages with different morphological properties. We find that for languages with a high word form ambiguity such as German, the pruning results in a moderate drop in tagging accuracy while for languages with less ambiguity such as Spanish and Hungarian the loss due to pruning is negligible. However, our pruning strategy allows us to train higher order models (order > 1), which give substantial improvements for all languages and also outperform unpruned first-order models. That is, the model might lose some of the correct readings during pruning, but is also able to solve more of the harder cases that require more context. We also find our model to substantially and significantly outperform a number of frequently used taggers such as Morfette and SVMTool. Based on our morphological tagger we develop a simple method to increase the performance of a state-of-the-art constituency parser. A constituency tree describes the syntactic properties of a sentence by assigning spans of text to a hierarchical bracket structure. developed a language-independent approach for the automatic annotation of accurate and compact grammars. Their implementation -- known as the Berkeley parser -- gives state-of-the-art results for many languages such as English and German. For some MRLS such as Basque and Korean, however, the parser gives unsatisfactory results because of its simple unknown word model. This model maps unknown words to a small number of signatures (similar to our morphological classes). These signatures do not seem expressive enough for many of the subtle distinctions made during parsing. We propose to replace rare words by the morphological reading generated by our tagger instead. The motivation is twofold. First, our tagger has access to a number of lexical and sublexical features not available during parsing. Second, we expect the morphological readings to contain most of the information required to make the correct parsing decision even though we know that things such as the correct attachment of prepositional phrases might require some notion of lexical semantics. In experiments on the SPMRL 2013 dataset of nine MRLS we find our method to give improvements for all languages except French for which we observe a minor drop in the Parseval score of 0.06. For Hebrew, Hungarian and Basque we find substantial absolute improvements of 5.65, 11.87 and 15.16, respectively. We also performed an extensive evaluation on the utility of word representations for morphological tagging. Our goal was to reduce the drop in performance that is caused when a model trained on a specific domain is applied to some other domain. This problem is usually addressed by domain adaption (DA). DA adapts a model towards a specific domain using a small amount of labeled or a huge amount of unlabeled data from that domain. However, this procedure requires us to train a model for every target domain. Instead we are trying to build a robust system that is trained on domain-specific labeled and domain-independent or general unlabeled data. We believe word representations to be key in the development of such models because they allow us to leverage unlabeled data efficiently. We compare data-driven representations to manually created morphological analyzers. We understand data-driven representations as models that cluster word forms or map them to a vectorial representation. Examples heavily used in the literature include Brown clusters, Singular Value Decompositions of count vectors and neural-network-based embeddings. We create a test suite of six languages consisting of in-domain and out-of-domain test sets. To this end we converted annotations for Spanish and Czech and annotated the German part of the Smultron treebank with a morphological layer. In our experiments on these data sets we find Brown clusters to outperform the other data-driven representations. Regarding the comparison with morphological analyzers, we find Brown clusters to give slightly better performance in part-of-speech tagging, but to be substantially outperformed in morphological tagging.

Prediction problems on high-dimensional molecular data, e.g. the classification of microar- ray samples into normal and cancer tissues, are complex and ill-posed since the number of variables usually exceeds the number of observations by orders of magnitude. Recent research in the area has propagated a variety of new statistical models in order to handle these new biological datasets. In practice, however, these models are always applied in combination with preprocessing and variable selection methods as well as model selection which is mostly performed by cross-validation. Varma and Simon (2006) have used the term ‘wrapper-algorithm’ for this integration of preprocessing and model selection into the construction of statistical models. Additionally, they have proposed the method of nested cross-validation (NCV) as a way of estimating their prediction error which has evolved to the gold-standard by now. In the first part, this thesis provides further theoretical and empirical justification for the usage of NCV in the context of wrapper-algorithms. Moreover, a computationally less intensive alternative to NCV is proposed which can be motivated in a decision theoretic framework. The new method can be interpreted as a smoothed variant of NCV and, in contrast to NCV, guarantees intuitive bounds for the estimation of the prediction error. The second part focuses on the ranking of wrapper algorithms. Cross-study-validation is proposed as an alternative concept to the repetition of separated within-study-validations if several similar prediction problems are available. The concept is demonstrated using six different wrapper algorithms for survival prediction on censored data on a selection of eight breast cancer datasets. Additionally, a parametric bootstrap approach for simulating realistic data from such related prediction problems is described and subsequently applied to illustrate the concept of cross-study-validation for the ranking of wrapper algorithms. Eventually, the last part approaches computational aspects of the analyses and simula- tions performed in the thesis. The preprocessing before the analysis as well as the evaluation of the prediction models requires the usage of large computing resources. Parallel comput- ing approaches are illustrated on cluster, cloud and high performance computing resources using the R programming language. Usage of heterogeneous hardware and processing of large datasets are covered as well as the implementation of the R-package survHD for the analysis and evaluation of high-dimensional wrapper algorithms for survival prediction from censored data. / Prädiktionsprobleme für hochdimensionale genetische Daten, z.B. die Klassifikation von Proben in normales und Krebsgewebe, sind komplex und unterbestimmt, da die Anzahl der Variablen die Anzahl der Beobachtungen um ein Vielfaches übersteigt. Die Forschung hat auf diesem Gebiet in den letzten Jahren eine Vielzahl an neuen statistischen Meth- oden hervorgebracht. In der Praxis werden diese Algorithmen jedoch stets in Kombination mit Vorbearbeitung und Variablenselektion sowie Modellwahlverfahren angewandt, wobei letztere vorwiegend mit Hilfe von Kreuzvalidierung durchgeführt werden. Varma und Simon (2006) haben den Begriff ’Wrapper-Algorithmus’ für eine derartige Einbet- tung von Vorbearbeitung und Modellwahl in die Konstruktion einer statistischen Methode verwendet. Zudem haben sie die genestete Kreuzvalidierung (NCV) als eine Methode zur Sch ̈atzung ihrer Fehlerrate eingeführt, welche sich mittlerweile zum Goldstandard entwickelt hat. Im ersten Teil dieser Doktorarbeit, wird eine tiefergreifende theoretische Grundlage sowie eine empirische Rechtfertigung für die Anwendung von NCV bei solchen ’Wrapper-Algorithmen’ vorgestellt. Außerdem wird eine alternative, weniger computerintensive Methode vorgeschlagen, welche im Rahmen der Entscheidungstheorie motiviert wird. Diese neue Methode kann als eine gegl ̈attete Variante von NCV interpretiert wer- den und hält im Gegensatz zu NCV intuitive Grenzen bei der Fehlerratenschätzung ein. Der zweite Teil behandelt den Vergleich verschiedener ’Wrapper-Algorithmen’ bzw. das Sch ̈atzen ihrer Reihenfolge gem ̈aß eines bestimmten Gütekriteriums. Als eine Alterna- tive zur wiederholten Durchführung von Kreuzvalidierung auf einzelnen Datensätzen wird das Konzept der studienübergreifenden Validierung vorgeschlagen. Das Konzept wird anhand von sechs verschiedenen ’Wrapper-Algorithmen’ für die Vorhersage von Uberlebenszeiten bei acht Brustkrebsstudien dargestellt. Zusätzlich wird ein Bootstrapverfahren beschrieben, mit dessen Hilfe man mehrere realistische Datens ̈atze aus einer Menge von solchen verwandten Prädiktionsproblemen generieren kann. Der letzte Teil beleuchtet schließlich computationale Verfahren, die bei der Umsetzung der Analysen in dieser Dissertation eine tragende Rolle gespielt haben. Die Vorbearbeitungsschritte sowie die Evaluation der Prädiktionsmodelle erfordert die extensive Nutzung von Computerressourcen. Es werden Ansätze zum parallelen Rechnen auf Cluster-, Cloud- und Hochleistungsrechen- ressourcen unter der Verwendung der Programmiersprache R beschrieben. Die Benutzung von heterogenen Hardwarearchitekturen, die Verarbeitung von großen Datensätzen sowie die Entwicklung des R-Pakets survHD für die Analyse und Evaluierung von ’Wrapper- Algorithmen’ zur Uberlebenszeitenanalyse werden thematisiert.

The topic of this thesis is a mathematical treatment of Anderson's orthogonality catastrophe. Named after P.W. Anderson, who studied the phenomenon in the late 1960s, the catastrophe is an intrinsic effect in Fermi gases. In his first work on the topic in [Phys. Rev. Lett. 18:1049--1051], Anderson studied a system of $N$ noninteracting fermions in three space dimensions and found the ground state to be asymptotically orthogonal to the ground state of the same system perturbed by a finite-range scattering potential. More precisely, let $\Phi_L^N$ be the $N$-body ground state of the fermionic system in a $d$-dimensional box of length $L$,and let $\Psi_L^N$ be the ground state of the corresponding system in the presence of the additional finite-range potential. Then the catastrophe brings about the asymptotic vanishing $$\S_L^N := \<\Phi_L^N, \Psi_L^N\> \sim L^{-\gamma/2}$$ of the overlap $\S_L^N$ of the $N$-body ground states $\Phi_L^N$ and $\Psi_L^N$. The asymptotics is in the thermodynamic limit $L\to\infty$ and $N\to\infty$ with fixed density $N/L^d\to\varrho > 0$. In [Commun. Math. Phys. 329:979--998], the overlap $\S_L^N$ has been bounded from above with an asymptotic bound of the form $$\abs{\S_L^N}^2 \lesssim L^{-\tilde{\gamma}}$$. The decay exponent $\tilde{\gamma}$ there corresponds to the one of Anderson in [Phys. Rev. Lett. 18:1049--1051]. Another publication by Anderson from the same year, [Phys. Rev. 164:352--359], contains the exact asymptotics with a bigger coefficient $\gamma$. This thesis features a step towards the exact asymptotics. We prove a bound with a coefficient $\gamma$ that corresponds in a certain sense to the one in [Phys. Rev. 164:352--359], and improves upon the one in [Commun. Math. Phys. 329:979--998]. We use the methods from [Commun. Math. Phys. 329:979--998], but treat every term in a series expansion of $\ln S_L^N$, instead of only the first one. Treating the higher order terms introduces additional arguments since the trace expressions occurring are no longer necessarily nonnegative, which complicates some of the estimates. The main contents of this thesis will also be published in a forthcoming article co-authored with Martin Gebert, Peter Müller, and Peter Otte.

No description available.

No description available.

Due to the increasing power of data acquisition and data storage technologies, a large amount of data sets with complex structure are collected in the era of data explosion. Instead of simple representations by low-dimensional numerical features, such data sources range from high-dimensional feature spaces to graph data describing relationships among objects. Many techniques exist in the literature for mining simple numerical data but only a few approaches touch the increasing challenge of mining complex data, such as high-dimensional vectors of non-numerical data type, time series data, graphs, and multi-instance data where each object is represented by a finite set of feature vectors. Besides, there are many important data mining tasks for high-dimensional data, such as clustering, outlier detection, dimensionality reduction, similarity search, classification, prediction and result interpretation. Many algorithms have been proposed to solve these tasks separately, although in some cases they are closely related. Detecting and exploiting the relationships among them is another important challenge. This thesis aims to solve these challenges in order to gain new knowledge from complex high-dimensional data. We propose several new algorithms combining different data mining tasks to acquire novel knowledge from complex high-dimensional data: ROCAT (Relevant Overlapping Subspace Clusters on Categorical Data) automatically detects the most relevant overlapping subspace clusters on categorical data. It integrates clustering, feature selection and pattern mining without any input parameters in an information theoretic way. The next algorithm MSS (Multiple Subspace Selection) finds multiple low-dimensional subspaces for moderately high-dimensional data, each exhibiting an interesting cluster structure. For better interpretation of the results, MSS visualizes the clusters in multiple low-dimensional subspaces in a hierarchical way. SCMiner (Summarization-Compression Miner) focuses on bipartite graph data, which integrates co-clustering, graph summarization, link prediction, and the discovery of the hidden structure of a bipartite graph data on the basis of data compression. Finally, we propose a novel similarity measure for multi-instance data. The Probabilistic Integral Metric (PIM) is based on a probabilistic generative model requiring few assumptions. Experiments demonstrate the effectiveness and efficiency of PIM for similarity search (multi-instance data indexing with M-tree), explorative data analysis and data mining (multi-instance classification). To sum up, we propose algorithms combining different data mining tasks for complex data with various data types and data structures to discover the novel knowledge hidden behind the complex data.

In recent years, Hilbert's Programme has been resumed within the framework of constructive mathematics. This undertaking has already shown its feasability for a considerable part of commutative algebra. In particular, point-free methods have been playing a primary role, emerging as the appropriate language for expressing the interplay between real and ideal in mathematics. This dissertation is written within this tradition and has Sambin's notion of formal topology at its core. We start by developing general tools, in order to make this notion more immediate for algebraic application. We revise the Zariski spectrum as an inductively generated basic topology, and we analyse the constructive status of the corresponding principles of spatiality and reducibility. Through a series of examples, we show how the principle of spatiality is recurrent in the mathematical practice. The tools developed before are applied to specific problems in constructive algebra. In particular, we find an elementary characterization of the notion of codimension for ideals of a commutative ring, by means of which a constructive version of Krull's principal ideal theorem can be stated and proved. We prove a formal version of the projective Eisenbud-Evans-Storch theorem. Finally, guided by the algebraic intuition, we present an application in constructive domain theory, by proving a finite version of Kleene-Kreisel density theorem for non-flat information systems. / In den vergangenen Jahren wurde das Hilbertsche Programm im Rahmen der konstruktiven Mathematik wiederaufgenommen. Diese Unternehmung hat sich vor allem in der kommutativen Algebra als praktikabel erwiesen. Insbesondere spielen punktfreie Methoden eine wesentliche Rolle: sie haben sich als die angemessene Sprache herausgestellt, um das Zwischenspiel von "real'" und "ideal" in der Mathematik auszudrücken. Die vorliegende Dissertation steht in dieser Tradition; zentral ist Sambins Begriff der formalen Topologie. Zunächst entwickeln wir ein allgemeines Instrumentarium, das geeignet ist, diesen Begriff seinen algebraischen Anwendungen näherzubringen. Sodann arbeiten wir das Zariski-Spektrum in eine induktiv erzeugte "basic topology" um und analysieren den konstruktiven Status der einschlägigen Varianten von Spatialität und Reduzibilität. Durch Angabe einer Reihe von Instanzen zeigen wir, wie häufig das Prinzip der Spatialität in der mathematischen Praxis vorkommt. Die eigens entwickelten Werkzeuge werden schließlich auf spezifische Probleme aus der konstruktiven Algebra angewandt. Insbesondere geben wir eine elementare Charakterisierung der Kodimension eines Ideals in einem kommutativen Ring an, mit der eine konstruktive Fassung des Krullschen Hauptidealsatzes formuliert und bewiesen werden kann. Ferner beweisen wir eine formale Fassung des Satzes von Eisenbud-Evans-Storch im projektiven Fall. Geleitet von der algebraischen Intuition stellen wir zuletzt eine Anwendung in der konstruktiven Bereichstheorie vor, indem wir eine finite Variante des Dichtheitssatzes von Kleene und Kreisel für nicht-flache Informationssysteme beweisen.