🤖 machine learning

Stage-dependent integer-binary encoding in factorization-machine black-box optimization

本文提出了一种具有二次优化退火（FMQA）框架的阶段依赖型因子分解机，该框架利用单热编码进行代理学习，并利用畴壁编码进行伊辛机搜索，证明了虽然学习阶段的单热编码是优化性能的主要驱动力，但在细粒度离散化条件下，切换到用于搜索的畴壁编码可以进一步提升结果。

原作者： Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：用两张不同的地图破解谜题

想象你是一名侦探，正试图在一片广袤且大雾弥漫的山脉中（黑盒优化问题）寻找最低点。你无法看到完整的地图；你只能派一名侦察兵去某个特定地点，测量海拔，然后汇报回来。你的目标是以尽可能少的次数找到山谷的最深处（全局最优解），因为每一次出巡都会耗费大量的金钱和时间。

为了高效地完成任务，你建立了一个代理模型（surrogate model）——即根据你已经访问过的地点绘制的一份地形粗略草图。然后，你使用一台超级快速的计算机（伊辛机/Ising Machine）来观察你的草图，并预测哪里可能是最低点。

Ogawa、Nakano、Seki 和 Tanaka 的这篇论文解决了一个关于这个过程的具体问题：如何将现实世界翻译成超级计算机能理解的语言？

问题所在：一种语言并不适用于所有场景

在过去，研究人员在整个过程中使用单一的“翻译方法”（称为整数-二进制编码）。他们使用同一种方法来进行：

学习： 根据数据训练草图（代理模型）。
搜索： 要求超级计算机在草图上寻找最佳位置。

作者们意识到，最适合学习的“语言”可能与最适合搜索的“语言”不同。这就像写小说：你可能会用一套特定的词汇来教导学生如何写作，但会用另一套完全不同的规则来评判他们的期末考试。

解决方案：“阶段依赖型”策略

该团队提出了一种名为 Stage-Dependent FMQA 的新框架。他们不再在整个旅程中使用同一种翻译方法，而是在中途切换语言。

他们测试了两种主要的用于将数字翻译成二进制代码（0 和 1）的“语言”：

独热编码 (One-Hot Encoding)： 想象一排电灯开关。要表示数字“3”，你只需打开第 3 个开关。它非常清晰且具有辨识度，但需要更多的开关。
域壁编码 (Domain-Wall Encoding)： 想象一排多米诺骨牌。要表示“3”，你只需推倒前三个骨牌，让剩下的骨牌保持直立。它更紧凑，并在倾倒与直立之间创造了一个平滑的“墙”。

神奇之处：
作者们推导出了一个数学公式，可以将“草图”从 One-Hot 语言转换为 Domain-Wall 语言（反之亦然），且不会丢失任何信息。这使得他们能够：

使用 One-Hot 进行学习（因为它能让草图非常精确）。
使用 Domain-Wall 进行搜索（因为超级计算机在这种格式下寻找答案的速度更快、更可靠）。

他们将这种特定的组合称为 OhDw 方法（One-Hot 用于学习，Domain-Wall 用于搜索）。

实验：拉斯特里金山 (Rastrigin Mountain)

为了测试这一点，他们使用了一个著名的、极具挑战性的测试函数，称为 Rastrigin 函数。

类比： 想象一个景观，周围布满了数以千计的小型、完全相同的陨石坑（局部最优解），而中心则有一个巨大的、深邃的峡谷（全局最优解）。你非常容易陷入一个小陨石坑，并误以为找到了底部。
设置： 他们在不同规模（维度）和不同精细程度（离散化水平）的山脉上进行了测试。

结果：为什么切换有效

实验揭示了一些引人入胜的见解：

学习是关键： 成功的最重要因素是学习阶段所使用的语言。使用 One-Hot 编码来构建草图，其效果始终优于使用 Domain-Wall 或标准二进制编码。看起来 One-Hot 能帮助 AI 更清晰地“看见”地形。
搜索需要助力： 一旦草图构建完成，在搜索阶段切换到 Domain-Wall 编码有助于超级计算机更好地在地形中导航，尤其是在复杂、高细节度的场景下。
黄金平衡点：
- 对于简单的、低细节的问题，仅使用 One-Hot 就足够了。
- 对于复杂的、高细节的问题（拥有许多微小陨石坑的大型山脉），OhDw 方法（切换语言）是明显的赢家。它比任何其他方法都能更准确、误差更小地找到峡谷的底部。

核心启示

论文的结论是，在 AI 优化领域，并非一种尺寸适用于所有情况。

正如木匠可能会用细齿锯切割精细的木材，而用重锤驱动钉子一样，这种新方法表明，我们应该使用 One-Hot 编码来进行学习（因为它精确），并使用 Domain-Wall 编码来进行搜索（因为它高效）。通过在正确的时刻切换工具，我们可以更快、更准确地解决复杂的优化难题。

简而言之： 不要用同一张地图既用来研究领土，又用来导航。要为手头的任务选择最合适的地图，这样你就能更快找到目的地。

技术摘要：因子分解机黑盒优化中的阶段相关整数-二进制编码

问题陈述
黑盒优化（BBO）旨在解决目标函数缺乏显式解析形式且评估成本高昂的问题。具有二次优化退火功能的因子分解机（FMQA）是一种突出的 BBO 方法，它利用因子分解机（FM）构建代理模型，并使用伊辛机（Ising machine）对其进行优化。FMQA 的一个关键组件是通过整数-二进制编码（例如，独热编码、域壁编码或二进制编码）将整数或连续变量转换为二进制变量，从而将问题表述为二次无约束二进制优化（QUBO）模型。

传统的 FMQA 在机器学习阶段（代理模型构建）和解搜索阶段（伊辛机优化）均采用单一的整数-二进制编码方法。然而，先前的研究表明存在一种权衡：域壁编码通常在伊辛机中表现出更优的解搜索性能，而独热编码则被观察到能在整个 FMQA 优化过程中产生更低的目标函数值。这种差异意味着，对于学习代理景观（landscape）最优的编码可能与对于搜索该景观最优的编码不同。传统方法通过固定单一编码，可能无法充分利用 FM 和伊辛机的不同能力。

方法论
作者提出了一种阶段相关的 FMQA 框架，该框架在机器学习阶段和解搜索阶段使用不同的整数-二进制编码方法。该方法的核心包括：

双重编码策略： 该框架使用适合学习的编码（具体而言，在提出的“OhDw”变体中使用独热编码）来训练 FM 代理模型，然后在由伊辛机进行优化之前，将生成的代理模型转换为另一种适合搜索的编码（具体而言，使用域壁编码）。
QUBO 矩阵转换： 为了实现这种切换，作者推导了独热编码与域壁编码之间 QUBO 矩阵的数学转换公式。这些公式确保了在可行整数状态下，代理目标景观在相差一个加性常数的情况下得以保留。
- 从独热到域壁的转换涉及使用特定的求和关系（公式 18–20）将 QUBO 矩阵 $Q^{(oh)}$ 的对角项和非对角项转换为 $Q^{(dw)}$ 。
- 逆向转换（域壁到独热）也被推导出来（公式 22–24）。
- 这些相互转换的计算复杂度确定为 $O(N^2q^2)$ ，其中 $N$ 是输入维度， $q$ 是离散化层级。
算法工作流：
- 学习阶段： 使用经过独热编码处理的输入-输出数据训练 FM。
- 转换： 将训练好的代理模型（以 QUBO 矩阵表示）从独热编码转换为域壁编码。
- 搜索阶段： 将转换后的 QUBO 结合域壁编码约束，使用伊辛机（Fixstars Amplify 退火引擎）进行优化，以寻找候选解。
- 评估： 对解进行解码，针对真实的黑盒函数进行评估，并将其添加到下一轮迭代的训练数据集中。

核心贡献

框架提议： 引入了一种 FMQA 框架，该框架将学习阶段与搜索阶段的编码选择解耦，而不是在整个过程中固定单一编码。
理论推导： 推导了独热与域壁 QUBO 矩阵之间的相互转换公式，这些公式在保持可行状态下代理目标景观的同时，实现了编码的切换，从而避免了丢失已学习模型的保真度。
经验分解： 对整数-二进制编码的影响进行了数值分解，将其分解为学习阶段和解搜索阶段的贡献，并分别评估它们，以了解其对性能的不同影响。

实验结果
所提方法在 Rastrigin 函数（一个多峰基准问题）上进行了评估，输入维度 $N \in \{2, 5\}$ ，离散化层级 $q \in \{61, 301\}$ 。将所提方法的“OhDw”方案（学习阶段用独热，搜索阶段用域壁）与传统的单一编码变体（Oh、Dw、Bi）以及贝叶斯优化（BO）进行了比较。

学习阶段编码的主导地位： 在所有条件下，用于学习阶段的编码是决定优化性能的主导因素。采用独热编码进行学习的方法（Oh 和 OhDw）比使用域壁或二进制编码进行学习的方法始终能获得更低的残差误差。
阶段相关收益： 切换到域壁编码进行搜索阶段的收益取决于具体条件：
- 对于 $N=5$ 且 $q=301$ （更细的离散化，更大的搜索空间），OhDw 方法比 Oh 方法（仅独热）实现了更低的残差误差和更接近全局最优解。
- 对于 $N=5$ 且 $q=61$ ，Oh 方法的表现略优于 OhDw。
- 对于 $N=2$ ，未观察到 Oh 和 OhDw 之间有显著的性能差异。
搜索稳定性： 对解搜索阶段的分析表明，域壁编码允许伊辛机在可行状态之间进行更稳定的转换，而独热编码则需要经过违反约束的状态，这可能会降低搜索稳定性。

意义与主张
本文声称，整数-二进制编码的选择不仅是一个表示性的选择，还是一个设计元素，在 FMQA 的学习阶段和解搜索阶段发挥着不同的作用。主要发现是，学习阶段的独热编码是优化性能的主要驱动力，这可能是由于其构建准确代理模型的能力更强。然而，研究表明，采用阶段相关的编码——特别是将独热用于学习并结合域壁用于搜索——可以提供进一步的改进，特别是在输入维度较大且离散化更细、搜索空间更复杂的场景下。

作者总结道，虽然 OhDw 方法展现出了潜力，但其通用性仍需在更多样化的基准函数和实际设计优化问题上进行进一步验证。此外，对惩罚系数敏感性的系统分析以及对 QUBO 密度差异的分析仍是未来的研究方向。