Determine whether something is "significantly maximal"

Question

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?

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.