Jun, 2024

多项式阈值函数可测学习

PDF
TL;DR该研究论文介绍了可测试学习的概念，并研究了在测试者接受标准高斯数据的情况下，多项式阈值函数的可测试学习。研究结果表明，任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习，与测试属性的典型模型相匹配。同时，该研究证明了直接证明可测试学习（而非愚弄测试者）的方法在多项式阈值函数上是行不通的。
testable learningagnostic modelgaussian datapolynomial threshold functionsfooling
发现论文，激发创造
  • 应对噪声的几何概念学习

    我们研究了在部分数据遭到敌对噪声污染的情况下，几何概念类（特别是低次多项式阈值函数（PTF）和半空间的交集）的高效可学习性，并给出了这些概念类的首个多项式时间 PAC 学习算法，具有不依赖于维度的误差保证。

    Jul, 2017

  • 多项式的超非奇异分解及其在鲁棒学习低次 PTF 中的应用

    我们研究了在存在恶意污染的情况下低次多项式阈值函数（PTFs）的高效学习性能。我们的主要算法结果是在强污染模型下，基于高斯分布的概念类的多项式时间 PAC 学习算法，具有 $O_{d, c}(ext {opt}^{1-c})$ 的误差保证，其中 $c>0$ 为常数，$ ext {opt}$ 为污染比例。我们的算法采用了一个受线性阈值函数学习环境启发的迭代方法，使用鲁棒感知器算法计算一个良好的部分分类器，并对未分类的点进行迭代。为了实现这一点，我们需要利用一些多项式不等式定义的集合，并将其划分为几个行为良好的子集。为此，我们开发了一些可能具有独立兴趣的新多项式分解技术。

    Mar, 2024

  • 具有分布转变的可测试学习

    在学习分布转移的基本问题中，我们提出了一个新模型，称为可测试学习，可以通过一个相关的测试来得到分类器在测试分布上的性能证明，并证明了对于一些常见概念类别如半空间、半空间的交、决策树等，以及具有低次 $L_2$- 夹逼多项式逼近器的任何函数类别都可以在这个模型下学习。

    Nov, 2023

  • 属性高效的带有恶意噪声的低次多项式阈值函数 PAC 学习

    论文研究了稀疏度 - d 多项式阈值函数的属性稀疏特性和机器学习的 PAC 学习方法，提出了一种新算法，使用仅限 Frobenius 范数来验证好的近似或识别受污染样本的杂音过滤器。

    Jun, 2023

  • 一种对半空间进行不可知学习的 PTAS 算法

    本文提出了一个以多项式回归和定位技术相结合的算法， 用于在 d - 球上均匀分布的情况下，实现对零时最佳半空间分类器的确定性多项式近似方案（PTAS），误差保证为 opt 的 (1+μ)+ε 倍， 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。

    Oct, 2014

  • 测试者学习半空间的通用算法

    本研究提出了一种普适性的半空间测试学习算法，它可以在所有满足 Poincaré 不等式的分布上获得较小误差，具体实现是使用 sum-of-squares 算法检查分布的超对称性。

    May, 2023

  • 学习半空间的复杂性理论限制

    该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

    May, 2015

  • 分布无关可靠学习

    研究可靠的不可知学习框架中的问题，使用单边多项式逼近可学习可靠分类器和构建适当的单边多项式逼近来学习大多数时完全可靠，这些算法还满足强属性效率属性并提供样本复杂度和运行时间之间的平滑折衷。

    Feb, 2014

  • 关于交互证明学习的能力

    我们针对不均衡分布学习问题，构建了一种双效证明系统的交互式协议，该协议能够学习给定函数的最大傅立叶特征，学习类 AC^0 [2] 和 k-juntas。此外，我们还提供了一个用于布尔函数学习的新模型，样本复杂度与 n 无关。

    Apr, 2024

  • 半空间学习单项式是困难的

    该研究证明了在符合某些要求的示例分布下，多项式的弱会混淆学习几乎不可能，即使在输出更大的概念类的假设的情况下也是如此，这种难度结果从某种程度上包括以前的研究结果，包括最近的对单项式和半空间的适当学习的难度结果。

    Dec, 2010