精确确定多标签F1损失的秩与凸校准维度下界，揭示其复杂性本质。
Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss
- 通过子集包含矩阵和柯西矩阵分解，证明F1损失矩阵秩为s²−s+2。
- 构造特定分布，证明凸校准维度下界约为(2/(3√3))s²，接近二次方阶。
- 结果表明F1损失需至少二次方维的代理函数，对算法设计具指导意义。
实例级F1度量是多标签分类的核心评估指标。对于s个标签的问题，其定义了一个2^s×2^s的损失矩阵。先前工作给出了s²+1维仿射与平移低秩表示，并据此构建了二次维的凸校准代理损失。本文确定了精确秩：在约定F₁(∅,∅)=1条件下，F1得分矩阵、平移损失矩阵与未平移损失矩阵的秩均为s²−s+2，而损失的列仿射维数为s²−s+1。证明通过非空得分矩阵经子集包含矩阵与正定柯西矩阵分解实现。精确秩本身不直接给出任意凸校准代理的维度下界。因此我们直接分析F1的贝叶斯几何结构，构造一个分布，其中恰好所有固定核心标签集的超集均为贝叶斯最优解，且对应活动损失列在见证支持集上具有仿射维数hn，其中n=s−⌊s/3⌋，h=⌈(s⌊s/3⌋)^{1/2}⌉−1。应用可行子空间法得到凸校准维度下界：CCdim(L^{F₁}) ≥ (2/(3√3)−o(1))s²。结合已知的二次上界，得出CCdim(L^{F₁}) = Θ(s²)。
原文摘要 · Abstract (English)
The instance-wise $F_1$ measure is a central performance measure for multi-label classification. For a problem with $s$ labels, it defines a $2^s\times 2^s$ loss matrix. Previous work exhibited $s^2+1$-coordinate affine and shifted low-rank representations and used them to construct quadratic-dimensional convex calibrated surrogates. We determine the exact rank. Under the convention $F_1(\varnothing,\varnothing)=1$, the $F_1$ score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank $s^2-s+2$, while the column-affine dimension of the loss is $s^2-s+1$. The proof factors the nonempty score matrix through subset-incidence matrices and a positive-definite Cauchy matrix. Exact rank does not, by itself, lower-bound the dimension of an arbitrary convex calibrated surrogate. We therefore analyze the Bayes geometry of $F_1$ directly. We construct a distribution for which precisely all supersets of a fixed core label set are Bayes optimal, and show that the corresponding active loss columns, restricted to the witness support, have affine dimension $hn$, where $n=s-\lfloor s/3\rfloor$ and $h=\lceil(s\lfloor s/3\rfloor)^{1/2}\rceil-1$. Applying the feasible-subspace lower bound for convex calibration dimension gives \[ \operatorname{CCdim}(L^{F_1}) \ge \left(\frac{2}{3\sqrt{3}}-o(1)\right)s^2. \] Together with the quadratic upper bound, this establishes $\operatorname{CCdim}(L^{F_1})=Θ(s^2)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。