证明了多标签Jaccard度量校准需指数级预测维度,但可多项式近似。
Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
- 用最小哈希和布尔莫比乌斯反演证明损失矩阵满秩
- 精确校准至少需 $2^{s-1}$ 维度,最多 $2^s-1$ 维度
- 固定误差容忍下可用多项式维度近似,适合实际部署
在多标签分类与二值分割中,实例级的交并比(IoU)是标准评价指标。当有 $s$ 个标签时,其损失矩阵包含 $2^s$ 种可能结果。在空集对空集的定义为 1 的约定下,我们证明了 Jaccard 分数、移位损失与普通损失矩阵均为非奇异,并且损失列具有仿射维度 $2^s-1$。该证明结合了有限最小哈希格拉姆表示与布尔莫比乌斯反演。对于精确校准,我们证明 $2^{s-1} \ leq \mathrm{CCdim}(L^{ mathrm{Jac}}) \ leq 2^s-1$。下界基于一个具有 $2^{s-1}+1$ 个支持结果的阶乘加权分布与贝叶斯最优报告。因此,每个精确校准的凸代理都需要指数级预测坐标。我们还给出了两个多项式维数的近似保证,含明确的遗憾转移。一个新的 $F_1$ 到 Jaccard 转移将现有的 $(s^2+1)$ 维 $F_1$ 代理转化为多项式时间规则,渐近 Jaccard 遗憾不超过 $3-2\sqrt{2}$。对于任意 $α>0$ 与 $0<ρ<1$,最小哈希平方损失代理在任意条件标签分布上均能实现统一的 Jaccard 遗憾下界 $α$。以至少 $1-ρ$ 的概率,直接构造的维度为 $O((s^2+s\log(1/ρ))/α^2)$,而带符号变体为 $O((s+\log(1/ρ))/α^2)$。因此,零遗憾校准需要指数维度,而任意固定的加性遗憾容限则允许多项式预测维度。
原文摘要 · Abstract (English)
The per-instance Jaccard score, or intersection over union (IoU), is standard in multi-label classification and binary segmentation. With $s$ labels, its loss matrix has $2^s$ outcomes and reports. Under the convention $\mathrm{Jac}(\varnothing,\varnothing)=1$, we prove that the Jaccard score, shifted-loss, and ordinary loss matrices are nonsingular and that the loss columns have affine dimension $2^s-1$. The proof combines a finite MinHash Gram representation with Boolean Möbius inversion. For exact calibration, we prove $2^{s-1} \leq \mathrm{CCdim}(L^{\mathrm{Jac}}) \leq 2^s-1$. The lower bound uses a factorially weighted distribution with $2^{s-1}+1$ supported outcomes and Bayes-optimal reports. Consequently, every exactly calibrated convex surrogate requires exponentially many prediction coordinates. We also give two polynomial-dimensional approximation guarantees with explicit regret transfers. A new $F_1$-to-Jaccard transfer turns an existing $(s^2+1)$-dimensional $F_1$ surrogate into a polynomial-time rule with asymptotic Jaccard regret at most $3-2\sqrt{2}$. For any $α>0$ and $0<ρ<1$, a MinHash square-loss surrogate attains Jaccard-regret floor $α$ uniformly over arbitrary conditional label distributions. With probability at least $1-ρ$, the direct construction has dimension $O((s^2+s\log(1/ρ))/α^2)$, while a signed variant has dimension $O((s+\log(1/ρ))/α^2)$. Thus zero-regret calibration requires exponential dimension, whereas every fixed additive regret tolerance admits polynomial prediction dimension.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。