可机器学习集合

# 机器可学习集  
来源：https://arxiv.org/html/2606.28947  
††感谢：ve10@cornell\.edu  
††感谢：manish\.krishanlal@gmail\.com  
Manish Krishan Lal  
数学，独立研究者，印度  

###### 摘要  
在本研究中，我们正式定义了具有以下三个非正式性质的大规模离散集：其元素易于识别、易于生成，且后两个任务易于从示例中学习。该形式化专门针对二进制字符串集合，并基于存在有界复杂度布尔自编码器（该自编码器固定集合中的元素）来定义“机器可学习性”。我们通过布尔阈值函数网络实现自编码器进行实验。对于罗夏模式（可能在镜像半部分反转对比度）以及更“狂野”的集合（其中元素仅被可容许的自编码器近似固定），我们展示了机器可学习性。在第二种情况下，我们演示了一种简单的迭代，该迭代演化狂野集合并使其成为真正的机器可学习集。

## I. 引言  
机器学习的形式化模型用于确定何种学习在原则上是可能的，并为其实践评估提供框架。Gold[4 (https://arxiv.org/html/2606.28947#bib.bib1)]的“极限语言识别”是前者的最著名例子，并开启了算法学习理论领域。该任务是从示例中学习抽象语言的语法，计算仅受限于图灵机。Valiant[9 (https://arxiv.org/html/2606.28947#bib.bib2)]的“可能近似正确”（PAC）学习模型将焦点转向实践。PAC模型中的计算具有多项式复杂度界限，且精确学习被概率保证取代。在本文中，我们进一步将标准推向神经网络，对计算施加显式界限。该模型称为**机器可学习集**，将可学习性视为一种内在有趣的现象。语言习得——在人类中，而非机器——是我们最熟悉的可学习集示例。所涉及的集合是某语言中所有语法正确的有界长度句子的集合 \( X \)。\( X \) 的一个显著特征是无法列举其所有元素。尽管如此，\( X \) 具有以下良好性质：

1. 给定一个符号串 \( x \)，容易判断 \( x \in X \)。
2. 容易均匀采样 \( X \) 的所有元素。
3. 虽然稍难，但任务 1 和 2 可以从正例 \( x \in X^* \subset X \) 中学习，其中 \( |X^*| \ll |X| \)。

不太正式地说，即使父母分心，孩子也能轻松成长为语法流畅的“话匣子”！当然，语言远不止这些性质所试图捕捉的内容，我们也不声称类似的东西是自然语言的核心。尽管如此，如我们接下来所解释的，语言暗示了一种机制——机器可以实现的——用于实现具有上述性质的集合 \( X \)。每个语法句子背后（之下？之上？）都有其含义。语言的使用者能同样自如地将句子转换为含义，或将含义转换为句子。我们倾向于将含义视为跨语言共享的，而英语和印地语仅在句子的转换上有所不同。我们可以通过机器学习的自编码器架构来形式化这种看待语言的方式。自编码器接收某种语言的句子，轻松将其转换为紧凑的通用含义，并同样轻松地将含义转换回原始句子。句子由符号表示是众所周知的，而含义的表示则远非如此。如果我们将两者都表示为比特串，那么由于自编码器中的转换是确定性的，两种字符串具有相等的熵。一种有趣的情况是句子字符串比含义字符串长若干倍（超过 2 倍），且含义字符串的长度接近字符串（无论哪种）的比特熵。具有这些特征的自编码器只能在句子字符串的一个非常特殊的子集上充当恒等映射——那些具有关联含义字符串的句子——而这些句子定义了列表中的集合 \( X \)。要执行任务 1，只需输入 \( x \) 并检查 \( x \) 是否被输出。由自编码器输出半部分从自由采样的含义字符串生成的句子字符串，完成了任务 2。上述列表中的性质 3 仅仅是观察到：如果自编码器的复杂度可以被适当限制，那么通过适度的句子示例数量所提供的信息应该足以唯一地重建它。

语言示例迫使我们将自编码器两半的常规命名颠倒过来。含义是首要的，而语言是含义被编码到其中以及从中解码的码。在本文中，编码器始终是自编码器的输出半部分。语言也是我们将注意力从作用于集合的函数转移到集合本身背后的动机。MNIST 的遗产之一是对数据持“它们就是它们……”的态度，并且不让这种态度阻碍对完美分类的追求。虽然在机器学习的大多数应用（如果不是全部）中这是正确的态度，但在语言的情况下，我们可能会质疑数据（例如语法）是否值得同样不加置疑的永久性。假设 \( X_0 \) 是一种原始语言，第 0 代的使用者由于它的缺陷而学习得很差——作为自编码器 \( \mathcal{A}_0 \)。也就是说，\( \mathcal{A}_0(X_0) = X_1 \)，其中 \( X_1 \) 接近但不同于原始语言 \( X_0 \)。随着 \( X_1 \) 在群体中传播，第 1 代的使用者将开始学习语言 \( X_1 \)，同样不完美地作为 \( \mathcal{A}_1 \) 并引入另一个变体 \( \mathcal{A}_1(X_1) = X_2 \)。依此类推，其中改进变得越来越小，语言变得越来越容易学习。西班牙语可能不仅是最容易学习的语言，而且是最进化的语言！

机器可学习集中的**机器**限定词使我们的学习模型区别于之前的模型。与通过神经网络传递数据来处理数据相比，PAC 学习中的多项式时空限制显得奢侈。缩小的计算模型也符合我们对语言习得的经验：一种与“思考”不同的自动过程。任务 1 和 2 的自编码器实现显然符合这一描述。直到最近，任务 3（涉及神经网络训练）仍无法解决，因为离散表示和电路（编码器/解码器）重建超出了基于梯度优化的范围。然而，使用约束方法训练布尔阈值函数网络的初步结果[2 (https://arxiv.org/html/2606.28947#bib.bib3)]表明这些限制不再适用。

本文其余部分组织如下。相关工作在第二节 (https://arxiv.org/html/2606.28947#S2) 中回顾。机器可学习集在第三节 (https://arxiv.org/html/2606.28947#S3) 中以与应用无关的术语正式定义。语言的“含义字符串”只是另一个称为 \( Y \) 的集合。第三节 (https://arxiv.org/html/2606.28947#S3) 还介绍了性质 3（一种泛化形式）背后的理论，以及一个启发式论证，说明上述集合迁移过程（在迭代不完美的自编码器时）为何可能收敛。第四节 (https://arxiv.org/html/2606.28947#S4) 简要回顾了训练网络的约束方法，其中神经元——布尔阈值函数——具有严格的 \( \pm 1 \) 输出。从用户角度来看，使用布尔网络与使用标准网络并没有太大不同。学习算法不是最小化损失，而是“缩小差距”。第五节 (https://arxiv.org/html/2606.28947#S5) 和第六节 (https://arxiv.org/html/2606.28947#S6) 展示了完美和不完美机器可学习集的机器学习实验。在第一种情况下，当传递给网络的像素值被强制流经一层节点数仅为像素数一半的层时，自编码器非常快速地意识到它正在处理罗夏模式。通过翻转某些数据中镜像像素的对比度，任务变得更加困难。第二种情况（第六节 (https://arxiv.org/html/2606.28947#S6)）中的机器可学习集是“狂野的”，因为在其定义中没有简单的原则（如罗夏对称性）。我们首先考虑由随机编码器电路创建的集合 \( X_0 \)，而解码器（甚至其架构）是未知的。在第二个示例中，\( X_0 \) 是下采样的 MNIST，连编码器的存在与否都是未知的。然而，实验表明，通过受语言启发的迭代方案对 \( X_0 \) 进行改进（均使用相同的自编码器架构计算），会变得越来越机器可学习。本工作中统计学习理论（或任何已建立理论）的显著缺失在第七节 (https://arxiv.org/html/2606.28947#S7) 中讨论。虽然某种形式的保证在机器学习应用中始终有价值，但本文采取的更具探究性的方法提供了重要的补充。

## II. 相关工作  
我们惊讶地发现，启发我们工作的几个想法此前已由 Kirby 等人[8 (https://arxiv.org/html/2606.28947#bib.bib8), 7 (https://arxiv.org/html/2606.28947#bib.bib6)]提出。不仅是将共享硬件学习作为结构化数据（语言）演化基础的想法，还有“通过狭窄瓶颈传输的问题”[7 (https://arxiv.org/html/2606.28947#bib.bib6)]中呈现的更多技术细节。我们的工作可以视为这些想法的形式化提炼，包括在复杂度远低于语言的结构化数据上的演示。正如第七节 (https://arxiv.org/html/2606.28947#S7) 中更全面解释的，我们的方法超出了通常的统计学习框架。我们通过迫使所有激活都是离散的，并学习拒绝哪些潜在配置，从而无需分布。潜在变量为离散（通过向量量化）的变分自编码器由 van den Oord 等人[10 (https://arxiv.org/html/2606.28947#bib.bib7)]开发。该工作还表明，使用改进的基于梯度的优化器可以学习潜在变量上的分布。我们的基于约束的优化器允许所有神经元的输出都是离散的——这是限制自编码器复杂度所必需的性质。

## III. 机器可学习集  
机器可学习集是布尔字符串的集合。在定义它们之前，我们先定义该域上的函数集合。

###### 定义 III.1。 \( \mathcal{B}(m, n, k) \) 是布尔函数 \( \{0,1\}^m \to \{0,1\}^n \) 的一个类，该类可以用 \( k \) 比特信息指定。整数 \( m \) 和 \( n \) 分别称为输入维度和输出维度。在下一节（涵盖布尔函数的实现）中，我们将具体化到一类特定的函数。如果你需要在此期间更具体的想法，可以将 \( \mathcal{B}(m, n, k) \) 中的 \( k \) 视为电路中门数量的对界。一般来说，如果 \( 2n > m \)，则即使是随机编码器也具有非常高的概率是单射的。如果 \( M = 2^m \) 且 \( N = 2^n \)，则该概率等于  
\[
p_{\text{inj}} = \frac{M(M-1)\cdots(M-N+1)}{M^N}.
\]  
当 \( M \) 很大时，  
\[
\log p_{\text{inj}} \sim M \int_0^f \log(1-z) dz = -M \left( f + (1-f)\log(1-f) \right),
\]  
其中 \( f = N/M \)。由于 \( f = 2^{-(m-n)} \to 0 \)（对于大的 \( m \) 且 \( m > 2n \)），我们可以只保留 (1) 中小 \( f \) 的领先阶项，结果为  
\[
p_{\text{inj}} \sim e^{-N^2/(2M)} = e^{-2^{2n-m-1}}.
\]  
对于固定的 \( m/n > 2 \)，这随 \( m \) 指数趋近于 1。引言中给出的机器可学习集的前两个性质直接来自定义 III.2 (https://arxiv.org/html/2606.28947#S3.Thmtheorem2)。使用自编码器测试 \( x \in \{0,1\}^m \) 是否是 \( X \) 的元素“容易”是因为解码器和编码器的复杂度界限。要均匀采样 \( X \) 的元素，首先生成 \( y \in \{0,1\}^n \) 的均匀样本，将其编码为 \( x = \mathcal{E}(y) \)，然后使用自编码器测试 \( x \in X \)。根据定义 III.2 (https://arxiv.org/html/2606.28947#S3.Thmtheorem2) 中的第二个性质，测试成功的概率为 \( c \)，或平均需要 \( 1/c \) 次尝试才能获得 \( X \) 的一个样本。因此，只要 \( c \) 不是太小，采样也将是“容易的”。只有在 \( \mathcal{E} \) 是单射时，样本才是严格均匀的，但如上所示，当 \( m > 2n \) 时，即使是随机编码器也具有很高的概率是单射。

#### III.0.2 经验容量  
在应用中，通常没有定义 III.2 (https://arxiv.org/html/2606.28947#S3.Thmtheorem2) 中容量 \( c \) 的值。然而，拒绝采样过程使我们能够经验性地确定容量：  
\[
c = \underset{y \in \{0,1\}^n}{\text{prob}} \left( \mathcal{A}(\mathcal{E}(y)) = \mathcal{E}(y) \right),
\]  
其中 \( y \) 是从均匀分布采样的。在本文其余部分，\( c \) 表示经验估计的容量。

#### III.0.3 自编码器复杂度  
由于自编码器 \( \mathcal{A} \) 是解码器和编码器的复合，\( \mathcal{A} \in \mathcal{B}(m, m, k_{\mathcal{A}}) \)，其中 \( k_{\mathcal{A}} = k_{\mathcal{D}} + k_{\mathcal{E}} \)。然而，应注意其复杂度可能更低。如果 \( \Pi : \{0,1\}^n \to \{0,1\}^n \) 是任意双射，且  
\[
\begin{align*}
\mathcal{D}' &= \Pi \circ \mathcal{D} &&\in \mathcal{B}(m, n, k_{\mathcal{D}}'), \\
\mathcal{E}' &= \mathcal{E} \circ \Pi^{-1} &&\in \mathcal{B}(n, m, k_{\mathcal{E}}'),
\end{align*}
\]  
那么 \( \mathcal{E}' \circ \mathcal{D}' = \mathcal{E} \circ \mathcal{D} \) 定义了相同的自编码器。最小复杂度自编码器具有对数复杂度  
\[
\min_{\Pi} (k_{\mathcal{D}}' + k_{\mathcal{E}}').
\]  
由于 \( \Pi \) 仅对输入到编码器的样本进行置换，\( c \) 不受此影响。因此，当我们写 \( \mathcal{A} \in \mathcal{B}(m, m, k_{\mathcal{A}}) \) 时，理解为 \( \mathcal{A} \) 具有内部维度 \( n \)，且 \( k_{\mathcal{A}} \) 是解码器和编码器的对数复杂度之和。

#### III.0.4 信息充分性  
性质 3 中的短语“可以学习”需要在正式定义中详细说明。将其重新表述为“原则上可以学习”，并借助信息论，我们可以掌握这一性质。我们首先定义，对于任意 \( \mathcal{A} \in \mathcal{B}(m, m, k_A) \)，