🤖 AI

Learning with Boolean threshold functions

本文介绍了一种基于投影的约束满足方法，该方法利用 reflect-reflect-relax 算法来训练具有严格 $\pm 1$ 布尔值和权重的神经网络，从而能够发现比标准梯度下降方法在离散任务上表现更优的稀疏且具解释性的逻辑门网络。

原作者： Veit Elser, Manish Krishan Lal

发布于 2026-08-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Veit Elser, Manish Krishan Lal

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代人工智能的广袤版图中，教导计算机识别模式的主流方法依赖于一种被称为“反向传播”的技术。这种方法将学习视为一个逐渐精炼的过程，其中一个由互连节点组成的网络通过计算微小的误差并将其平滑化，在数百万个步骤中不断调整其内部连接。这是一个强大的工具，但它运行在一个连续数值的世界里，其中的数值可以是从零到无穷大的任何值，且最终结果通常是一个复杂的、不透明的浮点数网络。虽然这在图像和语音识别方面取得了卓越成就，但当问题本身本质上是离散的——涉及严格的“是或否”决策或二进制逻辑时，它就留下了空白。对于需要数字电路般的精确度或逻辑规则般的清晰度的任务，标准训练那种平滑且具有概率性的本质，感觉就像是在尝试用湿沙来建造石墙。

一支研究团队提出了一条不同的路径，他们放弃了“最小化误差”的想法，转而追求“满足严格的逻辑约束”。他们不再要求计算机缓慢地向解靠近，而是要求它寻找一个能让每一条规则都同时被完美遵守的状态。这种方法不将神经网络视为一个近似答案的系统，而是将其视为一组必须处于“全开”或“全关”状态的开关。通过强制网络遵循这些刚性条件，研究人员开发出了一种能够训练机器学习精确逻辑电路的方法，从而以传统方法难以实现的清晰度，发现数据的底层规则。

这种新方法的核心在于一种特定类型的决策单元，称为“布尔阈值函数”。想象一个神经元，它输出的不是模糊的“也许”或类似 0.5 的数值，而是做出一个明确的选择：输出要么是正一，要么是负一。为了确保这种决策具有说服力，研究人员规定内部计算必须远离零，以避免歧义。这创造了一个确定性的“裕度”（margin）。当网络在这些条件下进行训练时，它不仅仅是在寻找一个良好的拟合，而是在搜索一种配置，在这种配置下，每个节点的决策在数学上都能根据其输入得到保证是正确的。研究人员发现，通过强制执行这种严格性，网络会自然地实现自我简化。复杂的连接网络会坍缩成一种稀疏的结构，其中仅保留少数核心链路，且这些链路上的权重会变成简单的整数，即正一或负一。

为了解决这个困难的谜题，研究人员采用了被称为“划分与一致”（divide and concur）的策略。他们将训练整个网络的庞大问题分解为两个较小且易于处理的部分。第一部分是“划分”步骤，它孤立地观察每个神经元，确保其特定的输入和权重满足严格的逻辑规则。第二部分是“一致”步骤，它从整体上看待网络，确保一个神经元的输出与下一个神经元的输入相匹配，并且在所有数据样本中使用的权重集是一致的。算法随后在两种视角之间交替，利用反射与松弛的几何过程，使孤立的决策与全局结构达成一致。这是一个协调的过程，算法迭代地调整其内部状态，直到局部规则与全局架构完美对齐。

应用此方法的实验结果令人瞩目，尤其是与标准的基于梯度的算法相比。在一系列实验中，研究人员要求网络学习各种逻辑谜题背后的规则。在其中一个案例中，他们要求系统发现二进制数乘法的电路规则。虽然标准训练方法即使使用大量数据也难以达到完美的准确度，但这种基于约束的方法找到了精确解。网络重建了乘法所需的精确逻辑门，揭示了一个由简单的“与”（AND）门和“或”（OR）门组成的电路。在另一个涉及细胞自动机（一种细胞根据邻居状态改变自身状态的系统）的测试中，该方法成功学习了控制系统演化的复杂规则。它展现出的泛化能力使其能够预测从未见过的系统行为，而标准方法在可靠性方面未能复制这一成就。

这项工作最引人入胜的方面之一是结果的可解释性。因为网络被强制仅使用简单的二进制权重，最终的模型是透明的。研究人员可以通过观察训练后的网络，立即看到哪些连接是活跃的，以及每个节点正在执行何种逻辑功能。无需猜测“黑盒”在想什么；逻辑是清晰可见的。例如，在乘法任务中，网络揭示了乘积的最低有效位仅仅是两个因子最低有效位的逻辑“与”运算，这是算法直接发现并编码的数学基本事实。这种清晰度延伸到了网络本身的结构中，其结构往往比标准方法所需的更加简单，使用更少的连接和更少的层级即可达到相同甚至更好的效果。

研究人员还探索了该方法如何处理并非完全干净或严格二进制的数据，例如手写数字图像。即使输入数据是模拟且带有噪声的，该方法也表现出了鲁棒性。通过调整裕度约束的严格程度，他们可以控制网络偏离完美解的程度。当裕度设置得非常大，强制网络变得极其果断时，它在测试数据上的准确度高于裕度较小时的情况。这表明，追求清晰、自信决策的压力起到了强大的正则化作用，防止网络过度拟合训练数据中的噪声，并帮助其学习真正的底层模式。

这项工作并不声称要取代过去四十年建立的庞大深度学习生态系统。相反，它为一类特定问题提供了一个独特的替代方案——在这些问题中，答案不是一个概率，而是一个事实。它表明，对于涉及逻辑、推理和离散结构的任务，通往智能的路径可能不在于平滑误差，而在于对约束的严格满足。该方法证明，通过将基本问题从“我们如何减少误差？”转变为“我们如何满足规则？”，我们能够构建出以清晰、逻辑化方式思考的机器，其精度和透明度是长期以来难以企及的。研究人员已经证明，这种基于约束的方法不仅是一个理论上的奇思妙想，更是训练能够以清晰逻辑思维的神经系统的可行且强大的工具。

技术摘要：基于布尔阈值函数的学习

问题陈述
本文探讨了在严格的布尔数据（所有节点值限制为 $\pm 1$ ）上训练神经网络所面临的挑战。标准的基于梯度的优化方法（反向传播）依赖于可微激活函数（如 Sigmoid）和连续权重。虽然这些方法可以近似布尔行为，但往往无法产生严格的二进制输出或稀疏、可解释的权重结构（例如，权重严格为 $\pm 1$ ）。此外，在需要从有限数据中实现高泛化能力或满足严格逻辑约束的场景下，梯度下降往往难以找到精确解，或者收敛到缺乏可解释性的表示（例如，权重值为 $0.5$）。作者提出了一种替代框架，将神经网络训练视为一个约束满足问题，而非损失函数的最小化问题。

方法论
核心方法论使用布尔阈值函数 (Boolean Threshold Functions, BTFs) 取代了损失最小化，将其转化为一个非凸约束问题。

布尔阈值函数 (BTFs)：
每个节点实现一个函数 $y = \text{sgn}(w \cdot x)$ ，其中输入 $x$ 和输出 $y$ 严格为 $\pm 1$ 。至关重要的是，该方法施加了一个间隔约束 (margin constraint)： $|w \cdot x| \ge \mu$ 。这确保了网络在决策时具有“确定性”，避免了零点附近的“灰色地带”。间隔 $\mu$ 定义为 $\mu_m = \sqrt{m/\sigma}$ ，其中 $m$ 是输入数量， $\sigma$ 是支持超参数。该约束强制学习到的表示具有稀疏性；具体而言，如果 $\sigma$ 较小（例如 $\sigma=3$ ），BTF 在数学上等价于具有相等量级权重（ $\pm 1$ ）的简单逻辑门（如 Copy、AND、OR、Majority）。
分而治之与一致性 (Divide-and-Concur) 框架：
训练问题被分解为两个互补的约束 $A$ 和 $B$ ，并使用 反射-反射-松弛 (Reflect-Reflect-Relax, RRR) 投影算法进行求解：
- 约束 A (Divide/划分)： 确保每个 BTF 的局部一致性。对于每个神经元和每个数据实例，三元组（权重、输入、输出）必须满足 BTF 的定义和间隔约束。该约束针对每个节点和数据项独立处理。
- 约束 B (Concur/一致)： 确保架构的一致性。它使一个神经元的输出等于下一个神经元的输入（ $y_{out} = x_{in}$ ），并且关键在于，强制权重向量在所有数据实例化中保持一致。
- 数据约束： 输入数据被投影到输入节点（约束 A），输出目标被投影到输出节点（约束 B）。
RRR 算法：
该算法迭代地将系统状态 $z$ 投影到集合 $A$ 和 $B$ 上。更新规则为 $z' = z + \beta(P_B(R_A(z)) - P_A(z))$ ，其中 $R_A$ 是反射操作， $\beta$ 是步长。与最小化标量损失的梯度下降不同，RRR 旨在寻找两个集合 $A \cap B$ 的交点。如果交集为空（不可行），算法会收敛到一个具有最小间隙 $\Delta = \|z_A - z_B\|$ 的“近邻对 (proximal pair)”。
度量自动调优 (Metric Auto-Tuning)：
为了提高收敛性，该方法采用一种启发式方法来调整度量系数 ( $g_{qi}$ )，根据每个神经元和数据项的局部间隙大小重新分配变量变化，以避免停滞。

主要贡献

基于约束的学习： 为离散系统提出了一种严谨的梯度下降替代方案，将学习定义为寻找几何约束交点中的可行点，而非最小化损失景观。
具有可证明稀疏性和可解释性的模型： 证明了通过调节间隔超参数 $\sigma$ ，该方法能迫使网络采用等效于简单逻辑门且权重为 $\pm 1$ 的稀疏结构。这消除了实现稀疏性所需的后验剪枝或正则化。
离散领域的精确解： 表明对于布尔原生任务，该方法可以找到精确解（零间隙），而梯度下降方法即使经过大量迭代也无法达到 100% 的准确率。
通过模型偏差实现泛化： 作者认为，这种约束方法自然地融入了强烈的归纳偏置（稀疏性、布尔逻辑），从而允许从极小的数据集（例如，从 256 个样本中学习逻辑电路）中实现完美泛化。

实验结果
作者通过六个应用验证了该方法：

乘法器电路发现： 该方法成功从真值表重建了精确的 2 位和 3 位乘法器电路。它识别出了正确的逻辑门（AND、OR、NOT）和拓扑结构。相比之下，梯度下降即使经过多次迭代也无法达到 100% 的测试准确率。
二进制自编码： 该方法实现了真正的二进制编码-解码（输出严格为 $\pm 1$ ），适用于 $k=3,4,5$ 位；而使用 Sigmoid 的标准反向传播则会产生非二进制值（如 $0.5$）。
MNIST 生成 (4s)： 使用 One-hot 编码，该方法从 1024 个样本中生成了 16 张数字“4”的“原型”图像。虽然该问题是不可行的（不存在完美的 BTF 生成器来处理此类数据），但算法找到了一个近邻对，将数据聚类为 16 个子集，重建准确率为 81%，与二进制 k-modes 相当。
MNIST 分类 (模拟数据)： 在 8x8 下采样的 MNIST 数字上应用该方法，结果显示，强制执行大间隔（使问题变得不可行）实际上比小间隔提高了泛化准确率，这表明“硬”约束有助于分离类别。
逻辑电路推理： 该方法从输入-输出对中学习了随机 5 层逻辑电路（AND/OR 或 Majority 门）。一旦训练样本数超过理论信息论阈值（约 132–176 个样本），它表现出向 100% 测试准确率的锐利转变，这一现象在梯度下降中并未观察到。
细胞自动机 (Rule 30)： 该方法从输入-输出模式中学习了 Rule 30 细胞自动机规则。它成功识别了底层的逻辑结构（等效于特定的 AND/OR/Majority 门的组合）。带有稀疏惩罚项的梯度下降在同一任务上难以达到 100% 的准确率。

意义与主张
论文声称，基于投影的约束满足为离散神经网络的学习提供了一个“可行且概念上截然不同的基础”。

可解释性： 所得模型本质上是可解释的，即由简单的逻辑门和 $\pm 1$ 权重组成的网络，消除了连续权重带来的“黑盒”性质。
效率： 使用 $\pm 1$ 权重进行推理仅需整数加法，这可能降低数据中心的功耗。
数据效率： 该方法证明，强结构约束（布尔逻辑、稀疏性）允许从极少量的样本中学习复杂规则，在“刺激贫乏 (poverty of stimulus)”环境下优于梯度方法。
理论立场： 作者承认，虽然针对非凸约束满足的严谨“学习定理”仍难以捉摸（类似于反向传播在历史上面临的挑战），但 RRR 间隙在不同任务中消失的经验一致性表明该方法是鲁棒的。他们认为这并非要取代所有的梯度下降学习，而是作为一种专门的、强大的工具，用于处理布尔原生问题以及对严格可解释性有要求的场景。

论文最后概述了未来的工作方向，包括分布式处理、Python 接口，以及开发能够将连续权重解转换为等效 $\pm 1$ 权重网络的模型解释器。

技术摘要：基于布尔阈值函数的学习

类似论文