# Determine whether something is “significantly maximal”

### 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?

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 http://www.tandfonline.com/doi/abs/10.1080/00401706.1965.10490251#.VFs7hfmG98E

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 http://www.amazon.com/Multiple-Decision-Procedures-Methodology-Populations/dp/0898715326/ref=sr_1_15?s=books&ie=UTF8&qid=1415269310&sr=1-15&keywords=ranking+and+selection

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

• 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. – A. Donda Nov 6 '14 at 17:32
• 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. – A. Donda Nov 6 '14 at 19:58