Manifold Sampling via Entropy Maximization¶
会议: NeurIPS 2026
arXiv: 2605.12338
OpenReview: https://openreview.net/forum?id=mAVz31YJlN
代码: https://github.com/LIS-TU-Berlin/masem
领域: 优化/理论
关键词: 流形采样, 约束采样, 最大熵, 重采样, 机器人运动规划
一句话总结¶
针对非连通流形上传统局部 MCMC 采样器无法跨越不可行势垒正确分配分量概率质量的难题，提出通过 k 近邻密度估计进行最大熵重采样的 MASEM 框架，证明了其在均场下以几何速率指数收缩 KL 散度，并在合成与真实机器人基准上将 Sinkhorn 距离降低了一个数量级。
研究背景与动机¶
在机器学习与具身智能领域，从复杂约束分布中采样具有至关重要的应用，包括贝叶斯优化、分子构象生成、机器人避障运动规划以及强化学习初始复位状态生成。然而，实际系统中的可行集通常由高度非线性的光滑等式和不等式约束隐式定义，无法获得解析几何性质，且仅支持点值评估。现有的约束采样主流范式依赖于结合投影或着陆机制（Landing）的局部马尔可夫链蒙特卡洛（MCMC）方法（如投影郎之万动力学、约束 HMC、非线性 Hit-and-Run 即 NHR 以及流形着陆扩散采样 OLLA）。
这些局部约束采样方法的核心矛盾在于：它们严重依赖局部转移核，移动范围严格受限于可行集的单个连通分支。当流形因障碍物割裂或复杂几何拓扑而分解为若干互不相连的连通分量时，局部核无法穿越不可行障碍区域，从而根本无法感知各分量的测度大小，导致粒子群在各孤立分支间的质量分配严重失衡；而传统的软约束退火方案（如 SCMC）虽然允许穿越不可行域，但极易退化到局部约束极小值，且在收敛时无法保证严格可行。
本文的切入角度是：无需为跨分量跳转设计复杂的全局几何跳跃核，而是借助最大熵原理来统摄流形上的均匀采样，利用局部 k 近邻（k-NN）距离非参数化估计流形经验密度，并通过序列蒙特卡洛（SMC）式的重要重采样动态重合粒子质量。核心 idea：将约束流形均匀采样转化为经验分布的熵最大化过程，利用基于 k 近邻距离的反比重要性重采样机制自动向上调低密度分量分配粒子，证明其在均场下以几何收缩率逼近均匀目标，且可无缝即插即用至任意局部约束采样器。
方法详解¶
整体框架¶
MASEM（Manifold Sampling via Entropy Maximization）旨在从隐式光滑等式 \(h(x)=0\) 与不等式 \(g(x)\le 0\) 定义的有界流形 \(\Sigma = \Sigma_1 \sqcup \cdots \sqcup \Sigma_C \subset \mathbb{R}^d\) 上均匀采样。系统输入为约束函数及初始化尺度 \(\sigma^2\)，输出为经验分布逼近流形最大熵均匀分布的目标粒子集。整体流程分为两个核心阶段：首先在高斯先验下通过高斯-牛顿法沿松弛变量投影获得可行粒子并混匀，随后交替执行基于 k 近邻逆密度的熵最大化重采样与保持流形可行性的局部核再混淆（Rejuvenation）。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["环境先验高斯采样<br/>x ~ N(0, σ²I)"] --> B["松弛变量投影<br/>高斯-牛顿下降至可行集 Σ"]
B --> C["可行性保持核再混淆<br/>K 执行局部充分混合"]
C --> D["k近邻逆密度估计<br/>计算粒子局部半径 ε_i,k"]
D --> E["熵最大化重要性重采样<br/>基于几何平均逆密度重分配质量"]
E --> F["松弛约束惩罚修正<br/>抑制不可行粒子被过度复制"]
F --> G["流形核推进与再平衡<br/>局部混合核 K 执行 M 步迭代"]
G -->|未达迭代上限 T| D
G -->|完成 T 轮迭代| H["输出流形最大熵均匀样本集"]关键设计¶
1. 基于 k 近邻逆密度的最大熵重采样机制
为在未知流形分支拓扑与各分支绝对测度的前提下实现均匀覆盖，MASEM 锚定最大熵目标分布（即连续紧致流形上的均匀分布 \(u_\Sigma\)）。若当前流形上的粒子经验分布密度为 \(q(x)\)，根据重要性重采样原理，目标均匀密度 \(p(x) \propto 1\) 对应的最优重采样权重应正比于 \(p(x)/q(x) \propto q(x)^{-1}\)。在 \(p\) 维黎曼子流形上，第 \(i\) 个粒子的局部密度可通过其到第 \(k\) 个最近邻的欧氏距离 \(\varepsilon_{i,k}\) 以渐近一致形式估计为 \(\hat{\rho}(x_i) \propto \varepsilon_{i,k}^{-p}\)。MASEM 引入温度参数 \(\tau > 0\) 替代未知内蕴维度 \(p\)，将未归一化采样权重定义为粒子局部半径的幂函数： $\(w_i = \frac{\bar{w}_i}{\sum_{j=1}^N \bar{w}_j}, \qquad \bar{w}_i = \varepsilon_{i,k}^\tau\)$ 处于欠采样或粒子稀疏的连通分量中的样本具有显著更大的 \(k\)-NN 半径，从而被赋予更高的重采样权重。这一机制自然驱使粒子在后续重抽样中从过度聚集的分支复制转移至未饱和分支，且计算开销仅依赖近邻距离，无需显式聚类或分量体积重构。
2. 松弛约束惩罚与近邻距离几何平均方差缩减
在实际数值流形采样中，由于局部转移核无法做到绝对理想收敛，局部离群点或偏离流形的可行性违背粒子往往因周围邻居稀疏而表现出极大的 \(k\)-NN 距离，若直接应用重采样会导致严重违背约束的粒子被灾难性放大。针对该缺陷，MASEM 引入基于松弛变量（Slack）的自适应衰减因子： $\(w_i \leftarrow w_i \cdot \frac{1}{\exp(\mu \cdot \text{Slack}(x_i))}, \qquad \text{Slack}(x) = \frac{1}{2}(\|g(x)_+\|^2 + \|h(x)\|^2)\)$ 通过设置 \(\mu = 1000\)，强行截断脱靶粒子的权重增益。此外，单 \(k\) 近邻估计在有限样本下方差较大，MASEM 借鉴对比内蕴控制的思想，采用前 \(k\) 个邻居距离的几何平均值构造几何半径： $\(\bar{w}_i = \left(\prod_{j=1}^k \varepsilon_{i,j}\right)^{\frac{\tau}{k}}\)$ 该设计显著平滑了流形边缘及维度局部畸变带来的估计噪声，在保证单步重平衡效力的同时大幅提升了超参数选择的鲁棒性。
3. 均场收缩与局部再混淆协同保证
MASEM 采用模块化解耦设计：全局分量平衡由离散重采样承担，而分量内部的精细几何混合则交由通用的流形约束 MCMC 核 \(K\)（如 NHR 或 OLLA）完成。在理论分析上，设每个分量的粒子占比为 \(\alpha_c = N_c/N\)，目标测度比为 \(\alpha_c^* = \sigma_c / S\)。在 \(N \to \infty\) 的均场极限下，重采样诱导出单纯形上的非线性映射 \((\Phi \alpha)_c \propto \alpha_c^{1-\beta} (\alpha_c^*)^\beta\)（其中 \(\beta = \tau / p\)）。通过将迭代过程转化为以逆温度 \(a_t = (1-\beta)^t\) 衰减的累积生成函数分析，证明了单步迭代下经验分布与均匀目标之间的 KL 散度满足严格二次几何级数收缩： $\(D_{\mathrm{KL}}^\Sigma(p_{\alpha_t} \,|\, p_{\alpha^*}) \le C_0 \left(1 - \frac{\tau}{p}\right)^{2t}\)$ 只要初始化阶段粒子投影覆盖了全部连通支，系统在均场下将以指数速率消除跨分支质量分配偏差；结合有限步局部混淆核 \(M\)，不仅彻底规避了不可行屏障阻隔，更消除了局部流形曲率对全局采样的负面制约。
损失函数 / 训练策略¶
MASEM 为免训练（Training-free）的粒子系统采样算法。实验中统一在 JAX 框架下以 2000 个并行链执行 5000 次目标函数评估。投影步使用阻尼 Gauss-Newton 进行 500 步优化，并添加尺度 \(\epsilon=0.01\) 的高斯扰动以提升模式覆盖概率。针对超参数选择，推荐使用通用的标准免调参数组合：温度 \(\tau = 0.3\)，再混淆步数 \(M = 20\)，近邻数 \(k = 20\)；在内蕴维度未知时，选取保守温度 \(\tau < p\) 即可确保算法稳定收敛。
实验关键数据¶
主实验¶
主实验在 5 组具有挑战性的低维流形上评估采样质量，包括球面上连通与非连通的双圆盘（Connected / Disconnected Disks, 3d）、高曲率七叶形流形（Seven Lobes, 2d）、被不等式截断为离散弧段的正弦曲线（Sine, 2d）以及由 6 个圆与阿基米德螺旋线组成的非连通瑞士卷（Swiss Roll, 2d）。评估指标采用衡量与真实几何均匀样本分布差异的二次 Sinkhorn 距离 \(\mathcal{W}_2^2\)（基于 5 个随机种子统计均值与 95% 置信区间）。
| 数据集 | 指标 (\(\mathcal{W}_2^2 \downarrow\)) | NHR 基线 | MASEM-NHR (本文) | OLLA 基线 | MASEM-OLLA (本文) |
|---|---|---|---|---|---|
| Connected Disks (3d) | \(\mathcal{W}_2^2\) | \(0.06 \pm 0.01\) | \(\mathbf{0.00 \pm 0.00}\) | \(0.04 \pm 0.00\) | \(\mathbf{0.00 \pm 0.00}\) |
| Disconn. Disks (3d) | \(\mathcal{W}_2^2\) | \(1.98 \pm 0.12\) | \(\mathbf{0.01 \pm 0.01}\) | \(1.95 \pm 0.11\) | \(\mathbf{0.02 \pm 0.00}\) |
| Seven Lobes (2d) | \(\mathcal{W}_2^2\) | \(0.37 \pm 0.02\) | \(\mathbf{0.05 \pm 0.02}\) | \(0.89 \pm 0.08\) | \(\mathbf{0.05 \pm 0.02}\) |
| Sine (2d) | \(\mathcal{W}_2^2\) | \(100.21 \pm 4.09\) | \(\mathbf{0.13 \pm 0.06}\) | \(128.38 \pm 3.79\) | \(\mathbf{0.13 \pm 0.07}\) |
| Swiss Roll (2d) | \(\mathcal{W}_2^2\) | \(6.08 \pm 0.75\) | \(\mathbf{0.08 \pm 0.02}\) | \(18.96 \pm 1.15\) | \(\mathbf{0.29 \pm 0.09}\) |
消融实验¶
为了对比不同全局平衡策略并检验流形可行性，实验对比了软约束退火方法 SCMC、显式聚类并估计簇体积重采样的 Cluster-NHR 以及 MASEM-NHR，同时记录了流形松弛度违背均值（\(\text{Slack} \times 10^{-3} \downarrow\)）。
| 配置 / 机制 | 七叶形 \(\mathcal{W}_2^2 \downarrow\) | 正弦波 \(\mathcal{W}_2^2 \downarrow\) | 瑞士卷 \(\mathcal{W}_2^2 \downarrow\) | 瑞士卷 Slack \(\times 10^{-3} \downarrow\) | 说明 |
|---|---|---|---|---|---|
| SCMC (退火软约束) | \(0.12 \pm 0.06\) | \(126.79 \pm 10.85\) | \(1.10 \pm 0.42\) | \(2.77 \pm 0.71\) | 易陷入局部极值，高度非线性下约束违背严重 |
| Cluster-NHR (显式聚类) | \(0.14 \pm 0.04\) | \(0.91 \pm 1.04\) | \(0.42 \pm 0.26\) | \(0.00 \pm 0.00\) | 启发式聚类容易出现分支归属错误与体积偏差 |
| MASEM-NHR (完整模型) | \(\mathbf{0.05 \pm 0.02}\) | \(\mathbf{0.13 \pm 0.06}\) | \(\mathbf{0.08 \pm 0.02}\) | \(\mathbf{0.00 \pm 0.00}\) | 隐式非参数化重平衡，兼具最低分布距离与零松弛违背 |
关键发现¶
- 在所有非连通流形问题（Disconn. Disks, Sine, Swiss Roll）上，MASEM 将底层局部采样器的 Sinkhorn 距离降低了 1 至 3 个数量级（例如在正弦曲线断裂流形上，NHR 误差高达 100.21，而引入 MASEM 后直接骤降至 0.13）。
- 在真实高维机器人实验（随机与网格障碍物轨迹规划、18 维三指胶囊抓取）中，MASEM 显著提升了可行熵（Feasible Entropy），成功探索出被基线完全漏采的狭窄核心通道与对偶同伦类轨迹；且对 OLLA 这类原本在流形边界易产生穿透的采样器提升尤为明显。
- 敏感度分析表明，当温度参数 \(\tau\) 小于流形内蕴维度 \(p\) 时，收敛稳定且对 \(M\) 和 \(N\) 展现极强鲁棒性；即使在 100 个孤立分量的极端测试下，每个分量仅需平均 4 条链即可将分支灭绝（Component Loss）概率压制在 0.1% 以下。
亮点与洞察¶
- 将 SMC 重要性重采样与局部 \(k\)-NN 密度估计优雅结合，不依赖显式流形分量划分或体积积分即可实现纯隐式跨分支质量再平衡。
- 理论证明极为完备，首次给出非连通流形约束采样在均场意义下的严格 KL 散度几何收敛界 \((1-\tau/p)^{2t}\)。
- 引入松弛违背指数惩罚 \(\exp(-\mu \cdot \text{Slack})\) 与几何平均邻域距离，巧妙兼顾了理论收敛性与数值工程中对不可行离群点的鲁棒抑制。
局限与展望¶
- 理论收敛速度及分量保全保证建立在 \(N \to \infty\) 的均场极限和局部核充分混合假设之上，有限粒子与高维小样本下的混合漂移仍需更深入的测度下界分析。
- 每次重采样需计算成对粒子间距离，虽可通过近似近邻搜索（ANN）压低开销，但在海量粒子与极高环境维度下仍存在额外的内存与计算常数。
- 当前聚焦于流形上的最大熵均匀采样，未来推广至非均匀任意目标分布（如流形上的玻尔兹曼分布采样）极具理论与实际价值。
相关工作与启发¶
- vs NHR / OLLA: 传统局部约束采样核局限于单一连通分支内部移动，MASEM 提供了正交且通用的外层重采样封装，以极低开销解决跨势垒质量调配。
- vs SCMC: SCMC 通过松弛约束构建平滑退火势场，但在强非凸约束下极易退化且终态无法保证严格可行；MASEM 始终在流形邻域推进，最终松弛度维持在零误差级别。
- vs Cluster-NHR: 显式聚类方法在未知复杂流形上极易产生连通性误判与维数灾难，MASEM 基于局部近邻距离的隐式逆密度加权更加优雅且具通用性。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次提出利用 k 近邻逆密度估计结合重采样解决非连通流形约束均匀采样难题，理论与框架设计极具启发性。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖低维几何基准、高维曲率压力测试以及复杂机器人运动规划和多指抓取，指标严谨。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严密流畅，实验设计由浅入深，图表呈现与问题刻画非常清晰。
- 价值: ⭐⭐⭐⭐⭐ 为强化学习安全探索、机器人灵巧操作及多模态动力系统提供了坚实的高质量多样化数据采样工具。