动机
在普通监督学习中,学习器接收从某个分布抽取的有标签样本。主动学习允许它在一定程度上选择要请求哪些标签。当输入容易取得、正确标签却需要昂贵实验或专家判断时,这种选择可能很有价值。一个信息量高的问题可以同时排除许多假设;随机有标签样本则可能反复落在剩余假设都已一致的区域。
“学习器选择一个例子”背后有多种不同模型:它能选择实例空间中的任意点,还是只能从有限样本池中选择?输入分布是否已知?预言机的答案是否总是正确?无标签数据和计算是否有成本?不给出这些条件,标签数量的结论可能造成误解。我们先证明一个条件特别有利、但清楚可检验的结果,然后分析这些条件的作用。
定义
定义 8.1.1
(可实现成员查询模型)
设 ,未知目标是阈值函数
学习器可以自适应地选择任意 ,向预言机询问准确标签 ,每次请求计一个标签。后续查询可以依赖此前查询、标签和算法内部随机性。评估误差时的输入分布为 上的均匀分布,且学习器知道这一点。输出为某个阈值 。
总体误差为 。标签复杂度保证说明:对所有允许的目标,要达到指定误差和置信度,需要多少次标签请求。此模型只计算标签数量,不计算查询位置的数值精度、预言机计算或无标签抽样成本。
两个阈值的分歧区域是参数之间的区间,至多相差端点。因此
等号处的标记约定只影响单点,在均匀分布下概率为零。换一个分布后,参数距离不一定等于错误概率。学习器也不能直接读取目标的数值参数;它必须根据预言机回答推断一个足够小、包含目标的区间。
定义 8.1.2
(版本空间与样本池查询)
给定有限的有标签记录,版本空间是所选假设类中与每个已请求标签一致的假设集合。分歧区域是至少两个剩余假设给出不同标签的输入集合。样本池模型中,学习器取得或抽取一批无标签输入,只能请求池中点的标签;成员查询则可请求 中任意允许的点。两种访问方式的标签复杂度和无标签数据成本不一定相同。
定理/命题
定理 8.1.3
(二分法学习均匀分布下的阈值)
在上述无噪声成员查询模型中,有一个确定性算法在取得 个标签后,对每个 输出总体误差至多为 的阈值。因此对 ,至多 个标签即可保证误差不超过 ,置信度为一。
定理 8.1.4
(同一目标类下的被动学习比较)
设 、,并以 表示自然对数。被动算法接收 个独立均匀输入及其阈值标签,并对该类中每个阈值,以至少 的概率输出误差至多为 的分类器。那么必有
此下界允许算法使用随机性,也不要求输出必须是阈值。它计算独立同分布有标签样本的数量,只比较此特定的均匀、无噪声问题,并非所有主动与被动模型都存在相同差距。
定理 8.1.5
(匹配量级的被动上界)
对同一个均匀、无噪声阈值类,若被动学习器返回与 个独立同分布有标签样本一致的阈值,那么只要
其误差以至少 的概率不超过 。因此当 ,上述下界关于 和 的依赖在常数因子内是正确量级。
证明思路
证明
(二分法维持包含目标的区间)
最初学习器知道 。第 轮查询中点 。若答案为一,目标定义给出 ,保留 ;若答案为零,则 ,保留 。后一个闭区间包含一个不可能的端点,但仍安全地包含目标。无论答案如何,区间均为闭区间、包含 ,且长度减半。
归纳得到 。输出 ,两个参数都在保留区间中,故距离至多为 ,这也就是均匀分布下的误差。不需要概率计算:每个可能目标及与它一致的回答序列都满足此不变量。 时无需标签,界为一。中点与区间内每点的距离至多为区间长度的一半,故输出中点可得到更精确的界 ;但现有界已经说明对 是对数依赖。
概念视角组合
二分法读出二进制数字
二分法的每个答案恰好是目标的一个二进制数字:答案为一表示 在左半部分,数字为 ;答案为零表示在右半部分,数字为 。经过 次询问,学习器得到 的前 位数字(对 ,取不以零结尾的展开),所以误差 就是 位数字的代价。例如 ,答案一、零、一、零拼出 。
证明
(被动样本为何可能错过关键区间)
取 和 ,二者标签在均匀质量为 的区间上不同。令事件 表示 个输入均未落入该区间,则 。在给定 的条件下,两个目标产生的完整有标签数据集具有相同分布;加入独立的算法随机性后仍然相同。
两个目标分类器的分歧质量为 。对任意输出分类器 ,包含关系 给出
因此同一输出不可能对两个目标都具有至多 的误差。在给定 的共同条件分布下,两个目标各自的失败概率之和至少为一。乘以 ,至少一个无条件失败概率不小于 。如果对所有目标的失败概率均不超过 ,就需要 ;取对数得到第一个不等式。
当 时,。取 ,有 ,即得第二个不等式。下界计算的是有标签观测;它并不声称主动学习可以免费获得真实标签,也不声称每个分布都允许二分。
证明被动上界时,取任意与样本一致的阈值。若其误差大于 ,它位于真实参数左侧或右侧超过 的位置。前一种情况说明样本没有输入落在 ;后一种情况说明没有输入落在 。若相应区间超出 ,该方向本身不可能出现。每个相关区间的均匀质量均为 ,故存在坏的一致阈值的概率至多为 。所示样本数使其不超过 。这一论证适用于任何一致选择,包括观察数据后作出的选择。
证明透视
标签节省来自哪里?
中点查询在当前不确定区间已知之后才选出,所以任意一个答案都能排除区间的一半。被动样本则可能反复错过两个可能目标的分歧区域。两个证明比较的是不同的信息访问方式:任意无噪声成员查询与独立同分布有标签样本。引用结论时必须同时保留这些条件。
例题
例题 8.1.6
(未知阈值的二分过程)
假设真实阈值为 ,但学习器并不知道。第一次查询 得到一,保留 ;第二次查询 得到零,保留 。查询 得到一,保留 ;查询 得到零,保留 。
四个标签后区间长度是 。若返回左端点,误差为 。算法不需要知道实际误差;区间长度就是误差证书。若返回中点,误差为 ,至多为 。
例题 8.1.7
(具体的精度要求)
使用上述返回左端点的算法,为保证均匀误差至多 ,取 。最终区间长度为 ,与阈值位置无关。对于置信度 ,被动下界说明任何对所有目标都成功的被动算法至少需要
个有标签样本,即至少 个。这分别是不同过程的充分界与必要界,并非精确最优值。被动数量允许 失败概率,而二分保证对每个目标和每个一致回答记录成立。
例题 8.1.8
(样本池可能缺少有用查询)
假设无标签池只有 ,目标阈值不是 就是 。在两个目标下,池中标签完全相同:前两点为零,后两点为一。即使请求全部四个标签,也无法从固定样本池分辨目标。查询 的成员查询却能立即区分它们。两个目标在均匀分布下的分歧质量为 ,所以任何一个分类器不可能对二者的误差都小于 。更多无标签点可能有帮助,但必须另行计入其获取成本并说明抽样假设。
反例模式
查询不一定能将版本空间平分
令 ,,并设 ,。查询 相当于询问目标是否为唯一假设 ;若回答为零,仅排除这一个候选。对于确定性精确识别算法,对手可以一直回答零,直到排除 个候选,余下的目标才确定。因此可能需要 次查询;相比之下,对 个有序阈值适当进行成员查询,至多 次即可二分识别。此例证明的是精确识别的最坏查询成本,本身并未给出近似学习的下界。主动选择本身并不保证均衡划分。
常见错误
常见错误
(参数区间小不自动意味着概率误差小)
二分证明使用均匀输入分布,将区间长度转换为错误概率。若所有概率质量集中在短区间内某一点,该点两侧的阈值可能在全部概率质量上产生分歧。对于任意未知分布,参数区间短本身不足以保证总体误差小。
常见错误
(完美预言机是条件而非结论)
一次错误回答就可能使真实阈值被丢弃,此后区间不变量失效。在明确规定独立噪声模型的情况下,重复查询并取多数可能有用;但任意或相关的错误并不会自动因重复而消失。同样,中点查询需要成员查询权限,固定样本池不一定包含中点。
除非模型明确纳入其他资源,标签复杂度不会计算它们。确定窄区间可能需要高精度查询位置;样本池方法可能在找到有用点前检查许多无标签输入。泛化结论还需说明概率针对样本产生、预言机噪声、算法随机性,还是它们的组合。上面的置信度一依赖于无噪声回答及确定性的几何不变量。
总结
主动学习器利用此前答案选择标签。在任意无噪声成员查询及均匀输入分布下,阈值二分法有对数标签界;被动样本可能错过区分两个目标的区域,在此例中产生上述下界。当 时,该界至少为 。改变假设类、限制样本池、改变分布或加入标签噪声,都可能消除这一优势。
练习
快速检查
(从 出发,对 做三次二分查询。写出每次后的区间和最终左端点假设在均匀分布下的误差。)
记住标签为一表示 。
解答 · 答案
查询 、、,得到标签零、一、零。区间依次为 、、。左端点假设的误差为 。
快速检查
(若 ,上述左端点定理保证需要多少标签?如果返回最终区间中点,可以得到什么误差界?)
使用 。
解答 · 答案
五个标签足够,因为 。最终区间长度为 ,中点与目标相距至多 ,故均匀误差至多 。
快速检查
(对阈值 和 ,计算 个独立均匀输入在两个目标下全部得到相同标签的概率。解释该事件上观察到的有标签数据为何不能确定哪个目标产生了它。)
先找出两个阈值产生分歧的区间。
解答 · 答案
两个目标在 上分歧,其质量为 ;全部 个输入都避开该区间的概率为 。在该事件上,两个目标对每个观察输入赋予相同标签,因此数据与二者都相容;仅凭数据不能确定哪一个目标正确;对两个目标均赋予正概率的先验,也不能使这一共同记录产生确定性。
快速检查
(对反例中的单点类,令 。给出最多请求四个准确标签就能识别目标的确定性策略,并解释为何最坏情况下三个标签不够。)
想想某次查询回答为零时,对手会怎样回答。
解答 · 答案
查询四个互异点。若某次答案为一,该点便识别目标;若全为零,则第五个假设是唯一剩余者。对任何最多查询三次的确定性策略,对手都可以回答零,使至少两个目标与记录相容。同一个输出不能同时精确识别二者,故三个查询无法保证成功。