SOS Polynomials

该数据集名为SOS Polynomials，由柏林Zuse研究所和柏林工业大学的研究团队创建。数据集包含了超过1亿个SOS多项式，用于训练Transformer模型，以预测给定多项式的近似最小单项式基，从而大幅度减少相应SDP问题的规模。数据集的创建过程采用了反向采样技术，确保了生成的基础具有足够的代表性。该数据集在多项式优化、控制理论、机器人等领域有着广泛的应用前景，有助于解决多项式非负性验证这一NP难题。

This dataset, named SOS Polynomials, was developed by a research team from the Zuse Institute Berlin and the Technical University of Berlin. It contains over 100 million sum-of-squares (SOS) polynomials, and is used to train Transformer models to predict the approximate minimal monomial basis of a given polynomial, thereby drastically reducing the scale of the corresponding semidefinite programming (SDP) problems. The dataset was constructed using reverse sampling techniques, which ensures that the generated basis has sufficient representativeness. This dataset has broad application prospects in fields such as polynomial optimization, control theory, robotics and other relevant domains, and can help solve the NP-hard problem of polynomial nonnegativity verification.

搜集汇总

数据集介绍

构建方式

SOS Polynomials 数据集的构建采用了一种创新的反向采样策略。研究者首先随机采样一组单项式集合 B，随后生成一个半正定矩阵 Q，并通过 p(x) = z_B(x)^T Q z_B(x) 的形式构造多项式，从而确保 B 天然成为该多项式的一个有效平方和（SOS）基。为了覆盖多样的多项式结构，生成过程中系统性地变化了 Q 的矩阵类型，包括稠密满秩、非结构化稀疏、块对角以及低秩四种形态。此外，数据集的生成还调整了变量数量、多项式次数和项数，最终产出了超过一亿个 SOS 多项式样本，为 Transformer 模型的训练提供了丰富且具有代表性的监督数据。

特点

该数据集最为显著的特点在于其构建方式保证了每个多项式都拥有已知且近乎最小的 SOS 基，这为监督学习提供了高质量的标签。通过精心设计的反向采样流程，生成的基在经验上被验证与理论下界非常接近，从而使得模型能够学习到如何从庞大的候选单项式空间中精准识别出最紧凑的表示。数据集覆盖了从稠密到稀疏、从低秩到块对角等多种矩阵结构，并横跨了不同的变量维度和多项式次数，这赋予了模型强大的泛化能力，使其能够处理在训练中未曾见过的多项式结构。

使用方法

该数据集专为训练一个用于预测 SOS 基的 Transformer 模型而设计。使用时，首先将多项式按照特定规则进行分词处理，输入 Transformer 模型，模型则自回归地输出一个预测的单项式基。随后，通过一个包含覆盖性检查和迭代扩展的修复机制，对预测基进行验证和修正，以保证最终能够构造出有效的 SOS 分解。整个流程将机器学习预测与传统的半定规划求解器相结合，在保证正确性的前提下，通过预测出更小的基来显著降低后续 SDP 问题的求解规模，从而实现计算加速。

背景与挑战

背景概述

多项式非负性判定是全局优化、控制理论与机器人学等领域的核心难题，其NP-hard性质催生了和平方（Sum of Squares, SOS）松弛这一经典方法。然而，传统的SOS验证需借助半定规划（SDP）求解，其计算复杂度随单项式基的规模呈二次增长，成为制约实际应用的关键瓶颈。为应对这一挑战，柏林祖斯研究所与柏林工业大学等机构的研究人员于2025年提出了SOS Polynomials数据集，该数据集包含超过1亿个SOS多项式及其近最小单项式基的配对，旨在通过训练Transformer模型预测紧凑的单项式基，从而大幅压缩SDP的求解规模。这一开创性工作将机器学习引入SOS编程领域，为高维多项式优化问题的可扩展求解开辟了新路径。

当前挑战

SOS Polynomials数据集所面临的挑战主要来自两个方面。首先，多项式非负性判定本身是NP-hard问题，即便采用SOS松弛，寻找最小单项式基仍属计算难题；传统几何方法（如牛顿多面体）虽能缩减基规模，却往往无法达到理论下界，导致SDP求解效率低下。其次，在数据集构建过程中，生成上亿个带有近最小基标注的SOS多项式极为困难，研究者不得不采用反向采样策略——先随机生成正半定矩阵与基，再构造对应的多项式——以保证标注的准确性。此外，Transformer模型预测的基可能不完整，需设计系统性的修复机制（如覆盖修复与基于排列的评分扩展）来确保算法最终能正确验证SOS性质，这一修复过程的效率与鲁棒性同样构成关键挑战。

常用场景

经典使用场景

SOS Polynomials 数据集的核心应用场景在于为多项式非负性验证提供高效的监督学习范式。在全局优化、控制理论与机器人学等领域，判定多项式非负性是一个经典的 NP-难问题，而平方和（SOS）条件作为其充分松弛，通常需借助半定规划（SDP）求解。该数据集通过反向采样策略生成超过一亿个带有已知紧致单项式基的 SOS 多项式，覆盖稠密、稀疏、块对角与低秩四种矩阵结构，为训练 Transformer 模型预测近最小单项式基提供了海量高质量标注数据，从而将 SDP 的求解规模从指数级候选集压缩至近乎最优的极小基。

解决学术问题

该数据集直接回应了 SOS 规划中计算效率的核心瓶颈：传统方法依赖牛顿多面体或弦稀疏性等规则化基选择策略，但所获基往往远非最小，导致 SDP 维度随单项式基数二次增长。通过将基选择转化为序列预测任务，数据集支撑的 Transformer 模型能够学习多项式内部的结构模式，预测出比规则方法显著更紧凑的基，在超过 200 个基准数据集上实现相较于最先进求解器 100 倍以上的加速。其意义在于首次将学习增强算法引入 SOS 规划，在保持正确性保证的前提下，将多项式非负性验证的实用可扩展性推向新高度，为全局优化与控制综合等下游任务提供了更高效的数学工具。

衍生相关工作

该数据集衍生了一系列关于学习增强代数推理的经典工作。最直接的是本论文提出的 Neural Sum-of-Squares 框架，它结合 Transformer 预测与系统性修复机制，首次实现了带正确性保证的 SOS 基学习。后续工作包括利用大语言模型进行 SOS 必要条件推理的探索，以及将单项式嵌入与注意力机制推广至更广泛的代数计算任务（如边界基算法）。此外，该数据集为算法预测理论提供了新的实例，推动了带有预测的算法设计在组合优化与数学规划领域的交叉研究，其反向采样生成策略也为其他 NP-难问题的数据驱动求解提供了可复现的范式。