合取式只有一个共同要求:每个保留文字都必须为真。决策列表则能依次处理例外:如果某个文字为真,就给出一个标签;否则尝试下一条规则。最先匹配的规则决定输出。我们将从可实现数据中高效找出一致列表,再证明其总体错误率以高概率较小。
规则、次序与学习任务
固定 ,令定义域 。可用文字是 和 ,其中 。
定义 1.4.1
(带符号文字决策列表)
带符号文字决策列表具有规则
之后跟一个默认标签 。对输入 ,返回第一个为真的文字 对应的 ;若没有文字为真,返回 。空列表是常量分类器。
稍后再次出现同一文字不会改变函数,因为满足它的输入已经在第一次出现时停止;因此可以只考虑文字互异且 的列表。
概念视角结构
决策列表是一棵偏斜的决策树
把每条规则 画成一个检验 的结点:为真则走向标签为 的叶子,为假则走向下一个结点。最后一条为假的分支终止于标签为 的叶子。含 条规则的列表恰好就是这样的树:共 个检验,每个检验旁挂着一片叶子,通向默认标签的路径长度为 。
假设一个固定目标列表 无噪声地标记数据: 独立同分布于 上任意分布 ,且几乎必然有 。样本含 个带标签例子。风险是独立输入 上的 。
逐次剥离同标签规则的学习器
保留一个活动样本指标集合,初始为所有指标,并从空输出列表开始。重复以下步骤:
- 若没有指标剩余,添加默认标签 0 并停止。若所有剩余标签都等于同一个 ,添加默认标签 并停止。
- 否则按固定顺序搜索文字,找到一个在至少一个活动例子上为真、且所有满足它的活动例子具有同一标签 的文字。
- 添加 ,删除所有满足 的活动例子,再重复。若找不到这样的文字,报告失败。
覆盖集合非空的条件防止规则没有进展。此前选过的文字在每个剩余例子上都为假,因此不能再次被选中。由于活动集合只会缩小,且所选文字的覆盖非空,非默认规则至多有 条。在单位成本比特访问模型下,每轮对每个文字扫描至多 个例子,同时检查覆盖非空和标签一致,因此时间为 。活动指标占用 空间,输出占用 个字,均不包括样本本身。
定理 1.4.2
(可实现决策列表可被一致学习)
若同一个目标列表正确标记每个样本,则该过程永不报告失败,必定终止,并输出与整个样本一致的列表。
证明
(一个不变量与一个合格文字)
每轮之后,活动例子恰好是不满足任何已输出文字的样本;每个已删除例子都被已输出前缀正确标记;目标 仍正确标记每个活动例子。这个不变量初始成立,删除覆盖的同标签集合后仍成立。只有当活动例子中两种标签都出现时,才进入步骤 2。至少有一个活动例子必须触发目标的一条规则;否则每个活动例子都会得到同一个目标默认标签。选择目标中最早在任意活动例子上触发的规则。之前的目标规则在所有活动例子上都不触发,因此每个满足该文字的活动例子都会到达这条规则,并具有它的标签。于是该文字覆盖一个非空的同标签集合,搜索必定成功。这个存在性论证与搜索顺序无关;固定顺序使过程确定。
选中的规则恰好标记该轮删除的例子;此前输出的规则在当时的所有活动例子上均为假,因此之后的规则不能改变这些预测。默认标签标记停止时剩下的所有例子。每个非默认步骤至少删除一个例子且不能重复使用文字,所以算法终止,输出一致。
证明透视
最早目标规则只是存在性见证
证明使用未知目标来说明某个合格文字存在。算法可能选择固定搜索次序中更早的另一个合格文字。它不必恢复目标的语法形式,只需正确分类观察到的样本。
例题 1.4.3
(同一个样本的两个一致列表)
在两个比特上,设活动样本为 、、、。它们由“若 则 1;否则若 则 0;否则 1”标记。若搜索先选 ,便以标签 1 删除前两个例子;对剩下两个例子,可选择标签为 0 的 ,然后使用默认标签 1。另一种选择是先用标签 1 选择 ,它删除 和 。剩余例子 和 可由“若 则 1;否则 0”处理,得到不同的一致列表。
常见错误
(用多数标签代替要求覆盖集合同标签)
在同一个样本中,文字 在 和 上都为真,所以它的覆盖集合含有两种标签。无论取哪个 ,添加 都会误分类这两个例子之一,而两者都被删除就把错误固定下来,因为被删除的例子不会再被检查。一致性不变量要求每个被覆盖的活动例子具有相同标签。
从一致性得到 PAC 保证
令 为抽样前固定的语法列表集合:文字互异,规则至多 条,默认标签任选。学习器不重复文字,所以输出属于 。列表最多有 个规则位置。为得到简单的固定类计数,每个规则位置至多有 种文字选择和两种输出选择。在计数时允许重复只会增加数量。算上两个默认标签并对长度求和,
定理 1.4.4
(分布无关的可实现界)
假设 且几乎必然有 。对 ,若
则输出满足 的概率至少为 。对数是自然对数。
证明
(对固定类取并集界)
对风险 的任一固定列表 ,它在独立同分布样本上不犯错的概率为 。由并集界,固定假设类中任意坏列表仍与样本一致的概率至多为 。在概率为一的可实现事件上,学习器输出一致,因此在上述坏事件外其风险至多为 。并集针对固定有限语法列表集合,而不是假设依赖样本的输出是固定的。
例题 1.4.5
(一个具体的样本量)
当 时,计数为 。取 、,定理要求 ,所以 个样本即可。粗略的界 比 大约大 倍,这只使定理中的对数增加约 。
例题 1.4.6
(只有单一标签的样本)
令 ,目标为“若 则 1;否则 0”。设样本为 和 。第一轮所有剩余标签都等于 ,所以学习器添加默认标签 并停止,输出空列表,即常值分类器 。它与样本一致,但在每个 的输入上都不同于目标,所以风险为 。PAC 界说明:除非该概率很小,这样的误导性样本在 足够大时不太可能出现。
所给计数刻意求简单而不是精确。它给出的充分样本量级为 ,并可与多项式时间一致性算法结合。它没有说明学到的列表在样本外等于目标,也没有说明此样本界最优。
假设失效时
反例模式
冲突标签可能使搜索停止
取同一输入的两个副本,给它们相反标签。活动标签不全相等,而任何覆盖其中一个副本的文字也覆盖另一个,因此不存在覆盖非空且标签相同的文字。算法报告失败。没有确定性决策列表能拟合该样本,所以可实现性假设确实失效。此例没有刻画每一种噪声模型下的行为。
常见错误
(决策列表不是规则的集合)
即使没有噪声,次序也很重要。“若 则 1;否则若 则 0;否则 1”在 上预测 1;颠倒两条规则则预测 0。列表不是一个无序的、各自独立生效的规则集合。
练习与解答
快速检查
(对两个比特的例子,目标列表在 和 上分别预测什么?)
按 的次序找第一个为真的文字。
解答 · 答案
在 上第一条规则触发并返回 1;在 上第一条规则为假,所以第二条规则触发并返回 0。
快速检查
(若所有活动标签均为 0,算法接下来必须输出什么?为什么它在活动例子上一致?)
看过程的第 1 步。
解答 · 答案
算法必须以默认标签 0 停止。活动例子均不满足先前输出的文字,所以由默认标签得到 0,而前缀已正确处理被删除的例子。
快速检查
(为什么此前选中的文字不可能在之后某轮再次被选中?)
满足该文字的例子后来怎样了?
解答 · 答案
满足该文字的所有活动例子都已删除,且活动集合只会缩小;故它之后的覆盖为空,不能再次满足非空覆盖规则。
快速检查
(若固定候选列表的总体风险为 ,它与 个独立样本一致的概率是多少?)
每个样本都必须被正确分类。
解答 · 答案
,因为每个独立样本被正确分类的概率为 。
快速检查
(当输出列表依赖样本时,为什么需要并集界?)
哪一个概率界只对预先固定的列表有效?
解答 · 答案
不能将固定列表的概率界直接用于观察样本后才选出的列表;并集界给出同时控制固定类中每个列表、包括所选列表的一个事件。