5
$\begingroup$

I'm trying to assess the difference between two algorithms. They are stochastic, so I've run them multiple times against the same input files and noted their results. I want to determine whether my algorithm offers a statistically significant improvement over a previous approach. From my (potentially flawed) understanding this sort of situation is where I should (or rather could) use the Wilcoxon Sign Rank test.

The data is naturally paired, so I can join together outputs of both algorithms by the particular input problem they used. Since I want to test that my algorithm is not just different, but actually better (in this case returning lower values) than the other algorithm this appears to be a one-tailed assumption.

I'm using the R wilcox.test function to perform the test and I'm slightly confused about how I should interpret the results. I have read the help page for wilcox.test and it doesn't seem to offer much information about the results, more focus is made to the function's arguments. I've made a minimal working example with a small subset of my data:

x <- structure(list(instance = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L), .Label = c("competition01", "competition02", 
"competition03", "competition04", "competition05", "competition06", 
"competition07", "competition08", "competition09", "competition10", 
"competition11", "competition12", "competition13", "competition14", 
"competition15", "competition16", "competition17", "competition18", 
"competition19", "competition20"), class = "factor"), nhoods = structure(c(1L, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), .Label = c("nhoods1", "nhoods2", 
"nhoods3", "nhoods4", "nhoods5"), class = "factor"), run.no = structure(c(1L, 
1L, 2L, 2L, 3L, 3L, 4L, 4L, 5L, 5L), .Label = c("1", "2", "3", 
"4", "5"), class = "factor"), partition = structure(c(1L, 2L, 
1L, 2L, 1L, 2L, 1L, 2L, 1L, 2L), .Label = c("Hard-Soft", "Full"
), class = "factor"), VNS = c(984L, 1445L, 1033L, 1445L, 1035L, 
1318L, 1058L, 1445L, 913L, 1445L), `VNS-Skip` = c(1083L, 1425L, 
1099L, 1230L, 1077L, 1363L, 1102L, 1442L, 1093L, 1252L)), .Names = c("instance", 
"nhoods", "run.no", "partition", "VNS", "VNS-Skip"), row.names = c(NA, 
10L), class = "data.frame")

wilcox.test(x[,5], x[,6], paired = TRUE, conf.int = TRUE, alternative = "greater")

My algorithm's results are in the 6th column and the original ones are in the 5th column. Since I want to assess whether my algorithm is better I've used the alternative = "greater" option which should mean that the test is checking for 1st arg > 2nd arg.

This results in the output:

  Wilcoxon signed rank test

  data:  x[, 5] and x[, 6] 
  V = 22, p-value = 0.7217
  alternative hypothesis: true location shift is greater than 0 
  95 percent confidence interval:
  -72 Inf 
  sample estimates:
  (pseudo)median 
        -21 

In this case the p-value is not less than 0.05 so there is not enough evidence to discard the null hypothesis.

What does having infinity as the upper bound of a confidence interval mean? Is this because I'm using the one-tailed version of the test? All the tests I've run on my data always have the upper confidence interval as Inf. If the p-value were less than 0.05 would that mean I would be justified in saying "with a 95% confidence x[,5]'s mean will be within -72 of x[,6]'s?"

What does the V value mean with regard to my data? From what I can see it is the difference between median(x[,5]) and median(x[,6] but how would describe that in prose? Does anyone actually use the V value is the discussion of their data analyses?

$\endgroup$
6
$\begingroup$

What does having infinity as the upper bound of a confidence interval mean? Is this because I'm using the one-tailed version of the test?

Yes, it's because you're doing a one-tailed version of the test; no matter how far the sample location is in the 'wrong' direction (i.e. the direction inconsistent with the alternative), it's still consistent with the null - so you're only considering one-sided bounds.

would that mean I would be justified in saying "with a 95% confidence x[,5]'s mean will be within -72 of x[,6]'s?"

No it wouldn't justify that statement. For starters you're not testing means at all unless you make some additional assumptions that would make difference in means coincide with the population equivalent of the location-shift estimate for the test.

In the second place, the location-difference could be in the 'wrong' direction, so 'within' doesn't quite work either.

In the third place, two locations aren't normally considered to be 'within' a negative distance of each other.

You could say something like "the estimated improvement from the first to the second algorithm was 21" (and then give the units!). Note that I said 21 and not 72. If you explain to the reader what the pseudo-median of the differences is, you can give more detail about what this difference is measuring.

What does the V value mean with regard to my data?

It's the value of the Signed Rank statistic. Check the references mentioned below for how it's calculated (particularly Hollander & Wolfe if you can find it since that's the references given in the R help, so the statistic is sure to correspond).

Specifically, the two main definitions that I've seen are either that all signed ranks are added (this is the version on the Wikipedia page), OR that only the positive-signed ranks are added. It looks like R uses the second one. That is, if $x$ and $y$ are the two paired samples, so the differences $x-y$ are tested, then

 sum(rank(abs(x-y))[x>y])

should give the same statistic as R. Like so:

> sum(rank(abs(x[,5]-x[,6]))[x[,5]>x[,6]])
[1] 22

From what I can see it is the difference between median(x[,5]) and median(x[,6]

It isn't. Well, they might coincide occasionally (as with your sample) but that's not what is going on. You should probably start by reading up about how the statistic works. I'd suggest something like Conover's Practical Nonparametric Statistics. Or, ideally, you could check the Signed Rank Test reference in the R help on wilcox.test (Hollander & Wolfe).

The actual value of the statistic isn't usually of interest. The estimate of the size of the location-shift would be relevant (and doesn't depend on which definition of the statistic is used). That is, the fact that 0 is inside the interval matters a lot, the "-21" matters somewhat, the "-72" might matter, the "22" probably doesn't (though there's little harm in quoting it if the definition of the statistic is clear to the reader).

$\endgroup$
  • $\begingroup$ Thanks for a great explanation. One minor thing I'm not fully clear on is your point re: the location shift and whether 0 is inside the interval. I remember reading that an interval which contains 0 is not statistically significant. In this one-tailed case we've only got one actual limit, can we use an unbounded interval? So (-72 < 0 < +Inf) thus it's not significant (as 0 is between the limits). If, for example, the range was (22 < +Inf), this interval is fully positive and 0 isn't within it. Is that correct? $\endgroup$ – Alastair Nov 1 '12 at 10:47
  • $\begingroup$ Your reasoning is correct; the alternative is to look at the p-value (they give identical conclusions) $\endgroup$ – Glen_b Nov 1 '12 at 10:55

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.