A martingale framework for detecting changes in data streams by testing exchangeability

Area of Science:

• Computer Science
• Statistics
• Machine Learning

Background:

• Data streams present challenges due to sequential observations and potential changes in the underlying data-generating model.
• Detecting these changes is crucial for maintaining model accuracy and reliability in dynamic environments.

Purpose of the Study:

• To propose a novel method for detecting changes in data streams by leveraging the concept of data exchangeability.
• To introduce an efficient, nonparametric, one-pass algorithm based on martingales for change detection.

Main Methods:

• The core methodology involves testing the exchangeability property of observed data points in a sequential manner.
• A martingale-based approach is developed as an efficient, nonparametric, one-pass algorithm.
• The algorithm's effectiveness is evaluated across classification, clustering, and regression data-generating models.

Main Results:

• Experimental results demonstrate the feasibility and effectiveness of the martingale methodology in detecting changes in time-varying data streams.
• An adaptive support vector machine (SVM) using the martingale approach showed superior performance compared to an SVM with a sliding window.
• A multiple martingale video-shot change detector achieved better results than standard shot-change detection algorithms.

Conclusions:

• The martingale approach provides an effective and efficient solution for detecting changes in data streams.
• This nonparametric, one-pass algorithm is versatile and applicable to diverse data-generating models.
• The proposed methodology offers advantages over existing techniques, including sliding windows and standard shot-change detectors.