On the Detection of Concept Changes in Time-Varying Data Stream by Testing Exchangeability
Shen-Shyang Ho, Harry Wechsler
A martingale framework for concept change detection based on testing data exchangeability was recently proposed (Ho, 2005). In this paper, we describe the proposed change-detection test based on the Doob's Maximal Inequality and show that it is an approximation of the sequential probability ratio test (SPRT). The relationship between the threshold value used in the proposed test and its size and power is deduced from the approximation. The mean delay time before a change is detected is estimated using the average sample number of a SPRT. The performance of the test using various threshold values is examined on five different data stream scenarios simulated using two synthetic data sets. Finally, experimental results show that the test is effective in detecting changes in time-varying data streams simulated using three benchmark data sets.
PDF Link: /papers/05/p267-ho.pdf
AUTHOR = "Shen-Shyang Ho
and Harry Wechsler",
TITLE = "On the Detection of Concept Changes in Time-Varying Data Stream by Testing Exchangeability",
BOOKTITLE = "Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2005",
PAGES = "267--274"