在正样本学习中引入平滑分析,使几乎所有类别都可学习。
Smoothed Analysis of Learning from Positive Samples
- 假设真实分布相对于参考分布平滑,打破原有不可学习的困境
- 所有VC类可在O(VC/ε²)个正样本下实现ε误差分类
- 适用于生物信息学、生态学等依赖启发式方法的场景
从仅含正样本的二分类是PAC学习的一种变体,学习者仅接收独立同分布的正样本,目标是学习一个低误差的分类器。以往研究显示,在最坏情况下几乎无有意义类别可学习,包括二维半空间。这给生物信息学、生态学等领域的实践带来挑战,因从业者依赖启发式方法。本文首次对正样本学习进行平滑分析,假设真实分布 $D^*$ 相对于参考分布 $D$ 是平滑的。与最坏情况相反,我们证明所有VC类在平滑模型中均可学习,仅需 $O(VC/ε^2)$ 个正样本即可达到 $ε$ 分类误差。此外,我们提出一种高效算法,适用于能被次数为 $k$ 的多项式以 $ ext{poly}(ε)$ 精度逼近且在L1范数下下界为常数的类别,运行时间为 $ ext{poly}(d^k/ε)$,定性上匹配L1回归。该结果还推导出更快速或更通用的算法:(1) 未知截断下的估计,首次给出指数族参数的多项式时间估计方法,基于截断集可由非负多项式在L1范数下逼近;(2) 广义截断检测,适用于非乘积分布,优于[DLNS STOC24]仅限乘积分布的限制;(3) 从一组参考分布中学习,当样本来自 $O(1)$ 个分布之一且其满足平滑性时,适用于列表解码算法从污染数据中学习采样器 $D^*$。
原文摘要 · Abstract (English)
Binary classification from positive-only samples is a variant of PAC learning where the learner receives i.i.d. positive samples and aims to learn a classifier with low error. Previous work by Natarajan, Gereb-Graus, and Shvaytser characterized learnability and revealed a largely negative picture: almost no interesting classes, including two-dimensional halfspaces, are learnable. This poses a challenge for applications from bioinformatics to ecology, where practitioners rely on heuristics. In this work, we initiate a smoothed analysis of positive-only learning. We assume samples from a reference distribution $D$ such that the true distribution $D^*$ is smooth with respect to it. In stark contrast to the worst-case setting, we show that all VC classes become learnable in the smoothed model, requiring $O(VC/ε^2)$ positive samples for $ε$ classification error. We also give an efficient algorithm for any class admitting $\mathrm{poly}(ε)$-approximation by degree-$k$ polynomials whose range is lower-bounded by a constant with respect to $D$ in L1-norm. It runs in time $\mathrm{poly}(d^k/ε)$, qualitatively matching L1-regression. Our results also imply faster or more general algorithms for: (1) estimation with unknown-truncation, giving the first polynomial-time algorithm for estimating exponential-family parameters from samples truncated to an unknown set approximable by non-negative polynomials in L1 norm, improving on [KTZ FOCS19; LMZ FOCS24], who required strong L2-approximation; (2) truncation detection for broad classes, including non-product distributions, improving on [DLNS STOC24]'s who required product distributions; and (3) learning from a list of reference distributions, where samples come from $O(1)$ distributions, one of which witnesses smoothness of $D^*$, as arises when list-decoding algorithms learn samplers for $D^*$ from corrupted data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。