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

Quantile regression allows to model the complete conditional distribution of a response variable - expressed by its quantiles - depending on covariates, and thereby extends classical regression models which mainly address the conditional mean of a response variable.

The present thesis introduces the generic model class of structured additive quantile regression. This model class combines quantile regression with a structured additive predictor and thereby enables a variety of covariate effects to be flexibly modelled. Among other components, the structured additive predictor comprises smooth non-linear effects of continuous covariates and individual-specific effects which are particularly important in longitudinal data settings.

Furthermore, this thesis gives an extensive overview of existing approaches for parameter estimation in structured additive quantile regression models. These approaches are structured into distribution-free and distribution-based approaches as well as related model classes. Each approach is systematically discussed with regard to the four previously defined criteria, (i) which different components of the generic predictor can be estimated, (ii) which properties can be attributed to the estimators, (iii) if variable selection is possible, and, finally, (iv) if software is available for practical applications.

The main methodological development of this thesis is a boosting algorithm which is presented as an alternative estimation approach for structured additive quantile regression. The discussion of this innovative approach with respect to the four criteria points out that quantile boosting involves great advantages regarding almost all criteria - in particular regarding variable selection. In addition, the results of several simulation studies provide a practical comparison of boosting with alternative estimation approaches.

From the beginning of this thesis, the development of structured additive quantile regression is motivated by two relevant applications from the field of epidemiology: the investigation of risk factors for child undernutrition in India (by a cross-sectional study) and for child overweight and obesity in Germany (by a birth cohort study). In both applications, extreme quantiles of the response variables are modelled by structured additive quantile regression and estimated by quantile boosting. The results are described and discussed in detail.

Pathological studies show that tumors consist of different sub-regions with more homogeneous vascular properties during their growth. In addition, destroying tumor's blood supply is the target of most cancer therapies. Finding the sub-regions in the tissue of interest with similar perfusion patterns provides us with valuable information about tissue structure and angiogenesis. This information on cancer therapy, for example, can be used in monitoring the response of the cancer treatment to the drug. Cluster analysis of perfusion curves assays to find sub-regions with a similar perfusion pattern. The present work focuses on the cluster analysis of perfusion curves, measured by dynamic contrast enhanced magnetic resonance imaging (DCE-MRI). The study, besides searching for the proper clustering method, follows two other major topics, the choice of an appropriate similarity measure, and determining the number of clusters. These three subjects are connected to each other in such a way that success in one direction will help solving the other problems. This work introduces a new similarity measure, parallelism measure (PM), for comparing the parallelism in the washout phase of the signal curves. Most of the previous works used the Euclidean distance as the measure of dissimilarity. However, the Euclidean distance does not take the patterns of the signal curves into account and therefore for comparing the signal curves is not sufficient. To combine the advantages of both measures a two-steps clustering is developed. The two-steps clustering uses two different similarity measures, the introduced PM measure and Euclidean distance in two consecutive steps. The results of two-steps clustering are compared with the results of other clustering methods. The two-steps clustering besides good performance has some other advantages. The granularity and the number of clusters are controlled by thresholds defined by considering the noise in signal curves. The method is easy to implement and is robust against noise. The focus of the work is mainly the cluster analysis of breast tumors in DCE-MRI datasets. The possibility to adopt the method for liver datasets is studied as well.

Random Forests are widely used for data prediction and interpretation purposes. They

show many appealing characteristics, such as the ability to deal with high dimensional data,

complex interactions and correlations. Furthermore, missing values can easily be processed

by the built-in procedure of surrogate splits. However, there is only little knowledge about

the properties of recursive partitioning in missing data situations. Therefore, extensive

simulation studies and empirical evaluations have been conducted to gain deeper insight.

In addition, new methods have been developed to enhance methodology and solve current

issues of data interpretation, prediction and variable selection.

A variable’s relevance in a Random Forest can be assessed by means of importance

measures. Unfortunately, existing methods cannot be applied when the data contain miss-

ing values. Thus, one of the most appreciated properties of Random Forests – its ability

to handle missing values – gets lost for the computation of such measures. This work

presents a new approach that is designed to deal with missing values in an intuitive and

straightforward way, yet retains widely appreciated qualities of existing methods. Results

indicate that it meets sensible requirements and shows good variable ranking properties.

Random Forests provide variable selection that is usually based on importance mea-

sures. An extensive review of corresponding literature led to the development of a new

approach that is based on a profound theoretical framework and meets important statis-

tical properties. A comparison to another eight popular methods showed that it controls

the test-wise and family-wise error rate, provides a higher power to distinguish relevant

from non-relevant variables and leads to models located among the best performing ones.

Alternative ways to handle missing values are the application of imputation methods

and complete case analysis. Yet it is unknown to what extent these approaches are able

to provide sensible variable rankings and meaningful variable selections. Investigations

showed that complete case analysis leads to inaccurate variable selection as it may in-

appropriately penalize the importance of fully observed variables. By contrast, the new

importance measure decreases for variables with missing values and therefore causes se-

lections that accurately reflect the information given in actual data situations. Multiple

imputation leads to an assessment of a variable’s importance and to selection frequencies

that would be expected for data that was completely observed. In several performance

evaluations the best prediction accuracy emerged from multiple imputation, closely fol-

lowed by the application of surrogate splits. Complete case analysis clearly performed

worst.

As software systems rise in size and complexity, the need for verifying some of their properties

increases. One important property to be verified is the resource usage, i.e. how many resources the program will need for its execution, where resources include execution time, memory,

power, etc. Resource usage analysis is important in many areas, in particular embedded systems

and cloud computing. Thus, resource analysis has been widely researched and some different

approaches to this have been proposed based in particular on recurrence solving, abstract

interpretation and amortised analysis.

In the amortised analysis technique, a nonnegative number, called potential, is assigned to a data structure. The amortised cost of operations is then defined by its actual cost plus the difference in potential of the data structure before and after performing the operation.

Amortised analysis has been used for automatic resource analysis of functional and object-oriented programs. The potentials are defined using refined types and typing rules then ensure that potential and actual resource usage is accounted for correctly. The automatic inference of the potential functions can then be achieved by type inference.

In the case of functional programs, the structure of the types is known. Thus, type inference can be

reduced to solving linear arithmetic constraints. For object-oriented programs, however, the refined

types are more complicated because of the general nature of objects: they can be used to define any

data structure. Thus, the type inference must discover not only the potential functions for the data structure but also the data structures themselves. Other features of object-oriented programs that complicate the analysis are aliasing and imperative update. Hofmann and Jost presented in 2006 a type system for amortised heap-space analysis of object-oriented programs, called Resource Aware JAva (RAJA). However, they left the problem of type inference open.

In this thesis we present a type inference algorithm for the RAJA system. We were able to reduce the type inference problem to the novel problem of satisfiability of arithmetic constraints over infinite trees and we developed a heuristic algorithm for satisfiability of these constraints. We proved the soundness of the type inference algorithm and developed an OCaml implementation and experimental evaluation that shows that we can compute linear upper-bounds to the heap-space requirements of many programs, including sorting algorithms for lists such as insertion sort and merge sort and also programs that contain different interacting objects that describe real-life scenarios like a bank account.

Another contribution of this thesis is a type checking algorithm for the RAJA system that is useful for verifying the types discovered by the type inference by using the \emph{proof carrying code} technology.

A generally observable trend of the past 10 years is that the amount of sensors embedded in mobile devices such as smart phones and tablets is rising steadily. Arguably, the available sensors are mostly underutilized by existing mobile user interfaces. In this dissertation, we explore sensor-based user interface concepts for mobile devices with the goal of making better use of the available sensing capabilities on mobile devices as well as gaining insights on the types of sensor technologies that could be added to future mobile devices. We are particularly interested how novel sensor technologies could be used to implement novel and engaging mobile user interface concepts.

We explore three particular areas of interest for research into sensor-based user interface concepts for mobile devices: continuous interaction, around-device interaction and motion gestures.

For continuous interaction, we explore the use of dynamic state-space systems to implement user interfaces based on a constant sensor data stream. In particular, we examine zoom automation in tilt-based map scrolling interfaces. We show that although fully automatic zooming is desirable in certain situations, adding a manual override capability of the zoom level (Semi-Automatic Zooming) will increase the usability of such a system, as shown through a decrease in task completion times and improved user ratings of user study. The presented work on continuous interaction also highlights how the sensors embedded in current mobile devices can be used to support complex interaction tasks.

We go on to introduce the concept of Around-Device Interaction (ADI). By extending the interactive area of the mobile device to its entire surface and the physical volume surrounding it we aim to show how the expressivity and possibilities of mobile input can be improved this way. We derive a design space for ADI and evaluate three prototypes in this context. HoverFlow is a prototype allowing coarse hand gesture recognition around a mobile device using only a simple set of sensors. PalmSpace a prototype exploring the use of depth cameras on mobile devices to track the user's hands in direct manipulation interfaces through spatial gestures. Lastly, the iPhone Sandwich is a prototype supporting dual-sided pressure-sensitive multi-touch interaction. Through the results of user studies, we show that ADI can lead to improved usability for mobile user interfaces. Furthermore, the work on ADI contributes suggestions for the types of sensors could be incorporated in future mobile devices to expand the input capabilities of those devices.

In order to broaden the scope of uses for mobile accelerometer and gyroscope data, we conducted research on motion gesture recognition. With the aim of supporting practitioners and researchers in integrating motion gestures into their user interfaces at early development stages, we developed two motion gesture recognition algorithms, the $3 Gesture Recognizer and Protractor 3D that are easy to incorporate into existing projects, have good recognition rates and require a low amount of training data. To exemplify an application area for motion gestures, we present the results of a study on the feasibility and usability of gesture-based authentication.

With the goal of making it easier to connect meaningful functionality with gesture-based input, we developed Mayhem, a graphical end-user programming tool for users without prior programming skills. Mayhem can be used to for rapid prototyping of mobile gestural user interfaces.

The main contribution of this dissertation is the development of a number of novel user interface concepts for sensor-based interaction. They will help developers of mobile user interfaces make better use of the existing sensory capabilities of mobile devices. Furthermore, manufacturers of mobile device hardware obtain suggestions for the types of novel sensor technologies that are needed in order to expand the input capabilitie

In this thesis, we analyze nonparametric estimation of Lévy-based models using wavelets methods. As the considered class is restricted to pure-jump Lévy processes, it is sufficient to estimate their Lévy densities. For implementing a wavelet density estimator, it is necessary to setup a preliminary histogram estimator. Simulation studies show that there is an improvement of the wavelet estimator by invoking an optimally selected histogram. The wavelet estimator is based on block-thresholding of empirical coefficients. We conclude with two empirical applications which show that there is a very high arrival rate of small jumps in financial data sets.

Ortsbezogene Dienste (Location-based Services, LBS) sind in den letzten Jahren durch die weite Verfügbarkeit von GPS zu einem Massenphänomen gewachsen. Insbesondere für die Steuerung von mobilen Endgeräten wird mehr und mehr Kontextinformation hinzugenommen, da sowohl die Bedienbarkeit als auch die Informationsdichte auf den kleinen Smartphones im Kontrast zur Informationsfülle des Internets stehen. Daher werden vielfach Dienste nicht mehr allein auf der Nutzereingabe basierend erbracht (reaktiv), sondern bieten dem Nutzer relevante Informationen vollautomatisch und kontextabhängig (proaktiv) an.

Durch die proaktive Diensterbringung und ortsbezogene Personalisierung wird die Benutzbarkeit der Dienste verbessert. Leider kann man derzeit solche Dienste nur außerhalb von Gebäuden anbieten, da zum Einen kein einheitliches und günstiges Positionierungssystem verfügbar ist, und zum Anderen die notwendigen Kartendaten nicht vorliegen. Vor allem bei den Kartendaten fehlt es an einfachen Standards und Tools, die es dem Eigentümer eines Gebäudes ermöglichen, qualitativ hochwertige Kartendaten zur Verfügung zu stellen.

In der vorliegenden Dissertation werden einige notwendige Schritte zur Ermöglichung ubiquitärer und skalierbarer

Indoornavigation vorgestellt. Hierbei werden die Themenfelder Positionierung, Modellierung und Kartographie, sowie Navigation und Wegfindung in einen umfassenden Zusammenhang gestellt, um so eine tragfähige, einfache und skalierbare Navigation zu ermöglichen. Zunächst werden einige Verbesserungen an Terminal-basierten WLAN-Indoorpositionierungssystemen vorgeschlagen und diskutiert, die teils auf der Verwendung neuer Sensorik aktueller Smartphones basieren, und teils auf der Verwendung besonders kompakter Umgebungsmodelle auf mobilen Endgeräten. Insbesondere werden Verfahren vorgeschlagen und evaluiert, mit denen sich aus typischen CAD-Daten mit geringem Bearbeitungsaufwand die notwendigen Zusatzinformationen für eine flächendeckende Indoornavigation modellieren lassen. Darüber hinaus werden Methoden untersucht, die diese semantischen Erweiterungen teil- bzw. vollautomatisch aus Zeichnungen extrahieren können. Ausgehend von dem Ziel, flächendeckende Navigation basierend auf CAD-Daten zu ermöglichen, stößt man auf das Problem, eine Menge an interessanten Punkten so zu ordnen, dass der Reiseweg kurz ist.Dieses Problem ist mit dem NP-vollständigen Travelling-Salesman-Problem verwandt. Allerdings ist die geometrische Situation in Gebäuden derart komplex, dass sich die meisten derzeit bekannten heuristischen Lösungsalgorithmen für das Travelling-Salesman-Problem nicht ohne Weiteres auf die Situation im Inneren von Gebäuden übertragen lassen. Für dieses Problem wird ein heuristischer Algorithmus angegeben, der in linearer Laufzeit kleinere Instanzen des Problems mit akzeptablen Fehlern lösen kann. Diese Verfahren wurden im Rahmen eines Projekts mit dem Flughafen München erarbeitet und umgesetzt. In diesem Projekt sollten die ungelösten Probleme einer bereits existierenden kleinflächigen Demonstrator-Implementierung eines Fluggastinformationssystems gelöst werden. Auf diesen Algorithmen und Verfahren basiert die Navigationskomponente des Fluggastinformationssystems InfoGate, das die flächendeckende Navigation in den Terminals des Flughafen München mit verteilten Anzeigesystemen ermöglicht und seit dem 6. Juni 2011 im Produktivbetrieb ist. So konnten die Verfahren dieser Arbeit in einer real existierenden, komplexen Umgebung evaluiert werden.

The interconnection of vehicles is an important topic concerning the enhancement of

traffic safety and trffic efficiency. Therefore, vehicles exchange position and state information

with each other to establish an awareness level for the calculation of collision

probabilities with their neighbors. To recognize critical safety situations it is essential to

receive information reliably. However, these systems are typically based on wireless ad-hoc

networks that cannot guarantee reliable packet transmission. This is especially the case in

situations where a high number of communication nodes exist.

The aim of this work at hand is the definition of a beaconing algorithm that enables the

establishment of a desired awareness level for critical safety situations especially in high

density traffic scenarios.

First, representative scenarios for collision detection and collision avoidance were specified and metrics for the evaluation of the beaconing algorithms were defined. Based on

these metrics the performance of beaconing algorithms with different static periodical update

rates was evaluated. It is presented that these kinds of beaconing algorithms cannot

provide sfficient results with respect to the required constant information throughput in

high density traffic situations. To provide a high awareness level for each vehicle in its

individual situation in spite of an unreliable communication channel a service-oriented beaconing

approach is dened in this work. It is based on a request/response communication

scheme to compensate particular packet loss. Hereby, a broadcast and a unicast occurrence

of the algorithm are defined accordingly to the corresponding representative scenarios.

It is presented that the service-oriented beaconing approach provides a signicant benefit with respect to the information throughput for low and middle traffic density situations.

However, in high density situations the benefit of this approach is decreasing due to the

increased communication overhead. This is a result of using one single communication

channel. To achieve a high awareness level also in high density trac situations, a signi-

cant modification was defined. Therefore, the usage of multiple communication channels

was introduced to distribute the communication load over several channels. It is specified

to send all service responses on a dedicated service channel to reduce the load on the control

channel where the service requests are transmitted. After an extensive evaluation of

the multi-channel utilization in vehicle ad-hoc networks using IEEE 802.11p it is shown

that the multi-channel version of the service-oriented beaconing approach can achieve significant benefits concerning the information throughput for the collision detection and

collision avoidance scenarios even in high density traffic situations.

The human-machine interfaces (HMIs) of today’s premium automotive infotainment systems are complex embedded systems which have special characteristics in comparison to GUIs of standard PC applications, in particular regarding their variability. The variability of infotainment system HMIs results from different car models, product series, markets, equipment configuration possibilities, system types and languages and necessitates enormous testing efforts. The model-based testing approach is a promising solution for reducing testing efforts and increasing test coverage. However, while model-based testing has been widely used for function tests of subsystems in practice, HMI tests have remained manual or only semi-automated and are very time-consuming and work-intensive. Also, it is very difficult to achieve systematic or high test coverage via manual tests. A large amount of research work has addressed GUI testing in recent years. In addition, variability is becoming an ever more popular topic in the domain of software product line development. However, a model-based testing approach for complex HMIs which also considers variability is still lacking. This thesis presents a model-based testing approach for infotainment system HMIs with the particular aim of resolving the variability problem. Furthermore, the thesis provides a foundation for future standards of HMI testing in practice.

The proposed approach is based on a model-based HMI testing framework which includes two essential components: a test-oriented HMI specification and a test generation component. The test-oriented HMI specification has a layered structure and is suited to specifying data which is required for testing different features of the HMI. Both the dynamic behavior and the representation of the HMI are the testing focuses of this thesis. The test generation component automatically generates tests from the test-oriented HMI specification. Furthermore, the framework can be extended in order to automatically execute the generated tests. Generated tests must first be initialized, which means that they are enhanced with concrete user input data. Afterwards, initialized tests can be automatically executed with the help of a test execution tool which must be extended into the testing framework.

In this thesis, it is proposed to specify and test different HMI-variants which have a large set of commonalities based on the software product line approach. This means the test-oriented HMI specification is extended in order to describe the commonalities and variabilities between HMI variants of an HMI product line. In particular, strategies are developed in order to generate tests for different HMI products. One special feature is that redundancies are avoided both for the test generation and the execution processes. This is especially important for the industrial practice due to limited test resources. Modeling and testing variability of automotive HMIs make up the main research contributions of this thesis.

We hope that the results presented in this thesis will offer GUI testing research a solution for model-based testing of multi-variant HMIs and provide the automotive industry with a foundation for future HMI testing standards.