Article Preview
Top1. Introduction
Today, with the big data phenomenon, considerable research is being put on designing online algorithms capable of detecting changes in the distribution of streaming data. Such changes happen in any system due to unforeseen external conditions and can indicate possible faults, anomalies, or any significant events that require the attention of a human expert. A change happens when new data observations deviate from previous ones and become not identically distributed (i.e. way say that the exchangeability assumption is violated). To detect such changes, it is often necessary to model the system's behavior (e.g. have knowledge about the distribution of the data). However, in a time where the volumes of data and the complexity of systems is continuously growing, it becomes not always feasible for human experts to build an exhaustive or good definition of each system's behavior. This paper discusses the exchangeability test for a given random sequence using the martingale-based approach. The results can be applied for detecting change-point in streaming data including cases for abrupt change and concept drift, i.e. changes that happen in a smooth and incremental manner. In real world applications, systems often exhibit complex behavior and the data distribution is unknown. The martingale based approach is well suited in these scenarios for change-point detection since it does not rely on any distributional knowledge about the data, which is in contrast to the traditional sequential change-point detection methods such as Sequential Probability Ratio Test (Wald, 1945), and the Cumulative SUM control chart (Page, 1954). The work in this paper can be beneficial to a wide range of applications, such as, monitoring systems for fault detection (Farouq, 2020; Smolyakov, 2018), detection changes in driving behavior (Ali, 2017), emotion change from speed (Zhaocheng, 2016), and detecting anomalous situations in ambient assisted living applications (Bersch, 2013).
The idea of using martingale for exchangeability test dates back to the work in (Vovk 2003), building on the theory of Transductive Confidence Machine (Vovk 2005), where the concept of “exchangeability martingales” was introduced for implementing the test which works in an online manner. Later, it was further established that (Fedorova 2012) to maximize the logarithmic growth rate of the multiplicative martingale, the betting function used for constructing the martingale should be chosen as the empirical probability density function (p.d.f.) of the p-values. The way to construct this empirical p.d.f. suggested therein was to use a modified kernel density estimator. In (Ho 2005a; Ho 2005b), the authors applied various concentration inequalities on the multiplicative martingale sequence to design tests for detecting change in data streams. However, due to the high variability of the multiplicative martingale sequence, it is hard to design the test based on concentration inequalities. In addition, the multiplicative martingale values in the log scale will exhibit an undesirable behavior that a decreasing trend even when no change happens (which will be illustrated by an example in the Evaluation section).
In order to address these shortcomings as stated before, this paper proposes a new type of martingale for the exchangeability test (called “additive martingale”) which can be implemented in an online fashion. Different betting functions for constructing the additive martingale are discussed as well. Interestingly, similar to the multiplicative martingale case, it is shown that by choosing the betting function as the underlying p.d.f. of the p-values, when a change-point appears (then the generated p-values are not uniformly distributed), a satisfying balance between the smoothness and expected one-step increment in the martingale sequence will be obtained. Based on Beta distribution parametrization, a computationally efficient way for constructing this betting function is discussed. Finally, designing tests for change-point detection based on different concentration inequalities are discussed. The novelty and contributions of this paper are summarized as follows:
- •
Formulation of a new martingale for change-point detection, which makes it possible to define an upper bound confidence using the Hoeffding-Azuma lemma.
- •
A proof that constructing the martingale sequence using the “underlying p.d.f of the p-values” as a betting function, leads to a satisfying trade-off between: (i) “how fast the sequence values grow when a change in the data distribution occurs”, and (ii) “the smoothness of the sequence when no change occurs”.
- •
An online/incremental algorithm based on the Beta distribution parametrization for constructing the proposed martingale.