1
$\begingroup$

I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the smaller S will be) and P < P_th (the wider the interval the higher P will be).

  • I am not 100% certain the claims in parenthesis are always correct as, I think, it is affected by the distance between the Red and Green graphs.

The graphs R and G is KDEs generated with Gaussian functions, therefore continuous.

I already know that the conditions can be true only where the Red graph is above the Green one. I, therefore, find the intersections between the graphs (e.g. with brentq) and find relevant intervals by calculation a single point in them.

Below are a few examples of graphs I want to analyze. The blue vertical lines mark graph intersections; blue horizontal lines with the condition results on top are shown only when the conditions were met for the whole interval.

The vertical and horizontal lines in black are generated from an ML algorithm which I want to replace with a numerical calculation. As it can be seen it, usually, finds intervals that are smaller than the whole area where red is on top.

Example 1: ML algo found the better solution on the right section, neither found the left one interesting. enter image description here

Example 2: On the right, you can see the ML algo suggesting a range not quite between the blue lines. I am OK with the new algo clipping the portion on the left. enter image description here Example 3: showing that there may be more than one interesting range per marked section. enter image description here Example 4: ML algo missed the leftmost range enter image description here

$\endgroup$
4
  • $\begingroup$ @PålGD the question is how to define the search problem to get relevant ranges. The functions are Gaussians, so I assume I can calculate any derivative $\endgroup$
    – mibm
    Sep 8 '20 at 13:17
  • 1
    $\begingroup$ The points are roots of the difference of the two functions. So, this problem is nothing else than root finding. $\endgroup$
    – plop
    Sep 8 '20 at 13:19
  • $\begingroup$ What are S and P, and how do they relate to the R and G curves? Please define all notation in the question... $\endgroup$
    – D.W.
    Sep 9 '20 at 15:57
  • $\begingroup$ S is simply size; P is some metric, e.g. goodness. Both are calculated on the intervals marked on the KDE graphs on an actual data-set. $\endgroup$
    – mibm
    Sep 14 '20 at 13:14
0
$\begingroup$

Let $x_1,x_2,\dots,x_n$ denote the $x$-values where the two curves intersect; you say you know how to find these. Let's add $x_0=-\infty$ and $x_{n+1}=+\infty$. Then in each interval $[x_i,x_{i+1}]$, either the red curve is consistently above the green curve or vice versa, so label that interval with the color of the curve that is on top. This is easy to do by picking an arbitrary $x$-value in $(x_i,x_{i+1})$ evaluating the height of both points at that point.

Now your problem reduces to the following: find $x_i,x_j$ that maximize $x_j-x_i$, such that all of the intervals $[x_i,x_{i+1}],[x_{i+1},x_{i+2}],\dots,[x_{j-1},x_j]$ are labelled red.

This problem can be solved in a straightforward way, in linear time. Iterate through $j:=1,2,\dots,$, scanning from left-to-right, keeping track of the smallest $i$ such that all intervals between $x_i..x_j$ are labelled red. Thus, when you encounter a red interval $[x_{j-1},x_j]$, you do nothing; when you encounter a green interval $[x_{j-1},x_j]$, you reset $i := j$. Keep track of the longest range you've found so far as you do the linear scan.

$\endgroup$
3
  • $\begingroup$ I probably didn't clearly state the problem. Every interval where red is above green (found them all) potentially contains an interesting (sub)range. I cannot simply shrink the interval from left/right and calculate condition because it may happen that shrinking by an epsilon from either side increases P (lower better) however if I keep shrinking it gets under the original P. This has to do with the distance between red and green (so maybe my optimization should be on some aspect of the integral between graphs) $\endgroup$
    – mibm
    Sep 9 '20 at 6:54
  • $\begingroup$ @mibm, I am sorry, but I don't understand what you're saying or what the actual problem statement is, and unfortunately, if I don't understand that, I won't be able to suggest algorithms. Perhaps you can think about how to formulate your problem more accurately and then post a new question or edit the existing one. I don't know what the definition of "interesting" is or what P is or what you want an algorithm to produce as output. $\endgroup$
    – D.W.
    Sep 9 '20 at 9:17
  • $\begingroup$ I tried to better organize my question. The relevant intervals for the search problem are where red is on top. I think the diff between the graphs may be relevant since P is lower when the diff is larger. $\endgroup$
    – mibm
    Sep 9 '20 at 15:50

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.