Power martingales for change detection: M goes to zero?

Question

I'm trying to apply the power martingale framework by [Vovk et al., 2003] to change detection in unlabeled data streams, just like in [Ho and Wechsler, 2007]. The basic idea involves using a power martingale of the form $$M_n^{(\epsilon)} := \prod_{i=1}^n\left(\epsilon p_i^{\epsilon-1}\right) = \epsilon p_n^{\epsilon-1} M_{n-1}^{(\epsilon)}.$$ If I understand the method correctly, it is supposed to work as follows:

• $p_i$ are p-values of some input sequence that are distributed uniformly on $[0,1]$ when the sequence is exchangeable;
• when exchangeability is violated, $p_i$ become smaller, and $M_n$ starts to grow;
• when $M_n$ has grown to some threshold or the difference between neighboring $M_n$ has exceeded some threshold, we ring the alarm that some change has occurred and start over.

Looks very simple, but I couldn't get it to work: on my data, the values of $M_n$ did oscillate randomly for a while but very soon dropped to zero (to values like 1e-100) an stayed there; there were some large factors when actual change occurred in the data, but it would take a lot of factors to return from 1e-100...

I tried a simple test: generated uniformly distributed $p_i$ and computed $M_n$ for them. Here is the complete python code of my test ($\epsilon=0.92$ is a suggested value from the papers, but I've tried other $\epsilon$ with similar results):

epsilon = 0.92
pv_test = [random.random() for _ in xrange(5000)]
test_mult = [epsilon * (x ** (epsilon - 1)) for x in pv_test]
Mtest = [1]
for i in xrange(len(test_mult)):
    Mtest.append(Mtest[i] * test_mult[i])

And I observed the very same behaviour: $M_n$ always dropped to zero! Sometimes faster, sometimes slower, but always. Here are some sample graphs of $M_n$:

It does look like a random walk, but it always eventually drops to zero even for perfectly uniform p-values. This obviously will not work for change detection because even a relatively long sequence of small p-values cannot resurrect $M_n$ from 1e-100.

So my question is: what am I doing wrong?..

Answer 1

Your implementation is correct. The power martingale tends to get very small (closer to 0) when p-values are uniformly distributed. To avoid that, you just need to restart your martingale from 1 as soon as it gets smaller than 1. So just add:

Mtest[i] = max(Mtest[i], 1)

This will keep your martingale small (but not less than 1) when the p-values are uniformly distributed, even for a long period.

Answer 2

I think you can see the nature of the problem if you calculate how many "strange" data points you need, given that you've observed a long run of "not-strange" data points (using the language of Ho and Wechsler here).

Let's do some back-of-the-envelope calculations: for a stream of $k$ data points with constant $p_i = p$ then $M_k \sim 10^{k(\text{log}_{10}(\epsilon) + (\epsilon-1) \text{log}_{10}(p))}$. Let's say that after a number $n$ of non-strange data points with $p_i = .5$ (the expected value of a uniform RV over $[0,1]$), we get a stream of $\eta$ strange events with $p_i \sim 10^{-3}$. We then ask "how big does $\eta$ have to be before $M_{n+\eta} \sim 10$?" (the threshold given in Ho and Wechsler).

If we use $\epsilon = .92$ then after the not-strange data stream ($n$ points with $p_i=.5$) we have that $M_n \sim 10^{-.012n}$. Abusing notation a little let's denote the "contribution" of the surprising data stream to be $M_{\eta}$ (so $M_{n+\eta} = M_n M_{\eta}$), we can then calculate that $M_{\eta} = 10^{.204 \eta}$. Given the threshold of $10$ we want $M_{n+\eta} = 10^{.204\eta - .012n} = 10$ or $.204\eta - .012n = 1$, hence $\eta = \frac{1+.012n}{.204} \approx 5 + .06 n$. What this means is that $\eta$ needs to be around 6% of $n$ if we're going to pass the threshold of 10.

Obviously this is only a rough calculation, but I think it presents a clear intuition of the problem: this martingale method is robust against short runs of surprising data. The more unsurprising data you have, the more surprising data you will need before it concludes that a change has occurred. Because you're feeding it 5000 not-strange observations, you'll need around 300 pretty strange ones to convince it that a change has occurred. Note that in Ho and Wechsler they seem to be feeding in surprising data every 1000 data points, with means that they only need around 60 surprising data points.

Answer 3

In my opinion you don't understand change concept. Try to do this:

1. You must implement a dataset with at least 2 clusters with n-dimension vectors (for a test is better 2-dimesion).
2. Your code must reads one-to-one all the dates from cluster #1. When your code starts to read dates from cluster #2 your martigale must detect a change.

About the algorithm. You need to implement (all the reference are on Ho & Wechler paper):

1. Strangeness measure. I'd try to implement Cluster Model (formula 7). Calculate all the dates mean read until that moment (cluster centroid). Following you need to calculate the euclidean distance for each point read until that moment from the centroid.
2. P-value function (formula 7). Strangeness measure is an input for this formula.
3. Introduce each p-value in Martingale.
4. You must define a Lambda value to trigger an change alarm.