2
$\begingroup$

I am looking for the name of an algorithm category, or even specific algorithms, that solve the following problem.

I have noisy data. For simplicity, let this data be represented by numbers. I have the full data set in RAM. In this noisy data, I want to find signal. Signal is an interval of contiguous numbers that are close-enough to each other. In other words, their standard deviation is below some threshold. At the same time, I don't trust the signal if it is too short-lived, so it must be at least n contiguous numbers long.

In other words, I want to find non-overlapping intervals of values, where each interval has at least n values, and those values have a standard deviation of at most sd.

The intervals do not need to be contiguous. (Signal is intermittent in all the noise.)

I want to minimize sd in these intervals, so given a choice of one interval with a higher sd or two intervals with a lower sd, I prefer the latter. (As long as both intervals have at least n values, as I said earlier.)

For example, suppose I configure a minimum interval size of 5, and I have the following list:

7, 7, 8, 7, 7, 4, 5, 5, 5, 4, 6, 6

The sd for this whole interval is 1.31. If we split it into

7, 7, 8, 7, 7

then drop the middle 4, and continue to the next interval,

5, 5, 5, 4, 6

then drop the final 6, we get sd of 0.45 and 0.71, which intuitively seems optimal to me.

Had we kept the middle “4” in the second interval, that interval’s sd would have been 0.82. Had we kept the final “6”, that interval’s sd would have been 0.76. We could have decreased sd even further by removing more elements, except intervals in this example must have at least 5 elements.

(Note, I came up with this particular split intuitively, so it may not be the optimal split.)

What algorithm(s) can solve this problem?

$\endgroup$
  • $\begingroup$ Your question looks like interesting. If it comes from an online source, please add a URL in the question. If it comes from a book or a paper, a reference. Besides giving proper credit to the original source, all that information motivates and helps more people answer your question faster and better. $\endgroup$ – Apass.Jack Nov 12 '18 at 20:50
  • $\begingroup$ @Apass.Jack it is not sourced from anywhere. I have an idea for a webapp that analyzes one’s athletic performance, and solving this problem is central to the app. $\endgroup$ – Philip Nov 12 '18 at 20:52
1
$\begingroup$

Let the $n$ numbers be $x[1..n]$, and the minimum interval size $k$.

Formulating an objective function

There's a conflict here between two goals: Reporting more intervals will often mean reporting worse intervals. We need an unambiguous way to decide which set of intervals is "best". A good way to resolve this is by assigning some score value to any interval that includes two terms: a positive term (perhaps dependent on the length), as well as a negative term for the "quality" (here, standard deviation). The goal is now to choose a set of nonoverlapping intervals that maximises the sum of scores. For example, we could say that the score $s(i, j)$ of the interval $i..j$ is $10 + j - i - 7*StdDev(x[i..j])$.

A quadratic-time dynamic programming algorithm

The following dynamic programming algorithm takes $O(n^2)$ time and $O(n)$ space to find a solution having optimal score (there may in general be more than one such), and works for any scoring function $s$ that depends only on the beginning and end positions of the given interval (so you may certainly tweak my example function until you get results that look good). It seems likely to me that a faster (linear or at least log-linear) algorithm exists for simple scoring functions, but in any case the following is flexible and will certainly handle $n$ up to 10000 in well under a second on any modern-day computer.

For any $1 \le i \le n$, let $f(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$. So in particular, $f(n)$ will be the maximum sum of scores achievable on the entire dataset. For now, let's imagine that we have an algorithm to compute $f(i)$, and use that to compute a related quantity for an "end-inclusive" variant of the problem: let $g(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$ that places the final ($i$-th) element inside an interval. We can compute $g(i)$ as follows:

$g(0 \le i < k) = -\infty$

$g(i \ge k) = \max_{0 \le j < i}(f(j) + s(j+1, i))$

The first equation expresses that there can be no valid end-inclusive solution if there are fewer than $k$ items in total. Using negative infinity is essentially a trick to ensure that this value is "ignored" by any $\max$ expression it happens to find itself in. You wouldn't need to actually represent negative infinity in a program; any sufficiently large negative number would work.

The second equation says that we can always form an optimal solution to the length-$i$ end-inclusive subproblem by taking an optimal solution to some length-$j$ subproblem (which may or may not be end-inclusive), and appending a final interval to it containing every element after the $j$-th, up to the $i$-th -- specifically, whichever choice of $j$ yields the highest combined score. This is the core insight of the algorithm; it's worth taking the time to convince yourself that this is really true.

From here, it's simple to compute $f(i)$:

$f(0) = 0$

$f(i \ge 1) = \max \{g(i), f(i-1)\}$

The first equation is obvious. The second says that we can always form an optimal solution to the length-$i$ unrestricted subproblem by taking either the optimal solution to the corresponding end-inclusive variant of this subproblem (which puts $x[i]$ in an interval), or an optimal solution to the one-shorter unrestricted subproblem (which doesn't) -- whichever has higher score. Again, it's worth checking that this is indeed true.

Memoisation

You can turn each of the above equations into program code to get a working, but exponential-time recursive program that can calculate $f(n)$, the maximum score achievable. To speed this up to quadratic time only requires not recomputing answers to subproblems that we have seen before. This can be as simple as using an array $m[0..n]$, initially filled with some placeholder value like -1, to record answers just before you return them: When $f(i)$ is called, we first check whether $m[i]$ contains a non-placeholder value, and if so immediately return that. This approach to dynamic programming is called memoisation (that's right, there's no "R" in there).

Actually computing a solution

You may have noticed that until now, the things we have been computing ($f(\cdot)$ and $g(\cdot)$) are not actual solutions to the problem but just the scores of those solutions. Fortunately, an actual solution can be recovered without much effort using a technique called traceback.

The key idea is that $\max$ function evaluations encode the "decisions" made by the algorithm. We start at the end with the final total score value $f(n)$, which we know to be optimal, and work backwards, at each step determining which argument to a $\max$ function "won" (was highest): this tells us which subproblem to consider next, and (implicitly) describes one piece of the optimal solution. (Actually there may be multiple highest-equal arguments to a $\max$; convince yourself that choosing any of them will lead to an optimal solution.) We must do this for both $f$ and $g$.

For example, suppose that $n=1000$ and that in the very first step we have $f(1000)=150$. From looking at the second equation defining $f$, our first question is whether this 150 value arose from $g(1000)$ (indicating that $x[1000]$ is in an interval) or from $f(999)$ (indicating that it isn't). Suppose $g(1000)=150$ and $f(999)=133$: then the former wins, so it must be that $x[1000]$ is in an interval in every optimal solution. The next step is to determine which $j$, in the range 0-999, gave rise to the value $g(999)=150$; this will implicitly tell us the length of this final interval, and provide the next subproblem to consider.

Often tracing back is sped up by storing the index of the "winner" in an extra array during the initial forward pass, but it can also be accomplished by recomputing the $f(\cdot)$ or $g(\cdot)$ function value at each step during the backward pass (which is slower, but not asyptotically so).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.