AUC指标的公榜探测次数

（本文主要源自与@broccoli beef的讨论。）

对于AUC指标，公榜探测需要多少次能得到？

我们可以提前给个结论，一个粗糙的用来估计的界限是N*H(p)/2log2(N)。

---

对于AUC，总所周知的定义是：

$$\mathrm{AUC}=E(1(f(x^+)>f(x^-)))$$

但是常被忽视的定义是：

$$\mathrm{AUC}=\frac{\sum R_{pos} -\frac{n_{pos}*(n_{pos}+1)}{2}}{n_{pos}n_{neg}}$$

其中$R_{pos}$是正样本的排名。

故我们可以不断提交笔记本获得公榜来获取某个样本的排名，并可得知该样本前后的样本数，正负样本数可以通过排行榜的差值来获取。即

Before: m pos  || rank i  || n pos
After: m pos   ||   n pos   ||   rank i

类似于我们可以大幅降低复杂度，比如在正负样本3:1的情况下150次提交可以把$\binom{N}{\frac{3}{4}N}$降为$\binom{\frac{1}{150}N}{\frac{1}{150}\frac{3}{4}N}^{150}$。

但是这种方法还是太暴力和粗糙。

还有没有更快的呢？有的有的。

更快的方法：

根据AUC的后一个定义，我们发现其是线性的。实际上这是一个混合整数规划（Mixed Integer Programming, MIP）。

我们可以使用ortools来求解，比如：

N=146
p=113
n=33
from ortools.sat.python import cp_model

class SolutionCallback(cp_model.CpSolverSolutionCallback):

    def __init__(self):
        super().__init__()
        self.solutions = []

    def on_solution_callback(self):
        self.solutions.append([self.Value(x[i]) for i in range(N)])

model = cp_model.CpModel()
x = [model.NewIntVar(0, 1, F'x[{i}]') for i in range(N)]

model.Add(sum(x)==p)

for m in range(10):
    y_pred = preds[m]
    r = pd.Series(y_pred).rank().values
    model.Add(sum(x[i]*int(np.around(r[i]*2)) for i in range(N))==int(np.around(scores[m]*n*p*2))+p*(p+1))

solver = cp_model.CpSolver()
s = SolutionCallback()
solver.SearchForAllSolutions(model, s)

另一个更重要的问题是，我们大概需要多少个提交呢？

我们可以使用信息论粗糙地估计一下。

总信息量是$log_2\binom{N}{\frac{3}{4}N}\approx N*H(p)$，其中H是熵。

如果我们使用斯特林公式，即$ln(n!)\approx nlnn−n+\frac{1}{2}ln(2\pi n)$则：

$$
log_2\binom{N}{\frac{3}{4}N}\approx N*H(p)-\frac{1}{2}log_2(2\pi Np(1-p))
$$

每次探测大概有O(N^2)的范围，大概能提供$2log_2N$的信息量.

$$k\approx\frac{N*H(p)}{2log_2N}$$

对于3月的TPS数据集，公榜为146，正负样本比例为3:1，k~8，和现实的实践是一样的。