证明结构化SVM的常见测地线条件不足以保证最优解为贝叶斯解。
Common Geodesics Do Not Guarantee Fisher Consistency of the Structured SVM: Minimal Counterexamples and a Tree-Metric Classification
- 发现四输出星形结构存在严格非贝叶斯最优解
- 树度量下仅路径型树满足最大化一致性
- 最小反例为四输出星形或K_{2,3}图结构
已知结构化支持向量机实现费雪一致性的必要条件是任务损失为存在共测地线的度量。本文证明该条件对标准坐标argmax解码器不充分:四输出星形结构存在精确最优得分向量,其最大化者全为严格非贝叶斯解,且四输出为满足该条件的最小反例。我们完全分类了输出空间为顶点集的正权树度量:argmax一致性成立当且仅当树为路径。分支树上的失败局限于边界分布;所有树在满支持分布上均保持argmax性质。在满足共同测地线条件的度量中,五输出是满支持反例的必要与充分条件;K_{2,3}是无限族K_{m,n}中最小成员。此外,还给出三维汉明立方体的满支持反例。所有最优性声明均有精确的原始-对偶证书。反例揭示了具体解码差距:在此多面体设定下,嵌入可保证校准连接的存在,却无法验证每个代理风险最小化器上的指定argmax连接。
原文摘要 · Abstract (English)
A known necessary condition for Fisher consistency of the structured support vector machine requires the task loss to be a metric for which every output triple has a common geodesic point. We show that this condition is not sufficient for the canonical coordinate-wise argmax decoder. A four-output unit star admits an exactly optimal score vector whose maximizers are all strictly non-Bayes, and four outputs are minimal among metrics satisfying the condition. We then completely classify positively weighted tree metrics whose vertex set is the output space: argmax consistency holds if and only if the tree is a path. The failure on branching trees is confined to boundary distributions; every tree retains the argmax property at every full-support distribution. Among metrics satisfying the common-geodesic condition, five outputs are necessary and sufficient for a full-support counterexample; $K_{2,3}$ is the smallest member of an infinite $K_{m,n}$ family. We additionally give a full-support counterexample for the three-dimensional Hamming cube. All optimality claims have exact primal-dual certificates. The counterexamples expose a concrete decoder gap: in this polyhedral setting, an embedding can guarantee the existence of a calibrated link without validating a prescribed argmax link on every surrogate-risk minimizer.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。