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, Vol. 79, No. 3, pp. 283-306, July 2009.
      BibTeX TR2009-057 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 = {}
      • }
  • 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.


  • Related News & Events