Detecting Changes in Unlabeled Data Streams Using Martingale

1 Introduction

The problem of detecting changes in low-dimensional sequential data has been studied by statisticians for more than fifty years. Methods of change detection first appeared in the 1940s based on Wald's sequential analysis [Wald, 1947], in particular the sequential probability sequential test (SPRT) [Basseville and Nikiforov, 1993], and later, Page introduced the cumulative sum method [Page, 1954]. Recently, the machine learning and the data mining communities become interested in the change detection problem due to the need to discover changes in data, such as customer click streams, high-dimensional multimedia data, and retail chain transactions, generated from online processes that are not stationary [Domingos and Hulten, 2001]. The target concepts change over time. It is, hence, vital to detect the changes in the data generating processes so that timely decisions can be made.

One real-world problem that requires detecting changes is the video segmentation problem which corresponds to videoshot change or video break detection. Many algorithms [Gargi et al., 2000; Lefevre et al., 2003; Zhai and Shah, 2005] have been proposed to perform video-shot change detection. The range of existing methods includes pixel and histogrambased difference methods and motion-based methods (e.g.

optical flow). Threshold selection, a critical step for successful change detection, is required by methods using global or local thresholds. For video sequences with clear and distinct shots, a single global threshold would be sufficient. For video sequences that have both abrupt and gradual changes between shots, however, a global threshold cannot be found. To address such concerns [Gargi et al., 2000] argued for the use of local thresholds. The use of local thresholds requires choosing appropriate window size. Alternatively, Zhai and Shah [Zhai and Shah, 2005] proposed that video breaks should be detected using the deviation from some current model.

Recently, [Ho, 2005] proposed a martingale method for change detection for high-dimensional labeled data streams. An adaptive support vector machine for time-varying data streams was proposed based on the martingale method [Ho and Wechsler, 2005a]. The main contributions of the present paper are: (i) the extension of the martingale methodology to unlabeled data stream, and (ii) the multiple-martingale test based on multiple views (features). We show empirically that the martingale method works well for unlabeled data stream and the multiple-martingale test compares favorably with alternative video-shot change detection methods for unlabeled video stream.

The paper is organized as follows. In Section 2, we review the concept of exchangeability and martingale. In Section 3, we introduce the concept of strangeness and p-values, and propose the strangeness measure for unlabeled data using clustering concept. In Section 4, we state the theorem on the martingale method for change detection which is applicable to both labeled and unlabeled data stream. In Section 5, we show the feasibility of the martingale method for change detection on an unlabeled synthetic data stream. In Section 6, we propose the multiple-martingale test for change detection. In Section 7, we apply the multiple-martingale test to video-shot change detection.

2 Exchangeability andMartingale

Let {Zi : 1 ≤ i < ∞} be a sequence of random variables. A finite sequence of random variables Z1, · · · ,Zi is exchangeable if the joint distribution p(Z1, · · · ,Zi) is invariant under any permutation of the indices of the random variables. The satisfaction of exchangeability condition indicates that the distribution that the sequence of random variables is drawn from is stationary.

[Vovk et al., 2003] introduced the idea of testing exchangeability online using the martingale. A martingale is a sequence of random variables {Mi : 0 ≤ i < ∞} such that Mn is a measurable function of Z1, · · · ,Zn for all n = 0, 1, · · · (in particular, M0 is a constant value) and the conditional expectation of Mn+1 given M0, · · · ,Mn is equal toMn, i.e.

After each new data point is received, an observer outputs a positive martingale value reflecting the strength of evidence found against the null hypothesis of data exchangeability. The testing of exchangeability is used to detect changes in timevarying labeled data streams [Ho and Wechsler, 2005b].

3 Strangeness and p-values

To apply the martingale method one needs to rank the data points according to their differences. Towards that end, one defines a strangeness measure that scores how much a data point is different from the other data points. Consider the set of labeled data points Z = {z1, · · · , zn-1} and the new labeled data point zn. Each data point is assigned a strangeness value based on the classifier, such as the support vector machine (SVM) or the nearest neighbor rule, used to classify the data points Z ⋃{zn} [Vovk et al., 2005].

To define a valid strangeness value for each data point, the simple assumption that at any time instance the strangeness value of each data point seen so far should be independent of the order these data points are used in the strangeness computation must be satisfied [Vovk et al., 2005]. For instance, when a k-nearest neighbor rule is used, the strangeness value of a particular data point is the ratio of the sum of the knearest data points with similar label (Ss) to the sum of the k-nearest data points with difference label (Sd). Hence, the higher Ss is, the higher the strangeness value, and vice versa. On the other hand, when Sd is high, the strangeness value is low. This is clearly a method that constructs valid strangeness values for labeled data points.

For unlabeled data, the strangeness measure is derived using clustering algorithm such as K-mean/median clustering with K = 1. Consider the set of unlabeled data points Z = {z1, · · · , zn-1} and the new unlabeled data point zn. The strangeness value si of zi for i = 1, · · · , n is

where C(·) is some cluster representation and ‖ · ‖ is some distance measure. The strangeness value for a data point is high when it is further away from the cluster representation, e.g. the cluster center.

Next, a statistic is constructed to rank the strangeness value of the new data point zn with respect to the strangeness values of all the observed data points. The statistic, called the pvalue of zn, is defined as

where si is the strangeness measure for zi, i = 1, 2, · · · , n and θn is randomly chosen from [0, 1].

The random number θn in (3) ensures that the pvalues p1, p2, · · · output by the p-value function V are distributed uniformly in [0, 1], provided that the input examples z1, z2, · · · are generated by an exchangeable probability distribution in the input space [Vovk et al., 2003]. This property of output p-values no longer holds when the exchangeability condition is not satisfied.

4 Change Detection usingMartingale

Intuitively, we assume that a sequence of data points with a change consists of concatenating two data segments, S1 and S2, such that the data distribution of S1 and S2 are P1 and P2 respectively and P1 ̸= P2. Switching a data point zi from S2 to a position in S1 will make the data point stand out in S1. The exchangeability condition is, therefore, violated. Exchangeability is a sufficient condition for a stable data stream. The absence of exchangeability suggests the occurrence of change.

A family of martingales, indexed by ϵ ∈ [0, 1], and referred to as the power martingale, is defined as

where the pis are the output p-values from the function V , with the initial martingale M (ϵ) 0 = 1. We note that M (ϵ) n = ϵpϵ-1 n M (ϵ) n-1 . Hence, it is not necessary to store the previous p-values. In our experiments, we use ϵ = 0.92, which is within the desirable range where the martingale value is more sensitive to a violation of the exchangeability condition [Vovk et al., 2003].

The following theorem is applicable to both labeled and unlabeled data streams as long as the assumption (stated in Section 3) on the strangeness measure is satisfied.

Theorem 1 ([Ho andWechsler, 2005b]) Let {M (ϵ) i : 0 ≤ i < ∞} be a martingale sequence of the form (4) constructed using p-values {pi : 1 ≤ i < ∞} computed from (3) based on a valid strangeness measure for a given data stream:

1. If no change occurs in the given data stream, then

where λ is a positive number.

1. Let α be the size of the test deciding in favor of the alternative hypothesis "change occurs in the data stream" when the null hypothesis "no change occurs in the data stream" is true and 1 - β be the power of the test deciding in favor of the alternative hypothesis when it is true, the martingale test according to (5) is an approximation of the sequential probability ratio test (SPRT), with

α

and the mean delay time E(m), i.e. the expected number of data points, m, observed before a change is detected, is approximated from the SPRT as follows:

where

A user selects a desirable threshold λ for the martingale test (5) based on (6). To estimate the start of the change, (7) is used .

5 Experimental Result: Synthetic Unlabeled Data Stream

We construct an artificial unlabeled data stream as follows:

1. Randomly generate four sets of 1050 data points S1, S2, S3, and S4 from four overlapping Gaussian distributions with randomly generated mean with variance 1.
2. Concatenate S1, S2, S3, and S4 to form a sequence D consisting of 4200 data points such that D = {S1; S2; S3; S4}.

Left graph in Figure 1(a) shows a sketch of four overlapping 2-dimensional Gaussian distributions generated by Step 1 of the above procedure. The data distribution of the data sequence D changes with 3 change points.

In the experiment, the first 50 points from D is first used to compute the center of the initial 1-mean cluster with strangeness of each data point computed using (2) with the Euclidean distance. The threshold λ value for the martingale test is set to 10. The data points from the data stream D are observed sequentially. The cluster center is updated. Strangeness for all seen data points are computed. The martingale at each instance is computed using (4) based on the computed p-values from (3). When the martingale value is greater than λ, a change in the mean of the Gaussian distribution is detected. All previously seen data points are removed. The martingale is reset to 1. The next 50 data points are used to construct a new 1-mean cluster. The process repeats till the data points in D are exhausted.

Right graph in Figure 1(a) shows the trajectory of the center of 1-mean cluster in the experiment. The theoretical basis for signaling a change is (5). Figure 1(b) shows the martingale values. Detection occurs when the martingale value is greater than λ = 10. The true change points are at data points 1000, 2000 and 3000. The dimension of the Gaussian distribution is then increased to 10. Figure 2 shows that the changes in mean parameter of the high-dimensional Gaussian distribution are detected as well.

We note that in some real-world problems, more than one data feature is good in representing the data. In order to utilize this observation to improve the sensitivity and performance of the martingale test, one can perform a number of martingale tests constructed based on different characteristics or features of the data.

6 Multiple-Martingale Test usingMulti-Views

In the multi-view learning problem, an example z is represented by a number of feature subsets. Each feature subset describes a view of the example [Muslea et al., 2002]. The multi-view setting is closely related to co-training [Blum and Mitchell, 1998].

For the multiple-martingale test, we consider the multiview setting such that each constructed martingale attempts to identify changes with respect to the particular feature subset. Besides the fact that the features are extracted from the original data, the feature subsets should be independent of one another to minimize redundancy.

We note that according to the martingale theory, the data representation does not affect the probability bound (5). On the other hand,

Corollary 1 When the multiple martingale test with Mviews is used for change detection, the expected number of data points, m, observed before a change point is detected,

Obviously, one can conclude that the number of miss detection using the multiple-martingale test is upper-bounded by the number of miss detection using the original martingale method. Moreover, the number of false alarm using the multiple martingale test is lower-bounded by the number of false alarm using the original martingale method.

Algorithm 1 is the multiple-martingale test with two views. The algorithm can be trivially extended to M > 2.

Algorithm 1 : Multiple-Martingale Test with M-View, M= 2

Initialize: M1(0) = M2(0) = 1; i = 1; T = {}. Set: λ.

• 1: loop
• 2: A new unlabeled example xi is observed.
• 3: Construct the two views/features from xi, i.e., ¯ xi = {fi1, fi2}.
• 4: Compute the strangeness measure ⃗s1 and ⃗s2 (vectors containing strangeness for seen examples) using (2) from {f11, · · · , fi1} and {f12, · · · , fi2}.
• 5: Compute the p-values p1 and p2 from ⃗s1 and ⃗s2, respectively, using (3).
• 6: Compute M1(i) andM2(i) from p1 and p2 using (4).
• 7: if M1(i) > λ OR M2(i) > λ then
• 8: CHANGE DETECTED
• 9: Set M1(i) and M2(i) to 1;
• 10: Re-initialize T to an empty set.
• 11: else
• 12: Add xi into T.
• 13: end if
• 14: i := i +1;
• 15: end loop

7 Video-Shot Change Detection Problem

In Section 7.1, we describe the method of constructing valid strangeness for video stream. In Section 7.2, we analyze the martingale test method and motivate using the multiplemartingale test on detecting changes in video stream. In Section 7.3, we compare the multiple martingale test method with alternative video-shot change detection methods.

7.1 Strangeness Measure for Video Stream

We describe the representation and the strangeness measure for the unlabeled video image in this subsection.

Image Representation Using Color and Edge Histograms

The image representations are based on the color and edge histograms. The color histogram is constructed with 4096 bins. [(r/16) ∗ 256 + (g/16) ∗ 16 + b/16] is used to convert RGB values of a pixel into an index, with integer division where r, g and b are red, green and blue values respectively. The edge histogram consists of 36 bins such that a gradient angle is converted into an index by dividing the orientation angle by 10 and rounding to the nearest integer.

To capture local information from an image frame, the image frame is partitioned such that a histogram is constructed for each area partitioned along either the horizontal or the vertical axis. For example, for a 352×240 image, histograms are constructed on 3 areas of 88 × 240 by partitioning along the horizontal axis and 3 areas of 352 × 80 by partitioning along the vertical axis. Using this construction, we have two image representations: one consisting of six color histograms, Rcc = {H1 c ,H2 c ,H3 c ,H4 c ,H5 c ,H6 c }, and one consisting of six edge histograms, Ree = {H1 e , H2 e , H3 e , H4 e , H5 e , H6 e }. The two image representations are used as the two views in Algorithm 1.

Strangeness Measure of the Image Representations, Rcc and Ree

Consider the set of image representations, i.e. Z = {R1, · · · , R(n-1)} and a new image representation Rn in the form of either Rcc or Ree. First, we define

which contains the maximum value for each bin in the histograms of the image representation.

We note that as the number of observed image frames increases, ||Ω||, where || · || is some distance measure, is monotonically increasing. Ω ensures that the cluster center will maintain information from previously observed image frames and not be affected by a small drift in image content when a new image frame is observed. The effect of a small drift in image content is significant when the mean, median or minimum value is used. Ω assumes the role of the cluster center for the images.

We are interested in the difference between the image representation Ri, i = 1, · · · , n and Ω. Using the Euclidean norm, the strangeness value for Ri is

This strangeness measure is valid for an image representation Ri in the form of either Rcc or Ree as it satisfies the assumption in Section 3. The set of computed strangeness values {s1, · · · , sn} for Ri, i = 1, · · · , n is used to compute the pvalue of Rn using (3).

7.2 Characteristics of the Martingale Method for Video Stream

Consider the example shown in Figure 3, we use the image representation Rcc and the threshold value λ = 10 to demonstrate some characteristics of the martingale method.

The characteristic of Ωc (for color histogram representation, Rcc) is shown in Figure 4. The shot change is detected at Frame 158 and all previous information is removed from the memory. Unlike labeled data stream where the data-generating process changes at some particular time instances [Ho, 2005; Ho and Wechsler, 2005b], the unlabeled video sequence is usually non-stationary, with constant small changes. The "cluster" representation Ωc should be either (i)

insensitive to small changes or (ii) maintain most information from the previously observed data. Ωc satisfies the two criteria.

We perform the Kolmogorov-Smirnov test (KS-Test) to see whether the p-values computed using (3) is uniformly distributed when the video content is nearly stationary. This important property of p-values computed using (3) does not hold when the video sequence no longer satisfies the exchangeability condition. The mean of the p-values lowers and the martingale values start to increase. In this experiment, we perform the martingale method without reacting to shot change detected, removing data points and resetting variables. In Figure 5, we observed that with high confidence (based on p-values obtained from the KS-Test) the p-values computed using (3) is uniformly distributed before Frame 163. After Frame 163, the p-values are no longer uniformly distributed at 0.05 significance level.

In Figure 6, we show the martingale values computed using the color feature, Rcc and the edge feature, Ree. One notes that for this particular example shown in Figure 3, the edge feature is more sensitive than the color feature. The martingale values computed using the edge feature increase faster and higher than the ones computed using the color feature near the image frame where the change occurs. Hence, by using the multiple-martingale test with 2 views, the number of image frames observed before detecting the change point is lowered. Hence, the sensitivity of the martingale method can be increased using multiple views.

7.3 Comparison with Alternative Methods

Experiments were performed to compare the multiplemartingale test with alternative methods. Four sets of videos, consisting of two documentary video streams (anni, ugs) 1 and two video streams from hand-held digital video camera (outdoor, indoor), are used. The "anni" video stream consists of 9 shots and 8 gradual transitions between shots. The "ugs" video stream consists of 13 shots with some fast transitions and moving camera. The "outdoor" and "indoor" video streams consist of continuous changes due to the motion of the camera. The two video streams are captured from the top of a hill and from an apartment, respectively.

The performance of the methods is measured based on the number of detections, miss detections and false detections. They are summarized using the recall, precision and the F1 measure:

Precision is the probability that a detection is actually correct, i.e. detecting a true change. Recall is the probability that a change detection system recognizes a true change. F1 measure represents a harmonic mean between recall and precision. A high value of F1 measure ensures that the precision and recall are reasonably high.

In the experiment, we use λ = 20 which corresponds to the fact that the computed martingale values are unlikely to be higher than 20 with probability bound of 0.05 if no change occurs. We compare the multiple-martingale test (MT (20)) with the alternative methods. For the alternative methods, the color histogram is used as the image representation and the local threshold is selected based on window averaging [Gargi et al., 2000] on three similarity measures: histogram intersection (HI), chi-square measure (χ2 ) and Euclidean distance (ED), to measure the similarity between any two image frames for all the image frames in a video sequence. The parameters, such as the window size, are varied so that the best results can be obtained from the alternative methods. The experimental results on the four video sequences are shown in Table 1.

1 The documentary videos can be obtained freely from http://www.open-video.org

Based on the F1 measure, the multiple-martingale test performed the best three out of the four video sequences. The main difference between the alternative methods and ours is the fact that our threshold is chosen a prior with theoretical consideration while the thresholds selected by the alternative methods are heuristics such that the window size and other parameters need to be tuned to achieve good result. Moreover, the martingale method is a one-pass algorithm while the alternative methods are not.

8 Conclusions

In this paper, we extend the martingale methodology [Ho, 2005] to be used on unlabeled data. We also proposed the multiplemartingale test based on building different martingales using multiple views (features) to enhance the performance of the martingale methodology. We apply this multiple martingale test method to the video-shot change detection and show that it compares favorably with alternative methods.