受Kaczmarz启发的核典型相关分析加速方法：理论、算法及其在信息检索中的应用

《Neural Networks》：Kaczmarz-Inspired Acceleration for Kernel Canonical Correlation Analysis: Theory, Algorithms, and Its Applications to Information Retrieval

　　

摘要

典型相关分析（CCA）作为多元统计分析中的一种基本方法，能有效捕捉配对变量之间的线性关系。然而，其线性约束限制了其在复杂非线性依赖关系建模中的适用性。核典型相关分析（KCCA）通过实现非线性关系建模和高维特征选择克服了这一局限性。现有的KCCA方法在处理大规模数据时面临严重的计算瓶颈，主要源于其过高的内存和时间复杂度。为突破这些限制，我们开发了两种加速KCCA求解器，分别为KCCA-GRK和KCCA-MWRK，其方法是将已建立的贪心随机Kaczmarz（GRK）和最大加权残差Kaczmarz（MWRK）行选择原理应用于SVD重构的KCCA系统。我们的贡献具有KCCA特异性：由于重构后的系数矩阵具有正交归一化行，基于范数的Kaczmarz采样退化为均匀采样；KCCA-GRK和KCCA-MWRK分别通过残差驱动的随机规则和确定性规则恢复了有信息量的行选择。我们进一步建立了所提算法的显式收敛界和充分迭代次数估计。在一个合成数据集和四个真实世界数据集上的实验表明，所提方法在保持检索性能的同时，大幅减少了迭代次数和运行时间。

引言

从大规模数据中高效快速地识别最相关信息——无论是文本、视觉还是视频——是一个关键挑战。典型相关分析（CCA）（Hotelling, 2012）通过识别线性变换来应对这一挑战，该变换在低维空间中最大化两组变量之间的相关性。由于CCA能够揭示配对数据之间的多元关系，它在机器学习（Hardoon等, 2004b）、跨模态信息检索（Gong, Wang, Hodosh, Hockenmaier, Lazebnik, 2014; Rasiwasia, Pereira, Coviello, Doyle,兰克罗伊特, 吕维, 瓦斯孔塞洛斯, 2010）和生物信息学（Waaaijenborg, Verselewel de Witt Hamer, Zwinderman, 2008; Witten, Tibshirani, Hastie, 2009）等领域获得了广泛关注。然而，CCA存在若干固有局限：它仅限于建模线性关系，无法捕捉复杂的非线性依赖；它涉及求解广义特征值问题（Hsu等, 2012），其中样本协方差矩阵可能具有高维且奇异的特点，导致计算复杂度过高（Tao等, 2014）；在高维空间中容易过拟合，限制了泛化性能（He等, 2023）。

核典型相关分析（KCCA）（Melzer等, 2001）将传统CCA扩展到能够捕捉多元数据间的非线性依赖关系。通过利用核技巧，KCCA将原始变量隐式投影到高维再生核希尔伯特空间（RKHS）中，从而实现复杂非线性交互的建模，同时无需显式计算即可实现降维。由于KCCA能够揭示潜在的非线性关联，它在生物学和神经科学（Hardoon, Shawe-Taylor, Friman, 2004a; Vert, Kanehisa, 2002）、排序（Pan, You, Chen, Tao, Pang, 2013; Tao, Jin, Yuan, Xue, 2014）和信息检索（Hardoon, Szedmak, Shawe-Taylor, 2004b; Vinokourov, Cristianini, Shawe-Taylor, 2002）等领域展现了广泛的实用性。KCCA已在多个方向上得到扩展，以提升其适用性、鲁棒性和可扩展性。Yoshida等（2017）提出了一种两阶段KCCA算法，在高维空间中选取稀疏特征的同时捕捉多种非线性关联。Chen等（2022）引入了一种K-means聚类增强的特征融合方法，其中特征分类由情感标签的影响而非模态引导，从而提高了KCCA的有效性。Jin等（2024）开发了一种正则化KCCA框架，解决了非线性大规模过程系统中的监测难题。Huang等（2023）创建了一个增强KCCA框架，采用基于核的非线性映射来揭示RKHS投影数据中的内在线性依赖。Wu等（2025）设计了三种新颖的KCCA变体，融合了非线性、稀疏性和广义多视图能力，用于高维生物医学数据。

一旦核矩阵计算完成，KCCA的执行过程对于原始数据维度始终保持稳定（Akaho, Melzer, Reiter, Bischof, 2001）。然而，其核心计算瓶颈在于求解大规模特征值分解问题，对于海量数据集来说这是不可接受的。为减轻这一负担，基于随机梯度下降（SGD）的CCA算法应运而生（Ma等, 2015）。在SGD-CCA的基础上，Cai等（2016）提出了基于梯度的KCCA算法，显著提升了计算效率和泛化性能。Cai和Huang（2017）的后续工作开发了一种鲁棒公式，实现了严格的稳定性分析，进一步推动了该领域的发展。尽管有这些改进，基于SGD的KCCA算法仍然受限于收敛条件和停止准则，往往导致次优解和收敛效率低下。

近期发展利用随机迭代方法实现快速机器学习。Strohmer和Vershynin（2009）证明，当矩阵行按照其平方欧几里得范数比例选择时，随机Kaczmarz（RK）方法可以达到期望指数收敛率。在此基础上，Cai和Tang（2018）提出了KCCA-RK，将KCCA重构为线性矩阵方程组并整合RK迭代。通过避免基于奇异值分解（SVD）的KCCA求解器中固有的系数矩阵伪逆计算（Chu, Liao, Ng, Zhang, 2013a; Chu, Liao, Ng, Zhang, 2013b），KCCA-RK在保持泛化性能的同时显著加速了收敛。

行选择在Kaczmarz类方法的收敛中起核心作用。对于线性系统，He等（2023）提出了角度相关采样策略，Bai和Wu（2018）开发了贪心随机Kaczmarz（GRK）方法，Du和Gao（2019）分析了最大加权残差Kaczmarz（MWRK）方法。因此，GRK和MWRK均为一般线性系统的已确立行选择策略。我们的贡献在于将这些策略适应到KCCA的特定结构上并建立相应的收敛分析。虽然KCCA-RK避免了经典SVD-based KCCA求解器所需的计算昂贵的伪逆运算，但它操作于从KCCA的SVD重构中获得的线性矩阵方程。对应的系数矩阵为$?^T \in \mathbb{R}^{r_1 \times m}$和$V?^T \in \mathbb{R}^{r_2 \times m}$，其行是正交归一化的，因此具有相同的单位欧几里得范数。结果是，RK的范数比例采样概率分别退化为$1/r_1$和$1/r_2$，导致均匀随机采样，无法根据行范数区分不同方程。为解决这种基于范数的采样的结构性退化问题，我们开发了KCCA-GRK和KCCA-MWRK作为重构KCCA系统的残差驱动求解器。具体而言，KCCA-GRK构建基于残差的候选集并在该集内进行随机采样，而KCCA-MWRK直接选择具有最大加权残差的行。此外，我们为两种方法建立了直接的基于矩阵的收敛分析，避免了Cai和Tang（2018）中采用的矩阵向量化分解，并推导了显式收敛界和充分迭代次数估计。在一个合成数据集和四个真实检索数据集上的数值实验表明，KCCA-GRK和KCCA-MWRK在保持检索性能的同时，大幅减少了所需迭代次数和计算时间。

这些KCCA特定的方法和理论发展总结如下：

- 我们发现了KCCA-RK的一个KCCA特异性局限：基于SVD重构后，系数矩阵$?^T$和$V?^T$的行是正交归一化的，导致基于范数的RK采样规则退化为均匀采样。
- 基于已确立的GRK和MWRK行选择原理，我们提出了两个专门为SVD重构KCCA系统设计 的残差驱动求解器。KCCA-GRK使用基于残差的候选集与随机选择，而KCCA-MWRK确定性地选择具有最大加权残差的行。
- 我们为KCCA-GRK和KCCA-MWRK开发了直接的基于矩阵的收敛分析，避免了先前KCCA-RK分析中使用的矩阵向量化分解。
- 我们推导了显式收敛上界和充分迭代次数估计，表明所提残差驱动策略允许比KCCA-RK更紧的收缩因子，其中KCCA-MWRK在所提方法中具有最紧的界。
- 在跨语言文档检索和基于内容图像检索上的实验表明，所提方法在保持检索质量的同时，显著减少了运行时间和迭代次数。

本文其余部分组织如下。第2节介绍CCA和KCCA的理论背景。第3节介绍KCCA-RK、所提的KCCA-GRK和所提的KCCA-MWRK算法。第4节报告多个数据集上的实验结果。第5节总结本文。所有理论结果的证明见（附录A）。

各章节片段

背景

典型相关分析：设$x \in \mathbb{R}^{n_1}$和$y \in \mathbb{R}^{n_2}$为两个随机变量，$\{x_i\}_{i=1}^m$和$\{y_i\}_{i=1}^m$分别表示$x$和$y$的$m$个独立观测。定义相应矩阵$X = [x_1, \ldots, x_m] \in \mathbb{R}^{n_1 \times m}$和$Y = [y_1, \ldots, y_m] \in \mathbb{R}^{n_2 \times m}$。不失一般性（w.l.o.g.），我们假设$X$和$Y$均已中心化。CCA即求解如下优化问题：

$$\max_{w_x \in \mathbb{R}^{n_1}, w_y \in \mathbb{R}^{n_2}} \frac{w_x^T X Y^T w_y}{\sqrt{w_x^T X X^T w_x} \cdot \sqrt{w_y^T Y Y^T w_y}}$$

其中$w_x$和$w_y$是线性变换$X$和$Y$的权重向量。

所提算法与理论分析

基于第2节中CCA和KCCA的概述，本节：在第3.1节中系统化SVD-based KCCA的理论框架；在第3.1.2节中分析现有KCCA-RK方法的局限，重点关注收敛速度约束；分别在第3.2节和第3.3节中介绍所提的KCCA-GRK和KCCA-MWRK算法；并分别在第3.2.1节和第3.3.1节中建立所提算法收敛率的理论估计。

CRediT作者贡献声明

千左：调查研究、基金获取、正式分析。陆张：写作——审阅与编辑、软件。辛廖：软件、概念化。韩宇宣：写作——审阅与编辑。

利益冲突声明

作者声明他们不存在任何已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

致谢

我们感谢两位匿名审稿人对本文早期草稿提出的宝贵意见。我们感谢新加坡科技研究局生物信息学研究所的张晓微博士慷慨提供KCCA-ALB代码。我们也衷心感谢广东金融经济大学蔡嘉教授分享KCCA-RK代码以及围绕……所进行的深入讨论。

千左 | 陆张 | 辛廖 | 韩宇宣