Adaptive Support Vector Machine for Time-Varying Data Streams Using Martingale

1 Introduction

In this paper we propose an efficient adaptive support vector machine (SVM) for time-varying data streams based on the martingale approach [Vovk et al., 2003] and using adiabatic incremental learning [Cauwenberghs and Poggio, 2000]. When a new data point is observed, hypothesis testing decides whether any change has occurred. Once a change is detected, historical information about previous data is removed from the memory.

2 Change Detection UsingMartingale

[Vovk et al., 2003] introduced the idea of testing exchangeability online using martingale. The sequence of random variables z1, · · · , zn is exchangeable if the joint distribution p(z1, · · · , zn) is invariant under any permutation of the indices of the random variables. When a new labeled example, zn, is observed, testing exchangeability of the sequence of examples z1, z2, · · · , zn consists of two main steps [Vovk et al., 2003]:

1. Extract the randomized p-value for zn:

where αi is the strangeness measure (for SVM, one can use either the Lagrange multipliers or the distances from the hyperplane) for zi, i = 1, 2, · · · , n and θn is a random number between 0 and 1.

1. Construct the randomized martingale:

where pi are p-values, a constant ϵ ∈ [0, 1], and the initial martingale M (ϵ) 1 = 1.

pi andM (ϵ) i , for i = 2, · · · , n-1, are computed using Step 1 and 2.

The exchangeability of a data sequence is a slightly weaker assumption compared to the randomness (i.i.d.) assumption. Hypothesis testing using the randomized martingale is suitable to check for the randomness of a data sequence which, in turn, can detect changes.

One tests the null hypothesis H0 : "no change in the data stream" against the alternative hypothesis H1 : "change in the data stream". The martingale test continues as long as

One rejects the null hypothesis when M (ϵ) n ≥ λ.

The martingale test is justified using the Doob's Maximal Inequality [Steele, 2001] which states that for a martingale {Mk} and any λ > 0,

Hence, if E(Mn) = E(M1) = 1, then

This inequality means that it is unlikely for Mn to have a high value. Based on this inequality, λ is appropriately set to reject the null hypothesis.

3 Experiments

Experiments are first conducted on a binary-class twodimensional rotating hyperplane data stream [Hulten et al., 2001]. To show the performance of the adaptive SVM on high dimensional multi-class data stream, experiments are carried out using a modified three-digit data stream based on the USPS handwritten digit dataset [LeCun et al., 1989]. For the SVMs, C = 10 and the Gaussian kernel are used.

A. 2-D Rotating Hyperplane Synthetic Dataset

For the two-dimensional rotating hyperplane data stream, the sequence consists of 16,000 data points with changes in the data distribution occurring at points (1000 × i) + 1, for i = 1, 2, · · · , 15. For each segment of a steady data distribution, 500 points from the same data distribution are used to assess the performance of the SVM classifier.

The adaptive SVMs using λ = 16, for the martingale test (3), displays very good performance as shown in Figure 1. The difference in accuracy from baseline accuracy (performance of the classifier that adapts to the given true change points) is near zero most of the time. Short bursts of accuracy discrepancy occur between true change points and their corresponding detected change points. Longer accuracy discrepancies happen when a significant change is detected late (e.g. change point 4001) as shown in Figure 1. In Figure 2, we observe that the martingale value is small and stable when no change in the data distribution is detected. The martingale value increases abruptly when change is suspected.

B. Three-digit Data Stream

The USPS handwritten digits dataset, which consists of 10 classes of dimension 256 and includes 7,291 data points, is modified to form a data stream as follows. There are four different data segments. Each segment draws from a fixed set of three different digits in a random fashion. The threedigit set changes from one segment to the next. The composition of the data stream and ground truth for the change points are summarized in Table 1. Ten simulations were performed on the simulated data stream using the one-against-the-rest multi-class SVM and the martingale test with λ = 10.

For the three-class data stream there are three martingale values that have to be computed at each point in order to detect change. When one of the martingale values is greater than λ, the SVMwill detect and adapt to the change. One can see from Figure 3 that the adaptive SVM performs extremely well. About 94% of the data points have a difference from baseline accuracy less than or equal to 1%. There are no miss detections for all the ten simulations.