- 私有的 PAC 学习可能比在线学习更困难
根据合理的密码学假设,我们展示了一个概念类别,该类别允许在多项式时间内以多项式错误边界运行的在线学习器,但不存在计算效率高的差异隐私 PAC 学习器。
- 图中球的非冲突教学映射
研究了概念类别的非冲突教学映射 (NCTM) 和带有正例的非冲突教学映射 (NCTM$^+$),并发现与三种图形有关的相关决策问题对于非冲突教学维数 (NCTD) 和 NCTD$^+$ 来说都是 NP 完全的,同时推断出在一些条件下存在算法 - Occam 算法的等价性
通过在 Occam 算法中使用与 δ 无关的复杂性,本研究论文证明了 Board 和 Pitt 的部分对偶定理也适用于其,从而提供了各种理论结果和基于该对偶定理的算法设计方法的事后验证。
- 计算递归教学维度的难度注释
计算概念类的递归教学维度的问题在指数时间假设下需要 n^Ω(log n) 的时间,与问题的暴力算法的运行时间 n^O (log n) 相匹配。
- 普适性学习理论
本文研究了一种更贴近于实际机器学习应用的学习模型,但仍然在学习可能性方面提供了完整的理论,并通过探索万能学习问题的学习曲线发现,每个概念类的学习曲线都以指数、线性或任意缓慢的速率衰减,并提出了最优学习算法来实现每种情况下最佳的可能速率。
- 随机梯度下降能否学习具有可证明泛化性的循环神经网络?
本文研究了 RNN 模型在 PAC 学习语言中所能学习的概念类别以及如何通过渐进多项式时间和样本复杂度来有效地学习一些显著的概念类别,例如使用平滑的双层神经网络从不同的输入信息生成各自的输出信息。
- 基于偏好的教学
介绍了一种新的教学模型 —— 基于偏好的教学,提出了偏好教学维度这个复杂度参数,用于表示在给定的概念类中教授任何概念所需的最差例子数量,通过组合的理论框架,得出了关于偏好教学维度的界限,并研究了在无限类上的性质和应用。
- 使用平滑相对遗憾逼近技术的主动学习及其应用
我们提出了一种基于池泛型主动学习的不同工具,该工具基于学习器计算假设损失和某个固定 “关键” 假设之间差异的估计器能力,进而得到一些显著意义上的主动学习界限,尤其对于那些只依赖于不一致性系数限制的方法在某些问题上无法提供有用边界的情况下。