Context-Driven Predictions

Marc G. Bellemare, Doina PrecupIJCAI 2007 · OpenReview

Introduction

Predicting future events in partially observable environments is a cornerstone of intelligent behavior. Traditional approaches often rely on Markov models, which assume that the current state encapsulates all necessary information for future predictions. However, in real-world scenarios, crucial information may be buried in the distant past. This paper by Marc G. Bellemare and Doina Precup (2007) introduces a context-driven prediction framework that leverages associative memory to bridge these temporal gaps without the computational complexity of hidden state models.

The Challenge of Partial Observability

Standard Markov Chains struggle when the "Markov property" is violated—that is, when a single observation is insufficient for prediction. Common workarounds include:

  1. Fixed-order models: These use a sliding window of the last $N$ observations. They fail if the relevant context occurred $N+1$ steps ago.
  2. Latent state models (HMMs/POMDPs): These maintain a belief state over hidden variables. While robust, they require pre-defined state spaces and are often computationally intensive.

The authors propose a middle ground: a model that learns context incrementally from an arbitrary history length without requiring a pre-defined hidden state space.

Methodology: Saliency and Associative Memory

The framework is built upon Sparse Distributed Memories (SDMs). The core innovation lies in how "context" is represented and updated.

The Saliency Vector ($s$)

Instead of a discrete state, the model maintains a saliency vector $s$. When an observation (percept) $p$ occurs, its corresponding entry in $s$ is set to 1. Over time, these values decay by a factor $\gamma \in [0, 1]$. This creates a "trace" where recent events have high saliency and older events have lower saliency, effectively representing the temporal context as a gradient of influence.

Learning and Prediction

The model uses a weight matrix $W$ to map the current saliency vector to predictions. Predictions are generated using a Boltzmann (softmax) distribution, allowing the model to represent uncertainty across multiple possible future events.

The learning algorithm updates weights based on the difference between predicted probabilities and observed percepts.

Weights are updated via gradient descent to minimize the squared error between the predicted distribution $\pi$ and the actual subsequent observation $\alpha(p)$.

Experimental Results

The model was evaluated on several synthetic symbolic sequences designed to test specific predictive capabilities.

Frequency and Ordering

The model successfully matched underlying probabilities in stochastic sequences (e.g., correctly predicting a symbol with 75% probability when its true frequency was 0.75). It also demonstrated "temporal discrimination," distinguishing between sequences like 1-2-3 and 2-1-4 where the order of events determines the outcome.

Long-Term Context

A key strength of the saliency-based approach is its ability to handle long-term dependencies. In tests where a "clue" symbol (e.g., 6 or 7) appeared at the start of a long sequence, the model could still use that information to predict the final symbol, even after five intervening steps had caused the original clue's saliency to decay significantly.

Prediction accuracy for long-term context sequences across varying episode counts.

As shown in the results, the model's accuracy improves steadily with more training episodes, even for complex sequences like 6123458 vs 7123459 where the differentiating information is distant.

Discussion and Limitations

While powerful, the model has notable limitations. It currently struggles with "counting"—distinguishing between seeing a percept once versus twice in a short window—because the saliency trace is simple. Additionally, the model assumes "hard locations" (the basic units of percepts) are pre-defined. Future work aims to scale this approach to high-dimensional, noisy sensory data and to automate the discovery of relevant percepts.

Conclusion

By treating context as a decaying trace of past influences rather than a rigid state transition, this model provides a flexible and computationally efficient alternative for prediction in complex environments. It successfully bridges the gap between simple fixed-order models and complex latent state representations.

Summary updated

Abstract

Markov models have been a keystone in Artificial Intelligence for many decades. However, they remain unsatisfactory when the environment modelled is partially observable. There are pathological examples where no history of fixed length is sufficient for accurate prediction or decision making. On the other hand, working with a hidden state (like in Hidden Markov Models or Partially Observable Markov Decision Processes) has a high computational cost. In order to circumvent this problem, we suggest the use of a context-based model. Our approach replaces strict transition probabilities by influences on transitions. The method proposed provides a trade-off between a fully and partially observable model. We also discuss the capacity of our framework to model hierarchical knowledge and abstraction. Simple examples are given in order to show the advantages of the algorithm.
BibTeX
@inproceedings{bellemare2007context,
  author = {Marc G. Bellemare and Doina Precup},
  title = {{Context-Driven Predictions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=HkZcoNzObH},
}
Figure