提出高效算法，在恶意噪声下仍能学习多分类线性模型。
Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
- 用聚类剪枝+多分类铰链损失，实现噪声鲁棒学习。
- 仅需O(k²(d log d + log k))样本，即可在恒定噪声率下学习。
- 适用于高维多分类场景，尤其适合对鲁棒性要求高的应用。
噪声容忍的PAC学习线性模型是机器学习领域的核心问题。近年来，针对多种噪声模型下的线性阈值函数学习，已提出许多计算高效的算法。然而，在多分类情形（类别数k≥3）下，当数据被恶意污染时，是否存在计算高效的PAC学习算法仍未知。本文考虑边际分布为有界方差分布的混合分布，并满足分类边界条件。我们证明存在一个计算高效的算法，可使用至多O(k²(d log d + log k))个样本，即使在恒定比例的恶意噪声下，仍能学习多分类线性分类器{h_w: x ↦ argmax_{y∈[k]} w_y·x, x∈ℝ^d, w∈ℝ^{kd}}。该算法包含两个核心部分：基于聚类的剪枝策略与标准的多分类铰链损失最小化程序。即使在二分类情形（k=2），本结果也优于所有已有工作。
原文摘要 · Abstract (English)
Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes $k$ is at least $3$, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers $\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}$ using at most $O(k^2\cdot (d\log d+\log k))$ samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e. $k=2$, our result is strictly stronger than all prior works.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。