Contextualized and personalized location-based services

Advances in the technologies of smart mobile devices and tiny sensors together with the increase in the number of web resources open up a plethora of new mobile information services where people can acquire and disseminate information at any place and any time. Location-based services (LBS) are characterized by providing users with useful and local information, i.e. information that belongs to a particular domain of interest to the user and can be of use while the user remains in a particular area. In addition, LBS need to take into account the interactions and dependencies between services, user and context for the information filtering and delivery in order to fulfill the needs and constraints of mobile users. We argue that consequently it brings up a series of technical challenges in terms of data semantics and infrastructure, context-awareness and personalization, as well as query formulation and answering etc. They can not be simply extended from existing traditional data management strategies. Instead, they need a new solution. Firstly, we propose a semantic LBS infrastructure on the basis of the modularized ontologies approach. We elaborate a core ontology which is mainly composed of three modules describing the services, users and contexts. The core ontology aims at presenting an abstract view (a model) of all information in LBS. In contrast, data describing the instances (of services user and actual contextual data) are stored in three independent data stores, called the service profiles, user profiles and context profiles. These data are semantically aligned with the concepts in the core ontology through a set of mappings. This approach enables the distributed data sources to be maintained in a autonomous manner, which is well adapted to the high dynamics and mobility of the data sources. Secondly, we separately address the function, features, and our modelling approach of the three major players, i.e. service, context and user in LBS. Then, we define a set of constructs to represent their interactions and inter-dependencies and illustrate how these semantic constructs can contribute to personalized and contextualized query processing. Service classes are organized in a taxonomy, which distinguishes the services by their business functions. This concept hierarchy helps to analyze and reformulate the users' queries. We introduce three new kinds of relationships in the service module to enhance the semantics of interactions and dependencies between services. We identify five key components of contexts in LBS and regard them as a semantic contextual basis for LBS. Component contexts are related together by specific composition relationships that can describe spatio-temporal constraints. A user profile contains personal information about a given user and possibly a set of self-defined rules, which offer hints on what the user likes or dislikes, and what could attract him or her. In the core ontology clustering users with common features can help the cooperative query answering. Each of the three modules of the core ontology is an ontology in itself. They are inter-related by relationships that link concepts belonging to two different modules. The LBS fully benefits from the modularized structure of the core ontology. It allows restricting the search space, as well as facilitating the maintenance of each module. Finally, we studied the query reformulation and processing issues in LBS. How to make the query interface tangible and provide rapid and relevant answers are typical concerns in all information services. Our query format not only fully obeys the "simple, tangible and effective" golden-rules of user-interface design, but also satisfies the needs of domain-independent interface and emphasizes the importance of spatio-temporal constraints in LBS. With pre-defined spatio-temporal operators, users can easily specify in their queries the spatio-temporal availability they need for the services they are looking for. This allows eliminating most of irrelevant answers that are usually generated by keyword-based approaches. Constraints in the various dimensions (what, when, where and what-else) can be expressed by a conjunctive query, and then be smoothly translated to RDF-patterns. We illustrate our query answering strategy by using the SPARQL syntax, and explain how the relaxation can be done with rules specified in the query relaxation profile.

Predictive approach for schema evolution

Hassina Bounif

In today's companies and organizations, databases are omnipresent. They are the means to represent and store information. Therefore, they must evolve whenever the information architecture (semantic and structure) changes. Databases are subject to evolution for several reasons that include the changes to the real-world or the emergence of new database user requirements. We may also consider non representational and non-functional aspects such as the technology and performance requirements. Those can also compel the database designer or administrator to change the database in order to be more optimal and adapted to those requirements. This thesis proposes to address the schema evolution problem by anticipating the potential changes for the evolution of the schema. The approach adopts the a priori perspective i.e. to plan in advance for a possible solution that makes a schema evolve over time. Such a solution works with both a set of assumptions and techniques. The elaborated approach is based on different components: • First, we propose to develop a schema repository which contains a wide number of heterogeneous schemas and their historical versions. This repository serves in a series of operations that are important for the study of the schemas such as selecting the pertinent schemas, building the change matrices and performing the data-mining process. • Second, we propose to develop a requirements ontology, meaning to say a domain ontology that describes the current concepts of a database as well as the concepts that represent the potential future requirements that could be part of the evolution. The method of construction of this ontology includes several phases such as the preparation of the data for this ontology, the establishment of the data-dictionary besides change perspectives that store the concepts that are associated to other concepts by relationships resulting from the application of the data-mining process, the evaluation of the domain ontology using a graph structure and finally the construction of the ontology using a set of procedures. • Third, we propose to develop a predicted schema which is a database schema that contains two types of metadata. The metadata, that represents current entities of the database and the metadata that represents potential future entities. The predicted schema has two methods of representation: the multi-representation strategy and the predicted design repository schemas strategy. The schemas with the multi-representation strategy are particular versions of schemas whereas the schemas with the predicted design repository schemas are particular repositories of schemas. • Finally, we propose a case study and an analysis of the approach. The case study to better understand how this approach works and the analysis to show its feasibility, the positive as well as negative aspects.

EPFL2009

Cognitive language engineering towards robust human-computer interaction

Vincenzo Pallotta

Intelligent information processing seems to be one of the most challenging task among those involved in human-computer interaction. A central issue is how to model the various types of interaction among artificial and natural entities at different levels of abstraction. On the one hand, models of interaction are required to better understand the communication phenomena. On the other, suitable languages and paradigms should provide powerful frameworks for developing computer-based applications. In this dissertation I focus on different aspects of the second problem, trying to develop a methodology for the design of interactive natural language applications (e.g. from question-answering to mixed-initiative dialogue). One of the main aspects I am concerned with in this work is the problem of their robustness. Several methods have been proposed for achieving robustness in natural language understanding, but these methods are sometimes hard to scale up or re-use in different applications. Moreover, they often concentrate on a single linguistic level of the processing rather than offering a global solution. I will set up a Language Engineering environment whose goal is to combine software engineering and cognitive aspects (e.g. aspects related to representation of a mental model of the speaker). Given its complexity, it is apparent that the problem can be solved only partially. I want to stress here that the main contribution of my work is a holistic perspective on the problem of natural language understanding. Rather than focusing on a particular aspect of natural language processing, I tried to benefit from the big amount of work that has been already done in Computational Linguistics and Computer Science merging different ideas and techniques. In the first part of the dissertation I explore the universe of Language Engineering in order to clarify how my contribution can be situated. After a survey on the state of the art on robust methods in analysis of natural language data, I focus on the role that Computational Logic plays in relating the syntactic and semantic analysis of natural language to its practical understanding within specific applications. Robustness is considered from two complementary perspectives, borrowing the terminology from modern software engineering: robustness "in the small" and robustness "in the large". The first perspective is discussed while presenting an application for the Interaction through Speech with Information Systems, where robust semantic parsing is used to extract queries from spoken natural language utterances.The second perspective is examplified by the re-engineering of an existing text analysis system using a new Language Engineering methodology: Agent-Oriented Language Engineering. In the second part of the thesis I discuss how cognitive aspects can be integrated into a Language Engineering environment leading to the notion of Cognitive Language Enginering. I tackle the difficult problem of robust dialogue management from both a cognitive and computational perspective. I propose two frameworks for the semantic representation and assimilation of information into the dialogue information state. The first framework allows us to represent and reason about the dynamic aspects of objects and events. The second framework is centered on the notion of mental space and it is used to build representations of the cognitive processing of information during communication.

EPFL2002

Graph Signal Processing

Ntorina Thanou

Over the past few decades we have been experiencing an explosion of information generated by large networks of sensors and other data sources. Much of this data is intrinsically structured, such as traffic evolution in a transportation network, temperature values in different geographical locations, information diffusion in social networks, functional activities in the brain, or 3D meshes in computer graphics. The representation, analysis, and compression of such data is a challenging task and requires the development of new tools that can identify and properly exploit the data structure. In this thesis, we formulate the processing and analysis of structured data using the emerging framework of graph signal processing. Graphs are generic data representation forms, suitable for modeling the geometric structure of signals that live on topologically complicated domains. The vertices of the graph represent the discrete data domain, and the edge weights capture the pairwise relationships between the vertices. A graph signal is then defined as a function that assigns a real value to each vertex. Graph signal processing is a useful framework for handling efficiently such data as it takes into consideration both the signal and the graph structure. In this work, we develop new methods and study several important problems related to the representation and structure-aware processing of graph signals in both centralized and distributed settings. We focus in particular in the theory of sparse graph signal representation and its applications and we bring some insights towards better understanding the interplay between graphs and signals on graphs. First, we study a novel yet natural application of the graph signal processing framework for the representation of 3D point cloud sequences. We exploit graph-based transform signal representations for addressing the challenging problem of compression of data that is characterized by dynamic 3D positions and color attributes. Next, we depart from graph-based transform signal representations to design new overcomplete representations, or dictionaries, which are adapted to specific classes of graph signals. In particular, we address the problem of sparse representation of graph signals residing on weighted graphs by learning graph structured dictionaries that incorporate the intrinsic geometric structure of the irregular data domain and are adapted to the characteristics of the signals. Then, we move to the efficient processing of graph signals in distributed scenarios, such as sensor or camera networks, which brings important constraints in terms of communication and computation in realistic settings. In particular, we study the effect of quantization in the distributed processing of graph signals that are represented by graph spectral dictionaries and we show that the impact of the quantization depends on the graph geometry and on the structure of the spectral dictionaries. Finally, we focus on a widely used graph process, the problem of distributed average consensus in a sensor network where sensors exchange quantized information with their neighbors. We propose a novel quantization scheme that depends on the graph topology and exploits the increasing correlation between the values exchanged by the sensors throughout the iterations of the consensus algorithm.

EPFL2016