7
$\begingroup$

Disclaimer: I'm a software engineer, not a statistician, so please forgive any blunt error :-)

I have a set of time-series "curves", each measuring the entropy of a given artifact. Now, I'm standing over the following premises (please criticize them as you see fit):

  1. In order to approximate the upper bounds of the Kolmogorov complexity $K(s)$, of a string $s$, one can simply compress the string $s$ with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the resulting string's length.
  2. For this purpose, I've used the bzip2 application, setting its compression level to the supported maximum (-9).
  3. If one is only interested in a time-series analysis of a set of evolving strings, calculating the compressed deltas is enough to present a relative measure of entropy between any two strings (at least that's my interpretation after reading Cilibrasi05).
  4. For that, I used the diff unix tool, with the (--minimal) parameter, again followed by a bzip2 compression, with the aforementioned settings.

I'm doing this to analyze the evolution of the entropy in a software artifact (code, model, whatever). I'm not worried with the absolute values, but with the relative increase (or decrease) in entropy. Now here comes the problem:

  1. I've done this for a set of 6 artifacts, which ought to belong to the same population, but I don't know how to provide statistical evidence of that (the corresponding of doing a two-tailed t-test of two samples).
  2. One of the artifacts evolution should be different from all the others. We're talking something like an exponential v.s. sub-linear growth. How do I provide statistical evidence of that?

Again, the disclaimer of being a software engineer. Although I would appreciate every academic reference (papers, books, etc.) you could handle, I'm looking for something pragmatic that I can use in the next few days, like a script in R, or something in SPSS.

P.S. I'm sorry for asking for a recipe, instead of a theoretical explanation.

$\endgroup$
6
+50
$\begingroup$

I have a relatively simple solution to propose, Hugo. Because you're forthright about not being a statistician (often a plus ;-) but obviously can handle technical language, I'll take some pains to be technically clear but avoid statistical jargon.

Let's start by checking my understanding: you have six series of data (t[j,i], h[j,i]), 1 <= j <= 6, 1 <= i <= n[j], where t[j,i] is the time you measured the entropy h[j,i] for artifact j and n[j] is the number of observations made of artifact j.

We may as well assume t[j,i] <= t[j,i+1] is always the case, but it sounds like you cannot necessarily assume that t[1,i] = ... = t[6,i] for all i (synchronous measurements) or even that t[j,i+1] - t[j,i] is a constant for any given j (equal time increments). We might as well also suppose j=1 designates your special artifact.

We do need a model for the data. "Exponential" versus "sublinear" covers a lot of ground, suggesting we should adopt a very broad (non-parametric) model for the behavior of the curves. One thing that simply distinguishes these two forms of evolution is that the increments h[j,i+1] - h[j,i] in the exponential case will be increasing whereas for concave sublinear growth the increments will decreasing. Specifically, the increments of the increments,

d2[j,i] = h[j,i+1] - 2*h[j,i+1] + h[j,i], 1 <= i <= n[j]-2,

will either tend to be positive (for artifact 1) or negative (for the others).

A big question concerns the nature of variation: the observed entropies might not exactly fit along any nice curve; they might oscillate, seemingly at random, around some ideal curve. Because you don't want to do any statistical modeling, we aren't going to learn much about the nature of this variation, but let's hope that the amount of variation for any given artifact j is typically about the same size for all times t[j,i]. This lets us write each entropy in the form

h[j,i] = y[j,i] + e[j,i]

where y[j,i] is the "true" entropy for artifact j at time t[j,i] and e[j,i] is the difference between the observed entropy h[j,i] and the true entropy. It might be reasonable, as a first cut at this problem, to hope that the e[j,i] act randomly and appear to be statistically independent of each other and of the y[j,i] and t[j,i].

This setup and these assumptions imply that the set of second increments for artifact j, {d2[j,i] | 1 <= i <= n[j]-2}, will not necessarily be entirely positive or entirely negative, but that each such set should look like a bunch of (potentially different) positive or negative numbers plus some fluctuation:

d2[j,i] = (y[j,i+2] - 2*y[j,i+1] + y[j,i]) + (e[j,i+2] - 2*e[j,i+1] + e[j,i]).

We're still not in a classic probability context, but we're close if we (incorrectly, but perhaps not fatally) treat the correct second increments (y[j,i+2] - 2*y[j,i+1] + y[j,i]) as if they were numbers drawn randomly from some box. In the case of artifact 1 your hope is that this is a box of all positive numbers; for the other artifacts, your hope is that it is a box of all negative numbers.

At this point we can apply some standard machinery for hypothesis testing. The null hypothesis is that the true second increments are all (or most of them) negative; the alternative hypothesis covers all the other 2^6-1 possibilities concerning the signs of the six batches of second increments. This suggests running a t-test separately for each collection of actual second increments to compare them against zero. (A non-parametric equivalent, such as a sign test, would be fine, too.) Use a Bonferroni correction with these planned multiple comparisons; that is, if you want to test at a level of alpha (e.g., 5%) to attain a desired "probability value," use the alpha/6 critical value for the test. This can readily be done even in a spreadsheet if you like. It's fast and straightforward.

This approach is not going to be the best one because among all those that could be conceived: it's one of the less powerful and it still makes some assumptions (such as independence of the errors); but if it works--that is, if you find the second increments for j=1 to be significantly above 0 and all the others to be significantly below 0--then it will have done its job. If this is not the case, your expectations might still be correct, but it would take a greater statistical modeling effort to analyze the data. (The next phase, if needed, might be to look at the runs of increments for each artifact to see whether there's evidence that eventually each curve becomes exponential or sublinear. It should also involve a deeper analysis of the nature of variation in the data.)

$\endgroup$
  • $\begingroup$ That was a great insight! All your assumptions can be considered, and your rationale is sound! I do have some doubts though, if you don't mind: (I) Shouldn't d2[j,i] = h[j,i+2] ...? (II) Why do you consider the increment as y[j,i+2] - 2*y[j,i+1] + y[j,i] and not just y[j,i+1]-y[j,i]? Is it a kind of derivative (i.e., to calculate the "slope")? $\endgroup$ – Hugo Sereno Ferreira Aug 25 '10 at 13:25
  • $\begingroup$ (1) Yes, good catch. I fixed that typo. (2) We're really looking at second derivatives: the increments d[j,i] = h[j,i+1] - h[j,i] act like slopes (and are slopes when times are equally spaced). I am proposing to distinguish "exponential" from "sublinear" behavior in terms of changes in the slopes. Whence we want to consider the signs of d2[j,i] := d[j,i+1] - d[j,i] = (h[j,i+2] - h[j,i+1]) - (h[j,i+1] - h[j,i]) etc. $\endgroup$ – whuber Aug 25 '10 at 13:32
1
$\begingroup$

You can do it all on Excel.

Plotting the six time series should give you a hint of the shapes of the curves. Let's say that, as you mentioned, five of the curves look like they're exponential and the sixth looks like it grows sub-linearly.

Insert a trendline for each curve. If you are right, five of them will provide the best fit (as measured by r squared) with an exponential trendline, while the sixth will be best fitted to a logarithmic trendline.

This may sound non-deterministic, but if all six values of r squared are close to 1 you can be pretty confident of your result.

$\endgroup$
  • 1
    $\begingroup$ Carlos, thank you for your contribution, but the level of scientific validation that I need should, at least, give me a "probability" value of that claim. Thanks, anyway. $\endgroup$ – Hugo Sereno Ferreira Aug 23 '10 at 16:20

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.