The Hierarchical ICI-based CDT


The Problem

One of the most important challenges in datastream analysis is the online detection of changes affecting the data-generating process. Changes might reveal critical situations, such as a fault affecting a sensing apparatus, an anomalous event, or an unforeseen evolution of the surrounding environment, to name a few examples.

Methods designed to detect changes in datastreams are typically referred to as change-detection tests (CDTs). Due to their statistical nature, CDTs intrinsically introduce false-positives, which might prompt costly and unnecessary reactions to the detected -not existing- change.


Hierarchical CDTs

We propose hierarchical change-detection tests (HCDTs), powerful algorithms that combine different techniques to detect and validate changes [Alippi et al. 2016]. HCDTs feature a two-layered architecture consisting in a detection layer and validation layer, and implements an automatic reconfiguration mechanism.

  • The Detection Layer is designed to steadily analyze the datastream at a low computational cost, by means of an online and sequential CDT (like, for instance, the ICI-based CDT [Alippi et al. 2011 b]).
  • The Validation Layer performs an offline analysis based on an hypothesis test (HT) to determine whether the detection corresponds to an actual change in the data-generating process or not (false-positive detection).
When the change is actually confirmed, the validation layer automatically identifies a sequence of data generated in the post-change conditions to be used to reconfigure the HCDT. Differently, when the change is not confirmed, the HCDT restarts in its initial conditions

In [Alippi et al. 2016] we show that the change-detection performance can be often improved by introducing a validation layer. In fact, HCDTs often achieve a far more convenient false-positive rate (FPR) vs detection-delay (DD) trade-off than their single-layered counterpart. This is in particular true in monitoring scenarios where the pre/post change states of the data-generating process are unknown.

Figure 1 illustrate HCDTs from an high-level perspective, which can be customized by using specirfic change-detection and validation techniques.

Figure 1 A scheme illustrating HCDTs architecture and basic functioning. When the input datastream {s(t), t = 1,..} can not be modeled as a sequence of i.i.d. random values, it is necessary to perform a preliminary processing P yielding the stream of i.i.d. change indicators X = {x(t), t = 1,...}, otherwise s(t) = x(t). The detection layer runs a CDT on the input stream X, and activates the validation layer as soon as it detects a change at time \hat{T}. Then, the validation layer identifies a suitable validation sequence V and runs an HT to assess whether V contains a change point or not. When the change point is found at \hat{T^*}, the detection is confirmed, and a subsequence of the datastream R = {s(t), t = 1, .., \hat{T^*} is identified to reconfigure the HCDT and possibly the preprocessing. Differently, when the change is not validated, R remains the original training sequence and the HCDT is restarted in its previous conditions. This automatic reconfiguration makes the HCDT able to continue the monitoring activity after each detected change, thus being able to detect any further departure from the post-change conditions.


Hierarchical ICI-based CDTs

The hierarchical ICI-based CDT [Alippi et al. 2011 b] belongs to the family of ICI-based CDTs [Alippi et al. 2011 b], that sequentialy monitors a set of features extracted from datastream, and assess feature stationarity by means of the ICI rule [Goldenshluger and Nemirovski 1997]. For a detailed description of the hierarchical ICI-based CDT, please refer to [Alippi et al. 2011 a]. A distributed solution meant for wireless sensor networks has been presented in [Alippi et al. 2011 c].


Codes are available for Download (Matlab Package Updated on March, 2016)

A Matlab package containing the functions implementing 4 HCDTs used in [Alippi et al. 2016] :

  • Hierarchical CUSUM test
  • Hierarchical ICI-based test (using Lepage CPM at the validation layer)
  • Hierarchical ICI-based test (using Hotelling T2 test at the validation layer)
  • Hierarchical NP-CUSUM test

See [Alippi et al. 2016] for deatiled description of these HCDTs


References

[Alippi et al. 2016] Hierarchical Change-Detection Tests
Cesare Alippi, Giacomo Boracchi, Manuel Roveri, IEEE Transactions on Neural Networks and Learning Systems, In Press (2016), 13 pages doi:10.1109/TNNLS.2015.2512714
(Preprint), (Original), (BibTeX).

[Alippi et al. 2011 a] A Hierarchical, Nonparametric Sequential Change-Detection Test
Cesare Alippi, Giacomo Boracchi and Manuel Roveri, in Proceedings of IJCNN 2011, the International Joint Conference on Neural Networks, San Jose, California July 31 - August 5, 2011. pp 2889 - 2896, doi: 10.1109/IJCNN.2011.6033600
(Preprint), (BibTeX), (Original)

[Alippi et al. 2011 b] A just-in-time adaptive classification system based on the intersection of confidence intervals rule,
Cesare Alippi, Giacomo Boracchi, Manuel Roveri Neural Networks, Elsevier vol. 24 (2011), pp. 791-800
doi: 10.1016/j.neunet.2011.05.012
(Preprint), (BibTeX), (Original)

[Alippi et al. 2011 c] A distributed Self-adaptive Nonparametric Change-Detection Test for Sensor/Actuator Networks,
Cesare Alippi, Giacomo Boracchi and Manuel Roveri, ICANN 2011, 21th International Conference on Artificial Neural Networks, June 14-17th, 2011, Espoo, Finland. Lecture Notes in Computer Science, 2011, Vol. 6792/2011, 173-180, doi: 10.1007/978-3-642-21738-8_23 The original publication is available at www.springerlink.com .
(Preprint), (BibTeX), (Original)

[Goldenshluger and Nemirovski 1997] On spatial adaptive estimation of nonparametric regression.
Goldenshluger, A., & Nemirovski, A. (1997) Mathematical Methods of Statistics, vol 6, 135-170.