成员与等价查询学习

精确学习协议 ​

设概念类 $C\subseteq \{0,1{\}}^X$，未知目标为 $c^{\ast }\in C$。学习器不接收被动 IID 样本，而是与 oracle 交互，目标在有限次查询后输出与 $c^{\ast }$ 在整个 $X$ 上完全相同的假设。两种经典查询提供不同信息。

成员查询（membership query）。 学习器选择任意 $x\in X$，oracle 返回 $c^{\ast }(x)$。它回答一个由学习器主动设计的局部标签问题。

等价查询（equivalence query）。 学习器提交候选 $h:X\to \{0,1\}$。若 $h=c^{\ast }$，oracle 回答 YES；否则返回某个反例 $x$，满足 $h(x)\ne c^{\ast }(x)$。反例由 oracle 在所有分歧点中选择，通常不能假设随机、最短或对学习器最有利。

查询复杂度计算成员和等价查询次数，计算复杂度还计生成查询、处理反例和表示假设的时间。若单次查询本身需要指数长度，就不能只凭查询次数多项式而称高效。

一个有限状态图像 ​

学习 DFA 时，成员查询可问某个字符串是否被目标语言接受；等价查询提交当前自动机，oracle 若否便给一条区分目标与候选的字符串。反例不仅提供一个标签，还揭示当前状态划分在哪段前缀后合并了本应区分的行为。Angluin 的 $L^{\ast }$ 算法利用 observation table 系统地吸收这种结构，最终精确恢复最小 DFA 的等价类。

若只有随机正负样本，一条关键但分布概率极低的区分字符串可能长期看不到；成员查询可主动定位它，等价查询则让 oracle 直接暴露某处全局不一致。协议更强，正是查询学习能得到不同复杂度结果的原因。

version space 的变化 ​

成员回答把候选集限制为

$$V\leftarrow \{c\in V:c(x)=c^{\ast }(x)\}.$$

理想查询会大致平分 version space，但找这种点本身可能困难。等价查询的反例同样删除所有在该点与目标标签不符的候选，却还允许学习器用候选的结构组织下一步。

oracle 可以对同一错误候选返回不同反例，算法证明必须对任意合法反例序列成立。把等价 oracle 想象成“总给最有帮助的反例”，会低估最坏查询复杂度。

与 PAC 的连接 ​

现代 PAC 学习通常只允许来自未知分布的 IID 标记样本，并要求小分布风险，而非在所有 $x$ 上完全等价。成员和等价查询不是 PAC 定义的默认能力。若一个查询算法可模拟等价查询，例如从分布抽样测试候选并在发现错误时返回样本反例，可在额外条件下转成 PAC 学习器；模拟失败概率和样本量需明确计入。

反方向也不自动成立。PAC 学习器可以忽略分布质量极小的区域，而精确等价查询要求这些区域也完全正确。一个类在分布意义上容易学习，仍可能需要很多查询才能精确识别。

Valiant 1984 年的历史模型包含正例生成与特定 oracle/表达条件，和现代教科书的分布无关 PAC 定义并不完全相同。回顾历史时应列出当时可用查询，不能把后来的简化定义倒写进原模型。

与统计查询的区别 ​

统计查询模型公理库统计查询模型statistical query model · SQ model让学习器查询有界统计量的近似期望，并以查询数、容差和计算量衡量效率。询问有界函数在带标记分布下的期望，并得到容差内近似值；成员查询询问一个人为选择点的精确标签。前者不保证能把质量集中到任意单点，后者也不直接提供分布平均。两种模型都叫 query learning，但 oracle 语义不同。

它们与布尔函数查询复杂度公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。也不能只按调用次数对齐：位查询读取一个固定输入的坐标，成员查询读取未知目标概念在学习器所选点上的标签，等价查询还可返回全局反例。性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。的目标则是判断当前对象属于性质还是 $\epsilon$-far，并允许在两阈值之间不作承诺；本页协议要求最终在整个 $X$ 上精确识别 $c^{\ast }$。把精确学习器改成 tester，必须说明如何从候选识别得到 gap decision 及其距离与错误参数，不能把一次等价查询直接算成一次普通坐标查询。

经典 classification noise 下，统计查询算法常可稳健模拟，因为期望能通过样本估计；成员标签若被独立噪声翻转，则需重复询问或专门容错，而同一点多次询问的噪声是否独立又是额外协议假设。

边界 ​

现实系统中的“询问专家”通常有成本、延迟和不可回答区域，未必提供精确成员 oracle。等价 oracle 更强，往往只能由形式验证器、测试生成器或教师近似实现。若 oracle 不完备，返回 YES 可能只表示没找到反例，而非全域等价。

主动学习也会选择要标注的样本，但通常只能从未标记流或池中选点，目标仍是低分布风险。任意成员查询、池式主动学习和等价查询应作为三种不同可访问性模型分别描述。

参考资料

• Dana Angluin, “Queries and Concept Learning,” Machine Learning, 1988.
• Dana Angluin, “Learning Regular Sets from Queries and Counterexamples,” Information and Computation, 1987.
• Leslie Valiant, “A Theory of the Learnable,” Communications of the ACM, 1984.