Fast Adaptive Algorithms for Abrupt Change Detection
| Citation: | Nikovski, D.N.; Jain, A., "Fast Adaptive Algorithms for Abrupt Change Detection", Machine Learning, ISSN 0885-6125; DOI 10.1007/s10994-009-5122-x, July 2009 (SpringerLink) |
| MERL Report: | TR2009-057 |
| MERL Contact: | Daniel Nikovski |
An instance of a sliding window and its probable sub-windows
We propose two fast algorithms for abrupt change detection in streaming data that can operate on arbitrary unknown data distributions before and after the change. The first algorithm, MB-GT, computes efficiently the average Euclidean distance between all pairs of data points before and after the hypothesized change. The second algorithm, MB-CUSUM, computes the log-likelihood ratio statistic for the data distributions before and after the change, similarly to the classical CUSUM algorithm, but unlike that algorithm, MB-CUSUM does not need to know the exact distributions, and uses kernel density estimates instead. Although a straightforward computation of the two change statistics would have computational complexity of O(N4) with respect to the size N of the streaming data buffer, the proposed algorithms are able to use the computational structure of these statistics to achieve a computational complexity of only O(N2) and memory requirement of O(N). Furthermore, the algorithms perform surprisingly well on dependent observations generated by underlying dynamical systems, unlike traditional change detection algorithms.
 | Read the full technical report (PDF: 921.6 kB) |