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

The theory of Bishop spaces (TBS) is so far the least developed approach to constructive topology with points. Bishop introduced function spaces, here called Bishop spaces, in 1967, without really exploring them, and in 2012 Bridges revived the subject. In this Thesis we develop TBS.

Instead of having a common space-structure on a set X and R, where R denotes the set of

constructive reals, that determines a posteriori which functions of type X -> R are continuous with respect to it, within TBS we start from a given class of "continuous" functions of type X -> R that determines a posteriori a space-structure on X. A Bishop space is a pair (X, F),

where X is an inhabited set and F, a Bishop topology, or simply a topology, is a subset of all functions of type X -> R that includes the constant maps and it is closed under addition, uniform limits and composition with the Bishop continuous functions of type R -> R.

The main motivation behind the introduction of Bishop spaces is that function-based concepts are more suitable to constructive study than set-based ones. Although a Bishop topology of functions F on X is a set of functions,

the set-theoretic character of TBS is not that central as it seems. The reason for this is Bishop's inductive concept of the least topology generated by a given subbase. The definitional clauses of a Bishop space, seen as inductive rules, induce the corresponding induction principle. Hence, starting with a

constructively acceptable subbase the generated topology is a constructively graspable set of functions exactly because of the corresponding principle. The function-theoretic character of TBS is also evident in the characterization of morphisms between Bishop spaces.

The development of constructive point-function topology in this Thesis takes two directions. The first is a purely topological one. We introduce and study, among other notions, the quotient,

the pointwise exponential, the dual, the Hausdorff, the completely regular, the 2-compact,

the pair-compact and the 2-connected Bishop spaces. We prove, among other results, a Stone-Cech theorem, the Embedding lemma, a generalized version of the Tychonoff embedding theorem for completely regular Bishop spaces, the Gelfand-Kolmogoroff theorem for fixed and completely regular Bishop spaces, a Stone-Weierstrass theorem for pseudo-compact Bishop spaces and a Stone-Weierstrass theorem for pair-compact Bishop spaces. Of special importance is the notion of 2-compactness, a constructive function-theoretic notion of compactness for which we show that it generalizes the notion of a compact metric space. In the last chapter we initiate the basic homotopy theory of Bishop spaces.

The other direction in the development of TBS is related to the analogy between a Bishop topology F, which is a ring and a lattice, and the ring of real-valued continuous functions C(X) on a topological space X. This analogy permits a direct "communication" between TBS and the theory of rings of continuous functions, although due to the classical set-theoretic character of C(X) this does not mean a direct translation of the latter to the former. We study the zero sets of a Bishop space and we prove the Urysohn lemma for them. We also develop the basic theory of embeddings of Bishop spaces in parallel to the basic classical theory of embeddings of rings of continuous functions and we show constructively

the Urysohn extension theorem for Bishop spaces.

The constructive development of topology in this Thesis is within Bishop's informal system of constructive mathematics BISH, inductive definitions with rules of countably many premises included.

Time series modeling and forecasting are of vital importance in many real world applications. Recently nonlinear time series models have gained much attention, due to the fact that linear time series models faced various limitations in many empirical applications. In this thesis, a large variety of standard and extended linear and nonlinear time series models is considered in order to compare their out-of-sample forecasting performance. We examined the out-of-sample forecast accuracy of linear Autoregressive (AR), Heterogeneous Autoregressive (HAR), Autoregressive Conditional Duration (ACD), Threshold Autoregressive (TAR), Self-Exciting Threshold Autoregressive (SETAR), Logistic Smooth Transition Autoregressive (LSTAR), Additive Autoregressive (AAR) and Artificial Neural Network (ANN) models and also the extended Heterogeneous Threshold Autoregressive (HTAR) or Heterogeneous Self-Exciting Threshold Autoregressive (HSETAR) model for financial, economic and seismic time series. We also extended the previous studies by using Vector Autoregressive (VAR) and Threshold Vector Autoregressive (TVAR) models and compared their forecasting accuracy with linear models for the above mentioned time series.

Unlike previous studies that typically consider the threshold models specifications by using internal threshold variable, we specified the threshold models with external transition variables and compared their out-of-sample forecasting performance with the linear benchmark HAR and AR models by using the financial, economic and seismic time series. According to our knowledge, this is the first study of its kind that extends the usage of linear and nonlinear time series models in the field of seismology by utilizing the seismic data from the Hindu Kush region of Pakistan.

The question addressed in this study is whether nonlinear models produce 1 through 4 step-ahead forecasts that improve upon linear models. The answer is that linear model mostly yields more accurate forecasts than nonlinear ones for financial, economic and seismic time series. Furthermore, while modeling and forecasting the financial (DJIA, FTSE100, DAX and Nikkei), economic (the USA GDP growth rate) and seismic (earthquake magnitudes, consecutive elapsed times and consecutive distances between earthquakes occurred in the Hindu Kush region of Pakistan) time series, it appears that using various external threshold variables in threshold models improve their out-of-sample forecasting performance. The results of this study suggest that constructing the nonlinear models with external threshold variables has a positive effect on their forecasting accuracy. Similarly for seismic time series, in some cases, TVAR and VAR models provide improved forecasts over benchmark linear AR model. The findings of this study could somehow bridge the analytical gap between statistics and seismology through the potential use of linear and nonlinear time series models.

Secondly, we extended the linear Heterogeneous Autoregressive (HAR) model in a nonlinear framework, namely Heterogeneous Threshold Autoregressive (HTAR) model, to model and forecast a time series that contains simultaneously nonlinear and long-range dependence phenomena. The model has successfully been applied to financial data (DJIA, FTSE100, DAX and Nikkei) and the results show that HTAR model has improved 1-step-ahead forecasting performance than linear HAR model by utilizing the financial data of DJIA. For DJIA, the combination of the forecasts from HTAR and linear HAR models are improved over those obtained from the benchmark HAR model.

Furthermore, we conducted a simulated study to assess the performance of HAR and HSETAR models in the presence of spurious long-memory type phenomena contains by a time series. The main purpose of this study is to answer the question, for a time series, whether the HAR and HSETAR models have an ability to detect spurious long-memory type phenomena. The simulation results show tha

Real world data from various application domains can be modeled as a graph, e.g. social networks and biomedical networks like protein interaction networks or co-activation networks of brain regions. A graph is a powerful concept to model arbitrary (structural) relationships among objects. In recent years, the prevalence of social networks has made graph mining an important center of attention in the data mining field. There are many important tasks in graph mining, such as graph clustering, outlier detection, and link prediction. Many algorithms have been proposed in the literature to solve these tasks. However, normally these issues are solved separately, although they are closely related. Detecting and exploiting the relationship among them is a new challenge in graph mining. Moreover, with data explosion, more information has already been integrated into graph structure. For example, bipartite graphs contain two types of node and graphs with node attributes offer additional non-structural information. Therefore, more challenges arise from the increasing graph complexity. This thesis aims to solve these challenges in order to gain new knowledge from graph data.

An important paradigm of data mining used in this thesis is the principle of Minimum Description Length (MDL). It follows the assumption: the more knowledge we have learned from the data, the better we are able to compress the data. The MDL principle balances the complexity of the selected model and the goodness of fit between model and data. Thus, it naturally avoids over-fitting.

This thesis proposes several algorithms based on the MDL principle to acquire knowledge from various types of graphs: Info-spot (Automatically Spotting Information-rich Nodes in Graphs) proposes a parameter-free and efficient algorithm for the fully automatic detection of interesting nodes which is a novel outlier notion in graph. Then in contrast to traditional graph mining approaches that focus on discovering dense subgraphs, a novel graph mining technique CXprime (Compression-based eXploiting Primitives) is proposed. It models the transitivity and the hubness of a graph using structure primitives (all possible three-node substructures). Under the coding scheme of CXprime, clusters with structural information can be discovered, dominating substructures of a graph can be distinguished, and a new link prediction score based on substructures is proposed. The next algorithm SCMiner (Summarization-Compression Miner) integrates tasks such as graph summarization, graph clustering, link prediction, and the discovery of the hidden structure of a bipartite graph on the basis of data compression. Finally, a method for non-redundant graph clustering called IROC (Information-theoretic non-Redundant Overlapping Clustering) is proposed to smartly combine structural information with non-structural information based on MDL. IROC is able to detect overlapping communities within subspaces of the attributes.

To sum up, algorithms to unify different learning tasks for various types of graphs are proposed. Additionally, these algorithms are based on the MDL principle, which facilitates the unification of different graph learning tasks, the integration of different graph types, and the automatic selection of input parameters that are otherwise difficult to estimate.

Partizipative Sensornetze (PSNs) stellen eine neue Art von Sensornetzen dar, die auf Basis von freiwillig zur Verfügung gestellten Mobiltelefonen etabliert werden. Sie ermöglichen eine großflächige Erfassung von Messdaten im direkten Umfeld von Menschen und können für zahlreiche Anwendungsszenarien verwendet werden. Neben ihren Vorzügen bringen PSNs aber auch Schwierigkeiten mit sich. Zwei zentrale Herausforderungen sind die ressourcenschonende Datenerfassung und der Schutz der Privatsphäre – beide resultieren aus der Instrumentalisierung privater Mobiltelefone zur Datenerfassung. Da der primäre Verwendungszweck der Geräte nicht die Aufzeichnung von Messdaten ist, darf diese deren Ressourcen nicht merklich belasten. Außerdem muss sichergestellt werden, dass durch die Erfassung von Messdaten die Privatsphäre der teilnehmenden Nutzer nicht verletzt wird.

Der erste Teil der Arbeit beschäftigt sich mit dem Aspekt der ressourcenschonenden Datenerfassung. Zunächst werden PSNs betrachtet, bei denen punktuell Messungen durchgeführt werden. Bei diesen Netzen müssen die teilnehmenden Geräte über die durchzuführenden Messungen unterrichtet werden. Damit hierbei die Ressourcen der Endgeräte nicht unnötig belastet werden, wird ein Konzept vorgestellt, das einerseits eine robuste Verteilung der Messaufgaben sicherstellt, gleichzeitig jedoch versucht, die Energieressourcen der Mobiltelefone zu schonen. Bei PSNs mit großflächiger und kontinuierlicher Datenerfassung spielt die Verteilung der Messaufgaben keine so entscheidende Rolle. Hier muss vielmehr sichergestellt werden, dass die Energie- und die Übertragungskosten auf Seiten der Nutzer möglichst gering bleiben. Aus diesem Grund wird ein Ansatz zur lokalen Gruppierung von Messknoten beschrieben, der durch eine Aufteilung der anfallenden Aufgaben und eine intelligente Auswahl der Knoten zu einer ressourcenschonenden und weniger redundanten Datenerfassung führt.

Der zweite Teil der Arbeit befasst sich mit dem Schutz der Privatsphäre der Teilnehmer und beinhaltet zwei Themenblöcke. Zum einen wird ein Ansatz zur automatisierten Erzeugung von Privatsphäre-Zonen vorgestellt, der ohne das Eingreifen der Nutzer die Zonen an das jeweilige Umfeld anpasst. Diese Zonen werden um die vom Nutzer häufig besuchten Orte erstellt und verhindern so mögliche, auf der Identifikation dieser Orte basierende Deanonymisierungsangriffe. Zum anderen wird ein Kalibrierungssystem für PSNs beschrieben, dessen Fokus sowohl auf der Verbesserung der Datenqualität als auch auf der Wahrung der Privatsphäre der Nutzer liegt. Hierfür ermöglicht dieses eine rückwirkende Anpassung bereits übertragener Daten, verhindert aber gleichzeitig durch eine Modifikation der Kalibrierungsparameter und der Upload-Zeitpunkte eine direkte Zuordnung zu einem Nutzer.

Compartment models are a frequently used tool for imaging data gained with medical and biological imaging techniques. The solutions of the differential equations derived from a compartment model provide nonlinear parametric functions, based on which the behavior of a concentration of interest over time can be described.

Often, the number of compartments in a compartment model is unknown. As the model complexity itself, which is, the number of compartments, is certainly an important information, it is desirable to estimate it from the observed data. Additionally, the unknown parameters have to be estimated. Therefore, methods dealing with both the parameter estimation and model selection in compartment models are needed. The methods proposed in this thesis are motivated by two applications from the field of medical and biological imaging.

In the first application, the quantitative analysis of Fluorescence recovery after photobleaching (FRAP) data, compartment models are used in order to gain insight into the binding behavior of molecules in living cells. As a first approach, we developed a Bayesian nonlinear mixed-effects model for the analysis of a series of FRAP images. Mixed-effect priors are defined on the parameters of the nonlinear model, which is a novel approach. With the proposed model, we get parameter estimates and additionally gain information about the variability between nuclei, which has not been studied so far. The proposed method was evaluated on half-nucleus FRAP data, also in comparison with different kinds of fixed-effects models. As a second approach, a pixelwise analysis of FRAP data is proposed, where information from the neighboring pixels is included into the nonlinear model for each pixel. This is innovative as the existing models are suitable for the analysis of FRAP data for some regions of interest only.

For the second application, the quantitative analysis of dynamic contrast-enhanced magnetic resonance imaging (DCE-MRI) of the breast, we use a compartment model which describes the exchange of blood between different, well-mixed compartments. In the analysis of such data, the number of compartments allows conclusions about the heterogeneity of cancerous tissue. Therefore, an estimation and model selection approach based on boosting, with which the number of compartments and the unknown parameters can be estimated at the voxel level, is proposed. In contrast to boosting for additive regression, where smoothing approaches are used, boosting in nonlinear parametric regression as described in this thesis is a novel approach. In an extension of this approach, the spatial structure of an image is taken into account by penalizing the differences in the parameter estimates of neighboring voxels. The evaluation of the method was done in simulation studies, as well as in the application to data from a breast cancer study.

The majority of the program code used in the three approaches was newly developed in the programming languages R and C. Based on that code, two R packages were built.

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

Global tests are in demand whenever it is of interest to draw inferential conclusions about sets of variables as a whole. The present thesis attempts to develop such tests for the case of multivariate ordinal data in possibly high-dimensional set-ups, and has primarily been motivated by research questions that arise from data collected by means of the 'International Classification of Functioning, Disability and Health'.

The thesis essentially comprises two parts. In the first part two tests are discussed, each of which addresses one specific problem in the classical two-group scenario. Since both are permutation tests, their validity relies on the condition that, under the null hypothesis, the joint distribution of the variables in the set to be tested is the same in both groups. Extensive simulation studies on the basis of the tests proposed suggest, however, that violations of this condition, from the purely practical viewpoint, do not automatically lead to invalid tests. Rather, two-sample permutation tests' failure appears to depend on numerous parameters, such as the proportion between group sizes, the number of variables in the set of interest and, importantly, the test statistic used. In the second part two further tests are developed which both can be used to test for association, if desired after adjustment for certain covariates, between a set of ordinally scaled covariates and an outcome variable within the range of generalized linear models. The first test rests upon explicit assumptions on the distances between the covariates' categories, and is shown to be a proper generalization of the traditional Cochran-Armitage test to higher dimensions, covariate-adjusted scenarios and generalized linear model-specific outcomes. The second test in turn parametrizes these distances and thus keeps them flexible. Based on the tests' power properties, practical recommendations are provided on when to favour one or the other, and connections with the permutation tests from the first part of the thesis are pointed out. For illustration of the methods developed, data from two studies based on the 'International Classification of Functioning, Disability and Health' are analyzed. The results promise vast potential of the proposed tests in this data context and beyond.

In 1992, Englert [Phys. Rev. A, 45;127--134] found a momentum energy functional for atoms and discussed the relation to the Thomas-Fermi functional (Lenz [Z. Phys., 77;713--721]). We place this model in a mathematical setting. Our results include a proof of existence and uniqueness of a minimizing momentum density for this momentum energy functional. Further, we investigate some properties of this minimizer, among them the connection with Euler's equation.

We relate the minimizers of the Thomas-Fermi functional and the momentum energy functional found by Englert by explicit transforms. It turns out that in this way results well-known in the Thomas-Fermi model can be transferred directly to the model under consideration. In fact, we gain equivalence of the two functionals upon minimization.

Finally, we consider momentum dependent perturbations. In particular, we show that the atomic momentum density converges to the minimizer of the momentum energy functional as the total nuclear charge becomes large in a certain sense.

This thesis is based on joint work with Prof. Dr. Heinz Siedentop and the main contents will also appear in a joint article.