Learning geometric concepts with nasty noise
Learning geometric concepts with nasty noise
复制标题
通过讨厌的噪音学习几何概念
DOI：
10.1145/3188745.3188754
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Stewart, Alistair
中科院分区：
文献类型：
--
作者：
Diakonikolas, Ilias;Kane, Daniel M.;Stewart, Alistair
我们研究了当一小部分训练数据被对抗性破坏时，几何概念类的有效可学习性——特别是低次多项式阈值函数（PTF）和半空间的交集。我们为这些概念类给出了第一个多项式时间 PAC 学习算法，在高斯分布下存在令人讨厌的噪声的情况下具有与维度无关的误差保证。在令人讨厌的噪声模型中，无所不知的对手可以任意破坏未标记数据点及其标签的一小部分。该模型概括了经过充分研究的噪声模型，包括恶意噪声模型和不可知（对抗性标签噪声）模型。在我们的工作之前，已知有效恶意学习算法的唯一概念类是以原点为中心的半空间类。我们结果的核心是一种有效的算法，可以在存在令人讨厌的噪声的情况下逼近任何有界函数的低次 Chow 参数。我们针对 Chow 参数的稳健近似算法为满足温和浓度界限和矩条件的一系列分布族提供了近乎最优的误差保证。在技术层面上，该算法采用迭代“谱”技术进行异常值检测和去除，其灵感来自于鲁棒无监督学习的最新工作，该技术充分利用了低次多元多项式。我们针对低次 PTF 的鲁棒学习算法为一类温和分布提供了与维度无关的误差保证，包括高斯分布，更一般地说，任何具有（近似）已知低次矩的对数凹分布。对于高斯分布下的 LTF，使用定位技术的细化，我们给出了一种多项式时间算法，该算法实现了 O(є) 的接近最优误差，其中 є 是噪声率。我们针对半空间相交的稳健学习算法通过向下投影到适当的低维子空间来进行。它的正确性充分利用了具有独立意义的新颖的稳健逆独立引理。
We study the efficient learnability of geometric concept classes — specifically, low-degree polynomial threshold functions (PTFs) and intersections of halfspaces — when a fraction of the training data is adversarially corrupted. We give the first polynomial-time PAC learning algorithms for these concept classes withdimension-independenterror guarantees in the presence ofnasty noiseunder the Gaussian distribution. In the nasty noise model, an omniscient adversary can arbitrarily corrupt a small fraction of both the unlabeled data points and their labels. This model generalizes well-studied noise models, including the malicious noise model and the agnostic (adversarial label noise) model. Prior to our work, the only concept class for which efficient malicious learning algorithms were known was the class oforigin-centeredhalfspaces.At the core of our results is an efficient algorithm to approximate thelow-degree Chow-parametersof any bounded function in the presence of nasty noise. Our robust approximation algorithm for the Chow parameters provides near-optimal error guarantees for a range of distribution families satisfying mild concentration bounds and moment conditions. At the technical level, this algorithm employs an iterative “spectral” technique for outlier detection and removal inspired by recent work in robust unsupervised learning, which makes essential use of low-degree multivariate polynomials.Our robust learning algorithm for low-degree PTFs provides dimension-independent error guarantees for a class of tame distributions, including Gaussians and, more generally, any logconcave distribution with (approximately) known low-degree moments. For LTFs under the Gaussian distribution, using a refinement of the localization technique, we give a polynomial-time algorithm that achieves a near-optimal error ofO(є), where є is the noise rate. Our robust learning algorithm for intersections of halfspaces proceeds by projecting down to an appropriate low-dimensional subspace. Its correctness makes essential use of a novel robust inverse independence lemma that is of independent interest.
登录
查看更多内容
限制多项式阈值函数的平均灵敏度和噪声灵敏度
DOI：
--
发表时间：
2010
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Ilias Diakonikolas;P. Harsha;Adam R. Klivans;Raghu Meka;Prasad Raghavendra;Rocco A. Servedio;Li
通讯作者：
Li
DOI：
10.1145/62212.62238
发表时间：
1993-08
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Kearns;Ming Li
通讯作者：
M. Kearns;Ming Li
DOI：
10.1137/1.9781611975031.171
发表时间：
2017-04
期刊：
ArXiv
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
d次多项式阈值函数的高斯表面积和噪声灵敏度
DOI：
--
发表时间：
2010
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
D. Kane
通讯作者：
D. Kane
影响因子：
1.2
作者：
D. Kane
通讯作者：
D. Kane