Can queries really be permuted independently?

[danr]

Under the header Assigning significance to mAP scores you write

To generate mAP distribution under the null hypothesis, we repeatedly reshuffle the rank list and recalculate mAP.

You refer to the rank list. But there is one rank list for each query profile. Looking at your code it seems you treat these rank lists independently. But would it not be more correct to shuffle the profile labels (query or reference), then calculate mAP by recalculating each query profile's rank list? Why is your shortcut correct?

Thanks!

[alxndrkalinin]

Sorry for not responding earlier, I just saw your comment.

Because AP calculation relies solely on ranks and not distance metric values, both these approaches are equivalent. Our null hypothesis is that M profiles in the query group come from the same distribution as N profiles in the reference group (i.e. produced by the same data-generating process). For each query profile the calculation procedure will produce a binary rank list of size N+(M-1). Since sizes of both groups are fixed and ranking is binary, the null distribution will always include all possible binary rankings. Thus, it only depends on two parameters: M-1 and N+(M-1) and has the exact size equal to the binomial coefficient N+(M-1) choose M-1. If we re-shuffle labels instead given a query and convert results into binary rank lists, we will recover the same null distribution.

Hope this illustration for M=2 and N=3 helps: