Context Prediction

Context prediction teaser A context-aware application might be aware of its present, past or future context. Most work is carried out taking present or past context into consideration. By extending this concept to also consider future contexts, pro-active application behaviour becomes possible. Applications then might be aware of probable future situations and then anticipate appropriate actions to best meet such situation.
This is commonly referred to as context prediction or pro-active context computing. In this project we investigate issues related to the inference of future context and to the utilisation of past and present contexts in this setting. We discuss the task of pro-active context computing and identify chances and challenges that derive from it.

A context prediction capable application can, for instance, foresee interdependencies that are hard to keep track of for a user due to their high complexity. Consider, for example, a device that automatically informs the person you are about to meet that you will be delayed by a traffic jam or due to a delayed train even before you are actually late. Furthermore, in mobile scenarios, prediction of resource consumption of mobile users might contribute to the improvement of the overall network capacity. Also, if the availability of an individual in her office is predicted for potential visitors, these could more efficiently schedule their appointments with the person in question.

Challenges

Challenges for context prediction start with matters as essential as needing a formal definition of the context prediction task. Several authors who have approached context prediction provide informal descriptions of the problem their algorithms are solving, or provide an abstract idea of the desired output of the prediction process. However, no formal description of the context prediction task that contains a description of the input and output data, as well as the prediction aim of the prediction process, had been provided so far.

High-level vs. Low-level Another challenge is posed by the prediction architecture. Few approaches to this question have yet been published. However, these are too restricted, focusing on specific classes of applications, to be generally applicable for context prediction tasks. In particular, the application to contexts of arbitrary context abstraction levels is not considered by these architectures.

Furthermore, for context prediction algorithms, a thorough overview and comparison has not been provided until now. Additionally, the application domains these algorithms are applied to are few. A comprehensive discussion on these context prediction algorithms is still lacking.

Requirements for context prediction algorithms have also not yet been stated comprehensively. Requirements that are commonly referred to are high prediction accuracy as well as low processing cost along with low memory consumption. However, also other properties might prove useful for context prediction approaches. Candidates are, for example, a high adaptability to changing environments, as well as applicability to contexts of arbitrary context data type. Various algorithms have to be compared in identical application domains and for varying configuration parameters. Interesting questions raised by this challenge are the relation between the length of the prediction horizon and the prediction accuracy, as well as on the influence of the memory consumption and runtime related to the accuracy.

Context prediction example Probably the most serious challenge for context prediction tasks is related to the prediction accuracy. The usefulness of context prediction approaches is directly connected to the quality of the prediction in terms of accuracy. Although accuracies for distinct algorithms with unique configurations that are applied to typical application domains are known, a more general discussion is missing.

Further aspects that are independent of the prediction algorithm and that impact the prediction accuracy are not yet considered. Likely influences on the prediction accuracy originate, for example, from the number and type of sensors utilised for prediction tasks as well as from the context abstraction level.

Context prediction performance

Contributions


Results

Analytic consideration

Context prediction steps We study context prediction schemes for their prediction accuracy and provide guidelines to application designers as to which prediction scheme to utilise in which situation. We considered the impact of the order of context processing operations on the accuracy of the processing result, and the application of context prediction at various context abstraction levels. This was first carried out in an analytical fashion and the results were then verified using simulation and experiments.
The impact of specific input parameters on the context prediction accuracy in terms of high-level (hl)- and low-level (ll)-context prediction schemes was also investigated. Specifically, these parameters are the length of the context history, the dimension of the observed ll and generated hl-context sequences as well as the number of distinct values for hl- and ll-contexts. It was shown that these parameters have a different impact on the prediction accuracy depending on the order in which the acquisition, interpretation and prediction context processing operations are applied.
As a major contribution of our study we derive probabilistic formulae that describe the overall error probability for a specific set of context processing operations applied in a specific order. We also indicated that for highly-dimensional input time series, prediction accuracy can be improved by applying context prediction after the context interpretation process, e.g. on higher-level context data. The opposite was observed for the length of the context history, where the prediction accuracy increases when prediction is applied before context interpretation. This indicates that for relatively long context histories it is advantageous to use lower-level prediction as apposed to higher-level prediction.
A further result attained in the theoretical analysis and later validated in the experiments is that the nature of the input data, the quality of the output and the construction of a flow of processing operations to achieve prediction are correlated. In particular, we expect greater accuracy of context prediction when either the input data for context prediction, which may be the output from other context processing operations, has a high accuracy, or, when context prediction is applied before any further context processing operations are carried out.

Architecture

Context prediction architecture For context prediction, standardised architectures might foster a wide application in various application domains. However, only few approaches to context prediction architectures have been considered yet. These proposals are static in regard to the context abstraction level. We develop a novel architecture for context prediction approaches that is applicable to arbitrary context abstraction levels. This architecture also allows distribution of components to various intercommunicating devices in a mobile ubiquitous computing environment.

We have discussed requirements for an architecture for context prediction on low-level contexts in UbiComp environments and identified the support for a distributed design as well as an adaptability to the changing environment as main design issues.
Consequently, we have proposed a modular design that integrates between the context acquisition and the context interpretation layer. Alternatively, the context prediction architecture might also be applied on top of the context interpretation layer on high-level context time series.

Our architecture is composed from two functional, loosely coupled entities. These are a learning module and a prediction module. Both contain all functions required to state a prediction on contexts of arbitrary context abstraction level. Furthermore, we have proposed sample implementations for the modules. Among the implemented modules are several prediction components, namely a Markov prediction component, an ARMA prediction component and an alignment prediction component.

Alignment prediction algorithm

Context prediction algorithm Another aspect of context prediction are algorithms for this task. For context prediction algorithms, we discussed strengths and weaknesses of state-of-the-art approaches such as ARMA, Markov, Ingependent Component Analysis (ICA) or Principal Component Analysis (PCA) algorithms.
On the basis of requirements identified for algorithms in context prediction scenarios, we are able to single out those approaches that are best suited for context prediction tasks.

A novel context prediction scheme that was developed in the scope of the thesis is also compared to the existing algorithms. For various exemplary algorithms, we provide results from simulations and case studies in various application domains. A prediction algorithm's performance is always dependent on the input data's structure and type.

Whereas the ARMA prediction approach showed remarkable results on numeric-input time series incorporating trends and periodic patterns, the alignment prediction approach easily outperformed it in environments dominated by frequently reappearing typical patterns, especially for long prediction horizons. Markov prediction is especially well suited for short prediction horizons and dominated the other approaches in the scenario with many nominal contexts. Regarding the ICA- and PCA-based prediction approaches, the former achieved better results with many nominal contexts, whereas the latter performed better with fewer nominal contexts. However, both methods require a priori knowledge on behavior patterns’ intermittency.

With our quantitative results, we expect that researchers will have a better understanding of prediction process’s impacts and make better algorithmic decisions in future studies and implementations.

Publications