为什么 PAC 学习侧重于假设类的可学习性而不是目标函数?

数据挖掘 pac学习
2022-03-10 23:33:01

PAC学习的定义大致是

一个算法是一个 PAC 学习算法,如果它给定足够的数据,对于任何目标函数,它在给定它能够表示的函数的情况下尽可能地渐近地做。

这个定义似乎有点野心。实际上,我更关心在绝对意义上很好地逼近目标函数,而不仅仅是逼近它以及我的假设类可以召集。根据某种无免费午餐原则,可能不可能对所有目标函数都这样做,因此我们需要对在一类目标函数上学习良好的算法感到满意。如果我要尝试定义“学习”的概念,它看起来像这样:

算法学习一个类中的随机变量X×R如果对任何(X,),那么对于任何δ,ε,给定足够的独立同分布样本(X,),算法返回一个函数H这样(|H(X)-|ε)>1-δ.

一类如果存在学习它的算法,则随机变量的数量是可学习的。

我有两个问题:

  1. 为什么要强调获得近似假设类的良好界限,而不是目标函数/分布,而我们确实关心的是后者?
  2. 像我的定义这样的东西也被研究过吗?
1个回答

公平的警告,这只是一种直觉,我并不是这类问题的专家。无论如何,好问题:)

像 PAC 这样的学习理论模型旨在用于证明可学习性结果。因此,重要的不仅是定义对应于“学习”意味着什么的直觉,而且实际上在技术上可以用这个定义证明任何事情。我怀疑这就是为什么(或其中一个原因)PAC 定义受限于算法处理的特定函数类,因为它可以从理论上确定什么是该类中真正的最佳函数。这需要证明(或反驳)算法总是可以返回它。

我还怀疑在所有可能函数的宇宙中,最优函数总是可能是某种无限的非泛化函数,它准确地分配了真实的对于任何X(至少在可能的范围内,即当XX'')。从这个角度来看,限制目标函数的类别会迫使算法进行泛化,因为它必须在函数类参数的有限空间中表示数据。

这可以解释为什么 OP 提出的定义不可用:如果我没记错的话,根本没有办法用它来证明任何可学习性结果。