[论文] Exponential Convex Calibration Dimension for the Multi-Label Jaccard M...
论文概要
研究领域: ML 作者: Mingyuan Zhang 发布时间: 2026-08-13 arXiv: 2608.13549中文摘要
每个实例的Jaccard分数（即交并比IoU）是多标签分类和二值分割的标准指标。对于s个标签，其损失矩阵有2^s个结果和报告。在约定Jac(∅,∅)=1下，我们证明Jaccard分数、移位损失和普通损失矩阵都是非奇异的，且损失列具有仿射维度2^s-1。证明结合了有限MinHash Gram表示与布尔Möbius反演。对于精确校准，我们证明2^(s-1) ≤ CCdim(L^Jac) ≤ 2^s-1。下界使用阶乘加权分布，具有2^(s-1)+1个支持结果和贝叶斯最优报告。因此，每个精确校准的凸替代需要指数级多的预测坐标。我们还给出两个多项式维度的近似保证，具有显式的遗憾转移。一种新的F1-to-Jaccard转移将现有的(s^2+1)维F1替代转化为多项式时间规则，渐近Jaccard遗憾至多为3-2√2。对于任意α>0和0<ρ<1，MinHash平方损失替代在任意条件标签分布上统一达到Jaccard遗憾下限α。概率至少为1-ρ时，直接构造的维度为O((s^2+s log(1/ρ))/α^2)，而有符号变体的维度为O((s+log(1/ρ))/α^2)。因此，零遗憾校准需要指数维度，而每个固定的加性遗憾容忍度允许多项式预测维度。原文摘要
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 Jac(∅,∅)=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) ≤ CCdim(L^Jac) ≤ 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 F1-to-Jaccard transfer turns an existing (s^2+1)-dimensional F1 surrogate into a polynomial-time rule with asymptotic Jaccard regret at most 3-2√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.--- *自动采集于 2026-08-15*
#论文 #arXiv #ML #小凯