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

Benchmark experiments nowadays are the method of choice to evaluate learning algorithms in most research fields with applications related to statistical learning. Benchmark experiments are an empirical tool to analyze statistical learning algorithms on one or more data sets: to compare a set of algorithms, to find the best hyperparameters for an algorithm, or to make a sensitivity analysis of an algorithm. In the main part, this dissertation focus on the comparison of candidate algorithms and introduces a comprehensive toolbox for analyzing such benchmark experiments. A systematic approach is introduced -- from exploratory analyses with specialized visualizations static and interactive) via formal investigations and their interpretation as preference relations through to a consensus order of the algorithms, based on one or more performance measures and data sets. The performance of learning algorithms is determined by data set characteristics, this is common knowledge. Not exactly known is the concrete relationship between characteristics and algorithms. A formal framework on top of benchmark experiments is presented for investigation on this relationship. Furthermore, benchmark experiments are commonly treated as fixed-sample experiments, but their nature is sequential. First thoughts on a sequential framework are presented and its advantages are discussed. Finally, this main part of the dissertation is concluded with a discussion on future research topics in the field of benchmark experiments. The second part of the dissertation is concerned with archetypal analysis. Archetypal analysis has the aim to represent observations in a data set as convex combinations of a few extremal points. This is used as an analysis approach for benchmark experiments -- the identification and interpretation of the extreme performances of candidate algorithms. In turn, benchmark experiments are used to analyze the general framework for archetypal analyses worked out in this second part of the dissertation. Using its generalizability, the weighted and robust archetypal problems are introduced and solved; and in the outlook a generalization towards prototypes is discussed. The two freely available R packages -- benchmark and archetypes -- make the introduced methods generally applicable.

Enabling non-experts to publish data on the web is an important achievement of the social web and one of the primary goals of the social semantic web. Making the data easily accessible in turn has received only little attention, which is problematic from the point of view of incentives: users are likely to be less motivated to participate in the creation of content if the use of this content is mostly reserved to experts. Querying in semantic wikis, for example, is typically realized in terms of full text search over the textual content and a web query language such as SPARQL for the annotations. This approach has two shortcomings that limit the extent to which data can be leveraged by users: combined queries over content and annotations are not possible, and users either are restricted to expressing their query intent using simple but vague keyword queries or have to learn a complex web query language. The work presented in this dissertation investigates a more suitable form of querying for semantic wikis that consolidates two seemingly conflicting characteristics of query languages, ease of use and expressiveness. This work was carried out in the context of the semantic wiki KiWi, but the underlying ideas apply more generally to the social semantic and social web. We begin by defining a simple modular conceptual model for the KiWi wiki that enables rich and expressive knowledge representation. A component of this model are structured tags, an annotation formalism that is simple yet flexible and expressive, and aims at bridging the gap between atomic tags and RDF. The viability of the approach is confirmed by a user study, which finds that structured tags are suitable for quickly annotating evolving knowledge and are perceived well by the users. The main contribution of this dissertation is the design and implementation of KWQL, a query language for semantic wikis. KWQL combines keyword search and web querying to enable querying that scales with user experience and information need: basic queries are easy to express; as the search criteria become more complex, more expertise is needed to formulate the corresponding query. A novel aspect of KWQL is that it combines both paradigms in a bottom-up fashion. It treats neither of the two as an extension to the other, but instead integrates both in one framework. The language allows for rich combined queries of full text, metadata, document structure, and informal to formal semantic annotations. KWilt, the KWQL query engine, provides the full expressive power of first-order queries, but at the same time can evaluate basic queries at almost the speed of the underlying search engine. KWQL is accompanied by the visual query language visKWQL, and an editor that displays both the textual and visual form of the current query and reflects changes to either representation in the other. A user study shows that participants quickly learn to construct KWQL and visKWQL queries, even when given only a short introduction. KWQL allows users to sift the wealth of structure and annotations in an information system for relevant data. If relevant data constitutes a substantial fraction of all data, ranking becomes important. To this end, we propose PEST, a novel ranking method that propagates relevance among structurally related or similarly annotated data. Extensive experiments, including a user study on a real life wiki, show that pest improves the quality of the ranking over a range of existing ranking approaches.

In this day and age, the mobile phone is becoming one of the most indispensable personal computing device. People no longer use it just for communication (i.e. calling, sending messages) but also for other aspects of their lives as well. Because of this rise in demand for different and innovative applications, mobile companies (i.e. mobile handset manufacturers and mobile network providers) and organizations have realized the power of collaborative software development and have changed their business strategy. Instead of hiring specific organizations to do programming, they are now opening up their APIs and tools to allow ordinary people create their own mobile applications either for personal use or for profit. However, the problem with this approach is that there are people who might have nice ideas of their own but do not possess the technical expertise in order to create applications implementing these ideas. The goal of this research is to find ways to simplify the creation of mobile applications for non-technical people by applying model-driven software development particularly domain-specific modeling combined with techniques from the field of human-computer interaction (HCI) particularly iterative, user-centered system design. As proof of concept, we concentrate on the development of applications in the domain of mHealth and use the Android Framework as the target platform for code generation. The iterative user-centered design and development of the front-end tool which is called the Mobia Modeler, led us to eventually create a tool that features a configurable-component based design and integrated modeless environment to simplify the different development tasks of end-users. The Mobia models feature both constructs specialized for specific domains (e.g. sensor component, special component ), and also those that are applicable to any type of domain (e.g. structure component, basic component ). In order to accommodate different needs of end-users, a clear separation between the front-end tools (i.e. Mobia Modeler ) and the underlying code generator (i.e. Mobia Processor ) is recommended as long as there is a consistent model in between, that serves as a bridge between the different tools.

Knowledge Discovery in Databases (KDD) is the non-trivial process of identifying valid, novel, useful and ultimately understandable patterns in data. The core step of the KDD process is the application of Data Mining (DM) algorithms to efficiently find interesting patterns in large databases. This thesis concerns itself with three inter-related themes: Generalised interaction and rule mining; the incorporation of statistics into novel data mining approaches; and probabilistic frequent pattern mining in uncertain databases. An interaction describes an effect that variables have -- or appear to have -- on each other. Interaction mining is the process of mining structures on variables describing their interaction patterns -- usually represented as sets, graphs or rules. Interactions may be complex, represent both positive and negative relationships, and the presence of interactions can influence another interaction or variable in interesting ways. Finding interactions is useful in domains ranging from social network analysis, marketing, the sciences, e-commerce, to statistics and finance. Many data mining tasks may be considered as mining interactions, such as clustering; frequent itemset mining; association rule mining; classification rules; graph mining; flock mining; etc. Interaction mining problems can have very different semantics, pattern definitions, interestingness measures and data types. Solving a wide range of interaction mining problems at the abstract level, and doing so efficiently -- ideally more efficiently than with specialised approaches, is a challenging problem. This thesis introduces and solves the Generalised Interaction Mining (GIM) and Generalised Rule Mining (GRM) problems. GIM and GRM use an efficient and intuitive computational model based purely on vector valued functions. The semantics of the interactions, their interestingness measures and the type of data considered are flexible components of vectorised frameworks. By separating the semantics of a problem from the algorithm used to mine it, the frameworks allow both to vary independently of each other. This makes it easier to develop new methods by focusing purely on a problem's semantics and removing the burden of designing an efficient algorithm. By encoding interactions as vectors in the space (or a sub-space) of samples, they provide an intuitive geometric interpretation that inspires novel methods. By operating in time linear in the number of interesting interactions that need to be examined, the GIM and GRM algorithms are optimal. The use of GRM or GIM provides efficient solutions to a range of problems in this thesis, including graph mining, counting based methods, itemset mining, clique mining, a clustering problem, complex pattern mining, negative pattern mining, solving an optimisation problem, spatial data mining, probabilistic itemset mining, probabilistic association rule mining, feature selection and generation, classification and multiplication rule mining. Data mining is a hypothesis generating endeavour, examining large databases for patterns suggesting novel and useful knowledge to the user. Since the database is a sample, the patterns found should describe hypotheses about the underlying process generating the data. In searching for these patterns, a DM algorithm makes additional hypothesis when it prunes the search space. Natural questions to ask then, are: "Does the algorithm find patterns that are statistically significant?" and "Did the algorithm make significant decisions during its search?". Such questions address the quality of patterns found though data mining and the confidence that a user can have in utilising them. Finally, statistics has a range of useful tools and measures that are applicable in data mining. In this context, this thesis incorporates statistical techniques -- in particular, non-parametric significance tests and correlation -- directly into novel data mining approaches. This idea is applied to statistically significant and relatively class correlated rule based classification of imbalanced data sets; significant frequent itemset mining; mining complex correlation structures between variables for feature selection; mining correlated multiplication rules for interaction mining and feature generation; and conjunctive correlation rules for classification. The application of GIM or GRM to these problems lead to efficient and intuitive solutions. Frequent itemset mining (FIM) is a fundamental problem in data mining. While it is usually assumed that the items occurring in a transaction are known for certain, in many applications the data is inherently noisy or probabilistic; such as adding noise in privacy preserving data mining applications, aggregation or grouping of records leading to estimated purchase probabilities, and databases capturing naturally uncertain phenomena. The consideration of existential uncertainty of item(sets) makes traditional techniques inapplicable. Prior to the work in this thesis, itemsets were mined if their expected support is high. This returns only an estimate, ignores the probability distribution of support, provides no confidence in the results, and can lead to scenarios where itemsets are labeled frequent even if they are more likely to be infrequent. Clearly, this is undesirable. This thesis proposes and solves the Probabilistic Frequent Itemset Mining (PFIM) problem, where itemsets are considered interesting if the probability that they are frequent is high. The problem is solved under the possible worlds model and a proposed probabilistic framework for PFIM. Novel and efficient methods are developed for computing an itemset's exact support probability distribution and frequentness probability, using the Poisson binomial recurrence, generating functions, or a Normal approximation. Incremental methods are proposed to answer queries such as finding the top-k probabilistic frequent itemsets. A number of specialised PFIM algorithms are developed, with each being more efficient than the last: ProApriori is the first solution to PFIM and is based on candidate generation and testing. ProFP-Growth is the first probabilistic FP-Growth type algorithm and uses a proposed probabilistic frequent pattern tree (Pro-FPTree) to avoid candidate generation. Finally, the application of GIM leads to GIM-PFIM; the fastest known algorithm for solving the PFIM problem. It achieves orders of magnitude improvements in space and time usage, and leads to an intuitive subspace and probability-vector based interpretation of PFIM.

UML state machines are a widely used language for modeling software behavior. They are considered to be simple and intuitively comprehensible, and are hence one of the most popular languages for modeling reactive components. However, this seeming ease to use vanishes rapidly as soon as the complexity of the system to model increases. In fact, even state machines modeling ``almost trivial'' behavior may get rather hard to understand and error-prone. In particular, synchronization of parallel regions and history-based features are often difficult to model in UML state machines. We therefore propose High-Level Aspect (HiLA), a new, aspect-oriented extension of UML state machines, which can improve the modularity, thus the comprehensibility and reusability of UML state machines considerably. Aspects are used to define additional or alternative system behaviors at certain ``interesting'' points of time in the execution of the state machine, and achieve a high degree of separation of concerns. The distinguishing feature of HiLA w.r.t. other approaches of aspect-oriented state machines is that HiLA aspects are defined on a high, i.e. semantic level as opposed to a low, i.e. syntactic level. This semantic approach makes \HiLA aspects often simpler and better comprehensible than aspects of syntactic approaches. The contributions of this thesis include 1) the abstract and the concrete syntax of HiLA, 2) the weaving algorithms showing how the (additional or alternative) behaviors, separately modeled in aspects, are composed with the base state machine, giving the complete behavior of the system, 3) a formal semantics for HiLA aspects to define how the aspects are activated and (after the execution) left. We also discuss what conflicts between HiLA aspects are possible and how to detect them. The practical applicability of HiLA is shown in a case study of a crisis management system.

Performanzprobleme treten in der Praxis von IT-Anwendungen häufig auf, trotz steigender Hardwareleistung und verschiedenster Ansätze zur Entwicklung performanter Software im Softwarelebenszyklus. Modellbasierte Performanzanalysen ermöglichen auf Basis von Entwurfsartefakten eine Prävention von Performanzproblemen. Bei bestehenden oder teilweise implementierten IT-Anwendungen wird versucht, durch Hardwareskalierung oder Optimierung des Codes Performanzprobleme zu beheben. Beide Ansätze haben Nachteile: modellbasierte Ansätze werden durch die benötigte hohe Expertise nicht generell genutzt, die nachträgliche Optimierung ist ein unsystematischer und unkoordinierter Prozess. Diese Dissertation schlägt einen neuen Ansatz zur Performanzanalyse für eine nachfolgende Optimierung vor. Mittels eines Experiments werden Performanzwechselwirkungen in der IT-Anwendung identifiziert. Basis des Experiments, das Analyseinstrumentarium, ist eine zielgerichtete, zeitliche Variation von Start-, Endzeitpunkt oder Laufzeitdauer von Abläufen der IT-Anwendung. Diese Herangehensweise ist automatisierbar und kann strukturiert und ohne hohen Lernaufwand im Softwareentwicklungsprozess angewandt werden. Mittels der Turingmaschine wird bewiesen, dass durch die zeitliche Variation des Analyseinstrumentariums die Korrektheit von sequentiellen Berechnung beibehalten wird. Dies wird auf nebenläufige Systeme mittels der parallelen Registermaschine erweitert und diskutiert. Mit diesem praxisnahen Maschinenmodell wird dargelegt, dass die entdeckten Wirkzusammenhänge des Analyseinstrumentariums Optimierungskandidaten identifizieren. Eine spezielle Experimentierumgebung, in der die Abläufe eines Systems, bestehend aus Software und Hardware, programmierbar variiert werden können, wird mittels einer Virtualisierungslösung realisiert. Techniken zur Nutzung des Analyseinstrumentariums durch eine Instrumentierung werden angegeben. Eine Methode zur Ermittlung von Mindestanforderungen von IT-Anwendungen an die Hardware wird präsentiert und mittels der Experimentierumgebung anhand von zwei Szenarios und dem Android Betriebssystem exemplifiziert. Verschiedene Verfahren, um aus den Beobachtungen des Experiments die Optimierungskandidaten des Systems zu eruieren, werden vorgestellt, klassifiziert und evaluiert. Die Identifikation von Optimierungskandidaten und -potenzial wird an Illustrationsszenarios und mehreren großen IT-Anwendungen mittels dieser Methoden praktisch demonstriert. Als konsequente Erweiterung wird auf Basis des Analyseinstrumentariums eine Testmethode zum Validieren eines Systems gegenüber nicht deterministisch reproduzierbaren Fehlern, die auf Grund mangelnder Synchronisationsmechanismen (z.B. Races) oder zeitlicher Abläufe entstehen (z.B. Heisenbugs, alterungsbedingte Fehler), angegeben.

Analyzing, understanding and working with complex systems and large datasets has become a familiar challenge in the information era. The explosion of data worldwide affects nearly every part of society, particularly the science, engineering, health, and financial domains. Looking, for instance at the automotive industry, engineers are confronted with the enormously increased complexity of vehicle electronics. Over the years, a large number of advanced functions, such as ACC (adaptive cruise control), rear seat entertainment systems or automatic start/stop engines, has been integrated into the vehicle. Thereby, the functions have been more and more distributed over the vehicle, leading to the introduction of several communication networks. Overlooking all relevant data facets, understanding dependencies, analyzing the flow of messages and tracking down problems in these networks has become a major challenge for automotive engineers. Promising approaches to overcome information overload and to provide insight into complex data are Information Visualization (InfoVis) and Visual Analytics (VA). Over the last decades, these research communities spent much effort on developing new methods to help users obtain insight into complex data. However, few of these solutions have yet reached end users, and moving research into practice remains one of the great challenges in visual data analysis. This situation is particularly true for large company settings, where very little is known about additional challenges, obstacles and requirements in InfoVis/VA development and evaluation. Users have to be better integrated into our research processes in terms of adequate requirements analysis, understanding practices and challenges, developing well-directed, user-centered technologies and evaluating their value within a realistic context. This dissertation explores a novel InfoVis/VA application area, namely in-car communication networks, and demonstrates how information visualization methods and techniques can help engineers to work with and better understand these networks. Based on a three-year internship with a large automotive company and the close cooperation with domain experts, I grounded a profound understanding of specific challenges, requirements and obstacles for InfoVis/VA application in this area and learned that “designing with not for the people” is highly important for successful solutions. The three main contributions of this dissertation are: (1) An empirical analysis of current working practices of automotive engineers and the derivation of specific design requirements for InfoVis/VA tools; (2) the successful application and evaluation of nine prototypes, including the deployment of five systems; and (3) based on the three-year experience, a set of recommendations for developing and evaluating InfoVis systems in large company settings. I present ethnographic studies with more than 150 automotive engineers. These studies helped us to understand currently used tools, the underlying data, tasks as well as user groups and to categorize the field into application sub-domains. Based on these findings, we propose implications and recommendations for designing tools to support current practices of automotive network engineers with InfoVis/VA technologies. I also present nine InfoVis design studies that we built and evaluated with automotive domain experts and use them to systematically explore the design space of applying InfoVis to in-car communication networks. Each prototype was developed in a user-centered, participatory process, respectively with a focus on a specific sub-domain of target users with specific data and tasks. Experimental results from studies with real users are presented, that show that the visualization prototypes can improve the engineers’ work in terms of working efficiency, better understanding and novel insights. Based on lessons learned from repeatedly designing and evaluating our tools together with domain experts at a large automotive company, I discuss challenges and present recommendations for deploying and evaluating VA/InfoVis tools in large company settings. I hope that these recommendations can guide other InfoVis researchers and practitioners in similar projects by providing them with new insights, such as the necessity for close integration with current tools and given processes, distributed knowledge and high degree of specialization, and the importance of addressing prevailing mental models and time restrictions. In general, I think that large company settings are a promising and fruitful field for novel InfoVis applications and expect our recommendations to be useful tools for other researchers and tool designers.

Gängige Theorien der mathematischen Finanzwirtschaft wie zum Beispiel der Mean-Variance-Ansatz zur Portfolio-Selektion oder Modelle zur Bewertung von Wertpapieren basieren alle auf der Annahme, dass Renditen im Zeitablauf unabhngig und identisch verteilt sind und einer Normalverteilung folgen. Empirische Untersuchungen liefern jedoch signifikante Hinweise dahingehend, dass diese Annahme f¨ur wichtige Anlageklassen unzutreffend ist. Stattdessen sindWertpapierrenditen zeitabh¨angige Volatilit¨aten, Heavy Tails (schwere Verteilungsr¨ander), Tail Dependence (Extremwertabh¨angigkeit) sowie Schiefe gekennzeichnet. Diese Eigenschaften haben Auswirkungen sowohl auf die theoretische als auch praktischeModellierung in der Finanzwirtschaft. Nach der Pr¨asentation des theoretischen Hintergrundes spricht die Arbeit die Modellierungsprobleme an, die sich aus diesen h¨aufig beobachteten Ph¨anomenen ergeben. Speziell werden Fragen bez¨uglich der Modellierung von Marktund Kreditrisiken volatiler M¨arkte behandelt als auch Probleme bei der Portfolio-Optimierung unter Verwendung alternativer Risikomae und Zielfunktionen. Fragen der praktischen Implementierung wird dabei besondere Aufmerksamkeit gewidmet.

Diffusion processes are a promising instrument to realistically model the time-continuous evolution of natural phenomena in life sciences. However, approximation of a given system is often carried out heuristically, leading to diffusions that do not correctly reflect the true dynamics of the original process. Moreover, statistical inference for diffusions proves to be challenging in practice as the likelihood function is typically intractable. This thesis contributes to stochastic modelling and statistical estimation of real problems in life sciences by means of diffusion processes. In particular, it creates a framework from existing and novel techniques for the correct approximation of pure Markov jump processes by diffusions. Concerning statistical inference, the thesis reviews existing practices and analyses and further develops a well-known Bayesian approach which introduces auxiliary observations by means of Markov chain Monte Carlo (MCMC) techniques. This procedure originally suffers from convergence problems which stem from a deterministic link between the model parameters and the quadratic variation of a continuously observed diffusion path. This thesis formulates a neat modification of the above approach for general multi-dimensional diffusions and provides the mathematical and empirical proof that the so-constructed MCMC scheme converges. The potential of the newly developed modelling and estimation methods is demonstrated in two real-data application studies: the spatial spread of human influenza in Germany and the in vivo binding behaviour of proteins in cell nuclei.