提出相对误差最优的单调分类算法，首次实现误差仅超最优解一倍。
Monotone Classification with Relative Approximations
- 基于相对近似设计新算法，允许误差比最优值高最多1+ε倍
- 理论证明上下界几乎匹配，覆盖所有ε≥0的情形
- 相比之前只能保证绝对误差的算法，显著提升精度
在单调分类中，输入为ℝ^d中的点集P，每个点带有隐藏标签{-1, 1}。目标是找到一个单调函数h: ℝ^d → {-1, 1}，使分类错误数最小（即与真实标签不一致的点数）。算法代价定义为需查询标签的点数。本文首次研究在误差不超过最优解的(1 + ε) · k*（ε ≥ 0）时，所需的最低查询代价。其中k*为最优单调分类器能达到的最小错误数。对所有ε ≥ 0给出了近乎紧的上下界。此前工作仅能保证绝对误差上界，本工作实现了相对误差近似，具有理论突破意义。
原文摘要 · Abstract (English)
In monotone classification, the input is a multi-set $P$ of points in $\mathbb{R}^d$, each associated with a hidden label from $\{-1, 1\}$. The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $\mathbb{R}^d$ to $\{-1, 1\}$ with a small {\em error}, measured as the number of points $p \in P$ whose labels differ from the function values $h(p)$. The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most $(1 + ε) \cdot k^*$ where $ε\ge 0$ and $k^*$ is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of $ε$. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。