学习随机约简
本文介绍了一种名为 Bitween 的自动化学习方法和工具，用于发现数学函数中的随机自约简 (RSR)。
RSR 允许使用自纠正器将不完全正确的函数转变为高概率正确的函数，其核心在于给定点的值可以通过计算相关随机点的函数值来恢复。
Bitween 通过线性回归学习框架，在发现 RSR 方面优于遗传算法、符号回归和混合整数线性规划等传统方法。
此外，研究人员还引入了 Agentic Bitween，这是一种神经符号方法，利用大型语言模型动态发现新的查询函数，从而超越了以往文献中常用的固定查询函数，并在 80 个科学和机器学习函数的基准测试中表现出色。
查看原文开头（英文 · 仅前 3 段）
View PDF
Abstract:A self-corrector for a function $f$ takes a black-box oracle computing $f$ that is correct on most inputs and turns it into one that is correct on every input with high probability. Self-correctors exist for any function that is randomly self-reducible (RSR), where the value $f$ at a given point $x$ can be recovered by computing $f$ on random correlated points. While RSRs enable powerful self-correction capabilities and have applications in complexity theory and cryptography, their discovery has traditionally required manual derivation by experts. We present Bitween, a method and tool for automated learning of randomized self-reductions for mathematical functions. We make two key contributions: First, we demonstrate that our learning framework based on linear regression outperforms sophisticated methods including genetic algorithms, symbolic regression, and mixed-integer linear programming for discovering RSRs from correlated samples. Second, we introduce Agentic Bitween, a neuro-symbolic approach where large language models dynamically discover novel query functions for RSR property discovery, leveraging vanilla Bitween as a tool for inference and verification, moving beyond the fixed query functions ($x+r$, $x-r$, $x \cdot r$, $x$, $r$) previously used in the literature. On RSR-Bench, our benchmark suite of 80 scientific and machine learning functions, vanilla Bitween surpasses existing symbolic methods, while Agentic Bitween discovers new RSR properties using frontier models to uncover query functions.
Subjects:
※ 出于版权考虑，仅引用前 3 段。完整内容请阅读原文。