统计查询模型

模型 ​

统计查询学习器不访问单个样本，而向 oracle 提交有界函数 $\varphi :\mathcal{Z}\to [-1,1]$ 和容差 $\tau >0$。oracle 返回某个 $v$，保证

$$|v-{\mathbb{E}}_{Z\sim D}\varphi (Z)|\le \tau .$$

返回值不是精确期望，也不必随机或无偏；它可在允许区间内采取对学习器最不利的值。算法可根据此前回答自适应地选择后续查询。

复杂度的三个坐标 ​

高效 SQ 学习必须同时控制查询次数、最小容差和处理每个查询的计算时间。一个只发一次查询但要求 $\tau =2^{-d}$ 的算法并不高效：模拟该精度通常需要指数样本，答案也需大量位表示。因而 SQ 下界常证明，任何学习器要么发非常多查询，要么请求极小容差。

用样本模拟 oracle ​

对固定 $\varphi \in [-1,1]$，用 $m$ 个 IID 样本返回经验平均 $\hat{v}=m^{-1}\sum _j\varphi (Z_j)$。Hoeffding 界给出

$$\text{Pr}(|\hat{v}-\mathbb{E}\varphi |>\tau )\le 2e^{-m{\tau }^2/2}.$$

因此模拟一个固定查询到失败概率 $\delta$ 需要 $m=O({\tau }^{-2}\log \left(1/\delta \right))$。若有 $q$ 个自适应查询，直接复用同一数据会引入 adaptive data analysis 问题；简单做法是为每个查询使用独立样本并分配 $\delta /q$，但样本代价相应增加。

相关性例子 ​

二分类中可查询 ${\varphi }_j(x,y)=y{x}_j$（先把特征截放到 $[-1,1]$），从而估计第 $j$ 个特征与标签的相关性。弱相关特征只有在容差小于相关 gap 时才可可靠区分。这个例子展示 SQ 如何表达许多基于矩和梯度期望的算法，而不是数据库 SQL 查询。

边界与关系 ​

查询函数有界是有限样本模拟的关键；无界统计量需尾部假设或稳健估计。经典 SQ 模型与随机分类噪声有紧密联系，但不是所有样本算法都能高效表达为 SQ，奇偶函数学习就是重要分界。高效 PAC 学习公理库高效 PAC 学习Efficient PAC learning在 PAC 统计保证之外，要求样本处理、运行时间与输出评价均为多项式。直接获取样本；SQ 限制了访问分布的接口，因此其困难性是更具体的计算/信息限制。

SQ oracle 也不同于普通查询复杂度公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。中的坐标 oracle：后者返回隐藏输入某一位置的精确值，前者返回分布期望的容差近似，单次答案依赖整个分布。性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。则描述成员与 $\epsilon$-far 的判定目标，测试器具体可以使用坐标、样本或更强的分布访问接口。一个 SQ 算法可以实现某些测试器，但“查询数 $q$”只有连同容差 $\tau$、样本模拟方式与距离参数一起转换，才可与 property-testing 查询复杂度比较。

参考资料

• Michael Kearns, Efficient Noise-Tolerant Learning from Statistical Queries, JACM, 1998.
• Vitaly Feldman, A General Characterization of the Statistical Query Complexity, COLT, 2017.