跳转至

单调且可分离的集合函数：特征刻画与神经模型

文章背景与核心概要

本文研究了设计能够保持集合自然偏序关系（即 \(S \subseteq T\) 当且仅当 \(F(S) \leq F(T)\)）的集合到向量函数这一基础问题。作者将满足该性质的函数定义为单调且可分离（MAS）集合函数，并根据多重集与基础集的基数，确立了实现这些函数所需的向量维度的上界与下界。

对于无限基础集，MAS 函数并不存在，这促使作者引入了一种新颖的模型，该模型满足一种被称为“弱 MAS”的松弛性质，并具有赫尔德连续性（Hölder continuity）稳定性。他们还证明了 MAS 函数可用于构建通用模型，通过构造方式天然满足单调性，并能逼近所有单调集合函数。在各种集合包含任务上的经验评估表明，引入这种集合包含的归纳偏置，能够显著提升标准集合模型的性能。

arXiv: 2510.23634 [cs.LG]
DOI: 10.48550/arXiv.2510.23634
作者: Soutrik Sarangi, Yonatan Sverdlov, Nadav Dym, Abir De
提交时间: 2025年10月24日（最后修订：2026年8月25日）

摘要 (Abstract)

受集合包含问题应用的启发，我们考虑以下基础问题：我们能否设计出能够保持集合自然偏序关系的集合到向量函数，即 \(S\subseteq T \text{ 当且仅当 } F(S)\leq F(T)\)？我们将满足这一性质的函数称为单调且可分离（MAS）集合函数。

我们建立了获取 MAS 函数所需的向量维度的下界和上界，该维度是多重集基数与底层基础集基数的函数。在无限基础集这一重要情况下，我们证明了 MAS 函数并不存在，但我们提供了一个模型，该模型可证明地拥有我们称为“弱 MAS”的松弛性质，并且在赫尔德连续性的意义上是稳定的。我们还证明了 MAS 函数可用于构建通用模型，这些模型在构造上是单调的，并且能够逼近所有单调集合函数。在实验方面，我们评估了各种集合包含任务。实验结果表明，与未将集合包含作为归纳偏置的标准集合模型相比，使用我们的模型具有明显的优势。

Motivated by applications for set containment problems, we consider the following fundamental problem: can we design set-to-vector functions so that the natural partial order on sets is preserved, namely $S\subseteq T \text{ if and only if } F(S)\leq F(T) $. We call functions satisfying this property Monotone and Separating (MAS) set functions.

We establish lower and upper bounds for the vector dimension necessary to obtain MAS functions, as a function of the cardinality of the multisets and the underlying ground set. In the important case of an infinite ground set, we show that MAS functions do not exist, but provide a model which provably enjoys a relaxed MAS property we name "weakly MAS" and is stable in the sense of Holder continuity. We also show that MAS functions can be used to construct universal models that are monotone by construction and can approximate all monotone set functions. Experimentally, we consider a variety of set containment tasks. The experiments show the benefit of using our model, in comparison with standard set models which do not incorporate set containment as an inductive bias.