TY - JOUR
T1 - A Martingale framework for detecting changes in data streams by testing exchangeability
AU - Ho, Shen Shyang
AU - Wechsler, Harry
N1 - Funding Information:
The authors thank the anonymous reviewers for their suggestions and Vladimir Vovk for useful discussions. The research described in this paper was partially carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration (NASA). Shen-Shyang Ho was supported by the NASA Postdoctoral Program (NPP) administrated by Oak Ridge Associated Universities (ORAU) through a contract with NASA when this paper was completed.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=78049529489&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78049529489&partnerID=8YFLogxK
U2 - 10.1109/TPAMI.2010.48
DO - 10.1109/TPAMI.2010.48
M3 - Article
C2 - 20975112
AN - SCOPUS:78049529489
VL - 32
SP - 2113
EP - 2127
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
SN - 0162-8828
IS - 12
M1 - 5432193
ER -