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

The global information space provided by the World Wide Web has changed dramatically

the way knowledge is shared all over the world. To make this unbelievable huge information

space accessible, search engines index the uploaded contents and provide efficient

algorithmic machinery for ranking the importance of documents with respect to an input

query. All major search engines such as Google, Yahoo or Bing are keyword-based, which

is indisputable a very powerful tool for accessing information needs centered around documents.

However, this unstructured, document-oriented paradigm of the World Wide Web has serious drawbacks, when searching for specific knowledge about real-world entities.

When asking for advanced facts about entities, today's search engines are not very good in providing accurate answers. Hand-built knowledge bases such as Wikipedia or its structured counterpart DBpedia are excellent sources that provide common facts. However, these knowledge bases are far from being complete and most of the knowledge lies still buried in unstructured documents.

Statistical machine learning methods have the great potential to help to bridge the gap between text and knowledge by (semi-)automatically transforming the unstructured representation of the today's World Wide Web to a more structured representation. This

thesis is devoted to reduce this gap with Probabilistic Graphical Models. Probabilistic

Graphical Models play a crucial role in modern pattern recognition as they merge two important fields of applied mathematics: Graph Theory and Probability Theory.

The first part of the thesis will present a novel system called Text2SemRel that is able to (semi-)automatically construct knowledge bases from textual document collections. The resulting knowledge base consists of facts centered around entities and their relations.

Essential part of the system is a novel algorithm for extracting relations between entity

mentions that is based on Conditional Random Fields, which are Undirected Probabilistic Graphical Models.

In the second part of the thesis, we will use the power of Directed Probabilistic Graphical Models to solve important knowledge discovery tasks in semantically annotated large document collections. In particular, we present extensions of the Latent Dirichlet Allocation framework that are able to learn in an unsupervised way the statistical semantic

dependencies between unstructured representations such as documents and their semantic annotations. Semantic annotations of documents might refer to concepts originating from a thesaurus or ontology but also to user-generated informal tags in social tagging

systems. These forms of annotations represent a first step towards the conversion to a more structured form of the World Wide Web.

In the last part of the thesis, we prove the large-scale applicability of the proposed fact extraction system Text2SemRel. In particular, we extract semantic relations between genes and diseases from a large biomedical textual repository. The resulting knowledge

base contains far more potential disease genes exceeding the number of disease genes that

are currently stored in curated databases. Thus, the proposed system is able to unlock

knowledge currently buried in the literature. The literature-derived human gene-disease

network is subject of further analysis with respect to existing curated state of the art

databases. We analyze the derived knowledge base quantitatively by comparing it with

several curated databases with regard to size of the databases and properties of known

disease genes among other things. Our experimental analysis shows that the facts extracted

from the literature are of high quality.

In recent years the digital media has influenced many areas of our life. The transition from analogue to digital has substantially changed our ways of dealing with media collections. Today‟s interfaces for managing digital media mainly offer fixed linear models corresponding to the underlying technical concepts (folders, events, albums, etc.), or the metaphors borrowed from the analogue counterparts (e.g., stacks, film rolls). However, people‟s mental interpretations of their media collections often go beyond the scope of linear scan. Besides explicit search with specific goals, current interfaces can not sufficiently support the explorative and often non-linear behavior. This dissertation presents an exploration of interface design to enhance the browsing experience with media collections. The main outcome of this thesis is a new model of Exploratory Browsing to guide the design of interfaces to support the full range of browsing activities, especially the Exploratory Browsing.

We define Exploratory Browsing as the behavior when the user is uncertain about her or his targets and needs to discover areas of interest (exploratory), in which she or he can explore in detail and possibly find some acceptable items (browsing). According to the browsing objectives, we group browsing activities into three categories: Search Browsing, General Purpose Browsing and Serendipitous Browsing. In the context of this thesis, Exploratory Browsing refers to the latter two browsing activities, which goes beyond explicit search with specific objectives.

We systematically explore the design space of interfaces to support the Exploratory Browsing experience. Applying the methodology of User-Centered Design, we develop eight prototypes, covering two main usage contexts of browsing with personal collections and in online communities.

The main studied media types are photographs and music.

The main contribution of this thesis lies in deepening the understanding of how people‟s exploratory behavior has an impact on the interface design. This thesis contributes to the field of interface design for media collections in several aspects. With the goal to inform the interface design to support the Exploratory Browsing experience with media collections, we present a model of Exploratory Browsing, covering the full range of exploratory activities around media collections. We investigate this model in different usage contexts and develop eight prototypes. The substantial implications gathered during the development and evaluation of these prototypes inform the further refinement of our model: We uncover the underlying transitional relations between browsing activities and discover several stimulators to encourage a fluid and effective activity transition. Based on this model, we propose a catalogue of general interface characteristics, and employ this catalogue as criteria to analyze the effectiveness of our prototypes. We also present several general suggestions for designing interfaces for media collections.

On classical Lie groups, which act by means of a unitary representation on finite dimensional Hilbert spaces H, we identify two classes of tensor field constructions.

First, as pull-back tensor fields of order two from modified Hermitian tensor fields, constructed on Hilbert spaces by means of the property of having the vertical

distributions of the C_0-principal bundle H_0 over the projective Hilbert space P(H) in the kernel. And second, directly constructed on the Lie group, as

left-invariant representation-dependent operator-valued tensor fields (LIROVTs) of arbitrary order being evaluated on a quantum state. Within the NP-hard problem

of deciding whether a given state in a n-level bi-partite quantum system is entangled or separable (Gurvits, 2003), we show that both tensor field constructions admit a geometric approach to this problem, which evades the traditional ambiguity on defining metrical structures on the convex set of mixed states. In particular by considering manifolds associated to orbits passing through a selected

state when acted upon by the local unitary group U(n)xU(n) of Schmidt coefficient decomposition inducing transformations, we find the following results: In the

case of pure states we show that Schmidt-equivalence classes which are Lagrangian submanifolds define maximal entangled states. This implies a stronger statement

as the one proposed by Bengtsson (2007). Moreover, Riemannian pull-back tensor fields split on orbits of separable states and provide a quantitative characterization

of entanglement which recover the entanglement measure proposed by Schlienz and Mahler (1995). In the case of mixed states we highlight a relation between LIROVTs of order two and a class of computable separability criteria based on the Bloch-representation (de Vicente, 2007).

The increasing availability of displays at lower costs has led to a proliferation of such in our everyday lives. Additionally, mobile devices are ready to hand and have been proposed as interaction devices for external screens. However, only their input mechanism was taken into account without considering three additional factors in environments hosting several displays: first, a connection needs to be established to the desired target display (modality). Second, screens in the environment may be re-arranged (flexibility). And third, displays may be out of the user’s reach (distance). In our research we aim to overcome the problems resulting from these characteristics. The overall goal is a new interaction model that allows for (1) a non-modal connection mechanism for impromptu use on various displays in the environment, (2) interaction on and across displays in highly flexible environments, and (3) interacting at variable distances. In this work we propose a new interaction model called through the display interaction which enables users to interact with remote content on their personal device in an absolute and direct fashion.

To gain a better understanding of the effects of the additional characteristics, we implemented two prototypes each of which investigates a different distance to the target display: LucidDisplay allows users to place their mobile device directly on top of a larger external screen. MobileVue on the other hand enables users to interact with an external screen at a distance. In each of these prototypes we analyzed their effects on the remaining two criteria – namely the modality of the connection mechanism as well as the flexibility of the environment.

With the findings gained in this initial phase we designed Shoot & Copy, a system that allows the detection of screens purely based on their visual content. Users aim their personal device’s camera at the target display which then appears in live video shown in the viewfinder. To select an item, users take a picture which is analyzed to determine the targeted region. We further extended this approach to multiple displays by using a centralized component serving as gateway to the display environment. In Tap & Drop we refined this prototype to support real-time feedback. Instead of taking pictures, users can now aim their mobile device at the display resulting and start interacting immediately. In doing so, we broke the rigid sequential interaction of content selection and content manipulation. Both prototypes allow for (1) connections in a non-modal way (i.e., aim at the display and start interacting with it) from the user’s point of view and (2) fully flexible environments (i.e., the mobile device tracks itself with respect to displays in the environment). However, the wide-angle lenses and thus greater field of views of current mobile devices still do not allow for variable distances. In Touch Projector, we overcome this limitation by introducing zooming in combination with temporarily freezing the video image.

Based on our extensions to taxonomy of mobile device interaction on external displays, we created a refined model of interacting through the display for mobile use. It enables users to interact impromptu without explicitly establishing a connection to the target display (non-modal). As the mobile device tracks itself with respect to displays in the environment, the model further allows for full flexibility of the environment (i.e., displays can be re-arranged without affecting on the interaction). And above all, users can interact with external displays regardless of their actual size at variable distances without any loss of accuracy.

Most temporal logics which have been introduced and studied in the past decades can be embedded into the modal mu-calculus. This is the case for e.g. PDL, CTL, CTL*, ECTL, LTL, etc. and entails that these logics cannot express non-regular program properties. In recent years, some novel approaches towards an increase in expressive power have been made: Fixpoint Logic with Chop enriches the mu-calculus with a sequential composition operator and thereby allows to characterise context-free processes. The Modal Iteration Calculus uses inflationary fixpoints to exceed the expressive power of the mu-calculus. Higher-Order Fixpoint Logic (HFL) incorporates a simply typed lambda-calculus into a setting with extremal fixpoint operators and even exceeds the expressive power of Fixpoint Logic with Chop. But also PDL has been equipped with context-free programs instead of regular ones.

In terms of expressivity there is a natural demand for richer frameworks since program property specifications are simply not limited to the regular sphere. Expressivity however usually comes at the price of an increased computational complexity of logic-related decision problems. For instance are the satisfiability problems for the above mentioned logics undecidable. We investigate in this work the model checking problem of three different logics which are capable of expressing non-regular program properties and aim at identifying fragments with feasible model checking complexity.

Firstly, we develop a generic method for determining the complexity of model checking PDL over arbitrary classes of programs and show that the border to undecidability runs between PDL over indexed languages and PDL over context-sensitive languages. It is however still in PTIME for PDL over linear indexed languages and in EXPTIME for PDL over indexed languages. We present concrete algorithms which allow implementations of model checkers for these two fragments.

We then introduce an extension of CTL in which the UNTIL- and RELEASE- operators are adorned with formal languages. These are interpreted over labeled paths and restrict the moments on such a path at which the operators are satisfied. The UNTIL-operator is for instance satisfied if some path prefix forms a word in the language it is adorned with (besides the usual requirement that until that moment some property has to hold and at that very moment some other property must hold). Again, we determine the computational complexities of the model checking problems for varying classes of allowed languages in either operator. It turns out that either enabling context-sensitive languages in the UNTIL or context-free languages in the RELEASE- operator renders the model checking problem undecidable while it is EXPTIME-complete for indexed languages in the UNTIL and visibly pushdown languages in the RELEASE- operator. PTIME-completeness is a result of allowing linear indexed languages in the UNTIL and deterministic context-free languages in the RELEASE. We do also give concrete model checking algorithms for several interesting fragments of these logics.

Finally, we turn our attention to the model checking problem of HFL which we have already studied in previous works. On finite state models it is k-EXPTIME-complete for HFL(k), the fragment of HFL obtained by restricting functions in the lambda-calculus to order k. Novel in this work is however the generalisation (from the first-order case to the case for functions of arbitrary order) of an idea to improve the best and average case behaviour of a model checking algorithm by using partial functions during the fixpoint iteration guided by the neededness of arguments. This is possible, because the semantics of a closed HFL formula is not a total function but the value of a function at some argument. Again, we give a concrete algorithm for such an improved model checker and argue that despite the very high model checking complexity this improvement is very useful in practice and gives

In the style of the tree property, we give combinatorial principles that capture the concepts of the so-called subtle and ineffable cardinals in such a way that they are also applicable to small cardinals. Building upon these principles we then develop a further one that even achieves this for supercompactness.

We show the consistency of these principles starting from the corresponding large cardinals. Furthermore we show the equiconsistency for subtle and ineffable. For supercompactness, utilizing the failure of square we prove that the best currently known lower bounds for consistency strength in general can be applied.

The main result of the thesis is the theorem that the Proper Forcing Axiom implies the principle

corresponding to supercompactness.

With a growing number of computer devices around us, and the increasing time we spend for interacting with such devices, we are strongly interested in finding new interaction methods which ease the use of computers or increase interaction efficiency. Eye tracking seems to be a promising technology to achieve this goal.

This thesis researches interaction methods based on eye-tracking technology. After a discussion of the limitations of the eyes regarding accuracy and speed, including a general discussion on Fitts’ law, the thesis follows three different approaches on how to utilize eye tracking for computer input. The first approach researches eye gaze as pointing device in combination with a touch sensor for multimodal input and presents a method using a touch sensitive mouse. The second approach examines people’s ability to perform gestures with the eyes for computer input and the separation of gaze gestures from natural eye movements. The third approach deals with the information inherent in the movement of the eyes and its application to assist the user. The thesis presents a usability tool for recording of interaction and gaze activity. It also describes algorithms for reading detection.

All approaches present results based on user studies conducted with prototypes developed for the purpose.

Society is currently inundated with more information than ever, making efficient management

a necessity. Alas, most of current information management suffers from several

levels of disconnectedness: Applications partition data into segregated islands,

small notes don’t fit into traditional application categories, navigating the data is different

for each kind of data; data is either available at a certain computer or only online,

but rarely both. Connected information management (CoIM) is an approach to information

management that avoids these ways of disconnectedness. The core idea of

CoIM is to keep all information in a central repository, with generic means for organization

such as tagging. The heterogeneity of data is taken into account by offering

specialized editors.

The central repository eliminates the islands of application-specific data and is formally

grounded by a CoIM model. The foundation for structured data is an RDF repository.

The RDF editing meta-model (REMM) enables form-based editing of this data,

similar to database applications such as MS access. Further kinds of data are supported

by extending RDF, as follows. Wiki text is stored as RDF and can both contain

structured text and be combined with structured data. Files are also supported by the

CoIM model and are kept externally. Notes can be quickly captured and annotated with

meta-data. Generic means for organization and navigation apply to all kinds of data.

Ubiquitous availability of data is ensured via two CoIM implementations, the web application

HYENA/Web and the desktop application HYENA/Eclipse. All data can be

synchronized between these applications. The applications were used to validate the

CoIM ideas.