一个与 ZF 公理无关的学习问题
近期的学习研究显示,学习问题的可学习性可能是不可判定的,或者与标准集合论的 ZFC 公理无关。此外,这些问题的可学习性可能不是有限特性:简单来说,通过检查问题的有限投影无法检测出可学习性。然而,学习理论在定义学习的维度时充斥着只考虑问题的有限限制的概念,即具有有限特性的性质。如何调和这些结果呢?具体而言,哪些学习问题容易受到逻辑不可判定性的影响,哪些问题可以用有限特性来解决?我们证明了具有测度损失的监督学习的困难可以通过有限特性来精确描述。尤其是我们证明了学习一个假设类的样本复杂度可以通过检查其有限投影来判断。对于广泛类别的适当损失函数的可实现和了解学习,我们证明了一个确切的紧致性结果:一个类别在具有给定样本复杂度时可以学习,仅当其所有有限投影也是如此。对于具有不适当损失函数的可实现学习,我们证明了样本复杂度的确切紧致性可能会失败,并提供了样本复杂度相差 2 倍的相匹配上下界。我们猜想对于了解学习的情况可能存在更大的差距。我们技术工作的核心是一个关于变量分配的紧致性结果,它在保持函数类别在目标值以下方面具有广泛的兴趣,该结果推广了霍尔(Hall)经典匹配定理,可能具有独立的兴趣。
Feb, 2024
本文提供了一个关于期望最大化 (EM) 算法应用于高维潜变量模型推断的一般理论。作者提出了一个新的高维 EM 算法,自然地融入了稀疏结构到参数估计中。基于估计值,作者提出了新的推论程序来测试假设并构建置信区间。这个算法针对广泛的统计模型,提供了高维最先进的估计和渐近推断的第一个可计算的方法。
Dec, 2014
在本文中,我们提出了一种新的损失函数和一种计算高效的估计器,它在温和条件下是一致且渐近正态的。我们将我们的方法视为同一类指数族的重新参数化分布的最大似然估计,并证明我们的估计器可以解释为最小化特定的 Bregman 得分以及最小化代理似然的实例。同时,我们还提供了有限样本保证,以在参数估计中实现误差(在ℓ₂范数中)为 α,样本复杂度为 O (poly (k)/α²)。当定制为节点稀疏马尔可夫随机场时,我们的方法实现了 O (log (k)/α²) 的优化样本复杂度。最后,我们通过数值实验展示了我们估计器的性能。
Sep, 2023
每个学习二进制假设类都具有有限的 VC 维度且可采用一个与 VC 维度无关的有限函数大小的样本压缩方案,然而,每个学习多类假设类都具有有限的 DS 维度且不具有一个与 DS 维度无关的有限函数大小的样本压缩方案。
Aug, 2023
通过本文,我们研究并证明了一种简化的通信高效分布式学习框架,它利用数据子集计算本地最大似然估计量,并结合本地估计值实现对全局 MLE 的最佳近似,并证明了该框架的统计性质与误差率性质。我们还研究了使用 KL 散度方法与更常见的线性组合方法组合本地 MLE 的经验性能,并表明 KL 方法在实际设置中比线性组合方法更为优越,可解决模型错误、非凸性和异构数据分区等问题。
Oct, 2014
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
开发了一种在没有约束条件的情况下近似计算 VC 维度的方法,该方法基于经验风险最小化学习范式,用于表征概念类的粉碎性质。
Aug, 2023
本文研究了样本压缩方案与统计学习之间的关系,探究了学习能力与可压缩性之间的等价性,并在多类别分类问题中研究了统计学习理论。作者证明了在零 / 一损失分类的情况下,可学习性等价于对数样本大小的压缩,并且一致收敛意味着恒定大小的压缩。作者还探究了在 Vapnik 的一般学习设置下压缩能力与学习能力的等价性,并给出了一些在多类别分类问题中的应用。
Oct, 2016