一个关于数据访问方式的问题
统计查询学习器询问近似平均值,例如某个规则与标签的相关性;它不接收用于形成这些平均值的单个样本。这种限制是否重要?奇偶函数提供了一个鲜明的测试:单个有标签样本是二元域上的一个线性方程,而近似平均值却可能在许多相互正交的候选中隐藏有关目标的线索。
下文的结果是针对明确统计查询模型的信息访问下界,不是密码学困难性定理,也不是说普通样本下奇偶函数难以学习。事实上,最后会给出从有标签样本高效精确学习的算法。下界还依赖查询容差:允许极高精度的回答会改变一个查询能够透露的信息。
模型与记号
定义 7.1.1
(均匀分布下的奇偶目标)
固定整数 ,令 ,并从 均匀抽取 。对每个子集 定义
未知目标是这 个奇偶函数之一,标签准确地满足 。分类器可以是任意函数 ,不一定是奇偶函数。对目标 ,其总体错误率为 。
输入分布公开且固定,只有 未知。我们包含空集对应的常值一函数,以取得全部 个特征函数。此处输入和标签使用正负号;稍后求解线性方程时会明确换成二进制位。正交性计算依赖均匀分布,此处不声称对任意输入分布都有相同结论。
定义 7.1.2
(统计查询访问与容差)
一个查询是任意函数 。固定容差 ,针对目标 的预言机可返回任何满足下式的实数 :
学习器知道 、均匀输入边缘分布和 ,可利用此前全部答案选择下一查询。每个答案计一次查询;下文的 是每次运行及每个随机种子上的最坏情况上限,不是期望查询次数。保证必须对每个目标以及每个满足容差条件的回答序列成立,包括由对手选择的回答。此模型中学习器不接收单个有标签样本;我们不限制查询或最终分类器的计算量,下界只计算查询次数。
对优势 ,错误率至多为 表示比随机猜测好至少 。当 时,
因此达到该精度需要至少 的相关性。这个恒等式讨论的是均匀总体分布,而不是某个有限样本上的表现。
正交性限制一次查询
定理 7.1.3
(奇偶特征函数与单查询计数引理)
在均匀分布下,
对任意查询 定义
目标 下的期望为 。其期望与共同值 的距离超过 的目标,至多有 个。
证明
(正交性与 Bessel 不等式)
若 ,乘积 是非空对称差 的奇偶函数。取对称差中的一个坐标;它是均值为零的独立均匀正负号,因此整个乘积的期望为零。若 ,乘积恒为一。
个函数 对内积 构成标准正交族。对任意实值 ,有限维 Bessel 不等式给出
对上述查询,两个查询值均在 ,所以 ,相关性平方和至多为一。若超过 个相关性的绝对值严格大于 ,其平方和就会超过一,矛盾,故得计数结论。
至于期望恒等式,对 写出 ,再代入 即得。共同回答 由查询和已知均匀边缘分布决定,不依赖目标。
同样的正交性也限制一个最终分类器。因为 ,Bessel 不等式给出
因此满足 的目标奇偶函数至多有 个。这只讨论一个固定的 ;下文证明还必须处理学习器在收到回答后才选择 的情况。
概念视角分析
查询读取的是立方体上的傅里叶(Fourier)系数
在目标 之下,回答中唯一依赖目标的部分是 ,也就是 在 上函数的奇偶基下的系数。这 个函数构成一组基,所以 Bessel 不等式在这里成为等式:。有界查询的总谱权重至多为一,因此绝对值超过 的系数至多有 个。
对手回答下的查询下界
定理 7.1.4
(确定性有限查询下界)
若确定性学习器至多进行 个容差为 的查询,并必须对每个目标及每个容差有效的预言机输出错误率至多 的分类器,则
若右边为负,此不等式没有实际约束。查询次数 是整数,因此正的非整数下界可以向上取整。
证明
(一个共同查询记录保留许多可能目标)
先让确定性学习器与一个参考预言机交互:每个查询 都回答与目标无关的 。这确定了至多 个查询、相应参考回答以及一个最终分类器 。参考预言机只是构造记录的工具,其回答不必对每个目标都有效。
对该记录上的每个查询,引理说明参考回答无效的目标至多有 个。删去所有这些例外集合的并集,至少还剩 个目标。对于其中任一目标,每个参考回答都在容差内。由于学习器是确定性的,预言机给出这些答案时,它会提出完全相同的后续查询并输出同一个 ;自适应性不会使这条路径分叉。
最终分类器计数说明, 对至多 个目标达到所需优势。若 ,至少有一个剩余目标既容许参考记录,又使 失败,矛盾。否定该严格不等式并整理,得到定理。
证明透视
自适应性在何处得到处理
证明并未假设学习器事先固定全部查询。它沿着“每次都收到共同基准值”这一条记录运行;自适应记录确定后,才统计哪些目标使这条路径上的每个回答都有效。这些目标对本次运行不可区分,即使其他回答序列可能使算法走向别处。
也有随机化版本。设对每个目标及每个有效预言机,算法对自身随机选择的成功概率至少为 ,其中 。那么必有
附加论证如下。对每个目标采用一个固定预言机策略:查询 时,如果 与真实回答的距离在容差内,则返回它;否则返回精确期望。该策略对每次查询都有效。固定学习器的随机种子,将其运行与该种子对应的基准记录比较。对均匀随机目标,沿此记录用并集界可知,发生至少一次偏离基准回答的概率至多为 。若从未偏离,输出固定,而它至多对 个目标成功。再对随机种子取平均,平均成功概率至多为
若所声称的保证对每个目标及这个有效策略都成立,其平均值至少为 ,整理便得下界。对手策略在随机种子抽取之前固定,不需要知道种子。这并不是说每个可能的预言机回答都没有信息:精确回答可能比容差保证所要求的回答提供更多信息。
例题
例题 7.1.5
(一次相关性查询)
对固定子集 查询 。若 ,其期望为一,否则为零。当容差小于 ,该查询可以检验这一个候选,却不能自动确定其余 个候选中哪个正确。上面的下界适用于比这种简单检验更一般的有界查询,也适用于自适应选择的查询。
例题 7.1.6
(一个有限的数值下界)
取 、、,共有 个目标。若确定性学习器对每个目标及每个有效预言机都保证错误率至多为 ,它至少需要
次查询。这是下界,并未给出恰用这么多查询的算法。固定正的 和 时,主项随 指数增长;若 随 缩小,则必须把该依赖代入公式,不能自动称其为指数下界。
例题 7.1.7
(单个有标签样本给出线性方程)
写 、,当 时令 ,否则令 。一个有标签样本给出
若有 个独立均匀输入,由各行 构成的 矩阵有非零核向量的概率至多为 :每个固定非零向量与一个均匀随机行正交的概率为 ,各行独立,而非零向量共有 个。因此对 ,取 ,不能唯一恢复目标的概率小于 。在满秩事件上,高斯(Gauss)消元法可以多项式时间精确恢复 。
这一比较改变了提供给学习器的信息,不能将统计查询下界当作普通样本模型中的计算困难性结论。
反例模式
假设类很大本身不能证明统计查询下界
个奇偶目标确实很多,但数量本身不是证明。在某些模型中,一个精确实数回答可以编码许多可能性,而一个查询也可以同时涉及所有坐标。下界使用了均匀分布下特定的正交性、每次查询的有界值域,以及预言机可返回容差内任意答案的自由。去掉任一条件,都必须重新分析。
常见错误
常见错误
(假设预言机总给出精确均值)
精确期望是允许的回答,但统计查询保证必须容忍 范围内每一个回答。一个只有在预言机恰好透露精确值时才成功的算法,不满足所述模型。反过来,这个对手容差下界也不是对必须返回精确期望的预言机的下界。
常见错误
(忽略容差如何随维度变化)
确定性下界包含 因子。固定优势和常数容差时,它关于 指数增长;若容差指数级缩小,下界可能很弱甚至没有约束。通过样本取得高精度查询本身可能有成本,必须另行分析,不能悄悄略去。
容差为何是一种资源,可以通过一个具体模拟看出。如果独立有标签样本只用于估计查询均值,那么对至多 个自适应有界查询,固定 ,每次使用一批新的、大小满足
的样本,由 Hoeffding 不等式与并集界,以至少 的概率所有回答同时落在容差内。每一批新样本都与此前记录独立。这是某个模拟方法的充分样本界,并非对所有方法的下界。若 极小,此模拟相应昂贵;仅靠查询次数定理不能量化这一成本。
总结
均匀分布下的奇偶特征函数相互正交。有界查询只能与有限个目标具有较大相关性,因此容差有效的基准回答可以使许多目标与同一条自适应记录一致;最终分类器又只能对有限个目标具有固定优势。所得查询界依赖具体模型,同时存在从单个有标签样本高效精确学习的方法。
练习
快速检查
(对 ,设 、。计算 及其在均匀 下的期望。)
利用 。
解答 · 答案
,因为 。独立性和均匀正负号的零均值给出期望零。
快速检查
(对 、、,用确定性定理给出 的整数下界。)
计算 并向上取整。
解答 · 答案
,。下界为 ;查询次数为整数,所以 。
快速检查
(令 。某统计查询预言机对 的回答为 、容差为 。哪些奇偶目标与这一个回答相容?)
对四个目标分别计算查询的真实期望。
解答 · 答案
查询期望为 ; 时为一,其余三个子集时为零。回答零对 超出容差,对 均有效。这排除了一个目标,但不能确定剩余三个中的哪一个正确。
快速检查
(对 、,要满足文中满秩概率保证,多少个独立同分布有标签样本足够?解释每个样本为何给出一个线性方程。)
用 。
解答 · 答案
文中充分样本数为 。写 后,标签位满足模二方程 ,所以每个有标签对给出一行方程。八行不能确定五位向量的概率至多为 。