A Multi-Objective Multi-Modal Optimization Approach for Mining Stable Spatio-Temporal Patterns

Michèle Sebag, Nicolas Tarrisson, Olivier Teytaud, Julien Lefèvre, Sylvain BailletIJCAI 2005 · OpenReview

Abstract

Functional brain imaging, specifically Magnetoencephalography (MEG), presents a significant data mining challenge: identifying stable spatio-temporal patterns (STPs) within massive, noisy datasets. This paper introduces 4D-Miner, an evolutionary algorithm that treats pattern discovery as a multi-objective multi-modal optimization problem. By balancing conflicting objectives like spatial amplitude and temporal duration while maintaining solution diversity, 4D-Miner can identify multiple distinct brain activity regions simultaneously. Empirical results on artificial and real-world datasets demonstrate that the algorithm is highly scalable, processing datasets exceeding 400 MB in minutes.

Introduction

Functional brain imaging captures neural activity with millisecond temporal resolution. While this provides a wealth of data, it creates a "needle in a haystack" problem for neuroscientists. They are looking for Stable Spatio-Temporal Patterns (STPs): specific groups of sensors that show highly correlated activity over a specific window of time. Traditionally, these patterns were identified manually—a tedious, subjective process that hindered the reproducibility of results. Standard data mining techniques often struggle here because a "good" pattern needs to be large, last a long time, and have high internal consistency; improving one often degrades the others.

The 4D-Miner Framework

The researchers developed 4D-Miner, an evolutionary algorithm designed to automatically find these patterns by framing the search as a "multi-objective multi-modal" optimization problem.

Multi-Objective Optimization

Instead of merging goals into a single score, the algorithm uses Pareto domination. A pattern is only considered "worse" than another if it is inferior across all criteria: spatial size, temporal duration, and signal alignment. This allows the algorithm to explore the trade-offs between these conflicting goals naturally.

Multi-Modal Diversity (p-inclusion)

In brain mapping, the "second-best" pattern is just as important as the first if it occurs in a different part of the brain. To ensure the algorithm doesn't just find variations of the same "best" pattern, the authors introduced p-inclusion. This diversity criterion allows the algorithm to keep "dominated" patterns in the results as long as they cover a different physical or temporal area of the brain, ensuring a map of all distinct active regions.

Evolutionary Strategy

4D-Miner acts like a digital evolution process. It starts with a random population of potential patterns (defined as ellipsoids in 3D space plus a time interval). It then evolves them through mutation (randomly shifting location or size), crossover (combining features of successful patterns), and selection (maintaining a Pareto archive of the most promising and diverse patterns).

Experimental Validation

The algorithm was tested on both artificial and real-world datasets:

  1. Artificial Datasets: Synthetic data where 10 target patterns were hidden inside varying levels of noise. This allowed for precise measurement of recall and precision across datasets scaled up to 4,000 sensors and 8,000 time steps.
  2. Real-World MEG Data: Data recorded from subjects watching a moving ball, involving 151 sensors and 875 time steps.

Key Results

Performance and Recall

In synthetic tests, 4D-Miner demonstrated high recall, successfully identifying hidden patterns even in noisy environments. As shown in the figure below, the recall rate improves steadily as the number of fitness evaluations increases, reaching high stability across different configurations.

Figure 5: Recall performance of 4D-Miner over fitness evaluations for artificial datasets.

Linear Scalability

One of the most significant findings is the algorithm's efficiency. The computational cost grows linearly with the number of sensors ($N$) and is largely unaffected by the number of time steps ($T$). On real-world datasets, 4D-Miner identified satisfactory STPs in less than one minute on a standard PC.

Figure 6: Computational cost of 4D-Miner, showing linear runtime growth relative to the number of sensors (N).

Conclusion

4D-Miner provides an efficient, automated tool for neuroscientists to map brain activity. By prioritizing diversity as a core requirement rather than a heuristic, it ensures that all relevant active regions are captured. Future work will focus on automating parameter tuning and extending the tool to supervised learning tasks, such as comparing patterns between healthy subjects and those with neurological conditions.

Summary updated

Abstract

This paper, motivated by functional brain imaging applications, is interested in the discovery of stable spatio-temporal patterns. This problem is formalized as a multi-objective multi-modal optimization problem: on one hand, the target patterns must show a good stability in a wide spatio-temporal region (antagonistic objectives); on the other hand, experts are interested in finding all such patterns (global and local optima). The proposed algorithm, termed 4D-Miner, is empirically validated on artificial and real-world datasets; it shows good performances and scalability, detecting target spatiotemporal patterns within minutes from 400+ Mo datasets.
BibTeX
@inproceedings{sebag2005multi,
  author = {Michèle Sebag and Nicolas Tarrisson and Olivier Teytaud and Julien Lefèvre and Sylvain Baillet},
  title = {{A Multi-Objective Multi-Modal Optimization Approach for Mining Stable Spatio-Temporal Patterns}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=rkNNaMG_br},
}

Loading related content...

Figure