The problem:

I have a measure $D_i$ that quantifies how well a single target "feature" can be predicted from a set of (other) features $i$ (similar to an AUC). $D_i$ is computed based on a set of $n$ data points (instances), for a number of different feature sets $i = 1 \ldots N$. Different feature sets may have some features in common.

I'm interested to know whether the feature set with the largest estimated value $D_{(1)}$ (where numbers in parentheses denote the empirical rank in descending order) is actually the best, i.e. whether $D_{(1)}$ is not just empirically but "significantly" maximal. To put it differently, I'm looking for a significance test with the null hypothesis $d_{(1)} \leq d_{(2)}$, where $d_{(i)}$ is the "true value" of $D_{(i)}$ computed from an infinite amount of data ($n \to \infty$), against the alternative $d_{(1)} > d_{(2)}$.

For a given pair of feature sets $i$ and $j$ I can construct a one-sided test by computing a $(1 - 2 \alpha)$-confidence interval for $d_i - d_j$ via bootstrap and rejecting the null hypothesis if the CI lies above 0. However, if I apply such a test to the two highest-ranked, $i = (1)$ and $j = (2)$, I have selected them based on the data, rendering this test invalid.

It appears that the Friedman test is the solution for a similar problem. It seems however that I can not fulfill the assumptions of that test: The $D$s for different feature sets are not mutually independent because of feature overlap, and I do not have multiple independent values of each of them. The latter problem could be addressed by splitting the data set into multiple equal-sized subsets, but I fear that this will destroy my chance to get any result at all.

What I have come up with so far:

  1. Based on the pairwise test described above, for a given $i$ I can test whether $d_{i} > d_{j}$ for all $j \neq i$, and declare $i$ to be "significantly maximal" if all of these $N - 1$ tests have a positive outcome. Since the outcomes of the single tests enter a conjunction, I do not have to correct for multiple comparisons. Rather, the probability of a false positive will often be strongly reduced. However, since the null hypothesis does not make any statement about the performance of worse feature sets $d_{(3)}$, $d_{(4)}$, $d_{(5)}$, …, the amount of this reduction cannot be determined.

  2. I apply this procedure to every feature set $i = 1 \ldots N$. Assuming a not-too-weird sampling distribution (e.g. finite variance, compact support?), this can only lead to a result of "significantly maximal" for one of the $D_i$, and this is exactly $D_{(1)}$ – or to the result that none of the $D_i$ is "significantly maximal". Each of these $N$ tests – but only one of them – may result in a false positive, which means we have the case of perfect negative dependence in which Bonferroni correction is exact. The elementary pairwise tests have to performed such that $\alpha N$ is the desired size of the total test procedure.

  3. Since only $(1)$ has a chance to be "significantly maximal" and only $(2)$ has a chance to rob $(1)$ of that status, it is practically sufficient to apply the pairwise test to the two highest-ranked, $i = (1)$ vs $j = (2)$, but still apply Bonferroni correction to account for the fact that they have been selected based on the data.

My questions:

  • Do you think the procedure described above is correct, i.e. leads to a valid test of the specified null hypothesis?

  • Can the procedure be made more powerful, e.g. by somehow accounting for the reduction of the false positive rate under 2.?

  • Can you think of another approach to the problem, which might be more powerful than this one?

  • It might be that $(1)$ and $(2)$ are tied, but both better than $(3)$ and the rest. How would one approach the generalized problem of finding "significant gaps" in the ranked list of $D$s?


1 Answer 1


So you have some observations $D_1, \dots, D_n$ where each are an observation (or for example means of observations) from some distribution with means $\mu_1, \dots, \mu_n$.

The observation with largest mean is then $D_{(1)}$. You want to know if the corresponding mean is really the largest from among $\mu_1, \dots, \mu_n$. This problem have been studied under the name of the subset selection problem. Put into google scholar the search terms: subset selection problem Gupta one of the hits will be On Some Multiple Decision (Selection and Ranking) Rules

There is an immense literature on this problem, mostly theoretical, applications seems to be few.

The idea is to require a "subset of the $n$ populations with indices $1,2, \dots, n$ such that this subset selection procedure contains the population with maximum mean, mat least, say, $95\%$ of time.

A book-length treatment of such ideas is in Multiple Decision Procedures: Theory and Methodology of Selecting and Ranking Populations (Classics in Applied Mathematics)

If you think some such procedure could be useful for you, I can extend this answer with some details of the procedure.

  • 1
    $\begingroup$ I don't have access to that paper and book, so I could only read the abstracts, but yes, this looks like it is relevant, and I would very much like an extended answer. I wouldn't make any distributional assumptions for the $D$s though, apart from some general sanity properties, and I also wouldn't necessarily expect that they are unbiased estimators (except asymptotically) of the $d$s. $\endgroup$
    – A. Donda
    Nov 6, 2014 at 17:32
  • $\begingroup$ On second thought: Instead of defining the $d$s as the infinite data limit, it would also be ok to define them as the expectation of the sampling distribution of the $D$s. In that case, we do have unbiased estimators. $\endgroup$
    – A. Donda
    Nov 6, 2014 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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