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.
ChallengesChallenges 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. 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. 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.
- Formal definition of the context prediction task
- Flexible and lean architecture for context prediction which can be applied to general context prediction tasks and which supports arbitrary order of context prediction operations
- Novel alignment prediction algorithm together with extensive studies on its prediction accuracy compared to state-of-the-art prediction methods
- Comprehensive analytic model of the impact of various design parameters (e.g. dimension and size of the context history, order of context processing operations,...) on the context prediction accuracy (independent from the algorithm employed!)
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.
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
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.
- Stephan Sigg, Dawud Gordon, Georg von Zengen, Michael Beigl, Sandra Haseloff and Klaus David: Investigation of context prediction accuracy for different context abstraction levels, in IEEE Transactions on Mobile Computing (TMC), 2012 (DOI)
- Dawud Gordon, Stephan Sigg and Michael Beigl: Using Prediction to Conserve Energy in Recognition on Mobile Devices, in 9th IEEE International Conference on Pervasive Computing and Communications (PerCom), WiP session, 2011 (DOI)
- Stephan Sigg, Klaus David and Sandra Haseloff: An Alignment Approach for Context Prediction Tasks in UbiComp Environments, in IEEE Pervasive Computing, Los Alamitos, CA, USA, IEEE Computer Society, 2010 (DOI)
- Stephan Sigg, Monty Beuster, Daniel Roehr and Michael Beigl: Search Space Size and Context Prediction, in Proceedings of the fifth International Conference on Networked Sensing Systems (INSS'08), June 2008
- Stephan Sigg: Development of a novel context prediction algorithm and analysis of context prediction schemes, University of Kassel, Chair for Communication Technology, ComTec, February 2008 (DOI)
- Stephan Sigg, Sandra Haseloff and Klaus David: A Study on Context Prediction and Adaptivity, in Proceedings of the International Workshop on Context Modeling and Management for Smart Environments (CMMSE'07), October 2007 (DOI)
- Stephan Sigg, Sandra Haseloff and Klaus David: Prediction of Context Time Series (PDF), in Proceedings of the 5th Workshop on Applications of Wireless Communications (WAWC'07), J. Ikonen and M. Juutilainen and J. Porras, Seite 31-45, August 2007
- Stephan Sigg, Sian Lun Lau, Sandra Haseloff and Klaus David: Approaching a Definition of Context Prediction, in Proceedings of the Third Workshop on Context Awareness for Proactive Systems (CAPS'07), June 2007
- Stephan Sigg, Sandra Haseloff and Klaus David: Minimising the Context Prediction Error, in Proceedings of IEEE 65th Vehicular Technology Conference VTC2007-Spring (VTC-2007 Spring), April 2007 (DOI)
- Stephan Sigg, Sandra Haseloff and Klaus David: A novel approach to context prediction in ubicomp environments, in Proceedings of the 17th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2006), September 2006 (DOI)
- Stephan Sigg, Sandra Haseloff and Klaus David: The Impact of the Context Interpretation Error on the Context Prediction Accuracy, in Proceedings of the 3rd Annual International Conference on Mobile and Ubiquitous Systems: Networks and Services (MOBIQUITOUS 2006), July 2006 (DOI)
- Stephan Sigg, Sandra Haseloff and Klaus David: Context Prediction by Alignment Methods, in Poster Proceedings of the 4th International Conference on Mobile Systems, Applications, and Services (MobiSys 2006), June 2006 (PDF)
- Tino Loeffler, Stephan Sigg, Sandra Haseloff and Klaus David: The Quick Step to Foxtrot, in Proceedings of the Second Workshop on Context Awareness for Proactive Systems (CAPS 2006), Klaus David and Olaf Droegehorn and Sandra Haseloff, Kassel University press, June 2006 (Online)
- Stephan Sigg, Tino Loeffler, Sandra Haseloff and Klaus David: A Flexible Architecture For Context Aware Applications, in Workshop: Selbstorganisierende, adaptive und kontextsensitive Systeme (SAKS), 2006