使用 0-1 损失函数学习基于核的半空间
本研究提出了一种普适性的半空间测试学习算法,它可以在所有满足 Poincaré 不等式的分布上获得较小误差,具体实现是使用 sum-of-squares 算法检查分布的超对称性。
May, 2023
研究非凸经验风险最小化法,通过多次随机初始化加优化步骤实现学习半空间和神经网络,并证明了学习数据以大于零的常数保持可分的神经网络的可学习性质,以及数据标签随机翻转的情况下的学习结果。
Nov, 2015
通过与半空间和所谓的并行煎饼分布的新颖联系,我们以统一的方式获得了较强(而且令人惊讶地简单)的在不适当的情况下学习半空间交集的下界,这是过去几年强大的高维统计学中许多下界构造的核心,我们还给出了统计查询框架下的无条件难度结果。
Feb, 2024
研究如何在噪音下进行有效的学习,在保证计算效率的前提下设计了一种主动学习算法,并根据半空间的结构进行加权和风险最小化等方法的技术优化,解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。
Jun, 2020
通过对未知对称一维对数凹分布的 d 维空间的 d 倍积的未知仿射变换的环境分布内带有一定间距的高维半空间的多项式时间学习算法,从一个组分分布的数据中删除至少一个 ε 分数的数据引入了半空间。值得注意的是,我们的算法不需要标签,并在这种分布假设下确立了隐藏半空间的独特性(以及高效性)。该算法的样本和时间复杂度在维度和 1/ε 上是多项式的。该算法只使用经验分布的适当重新加权的前两个矩,我们称之为对比矩;其分析使用了关于广义狄利克雷多项式的经典事实,并且关键地依赖于对对数凹分布截断的矩比的新的单调性属性。此前的研究处理了当底层分布是通过非高斯成分分析来进行的非高斯分布的特殊情况。我们通过提供基于总变分距离而不是现有的可以是超多项式的矩边界保证,改进了这一点。我们的工作也是在这个设置中首次超越高斯分布。
Nov, 2023
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
传统的监督学习模型中,学习器的目标是基于一些类别中最适应的概念,通过学习任意分布的示例,输出一个与之相差不超过 epsilon 的假设。本研究引入了平滑分析框架,要求学习器只需与对小的随机高斯扰动具有鲁棒性的最佳分类器竞争,从而提供了广泛的学习结果。此类别包括依赖于低维子空间(即多索引模型)和具有有界高斯曲面积的概念。有趣的是,我们的分析还为传统的非平滑框架(如学习边际)提供了新的结果。特别地,在时间复杂度为 k ^poly(log(k)/(epsilon * gamma))的算法中,我们首次获得了关于 k 半空间求交的无偏学习算法,这里 gamma 是边际参数。在之前的工作中,最优的运行时间复杂度是指数级的(Arriaga 和 Vempala,1999 年)。
Jul, 2024
本文提出了一种半空间主动学习算法,能够在存在噪声和尽可能少的标签情况下,有效地学习均匀分布在单位球上的均匀半空间,并证明其在两种噪声情况下均达到了近似最优标签复杂度。
Feb, 2017
本文提出了一个以多项式回归和定位技术相结合的算法, 用于在 d - 球上均匀分布的情况下,实现对零时最佳半空间分类器的确定性多项式近似方案(PTAS),误差保证为 opt 的 (1+μ)+ε 倍, 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。
Oct, 2014