TR2009-057

Fast Adaptive Algorithms for Abrupt Change Detection


    •  Nikovski, D.N.; Jain, A., "Fast Adaptive Algorithms for Abrupt Change Detection", Machine Learning, DOI: 10.1007/S10994-009-5122-X, ISSN: 0885-6125, Vol. 79, No. 3, pp. 283-306, July 2009.
      BibTeX Download PDF
      • @article{Nikovski2009jul2,
      • author = {Nikovski, D.N. and Jain, A.},
      • title = {Fast Adaptive Algorithms for Abrupt Change Detection},
      • journal = {Machine Learning},
      • year = 2009,
      • volume = 79,
      • number = 3,
      • pages = {283--306},
      • month = jul,
      • doi = {10.1007/S10994-009-5122-X},
      • issn = {0885-6125},
      • url = {http://www.merl.com/publications/TR2009-057}
      • }
  • MERL Contact:
  • Research Areas:

    Data Analytics, Optimization


TR Image
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.