Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

技术摘要：噪声观测下学习核化支持向量机的自适应测量分配

问题表述
核方法，特别是支持向量机（SVM），传统上是在假设格拉姆矩阵（核矩阵）以精确、无噪声的精度可用的前提下构建的。然而，在量子机器学习（QML）等新兴领域中，核条目无法通过闭式函数计算。相反，它们必须从噪声观测中推断，通常被建模为参数化量子电路的重复伯努利试验或多项式试验（shots）。在这些设定下，核条目 $K_{ij}$ 的精度直接取决于分配给其估计的测量试验次数（$N_{ij}$）。

所解决的核心挑战是在 $O(n^2)$ 个独立核条目之间分配有限的全球测量预算（$N_{tot}$）。文献中的标准方法是均匀分配，即每个条目获得相同数量的试验。虽然均匀分配最小化了条目间的最大方差并确保了误差分布的对称性，但它是“任务无关”的。它未能考虑到 SVM 分类器对格拉姆矩阵的高度非均匀依赖。具体而言，SVM 解主要由训练点的稀疏子集（支持向量）及其相互作用决定。因此，均匀估计对于 SVM 而言本质上是次优的，因为它将资源浪费在对决策边界影响微乎其微的核条目上，而对关键区域采样不足。

方法论
作者提出了一种任务感知自适应测量分配策略，旨在从噪声伯努利观测中学习核化 SVM。该方法基于以下原则：测量资源应集中在核矩阵中对分类器几何结构和稳定性最为关键的区域。

该方法基于两个互补的信号：

1. 几何敏感性：这捕捉了核条目 $K_{ij}$ 对平方间隔 $\|w\|^2$ 的一阶影响。利用包络定理，敏感性推导为与 $\alpha_i \alpha_j y_i y_j$ 成正比，其中 $\alpha$ 为对偶系数。涉及支持向量（$\alpha > 0$）的条目对间隔有直接的、非零的影响，而非支持向量的条目则没有一阶影响。
2. 活跃集不稳定性：这量化了分类器离散结构变化的概率，具体指由于测量噪声导致数据点进入或离开支持向量集的可能性。这通过估计间隔残差 $\Delta_i = y_i f(x_i) - 1$ 跨越零点的概率来建模，利用决策函数的方差和标准正态累积分布函数进行近似。

算法框架
所提出的算法在一个多轮自适应循环中执行：

• 试点阶段：向所有条目分配少量均匀数量的试验，以生成初始核估计 $\hat{K}^{(0)}$ 并训练初步 SVM。这提供了支持向量集和对偶系数的粗略估计。
• 自适应轮次：在随后的每一轮中，算法为每个核条目计算成对分配分数 $s_{ij}$。该分数结合了几何敏感性（$|\alpha_i \alpha_j y_i y_j|$）和活跃集不稳定性（$P_i P_j$），并由参数 $\lambda$ 加权。分数进一步通过伯努利方差项进行调制，以优先考虑统计上不确定的条目。
• 资源再分配：剩余预算的一部分通过多项式采样按比例分配给这些分数，以确保整数试验计数。更新核估计并重新训练 SVM。
• 早停：当总预算耗尽或对偶系数稳定（通过轮次间 $y_i \alpha_i$ 的相对变化衡量）时，过程终止。该标准允许算法在分类器有效收敛后停止，避免不必要的测量。

主要贡献

1. 任务感知表述：本文将测量分配表述为 SVM 学习流程的组成部分，而非孤立的估计问题，明确强调了分类器对核条目的非均匀依赖。
2. 新颖的分配准则：作者引入了一种结合间隔敏感性和活跃集不稳定性的准则。这为基于梯度的分配策略（如自适应量子核分配中使用的策略）提供了一种可解释的替代方案，直接针对 SVM 决策边界。
3. 理论分析：该工作提供了理论分析，表明自适应分配的优势由诱导的核重要性结构的异质性决定。它识别了不同的机制：
   • 高结构机制：在对偶系数稀疏且权重具有异质性时，自适应分配显著优于均匀采样。
   • 低结构机制：当解近乎均匀时，自适应的好处减弱，由于均匀分配对估计噪声具有鲁棒性，可能更为可取。
4. 实证验证：在合成数据集和真实世界量子核（源自印第安松数据集）上的广泛实验表明，在固定预算下，自适应策略提高了支持向量恢复、间隔估计和决策函数精度。

结果与性能

• 固定预算性能：在固定测量预算下，自适应策略在任务相关指标（SV 块均方根误差、支持向量恢复和决策函数误差）上始终优于均匀分配，即使在第一轮细化之后也是如此。值得注意的是，虽然均匀分配通常能实现更低的全局核重构误差（所有条目的均方根误差），但它在决定分类器的特定条目上表现不佳。
• 早停：对偶系数稳定性标准使算法能够提前终止，通常仅使用总测量预算的一小部分（例如约 16%），即可实现与使用完整预算的均匀采样相当甚至更好的性能。
• 量子核机制：对量子核的实验揭示了基于系统规模（量子比特数量）的三机制行为：
  • 低量子比特：由于结构区分度弱，均匀采样具有竞争力。
  • 中等量子比特：随着核诱导出结构化的异质性 SVM 解，自适应分配产生了显著增益。
  • 高量子比特：核集中效应削弱了两种方法的信号，尽管自适应分配在资源使用方面仍然更高效。
• 成本效率：本文分析了量子测量成本与经典重训练开销之间的权衡。结论是，在典型的 QML 设定中（测量成本高且数据集规模中等），自适应方案提供了双重好处：提高分类器保真度并降低总体计算成本。

意义
本文确立了自适应测量分配作为学习噪声核时均匀采样的原则性且有效的替代方案。通过将重点从最小化全局估计误差转移到最小化噪声对特定学习任务（SVM 分类）的影响，所提出的方法在分类器保真度和计算效率方面提供了显著改进。这项工作对于量子机器学习尤为重要，因为在该领域中测量资源稀缺，且像核集中这样的现象构成了严峻挑战。结果表明，“智能”分配策略可以扩展基于核的学习的运行机制，使得在均匀采样会失败或成本 prohibitively 高昂的场景中进行有意义的训练成为可能。