Change point identification

Question

I have a question related to change detection. Application domain is robotics/planning.

Background/setting:

There is a sensor detecting distance from obstacle (ultrasonic / sonar sensor) at a specific position (x, y, theta) in the environment.

It returns some reading at regular time intervals. Lets say the reading is R and over a period of time it records R+ or R- (+/- means variation due to sensor inaccuracies).

Case 1: I introduce an additional object between the sensor and the obstacle at a distance D (D < R) so that at the next instance D is detected and returned

Case 2: I remove the original obstacle and now the next obstacle is D' (D' > R) and at the next instance D' is returned.

Question

Is there a way to exactly (or with high probability) say that a changed occurred NOW (when I add or remove an obstacle)?

Most change analysis algorithms consider a run length before change point and some data after change point and indicate the position change occurred.

But none I have read so far say change happened NOW; even the "online" algorithms seem to need some burn in data.

Ultimate goal

I want to implement a method that takes the data vector and return if the latest data point was a change point.

EDIT:

Adding some sample data

Here is a sample set of readings from a trial run:

[4.246904919227158, 4.063425344645503, 3.8522606458184168, 4.089331294361679, 4.227116239146714, 4.1902677894197256, 4.2114944818819655, 3.8056165437493474, 3.856400573638567, 4.010168749304731, 3.9006359327215225, 4.228516948802346, 3.345646289458722, 3.9652605551178945, 3.887277610253342, 4.03333576199138, 4.080046765134659, 4.056694343861694, 4.071850586980991, 4.100334404631286, 3.9658145837839665, 4.123166010661199, 3.8648499221011803, 4.2663999562925925, 4.093156431199762, 4.030454419556623, 4.150180573287889, 4.036968026040318, 3.968487007085925, 4.0230405601135795, 3.8041071703789893, 3.969994970247766, 4.041273183800564, 3.9044735289368897, 3.9436795221011653, 4.31314266597137, 4.086383240385605, 4.058007914552306, 4.07536832934258, 3.992830928581128, 1.992831838099113]

As you can see, the first 40 values have a mean of 4 the last one has a mean of 2.

EDIT 2:

A possible Solution/hack

Since my work involves streaming data, this is the approach I am currently taking.

1. Read a window of data (for now, my window size is 20 values) from the end of the stream.
2. Run bcp (from R) on this window.
3. Check for the posterior probability of the change at location 18. (for all the runs i just had, the last value is NA, hence ignore that, and the data is zero indexed, (calling R from Python using rpy2), hence, the position turns out 18 for window size of 20.
4. Set a threshold of 70% for the posterior probability (for now in my experimental setting this works fine, I may have to work on getting a proper threshold later)
5. If the posterior probability at location 18 > 70%, I return TRUE indicating the recent data point has a different mean, or "change detected", else return FALSE.

This may not be the most efficient way of doing it, but it is doing its job for now. I am using this approach to carry my work forward.

I will update the thread if I find a better approach.

Thanks you all for the help!

Answer 1

This is an interesting question. In essence the answer will come down to what assumptions you are making and how large the change you record is. If the change is large enough then you will see it immediately. For example, using the changepoint package in the statistical software 'R':

library(changepoint) set.seed(10) cpts(cpt.mean(c(rnorm(50),10),method='PELT'))

Here we have simulated 50 data points from a Normal distribution with mean 0 and variance 1 then added a 10 at the end as our "new" data point, maybe an example of removing an object. The cpt.mean function is for detecting changes in mean and defaults to a Normal distribution assumption. I have then put cpts() around it so only the changes are returned.

The above correctly identifies the change as being at time 50, i.e. the last data point is from a new regime. This is identified as the new data point is very different from the existing data.

In essence (when using distributional assumptions) if the new data point is within the expected range of the distribution (in this case you expect to see a value of 3 or above roughly once every thousand observations and a value of 10 or above is within machine precision of 0) then a change won't be signalled immediately. It may be that your change is too small to be able to detect with a single data point (or that your assumptions mean this is so).

Answer 2

Identifying whether or not the last observation is significantly different from expectations requires expectations. I have the following mission statement for AUTOBOX (available in a R Version), a piece of software that I have helped to develop. Other vendors like SAS, SPSS offer some capability in this area of expertise.

"To do science is to search for repeated patterns.
To detect anomalies is to identify values that do not follow repeated patterns. For whoever knows the ways of Nature will more easily notice her deviations
and, on the other hand, whoever knows her deviations will more accurately
describe her ways. (Francis Bacon)

One learns the rules by observing when the current rules fail.

Can you tell me the probability that a single data point (e.g. the latest
reading) came from the distribution represented by all the previous data points? "

There are free R based solutions which attempt to do the same thing but if you have supporting variables or if you have data that has parameters or error variance that changes over time you might need to upgrade.

The general solution (Intervention Detection ) requires combining both appropriate memory (ARIMA) and any needed trend/level changes in an artful way that doesn't assume that you treat memory first.

If you wish to post some of your real data I will try and demonstrate this to you.

EDITED: After receipt of data

Your data suggested an ARIMA model of the form [ . The residuals from this model suggested three anomalies with period 41 being overwhelmingly dominant . Upon incorporating these three pulses the "new residuals" from this augmented model suggest a possible non-constant error process which is another assumption of the changepoint software recommended by @Aduniac. The results of the test are shown here and here . This test was developed by Tsay in 1988 http://onlinelibrary.wiley.com/doi/10.1002/for.3980070102/abstract but has largely been ignored by software developers ( but not all ! ). The final model is here .

In summary if your data looks like this then perhaps simple tools like changepoint might be sufficient. On the other hand if your data exhibits more complex structure than white noise you should stay way clear of simple approaches as they can often mislead. Somebody ( Einstein, Tukey or Box) once opined "Make things as complex as needed but not too complex". Hope this helps.

Answer 3

My advice is to construct a model which describes how the world works, including how the world affects sensors, and then use that model to infer the world state from sensor observations. It doesn't have to be grandiose: your world comprises just some objects. But you do have to think about how the objects come and go and how the sensor reacts to them. Is it possible that the objects can sometimes move slowly relative to the sensor reading interval? Is it possible that orientation of objects changes the sensor reading? Is is possible that objects can be different sizes? Does the sensor have any physical persistence, i.e. does the reading now depend on the reading 1 second ago? What kind of reading do you get when the sensor is malfunctioning? Etc etc.

When you go through this exercise, you will come up with an inferential method which is exactly suited to your problem in the sense that it takes all of the assumptions you have identified into account. You might have to cut some corners and make simplifying assumptions in some cases. That's OK, do whatever you need to do, but at least you know where and how your model diverges from reality.