多标签Jaccard测度的凸校准维度指数下界
Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
做多标签分类调Jaccard的同学看看:精确校准要指数维度,但固定误差容忍度有多项式解法,MinHash思路挺巧。
该论文研究多标签分类中逐样本Jaccard分数(IoU)的校准维度。作者证明Jaccard损失、平移损失和普通损失矩阵均非奇异,损失列仿射维度为2^s−1。
精确校准的凸校准维度满足2^{s−1} ≤ CCdim ≤ 2^s−1,因此任何精确校准的凸代理都需要指数多个预测坐标。针对固定误差容忍度,论文给出多项式维度近似:F1到Jaccard的转移在维度s^2+1下达到至多3−2√2的渐近遗憾;
MinHash平方损失代理在维度O((s^2+s log(1/ρ))/α^2)下达到遗憾上界α。
Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include Jaccard, MinHash, multi-label classification, calibration.
Source attribution: curated from arXiv cs.LG (@Mingyuan Zhang).