c.e.集合的容忍学习层级：基于索引等价关系的极限识别框架

《Annals of Pure and Applied Logic》：The Tolerant Learning Hierarchy for c.e. Sets

　　

从正数据学习刻画了这样一种场景：学习器接收一个未知集合的枚举的越来越长的初始段，并反复输出关于该集合的一个猜想。经典的极限识别要求学习器最终稳定到一个精确命名目标的假设，而异常学习则通过允许最终假设中出现有限多个错误来放宽这一要求。研究人员对计算可枚举（c.e.）集合发展了一个自然推广，其中正确性由索引上的一个任意等价关系决定，该关系尊重它们所枚举集合的相等性。研究人员将所得到的框架称为容忍学习（tolerant learning）。精确学习和有限异常学习是特例。通过根据可学习族来比较容忍关系，研究人员得到一个新的度结构，即容忍学习层级（tolerant learning hierarchy）。研究人员将锁定序列（locking sequences）和特征集（tell-tales）的经典方法推广到这一设定，并推导出那些具有普遍性（universal）的容忍关系的一个组合刻画（即在它们之下，每个非空计算可枚举集合族都是可学习的）。研究人员随后证明该层级是一个有界下半格但不是上半格，无原子且无共原子，并包含大小为连续统的链和反链。研究人员还分析了自然的基准关系，包括描述集合论中标准等价关系的c.e.-指标类比，并建立了它们学习能力之间的实质性不可比性。最后，研究人员通过展示一个普遍但不是可计算普遍的（computably universal）关系，将非有效与可计算容忍学习分离开来。这些结果表明，语义容忍在算法学习与等价关系理论的交界处产生了一个真正的度理论。

从Gold的极限识别模型出发，学习器接收未知集合的正数据枚举的越来越长的初始段，并反复输出关于该集合的猜想。经典精确学习（Ex-learning）要求学习器最终稳定到精确命名目标的假设；异常学习（anomalous learning）放宽了这一要求，允许最终假设中出现有限多个错误。然而，有限对称差只是近似语义之一种。一旦假设是c.e.集合的指标，任何扩展了集合相等关系=_ce的指标等价关系都可以作为正确性判定的容忍关系。基于这一观察，研究人员提出了容忍学习（tolerant learning）：最终假设只需相对于选定的等价关系正确。精确学习和有限异常学习分别对应于等词=_ce和有限对称差关系E₀^ce。通过按照可学习族比较容忍关系，研究人员建立了容忍学习层级（Tolerant Learning Hierarchy, TLH）。这项研究的意义在于将学习机制与正确性语义分离，从而在算法学习理论与等价关系理论之间建立起一个新的度结构。

研究人员首先推广了经典方法。他们定义了容忍锁定序列，证明若一个学习器容忍地学习某个族，则每个目标都存在一个锁定序列，即学习器在该有限片段后不再改变假设，且该假设在容忍关系下正确。接着，他们证明了Angluin式特征集定理：一个族K是E_ce-可学习的当且仅当每个目标W_e∈K都有一个有限子集D?W_e，使得任何与W_e不等价的族内集合若包含D则不是W_e的子集。该定理将可学习性转化为纯组合条件。为了便于结构论证，他们将特征集对偶化为吸收集：一个集合是吸收的，如果每个有限片段都能扩张到一个错误的真子目标。命题3.5表明，一个族不可学习当且仅当它含有吸收集。这个看似简单的转换成为后续证明的关键工具。进一步，他们证明了一个桥定理：若E_ce严格小于F_ce，则存在一个族不是E_ce-可学习的，但其所有成员都在同一个F_ce-等价类中。关于普遍性，定理3.10给出简洁刻画：E_ce是普遍的当且仅当它满足锁定性质，即任何递增有限近似序列若并集为非空c.e.集合W_e，则最终所有指标都E_ce-等价于e。

在TLH的结构性质方面，研究人员证明了TLH是有界的，底元素为[=_ce]_≡Learn，顶元素为[Id₁]_≡Learn。通过构造依赖于子集C?ω的等价关系E_(C)^ce，他们证明了C?D等价于E_(C)^ce≤LearnE_(D)^ce，从而将整个幂集结构(??(ω),?)嵌入TLH，因此TLH的宽度和高度均为2^?₀。对于交运算，定理4.5说明族K是(E_ce∩F_ce)-可学习的当且仅当它同时是E_ce-和F_ce-可学习的，因此TLH是下半格，交由关系的交集表示。然而，定理4.7构造了两个等价关系，使得它们的公共上界集合没有最小元，从而证明TLH不是上半格。最后，通过在第4.3节中嵌入P_fin(2^ω)（有限子集格），他们证明了TLH是既无原子又无共原子的。

在基准关系分析中，论文定义了c.e.-指标版本的关系E₀^ce、E₁^ce、E₃^ce、E_set^ce、E_min^ce和E_max^ce，它们分别是描述集合论中经典关系E0、E1、E3、Eset的类比。首先，命题5.1证明=_ce0^ce，即有限错误容忍严格强于精确学习。但定理5.3表明E₀^ce是弱的：任何扩展它的普遍关系只能是Id₁。通过构造三个特定族K_A、K_B、K_C，论文分别证明了它们在不同关系下的可学习性，从而得出定理5.8：E₁^ce、E₃^ce、E_set^ce和E_max^ce两两不可比。此外，命题5.10证明E_min^ce是普遍的。第5.1节进一步将这些关系在Borel归约、连续归约、可计算归约和学习归约下的行为进行了对比，表明学习归约产生了一种全新的顺序。

在可计算普遍性方面，论文区分了非有效学习器与可计算学习器。命题6.3证明对任意集合A?ω，关系E_A^ce都是普遍的。特别地，取A为停机集K，得到E_K^ce是普遍的。但定理6.4证明E_K^ce不是可计算普遍的：若存在可计算学习器M，则利用锁定序列可以构造一个枚举补集K￣的程序，从而推出K是可计算的矛盾。因此，非有效普遍性严格弱于可计算普遍性。

最后，论文在结论部分总结了主要发现：容忍学习层级保留了正数据学习的核心紧致性障碍，同时具有丰富的度结构；基准关系在学习归约下的行为不同于经典归约；可计算性要求使普遍性概念发生分化。开放问题包括TLH是否稠密，以及可计算E₀^ce-可学习族是否仍可计算E_max^ce-可学习。这些结果确立了语义容忍作为算法学习与等价关系理论交汇处一种真正度理论的地位。