Context Prediction

We investigate the feasibility of next context prediction using sequences of previously contexts and compare the efficiency of several prediction methods. There are four main contexts: the id, the location, the time, and the activity. We concentrate mostly on the location and evaluate the prediction methods in a scenario which concerns employees in an office building visiting offices in a regular fashion over some period of time. We model the scenario by different prediction techniques like dynamic Bayesian networks, neural networks, Markov predictors, and state predictors.

The aim of the project is to investigate how far machine learning techniques can dynamically predict location sequences, time of location entry, and duration of stays independent of additional knowledge. Of course the information could be combined with contextual knowledge as e.g. the office time table or personal schedule of a person; however, we focus currently on dynamic techniques without contextual knowledge.

Further interesting questions concern the efficiency of training of a predictor, before the first useful predictions can be performed, and of retraining, i.e. how long it takes until the predictor adapts to a habitual change and provides again useful predictions. Predictions are called useful if a prediction is accurate with a certain confidence level. Moreover, memory and performance requirements of a predictor are of interest in particular for mobile appliances with limited performance ability and power supply.

The predictions could be used for a number of applications in a smart office environment:

• In the Smart Doorplate Project a visitor is notified about the probable next location of an absent office owner within a smart office building. The prediction is needed to decide if the visitor should follow the searched person to his current location, go to the predicted next location, or just wait till the office owner comes back.

• Phone call forwarding to the current office location of a person is an often proposed smart office application, but where to forward a phone call in case that a person just left his office and did not yet reach his destination? The phone call could be forwarded to the predicted room and answered as soon as the person reaches his destination.

Our experiments as part of Smart Doorplate Project yielded a collection of movement data of four persons over several months that are publicly available as Augsburg Indoor Location Tracking Benchmarks. We use this benchmark data to evaluate several prediction techniques and compare the efficiency of these techniques with exactly the same evaluation set-up and data. Moreover, we can estimate how good next location prediction works - at least for the Augsburg Indoor Location Tracking Benchmark data.

We investigate neural networks, Bayesian networks, Markov predictors, and State predictors. First we chose from the multitude of neural networks the most well-known, the Multi-Layer Perceptron with one hidden layer and back-propagation learning algorithm. The multi-layer perceptron was chosen because of its general application domain and its popularity in the neural network research community. After analyzing more neural networks we decided that an Elman Net fits better for solving the next location problem. Elman nets hold a so-called context layer. With this layer the nets are suited to learn sequences. The results show that Elman nets are usually better suited than the multi-layer perceptron.

In the case of Bayesian networks we started with a static Bayesian network. Afterwards, in order to predict a future context of a person, the usage of a Dynamic Bayesian Network was chosen. This network consists of different time slices which all contain an identical Bayesian network. Bayesian networks are particularly well suited to model time.

The State Predictor method originates in branch prediction and data compression algorithms that are transformed and adapted to fit the scenario of context prediction. Generally speaking, the prediction principle is derived from Markov chains theory. Several one- and two-level predictors were proposed and evaluated first by synthetic benchmarks.

	Elman net	Multi-layer perceptron	Bayesian network	State predictor	Markov predictor
Person A	91.07 %	87.39 %	85.58 %	88.39 %	90.18 %
Person B	78.88 %	75.66 %	86.54 %	80.35 %	78.97 %
Person C	69.92 %	68.68 %	86.77 %	75.17 %	75.17 %
Person D	78.83 %	74.06 %	69.78 %	76.42 %	78.05 %

The table compares the prediction accuracies of the neural networks Elman net and multi-layer perceptron, Bayesian network, state predictor, and Markov Predictor showing always the best results yielded for each person of the Augsburg Benchmarks. The configurations may vary for different persons. Typically, there is no superb configuration of a predictor for all persons. The shown prediction accuracies are derived for the first scenario where a visitor will be informed about the potential return of an office owner. That means the accuracies include only predictions when the employee isn't in his own room. Furthermore the following set-up was used: All prediction algorithms were trained with summer data and the accuracies were measured with the fall data (see Augsburg Benchmarks). The results show that there isn't a universal predictor.

Because of the sometimes unreliable results of predictions it may be sometimes better to make no prediction instead of a wrong prediction. Humans may be frustrated by too many wrong predictions and won't believe in further predictions even when the prediction accuracy improves over time. Therefore Confidence Estimation of context prediction methods is necessary. We propose and evaluate three confidence estimation techniques for the state predictor method – the strong state method, the threshold method, and the confidence counter method. The proposed confidence estimation techniques can also be transferred to other prediction methods like Markov predictors, neural network, or Bayesian networks.

Moreover, also the length of stay is of interest. This can easily be predicted by dynamic Bayesian networks or attached to other predictors as arithmetic mean or median of previous length of stay in the respective location.

A user must set up a lot of parameters before he can use one of the proposed prediction methods and these parameters differ for each user. Therefore a complex configuration must be made before such a method can be used. A Hybrid Predictor can reduce the configuration overhead utilizing different prediction methods or configurations in parallel to yield different prediction results. A selector chooses the most appropriate prediction result from the result set of the base predictors. We propose and evaluate three principal hybrid predictor approaches – the warm-up predictor, the majority predictor, and the confidence predictor – with several variants. The hybrid predictors reach higher prediction accuracy than the average of the prediction accuracies of the separately used predictors.

The project Context Prediction in Ubiquitous Computing was finished with the PhD thesis of Jan Petzold.

Publications