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

Cloud Computing bietet dem Nutzer die Möglichkeit, virtualisierte Applikationen, Plattformen und sogar Hardware wie Dienste zu nutzen. Der bereitstellende Provider kann die nötige Dienstkapazität in der Cloud elastisch an den aktuellen Bedarf anpassen. Durch die beliebige Ressourcenzuschaltung erwächst jedoch eine erhebliche ökologische und ökonomische Verantwortung. Zudem wird meist teuer überprovisioniert, um im Falle von Lastspitzen das Ablehnen von Anfragen zu vermeiden.

Bis heute bietet noch kein Anbieter eine voll automatisierte Lösung zum optimalen Ressourcenmanagement an. Zur Gewährleistung der Skalierbarkeit eines Cloud-basierten Systems bestehen lediglich regelbasierte Mechanismen. Der Nutzer muss die Logik manuell einstellen, um die benötigte Anzahl an Maschinen und ihre Lokalität festzulegen. So sind viele Fragen zu der Ressourcenverwaltung und den entstehenden Kosten für den Cloud-Anwender ungelöst.

In dieser Arbeit wird ein Protokoll entwickelt, das eine verbesserte Reihenfolge der Anfragenbearbeitung festlegt und die nötige Ressourcenmenge bestimmt. Die Ressourcenzuteilung basiert zum einen auf der Bedarfsreservierung durch die Ressourcen. Zum anderen kann das Nutzungsverhalten durch den Dienst beeinflusst werden. Die Simulationsergebnisse zeigen so stark reduzierte Antwortzeiten und Verwurfsraten.

Im Cloud-Umfeld ist die effiziente Bearbeitung der Anfragen allerdings häufig aufgrund von Abhängigkeiten zwischen den dienstbetreibenden Maschinen beeinträchtigt. Deshalb wird das Protokoll um einen Selbstkalibrierungsmechanismus und ein Ressourcenregelverfahren erweitert. Mit der Abbildung der Abhängigkeiten auf einen Graphen ist das Gesamtsystem skalierbar, ohne die Auslastung aller Ressourcen einzeln kontrollieren zu müssen.

Vom menschlichen Benutzer kann man jedoch keine Vorabreservierung bezüglich des Zeitpunkts seiner Dienstnutzung fordern - so wie das von Maschinen problemlos möglich ist. Für diesen Fall ermöglicht die vorliegende Arbeit deshalb die Extrapolation der Nutzerdaten aus Aufzeichnungen sozialer Netzwerke. Ohne Belastung der Anwender wird die Identifikation des Ressourcenbedarfs an einem bestimmten Ort realisiert.

Für eine solche Systemadaption führt der in dieser Arbeit entworfene Algorithmus eine ortsspezifische Vorhersagende der nötigen Ressourcenanzahl durch. Diese Informationen dienen als Input für das entwickelte Protokoll und bieten so eine wohlproportionierte Provisionierung.

Die bei Skalierungen entstehenden Kosten sind meist schwer abzuschätzen. Aus diesem Grund werden im Verlauf dieser Arbeit Kostenfunktionen für den Nutzer und den Anbieter erstellt. Sie machen das optimale Mittel zwischen geringeren Kosten bei niedriger Ressourcenmenge und höherer Nutzerzufriedenheit bei großzügiger Kapazitätsabdeckung berechenbar.

Eine prototypische Umsetzung einschließlich verschiedener Simulationen zeigt, dass die entwickelten Ansätze ein deutlich verbessertes automatisiertes Ressourcenmanagement umsetzen.

In our everyday life we carry out a multitude of activities in parallel without focusing our attention explicitly on them. We drink a cup of tea while reading a book, we signal a colleague passing by with a hand gesture, that we are concentrated right now and that he should wait one moment, or we walk a few steps backwards while taking photos. Many of these interactions - like drinking, sending signals via gestures or walking - are rather complex by themselves. By means of learning and training, however, these interactions become part of our routines and habits and therefore only consume little or no attentional resources. In contrast, when interacting with digital devices, we are often asked for our full attention. To carry out - even small and marginal tasks - we are regularly forced to switch windows, do precise interactions (e.g., pointing with the mouse) and thereby these systems trigger context and focus switches, disrupting us in our main focus and task. Peripheral interaction aims at making use of human capabilities and senses like divided attention, spatial memory and proprioception to support interaction with digital devices in the periphery of the attention, consequently quasi-parallel to another primary task.

In this thesis we investigate peripheral interaction in the context of a standard desktop computer environment. We explore three interaction styles for peripheral interaction: graspable interaction, touch input and freehand gestures. StaTube investigates graspable interaction in the domain of instant messaging, while the Appointment Projection uses simple wiping gestures to access information about upcoming appointments. These two explorations focus on one interaction style each and offer first insights into the general benefits of peripheral interaction. In the following we carried out two studies comparing all three interaction styles (graspable, touch, freehand) for audio player control and for dealing with notifications. We found that all three interaction styles are generally fit for peripheral interaction but come with different advantages and disadvantages. The last set of explorative studies deals with the ability to recall spatial locations in 2D as well as 3D. The Unadorned Desk makes use of the physical space around the desktop computer and thereby offers an extended interaction space to store and retrieve virtual items such as commands, applications or tools. Finally, evaluation of peripheral interaction is not straightforward as the systems are designed to blend into the environment and not draw attention on them. We propose an additional evaluation method for the lab to complement the current evaluation practice in the field.

The main contributions of this thesis are (1) an exhaustive classification and a more detailed look at manual peripheral interaction for tangible, touch and freehand interaction. Based on these exploration with all three interaction styles, we offer (2) implications in terms of overall benefits of peripheral interaction, learnability and habituation, visual and mental attention, feedback and handedness for future peripheral interaction design. Finally, derived from a diverse set of user studies, we assess (3) evaluation strategies enriching the design process for peripheral interaction.

One of the most frequent ways to interact with the surrounding environment occurs

as a visual way. Hence imaging is a very common way in order to gain information

and learn from the environment. Particularly in the field of cellular biology, imaging

is applied in order to get an insight into the minute world of cellular complexes. As

a result, in recent years many researches have focused on developing new suitable

image processing approaches which have facilitates the extraction of meaningful

quantitative information from image data sets. In spite of recent progress, but due to

the huge data set of acquired images and the demand for increasing precision, digital

image processing and statistical analysis are gaining more and more importance in

this field.

There are still limitations in bioimaging techniques that are preventing sophisticated

optical methods from reaching their full potential. For instance, in the 3D

Electron Microscopy(3DEM) process nearly all acquired images require manual postprocessing

to enhance the performance, which should be substitute by an automatic

and reliable approach (dealt in Part I). Furthermore, the algorithms to localize individual

fluorophores in 3D super-resolution microscopy data are still in their initial

phase (discussed in Part II). In general, biologists currently lack automated and high

throughput methods for quantitative global analysis of 3D gene structures.

This thesis focuses mainly on microscopy imaging approaches based on Machine

Learning, statistical analysis and image processing in order to cope and improve the

task of quantitative analysis of huge image data. The main task consists of building

a novel paradigm for microscopy imaging processes which is able to work in an

automatic, accurate and reliable way.

The specific contributions of this thesis can be summarized as follows:

• Substitution of the time-consuming, subjective and laborious task of manual

post-picking in Cryo-EM process by a fully automatic particle post-picking

routine based on Machine Learning methods (Part I).

• Quality enhancement of the 3D reconstruction image due to the high performance

of automatically post-picking steps (Part I).

• Developing a full automatic tool for detecting subcellular objects in multichannel

3D Fluorescence images (Part II).

• Extension of known colocalization analysis by using spatial statistics in order

to investigate the surrounding point distribution and enabling to analyze the

colocalization in combination with statistical significance (Part II).

All introduced approaches are implemented and provided as toolboxes which are

free available for research purposes.

Although time measurements are routinely performed in laboratories, their theoretical description is still an open problem.

Similarly, also the validity and the status of the energy-time uncertainty relation is unsettled.

In the first part of this work the necessity of positive operator valued measures (POVM) as descriptions of every quantum experiment is reviewed, as well as the suggestive role played by the probability current in time measurements.

Furthermore, it is shown that no POVM exists, which approximately agrees with the probability current on a very natural set of wave functions; nevertheless, the choice of the set is crucial, and on more restrictive sets the probability current does provide a good arrival time prediction.

Some ideas to experimentally detect quantum effects in time measurements are discussed.

In the second part of the work the energy-time uncertainty relation is considered, in particular for a model of alpha decay for which the variance of the energy can be calculated explicitly, and the variance of time can be estimated.

This estimate is tight for systems with long lifetimes, in which case the uncertainty relation is shown to be satisfied.

Also the linewidth-lifetime relation is shown to hold, but contrary to the common expectation, it is found that the two relations behave independently, and therefore it is not possible to interpret one as a consequence of the other.

To perform the mentioned analysis quantitative scattering estimates are necessary.

To this end, bounds of the form $\|\1_Re^{-iHt}\psi\|_2^2 \leq C t^{-3}$ have been derived, where $\psi$ denotes the initial state, $H$ the Hamiltonian, $R$ a positive constant, and $C$ is explicitly known.

As intermediate step, bounds on the derivatives of the $S$-matrix in the form $\|\1_K S^{(n)}\|_\infty \leq C_{n,K} $ have been established, with $n=1,2,3$, and the constants $C_{n,K}$ explicitly known.

This thesis is concerned with quantum mechanical decay processes and their mathematical description. It consists out of three parts:

In the first part we look at Laser induced ionization, whose mathematical description is often based on the so-called dipole approximation. Employing it essentially means to replace the Laser's vector potential $\vec A(\vec r,t)$ in the Hamiltonian by $\vec A(0, t).$ Heuristically this is justified under usual experimental conditions, because the Laser varies only slowly in $\vec r$ on atomic length scales. We make this heuristics rigorous by proving the dipole approximation in the limit in which the Laser's length scale becomes infinite compared to the atomic length scale. Our results apply to $N$-body Hamiltonians.

In the second part we look at alpha decay as described by Skibsted (Comm. Math. Phys. 104, 1986) and show that Skibsted's model satisfies an energy-time uncertainty relation. Since there is no self-adjoint time operator, the uncertainty relation for energy and time can not be proven in the same way as the uncertainty relation for position and momentum. To define the time variance without a self-adjoint time operator, we will use the arrival time distribution obtained from the quantum current. Our proof of the energy-time uncertainty relation is then based on the quantitative scattering estimates that will be derived in the third part of the thesis and on a result from Skibsted. In addition to that, we will show that this uncertainty relation is different from the well known {\it linewidth-lifetime relation}.

The third part is about quantitative scattering estimates, which are of interest in their own right. For rotationally symmetric potentials having support in $[0,R_V]$ we will show that for $R\geq R_V$, the time evolved wave function $e^{-iHt}\psi$ satisfies

\begin{align}\nonumber

\|\1_R e^{-iHt}\psi\|_2^2\leq c_1t^{-1}+c_2t^{-2}+c_3t^{-3}+c_4t^{-4}

\end{align}

with explicit quantitative bounds on the constants $c_n$ in terms of the resonances of the $S$-Matrix. While such bounds on $\|\1_R e^{-iHt}\psi\|_2$ have been proven before, the quantitative estimates on the constants $c_n$ are new. These results are based on a detailed analysis of the $S$-matrix in the complex momentum plane, which in turn becomes possible by expressing the $S$-matrix in terms of the Jost function that can be factorized in a Hadamard product.

Ein heutiger Computerarbeitsplatz besteht normalerweise aus einer horizontalen Arbeitsfläche und mindestens einem vertikalen Bildschirm. Beide Orientierungen der Arbeitsbereiche haben Vorteile für einzelne Arbeitsschritte. Auf vertikalen Flächen ist beispielsweise das Lesen langer Texte ergonomischer, während das direkte Bearbeiten von Texten auf horizontalen Flächen weniger anstrengend ist. Der Wechsel zwischen den beiden Arbeitsbereichen ist jedoch umständlich, da die horizontale Arbeitsfläche häufig nicht digital ist. Doch selbst die steigende Verbreitung berührungsempfindlicher Bildschirme im horizontalen Arbeitsbereich (z.B. Tablets) löst dieses Problem nicht. Zwar bringen diese Geräte zum einen die Vorteile direkter Interaktion mit sich, führen aber zum anderen zur Frage, wie die digitalen Inhalte zwischen den unterschiedlich orientierten, digitalen Bereichen ausgetauscht werden.

Eine Lösung hierfür ist die Kombination unterschiedlich orientierter Displays. Es gibt mehrere Ansätze diese zu kombinieren, jedoch sind die Displays dabei meistens physikalisch voneinander getrennt. Das führt dazu, dass der Nutzer die Displays zum einen eher als separate Einheiten wahrnimmt und zum anderen kein einfacher Übergang zwischen den Displays möglich ist. Eine Verbindungsart, die bis jetzt noch weitgehend unerforscht ist, ist die Kombination beider Displaybereiche durch eine gebogene Verbindung. Die Biegung stellt eine nahtlose Verbindung und einen unterbrechungsfreien Übergang zwischen den Displaybereichen her. Der Effekt eines solchen Übergangs auf die Nutzerinteraktion ist jedoch unbekannt. Die Biegung des Bildschirms eröffnet darüber hinaus auch die Möglichkeit für neuartige Visualisierungen, die von der nahtlosen Kombination unterschiedlicher Displayorientierungen profitieren. Außerdem können auch gewöhnliche, grafische Benutzerschnittstellen hinsichtlich der Displayform optimiert werden.

Im Rahmen dieser Arbeit wird ein solches Display vorgestellt und dessen Effekte auf die Nutzerinteraktion und Potenziale für grafische Benutzerschnittstellen untersucht. Der Curve ist ein interaktives Display, das einen horizontalen und einen vertikalen Bereich durch eine nahtlose, gebogene Verbindung kombiniert. Im ersten Teil der Arbeit werden die Entwicklung der Displayform und die technische Umsetzung des Prototyps beschrieben. Anschließend wird im zweiten Teil der Einfluss der Displayform sowohl auf direkte als auch auf indirekte Interaktionsarten evaluiert. Außerdem wird der Curve um eine greifbare Benutzerschnittstelle erweitert und die Auswirkung der Displayform auf die Bedienbarkeit dieser Schnittstelle untersucht. Im dritten Teil werden zwei Visualisierungen und eine vorhandene, grafische Benutzerschnittstelle vorgestellt, die jeweils an die gebogene Displayform angepasst wurden. Die praktischen Erfahrungen aus den Entwicklungsprozessen werden dann in Form von Empfehlungen für vergleichbare Displayprojekte zusammengefasst. Am Ende der Arbeit stehen sowohl Ausgangspunkte für eine technische Weiterentwicklung, als auch weitere exemplarische Anwendungsszenarien, die von der gebogenen Displayform des Curve profitieren können.

Program extraction has been initiated in the field of constructive

mathematics, and it attracts interest not only from mathematicians but

also from computer scientists nowadays. From a mathematical viewpoint

its aim is to figure out computational meaning of proofs, while from a

computer-scientific viewpoint its aim is the study of a method to

obtain correct programs. Therefore, it is natural to have both

theoretical results and a practical computer system to develop

executable programs via program extraction.

In this Thesis we study the computational interpretation of

constructive proofs involving inductive and coinductive reasoning. We

interpret proofs by translating the computational content of proofs

into executable program code. This translation is the procedure we

call program extraction and it is given through Kreisel's modified

realizability. Here we study a proof-theoretic foundation for program

extraction, enriching the proof assistant system Minlog based on this

theoretical improvement. Once a proof of a formula is written in

Minlog, a program can be extracted from the proof by the system

itself, and the extracted program can be executed in Minlog.

Moreover, extracted programs are provably correct with respect to the

proven formula due to a soundness theorem which we prove. We practice

program extraction by elaborating some case studies from exact real

arithmetic within our formal theory. Although these case studies have

been studied elsewhere, here we offer a formalization of them in

Minlog, and also machine-extraction of the corresponding programs.

Knowledge Discovery in Databases (KDD) ist der Prozess, nicht-triviale Muster aus großen Datenbanken zu extrahieren, mit dem Ziel, dass diese bisher unbekannt, potentiell nützlich, statistisch fundiert und verständlich sind. Der Prozess umfasst mehrere Schritte wie die Selektion, Vorverarbeitung, Evaluierung und den Analyseschritt, der als Data-Mining bekannt ist. Eine der zentralen Aufgabenstellungen im Data-Mining ist die Ausreißererkennung, das Identifizieren von Beobachtungen, die ungewöhnlich sind und mit der Mehrzahl der Daten inkonsistent erscheinen. Solche seltene Beobachtungen können verschiedene Ursachen haben:

Messfehler, ungewöhnlich starke (aber dennoch genuine) Abweichungen, beschädigte oder auch manipulierte Daten. In den letzten Jahren wurden zahlreiche Verfahren zur Erkennung von Ausreißern vorgeschlagen, die sich oft nur geringfügig zu unterscheiden scheinen, aber in den Publikationen experimental als ``klar besser'' dargestellt sind. Ein Schwerpunkt dieser Arbeit ist es, die unterschiedlichen Verfahren zusammenzuführen und in einem gemeinsamen Formalismus zu modularisieren. Damit wird einerseits die Analyse der Unterschiede vereinfacht, andererseits aber die Flexibilität der Verfahren erhöht, indem man Module hinzufügen oder ersetzen und damit die Methode an geänderte Anforderungen und Datentypen anpassen kann.

Um die Vorteile der modularisierten Struktur zu zeigen, werden

(i) zahlreiche bestehende Algorithmen in dem Schema formalisiert,

(ii) neue Module hinzugefügt, um die Robustheit, Effizienz, statistische Aussagekraft und Nutzbarkeit der Bewertungsfunktionen zu verbessern, mit denen die existierenden Methoden kombiniert werden können,

(iii) Module modifiziert, um bestehende und neue Algorithmen auf andere, oft komplexere, Datentypen anzuwenden wie geographisch annotierte Daten, Zeitreihen und hochdimensionale Räume,

(iv) mehrere Methoden in ein Verfahren kombiniert, um bessere Ergebnisse zu erzielen,

(v) die Skalierbarkeit auf große Datenmengen durch approximative oder exakte Indizierung verbessert.

Ausgangspunkt der Arbeit ist der Algorithmus Local Outlier Factor (LOF). Er wird zunächst mit kleinen Erweiterungen modifiziert, um die Robustheit und die Nutzbarkeit der Bewertung zu verbessern. Diese Methoden werden anschließend in einem gemeinsamen Rahmen zur Erkennung lokaler Ausreißer formalisiert, um die entsprechenden Vorteile auch in anderen Algorithmen nutzen zu können. Durch Abstraktion von einem einzelnen Vektorraum zu allgemeinen Datentypen können auch räumliche und zeitliche Beziehungen analysiert werden. Die Verwendung von Unterraum- und Korrelations-basierten Nachbarschaften ermöglicht dann, einen neue Arten von Ausreißern in beliebig orientierten Projektionen zu erkennen. Verbesserungen bei den Bewertungsfunktionen erlauben es, die Bewertung mit der statistischen Intuition einer Wahrscheinlichkeit zu interpretieren und nicht nur eine Ausreißer-Rangfolge zu erstellen wie zuvor. Verbesserte Modelle generieren auch Erklärungen, warum ein Objekt als Ausreißer bewertet wurde.

Anschließend werden für verschiedene Module Verbesserungen eingeführt, die unter anderem ermöglichen, die Algorithmen auf wesentlich größere Datensätze anzuwenden -- in annähernd linearer statt in quadratischer Zeit --, indem man approximative Nachbarschaften bei geringem Verlust an Präzision und Effektivität erlaubt. Des weiteren wird gezeigt, wie mehrere solcher Algorithmen mit unterschiedlichen Intuitionen gleichzeitig benutzt und die Ergebnisse in einer Methode kombiniert werden können, die dadurch unterschiedliche Arten von Ausreißern erkennen kann.

Schließlich werden für reale Datensätze neue Ausreißeralgorithmen konstruiert, die auf das spezifische Problem angepasst sind. Diese neuen Methoden erlauben es, so aufschlussreiche Ergebnisse zu erhalten, die mit den bestehenden Methoden nicht erreicht werden konnten. Da sie aus den Bausteinen der modularen Struktur entwickelt wurden, ist ein direkter Bezug z

This thesis is about an operator algebraic approach towards the derivation of the electrical conductivity in disordered solid states based on the theory of quantum many-particle systems. Such an approach is of interest since it allows for the description of interacting electron gases, which is a feature not present in previous work.

In the context of the description of ergodic media, new concepts are introduced, such as covariant states and covariant morphisms. Moreover, the concept of covariant states is combined with the well-known concept of KMS states.

In its covariant form, KMS states describe electron gases in ergodic media at thermal equilibrium. Such states are the starting point of the electron gases considered here. An external electric field is applied to the system, influences the electron gas and causes internal electric currents. Thus, the equilibrium position of the system is disturbed, leading to a time evolution of the system, which is described by covariant automorphisms. Summing up, the system is given in a time dependent, covariant state that acts on the algebra of bounded and local operators on the fermionic Fock space defined over some given one-particle Hilbert space. For a discrete model of an extended electron gas in one space dimension with a pair interaction of finite range, explicit constructions of the above states are presented. In addition, for the special case of non-interacting electron gases, the construction of the time dependent covariant state is carried out in arbitrary space dimension.

Since measurements in a quantum system are implemented by the action of its state on bounded, local and self-adjoint operators, the concept of a current density operator is introduced. The current density is then defined as the result of the measurement of the current density operator. By an application of Birkhoff’s ergodic theorem, the transformation law of the current density operator together with the covariant transformation law of the state of the electron gas implies the almost sure existence of the spatial mean of the current density. Moreover, the spatial mean current density is almost surely independent of the concrete realisation given.

The electric current density describes the linear dependence of the spatial mean current density on the external electric field, for small strengths. Via linear response theory for the noninteracting model of an electron gas, an explicit expression for the current density is derived in terms of a so called Kubo formula. For the derivation the system needs to satisfy a localisation condition, which is specifically designed for non-interacting electron gases. In view of a linear response theory of interacting electron gases, candidates for a generalisation of this localisation criterion that also apply to interacting systems are introduced.

Statistical methods usually require that the analyzed data are correct and precise observations of the variables of interest. In practice, however, often only incomplete or uncertain information about the quantities of interest is available. The question studied in the present thesis is, how a regression analysis can reasonably be performed when the variables are only imprecisely observed.

At first, different approaches to analyzing imprecisely observed variables that were proposed in the Statistics literature are discussed. Then, a new likelihood-based methodology for regression analysis with imprecise data called Likelihood-based Imprecise Regression is introduced. The corresponding methodological framework is very broad and permits accounting for coarsening errors, in contrast to most alternative approaches to analyzing imprecise data. The methodology suggests considering as the result of a regression analysis the entire set of all regression functions that cannot be excluded in the light of the data, which can be interpreted as a confidence set. In the subsequent chapter, a very general regression method is derived from the likelihood-based methodology. This regression method does not impose restrictive assumptions about the form of the imprecise observations, about the underlying probability distribution, and about the shape of the relationship between the variables. Moreover, an exact algorithm is developed for the special case of simple linear regression with interval data and selected statistical properties of this regression method are studied. The proposed regression method turns out to be robust in terms of a high breakdown point and to provide very reliable insights in the sense of a set-valued result with a high coverage probability. In addition, an alternative approach proposed in the literature based on Support Vector Regression is studied in detail and generalized by embedding it into the framework of the formerly introduced likelihood-based methodology. In the end, the discussed regression methods are applied to two practical questions.