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

Shen Shyang Ho, Harry Wechsler

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

In a data streaming setting, data points are observed sequentially. The data generating model may change as the data are streaming. In this paper, we propose detecting this change in data streams by testing the exchangeability property of the observed data. Our martingale approach is an efficient, nonparametric, one-pass algorithm that is effective on the classification, cluster, and regression data generating models. Experimental results show the feasibility and effectiveness of the martingale methodology in detecting changes in the data generating model for time-varying data streams. Moreover, we also show that: 1) An adaptive support vector machine (SVM) utilizing the martingale methodology compares favorably against an adaptive SVM utilizing a sliding window, and 2) a multiple martingale video-shot change detector compares favorably against standard shot-change detection algorithms.

Original languageEnglish (US)
Article number5432193
Pages (from-to)2113-2127
Number of pages15
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume32
Issue number12
DOIs
StatePublished - 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A Martingale framework for detecting changes in data streams by testing exchangeability'. Together they form a unique fingerprint.

Cite this