Center for Automated Research, University of Maryland Institute for Advanced Computer Studies, A.V. Williams Building, College Park, MD 20742, USA.
IEEE Trans Pattern Anal Mach Intell. 2010 Dec;32(12):2113-27. doi: 10.1109/TPAMI.2010.48.
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.
在数据流设置中，数据点是顺序观察到的。随着数据的流动，数据生成模型可能会发生变化。在本文中，我们通过检验观测数据的可交换性来检测数据流中的这种变化。我们的鞅方法是一种有效的、非参数的、一次通过的算法，对分类、聚类和回归数据生成模型都有效。实验结果表明，鞅方法在检测时变数据流中数据生成模型的变化方面具有可行性和有效性。此外，我们还表明：1）利用鞅方法的自适应支持向量机（SVM）优于利用滑动窗口的自适应 SVM，2）多个鞅视频镜头变化检测器优于标准镜头变化检测算法。
