arXiv:2507.08796cs.PLcs.LG2025-07

提出滤波等变函数,实现列表长度外推的规则化建模

Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists

  • 定义滤波等变函数类,保证移除元素后行为可预测
  • 提出合并算法,通过子列表行为完美外推输出结果
  • 揭示其与单纯形结构的几何对应,适用于序列建模任务

如何设计能超越已知输入/输出样本的函数?我们主张,一个‘好’的外推函数应遵循特定规则。本文聚焦列表函数中一种优美的规则性:即使移除某些元素,函数行为仍应保持可预测。在函数式编程中,过滤操作常用于表达此类移除。为此,我们提出一类新的函数语义类别——滤波等变函数(filter equivariant functions)。该类包含有趣实例,我们证明了若干基本定理,并将其与经典的映射等变函数类关联。此外,我们给出了滤波等变函数的几何解释,揭示其自然对应于特定单纯形结构。核心成果为合并算法,该算法通过分析函数在输入子列表上的表现,实现完全外推。

原文摘要 · Abstract (English)

What should a function that extrapolates beyond known input/output examples look like? This is a tricky question to answer in general, as any function matching the outputs on those examples can in principle be a correct extrapolant. We argue that a "good" extrapolant should follow certain kinds of rules, and here we study a particularly appealing criterion for rule-following in list functions: that the function should behave predictably even when certain elements are removed. In functional programming, a standard way to express such removal operations is by using a filter function. Accordingly, our paper introduces a new semantic class of functions -- the filter equivariant functions. We show that this class contains interesting examples, prove some basic theorems about it, and relate it to the well-known class of map equivariant functions. We also present a geometric account of filter equivariants, showing how they correspond naturally to certain simplicial structures. Our highlight result is the amalgamation algorithm, which constructs any filter-equivariant function's output by first studying how it behaves on sublists of the input, in a way that extrapolates perfectly.

函数建模序列外推等变性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。