合取式描述一个区域:规则中的每个文字都必须成立。析取范式(DNF)描述这些区域的并:只要至少一个项成立,输入就是正例。我们不知道每个正例是由哪一项产生的,还能高效学习吗?当每项使用的变量数至多为固定常数时,可以列出所有可能的短项,再删除与负样本矛盾的项。如果允许宽度增长,同样的构造可能大得多。
本节使用可实现、无噪声的 PAC 模型。证明分开处理两个问题:算法必须确实找到一个与样本一致的规则;然后样本界必须控制看过样本后才选出的规则。有限类保证解决第二个问题,本身并不提供高效算法。
项、宽度与学习模型
固定整数 和 ,输入空间为 。
定义 1.5.1
(项与宽度为 k 的 DNF)
文字是 或 。一个项是至多 个文字的合取,各文字使用不同变量;空合取的值为 1。宽度为 的 DNF 是这些项任意子集的析取;空析取的值为 0。
这个表中恰有
个不同的语法项:选择 个变量,并为每个变量选择正负号。一个 DNF 可以使用这 项中的任意多个。
常见错误
(宽度不是项数)
宽度限制的是每个项的文字数,而非项数。至多有 项、但每项可任意长的 DNF 是另一类;下面的算法没有证明那一类可高效学习。
未知的固定宽度 目标 给独立样本 标注,其中 独立同分布于 上任意分布 ,且 。假设 的总体风险为
目标和分布在抽样前固定,学习器不知道它们。我们的目标是 下的预测误差,不要求恢复目标公式的精确写法。
删除与负例矛盾的项
令 为全部 个项的固定列表。开始时保留所有项。对每个标签为 0 的样本点,删除在该点取值为 1 的所有保留项;删除过程中忽略正例。输出剩余项的析取 ;若没有剩余项,则输出 0。
定理 1.5.2
(一致性与单侧预测)
对于任何由宽度 目标标注的样本,该算法输出与样本一致的宽度 DNF。而且对每个 ,
因此可能发生的错误是假阳性,不是假阴性。
证明
(目标项从不被删除)
目标中出现的每一项在每个负例上都取 0:若某项取 1,它们的析取 在该点便为 1。所以目标项都不会被删除。因此只要 ,至少一个保留下来的目标项在 处取 1,故 。这包括每个正训练点。另一方面,负训练点会删除所有在它上面取 1 的项,因此没有保留项在该点触发, 预测 0。故 在两种标签上均与样本一致。论证同样适用于常零目标、由空项表示的常一目标,以及没有负例的样本。
证明透视
包含关系的方向是什么?
删除析取项会使析取式更难成立。但每个目标项都存活,输出仍包含所有目标项,也可能包含额外项。因此输出的正区域包含目标的正区域。这与在一个合取式中保留额外文字所得到的包含方向相反。可实现性恰好用了一次,即保证每个目标项在每个负例上都取 0;正例从不被检查,却自动被拟合。
例题 1.5.3
(一致但不等于目标)
取 、,目标为 。观察到 标签为 1, 标签为 0。初始项为 。负例删除 ,剩余 。它符合两个观察值,却在目标值为 0 的 上预测 1。若 对 赋予正概率,这个样本可能留下正的总体误差。样本一致不等于处处相等。
例题 1.5.4
(常值目标)
令 、。若 (空项),且样本只含正例,则没有任何项被删除, 是全部五个项的析取,其中含有项 ,因此处处等于 :与 一致。若 (空析取),且样本含负例 和 ,则 删除 , 删除 。没有项剩下,输出为空析取 ,同样等于 。若只有单个负例 ,输出会是 ,在 上出现假阳性。
从有限假设得到 PAC 界
定理 1.5.5
(分布无关的可实现保证)
设 。如果
则对每个分布 和每个宽度 目标,删除学习器以至少 的样本概率满足 。对数为自然对数。
证明
(语法假设的计数)
假设类在抽样前固定。每个假设对应 的一个子集,因此语法假设至多有 个;不同子集可能定义相同函数,这只使上界较松。固定风险 的任意假设 ,独立性给出
对固定假设类取并界,可知存在任何风险至少为 且与样本一致的假设,其概率至多为 。在补事件上,每个一致假设的风险都小于 。前一条定理保证删除算法依赖样本的输出也是一致假设,因此满足这一结论。
证明透视
为什么依赖样本的输出也被涵盖
这里有依次出现的三个成分。至多 个语法假设构成的类在抽样前固定,这使得对它取并界是合理的。对每个固定的、满足 的 , 次抽样的独立性给出因子 。并界随后产生一个概率至少为 的事件,在其上类中每个一致成员的风险都很小。学习器的输出是看过样本后选出的某个一致成员,因此落在该事件的结论之内;整个论证从不假设输出与样本独立。
不能把最终输出当成独立于样本预先固定的假设。定理给出充分样本量,并不宣称最优。
例题 1.5.6
(、 时的样本量)
此时 。取 、。定理要求 ,所以 个样本即可。该界关于 线性增长,这就是为什么只有固定 时它才关于 保持多项式。
“高效”依赖什么
对于每个负例,计算所有项至多需要 次文字操作。因此列出所有项并处理 个样本需要 次操作(包括完整读取输入位),显式列表占 空间,不计输入存储。固定 时,,所以算法和上述样本界都关于 和 为多项式。
如果 ,则 ,我们的显式展开需要指数资源。这是本算法的局限,并不证明所有可能的 DNF 学习器都有计算下界。
常见错误
(样本保证不等于算法)
有限类的界说明该类中任何一个一致的成员都能推广,却没有说明如何找到这样的成员。即使 固定,对 个语法假设做暴力搜索也不高效。真正提供一致输出的是删除规则,它的运行时间关于 和 为多项式。
上述保证依赖无噪声可实现性,下面的例子说明这一点。
反例模式
一个被翻转的标签删除了目标项
取 、,目标 , 均匀分布于 。设 处的标签被错误记录为 ,而 的标签 正确。 处的负例记录删除在该点取 1 的每个项:、 和 。剩下 和 ,故 。它与所记录的样本一致,因为 、。但 而 :这是假阴性,所以 ,单侧结论不再成立。证明所需要的恰恰是存活不变量,即没有目标项被删除。这个例子本身没有分析某一种随机噪声模型。
练习与解答
快速检查
(计算 、 时的 。这计算的是公式数还是候选项数?)
对 求 之和。
解答 · 答案
个候选项。这些项的语法析取至多有 个。
快速检查
(对 、 和负例 ,哪些候选项经过该负例后存活?)
分别计算 在 处的值。
解答 · 答案
在 上取 0 的 和 存活;在该点取 1 的 被删除。
快速检查
(为什么在可实现模型中,学习器忽略正例仍能与它们一致?)
正例的标签从何而来?
解答 · 答案
每个正例都有一个为真的目标项,而正确标记的负例不会删除任何目标项,所以该项存活并使 预测 1。
快速检查
(定理是否说明宽度 的 DNF 至多有 项?当 时,它是否给出多项式时间算法?)
究竟限制了什么?
解答 · 答案
否: 限制每项的文字数,公式可有很多项。对于 ,这个显式算法的列表有 项,运行时间不是多项式。
快速检查
(为什么不能直接对依赖数据的最终输出使用固定假设的一致概率公式?)
哪个对象在抽样前固定,哪个不是?
解答 · 答案
输出随样本变化。对固定类取并界得到一个对所有一致候选同时成立的高概率事件,其中包括输出。