CG4AI: 一种在约束条件下训练AI模型的列生成框架

# CG4AI：一种用于在约束下训练AI模型的列生成框架
来源：https://arxiv.org/html/2608.26375

Youcef Magnouche，单位：华为技术有限公司\, 法国研究中心, 18 Quai du Point du Jour, Boulogne\-Billancourt, 92100, 法国
Abderrahmane Driouch，邮箱：[driouch\.ab\.dr@gmail\.com](mailto:[email protected])，单位：华为技术有限公司\, 法国研究中心, 18 Quai du Point du Jour, Boulogne\-Billancourt, 92100, 法国
Sébastien Martin，单位：华为技术有限公司\, 法国研究中心, 18 Quai du Point du Jour, Boulogne\-Billancourt, 92100, 法国
Pierre Bauguion，邮箱：[firstname\.lastname@huawei\.com](mailto:[email protected])，单位：华为技术有限公司\, 法国研究中心, 18 Quai du Point du Jour, Boulogne\-Billancourt, 92100, 法国

###### 摘要

标准机器学习训练在数据集上最小化损失函数，但并不能保证所得模型能遵守预设的关于其输出的规则或约束。在许多实际应用中，从自主系统到网络路由，此类保证至关重要。我们提出了*CG4AI*，一个构建AI模型凸组合的框架，同时对组合后的输出施加线性约束。一个主问题线性规划 (LP) 确定最优混合权重，而一个定价子问题在LP对偶变量的引导下生成新模型，重点关注那些被违反最严重的约束。割平面程序将可行性保证扩展到训练集之外。我们将CG4AI应用于两个问题：(i) MNIST上的数字分类，我们展示了约束的四种不同用途：仅从约束中学习、提高对抗鲁棒性、纠正误分类样本以及强制输出重新标记；以及 (ii) 多商品流问题，在该问题中，对神经网络路由预测器施加链路容量约束。在MNIST和标准SNDLIB基准网络上的实验表明，CG4AI能可靠地生成可行的预测器，同时实现了比单模型基线更好的准确率。

###### 关键词

列生成，硬约束，神经网络，集成学习，多商品流，可信人工智能，线性规划，安全性

### 1 引言

人工智能模型正越来越多地被用于支持或自动化交通、医疗和电信等关键领域的决策。这些模型通常通过在标注数据集上最小化损失函数来进行训练。这一过程并未提供任何明确的保证，确保预测会遵守安全规则、物理定律或监管要求：模型可能在训练数据上表现正确，但在新输入上仍然产生不可行或不安全的输出。

当预测必须满足*硬约束*（即在任何情况下都不能违反的严格条件）时，这种局限性变得尤为重要。硬约束在许多场景中自然产生，例如自动驾驶汽车需要执行避碰规则，或放射治疗规划中，对于任何肿瘤配置，输送到健康组织的剂量都不得超过给定限值。它们也出现在网络路由中，用于预测满足链路容量约束的流量拆分。另一个有趣的应用是监管与合规领域，例如贷款模型必须始终遵守法律公平性要求，即使对于不常见的申请人信息也是如此。

在学习模型中强制执行此类约束具有挑战性。最常见的方法是在训练目标中添加惩罚项以抑制违反。这将硬约束转化为软约束，并且无法保证测试时的可行性。调整惩罚权重也众所周知地困难。更近期的方法将模型输出投影到可行集上（Min 和 Azizan, 2024 (https://arxiv.org/html/2608.26375#bib.bib1); Tordesillas et al., 2023 (https://arxiv.org/html/2608.26375#bib.bib2)）或将凸优化作为可微层嵌入（Amos 和 Kolter, 2017 (https://arxiv.org/html/2608.26375#bib.bib3)）。投影方法能严格满足约束，但在推理时需要解决一个优化问题，这增加了延迟并限制了可扩展性。优化层对于凸约束效果良好，但不能自然地扩展到组合或大规模场景。

在本文中，我们提出CG4AI，一个利用列生成在*训练期间*强制执行硬线性约束的框架。我们不是训练单个模型，而是构建一个凸集成：最终的预测器是多个更简单模型（即*列*）的加权组合，其权重由一个主LP确定。对集成输出的约束直接作为线性不等式加入主LP，这确保只要LP是可行的，组合预测器就是可行的。每个新列通过解决一个*定价问题*获得，该问题最小化LP的简约成本：一个结合了有监督训练损失和被违反最严重约束的对偶值的量。对偶变量在训练期间充当重要性权重，引导新模型关注当前集成未能满足约束的输入。当约束集合很大时，割平面程序在每次迭代中只添加被违反最严重的约束，保持LP的可处理性。

CG4AI相对于基于惩罚和基于投影的方法的主要优势在于，约束满足是在LP层面强制执行的，而不是通过软惩罚或事后校正。一旦LP可行，模型的凸组合就保证满足所有强制执行的约束，与各个模型的架构无关。CG4AI将任何类型的AI模型视为子问题，同时它接受自定义损失函数。

#### 贡献

这种将输出满足约束添加到列生成LP的提议机制使我们能够做出以下贡献：

1.  **1. CG4AI：在输出约束下的LP认证集成学习。** 我们提出了一个通用框架，用于构建AI模型的凸集成，使其组合输出满足给定的一组线性约束。一个主LP（具有与LPBoost (Demiriz et al., 2002 (https://arxiv.org/html/2608.26375#bib.bib4)) 相同的列生成结构，但有不同的目标函数和新的输出约束族）确定混合权重；一个定价子问题在LP对偶变量的引导下训练新模型。这从三个方面扩展了LPBoost：(a) 主LP包含对组合输出的*外部*约束，编码安全、物理或用户定义的要求；(b) 这些约束与可能完全独立于训练数据的AI模型输入相关联，将模型*必须*满足的要求与其*优化*的内容分离开来；(c) 自然处理多种约束类型，包括对抗鲁棒性、误分类样本纠正和输出重新标记，而无需修改框架。
2.  **2. 基于LP的训练 vs. 推理时投影。** 与HardNet (Min 和 Azizan, 2024 (https://arxiv.org/html/2608.26375#bib.bib1)) 和 RAYEN (Tordesillas et al., 2023 (https://arxiv.org/html/2608.26375#bib.bib2)) 在每个前向传播时将模型输出投影到可行集不同，CG4AI通过LP主问题在训练期间强制执行约束。一旦构建完成，AI模型的凸集成 (CE) 从LP继承可行性，推理时零运行时开销。
3.  **3. 扩展到连续输入空间的割平面方法。** 一个分离预言机在约束数据集中搜索被违反最严重的输入，并将其作为新的LP行添加，从而将可行性保证扩展到任何有限约束集之外。
4.  **4. 两个应用。** 在MNIST（概念验证）上，我们说明了四种约束类型：仅从约束中学习、对抗鲁棒性、误分类纠正和输出重新标记。在多商品流问题（主要用例）中，我们在41个SNDLIB基准配置上，对神经网络路由预测器强制执行链路容量约束。

本文结构如下。第2节 (https://arxiv.org/html/2608.26375#S2) 回顾相关工作。第3节 (https://arxiv.org/html/2608.26375#S3) 描述CG4AI框架。第4节 (https://arxiv.org/html/2608.26375#S4) 和第5节 (https://arxiv.org/html/2608.26375#S5) 介绍两个应用。第6节 (https://arxiv.org/html/2608.26375#S6) 给出结论和新的研究方向。

### 2 相关工作

我们回顾五条与CG4AI直接相关的工作路线：惩罚与拉格朗日方法、可微优化层、投影与架构方法、基于MIP的公式化，以及列生成在机器学习中的使用。

##### 惩罚与拉格朗日方法
将约束融入学习的最常见方法是在训练损失中添加惩罚违反的项。虽然易于实现，但这些软约束方法无法保证推理时的可行性，并且需要仔细调整惩罚权重 (Goodfellow et al., 2016 (https://arxiv.org/html/2608.26375#bib.bib5))。为了提供更原理化的处理，Chamon 和 Ribeiro (2020) (https://arxiv.org/html/2608.26375#bib.bib6) 基于PAC框架开发了约束学习的泛化理论，表明任何PAC可学习的类别在附加约束下也是可学习的，使用了对偶上升算法。Elenter et al. (2024) (https://arxiv.org/html/2608.26375#bib.bib7) 扩展了这项工作，并表明对偶上升方法的原始迭代在过参数化区域中可以是近可行和近最优的。增广拉格朗日方法已被应用于物理信息神经网络以强制执行硬等式约束 (Lu et al., 2021 (https://arxiv.org/html/2608.26375#bib.bib8))，但它们不能自然地推广到不等式或组合约束。

##### 可微优化层
Amos 和 Kolter (2017) (https://arxiv.org/html/2608.26375#bib.bib3) 引入了OptNet，它将凸二次规划作为可微层嵌入神经网络内，允许约束感知的端到端训练。可行性对前向传播中看到的输入得到保证，但对任意未见过的输入则不保证，并且该方法在大规模应用时成本高昂。Agrawal et al. (2019) (https://arxiv.org/html/2608.26375#bib.bib9) 通过CVXPYlayers框架将其推广到任意凸锥规划。Donti et al. (2021) (https://arxiv.org/html/2608.26375#bib.bib10) 提出了DC3，它通过可微的补全和校正程序强制执行硬约束：等式约束通过隐式补全满足，而不等式约束通过展开梯度步骤处理。DC3通常不保证可行性，并且对梯度步骤的数量敏感。

##### 投影与架构方法
Min 和 Azizan (2024) (https://arxiv.org/html/2608.26375#bib.bib1) 提出了HardNet，一个基于投影的框架，通过在每个前向传播后将网络输出投影到可行区域来保证约束满足，并具有通用近似保证。Tordesillas et al. (2023) (https://arxiv.org/html/2608.26375#bib.bib2) 引入了RAYEN，它以分析方式参数化一个可行的凸区域，并高效地投影到其上而无需迭代求解器，专注于连续凸约束。Balestriero 和 LeCun (2023) (https://arxiv.org/html/2608.26375#bib.bib11) 提出了POLICE，它通过对网络重新表述为给定区域上的连续分段仿射映射，在构造上强制执行仿射输出约束；这避免了任何运行时开销，但限于单个凸区域和仿射约束。Constante Flores et al. (2025) (https://arxiv.org/html/2608.26375#bib.bib12) 通过固定凸组合结合了一个任务网络（最小化损失）和一个安全网络（满足约束），其中组合的可行性由鲁棒优化对偶性保证。所有这些投影和架构方法都局限于凸约束或仿射约束，不能自然地扩展到组合或高维设置。

##### 基于MIP的公式化
Aftabi et al. (2025) (https://arxiv.org/html/2608.26375#bib.bib13) 将具有二元激活的已训练神经网络表述为混合整数规划，从而能够精确地执行组合约束。该方法在理论上是完备的，但无法扩展到大型网络。Tjeng et al. (2019) (https://arxiv.org/html/2608.26375#bib.bib14) 使用MIP公式化评估神经网络鲁棒性的相关工作，以及Anderson et al. (2020) (https://arxiv.org/html/2608.26375#bib.bib15) 在MIP框架内为ReLU网络开发了强松弛。

##### 列生成在机器学习中的应用
列生成主要在提升（boosting）的背景下用于机器学习。Demiriz et al. (2002) (https://arxiv.org/html/2608.26375#bib.bib4) 提出了LPBoost，将提升问题转化为线性规划并利用列生成求解：定价问题在对偶误分类成本的引导下生成新的弱学习器。Aziz et al. (2024) (https://arxiv.org/html/2608.26375#bib.bib16) 将这一思想扩展到CIFAR\-10上的深度CNN基础学习器。

##### CG4AI作为LPBoost的扩展
CG4AI直接建立在Demiriz et al. (2002) (https://arxiv.org/html/2608.26375#bib.bib4) 的LPBoost框架之上。令n∈Nn\\in\\mathbb\{N\}为训练数据集大小，II为所有可能的AI模型的集合。LPBoost解决以下关于学习器si:Rd→\{−1,\+1\}s\_\{i\}:\\mathbb\{R\}^\{d\}\\to\\\{\-1,\+1\\\}的混合权重λi≥0\\lambda\_\{i\}\\geq 0的线性规划：

max⁡ρ−ν∑j=1nδjs\.t\.∑i∈Iλi=1,∑i∈Iλisi\(x ̄j\)y^j\+δj≥ρ,∀j=1,n ̄\\max\\rho\-\\nu\\sum\_\{j=1\}^\{n\}\\delta\_\{j\}\\quad\\text\{s\.t\.\}\\quad\\sum\_\{i\\in I\}\\lambda\_\{i\}=1,\\sum\_\{i\\in I\}\\lambda\_\{i\}\\,s\_\{i\}\(\\bar\{x\}\_\{j\}\)\\,\\hat\{y\}\_\{j\}\+\\delta\_\{j\}\\;\\geq\\;\\rho,\\ \\forall j=\\overline\{1,n\}\(1\)其中x ̄j∈Rd\\bar\{x\}\_\{j\}\\in\\mathbb\{R\}^\{d\}是第j\-个训练样本，y^j∈\{−1,\+1\}\\hat\{y\}\_\{j\}\\in\\\{\-1,\+1\\\}是其标签，ρ\\rho是最小间隔待最大化，δj≥0\\delta\_\{j\}\\geq 0是每个样本的松弛变量，ν∈R\+\\nu\\in\\mathbb\{R\}^\{\+\}是正则化参数。间隔约束的对偶变量扮演误分类权重的角色（类似于AdaBoost），列生成定价寻找能最大程度降低加权训练误差的学习器is\_\{i\}。

CG4AI保留了LPBoost的列生成结构（列索引集II，混合权重λi\\lambda\_\{i\}，凸性约束），其中si:Rd⇒Rrs\_\{i\}:\\mathbb\{R\}^\{d\}\\Rightarrow\\mathbb\{R\}^\{r\}是一个通用AI模型，而非二分类器（即不是si:Rd→\{−1,\+1\}s\_\{i\}:\\mathbb\{R\}^\{d\}\\to\\\{\-1,\+1\\\}）。它在两个根本方面有所不同。
*(i) 不同的目标函数。* CG4AI最小化训练损失∑iLiλi\\sum\_\{i\}\\mathcal\{L\}\_\{i\}\\lambda\_\{i\}而非最大化间隔；这允许使用任何可微损失（交叉熵、MSE等），并且不限于二分类。
*(ii) 新的输出约束族。* 除了凸性约束∑iλi=1\\sum\_\{i\}\\lambda\_\{i\}=1，CG4AI为约束集中的每个点j添加形式为∑i∈Iλi∑q=1rajqsiq\(x ̄j\)≥bj\\sum\_\{i\\in I\}\\lambda\_\{i\}\\sum\_\{q=1\}^\{r\}a^\{q\}\_\{j\}s^\{q\}\_\{i\}\(\\bar\{x\}\_\{j\}\)\\geq\\;b\_\{j\}的行，该约束集可以完全独立于训练集。这些约束编码了对模型输出的外部要求（安全规则、物理