学习算法可以通过改变后续轮次中各样本的重要程度来改进弱规则;也可以查询有标签分布的平均性质,而不直接要求单个有标签样本。这是两个不同的模型:提升法结合在不断变化的权重下产生的假设,统计查询学习则控制提供给学习算法的信息精度。两者的保证都必须先说明分布和误差标准。
加权多数投票
定义 6.1.1
(指数重新加权的加权多数投票)
固定非空有标签样本 ,其中整数 ,;假设每个基础规则 的输出也属于 。初始权重为 。第 轮选择一个规则,其加权训练误差为
当 时定义
其中 使权重之和为一。归一化之前,错分样本的权重乘以 ,正确样本的权重乘以 。最终得分为 ,分类器根据其符号预测。得分为零时需要约定;下面的界将平局计作错误,因此对任何固定平局处理方式都成立。
上述有限更新要求 。若 ,当前规则已正确分类整个训练样本,可以停止。若 ,其系数为零;若误差大于 ,系数为负。这些轮次不满足下文的正弱优势条件。若假设类允许取反,翻转规则会反转其误差。 时,所写的有限更新没有定义。
例题 6.1.2
(重新加权四个样本)
四个样本初始等权,设 仅错分一个,则 、,归一化常数为 。更新后,错分样本的权重是 ,每个正确样本的权重是 。第二个规则须按这些新权重评估,而不是按原先的均匀权重评估。
递减的训练误差界
定理 6.1.3
(加权投票的训练误差界)
若每轮都满足 并使用上述更新,则满足 的样本比例至多为
若每轮 ,其中固定的 ,则上界至多为 。
证明
(指数损失控制错误指示函数)
对任意实数 ,有 。从 出发迭代更新,得到
对 求和并使用 ,可知平均指数损失等于 ,它控制非正间隔的样本比例。每轮有
写 ,其中 ,则 。逐轮相乘即得结论。
证明透视
界的每一步从何而来
这个证明含一个不等式和两个恒等式。不等式 是唯一损失信息的地方:它把错误个数换成光滑的损失。第一个恒等式 成立,是因为每次更新都把权重乘以 再除以 ,指数相加恰为 ;归一化于是迫使 的平均值恰好等于 。第二个恒等式在所选的 下计算 ;这个 正是 的极小点,因此没有其他投票权重能使这个因子更小。弱优势假设只在最后才出现: 当且仅当 ,否则 ,所以一致的优势 才使乘积按几何速度下降。论证中没有任何地方涉及样本如何产生,这正是结论只针对该样本的原因。
例题 6.1.4
(没有优势的一轮)
延续四个样本的例子。第一轮后权重为 ,权重大的点就是 错分的那个。设 恰好在该点出错,其余三点正确。它在均匀权重下的训练误差是 ,但真正起作用的是它在 下的误差 。于是 ,每个权重都乘以 ,,。这一轮不改变乘积界,只是在得分中加上 。它就是定理允许的边界情形 :没有坏处,但必须有正优势 ,才会出现小于 的因子 。
常见错误
(训练误差界不是泛化界)
人们容易把很小的 读成“分类器在未来样本上也准确”。该定理是关于固定训练样本及实际选出的假设的确定性结论,本身并不给出未来样本上的误差界;那需要额外的泛化论证,包括样本及自适应选择如何产生。定理也不保证每个遇到的分布下都存在具有所述优势的弱学习器;这是提升分析的假设。下面的例子具体展示了这个差距。
反例模式
训练误差为零不代表总体误差为零
令 上两点等概率, 的标签为 , 的标签为 。处处预测 的规则具有总体错误率 。若独立抽取的 个输入恰好全为 ,这一事件概率为 ,则训练误差为零。泛化界控制此类误导性样本出现的概率,并不能使它们不可能发生。
统计查询:以平均值作为接口
定义 6.1.5
(统计查询预言机)
令 为实例空间 上有标签对 的分布。对任意查询函数 及容差 ,统计查询预言机返回某个 ,满足
统计查询算法必须对容差内每一个允许的回答都有效,而不只是对精确期望有效。查询函数、容差、查询次数和运行时间都是模型的一部分。示性函数查询 询问 的错误率;若 输出正负号,相关性查询 询问的是 。
命题 6.1.6
(以全新批次模拟统计查询)
假设算法最多进行整数 次自适应查询,每次均使用容差 。固定 。从 取得独立同分布的有标签样本,每个查询使用一批全新的
个样本来回答,则所有回答均满足容差的概率至少为 。
证明
(对交互记录取条件,再用并集界)
在给定此前的全部查询记录以及选取下一查询时使用的随机选择之后,当前查询固定,而新一批样本仍是来自 的独立样本。对取值于 的变量应用 Hoeffding 不等式,样本均值偏离期望超过 的概率至多为 。此界对每一种此前记录都成立,故无条件概率也满足同样的界。对至多 轮使用并集界得到结论。新样本批次对于这个简单的自适应论证至关重要:根据重复使用的数据集选择查询后,固定查询的集中界不一定在条件下继续成立。
这只建立了一个方向的模拟:随机样本可按上面的样本成本近似有限次统计查询回答。它并不意味着统计查询预言机透露单个样本,也不意味着所有使用样本的算法都能由统计查询高效实现。
例题 6.1.7
(自适应查询的样本预算)
某算法进行 次自适应查询,容差为 ,要求所有回答都正确的概率至少为 ,即 。命题要求 ,所以每个查询使用 个全新样本,共计 个。在边界情形 ,并集界是平凡的,需求为 ,即 个样本。成本对 只是对数增长,对 却是二次增长:把 减半到 ,因子 就乘以四。
例题 6.1.8
(解读带容差的回答)
假设 输出正负号,对 的查询返回 ,容差为 。真实相关性属于 ,所以错误率属于 。数值 只是区间中点的估计;转换时必须保留容差。
常见错误
(回答给出的是保证范围,而不是真值)
对上面的回答 ,若把错误率报告为恰好 ,或把 当作真实错误率交给后续步骤,都是错的。区间 内的每个相关性都与该回答相容,所以只有 得到了保证。由于 ,相关性的容差 对应错误率的容差 。统计查询算法必须对容差内的每个回答都保持正确,而不是只对中点正确。
练习与解答
快速检查
(四个样本等权,规则错分一个。求更新后该点的权重和其他三个点的权重之和。)
先算 ,再算 和 。
解答 · 答案
错分点获得权重 ,正确点合计权重也是 。事实上 给出 ;归一化之前,错分点为 ,三个正确点合计为 ,两边各占总和的一半。
快速检查
(若某轮提升的误差为 ,计算 ,并求连续十轮都具有此误差时的乘积界。)
使用 。
解答 · 答案
,故训练误差的乘积界为 。取 的较弱指数界为 。这些界不一定紧。
快速检查
(某错误率示性函数查询的回答为 、容差为 。能证明真实错误率位于什么范围?)
回答在两个方向上最多可偏离容差。
解答 · 答案
真实错误率在 中。这里端点已是有效概率;一般情况下要将容差区间与 取交集。
重复使用同一样本:固定查询论证在哪里失效
上一节的证明为每个自适应统计查询抽取一批全新的独立同分布样本。回答第 个查询所用的样本,与决定 的全部信息相互独立。因此我们可以对交互记录取条件,把 视为固定查询,再对有界的固定查询使用普通的集中性结论。下面的例子说明:重复使用同一个数据集时,这一步条件化并没有自动成立的对应版本。
反例模式
自适应地重复使用样本
设定。 令 ,。设 在 上均匀分布,且总有 。独立同分布地抽取一个样本 ,并用经验平均 回答每个查询 。
第一阶段(非自适应)。 提出 个单点查询 ,每个的期望都是 。 的回答为正,当且仅当 出现在 中。因此这些回答恰好揭示了集合 。
第二阶段(自适应)。 仅根据这些回答,选取 。对任意样本都有 。令 为一次独立的新抽样。给定交互记录后,,所以误差至少为 。查询总数为 。
第一阶段看似无害。 对 个点对使用并集界,可知各 两两不同的概率至少为 。在该事件上,每个单点回答为 或 。因此每个回答与 的差都小于 ,落在容差 之内。然而最后一个回答违反了 。
所有查询都取值于 。 的选择只依赖先前的回答。每个查询若事先固定,并在全新的独立数据上计算,都满足普通的集中性。失效的是独立性: 通过交互记录成为 的函数。在同一个 上,它不再是固定查询。
适用范围。 这个例子并不说明所有重复使用数据集的方法都会失败,也不说明不可能存在高概率的一致界。它只说明简单的条件化固定查询证明不能直接移植到这里。它不是针对所有可重用数据算法的下界。
快速检查
(对一般的 和 ,证明 ,并且最终差距至少为 。解释为什么这个下界只有在 时才为正。)
比较 在 上的经验平均与它在新抽样上的均值。
解答 · 答案
样本中不同的输入至多有 个,故 。给定交互记录后,在新的独立抽样上该查询的总体均值为 ,而它在 上的经验平均为 。两者之差是 。这个下界恰在 时严格为正;当 时它未必提供有用信息。