用于加速支持张量回归的双重安全筛选框架

《Neurocomputing》：A double safe screening framework for accelerating support tensor regression

　　摘要
支持张量回归（STR）通过保留数据的内在结构，实现了对张量结构数据的有效处理，并展现出强大的预测性能。然而，其优化过程计算成本高昂，导致训练时间过长。为解决这一问题，我们提出了一种适用于一阶及高阶支持张量回归模型的安全筛选加速框架SSVI-DG。我们推导出了STR对偶解的稀疏性特征，为张量回归中的安全筛选提供了理论依据。基于这些特性，我们设计了两种安全筛选规则：基于变分不等式的安全筛选（SSVI）和基于对偶间隙的安全筛选（SSDG），分别用于优化过程的不同阶段。SSVI在训练前应用，可跨参数序列操作，有效降低问题规模，同时为后续优化提供高质量的初始可行解。SSDG则嵌入到迭代求解过程中，在优化过程中动态识别出无效变量。为进一步确保安全性，还加入了事后检查步骤，以识别可能被错误移除的变量并重新引入以便重新训练。通过结合这两种策略以及事后检查步骤，SSVI-DG在保证精确解的同时加快了优化速度。我们在合成数据以及七个真实世界的张量数据集上进行了大量实验，结果表明该框架在保持相近预测性能的同时显著降低了训练时间。实验结果进一步验证了该框架在一阶和支持高阶张量回归场景下的安全性与有效性。

引言
在许多实际应用中，数据往往具有高维结构，这类结构可方便地用张量来表示。典型例子包括灰度图像（二阶张量）[1]、[2]、[3]，彩色图像（三阶张量）[4]、[5]、[6]，以及彩色视频（四阶张量）[7]、[8]、[9]。作为经典的回归模型，支持向量回归（SVR）[10]、[11]、[12]因其强大的泛化能力和稳定性而被广泛采用。SVR不仅拥有坚实的理论基础，在模式识别[13]、[14]、金融时间序列预测[15]、交通流量预测[16]以及风速预测[17]等实际应用中也取得了优异成果。但由于SVR最初是为向量输入设计的，因此在应用于张量数据时需要进行向量化处理，这导致了维度灾难，使得计算复杂度和内存消耗大幅上升。此外，向量化还会破坏张量之间的内在结构关联，进而降低SVR的预测性能。

为克服这些局限，人们提出了支持张量回归（STR）[18]，该方法可直接处理张量数据并保留其结构信息。在张量回归领域，人们通过对系数张量施加不同的结构约束或进行张量分解，开发出了多种框架。例如，Wang等人[19]对系数张量施加了一阶约束，而Guo等人[18]则基于CANDECOMP/PARAFAC（CP）分解方法发展了STR及其变体[20]。具体而言，STR将系数张量分解为一组一阶张量的和，从而将原始优化问题转化为多个向量子问题。除了基于CP的方法之外，Liu等人[21]还提出了用于张量上张量回归的低秩张量列车（TT）系数估计框架。2017年，Song等人[22]提出了正则化多线性回归与选择方法（Remurs），该方法结合核范数和λ-范数，在保留张量结构的同时提升预测能力和可解释性。该模型可通过交替方向乘子法（ADMM）[23]高效求解，并在合成数据及fMRI数据集上表现出优于Lasso、Elastic Net及其多线性扩展方法的性能。尽管这些张量回归模型具备强大的预测能力，但由于训练过程中涉及张量运算、矩阵计算以及迭代优化步骤，它们仍然面临较高的计算难度。为提高效率，人们开始探索各种加速策略。2018年，人们提出了快速分阶段单位秩张量分解方法（SURF）[24]，该方法通过CP分解将系数张量转化为多个向量子问题，从而实现稀疏优化。近期，还有启发式加速方法被引入以进一步提升计算效率[25]。虽然这些方法能够显著缩短训练时间，但在计算效率、预测性能以及解的可靠性之间取得平衡，仍是张量回归领域的一个重要挑战。

近年来，张量分解方法的进步进一步提升了高阶张量计算的效率。例如，人们开发了自适应张量分解技术，通过利用张量模态之间的内在关联，并动态确定分解结构和秩，来实现高阶张量的恢复与压缩[26]。这类技术能有效控制模型复杂度并提高计算效率。此外，人们还研究了随机草图法以加速张量分解。针对Tucker分解，人们已经开发出了快速且精确的草图ALS算法，该算法能够在保持相当分解精度的同时降低计算成本[27]。在超光谱图像处理领域，人们也探讨了低秩张量分解技术[28]，通过低秩表示对空间-光谱结构进行建模，用于超分辨率处理和去噪等任务[29]、[30]。尽管在张量分解与因子化方面取得了诸多进展，但像STR这样的张量回归模型仍需对回归系数进行迭代优化，而反复求解大规模优化子问题在处理高维张量数据时仍具有较高的计算成本。因此，尽管快速张量分解技术已取得显著进展，但如何提高张量回归模型中优化过程的效率，依然是重要的研究方向。

正是出于这一挑战，我们聚焦于传统的STR模型，因为它在保持可靠优化行为的同时具备出色的预测性能。我们并非追求激进的加速方式，而是旨在开发一种稳定且安全的加速框架，该框架在提升计算效率的同时，还能保持预测性能和精确解。所提出的安全筛选框架可补充现有的快速张量分解技术，二者结合可进一步提升效率。安全筛选是一种有效的加速技术，它利用模型的稀疏性，在优化之前或优化过程中安全地筛选掉无效变量或样本，从而在不影响最优解的情况下降低计算成本。现有研究已成功将安全筛选技术应用于支持张量机（STM）等张量分类模型[31]。例如，Wang等人[32]提出了基于CP分解的STM两阶段安全筛选规则，而Li等人[33]则开发了一种融合CP、Tucker[20]以及张量列车（TT）[34]分解方法的通用筛选框架。然而，针对STR的安全筛选研究仍相对有限。尽管STR的对偶解也具有稀疏性，但其优化过程存在更多挑战，比如变量尺度更大，以及由于张量分解而导致样本矩阵不断变化，这使得基于现有SVR[35]或STM的筛选方法无法直接应用。

基于以上分析，本文提出了一种高效的安全筛选加速框架SSVI-DG，用于STR模型，该框架既适用于一阶支持张量回归（Rank-1 STR），也适用于高阶支持张量回归（HR-STR）。由于CP分解会将STR转化为多个向量子问题，因此核心思路是通过顺序筛选与动态筛选策略的结合来加速每个子问题的求解。具体而言，我们采用了快速优化算法——对偶坐标下降法（DCDM）[36]来高效处理每个子问题。在利用STR对偶解的稀疏性特征的基础上，我们进一步提出了两种安全筛选规则：基于变分不等式的安全筛选（SSVI）和基于对偶间隙的安全筛选（SSDG）。SSVI用于对参数序列进行顺序筛选，而SSDG则嵌入到迭代优化过程中，以便在训练过程中动态移除无效变量。此外，我们还引入了基于Karush-Kuhn-Tucker（KKT）条件的验证方法[37]，以确保筛选的正确性并保持最优性。通过将顺序筛选与动态筛选整合为一个统一框架，所提出的SSVI-DG框架在保持预测性能和精确解的同时，大幅降低了计算成本。总体而言，本文的主要贡献如下：
(1) 针对支持张量回归，我们基于CP分解后子问题的结构，推导出了相关的理论性质。这些性质揭示了对偶解的稀疏性，为开发安全筛选规则以加速求解过程提供了理论基础。
(2) 我们提出了一种名为SSVI-DG的高效安全筛选加速框架，用于STR模型。该框架结合了基于SSVI的顺序筛选、基于SSDG的动态筛选以及事后检查步骤，能够在不改变原问题最优解的情况下，高效地加速优化前的准备及优化过程中的计算。
(3) 我们在一阶支持张量回归和高阶支持张量回归模型上进行了大量实验，以评估其预测性能、计算效率以及实验安全性。同时，我们还定义了两个评价指标来衡量基于筛选方法的实验安全性。

本文结构如下：第2节简要回顾了基本张量概念、STR模型以及安全筛选规则；第3节分析了一阶支持张量回归和高阶支持张量回归的稀疏性特征；第4节介绍了针对这两种模型的安全筛选规则以及SSVI-DG框架；第5节通过大量数值实验评估了所提方法的有效性；最后，第6节对全文进行了总结。

相关工作
本节首先回顾了文中使用的基本张量运算与符号，随后介绍了作为本研究主要学习框架的支持张量回归（STR）模型。接着总结了现有的安全筛选方法，并进一步探讨了为STR开发安全筛选规则的挑战。

两种支持张量回归模型及其稀疏性
在本节中，我们介绍了两种STR模型——一阶支持张量回归和高阶支持张量回归，以及它们对应的对偶形式和求解策略。具体而言，我们在对偶空间中对这两种模型进行了重新表述，这一视角有助于设计高效的优化算法。同时，我们还推导出了对偶解的稀疏性特征，这些特征将为后续开发安全筛选规则提供理论基础。

SSVI-DG：一种用于一阶支持张量回归和高阶支持张量回归的安全筛选框架
为高效求解一阶支持张量回归和高阶支持张量回归问题，本节提出了两种安全筛选规则，即SSVI和SSDG。这些筛选规则针对STR模型优化过程中出现的子问题设计，旨在通过安全识别无效变量来降低计算复杂度。为确保所提框架的安全性，我们还引入了KKT条件检验策略，用于识别并恢复可能被错误筛选掉的变量。

数值实验
在本节中，我们通过数值实验来评估所提出的安全筛选框架。实验从三个角度展开：首先，使用合成数据验证所提出的筛选规则是否能在不改变预测性能的前提下加速优化过程；其次，使用七个真实世界数据集，评估在引入SSVI-DG框架之后，包括一阶支持张量回归和高阶支持张量回归在内的现有STR模型的预测性能。

结论
在本研究中，我们提出了SSVI-DG，这是一种用于支持张量回归的安全筛选加速框架，其目标是在保持安全筛选所保障的解的一致性的同时，降低STR模型的高昂计算成本。我们分析了对偶解的稀疏性特征，这些特征为识别无效变量提供了理论依据。基于这些特征，我们开发了SSVI和SSDG两种筛选规则。结合KKT条件检验策略，这些规则共同构成了高效的优化加速方案。