内容简介

黑盒优化指的是一些没有具体数学表达的优化问题，一种解决方案是引入代理模型去近似目标黑盒函数。通常假定代理模型是一个二阶或高阶交叉特征模型（形式与QUBO、HUBO相同）则可以使用量子算法求解。因子分解机(FMs)是一种监督学习方法，可以用于代理模型中特征系数的训练。本文将介绍利用交叉熵改进的因子分解机量子退火算法，以及高阶因子分解机对黑盒优化算法的可能改进。

相关论文1

标题：Black box optimization using QUBO and the cross entropy method
作者：Jonas N¨ußlein, Christoph Roch, Thomas Gabor, Jonas Stein, Claudia Linnhoff-Popien, and Sebastian Feld
期刊: Springer Nature Switzerland, 2023: 48-55

相关论文2

标题：Higher-Order Factorization Machines
作者：Mathieu Blondel, Akinori Fujino, Naonori Ueda, Masakazu Ishihata
会议: Advances in Neural Information Processing Systems, 2016, 29

01 因子分解机+量子退火（FMQA）

二阶交叉特征模型定义为

待训练的是参数w_ij，每个x_i都是独立变量。在处理稀疏矩阵时由于交叉项太少，参数训练容易不充分。如果借助矩阵分解的思路将w_ij看成是两个矩阵的乘积，重构特征系数后独立变量变少就可以达到用较少的数据得到特征矩阵的目的

其中w=(w₁,......,w_n)是一个n维向量;  v_i, v_j是低维向量（k维），V是由v_i组成的矩阵，<*>为两个k维向量的内积：

k是一个超参。根据线性代数，对于任意对称正半定矩阵W，只要k足够大，一定存在矩阵V使得。对于黑盒问题，往往是我们预先设定代理模型为QUBO问题的形式，然后借助因子分解机训练得到交叉项的信息。当我们的模型重写为上式之后，每个w_ij都是两个向量的内积，因此一定是对称的，此外只要对角元素足够大，就能保证W是半正定的。

对于交叉项可以做一些变换简化计算

原项求解的就是矩阵上三角之和，上式第1步就是整个矩阵之和减去矩阵的迹，然后求一半。经过这样的推导之后二阶FM最终表达为：

由此可以推导出FM对参数的梯度公式

有了梯度公式，就可以用各种基于梯度的算法来训练模型了，FMQA算法流程为：

（1） 随机初始化若干个解作为初始训练集

（2）FM训练得到初始QUBO模型

（3）在当前的QUBO模型（代理模型）下计算得到最优解

（4）计算黑盒模型的损失函数

（5）将新的解加入训练集并且重新训练更新QUBO模型

重复循环3-5步直到结束。

02 基于交叉熵的BOX-QUBO算法

交叉熵模型：交叉熵方法是一种通用的迭代优化方法。基本思想是给定一个参数的概率分布f(x;v)和一个目标函数g(x)，在从该概率分布采样X~f(x)和优化这个概率分布之间迭代。从随机参数v开始,然后对解X~f(x;v)进行采样，并按其值g(x)按递增顺序对其进行排序，最后调整参数v使得g(x)更大并获得新的概率分布f(x;v)。

Main idea：QUBO矩阵是一种低容量的代理模型，对于n个变量仅有n(n+1)/2可训练的变量，通常是对所有的训练数据做回归（如前文的FMQA）。然而随着问题规模的增大，因为其能训练的参数有限，表达能力也有限，损失函数的值往往会增大。本文的亮点是提出一种新的策略，仅对一小部分的训练数据做回归，对剩下的数据只做分类，因为分类对模型的表达能力要求更低。为此需要将训练集根据其解得质量（也就是能量）E(x)划分为两个集合：能量高的解H和能量低的解L:

注意我们的目标是找到一个解x^*始得能量最小。分类任务的目标就是将解集x分为高能和低能的部分，并且对低能解的集合L做回归。L的大小有超参k决定，例如k+0.03则L为所有样本的百分之3，因此回归会更加精准。

BOX-QUBO算法流程：

(1)随机初始化QUBO的矩阵Q

(2) 在当前的QUBO模型（代理模型）下，解出最好的k个解X^*（用QA等算法）

(3)计算黑盒模型的损失函数E(X^*)

(4)将这些解加入训练集D并且重新训练得到QUBO的矩阵Q，训练Q的过程则如上文所说，将训练集分为高能和低能两个部分，对低能部分进行回归。

在分类结束之后，Q会训练n个循环，这里n是一个超参文章中选取5-10之间。在每个循环中临时训练集T是动态创建的：所有低能矢量都在T内，而高能部分的矢量仅有一部分当前预测值小于阈值的属于T。临时训练集的损失函数是y_predict=x^TQx和y_target的均方误差，对低能部分其损失函数为E(x)，高能部分为

使用梯度下降来优化Q。

03  效果测试

文章在四个问题上测试对比了BOX-QUBO和FMQA方法：两个MAX-k-SAT、FVS和MaxClique。测试问题简介：

- MAX-SAT

令V=v₁,......,v_n为一组布尔变量且f为如下形式的布尔表达式：

该问题的任务是找到一组V使f(V)=1。MAX-SAT问题是SAT的变种，它所要求的是尽可能多的子句被满足，MAX-k-SAT中的k指子句的长度。

- Feedback Vertex Set (FVS)

假设G=(V,E)是一个包含V个顶点E条边，且有圈的有向图。圈的定义为从顶点v₈出发并在v₈结束的路径。FVS问题的目标是找到最小的子集使得图G=(V\V',E')是不包含圈的，即

- MaxClique

假设G=(V,E)是一个包含V个顶点E条边的无向图。图G的一个集团定义为一个子集中的任意两个顶点都被一条边相连，即。MaxClique的任务是找到给定图中最大的集团。

在测试中，将上述三个问题封装成Oracles以模拟黑盒问题的情形（即不知道具体的布尔表达式或者具体的图）。

求解的四个问题：

(1)Max-4-SAT , V=20, C=300

(2) Max-4-SAT , V=30, C=400

(3) FVS , V=25, E=200

(4) MaxClique , V=30, E=350

在MAX-k-SAT问题中，V为变量个数，C为子句个数；在FVS和MaxClique问题中，V为顶点个数，E为边数。对于每个问题都随机生成了15个例子使用进行求解。

首先先随机生成了2000个（问题1），和1000个（问题234）QUBO解作为初始训练集，两种算法都使用相同的初始训练集，将其中最好的结果做为基线（base）。同时每个例子都会使用白盒模型求解出一个最优解（optimum）。为了更好的衡量BOX-QUBO和FMQA两种方法的求解表现，定义了以下公式：

当f(y^*)=1时说明y^*与白盒模型求解出的最优解一致。

上图中的x轴表示迭代次数，y轴表示15个实例上f(y^*)的平均值：，其中y*是在当前迭代中实例i找到的最佳解的值。

除了BOX-QUBO和FMQA之外，还将各自的实例使用白盒模型的算法进行了求解以便进行比较。结果中有两点值得一提。首先可以看到在两个Max-4-SAT问题的结果中黑盒优化（包括BOX-QUBO和FMQA）找到的解决方案明显优于崔的白盒解决方案。但不是所有问题使用黑盒方法求解都比白盒方法更好，在FVS和MaxClique两个问题是白盒求解更有，但BOX-QUBO的结果要比FMQA更好。下表还展示了黑盒算法所用到的QUBO矩阵维数和白盒算法的对比。

04 高阶因子分解机

另一种提升黑盒优化效果的思路则是提高代理模型容量，QUBO模型由于参数太少，在面对更复杂的问题时会越来越无力。高阶因子分解机+HUBO模型可能是一个有用的方案。首先定义m阶因子分解机

其中定义 ( 按位相乘求和)。对于高阶项这种很复杂的形式，可以使用核函数来处理，对于阶数a≤m≤d定义ANOVA核

并定义A⁰(p,x):=1以及A¹(p,x):=<p,x>，则高阶因子分解机可改写为如下形式：

其中p_s^(t)是p^(t)的第s列。从这个角度看，我们可以将二阶及高阶因子分解机看作一种直接从数据中学习“支持向量”的核机器。

从上文的分析可知，对于训练高阶FM，ANOVA是主要的计算单元。论文2发展了一种动力学算法（Dynamic Programming, DP）来计算ANOVA核函数，并且在线性时间O(dm)计算其梯度。ANOVA核的一个特点是有如下递推关系

为p_j去掉一维后的(d-1)维矢量，同理。也就是说当其他项固定时A^m(p,x)是p_j的放射函数。记p的一个子矢量为，x同理，定义a_j,t:=A^t(p_1:j,x_1:j)，则前述递推关系写为

使用自下而上的方法在DP表中组织计算,从左上角开始初始化递归然后遍历表，得出右下角的最终结果。这个过程需要O(dm)的时间和内存。

在计算梯度时则利用反向传播，根据链式规则

整个梯度

05 总结

(1)通过在BOX-QUBO方法中同时使用分类和回归而不是单独的回归，对代理模型的容量提出了更低的要求，这提高了对未知解的泛化能力，从而使黑盒优化整体上更成功（找到更好的解）。

(2)对于部分问题，将白盒问题也考虑为黑盒求解能得到更好的解。

(3)使用HUBO表示的代理模型提高容量是另一种可能的优化思路，高阶因子分解机能帮助我们训练高阶的模型。

BOX-QUBO的代码：https: //github.com/JonasNuesslein/BOX-QUBO

FMQA代码：https://github.com/tsudalab/fmqa

————————————————

本文转载自CSDN博主：量子小Q

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/2401_83053014/article/details/136993546

内容简介

黑盒优化指的是一些没有具体数学表达的优化问题，一种解决方案是引入代理模型去近似目标黑盒函数。通常假定代理模型是一个二阶或高阶交叉特征模型（形式与QUBO、HUBO相同）则可以使用量子算法求解。因子分解机(FMs)是一种监督学习方法，可以用于代理模型中特征系数的训练。本文将介绍利用交叉熵改进的因子分解机量子退火算法，以及高阶因子分解机对黑盒优化算法的可能改进。

相关论文1

标题：Black box optimization using QUBO and the cross entropy method
作者：Jonas N¨ußlein, Christoph Roch, Thomas Gabor, Jonas Stein, Claudia Linnhoff-Popien, and Sebastian Feld
期刊: Springer Nature Switzerland, 2023: 48-55

相关论文2

标题：Higher-Order Factorization Machines
作者：Mathieu Blondel, Akinori Fujino, Naonori Ueda, Masakazu Ishihata
会议: Advances in Neural Information Processing Systems, 2016, 29

01 因子分解机+量子退火（FMQA）

二阶交叉特征模型定义为

待训练的是参数w_ij，每个x_i都是独立变量。在处理稀疏矩阵时由于交叉项太少，参数训练容易不充分。如果借助矩阵分解的思路将w_ij看成是两个矩阵的乘积，重构特征系数后独立变量变少就可以达到用较少的数据得到特征矩阵的目的

其中w=(w₁,......,w_n)是一个n维向量;  v_i, v_j是低维向量（k维），V是由v_i组成的矩阵，<*>为两个k维向量的内积：

k是一个超参。根据线性代数，对于任意对称正半定矩阵W，只要k足够大，一定存在矩阵V使得。对于黑盒问题，往往是我们预先设定代理模型为QUBO问题的形式，然后借助因子分解机训练得到交叉项的信息。当我们的模型重写为上式之后，每个w_ij都是两个向量的内积，因此一定是对称的，此外只要对角元素足够大，就能保证W是半正定的。

对于交叉项可以做一些变换简化计算

原项求解的就是矩阵上三角之和，上式第1步就是整个矩阵之和减去矩阵的迹，然后求一半。经过这样的推导之后二阶FM最终表达为：

由此可以推导出FM对参数的梯度公式

有了梯度公式，就可以用各种基于梯度的算法来训练模型了，FMQA算法流程为：

（1） 随机初始化若干个解作为初始训练集

（2）FM训练得到初始QUBO模型

（3）在当前的QUBO模型（代理模型）下计算得到最优解

（4）计算黑盒模型的损失函数

（5）将新的解加入训练集并且重新训练更新QUBO模型

重复循环3-5步直到结束。

02 基于交叉熵的BOX-QUBO算法

交叉熵模型：交叉熵方法是一种通用的迭代优化方法。基本思想是给定一个参数的概率分布f(x;v)和一个目标函数g(x)，在从该概率分布采样X~f(x)和优化这个概率分布之间迭代。从随机参数v开始,然后对解X~f(x;v)进行采样，并按其值g(x)按递增顺序对其进行排序，最后调整参数v使得g(x)更大并获得新的概率分布f(x;v)。

Main idea：QUBO矩阵是一种低容量的代理模型，对于n个变量仅有n(n+1)/2可训练的变量，通常是对所有的训练数据做回归（如前文的FMQA）。然而随着问题规模的增大，因为其能训练的参数有限，表达能力也有限，损失函数的值往往会增大。本文的亮点是提出一种新的策略，仅对一小部分的训练数据做回归，对剩下的数据只做分类，因为分类对模型的表达能力要求更低。为此需要将训练集根据其解得质量（也就是能量）E(x)划分为两个集合：能量高的解H和能量低的解L:

注意我们的目标是找到一个解x^*始得能量最小。分类任务的目标就是将解集x分为高能和低能的部分，并且对低能解的集合L做回归。L的大小有超参k决定，例如k+0.03则L为所有样本的百分之3，因此回归会更加精准。

BOX-QUBO算法流程：

(1)随机初始化QUBO的矩阵Q

(2) 在当前的QUBO模型（代理模型）下，解出最好的k个解X^*（用QA等算法）

(3)计算黑盒模型的损失函数E(X^*)

(4)将这些解加入训练集D并且重新训练得到QUBO的矩阵Q，训练Q的过程则如上文所说，将训练集分为高能和低能两个部分，对低能部分进行回归。

在分类结束之后，Q会训练n个循环，这里n是一个超参文章中选取5-10之间。在每个循环中临时训练集T是动态创建的：所有低能矢量都在T内，而高能部分的矢量仅有一部分当前预测值小于阈值的属于T。临时训练集的损失函数是y_predict=x^TQx和y_target的均方误差，对低能部分其损失函数为E(x)，高能部分为

使用梯度下降来优化Q。

03  效果测试

文章在四个问题上测试对比了BOX-QUBO和FMQA方法：两个MAX-k-SAT、FVS和MaxClique。测试问题简介：

- MAX-SAT

令V=v₁,......,v_n为一组布尔变量且f为如下形式的布尔表达式：

该问题的任务是找到一组V使f(V)=1。MAX-SAT问题是SAT的变种，它所要求的是尽可能多的子句被满足，MAX-k-SAT中的k指子句的长度。

- Feedback Vertex Set (FVS)

假设G=(V,E)是一个包含V个顶点E条边，且有圈的有向图。圈的定义为从顶点v₈出发并在v₈结束的路径。FVS问题的目标是找到最小的子集使得图G=(V\V',E')是不包含圈的，即

- MaxClique

假设G=(V,E)是一个包含V个顶点E条边的无向图。图G的一个集团定义为一个子集中的任意两个顶点都被一条边相连，即。MaxClique的任务是找到给定图中最大的集团。

在测试中，将上述三个问题封装成Oracles以模拟黑盒问题的情形（即不知道具体的布尔表达式或者具体的图）。

求解的四个问题：

(1)Max-4-SAT , V=20, C=300

(2) Max-4-SAT , V=30, C=400

(3) FVS , V=25, E=200

(4) MaxClique , V=30, E=350

在MAX-k-SAT问题中，V为变量个数，C为子句个数；在FVS和MaxClique问题中，V为顶点个数，E为边数。对于每个问题都随机生成了15个例子使用进行求解。

首先先随机生成了2000个（问题1），和1000个（问题234）QUBO解作为初始训练集，两种算法都使用相同的初始训练集，将其中最好的结果做为基线（base）。同时每个例子都会使用白盒模型求解出一个最优解（optimum）。为了更好的衡量BOX-QUBO和FMQA两种方法的求解表现，定义了以下公式：

当f(y^*)=1时说明y^*与白盒模型求解出的最优解一致。

上图中的x轴表示迭代次数，y轴表示15个实例上f(y^*)的平均值：，其中y*是在当前迭代中实例i找到的最佳解的值。

除了BOX-QUBO和FMQA之外，还将各自的实例使用白盒模型的算法进行了求解以便进行比较。结果中有两点值得一提。首先可以看到在两个Max-4-SAT问题的结果中黑盒优化（包括BOX-QUBO和FMQA）找到的解决方案明显优于崔的白盒解决方案。但不是所有问题使用黑盒方法求解都比白盒方法更好，在FVS和MaxClique两个问题是白盒求解更有，但BOX-QUBO的结果要比FMQA更好。下表还展示了黑盒算法所用到的QUBO矩阵维数和白盒算法的对比。

04 高阶因子分解机

另一种提升黑盒优化效果的思路则是提高代理模型容量，QUBO模型由于参数太少，在面对更复杂的问题时会越来越无力。高阶因子分解机+HUBO模型可能是一个有用的方案。首先定义m阶因子分解机

其中定义 ( 按位相乘求和)。对于高阶项这种很复杂的形式，可以使用核函数来处理，对于阶数a≤m≤d定义ANOVA核

并定义A⁰(p,x):=1以及A¹(p,x):=<p,x>，则高阶因子分解机可改写为如下形式：

其中p_s^(t)是p^(t)的第s列。从这个角度看，我们可以将二阶及高阶因子分解机看作一种直接从数据中学习“支持向量”的核机器。

从上文的分析可知，对于训练高阶FM，ANOVA是主要的计算单元。论文2发展了一种动力学算法（Dynamic Programming, DP）来计算ANOVA核函数，并且在线性时间O(dm)计算其梯度。ANOVA核的一个特点是有如下递推关系

为p_j去掉一维后的(d-1)维矢量，同理。也就是说当其他项固定时A^m(p,x)是p_j的放射函数。记p的一个子矢量为，x同理，定义a_j,t:=A^t(p_1:j,x_1:j)，则前述递推关系写为

使用自下而上的方法在DP表中组织计算,从左上角开始初始化递归然后遍历表，得出右下角的最终结果。这个过程需要O(dm)的时间和内存。

在计算梯度时则利用反向传播，根据链式规则

整个梯度

05 总结

(1)通过在BOX-QUBO方法中同时使用分类和回归而不是单独的回归，对代理模型的容量提出了更低的要求，这提高了对未知解的泛化能力，从而使黑盒优化整体上更成功（找到更好的解）。

(2)对于部分问题，将白盒问题也考虑为黑盒求解能得到更好的解。

(3)使用HUBO表示的代理模型提高容量是另一种可能的优化思路，高阶因子分解机能帮助我们训练高阶的模型。

BOX-QUBO的代码：https: //github.com/JonasNuesslein/BOX-QUBO

FMQA代码：https://github.com/tsudalab/fmqa

————————————————

本文转载自CSDN博主：量子小Q

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：https://blog.csdn.net/2401_83053014/article/details/136993546