change detection

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.

EDIT:

Ultimate goal

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

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

Consider how an algorithm might detect a change. You're observing instances of some random variable, $X_1,X_2,\dots,X_{k-1}$. Suddenly (and unknown to you) at $X_k$ something about the distribution of $X$ changes. Now your observations $X_k,\dots,X_n$ are different in some way. You want to know what $k$ is based on your observations alone.

In order to detect the change, you have to have some idea of what 'before' might look like so you can have confidence that 'after' is really different. So, yes, all change detection algorithms will use some run length before and after the true change to make a decision (edit: actually, you don't need run length before and after, you could just have an assumption about the data-generating process. Maybe you say its normal mean 0 variance 1 and your first observation is 5000, you don't need run length to know you're wrong somewhere). Anything else would be an even wilder kind of predicting the future.

It seems like the real concern might be the latency of signal detection. You'd like the sensor to detect it after just a few instances of the data after the true change point.

So my question is, do you really need it to work now? It seems reasonable to me that you're not interested in the number of data points, but the time it takes to gather them. If you have a sensor that updates 100,000 times a second, 100 data points isn't a huge deal.

Answer 2

You can calculate the confidence interval for the current distance R based on a sliding window approach and immediately signal if the next reading D falls out of that interval.

Answer 3

Here is a pretty extensive guide on change/anomaly detection in time series: "Anomaly Detection of Time Series", a masters thesis by Deepthi Cheboli.

You can start from the simple parametric approaches that have been mentioned before, but I want to let you know that there is an actual methodology devoted to this exact problem, which is very easy to build and use.

The name of your problem is novelty detection, and the perfect tool to handle it without any burn-in data, is called One-Class Support Vector Machines.

What it does is it learns from the single class, and checks any test cases against the learned single group to see if it is different than what it is used to seeing.

I guess this is what you are trying to do. You are avoiding sacrificing any time or data points after the change happens. If you were fine with burning in some data after the change, and build a "classification" (with an abuse of the term) approach, then you didn't have to go the one-class SVM way. If you believe the time-series that you currently have has a good behavior, and anything that doesn't look like it should be immediately detected, then one-class SVM it is.

This model is implemented in R, Python, Matlab, and I am sure many other platforms, so depending on which program you use, I'd recommend giving it a try.