{'fraction_non_alphanumeric': 0.04038984587488667, 'fraction_numerical': 0.011876699909338168, 'mean_word_length': 4.232685009487666, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Plug-in martingales for testing exchangeability on-line

A standard assumption in machine learning is the exchangeability of data, which is equivalent to assuming that the examples are generated from the same probability distribution independently. This paper is devoted to testing the assumption of exchangeability on-line: the examples arrive one by one, and after receiving each example we would like to have a valid measure of the degree to which the assumption of exchangeability has been falsified. Such measures are provided by exchangeability martingales. We extend known techniques for constructing exchangeability martingales and show that our new method is competitive with the martingales introduced before. Finally we investigate the performance of our testing method on two benchmark datasets, USPS and Statlog Satellite data; for the former, the known techniques give satisfactory results, but for the latter our new more flexible method becomes necessary.


Introduction
Many machine learning algorithms have been developed to deal with real-life high dimensional data. In order to state and prove properties of such algorithms it is standard to assume that the data satisfy the exchangeability assumption (although some algorithms make different assumptions or, in the case of prediction with expert advice, do not make any statistical assumptions at all). These properties can be violated if the assumption is not satisfied, which makes it important to test the data for satisfying it.
Note that the popular assumption that the data is i.i.d. (independent and identically distributed) has the same meaning for testing as the exchangeability assumption. A joint distribution of an infinite sequence of examples is exchangeable if it is invariant w.r. to any permutation of examples. Hence if the data is i.i.d., its distribution is exchangeable. On the other hand, by de Finetti's theorem (see, e.g., Schervish, 1995, p. 28) any exchangeable distribution on the data (a potentially infinite sequence of examples) is a mixture of distributions under which the data is i.i.d. Therefore, testing for exchangeability is equivalent to testing for being i.i.d.
Traditional statistical approaches to testing are inappropriate for high dimensional data (see, e.g., Vapnik, 1998, pp. 6-7). To address this challenge a previous study (Vovk et al., 2003) suggested a way of on-line testing by employing the theory of conformal prediction and calculating exchangeability martingales. Basically testing proceeds in two steps. The first step is implemented by a conformal predictor that outputs a sequence of p-values. The sequence is generated in the on-line mode: examples are presented one by one and for each new example a p-value is calculated from this and all the previous examples. For the second step the authors introduced exchangeability martingales that are functions of the p-values and track the deviation from the assumption. Once the martingale grows up to a large value (20 and 100 are convenient rules of thumb) the exchangeability assumption can be rejected for the data. This paper proposes a new way of constructing martingales in the second step of testing. To construct an exchangeability martingale based on the sequence of p-values we need a betting function, which determines the contribution of a p-value to the value of the martingale. In contrast to the previous studies that use a fixed betting function the new martingale tunes its betting function to the sequence to detect any deviation from arXiv:1204.3251v2 [cs.LG] 28 Jun 2012 the assumption. We show that this martingale, which we call a plug-in martingale, is competitive with all the martingales covered by the previous studies; namely, asymptotically the former grows faster than the latter.

Related work
The first procedure of testing exchangeability on-line is described in Vovk et al. (2003). The core testing mechanism is an exchangeability martingale. Exchangeability martingales are constructed using a sequence of p-values. The algorithm for generating p-values assigns small p-values to unusual examples. It implies the idea of designing martingales that would have a large value if too many small p-values were generated, and suggests corresponding power martingales. Other martingales (simple mixture and sleepy jumper) implement more complicated strategies, but follow the same idea of scoring on small p-values.
Ho (2005) applies power martingales to the problem of change detection in time-varying data streams. The author shows that small p-values inflate the martingale values and suggests to use the martingale difference as another test for the problem.

This paper
To the best of our knowledge, no study has aimed to find any other ways of translating p-values into a martingale value. In this paper we propose a new more flexible method of constructing exchangeability martingales for a given sequence of p-values.
The rest of the paper is organised as follows. Section 2 gives the definition of exchangeability martingales. Section 3 presents the construction of plug-in exchangeability martingales, explains the rationale behind them, and compares them to the power martingales, which have been used previously. Section 4 shows experimental results of testing two real-life datasets for exchangeability; for one of these datasets power martingales work satisfactorily and for the other one the greater flexibility of plug-in martingales becomes essential. Section 5 summarises the paper.

Exchangeability martingales
This section outlines necessary definitions and results of the previous studies.

Exchangeability
Consider a sequence of random variables Z 1 , Z 2 , . . .) that all take values in the same example space. Then the joint probability distribution P(Z 1 , . . . , Z N ) of a finite number of the random variables is exchangeable if it is invariant under any permutation of the random variables. The joint distribution of infinite number of random variables Z 1 , Z 2 , . . .) is exchangeable if the marginal distribution P(Z 1 , . . . , Z N ) is exchangeable for every N .

Martingales for testing
As in Vovk et al. (2003), the main tool for testing exchangeability on-line is a martingale. The value of the martingale reflects the strength of evidence against the exchangeability assumption. An exchangeability martingale is a sequence of non-negative random variables S 0 , S 1 , . . . that keep the conditional expectation: where E refers to the expected value with respect to any exchangeable distribution on examples. We also assume S 0 = 1. Note that we will obtain an equivalent definition if we replace "any exchangeable distribution on examples" by "any distribution under which the examples are i.i.d." (remember the discussion of de Finetti's theorem in Section 1).
To understand the idea behind martingale testing we can imagine a game where a player starts from the capital of 1, places bets on the outcomes of a sequence of events, and never risks bankruptcy. Then a martingale corresponds to a strategy of the player, and its value reflects the acquired capital. According to Ville's inequality (see Ville, 1939, p. 100), P ∃n : S n ≥ C ≤ 1/C, ∀C ≥ 1, it is unlikely for any S n to have a large value. For the problem of testing exchangeability, if the final value of a martingale is large then the exchangeability assumption for the data can be rejected with the corresponding probability.

On-line calculation of p-values
Let (z 1 , z 2 , . . .) denote a sequence of examples. Each example z i is the vector representing a set of attributes x i and a label y i : z i = (x i , y i ). In this paper we use conformal predictors to generate a sequence of p-values that corresponds to the given examples. The general idea of conformal prediction is to test how well a new example fits to the previously observed examples. For this purpose a "nonconformity measure" is defined. This is a function that estimates the strangeness of one example with respect to others:

Algorithm 1 Generating p-values on-line
Input: (z 1 , z 2 , . . .) data for testing Output: (p 1 , p 2 , . . .) sequence of p-values where in general {. . .} stands for a multiset (the same element may be repeated more than once) rather than a set. Typically, each example is assigned a "nonconformity score" α i based on some prediction method. In this paper we deal with the classification problem and the 1-Nearest Neighbor (1-NN) algorithm is used as the underling method to compute the nonconformity scores. The algorithm is simple but it works well enough in many cases (see, e.g., Hastie et al., 2001, pp. 422-427).
A natural way to define the nonconformity score of an example is by comparing its distance to the examples with the same label to its distance to the examples with a different label: where d(x i , x j ) is the Euclidean distance. According to the chosen nonconformity measure, α i is high if the example is close to another example with a different label and far from any examples with the same label.
Using the calculated nonconformity scores of all observed examples, the p-value p n that corresponds to an example z n is calculated as where θ n is a random number from [0, 1] and the symbol # means the cardinality of a set. Algorithm 1 summarises the process of on-line calculation of p-values (it is clear that it can also be applied to a finite dataset (z 1 , . . . , z n ) producing a finite sequence (p 1 , . . . , p n ) of p-values).
The following is a standard result in the theory of conformal prediction (see, e.g., Vovk et al. 2003, Theorem 1).
The property that the examples generated by an exchangeable distribution provide uniformly and independently distributed p-values allows us to test exchangeability by calculating martingales as functions of the p-values.

Martingales based on p-values
This section focuses on the second part of testing: given the sequence of p-values a martingale is calculated as a function of the p-values.
. .) be the sequence of p-values generated by Algorithm 1. We consider martingales S n of the form where we denote f i (p) = f i (p 1 , . . . , p i−1 , p) and call the function f i (p) a betting function.
To be sure that (2) is indeed a martingale we need the following constraint on the betting functions f i : Then we can check: Using representation (2) we can update the martingale on-line: having calculated a p-value p i for a new example in Algorithm 1 the current martingale value becomes S i = S i−1 · f i (p i ). To define the martingales completely we need to describe the betting functions f i .

Previous results: power and simple mixture martingales
Previous studies (Vovk et al., 2003) have proposed to use a fixed betting function where ε ∈ [0, 1]. Several martingales were constructed using the function. The power martingale for some ε, denoted as M ε n , is defined as The simple mixture martingale, denoted as M n , is the mixture of power martingales over different ε ∈ [0, 1]: Such a martingale will grow only if there are many small p-values in the sequence. This follows from the shape of the betting functions: see Figure 1. If the generated p-values concentrate in any other part of the unit interval, we cannot expect the martingale to grow. So it might be difficult to reject the assumption of exchangeability for such sequences.

Plug-in martingale
Let us use an estimated probability density function as the betting function f i (p). At each step the probability density function is estimated using the accumulated p-values: where ρ(p 1 , . . . , p i−1 , p) is the estimate of the probability density function using the p-values p 1 , . . . , p i−1 output by Algorithm 1.
Substituting these betting functions into (2) we get a new martingale that we call a plug-in martingale. The martingale avoids betting if the p-values are distributed uniformly, but if there is any peak it will be used for betting.
Estimating a probability density function. In our experiments we have used the statistical environment and language R. The density function in its Stats package implements kernel density estimation with different parameters. But since p-values always lie in the unit interval, the standard methods of kernel density estimation lead to poor results for the points that are near the boundary. To get better results for the boundary points the sequence of p-values is reflected to the left from zero and to the right from one. Then the kernel density estimate is calculated using the extended sample ∪ n i=1 −p i , p i , 2 − p i . The estimated density function is set to zero outside the unit interval and then normalised to integrate to one. For the results presented in this paper the parameters used are the Gaussian kernel and Silverman's "rule of thumb" for bandwidth selection. Other settings have been tried as well, but the results are comparable and lead to the same conclusions.
The values S n of the plug-in martingale can be updated recursively. Suppose computing the nonconformity scores (α 1 , . . . , α n ) from (z 1 , . . . , z n ) takes time g(n) and evaluating (3) takes time h(n). Then updating S n−1 to S n takes time O(g(n) + n + h(n)): indeed, it is easy to see that calculating the rank of α n in the multiset {α 1 , . . . , α n } takes time Θ(n).
The performance of the plug-in martingale on real-life datasets will be presented in Section 4. The rest of the current section proves that the plug-in martingale provides asymptotically a better growth rate than any martingale with a fixed betting function. To prove this asymptotical property of the plug-in martingale we need the following assumptions.

Assumptions
Consider an infinite sequence of p-values (p 1 , p 2 , . . .). (This is simply a deterministic sequence.) For its finite prefix (p 1 , . . . , p n ) define the corresponding empirical probability measure P n : for a Borel set A in R, P n (A) = #{i = 1, . . . , n : p i ∈ A} n .
We say that the sequence (p 1 , p 2 , . . .) is stable if there exists a probability measure P on R such that: 2. there exists a positive continuous density function ρ(p) for P: for any Borel set A in R, P(A) = A ρ(p)dp.
Intuitively, the stability means that asymptotically the sequence of p-values can be described well by a probability distribution.
Consider a sequence (f 1 (p), f 2 (p), . . .) of betting functions. (This is simply a deterministic sequence of functions f i : [0, 1] → [0, ∞), although we are particularly interested in the functions f i (p) = ρ i (p), as defined in (3).) We say that this sequence is consistent for Intuitively, consistency is an assumption about the algorithm that we use to estimate the function ρ(p); in the limit we want a good approximation.

Growth rate of plug-in martingale
The following result says that, under our assumptions, the logarithmic growth rate of the plug-in martingale is better than that of any martingale with a fixed betting function (remember that by a betting function we mean any function mapping [0, 1] to [0, ∞)).
Theorem 2. If a sequence (p 1 , p 2 , . . .) ∈ [0, 1] ∞ is stable and a sequence of betting functions f 1 (p), f 2 (p), . . . is consistent for it then, for any positive continuous betting function f , First we explain the meaning of Theorem 2 and then prove it. According to representation (2) after n steps the martingale grows to Note that if for any p-value p ∈ [0, 1] we have f i (p) = 0 then the martingale can become zero and will never change after that. Therefore, it is reasonable to consider positive f i (p). Then we can rewrite product (4) as sum of logarithms, which gives us the logarithmic growth of the martingale: We assume that the sequence of p-values is stable and the sequence of estimated probability density functions that is used to construct the plug-in martingale is consistent. Then the limit inequality from Theorem 2 states that the logarithmic growth rate of the plug-in martingale is asymptotically at least as high as that of any martingale with a fixed betting function (which have been suggested in previous studies).
To prove Theorem 2 we will use the following lemma.
Proof of Lemma 1. It is well known (Kullback, 1959, p. 14) that the Kullback-Leibler divergence is always non-negative: This is equivalent to the inequality asserted by Lemma 1.

Substituting the definition of ρ(p) into Lemma 1 we obtain
From the stability of (p 1 , p 2 , . . .) it follows that there exists a number N 1 = N 1 (ε) such that, for all n > N 1 , log ρ(p) dP < ε.
Then inequality (6) implies that, for all n ≥ N 1 , By the definition of the probability measure P n , the last inequality is the same thing as By the consistency of f 1 (p), f 2 (p), . . . there exists a number N 2 = N 2 (ε) such that, for all i > N 2 and all p ∈ [0, 1], Let us define the number From (8) and (9) we have Denote N 3 = max (N 1 , N 2 ). Then, using (10) and (7), we obtain, for all n > N 3 , Denoting N 4 = max(N 3 , M N3 ε ), we can rewrite the last inequality as for all n > N 4 . Finally, recalling that ε < δ 4 , we have, for all n > N 4 , This contradicts (5) and therefore completes the proof of Theorem 2.

Empirical results
In this section we investigate the performance of our plug-in martingale and compare it with that of the simple mixture martingale. Two real-life datasets have been tested for exchangeability: the USPS dataset and the Statlog Satellite dataset.  (Vovk et al., 2003), and any reasonable test should reject exchangeability there.
In our experiments we merge the training and test sets and perform testing for the full dataset of 9298 examples.  The p-values are generated on-line by Algorithm 1 and the two martingales are calculated from the same sequence of p-values. The final value for the simple mixture martingale is 2.0 × 10 10 , and the final value for the plug-in martingale is 3.9 × 10 8 . Figure 6 shows the betting functions that correspond to the plug-in martingale and the "best" power martingale. For the plug-in martingale, the function is the estimated probability density function calculated using the whole sequence of p-values. The betting function for the family of power martingale corresponds to the parameter ε * that provides the largest final value among all power martingales. It gives a clue why we could not see advantages of the new approach for this dataset: both martingales grew up to approximately the same level. There is not much difference between the best betting functions for the old and new methods, and the new method suffers because of its greater flexibility.

Statlog Satellite dataset
Data The Statlog Satellite dataset (Frank & Asuncion, 2010)  values in different spectral bands. Each example is represented by 36 attributes and a label indicating the classification of the central pixel. Labels are numbers from 1 to 7, excluding 6. The testing results are described below. Figure 3 shows the performance of the martingales for randomly shuffled examples of the dataset. As expected, the martingales do not reject the exchangeability assumption there. Figure 5 presents the performance of the martingales when the examples arrive in the original order. The final value for the simple mixture martingale is 5.6×10 2 and the final value for the plug-in martingale is 1.8 × 10 17 . Again, the corresponding betting functions for the plug-in martingale and the "best" power martingale are presented in Figure 7. For this dataset the generated p-values have a tricky distribution. The family of power betting functions εp ε−1 cannot provide a good approximation. The power martingales lose on p-values close to the second peak of the p-values distribution. But the plug-in martingale is more flexible and ends up with a much higher final value.
It can be argued that both methods, old and new, work for the Statlog Satellite dataset in the sense of rejecting the exchangeability assumption at any of the commonly used thresholds (such as 20 or 100). However

Discussion and conclusions
In this paper we have introduced a new way of constructing martingales for testing exchangeability online. We have shown that for stable sequences of p-values the new more adaptive martingale provides asymptotically the best result compared with any other martingale with a fixed betting function. The experiments of testing two real-life datasets have been presented. Using the same sequence of p-values the plug-in martingale extracts approximately the same amount or more information about the data-generating distribution as compared to the previously introduced power martingales.
Remark. The previous studies were based on the natural idea that lack of exchangeability leads to new examples looking strange as compared to the old ones and therefore to small p-values (for example, if the datagenerating mechanism changes its regime and starts producing a different kind of examples). This is, however, a situation where lack of exchangeability makes the p-values cluster around 1: we observe examples that are ideal shapes of several kinds distorted by random noise, and the amount of noise decreases with time. Predicting the kind of a new example using the nonconformity measure (1) will then tend to produce large p-values.
Our goal has been to find an exchangeability martingale that does not need any assumptions about the p-values generated by the method of conformal prediction. Our proposed martingale adapts to the unknown distribution of the p-values by estimating a good bet- ting function from the past data. This is an example of the plug-in approach. It is generally believed that the Bayesian approach is more efficient than the plug-in approach (see, e.g., Bernardo & Smith, 2000, p. 483). In our present context, the Bayesian approach would involve choosing a prior distribution on the betting functions and integrating the exchangeability martingales corresponding to these betting functions over the prior distribution. It is not clear yet whether this can be done efficiently and, if yes, whether this can improve the performance of exchangeability martingales.