8
$\begingroup$

My dataset contains two (rather strongly correlated) variables $t$ (runtime of algorithm) and $n$ (number of examined nodes, whatever). Both are strongly correlated by design, because the algorithm can manage roughly $c$ nodes per second.

The algorithm was run on several problems, but it was terminated if a solution hasn't been found after some timeout $T$. So data is right-censored on the time variable.

I plot the estimated cumulative density function (or the cumulated count) of variable $n$ for the cases where the algorithm did terminate with $t<T$. This shows how many problems could be solved by expanding at most $n$ nodes and is useful for comparing different configurations of the algorithm. But in the plot for $n$, there are those funny tails at the top going right sharply, as can be seen in the image below. Compare the ecdf for variable $t$, on which the censoring was done.

Cumulated Count of $n$

ecdf of n

Cumulated Count of $t$

ecdf of t

Simulation

I understand why this happens, and can reproduce the effect in a simulation using the following R code. It's caused by censoring on a strongly correlated variable under the addition of some noise.

qplot(
  Filter(function(x) (x + rnorm(1,0,1)[1]) < 5,
         runif(10000,0,10)),
  stat="ecdf",geom="step")

synthetic data

How is this phenomenon called? I need to state in a publication that these fans are artifacts of the experiment and do not reflect the real distribution.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Is this due to early termination ? $\endgroup$ – lcrmorin Apr 30 '13 at 16:15
  • $\begingroup$ Can you model your data with a parametric distribution? You could try that using just the uncensored data. If it works, then you could use maximum likelihood on the entire dataset to get an estimate of the true CDF and eliminate the behavior in your chart. $\endgroup$ – soakley Apr 30 '13 at 16:41
  • $\begingroup$ @soakly The samples are not iis. The algorithm runs on a set of benchmark problems, and those basically define the shape of the curve (together with the characteristics of the algorithm configurations). $\endgroup$ – ziggystar Apr 30 '13 at 17:16
  • $\begingroup$ @lmorin I don't exactly know what early termination means, but the data is cleanly right-censored on the time variable. $\endgroup$ – ziggystar Apr 30 '13 at 17:18
  • 1
    $\begingroup$ The quantities in the first two displays aren't actually ECDFs, since the values taken by ECDFs are on [0,1]. It would be better to label them with a more accurate title. $\endgroup$ – Glen_b -Reinstate Monica Oct 29 '13 at 23:16
1
$\begingroup$

I'm not an expert, but I believe what you're seeing is analogous to soft clipping.

Sort Clipping (Gain Compression)

It's a little different, because your clipping is caused by a non-deterministic process, in that your signal is clipped when it plus a random noise exceeds a threshold, instead of a device that deterministically reduces an analog signal. I have a guitar pedal that does this, it softens the "punch" of playing an electric guitar:

Keeyley Compressor Demo

Seems like a decent analogy. Im not sure if there is a name in the statistical community.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

I suspect you run into the family of stable non-symmetric distributions.
First, plot your ecdf in a log-log plot. Adopt a parametric approach, assume Pareto Distribution, enter image description here

The cdf in your case is translated as $F_t(t)=1-(\frac{t_{min}}{t})^a \ for \ t>t_{min}$, where $t_{min}$ is the minimum completion time of your algorithm, hence the threshold appearing on the left side of the ecdf graph
If you see a line in the log-log plot, then you are on the right path, make a linear regression on the log transformed data you have, to find out $\hat{\alpha}$, the so called Pareto index.

Pareto index must be greater than 1, it gives and interpretation of the heavy "tailness" of the distribution, how much data is spans on the edges. The closer to 1 the more pathogenic situation you have.
In other words, $\alpha$ expresses the ratio of nodes spent negligible time vs nodes spent excessive time before their completion. Previous reader pinpointed the fact you terminate abruptly your experiment, this introduces a complication described as $\hat{\alpha}=\hat{\alpha}(T)$. I suggest you should vary $T$ to explore this dependence.

Heavy tails phenomenon is common in computer science, particularly when nodes compete against shared resources in a random fashion, e.g. computer networks.

| cite | improve this answer | | | | |
$\endgroup$
  • 2
    $\begingroup$ I don't think my problem lies with finding the correct model. You see the second plot in my question? The true distribution would show as a line, but due to the censoring effect it becomes a curve. I want to know how to call this phenomenon. $\endgroup$ – ziggystar May 1 '13 at 20:24
  • $\begingroup$ Your nodes share a common resource, your cpu which indirectly is reflected to time completion fluctuations and these red and pink dots that are quite far away from the main mass of their respective distribution is what makes me suspicious. The long lasting processing nodes will affect rest nodes, I speculate that they will eventually drive the mass away from its center. $\endgroup$ – aarsakian May 1 '13 at 20:58
  • 2
    $\begingroup$ I'm not sure whether you understood the domain correctly: The problem is a search. The algorithm looks at a node at a time in order to find a solution node. A better algorithm has to look at less nodes before it finds a solution (because it selects nodes more cleverly). Looking at a node requires some time, and so number of nodes examined and time consumed should correlate rather strongly. $\endgroup$ – ziggystar May 2 '13 at 11:44
-1
$\begingroup$

say that your distribution is truncated, like truncated normal

| cite | improve this answer | | | | |
$\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.