Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

本文提出通过采用拉丁超立方和索博尔采样方法设计初始训练数据，以确保独热编码中的边际位完全覆盖，从而增强具有二次优化退火（FMQA）的因子分解机算法，进而提升其在整数和离散化连续变量问题上的优化性能。

要点

想象一下，你正在为一款人力飞机寻找完美的机翼形状。你希望它飞得尽可能快，但涉及的物理原理过于复杂，无法用简单的公式来预测速度。相反，你必须构建一个虚拟模型，进行测试，观察其飞行速度，然后再次尝试。这是一个“黑箱”问题：你输入一个设计方案，就会得到一个速度输出，但你不知道内部的“秘密配方”。

为了解决这个问题，研究人员使用了一种名为FMQA的智能计算机程序。将 FMQA 想象成一个两步走的侦探团队：

1. 代理（学生）：一个机器学习模型，它试图根据过去的测试来猜测答案。
2. 搜索者（猎人）：一台专用计算机（“伊辛机”），它利用“学生”的猜测来搜寻最佳的机翼形状。

问题：“静默”的位

为了让计算机理解机翼形状，研究人员使用一种称为**独热编码（one-hot encoding）**的方法，将连续的设计变量（如“机翼长度”）转换为一串二进制开关（0 和 1）。

想象你有 32 个代表“机翼长度”的开关。要表示长度为“中等”，你需要将 32 个开关中的恰好一个翻转到“开”（1）的状态，而让其余 31 个保持“关”（0）。

该论文指出了他们通常启动这一过程时存在的一个缺陷。他们通常通过掷骰子（随机采样）来选择初始的机翼形状。

• 问题所在：如果仅掷 32 次骰子作为初始阶段，那么在这些初始阶段中，某些 32 个开关从未被翻转到“开”状态的概率很高（约 36%）。
• 后果：“学生”（机器学习模型）通过观察处于“开”状态的开关来学习。如果某个开关从未处于“开”状态，“学生”就永远无法了解该特定设置如何影响速度。这就像一位老师试图给一个从未举手的学生的能力打分；老师没有关于该学生能力的任何数据。
• 结果：计算机对问题的“地图”存在盲点。当“猎人”寻找最佳解决方案时，它可能会忽略某些优质区域，因为地图显示：“我们不知道这里会发生什么。”

解决方案：“公平采样”策略

作者提出了一种选择初始机翼形状的新方法。他们不再仅仅依靠掷骰子，而是使用两种数学工具：拉丁超立方采样（LHS）和Sobol'序列。

将这些工具想象成一位公平检查员。

• 检查员不再指望运气能让每个开关翻转，而是确保在最初的 32 次测试中，32 个开关中的每一个都至少被翻转一次至“开”状态。
• 这保证了在真正的搜索开始之前，“学生”就能直接学习每一个可能的设置。没有任何开关被置于黑暗之中。

结果：更好的机翼，更快的速度

研究人员在两个版本的飞机机翼问题上测试了这种方法：一个包含 17 个设计变量，另一个更难的包含 32 个变量。

1. “旧方法”（随机）：即使运行了 200 次测试，在初始数据中仍有约 36% 的开关从未被打开。计算机的性能尚可，但存在盲点。
2. “新方法”（LHS 和 Sobol'）：从一开始，每个开关都至少被打开了一次。
   • 结果：新方法找到的机翼形状比旧的随机方法飞得更快。
   • 差异：对于较简单的问题，改进幅度较小，但对于更难的 32 变量问题，改进变得非常明显。这就像当地形变得更加复杂时，地图上的盲点就显得更加重要了。

核心启示

该论文并未声称这能让计算机亲自驾驶飞机，也未声称这能解决所有优化问题。它仅仅表明如何开始至关重要。

通过使用“公平采样”策略，确保每个可能的选项在初始训练数据中都有机会被看到，计算机就能构建出更好的问题地图。这使得它能够更快地找到更好的解决方案，尤其是在问题变得复杂时。这是一个提醒：在优化中，你不仅需要智能的搜索引擎，还需要一种聪明的方式来开启旅程。

技术摘要

技术摘要：通过考虑独热编码中边际比特覆盖的初始训练数据设计来改进 FMQA

问题陈述
带有二次优化退火的因子分解机（FMQA）是一种结合因子分解机（FM）代理模型与伊辛机进行搜索的黑盒优化（BBO）方法。当 FMQA 应用于整数或离散化连续变量并使用独热编码时，均匀随机初始采样会引发一个关键问题。在此场景下，初始训练数据集中的许多二进制变量（比特）可能永远不会取值为"1"。由于 FM 输出相对于与特定比特相关联的参数的梯度与该比特的值成正比，因此在整个初始数据集中始终保持为"0"的比特所对应的参数，无法从观测响应中获得直接的梯度更新。 Consequently，这些参数仅基于初始化和权重衰减进行演化，从而在估计的二次无约束二进制优化（QUBO）系数中引入偏差。这种偏差会降低伊辛机执行的解搜索质量，特别是在高维问题中。

方法论
作者提出了一种针对 FMQA 框架的修改方案，重点在于初始训练数据的设计。其核心目标是实现完全的边际比特覆盖，确保通过独热编码获得的每个二进制变量在初始数据集中至少取一次值为"1"。

为实现这一目标，作者引入了两种基于空间填充采样技术的初始数据生成方法：

1. LHS-FMQA：利用拉丁超立方采样（LHS）。
2. Sobol'-FMQA：利用 Sobol'序列（一种确定性低差异序列）。

这两种方法均配置为初始样本数（$N_0$）等于每个变量的离散值数量（$M$）。在独热编码下，每个原始变量由 $M$ 个二进制比特表示，设定 $N_0 = M$ 使得这些采样策略能够保证每个离散值至少被选择一次。通过解码映射，这确保了每个对应的二进制比特至少取一次值为"1"。这保证了所有 FM 参数在初始训练阶段都能获得源自数据集的直接梯度更新，从而减轻由“永不激活”比特引起的偏差。

主要贡献

• 偏差机制的识别：本文正式指出，独热编码 FMQA 中的均匀随机采样会导致“永不激活”的比特，致使特定的 FM 参数无法从观测到的黑盒响应中获取信息。
• 提出的初始化策略：作者提出并实施了利用 LHS 和 Sobol'序列的初始训练数据设计，专门用于强制实施边际比特覆盖（$N_0 = M$）。
• 实证验证：这些方法在人力动力飞机（HPA）机翼形状优化基准（HPA103）上进行了评估，这是一个具有隐式约束且无解析梯度信息的复杂工程问题。实验在两个问题规模上进行：17 个设计变量（HPA103-1）和 32 个设计变量（HPA103-2）。

结果
数值实验将所提出的方法（LHS-FMQA 和 Sobol'-FMQA）与基线 Conv-FMQA（均匀随机初始化）及其他优化器（GP-BO、NSGA-II、随机搜索）进行了比较，结果如下：

• 性能提升：所提出的两种方法实现的数值平均最终巡航速度均高于基线 Conv-FMQA。
• 维度依赖性：所提出方法的优势在高维问题（HPA103-2，32 个变量）中更为显著。在 17 变量问题上，最终巡航速度相对于基线的提升约为 LHS +0.135 m/s 和 Sobol' +0.192 m/s；而在 32 变量问题上，这一提升分别增加至 +0.333 m/s 和 +0.352 m/s。
• 机制确认：对比特使用分布的分析证实，尽管 Conv-FMQA 即使在完整评估预算后仍保留了约 36% 的“永不激活”比特，但所提出的方法实现了 0% 的“永不激活”比特。
• 与其他优化器的比较：所提出的方法表现与 GP-BO 和 NSGA-II 相当或更优。值得注意的是，相对于 Conv-FMQA 的改进是由初始采样阶段之后的优化过程（更高的“增益”）驱动的，而不仅仅是从更好的初始最佳值开始。

意义与主张
本文主张，改善初始训练数据中的边际比特覆盖是提升 FMQA 性能的关键因素。通过确保每个二进制变量至少激活一次，所提出的方法防止了 QUBO 系数在特定方向上仅由初始化和权重衰减决定。这使得伊辛机能够在所有设计维度上进行有信息的搜索。

作者谦逊地指出，虽然他们的结果支持了边际覆盖可减少偏差的假设，但当前研究并未完全将边际覆盖的效果与 LHS 和 Sobol'序列的空间填充属性隔离开来。他们承认，所提出的方法同时实现了这两种属性。此外，他们指出这些方法保证了边际覆盖，但并未保证成对比特覆盖（比特间的相互作用）。研究结论认为，这些初始化策略对于高维问题尤为有效，因为在随机采样中，否则潜在的非激活比特的绝对数量将会很大。未来的工作建议将边际覆盖与空间填充属性解耦，并研究成对覆盖策略。