2026-09-19

1984年，莱斯利·瓦利安特（Leslie Valiant）提出了PAC学习理论（Probably Approximately Correct Learning），它为机器学习提供了第一个严格的数学分析框架，将学习问题从哲学思辨转变为可证明的计算问题，精确地定义了在什么条件下、以何种代价，学习可以被认为是可行的（即多项式），奠定了现代机器学习理论分析的基础范式。

具体协议允许两种信息供应。首先，学习者可以获得典型数据，这些数据正面例示概念。更精确地说，假设这些正例具有由自然任意决定的概率分布。调用例程 EXAMPLES 会产生一个这样的正例。产生不同示例的相对概率由分布决定。第二种可能可用的信息源是例程 ORACLE。在其最基本版本中，当向它呈现数据时，它会告诉学习者该数据是否正面例示该概念。

剩下的主要设计选择是知识表示。既然我们宣称目标是表示一般知识，似乎几乎不可避免地要使用某种逻辑，而不是例如形式文法或几何构造。在本文中，我们将概念表示为命题变量集合的布尔函数。我们试图推导的识别算法因此将是布尔电路或表达式。

命题演算在实践学习系统中表示知识的充分性显然是一个关键且有争议的问题。很少有人会争辩说这种能力不必要。问题是它是否足够。有若干论据表明，这样的系统至少是一个很好的开端。首先，当考察体现预编程知识的最著名系统，即专家系统如 DENDRAL 和 MYCIN 时，本质上没有使用超出命题演算的逻辑记号。如果试图把学习系统建立在比已成功管理的编程系统更强的表示上，那肯定过于雄心勃勃。其次，本文结果可以被负面地解释为表明，即使在命题演算内，可学习概念类也受到严重限制。这表明，寻找具有显著更大可学习类的命题演算扩展可能是困难的。

本文的正面结论是，使用所述类型的学习协议，有一些特定概念类可在多项式时间内学习。这些类都可以通过定义识别它们的程序类来刻画。在每种情况下，程序都是特殊类型的布尔表达式。这三类是：(1) 每个子句有界数量文字的合取范式表达式；(2) 单调析取范式表达式；(3) 每个变量只出现一次的任意表达式。第一类不需要调用预言机。最后一类不需要访问典型例子，但预言机需要比上述更强大。

推导过程在每种情况下都会输出一个表达式，它以高概率紧密逼近待学习表达式。这样的近似表达式从不在不应说“是”时说“是”，但可能在一小部分概率空间的正例上说“否”。通过增加推导过程的运行时间，这个比例可以任意小。也许本文包含的主要技术发现是，在这种概率学习概念下，对于整类布尔函数，高度收敛的学习是可能的。这似乎将本方法与更传统的方法区分开来，后者将学习视为从不足以进行可靠推导的信息中“归纳”出某种一般规则的过程。这种概率观点的力量可由以下事实说明：任意多项式多个正例集合不能被可靠地用来确定甚至仅由单个单项式组成的表达式。关于这一方法论问题的更详细描述可见 [9]。

我们表述的另一个值得强调的方面是：在一个即将学习新概念的学习系统中，可能有数量巨大的命题变量可用。这些变量可能是原始输入、预编程概念的值，或先前已学习概念的值。我们希望学习新概念的复杂度只与自然例子中可能被设置的变量数量有关，而不依赖于可用变量全集的基数。因此，向 ORACLE 提出的问题和 EXAMPLES 给出的值不会是所有变量的真值赋值。在典型情况下，它们将指定对变量子集的赋值，而该子集仍足以保证函数的真值。

可学习布尔概念类是否能显著扩展到上述三类之外，是一个有趣问题。然而，来自密码学的间接证据表明，由多项式规模电路可计算的所有函数类并不可学习。考虑一个密码方案，它通过计算函数 E_k 来编码消息，其中 k 指定密钥。假设该方案对选择明文攻击免疫，即即使已知 E_k 在多项式多个动态选择输入上的值，要推导出 E_k 或其近似的算法在计算上也不可行。然而，这等价于说 E_k 不可学习。因此，猜想存在的易于计算的良好密码函数意味着有些易于计算的函数不可学习。

如果可学习概念类如我们的结果所暗示的那样受到严重限制，那么教授更复杂概念的唯一方式就是从这些简单概念构建它们。因此，好老师必须像程序员那样识别、命名并排序这些中间概念。可学习性理论的结果将表明无需编程即可获得的单个概念的最大粒度。

总结来说，本文试图探索算法复杂性所允许的可学习之物的界限。其结果与先前大量学习工作不同，因为它们试图调和前面提到的三个性质 (1)-(3)。在严格性上最接近我们方法的是归纳推理文献（见 Angluin 和 Smith [1] 综述），它处理从例子中归纳递归函数或形式文法（但不是布尔函数）。有大量关于模式识别和分类的工作，使用统计和其他工具（例如 [4]），但一般知识表示问题在那里未被直接处理。各种不太形式意义上的学习已作为人工智能分支被广泛研究。综述和参考文献见 [2,7]。在他们的术语中，本文主题是概念学习。

在先前关于学习的工作中，许多重点放在人类似乎使用的多样方法上。这些包括从例子学习、通过类比学习、通过被告知学习。本文强调通过被编程学习和在没有任何编程元素情况下学习之间的对立。许多传统上接受的学习模式可视为这两个极端的混合。

2. 布尔函数的学习协议

我们考虑 t 个布尔变量 p_1,\ldots,p_t，每个可取 1 或 0，以指示相关命题为真或假。不假设变量独立。事实上，它们可能是彼此的函数。

向量是对 t 个变量中每一个赋予来自 {0,1,\star} 的值。符号 \star 表示变量未确定。如果每个变量都确定（即赋值为 {0,1} 中的值），则向量是完全的。例如，赋值 p_1=p_3=1，p_4=0，p_2=\star 是一个非完全向量。

布尔函数 F 是从 2^t 个完全向量集合到 {0,1} 的映射。如果将其定义域扩展到所有向量集合，布尔函数 F 变成概念 F，如下：对于向量 v，F(v)=1 当且仅当对于所有与 v 在所有 v 已确定变量上一致的完全向量 w，都有 F(w)=1。这种扩展的目的是允许我们不提及 F 不依赖的变量。

给定概念 F，我们考虑在所有满足 F(v)=1 的向量 v 集合上的任意概率分布 D。换言之，对每个满足 F(v)=1 的 v，有 D(v)\ge 0。并且当在这个向量集合上求和时 \sum D(v)=1。对 D 没有其他假定限制，它意在描述 F 的正例在自然界中出现的相对频率。

哪些是合理的学习协议？首先必须避免给教师太多权力，即逐条指令传达程序的权力。例如，如果可以传达一个预先策划的带重复向量序列，那么即使只用两个这样的向量进行二进制记法，也可以用来编码程序描述。其次必须避免给教师明显太少的权力。特别是，协议必须提供一些 F 为真的典型向量例子，否则，如果 F 仅对一个完全向量为真，那么只有指数搜索或更强大的预言机才能找到它。

这些考虑使我们考虑以下学习协议是合理的。它让学习者访问以下两个例程：

EXAMPLES：无输入。输出一个满足 F(v)=1 的向量 v。对每个这样的 v，任意单次调用输出 v 的概率是 D(v)。
ORACLE()：以向量 v 为输入，根据 F(v)=1 还是 0 输出 1 或 0。

第一个给出随机选择的正例。第二个提供测试，判断推导过程认为关键的向量是否是概念的例子。在真实系统中，预言机可能是人类专家、过去观察数据库、某种演绎系统或它们的组合。

最后我们注意到，我们特定选择的学习协议强烈受到早先决定处理概念而非原始布尔函数的影响。如果处理后者，则许多其他替代方案同样自然。例如，给定向量 v，我们可以问是否存在任何完成使它为真，而不是像我们那样问是否所有完成都使函数为真。这提示 EXAMPLES 和 ORACLE 的自然替代语义。在第 7 节我们将使用这种更精细的预言机。

3. 可学习性

我们将考虑各种以 p_1,\ldots,p_t 为输入的程序类，并表明在每种情况下，该类中任何程序都可以使用前述协议在多项式时间内以很小误差概率推导出来。我们假设程序可取 1、0 和未确定值。

更精确地说，我们说程序类 X 相对于给定学习协议是可学习的，当且仅当存在一个算法 A（推导过程）调用该协议，具有以下性质：

算法运行时间在可调参数 h、量化待学习程序大小的各种参数以及变量数 t 中都是多项式。
对所有程序 f\in X 和所有在 f 输出 1 的向量 v 上的分布 D，算法将以至少 (1-h^{-1}) 的概率推导出一个程序 g\in X，它从不在不应输出 1 时输出 1，但在应输出 1 时几乎总是输出 1。特别地，(i) 对所有向量 v，g(v)=1 蕴含 f(v)=1；(ii) 对所有满足 f(v)=1 但 g(v)\ne 1 的 v，D(v) 之和至多为 h^{-1}。

在我们的定义中，我们不允许 g 的正回答出错，仅因为本文中的特定类 X 不需要它。我们称之为单侧误差学习。在其他情况下，允许双侧误差可能更有效。在更一般的情况下，我们需要在满足 f(v)\ne 1 的向量集合上放一个概率分布 \bar D。条件 (2) 中的 (i) 则替换为：对所有满足 f(v)\ne 1 但 g(v)=1 的 v，\sum \bar D(v) 至多为 h^{-1}。

我们定义的第二个方面是参数 h 用于两个独立概率界。这简化了结果陈述。然而，更精确地应显式使用两个独立参数 h_1 和 h_2。

第三，我们应注意，计算概念的程序应与仅计算布尔函数的程序区分。这种区别对我们考虑的三类表达式后果很小，因为在这些情况下，概念的程序直接来自表达式规格。为了一般性，我们的定义确实允许程序值未定义，因为非完全向量一般不会把表达式值确定为 0 或 1。

除了引言中提到的非正式密码学证据之外，获得表明无限制布尔电路类不可学习的负面结果将很有趣。最近一个结果 [6] 在此方向上确实在整数分解不可处理的假设下确立了这一点。他们的结果适用于由 EXAMPLES 和 ORACLE 组成的学习协议，其中后者限制在完全向量上。朝相反方向探索也可能有趣，例如确定 P=NP 假设是否意味着所有有趣类都可学习。

4. 一个组合界

我们后续结果所需的概率分析可以抽象为一个引理。该引理的证明独立于本文其余部分。

对任何大于 1 的实数 h 和任何正整数 S，定义函数 L(h,S) 如下：令 L(h,S) 为最小整数，使得在 L(h,S) 次独立伯努利试验中，每次成功概率至少为 h^{-1}，成功次数少于 S 的概率小于 h^{-1}。

函数 L(h,S) 与学习的相关性可如下说明。考虑一个瓮 U，包含非常多的弹珠，可能有许多不同类型。假设我们想通过取小随机样本 X 来“学习”U 包含哪些类型的弹珠。如果 U 中所有弹珠都是不同类型，那么显然无法推断太多信息。然而，假设我们知道只有 S 种类型，并且希望选择 X，使其包含 U 中除 1% 以外所有弹珠的代表。无论 S 种类型的各自频率如何，L(h,S) 的定义意味着如果

=L(100,S)，那么以大于 99% 的概率我们将成功。要理解为何此蕴含成立，假设在 L(100,S) 次连续选择后，代表瓮中至少 1% 的弹珠类型仍未被选中。在这种情况下，我们进行了 L(100,S) 次伯努利试验，每次成功概率至少 1%（即选中一个先前未选类型），并且成功少于 S 次（因为仍有某类型未被选中）。注意这里何谓成功取决于先前选择。然而，成功概率总是至少 1%，独立于先前选择，这足以支持我们的论证。以下简单上界在整个 S 和 h 值范围内成立，并表明 L(h,S) 本质上在 h 和 S 上都是线性的。

命题： 对所有整数 S\ge 1 和所有实数 h>1， \(L(h,S) \le 2h(S+\log h).\)

证明： 我们使用以下三个著名不等式，最后一个归功于 Chernoff（见 [6] 第 18 页）。

对所有 x>0，(1+x^{-1})^x<e。
对所有 x>0，(1-x^{-1})^x<e^{-1}。
在 m 次独立试验中，每次成功概率至少为 p，成功次数至多为 k 的概率，其中 k<mp，至多为 \(\left(\frac{m-mp}{m-k}\right)^{m-k}\left(\frac{mp}{k}\right)^k.\)

上述表达式中的第一个因子可重写为 \(\left(1-\frac{mp-k}{m-k}\right)^{\frac{m-k}{mp-k}(mp-k)}.\) 使用 (2) 并令 x=(m-k)/(mp-k)，可将乘积上界为 \(e^{-mp+k}(mp/k)^k.\) 代入 m=2h(S+\log h)，p=h^{-1}，k=S，并使用以 e 为底的对数，得到界 \(e^{-2S-2\log h+S}\cdot [2(1+(\log h)/S)]^{(S/\log h)\log h}.\) 使用 (1) 并令 x=(\log h)/S 重写，得到 \(e^{-S-2\log h}\cdot 2^S\cdot e^{\log h}\le (2/e)^S\cdot e^{-\log h}\le h^{-1}.\)

作为应用示例，假设我们可以访问 EXAMPLES，即概念 F 的自然正例向量来源。假设我们想找到变量子集 P 的近似，这些变量在 F 的至少一个自然例子中被确定。考虑以下过程：选取 EXAMPLES 提供的前 L(h,

) 个向量，令 P’ 为这些向量所确定变量集合的并集。定义意味着以至少 1-h^{-1} 的概率，集合 P’ 将具有以下性质：如果按分布 D 选择一个向量，那么它确定 P-P’ 中变量的概率小于 h^{-1}。上述关于瓮模型的论证如下确立这一点：如果 P’ 不具有所声称的性质，那么发生了以下情况：进行了 L(h,

) 次试验（即调用 EXAMPLES），每次成功概率大于 h^{-1}（即找到一个确定 P-P’ 中变量的向量），但成功少于

次（即发现 P’ 的新增元素）。根据 L 的定义，这种情况发生的概率小于 h^{-1}。

上述应用表明，在 F 的自然例子中被确定的变量集合可以由一个运行时间独立于 t（总变量数）的过程来近似。因此，在可学习性定义中，第 (1) 部分对 t 的依赖可以放宽为对正例中曾定义过的变量数量的依赖。

5. 有界 CNF 表达式

合取范式（CNF）表达式是任意乘积 c_1c_2\dots c_r，其中每个子句 c_i 是文字的和 q_1+q_2+\dots+q_i。文字 q 要么是变量 p，要么是变量 p 的否定 \bar p。例如，(p_1+\bar p_2)(\bar p_1+\bar p_2+p_3) 是一个 CNF 表达式。对正整数 k，k-CNF 表达式是每个子句至多 k 个文字之和的 CNF 表达式。

对于一般 CNF 表达式，我们不知道相对于我们的学习协议有任何多项式时间推导过程。是否存在这样的过程这个问题因其表面简单而令人好奇。

在本节中，我们将证明，对任何固定整数 k，k-CNF 表达式类是可学习的。事实上，它很容易学习，因为调用 EXAMPLES 就足够，不需要调用 ORACLE。

在本节及后续各节中，我们将如下使用概念上的关系 \Rightarrow：F\Rightarrow G 意味着对所有向量 v，只要 F(v)=1，也有 G(v)=1。（注意，这等价于将 F,G 视为函数时的关系 F\Rightarrow G。）为简洁起见，我们常把表达式甚至向量表示为其所代表的概念。因此，向量 w 所表示的概念恰好在那些与 w 在所有 w 已确定变量上一致的向量上为真。表达式 f 所表示的概念通过考虑 f 计算的布尔函数并将其定义域扩展为概念而得到。在本节中，我们将子句 c_i 视为一种特殊表达式。在第 7 和 8 节中，我们考虑单项式 m，即文字的简单乘积，作为特殊形式的表达式。在所有情况下，形如 f\Rightarrow g、v\Rightarrow c_i、v\Rightarrow m 或 m\Rightarrow f 的陈述都可以通过将两边解释为概念或函数来理解。

定理 A： 对任何正整数 k，k-CNF 表达式类可通过算法 A 学习，该算法使用 L=L(h,(2t)^{k+1}) 次 EXAMPLES 调用且不调用 ORACLE，其中 t 是变量数。

证明： 算法初始化公式 g 为来自 {p_1,\bar p_1,p_2,\bar p_2,\dots,p_t,\bar p_t} 的所有最多 k 个文字的可能子句的乘积。显然，选择恰好 k 个文字子句的方式数至多 (2t)^k，因此选择最多 k 个文字子句的方式数小于 2t+(2t)^2+\dots+(2t)^k<(2t)^{k+1}。这界定了 g 初始子句数。

算法然后调用 EXAMPLES L 次，以获得 k-CNF 公式 f 所代表概念的正例。对如此得到的每个向量 v，它删除 g 中所有剩余的不包含在 v 中被确定为真的文字的子句（即在被删除的子句中，每个文字要么未确定，要么在 v 中被否定）。更精确地，以下重复 L 次：

begin
  v := EXAMPLES
  for each c_i in g delete c_i if v ⇒ c_i
end

断言是，在块第 L 次执行后，g 的值将以高概率成为正在学习的公式 f 的所需近似。

最初，集合 {v

v\Rightarrow g} 显然为空。我们首先声称，随着算法进行，集合 {v

v\Rightarrow g} 将始终是 {v

v\Rightarrow f} 的子集。为证明这一点，显然只需证明当两个集合都限制在完全向量上时同样陈述成立。令 B 为所有具有以下性质的最多 k 个文字子句 c 的乘积：“\forall v 若 v\Rightarrow f 则 v\Rightarrow c。”显然，在算法过程中，B 中任何子句都不会被删除。因此，确实有 {v

v\Rightarrow g}\subset{v

v\Rightarrow B}。为确立断言，只需证明 B 计算与 f 相同的布尔函数。（事实上，B 将是等价于 f 的最大 k-CNF 公式。）容易看出 f\Rightarrow B，因为根据 B 的定义，对 B 中每个 c，都有“对所有 v，若 v\Rightarrow f 则 v\Rightarrow c”。为验证逆命题 B\Rightarrow f，我们首先注意，根据定义，f 是 k-CNF 公式。如果 f 中某个子句不出现在 B 中，那么该子句 c’ 将具有性质：“\exists v 使得 v\Rightarrow f 但 v\not\Rightarrow c’。”但这不可能，因为如果 c’ 是 f 的子句且 v\not\Rightarrow c’，则 v\not\Rightarrow f。我们得出结论，函数 f 所表示的每个 k-CNF 表示都由 B 中子句集合的子集组成。因此 B\Rightarrow f。

令 X=\sum D(v)，求和遍及所有（不一定完全）满足 v\Rightarrow f 但 v\not\Rightarrow g 的向量 v。该量在算法过程中对每个中间值 g 定义，且容易验证随时间单调递减。现在，当 EXAMPLES 输出一个满足 v\not\Rightarrow g 的向量 v 时，子句将从 g 中删除。在任何时刻发生此事的概率恰好是 X 的当前值。此外，运行算法至完成的过程只有两种可能结果：(1) 在某时刻 X 变得小于 h^{-1}，此时找到的 g 将完全按可学习性定义所要求逼近 f。(2) X 的值从未低于 h^{-1}，因此 g 不是可接受的近似。后一种事件概率至多 h^{-1}，因为它对应于进行 L(h,(2t)^{k+1}) 次伯努利实验（即调用 EXAMPLES），每次成功概率大于 h^{-1}（即找到一个满足 v\not\Rightarrow g 的 v），而成功少于 (2t)^{k+1} 次（一次成功表现为从 g 中删除至少一个子句）。

总之，我们注意到 CNF 表达式 g 立即产生计算相关概念的程序。给定向量 v，我们将已确定的真值代入 g。该概念对 v 为真当且仅当所有子句在代入后都为真。

6. DNF 表达式

析取范式（DNF）表达式是单项式的任意和 m_1+m_2+\dots+m_r，其中每个单项式 m_i 是文字的乘积。例如，p_1\bar p_2+p_1p_3\bar p_4 是 DNF 表达式。这类表达式似乎特别容易让人类理解。因此我们预期任何实践学习系统都必须允许它们。

如果一个表达式中没有变量被否定，则它是单调的。我们将证明，对单调 DNF 表达式，存在一个简单推导过程，同时使用 EXAMPLES 和 ORACLE。对于无限制 DNF，相对于不同的规模度量可以证明类似结果。在无限制情况下，还有额外困难：我们只能保证推导出函数的程序，而不是概念的程序。这一困难在单调情况下不会出现，因为给定表达式，我们总可以通过代入并询问所得表达式是否恒真来计算相关概念在向量 v 上的值。

单项式 m 是函数 F（或表示该函数的表达式）的素蕴含项，如果 m\Rightarrow F，且对从 m 删除一个文字得到的任何 m’，m’\ne F。一个 DNF 表达式是素的，如果它由素蕴含项之和组成，且其中没有一个在“被其他项之和蕴含”的意义下冗余。在单调情况下总存在唯一素 DNF 表达式，但一般情况下不唯一。因此我们定义 DNF 表达式的度为等价于它的素 DNF 表达式可拥有的最大单项式数量。单调情况下的唯一素 DNF 表达式就是所有素蕴含项之和。

定理 B： 单调 DNF 表达式类可通过算法 B 学习，该算法使用 L=L(h,d) 次 EXAMPLES 调用和 dt 次 ORACLE 调用，其中 d 是待学习 DNF 表达式 f 的度，t 是变量数。

证明： 算法初始化公式 g 恒等于常量零。算法然后调用 EXAMPLES L 次，以产生 f 的正例。每次产生一个满足 v\not\Rightarrow g 的向量 v 时，向 g 添加一个新单项式 m。单项式 m 是 v 中确定的、对于使 v\Rightarrow f 必不可少的那些文字的乘积。更精确地，执行 L 次的循环如下：

begin
  v := EXAMPLES
  if v ≠ g then
  begin
    for i := 1 to t do
      if p_i 在 v 中确定 then
      begin
        设 \bar v 等于 v，但 p_i := *
        if ORACLE(\bar v) = 1 then v := \bar v
      end
    设 m 为所有满足 v ⇒ q 的文字 q 的乘积
    g := g + m
  end
end

测试 v\not\Rightarrow g 等价于询问 g 中是否没有任何单项式被 v 中确定为真的值所满足。每当 EXAMPLES 产生一个满足 v\not\Rightarrow g 的值 v 时，算法内层循环将找到一个素蕴含项 m 添加到 g。每个这样的 m 都不同于任何先前添加的（因为相反会意味着 v\Rightarrow g）。由此可知，这样的 v 最多被找到 d 次，因此 ORACLE 最多被调用 dt 次。

令 X=\sum D(w)，求和遍及所有（不一定完全）满足 w\Rightarrow f 但 w\not\Rightarrow g 的向量 w。该量在算法过程中对每个中间值 g 定义，初始为 1，并随时间单调递减。现在，每当 EXAMPLES 输出一个满足 v\not\Rightarrow g 的向量 v 时，就向 g 添加一个单项式。在任何一次调用 EXAMPLES 时发生此事的概率恰好是 X。运行算法至完成的过程只有两种可能结果：(1) 某时 X 变得小于 h^{-1}，此时找到的最终表达式 g 将按可学习性定义所要求逼近 f；(2) X 的值从未低于 h^{-1}，因此 g 不是可接受的近似。第二种事件的概率至多 h^{-1}，因为它对应于进行 L(h,d) 次伯努利实验（即调用 EXAMPLES），每次成功概率大于 h^{-1}（即找到一个满足 v\Rightarrow f 但 v\not\Rightarrow g 的 v），而成功少于 d 次（每次成功表现为添加一个新单项式）。

对于无限制 DNF 表达式，会出现若干问题。主要困难来源是：确定一个非完全向量是否蕴含由 DNF 公式指定的函数是 NP 难的。这仅仅因为确定完全未确定向量是否蕴含该函数就是 Cook [3] 的重言式问题。其直接后果是，假设正在学习的程序计算概念而不是函数是不合理的。另一个后果是，在与算法 B 类似的任何算法中，如果 v 不是完全的，测试 v\not\Rightarrow g 可能不可行。然而，算法 B 足以确立以下结论：

定理 B’： 假设可学习性概念限制在满足以下条件的分布 D 上：只要 v 不是完全向量，就有 D(v)=0。那么 DNF 表达式类是可学习的，其意义是可以在 L(h,d) 次 EXAMPLES 调用和 dt 次 ORACLE 调用中推导出函数（但不一定是概念）的程序，其中 d 是待学习 DNF 表达式的度。

读者应注意，这里还有一个额外的哲学困难：表达式的可用性本身并不意味着有用于 ORACLE 的多项式时间算法。另一方面，该定理确实说，如果一个主体拥有某种也许临时的 ORACLE 黑箱，其工作方式对他或她未知，那么它可以用来教另一个人一个逼近该函数的 DNF 表达式。

最后，也许值得强调，单调情况没有问题，其推导过程非常简单。如果有上下文能证明更复杂的推导过程有优势，那么为其研究更复杂的推导过程可能有趣。单调 DNF 表达式是否能仅从 EXAMPLES 学习是一个开放问题。肯定答案将特别重要。朝这个方向的部分结果可以通过对偶化定理 A 得到：对任何 k，每个析取项长度有界 k 的 DNF 表达式类可以仅从负例（即来自满足 \bar D(v)\ne 0 的向量 v 来源）在多项式时间内学习。

7. \mu-表达式

我们已经看到一类表达式，即 k-CNF 表达式，可以仅从正例学习。这里我们将考虑另一个极端，一类可以仅使用预言机学习的表达式。

推导结构限制比 DNF 或 CNF 更少的表达式似乎困难得多。本节目的是给出一个范例，说明如果愿意付出比先前描述的预言机更复杂的预言机的代价，我们能走多远。

变量集 {p_1,\ldots,p_t} 上的一般表达式递归定义如下：

对每个 i（1\le i\le t），”p_i” 和 “\bar p_i” 是表达式；
如果 f_1,\ldots,f_r 是表达式，则 f_1+f_2+\dots+f_r 是表达式（称为加表达式）；
如果 f_1,\ldots,f_r 是表达式，则 f_1\times f_2\times\dots\times f_r 是表达式（称为乘表达式）。

\mu-表达式是每个变量至多出现一次的表达式。我们可以假设 \mu-表达式是单调的，因为总可以用表示其否定的新名字重新标记被否定的变量。在任何 \mu-表达式的递归定义中，显然至多有 2t-1 个中间表达式，其中至多 t 个是类型 (1)，至多 t-1 个是类型 (2) 或 (3)。不失一般性，我们假设在 \mu-表达式的定义中规则 (2) 和 (3) 交替。如果两个 \mu-表达式的定义可以通过重排和与积以及必要时重新标记而在形式上相同，则我们认为它们相同。

为了学习 \mu-表达式，我们将使用更强大的预言机。合理与不合理预言机之间的边界似乎并不清晰。除这些新预言机可能作为理解可学习性的工具之外，我们不声称它们合理。

这些定义涉及布尔函数 F（这里不视为概念）。第 2 节的预言机将更名为 N-ORACLE，因为它是必然性预言机：N-ORACLE(v)=1 当且仅当对所有满足 w\Rightarrow v 的完全向量 w，都有 F(w)=1。其对偶是可能性预言机：P-ORACLE(v)=1 当且仅当存在满足 w\Rightarrow v 且 F(w)=1 的完全向量 w。为简洁，我们还定义素蕴含项预言机：PI(v)=1 当且仅当 N-ORACLE(v)=1，但对任何通过将 v 中一个确定变量变为未确定而得到的 w，N-ORACLE(w)=0。

最后我们定义另外两个预言机：相关可能性 RP 和相关伴随 RA。为方便，我们通过其在表示为单项式的向量上的行为来定义第一个：RP(m)=1 当且仅当存在某个单项式 m’，使得 mm’ 是 f 的素蕴含项。对变量集合 V,W，我们定义 RA(V,W)=1 当且仅当 f 的每个包含 V 中变量的素蕴含项也包含 W 中变量。

定理 C： \mu-表达式类可通过推导过程 C 学习，该过程总共使用 O(t^3) 次 N-ORACLE、RP 和 RA 调用，其中 t 是变量数（且不调用 EXAMPLES）。该过程总是精确推导出正确表达式。

证明： 令 \lambda 为无文字乘积（空单项式）。算法首先对每个 p_j 计算 RP(p_j)，以确定哪些变量出现在待学习表达式 f 所表示函数的素蕴含项中。令 g_1,\ldots,g_r 为不同的单变量表达式，每个对应于满足 RP(p_j)=1 的 p_j。注意这些恰好是出现在 f 中的变量，因为 f 是单调的。

对每个 g_i，我们关联两个单项式 m_i 和 \dot m_i。前者将是 g_i 所表示的单个变量 p_j。后者定义为任何与 m_i 无公共变量的单项式 \dot m，使得 m_i\dot m 是 f 的素蕴含项。算法将构造每个这样的 \dot m_i，作为以下过程中 m 的最终值：置 m=\lambda；当 PI(mm_i)=0 时，找一个不在 mm_i 中的 p_i，使得 RP(p_imm_i)=1，并置 m:=p_im。因此至多 t^2 次 PI 调用（即 t^3 次 N-ORACLE 调用）和 t^2 次 RP 调用后，将找到每个 \dot m_i 的值。

初始化后，算法交替执行加阶段和乘阶段。每个阶段开始时，我们有一组表达式 g_1,\ldots,g_r，每个 g_i 关联两个无公共变量的单项式 m_i 和 \dot m_i，其中 m_i 是 g_i 的素蕴含项，m_i\dot m_i 是 f 的素蕴含项。我们根据最外层构造规则是加法还是乘法，将 g_i 区分为加表达式或乘表达式。加阶段首先在 {g_i} 中那些乘表达式子集上计算等价关系 S。对每个等价类 G，如果 G 中没有 g_i 已经作为和项出现，则构造一个新表达式，即 G 中成员之和，并称其为 g_k，其中 k 是先前未使用的索引。如果 G 中某些成员已经出现在某个和，例如 g_l 中（注意它们从不会分布在多个和中），则修改和表达式 g_l，使其等于 G 中每个表达式之和。乘阶段完全类似，只是它现在在加表达式上计算不同的等价关系 T，并将形成新的或扩展旧的乘表达式。在上述语境中，单变量表达式将同时视为乘表达式和加表达式。此外，用哪种阶段开始算法无关紧要。

算法意图最好由以下将要验证的断言表达。假设出现在 f 定义中的表达式是 f_1,\ldots,f_q（其中 q\le 2t-1）。我们将说 g\le f_i 当且仅当 g 的素蕴含项集合是 \hat f_i 的素蕴含项集合的子集，其中 (1) 如果 f_i 是加表达式，则 \hat f_i=f_i；(2) 如果 f_i 是乘表达式，则 \hat f_i 是 f_i 的某个乘数子集的乘积。

断言 1： 算法每个阶段之后，对每个已构造的 g_i，恰有一个表达式 f_i 使得 (1) g_i\le f_i，且 (2) f_i 与 g_i 同种（即加或乘）。

该过程从叶子开始，将表达式的有根树构建为有根子树。一个明显困难是，没有关于树形状的先验知识。因此，在嫁接过程中，一个子树可能连接到另一个子树的几乎任何节点上。

每当创建或扩大一个加或乘表达式 g_i 时，其关联的 m_i 和 \hat m_i 如下更新。如果 g_i 是和，则对任何作为 g_i 中加项的 g_i，令 m_i=m_i 且 \hat m_i=\hat m_i。如果 g_i 是乘积，则 m_i 将是 g_i 中乘数对应的所有 m_i 的乘积。最后 \hat m_i 将作为以下过程中 m 的最终值生成：置 m:=\lambda；当 PI(mm_i)=0 时，找一个不在 m_i 中的 p_i，使得 RP(p_imm_i)=1，并置 m:=p_im。由于这样的 \hat m_i 在整个算法中至多需要找 t 次，总成本至多 t^2 次 PI 调用（即 t^3 次 N-ORACLE 调用）和 t^2 次 RP 调用。

为完成算法描述，只剩下定义等价关系 S 和 T。

定义： g_i S g_j 当且仅当

PI(m_i\hat m_i)=PI(m_j\hat m_j)=1，且
m_i 与 \hat m_i 包含不相交变量集，m_j 与 \hat m_j 也如此。

为定义 T，我们用 V_i 表示出现在表达式 g_i 中的变量集合。

定义： g_i T g_j 当且仅当 RA(V_i,V_j)=RA(V_j,V_i)=1。

首先我们验证，在假设每个阶段开始时断言 1 成立的情况下，S 和 T 确实是等价关系。显然 S 和 T 定义为自反且对称的。为验证 T 的传递性，假设 g_i T g_j 且 g_j T g_k。前者意味着 f 的每个包含 g_i 中某变量的素蕴含项也包含 g_j 中某变量。因此 g_i T g_k 成立。为验证 S 的传递性，我们将对 f 的任意子表达式做一个更一般的观察。

断言 2： 如果 m_i,m_j 是 f 的不同乘子表达式 f_i,f_j 的素蕴含项，且对某个与 m_i 或 m_j 都无公共变量的 m，m_i m 和 m_j m 都是 f 的素蕴含项，那么 f_i,f_j 必须作为同一加表达式中的加项出现。

证明： 最容易通过将表达式 f 表示为有向图（例如 [8]）来验证，边用布尔变量标记。在 \mu 表达式情况下所有边都有不同标签，从一 distinguished 源节点到一 distinguished 汇节点的有向路径上的标签集合恰好对应素蕴含项。

现在验证 S 的传递性，假设 g_i S g_j 且 g_j S g_k，其中根据断言 1，g_i\le f_i,g_j\le f_j,g_k\le f_k 对应适当的乘表达式 f_i,f_j,f_k。那么可推出 m_i\hat m_i,m_j\hat m_j,m_k\hat m_k 都是 f 的素蕴含项，其中 m_i,m_j,m_k 与 \hat m_i 无公共变量。由断言 2 可推出 f_i,f_j,f_k 是同一和表达式中的加项。因此 g_i S g_k 成立。

断言 3： 假设算法某阶段后断言 1 成立，且已形成乘表达式 g_i,g_j，其中 g_i\le f_i,g_j\le f_j，且 f_i,f_j 是乘表达式。那么 g_i 和 g_j 将在下一个加阶段被放入同一和表达式，当且仅当 f_i=f_i,f_j=f_j，且 f_i,f_j 是 f 中同一和表达式的加项。

证明： (\Rightarrow) 如果 g_i\le f_i=f_i,g_j\le f_j=f_j，且 f_i,f_j 在同一和中，则 m_i,m_j 将是 f_i,f_j 的素蕴含项。又 m_i\hat m_i 和 m_j\hat m_j 将是 f 的素蕴含项，且 m_i 中变量与 \hat m_i 中变量不相交，m_j 与 \hat m_j 也如此。因此 g_i S g_j 成立，下一个加阶段后 g_i g_j 将在同一加表达式中。

(\Leftarrow) 假设 g_i\le f_i,g_j\le f_j，且 g_i S g_j 成立。则 m_i,m_j 将分别是 g_i,g_j 的素蕴含项，m_i\hat m_i,m_j\hat m_j 都将是 f 的素蕴含项，且 \hat m_i 中变量与 m_i 和 m_j 中变量都不相交。由断言 2 可推出 f_i=f_i,f_j=f_j 必须作为 f 中同一加表达式的加项出现。[注意：这里我们使用的事实是，如果允许“乘子表达式”是 f 中乘表达式的任意乘数子集的乘积，断言 2 仍然成立。]

断言 4： 假设算法某阶段后断言 1 成立，且已找到某些加表达式 g_i\le f_i 和 g_j\le f_j（f_i,f_j 为加表达式）。(1) 如果 g_i=f_i,g_j=f_j，且 f_i,f_j 是 f 中同一乘表达式的乘数，则 g_i,g_j 将在下一个乘阶段被放入同一乘表达式。(2) 如果 g_i,g_j 在任何后续阶段被放入同一乘表达式，则 f_i,f_j 在 f 中同一乘积中。

证明： (1) 如果上述 (1) 条件成立，则在下一个乘阶段将发现 g_i T g_j，断言随之成立。(2) 如果 f_i,f_j 不在 f 中同一乘积中，则 f 包含某个素蕴含项，它含有来自 g_i,g_j 之一的变量而不含另一个的变量。因此 g_i T g_j 永远不会成立。

断言 1 的证明： 对阶段数进行归纳，同时使用断言 1、3 和 4。

我们定义公式 f_i 的深度为其定义中所需的和与积交替的最大次数。

断言 5： 如果 f_i 是 f 中深度为 k 的表达式，则在 k 个阶段后，算法将构造出与 f_i 相同的 g_i。

证明： 对断言 3 和 4 进行归纳。

为结束定理证明，只需分析运行时间。主要成本由计算 m_i 和 \hat m_i 的成本支配，我们已计算过，加上计算等价关系 S 和 T 的成本。首先注意在算法过程中使用的表达式名 g_i 少于 2t 个。当一个表达式被嫁接到另一个表达式的深处时，后者上方所有子表达式的语义将改变。根据断言 3 和 4，这种嫁接可以在一个 g_i 被加入和表达式时发生，但在加入乘表达式时不会发生。因此，当这种嫁接发生时，不需要为任何表达式改变 m_i 和 \hat m_i 的值。由此可知，为计算 S，只需考虑 2t 个 m_i,\hat m_i 值。因此总体 O(t^2) 次 PI 调用或 O(t^3) 次 N-ORACLE 调用足够。为计算 T，嫁接可能引起涟漪效应。每次 V_j 的值可能需要对至多 t 个这样的集合更新，因此 t^2 次 RA 调用足够。因此整个算法中 O(t^3) 次 RA 调用足够。

8. 评论

在本文中，我们将学习视为从信息中推导出执行任务的程序的过程，而这些信息并不提供此类程序的显式描述。我们赋予这种学习概念精确含义，并表明在一些受限但非平凡的语境中，它在计算上是可行的。

考虑一个包含机器人和大象的世界。假设其中一个机器人发现了一种识别大象的算法，该算法可以有意义地用 k-合取范式表达。我们的定理 A 意味着，这个机器人可以通过每当大象出现时简单地喊“大象”，将其算法传达给其余机器人群体。

我们方法的一个重要方面，如果以其最大一般性来表述，是我们要求教师和学习者的识别算法只在自然输入的一个压倒性比例上一致。它们在非自然输入上的行为无关紧要，因此不需要描述所有可能世界。如果推到底，这一想法有相当大的哲学含义：一个可学习概念不过是一个短程序，它区分某些自然输入与另一些自然输入。如果这样的概念以分布式方式在群体中传递，意义可能产生实质性变化。更重要的是，无论存在何种共识，它只对自然输入有意义。个体程序对非自然输入的行为无关紧要。因此，涉及非自然假设情境的思想实验和逻辑论证可能是无意义的活动。

该表述的第二个重要方面是，预言机概念使得讨论超出简单识别例子的整个师生互动范围成为可能。这在人工智能语境中很重要，因为人类可能愿意付出巨大努力把技能传授给机器，却因无法说清自己实践技能时使用的算法而受挫。我们预期，对于传递超出某些难度限制的技能，某些显式编程确实变得必要。识别这些限制是本文所提出工作路线的主要目标。

本文写作过程中使用了 AI 辅助整理，内容经作者核对与修改。