arXiv:2608.13549cs.LGstat.ML2026-08被引 1

证明了多标签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 官方产品;中文卡片由大模型生成,请以原文为准。