概要：本次分析的论文为2023年发表于 Quantum Machine Intelligence 的文章： Feature selection on quantum computers，作者为Sascha Mücke、Raoul Heese、Sabine Müller、Moritz Wolter 和 Nico Piatkowski 。文章提出了一种新颖的特征选择框架，将特征与标签、特征间的互信息分别衡量为重要性和冗余性，并通过参数 α 线性插值，将选中特征子集问题转化为一个二次无约束二值优化（QUBO）问题。作者从理论上证明，对任意目标子集规模 k，都存在一个 α 使最优解恰好包含 k 个特征，无需额外惩罚项；并在经典求解器、量子计算真机等多种平台上开展实验，在 MNIST、Ionosphere、Madelon 等数据集上的分类和压缩重构任务中验证了其优越性能。

 

特征选择是机器学习中降低模型复杂度与提升可解释性的关键环节。传统方法往往依赖复杂的惩罚项或贪心搜索，难以同时兼顾全局最优性与可控子集规模。本文提出一种基于二次无约束二值优化（QUBO）的特征选择框架，通过互信息度量的重要性与冗余性插值，简洁地将选中特征数量映射到单一参数α的取值。该方法无需额外约束即可精确控制特征数量，且兼容经典优化器与量子计算硬件。文章在多组公开数据集及真实量子设备上验证了该框架的有效性与优越性。

一、方法介绍

该节介绍一种基于二次无约束二值优化（QUBO）的特征选择算法——QFS算法。首先构建优化目标，然后说明如何通过参数$\alpha$精确控制选中特征数量，最后给出完整的算法流程。假设有数据集
其中每个样本的特征向量x_i∈Rⁿ，标签y_i取自离散集合Y。将特征子集表示为二值指示向量

为同时最大化重要性并最小化冗余度，该文章构造目标函数
其中，I_i为第i个特征与标签间的互信息，衡量特征的重要性；R_ij为特征之间的互信息，衡量冗余度；α∈[0,1]用于平衡重要性与冗余度。该目标可写为矩阵形式

其中：

 

图1：QFS示意图

2. 互信息估计及边缘分布定义

直接计算互信息需估计连续特征的联合分布，难度大。为简化过程，文章对每个特征按分位数离散化为B个分箱，并定义离散化后的数据集

其中 b_ij∈[1,...,B]为样本j在第i维的箱号。经验概率定义为

由此得到边缘分布：

利用这些概率，可分别近似互信息

该离散化方式无需对原始分布做假设，且随着 B→∞，可收敛到真实互信息。为简化表示，后文省略对I_i和R_ij中离散化箱数的依赖。先从数据集中计算互信息形成I和R，然后插值生成 QUBO 矩阵，最后使用经典或量子求解器获得特征掩码。

3. 精确控制特征数量

若要强制选出恰好k个特征，可在原问题上添加约束：

该问题不再是标准 QUBO，可通过惩罚项恢复无约束形式：

其中λ>0为拉格朗日乘子。需要注意，一方面，λ的取值需根据Q的量级精心调整，过小会忽略约束，过大则损失数值精度；另一方面，大范围系数导致 QUBO 矩阵元素跨度过大，不利于求解器区分有效差异，也无法保证始终存在可行解。

基于此，文章提出无需惩罚的替代策略：当α=0时，Q只考虑冗余，最优解为空集或单个特征；当α=1时，仅考虑重要性，最优解为全体特征。通过在[0,1]上调节α，可使最优解的非零元素数||x*||₁以步长 1 单调从0变化到n。因此，只要二分搜索α即可获得任意给定的k。进一步地，为避免互信息近零的特征因噪声被随机选入，当αI_i<ε时，将对应对角元设置为微小正值μ，确保这些特征不会出现在最优解中。

4. 算法流程

基于上述性质，QFS算法采用二分查找框架：

1. 在区间[0,1]上初始化α，求解QUBO并计算x* 及其|x*||₁。
2. 若|x*||₁>k，则将上界更新为当前α；若 |x*||₁<k，则将下界更新为当前α。
3. 重复直至|x*||₁=k。
4. 输出最终α与特征指示向量x*。

图1. QFS算法伪代码。该算法需O(log n)次 QUBO 求解调用。

二、实验与结果

本节通过四组实验验证 QFS 方法，并在不同场景下进行性能对比。

1. 实验一：MNIST 数据集上的特征质量

文章在 MNIST 手写数字数据集上，对每个数字单独运行 QFS，固定选取 \(k=30\) 个像素作为特征。随后使用随机森林进行 1-vs-all 二分类，并与以下两种Baseline进行对比：  

全部特征：使用所有 784 个像素；  
随机特征：随机抽取 30 个像素（重复 5 次，取平均结果）。

结果显示，在所有 10 个数字类别中，QFS 选取的 30 个像素均能显著提升分类准确率优于随机子集，还在多数类别上超过了使用全部特征的模型，表明 QFS 能精准提取信息密度最高、冗余度最低的像素位置。

图2：基于 10 折交叉验证的分类准确率对比。三种方案分别为“所有像素”“随机选取 30 个像素”与“QFS 选取 30 个像素”。QFS 的准确率和稳定性明显优于基线。

2. 实验二：与其他方法的横向对比

在五个数据集（MNIST、Ionosphere、Madelon、Synth_100、Waveform）以及五种分类器（神经网络、逻辑回归、决策树、随机森林、朴素贝叶斯）上，对比 QFS 与三种常见 Filter/Wrapper 方法：  

1. 基于逻辑回归系数绝对值的排序；  
2. Extra Trees 分类器的 impurity-based 特征重要性；  
3. 基于决策树的递归特征消除（RFE）。  

所有模型均采用 10 折交叉验证。结果表明，QFS 在大多数组合中取得与 RFE 相当或略优的分类效果，且求解时间显著更短。在 Madelon 和 Synth_100 两个人工数据集上，由于其真实的“重要”特征已知，文章还计算了各方法选出子集与真实子集之间的编辑距离。QFS 的编辑距离最小，说明其子集选择更接近真值。

图3：不同方法选取特征后，各分类器在三个数据集上的 10 折交叉验证准确率对比。误差条表示一倍标准差，QFS 在大多数情况下具有竞争力。

图4：编辑距离网络图（Madelon 与 Synth100）。节点表示特征选择方法，边权为与“真实”重要特征集的编辑距离。QFS 更贴近真值，Extra Tree 紧随其后。

3. 实验三：基于 QFS 的图像压缩与重构

以 MNIST 为例，文章令k=25，使用 QFS 提取 25 个像素作为低维“潜变量”。然后构建一个小型卷积解码器，将这 25 维输入恢复为 28×28 的图像，并以均方误差（MSE）为损失训练。最终平均 MSE 为 0.0277，重构结果在视觉上与原始图像高度一致，证明 QFS 提取的少量像素包含了足够的结构信息，可用于高质量重建。

图5：QFS 选取 25 个像素后的压缩—解压流水线示意。左侧为原始图像，中心为按掩码提取的 25 维向量，右侧为解码器输出的重构图。

图6：20 个随机 MNIST 样本及其通过 QFS+CNN 解码后的重构对比。重构图与原图高度相似。

三、总结

该研究提出了一种基于 QUBO 的通用特征选择框架，通过将互信息度量的重要性与冗余性以插值参数 α 线性组合，既能最大化所选特征的信息含量，又能最小化冗余而仅用一个参数即可精确控制选中特征的数量。作者从理论上证明，对任意目标子集大小 k，始终存在一个 α 使得最优解恰好包含 k 个特征，无需额外惩罚项或复杂约束。该方法可表示为二次无约束布尔优化问题，既可调用经典启发式或精确求解器，也能映射到量子计算真机等平台。

通过在 MNIST、Ionosphere、Madelon 等多种公开数据集上的对比实验，QFS 在分类准确率和子集质量方面均表现出明显优势，既能超越随机选取，也能与递归特征消除等经典方法一较高下；在 MNIST 图像压缩重构任务中，25 个像素便可实现高保真重建，进一步体现了所选特征的信息承载能力。整体而言，该研究不仅在理论上打通了特征数量可控与 QUBO 求解之间的桥梁，也在实践中展示了良好的效果与扩展潜力，为更大规模或实时特征选择问题提供了新的思路。未来可在更高维度数据、不同互信息估计方法或更先进的量子硬件上，进一步探索该框架的应用边界。  

 

概要：本次分析的论文为2023年发表于 Quantum Machine Intelligence 的文章： Feature selection on quantum computers，作者为Sascha Mücke、Raoul Heese、Sabine Müller、Moritz Wolter 和 Nico Piatkowski 。文章提出了一种新颖的特征选择框架，将特征与标签、特征间的互信息分别衡量为重要性和冗余性，并通过参数 α 线性插值，将选中特征子集问题转化为一个二次无约束二值优化（QUBO）问题。作者从理论上证明，对任意目标子集规模 k，都存在一个 α 使最优解恰好包含 k 个特征，无需额外惩罚项；并在经典求解器、量子计算真机等多种平台上开展实验，在 MNIST、Ionosphere、Madelon 等数据集上的分类和压缩重构任务中验证了其优越性能。

 

特征选择是机器学习中降低模型复杂度与提升可解释性的关键环节。传统方法往往依赖复杂的惩罚项或贪心搜索，难以同时兼顾全局最优性与可控子集规模。本文提出一种基于二次无约束二值优化（QUBO）的特征选择框架，通过互信息度量的重要性与冗余性插值，简洁地将选中特征数量映射到单一参数α的取值。该方法无需额外约束即可精确控制特征数量，且兼容经典优化器与量子计算硬件。文章在多组公开数据集及真实量子设备上验证了该框架的有效性与优越性。

一、方法介绍

该节介绍一种基于二次无约束二值优化（QUBO）的特征选择算法——QFS算法。首先构建优化目标，然后说明如何通过参数$\alpha$精确控制选中特征数量，最后给出完整的算法流程。假设有数据集
其中每个样本的特征向量x_i∈Rⁿ，标签y_i取自离散集合Y。将特征子集表示为二值指示向量

为同时最大化重要性并最小化冗余度，该文章构造目标函数
其中，I_i为第i个特征与标签间的互信息，衡量特征的重要性；R_ij为特征之间的互信息，衡量冗余度；α∈[0,1]用于平衡重要性与冗余度。该目标可写为矩阵形式

其中：

 

图1：QFS示意图

2. 互信息估计及边缘分布定义

直接计算互信息需估计连续特征的联合分布，难度大。为简化过程，文章对每个特征按分位数离散化为B个分箱，并定义离散化后的数据集

其中 b_ij∈[1,...,B]为样本j在第i维的箱号。经验概率定义为

由此得到边缘分布：

利用这些概率，可分别近似互信息

该离散化方式无需对原始分布做假设，且随着 B→∞，可收敛到真实互信息。为简化表示，后文省略对I_i和R_ij中离散化箱数的依赖。先从数据集中计算互信息形成I和R，然后插值生成 QUBO 矩阵，最后使用经典或量子求解器获得特征掩码。

3. 精确控制特征数量

若要强制选出恰好k个特征，可在原问题上添加约束：

该问题不再是标准 QUBO，可通过惩罚项恢复无约束形式：

其中λ>0为拉格朗日乘子。需要注意，一方面，λ的取值需根据Q的量级精心调整，过小会忽略约束，过大则损失数值精度；另一方面，大范围系数导致 QUBO 矩阵元素跨度过大，不利于求解器区分有效差异，也无法保证始终存在可行解。

基于此，文章提出无需惩罚的替代策略：当α=0时，Q只考虑冗余，最优解为空集或单个特征；当α=1时，仅考虑重要性，最优解为全体特征。通过在[0,1]上调节α，可使最优解的非零元素数||x*||₁以步长 1 单调从0变化到n。因此，只要二分搜索α即可获得任意给定的k。进一步地，为避免互信息近零的特征因噪声被随机选入，当αI_i<ε时，将对应对角元设置为微小正值μ，确保这些特征不会出现在最优解中。

4. 算法流程

基于上述性质，QFS算法采用二分查找框架：

1. 在区间[0,1]上初始化α，求解QUBO并计算x* 及其|x*||₁。
2. 若|x*||₁>k，则将上界更新为当前α；若 |x*||₁<k，则将下界更新为当前α。
3. 重复直至|x*||₁=k。
4. 输出最终α与特征指示向量x*。

图1. QFS算法伪代码。该算法需O(log n)次 QUBO 求解调用。

二、实验与结果

本节通过四组实验验证 QFS 方法，并在不同场景下进行性能对比。

1. 实验一：MNIST 数据集上的特征质量

文章在 MNIST 手写数字数据集上，对每个数字单独运行 QFS，固定选取 \(k=30\) 个像素作为特征。随后使用随机森林进行 1-vs-all 二分类，并与以下两种Baseline进行对比：  

全部特征：使用所有 784 个像素；  
随机特征：随机抽取 30 个像素（重复 5 次，取平均结果）。

结果显示，在所有 10 个数字类别中，QFS 选取的 30 个像素均能显著提升分类准确率优于随机子集，还在多数类别上超过了使用全部特征的模型，表明 QFS 能精准提取信息密度最高、冗余度最低的像素位置。

图2：基于 10 折交叉验证的分类准确率对比。三种方案分别为“所有像素”“随机选取 30 个像素”与“QFS 选取 30 个像素”。QFS 的准确率和稳定性明显优于基线。

2. 实验二：与其他方法的横向对比

在五个数据集（MNIST、Ionosphere、Madelon、Synth_100、Waveform）以及五种分类器（神经网络、逻辑回归、决策树、随机森林、朴素贝叶斯）上，对比 QFS 与三种常见 Filter/Wrapper 方法：  

1. 基于逻辑回归系数绝对值的排序；  
2. Extra Trees 分类器的 impurity-based 特征重要性；  
3. 基于决策树的递归特征消除（RFE）。  

所有模型均采用 10 折交叉验证。结果表明，QFS 在大多数组合中取得与 RFE 相当或略优的分类效果，且求解时间显著更短。在 Madelon 和 Synth_100 两个人工数据集上，由于其真实的“重要”特征已知，文章还计算了各方法选出子集与真实子集之间的编辑距离。QFS 的编辑距离最小，说明其子集选择更接近真值。

图3：不同方法选取特征后，各分类器在三个数据集上的 10 折交叉验证准确率对比。误差条表示一倍标准差，QFS 在大多数情况下具有竞争力。

图4：编辑距离网络图（Madelon 与 Synth100）。节点表示特征选择方法，边权为与“真实”重要特征集的编辑距离。QFS 更贴近真值，Extra Tree 紧随其后。

3. 实验三：基于 QFS 的图像压缩与重构

以 MNIST 为例，文章令k=25，使用 QFS 提取 25 个像素作为低维“潜变量”。然后构建一个小型卷积解码器，将这 25 维输入恢复为 28×28 的图像，并以均方误差（MSE）为损失训练。最终平均 MSE 为 0.0277，重构结果在视觉上与原始图像高度一致，证明 QFS 提取的少量像素包含了足够的结构信息，可用于高质量重建。

图5：QFS 选取 25 个像素后的压缩—解压流水线示意。左侧为原始图像，中心为按掩码提取的 25 维向量，右侧为解码器输出的重构图。

图6：20 个随机 MNIST 样本及其通过 QFS+CNN 解码后的重构对比。重构图与原图高度相似。

三、总结

该研究提出了一种基于 QUBO 的通用特征选择框架，通过将互信息度量的重要性与冗余性以插值参数 α 线性组合，既能最大化所选特征的信息含量，又能最小化冗余而仅用一个参数即可精确控制选中特征的数量。作者从理论上证明，对任意目标子集大小 k，始终存在一个 α 使得最优解恰好包含 k 个特征，无需额外惩罚项或复杂约束。该方法可表示为二次无约束布尔优化问题，既可调用经典启发式或精确求解器，也能映射到量子计算真机等平台。

通过在 MNIST、Ionosphere、Madelon 等多种公开数据集上的对比实验，QFS 在分类准确率和子集质量方面均表现出明显优势，既能超越随机选取，也能与递归特征消除等经典方法一较高下；在 MNIST 图像压缩重构任务中，25 个像素便可实现高保真重建，进一步体现了所选特征的信息承载能力。整体而言，该研究不仅在理论上打通了特征数量可控与 QUBO 求解之间的桥梁，也在实践中展示了良好的效果与扩展潜力，为更大规模或实时特征选择问题提供了新的思路。未来可在更高维度数据、不同互信息估计方法或更先进的量子硬件上，进一步探索该框架的应用边界。